Method, apparatus, and system for storing memory encryption realm key IDs

A method, apparatus, and system for storing memory encryption realm key IDs is disclosed. A method comprises accessing a memory ownership table with a physical address to determine a realm ID associated with the physical address, accessing a key ID association structure with the realm ID to determine a realm key IS associated with the realm ID, and initiating a memory transaction based on the realm key ID. Once retrieved, the realm key ID may be stored in a translation lookaside buffer.

FIELD

Aspects of the present disclosure relate generally to memory encryption, and more specifically to management of keys for memory encryption in systems utilizing virtualized computing devices.

BACKGROUND

Cryptography is used to keep a user's private data secure from unauthorized viewers by, for example, encrypting the user's data intended to be kept private, known as plaintext, into ciphertext that is incomprehensible to unauthorized viewers. The encoded ciphertext, which appears as gibberish, may then be securely stored and/or transmitted. Subsequently, when needed, the user or an authorized viewer may have the ciphertext decrypted back into plaintext. This encryption and decryption process allows a user to create and access private data in plaintext form while preventing unauthorized access to the private data when stored and/or transmitted in ciphertext form.

Encryption and decryption are conventionally performed by processing an input (plaintext or ciphertext, respectively) using a cryptographic key to generate a corresponding output (ciphertext or plaintext, respectively). A cryptographic system that uses the same key for both encryption and decryption is categorized as a symmetric cryptographic system. One popular symmetric cryptographic system is the Advanced Encryption Standard (AES), which is described in Federal Information Standards (FIPS) Publication 197.

Computing devices, and particularly virtualized computing devices (e.g., virtualized server environments), may allow a single physical computing platform to be shared by one or more entities, such as an application, process or virtual machine (VM), also referred to as “realms.” In a server class system, the total number of realms an exceed ten thousand.

Note that a single physical server, which may comprise multiple processor cores on multiple IC devices, is operated as a single platform. The physical platform supports a hypervisor program, which manages the operation of multiple realms on the physical platform. A particular realm managed by the hypervisor may be actively running on the physical platform or may be stored in a memory in a suspended state. An active realm may access multiple different memory types and/or locations, some of which may be accessible to other realms running on the platform (such as, for example, the hypervisor itself). A realm may also access the memory contents of another realm, or the memory contents of the hypervisor, provided that access control permits such accesses. To protect the confidentiality of each realm against physical attacks such as DRAM probing/snooping, a portion—up to the entirety—of the realm's contents may be encrypted. For effective security, each realm should use one or more unique (i.e., exclusive) cryptographic key(s). Systems and methods to manage keys for encryption and/or decryption of VM code and data may be useful.

It would thus be desirable to provide a mechanism to manage encryption keys in a manner that conserves system resources (such as system bus bandwidth) while performing associated memory transactions and limiting physical chip area.

SUMMARY

In one aspect, an apparatus comprises a realm management unit having a key ID association table indexed by a realm ID. The key ID association table is configured to associate a realm key ID with the realm ID, and to provide the associated realm key ID when looked up with the realm ID. The apparatus may further comprise a memory ownership table indexed by a physical address. The memory ownership table may be configured to associate a realm ID with a physical address, and to provide the associated realm ID to the realm management unit when looked up with the physical address.

In another aspect, a method comprises accessing a memory ownership table with a physical address to determine a realm ID associated with the physical address. The method further comprises accessing a key ID association structure with the realm ID to determine a realm key ID associated with the realm ID. The method further comprises initiating a memory transaction based on the realm key ID. The method may further comprise caching the realm key ID in a translation lookaside buffer.

In yet another aspect, an apparatus comprises means for realm management comprising a means for storing key ID associations indexed by a realm ID. The means for storing key ID associations is configured to associate a realm key ID with the realm ID, and to provide the associated realm key ID when looked up with the realm ID.

In yet another aspect, a non-transitory computer-readable medium comprises instruction which, when executed by a processor, cause the processor to access a memory ownership table with a physical address to determine a realm ID associated with the physical address. The instructions further cause the processor to access a key ID association structure with the realm ID to determine a realm key ID associated with the realm ID. The instructions further cause the processor to initiate a memory transaction based on the realm key ID.

