Virtual address to physical address translation cache that supports multiple page sizes

• US 5,479,627 A
• Filed: 09/08/1993
• Issued: 12/26/1995
• Est. Priority Date: 09/08/1993
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Khalidi, Yousef A., Talluri, Madhusudhan, Narad, Charles E., Chessin, Stephen A., Anderson, Glen R., Kong, Shing I.
• Primary Examiner(s): WHITFIELD, MICHAEL
• Application Number:
  US08/118,398
• Time in Patent Office: 839 Days
• Field of Search: 395/400, 395/425
• US Class Current: 711/205
• 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 2212/652 Page size control

Abstract

A method and apparatus for translating a virtual address to a physical address. A virtual address to be translated has a virtual page offset and a virtual page number. The virtual address to be translated addresses a page of memory. The size of this page is unknown. There are L different possible page sizes where L is a positive integer greater than one. Each of the L different page sizes is selected to be a test page size and a test is performed. During the test, a pointer into a translation storage buffer is calculated. The pointer is calculated from the virtual address to be translated by assuming that the virtual address to be translated corresponds to a mapping of the test page size. The pointer points to a candidate translation table entry of the translation storage buffer. The candidate translation table entry has a candidate tag and candidate data. The candidate tag identifies a particular virtual address and the candidate data identifies a particular physical address corresponding to the particular virtual address. A virtual address target tag is extracted from the virtual address to be translated. The virtual address target tag is calculated by assuming that the virtual address to be translated corresponds to a mapping of the test page size. The target tag and the candidate tag are then compared. If the target tag matches the candidate tag, the candidate data is provided as the physical address translation corresponding to the virtual address to be translated.

Claims

1. A method for translating a first virtual address to a physical address, the method comprising the steps of:

receiving the first virtual address, the first virtual address comprising a virtual page offset and a virtual page number, the first virtual address being mapped by an unknown page size, the unknown page size being one of L different page sizes where L is a positive integer greater than one;

then, for each of the L page sizes, selecting a different one of the L page sizes to be a test page size,

(i) calculating a pointer into a translation storage buffer, the pointer being calculated from the first virtual address by assuming that the first virtual address corresponds to a mapping of the test page size, the pointer pointing to a candidate translation table entry of the translation storage buffer, the candidate translation table entry comprising a candidate tag and candidate data, the candidate tag identifying a particular virtual address and the candidate data identifying a particular physical address corresponding to the particular virtual address,

(ii) extracting a virtual address target tag from the first virtual address, the virtual address target tag being calculated by assuming that the first virtual address corresponds to a mapping of the test page size,

(iii) comparing target tag to the candidate tag, and

(iv) if the target tag matches the candidate tag, providing the candidate data as the physical address translation corresponding to the first virtual address,

wherein the translation storage buffer is comprised of an Nth power of two translation table entries and each translation table entry is M words in size where N and M are positive integers, and the step of calculating the pointer includes the steps of;

forming a translation storage buffer index by extracting N least significant bits of the virtual page number of the first virtual address assuming the first virtual address is mapped using the test page size;

adding the product of the translation storage buffer index and M to a base address to form the pointer.

2. The method as set forth in claim 1 wherein the pointer is a second virtual address.

3. The method as set forth in claim 1 wherein:

a smallest page size is selected from among the L page sizes;

the target tag is formed by extracting all but N least significant bits of the virtual page number of the first virtual address assuming the first virtual address is mapped using the smallest page size; and

the candidate tag is formed by extracting all but N least significant bits of the virtual page number of the particular virtual address assuming the particular virtual address is mapped using the smallest page size.

4. The method as set forth in claim 1, the method further comprising the step of signaling that a translation failed if the target tag has not matched the candidate tag after testing every page size.

5. A method for translating a first virtual address to a physical address, the method comprising the steps of:

receiving the first virtual address, the first virtual address comprising a virtual page offset and a virtual page number, the first virtual address being mapped by an unknown page size, the unknown page size being one of L different page sizes where L is a positive integer greater than one;

then, for each of the L page sizes, selecting a different one of the L page sizes to be a test page size,

(i) calculating a pointer into a translation storage buffer, the pointer being calculated from the first virtual address by assuming that the first virtual address corresponds to a mapping of the test page size, the pointer pointing to a candidate translation table entry of the translation storage buffer, the candidate translation table entry comprising a candidate tag and candidate data, the candidate tag identifying a particular virtual address and the candidate data identifying a particular physical address corresponding to the particular virtual address,

