ファイルシステムを自作しています.

どうも,最近Blog書こうという気持ちは高まっていてネタ帳は増えてるけど書いてなかったんでいい加減書こうと思って書きます.
筑波大学の情報学群情報科学類では,3年次に主専攻実験というものがあり,これは情報科学類に存在する3つの専攻に所属し,各専攻が開設する実験を履修するというものです. それで,履修する実験は決められたルールのもとで自由に選ぶことができることになっています. そこで自分は,春学期は「カーネルハック」を履修しています(面白いことに,今年は自分1人だけが履修しています.)

そこの課題の一つに,ファイルシステムを実装するというものがあり,初めにFUSEを用いたファイルシステムの実装を行っています. 半分趣味みたいな形で実験ができることは本当によくて家でも楽しく実装をしています.

実装や設計については続きからどうぞ.

はじめに

コードは次のRepositoryにて公開しています: KFS また,現在このファイルシステムFUSEを用いてユーザー空間で動作します. 動作の確認は,Linux上でのlibfuseとOSXFUSEで確認しました.

また,現時点で次に示すオペレーションが実装してあります.

  • getatt
  • readdir
  • open
  • read
  • write
  • mkdir
  • access
  • create
  • utimens
  • unlink
  • chmod
  • truncate

また,

  • chown

なども実装する予定です. また,現在パーミッションのチェックは実装中です.(思いの外難航しており,readdir, read, write, openにしか対応できていません.)

設計について

初めに,このファイルシステム(KFS)はすべてのノード(エントリと呼んでいます)が以下に示すKFS_Entryという構造体になっています. また,現在は物理的なディスクには書き込んでおらず,すべてメモリ上にデータを保存しています.(これを私はインメモリなファイルシステム,と呼んでいます.)

typedef struct KFS_Entry {
  sds name; // ファイル名(ディレクトリ名)が入る
  int entry_type; // 次のunion が KFS_Dir or KFS_File のどちらかを示す

  union {
    KFS_Dir *dentry; // このエントリがディレクトリを表す場合に後述するKFS_Dirがはいる
    KFS_File *fentry; // 同様にファイルの場合はKFS_Fileがここにはいる
  };

  mode_t mode; // ファイルのパーミッション RWXなどの情報が入る
  off_t size; // ファイルサイズ
  nlink_t nlink; // このエントリに対するハードリンクの数
  struct KFS_Entry *prev; // 親エントリ
  struct timespec atime; // タイムスタンプ
  struct timespec mtime; // タイムスタンプ
  uid_t uid; // このファイルの所有者
  gid_t gid; // このファイルのグループ
} KFS_Entry;

この様になっています.

そして,ファイルを表す構造体KFS_Fileについては次のような簡単な定義となっています.

typedef struct {
  char *data; // ファイル本体のバイト列
} KFS_File;

データを書き込む際にはこのdataにメモリを確保してから書き込み,読み込むときはこれを読み取ります.

また,ディレクトリはつぎのような定義になっています.

typedef struct {
  AVLTree *childs;
} KFS_Dir;

childsというAVL木になっていて,このAVL木はキーとしてエントリ名をとり,それに対応する値としてエントリ(KSF_Entry)を持ちます.

つまり,以下のようになります.

/ <root, KFS_Dir, AVLTree>
  /hoge <KFS_Dir, AVLTree>
    /foo <KFS_File, char*>
  /bar <KFS_Dir, AVLTree>
  /baz <KFS_Dir, AVLTree>

つまり,すべてのディレクトリは一つずつAVL木を持ち,そのディレクトリの要素を格納します. よって,/A/B/Cというパスが与えられた場合AのAVL木からBを探索BのAVL木からCを探索Cという形で探索することになります.

これがKFSでのファイルとディレクトリの表現方法となります.

オペレーションの実装

FUSEシステムコールに対応する処理をユーザー空間で実装し,それをfuse_operationsという構造体のメンバに関数ポインタとして格納することで,そのメンバが 適切にVFS*1のインターフェースに接続されます.

つまり,次のような形となります.(概念図なので正確ではありません)

