Page History

...

The user 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.

...

Code Block

bgColor	#FFcccc
lang	c

#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;
  int my_step = (int)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) {
  int i;
  thrd_t threads[NTHREADS];
  int 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 (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 (i = NTHREADS - 1; i >= 0; --i) {
    if (thrd_success != thrd_join(threads[i], NULL)) {
      /* Handle error condition */
    }
  }

  mtx_destroy(&mutex);
  cnd_destroy(&cond);
  return 0;
}

...

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++; signal()`
4	1	1	Thread 1 executes first time: predicate is `TRUE -> current_step++; signal()`
5	3	2	Thread 3 wakes up (scheduler choice): predicate is `FALSE -> wait()`
6	—	—	Deadlock situation! No more threads to run, and a signal is needed to wake up the others.

This noncompliant code example violates the liveness property.

...

Code Block

bgColor	#ccccff
lang	c

#include <stdio.h>
#include <threads.h>
 
int run_step(void *t) {
  static int current_step = 0;
  int my_step = (int)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;
}

...

Code Block

bgColor	#ccccff
lang	c

#include <Windows.h>
#include <stdio.h>
 
CRITICAL_SECTION lock;
CONDITION_VARIABLE cond;
 
DWORD WINAPI run_step(LPVOID t) {
  static int current_step = 0;
  int my_step = (int)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 (int 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;
}

...

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()) only 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.

...

Code Block

bgColor	#ccccff
lang	c

#include <stdio.h>
#include <threads.h>

enum { NTHREADS = 5 };

mtx_t mutex;
cnd_t cond[NTHREADS];

int run_step(void *t) {
  static int current_step = 0;
  int my_step = (int)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) {
  int i;
  thrd_t threads[NTHREADS];
  int step[NTHREADS];

  if (thrd_success != mtx_init(&mutex, mtx_plain)) {
    /* Handle error condition. */
  }

  for (i = 0; i< NTHREADS; ++i) {
    if (thrd_success != cnd_init(&cond[i])) {
      /* Handle error condition. */
    }
  }

  /* Create threads. */
  for (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 (i = NTHREADS - 1; i >= 0; --i) {
    if (thrd_success != thrd_join(threads[i], NULL)) {
      /* Handle error condition. */
    }
  }

  mtx_destroy(&mutex);

  for (i = 0; i < NTHREADS; ++i) {
    cnd_destroy(&cond[i]);
  }
  return 0;
}

...

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	lowLow	unlikelyUnlikely	mediumMedium	P2	L3

Related Vulnerabilities

Search for vulnerabilities resulting from the violation of this rule on the CERT website.

...

Space shortcuts

Page tree

Versions Compared

Old Version 42

New Version 43

Key

Related Vulnerabilities