Incremental class unloading in a train-algorithm-based garbage collector

• US 6,529,919 B1
• Filed: 02/15/2000
• Issued: 03/04/2003
• Est. Priority Date: 02/15/2000
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Agesen, Ole, Garthwaite, Alexander T.
• Primary Examiner(s): Breene, John E.
• Assistant Examiner(s): DODDS, HAROLD E
• Application Number:
  US09/504,091
• Time in Patent Office: 1,113 Days
• Field of Search: 707/1, 707/4, 707/10, 707/100, 707/101, 707/103, 707/104.1, 707/200, 707/202-206, 707/15, 707/16, 707/20, 707/25, 711/100, 711/154, 711/165, 711/170, 711/171, 711/173, 706/15, 706/16, 706/20, 706/25
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: G06F 9/44594 Unloading
• CPC Class Codes: G06F 9/4493 Object persistence
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A garbage collector collects a train-managed heap in accordance with the train algorithm. In doing so, it concentrates into a respective train the heap-located objects that belong to garbage cycles even if those cycles additionally include certain types of objects that are outside the train-managed heap. It does so by using objects within the heap as proxies for those extra-heap objects, and it evacuates into a proxy object'"'"'s train any collection-set objects referred to by the extra-heap objects for which the proxy object is a proxy. The objects in those garbage cycles containing the extra-heap objects can thereby be collected incrementally despite the extra-heap references to them.

Claims

1. A method of garbage collection in which a train-algorithm-managed generation of a garbage-collected heap contains objects located in car sections and is collected in accordance with the train algorithm, in collection cycles for which respective collection sets of the car sections are established, by repeatedly establishing new trains, evacuating from the collection set the objects in the collection set that are referred to from outside the collection set, placing objects thus evacuated into trains containing objects that refer to them, and reclaiming the car sections that remain in the collection set, wherein the method further includes:

A) associating proxy objects in the garbage-collected heap with respective external objects outside the garbage-collected heap; and

B) evacuating from the collection set those of its objects that are referred to by external objects associated with proxy objects not in the collection set, the trains into which the objects thus evacuated are placed when the respective proxy objects are in the train-managed generation being the trains to which the respective proxy objects belong or to which the respective proxy objects are currently destined for evacuation.

2. A method as defined in claim 1 that further includes reclaiming the external objects with which are associated proxy objects that remain in the collection set after evacuation.

3. A method as defined in claim 1 wherein the external objects associated with the proxy objects represent object classes.

4. A method as defined in claim 3 that further includes reclaiming the external objects with which are associated proxy objects that remain in the collection set after evacuation.

5. A method as defined in claim 3 wherein the method includes evacuating from the collection set any proxy object with which is associated an external object that represents a class of which an instance exists outside the collection set.

6. A method as defined in claim 5 that further includes reclaiming the external objects with which are associated proxy objects that remain in the collection set after evacuation.

7. A method as defined in claim 5 wherein the method includes, when the collection set contains proxy objects with which are associated external objects that represent classes of which instances exist in trains within the garbage-collected generation, evacuating those proxy objects into the trains that contain those instances.

8. A method as defined in claim 7 that further includes reclaiming the external objects with which are associated proxy objects that remain in the collection set after evacuation.

9. A method as defined in claim 7 wherein the trains into which are evacuated proxy objects when the collection sets contain proxy objects with which are associated external objects that represent classes of which instances exist in trains within the garbage-collected generation are the youngest trains that contain those instances.

10. A method as defined in claim 9 that further includes reclaiming the external objects with which are associated proxy objects that remain in the collection set after evacuation.

11. A method as defined in claim 9 further comprising:

A) maintaining for each class represented by an external structure associated with a proxy object in the train-algorithm-managed generation a youngest-train identifier of the youngest train containing an instance of that class; and

B) evacuating proxy objects from the collection sets in accordance with youngest-train identifier maintained for the classes represented by the external structures with which those proxy objects are associated.

12. A method as defined in claim 11 wherein the method includes maintaining, for each car section that contains a proxy object associated with an external object that represents a class of which a younger train contains an instance, a remembered set containing the youngest-train identifier for each such class.

