Microsoft Technology Licensing, LLC

Microsoft Corporation

Maoni Zhang Stephens

Patrick Henri Dussud

Peter F Sollich

Corneliu I Lupu

Mark Ronald Plesko

Donald J Munsil

Mark S Carroll

Peter Franz Valentin Sollich

Ying Hung Au

Claudio Caldato

Vadim Bluvshteyn

Michael Sciacqua

Steven S Heinz

Manish Godse

Mukund Raghav Sharma

Some embodiments perform lightweight monitoring for garbage collection (GC) flow events, then perform focused tracing after detecting a performance problem signal. The tracing is focused by constraints which are specified in a designation data structure, including a performance problem signal definition, a corresponding trace data category and a corresponding tracing stop trigger. Tracing is done only in the specified category and only for the specified time period, to reduce or avoid collection of irrelevant trace data and to reduce or avoid changes in program behavior caused by the tracing itself. Some designation data structures also specify a corresponding trace data analysis. In operation, some embodiments dynamically re-focus tracing on an offshoot trace in response to a trace data analysis result obtained while the program is still executing.

Garbage collection lightweight dynamic tracing and analysis

Garbage collection or other computational work accesses memory which is located outside processor registers. Some embodiments specify at least some of the memory accesses and separate them from other computations, and utilize a memory access state machine to control the execution of both kinds of computation. Code that employs memory access results is placed in a run routine which is divided between respective states of the state machine. The specified memory accesses are invoked from a state code, and overlap other computation. A prefetch buffer may be dynamically sized based on the availability of space in the prefetch buffer. Code for shared work, such as address relocation code, may be placed in its own state structure. Candidate code for possible separation into a specified memory access routine may be automatically recognized.

Garbage collection prefetching state machine

Systems and methods for garbage collection are disclosed. A garbage collection is triggered in a memory allocation based on a free list and selected amount of free space in an inner closed feedback loop. The free list is determined from a selected memory load and a current memory load as generated from the garbage collection in an outer feedback loop.

Closed loop garbage collector

Managing secondary objects efficiently increases garbage collection concurrency and reduces object storage requirements. Aliveness marking of secondary objects is integrated with aliveness marking of referenced objects. Allocation of reference-sized secondary object identifier fields in objects which are not primary objects is avoided; a dedicated bit specifies primary objects, together with an object relationship table. A primary object is one with at least one secondary object which is deemed alive by garbage collection if the primary object is alive, without being a referenced object of the primary object. Any referenced objects of the alive primary object will also still be deemed alive. Code paths for marking referenced objects can be shared to allow more efficient secondary object marking. Primary-secondary object relationships may be represented in dependent handles, and may be specified in a hash table or other data structure.

Integrated reference and secondary marking

Garbage collectors and other software may utilize performant lock-free multithreaded software. Unitary lock-free updates to a set of variables involves an updating value Z, release barriers and acquire barriers that enforce orderings on code execution, and atomicity resulting from variable alignment. Conveyance is accomplished with a values placing step and a values retrieving step. Values placing replaces a non-updated value in a variable Var1 with Z, executes a release barrier, replaces the non-updated values of other variables with update values, executes another release barrier, and replaces Z with the Var1 update value. Values retrieving reads from Var1 into a variable DestVar1A, executes an acquire barrier, reads from the other variables into respective destination variables, executes another acquire barrier, reads from Var1 into a variable DestVar1B, and repeats if DestVar1A is Z or if DestVar1A and DestVar1B are unequal. This solution conveys the update values without locks, as a unit.

Lock-free reading of unitary value sets

Memory reclamation is tailored to avoid certain synchronization instructions, speeding concurrent garbage collection while preserving data integrity and availability. Garbage collection reclaims objects no longer in use, or other unused areas of memory. Pointers are partitioned into address portions holding address values and non-address portions having a special bit. Marking code writes only the non-address portions, setting the special bit as a mark reference, relocation candidate, etc. Mutator threads may concurrently mutate the entire pointer to update the address, but mutation does not cause incorrect reclamations or failure to do other operations such as relocation. Meanwhile, execution speed is increased by avoiding CAS (compare-and-swap instructions or compare-and-set) synchronization instructions. Non-CAS yet nonetheless atomic writes are used instead. Mutators run in user or kernel address spaces. Partitioned pointers and their use may be enclosed to avoid runtime errors by code that expects references to be in a canonical non-partitioned form.

