Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-09-15
2001-12-04
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06327701
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of computer systems, and, more specifically, to memory management garbage collection processes.
Sun, Sun Microsystems, the Sun logo, Java and all Java-based trademarks and logos are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. All SPARC trademarks are used under license and are trademarks of SPARC International, Inc. in the United States and other countries. Products bearing SPARC trademarks are based upon an architecture developed by Sun Microsystems, Inc.
2. Background Art
An important aspect of memory management in any computer system is garbage collection. Garbage collection (GC) refers to the process of reclaiming portions of main memory that are no longer in use by the system or any running applications. In an object-oriented system, garbage collection is typically carried out to reclaim memory allocated to objects and other data structures (e.g., arrays, etc.) that are no longer referenced by an application. The reclaimed memory can then be re-allocated to store new objects or data structures.
In a Javat™ virtual machine, garbage collection is performed to reclaim memory space from a region of memory known as the heap. The heap is used to store objects and arrays that are referenced by pointers stored as local variables in activation records, or “stack frames,” of a stack associated with an individual thread of execution in the virtual machine. The invocation of a method by a given thread results in the creation of a new stack frame that is “pushed” onto the stack of that thread. References to objects on the heap may be removed by an active (i.e., currently executing) method setting the respective pointer to a “null” value, or by removal of a respective stack frame in response to completion of its associated method.
In any thread of execution, there may be many garbage collection points, or “gc-points,” where garbage collection can occur. However, actual garbage collection typically takes place at only a fraction of these possible gc-points each time the given thread of execution is run. In virtual machine implementations using a compiler, the compiler provides information at each gc-point about the set of locations in the stack frames that contain pointers to objects or arrays. Garbage collection is performed by determining which objects and arrays in the heap are referenced from within the set of locations specified by the compiler, and reclaiming those objects and arrays that are no longer referenced.
Unfortunately, the compiler may have an error (i.e., a “bug”) that causes a stack location to be mistakenly omitted from the specified set of pointer locations. This type of compiler bug can result in the reclaiming of an object or array when a reference still exists. Also, for a type of garbage collection known as “copying” garbage collection, this compiler bug may result in a failure to update a pointer reference to point to the appropriate copy of the associated object or array. In either case, future references made to the object or array through the omitted stack location can result in improper execution of an application. This bug is garbage collection-related, but it may appear to be a code generation bug, making detection and correction difficult.
To provide a better understanding of the problems associated with garbage collection in a virtual machine, an overview of garbage collection techniques is provided below.
Garbage Collection
Garbage collection may be either conservative or exact. Conservative garbage collection involves scanning memory space for stored values that match the address of an object (or other memory structure) that is being considered for collection. If a matching value is not found in the memory being scanned, then no references to the object exist, and the object may be safely collected. If a matching value is found, it is assumed that the value is a reference (e.g., a pointer) to the object under consideration, and the object is not collected. This assumption means that an object is not collected even if the matching memory value is not a reference to the object, but rather a data value that coincidentally matches the base address of the object.
In exact garbage collection, only true references (pointers) are considered in a scan, so coincidentally matching data values are ignored in the collection process. This means that an object without any associated references is always considered garbage in a scan, and more efficient collection is achieved. However, to perform exact garbage collection, the scanning process must have information regarding which memory locations contain live references (i.e., active, non-null references). Only those memory locations containing live references are scanned to determine reference matches for objects under consideration for collection.
To provide more efficient use of memory space in terms of compaction, “copying” garbage collection is commonly implemented. In copying garbage collection, the memory space is divided into regions and an object transfer is performed. When garbage collection is carried out, objects in a portion of memory referred to as “from” space are copied to a portion referred to as “to” space. Those objects in “from” space that are considered “garbage” by the scan process are not copied to “to” space. The process of copying the objects results in reduced fragmentation of the memory space and better compaction.
FIG. 1
is a flow diagram illustrating a copying garbage collection process. In step
100
, the set of references to be scanned is determined. For example, a mechanism may be provided that tracks the creation of references, and maintains a list of current references for exact garbage collection. This list may be used to define the set to be scanned in step
100
. In step
101
, the garbage collection process obtains the first reference from the set of references. In step
102
, the reference is analyzed to determine if the reference points to an object in “from” space. If the reference does not point to an object in “from” space, the process jumps to step
107
. If, however, the reference does point to an object in “from” space, the process continues at step
103
.
In step
103
, the referenced object in “from” space is examined to determine whether the object is marked as copied. If the referenced object is marked, the process jumps to step
106
. However, if the referenced object in “from” space is not marked as copied, the process continues at step
104
, in which the referenced object is copied into “to” space. In subsequent step
105
, the referenced object in “from” space is marked as copied (e.g., replaced with a marker), with the location of the new copy in “to” space identified in the marker. In step
106
, the current reference is updated to point to the location of the new copy of the object in “to” space, as identified by the marked object in “from” space. The process continues in step
107
.
In step
107
, a check is performed to determine whether the current reference is the last reference in the set of references to be scanned. If the current reference is not the last reference, in step
108
, the next reference in the set is obtained, and the process returns to step
102
. If, however, in step
107
, the current reference is the last reference in the set, the process completes in step
109
where “from” space is collected in its entirety. Ideally, no references will be made in the future to objects in “from” space. In a subsequent garbage collection, “from” space becomes “to” space and “to” space becomes “from” space for purposes of copying.
The copying garbage collection scheme described above may be expanded to implement a generational approach. Generational collection schemes are predicated on the general assumption that newly created objects are more prone to collection than objects that have survived several garbage collection cycles. Using the generational approach, objects are segregated into generational group
Das Chameli C.
Powell Mark R.
Sun Microsystems Inc.
The Hecker Law Group
LandOfFree
Method and apparatus for finding bugs related to garbage... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for finding bugs related to garbage..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for finding bugs related to garbage... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2571350