Browse Prior Art Database

Write barrier that allows stopping thread anywhere

IP.com Disclosure Number: IPCOM000019886D
Original Publication Date: 2003-Oct-07
Included in the Prior Art Database: 2003-Oct-07
Document File: 3 page(s) / 45K

Publishing Venue

IBM

Abstract

Disclosed is a write barrier that allows the program threads to be stopped at any point during the execution of garbage collection (gc). This invention is especially useful in systems that do not employ gc safe-points.

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

Page 1 of 3

Write barrier that allows stopping thread anywhere

Invention

    Disclosed is a write barrier that allows the program threads to be stopped at any point during the execution of garbage collection (gc). This invention is especially useful in systems that do not employ gc safe-points.

Prior Art

    A garbage collector (GC) is a system program that automatically manages heap memory. A tracing collector (mark-sweep or copying) traces all the objects accessible by an application program, and then collects the space occupied by the non-accessible objects. This collected memory is used to satisfy future allocations by the application program.

A stop-the-worldGC performs this by (1) stopping all the application threads;
(2) identifying the roots, which include the static variables and local variables, i.e., the references in the program-stacks of the application threads (the contents of the machine registers are assumed to be stored on the program stack as part of stopping a running thread); and (3) tracing from these roots onto the heap (main memory), object by object; from each object onto the objects it references. Each object thus visited is reachable and must be maintained. The objects that were not traced are collected, and their space is used by the system to supply further allocation requests.

    A concurrentGC traces the graph of reachable objects while the application threads continue to run. There may be a stop-the-world phase at the beginning and/or end of a collection cycle. The object graph may change as the GC traces through the reachable objects. In order not to erroneously avoid tracing reachable objects, the application threads are required to do extra work when they access memory. One mechanism used by some concurrent collectors is a write barrier. A write barrier keeps track of the reference slots in memory that have been written. A write barrier can be implemented by adding the address of the modified object or address of the modified object slot to a list, or by marking in a bit or byte vector the entry corresponding to a small address aligned section of memory (called a card). The size of the card that contains the updated slot is usually a power of 2 (e.g., 512 bytes). We will call this "enlisting the updated object."

    To illustrate the usefulness of the write barrier, consider its use in a mostly concurrent mark/sweep collector. A mostly concurrent collector traces and marks reachable objects, starting from the roots, while the application threads continue to run. As the application threads run, the write barrier keeps track of the object slots containing references, which they update. These slots may contain references to objects that the mostly concurrent tracer has not marked. The mostly concurrent phase is followed by a stop-the-world phase. In this phase, the threads are stopped, their stacks and registers are rescanned for unmarked objects, and the object slots enlisted by the write barrier for marked objects are retr...