Method and apparatus for performing generational garbage collection using middle-aged objects

• US 6,470,361 B1
• Filed: 01/10/2000
• Issued: 10/22/2002
• 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): Vu, Kim
• Assistant Examiner(s): PHAM, HUNG Q
• Application Number:
  US09/480,186
• Time in Patent Office: 1,016 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. The present invention detects when an old object has a pointer to a young object, and needs to be added to the remembered set. A write buffer and a temporary buffer are used to create and maintain the remembered set. Entries in the write and temporary buffers are used as part of the root set for creating the remembered set for the next garbage collection. A barrier bit associated with each object differentiates generations in the generational garbage collection scheme and is used to determine whether to make an entry into a write buffer when a reference to another object is stored into an object. Objects that have survived one or more collections, but not the minimum number, N, of collections to be considered an old object are referred to as “middle-aged” objects. During a minor garbage collection, the write buffer is scanned. Objects identified in the write buffer are transferred to the remembered set for the next cycle if the object is (i) an old object pointing to a younger object, or (ii) a middle-aged object that is determined to be live. Middle-aged objects identified in the write buffer that are not yet known to be live are transferred to the temporary buffer. At the end of the minor collection, the temporary buffer is processed and objects that are then known to be live are transferred into the remembered set.

Claims

1. In a computer system comprising a heap that stores a plurality of objects that are logically partitioned into at least a set of old objects that have each survived at least a predetermined number N of reclamation operations, a set of middle-aged objects that have each survived at least a predetermined number M of reclamation operations, wherein M is less than N, and a third set of objects distinct from said old and middle-aged sets of objects, and wherein the computer system performs a plurality of reclamation operations that use a remembered set to reclaim space in the heap, a method for maintaining the remembered set comprising the steps of:

providing said remembered set from a previous reclamation operation;

identifying said old or middle-aged objects that include an object reference that has been modified since the last reclamation operation; and

creating an entry in a remembered set for a next reclamation period for a middle-aged object that is live and (i) identified in said remembered set from a previous reclamation operation or (ii) identified as having an object reference that has been modified since the last reclamation operation.

2. The method of claim 1, wherein said remembered set entry has an associated counter, C, indicating said reclamation operation when said entry was created.

3. The method of claim 2, further comprising the step of discarding said entry when said reclamation operation has a value of C plus N.

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

5. 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.

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

7. The method of claim 1, wherein said remembered sets identify (i) a given object in said set of old objects that contains an object reference to an object in the set of middle-aged objects or the third set of objects;

or (ii) a given object in said set of middle-aged objects that contains an object reference to an object in the third set of objects.

8. The method of claim 1, wherein said creating step further comprises the step of creating an entry in said remembered set for said next reclamation period only for objects in said set of middle-aged objects that contain an object reference to an object in the third set of objects.

9. The method of claim 1, wherein said creating step further comprises the step of creating an entry in said remembered set for all objects in the set middle-aged objects that are (i) identified in said remembered set from a previous reclamation operation, or (ii) identified as having an object reference that has been modified since the last reclamation operation.

10. In a computer system comprising a heap that stores a plurality of objects that are logically partitioned into at least a set of old objects that have each survived at least a predetermined number N of reclamation operations, a set of middle-aged objects that have each survived at least a predetermined number M of reclamation operations, wherein M is less than N, and a third set of objects distinct from said old and middle-aged sets of objects, and wherein the computer system performs a plurality of reclamation operations that use a remembered set to reclaim space in the heap, a method for maintaining the remembered set comprising the steps of:

providing said remembered set from a previous reclamation operation;

identifying said old or middle-aged objects that include an object reference that has been modified since the last reclamation operation; and

creating an entry in a remembered set for a next reclamation period for an old object that is (i) identified in said remembered set from a previous reclamation operation, or (ii) identified as having an object reference that has been modified since the last reclamation operation.

11. The method of claim 10, wherein said remembered set entry has an associated counter, C, indicating said reclamation operation when said entry was created.

12. The method of claim 11, further comprising the step of discarding said entry when said reclamation operation has a value of C plus N.

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

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

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

16. The method of claim 10, wherein said remembered sets identify (i) a given object in said set of old objects that contains an object reference to an object in the set of middle-aged objects or the third set of objects;

or (ii) a given object in said set of middle-aged objects that contains an object reference to an object in the third set of objects.

17. The method of claim 10, wherein said creating step further comprises the step of creating an entry in said remembered set for said next reclamation period only for objects in said set of old objects that contain an object reference to an object in the set of middle-aged objects or the third set of objects.

18. The method of claim 10, wherein said creating step further comprises the step of creating an entry in said remembered set for all objects in the set of old objects that are (i) identified in said remembered set from a previous reclamation operation, or (ii) identified as having an object reference that has been modified since the last reclamation operation.

29. The method of claim 10, wherein said creating step further comprises the step of creating an entry in said table of entries for all objects in the set of middle-aged objects that are not known to be live and are (i) identified in said remembered set from a previous reclamation operation, or (ii) identified as having an object reference that has been modified\ since the last reclamation operation.

19. In a computer system comprising a heap that stores a plurality of objects that are logically partitioned into at least a set of old objects that have each survived at least a predetermined number N of reclamation operations, a set of middle-aged objects that have each survived at least a predetermined number M of reclamation operations, wherein M is less than N, and a third set of objects distinct from said old and middle-aged sets of objects, and wherein the computer system performs a plurality of reclamation operations that use a remembered set to reclaim space in the heap, a method for maintaining the remembered set comprising the steps of:

