Content-based, transparent sharing of memory units

• US 6,789,156 B1
• Filed: 07/25/2001
• Issued: 09/07/2004
• Est. Priority Date: 05/22/2001
• Status: Expired due to Term

• Current Assignee: VMware, Inc. (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Waldspurger, Carl A.
• Primary Examiner(s): Padmanabhan, Mano
• Assistant Examiner(s): Song, Jasmine
• Application Number:
  US09/915,045
• Time in Patent Office: 1,140 Days
• Field of Search: 711/6, 711/216, 711/202, 711/203, 711/206, 718/1
• US Class Current: 711/6
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 12/1036 for multiple virtual address spaces, e.g. segmentation G06F12/1045 takes precedence
• CPC Class Codes: G06F 2212/151 Emulated environment, e.g. virtual machine

Abstract

A computer system has one or more software context that share use of a memory that is divided into units such as pages. In the preferred embodiment of the invention, the context are, or include, virtual machines running on a common hardware platform. The context, as opposed to merely the addresses or page numbers, of virtual memory pages that accessible to one or more contexts are examined. If two or more context pages are identical, then their memory mappings are changed to point to a single, shared copy of the page in the hardware memory, thereby freeing the memory space taken up by the redundant copies. The shared copy is ten preferable marked copy-on-write. Sharing is preferably dynamic, whereby the presence of redundant copies of pages is preferably determined by hashing page contents and performing full content comparisons only when two or more pages hash to the same key.

Claims

1. In a computer system that includes a hardware memory and at least one context, which has a virtual memory that is divided into a plurality of virtual memory units that are mappable to corresponding hardware memory units, a method comprising the following steps:

selecting candidate memory units from among the virtual memory units;

identifying virtual memory units that have contents identical to those of the candidate memory units; and

mapping those virtual memory units identified as having identical contents to a single instance of a corresponding one of the hardware memory units

in which;

the step of identifying virtual memory units that have identical contents includes the following sub-steps;

calculating a hash value by applying a hash function to the contents of a current one of the candidate memory units;

searching a data structure to determine the presence of a previous data structure entry corresponding to the calculated hash value;

if a previous entry is not present in the data structure, inserting into the data structure a new entry corresponding to the current candidate memory unit; and

if a previous entry is present in the data structure, comparing the entire contents of the current candidate memory unit with the contents of the single instance indicated by the previous entry.

2. A method as in claim 1, in which the data structure is a hash table.

3. A method as in claim 1,

in which the step of mapping the virtual memory units having identical contents further comprises write-protecting selected ones of the virtual memory units that are mapped to the single instance.

4. A method as in claim 3, which any and all of the virtual memory units that are mapped to the single instance are write-protected.

5. A method as in claim 3, further including the following steps:

sensing a request by any context to write to any write-protected virtual memory unit and, upon sensing such request,

for the requesting context, generating in the hardware memory a private copy of the write-protected virtual memory unit; and

remapping the write-protected virtual memory unit to the private copy.

6. A method as in claim 3, further comprising the step of identifying virtual memory units that have a relatively high probability of impending modification.

7. A method as in claim 6, further comprising the following steps:

designating as temporarily non-sharable the virtual memory units that have the relatively high probability of impending modification; and

deferring the step of mapping to the single instance for the temporarily non-sharable virtual memory units.

8. A method as in claim 6, further comprising the following steps:

designating as temporarily non-sharable the virtual memory units that have the relatively high probability of impending modification; and

deferring the step of write-protecting each temporarily non-sharable virtual memory unit until a subsequent identification of a different one of the virtual memory units having contents identical to the respective temporarily non-sharable virtual memory unit.

9. A method as in claim 3, further comprising deferring the step of write-protecting each virtual memory unit for which no other virtual memory unit has yet been identified as having identical contents.

10. A method as in claim 1, in which the step of identifying virtual memory units that have identical contents comprises randomly selecting the virtual memory units for content comparison with at least one other of the virtual memory units.

11. A method as in claim 1, in which the step of identifying virtual memory units that have identical contents comprises selecting the virtual memory units for content comparison with at least one other of the virtual memory units according to a predetermined heuristic criterion.

12. A method as in claim 1, in which the step of identifying virtual memory units is performed during a system idle time.

13. A method as in claim 1, in which at least one context is a virtual machine.

14. A method as in claim 1, in which at least one context is a virtual disk.

15. A method as in claim 1, in which the step of identifying virtual memory units that have identical contents comprises the step of comparing the contents of each of the virtual memory units with the contents of each of the other virtual memory units.

16. A method as in claim 1, further comprising the following steps:

partitioning the virtual memory units into a plurality of classes; and

performing the step of identifying virtual memory units that have identical contents and the step of mapping those virtual memory units to a single shared instance of a corresponding hardware memory unit separately and independently for each of the classes,

sharing single instances of the hardware memory units thereby taking place only among virtual memory units in the same class.

17. A method as in claim 16, in which the classes are page colors of the hardware memory units to which the corresponding virtual memory units are currently mapped.

18. A method as in claim 16, in which the computer system further has a multiprocessor architecture with a non-uniform memory access property and a plurality of memory modules having different access latency, and in which the classes are the memory modules to which the corresponding virtual memory units are currently mapped.

19. A method for sharing memory in a computer system comprising:

installing in the computer system at least one virtual machine that comprises;

at least one address space that is divided into a plurality of virtual memory units; and

a virtual operating system that maps each virtual memory unit to a corresponding intermediate memory unit;

selecting candidate memory units from among the intermediate memory units;

for each virtual machine, maintaining in a virtual machine monitor an intermediate mapping that maps each intermediate memory unit to a corresponding hardware memory unit of a hardware memory;

identifying intermediate memory units that have identical contents by hashing the contents of the candidate memory units; and

via the intermediate mapping, mapping those intermediate memory units identified as having identical contents to a single instance of a corresponding one of the hardware memory units;

in which the step of identifying intermediate memory units that have identical contents further includes the following sub-steps;

calculating a hash value by applying a hash function to the contents of a current one of the candidate memory units;

searching a data structure to determine the presence of a previous data structure entry corresponding to the calculated hash value;

if a previous entry is not present in the data structure, inserting into the data structure a new entry corresponding to the current candidate memory unit; and

if a previous entry is present in the data structure, comparing the entire contents of the current candidate memory unit with the contents of the single instance indicated by the previous entry.

20. A method as in claim 19, in which the data structure is a hash table.

21. A method as in claim 19,

in which the step of mapping the intermediate memory units having identical contents further comprises write-protecting selected ones of the intermediate memory units that are mapped to the single instance.

22. A method as in claim 21, in which any and all of the intermediate memory units that are mapped to the single instance are write-protected.

23. A method as in claim 21, further including the following steps:

sensing a request by any context to write to any write-protected intermediate memory unit and, upon sensing such request,

for the requesting context, generating in the hardware memory a private copy of the write-protected intermediate memory unit; and

remapping the write-protected intermediate memory unit to the private copy.

24. A method as in claim 21, further comprising the step of identifying intermediate memory units that have a relatively high probability of impending modification.

25. A method as in claim 24, further comprising the following steps:

designating as temporarily non-sharable the intermediate memory units that have the relatively high probability of impending modification; and

deferring the step of mapping to the single instance for the temporarily non-sharable intermediate memory units.

26. A method as in claim 24, further comprising the following steps:

designating as temporarily non-sharable the intermediate memory units that have the relatively high probability of impending modification; and

deferring the step of write-protecting each temporarily non-sharable intermediate memory unit until a subsequent identification of a different one of the intermediate memory units having contents identical to the respective temporarily non-sharable intermediate memory unit.

27. A method as in claim 21, further comprising deferring the step of write-protecting each intermediate memory unit for which no other intermediate memory unit has yet been identified as having identical contents.

28. A method as in claim 19, in which the step of identifying intermediate memory units that have identical contents comprises randomly selecting the intermediate memory units for content comparison with at least one other of the intermediate memory units.

29. A method as in claim 19, in which the step of identifying intermediate memory units that have identical contents comprises selecting the intermediate memory units for content comparison with at least one other of the intermediate memory units according to a predetermined heuristic criterion.

30. A method as in claim 19, in which the step of identifying intermediate memory units is performed during a system idle time.

31. A method as in claim 19, in which the step of identifying intermediate memory units that have identical contents comprises the step of comparing the contents of each of the intermediate memory units with the contents of each of the other intermediate memory units.

32. A method as in claim 19, further comprising the following steps:

partitioning the intermediate memory units into a plurality of classes; and

performing the step of identifying intermediate memory units that have identical contents and the step of mapping those intermediate memory units to a single shared instance of a corresponding hardware memory unit separately and independently for each of the classes,

sharing single instances of the hardware memory units thereby taking place only among intermediate memory units in the same class.

33. A method as in claim 32, in which the classes are page colors of the hardware memory units to which the corresponding intermediate memory units are currently mapped.

34. A method as in claim 32, in which the computer system further has a multiprocessor architecture with a non-uniform memory access property and a plurality of memory modules having different access latency, and in which the classes are the memory modules to which the corresponding intermediate memory units are currently mapped.

35. In a computer system that includes a hardware memory and at least one context, which has a virtual memory that is divided into a plurality of virtual memory units that are mappable to corresponding hardware memory units, a method comprising the following steps:

A) identifying virtual memory units that have identical contents; and

