Electrical computers and digital processing systems: memory – Address formation – Hashing
Reexamination Certificate
2000-11-01
2002-08-06
Hudspeth, David (Department: 2651)
Electrical computers and digital processing systems: memory
Address formation
Hashing
C711S205000, C711S206000
Reexamination Certificate
active
06430670
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to an apparatus and method for efficiently translating virtual addresses utilizing either single address space or multiple address space models in a virtual memory management system. In particular, a virtual hash page table (VHPT), an extension of the translation lookaside buffer (TLB) hierarchy, is designed to enhance virtual address translation performance. In addition, the VHPT is also designed to be efficiently utilized with either multiple address space (linear page table per address space) or single address space (hashed page table) methods.
2. Description of Related Art
Virtual addresses must be mapped (translated) into physical addresses before they can be read or written. Due to the high frequency of such mappings, their size and performance is critical to the performance of the system as a whole. There are two basic types of mapping methods, the single address space (typically associated with a hashed page table), and multiple address space models (typically associated with page tables).
Operating systems create and maintain these mappings in data structures that are specific to the operating system. Hardware must have mappings organized in ways it understands. One such hardware structure that must understand the mapping structure is a Translation Lookaside Buffer (TLB), which is typically used to cache a small number of recently used translations where the central processing unit (CPU) can quickly access and apply them. The work in loading the cache with proper translations is split between the hardware and software. The balance of this split is highly dependent on a number of criteria, including the data structures used by the hardware and software to represent these mappings outside the TLB. The criteria is hardware architecture and implementation specific. The range varies between full hardware control over TLB insertion to full software control over TLB insertion.
Multiple-address-space based operating systems tend to use forward mapped page tables to store translations, and need a small amount of information per mapping. This can be made even more efficient if the page tables are allocated contiguously in virtual space, allowing a single linear lookup to find a translation. Windows NT is an example of such an operation system.
Single-address-space based operating systems need more information per mapping (e.g. protection domain information), and make more efficient use of a hashed page table. HP-UX, which is manufactured and commercially available from Hewlett Packard Company, USA, is an example of such an operating system.
Until now, processor architectures have lacked the ability to efficiently utilize both single-address and multiple-address space references for translation from virtual addresses to physical addresses, and match the operating system native format. Other processor architectures could either manage a virtual linear table, or a physical hash table, or a physical forward mapped page tables mappings. The present invention is the first time that support of translations, both single-address and multiple-address spaced models, from virtual addresses to physical addresses has been provided in virtual space.
SUMMARY OF THE INVENTION
Certain objects, advantages and novel features of the invention will be set forth in part in the description that follows and in part will become apparent to those skilled in the art upon examination of the following or may be learned with the practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentality's and combinations particularly pointed out in the appended claims.
To achieve the advantages and novel features, the present invention is generally directed to a configurable virtual hash page table (VHPT). This data structure and mechanism are used to represent and access the mappings between virtual addresses and physical addresses. The data structure is accessed through virtual address references. Both hardware and software can use VHPT to lookup mappings, however only software can write to the VHPT.
One embodiment of the VHPT apparatus and method for utilizing the VHPT, is the single architectural feature that stores virtual to physical address mappings, and efficiently supports two different methods of virtual address mapping operating systems. This is permissible, since the VHPT is configurable to allow either linear access or hashed access. This invention increases the number of important operating systems that can directly share their method of managing virtual to physical mappings with the hardware. Without it, more operating systems would have to maintain two data structures: one for the operating system and one for the hardware. This costs engineering time, as well as end user time and memory.
The form of use taken by the VHPT, either a virtual linear table or as a virtual hash table, is determined by the Page Table Address (PTA) Control Register. Fields in this register determine the size of the entries, either 8-byte or 32-byte-entries in the VHPT, associated with whether or not the VHPT is linear or hashed. A VHPT using 8-byte entries is referred to as a short format VHPT, while one using 32-byte entries is referred to as a long format VHPT. The short format is typically used for a virtual linear page table, while the long format is typically used for a hashed page table.
An alternate embodiment provides an apparatus and method for implementing a hardware VHPT walker that can, without software intervention, resolve a TLB-miss by looking up the mapping in the VHPT.
In another alternate embodiment, nested data TLB misses are supported, because the VHPT is virtual, and attempts to resolve virtual to physical mappings can result in nested requests for other virtual to physical mappings. Hence, the architecture provides support for efficiently and simply managing nested TLB misses.
In another alternate embodiment, hardware provides instructions for software to access and utilize the VHPT much like the hardware does.
REFERENCES:
patent: 4680700 (1987-07-01), Hester et al.
patent: 5392410 (1995-02-01), Lin
patent: 5526504 (1996-06-01), Hsu et al.
patent: 5713001 (1998-01-01), Eberhard et al.
patent: 5724538 (1998-03-01), Morris et al.
patent: 5751990 (1998-05-01), Krolak et al.
patent: 5809563 (1998-09-01), Yamada et al.
patent: 5835964 (1998-11-01), Draves et al.
patent: 5860144 (1999-01-01), Frank et al.
patent: 6012132 (2000-01-01), Yamada et al.
Bryg William R.
Burger Stephen G.
Hammond Gary N.
Hays James O.
Kessenich John M.
Hewlett-Packard Co.
Hudspeth David
Tzeng Fred F.
LandOfFree
Apparatus and method for a virtual hashed page table does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for a virtual hashed page table, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for a virtual hashed page table will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2948927