技術

[xv6 #62] Chapter 5 – File system – Code: Inodes

テキストの70〜71ページ

本文

新しいinodeを割り当てるために(例えば、ファイルを作るときなど)、xv6はialloc関数を呼ぶ。
ialloc関数は、balloc関数に似ていて、ディスク上のinodeの構造体群を走査し、一度に一つのブロックについて、そのブロックが「空き」とマークされているかどうか調べる。
そのようなブロックが見つかったら、新しいtype変数の内容をディスクに書き込み、それからreturn文で呼ばれるiget関数の呼び出しによって、inodeキャッシュから一つのエントリを返す。
balloc関数での処理のように、ialloc関数は正しく処理を行うために、変数bpに対する参照を保持できるのは一度に一つのプロセスだけという事実に依存している。
ialloc関数は、その取得可能なinodeを他のプロセスが同時に参照してない事を保証でき、そしてその取得可能なinodeの要求を試みる。

fs.cのialloc, iget関数

// Allocate a new inode with the given type on device dev.
struct inode*
ialloc(uint dev, short type)
{
  int inum;
  struct buf *bp;
  struct dinode *dip;
  struct superblock sb;

  readsb(dev, &sb);
  for(inum = 1; inum < sb.ninodes; inum++){  // loop over inode blocks
    bp = bread(dev, IBLOCK(inum));
    dip = (struct dinode*)bp->data + inum%IPB;
    if(dip->type == 0){  // a free inode
      memset(dip, 0, sizeof(*dip));
      dip->type = type;
      log_write(bp);   // mark it allocated on the disk
      brelse(bp);
      return iget(dev, inum);
    }
    brelse(bp);
  }
  panic("ialloc: no inodes");
}

// Find the inode with number inum on device dev
// and return the in-memory copy.
static struct inode*
iget(uint dev, uint inum)
{
  struct inode *ip, *empty;

  acquire(&icache.lock);

  // Try for cached inode.
  empty = 0;
  for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){
    if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){
      ip->ref++;
      release(&icache.lock);
      return ip;
    }
    if(empty == 0 && ip->ref == 0)    // Remember empty slot.
      empty = ip;
  }

  // Allocate fresh inode.
  if(empty == 0)
    panic("iget: no inodes");

  ip = empty;
  ip->dev = dev;
  ip->inum = inum;
  ip->ref = 1;
  ip->flags = 0;
  release(&icache.lock);

  return ip;
}

iget関数は、渡されたデバイス番号とinode番号を元に、アクティブなエントリ(ip->ref > 0)を、inodeキャッシュの中を走査して探す。
そのようなエントリが見つかったら、そのinodeに対する新しい参照を返す。
そのiget関数の走査によって、最初の空きスロットの位置を記録し(Remember empty slot.というコメントの部分)、その空きスロットは新しいキャッシュエントリを割り当てる必要がある場合に使われる。
どちらの場合も(inodeキャッシュから見つかった場合とそうでない場合)、iget関数は、呼び出し元に一つの参照を返す。
呼び出し側には、iput関数世を呼び、そのinodeを解放する責任がある。
これは、いくつかのプロセスが、複数回のiput関数の呼び出しを配置する場合に便利である。
idup関数は、inodeの参照カウントを増加させるので、そのinodeのキャッシュをやめさせる前に、追加のiput関数の呼び出しが必要である。

fs.cのidup関数

// Increment reference count for ip.
// Returns ip to enable ip = idup(ip1) idiom.
struct inode*
idup(struct inode *ip)
{
  acquire(&icache.lock);
  ip->ref++;
  release(&icache.lock);
  return ip;
}

呼び出し側は、inodeのメタデータや内容を読み書きする前に、ilock関数を使ってそのinodeをロックしなければならない。
ilock関数は、今はおなじみのsleepループを使って、ip->flagのI_BUSYビットがクリアされるのを待ち、そしたらip->flagにI_BUSYビットをセットする。
一度ilock感菅、inodeに対する排他的なアクセス権を得たら、必要に応じてディスクから(バッファキャッシュからの可能性も高い)そのinodeのメタデータを読み込むことが出来る。
iunlock関数は、I_BUSYビットをクリアし、ilockでスリープしている他のプロセスのいずれかを起こす。

fs.cのilock, iunlock関数

// Lock the given inode.
void
ilock(struct inode *ip)
{
  struct buf *bp;
  struct dinode *dip;

  if(ip == 0 || ip->ref < 1)
    panic("ilock");

  acquire(&icache.lock);
  while(ip->flags & I_BUSY)
    sleep(ip, &icache.lock);
  ip->flags |= I_BUSY;
  release(&icache.lock);

  if(!(ip->flags & I_VALID)){
    bp = bread(ip->dev, IBLOCK(ip->inum));
    dip = (struct dinode*)bp->data + ip->inum%IPB;
    ip->type = dip->type;
    ip->major = dip->major;
    ip->minor = dip->minor;
    ip->nlink = dip->nlink;
    ip->size = dip->size;
    memmove(ip->addrs, dip->addrs, sizeof(ip->addrs));
    brelse(bp);
    ip->flags |= I_VALID;
    if(ip->type == 0)
      panic("ilock: no type");
  }
}

