blog.dopana

Back

In our previous deep dive, we explored the radical architectural premise of Goose: a modern systems programming language that completely eliminates general-purpose heap allocations, discards garbage collection, and automatically reclaims data on compiler-managed Data Stacks at lexical scope boundaries.

However, an experienced systems engineer encountering this model will immediately raise an essential architectural challenge:

“If all dynamic values are tied to lexical scopes on Data Stacks, how do we represent data structures with non-nested lifetimes? How do we build arbitrary N-ary directory trees where nodes are created and deleted out of order, cyclic graphs, game entity-component systems (ECS), or LRU caches?”

In C and C++, developers tackle this via malloc/free, paying the price in use-after-free vulnerabilities and heap fragmentation. In Rust, handling cyclic graphs is notoriously difficult, requiring heavy machinery like Rc<RefCell<T>>, Arc<Mutex<T>>, or external crates like SlotMap backed by generational integer indices.

Goose provides an elegant, safe, and cache-friendly alternative: Memory Pools (slot_pool<T> and slice_pool<T>).

1. The Core Dilemma: Non-Lexical Data Lifetimes#

Consider a standard filesystem directory tree:

/ (root)
├─bin/
│   ├─app
│   └─util
└─docs/
  └─readme.md
text

In real-world usage, files and directories are created, renamed, modified, and deleted in completely arbitrary order. Node lifecycles do not obey the strict Last-In-First-Out (LIFO) discipline of the call stack.

If an architecture only offered linear data stacks:

  • You could not delete an intermediate node in a growable array without shuffling all subsequent entries.
  • You could not reclaim individual allocations while neighboring elements remain active.

To bridge this gap without reintroducing a fragmented system heap, Goose provides two complementary standard abstractions: slot_pool<T> and slice_pool<T>.

2. Dual Pool Architecture: slot_pool and slice_pool#

slot_pool: Fixed-Size Node Allocationslice_pool: Dynamic Contiguous Slicesslice_pool: Dynamic Contiguous SlicesRelative Reference: Link u32 innodesItems Array (Node[>..] DataStack)Freelist (Recycled Slot Indices)alloc_ref: Reuse Freelist Slot orPushfree: Return Slot Index toFreelistContiguous Run Buffer(Link[>..])Span Freelist (AdjacentMerging)alloc_slice or realloc_slice

1. slot_pool<T>: Fixed-Size Node Management#

  • Combines a grow-only backing array (T[>..]) anchored to a Data Stack with a fast in-memory freelist.
  • alloc_ref(value): Checks the freelist for previously deleted slots. If one exists, it recycles that slot instantly. If the freelist is empty, it advances the stack bump pointer (push) to append a new element.
  • free(slot): Does not return memory to the OS kernel! It simply registers the slot’s index back onto the freelist for subsequent reuse.

2. slice_pool<T>: Contiguous Dynamic Run Management#

  • Designed for child lists and variable-length collections (e.g., directory children or adjacency lists).
  • Exposes primitive operations: alloc_slice(n), realloc_slice(s, n), and free_slice(s).
  • When a slice is released, slice_pool automatically merges adjacent free memory spans, preventing fragmentation without requiring OS heap defragmentation.

3. The Security Guarantee: Type-Safe Reuse#

What makes free() in C and C++ so perilous? Once memory is deallocated, the OS may reassign that physical address space to an entirely different subsystem or data structure. If a dangling pointer reads that location later, it triggers segmentation faults or catastrophic Remote Code Execution (RCE) exploits.

Goose neutralizes this threat through Type-Safe Reuse:

Goose slot_pool: Type-Safe ReuseC / C++: Dangling Pointer and CrashNode Allocated (malloc)Node Freed (free)OS Memory Returned / Reusedfor Other TypesStale Pointer Read: Segfault orSecurity ExploitSlot Allocated (alloc_ref)Slot Returned to Pool Freelist(free)Memory Remains Allocated inStackStale Reference Read: ValidNode of Type T (Safe)

[!TIP] The Goose Safety Invariant: Memory assigned to a pool’s backing array is never returned to the OS until the entire pool’s scope exits. If application logic accidentally dereferences a stale link to a freed slot, it simply reads whatever valid record of type T currently occupies that slot. It may be a logical bug, but it is physically incapable of causing memory corruption, wild pointer jumps, or arbitrary code execution!

4. Production Walkthrough: The N-ary File Tree (26_file_tree.goose)#

Let us examine how Goose coordinates pools in a real-world directory tree implementation from the official repository:

Architectural Highlights#

  1. Ultra-Narrow 4-Byte Links (Node&<u32 in nodes>?): Rather than consuming 8 bytes for a full virtual pointer, parent-child connections consume only 4 bytes (a 32-bit offset relative to the base of the nodes pool). A value of 0 cleanly represents null via ?.
  2. Cache-Friendly Contiguous Child Traversal: A directory’s children are represented as entries: Link[:]. Walking a directory’s contents streams through a linear, flat memory block with zero pointer-chasing overhead.
  3. In-Place Slice Expansion: realloc_slice grows child runs in-place if contiguous unallocated space remains immediately after the slice. If blocked by adjacent data, it relocates the run to the end of the pool and marks the prior span free.
  4. Zero System Heap Overhead: Millions of tree nodes reside exclusively across two pre-allocated Data Stacks. When the directory operation finishes and the enclosing scope terminates, the entire tree structure is reclaimed in two CPU store operations!

5. Seamless Cyclic Graphs#

In Rust, constructing cyclic graphs (Node A points to B, B points to C, and C points back to A) is notoriously complex, frequently running afoul of the borrow checker. In C++, circular references with std::shared_ptr inevitably cause memory leaks unless manually mitigated with std::weak_ptr.

In Goose, cyclic graphs require zero runtime reference counters and zero unsafe blocks:

Every vertex resides in vertices, and every edge resides in edges. Because cleanup happens in bulk when the pool scope terminates, cyclic cross-references never obstruct deallocation.

6. Technical Comparison: Graph Representations Across Languages#

AttributeC++ (std::shared_ptr)Rust (Rc<RefCell<T>>)Rust (SlotMap + Id)Goose (slot_pool + slice_pool)
Syntax OverheadHigh, prone to cyclic leaksHeavy boilerplate, runtime panicsRequires manual ID lookupsNatural, transparent .= syntax
Link Size16 bytes (ptr + control block)16 bytes (ptr + strong/weak counts)8 bytes (Index + Generation)4 bytes (Node&<u32>)
Allocation Cost1 heap allocation / node1 heap allocation / nodeAuxiliary array reallocationsPointer bump (O(1)O(1))
Deallocation CostCascading ref count decrementsCascading ref count decrementsArray dropSingle CPU store at scope exit
Cycle Leak Resistance❌ Leaks without weak_ptr❌ Leaks without Weak✅ Cleaned on map drop✅ Zero leaks guaranteed

7. Conclusion#

Goose’s Memory Pools demonstrate that systems software does not need to compromise between structural flexibility and rock-solid memory safety:

  1. You do not need a Garbage Collector to clean up complex graphs.
  2. You do not need a restrictive borrow checker to interlink cyclical nodes.
  3. You do not need an OS heap allocator with its fragmentation and synchronization lock contention.

By pairing compiler-managed Data Stacks, slot_pool abstractions, and compact 4-byte relative references, Goose provides an extraordinary blueprint for building fast, small, and completely safe systems software.

References#