Method and apparatus for segregation of virtual address space

The invention relates generally to memory management in a computer system and more specifically to a method and apparatus for performing a memory access operation in a computer system.

In a computer system, instructions and data are stored in a memory device until they are needed. The memory device is organized according to an addressing scheme to allow the instructions and data to be located by specifying an address. However, while the memory device is organized into a plurality of physical addresses, it is often useful for a processor to consider the instructions and data to be organized according to a different addressing scheme, denoted by virtual addresses. The virtual addresses may be converted to physical addresses to allow the instructions and data to be accessed in the memory device.

A translation lookaside buffer (TLB) structure may be used to provide a cache for translation of virtual addresses to physical addresses. The TLB structure includes a plurality of page directories that contain page directory entries and a plurality of page tables that contain page table entries. The page directory entries serve as pointers to the plurality of page tables and the page table entries serve as pointers to pages of data in the memory device.

FIG. 6 is a block diagram illustrating the relationship between a processor, a TLB structure, and memory. Processor 601 is coupled to and communicates in virtual addresses with TLB structure 602 . TLB structure 602 is coupled to and communicates in physical addresses with memory device 603 .

FIG. 1 is a flow diagram illustrating a prior art process for obtaining data from a TLB structure. In step 101 , a page directory entry is read from a page directory. In step 102 , a page table entry is read from a page table using the page directory entry. In step 103 , data are read from a page in the memory device using the page table entry.

While a TLB structure is useful for caching virtual address-to-physical address translations, it is not readily compatible with a computer architecture that provides for the emulation of an emulated processor using a native processor. The native processor is the processor actually present in the system, while the emulated processor is a processor whose performance characteristics simulated by the native processor. The emulation allows execution on the native processor of software programmed to be executed on a processor of the same type as the emulated processor. However, software programmed to be executed on a processor of the same type as the emulated processor is subject to the constraints and conditions associated with that type of processor. For example, the emulated processor architecture may already use all of its address space thereby causing incompatibility with certain bookkeeping techniques commonly used with prior art TLBs. Thus, a method and apparatus is needed to allow efficient memory accesses given the constraints imposed by an emulated processor architecture.

FIG. 1 is a flow diagram illustrating a prior art process for obtaining data from a translation lookaside buffer structure.

FIG. 2 is a flow diagram illustrating a process for obtaining data from a translation lookaside buffer structure according to an embodiment of the invention.

FIG. 3 is a block diagram illustrating a memory map according to an embodiment of the invention.

FIG. 4 is a block diagram illustrating a virtual address with an address space tag according to an embodiment of the invention.

FIG. 5 is a block diagram illustrating a translation lookaside buffer structure for using an address space tag according to an embodiment of the invention.

FIG. 6 is a block diagram illustrating the relationship between a processor, a translation lookaside buffer structure, and memory.

FIG. 7 is a block diagram illustrating an example of a translation lookaside buffer structure.

The invention provides a method and apparatus for segregation of virtual address space in a computer system. An embodiment of the invention provides compatibility of an emulated processor architecture with a native processor architecture. Address space for the emulated processor architecture is provided and segregated from other address space, such as address space designated for use by a native processor, where the native processor is the processor actually present in a computer system. An embodiment of the invention provides separate exception handlers to handle translation lookaside buffer (TLB) misses for each address space. An embodiment of the invention provides an address space tag associated with a virtual address to designate the address space to which that virtual address pertains.

An embodiment of the invention is useful in a computer that does load or store instructions or executes instruction code fetches where the resulting memory access has a virtual address. An address space for the memory access may be implicitly or explicitly provided. A TLB structure matches the address space and virtual address to produce a physical address or, if no entry is present, an exception. By providing an address space tied to a memory access instruction and the TLB structure that matches it, this embodiment of the invention provides advantages not heretofore realized.

Optionally, memory accesses for one or more address spaces may bypass the TLB structure. Thus, use of the TLB structure may be made dependent upon the address space specified for the memory access.

In accordance with an embodiment of the invention, each address space may generate its own unique exception (i.e., each address space may have its own exception handler). Thus, a different mechanism is provided to handle exceptions for each address space.

Optionally, one or more address spaces may be protected so that instructions that are not privileged operating system instructions cause an exception. Thus, intentional or accidental memory accesses to an improper memory space are prevented and handled by an exception handler.

