Method and apparatus for detecting lock acquisition hierarchy violations and unsafe lock releases

• US 8,069,445 B2
• Filed: 06/30/2006
• Issued: 11/29/2011
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Ma, Zhiqiang
• Primary Examiner(s): An; Meng
• Assistant Examiner(s): KAWSAR, ABDULLAH AL
• Application Number:
  US11/480,141
• Publication Number:
  US 20080005742A1
• Time in Patent Office: 1,978 Days
• Field of Search: None
• US Class Current: 718/104
• CPC Class Codes: G06F 11/0715 in a system implementing multitasking multitasking per se G06F9/46
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06

Abstract

A thread analysis tool records a set of currently-held synchronization objects and currently-acquired objects when a thread acquires one or more objects, then searches for a lock acquisition hierarchy violation that may cause program deadlock. If a violation is found, it is reported to the user. Software to implement the methods of the analysis tool, and systems using the methods, are also described and claimed.

Claims

1. A method comprising:

for a first thread which acquires a synchronization primitive, recording a set of currently-held synchronization primitives and a set of currently-acquired synchronization primitives;

indicating a possibly-unsafe lock release when the first thread releases a resource set s of resource set elements r and one or more of the resource set elements r of the resource set s was not among a plurality of resource set elements acquired by the first thread on entry to the synchronization primitive previously acquired by the first thread;

constructing a graph of connected nodes, where a node indicates the set of currently-held synchronization primitives and the set of currently-acquired synchronization primitives;

searching the graph for a node to indicate the set of currently-held synchronization primitives and the set of currently-acquired synchronization primitives; and

searching for a lock acquisition hierarchy violation, in which a second thread acquires a partial acquisition hierarchy of the synchronization primitive previously acquired by the first thread, wherein searching for a lock acquisition hierarchy violation comprises searching for a cycle in the graph;

reporting the lock acquisition hierarchy violation; and

reporting the possibly-unsafe lock release.

2. The method of claim 1, wherein reporting the unsafe lock release comprises reporting the unsafe lock release when the first thread acquires a second synchronization primitive while the first thread is holding the synchronization primitive previously acquired in which the one or more of the resource set elements r of the resource set s was not among the plurality of resource set elements acquired by the first thread on entry to the synchronization primitive previously acquired by the first thread.

3. The method of claim 2, further comprising:

updating the current synchronization state of the first thread.

4. The method of claim 1, further comprising:

creating a new node if the searching operation returns no node.

5. The method of claim 1 wherein a cardinality of the set of currently-acquired synchronization primitives is one.

6. The method of claim 1, further comprising:

recording at least one of a thread identifier, a time, or an instruction pointer when the first thread or the second thread acquires a synchronization primitive.

7. A non-transitory computer-readable medium having instructions stored thereon to cause a programmable machine to perform operations comprising:

for a first thread which acquires a synchronization primitive, recording a set of currently-held synchronization primitives and a set of currently-acquired synchronization primitives;

indicating a possibly-unsafe lock release when the first thread releases a resource set s of resource set elements r and one or more of the resource set elements r of the resource set s was not among a plurality of resource set elements acquired by the first thread on entry to the synchronization primitive previously acquired by the first thread;

constructing a graph of connected nodes, where a node indicates the set of currently-held synchronization primitives and the set of currently-acquired synchronization primitives;

searching the graph for a node to indicate the set of currently-held synchronization primitives and the set of currently-acquired synchronization primitives; and

searching for a lock acquisition hierarchy violation, in which a second thread acquires a partial acquisition hierarchy of the synchronization primitive previously acquired by the first thread, wherein searching for a lock acquisition hierarchy violation comprises searching for a cycle in the graph;

reporting the lock acquisition hierarchy violation; and

reporting the possibly-unsafe lock release.

8. The non-transitory computer-readable medium of claim 7, wherein reporting the unsafe lock release comprises reporting the unsafe lock release when the first thread acquires a second synchronization primitive while the first thread is holding the synchronization primitive previously acquired in which the one or more of the resource set elements r of the resource set s was not among the plurality of resource set elements acquired by the first thread on entry to the synchronization primitive previously acquired by the first thread.

