SYSTEMS AND METHODS FOR FINDING CONCURRENCY ERRORS

• US 20120144372A1
• Filed: 12/06/2011
• Published: 06/07/2012
• 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 8,832,659 B2
• Time in Patent Office: Days
• US Class Current: 717/124
• 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 nontransitory computer-readable medium having computer-executable instructions stored thereon that, if executed by one or more processors of a computing device, cause the computing device to perform actions to analyze a set of context-aware communication graphs for debugging, the actions comprising:

creating, by the computing device, a set of aggregate reconstructions based on edges of the set of communication graphs;

ranking, by the computing device, the aggregate reconstructions in order of likelihood of being associated with a failed execution; and

presenting, by the computing device, one or more highly ranked aggregate reconstructions.

2. The computer-readable medium of claim 1, wherein the actions further comprise:

selecting edges of the set of communication graphs for creating aggregate reconstructions based on a correlation of edges of the set of communication graphs with failed executions.

3. The computer-readable medium of claim 2, wherein selecting edges includes determining a correlation for one or more edges of the set of communication graphs with failed executions.

4. The computer-readable medium of claim 3, wherein determining the correlation for an edge of the set of communication graphs with failed executions comprises:

determining a failed execution fraction for the edge;

determining a correct execution fraction for the edge; and

determining a failed frequency ratio based on the failed execution fraction and the correct execution fraction.

5. The computer-readable medium of claim 1, wherein each aggregate reconstruction includes an edge, wherein ranking the aggregate reconstructions includes calculating a score for each aggregate reconstruction, and wherein the score is based on at least one of:

a correlation of the edge of the aggregate reconstruction with failed executions;

a difference in interleaving around the edge between failed executions and correct executions; and

a level of consistency for the aggregate reconstruction.

6. The computer-readable medium of claim 5, wherein the difference in interleaving around the edge between failed executions and correct executions is calculated by:

calculating a number of failed contexts associated with a source node of the edge and a sink node of the edge from failed executions;

calculating a number of correct contexts associated with the source node and the sink node from correct executions; and

calculating a context variation ratio based on the number of failed contexts and the number of correct contexts.

7. The computer-readable medium of claim 5, wherein the level of consistency for the aggregate reconstruction is calculated by:

calculating a first total of confidence values for each prefix node in the aggregate reconstruction;

calculating a second total of confidence values for each body node in the aggregate reconstruction;

calculating a third total of confidence values for each suffix node in the aggregate reconstruction;

calculating a sum of the first, second and third total confidence values; and

dividing the sum by a sum of a total number of prefix nodes, a total number of body nodes, and a total number of suffix nodes.

8. 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.

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

10. The computer-implemented method of claim 8, 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.

11. The computer-implemented method of claim 10, 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.

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

13. The computer-implemented method of claim 8, 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.

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

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

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

17. A computing device for detecting concurrency bugs, the device comprising:

at least two processing cores;

at least two cache memories, wherein each cache memory is associated with at least one processing core, and wherein each cache memory is associated with coherence logic;

a coherence interconnect communicatively coupled to each of the cache memories; and

a communication graph data store;

wherein the coherence logic is configured to add edges to a communication graph stored in the communication graph data store based on coherence messages transmitted on the coherence interconnect.

18. The computing device of claim 17, wherein each cache memory includes a plurality of cache lines, each cache line including metadata associated with a last write to the cache line.

19. The computing device of claim 18, wherein the metadata includes a writer instruction address.

20. The computing device of claim 19, wherein the metadata includes a writer context.

21. The computing device of claim 20, wherein the metadata further includes a timestamp.

22. The computing device of claim 17, wherein each processing core includes a context register.

23. The computing device of claim 17, wherein the coherence logic is configured according to an MESI cache coherence protocol.

24. The computing device of claim 23, wherein the MESI cache coherence protocol includes:

a read reply that includes a writer context and a writer instruction address of an associated cache line; and

an invalidate reply that includes a writer context and a writer instruction address of an associated cache line.

25. The computing device of claim 24,

wherein the coherence logic is configured to add an edge to a communication graph stored in the communication graph data store upon detecting a read reply;

wherein the edge includes a source node and a sink node;

wherein the source node includes the writer context and the writer instruction address of the read reply; and

wherein the sink node includes a reader instruction and a context of a thread that caused a cache miss associated with the read reply.

26. The computing device of claim 24,

wherein the coherence logic is configured to add an edge to a communication graph stored in the communication graph data store upon detecting an invalidate reply;

wherein the edge includes a source node and a sink node;

wherein the source node includes the writer context and the writer instruction address of the invalidate reply; and

wherein the sink node includes a writer instruction and a context of a thread that caused the invalidate request to be generated.