| Address translation is the process of translating a virtual address to a physical address. Before we begin the translation process, the virtual address is divided into a virtual page number (VPN) and an offset into that page. The VPN is then translated into a physical page number (PPN), and the offset is used as the offset into that physical page. In PA-RISC 1.1, all pages are a fixed 4 KB long. This means that the offset portion of a virtual address is the lower 12 bits, and the VPN is the upper 20 bits. With PA-RISC 2.0, we introduced the concept of variable-sized pages. This means that the physical pages can be from 4 KB to 64 MB. However, for the purposes of address translation, we assume a 4-KB page size. Thus, we still use the upper 20 bits as the VPN. Once the VPN is translated to a PPN, we can determine how big the actual page is and thus how many bits of the address are used as the offset into the page. Figure 1-8 illustrates this translation process. Figure 1-8. Translation of Virtual Address to Physical Address 
Address Translation Components There are several components that are used to translate a virtual address to a physical address. The first of these is the PDIR, a table that lists pages currently in memory. It includes the VPN and PPN of each page and flags indicating the status of the entry. PA-RISC systems also have a TLB. This is a hardware version of the PDIR. It is not large enough to hold all of the PDIR entries, but it is much faster to reference the TLB than it is to reference the PDIR. Recently and frequently used PDIR entries are kept in the TLB for fast access. In this way, the TLB functions like a cache for PDIR entries. The system also has one or two memory caches. Systems may have separate caches for instructions and data, or they may have a combined cache. While the cache isn't strictly used for address translation, it is part of the process of finding the required data given a virtual address. When the system wants to access a particular virtual address, it first checks the TLB to see if the VPN is in there. If it is not, then it goes to the PDIR to see if the entry is there. If the entry is found in the PDIR, it is inserted into the TLB and the process starts over. If the entry is not found in the PDIR, a page fault is generated and the kernel must bring the page in from disk. Once the PPN has been obtained from the TLB, the cache is checked to see if the address is in the cache. If so, then the data is loaded from the cache. If not, the cache is loaded from memory and the process is restarted. The flowchart in Figure 1-9 illustrates this process. Figure 1-9. Address Translation through the TLB and Cache 
Translation Lookaside Buffer The TLB is a hardware unit that holds mappings from virtual pages to physical pages. Each TLB entry has the VPN and the corresponding PPN. In addition, the TLB entry is used for controlling access to pages. Each entry has a field for access rights and an access ID. In PA-RISC 2.0, with its support for variable-sized pages, the TLB also must have a field indicating the size of the physical page. Finally, each entry has a set of flags indicating the state of the entry. The actual layout and operation of the TLB is not significant. For an understanding of the HP-UX kernel, it is sufficient to know that the TLB is there and what it does. Access Control The TLB is also responsible for controlling access to pages. This is handled on two different levels. The first makes use of protection IDs and the access ID field in the TLB. This determines whether a particular process or context has access to a page. The second makes use of the instruction privilege level and the access rights field in the TLB. This determines whether the CPU's current privilege level is sufficient to access the page. Each TLB entry has an access ID field, which is 15 to 18 bits long on PA-RISC 1.1 and 15 to 31 bits long on PA-RISC 2.0. Each processor also has several protection IDs associated with it. These protection IDs are stored in control registers 8, 9, 12, and 13. Each protection ID is 32 bits long. On PA-RISC 1.1, with its 32-bit wide registers, four protection IDs are available. On PA-RISC 2.0, each register can hold two protection IDs for a total of eight. Once a match is found in the TLB for a particular VPN, the system then checks the access ID field in the TLB against each of the protection IDs. The access ID must match one of the protection IDs for the access to be allowed. The lowest bit of each protection ID is a write disable bit. If the operation is a write, then at least one of the matched protection IDs must have its low bit off, indicating the protection ID is valid for a write operation. Each TLB entry also has an access rights field, which indicates what privilege level is required for reading, writing, and executing addresses on the page. Recall that PA-RISC provides for four privilege levels, but only two of these are used by HP-UX. Privilege level 0 is used by the kernel, and privilege level 3 is used for user processes. The current privilege level is coded into the lower 2 bits of the instruction address. Because every instruction is 32 bits long, the address of an instruction must always be a multiple of four bytes. In other words, the lower 2 bits of the instruction address are never needed for addressing an instruction. Instead, these 2 bits encode the current privilege level. The access rights field in the TLB insures that only processes with the correct privilege level can access a page. An example of this is requiring privilege level 0 in order to access kernel private data. If a user process attempts to access kernel data directly, it will fail the access rights check. Both of the above access checks must pass in order for an access to be allowed. If either check fails, a Protection Fault as generated. TLB Miss Handlers Recall that the TLB is a limited resource and holds only a subset of the translations in the PDIR. If the system does not find the VPN it is looking for in the TLB, it generates a TLB miss. The information must then be retrieved from the PDIR and inserted into the TLB. Some PARISC 1.1 systems have a hardware TLB miss handler, which can search the PDIR in memory looking for a match. The entries in the PDIR are actually stored using a hashed chain structure, discussed in detail in Chapter 6. Because of this the hardware, TLB miss handler cannot see all entries in the PDIR. In addition, the TLB miss handler doesn't do access checking, so once the new entry is inserted into the TLB, it still needs to be have its access verified. There also is a software implementation of the TLB miss handler for systems without the hardware TLB miss handler and for cases where the hardware is unable to find the PDIR entry. Both the hardware and software miss handlers perform the same function: check the PDIR for a translation of a VPN. If the translation is found, it is inserted into the TLB. If the translation is not found, a Page Fault is generated so that the page can be brought in from disk. PA-RISC provides instructions for inserting entries into and deleting entries from the TLB. These instructions are used by the TLB miss handlers to manage the TLB. Cache Organization Once the address has been translated, the next step is to retrieve the data from that address. The cache stores data in blocks of data called cache lines. A cache line is the unit of data passed between main memory and cache. This size can vary between systems, but a typical implementation uses a 32-byte cache line. Each cache line has a cache tag that goes along with it and describes the data. This cache tag includes the physical page that the data came from as well as flags indicating the state of the data. The cache is accessed by a hash function using the VPN the same hash function used by the TLB. This means that given a VPN, the system can simultaneously check the TLB for the translation and access rights and also look for the data in the cache. Once the system has the PPN from the TLB and the PPN from the cache, it compares the two to see if the cached data is really from the correct page. Because the hash function can map multiple VPNs to a single entry, it is possible that the cache data found by the hash function will belong to a different physical page. If the PPNs from the cache and the TLB match, then the system can use the data from the cache. If the PPNs don't match, then we have a cache miss, and the system must retrieve the data from main memory. PA-RISC provides instructions for flushing cache to memory. The cache data will be written to main memory if the "dirty" flag is set in the cache tag, indicating that the cache data is newer than the memory data. There is also an instruction for purging the data cache, which simply flags the tag as invalid. Note that there are no instructions for inserting data into the cache. Cache insertion is handled automatically by the CPU when main memory is accessed. | 