Parallel card table scanning and updating
View Patent ↗During a collection interval, if a multi-threaded generational, copying garbage collector finds that a card contains a reference to a younger generation, it gives a corresponding card table entry a youngergen value selected from a plurality of youngergen values at the beginning of the interval as the “current” youngergen value. The youngergen value chosen for a given collection interval differs from the one that was chosen for the previous collection interval. As a result, a collector thread is able to distinguish between a card in which a reference to the younger generation remained at the end of the previous interval and one identified by some other thread during the current interval as referring to a young-generation object. In that way, the thread is able to avoid unnecessary scanning.
1. A method of garbage collection comprising:
A) providing a computer system that includes memory and executes a mutator that modifies references in a dynamically allocated heap in the memory;
B) configuring the computer system to act as a garbage collector that:
i) treats the heap as divided into a plurality of generations, including at least one young generation and at least one old generation;
ii) treats the old generation as divided into cards;
iii) maintains a card table, comprising a plurality of card-table fields of which each is associated with a respective card and card range, in which the mutator indicates where it has modified references, a value contained in each card-table field being one of a plurality of possible entry values that include at least one clean-indicating value, at least one non-clean-indicating value, at least one current-younger-generation-and-non-clean-indicating value, and a plurality are younger-generation-indicating values; and
iv) performs young-generation collections in each of which the garbage collector performs a reachable-object-identification operation, in which it identifies selected objects in the young generation, and reclaims memory space in the young generation not occupied by objects thus identified, the reachable-object-identification operation including performing in a plurality of garbage-collection threads an old-generation-scanning operation, in which the garbage collector identifies objects in the young generation referred to by old-generation references, the objects thus identified sometimes being promoted into the old generation and sometimes remaining in the young generation, the old-generation-scanning operation including:
a) adopting as the current younger-generation-indicating value for that young-generation collection one of the younger-generation-indicating values different from the younger-generation-indicating value adopted as the current younger-generation-indicating value in the previous old-generation-scanning operation;
b) adopting at least one other younger-generation-indicating value as the previous younger-generation-indicating value for that collection, the previous younger-generation-indicating value being interpreted as a non-clean-indicating value;
c) for each card-table field, employing a garbage-collection thread to perform an entry-processing operation in which that garbage-collection thread:
(1) makes a scan determination, based on the contents of that card-table field, of whether to perform a range-scanning operation on the card range associated with that card-table field, the determination being affirmative if that card-table field contains a non-clean-indicating value or the current-generation-and-non-clean-indicating value; and
(2) if the scan determination is affirmative, performs a range-scanning operation, in which:
(a) that garbage-collection thread performs a range-scan reference-inspection operation in which it scans the card range for references that are contained in objects not promoted during that young-generation collection and refer to objects in the young generation, whereby objects thus referred to are identified by the reachable-object-identification operation; and
(b) that garbage-collection thread performs a range-scan entry-update operation in which:
(i) the resultant value of that card-table field's contents is the current younger-generation-indicating value if any object thus identified is not promoted as a result; and
(ii) otherwise, the value of that card-table field's contents are changed either from a non-clean-indicating value to the clean-indicating value or from the current-younger-generation-and-non-clean-indicating value to the current younger-generation-indicating value; and
d) for each object promoted into the old generation during that young-generation collection, employing a garbage-collection thread to perform a promoted-object-scanning operation, in which that garbage-collection thread:
(1) scans that object for references that refer to objects in the young generation, whereby objects thus referred to are identified by the reachable-object-identification operation; and
(2) performs an object-scan entry-update operation, in which, for each reference in that object that refers to an object thus identified that is not promoted as a result:
(a) the value of the contents of the card-table field for the card range containing that reference becomes the current-younger-generation-and-non-clean-indicating value if that card-table field's immediately previous contents are a non-clean-indicating value; and
(b) otherwise, the resultant value of the contents of the card-table field for the card range containing that reference is the current younger-generation-indicating value; and
C) employing the computer system to execute the garbage collector.
2. A method as defined in claim 1 wherein the card range associated with a given card-table field includes the memory occupied by all objects that begin in the card associated with that card-table field.
3. A method as defined in claim 1 wherein the card range associated with a given card-table field is the card associated with that card-table field.
4. A method as defined in claim 1 wherein:
A) the scan determination is negative if the card-table field contains the current younger-generation-indicating value or the clean-indicating value; and
B) the garbage collector refrains from performing a range-scan reference-inspection operation on a card range for which the scan determination is negative.
5. A method as defined in claim 1 wherein the range-scan entry-update operation for a given card-table field includes, before the range-scan reference-inspection operation, an entry-initialization operation in which:
A) if the value of the given card-table field's contents is the current-younger-generation-and-non-clean-indicating value, those contents are changed to the current younger-generation-indicating value; and
B) the value of the given card-table field's contents is otherwise changed to the clean-indicating value.
6. A method as defined in claim 1 wherein:
A) the possible entry values include a dirty value, which the garbage collector interprets as a non-clean-indicating value; and
B) the mutator indicates where it has modified a reference by writing the dirty value into the card-table field with which the card range containing that reference is associated.
7. A method as defined in claim 1 wherein the range-scan entry-update operation places the clean-indicating value into a card-table field only by successfully performing an atomic update operation that includes atomically:
A) reading the contents of that card-table field to verify that it contains a previously determined non-clean-indicating value;
B) placing the clean-indicating value in that card-table field, and thereby being successful, only if the contents thereby read are the previously determined non-clean-indicating value; and
C) otherwise being unsuccessful by refraining from placing a value into that card-table field.
8. A method as defined in claim 7 wherein the object-scan entry-update operation places the current-younger-generation-and-non-clean-indicating value into a card-table field only by successfully performing an atomic update operation that includes atomically:
A) reading the contents of that card-table field to verify that it contains a previously determined non-clean-indicating value;
B) placing the current-younger-generation-and-non-clean-indicating value into that card-table field, and thereby being successful, only if the contents thereby read are the previously determined non-clean-indicating value; and
C) otherwise being unsuccessful by refraining from placing a value into that card-table field.
9. A method as defined in claim 8 wherein:
A) the scan determination is negative if the card-table field contains the current younger-generation-indicating value or the clean-indicating value; and
B) the garbage collector refrains from performing a range-scan reference-inspection operation on a card range for which the scan determination is negative.
10. A method as defined in claim 8 wherein the range-scan entry-update operation for a given card-table field includes, before the range-scan reference-inspection operation, an entry-initialization operation in which:
A) if the value of the given card-table field's contents is the current-younger-generation-and-non-clean-indicating value, those contents are changed to the current younger-generation-indicating value; and
B) the value of the given card-table field's contents is otherwise changed to the clean-indicating value.
11. A method as defined in claim 8 wherein:
A) the possible entry values include a dirty value, which the garbage collector interprets as a non-clean-indicating value; and
B) the mutator indicates where it has modified a reference by writing the dirty value into the card-table field with which the card range containing that reference is associated.
12. A method as defined in claim 7 wherein:
A) the scan determination is negative if the card-table field contains the current younger-generation-indicating value or the clean-indicating value; and
B) the garbage collector refrains from performing a range-scan reference-inspection operation on a card range for which the scan determination is negative.
13. A method as defined in claim 7 wherein the range-scan entry-update operation for a given card-table field includes, before the range-scan reference-inspection operation, an entry-initialization operation in which:
A) if the value of the given card-table field's contents is the current-younger-generation-and-non-clean-indicating value, those contents are changed to the current younger-generation-indicating value; and
B) the value of the given card-table field's contents is otherwise changed to the clean-indicating value.
14. A method as defined in claim 7 wherein:
A) the possible entry values include a dirty value, which the garbage collector interprets as a non-clean-indicating value; and
B) the mutator indicates where it has modified a reference by writing the dirty value into the card-table field with which the card range containing that reference is associated.
15. A method as defined in claim 1 wherein the object-scan entry-update operation places the current-younger-generation-and-non-clean-indicating value into a card-table field only by successfully performing an atomic update operation that includes atomically:
A) reading the contents of that card-table field to verify that it contains a previously determined non-clean-indicating value;
B) placing the current-younger-generation-and- -non-clean-indicating value into that card-table field, and thereby being successful, only if the contents thereby read are the previously determined non-clean-indicating value; and
C) otherwise being unsuccessful by refraining from placing a value into that card-table field.
16. A computer system comprising:
A) processor circuitry operable to execute processor instructions; and
B) memory circuitry, to which the processor circuitry is responsive, that includes a heap in which memory space is dynamically allocated and that contains processor instructions readable by the processor circuitry to configure the computer system as a mutator that modifies references in the heap and as a garbage collector that:
i) treats the heap as divided into a plurality of generations, including at least one young generation and at least one old generation;
ii) treats the old generation as divided into cards;
iii) maintains a card table, comprising a plurality of card-table fields of which each is associated with a respective card and card range, in which the mutator indicates where it has modified references, a value contained in each card-table field being one of a plurality of possible entry values that include at least one clean-indicating value, at least one non-clean-indicating value, at least one current-younger-generation-and-n-on-clean-indicating value, and a plurality are younger-generation-indicating values; and
iv) performs young-generation collections in each of which the garbage collector performs a reachable-object-identification operation, in which it identifies selected objects in the young generation, and reclaims memory space in the young generation not occupied by objects thus identified, the reachable-object-identification operation including performing in a plurality of garbage-collection threads an old-generation-scanning operation, in which the garbage collector identifies objects in the young generation referred to by old-generation references, the objects thus identified sometimes being promoted into the old generation and sometimes remaining in the young generation, the old-generation-scanning operation including:
a) adopting as the current younger-generation-indicating value for that young-generation collection one of the younger-generation-indicating values different from the younger-generation-indicating value adopted as the current younger-generation-indicating value in the previous old-generation-scanning operation;
b) adopting at least one other younger-generation-indicating value as the previous younger-generation-indicating value for that collection, the previous younger-generation-indicating value being interpreted as a non-clean-indicating value;
c) for each card-table field, employing a garbage-collection thread to perform an entry-processing operation in which that garbage-collection thread:
(1) makes a scan determination, based on the contents of that card-table field, of whether to perform a range-scanning operation on the card range associated with that card-table field, the determination being affirmative if that card-table field contains a non-clean-indicating value or the current-generation-and-non-clean-indicating value; and
(2) if the scan determination is affirmative, performs a range-scanning operation, in which:
(a) that garbage-collection thread performs a range-scan reference-inspection operation in which it scans the card range for references that are contained in objects not promoted during that young-generation collection and refer to objects in the young generation, whereby objects thus referred to are identified by the reachable-object-identification operation; and
(b) that garbage-collection thread performs a range-scan entry-update operation in which:
(i) the resultant value of that card-table field's contents is the current younger-generation-indicating value if any object thus identified is not promoted as a result; and
(ii) otherwise, the value of that card-table field's contents are changed either from a non-clean-indicating value to the clean-indicating value or from the current-younger-generation-and-non-clean-indicating value to the current younger-generation-indicating value; and
d) for each object promoted into the old generation during that young-generation collection, employing a garbage-collection thread to perform a promoted-object-scanning operation, in which that garbage-collection thread:
(1) scans that object for references that refer to objects in the young generation, whereby objects thus referred to are identified by the reachable-object-identification operation; and
(2) performs an object-scan entry-update operation, in which, for each reference in that object that refers to an object thus identified that is not promoted as a result:
(a) the value of the contents of the card-table field for the card range containing that reference becomes the current-younger-generation-and-non-clean-indicating value if that card-table field's immediately previous contents are a non-clean-indicating value; and
(b) otherwise, the resultant value of the contents of the card-table field for the card range containing that reference is the current younger-generation-indicating value.
17. A computer system as defined in claim 16 wherein:
A) the scan determination is negative if the card-table field contains the current younger-generation-indicating value or the clean-indicating value; and
B) the garbage collector refrains from performing a range-scan reference-inspection operation on a card range for which the scan determination is negative.
18. A computer system as defined in claim 16 wherein the range-scan entry-update operation for a given card-table field includes, before the range-scan reference-inspection operation, an entry-initialization operation in which:
A) if the value of the given card-table field's contents is the current-younger-generation-and-non-clean-indicating value, those contents are changed to the current younger-generation-indicating value; and
B) the value of the given card-table field's contents is otherwise changed to the clean-indicating value.
19. A computer system as defined in claim 16 wherein:
A) the possible entry values include a dirty value, which the garbage collector interprets as a non-clean-indicating value; and
B) the mutator indicates where it has modified a reference by writing the dirty value into the card-table field with which the card range containing that reference is associated.
20. A computer system as defined in claim 16 wherein the range-scan entry-update operation places the clean-indicating value into a card-table field only by successfully performing an atomic update operation that includes atomically:
A) reading the contents of that card-table field to verify that it contains a previously determined non-clean-indicating value;
B) placing the clean-indicating value in that card-table field, and thereby being successful, only if the contents thereby read are the previously determined non-clean-indicating value; and
C) otherwise being unsuccessful by refraining from placing a value into that card-table field.
21. A computer system as defined in claim 20 wherein the object-scan entry-update operation places the current-younger-generation-and-non-clean-indicating value into a card-table field only by successfully performing an atomic update operation that includes atomically:
A) reading the contents of that card-table field to verify that it contains a previously determined non-clean-indicating value;
B) placing the current-younger-generation-and-non-clean-indicating value into that card-table field, and thereby being successful, only if the contents thereby read are the previously determined non-clean-indicating value; and
C) otherwise being unsuccessful by refraining from placing a value into that card-table field.
22. A computer system as defined in claim 21 wherein:
A) the scan determination is negative if the card-table field contains the current younger-generation-indicating value or the clean-indicating value; and
B) the garbage collector refrains from performing a range-scan reference-inspection operation on a card range for which the scan determination is negative.
23. A computer system as defined in claim 21 wherein the range-scan entry-update operation for a given card-table field includes, before the range-scan reference-inspection operation, an entry-initialization operation in which:
A) if the value of the given card-table field's contents is the current-younger-generation-and-non-clean-indicating value, those contents are changed to the current younger-generation-indicating value; and
B) the value of the given card-table field's contents is otherwise changed to 8 the clean-indicating value.
24. A computer system as defined in claim 21 wherein:
A) the possible entry values include a dirty value, which the garbage collector interprets as a non-clean-indicating value; and
B) the mutator indicates where it has modified a reference by writing the dirty value into the card-table field with which the card range containing that reference is associated.
25. A computer system as defined in claim 20 wherein:
A) the scan determination is negative if the card-table field contains the current younger-generation-indicating value or the clean-indicating value; and
B) the garbage collector refrains from performing a range-scan reference-inspection operation on a card range for which the scan determination is negative.
26. A computer system as defined in claim 20 wherein the range-scan entry-update operation for a given card-table field includes, before the range-scan reference-inspection operation, an entry-initialization operation in which:
A) if the value of the given card-table field's contents is the current-younger-generation-and-non-clean-indicating value, those contents are changed to the current younger-generation-indicating value; and
B) the value of the given card-table field's contents is otherwise changed to the clean-indicating value.
27. A computer system as defined in claim 20 wherein:
A) the possible entry values include a dirty value, which the garbage collector interprets as a non-clean-indicating value; and
B) the mutator indicates where it has modified a reference by writing the dirty value into the card-table field with which the card range containing that reference is associated.
28. A computer system as defined in claim 16 wherein the object-scan entry-update operation places the current-younger-generation-and-non-clean-indicating value into a card-table field only by successfully performing an atomic update operation that includes atomically:
A) reading the contents of that card-table field to verify that it contains a previously determined non-clean-indicating value;
B) placing the current-younger-generation-and-non-clean-indicating value into that card-table field, and thereby being successful, only if the contents thereby read are the previously determined non-clean-indicating value; and
C) otherwise being unsuccessful by refraining from placing a value into that card-table field.
29. A storage medium containing instructions readable, by a computer system that includes memory including a heap in which space is dynamically allocated to a mutator that modifies references therein, to configure the computer system to operate as a garbage collector that:
A) treats the heap as divided into a plurality of generations, including at least one young generation and at least one old generation;
B) treats the old generation as divided into cards;
C) maintains a card table, comprising a plurality of card-table fields of which each is associated with a respective card and card range, in which the mutator indicates where it has modified references, the a value contained in each card-table field being one of a plurality of possible entry values that include at least one clean-indicating value, at least one non-clean-indicating value, at least one current-younger-generation-and-non-clean-indicating value, and a plurality are younger-generation-indicating values; and
D) performs young-generation collections in each of which the garbage collector performs a reachable-object-identification operation, in which it identifies selected objects in the young generation, and reclaims memory space in the young generation not occupied by objects thus identified, the reachable-object-identification operation including performing in a plurality of garbage-collection threads an old-generation-scanning operation, in which the garbage collector identifies objects in the young generation referred to by old-generation references, the objects thus identified sometimes being promoted into the old generation and sometimes remaining in the young generation, the old-generation-scanning operation including:
i) adopting as the current younger-generation-indicating value for that young-generation collection one of the younger-generation-indicating values different from the younger-generation-indicating value adopted as the current younger-generation-indicating value in the previous old-generation-scanning operation;
ii) adopting at least one other younger-generation-indicating value as the previous younger-generation-indicating value for that collection, the previous younger-generation-indicating value being interpreted as a non-clean-indicating value;
iii) for each card-table field, employing a garbage-collection thread to perform an entry-processing operation in which that garbage-collection thread:
a) makes a scan determination, based on the contents of that card-table field, of whether to perform a range-scanning operation on the card range associated with that card-table field, the determination being affirmative if that card-table field contains a non-clean-indicating value or the current-generation-and-non-clean-indicating value; and
b) if the scan determination is affirmative, performs a range-scanning operation, in which:
(1) that garbage-collection thread performs a range-scan reference-inspection operation in which it scans the card range for references that are contained in objects not promoted during that young-generation collection and refer to objects in the young generation, whereby objects thus referred to are identified by the reachable-object-identification operation; and
(2) that garbage-collection thread performs a range-scan entry-update operation in which:
(a) the resultant value of that card-table field's contents is the current younger-generation-indicating value if any object thus identified is not promoted as a result; and
(b) otherwise, the value of that card-table field's contents are changed either from a non-clean-indicating value to the clean-indicating value or from the current-younger-generation-and-non-clean indicating value to the current younger-generation-indicating value; and
iv) for each object promoted into the old generation during that young-generation collection, employing a garbage-collection thread to perform a promoted-object-scanning operation, in which that garbage-collection thread:
a) scans that object for references that refer to objects in the young generation, whereby objects thus referred to are identified as potentially reachable by the reachable-object-identification operation; and
b) performs an object-scan entry-update operation, in which, for each reference in that object that refers to an object thus identified that is not promoted as a result:
(1) the value of the contents of the card-table field for the card range containing that reference becomes the current-younger-generation-and-non-clean-indicating value if that card-table field's immediately previous contents are a non-clean-indicating value; and
(2) otherwise, the resultant value of the contents of the card-table field for the card range containing that reference is the current younger-generation-indicating value.
30. A storage medium as defined in claim 29 wherein:
A) the scan determination is negative if the card-table field contains the current younger-generation-indicating value or the clean-indicating value; and
B) the garbage collector refrains from performing a range-scan reference-inspection operation on a card range for which the scan determination is negative.
31. A storage medium as defined in claim 29 wherein the range-scan entry-update operation for a given card-table field includes, before the range-scan reference-inspection operation, an entry-initialization operation in which:
A) if the value of the given card-table field's contents is the current-younger-generation-and-non-clean-indicating value, those contents are changed to the current younger-generation-indicating value; and
B) the value of the given card-table field's contents is otherwise changed to the clean-indicating value.
32. A storage medium as defined in claim 29 wherein:
A) the possible entry values include a dirty value, which the garbage collector interprets as a non-clean-indicating value; and
B) the mutator indicates where it has modified a reference by writing the dirty value into the card-table field with which the card range containing that reference is associated.
33. A storage medium as defined in claim 29 wherein the range-scan entry-update operation places the clean-indicating value into a card-table field only by successfully performing an atomic update operation that includes atomically:
A) reading the contents of that card-table field to verify that it contains a previously determined non-clean-indicating value;
B) placing the clean-indicating value in that card-table field, and thereby being successful, only if the contents thereby read are the previously determined non-clean-indicating value; and
C) otherwise being unsuccessful by refraining from placing a value into that card-table field.
34. A storage medium as defined in claim 33 wherein the object-scan entry-update operation places the current-younger-generation-and-non-clean-indicating value into a card-table field only by successfully performing an atomicupdate operation that includes atomically:
A) reading the contents of that card-table field to verify that it contains a previously determined non-clean-indicating value;
B) placing the current-younger-generation-and-non-clean-indicating value into that card-table field, and thereby being successful, only if the contents thereby read are the previously determined non-clean-indicating value; and
C) otherwise being unsuccessful by refraining from placing a value into that card-table field.
35. A storage medium as defined in claim 34 wherein:
A) the scan determination is negative if the card-table field contains the current younger-generation-indicating value or the clean-indicating value; and
B) the garbage collector refrains from performing a range-scan reference-inspection operation on a card range for which the scan determination is negative.
36. A storage medium as defined in claim 34 wherein the range-scan entry-update operation for a given card-table field includes, before the range-scan reference-inspection operation, an entry-initialization operation in which:
A) if the value of the given card-table field's contents is the current-younger-generation-and-non-clean-indicating value, those contents are changed to the current younger-generation-indicating value; and
B) the value of the given card-table field's contents is otherwise changed to the clean-indicating value.
37. A storage medium as defined in claim 34 wherein:
A) the possible entry values include a dirty value, which the garbage collector interprets as a non-clean-indicating value; and
B) the mutator indicates where it has modified a reference by writing the dirty value into the card-table field with which the card range containing that reference is associated.
38. A storage medium as defined in claim 33 wherein:
A) the scan determination is negative if the card-table field contains the current younger-generation-indicating value or the clean-indicating value; and
B) the garbage collector refrains from performing a range-scan reference-inspection operation on a card range for which the scan determination is negative.
39. A storage medium as defined in claim 33 wherein the range-scan entry-update operation for a given card-table field includes, before the range-scan reference-inspection operation, an entry-initialization operation in which:
A) if the value of the given card-table field's contents is the current-younger-generation-and-non-clean-indicating value, those contents are changed to the current younger-generation-indicating value; and
B) the value of the given card-table field's contents is otherwise changed to the clean-indicating value.
40. A storage medium as defined in claim 33 wherein:
A) the possible entry values include a dirty value, which the garbage collector interprets as a non-clean-indicating value; and
B) the mutator indicates where it has modified a reference by writing the dirty value into the card-table field with which the card range containing that reference is associated.
41. A storage medium as defined in claim 29 wherein the object-scan entry-update operation places the current-younger-generation-and-non-clean-indicating value into a card-table field only by successfully performing an atomic update operation that includes atomically:
A) reading the contents of that card-table field to verify that it contains a previously determined non-clean-indicating value;
B) placing the current-younger-generation-and-non-clean-indicating value into that card-table field, and thereby being successful, only if the contents thereby read are the previously determined non-clean-indicating value; and
C) otherwise being unsuccessful by refraining from placing a value into that card-table field.
42. For reclaiming memory in a dynamically allocated heap in which a mutator modifies references, a garbage collector comprising:
A) means for treating the heap as divided into a plurality of generations, including at least one young generation and at least one old generation;
B) means for treating the old generation as divided into cards;
C) means for maintaining a card table, comprising a plurality of card-table fields of which each is associated with a respective card and card range, in which the mutator indicates where it has modified references, a value contained in each card-table field being one of a plurality of possible entry values that include at least one clean-indicating value, at least one non-clean-indicating value, at least one current-younger-generation-and-non-clean-indicating value, and a plurality are younger-generation-indicating values; and
D) means for performing young-generation collections in each of which the garbage collector performs a reachable-object-identification operation, in which it identifies selected objects in the young generation, and reclaims memory space in the young generation not occupied by objects thus identified, the reachable-object-identification operation including performing in a plurality of garbage-collection threads an old-generation-scanning operation, in which the garbage collector identifies objects in the young-generation referred to by old-generation references, the objects thus identified sometimes being promoted into the old generation and sometimes remaining in the young generation, the old-generation-scanning operation including:
i) adopting as the current younger-generation-indicating value for that young-generation collection one of the younger-generation-indicating values different from the younger-generation-indicating value adopted as the current younger-generation-indicating value in the previous old-generation-scanning operation;
ii) adopting at least one other younger-generation-indicating value as the previous younger-generation-indicating value for that collection, the previous younger-generation-indicating value being interpreted as a non-clean-indicating value;
iii) for each card-table field, employing a garbage-collection thread to perform an entry-processing operation in which that garbage-collection thread:
a) makes a scan determination, based on the contents of that card-table field, of whether to perform a range-scanning operation on the card range associated with that card-table field, the determination being affirmative if that card-table field contains a non-clean-indicating value or the current-generation-and-non-clean-indicating value; and
b) if the scan determination is affirmative, performs a range-scanning operation, in which:
(1) that garbage-collection thread performs a range-scan reference-inspection operation in which it scans the card range for references that are contained in objects not promoted during that young-generation collection and refer to objects in the young generation, whereby objects thus referred to are identified by the reachable-object-identification operation; and
(2) that garbage-collection thread performs a range-scan entry-update operation in which:
(a) the resultant value of that card-table field's contents is the current younger-generation-indicating value if any object thus identified is not promoted as a result; and
(b) otherwise, the value of that card-table field's contents are changed either from a non-clean-indicating value to the clean-indicating value or from the current-younger-generation-and-non-clean indicating value to the current younger-generation-indicating value; and
iv) for each object promoted into the old generation during that young-generation collection, employing a garbage-collection thread to perform a promoted-object-scanning operation, in which that garbage-collection thread:
a) scans that object for references that refer to objects in the young generation, whereby objects thus referred to are identified by the reachable-object-identification operation; and
b) performs an object-scan entry-update operation, in which, for each reference in that object that refers to an object thus identified that is not promoted as a result:
(1) the value of the contents of the card-table field for the card range containing that reference becomes the current-younger-generation-and-non-clean-indicating value if that card-table field's immediately previous contents are a non-clean-indicating value; and
(2) otherwise, the resultant value of the contents of the card-table field for the card range containing that reference is the current younger-generation-indicating value.