Incremental scanning of enormous objects to improve scheduling and pause-time behavior of garbage collection

• US 20040199556A1
• Filed: 02/27/2003
• Published: 10/07/2004
• Est. Priority Date: 02/27/2003
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Garthwaite, Alexander T.
• Granted Patent: US 7,062,519 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A technique for incrementally collecting enormous objects including scanning portions of the enormous objects on different collection steps. The scanning can be accomplished with a number of collection sets where the enormous object is re-linked and older cars remembered sets are updated on subsequent collection steps. Unscanned portions of the enormous object are scanned on subsequent collection cycles until the enormous object has been fully scanned. This incremental collection can be performed concurrently with collections of other generations and applications.

Claims

1. In a garbage collector based on the Train algorithm, a process for collecting enormous objects and for reference insertions into remembered sets of other cars, the process comprising the steps of:

including at least one enormous object as part of a collection set,

evacuating the enormous object by re-linking,

finding an unscanned portion of the enormous object,

scanning a preset amount of the unscanned portion for references to objects in other cars, wherein

if a reference to an object in another car is found, updating the remembered set of that other car, and

scanning the enormous object for references into the collection set, if the collection set is not empty.

2. The process of claim 1 further comprising the step of saving the location of the unscanned portion of the enormous object.

3. The process of claim 1 further comprising the step of returning to the collection process if no unscanned portion of the enormous object is found.

4. The process of claim 1 further comprising the steps of:

if the collection set includes at least one other object,

scanning the enormous object for references to the at least one other object, and, if any such references are found,

re-locating the at least one other object if it has not already been relocated, and

updating the references in the re-linked enormous object to reflect the new location of the at least one other object.

5. The process of claim 2 further comprising the steps of:

finding references in the relocated at least one other object to other objects in older cars and updating the remembered sets of the older cars with respect to the relocated at least one other object.

6. The process of claim 2 further comprising the steps of;

finding the at least one other object in another car in the collection set,

scanning the enormous object for references to the at least one other object, and, if any such references are found,

re-locating the at least one object if it has not already been relocated, and

updating the references in the re-linked enormous object to reflect the new location of the at least one other object.

7. The process of claim 1, wherein at least one other car with at least one other object is in the collection set, the process further comprising the steps of:

re-locating the at least one other object,

scanning the enormous object for references to the at least one other object, if such a reference is found,

updating the reference to the relocated object, and

scanning the relocated at least one other object for references to other objects in other cars and updating the remembered sets of the other cars with respect to the relocated at least one other object.

8. The process of claim 1 further comprising the steps of:

maintaining for each train a list of partially scanned enormous objects wherein in each collection increment some unscanned portion of some of these partially scanned objects is scanned for references to objects in other cars, wherein if a reference to an object in another car is found, updating the remembered set of that other car, and

scanning the remaining unscanned portion of the enormous objects in each pertrain list for references into the collection set, if the collection set is not empty.

9. An electronic computer controlled train/car collector for collecting enormous objects and inserting references into remembered sets of other cars, the collector comprising:

a collection set including at least one enormous object,

means for evacuating the enormous object by re-linking,

means for finding an unscanned portion of the enormous object,

means for scanning a preset amount of the unscanned portion for references to objects in other cars, wherein if a referenced to an object in an other car is found,

means for updating the remembered set of that other car, and

means for scanning the enormous object for references into the collection set, if the collection set is not empty.

10. The collector of claim 9 further comprising means for saving the location of the unscanned portion of the enormous object.

11. The collector of claim 9 further comprising means for returning to the collection process, if no unscanned portion of the enormous object is found.

12. The collector of claim 10, wherein if the collection set includes at least one other object, further comprising:

means for scanning the enormous object for references to the at least one other object, and, if any such references are found,

means for re-locating the at least one other object if it has not already been relocated, and;

means for updating the references in the re-linked enormous object to reflect the new location of the at least one other object.

13. The collector of claim 10 further comprising:

means for finding references in the relocated at least one other object to other objects in other cars, and

means for updating the remembered sets of the other cars with respect to the relocated at least one other object.

14. The collector of claim 10 further comprising;

at least one other object in another car in the collection set,

means for re-locating the at least one object,

means for scanning the enormous object for references to the at least one other object, and, if any such references are found,

means for updating the references in the re-linked enormous object.

15. The collector of claim 9, wherein at least one other car with at least one other object is in the collection set, the collector further comprising:

means for re-location the at least one other object,

means for scanning the enormous objects for references to the at least one other object, and if such a reference is found,

means for updating the reference to the relocated at least one other object

means for scanning the relocated at least one other object for references to other objects in other cars and updating the remembered sets of the other cars with respect to the re-located at least one other object.

16. The collector of claim 9 further comprising:

means for maintaining for each train a list of partially scanned enormous objects wherein in each collection increment some unscanned portion of some of these partially scanned objects is scanned for references to objects in other cars, wherein if a reference to an object in another car is found, updating the remembered set of that other car, and

means for scanning the remaining unscanned portion of the enormous objects in each per-train list for references into the collection set, if the collection set is not empty.

18. The computer readable media of claim 17 comprising further readable media containing instructions for execution in a processor for the practice of the process of claim 15 further including the step of saving the location of the unscanned portion of the enormous object.

19. The computer readable media of claim 17 comprising further readable media containing instructions for execution in a processor for the practice of the process of claim 16 further including the step of returning to the collection process if no- unscanned portion of the enormous object is found.

20. The computer readable media of claim 17 comprising further readable media containing instructions for execution in a processor for the practice of the process of claim 16 further including the step of steps of:

