Systems and methods for finding concurrency errors
View Patent ↗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.
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;
wherein edges of the set of communication graphs represent communication events between threads;
wherein nodes of the set of communication graphs each include an instruction address and a context; and
wherein the context represents a sequence of communication events observed by a thread prior to the execution of an instruction at the instruction address regardless of the memory location involved in the sequence of communication events.
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 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;
wherein edges of the communication graph represent communication events between threads;
wherein nodes of the communication graph each include an instruction address and a context; and
wherein the context represents a sequence of communication events observed by a thread prior to the execution of an instruction at the instruction address regardless of the memory location involved in the sequence of communication events.
9. The computing device of claim 8 , wherein each cache memory includes a plurality of cache lines, each cache line including metadata associated with a last write to the cache line.
10. The computing device of claim 9 , wherein the metadata includes a writer instruction address.
11. The computing device of claim 10 , wherein the metadata includes a writer context.
12. The computing device of claim 11 , wherein the metadata further includes a timestamp.
13. The computing device of claim 8 , wherein each processing core includes a context register.
14. The computing device of claim 8 , wherein the coherence logic is configured according to an MESI cache coherence protocol.
15. The computing device of claim 14 , 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.
16. The computing device of claim 15 ,
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.
17. The computing device of claim 15 ,
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.