Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
1999-03-22
2001-04-03
Robertson, David L. (Department: 2759)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
Reexamination Certificate
active
06212613
ABSTRACT:
BACKGROUND OF THE INVENTION
A typical computer provides a virtual addressing environment to the computer's operating system and other running programs. In general, the computer forms such an environment by generating and maintaining a set of address mappings that map virtual addresses ranges to physical addresses ranges (e.g., 4 kilobyte pages), and using the set of address mappings to translate virtual addresses into physical addresses. Virtual addresses are abstractions that the running programs perceive as actual addresses of the computer's memory. Physical addresses are the actual addresses of the computer's memory.
In general, the computer implements the virtual addressing environment using what are commonly known as “page tables” and a “translation lookaside buffer” (TLB). The page tables are large data structures in memory which store the entire set of address mappings. The TLB (or memory management unit) is a special cache having TLB entries which temporarily store often-used address mappings from the page tables. This cache is typically built into the computer's processor to provide the processor with quicker access to the address mappings than that provided by the page tables.
Typically, each TLB entry includes a valid bit. If the valid bit of a TLB entry is set (e.g., equals “1”), that TLB entry is usable by the computer for address translation. However, if the valid bit of a TLB entry is cleared (e.g., equals zero), that TLB entry is not usable for address translation.
In general, when a program accesses memory using a particular virtual address, the computer checks valid TLB entries for an address mapping that maps a virtual address range covering the particular virtual address. If the computer finds such a mapping in a valid TLB entry, the computer translates the particular virtual address into a physical address using that mapping, and then accesses the memory according to the translated physical address. However, if the computer does not find such a mapping in a valid TLB entry, a TLB exception is said to have occurred. The computer handles the TLB exception by transferring a copy of the address mapping that maps the virtual address range covering the particular address from the page tables to an entry of the TLB, and validates that entry. Then, in the manner described above, the computer translates the particular virtual address into the physical address using the address mapping from the valid TLB entry, and accesses the computer's memory according to the physical address.
When a running program gives up or “frees” a previously allocated memory space that it will no longer use, any valid TLB entries, which store address mappings for translating virtual addresses to that memory space, are said to become “stale”. A stale TLB entry is a valid TLB entry that stores an old address mapping that is no longer correct.
Typically, a computer does not invalidate stale TLB entries in response to a running program freeing memory space. Rather, the computer allows the stale TLB entries to remain in the TLB for a short time so that it can deal with the stale TLB entries in a more routine manner.
However, the computer must then respond immediately to some situations by operating on the TLB to avoid inadvertently using stale TLB entries to translate addresses. In particular, the computer must respond immediately to dynamic mapping operations (e.g., a memory allocation request by a running program) as will be made clearer by the following dynamic mapping example.
Suppose that a running program routinely reuses the same virtual address to access multiple memory spaces at different times. That is, the running program issues a first memory allocation request. The computer responds by allocating a memory space which the running program can access using a particular virtual address, and by further storing, in the page tables, an address mapping that maps a virtual address range covering the particular virtual address to the appropriate physical address range for the memory space. When the program attempts to access the memory space using the particular virtual address, a TLB exception occurs causing the computer to transfer the address mapping from the page tables to an entry of the TLB, validate that entry, and then use the valid TLB entry to translate the particular virtual address into the proper physical address to access the memory space.
When the running program subsequently frees the memory space, the computer allows the now stale TLB entry storing the address mapping to remain unchanged in the TLB. That is, the stale TLB entry remains valid.
Now, suppose that the running program issues a second memory allocation request which it plans to access using the same particular virtual address. The computer responds by allocating a new memory space to the running program, and by further storing, in the page tables, a new address mapping that maps the same particular virtual address range covering the particular virtual address to the appropriate physical address range for the new memory space. At this point, the computer must also invalidate the stale TLB entry which stores the original address mapping. Otherwise, when the running program attempts to access the new memory space using the same particular address, a TLB exception will not occur, and the computer will not transfer the new address mapping from the page tables into an entry of the TLB for address translation. Rather, the computer will translate the particular virtual address using the stale TLB entry and the running program will access the original (and now freed) memory space resulting in incorrect operation.
Computers use various approaches to prevent stale TLB entries from causing improper address translations when responding to dynamic memory allocation requests. In general, conventional approaches involve accessing each of the entries within the TLB in response to a dynamic mapping request. Two common approaches are described below.
In one approach (hereinafter called the “blanket approach”), the computer invalidates each entry within the TLB in response to a dynamic mapping request from a running program. Since the computer invalidates each TLB entry, there are no usable TLB entries remaining in the TLB for address translation. Accordingly, improper address translation using a stale and incorrect TLB entry is prevented. For a TLB having N TLB entries, the blanket approach requires N TLB accesses, one access to invalidate each TLB entry.
In another approach (hereinafter called the “check-first approach”), the computer checks each TLB entry in response to a dynamic mapping request. If a TLB entry stores an address mapping that maps a virtual address range covering the virtual address provided by the dynamic mapping request, the computer invalidates that TLB entry. Otherwise, the computer leaves that TLB entry unchanged. If there are no entries in the TLB that store an address mapping which maps the same virtual address range, there are at most N TLB accesses (each TLB entry being accessed to obtain its stored address mapping). On the other hand, when such a stale TLB entry exists, more than N TLB accesses will be required.
It may seem that the blanket approach is superior to the check-first approach because check-first approach may require more TLB accesses. However, in some situations, the check-first approach may provide superior performance than the blanket approach since the check-first approach invalidates TLB entries only when necessary. Accordingly, there may be a tendency for the check-first approach to generate less TLB exceptions resulting in less TLB accesses overall and better performance than the blanket approach.
SUMMARY OF THE INVENTION
In contrast to conventional approaches for reusing addresses which access each entry of a translation lookaside buffer (TLB) when responding to a dynamic mapping request, the invention is directed to techniques for reusing addresses that involve accessing at least one entry of the TLB, but less than all of the entries of the TLB when respondin
Chapin & Huang , L.L.C.
Cisco Technology Inc.
Huang David E.
Robertson David L.
LandOfFree
Methods and apparatus for reusing addresses in a computer does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for reusing addresses in a computer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for reusing addresses in a computer will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2479695