Mutexes are often used to prevent multiple threads from accessing critical causing a data race by accessing shared resources at the same time. Sometimes, when locking mutexes, multiple threads hold each other's lock, and the program consequently deadlocks. There Four conditions are four requirements required for deadlock to occur:
- Mutual exclusion
- Hold and wait
- No preemption
- Circular wait
Deadlock requires needs all four conditions, so to prevent deadlock, prevent preventing deadlock requires preventing any one of the four conditions. This guideline recommends locking One simple solution is to lock the mutexes in a predefined order to prevent , which prevents circular wait.
Noncompliant Code Example
The following code has behavior that behavior of this noncompliant code example depends on the runtime environment and the platform's scheduler. However, with proper timing, the main() function will deadlock when running thr1 and thr2, where thr1 tries The program is susceptible to deadlock if thread thr1 attempts to lock ba2's mutex , while thr2 tries at the same time thread thr2 attempts to lock ba1's mutex in the deposit() function, and the program will not progress.
| Code Block | ||||
|---|---|---|---|---|
| ||||
#include <stdlib.h>
#include <threads.h>
typedef struct {
int balance;
mtx_t balance_mutex;
} bank_account;
typedef struct {
bank_account *from;
bank_account *to;
int amount;
} deposit_thr_argstransaction;
void create_bank_account(bank_account **ba,
int initial_amount) {
int result;
bank_account *nba = (bank_account *)
malloc(
malloc(sizeof(bank_account)
);
if (nba == NULL) {
/* Handle Errorerror */
}
nba->balance = initial_amount;
if (thrd_success
result != mtx_init(&nba->balance_mutex, mtx_plain);
if (result == thrd_error) {
/* Handle error */
}
*ba = nba;
}
int deposit(void *ptr) {
int result;
deposit_thr_argstransaction *args = (deposit_thr_argstransaction *)ptr;
if ((resultthrd_success != mtx_lock(&(args->from->balance_mutex)))
!= thrd_success) {
/* Handle error */
}
/* notNot enough balance to transfer */
if (args->from->balance < args->amount) {
if ((result thrd_success
!= mtx_unlock(&(args->from->balance_mutex)))
!= thrd_success) {
/* Handle error */
}
return -1; /* Indicate error */
}
if ((resultthrd_success != mtx_lock(&(args->to->balance_mutex)))
!= thrd_success) {
/* Handle error */
}
args->from->balance -= args->amount;
args->to->balance += args->amount;
if ((result thrd_success
!= mtx_unlock(&(args->from->balance_mutex)))
!= thrd_success) {
/* Handle error */
}
if ((result thrd_success
!= mtx_unlock(&(args->to->balance_mutex)))
!= thrd_success) {
/* Handle error */
}
free(ptr);
return 0;
}
int main(void) {
pthreadthrd_t thr1, thr2;
int result;
deposit_thr_argstransaction *arg1;
deposit_thr_argstransaction *arg2;
bank_account *ba1;
bank_account *ba2;
create_bank_account(&ba1, 1000);
create_bank_account(&ba2, 1000);
arg1 = (deposit_thr_argstransaction *)malloc(sizeof(deposit_thr_argstransaction));
if (arg1 == NULL) {
/* Handle error */
}
arg2 = (deposit_thr_argstransaction *)malloc(sizeof(deposit_thr_argstransaction));
if (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 ((result thrd_success
!= thrd_create(&thr1, deposit, (void *)arg1))
!= thrd_success) {
/* Handle error */
}
if ((result thrd_success
!= thrd_create(&thr2, deposit, (void *)arg2))
!= thrd_success) {
/* Handle error */
}
return 0;
}
|
Compliant Solution
The This compliant solution to the deadlock problem is to use eliminates the circular wait condition by establishing a predefined order for the locks locking in the deposit() function. In the following compliant solution, each Each thread will lock on the basis of the bank_account ID, defined in the struct initialization. This solution prevents the circular wait problem:which is set when the bank_account struct is initialized.
| Code Block | ||||
|---|---|---|---|---|
| ||||
#include <stdlib.h>
#include <threads.h>
typedef struct {
int balance;
mtx_t balance_mutex;
/* Should nevernot be changedchange after initialized.initialization */
unsigned int id;
} bank_account;
typedef struct {
bank_account *from;
bank_account *to;
int amount;
} transaction;
unsigned int global_id = 1;
void create_bank_account(bank_account **ba,
int initial_amount) {
int result;
bank_account *nba = (bank_account *)
malloc(
malloc(sizeof(bank_account)
);
if (nba == NULL) {
/* Handle error */
}
nba->balance = initial_amount;
if (thrd_success
result != mtx_init(&nba->balance_mutex, mtx_plain);
if (result != thrd_success) {
/* Handle error */
}
nba->id = global_id++;
*ba = nba;
}
int deposit(void *ptr) {
deposit_thr_argstransaction *args = (deposit_thr_argstransaction *)ptr;
int result, ret_val = -1;
mtx_t *first;
mtx_t *second;
if (args->from->id == args->to->id) {
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 ((resultthrd_success != mtx_lock(first)) != thrd_success) {
/* Handle error */
}
if ((resultthrd_success != mtx_lock(second)) != thrd_success) {
/* Handle error */
}
/* Not enough balance to transfer. */
if (args->from->balance >= args->amount) {
args->from->balance -= args->amount;
args->to->balance += args->amount;
ret_valresult = 0;
}
if ((resultthrd_success != mtx_unlock(second)) != thrd_success) {
/* Handle error */
}
if ((resultthrd_success != mtx_unlock(first)) != thrd_success) {
/* Handle error */
}
free(ptr);
returnreturn ret_valresult;
}
|
Risk Assessment
Deadlock prevents multiple threads from progressing, thus halting the executing program execution. A denial-of-service attack is possible because if the attacker can force deadlock situations. Deadlock is likely to occur in multithreaded programs that manage multiple shared resources.create the conditions for deadlock.
Rule |
|---|
Severity | Likelihood | Remediation Cost | Priority | Level | |
|---|---|---|---|---|---|
CON35-C |
Low |
Probable |
Medium | P4 | L3 |
Related Vulnerabilities
Search for vulnerabilities resulting from the violation of this rule on the CERT website.
Automated Detection
| Tool | Version | Checker | Description | ||||||
|---|---|---|---|---|---|---|---|---|---|
| Astrée |
| deadlock | Supported by sound analysis (deadlock alarm) | ||||||
| CodeSonar |
| CONCURRENCY.LOCK.ORDER | Conflicting lock order | ||||||
| Coverity |
|
Related Guidelines
| ORDER_REVERSAL | Fully implemented | |||||||
| Cppcheck Premium |
| premium-cert-con35-c | Partially implemented | ||||||
| Helix QAC |
| C1772, C1773 | |||||||
| Klocwork |
| CONC.DL | |||||||
| Parasoft C/C++test |
| CERT_C-CON35-a | Do not acquire locks in different order | ||||||
| PC-lint Plus |
| 2462 | Fully supported | ||||||
| Polyspace Bug Finder |
| CERT C: Rule CON35-C | Checks for deadlock (rule partially covered) |
Related Guidelines
Key here (explains table format and definitions)
Taxonomy | Taxonomy item | Relationship |
|---|---|---|
| CERT Oracle Secure Coding Standard for Java | LCK07-J. Avoid deadlock by requesting and releasing locks in the same order |
Bibliography
| [Barney 2010] | pthread_mutex tutorial |
| [Bryant 2003] | Chapter 13, "Concurrent Programming" |
| Prior to 2018-01-12: CERT: Unspecified Relationship |
...