In yet another aspect, an apparatus, comprises a processor, a memory system organized into pages, each of at least some pages being associated with a realm ID and encrypted with one of a plurality of keys identified by a realm key ID, a realm management unit having a key ID association table configured to associate a realm ID with a realm key ID, and wherein a page in memory is accessed using a realm key ID associated with the realm ID associated with the page.

DETAILED DESCRIPTION

Various embodiments are now described with reference to the drawings. In the following description, for purposes of explanation, specific details are set forth to provide a thorough understanding of one or more embodiments. It may be evident, however, that such embodiment(s) may be practiced without these specific details. Additionally, the term “component” as used herein may be one of the parts that make up a system, may be hardware, firmware, and/or software stored on a computer-readable medium, and may be divided into other components.

The following description provides examples, and is not limiting of the scope, applicability, or examples set forth in the claims. Changes may be made in the function and arrangement of elements discussed without departing from the scope of the disclosure. Various examples may omit, substitute, or add various procedures or components as appropriate. For instance, the methods described may be performed in an order different from that described, and various steps may be added, omitted, or combined. Also, features described with respect to some examples may be combined in other examples. Note that, for ease of reference and increased clarity, only one instance of multiple substantially identical elements may be individually labeled in the figures.

Embodiments of the present disclosure include systems wherein each VM runs within a corresponding protected software environment (PSE). The PSEs are managed by PSE management software. Note that cryptographic protection may be applied to any arbitrary software layer (e.g., firmware, hypervisor, VM/kernel, driver, application, process, sub-process, thread, etc.). Any such software may function inside of a PSE. The hypervisor would typically be the PSE management software for PSEs that encapsulate VMs, and the OS kernel would typically be the PSE management software for PSEs that encapsulate applications. In general, the PSE management software role would typically be fulfilled by the software running at the next-higher privilege level from the software contained within a PSE.

Embodiments of the present disclosure include systems and methods for the storage of a first plurality of cryptographic keys associated with a first plurality of corresponding PSEs (e.g. encapsulating virtual machines) supervised by PSE management software (e.g. a hypervisor) running on a computer system and configured to supervise a superset of the plurality of PSEs. The computer system stores currently unused keys of the superset in a relatively cheap, large, and slow memory (e.g., DDR SDRAM) in encrypted form and caches the keys of the first plurality in a relatively fast, small, and expensive memory (e.g., on-chip SRAM) in plaintext form. In one embodiment, in a computer system having a first processor, a first memory controller, and a first RAM, the first memory controller has a memory cryptography circuit connected between the first processor and the first RAM, the memory cryptography circuit has a keystore and a first cryptographic engine, and the keystore comprises a plurality of storage spaces configured to store a first plurality of cryptographic keys accessible by a key identifier (KID).

In some embodiments, a computer system comprising one or more processors and capable of parallel processing is configured to support the secure and simultaneous (that is, parallel) operation of a plurality of PSEs, wherein the plurality of PSEs has a corresponding plurality of cryptographic keys—in other words, each PSE is associated with a corresponding cryptographic key. In addition, the computer system has a random-access memory shared by the plurality of PSEs. The computer system has a memory cryptography circuit (MCC) connected between the one or more processors and the shared memory, where the MCC includes a cryptography engine and a keystore for storing a subset of the plurality of cryptographic keys. During data transmission operations between the processor and the shared memory (for example, in the fetching of processor instructions, data reads, and data writes), the cryptography engine encrypts or decrypts the transmitted data (for example, processor instructions) using a corresponding cryptographic key stored in the keystore. The implementation of the MCC in hardware or firmware and the caching of likely-to-be-used keys in the keystore helps to allow for the rapid and efficient execution of cryptographic operations on the transmitted data.

FIG.1is a simplified schematic diagram of a computer system100in accordance with one embodiment of the disclosure. Computer system100comprises a system on chip (SoC)101and one or more SoC-external random-access memory (RAM) modules102, which may be, for example, double data rate (DDR) synchronous dynamic RAM (SDRAM) or any other suitable RAM. The computer system100also comprises user interface103and network interface104. Note that, as would be appreciated by a person of ordinary skill in the art, the computer system100, as well as any of its components, may further include any suitable assortment of various additional components (not shown) whose description is not needed to understand the embodiment.

