[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: JIT pluggability (GC Interface)
From: |
Chris Gray |
Subject: |
Re: JIT pluggability (GC Interface) |
Date: |
Mon, 12 Jan 2004 21:52:53 +0100 |
On Monday 12 January 2004 21:11, Patrik Reali wrote:
> Hi!
>
> let me add my 0.02 cents (of euro). :-)
Yup, it's "soldi" time. :)
> GC Interface:
>
> let's divide the GCs in 2x2 categories:
>
> * (TA) type-accurate: know where the pointers inside the objects are
> * (CO) conservative: guess where the pointers inside the objects are
>
> and
>
> * (NC) non-concurrent: the GC is the only thread running during the
> collection
> * (CI) concurrent / incremental: the GC and the mutator run
> (pseudo-)concurrently
CI corresponds to my type 1, NC to type 2.
> These categories affect the interface between compiler, generated code, and
> the gc itself.
Is anybody using CO?
> Static information (TA vs. CO):
> * All GCs need a hook into the memory management to return the blocks to
> the free-list.
> * All GCs need to access the whole heap
> * TA GCs need a root-set from which the collection starts: the list of all
> static fields, all pointers on the stack of each thread, all pointers in
> the CPU registers (and those in the stack when the thread is preemted) [The
> registers depend in fact on the compiler optimizations: if some value may
> live longer in a register than in a variable then yes, otherwise if the
> compiler ensures that all pointers in the registers are also anchored
> somewhere in a variable, then no]
> The list of static fields can be obtained through reflection; pointers on
> the stack are more complicated to get.
> * TA GCs need a type descriptor containing the pointer offsets inside each
> type; arrays of references are also to be collected
>
> Code Instrumentation (NC vs. CI):
> * NC GCs do not need code instrumentation
Not so fast.
A NC GC typically needs to bring all (non-GC) threads to a "safe" state
before it can run: a "safe" state is one in which all references from a
thread to the heap are visible to GC. So some degree of instrumentation is
needed in order to determine when a thread is "safe", and maybe also a
mechanism to politely ask a thread to become "safe" at the earliest
opportunity.
> * some CI GCs define code points where the GC can run
> * some CI use read barriers (each pointer read operation is instrumented)
> * some CI use write barriers (each pointer store operation is instrumented)
> * some GCs use master-lists (each pointer points to the real pointer which
> is present only once, thus moving an object correspond to moving a
> master-pointer instead of each reference)
AKA "handles".
>
> Example: Jaos + Aos Kernel
> The Aos kernel provides memory allocation with a mark & sweep GC; the mark
> operation is implemented using the pointer rotation algorithm (Deutsch
> Waite Schorre). This is a "stop the world" non-concurrent GC (even in the
> multiprocessor version of the kernel).
> The GC information is provided by the Jaos classloader (because it performs
> the field allocation during the load); each class has a module (a runtime
> compilation-unit) with the code, statics and a list of static pointers, and
> a type descriptor containing the pointer offsets, the method table, and the
> type hierarchy (those are then patched by the linker). The stack traversal
> is conservative.
>
> A few pointers:
> * http://www.memorymanagement.org
> * Paul Wilson; Uniprocessor Garbage Collection Techniques; Proceedings of
> the Memory Management, International Workshop, Saint Malo, France, Sep 1992
> (postscript 764KB; ftp://ftp.cs.utexas.edu/pub/garbage/bigsurv.ps)
> * Garbage Collection in Oberon: http://www.oberon.ethz.ch/gc/
> * Garbage Collection in .NET: (part 1)
> <http://msdn.microsoft.com/msdnmag/issues/1100/GCI/GCI.asp> and (part 2)
> <http://msdn.microsoft.com/msdnmag/nettop.asp?page=/msdnmag/issues/1200/GCI
> 2/GCI2.asp>
> * Slides from lecture "System Software" on Garbage Collection:
> http://www.cs.inf.ethz.ch/37-201/slides/ssw03_memorymanagement_2.pdf
And if you don't mind killing trees: Richard Jones, Rafael Lins; Garbage
Collection; John Wiley and Sons, 1996 (ISBN 0 471 94148 4).
> I hope this clarifies more than it confuses....
>
> -Patrik
>
>
> --On Samstag, 10. Januar 2004 11:29 +0100 Chris Gray <address@hidden>
>
> wrote:
> > On Friday 09 January 2004 09:45, Sascha Brawer wrote:
> >> Tom Tromey <address@hidden> wrote on Thu, 8 Jan 2004 17:48:59 -0700:
> >> > [standard pluggable JIT interface]
> >>
> >> This would indeed be quite nice, IMHO.
> >
> > IMHO2 (that should probably be 3 or 4 by now).
> >
> > I suspect that the interface to GC will be hard to define, though. There
> > are several possible models, including:
> > 1. The mutator (JITted code) tells GC, "hey! I just mutated
> > something!", whereupon GC either (a) aborts the current attempt to mark
> > the heap or (b) makes a note to re-mark the affected objects before
> > doing a sweep. 2. No one is allowed to mutate anything during the
> > marking process, so a protocol is devised which ensures this without
> > deadlock.
> >
> > And that's only counting mark-and-sweep collectors ...
> >
> >> > Language choice for API.
> >> > The obvious choices being:
> >> > C lowest common denominator
> >> > C++ next-to-lowest common denominator :-) provides some
> >> > abstraction benefit, maybe
> >> > Java using our own tools...
> >>
> >> There are some users of Classpath who cannot execute any C code, such as
> >> Jaos and JNodeOS. If the pluggable JIT interface was in Java, these
> >> systems would be able to use it (assuming that someone writes a JITter
> >> in Java, like IBM did with their JalapeƱo/Jikes RVM).
> >>
> >> Also, I'd assume that the interface would be rather narrow in the sense
> >> that it wouldn't get invoked very often in the direction VM --> JIT;
> >> probably once for each class or method to be compiled. But the JIT would
> >> presumably have to call a lot into the VM (for retrieving field offsets
> >> etc.).
> >>
> >> > ABI Issues
> >>
> >> According to IBM's publications and web pages, Jikes RVM seems to nicely
> >> cope with different ABIs (such as the slightly different calling
> >> conventions for AIX and MacOS X). Maybe, their code could serve as an
> >> example for how to structure the JIT interface so it can cope with
> >> different ABIs.
> >>
> >> Jaos works on top of an abstraction called "object kernel", which
> >> basically is an API to garbage collection, synchronization, etc. Patrik
> >> Reali might be able to tell the list more about this.
> >>
> >> > General API
> >> >
> >> > - Verifier interface?
> >> > Does the verifier do all checking or does it impose some
> >> > requirements on the JIT/interpreter? (Some verifiers choose to
> >> > delay some checking until interpretation.)
> >> > Does the JIT want/need information already computed by the verifier?
> >> > For instance basic blocks or the type map at a given statement.
> >>
> >> I think it would be very wasteful to compute this information twice, but
> >> it might be very difficult to define common data structures that are
> >> suitable for everyone. Might it be sufficient if a verifier could store
> >> some opaque reference for later use by the JIT?
> >>
> >> AegisVM writes that they have developed a modular bytecode verification
> >> architecture, but I didn't look at this yet.
> >>
> >> Another thing that might be interesting to share is parts of a compiler
> >> backend, such as assemblers.
> >>
> >> -- Sascha
> >>
> >> Sascha Brawer, address@hidden, http://www.dandelis.ch/people/brawer/
> >>
> >>
> >>
> >>
> >> _______________________________________________
> >> Classpath mailing list
> >> address@hidden
> >> http://mail.gnu.org/mailman/listinfo/classpath
> >
> > --
> > Chris Gray /k/ Embedded Java Solutions
> > Embedded & Mobile Java, OSGi http://www.kiffer.be/k/
> > address@hidden +32 477 599 703
> >
> >
> > _______________________________________________
> > Classpath mailing list
> > address@hidden
> > http://mail.gnu.org/mailman/listinfo/classpath
>
> --------------------------------
> Patrik Reali
> http://www.reali.ch/~patrik/
> http://www.oberon.ethz.ch/jaos/
> http://www.classpath.org/
> http://iiop-net.sourceforge.net/
--
Chris Gray /k/ Embedded Java Solutions
Embedded & Mobile Java, OSGi http://www.kiffer.be/k/
address@hidden +32 477 599 703
- JIT pluggability, Tom Tromey, 2004/01/08
- Re: JIT pluggability, Sascha Brawer, 2004/01/09
- Re: JIT pluggability (ABI Issues), Patrik Reali, 2004/01/12
- Re: JIT pluggability (ABI Issues), Chris Gray, 2004/01/13
- Re: JIT pluggability (ABI Issues), shudo, 2004/01/13
- Re: JIT pluggability (ABI Issues), Sascha Brawer, 2004/01/13
Re: JIT pluggability, Artur Biesiadowski, 2004/01/09
Re: JIT pluggability, Niranjan Suri, 2004/01/10