How Does Maru's Garbage Collector Work? A Deep Dive into the Mark-and-Sweep Implementation

Maru implements a naïve, precise, mark-and-sweep garbage collector entirely within the language itself, using a singly-linked list of heap chunks with explicit header metadata to track object liveness and type information.

Maru is a self-hosting Lisp system where the garbage collector (GC) is not a black-box runtime component but rather a set of Lisp functions defined in source/evaluator/gc.l. Understanding how Maru's garbage collector works reveals a straightforward yet effective memory management strategy based on classical mark-and-sweep principles, optimized for a single-threaded interpreter with precise pointer identification.

Heap Structure and Memory Layout

Maru organizes the heap as a singly-linked list of chunks, where each allocation is preceded by a header record containing metadata about the object.

The Chunk Header (<header>)

Every heap object in Maru is prefixed with a <header> structure defined in source/evaluator/gc.l:

(define-record <header> ()
  (next size flags type (when-at-expand (feature object-canary) canary))
  raw-slot-access)

The header fields serve specific purposes in the garbage collection process:

• next – Pointer to the next chunk, forming the linked list traversal path
• size – Payload size in bytes (excluding the header itself)
• flags – Bit-mask tracking object state (used, opaque, mark)
• type – Runtime type identifier (0 indicates a free chunk)
• canary – Optional debug token (0xDEADBEE) when the object-canary feature is enabled

Flag Constants and State Tracking

Maru uses three flag bits defined as constants in gc.l to manage object lifecycle:

(define-constant <header>-flags/used   1)   ; Object is allocated
(define-constant <header>-flags/opaque 2)   ; Object contains non-pointer data
(define-constant <header>-flags/mark   4)   ; Object is reachable (marked)

The opaque flag is particularly important for GC efficiency—it tells the collector that the object's payload contains raw data (like strings or bytevectors) rather than pointers to other heap objects, allowing the mark phase to skip recursive scanning of that memory.

Allocation and Heap Growth

Maru handles memory allocation through two primary mechanisms: acquiring new blocks from the platform and linking them into the existing heap structure.

Acquiring New Heap Space

When the allocator needs fresh memory, it calls gc/acquire-new-heap-space, which requests raw memory from the platform and initializes a header:

(define-function gc/acquire-new-heap-space (size)
  (let ((ptr (platform/acquire-memory size)))
    (set (<header>-size  ptr) (- size size-of-<header>))
    (set (<header>-flags ptr) 0)
    (set (<header>-next  ptr) ptr)                ; Points to self initially
    ptr))

This function returns a pointer to the payload area (just past the header), with the header's next field temporarily pointing to itself.

Growing the Heap

The gc/grow-heap function integrates new blocks into the global heap list:

(define-function gc/grow-heap (size)
  (let ((new-block (gc/acquire-new-heap-space size)))
    (set (<header>-next new-block) (<header>-next gc/memory-last))
    (set (<header>-next gc/memory-last) new-block)
    new-block))

Here, gc/memory-last serves as the anchor point of the heap list. The new block is inserted after this anchor, extending the available memory for subsequent allocations.

Garbage Collection Phases

Maru's garbage collector operates in two distinct phases: marking reachable objects from roots, then sweeping away the unmarked debris.

Root Registration and Management

Before collection can begin, Maru must know which objects are globally reachable. The interpreter registers permanent roots at startup in source/evaluator/vm-late.l:

(gc/push-root (address-of *globals*))
(gc/push-root (address-of *symbols*))
(gc/push-root (address-of *maru*))

For temporary protection of intermediate values during complex operations, Maru provides the gc/let* macro. This automatically pushes local variables as roots for the duration of the lexical scope, ensuring they survive any collections triggered during their use.

The Mark Phase (gc/mark-and-trace)

The gc/mark-and-trace function implements the recursive traversal of the object graph. It is defined in source/evaluator/gc.l and performs the following steps:

(define-function gc/mark-and-trace (obj)
  (and (not (immediate? obj))
       (not (gc/read-only-object? obj))
       (let* ((header (gc/header-of obj))
              (flags  (<header>-flags header)))
         (unless (bitwise-and flags <header>-flags/mark)
           (set (<header>-flags header) (bitwise-or flags <header>-flags/mark))
           (unless (bitwise-and flags <header>-flags/opaque)
             (let ((index (bytes-to-words (<header>-size header))))
               (while index
                 (decr index)
                 (gc/mark-and-trace (oop-at obj index))))))))))

This function first validates that the object is a heap pointer (not an immediate value like a fixnum) and not in read-only memory. It then checks the mark bit to avoid cycles. If the object is unmarked, it sets the mark flag and—crucially—checks the opaque flag before recursing. Non-opaque objects are scanned word-by-word, treating each slot as a potential pointer to another heap object.