FIG.2is a simplified schematic diagram of a detailed portion of the computer system100ofFIG.1. The SoC101comprises one or more central processing unit (CPU) cores201, each of which may be a single-threaded or multi-threaded processor. Each CPU core201may include an L1 cache (not shown) and an L2 cache202. The SoC101further comprises one or more L3 caches203, one or more memory controllers204, one or more physical layer (PHY) interfaces205, and a system bus206. The SoC101further comprises a key management unit (KMU)207, which may be implemented as a discrete standalone module as shown, as a distributed module within two or more CPU cores201, or in any suitable manner. The system bus206interconnects the CPU cores201, L3 caches203, KMU207, and memory controllers204, along with any other peripheral devices which may be included within the SoC101.

The memory controller204comprises a bus interface208connected to the system bus206. The bus interface208is also connected, via a data path209a,to a memory cryptography (MC) circuit (MCC)209that is, in turn, connected to an optional error-correction-code (ECC) circuit210via a data path209b.Note that in alternative embodiments, the MCC209may connect to the PHY205without an intermediary ECC circuit. The memory controller204is communicatively coupled to a corresponding PHY interface205, which is, in turn, communicatively coupled to a corresponding external RAM module102.

The computer system100supports the management, by PSE management software, of a plurality of PSEs, where a subset of the plurality of PSEs may run simultaneously as parallel processes. The computer system100supports parallel processing by multiple CPU cores201. In some implementations, one or more of the CPU cores201may be configured to execute multiple threads in parallel. Note that in some alternative embodiments, the computer system100may have only one CPU core201, which, however, supports multi-threaded processing and, consequently, parallel processing. Further note that in some alternative embodiments, the computer system100may comprise two or more SoCs coherently connected through chip-to-chip interfaces to form a multi-socket system.

The computer system100may support an arbitrarily large number of PSEs, each associated with a unique cryptographic key, which allows for the secure sharing of RAM modules102by the CPU cores201and allows the PSEs to operate securely from snooping by other processes such as, for example, other PSEs, the PSE management software, and attackers with physical access to the computer system100(e.g., physical attackers). The SoC101may be designed to use time-slicing to support an almost-simultaneous execution of a number of PSEs that is greater than the number of parallel processes supportable by the SoC101on the corresponding CPU cores201, but lesser than the arbitrarily large total number of PSEs supportable by the computer system100. As will be explained in greater detail below, the KMU207stores and manages the cryptographic keys and corresponding KIDs for the PSEs supported by the computer system100.

As will be explained in greater detail below, in operation, when a first PSE running on a first CPU core201needs to write a data block to a RAM102, the data block is encrypted by the MC circuit209using a first cryptographic key uniquely corresponding to the first PSE. The corresponding encrypted data block is then written to a first RAM module102. When the first PSE needs to read a data block from RAM module102, the data block, which is encrypted on the RAM module102, is decrypted by the MC circuit209using the first cryptographic key and the corresponding decrypted data block is then transmitted to the CPU core201on which the first PSE is running. Note that writing to and reading from RAM modules102may be performed as part of routine instruction execution by CPU cores201.

FIG.3is a simplified schematic diagram of the memory cryptography circuit209ofFIG.2. MC circuit209comprises an encryption engine301, a decryption engine302, a keystore303, and an arbiter304. The encryption engine301and the decryption engine302are two different types of cryptographic engines. The encryption engine301is a circuit configured to receive a block of plaintext and a cryptographic key, encrypt the plaintext with the cryptographic key using an encryption algorithm such as, for example, AES using an appropriate cipher mode of operation, and output a corresponding block of ciphertext. The decryption engine302is a circuit configured to receive a block of ciphertext and a cryptographic key, decrypt the ciphertext with the cryptographic key using a decryption algorithm such as, for example, AES using an appropriate cipher mode of operation, and output a corresponding block of plaintext. The keystore303may be a SRAM, register file, or similarly fast-access RAM configured to addressably store and update a plurality of cryptographic keys.

