Date: 2026-05-29
Time: 07:50
PageManager.free_pagefreepage returns a disk page to a singly-linked free list so it can be reused by future allocatepage calls. Without it, deleted B-tree nodes would leave permanent holes in the data file — the file would grow monotonically even under heavy delete workloads. This is the deallocation half of the page allocator; allocate_page is the allocation half.
Preconditions:
page_num must refer to a valid, currently-in-use page that is no longer referenced by any B-tree node. The caller is responsible for unlinking it from the tree first. Freeing a page that is still pointed to by an internal node or sibling pointer corrupts the tree silently — nothing enforces this.Postconditions:
next_free (the high-water mark for fresh page allocation) is unchanged — only the free-list head pointer in metadata is updated.Invariant preserved: The free list is a singly-linked list threaded through the pages themselves, terminated by NOSIBLING (0xFFFFFFFF). After this call, freehead → pagenum → oldfreehead → ... → NOSIBLING.
| Parameter | Type | Description |
|-----------|------|-------------|
| self | PageManager | The page manager with an open data file |
| page_num | int | The page number to free. Must be a valid, unreferenced page. No bounds checking is performed. |
None. All effects are through side effects on disk.
1. Read current metadata — fetches (root, height, totalkeys, nextfree, free_head) from page 0.
2. Build a free-list node — constructs a minimal page payload:
struct.pack(HEADER_FMT, 0, 0) → page type 0, key count 0) — type 0 is INTERNAL, but with 0 keys it's recognizable as a free-list node.HEADER_SIZE. This is the "next" pointer in the linked list.3. Write the free-list node to pagenum — overwrites whatever was there. The data is padded to pagesize by write_page.
4. Update metadata — writes the same root, height, totalkeys, and nextfree, but replaces freehead with pagenum. This makes the freed page the new head of the list.
The key insight: the free list is intrusive — each free page stores its own "next" pointer in its body, so no separate data structure is needed.
flush() calls (inside writepage and writemeta).self.pageswritten by 1 (the metadata write goes through writemeta, which bypasses the counter; only the writepage call increments it).PageManager level, below the WAL. The BTree.delete method that calls it wraps the surrounding operations in WAL entries, but the freepage call itself is not individually WAL-protected. If a crash occurs between the writepage and writemeta calls, the page is overwritten but the metadata still points to the old free head — the freed page becomes a leaked orphan.None. If the file I/O fails, the underlying write/seek calls raise OSError and the free list is left in a partially-updated state. There is no rollback or atomicity guarantee at this level.
The only caller in this codebase is BTree._delete at line ~247, which frees an empty leaf after merging its sibling pointer:
self.pm.free_page(child_page)
The caller must:
1. First unlink the page from the tree structure (update parent's children list, fix sibling pointers).
2. Then call free_page.
3. The corresponding allocatepage method checks freehead != NO_SIBLING before allocating from the high-water mark, so freed pages are reused LIFO (most-recently-freed page is allocated first).
struct — for packing the header and pointer in big-endian format.self.readmeta() / self.writemeta() — to atomically read and update the free-list head pointer.self.write_page() — to overwrite the freed page with the free-list node.HEADERFMT (3 bytes: >BH) and implicitly METAFMT (20 bytes: >5I).1. No double-free detection — freeing the same page twice creates a cycle in the free list, causing allocate_page to return the same page number repeatedly, silently corrupting the tree.
2. No bounds checking — page_num could be 0 (the metadata page) or beyond the file's extent; both would corrupt state.
3. No crash atomicity — the writepage and writemeta are not atomic together. A crash between them leaks the page.
4. Free-list node is typed as INTERNAL with 0 keys — allocate_page doesn't validate the page type when popping from the free list, so this works, but nothing prevents confusing a free-list node with a real empty internal node during debugging or recovery.
free-list-is-lifo — The page free list is LIFO: freepage pushes to the head, allocatepage pops from the head, so the most recently freed page is reused first.free-page-not-wal-protected — PageManager.free_page performs two non-atomic writes without WAL logging; a crash between them leaks the freed page permanently.free-list-intrusive-storage — Free-list "next" pointers are stored inside the free pages themselves at offset HEADER_SIZE (byte 3), requiring no separate allocation metadata structure.no-double-free-detection — Calling freepage twice on the same page creates a cycle in the free list, which allocatepage cannot detect, leading to silent corruption.free-page-only-called-from-delete — In this codebase, freepage is only invoked by BTree.delete when removing an emptied leaf node from the tree.