US 2004/0111446 A1Published application

Combining entries in a card object table

AssigneeSun Microsystems, Inc.

InventorAlexander T. Garthwaite

Life of this patent

Estimating the term…

Loading patent…

Abstract

A garbage collector divides the garbage-collected heap into “cards.” It maintains a table containing a card-object table entry for each card. A card's entry contains information from which the collector can determine where any references in the card are located and thereby identify objects that may be reachable. Specifically, although each entry is smaller than a memory address, it has enough possible values to give the relative location of the object in which the associated card begins or to direct the collector to another entry for that information. But the entries are additionally grouped into sequences of contiguous entries that together are large enough to contain a complete address. When every card associated with a entry in a given (address-sized) entry sequence begins in the same object, that entry sequence is together given a value that the collector can recognize as indicating that object's absolute location.

Claims35

Dependent claims

For operating a computer system including memory as a garbage collector, a method comprising:

A) providing a computer system that includes memory;
B) configuring the computer system to operate as a garbage collector that:
i) treats at least a portion of a garbage-collected heap in the memory as divided into cards with which the garbage collector associates respective card-object-table entries;
ii) maintains the card-object-table entries;
iii) determines whether a multiple-card-object-table-entry sequence that includes the card-object-table entry with which a given card is associated satisfies a predetermined common-object criterion;
iv) if that multiple-card-object-table-entry sequence is thereby determined to satisfy the common-object criterion, interprets that multiple-card-object-entry sequence as an indicator of the location at which is located a predetermined field of an object in which a predetermined location in the given card is located;
V) if that multiple-card-object-table-entry sequence is thereby determined not to satisfy the common-object criterion, interprets the card-object-table entry with which the given card is associated as locator information maintained by the collector for the given card;
vi) bases on that interpretation a determination of which locations in the card contain references;
vii) determines the reachability of objects from the contents of locations thereby determined to be references;
and
viii) reclaims memory space occupied by objects thereby determined not to be potentially reachable;
and
C) causing the computer system to operate as the garbage collector as which it is thereby configured.

10 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 to operate as a garbage collector that:
i) treats at least a portion of a garbage-collected heap in the memory as divided into cards with which the garbage collector associates respective card-object-table entries;
ii) maintains the card-object-table entries;
iii) determines whether a multiple-card-object-table-entry sequence that includes the card-object-table entry with which a given card is associated satisfies a predetermined common-object criterion;
iv) if that multiple-card-object-table-entry sequence is thereby determined to satisfy the common-object criterion, interprets that multiple-card-object-entry sequence as an indicator of the location at which is located a predetermined field of an object in which a predetermined location in the given card is located;
V) if that multiple-card-object-table-entry sequence is thereby determined not to satisfy the common-object criterion, interprets the card-object-table entry with which the given card is associated as locator information maintained by the collector for the given card;
vi) bases on that interpretation a determination of which locations in the card contain references;
vii) determines the reachability of objects from the contents of locations thereby determined to be references;
and
C) reclaims memory space occupied by objects thereby determined not to be potentially reachable.

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:

A) treats at least a portion of a garbage-collected heap in the memory as divided into cards with which the garbage collector associates respective card-object-table entries;
B) maintains the card-object-table entries;
C) determines whether a multiple-card-object-table-entry sequence that includes the card-object-table entry with which a given card is associated satisfies a predetermined common-object criterion;
D) if that multiple-card-object-table-entry sequence is thereby determined to satisfy the common-object criterion, interprets that multiple-card-object-entry sequence as an indicator of the location at which is located a predetermined field of an object in which a predetermined location in the given card is located;
E) if that multiple-card-object-table-entry sequence is thereby determined not to satisfy the common-object criterion, interprets the card-object-table entry with which the given card is associated as locator information maintained by the collector for the given card;
F) bases on that interpretation a determination of which locations in the card contain references;
G) determines the reachability of objects from the contents of locations thereby determined to be references;
and
H) reclaims memory space occupied by objects thereby determined not to be potentially reachable.

6 more elements

An electromagnetic signal representing sequences of instructions that, when executed by a computer system that includes memory, cause it to operate as a garbage collector that:

A) treats at least a portion of a garbage-collected heap in the memory as divided into cards with which the garbage collector associates respective card-object-table entries;
B) maintains the card-object-table entries;
C) determines whether a multiple-card-object-table-entry sequence that includes the card-object-table entry with which a given card is associated satisfies a predetermined common-object criterion;
D) if that multiple-card-object-table-entry sequence is thereby determined to satisfy the common-object criterion, interprets that multiple-card-object-entry sequence as an indicator of the location at which is located a predetermined field of an object in which a predetermined location in the given card is located;
E) if that multiple-card-object-table-entry sequence is thereby determined not to satisfy the common-object criterion, interprets the card-object-table entry with which the given card is associated as locator information maintained by the collector for the given card;
F) bases on that interpretation a determination of which locations in the card contain references;
G) determines the reachability of objects from the contents of locations thereby determined to be references;
and
H) reclaims memory space occupied by objects thereby determined not to be potentially reachable.

6 more elements

Dependencies are inferred from the claim text.