The keystore303is configured to receive a KID from the arbiter304. In response to receiving a KID, the keystore303is configured to output the cryptographic key stored at the keystore address indicated by the KID. The output of the keystore303is connected to the cryptographic engines301and302. The keystore303is also configured to receive, for storage, cryptographic keys from the Key Management Unit (KMU)207via the configuration interface. The KMU207, via the configuration interface, provides, for example, a 256-bit cryptographic key and, via the arbiter304, a corresponding KID. In response, the keystore303stores the received cryptographic key at the keystore address indicated by the KID.

The arbiter304is configured to receive a KID (i) from the CPU core201via the path209a,and (ii) from the KMU207via the path209a.Note that for both read and write requests, the KID is received from the CPU core201. The KID is carried on the system bus206and may also be stored in the caches, where each cache lines carries the KID along with a memory address and data. Write requests from the CPU core201include plaintext data and the KID corresponding to the PSE running on the CPU core201. Read requests from the CPU core201include a memory address and the PSE-corresponding KID. In response to the read request, the KID, or the corresponding key from the keystore303, may be buffered by the MC circuit209until the ciphertext block located at the requested memory address is retrieved from the RAM102, at which point, if the KID is buffered, then the KID is used to retrieve the corresponding key from the keystore303. The ciphertext block and the key are then provided to the decryption engine302.

The arbiter304multiplexes its KID inputs into one KID output provided to a KID input of the keystore303. These arbiter304inputs may be referred to as, (i) memory write path, (ii) memory read-request path, and (iii) configuration interface path. The arbiter304may be configured to arbitrate among colliding KID inputs that are substantially simultaneously received based on, for example, assigned priority. In one implementation, KIDs associated with reads retrieved from the RAM module102are given the highest priority, KIDs associated with writes received from the CPU core201are given medium priority, and key updates received from the KMU are given the lowest priority. Note that alternative embodiments of the MC circuit209may forgo the arbiter304and, instead, have the KIDs provided directly to the keystore303and may have any suitable alternative mechanism for handling conflicting KID inputs to the keystore303.

Note that each of the encryption engine301and the decryption engine302may be generically referred to as a cryptography engine. Note that, in some alternative embodiments, a single cryptography engine performs both encryption and decryption and additional circuitry provides the needed routing of data, address, and/or KID. Note that, in some alternative embodiments, the MC circuit209may have only one type of cryptography engine. In other words, in some alternative embodiments, the MC circuit209may have only an encryption engine and no decryption engine, or vice-versa.

In one implementation, the SoC101comprises sixteen single-threaded CPU cores201, thereby allowing sixteen unique PSEs to run simultaneously. The PSE management software may be a program running distributed across one, some, or all of the CPU cores201. The SoC101is configured to support thousands of PSEs and support time-slicing up to128PSEs at any one time. In other words, during normal operation, thousands of PSEs are suspended (in other words, are dormant), where a PSE's code and data exist in RAM encrypted with that PSE's key, but the PSE's corresponding cryptographic key is stored by the KMU in a relatively cheap, large, and slow memory (e.g., DDR SDRAM) in encrypted form, and therefore not immediately available for encrypting/decrypting that PSE's code and data. Meanwhile, scores of PSEs may be executing by time-slice sharing the sixteen CPU cores201of the SoC101, where these PSEs' cryptographic keys are stored in the keystore303(a relatively fast, small, and expensive memory, e.g., on-chip SRAM) for rapid access by the cryptographic engines301and302, where these PSEs' code and data may be stored in the RAM modules102, and where up to sixteen of these PSEs may be executing simultaneously on the CPU cores201.

Accordingly, the keystore303may be configured to cache128cryptographic keys. Each cryptographic key is stored in a corresponding 7-bit addressable (using the KID) memory location in the keystore303. Note that a 7-bit address is usable to uniquely address 128 cryptographic-key locations (as 27equals 128). In one implementation, each cryptographic key is 256 bits.

