Let’s say it is a concurrent mark-and-sweep garbage collector.
When such GC handles constant pointers it just walks through them (starting from roots), and marks every encountered data block. Then sweeps everything unmarked. A client code should mark the data blocks it uses as roots.
But what to do with variables? Here is a situation:
Vis a variable, which stores a pointer to objectA.Thread 1readsVand suspends.Thread 2modifiesVand makes it point to objectB.- The garbage collector runs its “mark” phase and encounters that
Ais no longer referenced, then deallocates it during the “sweep” phase. Thread 1awakens and tries to useA(already read fromVat step 2) by marking it as root. And fails, becauseAis no longer exists.
So, how to handle this?
The Thread 2 can mark the replaced object A with a special do-not-remove flag (similar flag is used for newly allocated objects). But when this flag should be removed? Of course Thread 1 could do that. But Thread 2 knows nothing about Thread 1, and thus can not be sure that this will be done ever. This may lead to A will never be freed. And if GC will remove that flag, then nothing prevents A from being removed when GC runs for the second time…
The on-the-fly mark-and-sweep garbage collector descriptions I’ve read just mention that the replaced object should be “grayed”. But without any specifics. A link to a more detailed description of the solution would be highly appreciated.
Depending on the precise details of the garbage collector implementation, this may not be a problem at all in your step 4. For example, in step 2, thread 1 presumably reads V into a register. The garbage collector will probably need to examine the contents of the registers for all active (running and suspended) threads to see if there is a reference to any object held in the registers.
Inevitably, a garbage collector implementation is tightly coupled to the operating (and threading) environment in which it runs. There are many implementation techniques for ensuring that all stored and transient references are considered.
4
You have to mark local variables sometime during the mark phase. All local variables, including those that normally live on stack. Somehow.
I additionally think it has to be done during the synchronous (all mutators stopped) phase of scanning modified objects. In fact the same problem might arise even without considering local variables/registers. Consider object A pointing to null and object B pointing to C. Now you scan object A, a mutator thread comes, copies the reference to C from B to A, nulls out B. And now you get around to scanning B. And C slipped under your fingers.
I don’t know about any way for dealing with this that wouldn’t involve stopping the mutators. The usual technique is at the end of mark phase to stop all mutators and re-mark all objects that they mutated during the main marking phase. And include stacks and registers in that.
Marking registers is normally worked around by doing it synchronously by calling the collector in the thread sometimes. Inside the collector function, only it’s own local variables (which are not roots) can be in registers, all other local variables in the call chain are on stack, so you can walk the stack.
Alternatively you can send a signal to the thread. The signal handler will again force all variables on the stack, so you can walk them. Disadvantage of this method is that it is platform dependent.
10