Efficient encoding of references into a collection set

• US 20040088339A1
• Filed: 11/05/2002
• Published: 05/06/2004
• Est. Priority Date: 11/05/2002
• Status: Active Grant

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

Abstract

A garbage collector employs the train algorithm, in which a generation of a heap is divided into so-called car sections that are grouped into “trains.” Remembered sets associated with respective car sections contain entries that list locations where references to objects in the respective car sections have been found as a result of scanning locations identified by write barriers. In each collection increment, the entries in the remembered sets associated with the car sections to be collected during that increment are processed to find which of the locations thus listed still contain references into the cars to be collected. The resultant locations are stored in scratch-pad lists, and each entry in that list includes a mode indicator that specifies whether the entry represents a single reference'"'"'s location or the locations of more than one reference. One possible value of the mode indicator indicates that the entry consists of two computer words rather than one, the second computer word containing a list of offsets into a region specified by the first word. Another possible mode-indicator value indicates that a region contains references, but it does not specify where within the region those references occur.

Claims

1. For employing a computer system, which includes memory of which at least some is used as a heap for dynamic allocation, to perform garbage collection on an incrementally collected generation of the heap in collection increments with which respective collections sets are associated, a method comprising, in each of at least some of the collection increments:

A) identifying references that are located outside the collection set and refer to objects in the collection set;

B) creating a reference list of reference-list entries representing references thus identified, each of at least some of the reference-list entries including a location identifier and a mode indicator that indicates whether the location identifier specifies;

i) an individual-reference location in which a single reference represented by that reference-list entry is located;

or

ii) a region that is sized to contain more than one reference and contains each reference represented by that reference-list entry;

C) performing an evacuation operation that includes, for each of at least some of the reference-list entries;

i) identifying each reference represented by that reference-list entry by;

a) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies an individual-reference location, identifying as the reference represented by that reference-list entry the reference that occupies the individual-reference location thereby specified; and

b) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies a region sized to contain more than one reference, identifying as one said reference represented by that reference-list entry each reference that is located in the region thereby specified and refers to an object in the collection set; and

ii) evacuating from the collection set each object referred to by a reference represented by that reference-list entry or referred to by a reference in an object thereby evacuated; and

D) reclaiming the memory space occupied by the collection set.

2. A method as defined in claim 1 wherein:

A) the garbage collection is performed on the incrementally collected generation in accordance with the train algorithm, in which the incrementally collected generation is treated as divided into car sections grouped into trains;

B) the reference list is a composite reference list divided into constituent reference lists of which each is associated with a different train; and

C) each collection-set object referred to by a reference represented by reference-list entry in a constituent reference list and not previously evacuated is evacuated to a car section that belongs to the train with which that constituent reference list is associated.

3. A method as defined in claim 1 wherein:

A) when the mode indicator indicates that the reference-list entry specifies a region sized to contain more than one reference, it further indicates whether the entry additionally indicates where each reference represented by that reference-list entry is located within that region; and

B) when the mode indicator indicates that the reference-list entry additionally indicates where each reference represented by that reference-list entry is located within that region, the reference-list entry further includes an offset list that indicates where each reference represented by that reference-list entry is located within that region.

4. A method as defined in claim 3 wherein the number of bits of which a reference-list entry consists depends on whether the mode indicator indicates that the reference-list entry additionally indicates where each reference represented by that reference-list entry is located within that region.

5. A method as defined in claim 3 wherein at least some possible values of the mode indicator additionally indicate different numbers of offsets in the offset list.

6. A method as defined in claim 1 wherein the location identifier and mode indicator together consist of the number of bits in an address.

7. A method as defined in claim 1 wherein:

A) references are so aligned that the least-significant bits of every reference'"'"'s address contain the same value, whereby a reference'"'"'s address consists of explicit bits, which vary from reference to reference, and implicit bits, which do not;

B) regions specified by reference-list identifiers are so aligned that the least-significant bits of every such region'"'"'s address contain the same value, whereby such a region'"'"'s address consists of an explicit part, whose contents vary from region to region, and an implicit part, which does not; and

