Patent Description:
TLBs are specialized cache structures at a computing device for optimizing the translation of virtual memory addresses to physical memory addresses in systems using segmented or virtual memory. In such systems, each process addresses its memory space using virtual addresses, which are separate from the physical addresses of the actual memory locations storing the process data. Entries of the mapping from virtual addresses to physical addresses are stored in the TLB by caching entries from a page table. A TLB stores frequently used entries to avoid having to access the page table for each address translation in order to improve translation performance. In some examples, the entry may be moved while stored in the TLB, and the TLB entry can become invalid. In this example, the computing device can perform a TLB invalidation procedure to remove the entry from the TLB, which may increase the efficiency of the TLB. However, in some instances, such as the case when the entry is not present in a large TLB, the computing device searches through the entire large TLB structure to determine that the entry is not present, which can increase power consumption and inefficiency. <CIT> deals with determining whether to perform a translation lookaside buffer, TLB, invalidation procedure using sticky bits that indicate whether entries corresponding to a context are stored in the TLB.

This specification describes how a system can determine whether to perform a translation lookaside buffer (TLB) invalidation procedure for TLB entries associated with an application based on a non-address characteristic of TLB entries. The non-address characteristic can be an identifier of the application itself, e.g., an application space identifier (ASID) of the application; or a virtual machine identifier (VMID) for the application. For example, the system can pass an ASID through multiple Bloom filters to determine whether the TLB lacks entries for that ASID. If so, the system need not scan the TLB to invalidate such entries, which reduces the overhead of TLB invalidation procedures. When examples below discuss using the ASID of an application, the same techniques can be used for any other appropriate characteristic of virtual addresses or their corresponding TLB entries, e.g., a VMID.

The system described in this specification can allow a computing device to determine whether to perform a TLB invalidation procedure by using Bloom filters with an ASID. In conventional systems that perform such TLB invalidation procedures, a computing device receives an instruction from another computing device to remove an application space identifier associated with multiple virtual addresses. The computing device can remove any entry associated with the application space identifier by walking through the cache structure of the TLB. However, virtual addresses for that ASID may not actually be included in the TLB, and the computing device may delay other functions by searching for an entry that is not present. For example, the computing device might have to walk through the entire cache structure of the TLB to search for the one or more entries associated with the application space identifier, which can require many cycles.

The performance impact on performing needless TLBI procedures increases with cache size. For relatively small cache sizes, e.g., <NUM>-entry cache structuresa computing device may be able to determine whether an entry is present in the TLB in a single cycle, due to the relatively small number of entries.

However, larger cache structures, such as a Level <NUM> (L2) cache, can contain a relatively larger number of entries and might not be fully associative. In this case, the computing device cannot scan the L2 cache structure in a single cycle to find the entry. The computing device must scan the L2 cache structure over multiple cycles. For example, the L2 cache structure can be a set associative structure with <NUM> entries. The cache structure is divided into multiple sets containing multiple entries (e.g., <NUM> sets with <NUM> entries per set). The computing device can scan one set at a time, and the computing device takes multiple cycles to scan each set in the entirety of the cache structure. The inability to search for an entry in a single cycle delays the TLB invalidation procedure and other procedures at the computing device, even if the entry is not present in the L2 cache structure.

In contrast, the system described in this specification need not scan the entire cache structure on every invalidation request to determine whether or not the requested entry is represented in the cache. The systems and techniques described in this specification can allow a computing device to quickly determine whether to skip or perform the TLB invalidation procedure. The computing device uses multiple Bloom filters corresponding to multiple hash functions to determine whether entries of an application space identifier (ASID) are represented in the TLB. Based on whether the entry is represented according to values given by the multiple Bloom filters, the computing device can walk through the cache structure in search of the entry or can bypass the TLB invalidation procedure entirely, which can decrease the delay associated with performing the TLB invalidation procedure and conserve computational resources of the computing device.

Additionally, using an ASID to scan the TLB is more efficient than using virtual addresses. The computing device may have to scan each set in search of a virtual address to perform the invalidation procedure, while using an ASID, the computing device might not need to scan each set.

In some implementations, the computing device maintains the multiple Bloom filters using a respective hash function for each Bloom filter. The computing device is configured to add the entries present in the TLB to the Bloom filter using the respective hash functions to set a hash value. The computing device can scan the Bloom filter for a requested entry using the respective hash function. The computing device can determine whether the requested entry is not represented in the TLB if the requested entry is not represented in the Bloom filter, or whether the requested entry is potentially present in the TLB if the requested entry is represented in the Bloom filter. The computing device is configured to bypass the TLB invalidation procedure if the computing device determines that the requested entry is not represented in the TLB based on the Bloom filter. By bypassing the TLB invalidation procedure, the computing device reduces the number of cache structure searches and cycles, which can lead to greater TLB efficiency and greater overall system performance.

