JP2000122928A - Access method for page table - Google Patents

Abstract

PROBLEM TO BE SOLVED: To enable an operating system to access hash algorithm used by hardware by storing virtual memory page address-to-physical memory page address conversion and a tag in an entry of a page table. SOLUTION: When an instruction is a TTAG instruction, a program location held in a TTAG entry of an interruption trap handler pointer 504 is loaded to a program counter 506. Then a 1st instruction of a software-based tag hash function 510 is loaded to an instruction register 502 and the software-based tag hash function 510 is executed. While the function 510 is executed, a register Ry including a virtual address is taken out of a register file 512. The function 510 generates a hash tag by processing the virtual address and stores the hash tag in the register Ry.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to memory organization in a computer system. More specifically,
The present invention relates to a virtual memory system having a page table accessed by a hash function.

[0002]

2. Description of the Related Art Conventional computer systems simulate more logical memory than physical memory actually exists, allowing virtual memory to allow a computer to execute several programs in parallel regardless of their size. Use a technology called. Parallel user programs access physical main memory addresses through virtual addresses assigned by the operating system. Mapping virtual addresses to physical main memory addresses is a process known as virtual address translation. Virtual memory translation can be accomplished by a number of techniques, and the processor can access the desired information in main memory.

[0003] The virtual address space and the physical address space are:
Divided into equal sized memory blocks, commonly called pages, the page tables provide translation between virtual and physical addresses. Each page table entry generally includes virtual and / or physical addresses, as well as protection and status information about the page. The context generally includes information about the type of access the page has received. For example, a dirty bit indicates that the data in the page has been modified.
Typically, the page table is stored in memory because it is large. Thus, each of the normal memory accesses may require at least two accesses, one to accomplish the translation and another to access the physical memory location.

[0004] Many computer systems that support virtual address translation include translation reference buffers (TLB, Tabl).
e Lookaside Buffer). TLB is generally
A small, fast associative memory, typically located on or near the processing unit, that stores recently used virtual and physical address pairs. The TLB contains a subset of the translations in the page table and can be accessed very quickly. When the processing unit needs information from main memory, the processing unit sets the virtual address to TLB
Send to The TLB receives the page number of the virtual address and returns the physical page number. The physical page number is combined with the lower address information to access the desired byte or word in main memory.

[0005] In most cases, the TLB cannot contain the entire page table, so a procedure must be implemented to update the TLB. If the virtual page is accessed and there is no translation in the TLB, the page table is accessed to determine the translation of this virtual page number to a physical page number and that information is entered into the TLB. Accessing the page table takes 20 times longer than accessing the TLB, and thus the speed of execution of the program is optimized by keeping the translations utilized within the TLB.

[0006] Most computer systems today have physical random access (RA) in the computer.
M) To increase memory, some mass storage, typically disks, is used. This enhancement of main memory allows larger programs to be executed than would be possible if only main memory were available. Also,
Disk memory is much cheaper than RAM, but much slower. Depending on the length of the program and contention with other programs, a portion of the program may be in main memory and a portion may be on disk. Immediately accessible parts of the program are sent to main memory, while those parts which are not being used are left on disk.

For example, if a program is used on a computer that is 2 megabytes long and has 1 megabyte of main memory, the program uses 2 megabytes of virtual addresses. Since the main memory can only hold one megabyte of information, the remaining one megabyte of program information is stored on disk. At any one time, half of the program occupies the available physical memory, so half of the virtual addresses can be mapped to program information and the other half cannot. Access to information in the main memory is performed normally. That is,
First, the TLB is referenced to see if it contains a translation, and if there is no translation, the TLB is updated with the information in the page table and the TLB is
Is referred to again.

When accessing information that is not in main memory, the TLB must first be converted for translation that is not in that memory.
Is referred to. Next, the page table is referenced to obtain conversion information for updating the TLB. However,
The page table only has a translation of the information in main memory, and thus does not have the necessary translation information. This condition is called a page fault. In response to a page fault, a physical page is assigned to the referencing virtual page, and this information is inserted into the page directory. If all physical pages are already associated with other virtual pages, a page fault
The handler needs to select the old virtual page to swap out from the physical page to disk, so that the physical page is free to receive the new virtual page. There are many algorithms for determining old virtual pages to swap out, such as a first-in first-out or least recently used algorithm. As is well known in the art, page fault handlers are generally implemented in software, but the TLB update process can operate on either hardware or software.

