Virtual memory address translation apparatus and method using link, auxiliary link and page tables

Claim 1

A method for translating a virtual address into a real address, comprising: a virtual address holding step of holding a virtual address larger than 32 bits comprising a segment number, a page index formatted as in a virtual address not larger than 32 bits and a page offset formatted as in a virtual address not larger than 32 bits, said virtual address being held as a translational object in such a manner as to correspond to a structure having a virtual space divided into segment units, each segment region is divided into page units corresponding to a real space; a hash processing step of generating a hash address from a part of said virtual address to serve as a base address of a link table; a link table retrieving step of adding a predetermined number of lower order bits of said segment number as an offset, to said hash address, retrieving said link table to obtain tag information of said virtual address, a base address of a page table and a link pointer used for retrieving an auxiliary link table and, outputting said base address of said page table as a correct base address when said tag information of said virtual address coincides with a predetermined number of higher order bits of said segment number; an auxiliary link table retrieving step of retrieving said auxiliary link table by said link pointer when said tag information does not coincide with said predetermined number of higher order bits of said segment number to obtain tag information of a next virtual address, a base address of a next page table and a next link pointer, and continuing retrieval of said auxiliary link table on the basis of said link pointer until a correct base address of said page table is obtained; a page table retrieving step of adding, as an offset, a part of said virtual address to said base address of said page table obtained in said link table retrieving step or in said auxiliary link table retrieving step so as to retrieve said page table, and obtaining a page frame number; and a real address generating step of combining a part of said virtual address as an offset with said page frame number obtained in said page table retrieving step, and generating a real address.

Claim 2

A method for translating a virtual address into a real address, comprising: a virtual address holding step of holding a virtual address larger than 32 bits comprising a segment number, a page index formatted as in a virtual address not larger than 32 bits and a page offset formatted as in a virtual address not larger than 32 bits, said virtual address being held as a translational object in such a manner as to correspond to a structure having a virtual space divided into segment units, each segment region is divided into page units corresponding to a real space; a hash processing step of generating a hash address from a part of said virtual address to serve as a base address of a link table; a link table retrieving step of adding a predetermined number of lower order bits of said segment number as an offset, to said hash address, retrieving said link table to obtain tag information of said virtual address, a base address of a page table and a link pointer used for retrieving an auxiliary link table and, outputting said base address of said page table as a correct base address when said tag information of said virtual address coincides with a predetermined number of higher order bits of said segment number; an auxiliary link table retrieving step of retrieving said auxiliary link table by said link pointer when said tag information does not coincide with said predetermined number of higher order bits of said segment number to obtain tag information of a next virtual address, a base address of a next page table and a next link pointer, and continuing retrieval of said auxiliary link table on the basis of said link pointer until a correct base address of said page table is obtained; a page table retrieving step of adding, as an offset, a part of said virtual address to said base address of said page table obtained in said link table retrieving step or in said auxiliary link table retrieving step so as to retrieve said page table, and obtaining a page frame number; and a real address generating step of combining a part of said virtual address as an offset with said page frame number obtained in said page table retrieving step, and generating a real address.

Claim 7

An apparatus for translating a virtual address into a real address, comprising: a virtual address holding means for holding a virtual address larger than 32 bits comprising a segment number, a page index formatted as in a virtual address not larger than 32 bits and a page offset formatted as in a virtual address not larger than 32 bits, in such a manner as to correspond to a structure having a virtual space divided into segment units, each segment region is divided into page units corresponding to a real space; 1 hash generation means for generating a hash address from a part of said virtual address to serve as a base address of a link table; a link table retrieving means for adding a predetermined number of lower order bits of said segment number as an offset, to said hash address, retrieving said link table to obtain tag information of said virtual address, a base address of a page table and a link pointer used for retrieving an auxiliary link table and, outputting said base address of said page table as a correct base address when said tag information of said virtual address coincides with a predetermined number of higher order bits of said segment number; auxiliary link table retrieving means for retrieving said auxiliary link table by said link pointer when said tag information does not coincide with said predetermined number of higher order bits of said segment number to obtain tag information of a next virtual address, a base address of a next page table and a next link pointer, and continuing retrieval of said auxiliary link table on the basis of said link pointer until a correct base address of said page table is obtained; a page table retrieving means for adding, as an offset, a part of said virtual address to said base address of said page table obtained by said link table retrieving means or by said auxiliary link table retrieving means so as to retrieve said page table, and obtaining a page frame number; and a real address generation means for combining a part of said virtual address as an offset with said page frame number obtained by said page table retrieving means, and generating a real address.