<FIG> shows an example system <NUM>. The system <NUM> is an example of a system in which the systems, components, and techniques described below are implemented.

The system <NUM> is configured to determine whether to perform a TLB invalidation procedure for an application space identifier (ASID) or another non-address characteristic of a virtual address, e.g., a virtual machine identifiers (e.g., VMIDs).

The system <NUM> includes multiple computing devices <NUM> and a main memory <NUM>. The multiple computing devices <NUM> can send ASIDs <NUM> to each other to perform memory operations. Each computing device <NUM> can be coupled to the main memory <NUM>.

Each computing device <NUM> can process ASIDs <NUM>, which can be encountered during normal operation of storing virtual address translation mappings, or from another computing device <NUM>, which each computing device can interpret to as a request to invalidate TLB entries associated with that ASID.

The TLB <NUM> is an example of a special purpose cache that is used in virtual address translation. The TLB <NUM> stores mappings from virtual memory addresses to physical memory addresses by caching entries.

When the computing device <NUM> receives an ASID <NUM> from another computing device, the computing device <NUM> can seek to invalidate all virtual address entries in the TLB associated with the ASID <NUM>.

The TLB <NUM> includes storage for TLB entries <NUM> that each store mappings of virtual addresses to physical addresses in the main memory <NUM>. The TLB <NUM> also includes a set of hash functions <NUM> and a set of Bloom filters <NUM>. A Bloom filter <NUM> is a data structure that can be used to determine whether an element is not present in a set. In this example, the computing device <NUM> can use the Bloom filters <NUM> to determine whether an entry is not represented in the TLB <NUM> based on its ASID. The computing device <NUM> can set the values of the Bloom filters <NUM> using hash functions <NUM>.

The hash functions <NUM> can be implemented in logic circuitry that is configured to generate a hash value from an input. The logic circuitry of the hash functions <NUM> can implement a function that produces output values that are all the same number of bits. For example, the computing device <NUM> can input an ASID value into a hash function <NUM> to obtain a corresponding hash value. The computing device <NUM> can then set the hash value for a corresponding Bloom filter <NUM>, a process that is described in further detail below with reference to <FIG>.

In this example, the computing device <NUM> is configured to access the TLB <NUM> and to use Bloom filters <NUM> to determine whether to perform a TLB invalidation procedure for a particular ASID. The computing device <NUM> can populate the Bloom filters <NUM> using the set of hash functions <NUM> as TLB entries <NUM> are added during normal operation. The computing device <NUM> can for example generate a hash value of the ASID of each of the entries <NUM>, either before or after they are cached, and can set the hash values of the entries <NUM> by updating the corresponding values in each of the Bloom filters <NUM>. Therefore, the Bloom filters <NUM> include data that represents all of the ASIDs of the entries <NUM> that are cached in the TLB <NUM>.

Regardless of the implementation, when the computing device <NUM> receives an invalidation request <NUM>, the computing device <NUM> can consult the TLB <NUM> to determine if the TLB <NUM> stores a mapping for the particular virtual address associated with the ASID <NUM> indicated by the invalidation request <NUM>.

In this example, the computing device <NUM> can receive the invalidation request <NUM> from another computing device <NUM>. The invalidation request <NUM> can include a request to perform a TLB invalidation procedure, e.g., using TLB invalidation logic <NUM> that invalidates cached TLB entries with an ASID indicated by the request <NUM>.

The computing device <NUM> generates multiple hash values from the multiple hash functions <NUM> that correspond respectively to each of the Bloom filters <NUM>. In some implementations, the computing device <NUM> determines if the TLB <NUM> stores a mapping for the entries associated with the ASID <NUM> by checking the hash values with their corresponding Bloom filters <NUM>. The computing device <NUM> uses the multiple hash functions <NUM> to generate respective hash values from the ASID <NUM>. The computing device <NUM> can check the Bloom filters <NUM> using respective hash values of the multiple hash functions <NUM> to determine whether to bypass searching for entries having the ASID <NUM>.