FIG. 1 illustrates the above process. At step 112, the virtual address is presented to the TLB. If the translation for that virtual address is in the TLB (TLB hit), the associated physical address is obtained from the TLB and used to access physical memory (step 1).
14). If the translation for the virtual address is not in the TLB (TLB miss), the translation for the virtual address is referenced in the page directory / table (step 116). If the translation is in the page directory, this information is inserted into the TLB (step 118) and the virtual address is presented again (step 11).
2). At this time, a TLB hit occurs, and the physical memory is accessed using the obtained physical address.

If the virtual address is on a page at a virtual address that is not associated with a page at the physical address, there is no entry for this page in the page directory and a page fault occurs. In this situation, the software page fault handler (step 1
20) assigns physical pages to virtual pages, copies pages from disk to physical pages, and updates the page table. Next, the virtual address is presented again to the TLB. However, because there is no translation in the TLB yet, a TLB miss occurs and the TLB is updated from the page directory. When the virtual address is presented again to the TLB, a TLB hit is made and the physical memory obtained is used to access the physical memory.

FIG. 2 shows a simplified method of accessing an entry in a translation reference buffer (TLB) in response to the presentation of a virtual address. For purposes of illustration, the illustrated TLB has only one entry, but typically the TLB has many more entries. The virtual address is loaded into register 201. This virtual address is virtual page number 2
03 and a physical offset 205. The physical offset corresponds to the page size. 4 km
For a computer system having a page size of bytes, the physical offset 205 is the lower one of the address.
Two bits (bits 11 to 0) specify a specific byte in the page. The remaining bits in the register indicate the virtual page number. The term “page offset” is a term often used in the art and is synonymous with the term “physical offset”.

Other bits may be used to uniquely specify the conversion to a physical page number. For example,
The “address space identifier” bit or the “region identifier” bit can be used to identify a physical page.
However, for the purposes of the present invention, all such bits are considered part of the virtual page number.

In the example shown, the virtual page number becomes a virtual tag and is provided as one input to the TLB comparator 207. The TLB 209 has two connected portions of a TLB tag 211 and a physical page number 213 associated therewith. TLB tag 211 provides a second input to TLB comparator 207, which compares the TLB tag with the virtual tag. If the tags match, the comparator indicates a TLB hit and the physical page number 213 is combined with the physical offset 205 to provide the physical (real) memory address. If the tags do not match, there is a TLB miss and
TLB using the TLB miss process described in connection with
Update LB.

FIG. 3 illustrates the process of retrieving physical page information that provides the virtual page number needed to update the TLB after a TLB miss. As mentioned above, the virtual-physical mapping is maintained in a page table. One approach to converting a given virtual address to a physical address is to use a many-to-one function (hash
(hash)) to form an index into the page table. This provides a pointer to a linked list of entries. Next, the entries are searched for a match. The virtual page number is compared to an entry in the page table (virtual tag) to determine a match. If the two are equal, the page / table /
Entries provide physical address translation.

In the example shown, hash function 301 is performed on virtual page number 203 to form an index. This index is stored in the page table 303
Offset into As shown, the index is 0, ie, the index points to the first entry 305 in the page table. Each entry in the page table has multiple parts, but generally includes at least a virtual tag 307, a physical page 309, and a pointer 311. If virtual page number 203 is equal to virtual tag 307, physical page 309 provides the desired physical (real) memory page address. If the virtual tags do not match, the pointer 311 effectively points to a chain of entries in memory included in the physical translation information. The additional information contained in this chain is needed when multiple virtual page numbers can hash to the same page table entry.

As shown, pointer 311 points to chain segment 313. This chain segment contains the same type of information as the page table.
As before, the virtual page number 203 is compared to the next virtual tag 315 to see if a match occurs. If a match occurs, the associated physical page 317
Provide the address of the desired physical memory page.
If no match occurs, pointer 319 is examined to find the next chain segment, if necessary. As shown, the pointer 319 is in another chain
If it does not point to a segment, a page fault has occurred. In that case, the page fault software program is used and the page table is updated, as described in connection with FIG.

