読者です 読者をやめる 読者になる 読者になる

by shigemk2

当面は技術的なことしか書かない

ファイルシステムの話 その1 bmap #ikebin

UNIX

悪魔合体

UNIX V6 40年前 → FreeBSD 10年前 だいたいつながってる

ソースコードをひたすら読む

P282

最近のOSがどういう風になっているのか

V6本 P282

ファイルシステムってなに

ディレクトリとかファイルとかの階層構造を表現するもの

/a.txt
/sub/b.txt

HDDは図にすると円柱みたいなやつ

ディスクは円盤が何枚も重なっているが、そういう物理的な構造はOSからしたらあんまり関係がなく、開発者やユーザーは意識せずに使うことができる

巨大な配列

______
|    |
|    |
|    |
|    |
|    |
|    |
|    |
------

512バイト単位 1バイト単位で任意の場所での読み書きはできない

読み込み
  1. 512バイトごとの単位をセクタといい、セクタのデータをメモリに読み込む
  2. メモリの中からアクセスしたい場所にアクセスする
書き込み
  1. 512バイトごとの単位をセクタといい、セクタのデータをメモリに読み込む
  2. メモリの中からアクセスしたい場所にアクセスして書き換え、ディスクにデータを戻す

都度書き換えしてたら処理速度が爆遅になるのでいっぺんに読んでいっぺんに書くみたいなのをやる。 データを読み書きする場所をバッファとかキャッシュとかいい、すぐには消されない。

バッファでの編集内容をディスクに反映させないとデータの読み書きが反映されないので、うまい塩梅のタイミングで書き戻しがなされる。

仮想記憶

上記のディスクとバッファの関係を実装したもの。V6の時代にはない。FreeBSDよりも前に実装された。

ディスクのなかにファイルシステムがどのように構築されているのか。

ディスクの構造

P262 UNIXにおけるデバイスの構造(V6から連綿と続くアレだが、V6のディスク容量は2MB)

0MB
______
|    | ブートローダー(起動用)
------
|    | スーパーブロック(inodeなどを管理する領域)
------
|    | inode(ファイルひとつひとつについてる背番号のようなものが格納されているが、FATにはついてない)
------
|    | ストレージ領域(データ。ファイルの実体=バイナリなど。)
------
2MB

inodeの情報は構造体として定義されている(P265)

データの共用

i_nlink… ハードリンクを利用して、まったく同じ内容のものを別々のディレクトリに突っ込む

inode領域

inode領域内

------------------
|    ブロック    |
------------------
|    ブロック    |
------------------
|    ブロック    |
------------------

ブロック内

------------------
|      inode     |
------------------
|      inode     |
------------------
|      inode     |
------------------

ストレージ領域

そのファイルのデータが存在するブロックは連続していない = 断片化!!

セクタが512あってinodeは1つのセクタに8つ搭載されてる 直接参照のみだと512x8(だいたい4mb4kbほど) 間接参照は8x256x512(20mbに増える)

二重間接参照

間接参照 アドレス→(ブロック番号のインデックス→データの実体) ストレージ領域 二重間接参照 アドレス→(ブロック番号のインデックス→ブロック番号のインデックス→データの実体) ストレージ領域

ではどうやって上のシステムを実装してるのか

論理ブロック番号 vs 物理ブロック番号

論理ブロック番号 = バイトオフセット / 512 した値

物理ブロック番号 実際のストレージ領域のブロック番号

実装

bmap inodeからファイルのデータをストレージ領域から探す関数(=論理ブロック番号から対応する物理ブロック番号を算出する)

P283

i = バイトオフセット / 512 / 256

/* ip inode
   bn 論理ブロック番号
*/
bmap(ip, bn)
struct  inode *ip;
int bn;
{
    register *bp, *bap, nb;
    int *nbp, d, i;

    d = ip->i_dev;
    /* 論理ブロック番号 エラーチェック */
    /* bn < 0 でも動くはずだが */
    if(bn & ~077777) {
        u.u_error = EFBIG;
        return (0);
    }

    /* 直接参照 と 間接参照 と 二重間接参照を実装する */
    /* 直接参照 */
    if((ip->i_node&ILARG) == 0) {
        /* b > 7 大小の比較をビットでやってる */
        if((bn & ~7) != 0) {
            /* ... */
        }
        /* ... */
        nb = ip->i_addr[bn];
        if(nb == 0 && (bp = alloc(d)) != NULL) {
            bwrite(bp);
            nb = bp->b_blkno;
        }
        /* ... */
        return(nb);             /* 最終的に返される物理ブロック番号 */
    }
};

なんかbdwriteとか書き込みっぽいことをしているのは、もともとストレージに書き込まれていないデータを更新するため。

bp->b_addr アドレスと書き込み先のストレージを保存している。