Method and apparatus for implementing a page table walker that uses a sliding field in the virtual addresses to identify entries in a page table

• US 6,012,132 A
• Filed: 03/31/1997
• Issued: 01/04/2000
• Est. Priority Date: 03/31/1997
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Yamada, Koichi, Hammond, Gary N.
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US08/829,782
• Time in Patent Office: 1,009 Days
• Field of Search: 711/202, 711/203, 711/205, 711/206, 711/207, 711/209
• US Class Current: 711/207
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 2212/652 Page size control

Abstract

A method and apparatus for implementing a page table walker that uses a sliding field in the virtual addresses to identify entries in a page table. According to one aspect of the invention, an apparatus for use in a computer system is provided that includes a page size storage area and a page table walker. The page size storage area is used to store a number of page sizes selected for translating a number of virtual addresses. The page table walker includes a selection unit coupled to the page size storage area, as well as a page entry address generator coupled to the selection unit. For each virtual address received by the selection unit, the selection unit positions a field in that virtual address based on the page size selected for translating that virtual address. In response to receiving the bits in the field identified for each of the virtual addresses, the page entry address generator identifies an entry in a page table based on those bits.

Claims

1. An apparatus for use in a computer system, said apparatus comprising:

a page size storage area for storing a plurality of page sizes selected for translating a plurality of virtual addresses; and

a page table walker including,

a selection unit coupled to said page size storage area to select a field in each of said plurality of virtual addresses, said field is based on the page size selected for translating that virtual address to a page table entry and on the size of the page table, and

a page table entry address generator coupled to receive bits in the selected field identified for each of said plurality of virtual addresses for selecting an entry in the page table for each virtual address.

2. The apparatus of claim 1, wherein:

for each of said plurality of virtual addresses, said page table entry address generator performs a hash function on the bits that fall within the field identified for that virtual address to identify a corresponding entry in a page table.

3. The apparatus of claim 1, wherein said page size storage area includes:

a set of registers each having a page size field, wherein each page size field is for storing the one of said plurality of page sizes to be used by said page table walker when translating a different set of virtual addresses.

4. The apparatus of claim 1 further comprising:

a translation unit, coupled to said page table walker, to store a plurality of translations for translating virtual addresses into physical addresses, wherein said page table walker operates in response to a page miss signal from said translation unit.

5. The apparatus of claim 1 further comprising:

a register, coupled to said selection unit, for storing a dynamic indication of the size of the page table.

6. The apparatus of claim 1, wherein said selection unit is implemented in hardware on a processor.

22. The apparatus of claim 1, wherein each of said plurality of virtual addresses comprises an offset field, wherein said offset field in each of said plurality of virtual addresses does not overlap said field selected by said selection unit in that virtual address.

7. A computer system including a processor coupled to a main memory, said computer system comprising:

a page table Stored in said main memory;

a page size storage area having stored therein a plurality of page sizes selected for translating a plurality of virtual addresses;

a page table walker coupled to said page table and including,

a selection unit coupled to said page size storage area to select a field in each of said plurality of virtual addresses, said field is based on the page size selected for translating that virtual address to a page table entry and on the size of the page table, and

a page table entry address generator coupled to receive bits in the selected field identified for each of said plurality of virtual addresses for selecting an entry in said page table for each virtual address.

8. The computer system of claim 7, wherein:

for each of said plurality of virtual addresses, said page table entry address generator performs a hash function on the bits that fall within the field identified for that virtual address to select the entry in said page table for that virtual address.

9. The computer system of claim 7, wherein said page size storage area includes:

a set of registers each having a page size field, wherein each page size field has stored therein the one of said plurality of page sizes to be used by said selection unit when translating a different set of virtual addresses.

10. The computer system of claim 7 further comprising:

translation unit, coupled to said page table walker, having stored therein a plurality of translations for translating virtual addresses into physical addresses, wherein said page table walker operates in response to a page miss signal from said translation unit.

11. The computer system of claim 7 further comprising:

a register, coupled to said selection unit, having stored therein the size of the page table.

12. The computer system of claim 7, wherein said page table walker is implemented in hardware on said processor.

23. The computer system of claim 7, wherein said computer system uses a single page table scheme.

24. The computer system of claim 23, wherein each of said plurality of virtual addresses is translated into a physical address identifying a location in a page of memory, and wherein each said page has a single entry in said page table.

13. A method for determining virtual address to physical address translations by use of a page table, said method comprising the computer implemented steps of:

identifying different page sizes from a page size storage that have been selected for translating a plurality of virtual addresses;

selecting a field in each of said plurality of virtual addresses based on the page size selected for that virtual address and on the size of a page table, wherein at least two different field positions are selected;

for each of said plurality of virtual addresses, identifying an entry in the page table based on data in the field identified for that virtual address;

accessing each identified entry in said page table; and

determining translations for translating said plurality of virtual addresses by using entries in said page table.

14. The method of claim 13 further comprising the preliminary step of:

detecting that translations for said plurality of virtual addresses are not stored in a translation look-aside buffer.

15. The method of claim 13, wherein said step of identifying different page sizes includes the step of identifying a page size for each of said plurality of virtual addresses based on particular bits in that virtual address, wherein at least two different page sizes are identified by the bits.

16. The method of claim 13, further comprising the steps of:

selecting said different page sizes for translating said plurality of virtual addresses; and

generating page table entry addresses to access entries in said page table.

17. The method of claim 13

further includes the step of storing in a dynamic storage area data indicating the size for the page table.

25. The method of claim 13, wherein the translations are determined using a single page table.

26. The method of claim 25, further comprising the step of:

determining a physical address for each of said plurality of virtual addresses using the translations, each physical address identifying a location in a page, wherein each said page has one entry in said page table.

18. A method for determining virtual address to physical address translations by use of a page table, said method comprising the computer implemented steps of:

identifying first and second page sizes from a page size storage for respectively translating first and second virtual addresses;

selecting a field in each of said first and second virtual addresses based on the size of the page table and based respectively on said first and second page sizes;

identifying first and second entries in said page table based respectively on data in the fields selected for said first and second virtual addresses;

accessing said first and second entries in said page table; and

determining translations for translating said first and second virtual addresses by using entries from said page table.

19. The method of claim 18, wherein said step of identifying first and second page sizes includes the step of selecting said first and second page size based respectively on particular bits in said first and second virtual addresses.

20. The method of claim 18 further comprising the steps of:

selecting said first and second page sizes for translating said first and second virtual addresses; and

generating page table entry addresses to access entries in said page table.

21. The method of claim 18 further comprising the preliminary step of:

detecting that translations for first and second virtual addresses are not stored in a translation look-aside buffer.

27. The method of claim 18, wherein the translations are determined using a single page table.

28. The method of claim 27 wherein each entry in said page table identifies a separate page for data storage.