Manual memory management using lazy patching

• US 10,496,534 B2
• Filed: 06/15/2017
• Issued: 12/03/2019
• Est. Priority Date: 03/27/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Vytiniotis, Dimitrios, Costa, Manuel Silverio da Silva, Vaswani, Kapil, Parkinson, Matthew John, Kedia, Piyus Kumar
• Primary Examiner(s): Farrokh, Hashem
• Application Number:
  US15/624,687
• Publication Number:
  US 20180276120A1
• Time in Patent Office: 901 Days
• Field of Search: 711166, 711170
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0261 using reference counting
• CPC Class Codes: G06F 12/109 for multiple virtual address spaces, e.g. segmentation G06F12/1036 takes precedence
• CPC Class Codes: G06F 12/145 the protection being virtual, e.g. for virtual blocks or segments before a translation mechanism
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/1052 Security improvement
• CPC Class Codes: G06F 2212/657 Virtual address space management

Abstract

A method of manual memory management is described. In response to detecting an access violation triggered by the use of an invalid reference to an object in a manual heap, a source of the access in a register or stack is identified. An updated reference for the object using stored mapping data is determined and used to replace the invalid reference in the source.

Claims

1. A method of manual memory management comprising:

in response to detecting an access violation when an invalid reference to a child object in a manual heap is used;

identifying a source of the access violation in a register or stack;

identifying a parent object in the manual heap, wherein the parent object is an object from which the source was loaded into the register or stack;

determining an updated reference for the child object using stored mapping data; and

replacing the invalid reference in the source with the updated reference to the child object in the parent object.

2. The method according to claim 1, wherein the manual heap is defined in virtual address space and divided into a plurality of pages and wherein the invalid reference is a consequence of the object having been copied from a first page in the virtual address space to a second page in the virtual address space.

3. The method according to claim 2, wherein the stored mapping data defines a mapping from a location of the object on the first page to a location of the object on the second page.

4. The method according to claim 1, further comprising, in response to detecting an access violation when an invalid reference to an object in a manual heap is used:

searching the register and stack to identify any other instances of the invalid reference; and

replacing the invalid reference in any identified instances with an updated reference.

5. The method according to claim 4, wherein identifying a source of the access in a register or stack comprises:

searching a current stack frame for the invalid reference; and

in response to failing to find the invalid reference in the current stack frame, repeatedly popping the current stack frame and searching a next stack frame until the invalid reference is found.

6. The method according to claim 1, further comprising, at compile-time:

extending a lifetime of a variable containing a reference to a parent object such that the variable containing the reference to the parent object is in a register or stack when any references to a child object are used.

7. The method according to claim 1, further comprising, at compile-time:

modifying generation of code to explicitly expose references to a parent object in the stack or registers.

8. The method according to claim 1, further comprising, at compile-time:

instrumenting memory management patches that return a child object to push a reference to a parent object into a circular buffer,

and wherein identifying a parent object in the manual heap comprises;

scanning the circular buffer for a reference to the parent object.

9. The method according to claim 1, wherein the manual heap is defined in virtual address space and divided into a plurality of pages, the method further comprising:

in response to deallocation of an object in a manual heap, marking the object as freed;

in response to determining that an entire page of the virtual address space comprises only freed objects and no live objects, unmapping the page from physical address space; and

in response to determining that fragmentation of one or more pages of the virtual address space exceeds a fragmentation threshold, selecting a page from the one or more pages, moving all live objects from the selected page to another page and unmapping the selected page from physical address space.

10. The method according to claim 9, wherein selecting a page from the one or more pages, moving all live objects from the selected page to another page and unmapping the selected page from physical address space comprises:

first selecting a page from the one or more pages;

disabling write access to the selected page;

after disabling write access to the selected page, copying all live objects from the selected page to a target page;

after copying all the live objects, disabling write access to the target page;

storing mapping data mapping locations of all the live objects on the selected page to their locations on the target page;

after copying all the live objects, unmapping the selected page from physical address space; and

subsequently enabling write access to the target page.

11. The method according to claim 9, wherein the manual heap is logically divided into segments and each segment is divided into a plurality of generations, and wherein moving all live objects from the selected page to another page comprises:

moving all live objects from the selected page in a first generation in a segment to another page in a next generation within the same segment.

12. The method according to claim 9, wherein determining that fragmentation of one or more pages of the virtual address space exceeds a fragmentation threshold comprises:

determining that fragmentation of the entire virtual address space exceeds a first fragmentation threshold; and

in response to determining that fragmentation of the entire virtual address space exceeds a first fragmentation threshold, selecting a plurality of candidate pages;

and repeatedly selecting a candidate page, moving all live objects from the selected candidate page to another page and unmapping the selected candidate page from physical address space until the fragmentation of the entire virtual address space does not exceed a second fragmentation threshold, wherein the first fragmentation threshold is higher than the second fragmentation threshold.

13. The method according to claim 1, further comprising:

in response to detecting a rate of access violations in excess of a threshold rate, scanning live objects in the manual heap and replacing invalid references.

14. A method of memory reclamation comprising:

in response to deallocation of an object in a manual heap, marking the object as freed, wherein the manual heap is defined in virtual address space and divided into a plurality of pages;

in response to determining that an entire page of the virtual address space comprises only freed objects and no live objects, unmapping the page from physical address space; and

in response to determining that fragmentation of one or more pages of the virtual address space exceeds a fragmentation threshold, selecting a page from the one or more pages, moving all live objects from the selected page to another page and unmapping the selected page from physical address space.

15. The method according to claim 14, wherein selecting a page from the one or more pages, moving all live objects from the selected page to another page and unmapping the selected page from physical address space comprises:

first selecting a page from the one or more pages;

disabling write access to the selected page;

after disabling write access to the selected page, copying all live objects from the selected page to a target page;

after copying all the live objects, disabling write access to the target page;

storing mapping data mapping locations of all the live objects on the selected page to their locations on the target page;

after copying all the live objects, unmapping the selected page from physical address space; and

subsequently enabling write access to the target page.

16. The method according to claim 15, wherein the manual heap is logically divided into segments and each segment is divided into a plurality of generations, and wherein moving all live objects from the selected page to another page comprises:

moving all live objects from the selected page in a first generation in a segment to another page in a next generation within the same segment.

17. The method according to claim 15, wherein determining that fragmentation of one or more pages of the virtual address space exceeds a fragmentation threshold comprises:

determining that fragmentation of the entire virtual address space exceeds a first fragmentation threshold; and

in response to determining that fragmentation of the entire virtual address space exceeds a first fragmentation threshold, selecting a plurality of candidate pages; and

repeatedly selecting a candidate page, moving all live objects from the selected candidate page to another page and unmapping the selected candidate page from physical address space until the fragmentation of the entire virtual address space does not exceed a second fragmentation threshold, wherein the first fragmentation threshold is higher than the second fragmentation threshold.

18. The method according to claim 17, wherein fragmentation of the entire virtual address space is determined by dividing total non-reclaimed bytes by total bytes allocated to live objects.

20. The method according to claim 17, wherein the first fragmentation threshold is 0.5.

19. A method comprising two or more of:

modifying, in a compiler, generation of code to explicitly expose references to a parent object in a stack or registers, wherein a parent object is an object in a manual heap that contains a reference to a second object, wherein the second object is a child object corresponding to the parent object;

extending, in the compiler, a lifetime of a variable containing a reference to a parent object such that the variable containing the reference to the parent object is in a register or stack when any references to a corresponding child object are used; and

instrumenting, in the compiler, memory management patches that return a child object to push a reference to the corresponding parent object into a circular buffer.