Projects

[Jonathan P. Olson]

On Wed, 03 May 2000, Tom Tromey wrote:
>>>>>> "Jon" == Jonathan P Olson <olson@mmsi.com> writes:
>
>Jon> I put write barriers into g++ and gcj over a year ago and have
>Jon> been using it on our embedded products that use Super-H,
>Jon> StrongARM, and AMD 29k processors.
>
>We definitely have to get this work into gcc.  Can we do that?  From
>you we'd need patches (that are in accordance with the GNU coding
>standards) and paperwork.  Then we'd have to convince the gcc
>maintainers to accept them.
>
>Last time you posted about these patches and about your
>exception-handling changes, we really dropped the ball.  I'm sorry
>about that.  I'd like to see if we can make amends this time around.

Last year shortly after we talked about the exception handling code,
I went to Perth to work on a job there for about 6 months.  Actually,
we sort of both dropped the ball.  How do I get a copy of the paperwork?
Can you email a copy to sign?  Who do you need to sign it?  I'm CTO
here at MMS, is that OK?  Who accepts patches for `gcc'?  On what
criteria do they accept them?

No problem generating the patches.  After all, they're only about a couple
dozen lines against the C source code.  Note, however, that somebody
needs to write up the write_barrier patterns for all the supported
architectures.  I can give you the a29k, arm, and super-h.  Maybe
somebody else can do the more important architectures like x86,
sparc, and ppc.

Against what version of gcc do the patches need to be made?  Currently,
I'm using egcs-2.92 for development.  If the patches need to be against
gcc 2.95, I'll need to integrate and test out everything against the new
compiler.   I've been planning on doing that anyway to get the inner
class support for Java, but not quite yet.

>It would definitely be best to bring up the two things separately with
>the gcc hackers, though, because I have a feeling that changes to
>exception handling are going to be a lot harder than write barriers.
>

The exception handling patches are definitely alot messier than write
barriers.  Exceptions in gcc are currently quite broken on many architectures
and terribly inefficient on others.  There are two different exception handling
strategies intermingled in the gcc code.  Adding a third makes an enormous
spaghetti bowl and is contrary to the overall goal of eliminating compilation
options.  I opted for just replacing the existing code, but I doubt if that's
politically acceptable for gcc in general since libraries are currently built
using the existing mechanism(s).

I designed a very space efficient exception mechanism for `gcj', but never
got these same patches integrated with `g++'.  Problem with c++ is that
it allows you to throw ANYTHING, even an int, double, or stack allocated
object.  Java at least requires an exception to be a Throwable object.
For c++, I'd probably wrap up whatever is being thrown into a new Exception
object so the catch mechanism can more easily introspect into its type.
In addition, a robust exception mechanism is best implemented in the
presence of a garbage collector.  This allows GC to clean up after memory
allocated both by the application and the exception throwing mechanism.

Is it acceptable to require GC with exception handling to eliminate memory
leaks?

>Jon> Note that write barriers allow the garbage collector to run at
>Jon> low priority and not affect other time critical tasks.  The way I
>Jon> implemented them, they do not allow the implementation of a
>Jon> precise collector, since the write barrier traps only occur
>Jon> during garbage collection.
>
>I assume this is a feature of the underlying write barrier code (i.e.,
>its expansion on a particular architecture) and not something
>intrinsic to the whole idea of compiler-supported write barriers in
>gcc?  Hmm..  I find it hard to explain what I mean here.
>

Precise collection implies that there is enough information at run-time
for GC to know exactly what memory locations contain pointers.
This is really not a write-barrier issue but rather having the compiler
generate alot of run-time type information about objects and what
locations within objects contain pointers.  Precise collectors have the
following advantages.

  1) They avoid memory lossage from floating point numbers and
      integers which `look' like pointers.
  2) They allow the implementation of copying collectors.
  3) They avoid scanning memory which does not contain pointers.

In my opinion, 1) isn't significant.  The additional memory required for
the run-time type information far exceeds the memory lossage of pointer
aliasing.

Option 2) just isn't practical in a C or C++ environment.  There are
just too many registers, unions, assembly code, etc., which contain
pointers to realistically relocate them in a copying collector.  I toyed
around with the idea of giving pointers an extra level of indirection
in `gcj' but decided that this would make Java and C++ too incompatible
and cost too much in code efficiency because pointers could never be
promoted to registers.

Option 3) is the only real excuse.  In typical embedded systems, the
heap is small and never swapped so the penalty of scanning pointerless
memory is small.  However even on a Unix implementation, for 3) to
be an advantage GC must allocate pointerless allocations to different
memory blocks than pointerful allocations.  Making a distinction at
allocation time between allocations which contain no pointers like large
character buffers vs. pointerful objects eliminate many of the performance
advantages you'll get with a precise collector.  In my opinion, the precise
collector will probably use more time per pointer checked than the
imprecise collector as it must interpret the run-time type information
to determine which memory locations really contain pointers.

>Jon> This implementation maintains a global write-barrier threshold
>Jon> register in a location easily accessible to the run-time
>Jon> environment.
>
>Is this something that can be easily changed?
>

This write-barrier implementation merely invokes a RTL pattern in the
compiler back end whenever the compiler writes to a pointer.  This
RTL pattern is free to do anything, but it should be very fast.  The purpose
of this write barrier (whether you're implementing a precise or imprecise GC)
is to inform the collector that the object which this pointer references
is live and should not be collected.  When GC is idle, write barriers
aren't important, should be a NOP, and should be as fast as possible.

>Jon> As you can see, the target specific code for the write barriers
>Jon> is really pretty simple.  It executes an extra 1-4 instructions
>Jon> per pointer write when collection is not running.
>
>If this requires hooks into the scheduler, then this approach will be
>a problem in general (e.g., POSIX systems).
>

For a collector to be preemptible, it must know about all pointers that
change during the course of its collection.  For application code,
the GCC write barriers handle this.  When a thread is executes, however,
code executes which modifies its registers and stack which is not write
barriered.  To handle this, GC can take one of two approaches:

  1) Disable thread scheduling while scanning thread stacks and
      register contexts.
  2) Rescan any thread contexts which get run while the collector
      is scanning threads.

If you have a totally uncooperative threading system, the collector
can always choose approach 1) which increases scheduling latency.
Adding a simple hook to the scheduler allows you to leave the
scheduler enabled while scanning thread contexts.

>Our ultimate goal is to allow different write barrier implementations
>depending on the underlying GC and the system.  Ideally we'd also like
>to have support for precise GC and a copying GC -- but the latter
>might be too hard (there is a paper about this that I have lying
>around; you have to augment the code with tables describing how
>pointers might be hidden).
>
>Tom

Replacing the write barrier implementation is merely linking with
a library containing the desired write barrier code.  For example,
if an `arm' is writing register `r4', the compiler might generate the
following code to tell GC that the object pointed to by `r4' is still
live.

	str	r4,[r5]
	bl	__write_barrier_r4

The code that implements the barrier can be anything you like that's appropriate
for the collector you're using, however I'd recommend statically
linking the write barrier library to avoid the overhead of dynamically
linked calls.

Regarding precise and copying GCs, see my comments above.  In a C
or C++ environment I just don't see how they're justifyable.

-- 
Jon Olson, Modular Mining Systems
	   3289 E. Hemisphere Loop
	   Tucson, AZ 85706
olson@mmsi.com
Phone:	(520)746-9127
Fax:	(520)889-5790