FIG.4is a schematic representation of an exemplary data packet400in accordance with one embodiment of the computer system100ofFIG.2. The data packet400includes a data payload403, a key identifier (KID)402, and a header401. In one implementation, (i) the data payload field403is at least 128 bits so as to be able to contain an entire 128-bit standard AES block, and (ii) the KID field is at least 7 bits to support addressing 128 cryptographic-key locations in the keystore303. The header401may contain any suitable header information, such as, for example, attribute information for transmission of the data packet400on the system bus206(e.g., memory address, read/write indicator, source address for routing response, etc.). Note that a read-request packet may include only a KID and a header, including a memory address, with no payload. Relatedly, a read-response packet may include only a data payload and a header with no KID. Note further that the KID, when used, does not have to be an exclusive-use segment of the data packet and may be, for example, part of the header and/or used for purposes other than identifying a key location in the keystore.

FIG.5is a flowchart for a process500in accordance with one embodiment. The process500starts when a determination is made by a writing module that a data block needs to be written to a RAM module102(step501). The writing module may be made by, for example, a first PSE executing on a first CPU that needs to directly write a block to memory or a first cache that needs to evict a cache line. Note that, in general, write requests from a PSE executing on a CPU may be cached and, while in the cache hierarchy of SoC101, the data block is associated with the KID of the PSE. The writing module provides to the MC circuit209, via the system bus206and bus interface208, a corresponding data packet400, which comprises the plaintext data block in the data payload403and the KID corresponding to the first PSE in the KID field402(step502). Note that the data payload403may include suffix and/or prefix padding bits together with the data block. The data payload403is provided to the encryption engine301and the KID is provided to the arbiter304, which provides the KID to the keystore303(step503).

The keystore303outputs the cryptographic key stored at the address specified by the KID and provides that key to the encryption engine301(step504). The encryption engine301executes an encryption algorithm (e.g., AES encryption) on the received plaintext data using the received key and outputs a corresponding ciphertext data block (step505). The ciphertext data block is then provided to the RAM module102(step506).

FIG.6is a flowchart of a process600in accordance with one embodiment. The process600starts when the memory controller204receives a data packet via the bus interface208and determines that a data block needs to be read (i.e., retrieved) from the RAM module102using the address and KID provided in the data packet(step601). The data packet may be received from, for example, a CPU core201, L2 cache202, or L3 cache203. The memory controller204initiates a read of the corresponding data block from the RAM module102and buffers the corresponding KID (step602). The MC circuit209receives the requested encrypted data block from the RAM module102(step603).

The KID is provided to the keystore303(step604). The decryption engine302is provided (1) the retrieved encrypted data block and (2) the key stored at the KID address in the keystore303(step605). The decryption engine302executes a decryption algorithm (e.g., AES decryption) on the received encrypted data block using the received key and outputs a corresponding plaintext data block (step606). The memory controller204provides a response data packet containing the plaintext data block via the bus interface208for routing back to the requesting CPU core or cache (step607).

Generic terms may be used to describe the steps of the above-described read and write processes500and600. Determining needs to write or read data is determining a need to transfer data between the first PSE and a RAM module102. Ciphertext and plaintext are data. Encryption and decryption are cryptographic operations, which take a first data block and output a first cryptographically corresponding data block.

FIG.7is a flowchart of a process700in accordance with one embodiment. The process700starts when the PSE management software determines that a new or dormant PSE needs to be activated (step701). In response to the determination, the PSE management software notifies the KMU207, which determines if there is a free (e.g., empty) slot available in the keystore303(step702). If there is, then the cryptographic key for the activating PSE is stored in the available slot in the keystore303and that activating PSE is associated with the KID corresponding to the keystore address of the available slot (step703). If in step702it was determined that there is no free slot available in the keystore303, then the KMU207selects a PSE whose corresponding key is to be evicted from the keystore303and puts the selected PSE in a dormant state (step704). Any suitable algorithm—or combination of algorithms—may be used to determine which PSE to evict—for example, least used KID, randomly selected KID, sequentially selected KID, or lowest-priority-PSE KID.

