Pager and Buffer Pool

Allocate pages of 4096 zero bytes numbered 0, 1, 2, and so on, give back any allocated page by its number, store bytes in a page and read them back, and refuse page numbers that do not name an allocated page.

Not run yet · 17 tests

Why this stage exists

The previous stage turned a row into 60 bytes. Those bytes need somewhere to live, and the somewhere cannot be "wherever the language puts things": the next stage writes them to a file and a later run of the program reads them back. A file is read and written in fixed-size blocks, so the engine is built on the same idea. Storage is a sequence of pages of 4096 bytes each, named by number: page 0, page 1, page 2.

The pager is the one component that owns the pages. Every other layer asks it for page N and gets back that page's bytes; nothing else allocates a page or decides where one lives. In this stage the pages live in memory only. That is on purpose: numbering, bounds and the bytes of a page can be checked on their own, before a file adds the question of what is on disk and what is not.

Nothing else in the engine uses the pager yet. The B+Tree, from the btree-leaf stage on, stores its nodes in pages, one node per page, and asks for them by number.

What changes: numbered pages of bytes

A page is 4096 bytes and nothing else: no type, no header, no length. What a page means is decided by whoever writes it. For now that is you, with two debug commands: pager write puts a text at the start of a page followed by a zero byte, and pager read reads up to the first zero byte.

These are the first 16 bytes of page 0 after pager write 0 hello world, then pager write 0 hi:

textbytes 0–1 (2 bytes) · 'hi', from the second write
endbytes 2–2 (1 bytes) · the zero byte the second write put after it
old bytesbytes 3–11 (9 bytes) · 'lo world' and its zero, left by the first write
never writtenbytes 12–15 (4 bytes) · still zero, like the 4080 bytes after them

The second write copied two bytes and a zero, and touched nothing else. A read stops at the first zero, so it gives back 'hi'. The rest of the first write is still in the page, unreachable.

The old bytes staying in the page is not a bug. A page is storage, not a string: writing to it changes the bytes you write and no others. Later stages rely on exactly that when they update one cell of a page and leave the rest alone.

Pages are named by number

A page number is a position: page 5 is the sixth page. It is never an address in memory. The next stage makes this matter, because page 5 is then the 4096 bytes at offset 5 × 4096 in the file, and that has to be true in every run of the program. So allocation always gives the next number, 0, 1, 2, in order, with no gaps, and a number that was never handed out names nothing.

A limit, and bounds

The pager holds at most 1000 pages. The 1001st allocation is error 00602: refused, not crashed, and the 1000 pages that exist are untouched.

Asking for a page that was never allocated is error 00601, whether it is the page just after the last one or page 999 of an empty pager. It is not a reason to allocate the page. A lookup that quietly creates what it looked for hides the bug that asked for the wrong page.

Why "buffer pool" and "cache hit" already

pager get reports CACHE_HIT and pager status reports how many pages are cached. In this stage every allocated page is in memory, so cached always equals total_pages and every get is a hit. The words are there because the next stage changes the answer: once pages come from a file, a page that has not been read yet is a CACHE_MISS, read from disk on first use. Later still, when the file can hold more pages than memory, the pager keeps some of them and lets others go, and the page table becomes a real buffer pool. The page table you build now is the thing those stages extend.

The algorithm in words

Allocate a page

A new page is always the next number, and always starts as zeros.

1.If 1000 pages already exist, refuse with error 00602 and change nothing.
2.Otherwise the new page's number is the number of pages that exist now: 0 for the first, 1 for the second.
3.Give it 4096 bytes, every one of them zero, and keep them in the page table under that number.
4.Invariants: page numbers have no gaps and are never reused; the count of pages grew by exactly one; no other page changed.

Get a page by its number

Every command that touches a page, get, read and write, starts here.

1.The argument must be decimal digits. Anything else, a negative number included, is error 00104.
2.If the number is not smaller than the count of pages, the page was never allocated: error 00601. Nothing is allocated.
3.Otherwise the page is in the page table. In this stage it always is, so the answer is always a cache hit.
4.Invariant: getting a page never changes its bytes and never changes the count of pages.

Write and read the bytes of a page

Two debug commands that prove a page really is 4096 bytes you can change and read back.

