Microsoft Technology Licensing, LLC

Microsoft Corporation

Patrick Henri Dussud

Maoni Zhang Stephens

Vance Palmer Morrison

Christopher Wellington Brumme

James S Miller

Mircea Trofin

Raja Krishnaswamy

Sean Edwin Trowbridge

Mahesh Prakriya

Frank V Peschel-Gallee

Rudi Martin

George Harold Bosworth

David Charles Wrighton

John Lawrence Hamby

Peter F Sollich

Michael M Magruder

Krzysztof J Cwalina

Atsushi Kanamori

Brian D Harry

Daryl B Olander

Michal Strehovsky

Scott D Mosier

Fadi M Hanna

Ian H Carmichael

John Joseph Duffy

Steven E Lucco

Jerry Jay Dunietz

Michael Joseph Toutonghi

Martyn S Lovell

Rico Mariani

Brian M Grunkemeyer

Elliot H Omiya

Stephen C Rowe

Madhusudhan Talluri

Ales Holecek

Tassaduq Basu

Noel Richard Cross

James F Springfield

Bradley Moore Abrams

Brent Rector

Andrew J Pardoe

Peter Kukol

Simon Jeremy Hall

Li Zhang

Brian Robert Crawford

Peter A Hallam

James H Hogg

Jason L Zander

Sam Spencer

William G Evans

John Joseph Rivard

Douglas Jay Rosen

Steven J Steiner

Bradley M Abrams

WeiWen Liu

Jennifer A Hamilton

Mario Chenier

Habib Heydarian

Lawrence B Sullivan

Christopher S George

Gang Peng

Claudio Caldato

Robin M Maffeo

Steven Edward Lucco

Brent E Rector

Tassaduq H Basu

George H Bossworth

George H Bosworth

Christopher W Brumme

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

The present invention extends to methods, systems, and computer program products for controlling runtime access to application programming interfaces Embodiments of the invention allow library developers to more precisely and easily control which of their libraries' APIs can be called dynamically. Thus, their servicing and versioning burden can be more appropriately controlled. Further, application developers can control which such APIs to further exclude from dynamic calling scenarios, to minimize the runtime support overhead (e.g., preventing generation of metadata).

Controlling runtime access to application program interfaces

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

Platform-agnostic source code can be augmented with one or more portions of source code annotated for different platforms and/or versions. The source code including both the platform-agnostic and platform-specific and/or version-specific portions can be compiled once to create a single executable that can be distributed to and can run on multiple device platforms and/or multiple versions of one or more platforms. Platform-specific or version-specific executables (e.g., assemblies, binaries, etc.) can be embedded into a binary or executable as resources (e.g., data). When the compiled code is executed on a device, the runtime can extract the platform-specific portion corresponding to the device on which the executable is being run, can bind the extracted portion to the executable and can load and execute the executable. Hence the same binary can produce different results or functionalities depending on the capabilities of the platform on which the binary runs.

Adaptive portable libraries

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

API (application program interface) features defined by a set of APIs provide a different cross-sectional view of an application or framework than the view provided by sectioning along class or library boundaries, or binding units, for example. An API feature includes a proper subset of a library of a framework used by an application, and/or APIs which collectively reside in different libraries. A functionality feature API set provides an exposed surface area of a functionality feature of an application. Upon receiving a compilation request and determining that an API feature is to be excluded, an attempt is made to produce a compiled version of the application without the feature's APIs. In some cases, the functionality feature is independent of a baseline functionality of the application. Developers can obtain smaller but fully functional binaries. Framework architects can identify dependencies between API implementations when creating or modifying a software framework's architecture.

Cross-library framework architecture feature sets

Multiple different type hierarchies can communicate in a high performance and seamless manner by sharing a GC and interface dispatch logic. A runtime environment can support multiple independent type hierarchies, each type hierarchy defined by the module which defines the root of a type graph and some other helper functionality. Code that uses the dispatch logic has to follow certain rules in order to maintain GC and type safety. Different types in disjoint type graphs can behave as if they were one type for cross type graph communication purposes.

Seamless high performance interoperability between different type graphs that share a garbage collector

Growing community of inventors

Redmond, WA, United States of America

Patrick Henri Dussud