...
Code Block | ||||
---|---|---|---|---|
| ||||
#include <stdio.h> #include <threads.h> enum { NTHREADS = 5 }; mtx_t mutex; cnd_t cond; int run_step(void *t) { static int current_step = 0; size_t my_step = *(size_t *)t; if (thrd_success != mtx_lock(&mutex)) { /* Handle error condition */ } printf("Thread %d has the lock\n", my_step); while (current_step != my_step) { printf("Thread %d is sleeping...\n", my_step); if (thrd_success != cnd_wait(&cond, &mutex)) { /* Handle error condition */ } printf("Thread %d woke up\n", my_step); } /* Do processing ... */ printf("Thread %d is processing...\n", my_step); current_step++; /* Signal a waitingawaiting task */ if (thrd_success != cnd_signal(&cond)) { /* Handle error condition */ } printf("Thread %d is exiting...\n", my_step); if (thrd_success != mtx_unlock(&mutex)) { /* Handle error condition */ } return 0; } int main(int argc, char** argvvoid) { thrd_t threads[NTHREADS]; size_t step[NTHREADS]; if (thrd_success != mtx_init(&mutex, mtx_plain)) { /* Handle error condition */ } if (thrd_success != cnd_init(&cond)) { /* Handle error condition */ } /* Create threads */ for (size_t i = 0; i < NTHREADS; ++i) { step[i] = i; if (thrd_success != thrd_create(&threads[i], run_step, (void *)&step[i])) { /* Handle error condition */ } } /* Wait for all threads to complete */ for (size_t i = NTHREADS; i != 0; --i) { if (thrd_success != thrd_join(threads[i-1], NULL)) { /* Handle error condition */ } } mtx_destroy(&mutex); cndcnd_destroy(&cond); return 0; } |
In this example, each thread all threads share a condition variable. Each thread has its own distinct condition predicate because each thread requires current_step
to have a different value before proceeding. Upon the signal operation (cnd_signal()
)When the condition variable is signaled, any of the waiting threads can wake up. The following table illustrates a possible scenario in which the liveness property is violated. If, by chance, the notified thread is not the thread with the next step value, that thread will wait again (cnd_wait()
), resulting in a deadlock situation because no more . No additional notifications can occur, and eventually the pool of available threads will be exhausted.Consider the following example:
Deadlock: Out-of-Sequence Step Value
Time | Thread # |
| Action |
---|---|---|---|
0 | 3 | 0 | Thread 3 executes first time: predicate is |
1 | 2 | 0 | Thread 2 executes first time: predicate is |
2 | 4 | 0 | Thread 4 executes first time: predicate is |
3 | 0 | 0 | Thread 0 executes first time: predicate is |
4 | 1 | 1 | Thread 1 executes first time: predicate is |
5 | 3 | 2 | Thread 3 wakes up (scheduler choice): predicate is |
6 | — | — | Deadlock situationThread exhaustion! No more threads to run, and a conditional variable signal is needed to wake up the others |
...
Code Block | ||||
---|---|---|---|---|
| ||||
#include <stdio.h> #include <threads.h> int run_step(void *t) { static size_t current_step = 0; size_t my_step = *(size_t *)t; if (thrd_success != mtx_lock(&mutex)) { /* Handle error condition */ } printf("Thread %d has the lock\n", my_step); while (current_step != my_step) { printf("Thread %d is sleeping...\n", my_step); if (thrd_success != cnd_wait(&cond, &mutex)) { /* Handle error condition */ } printf("Thread %d woke up\n", my_step); } /* Do processing ... */ printf("Thread %d is processing...\n", my_step); current_step++; /* Signal ALL waiting tasks */ if (thrd_success != cnd_broadcast(&cond)) { /* Handle error condition */ } printf("Thread %d is exiting...\n", my_step); if (thrd_success != mtx_unlock(&mutex)) { /* Handle error condition */ } return 0; } |
Awakening all threads solves guarantees the liveness property because each thread will execute its its condition predicate test, and exactly one will succeed and continue execution.
Compliant Solution (Using cnd_signal()
...
with a Unique Condition Variable per Thread)
Another compliant solution is to use a unique condition variable for each thread (all associated with a single the same mutex). In this case, the signal operation ( cnd_signal())
wakes up only the thread that is waiting on it. This solution is more efficient than using cnd_broadcast()
because only the desired thread is awakened.
Note that the the condition predicate of the signaled thread must be true; otherwise, a deadlock will occur.
Code Block | ||||
---|---|---|---|---|
| ||||
#include <stdio.h> #include <threads.h> enum { NTHREADS = 5 }; mtx_t mutex; cnd_t cond[NTHREADS]; int run_step(void *t) { static size_t current_step = 0; size_t my_step = *(size_t *)t; if (thrd_success != mtx_lock(&mutex)) { /* Handle error condition */ } printf("Thread %d has the lock\n", my_step); while (current_step != my_step) { printf("Thread %d is sleeping...\n", my_step); if (thrd_success != cnd_wait(&cond[my_step], &mutex)) { /* Handle error condition */ } printf("Thread %d woke up\n", my_step); } /* Do processing ... */ printf("Thread %d is processing...\n", my_step); current_step++; /* Signal next step thread */ if ((my_step + 1) < NTHREADS) { if (thrd_success != cnd_signal(&cond[my_step + 1])) { /* Handle error condition */ } } printf("Thread %d is exiting...\n", my_step); if (thrd_success != mtx_unlock(&mutex)) { /* Handle error condition */ } return 0; } int main(int argc, char *argv[]void) { thrd_t threads[NTHREADS]; size_t step[NTHREADS]; if (thrd_success != mtx_init(&mutex, mtx_plain)) { /* Handle error condition */ } for (size_t i = 0; i< NTHREADS; ++i) { if (thrd_success != cnd_init(&cond[i])) { /* Handle error condition */ } } /* Create threads */ for (size_t i = 0; i < NTHREADS; ++i) { step[i] = i; if (thrd_success != thrd_create(&threads[i], run_step, (void *)&step[i])) { /* Handle error condition */ } } /* Wait for all threads to complete */ for (size_t i = NTHREADS; i != 0; --i) { if (thrd_success != thrd_join(threads[i-1], NULL)) { /* Handle error condition */ } } mtx_destroy(&mutex); for (size_t i = 0; i < NTHREADS; ++i) { cnd_destroy(&cond[i]); } return 0; } |
Compliant Solution (Windows, Condition Variables)
This compliant solution uses a CONDITION_VARIABLE
object, available on Microsoft Windows (Vista and later).:
Code Block | ||||
---|---|---|---|---|
| ||||
#include <Windows.h> #include <stdio.h> CRITICAL_SECTION lock; CONDITION_VARIABLE cond; DWORD WINAPI run_step(LPVOID t) { static size_t current_step = 0; size_t my_step = (size_t)t; EnterCriticalSection(&lock); printf("Thread %d has the lock\n", my_step); while (current_step != my_step) { printf("Thread %d is sleeping...\n", my_step); if (!SleepConditionVariableCS(&cond, &lock, INFINITE)) { /* Handle error condition */ } printf("Thread %d woke up\n", my_step); } /* Do processing ... */ printf("Thread %d is processing...\n", my_step); current_step++; LeaveCriticalSection(&lock); /* Signal ALL waiting tasks */ WakeAllConditionVariable(&cond); printf("Thread %d is exiting...\n", my_step); return 0; } enum { NTHREADS = 5 }; int main(int argc, char *argv[]void) { HANDLE threads[NTHREADS]; InitializeCriticalSection(&lock); InitializeConditionVariable(&cond); /* Create threads */ for (size_t i = 0; i < NTHREADS; ++i) { threads[i] = CreateThread(NULL, 0, run_step, (LPVOID)i, 0, NULL); } /* Wait for all threads to complete */ WaitForMultipleObjects(NTHREADS, threads, TRUE, INFINITE); DeleteCriticalSection(&lock); return 0; } |
Risk Assessment
Signaling a single thread instead of all waiting threads can pose a threat to the liveness property of the systemFailing to preserve the thread safety and liveness of a program when using condition variables can lead to indefinite blocking and denial of service (DoS).
Rule | Severity | Likelihood | Remediation Cost | Priority | Level |
---|---|---|---|---|---|
CON38-C | Low | Unlikely | Medium | P2 | L3 |
...
[IEEE Std 1003.1:2013] | XSH, System Interfaces, pthread_cond_broadcast XSH, System Interfaces, pthread_cond_signal |
[Lea 2000] |
...