Virtual memory address translation mechanism with combined hash address table and inverted page table

• US 4,680,700 A
• Filed: 12/19/1986
• Issued: 07/14/1987
• Est. Priority Date: 12/07/1983
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Simpson, Richard O., Hester, Phillip D.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Lacasse, Randy W.
• Application Number:
  US06/845,228
• Time in Patent Office: 207 Days
• Field of Search: 364/200, 364/900
• US Class Current: 711/206
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 12/1036 for multiple virtual address spaces, e.g. segmentation G06F12/1045 takes precedence
• CPC Class Codes: G06F 2212/652 Page size control
• CPC Class Codes: G06F 2212/683 Invalidation

Abstract

A virtual memory address translation mechanism is provided for converting virtual memory addresses provided by a CPU into real memory addresses within page frames in a large hierachial memory wherein the real memory space is substantially smaller than the scope of the virtual memory. The conversion or translation mechanism includes a combined table in the memory which includes a first list covering the respective virtual address of each memory address (Inverted Page Table or IPT) and a second list connecting each of a plurality of hashed addresses with a predetermined initial virtual address of a linked group of virtual addresses, each of which when hashed produces the connected hashed address (Hashed Addressed Table, HAT). The system also has means for hashing a selected virtual address to produce a hashed address. Also included is apparatus for sequentially searching through the linked group of virtual addresses in the combined table until a selected virtual address is located as well as apparatus responsive to the location of a particular selected virtual address for accessing from the first list, the real memory address of the located virtual address.

Claims

1. A data processing system comprising:

a central processing unit for accessing information stored in page frames by providing a virtual memory address from a virtual memory address space, said virtual memory address space including a plurality of page frame addresses,

a first memory for storing information organized as a plurality of page frames and accessible by memory addresses represented by a real memory address space and wherein the virtual memory address space includes a substantially larger number of page frames than the real memory address space;

means connected to the central processing unit and the first memory for converting virtual memory addresses received from the central processing unit into real memory addresses for accessing information from single page frames from said first memory, said converting means including;

means for hashing a selected virtual address to produce a hashed address;

a first table having a list of hashed addresses each with a corresponding predetermined initial virtual address and a pointer to an entry in a second table;

said second table having a list of virtual addresses corresponding to the initial virtual addresses in the first table and further having a location in the second table corresponding directly to a unique page frame in the real memory address space and each virtual address including a corresponding link address, said link address connecting a plurality of noncontiguous virtual addresses that when hashed produce the same hashed address; and

means for receiving an input virtual memory address, hashing said input virtual memory address with said hashing means to produce an input hashed address, selecting a location in said first table in accordance with said input hashed address, searching the corresponding linked addressed locations until the input virtual memory address is located, locating the corresponding input virtual address in the second table and its corresponding real address.

2. A data processing unit according to claim 1 wherein said virtual address converting means further includes means for storing said first and second table in a manner that access to an entry in the first table will provide access to the corresponding entry in the second table.

3. A data processing system according to claim 2 wherein said virtual address converting means further includes means for providing said real address by calculating a table offset value for the entry in the second table.

4. A data processing system according to claim 3 wherein said virtual address converting means includes means for accessing addresses in said second table by calculating the offset based upon the link address of the corresponding predetermined initial virtual address and an address of the table entry.

5. In a data processing system having a central processing unit for accessing information stored in page frames by providing a virtual memory address from a virtual memory address space, said virtual memory address space including a plurality of page frame addresses, a first memory for storing information organized as a plurality of page frames and accessible by memory addresses represented by a real memory address space and wherein the virtual memory address space includes a substantially larger number of page frames than the real memory address space, the first memory also including a first table having a list of hashed addresses each with a corresponding predetermined initial virtual address and a pointer to an entry to a second table and said second table having a list of virtual addresses corresponding to the initial virtual addresses in the first table and further having a location in the second table corresponding directly to a unique page frame in the real memory address space and each virtual address including a corresponding link address, said link address connecting a plurality of noncontiguous virtual addresses that when hashed produce the same hashed address, a method for converting an input virtual address to a corresponding real address, said method comprising the steps of:

