Microsoft Technology Licensing, LLC

Bjarne Steensgaard

Erez Petrank

Filip Pizlo

Galen Clyde Hunt

James R Larus

Brian Don Zill

David Read Tarditi, Jr

Gabriel Kliot

David R Tarditi

Avraham E Shinnar

Daniel John Spoonhower

Manuel A Fähndrich

David Edward Gay

Object relocation often involves a multi-word copy of the object from a source address to a destination address, followed by updating the references (e.g., pointers) to the object. However, during the relocation, other threads may write to portions of the object that have already been relocated, and the updates may be lost when the references are updated to point to the destination address. A non-blocking relocation technique may be implemented to permit threads to write to the object during the relocation, wherein the memory accesses are monitored for a write to the object. If a write is detected during the relocation, the relocation fails and the memory at the destination address is deallocated; but if no write is detected, the relocation succeeds and the references are updated to point to the destination address. Refinements of this technique may be implemented to reduce other synchronization issues.

Optimistic object relocation

Concurrent, incremental, and lock-free stack scanning for garbage collectors is disclosed. This method uses a summary table and return barriers to allow high responsiveness. The method also supports programs that employ fine-synchronization to avoid locks, imposes negligible overhead on program execution, can be used with existing concurrent collectors, and supports the special in-stack references existing in languages such as C#.

Incremental lock-free stack scanning for garbage collection

Mechanism that employs code cloning and specialized code execution for barriers to minimize runtime overhead. This is facilitated by duplicating code and inserting specializations of the barriers in the code copies. The mechanism is effective for garbage collection when the garbage collection executes through different phases, and the barrier behavior and overheads depend on these phases. The duplicated and specialized code enables the program to run efficiently by reducing the dynamic count of a phase check when the phase is well-known and phase checks can be avoided.

Path specializations for runtime code with phase behavior

Object relocation often involves a multi-word copy of the object from a source memory to a destination memory, followed by updating the references (e.g., pointers) to the object. However, during the relocation, other threads may write to portions of the object that have already been relocated, and the updates may be lost when the references are updated to point to the destination memory. The object relocation may therefore mark the words of the object during relocation with a relocation value to indicate transfer to the destination memory without locking the threads. The threads may be configured to check the value the source memory during object access, and to access the corresponding word of the destination memory if the source memory word comprises the relocation value. While the probability of a large (e.g., 64-bit) relocation value appearing in the object is small, safety measures are provided to detect and mitigate conflicts.

Probabilistic object relocation

Described is a technology by which a real-time data relocating mechanism is provided for multiprocessing environments, including supporting lock-free programs that run in parallel. The relocating mechanism moves an object by using a status field related to the data field, possibly in an interim (wide) object space, which is then copied to a to-space object. The status information for each data field of the original object contains information indicating where a current version of the data for each field is present, that is, in the original, wide or to-space object. In one example, a handshake mechanism of a garbage collector establishes preparation and copy phases between the mechanism and other threads that determine where memory accesses occur. Also described is support for program thread compare-and-swap (CAS) operations and/or multi-word atomic operations.

Concurrent, lock-free object copying

Described herein are one or more implementations that separate kernel interfaces functions into those that act on kernel objects owned by a process and accessed exclusively by that process&#x2014;described herein as local kernel objects&#x2014;from access to kernel objects owned by a process and accessible by other active processes.

Kernel interface with categorized kernel objects

Existing methods for returning program state to a previous state are often too heavy weight. Often these methods attempt to guarantee a series of properties to a programmer across a distributed environment or multiple threads. Instead, a program state reversion mechanism provides a light weight and efficient runtime solution for general purpose programming languages. For example, a series of program statements (e.g., methods, instructions, etc.) are indicated by a programmer in a state reversion language construct, such as a TryAll block. If an exception is thrown anywhere from within the TryAll block, the program is reverted to the pre-TryAll block state.

Programming language support for integrating undo and exception handling

An object-oriented program is modified to create objects within specified regions, allowing memory de-allocation to take place for entire regions at once. The contents and associations between the regions are described by one or more shape graphs, which are created from an analysis of the program code. The region association metadata stored by the shape graphs allows the region-based memory management to take place while requiring no more than one region to be passed to methods for each object passed.