(ii) extracting a virtual address target tag from the first virtual address, the virtual address target tag being calculated by assuming that the first virtual address corresponds to a mapping of the test page size,

(iii) comparing the target tag to the candidate tag, and

(iv) if the target tag matches the candidate tag, providing the candidate data as the physical address translation corresponding to the first virtual address,

wherein the translation steerage buffer is comprised of sub translation storage buffers, each sub translation storage buffer corresponding to a page size and is comprised of a positive integral power of two translation table entries and each translation table entry is M words in size where M is a positive integer, and the step of calculating the pointer includes the steps of;

forming a translation storage buffer index by extracting N least significant bits of the virtual page number of the first virtual address assuming the first virtual address is mapped using the test page size where N is the base two logarithm of the number of translation table entries of the sub translation storage buffer corresponding to the test page size; and

adding the product of the translation storage buffer index and M to a base address to form the pointer, the base address corresponding to the test page size, the base address being one of L base addresses.

6. The method as set forth in claim 5 wherein multiple translation storage buffers are tested.

7. A method for translating a first virtual address to a physical address, the method comprising the steps of:

receiving the first virtual address to be translated, the first virtual address comprising a virtual page offset and a virtual page number, the first virtual address being mapped by an unknown page size, the unknown page size being a first or second page size, the first page size not equal to the second page size;

calculating first and second pointers into a translation storage buffer, the first pointer being calculated from the first virtual address by assuming that the first virtual address corresponds to a mapping of the first page size, the first pointer pointing to a first candidate translation table entry of the translation storage buffer, the first candidate translation table entry comprising a first candidate tag and first candidate data, the first candidate tag identifying a first particular virtual address and the first candidate data identifying a first particular physical address corresponding to the first particular virtual address, the second pointer being calculated from the virtual address to be translated by assuming that the first virtual address corresponds to a mapping of the second page size, the second pointer pointing to a second candidate translation table entry of the translation storage buffer, the second candidate translation table entry comprising a second candidate tag and second candidate data, the second candidate tag identifying a second particular virtual address and the second candidate data identifying a second particular physical address corresponding to the second particular virtual address;

extracting first and second virtual address target tags from the first virtual address, the first virtual address target tag being calculated by assuming that the first virtual address corresponds to a mapping of the first page size, the second virtual address target tag being calculated by assuming that the first virtual address corresponds to a mapping of the second page size;

comparing the first target tag to the first candidate tag;

if the first target tag matches the first candidate tag, providing the first candidate data as the physical address translation corresponding to the first virtual address;

comparing the second target tag to the second candidate tag;

if the second target tag matches the second candidate tag, providing the second candidate data as the physical address translation corresponding to the first virtual address,

wherein the translation storage buffer is comprised of sub translation storage buffers, each sub translation storage buffer corresponding to a page size of the first and second page sizes and is comprised of a positive integral power of two translation table entries and each translation table entry is M words in size where M is a positive integer, the step of calculating the first and second pointers includes the steps of;

forming a first translation storage buffer index by extracting N1 least significant bits of the virtual page number of the first virtual address assuming the first virtual address is mapped using the first page size where N1 is the base two logarithm of the number of translation-table entries of the sub translation storage buffer corresponding to the first page size;

adding the product of the first translation storage buffer index and M to a first base address to form the first pointer;

forming a second translation storage buffer index by extracting N2 least significant bits of the virtual page number of the first virtual address assuming the first virtual address is mapped using the second page size where N2 is the base two logarithm of the number of translation table entries of the sub translation storage buffer corresponding to the second page size; and

adding the product of the second translation storage buffer index and M to a second base address to form the second pointer.

8. The method as set forth in claim 7 wherein the first base address is equal to the second base address.

9. The method as set forth in claim 7 wherein the first pointer is a second virtual address and the second pointer is a third virtual address.

10. The method as set forth in claim 7 wherein:

the translation storage buffer is comprised of an Nth power of two translation table entries where N is a positive integer;

the first page size is smaller than the second page size;

the first target tag is formed by extracting all but N least significant bits of the virtual page number of the first virtual address assuming the first virtual address is mapped using the first page size;

the first candidate tag is formed by extracting all but N least significant bits of the virtual page number of the first particular virtual address assuming the first particular virtual address is mapped using the first page size;

the second target tag is formed by extracting all but N least significant bits of the virtual page number of the first virtual address assuming the first virtual address is mapped using the first page size; and

the second candidate tag is formed by extracting all but N least significant bits of the virtual page number of the second particular virtual address assuming the second particular virtual address is mapped using the first page size.