Following the selection of the eviction PSE, the cache lines associated with the PSE of the key to be evicted are flushed and the translation lookaside buffer (TLB) entries associated with the PSE of the key to be evicted are invalidated (step705). If not already stored, then the eviction PSE's corresponding cryptographic key is stored for possible later use, in a relatively cheaper, larger, and slower memory (e.g., DDR SDRAM) in encrypted form (step706). The KMU207provides to the keystore303(1) via the arbiter304, the KID of the evicted key and (2) the cryptographic key of the activation PSE (step707) and the keystore303stores the cryptographic key of the activation PSE in the memory address indicated by the KID of the evicted key (step708), thereby replacing the key of the eviction PSE with the key of the activation PSE in the keystore303.

It should be noted that the above-described memory cryptography circuit may be used in systems other than computer system100. For example, MC circuit209may be used in the management of encryption of so-called data at rest stored on shared non-volatile memory (e.g., on one or more non-volatile dual in-line memory modules NVDIMMs) by a plurality of filesystem, where each filesystem has a corresponding cryptographic key, similar to the above-described PSEs. In general, the memory cryptography circuit may be used in any suitable system where a relatively large plurality of clients and corresponding cryptographic keys are managed.

FIG.8shows a block diagram of a computing device1100in accordance with another aspect of the present invention. Systems (which may be implemented on SoCs) may provide the ability to protect software running in “Realms” (e.g. a virtual machine, file system or application process) from higher privileged software (e.g. the hypervisor). These systems additionally provide protection against physical attacks (e.g. DRAM snooping), which requires the memory to be encrypted. To prevent certain classes of attacks, each Realm running on the system may utilize its own unique memory encryption key. There could be thousands of unique Realms running at any given time, so a high-performance method for using the correct key is necessary.

A CPU could tag all memory transactions with an ID of the key associated with the Realm currently running on the CPU—termed the Realm Key ID (RKID). The appropriate RKID could be programmed into a system register when loading or switching to the Realm. With this scheme, it would be difficult for one Realm to access memory pages belonging to another Realm—which may be undesirable. Further, the width of the RKID dictates by the max number of keys that will be stored and utilized. For example, if the RKID is 7 bits, the maximum number of keys is 128. Given the structure of modern systems, it is probably that there may be more realms then there are RKIDs.

Another method for the use of RKIDs would be to assign each memory page in the system a Realm ID of the Realm that owns the page. The memory system could perform a lookup using the page identifier/address to determine the RKID assigned to that Realm and tag any transaction with the appropriate RKID. In this way, the Realm ID namespace could be very large, much larger than the number of RKIDs. For example, Realm IDs may be 32 bits long (for a total of 4,294,967,296 possible Realms), while RKIDs may be only 12 bits long (for a total of 4,096 RKIDs). This method would also facilitate one Realm accessing the memory pages of another Realm. The present aspect is suitable for the fast lookup of a RKID using a Realm ID and/or a filesystem ID (referred to herein as the Realm ID for simplicity).

The computing device1100illustrated inFIG.8is configured to allow for fast storage and retrieval of RKIDs according to certain aspects of the present disclosure. Preferably, RKIDs are identifiers that consume a relatively smaller number of bits and may be dynamically associated with a specific realm ID.

The computing device1100comprises a CPU1110coupled to a memory management unit1120. The memory management unit1120is further coupled to a realm management unit1130(similar in function to the KMU207), and to a memory system1150(e.g. a cache or main memory) via a system bus1140. The memory management unit (MMU)1120includes a translation lookaside buffer (TLB)1122and an associated memory ownership table1124. The memory ownership table1124is configured to associate a physical memory page with a realm ID. The realm management unit1130includes a key ID association structure1134, and is responsible for managing allocation, deletion, and replacement of mappings in the key ID association structure1134. The key ID association structure1134is configured to associate a realm ID with a realm key ID.

When the CPU1110wants to perform a memory access to a memory page, it sends a request for access to the memory page to the MMU1120. The MMU1120will then access the TLB1122to determine the physical address of the memory page. Once the MMU1120has determined the physical address, it will access the memory ownership table1124to determine a realm ID of the realm that owns the page of memory associated with that physical address.

