Reuse of dynamically allocated memory

• US 9,069,477 B1
• Filed: 06/16/2011
• Issued: 06/30/2015
• Est. Priority Date: 06/16/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Overton, Adam J.
• Primary Examiner(s): Birkhimer, Christopher D
• Application Number:
  US13/161,844
• Time in Patent Office: 1,475 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0886 Variable-length word access
• 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/657 Virtual address space management

Abstract

Overall memory requirements are minimized by performing copy on write and collapse on write operations using memory pointers when storing data within memory pages. Multiple memory pointers may refer to a primary page storing a definitive copy of data. When that data is to be modified, a copy on write operation creates a second copy in another memory page which may then be modified and updates memory pointers accordingly. When data within two or more memory pages is identical to data within a primary page, a collapse on write operation updates memory pointers to refer to the primary page and de-allocates the duplicative and now unused memory pages.

Claims

1. A computer-readable storage media storing instructions that, when executed, instruct a processor to perform acts comprising:

associating a first virtual memory address pointer to a first memory page of a random access memory (RAM) and a second virtual memory address pointer to a second memory page of the RAM;

identifying one or more flagged memory pages of a plurality of memory pages, the one or more flagged memory pages associated with a flag that indicates that the corresponding page has been modified within a pre-determined interval of time;

identifying a plurality of target memory pages of the plurality of memory pages, the target memory pages excluding the one or more flagged memory pages and including at least the first memory page and the second memory page;

scanning the plurality of target memory pages for memory pages deemed to have identical contents;

identifying, based at least in part on the scanning, that the first memory page and the second memory page have contents that are deemed to be identical to one another;

designating the first memory page as a primary page;

designating the second memory page as a duplicate page; and

updating the second virtual memory address pointer referring to the second memory page to refer to the first memory page.

2. The computer-readable storage media of claim 1, further comprising de-allocating the second memory page.

3. The computer-readable storage media of claim 1, wherein the scanning comprises comparing hashes of the target memory pages.

4. The computer-readable storage media of claim 3, wherein the comparing hashes comprises querying a content addressable memory storing the hashes.

5. The computer-readable storage media of claim 1, wherein the scanning comprises:

identifying one or more updated memory pages of the one or more flagged memory pages, individual ones of the one or more updated memory pages indicating that a corresponding page has not been modified within the pre-determined interval of time; and

scanning the updated memory pages.

6. The computer-readable storage media of claim 1, wherein the pre-determined interval comprises a pre-determined number of memory access cycles.

7. The computer-readable storage media of claim 1, wherein the pre-determined interval is tracked using a timer configured to reset to a pre-determined value in response to a write request.

8. A system comprising:

a processor;

a random access memory (RAM), coupled to the processor; and

a memory manager module, coupled to the processor and coupled to the RAM, the memory manager module configured to;

associate a first address pointer to a first memory location of the RAM and a second address pointer to a second memory location of the RAM;

identify one or more flagged memory locations associated with a flag that indicates that a corresponding memory location is being read from or written to;

identify target memory locations excluding the one or more flagged memory locations, the target memory locations including at least the first memory location and the second memory location;

scan the target memory locations for memory locations deemed to have identical contents;

identify, based at least in part on the scanning, that the first memory location and the second memory location have contents that are deemed to be identical to one another;

designate the first memory location as a primary location;

designate the second memory location as a duplicate location; and

update the second address pointer referring to the second memory location to refer to the first memory location.

9. The system of claim 8, wherein the memory management module is further configured to de-allocate the second memory location.

10. The system of claim 8, wherein the scanning comprises comparing hashes of the target memory locations.

11. The system of claim 10, wherein the comparing hashes comprises querying a content addressable memory storing the hashes.

12. The system of claim 8, wherein the scanning comprises:

identifying one or more updated memory locations of the one or more flagged memory pages, individual ones of the one or more updated memory pages indicating that a corresponding location is no longer being read from or written to; and

scanning the updated memory locations.

13. The system of claim 8, wherein the flag indicates that the corresponding memory location has been modified within a pre-determined interval of time wherein the pre-determined interval comprises a pre-determined number of memory access cycles.

14. A method comprising:

identifying flagged memory pages of a Random Access Memory (RAM), the flagged memory pages associated with a flag indicating that a corresponding memory page has been modified within a pre-determined interval of time;

scanning target memory pages of the RAM for memory pages deemed to have identical contents, the target memory pages excluding the flagged memory pages;

identifying, based at least in part on the scanning, identical memory pages having contents that are deemed to be identical to one another; and

updating one or more address pointers referencing individual ones of the identical memory pages to reference a primary page of the identical memory pages.

15. The method of claim 14, the method further comprising de-allocating one or more of the identical memory pages.

16. The method of claim 14, wherein the scanning comprises comparing hashes of content stored at the target memory pages.

17. The method of claim 16, wherein the comparing hashes comprises querying a content addressable memory storing the hashes.

18. The method of claim 14, wherein the scanning comprises:

identifying one or more updated memory pages of the one or more flagged memory pages, individual ones of the one or more updated memory pages indicating that a corresponding page has not been modified within the pre-determined interval of time; and

scanning the updated memory pages.

19. The method of claim 14, wherein the pre-determined interval is tracked using a timer configured to reset to a pre-determined value in response to a write request.

20. One or more computer-readable storage media encoded with instructions that, when executed by one or more processors, causes the one or more processors to perform acts comprising:

identifying one or more flagged memory pages of a Random Access Memory (RAM), the one or more flagged memory pages associated with a flag indicating that a corresponding memory page has been modified within a pre-determined interval of time;

scanning target memory pages of the RAM for memory pages deemed to have identical contents, the target memory pages excluding the flagged memory pages;

identifying, based at least in part on the scanning, identical memory pages having contents that are deemed to be identical to one another; and

updating one or more address pointers referencing individual ones of the identical memory pages to reference a primary page of the identical memory pages.

21. The one or more computer-readable storage media of claim 20, further comprising de-allocating one or more of the identical memory pages.

22. The one or more computer-readable storage media of claim 20, wherein the scanning comprises comparing hashes of content stored at the target memory pages.

23. The one or more computer-readable storage media of claim 20, wherein the scanning comprises:

identifying one or more updated memory pages of the one or more flagged memory pages, individual ones of the one or more updated memory pages indicating that a corresponding page has not been modified within the pre-determined interval of time; and

scanning the updated memory pages.

24. The one or more computer-readable storage media of claim 20, wherein the pre-determined interval is tracked using a timer configured to reset to a pre-determined value in response to a write request.