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. There are four requirements for deadlockconsequently deadlocks. Four conditions are required for deadlock to occur:

Mutual Exclusionexclusion
Hold and Waitwait
No Preemptionpreemption
Circular Waitwait

Deadlock needs Each deadlock requires all four . Therefore, to prevent deadlock one just need to avoid conditions, so preventing deadlock requires preventing any one of the four . The advice of this guideline conditions. One simple solution is to require locking lock the mutexes in a predefined order to prevent , 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 main() will deadlock when running thr1 and thr2 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 in the deposit() function and the program will not progress.

Code Block

bgColor	#ffcccc
lang	c


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

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

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

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

  int ret;
  bank_account *nba = (bank_account *)malloc(
    sizeof(bank_account)
  );
  if (nba == NULL) {
    return -1;/* Handle error */
  }

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

  *ba = nba;

  return 0;
}


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

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

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

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

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

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

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

  free(ptr);
  return NULL0;
}

int main(void) {

  pthreadthrd_t thr1, thr2;
  inttransaction err*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);
  if (err < 0) 
  arg1 = exit(err);

  deposit_thr_args *arg1 = (transaction *)malloc(sizeof(deposit_thr_argstransaction));
  if (arg1 == NULL) {
    exit(-1);

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

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

  /* performPerform the depositdeposits */
  err if (thrd_success
     != pthreadthrd_create(&thr1, NULL, deposit, (void *)arg1)); {
    if (err)
    exit(err);

  err = pthread/* Handle error */
  }
  if (thrd_success
      != thrd_create(&thr2, NULL, deposit, (void *)arg2)); {
  if (err)
 /* Handle  exit(err);
error */
  pthread_exit(NULL);
}
  return 0;
}

Compliant Solution

The This compliant solution to the deadlock problem is to lock in predefined order eliminates the circular wait condition by establishing a predefined order for locking in the deposit() function. In the following example, each Each thread will lock based on lock on the basis of the bank_account's id defined in the struct initialization. This way circular wait problem is avoided and when one thread requires a lock will guarantee it will require the next lock 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;
  pthread_mutexmtx_t balance_mutex;
 
  /* Should not change after initialization */
  unsigned int id; /* read only and should never be changed */
} bank_account
} bank_account;

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

unsigned int global_id = 1;

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

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

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

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

  nba->id = global_id++;

  *ba = nba;

  return 0;
}


voidint *deposit(void *ptr) {
	
  deposit_thr_argstransaction *args = (deposit_thr_args *)ptrtransaction *)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 locking */
  if (args->from->id < args->to->id) {
    pthread_mutex_lock(&( first = &args->from->balance_mutex));
    second = pthread_mutex_lock(&(args->to->balance_mutex));
  } else {
     pthread_mutex_lock(&(first = &args->to->balance_mutex));
    second = pthread_mutex_lock(&(args->from->balance_mutex));;
  }
  if (thrd_success != mtx_lock(first)) {
    /* Handle error */
  }
  if (thrd_success != mtx_lock(second)) {
    /* Handle error */
  }

  /* notNot enough balance to transfer */
  if (args->from->balance <>= args->amount) {
    pthread_mutex_unlock(&(args->from->balance_mutex)) -= args->amount;
    pthread_mutex_unlock(&(args->to->balance_mutex)) += args->amount;
    result return= NULL0;
  }

  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;
}

Risk Assessment

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 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 is possible if the attacker can force create the conditions for 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 manually.

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

Other Languages

.

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

References

Prior to 2018-01-12: CERT: Unspecified Relationship

...

Image Added Image Added Image Added 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 32

New Version Current

Key

Noncompliant Code Example

Compliant Solution

Risk Assessment

Risk Assessment

Other Languages

Related Vulnerabilities

Automated Detection

Related Guidelines

References