Address translation table synchronization

A system, method and computer-readable medium for updating an address translation table. In the method, a message indicating a physical memory location that corresponds to a virtual address is received from a processor. An I/O Memory Management Unit (IOMMU) is used to update an entry within the address translation table corresponding to the virtual address according to the indicated physical memory location.

BACKGROUND

Translation tables are used in computing systems to provide an interface between a device, such as an Input/Output (I/O) device, and the central core of the computing system. For example, an I/O device may be assigned a set of virtual addresses it may use for accessing resources provided by the computing system. The virtual addresses are independent of the actual, physical memory locations of the resources in the computing system. In such a manner, the I/O device does not need to be updated any time there is a change within the computing system. Instead, when the I/O device requests to access a particular resource, it simply presents the assigned virtual address in its request. An I/O Memory Management Unit (IOMMU) receives the request from the I/O device and translates the virtual address into the physical memory location of the resource.

To accomplish this task, the IOMMU uses one or more address translation tables. An address translation table stores entries that provide a location of a physical memory page. The tables are indexed using high-order bits of the virtual address from the I/O device. Thus, when the request to access a system resource is received, the IOMMU can access the appropriate entry in the address translation table to complete the request. Address translation tables are maintained by a processor of the computer system. That is, the processor has read and write access to the translation table, while the IOMMU and any other devices that use the table, if present, have only read access.

Address translation tables can be very large, and are typically constructed as a series of tables arranged in a tree format. In this tree format, an entry in a table may point to another table, which in turn may point to another table, and so on, until a “leaf” level is reached. The leaf level is the point in the tree at which the appropriate physical memory location, or a pointer to the location, is stored. The process of following these pointers to the leaf level, called “walking” the tree, takes up valuable processing time due to the complexity involved with the process of walking through all of the necessary levels of the tree to reach the appropriate leaf level, particularly if the table is very large. Because some physical memory locations are accessed repeatedly, a cache is typically used to store entries for such frequently-accessed locations. Thus, upon receiving an I/O device request to access a computer resource, the IOMMU first checks the cache to determine whether an entry corresponding to the requested virtual address is present. If the entry is present, the IOMMU acquires the physical memory location from the cache entry, thereby avoiding walking the tree. If the entry is not present, the IOMMU walks the tree to find the appropriate entry and, upon finding the entry, uses the physical address to complete the access and may also create a cache entry to avoid walking the tree in the future.

Sometimes the physical memory location that is associated with virtual address is changed. In such a situation, the address translation table entry that associates the virtual address with the old physical memory location is changed to point to the new physical memory location. Because, conventionally, the processor is the only component that is permitted to write to an address translation table, the processor makes the change to the appropriate entry. If the entry has been stored in a cache, the processor generates a message containing a virtual address or a range of virtual addresses corresponding to the entry to the IOMMU, and an indication that the cache entry must be deleted. The IOMMU then flushes the indicated entry from the cache. When a request is subsequently received for the virtual address, the IOMMU will check the cache, find that the entry is not present, and then walk the address translation table to find the entry. The IOMMU may also save the new entry to the cache.

There are several shortcomings associated with the conventional mechanism for handling address translation tables. For example, because the IOMMU is only able to read from an address translation table, the information the IOMMU is able to provide to other components is limited to that which is provided by the processor. In some situations, it may be useful to store additional information in the address translation table that the IOMMU could use for performance tracking and other purposes. Because the processor maintains the tables, however, the IOMMU is not able to do this because the processor and the IOMMU are not in the same coherency domain. That is, any changes made by the IOMMU could result in a conflict with those made by the processor, which could cause serious faults in the system. Having the processor maintain such additional information would unduly burden the processor with additional workload and adversely affect system performance.

In addition, the conventional update mechanism is inefficient. For example, when the processor sends a message to the IOMMU indicating that a cache entry has been changed, the processor only provides sufficient information for the IOMMU to delete the cache entry. The IOMMU must then walk through the address translation table the next time the virtual address associated with the entry is presented, which is time consuming. In addition, if a cache entry of the new address is desired, the IOMMU must create a new cache entry in an operation that is separate from the cache entry delete operation.

SUMMARY

An embodiment of the present invention provides a system, method and computer-readable medium for maintaining an address translation table using an IOMMU. In such an embodiment, upon a change to one or more physical memory locations that are associated with an entry in an address translation table, the processor passes a message to the IOMMU. The message identifies the affected entry and a new physical memory location associated with the entry. The IOMMU then updates the entry in the address translation table and a corresponding entry in a cache, if present.

