Method and apparatus for performing generational garbage collection using barrier bits

• US 6,510,440 B1
• Filed: 01/10/2000
• Issued: 01/21/2003
• 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,189
• Time in Patent Office: 1,107 Days
• Field of Search: 707/200, 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

A method and apparatus are disclosed for efficiently creating and maintaining a remembered set in a generational garbage collection scheme using a write buffer and a barrier bit associated with each object. A barrier bit associated with each object differentiates generations in a generational garbage collection scheme. When an object is first created, the barrier bit of the object is set to zero. The barrier bit is set when the object becomes old, for example, after surviving a first garbage collection. The barrier bit is used to determine whether to make an entry into a write buffer when a reference to another object is stored into an object. An entry is made in the write buffer only if the barrier bit of the object that is written into is set. At the end of each garbage collection, entries in the write buffer are added to the remembered set for the next garbage collection if the objects satisfy the criterion for membership, i.e., they are live and may contain pointers to objects in a younger generation. Thus, the remembered set consists of objects that were in the write buffer at the time of a garbage collection, that must be remembered for the next garbage collection. The write buffer is kept small by eliminating duplicate entries. The present invention turns off the barrier bit after the first store during each reclamation period (which causes the object to be identified in the write buffer). The barrier bit is turned on again by the garbage collector after the write buffer has been processed.

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 and a second set of objects distinct from said first set of objects, wherein the computer system further includes a remembered 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:

storing the remembered set from the last reclamation operation;

storing a table of entries between each reclamation operation, 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;

selecting from the table at least one entry corresponding to an object, O; and

updating the remembered set to identify the object, O, corresponding to the selected at least one entry, and storing the updated remembered set for the next reclamation operation.

2. The method of claim 1, wherein at least one entry of the table uniquely identifies a given object that includes an object reference to at least one object in the second set of objects.

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

4. The method of claim 3, 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.

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

6. The method of claim 1, further comprising the step of setting a barrier bit associated with a given object when said object is promoted to said first set.

7. The method of claim 6, 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.

8. A method for managing a remembered set in a generational garbage collection system that stores a plurality of objects that arc 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 comprising the steps of:

setting a barrier bit associated with a given object when said object is promoted to said first set; and

storing said given object in a table of entries if said barrier bit is set and an object reference is stored in said given object, wherein said table of entries is a data structure distinct from said remembered set.

9. The method of claim 8, wherein at least one entry of the table uniquely identifies a given object that includes an object reference to at least one object in the second set of objects.

10. The method of claim 8, further comprising the step of updating a remembered set to identify an object, O, that includes an object reference to at least one object in the second set and storing the updated remembered set for the next reclamation operation.

11. The method of claim 8, further comprising the step of updating a remembered set to identify all objects in said table and storing the updated remembered set for the next reclamation operation.

12. The method of claim 8, 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. The method of claim 8, wherein said object is promoted to said first set after said object survives a first reclamation operation.

14. 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 comprising the steps of:

storing said remembered set from the last reclamation operation;

storing a given object in a table of entries between each reclamation operation if a barrier bit associated with said object indicates that said given object is in said first set and an object reference is stored in said given object;

identifying objects to be processed for said reclamation operation using said table; and

updating the remembered set for the next reclamation operation with entries from said table.

15. The method of claim 14, wherein at least one entry of the table uniquely identifies a given object that includes an object reference to at least one object in the second set of objects.

16. The method of claim 14, further comprising the step of updating the remembered set to identify an object, O, that includes an object reference to at least one object in the second set and storing the updated remembered set for the next reclamation operation.

17. The method of claim 14, further comprising the step of updating the remembered set to identify all objects in said table and storing the updated remembered set for the next reclamation operation.

18. The method of claim 14, 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.

19. 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 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;

store the remembered set from the last reclamation operation;

store a table of entries between each reclamation operation, 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;

select from the table at least one entry corresponding to an object, O; and

update the remembered set to identify the object, O, corresponding to the selected at least one entry, and storing the updated remembered set for the next reclamation operation.

20. The generational garbage collection manager of claim 19, wherein at least one entry of the table uniquely identifies a given object that includes an object reference to at least one object in the second set of objects.

21. The generational garbage collection manager of claim 19, wherein said remembered set identifies objects in the first set that contain an object reference to objects in the second set.

22. The generational garbage collection manager of claim 19, wherein said processor is configured to create an entry in said remembered set only for objects in the first set that contain an object reference to objects in the second set.

23. The generational garbage collection manager of claim 19, wherein said processor is configured to create an entry in said remembered set for all objects in the first set.

24. The generational garbage collection manager of claim 19, wherein said processor is configured to set a barrier bit associated with a given object when said object is promoted to said first set.

25. The generational garbage collection manager of claim 24, 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.

26. 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 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;

set a barrier bit associated with a given object when said object is promoted to said first set; and

store said given object in a table of entries if said barrier bit is set and an object reference is stored in said given object, wherein said table of entries is a data structure distinct from said remembered set.

27. The generational garbage collection manager of claim 26, wherein at least one entry of the table uniquely identifies a given object that includes an object reference to at least one object in the second set of objects.

28. The generational garbage collection manager of claim 26, wherein said processor is further configured to update the remembered set to only identify an object, O, that includes an object reference to at least one object in the second set and storing the updated remembered set for the next reclamation operation.

29. The generational garbage collection manager of claim 26, wherein said processor is further configured to update the remembered set to identify all objects in said table and storing the updated remembered set for the next reclamation operation.

30. The generational garbage collection manager of claim 26, 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.

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 first set of objects and a second set of objects distinct from said first set of objects, 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;

store a given object in a table of entries between each reclamation operation if a barrier bit associated with said object indicates that said given object is in said first set and an object reference is stored in said given object;

identify objects to be processed for said reclamation operation using said table; and

update the remembered set for the next reclamation operation with entries from said table.

32. The generational garbage collection manager of claim 31, wherein at least one entry of the table uniquely identifies a given object that includes an object reference to at least one object in the second set of objects.

33. The generational garbage collection manager of claim 31, wherein said processor is further configured to update the remembered set to identify an object, O, that includes an object reference to at least one object in the second set and storing the updated remembered set for the next reclamation operation.

34. The generational garbage collection manager of claim 31, wherein said processor is further configured to update the remembered set to identify all objects in said table and storing the updated remembered set for the next reclamation operation.

35. The generational garbage collection manager of claim 31, 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.

36. 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 method steps comprising:

storing the remembered set from the last reclamation operation;

storing a table of entries between each reclamation operation, 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;

selecting from the table at least one entry corresponding to an object, O; and

updating the remembered set to identify the object, O, corresponding to the selected at least one entry, and storing the updated remembered set for the next reclamation operation.

37. 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 method steps comprising:

setting a barrier bit associated with a given object when said object is promoted to said first set; and

storing said given object in a table of entries if said barrier bit is set and an object reference is stored in said given object, wherein said table of entries is a data structure distinct from said remembered set.

38. 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 gargage 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 seet of objects distinct from said first set of objects, said method steps comprising:

setting a barrier bit associated with a given object when said object is promoted to said first set; and

storing said given object in a table of entries if said barrrier bit is set and an object reference is stored in said given object, wherein said table of entries is a data structure distinct from said remembered set.