UNDER CONSTRUCTION
Mutexes are used to prevent multiple threads from causing a data race by accessing shared resources 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.).
- Mutual exclusion
- Hold and wait
- No preemption
- Circular wait
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.
...
Code Block | ||||
---|---|---|---|---|
| ||||
#include <stdlib.h><mutex> #include <threads.h><thread> typedefclass structBankAccount { int balance; public: mtx_t balance_mutex; } bank_account; typedef struct { bank_account *fromstd::mutex balanceMutex; BankAccount() = delete; bank_account *to; int amount; } transaction; void create_bank_account(bank_account **ba, int initial_amount) { bank_account *nba = (bank_account *)malloc( sizeof(bank_account) ); if (nba == NULL) { /* Handle error */ } nba->balance = initial_amount; if (thrd_success != mtx_init(&nba->balance_mutex, mtx_plain)) { /* Handle error */ } *ba = nba; } int deposit(void *ptr) { transaction *args = (transaction *)ptr; if (thrd_success != mtx_lock(&args->from->balance_mutex)) { /* Handle error */ } /*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 (args->from->balancefrom->get_balance() < args->amountamount) { if (thrd_success != mtx_unlock(&args->from->balance_mutex)) { /* Handle error */ } return -1; /*/ Indicate error */ } if (thrd_success != mtxstd::lock_guard<std::mutex> to_lock(&args->to->balance_mutex)) { /* Handle error */ } args->from->balance -= args->amountto->balanceMutex); from->set_balance(from->get_balance() - amount); args->to->balance += args->amount; if (thrd_success != mtx_unlock(&args->from->balance_mutex)) { /* Handle error */ } if (thrd_success != mtx_unlock(&args->to->balance_mutex)) { /* Handle error */ } free(ptr);to->set_balance(to->get_balance() + amount); return 0; } intvoid main(void) { thrd_t thr1, thr2; transaction *arg1; transaction *arg2; bank_accountf(BankAccount *ba1; , BankAccount bank_account *ba2; create_bank_account(&ba1, 1000); create_bank_account(&ba2, 1000); arg1 = (transaction *)malloc(sizeof(transaction)); if (arg1 == NULL) { /* Handle error */ Perform } arg2 = (transaction *)malloc(sizeof(transaction));the deposits. ifstd::thread thr1(arg2 == NULL) { /* Handle error */ } arg1->from = ba1; arg1->to = ba2; arg1->amount = 100; arg2->from = ba2; arg2->to = ba1; arg2->amount = 100; /* Perform the deposits */ if (thrd_success != thrd_create(&thr1, deposit, (void *)arg1)) { /* Handle error */ } if (thrd_success != thrd_create(&thr2, deposit, (void *)arg2)) { /* Handle error */ } return 0; } |
...
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 bank_account
BankAccount
ID, which is set when the bank_account struct
BankAccount
object is initialized.
Code Block | ||||
---|---|---|---|---|
| ||||
#include <stdlib.h><atomic> #include <mutex> #include <threads.h><thread> typedefclass structBankAccount { int balance; mtx_t balance_mutex; static std::atomic<unsigned int> globalId; /* Should not change after initialization */ const unsigned int id; } bank_account int balance; public: typedef struct { std::mutex balanceMutex; bank_account *fromBankAccount() = delete; bank_account *to; int amount; } transaction; explicit BankAccount(int initialAmount) : id(globalId++), balance(initialAmount) {} unsigned int globalget_id = 1; void create_bank_account(bank_account **ba,() 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 initial_amount) { bank_accountstd::mutex *nbafirst; = (bank_account *)malloc( sizeof(bank_account) ); if (nba == NULL std::mutex *second; if (from->get_id() == to->get_id()) { return -1; /*/ HandleIndicate error */ } nba->balance = initial_amount; if (thrd_success != mtx_init(&nba->balance_mutex, mtx_plain// Ensure proper ordering for locking. if (from->get_id() < to->get_id()) { /*first Handle error */= &from->balanceMutex; } nba->idsecond = global_id++&to->balanceMutex; *ba = nba; } int deposit(void *ptr) else { transaction *argsfirst = (transaction *)ptr&to->balanceMutex; int resultsecond = &from-1>balanceMutex; mtx_t *first} std::lock_guard<std::mutex> firstLock(*first); mtx_t std::lock_guard<std::mutex> secondLock(*second); // Check for enough balance to transfer. if (args->from->id == args->to->id) {from->get_balance() >= amount) { from->set_balance(from->get_balance() - amount); return -1; /* Indicate error */ } /* Ensure proper ordering for locking */ if (args->from->id < args->to->id) { first = &args->from->balance_mutex; second = &args->to->balance_mutex; } else { first = &args->to->balance_mutex; second = &args->from->balance_mutex; } if (thrd_success != mtx_lock(first)) { /* Handle error */ } if (thrd_success != mtx_lock(second)) { /* Handle error */ } /* Not enough balance to transfer */ if (args->from->balance >= args->amountto->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.
Code Block | ||||
---|---|---|---|---|
| ||||
#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) { args->from->balancefrom->set_balance(from->get_balance() -= args->amountamount); args->to->balanceto->set_balance(to->get_balance() += args->amountamount); result =return 0; } if (thrd_success != mtx_unlock(second))return -1; } void f(BankAccount *ba1, BankAccount *ba2) { //* HandlePerform errorthe */deposits. } if (thrd_success != mtx_unlock(first)) { /* Handle error */ } free(ptr); return result; } 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 Vulnerabilities
...
Automated Detection
Tool | Version | Checker | Description | ||||||
---|---|---|---|---|---|---|---|---|---|
CodeSonar |
| CONCURRENCY.LOCK.ORDER | Conflicting lock order | ||||||
Coverity | 6.5 | DEADLOCK | Fully implemented | ||||||
Helix QAC |
| C++1772, C++1773 | |||||||
Parasoft C/C++test |
| CERT_CPP-CON53-a | Do not acquire locks in different order | |||||||
Polyspace Bug Finder |
| CERT C++: CON53-CPP | Checks for deadlocks |
Related Vulnerabilities
Search for vulnerabilities resulting from the violation of this rule on the CERT website.
Related Guidelines
CERT Oracle Secure Coding Standard for Java | LCK07-J. Avoid deadlock by requesting and releasing locks in the same order |
MITRE CWE | CWE-764, Multiple Locks of a Critical Resource |
...
Bibliography
[ISO/IEC 14882-2014] | Subclause 30.4, "Mutual Exclusion" |