技術

[xv6 #42] Chapter 3 – Locking – Exercises

テキストの49〜50ページ

本文

1. acquire関数からxchg命令を取り除きなさい。
そしてxv6を実行したとき何が起きるか説明しなさい。

2. iderw関数のacquireの呼び出しをsleep関数の前に移動しなさい。
競合は存在しますか?
xv6を起動してstressfsプログラムを実行し観察してみよう。
今度は、ダミーのループを使って危険な箇所を増やしてみましょう。
そしたら何が起きますか?説明しなさい。

3. 投稿された宿題をやりなさい。(謎)

4. バッファのflagsフィールドの設定は、アトミックな操作ではない。
プロセッサは、flagsのコピーをレジスタに作り、そのレジスタを変更し、それを書き戻す。
なので、2つのプロセッサが同時にflagsを書き換えないことが重要である。
xv6は、B_BUSYフラグを編集するときだけbuflockを保持するが、B_VALIDとB_WRITEを編集するときはどのロックも使わない。
なぜこれは安全なのだろう?

作業

1. について
spinlock.cのacquire関数のxchg命令を実行してるwhile文ごとコメントアウトしてみました。
release関数内で、ロックが保持されてないのに呼ばれるとpanicするようになってるので、そのとおりになりました。
(これって質問の意図と合ってるのかな)

2. について
ide.cのiderw関数のacquire呼び出しは元々sleep関数の前にありますが、間にキューの操作が入ってるので、その直後と解釈して(stressfsのソースに書いてあるし)、キュー操作の直後(*pp = b;の直後)にacquireを移動してみました。
起動やstressfsの実行程度では問題は表面化しませんでした。
ちなみにstressfsは、4つの子プロセスを数珠つなぎ?に生成しながら、最初の親プロセスも含めた計5つのプロセスで、それぞれ同時に個別のファイルに0〜99を出力するというプログラムです。

次に、acquireの直前のキュー操作の最中(*pp = b;の直前、ループの外)に、ダミーで4万回ループするコード(volatile int i;を使って4万回forループ)を挿入しました。
しかし何回かstressfsしても競合は起きず。
ダミーループの回数を増やしたり、開発環境を実機で動かしたり(いままでVMware上で2コア割り当てたFedoraでコンパイル・実行してた)、QEMUの設定でCPUコア数を8コアぐらいまで増やしたり、コンパイルで生成されたディスクイメージをVMwareに割り当てて直接起動してみたり、stressfsのソースも弄って負荷を上げるようにしたり色々やりましたが、競合は観測できず。

競合が起きると、idequeueの最後の要素が上書きされて失われる場合が出てくるはずで、そうなるとstressfsで出力されるファイルのサイズが普段より少し小さくなるはず、と思ってstressfs後に各ファイルのサイズを調べて競合が起きてるかどうか判断してたんですが、もしかしてそれが悪かったんでしょうか。

なんとしてでも競合を観測したかったんですが、後の章もあるので、この問題は一旦ここで置いておきます。
くやしい。

ide.cのiderw関数(変更前)

// Sync buf with disk. 
// If B_DIRTY is set, write buf to disk, clear B_DIRTY, set B_VALID.
// Else if B_VALID is not set, read buf from disk, set B_VALID.
void
iderw(struct buf *b)
{
  struct buf **pp;

  if(!(b->flags & B_BUSY))
    panic("iderw: buf not busy");
  if((b->flags & (B_VALID|B_DIRTY)) == B_VALID)
    panic("iderw: nothing to do");
  if(b->dev != 0 && !havedisk1)
    panic("iderw: ide disk 1 not present");

  acquire(&idelock);  // DOC:acquire-lock

  // Append b to idequeue.
  b->qnext = 0;
  for(pp=&idequeue; *pp; pp=&(*pp)->qnext)  // DOC:insert-queue
    ;
  *pp = b;
  
  // Start disk if necessary.
  if(idequeue == b)
    idestart(b);
  
  // Wait for request to finish.
  // Assuming will not sleep too long: ignore proc->killed.
  while((b->flags & (B_VALID|B_DIRTY)) != B_VALID){
    sleep(b, &idelock);
  }

  release(&idelock);
}

stressfs.c

// Demonstrate that moving the "acquire" in iderw after the loop that
// appends to the idequeue results in a race.

// For this to work, you should also add a spin within iderw's
// idequeue traversal loop.  Spinning 40000 times demonstrated the bug
// after about 5 runs of stressfs in QEMU on a 2.1GHz CPU.

#include "types.h"
#include "stat.h"
#include "user.h"
#include "fs.h"
#include "fcntl.h"

int
main(int argc, char *argv[])
{
  int fd, i;
  char path[] = "stressfs0";

  printf(1, "stressfs starting\n");

  for(i = 0; i < 4; i++)
    if(fork() > 0)
      break;

  printf(1, "%d\n", i);

  path[8] += i;
  fd = open(path, O_CREATE | O_RDWR);
  for(i = 0; i < 100; i++)
    printf(fd, "%d\n", i);
  close(fd);

  wait();
  
  exit();
}

3. について
謎です。

4. について
本文にB_WRITEとありますが、ソースにそんな定義はないので、他の定義からして多分B_DIRTYの間違いでしょう。
あとbuflockというロック変数もないので、状況からしてbcache.lockのことかと思います。

bio.c

// Buffer cache.
//
// The buffer cache is a linked list of buf structures holding
// cached copies of disk block contents.  Caching disk blocks
// in memory reduces the number of disk reads and also provides
// a synchronization point for disk blocks used by multiple processes.
// 
// Interface:
// * To get a buffer for a particular disk block, call bread.
// * After changing buffer data, call bwrite to flush it to disk.
// * When done with the buffer, call brelse.
// * Do not use the buffer after calling brelse.
// * Only one process at a time can use a buffer,
//     so do not keep them longer than necessary.
// 
// The implementation uses three state flags internally:
// * B_BUSY: the block has been returned from bread
//     and has not been passed back to brelse.  
// * B_VALID: the buffer data has been initialized
//     with the associated disk block contents.
// * B_DIRTY: the buffer data has been modified
//     and needs to be written to disk.

#include "types.h"
#include "defs.h"
#include "param.h"
#include "spinlock.h"
#include "buf.h"

struct {
  struct spinlock lock;
  struct buf buf[NBUF];

  // Linked list of all buffers, through prev/next.
  // head.next is most recently used.
  struct buf head;
} bcache;

void
binit(void)
{
  struct buf *b;

  initlock(&bcache.lock, "bcache");

//PAGEBREAK!
  // Create linked list of buffers
  bcache.head.prev = &bcache.head;
  bcache.head.next = &bcache.head;
  for(b = bcache.buf; b < bcache.buf+NBUF; b++){
    b->next = bcache.head.next;
    b->prev = &bcache.head;
    b->dev = -1;
    bcache.head.next->prev = b;
    bcache.head.next = b;
  }
}

// Look through buffer cache for sector on device dev.
// If not found, allocate fresh block.
// In either case, return locked buffer.
static struct buf*
bget(uint dev, uint sector)
{
  struct buf *b;

  acquire(&bcache.lock);

 loop:
  // Try for cached block.
  for(b = bcache.head.next; b != &bcache.head; b = b->next){
    if(b->dev == dev && b->sector == sector){
      if(!(b->flags & B_BUSY)){
        b->flags |= B_BUSY;
        release(&bcache.lock);
        return b;
      }
      sleep(b, &bcache.lock);
      goto loop;
    }
  }

  // Allocate fresh block.
  for(b = bcache.head.prev; b != &bcache.head; b = b->prev){
    if((b->flags & B_BUSY) == 0){
      b->dev = dev;
      b->sector = sector;
      b->flags = B_BUSY;
      release(&bcache.lock);
      return b;
    }
  }
  panic("bget: no buffers");
}

// Return a B_BUSY buf with the contents of the indicated disk sector.
struct buf*
bread(uint dev, uint sector)
{
  struct buf *b;

  b = bget(dev, sector);
  if(!(b->flags & B_VALID))
    iderw(b);
  return b;
}

// Write b's contents to disk.  Must be locked.
void
bwrite(struct buf *b)
{
  if((b->flags & B_BUSY) == 0)
    panic("bwrite");
  b->flags |= B_DIRTY;
  iderw(b);
}

// Release the buffer b.
void
brelse(struct buf *b)
{
  if((b->flags & B_BUSY) == 0)
    panic("brelse");

  acquire(&bcache.lock);

  b->next->prev = b->prev;
  b->prev->next = b->next;
  b->next = bcache.head.next;
  b->prev = &bcache.head;
  bcache.head.next->prev = b;
  bcache.head.next = b;

  b->flags &= ~B_BUSY;
  wakeup(b);

  release(&bcache.lock);
}

それぞれのフラグの意味をまとまると次のようになります。

B_BUSY
そのバッファはbreadで読み込まれたが、まだbrelseされてない。
breadはディスクからバッファへの読み込みを行う。
brelseはデータをバッファからキャッシュへ移動する。
bio.cのbget関数(breadから呼ばれる)のみでセットされる。

B_VALID
そのバッファは読み込まれまだ変更されてない。
セットされてるのは、ide.cのideintr関数でのみ。

B_DIRTY
バッファの内容が変更されたので書き込みの必要あり。
セットされてるのは、bio.cのbwrite関数でのみ。
ロックはinodeレベルで行われる。

課題の意図としては、bio.cのbget関数でB_BUSYフラグを立てるときはbcache.lockを使ってるのに、他のフラグを立てるときはbcache.lockを使ってないのはなぜ?ということかなと思います。

まずB_VALIDについては、ide.cのideintr関数でフラグを立てますが、ideintrは割り込み中かつ他のロック(idelock)を獲得済みであり、他でロックが必要な操作がされてない事が明らかなのでロックする必要がない、ってところかなと思います。

B_DIRTYについてはちょと追うのが難しかったのですが、要はinodeのレベルでロックを獲得済みだから必要ないのかなと思います。
まだ出てきてないfs.cを読んだところ、システムコールを使って書き込む場合、超大雑把には
sys_write関数→filewrite関数(この中でinode単位でロックを獲得)→writei関数→bwrite関数
という階層関係で関数が呼ばれます。
バッファを内包するinode単位でロックを獲得済みなら、バッファの操作も他と被ることがないから改めてバッファ単位でロックを獲得する必要はないのかなと思います。

感想

なんだか不完全燃焼です。
しかしいつまでもここで留まってるわけにも行かないので先に進みますが、ちょくちょく試してみてとにかく競合状態は確認したいなと思ってます。

コメントを残す

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



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

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください