日曜研究室 LLVMによるプログラミング言語の実装 xv6ソースコードリーディング 技術 日記
日曜研究室

日曜研究室

まだ庭の小石の数を数え終わっていない

技術

[xv6 #69] Chapter 5 – File system – Exercises

投稿日
2012/4/29 日曜日
カテゴリー
技術
タグ
著者
Take it easy!

テキストの77ページ

本文

1. どういう場合にballocでpanicが起きるか？ それを回復することはできるか？

2. どういう場合にiallocでpanicが起きるか？ それを回復することはできるか？

3. inode世代番号。

4. fileがない場合になぜfileallocはpanicを起こさないのか？ なぜこれがより一般的でそれゆえ良いハンドリングの方法なのか？

5. sys_linkがiunlock(ip)とdirlinkを呼び出す間に、そのipが、他のプロセスによってアンリンクされたipと一致すると仮定する。
リンクは正しく作成されるだろうか？
なぜ正しく作成されるのか？もしくはなぜ正しく作成されないのか？

6. createは正常に完了するために4つの関数呼び出し（一つはialloc、他の三つはdirlink）を必要とする。
そうでない場合、createはpanicを呼ぶ。
なぜこれは許容できるのか？
なぜ、それらの4つの関数呼び出しは失敗し得ないのだろうか？

7. sys_chdirはiput(cp->cwd)の前にiunlock(ip)を呼び、iput(cp->cwd)はcp->cwdをロックしようとする。
iputの後のiunlock(ip)はデッドロックを引き起こさないが、それは何故か？

作業

1. について

見ての通り、ballocは空いてるブロックを探して返すので、空きブロックがなければpanicまで到達します。
panicじゃなくて呼び出し元に例外を通知するような仕組みにするとpanicは回避出来るかもしれませんが、どちらにしろ無いものを魔法の力で捻出することは出来ないので回復は無理だと思います。

fs.cのballoc関数

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Allocate a zeroed disk block.
static uint
balloc(uint dev)
{
  int b, bi, m;
  struct buf *bp;
  struct superblock sb;
 
  bp = 0;
  readsb(dev, &sb);
  for(b = 0; b < sb.size; b += BPB){
    bp = bread(dev, BBLOCK(b, sb.ninodes));
    for(bi = 0; bi < BPB && bi < (sb.size - b); bi++){
      m = 1 << (bi % 8);
      if((bp->data[bi/8] & m) == 0){  // Is block free?
        bp->data[bi/8] |= m;  // Mark block in use on disk.
        log_write(bp);
        brelse(bp);
        bzero(dev, b + bi);
        return b + bi;
      }
    }
    brelse(bp);
  }
  panic("balloc: out of blocks");
}

2. について

これも1と同じだと思います。

fs.cのialloc関数

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 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");
}

3. について

元の文もinode generation numbers.だけなのでちょっと課題の意図が分かりませんが、inode世代番号を実装するにはどうしたら良いか？という事だと解釈して考えてみます。
まずinode世代番号というのは、あるinodeが指し示すデータが変更されたタイミングでインクリメントされる値です。（多分…）
これはinodeの変更状況を追跡するのに使えて、その値を元に割り当てのアルゴリズムなんかも改良出来たりするんじゃないかななんて思います。（想像）
inode世代番号なんて言葉正直今日知りました。
で、inode世代番号の実装方法ですが、まずinode構造体とdinode構造体に世代番号のフィールドを追加する必要があるでしょう。
dinodeのほうには追加せずに、例えばスーパーブロックとかにまとめて記録するのもありかもしれません。
そしたら、fs.cのwritei関数でその世代番号をインクリメントしてあげればいいと思いますが、ジャーナリングのために実際はwriteiではなくそこから呼ばれるlog_writeで書き込みが行われるので、そちらで実装する必要があると思います。
実際の実装レベルであまり細かいところまで考えるとロックとかでドツボにハマリそうなのでこの程度で勘弁していただきたく…

4. について

ballocやiallocは、ブロックやinode単位の割り当てであり、そのレベルで失敗してもユーザプログラムは正直何も出来ないはず（何か出来るということはカーネルがやってることより難しいことをしなきゃならないわけで…）なので、panicせずユーザプログラムに事後処理の責任を負わせるのは現実的じゃないと思います。
一方、fileallocが失敗するのは、システム全体で同時に開けるファイルの最大数（xv6の場合はたったの100）に達したときであって、前者の失敗の深刻度と比べたら、かなりヌルい失敗と言えます。
ユーザプログラムも、fileallocが失敗したら、必要なファイルが開けなかったとして単に終了するとか、開けるようになるまで、それまで開いてて必要のないファイルを閉じるとかの事後処理が行え、その実装はプログラムの内容にもよりますが基本的にはそう難しくないはずです。
なので、このレベルの失敗でいちいちpanicするよりは、ユーザプログラムにその後の処理を任せた方が現実的かなと思います。

file.cのfilealloc関数

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
// Allocate a file structure.
struct file*
filealloc(void)
{
  struct file *f;
 
  acquire(&ftable.lock);
  for(f = ftable.file; f < ftable.file + NFILE; f++){
    if(f->ref == 0){
      f->ref = 1;
      release(&ftable.lock);
      return f;
    }
  }
  release(&ftable.lock);
  return 0;
}

5. について

