Patent ID: 7895410

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