hashing the input virtual address to produce an input hashed address;

selecting a location in the first table in accordance with the input hashed address;

searching the linked addressed locations to locate the input virtual address; and

locating in the second table the corresponding virtual address and its corresponding real address.

6. A method according to claim 5 wherein said step of locating in the second table the real address includes the step of calculating the real address from the offset position of the corresponding virtual address in the second table.

7. A method according to claim 6 wherein said step of calculating the real address includes the step of calculating the offset based upon the link address of the corresponding predetermined initial virtual address in the first table.

8. A data processing system comprising:

a central processing unit for accessing information stored in page frames by providing a virtual memory address from a virtual memory address space, said virtual memory address space including a plurality of page frame addresses,

a first memory for storing information organized as a plurality of page frames and accessible by memory addresses represented by a real memory address space and wherein the virtual memory address space includes a substantially larger number of page frames than the real memory address space;

means connected to the central processing unit and the first memory for converting virtual memory addresses received from the central processing unit into real memory addresses for accessing inforamtion from single page frames from said first memory, said converting means including;

means for hashing a selected virtual address to produce a hashed address;

a first table having a list of hashed addresses each with a corresponding predetermined initial virtual address and a pointer to an entry in a second table;

said second table having a list of virtual addresses corresponding to the initial virtual addresses in the first table and further having a location in the second table corresponding directly to a unique page frame address in the real memory address space and each virtual address including a corresponding link address, said link address connecting a plurality of noncontiguous virtual addresses that when hashed produce the same hashed address and wherein each of said linking addresses is the address of the next connected virtual address in the second table; and

means for receiving an input virtual memory address, hashing said input virtual memory address with said hashing means to produce an input hashed address, selecting a location in said first table in accordance with said input hashed address, searching the corresponding linked addressed locations until the input virtual memory address is located, locating the corresponding input virtual address in the second table and its corresponding real address.

9. A data processing unit according to claim 8 wherein said virtual address converting means further includes means for storing said first and second table in a manner that access to an entry in the first table will provide access to the corresponding entry in the second table.

10. A data processing system according to claim 9 wherein said virtual address converting means further includes means for providing said real address by calculating a table offset value for the entry in the second table.

11. A data processing system according to claim 10 wherein said virtual address converting means includes means for accessing addresses in said second table by calculating the offset based upon the link address of the corresponding predetermined initial virtual address and an address of the table entry.

12. In a data processing system having a central processing unit for accessing information stored in page frames by providing a virtual memory address from a virtual memory address space, said virtual memory address space including a plurality of page frame addresses, a first memory for storing information organized as a plurality of page frames and accessible by memory addresses represented by a real memory address space and wherein the virtual memory address space includes a substantially larger number of page frames than the real memory address space, the first memory also including a first table having a list of hashed addresses each with a corresponding predetermined initial virtual address and a pointer to an entry to a second table and said second table having a list of virtual addresses corresponding to the initial virtual addresses in the first table and further having locations in the second table corresponding directly to page frame addresses in the realmemory address space and each virtual address including a corresponding link address, said link address connecting a plurality of noncontiguous virtual addresses than when hashed produce the same hashed address and wherein each of said linking addresses is the address of the next connected virtual address in the second table, a method for converting an input virtual address to a corresponding real address, said method comprising the steps of:

hashing the input virtual address to produce an input hashed address;

selecting a location in the first table in accordance with the input hashed address;

seaching the linked addressed locations to locate the input virtual address; and

locating in the second table the corresponding virtual address and its corresponding real address.

13. A method according to claim 12 wherein said step of locating in the second table the real address includes the step of calculating the real address from the offset position of the corresponding virtual address in the second table.

14. A method according to claim 13 wherein said step of calculating the real address includes the step of calculating the offset based upon the link address of the corresponding predetermined initial virtual address in the first table.