CertC++-CON53

Avoid deadlock by locking in a predefined order

Required inputs: IR

Mutexes are used to prevent multiple threads from causing a data race by accessing the same shared resource at the same time. Sometimes, when locking mutexes, multiple threads hold each other's lock, and the program consequently deadlocks. Four conditions are required for deadlock to occur:

  • mutual exclusion (At least one nonshareable resource must be held.),
  • hold and wait (A thread must hold a resource while awaiting availability of another resource.),
  • no preemption (Resources cannot be taken away from a thread while they are in-use.), and
  • circular wait (A thread must await a resource held by another thread which is, in turn, awaiting a resource held by the first thread.).

Deadlock needs all four conditions, so preventing deadlock requires preventing any one of the four conditions. One simple solution is to lock the mutexes in a predefined order, which prevents circular wait.

Noncompliant Code Example

The behavior of this noncompliant code example depends on the runtime environment and the platform's scheduler. The program is susceptible to deadlock if thread thr1 attempts to lock ba2's mutex at the same time thread thr2 attempts to lock ba1's mutex in the deposit() function. 

#include <mutex>
#include <thread>

class BankAccount {
  int balance;
public:
  std::mutex balanceMutex;
  BankAccount() = delete;
  explicit BankAccount(int initialAmount) : balance(initialAmount) {}
  int get_balance() const { return balance; }
  void set_balance(int amount) { balance = amount; }
};

int deposit(BankAccount *from, BankAccount *to, int amount) {
  std::lock_guard<std::mutex> from_lock(from->balanceMutex);

  // Not enough balance to transfer.
  if (from->get_balance() < amount) {
    return -1; // Indicate error
  }
  std::lock_guard<std::mutex> to_lock(to->balanceMutex);

  from->set_balance(from->get_balance() - amount);
  to->set_balance(to->get_balance() + amount);

  return 0;
}

void f(BankAccount *ba1, BankAccount *ba2) {
  // Perform the deposits.
  std::thread thr1(deposit, ba1, ba2, 100);
  std::thread thr2(deposit, ba2, ba1, 100);
  thr1.join();
  thr2.join();
}
Compliant Solution (Manual Ordering)

This compliant solution eliminates the circular wait condition by establishing a predefined order for locking in the deposit() function. Each thread will lock on the basis of the BankAccount ID, which is set when the BankAccount object is initialized. 

#include <atomic>
#include <mutex>
#include <thread>

class BankAccount {
  static std::atomic<unsigned int> globalId;
  const unsigned int id;
  int balance;
public:
  std::mutex balanceMutex;
  BankAccount() = delete;
  explicit BankAccount(int initialAmount) : id(globalId++), balance(initialAmount) {}
  unsigned int get_id() const { return id; }
  int get_balance() const { return balance; }
  void set_balance(int amount) { balance = amount; }
};

std::atomic<unsigned int> BankAccount::globalId(1);

int deposit(BankAccount *from, BankAccount *to, int amount) {
  std::mutex *first;
  std::mutex *second;

  if (from->get_id() == to->get_id()) {
    return -1; // Indicate error
  }

  // Ensure proper ordering for locking.
  if (from->get_id() < to->get_id()) {
    first = &from->balanceMutex;
    second = &to->balanceMutex;
  } else {
    first = &to->balanceMutex;
    second = &from->balanceMutex;
  }
  std::lock_guard<std::mutex> firstLock(*first);
  std::lock_guard<std::mutex> secondLock(*second);

  // Check for enough balance to transfer.
  if (from->get_balance() >= amount) {
    from->set_balance(from->get_balance() - amount);
    to->set_balance(to->get_balance() + amount);
    return 0;
  }
  return -1;
}
 
void f(BankAccount *ba1, BankAccount *ba2) {
  // Perform the deposits.
  std::thread thr1(deposit, ba1, ba2, 100);
  std::thread thr2(deposit, ba2, ba1, 100);
  thr1.join();
  thr2.join();
}
Compliant Solution ( std::lock())

