US 9,069,894 B2Granted

Data collisions in concurrent programs

AssigneeMicrosoft Technology Licensing, LLC

InventorsJohn Erickson, Madan Musuvathi

Life of this patent

Estimating the term…

Loading patent…

Abstract

Described are techniques for detecting data collisions between a first portion and a second portion of an application executing on a computer, the first portion and the second portions executing concurrently with respect to each other. While the first portion and second portion are executing, before the first portion accesses a memory location shared by the first portion and the second portion, a value stored in the memory location is captured and the first portion is delayed. While the second portion continues to execute the first portion is delayed. After a period of the first portion having been paused or slowed, the current content of the memory location is compared with the captured content to determine if there is a data collision. The first and second portions may be threads, and the capturing, delaying, and determining may be performed by code inserted to the application after it has been compiled.

Claims17

Dependent claims

A method of testing for potential data collisions between a first thread and a second thread of an application executing on a computer, the first thread and the second thread configured to execute concurrently with respect to each other, the method comprising:

automatically identifying a variable as a test target by determining that the variable is accessed by the first thread by determining that the same variable is also accessed by the second thread;
based on the variable having been identified as a test target, automatically inserting test code into the application, the test code inserted within application code of the first thread and at a location of an access operation within application code of the first thread that accesses the variable, the test code located according to the location of the access operation within the application code of the first thread;
while the first thread and second thread are executing, before the access operation accesses the identified variable shared by the first thread and the second thread, determining, by the test code, whether an indication of the variable is in a list of active variables, and in response to the determining, the test code:
when an indication of the variable is not in the list:
adds an indication of the variable to the list induces a delay of the first thread, wherein the second thread continues to execute while the first thread is delayed, and, after the delay, removes the indication of the variable from the list;
and
when an indication of the variable is in the list:
a collision is determined to have occurred and in response a debugging action is taken.

5 more elements

A computer-readable storage device storing information to enable a computer to perform a process, wherein the computer-readable storage device is not a signal, the process comprising:

automatically determining that a thread of an application has an access operation that accesses a shared memory location and based thereon automatically inserting test code into native code of the thread at the access operation of the thread of the application, wherein the determining comprises identifying the shared memory location on the basis of the shared memory location having accesses thereto in multiple threads, including the thread;
and
executing the application, the application comprising the native code and the test code, wherein when the test code executes the test code determines whether an indication of the shared memory location is in an active-data list, wherein, when an indication of the shared memory location is determined to be in the active-data list, a collision is determined to have occurred and in response a debugging action is invoked, and when an indication of the shared memory location is determined to be not in the active-data list, an indication of the shared memory location is added to the active-data list, an artificial delay of the thread is induced, and the indication of the shared memory location is removed from the active-data list after the delay.

A method of detecting a data collision over shared data that is shared by concurrently executing first and second threads of an application, the first thread and the second thread both having code that accesses shared data without a lock, the method comprising:

automatically locating access operations of the first thread that access the shared data, and in response automatically inserting test code into the first thread at the identified access operations;
maintaining, by test code inserted into the application, including the test code inserted into the first thread, an active list indicating active shared data items;
executing the first thread, including executing the test code, the test code, when executed, performing a check to determine whether an indication of the shared data is in the active list, wherein if determined that an indication of the shared data is not in the active list, then an indication of the shared data is added to the active list, wherein the test code causes the first thread to artificially slow or pause near the portions of the first thread that access the shared data, and wherein if determined that the shared data is in the active list then a data collision is determined to have occurred and a corresponding debug action is performed;
determining, by the test code, if the shared data changed while the first thread was slowed or paused;
when determined by the test code that the shared data changed, initiating a debugging or testing action;
and
after an access operation has completed, removing, by the test code, if the any indication of the shared data that was added to the active list by the execution of the test code.

4 more elements

Dependencies are inferred from the claim text.