If the computing device <NUM> determines that each hash value of the respective hash values is represented in each Bloom filter <NUM>, the computing device <NUM> can perform the TLB invalidation procedure <NUM>, e.g., by searching through and invalidating all TLB entries having the associated ASID. If however the computing device <NUM> determines that any hash value of the respective hash values is not represented in its respective Bloom filter <NUM>, the computing device <NUM> can bypass performing the TLB invalidation procedure, which saves the computing device <NUM> from having to search for any TLB entries having the associated ASID. This process is described in further detail with reference to <FIG>.

<FIG> is a flow diagram of an example process for determining whether to perform the TLBI procedure. For convenience, the process <NUM> will be described as being performed by a computing device, , e.g., the computing device <NUM> of <FIG>, appropriately configured in accordance with this specification.

The computing device receives a request to perform the TLB invalidation procedure (<NUM>). The request can include an instruction received from another computing device to remove the entries associated with an ASID.

The computing device <NUM> maintains multiple Bloom filters that correspond to multiple hash functions (<NUM>) by performing fill operations.

The computing device can perform fill operations of the Bloom filters by providing an ASID as input to each of the multiple hash functions. The computing device can initialize a Bloom filter by initializing a vector that includes a set of values (e.g., values of zero). The computing device generates a set of multiple hash values for the ASID. For example, as shown above in reference to Table <NUM>, the computing device can use two Bloom filters with two corresponding hash vectors. The computing device can input an ASID into a first hash function that corresponds to a first Bloom filter and into a second hash function that corresponds to a second Bloom filter located in the TLB. In this example, the ASID value is <NUM>'hEF54. The hash value output of the first hash function in this example is a <NUM>-bit value, <NUM>, representing a location in Hash Vector <NUM>. A three-bit value representing the decimal value <NUM> can be expressed as <NUM>'d5. In this example, <NUM> represents the 5th most significant bit from right to left in TABLE <NUM>. In other words, Hash1(ASID) = <NUM>. The hash value output of the second hash function is a three-bit value representing <NUM>, e.g., Hash2(ASID) = <NUM>'d6. In this example, the hash functions compress the original <NUM>-bit ASID value into a <NUM>-bit value that represents a location in a hash vector of a Bloom filter.

The computing device performs the first fill operation (Fill <NUM>) on each of the Bloom filters using the hash value outputs. The computing device sets the corresponding bit of each Bloom filter in accordance with the hash value outputs and the bit location, as shown above in Table <NUM>. In this example, only <NUM> bit locations are shown, but in practice, each of the Bloom filters can include any appropriate number of bit locations, e.g., <NUM>, <NUM>, <NUM>, or <NUM>, to name just a few examples.

