Combining external and intragenerational reference-processing in a garbage collector based on the train algorithm

• US 7,031,990 B2
• Filed: 12/06/2002
• Issued: 04/18/2006
• Est. Priority Date: 12/06/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Garthwaite, Alexander T.
• Primary Examiner(s): MIZRAHI, DIANE D
• Application Number:
  US10/313,254
• Publication Number:
  US 20040111447A1
• Time in Patent Office: 1,229 Days
• Field of Search: 707/206, 707 1- 10, 707100-1041, 707200-205, 711/159, 717/166
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A garbage collector collects at least a generation of a dynamically allocated heap in increments. In each increment, it identifies references located outside a collection set that refer to objects that belong to the collection set, and it evacuates the objects thus referred to before it reclaims the memory space that the collection set occupies. In some collection increments, references to collection-set objects are located both inside and outside the generation. The collector locates all such references, both those inside the generation and those outside it, before it evacuates any objects in response to any of them. By doing so, it is able to reduce the cost of locating references and evacuating objects.

Claims

1. For operating a computer system, which includes memory, as a garbage collector that treats at least a generation of a garbage-collected heap in the memory as divided into sections and collects the generation in collection increments with which the garbage collector associates respective collection sets in the generation, a method comprising, in at least some of the collection increments:

A) finding references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation, listing the external references thereby found that refer to objects in the collection set, and marking sections of the generation that contain objects to which the external references thereby found refer;

B) identifying and including in the collection set at least one section, denominated a dead section, not reachable through a reference chain that includes an external reference thereby found;

C) finding references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set;

D) evacuating from the collection set objects reachable from outside the collection set without evacuating therefrom any object located in a dead section even if that dead section contains an object referred to by an internal reference; and

E) reclaiming the collection set.

2. A method as defined in claim 1 wherein:

A) the method further includes maintaining for each of at least some of the sections a respective remembered set, associated therewith, of locations in the generation where references have been found to an objects in the associated section; and

B) in at least some of the collection increments;

i) the remembered set associated with a dead section included in the collection set lists at least one location in that dead section at which a reference to an object in the collection set has been found; and

ii) the step of finding internal references to objects in the collection set includes, without scanning locations listed in any remembered set associated with a dead section, scanning the locations listed in every other remembered set associated with a section that contains an object in the collection set.

3. A computer system comprising:

A) processor circuitry operable to execute processor instructions; and

B) memory circuitry, to which the processor circuitry is responsive, that contains processor instructions readable by the processor circuitry to configure the computer system to operate as a garbage collector that;

i) treats at least a generation of a garbage-collected heap in the memory as divided into sections; and

ii) collects the generation in collection increments with which the garbage collector associates respective collection sets in the generation and in at least some of which the garbage collector;

a) finds references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation

b) lists the external references thereby found that refer to objects in the collection set;

c) marks sections of the generation that contain objects to which the external references thereby found refer;

d) identifies and includes in the collection set at least one section, denominated a dead section, not reachable through a reference chain that includes an external reference thereby found;

e) finds references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set;

f) evacuates from the collection set objects reachable from outside the collection set without evacuating therefrom any object located in a dead section even if that dead section contains an object referred to by an internal reference; and

iii) reclaims the collection set.

4. A computer system as defined in claim 3 wherein:

A) the garbage collector maintains for each of at least some of the sections a respective remembered set, associated therewith, of locations in the generation where references have been found to an objects in the associated section; and

B) in at least some of the collection increments;

i) the remembered set associated with a dead section included in the collection set lists at least one location in that dead section at which a reference to an object in the collection set has been found; and

ii) when the garbage collector finds the internal references to objects in the collection set in an operation, the garbage collector does so by, without scanning locations listed in any remembered set associated with a dead section, scanning the locations listed in every other remembered set associated with a section that contains an object in the collection set.

5. A storage medium containing instructions readable by a computer system that includes memory to configure the computer system to operate as a garbage collector that:

