In the first post in the Ruby Garbage Collection Deep Dive series, we went through a few definitions to give us a picture of how Ruby stores values in memory. If you haven’t read it yet, read it first! We’ll build on those definitions in this post. Particularly, we’ll talk more about the Ruby Heap, Pages, Slots and RVALUES.

Okay, now that we have those baseline definitions out of the way, this post is going to explain the algorithm Ruby’s garbage collector uses to determine which objects it can collect: the Tri-Color Mark and Sweep algorithm. There are two phases to this algorithm. You guessed it: marking and sweeping. In the marking phase, the garbage collector marks all slots which contain accessible RVALUES. In the sweeping phase, the garbage collector clears the RVALUES out of all slots which are not marked. Let’s dig in!

Tri-Color Mark and Sweep

Marking

We’ll start off by discussing the marking phase. This is most straightforward to understand if we imagine the Ruby ObjectSpace to be a directed graph with root nodes. All of the nodes in the graphs are RVALUES. All of the edges in the graph are references from one RVALUE to another.

Ruby’s garbage collector starts at the root nodes and traces every edge it can access from these root nodes, marking every RVALUE it sees through this process. At the end, any RVALUE which was not traced, and therefore not accessible from a root RVALUE will be garbage collected.

Tri-Color

Okay, but the algorithm Ruby uses for garbage collection is called a Tri-Color Mark and Sweep algorithm, so what’s the Tri-Color part all about? The Tri-Color algorithm is a model we can use to understand what Ruby’s garbage collector is doing, and how tracks its progress. The three colors in the Tri-Color algorithm (three shades, really) are white, black and grey.

At the beginning of garbage collection, every slot in the Ruby Heap is white. Then, as part of the initial setup, all slots which contain root RVALUEs are marked as grey.

Root RVALUES are all of the RVALUES that a Ruby program knows it will need to run. Examples of these are RVALUES that exist on the stack of instructions that the program is following, or protected global variables.

With all root slots grey, and all other slots white, we then get to the crux of the algorithm:

while (!grey_slots.empty?)
  current_slot = grey_slots.pop
  grey_slots += current_slot.referenced_slots
  black_slots << current_slot
end

We iterate over all grey slots, coloring the slots that their RVALUES reference grey, and coloring themselves black. The algorithm continues until there are no grey slots left. At this point, any black slots contain RVALUES which were reachable by the RVALUEs in the root slots, and any white slots do not contain RVALUES which were reachable so can be swept away!

For the visual learners, here’s a gif of what the algorithm is doing:

mark-gif

References

There is one detail which needs further explanation here: how does an RVALUE know which other RVALUES it references?

It depends on the type of object. For Ruby builtins, tracing the references are just baked into the garbage collector code itself. For example, to find all references from an array RVALUE, the collector iterates each element in the array and finds its references. For a hash, it will do this for both the keys and the values. This all happens in the garbage collector’s mark_children method.

But, when objects are defined by C extensions, the C extensions must mark all child objects on their own. We’ll dive more into this in a future C extensions post (which I’ll backlink here).

Okay, so now that we understand how we find all accessbile objects, we need to learn how to dispose of all unaccessible objects.

Sweeping

At this point, we have two sets: black slots and white slots. Internally, these are represented as a marked bitmap. Every Page on the Ruby Heap has its own marked bitmap with one bit per slot. A 1 bit means the slot is accessible, or Black in our Tri-Color scheme. A 0 bit means that the slot is no longer accessible, or White in our Tri-Color scheme.

In addition to holding this marked bitmap, each page also has a freelist which represents slots on that page which do not have live objects. The garbage collector iterates over all pages, finding all slots which are not marked. Where applicable, the garbage collector then adds the unmarked slots to each page’s freelist. If the RVALUES which were occupying these slots are also taking up space in the operating system heap, it also frees this memory.

Once pages have been swept, there might be pages which are now completely unallocated; they have no slots which contain RVALUES. These pages are referred to as “Tomb Pages.” Tomb pages have their memory completely returned to the operating system’s heap. This is really helpful for memory management. It means that sweeping can result in freeing memory, or diminishing the overall size of the Ruby Heap.

Any pages with at least one occupied slot are called “Eden Pages”. The sweeping phase might reduce the number of occupied slots in an Eden Page. The garbage collector will use the freelists from Eden Pages for future object allocations. That is to say, if you instantiate an object, the garbage collector will look for one of these free slots in an Eden Page and place the RVALUE representing your object in there.

eden-and-tomb

There is one more nuance here. As of Ruby 3.0, if auto-compaction is enabled, compaction will actually happen as part of the sweeping phase. A more in depth explanation of how and why this happens will follow in a later post about compaction in this Garbage Collection Deep Dive Series.

TL;DR

The Tri-Color mark and sweep algorithm is what Ruby’s garbage collector uses to determine which slots hold objects which no longer have accessible references. It marks all of the slots it has references to by following the Tri-Color algorithm in which it follows all references from root RVALUES. Once the garbage collector knows which objects are accessible from the roots, it can begin the sweep phase, where it will add the unoccupied slots to each page’s freelist, and release any operating system memory those RVALUES held. This enables the slots to be reused for new object allocation.

Here are a few new definitions we learned:

  • Eden page: A page which contains slots with RVALUES, might also have empty slots
  • Tomb page: A page which contains only empty slots
  • Free list: A linked list per Heap Page of empty slots

And that’s it for this post! I’m going to continue writing blog posts in this series, and am also writing a book about managed garbage collection, with a focus on Ruby. If this interests you, join the newsletter below or follow me on twitter for updates!