> Interesting idea! It seems the real issue is "marking and sweeping" the > vtables. A stab at categorizing the approaches: > > a) > Force vtables to be as similar to ordinary java objects as possible. The > upside: existing GC algorithms will work unaltered. The downside is > vtables > of vtables of vtables... This has already been discussed at length. > > b) > Force vtables to live and die in a unique "vtable space". The big > challenge seems to be building a custom GC algorithm that is simpler and > less invasive than doing a) above. Most likely the performance of the > custom GC algorithm will never be an issue. Vtables have some very > interesting properties that may make this doable. The 4 (or 8) bytes at > offset "K" always point to a class structure which, in turn, always has a > pointer at offset "Z" back to the vtable. There are way fewer vtables > than > objects. For practical reasons, it can be assumed that vtables will > always > be pinned. The number of class structs/objects is no greater than the > number of vtables.
I guess ... the issue of where vtables and other classloader related structures lives seems to me to be simple engineering. Whether they are malloced in the C heap or 'new'ed in an immovable Java heap makes little difference. After all they are very very small compared to the rest of the heap. > A half-baked scheme that might be good enough: Partition off 50 megabytes > as a hard, fixed vtables space. Then do a word-by-word scan to pick up > candidate pointers class structs. Then filter the candidate class struct > pointers by verifying the back pointers. Occasionally there might be > "floating garbage" with this approach but a valid, live vtable should > never > be accidentally freed. The filtered set are the "live" vtables. Next > scan > the live vtables looking for members that were never marked by the regular > GC as mentioned below. When found, zero the vtable, link-list on a free > vtable space list, mark the class struct as "vtable-less". Process the > "vtable-less" class struct, etc... This sounds a bit complicated - i'm sure it could be done by maintaining linked lists of all the classes loaded by each classloader (pointing to vtables from there) and traversing it. Traverse this once, propagating the mark bits upwards and you are done. > It seems as long as part of the system is built using garbage collected > java > objects and part of the system is built using malloc/free C structs, the > problem of releasing connected objects/C_structs will be messy and hacky. > In a sense, this issue is really a motivation for re-writing the whole VM > in > Java... hmmm... Well in Java-in-Java you would hardly want to do a full trace operation for every vtable pointer - that would be quite costly imo, because in a full gc you do a test-and-set, then conditionally copy and/or enqueue for scanning. So there's a dependent load and conditional store, and the test to detect the gc policy for the vtable space. And you really don't want to have moveable vtables. The cost of updating the forwarding pointers alone would be a killer, let alone the engineering difficulties. There are definitely reasons to write a VM in java, but I don't believe this is one of them! As I say below I wouldn't do class unloading on top of the standard GC mechanism - I would do it in the VM, using a hook from the GC's tracing. > > On 10/31/06, Robin Garner <[EMAIL PROTECTED]> wrote: >> >> Actually, just thinking about how I would implement this in JikesRVM, I >> would use the reachability based algorithm, but piggyback on the >> existing GC mechanisms: >> >> - Allocate a byte (or word) in each vtable for the purpose of tracking >> class reachability. >> - Periodically, at a time when no GC is running (even the most >> aggressive concurrent GC algorithms have these, I believe), zero this >> flag across all vtables. This is the beginning of a class-unloading >> epoch. >> - During each GC, when the GC is fetching the GC map for an object, >> *unconditionally* write a value to the class reachability byte. It may >> make sense for this byte to be in either the first cache-line of the >> vtable, or the cache line that points to the GC map - just make sure the >> mark operation doesn't in general fetch an additional cache line. >> - At a point in the sufficiently far future, when all reachable objects >> are known to have been traced by the GC, sweep the vtables and check the >> reachability of the classloaders. >> >> The features of this approach are: >> >> - Minimal additional work at GC time. The additional write will cause >> some additional memory traffic, but a) it's to memory that is already >> guaranteed to be in L1 cache, and b) it's an unconditional independent >> write, and c) multiple writes to common classes will be absorbed by the >> write buffer. >> >> - Space cost of at most 1 word per vtable. >> >> - This works whether vtables are objects or VM structures >> >> - If the relationship between a class and a vtable is not 1:1, this only >> need affect the periodic sweep process, which should be infrequent and >> small compared to a GC. >> >> - shouldn't need a stop-the-world at any point. >> >> I've implemented and tested the GC-relevant part of this in JikesRVM, >> and the GC time overhead appears to be just under 1% in the MMTk >> MarkSweep collector. >> >> cheers, >> Robin >> > > > > -- > Weldon Washburn > Intel Enterprise Solutions Software Division >
