Sun Microsystems, Inc.

Red Hat, Inc.

Oracle America, Inc.

Christine H Flood

David L Detlefs

Nir N Shavit

Ole Agesen

Alexander T Garthwaite

Xiaolan Zhang

Steven K Heller

Paul A Martin

Andrew Edward Dinn

David Dice

Guy Lewis Steele, Jr

Victor M Luchangco

Guy L Steele

Jan-Willem Maessen

Steve Heller

Roman Kennke

Systems and techniques for garbage collection are disclosed for concurrently performing a garbage collection cycle in a single traversal of a garbage collection heap while application threads are running. The garbage collection cycle includes marking a first memory object as live. The garbage collection cycle also includes determining that a forwarding pointer of the first memory object points to the first memory object. The garbage collection cycle further includes evacuating the first memory object to a free region based on the determining. The garbage collection cycle additionally includes evacuating a second memory object in the same single traversal of the garbage collection heap in which the first memory object is being marked live.

Concurrent garbage collection with minimal graph traversal

A system, method, and techniques for managing memory are provided. An example method includes identifying a plurality of regions in a heap storing one or more objects of a first type and one or more objects of a second type. Each object of the first type includes application data and management data, and the management data is used by a managed runtime to manage the application data. The method also includes determining an object of the first type to read and computing, based on a last-known memory address of the object of the first type, a memory address of an object of the second type storing a current memory address of the object of the first type. The method further includes reading the current memory address stored in the object of the second type and locating the object of the first type at the read memory address.

Non-intrusive storage of garbage collector-specific management data

An example method of managing memory includes identifying a first object of the first type to update, the first object being stored on a heap. The method also includes reading a first memory address stored in a second object of the second type and storing a copy of the first object at a second memory address. The first memory address is an initial memory address of the first object. The method further includes after the copy is stored, reading a third memory address stored in the second object. The third memory address is a current memory address of the first object. The method also includes determining whether the first memory address matches the third memory address, and when the first memory address is determined to match the third memory address, updating the first memory address stored in the second object with the second memory address.

Pauseless garbage collector write barrier

An example method of managing memory for an application includes identifying a plurality of regions of a heap storing one or more objects of a first type and one or more objects of a second type. Each object of the second type stores a memory address of an object of the first type. The method also includes selecting a set of target collection regions of the heap. The method includes in a concurrent marking phase, marking one or more reachable objects of the first type as live data. The method further includes for each region of the plurality maintaining a calculation of live data in the respective region. The method also includes traversing the objects of the first type marked in the concurrent marking phase and evacuating a set of traversed objects from a target collection region to a destination region of the heap.

Concurrent garbage collector thread

A system for managing transactions, including a first reference cell associated with a starting value for a first variable, a first thread having an outer atomic transaction including a first instruction to write a first value to the first variable, a second thread, executing in parallel with the first thread, having an inner atomic transaction including a second instruction to write a second value to the first variable, where the inner atomic transaction is nested within the outer atomic transaction, a first value node created by the outer atomic transaction and storing the first value in response to execution of the first instruction, and a second value node created by the inner atomic transaction, storing the second value in response to execution of the second instruction, and having a previous node pointer referencing the first value node.

Parallel nested transactions

A multiprocessor, multi-program, stop-the-world garbage collection program is described. The system initially over partitions the root sources, and then iteratively employs static and dynamic work balancing. Garbage collection threads compete dynamically for the initial partitions. Work stealing double-ended queues, where contention is reduced, are described to provide dynamic load balancing among the threads. Contention is resolved by using atomic instructions. The heap is broken into a young and an old generation where parallel semi-space copying is used to collect the young generation and parallel mark-compacting the old generation. Speed and efficiency of collection is enhanced by use of card tables and linking objects, and overflow conditions are efficiently handled by linking using class pointers. A garbage collection termination employs a global status word.

Work stealing queues for parallel garbage collection

One embodiment of the present invention provides a system that facilitates performing operations on a lock-free double-ended queue (deque). This deque is implemented as a doubly-linked list of nodes formed into a ring, so that node pointers in one direction form an inner ring, and node pointers in the other direction form an outer ring. The deque has an inner hat, which points to a node next to the last occupied node along the inner ring, and an outer hat, which points to a node next to the last occupied node along the outer ring. The system uses a double compare-and-swap (DCAS) operation while performing pop and push operations onto either end of the deque, as well as growing and shrinking operations to change the number of nodes that are in the ring used by the deque.

Lock-free double-ended queue based on a dynamic ring