The realm ID is the provided to the realm management unit1130, which performs a lookup in the key ID association structure1134to determine a realm key ID that is associated with the provided realm ID. Once the appropriate realm key ID is known, the memory access from CPU1110can be launched onto the system bus1140with the associated realm key ID (RKID) to access the memory system1150. Further, once the RKID has been retrieved from the key ID association structure1134, in some aspects it may thereafter be cached in the TLB1122in association with the block or page of memory being accessed (i.e., with the associated virtual address). This can avoid further lookups in the memory ownership table1124and the key ID association structure1134when access to that block or page of memory is requested. If the realm key ID is cached in the TLB1122, the TLB1122may further implement a “TLB invalidate by RKID” function to invalidate any TLB entries associated with a particular RKID to handle the case where an RKID is deallocated from association with one realm and is allocated to another realm. Alternatively, the RKID retrieved from the key ID association structure1134may be cached in a separate key association cache (not illustrated) which would be accessed in parallel with the TLB1122and would implement an analogous “invalidate by RKID” function.

FIG.9shows a detailed block diagram1200of the memory ownership table1124and the key ID association structure1134of the computing device according to certain aspects of the present disclosure. The memory ownership table1124comprises a look-up table1204with a first column1204aincluding a physical address and a second column1204bincluding a realm ID associated with the physical address. Although the look-up table1204is illustrated as having four entries (rows), those having skill in the art will recognize that the number of entries is a design choice, and differing numbers of entries for the look-up table1204may be chosen in other aspects.

The key ID association structure1134contains a look-up table1214having a first column1214aincluding a realm ID, a second column1214bincluding a first realm key ID, a third column1214cincluding a second realm key ID, a fourth column1214dincluding a third realm key ID, and a fifth column1214eincluding a pointer to another table entry. Although the look-up table1214has been illustrated as including six entries (rows), each having three realm key IDs and a pointer to another table entry, those having skill in the art will again recognize that the number of entries, number of realm key IDs, and use of a pointer are all design choices. Where the look-up table1214is implemented as a hash table, the use of a pointer may be advantageous to allow to look-up table1214to handle collisions (i.e., more realm key IDs mapped to a single realm ID than there are columns to store realm key IDs) by setting the pointer to point to another entry in the look-up table1214when an attempt is made to add another realm key ID to an entry that already contains the maximum number. In some aspects, the look-up table1214may employ cuckoo hashing (i.e., having two active hash functions that may be used to insert or retrieve entries from the table) to further reduce collisions. Again, those having skill in the art will recognize that other aspects may implement the look-up table1214as a data structure other than a hash table, which may solve the problem of collisions differently.

In operation, a physical address1202is received by the memory ownership table1124from the TLB1122. The memory ownership table1124then looks up the physical address1202in the look-up table1204. If the physical address1202is present, an associated realm ID1212is identified. The associated realm ID1212is then provided to the key ID association structure1134, which looks up the realm ID1212in the look-up table1214. If the realm ID1212is present in the look-up table1214, an associated realm key ID1222is identified, and then provided back to the MMU1120(and the TLB1122). The MMU1120then initiates the memory access on the system bus1140with the associated realm key ID1222.

If the realm ID1212is not present in the look-up table1214(i.e., that realm ID does not have an associated realm key ID), a miss occurs. This happens, for example, when a realm attempts to gain access to a memory page owned by another realm, access controls permit the access, and the other realm isn't currently executing and has thus had its previous RKID reassigned. When this occurs, if there are unassigned RKIDs, the RMU1130assigns one of the unassigned RKIDs to the realm ID that caused the miss (in this case, realm ID1212). If there are no unassigned RKIDs, the RMU1130will choose a “victim” RKID (which may be done by selecting a least recently used RKID, or by other replacement algorithms known to those having skill in the art), delete that RKID's current assignment to a realm ID (including updating any and all associated data structures), and assign the victim RKID to the realm ID that caused the miss (again, in this case, realm ID1212). Once the realm ID1212has been associated with an RKID, the RMU1130signals to the MMU120to re-try the operation, which will now succeed.

