Page History

...

Code Block

bgColor	#ffcccc

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

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

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

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

  bank_account *nba = malloc(sizeof(bank_account));
  if (nba == NULL) {
    return -1;
  }

  nba->balance = initial_amount;
  pthread_mutex_init(&nba->balance_mutex, NULL);

  *ba = nba;

  return 0;
}


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

  pthread_mutex_lock(&(args->from->balance_mutex));

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

  pthread_mutex_lock(&(args->to->balance_mutex));
  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));
  if (arg1 == NULL)
    exit(-1);

  deposit_thr_args *arg2 = malloc(sizeof(deposit_thr_args));
  if (arg2 == NULL)
    exit(-1);

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

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

  /* perform the deposit */
  err = pthread_create(&thr1, NULL, deposit, (void *)arg1);
  if (err)
    exit(err);

  err = pthread_create(&thr2, NULL, deposit, (void *)arg2);
  if (err)
    exit(err);

  pthread_exit(NULL);

  return 0;
}

...

The 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 lock.

Code Block

bgColor	#ccccff


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

typedef struct {
  int balance;
  pthread_mutex_t balance_mutex; 
  unsigned int id; /* read only and should never be changed */
} bank_account;

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

unsigned int global_id = 1;

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

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

  if (nba == NULL) {
    return -1;
  }

  nba->balance = initial_amount;
  pthread_mutex_init(&nba->balance_mutex, NULL);
  nba->id = global_id++;

  *ba = nba;

  return 0;
}


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

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

  /* ensure proper ordering for locking */
  if (args->from->id < args->to->id) {
    pthread_mutex_lock(&(args->from->balance_mutex));
    pthread_mutex_lock(&(args->to->balance_mutex));
  } else {
    pthread_mutex_lock(&(args->to->balance_mutex));
    pthread_mutex_lock(&(args->from->balance_mutex));
  }

  /* 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 manually.

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

Other Languages

CON12-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

Other Languages

CON12-J. Avoid deadlock by requesting and releasing locks in the same order

Space shortcuts

Page tree

Versions Compared

Old Version 28

New Version 29

Key

Risk Assessment

Other Languages

References

Other Languages