if the collection set includes at least one other object,

scanning the enormous object for references to the at least one other object, and, if any such references are found,

re-locating the at least one other object if it has not already been relocated, and,

updating the references in the re-linked enormous object to reflect the new location of the at least one other object.

21. The computer readable media of claim 18 comprising further readable media containing instructions for execution in a processor for the practice of the process of claim 15 further including the step of:

finding references in the relocated at least one other object to other objects in other cars and updating the remembered sets of the other cars with respect to the relocated at least one other object.

22. The computer readable media of claim 18 comprising further readable- media containing instructions for execution in a processor for the practice of the process of claim 16 further including the step of;

finding the at least one other object in another car in-the collection set,

scanning the enormous object for references to the at least one other object, and, if any such references are found,

re-locating the at least one object if it has not already been relocated, and,

updating the references in the re-linked enormous object to reflect the new location of the at least one other object.

23. The computer readable media of claim 17 comprising further readable media containing instructions for execution in a processor for the practice of the process of claim 15, wherein at least one other car with at least one other object is in the collection set, the process further including the steps of:

re-locating the at least one other object,

scanning the enormous object for references to the at least one other object, if such a reference is found,

updating the reference to the relocated object, and

scanning the relocated at least one other object for references to other objects in other cars and updating the remembered sets of the other cars with respect to the relocated at least one other object.

24. The computer readable media of claim 17 comprising further readable media containing instructions for execution in a processor for the practice of the process of claim 15, wherein at least one other car with at least one other object is in the collection set, the process further including the steps of:

maintaining for each train a list of partially scanned enormous objects wherein in each collection increment some unscanned portion of some of these partially scanned objects is scanned for references to objects in other cars, wherein if a reference to an object in another car is found, updating the remembered set of that other car, and

scanning the remaining unscanned portion of the enormous objects in each pertrain list for references into the collection set, if the collection set is not empty.

17. A computer readable media comprising:

the computer readable media containing instructions for executing in a processor for the practice of the process of;

including at least one enormous object as part of a collection set,

evacuating the enormous object by re-linking,

finding an unscanned portion of the enormous object,

scanning a preset amount of the unscanned portion for references to objects in other cars, wherein

if a reference to an object in another car is found, updating the remembered set of that other car, and

scanning the enormous object for references into the collection set, if the collection set is not empty.

25. Electromagnetic signals propagating on a computer network comprising, the electromagnetic signals carrying instructions for execution on a processor for the practice, in a train/car garbage collector, of a process for collecting enormous objects and for reference insertions into remembered sets of other cars, the process comprising the steps of:

including at least one enormous object as part of a collection set,

evacuating the enormous object by re-linking,

finding an unscanned portion of the enormous object,

scanning a preset amount of the unscanned portion for references to objects in other cars, wherein

if a reference to an object in an other car is found, updating the remembered set of that other car, and

scanning the enormous object for references into the collection set, if the collection set is not empty.

26. The electromagnetic signals of claim 25 further comprising electromagnetic signals carrying instructions for execution on a processor for the practice of the process of claim 25 further comprising the step of saving the location of the unscanned portion of the enormous object.

27. The electromagnetic signals of claim 25 further comprising electromagnetic signals carrying instructions for execution on a processor for the practice of the process of claim 25 further comprising the step of returning to the collection process if no unscanned portion of the enormous object is found.

28. The electromagnetic signals of claim 25 further comprising electromagnetic signals carrying instructions for execution on a processor for the practice of the process of claim 25 further comprising the steps of:

if the collection set includes at least one other object,

scanning the enormous object for references to the at least one other object, and, if any such references are found,

re-locating the at least one other object if it has not already been relocated, and

updating the references in the re-linked enormous object to reflect the new location of the at least one other object.

29. The electromagnetic signals of claim 26 further comprising electromagnetic signals carrying instructions for execution on a processor for the practice of the process of claim 26 further comprising the steps of finding references in the relocated at least one other object to other objects in other cars and updating the remembered sets of the other cars with respect to the re-located at least one other object.

30. The electromagnetic signals of claim 26 further comprising electromagnetic signals carrying instructions for execution on a processor for the practice of the process of claim 26 further comprising the step of;

finding the at least one other object in another car in the collection set,

scanning the enormous object for references to the at least one other object, and, if any such references are found,

re-locating the at least one other object if it has not already been relocated, and

updating the references in the re-linked enormous object to reflect the new location of the at least one other object.

31. The electromagnetic signals of claim 25 further comprising electromagnetic signals carrying instructions for execution on a processor for the practice of the process of claim 25, wherein at least one other car with at least one other object is in the collection set, the process further comprising the steps of:

re-locating the at least one other object,

scanning the enormous object for references to the at least one other object, if such a reference is found,

updating the reference to the relocated object, and

scanning the relocated at least one other object for references to other objects in other cars and updating the remembered sets of the other cars with respect to the relocated at least one other object.

32. The electromagnetic signals of claim 25 further comprising electromagnetic signals carrying instructions for execution on a processor for the practice of the process of claim 25, wherein at least one other car with at least one other object is in the collection set, the process further comprising the steps of:

maintaining for each train a list of partially scanned enormous objects wherein in each collection increment some unscanned portion of some of these partially scanned objects is scanned for references to objects in other cars, wherein if a reference to an object in another car is found, updating the remembered set of that other car, and

scanning the remaining unscanned portion of the enormous objects in each pertrain list for references into the collection set, if the collection set is not empty.