Methods and systems to identify and reproduce concurrency violations in multi-threaded programs

• US 10,191,834 B2
• Filed: 04/11/2016
• Issued: 01/29/2019
• Est. Priority Date: 12/21/2011
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Gottschlich, Justin, Pokam, Gilles, Pereira, Cristiano, Ha, Jungwoo
• Primary Examiner(s): Kamran, Mehran
• Application Number:
  US15/096,141
• Publication Number:
  US 20160224457A1
• Time in Patent Office: 1,023 Days
• Field of Search: 718106
• CPC Class Codes: G06F 11/3632 of specific synchronisation aspects
• CPC Class Codes: G06F 11/3644 by instrumenting at runtime
• CPC Class Codes: G06F 11/3648 using additional hardware
• CPC Class Codes: G06F 11/366 using diagnostics G06F11/0703 takes precedence
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3861 Recovery, e.g. branch miss-prediction, exception handling error detection or correction G06F11/00
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

Methods and systems to identify and reproduce concurrency violations in multi-threaded programs are disclosed. An example method disclosed herein comprises determining whether a condition is met and serializing an operation of a first thread of a multi-threaded program relative to an operation of a second thread of the multi-threaded program. The serialization of the operations of the first and second threads results in a concurrency violation or bug thereby causing the multi-threaded program to crash. In this way, the operations of the first and second threads of the multi-threaded program that are responsible for the concurrency violation are identified and can be revised to remove the bug.

Claims

1. A method to identify threads responsible for causing a concurrency violation in a multi-threaded program comprising:

executing, with a processor, at least one of a plurality of thread controllers inserted into respective threads of a plurality of threads of a multi-threaded program to be debugged, a first thread controller of the plurality of thread controllers controlling an order in which first operations of a first respective thread of the plurality of threads are executed relative to second operations of a second thread of the plurality of threads, the controlling of the order in which first operations are executed relative to second operations including, when a first condition is met in the first thread, the first thread controller causing the first thread to stall, the stalling of the first thread to cause the first condition to remain satisfied while the other threads of the multi-threaded program continue to execute;

causing the concurrency violation to occur based on a determination that a threshold number of a plurality of respective conditions defined in the respective thread controllers have been concurrently satisfied;

based on the occurrence of the concurrency violation, identifying the respective threads that define the respective conditions that have been satisfied as being responsible for causing the concurrency violation; and

when the threshold number of the plurality of respective conditions have not been satisfied within a threshold duration, halting the plurality of threads of the multithreaded program.

2. A method as defined in claim 1, wherein a second thread controller of the plurality of thread controllers permits execution of the second thread of the multi-threaded program to advance until a second condition defined in the second thread controller is satisfied, and the second thread controller causes execution of the second thread to stall when the second condition defined in the second thread controller is satisfied, the stalling of the second thread to cause the second condition to remain satisfied while the threads, other than the first thread, continue to execute.

3. A method as defined in claim 1, further including:

determining whether the threshold number of conditions have been satisfied within a threshold duration;

if the threshold number of conditions have not been satisfied within the threshold duration, causing the plurality of threads to halt execution and generating an indication that the concurrency violation has not occurred; and

if the threshold number of conditions have been satisfied within the threshold duration, generating an indication that the concurrency violation has occurred.

4. A method as defined in claim 1, wherein the threshold number of conditions to be satisfied includes one of the conditions being satisfied a threshold number of times.

5. A method as defined in claim 1, wherein causing the concurrency violation to occur is further based on the threshold number of conditions being satisfied in a specified order.

6. A tangible computer readable medium comprising computer readable instructions which, when executed, cause a computer to at least:

control an order in which first operations of a first thread of a multi-threaded program to be debugged are executed relative to operations of a second thread of the multi-threaded program by causing the first thread to stall upon a first determination that a first condition inserted into the first thread has been satisfied, the stalling of the first thread to cause the first condition to remain satisfied while the other threads of the multi-threaded program continue to execute;

cause a concurrency violation to occur based on a second determination that a threshold number of a plurality of respective conditions defined in respective threads of the multi-threaded program have been concurrently satisfied;

based on the occurrence of the concurrency violation, identify the respective threads that define the respective conditions that have been satisfied as being responsible for causing the concurrency violation; and

halt the plurality of threads of the multi-threaded program based on a third determination that the threshold number of the respective conditions have not been satisfied within a threshold duration.

7. A computer readable medium as defined in claim 6, wherein the instructions further cause the computer to:

determine whether the threshold number of conditions have been satisfied within a threshold duration;

if the threshold number of conditions have not been satisfied within the threshold duration, cause the plurality of threads to halt execution and generate an indication that the concurrency violation has not been detected; and

if the threshold number of conditions have been satisfied within the threshold duration, generate an indication that the concurrency violation has occurred.

8. A computer readable medium as defined in claim 6, wherein the threshold number of conditions to be met includes one of the conditions being met a threshold number of times.

9. An apparatus to identify threads responsible for causing a concurrency violation in a multi-threaded computer program, the apparatus comprising:

memory including computer readable instructions; and

a processor to execute the computer readable instructions, the instructions, when executed to cause the processor to at least;

control an order in which first operations of a first thread of a multi-threaded program are executed relative to operations of a second thread of the multi-threaded program by causing the first thread to stall upon a first determination that a first condition inserted into the first thread has been satisfied, the stalling of the first thread to cause the first condition to remain satisfied while the other threads of the multi-threaded program continue to execute;

cause a concurrency violation to occur based on a second determination that a threshold number of a plurality of respective conditions defined in respective threads of the multi-threaded program have been concurrently satisfied;

based on the occurrence of the concurrency violation, identify the respective threads that define the respective conditions that have been satisfied as being responsible for causing the concurrency violation; and

halt the plurality of threads of the multi-threaded program based on a third determination that the threshold number of the respective conditions have not been satisfied within a threshold duration.

10. An apparatus as defined in claim 9, wherein the instructions further cause the processor to:

determine whether the threshold number of conditions have been satisfied within a threshold duration;

if the threshold number of conditions have not been satisfied within the threshold duration, cause the plurality of threads to halt execution and generate an indication that the concurrency violation has not been detected; and

if the threshold number of conditions have been satisfied within the threshold duration, generate an indication that the concurrency violation has occurred.

11. An apparatus as defined in claim 9, wherein the threshold number of conditions to be met includes one of the conditions being met a threshold number of times.

12. An apparatus as defined in claim 9, wherein the threshold number of conditions to be satisfied are to be satisfied in a specified order.