質問の答えとしては、「正しく作成されない。なぜならdirlinkが失敗するので、badラベル以下の行が実行され巻き戻されるので。」ということになるかと思います。
トランザクションを使ってるので、中途半端な状態で終わることはないので問題ないはずです。

sysfile.cのsys_link関数

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// Create the path new as a link to the same inode as old.
int
sys_link(void)
{
  char name[DIRSIZ], *new, *old;
  struct inode *dp, *ip;
 
  if(argstr(0, &old) < 0 || argstr(1, &new) < 0)
    return -1;
  if((ip = namei(old)) == 0)
    return -1;
 
  begin_trans();
 
  ilock(ip);
  if(ip->type == T_DIR){
    iunlockput(ip);
    commit_trans();
    return -1;
  }
 
  ip->nlink++;
  iupdate(ip);
  iunlock(ip);
 
  if((dp = nameiparent(new, name)) == 0)
    goto bad;
  ilock(dp);
  if(dp->dev != ip->dev || dirlink(dp, name, ip->inum) < 0){
    iunlockput(dp);
    goto bad;
  }
  iunlockput(dp);
  iput(ip);
 
  commit_trans();
 
  return 0;
 
bad:
  ilock(ip);
  ip->nlink--;
  iupdate(ip);
  iunlockput(ip);
  commit_trans();
  return -1;
}

6. について

まず、dirlinkが失敗（panicではなく）するパターンというのは、対象のディレクトリにすでに同じ名前が登録されているときだけです。
3つのdirlinkのうち2つは、新しく作成されたディレクトリに対して”.”と”..”を作成する処理であり、上記の理由から失敗しようがないはずです。
また3つめのdirlinkは、新しく作成したディレクトリ、もしくはファイルを親ディレクトリに登録するためのものですが、すでに親ディレクトリに同じ名前が登録されている場合は、前半のif((ip = dirlookup(dp, name, &off)) != 0)の部分によって除外されるので、3つめのdirlinkは失敗しないことになります。
当然、一連の処理中はdp（親ディレクトリのinode）がロックされているので、途中で他のプロセスで変更されることを考慮する必要もありません。

sysfile.cのcreate関数

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
static struct inode*
create(char *path, short type, short major, short minor)
{
  uint off;
  struct inode *ip, *dp;
  char name[DIRSIZ];
 
  if((dp = nameiparent(path, name)) == 0)
    return 0;
  ilock(dp);
 
  if((ip = dirlookup(dp, name, &off)) != 0){
    iunlockput(dp);
    ilock(ip);
    if(type == T_FILE && ip->type == T_FILE)
      return ip;
    iunlockput(ip);
    return 0;
  }
 
  if((ip = ialloc(dp->dev, type)) == 0)
    panic("create: ialloc");
 
  ilock(ip);
  ip->major = major;
  ip->minor = minor;
  ip->nlink = 1;
  iupdate(ip);
 
  if(type == T_DIR){  // Create . and .. entries.
    dp->nlink++;  // for ".."
    iupdate(dp);
    // No ip->nlink++ for ".": avoid cyclic ref count.
    if(dirlink(ip, ".", ip->inum) < 0 || dirlink(ip, "..", dp->inum) < 0)
      panic("create dots");
  }
 
  if(dirlink(dp, name, ip->inum) < 0)
    panic("create: dirlink");
 
  iunlockput(dp);
 
  return ip;
}

7. について

本文でははiput(cp->cwd)となってますが、ソースではiput(proc->cwd)となっています。
また、ソースではiputでiunlockは呼ばれません。
ソースのログを辿ったところ、この課題は今のソースではなく古いソースに対するもののようです。
古いソースでは、iputはロック中のinodeを要求するようになってました。（現在は未ロックのinodeを要求する。）
iputだけでなく関連の関数の実装も今と大きく違うみたいなので、この課題はパスします。

sysfile.cのsys_chdir関数

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
int
sys_chdir(void)
{
  char *path;
  struct inode *ip;
 
  if(argstr(0, &path) < 0 || (ip = namei(path)) == 0)
    return -1;
  ilock(ip);
  if(ip->type != T_DIR){
    iunlockput(ip);
    return -1;
  }
  iunlock(ip);
  iput(proc->cwd);
  proc->cwd = ip;
  return 0;
}

感想

今までのExercisesの回の中では一番まともに対応できたんじゃないかと思います。
まぁ思い込みで嘘書いてる可能性も大ですが…

一応今回で本文は終わりです。
長いようで短かったです。
興味深く読めたので、ここまで続けれたんだと思います。

あとは、付録A, Bが残ってますのでぼちぼちそちらも読んでいきたいと思います。

コメント

こんにちは。
オフライン端末や印刷したものを読みたいので、これらのページをPDFで配布して欲しいです。

コメントありがとうございます。

PDF化しました。
こちらからzipで一括ダウンロードできます。
フォーマット等気に入らなければ勝手にPDF化していただいて構いません。
その他の注意点はこちら。

いきなり不躾な要望ですみませんでした。
それにも関わらず、心良く応じてくださりありがとうございます。
「英語のドキュメントばかりだと、時間がある時に本腰を入れて
読まないといけないな…(→結局読まない)」という方は私だけではなく、
たくさんいらっしゃると思います。
xv6の学習の間口を広げていただき、ありがとうございます。
早速読ませていただきます！

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です



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

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