Skip to main content

Memory Model

Mux uses reference counting for deterministic memory management. This document describes the memory model in detail.

Overview​

Mux provides automatic memory management through atomic reference counting (RC):

  • No manual free or delete
  • No garbage collector pauses
  • Deterministic cleanup when references go out of scope
  • Thread-safe reference count operations

Memory Layout​

Heap Allocation​

All non-primitive values are heap-allocated

Value Types​

TypeStorageMemory Management
int, float, bool, charInline (boxed in Value enum)Reference counted
stringHeap-allocated UTF-8Reference counted
list<T>Heap-allocated vectorReference counted
map<K,V>Heap-allocated BTreeMapReference counted
tuple<K,V>Heap-allocated objectReference counted
set<T>Heap-allocated BTreeSetReference counted
optional<T>, result<T,E>Boxed enumReference counted
Class instancesHeap-allocated objectReference counted
References (&T)PointerNot RC'd (borrowed)

Reference Counting Operations​

Increment (mux_rc_inc the reference count when)​

Increments creating a new reference:

snippet.mux
Loading...
Ctrl + Enter to run

When increment happens:

  • Variable assignment
  • Function argument passing
  • Adding to collection
  • Returning from function

Decrement (mux_rc_dec)​

Decrements the reference count when a reference goes out of scope:

snippet.mux
Loading...
Ctrl + Enter to run

When decrement happens:

  • Variable assignment (old value)
  • Function return (local variables)
  • Scope exit
  • Collection element removal

Cleanup​

When mux_rc_dec returns true, the refcount reached zero and memory is freed:

  1. For classes with destructors: call destructor
  2. Free the allocation

Scope-Based Tracking​

The compiler generates cleanup code using a scope stack:

  1. Enter scope -> push_rc_scope() (function entry, if-block, loop-body, match-arm)
  2. Track variable -> track_rc_variable(name, alloca) for each RC-allocated variable
  3. Exit scope -> generate_all_scopes_cleanup() iterates through all scopes in reverse order

Example: Scope Cleanup​

snippet.mux
Loading...
Ctrl + Enter to run

Early Returns​

snippet.mux
Loading...
Ctrl + Enter to run

Collections and Memory​

Collections contain RC-allocated values. When freed:

  1. Collection's refcount reaches zero
  2. Collection's container (Vec<Value>, etc.) is dropped
  3. Each contained Value has its refcount decremented
  4. Nested collections are freed recursively

Nested Collections​

snippet.mux
Loading...
Ctrl + Enter to run

Cleanup order:

  1. Outer list refcount -> 0
  2. Drop outer list
  3. Each map's refcount -> 0
  4. Drop each map
  5. Each inner list's refcount -> 0
  6. Drop inner lists
  7. All strings freed

Value Semantics​

Reference vs Value​

snippet.mux
Loading...
Ctrl + Enter to run

References (&T)​

References provide non-owning pointers to values:

snippet.mux
Loading...
Ctrl + Enter to run

Reference Rules​

  • References are non-nullable
  • No reference arithmetic
  • References do not affect reference counts
  • optional references: optional<&T>
snippet.mux
Loading...
Ctrl + Enter to run

Memory Safety​

No Use-After-Free​

Memory is only freed when all references are gone:

snippet.mux
Loading...
Ctrl + Enter to run

No Double-Free​

Reference counting prevents double-free:

snippet.mux
Loading...
Ctrl + Enter to run

Performance Characteristics​

OperationComplexity
AllocationO(1) amortized
Clone (increment)O(1) atomic
Drop (decrement)O(1) atomic
Clone collectionO(n) copy all elements
Clone map/setO(n log n) insert all elements

Thread Safety​

Reference count operations use atomic operations:

// mux_rc_inc
fn rc_inc(ptr: *mut Value) {
    let header = get_ref_header(ptr);
    header.ref_count.fetch_add(1, Ordering::AcqRel);
}

// mux_rc_dec
fn rc_dec(ptr: *mut Value) -> bool {
    let header = get_ref_header(ptr);
    if header.ref_count.fetch_sub(1, Ordering::AcqRel) == 1 {
        // Last reference - free memory
        free(ptr);
        true
    } else {
        false
    }
}

See Also​