If the changed physical memory location necessitates a change to a branch of the address translation table's tree structure, the processor prepares a new branch prior to sending the message to the IOMMU. The message may include the new physical memory location and a first pointer for the new branch. The IOMMU then updates the corresponding cache entry, if present, with the new physical memory location, and a first entry in the address translation table with the first pointer to the new branch. In such a manner, the old branch is bypassed and the new branch is added to the address translation table.

DETAILED DESCRIPTION

Example Computing Environment

FIG. 1illustrates example computing system environment100in which aspects of the invention may be implemented. Computing environment100may correspond to, for example, a Northbridge/Southbridge chipset computer architecture in which split-transaction semantics are enabled. However, the computing environment100is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention. Neither should computing environment100be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the example computing environment100.

Processor110may be a programmable logic device that performs instruction, logic and mathematical processing. Processor110is operatively connected to chipset120. Chipset120is a collection of microchips that perform functions in support of processor110. For example, chipset120may include memory bridge122and I/O bridge124. Memory bridge122communicates with processor110and controls interaction with memory150and Accelerated Graphics Port (AGP)130activities. Memory bridge122includes IOMMU126, which intercepts memory accesses from I/O devices (e.g., devices and buses that are operatively connected to I/O bridge124) so as to translate virtual addresses into the appropriate memory location. IOMMU126may be configured in any manner. For example, instead of a single IOMMU126, memory bridge122may include a plurality of IOMMUs126, such as an IOMMU126that is dedicated to translating memory accesses from AGP130and a second IOMMU126that is dedicated to translating memory accesses from the I/O bridge124. Any such configuration is consistent with an embodiment. Memory150may include computer storage media in the form of volatile and/or non-volatile memory such as ROM and RAM. For example, RAM typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processor110.

I/O bridge124implements the relatively slower capabilities of computing environment100. As can be seen inFIG. 1, I/O bridge124is operatively connected to processor110by way of memory bridge122. A non-exhaustive listing of components that be implemented by I/O bridge124include hard disk drive140, switch142, USB and PCI buses, and I/O device160. Hard disk drive140provides storage of computer readable instructions, data structures, program modules and other data for computing environment100. Switch142enables I/O bridge124to communicate with a variety of I/O endpoints, such as mobile docking port144and Ethernet port146, for example. I/O bridge124may also implement a PCI or USB bus. In addition, I/O bridge124may implement any type of I/O Device160.

As noted above, computing environment100may reside within a variety of different types of computing devices. Accordingly, computing environment100may further include components, devices, and the like that are not illustrated inFIG. 1for clarity. Furthermore, some components that are illustrated separately inFIG. 1may, in fact, have their functionality implemented by a single hardware component. For example, the functions of switch142and I/O bridge124may be performed by a single component.

Example Embodiments

In the discussion that follows, it is assumed herein that one skilled in the art is familiar with processor code and the operation of I/O Memory Management Units (IOMMUs), and therefore details relating to such matters are omitted herein for clarity.FIG. 2Ais a diagram illustrating an environment in which an example mechanism for updating an address translation table in accordance with an embodiment may be implemented. As can be seen, processor110is in operative communications with I/O Memory Management Unit (IOMMU)126. Processor110communicates with IOMMU126using any type or format of inter-device communication. IOMMU126may be any type of hardware device or circuit that supports the use of virtual memory by providing a mechanism for translating a virtual address into a corresponding physical memory location.

Address translation table152is operatively connected to IOMMU126. Address translation table152may be part of memory150, for example, and contains at least one entry154that references physical memory location156associated with a virtual address (physical memory location156normally references a range of memory locations often referred to as a “page”). Entry154may indicate physical memory location156in any number of ways. For example, entry154may simply include physical memory location156itself, or may use some other method such as, for example, a pointer in the form of several high-order bits or the like, an offset, etc. The discussion herein refers to a “pointer” in its broadest sense, meaning any type of data construct that leads, using any mechanism, to a location of data.