An embodiment of the invention provides for the emulation of a traditional page table structure (e.g., that of an x86 processor architecture) some or all of the above-described features and software exception handlers. As an example, a first address space may be used to emulate a full (e.g., 32-bit) traditional address space mapped by page tables where accesses to a first address in the first address space that miss in the TLB structure jump to a first software exception handler.

The first software exception handler generates a second address in a second address space derived from the first address in the first address space that missed (i.e., could not be found) in the TLB structure and attempts to read a page table entry from the second address in the second address space. In attempting to read a page table entry from the second address in the second address space, one of two things may occur. One possibility is that the second address in the second address space matches a translation lookaside buffer structure entry. If so, a page table entry is read from memory and placed in the TLB structure mapping the first address from the first address space to the page table entry. A second possibility is that the second address in the second address space doesn't match the TLB structure entry and the processor jumps to a second software exception handler.

In the latter case, the second software exception handler generates a third address in a third address space derived from the second address in the second address space that missed in the TLB structure and attempts to read a page table entry from the third address in the third address space. The attempt to read the page table entry from the third address in the third address space does not require reference to the TLB structure (i.e., the TLB structure is bypassed).

From the third address in the third address space, a page table entry is read from a memory device and placed in the TLB structure, mapping the second address from the second address space to the page table entry.

After a page table entry is read from memory and placed in the TLB structure mapping the first address from the first address space to the page table entry in accordance with the first possibility discussed above, then the access to the first address in the first address space is tried again and succeeds.

After a page table entry is read from a memory device and placed in the TLB structure mapping the second address from the second address space to the page table entry in accordance with the second possibility discussed above, then the access to the second address in the second address space is tried again and succeeds. Then a page table entry is read from memory and placed in the TLB structure, mapping the first address from the first address space to the page table entry. Then the access to the first address space is tried again and succeeds.

FIG. 2 is a flow diagram illustrating a process for obtaining data from a translation lookaside buffer structure according to an embodiment of the invention. The process begins in step 201 . In step 202 , the execution of an instruction involving a memory access operation begins. In step 203 , the memory access operation begins. A first virtual address and a first address space are generated. In step 204 , the TLB structure is checked to determine if a TLB entry exists that matches the first virtual address and the first address space to produce a physical address in a memory device. If a TLB entry exists, the process continues in step 205 . In step 205 , the data access is performed and the data are obtained from the memory device using the physical address. Following the successful data access, the remainder of the instruction is executed using the data obtained from the memory device and the process returns to step 202 to begin execution of another instruction.

If, in step 204 , a TLB miss occurs (i.e., no matching TLB is found in the TLB structure), the process continues in step 206 . In step 206 , the processor generates an exception and executes a first exception handler. In step 207 , a page table entry address is created identifying a second virtual address in a second address space. In step 208 , a memory access operation begins based on the second virtual address and the second address space. In step 209 , the TLB structure is checked to determine if a TLB entry exists that matches the second virtual address and the second address space to produce a physical address in the memory device. If a TLB entry exists, the process continues in step 210 . In step 210 , the page table entry identified by the page table entry address generated in step 207 is loaded from the memory device. In step 211 , the page table entry is placed in the TLB structure to map the first virtual address and the first address space to the physical address of the location in the memory device, and the process returns to step 203 . After step 203 , since the TLB entry is then present in the TLB structure, the process will continue to step 205 from step 204 , and the data will be successfully obtained from the memory device.

If, in step 209 , a TLB miss occurs, the process continues in step 212 . In step 212 , the processor generates an exception and executes a second exception handler. In step 213 , a page directory entry address is generated identifying a third virtual address and a third address space. In step 214 , the memory device is accessed based on the third virtual address and the third address space. The TLB structure need not be consulted for this memory access. In step 215 , the page directory entry specified according to step 213 is loaded from the memory device. In step 216 , the page directory entry is placed in the TLB structure to map the second virtual address and the second address space to the physical address of the location in the memory device, and the process returns to step 208 . After step 208 , since the TLB entry is then present in the TLB structure, the process will continue to step 210 from step 209 , and the page table entry will be successfully loaded from the memory device.