A) treats at least a generation of a garbage-collected heap in the memory as divided into sections; and

B) collects the generation in collection increments with which the garbage collector associates respective collection sets in the generation and in at least some of which the garbage collector;

i) finds references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation

ii) lists the external references thereby found that refer to objects in the collection set;

iii) marks sections of the generation that contain objects to which the external references thereby found refer;

iv) identifies and includes in the collection set at least one section, denominated a dead section, not reachable through a reference chain that includes an external reference thereby found;

v) finds references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set;

vi) evacuates from the collection set objects reachable from outside the collection set without evacuating therefrom any object located in a dead section even if that dead section contains an object referred to by an internal reference; and

vii) reclaims the collection set.

6. A storage medium as defined in claim 5 wherein:

A) the garbage collector maintains for each of at least some of the sections a respective remembered set, associated therewith, of locations in the generation where references have been found to an objects in the associated section; and

B) in at least some of the collection increments;

i) the remembered set associated with a dead section included in the collection set lists at least one location in that dead section at which a reference to an object in the collection set has been found; and

ii) when the garbage collector finds the internal references to objects in the collection set in an operation, the garbage collector does so by, without scanning locations listed in any remembered set associated with a dead section, scanning the locations listed in every other remembered set associated with a section that contains an object in the collection set.

7. For collecting at least a generation of a garbage-collected heap in a computer system'"'"'s memory in collection increments with which each of which a garbage collector associates a respective collection set in the generation, the garbage collector comprising:

A) means for treating the generation as divided into sections;

B) means for finding references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation

C) means for listing the external references thereby found that refer to objects in the collection set;

D) means for marking sections of the generation that contain objects to which the external references thereby found refer;

E) means for identifying and including in the collection set at least one section, denominated a dead section, not reachable through a reference chain that includes an external reference thereby found;

F) means for finding references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set;

G) means for evacuating from the collection set objects reachable from outside the collection set without evacuating therefrom any object located in a dead section even if that dead section contains an object referred to by an internal reference; and

H) means for reclaiming the collection set.

8. For operating a computer system, which includes memory, as a garbage collector that treats at least a generation of a garbage-collected heap in the memory as divided into car sections grouped into trains and collects the generation in accordance with the train algorithm in collection increments with which the garbage collector associates respective collection sets in the generation, a method comprising, in each of at least some of the collection increments:

A) finding references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation;

B) finding references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set;

C) evacuating potentially reachable objects from the collection set in operations that include;

i) in response to at least one said external reference that refers to an object in the collection set, evacuating that object to a car section belonging to a train, denominated an external-reference train, that is empty at the beginning of that collection increment; and

ii) in response to at least one internal reference that refers to an object in the collection set also referred to by at least one external reference, evacuating that object to a car section in the train to which the car containing that internal reference belongs; and

D) reclaiming the collection set.

9. A computer system comprising:

A) processor circuitry operable to execute processor instructions; and

B) memory circuitry, to which the processor circuitry is responsive, that contains processor instructions readable by the processor circuitry to configure the computer system to operate as a garbage collector that;

i) treats at least a generation of a garbage-collected heap in the memory as divided into car sections grouped into trains; and

ii) collects the generation in accordance with the train algorithm in collection increments with which the garbage collector associates respective collection sets in the generation and in at least some of which the garbage collector;

a) finds references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation;

b) finds references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set;

c) evacuates potentially reachable objects from the collection set in operations that include;

(1) in response to at least one said external reference that refers to an object in the collection set, evacuating that object to a car section belonging to a train, denominated an external-reference train, that is empty at the beginning of that collection increment; and

(2) in response to at least one internal reference that refers to an object in the collection set also referred to by at least one external reference, evacuating that object to a car section in the train to which the car containing that internal reference belongs; and

d) reclaims the collection set.

10. A storage medium containing instructions readable by a computer system that includes memory to configure the computer system to operate as a garbage collector that:

