Conservative garbage collecting and tagged integers for memory management

Patent metadata

Field	Value
Publication number	US-9684679-B2
Application number	US-201414485800-A
Country	US
Kind code	B2
Filing date	Sep 15, 2014
Priority date	Apr 25, 2011
Publication date	Jun 20, 2017
Grant date	Jun 20, 2017

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 object graph including at least one object associated with a tagged integer representation and at least one object associated with an untagged 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 only on objects associated with the untagged pointer representations after distinguishing the objects associated with the untagged pointer representations from the objects 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.

2. The method of claim 1 , wherein the first trace is performed on root objects reachable by an unexecuted portion of the call stack.

3. The method of claim 1 , wherein the second trace is a subsequent trace of objects related to one or more objects on which the first trace was performed.

4. The method claim of claim 1 , wherein the monitored size of the heap is determined during execution of the call stack.

5. The method of claim 1 , wherein reclaiming memory locations further comprises:
preserving objects reachable by the unexecuted portion of the call stack in original storage locations of the heap.

6. The method of claim 1 , wherein reclaiming memory locations further comprises:
clearing memory allocated to one or more objects unreachable by the unexecuted portion of the call stack.

7. The method of claim 3 , wherein the second trace further comprises:
skipping the subsequent trace on objects associated with the tagged integer representations.

8. A device, comprising:
at least one processor and a memory;
the at least one processor configured to:
tag integer representations in an object graph associated with a call stack, the object graph including at least one object associated with a tagged integer representation and at least one object associated with an untagged pointer representation;
generate 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;
determine whether a monitored size of the heap exceeds a threshold;
based on the determination, perform a first trace on objects reachable by an unexecuted portion of the call stack;
perform a second trace only on objects associated with the untagged pointer representations after distinguishing the objects associated with the untagged pointer representations from the objects associated with the tagged integer representations; and
reclaim memory locations corresponding to one or more objects unreachable by the unexecuted portion of the call stack.

9. The device of claim 8 , wherein the first trace is performed on root objects reachable by an unexecuted portion of the call stack.

10. The device of claim 8 , wherein the second trace is a subsequent trace of objects related to one or more objects on which the first trace was performed.

11. The device of claim 8 , wherein the monitored size of the heap is determined during execution of the call stack.

12. The device of claim 8 , wherein the at least one processor is further configured to:
preserve objects reachable by the unexecuted portion of the call stack in original storage locations of the heap.

13. The device of claim 8 , wherein the at least one processor is further configured to:
clear memory allocated to one or more objects unreachable by the unexecuted portion of the call stack.

14. The device of 10 , wherein the at least one processor is further configured to:
during the second trace, skip the subsequent trace on objects associated with the tagged integer.

15. A system, comprising:
at least one processor and a memory;
the memory including at least one module including instructions for causing the at least one processor to perform actions comprising:
tag integer representations in an object graph associated with a call stack, the object graph including at least one object associated with a tagged integer representation and at least one object associated with an untagged pointer representation;
generate 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;
determine whether a monitored size of the heap exceeds a threshold;
based on the determination, perform a first trace on objects reachable by an unexecuted portion of the call stack;
perform a second trace only on objects associated with the untagged pointer representations after distinguishing the objects associated with the untagged pointer representations from the objects associated with the tagged integer representations; and
reclaim memory locations corresponding to one or more objects unreachable by the unexecuted portion of the call stack.

16. The system of claim 15 , wherein the first trace is performed on root objects reachable by an unexecuted portion of the call stack.

17. The system of claim 15 , wherein the second trace is a subsequent trace of objects related to one or more objects on which the first trace was performed.

18. The system of claim 15 , wherein the monitored size of the heap is determined during execution of the call stack.

19. The system of claim 15 , wherein reclaiming memory locations further comprises:
preserving objects reachable by the unexecuted portion of the call stack in original storage locations of the heap.

20. The system of claim 15 , wherein the at least one module includes further instructions for causing the at least one processor to perform actions comprising:
clear memory allocated to one or more objects unreachable by the unexecuted portion of the call stack.

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

• G06F16/215 Primary

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

• G06F2212/702

  Conservative garbage collection · CPC title

• G06F17/30303 Primary

  Physics · mapped topic