This compliant solution uses Standard Template Library facilities to ensure that deadlock does not occur due to circular wait conditions. The  std::lock() function takes a variable number of lockable objects and attempts to lock them such that deadlock does not occur [ ISO/IEC 14882-2014]. In typical implementations, this is done by using a combination of  lock(),  try_lock(), and unlock() to attempt to lock the object and backing off if the lock is not acquired, which may have worse performance than a solution that locks in predefined order explicitly. 

#include <mutex>
#include <thread>

class BankAccount {
  int balance;
public:
  std::mutex balanceMutex;
  BankAccount() = delete;
  explicit BankAccount(int initialAmount) : balance(initialAmount) {}
  int get_balance() const { return balance; }
  void set_balance(int amount) { balance = amount; }
};

int deposit(BankAccount *from, BankAccount *to, int amount) {
  // Create lock objects but defer locking them until later.
  std::unique_lock<std::mutex> lk1(from->balanceMutex, std::defer_lock);
  std::unique_lock<std::mutex> lk2(to->balanceMutex, std::defer_lock);

  // Lock both of the lock objects simultaneously.
  std::lock(lk1, lk2);

  if (from->get_balance() >= amount) {
    from->set_balance(from->get_balance() - amount);
    to->set_balance(to->get_balance() + amount);
    return 0;
  }
  return -1;
}
 
void f(BankAccount *ba1, BankAccount *ba2) {
  // Perform the deposits.
  std::thread thr1(deposit, ba1, ba2, 100);
  std::thread thr2(deposit, ba2, ba1, 100);
  thr1.join();
  thr2.join();
}
Risk Assessment

Deadlock prevents multiple threads from progressing, halting program execution. A denial-of-service attack is possible if the attacker can create the conditions for deadlock.

Rule Severity Likelihood Remediation Cost Priority Level
CON53-CPP Low Probable Medium P4 L3
Related Guidelines
CERT Oracle Secure Coding Standard for Java LCK07-J. Avoid deadlock by requesting and releasing locks in the same order
SEI CERT C Coding Standard CON35-C. Avoid deadlock by locking in a predefined order
MITRE CWE CWE-764, Multiple Locks of a Critical Resource
Bibliography
[ ISO/IEC 14882-2014] Subclause 30.4, "Mutual Exclusion"
Subclause 30.4.3, "Generic Locking Algorithms"
Excerpt from SEI CERT C++ Coding Standard [https://cmu-sei.github.io/secure-coding-standards/sei-cert-cpp-coding-standard/rules/concurrency-con/con53-cpp], Copyright (C) 1995-2026 Carnegie Mellon University. See section 9.4. "3rd-Party Licenses" in the documentation for full details.

Possible Messages

Key

Text

Severity

Disabled

deadlock

Unfavorable locking sequence could lead to deadlock.

None

False

Options

additional_lock_api_callables

additional_lock_api_callables

Type: typing.Callable[[bauhaus.ir.Graph], typing.Iterable[tuple[bauhaus.rules.parallelism.locksets.LockApiCallableKind, str]]] | None

Default: None

Python callable that generates additional [enter|exit]_additional_functions from the ir.Graph.
 

enter_critical_functions

enter_critical_functions

Type: set[bauhaus.analysis.config.QualifiedName]

Default: {'mtx_lock', 'std::_Mutex_base::lock', 'std::lock_guard::lock_guard', 'std::mutex::lock'}

Set of function names to enter a critical region.
 

enter_critical_macros

enter_critical_macros : set[bauhaus.analysis.config.MacroName] = set()

Set of macro names to enter a critical region (macros must expand to asm() statement).
 

exit_critical_functions

exit_critical_functions

Type: set[bauhaus.analysis.config.QualifiedName]

Default: {'mtx_unlock', 'std::_Mutex_base::unlock', 'std::lock_guard::~lock_guard', 'std::mutex::unlock'}

Set of function names to exit a critical region.
 

exit_critical_macros

exit_critical_macros : set[bauhaus.analysis.config.MacroName] = set()

Set of macro names to exit a critical region (macros must expand to asm() statement).
 

nested_critical_regions

nested_critical_regions : bool = True

If set to true, critical regions nest; if set to false, a single exit-critical-region terminates all open critical regions.