free-space-map

# free-space-map — where INSERT finds room

The Free Space Map tracks approximate free space per page in a relation, so INSERT and other appenders can find a target page without scanning. It's a **fork** of the relation (like the visibility map — a separate file at `<relfilenumber>_fsm`), organized as a tree over the heap's page numbers.

The design tradeoff: exact byte-level accounting would require WAL-logging every space change and dominate write traffic. Instead, FSM stores a small **category** per heap page (5 bits, 32 buckets) and updates it lazily — not WAL-logged in the hot path — with periodic reconciliation by VACUUM.

## The file map

| File | Lines | Role |
|---|---:|---|
| `freespace.c` | ~870 | Main API: `RecordAndGetPageWithFreeSpace`, `GetPageWithFreeSpace`, `RecordPageWithFreeSpace`, `FreeSpaceMapVacuum{Range}`. Tree traversal + descent. |
| `fsmpage.c` | ~430 | Per-FSM-page operations. Each FSM page is a binary tree; `fsm_search_avail`, `fsm_set_and_search`, path navigation within a page. |
| `indexfsm.c` | ~55 | The 2-function shim for indexes. Indexes reuse the FSM machinery but only for "is this page reusable?" — the category is 0/nonzero. |

The README in `src/backend/storage/freespace/` has an ASCII diagram of the tree layout — read it before touching FSM code. It's the shortest path to understanding the layout.

## The 3-level tree

FSM's `<relfilenumber>_fsm` file contains FSM PAGES (not heap pages). Each FSM page holds a **binary tree of 4096 slots**, packed. Slots at the bottom level correspond to heap pages (one FSM slot ~ one heap page). Slots higher up hold **maximums of their children**.

Traversal to find a heap page with N bytes free:

1. Start at the FSM tree root.
2. At each level: read the root slot's value (which is the max in its subtree). If < N, this subtree can't help.
3. Otherwise descend into the left or right child (whichever has the max).
4. Eventually reach a leaf slot → return the heap block number.

Insert of new free-space info:

1. Update the leaf slot for the heap page.
2. If the leaf slot changed, propagate up: parent's slot = max(children).
3. If parent changed, keep propagating.
4. Stop when a parent's value doesn't change.

## The category encoding

Free space is bucketed into **32 categories** (5 bits per slot). Category 0 = 0 bytes free. Category 31 = at least 31 × (BLCKSZ / 32) = ~256 bytes buckets. See `MaxFSMRequestSize` in `freespace.h`.

Consequence: FSM tells you "at least category N free" but the actual number could be higher. Callers that need EXACT free must double-check the page after locking it. `RecordAndGetPageWithFreeSpace` also encapsulates the "get + record actual" round-trip.

## The lock discipline

FSM pages have **their own lock protocol**, DIFFERENT from heap pages:

- `RelationExtensionLock` (heavyweight lock) — held only while extending a relation (adding a new page). NOT during FSM navigation.
- **FSM page pin + share/exclusive** — normal buffer lock semantics, but FSM concurrent readers/writers are very tolerant of stale data because the encoded value is approximate anyway.
- **No WAL logging in the hot path** — `RecordPageWithFreeSpace` is a hint. It's OK if a crash loses the FSM update; VACUUM will reconcile.
- **VACUUM's FSM pass IS logged** — `FreeSpaceMapVacuum` after a heap scan writes canonical values that are WAL'd.

This asymmetry is by design: hot-path INSERTs don't slow down for FSM updates; recovery re-derives from the vacuum-produced records.

## The public API surface (freespace.c)

- `GetPageWithFreeSpace(rel, min_space)` — read-only: find a page with at least `min_space` bytes free. Returns block# or `InvalidBlockNumber`.
- `RecordAndGetPageWithFreeSpace(rel, oldPage, oldFreeSpace, min_space)` — combined: record that `oldPage` has `oldFreeSpace` bytes free, AND find a new candidate. Common pattern: after failing to fit a tuple, tell FSM the actual remaining free space + get another candidate.
- `RecordPageWithFreeSpace(rel, page, spaceAvail)` — pure record; no lookup.
- `XLogRecordPageWithFreeSpace(reln, page, spaceAvail)` — write a WAL record about a page's free space (used by heap_multi_insert for post-COPY reconciliation).
- `FreeSpaceMapVacuumRange(rel, start, end)` — canonical reconciliation over a page range. Called by VACUUM.
- `FreeSpaceMapVacuum(rel)` — same for the whole relation.

## When FSM lies (and how)

The category-encoded value can drift below reality:

- INSERTS that don't fit: caller records the ACTUAL remaining space, so this converges.
- DELETEs that don't record: FSM stays stale (says "less free" than reality). VACUUM fixes.
- VACUUM's post-scan pass writes canonical values.

The category-encoded value can also drift ABOVE reality:

