Lock Hierarchy Violation

Occurs when two or more locks are acquired in a different order in two task executions, potentially leading to a deadlock when the program's tasks execute in parallel.

A Lock hierarchy violation problem indicates the following timeline:

Task 1

  1. Acquire lock A.

  2. Acquire lock B.

  3. Release lock B.

  4. Release lock A.

Task 2

  1. Acquire lock B.

  2. Acquire lock A.

  3. Release lock A.

  4. Release lock B.

If these time lines are interleaved when the two tasks execute in parallel, a Deadlock occurs:

  1. Task 1: Acquire lock A.

  2. Task 2: Acquire lock B.

  3. Task 1: Try to acquire lock B; wait until task 2 releases it.

  4. Task 2: Try to acquire lock A; wait until task 1 releases it.

The Dependencies tool reports a Lock hierarchy violation as multiple problems in a problem set. Each problem shows a portion of the Lock hierarchy violation from the perspective of a single thread.

Lock hierarchy violation problems are the most common cause of Deadlock problems, and a report of a Lock hierarchy violation problem indicates a Deadlock problem might occur when the target executes in parallel.

Syntax

Problem type: Lock hierarchy violation

ID

Code Location

Description

1

Allocation site

If present, represents the location and its associated call stack where the synchronization object acquired by a thread (usually the object acquired first) was created.

2

Parallel site

If present, represents the location and associated call stack of the parallel site containing the Lock Hierarchy Violation problem.

3

Lock owned

Represents the location and associated call stack where a task acquired a lock.

4

Lock owned

Represents the location and associated call stack where a task acquired a second lock while the task still held the first lock.

Example

// in task 1

ANNOTATE_LOCK_ACQUIRE(&lahv_lock1);
ANNOTATE_LOCK_ACQUIRE(&lahv_lock2); /* lock hierarchy violation */
ANNOTATE_LOCK_RELEASE(&lahv_lock2);
ANNOTATE_LOCK_RELEASE(&lahv_lock1);

// in task 2

ANNOTATE_LOCK_ACQUIRE(&lahv_lock2);
ANNOTATE_LOCK_ACQUIRE(&lahv_lock1); /* lock hierarchy violation */
ANNOTATE_LOCK_RELEASE(&lahv_lock1);
ANNOTATE_LOCK_RELEASE(&lahv_lock2);

Possible Correction Strategies

Determine if interleaving is possible, or whether some other synchronization exists that might prevent interleaving. If interleaving is possible, consider the following options.

Use a single lock instead of multiple locks:

// in task 1

ANNOTATE_LOCK_ACQUIRE(&lahv_lock1);
a++;
b += a;
ANNOTATE_LOCK_RELEASE(&lahv_lock1);

// in task 2

ANNOTATE_LOCK_ACQUIRE(&lahv_lock2); 
b += x[i];
a -= b;
ANNOTATE_LOCK_RELEASE(&lahv_lock2); 

Try to define a consistent order for your locks, so that any task that acquires the same set of locks, will acquire them in the same order:

// in task 1

ANNOTATE_LOCK_ACQUIRE(&lahv_lock1);
a++;
b += a;
ANNOTATE_LOCK_RELEASE(&lahv_lock1);

// in task 2

ANNOTATE_LOCK_ACQUIRE(&lahv_lock2); 
b += x[i];
a -= b;
ANNOTATE_LOCK_RELEASE(&lahv_lock2);

When a task acquires multiple locks, make sure that it always releases them in the opposite order that it acquired them.

For more complete information about compiler optimizations, see our Optimization Notice.