B) mapping those virtual memory units identified as having identical contents to a single instance of a corresponding one of the hardware memory units;

in which;

C) the step of identifying virtual memory units that have identical contents includes the following sub-steps;

i) selecting candidate memory units from among the virtual memory units;

ii) calculating a hash value by applying a hash function to the contents of a current one of the candidate memory units;

iii) searching a hash table to determine the presence of a previous hash table entry corresponding to the calculated hash value and

a) if a previous entry is not present in the hash table, inserting into the hash table a new entry corresponding to the current candidate memory unit; and

b) if a previous entry is present in the hash table, comparing the entire contents of the current candidate memory unit with the contents of the single instance indicated by the previous entry;

D) write-protecting selected ones of the virtual memory units that are mapped to the single instance; and

E) sensing a request by any context to write to any write-protected virtual memory unit and, upon sensing such request, for the requesting context, generating in the hardware memory a private copy of the write-protected virtual memory unit and remapping the write-protected virtual memory unit to the private copy.

36. A method for sharing memory in a computer system comprising:

A) installing in the computer system at least one virtual machine that comprises;

i) at least one address space that is divided into a plurality of virtual memory units; and

ii) a virtual operating system that maps each virtual memory unit to a corresponding intermediate memory unit;

B) for each virtual machine, maintaining in a virtual machine monitor an intermediate mapping that maps each intermediate memory unit to a corresponding hardware memory unit of a hardware memory;