- Concurrent INSERT into the "found" page fills it before you write. Caller must re-check after buffer lock.

**This is why `RelationGetBufferForTuple` (in `access/heap/hio.c`) has a retry loop** — it may consult FSM 2-3 times before either committing to a page or extending the relation.

## Index FSM

Indexes track "empty pages that can be recycled" — a bit for each page. Uses the same FSM machinery but only cares about category 0 (fully-empty) vs nonzero. Consumed by btree page-splits (which drop-and-recycle) and by btree page-deletes.

Files: `indexfsm.c` (the shim), plus per-index-AM users:
- `access/nbtree/nbtxlog.c` + `nbtree.c` — records + reads pages.
- `access/hash/hashovfl.c` — hash overflow page recycling (uses its own bitmap for MUCH tighter tracking, not FSM).

## Common patch shapes

### Add a new FSM consumer

- Call `GetPageWithFreeSpace` in the search phase.
- After committing space use, call `RecordPageWithFreeSpace` with the remaining.
- Add a WAL log via `XLogRecordPageWithFreeSpace` if reliability matters for the recovery-side FSM state.
- Test with `pg_freespacemap` (contrib) to verify the FSM state after your workload.

### Debug "INSERT is extending the relation instead of reusing space"

- `pg_freespacemap.pg_freespace(rel::regclass, blkno)` — see the encoded category.
- If category=0 for pages that clearly have space: VACUUM hasn't reconciled since the last delete. Run VACUUM.
- If categories look right but INSERT still extends: your row's `min_space` request may be larger than any single-page category can encode. Check `MaxFSMRequestSize`.

### Change the category encoding (rare, dangerous)

Would touch `fsm_get_max_avail`, `fsm_free_bits_to_avail`, all callers relying on bucket size, plus on-disk file format (bump `FSM_PAGE_MAGIC`). Almost certainly requires hackers-list discussion.

## Pitfalls

- **FSM is NOT crash-safe by default** — hot-path updates are unlogged. This is intentional; recovery uses VACUUM's post-scan pass. Don't add "just log it" without hackers discussion.
- **FSM can point at now-full pages** — the "found" page may be full by the time you lock it. Every consumer must re-check under buffer lock.
- **Concurrent extensions can race with FSM traversal** — a new page appears; FSM tree may not know about it yet. `RelationGetBufferForTuple` handles this with retry.
- **VACUUM's FSM pass is expensive on huge tables** — it walks the whole tree. In PG 17+ it's incremental; in older releases it always did the whole relation.
- **`MaxFSMRequestSize`** — you can only ask for up to this much space; larger requests always miss FSM and extend the relation. Something like ~BLCKSZ/4.
- **Small relations skip FSM** — if the relation is under `HEAP_FSM_CREATION_THRESHOLD` pages, no FSM fork is created (small tables just do sequential-fit). This means the first ~10 pages don't get FSM tracking.
- **Index FSM has different semantics** — category 0 vs nonzero, no bucket ladder. Don't code as if index FSM is heap FSM.
- **FSM lives per-fork per-relation** — main fork FSM (for INSERT). Toast tables have their own FSM. Indexes have their own FSM. Don't cross-reference.

## Related corpus

- **Idiom**: no direct FSM idiom (candidate for future authoring). The FSM interacts with `heap-tuple-freeze` (VACUUM's post-heap-scan FSM pass) and `vacuum-two-pass-heap` (the orchestration).
- **File docs**: `knowledge/files/src/backend/storage/freespace/freespace.c.md`, `fsmpage.c.md`, `indexfsm.c.md`.
- **Subsystems**: `storage-buffer` (FSM pages are buffered), `access-heap` (`hio.c` is the primary consumer via `RelationGetBufferForTuple`), `vacuum-autovacuum` (the reconciliation driver).
- **README**: `source/src/backend/storage/freespace/README` — the definitive design doc; shorter than this skill and worth reading before deep work.

## Corpus-chain shortcut

```
python3 scripts/corpus-chain.py --file src/backend/storage/freespace/freespace.c
python3 scripts/corpus-chain.py --file src/backend/access/heap/hio.c
```

Second one shows the primary consumer — RelationGetBufferForTuple + its retry loop.

## Boundary

**Use this skill** for `src/backend/storage/freespace/` + FSM consumers.

**Don't use** for:
- **Visibility Map** — sibling machinery in `storage/freespace/`? NO — VM is in `access/heap/visibilitymap.c`. Different subsystem, different design.
- **`pg_freespacemap` contrib** — SQL introspection wrapper over FSM; small contrib module, use its own docs if the ask is about the SQL interface.
- **Btree page-deletion tracking** — uses index FSM but the recycling logic is in `access/nbtree/`; skill lives there.
- **Hash overflow-page management** — uses its own bitmap, NOT FSM. See `contrib-hash` or the hash-am subsystem.