US 5,848,423 A · Garbage collection system and method for locating root set pointers in method activation records

Abstract

In an object oriented computer system, a root set of object references includes object references stored in the computer system's registers, as well as object references stored in activation records in the program stack. Whenever a method is invoked, a corresponding activation record is stored on the program stack. The activation record includes the invocation address for the method called as well as parameters passed to the called method. A class loader, which loads object classes into memory, determines the locations of the object references in the activation records associated with each method in a loaded object class. A list of offset values for each method activation record is stored by the class loader in a hash table data structure at a location in the hash table data structure determined by hashing the unique invocation address assigned to the method. At the beginning of each garbage collection cycle, a root set locator procedure processes each activation record in the program stack by applying a hash function to the invocation address in the activation record to determine where in the hash table data structure to locate the object reference offsets for that activation record. Using the located object reference offsets, each of the object references in the activation record is added to a root set list. The number of processor cycles required to locate and copy all the object references in activation records in the program stack is a linear function of the number of such object references.

Claims16

Dependent claims

A method of operating a computer system so as to efficiently locate root set object references for garbage collection of inaccessible objects in the computer system's memory, comprising the steps of:

loading an object class having a plurality of methods into the computer system's memory;
each method of the loaded object class having an associated activation record;
an instance of which is stored on a program stack in the each method's activation record including a unique identifier associated with the method and zero or more parameters, each of the parameters having an associated data type and location in the activation record that is defined by the loaded object class;
wherein a subset of the parameters in the activation records for the methods in the loaded object class are object references having an object reference data type;
while performing the loading step,
associating each method in the loaded class file with an entry in a table;
and
storing in the table data for each method in the loaded class file, at the associated entry for the method, the stored data indicating where each of the object references, if any, are located in the activation record for the method;
executing a mutator task that stores objects in the computer system's memory;
storing on a program stack an instance of the activation record for each method invoked by the mutator task;
and
performing garbage collection on objects in memory, including scanning the activation records stored in the program stack to identify object references therein, including processing each activation record in the program stack by:
locating the entry in the table that corresponds to the activation record being processed;
and
identifying each of the object references in the activation record being processed in accordance with the data stored in the located table entry, whereby objects stored in memory are efficiently identified from parameters in the activation records stored in the program stack.

12 more elements

A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a class loader procedure that loads an object class having a plurality of methods into the computer system's memory;
each method of the loaded object class having an associated activation record;
each method's activation record including a unique identifier associated with the method and zero or more parameters, each of the parameters having an associated data type and location in the activation record that is defined by the loaded object class;
wherein a subset of the parameters in the activation records for the methods in the loaded object class are object references having an object reference data type;
the class loader procedure including:
instructions for associating each method in the loaded class file with an entry in a table;
and
instructions for storing in the table data for each method in the loaded class file, at the associated entry for the method, the stored data indicating where each of the object references, if any, are located in the activation record for the method;
a mutator task that stores objects in the computer system's memory;
an operating system that includes instructions for storing activation records in the program stack, including an activation record for each method invoked by the mutator task;
and
a garbage collection procedure that processes the activation records stored in the program stack to identify object references therein, the garbage collection procedure including a root set locator procedure that includes:
instructions for locating the entry in the table that corresponds to the activation record being processed;
and
instructions for identifying each of the object references in the activation record being processed in accordance with the data stored in the located table entry;
whereby objects stored in memory are efficiently identified from parameters in the activation records stored in the program stack.

13 more elements

A method of operating a computer system so as to efficiently locate root set object references during garbage collection of inaccessible objects in the computer system's memory, comprising the steps of:

loading methods or procedures into the computer system's memory;
each method or procedure having an associated activation record;
each method or procedure's activation record including a unique identifier associated with the method or procedure and zero or more parameters, each of the parameters having an associated data type and location in the activation record;
wherein a subset of the parameters in the activation records for the loaded methods and/or procedures are object references having an object reference data type;
while performing the loading step,
associating each loaded method or procedure with an entry in a table;
and
storing in the table data for each loaded method or procedure, at the associated entry for the method or procedure, the stored data indicating where each of the object references, if any, are located in the activation record for the method or procedure;
executing a mutator task that stores objects in the computer system's memory;
storing on a program stack an instance of the activation record for each method or procedure invoked by the mutator task;
and
performing garbage collection on objects in memory, including scanning the activation records stored in the program stack to identify object references therein, including processing each activation record in the program stack by:
locating the entry in the table that corresponds to the activation record being processed;
and
identifying each of the object references in the activation record being processed in accordance with the data stored in the located table entry, whereby objects stored in memory are efficiently identified from parameters in the activation records stored in the program stack.

12 more elements

a loader/linker procedure that loads/links methods or procedures into the computer system's memory;
each loaded method or procedure having an associated activation record;
each method or procedure's activation record including a unique identifier associated with the method or procedure and zero or more parameters, each of the parameters having an associated data type and location in the activation record;
wherein a subset of the parameters in the activation records for the loaded methods and/or procedures are object references having an object reference data type;
the loader/linker procedure including:
instructions for associating each loaded method or procedure with an entry in a table;
and
instructions for storing in the table data for each loaded method or procedure, at the associated entry for the method or procedure, the stored data indicating where each of the object references, if any, are located in the activation record for the method or procedure;
a mutator task that stores objects in the computer system's memory;
an operating system that includes instructions for storing activation records in the program stack, including an activation record for each method or procedure invoked by the mutator task;
and
a garbage collection procedure that processes the activation records stored in the program stack to identify object references therein, the garbage collection procedure including a root set locator procedure that includes:
instructions for locating the entry in the table that corresponds to the activation record being processed;
and
instructions for identifying each of the object references in the activation record being processed in accordance with the data stored in the located table entry;
whereby objects stored in memory are efficiently identified from parameters in the activation records stored in the program stack.

13 more elements

Dependencies are inferred from the claim text.

Garbage collection system and method for locating root set pointers in method activation records

Life of this patent

Garbage collection system and method for locating root set pointers in method activation records

Life of this patent

Abstract

Claims16