Method and apparatus for performing generational garbage collection in a segmented heap

• US 6,928,460 B2
• Filed: 07/01/2002
• Issued: 08/09/2005
• Est. Priority Date: 07/01/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Fresko, Nedim, Rochetti, Robert, Nagarajan, Vijay G.
• Primary Examiner(s): Wassum, Luke S
• Application Number:
  US10/189,054
• Publication Number:
  US 20040003014A1
• Time in Patent Office: 1,135 Days
• Field of Search: 707/206
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

One embodiment of the present invention provides a system that facilitates performing generational garbage collection on a heap. The system operates by dividing an old generation of the heap into segments. Next, the system divides each segment into a series of cards and associates a separate card table with each segment. This card table has an entry for each card in the segment. In a variation on this embodiment, while updating a pointer within an object in the old generation, the system locates the segment containing the object and accesses the card table for the segment. The system then marks the entry in the card table associated with the card containing the object.

Claims

1. A method for performing generational garbage collection on a heap, comprising:

dividing an old generation of the heap into segments;

dividing each segment into a series of cards; and

associating a card table with each segment, wherein the card table has an entry for each card in the series of cards.

2. The method of claim 1, further comprising storing the card table for a segment within the segment.

3. The method of claim 2, wherein upon receiving an update to a pointer within an object in the old generation, the method further comprises:

locating the segment containing the object;

accessing the card table for the segment; and

marking the entry in the card table associated with the card containing the object.

4. The method of claim 3, wherein during garbage collection, the method further comprises:

locating an updated card in the old generation by inspecting the card table for a marked entry;

examining pointers in the updated card; and

establishing that objects pointed to by pointers in the updated card are still active.

5. The method of claim 1, wherein dividing the heap into segments involves dividing the heap in segments along power-of-two address boundaries.

6. The method of claim 5,

wherein if a large object that is larger than the size of the segment requires storage, a large segment is allocated with sufficient memory to hold the object;

and

wherein the large segment stores only the large object.

7. The method of claim 6, wherein the large segment is not moved during a heap compaction.

8. The method of claim 1, further comprising:

maintaining a hot list of segments that hold objects newly promoted from a young generation to the old generation; and

adding an updated segment to the hot list when an object is promoted from the young generation to the old generation.

9. The method of claim 1, further comprising maintaining a list of segments, wherein the list of segments is maintained in low-to-high address order.

10. The method of claim 1, further comprising promoting objects from a young generation to the old generation by:

selecting an object that can be promoted; and

iterating through segments to find a hole in the old generation that can hold the selected object.

11. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for performing generational garbage collection on a heap, the method comprising:

dividing an old generation of the heap into segments;

dividing each segment into a series of cards; and

associating a card table with each segment, wherein the card table has an entry for each card in the series of cards.

12. The computer-readable storage medium of claim 11, the method further comprising storing the card table for a segment within the segment.

13. The computer-readable storage medium of claim 12, wherein upon receiving an update to a pointer within an object in the old generation, the method further comprises:

locating the segment containing the object;

accessing the card table for the segment; and

marking the entry in the card table associated with the card containing the object.

14. The computer-readable storage medium of claim 13, wherein during garbage collection, the method further comprises:

locating an updated card in the old generation by inspecting the card table for a marked entry;

examining pointers in the updated card; and

establishing that objects pointed to by pointers in the updated card are still active.

15. The computer-readable storage medium of claim 11, wherein dividing the heap into segments involves dividing the heap in segments along power-of-two address boundaries.

16. The computer-readable storage medium of claim 15,

wherein if a large object that is larger than the size of the segment requires storage, a large segment is allocated with sufficient memory to hold the object;

and

wherein the large segment stores only the large object.

17. The computer-readable storage medium of claim 16, wherein the large segment is not moved during a heap compaction.

18. The computer-readable storage medium of claim 11, the method further comprising:

maintaining a hot list of segments that hold objects newly promoted from a young generation to the old generation; and

adding an updated segment to the hot list when an object is promoted from the young generation to the old generation.

19. The computer-readable storage medium of claim 11, the method further comprising maintaining a list of segments, wherein the list of segments is maintained in low-to-high address order.

20. The computer-readable storage medium of claim 11, the method further comprising promoting objects from a young generation to the old generation by:

selecting an object that can be promoted; and

iterating through segments to find a hole in the old generation that can hold the selected object.

21. An apparatus for performing generational garbage collection on a heap, comprising:

a dividing mechanism that is configured to divide an old generation of the heap into segments;

wherein the dividing mechanism is further configured to divide each segment into a series of cards; and

an associating mechanism that is configured to associate a card table with each segment, wherein the card table has an entry for each card in the series of cards.

22. The apparatus of claim 21, further comprising a storing mechanism that is configured to store the card table for a segment within the segment.

23. The apparatus of claim 22, further comprising:

a locating mechanism that is configured to locate the segment containing an object;

an accessing mechanism that is configured to access the card table for the segment; and

a marking mechanism that is configured to mark the entry in the card table associated with the card containing the object.

24. The apparatus of claim 22, further comprising:

a locating mechanism that is configured to locate an updated card in the old generation by inspecting the card table for a marked entry;

an examining mechanism that is configured to examine pointers in the updated card; and

an establishing mechanism that is configured to establish that objects pointed to by pointers in the updated card are still active.

25. The apparatus of claim 21, wherein dividing the heap into segments involves dividing the heap in segments along power-of-two address boundaries.

26. The apparatus of claim 25,

wherein if a large object that is larger than the size of the segment requires storage, a large segment is allocated with sufficient memory to hold the object;

and

wherein the large segment stores only the large object.

27. The apparatus of claim 26, wherein the large segment is not moved during a heap compaction.

28. The apparatus of claim 21, further comprising:

a hot list maintaining mechanism that is configured to maintain a hot list of segments that hold objects newly promoted from a young generation to the old generation; and

an adding mechanism that is configured to add an updated segment to the hot list when an object is promoted from the young generation to the old generation.

29. The apparatus of claim 21, further comprising a list maintaining mechanism that is configured to maintain a list of segments, wherein the list of segments is maintained in low-to-high address order.

30. The apparatus of claim 21, further comprising:

a selecting mechanism that is configured to select an object that can be promoted; and

an iterating mechanism that is configured to iterate through segments to find a hole in the old generation that can hold the selected object.