OS自作入門を勝手に続けてみる - ファイルシステムの開発1

今回の目標

とりあえずファイルとディレクトリを作れるようにしてみる。

どう作るか？

ディスクI/Oがまだ実装できていないため、ファイルの中身とファイル情報は
さしあたってメモリ上に配置することにした。

「ファイルの情報」を表すような構造体をつくり、
そこにファイルのID、名前、種類、内容へのポインタなどを格納していくことにした。

また、各ファイルには親ディレクトリのID、子供のID(のうちの一つ)を持たせ、
ディレクトリをたどれるようにしてみた。同一レベルでのアクセスはどうするか悩んだが、
ファイルに「次のファイル情報」へのポインタを持たせ、ループするリンクリストを作った。

以上を図にすると以下のような形になる。

ファイルの情報を得る

構造体はFILEINFOと名付けることにした。

struct FILEINFO {
  int id, parent, child;
  unsigned char name[16], type;
  unsigned int timestamp;
  unsigned int *addr;
  unsigned int size;
  struct FILEINFO *next
};

名前はとりあえず16文字まで、typeにはファイルの種別、アクセス権を代入する予定。
addrはmemman_allocで確保したファイルの内容へのポインタにする予定である。

メモリ上の位置は 0x00102600 に設定、id順に並べることにしたので、
「あるファイルidを持つFILEINFOを取得する」関数は簡単に書けそうである。

struct FILEINFO* file_getinfo(int id)
{
  struct FILEMAN *fileman = (struct FILEMAN *) FILEMAN_ADDR;
  return (struct FILEINFO*) (fileman->info_top + sizeof(struct FILEINFO) * id);
}

filemanにはFILEINFOの先頭位置(info_top = 0x00102600)や、現在割り当てられているid数の情報を持たせてある。
場所も決めうちで、

#define FILEMAN_ADDR 0x00300000

とした。

指定された名前のファイルを探す

指定されたパスのファイルを探す関数を書いてみた。

// 指定されたパスのファイルを探す
struct FILEINFO* file_search_path(char *name, int current)
{
  int p;
  char s[32];
  struct FILEINFO *dir_file;

  if ((p = strutil_search(name, '/')) == -1) {
    return file_search(name, current);
  } else {
    if (p == 0) {
      dir_file = file_getinfo(0);
    } else {
      strutil_substr(s, name, 0, p);
      dir_file = file_search(s, current);
    }
    if (dir_file != -1) {
      current = dir_file->id;
      p++;
      return file_search_path(name + p, current);
    } else {
      return (struct FILEINFO*) -1;
    }
  }
}

strutil_ で始まる関数は自前で作成したもので、意味はそれぞれ

strutil_search: 文字列の中で指定された文字の位置を返す関数
strutil_searchl: strutil_searchと同じだが文字列の末尾から検索する
strutil_substr: 部分文字列を切り出す。PHP等のsubstrとほぼ同じ

である。

ディレクトリの階層移動を表す文字「/」をパスの中から探し、見つからなければ、現在のディレクトリの中で該当するファイルを探す処理をする。
「/」が見つかったなら、最初の「/」までの文字をstrutil_substrを用いて切り出し、その名前を持ったディレクトリを探す。
見つかれば、現在のディレクトリをそのディレクトリに設定し、最初の「/」以降の文字を新たなパスとして、再度file_search_pathを実行する。

また、file_searchの処理内容は以下のようにした。

// 指定された名前のファイルを探す
struct FILEINFO* file_search(char *name, int current)
{
  struct FILEINFO *current_dir = file_getinfo(current);
  struct FILEINFO *first_child, *child;
	
  if (strlen(name) == 0) {
    return current_dir;
  }
  if (name[0] == '.' && name[1] == '.') {
    return file_getinfo(current_dir->parent);
  }
  if (current_dir->child != FILE_NO_CHILD) {
    first_child = file_getinfo(current_dir->child);
    child = first_child;
    do {
      if (strcmp(child->name, name) == 0) {
        return child;
      }
      child = child->next;
    } while(child != first_child);
  }
  return (struct FILEINFO*) -1;
}

現在のディレクトリのFILEINFOを取得し、そのchildの値を見る。
childの値が FILE_NO_CHILD であった子供はいないと判断し、ファイルは見つからなかったことにする。
そうでなければディレクトリの子供(のひとつ)のFILEINFOを取得する。

そのFILEINFOからnextの値を見ていき、nextが最初に取得した子供のFILEINFOを指すまでループする。
その中で、FILEINFOのnameの値が指定された名前であるものを探している。

ファイルをリンク、アンリンクする

ファイルを作成する関数を作成する前に、
ファイルを特定のディレクトリの中に入れたり(リンク)、ディレクトリから外したり(アンリンク)する関数を書いた。
また、ファイルそのものを削除する(FILEINFOが指し示す先のメモリを開放し、アンリンクを行う)関数も作成した。
処理内容は以下の通り。

