RU2780969C1 - Faster access of the memory apparatus of a virtual machine reserved by a virtual memory apparatus of a computing host apparatus - Google Patents

Abstract

FIELD: information technology.

SUBSTANCE: to realise the technical result, one or more hierarchical levels of tables in a second-level address table (SLAT) may be skipped or otherwise not accessed. Even though the SLAT may be filled with correlations in the memory apparatus at hierarchically higher table levels, the table of page of the computing host apparatus supporting the initialisation of the computing host apparatus of the virtual memory apparatus may support the corresponding adjacent set of correlations in the memory apparatus at the hierarchically lowest table level. If such manipulation occurs, the SLAT may be refilled with correlations in the memory apparatus at the hierarchically lowest table level.

EFFECT: increase in the efficiency of using a memory apparatus by means of virtual machine processes executed on a computing host apparatus.

20 cl, 8 dwg

Description

State of the art

[0001] Modern computing devices operate by executing computer-executable instructions from a high-speed volatile storage device in the form of random access memory (RAM), and execution of such computer-executable instructions often entails reading data from RAM. Due to cost, physical size limitations, power requirements, and other similar constraints, computing devices typically contain less RAM than is required by the processes that typically run on such computing devices. To cope with such limitations, virtual storage is used, whereby the storage that appears to be available to processes running on the computing device is larger than the physical storage layout provides. The relationship between virtual storage and physical storage is typically managed by one or more storage managers that implement, maintain, and/or access a "page table" whose information demarcates the relationship between one or more virtual storage cell addresses and corresponding data locations. , in physical storage, or in some form of storage media. To handle the storage capacities relevant to modern computing devices and the processes running on them, a modern page table typically consists of several hierarchical levels of tables, with the higher level table having entries that identify a different lower level table, and the hierarchically lowest level table contains entries that do not identify yet another additional table, but instead directly identify the addresses of the memory cells.

[0002] Of the processes that can be executed by computing devices, processes are provided that virtualize or abstract the underlying hardware of a computing device. Such processes include virtual machines that can simulate a complete underlying computing device for processes running within a virtualized computing context provided by such virtual machines. A hypervisor or similar set of machine-executable instructions may facilitate initialization of a virtual machine by virtualizing or abstracting the underlying hardware of the physical computing device hosting such a hypervisor. The hypervisor may maintain a Second Level Address Table (SLAT), which may also be hierarchically organized in a manner similar to the above page tables. The SLAT may store information that delimits a relationship between one or more storage cell addresses that appear to be physical storage cell locations for processes running on top of a hypervisor, including processes running inside a virtual machine context whose underlying computing hardware virtualization is facilitated by hypervisor, and storage cell locations directly to the actual physical storage device.

[0003] When a process running inside a virtual machine context, for example, accesses a storage device, two different lookups can be performed. One lookup may be performed directly in the virtual machine context to correlate the requested virtual storage cell address with the physical storage cell address. Because such a lookup is performed directly within the virtual machine context, the physical storage location address identified is only the address of the physical storage location as perceived by processes running within the virtual machine context. Such a lookup may be performed by a storage manager running within a virtual machine context, and may be performed by referring to a page table that exists within the virtual machine context. The second lookup can then be performed outside of the virtual machine context. More specifically, the physical storage location address (in the context of a virtual machine) identified by the first lookup may be correlated with the actual physical storage location address. Such a second lookup may entail accessing, by one or more processing units of the computing device, an SLAT that may correlate perceived physical storage cell addresses with actual physical storage cell addresses.

[0004] As indicated, both page tables and SLATs can be hierarchical arrangements of different hierarchical levels of tables. Thus, the performance of a table lookup, whether performed by the storage manager accessing the page table or performed by the hypervisor accessing the SLAT, may entail determining the corresponding table entry at the hierarchical topmost level of the table when the table is accessed. hierarchically lower level that is identified by this table entry, determining the corresponding table entry in this hierarchically lower level table, referring to the table of a still lower level hierarchically that is identified by this table entry, etc., until table of the lowest hierarchical level is not reached, whereupon the individual entries of this table of the lowest hierarchical level identify one or more specific addresses or address ranges of immediate storage, presumably to identify yet another additional table. Each access to a table in a hierarchically lower level consumes processor cycles and increases the duration of access to the storage device.

[0005] In the case of accessing the storage device from a process executing inside a virtual machine context, for example, the duration of such access to the storage device may include traversal of the page table hierarchical levels performed by the storage manager, in the context of the virtual machine, and, in addition to of this, traversal of the hierarchical SLAT levels performed by the hypervisor. The extra latency introduced by hypervisor-based lookups with SLAT calls makes accessing the storage device from processes running inside the VM context, or, in fact, from any process that accesses the storage device through the hypervisor, more inefficient. compared to processes that access the storage device more directly. Such inefficiency may prevent users from achieving the security and other benefits provided by accessing the storage device through a hypervisor.

The essence of the invention

[0006] In order to improve storage efficiency by virtual machine processes executing on a host computing device, these virtual machine processes can be backed up by host virtual storage, thereby allowing conventional virtual storage efficiencies to be applied to storage consumed by such virtual machine processes. To increase the rate at which hierarchical levels of the Second Level Address Table (SLAT) are traversed as part of a storage access in such an environment in which the guest physical storage of the virtual machine environment is backed up by a virtual storage assigned to one or more processes running on computing host device, one or more hierarchical levels of tables in the SLAT may be skipped or otherwise unreferenced, thereby resulting in more efficient SLAT traversal and more efficient storage access. While the SLAT may be populated with in-memory correlations at hierarchically higher table levels, a computing host page table supporting initialization of the virtual storage computing host can maintain a corresponding contiguous set of in-memory correlations at the hierarchically lower table level, by thereby allowing the computing host device to page out or otherwise manipulate smaller portions of the storage device. If such manipulation occurs, the SLAT may be repopulated with correlations in storage at the hierarchically lowest level of the table. On the other hand, if the host can reassemble a large enough contiguous set of small pages, the SLAT can repopulate with correlation at hierarchically higher table levels, thereby again resulting in more efficient SLAT traversal and more efficient storage access. Thus, more efficient SLAT traversal can be achieved while maintaining the storage efficiency advantages of redundant virtual machine processes with virtual storage of the computing host device.

[0007] This Summary is provided to introduce in simplified form a selection of concepts that are further described below in the Detailed Description. This summary is not intended to identify key features or essential features of the claimed invention, nor is it intended to be used to limit the scope of the claimed invention.

[0008] Additional features and advantages should become apparent from the following detailed description, which is set forth with reference to the accompanying drawings.

Brief description of the drawings

[0009] The following detailed description may be best understood when viewed in conjunction with the accompanying drawings, of which:

[0010] FIG. 1 is a block diagram of an exemplary computing device;

[0011] FIG. 2 is a system diagram for an exemplary hardware and software computing system;

[0012] FIG. 3 is a block diagram illustrating the terminology used in this document;

[0013] FIG. 4 is a flowchart illustrating an exemplary method for reserving guest physical storage with host virtual storage;

[0014] FIG. 5 is a flowchart illustrating various exemplary activities in the life cycle of data in a guest physical storage device that is backed up by a host virtual storage device;

[0015] FIG. 6 is a block diagram illustrating an exemplary mechanism for reserving guest physical storage with host virtual storage;

[0016] FIG. 7 is a block diagram illustrating an exemplary mechanism for more efficient translation between guest physical storage and host physical storage when reserving a guest physical storage with host virtual storage; and

[0017] FIG. 8 is a flowchart illustrating an exemplary method for more efficient translation between guest physical storage and host physical storage when reserving a guest physical storage with host virtual storage.

Detailed description of the invention

[0018] The following description relates to improving the efficiency of storage access while providing more efficient use of storage on computing devices hosting one or more virtual machine processes that provide virtual machine computing environments. To improve storage efficiency by virtual machine processes running on a host computing device, these virtual machine processes can be backed up by host virtual storage, thereby allowing conventional virtual storage efficiencies to be applied to storage consumed by such virtual storage processes. cars. To increase the rate at which hierarchical levels of the Second Level Address Table (SLAT) are traversed as part of a storage access in such an environment in which the guest physical storage of the virtual machine environment is backed up by a virtual storage assigned to one or more processes running on computing host device, one or more hierarchical levels of tables in the SLAT may be skipped or otherwise unreferenced, thereby resulting in more efficient SLAT traversal and more efficient storage access. While the SLAT may be populated with in-memory correlations at hierarchically higher table levels, a computing host page table supporting initialization of the virtual storage computing host can maintain a corresponding contiguous set of in-memory correlations at the hierarchically lower table level, by thereby allowing the computing host device to page out or otherwise manipulate smaller portions of the storage device. If such manipulation occurs, the SLAT may be repopulated with correlations in storage at the hierarchically lowest level of the table. On the other hand, if the host can reassemble a large enough contiguous set of small pages, the SLAT can repopulate with correlation at hierarchically higher table levels, thereby again resulting in more efficient SLAT traversal and more efficient storage access. Thus, more efficient SLAT traversal can be achieved while maintaining the storage efficiency advantages of redundant virtual machine processes with virtual storage of the computing host device.

[0019] Although optional, the following description is given in the general context of computer-executable instructions, such as program modules, executable by a computing device. More specifically, the description refers to acts and symbolic representations of operations that are performed by one or more computing devices or peripherals, unless otherwise noted. As such, it should be understood that such actions and operations, which are sometimes referred to as computer-executed, include the manipulation, by means of a processing module, of electrical signals representing data in a structured form. This manipulation transforms or maintains data in storage locations that reconfigure or otherwise change the operation of the computing device or peripherals in a manner well understood by those skilled in the art. The data structures in which data is stored are physical locations that have specific properties specified by the data format.

[0020] In general, program modules include procedures, programs, objects, components, data structures, and the like that perform specific tasks or implement specific abstract data types. Furthermore, those skilled in the art should appreciate that computing devices should not necessarily be limited to traditional personal computers and include other computing configurations including servers, handheld devices, multiprocessor systems, microprocessor or programmable consumer electronics, network PCs, minicomputers, mainframes, etc. Likewise, computing devices need not be limited to stand-alone computing devices, as the mechanisms may also be practiced in distributed computing environments where tasks are performed by remote processing devices that communicate through a communications network. In a distributed computing environment, program modules may reside in both local and remote storage devices.

[0021] Before continuing with the detailed description of storage allocation and access mechanisms mentioned above, the detailed description of an exemplary computing host device, which provides context for the descriptions below, makes reference to the exemplary computing device 100 shown in FIG. 1. Exemplary computing device 100 may include, but is not limited to, one or more central processing units (CPUs) 120, system storage 130, and a system bus 121 that connects various system components, including system storage, to module 120. processing. System bus 121 may be any of several types of bus structures including a storage bus or storage controller, a peripheral bus, and a local bus using any of a variety of bus architectures. Computing device 100 may optionally include graphics hardware, including, but not limited to, a graphical hardware interface 160 and a display device 161, which may include display devices capable of receiving touch user input, such as a touch or multi-touch display device. . Depending on the particular physical implementation, one or more of CPU 120, system storage 130, and other components of computing device 100 may be physically co-located, such as on the same chip. In such a case, some or all of the system bus 121 may be solely silicon traces in a single-chip structure, and its illustration in FIG. 1 may be merely a convenience of designation for purposes of illustration.

[0022] Computing device 100 also typically includes computer-readable media, which may include any available media that can be accessed by computing device 100, and includes volatile and non-volatile media, as well as removable and non-removable media. By way of example, and not limitation, computer-readable media may include computer storage media and communication media. Computer storage media includes media implemented in any method or technology for storing content, such as computer readable instructions, data structures, program modules, or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other storage technology, CD-ROM, digital versatile disk (DVD) or other optical disc storage device, magnetic cassette, magnetic tape, magnetic disk storage, or other magnetic storage devices, or any other medium that can be used to store the desired content and that can be accessed by the computing device 100. However, computer storage media is not include communication media. Communication media typically comprises computer readable instructions, data structures, program modules, or other data in a modulated data signal such as a carrier wave or other transport mechanism, and includes any content delivery media. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, radio frequency (RF), infrared, and other wireless media. Combinations of any of the above types should also be included in computer readable media.

