Hardware contiguous memory region tracking

Embodiments of the invention relate to performing a scan of a memory region associated with a virtual machine. The scan is performed by a hardware mechanism in response to a call. A data structure that includes information about substrings identified during the scan and a number of replications for each substring is constructed by the hardware mechanism. The data structure is stored by the hardware mechanism at a location determined by the call.

BACKGROUND

The present invention relates to management of virtual machines (VMs), and more specifically, to a method for balancing virtual machine loads between hardware platforms.

Providers of cloud computing have the competing tasks of providing desired performance for consumers or end users while also efficiently allocating the resources used to provide services to consumers. The resources may be dynamically allocated by the provider to help achieve these goals. Accordingly, a hardware platform may host a plurality of virtual machines, wherein each virtual machine corresponds to a consumer. Efficient use of the hardware platform resources dictates that the provider place as many virtual machines on the platform as possible without compromising the consumer's use of the virtual machine and experience. It may be desirable to move or migrate a virtual machine from one hardware platform to another to ensure that the customer is not adversely affected by changes in resource availability for the virtual machines.

SUMMARY

An embodiment is a method for performing a scan of a memory region associated with a virtual machine. The scan is performed by a hardware mechanism in response to a call. A data structure that includes information about substrings identified during the scan and a number of replications for each substring is constructed by the hardware mechanism. The data structure is stored by the hardware mechanism at a location determined by the call.

Another embodiment is an apparatus that includes at least one processor and a storage device. The storage device has instructions stored thereon that, when executed by the at least one processor, cause the apparatus to perform a scan of a memory region associated with a virtual machine. The scan is performed by a hardware mechanism in response to a call. A data structure that includes information about substrings identified during the scan and a number of replications for each substring is constructed by the hardware mechanism. The data structure is stored by the hardware mechanism at a location determined by the call.

A further embodiment is a computer program product that includes a computer readable storage medium having computer readable program code embodied therewith. The computer readable program code includes computer readable program code configured for performing a scan of a memory region associated with a virtual machine. The scan is performed by a hardware mechanism in response to a call. A data structure that includes information about substrings identified during the scan and a number of replications for each substring is constructed by the hardware mechanism. The data structure is stored by the hardware mechanism at a location determined by the call.

DETAILED DESCRIPTION

Embodiments described herein are directed to performing a scan of a region of memory associated with a virtual machine (VM). In some embodiments, based on the scan of the memory region, a data structure is constructed that identifies indices of pages that are identical. In some embodiments, if no pages are the same, then the data structure indicates that with, for example, a value of ‘null’.

Characteristics are as follows:

Service Models are as follows:

Deployment Models are as follows:

Workloads layer66provides examples of functionality for which the cloud computing environment may be utilized. Examples of workloads and functions which may be provided from this layer include: mapping and navigation; software development and lifecycle management; virtual classroom education delivery; data analytics processing; transaction processing; and a mobile desktop for mobile devices (e.g.,54A,54C, and54N, as well as mobile nodes10in cloud computing environment50) accessing the cloud computing services.

In one embodiment, one or both of the hardware and software layer60and the virtualization layer62may include edge components, such as a web server front end and image cache, as well as an image library store, e.g., in a high-performance RAID storage area network (SAN). In an exemplary embodiment, an application, such as a virtual machine monitoring application70in the virtualization layer62, may implement a process or method for scanning one or more memory regions associated with one or more virtual machines; however, it will be understood that the application70may be implemented in any layer.

