Scanning of evacuated objects in a generation managed by the train algorithm

• US 7,676,801 B1
• Filed: 08/31/2004
• Issued: 03/09/2010
• Est. Priority Date: 08/31/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Garthwaite, Alexander T.
• Primary Examiner(s): MITCHELL, JASON D
• Application Number:
  US10/930,483
• Time in Patent Office: 2,016 Days
• Field of Search: 717/162
• US Class Current: 717/165
• CPC Class Codes: G06F 12/0276 Generational garbage collection

Abstract

In computer systems including memory which execute programs of instructions, vtables associated with objects contain pointers which invoke operations to be performed by the program which are related to the objects. The operation invoked may include the step of modifying the pointer such that upon a subsequent reference to the vtable a different operation is invoked. In one embodiment, such vtables are utilized in conjunction with garbage collection methodologies such as those that invoke the train algorithm, such that operations such as reference processing, insertion and scanning during garbage collection may be invoked by pointers in vtables associated with cars or objects in the cars, and the vtables may invoke differing versions of the said operations depending on the characteristics and past history of the car or object, and upon an operation being executed the operation may change the pointer so that a different version of the operation is performed upon a subsequent reference to the vtable associated with the car or object.

Claims

1. A method for employing a computer system including memory as a garbage collector that treats a generation of a heap in the memory as divided into cars grouped into trains ordered in a nominal collection order and collects in collection increments respective collection sets of those cars in accordance with the train algorithm, wherein, in at least some of the collection increments:

A) for a car of said cars in a train of said trains, a remembered set and a virtual table (vtable) are associated with said car and a scratch-pad-list is associated with the train, wherein the vtable is separate from the remembered set;

B) said vtable stores a pointer to an operation related to said car to be performed,

wherein said operation to be performed includes the step of modifying the pointer stored in said vtable to reference a different operation related to said car, such that a subsequent reference to said vtable results in the modified pointer invoking the different operation related to said car to be performed by said program;

C) said operation to be performed is an insertion operation;

D) in the case of said car being a normal car, the pointer to said insertion operation invokes an operation in which an entry is inserted into said remembered set associated with said car;

E) in the case of said car being a special car which has a predetermined number of entries in said remembered set associated with said car, the pointer to said insertion operation invokes an operation in which a further entry is not inserted into said remembered set when said further entry relates to an object in a car which car is not younger than all of the cars associated with existing entries in said remembered set; and

F) in the case of said car being a special car which has fewer than said predetermined number of entries in said remembered set associated with the car, the pointer to said insertion operation invokes an operation in which a further entry is inserted into said remembered set, and in the event that said insertion causes the number of entries in the remembered set to reach said predetermined number, said operation modifies said pointer contained in said vtable, such that a subsequent reference to said vtable associated with said car results in the modified pointer invoking the insertion operation according to step C).

2. The method as defined in claim 1, wherein

G) a second operation to be performed is a reference processing operation,

H) in the case of said car comprising a formerly-popular object, the pointer to said reference processing operation invokes an operation in which an object in said car is copied to another car, and

I) in the case of said car being an oversized car or a car which contains a still-popular object, the pointer to said reference processing operation invokes an operation in which an object in said car is relinked.

3. The method as defined in claim 2, wherein

J) in the case of said car being a car which contains a formerly-popular object, and another object containing a reference to said copied object, the pointer to said reference processing operation invokes an operation in which the reference in the other object to said copied object is updated, and

K) in the case of said car being an oversized car or a car which contains a still-popular object, the pointer to said reference processing operation invokes an operation in which references in other objects to said relinked object are not updated.

4. The method as defined in claim 1, wherein in the case of said car being a special car which has a predetermined number of entries in said remembered set associated with said car, the pointer to said insertion operation invokes an operation in which a further entry is inserted into said remembered set when said further entry relates to an object in a car which car is younger than all of the cars associated with existing entries in said remembered set.

5. The method as defined in claim 1, wherein

G) a second operation to be performed is a scanning operation,

H) in the case of said car being a newly-popular car and an object in said car having been evacuated from the collection set, and said evacuated object containing a reference to another object, the pointer to said scanning operation invokes an operation in which the reference in said evacuated object to another object is appropriately recorded when said other object is in an older car than the evacuated object and in which the reference in said evacuated object to another object is appropriately recorded when said other object is in a younger generation;

and

I) in the case of said car being an oversized car or a car which contains a still-popular object, and an object in said car having been evacuated from the collection set, and said evacuated object containing a reference to another object, the pointer to said scanning operation invokes an operation in which the reference in said evacuated object to another object is appropriately recorded when said other object is in an older car than the evacuated object and in which the reference in said evacuated object to another object is not recorded when said other object is in a younger generation.