// Unlock the given inode.
void
iunlock(struct inode *ip)
{
  if(ip == 0 || !(ip->flags & I_BUSY) || ip->ref < 1)
    panic("iunlock");

  acquire(&icache.lock);
  ip->flags &= ~I_BUSY;
  wakeup(ip);
  release(&icache.lock);
}

iput関数は、参照カウントをデクリメントする事によって、あるinodeに対するCポインタを解放する。
もし最後の参照だった場合、inodeキャッシュにおけるそのinodeのスロットは空きとなり、他のinodeによって再利用可能となる。

fs.cのiput関数

// Caller holds reference to unlocked ip.  Drop reference.
void
iput(struct inode *ip)
{
  acquire(&icache.lock);
  if(ip->ref == 1 && (ip->flags & I_VALID) && ip->nlink == 0){
    // inode is no longer used: truncate and free inode.
    if(ip->flags & I_BUSY)
      panic("iput busy");
    ip->flags |= I_BUSY;
    release(&icache.lock);
    itrunc(ip);
    ip->type = 0;
    iupdate(ip);
    acquire(&icache.lock);
    ip->flags = 0;
    wakeup(ip);
  }
  ip->ref--;
  release(&icache.lock);
}

もしinodeに対するCポインタが一つも無く、リンクも持たない(どのディレクトリにも属さない)ということをiput関数が発見した場合、そのinodeとそのデータブロックは解放されなければならない。
iput関数は、そのinodeを再ロックし(ip->flags |= I_BUSY;)、ファイルを0バイトに切り詰めるためにitrunc関数を呼び、データブロックを解放し、そのinodeのタイプを0(未割り当て)にセットし、この変更をディスクに書き込み、そして最後にそのinodeのロックを解放(ip->flags = 0;)する。(この一連の処理は、iput関数のif文のブロックの中の話。)

iput関数におけるロック手法は注目に値する。
価値ある例のまず一つめの部分は、ipをロックするとき、iput関数は、sleepループを使わずに、単純にそれがロックされてないだろうと仮定する。
これは、呼び出し側がiput関数を呼び出す前にipをロックしてない事を要求され、そして呼び出し側がそれに対する唯一の参照を持つ(ip->ref == 1)場合でなければならない。
価値ある例の二つめの部分は、iput関数が一時的に解放し(ifブロック中のrelease(&icache.lock);のところ)、再度キャッシュのロックを獲得する(ifブロック中のacquire(&icache.lock);のところ)事である。
これは、itrunc関数とiupdate関数がディスクI/O待ちでスリープする可能性があるので、必要とされるのだが、我々は、ロックを保持してない間に何が起きうるかについて熟考しなければならない。
具体的に言うと、一度iupdate関数が完了したら、ディスク上の構造体は、利用可能である(空きである)とマークされ、そしてiput関数が終わる前に、同時実行されるiallocの呼び出しが、それを見つけ再割当てしてしまうかもしれない。
ialloc関数で、iget関数が呼び出され、iget関数がキャッシュの中からipを見つけ、最終的にialloc関数はそのブロックへの参照を返す可能性がある。
その場合、そのinodeはI_BUSYフラグがセットされている状態であり、ialloc関数の呼び出し側がそのinodeを読み書きしようとしてilock関数を呼び出すと、スリープする。
そうなるとメモリ上のinodeがディスク上のそれと比べて一致してない状態になる。
ialloc関数は、ディスクの側を再初期化したが、ilock関数の間に呼び出し側がそれをメモリに読み込むことを当てにしている。
これが起きることを確実にするために、iput関数は、inodeのロックを解放する前に、I_BUSYフラグだけでなくI_VALIDフラグもクリアしなければならない。
これは、flagsに0をセットすることで行われる。(iput関数のifブロック中のip->flags = 0;のところ)

感想

inodeの管理についてのコードの説明です。
ちょっと最後の段落が難しいです。
重要なのは多分、iputにおける消去処理中のinodeを、偶然他のプロセスがiallocによってされてしまった場合、そのinodeを何も気づかず使ってしまうのを防ぐために、最後にI_VALIDもクリアしてる部分だと思います。
他のプロセスがすでにilockまで到達しsleep中かもしれないので、さらに直後にwakeupを呼ぶことも何気に重要かもしれません。

今まではなるべくソースはそのまま掲載するように、部分的に掲載する場合も関数の順番はなるべく元のままにするようにしてましたが、ちょっと今回は参照する関数が多い上に、本文と元のソースの関数の順番が違いすぎるので、本文に合わせて関数を抜き出しつつ順番を変えて掲載しています。

コメントを残す

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



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

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