When a given thread waits (cnd_wait() or cnd_timedwait()) on a condition variable, it can be awakened as a result of a signal operation (cnd_signal()). However, if multiple threads are waiting on the same condition variable, any of those threads can be selected by the scheduler to be awakened (assuming that all threads have the same priority level).
The programmer is forced to create a predicate-testing loop around the wait condition to guarantee that each thread executes only if its predicate test is true (recommendation in IEEE Std 1003.1 since the 2001 release [IEEE Std 1003.1-2004]). As a consequence, if a given thread finds the predicate test to be false, it waits again, eventually resulting in a deadlock situation.
The use of cnd_signal() is safe only if the following conditions are met:
- All threads must perform the same set of operations after waking up, which means that any thread can be selected to wake up and resume for a single invocation of
cnd_signal(). - Only one thread is required to wake upon receiving the signal.
The use of cnd_signal() is also safe if each thread uses a unique condition variable.
The use of cnd_broadcast() avoids these problems because it wakes up all the threads associated with the condition variable, and because all the threads must reevaluate the predicate condition, one thread will find its test to be true, avoiding deadlock.
Noncompliant Code Example (cnd_signal())
This noncompliant code example uses five threads that are intended to execute one after another according to the step level assigned to each thread when it is created (serialized processing). The current_step variable holds the current step level and is incremented when the respective thread completes. Finally, another thread is signaled so that the next step can be executed. Each thread waits until its step level is ready, and the cnd_wait() function call is wrapped inside a while loop, in compliance with CON44-C. Wrap functions that can fail spuriously in a loop.
#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 waiting 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** argv) {
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);
cnd_destroy(&cond);
return 0;
}
In this example, 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()), any of the waiting threads can wake up. 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 notifications can occur.
Consider the following example:
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 situation! No more threads to run, and a conditional variable signal is needed to wake up the others |
This noncompliant code example violates the liveness property.
Compliant Solution (cnd_broadcast())
This compliant solution uses the cnd_broadcast() function to signal all waiting threads instead of a single random thread. Only the run_step() thread code from the noncompliant code example is modified, as follows:
#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 guarantess the liveness property because each thread will execute its condition predicate test, and exactly one will succeed and continue execution.
Compliant Solution (Windows, Condition Variables)
This compliant solution uses a CONDITION_VARIABLE object, available on Microsoft Windows (Vista and later).
#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[]) {
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;
}
Compliant Solution (Using cnd_signal() but with a Unique Condition Variable per Thread)
Another way to solve the signal issue is to use a unique condition variable for each thread (all associated with a single mutex). In this case, the signal operation (cnd_signal()) wakes up only the thread that is waiting on it. This solution turns out to be more efficient than using cnd_broadcast() because only the desired thread is awakened.
NOTE: The condition predicate of the signaled thread must be true; otherwise, a deadlock will occur.
#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[]) {
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;
}
Risk Assessment
Signaling a single thread instead of all waiting threads can pose a threat to the liveness property of the system.
Rule | Severity | Likelihood | Remediation Cost | Priority | Level |
|---|---|---|---|---|---|
CON38-C | Low | Unlikely | Medium | P2 | L3 |
Related Vulnerabilities
Search for vulnerabilities resulting from the violation of this rule on the CERT website.
Related Guidelines
| CERT Oracle Secure Coding Standard for Java | THI04-J. Notify all waiting threads rather than a single thread |
Bibliography