Claim 8

An apparatus for translating a virtual address into a real address, comprising: a virtual address holding means for holding a virtual address larger than 32 bits comprising a segment number, a page index formatted as in a virtual address not larger than 32 bits and a page offset formatted as in a virtual address not larger than 32 bits, in such a manner as to correspond to a structure having a virtual space divided into segment units, each segment region is divided into page units corresponding to a real space; 1 hash generation means for generating a hash address from a part of said virtual address to serve as a base address of a link table; a link table retrieving means for adding a predetermined number of lower order bits of said segment number as an offset, to said hash address, retrieving said link table to obtain tag information of said virtual address, a base address of a page table and a link pointer used for retrieving an auxiliary link table and, outputting said base address of said page table as a correct base address when said tag information of said virtual address coincides with a predetermined number of higher order bits of said segment number; auxiliary link table retrieving means for retrieving said auxiliary link table by said link pointer when said tag information does not coincide with said predetermined number of higher order bits of said segment number to obtain tag information of a next virtual address, a base address of a next page table and a next link pointer, and continuing retrieval of said auxiliary link table on the basis of said link pointer until a correct base address of said page table is obtained; a page table retrieving means for adding, as an offset, a part of said virtual address to said base address of said page table obtained by said link table retrieving means or by said auxiliary link table retrieving means so as to retrieve said page table, and obtaining a page frame number; and a real address generation means for combining a part of said virtual address as an offset with said page frame number obtained by said page table retrieving means, and generating a real address.

Claim 13

A method for translating a virtual address into a real address, comprising: a process ID holding step of holding an ID number of a process for address translation; a virtual address holding step of holding a virtual address larger than 32 bits comprising a segment number, a page index formatted as in a virtual address not larger than 32 bits and a page offset formatted as in a virtual address not larger than 32 bits, said virtual address being held as translational object in such a manner as to correspond to a structure having a virtual space divided into segment units, each segment region is divided into page units corresponding to a real space; a hash processing step of generating a hash address from said process ID and a part of said virtual address to serve as a base address of a link table; a link table retrieving step of adding a predetermined number of lower order bits of said segment number to said hash address, retrieving said link table to obtain said process ID, tag information of said virtual address, a base address of a page table and a link pointer used for retrieving an auxiliary link table and, outputting said base address of said page table as a correct base address when said process ID obtained by said table retrieval coincides with said process ID held by said process ID holding step and said tag information of said virtual address obtained by said table retrieval coincides with a predetermined number of higher order bits of said segment number; an auxiliary link table retrieving step of retrieving said auxiliary link table by said link pointer when at least one of said tag information and said process ID obtained in said link table retrieving step does not coincide, to thereby obtain a next process ID, tag information of a next virtual address, a base address of a next page table and a next link pointer, and continuing retrieval of said auxiliary link table on the basis of said link pointer until a correct base address of said page table is obtained; a page table retrieving step of adding, as an offset, a part of said virtual address to said base address of said page table obtained in said link table retrieving step or in said auxiliary link table retrieving step so as to retrieve said page table, and obtaining a page frame number; and a real address generating step of combining a part of said virtual address as an offset with said page frame number obtained in said page table retrieving step, and generating a real address.

Claim 14