C) identifying intermediate memory units that have identical contents; and

D) via the intermediate mapping, mapping those intermediate memory units identified as having identical contents to a single instance of a corresponding one of the hardware memory units;

in which;

D) the step of identifying intermediate memory units that have identical contents includes the following sub-steps;

i) selecting candidate memory units from among the intermediate memory units;

ii) calculating a hash value by applying a hash function to the contents of a current one of the candidate memory units;

iii) searching a hash table to determine the presence of a previous hash table entry corresponding to the calculated hash value and

a) if a previous entry is not present in the hash table, inserting into the hash table a new entry corresponding to the current candidate memory unit; and

b) if a previous entry is present in the hash table, comparing the entire contents of the current candidate memory unit with the contents of the single instance indicated by the previous entry;

E) write-protecting selected ones of the intermediate memory units that are mapped to the single instance; and

F) sensing a request by any context to write to any write-protected virtual memory unit and, upon sensing such request, for the requesting context, generating in the hardware memory a private copy of the write-protected virtual memory unit and remapping the write-protected virtual memory unit to the private copy.

37. A computer system comprising:

a hardware memory;

at least one context, which has a virtual memory that is divided into a plurality of virtual memory units that are mappable to corresponding hardware memory units; and

a memory sharing module comprising computer-executable code for identifying virtual memory units that have identical contents and for mapping those virtual memory units identified as having identical contents to a single instance of a corresponding one of the hardware memory units

