Garbage collector/tracing the stack/registers

[AndrewAPrice]

I'm trying to figure out how you would walk up the stack and registers in a garbage collector on JIT'ed code.

Here's one scenario I came up with: In a single threaded environment, every time I call a function pointer or perform a memory allocation, I have to make sure that any registers containing an object pointer is spilled to the stack.

I'll have to lay out my stack frame in a consistent way so my GC can scan it, something like this (growing down):
- Previous BP
- Number of GC pointers
- GC pointer 0
- GC pointer 1
...
- GC pointer n
- Shadow space for other variables

Then when my GC is invoked, it can walk up the stack frame by following the BP (EBP/RBP) pointers.

I do have to handle a special case. That is when we enter native code C. When I thunk from native->managed (JIT'ed) code I could put a little dummy frame where the "number of GC pointers" is 0xFFFF FFFF FFFF FFFF, and that alerts my GC to stop walking the stack because we're about to reach native code.

This fails if my JIT'ed environment is called recursively:
native block 1->managed block 1->native block 2->managed block 2

If the GC is invoked in managed block 2, it'll walk up the stack, reach native block 2, stop walking and we couldn't trace all references in managed block 1.

My solution would be to pass a "managed BP" in my managed->native thunks, and pass that "managed BP" back in my native->managed thunks, then in my stack frame the "previous BP" pointers can jump over the the native block. The thunks can either read/write this from memory (e.g. a thread->lastBP field somewhere) - but then I may be accessing arbitrary memory and breaking the CPU cache - or I can pass this as a parameter back to native code and the burden goes to the programmer to remember to pass this back into the VM when we call managed code again.

Now this wouldn't work in a multithreaded environment. Because if we stop all threads at some arbitrary point in time, we can't assume:
a) That all threads have all of their pointers spilled on the stack. Even if we defensively spill these registers on the stack between every assignment - there will be points of time - such as when a function call returns an object - that it exists purely in a register and not in the stack - unless I always have one register (e.g. r15) that is only ever used for returning and temporarily holding pointers, and my GC can check that when tracing a thread.

b) We will be in managed code. If we stop in native code, then all bets with scanning the registers and stacks are off. Unless again we are writing to thread->lastBP everytime we thunk into native code, and clearing it everytime we are entering managed code, and when we walk up the stack we start walking from either thread->lastBP if it's set (meaning we're in native code) or the RBP pointer (meaning we're in managed code.) But what if our native code is holding to a pointer to something?

But.. a) I've lost a register, b) I'm writing to memory (thread->lastBP) every time I jump between native and managed code and we still wouldn't find everything native code is holding a pointer to.

There is a lot of information online about garbage collectors but I've found very little information about how you would trace around registers and in multithreaded environment. Is there a better way to do this?

[AndrewAPrice]

The multithreaded problem is a tricky one, because I'm planning on doing a compacting GC which means pointers can move. If a thread has an object on the stack, but has read it into a register to pass it as a parameter or something - the GC may update the pointer on the stack but not the dangling pointer in the register. So we may need synchronize points where the GC will run.

The GC needs a way to know when threads can reach a sync point in which all registers are spilled onto the stack. For example, a function epilog may be a good place to insert something like this:
if(gc_waiting) sleep();

