Browse Prior Art Database

Preventing the concurrent collection from tracing into an unassigned local copy of an object on weak ordering hardware

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

Publishing Venue

IBM

Abstract

Disclosed is a method for allowing concurrent garbage collectors, running on a weak ordering hardware, to trace only into objects whose assigned copy was already made global.

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

Page 1 of 3

  Preventing the concurrent collection from tracing into an unassigned local copy of an object on weak ordering hardware

Disclosed is a method for allowing concurrent garbage collectors, running on a weak ordering hardware, to trace only into objects whose assigned copy was already made global.

The problem solved by this method:

    Garbage collectors designed for large server configurations must take into account processor architecture design based on a weak ordering memory consistency model, e.g., IBM's PowerPC and Intel's IA-64. Weak ordering is a part of the wider issue of Relaxed Consistency memory models.

    In a weak ordering memory model, there is no guarantee of the order in which writes, issued on one processor, become visible to other processors. For example, suppose a thread running on processor A stores x_1 to location X, replacing its previous value x_0, and then stores y_1 to location Y. If another thread on processor B first loads Y and then loads X, it may see the new value of Y (y_1), but the old value of X (x_0). To solve such problems, weak ordering architectures provide memory synchronization operations, also called fence operations. A fence operation guarantees that the execution of all preceding store and load operations complete before any subsequent store or load operation.

    We use the same example as above, but now the processor A issues a fence between the two stores, and processor B issues a fence between the two loads. In this case, if B loads y_1 from Y, it is bound to load x_1 from X. Notice that both fences are needed, since a reordering of memory access by either processor could cause the anomalous behavior described earlier.

    These fence operations are expensive multi-cycle instructions. Because a garbage collector is a performance-sensitive component, it is important to avoid the use of fences as much as possible.

    A primary weak ordering problem for parallel and concurrent collectors exist when a mutator thread allocates and initializes an object, and a collector thread traces it.

    The problem could allow a concurrent tracing thread to begin tracing an object, but see the uninitialized memory that preceded the creation and initialization of the object. Incorrect behavior and a memory access violation could result. We describe the scenario that could produce the problem and the solution below.

    Suppose that mutator A, executing on one processor, creates and stores an initial value in object O_2, and then stores a reference to O_2 in object O_1. Further, suppose that the processor reverses the order of the stores. Now a tracing thread B, running on another processor, loads O_1, containing the reference to O_2, and attempts to trace into O_2 before the initial value of O_2 has been stored into memory. Thread B has accessed uninitialized memory in O_2.

    A simple but inefficient solution would be to add a fence right after the creation and initialization of every object. Thus, a tracing thread would always see init...