Page table walker that uses at least one of a default page size and a page size selected for a virtual address space to position a sliding field in a virtual address

• US 6,088,780 A
• Filed: 03/31/1997
• Issued: 07/11/2000
• Est. Priority Date: 03/31/1997
• Status: Expired due to Term

• Current Assignee: Institute For The Development of Emerging Architectures LLC, Institute Of The Development Of Emerging Architecture, L.L.C.
• Original Assignee: Institute For The Development of Emerging Architectures LLC
• Inventors: Yamada, Koichi, Hays, Jim, Ross, Jonathan Kent, Burger, Stephen, Hammond, Gary N., Bryg, William R.
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): Verbrugge, Kevin
• Application Number:
  US08/829,337
• Time in Patent Office: 1,198 Days
• Field of Search: 711/204, 711/206, 711/209, 711/216
• US Class Current: 711/206
• 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 at least one of a default page size and a page size selected for a virtual address space to position a sliding field in a virtual address. 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 each selected for translating a different set 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 of the virtual address received, the selection unit positions a field in that virtual address based on the page size selected for translating the set of virtual addresses to which that virtual address belongs. 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 default page sizes each default page size selected for translating a different set of virtual addresses, wherein each different set of virtual addresses is mapped to one or more page sizes that are equal to or larger than the default page size for that set of virtual addresses; and

a page table walker including,

a selection unit coupled to said page size storage area to position a field in each virtual address received by selection unit based on the page size selected for translating that virtual address, and

a page table entry address generator coupled to receive the bits in the field identified for each virtual address.

2. The apparatus of claim 1, wherein:

for each virtual address received by said page table walker, 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 an 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 said different set of virtual addresses.

4. The apparatus of claim 3, wherein each register in said set of registers is also for storing a corresponding virtual address extension specifying a different virtual address space for each set of virtual addresses.

5. The apparatus of claim 4, wherein said set of registers are coupled to said page table entry address generator to provide the virtual address extension corresponding to the virtual address currently being translated.

6. The apparatus of claim 5, wherein said page table entry address generator performs a hash function on said virtual address extension and the output of said selection unit when identifying a entry in a page table for the virtual address currently being translated.

7. 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.

8. The apparatus of claim 1 further comprising:

a register, coupled to said selection unit, for storing a page table size, said selection unit positioning the field in each virtual address based on both the page size selected for translating that virtual address and the page table size.

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

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

a page size storage area for storing a plurality of default page sizes each default page size selected for translating a different set of virtual addresses, wherein each different set of virtual addresses is mapped to one or more page sizes that are equal to or larger than the default page size for that set of virtual addresses; and

a page table walker including,

a selection unit coupled to said page size storage area to position a field in each virtual address received by said selection unit based on the page size selected for translating that virtual address, and

a page table entry address generator coupled to receive the bits in the field identified for each virtual address; and

a page table stored in said main memory and coupled to said page table walker.

11. The computer system of claim 10, wherein:

for each virtual address received by said page table walker, 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 an entry in a page table.

12. The computer system of claim 10, 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 said different set of virtual addresses.

13. The computer system of claim 12, wherein each register in said set of registers also has stored therein a corresponding virtual address extension specifying a different virtual address space for each set of virtual addresses.

14. The computer system of claim 12, wherein said set of registers are coupled to said page table entry address generator to provide said virtual address extension corresponding to the virtual address currently being translated.

15. The computer system of claim 14, wherein said page table entry address generator performs a hash function on said virtual address extension and the output of said selection unit when identifying a entry in a page table for the virtual address currently being translated.

16. The computer system of claim 10 further comprising:

a 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.

17. The computer system of claim 10 further comprising:

a register, coupled to said selection unit, having stored therein a page table size, said selection unit positioning the field in each virtual address based on both the page size selected for translating that virtual address and the page table size.

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

19. A computer system comprising:

an operating system stored in a machine readable medium coupled to a processor, said operating system for causing said processor to distinguish between a first and second virtual address space;

a page table stored in said machine readable medium; and

a page table walker in said processor including,

a selection unit to position a field in each virtual address received in either a first or second position based respectively on which of said first and second virtual address spaces that virtual address belongs, and

a page table entry address generator coupled to said selection unit to identify entries in said page table based on the bits in the field identified for each of the virtual addresses.

20. The computer system of claim 19, wherein:

for each of the virtual addresses received, 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 an entry in said page table.

21. The computer system of claim 19, wherein the first and second positions are respectively for a smaller and larger page size.

22. The computer system of claim 21, wherein the smaller page size is equal to or smaller than every page size found in the first virtual address space, and the larger page size is equal to or smaller than every page size found in the second virtual address space.

23. The computer system of claim 19 further comprising:

a set of registers in said processor and coupled to said page table walker, wherein said processor executing said operating system stores in said set of registers a different virtual address extension for each of said first and second virtual address spaces, and wherein said processor executing said operating system also stores in said set of registers a page size for each of said first and second virtual address spaces, the page sizes identifying said first and second positions.

24. The computer system of claim 19 further comprising:

a translation unit in said processor and 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.

25. The computer system of claim 19 further comprising:

a register, coupled to said selection unit, for storing a page table size, said selection unit locating the field in each virtual address also based on the page table size.

26. A method for determining virtual address to physical address translations, said method comprising the computer implemented steps of:

identifying a first and second page size for respectively translating a first and second virtual address;

positioning a field in each of said first and second virtual addresses based respectively on said first and second page sizes;

identifying a first and second entry in a page table based respectively on data in the fields positioned for said first and second virtual addresses;

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

determining that said first virtual address is mapped to a page having an actual size that is larger than said first page size; and

determining translations for translating said first and second virtual addresses based respectively on the actual size of the page and said second page size.

27. The method of claim 26 further comprising the preliminary step of:

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

28. The method of claim 26, wherein said step of identifying said first and second page size includes the step identifying said first and second page size based respectively on bits said first and second virtual addresses.

29. The method of claim 26, wherein said method further includes the steps of:

identifying a first and second virtual address extension based respectively on bits in said first and second virtual addresses; and

identifying said first and second entry in said page table also based respectively on said first and second virtual address extensions.

30. The method of claim 26 further comprising the steps of:

storing in a dynamic storage area data indicating a size for the page table; and

identifying said first and second entry in said page table also based respectively on said size.

31. A method for determining virtual address to physical address translations, said method comprising the computer implemented steps of:

identifying a first and second page size for respectively translating virtual addresses that belong to a first and second virtual address space;

positioning a field in each of a first and second virtual address based respectively on said first and second page sizes;

identifying a first and second entry in a page table based respectively on data in the fields positioned 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.

32. The method of claim 31, wherein said method further includes the step of:

associating said first and second page size respectively with said first and second virtual addresses based on bits in said first and second virtual addresses.

33. The method of claim 31, wherein:

said method further includes the step of identifying a first and second virtual address extension respectively for said first and second virtual address space; and

said step of identifying said first and second entry further includes the step of identifying said first and second entry also based respectively on said first and second virtual address extensions.

34. The method of claim 31 further includes the steps of:

selecting said first page size to be equal to or smaller than the smallest page size in said first virtual address space; and

selecting said second page size to be equal to or smaller than the smallest page size in said second virtual address space.

35. The method of claim 31 further comprising the preliminary step of:

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