Region-based memory management for object-oriented programs

Thread-specific heaps are employed in multithreaded programs to decrease garbage collection latency in such programs. Program data in a target program is analyzed to identify thread-specific data and shared data. Thread-specific data is identified on the basis that the thread-specific data is determined to be reachable only from a single program thread of the target program. Each program thread can be associated with an individual thread-specific heap. Shared data is identified on the basis that the shared data is potentially reachable from a plurality of program threads of the target program. An exemplary method of identifying such data is referred to as a thread escape analysis. Garbage collection of such heaps may be performed independently or with minimal synchronization. Remembered sets may also be used to increase the independence of collection of individual heaps and to decrease garbage collection latency.

Thread-specific heaps

Location types in unification-based, flow-insensitive 'points-to' analyses represent three kinds of sets of abstract memory locations in a three-level subtyping system. The data constructor for 'middle' and &#x201c;upper&#x201d; kinds of location types has a reader and a writer component. The &#x201c;middle&#x201d; kind of location types represent singleton sets of abstract locations. The reader and writer components of the &#x201c;middle&#x201d; type are both the same location type. The &#x201c;upper&#x201d; kind of location types represent complex sets of abstract locations. The reader and writer components of the &#x201c;upper&#x201d; type may be dissimilar location types. The reader components represent the set of values that may be read from memory via a pointer represented by the location type containing the reader component. The writer components represent the set of values that may be written to memory via a pointer represented by the location type containing the writer component.

Unification-based points-to-analysis using multilevel typing

A method for determining object bounds for objects within a program comprises receiving the program code in a suitable language and analyzing the received code with a set of rules defining an escape analysis with a complexity linear in time and space with the size of the program plus the program's call graph.

Method and apparatus for determining the relationships and useful lifetime of objects in a program

A pointer analysis by type inference for a computer program ith structured memory objects and potentially inconsistent memory object accesses helps approximate run-time store usage for the program. The analysis represents locations for the program with types describing access patterns for the represented locations based on how the locations are accessed in the program. The analysis describes access patterns for structured memory objects, elements of structured memory objects, and memory objects accessed in inconsistent manners in the program. The analysis identifies store usages described by the program and determines whether the location(s) and/or function(s) affected by the identified store usages are well-typed under typing constraints. If the identified store usages are not well-typed, the analysis modifies types for location(s) and/or function(s) affected by the identified store usages as necessary so the store usages are well-typed. When the locations and/or functions for all identified store usages are well-typed, the program is well-typed with the set of types defining a store model for the program.

Pointer analysis by type inference for programs with structured memory objects and potentially inconsistent memory object accesses

A pointer analysis by type inference combined with a non-pointer analysis helps approximate run-time store usage for a computer program. The analysis initially describes the content of each location for the program with a separate type as a non-pointer value. The analysis identifies store relationships described by the program and determines whether the location(s) and/or function(s) affected by the identified store relationships are well-typed under typing constraints. For well-typed store relationships, the analysis identifies any potential points-to relationships for types representing non-pointer values in case the analysis subsequently determines in processing other store relationships that the types may represent a pointer value. If the identified store relationships are not well-typed, the analysis modifies types for location(s) and/or function(s) affected by the identified store relationships as necessary so the store relationships are well-typed. The analysis also modifies types for locations and/or functions for potential points-to relationships affected by the modification of types When the locations and/or functions for all identified store relationships are well-typed, the program is well-typed with the set of types defining a store model for the program.

Pointer analysis by type inference combined with a non-pointer analysis

A terminating polymorphic type inference program analysis helps to better optimize, understand, and/or browse computer programs. The analysis represents parameter values for each function call in the program with separate types and modifies the types to comply with typing constraints. The analysis also determines whether a potential non-terminating loop has been entered. If so, the analysis modifies the types such that the types comply with the typing constraints and such that the type inference analysis will terminate. In this manner, the analysis will generate a usable finite set of types for programs regardless of whether the principal typing for the program is infinite in size.

Growing community of inventors

Bothell, WA, United States of America

Bjarne Steensgaard