Content-based, transparent sharing of memory units

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.