MEMORY SHARING AMONG COMPUTER PROGRAMS

• US 20100223432A1
• Filed: 02/27/2009
• Published: 09/02/2010
• Est. Priority Date: 02/27/2009
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Inventors: Arcangeli, Andrea, Wright, Christopher M., Eidus, Izik
• Granted Patent: US 8,190,827 B2
• Time in Patent Office: Days
• US Class Current: 711/148
• CPC Class Codes: G06F 12/1036 for multiple virtual address spaces, e.g. segmentation G06F12/1045 takes precedence
• CPC Class Codes: G06F 12/109 for multiple virtual address spaces, e.g. segmentation G06F12/1036 takes precedence
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 2212/656 Address space sharing
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes

Abstract

A physical memory location among multiple programs is shared among multiple programs. In one embodiment, multiple memory units are scanned to detect duplicated contents in the memory units. The memory units are used by programs running on a computer system. A data structure is used to identify memory units of identical contents. To improve performance, an additional data structure can be used to identify memory units of identical contents. Memory units that are identified to have identical contents can share the same physical memory space.

Claims

1. A computer-implemented method comprising:

scanning, by a computer system, each of a plurality of memory units that are used by a plurality of programs running on the computer system;

sorting, by the computer system, the memory units by contents using a data structure that contains references to the memory units to identify the memory units having identical contents; and

causing, by the computer system, the same physical memory space to be shared among the memory units that are identified to have identical contents.

2. The method of claim 1, wherein all of the memory units pointed to by the data structure are protected against write operations.

3. The method of claim 1, wherein the data structure is a tree.

4. The method of claim 1, wherein the data structure contains references to only the memory units that have unchanged contents for a period of time.

5. The method of claim 4, further comprising:

using a checksum, a hash value, or a dirty bit to determine whether a candidate memory unit has unchanged contents for the period of time.

6. The method of claim 1, further comprising:

re-initializing the data structure each time after all of the memory units are scanned.

7. The method of claim 1, wherein the data structure is a red-black tree (rbtree).

8. The method of claim 1, wherein the data structure holds internal information inside each tree node to guarantee O(log(N)) lookup, insertion and deletion computational complexity, the computational complexity staying the same when the contents of the memory units are changing and the data structure is not being updated accordingly.

9. The method of claim 1, further comprising:

sorting, by the computer system, the memory units by contents using an additional data structure that contains references to the memory units;

identifying the memory units having identical contents using the additional data structure; and

placing the memory units identified with the additional data structure into the data structure.

10. The method of claim 9, wherein the additional data structure is a tree.

11. The method of claim 9, wherein the additional data structure contains references to only the memory units that have unchanged contents for a period of time.

12. The method of claim 11, further comprising:

using a checksum, a hash value, or a dirty bit to determine whether a candidate memory unit has unchanged contents for the period of time.

13. The method of claim 9, further comprising:

re-initializing the additional data structure each time after all of the memory units are scanned.

14. The method of claim 9, wherein the additional data structure is a red-black tree (rbtree).

15. The method of claim 9, wherein the additional data structure holds internal information inside each tree node to guarantee O(log(N)) lookup, insertion and deletion computational complexity, the computational complexity staying the same when the contents of the memory units are changing and the additional data structure is not being updated accordingly.

16. The method of claim 1, further comprising:

sorting, by the computer system, the memory units by contents using an additional data structure that contains references to the memory units that are not write protected, while the data structure contains only references to memory units that are write protected;

identifying memory units having the same contents as the candidate memory unit by searching both the data structure and the additional data structure if no match is found in the data structure; and

placing a merged memory unit into the data structure if a match is found in the additional data structure, the merged memory unit formed by merging the candidate memory unit and a matching memory unit found in the additional data structure.

17. The method of claim 1, wherein the memory units include disk storage units.

18. The method of claim 1, wherein causing the same physical memory space to be shared further comprises:

determining whether the memory units can share the same physical memory space by taking into consideration of the locality of the memory units with respect to NUMA nodes in the computer system.

19. A system comprising:

data storage to include a plurality of memory units that are used by a plurality of programs running on a computer system;

a memory manager coupled to the data storage, the memory manager to scan each of the plurality of memory units and to sort the memory units by contents using a data structure to identify the memory units having identical contents, wherein the data structure contains references to the memory units; and

a page mapping module coupled to the memory manager to map the same physical memory space to the memory units that are identified to have identical contents.

20. The system of claim 19, wherein all of the memory units pointed to by the data structure are protected against write operations.

21. The system of claim 19, wherein the data structure contains references to only the memory units that have unchanged contents for a period of time.

22. The system of claim 19, wherein the data structure is re-initialized each time after all of the memory units are scanned.

23. The system of claim 19, wherein the memory manager is to further sort the memory units by contents using an additional data structure that contains references to the memory units, to identify the memory units having identical contents using the additional data structure, and to place the memory units identified with the additional data structure into the data structure.

26. The computer readable storage medium of claim 23, wherein the data structure contains references to only the memory units that have unchanged contents for a period of time.

24. A computer readable storage medium including instructions that, when executed by a processing system, cause the processing system to perform a method comprising:

scanning each of a plurality of memory units that are used by a plurality of programs running on the computer system;

sorting the memory units by contents using a data structure that contains references to the memory units to identify the memory units having identical contents; and

causing the same physical memory space to be shared among the memory units that are identified to have identical contents.

25. The computer readable storage medium of claim 24, wherein all of the memory units pointed to by the data structure are protected against write operations.

27. The computer readable storage medium of claim 24, wherein the method further comprises:

re-initializing the data structure each time after all of the memory units are scanned.

28. The computer readable storage medium of claim 24, wherein the method further comprises:

sorting, by the computer system, the memory units by contents using an additional data structure that contains references to the memory units;

identifying the memory units having identical contents using the additional data structure; and

placing the memory units identified with the additional data structure into the data structure.