FIG.10shows a method1300of retrieving a realm key ID according to certain aspects of the present disclosure. The method1300begins in block1310, where a memory ownership table is accessed with a physical address to determine a realm ID associated with that physical address. For example, the memory ownership table1124is accessed with the physical address1202to retrieve the associated realm ID1212.

The method continues in block1320, where a key ID association structure is accessed with the realm ID to determine a realm key ID associated with the realm ID. For example, the key ID association structure1134is accessed with the realm ID1212to retrieve the associated realm key ID1222.

The method continues in block1330, where a memory transaction is initiated based on the realm key ID. For examples, the MMU1120receives the realm key ID1222from the key ID association structure1134and initiates a memory transaction based on the realm key ID1222.

The method continues in block1340, where the received realm key ID is cached in a translation lookaside buffer. This allows future accesses to proceed more quickly, since the realm key ID can be retrieved directly from the TLB. For example, the realm key ID1222is cache by the MMU1120in the TLB1122along with the entry for the associated memory page. In an alternative aspect, the received realm key ID may be cached in a dedicated cache, as discussed with respect toFIG.8.

FIG.11shows a method400of replacing a hashing function associated with storing realm key IDs according to certain aspects of the present disclosure. As discussed with reference toFIG.9, the occurrence of collisions in the key ID association structure1134may degrade system performance because multiple entries of the key ID association structure1134may need to be traversed via pointers (e.g., as a linked list) to locate a desired realm key ID. It may thus be advantageous to replace the hashing function associated with the key ID association structure1134. To this end, the method1400begins at block1410, where the performance of a current hashing function is evaluated. This may further include, at block1415, detecting that a number of collisions exceeds a threshold. The threshold may be programmable or otherwise dynamic in nature.

The method1400continues at block1420, where a scratch hash table with a new hash function (e.g., a hash function using a different seed value) is established. In block1430, the new hash function is evaluated for collisions. In block1440, it is determined whether the performance of the new has function is acceptable. If the performance is not acceptable, the method returns to block1420and a different new hash function is established for the scratch hash table. The current hashing function may be retained during the operations of block1420-1440so that the computing device can continue to perform computations while new hashing functions are evaluated.

If the performance of the new hashing function is acceptable, the method continues to block1450. In block1450, the current hashing function is replaced with the new hashing function.

FIG.12shows a diagram of a computing device1500incorporating a structure for storing realm key IDs as described with respect toFIG.8andFIG.9, and which may be operable in accordance with the methods described inFIGS.10and11. In that regard, the system1500includes the processor1502which may incorporate CPU1110, MMU1120, and RMU1130as described with regard toFIGS.8and9. The system1500further includes the memory1150coupled to the processor1502via the system bus1140. The memory1150may further store non-transitory computer-readable instructions that, when executed by the processor1502, may perform the method1300ofFIG.10or the method1400ofFIG.11.

FIG.12also shows optional blocks in dashed lines, such as coder/decoder (CODEC)1534(e.g., an audio and/or voice CODEC) coupled to processor1502. An optional speaker1536and microphone1538can be coupled to CODEC1534. An optional wireless antenna1542coupled to an optional wireless controller540which is, in turn, coupled to processor1502. Further, the system1502also illustrates and optional display controller1526coupled to processor1502and to an optional display1528. An optional wired network controller1570is illustrated as being coupled to processor1502and to an optional network1572. Processor1502, display controller1526, memory1150, and wireless controller1540may be included in a system-in-package or system-on-chip device1522.

Accordingly, input device1530and power supply1544are coupled to the system-on-chip device1522. Moreover, as illustrated inFIG.12, where one or more optional blocks are present, display1528, input device1530, speaker1536, microphone1538, wireless antenna1542, and power supply1544are external to the system-on-chip device1522. However, each of display1528, input device1530, speaker1536, microphone1538, wireless antenna1542, and power supply1544can be coupled to a component of the system-on-chip device1522, such as an interface or a controller.

It should be noted that althoughFIG.12generally depicts a computing device, processor1502and memory1150, may also be integrated into a mobile phone, a communications device, a computer, a server, a laptop, a tablet, a personal digital assistant, a music player, a video player, an entertainment unit, and a set top box, or other similar devices.