Implement Conservative Garbage Collection

Topic Overview

Scan Stacks Without Exact Maps

Conservative GC treats stack and register words as possible pointers. If a word points into the heap, keep the object. Boehm-Demers-Weiser GC powers some C/C++ runtimes where precise roots are unavailable.

Conservative Root Scan

Walk stack slots; if value looks like heap address and aligns to object boundary, treat as reference. No relocation possible because any word might be a disguised pointer.

cCopy
Loading…

• Cannot compact or move objects
• False retention causes memory leaks of a sort
• Works with uncooperative C code
• Used when precise stack maps are too costly

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will implement conservative garbage collection root scanning. This exercise requires walking stack words, testing heap likelihood, and marking objects without exact pointer maps.

Your Task

Implement a conservative collector in the style of the Boehm GC, used by C programs and language runtimes that can't tell pointers from integers: treat every word on the stack and in reachable objects as a potential pointer, keep alive any object it points into, and measure the cost: objects kept alive by integers that merely look like addresses.

Input

cCopy
Loading…

VALUE is hex (0x...) or decimal. The optional int tag says what the program meant: the value is really an integer. The collector cannot see this tag; it is only used for the report.

Collection

1. A value hits an object if it equals the object's start address, or, with interior yes: lies anywhere in [start, start + SIZE).
2. Scan the stack words in order; each hit marks its object.
3. Then scan the words of marked objects: repeatedly take the marked-but-unscanned object that was marked earliest, and scan its words in offset order, marking whatever they hit.
4. Free every unmarked object.

Output

For every stack or heap word that hits an object:

cCopy
Loading…

Then:

cCopy
Loading…

Values print in lower-case hex.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. An object table sorted or searchable by address range, a "hit" function honouring the interior setting, and a worklist of marked objects.
2. A second, precise marking pass (ignoring int-tagged words) for the false-retention report.

Hidden tests cover interior no, integers that land on object start addresses, pointers hidden inside heap objects, and values that point just past the end of an object.