Method and apparatus for performing generational garbage collection using remembered set counter

• US 6,226,653 B1
• Filed: 01/10/2000
• Issued: 05/01/2001
• Est. Priority Date: 01/10/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Alpern, Bowen, Smith, Stephen Edwin, Attanasio, Clement Richard
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US09/480,190
• Time in Patent Office: 477 Days
• Field of Search: 707/206, 707/1
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A method and apparatus are provided for the efficient management of remembered sets in a generational garbage collection scheme. In order to manage the remembered set, the present invention provides a first mechanism for detecting when an old object has a pointer to a young object, and needs to be added to the remembered set, and a second mechanism for detecting when an object already in the remembered set no longer contains a pointer to a young object, so that the object can be removed from the remembered set. Entries in the remembered set have an associated counter, C, identifying the garbage collection cycle during which the object was placed in the remembered set. Objects inserted into the remembered set are assumed to point to the youngest possible object. Entries automatically expire from the remembered set when the garbage collection counter reaches C+N, since the objects pointed to by the object in the remembered set must now themselves be old objects. If an old object (one that has survived at least N garbage collections) is identified during a minor garbage collection, the old object is scanned normally, and is placed into the remembered set, with a counter C identifying the garbage collection cycle during which the old object was placed in the remembered set. The counter identifies the age of the youngest possible object pointed to by this object. When the garbage collection count reaches C+N, this entry can be discarded from the remembered set, since the associated object cannot point to any objects that are not old unless another more recent entry in the remembered set or write buffer exists for that object.

Claims

1. In a computer system comprising a heap that stores a plurality of objects that are logically partitioned into at least a first set of objects that have each survived at least a predetermined number N of reclamation operations and a second set of objects distinct from said first set of objects, wherein the computer system further includes a remembered set identifying objects in the first set, and wherein the computer system performs a plurality of reclamation operations that use the remembered set to reclaim space in the heap, a method for maintaining the remembered set comprising the steps of:

identifying objects that include an object reference that has been modified since the last reclamation operation;

updating the remembered set to include an entry for said identified objects, wherein each entry in said remembered set has an associated counter, C, indicating said reclamation operation when said entry was created; and

storing the updated remembered set for the next reclamation operation.

2. The method of claim 1, wherein said identifying step further comprises the step of storing an indication of said modified object in at least one table of entries.

3. The method of claim 1, wherein said identifying step employs a card marking scheme.

4. The method of claim 1, wherein said remembered set identifies objects in the first set that contain an object reference to objects in the second set.

5. The method of claim 4, wherein said updating step further comprises the step of creating an entry in said remembered set only for objects in the first set that contain an object reference to objects in the second set.

6. The method of claim 1, wherein said updating step further comprises the step of creating an entry in said remembered set for all objects in the first set.

7. The method of claim 1, further comprising the step of discarding said remembered set entry when said reclamation operation has a value of C plus N.

8. The method of claim 1, wherein said counter, C, is recorded in said entry.

9. The method of claim 1, wherein said counter, C, is associated with a plurality of said entries created during the same reclamation operation.

10. The method of claim 1, wherein said counter, C, is decremented for each reclamation operation and wherein said corresponding entry is discarded when said counter value is zero.

11. The method of claim 1, further comprising the step of setting a barrier bit associated with a given object when said object survives a first reclamation operation.

12. The method of claim 11, wherein said barrier bit is turned off after a first storage of a given object in said table of entries during a given reclamation period.

13. A method for managing a remembered set in a generational garbage collection system that stores a plurality of objects that are logically partitioned into at least a first set of objects and a second set of objects distinct from said first set of objects, said method employing a plurality of reclamation operations that use a remembered set identifying objects in the first set to reclaim space in the heap, said method comprising the steps of:

identifying objects that include an object reference that has been modified since the last reclamation operation;

creating an entry in said remembered set during one of said reclamation operations for said identified objects;

associating a counter, C, with said remembered set entry indicating said reclamation operation when said entry was created; and

discarding said entry when said counter has a predefined value.