The above method works well in systems where the virtual tags are smaller than the computer's base data path size. However, if the virtual tag is
If so, two comparisons are needed to see if the virtual tag and virtual page number are the same.

Transferred to Dale Morris et al., "Computer Memory Address Control Apparatus
Utilizing Hashed Address Tags in Page Tables Whic
h Are Compared to a Combined Address Tag and Index
Which Are Longer than the Basic Data Width of the
U.S. Pat. No. 5,724,538, entitled "Associated Computer," incorporated herein by reference, discloses a method for reducing the size of a virtual tag and thereby determining whether the virtual tag and the virtual page number are the same. A scheme is disclosed that reduces the number of required comparisons. Basically, Dale
Maurice and colleagues believe that a portion of the virtual
It was represented by an index, and thus knew that a portion of the address did not need to be represented by a virtual tag.

FIG. 4 shows a simplified block diagram of the embodiment disclosed by Dale Morris et al. In FIG. 4, the page table 413 includes “hash tags” 421 and 423. The hash index 409 is formed by taking the virtual page number bits 401 and performing the index hash function 405 on the bits so that they are no longer than the basic data width of the computer. Similarly, a hash tag is formed by taking the virtual page number bits 401 and performing a tag hash function 427, the resulting hash tag being no longer than the basic data width of the computer. Although FIG. 4 does not show an explicit connection between the tag hash function 427 and the hash tags 421 and 423, the algorithm represented by the tag hash function 427 uses the hash tags 421 and 42.
Note that 3 is used when generated and inserted into page table 413.

[0020] The index hash function 405 and the tag hash function 427 are used to the extent that, for any given virtual page number, the combination of the resulting hash index and the resulting hash tag is unique. Complementary. Therefore, when a virtual page is accessed, the virtual page number 401 is applied to the index hash function 405 and the hash tag (hash tag 42) in the page table 413 is used.
1, 423, etc.). The hash tag provided from table 413 is sent to comparison function 429. At the same time, the virtual page number 401 and the hash tag 425 provided to the tag hash function 427 are generated. If the hash tag 425 matches the hash tag from the page table 413, the memory access operation is completed using a physical page (such as the physical page stored in the entry 317 of 417). If the tags do not match, a pointer to the page table entry (pointers 319, 419) is used to determine if a chain segment exists.
Etc.) are accessed. No chain segments or all chain segments without finding a match
If a segment is found, the operating system page fault handler is invoked, as described above.

Note that index hash function 405 and tag hash function 427 are accessed by both hardware and software. The hardware accesses the hash function when converting virtual page numbers to physical page numbers, and the software accesses the hash table when initializing the page table and
When accessing and modifying a table, the page
You must access the hash function as needed to correct the fault. In the prior art, hash algorithms have been provided in essentially two forms. Computer hardware includes a hardware-based version of a hashing algorithm that can expedite the virtual-to-physical conversion, and the operating system allows the virtual-to-physical conversion when initializing, accessing, or modifying the page tables. Included a software-based version of the hash algorithm to generate the physical transformation.

[0022]

Therefore, changes in the hash algorithm negatively impact the length of the design cycle and require close coordination between hardware and operating system designers. Required both hardware and software changes. In addition, Windows provided by Microsoft
It is impractical for commercial operating systems, such as NT, to support a variety of changing hash algorithms. What is needed in the art is to allow an operating system to access the hash algorithm used by the hardware, thereby replacing the actual hash algorithm with the operating system.
It is not necessary to code it in the system.

[0023]

SUMMARY OF THE INVENTION The present invention is a method and apparatus for applying hardware-based virtual memory to software. In the field of computing technology, virtual memory schemes are used to translate logical virtual addresses to physical addresses used by computer hardware, and page tables are generally used to store virtual-to-physical translations. used.

