FreeBSD / vm_map / options DIAGNOSTIC

vm_map Check Walkthrough

companion to Quadratic vm_map Check After fork() _vm_map_assert_consistent(), the linear check example: 7 entries, addresses in pages, map range 0 to 256

The check walks the map's tree once, depth-first. It carries three things: cur, the entry being checked; lbound, the nearest ancestor the walk went right from; and ubound, the nearest ancestor it went left from. Every entry in the subtree under cur must lie within [lbound->end, ubound->start]; touching a bound is allowed, since neighboring entries often abut. A fourth thing, pending, holds the sides it has put off.

At the top of the tree both bounds are the header, which plays both ends at once: its end is the map's minimum address and its start is the maximum. A leaf has no children, so its links point at its in-order neighbors instead, and those neighbors are exactly the bounds: a link equal to its bound is a thread, anything else is a child.

The example map: seven entries, one tree, the header at both ends

Children: solid lines. A leaf's links are threads to its in-order neighbors. Addresses in pages. d [9,10)max_free 240 b [5,6)max_free 3 f [13,14)max_free 240 a [1,2)max_free 3 left → headerright → b c [7,8)max_free 1 left → bright → d e [11,12)max_free 1 left → dright → f g [15,16)max_free 240 left → fright → header // 0 4 8 12 16 256 a b c d e f g header->end = 0the floor; header->right = a, the first entry header->start = 256the ceiling; header->left = g, the last entry g's max_free is 240: the gap from 16 to 256. a's is 3: the gap from 2 to 5.
One struct at both ends. The header's end is the floor and its start is the ceiling, so it serves as lbound for the leftmost entries and as ubound for the rightmost ones. max_free is the largest gap in a subtree, counting the gaps to its bounds; the walk recomputes it from the two sides and compares.

One node, every check: step 2 at b, with lbound = header and ubound = d

AssertionWith the values at bResult
cur != headerb is an entryholds
cur->start < cur->end5 < 6holds
lbound->end <= cur->startheader->end 0 <= 5holds
cur->end <= ubound->start6 <= d->start 9holds
left == header || left->start < cur->startleft is a: 1 < 5holds
right == header || cur->start < right->startright is c: 5 < 7holds
left != header || header->right == curleft is a, not the headernot applicable
right != header || header->left == curright is c, not the headernot applicable
max_free == max(max_left, max_right)a is a child, so max_left = a->max_free = 3; c is a child, so max_right = c->max_free = 1; max is 3, and b->max_free is 3holds
Then the moveWith the values at bOutcome
left != lbound and right != ubounda is not the header, c is not dtwo children: one side must wait
left span cur->start - lbound->end5 - 0 = 55 < 3 is false, so the right side goes first
right span ubound->start - cur->end9 - 6 = 3
pending[sp] = { cur, the far bound }{ b, lbound = header }sp becomes 2
descend rightlbound = b, ubound stays d, cur = cstep 3 checks c against (b, d)
Nine assertions, then one decision. The two header assertions only apply to a link that is the header, so at b they do not fire. A thread side contributes its gap to max_free; a child side contributes the child's own max_free. The spans use the bounds, not the children, so the right side can be the smaller one even when the left child is the nearer address. Before step 1 the function also checks that header->end <= header->start (0 <= 256) and that a map with no root has both header links pointing at the header itself.

The walk: seven steps, and the bounds at each one

Step number in teal; under each node, the (lbound, ubound) it was checked against. d [9,10)(header, header) 1 b [5,6)(header, d) 2 f [13,14)(d, header) 5 a [1,2)(header, b) 4 c [7,8)(b, d) 3 e [11,12)(d, f) 6 g [15,16)(f, header) 7 Each bound is an ancestor on the path from the root, or the header. Going left sets ubound to the node left behind; going right sets lbound.
StepcurlbounduboundLinksSpans L / RActionPending after
1dheaderheaderb child, f child9 / 246left first; push {d, header}; ubound = d{d, header}
2bheaderda child, c child5 / 3right first; push {b, header}; lbound = b{d, header} {b, header}
3cbdb thread, d threadpop {b, header}: 7 < 5 is false, so the left side remains; lbound = header, ubound = b, cur = a{d, header}
4aheaderbheader thread (header->right == a), b threadpop {d, header}: 1 < 9, so the right side remains; lbound = d, ubound = header, cur = fempty
5fdheadere child, g child3 / 242left first; push {f, header}; ubound = f{f, header}
6edfd thread, f threadpop {f, header}: 11 < 13, so the right side remains; lbound = f, ubound = header, cur = gempty
7gfheaderf thread, header thread (header->left == g)nothing pending: doneempty
Every node once, two slots at most. A node with two children pushes the side it is not taking and descends; a node whose links are both threads pops. The spans decide the order: at d and f the right side runs to the top of the map, so the left side goes first; at b the right gap is the smaller one. This trace is the output of the checker itself, run on the example in userland.

Popping: the entry just visited says which side is left

Step 3: pop {b, header} with cur = c pending top: {b, header} b [5,6) a [1,2) c [7,8) cur, done 7 < 5 is false: cur came from the right, so the left remains. lbound = header (saved), ubound = b, cur = b->left = a Step 4: pop {d, header} with cur = a pending top: {d, header} d [9,10) b subtree f [13,14) cur = a, done 1 < 9: cur came from the left, so the right remains. lbound = d, ubound = header (saved), cur = d->right = f
Two pointers per slot, no direction flag. A slot stores the node and the bound on its far side. When the walk runs out of children it pops the slot and compares cur->start with the node's start: the bounds guarantee everything under the left child is below the node and everything under the right child is above it, so that one comparison says which side was visited. The node itself becomes the near bound of the side that remains, and the saved bound returns as the far one.

Why 64 slots are always enough

At a node with two children, the span S = ubound->start - lbound->end splits three ways left span cur right span, pushed left + right = S - (cur->end - cur->start) < S, so the smaller side is less than S / 2. Ties go right. In the example, with two slots in use (step 2) at d: S = 256 - 0 = 256 left of d: 9 - 0 = 9 right of b: 9 - 6 = 3 →→ After k pushes the span is below 2^64 / 2^k on a 64-bit map. A push needs a span of at least 3 (two children and the node, one byte each), so no push is possible after 62 halvings: at most 63 slots are ever in use, and the array has 64, one per address bit. The walk never revisits a node either: a node's range fits in only one place between the bounds, so a map that loops asserts instead.
The address space bounds the pending depth, not the entry count. Each slot in use represents one halving of the span, so even a map with millions of entries cannot need more slots than the address has bits. That is why the array is pending[sizeof(vm_offset_t) * NBBY] and overflow is an assertion, not a case.