8

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:

  1. V is a variable, which stores a pointer to object A.
  2. Thread 1 reads V and suspends.
  3. Thread 2 modifies V and makes it point to object B.
  4. The garbage collector runs its "mark" phase and encounters that A is no longer referenced, then deallocates it during the "sweep" phase.
  5. Thread 1 awakens and tries to use A (already read from V at step 2) by marking it as root. And fails, because A is 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.

lorus
  • 497
  • 1
  • 3
  • 10

2 Answers2

4

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.

Greg Hewgill
  • 10,231
  • But is there any way to do it in a platform-independent way? The register may contain the data, which only looks like a pointer, but in fact it is not. My GC implementation is exact and relies on the fact that any pointer it processes points to a data block of certain structure. – lorus Mar 06 '13 at 04:08
  • Hmm, but this is an idea! I can place such such pointer to some known place in the stack (or thread-local variable) and make GC examine it. – lorus Mar 06 '13 at 04:10
  • @lorus - for many garbage collectors, the tables generated by the compiler tell the GC what registers contain pointers at any given point in a method. For others, the GC only runs at a "safe point" which implicitly invalidates the register contents. Also, GC implementations are inherently platform dependent at some level. – Stephen C Mar 06 '13 at 04:49
  • @StephenC Well, I don't think so general purpose algorithm like garbage collection requires to be so platform-dependent. Atomic operations and memory barriers - yes. But direct access to registers? No, I don't think so. It would be efficient, but I believe it is not absolutely required. I would like to know more about such platform-independent algorithms. – lorus Mar 06 '13 at 05:07
0

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.

Jan Hudec
  • 18,340
  • Yes. But situation a was talking about is not about a local variable. It is about a global one, which can be simultaneously accessed and modified by different threads. – lorus Mar 06 '13 at 08:27
  • if after thread1 has read V and A isn't in a local variable of thread1 then A won't be reachable after thread2 modified V, so it will be ready for collection anyway – ratchet freak Mar 06 '13 at 08:32
  • @lorus: If a thread loads something into register, the register is it's local variable. Whether it was mentioned in high-level source or added by the compiler does not matter. You just treat it as local variable. – Jan Hudec Mar 06 '13 at 08:44
  • @JanHudec Ok. Now I get it. So, the calling the collector in the (client) thread is actually some kind of a global lock? – lorus Mar 06 '13 at 08:53
  • @lorus: I believe that you have to scan the local variables during the brief stop-the-world-and-scan-the-modified-objects phase, but I am not completely sure. – Jan Hudec Mar 06 '13 at 13:54
  • @lorus: I don't think that a completely parallel garbage collector exists. The only parallel (parallel with mutators) algorithm I know of needs a brief phase with mutators stopped when it scans objects that were modified during the main scan. In this regard local variables are considered modified and thus scanned in this phase. – Jan Hudec Mar 06 '13 at 13:57
  • 1
    @JanHudec unless the threads work with the GC and can add objects to a to-mark queue, each time a thread reads a reference – ratchet freak Mar 06 '13 at 15:41
  • @ratchetfreak: That would likely be slow as molasses. And could easily starve the collector, because mutators are reading something all the time, so when the queue would be nearing empty, some mutator would push more stuff in. – Jan Hudec Mar 06 '13 at 19:32
  • unless you add a flag in the object which keep whether it's already added to the queue, (which you clear along with the mark) so the mutator knows whether to add it in or not (and sets the flag when the object is added) – ratchet freak Mar 06 '13 at 19:35
  • @ratchetfreak: No, such flag wouldn't help. I assumed it would exist when I wrote the comment. It's kind of obvious that it would have to. The problem is that the fewer objects are in the queue, the higher the chance that some thread will add a new one. So unless the mutators are stopped for at least a short while, the queue never drains completely. That is also assuming that threads actually execute in parallel rather than time-multiplexed, but even mobile phones already have multi-core CPUs, so the threads do actually execute in parallel in most cases. – Jan Hudec Mar 07 '13 at 06:46