Page History

Mutexes are often used for critical resources to prevent multiple threads accessing them from causing a data race by accessing shared resources at the same time. Sometimes, when locking mutexes, deadlock will happen when multiple threads hold each other's lock, and the program come to a halt.consequently deadlocks. Four conditions are required for deadlock to occur:

Mutual exclusion
Hold and wait
No preemption
Circular wait

Deadlock needs all four conditions, so preventing deadlock requires preventing any one of the four conditions. One simple solution is to lock To prevent deadlock, one can try to avoid circular wait by locking the mutexes in a predefined order, which prevents circular wait.

Noncompliant Code Example

Based on The behavior of this noncompliant code example depends on the runtime environment and the scheduler on the operating system, the following code will have different behaviors. However, with proper timing, the code will deadlock in which thr1 tries platform's scheduler. The program is susceptible to deadlock if thread thr1 attempts to lock ba2's mutex while thr2 tries at the same time thread thr2 attempts to lock on ba1's mutex and the program will not progressin the deposit() function.

Code Block

bgColor	#ffcccc
lang	c


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

typedef struct {
	  int balance;
	pthread_mutex_  mtx_t balance_mutex; 
} bank_account;

typedef struct {
	  bank_account *from;
	  bank_account *to;
	  int amount;
} deposit_thr_argstransaction;

/* return negative on error */
int void create_bank_account(bank_account **ba,
                         int initial_amount) {

	  bank_account *nba = (bank_account *)malloc(
    sizeof(bank_account)
  );

	  if (nba == NULL) {
		return -1;
	    /* Handle error */
  }

	  nba->balance = initial_amount;
	pthread_mutex  if (thrd_success
      != mtx_init(&nba->balance_mutex, NULL);

	mtx_plain)) {
    /* Handle error */
  }

  *ba = nba;

	return 0;
}


voidint *deposit(void *ptr) {
	
	deposit_thr_args  transaction *args = (deposit_thr_argstransaction *)ptr;

	pthread_mutex  if (thrd_success != mtx_lock(&(args->from->balance_mutex));

	 {
    /* Handle error */
  }

  /* notNot enough balance to transfer */
	  if (args->from->balance < args->amount) {
		pthread_mutex    if (thrd_success
        != mtx_unlock(&(args->from->balance_mutex));
		return NULL;
	}

	pthread_mutex {
      /* Handle error */
    }
    return -1; /* Indicate error */
  }
  if (thrd_success != mtx_lock(&(args->to->balance_mutex));
	 {
    /* Handle error */
  }

  args->from->balance -= args->amount;
	  args->to->balance += args->amount;

	pthread_mutex  if (thrd_success
      != mtx_unlock(&(args->from->balance_mutex));
	pthread_mutex {
    /* Handle error */
  }

  if (thrd_success
      != mtx_unlock(&(args->to->balance_mutex));

	return NULL {
    /* Handle error */
  }

  free(ptr);
  return 0;
}

int main(void) {

	pthread  thrd_t thr1, thr2;
	int err;

	  transaction *arg1;
  transaction *arg2;
  bank_account *ba1,;
  bank_account *ba2;

	err = create_bank_account(&ba1, 1000);
	if (err < 0) 
		exit(err);

	err = create_bank_account(&ba2, 1000);
	
  arg1 = (transaction *)malloc(sizeof(transaction));
  if (errarg1 <== 0NULL) 
		exit(err);

	deposit_thr_args *arg1 = malloc(sizeof(deposit_thr_args));
	deposit_thr_args *arg2 = malloc(sizeof(deposit_thr_args));

	{
    /* Handle error */
  }
  arg2 = (transaction *)malloc(sizeof(transaction));
  if (arg2 == NULL) {
    /* Handle error */
  }
  arg1->from = ba1;
	  arg1->to = ba2;
	  arg1->amount = 100;

	  arg2->from = ba2;
	  arg2->to = ba1;
	  arg2->amount = 100;

	  /* performPerform the depositdeposits */
	pthread  if (thrd_success
     != thrd_create(&thr1, NULL, deposit, (void *)arg1);
	pthread)) {
    /* Handle error */
  }
  if (thrd_success
      != thrd_create(&thr2, NULL, deposit, (void *)arg2));

	pthread_exit(NULL);

	 {
    /* Handle error */
  }
  return 0;
}

Compliant Solution

The This compliant solution to the deadlock problem is to lock in predefined order. In the following example, each thread will lock based on bank_account's id in increasing order. This way circular wait problem is avoided and when one thread requires a lock will guarantee it will require the next lockeliminates the circular wait condition by establishing a predefined order for locking in the deposit() function. Each thread will lock on the basis of the bank_account ID, which is set when the bank_account struct is initialized.

Code Block

bgColor	#ccccff
lang	c


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

typedef struct {
	  int balance;
	pthread_mutex_  mtx_t balance_mutex; 
	unsigned int id;
 
  /* read only and should never be changed */Should not change after initialization */
  unsigned int id;
} bank_account;

typedef struct {
	  bank_account *from;
	  bank_account *to;
	  int amount;
} deposit_thr_argstransaction;

unsigned int global_id = 1;

/* return negative on error */
int void create_bank_account(bank_account **ba,
                         int initial_amount) {

	  bank_account *nba = (bank_account *)malloc(
    sizeof(bank_account)
  );

	  if (nba == NULL) {
		return -1;
	    /* Handle error */
  }

	  nba->balance = initial_amount;
	pthread_mutex  if (thrd_success
      != mtx_init(&nba->balance_mutex, NULL);
	mtx_plain)) {
    /* Handle error */
  }

  nba->id = global_id++;

	  *ba = nba;

	return 0;
}


voidint *deposit(void *ptr) {
	
	deposit_thr_args  transaction *args = (deposit_thr_args *)ptr;

	transaction *)ptr;
  int result = -1;
  mtx_t *first;
  mtx_t *second;

  if (args->from->id == args->to->id) 
		{
    return NULL;

	-1; /* Indicate error */
  }

  /* ensureEnsure proper ordering for unlockinglocking */
	  if (args->from->id < args->to->id) {
		pthread_mutex_lock(&(    first = &args->from->balance_mutex));
		pthread_mutex_lock(&(;
    second = &args->to->balance_mutex));
	  } else {
		pthread_mutex_lock(&(    first = &args->to->balance_mutex));
		pthread_mutex_lock(&(;
    second = &args->from->balance_mutex));
	}

	/* not;
  }
  if (thrd_success != mtx_lock(first)) {
    /* Handle error */
  }
  if (thrd_success != mtx_lock(second)) {
    /* Handle error */
  }

  /* Not enough balance to transfer */
	  if (args->from->balance <>= args->amount) {
		pthread_mutex_unlock(&(args->from->balance_mutex));
		pthread_mutex_unlock(&(args->to->balance_mutex));
		return NULL;
	}

	    args->from->balance -= args->amount;
	    args->to->balance += args->amount;

	pthread_mutex_unlock(&(args->from->balance_mutex));
	pthread_mutex_unlock(&(args->to->balance_mutex));

	return NULL;
}

