# Exercise 02 — The cache we emptied and the memory we did not get back

**Failure mode:** heap fragmentation — free bytes that are not a free region
**Language:** C · **Runtime:** about 3 seconds · **Difficulty:** the one where nothing is leaking

---

## The prompt

> A map tile cache holds 20,000 decoded tiles of 32 KiB each. When the viewport moves, the
> tiles that left it are evicted. Eviction is interleaved — the evicted tiles are scattered
> through the allocation order, not grouped at the end of it.
>
> The field reports: "we evict half the cache and the process footprint does not move at
> all."
>
> There is no leak. Every byte is freed. Explain the measurement, fix it, and tell me what
> your fix gives up.

Answer before you run anything: **what, exactly, does `free()` promise?**

---

## What you are given

| Path | What it is |
| --- | --- |
| `broken/tilecache.c` | The starting point. 32 KiB tiles from `malloc`. |
| `fixed/tilecache.c` | One correct repair. |
| `solution.patch` | The diff between the two, applies with `patch -p1`. |
| `check.sh` | Asserts the recovered fraction in both builds. |

---

## Reproduce the measurement

```bash
cd exercises/02-heap-fragmentation
clang -O2 -g -Wall -Wextra broken/tilecache.c -o /tmp/tiles_broken
clang -O2 -g -Wall -Wextra fixed/tilecache.c  -o /tmp/tiles_fixed
/tmp/tiles_broken
/tmp/tiles_fixed
```

Observed on an Apple M4 Pro, macOS 26.3 (25D125), 16 KiB pages:

```
                              broken        fixed
phase=full                    628.9 MB      626.4 MB
phase=evicted-half            628.9 MB      313.9 MB     <- the whole exercise
phase=after-pressure-relief   628.9 MB      313.9 MB
phase=empty                   246.7 MB        1.1 MB
recoveredFractionAtHalf       0.000         0.500
```

**Reproduce these; do not quote them.**

---

## The evidence to collect

1. **`recoveredFractionAtHalf = 0.000`.** Ten thousand `free()` calls, 312 MB of bytes
   returned to the allocator, and the process footprint is unchanged to one decimal place.

2. **`malloc_zone_pressure_relief(NULL, 0)` returns 0 bytes** and changes nothing. This is
   worth running because it is the documented way to ask the allocator to release what it
   can, and its answer here is "nothing". That is the measurement that rules out "the
   allocator is just being lazy and will get round to it".

3. **`phase=empty` is 246.7 MB.** Even after *every* tile is freed the process is still
   holding a quarter of a gigabyte. The allocator keeps its arenas.

4. **The mechanism.** The allocator serves 32 KiB requests out of larger regions it obtained
   from the kernel. A region can only be returned when **every** allocation in it is free.
   Freeing every *other* tile leaves every region with live tenants, so not one region
   qualifies. The bytes are free; no *page* is.

   ```
   region  [ T0 | T1 | T2 | T3 | T4 | T5 | T6 | T7 ]   before eviction
   region  [ .. | T1 | .. | T3 | .. | T5 | .. | T7 ]   after evicting the evens
                 ^ 50% free, 0% returnable
   ```

5. **`vmmap` shows the same thing from outside**, if you want a second source:

   ```bash
   /tmp/tiles_broken & sleep 1; vmmap $! | grep -i malloc
   ```

   The `MALLOC_` regions stay mapped with a large `dirty` column.

---

## Success criteria

- [ ] The broken build still recovers nothing — you have not edited it.
- [ ] Your fixed build's `recoveredFractionAtHalf` is at least **0.40**.
- [ ] Your fixed build's `finalMB` is at most **10%** of its peak.
- [ ] Your fixed build's `checksum` equals the broken build's, exactly.
- [ ] You can state the size threshold above which your repair is worth applying, and what
      it costs below that threshold.

Run `./check.sh` to have all of that checked for you.

---

## Hints

<details>
<summary>Hint 1 — the allocator is not the virtual memory system</summary>

`malloc` and `free` manage *bytes inside regions*. `mmap` and `munmap` manage *regions*.
Only the second pair talks to the kernel about page residency. Ask which one you actually
need for an object whose lifetime is independent of its neighbours'.
</details>

<details>
<summary>Hint 2 — look at the size</summary>

`sysctl -n hw.pagesize` on Apple silicon is 16384. A tile is 32768 bytes: exactly two
pages, with nothing left over. An allocation that is a whole number of pages and lives and
dies on its own has no reason to share a region with anything.
</details>

<details>
<summary>Hint 3 — and know when NOT to do this</summary>

Whatever you are about to reach for, it has a per-call cost in the kernel and a minimum
granularity of one page. Applying it to 64-byte objects would be a catastrophe. Work out
roughly where the crossover is before you write the code, and say so in your answer.
</details>

---

## Solution

<details>
<summary>Reveal the solution</summary>

### The repair

```c
tiles[i] = mmap(NULL, TILE_BYTES, PROT_READ | PROT_WRITE,
                MAP_PRIVATE | MAP_ANON, -1, 0);
...
munmap(tiles[i], TILE_BYTES);
```

Each tile becomes its own anonymous mapping. `munmap` returns those pages to the kernel
immediately and unconditionally, because there are no neighbours to strand. Eviction order
stops mattering entirely.

### Why this works and `free()` cannot

`free()` is a promise about *reuse*, not about *residency*: it says the bytes may be handed
out again by this allocator. It deliberately does not promise to return anything to the OS,
because doing so on every free would mean a system call per free and a fresh page fault on
the next allocation. The allocator's whole value is amortising those away.

`munmap` is a promise about residency, and you pay for it in system calls.

### What it costs

- **One `mmap` and one `munmap` per tile**, i.e. two kernel transitions per object instead
  of roughly zero. Measured here that is invisible against 32 KiB of `memset`; against a
  64-byte object it would dominate completely.
- **Page granularity.** A 20 KiB allocation would round up to 32 KiB of pages and waste 12.
- **A fresh zero-fill fault per page on first touch**, because a new anonymous mapping
  starts out unbacked. The broken version often reuses already-faulted memory.

**The rule of thumb to say out loud:** allocations that are large (several pages or more),
independently lifetimed, and few enough that two system calls each are affordable belong in
their own mappings. Everything else belongs on the heap.

### The repairs that do not work, and why

- **`malloc_zone_pressure_relief`.** Already in the fixture. It returns 0 here. It can only
  release regions that are entirely free, which is exactly what fragmentation prevents.
- **Evicting in allocation order instead of viewport order.** This does help, sometimes a
  lot — but it means the eviction policy is now chosen by the allocator's convenience rather
  than by what the user is looking at. Worth naming as a trade; rarely worth taking.
- **A bigger cache.** Raises the peak and changes nothing about the shape.
- **A custom zone** (`malloc_create_zone`) with tiles allocated from it and the whole zone
  destroyed at once. This genuinely works when whole-generation eviction is acceptable —
  `malloc_destroy_zone` releases everything — but it does not help interleaved eviction,
  which is the case in the prompt.
</details>

---

## Going further

- Change the eviction loop to free the **last half** rather than every other tile and
  re-measure the broken build. Some of the footprint comes back. Explain why that is the
  same defect, not the absence of one.
- Print `malloc_size()` next to each request size in a small probe. On macOS 26.3 the
  size-class ladder rounds 1–128 bytes to 16, 129–256 to 32, 257–512 to 64, and so on,
  doubling the quantum each band. A 129-byte request occupies 160 bytes — 24% overhead
  before any fragmentation at all.