CON35-C. あらかじめ定義した順番でロックしてデッドロックを防ぐ

複数のスレッドが重要なリソースに同時にアクセスするのを防ぐために、ミューテックスが使われることが多い。このミューテックスをロックしたときに、複数のスレッドが互いのロックを保持し合い、プログラムのデッドロックを引き起こすことがある。デッドロックが生じる条件は、次のように 4 つある。

相互排他
保持したまま待機
先取り不可
巡回待機

デッドロックが生じるには、4 つの条件がすべて成立する必要があるため、デッドロックを防ぐには、4 つの条件のいずれかを防げばよい。このガイドラインでは、ミューテックスをあらかじめ定義した順番でロックして巡回待機を防ぐことを推奨する。

違反コード

次のコードは、実行時環境やプラットフォームのスケジューラに依存する動作をもたらす。しかし、thr1 と thr2 の実行中に、thr1 が ba2 のミューテックスをロックしようとし、thr2 が deposit() 関数内で ba1 のミューテックスをロックしようとした場合に、しかるべきタイミングで main() 関数がデッドロックする。

typedef struct {
  int balance;
  mtx_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) {
    /* エラー処理 */
  }

  nba->balance = initial_amount;
  result = mtx_init(&nba->balance_mutex, mtx_plain);
  if (result == thrd_error) {
    /* エラー処理 */
  }

  *ba = nba;
}


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

  if ((result = mtx_lock(&(args->from->balance_mutex))) != thrd_success) {
    /* エラー処理 */
  }

  /* 送金に必要な残高が足りない */
  if (args->from->balance < args->amount) {
    if ((result = mtx_unlock(&(args->from->balance_mutex))) != thrd_success) {
      /* エラー処理  */
    }
    return NULL;
  }

  if ((result = mtx_lock(&(args->to->balance_mutex))) != thrd_success) {
    /* エラー処理 */
  }

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

  if ((result = mtx_unlock(&(args->from->balance_mutex))) != thrd_success) {
    /* エラー処理 */
  }
  if ((result = mtx_unlock(&(args->to->balance_mutex))) != thrd_success) {
    /* エラー処理 */
  }


  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) {
    /* エラー処理 */
  }
  deposit_thr_args *arg2 = malloc(sizeof(deposit_thr_args));
  if (arg2 == NULL) {
    /* エラー処理 */
  }

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

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

  /* 入金処理を実行 */
  if ((result = thrd_create(&thr1, deposit, (void *)arg1)) != thrd_success) {
    /* エラー処理 */
  }
  if ((result = thrd_create(&thr2, deposit, (void *)arg2)) != thrd_success) {
    /* エラー処理 */
  }

  thrd_exit(NULL);
  return 0;
}

適合コード

デッドロックの問題を解決するには、deposit() 関数内でロックの順番をあらかじめ定義しておく。以下の適合コードでは、各スレッドは struct の初期化時に定義した bank_account の ID に基づいてロックを実施している。この適合コードにより巡回待機の問題を防ぐことができる。

typedef struct {
  int balance;
  mtx_t balance_mutex;
  unsigned int id; /* 初期化した後は変更してはならない */
} 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) {
    /* エラー処理 */
  }

  nba->balance = initial_amount;
  result = mtx_init(&nba->balance_mutex, mtx_plain);
  if (result != thrd_success) {
    /* エラー処理 */
  }

  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;

  /* 正しいロック順序を確保 */
  if (args->from->id < args->to->id) {
    if ((result = mtx_lock(&(args->from->balance_mutex))) != thrd_success) {
      /* エラー処理 */
    }
    if ((result = mtx_lock(&(args->to->balance_mutex))) != thrd_success) {
      /* エラー処理 */
    }
  } else {
    if ((result = mtx_lock(&(args->to->balance_mutex))) != thrd_success) {
      /* エラー処理 */
    }
    if ((result = mtx_lock(&(args->from->balance_mutex))) != thrd_success) {
      /* エラー処理 */
    }
  }

  /* 送金に必要な残高が足りない */
  if (args->from->balance < args->amount) {
    if ((result = mtx_unlock(&(args->from->balance_mutex))) != thrd_success) {
      /* エラー処理 */
    }
    if ((result = mtx_unlock(&(args->to->balance_mutex))) != thrd_success) {
      /* エラー処理 */
    }
    return;
  }

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

  if ((result = mtx_unlock(&(args->from->balance_mutex))) != thrd_success) {
    /* エラー処理 */
  }
  if ((result = mtx_unlock(&(args->to->balance_mutex))) != thrd_success) {
    /* エラー処理 */
  }


  free(ptr);
  return;
}

リスク評価

デッドロックにより複数のスレッドの処理が妨げられ、プログラムの実行停止につながる。これにより、攻撃者はデッドロック状態を強要することができるため、サービス運用妨害(DoS)攻撃が引き起こされる可能性がある。デッドロックは、複数の共有リソースを管理するマルチスレッドプログラムで生じる可能性がある。

レコメンデーション	深刻度	可能性	修正コスト	優先度	レベル
CON35-C	低	中	中	P4	L3

自動検出（最新の情報はこちら）

ツール	バージョン	チェッカー	説明
Coverity	6.5	DEADLOCK	実装済み

参考資料

[Barney 2010]	pthread_mutex tutorial
[Bryant 2003]	Chapter 13, "Concurrent Programming"

翻訳元

これは以下のページを翻訳したものです。

CON35-C. Avoid deadlock by locking in predefined order (revision 58)

Top へ

Topへ

CERT Oracle Secure Coding Standard for Java	LCK07-J. デッドロックを回避するためにロックは同一順序で要求および解放する
MITRE CWE	CWE-764, Multiple locks of critical resources