6. The method as defined in claim 5, wherein, in the operation which the pointer to said scanning operation invokes, a reference in said evacuated object to the object in an older car is appropriately recorded by placing an entry in a remembered set of said object in an older car to which said evacuated object refers.

7. The method as defined in claim 5, wherein, in the operation which the pointer to said scanning operation invokes, a reference in said evacuated object to the object in an older car is appropriately recorded by placing an entry in a remembered set of said object in an older car to which said evacuated object refers except in the event that said remembered set is of fixed size and full and the car which contains said evacuated object is not younger than all of the cars associated with existing entries in said remembered set.

8. The method as defined in claim 5, wherein, in the case of said car being a newly-popular car, the pointer to said scanning operation invokes an operation which modifies said pointer, such that a subsequent reference to said vtable associated with said car results in the modified pointer invoking the scanning operation for a car with a still-popular object.

9. A computer system including memory and configured as a garbage collector that treats a generation of a heap in the memory as divided into cars grouped into trains ordered in a nominal collection order and collects in collection increments respective collection sets of those cars in accordance with the train algorithm, wherein, in at least some of the collection increments:

A) for a car of said cars in a train of said trains, a remembered set and a virtual table (vtable) are associated with said car and a scratch-pad-list is associated with the train, wherein the vtable is separate from the remembered set; and

B) said vtable stores a pointer to an operation related to said car to be performed,

wherein said operation to be performed includes the step of modifying the pointer stored in said vtable to reference a different operation related to said car, such that a subsequent reference to said vtable results in the modified pointer invoking the different operation related to said car to be performed by said program;

C) said operation to be performed is an insertion operation;

D) in the case of said car being a normal car, the pointer to said insertion operation invokes an operation in which an entry is inserted into said remembered set associated with said car;

E) in the case of said car being a special car which has a predetermined number of entries in said remembered set associated with said car, the pointer to said insertion operation invokes an operation in which a further entry is not inserted into said remembered set when said further entry relates to an object in a car which car is not younger than all of the cars associated with existing entries in said remembered set; and

F) in the case of said car being a special car which has fewer than said predetermined number of entries in said remembered set associated with the car, the pointer to said insertion operation invokes an operation in which a further entry is inserted into said remembered set, and in the event that said insertion causes the number of entries in the remembered set to reach said predetermined number, said operation modifies said pointer contained in said vtable, such that a subsequent reference to said vtable associated with said car results in the modified pointer invoking the insertion operation according to step C).

10. The system as defined in claim 9, wherein

G) a second operation to be performed is a reference processing operation;

H) in the case of said car comprising a formerly-popular object, the pointer to said reference processing operation invokes an operation in which an object in said car is copied to another car; and

I) in the case of said car being an oversized car or a car which contains a still-popular object, the pointer to said reference processing operation invokes an operation in which said car is relinked.

11. The system as defined in claim 10, wherein

J) in the case of said car being a car which contains a formerly-popular object, and another object containing a reference to said copied object, the pointer to said reference processing operation invokes an operation in which the reference in the other object to said copied object is updated;

and

K) in the case of said car being an oversized car or a car which contains a still-popular object, the pointer to said reference processing operation invokes an operation in which references in other objects to said relinked object are not updated.

12. The system as defined in claim 9, wherein in the case of said car being a special car which has a predetermined number of entries in said remembered set associated with said car, the pointer to said insertion operation invokes an operation in which a further entry is inserted into said remembered set when said further entry relates to an object in a car which car is younger than all of the cars associated with existing entries in said remembered set.

13. The system as defined in claim 9, wherein

G) a second operation to be performed is a scanning operation;

H) in the case of said car being a newly-popular car and an object in said car having been evacuated from the collection set, and said evacuated object containing a reference to another object, the pointer to said scanning operation invokes an operation in which the reference in said evacuated object to another object is appropriately recorded when said other object is in an older car than the evacuated object and in which the reference in said evacuated object to another object is appropriately recorded when said other object is in a younger generation; and

I) in the case of said car being an oversized car or a car which contains a still-popular object, and an object in said car having been evacuated from the collection set, and said evacuated object containing a reference to another object, the pointer to said scanning operation invokes an operation in which the reference in said evacuated object to another object is appropriately recorded when said other object is in an older car than the evacuated object and in which the reference in said evacuated object to another object is not recorded when said other object is in a younger generation.

14. The system as defined in claim 13, wherein, in the operation which the pointer to said scanning operation invokes, a reference in said evacuated object to the object in an older car is appropriately recorded by placing an entry in a remembered set of said object in an older car to which said evacuated object refers.

15. The system as defined in claim 13, wherein, in the operation which the pointer to said scanning operation invokes, a reference in said evacuated object to the object in an older car is appropriately recorded by placing an entry in a remembered set of said object in an older car to which said evacuated object refers except in the event that said remembered set is of fixed size and full and the car which contains said evacuated object is not younger than all of the cars associated with existing entries in said remembered set.

