Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

Code Block
bgColor#FFcccc
langc
#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 #
(my_step)

current_step

Action

0

3

0

Thread 3 executes first time: predicate is FALSE -> wait()

1

2

0

Thread 2 executes first time: predicate is FALSE -> wait()

2

4

0

Thread 4 executes first time: predicate is FALSE -> wait()

3

0

0

Thread 0 executes first time: predicate is TRUE -> current_step++; cnd_signal()

4

1

1

Thread 1 executes first time: predicate is TRUE -> current_step++; cnd_signal()

5

3

2

Thread 3 wakes up (scheduler choice): predicate is FALSE -> wait()

6

Deadlock situationThread exhaustion! No more threads to run, and a conditional variable signal is needed to wake up the others

...

Code Block
bgColor#ccccff
langc
#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
bgColor#ccccff
langc
#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
bgColor#ccccff
langc
#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] 

 

...