[0023] System storage 130 includes computer storage media in the form of volatile and/or non-volatile storage, such as Read Only Memory (ROM) 131 and Random Access Memory (RAM) 132. A basic input/output system (BIOS) 133 containing basic routines that help transfer content between elements in computing device 100, such as during startup, is typically stored in ROM 131. RAM 132 typically contains data and/or program modules that are directly accessible and/or currently managed by the processing module 120 . By way of example, and not limitation, FIG. 1 illustrates an operating system 134, other program modules 135, and program data 136.

[0024] Computing device 100 may also include other removable/fixed, volatile/nonvolatile computer storage media. By way of example only, FIG. 1 illustrates a hard disk drive 141 that reads from or writes to/from stationary non-volatile magnetic media. Other removable/non-removable, volatile/nonvolatile computer storage media that may be used with an exemplary computing device include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, semiconductor RAM, semiconductor ROM and other computer storage media defined and defined above. The hard drive 141 is typically connected to the system bus 121 via a non-volatile storage interface such as interface 140.

[0025] The drives and associated computer storage media discussed above and illustrated in FIG. 1 provide storage of computer readable instructions, data structures, program modules, and other data for computing device 100. FIG. 1, for example, a hard disk drive 141 is illustrated as storing an operating system 144, other program modules 145, and program data 146. It should be noted that these components may be either identical or different from the operating system 134, other program modules 135, and program data. 136. The operating system 144, other program modules 145, and program data 146 are given herein with different numbers to illustrate that, at a minimum, they are different copies.

[0026] Computing device 100 may operate in a networked environment using logical connections to one or more remote computers. The computing device 100 is illustrated as being connected to a common network connection 151 (to the network 190) via a network interface or adapter 150, which in turn is connected to the system bus 121. In a networked environment, the program modules illustrated with respect to the computing device 100 or parts thereof or peripheral devices may be stored in the memory of one or more other computing devices that are operatively connected to the computing device 100 via a common network connection 161. It will be appreciated that the network connections shown are exemplary and other means of establishing a communication link between computing devices.

[0027] Although described as a single physical device, exemplary computing device 100 may be a virtual computing device, in which case the functionality of the physical components described above, such as CPU 120, system storage 130, network interface 160, and other similar components, may provided by machine-executable instructions. Such computer-executable instructions may be executed on a single physical computing device or may be distributed across multiple physical computing devices, including being distributed across multiple physical computing devices in a dynamic manner such that the specific physical computing devices housing such computer-executable instructions may dynamically change over time in depending on need and availability. In a situation in which the exemplary computing device 100 is a virtualized device, the underlying physical computing devices housing such a virtualized computing device may directly contain physical components similar to the physical components described above and operate similarly. In addition, virtual computing devices may be used at multiple levels, with one virtual computing device running within the construct of another virtual computing device. Thus, the term "computing device", as used herein, means either a physical computing device or a virtualized computing environment, including a virtual computing device, in which computer-executable instructions can be executed in a manner compatible with their execution by a physical computing device. Similarly, terms referring to the physical components of a computing device, as used herein, refer to either those physical components or virtualizations thereof that perform identical or equivalent functions.

[0028] Referring to FIG. 2, the system 200 shown therein illustrates a computing system including both computing device hardware and processes running therein. More specifically, the exemplary system 200 shown in FIG. 2 includes the computing device hardware itself, such as the above processing modules 120 and RAM 132 illustrated as part of the exemplary computing device 100 described above. of computer-executable instructions that are executed by exemplary computing device 100 to enable computing device 100 to perform functionality associated with exemplary hypervisor 210. As described in more detail below, exemplary hypervisor 210 may include or may access a second level address table (SLAT) , such as the exemplary SLAT 220.

[0029] The exemplary hypervisor 210 may virtualize a set of computing hardware that may either be commensurate with or different from computing device 100 hardware, including differences in processor type and/or bitness, size and/or type differences. RAM, size and/or type of storage media, and other similar differences. Such virtualization may, among other things, activate one or more virtual machine processes, such as exemplary virtual machine processes 260 and 250. The hypervisor 210 may represent, both for processes running within the context of these virtual machines, and for any other process running on top of the hypervisor, the probability of executing directly on the hardware 110 of the computing device. The exemplary system 200 shown in FIG. 2 illustrates an operating system, such as an exemplary operating system 240, running on top of an exemplary hypervisor 210. In turn, as illustrated by an exemplary system 200, an exemplary operating system 240 may have one or more computer-executable applications running therein, such as those described above. processes 260 and 250 of the virtual machine.

[0030] Exemplary operating system 240 may include various components, subcomponents, or aspects thereof that are relevant to the descriptions below. Although illustrated as visually distinct elements in FIG. 2, such a visualization is not intended to convey particular computational independence, such as process boundaries, independent storage stores, or other similar computational distinctions. One aspect of operating system 240 may be a storage device manager, such as the exemplary storage device manager 241 . More specifically, the exemplary storage manager 241 can read code or data from one or more computer-readable storage media and copy such code or data to a storage device that can be supported by RAM 132.

[0031] As used herein, the term "virtual storage" is not used with reference to a virtual machine, but instead to the concept of representing, for applications or other processes running on a computing device, the likelihood of having access to more storage than is physically present in RAM 132. Thus, for example, virtual storage functionality provided by operating system 240 may allow code and/or data to be loaded into storage that is ultimately supported by physical storage, such as physical storage device 132, but which is larger than the physical storage device. The storage manager 241 executing as part of the operating system 240 may maintain, modify, and/or use the page table 250 to account for the correlation between one or more virtual storage cell addresses and one or more physical storage cell addresses. More specifically, the page table 250 provides address translation between one memory cell addressing scheme and another different memory cell addressing scheme. To achieve this, the page table 250 may comprise several hierarchical levels of tables, described in more detail below, which may correlate one or more storage cell addresses according to one storage cell addressing scheme, namely virtual storage cell addresses, with one or more addresses memory cells according to a different, different memory cell addressing scheme, namely physical memory cell addresses.

[0032] The exemplary system 200 shown in FIG. 2 illustrates applications running on top of operating system 240. In particular, such applications may be virtual machine applications that can instantiate virtual machine processes, such as exemplary virtual machine processes 260 and 270. Each virtual machine process can create a virtual computing environment that can host its own operating system, application programs, and other similar functionality that can host a physical computing environment, such as the physical computing environment represented by computing device 100. In the exemplary system 200 shown in fig. 2, an exemplary virtual machine process 260 is illustrated as creating a virtual machine environment 261, and an exemplary virtual machine process 270 is illustrated as creating a virtual machine environment 271. The exemplary virtual machine environment 271 is illustrated as accommodating an operating system, in the form of an exemplary operating system 281, which may be similar to the exemplary operating system 240 or may be a different type of operating system. For purposes of illustration, an exemplary operating system 281 running within an exemplary virtual machine environment 271 is illustrated as including a storage manager, namely an exemplary storage manager 282, which in turn accesses a page table, namely an exemplary table. 283 pages in order to provide virtual storage in a virtual machine environment 271 . Such virtual storage in virtual machine environment 271 may be used by processes running on top of exemplary operating system 281, such as exemplary processes 291 and 292, which are illustrated in FIG. 2 as also running within the exemplary virtual machine environment 271.

[0033] In a manner similar to that implemented by the storage device managers 241 and 282, the hypervisor 210, in facilitating the representation of a virtual set of computing hardware including storage, can similarly translate storage device cell addresses from one storage cell addressing scheme to a different, different addressing scheme for memory cells. More specifically, hypervisor 210 can translate storage cell addresses, which are represented by hypervisor 210 as physical storage cell addresses, to actual physical storage cell addresses, such as, for example, storage cell addresses that identify physical locations within the storage device. 132. Such translation may be performed by referring to another hierarchically organized table, namely SLAT 220, which may also provide translation of storage cell addresses between the same storage cell addressing scheme, in this case addresses that are perceived by processes running on top of hypervisor 210, as physical storage cell addresses, and another different memory cell addressing scheme, namely, in this case, the actual physical storage cell addresses .

[0034] According to one aspect, the virtual storage provided by the operating system 240 can be used to back up the virtual machine's physical storage instead of using non-paging physical storage cell allocations on the computing host device. This allows the storage manager 241 to manage the host physical storage associated with the guest physical storage. In particular, storage management logic that already exists on the host, such as the storage manager 241, can now be used to manage the physical storage of guest virtual machines. This allows the use of a smaller hypervisor, in terms of the amount of code used to implement the hypervisor, such as the exemplary hypervisor 210. The smaller hypervisor may be more secure because there is less code that may be used or that may have bugs. . Additionally, this provides increased density of virtual machines on the host, as less host physical storage can be used to implement virtual machines. For example, previously, since a virtual machine process requires non-paging storage, if the exemplary computing device 100 contains 3 GB of RAM 132, then it can only accommodate one virtual machine process that creates a virtual machine having 2 GB of RAM. In contrast, if the storage device consumed by the virtual machine process, such as the exemplary virtual machine process 270, is virtual storage, such as the virtual storage device provided by the operating system 240 storage manager 241, then the virtual storage space at 4 GB can provide support for two virtual machine processes, each of which creates a virtual machine that has 2 GB of RAM. Thus, exemplary computing device 100 can accommodate two virtual machine processes instead of just one, thereby increasing the density of virtual machine processes running on exemplary computing device 100.

[0035] Other advantages include a single storage management codebase managing all of the storage in the system (host and virtual machine). Thus, improvements, fixes, and/or tweaks to one codebase provide benefits for everyone. Additionally, this may result in reduced engineering costs due to the need to maintain only one codebase. Another exemplary benefit could be that VMs can immediately benefit from density improvements such as paging, page sharing, working set training and tuning, failure clustering, and so on. Another exemplary advantage may be that virtual storage and physical storage consumption limits can be set on virtual machines identically to any other process, providing administrators with the ability to control system behavior. Another exemplary benefit would be that additional features can be added to the host storage manager in order to provide greater performance, density, and functionality for virtual machines (and other non-virtual machine workloads are likely to benefit from them as well). ).

[0036] Referring to FIG. 3, system 300 illustrates the terminology used herein to refer to multiple levels of page tables and corresponding memory cell addressing schemes that are applicable to system 200 shown in FIG. 2. More specifically, in virtual machine environment 271, exemplary storage manager 282 may access page table 283 in order to correlate virtual storage cell addresses, in the context of virtual machine environment 271, to physical storage cell addresses, again, in context of the environment 271 of the virtual machine. As stated above, the term "virtual storage" does not mean storage in the virtual machine environment, but instead the amount of storage available to processes running on the computing device that is supported by but exceeds the capacity of physical storage. Thus, to nominate between virtual storage in a virtual machine environment and virtual storage in a non-virtualized (or no software) computing environment, the adjectives "guest" and "host-" are used, with the adjective "guest" indicating the computing environment of the virtual machine. machine, and the adjective "host-" indicates a non-software computing environment in which a virtual machine process is running that provides the virtual machine environment.

[0037] As such, and as illustrated in system 301, addresses in the "guest virtual storage 311" cell addressing scheme can be correlated with addresses in the "guest physical storage 312" cell addressing scheme via a page table 283 in the virtual machine environment 271, which is shown in FIG. 2. Similarly, addresses in the "host virtual storage 321" addressing scheme may be correlated with addresses in the "host physical storage 322" addressing scheme via a page table 250 that is part of an exemplary operating system 240 that shown in FIG. 2 as running in a non-virtual computing environment. Although not illustrated by exemplary system 301 in FIG. 3, according to one aspect and as described in more detail below, the guest physical storage device 312 of the virtual machine environment can be backed up by the virtual storage device of the host 321, thereby providing the above advantages. Such reservation of guest physical storage 312 with host virtual storage 321 may entail a modification of SLAT 220 that provides a translation between the "guest physical storage 312" cell addressing scheme and the "host physical storage 322" cell addressing scheme, as illustrated by exemplary system 301.

