3

I have read through A tour of V8: Garbage Collection and am stuck on this part:

Distinguishing pointers and data on the heap is the first problem any garbage collector needs to solve. The GC needs to follow pointers in order to discover live objects.

I understand the rest of the document for the most part, talking about how to actually perform the garbage collection once you have the live objects. But I don't understand how you identify the live objects.

After that quote they go on to describe 3 ways of distinguishing pointers from data, but the second one is glossed over a bit:

As long as we can identify what class an object comes from, we can find all of its pointers.

That sounds nice, I would like to know how to do that. I assume they mean when you construct a new class like new Foo(), under the hood it associates the instance of the class with a pointer to the actual class. But I don't see how the garbage collector then uses this information to determine which objects are live or not.

Likewise, this resource is a bit vague on the same detail:

The garbage collector works in two phases: the mark phase, and the sweep phase. In the mark phase, the garbage collector starts walks object references in order to find objects that are still reachable. The garbage collector starts at a few basic places where the object references are stored and given names (the stack, and global storage, and static storage), and then traverses references in the objects.

This is a bit more helpful, but still pretty vague:

Tracing garbage collection traverses the object graph forward, starting with the roots, to find the live data. Reference counting traverses the object graph forward, starting with the anti-roots (the set of objects whose reference counts were decremented to 0), to find dead data.

Intuitively, one can think of tracing as operating on “matter” and reference counting as operating on “anti-matter”.

I don't see how you can traverse objects, and know that it is ready to be garbage collected or not. Any tips on understanding that part would be of help. Thank you!

  • Objects hold references to other objects. Start at known objects (stack, global, static storage) and go to things the reference (that you haven’t visited). Repeat. I’m not sure what part you’re unclear on, so it’s hard to help. – Telastyn Aug 20 '18 at 23:51
  • If you are interested in detailed Java GC process see this link by kdgregory – Abhishek Bhatia Aug 25 '18 at 9:53
7

I'm sure Erik's answer has lots of great info but I think you are stuck on the fundamentals. I'm more familiar with Java GC but the basic principles are pretty universal.

I understand the rest of the document for the most part, talking about how to actually perform the garbage collection once you have the live objects. But I don't understand how you identify the live objects.

The thing I think you are missing is that there is necessarily a set of root references. In Java that's your stack, and static values etc. In JS, I'd guess it's things like the window object. I think a picture helps here:

Objects in memory

The circles represent objects and the arrows are references to other objects. On the left I've labelled three objects as being part of the root references. What that is exactly isn't terribly important but what you need to know is that these are basically implicit/hardcoded. They are fundamental to the runtime environment i.e. there's no need to find them. We know what and where they are inherently.

I think the easiest algorithm to understand is the mark-sweep and it's guaranteed to find all the garbage unlike other approaches such as reference counting. The first step is to mark.

enter image description here

I've added a green checkmark to each object that is referenced from the roots. You should be able to verify whether I've gotten it right (please do!) Just start with each root and follow it's references. Then follow the references from those until there are no more paths to follow. This is the 'live set' of objects.

Now comes the sweep:

enter image description here

Everything that wasn't identified as live is considered part of the 'dead set'. These are what can be removed. Notice the cycle of references in the lower-right corner. These are all in the dead set even though there are reference to them. This is because there is no path from the roots to any of those objects.

5

Distinguishing pointers and data on the heap is the first problem any garbage collector needs to solve. The GC needs to follow pointers in order to discover live objects.

Broadly speaking, there are two approaches to identifying references vs. non-references:

  1. Metadata that tells you whether a variable is a reference variable or otherwise.  This metadata will also tell you where the variable is, whether in a register for some duration, or in a memory location.  Such metadata is generated during code generation.  Generally speaking, the code generated will be done conscious of the need for this metadata, and this can have some minor affects on the register and memory location choices so that the metadata is not overly complex.  Still, all the info that the identifier of the object roots needs is to know whether each memory location is a pointer or not, wherever a method is suspended (e.g. at call sites, suspend on the stack).

  2. Guessing, which is accomplished by looking at the values to see if they might be in the range of the garbage collected heap.  Such an approach, in order to be correct, must be conservative, so assuming certain values as being pointers even if they might not be.  Such an approach might be found in approaches to garbage collection for C/C++ (yes, they exist!) where the compiler isn't known to help, and we have to worry about integers that hold pointers.  This would probably not be used for other languages that are more designed to support the metadata approach.  (Also note that guessing precludes compaction as we cannot risk to modify integers that look like pointers.)

As long as we can identify what class an object comes from, we can find all of its pointers.

In garbage collected runtimes, we will often find that the object model prescribes that the first slot of the object is a vtable pointer or other class reference.  Such a reference is basically hidden from the user, though used to perform casts, virtual method calls, find interfaces, and locate references within the object.

The garbage collector works in two phases: the mark phase, and the sweep phase. In the mark phase, the garbage collector starts walks object references in order to find objects that are still reachable. The garbage collector starts at a few basic places where the object references are stored and given names (the stack, and global storage, and static storage), and then traverses references in the objects.

Certain references are seen as live roots, so anything these roots reach (or could reach) is live, and should be considered live and thus not be collected.  The roots constitute all threads (i.e. their stacks, aka activations, aka stack frames), and also all static/global variables.  The metadata we're taking about above describes stack frames, and static/global variables.

I don't see how you can traverse objects, and know that it is ready to be garbage collected or not. Any tips on understanding that part would be of help

We don't: any traversed objects are necessarily considered live.  The trick then is to identify the objects that are not traversed from the latest traversal that starts at these roots.  Thus, the objects are tagged as live, or unknown/dead.  (During traversal we have live vs. unvisited, and post traversal we have live vs. dead.)  Sometimes the bit for this tag is stolen from the vtable or class pointer in the first slot, since there are (generally broadly speaking) bits that should always be zero at the LSB of such pointers (the pointers then have to be used more carefully).  During the trace, objects that are known to be reachable are marked as such, while objects that are not remain unmodified.

You might think that all objects would need to be marked as unreachable first, in order to identify the ones that are not reached, and yet most GC algorithms don't call out this initialization, though this is because there is a trick that can be used which is to reverse the sense of this live/unknown bit on every GC collection traversal: thus the visited nodes are marked "1" on one GC collection (and the ones marked "0" are collected as garbage) while on the next collection, we use "0" to mark the reachable ones, and the unreachable ones still hold "1" from the prior collection.

You can see from this that it is necessary to be able to find the remaining untraversed objects, which can be done by traversing the heap in memory order, given that typically object models prescribe that each object has a vtable reference or class pointer in the first slot, so you can easily tell how large the object is and thus where the next object is located sequentially in the gc heap.


Even in the case where metadata identifies roots, used as the start of live objects (traversal), these roots may be conservative in the sense that some of the roots might not actually be used later on.  So, while in a metadata oriented approach we know for sure whether a variable is a reference or not, we don't really know if the variable will or will not be used later in the algorithm of the code (i.e. the threads).  In this sense there is some conservatism in this approach.  Some compiler/optimization approaches (e.g. incorporated into the metadata) can reduce the window of potential liveness, such that even though some variables may still hold a reference it is known not to be used, for example, after the last use of the variable even if its storage location still holds a reference.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.