Oracle International Corporation

Erik Österlund

Stefan Mats Rikard Karlsson

Per A Liden

John Robert Rose

Axel Boldt-Christmas

Mikael Vidstedt

Ron Pressler

Nils Erik Eliasson

Techniques for concurrent lazy reference tracking in an old garbage collection generation are disclosed, including: encountering, by a mutator thread during a garbage collection epoch, a first instruction to write a first value to a field; responsive to encountering the first instruction to write the first value to the field: entering a slow-path write barrier; performing, by the slow-path write barrier, a first one or more reference counting operations with respect to the field; encountering, by the mutator thread during the first garbage collection epoch and subsequent to encountering the first instruction to write the first value to the field, a second instruction to write a second value to the field; responsive to encountering the second instruction to write the second value to the field: entering a fast-path write barrier; wherein the fast-path write barrier does not perform any reference counting operations with respect to the field.

Concurrent lazy reference counting in an old garbage collection generation

A system executes a first virtual thread, including storing a first shared object in a first private memory region, storing a pointer in a shared memory region, and determining that the pointer includes a reference to a location of the first shared object in the first private memory region. Responsive to determining that the pointer includes the reference, the system designates the first virtual thread as disqualified from eligibility for execution of a sweeping thread-local garbage collection process and augments the pointer to indicate that the pointer includes the reference to the location of the first shared object. The system executes a second virtual thread, including loading the pointer and determining that the pointer has been augmented. Responsive to determining that the pointer has been augmented, the system designates the second virtual thread as disqualified from eligibility for execution of the sweeping thread-local garbage collection process.

Selecting garbage collection processes

A system selects a first garbage collection process from a group of garbage collection processes. When a first thread stores a first set of objects to a first private memory region that is exclusive of any shared objects accessible by one or more additional threads, the system executes a sweeping thread-local garbage collection process upon termination of the first thread, including reclaiming the first private memory region. When a second thread stores to a second private memory region at least one shared object accessible by one or more additional threads, the system executes the selective garbage collection process upon termination of the second thread. The selective garbage collection process includes selectively reclaiming a second subset of memory blocks from the second private memory region allocated for a subset of private objects that are inaccessible from any thread.

Techniques are described herein for performing thread-local garbage collection. The techniques include automatic profiling and separation of private and shared objects, allowing for efficient reclamation of memory local to threads. In some embodiments, threads are assigned speculatively-private heaps within memory. Unless there is a prior indication that an allocation site yields shared objects, then a garbage collection system may assume and operate as if such allocations are private until proven otherwise. Object allocations in a private heap may violate the speculative state of the heap when reachable outside of the thread. When violations to the speculative state are detected, an indication may be generated to notify the garbage collection system, which may prevent thread-local memory reclamation operations until the speculative state is restored. The garbage collection system may learn from the violations to reduce the allocation of invalidly private objects and increase the efficiency of the garbage collection system.

Thread-local garbage collection

Techniques are disclosed for eliding load and store barriers while maintaining garbage collection invariants. Embodiments described herein include techniques for identifying an instruction, such as a safepoint poll, that checks whether to pause a thread between execution of a dominant and dominated access to the same data field. If a poll instruction is identified between the two data accesses, then a pointer for the data field may be recorded in an entry associated with the poll instruction. When the thread is paused to execute a garbage collection operation, the recorded information may be used to update values associated with the data field in memory such that the dominated access may be executed without any load or store barriers.

Cooperative garbage collection barrier elision

Techniques for lazy compaction are disclosed, including: selecting, by a garbage collector, multiple regions of a memory for inclusion in a relocation set; populating, by the garbage collector, a lazy free list (LFL) with the multiple regions selected for inclusion in the relocation set; subsequent to populating the LFL: determining, by an allocator, that an ordinary free list managed by the garbage collector is depleted; responsive to determining that the ordinary free list is depleted: selecting a region in the LFL; executing one or more load barriers associated respectively with one or more objects marked as live in the region, each respective load barrier being configured to relocate the associated object from the region if the associated object is still live; subsequent to executing the one or more load barriers: allocating the region.

Lazy compaction in garbage collection

A global state associated with a garbage collection (GC) process is a state assumed by a reference after GC operations for a current GC phase are performed for the reference. A frame state of a frame on a call stack of an application thread tracks a progress of GC operations for references therein. A color watermark is added after a global state change. The frame originally marked by a stack watermark is now marked by the new color watermark. The new color watermark marks a deepest frame on the call stack having the old global state. A color watermark is deleted when the stack watermark meets the color watermark. If the stack watermark is shifted in the call stack to mark the same frame as a color watermark, then the color watermark is deleted. The marked frame is a deepest frame on the call stack having the current global state.

Tracking frame states of call stack frames including colorless roots

