Method and apparatus for facilitating adaptive page sizes

1. A method for performing a page-table lookup in a manner that supports adaptive page sizes, comprising:

maintaining a page size for each page table entry in a set of page table entries in a page table, wherein the page size of a page table entry changes, during execution of a process, based on contention for the page table entry;

receiving a virtual address;

looking up the virtual address in the page table by performing a binary search on addresses in the page table to find an entry where the virtual address is in a range defined by the entry's starting virtual address and the entry's page size field,

wherein the entries in the page table are sorted by a starting virtual address in the page table entry; and

wherein during the lookup process the page size is used to determine a number of bits that must be compared to find a matching page table entry;

determining that a page table entry matches the virtual address if a virtual address in the page table entry matches the virtual address in the determined number of bits; and

if a matching page table entry is found, returning a physical page address from the matching page table entry.

2. The method of claim 1 , wherein physical pages are disjoint, such that a virtual address can only be present in one physical page.

3. The method of claim 2 , wherein changing the page size of the physical page dynamically optimizes performance criteria, including:

minimizing memory overhead and fragmentation of the page table;

minimizing the miss ratio of a translation look-aside buffer (TLB);

minimizing overhead in an input/output (I/O) system;

reducing contention for memory pages; or

minimizing a heuristically-weighted sum of several criteria.

4. The method of claim 2 , wherein looking up the virtual address in the page table involves first looking up the page table entry in a TLB which caches recently-accessed page table entries.

5. The method of claim 4 , wherein the page table is ordered by the starting address of virtual pages, and wherein if the TLB lookup fails, performing a lookup in the page table in main memory involves executing a binary search operation to determine which page table entry corresponds to the virtual address.

6. The method of claim 1 , wherein maintaining the page size for each physical page in the page table involves:

maintaining a segment table which includes entries for different memory segments;

wherein a given segment table entry contains a pointer to the page table for a corresponding memory segment; and

wherein the segment table entry contains a physical page size for all of the physical pages in the memory segment.

7. The method of claim 1 , wherein the method can be applied to a number of paging variations including:

segmented paging;

traditional paging;

multi-level hierarchical paging; or

paged segmentation.

8. The method of claim 1 , wherein the page size in an entry is independently updated when a corresponding physical page is split or merged.

9. The method of claim 1 , wherein the page size indicates an arbitrarily and dynamically-sized physical memory block.

10. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for performing a page-table lookup in a manner that supports adaptive page sizes, comprising:

maintaining a page size for each page table entry in a set of page table entries in a page table, wherein the page size of a page table entry changes, during execution of a process, based on contention for the page table entry;

receiving a virtual address;

looking up the virtual address in the page table by performing a binary search on addresses in the page table to find an entry where the virtual address is in a range defined by the entry's starting virtual address and the entry's page size field,

wherein the entries in the page table are sorted by a starting virtual address in the page table entry; and

wherein during the lookup process the page size is used to determine a number of bits that must be compared to find a matching page table entry;

determining that a page table entry matches the virtual address if a virtual address in the page table entry matches the virtual address in the determined number of bits; and

if a matching page table entry is found, returning a physical page address from the matching page table entry.

11. The non-transitory computer-readable storage medium of claim 10 , wherein physical pages are disjoint, such that a virtual address can only be present in one physical page.

12. The non-transitory computer-readable storage medium of claim 11 , wherein changing the page size of the physical page dynamically optimizes performance criteria, including:

minimizing memory overhead and fragmentation of the page table;

minimizing the miss ratio of a translation look-aside buffer (TLB);

minimizing overhead in an input/output (I/O) system;

reducing contention for memory pages; or

minimizing a heuristically-weighted sum of several criteria.

13. The non-transitory computer-readable storage medium of claim 11 , wherein looking up the virtual address in the page table involves first looking up the page table entry in a TLB which caches recently-accessed page table entries.

14. The non-transitory computer-readable storage medium of claim 13 , wherein the page table is ordered by the starting address of virtual pages, and wherein if the TLB lookup fails, performing a lookup in the page table in main memory involves executing a binary search operation to determine which page table entry corresponds to the virtual address.

15. The non-transitory computer-readable storage medium of claim 10 , wherein maintaining the page size for each physical page in the page table involves:

maintaining a segment table which includes entries for different memory segments;

wherein a given segment table entry contains a pointer to the page table for a corresponding memory segment; and

wherein the segment table entry contains a physical page size for all of the physical pages in the memory segment.

16. The non-transitory computer-readable storage medium of claim 10 , wherein the method can be applied to a number of paging variations including:

segmented paging;

traditional paging;

multi-level hierarchical paging; or

paged segmentation.

17. The non-transitory computer-readable storage medium of claim 10 , wherein the page size in an entry is independently updated when a corresponding physical page is split or merged.

18. The non-transitory computer-readable storage medium of claim 10 , wherein the page size indicates an arbitrarily and dynamically-sized physical memory block.

19. An apparatus that performs a page-table lookup in a manner that supports adaptive page sizes, comprising:

a page-size-maintaining mechanism configured to maintain a page size for each page table entry in a set of page table entries in a page table, wherein the page size of a page table entry changes, during execution of a process, based on contention for the page table entry;

a receiving mechanism configured to receive a virtual address;

a lookup mechanism configured to look up the virtual address in the page table by performing a binary search on addresses in the page table to find an entry where the virtual address is in a range defined by the entry's starting virtual address and the entry's page size field,

wherein the entries in the page table are sorted by a starting virtual address in the page table entry; and

wherein during the lookup process the page size is used to determine a number of bits that must be compared to find a matching page table entry;

a comparison mechanism configured to determine whether a page table entry matches the virtual address by comparing the determined number of bits of the virtual address with a virtual address in the page table entry; and

a response mechanism, wherein if a matching page table entry is found, the response mechanism is configured to return a physical page address from the matching page table entry.