US 7,069,281 B2 · Efficient collocation of evacuated objects in a copying garbage collector using variably filled local allocation buffers

Abstract

A copying garbage collector evacuates to a to space the objects in a from space that are referred to by references, including references in previously evacuated objects, that are located outside the from space. It divides the to space into local-allocation buffers (“LABs”), and it adopts one of these as a destination LAB, i.e., as the LAB into which it places the objects that it evacuates. When a destination LAB becomes full, the thread adopts a new LAB as its destination LAB. When a destination LAB's contents fill it to some predetermined fill threshold, that destination LAB becomes the source LAB, i.e., the LAB that the collector scans for references to the collection-set objects. If a previous source LAB's contents has not yet been completely scanned when the collector thus adopts a new source LAB, the previous source LAB is placed on a LAB stack. When no more references to unevacuated collection-set objects remain in its current source LAB, the collector then pops a LAB from its LAB stack on a last-in, first-out basis and adopts that LAB as the source LAB.

Claims42

Dependent claims

For operating a computer system that includes a memory as a garbage collector that reclaims space in the memory occupied by unreachable objects, method comprising:

A) dividing a to space of the memory into local allocation buffers (LABs) with which respective fill thresholds are associated, the fill thresholds of at least some LABs being less than those LABs' capacities and greater than empty;
B) adopting one said LAB at a time as a destination LAB and one said LAB at a time as a source LAB;
C) performing an evacuation operation that includes repeatedly evacuating into the destination lab objects in a from space of the memory referred to by references in the source lab while:
i) if the destination LAB becomes full, replacing that LAB with a new LAB as the destination LAB;
ii) monitoring the level to which the destination LAB has been filled to determine when it reaches the destination LAB's fill threshold and, if the destination LAB is not already the source LAB when the level reaches the destination LAB's fill threshold:
a) placing the source LAB on a LAB stack if the source LAB contains references to from-space objects that have not yet been evacuated;
and
b) adopting the destination LAB as the source LAB;
and
iii) if the source LAB is the destination LAB, no reference in the source LAB refers to an object in the from space that has not yet been evacuated, and at least one LAB remains on the LAB stack, adopting as the source LAB the last LAB added to the LAB stack;
and
D) reclaiming the from space.

9 more elements

For operating a computer system that includes a memory as a garbage collector that executes in a plurality of threads to reclaim space in the memory occupied by unreachable objects, method comprising:

A) dividing a to space of the memory into local allocation buffers (LABs) with which respective fill thresholds are associated;
B) employing each thread to:
i) adopt one said LAB at a time as that thread's destination LAB and one said LAB at a time as that thread's source LAB;
and
ii) perform an evacuation operation that includes repeatedly evacuating into the destination LAB objects in a from space of the memory referred to by references in the source LAB while:
a) if that thread's destination LAB becomes full, replacing that LAB with a new LAB as that thread's destination LAB;
b) monitoring the level to which the destination LAB has been filled to determine when it reaches the destination LAB's fill threshold and, if the destination LAB is not already the source LAB when the level reaches the destination LAB's fill threshold:
(1) placing the source LAB on a LAB stack if the source LAB contains references to from-space objects that have not yet been evacuated;
and
(2) adopting the destination LAB as the source LAB;
and
c) if that thread's source LAB is its destination LAB and no reference in its source LAB refers to an object in the from space that has not yet been evacuated:
(1) if at least one LAB remains on its LAB stack, adopting as the source LAB a LAB on its LAB stack;
and
(2) if no LAB remains on its LAB stack and a LAB is available on the LAB stack of another said thread, adopting as that thread's source LAB a LAB on that other thread's LAB stack;
and
C) reclaiming the from space.

14 more elements

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 the computer system as a garbage collector that reclaims space in the memory occupied by unreachable objects by:
i) dividing a to space of the memory into local allocation buffers (LABs) with which respective fill thresholds are associated, the fill thresholds of at least some LABs being less than those LABs' capacities and greater than empty;
ii) adopting one said LAB at a time as a destination LAB and one said LAB at a time as a source LAB;
iii) performing an evacuation operation that includes repeatedly evacuating into the destination LAB objects in a from space of the memory referred to by references in the source LAB while:
a) if the destination LAB becomes full, replacing that LAB with a new LAB as the destination LAB;
b) monitoring the level to which the destination LAB has been filled to determine when it reaches the destination LAB's fill threshold and, if the destination LAB is not already the source LAB when the level reaches the destination LAB's fill threshold:
(1) placing the source LAB on a LAB stack if the source LAB contains references to from-space objects that have not yet been evacuated;
and
(2) adopting the destination LAB as the source LAB;
and
c) if the source LAB is the destination LAB, no reference in the source LAB refers to an object in the from space that has not yet been evacuated, and at least one LAB remains on the LAB stack, adopting as the source LAB the last LAB added to the LAB stack;
and iv) reclaiming the from space.

