Page History

Mutexes are used to prevent multiple threads from causing a data race by accessing shared resources at the same time. Sometimes, when locking mutexes, multiple threads hold each other's lock, and the program 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 the mutexes in a predefined order, which prevents circular wait.

Noncompliant Code Example

The behavior of this noncompliant code example depends on the runtime environment and the platform's scheduler. The program is susceptible to deadlock if thread thr1 attempts to lock ba2's mutex at the same time thread thr2 attempts to lock ba1's mutex in the deposit() function.

Code Block

bgColor	#ffcccc
lang	c

#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

This compliant solution eliminates 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 <stdlib.h>
#include <threads.h>
 
typedef struct {
  int balance;
  mtx_t balance_mutex;
 
  /* Should not change after initialization */
  unsigned int id;
} bank_account;

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

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, halting program execution. A denial-of-service attack is possible if the attacker can create the conditions for deadlock.

Rule	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

Astrée

Include Page

	Astrée_V
	Astrée_V

deadlock

Supported by sound analysis (deadlock alarm)

CodeSonar

Include Page

	CodeSonar_V
	CodeSonar_V

CONCURRENCY.LOCK.ORDER

Conflicting lock order

Coverity

Include Page

	Coverity_V
	Coverity_V

ORDER_REVERSAL

Fully implemented

Cppcheck Premium

Include Page

	Cppcheck Premium_V
	Cppcheck Premium_V

premium-cert-con35-c

Partially implemented

Helix QAC

Include Page

	Helix QAC_V
	Helix QAC_V

C1772, C1773

Klocwork

Include Page

	Klocwork_V
	Klocwork_V

CONC.DL
CONC.NO_UNLOCK

Parasoft C/C++test

Include Page

	Parasoft_V
	Parasoft_V

CERT_C-CON35-a

Do not acquire locks in different order

PC-lint Plus

Include Page

	PC-lint Plus_V
	PC-lint Plus_V

2462

Fully supported

Polyspace Bug Finder

Include Page

	Polyspace Bug Finder_V
	Polyspace Bug Finder_V

CERT C: Rule CON35-C

Checks for deadlock (rule partially covered)

Related Guidelines

Key here (explains table format and definitions)

Taxonomy	Taxonomy item	Relationship
CERT Oracle Secure Coding Standard for Java	LCK07-J. Avoid deadlock by requesting and releasing locks in the same order	Prior to 2018-01-12: CERT: Unspecified Relationship

...

Image Added Image Added Image Added

Introduction

Whenever threads come into play, there are bounded to be shared memory or resources that each thread wants to access. But because of the random nature of execution of each thread, there will be corruption of data when multiple threads try to read and write into the same memory space. One possible way to fix the problem is using locking mechanism like a mutex. POSIX provides a mutex called pthread_mutex_t just for this purpose.

Deadlock can happen when multiple threads each holds a lock the other needs and are waiting for each other to release the resource. One way to fix the problem is to avoid circular wait by locking the mutex in a predefined order.

Noncompliant Code Example

...

bgColor	#ccccff

...

Space shortcuts

Page tree

Versions Compared

Old Version 4

New Version Current

Key

Noncompliant Code Example

Compliant Solution

Risk Assessment

Related Vulnerabilities

Automated Detection

Related Guidelines

Introduction

Noncompliant Code Example