Introduction
Whenever threads come into play, there are bounded to be shared memory or resources that each thread wants to access. But because of the random nature of execution of each thread, there will be corruption of data when multiple threads try to read and write into the same memory space. One possible way to fix the problem is using locking mechanism like a mutex. POSIX provides a mutex called pthread_mutex_t just for this purpose. See POS00-C Avoid race conditions with multiple threads for more information.
Deadlock can happen when multiple threads each holds a lock the other needs and are waiting for each other to release that resource. One way to fix the problem is to avoid circular wait by locking the mutex in a predefined order.
Noncompliant Code Example
Based on runtime environment and the scheduler on the operating system, the following code will have different behaviors. Let's assume function thread1 and thread2 are called consecutively as in pthread_create is called for thread2 right after pthread_create is called for thread1. If lucky, the code will run without any problems. In other times, the code will deadlock in which thread1 try to lock m1 while thread2 try to lock on m2 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));
deposit_thr_args *arg2 = malloc(sizeof(deposit_thr_args));
arg1->from = ba1;
arg1->to = ba2;
arg1->amount = 100;
arg2->from = ba2;
arg2->to = ba1;
arg2->amount = 100;
/* perform the deposit */
pthread_create(&thr1, NULL, deposit, (void *)arg1);
pthread_create(&thr2, NULL, deposit, (void *)arg2);
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 m1 first then m2. This way circular wait problem is avoided and when one thread requires a lock will guarantee it will require the next lock.
#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
typedef struct {
int balance;
pthread_mutex_t balance_mutex;
unsigned int id; /* read only and should never be changed */
} bank_account;
typedef struct {
bank_account *from;
bank_account *to;
int amount;
} deposit_thr_args;
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 unlocking */
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;
}
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));
deposit_thr_args *arg2 = malloc(sizeof(deposit_thr_args));
arg1->from = ba1;
arg1->to = ba2;
arg1->amount = 100;
arg2->from = ba2;
arg2->to = ba1;
arg2->amount = 100;
/* perform the deposit */
pthread_create(&thr1, NULL, deposit, (void *)arg1);
pthread_create(&thr2, NULL, deposit, (void *)arg2);
pthread_exit(NULL);
return 0;
}
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 automatically using some graph algorithm like Dijkstra, but most like be manual.
Recommendation |
Severity |
Likelihood |
Remediation Cost |
Level |
Priority |
|---|---|---|---|---|---|
POS43-C |
low |
probable |
medium |
L3 |
P4 |
References
[pthread_mutex 
] pthread_mutex tutorial
[MITRE CWE:764 ] Multiple Locks of Critical Resources
[[Bryant 03]] Chapter 13, Concurrent Programming
Other Languages
CON12-J. Avoid deadlock by requesting and releasing locks in the same order