メモ置き場

ロックの種類と規則 (linux)

20 min read

Lock types and their rules の日本語訳

はじめに

カーネルは主に 3 つのカテゴリに分類できる、様々なロックプリミティブを提供している:

  • sleeping locks
  • CPU local locks
  • Spinning locks

このドキュメントはこれらのロックの種類について説明し、これらを入れ子にするときの規則について説明する。 PREEMPT_RT における規則についても説明する。

ロックの種類

Sleeping locks

Sleeping lock はプリエンプト可能なタスクのコンテキストでのみ獲得することができる。

実装では、他のコンテキストから try_lock() を呼び出すことができるようになっているが、try_lock() の安全性と同じように unlock() の安全性について慎重に評価する必要がある。 さらに、これらのプリミティブのデバッグ用のバージョンについても同様に慎重に評価する必要がある。 つまり、他に選択肢がない限り、他のコンテキストから sleeping lock を獲得してはいけない。

Sleeping lock の種類は以下の通り:

  • mutex
  • rt_mutex
  • semaphore
  • rw_semaphore
  • ww_mutex
  • percpu_rw_semaphore

PREEMPT_RT なカーネルでは、以下の種類のロックも sleeping lock になる:

  • local_lock
  • spinlock_t
  • rwlock_t

CPU local locks

  • local_lock

PREEMPT_RT ではないカーネルにおいて、local_lock に関する関数はプリエンプションと割り込みを無効化するプリミティブのラッパーである。 他のロック機構とは異なり、プリエンプションや割り込みを無効化することは純粋に CPU ローカルな並列制御機構であり、CPU 間の並列制御には向いていない。

Spinning locks

  • raw_spinlock_t
  • bit spinlocks

PREEMPT_RT ではないカーネルにおいて、以下の種類のロックも spinning lock である:

  • spinlock_t
  • rwlock_t

Spinning lock は暗黙裡にプリエンプションを無効化する。 ロック・アンロックをする関数は、その接尾辞によってさらなる保護を適用する:

  • _bh() - ソフトウェア割り込み (bottom halves とも呼ぶ) を無効化・有効化する
  • _irq() - 割り込みを無効化・有効化する
  • _irqsave/restore() - 割り込みの無効化・有効化状態を保存して無効化、復元する

所有者意味論

Semaphore 以外の先述のロックは、厳格な所有者意味論を持つ: ロックを獲得したコンテキスト (タスク) がロックを解放しなければならない。

Rw_semaphore は reader のために所有者以外が解放するための特別なインターフェースを持つ。

rtmutex

RT-mutex は優先度継承 (priority inheritance; PI) をサポートしている mutex である。

PI は PREEMPT_RT ではないカーネルにおいて、プリエンプションと割り込みが無効化されたセクションのせいで制約がある。

PI は明らかに、プリエンプションが無効であるまたは割り込みが無効であるコード領域をプリエンプトすることができない。 PREEMPT_RT なカーネルにおいてさえ同様である。 代わりに、PREEMPT_RT なカーネルはそのようなコード領域の大部分、特に割り込みハンドラやソフトウェア割り込みなどのコード領域をプリエンプト可能なコンテキストで実行する。 このような変更により、spinlock_t と rwlock_t を RT-mutex を使って実装することができるようになる。

semaphore

semaphore はカウンティング・セマフォの実装である。

セマフォは直列化と待機の両方に使われるが、新しいユースケースでは、mutex と completion のように直列化と待機の別々のメカニズムを使うべきである。

Semaphore と PREEMPT_RT

PREEMPT_RT によって semaphore の実装は変化しない。なぜなら、カウンティング・セマフォには所有者の概念はなく、したがって PREEMPT_RT によって優先度継承を semaphore 向けに提供することができないからである。 結局、所有者が不明ならブーストすることはできない。 結果として、semaphore においてブロックすると優先度の逆転が発生してしまう。

rw_semaphore

rw_semaphore は複数の reader と 1 つの writer のロック機構である。

PREEMPT_RT でないカーネルにおいて、rw_semaphore の実装は公平であるため、writer は飢餓状態にならない。

rw_semaphore はデフォルトでは厳格な所有者意味論に従う。 しかし、所有者以外が reader のためにロックを解放するインターフェースが存在する。 これらのインターフェースはカーネルの設定とは無関係に動作する。

