A Real TLB Entry

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 address. 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 ($2^{24}$ 4KB pages).

Other bits

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 described above). One question for you: what should the OS do if there are more than 256 ($2^8$) 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 mappings 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).

Instructions for updating TLB

Because the MIPS TLB is software managed, there needs to be instructions 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 replaces 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 taking over the machine, running its own malicious “OS”, or even making the Sun disappear).

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. Sometimes randomly accessing your address space, particularly if the number of pages accessed exceeds the TLB coverage, can lead to severe performance penalties. Because one of our advisors, David Culler, used to always point to the TLB as the source of many performance problems, we name this law in his honor: Culler’s Law.