In prior art computer systems, a hash algorithm is used to generate a hash index and a hash tag from a virtual address. The hash index is used to refer to the entry in the page table, and the hash index
The tag was stored in the entry along with the physical page number. In such computer systems, computer hardware had to generate hash indexes and hash tags when handling translation reference buffer (TLB) misses. In addition, the computer operating system (or other system hardware) generates hash indexes and hash tags when initializing, modifying, or accessing page tables, such as when handling page faults I had to. Therefore,
Such computer systems are computer
A first version used by the hardware;
A second coded in the computer operating system (or other system software)
This version included two versions of the hash algorithm.

In accordance with the present invention, two instructions are provided that expose a hardware hash algorithm to software. The first instruction is a translation hash entry address (THASH).
ss) The instruction generates a hash index indicating an entry in the page table from the virtual address.
The second instruction is a translation hash entry tag (TTA
G: translation Hashed Entry Tag) instruction, which generates a hash tag stored in the entry of the page table referred to by the hash index from the virtual address. By providing these two instructions, the computer operating system (or other system software) does not need to code the hash algorithm used by the computer hardware. Rather, the THASH and TTAG instructions provide an interface that allows software to access the hash algorithm used by the hardware.

In the first embodiment of the present invention, THA
When a SH or TTAG instruction is executed, a trap is generated that executes a routine that implements the appropriate hash function. In a second embodiment of the present invention, the THA
The SH and TTAG instructions are executed in hardware by the CPU.

[0027]

DETAILED DESCRIPTION OF THE INVENTION The present invention does not require the hash function to be implemented in software, but rather allows the operating system (or other software) to use the hardware by the hardware of the computer system on which the software is running. Methods and apparatus that can access index and tag hash functions that are performed. The invention is basically realized by two computer instructions. The first instruction is a translation hash entry address instruction (Translation Hash
ed Entry Address instruction), which is referred to herein as a THASH instruction. The second instruction is Translation Hashed EntryTag in
struction) instruction, and is referred to herein as a TTAG instruction.

The THASH instruction has the following format.

THASH Rx = Ry

The virtual address is specified by the register Ry, and the generated hash index is stored in the register Ry.
Put in x. Therefore, in FIG.
The H instruction applies the index hash function 405 to software.

Similarly, the TTAG instruction has the following format.

TTAG Rx = Ry

The virtual address is specified by the register Ry, and the generated hash tag is stored in the register Rx. Thus, the TTAG instruction exposes the index hash function 427 of FIG. 4 to software.

The invention is implemented in computer systems from low performance desktop computers having a single CPU to relatively complex high performance server computers having more than 32 CPUs. In low performance computers, the hash function can be implemented by a series of software instructions stored in the computer's basic input / output system (BIOS) code.
In such computers, the most frequently used transform fits into a translation reference buffer (TLB). T
When encountering an LB miss, the processor jumps to a hash function stored in the BIOS to calculate the hash index and hash tag. In such computers, this scheme provides satisfactory performance because the page tables are not accessed very often.

In higher performance computers with multiple CPUs, the hash function can be implemented in hardware. In such a computer, many programs can be active at the same time, and not all frequently used conversions are compatible with the TLB.
Thus, when a TLB miss occurs, a hardware-based hash function is accessed and a hash index and hash tag are generated.

FIG. 5 is a simplified block diagram illustrating an embodiment of the present invention implemented on a low performance computer 501. The computer 501 includes an instruction register 502, an instruction decode execution logic 503, an interrupt trap handler pointer 504, a program counter 506,
Software-based index hash function 5
08, software-based tag hash function 51
Register file 5 which is 0 and N registers
12 inclusive.

When the computer 501 executes a THASH or TTAG instruction, the instruction is stored in the instruction register 5
02 is loaded. Instruction decode execution logic 503
Decodes a THASH or TTAG instruction and generates an instruction trap. If the instruction is a THASH instruction, the THASH of the interrupt trap handler pointer 504
The program location held in the entry is loaded into the program counter 506. Then, the software-based index hash function 50
8 are loaded into the instruction register 502;
Software-based index hash function 5
08 is executed. During execution of function 508, register Ry containing the virtual address is retrieved from register file 512. Function 508 processes the virtual address to generate a hash index and stores the hash index in register Rx. Next, the function 50
8 ends and execution continues with the instruction immediately after the THASH instruction.