Cache127is a store of physical memory locations156that may be referenced by way of their corresponding virtual address. Cache127may be any type of rapid-access memory structure such as, for example, an IOTLB. It will be appreciated that instead of storing the entire virtual address or physical memory location156, a hash or other type of compressed data shorthand mechanism may be employed. The format of the data stored may be the same as or different than that used in address translation table152. For example, address translation table may indicate physical memory location156using a pointer, while cache127may use some other means for indicating physical memory location156. In any event, cache127provides IOMMU126with a mechanism by which address translation table152need not be used to look up a physical memory location that corresponds to a particular virtual address. For example, the first time a particular virtual address is presented to IOMMU126(e.g., as part of a request from an I/O device or the like), a corresponding physical memory location156may not be present in cache127. As a result, IOMMU126must access address translation table152to locate physical memory location156. As will be discussed below in connection withFIGS. 3A-C, when entries154in address translation table152are arranged as a large tree, the processing time involved with walking through the tree to reach the appropriate physical memory location156may be substantial. Thus, in connection with returning a result, IOMMU126stores the ultimate physical memory location156(or a pointer to said location156, or the like). As a result, subsequent requests for the physical memory location156corresponding to the virtual address can be serviced quickly.

In an embodiment, IOMMU126is provided with write access to address translation table152, and processor110does not write to address translation table152. Such a configuration may be implemented using any type of hardware or software modification to processor110(to prevent it from modifying address translation table152) and IOMMU126(to enable it to modify address translation table152). For example, processor110code that carries out a write to address translation table152may be bypassed such that processor110no longer writes to address translation table126. A setting change or the like may be made to IOMMU126such that write access to address translation table126is enabled. Code or the like may be written for IOMMU126such that IOMMU126is able to write to address translation table152to update entries154. IOMMU126may also be programmed to store additional information in address translation table152such as, for example, performance information (e.g., use counts, record status, etc.) and the like.

FIG. 2Bis a diagram illustrating an example processor message according to an embodiment. In an embodiment, message112is generated by processor110and sent to IOMMU126when a physical memory location156corresponding to a particular virtual address or the like has been changed. Message112contains an virtual address identifier112a—which may be the virtual address itself or some other representation, such as a hash, pointer or the like—and a new value entry112bindicating the new physical memory location156. In such a manner, therefore, an embodiment provides IOMMU126with sufficient information to update cache127with new value112b. Thus, upon a subsequent request for the virtual address, IOMMU126will be able to avoid walking through address translation table152and will be able to simply access cache127. It will also be appreciated that by providing the new value112b, message112enables IOMMU126to update address translation table152. Although not shown inFIG. 2B, message112may also contain one or more additional entries or other fields. For example, message112may include an indication of the operation to be performed such as, for example, an indication that a new entry154needs to be created, that an existing entry is to be updated, or the like.

FIG. 2Cis a flowchart illustrating an example method300aof updating an address translation table according to an embodiment. References are also made toFIGS. 2A-Bas appropriate. At step310, an update message112from processor110is received by IOMMU126. In an embodiment, message112may be configured as indicated above in connection withFIG. 2B. In other embodiments message112may contain additional or alternate entries. For example, in an embodiment, message112may contain numerous virtual address112aand new value112bentries so as to enable a batch of memory locations to be updated using a single message112. In another embodiment, message112may have one virtual address112aand a series of physical memory locations in one or more entries112b, which can be used by IOMMU126to update a range of virtual addresses.

At step320, IOMMU126updates cache127with the new value represented by new value entry112b. Step320may simply involve clearing a pre-existing entry and entering the new value, or may involve any number of steps, depending on the particular configuration of cache127being used. It will be appreciated that step320may be skipped if no cache127entry exists for the given virtual address.

At step330, IOMMU126updates entry154of address translation table152with the new value represented by new value entry112b. It will be appreciated that in updating address translation table152IOMMU126may need to walk through the table152, as will be discussed below in connection withFIGS. 3A-C, to reach the appropriate entry to change. In one embodiment, steps320and330may be performed atomically.

At optional step340, IOMMU126may add, modify or delete additional data within address translation table152. For example, IOMMU126could include additional entries154within address translation table152that pertain to performance data and the like. Step340may take place in connection with steps310-330, or may be a stand-alone step that may be taken at any time.