13. A method as defined in claim 12 that further includes reclaiming the external objects with which are associated proxy objects that remain in the collection set after evacuation.

14. A method as defined in claim 12 wherein:

A) the method includes maintaining for each car section a regular remembered set containing entries corresponding to references into the car section from younger car sections; and

B) objects are evacuated from car sections in accordance with the contents of those car sections'"'"' regular remembered sets.

15. A method as defined in claim 1 wherein:

A) the external objects contain information on which objects in the train-managed generation depend; and

B) the method further includes evacuating from the collection set those of its proxy objects that are associated with the external objects that contain information on which depend objects outside the collection set.

16. A method as defined in claim 15 that further includes reclaiming the external objects with which are associated proxy objects that remain in the collection set after evacuation.

17. A method as defined in claim 15 wherein the train into which is evacuated a proxy object from the collection set if that proxy object is associated with an external object containing information on which an object in a train within the garbage-collected generation depends is least as young as the youngest train that contains an object that depends on that external object.

18. A method as defined in claim 17 that further includes reclaiming the external objects with which are associated proxy objects that remain in the collection set after evacuation.

19. A garbage collector that employs the train algorithm to collect a train-algorithm-managed generation of a garbage-collected heap, which train-algorithm-managed generation contains objects located in car sections, the garbage collector collecting the train-algorithm-managed generation, in collection cycles for which respective collection sets of the car sections are established, by repeatedly establishing new trains, evacuating from the collection set the objects in the collection set that are referred to from outside the collection set, placing objects thus evacuated into trains containing objects that refer to them, and reclaiming the car sections that remain in the collection set, wherein the garbage collector:

A) associates proxy objects in the garbage-collected heap with respective external objects outside the garbage-collected heap; and

B) evacuates from the collection set those of its objects that are referred to by external objects associated with proxy objects not in the collection set, the trains into which the objects thus evacuated are placed when the respective proxy objects are in the train-managed generation being the trains to which the respective proxy objects belong or to which the respective proxy objects are currently destined for evacuation.

20. A garbage collector as defined in claim 19 that additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

21. A garbage collector as defined in claim 19 wherein the external objects associated with the proxy objects represent object classes.

22. A garbage collector as defined in claim 21 that additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

23. A garbage collector as defined in claim 21 that additionally evacuates from the collection set any proxy object with which is associated an external object that represents a class of which an instance exists outside the collection set.

24. A garbage collector as defined in claim 23 that additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

25. A garbage collector as defined in claim 23 that, when the collection set contains proxy objects with which are associated external objects that represent classes of which instances exist in trains within the garbage-collected generation, evacuates those proxy objects into the trains that contain those instances.

26. A garbage collector as defined in claim 25 that additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

27. A garbage collector as defined in claim 25 wherein the trains into which are evacuated proxy objects when the collection sets contain proxy objects with which are associated external objects that represent classes of which instances exist in trains within the garbage-collected generation are the youngest trains that contain those instances.

28. A garbage collector as defined in claim 27 that additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

29. A garbage collector as defined in claim 27 that additionally:

A) maintains for each class represented by an external structure associated with a proxy object in the train-algorithm-managed generation a youngest-train identifier of the youngest train containing an instance of that class; and

B) evacuates proxy objects from the collection sets in accordance with youngest-train identifier maintained for the classes represented by the external structures with which those proxy objects are associated.

30. A garbage collector as defined in claim 29 wherein the garbage collector maintains, for each car section that contains a proxy object associated with an external object that represents a class of which a younger train contains an instance, a remembered set containing the youngest-train identifier for each such class.

31. A garbage collector as defined in claim 30 that additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

32. A garbage collector as defined in claim 30 wherein:

A) the garbage collector maintains for each car section a regular remembered set containing entries corresponding to references into the car section from younger car sections; and

B) objects are evacuated from car sections in accordance with the contents of those car sections'"'"' regular remembered sets.

33. A garbage collector as defined in claim 19 wherein:

A) the external objects contain information on which objects in the train-managed generation depend; and

