Conservative garbage collecting and tagged integers for memory management

Patent metadata

Field	Value
Publication number	US-10628398-B2
Application number	US-201715597096-A
Country	US
Kind code	B2
Filing date	May 16, 2017
Priority date	Apr 25, 2011
Publication date	Apr 21, 2020
Grant date	Apr 21, 2020

Abstract

Aspects for conservative garbage collecting are disclosed. In one aspect, root objects included in a call stack are identified, which comprise integers and pointers. Integer representations are tagged and distinguishable from untagged pointer representations. Root objects are traced to corresponding memory locations such that a subsequent tracing is performed on the pointer representations and skipped on the integer representations. Memory allocated to objects unreachable by the call stack is then freed. In another aspect, an object graph associated with a call stack is tagged, and a heap is generated comprising objects included in an executed portion of the call stack. Objects included in an unexecuted portion of the call stack are traced to corresponding memory locations on the heap such that a subsequent tracing is only performed on the untagged pointer representations. Memory locations corresponding to heap objects unreachable by the unexecuted portion of the call stack are then cleared.

First claim

What is claimed is:

1. A method, comprising:
tagging integer representations in an object graph associated with a call stack, the call stack including one or more root objects, the object graph including at least one root object associated with a tagged integer representation and at least one root object associated with an untagged pointer representation;
generating a heap of objects during an execution of the call stack, the heap of objects including root objects in an executed portion of the call stack;
performing a first trace on unexecuted root objects included in an unexecuted portion of the call stack to corresponding memory locations on the heap;
performing a subsequent trace on memory locations associated with the untagged pointer representations identified by the object graph, while skipping the subsequent trace on the tagged integer representations identified by the object graph; and
clearing memory locations corresponding to objects on the heap unreachable by one or more root objects in the unexecuted portion of the call stack.

2. The method of claim 1 , further comprising:
monitoring a size of the heap during the execution of the call stack, and wherein the clearing of memory locations corresponding to objects is triggered by the size of the heap exceeding a threshold.

3. The method of claim 1 , wherein clearing memory locations corresponding to objects, further comprises:
preserving a storage of reachable objects in original memory locations of the heap, the reachable objects are reachable by the unexecuted portion of the call stack.

4. The method of claim 1 , wherein the call stack is associated with a compilation of a script.

5. The method of claim 1 , wherein the call stack is associated with a modification of an object model.

6. The method of claim 1 , wherein tagging integer representations in an object graph associated with a call stack further comprises:
transforming the integer representations into a data structure that differs from the pointer representations.

7. The method of claim 6 , wherein at least one bit of the different data structure represents a tag.

8. A method, comprising:
executing script code that allocates memory for a plurality of objects, the plurality of objects including at least one of an integer value and a pointer value;
during execution of the script code, tagging the at least one integer value in a tagged object graph;
determining which objects of the plurality of objects are unreachable by an unexecuted call stack by identifying the unreachable objects as not being included in the tagged object graph; and
clearing memory locations corresponding to the unreachable objects.

9. The method of claim 8 , wherein the script code includes Javascript code that is executed against a document object model.

10. The method of claim 8 , further comprising:
using the tagged object graph to determine which objects in the unexecuted call stack are reachable by tracing root objects in the unexecuted call stack to corresponding memory locations.

11. The method of claim 10 , further comprising:
skipping a subsequent trace on a reachable tagged integer value and performing the subsequent trace on reachable untagged pointer values.

12. The method of claim 10 , further comprising:
tracing one or more untagged root pointer values to identity a reachable object and only performing a subsequent trace on a reachable untagged pointer value.

13. The method of claim 8 , wherein execution of the script code further comprises:
executing a call stack; and
generating the memory for the plurality of objects in a heap.

14. The method of claim 13 , further comprising:
tracing objects in an unexecuted portion of the call stack to locations in the heap and only performing a subsequent trace on reachable pointer values.

15. A method, comprising:
tagging integer representations in an object graph associated with a call stack, the object graph including at least one root object associated with a tagged integer representation and at least one root object associated with a pointer representation;
generating a heap of objects during an execution of the call stack, the heap of objects including one or more objects associated with the call stack;
determining whether a monitored size of the heap exceeds a threshold;
based on the determination, performing a first trace on objects reachable by an unexecuted portion of the call stack;
performing a second trace on objects that are not associated with the tagged integer representations; and
reclaiming memory locations corresponding to one or more objects unreachable by the unexecuted portion of the call stack.

16. A method, comprising:
determining whether a monitored size of a heap exceeds a threshold, wherein the heap comprises a first set of integer objects and a second set of pointer objects, and wherein one or more objects in the first set of objects are associated with a tagged integer representation;
based on the determination, performing a first trace on objects reachable by an unexecuted portion of the call stack;
performing a second trace, wherein the second trace does not include the one or more objects in the first set associated with a tagged integer representation; and
reclaiming memory locations corresponding to one or more unreachable objects.

17. The method of claim 16 further comprising tagging the one or more objects in the first set and transforming integer representations of the one or more objects in the first set into a first data structure.

18. The method of claim 17 , wherein the first data structure comprises at least one bit dedicated to a tag.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Lucco Steven
• Man Curtis Cheng-Cheng

Classifications

• G06F12/0253 Primary

  Garbage collection, i.e. reclamation of unreferenced memory · CPC title

• G06F2212/702

  Conservative garbage collection · CPC title

• G06F16/215 Primary

  Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors · CPC title