The Free List and Page Reuse

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.

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.

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

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.

Output contract for this stage

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

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:

$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!

$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.