Memory sharing and page deduplication using indirect lines

Patent metadata

Field	Value
Publication number	US-9501421-B1
Application number	US-201213541396-A
Country	US
Kind code	B1
Filing date	Jul 3, 2012
Priority date	Jul 5, 2011
Publication date	Nov 22, 2016
Grant date	Nov 22, 2016

Abstract

Memory management includes maintaining a plurality of physical pages corresponding to a respective plurality of indirect lines, where each of the plurality of indirect lines corresponds to a set of one or more data lines. Memory management further includes receiving a request to create a new physical page; determining whether there is an existing physical page that has matching content to the new physical page; and in the event that there is an existing physical page that has matching content as the new physical page, associating the new physical page with the same data lines as those corresponding to the matching content referenced by the indirect line associated with the existing physical page.

First claim

What is claimed is:

1. A memory system comprising:
a memory to maintain a plurality of physical pages that reference a respective plurality of indirect lines, wherein each of the plurality of indirect lines corresponds to a set of one or more data lines, and wherein a data line in the set of one or more data lines is distinct from any of the plurality of physical pages; and
a memory module coupled to the memory, to:
in response to a request to create a new physical page:
determine whether there is an existing physical page that has matching content as the new physical page, wherein the new physical page is distinct from any indirect line and is distinct from any data line, and the existing physical page is distinct from any indirect line and is distinct from any data line; and
in the event that there is an existing physical page that has matching content as the new physical page, associate the new physical page with the same data lines as those corresponding to the matching content referenced by at least one indirect line associated with the existing physical page, wherein the new physical page is associated with the same data lines by associating the new physical page with the same at least one indirect line associated with the existing physical page, and wherein:
the existing physical page, which is determined to have matching content as the new physical page, resides in a first memory space and references the at least one indirect line,
the at least one indirect line resides in a second memory space that is separate from the first memory space, and
the at least one indirect line references a set of data lines storing the matching content.

2. The system of claim 1 , wherein each of the plurality of physical pages is created to include unique content.

3. The system of claim 1 , wherein the data lines have immutable content.

4. The system of claim 1 , wherein a virtual memory page that corresponds to the new physical page is marked as read-only or copy-on-write.

5. The system of claim 1 , wherein the memory is further to maintain a physical page map collection (PPMC) to support lookup of specific physical pages.

6. The system of claim 5 , wherein the PPMC includes a table that maps hash values of physical page content to physical pages.

7. The system of claim 5 , wherein the PPMC includes a table that maps identifiers of physical page content to physical pages.

8. The system of claim 5 , wherein the memory module to determine whether there is an existing physical page that has matching content as the new physical page includes to look up the existing physical page in the PPMC.

9. The system of claim 5 , wherein in the event that there is an existing physical page that has matching content as the new physical page, the memory module is further to update the PPMC with the new physical page.

10. The system of claim 1 , wherein a physical page and a virtual page are equal in size.

11. The system of claim 1 , wherein a virtual page is greater in size than a physical page.

12. The system of claim 11 , wherein the new physical page is one of a plurality of consecutive new pages that correspond to the virtual page.

13. The system of claim 1 , wherein the new physical page is associated with an indirect line that references a data line filled with zeros.

14. The system of claim 1 , wherein the memory module is further to:
in response to a request to write content to a shared physical page:
obtain a destination page;
obtain a new indirect line that is an indirect copy of an indirect line associated with the shared physical page;
determine an appropriate data line comprising at least a portion of the content to be written;
associate the appropriate data line with the new indirect line;
and associate the new indirect line with the destination page.

15. The system of claim 14 , wherein the appropriate data line comprising at least a portion of the content to be written is identified among existing data lines.

16. The system of claim 14 , wherein the appropriate data line comprising at least a portion of the content to be written is created.

17. The system of claim 14 , wherein in response to the request to write content to the shared physical page, the memory module is further to update a physical page map collection (PPMC) that supports lookup of specific physical pages.

18. The system of claim 14 , wherein the new indirect line is created before the request to write is initiated.

19. The system of claim 1 , further comprising a processor to perform garbage collection on unreferenced data lines.

20. The system of claim 1 , further comprising a processor to detect duplicated physical pages and perform deduplication.

21. A method of memory management, comprising:
maintaining a plurality of physical pages that reference a respective plurality of indirect lines, wherein each of the plurality of indirect lines corresponds to a set of one or more data lines, and wherein a data line in the set of one or more data lines is distinct from any of the plurality of physical pages;
receiving a request to create a new physical page;
determining whether there is an existing physical page that has matching content as the new physical page, wherein the new physical page is distinct from any indirect line and is distinct from any data line; and the existing physical page is distinct from any indirect line and is distinct from any data line; and
in the event that there is an existing physical page that has matching content as the new physical page, associating the new physical page with the same data lines as those corresponding to the matching content referenced by at least one indirect line associated with the existing physical page, wherein the new physical page is associated with the same data lines by associating the new physical page with the same at least one indirect line associated with the existing physical page, and wherein:
the existing physical page, which is determined to have matching content as the new physical page, resides in a first memory space and references the at least one indirect line,
the at least one indirect line resides in a second memory space that is separate from the first memory space, and
the at least one indirect line references a set of data lines storing the matching content.

22. A computer program product for memory management, the computer program product being embodied in a tangible non-transitory computer readable storage medium and comprising computer instructions, which in response to execution by one or more processors, cause to:
maintain a plurality of physical pages that reference a respective plurality of indirect lines, wherein each of the plurality of indirect lines corresponds to a set of one or more data lines, and wherein a data line in the set of one or more data lines is distinct from any of the plurality of physical pages;
receive a request to create a new physical page;
determine whether there is an existing physical page that has matching content as the new physical page, wherein the new physical page is distinct from any indirect line and is distinct from any data line, and the existing physical page is distinct from any indirect line and is distinct from any data line; and
in the event that there is an existing physical page that has matching content as the new physical page, associate the new physical page with the same data lines as those corresponding to the matching content referenced by at least one indirect line ass

Assignees

• Cheriton David R
• Intel Corp

Inventors

• Cheriton David R

Classifications

• G06F3/0641

  De-duplication techniques · CPC title

• G06F12/10 Primary

  Address translation · CPC title

• G06F3/0608

  Saving storage space on storage systems · CPC title