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

Claim 3

The method of claim 1, wherein the unique identifier associated with each method is a unique invocation address assigned to the method when the method is loaded into memory; the step of associating a method with a table entry comprises applying a hash function to the method's invocation address so as to generate a value indicative of the table entry; and the entry locating step comprises applying the hash function to the invocation address in the activation record being processed so as to generate a value indicative of the table entry corresponding to the activation record being processed.

Claim 4

The method of claim 1, further characterized by: each activation record including a back pointer to a previous activation record, if any, stored on the program stack; the activation record processing step including jumping to the previous activation record pointed to by the back pointer in the activation record after identifying the object references in the activation record being processed; whereby portions of the activation records in the program stack that do not store object references are skipped during the step of scanning the activation records stored in the program stack.

Claim 5

The method of claim 3, further characterized by: the table comprising a two level data structure including a hash table and an offset values table, each utilized entry in the hash table storing (A) data uniquely identifying a corresponding method, and (B) a pointer to a portion of the offset values table; the offset values table storing offset values indicative of the locations of the object references in the activation records associated with the methods loaded into memory; the step of associating a method with a table entry including locating an unused entry in the hash, locating an unused portion of the offset values table, and storing in the located hash table entry a pointer to the located portion of the offset values table; and the data storing step including storing in the located hash table entry a datum uniquely identifying the method associated with the located hash table entry, and storing in the located portion of the offset values table the data indicating where each of the object references, if any, are located in the activation record for the method.

Claim 6

The method of claim 4, the step of associating a method with a table entry including, when the activation record for the method does not include any object references, skipping the steps of locating an unused portion of the offset values table and storing in the located hash table entry a pointer to the located portion of the offset values table; and the data storing step including, when the activation record for the method does not include any object references, skipping the step of storing data in the located portion of the offset values table.

Claim 7

The method of claim 1, the activation records storing step including, storing as part of each activation record under direct hardware control a return address value, a pointer to a previous activation record, if any, and a method invocation address for the method associated with the activation record.

Claim 8

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.

Claim 9

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.

Claim 10

The computer program product of claim 7, wherein the unique identifier associated with each method is a unique invocation address assigned to the method when the method is loaded into memory; the table entry associating instructions comprise instructions for applying a hash function to the method's invocation address so as to generate a value indicative of the table entry; and the table entry locating instructions comprises instructions for applying the hash function to the invocation address in the activation record being processed so as to generate a value indicative of the table entry corresponding to the activation record being processed.

Claim 11

The computer program product of claim 7, further characterized by: each activation record including a back pointer to a previous activation record, if any, stored on the program stack; the garbage collection procedure including instructions for jumping to the previous activation record pointed to by the back pointer in the activation record after identifying the object references in the activation record being processed; whereby portions of the activation records in the program stack that do not store object references are skipped by the root set locator procedure.

Claim 12

The computer program product of claim 9, further characterized by: the table comprising a two level data structure including a hash table and an offset values table, each utilized entry in the hash table storing (A) data uniquely identifying a corresponding method, and (B) a pointer to a portion of the offset values table; the offset values table storing offset values indicative of the locations of the object references in the activation records associated with the methods loaded into memory; the table entry associating instructions comprising instructions for locating an unused entry in the hash, locating an unused portion of the offset values table, and storing in the located hash table entry a pointer to the located portion of the offset values table; and the table entry data storing instructions comprising instructions for storing in the located hash table entry a datum uniquely identifying the method associated with the located hash table entry, and storing in the located portion of the offset values table the data indicating where each of the object references, if any, are located in the activation record for the method.

Claim 13

The computer program product of claim 10, the table entry associating instructions including instructions for not locating an unused portion of the offset values table and not storing in the located hash table entry a pointer to the located portion of the offset values table when the activation record for the method does not include any object references; and the table entry data storing instruction including instructions for not storing data in the located portion of the offset values table when the activation record for the method does not include any object references.

Claim 14

The computer program product of claim 7, the data processor including instruction execution logic for executing method invocation instructions, the instruction execution logic including hardware logic for storing as part of each activation record a return address value, a pointer to a previous activation record, if any, and a method invocation address for the method associated with the activation record.

Claim 17

The method of claim 13, wherein the unique identifier associated with each method or procedure is a unique invocation address assigned to the method or procedure when the method or procedure is loaded into memory; the step of associating a method or procedure with a table entry comprises applying a hash function to the method or procedure's invocation address so as to generate a value indicative of the table entry; and the entry locating step comprises applying the hash function to the invocation address in the activation record being processed so as to generate a value indicative of the table entry corresponding to the activation record being processed.

Claim 18

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 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.

Claim 19

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 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.

Claim 20

The computer program product of claim 15, wherein the unique identifier associated with each method or procedure is a unique invocation address assigned to the method or procedure when the method or procedure is loaded into memory; the table entry associating instructions comprise instructions for applying a hash function to the method or procedure's invocation address so as to generate a value indicative of the table entry; and the table entry locating instructions comprises instructions for applying the hash function to the invocation address in the activation record being processed so as to generate a value indicative of the table entry corresponding to the activation record being processed.