The Sweep Phase (gc/sweep)

After marking completes, gc/sweep traverses the entire heap list to reclaim unmarked memory:

(define-function gc/sweep ()
  (let ((ptr gc/memory-base) (nobjs 0) (nused 0) (nfree 0))
    (while ptr
      (let ((flags (<header>-flags ptr)))
        (if (bitwise-and flags <header>-flags/mark)
            (progn
              (set nused (+ nused (<header>-size ptr)))
              (set nobjs (+ nobjs 1))
              (set (<header>-flags ptr) (bitwise-xor flags <header>-flags/mark)))
          (progn
            (set nfree (+ nfree (<header>-size ptr)))
            (set (<header>-flags ptr) 0)
            (set (<header>-type ptr) 0))))
      (set ptr (if (= gc/memory-base (<header>-next ptr))
                  0
                  (<header>-next ptr))))
    (set gc/objects-live nobjs)
    (set gc/bytes-used nused)
    (set gc/bytes-free nfree)) )

During the sweep, marked objects have their mark bit cleared for the next collection cycle and are tallied as live. Unmarked chunks are reset to a free state (flags and type zeroed) and their memory is effectively returned to the allocator for reuse. The function updates global statistics tracking live object counts and memory usage.

Triggering Collection

Maru's garbage collector runs automatically when allocation pressure exceeds a threshold or manually via explicit invocation. The allocation counter gc/allocations-until-gc defaults to approximately 131,000 allocations; when exhausted, gc/collect is invoked:

(define-function gc/collect ()
  (set gc/collection-count (+ gc/collection-count 1))
  (gc/mark-roots)   ; walks the root list
  (gc/sweep) )

The gc/mark-roots helper iterates through the registered root list (populated via gc/push-root) and calls gc/mark-and-trace on each, ensuring the mark phase sees all globally reachable objects before the sweep begins.

Practical Example: Protecting Objects During Allocation

When writing Maru code, you must ensure temporary objects survive collection during complex operations. The gc/let* macro creates temporary roots automatically:

;; Allocate a new vector and keep a reference in a root
(gc/let* ((v (vector 1 2 3)))
  ;; Use the vector …
  (print v))

;; Force a collection (for testing)
(gc/collect)

In this example, v is registered as a root for the duration of the gc/let* block. If gc/collect triggers during the print operation, the vector remains marked as reachable. After the block exits, the root is popped; a subsequent collection will reclaim the vector if no other references exist.

Summary

Maru's garbage collector demonstrates that a fully functional memory management system can be implemented within a Lisp runtime itself. Key takeaways include:

• Mark-and-sweep algorithm: Uses a precise tracing collector with distinct mark and sweep phases implemented in source/evaluator/gc.l.
• Chunk-based heap: Memory is organized as a singly-linked list of headers (<header>) containing size, type, and flag metadata.
• Opaque objects: The opaque flag optimizes collection by skipping recursive scanning of raw data buffers.
• Explicit root management: Global roots are registered with gc/push-root, while temporary roots use the gc/let* macro.
• Automatic triggering: Collections occur after approximately 131,000 allocations or via manual gc/collect calls.

Frequently Asked Questions

What type of garbage collector does Maru use?

Maru implements a naïve, precise, mark-and-sweep collector written entirely in Lisp. It is "precise" because it knows exactly which values are pointers versus immediate values (like fixnums), and "naïve" because it uses a simple linked-list heap structure without generational or incremental collection strategies.

How does Maru track which objects are reachable during collection?

The collector maintains a root list populated via gc/push-root for global structures like *globals* and *symbols*, and temporarily via the gc/let* macro for local variables. During the mark phase, gc/mark-and-trace recursively traverses these roots, setting the <header>-flags/mark bit on every reachable object and descending into non-opaque objects to find nested references.

What is the purpose of the opaque flag in Maru's GC?

The opaque flag (<header>-flags/opaque, value 2) indicates that an object's payload contains raw binary data rather than pointers to other heap objects. When gc/mark-and-trace encounters an opaque chunk, it marks the object itself but skips the recursive word-by-word scan of its contents, significantly improving collection performance for strings, bytevectors, and similar data types.

How can I manually trigger garbage collection in Maru?

You can force an immediate collection by calling gc/collect, which increments the collection counter, marks all reachable objects from the current roots via gc/mark-roots, and then sweeps unmarked memory. For debugging or testing purposes, you can also check the allocation threshold counter gc/allocations-until-gc (default ~131,000) to see when the next automatic collection will occur.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}