Semmle 1.21
Skip to end of metadata
Go to start of metadata

Name: Cyclic lock order dependency

Description: Locking mutexes in different orders in different threads can cause deadlock.

ID: cpp/lock-order-cycle

Kind: problem

Severity: error

Query: LockOrderCycle.ql
/**
 * @name Cyclic lock order dependency
 * @description Locking mutexes in different orders in different
 *              threads can cause deadlock.
 * @kind problem
 * @id cpp/lock-order-cycle
 * @problem.severity error
 * @tags security
 *       external/cwe/cwe-764
 *       external/cwe/cwe-833
 */
import cpp
import semmle.code.cpp.commons.Synchronization
import LockFlow

/**
 * Gets a variable that might be locked while a lock on `v` is held.
 *
 * For example, with
 * ```
 * x.lock()
 * y.lock()
 * x.unlock()
 * y.unlock()
 *```
 * `x` is already locked when `y.lock()` is called, so `y` is a result
 * of `lockSuccessor(x)`. If you consider this an edge from `x` to `y`
 * in a directed graph, then a cycle in the graph indicates a potential
 * source of deadlock. The dining philosophers are the classic example.
 */
Variable lockSuccessor(Variable v) {
  exists (FunctionCall call
  | lockedOnEntry(v.getAnAccess(), call) and
    lockedInCall(result.getAnAccess(), call))
}

from Variable v1, Variable v2
where v1 != v2 and lockSuccessor+(v1) = v2 and lockSuccessor+(v2) = v1
select v1, "Mutex " + v1 + " has a cyclic lock order dependency with $@.", v2, "mutex " + v2

Deadlock can occur when two or more threads each attempt to lock multiple mutexes, but not in the same order. A famous example of this is the "Dining Philosophers Problem" (see references below). In this example, deadlock occurs when all five philosophers simultaneously pick up the fork to their left because then none of them can pick up the fork to their right. A simple solution is to assign an order to the mutexes. If the philosophers always pick up the lower numbered fork first, rather than the fork to their left, then deadlock cannot occur.

In general, we can build a graph of the order in which the mutexes are locked. For example, if one of the threads locks mutex A first and B second (while A is still locked), then we add a graph edge from A to B. If the resulting graph contains a cycle then there is a possibility of deadlock. The graph for the dining philosophers example contains a cycle because each philosopher creates a graph edge from their left fork to their right fork.

Recommendation

If multiple mutexes need to be locked simultaneously, then make sure that all threads lock them in the same order.

Example

In this example, f1 locks mtx1 first and mtx2 second, but f2 locks them in the opposite order. If f1 and f2 are run simultaneously in separate threads then they could cause a deadlock.

std::mutex mtx1;
std::mutex mtx2;

void f1() {
  // GOOD: lock mtx1 before mtx2.
  mtx1.lock();
  mtx2.lock();
  printf("f1");
  mtx2.unlock();
  mtx1.unlock();
}

void f2() {
  // BAD: lock mtx2 before mtx1.
  mtx2.lock();
  mtx1.lock();
  printf("f2");
  mtx1.unlock();
  mtx2.unlock();
}

References