1.Write: copy the bytes of the text to the start of the page, then one zero byte after them. Bytes after that zero stay as they were.
2.Read: take the bytes from the start of the page up to the first zero byte.
3.Invariants: after a write, a read of the same page gives back exactly that text; writing one page never changes another.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, sections 3 and 7.

Input	Output
`pager status`	`[PAGER] Status: total_pages=<n> cached=<m>`
`pager alloc`	`[PAGER] Alloc: page <n> (4096 bytes, zeroed)`
`pager get <n>`	`[PAGER] Get page <n>: CACHE_HIT`
`pager write <n> <text>`	`[PAGER] Write page <n>: <k> bytes`, where `<k>` is the length of the text in bytes
`pager read <n>`	`[PAGER] Read page <n>: '<text>'`, the bytes up to the first zero byte
a page that was never allocated, to `get`, `read` or `write`	`[ERROR:00601] <message>`
`pager alloc` when 1000 pages exist	`[ERROR:00602] <message>`
a page number that is not decimal digits, or no page number	`[ERROR:00104] <message>`

A fresh start has total_pages=0 cached=0. cached counts the pages in memory, which in this stage is every allocated page. The text of pager write is the rest of the line after the page number and one space, spaces inside it included. A page nothing has written reads back as ''. An error changes nothing: no page is allocated, no byte is written.

What you should see when done

droid session

Welcome to droid!
>pager status
[PAGER] Status: total_pages=0 cached=0
>pager alloc
[PAGER] Alloc: page 0 (4096 bytes, zeroed)
>pager alloc
[PAGER] Alloc: page 1 (4096 bytes, zeroed)
>pager write 0 hello world
[PAGER] Write page 0: 11 bytes
>pager write 0 hi
[PAGER] Write page 0: 2 bytes
>pager read 0
[PAGER] Read page 0: 'hi'
>pager read 1
[PAGER] Read page 1: ''
>pager get 1
[PAGER] Get page 1: CACHE_HIT
>pager get 2
[ERROR:00601] Page 2 was never allocated
>pager get -1
[ERROR:00104] Not a page number: -1
>pager status
[PAGER] Status: total_pages=2 cached=2
>.exit
exiting.. good bye!

Three things to notice. hi written over hello world reads back as hi, although most of hello world is still in the page. Page 1 reads back empty after page 0 was written: pages share nothing. And the failed get 2 did not create page 2; the count is still 2. The error messages are yours to word; the tests check only the codes.

Common bugs in this stage

Printing without storing. A counter and a few print statements pass status and alloc, and fail every write and read case. The page has to be real bytes.
A page smaller than 4096 bytes. A short fixed field holds hello world and truncates a 4000-byte text. Give every page all 4096 bytes.
New pages that are not zero. Memory from the language's allocator may hold whatever was there before. pager read of a new page must be '', so zero the page when you allocate it.
One buffer shared by every page. Writing page 0 then reading page 1 gives page 0's text. Each page number needs its own 4096 bytes.
No zero byte after the text. hi over hello world reads back as hillo world. The write puts a zero after what it copied.
Off by one at the last page. With 2 pages, page 1 exists and page 2 does not. The valid numbers are 0 up to one less than the count.
A lookup that allocates. pager get 5 on a pager with 2 pages creates pages up to 5, or bumps the count. An error changes nothing.
A crash on a bad number. abc read as 0, or -1 wrapping around to a huge unsigned number and indexing past the page table. Check the argument is digits before you use it as a number.
The 1001st page. Checking the limit after allocating, so page 1000 exists for a moment, or the count reads 1001.

Language notes

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

C and C++: calloc returns zeroed memory; malloc does not. A table of pointers to pages lets each page stay where it was allocated. Parse page numbers with a function that reports where it stopped, such as strtoul with its end pointer, and reject a leading - yourself: strtoul accepts it.
Rust: vec![0u8; 4096] or Box::new([0u8; 4096]) gives a zeroed page. str::parse::<u32> rejects -1 and abc for you.
Zig: allocator.alloc(u8, 4096) does not zero the memory; @memset(page, 0) does. std.fmt.parseInt(u32, text, 10) returns an error for -1 and abc.
Every language: if pages live inline in a growable array, adding a page may move all of them in memory. Nothing holds on to a page across commands yet, but the B+Tree will. Keeping each page in its own allocation avoids the problem.

Loading starter code…

No run yet

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