FIG. 3Ais a diagram illustrating an environment in which an example mechanism for updating an address translation table in accordance with an embodiment may be implemented. In contrast to the environment ofFIG. 2A, discussed above, entry154of address translation table152does not lead directly to physical memory location156. Instead, entry154may contain a pointer that leads to another entry154awithin tree158. Tree158may correspond to a part (i.e., a “branch”) of address translation table152's tree structure of entries154-154a, or to the entire tree structure, for example. The structure of tree158is illustrated functionally, that is, the arrangement of entries154-154aof tree158is depicted to show the relationship between entries154-154awithin tree158. Furthermore, each entry154-154amay itself be a table or other data structure. Any type of pointer may be used such as, for example, high-order bits of entry154aor the like. Ultimately, by following the pointers—or “walking”—through entries154aof tree158, an example of which is illustrated as the series of arrows labeled A, physical memory location156may be located. For example, within the appropriate entry154aof the last level of tree158, a pointer may point to a physical page (e.g., physical memory location156) that is indexed by a byte offset within that page, for example. As noted above, cache127contains the ultimate physical memory location156(or a pointer to physical memory location156as noted above, or the like), thereby shortening the amount of time IOMMU126takes to obtain physical memory location156.

FIG. 3Billustrates a walk of a tree in greater detail. In an embodiment, the accessing of physical memory address156is broken down into successive steps. At each step, some number of high-order address bits are used to index (or “point”) to an entry154referenced by the previous level. Using 4 kb pages and 64-bit entries as an example, a page of memory may contain 512 entries so 9 bits of address may be used to index at each level. InFIG. 3B, therefore, pointer157of entry154points to pointer157aof entry154a′, as illustrated by arrow A. Likewise, pointer157aof entry154a′ points to pointer157bof entry154b′, and so on, until pointer157eof entry154e′ points to physical memory location156, which is located in entry154f′. It should be appreciated that the number of entries154-154f′ illustrated inFIG. 3Bis for purposes of explanation only, and any number of such entries154-154f′, may be used in connection with an embodiment.

FIG. 3Cis a flowchart illustrating an example method300bof updating address translation table152, according to an embodiment. References are also made toFIGS. 2B and 3Aas appropriate. In an embodiment, method300boccurs when a change to tree158needs to be made to reflect one or more changes to entries154aand/or physical memory location156. In such an embodiment, tree158is replaced by new tree158′. At step305, therefore, processor110prepares and stores new tree158′, which may include one or more new entries154a′ and/or physical memory location156′. The creation of new tree158′ by processor110is represented inFIG. 3Aby arrow B.

At step310, an update message112from processor110is received by IOMMU126. As was discussed above in connection withFIG. 2C, message112may be configured as indicated above in connection withFIG. 2B. In an embodiment, message112includes virtual address112aand new value entry112b. Once entry154is updated with the new value represented by new entry112b(to be discussed below), therefore, it will refer to entry154a′ of new tree158′ instead of entry154aof tree158, which is represented inFIG. 3Aby arrow C.

At step320, IOMMU126updates cache127with the new value represented by new value entry112b. Step320may simply involve clearing a pre-existing entry and entering the new value, or may involve any number of steps, depending on the particular configuration of cache127being used. At step330, IOMMU126updates entry154of address translation table152with the new value represented by new value entry112b.

It will be appreciated that method300bprovides a mechanism by which tree158may be updated to tree158′ in one operation (e.g., steps320-330). In such a manner, processor110may take as much time as necessary to create158′ (which may be done by creating an entirely new tree, or by using parts of tree158, for example), and then can send message112to IOMMU126to have the change over occur in one operation. It can be seen that, in an embodiment, IOMMU126need only update entry154with the new value contained in new value entry112bto switch from tree158to tree158′. Once the new value has been added to entry154, entry154points to tree158′ (as represented inFIG. 3Aby arrow C), and then any pointers in entries154a′ will ultimately lead to physical memory location156′. Such a mechanism provides a complete switch to new tree158′ and therefore may avoid deleterious coherency issues. Old tree158may be deleted, allowed to be overwritten, or the like.

As was the case in method300aofFIG. 2C, at optional step340, IOMMU126may add, modify or delete additional data within address translation table152. For example, IOMMU126could include additional entries154within address translation table152that pertain to performance data and the like. Step340may take place in connection with steps310-330, or may be a stand-alone step that may be taken at any time.

While the above examples involve updating existing entries and the like with new values, it should be appreciated that embodiments may involve the creation of entirely new entries154and/or trees158. For example, new virtual addresses or physical memory locations156may be created, which may necessitate new entries154and/or trees158. In an embodiment, all changes to address translation table152are run through IOMMU126in the manner described herein. In such an embodiment, other computer components—including processor110—are only allowed to read from address translation table152to avoid coherency problems. It will be appreciated that in typical computer systems, processor110may retain “permission” to write to any memory location, including address translation table152, because processors generally have access to all system resources. Nevertheless, in an embodiment, processor110should be instructed not to do so through processor code sequence changes and the like.