Sound Garbage Collection for C using Pointer Provenance
summary
Presents a sound garbage collector for C that tracks pointer provenance at runtime rather than guessing pointers by value, using Dynamic Pointer Provenance Tracking and an Optimistic Hybrid Analysis of profiling plus static analysis to elide most tracking. Implements provenance metadata with shadow memory and splay trees and modifies the Boehm‑Demers‑Weiser GC into Prov-GC. Reports about 16% tracking overhead on standard‑compliant C, single-collection time ~13% faster than BDW‑GC, and about 4% more memory reclaimed.
AI-written summary · about
chapters (14)
- 0:00Memory safety in C
- 1:50Prior GC limitations
- 3:43XOR linked lists problem
- 4:49Pointer Provenance Tracking
- 6:14Naive tracking inefficiency
- 7:02Static analysis optimization
- 8:11Safe pointers without Points-To
- 9:43C standard for pointer safety
- 10:26Control-flow tracking in GC
- 11:34Hybrid analysis optimization
- 13:05Prov-GC integration
- 14:10Provenance GC overhead
- 14:55Collection time and reclamation
- 15:41Sound GC with PPT
related talks
50mAn insight into Go Garbage Collection
21mGarbage Collection for Higher Inductive Types
28mA Mechanically Verified Garbage Collector for OCaml
54mGarbage Collection, State of the Art
57mWriting a custom, real-world .NET GC
14mPathological Cases for a Class of Reachability-Based Garbage Collectors
31mBlame-Preserving Secure Compilation
24mCross-Component Garbage Collection