Reducing synchronization reliance in marking

An arena-based memory management system is disclosed. In response to a call to reclaim memory storing a plurality of objects allocated in an arena, a garbage collection of the arena is triggered based on heap-related parameter. A live object of the plurality of objects is preserved with the garbage collection.

Arena-based memory management

Memory reclamation is tailored to avoid certain synchronization instructions, speeding concurrent garbage collection while preserving data integrity and availability. Garbage collection reclaims objects no longer in use, or other unused areas of memory. Pointers are partitioned into address portions holding address values and garbage collection portions having a special bit. Marking code writes only the garbage collection portions, setting the special bit as a mark reference, relocation candidate, etc. Mutator threads may concurrently mutate the entire pointer to update the address, but mutation does not cause incorrect reclamations or failure to do other operations such as relocation. Meanwhile, execution speed is increased by avoiding CAS (compare-and-swap instructions or compare-and-set) synchronization instructions in the garbage collector. Non-CAS yet nonetheless atomic writes are used instead. Mutators run in user or kernel address spaces. Partitioned pointers and their use may be enclosed in the garbage collector to avoid runtime errors by code that expects references to be in a canonical non-partitioned form.

Reducing synchronization reliance in garbage collection marking

A process may utilize multiple garbage collector threads, each having the capability to steal partially-marked object references from an accessible mark stack having additional work that has yet to be processed. A partially-marked object reference may be represented as a pair of entries on a mark stack. A garbage collector thread may utilize an atomic operation to access the pair of entries in a prescribed manner to steal an unprocessed partially-marked object reference. In this manner, the workload of an overloaded garbage collector thread is offloaded to another garbage collector thread that may be idle thereby balancing the workload more evenly among multiple garbage collector threads.

Work stealing of partially-marked objects

A method for use with a garbage collector to provide garbage collection is disclosed. The garbage collection is a concurrent garbage collection provided in a dedicated thread concurrently running in a computing device with a mutator thread. The concurrent garbage collection is triggered based on a dynamically tunable parameter from a previous garbage collection in closed loop feedback.

Garbage collector

A method for use with a garbage collector to provide different garbage collections is disclosed. The garbage collections are concurrent garbage collection provided in a dedicated thread concurrently running in a computing device with a mutator thread. A heap size stage, from multiple heap size stages including a heap size growth stage and a heap size stable stage, is determined from a free space amount subsequent a garbage collection. A heap stable garbage collection is applied in response to the heap size stage being the heap size stable stage. A heap growth garbage collection is applied in response to the heap size stage being the heap size growth stage.

Multiple stage garbage collector

Garbage collection of objects within the heap of a computing system, and movement of adjacent sets of live objects as a whole in order to perform compaction. The compaction may be performed even if there are adjacent sets of live objects that include one or more pinned objects that should not be moved by the garbage collector. The garbage collector uses gaps to include relocation information with respect to sets of adjacent objects of the same pinned status. Some gaps may be formulated by writing over the live objects themselves, in which case that written over data is saved off prior to formulating the gap. When compaction is performed, the saved off data is used to fully integrate the adjacent objects of the same pinned status in the process of compaction.

Garbage collection of non-pinned objects within heap

Efforts to avoid time-outs during execution of an application in a managed execution environment may be implemented by monitoring memory allocation.

Load balancing based on impending garbage collection in execution environment

Controlling garbage collection operations. The method includes setting up garbage collection to collect objects that are no longer in use in a managed code environment. The method further includes receiving managed code input specifying a desired quantum within which it is desired that garbage collection not be performed. The method further includes performing a computing operation to determine the desired quantum can likely be met. The method further includes running memory operations within the quantum without running the initialized garbage collection.

Garbage collection control in managed code

Based on a requested allocation of a managed object, a native memory required with the managed object is determined. A portion of native memory is allocated and a portion of managed memory is allocated based on requirements of the managed object. A memory management strategy is implemented based on the allocation of native memory and unmanaged memory. For example, the memory management strategy can comprise garbage collection of first managed objects that have only managed heap associated therewith is performed before garbage collection of second managed objects that have both managed heap and native memory associated therewith.

Growing community of inventors

Kirkland, WA, United States of America

Maoni Zhang Stephens