技術

[xv6 #39] Chapter 3 – Locking – Interrupt handlers

テキストの48ページ

本文

xv6は、あるCPUで実行される割り込みハンドラを、他のCPUで実行され同じデータにアクセスする非割り込みコードから保護するために、ロックを使う。
例えば、タイマー割り込みハンドラは、ticks変数をインクリメントするが、他のCPUでその変数を使うsys_sleep関数が同時に実行される可能性がある。
tickslockというロックは、2つのCPUが1つの変数へ同期的にアクセスするためにある。

trap.cのtrap関数のタイマー割り込みを制御する部分(ticksはtrap.cで uint ticks; と定義されている)

  case T_IRQ0 + IRQ_TIMER:
    if(cpu->id == 0){
      acquire(&tickslock);
      ticks++;
      wakeup(&ticks);
      release(&tickslock);
    }
    lapiceoi();
    break;

sysproc.cのsys_sleep関数(ticksはtrap.cの uint ticks; を参照する)

int
sys_sleep(void)
{
  int n;
  uint ticks0;
  
  if(argint(0, &n) < 0)
    return -1;
  acquire(&tickslock);
  ticks0 = ticks;
  while(ticks - ticks0 < n){
    if(proc->killed){
      release(&tickslock);
      return -1;
    }
    sleep(&ticks, &tickslock);
  }
  release(&tickslock);
  return 0;
}

割り込みは、シングルプロセッサ上でも同じく同時実行を引き起こす可能性がある。
割り込みが有効な場合、カーネルのコードは、割り込みハンドラを実行しないで、いつでも停止することが出来る。
iderw関数がidelockを保持してるときに、ideintrを実行するために割り込まれたと仮定しよう。
ideintrは、idelockを獲得しようとするだろうが、それは既にiderwによって保持されているので、ideintrはそのロックが解放されるまで待つだろう。
しかしこの場合、idelockは決して解放されず(iderwだけがそれを解放可能なのに、iderwはideintrが終わるまで続行することは出来ないので)、プロセッサ、そして結局はシステム全体が、デッドロックに陥るだろう。

そんな事態を避けるために、割り込みが有効かつ、割り込みハンドラでロックが使われている場合、プロセッサはその割り込みの前にそのロックを決して保持しないようにする必要がある。
xv6はかなり保守的である。
xv6は、割り込みが有効な場合は、どんなロックも決して保持しない。
xv6は、”割り込み無効化”の操作のスタックを管理するために、pushcli関数とpopcli関数を使う。
cliとは、割り込みを無効化するx86の命令である。
acquire関数は、ロックを獲得しようとする前にpushcli関数を呼ぶ。
そしてrelease関数は、ロックを開放した後にpopcli関数を呼ぶ。
pushcliとpopcliは、cli命令とsti命令を単純にラップするだけではない。
それらの呼び出し回数は記録され、2回のpushcliの呼び出しを元に戻すためには、2回のpopcliの呼び出しが必要となる。
以上のことから、コードがそれぞれ違う2つのロックを獲得する場合、両方のロックが解放されるまで、割り込みが再度有効になることは無いだろう。

spinlock.c

// Mutual exclusion spin locks.

#include "types.h"
#include "defs.h"
#include "param.h"
#include "x86.h"
#include "memlayout.h"
#include "mmu.h"
#include "proc.h"
#include "spinlock.h"

void
initlock(struct spinlock *lk, char *name)
{
  lk->name = name;
  lk->locked = 0;
  lk->cpu = 0;
}

// Acquire the lock.
// Loops (spins) until the lock is acquired.
// Holding a lock for a long time may cause
// other CPUs to waste time spinning to acquire it.
void
acquire(struct spinlock *lk)
{
  pushcli(); // disable interrupts to avoid deadlock.
  if(holding(lk))
    panic("acquire");

  // The xchg is atomic.
  // It also serializes, so that reads after acquire are not
  // reordered before it. 
  while(xchg(&lk->locked, 1) != 0)
    ;

  // Record info about lock acquisition for debugging.
  lk->cpu = cpu;
  getcallerpcs(&lk, lk->pcs);
}

// Release the lock.
void
release(struct spinlock *lk)
{
  if(!holding(lk))
    panic("release");

  lk->pcs[0] = 0;
  lk->cpu = 0;

  // The xchg serializes, so that reads before release are 
  // not reordered after it.  The 1996 PentiumPro manual (Volume 3,
  // 7.2) says reads can be carried out speculatively and in
  // any order, which implies we need to serialize here.
  // But the 2007 Intel 64 Architecture Memory Ordering White
  // Paper says that Intel 64 and IA-32 will not move a load
  // after a store. So lock->locked = 0 would work here.
  // The xchg being asm volatile ensures gcc emits it after
  // the above assignments (and after the critical section).
  xchg(&lk->locked, 0);

  popcli();
}

// Record the current call stack in pcs[] by following the %ebp chain.
void
getcallerpcs(void *v, uint pcs[])
{
  uint *ebp;
  int i;
  
  ebp = (uint*)v - 2;
  for(i = 0; i < 10; i++){
    if(ebp == 0 || ebp < (uint*)KERNBASE || ebp == (uint*)0xffffffff)
      break;
    pcs&#91;i&#93; = ebp&#91;1&#93;;     // saved %eip
    ebp = (uint*)ebp&#91;0&#93;; // saved %ebp
  }
  for(; i < 10; i++)
    pcs&#91;i&#93; = 0;
}

// Check whether this cpu is holding the lock.
int
holding(struct spinlock *lock)
{
  return lock->locked && lock->cpu == cpu;
}


// Pushcli/popcli are like cli/sti except that they are matched:
// it takes two popcli to undo two pushcli.  Also, if interrupts
// are off, then pushcli, popcli leaves them off.

void
pushcli(void)
{
  int eflags;
  
  eflags = readeflags();
  cli();
  if(cpu->ncli++ == 0)
    cpu->intena = eflags & FL_IF;
}

void
popcli(void)
{
  if(readeflags()&FL_IF)
    panic("popcli - interruptible");
  if(--cpu->ncli < 0)
    panic("popcli");
  if(cpu->ncli == 0 && cpu->intena)
    sti();
}

acquireが、実際にロックを獲得するためのxchg命令を実行する前にpushcliを呼ぶ事は重要である。
それら2つの順番が逆だと、割り込みが有効な場合にロックが保持されたとき、いくつかの命令サイクルののち、残念ながら定期的に区切られる割り込みは、システムをデッドロックに陥れるだろう。(謎)
同様にreleaseが、実際にロックを解放するためのxchg命令を実行する前にpopcliを呼ぶ事は重要である。

割り込みハンドラと割り込みじゃないコードの間の相互作用は、再帰ロックに何故問題があるのかということの良い例である。
xv6が再帰ロックを使った場合(最初のロックの獲得の時と同じCPUでロックを獲得した場合、ひとつのCPU上で分割してロックを獲得することが可能となる。)、割り込みじゃないコードが重要な部分を実行してる時に、割り込みハンドラが実行出来ることとなる。
割り込みハンドラの実行中、そのハンドラのインバリアントは一時的な違反に依存するので、これは混乱をもたらす。
例えばideintrは、リンクリストが正しい形式の未実行リクエストで構成されていると仮定する。
もしxv6が再帰ロックを使ってた場合、ideintrはiderwがリンクリストを操作してる最中に実行でき、そしてリンクリストは最終的におかしな状態になる。

感想

割り込みハンドラとロックの関係についてです。

本文では「xv6は、割り込みが有効な場合は、どんなロックも決して保持しない。」と書かれてますが、処理の説明としては、割り込みが有効なときロックを保持しないのではなく、ロックを保持したら割り込みを無効にする、と言ったほうが正しいかもです。
まぁどっも事実の説明としては、主眼をどこに置くかが違うだけで同じような意味ではあるのですが。

謎と書いた部分についてですが、割り込み無効化→ロック獲得、の順番ではなく、ロック獲得→割り込み無効化、の順番だと、非割り込みコードがロックを保持したまま、割り込みハンドラが実行される可能性があり、そのハンドラが同じロックを保持しようとしてデッドロックに陥る可能性があり、だからダメだということかなと思います。

再帰ロックを採用した場合、非割り込みコードでロックを獲得してるにもかかわらず割り込みが無効にならない、というその理由がよく分かりません。
再帰ロックの場合、何回acquireされたかは、ロック変数毎に保持しとけばいいだけですし、ロックがゼロか否かなんてのは、今のacquireとreleaseの仕組みで十分判定出来るはずです。
だから再帰ロックを使ってても、どっかで1回でもacquireされてたら割り込みを無効にし、全てreleaseされたら再度割り込みを有効にする、なんて事は普通に出来る気がするんですが。

割り込み非割り込みに関わらず、同じCPUなら同じロックを何回でも獲得”出来なければならない”(単に出来るというのとは違って)というのが、ここで言う再帰ロックの定義だというのなら、本文の通りだと思います。

う〜ん、何か思い違いをしてる気がする。

コメントを残す

メールアドレスが公開されることはありません。



※画像をクリックして別の画像を表示