Techniques for computing and storing object identity hash values are disclosed. In some embodiments, a runtime system generates a value, such as a nonce, that is unique to a particular allocation region within memory. The runtime system may mix the value with one or more seed values that are associated with one or more respective objects stored in the allocation region. The runtime system may obtain object identifiers for the respective objects by applying a hash function to the result of mixing the seed value with at least the value associated with the allocation region. Conditioning operations may also be applied before, during or after the mixing operations to make the values appear more random. The nonce value may be changed from time to time, such as when memory is recycled in the allocation region, to reduce the risk of hash collisions.

Computation and storage of object identity hash values

A request is received, from a mutator thread, to load a first reference to a first object from a heap memory onto a call stack of the application thread. Responsive to receiving the request, a system retrieves the first reference from the heap memory. The system executes a bitwise shift operation that (a) removes one or more bits representing the first garbage collection state and (b) generates a second reference from the first reference. Based on a particular bit, of the one or more bits removed from the first reference by the shift operation, the system determines whether to perform a set of garbage collection operations on the first reference to bring the first reference to a good state. The second reference, without any indication of any of the plurality of garbage collection states, is stored to the call stack.

Colorless roots implementation in Z garbage collector

During execution of garbage collection marking, an application thread receives a first request to overwrite a reference field of an object, the object comprising at least a first reference and the first request comprising a second reference to be written to the reference field. Responsive to receiving the first request, the application thread determines a marking parity for objects being traversed by the garbage collection marking process and loads the first reference from the heap. The application thread determines that marking metadata of the first reference does not match the marking parity. Responsive to that determination, the application thread adds the first reference to a marking list, modifies the second reference to include the current marking parity as the marking metadata, and stores the modified second reference to the first reference field. In subsequent writes to the reference field, the application thread refrains from adding to the marking list.

Snapshot at the beginning marking in Z garbage collector

Techniques for efficient continuation stack storage are disclosed. In some embodiments, when a continuation yields, the continuation stack, or portion thereof, is copied from a thread stack to a data object, referred to herein as a chunk, allocated from memory. The copied stack portion may maintain the same representation in the chunk as on the thread stack to minimize processing overhead of the operation. When the continuation resumes, the continuation stack, or some portion thereof, is copied from the chunk to the thread stack. During execution, the continuation stack that was copied may be modified on the thread stack. When the continuation yields again, the runtime environment may determine, based at least in part on whether the first object in memory is subject to a garbage collection barrier, whether to copy the modified portion of the continuation stack to the existing chunk or to allocate a new chunk.

Efficient continuation stack storage in languages with a garbage collector

An application thread executes concurrently with a garbage collection (GC) thread traversing a call stack of the application thread. Frames of the call stack that have been processed by the GC thread assume a global state associated with the GC thread. The application thread may attempt to return to a target frame that has not yet assumed the global state. The application thread hits a frame barrier, preventing return to the target frame. The application thread determines a frame state of the target frame. The application thread selects appropriate operations for bringing the target frame to the global state based on the frame state. The selected operations are performed to bring the target frame to the global state. The application thread returns to the target frame.

Implementing state-based frame barriers to process colorless roots during concurrent execution

Garbage collection (GC) states are stored within references stored on a heap memory to track a progress of GC operations with respect to the references. GC state may be stored in a non-addressable portion of references. Based on the GC state of a particular reference, a set of GC operations are selected and performed for the reference. However, references stored on a call stack do not include any indication of GC state. Hence, loading a reference from heap to call stack involves removing the indication of GC state. Writing a reference to heap involves adding the indication of GC state. References embedded within a compiled method also do not indicate any GC state. Metadata of the compiled method indicate a GC state, which is implicated to the embedded references. GC operations are selected and performed for each embedded reference based on the GC state of the compiled method.

Tracking garbage collection states of references

During a concurrent Relocation Phase, a GC thread relocates live objects, as an application thread executes. References in a frame on a call stack are remapped if the application thread attempts to access the frame. References on the call stack remains stale if no application thread attempts access. The GC thread may proceed with a subsequent phase of a GC cycle, even if a frame has stale references and therefore has not assumed a remap state. During a concurrent Mark/Remap Phase, the call stack may include frames in different frame states. The GC thread selects appropriate operations for processing each frame based on the respective frame state. When the GC thread encounters a frame not in the remap state, references therein are first remapped, and then identified as roots. Hence, root reference remapping and identification are performed in a single concurrent phase of a GC cycle.

Consolidated and concurrent remapping and identification for colorless roots

During execution of garbage collection, an application receives a first request to overwrite a reference field of an object, the object comprising a first reference and the first request comprising a memory address at which the reference field is stored, and a second reference to be written to the reference field. Responsive to receiving the first request, the system determines a current remembered set phase, and loads the first reference. The application determines that remembered set metadata of the first reference does not match the current remembered set phase. Responsive to that determination, the application adds an entry to a remembered set data structure, modifies the second reference to include the current remembered set phase as the remembered set metadata, and stores the modified second reference to the reference field. In subsequent writes to the reference field, the application refrains from adding to the remembered set data structure.

Growing community of inventors

Västerhaninge, Sweden

Erik Österlund