Background

Recently, I’ve been working on an experimental project called Ccache(https://github.com/yfractal/ccache), which implements core functions in Rust and integrates with other languages such as Ruby and Golang. Rust is a systems programming language that doesn’t use garbage collection (GC) for memory management. However, Ruby and Golang do use GC. This raises an interesting question: how can Rust interact safely and effectively with languages that use GC? To answer this question, I spent some time understanding how Ruby's GC works.

Introduction

In this article, I will describe how RGenGC (Restricted Generational GC), introduced in Ruby 2.2, works. To make things easier, I will first explain how garbage collection works in general, and then describe the unique problems that RGenGC solves, along with its mechanisms and source code.

Garbage Collection 101

Programs allocate virtual memory from the operating system, which maps the virtual memory to physical memory (or other resources such as files). Due to the limitations of physical memory and performance requirements, programs need to return the memory back once they are done using it.

Programs use two kinds of memory: stack and heap. Rust primarily uses stack memory, which requires knowing the size of variables before allocating memory. For dynamically sized structures, such as vectors, Rust allocates memory on the heap. To manage memory safely and efficiently, Rust doesn’t allow shared mutable and cyclic references. These restrictions allow Rust to use reference counting for managing heap memory but make it challenging to implement certain structures, like doubly linked lists[1].

C requires programmers to allocate and free heap memory manually, which is extremely difficult to manage correctly. Rust uses lifetimes and ownership to make memory management explicit and safe, minimizing performance costs as a system language.

Languages like Ruby and Go use GC—programmers do not need to consider when memory is freed, as it’s handled by the GC. Simply put, GC needs to return unused memory back to the system efficiently.

Mark and Sweep

Mark-and-sweep is a garbage collection algorithm that detects and frees inactive memory.

To find unused memory, the mark-and-sweep algorithm traverses all reachable objects through references. Unvisited objects are deemed inactive and can be freed. The mark phase identifies all reachable objects and marks them as such. In the sweep phase, these marked objects are retained while the others are freed.

To traverse all reachable objects, it uses the breadth-first search (BFS) algorithm. It recursively finds all direct references to each item. To avoid infinite loops, once all direct references of an item are identified, the item is marked as visited, ensuring it won't be revisited.

The algorithm maintains a queue to hold currently known reachable items. It dequeues an item, enqueues all its references, and marks it as visited. If a reference has already been visited, it isn’t added to the queue. This process continues until the queue is empty, indicating all reachable items have been visited.

Here's the pseudocode:

queue = init_queue()

for object in global_objects:
  object.visted = true
  queue.enqueue(object)


while queue.is_empty() == true:
  object = queue.dequeue
  for reference in object.references:
    if reference.visited == false
       reference.visited = true
       queue.enqueue(reference)

Now that all reachable objects are known, the sweep phase involves looping through all objects. If an object’s visited field is false, it means the object is unreachable and can be freed.

To summary, the process is:

Mark stage: Breadth-first search marked all of the live objects. Sweep stage: Scan over memory to free unmarked objects.

Mark and Compact

While mark-and-sweep can free unreachable objects, it doesn’t deal with fragmentation, which creates holes in memory.

!

As the freed objects are discontinuous, memory cannot be allocated for large structures even if there is enough total memory available.

Mark and Compact solves this issue by not only freeing unused memory but also rearranging live objects to make free memory contiguous.

The idea is to divide memory into two halves, FROM space and TO space. When FROM space is "full," the mark phase starts. During the mark phase, objects are moved from FROM space to TO space. Since other objects may refer to the moved object, a forward reference is recorded in the object’s old memory. The object’s references are also moved to TO space, and their pointers are updated to the new address. After the marking phase, all reachable references have been moved to TO space, and the old space can be freed.

You can also consider TO space as the queue in the mark-and-sweep algorithm, with two pointers representing the start and end of the queue.

Generational Garbage Collection

To release TO space, the mark-and-compact algorithm has to scan through all objects, which is time-consuming. Generational garbage collection improves this by scanning only new objects most of the time.

Generational garbage collection is based on a simple observation: if an object lives for a long time, it tends to live even longer[3]. This means we only need to check new objects most of the time. For example, when a request comes in, Rails creates a controller instance, which should be reclaimed after the request finishes. However, DB connection instances can live for a while and should not be reclaimed.

To simplify, objects are divided into two categories: new generation and old generation. New-generation objects have been created recently, while old-generation objects have been around for a while. The goal is to free memory related to new-generation objects after scanning them.

For an object to be marked as dead, there must be no references to it. During the marking phase, we scan all new-generation objects. If an old object references a new object, we need to record it and scan it during the marking phase.

When we create a reference to an object, we need to look at the objects that reference it. If the referencing objects are in the same generation or the new generation, they can be considered in our marking phase. For objects that are older than the referenced object, they are recorded separately and also considered in our marking phase. By considering all these objects, we can safely mark an object as dead during the marking phase.

Ruby RGenGC

The Write Barrier

During generational garbage collection, we scan young generation objects most of the time to reduce GC cost. To do this safely, we need to record when an old object references a young object. This record is called a Write Barrier.

The Unique Problem Ruby Faces

Before Ruby 2.2, Ruby only had a non-generational mark-and-sweep GC[4]. To support generational GC, we need a write barrier to record when an old object references a new object. However, this is challenging because Ruby has a large code base and many third-party C extensions.

To solve this compatibility issue, the Ruby team created the concept of Write-Barrier-Unprotected Objects.

Write-Barrier-Unprotected Objects

Since we can't let all Ruby objects use a Write Barrier when an old object references a new object, we don't know if these objects reference new objects or not. During minor GC, we must scan these objects.

Ruby RGenGC Marking Steps without WB-unprotected objects[4]:

1. Put the root-set objects and objects referenced from the remembered set objects into the work queue.
2. Repeat the following until the work queue is empty:
a. Dequeue an object p from the work queue.
b. For each object c referenced from p do:
    i. If p is an old object:
       • If c is already marked, makes c an old object and add c to the remembered set.
       • If c is not marked and not an old object, makes c’s age two (becomes an old object at the next step).
   ii. Increment the age of c by one, mark c, and then put c to work queue if c was not marked and is not an old object. Note that, in our implementation, if the age of an object becomes 3, the object becomes an old object.

To make Write-Barrier-Unprotected Objects safe, Ruby detects these objects and puts them in a set for scanning during minor GC.

Based on the above steps, Ruby ensures the safety of Write-Barrier-Unprotected Objects by detecting and recording them in a set.

Here is the relevant Ruby 2.2 code (simplified by removing unrelated code)[6]:

static void
gc_mark_ptr(rb_objspace_t *objspace, VALUE obj)
{
    rgengc_check_relation(objspace, obj);

    if (!gc_mark_set(objspace, obj)) return; /* already marked */
    gc_aging(objspace, obj);
    gc_grey(objspace, obj);
}

static void
rgengc_check_relation(rb_objspace_t *objspace, VALUE obj)
{
    const VALUE old_parent = objspace->rgengc.parent_object;

    if (old_parent) { /* parent object is old */
        if (RVALUE_WB_UNPROTECTED(obj)) {
            gc_remember_unprotected(objspace, obj)
        } else {
            if (!RVALUE_OLD_P(obj)) {
                if (RVALUE_MARKED(obj)) {
                    /* An object pointed from an OLD object should be OLD. */
                    RVALUE_AGE_SET_OLD(objspace, obj);
                    if (is_incremental_marking(objspace)) {
                        if (!RVALUE_MARKING(obj)) {
                            gc_grey(objspace, obj);
                        }
                    } else {
                        rgengc_remember(objspace, obj);
                    }
                } else {
                    RVALUE_AGE_SET_CANDIDATE(objspace, obj);
                }
            }
        }
    }
}

Summary

This article introduced several basic GC algorithms to help understand Ruby's RGenGC more easily. It doesn’t cover many interesting topics such as the Parallel Garbage Collector[8] because the focus is on the basics and those related to Ruby. Some details are intentionally omitted, such as the flip in Mark and Compact, as they are obvious and easy to understand. For more details, you can refer to these links: [2][3][4][5][7][8].

References

1. GhostCell: Separating Permissions from Data in Rust
2. https://ruby-china.org/topics/32226
3. A Real-Time Garbage Collector Based on the Lifetimes of Objects
4. Gradual Write-Barrier Insertion into a Ruby Interpreter
5. https://blog.peterzhu.ca/notes-on-ruby-gc/
6. https://github.com/ruby/ruby/releases/tag/v2_2_1
7. https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/resources/lecture-11-storage-allocation/
8. https://inside.java/2022/08/01/sip062/