9. The non-transitory computer-readable medium of claim 7:

wherein constructing the graph of connected nodes comprises;

building a data structure to represent operations for a plurality of threads of a multi-threaded program associated with the synchronization primitive acquired by the first thread; and

wherein the non-transitory computer-readable medium includes additional instructions to cause the programmable machine to perform operations further comprising;

adding a node to the data structure for each one of the plurality of threads that acquires a synchronization primitive, and

reusing the node when one of the plurality of threads acquires the first set of synchronization primitives while holding a second set of synchronization primitives within the partial acquisition hierarchy acquired by the second thread.

10. The non-transitory computer-readable medium of claim 7, containing additional instructions to cause the programmable machine to perform further operations comprising:

maintaining an association between each of the first thread and the second thread and a corresponding node of the data structure.

11. The non-transitory computer-readable medium of claim 7, wherein reporting the unsafe lock release comprises reporting the unsafe lock release when the first thread acquires a second synchronization primitive while the first thread is holding the synchronization primitive previously acquired in which the one or more of the resource set elements r of the resource set s was not among the plurality of resource set elements acquired by the first thread on entry to the synchronization primitive previously acquired by the first thread.

12. The non-transitory computer-readable medium of claim 7, containing additional instructions to cause the programmable machine to perform further operations comprising:

instrumenting a multi-threaded program to monitor synchronization primitive operations of a plurality of threads of the program by introducing code into the program or into libraries utilized by the program, or both.

13. A system comprising:

a plurality of processors;

a multi-threaded program;

data collection logic to collect information about synchronization operations of the program;

analysis logic to examine the information and detect a first thread which acquires a synchronization primitive;

reporting logic to record a set of currently-held synchronization primitives and a set of currently-acquired synchronization primitives based on the detected first thread;

wherein the analysis logic to further indicate a possibly-unsafe lock release when the first thread releases a resource set s of resource set elements r and one or more of the resource set elements r of the resource set s was not among a plurality of resource set elements acquired by the first thread on entry to the synchronization primitive previously acquired by the first thread;

wherein the analysis logic to further construct a graph of connected nodes, where a node indicates the set of currently-held synchronization primitives and the set of currently-acquired synchronization primitives;

wherein the analysis logic to further search the graph for a node to indicate the set of currently-held synchronization primitives and the set of currently-acquired synchronization primitives;

wherein the analysis logic to further search for a lock acquisition hierarchy violation, in which a second thread acquires a partial acquisition hierarchy of the synchronization primitive previously acquired by the first thread, wherein the search for a lock acquisition hierarchy violation comprises a search for a cycle in the graph; and

wherein the reporting logic to further report the lock acquisition hierarchy violation and report the possibly-unsafe lock release.

14. The system of claim 13 wherein the analysis logic to further indicate a possibly-unsafe lock release comprises the analysis logic to further emit a warning about the potentially unsafe lock release when the first thread acquires a second synchronization primitive while the first thread is holding the synchronization primitive previously acquired in which the one or more of the resource set elements r of the resource set s was not among the plurality of resource set elements acquired by the first thread on entry to the synchronization primitive previously acquired by the first thread.

15. The system of claim 13:

wherein the analysis logic to construct the graph of connected nodes comprises the analysis logic to;

build a data structure to represent operations for a plurality of threads of a multi-threaded program associated with the synchronization primitive acquired by the first thread; and

wherein the analysis logic is to further;

add a node to the data structure for each one of the plurality of threads that acquires a synchronization primitive.

16. The system of claim 15 wherein the data collection logic re-uses a node in the data structure when one of the plurality of threads acquires the first set of synchronization primitives while holding a second set of synchronization primitives within the partial acquisition hierarchy acquired by the second thread.

17. The system of claim 13 wherein the reporting logic is to identify at least one of a thread, an object location, or a source code location associated with the lock acquisition hierarchy violation.

18. The system of claim 13 wherein the analysis logic detects the lock acquisition hierarchy violation when the multi-threaded program operates normally and runs to completion by executing without deadlock.