[File System(Kernel Land)] <------- VFS -------> OS(システムコールが発行される)
これが次のようになります.
[FUSE(Kernel Land)]          <------- VFS -------> OS
           |
           |----------[User空間から渡されたハンドラが呼ばれる]

fuse_operationsには,具体的に次のようなオペレーションに対応する処理を行う関数ポインタを設定します.

  • getatt
  • readdir
  • open
  • read
  • write
  • mkdir
  • access
  • create
  • utimens
  • unlink
  • chmod
  • truncate
  • chown

それぞれインターフェースが決まっているので,そのインターフェースに従って実装します.

例としてreadに対応するインターフェースの実装を示します.(詳細はGitHubのコードを見てください)

int itf_fuse_kfs_read(const char *path, char *buf, size_t size, off_t offset,
                      struct fuse_file_info *fi) {
  (void)fi;
  // パスが読み取り可能かを調べ,Not found or 読み取り不可能な場合エラーを返すマクロ
  CheckEntryReadPermission(path);

  int res = 0;
  sds spath = sdsnew(path); // char*を扱いやすいsdsに変換
  // KFS_ROOTは "/" つまりファイルシステムのルート.
  KFS_Entry *entry = kfs_find(KFS_ROOT, spath); // ファイルシステムにパスが存在するかを調べる

  if (entry == NULL) {
    // 上のマクロが検査しているのでここが呼ばれることはないが
    // ファイルシステム上にエントリが存在しない場合はこれが返り値となる.
    res = -ENOENT;
  } else {
    SizedData *sdata = kfs_read(entry);
    size_t len = sdata->size;

    if (offset < (off_t)len) {
      if (offset + size > len) {
        size = len - offset;
      }
      memcpy(buf, sdata->data, size);
      res = size;
    } else {
      res = 0;
    }
  }

  sdsfree(spath);
  return res;
}

このような感じでインターフェースを満たしながらオペレーションを実装していきます.

また,AVL木を多段に構成することでKFSは階層構造を表現しているのですが,それを探索(検索,つまり上のコードでのkfs_find)するコードを参考までに示します.

// ディレクトリの中から実際にnameに対応するエントリがあるかを探す.
// 下の階層(つまりディレクトリ)は遡らない
KFS_Entry *kfs_find_on(KFS_Entry *this, sds name) {
  assert_is_dir(this); // thisがディレクトリであることをチェックする.
  return avl_find(GetAVLTree(this), name, path_cmp);
}

// thisの中からpathに対応するエントリを検索する
KFS_Entry *kfs_find(KFS_Entry *this, sds path) {
  assert_is_dir(this);
  sds slash = sdsnew("/");

  // もしthisがroot(/)でpathが/の場合はthisを返す
  if (sdscmp(path, slash) == 0) {
    if (sdscmp(this->name, slash) == 0) {
      return this;
    } else {
      return NULL;
    }
  }

  // 先頭の '/' をとる.
  if (sdslen(path) > 1 && path[0] == '/') {
    sdsrange(path, 1, -1);
  }

  //パスをスラッシュ区切りにする.
  Vector *paths = sdssplitvec(path, '/');
  KFS_Entry *tentry = this; // 探索対象のエントリ(ディレクトリが入る)

  // パス区切りで階層を掘り下げていく
  for (size_t i = 0; i < paths->len; i++) {
    // 検索対象のディレクトリ
    sds tpath = paths->data[i];
    // 検索対象が前回のループで見つからなかった場合,なかったことになるのでNULLを返す
    if (tentry == NULL) {
      return NULL;
    }

    // pathの終端の場合,探すのをここでうちきる.
    if (i + 1 == paths->len) {
      if (tentry->entry_type == tKFS_File) { // ファイルの場合
        // tpathとtentry->nameが一致している場合,これが求めていたpath
        // に対応するエントリなのでこれを返す
        if (sdscmp(tpath, tentry->name) == 0) {
          return tentry;
        } else {
          // 違った場合,これ以上掘り下げれないのでNULL
          return NULL;
        }
      } else {
        // ディレクトリの場合は検索する
        return kfs_find_on(tentry, tpath);
      }
    } else {
      // 途中にあったのがファイルの場合,目的のものはない(それ以上掘れないため)のでNULLを返す
      if (tentry->entry_type == tKFS_File) {
        return NULL;
      } else {
        // 1階層潜った結果をtentryに入れて掘り進む
        tentry = kfs_find_on(tentry, tpath);
      }
    }
  }

  sdsfree(slash);
  return NULL;
}