in which;

the memory sharing module includes;

a candidate selection sub-module for selecting candidate memory units from among the virtual memory units; and

a hashing sub-module or hashing the contents of the candidate memory units;

the hashing module is further provided for calculating a hash value by applying a hash function to the contents of a current one of the candidate memory units and for searching a data structure to determine the presence of a previous data structure entry corresponding to the calculated hash value; and

the memory sharing module is further provided for inserting into the data structure a new entry corresponding to the current candidate memory unit if a previous entry is not present in the data structure; and

for comparing the entire contents of the current candidate memory unit with the contents of the single instance indicated by the previous entry if a previous entry is present in the data structure.

38. A system as in claim 37, in which the data structure is a hash table.

39. A system as in claim 37, further comprising:

a write-protection mechanism for write-protecting selected ones of the virtual memory units that are mapped to the single instance.

40. A system as in claim 39, in which any and all of the virtual memory units that are mapped to the single instance are write-protected.

41. A system as in claim 39, in which the memory sharing module is further provided for sensing a request by any context to write to any write-protected virtual memory unit and, upon sensing such request, for the requesting context, for generating in the hardware memory a private copy of the write-protected virtual memory unit and for remapping the write-protected virtual memory unit to the private copy.

42. A system as in claim 39, in which the memory sharing module is provided for deferring the step of write-protecting each virtual memory unit for which no other virtual memory unit has yet been identified as having identical contents.

43. A system as in claim 37, in which at least one context is a virtual machine.

44. A system as in claim 37, in which at least one context is a virtual disk.

45. A system as in claim 37, in which the memory sharing module is provided for comparing the contents of each of the virtual memory units with the contents of each of the other virtual memory units.

46. A system as in claim 37, in which:

the virtual memory units are partitioned into a plurality of classes; and

the memory sharing module is further provided for identifying virtual memory units that have identical contents and for mapping those virtual memory units to a single shared instance of a corresponding hardware memory unit separately and independently for each of the classes, whereby single instances of the hardware memory units are shared only among virtual memory units in the same class.

47. A system as in claim 46, in which the classes are page colors of the hardware memory units to which the corresponding virtual memory units are currently mapped.

48. A system as in claim 46, in which the computer system further has a multiprocessor architecture with a non-uniform memory access property and a plurality of memory modules having different access latency, and in which the classes are the memory modules to which the corresponding virtual memory units are currently mapped.

49. A computer system comprising:

a hardware memory;

at least one virtual machine that comprises;

at least one address space that is divided into a plurality of virtual memory units; and

a virtual operating system including means for mapping each virtual memory unit to a corresponding intermediate memory unit;

for each virtual machine, a corresponding virtual machine monitor including intermediate mapping means for mapping each intermediate memory unit to a corresponding hardware memory unit of the hardware memory;

a memory sharing module comprising computer-executable code for identifying intermediate memory units that have identical contents, and, via the intermediate mapping means, for mapping those intermediate memory units identified as having identical contents to a single instance of a corresponding one of the hardware memory units;

in which;

the memory sharing module includes;

a candidate selection sub-module for selecting candidate memory units from among the intermediate memory units; and

a hashing sub-module for hashing the contents of the candidate memory units;

the hashing module is further provided for calculating a hash value by applying a hash function to the contents of a current one of the candidate memory units and for searching a data structure to determine the presence of a previous data structure entry corresponding to the calculated hash value; and

the memory sharing module is further provided for inserting into the data structure a new entry corresponding to the current candidate memory unit if a previous entry is not present in the data structure; and

for comparing the entire contents of the current candidate memory unit with the contents of the single instance indicated by the previous entry if a previous entry is present in the data structure.

50. A system as in claim 49, in which the data structure is a hash table.

51. A system as in claim 49, further comprising:

a write-protection mechanism for write-protecting selected ones of the intermediate memory units that are mapped to the single instance.

52. A system as in claim 51, in which any and all of the intermediate memory units that are mapped to the single instance are write-protected.

