CONC.DL
Deadlock
Deadlock in a multi-threaded program is a condition in which two or more threads mutually block, each waiting for the other to finish. This is typically caused by out-of-order lock contention, in which each thread holds a resource that another thread requires, and so none can unblock until it acquires the resource.
Deadlocks are typically caused by circular chains of locks that are reserved out of order. For example, Thread 1 executes code that has a lock reservation pattern that calls for lock A to be reserved before lock B, while Thread 2 executes (potentially the same) code, but instead has a lock reservation pattern that calls for lock B to be reserved before lock A. If these two threads collide in execution, it is possible that Thread 1 will be requesting lock B after Thread 2 has already reserved it. Thread 2 may request lock A, only to be blocked because Thread 1 has already reserved it.
Checker CONC.DL finds instances of deadlock.
Vulnerability and risk
This type of circular lock reference can cause stuck programs, inactive UIs, unresponsive devices, and similar problems. Debugging these issues in the field can easily consume weeks of developer time and customer frustration.
Mitigation and prevention
To help avoid lock contention:
- Try to keep locked sections of code as small and as simple to understand as possible.
- Don't lock sections of code that can cause concurrency problems, such as data races.
- Avoid circular wait conditions at all costs.
- If several locks are used, typically in an escalating guard pattern, make absolutely sure that the escalation is performed exactly the same in every circumstance.
Vulnerable code example 1
#include <stdio.h>
#include <pthread.h>
static pthread_mutex_t A, B;
void *printmsg1(void *msg) {
pthread_mutex_lock(&A); // Execution step 1
pthread_mutex_lock(&B); // Execution step 3
printf("printmsg1\n");
pthread_mutex_unlock(&B);
pthread_mutex_unlock(&A);
return 0;
}
void *printmsg2(void *msg) {
pthread_mutex_lock(&B); // Execution step 2
pthread_mutex_lock(&A);
printf("printmsg2\n");
pthread_mutex_unlock(&A);
pthread_mutex_unlock(&B);
return 0;
}
int main(int argc, char**argv) {
pthread_t pt1, pt2;
pthread_mutex_init(&A, NULL);
pthread_mutex_init(&B, NULL);
pthread_create(&pt1,0, printmsg1, NULL);
pthread_create(&pt2,0, printmsg2, NULL);
pthread_join(pt1,0);
pthread_join(pt2,0);
pthread_mutex_destroy(&A);
pthread_mutex_destroy(&B);
return 0;
}Klocwork reports a possible deadlock on line 6 between between the two threads using global mutexes 'A' and 'B'. The main routine creates and starts two threads, which are defined in functions 'printmsg1' and 'printmsg2'. The first thread waits to acquire the lock on mutex 'B' at line 7 while holding the lock on mutex 'A'. The second thread waits to acquire the lock on mutex 'A' at line 16 while holding the lock on mutex 'B'. This circular chain of locks between the two threads can be responsible for a deadlock.
Fixed code example 1
#include <stdio.h>
#include <pthread.h>
static pthread_mutex_t A, B;
void *printmsg1(void *msg) {
pthread_mutex_lock(&A);
pthread_mutex_lock(&B);
printf("printmsg1\n");
pthread_mutex_unlock(&B);
pthread_mutex_unlock(&A);
return 0;
}
void *printmsg2(void *msg) {
pthread_mutex_lock(&A);
pthread_mutex_lock(&B);
printf("printmsg2\n");
pthread_mutex_unlock(&B);
pthread_mutex_unlock(&A);
return 0;
}
int main(int argc, char**argv) {
pthread_t pt1, pt2;
pthread_mutex_init(&A, NULL);
pthread_mutex_init(&B, NULL);
pthread_create(&pt1,0, printmsg1, NULL);
pthread_create(&pt2,0, printmsg2, NULL);
pthread_join(pt1,0);
pthread_join(pt2,0);
pthread_mutex_destroy(&A);
pthread_mutex_destroy(&B);
return 0;
}If several mutexes are used for synchronization in each process, mutexes should be locked in the same order. In the fixed code example, the order of the locks and unlocks is changed in lines 15, 16, 18, and 19 to be the same in 'printmsg2' as in 'printmsg1', ensuring that a circular chain doesn't occur.
Vulnerable code example 2
#include <stdio.h>
#include <pthread.h>
static pthread_mutex_t A, B;
static pthread_cond_t cond;
static int count;
void *f1(void *msg) {
pthread_mutex_lock(&A);
pthread_mutex_lock(&B);
while (count) {
pthread_cond_wait(&cond, &B);
}
pthread_mutex_unlock(&B);
pthread_mutex_unlock(&A);
return 0;
}
void *f2(void *msg) {
pthread_mutex_lock(&A);
pthread_mutex_lock(&B);
count--;
pthread_cond_broadcast(&cond);
pthread_mutex_unlock(&B);
pthread_mutex_unlock(&A);
return 0;
}
int main(int argc, char**argv) {
pthread_t pt1, pt2;
pthread_mutex_init(&A, NULL);
pthread_mutex_init(&B, NULL);
pthread_cond_init(&cond, NULL);
count = 1;
pthread_create(&pt1,0, f1, NULL);
pthread_create(&pt2,0, f2, NULL);
pthread_join(pt1, NULL);
pthread_join(pt2, NULL);
pthread_mutex_destroy(&A);
pthread_mutex_destroy(&B);
pthread_cond_destroy(&cond);
return 0;
}Klocwork reports a possible deadlock on line 11 between the two threads using global mutex 'A' and conditional variable 'cond'. The first thread may wait indefinitely for conditional variable 'cond' at line 11 while holding the lock on mutex 'A'. The second thread waits to acquire the lock on mutex 'A' at line 18 to change global variable 'count' and send a signal to conditional variable 'cond'.
Fixed code example 2
#include <stdio.h>
#include <pthread.h>
static pthread_mutex_t A, B;
static pthread_cond_t cond;
static int count;
void *f1(void *msg) {
pthread_mutex_lock(&B);
while (count) {
pthread_cond_wait(&cond, &B);
}
pthread_mutex_unlock(&B);
return 0;
}
void *f2(void *msg) {
pthread_mutex_lock(&A);
pthread_mutex_lock(&B);
count--;
pthread_cond_broadcast(&cond);
pthread_mutex_unlock(&B);
pthread_mutex_unlock(&A);
return 0;
}
int main(int argc, char**argv) {
pthread_t pt1, pt2;
pthread_mutex_init(&A, NULL);
pthread_mutex_init(&B, NULL);
pthread_cond_init(&cond, NULL);
count = 1;
pthread_create(&pt1,0, f1, NULL);
pthread_create(&pt2,0, f2, NULL);
pthread_join(pt1, NULL);
pthread_join(pt2, NULL);
pthread_mutex_destroy(&A);
pthread_mutex_destroy(&B);
pthread_cond_destroy(&cond);
return 0;
}Before a conditional wait function, a lock set should contain only mutexes that are required and unlocked in the same function. In the fixed code example, the mutex 'A' lock before the wait function 'pthread_cond_wait' has been removed, since it's unnecessary. Removing the mutex 'A' lock eliminates the possibility of a deadlock report at line 10.
Related checkers
External guidance
- CERT CON35-C: Avoid deadlock by locking in a predefined order
- CERT POS51-C: Avoid deadlock with POSIX threads by locking in predefined order
- CWE-412: Unrestricted Externally Accessible Lock
- CWE-667: Improper Locking
- CWE-833: Deadlock
- STIG-ID:APP3630.4 Application vulnerable to race conditions
- STIG-ID:APP3780 Web Service Availability
Security training
Application security training materials provided by Secure Code Warrior.
Extension
This checker can be extended. The related knowledge base record kinds are:
See Tuning C/C++ analysis for more information.