rw_semaphore と PREEMPT_RT

PREEMPT_RT なカーネルは rw_semaphore を rt_mutex をベースとした別の実装にマップする。 そのため、次のように公平性が変化する:

rw_semaphore では writer が複数の reader に優先度を与えることができないため、プリエンプトされた低優先度の reader はロックを所有し続け、高優先度の writer でさえ飢餓状態になる。 一方で、reader は writer に優先度を与えることができるため、プリエンプトされた低優先度の writer はロックを解放するまで優先度ブーストされることができ、したがって writer のせいで reader が飢餓状態になることはない。

local_lock

local_lock はプリエンプションまたは割り込みの無効化によって保護されたクリティカルセクションに名前付きのスコープをもたらす。

PREEMPT_RT ではないカーネルにおいて、local_lock の関数はプリエンプションと割り込みを無効化・有効化するプリミティブにマップされる:

  • local_lock(&llock) - preempt_disable()
  • local_unlock(&llock) - preempt_enable()
  • local_lock_irq(&llock) - local_irq_disable()
  • local_unlock_irq(&llock) - local_irq_enable()
  • local_lock_irqsave(&llock) - local_irq_save()
  • local_unlock_irqrestore(&llock) - local_irq_restore()

local_lock の名前付きスコープには通常のプリミティブに比べて 2 つの利点がある:

  • 通常のプリミティブにはスコープがなく不透明であるが、ロックに名前があることによって静的解析と保護のスコープについて明確なドキュメンテーションが可能になる。
  • lockdep が有効化されている場合、local_lock は保護の正しさを検証することを可能にする lockmap を獲得できる。これにより、たとえば保護機構として preempt_disable() を使用している関数が割り込みやソフトウェア割り込みのコンテキストから呼び出されるケースを検出することができる。lockdep_assert_held(&llock) は他のロックプリミティブと同様に動作する。

local_lock と PREEMPT_RT

PREEMPT_RT なカーネルは local_lock を CPU ごとの spinlock_t へマップする。 そのため、意味論が変化する:

  • spinlock_t におけるすべての変化が local_lock においても適用される。

local_lock の使用方法

PREEMPT_RT でないカーネルにおいて、local_lock はプリエンプションや割り込みを無効化することが CPU ごとのデータ構造を保護するための並列制御の適切な形態である状況で使用されるべきである。

PREEMPT_RT 特有の spinlock_t の意味論のせいで、PREEMPT_RT なカーネルにおいて、local_lock はプリエンプションや割り込みからの保護には向いていない。

raw_spinlock_t と spinlock_t

raw_spinlock_t

raw_spinlock_t は PREEMPT_RT なカーネルも含むすべてのカーネルにある、厳格なスピンロックの実装である。 低レベルの割り込みハンドリングや、例えばハードウェアの状態に安全にアクセスするためなど、プリエンプションや割り込みの無効化が必要な場所で、本当にクリティカルなコア部分のコードでのみ raw_spinlock_t を使用せよ。 時には raw_spinlock_t はクリティカルセクションが小さいとき、RT-mutex のオーバーヘッドを避けるためにも使用される。

spinlock_t

spinlock_t の意味論は PREEMPT_RT かどうかによって変わる。

PREEMPT_RT でないカーネルでは、spinlock_t は raw_spinlock_t にマップされ、全く同じ意味論を持つ。

spinlock_t と PREEMPT_RT

PREEMPT_RT なカーネルでは、spinlock_t は rt_mutex を元にした別の実装にマップされ、意味論が変化する:

  • プリエンプションは無効化されない
  • spin_lock、spin_unlock 操作における、ハードウェア割り込みに関する接尾辞 (_irq、_irqsave、_irqrestore) は CPU の割り込み無効化状態に影響を及ぼさない
  • ソフトウェア割り込みに関する接尾辞 (_bh()) は、PREEMPT_RT でないカーネルと同様にソフトウェア割り込みハンドラを無効化する。PREEMPT_RT でないカーネルは、ソフトウェア割り込みハンドラを無効化するためにプリエンプションを無効化する。PREEMPT_RT なカーネルはプリエンプションは有効なまま、直列化のために CPU ごとのロックを使用する。このロックはソフトウェア割り込みハンドラを無効化し、タスクのプリエンプションによる再入を妨げる。

