A method for treating mark stack overflow through card dirtying in concurrent garbage collectors
Original Publication Date: 2002-Oct-19
Included in the Prior Art Database: 2003-Jun-21
Invention 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).