Split-reference, two-pass mark-compaction

• US 7,389,395 B1
• Filed: 06/26/2005
• Issued: 06/17/2008
• Est. Priority Date: 06/26/2005
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Stoutamire, David P., Masamitsu, Jon A., Ramakrisha, Y Srinivas, Printezis, Antonios, Kessler, Peter B., Garthwaite, Alexander T., Detlefs, David L., Coomes, John W.
• Primary Examiner(s): Verbrugge; Kevin
• Application Number:
  US11/169,983
• Time in Patent Office: 1,087 Days
• Field of Search: None
• US Class Current: 711/165
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence

Abstract

A heap may be marked and compacted while performing only two passes over the objects and object references in the heap. Specifically, objects and object references are traversed once during a marking phase and again during a compaction phase of split-reference, two-pass mark-compaction. Object references are updated in two steps. First, during marking, each object reference may be updated to include the relative offset within its block of the referenced object and-during compaction that offset may be added to the block'"'"'s destination address resulting in a reference that points to the actual post-compaction location for the referenced object. Objects of a particular block may be rearranged, or permuted, with respect to each other within the block. However, the order between groups of objects in different blocks may be preserved across compaction.

Claims

1. A method for compacting a computer memory heap, comprising:

logically partitioning the heap into a plurality of logical blocks, wherein the heap comprises a plurality of reachable objects, wherein each of the plurality of reachable objects has a starting address in an associated one of plurality of blocks;

determining, for each of one or more of the plurality of reachable objects, an offset corresponding to a post-compaction address for the respective reachable object relative to a post-compaction address for an associated one of the blocks; and

wherein the respective offset for at least one of the one or more reachable objects is based on a combined size of one or more other reachable objects, wherein the at least one reachable object and the one or more other reachable objects are associated with a single associated one of the blocks.

2. The method of claim 1, wherein said determining comprises setting the respective offset to zero if no respective offset has been determined for any other reachable objects associated with the same associated block.

3. The method of claim 1, wherein said determining comprises:

if the respective reachable object spans a block boundary between the associated block and another one of the plurality of blocks storing an indication that the respective reachable object spans a block boundary in a header of the respective reachable object.

4. The method of claim 1, further comprising updating one or more references to one or more of the reachable objects, wherein said updating comprises modifying the respective object reference to include the determined offset for the respective referenced object.

5. The method of claim 4, wherein said updating comprises setting a plurality of low-order bits of the respective object reference to the determined offset for the respective referenced object.

6. The method of claim 1, further comprising for each of the one or more reachable objects:

adding a size of the respective reachable object to a count of reachable memory for the associated block.

7. The method of claim 6, further comprising, subsequent to determining the respective offsets for each of the one or more reachable objects:

determining the post-compaction address for each of the plurality of blocks, wherein the post-compaction address for a respective one of the plurality of blocks corresponds to a combined total of respective counts of live memory for one or more of the plurality of blocks located at lower heap addresses than the respective block.

8. The method of claim 1, further comprising updating each of the one or more object references to indicate the post-compaction address for the respective referenced object, wherein the post-compaction address for a respective reference object is based on the determined offset for the respective referenced object and the post-compaction address for a block associated with the respective referenced object.

9. The method of claim 1, further comprising moving each of the one or more reachable objects to its respective post-compaction address.

10. The method of claim 1, further comprising for each of the one or more reachable objects:

storing the determined offset in a header of the respective reachable object.

11. The method of claim 1, further comprising moving one or more of the plurality of reachable objects to respective locations in the heap to form a gap between two of the plurality of reachable objects.

12. The method of claim 1, wherein a plurality of threads perform said determining an offset for different ones of the one or more reachable objects in parallel.

13. A device, comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises program instructions configured to;

logically partition the heap into a plurality of logical blocks, wherein the heap comprises a plurality of reachable objects, wherein each of the plurality of reachable objects has a starting address in an associated one of plurality of blocks;

determine, for each of one or more of the plurality of reachable objects, an offset corresponding to a post-compaction address for the respective reachable object relative to a post-compaction address for an associated one of the blocks; and

wherein for at least one of the one or more reachable objects, the respective offset is based on a combined size of one or more other reachable objects, wherein the at least one reachable object and the one or more other reachable objects are associated with a single associated one of the blocks.

14. The device of claim 13, wherein in said determining the program instructions are further configured to set the respective offset to zero if no respective offset has been determined for any other reachable objects associated with the same associated block.

15. The device of claim 13, wherein in said determining the program instructions are further configured to:

if the respective reachable object spans a block boundary between the associated block and another one of the plurality of blocks store an indication that the respective reachable object spans a block boundary in a header of the respective reachable object.

16. The device of claim 13, wherein the program instructions are further configured to update one or more references to one or more of the reachable objects, wherein said updating comprises modifying the respective reference to include the determined offset for the respective referenced object.

17. The device of claim 16, wherein in said updating the program instructions are configured to set a plurality of low-order bits of the respective reference to the determined offset for the respective referenced object.

18. The device of claim 13, wherein the program instructions are further configured to, for each of the one or more reachable objects:

add a size of the respective reachable object to a count of reachable memory for the associated block.

19. The device of claim 18, wherein the program instructions are further configured to, subsequent to determining the respective offsets for each of the one or more reachable objects:

determine the post-compaction address for each of the plurality of blocks, wherein the post-compaction address for a respective one of the plurality of blocks corresponds to a combined total of respective counts of live memory for one or more of the plurality of blocks located at lower heap addresses than the respective block.

20. The device of claim 13, wherein the program instructions are further configured to update each of the one or more object references to indicate the post-compaction address for the respective referenced object, wherein the post-compaction address for a respective reference object is based on the determined offset for the respective referenced object and the post-compaction address for a block associated with the respective referenced object.

21. The device of claim 13, wherein the program instructions are further configured to move each of the one or more reachable objects to its respective post-compaction address.

22. The device of claim 13, wherein the program instructions are further configured to, for each of the one or more reachable objects, store the determined offset in a header of the respective reachable object.

23. The device of claim 13, wherein the program instructions are further configured to move one or more of the plurality of reachable objects to respective locations in the heap to form a gap between two of the plurality of reachable objects.

24. The device of claim 13, wherein the program instructions are configured to implement a plurality of threads;

wherein the plurality of threads perform determine an offset for different ones of the one or more reachable objects in parallel.

25. A computer accessible medium, comprising program instructions executable to implement:

logically partitioning the heap into a plurality of logical blocks, wherein the heap comprises a plurality of reachable objects, wherein each of the plurality of reachable objects has a starting address in an associated one of plurality of blocks;

determining, for each of one or more of the plurality of reachable objects, an offset corresponding to a post-compaction address for the respective reachable object relative to a post-compaction address for an associated one of the blocks; and

wherein for at least one of the one or more reachable objects, the respective offset is based on a combined size of one or more other reachable objects, wherein the at least one reachable object and the one or more other reachable objects are associated with a single associated one of the blocks.