Method and apparatus for mapping page table trees into virtual address space for address translation

Claim 1

A method for self-recursively mapping a page table tree into a virtual address space containing virtual pages, the method comprising the steps of: identifying a segment table node of the page table tree; identifying a plurality of leaf nodes of the page table tree, each leaf node containing at least one page table entry, each page table entry matching a virtual page number to a corresponding physical page number by containing the physical page number at a location in the page table tree that corresponds to the virtual page number, a plurality of the page table entries functioning simultaneously as pointers to nodes in the page table tree and as addresses of physical pages corresponding to virtual pages; and mapping the leaf nodes into the virtual address space with the page table entries ordered in the virtual address space according to their virtual page numbers.

Claim 2

A method for self-recursively mapping a page table tree into a virtual address space containing virtual pages, the method comprising the steps of: identifying a segment table node of the page table tree; identifying a plurality of leaf nodes of the page table tree, each leaf node containing at least one page table entry, each page table entry matching a virtual page number to a corresponding physical page number by containing the physical page number at a location in the page table tree that corresponds to the virtual page number, a plurality of the page table entries functioning simultaneously as pointers to nodes in the page table tree and as addresses of physical pages corresponding to virtual pages; and mapping the leaf nodes into the virtual address space with the page table entries ordered in the virtual address space according to their virtual page numbers.

Claim 12

A method for use by a virtual memory manager in managing a first virtual address space and a second virtual address space, the method comprising the steps of: identifying a first page table tree of a first process corresponding to the first virtual address space; identifying a second page table tree of a second process corresponding to the second virtual address space; and mapping the second virtual address space into the first virtual address space by placing the address of a segment node of the second page table tree into a reserved segment table entry in the first page table tree, at least one of the page table trees being self-recursive in that two nodes at different levels of that page table tree are both stored in the same page of memory.

Claim 13

A method for use by a virtual memory manager in managing a first virtual address space and a second virtual address space, the method comprising the steps of: identifying a first page table tree of a first process corresponding to the first virtual address space; identifying a second page table tree of a second process corresponding to the second virtual address space; and mapping the second virtual address space into the first virtual address space by placing the address of a segment node of the second page table tree into a reserved segment table entry in the first page table tree, at least one of the page table trees being self-recursive in that two nodes at different levels of that page table tree are both stored in the same page of memory.

Claim 16

An apparatus for translating a virtual page number portion of a given virtual address into a corresponding physical page number, the apparatus comprising: a self-recursive page table tree having a segment table node and a plurality of leaf nodes, each leaf node containing at least one page table entry, each page table entry matching a virtual page number to a corresponding physical page number by containing the physical page number at a location in the page table tree that corresponds to the virtual page number; a memory management unit configured to attempt no read the physical page number from the page table entry which matches the virtual page number, to fail in that attempt when no physical page number presently corresponds to the virtual page number, and to make an additional attempt after the page table entry is updated; and a virtual memory manager configured to update the page table entry if the memory management unit fails in its attempt to read a physical page number from the page table entry, the virtual memory manager accessing the page table entries by virtual addresses in a virtual address space.

Claim 17

An apparatus for translating a virtual page number portion of a given virtual address into a corresponding physical page number, the apparatus comprising: a self-recursive page table tree having a segment table node and a plurality of leaf nodes, each leaf node containing at least one page table entry, each page table entry matching a virtual page number to a corresponding physical page number by containing the physical page number at a location in the page table tree that corresponds to the virtual page number; a memory management unit configured to attempt no read the physical page number from the page table entry which matches the virtual page number, to fail in that attempt when no physical page number presently corresponds to the virtual page number, and to make an additional attempt after the page table entry is updated; and a virtual memory manager configured to update the page table entry if the memory management unit fails in its attempt to read a physical page number from the page table entry, the virtual memory manager accessing the page table entries by virtual addresses in a virtual address space.

Claim 26

An apparatus for translating a virtual page number portion of a given virtual address into a corresponding physical page number, the given virtual address being within the union of a first virtual address space and a second virtual address space, the apparatus comprising: a first page table tree of a first process corresponding to the first virtual address space; a second page table tree of a second process corresponding to the second virtual address space, each page table tree having a respective segment table node and a respective plurality of leaf nodes, each leaf node containing at least one page table entry, each page table entry matching a virtual page number to a corresponding physical page number by containing the physical page number at a location in the respective page table tree that corresponds to the virtual page number, at least one of the page table trees being self-recursive, the apparatus further characterized in that a reserved segment table entry in the first page table tree contains the address of the segment node of the second page table tree; a memory management unit configured to attempt to read the physical page number from the page table entry which matches the virtual page number, to fail in that attempt when no physical page number presently corresponds to the virtual page number, and to make an additional attempt after the page table entry is updated; and a virtual memory manager configured to update the page table entry if the memory management unit fails in its attempt to read a physical page number from the page table entry, the virtual memory manager accessing the page table entries by virtual addresses in a virtual address space.

Claim 27

An apparatus for translating a virtual page number portion of a given virtual address into a corresponding physical page number, the given virtual address being within the union of a first virtual address space and a second virtual address space, the apparatus comprising: a first page table tree of a first process corresponding to the first virtual address space; a second page table tree of a second process corresponding to the second virtual address space, each page table tree having a respective segment table node and a respective plurality of leaf nodes, each leaf node containing at least one page table entry, each page table entry matching a virtual page number to a corresponding physical page number by containing the physical page number at a location in the respective page table tree that corresponds to the virtual page number, at least one of the page table trees being self-recursive, the apparatus further characterized in that a reserved segment table entry in the first page table tree contains the address of the segment node of the second page table tree; a memory management unit configured to attempt to read the physical page number from the page table entry which matches the virtual page number, to fail in that attempt when no physical page number presently corresponds to the virtual page number, and to make an additional attempt after the page table entry is updated; and a virtual memory manager configured to update the page table entry if the memory management unit fails in its attempt to read a physical page number from the page table entry, the virtual memory manager accessing the page table entries by virtual addresses in a virtual address space.