Browse Prior Art Database

A method for treating mark stack overflow through card dirtying in concurrent garbage collectors Disclosure Number: IPCOM000015823D
Original Publication Date: 2002-Oct-19
Included in the Prior Art Database: 2003-Jun-21
Document File: 2 page(s) / 43K

Publishing Venue




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

Page 1 of 2

  A method for treating mark stack overflow through card dirtying in concurrent garbage collectors


Disclosed is a method for treating mark stack overflow through card dirtying in concurrent garbage collectors. This method provides a more efficient way for treating mark stack overflow, in garbage collection mechanisms that mark concurrently with the Java* motators, and use an additional data structure to tag objects which were modified during the marking phase.

Existing Garbage Collectors

    The process of tracing all reachable (live) objects in the heap is a basic component of most of the existing garbage collectors. This tracing is usually done by using a mark stack, with push and pop operations. Each object, when first identified as reachable from roots or another object, is marked and pushed to the stack. It is later popped from the stack and traced. In the trace step, all objects that are referenced from this object, and are not marked yet, are marked and pushed to the mark stack. The marking of objects is done in order to ensure that an object is pushed to the mark stack only once. Marking is done either by using a dedicated data field in the object, or by maintaining a separate bit-per-possible-object-slot vector, called the markbits vector. The collection may be done by several threads, each using a private mark stack. Two or more threads may reach the same object simultaneously (if this object is referenced from many objects). The (exclusive) pushing of this unmarked object is done by the thread that wins the race of marking the object. These marking data structures are common, and the race is usually handled by using synchronized operations, such as compare-and-swap (C&S).

    The collection may be done when the execution of the application is suspended (Stop the World collection, or STW), or concurrently with the execution of the application (concurrent collection), or mostly concurrently with the application execution, with the final (shorter) part performed when the application is suspended (mostly concurrent collection).

    Concurrent and mostly concurrent collections need to know about any changes of reference that the application makes in objects, in order to retrace such objects. This is handled by making the application perform a Write Barrier with every reference change. The Write Barrier dirties the card of the object whose reference was changed. The dirtying is done by marking this card as dirty, usually in a separa...