Hybrid address translation

• US 9,251,092 B2
• Filed: 03/04/2013
• Issued: 02/02/2016
• Est. Priority Date: 03/28/2012
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bybell, Anthony J., Gschwind, Michael K.
• Primary Examiner(s): Chace, Christian P
• Assistant Examiner(s): VILLANUEVA, LEANDRO R
• Application Number:
  US13/783,791
• Publication Number:
  US 20130262815A1
• Time in Patent Office: 1,065 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0292 using tables or multilevel address translation means G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 12/1036 for multiple virtual address spaces, e.g. segmentation G06F12/1045 takes precedence
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/651 Multi-level translation tables
• CPC Class Codes: G06F 2212/684 TLB miss handling

Abstract

Embodiments of the invention relate to hybrid address translation. An aspect of the invention includes receiving a first address, the first address referencing a location in a first address space. The computer searches a segment lookaside buffer (SLB) for a SLB entry corresponding to the first address; the SLB entry comprising a type field and an address field and determines whether a value of the type field in the SLB entry indicates a hashed page table (HPT) search or a radix tree search. Based on determining that the value of the type field indicates the HPT search, a HPT is searched to determine a second address, the second address comprising a translation of the first address into a second address space; and based on determining that the value of the type field indicates the radix tree search, a radix tree is searched to determine the second address.

Claims

1. A computer implemented method for hybrid address translation in a computer, the method comprising:

receiving a first address, the first address comprising an effective address referencing a location in a first address space in a computer system comprising a first page table comprising a hashed page table (HPT), and a second page table comprising a radix tree;

searching a segment lookaside buffer (SLB) for an SLB entry corresponding to the first address, the SLB comprising a plurality of SLB entries each comprising a respective type field and a respective address field, the plurality of SLB entries comprising a first entry comprising a first type field corresponding to a search of the first page table comprising the HPT, and a second entry comprising a second type field corresponding to a search of the second page table comprising the radix tree;

determining whether a value of the type field in the SLB entry corresponding to the first address corresponds to a search of the first page table comprising the HPT or a search of the second page table comprising the radix tree; and

searching one of the first and second page tables to determine an address translation for the first address based on the type field in the SLB entry corresponding to the first address by;

based on determining that the value of the type field corresponds to the search of the first page table comprising the HPT, searching the first page table comprising the HPT to determine a second address, the second address comprising a translation of the first address into a second address space; and

based on determining that the value of the type field corresponds to the search of the second page table comprising the radix tree, searching the second page table comprising the radix tree to determine the second address.

2. The method of claim 1, wherein the address field of the first entry in the SLB comprises a virtual address corresponding to an effective address, and wherein searching the first page table to determine the second address comprises:

extracting the virtual address associated with the first address from the address field of the SLB entry corresponding to the first address; and

searching the first page table for the virtual address.

3. The method of claim 1, wherein the address field of the second entry in the SLB comprises an address space identifier (ID) and a segment size corresponding to an effective address, and wherein searching the second page table to determine the second address comprises:

extracting the address space ID and the segment size associated with the first address from the address field of the SLB entry corresponding to the first address;

determining a root of the search of the second page table comprising the radix tree based on the address space ID and the segment size; and

searching the second page table for the first address starting at the root.

4. The method of claim 3, wherein the address space ID comprises a process ID associated with the first address.

5. The method of claim 3, wherein the address space ID and the segment size indicate that the root is a level in the radix tree that is below a top level of the radix tree, and wherein the search of the radix tree for the first address starts at the level that is below the top level of the radix tree, such that the top level of the radix tree is not searched.

6. The method of claim 1, wherein the first address comprises an effective address issued by an application running on a computer as part of a memory access, and wherein the second address comprises a real address, and the second address space comprises a physical computer memory of the computer.

7. The method of claim 1, wherein the value of the type field is based on at least one of a type of memory access and a type of application associated with the first address.

8. The method of claim 1, wherein the first address space comprises a plurality of discontiguous memory regions.