B) the garbage collector additionally evacuates from the collection set those of its proxy objects that are associated with the external objects that contain information on which depend objects outside the collection set.

34. A garbage collector as defined in claim 33 that additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

35. A garbage collector as defined in claim 33 wherein the train into which is evacuated a proxy object from the collection set if that proxy object is associated with an external object containing information on which an object in a train within the garbage-collected generation depends is least as young as the youngest train that contains an object that depends on that external object.

36. A garbage collector as defined in claim 35 that additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

37. A storage medium containing instructions readable by a computer configure the computer to operate as a garbage collector that employs the train algorithm to collect a train-algorithm-managed generation of a garbage-collected heap, which train-algorithm-managed generation contains objects located in car sections, the garbage collector collecting the train-algorithm-managed generation, in collection cycles for which respective collection sets of the car sections are established, by repeatedly establishing new trains, evacuating from the collection set the objects in the collection set referred to from outside the collection set, placing objects thus evacuated into trains containing objects that refer to them, and reclaiming the car sections that remain in the collection set, wherein the garbage collector:

A) associates proxy objects in the garbage-collected heap with respective external objects outside the garbage-collected heap; and

B) evacuates from the collection set those of its objects that are referred to by external objects associated with proxy objects not in the collection set, the trains into which the objects thus evacuated are placed when the respective proxy objects are in the train-managed generation being the trains to which the respective proxy objects belong or to which the respective proxy objects are currently destined for evacuation.

38. A storage medium as defined in claim 37 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

39. A storage medium as defined in claim 37 wherein the external objects associated with the proxy objects represent object classes.

40. A storage medium as defined in claim 39 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

41. A storage medium as defined in claim 39 wherein the garbage collector additionally evacuates from the collection set any proxy object with which is associated an external object that represents a class of which an instance exists outside the collection set.

42. A storage medium as defined in claim 41 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

43. A storage medium as defined in claim 41 wherein the garbage collector, when the collection set contains proxy objects with which are associated external objects that represent classes of which instances exist in trains within the garbage-collected generation, evacuates those proxy objects into the trains that contain those instances.

44. A storage medium as defined in claim 43 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

45. A storage medium as defined in claim 43 wherein the trains into which are evacuated proxy objects when the collection sets contain proxy objects with which are associated external objects that represent classes of which instances exist in trains within the garbage-collected generation are the youngest trains that contain those instances.

46. A storage medium as defined in claim 45 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

47. A storage medium as defined in claim 45 wherein the garbage collector additionally:

A) maintains for each class represented by an external structure associated with a proxy object in the train-algorithm-managed generation a youngest-train identifier of the youngest train containing an instance of that class; and

B) evacuates proxy objects from the collection sets in accordance with youngest-train identifier maintained for the classes represented by the external structures with which those proxy objects are associated.

48. A storage medium as defined in claim 47 wherein the garbage collector maintains, for each car section that contains a proxy object associated with an external object that represents a class of which a younger train contains an instance, a remembered set containing the youngest-train identifier for each such class.

49. A storage medium as defined in claim 48 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

50. A storage medium as defined in claim 48 wherein:

A) the garbage collector maintains for each car section a regular remembered set containing entries corresponding to references into the car section from younger car sections; and

B) objects are evacuated from car sections in accordance with the contents of those car sections'"'"' regular remembered sets.

51. A storage medium as defined in claim 37 wherein:

A) the external objects contain information on which objects in the train-managed generation depend; and

B) the garbage collector additionally evacuates from the collection set those of its proxy objects that are associated with the external objects that contain information on which depend objects outside the collection set.

52. A storage medium as defined in claim 51 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

53. A storage medium as defined in claim 51 wherein the train into which is evacuated a proxy object from the collection set if that proxy object is associated with an external object containing information on which an object in a train within the garbage-collected generation depends is least as young as the youngest train that contains an object that depends on that external object.

54. A storage medium as defined in claim 53 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

