Skip to content

GC worklist overflow for deeply nested object graphs #348

@aallan

Description

@aallan

The mark-sweep GC in vera/codegen/assembly.py uses a fixed-size worklist of 1024 entries (4096 bytes / 4 bytes per entry). If a deeply nested or wide object graph exceeds this capacity, reachable objects beyond the worklist limit will not be marked and will be incorrectly freed during the sweep phase.

Impact

Programs with deeply nested ADT structures (e.g., a large Json tree, deeply nested Option chains, or long linked lists) could trigger premature collection of reachable objects, causing use-after-free bugs.

Current mitigation

The 1024-entry limit is sufficient for typical programs. The risk increases with recursive ADT types like Json (JArray(Array<Json>) containing nested JObject(Map<String, Json>)).

Possible fix

  • Dynamic worklist growth (realloc when full)
  • Iterative deepening (re-scan from roots if worklist overflows)
  • Increase the fixed size (simple but doesn't eliminate the risk)

Affects: All heap-allocated types. Higher risk with recursive ADTs like Json.

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't workingcodegenCode generation backend

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions