The Free List and Page Reuse

Keep a list of free pages in the file: its head and length in two new header fields, and in each free page the number of the next. pager free puts a page at the head; every allocation takes the head before it makes the file longer. Show the list with db freelist.

Not run yet · 10 tests

Why this stage exists

Every page you have ever allocated is still in the file. Nothing gives one back: a page used for a while and then abandoned keeps its place, and the next allocation makes the file longer instead of using it. With what you have built so far that rarely matters, because nothing abandons a page. The next stages do. DROP TABLE throws away a whole tree, merging leaves on DELETE empties pages, and overflow chains come and go with the rows that own them. Without a way to reuse those pages, the file only ever grows, however small the data in it gets.

So before anything frees pages, there has to be a place for freed pages to go. Real databases call it the free list. It is the simplest structure that works: the free pages chained together, and the start of the chain written down somewhere you can always find it.

What changes: the header knows where the list starts

The header gains two fields after the root: the first free page, the head, and how many pages are on the list. A file with no free pages has zeros there, which is exactly what every header written before this stage already holds, so old files need no conversion.

magicbytes 0–7 (8 bytes) · droid db
versionbytes 8–11 (4 bytes) · 1
page sizebytes 12–15 (4 bytes) · 4096
rootbytes 16–19 (4 bytes) · the first tree's root, as before: 0, this file has no table
free headbytes 20–23 (4 bytes) · the first free page: 4. Page 0 is never free, so 0 means none
free pagesbytes 24–27 (4 bytes) · how many pages are on the list: 2

The first 28 bytes of page 0 of a file of five pages, the header and pages 1 to 4, after page 2 and then page 4 were freed. The new fields are bytes 20 to 23 and 24 to 27, little-endian like every integer in the file.

What changes: a free page points at the next

A free page is a page of type 4. It keeps the number of the next free page at bytes 10 to 13, the same place a B+Tree node keeps its link, and nothing else: every other byte up to the trailer is zero, and the trailer is written as for any page.

typebytes 0–0 (1 bytes) · 4: a free page
zerosbytes 1–9 (9 bytes) · unused
nextbytes 10–13 (4 bytes) · the next free page: 2. The last page of the list has 0

The first 14 bytes of free page 4. The rest is zeros up to the trailer. The type byte means btree dump and the page commands refuse it, as they refuse any page that is not theirs.

Follow the chain from the header and you visit every free page once:

Where	Says
header	head is page 4, 2 pages on the list
page 4	type 4, next is page 2
page 2	type 4, next is 0: the end

Freeing a page writes it as a free page whose next is the current head, then makes it the head and adds one to the count. Allocating takes the head: its next becomes the head, the count goes down by one, and the page is zeroed before anyone sees it. The last page freed is the first one reused, which is why only the head ever matters: nobody searches the list.

Both operations change two pages, the header and the free page, and both stay in the buffer pool like any other change until they are written. The list survives a restart because it is in those pages, not in memory.

SQLite keeps its free list the same way, a head and a count in the database header, except that its free pages are mostly "leaf" pages listed inside "trunk" pages, so one trunk read finds hundreds of free pages at once. PostgreSQL has no file-wide list; each table keeps a free space map of how full its own pages are.

The algorithm in words

Free a page

Freeing puts the page at the head of the list.

1.Check the page exists (00601), is not page 0 (01204), and is not already on the list (01203). Any of these changes nothing.
2.Turn the page into a free page: type 4 at byte 0, the current head at bytes 10 to 13, zeros everywhere else. Its old contents are gone.
3.Make it the head, and add 1 to the count. Both are header fields, so the header changes too.
4.Invariant: following next from the head visits exactly count pages, every one of type 4, and ends at 0.

Allocate a page

Every allocation, by pager alloc or by a statement that needs a page, asks the list first.

1.If the count is 0, make the file one page longer, as before.
2.Otherwise take the head. Its next becomes the new head, and the count goes down by 1.
3.Zero the whole page before handing it over, so nothing of the free page or of what it held before leaks out.
4.Invariant: total_pages and the size of the file never go down, and only go up when the list is empty.

Show the list

db freelist walks the chain.

1.Print the count and the pages from the head, following next, in list order.
2.On a file with no pages, print an empty list and create nothing: no header, no page.

Output contract for this stage

The full definition is on the output contract page, section 26.

Input	Output
`pager free <n>`	`[PAGER] Free: page <n>`
`db freelist`	`[DB] Free list: pages=<k> chain=[<p1>,<p2>,...]`, from the head; `pages=0 chain=[]` when empty
`pager free` of a page never allocated	`[ERROR:00601] <message>`, checked first
`pager free 0`	`[ERROR:01204] <message>`
`pager free` of a page already on the list	`[ERROR:01203] <message>`
`pager alloc` with a non-empty list	`[PAGER] Alloc: page <n> (4096 bytes, zeroed)`, `n` the old head

db header prints the line of section 18, unchanged. btree dump of a free page is 00703 and a page command on it 00606; pager get, read and write work on it as on any page.

What you should see when done

On a file of five pages, the header and pages 1 to 4:

shell

$droid --db pages.db
Welcome to droid!
>db freelist
[DB] Free list: pages=0 chain=[]
>pager free 1
[PAGER] Free: page 1
>pager free 3
[PAGER] Free: page 3
>db freelist
[DB] Free list: pages=2 chain=[3,1]
>pager free 3
[ERROR:01203] Page 3 is already free
>pager alloc
[PAGER] Alloc: page 3 (4096 bytes, zeroed)
>.exit
exiting.. good bye!

shell

$droid --db pages.db
Welcome to droid!
>db freelist
[DB] Free list: pages=1 chain=[1]
>pager alloc
[PAGER] Alloc: page 1 (4096 bytes, zeroed)
>pager alloc
[PAGER] Alloc: page 5 (4096 bytes, zeroed)
>.exit
exiting.. good bye!

Things to notice. Page 3 was freed last and came back first. The allocation did not make the file longer: it took page 3 instead of making page 5. The next session found page 1 still on the list, because the list is in the file, and only once it was empty did an allocation make page 5.

Common bugs in this stage

Keeping the list only in memory. It works until the first restart, when the freed pages are lost for good. Head and count belong in the header, and next in each free page.
Not zeroing a reused page. A reused page that still says type 4, or still holds an old row, is read back as whatever it used to be. Zero all of it on allocation.
Forgetting to mark the header dirty. Freeing and allocating change the header. If it is not written, the next session sees the old head and hands out a page that is already in use.
Allocating past the list. Every allocation must ask the list first: pager alloc, a leaf split, a new table's root. One code path that still appends to the file is enough to waste pages.
Checking the codes in the wrong order. A page that does not exist is 00601 before anything else, so pager free 0 on an empty file is 00601, not 01204.
Double free. Putting a page on the list twice makes a loop or hands the same page to two owners. Walk the list to check, or keep a set alongside it; the count is not enough.

Language notes

The page above is the same for every language. These are the only language-specific hints.

C: read and write the header fields with the same little-endian helpers as the root. memset the page to zero on allocation, then set nothing else: the caller decides what the page becomes.
C++: the same; a small struct view over the header bytes is tempting, but padding and byte order make explicit reads and writes safer.
Rust: u32::from_le_bytes over a four-byte slice reads a header field, and to_le_bytes writes one. fill(0) zeroes a reused page.
Zig: std.mem.readInt and std.mem.writeInt with .little read and write the fields; @memset zeroes a page.

Loading starter code…

No run yet

10 tests wait for your first run

Run tests builds your code, drives the binary through every case for this stage, and shows expected and received output side by side here. Failing cases come first.