[0038] Referring to system 302, also shown in FIG. 3, a hierarchical table layout is illustrated, for example, that can be used to implement an example page table 250, an example page table 283, and/or an example SLAT 220. To cope with storage capacities applicable to modern computing devices and application program processes , tables 250, 283 pages and/or SLAT 220 should have several, typically four, levels of hierarchical tables. However, for ease of illustration, system 302 illustrates only two levels of hierarchical tables. The hierarchically higher table 340 may contain multiple table entries, such as exemplary table entries 341, 342, 343, and 344. For example, the hierarchically higher table 340 may be 4 KB in size and may contain 512 discrete table entries, which may be eight bytes in size. Each table entry may contain a pointer or other similar hierarchically lower table identifier, such as one of the exemplary hierarchically lower tables 350 and 360. Thus, for example, exemplary table entry 341 may contain an identification of exemplary hierarchically lower table 350, as illustrated by arrow 371. at least some of these eight bytes of data may be a pointer or other similar identifier of the hierarchically lower table 350. The exemplary table entry 342 may likewise contain an identification of the hierarchically lower level table 360, as illustrated by arrow 372. Each of the remaining discrete table entries for the exemplary hierarchically higher table 340 may similarly identify unique tables of the hierarchically lower level. Thus, in an example where the hierarchical table 340 is 4 KB in size and contains 512 table entries, each of which is eight bytes in size, such hierarchical table 340 may contain 512 identifications of 512 unique hierarchical tables over lower level, such as exemplary tables 350 and 360 of the hierarchically lower level.

[0039] Each of the tables of the hierarchically lower level, in a similar way, may contain separate table entries. For example, exemplary hierarchically lower table 350 may contain exemplary table entries 251, 352, 353, and 354. Similarly, exemplary hierarchically lower table 360 may contain table entries 361, 362, 363, and 364. As one example, each of the hierarchically lower level tables may have an equivalent size and structure with the hierarchically higher level table 340. Thus, exemplary hierarchically lower table 350 may be 4 KB in size and may contain 512 table entries, such as exemplary table entries 351, 352, 353, and 354, which may be eight bytes in size. In the example illustrated by system 302, table entries for hierarchically lower tables, such as, for example, example table entries 351, 352, 353, and 354 for example hierarchically lower table 350, can identify a contiguous range of storage cell addresses. For example, an exemplary table entry 351 may identify a range of storage cell addresses 371, as illustrated by arrow 391. A storage cell address range 371 may comprise a storage "page" and may constitute the smallest individually manageable amount of storage. Thus, actions such as moving information stored in volatile storage temporarily to non-volatile storage media, or vice versa, as part of activating virtual storage capacity that exceeds the installed physical storage capacity, can be performed on a per-page basis. Additionally, access permissions may be set on a per-page basis. For example, since the range of storage 371 is separately identified by table entry 351, access permissions can apply to all storage cell addresses in storage 371 range. On the other hand, access permissions of storage device cell addresses in storage 371 range can be independent. from access permissions set for a range of storage 372 that can be uniquely identified by another table entry, namely table entry 352, as illustrated by arrow 392.

[0040] The storage capacity per page of the storage device, such as the range of the storage device 371, may depend on various factors including processor design and other hardware factors, as well as communication connections, and the like. In one example, a page of a storage device, such as the page represented by a range of storage device 371, may be 4 KB in size.

[0041] Upon receipt of a request to access storage cell locations identified by one or more memory cell addresses, a table entry in a hierarchically higher table can be identified that corresponds to a range of memory cell addresses that includes the addresses of the memory cells to be accessed. For example, if the addresses of storage cells that are accessed are included in the storage device represented by the storage device 371, the table entry 341 may be identified in the hierarchically higher level table 340. The identification of the table entry 341 may in turn lead to the identification of the hierarchically lower table 350. In the hierarchically lower table 350, the addresses of the storage cells to be accessed may be defined as part of the storage device, which is identified by the table entry 351. The information in the table entry 351 can then identify the storage device 371 being sought for access.

[0042] Each such traversal of the hierarchically lower level of the page table may increase the delay between receiving a request to access a storage device and returning access to that storage device. In one aspect, a table entry for a hierarchically higher table, such as, for example, exemplary table entry 341 for a hierarchically higher table 340, may not identify a hierarchically lower table, such as exemplary hierarchically lower table 350, but instead, a storage page that may correspond to the entire storage range to be identified by the table entries in the hierarchically lower table. Thus, for example, if each page of storage 371, 372, and 373 identified by individual table entries 351, 352, and 353 for hierarchically lower table 350 has a size of 4 KB, then a 2 MB storage range may be identified by the combined number of all individual table entries for hierarchically lower table 350, since exemplary hierarchically lower table 350 may contain 512 table entries, each identifying a 4 KB storage range. In such an example, if all 2 MB of storage is treated as one 2 MB storage page, such one large storage page can be identified directly by an exemplary table entry 341 for a hierarchically higher level table 340. In such a case, since the exemplary table entry 341 would directly identify one 2 MB storage page, such as the exemplary 2 MB storage page 370, and would not identify a table hierarchically lower, there is no need to refer to tables hierarchically higher at all. low level. For example, if a page table or SLAT contains four hierarchical levels, the use of a large storage page, such as exemplary large storage page 370, should allow one of these hierarchical levels of the tables to be skipped and unreferenced, thereby providing storage cell address translation. device between virtual and physical storage by accessing only three hierarchical levels of tables instead of four, allowing access to the storage device more efficiently, namely 25% more efficient. device with a size of 2 MB is used, then the storage permissions, for example, may be identical for all 2 MB of storage in such a large storage page.

[0043] As a further example, if a hierarchically organized table is provided that is hierarchically above exemplary table 340, and each entry in exemplary table 340, such as entries 341, 342, 343, and 344, can address a 2 MB memory page, such as an example page 370 of 2 MB storage, then 512 such individual table entries, when aggregated together, can address 1 GB of storage. If one page of a 1 GB storage device is used, the reference to table 340 and subsequent reference to a hierarchically lower table, such as exemplary table 350, may be eliminated. Returning to the example where the page table or SLAT contains four hierarchical levels, the use of such a huge storage page should allow two of these hierarchical levels of the tables to be skipped and unreversed, thereby allowing translation of storage cell addresses between virtual and physical storage. device by accessing only the hierarchical levels of the tables instead of four, allowing access to the storage device in about half the time. On the other hand, since a page is the smallest amount of separately managed storage, if a 1 GB storage page is in use, then storage permissions, for example, may be identical for just 1 GB of storage in such a huge storage page. .

[0044] The term "large storage page", as used herein, means a contiguous storage range that is of such a size that it covers all storage ranges to be identified by a single table at the hierarchically lowest level, and may be uniquely and directly identifiable by one table entry for the table one hierarchical level above the table of the hierarchically lowest level. In the specific sizing example provided above, "large storage page", as the term is defined herein, should be a 2 MB storage page. However, as stated, the term "large storage page" does not imply a specific size, and instead the amount of storage in a "large storage page" depends on the hierarchical design of the page table itself and the amount of storage accessed by each entry. tables at the hierarchically lowest level of the page table.

[0045] Similarly, the term "huge storage page", as used herein, means a contiguous storage range that is sized to cover all storage ranges to be identified by a single table at the hierarchically second-lowest level. , and can be uniquely and directly identified by a single table entry for a table one hierarchical level above the table of the hierarchically second lowest level. In the specific sizing example provided above, a "huge storage page", as that term is used herein, would be a 1 GB storage page. On the other hand, as stated, the term "storage giant page" does not mean a specific size, and instead the storage space in the "storage giant page" depends on the hierarchical design of the page table itself and the storage space accessed by each entry. tables at the hierarchically lowest level of the page table.

[0046] Returning to FIG. 2, descriptions of the mechanisms by which a host (computing host device) virtual storage device can be used to reserve a guest physical storage device (virtual machine) are provided with reference to a virtualization stack, such as the exemplary virtualization stack 230 shown in FIG. . 2. A user mode process may run on the host computing device to provide virtual storage for backing up guest virtual machines. One such user-mode process can be created for each guest machine. Alternatively, a single user mode process may be used for multiple virtual machines, or multiple processes may be used for a single virtual machine. Alternatively, virtual storage may be implemented in ways other than using a user mode process, as illustrated below. For illustration purposes, the virtual storage device assigned to the virtual machine process 270 may be used to reserve the guest physical storage device represented by the virtual machine process 270 in the virtual machine environment 271, and similarly, the virtual storage device assigned to the virtual machine process 260 machine, can be used to reserve the guest physical storage device represented by the process 260 virtual machine in the environment 261 virtual machine. While illustrated per se in the exemplary system 200 of FIG. 2, the above user-mode process may be separate from virtual machine processes, such as exemplary virtual machine processes 260 and 270.

[0047] In one aspect, a virtualization stack, such as exemplary virtualization stack 230, can allocate host virtual storage in the address space of a specified user-mode process that is to host a virtual machine, such as exemplary virtual machine process 260 or 270. The host storage manager 241 may treat this storage as any other virtual allocation, which means that it may be paging, the physical page reserving it may change to accommodate allocations of contiguous storage cells elsewhere in the system, physical pages can be shared with another virtual allocation in another process (which in turn can be another virtual machine reservation allocation or any other allocation in the system). At the same time, a variety of optimizations are possible to cause the host storage manager to handle virtual machine reservation virtual allocations in the specific manner desired. In addition, if the virtualization stack 230 chooses to prioritize performance above density, it can perform many of the operations supported by the operating system's storage manager 241, such as locking pages in storage to ensure that the virtual machine does not need to be paging for these parts. Likewise, large pages can be used to provide even more performance for the virtual machine, as described in more detail below.

[0048] A given virtual machine may reserve all of its guest physical storage cell addresses in the guest physical storage device via the host virtual storage device, or may reserve some of its guest physical storage cell addresses in the guest physical storage device via the host virtual storage device, and some through legacy mechanisms, such as non-paging physical storage cell allocations performed from the host's physical storage.

[0049] When a new virtual machine is created, the virtualization stack 230 may use a user mode process to organize the allocation of virtual storage cells in order to reserve guest physical storage. It can be a newly created empty process, an existing process that hosts multiple VMs, or a per-VM process that also contains other VM-related virtual allocations that are not visible to the VM itself (for example, stack data structures). virtualization). It is also possible to use the virtual address space of the kernel in order to reserve a virtual machine. Once such a process is found or created, the virtualization stack 230 can perform private virtual storage cell allocation (or partition/file mapping) in its address space, which corresponds to the amount of guest physical storage the virtual machine should have. In particular, the virtual storage device may be a private allocation, file conversion, partition conversion with reservation using a paging file, or any other type of allocation supported by the host storage manager 241 . It does not need to be a single contiguous allocation, although, as discussed in more detail below, such an allocation may provide access speed advantages. Such an allocation may instead be an arbitrary number of allocations.

[0050] Once allocations of virtual storage cells are made, they can be registered with components that need to manage the virtual machine's physical address space, such as an exemplary virtual machine environment 271, and store it in sync with host physical storage pages that the dispatcher 241 The host storage device must choose to reserve virtual storage cell allocations. These components may be a hypervisor 210 and a virtualization stack 230, which may be implemented as part of a host kernel and/or driver. The hypervisor 210 may manage translation between cell address ranges of the guest physical storage device and the corresponding cell address ranges of the host physical storage device through the use of SLAT 220. storage device. Hypervisor 210 can make available the ability of virtualization stack 230 to receive traps when a certain type of access is performed by a guest virtual machine, such as exemplary virtual machine 271, for a given guest physical storage cell address. For example, the virtualization stack 230 may request the ability to receive a capture when a certain physical address is written by the guest virtual machine 271.

