19
Paging: Faster Translations (TLBs)
Using paging as the core mechanism to support virtual memory can lead
to high performance overheads. By chopping the address space into small,
fixed-sized units (i.e., pages), paging requires a large amount of mapping
information. Because that mapping information is generally stored in
physical memory, paging logically requires an extra memory lookup for
each virtual address generated by the program. Going to memory for
translation information before every instruction fetch or explicit load or
store is prohibitively slow. And thus our problem:
THE CRUX:
HOW TO SPEED UP ADDRESS TRANSLATION
How can we speed up address translation, and generally avoid the
extra memory reference that paging seems to require? What hardware
support is required? What OS involvement is needed?
When we want to make things fast, the OS usually needs some help.
And help often comes from the OS’s old friend: the hardware. To speed
address translation, we are going to add what is called (for historical rea-
sons [CP78]) a translation-lookaside buffer, or TLB [CG68, C95]. A TLB
is part of the chip’s memory-management unit (MMU), and is simply a
hardware cache of popular virtual-to-physical address translations; thus,
a better name would be an address-translation cache. Upon each virtual
memory reference, the hardware first checks the TLB to see if the desired
translation is held therein; if so, the translation is performed (quickly)
without having to consult the page table (which has all translations). Be-
cause of their tremendous performance impact, TLBs in a real sense make
virtual memory possible [C95].
1
2 PAGING: FASTER TRANSLATIONS (TLBS)
1 VPN = (VirtualAddress & VPN_MASK) >> SHIFT
2 (Success, TlbEntry) = TLB_Lookup(VPN)
3 if (Success == True) // TLB Hit
4 if (CanAccess(TlbEntry.ProtectBits) == True)
5 Offset = VirtualAddress & OFFSET_MASK
6 PhysAddr = (TlbEntry.PFN << SHIFT) | Offset 7 Register = AccessMemory(PhysAddr) 8 else 9 RaiseException(PROTECTION_FAULT) 10 else // TLB Miss 11 PTEAddr = PTBR + (VPN * sizeof(PTE)) 12 PTE = AccessMemory(PTEAddr) 13 if (PTE.Valid == False) 14 RaiseException(SEGMENTATION_FAULT) 15 else if (CanAccess(PTE.ProtectBits) == False) 16 RaiseException(PROTECTION_FAULT) 17 else 18 TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits) 19 RetryInstruction() Figure 19.1: TLB Control Flow Algorithm 19.1 TLB Basic Algorithm Figure 19.1 shows a rough sketch of how hardware might handle a virtual address translation, assuming a simple linear page table (i.e., the page table is an array) and a hardware-managed TLB (i.e., the hardware handles much of the responsibility of page table accesses; we’ll explain more about this below). The algorithm the hardware follows works like this: first, extract the virtual page number (VPN) from the virtual address (Line 1 in Figure 19.1), and check if the TLB holds the translation for this VPN (Line 2). If it does, we have a TLB hit, which means the TLB holds the translation. Success! We can now extract the page frame number (PFN) from the relevant TLB entry, concatenate that onto the offset from the original virtual address, and form the desired physical address (PA), and access memory (Lines 5–7), assuming protection checks do not fail (Line 4). If the CPU does not find the translation in the TLB (a TLB miss), we have some more work to do. In this example, the hardware accesses the page table to find the translation (Lines 11–12), and, assuming that the virtual memory reference generated by the process is valid and accessi- ble (Lines 13, 15), updates the TLB with the translation (Line 18). These set of actions are costly, primarily because of the extra memory reference needed to access the page table (Line 12). Finally, once the TLB is up- dated, the hardware retries the instruction; this time, the translation is found in the TLB, and the memory reference is processed quickly. OPERATING SYSTEMS [VERSION 1.01] WWW.OSTEP.ORG PAGING: FASTER TRANSLATIONS (TLBS) 3 The TLB, like all caches, is built on the premise that in the common case, translations are found in the cache (i.e., are hits). If so, little over- head is added, as the TLB is found near the processing core and is de- signed to be quite fast. When a miss occurs, the high cost of paging is incurred; the page table must be accessed to find the translation, and an extra memory reference (or more, with more complex page tables) results. If this happens often, the program will likely run noticeably more slowly; memory accesses, relative to most CPU instructions, are quite costly, and TLB misses lead to more memory accesses. Thus, it is our hope to avoid TLB misses as much as we can. 19.2 Example: Accessing An Array To make clear the operation of a TLB, let’s examine a simple virtual address trace and see how a TLB can improve its performance. In this example, let’s assume we have an array of 10 4-byte integers in memory, starting at virtual address 100. Assume further that we have a small 8-bit virtual address space, with 16-byte pages; thus, a virtual address breaks down into a 4-bit VPN (there are 16 virtual pages) and a 4-bit offset (there are 16 bytes on each of those pages). Figure 19.2 (page 4) shows the array laid out on the 16 16-byte pages of the system. As you can see, the array’s first entry (a[0]) begins on (VPN=06, offset=04); only three 4-byte integers fit onto that page. The array continues onto the next page (VPN=07), where the next four entries (a[3] ... a[6]) are found. Finally, the last three entries of the 10-entry array (a[7] ... a[9]) are located on the next page of the address space (VPN=08). Now let’s consider a simple loop that accesses each array element, something that would look like this in C: int sum = 0; for (i = 0; i < 10; i++) { sum += a[i]; } For the sake of simplicity, we will pretend that the only memory ac- cesses the loop generates are to the array (ignoring the variables i and sum, as well as the instructions themselves). When the first array element (a[0]) is accessed, the CPU will see a load to virtual address 100. The hardware extracts the VPN from this (VPN=06), and uses that to check the TLB for a valid translation. Assuming this is the first time the pro- gram accesses the array, the result will be a TLB miss. The next access is to a[1], and there is some good news here: a TLB hit! Because the second element of the array is packed next to the first, it lives on the same page; because we’ve already accessed this page when accessing the first element of the array, the translation is already loaded c© 2008–19, ARPACI-DUSSEAU THREE EASY PIECES 4 PAGING: FASTER TRANSLATIONS (TLBS) VPN = 15 VPN = 14 VPN = 13 VPN = 12 VPN = 11 VPN = 10 VPN = 09 VPN = 08 VPN = 07 VPN = 06 VPN = 05 VPN = 04 VPN = 03 VPN = 02 VPN = 01 VPN = 00 00 04 08 12 16 Offset a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] Figure 19.2: Example: An Array In A Tiny Address Space into the TLB. And hence the reason for our success. Access to a[2] en- counters similar success (another hit), because it too lives on the same page as a[0] and a[1]. Unfortunately, when the program accesses a[3], we encounter an- other TLB miss. However, once again, the next entries (a[4] ... a[6]) will hit in the TLB, as they all reside on the same page in memory. Finally, access to a[7] causes one last TLB miss. The hardware once again consults the page table to figure out the location of this virtual page in physical memory, and updates the TLB accordingly. The final two ac- cesses (a[8] and a[9]) receive the benefits of this TLB update; when the hardware looks in the TLB for their translations, two more hits result. Let us summarize TLB activity during our ten accesses to the array: miss, hit, hit, miss, hit, hit, hit, miss, hit, hit. Thus, our TLB hit rate, which is the number of hits divided by the total number of accesses, is 70%. Although this is not too high (indeed, we desire hit rates that ap- proach 100%), it is non-zero, which may be a surprise. Even though this is the first time the program accesses the array, the TLB improves per- formance due to spatial locality. The elements of the array are packed tightly into pages (i.e., they are close to one another in space), and thus only the first access to an element on a page yields a TLB miss. Also note the role that page size plays in this example. If the page size OPERATING SYSTEMS [VERSION 1.01] WWW.OSTEP.ORG PAGING: FASTER TRANSLATIONS (TLBS) 5 TIP: USE CACHING WHEN POSSIBLE Caching is one of the most fundamental performance techniques in com- puter systems, one that is used again and again to make the “common- case fast” [HP06]. The idea behind hardware caches is to take advantage of locality in instruction and data references. There are usually two types of locality: temporal locality and spatial locality. With temporal locality, the idea is that an instruction or data item that has been recently accessed will likely be re-accessed soon in the future. Think of loop variables or in- structions in a loop; they are accessed repeatedly over time. With spatial locality, the idea is that if a program accesses memory at address x, it will likely soon access memory near x. Imagine here streaming through an array of some kind, accessing one element and then the next. Of course, these properties depend on the exact nature of the program, and thus are not hard-and-fast laws but more like rules of thumb. Hardware caches, whether for instructions, data, or address translations (as in our TLB) take advantage of locality by keeping copies of memory in small, fast on-chip memory. Instead of having to go to a (slow) memory to satisfy a request, the processor can first check if a nearby copy exists in a cache; if it does, the processor can access it quickly (i.e., in a few CPU cycles) and avoid spending the costly time it takes to access memory (many nanoseconds). You might be wondering: if caches (like the TLB) are so great, why don’t we just make bigger caches and keep all of our data in them? Unfor- tunately, this is where we run into more fundamental laws like those of physics. If you want a fast cache, it has to be small, as issues like the speed-of-light and other physical constraints become relevant. Any large cache by definition is slow, and thus defeats the purpose. Thus, we are stuck with small, fast caches; the question that remains is how to best use them to improve performance. had simply been twice as big (32 bytes, not 16), the array access would suffer even fewer misses. As typical page sizes are more like 4KB, these types of dense, array-based accesses achieve excellent TLB performance, encountering only a single miss per page of accesses. One last point about TLB performance: if the program, soon after this loop completes, accesses the array again, we’d likely see an even bet- ter result, assuming that we have a big enough TLB to cache the needed translations: hit, hit, hit, hit, hit, hit, hit, hit, hit, hit. In this case, the TLB hit rate would be high because of temporal locality, i.e., the quick re-referencing of memory items in time. Like any cache, TLBs rely upon both spatial and temporal locality for success, which are program proper- ties. If the program of interest exhibits such locality (and many programs do), the TLB hit rate will likely be high. c© 2008–19, ARPACI-DUSSEAU THREE EASY PIECES 6 PAGING: FASTER TRANSLATIONS (TLBS) 1 VPN = (VirtualAddress & VPN_MASK) >> SHIFT
2 (Success, TlbEntry) = TLB_Lookup(VPN)
3 if (Success == True) // TLB Hit
4 if (CanAccess(TlbEntry.ProtectBits) == True)
5 Offset = VirtualAddress & OFFSET_MASK
6 PhysAddr = (TlbEntry.PFN << SHIFT) | Offset 7 Register = AccessMemory(PhysAddr) 8 else 9 RaiseException(PROTECTION_FAULT) 10 else // TLB Miss 11 RaiseException(TLB_MISS) Figure 19.3: TLB Control Flow Algorithm (OS Handled) 19.3 Who Handles The TLB Miss? One question that we must answer: who handles a TLB miss? Two an- swers are possible: the hardware, or the software (OS). In the olden days, the hardware had complex instruction sets (sometimes called CISC, for complex-instruction set computers) and the people who built the hard- ware didn’t much trust those sneaky OS people. Thus, the hardware would handle the TLB miss entirely. To do this, the hardware has to know exactly where the page tables are located in memory (via a page- table base register, used in Line 11 in Figure 19.1), as well as their exact format; on a miss, the hardware would “walk” the page table, find the cor- rect page-table entry and extract the desired translation, update the TLB with the translation, and retry the instruction. An example of an “older” architecture that has hardware-managed TLBs is the Intel x86 architec- ture, which uses a fixed multi-level page table (see the next chapter for details); the current page table is pointed to by the CR3 register [I09]. More modern architectures (e.g., MIPS R10k [H93] or Sun’s SPARC v9 [WG00], both RISC or reduced-instruction set computers) have what is known as a software-managed TLB. On a TLB miss, the hardware sim- ply raises an exception (line 11 in Figure 19.3), which pauses the current instruction stream, raises the privilege level to kernel mode, and jumps to a trap handler. As you might guess, this trap handler is code within the OS that is written with the express purpose of handling TLB misses. When run, the code will lookup the translation in the page table, use spe- cial “privileged” instructions to update the TLB, and return from the trap; at this point, the hardware retries the instruction (resulting in a TLB hit). Let’s discuss a couple of important details. First, the return-from-trap instruction needs to be a little different than the return-from-trap we saw before when servicing a system call. In the latter case, the return-from- trap should resume execution at the instruction after the trap into the OS, just as a return from a procedure call returns to the instruction imme- diately following the call into the procedure. In the former case, when returning from a TLB miss-handling trap, the hardware must resume ex- ecution at the instruction that caused the trap; this retry thus lets the in- OPERATING SYSTEMS [VERSION 1.01] WWW.OSTEP.ORG PAGING: FASTER TRANSLATIONS (TLBS) 7 ASIDE: RISC VS. CISC In the 1980’s, a great battle took place in the computer architecture com- munity. On one side was the CISC camp, which stood for Complex Instruction Set Computing; on the other side was RISC, for Reduced Instruction Set Computing [PS81]. The RISC side was spear-headed by David Patterson at Berkeley and John Hennessy at Stanford (who are also co-authors of some famous books [HP06]), although later John Cocke was recognized with a Turing award for his earliest work on RISC [CM00]. CISC instruction sets tend to have a lot of instructions in them, and each instruction is relatively powerful. For example, you might see a string copy, which takes two pointers and a length and copies bytes from source to destination. The idea behind CISC was that instructions should be high-level primitives, to make the assembly language itself easier to use, and to make code more compact. RISC instruction sets are exactly the opposite. A key observation behind RISC is that instruction sets are really compiler targets, and all compil- ers really want are a few simple primitives that they can use to gener- ate high-performance code. Thus, RISC proponents argued, let’s rip out as much from the hardware as possible (especially the microcode), and make what’s left simple, uniform, and fast. In the early days, RISC chips made a huge impact, as they were noticeably faster [BC91]; many papers were written; a few companies were formed (e.g., MIPS and Sun). However, as time progressed, CISC manufacturers such as Intel incorporated many RISC techniques into the core of their processors, for example by adding early pipeline stages that transformed complex instructions into micro-instructions which could then be pro- cessed in a RISC-like manner. These innovations, plus a growing number of transistors on each chip, allowed CISC to remain competitive. The end result is that the debate died down, and today both types of processors can be made to run fast. struction run again, this time resulting in a TLB hit. Thus, depending on how a trap or exception was caused, the hardware must save a different PC when trapping into the OS, in order to resume properly when the time to do so arrives. Second, when running the TLB miss-handling code, the OS needs to be extra careful not to cause an infinite chain of TLB misses to occur. Many solutions exist; for example, you could keep TLB miss handlers in physi- cal memory (where they are unmapped and not subject to address trans- lation), or reserve some entries in the TLB for permanently-valid transla- tions and use some of those permanent translation slots for the handler code itself; these wired translations always hit in the TLB. The primary advantage of the software-managed approach is flexibil- ity: the OS can use any data structure it wants to implement the page c© 2008–19, ARPACI-DUSSEAU THREE EASY PIECES 8 PAGING: FASTER TRANSLATIONS (TLBS) ASIDE: TLB VALID BIT 6= PAGE TABLE VALID BIT A common mistake is to confuse the valid bits found in a TLB with those found in a page table. In a page table, when a page-table entry (PTE) is marked invalid, it means that the page has not been allocated by the process, and should not be accessed by a correctly-working program. The usual response when an invalid page is accessed is to trap to the OS, which will respond by killing the process. A TLB valid bit, in contrast, simply refers to whether a TLB entry has a valid translation within it. When a system boots, for example, a common initial state for each TLB entry is to be set to invalid, because no address translations are yet cached there. Once virtual memory is enabled, and once programs start running and accessing their virtual address spaces, the TLB is slowly populated, and thus valid entries soon fill the TLB. The TLB valid bit is quite useful when performing a context switch too, as we’ll discuss further below. By setting all TLB entries to invalid, the system can ensure that the about-to-be-run process does not accidentally use a virtual-to-physical translation from a previous process. table, without necessitating hardware change. Another advantage is sim- plicity, as seen in the TLB control flow (line 11 in Figure 19.3, in contrast to lines 11–19 in Figure 19.1). The hardware doesn’t do much on a miss: just raise an exception and let the OS TLB miss handler do the rest. 19.4 TLB Contents: What’s In There? Let’s look at the contents of the hardware TLB in more detail. A typical TLB might have 32, 64, or 128 entries and be what is called fully associa- tive. Basically, this just means that any given translation can be anywhere in the TLB, and that the hardware will search the entire TLB in parallel to find the desired translation. A TLB entry might look like this: VPN PFN other bits Note that both the VPN and PFN are present in each entry, as a trans- lation could end up in any of these locations (in hardware terms, the TLB is known as a fully-associative cache). The hardware searches the entries in parallel to see if there is a match. More interesting are the “other bits”. For example, the TLB commonly has a valid bit, which says whether the entry has a valid translation or not. Also common are protection bits, which determine how a page can be accessed (as in the page table). For example, code pages might be marked read and execute, whereas heap pages might be marked read and write. There may also be a few other fields, including an address-space identifier, a dirty bit, and so forth; see below for more information. OPERATING SYSTEMS [VERSION 1.01] WWW.OSTEP.ORG PAGING: FASTER TRANSLATIONS (TLBS) 9 19.5 TLB Issue: Context Switches With TLBs, some new issues arise when switching between processes (and hence address spaces). Specifically, the TLB contains virtual-to-physical translations that are only valid for the currently running process; these translations are not meaningful for other processes. As a result, when switching from one process to another, the hardware or OS (or both) must be careful to ensure that the about-to-be-run process does not accidentally use translations from some previously run process. To understand this situation better, let’s look at an example. When one process (P1) is running, it assumes the TLB might be caching translations that are valid for it, i.e., that come from P1’s page table. Assume, for this example, that the 10th virtual page of P1 is mapped to physical frame 100. In this example, assume another process (P2) exists, and the OS soon might decide to perform a context switch and run it. Assume here that the 10th virtual page of P2 is mapped to physical frame 170. If entries for both processes were in the TLB, the contents of the TLB would be: VPN PFN valid prot 10 100 1 rwx — — 0 — 10 170 1 rwx — — 0 — In the TLB above, we clearly have a problem: VPN 10 translates to either PFN 100 (P1) or PFN 170 (P2), but the hardware can’t distinguish which entry is meant for which process. Thus, we need to do some more work in order for the TLB to correctly and efficiently support virtualiza- tion across multiple processes. And thus, a crux: THE CRUX: HOW TO MANAGE TLB CONTENTS ON A CONTEXT SWITCH When context-switching between processes, the translations in the TLB for the last process are not meaningful to the about-to-be-run process. What should the hardware or OS do in order to solve this problem? There are a number of possible solutions to this problem. One ap- proach is to simply flush the TLB on context switches, thus emptying it before running the next process. On a software-based system, this can be accomplished with an explicit (and privileged) hardware instruc- tion; with a hardware-managed TLB, the flush could be enacted when the page-table base register is changed (note the OS must change the PTBR on a context switch anyhow). In either case, the flush operation simply sets all valid bits to 0, essentially clearing the contents of the TLB. By flushing the TLB on each context switch, we now have a working solution, as a process will never accidentally encounter the wrong trans- c© 2008–19, ARPACI-DUSSEAU THREE EASY PIECES 10 PAGING: FASTER TRANSLATIONS (TLBS) lations in the TLB. However, there is a cost: each time a process runs, it must incur TLB misses as it touches its data and code pages. If the OS switches between processes frequently, this cost may be high. To reduce this overhead, some systems add hardware support to en- able sharing of the TLB across context switches. In particular, some hard- ware systems provide an address space identifier (ASID) field in the TLB. You can think of the ASID as a process identifier (PID), but usu- ally it has fewer bits (e.g., 8 bits for the ASID versus 32 bits for a PID). If we take our example TLB from above and add ASIDs, it is clear processes can readily share the TLB: only the ASID field is needed to dif- ferentiate otherwise identical translations. Here is a depiction of a TLB with the added ASID field: VPN PFN valid prot ASID 10 100 1 rwx 1 — — 0 — — 10 170 1 rwx 2 — — 0 — — Thus, with address-space identifiers, the TLB can hold translations from different processes at the same time without any confusion. Of course, the hardware also needs to know which process is currently run- ning in order to perform translations, and thus the OS must, on a context switch, set some privileged register to the ASID of the current process. As an aside, you may also have thought of another case where two entries of the TLB are remarkably similar. In this example, there are two entries for two different processes with two different VPNs that point to the same physical page: VPN PFN valid prot ASID 10 101 1 r-x 1 — — 0 — — 50 101 1 r-x 2 — — 0 — — This situation might arise, for example, when two processes share a page (a code page, for example). In the example above, Process 1 is shar- ing physical page 101 with Process 2; P1 maps this page into the 10th page of its address space, whereas P2 maps it to the 50th page of its ad- dress space. Sharing of code pages (in binaries, or shared libraries) is useful as it reduces the number of physical pages in use, thus reducing memory overheads. OPERATING SYSTEMS [VERSION 1.01] WWW.OSTEP.ORG PAGING: FASTER TRANSLATIONS (TLBS) 11 19.6 Issue: Replacement Policy As with any cache, and thus also with the TLB, one more issue that we must consider is cache replacement. Specifically, when we are installing a new entry in the TLB, we have to replace an old one, and thus the question: which one to replace? THE CRUX: HOW TO DESIGN TLB REPLACEMENT POLICY Which TLB entry should be replaced when we add a new TLB entry? The goal, of course, being to minimize the miss rate (or increase hit rate) and thus improve performance. We will study such policies in some detail when we tackle the problem of swapping pages to disk; here we’ll just highlight a few typical policies. One common approach is to evict the least-recently-used or LRU entry. LRU tries to take advantage of locality in the memory-reference stream, assuming it is likely that an entry that has not recently been used is a good candidate for eviction. Another typical approach is to use a random pol- icy, which evicts a TLB mapping at random. Such a policy is useful due to its simplicity and ability to avoid corner-case behaviors; for example, a “reasonable” policy such as LRU behaves quite unreasonably when a program loops over n + 1 pages with a TLB of size n; in this case, LRU misses upon every access, whereas random does much better. 19.7 A Real TLB Entry Finally, let’s briefly look at a real TLB. This example is from the MIPS R4000 [H93], a modern system that uses software-managed TLBs; a slightly simplified MIPS TLB entry can be seen in Figure 19.4. The MIPS R4000 supports a 32-bit address space with 4KB pages. Thus, we would expect a 20-bit VPN and 12-bit offset in our typical virtual ad- dress. However, as you can see in the TLB, there are only 19 bits for the VPN; as it turns out, user addresses will only come from half the address space (the rest reserved for the kernel) and hence only 19 bits of VPN are needed. The VPN translates to up to a 24-bit physical frame number (PFN), and hence can support systems with up to 64GB of (physical) main memory (224 4KB pages). There are a few other interesting bits in the MIPS TLB. We see a global bit (G), which is used for pages that are globally-shared among processes. Thus, if the global bit is set, the ASID is ignored. We also see the 8-bit ASID, which the OS can use to distinguish between address spaces (as 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 3 0 3 1 VPN G ASID PFN C D V Figure 19.4: A MIPS TLB Entry c© 2008–19, ARPACI-DUSSEAU THREE EASY PIECES 12 PAGING: FASTER TRANSLATIONS (TLBS) TIP: RAM ISN’T ALWAYS RAM (CULLER’S LAW) The term random-access memory, or RAM, implies that you can access any part of RAM just as quickly as another. While it is generally good to think of RAM in this way, because of hardware/OS features such as the TLB, accessing a particular page of memory may be costly, particularly if that page isn’t currently mapped by your TLB. Thus, it is always good to remember the implementation tip: RAM isn’t always RAM. Some- times randomly accessing your address space, particularly if the number of pages accessed exceeds the TLB coverage, can lead to severe perfor- mance penalties. Because one of our advisors, David Culler, used to al- ways point to the TLB as the source of many performance problems, we name this law in his honor: Culler’s Law. described above). One question for you: what should the OS do if there are more than 256 (28) processes running at a time? Finally, we see 3 Coherence (C) bits, which determine how a page is cached by the hardware (a bit beyond the scope of these notes); a dirty bit which is marked when the page has been written to (we’ll see the use of this later); a valid bit which tells the hardware if there is a valid translation present in the entry. There is also a page mask field (not shown), which supports multiple page sizes; we’ll see later why having larger pages might be useful. Finally, some of the 64 bits are unused (shaded gray in the diagram). MIPS TLBs usually have 32 or 64 of these entries, most of which are used by user processes as they run. However, a few are reserved for the OS. A wired register can be set by the OS to tell the hardware how many slots of the TLB to reserve for the OS; the OS uses these reserved map- pings for code and data that it wants to access during critical times, where a TLB miss would be problematic (e.g., in the TLB miss handler). Because the MIPS TLB is software managed, there needs to be instruc- tions to update the TLB. The MIPS provides four such instructions: TLBP, which probes the TLB to see if a particular translation is in there; TLBR, which reads the contents of a TLB entry into registers; TLBWI, which re- places a specific TLB entry; and TLBWR, which replaces a random TLB entry. The OS uses these instructions to manage the TLB’s contents. It is of course critical that these instructions are privileged; imagine what a user process could do if it could modify the contents of the TLB (hint: just about anything, including take over the machine, run its own malicious “OS”, or even make the Sun disappear). 19.8 Summary We have seen how hardware can help us make address translation faster. By providing a small, dedicated on-chip TLB as an address-translation cache, most memory references will hopefully be handled without having to access the page table in main memory. Thus, in the common case, OPERATING SYSTEMS [VERSION 1.01] WWW.OSTEP.ORG PAGING: FASTER TRANSLATIONS (TLBS) 13 the performance of the program will be almost as if memory isn’t being virtualized at all, an excellent achievement for an operating system, and certainly essential to the use of paging in modern systems. However, TLBs do not make the world rosy for every program that exists. In particular, if the number of pages a program accesses in a short period of time exceeds the number of pages that fit into the TLB, the pro- gram will generate a large number of TLB misses, and thus run quite a bit more slowly. We refer to this phenomenon as exceeding the TLB cov- erage, and it can be quite a problem for certain programs. One solution, as we’ll discuss in the next chapter, is to include support for larger page sizes; by mapping key data structures into regions of the program’s ad- dress space that are mapped by larger pages, the effective coverage of the TLB can be increased. Support for large pages is often exploited by pro- grams such as a database management system (a DBMS), which have certain data structures that are both large and randomly-accessed. One other TLB issue worth mentioning: TLB access can easily be- come a bottleneck in the CPU pipeline, in particular with what is called a physically-indexed cache. With such a cache, address translation has to take place before the cache is accessed, which can slow things down quite a bit. Because of this potential problem, people have looked into all sorts of clever ways to access caches with virtual addresses, thus avoiding the expensive step of translation in the case of a cache hit. Such a virtually- indexed cache solves some performance problems, but introduces new issues into hardware design as well. See Wiggins’s fine survey for more details [W03]. c© 2008–19, ARPACI-DUSSEAU THREE EASY PIECES 14 PAGING: FASTER TRANSLATIONS (TLBS) References [BC91] “Performance from Architecture: Comparing a RISC and a CISC with Similar Hard- ware Organization” by D. Bhandarkar and Douglas W. Clark. Communications of the ACM, September 1991. A great and fair comparison between RISC and CISC. The bottom line: on similar hardware, RISC was about a factor of three better in performance. [CM00] “The evolution of RISC technology at IBM” by John Cocke, V. Markstein. IBM Journal of Research and Development, 44:1/2. A summary of the ideas and work behind the IBM 801, which many consider the first true RISC microprocessor. [C95] “The Core of the Black Canyon Computer Corporation” by John Couleur. IEEE Annals of History of Computing, 17:4, 1995. In this fascinating historical note, Couleur talks about how he invented the TLB in 1964 while working for GE, and the fortuitous collaboration that thus ensued with the Project MAC folks at MIT. [CG68] “Shared-access Data Processing System” by John F. Couleur, Edward L. Glaser. Patent 3412382, November 1968. The patent that contains the idea for an associative memory to store address translations. The idea, according to Couleur, came in 1964. [CP78] “The architecture of the IBM System/370” by R.P. Case, A. Padegs. Communications of the ACM. 21:1, 73-96, January 1978. Perhaps the first paper to use the term translation lookaside buffer. The name arises from the historical name for a cache, which was a lookaside buffer as called by those developing the Atlas system at the University of Manchester; a cache of address translations thus became a translation lookaside buffer. Even though the term lookaside buffer fell out of favor, TLB seems to have stuck, for whatever reason. [H93] “MIPS R4000 Microprocessor User’s Manual”. by Joe Heinrich. Prentice-Hall, June 1993. Available: http://cag.csail.mit.edu/raw/ . documents/R4400 Uman book Ed2.pdf A manual, one that is surprisingly readable. Or is it? [HP06] “Computer Architecture: A Quantitative Approach” by John Hennessy and David Pat- terson. Morgan-Kaufmann, 2006. A great book about computer architecture. We have a particular attachment to the classic first edition. [I09] “Intel 64 and IA-32 Architectures Software Developer’s Manuals” by Intel, 2009. Avail- able: http://www.intel.com/products/processor/manuals. In particular, pay attention to “Vol- ume 3A: System Programming Guide” Part 1 and “Volume 3B: System Programming Guide Part 2”. [PS81] “RISC-I: A Reduced Instruction Set VLSI Computer” by D.A. Patterson and C.H. Se- quin. ISCA ’81, Minneapolis, May 1981. The paper that introduced the term RISC, and started the avalanche of research into simplifying computer chips for performance. [SB92] “CPU Performance Evaluation and Execution Time Prediction Using Narrow Spectrum Benchmarking” by Rafael H. Saavedra-Barrera. EECS Department, University of California, Berkeley. Technical Report No. UCB/CSD-92-684, February 1992.. A great dissertation about how to predict execution time of applications by breaking them down into constituent pieces and knowing the cost of each piece. Probably the most interesting part that comes out of this work is the tool to measure details of the cache hierarchy (described in Chapter 5). Make sure to check out the wonderful diagrams therein. [W03] “A Survey on the Interaction Between Caching, Translation and Protection” by Adam Wiggins. University of New South Wales TR UNSW-CSE-TR-0321, August, 2003. An excellent survey of how TLBs interact with other parts of the CPU pipeline, namely hardware caches. [WG00] “The SPARC Architecture Manual: Version 9” by David L. Weaver and Tom Germond. SPARC International, San Jose, California, September 2000. Available: www.sparc.org/ standards/SPARCV9.pdf. Another manual. I bet you were hoping for a more fun citation to end this chapter. OPERATING SYSTEMS [VERSION 1.01] WWW.OSTEP.ORG PAGING: FASTER TRANSLATIONS (TLBS) 15 Homework (Measurement) In this homework, you are to measure the size and cost of accessing a TLB. The idea is based on work by Saavedra-Barrera [SB92], who de- veloped a simple but beautiful method to measure numerous aspects of cache hierarchies, all with a very simple user-level program. Read his work for more details. The basic idea is to access some number of pages within a large data structure (e.g., an array) and to time those accesses. For example, let’s say the TLB size of a machine happens to be 4 (which would be very small, but useful for the purposes of this discussion). If you write a program that touches 4 or fewer pages, each access should be a TLB hit, and thus relatively fast. However, once you touch 5 pages or more, repeatedly in a loop, each access will suddenly jump in cost, to that of a TLB miss. The basic code to loop through an array once should look like this: int jump = PAGESIZE / sizeof(int); for (i = 0; i < NUMPAGES * jump; i += jump) a[i] += 1; In this loop, one integer per page of the array a is updated, up to the number of pages specified by NUMPAGES. By timing such a loop repeat- edly (say, a few hundred million times in another loop around this one, or however many loops are needed to run for a few seconds), you can time how long each access takes (on average). By looking for jumps in cost as NUMPAGES increases, you can roughly determine how big the first-level TLB is, determine whether a second-level TLB exists (and how big it is if it does), and in general get a good sense of how TLB hits and misses can affect performance. 1 4 16 64 256 1024 0 20 40 60 80 TLB Size Measurement Number Of Pages T im e P e r A c c e s s ( n s ) Figure 19.5: Discovering TLB Sizes and Miss Costs c© 2008–19, ARPACI-DUSSEAU THREE EASY PIECES 16 PAGING: FASTER TRANSLATIONS (TLBS) Figure 19.5 (page 15) shows the average time per access as the number of pages accessed in the loop is increased. As you can see in the graph, when just a few pages are accessed (8 or fewer), the average access time is roughly 5 nanoseconds. When 16 or more pages are accessed, there is a sudden jump to about 20 nanoseconds per access. A final jump in cost occurs at around 1024 pages, at which point each access takes around 70 nanoseconds. From this data, we can conclude that there is a two-level TLB hierarchy; the first is quite small (probably holding between 8 and 16 entries); the second is larger but slower (holding roughly 512 entries). The overall difference between hits in the first-level TLB and misses is quite large, roughly a factor of fourteen. TLB performance matters! Questions 1. For timing, you’ll need to use a timer (e.g., gettimeofday()). How precise is such a timer? How long does an operation have to take in order for you to time it precisely? (this will help deter- mine how many times, in a loop, you’ll have to repeat a page access in order to time it successfully) 2. Write the program, called tlb.c, that can roughly measure the cost of accessing each page. Inputs to the program should be: the num- ber of pages to touch and the number of trials. 3. Now write a script in your favorite scripting language (bash?) to run this program, while varying the number of pages accessed from 1 up to a few thousand, perhaps incrementing by a factor of two per iteration. Run the script on different machines and gather some data. How many trials are needed to get reliable measurements? 4. Next, graph the results, making a graph that looks similar to the one above. Use a good tool like ploticus or even zplot. Visual- ization usually makes the data much easier to digest; why do you think that is? 5. One thing to watch out for is compiler optimization. Compilers do all sorts of clever things, including removing loops which incre- ment values that no other part of the program subsequently uses. How can you ensure the compiler does not remove the main loop above from your TLB size estimator? 6. Another thing to watch out for is the fact that most systems today ship with multiple CPUs, and each CPU, of course, has its own TLB hierarchy. To really get good measurements, you have to run your code on just one CPU, instead of letting the scheduler bounce it from one CPU to the next. How can you do that? (hint: look up “pinning a thread” on Google for some clues) What will happen if you don’t do this, and the code moves from one CPU to the other? 7. Another issue that might arise relates to initialization. If you don’t initialize the array a above before accessing it, the first time you access it will be very expensive, due to initial access costs such as demand zeroing. Will this affect your code and its timing? What can you do to counterbalance these potential costs? OPERATING SYSTEMS [VERSION 1.01] WWW.OSTEP.ORG Paging: Faster Translations (TLBs) TLB Basic Algorithm Example: Accessing An Array Who Handles The TLB Miss? TLB Contents: What's In There? TLB Issue: Context Switches Issue: Replacement Policy A Real TLB Entry Summary References Homework (Measurement)