A) treats at least a generation of a garbage-collected heap in the memory as divided into car sections grouped into trains; and

B) collects the generation in accordance with the train algorithm in collection increments with which the garbage collector associates respective collection sets in the generation and in at least some of which the garbage collector;

i) finds references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation;

ii) finds references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set;

iii) evacuates potentially reachable objects from the collection set in operations that include;

a) in response to at least one said external reference that refers to an object in the collection set, evacuating that object to a car section belonging to a train, denominated an external-reference train, that is empty at the beginning of that collection increment; and

b) in response to at least one internal reference that refers to an object in the collection set also referred to by at least one external reference, evacuating that object to a car section in the train to which the car containing that internal reference belongs; and

iv) reclaims the collection set.

11. For collecting at least a generation of a garbage collected heap in a computer system'"'"'s memory in accordance with the train algorithm in collection increments with which each of which a garbage collector associates a respective collection set in the generation, the garbage collector comprising:

A) means for treating the generation as divided into car sections grouped into trains; and

B) means for finds references, denominated external references, that are located outside the generation but refer to objects that are located inside the generation;

C) means for finding references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are located inside the collection set;

D) means for evacuating potentially reachable objects from the collection set in operations that include;

i) in response to at least one said external reference that refers to an object in the collection set, evacuating that object to a car section belonging to a train, denominated an external-reference train, that is empty at the beginning of that collection increment; and

ii) in response to at least one internal reference that refers to an object in the collection set also referred to by at least one external reference, evacuating that object to a car section in the train to which the car containing that internal reference belongs; and

E) means for reclaiming the collection set.

12. In the method of operating a computer system, which includes memory, as a garbage collector that collects at least a generation of a garbage-collected heap in the memory in collection increments with which the garbage collector associates respective collection sets in the generation and in at least some of which the garbage collector locates references, denominated external references, that are located outside the generation but refer to objects in the collection set, locates references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are inside the collection set, evacuates from the collection set objects referred to by references thereby found, and reclaims the collection set, the improvement wherein, in at least some collection increments, the garbage collector locates both the internal and the external references before any object is evacuated from the collection set in response to references thereby located.

13. A computer system comprising including memory that:

A) processor circuitry operable to execute processor instructions; and

B) memory circuitry, to which the processor circuitry is responsive, that contains processor instructions readable by the processor circuitry to configure the computer system to operate as a garbage collector that collects at least a generation of a garbage-collected heap in the memory in collection increments with which the garbage collector associates respective collection sets in the generation and in at least some of which the garbage collector;

i) locates references, denominated external references, that are located outside the generation but refer to objects in the collection set;

ii) locates references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are inside the collection set;

iii) evacuates from the collection set objects referred to by references thereby found, each such collection-set object being evacuated only after the garbage collector has located both the external and the external references; and

iv) reclaims the collection set.

14. A storage medium containing instructions readable by a computer system that includes memory to configure the computer system to operate as a garbage collector that collects at least a generation of a garbage-collected heap in the memory in collection increments with which the garbage collector associates respective collection sets in the generation and in at least some of which the garbage collector:

A) locates references, denominated external references, that are located outside the generation but refer to objects in the collection set;

B) locates references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are inside the collection set;

C) evacuates from the collection set objects referred to by references thereby found, each such collection-set object being evacuated only after the garbage collector has located both the external and the external references; and

D) reclaims the collection set.

15. For collecting at least a generation of a garbage-collected heap in a computer system'"'"'s memory in collection increments with each of which a garbage collector associates respective collection set in the generation, the garbage collector comprising:

A) means for locating references, denominated external references, that are located outside the generation but refer to objects in the collection set;

B) means for locating references, denominated internal references, that are located inside the generation but outside the collection set and refer to objects that are inside the collection set;

C) means for evacuating from the collection set objects referred to by references thereby found, each such collection-set object being evacuated only after the garbage collector has located both the external and the external references; and

D) means for reclaiming the collection set.