Happens-before-based dynamic concurrency analysis for actor-based programs

Patent metadata

Field	Value
Publication number	US-10719425-B2
Application number	US-201816007983-A
Country	US
Kind code	B2
Filing date	Jun 13, 2018
Priority date	Jun 13, 2018
Publication date	Jul 21, 2020
Grant date	Jul 21, 2020

Abstract

A method may include generating, for a concurrent application, an execution trace that includes operations, extracting actor pairs from the execution trace, assigning each of the operations to an actor pair, and generating vector clocks for the operations. Each vector clock may include a clock value for each of the actor pairs.

First claim

What is claimed is:

1. A method, comprising:
generating, for a concurrent application, an execution trace comprising a plurality of operations comprising a first operation and a second operation;
extracting, from the execution trace, a plurality of actor pairs comprising a first actor pair and a second actor pair, wherein each of the plurality of actor pairs comprises a sender and a receiver, wherein the sender sends a message to the receiver, and wherein the receiver performs an operation of the plurality of operations in response to receiving the message;
assigning the first operation to the first actor pair and the second operation to the second actor pair;
generating a plurality of vector clocks for the plurality of operations, each vector clock comprising a clock value for each of the plurality of actor pairs; and
determining that the first operation is synchronized with the second operation by determining that the receiver of the second actor pair sends a message that is received by the receiver of the first actor pair.

2. The method of claim 1 , wherein the plurality of vector clocks comprises a first vector clock for the first operation and a second vector clock for the second operation, the method further comprising:
determining whether the first operation and the second operation are concurrent by comparing the first vector clock and the second vector clock; and
in response to determining that the first operation and the second operation are concurrent, identifying a potential defect in the concurrent application.

3. The method of claim 2 , wherein comparing the first vector clock and the second vector clock comprises:
comparing the clock value for one or more of the plurality of actor pairs of the first vector clock with the clock value for the corresponding actor pair of the second vector clock.

4. The method of claim 2 , further comprising:
in response to determining that the first operation is synchronized with the second operation, joining the first vector clock with the second vector clock.

5. The method of claim 2 ,
wherein the execution trace indicates, for each of the plurality of operations, a thread of a computer system that executed the operation, and
wherein determining that the first operation and the second operation are concurrent is independent of the thread that executed the first operation and the thread that executed the second operation.

6. The method of claim 2 ,
wherein the plurality of vector clocks further comprises a previous vector clock for a previous operation of the plurality of operations,
wherein the previous operation is assigned to the first actor pair,
wherein the previous operation is executed before the first operation in the execution trace, and
wherein generating the first vector clock comprises:
copying each clock value of the previous vector clock into the first vector clock; and
incrementing, in the first vector clock, the clock value corresponding to the first actor pair.

7. The method of claim 1 , wherein the receiver of the second actor pair is the same as the sender of the first actor pair.

8. A system, comprising:
a memory, coupled to a processor, comprising a repository comprising:
a concurrent application,
an execution trace comprising a plurality of operations comprising a first operation and a second operation,
a plurality of actor pairs comprising a first actor pair and a second actor pair, wherein each of the plurality of actor pairs comprises a sender and a receiver, wherein the sender sends a message to the receiver, and wherein the receiver performs an operation of the plurality of operations in response to receiving the message, and
a plurality of vector clocks for the plurality of operations, each of the plurality of vector clocks comprising a clock value for each of the plurality of actor pairs, the plurality of vector clocks comprising a first vector clock for the first operation and a second vector clock for the second operation;

an execution trace manager executing on the processor and using the memory, configured to:
generate, for the concurrent application, the execution trace;
extract the plurality of actor pairs from the execution trace;
assign the first operation to the first actor pair and the second operation to the second actor pair; and
determine that the first operation is synchronized with the second operation by determining that the receiver of the second actor pair sends a message that is received by the receiver of the first actor pair; and

a vector clock generator executing on the processor and using the memory, configured to generate the plurality of vector clocks for the plurality of operations.

9. The system of claim 8 , further comprising:
a defect detector configured to:
determine whether the first operation and the second operation are concurrent by comparing the first vector clock and the second vector clock; and
in response to determining that the first operation and the second operation are concurrent, identify a potential defect in the concurrent application.

10. The system of claim 9 , wherein the defect detector is configured to compare the first vector clock and the second vector clock by comparing the clock value for one or more of the plurality of actor pairs of the first vector clock with the clock value for the corresponding actor pair of the second vector clock.

11. The system of claim 9 ,
wherein the execution trace indicates, for each of the plurality of operations, a thread of a computer system that executed the operation, and
wherein determining that the first operation and the second operation are concurrent is independent of the thread that executed the first operation and the thread that executed the second operation.

12. The system of claim 8 , wherein the vector clock generator is further configured to:
in response to determining that the first operation is synchronized with the second operation, join the first vector clock with the second vector clock.

13. The system of claim 8 ,
wherein the receiver of the second actor pair is the same as the sender of the first actor pair.

14. The system of claim 8 ,
wherein the plurality of vector clocks further comprises a previous vector clock for a previous operation of the plurality of operations,
wherein the previous operation is assigned to the first actor pair,
wherein the previous operation is executed before the first operation in the execution trace, and
wherein the vector clock generator is further configured to generate the first vector clock by:
copying each clock value of the previous vector clock into the first vector clock; and
incrementing, in the first vector clock, the clock value corresponding to the first actor pair.

15. A non-transitory computer readable medium comprising instructions that, when executed by a processor, perform:
generating, for a concurrent application, an execution trace comprising a plurality of operations comprising a first operation and a second operation;
extracting, from the execution trace, a plurality of actor pairs comprising a first actor pair and a second actor pair, wherein each of the plurality of actor pairs comprises a sender and a receiver, wherein the sender sends a message to the receiver, and wherein the receiver performs an operation of the plurality of operations in response to receiving the message;
assigning the first operation to the first actor pair and the second operation to the second actor pair;
generating a plurality of vector clocks for the plurality of operations, each vector clock comprising a clock value for each of the plu

Assignees

• Oracle Int Corp

Inventors

• Allen Nicholas John
• Zhao Yang
• Cifuentes Cristina Nicole
• Keynes Nathan Robert Albert

Classifications

• G06F11/366

  using diagnostics (G06F11/0703 takes precedence) · CPC title

• G06F11/3636 Primary

  by tracing the execution of the program · CPC title