技術

[xv6 #64] Chapter 5 – File system – Code: directory layer

テキストの71〜73ページ

本文

ディレクトリの層はシンプルである。
なぜならディレクトリは、今まで以上に特殊な種類のファイル、ではないからである。
ディレクトリのinodeはT_DIRというタイプを持ち、そのデータはディレクトリエントリの連なりである。
各エントリは、dirent構造体であり、名前とinode番号を含む。
名前は、最大でDIRSIZ(14)文字までであり、もしそれに満たなかったら、NUL(0)で終端される。
inode番号ゼロのディレクトリエントリは、空きを示す。

fs.h

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
48
49
50
// On-disk file system format.
// Both the kernel and user programs use this header file.
 
// Block 0 is unused.  Block 1 is super block.
// Inodes start at block 2.
 
#define ROOTINO 1  // root i-number
#define BSIZE 512  // block size
 
// File system super block
struct superblock {
  uint size;         // Size of file system image (blocks)
  uint nblocks;      // Number of data blocks
  uint ninodes;      // Number of inodes.
  uint nlog;         // Number of log blocks
};
 
#define NDIRECT 12
#define NINDIRECT (BSIZE / sizeof(uint))
#define MAXFILE (NDIRECT + NINDIRECT)
 
// On-disk inode structure
struct dinode {
  short type;           // File type
  short major;          // Major device number (T_DEV only)
  short minor;          // Minor device number (T_DEV only)
  short nlink;          // Number of links to inode in file system
  uint size;            // Size of file (bytes)
  uint addrs[NDIRECT+1];   // Data block addresses
};
 
// Inodes per block.
#define IPB           (BSIZE / sizeof(struct dinode))
 
// Block containing inode i
#define IBLOCK(i)     ((i) / IPB + 2)
 
// Bitmap bits per block
#define BPB           (BSIZE*8)
 
// Block containing bit for block b
#define BBLOCK(b, ninodes) (b/BPB + (ninodes)/IPB + 3)
 
// Directory is a file containing a sequence of dirent structures.
#define DIRSIZ 14
 
struct dirent {
  ushort inum;
  char name[DIRSIZ];
};

dirlookup関数は、引数で渡された名前に合致するディレクトリエントリをディレクトリの中から探す。
ディレクトリエントリが見つかった場合、それに対応するinodeのポインタ(ロックされていない)を返し、そして、呼び出し側がその見つかったディレクトリエントリを編集したい場合に備えて、*poffにそのディレクトリエントリのオフセットを格納する。
dirlookup関数が名前に対応するディレクトリエントリを見つけた場合、*poffを更新し、そのブロックを解放し、そしてiget関数から取得したロックされていないinodeを返す。(ここ、一つ前の文と内容が被ってる上に、ブロックを解放とか、ソースと一致してない部分があるため、もしかしたら昔のソースに対する説明の消し忘れかもしれない。)
iget関数は、ロックされていないinodeを返すということがその理由である。
呼び出し側がロック済みのdpを持っていて、カレントディレクトリの別名である「.」に対してdirlookup関数を使った場合、呼び出し元に戻るまえにそのinodeをロックしようとして、つまりdpを再度ロックしようとしてデッドロックを引き起こす可能性がある。(複数のプロセスや親ディレクトリの別名「..」がからんでデッドロックを引き起こすようなもっと複雑な場合もたくさんある。問題が起きるのは「.」のときだけではないのである。)
呼び出し側は、dpをアンロックしそしてそれからipをロックすることで、一度に一つのロックだけを保持する事を保証出来る。
(と、説明されてますが、dirlookupのコードパスを追ってみたところ、inode単位でロックを取得してるところ(ilock関数を呼んでるところ)は見当たりませんでした。何なんでしょうコレ。)

fs.cのnamecmp, dirlookup, dirlink関数

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// Directories
 
int
namecmp(const char *s, const char *t)
{
  return strncmp(s, t, DIRSIZ);
}
 
// Look for a directory entry in a directory.
// If found, set *poff to byte offset of entry.
// Caller must have already locked dp.
struct inode*
dirlookup(struct inode *dp, char *name, uint *poff)
{
  uint off, inum;
  struct dirent de;
 
  if(dp->type != T_DIR)
    panic("dirlookup not DIR");
 
  for(off = 0; off < dp->size; off += sizeof(de)){
    if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de))
      panic("dirlink read");
    if(de.inum == 0)
      continue;
    if(namecmp(name, de.name) == 0){
      // entry matches path element
      if(poff)
        *poff = off;
      inum = de.inum;
      return iget(dp->dev, inum);
    }
  }
 
  return 0;
}
 
// Write a new directory entry (name, inum) into the directory dp.
int
dirlink(struct inode *dp, char *name, uint inum)
{
  int off;
  struct dirent de;
  struct inode *ip;
 
  // Check that name is not present.
  if((ip = dirlookup(dp, name, 0)) != 0){
    iput(ip);
    return -1;
  }
 
  // Look for an empty dirent.
  for(off = 0; off < dp->size; off += sizeof(de)){
    if(readi(dp, (char*)&de, off, sizeof(de)) != sizeof(de))
      panic("dirlink read");
    if(de.inum == 0)
      break;
  }
 
  strncpy(de.name, name, DIRSIZ);
  de.inum = inum;
  if(writei(dp, (char*)&de, off, sizeof(de)) != sizeof(de))
    panic("dirlink");
   
  return 0;
}

dirlink関数は、引数で与えられた名前とinode番号を元に、新しいディレクトリエントリをディレクトリdpに書き込む。
もし名前が既に存在した場合、dirlink関数はエラーを返す。
メインのループでは、未割り当てのエントリを探すためにディレクトリエントリ群を走査する。
未割り当てのエントリが見つかれば、ループを終了する。
その時のoffにはそのエントリのオフセットが格納されている。
未割り当てのエントリが見つからない場合、offにdp->sizeが格納された状態でループを終える。
どちらにしろ、dirlink関数はそれからオフセットoffに書き込むことで新しいエントリをディレクトリに追加する。

感想

ディレクトリの実装についてです。
inodeはすでに自身の種類を表すビットを持つことが出来るようになってるので、inodeの層から見るとすでに「ディレクトリレディ」な状態と言えます。

そして、通常のファイルの場合はデータ部分に単にその内容を持つわけですが、ディレクトリの場合はファイル名とそれに対応するファイルのinodeをデータとして持つわけです。

本文にも括弧付きで書きましたが、ちょっとソースと合致してない部分が見受けられます。
「ブロックの解放」については、昔のソースをみたら確かにブロックを確保して、最後にbrelseを呼ぶようになってる時期があったのは確認しました。
デッドロックの方については、昔のソースをざっと見ただけだとまだ該当するようなところは見つけてないので、もしかしたら、あの説明が合ってて、私の認識が間違ってる可能性もおおいにあります。

コメントを残す

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



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

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