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

日曜研究室

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

技術

[xv6 #63] Chapter 5 – File system – Code: Inode contents

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

テキストの71〜73ページ

本文

ディスク上のinodeの構造を表すdinode構造体は、サイズとブロック番号の配列を含んでいる（図5-4参照）。
inodeのデータは、dinode構造体のaddrs配列に記録されているブロック群から見つける事ができる。
データの最初のNDIRECT個のブロックは、そのaddrs配列の最初のNDIRECT個のエントリに記録されている。
そのようなブロック群はダイレクトブロック（direct blocks）と呼ばれる。
データの次のNINDIRECT個のブロックは、そのinodeには直接記録されておらず、データブロックにある。
そのようなデータブロックはインダイレクトブロック（indirect block）と呼ばれる。
addrs配列の最後のエントリは、インダイレクトブロックのアドレス用である。
上で述べたように、ファイルの最初の6kB（NDIRECT * BSIZE）分は、inodeにリストアップされているブロック群から読み込むことが出来るが、次の64kB（NINDIRECT * BSIZE）分は、インダイレクトブロックを読み込んだ後にしか読み込むことは出来ない。
これはディスク上での良い表現法だが、この構造を利用するコードにとっては複雑である。
bmap関数は、readi関数やwritei関数（すぐ後で見ることになるだろう）などのより高い層のルーチンのために、この構造を管理する。
bmap関数は、inodeであるipを受け取り、そのinodeのbn番目のデータブロックのブロック番号を返す。
もしipがそのようなブロックをまだ持っていない場合は、bmap関数がそれを割り当てる。


図5-4 ディスク上におけるファイルの表現

fs.cのbmap関数

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
// Inode contents
//
// The contents (data) associated with each inode is stored
// in a sequence of blocks on the disk.  The first NDIRECT blocks
// are listed in ip->addrs[].  The next NINDIRECT blocks are
// listed in the block ip->addrs[NDIRECT].
 
// Return the disk block address of the nth block in inode ip.
// If there is no such block, bmap allocates one.
static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a;
  struct buf *bp;
 
  if(bn < NDIRECT){
    if((addr = ip->addrs[bn]) == 0)
      ip->addrs[bn] = addr = balloc(ip->dev);
    return addr;
  }
  bn -= NDIRECT;
 
  if(bn < NINDIRECT){
    // Load indirect block, allocating if necessary.
    if((addr = ip->addrs[NDIRECT]) == 0)
      ip->addrs[NDIRECT] = addr = balloc(ip->dev);
    bp = bread(ip->dev, addr);
    a = (uint*)bp->data;
    if((addr = a[bn]) == 0){
      a[bn] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    return addr;
  }
 
  panic("bmap: out of range");
}

bmap関数は、簡単な仕事から始める。
最初のNDIRECT個のブロックは、inodeそれ自身にリストアップされている。
次のNINDIRECT個のブロックは、ip->addrs[NDIRECT]で示されるインダイレクトブロックにリストアップされている。
bmap関数は、そのインダイレクトブロックを読み込み、そしてそのインダイレクトブロックの中の正しい位置からブロック番号を読み出す。
もしそのブロック番号が、NDIRECT + NINDIRECTを越えている場合、bmap関数はpanic関数を呼ぶ。
呼び出し側は、範囲外のブロック番号について問い合わせないようにする責任がある。

bmap関数は、必要に応じてブロックを割り当てる。
未割り当てのブロックは、ブロック番号0として示される。
よってbmap関数は0に遭遇したら、必要に応じて割り当てられた新しいブロックの番号でそれを置き換える。

bmap関数は、そのinodeが成長するときに必要に応じてブロックを割り当てる。
itrunc関数は、それらを解放し、inodeのサイズを0にリセットする。
itrunc関数は、ダイレクトブロックを解放することから初め、そしてそれからインダイレクトブロックの内容を解放し、そして最後にインダイレクトブロックそのものを解放する。

fs.cのitrunc関数

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
// Truncate inode (discard contents).
// Only called after the last dirent referring
// to this inode has been erased on disk.
static void
itrunc(struct inode *ip)
{
  int i, j;
  struct buf *bp;
  uint *a;
 
  for(i = 0; i < NDIRECT; i++){
    if(ip->addrs[i]){
      bfree(ip->dev, ip->addrs[i]);
      ip->addrs[i] = 0;
    }
  }
   
  if(ip->addrs[NDIRECT]){
    bp = bread(ip->dev, ip->addrs[NDIRECT]);
    a = (uint*)bp->data;
    for(j = 0; j < NINDIRECT; j++){
      if(a[j])
        bfree(ip->dev, a[j]);
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT]);
    ip->addrs[NDIRECT] = 0;
  }
 
  ip->size = 0;
  iupdate(ip);
}