Then in the garbage collector I keep spinning over all threads (except the GC's thread) until they are asleep. That's extra overhead stuck into a the end of functions though. But then I know that when a thread falls asleep - it's in managed code, all registers are spilled to the stack, and any returned pointer is in r15.

[Owen]

Your compiler needs

• A table somewhere, which contains information about where GC objects are at any particular moment in time. One simple but slow option is to maintain this as a linked list which the code manipulates as it allocates/deallocates objects; the better option is to maintain a map as a separate table
• Safe points. These are locations at which it is OK for the GC to step in. You might have these at the start of every function, and at the start of every loop iteration for example. The general technique is to poll a global bit which says to pause

One example of these maps might take the form

Code: Select all

struct FunctionMap {
    uint32_t pointerRegisters; // bitfield
    uint32_t returnAddressOffset; // offset at which the function return address may be found
    uint32_t stackPointerCount; // number of pointers on the stack
    uint32_t pointerStackOffsets[]; // offset of each pointer on the stack
};

You would chase this until you found a map which informed you it was an "entrypoint from native code", at which point you might use alternative methods (e.g. linked list of roots) to track things

This linked list might contain entries like

• Stack Root @ 0xFEEDFACE (trace the stack from here)
• Native root @ 0xFEED0000 (root in some native code which interacts with the VM)
• Native root @ 0xF00DF00D (same)
• Interpreter stack @ 0xF00D0000 (stack for the interpreter)
• Stack Root @ 0xF00C8000
• End

Also, make sure that native code can say "I'm exiting the VM now (i.e. this thread is at a safe point)" so that file I/O doesn't hold up collection

[AndrewAPrice]

Also, make sure that native code can say "I'm exiting the VM now (i.e. this thread is at a safe point)" so that file I/O doesn't hold up collection

The problem is.. what about managed objects being held by native code? What if the IO is writing into a managed buffer?

Since it is a compacting GC, pointers can update - even in native code, so to be safe we need to wait on native code. We also have to wrap managed pointers:

Code: Select all

class RootedPtr {
public:
   RootedPtr() {
     // add to list of roots
   }

   ~RootedPtr() {
     // remove from list of roots
   }

   RootedPtr *Prev;
   RootedPtr *Next;

   volatile void *Ptr;
}

Then pass around RootedPtrs everywhere in native code.

[Combuster]

Java has explicit lock operations on arrays, so that it's contents can be accessed from unsafe languages without them risking object movement.

[Owen]

The other thing JNI does is make the jobject (etc) that the JNI return be /handles/. Generally, they're pointers to a pointer to the actual object. It has two handle tables; the global table (which you explicitly create and delete) and the local tables (which form a stack - a new local frame is established each time control transitions into native code and destroyed when you return from it. If you want to, you can manually push/pop local frames also, and the pop function takes as a parameter one object to "rehome" in the parent frame (i.e. to be returned)

If you do this, you can collect at any point during native code execution because native code isn't touching the handles directly. Or, if the cost of locking and unlocking the handle table is too expensive, add functions such that the native code can explicitly say "I'm not touching VM objects any more for a while", so you can GC even when the code is blocked in read() (Indeed, this might even be an ideal time to do a collection)

[SpyderTL]

I'm not far enough along on my OS to have figured out how all of this is going to work, but here are some general ideas that I've been playing with. Maybe they will help you.

If you are running managed code, you should have access to reflection information about each objects type. That reflection information should be able to provide your GC with enough information to walk the object graph of each object on the stack, and in each register. Your GC will just need to know whether each "object" is a simple value (int), a (relative) pointer to a struct, or a reference to another object.

In order to move objects in memory, you will either need a table/list of pointers to those objects (and your references to objects are simply indexes into this table), or you will need a table/list that contains every reference from one object to another. I'm leaning toward the first option.

For non-managed code, you will need to be able to flag an object as non-movable while it is being accessed by non-managed code. The .NET CLR refers to this as "pinning" an object.

This is all high-level and overly simplified, of course. I'll have to deal with this issue myself before too long, so I'm also open to suggestions on this topic.

[AndrewAPrice]

In a multithreaded environment, we could sold the problem of stopping threads arbitrarily by giving the programmer control of when its safe to execute the GC.

Safe times to call the GC:

- The allocate is called. Sleeps if the garbage collector in another thread wants to run.
- A thread manually calls GC.Update(). Sleeps if the garbage collector in another thread wants to run, otherwise continues running. You can put this in update loops.
- The thread is already asleep. Safe to GC as everything will be on the stack.


But I don't like this approach because one of the purpose of multithreading is to prevent another thread (that may be stuck in an infinite loop) from freezing the entire application.