Page History

...

Each deadlock requires all four conditions. Therefore, to prevent deadlock, prevent any one of the four conditions from being satisfied. This guideline recommends locking the mutexes in a predefined order to prevent circular wait.

Noncompliant Code Example

The following code has behavior which is dependend on the runtime environment and the platform's scheduler. However, with proper timing, the main() function will deadlock when running thr1 and thr2 in which thr1 tries to lock ba2's mutex while thr2 tries to lock on ba1's mutex in the deposit() function and the program will not progress.

Code Block

bgColor	#ffcccc

typedef struct {
  int balance;
  pthread_mutex_t balance_mutex; 
} bank_account;

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

void create_bank_account(bank_account **ba, int initial_amount) {
  int result;
  bank_account *nba = malloc(sizeof(bank_account));
  if (nba == NULL) {
    /* Handle Error */
  }

  nba->balance = initial_amount;
  result = pthread_mutex_init(&nba->balance_mutex, NULL);
  if (result) {
    /* Handle Error */
  }

  *ba = nba;
}


void *deposit(void *ptr) {
  int result;
  deposit_thr_args *args = (deposit_thr_args *)ptr;

  if ((result = pthread_mutex_lock(&(args->from->balance_mutex))) != 0) {
    /* Handle Error */
  }

  /* not enough balance to transfer */
  if (args->from->balance < args->amount) {
    if ((result = pthread_mutex_unlock(&(args->from->balance_mutex))) != 0) {
      /* Handle Error  */
    }
    return NULL;
  }

  if ((result = pthread_mutex_lock(&(args->to->balance_mutex))) != 0) {
    /* Handle Error */
  }

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

  if ((result = pthread_mutex_unlock(&(args->from->balance_mutex))) != 0) {
    /* Handle Error */
  }
  if ((result = pthread_mutex_unlock(&(args->to->balance_mutex))) != 0) {
    /* Handle Error */
  }


  free(ptr);
  return NULL;
}


int main(void) {

  pthread_t thr1, thr2;
  int result;

  bank_account *ba1;
  bank_account *ba2;
  create_bank_account(&ba1, 1000);
  create_bank_account(&ba2, 1000);

  deposit_thr_args *arg1 = malloc(sizeof(deposit_thr_args));
  if (arg1 == NULL) {
    /* Handle Error */
  }
  deposit_thr_args *arg2 = malloc(sizeof(deposit_thr_args));
  if (arg2 == NULL) {
    /* Handle Error */
  }

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

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

  /* perform the deposits */
  if ((result = pthread_create(&thr1, NULL, deposit, (void *)arg1)) != 0) {
    /* Handle Error */
  }
  if ((result = pthread_create(&thr2, NULL, deposit, (void *)arg2)) != 0) {
    /* Handle Error */
  }

  pthread_exit(NULL);
  return 0;
}

Compliant Solution

The solution to the deadlock problem is to use a predefined order for the locks in the deposit() function. In the following compliant solution, each thread will lock based on the id of bank_account id defined in the struct initialization. This prevents the circular wait problem.

Code Block

bgColor	#ccccff

typedef struct {
  int balance;
  pthread_mutex_t balance_mutex; 
  unsigned int id; /* should never be changed after initialized */
} bank_account;

unsigned int global_id = 1;

void create_bank_account(bank_account **ba, int initial_amount) {
  int result;
  bank_account *nba = malloc(sizeof(bank_account));
  if (nba == NULL) {
    /* Handle Error */
  }

  nba->balance = initial_amount;
  result = pthread_mutex_init(&nba->balance_mutex, NULL);
  if (result != 0) {
    /* Handle Error */
  }

  nba->id = global_id++;
  *ba = nba;
}


void *deposit(void *ptr) {
  deposit_thr_args *args = (deposit_thr_args *)ptr;
  int result;

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

  /* ensure proper ordering for locking */
  if (args->from->id < args->to->id) {
    if ((result = pthread_mutex_lock(&(args->from->balance_mutex))) != 0) {
      /* Handle Error */
    }
    if ((result = pthread_mutex_lock(&(args->to->balance_mutex))) != 0) {
      /* Handle Error */
    }
  } else {
    if ((result = pthread_mutex_lock(&(args->to->balance_mutex))) != 0) {
      /* Handle Error */
    }
    if ((result = pthread_mutex_lock(&(args->from->balance_mutex))) != 0) {
      /* Handle Error */
    }
  }

  /* not enough balance to transfer */
  if (args->from->balance < args->amount) {
    if ((result = pthread_mutex_unlock(&(args->from->balance_mutex))) != 0) {
      /* Handle Error */
    }
    if ((result = pthread_mutex_unlock(&(args->to->balance_mutex))) != 0) {
      /* Handle Error */
    }
    return;
  }

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

  if ((result = pthread_mutex_unlock(&(args->from->balance_mutex))) != 0) {
    /* Handle Error */
  }
  if ((result = pthread_mutex_unlock(&(args->to->balance_mutex))) != 0) {
    /* Handle Error */
  }


  free(ptr);
  return;
}

Risk Assessment

Deadlock causes multiple threads to become unable to progress and thus halts the executing program. This is a potential denial-of-service attack because the attacker can force deadlock situations. It is likely for deadlock to occur in multi-threaded programs that manage multiple shared resources.

Recommendation	Severity	Likelihood	Remediation Cost	Level	Priority
POS43-C	low	probable	medium	L3	P3

Other Languages

This rule appears in the Java Secure Coding Standard as CON14-J. Avoid deadlock by requesting and releasing locks in the same order.

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

...

Space shortcuts

Page tree

Versions Compared

Old Version 39

New Version 40

Key

Noncompliant Code Example

Compliant Solution

Risk Assessment

Other Languages

References