CSE Roadmap

Core tier · about 6 hours · 7 parts

Part 4 of 7 · 3 min read

Table entries

In plain words: One row of the page table is a page table entry (PTE). It holds the frame number, and a few bits that the hardware and the kernel use:

Bit Name Meaning
Present (valid) P The page is in memory; if 0, an access traps (page 7)
Read/write W Writes are allowed
User/supervisor U User code may access it, and not only the kernel
Accessed A Set by the hardware when the page is read or written
Dirty D Set by the hardware when the page is written
No-execute NX Code may not be run from this page

On x86-64, the present bit is bit 0, the writable bit is bit 1, the user bit is bit 2, the accessed bit is bit 5, the dirty bit is bit 6 and the no-execute bit is bit 63. The frame number sits in the middle bits. The accessed and dirty bits are set by the hardware without any instruction. The replacement algorithms of page 8 depend on them.

The kernel lets a root user read these entries through /proc/self/pagemap: one 8-byte value for each virtual page, with the top bit set when the page is present and the low 55 bits holding the frame number. A short program mapped six pages with mmap and checked their entries:

char *p = mmap(0, n*ps, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
/* ... before touching: page 0 present = 0 ... */
for (int i = 0; i < n; i++) p[i*ps] = 1;          /* first touch of each page */
/* ... read the entry of each page from /proc/self/pagemap ... */

The output was:

before touching: page 0 present = 0
virtual page 0x7f398b572 -> present 1, frame 0x137273
virtual page 0x7f398b573 -> present 1, frame 0x123edf
virtual page 0x7f398b574 -> present 1, frame 0x1357e5
virtual page 0x7f398b575 -> present 1, frame 0x123b3b
virtual page 0x7f398b576 -> present 1, frame 0x12880a
virtual page 0x7f398b577 -> present 1, frame 0x1210f2

Two facts show up. Before the first touch, the page was not present: the kernel had promised the memory, but had not yet given a frame (page 7 explains why). After the touch, six neighbouring virtual pages sat in six unrelated frames, as in the toy example. A physical address is the frame number times 4,096: frame 0x137273 is at physical address 0x137273000.

Page table entry

A page table entry (PTE) is one record of a page table: it holds the frame number of a page and control bits such as present, writable, user, accessed and dirty, which the hardware checks and updates on each access.

Example: the entry for virtual page 0x7f398b572 held frame 0x137273, with the present bit set.

Check yourself: 1. What does the dirty bit tell the kernel? 2. Why were the frames of neighbouring pages unrelated? 3. What was the value of the present bit before the first touch, and why?