int main() {

	pthread_t thr1, thr2;
	int err;

	bank_account *ba1, *ba2;

	err = create_bank_account(&ba1, 1000);
	if (err < 0) 
		exit(err);

	err = create_bank_account(&ba2, 1000);
	if (err < 0) 
		exit(err);

	deposit_thr_args *arg1 = malloc(sizeof(deposit_thr_args));
	deposit_thr_args *arg2 = malloc(sizeof(deposit_thr_args));

	arg1->from = ba1;
	arg1->to = ba2;
	arg1->amount = 100;

	arg2->from = ba2;
	arg2->to = ba1;
	arg2->amount = 100;

	/* perform the deposit */
	pthread_create(&thr1, NULL, deposit, (void *)arg1);
	pthread_create(&thr2, NULL, deposit, (void *)arg2);

	pthread_exit(NULL);

	return 0;
}

Risk Assessment

Deadlock causes multiple threads to not be able to progress and thus halt the executing program. This is a potential denial-of-service attack when the attacker can force deadlock situations. It's probable that deadlock will occur in multi-thread programs that manage multiple resources. Some automation for detecting deadlock can be implemented in which the detector can try different inputs and wait for a timeout. The fixes can be done automatically using some graph algorithm like Dijkstra, but most like be manual.

 result = 0;
  }

  if (thrd_success != mtx_unlock(second)) {
    /* Handle error */
  }
  if (thrd_success != mtx_unlock(first)) {
    /* Handle error */
  }
  free(ptr);
  return result;
}

Risk Assessment

Deadlock prevents multiple threads from progressing, halting program execution. A denial-of-service attack is possible if the attacker can create the conditions for deadlock.

Rule

Recommendation

	Severity	Likelihood	Remediation Cost	Priority	Level

Priority

POS43

CON35-C

low

Low

Probable

probable

Medium

medium

L3

P3

References

Wiki Markup

\[[pthread_mutex | https://computing.llnl.gov/tutorials/pthreads/#Mutexes]\]  pthread_mutex tutorial
\[[MITRE CWE:764 | http://cwe.mitre.org/data/definitions/764.html]\] Multiple Locks of Critical Resources
\[[Bryant 03|AA. References#Bryant 03]\] Chapter 13, Concurrent Programming