SYSTEMS AND METHODS FOR FINDING CONCURRENCY ERRORS

• US 20140359577A1
• Filed: 08/20/2014
• Published: 12/04/2014
• Est. Priority Date: 12/06/2010
• Status: Active Grant

• Current Assignee: University of Washington
• Original Assignee: University of Washington
• Inventors: Ceze, Luis, Lucia, Brandon
• Granted Patent: US 9,146,737 B2
• Time in Patent Office: Days
• US Class Current: 717/123
• CPC Class Codes: G06F 11/3688 for test execution, e.g. scheduling of test suites
• CPC Class Codes: G06F 8/314 Parallel programming languages G06F8/313 takes precedence
• CPC Class Codes: G06F 8/75 Structural analysis for program understanding

Abstract

Systems and methods for detecting concurrency bugs are provided. In some embodiments, context-aware communication graphs that represent inter-thread communication are collected during test runs, and may be labeled according to whether the test run was correct or failed. Graph edges that are likely to be associated with failed behavior are determined, and probable reconstructions of failed behavior are constructed to assist in debugging. In some embodiments, software instrumentation is used to collect the communication graphs. In some embodiments, hardware configured to collect the communication graphs is provided.

Claims

1. A computer-implemented method of building a context-aware communication graph, the method comprising:

detecting an access of a memory location by a first instruction of a first thread;

updating a context associated with the first thread; and

in response to determining that a second instruction of a second thread different from the first thread was a last thread to write to the memory location;

adding an edge to the context-aware communication graph, the edge including the context associated with the first thread, a sink identifying the first instruction, a source identifying the second instruction, and a context associated with the second thread.

2. The computer-implemented method of claim 1, wherein the edge includes a timestamp of execution of the source instruction and a timestamp of execution of the sink instruction.

3. The computer-implemented method of claim 1, wherein the access of the memory location is a write, wherein updating the context associated with the first thread includes adding a local write indicator to the context of the first thread, and wherein the method further comprises adding a remote write indicator to a context of at least one thread other than the first thread.

4. The computer-implemented method of claim 3, wherein adding a remote write indicator to a context of at least one other thread other than the first thread includes adding a remote write indicator to a context of at least one thread other than the first thread that read the memory location since the last write.

5. The computer-implemented method of claim 3, further comprising clearing a list of threads that have read the memory location since the previous last write.

6. The computer-implemented method of claim 1, wherein the access of the memory location is a read, wherein updating the context associated with the first thread includes adding a local read indicator to the context of the first thread, and wherein the method further comprises adding a remote read indicator to a context of a last thread to write to the memory location.

7. The computer-implemented method of claim 6, further comprising adding the first thread to a list of threads that have read the memory location since the last write.

8. The computer-implemented method of claim 1, wherein updating a context associated with the first thread includes pushing an indicator onto a FIFO context queue associated with the first thread.

9. The computer-implemented method of claim 8, wherein the FIFO context queue has a predetermined length.

10. A computing device configured to build a context-aware communication graph by:

detecting an access of a memory location by a first instruction of a first thread;

updating a context associated with the first thread; and

in response to determining that a second instruction of a second thread different from the first thread was a last thread to write to the memory location;

adding an edge to the context-aware communication graph, the edge including the context associated with the first thread, a sink identifying the first instruction, a source identifying the second instruction, and a context associated with the second thread.

11. The computing device of claim 10, wherein the edge includes a timestamp of execution of the source instruction and a timestamp of execution of the sink instruction.

12. The computing device of claim 10, wherein the access of the memory location is a write, wherein updating the context associated with the first thread includes adding a local write indicator to the context of the first thread, and wherein the computing device is further configured to add a remote write indicator to a context of at least one thread other than the first thread.

13. The computing device of claim 12, wherein adding a remote write indicator to a context of at least one other thread other than the first thread includes adding a remote write indicator to a context of at least one thread other than the first thread that read the memory location since the last write.

14. The computing device of claim 12, wherein the computing device is further configured to clear a list of threads that have read the memory location since the previous last write.

15. The computing device of claim 10, wherein the access of the memory location is a read, wherein updating the context associated with the first thread includes adding a local read indicator to the context of the first thread, and wherein the computing device is further configured to add a remote read indicator to a context of a last thread to write to the memory location.

16. The computing device of claim 15, wherein the computing device is further configured to add the first thread to a list of threads that have read the memory location since the last write.

17. The computing device of claim 10, wherein updating a context associated with the first thread includes pushing an indicator onto a FIFO context queue associated with the first thread.

18. The computing device of claim 17, wherein the FIFO context queue has a predetermined length.

19. A nontransitory computer readable medium having computer-executable instructions stored thereon that, in response to execution by one or more processors of a computing device, cause the computing device to perform actions for building a context-aware communication graph, the method comprising:

detecting an access of a memory location by a first instruction of a first thread;

updating a context associated with the first thread; and

in response to determining that a second instruction of a second thread different from the first thread was a last thread to write to the memory location;

adding an edge to the context-aware communication graph, the edge including the context associated with the first thread, a sink identifying the first instruction, a source identifying the second instruction, and a context associated with the second thread.