11 more elements

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 the computer system as a garbage collector that executes in a plurality of threads to reclaim space in the memory occupied by unreachable objects by:
i) dividing a to space of the memory into local allocation buffers (LABs) with which respective fill thresholds are associated;
ii) employing each thread to:
a) adopt one said LAB at a time as that thread's destination LAB and one said LAB at a time as that thread's source LAB;
and
b) perform an evacuation operation that includes repeatedly evacuating into the destination LAB objects in a from space of the memory referred to by references in the source LAB while:
(1) if that thread's destination LAB becomes full, replacing that LAB with a new LAB as that thread's destination LAB;
(2) monitoring the level to which the destination LAB has been filled to determine when it reaches the destination LAB's fill threshold and, if the destination LAB is not already the source LAB when the level reaches the destination LAB's fill threshold:
(a) placing the source LAB on a LAB stack if the source LAB contains references to from-space objects that have not yet been evacuated;
and
(b) adopting the destination LAB as the source LAB;
and
(3) if that thread's source LAB is its destination LAB and no reference in its source LAB refers to an object in the from space that has not yet been evacuated:
(a) if at least one LAB remains on its LAB stack, adopting as the source LAB a LAB on its LAB stack;
and
(b) if no LAB remains on its LAB stack and a LAB is available on the LAB stack of another said thread, adopting as that thread's source LAB a LAB on that other thread's LAB stack;
and
iii) reclaiming the from space.

17 more elements

A storage medium containing instructions readable by a computer system that includes memory to configure the computer system to operate as a garbage collector that reclaims space in the memory occupied by unreachable objects by:

A) dividing a to space of the memory into local allocation buffers (LABs) with which respective fill thresholds are associated, the fill thresholds of at least some LABs being less than those LABs' capacities and greater than empty;
B) adopting one said LAB at a time as a destination LAB and one said LAB at a time as a source LAB;
C) performing an evacuation operation that includes repeatedly evacuating into the destination LAB objects in a from space of the memory referred to by references in the source LAB while:
i) if the destination LAB becomes full, replacing that LAB with a new LAB as the destination LAB;
ii) monitoring the level to which the destination LAB has been filled to determine when it reaches the destination LAB's fill threshold and, if the destination LAB is not already the source LAB when the level reaches the destination LAB's fill threshold:
a) placing the source LAB on a LAB stack if the source LAB contains references to from-space objects that have not yet been evacuated;
and
b) adopting the destination LAB as the source LAB;
and
iii) if the source LAB is the destination LAB, no reference in the source LAB refers to an object in the from space that has not yet been evacuated, and at least one LAB remains on the LAB stack, adopting as the source LAB the last LAB added to the LAB stack;
and
D) reclaiming the from space.

9 more elements

A storage medium containing instructions readable by a computer system that includes memory to configure the computer system to operate as a garbage collector that executes in a plurality of threads to reclaim space in the memory occupied by unreachable objects by:

A) dividing a to space of the memory into local allocation buffers (LABs) with which respective fill thresholds are associated;
B) employing each thread to:
i) adopt one said LAB at a time as that thread's destination LAB and one said LAB at a time as that thread's source LAB;
and
ii) perform an evacuation operation that includes repeatedly evacuating into the destination LAB objects in a from space of the memory referred to by references in the source LAB while:
a) if that thread's destination LAB becomes full, replacing that LAB with a new LAB as that thread's destination LAB;
b) monitoring the level to which the destination LAB has been filled to determine when it reaches the destination LAB's fill threshold and, if the destination LAB is not already the source LAB when the level reaches the destination LAB's fill threshold:
(1) placing the source LAB on a LAB stack if the source LAB contains references to from-space objects that have not yet been evacuated;
and
(2) adopting the destination LAB as the source LAB;
and
c) if that thread's source LAB is its destination LAB and no reference in its source LAB refers to an object in the from space that has not yet been evacuated:
(1) if at least one LAB remains on its LAB stack, adopting as the source LAB a LAB on its LAB stack;
and
(2) if no LAB remains on its LAB stack and a LAB is available on the LAB stack of another said thread, adopting as that thread's source LAB a LAB on that other thread's LAB stack;
and
C) reclaiming the from space.

14 more elements

Dependencies are inferred from the claim text.

Efficient collocation of evacuated objects in a copying garbage collector using variably filled local allocation buffers

Life of this patent

Efficient collocation of evacuated objects in a copying garbage collector using variably filled local allocation buffers

Life of this patent

Abstract

Claims42