53. A system as in claim 51, in which the memory sharing module is further provided for sensing a request by any virtual machine to write to any write-protected intermediate memory unit and, upon sensing such request, for the requesting virtual machine, for generating in the hardware memory a private copy of the write-protected intermediate memory unit and for remapping the write-protected intermediate memory unit to the private copy.

54. A system as in claim 51, in which the memory sharing module is provided for deferring the step of write-protecting each intermediate memory unit for which no other intermediate memory unit has yet been identified as having identical contents.

55. A system as in claim 49, in which the memory sharing module is provided for comparing the contents of each of the intermediate memory units with the contents of each of the other intermediate memory units.

56. A system as in claim 49, in which:

the virtual memory units are partitioned into a plurality of classes; and

the memory sharing module is further provided for identifying virtual memory units that have identical contents and for mapping those virtual memory units to a single shared instance of a corresponding hardware memory unit separately and independently for each of the classes, whereby single instances of the hardware memory units are shared only among virtual memory units in the same class.

57. A system as in claim 56, in which the classes are page colors of the hardware memory units to which the corresponding virtual memory units are currently mapped.

58. A system as in claim 56, in which the computer system further has a multiprocessor architecture with a non-uniform memory access property and a plurality of memory modules having different access latency, and in which the classes are the memory modules to which the corresponding virtual memory units are currently mapped.

59. In a computer system that includes a hardware memory and at least one context, which has a virtual memory that is divided into a plurality of virtual memory units that are mappable to corresponding hardware memory units, a method comprising the following steps:

selecting candidate memory units from among the virtual memory units;

identifying virtual memory units that have contents identical to the contents of the candidate memory units;

identifying virtual memory units that have a relatively high probability of impending modification; and

mapping those virtual memory units identified as having identical contents to a single instance of a corresponding one of the hardware memory units and write-protecting selected ones of the virtual memory units that are mapped to the single instance.

60. A method as in claim 59, further comprising the following steps:

designating as temporarily non-sharable the virtual memory units that have the relatively high probability of impending modification; and

deferring the step of mapping to the single instance for the temporarily non-sharable virtual memory units.

61. A method as in claim 59, further comprising the following steps:

designating as temporarily non-sharable the virtual memory units that have the relatively high probability of impending modification; and

deferring the step of write-protecting each temporarily non-sharable virtual memory unit until a subsequent identification of a different one of the virtual memory units having contents identical to the respective temporarily non-sharable virtual memory unit.

62. In a computer system that includes a hardware memory and at least one context, which has a virtual memory that is divided into a plurality of virtual memory units that are mappable to corresponding hardware memory units, a method comprising the following steps:

partitioning the virtual memory units into a plurality of classes;

identifying virtual memory units that have identical contents;

mapping those virtual memory units identified as having identical contents to a single instance of a corresponding one of the hardware memory units;

performing the step of identifying virtual memory units that have identical contents and the step of mapping those virtual memory units to a single shared instance of a corresponding hardware memory unit separately and independently for each of the classes; and

sharing single instances of the hardware memory units thereby taking place only among virtual memory units in the same class.

63. A method as in claim 62, in which the classes are page colors of the hardware memory units to which the corresponding virtual memory units are currently mapped.

64. A method as in claim 62, in which the computer system further has a multiprocessor architecture with a non-uniform memory access property and a plurality of memory modules having different access latency, and in which the classes are the memory modules to which the corresponding virtual memory units are currently mapped.

65. A method for sharing memory in a computer system comprising:

installing in the computer system at least one virtual machine that comprises;

at least one address space that is divided into a plurality of virtual memory units; and

a virtual operating system that maps each virtual memory unit to a corresponding intermediate memory unit;

for each virtual machine, maintaining in a virtual machine monitor an intermediate mapping that maps each intermediate memory unit to a corresponding hardware memory unit of a hardware memory;

selecting candidate memory units from among the intermediate memory units;

identifying intermediate memory units that have contents identical to those of the candidate memory units;

identifying intermediate memory units that have a relatively high probability of impending modification; and