// 指定したファイルを消す（ファイルだったらメモリを開放する）
void file_remove(struct FILEINFO *file, char recursive)
{
  struct MEMMAN *memman = (struct MEMMAN *) MEMMAN_ADDR;
  struct FILEINFO *child, *first;
  if (!FILE_IS_DIRECTORY(file)) {
    memman_free_4k(memman, (int) file->addr, file->size);
  } else if (file->child != FILE_NO_CHILD && recursive){
    first = child = file_getinfo(file->child);
    do {
      file_remove(child, recursive);
      child = child->next;
    } while(first != child);
  }
  file_unlink(file);
}

// 指定したファイルのリンクを解除する（中身・確保したメモリは消さない）
void file_unlink(struct FILEINFO *file)
{
  struct FILEINFO *parent, *brother;
  brother = file->next;
  parent = file_getinfo(file->parent);
  if (file == brother) {
    parent->child = FILE_NO_CHILD;
  } else {
    while( brother->next != file ) {
      brother = brother->next;
    }
    brother->next = file->next;
    parent->child = file->next;
  }
}

// 指定したファイルを特定の場所にリンクする
void file_link(struct FILEINFO *file, struct FILEINFO *directory)
{
  struct FILEINFO *brother, *sister;
  if (directory->child == FILE_NO_CHILD) {
    // 子供がいないなら、自分で自分を指してループを作る
    file->next = file;
    directory->child = file->id;
  } else {
    // 子供がいる場合は、間に挿入する
    brother = file_getinfo(directory->child);
    sister = brother->next;
    file->next = sister;
    brother->next = file;
  }
}

file_removeはファイルの削除を行う。
fileがディレクトリならばメモリの確保は行っていないため後述のunlinkのみ行う。
また、recursiveにtrueが指定されていたときは、fileの子供についても同様の処理を行う。

file_unlinkではfileを自身のparentの子供から外す処理を行っている。
unlinkによって子どもがなくなってしまう場合はchildにFILE_NO_CHILDを代入する。

file_linkでは、directoryの子ファイルとしてfileを登録する。
directoryの子どもがいないならfileのnextは自分自身を指すようにし、
子どもがいる場合は間に挿入するようにしてある。

ファイルを作成する

そして、上記関数を用いてファイルシステムにファイルを追加する関数を書いてみた。
これは後ほどのコマンド「mkfile」「mkdir」で使用する予定である。

// 指定した場所へデータを書き込む。
struct FILEINFO* file_write(char *name, char *data, int parent, int fid, char is_directory)
{
  struct FILEMAN *fileman = (struct FILEMAN *) FILEMAN_ADDR;
  struct MEMMAN *memman = (struct MEMMAN *) MEMMAN_ADDR;
  int id = fid;
  struct FILEINFO *info;
  struct FILEINFO *parent_info;
  
  // ファイルがnameであるものを探す。見つからなかったら新しく作成する
  // 見つかればそのファイルをいったん削除し、同じidにファイルを作成する
  info = file_search_path(name,  parent);
  if (info == -1) {
    id = fileman->allocated_id++;
    info = file_getinfo(id);
  } else {
    id = info->id;
    file_remove(info, 0);
  }
  if (!is_directory) {
    int *to = memman_alloc_4k(memman, strlen(data));
    int i = 0, size = strlen(data);
    // データのコピー
    for (i = 0 ; i < size ; i++) {
      to[i] = data[i];
    }
    info->addr = to;
    info->size = size;
  }

  // FILEINFOに書き込む
  strncpy(info->name, name, FILE_MAX_NAME);
  info->id = id;
  info->parent = parent;
  info->type = file_generate_type(is_directory, 1, 1);
  info->child = FILE_NO_CHILD;
  
  // 親のデータを取得してリンク作成
  parent_info = file_getinfo(parent);
  file_link(info, parent_info);
  
  return info;
}

まとめ

長くなってしまったので今回はここまで。
次回はこれらの関数を用いて、各コマンドを実装する。

今回作成した関数

ファイル情報とファイル検索

struct FILEINFO* file_getinfo(int id): 指定された番号のFILEINFOへのポインタを得る
struct FILEINFO* file_search_path(char *name, int current): 指定されたパスのファイルを探し、FILEINFOへのポインタを返す
struct FILEINFO* file_search(char *name, int current): 指定されたディレクトリの中でファイル名がnameであるものを探す。

ファイルの削除

void file_remove(struct FILEINFO *file, char recursive): ファイルを削除する。指定されたファイルがディレクトリであり、かつrecuresiveがtrueならば子となるファイルも再帰的に削除する。
void file_unlink(struct FILEINFO *file): ファイルをリンクから外す。削除は行わない。

ファイルの追加

struct FILEINFO* file_write(char *name, char *data, int parent, int fid, char is_directory): 指定されたディレクトリにファイルnameを追加する。すでにnameがあったらファイルを削除し、新たに作成する。
void file_link(struct FILEINFO *file, struct FILEINFO *directory): 指定されたファイルをdirectoryの子として登録する。

hama_duのブログ

ノンジャンル記事置き場