providing said remembered set from a previous reclamation operation;

identifying said old or middle-aged objects that include an object reference that has been modified since the last reclamation operation; and

creating an entry in a table of entries during one of said reclamation operations for a middle-aged object that is not known to be live and is (i) identified in said remembered set from a previous reclamation operation, or (ii) identified as having an object reference that has been modified since the last reclamation operation.

20. The method of claim 19, further comprising the steps of processing entries in said table following said reclamation operation and creating an entry in said remembered set for a next reclamation operation for a middle-aged object identified in said table that is live.

21. The method of claim 19, further comprising the steps of processing entries in said table following said reclamation operation and discarding an entry in said table for a middle-aged object identified in said table that is not known to be live.

22. The method of claim 19, wherein said remembered set entry has an associated counter, C, indicating said reclamation operation when said entry was created.

23. The method of claim 21, further comprising the step of discarding said entry when said reclamation operation has a value of C plus N.

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

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

26. The method of claim 19, wherein said identifying step employs a card marking scheme.

27. The method of claim 19, wherein said remembered set identifies (i) a given object in said set of old objects that contains an object reference to an object in the set of middle-aged objects or the third set of objects;

or (ii) a given object in said set of middle-aged objects that contains an object reference to an object in the third set of objects.

28. The method of claim 19, wherein said creating step further comprises the step of creating an entry in said table only for objects in said set of middle-aged objects that are not known to be live and contain an object reference to an object in the third set of objects.

30. 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 set of old objects that have each survived at least a predetermined number N of reclamation operations, a set of middle-aged objects that have each survived at least a predetermined number M of reclamation operations, wherein M is less than N, and a third set of objects distinct from said old and middle-aged sets of objects, and wherein the computer system performs a plurality of reclamation operations that use a remembered 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;

provide said remembered set from a previous reclamation operation;

identify said old or middle-aged objects that include an object reference that has been modified since the last reclamation operation; and

create an entry in a remembered set for a next reclamation period for a middle-aged object that is live and (i) identified in said remembered set from a previous reclamation operation or (ii) identified as having an object reference that has been modified since the last reclamation operation.

31. 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 set of old objects that have each survived at least a predetermined number N of reclamation operations, a set of middle-aged objects that have each survived at least a predetermined number M of reclamation operations, wherein M is less than N, and a third set of objects distinct from said old and middle-aged sets of objects, and wherein the computer system performs a plurality of reclamation operations that use a remembered 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;

provide said remembered set from a previous reclamation operation;

identify said old or middle-aged objects that include an object reference that has been modified since the last reclamation operation; and

create an entry in a remembered set for a next reclamation period for an old object that is (i) identified in said remembered set from a previous reclamation operation, or (ii) identified as having an object reference that has been modified since the last reclamation operation.

32. 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 set of old objects that have each survived at least a predetermined number N of reclamation operations, a set of middle-aged objects that have each survived at least a predetermined number M of reclamation operations, wherein M is less than N, and a third set of objects distinct from said old and middle-aged sets of objects, and wherein the computer system performs a plurality of reclamation operations that use a remembered 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;

provide said remembered set from a previous reclamation operation;

identify said old or middle-aged objects that include an object reference that has been modified since the last reclamation operation; and

create an entry in a table of entries during one of said reclamation operations for a middle-aged object that is not known to be live and is (i) identified in said remembered set from a previous reclamation operation, or (ii) identified as having an object reference that has been modified since the last reclamation operation.

33. 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 set of old objects that have each survived at least a predetermined number N of reclamation operations, a set of middle-aged objects that have each survived at least a predetermined number M of reclamation operations, wherein M is less than N, and a third set of objects distinct from said old and middle-aged sets of objects, and wherein the computer system performs a plurality of reclamation operations that use a remembered set to reclaim space in the heap, said method steps comprising:

providing said remembered set from a previous reclamation operation;

identifying said old or middle-aged objects that include an object reference that has been modified since the last reclamation operation; and

creating an entry in a remembered set for a next reclamation period for a middle-aged object that is live and (i) identified in said remembered set from a previous reclamation operation or (ii) identified as having an object reference that has been modified since the last reclamation operation.

34. 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 set of old objects that have each survived at least a predetermined number N of reclamation operations, a set of middle-aged objects that have each survived at least a predetermined number M of reclamation operations, wherein M is less than N, and a third set of objects distinct from said old and middle-aged sets of objects, and wherein the computer system performs a plurality of reclamation operations that use a remembered set to reclaim space in the heap, said method steps comprising:

providing said remembered set from a previous reclamation operation;

identifying said old or middle-aged objects that include an object reference that has been modified since the last reclamation operation; and

creating an entry in a remembered set for a next reclamation period for an old object that is (i) identified in said remembered set from a previous reclamation operation, or (ii) identified as having an object reference that has been modified since the last reclamation operation.

35. 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 set of old objects that have each survived at least a predetermined number N of reclamation operations, a set of middle-aged objects that have each survived at least a predetermined number M of reclamation operations, wherein M is less than N, and a third set of objects distinct from said old and middle-aged sets of objects, and wherein the computer system performs a plurality of reclamation operations that use a remembered set to reclaim space in the heap, said method steps comprising:

providing said remembered set from a previous reclamation operation;

identifying said old or middle-aged objects that include an object reference that has been modified since the last reclamation operation; and

creating an entry in a table of entries during one of said reclamation operations for a middle-aged object that is not known to be live and is (i) identified in said remembered set from a previous reclamation operation, or (ii) identified as having an object reference that has been modified since the last reclamation operation.