The Software · Chapter 9.b
Where does new memory come from?

Watch the opener · 1:11

Transcript

Where does new memory come from? A program keeps asking for memory, in sizes it can't predict.

I figured you'd keep a marker and just slide it forward for each request. But blocks come back in any order, and they leave holes.

So an allocator keeps a list of free runs. Sixteen cells, all free. Ask for A, B and C: each takes four cells from the front. Free A: a hole opens at the start. Free B: now two holes touch. The first hole ends where the second starts, so they merge into one run of eight. Without that merge, a request for eight would fail, with the room right there. Free C, and the heap is one run again.

So new memory comes from holes, merged back together! No space lost and no gaps left behind: that's the allocator's whole job.

Carve blocks out below and free them in any order. Can you leave a hole that won't merge?

A program rarely knows in advance how much memory it will need. It asks for some, uses it, gives it back, and asks again, in sizes and at moments it cannot predict. These requests usually go first to an allocator inside the process, such as the library routines malloc and free. The allocator subdivides memory already obtained from the operating system. Kernel requests like those of Chapter 9.a acquire or release larger regions as needed; each small allocation or release need not make a system call.

The region managed this way is the heap, and the allocator is its bookkeeper. Kernels can use similar bookkeeping internally, but this chapter’s Heap is an independent model of one fixed region, with no kernel calls. It tracks address ranges rather than storing the bytes in them.

The whole problem is the unpredictable order. If memory were only ever taken and never returned, handing it out would be trivial: keep a mark and move it forward. But blocks come back in any order, leaving holes, and the allocator must reuse those holes or the heap fills with gaps and can satisfy nothing.

9.b.1 The free list

The allocator keeps a free list: the runs of memory not currently in use, each a start and a length. To satisfy a request it finds a run large enough and carves the request off the front, leaving the remainder free. Figure 9.b.2 follows a small heap through a few requests.

The interactive version needs the in-browser runtime.

Example 9.b-1. Handing out and reclaiming memory

class Heap:
    """A region of memory, tracked as a free list of (start, length) runs and a
    map of the live allocations."""

    def __init__(self, size: int) -> None:
        self.size = size
        self.free = [(0, size)]   # runs not in use, kept sorted by start
        self.live = {}            # start address -> length of a live block

    def malloc(self, amount: int) -> int:
        """Carve `amount` cells off the first free run large enough and return the
        start address. Raise if no run is big enough."""
        if amount <= 0:
            raise ValueError("allocation size must be positive")
        for index, (start, length) in enumerate(self.free):
            if length >= amount:1
                if length == amount:
                    del self.free[index]
                else:
                    self.free[index] = (start + amount, length - amount)
                self.live[start] = amount
                return start
        raise MemoryError(f"no free run of {amount} cells")

    def release(self, address: int) -> None:
        """Return a live block to the free list, then merge it with any adjacent
        free run so the freed space does not stay fragmented."""
        amount = self.live.pop(address)
        self.free.append((address, amount))2
        self.free.sort()
        self._coalesce()

    def _coalesce(self) -> None:
        """Merge free runs that touch into single runs."""
        merged = []
        for start, length in self.free:
            if merged and merged[-1][0] + merged[-1][1] == start:3
                end = merged[-1][0]
                merged[-1] = (end, merged[-1][1] + length)
            else:
                merged.append((start, length))
        self.free = merged

• to allocate, find the first free run at least as large as the request and carve the request off its front
• to free, return the block’s run to the list
• then coalesce, merging adjacent free runs into one; Section 9.b.2 takes this up

Taking the first run large enough is the placement policy called first fit. It is the simplest choice, not the only one; real allocators use others, such as best fit, buddy systems, and size classes, to trade speed against how much the heap fragments.

9.b.2 Coalescing

Coalescing is what keeps the heap healthy. Without it, freeing a block next to an existing hole would leave two small runs where there should be one large one, and a later request for the combined size would fail even though the room exists. Merging adjacent runs, shown in Figure 9.b.3, undoes the fragmentation that freeing creates.

9.b.3 The allocator, run

Running ftb.allocator allocates three blocks, frees them so that two freed runs sit next to each other, and shows the free list at each step.

a heap of 16 cells, all free: [(0, 16)]

malloc(4) three times: a at 0, b at 4, c at 8
  free list now: [(12, 4)]

free a: leaves a hole at 0
  free list now: [(0, 4), (12, 4)]
free b: its run touches the hole, so they coalesce
  free list now: [(0, 8), (12, 4)]

free c: everything is free again, one run: [(0, 16)]

The three allocations carve the heap from the front. Freeing a opens a hole at the start; freeing b adds a run that touches it, and the two coalesce into a run of eight. When the last block goes back, the heap is a single free run again, exactly as it started. That round trip, no space lost and no gaps left behind, is the allocator’s whole job.

The allocator decides which address ranges are free. The next chapter asks how a program’s addresses map to physical memory, and what keeps private regions apart.

Exercises

• Allocate three blocks, free the middle one, then free a neighbour and watch the two free runs merge.
• Ask for more memory than any single free run can hold, and see what the allocator does.