bmap関数は、readi関数やwritei関数のような、inodeのデータストリームへアクセスする関数を書きやすくする。
readi関数は、inodeからデータを読み込む。
readi関数は、指定されたオフセットとカウントが、ファイルの終わりを超えないかどうかチェックする事から始める。
ファイルの終わりを超えたところから始まるような読み込みにはエラーを返す。
ファイルの終わりまたはファイルの終わりをまたぐような指示があった場合は、指定されたよりも少ないデータを返す。
メインのループは、ファイルの各ブロックを処理し、バッファからデータをdstに格納する。
writei関数は、3つの例外を除いてreadi関数ととてもよく似ている。
ファイルの終わりから、もしくはファイルの終をまたぐような書き込みは、ファイルの最大サイズを上限としてファイルを大きくする。
メインのループでは、データをバッファから取り出すのではなく、バッファに格納する。
そして、書き込みがファイルを拡張した場合、writei関数はそのサイズを更新しなければならない。

fs.cのreadi, writei関数

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
// Read data from inode.
int
readi(struct inode *ip, char *dst, uint off, uint n)
{
  uint tot, m;
  struct buf *bp;
 
  if(ip->type == T_DEV){
    if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read)
      return -1;
    return devsw[ip->major].read(ip, dst, n);
  }
 
  if(off > ip->size || off + n < off)
    return -1;
  if(off + n > ip->size)
    n = ip->size - off;
 
  for(tot=0; tot<n; tot+=m, off+=m, dst+=m){
    bp = bread(ip->dev, bmap(ip, off/BSIZE));
    m = min(n - tot, BSIZE - off%BSIZE);
    memmove(dst, bp->data + off%BSIZE, m);
    brelse(bp);
  }
  return n;
}
 
// PAGEBREAK!
// Write data to inode.
int
writei(struct inode *ip, char *src, uint off, uint n)
{
  uint tot, m;
  struct buf *bp;
 
  if(ip->type == T_DEV){
    if(ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].write)
      return -1;
    return devsw[ip->major].write(ip, src, n);
  }
 
  if(off > ip->size || off + n < off)
    return -1;
  if(off + n > MAXFILE*BSIZE)
    return -1;
 
  for(tot=0; tot<n; tot+=m, off+=m, src+=m){
    bp = bread(ip->dev, bmap(ip, off/BSIZE));
    m = min(n - tot, BSIZE - off%BSIZE);
    memmove(bp->data + off%BSIZE, src, m);
    log_write(bp);
    brelse(bp);
  }
 
  if(n > 0 && off > ip->size){
    ip->size = off;
    iupdate(ip);
  }
  return n;
}

readi関数とwritei関数の両方共、ip->type == T_DEVのチェックから始める。
これは、ファイルシステム上にデータがない、特殊なデバイスを制御するためにある。
その場合については、ファイルディスクリプタの層の節で説明するだろう。

stati関数は、inodeのメタデータをstat構造体にコピーする。
この構造体は、statシステムコール経由でユーザプログラムにそのまま提供される。

fs.cのstati関数

01
02
03
04
05
06
07
08
09
10
// Copy stat information from inode.
void
stati(struct inode *ip, struct stat *st)
{
  st->dev = ip->dev;
  st->ino = ip->inum;
  st->type = ip->type;
  st->nlink = ip->nlink;
  st->size = ip->size;
}

感想

ファイルがディスク上でどのように表現されているかと、その周辺の（といってもどれも必要不可欠）関数についての説明です。

bmapの実装からして1ファイル70kB（NDIRECT * BSIZE + NINDIRECT * BSIZE）まででしょうか。
writeiを見ても、MAXFILE * BSIZEまでとなっていて、MAXFILEはNDIRECT + NINDIRECTと定義されてるので多分そうでしょう。
これを拡張するには、インダイレクトブロックでもダイレクトブロックのように、addrs配列の最後に次のインダイレクトブロックのブロック番号を含めるようにすればいいのかな。

コメントを残す

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



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

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