Mutexes are often used for critical resources to prevent multiple threads accessing them at the same time. Sometimes, when locking mutexes, deadlock will happen when multiple threads hold each other's lock and the program come to a halt. There are four requirements for deadlock:
- Mutual Exclusion
- Hold and Wait
- No Preemption
- Circular Wait
Each deadlock requires all four. Therefore, to prevent deadlock one just need to avoid one of the four. The advice of this guideline is to require locking the mutexes in a predefined order to prevent circular wait.
Noncompliant Code Example
Based on runtime environment and the scheduler on the operating system, the following code will have different behaviors. However, with proper timing, the code will deadlock in which thr1 tries to lock ba2's mutex while thr2 tries to lock on ba1's mutex and the program will not progress.
#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
typedef struct {
int balance;
pthread_mutex_t balance_mutex;
} bank_account;
typedef struct {
bank_account *from;
bank_account *to;
int amount;
} deposit_thr_args;
/* return negative on error */
int create_bank_account(bank_account **ba, int initial_amount) {
bank_account *nba = malloc(sizeof(bank_account));
if (nba == NULL) {
return -1;
}
nba->balance = initial_amount;
pthread_mutex_init(&nba->balance_mutex, NULL);
*ba = nba;
return 0;
}
void *deposit(void *ptr) {
deposit_thr_args *args = (deposit_thr_args *)ptr;
pthread_mutex_lock(&(args->from->balance_mutex));
/* not enough balance to transfer */
if (args->from->balance < args->amount) {
pthread_mutex_unlock(&(args->from->balance_mutex));
return NULL;
}
pthread_mutex_lock(&(args->to->balance_mutex));
args->from->balance -= args->amount;
args->to->balance += args->amount;
pthread_mutex_unlock(&(args->from->balance_mutex));
pthread_mutex_unlock(&(args->to->balance_mutex));
return NULL;
}
int main() {
pthread_t thr1, thr2;
int err;
bank_account *ba1, *ba2;
err = create_bank_account(&ba1, 1000);
if (err < 0)
exit(err);
err = create_bank_account(&ba2, 1000);
if (err < 0)
exit(err);
deposit_thr_args *arg1 = malloc(sizeof(deposit_thr_args));
if (arg1 == NULL)
exit(-1);
deposit_thr_args *arg2 = malloc(sizeof(deposit_thr_args));
if (arg2 == NULL)
exit(-1);
arg1->from = ba1;
arg1->to = ba2;
arg1->amount = 100;
arg2->from = ba2;
arg2->to = ba1;
arg2->amount = 100;
/* perform the deposit */
err = pthread_create(&thr1, NULL, deposit, (void *)arg1);
if (err)
exit(err);
err = pthread_create(&thr2, NULL, deposit, (void *)arg2);
if (err)
exit(err);
pthread_exit(NULL);
return 0;
}
Compliant Solution
The solution to the deadlock problem is to lock in predefined order. In the following example, each thread will lock based on bank_account's id in increasing order. This way circular wait problem is avoided and when one thread requires a lock will guarantee it will require the next lock.
typedef struct {
int balance;
pthread_mutex_t balance_mutex;
unsigned int id; /* read only and should never be changed */
} bank_account;
unsigned int global_id = 1;
/* return negative on error */
int create_bank_account(bank_account **ba, int initial_amount) {
bank_account *nba = malloc(sizeof(bank_account));
if (nba == NULL) {
return -1;
}
nba->balance = initial_amount;
pthread_mutex_init(&nba->balance_mutex, NULL);
nba->id = global_id++;
*ba = nba;
return 0;
}
void *deposit(void *ptr) {
deposit_thr_args *args = (deposit_thr_args *)ptr;
if (args->from->id == args->to->id)
return NULL;
/* ensure proper ordering for locking */
if (args->from->id < args->to->id) {
pthread_mutex_lock(&(args->from->balance_mutex));
pthread_mutex_lock(&(args->to->balance_mutex));
} else {
pthread_mutex_lock(&(args->to->balance_mutex));
pthread_mutex_lock(&(args->from->balance_mutex));
}
/* not enough balance to transfer */
if (args->from->balance < args->amount) {
pthread_mutex_unlock(&(args->from->balance_mutex));
pthread_mutex_unlock(&(args->to->balance_mutex));
return NULL;
}
args->from->balance -= args->amount;
args->to->balance += args->amount;
pthread_mutex_unlock(&(args->from->balance_mutex));
pthread_mutex_unlock(&(args->to->balance_mutex));
return NULL;
}
Risk Assessment
Deadlock causes multiple threads to not be able to progress and thus halt the executing program. This is a potential denial-of-service attack when the attacker can force deadlock situations. It's probable that deadlock will occur in multi-thread programs that manage multiple resources. Some automation for detecting deadlock can be implemented in which the detector can try different inputs and wait for a timeout. The fixes can be done manually.
Recommendation |
Severity |
Likelihood |
Remediation Cost |
Level |
Priority |
|---|---|---|---|---|---|
POS43-C |
low |
probable |
medium |
L3 |
P3 |
Other Languages
CON12-J. Avoid deadlock by requesting and releasing locks in the same order
References
[pthread_mutex 
] pthread_mutex tutorial
[MITRE CWE:764 ] Multiple Locks of Critical Resources
[[Bryant 03]] Chapter 13, Concurrent Programming