In some implementations, the computing device performs multiple fill operations. For example, the computing device can input a second ASID value (ASID = <NUM>'h9988) into the first hash function (Hash <NUM>(ASID) = <NUM>'d4)) and the second hash function (Hash <NUM>(ASID) = <NUM>'d2).

The computing device performs a second fill operation (Fill <NUM>) using the second hash value outputs. The computing device sets the corresponding bits of the Bloom filters in accordance with the hash value outputs, as shown above. In some examples, the corresponding bits are already set in the Bloom filter, as seen in the second Bloom filter above corresponding to the second hash function. Therefore, the Bloom filters can depict which of the entries are not present in the TLB.

The computing device provides the ASID included in the TLB invalidation request to the multiple hash functions to obtain the respective hash values of the ASID (<NUM>). The computing device may input the ASID value to multiple hash functions to determine the hash value that may be present in the Bloom filter corresponding to the respective hash function.

The computing device determines whether any hash value representing the ASID value is not represented in a Bloom filter of the multiple Bloom filters (<NUM>) by performing lookup operations. For example, the computing device can receive an ASID value of <NUM>'h9988, and the computing device can input the ASID value into the first hash function (Hash <NUM>(ASID) = <NUM>'d4) and the second hash function (Hash <NUM>(ASID) = <NUM>'d2).

The computing device can perform the lookup operation (e.g., search through each of the Bloom filters) to determine whether the hash values (e.g., hash value outputs) are present in any of the corresponding Bloom filters by determining if the bit indicated by each of the hash values is enabled in the Bloom filters. For example, the computing device searches for <NUM>'d4 in the first Bloom filter and <NUM>'d2 in the second Bloom filter. In this example, the computing device determines that neither of the hash values are present in either of the two Bloom filters, and therefore, the ASID is guaranteed to not be present in the TLB structure.

As a result, the computing device can bypass performing the TLB invalidation procedure of the requested ASID (<NUM>).

In another example, the computing device performs the lookup operation and determines that both of the hash values are present in both of the Bloom filters. The computing device therefore determines the ASID may be present in the TLB structure.

As a result, the computing device performs the TLB invalidation procedure (<NUM>).

<FIG> is a flow diagram of an example process for performing the TLB invalidation procedure. For convenience, the process <NUM> will be described as being performed by a system of one or more computers located in one or more locations. For example, a computing device system, e.g., the system <NUM> of <FIG>, appropriately programmed in accordance with this specification, can perform the process <NUM>.

The computing device is configured to receive a second request with a second ASID (step <NUM>). The request includes an instruction received from another computing device to remove the entries associated with the second ASID.

The computing device <NUM> provides the second ASID as input to each of the multiple hash functions to obtain a second set of multiple hash values (<NUM>). For example, the computing device can receive an ASID value of <NUM>'h443D, and the computing device can input the ASID value into the first hash function (Hash <NUM>(ASID) = <NUM>'d5) and the second hash function (Hash <NUM>(ASID) = <NUM>'d6).

In this implementation, the computing device <NUM> determines that all the hash values of the second set of multiple hash values are represented in the multiple Bloom filters (<NUM>). For example, with reference to Table <NUM>, the computing device can search through each of the Bloom filters to determine whether the hash values of <NUM>'d5 and <NUM>'d6 are present in any of the Bloom filters by determining if the bit indicated by each of the hash values is enabled in the Bloom filters. In this example, the computing device determines that both of the hash values are present in both of the Bloom filters, and therefore, the ASID may be present in the TLB structure.

As a result, the computing device performs the TLB invalidation procedure and walks the TLB to invalidate entries belonging to the second ASID (<NUM>).

<FIG> is a flow diagram of an example process for determining whether to reinitialize a Bloom filter. For convenience, the process <NUM> will be described as being performed by a computing device, e.g., the computing device <NUM>, of <FIG>, appropriately configured in accordance with this specification.

The computing device can oversaturate the Bloom filters by performing fill operations, which can result in false positive instances. False positive instances are instances in which an ASID is not associated with any entries in the TLB, and the computing device determines that the hash value is represented in the Bloom filter (e.g., the computing device wrongly characterizes that the entry is represented in the TLB).

For example, the computing device can receive an ASID value of <NUM>'h1122, and the computing device can input the ASID value into the first hash function (Hash <NUM>(ASID) = <NUM>'d4) and the second hash function (Hash <NUM>(ASID) = <NUM>'d6). The computing device can search through each of the Bloom filters in Table <NUM> to determine whether the corresponding hash values of <NUM>'d4 and <NUM>'d6 are present in any of the Bloom filters by determining if the bit indicated by each of the hash values is enabled in the Bloom filters. In this example, with reference to Table <NUM>, the computing device determines that both of the hash values are present in both of the Bloom filters, and therefore, the ASID may possible be present in the TLB structure. As a result, the computing device performs the TLB invalidation procedure. However, the ASID value was not set in the Bloom filters as part of the fill operations described in <FIG>, and therefore, this instance is a false positive instance. In some examples, the computing device can set most of bits in the Bloom filter (e.g., utilize a majority of the Bloom filter), which can result in the computing device determining than an entry is present in the TLB, when in actuality, the entry is not present.

To reduce the false positive instances, the computing device can determine a performance metric of a Bloom filter based on a threshold number of false positive instances (<NUM>).

The computing device is configured to disable a Bloom filter based on the performance metric of the Bloom filter failing to satisfy a threshold of false positive instances (<NUM>). The computing device can be configured with the threshold by another computing device. For example, the computing device can determine to disable the first Bloom filter associated with Hash <NUM> shown in Table <NUM> if the first Bloom filter exceeds a number of false positive instances.

The computing device can use the other Bloom filters that are not disabled to determine if an entry is in the TLB. The computing device determines if any hash value is not represented in a non-disabled Bloom filter of the multiple Bloom filters (<NUM>). For example, the computing device can continue to use the second Bloom filter associated with Hash <NUM> shown in Table <NUM>. In this example, the computing device can determine a hash value of an ASID using the second hash function, and the computing device can determine whether the hash value is present in the second Bloom filter.

If any hash value is not represented in any non-disabled Bloom filter, the computing device can bypass performing the TLB invalidation procedure (<NUM>). For example, if the computing device determines that the hash value is not present in the second Bloom filter, the computing device determines that the ASID is not present in the TLB, and the computing device can bypass the TLB invalidation procedure.

If any hash value is represented in any of the non-disabled Bloom filters, the computing device can perform the TLB invalidation procedure (<NUM>). For example, if the computing device determines that the hash value is present in the second Bloom filter, the computing device determines that the ASID may be present in the TLB, and the computing device performs the TLB invalidation procedure.

Additionally, if the computing device determines that any hash value is represented in any of the non-disabled Bloom filters, the computing device can generate at least one other Bloom filter and a corresponding hash function (<NUM>). For example, if the computing device determines to perform the TLB invalidation procedure based on the hash value being present in the second Bloom filter, the computing device can reinitialize a Bloom filter and a hash function to replace the first Bloom filter and the first hash function. In another example, the computing device can additionally reinitialize another Bloom filter and another hash function to replace the second Bloom filter and the second hash function.

A program can be stored in a portion of a file that holds other programs or data, e.g., one or more scripts stored in a markup language document, in a single file dedicated to the program in question, or in multiple coordinated files, e.g., files that store one or more modules, sub-programs, or porions of code.

The processes and logic flows described in this specification can be performed by one or more programmable computing devices executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by special purpose logic circuitry, e.g., an FPGA or an ASIC, or by a combination of special purpose logic circuitry and one or more programmed computing devices.

Computing devices suitable for the execution of a computer program can be based on general or special purpose microprocessors or both, or any other kind of central processing unit. The essential elements of a computing device are a processing unit for performing or executing instructions and one or more memory devices for storing instructions and data. The computing devices and the memory can be supplemented by, or incorporated in, special purpose logic circuitry. A computing device can also be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto-optical disks, or optical disks. However, a computing device need not have such devices. Moreover, a computing device can be embedded in another device, e.g., a mobile telephone, a personal digital assistant (PDA), a mobile audio or video player, a game console, a Global Positioning System (GPS) receiver, or a portable storage device, e.g., a universal serial bus (USB) flash drive, to name just a few.

Embodiment <NUM> is a method comprising:.

Embodiment <NUM> is the method of embodiment <NUM>, wherein bypassing performing the TLB invalidation procedure comprises bypassing walking entries of the TLB to search for entries having the application space identifier.

Embodiment <NUM> is the method of any one of embodiments <NUM>-<NUM>, further comprising:.

Embodiment <NUM> is the method of any one of embodiments <NUM>-<NUM>, wherein the application space identifier represents an application executing on the computing device using the plurality of virtual addresses.

Embodiment <NUM> is the method of any one of embodiments <NUM>-<NUM>, wherein providing the application space identifier as input to each of the plurality of hash functions to obtain a plurality of hash values comprises, for each application space identifier:.

Embodiment <NUM> is the method of any one of embodiments <NUM>-<NUM>, wherein maintaining a plurality of Bloom filters, for each Bloom filter:
determining a performance metric of the Bloom filter, wherein the performance metric is based at least in part on a threshold number of false positive instances.

Embodiment <NUM> is the method of embodiment <NUM>, further comprising:
disabling the Bloom filter based at least in part on the performance metric failing to satisfy the threshold number of false positive instances.

Embodiment <NUM> is the method of embodiment <NUM>, wherein false positive instances are instances in which an application space identifier is not associated with any entries in the TLB, and the computing device determines that the hash value is represented in the Bloom filter.

Embodiment <NUM> is the method of embodiment <NUM>, wherein walking the TLB to invalidate entries belonging to the second application space identifier further comprises:
walking the TLB to invalidate entries based at least in part on the application space identifier being represented in at least one of non-disabled Bloom filters of the plurality of Bloom filters.

Embodiment <NUM> is the method of embodiment <NUM>, further comprising:
generating a Bloom filter and a corresponding hash function based at least in part on disabling the Bloom filter and performing the TLB invalidation procedure.

Embodiment <NUM> is a computing device configured to perform the operations of any one of embodiments <NUM>-<NUM>.

Claim 1:
A method performed by a computing device for determining whether to perform a translation lookaside buffer, TLB, invalidation procedure, the method comprising:
receiving a request to perform the TLB invalidation procedure, wherein the request specifies an application space identifier for a plurality of virtual addresses;
maintaining a plurality of Bloom filters, wherein each Bloom filter of the plurality of Bloom filters corresponds to a respective hash function of a plurality of hash functions;
providing the application space identifier as input to each of the plurality of hash functions to obtain a plurality of hash values;
determining that one of the hash values is not represented in one of the Bloom filters; and
in response, bypassing performing the TLB invalidation procedure.