14. The method of claim 13, wherein said identifying step further comprises the step of storing an indication of said modified object in at least one table of entries, wherein each entry identifies a given object that belongs to said first set of objects and includes an object reference that has been modified since the last reclamation operation.

15. The method of claim 13, wherein said identifying step employs a card marking scheme.

16. The method of claim 13, wherein said remembered set identifies objects in the first set that contain an object reference to objects in the second set.

17. The method of claim 16, wherein said updating step further comprises the step of creating an entry in said remembered set only for objects in the first set that contain an object reference to objects in the second set.

18. The method of claim 13, wherein said updating step further comprises the step of creating an entry in said remembered set only for all objects in the first set.

19. The method of claim 13, wherein said counter, C, is recorded in said entry.

20. The method of claim 13, wherein said counter, C, is associated with a plurality of said entries created during the same reclamation operation.

21. The method of claim 13, wherein said counter, C, is decremented for each reclamation operation and wherein said corresponding entry is discarded when said counter value is zero.

22. The method of claim 13, further comprising the step of setting a barrier bit associated with a given object when said object survives a first reclamation operation.

23. The method of claim 22, wherein said barrier bit is turned off after a first storage of a given object in said table of entries during a given reclamation period.

24. A generational garbage collection manager for a remembered set in a system that stores a plurality of objects that are logically partitioned into at least a first set of objects and a second set of objects distinct from said first set of objects, said generational garbage collection manager employing a plurality of reclamation operations that use a remembered set identifying objects in the first set to reclaim space in the heap, said generational garbage collection manager comprising:

a memory that stores computer-readable code; and

a processor operatively coupled to said memory, said processor configured to implement said computer-readable code, said computer-readable code configured to;

identify objects that include an object reference that has been modified since the last reclamation operation;

update the remembered set to include an entry for said identified objects, wherein each entry in said remembered set has an associated counter, C, indicating said reclamation operation when said entry was created; and

store the updated remembered set for the next reclamation operation.

25. A generational garbage collection manager for a remembered set in a system that stores a plurality of objects that are logically partitioned into at least a first set of objects and a second set of objects distinct from said first set of objects, said generational garbage collection manager employing a plurality of reclamation operations that use a remembered set identifying objects in the first set that contain an object reference to objects in the second set to reclaim space in the heap, said generational garbage collection manager comprising:

a memory that stores computer-readable code; and

a processor operatively coupled to said memory, said processor configured to implement said computer-readable code, said computer-readable code configured to;

identify objects that include an object reference that has been modified since the last reclamation operation;

create an entry in said remembered set during one of said reclamation operations for said identified objects;

associate a counter, C, with said remembered set entry indicating said reclamation operation when said entry was created; and

discard said entry when said counter has a predefined value.

26. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for managing a generational garbage collection system for a remembered set in a system that stores a plurality of objects that are logically partitioned into at least a first set of objects and a second set of objects distinct from said first set of objects, said generational garbage collection manager employing a plurality of reclamation operations that use a remembered set identifying objects in the first set that contain an object reference to objects in the second set to reclaim space in the heap, said method steps comprising:

identifying objects that include an object reference that has been modified since the last reclamation operation;

updating the remembered set to include an entry for said identified objects, wherein each entry in said remembered set has an associated counter, C, indicating said reclamation operation when said entry was created; and

storing the updated remembered set for the next reclamation operation.

27. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for managing a generational garbage collection system for a remembered set in a system that stores a plurality of objects that are logically partitioned into at least a first set of objects and a second set of objects distinct from said first set of objects, said generational garbage collection manager employing a plurality of reclamation operations that use a remembered set identifying objects in the first set that contain an object reference to objects in the second set to reclaim space in the heap, said method steps comprising:

identifying objects that include an object reference that has been modified since the last reclamation operation;

creating an entry in said remembered set during one of said reclamation operations for said identified objects;

associating a counter, C, with said remembered set entry indicating said reclamation operation when said entry was created; and

discarding said entry when said counter has a predefined value.