[0051] According to one aspect, when a virtual machine, such as exemplary virtual machine 271, is first created, SLAT 220 may not contain valid entries corresponding to such a virtual machine, since cell addresses of the host's physical storage may not be allocated in order to reserve addresses guest physical storage cells of such a virtual machine (although, as illustrated below, in some embodiments, SLAT 220 may be prepopulated for some guest physical storage cell addresses at or about the time virtual machine 271 is created). Hypervisor 210 may be aware of the address ranges of guest physical storage cells that are in use by virtual machine 27, but none of these should be backed up by any host physical storage at that point. When the virtual machine process 270 starts executing, it can start accessing its (guest) physical storage pages. As each new physical storage location address is accessed, it can generate a catch of the appropriate type (read/write/execute) because the corresponding SLAT record has not yet been populated with the corresponding host physical storage location addresses. The hypervisor 210 may receive the guest access capture and may forward it to the virtualization stack 230 . In turn, the virtualization stack 230 can access the data structure maintained by the virtualization stack 230 to find a host virtual storage cell address range that matches the requested guest physical storage cell address range (and the host process, from the virtual address reserved space, such as the exemplary virtual machine process 270). At this point, the virtualization stack 230 may know the specific host virtual storage cell address that corresponds to the guest physical storage cell address that generates the capture.

[0052] The virtualization stack 230 can then issue a virtual failure to the host storage manager 241 in the context of a process that holds a range of virtual addresses, such as a virtual machine process 270 . The virtual fault may be issued with the appropriate type of access (read/write/execute) of the initial trap that occurs when the virtual machine 271 accesses its physical address in the guest physical storage. A virtual fault may follow a similar or identical code execution path to that which a regular page fault should follow in order to ensure that the specified virtual address is valid and accessible by the host CPU. One difference may be that the virtual failure code execution path may return the physical page number that the storage manager 241 uses to ensure that the virtual address is valid. This physical page number may be a host physical storage location address that reserves a virtual host address, which in turn reserves a guest physical storage location address that initially generates a hijack in hypervisor 210. At this point, virtualization stack 230 may generate or update a table entry in SLAT 220 corresponding to the guest physical storage cell's source address, which forms an intercept with the host's physical storage cell address and the type of access (read/write/execute) used to ensure the validity of the virtual host addresses. Once this is done, the address of the guest physical storage location can be immediately available with this type of access to the guest virtual machine 271. For example, a parallel virtual processor in the guest virtual machine 271 can immediately access such an address without hijacking. The original trap processing can be completed, and the original VP that generates the trap can re-execute its instruction and proceed to access the storage device now that the SLAT contains a table entry that can correlate the requested physical address of the guest with the corresponding address of the physical storage location. host devices.

[0053] If and/or when the host storage manager 241 determines the need to perform any action that may or should change the physical host address reservation of the virtual host address that is set valid via virtual failure, it may flush the translation buffer (TLB) to do so. host virtual address. It may already perform such an action to comply with the current convention that the host storage manager 241 may have with hardware CPUs on the host. The virtualization stack 230 can intercept such TLB flushes and invalidate the corresponding SLAT records of any virtual host addresses that are being flushed that reserve any guest physical storage cell addresses in any virtual machines. A TLB flush call may identify the range of virtual addresses to be flushed. The virtualization stack 230 can then search for cleanup virtual host addresses relative to its data structures, which can be indexed by the virtual host address, to find guest physical ranges that can be reserved by the given virtual host address. If any such ranges are found, SLAT records corresponding to those guest physical storage cell addresses may be invalidated. Additionally, the host storage manager may handle virtual allocations that reserve virtual storage differently as needed or desired to optimize TLB flush behavior (e.g., to reduce SLAT invalidation time, subsequent storage grabs, etc.)

[0054] The virtualization stack 230 can carefully synchronize the SLAT 220 update with the host's physical storage page number returned from the virtual fault (which is maintained by the storage manager 241) relative to the TLB cleanups performed by the host (which are issued by the storage manager 241 ). This may be to avoid adding complex synchronization between the host storage manager 241 and the virtualization stack 230 . The physical page number returned by virtual fault may not be up to date by the time it is returned to the virtualization stack 230 . For example, virtual addresses may already be invalidated. By intercepting TLB flush calls from the host storage manager 241, the virtualization stack 230 can know when this race condition occurs and retry the virtual failure to obtain an updated physical page number.

[0055] When the virtualization stack 230 invalidates the SLAT entry, any subsequent access to that guest physical storage cell address by the virtual machine 271 again generates a trap to the hypervisor 210, which in turn is forwarded to the virtualization stack 230 to be resolved as described above. The same process may be repeated when the location address of the guest physical storage device is accessed for reading first and then later written to. The write forms a separate trap because a SLAT write can only be specified as valid with an access type of "read". This intercept may be redirected to the virtualization stack 230 as usual, and a virtual failure with "write" access may be issued to the host storage manager 241 for the corresponding virtual address. The host storage manager 241 may update its internal state (typically in a page table entry (or "PTE")) to indicate that the host's physical storage page is now dirty. This may be done before allowing the virtual machine to write to its address of guest physical storage cells, thereby avoiding data loss and/or corruption. If and/or when the host storage manager 241 determines that this virtual address needs to be tampered with (which should perform a TLB flush and invalidate the corresponding SLAT entry as a result), the host storage manager 241 may know that the page is dirty and should be written to a non-volatile computer-readable storage medium, such as a paging file on a hard disk drive, until remapped. Thus, the sequence described above is no different from what would occur with a regular private virtual allocation for any other process running on the computing host device 100.

[0056] As one optimization, the host storage manager 241 may choose to perform a page combining pass across its entire storage 120. This may be an operation in which the host storage manager 241 finds identical pages for all processes and combines them into one a non-rewritable copy of the page that is shared by all processes. If and/or when any of the combined virtual addresses is written, the storage device manager 241 may perform a copy-on-write operation to allow the write to continue. Such optimization can now work transparently for virtual machines, such as exemplary virtual machines 261 and 271, to increase the density of virtual machines running on a given computing device by combining identical pages on virtual machines and thereby reducing storage consumption. When page combining occurs, the host storage manager 241 can update the PTEs that translate the affected virtual addresses. During this update, it may perform a TLB cleanup because the host's physical storage location address may change for these virtual addresses from a unique private page to a shared page. As part of this, as described above, the virtualization stack 230 may invalidate the corresponding SLAT entries. If and/or when addresses of guest physical storage cells whose virtual addresses are combined to point to a shared page are read, virtual fault resolution may return the physical page number of the shared page during trap processing, and SLAT 220 may be updated, to point to a shared page.

[0057] If any of the combined guest physical storage cell addresses are being written by the virtual machine, the write-access virtual fault may perform a copy-on-write operation, and the new host physical storage private page number may be returned and updated in the SLAT 220. For example, the virtualization stack 230 may direct the host storage manager 241 to perform a page combining pass. In some embodiments, the virtualization stack 230 may indicate which part of the storage device is to be scanned for combining, or which processes are to be scanned. For example, virtualization stack 230 may identify processes, such as exemplary virtual machine processes 260 and 270, whose host virtual storage allocations reserve the guest physical storage of respective virtual machines, namely exemplary virtual machines 261 and 271, as being processes that should be scanned for combination.

[0058] Even when SLAT 220 is updated to enable write access due to a virtual write failure, hypervisor 210 can support triggering write captures to such SLAT records, upon request, by virtualization stack 230. This can be useful because the virtualization stack 230 may want to know when entries occur, regardless of the fact that it is valid for the host storage manager 241 that these entries occur. For example, live migration of virtual machines or snapshots of virtual machines may entail monitoring records through the stack 230 virtualization. The virtualization stack 230 can still be notified when writes occur even if the state of the host storage manager has already been updated accordingly for writes, such as if the PTE is already marked dirty.

[0059] Host storage manager 241 may be able to maintain an accurate access history for each host virtual page reserving guest physical storage address space, identical to regular host virtual pages allocated in any other process's address space. For example, the "bit to access" in the PTE may be updated during virtual failures performed as part of the processing of memory traps. When the host storage manager clears the access bit on any PTE, it may already clear the TLB to avoid corrupting the contents of the storage device. As described above, this TLB flush can invalidate the corresponding SLAT entry, which can in turn generate an access hijack if the virtual machine accesses its guest physical storage location address again. As part of the interception processing, the virtual failure handling in the host storage manager 241 may set the access bit again, thereby maintaining the proper access history for the page. Alternatively, for performance reasons, such as to avoid hijacking in hypervisor 210 as much as possible, host storage manager 241 may consume page access information directly from hypervisor 210 collected from SLAT records if supported by the underlying hardware. Host storage manager 241 can interact with virtualization stack 230 to translate access information in SLAT 220 (which is organized by guest physical storage cell addresses) to host virtual storage cell addresses reserving those guest physical storage cell addresses, to know what addresses have been accessed.

[0060] By having an accurate access history for pages, the host storage manager 241 can perform its usual intelligent training and process working set adjustment algorithms. This may allow the host storage manager 241 to analyze the state of the entire system and make intelligent choices as to which addresses should be tampered with and/or pumped, page-level, to disk, or other similar operations in order to alleviate force pressure. lack of a storage device if necessary, or for other reasons.

[0061] In some embodiments, virtual and physical storage limits may be imposed on virtual machines by the host storage manager 241 in an identical manner to any other process for the system. This may assist the system administrator to sandbox or otherwise restrict or enable virtual machines, such as exemplary virtual machines 261 and 271. The host system may use the same mechanisms to achieve this as it would for its own processes. For example, in some embodiments where higher performance is desired, the virtual machine may have all of its guest physical storage backed up directly by the host's physical storage. Alternatively, portions may be backed up by host virtual storage while other portions are backed up by host physical storage 120. As yet another example, if lower performance may be acceptable, the virtual machine may be backed up primarily by host virtual storage, and the host virtual storage may be limited to partial redundancy by the host physical storage. For example, a virtual machine, such as exemplary virtual machine 271, may represent 4 GB of guest physical storage, which in turn, using the processes described above, may be backed up by 4 GB of host virtual storage. However, host virtual storage may be limited to being backed up by only 2 GB of host physical storage. This may cause disk paging or other performance hindrance, but may be a way for administrators to enforce service level throttling or other control for virtual machine deployments. Likewise, a certain amount of physical storage may be guaranteed for a virtual machine (while allowing the virtual machine to be backed up by host virtual storage) maintained by the host storage manager in order to provide a certain consistent level of performance.

[0062] The amount of guest physical storage present in the virtual machine environment may change dynamically. When a guest physical storage device is to be added, a different host virtual storage cell address range may be allocated as described above. Once the virtualization stack 230 is ready to handle storage hijacks, the guest physical storage cell address range can be added to the virtual machine environment. When the guest physical storage cell addresses are deleted, portions of the host virtual address range reserving the deleted guest physical storage cell addresses can be freed by the host storage manager 241 (and updated accordingly in the virtualization stack 230 data structures). In addition, or in addition, various host storage manager APIs can be called on these portions of the host virtual address range in order to free host physical storage pages without releasing host virtual address space for them. Alternatively, in some embodiments, it is possible to do nothing at all, since the host storage manager 241 may eventually rearrange these pages from the working set and eventually write them to disk, for example, to a paging file, since in practice to it should no longer be accessed.

[0063] According to one aspect, SLAT 220 may be pre-populated with some or all of the translations of guest physical storage cell addresses to host physical storage cell addresses. This reduces the number of failover operations that are performed when the virtual machine is initialized. However, as the virtual machine is running, entries in SLAT 220 may be invalidated for various reasons, and the failover described above may be used to once again correlate guest physical storage cell addresses with physical storage cell addresses. host storage device. SLAT records may be prepopulated before the virtual computing environment bootstraps or at run time. Additionally, the entire SLAT 220 or only parts of it may be prefilled.