In some instances, it is desirable to move data from a first location to a second location. For example, as part of a migration of a VM, data may be moved from, e.g., a first location (e.g., a first device or machine) to a second location (e.g., a second device or machine. A movement of data may be performed at runtime, potentially with or without an interruption of service.

In some embodiments, after the data is moved from the first location to the second location, the data at the first location is deleted or the first location is flagged as being free or clear for writing. Such treatment of the first location may be used to free memory or storage at the first location.

In some embodiments, after the data is moved from the first location to the second location the data at the first location is retained. Such treatment may be used to facilitate generating a copy of the data for purposes of, e.g., enhanced reliability or quality of service (QoS).

Turning now toFIG. 4, a memory402is shown. In some embodiments, the memory402may correspond to the memory28ofFIG. 1(or a portion thereof). For purposes of illustrative simplicity, the memory402is shown as included sixteen addressable locations404, numbered 0 through 15 (404a-404p). In some embodiments, the memory402includes more or less than sixteen locations404. The locations 0-15 (404a-404p) may be contiguous or non-contiguous. In some embodiments, one or more of the locations404may correspond to a page.

In some embodiments, a scan of the memory402occurs. In some embodiments, the scan is performed by one or more devices or entities, such as the processing unit16ofFIG. 1.

In some embodiments, the scan may be performed using a processor or processing unit that is separate or distinct from the processing unit16ofFIG. 1. For example, as shown inFIG. 4, a processor420may perform the scan. The processor420may correspond to an offload processor, a general-purpose processor or GPU, etc.

In some embodiments the scan may be originated in a hypervisor operating system with full hardware addressing, or a hypervisor operating system using virtual hardware addressing, or by a userspace application using virtual addressing.

In some embodiments, the scan is used to identify substrings of data that repeat themselves in a region of the memory402that is of interest. The region of the memory402that is of interest may be identified using a beginning address and an ending address. In the illustrative example ofFIG. 4, the beginning address406acorresponds to address 2404cand the ending address406bcorresponds to address 9404j. The results of the scan may be written to a data structure, and the data structure may be stored to an identified memory address. In the illustrative example ofFIG. 4, the data structure may be written to a storage or memory address406ccorresponding to an address or location ‘Q’404q.

In some embodiments, to facilitate the above operation, a scan function, process, routine, procedure, etc., may be implemented of the form:
scn beginaddr endaddr storeaddr,
where scn is a scan call (e.g., a scan assembly call), beginaddr is the address at which the scan begins (e.g.,406ainFIG. 4), endaddr is the address at which the scan ends (e.g.,406binFIG. 4), and storeaddr is the address where the resulting data structure is stored in memory (e.g.,406cinFIG. 4).

The above scan call may be generalized to accommodate the use of registers as an alternative to, or in addition to, the use of addresses (e.g., memory addresses). For example, “beginaddr” can optionally be replaced with “beginreg” to identify a register that contains the starting address to start a scan with. Similarly, “endaddr” can optionally be replaced with “endreg” to identify a register that contains the ending address to end a scan with. Similarly, “storeaddr” can optionally be replaced with “storereg” to identify a register whose location will be filled with the starting address of a data structure that includes results from having performed the scan. Thus, a scan may be performed using any combination of addresses and registers for the beginning, ending, and storage location parameters or arguments.

In some embodiments, a flag or register may be used to indicate that all of memory should be scanned. For example, depending on the context, all host memory may be scanned, such as in situations where a hypervisor is performing the scan, or the root user of a virtual machine, or a virtual machine operating system scanning all memory in that virtual machine. In some embodiments, a separate assembler may be called, for example, scana or alternatively using particular values for the arguments.

In some embodiments, the scn call includes one or more additional arguments. For example, the scn call may take the form:
scn beginreg endaddr storeaddr minlen,
where the “minlen” argument represents a minimum length of a memory chunk whose replications are to be recorded. Specification of the “minlen” argument may be used to filter out short substrings that would not be of interest. Minlen may be expressed in some known units such as bytes, nibbles, words, bits, etc. For example, if the minlen is specified in bytes, setting minlen to one (1) may be used to filter out results of length less than one (1) byte from the resulting data structure.

The value for the argument “minlen” may be specified based on a particular application environment or context. In some embodiments, a scan is performed for various sized strings, sub strings, or chunks of memory. For example, a dynamic scan may be performed for various sized strings by changing or adjusting the “minlen” argument over multiple scn calls. In some embodiments, a particular value of minlen may be specified as an address or register that indicates the hardware is to perform dynamic scans without repeated calls to the scan assembler routine by the application.

Once beginning and ending locations are specified for a scan call, and the scan is performed, all substrings (or all substrings of at least “minlen” if such an argument is used) may be recorded or written to a storage location (e.g., memory address ‘Q’404q). In some embodiments, an identification or count of the number of instances or occurrences for each of the substrings is also recorded to the storage location in accordance with a known storage format.

Aspects of the disclosure may be applied in connection with metadata. For example, a register may have a value that is set to the length of the longest replicated string, an associated register may have a value that is set to the starting address of the replicated string, and a second associated register may contain the number of times the string has been replicated.

Turning now toFIG. 5, a flow chart of an exemplary method500is shown. The method500may be executed in connection with one or more systems, components, or devices, such as those described herein. In some embodiments, the method500may be implemented by the application70ofFIG. 3. The method500may be executed to collect metadata regarding information or data (e.g., substrings) stored in one or more memory devices.

In block502, the method500may start. From block502, flow may proceed to block504.

In block504, an entity (e.g., a system, an apparatus or device, etc.) may listen for a call, such as an assembler call. The call may correspond to an invocation of a scan routine, procedure, function, etc. From block504, flow may proceed to block506.

In block506, a determination may be made regarding one or more addresses or registers to begin and end a scan. The addresses and/or registers may be specified as part of the call of block504. From block506, flow may proceed to block508.

In block508, a location (e.g., an address) may be determined or identified for purposes of storing a data structure that includes results from the call or running a scan. The location may be specified as part of the call of block504. From block508, flow may proceed to block510.

In block510, a minimum length of a substring to track may be determined or identified. The minimum length may be specified as part of the call of block504. From block510, flow may proceed to block512.

In block512, a scan of memory may be performed based on the addresses and/or registers associated with block506. Some or all substrings may be tracked. For example, substrings that are greater than or equal to a minimum length (block510) may be tracked. A number of replications or occurrences of each substring that is tracked may also be tracked or recorded. From block512, flow may proceed to block514.

In block514, a data structure may be constructed. The constructed data structure may include information on the substrings that were tracked and the number of replications or occurrences (block512). This data structure may be located in a region of system memory, placed in vector pairs/sets of registers, or placed in some special purpose storage (volatile or nonvolatile). From block514, flow may proceed to block516.

In block516, the information or the data structure constructed as part of block514may be stored at the location determined/identified in block508. From block516, flow may proceed to block504. The flow from block516to block504may establish a loop, such that once a first call or scan is performed or processed, subsequent calls or scans may be performed and processed.

The blocks or operations of the method500are illustrative. In some embodiments, one or more of the blocks (or a portion thereof) is optional. In some embodiments, one or more blocks execute in an order or sequence different from what is shown inFIG. 5(e.g., blocks506,508, and510could execute in any order). In some embodiments, one or more additional blocks not shown are included.

In some embodiments a machine may determine what data is available at the machine by performing a scan. The scan may be performed by a hypervisor or virtual machine manager (VMM). The scan may be performed on memory, e.g., all or a portion of the memory, or virtual memory referenced by one or more VMs. The VMs may be located on, or hosted by, the machine. The machine may transmit or broadcast information relating to the data that is available. The data may pertain to strings, substrings, pages of memory, metadata, etc.

In some embodiments, a hardware entity may be configured to quickly scan a contiguous or non-contiguous memory region that includes one or more contiguous fixed size regions of memory. A data structure (e.g., a map, table, or chained linked list (optionally sorted)) may be constructed of page indices which are identical or may indicate or include a ‘null’ if no pages are the same. For example, a table may be configured such that if a contiguous known fixed length memory region's index is entered, a linked list of all other memory region indices, which contain identical contents at that address, may be provided (or a ‘null’ may be provided if no pages are the same).

In some embodiments, offsets or lengths may be used within a page or contiguous page regions to facilitate partial same-page replication detection. In some embodiments, a location of an optimal size region for memory sharing may be determined by iterating over all pages multiple times (e.g., multiple times per second), adjusting an index into the page by a single byte, and adjusting the length by a single byte, until all indices within a page and all region sizes within a page are computed. In some embodiments, scans may be performed in parallel to improve or enhance efficiency. The average size (e.g., mean, median, mode, and standard deviation, or any combination of the above) of chained items in a data structure (e.g., a map, table, or linked list) may be stored to obtain a sense for the distribution of same-page values. In some embodiments, the results of such a computation may be placed in a register, facilitating fast access to the results. In some embodiments, an operating system or other software may access the results.

In some embodiments, direct data or (sub)string comparisons may be performed to determine or identify instances or occurrences of data. Such information may be used to migrate a VM from a first machine to one or more additional machines. Hardware based scans may be performed to increase the speed at which a machine or VM's memory environment is characterized. Fast characterization may be needed in environments associated with large amounts of data, such as data centers, server applications, etc.

In some embodiments, VMs may point to or reference a shared memory such that data transfer or data replication operations may be reduced or minimized. Furthermore, resources (e.g., storage resources) may be preserved such that the number of VMs hosted on a single machine may be increased or maximized.

In some embodiments, one or more data structures may be implemented using rabin fingerprinting. Rabin fingerprinting may be used in some embodiments, potentially in lieu of using a hash table or hash table based protocol or in lieu of a perfect bit matching to enable speedups.

In some embodiments, entries may be invalidated when a guest is writing to referenced memory regions. Computed values may be correct for only a point in time, but may be invalidated seconds later under heavy dynamic memory workloads.

Technical effects and benefits include a storage of indices associated with shared memory regions. By keeping a data structure of indices, as opposed to storing or sharing entire memory pages, overhead may be reduced and performance may be increased or enhanced. The indices or metadata may be used to migrate between machines or facilitate generating copies of data between machines.

Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). In some embodiments, assembler or millicode/microcode on an embedded or special purpose processor may be used to implement one or more aspects of this disclosure.