What Actually Happens During Garbage Collection: Tri-Color Marking, Write Barriers, and Why RSS Stays High

If you ask most developers how garbage collection works, you usually get one of two answers:

1. "It uses reference counting and deletes objects when their count hits zero." (Almost no high-performance production runtime uses this for general heap management.)
2. "It pauses the application, scans everything in memory, deletes unused objects, and hands the RAM back to the operating system." (Which fails to explain concurrent collectors, sub-millisecond pauses, or why your server's RSS memory stays stubbornly high after a major GC.)

Garbage collection in modern runtimes like V8 (Node.js/Chrome), the Go runtime, and modern JVMs (ZGC, Shenandoah, G1) is an intricate piece of systems engineering. It balances CPU cache efficiency, hardware page tables, assembly-level write barriers, and memory allocators.

Here is what actually happens when an object is allocated, tracked, and collected under the hood.

---

1. Why Modern Runtimes Abandoned Naive Reference Counting

CPython and PHP use reference counting alongside a fallback cycle detector, but runtimes designed for high-concurrency and raw throughput (Go, V8, Java, .NET) rely almost entirely on tracing garbage collection.

There are two major reasons reference counting collapses in production systems:

1. Circular References: If object A points to object B, and object B points to object A, their reference counts will never drop to zero, even if your application loses all pointers to both. You need an expensive secondary cycle-detecting graph traversal anyway.
2. Atomic Overhead on Multi-Core CPUs: Every time a pointer is copied or passed to a function across threads, the CPU must perform an atomic increment (LOCK XADD on x86-64). This invalidates cache lines across CPU cores (cache bouncing) and creates massive memory bus contention.

Instead, tracing collectors do not care how many times an object is referenced. They care about one question: Is this object reachable from a Root?

What is a GC Root?

Tracing begins at the roots of your application:

• CPU Registers: Active memory addresses currently held in registers like RAX, RBX, or RSP.
• Active Stack Frames: Local variables and function parameters living on execution stacks for every running thread or goroutine.
• Global / Static Variables: Module-level state and global singletons that exist for the lifetime of the process.
• Runtime Handles: Persistent handles registered by C++ native addons, JNI, or runtime internals.

Any heap object that cannot be reached by following pointer chains from these roots is considered unreachable and eligible for reclamation.

---

2. The Tri-Color Marking Abstraction

To mark objects without freezing the entire process for several seconds, modern garbage collectors use Dijkstra's Tri-Color Marking algorithm.

During a collection cycle, every object on the heap exists in one of three conceptual colors:

[ WHITE ] ------------> [ GREY ] ------------> [ BLACK ]
Unvisited               Visited,               Visited,
Candidate for GC        Pointers Pending       Retained & Alive

• White (Unvisited): At the start of a GC cycle, every object on the heap is White. If an object is still White when marking finishes, it is garbage.
• Grey (Discovered / Pending): The GC has reached this object, but has not yet inspected the pointers inside it. Grey objects form the GC's worklist.
• Black (Scanned / Alive): The GC has inspected this object and pushed all of its child pointers into the Grey worklist. Black objects are guaranteed alive and will survive the cycle.

The Marking Flow:

1. Root Scanning: The runtime stops threads briefly (or scans stacks cooperatively) to find all GC Roots and mark them Grey.
2. Worklist Drain: Worker threads pop a Grey object from the worklist, scan all memory fields inside it, mark any White child objects as Grey, and then promote the parent object to Black.
3. Completion: The loop repeats until the Grey worklist is empty. At this point, the heap contains only Black (live objects) and White (dead objects).

---

3. The Concurrency Nightmare and Write Barriers

If your application threads (known in GC terminology as mutators) are completely paused during marking (Stop-the-World), Tri-Color marking is trivial.

However, modern runtimes run marking concurrently while your web server continues handling HTTP requests. This creates a critical race condition.

The Lost Object Problem

Imagine this scenario during concurrent marking:

1. The GC worker scans object A (Black) and is currently inspecting object B (Grey).
2. Object B holds a pointer to object C (White).
3. Concurrently, your application thread executes two lines of code:

   A.next = C;  // Black object now points directly to White object C
   B.next = null; // Grey object drops its pointer to White object C

1. The GC worker finishes scanning B. Because B.next is now null, the worker never visits C.
2. Object A is already Black, so the GC worker will never scan A again during this cycle.
3. C remains White at the end of marking, even though A is actively pointing to it.

When the sweep phase runs, the runtime frees C. Object A now holds a dangling pointer. The next write to A.next corrupts arbitrary memory or triggers a segmentation fault.

       [ Black A ] ------------ (mutator assigns C) ------------> [ White C ]
            |                                                           ^
            v                                                           |
       [ Grey B ] --- (mutator deletes link) ---------------------------+

The Solution: Write Barriers

To prevent this disaster, the runtime enforces the Tri-Color Invariant:

A Black object must never point directly to a White object without the collector noticing.

Whenever compiled code writes a pointer to heap memory (obj.field = target), the compiler injects a tiny snippet of assembly called a Write Barrier.

Different runtimes handle this with different strategies:

• Dijkstra's Insertion Barrier: If you write a pointer to any object, the write barrier checks if the target is White. If so, it immediately shades the target Grey and adds it to the worklist.
• Yuasa's Deletion Barrier (Snapshot-at-the-Beginning): If you overwrite or delete a pointer, the write barrier shades the old target Grey before overwriting it. This guarantees that anything reachable when GC began is preserved.
• Go's Hybrid Write Barrier: Introduced in Go 1.8, this combines aspects of both. Any new object allocated during marking is immediately shaded Black, and any pointer overwritten on the heap is shaded Grey. This eliminated the need to stop the world for stack rescans, dropping Go's GC pause times from tens of milliseconds to under 500 microseconds.

Here is a simplified conceptual view of what a write barrier looks like in JIT/compiled output:

void write_barrier_assign(HeapObject* parent, HeapObject** slot, HeapObject* new_val) {
    if (GC_Phase == GC_MARKING) {
        // If an existing reference is being overwritten, ensure it isn't lost
        HeapObject* old_val = *slot;
        if (old_val != NULL && old_val->color == WHITE) {
            shade_grey_and_enqueue(old_val);
        }
    }
    // Perform the actual pointer write
    *slot = new_val;
}

Because write barriers execute on every single pointer mutation while GC is active, runtimes disable them when marking finishes to eliminate CPU overhead during normal execution.

---

4. The Generational Hypothesis and Card Tables

Not all memory needs the same treatment. In the 1980s, garbage collection researchers discovered the Weak Generational Hypothesis:

Most objects die shortly after creation (usually within milliseconds), while objects that survive multiple GC cycles tend to live for a very long time.

Consider an Express.js or FastAPI server: request/response bodies, temporary strings, and promise allocations are created and discarded in under 10ms. On the other hand, database connection pools, routing tables, and configuration singletons stay alive for days.

Runtimes like V8 and the JVM take advantage of this by splitting the heap into Generations:

+------------------------------------+--------------------------------+
|       Young Generation (Nursery)   |    Old Generation (Tenured)    |
|  [ Eden ] -> [ From ] -> [ To ]    |   [ Mark-Sweep-Compact Heap ]  |
+------------------------------------+--------------------------------+

Minor GC (Scavenging in V8)

In V8, the Young Generation is divided into two semi-spaces: From-space and To-space (using Cheney's copying algorithm):

1. New allocations happen rapidly in contiguous nursery memory.
2. When the nursery fills up, a Minor GC (Scavenger) runs.
3. Instead of sweeping dead objects in place, the collector traces live objects and copies them sequentially into To-space.
4. Copying automatically compacts live objects, eliminating fragmentation.
5. Objects that survive multiple young-gen cycles are "promoted" (tenured) to the Old Generation.
6. The roles of From-space and To-space are swapped.

Because 95% of young objects are dead, copying only the surviving 5% takes less than 1 to 2 milliseconds.

The Cross-Generation Pointer Trap

What happens if an old object in the Old Generation is mutated to point to a new object in the Young Generation?

If a Minor GC only scans the Young Generation, it will miss the fact that the young object is reachable from the old object, and accidentally reclaim it.

Scanning the entire 4GB Old Generation on every 1ms Minor GC would destroy throughput.

The solution is a Card Table:

• The Old Generation memory is divided into virtual 512-byte blocks called Cards.
• The runtime maintains a compact byte array where each byte represents one 512-byte card.
• When an application thread writes a pointer into an old object, the write barrier marks the corresponding byte in the card table as dirty (0x01).
• During a Minor GC, the collector only scans the dirty 512-byte cards instead of the entire old heap.

Old Gen Heap (4 GB): [ 512B ][ 512B ][ 512B ][ 512B ] ...
                        |       |       |       |
Card Table Array:    [ 0x00 ][ 0x01 ][ 0x00 ][ 0x00 ] ... (dirty card scanned)

---

5. Why RSS Memory Stays High After a Major GC

A common frustration when profiling production services:

"Node.js reported heapUsed dropped from 1.8 GB to 250 MB after a GC run, but top and Kubernetes metrics show the container still consumes 2.1 GB of RSS (Resident Set Size). Why isn't memory being released?"

To understand this, you have to separate Heap Memory, Allocator Free Lists, and OS Physical Pages.

[ Application Code ] ---> [ Runtime Allocator (jemalloc/mheap) ] ---> [ OS Virtual Memory Subsystem ]
     heapUsed                       heapAlloc / Free Lists                       RSS (Page Tables)

1. The 4 KB Page Fragmentation Problem

The Linux kernel does not allocate memory in 16-byte object chunks. It allocates memory in 4 KB Physical Pages (or 2 MB huge pages).

Suppose a single 4 KB memory page contains 64 objects of 64 bytes each. Your application drops references to 63 of those objects. The GC marks 63 objects as dead and frees their space.

However, one single object on that page is still referenced.

Because that single object is alive, the CPU page table must retain the mapping to that physical RAM frame. The OS cannot reclaim that 4 KB page. Even if 98% of your objects are collected, page fragmentation can keep almost all physical pages resident in RAM.

2. Allocator Free-Lists

When the garbage collector reclaims an object, it does not issue a munmap() syscall to return the virtual address space to the Linux kernel. Syscalls are expensive, and acquiring new memory from the OS later triggers page faults and zero-fill overhead.

Instead, the runtime allocator (such as Go's mheap/mcentral, glibc's ptmalloc, or V8's page allocator) returns the reclaimed memory to internal Free Lists.

When your code calls new or make() five milliseconds later, the allocator immediately serves the memory from its internal cache without asking the OS.

3. madvise: MADV_DONTNEED vs MADV_FREE

To compromise between hoarding RAM and avoiding syscall churn, runtimes periodically inform the Linux kernel about unused address ranges using the madvise() system call:

// Inform the kernel that physical pages backing this range can be dropped
madvise(addr, length, MADV_DONTNEED);

• MADV_DONTNEED: The kernel immediately unmaps the physical page frames. RSS drops immediately. If the process touches that memory again, the CPU triggers a minor page fault and allocates a zeroed page.
• MADV_FREE (used by Go in certain versions): The kernel marks the pages as reclaimable. The pages remain in RSS until the operating system experiences actual memory pressure from other processes.

If your host has plenty of free RAM, the Linux kernel has no reason to reclaim MADV_FREE pages, so your process RSS will remain high even though the runtime has surrendered the pages.

---

6. Practical Takeaways for High-Throughput Systems

Understanding how the collector works under the hood changes how you write high-performance services:

1. Beware of Pointer-Dense Heaps: Tri-Color marking overhead scales with the number of pointers, not the size of raw byte buffers. A 100 MB buffer of raw bytes has zero pointers to trace. A 100 MB array of 1,000,000 small objects requires the GC worklist to trace 1,000,000 pointers on every cycle.
2. Reuse Allocations in Hot Loops: Object pooling (like sync.Pool in Go) keeps memory in the Old Generation and prevents the nursery/young generation from thrashing and triggering frequent Scavenger cycles.
3. Struct Layout and Value Types: Languages like Go and Rust (or C# structs) allow contiguous value layouts in memory, reducing pointer dereferencing and card table write barrier overhead.
4. Don't Panic Over RSS: High RSS after a traffic spike is normal allocator behavior. Verify heapUsed inside your runtime metrics before diagnosing a memory leak.

Automatic memory management is not magic. It is an active collaboration between compiled machine instructions, write barrier hooks, pointer worklists, and OS virtual page management. Knowing the mechanics helps you design code that works with the garbage collector instead of fighting it.