[0064] Another optimization may be to prefetch, into the physical host storage, additional portions of the host virtual storage, reserving the guest physical storage that has previously been page-level deflated such that when a subsequent storage hijack occurs, a virtual failure can be satisfied more quickly because it can be satisfied without having to go to the disk to read the data.

[0065] Referring to FIG. 4, a method 400 is illustrated providing an overview of the mechanisms detailed above. Method 400 may include steps for reserving guest physical storage with host virtual storage. The method includes, from a virtual machine when executing on a host computing device, attempting to access a guest physical storage device using guest physical storage access (block 402). For example, the virtual machine environment 271 shown in FIG. 2 can access a guest physical storage device that, to processes running inside the virtual machine environment 271, appears to be the actual physical storage device.

[0066] The method 400 can further include determining that the guest physical storage access is accessing a guest physical storage cell address that does not have a valid entry in a data structure that maps guest physical storage cell addresses to physical storage cell addresses. host storage device, (block 404). For example, a determination may be made that there are no valid entries in SLAT 220 shown in FIG. 2.

[0067] As a result, method 400 may include identifying a host virtual storage cell address that corresponds to a guest physical storage cell address and identifying a host physical storage cell address that corresponds to a host virtual storage cell address (block 406) . For example, the virtualization stack 230 shown in FIG. 2 can identify the host virtual storage slot address that corresponds to the guest physical storage slot address, and the storage manager 241, also shown in FIG. 2 can identify a host physical storage location address that corresponds to a host virtual storage location address.

[0068] Method 400 can further include updating a data structure that correlates guest physical storage cell addresses with host physical storage cell addresses, correlating the guest physical storage cell address and the identified host physical storage cell address (block 408) . For example, the virtualization stack 230 shown in FIG. 2 can obtain the host's physical storage location address from the storage manager 241, also shown in FIG. 2 and update SLAT 220 (shown in FIG. 2) with the correlation of the guest physical storage cell address and the identified host physical storage cell address.

[0069] Method 400 may be practiced by instructing interception. The capture can be redirected to the virtualization stack on the host. This may instruct the virtualization stack to identify the host virtual storage cell address that matches the guest physical storage cell address and fail the storage manager to obtain the host physical storage cell address that matches the host virtual storage cell address. . The virtualization stack can then update a data structure that correlates guest physical storage cell addresses with host physical storage cell addresses, correlating the guest physical storage cell address and the identified host physical storage cell address.

[0070] The method 400 can further include determining a type to access the guest physical storage and updating a data structure that maps guest physical storage cell addresses to host physical storage cell addresses, with the determined type correlated with the guest physical storage cell address. storage device and the identified location address of the physical storage device of the host. For example, if the guest physical storage access is a read, the SLAT may be updated to indicate this.

[0071] The method 400 can further include performing an action that can change the host physical storage cell address reserving the host virtual storage cell address. As a result, the method may include invalidating a record correlating a guest physical storage cell address with a host physical storage cell address in a data structure that maps guest physical storage cell addresses to host physical storage cell addresses. This may cause subsequent access to the guest physical storage cell address to generate a fault that can be used to update a data structure that maps guest physical storage cell addresses to host physical storage cell addresses, with the correct correlation for a virtual storage device of the host that reserves the address of the cell of the guest physical storage device. For example, the action may include a page combining operation. Page aggregation can be used to increase the density of virtual machines on a host.

[0072] Method 400 may include initializing a guest virtual machine. As part of initializing the guest virtual machine, method 400 may include prepopulating at least a data portion structure that maps guest physical storage cell addresses to host physical storage cell addresses with some or all of the guest physical storage cell address translations. devices to host physical storage cell addresses for the guest virtual machine. Thus, for example, physical host storage may be pre-allocated to a virtual machine, and appropriate correlations may be entered into the SLAT. This should result in fewer exceptions being needed in order to initialize the guest VM.