FIG. 3 is a block diagram illustrating a memory map according to an embodiment of the invention. In one example, the memory map provides multiple address spaces, each spanning four gigabytes (2 32 bytes) of virtual address space, based on the use of a 32-bit addressing scheme with an address space tag. Within the multiple address spaces, address space 303 is designated as normally-mapped address space. This address space may be used to implement the memory space normally used by a processor of the same type as the emulated processor.

Address space 302 is designated as emulator-mapped address space. This address space may be used to implement memory space for software executed by the native processor to control emulation of the emulated processor. This address space may be mapped using a page directory entry. According to one embodiment of the invention, different exception handlers are used to handle exceptions in address space 302 and address space 303 .

Address space 301 is designated as purely physically-mapped address space. The TLB structure need not be used for memory accesses to this address space. Thus, the TLB need not map virtual addresses to this address space.

Additionally, other address space may be defined, with segregation provided between it and existing address spaces. For example, page table entry address space may be defined to allow page tables to be virtually contiguous (i.e., contiguous within the page table entry address space). A separate exception handler may be provided to map virtual addresses within the page table entry address space.

FIG. 4 is a block diagram illustrating a virtual address with an address space tag according to an embodiment of the invention. While the desired address space may be identified in a memory access operation using a variety of techniques to specify, either implicitly or explicitly, which virtual address space should be used, one technique involves the use of an address space tag 401 associated with a virtual address 402 . Physical address 403 may be identified based on virtual address 402 and address space tag 401 . Unlike prior art schemes, address space tag 401 is not used to associate a virtual address with a particular process. Rather, address space tag 401 according to an embodiment of the invention allows differentiation between native processor address space, emulated processor address space, page table entry address space, unmapped address space, and any other address space that may be defined. Advantageously, this makes it possible to ensure that an emulated processor environment is provided with a similar configuration of address space as that provided for a processor of the same type as the emulated processor while still providing separate address space of the native processor and for other memory management uses.

FIG. 5 is a block diagram illustrating a translation lookaside buffer structure for using an address space tag according to an embodiment of the invention. Combined address space tag and virtual address 501 identifies page directory entry 502 in page directory 503 . Page directory entry 502 identifies page table entry 504 in page table 505 . Page table entry 504 identifies data 506 in page 507 . According to an embodiment of the invention, page directory 503 is defined within one address space, identified by a unique value of address space tag 401 , page table 505 is defined within another address space, identified by a different value of address space tag 401 , and page 507 is defined within yet another address space, identified by yet another value of address space tag 401 .

FIG. 7 is a block diagram illustrating an example of a translation lookaside buffer structure. The example shows the use of a TLB structure for accessing a cached translation of the 32-bit virtual address represented in hexadecimal as 0x12345678. The virtual address is divided into three parts. The first part comprises the most significant ten bits (bits 22 - 31 ). Since ten bits is not divisible into an integer number of hexadecimal digits, the boundaries between the hexadecimal digits change, giving the hexadecimal representation 0x048. The second part comprises ten bits (bits 12 - 21 ) of lesser significance than the ten most significant bits, but contiguous with the ten most significant bits. While these ten bits are also not divisible into an integer number of hexadecimal digits, since only the two most significant bits are truncated from the most significant hexadecimal digit of the second part, the hexadecimal representation of the second part remains 0x345. The third part comprises the twelve least significant bits (bits 0 - 11 ). Since these twelve bits are divisible into three hexadecimal digits, the hexadecimal representation for these twelve bits remains 0x678.

Page directory 701 begins at address AAAA. Applying the first part of the virtual address, denoted as 0x048, as an offset within page directory 701 yields an address AAAA+0x048 containing value BBBB. Value BBBB identifies the beginning of page table 703 . Applying four times the second part of the virtual address (i.e., the second part of the virtual address shifted to the left twice), denoted as 4·0x345, as an offset within page table 703 yields address BBBB+4·0x345 containing value CCCC. Value CCCC identifies the beginning of page 705 . Applying the third part of the virtual address, denoted as 0x678, as an offset within page 705 yields address CCCC+0x678 containing data 706 . Data 706 is the data stored at the physical address in the memory device that corresponds to the virtual address 0x12345678. Thus, the TLB structure provides caching of virtual address-to-physical address translations.

Thus, a method and apparatus for segregation of virtual address space in a computer system capable of providing compatibility of an emulated processor architecture with a native processor architecture has been provided.