11. The method as set forth in claim 7, the method further comprising the step of signaling that a translation failed if both the first target tag does not match the first candidate tag and the second target tag does not match the second candidate tag.

12. The method as set forth in claim 7 wherein multiple translation storage buffers are tested.

13. An apparatus for translating a first virtual address to a physical address, the apparatus comprising:

a receiver adapted to receiving the first virtual address, the virtual address comprising a virtual page offset and a virtual page number, the first virtual address being mapped by an unknown page size, the unknown page size being a first or second page size, the first page size not equal to the second page size;

a calculator adapted to calculating first and second pointers into a translation storage buffer, the calculator coupled to the receiver, the first pointer being calculated from the first virtual address by assuming that the first virtual address corresponds to a mapping of the first page size, the first pointer pointing to a first candidate translation table entry of the translation storage buffers, the first candidate translation table entry comprising a first candidate tag and first candidate data, the first candidate tag identifying a first particular virtual address and the first candidate data identifying a first particular physical address corresponding to the first particular virtual address, the second pointer being calculated from the first virtual address by assuming that the first virtual address corresponds to a mapping of the second page size, the second pointer pointing to a second candidate translation table entry of the translation storage buffer, the second candidate translation table entry comprising a second candidate tag and second candidate data, the second candidate tag identifying a second particular virtual address and the second candidate data identifying a second particular physical address corresponding to the second particular virtual address;

an extractor adapted to extracting first and second virtual address target tags from the first virtual address, the extractor coupled to the receiver, the first virtual address target tag being calculated by assuming that the first virtual address corresponds to a mapping of the first page size, the second virtual address target tag being calculated by assuming that the first virtual address corresponds to a mapping of the second page size;

a first comparator coupled to the calculator and the extractor, the first comparator adapted to comparing the first target tag to the first candidate tag;

a first provider coupled to the first comparator, the first provider adapted to providing the first candidate data as the physical address translation corresponding to the first virtual address if the first target tag matches the first candidate tag;

a second comparator coupled to the calculator and the extractor, the second comparator adapted to comparing the second target tag to the second candidate tag;

a second provider coupled to the second comparator, the second provider adapted to providing the second candidate data as the physical address translation corresponding to the first virtual address if the second target tag matches the second candidate tag,

wherein the translation storage buffer is comprised of sub translation storage buffers, each sub translation storage buffer corresponds to a page size of the first and second page sizes and is comprised of an integral power of two translation table entries and each translation table entry is M words in size where M is a positive integer, the calculator comprising;

a first indexer adapted to forming a first translation storage buffer index by extracting N1 least significant bits of the virtual page number of the first virtual address assuming the first virtual address is mapped using the first page size where N1 is the base two logarithm of the number of translation table entries of the sub translation storage buffer corresponding to the first page size;

a first pointer calculator adapted to adding the product of the first translation storage buffer index and M to a first base address to form the first pointer;

a second indexer adapted to forming a second translation storage buffer index by extracting N2 least significant bits of the virtual page number of the first virtual address assuming the first virtual address is mapped using the second page size where N2 is the base two logarithm of the number of translation table entries of the sub translation storage buffer corresponding to the second page size; and

a second pointer calculator adapted to adding the product of the second translation storage buffer index and M to a second base address to form the second pointer.

14. The apparatus as set forth in claim 13 wherein the first pointer is a second virtual address and the second pointer is a third virtual address.

15. The apparatus as set forth in claim 13 wherein the first base address is equal to the second base address.

16. The apparatus as set forth in claim 13 wherein:

the translation storage buffer is comprised of an Nth power of two translation table entries where N is a positive integer;

the first page size is smaller than the second page size;

the first target tag is formed by extracting all but N least significant bits of the virtual page number of the first virtual address assuming the first virtual address is mapped using the first page size;

the first candidate tag is formed by extracting all but N least significant bits of the virtual page number of the first particular virtual address assuming the first particular virtual address is mapped using the first page size;

the second target tag is formed by extracting all but N least significant bits of the virtual page number of the first virtual address assuming the first virtual address is mapped using the first page size; and

the second candidate tag is formed by extracting all but N least significant bits of the virtual page number of the second particular virtual address assuming the second particular virtual address is mapped using the first page size.

17. The apparatus as set forth in claim 13, the apparatus further comprising a signaler coupled to the first and second comparator, the signaler adapted to signaling that a translation failed if both the first target tag does not match the first candidate tag and the second target tag does not match the second candidate tag.