Apparatus and method for a virtual hashed page table

• US 6,216,214 B1
• Filed: 02/03/1998
• Issued: 04/10/2001
• Est. Priority Date: 11/12/1996
• Status: Expired due to Term

• Current Assignee: Institute For The Development of Emerging Architectures LLC
• Original Assignee: Institute For The Development of Emerging Architectures LLC
• Inventors: Yamada, Koichi, Hammond, Gary N., Ross, Jonathan K., Saxena, Sunil, Bryg, William R., Kessenich, John M., Hays, James O., Burger, Stephen G.
• Primary Examiner(s): Cadeca, John W.
• Assistant Examiner(s): TZENG, FRED
• Application Number:
  US09/018,326
• Time in Patent Office: 1,162 Days
• Field of Search: 711/206, 711/3, 711/207, 711/216, 711/203, 711/205
• US Class Current: 711/207
• CPC Class Codes: G06F 12/1036 for multiple virtual address spaces, e.g. segmentation G06F12/1045 takes precedence
• CPC Class Codes: G06F 2212/681 Multi-level TLB, e.g. microTLB and main TLB

Abstract

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. Virtual Hash Page Table (VHPT) efficiently supports two different methods of operating systems use to translate virtual addresses to physical addresses. This directly benefits the highly frequented path of address resolution.

Claims

1. A virtual hash page table apparatus for virtual address translation after a failed translation lookaside buffer search, comprising:

a virtual address; and

a mechanism used to compute a pointer from said virtual address to an index into a virtual hash page table, said index in the virtual hash page table comprising a translation to a physical address, said virtual hash page table apparatus is further configurable to allow both linear access and hashed access, and wherein said mechanism for virtual address translation further comprising;

circuitry to provide virtual address miss data;

circuitry to store said virtual address miss data describing said miss to enable an operating system to recover from said miss; and

circuitry to compute a second pointer from said virtual address miss data to a second index into said virtual hash page table, said second index in the virtual hash page table comprising a second translation to said physical address.

2. The apparatus of claim 1, wherein said index further comprising:

a virtual index used as a virtual address into said virtual hash page table.

3. The apparatus of claim 1, further comprising:

logic configured for an operating system to duplicate said mechanism used to compute said pointer from said virtual address.

4. The apparatus of claim 3, wherein said virtual hash page table apparatus configuration further indicates the format of translation pointer entries in said virtual hash page table.

5. The apparatus of claim 1, wherein said mechanism for virtual address translation further comprising:

circuitry to save virtual address miss data.

6. A method for use in processor for translating a virtual address, the method comprising the steps of:

configuring a virtual hash page table to allow both linear access and hashed access;

calculating a pointer from a virtual address;

utilizing said pointer to search said virtual hash page table for a virtual address translation to a physical address;

providing virtual address miss data on a translation miss;

storing said virtual address miss data describing said translation miss to enable an operating system to recover from said translation miss; and

computing a second pointer from said virtual address miss data, utilizing said second pointer to search said virtual hash page table for a second translation to said physical address.

7. The method of claim 6, wherein the set of calculating further includes:

using a value from a region register and a value from said virtual address for said calculation.

8. The method of claim 6, further including the step of:

searching said virtual hash page table using linear access.

9. The method of claim 6, further including the steps of:

searching said virtual hash page table using hashed access; and

computing a tag that uniquely identifies said translation given said index of said hashed access.

10. The method of claim 6, wherein said calculating a pointer from a virtual address step further including the step of:

computing a virtual index used as a virtual address into said virtual hash page table.

11. The method of claim 6, further including the steps of:

generating virtual address miss data if said search of said virtual hash page table for a virtual address translation to a physical address fails.

12. A virtual hash page table apparatus for virtual address translation after a failed translation lookaside buffer search, comprising:

means for configuring a virtual hash page table to allow both linear access and hashed access;

means for calculating a pointer from a virtual address;

means for utilizing said pointer to search said virtual hash page table for a virtual address translation to a physical address;

means for providing virtual address miss data on a translation miss; and

means for storing said virtual address miss data describing said translation miss to enable an operating system to recover from said translation miss; and

means for computing a second pointer from said virtual address miss data, said second pointer into said virtual hash page table for a second translation to said physical address.

13. The virtual hash page table apparatus of claim 12, further comprising:

means for using a value from a region register and a value from said virtual address for said calculation.

14. The virtual hash page table apparatus of claim 12, further comprising:

means for searching said virtual hash page table using linear access.

15. The virtual hash page table apparatus of claim 12, further comprising:

means for searching said virtual hash page table using hashed access; and

means for computing a tag that uniquely identifies said translation given said index of said hashed access.

16. The virtual hash page table apparatus of claim 12, wherein said means for calculating a pointer further comprises:

means for computing a virtual index used as a virtual address into said virtual hash page table.

17. The virtual hash page table apparatus of claim 12, further comprising:

means for generating virtual address miss data if said search of said virtual hash page table for said virtual address translation to said physical address fails.