An array-based concurrent shared object implementation has been developed that provides non-blocking and linearizable access to the concurrent shared object. In an application of the underlying techniques to a deque, the array-based algorithm allows uninterrupted concurrent access to both ends of the deque, while returning appropriate exceptions in the boundary cases when the deque is empty or full. An interesting characteristic of the concurrent deque implementation is that a processor can detect these boundary cases, e.g., determine whether the array is empty or full, without checking the relative locations of the two end pointers in an atomic operation.

Maintaining a double-ended queue in a contiguous array with concurrent non-blocking insert and remove operations using a double compare-and-swap primitive

A remembered set for a memory heap region in a garbage-collected computer system is modified to classify reference locations stored therein by the heap region from which the references originate so that the number of references originating from a given region can be easily determined. If the number of remembered set entries for references from a second region to a first region reaches a predetermined threshold, the second region is constrained so that it will be collected at the same time as, or before, the first region. Then, all entries in the remembered set associated with the first region for references from the second region to the first region can be deleted, and no such entries need be entered in the future thereby reducing the size of that remembered set and the time required to scan it.

Method and apparatus for reducing remembered set overhead in a generational garbage collector by constraining collection set choice

A 'garbage collector' employed to reclaim memory dynamically allocated to data objects employs multiple execution threads to perform a parallel-execution operation and its garbage-collection cycle. A thread executes tasks that it selects from lists whose entries represent tasks dynamically identified during other tasks' performance. When a thread fails to find a task in one of these lists, it sets to an inactivity-indicating value a field associated with it in a global status word. It also determines whether any field associated with any of the other threads indicates activity. If not, the thread concludes that the parallel-execution operation has been completed. Otherwise, it returns to searching for further tasks to perform.

Termination detection for shared-memory parallel programs

In response to source code that represents instructions for dynamically allocating memory to objects, a compiler/interpreter produces instructions that implement a garbage collector. The garbage collector operates in garbage-collection cycles, which include parallel-execution operations such as locating reachable objects. Each thread maintains a respective task queue onto which it pushes identifiers of objects thus found and from which it pops those identifiers in order to begin the tasks of locating the further objects to which objects specified by the thus-popped identifiers refer. A thread's access to its respective task queue ordinarily occurs on a last-in, first-out basis, but the access mode switches to a first-in, first-out basis if the number of task-queue entries exceeds a predetermined threshold.

Load-balancing queues employing LIFO/FIFO work stealing

A computer system employing a plurality of concurrent threads to perform tasks that dynamically identify further similar tasks employs a double-ended queue ('deque') to list the dynamically identified tasks. If a thread's deque runs out of tasks while other threads' deques have tasks remaining, the thread whose deque has become empty will remove one or more entries from another thread's deque and perform the tasks thereby identified. When a thread's deque becomes too full, it may allocate space for another deque, transfer entries from its existing deque, place an identifier of the existing deque into the new deque, and adopt the new deque as the one that it uses for storing and retrieving task identifiers. Alternatively, it may transfer some of the existing deque's entries into a newly allocated array and place an identifier of that array into the existing deque. The thread thereby deals with deque overflows without introducing additional synchronization requirements or restricting the deque's range of use.

Multi-threaded garbage collector employing cascaded memory arrays of task identifiers to implement work stealing queues for task identification and processing

A garbage collector employs a plurality of task queues for a parallel-execution operation in a garbage-collection cycle. Each task queue is associated with a different ordered pair of the threads that perform the parallel-execution operation in parallel. One of the threads, referred to as that task queue's 'enqueuer' thread, is the only one that can 'push' onto that queue an identifier of a dynamically identified task. The other thread, referred to as that task queue's &#x201c;dequeuer,&#x201d; is the only one that can &#x201c;pop&#x201d; tasks from that task queue for execution. Since, for each task queue, there is only one thread that can &#x201c;push&#x201d; task identifiers on to it and only one thread that can &#x201c;pop&#x201d; task identifiers from it, the garbage collector can share dynamically identified tasks optimally among its threads without suffering the cost imposed by making combinations of otherwise separate machine instructions atomic.

Globally distributed load balancing

A multiprocessor, multiprogram, stop-the-world garbage collection program is described. The system initially over partitions the root sources, and then iteratively employs static and dynamic work balancing. Garbage collection threads compete dynamically for the initial partitions. Work stealing double-ended queues, where contention is reduced, are described to provide dynamic load balancing among the threads. Contention is resolved by atomic instructions. The heap is broken into a young and an old generation where semi-space copying employing local allocation buffers is used to collect the reachable objects in the young section, and for promoting objects from the young to the old generations, and parallel mark-compacting is used for collecting the old generation. Efficiency of collection is enhanced by use of card tables and linking objects, and overflow conditions are efficiently handled by linking using class pointers. The garbage collection termination using a global status word is employed.

Growing community of inventors

Westford, MA, United States of America

Christine H Flood