16. The system as defined in claim 13, wherein, in the case of said car being a newly-popular car, the pointer to said scanning operation invokes an operation which modifies said pointer, such that a subsequent reference to said vtable associated with said car results in the modified pointer invoking the scanning operation for a car with a still-popular object.

17. A storage medium containing instructions readable by a computer system including memory to configure the computer system as a garbage collector that treats a generation of a heap in the memory as divided into cars grouped into trains ordered in a nominal collection order and collects in collection increments respective collection sets of those cars in accordance with the train algorithm, wherein, in at least some of the collection increments:

A) for a car of said cars in a train of said trains, a remembered set and a virtual table (vtable) are associated with said car and a scratch-pad-list is associated with the train, wherein the vtable is separate from the remembered set;

B) said vtable stores a pointer to an operation related to said car to be performed,

wherein said operation to be performed includes the step of modifying the pointer stored in said vtable to reference a different operation related to said car, such that a subsequent reference to said vtable associated with said car results in the modified pointer invoking the different operation related to said car to be performed by said program;

C) said operation to be performed is an insertion operation;

D) in the case of said car being a normal car, the pointer to said insertion operation invokes an operation in which an entry is inserted into said remembered set associated with said car;

E) in the case of said car being a special car which has a predetermined number of entries in said remembered set associated with said car, the pointer to said insertion operation invokes an operation in which a further entry is not inserted into said remembered set when said further entry relates to an object in a car which car is not younger than all of the cars associated with existing entries in said remembered set; and

F) in the case of said car being a special car which has fewer than said predetermined number of entries in said remembered set associated with the car, the pointer to said insertion operation invokes an operation in which a further entry is inserted into said remembered set, and in the event that said insertion causes the number of entries in the remembered set to reach said predetermined number, said operation modifies said pointer contained in said vtable, such that a subsequent reference to said vtable associated with said car results in the modified pointer invoking the insertion operation according to step C).

18. The storage medium as defined in claim 17, wherein

G) a second operation to be performed is a reference processing operation;

H) in the case of said car comprising a car which contains a formerly-popular object, the pointer to said reference processing operation invokes an operation in which an object in said car is copied to another car; and

I) in the case of said car being an oversized car or a car which contains a still-popular object, the pointer to said reference processing operation invokes an operation in which said car is relinked.

19. The storage medium as defined in claim 18, wherein

J) in the case of said car being a car which contains a formerly-popular object, and another object containing a reference to said copied object, the pointer to said reference processing operation invokes an operation in which the reference in the other object to said copied object is updated;

and

K) in the case of said car being an oversized car or a car which contains a still-popular object, the pointer to said reference processing operation invokes an operation in which references in other objects to said relinked object are not updated.

20. The storage medium as defined in claim 17, wherein in the case of said car being a special car which has a predetermined number of entries in said remembered set associated with said car, the pointer to said insertion operation invokes an operation in which a further entry is inserted into said remembered set when said further entry relates to an object in a car which car is younger than all of the cars associated with existing entries in said remembered set.

21. The storage medium as defined in claim 17, wherein

G) a second operation to be performed is a scanning operation;

H) in the case of said car being a newly-popular car and an object in said car having been evacuated from the collection set, and said evacuated object containing a reference to another object, the pointer to said scanning operation invokes an operation in which the reference in said evacuated object to another object is appropriately recorded when said other object is in an older car than the evacuated object and in which the reference in said evacuated object to another object is appropriately recorded when said other object is in a younger generation; and

I) in the case of said car being an oversized car or a car which contains a still-popular object, and an object in said car having been evacuated from the collection set, and said evacuated object containing a reference to another object, the pointer to said scanning operation invokes an operation in which the reference in said evacuated object to another object is appropriately recorded when said other object is in an older car than the evacuated object and in which the reference in said evacuated object to another object is not recorded when said other object is in a younger generation.

22. The storage medium as defined in claim 21, wherein, in the operation which the pointer to said scanning operation invokes, a reference in said evacuated object to the object in an older car is appropriately recorded by placing an entry in a remembered set of said object in an older car to which said evacuated object refers.

23. The storage medium as defined in claim 21, wherein, in the operation which the pointer to said scanning operation invokes, a reference in said evacuated object to the object in an older car is appropriately recorded by placing an entry in a remembered set of said object in an older car to which said evacuated object refers except in the event that said remembered set is of fixed size and full and the car which contains said evacuated object is not younger than all of the cars associated with existing entries in said remembered set.

24. The storage medium as defined in claim 21, wherein, in the case of said car being a newly-popular car, the pointer to said scanning operation invokes an operation which modifies said pointer, such that a subsequent reference to said vtable associated with said car results in the modified pointer invoking the scanning operation for a car with a still-popular object.