C) each location identifier consists of a predetermined number of bits and includes each bit of the explicit part of the address of the individual-reference location or region thereby specified but less than each bit of the implicit part thereof.

8. A method as defined in claim 7 wherein the location identifier and mode indicator together consist of the number of bits in an address.

9. A method as defined in claim 1 wherein at least some possible values of the mode indicator additionally indicate different sizes of the region whose location the location identifier specifies.

10. 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 it to treat at least a portion of the memory as a heap in which dynamic allocation occurs and act as a garbage collector that collects an incrementally collected generation of the heap in increments, with which respective collection sets are associated, by, in each of at least some of the collection increments;

i) identifying references that are located outside the collection set and refer to objects in the collection set;

ii) creating a reference list of reference-list entries representing references thus identified, each of at least some of the reference-list entries including a location identifier and a mode indicator that indicates whether the location identifier specifies;

a) an individual-reference location in which a single reference represented by that reference-list entry;

or

b) a region that is sized to contain more than one reference and contains each reference represented by that reference-list entry;

iii) performing an evacuation operation that includes, for each reference-list entry;

a) identifying each reference represented by that reference-list entry by;

(1) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies an individual-reference location, identifying as the reference represented by that reference-list entry the reference that occupies the individual-reference location thereby specified; and

(2) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies a region sized to contain more than one reference, identifying as one said reference represented by that reference-list entry each reference that is located in the region thereby specified and refers to an object in the collection set; and

b) evacuating from the collection set each object referred to by a reference represented by that reference-list entry or referred to by a reference in an object thereby evacuated; and

iv) reclaiming the memory space occupied by the collection set.

11. A computer system as defined in claim 10 wherein:

A) the garbage collector collects the incrementally collected generation in accordance with the train algorithm, in which the incrementally collected generation is treated as divided into car sections grouped into trains;

B) the reference list is a composite reference list divided into constituent reference lists of which each is associated with a different train; and

C) each collection-set object referred to by a reference represented by reference-list entry in a constituent reference list and not previously evacuated is evacuated to a car section that belongs to the train with which that constituent reference list is associated.

12. A computer system as defined in claim 10 wherein:

A) when the mode indicator indicates that the reference-list entry specifies a region sized to contain more than one reference, it further indicates whether the entry additionally indicates where each reference represented by that reference-list entry is located within that region; and

B) when the mode indicator indicates that the reference-list entry additionally indicates where each reference represented by that reference-list entry is located within that region, the reference-list entry further includes an offset list that indicates where each reference represented by that reference-list entry is located within that region.

13. A computer system as defined in claim 12 wherein the number of bits of which a reference-list entry consists depends on whether the mode indicator indicates that the reference-list entry additionally indicates where each reference represented by that reference-list entry is located within that region.

14. A computer system as defined in claim 12 wherein at least some possible values of the mode indicator additionally indicate different numbers of offsets in the offset list.

15. A computer system as defined in claim 10 wherein the location identifier and mode indicator together consist of the number of bits in an address.

16. A computer system as defined in claim 10 wherein:

A) references are so aligned that the least-significant bits of every reference'"'"'s address contain the same value, whereby a reference'"'"'s address consists of explicit bits, which vary from reference to reference, and implicit bits, which do not;

B) regions specified by reference-list identifiers are so aligned that the least-significant bits of every such region'"'"'s address contain the same value, whereby such a region'"'"'s address consists of an explicit part, whose contents vary from region to region, and an implicit part, which does not; and

C) each location identifier consists of a predetermined number of bits and includes each bit of the explicit part of the address of the individual-reference location or region thereby specified but less than each bit of the implicit part thereof.

17. A computer system as defined in claim 16 wherein the location identifier and mode indicator together consist of the number of bits in an address.

18. A computer system as defined in claim 10 wherein at least some possible values of the mode indicator additionally indicate different sizes of the region whose location the location identifier specifies.

19. A storage medium containing instructions readable by a computer system that includes memory to configure the computer system to treat at least a portion of the memory as a heap in which dynamic allocation occurs and act as a garbage collector that collects an incrementally collected generation of the heap in increments, with which respective collection sets are associated, by, in each of at least some of the collection increments:

