1
Placement: the allocator obeys the hash
On a page fault the allocator computes k candidate frames from the faulting address
and takes the first one that is free. It does not look for a convenient frame — the frame
is dictated by the hash, and the index it lands on is the physical page number, shifted
past the kernel's reserved region.
Page-table pages hash on address >> 21 rather than
>> 12, so a whole 2 MB region's PTEs share one hashed frame —
which is what lets the engine speculate on the walk as well as on the data.
2
Prediction: the engine replays the same arithmetic
The engine never consults a table. It re-derives the candidates from the virtual address with
the identical hash, adds the kernel offset, shifts back to a byte address and re-attaches the
page offset.
Both halves call the same one-liner, so the two sides cannot drift apart by accident:
The invariant. The allocator hashes i · to_hash for
i = 1…k; the engine hashes to_hash · (i+1) for
i = 0…k−1. Same multiplier set, same order — so candidate
j means the same frame on both sides. Change one and you must change the other; there
is no cross-check at runtime, the predictions just stop landing.
3
The race: prefetch the guesses while the walk runs
Each candidate is aligned to a cache line and handed to the L2 controller as an MMU prefetch,
tagged PAGE_TABLE_DATA or DATA so it lands in the right MSHR map. The
engine records the earliest completion, then upgrades that to the specific completion
of whichever candidate turns out to be right.
With k hashes the engine issues up to k prefetches, at
most one of which is right — so more hashes buy placement freedom at the cost of wasted
memory traffic. The optional filters exist to spend that traffic more carefully:
filter drops candidate j>0 when hash j is barely used, or
when the modelled DRAM latency for that address already exceeds a per-hash threshold.
4
Validation: the walk is still the authority
The MMU calls the engine only after a successful walk, passing the true physical
address — speculation never installs a translation, it only warms the cache. A guess that
arrives after the walk already finished bought nothing, and is counted as such.
A wrong guess therefore costs bandwidth and cache pressure, never correctness.
That asymmetry is why the design can afford to be aggressive when memory is empty.
5
Degradation: what happens when every hash is taken
This is the part that decides whether the idea holds up. If all k candidate slots are
occupied and swapping does not free one, the allocator falls back to a linear scan and puts the
page somewhere the hash does not point.
That page is now permanently unpredictable: the engine will keep proposing its k
hashed frames and keep missing. The fraction of such pages grows with occupancy — which is
why the artifact sweeps target_fragmentation from an empty pool to 80% full rather
than reporting a single number. More hashes push the fallback further out; swap mode buys room
by evicting a victim instead of giving up on the hash.
Read the stats, not just the IPC. hits_per_hash[i] against
prefetches_per_hash[i] tells you how much each additional hash actually earns, and
spec_late_mispredict how often a guess was both wrong and late. If hash 2 and 3
show hits near zero, the extra memory traffic is pure cost.