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

• US 20080005742A1
• Filed: 06/30/2006
• Published: 01/03/2008
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Ma, Zhiqiang
• Granted Patent: US 8,069,445 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• 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:

recording a set of currently-held synchronization primitives and a set of currently-acquired synchronization primitives if a thread acquires a synchronization primitive;

searching for a lock acquisition hierarchy violation; and

reporting the lock acquisition hierarchy violation if the lock acquisition hierarchy violation is found.

2. The method of claim 1, further comprising:

noting a possibly-unsafe resource release if a synchronization primitive that was not acquired upon entry to a current synchronization state is released;

reporting an unsafe resource release if a synchronization primitive is acquired after the possibly-unsafe resource release is recorded.

3. The method of claim 2, further comprising:

updating the current synchronization state of the thread.

4. The method of claim 1, further comprising:

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; and

wherein searching for a lock acquisition hierarchy violation comprises searching for a cycle in the graph.

5. The method of claim 4, further comprising:

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

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

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

7. The method of claim 1, further comprising:

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

8. A computer-readable medium containing instructions to cause a programmable machine to perform operations comprising:

building a data structure to represent synchronization primitive operations of a plurality of threads of a multi-threaded program;

adding a node to the data structure if one of the plurality of threads acquires a synchronization primitive;

analyzing the data structure to detect a lock acquisition hierarchy violation; and

reporting the lock acquisition hierarchy violation.

9. The computer-readable medium of claim 8 wherein the node is to represent an acquisition of a first set of synchronization primitives by a thread that holds a second set of synchronization primitives.

10. The computer-readable medium of claim 8 wherein analyzing the data structure comprises searching for a cycle in the data structure.

11. The computer-readable medium of claim 9, containing additional instructions to cause the programmable machine to perform further operations comprising:

reusing the node if one of the plurality of threads acquires the first set of synchronization primitives while holding the second set of synchronization primitives.

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

maintaining an association between a thread and a node of the data structure; and

noting a possible unsafe resource release if the thread releases a synchronization primitive and if the synchronization primitive was not acquired by the thread when the thread became associated with the node.

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

reporting an unsafe resource release if the thread acquires a synchronization primitive while holding a synchronization primitive.

14. The computer-readable medium of claim 8, 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.

15. 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 lock acquisition hierarchy violation; and

reporting logic to emit a warning about the violation.

16. The system of claim 15 wherein the analysis logic is to further detect a potentially unsafe lock release;

and the analysis logic is to emit a warning about the potentially unsafe lock release if a resource is acquired.

17. The system of claim 15, further comprising:

a data structure to record a plurality of synchronization states of the multi-threaded program;

wherein

the analysis logic is to search for a cycle in the data structure.

18. The system of claim 17 wherein the data collection logic re-uses a node in the data structure.

19. The system of claim 15 wherein the reporting logic is to identify at least one of a thread, an object location, or a source code location associated with the violation.

20. The system of claim 15 wherein the analysis logic detects a lock acquisition hierarchy violation if the multi-threaded program executes without deadlock.