A) identifying references that are located outside the collection set and refer to objects in the collection set;

B) creating a reference list of reference-list entries representing references thus identified, each of at least some of the reference-list entries including a location identifier and a mode indicator that indicates whether the location identifier specifies;

i) an individual-reference location in which a single reference represented by that reference-list entry;

or

ii) a region that is sized to contain more than one reference and contains each reference represented by that reference-list entry;

C) performing an evacuation operation that includes, for each reference-list entry;

i) identifying each reference represented by that reference-list entry by;

a) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies an individual-reference location, identifying as the reference represented by that reference-list entry the reference that occupies the individual-reference location thereby specified; and

b) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies a region sized to contain more than one reference, identifying as one said reference represented by that reference-list entry each reference that is located in the region thereby specified and refers to an object in the collection set; and

ii) evacuating from the collection set each object referred to by a reference represented by that reference-list entry or referred to by a reference in an object thereby evacuated; and

D) reclaiming the memory space occupied by the collection set.

20. A storage medium as defined in claim 19 wherein:

A) the garbage collector collects the incrementally collected generation in accordance with the train algorithm, in which the incrementally collected generation is treated as divided into car sections grouped into trains;

B) the reference list is a composite reference list divided into constituent reference lists of which each is associated with a different train; and

C) each collection-set object referred to by a reference represented by reference-list entry in a constituent reference list and not previously evacuated is evacuated to a car section that belongs to the train with which that constituent reference list is associated.

21. A storage medium as defined in claim 19 wherein:

A) when the mode indicator indicates that the reference-list entry specifies a region sized to contain more than one reference, it further indicates whether the entry additionally indicates where each reference represented by that reference-list entry is located within that region; and

B) when the mode indicator indicates that the reference-list entry additionally indicates where each reference represented by that reference-list entry is located within that region, the reference-list entry further includes an offset list that indicates where each reference represented by that reference-list entry is located within that region.

22. A storage medium as defined in claim 21 wherein the number of bits of which a reference-list entry consists depends on whether the mode indicator indicates that the reference-list entry additionally indicates where each reference represented by that reference-list entry is located within that region.

23. A storage medium as defined in claim 21 wherein at least some possible values of the mode indicator additionally indicate different numbers of offsets in the offset list.

24. A storage medium as defined in claim 19 wherein the location identifier and mode indicator together consist of the number of bits in an address.

25. A storage medium as defined in claim 19 wherein:

A) references are so aligned that the least-significant bits of every reference'"'"'s address contain the same value, whereby a reference'"'"'s address consists of explicit bits, which vary from reference to reference, and implicit bits, which do not;

B) regions specified by reference-list identifiers are so aligned that the least-significant bits of every such region'"'"'s address contain the same value, whereby such a region'"'"'s address consists of an explicit part, whose contents vary from region to region, and an implicit part, which does not; and

C) each location identifier consists of a predetermined number of bits and includes each bit of the explicit part of the address of the individual-reference location or region thereby specified but less than each bit of the implicit part thereof.

26. A storage medium as defined in claim 25 wherein the location identifier and mode indicator together consist of the number of bits in an address.

27. A storage medium as defined in claim 19 wherein at least some possible values of the mode indicator additionally indicate different sizes of the region whose location the location identifier specifies.

28. An electromagnetic signal representing sequences of instructions that, when executed by a computer system that includes memory, configure the computer system to treat at least a portion of the memory as a heap in which dynamic allocation occurs and act as a garbage collector that collects an incrementally collected generation of the heap in increments, with which respective collection sets are associated, by, in each of at least some of the collection increments:

A) identifying references that are located outside the collection set and refer to objects in the collection set;

B) creating a reference list of reference-list entries representing references thus identified, each of at least some of the reference-list entries including a location identifier and a mode indicator that indicates whether the location identifier specifies;

i) an individual-reference location in which a single reference represented by that reference-list entry;

or

ii) a region that is sized to contain more than one reference and contains each reference represented by that reference-list entry;

C) performing an evacuation operation that includes, for each reference-list entry;

i) identifying each reference represented by that reference-list entry by;

a) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies an individual-reference location, identifying as the reference represented by that reference-list entry the reference that occupies the individual-reference location thereby specified; and

b) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies a region sized to contain more than one reference, identifying as one said reference represented by that reference-list entry each reference that is located in the region thereby specified and refers to an object in the collection set; and

ii) evacuating from the collection set each object referred to by a reference represented by that reference-list entry or referred to by a reference in an object thereby evacuated; and

D) reclaiming the memory space occupied by the collection set.

29. A electromagnetic signal as defined in claim 28 wherein:

A) the garbage collector collects the incrementally collected generation in accordance with the train algorithm, in which the incrementally collected generation is treated as divided into car sections grouped into trains;

B) the reference list is a composite reference list divided into constituent reference lists of which each is associated with a different train; and

C) each collection-set object referred to by a reference represented by reference-list entry in a constituent reference list and not previously evacuated is evacuated to a car section that belongs to the train with which that constituent reference list is associated.

30. A electromagnetic signal as defined in claim 28 wherein:

A) when the mode indicator indicates that the reference-list entry specifies a region sized to contain more than one reference, it further indicates whether the entry additionally indicates where each reference represented by that reference-list entry is located within that region; and

B) when the mode indicator indicates that the reference-list entry additionally indicates where each reference represented by that reference-list entry is located within that region, the reference-list entry further includes an offset list that indicates where each reference represented by that reference-list entry is located within that region.

31. A electromagnetic signal as defined in claim 30 wherein the number of bits of which a reference-list entry consists depends on whether the mode indicator indicates that the reference-list entry additionally indicates where each reference represented by that reference-list entry is located within that region.

32. A electromagnetic signal as defined in claim 30 wherein at least some possible values of the mode indicator additionally indicate different numbers of offsets in the offset list.

33. A electromagnetic signal as defined in claim 28 wherein the location identifier and mode indicator together consist of the number of bits in an address.

34. A electromagnetic signal as defined in claim 28 wherein:

A) references are so aligned that the least-significant bits of every reference'"'"'s address contain the same value, whereby a reference'"'"'s address consists of explicit bits, which vary from reference to reference, and implicit bits, which do not;

B) regions specified by reference-list identifiers are so aligned that the least-significant bits of every such region'"'"'s address contain the same value, whereby such a region'"'"'s address consists of an explicit part, whose contents vary from region to region, and an implicit part, which does not; and

C) each location identifier consists of a predetermined number of bits and includes each bit of the explicit part of the address of the individual-reference location or region thereby specified but less than each bit of the implicit part thereof.

35. A electromagnetic signal as defined in claim 34 wherein the location identifier and mode indicator together consist of the number of bits in an address.

36. A electromagnetic signal as defined in claim 28 wherein at least some possible values of the mode indicator additionally indicate different sizes of the region whose location the location identifier specifies.

37. For collecting an incrementally collected generation of a heap portion of a computer system'"'"'s memory, where dynamic allocation occurs, in collection increments, with which respective collection sets are associated, a garbage collector comprising:

A) means for identifying references that are located outside the collection set and refer to objects in the collection set;

B) means for creating a reference list of reference-list entries representing references thus identified, each of at least some of the reference-list entries including a location identifier and a mode indicator that indicates whether the location identifier specifies;

i) an individual-reference location in which a single reference represented by that reference-list entry;

or

ii) a region that is sized to contain more than one reference and contains each reference represented by that reference-list entry;

C) means for performing an evacuation operation that includes, for each reference-list entry;

i) identifying each reference represented by that reference-list entry by;

a) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies an individual-reference location, identifying as the reference represented by that reference-list entry the reference that occupies the individual-reference location thereby specified; and

b) if that reference-list entry'"'"'s mode indicator indicates that the reference-list entry specifies a region sized to contain more than one reference, identifying as one said reference represented by that reference-list entry each reference that is located in the region thereby specified and refers to an object in the collection set; and

ii) evacuating from the collection set each object referred to by a reference represented by that reference-list entry or referred to by a reference in an object thereby evacuated; and

D) means for reclaiming the memory space occupied by the collection set.