[0073] Referring now to FIG. 5, an exemplary workflow 500 is illustrated showing various actions that may occur in terms of the lifetime of some data at an exemplary guest physical storage location address (hereinafter abbreviated as "GPA") of 0x1000. As illustrated at 502, the SLAT entry for GPA 0x1000 is invalid, which means that there are no SLAT entries for this particular GPA. As illustrated at 504, the virtual machine attempts to perform a read at GPA 0x1000 causing a read interception by the virtual machine ((hereinafter abbreviated "VM"). As illustrated at 506, the hypervisor redirects the interception to the virtualization stack on the host. At 508, the virtualization stack executes a virtualization lookup for a host virtual storage (VA) cell address corresponding to GPA 0x1000 The lookup results in VA 0x8501000 At 510, a virtual fault is configured for read access to VA 0x8501000 Virtual fault handling from the storage manager device returns a system physical address (hereinafter abbreviated as "SPA") at 0x88000 specifying an address in system storage in which data is physically located at GPA 0x1000. Therefore, as illustrated at 514, the SLAT is updated to correlate with GPA 0x1000 with SPA 0x88000 and mark data access as read-only.At 516, the virtualization stack and finishes processing the read hooks, and the hypervisor resumes executing the guest virtual machine.

[0074] As illustrated at 518, time passes. At 520, the virtual machine attempts a write access to GPA 0x1000. At 522, the hypervisor redirects write access to the virtualization stack on the host. At 524, the virtualization stack performs a virtualization search for the host VA for GPA 0x1000. As noted above, it runs in VA 0x8501000. At 526, a virtual failure occurs for write access to VA 0x8501000. At 528, virtual failure returns SPA 0388000 in physical storage. At 530, the SLAT entry for GPA 0x1000 is updated to indicate that the data access is read/write. At 532, the virtualization stack finishes processing the write captures. The hypervisor resumes running the guest virtual machine.

[0075] As illustrated at 534, some time passes. At 536, the host storage manager performs a page combining pass in order to combine all pages in the host's physical storage that are functionally identical. At 538, the host storage manager finds possible combinations for VA 0x8501000 and another virtual address in another process. At 540, the host performs a TLB cleanup for VA 0x8501000. At 542, the virtualization stack intercepts the TLB cleanup. At 544, the SLAT entry for GPA 0x1000 is invalid. At 546, virtual machine hijacking is performed for GPA 0x1000. At 548, a virtual failure occurs for read access to VA 0x8501000. At 550, the virtual fault returns SPA 0x52000, which is the shared page for N processes from the page combining pass at 536. At 552, the SLAT entry for GPA 0x1000 is updated to match SPA 0x52000 , with access set to read-only.

[0076] As illustrated at 554, some time passes. At 556, a VM write hijack occurs for GPA 0x1000. At 558, a virtual failure occurs for write access to VA 0x8501000. At 560, the host storage manager performs a copy-on-write for VA 0x8501000. At 562, the host performs a TLB cleanup for VA 0x850100. As illustrated at 564, this results in the SLAT entry for GPA 031000 being invalidated. At 566, virtual failure returns SPA 0x11000, which is a private page after copy-on-write. At 568, the SLAT entry for GPA 0x1000 is updated to SPA 0x1000, with access set to "read/write". At 570, the virtualization stack finishes processing the read captures and the hypervisor resumes executing the virtual machine.

[0077] Thus, as illustrated above, the physical address space of the virtual machine is reserved by host virtual storage (typically allocated in the user address space of the host process), which is subject to regular virtual storage management by the host storage manager. The virtual storage backing up the virtual machine's physical storage may be of any type supported by the host storage manager 118 (private allocation, file conversion, paging file-backed partition conversions, large page allocation, etc.) the host storage manager can perform its existing operations and enforce policies on the virtual storage and/or apply custom policies with the knowledge that the virtual storage will reserve the virtual machine's physical address space as needed.

[0078] Referring to FIG. 6, the exemplary system 600 shown here contains a block representation of the mechanisms summarized in FIG. 4 and detailed in FIG. 5 as described above. More specifically, guest virtual storage 311, guest physical storage 312, host virtual storage 321, and host physical storage 322 are illustrated as rectangular blocks whose width represents the storage range. For ease of illustration, the rectangular blocks are approximately equal in width even though, in practical operation, the amount of virtual storage is likely to exceed the amount of physical storage backing up such virtual storage.

[0079] As detailed above, when a process running within a virtual machine computing environment, such as the exemplary virtual machine computing environment 271 shown in FIG. 2 accesses a portion of a virtual storage device represented by an operating system running within such a virtual machine computing environment, that operating system's page table, such as the exemplary page table 283, may contain a PTE that may correlate a virtual storage location address to accessed with a physical storage location address at least perceptible by processes executing within the virtual machine's computing environment. Thus, for example, if the virtual storage device represented by the area 611 is accessed, the PTE 631, which may be part of the page table 283, can correlate this area 611 of the guest virtual storage device 311 with the area 621 of the guest physical storage device 312. As detailed above, the guest physical storage 312 may be reserved by a portion of the virtual storage of the host 321. Thus, the virtualization stack 230 described above may comprise a data structure that may include an entry 651 that may correlate the region 621 of the guest physical storage 312 with the host virtual storage area 641 321. Processes running on the computing host device including the page table 250 described above can then correlate the host virtual storage area 641 321 with the host physical storage area 661 322. As also described in detail above, SLAT 220 may contain a hierarchically organized set of tables that can be updated with a table entry 691 that can correlate the guest physical storage area 621 312 with the physical storage area 661 host 322. More specifically, mechanisms, such as those implemented by virtualization stack 230, may detect a correlation between area 621 and area 661, and may update or generate a table entry, such as entry 691, in SLAT 220, as illustrated by step 680, so it includes such a correlation. Thus, guest physical storage 312 can be backed up by host virtual storage 321 while continuing to allow existing mechanisms, including SLAT 220, to function in the traditional manner. For example, a subsequent access to the area 611 of the guest virtual storage device 311 of a process executing within that virtual machine environment may entail two page table lookups in the conventional manner: (1) a page table lookup performed in the virtual machine environment by accessing a page table 283 that may contain an entry, such as entry 631, that can correlate the requested area 611 with the corresponding area 621 in the guest physical storage 312, and (2) a page table lookup performed on the host computing device by accessing the SLAT 220 that may contain an entry, such as entry 691, that may correlate area 621 in guest physical storage 312 with area 661 in host physical storage 322, thereby completing the path to the relevant data stored in host physical storage.

[0080] As also detailed above, various page tables, such as an exemplary page table 283 in a virtual storage computing environment, an exemplary page table 250 on a computing host device, and an exemplary SLAT 220, may contain hierarchically organized levels of tables such that entries at the hierarchically lowest level of tables may identify "small pages" of storage, as the term is explicitly defined herein, which may represent the smallest range of storage cell addresses that can be separately and moderately maintained and managed through processes using the appropriate tables pages. In the exemplary system 600 shown in FIG. 6, various page table entries (PTEs) 631, 671, and 691 may reside at this lowest table level such that areas 611, 621, 641, and 661 may represent small memory pages. As detailed above, in one common microprocessor architecture, such small memory pages, as the term is explicitly defined herein, may contain 4 KB of contiguous memory cell addresses.

[0081] According to one aspect, in order to improve the speed and efficiency of accessing storage from a virtual machine computing environment whose physical storage is backed up by the virtual storage of the host computing device, SLAT 220 can maintain correlations at hierarchically upper levels of tables. In other words, SLAT 220 can correlate "Large Pages" of storage or "Huge Pages" of storage, as those terms are explicitly defined herein. In one common microprocessor architecture, large memory pages, when the term is explicitly defined herein, may contain 2 MB of contiguous memory cell addresses, and huge memory pages, when the term is explicitly defined herein, may contain 1 GB of contiguous memory cell addresses. On the other hand, as mentioned above, the terms "small page", "large page", and "huge page" are explicitly defined with reference to a hierarchical level, in a hierarchically organized set of page tables, and are not defined based on a specific storage capacity, since such storage capacities may vary between different microprocessor architectures, operating system architectures, and the like.

[0082] Referring to FIG. 7, one mechanism is shown for creating large page records in SLAT 220 and thereby improving the speed and efficiency of storage access from a virtual machine computing environment whose physical storage is backed up by the virtual storage of the host computing device. As shown in FIG. 6, in the system 700 shown in FIG. 7, guest virtual storage 311, guest physical storage 312, host virtual storage 321, and host physical storage 322 are illustrated as rectangular blocks whose width represents the storage range. Additionally, access to area 611 may continue in the manner detailed above and shown in FIG. 6. However, instead of generating a hierarchically lowest-level table entry in SLAT 220, the mechanisms described herein may generate a higher-level table entry, such as an exemplary table entry 711. As detailed above, such a higher-level table entry levels can correlate large pages or huge storage pages. Accordingly, when virtualization stack 230 instructs entry of table entry 711 into SLAT 220, table entry 711 may correlate large page size area 761 of guest physical storage 312 with large page size area 720 of host physical storage 322. However, as more described below, such large page size regions do not represent large pages from the point of view of a storage manager running on a computing host device using a 250 page table, and as a result, such large page size regions, for example, are not subject to pumpout, at the page level, as one large page, or otherwise processed as one indivisible large page by a storage manager running on the host computing device.

[0083] Conversely, in order to maintain the efficiency, density, and other benefits provided by the mechanisms detailed above, which allow guest physical storage, such as exemplary guest physical storage 312, to be backed up by host virtual storage, such as the exemplary host virtual storage device 321, the page table 250 executing on the host may not contain a higher level table entry similar to the higher level table entry 711 in SLAT 220, but may instead simply contain lower level table entries such as the exemplary lower level table entries 671, 731 and 732 shown in FIG. 7. More specifically, a particular set of lower level table entries in page table 250, such as exemplary lower level table entries 671, 731, 732, etc., can identify contiguous ranges of host physical storage 322 such that the cumulative the contiguous physical storage range of the host 322, identified by the entire equivalent sequence of lower level table entries in the page table 250, spans a storage range identical to the storage range for a single higher level table entry 711 in the SLAT 220. Thus, as one For example, in a microprocessor architecture where small pages are 4 KB in size and large pages are 2 MB in size, 512 contiguous small page entries in page table 250 can collectively identify contiguous 2 MB of host physical storage 322.

[0084] Because a virtual fault may not be generated for the entire area of a large page size storage device, only specific lower level table entries, such as exemplary lower level table entries 671, 731, and 732, may be used, while the remaining table entries are more low level may remain marked as free storage. For example, an application running in a virtual machine computing environment using guest physical storage 312 may initially require only one small page of storage. In such a case, one higher level table entry 711 may identify a large page size storage area, eg, a large page size area 720, as being in use. However, from the point of view of the storage manager of the computing host device, when referring to page table 250, only one of the lower level table entries, such as exemplary lower table entry 671, may be indicated as being in use, with the rest being indicated. as available. To prevent other entries from being treated as available, virtualization stack 230 may mark remaining lower level table entries, such as exemplary lower level table entries 731, 732, etc., as also in use. When an application running in the virtual machine's computing environment then needs to use additional storage spaces with a small page size, the virtualization stack 230 may use a storage cell location previously indicated as being in use, but which are not actually used yet by the application running in the computing environment. virtual machine to meet the additional storage requirements of the application.

[0085] According to one aspect, keeping track of an equivalent sequence of lower level table entries in the page table 250, such as the above notation, may be coordinated by the virtualization stack 230, as illustrated by block 730 in FIG. 7. In such a case, if the storage manager running on the host makes changes to one or more of these lower level table entries, the virtualization stack 230 can initiate appropriate changes to the corresponding entries in SLAT 220, such as the higher level table entry 711.

[0086] A sequence of lower level table entries in page table 250, which is equivalent to higher level table entry 711 in SLAT 220, may correlate a sequence of host virtual storage ranges, such as exemplary ranges 641, 741, and 742, with physical storage ranges. host devices, such as the exemplary ranges 661, 721, and 722, respectively. Therefore, a large page size virtual storage area of host 321, such as exemplary large page size area 751, is mapped to a large page size physical storage area of host 322, such as exemplary large page size area 720, via a sequence of table entries. lower level in the page table 250, namely, through exemplary entries 671, 731, 732 of the lower level table, etc. The virtualization stack 230 can support data structures such as hierarchically organized tables that can coordinate host virtual storage cell locations with guest physical storage cell locations. Thus, the virtualization stack may maintain one or more data records, such as an exemplary data record 771 that can correlate a large page size region 751 of host virtual storage 321 with a corresponding large page size region 761 of guest physical storage 312. Although the record 771 data is illustrated as a single entry, the virtualization stack 230 can support the above correlation as a single entry, as multiple entries, for example, by separately correlating subparts of area 761 with an area 751 including subparts that have a small page size, or as a combination of the above. To complete the loop, the above higher level table entry 711 in SLAT 220 can then correlate the large page size area 761 in the guest physical storage 312 with the large page size area 720 in the host physical storage 322. On the other hand, from the point of view of SLAT 220 having only one higher table entry 711, the large page size areas 720 and 761 are large pages that are unitarily processed by SLAT (according to one higher table entry 711), then how, from the point of view of the storage manager running on the host, the page table 250 and, in fact, the virtualization stack 230, such areas are not unitary, but rather consist of separately managed areas with small pages, identified, for example, by writing a table over low level in a 250 page table.

[0087] The availability of contiguous small storage pages in guest physical storage 312, equivalent to one or more large or huge storage pages, as these terms are defined herein, can be simple, since guest physical storage 312 is perceived, through processes, running inside the corresponding virtual machine computing environment, like physical storage. Therefore, the following descriptions focus on the adjacency of host physical storage 322. Additionally, since guest physical storage 312 is treated as physical storage, full storage access permissions (eg, "read/write/execute" permissions) remain over the entire range of the guest physical storage 312, and, accordingly, it is unlikely that there will be discontinuity in storage access permissions between the lower level table entries in the page table 250.

[0088] With focus on the page table 250 of the computing host device, if one or more areas of the host 322 physical storage device with a large page size remain unused, according to one aspect, when a virtual fault, as detailed above, is initiated for a small page in a storage range delimited into a large page size area that remains unused, remaining small pages in that large page size area, one higher level table entry, such as exemplary higher level table entry 711, may be generated in SLAT 220.

[0089] However, since the large page 720 corresponding to the higher level table entry 711, from the point of view of the page table 250, is a sequence of small pages, such as exemplary small pages 661, 721, 722, etc., due to sequence of lower level table entries, such as example lower level table entries 671, 731, 732, etc., storage management mechanisms using such a page table 250 may process each of the smaller pages separately, which may include paging such small pages to a non-volatile storage medium such as a hard disk drive. In such a case, according to one aspect, the higher level table entry 711, in SLAT 220, may be replaced by an equivalent sequence of lower level table entries. More specifically, the lower level table entries generated in SLAT 220 may be contiguous and, collectively, may refer to the same range of storage cell addresses as the higher level table entry 711, except that particular table entries lower level corresponding to pages that have been page-level pumped by the storage manager may not be present or otherwise not created.

[0090] According to other aspects, if the large or huge page size physical storage area of the host 322 is unavailable at the time the virtual failure as detailed above is triggered, the available large or huge page size host physical storage area may be constructed at interception time by assembling an appropriate number of contiguous small pages. For example, a large page size area may be constructed from contiguous small pages that are available from a "free list" or other similar enumeration of available pages of the host's physical storage. As another example, if small pages currently in use by other processes are required to establish the continuity necessary to assemble a sufficient number of small pages into a single large page size region, these small pages can be derived from such other processes, and the data they contain, may be transferred to other small pages, or may be pumped, at the page level, to disk. Once such a large page size area is constructed, virtual failover processing may proceed in the manner detailed above, including generating a higher level table entry, such as exemplary higher level table entry 711, in SLAT 220.

[0091] In some cases, a storage manager executing on a computing host device, when using the page table 250, may implement background or opportunistic mechanisms whereby large or huge page size accessible areas are constructed from a sufficient number of contiguous small pages. To the extent that such mechanisms result in a large page size available area, for example, when a virtual fault is triggered, processing may continue in the manner indicated above. However, to the extent that such mechanisms do not yet complete assembly of the larger page size available region, the construction of such a larger page size region may complete during a higher priority capture. For example, a process constructing such a large page size region may be given a higher execution priority, or may move from the background to the foreground, or may otherwise execute more aggressively.

[0092] Alternatively, if a larger page size area of the host's physical storage is unavailable when the virtual fault is triggered, processing may continue as detailed above using multiple smaller pages. Then, when the large page size area becomes available, data from several small pages previously in use (due to the large page size area being unavailable at the time) may be copied to the large page, and the previously used small pages may subsequently be freed. In such a case, the lower level table entries in SLAT 220 may be replaced by a single higher level table entry, such as exemplary higher level table entry 711.

[0093] Additionally, the parameters according to which larger page size regions are designed, whether during interception or opportunistically, may vary according to the balance between faster storage access due to skipping hierarchical table levels during SLAT search and initial delay in constructing an area with a large page size from small pages. One such parameter may be the number of contiguous small pages sufficient to initiate a page-level swap or rollback of other small pages needed to complete the adjacency for the entire large page size area. For example, if 512 contiguous small pages are required to construct a large page, and contiguous ranges of 200 small pages and 311 small pages exist, with one small page in between currently being used by another process, such a small page may be pumped at the pages or to be exchanged for another available small page such that all 512 contiguous small pages can be made available for construction as a single large page size area. In such an example, the fragmentation of available small pages can be very low. In contrast, continuous ranges of only 20-30 small pages that are constantly interrupted by other small pages currently being used by other processes may describe a small page range that has very high fragmentation. While such a highly fragmented set of small pages may still be exchanged, page-level pumped, or otherwise shuffled to form a contiguous range of small pages equivalent to a larger page size area, such an effort may take significantly longer. Accordingly, in one aspect, a fragmentation threshold may be set that may delimit whether or not efforts are made to construct a larger page size area from ranges of smaller pages having higher or lower fragmentation.

[0094] According to one aspect, constructing a large page size region can take advantage of existing small page usages through processes whose storage is used to reserve guest physical storage of virtual machine computing environments. As a simple example, if contiguous ranges of 200 small pages and 311 small pages have already been used by a process whose storage is backed up by guest physical storage 312 and only one small page between two contiguous ranges is required in order to establish a contiguous range of small pages equivalent to a large page, in such a case, after this small page is freed, for example, through a page-level rollback, or a swap, the only data to be copied may be the data corresponding to this one small page, while the remaining data may remain in place even though the corresponding lower level table entries in SLAT 220 may be invalidated and replaced with a single higher level table entry spanning an identical storage range.

[0095] To avoid the need to reconstruct large page size storage areas from contiguous ranges of small pages, an existing set of contiguous lower level table entries in page table 250 that collectively span an equivalent storage range with one higher table entry 711 level in SLAT 220 can be blocked in such a way that they can avoid paging. Thus, for example, the virtualization stack 230 may request that the lower level table entries 671, 731, 732, etc. be blocked in such a way that the corresponding ranges 661, 721, 722 of the physical storage device of the host, etc. can retain the data stored in them without paging to disk. According to one aspect, the decision, for example, by the virtualization stack 230, to request a lock on such records may depend on various factors. For example, one such factor may be the frequency of use of the data stored in these storage ranges, with more frequently used data resulting in records being locked and less frequently used data resulting in records being unlocked later. Other factors, such as the amount of system-wide storage fragmentation, the need for greater density of virtual machine computing environments on the host computing device, and other similar factors may be equally considered in determining whether or not to query what page table entries, higher-level tables that support writing to SLAT should be blocked.

[0096] Referring to FIG. 8, the flowchart 800 shown therein illustrates the above mechanisms as an exemplary sequence of steps. Initially, at 810, a virtual failure may occur, as detailed above. Then, at step 815, a determination can be made as to whether or not the virtual failure of step 810 is accessing a storage device in the large page size storage area, while no other storage device in the large page size area has been previously accessed. through virtual failure. In particular, the physical storage device of the host may be delimited into segments with a large page size. The first virtual failure accessing the storage device in one area with a large page size may result in a positive determination at block 815, whereby processing may proceed to block 835.

[0097] At step 835, one higher level table entry may be formed in the SLAT, while, accordingly, at step 840, multiple lower level table entries may be used in the host page table, in which the relevant number of multiple lower level table entries is the number that covers the storage range identical to the storage range for one entry of the higher level table formed in SLAT, namely, the storage range corresponding to the demarcated area with a large page size of the storage device containing the location of the storage cell, whose access initiates a virtual failure at step 810. As noted above, since the host page table contains multiple lower level table entries, as opposed to a single higher level table entry, storage management of the computing host device The property may choose to pump out, eg, by copying the content to disk, one or more storage areas or pages identified by such lower-level table entries in the host's page table. If such a pageout occurs, as determined at block 845, processing may proceed to block 850, and the higher level table entry in the SLAT may be replaced with multiple lower level table entries corresponding to the storage areas referenced by the lower level table entries in the SLAT. the host page table that is not paged out (and excluding SLAT, the level table entries corresponding to the storage areas referenced by the lower level table entries in the host page table that are actually paged out).

[0098] According to one aspect, if small pages from a large page size storage area are paged out at step 845 and the higher level table entry in the SLAT is invalidated and replaced with a corresponding sequence of lower level table entries (excluding any table entries lower level referring to paged out small pages), then optionally, processing may proceed to block 855 to continue checking for available large page size storage areas that become free. As detailed above, storage management processes running on a computing host device, for example, can opportunistically reclaim large page size areas of available storage. If such large page size storage areas become available, as determined at block 855, processing may proceed to block 860 where the lower level table entries in the SLAT may be replaced with a single higher level table entry in the SLAT, and if necessary, the data may be copied from storage areas referenced by previous lower-level table entries in the storage area now referenced by a single higher-level table entry (if the two storage areas are different).

[0099] Returning to step 815, if the virtual failure of step 810 is not the first for the reference memory in the large page size pre-delimited area, processing may proceed to step 820. At step 820, a determination may be made as to whether or not a large page is created at the time of interception, for example, in the manner detailed above. More specifically, if steps 835 and 840 were previously performed for a storage area with a large page size, and the SLAT now contains a single higher level table entry while the page table contains equivalent lower level table entries referring to subparts of the storage area referenced by a single higher table entry in the SLAT, then a subsequent storage access directed to any storage cell locations in the storage area referenced by the single higher table entry in the SLAT shall not trigger a virtual fault. as detailed above. Thus, if a virtual fault is triggered at step 810, and at step 815, it is determined that the virtual fault is not directed first to storage cell locations in a pre-delimited area with a large memory page size, then the virtual fault triggered at step 810, is highly likely triggered because steps 835 and 840 were previously performed for storage cell locations in this large page size area, but subsequently, one or more smaller pages that contain this large page size storage area are paged out as determined at block 845, and thus block 850 has previously been executed. Thus, at block 820, a determination may be made as to whether or not a storage area with a large page size should be constructed at the time of interception. If such a large page size area is to be constructed, then processing may proceed to block 830 and an appropriate number of contiguous small pages may be assembled as detailed above. Processing may then proceed to block 835 as above. On the other hand, if, at block 830, such construction on request of large page size available storage areas is not requested, processing may proceed to use lower level table entries in the host page table and SLAT in accordance with the mechanisms described in detail above with with reference to FIG. 4 and 5.

[00100] The above descriptions include, as a first example, a method for increasing a computer storage device access rate, the method comprising: detecting a first storage device access, from a first process running in a virtual machine computing environment directed to a first storage range devices; forming, as a precondition for performing the first access to the storage device, a first entry in a hierarchically organized second level address translation table, wherein the hierarchically organized second level address translation table maps host physical storage cell addresses to guest physical storage cell addresses, the first the entry is located at least one hierarchical level above the hierarchically lowest table level such that the second storage range identified by the first entry can be identified without reference to the tables at the hierarchically lowest table level at all, the second storage range greater than the first storage range; and in response to generating a first entry in the second level hierarchical address translation table, marking as in use the first set of entries in the hierarchical page table, the hierarchically organized page table mapping host physical storage cell addresses to host virtual storage cell addresses, the first the plurality of entries refer, collectively, to the same second storage range as the first entry in the hierarchically organized second level address translation table, wherein the entries from the first plurality of entries are at the hierarchically lowest level of the tables; wherein the addresses of the cells of the guest physical storage device are perceived as addresses in the physical storage device by processes running within the computing environment of the virtual machine; wherein the physical storage cell addresses of the host are addresses in the actual physical storage of the host computing device accommodating the virtual machine computing environment; wherein the host virtual storage cell addresses are addresses in a virtual storage provided by a storage manager running on a computing host device, the storage manager using a hierarchically organized page table to provide the virtual storage; and wherein the guest physical storage device identified by the cell addresses of the guest physical storage device is reserved by the host virtual storage portion identified by the cell address portion of the host virtual storage device.

[00101] The second example is a method of the first example, further comprising: detecting a second storage access from a first process running in the virtual machine computing environment, wherein the second storage access is directed to a third storage range that is different from the first storage range. devices; and satisfying the second access to the storage device by referring to the second subset of the first set of entries in the hierarchically organized page table; wherein the first storage access is satisfied by accessing a first subset of the first set of entries in the hierarchically organized page table, the first subset containing different entries in the hierarchically organized page table relative to the second subset.

[00102] The third example is a method of the first example, further comprising: detecting, after the first storage access is completed, that the first subset of the first set of entries in the hierarchically organized page table has data that is initially stored in the corresponding cell addresses the host's physical storage device, then deflated, at the page level, to a non-volatile storage medium; invalidating, in response to the discovery, the first entry in the hierarchically organized second level address translation table; and forming, instead of the first entry in the hierarchically organized second level address translation table, a second set of entries in the hierarchically organized second level address translation table, wherein the second set of entries refer, in the aggregate, to at least a portion of the same second storage range, as the first record, while the records from the second set of records are at the hierarchically lowest level of the tables.

[00103] The fourth example is the method of the third example, in which the second set of records access portions of the second storage range previously accessed by the first process and not paged out.

[00104] The fifth example is the method of the first example, further comprising: assembling a first plurality of contiguous small page size host physical storage areas into a single large page size host physical storage area.

[00105] The sixth example is the method of the fifth example, in which the assembly occurs after the detection of the first access to the storage device and before the formation of the first entry in the hierarchically organized second level address translation table.

[00106] The seventh example is a method of the fifth example, further comprising: generating a second entry in a hierarchically organized second level address translation table, the second entry being at least one hierarchical level above the hierarchically lowest level of the tables such that the third the storage range identified by the second entry can be identified without reference to tables at all at the hierarchically lowest table level, wherein the third storage range refers to a single larger page size area of the host physical storage into which a first plurality of contiguous physical storage areas are assembled. host devices with a small page size; and in response to generating a second entry in the second level hierarchical address translation table, marking as in use a second set of entries in the hierarchically organized page table, the second set of entries referencing a first set of contiguous small page size host physical storage areas that are assembled into one area with a large host physical storage page size.

[00107] The eighth example is a method of the seventh example, further comprising: generating a second entry in a hierarchically organized second level address translation table, the second entry being at least one hierarchical level above the hierarchically lowest level of the tables such that the third the storage range identified by the second entry can be identified without any reference to tables at the hierarchically lowest level of tables, wherein the third storage range refers to a single larger page size area of the host physical storage into which a first plurality of contiguous physical storage areas are assembled. host devices with a small page size; and in response to generating a second entry in the second level hierarchical address translation table, marking as in use a second set of entries in the hierarchically organized page table, the second set of entries referencing a first set of contiguous small page size host physical storage areas that are assembled into one area with a large host physical storage page size.

[00108] The ninth example is the method of the seventh example, further comprising: copying data from a second set of one or more small page size host physical storage areas to at least a portion of the first plurality of contiguous small page size areas; and invalidating a second set of entries in a hierarchically organized second level address translation table, the second set of entries comprising: both (1) a first subset of entries that refer to a second set of one or more small page size host physical storage areas, and ( 2) a second subset of entries that reference at least a portion of the first set of contiguous host physical storage areas with a small page size, the entries from the second set of entries being at the hierarchically lowest table level; wherein the generated second entry in the hierarchically organized second level address translation table is used in place of the second set of entries that are invalidated.

[00109] The tenth example is a method of the fifth example, wherein assembling the first plurality of contiguous small page size host physical storage areas comprises copying data from a portion of the first plurality of contiguous small page size areas to other small page size host physical storage areas , which are different from the first set of contiguous areas with a small page size.

[00110] The eleventh example is a method of the tenth example, in which copying data from a part of the first plurality of contiguous areas with a small page size to other areas with a small page size is performed only if the fragmentation of the first plurality of contiguous areas with a small page size is below a threshold fragmentation values.

[00111] The twelfth example is the method of the first example, further comprising: preventing paging of the second storage range.

[00112] The thirteenth example is the method of the twelfth example, wherein paging prevention of the second storage range is performed only if one or more portions of the second storage range is accessed more frequently than an access frequency threshold.

[00113] The fourteenth example is the method of the twelfth example, further comprising removing paging prevention of the second storage range if one or more portions of the second storage range are accessed less than an access frequency threshold.

[00114] The fifteenth example is the method of the first example, in which the second storage range has a size of 2 MB.

[00115] The sixteenth example is a computing device comprising: one or more central processing units; random access memory (RAM); and one or more computer-readable media comprising: a first set of computer-executable instructions that, when executed by a computing device, instructs the computing device to provide a storage manager that accesses a hierarchically organized page table in order to translate host virtual storage cell addresses into cell addresses the physical storage device of the host, which identify locations in RAM; a second set of machine-executable instructions that, when executed by the computing device, instructs the computing device to provide a virtual machine computing environment, wherein processes running within the virtual machine computing environment treat the guest physical storage cell addresses as addresses for the physical storage device, and when therein, the additional guest physical storage identified by the guest physical storage cell addresses is reserved by the host virtual storage portion identified by the host virtual storage cell address portion; and a third set of computer-executable instructions that, when executed by the computing device, cause the computing device to: detect access to the first storage device from a first process running in the virtual machine computing environment directed to the first storage device range; to form, as a precondition for performing the first access to the storage device, the first entry in the hierarchically organized second level address translation table, and the hierarchically organized second level address translation table correlates the addresses of cells of the host physical storage device with the addresses of cells of the guest physical storage device, and the first the entry is located at least one hierarchical level above the hierarchically lowest table level such that the second storage range identified by the first entry can be identified without reference to the tables at the hierarchically lowest table level at all, the second storage range greater than the first storage range; and in response to generating a first entry in the second-level hierarchically organized address translation table, marking as in use a first set of entries in the hierarchically organized page table, wherein the first set of entries refer, collectively, to the same second storage range as the first entry in a hierarchically organized second-level address translation table, wherein the entries from the first set of entries are at the hierarchically lowest level of the tables.

[00116] The seventeenth example is the computing device of the sixteenth example, in which the third set of computer-executable instructions contains additional computer-executable instructions that, when executed by the computing device, instruct the computing device: to detect, after the first access to the storage device is completed, then, that a first subset of the first plurality of entries in the hierarchically organized page table has data that is initially stored in respective host physical storage cell addresses, then siphoned off, at the page level, to a non-volatile storage medium; invalidate, in response to the discovery, the first entry in the hierarchically organized second level address translation table; and to form, instead of the first entry in the hierarchically organized second level address translation table, a second set of entries in the hierarchically organized second level address translation table, wherein the second set of entries refer, in the aggregate, to at least a portion of the second storage range identical to the storage range devices for the first record, while records from the second set of records are at the hierarchically lowest level of tables.

[00117] The eighteenth example is the computing device of the sixteenth example, wherein the third set of computer-executable instructions comprises additional computer-executable instructions that, when executed by the computing device, instruct the computing device to: assemble a first plurality of contiguous host physical storage areas with a small page size into one an area with a large page size of the physical storage device of the host; in this case, assembly occurs after the first access to the storage device is detected and before the formation of the first entry in the hierarchically organized second-level address translation table.

[00118] The nineteenth example is the computing device of the sixteenth example, in which the third set of computer-executable instructions contains additional computer-executable instructions that, when executed by the computing device, instruct the computing device to: prevent paging of the second storage range.

[00119] The twentieth example is one or more computer-readable storage media containing computer-executable instructions that, when executed, instruct the computing device to: detect access to a first storage device, from a first process running in a virtual machine computing environment directed to a first storage device range ; to form, as a precondition for performing the first access to the storage device, the first entry in the hierarchically organized second level address translation table, and the hierarchically organized second level address translation table correlates the addresses of cells of the host physical storage device with the addresses of cells of the guest physical storage device, and the first the entry is located at least one hierarchical level above the hierarchically lowest table level such that the second storage range identified by the first entry can be identified without reference to the tables at the hierarchically lowest table level at all, the second storage range greater than the first storage range; and, in response to generating a first entry in the second-level hierarchical address translation table, marking as in use the first set of entries in the hierarchical page table, the hierarchical page table mapping host physical storage cell addresses to host virtual storage cell addresses, the first the plurality of entries refer, collectively, to the same second storage range as the first entry in the hierarchically organized second level address translation table, wherein the entries from the first plurality of entries are at the hierarchically lowest table level; wherein the addresses of the cells of the guest physical storage device are perceived as addresses in the physical storage device by processes running within the computing environment of the virtual machine; wherein the physical storage cell addresses of the host are addresses in the actual physical storage of the host computing device accommodating the virtual machine computing environment; wherein the host virtual storage cell addresses are addresses in a virtual storage provided by a storage manager running on a computing host device, the storage manager using a hierarchically organized page table to provide the virtual storage; and wherein the guest physical storage identified by the guest physical storage cell addresses is reserved by the host virtual storage portion identified by the host virtual storage cell address portion.

[00120] As can be seen from the above descriptions, mechanisms are described by which access to a storage device via SLAT can be accelerated. In view of the many possible variations of the invention described herein, we claim in the claims, as our invention, all such embodiments as may fall within the scope of the appended claims and their equivalents.

Claims (60)

1. A method for increasing the speed of computer memory access, comprising the steps of: detecting a first memory access from a first process running in the virtual machine computing environment directed to a first memory range; form, as a precondition for performing the first memory access, the first entry in the hierarchically organized second level address translation table, and the hierarchically organized second level address translation table correlates host physical memory addresses with guest physical memory addresses, while the first entry is located on the at least one hierarchical level above the hierarchically lowest table level such that the second storage range identified by the first entry can be identified without reference to any table at the hierarchically lowest table level, the second storage range being greater than the first storage range; and in response to the formation of the first entry in the hierarchically organized second level address translation table, the first set of entries in the hierarchically organized page table is marked as used, and the hierarchically organized page table correlates host physical memory addresses with host virtual memory addresses, while the first set of entries are referenced, collectively, to the same second storage range as the first entry in the hierarchically organized second level address translation table, the entries from the first set of entries being at the hierarchically lowest level of the tables; while the addresses of the guest physical memory are perceived as addresses in physical memory by processes running in the computing environment of the virtual machine; wherein the host physical memory addresses are addresses in the actual physical memory of the host computing device that hosts the virtual machine computing environment; wherein the host virtual memory addresses are addresses in virtual memory provided by a memory manager executing on the host computing device, wherein the memory manager uses a hierarchically organized page table to provide virtual memory; and wherein the guest physical memory identified by the guest physical memory addresses is reserved by the host virtual memory portion identified by the host virtual memory address portion. 2. The method of claim 1, further comprising the steps of: detecting a second memory access from a first process running in the virtual machine computing environment, wherein the second memory access is directed to a third memory range that is different from the first memory range; and satisfying a second memory access by accessing a second subset of the first plurality of entries in the hierarchically organized page table; wherein the first memory access is satisfied by accessing the first subset of the first set of entries in the hierarchical page table, the first subset containing different entries in the hierarchical page table relative to the second subset. 3. The method according to claim 1, further comprising the steps of: detecting, after the first memory access is completed, that the first subset of the first plurality of entries in the hierarchically organized page table has data that was originally stored in the respective host physical memory addresses, then siphoned out, at the page level, to a non-volatile storage medium; invalidating, in response to this discovery, the first entry in the hierarchically organized second level address translation table; and form, instead of the first entry in the hierarchically organized second level address translation table, a second set of entries in the hierarchically organized second level address translation table, and the second set of entries refer, in the aggregate, to at least part of the same second memory range as the first record, while the records from the second set of records are at the hierarchically lowest level of tables. 4. The method of claim 3, wherein the second set of entries refer to parts of the second memory range that were previously accessed by the first process and that were not swapped out at the page level. 5. The method of claim 1, further comprising assembling a first plurality of contiguous host physical memory regions having a small page size into one host physical memory region having a large page size. 6. The method of claim 5, wherein said collection takes place after the first memory access is detected and before the formation of the first entry in the hierarchically organized second level address translation table. 7. The method of claim 5, further comprising the steps of: forming a second entry in a hierarchically organized second level address translation table, the second entry being at least one hierarchical level above the hierarchically lowest level of the tables such that the third memory range identified by the second entry can be identified without referring to any table at the hierarchically lowest level of tables, wherein the third memory range refers to a single host physical memory region having a large page size, into which a first plurality of contiguous host physical memory regions having a small page size are collected; and in response to the formation of the second entry in the hierarchically organized second level address translation table, the second set of entries in the hierarchically organized page table are marked as in use, and the second set of entries refer to the first set of contiguous host physical memory areas having a small page size, which are assembled into one an area of host physical memory that has a large page size. 8. The method of claim 7, further comprising the steps of: copy data from a second plurality of host physical memory regions having a small page size to at least a portion of a first plurality of contiguous regions having a small page size, wherein the second plurality of small page size regions are at least partially discontinuous ; and invalidate the second set of entries in the hierarchically organized second level address translation table that referred to the second set of host physical memory areas having a small page size, wherein the entries from the second set of entries are at the hierarchically lowest level of the tables; wherein the generated second entry in the hierarchically organized second level address translation table is used in place of the second set of entries that were invalidated. 9. The method according to claim 7, further comprising the steps of: copying data from a second set of one or more small page size areas of the host's physical memory to at least a portion of a first plurality of contiguous small page size areas; and invalidate a second set of entries in a hierarchically organized second level address translation table, wherein the second set of entries contain both (1) a first subset of entries that refer to a second set of one or more host physical memory areas having a small page size, and (2) a second subset of entries that reference at least a portion of the first plurality of contiguous host physical memory regions having a small page size, the records from the second plurality of records being at the hierarchically lowest level of tables; wherein the generated second entry in the hierarchically organized second level address translation table is used in place of the second set of entries that were invalidated. 10. The method of claim 5, wherein said collection of the first plurality of contiguous host physical memory regions having a small page size comprises copying data from a portion of the first plurality of contiguous regions having a small page size to other host physical memory regions. , having a small page size, which are different from the first set of contiguous areas having a small page size. 11. The method of claim 1, wherein copying data from a portion of the first plurality of contiguous areas having a small page size to other areas having a small page size is performed only if fragmentation of the first plurality of contiguous areas having a small page size , below the fragmentation threshold. 12. The method of claim 1, further comprising preventing paging of the second memory range. 13. The method of claim 12, wherein paging prevention of the second memory range is performed only if one or more portions of the second memory range are accessed faster than an access rate threshold. 14. The method of claim 12, further comprising removing paging prevention of the second memory range if one or more portions of the second memory range are accessed less than an access rate threshold. 15. The method of claim 1, wherein the size of the second memory range is 2 MB. 16. Computing device containing: one or more central processing units; random access memory (RAM); and one or more computer-readable media containing: a first set of computer-executable instructions that, when executed by a computing device, cause the computing device to provide a memory manager that accesses a hierarchically organized page table to translate host virtual memory addresses to host physical memory addresses that identify locations in RAM; a second set of machine-executable instructions that, when executed by the computing device, instructs the computing device to provide a virtual machine computing environment, wherein processes running in the virtual machine computing environment treat guest physical memory addresses as addresses in physical memory, and additionally guest physical memory, identified by the guest physical memory addresses is reserved by the host virtual memory portion identified by the host virtual memory address portion; and a third set of machine-executable instructions that, when executed by a computing device, instruct the computing device to: - detect the first memory access from the first process running in the virtual machine computing environment directed to the first memory range; - to form, as a precondition for performing the first memory access, the first entry in the hierarchically organized second level address translation table, and the hierarchically organized second level address translation table correlates host physical memory addresses with guest physical memory addresses, while the first entry is located on at least one hierarchical level above the hierarchically lowest table level such that the second storage range identified by the first entry can be identified without reference to any table at the hierarchically lowest table level, the second storage range being greater than the first storage range; and - in response to the formation of the first entry in the hierarchically organized second level address translation table, mark as used the first set of entries in the hierarchically organized page table, and the first set of entries refer, in aggregate, to the same second memory range as the first entry in the hierarchically organized the address translation table of the second level, while the records from the first set of records are at the hierarchically lowest level of the tables. 17. The computing device of claim 16, wherein the third set of computer-executable instructions comprises additional computer-executable instructions that, when executed by the computing device, instruct the computing device to: detect, after the first memory access is completed, that the first subset of the first plurality of entries in the hierarchically organized page table has data that was initially stored in the respective physical memory addresses of the host, then swapped out, at the page level, to a non-volatile storage medium; invalidate, in response to this detection, the first entry in the hierarchically organized second level address translation table; and form, instead of the first entry in the hierarchically organized second level address translation table, a second set of entries in the hierarchically organized second level address translation table, and the second set of entries refer, in the aggregate, to at least a part of the same second memory range as the first record, while the records from the second set of records are at the hierarchically lowest level of tables. 18. The computing device of claim 16, wherein the third set of computer-executable instructions comprises additional computer-executable instructions that, when executed by the computing device, instruct the computing device to assemble a first plurality of contiguous host physical memory regions having a small page size into a single host physical memory region, having a large page size, and this collection takes place after the first memory access is detected and before the formation of the first entry in the hierarchically organized second-level address translation table. 19. The computing device of claim 16, wherein the third set of computer-executable instructions comprises additional computer-executable instructions that, when executed by the computing device, instruct the computing device to prevent paging of the second memory range. 20. A computer-readable storage medium containing machine-executable instructions that, when executed, instruct the computing device: detect a first memory access from a first process running in the virtual machine computing environment directed to the first memory range; form, as a precondition for performing the first memory access, the first entry in a hierarchically organized second level address translation table, wherein the hierarchically organized second level address translation table maps host physical memory addresses to guest physical memory addresses, with the first entry located on the at least one hierarchical level above the hierarchically lowest table level such that the second storage range identified by the first entry can be identified without reference to any table at the hierarchically lowest table level, the second storage range being greater than the first storage range; and in response to the formation of the first entry in the hierarchically organized second-level address translation table, mark as used the first set of entries in the hierarchically organized page table, and the hierarchically organized page table correlates host physical memory addresses with host virtual memory addresses, while the first set of entries are referenced, collectively, to the same second storage range as the first entry in the hierarchically organized second level address translation table, the entries from the first set of entries being at the hierarchically lowest level of the tables; while the addresses of the guest physical memory are perceived as addresses in physical memory by processes running in the computing environment of the virtual machine; wherein the host physical memory addresses are addresses in the actual physical memory of the host computing device that hosts the virtual machine computing environment; wherein the host virtual memory addresses are addresses in virtual memory provided by a memory manager executing on the host computing device, wherein the memory manager uses a hierarchically organized page table to provide virtual memory; and wherein the guest physical memory identified by the guest physical memory addresses is reserved by the host virtual memory portion identified by the host virtual memory address portion.

Images