Memory management using transparent page transformation

Patent metadata

Field	Value
Publication number	US-9665498-B2
Application number	US-18298908-A
Country	US
Kind code	B2
Filing date	Jul 30, 2008
Priority date	Jul 30, 2008
Publication date	May 30, 2017
Grant date	May 30, 2017

Abstract

Memory space is managed to release storage area occupied by pages similar to stored reference pages. The memory is examined to find two similar pages, and a transformation is obtained. The transformation enables reconstructing one page from the other. The transformation is then stored and one of the pages is discarded to release its memory space. When the discarded page is needed, the remaining page is fetched, and the transformation is applied to the page to regenerate the discarded page.

First claim

We claim:

1. A non-transitory computer readable storage medium embodying software instructions for managing memory space, the software instructions causing a computer to perform a method, the method comprising the steps of:
identifying a page, within a memory space of a random access memory that is managed in units of pages, that is similar, but not identical, to a reference page within said memory space, wherein the identified page and the referenced page are each a single page in said memory space;
obtaining transformation information enabling re-creation of the identified page from the reference page;
storing at least one of the transformation information or a pointer to the transformation information; and,
deleting the identified page, wherein the step of obtaining the transformation information comprises calculating a set of vectors, each vector comprising an addend location and an addend, the addend location identifying a location in the identified page having a stored present value different from a reference value stored at a corresponding location on the reference page, the addend equaling a difference between the stored present value and the stored reference value.

2. A non-transitory computer readable storage medium embodying software instructions for managing memory space, the software instructions causing a computer to perform a method, the method comprising the steps of:
identifying a page, within a memory space of a random access memory that is managed in units of pages, that is similar, but not identical, to a reference page within said memory space, wherein the identified page and the referenced page are each a single page in said memory space;
obtaining transformation information enabling re-creation of the identified page from the reference page;
storing at least one of the transformation information or a pointer to the transformation information; and,
deleting the identified page,
wherein the step of obtaining the transformation information comprises determining one addend that is common to all memory locations of the identified page having a stored present value different from corresponding reference values stored on the reference page, the one addend equaling a difference between each of the stored present values and each of the corresponding stored reference values.

3. The non-transitory computer readable storage medium of claim 2 , wherein the step of storing the transformation information comprises storing the one addend and the memory locations of the identified page having a stored present value different from corresponding reference values stored on the reference page.

4. The non-transitory computer readable storage medium of claim 3 , wherein the step of deleting of the identified page comprises releasing the memory space occupied by the identified page.

5. The non-transitory computer readable storage medium of claim 3 , wherein the method further comprises the steps of
fetching the reference page and applying the transformation information to the reference page to regenerate the identified page on attempts to access the identified page.

6. The non-transitory computer readable storage medium of claim 3 , wherein the step of identifying of the page comprises applying heuristics to a plurality of pages to identify a page that is similar to the reference page.

7. The non-transitory computer readable storage medium of claim 6 , wherein the step of applying heuristics comprises comparing page headers of the plurality of pages.

8. The non-transitory computer readable storage medium of claim 3 , wherein the step of identifying the page comprises randomly selecting at least one of the identified page and the reference page from a plurality of pages.

9. The non-transitory computer readable storage medium of claim 3 , wherein the step of obtaining the transformation information comprises fetching previously calculated transformation information from a storage location and maintaining a reference counter to ensure one copy is in memory.

10. The non-transitory computer readable storage medium of claim 3 , wherein the method further comprises the steps of:
examining a size of the transformation information and performing the storing step only if storage saving resulting from discarding the identified page and storing the transformation information exceeds a threshold.

11. The non-transitory computer readable storage medium of claim 3 , wherein:
the computer comprises a virtualized computer system having virtualization software logically interposed between and interfacing with computer hardware and at least one virtual machine having a guest operating system and at least one application, the virtualization software comprising the software instructions for managing the memory space; and
the steps of identifying the page, obtaining the transformation information, the storing the at least one of the transformation information or the pointer, and deleting are performed by the virtualization software in the virtualized computer system.

12. The non-transitory computer readable storage medium of claim 3 , further comprising the step of:
selecting a size of the addend prior to obtaining of the transformation information.

13. The non-transitory computer readable storage medium of claim 12 , wherein the size of the addend is selected based on an expected size of differences between the identified page and the reference page.

14. The non-transitory computer readable storage medium of claim 12 , wherein the size of the addend is selected based a memory address size used by an operating system of the computer.

Assignees

• Kiriansky Vladimir L
• Vmware Inc

Inventors

• Kiriansky Vladimir L

Classifications

• G06F2212/401

  Compressed data · CPC title

• G06F12/10 Primary

  Address translation · CPC title