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

Claim 2

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.

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 10

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.

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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.

Claim 17

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.

Claim 18

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.