このようにして検索を行っています.

デバッグ方法について

また,FUSEの場合ユーザーランドで動作するのでデバッグが簡単にできます. そこで,デバッグの際に具体的にどのようにすると良いかについて簡単に書きます.

フォアグラウンドで動かしてデバッガにかける

FUSEfuse_mainという関数(実際はマクロですが)を呼び出すことでファイルシステムをマウントします. これは, fuse_main(argc, argv, op, user_data)という形になっていて,main関数が受け取ったargcargv(つまりコマンドライン引数)が渡ります. よって,コマンドライン引数で動作を指定できます. ここで,-fオプションを付けるとフォアグラウンドで動作するのでデバッグ用の出力などを見ることができます.(fflush(stdout)などのようにしてflushしないとかかれないことがあるのでそれは注意です) また,ユーザー空間で動作しているので簡単にデバッガを接続できます. 具体的にKFSの開発では次のようにしてデバッガを起動しています.

$ lldb -d ./generated/kfs
(lldb) target create "./generated/kfs"
Current executable set to './generated/kfs' (x86_64).
(lldb) r -f kfsdir/

このようにして起動することでkfsdirをKFSのルートとしてマウントし,-fによりフォアグラウンドで動作します.ここでC-cなどとするとファイルシステムの動作を止めたりできますし,breakpointを打つこともできます.(LLDBなのは,単に自分がLLDBしか使えないためです)

このようにしてデバッガを使うと効率的にデバッグができます.(カーネルランドの場合うかつに変な事をしてしまうとなかなかデバッグするのが大変なので,それと比較すると,すごく簡単にデバッガを使用できます)

straceでみる

また,プログラムがSEGVしたりした場合はデバッガで具体的なメモリ違反の箇所を特定できますが,プログラムがハングしない場合はどこでおかしくなったかの特定が面倒です. FUSEの場合,あるシステムコールが呼ばれると,それに対応するハンドラ(オペレーション)が呼ばれるため,期待していた戻り値と異なるシステムコールを探せば自動的にどこが実装上まずいかがわかります. ここでstraceを使ってファイルシステム上で操作することでおかしなオペレーションが特定できます.

具体的には

$ strace echo ABC > x

として,writeシステムコールがおかしい,となっていれば,fuse_operationswriteに渡したハンドラがおかしいことがわかりますし,ENOSYSが返っていれば対応するオペレーションが未実装(つまり,ハンドラが設定されていない)ことがわかります.

実装する過程で気がついたこと

最後に,実装する過程で気がついたこととしていくつか書きます.

1つめから3つめは感想みたいなものなので別に説明する必要は無いと思いますが,4については少しだけハマって面白かったので,それについて書きます.

ファイルシステムを作ったので,その上でCのコードを書き,コンパイルし,生成されたバイナリファイルを実行してみたくなるのはおおよそ自然な流れだと思うのですが,Linux上ではそれが失敗しました. つまり,gcc -o test test.cなどとして適当なCプログラムをコンパイルして,生成された実行バイナリを実行しようとしても不正なバイナリが出力されており,実行ができませんでした.

原因をいろいろな方法(デバッガとstraceを眺めたり生成されるELFをreadelfで睨んだ結果)で調べた結果,アセンブラ(GAS)が(少なくとも自分の)想定とは異なる挙動をしていたため,アセンブルに失敗していたことがわかりました.

これを説明するためにバグっていた時のKFSのまずい実装を示します. 具体的には,ファイルにデータを書き込む処理の実装に問題がありました.その実装を以下に示します.