A method for translating a virtual address into a real address, comprising: a process ID holding step of holding an ID number of a process for address translation; a virtual address holding step of holding a virtual address larger than 32 bits comprising a segment number, a page index formatted as in a virtual address not larger than 32 bits and a page offset formatted as in a virtual address not larger than 32 bits, said virtual address being held as translational object in such a manner as to correspond to a structure having a virtual space divided into segment units, each segment region is divided into page units corresponding to a real space; a hash processing step of generating a hash address from said process ID and a part of said virtual address to serve as a base address of a link table; a link table retrieving step of adding a predetermined number of lower order bits of said segment number to said hash address, retrieving said link table to obtain said process ID, tag information of said virtual address, a base address of a page table and a link pointer used for retrieving an auxiliary link table and, outputting said base address of said page table as a correct base address when said process ID obtained by said table retrieval coincides with said process ID held by said process ID holding step and said tag information of said virtual address obtained by said table retrieval coincides with a predetermined number of higher order bits of said segment number; an auxiliary link table retrieving step of retrieving said auxiliary link table by said link pointer when at least one of said tag information and said process ID obtained in said link table retrieving step does not coincide, to thereby obtain a next process ID, tag information of a next virtual address, a base address of a next page table and a next link pointer, and continuing retrieval of said auxiliary link table on the basis of said link pointer until a correct base address of said page table is obtained; a page table retrieving step of adding, as an offset, a part of said virtual address to said base address of said page table obtained in said link table retrieving step or in said auxiliary link table retrieving step so as to retrieve said page table, and obtaining a page frame number; and a real address generating step of combining a part of said virtual address as an offset with said page frame number obtained in said page table retrieving step, and generating a real address.

Claim 19

An apparatus for translating a virtual address into a real address, comprising: process ID holding means for holding an ID number of process for address translation; virtual address holding means for holding a virtual address larger than 32 bits comprising a segment number, a page index formatted as in a virtual address not larger than 32 bits and a page offset formatted as in a virtual address not larger than 32 bits, said virtual address being held as a translational object in such a manner as to correspond to a structure having a virtual space divided into segment units, and each segment region is divided into page units corresponding to a real space; hash generation means for generating a hash address from said process ID and a part of said virtual address to serve as a base address of a link table; link table retrieving means for adding a predetermined number of lower order bits of said segment number to said hash address, retrieving said link table to obtain said process ID, tag information of said virtual address, a base address of a page table and a link pointer used for retrieving an auxiliary link table and, outputting said base address of said page table as a correct base address when said process ID obtained by said table retrieval coincides with said process ID held by said process ID holding means and said tag information of said virtual address obtained by said table retrieval coincides with a predetermined number of higher order bits of said segment number; an auxiliary link table retrieving means for retrieving said auxiliary link table by said link pointer when at least one of said tag information and said process ID obtained by said link table retrieving means does not coincide, to thereby obtain a next process ID, tag information of a next virtual address, a base address of a next page table and a next link pointer, and continuing retrieval of said auxiliary link table on the basis of said link pointer until a correct base address of said page table is obtained; page table retrieving means for adding, as an offset, a part of said virtual address to said base address of said page table obtained by said link table retrieving means or by said auxiliary link table retrieving means so as to retrieve said page table, and obtaining a page frame number; and real address generation means for combining a part of said virtual address as an offset with said page frame number obtained by said page table retrieving means, and generating a real address.

Claim 20

An apparatus for translating a virtual address into a real address, comprising: process ID holding means for holding an ID number of process for address translation; virtual address holding means for holding a virtual address larger than 32 bits comprising a segment number, a page index formatted as in a virtual address not larger than 32 bits and a page offset formatted as in a virtual address not larger than 32 bits, said virtual address being held as a translational object in such a manner as to correspond to a structure having a virtual space divided into segment units, and each segment region is divided into page units corresponding to a real space; hash generation means for generating a hash address from said process ID and a part of said virtual address to serve as a base address of a link table; link table retrieving means for adding a predetermined number of lower order bits of said segment number to said hash address, retrieving said link table to obtain said process ID, tag information of said virtual address, a base address of a page table and a link pointer used for retrieving an auxiliary link table and, outputting said base address of said page table as a correct base address when said process ID obtained by said table retrieval coincides with said process ID held by said process ID holding means and said tag information of said virtual address obtained by said table retrieval coincides with a predetermined number of higher order bits of said segment number; an auxiliary link table retrieving means for retrieving said auxiliary link table by said link pointer when at least one of said tag information and said process ID obtained by said link table retrieving means does not coincide, to thereby obtain a next process ID, tag information of a next virtual address, a base address of a next page table and a next link pointer, and continuing retrieval of said auxiliary link table on the basis of said link pointer until a correct base address of said page table is obtained; page table retrieving means for adding, as an offset, a part of said virtual address to said base address of said page table obtained by said link table retrieving means or by said auxiliary link table retrieving means so as to retrieve said page table, and obtaining a page frame number; and real address generation means for combining a part of said virtual address as an offset with said page frame number obtained by said page table retrieving means, and generating a real address.