PREEMPT_RT なカーネルは spinlock_t の他のすべての意味論を保つ:

  • spinlock_t を所有しているタスクは移動しない。PREEMPT_RT でないカーネルはプリエンプションの無効化によってタスクの移動を防ぐ。PREEMPT_RT なカーネルは代わりにタスクの移動を無効化し、CPU ごとの変数へのポインタがタスクがプリエンプトされた場合でさえ有効なままになるようにする。
  • タスクの状態はスピンロックの獲得を通して保存され、タスク状態の規則がすべてのカーネル設定に従うことを保証する。PREEMPT_RT でないカーネルはタスクの状態にアクセスしないようにする。しかし、PREEMPT_RT なカーネルでは、ロックの獲得中にタスクがブロックされた場合、タスクの状態を変更しなければならない。したがって、いかに示すように、ブロックの前に現在のタスクの状態を保存し、ロックによる対応する起床時に復元する。
task->state = TASK_INTERRUPTIBLE
 lock()
  block()
    task->saved_state = task->state
    task->state = TASK_UNINTERRUPTIBLE
    schedule()
                                   ロックによる起床
                                     task->state = task->saved_state

他の種類の起床では、通常は無条件にタスクの状態を RUNNING に設定する。 しかし、タスクはロックが利用可能になるまでブロックされたままになる必要があるため、このケースではうまくいかない。 そのため、スピンロックを待機していてブロックされているタスクが、ロック以外の要因で起床しようとするとき、代わりに保存された状態を RUNNING に設定する。 これにより、ロックの獲得が完了したとき、ロックによる起床によってタスクの状態が保存された状態、この場合は RUNNING に設定される。

task->state = TASK_INTERRUPTIBLE
 lock()
   block()
     task->saved_state = task->state
     task->state = TASK_UNINTERRUPTIBLE
     schedule()
                                    ロックによるものではない起床
                                      task->saved_state = TASK_RUNNING

                                    ロックによる起床
                                      task->state = task->saved_state

これによって実際の起床が失われないようになる。

rwlock_t

rwlock_t は複数の reader と 1 つの writer のロック機構である。

PREEMPT_RT ではないカーネルでは、rwlock_t はスピンロックとして実装されており、関数名の接尾辞の意味は spinlock_t と同様である。 実装は公平であり、writer は飢餓状態にならない。

rwlock_t と PREEMPT_RT

PREEMPT_RT なカーネルでは、rwlock_t は rt_mutex を元にした別の実装にマップされ、意味論が変化する:

  • spinlock_t に関するすべての変更が rwlock_t にも適用される
  • rwlock_t の writer は複数の reader に優先度を与えることができないため、プリエンプトされた低優先度の reader はロックを保持し続け、高優先度の writer でさえ飢餓状態になる。一方で、reader は writer に優先度を与えることができるため、プリエンプトされた低優先度の writer はロックを解放するまで優先度ブーストを受けることができ、writer によって reader が飢餓状態になることはない。

PREEMPT_RT に関する補足事項

PREEMPT_RT における local_lock

PREEMPT_RT なカーネルにおいて local_lock が spinlock_t にマップされることによって、副次的な影響がある。 例えば、PREEMPT_RT ではないカーネルにおいて次のコードは期待通りに動作する:

local_lock_irq(&local_lock);
raw_spin_lock(&lock);

そして、以下と完全に同じである:

raw_spin_lock_irq(&lock);

PREEMPT_RT なカーネルにおいて、local_lock_irq() は割り込みもプリエンプションも無効化しない CPU ごとの spinlock_t にマップされるため、このコードは壊れる。 次のコードは PREEMPT_RT なカーネルにおいても PREEMPT_RT でないカーネルにおいても完全に正しく機能する:

local_lock_irq(&local_lock);
spin_lock(&lock);

local lock に関する他の補足事項として、それぞれの local_lock は特定の保護スコープを持つということがある。 そのため、次の置き換えは間違いである:

func1()
{
    local_irq_save(flags);    -> local_lock_irqsave(&local_lock_1, flags);
    func3();
    local_irq_restore(flags); -> local_unlock_irqrestore(&local_lock_1, flags);
}
 