Similarly, if the instruction is a TTAG instruction, the program location held in the TTAG entry of interrupt trap handler pointer 504 is loaded into program counter 506. Thereafter, the first instruction of the software-based tag hash function 510 is loaded into the instruction register 502 and the software-based tag hash function 510 is executed. During execution of function 510, register Ry containing the virtual address
Is retrieved from the register file 512. Function 510 processes the virtual address to generate a hash tag and stores the hash tag in register Ry. next,
Function 510 terminates and execution continues with the instruction immediately after the TTAG instruction.

Note that the software-based index hash function 508 and the software-based tag hash function 510 can be provided in various ways. These functions are contained in the BIOS code of the computer system and can be stored in read-only memory. Also, these functions are provided as part of an "abstraction layer" that implements certain architected computer instructions in software when such instructions are not explicitly supported in hardware by the CPU. Sometimes. Alternatively, functions 508 and 510 may be provided as part of a low-level driver specific to computer 501.
However, the part of the operating system that maintains and accesses the page tables may "don't know" the actual algorithm implemented by functions 508 and 510. The operating system is T
This is because these algorithms can be accessed by the ASH instruction and the TTAG instruction.

FIG. 6 is a simplified block diagram illustrating an embodiment of the present invention implemented on a high performance computer 601. The computer 601 includes an instruction register 602, an instruction decode execution logic 603, a hardware-based index hash function 604, a hardware
It includes a base tag hash function 605 and a register file 606 having N registers.

When the computer 601 is THASH or T
When executing a TAG instruction, the instruction is loaded into instruction register 602. Instruction decode execution logic 60
3 decodes a THASH or TTAG instruction.
If the instruction is a THASH instruction, the instruction decode execution logic 603 uses the register Ry in the register file 606
Fetches the virtual address from the hardware-based index hash function 60
Applies to 4. The function 604 generates a hash index, provides the hash index to the instruction decode execution logic 603, and stores the hash index in the register Rx of the register file 606. Next, the execution is continued by the instruction immediately after the THASH instruction.

Similarly, if the instruction is a TTAG instruction, instruction decode execution logic 603 causes register file 6
Fetch a virtual address from register Ry at 06 and apply the virtual address to hardware-based tag hash function 605. Function 605 generates a hash tag, provides the hash tag to instruction decode execution logic 603, and then stores the hash tag in register Rx of register file 606. Next, TTA
Execution continues with the instruction immediately following the G instruction. Note that the hardware-based hash function can be implemented on the same integrated circuit as the CPU, on a separate integrated circuit from the CPU, or in any other manner known in the art.

The present invention allows the operating system software (or other system software) to access the page tables even if the software does not "know" the actual hash algorithm used by the computer system. Make it possible. For example, when the operating system is initializing the page table, the operating system performs the following steps.

1. Create the first virtual-to-physical page mapping stored in the page table.

2. For each virtual-to-physical page mapping stored in the page table, the THAS
Execute the H instruction to generate a hash index pointing to an entry in the page table, execute the TTAG instruction to generate a hash tag stored in the page table, and execute the page index referenced by the hash index. Store the hash tag and physical page number in the table entry.

Similarly, when the required virtual pages are stored on disk and the operating system handles page faults, the operating system performs the following steps.

1. Retrieve a virtual page from disk. 2. Find the physical page that stores the virtual page. 3. Execute a THASH instruction to generate a hash index pointing to an entry in the page table. 4. Execute the TTAG instruction to generate a hash tag that is stored in the page table. 5. The hash tag and the physical page number are stored in the page table entry referenced by the hash index. 6. The virtual page extracted from the disk is stored in the physical page.

It is clear that the above steps have been simplified and that the operating system is quite complex. However, an important concept for the present invention is that in the prior art, software routines of the operating system (or other system software) included a hash algorithm to access the page table. In, the hash algorithm used by the hardware is "applied" to software that uses the TTAG and THASH instructions, so that the operating system does not actually need to include the hash algorithm.

