Train-algorithm-based garbage collector employing fixed-size remembered sets

• US 6,185,581 B1
• Filed: 08/19/1999
• Issued: 02/06/2001
• Est. Priority Date: 08/19/1999
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Garthwaite, Alexander T.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US09/377,555
• Time in Patent Office: 537 Days
• Field of Search: 707/206, 707/205, 707/100, 707/101, 707/102, 707/103, 707/104, 707/202
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A garbage collector collects a generation of a collected heap in accordance with the train algorithm. It employs remembered sets associated with respective car sections to keep track of references into the associated car sections. Each remembered set contains entries that identify respective regions in the generation that contain references into the associated car section. A limit is imposed on the number of entries in the remembered sets used to keep track of references to objects in certain car sections that contain only a single object each. An object in any such car section whose remembered set has more than a threshold number of entries is treated as reachable and relinked into a younger train without having the memory regions that those entries identify searched for valid references.

Claims

1. A method of garbage collection that includes treating a generation of a collected heap as divided into car sections that belong to trains in such a manner as to impose a collection sequence, maintaining remembered sets, associated with respective car sections, of remembered-set entries that identify regions containing inter-car references to objects contained in car sections with which those remembered sets are respectively associated, performing a remembered-set-update process by searching through the generation for references into the car sections with which the remembered sets are associated and adding to the remembered sets remembered-set entries that identify regions thereby found in car sections less forward in the collection sequence than the car sections with which the remembered sets are associated, and collecting the generation in collection cycles, in each of which a collection set of at least one car section is collected in accordance with the train algorithm and the remembered sets associated with each car section of the collection set are processed to identify objects that will survive the collection cycle, and wherein:

A) when the number of remembered-set entries in at least one, given remembered set associated with one, given car section that contains only a single, given object has reached a predetermined maximum, the remembered-set-update process includes increasing the number of remembered-set entries in the given remembered set no further; and

B) when the given car section'"'"'s turn for collection arrives and the regions identified by the given remembered set contain less than all the references to the given object found during the update process in car sections less forward than the given car section, the given car section is linked into a train independently of which regions identified by the given remembered set still contain references to the given object.

2. A method as defined in claim 1 wherein:

A) the remembered-set-update process includes maintaining a least-forward-train value for the given remembered set that identifies the least-forward train to which a car section belongs that contains a reference to the given object; and

B) the given car section is linked into the train identified by the least-forward-train value.

3. A garbage collector that treats a generation of a collected heap as divided into car sections, so links the car sections into trains as to impose a collection sequence on the car sections, maintains remembered sets, associated with respective car sections, of remembered-set entries that identify regions containing inter-car references to objects contained in the car sections with which those remembered sets are respectively associated, performs a remembered-set-update process by searching through the generation for references into the car sections with which the remembered sets are associated and adding to the remembered sets remembered-set entries that identify regions thereby found in car sections less forward in the collection sequence than the car sections with which the remembered sets are associated, and collects the generation in accordance with the collection sequence in collection cycles, in each of which the garbage collector collects a collection set of at least one car section in accordance with the train algorithm and processes the remembered sets associated with each car section of the collection set to identify objects that will survive the collection cycle, and wherein:

A) the garbage collector limits to a predetermined maximum the number of remembered-set entries in at least a given remembered set associated with a respective, given car section that contains a given object set of at least one object in such a manner as to permit the given remembered set to omit an entry that identifies a region, located in a car section farther forward than the given car section, that contains a reference to an object in the given object set; and

B) when the collection sequence reaches the given car section, the garbage collector'"'"'s processing of the given remembered set comprises;

i) making a remembered-set-omission determination of whether the remembered set may omit an entry that identifies a region, located in a car section farther forward than the given car section, that contains a reference to an object in the given object set; and

ii) if so, linking the given car section into a train independently of which regions identified by the given remembered set contain references to the given set.

4. A garbage collector as defined in claim 3 wherein the garbage collector permits only remembered sets associated with car sections that contain at most one object to omit entries that identify regions, located in car sections farther forward than the car sections with which those remembered sets are associated, that contain references to objects in the car sections with which those remembered sets are associated.

5. A garbage collector as defined in claim 3 wherein, when the remembered-set-omission determination is that the given remembered set does not omit an entry that identifies a region, located in a car section farther forward than the given car section, that contains a reference to an object in the given object set, the garbage collector'"'"'s processing of the given remembered set includes linking the given car section into the least-forward train into which is linked a car section that contains a region identified by an entry in the given remembered set.

6. A garbage collector as defined in claim 5 wherein the garbage collector permits only remembered sets associated with car sections that contain at most one object to omit entries that identify regions, located in car sections farther forward than the car sections with which those remembered sets are associated, that contain references to objects in the car sections with which those remembered sets are associated.

7. A garbage collector as defined in claim 3 wherein:

A) the remembered-set-update process includes maintaining for the given remembered set a least-forward-train value that identifies the least-forward train to which a car section belongs that contains a reference to an object in the object set; and

B) when the given car section is linked into a train independently of which regions identified by the given remembered set contain references to objects in the given object set, the given car section is linked into the train identified by the least-forward-train value.

8. A garbage collector as defined in claim 7 wherein the garbage collector permits only remembered sets associated with car sections that contain at most one object to omit entries that identify regions, located in car sections farther forward than the car sections with which those remembered sets are associated, that contain references to objects in the car sections with which those remembered sets are associated.

9. A garbage collector as defined in claim 7 wherein, when the remembered-set-omission determination is that the given remembered set does not omit an entry that identifies a region, located in a car section farther forward than the given car section, that contains a reference to an object in the given object set, the garbage collector'"'"'s processing of the given remembered set includes linking the given car section into the least-forward train into which is linked a car section that contains a region identified by an entry in the given remembered set.

10. A garbage collector as defined in claim 9 wherein the garbage collector permits only remembered sets associated with car sections that contain at most one object to omit entries that identify regions, located in car sections farther forward than the car sections with which those remembered sets are associated, that contain references to objects in the car sections with which those remembered sets are associated.

11. A garbage collector as defined in claim 3 wherein the garbage collector further so performs the remembered-set-update process for a second remembered set associated with a second car section, which contains a second object set of at least one object, as to require that the second remembered set contain an entry that identifies every region, located in a car section farther forward than the second car section, that contains a reference to an object in the second object set.

12. A garbage collector as defined in claim 11 wherein the garbage collector permits only remembered sets associated with car sections that contain at most one object to omit entries that identify regions, located in car sections farther forward than the car sections with which those remembered sets are associated, that contain references to objects in the car sections with which those remembered sets are associated.

13. A garbage collector as defined in claim 11 wherein the garbage collector imposes no limit on the number of remembered-set entries in the second remembered set.

14. A garbage collector as defined in claim 13 wherein the garbage collector permits only remembered sets associated with car sections that contain at most one object to omit entries that identify regions, located in car sections farther forward than the car sections with which those remembered sets are associated, that contain references to objects in the car sections with which those remembered sets are associated.