func2()
{
    local_irq_save(flags);    -> local_lock_irqsave(&local_lock_2, flags);
    func3();
    local_irq_restore(flags); -> local_unlock_irqrestore(&local_lock_2, flags);
}
 
func3()
{
    lockdep_assert_irqs_disabled();
    access_protected_data();
}

PREEMPT_RT でないカーネルにおいて、これは正しく動作する。 しかし、PREEMPT_RT なカーネルにおいて、local_lock_1 と local_lock_2 は区別されており、func3() の呼び出し元を直列化できない。 さらに、PREEMPT_RT なカーネルにおいて、spinlock_t の PREEMPT_RT 特有の意味論によって local_lock_irqsave() は割り込みを無効化しないため、lockdep のアサーションがトリガーされる。 正しい置き換えは以下の通りである:

func1()
{
  local_irq_save(flags);    -> local_lock_irqsave(&local_lock, flags);
  func3();
  local_irq_restore(flags); -> local_unlock_irqrestore(&local_lock, flags);
}
 
func2()
{
  local_irq_save(flags);    -> local_lock_irqsave(&local_lock, flags);
  func3();
  local_irq_restore(flags); -> local_unlock_irqrestore(&local_lock, flags);
}
 
func3()
{
  lockdep_assert_held(&local_lock);
  access_protected_data();
}

spinlock_t と rwlock_t

PREEMPT_RT なカーネルにおける spinlock_t と rwlock_t の意味論の変化により、副次的な影響がある。 例えば、PREEMPT_RT でないカーネルにおいて、次のコードは期待通りに動作する:

local_irq_disable();
spin_lock(&lock);

そして以下のコードと完全に同じである:

spin_lock_irq(&lock);

同じことが rwlock_t とその接尾辞 _irqsave() にも言える。

PREEMPT_RT なカーネルでは、RT-mutex が完全にプリエンプション可能なコンテキストを要求するので、このコードは壊れる。 代わりに、spin_lock_irq() か spin_lock_irqsave() とそれに対応する unlock 用関数を使用せよ。 割り込みとロックが分かれたままになっている必要があるケースのために、PREEMPT_RT なカーネルでは local_lock 機構が提供されている。 local_lock を取得することでタスクが CPU に固定され、CPU ごとの割り込みが無効化されたロックが獲得できるようになる。 しかし、このアプローチは絶対に必要な場合のみ用いられるべきである。

典型的なシナリオはスレッドのコンテキストで CPU ごとの変数を保護する場合である:

struct foo *p = get_cpu_ptr(&var1);
 
spin_lock(&p->lock);
p->count += this_cpu_read(var2);

このコードは PREEMPT_RT でないカーネルでは正しいが、PREEMPT_RT なカーネルでは壊れる。 spinlock_t の意味論の PREEMPT_RT 特有の変化によって、get_cpu_ptr() は暗黙裡にプリエンプションを無効化するので、p->lock を獲得することができない。 次に示す置き換えはどちらのカーネルでも動作する:

struct foo *p;
 
migrate_disable();
p = this_cpu_ptr(&var1);
spin_lock(&p->lock);
p->count += this_cpu_read(var2);

migrate_disable() はタスクを現在の CPU に固定し、タスクをプリエンプト可能にしたまま CPU ごとの var1 と var2 へのアクセスが同じ CPU から行われることを保証する。

migrate_disable() への置き換えは以下のシナリオでは正しくない:

 
func()
{
  struct foo *p;
 
  migrate_disable();
  p = this_cpu_ptr(&var1);
  p->val = func2();

migrate_disable() はプリエンプトしているタスクからの再入からの保護をしないため、このコードは壊れる。 この場合の正しい置き換えは以下の通りである:

func()
{
  struct foo *p;
 
  local_lock(&foo_lock);
  p = this_cpu_ptr(&var1);
  p->val = func2();

PREEMPT_RT でないカーネルにおいて、この手法はプリエンプトを無効化することによって再入からの保護をする。 PREEMPT_RT なカーネルでは、CPU ごとのスピンロックを獲得することによって再入からの保護をする。

"上"のページ: Linuxカーネル

グラフビュー