Browse Prior Art Database

Parallel stack overflow handling

IP.com Disclosure Number: IPCOM000016070D
Original Publication Date: 2002-Jul-14
Included in the Prior Art Database: 2003-Jun-21
Document File: 3 page(s) / 48K

Publishing Venue

IBM

Abstract

During the "mark" phase of a stop-the-world Garbage collection in a *Java Virtual Machine (JVM) we identify which objects in the heap are no longer reachable, i.e garbage, and can therefore be collected. As we have no way of individually identifying unreachable objects we instead identify all the reachable objects; the remainder are garbage. The process of identifying all the reachable objects is also known as "tracing". The active state of the JVM is made up of the saved registers for each thread, the set of stacks representing the threads, the statics within Java classes, the set of local and global JNI references. All invocations of functions within the JVM itself give rise to a frame on the C stack. This frame may itself contain references to objects either as a result of an assignment to a local variable or a parameter passed from the caller. These thread stacks are viewed as a set of 4 byte fields (8 bytes in 64 bit architecture) and are scanned from top to the bottom.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 36% of the total text.

Page 1 of 3

Parallel stack overflow handling

During the "mark" phase of a stop-the-world Garbage collection in a *Java Virtual Machine (JVM) we identify which objects in the heap are no longer reachable, i.e garbage, and can therefore be collected. As we have no way of individually identifying unreachable objects we instead identify all the reachable objects; the remainder are garbage. The process of identifying all the reachable objects is also known as "tracing". The active state of the JVM is made up of the saved registers for each thread, the set of stacks representing the threads, the statics within Java classes, the set of local and global JNI references. All invocations of functions within the JVM itself give rise to a frame on the C stack. This frame may itself contain references to objects either as a result of an assignment to a local variable or a parameter passed from the caller. These thread stacks are viewed as a set of 4 byte fields (8 bytes in 64 bit architecture) and are scanned from top to the bottom.

    All these references are treated equally by the tracing routines and each is examined to see if its points to an object in the heap. Note that this does not make it necessarily a pointer to an object since it may be just an unlucky combination of bits in a float or integer. Hence when we make this scan of the stacks we must be 'conservative'. Anything which points at an object is assumed to be a live reference. A reference is considered to be a pointer to an object if it fulfills the following three criteria:

1. It is grained on an 8 byte boundary.
2. It is within the bounds of the heap.
3. The allocbit is on. Objects referenced in this way are known as roots.

    Once we have identified all the roots tracing proceeds to all references to other objects within the roots. However as we know which slots within a object are references and which are not we can complete the tracing 'accurately'.

    The tracing process uses a stack which can hold a finite number of references. All references that are pushed to the stack are marked at the same time by setting on the relevant markbit. The roots are marked and pushed to the stack and then we start to pop entries off the stack and trace them.

    Normal objects (not arrays) are traced by using the mptr to access the classblock which will tell us where references to other objects are to be found in this object. As we find each reference, if it is not already marked, we mark and push it. Array objects are traced by looking at each array entry and, if a referenced object is not already marked, we mark and push it.

    The above process continues iteratively until the mark stack eventually becomes empty. As we have a fixed size for the mark stack it is possible for it to overflow. If this occurs we take the following action:

      Set a global flag to indicate that mark stack overflow has occurred. Set a bit, the "NotYetScanned bit", in the object that could not be pushed. Tracing can then continue with all other o...