Virtual memory computer apparatus and address translation mechanism employing hashing scheme and page frame descriptor that support multiple page sizes

A method for providing address translations for a computer system having a virtual memory that is mapped onto a physical memory, the apparatus comprising:

• a) providing at least one page frame descriptor for describing a contiguous portion of physical memory, each page frame descriptor having a base physical address, a physical address range beginning at the base physical address and a translation entry pointer;
• b) providing at least one translation block for describing a contiguous portion of virtual memory, each translation block having a base virtual address, a virtual address range beginning at the base virtual address, a page size used to map the virtual address range of the translation block, a header and at least one translation entry, each header having a translation block pointer and each translation entry having a backward pointer, each translation entry of the translation block corresponding to a different equal-sized translation range of the virtual address range of the translation block, if the translation range of a translation entry is backed by a physical memory page frame, then the backward pointer of the translation entry points to a describing page frame descriptor that describes the corresponding page frame and the translation entry pointer of the describing page frame descriptor points to the translation entry;
• and
• c) providing a hash list having a plurality of hash entries, each hash entry having a translation header pointer and an associated hash index unique to the hash entry, if a virtual address translation chain of at least one translation block exists, wherein each translation block of the virtual address translation chain has a virtual address range such that each virtual address of the virtual address range of a translation block of the virtual address translation chain can be hashed to provide a hash index of a same hash entry, then the translation header pointer of the hash entry having the hash index obtained will point to a first translation block of the virtual address translation chain, if more than one translation block is in the virtual address translation chain then the translation block pointer of the first translation block will point to a second translation block in the virtual address translation chain and every translation block of the virtual address translation chain except the first translation block will be pointed to by a translation block pointer of a different translation block of the virtual address translation chain;
• d) receiving a virtual address to be translated;
• e) extracting a first translation hash index from the virtual address to be translated;
• f) if a hash entry corresponding to the first translation hash index is not empty, then making the translation block pointed to by the translation header pointer of the hash entry corresponding to the first translation hash index a translation block being examined and examining the virtual address range of the translation block being examined to determine whether the virtual address to be translated is contained within the virtual address range of the translation block being examined;
• g) if the virtual address to be translated is contained within the virtual address range of the translation block being examined, examining the translation entry of the translation block being examined having a translation range that contains the virtual address to be translated to determine whether the translation entry is valid, if the translation entry is valid, using the backward pointer of the translation entry to locate the page frame descriptor that describes a page frame that is backed by the translation entry;
• h) if the virtual address to be translated is not contained within the virtual address range of the translation block being examined, then examining the translation block pointer of the translation block being examined and, if the translation block pointer is not empty, making the translation block pointed to by the translation block pointer of the translation block being examined the translation block being examined and repeating steps g) and h).

An apparatus for providing address translations for a computer system having a virtual memory that is mapped onto a physical memory, the apparatus comprising:

• at least one page frame descriptor for describing a contiguous portion of physical memory, each page frame descriptor having a base physical address, a physical address range beginning at the base physical address and a translation entry pointer;
• at least one translation block for describing a contiguous portion of virtual memory, each translation block having a base virtual address, a virtual address range beginning at the base virtual address, a page size used to map the virtual address range of the translation block, a header and at least one translation entry, each header having a translation block pointer and each translation entry having a backward pointer, each translation entry of the translation block a corresponding to a different equal-sized translation range of the virtual address range of the translation block, if the translation range of a translation entry is backed by a physical memory page frame, then the backward pointer of the translation entry points to a describing page frame descriptor that describes the corresponding page frame and the translation entry pointer of the describing page frame descriptor points to the translation entry;
• and
• a hash list having a plurality of hash entries, each hash entry having a translation header pointer and an associated hash index unique to the hash entry, if a virtual address translation chain of at least one translation block exists, wherein each translation block of the virtual address translation chain has a virtual address range such that each virtual address of the virtual address range of a translation block of the virtual address translation chain can be hashed to provide a hash index of a same hash entry, then the translation header pointer of the hash entry having the hash index obtained will point to a first translation block of the virtual address translation chain, if more than one translation block is in the virtual address translation chain then the translation block pointer of the first translation block will point to a second translation block in the virtual address translation chain and every translation block of the virtual address translation chain except the first translation block will be pointed to by a translation block pointer of a different translation block of the virtual address translation chain.