void kfs_write(KFS_Entry *this, const char *buf, long int size,
               long int offset) {
  assert_is_file(this);

  KFS_File *file = GetKFSFile(this);

  if (file->data != NULL && offset == 0) {
    xfree(&file->data);
  }

  if (offset) {
    if (this->size < offset + size) {
      size_t append_size = (offset + size) - this->size;
      file->data = realloc(file->data, this->size + append_size);
      this->size += append_size;
    }
  } else {
    file->data = xmalloc(size);
    this->size = size;
  }
  memcpy(file->data + offset, buf, size);
}

実際にまずいのは,主にこの部分です.

  if (file->data != NULL && offset == 0) {
    xfree(&file->data);
  }

これは,「writeする際に,オフセットが0なときに,ファイルがデータをもっている場合にファイルを空にする」という処理です. なぜこうしたのかと言うと,自分は

FILE *fp = fopen("some_exists_file", "w");

とした時に,ファイルにはデータがあるが中身が消去する必要がある,と考えこの様に実装しました. 実際はこれは誤りで,このようなコードを書くと

openat(AT_FDCWD, "some_exists_file", O_WRONLY|O_CREAT|O_TRUNC, 0666) = 3

というようなシステムコールが発行され,O_TRUNCによるtruncate some_exists_file --size 0としたのと同じ様にファイルサイズが0にされる処理が行われます. つまり,writeではファイルサイズを切り詰めてはいけません.(それはopenのような別のシステムコールが行う処理であるため) そのような誤解から上で示したようなコードを書いてしまいました.

で,なぜこれがまずいのかと言うと,次のような場合にファイルがこわれます.

  1. offset > 0 で書き込みを行う
  2. offset > 0 で書き込みを行う
  3. offset = 0 で先頭から書き込みを行う

というような流れで処理が行われた場合,つまり最初にファイルの途中を書いて,最後にマジックナンバーなどファイルの先頭に配置したいデータを書き込むような処理が 行われると,上の実装ではこれまでに書いた内容を破棄してしまいます.その結果,1, 2で書いていた内容が失われてしまうというバグが発生します.

前置きが長くなりましたがこのようなバグがありました.

それで,このバグによりGCCでCファイルをコンパイルしようとした際に,具体的にはアセンブルする際に,まさに先程示したように最後にoffset = 0とした書き込みが行われたために生成されたバイナリがこわれました. つまり,GCCアセンブラ(GAS)は次のような動作をしていました.

  1. ELFのセクションヘッダやシンボルテーブルなどをoffset > 0として書く.
  2. 最後にoffset = 0としてマジックナンバーなどを先頭に書く

これにより,2で1で書いた情報が消えてしまっていたというわけです. ちなみに,リンカはこわれたオブジェクトファイルをヘッダがELFなので,普通にELFだと解釈してエラーを吐かずにこわれたバイナリを出力しました. そのため最初はリンカがうまくリンクできてないのでは?と疑いましたがアセンブルした結果がこわれていたのでアセンブルする際にバイナリがこわれたことが特定できました.

なお,OSXFUSEを用いてmacOS上のclang(llvm-as)はファイルを先頭から書いていくようで先程のバグった実装でも動作しました.

まとめ

ファイルシステムを自作するのはとても楽しいし勉強になります. 将来的には,時間のある時に,好きなプログラミング言語処理と,ファイルシステム実装で学んだ知識を活かしデータベースエンジンを作ってみたいなあとぼんやり思っています. 取り敢えず,まだ細かい部分で完成していないのでちまちま実装していきたいなあと思います. また,来週からカーネルランドへの移植も行っていきたいと思います.

以下にファイルシステムを作っている途中のツイートを掲載します

  • 初めにCだと辛くなってDで実装したときの様子.(これを実装したあとに本格的にCで書き直したので更新していませんが,このとき作ったコードはこちら: kfsd)

  • 動いてきている時の図(まだread/writeはできてなさそう)

  • read/writeができるようになった時の図

  • Linux & KFS上でGCCを用いてCファイルをコンパイルし実行しようとしたけど,なんかダメで原因がわかってなかった時の図

*1:ファイルシステムのインターフェース,これを満たすように実装することでExt4やBtrfsが統一的に扱える