Systems Engineering · week 9 · station III

Runtime Systems

Malloc, garbage collection. Liveness is undecidable, so collectors compute reachability instead.

Malloc

Selfie's malloc is a bump pointer. Freeing memory makes everything harder.

        // emit_malloc, in spirit
        uint64_t* malloc(uint64_t size) {
          uint64_t* block = _bump;     // read
          _bump = _bump + size;        // modify, write
          if (_bump > brk) brk(_bump); // ask the kernel
          return block;
        }
      

A global pointer that moves up. Allocation is constant time, memory is never reused, and the heap grows until the kernel refuses. Selfie's compiler never frees a byte.

Add free and you need a free list, a fit policy, coalescing, and metadata per block. Every design is a different notation for the same meaning, with a different cost profile.

And the read-modify-write of _bump is last week's race: two threads can receive the same block. That is the assignment.

The theorem

Will this block be used again? Undecidable. Can it be reached? Decidable.

live memory may be used again; dead memory will not be; unreachable memory cannot be

A block is live if the program will use it again, dead if not. That is a property of future behaviour: Rice, exactly. No collector decides liveness.

A block is reachable if a chain of pointers leads to it from a variable: a property of the current state, computed by a graph traversal. Unreachable implies dead; the converse fails.

So every collector computes the decidable over-approximation of the undecidable property. Safe, never precise: bound what you cannot decide.

Roots and tracing

Start from the variables. Follow every word that looks like a pointer.

roots in the data and stack segments; the heap reached from them

The roots are the globals in the data segment and the locals and parameters on every stack. Mark everything reachable from them; sweep the rest. Selfie's collector does this from the emulator, or as a library inside the program, or both.

Which words are pointers? C* does not say. A conservative collector treats every word that could be a heap address as one: still safe, still a bound.

Try -gc at two levels: a collector collecting a guest that runs its own collector.

Cost

Time, space, and the pause.

Stop-the-world

Mark-and-sweep stops the program for a time linear in the heap. Fine for a compiler; not for a game, a pacemaker, or a kernel. Every collector since is a way to spread that time out.

Generational, incremental, concurrent

Most objects die young: collect the young ones often. Do a little marking per allocation. Mark while the program runs, with a barrier that tells the collector what changed. Each is a bound traded for a cost.

Reference counting

Count pointers instead of tracing; free at zero. No pause, but cycles are never freed: an under-approximation of unreachability. Safe in the other direction: leaks, never dangling pointers.

Managed languages are languages whose runtime does this for you, and the price is paid on every allocation. The Cost chapter's trade, once more.

Assignment

threadsafe-malloc: add lr.d and sc.d, then use them.

Add lr.d and sc.d to RISC-U: encoding and decoding in selfie, a case each in mipster's execute, and the reservation, cleared by any store to the address, in the machine context. Make hypster honour it too.
Provide them to C* as procedures lr() and sc(), emitted like the other library procedures.
Rewrite emit_malloc so that the read-modify-write of _bump is a retry loop on lr and sc. Test with last week's threads: many threads, many allocations, no two blocks overlapping.
./grader/self.py threadsafe-malloc.

Next week

The last systems assignment, treiber-stack, builds a lock-free stack on the same two instructions. And rotor-bounds turns a model checker on your sequential systems code, because rotor does not yet model threads. Both are introduced in week 10.

After this week

Listen, then read.

Listen

Wagner · Götterdämmerung — Barenboim, Bayreuth 1988. The end of the Ring returns everything: Valhalla burns, the ring goes back to the Rhine, and every motif of four evenings is reclaimed in the last twenty minutes. Garbage collection at the end of the world, and nothing reachable is lost.

Read

The Garbage Collection Handbook — Jones, Hosking and Moss: every collector, mark-sweep to concurrent, with the trade-offs; the week’s taxonomy in full. And, more technical, Garbage Collection in an Uncooperative Environment — Boehm and Weiser, 1988: the conservative collector, value or pointer, that selfie’s collector is modelled on.

SE 10 · Verifying Systems Code →