via the intermediate mapping, mapping those intermediate memory units identified as having identical contents to a single instance of a corresponding one of the hardware memory units;

in which the step of mapping the intermediate memory units having identical contents further comprises write-protecting selected ones of the intermediate memory units that are mapped to the single instance.

66. A method as in claim 65, further comprising the following steps:

designating as temporarily non-sharable the intermediate memory units that have the relatively high probability of impending modification; and

deferring the step of mapping to the single instance for the temporarily non-sharable intermediate memory units.

67. A method as in claim 65, further comprising the following steps:

designating as temporarily non-sharable the intermediate memory units that have the relatively high probability of impending modification; and

deferring the step of write-protecting each temporarily non-sharable intermediate memory unit until a subsequent identification of a different one of the intermediate memory units having contents identical to the respective temporarily non-sharable intermediate memory unit.

68. A method for sharing memory in a computer system comprising:

installing in the computer system at least one virtual machine that comprises;

at least one address space that is divided into a plurality of virtual memory units; and

a virtual operating system that maps each virtual memory unit to a corresponding intermediate memory unit;

for each virtual machine, maintaining in a virtual machine monitor an intermediate mapping that maps each intermediate memory unit to a corresponding hardware memory unit of a hardware memory;

partitioning the intermediate memory units into a plurality of classes;

identifying intermediate memory units that have identical contents;

via the intermediate mapping, mapping those intermediate memory units identified as having identical contents to a single instance of a corresponding one of the hardware memory units;

performing the step of identifying intermediate memory units that have identical contents and the step of mapping those intermediate memory units to a single shared instance of a corresponding hardware memory unit separately and independently for each of the classes; and

sharing single instances of the hardware memory units thereby taking place only among intermediate memory units in the same class.

69. A method as in claim 68, in which the classes are page colors of the hardware memory units to which the corresponding intermediate memory units are currently mapped.

70. A method as in claim 68, in which the computer system further has a multiprocessor architecture with a non-uniform memory access property and a plurality of memory modules having different access latency, and in which the classes are the memory modules to which the corresponding intermediate memory units are currently mapped.

71. A computer system comprising:

a hardware memory;

at least one context, which has a virtual memory that is divided into a plurality of virtual memory units that are mappable to corresponding hardware memory units; and

a memory sharing module comprising computer-executable code for identifying virtual memory units that have identical contents and for mapping those virtual memory units identified as having identical contents to a single instance of a corresponding one of the hardware memory units;

in which;

the virtual memory units are partitioned into a plurality of classes; and

the memory sharing module is further provided for identifying virtual memory units that have identical contents and for mapping those virtual memory units to a single shared instance of a corresponding hardware memory unit separately and independently for each of the classes, whereby single instances of the hardware memory units are shared only among virtual memory units in the same class.

72. A system as in claim 71, in which the classes are page colors of the hardware memory units to which the corresponding virtual memory units are currently mapped.

73. A system as in claim 71, in which the computer system further has a multiprocessor architecture with a non-uniform memory access property and a plurality of memory modules having different access latency, and in which the classes are the memory modules to which the corresponding virtual memory units are currently mapped.

74. A computer system comprising:

a hardware memory;

at least one virtual machine that comprises;

at least one address space that is divided into a plurality of virtual memory units; and

a virtual operating system including means for mapping each virtual memory unit to a corresponding intermediate memory unit;

for each virtual machine, a corresponding virtual machine monitor including intermediate mapping means for mapping each intermediate memory unit to a corresponding hardware memory unit of the hardware memory;

a memory sharing module comprising computer-executable code for identifying intermediate memory units that have identical contents, and, via the intermediate mapping means, for mapping those intermediate memory units identified as having identical contents to a single instance of a corresponding one of the hardware memory units;

in which;

the virtual memory units are partitioned into a plurality of classes; and

the memory sharing module is further provided for identifying virtual memory units that have identical contents and for mapping those virtual memory units to a single shared instance of a corresponding hardware memory unit separately and independently for each of the classes, whereby single instances of the hardware memory units are shared only among virtual memory units in the same class.