CON35-C. Avoid deadlock by locking in predefined order

Mutexes are often used to prevent multiple threads from accessing critical resources at the same time. Sometimes, when locking mutexes, multiple threads hold each other's lock, and the program consequently deadlocks. There are four requirements for deadlock:

Mutual exclusion
Hold and wait
No preemption
Circular wait

Deadlock requires all four conditions, so preventing deadlock requires preventing any one of the four conditions. One simple solution is to lock the mutexes in a predefined order, which prevents circular wait.

Noncompliant Code Example

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

#include <stdlib.h>
#include <threads.h>
 
typedef struct {
  int balance;
  mtx_t balance_mutex;
} bank_account;

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

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

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

  *ba = nba;
}

int deposit(void *ptr) {
  transaction *args = (transaction *)ptr;

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

  /* Not enough balance to transfer */
  if (args->from->balance < args->amount) {
    if (thrd_success != mtx_unlock(&(args->from->balance_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;

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

  free(ptr);
  
  return 0;
}

int main(void) {
  thrd_t thr1, thr2;
  transaction *arg1;
  transaction *arg2;
  bank_account *ba1;
  bank_account *ba2;

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

  arg1 = (transaction *)malloc(sizeof(transaction));
  if (arg1 == NULL) {
    /* 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;

  /* Perform the deposits. */
  if (thrd_success != thrd_create(&thr1, deposit, (void *)arg1)) {
    /* Handle error */
  }
  if (thrd_success != thrd_create(&thr2, deposit, (void *)arg2)) {
    /* Handle error */
  }
  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 on the basis of the bank_account ID, defined in the struct initialization. This solution prevents the circular wait problem:

#include <stdlib.h>
#include <threads.h>
 
typedef struct {
  int balance;
  mtx_t balance_mutex;
 
  /* Should never be changed after initialized */ 
  unsigned int id;
} bank_account;

unsigned int global_id = 1;

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

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

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

int deposit(void *ptr) {
  transaction *args = (transaction *)ptr;
  int result = -1;
  mtx_t *first;
  mtx_t *second;

  if (args->from->id == args->to->id)
    return -1;  /* Indicate error */

  /* Ensure proper ordering for locking */
  if (args->from->id < args->to->id) {
    first = &args->from->balance_mutex;
    second = &args->to->balance_mutex;
  } else {
    first = &args->to->balance_mutex;
    second = &args->from->balance_mutex;
  }
  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) {
    args->from->balance -= args->amount;
    args->to->balance += args->amount;
    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, thus halting the executing program. A denial-of-service attack is possible because the attacker can force deadlock situations. Deadlock is likely to occur in multithreaded programs that manage multiple shared resources.

Recommendation	Severity	Likelihood	Remediation Cost	Priority	Level
CON35-C	Low	Probable	Medium	P4	L3

Related Vulnerabilities

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

Automated Detection

Tool	Version	Checker	Description
Coverity	6.5	DEADLOCK	Fully implemented

Related Guidelines

CERT Oracle Secure Coding Standard for Java	LCK07-J. Avoid deadlock by requesting and releasing locks in the same order
MITRE CWE	CWE-764, Multiple locks of critical resources

Space shortcuts

Page tree