In US Pat. No. 5,724,538, incorporated by reference above, the primary purpose is to reduce the virtual address size to the basic data size of the computer system.
The object is to provide a mechanism by which the hash index of a hash tag can be adapted to the basic data path size of a computer system even if the path size is exceeded. For example, 32-bit data
Computers with a path size typically have 4 gigabytes of physical address space, and it may be desirable to have a larger virtual address space.

For computer systems having a data path size of 64 bits, this is less important. However, by using a hash function to form indexes and tags and providing access to the operating system (or other system software) by THASH and TTAG instructions (according to the invention), the computer designer can Will have a sophisticated tool that can balance the size of the page table with the time required to search the page table.

If the size of the page table is relatively large, the time required to search the page table is relatively flat, since the table has more entries and fewer chain segments. Be shortened. However, page tables require more memory and are relatively sparse.

In contrast, if the page table is small, the table has fewer entries and the chain
The more segments, the deeper the table and the longer the time required to search the page table. However, the page table requires less memory and many entries will include a virtual-to-physical translation.

The index hash function calculates the page hash
Associated with the size of the table, all virtual addresses generate a unique hash index and hash tag combination. Thus, the computer designer can change the page table size and hash algorithm based on the desired trade-off between speed and page table size. In fact, the page table size can be varied to tune the performance of a particular computer system executing a particular mixture of programs. In the computer system 501 of FIG. 5, only by replacing various functions,
Software-based index hash function 5
08 and software based tag hash function 51
0 can be changed. In the computer system 601 shown in FIG.
By changing the microcode of the PU, the hardware-based index hash function 604 and the hardware-based tag hash function 605 can be changed. Because the operating system (or other system software) utilizes these features through THASH and TTAG instructions,
There is no need to change the operating system (or other system software) when the hash function changes.

There is a continuing practical trend in the computer industry toward high performance hardware. However,
An inexpensive commercial "shirinki wrap (shirinki wrap) that can run on a variety of hardware architectures
There is also a somewhat contradictory practical trend towards "wrapped" operating systems. The present invention does not require that a commercially available "Silink Wrap" operating system, such as the Windows NT (TM) operating system provided by Microsoft, include the actual hash algorithm used to access the table. In addition, it allows access to virtual memory page tables of a variety of different types of computer systems. Thus, the present invention provides a mechanism by which both these practical trends can continue.

Although the present invention has been described with reference to preferred embodiments, workers skilled in the art will recognize that changes may be made in form and detail without departing from the spirit and scope of the invention.

According to the present invention, the operating system
Since the system has access to the hash algorithm used by the hardware, there is no need to code the hash algorithm into the operating system.

[Brief description of the drawings]

FIG. 1 illustrates a prior art procedure for responding to a virtual address presented during execution of a program.

FIG. 2 illustrates a prior art method of accessing an entry in a translation reference buffer (TLB).

FIG. 3 illustrates a prior art method for retrieving physical page information after a TLB miss and updating the TLB.

FIG. 4 is a diagram of a prior art page table scheme in which hash tags are stored in a page table.

FIG. 5 is a simplified block diagram illustrating an embodiment of the present invention as implemented on a low performance computer.

FIG. 6 is a simplified block diagram illustrating an embodiment of the present invention as implemented on a high performance computer.

[Explanation of symbols]

 413 page table

 ──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Stephen G. Burger United States 95050 Santa Clara, California, Forbes Avenue 2257 (72) Inventor Gary N. Hammond United States 95008 Campbell, California, Sunnybrook Drive 519 (72) Inventor James O. Hayes USA 95125 Campbell Avenue, San Jose, California 1722 (72) Inventor Jonathan Keros Inventor 94087 Sunnyvale, California USA Lawn Way 974 (72) Inventor Koichi Yamada United States 95134 San Jose, California, Elan Village Lane 371, Number 116

Claims (1)

[Claims] 1. A software-based method of accessing a page table, comprising: a virtual memory page address versus a physical memory page page.
Generating an address translation; executing a first hardware configuration instruction to translate the virtual memory page address into an index that references an entry in the page table; Executing instructions of the second hardware configuration to be translated; and virtual memory page address versus physical memory page page.
Storing the address translation and the tag in an entry of the page table referenced by the index.