Microsoft Technology Licensing, LLC

Christopher William Dern

Roy Patrick Tan

David L Detlefs

John Joseph Duffy

Vinod Grover

Timothy Lawrence Harris

Stephen Harris Toub

Michael M Magruder

Yosseff Levanoni

Martin Abadi

Madanlal S Musuvathi

Weirong Zhu

Lingli Zhang

Alexander Dadiomov

Dana D Groff

Sebastian Burckhardt

Sukhdeep S Sodhi

Raghuveer Simha

Shaun Emory Miller

A checking system is described for determining whether a component is thread safe in the course of interacting with two or threads in a client environment. The checking system uses a manual, automatic, or semi-automatic technique to generate a test. The checking system then defines a set of coarse-grained observations for the test, in which the component is assumed to exhibit linearizability when interacting with threads. The set of coarse-grained observations may include both complete and 'stuck' histories. The checking system then generates a set of fine-grained observations for the tests; here, the checking system makes no assumptions as to the linearizability of the component. The checking system identifies potential linearizability errors as those entries in the set of fine-grained observations that have no counterpart entries in the set of coarse-grained observations. The checking system may rely on a stateless model checking module to perform its functions.

Testing components for thread safety

One embodiment described herein is directed to a method practiced in a computing environment. The method includes acts for determining test suite effectiveness for testing for concurrency problems and/or product faults. The method includes identifying a plurality of synchronization primitives in a section of implementation source code. One or more of the synchronization primitives are iteratively modified and a same test suite is run for each iteration. For each iteration, a determination is made whether or not the test suite returns an error as a result of modifying one or more synchronization primitives. When the test suite does not return an error, the method includes providing to a user an indication which indicates at least one of a test adequacy hole for the test suite; an implementation source code fault; or an equivalent mutant of the implementation source code.

Concurrency test effectiveness via mutation testing and dynamic lock elision

Transactional memory compatibility type attributes are associated with intermediate language code to specify, for example, that intermediate language code must be run within a transaction, or must not be run within a transaction, or may be run within a transaction. Attributes are automatically produced while generating intermediate language code from annotated source code. Default rules also generate attributes. Tools use attributes to statically or dynamically check for incompatibility between intermediate language code and a transactional memory implementation.

Transactional memory compatibility management

A transactional memory implementation is tested using an automatically generated test program and a locking memory model implementation which defines atomicity semantics. Schedules of the test program specify different interleavings of read operations and write operations of the test program threads. Executing the schedules under the locking memory model implementation provides legal final states of the shared variable(s). Executing the schedules under the transactional memory implementation produces candidate final states of the shared variable(s). If the candidate final states are also legal final states, then the transactional memory implementation passes the test.

Checking transactional memory implementations

Growing community of inventors

Kirkland, WA, United States of America

Christopher William Dern