55. A computer signal representing sequences of instructions that, when executed by a processor, cause it to operate as a garbage collector that employs the train algorithm to collect a train-algorithm-managed generation of a garbage-collected heap, which train-algorithm-managed generation contains objects located in car sections, the garbage collector collecting the train-algorithm-managed generation, in collection cycles for which respective collection sets of the car sections are established, by repeatedly establishing new trains, evacuating from the collection set the objects in the collection set referred to from outside the collection set, placing objects thus evacuated into the youngest trains containing objects that refer to them, and reclaiming the car sections that remain in the collection set, wherein the garbage collector:

A) associates proxy objects in the garbage-collected heap with respective external objects outside the garbage-collected heap; and

B) evacuates from the collection set those of its objects that are referred to by external objects associated with proxy objects not in the collection set, the trains into which the objects thus evacuated are placed when the respective proxy objects are in the train-managed generation being the trains to which the respective proxy objects belong or to which the respective proxy objects are currently destined for evacuation.

56. A computer signal as defined in claim 55 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

57. A computer signal as defined in claim 55 wherein the external objects associated with the proxy objects represent object classes.

58. A computer signal as defined in claim 57 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

59. A computer signal as defined in claim 57 wherein the garbage collector additionally evacuates from the collection set any proxy object with which is associated an external object that represents a class of which an instance exists outside the collection set.

60. A computer signal as defined in claim 59 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

61. A computer signal as defined in claim 59 wherein the garbage collector, when the collection set contains proxy objects with which are associated external objects that represent classes of which instances exist in trains within the garbage-collected generation, evacuates those proxy objects into the trains that contain those instances.

62. A computer signal as defined in claim 61 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

63. A computer signal as defined in claim 61 wherein the trains into which are evacuated proxy objects when the collection sets contain proxy objects with which are associated external objects that represent classes of which instances exist in trains within the garbage-collected generation are the youngest trains that contain those instances.

64. A computer signal as defined in claim 63 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

65. A computer signal as defined in claim 63 wherein the garbage collector additionally:

A) maintains for each class represented by an external structure associated with a proxy object in the train-algorithm-managed generation a youngest-train identifier of the youngest train containing an instance of that class; and

B) evacuates proxy objects from the collection sets in accordance with youngest-train identifier maintained for the classes represented by the external structures with which those proxy objects are associated.

66. A computer signal as defined in claim 65 wherein the garbage collector maintains, for each car section that contains a proxy object associated with an external object that represents a class of which a younger train contains an instance, a remembered set containing the youngest-train identifier for each such class.

67. A computer signal as defined in claim 66 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

68. A computer signal as defined in claim 66 wherein:

A) the garbage collector maintains for each car section a regular remembered set containing entries corresponding to references into the car section from younger car sections; and

B) objects are evacuated from car sections in accordance with the contents of those car sections'"'"' regular remembered sets.

69. A computer signal as defined in claim 55 wherein:

A) the external objects contain information on which objects in the train-managed generation depend; and

B) the garbage collector additionally evacuates from the collection set those of its proxy objects that are associated with the external objects that contain information on which depend objects outside the collection set.

70. A computer signal as defined in claim 69 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

71. A computer signal as defined in claim 69 wherein the train into which is evacuated a proxy object from the collection set if that proxy object is associated with an external object containing information on which an object in a train within the garbage-collected generation depends is least as young as the youngest train that contains an object that depends on that external object.

72. A computer signal as defined in claim 71 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.

73. A garbage collector that employs the train algorithm to collect a train-algorithm-managed generation of a garbage-collected heap, which train-algorithm-managed generation contains objects located in car sections, the garbage collector collecting the train-algorithm-managed generation, in collection cycles for which respective collection sets of the car sections are established, by repeatedly establishing new trains, evacuating from the collection set the objects in the collection set referred to from outside the collection set, placing objects thus evacuated into trains containing objects that refer to them, and reclaiming the car sections that remain in the collection set, wherein the garbage collector includes:

A) means for associating proxy objects in the garbage-collected heap with respective external objects outside the garbage-collected heap; and

B) means for evacuating from the collection set those of its objects that are referred to by external objects associated with proxy objects not in the collection set, the trains into which the objects thus evacuated are placed when the respective proxy objects are in the train-managed generation being the trains to which the respective proxy objects belong or to which the respective proxy objects are currently destined for evacuation.