Reversing the Next-Page Prefetcher in Skylake-X
Introduction
Intel publishes very little about next-page prefetchers in their P-cores. Back in the Ivy Bridge days, it was known that IVB included a next-page prefetcher thanks to this ancient excerpt from an old copy of the Intel Architectures Optimization Reference Manual:
Hardware prefetch enhancement: A next-page prefetcher (NPP) is added in Intel microarchitecture code name Ivy Bridge. The NPP is triggered by sequential accesses to cache lines approaching the page boundary, either upwards or downwards.
A recent issue of the optimization manual states that Redwood Cove includes a Last Level Cache (LLC) Page Prefetcher which is like NPP but with a slightly more sophisticated prefetch algorithm:
The LLC Page Prefetcher extends the Next-Page-Prefetcher algorithm, which detects a sequence of accesses that are about to reach the end of a page (either going up towards the next page in memory or down towards the previous page in memory) and triggers a linear prefetch to the start of the next predicted page. NPP intends to prefetch the translation of the next page and initiate prefetching of the first few cache lines from that predicted page.
The LLC Page Prefetch enhances Next-Page Prefetcher in two significant ways:
- It issues prefetches two pages ahead in linear address space.
- The prefetch attempts to bring the entire 4Kb page to the last level cache using opportunistic IDI request slots without the DCU or MLC buffers.
Redwood Cove is a relatively recent microarchitecture which shipped in Meteor Lake P-cores starting late 2023. Ivy Bridge on the other hand is very old; It launched back in 2012 and was discontinued by 2015 right before Skylake launched.
That raises the question, what happened in-between? Did every microarchitecture after IVB include a next-page prefetcher? Itās unlikely that the details remain unchanged from one microarchitecture to the next but as it turns out, I recently got unlimited access to a Skylake-X machine that I didnāt have to pay a single dime for.
Given the setup, itās only natural I got nerd-sniped into reversing the next-page prefetcherā¦and thatās what this post is about. I hope you enjoy it!
So Whatās a Prefetcher
Hardware component that preloads data that the program might need soon. The goal is to eliminate memory stalls when the CPU actually demands the piece of data that the prefetcher could have loaded earlier.
All kinds of prefetchers exist in modern CPUs. Next-Line prefetchers prefetch the immediate next cache line when the Nāth cache line is accessed. Stride prefetchers (usually IP-based) track the stride of consecutive memory accesses that originate from the same instruction and if the access pattern turns out to be regular enough, it eagerly initiates the load from address that it predicted. Next-Page Prefetchers preload page table entries into the Translation Lookaside Buffer (TLB) provided software traverses memory pages in predictable manner.
These by no means are the only three kind; a high-performance CPU may implement many other types of prefetchers, some of which are documented in this Intel whitepaper.
Prefetchers that are required to act fast are logically simple and tend not to cross page boundaries because that may complicate things with, e.g. page faults and page walks on TLB misses. For example, the next-line prefetcher is supposed to fetch the next cache line if the accesses are sequential, but if the next cache line sits in a different page it may decide not to prefetch at all.
Next-page prefetchers are slightly different in that regard; they prefetch the next page table entry (PTE) into the TLB. They have to work across page boundaries by design.
In this post Iāll try to answer the following questions:
- Does Skylake-X have a next-page prefetcher?
- If yes, what triggers the next-page prefetch?
- How many āfutureā PTEs are prefetched?
- Where does the NPP load future PTEs?
- Whatās the direction of the prefetch? Forward-only? Backward-only (thatād be weird!)? Both?
But before we start, letās prepare the stage for our experiments.
Setting-up Linux for Experiments
If you donāt intend to run the experiments described in this post, you can skip this part. Documenting the many details of performance monitoring on various platforms deserves a post of its own, and a fairly long one at that. For simplicity Iām only going to focus on Linux.
Linux allows configuring performance monitoring events via the perf_event_open syscall. Thatās what Iāll be using in my experiments too but generally speaking, you donāt need special system APIs to access PMU counters. At least on Intel, you only need some way of writing a set of performance monitoring MSRs (usually only the IA32_PERFEVTSELx MSRs) and read the counters back from a set of corresponding IA32_PMCx MSRs. WRMSR and RDMSR require Ring0 access so if youāre on Windows, youād have to write a kernel-mode driver and use __readmsr / __writemsr intrinsics to read/write the relevant MSRs. That said, the hard part of making custom drivers for Windows isnāt writing the driver itself, rather convincing the kernel to load your driver. More on that in a future blog post.
Performance monitoring tools that allow reading PMU counters (e.g. perf, VTune) may also work. Iād stick to perf_event_open because it allows better control over the exact segment of code I need to measure. The manpage includes an example of how to use perf_event_open.
For our experiments we need three things in order:
- Configuring the events we want to count. Initially all counters will be disabled.
- Enabling the counters and running the workload. Hereās where the
IA32_PMCxcounters start ticking. - Once the workload completes execution, stopping the counters and reading their values.
Weāll write a helper for each of these steps: configure_event_group to configure the events, start_counters to enable the counters, and stop_counters to stop and read the counters.
With that aside, hereās configure_event_group:
Full source code of every experiment, data structure, and helpers used in this article can be found on github.
The group_fd identifies the event group that you configure via perf_event_open. You can use that group_fd to perform certain operations on the event group, like enabling or disabling the counters. Thatās what weāre going to do next: enable the counters with start_counters which is defined like this:
Calling start_counters sets off the counters for every event configured in the event group identified by group_fd. At this point weāll run our workload, then call stop_counters to stop and read the counters:
Before we can read PMU counters using the functions defined above, we need to tweak some settings on Linux. Depending on your distro, certain restrictions may apply by default on hardware PMU access due to security reasons. You can overcome them by setting perf_event_paranoid to 0 or -1:
You may also need to disable THP and pin the calling thread to a core if thereās too much going on in your machine.
Now we have all the pieces required to start monitoring hardware events. Throughout this post weād work with the following events:
| Event | Config | Description |
|---|---|---|
| MEM_INST_RETIRED.STLB_MISS_LOADS | 0x11D0 | Retired load instructions that start a miss in the STLB. |
| MEM_INST_RETIRED.STLB_MISS_STORES | 0x12D0 | Retired store instructions that start a miss in the STLB. |
| DTLB_LOAD_MISSES.STLB_HIT | 0x2008 | Loads that miss the data TLB and hit the unified STLB. |
Itās note hard to observe that the event configs are of the form 0x<Umask><EventSel>, where Umask and EventSel are coming straight from the āPROGRAMMING INFOā column of the corresponding event in the perfmon website (the āHā suffix is Intelās way of saying the number is given in hexadecimal). Not all event configs are derived this way, but itās enough for the simple ones weāre gonna use here.
TLB Hierarchy in Skylake-X
SKX (codename for Skylake-X) has two TLB levels: L1 and L2. Each SKX core gets a physically separate L1 data TLB (dTLB) and L1 instruction TLB (iTLB). The L2 TLB (also called Second Level TLB or STLB) is unified, i.e. both instruction and data PTEs go to the same STLB.
Both L1 and L2 TLBs are partitioned based on the page size. L1 dTLB has a total of 100 entries: 64 reserved for 4k pages, 32 for 2M or 4M pages, and 4 for 1G pages. The dTLB is 4-way set associative so each set can hold 4 page-table entries. The iTLB is also partitioned: has 128 entries for 4k pages, 16 entries for 2M or 4M pages, and none for 1G pages. The STLB has 1536 entries shared between 4k and 2M pages and an additional 16 entries for 1G huge pages. STLB is not inclusive of the L1 TLBs. That means at any given instance, a page-table entry may exist in one of the L1 TLBs, the STLB, or both.
For the purposes of this post, we donāt need to dig any further into the geometry of SKX TLBs. Itās time to run some experiments!
Does it Exist
The very first question that we should ask is whether the next-page prefetcher exists in SKX at all. NPPs seem like a good idea in general; given that Intel had the silicon budget to include one in Ivy Bridge, we expect the answer to be āYesā in SKX too.
To test this, weāll design a workload that walks a mapped range of 1000 4K pages sequentially and measure how many TLB misses we get. I cannot imagine a more favourable access pattern for the NPP to kick in if it truly exists. If the workload below doesnāt trigger the prefetcher, we can safely conclude that SKX doesnāt have one.
Not much going on here. We have a function that touches every byte in the mapped range starting at MAP_BASE. The seemingly useless zero helps ensure that loads from the mapped range execute serially.
Take a closer look at how weāre using zero in the loop. Loading the next byte from the mapped range at iteration i depends on the value of zero computed at iteration i-1. Computing zero at iteration i-1 in turn depends on computing dummy at iteration i-1. We have a cyclic loop-carried dependency chain here: the load in map_base[i + zero] feeds add in dummy += .... The result of that add then feeds the and in zero = zero & .... Result of the and feeds the next load at iteration i+1.
In layman terms, the loads at iteration i and iteration i+1 cannot execute together or out-of-order. This is intentional: alloweing out-of-order execution of the two loads could significantly perturb our results. Weāll see why in a moment.
The last line is a common trick to avoid the compiler throw away our computation; itās falsely advertising that the inline asm uses the value of dummy computed in the loop and forcing the compiler to materialize dummy into a register.
With g++ -O2, the loop compiles to:
Nice. A few instructions here and there but we got the loop compiled exactly how we wanted. Note that the dependency chain we just discussed translates exactly to assembly too.
Running the workload gives the following count for the two events:
DTLB_LOAD_MISSES.STLB_HIT = 70
MEM_INST_RETIRED.STLB_MISS_LOADS = 1
Over a few runs DTLB_LOAD_MISSES.STLB_HIT fluctuates between the 50..75 band, but never exceeds 75. Thatās already interesting: we walked through 1000 pages in the loop but DTLB_LOAD_MISSES.STLB_HIT is nowhere near 1000.
DTLB_LOAD_MISSES.STLB_HIT = 70 means only 70 out of the 1000 PTE requests missed in dTLB and hit STLB. The obvious next question is what happened to rest of the 1000 - 70 = 930 fresh PTE requests that the loop might have initiated? There are two possible answers:
- They miss in the STLB too.
- They didnāt miss dTLB.
We can quickly rule out (1) because MEM_INST_RETIRED.STLB_MISS_LOADS = 1. So that leaves us with (2): about 930 new PTE requests hit in the dTLB when the demand arrived. But that must mean that SKX has a prefetcher thatās prefilling the dTLB with future PTEs. Yep! Itās the next-page prefetcher in action. Well, strictly speaking this could also be a non-NPP prefetcher that is allowed prefetch beyond page boundaries but as they say, if it quacks like a duck, itās the next-page prefetcher!
Subtle point that is easy to miss: the prefetcher is loading entries into th dTLB. This doesnāt automatically prove or disprove that itās also prefilling STLB. Perhaps a carefully designed experiment can unveil that secret, but thatās not my focus in this post. Weād also not worry about the iTLB for now.
Microarchitecture explorations typically require careful use of statistics to extract signal buried in noise. Luckily in this case the signal is so strong that we can get away with sloppiness. Alright, we have established that SKX has a next-page prefetcher that prefills the dTLB. On to the next question!
What Triggers the Next-Page Prefetcher
Something in the loop in touch_all_bytes must have triggered the next-page prefetch. The most obvious guess is a load from the previous page. Question is, which load? Is it just a single load from a special offset? A set of loads? There are so many questions that could be asked hereā¦we need an experiment that narrows down the space of possibilities.
We can imagine a workload that touches only the left half of each page (bytes in the range page[0..2047], inclusive) and count the TLB misses. If we still see TLB miss numbers like in our first experiment, thatād mean accesses from the left half of the page triggers the prefetch. If we instead see TLB misses that add up to 1000 (or more), we can repeat the same experiment but this time touching the right half of the page (bytes in the range page[2048..4095], inclusive).
A generic workload that accepts an offset and a slice_length can handle both cases:
When touch_page_slice is called with offset = 0, slice_length = 2048, it walks left half of each of the 1000 mapped pages. Walking the right half is just as simple, just call touch_page_slice with offset = 2048 and slice_length = 2048.
Results from walking the left half:
Left half: DTLB_LOAD_MISSES.STLB_HIT = 33 `MEM_INST_RE
Comments
No comments yet. Start the discussion.