lemongc

A conservative garbage-collected allocator for C23. It scans the stack, .data, and .bss segments for root pointers and manages heap memory automatically using segregated freelists backed by 64 KB arenas. Collection triggers automatically at a 2 MB threshold, or manually via gc_collect().

Algorithms

Two collection algorithms are available, selected at compile time:

Mark-and-sweep (default) — stop-the-world collection. Captures roots via setjmp, marks reachable objects with a DFS worklist, then sweeps unmarked objects.

Incremental tricolor (-DGC_INCREMENTAL_TRICOLOR) — runs the mark phase on a background thread using a white/gray/black coloring scheme. A write barrier (GC_STORE_PTR) notifies the collector of pointer stores made while marking is in progress, preventing premature collection of live objects. Reduces main-thread pause time compared to stop-the-world.

Dependencies (Fedora)

sudo dnf install gcc cmake make

pthread is included in glibc, which is installed by default.

Building

git clone <repo>
cd lemongc
cmake -B build && cmake --build build

To enable incremental tricolor:

cmake -B build -DCMAKE_C_FLAGS="-DGC_INCREMENTAL_TRICOLOR" && cmake --build build

Benchmarks are built automatically alongside the library.

Importing into your project

Add lemongc as a subdirectory in your CMakeLists.txt:

add_subdirectory(lemongc)
target_link_libraries(your_target PRIVATE lemongc)

Then include the header:

#include "gc.h"

Usage

#include "gc.h"

typedef struct Node {
    struct Node* next;
    int value;
} Node;

int main(void) {
    void* stack_anchor = NULL;
    gc_init(&stack_anchor);  // pass a local in main as the stack top anchor

    Node* a = (Node*)gc_malloc(sizeof(Node));
    Node* b = (Node*)gc_malloc(sizeof(Node));

    // Use GC_STORE_PTR for pointer assignments.
    // Required in incremental tricolor mode; a direct store in standard mode.
    GC_STORE_PTR(a, a->next, b);
    a->value = 1;
    b->value = 2;

    // Memory is collected automatically. Force a collection if needed:
    gc_collect();

    const gc_metrics* m = gc_get_metrics();
    // fields: num_collections, max_spike_time_ns, total_gc_time_ns, etc.

    return 0;
}

Benchmarks

bin_tree

Builds a full binary tree of depth 18 (~500K nodes, all kept live) then performs 10,000 temporary allocations to simulate application churn. Reports total runtime, collection count, GC pause times (min/max/avg), and memory overhead.

latency_sim

Pre-allocates a 200,000-node linked list to create sustained heap pressure, then runs 10,000 allocation ticks measuring each tick's latency individually. Reports max tick latency and deadline miss counts at 1 ms, 5 ms, and 10 ms thresholds. Designed to evaluate the incremental tricolor algorithm's suitability for soft real-time workloads.

Both benchmarks output a single CSV line. Run from the build directory:

./benchmarks/bin_tree/benchmark_bin_tree
./benchmarks/latency_sim/benchmark_latency_sim

Output columns are printed in this order:

bin_tree: total_ns, gc_pause_ns, worker_ns, collections, min_spike_ns, max_spike_ns, avg_spike_ns, client_bytes, os_bytes

latency_sim: total_ns, gc_pause_ns, worker_ns, collections, max_spike_ns, max_tick_ns, miss_1ms, miss_5ms, miss_10ms