Implement Write Barriers for GC

Topic Overview

Remembered Sets for Generational GC

Minor GC scans nursery but must also scan old objects pointing into nursery. Tracking every old object is expensive. Write barriers log stores of old->young pointers into a remembered set or card table. HotSpot and Go use variants.

Barrier on Store

After old.field = young, barrier marks card containing old as dirty or logs the slot. Minor GC roots include remembered set entries.

cCopy
Loading…

• Store barriers vs load barriers (concurrent GC)
• Card size trades precision vs scanning cost
• Floating garbage in remembered set is ok
• Barrier code is inlined at every reference store

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 write barriers for generational GC. This exercise asks you to instrument reference stores and maintain a remembered set so minor collections find all nursery pointers.

Your Task

Implement the two classic write barriers a generational GC uses to find old→young pointers without scanning the whole old generation, and compare their costs: card marking (cheap barrier, coarse scan) and a precise remembered set of slots (costlier barrier, exact scan).

Input

cCopy
Loading…

Only old objects receive stores in these scripts. A slot is identified by its address; storing to it again overwrites its value.

Barriers

• card: every store marks the card containing the slot dirty, card number = (slot address − old-generation start) / cardsize, regardless of the target. Barrier work: 1 per store.
• remset: a store checks its target; if it is young, the slot address is added to the remembered set (once). Barrier work: 1 per store for the check, +1 when a slot is inserted.

Minor collection

• card: scan every slot whose address lies on a dirty card (ascending address); each scanned slot is 1 unit of scan work. Every young target found is a root. Then every card is cleaned except cards that still contain a slot pointing to a young object: those old→young pointers must be found again next time (young objects are never promoted in this model).
• remset: scan each remembered slot (ascending address), 1 unit each; if it still holds a young pointer it is a root; slots that no longer point to young objects are dropped from the set, the others stay.

(Young objects are not moved or promoted in this model.)

Output

For card mode each store prints store 0xSLOT -> TARGET: card N dirty; for remset mode, store 0xSLOT -> TARGET: remembered or store 0xSLOT -> TARGET: ignored. Each minor prints:

cCopy
Loading…

(cards none if no dirty card; young roots: none if empty; roots listed in slot order, each name once.) Finally barrier work=B scan work=S total=T.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. A map from slot address to current target, and either a card table (array of dirty flags) or a sorted set of slot addresses.
2. Keep barrier and scan work counters exactly as defined.

Hidden tests compare both modes on the same stores, include overwritten slots and null stores, and run several minor collections.