ディレクトリとは何か？minixファイルシステムのバイナリダンプとソースコードから理解する

#はじめに
ファイルやディレクトリについて調べているときに、「ディレクトリはファイルの一種」という説明を見たことがある方は多いと思います。
私は、ファイルはデータを保持する、ディレクトリはファイルを格納する、という認識でいたため、ディレクトリがファイルの一種という説明がいまいちピンと来ませんでした。
そこで、本記事ではディレクトリのどんなところをもってファイルの一種なのかを調査しました。
https://qiita.com/todok-r/items/1c47a0b270d42444d538
でも取り上げましたが、本記事でも比較的シンプルなminixファイルシステムを取りあげ、

1. ディレクトリやファイルを生成した際のファイルシステムの変化をバイナリデータレベルで観察
2. ディレクトリを触っているソースを見て具体的なディレクトリの扱いを調査

することで、ディレクトリとはなにかのイメージを掴んでいきたいと思います。
minixファイルシステムはバージョン1〜3がありますが、今回はバージョン1の前提です。
なお、コマンドの実行結果中で#で始まる行とソースコー中の日本語コメントはは私の追加したコメントです。

#1. minixファイルシステムの変化をバイナリデータ観点から見てみる

##minixファイルシステムの準備
まずはminixファイルシステムを作成します。
今回の調査では簡単のため、ブロックデバイスにminixファイルシステムを作るのではなく、ファイル上にファイルシステムを作成し、mountに-o loopをつけてマウントします。
また、ファイルシステムの変化を見るために、ファイルシステム作成直後のデータをminix.img.orgとして保持しておきます。

```
#ファイルシステムを作成するための領域をminix.imgファイルとして確保。1024byte✕1024個
$ dd if=/dev/zero of=minix.img bs=1024 count=1024
1024+0 レコード入力
1024+0 レコード出力
1048576 bytes (1.0 MB, 1.0 MiB) copied, 0.0067203 s, 156 MB/s

#minix.img上にminixファイルシステムを作成
$ mkfs.minix minix.img
352 inodes
1024 blocks
Firstdatazone=15 (15)
Zonesize=1024
Maxsize=268966912

#比較のために、ファイルシステム作成直後のイメージを保存
$ cp minix.img minix.img.org
```

##minixファイルシステムの構造
実際にファイルシステムをいじる前に、minixファイルシステムの構造について簡単に説明します。
minixファイルシステムの詳細について興味がある方は以下のページ等をご参照ください。
https://www.linux.org/threads/minix-mini-unix-file-system.8998/

minixファイルシステムの各領域はブロック単位で構成されます。1ブロックは1024バイトです。ブロック番号は0から開始します。

![minix.jpg](https://qiita-image-store.s3.amazonaws.com/0/328860/5aedbbad-e1b3-2457-a651-701c15fe217c.jpeg)


* ブートブロック：minixファイルシステムの先頭1ブロック目に格納される。ブートパーティションとして指定された場合の起動コードを格納する領域
* スーパーブロック：minixファイルシステムの先頭2ブロック目に格納される。ファイルシステムの各種情報を格納する領域
* inodeビットマップ：inode区画の使用状況を管理する。例えば、inode番号2が使用されている場合、inodeビットマップの2ビット目がセットされる
* ゾーンビットマップ：データ区画の使用状況を管理する
* inode区画：inodeが格納される領域

inode中のi_zoneメンバはそのinodeに割り当てられているデータ区画のブロック番号を指しています。
ファイルサイズが7✕1024バイト以下の場合は、先頭のi_zone[0]〜i_zone[6]のそれぞれがファイルのデータが格納されているデータ区画のブロック番号を示します。
今回は大きなファイルは作成しないため、i_zone[7]〜i_zone[9]についての説明は割愛します。

* データ区画：ファイルやディレクトリ等のデータが格納される領域


データ区画の開始位置はビットマップに割り当てるブロック数によって決まります。
mkfs.minixを実行したときに以下のように出力されていますが、ここでの「Firstdatazone」がデータ区画の開始ブロック番号を示します。ですので、今回作成したファイルシステムでは15ブロック目からデータ区画が開始します。
また、作成直後のファイルシステムを見てみると、imap_blocksとzmap_blocksがともに1となっています。
データ区画の開始ブロック番号が15であることから、inode区画のサイズは先頭15ブロックから4ブロック(ブートブロック、スーパーブロック、inodeビットマップ、ゾーンビットマップの4ブロック)を除いた11ブロックとなります。
(バイナリデータを見るときは、データがリトルエンディアンで格納されていることに注意してください)

```
$ mkfs.minix minix.img
352 inodes
1024 blocks
#データ区画の最初のブロック番号は15
Firstdatazone=15 (15)
Zonesize=1024
Maxsize=268966912
$ cp minix.img minix.img.org

$ hexdump -C minix.img
00000000  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
#0x400=スーパーブロック.
#0x410,0x411=ninodes=0x160=352
#0x412,0x413=nzones=0x400=1024
#0x414,0x415=imap_blocks=0x01=1
#0x416,0x417=zmap_blocks=0x01=1
#0x418,0x419=firstdatazone=0x0f=15
00000400  60 01 00 04 01 00 01 00  0f 00 00 00 00 1c 08 10  |`...............|
00000410  8f 13 01 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000420  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
#省略
```

次に実際にファイル、ディレクトリを作成するとファイルシステムがどう変化するかを見ていきます。

##ファイルを作成したとき
ディレクトリを作成する前にまずはファイル作成時にファイルシステムはどう変化するかを見ていきたいと思います。
minix.imgをmountに-o loopをつけてマウントした後に、マウントポイント直下に以下のようにファイルを作成しました。
マウントポイントはmountというディレクトリ名です。

| パス| データ | inode番号|
|:-------|:-----------|:-----------|
|mount | -  | 1 |
|mount/1.txt | aiueo  | 2 |
|mount/2.txt | 12345  | 3 |

マウントポイント直下に1.txtと2.txtを作成し、それぞれに"aiueo", "12345"を書き込んでみると、以下のようになりました。
1.txtのinode番号は2、2.txtのinode番号は3となっています。また、マウントポイントのディレクトリのinode番号は1となっています。

```
$ sudo mount -o loop minix.img mount
$ cd mount
mount$ echo aiueo > 1.txt
mount$ echo 12345 > 2.txt
mount$ ls -li
合計 2
2 -rw-rw-r-- 1 user user 6  1月 11 00:35 1.txt
3 -rw-rw-r-- 1 user user 6  1月 11 00:35 2.txt
mount$ cd ..
$ ls -ldi mount
1 drwxr-xr-x 2 user 232 128  1月 11 00:35 mount
$ sync
```

これによりファイルシステムイメージも更新されているはずです。書き込み前後のファイルシステムイメージをhexdumpでダンプし、変更前のファイルシステムイメージと差分を取ってみると、以下のようになりました。
<で始まる行がファイルシステム作成直後(minix.img.org)の状態、>で始まる行がファイル作成後の状態となります。

```
$ hexdump -C minix.img > minix.img.hex
$ hexdump -C minix.img.org > minix.img.org.hex
$ diff minix.img.org.hex minix.img.hex 
#0x400=スーパーブロック.
#0x412はスーパーブロックの状態を指す。今回は気にしない
4c4
< 00000410  8f 13 01 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
---
> 00000410  8f 13 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

#0x800=inodeビットマップ
#0x0f＝inode区画の0〜3が使用されている
7c7
< 00000800  03 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
---
> 00000800  0f 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

#0xc00=ゾーンビットマップ
#0x0f＝データ区画の0〜3ブロックが使用されている
12c12
< 00000c00  03 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
---
> 00000c00  0f 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

#0x1000=inode区画
#0x1000=inode番号1=マウントポイント
#i_zone[0](14,15バイト目)は0x0f=15番目のブロックを指している
18c18
< 00001000  ed 41 e8 03 40 00 00 00  2e 4c 37 5c e8 02 0f 00  |.A..@....L7\....|
---
> 00001000  ed 41 e8 03 80 00 00 00  36 66 37 5c e8 02 0f 00  |.A......6f7\....|

#0x1020=inode番号2=1.txt
#i_zone[0](14,15バイト目)は0x10=16番目のブロックを指している
19a20,23
> 00001020  b4 81 e8 03 06 00 00 00  33 66 37 5c e8 01 10 00  |........3f7\....|
> 00001030  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

#0x1040=inode番号3=2.txt
#i_zone[0](14,15バイト目)は0x11=17番目のブロックを指している
> 00001040  b4 81 e8 03 06 00 00 00  36 66 37 5c e8 01 11 00  |........6f7\....|
> 00001050  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

#0x3c00=15番めのブロック=inode番号1のデータ
25c29
< 00003c40  00 00 2e 62 61 64 62 6c  6f 63 6b 73 00 00 00 00  |...badblocks....|

#マウントポイント配下に作成したファイル名とinode番号が保存されている
---
> 00003c40  02 00 31 2e 74 78 74 00  00 00 00 00 00 00 00 00  |..1.txt.........|
26a31,38
> 00003c60  03 00 32 2e 74 78 74 00  00 00 00 00 00 00 00 00  |..2.txt.........|
> 00003c70  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
> *

#0x4000=16番めのブロック=inode番号2のデータ
> 00004000  61 69 75 65 6f 0a 00 00  00 00 00 00 00 00 00 00  |aiueo...........|
> 00004010  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
> *

#0x4400=17番めのブロック=inode番号3のデータ
> 00004400  31 32 33 34 35 0a 00 00  00 00 00 00 00 00 00 00  |12345...........|
> 00004410  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
```

inode番号2、3が追加されたので、inodeビットマップの該当するビットが使用中(ビットがセット)となっています。
inode区画は32バイトのstruct_minix_inodeデータが格納されていますが、1.txtを示すinode番号2のinode、2.txtを示すinode番号3のinodeがそれぞれ更新されています。
それぞれのinode中のi_zone[0]に該当するデータも更新されており、1.txtは0x0010=16番目のブロック、2.txtは0x0011=17番目のブロックを指しています。
それぞれのブロックを見てみると、"aiueo"、"12345"が格納されており、上述の通りにファイルシステムが更新されていることがわかります。
また、ファイルに書き込んだデータのサイズは5バイトしかありませんが、ファイルシステム上は1ブロックを使用していることもわかります。
ここまでの結果から、ファイル作成時にファイルシステムが更新されることがわかりました。

##ディレクトリを作成したとき
次にディレクトリ作成時のファイルシステムの変化を見ていきます。
その前に、上でファイルを作成した際に、inode番号1のinode中のi_zone[0]が0x000f=15番目のブロック(データ区画の先頭)を指していることに注目してください。inode番号1はマウントポイントのディレクトリですが、ファイルと同様にデータ区画にブロックが割り当てられています。
15番目のブロックを見てみると、マウントポイント配下に作成したファイル名が格納されており、ファイル名より前の2バイトにはinode番号が格納されています。

```
#マウントポイント配下に作成したファイル名とinode番号が保存されている
> 00003c40  02 00 31 2e 74 78 74 00  00 00 00 00 00 00 00 00  |..1.txt.........|
26a31,38
> 00003c60  03 00 32 2e 74 78 74 00  00 00 00 00 00 00 00 00  |..2.txt.........|
```

このことから、マウントポイントのディレクトリは、配下に格納しているファイルのファイル名、inode番号をデータとして持っていることがわかります。
これにより、ディレクトリはデータ区画にデータを持つ＝ファイルと同じようにデータを持っていそうなことが見えてきました。
それでは、次に実際にディレクトリを作成してみます。
マウントポイント直下にa, bディレクトリ、aディレクトリ配下にA.txtファイルを作成後の状態が以下の表です。以下の表の★印のついているのが作成したディレクトリとその配下のファイルとなります。

| パス| データ | inode番号|
|:-------|:-----------|:-----------|
|mount | -  | 1 |
|mount/1.txt | aiueo  | 2 |
|mount/2.txt | 12345  | 3 |
|★mount/a | -  | 4 |
|★mount/b | -  | 5 |
|★mount/a/A.txt | A  | 6 |
|★mount/a/B.txt | B  | 7 |


```
mount$ mkdir a b
mount$ echo A > a/A.txt
mount$ echo B > a/B.txt
mount$ ls -li
合計 4
2 -rw-rw-r-- 1 user user  6  1月 11 00:35 1.txt
3 -rw-rw-r-- 1 user user  6  1月 11 00:35 2.txt
4 drwxrwxr-x 2 user user 96  1月 11 01:15 a
5 drwxrwxr-x 2 user user 64  1月 11 01:14 b
mount$ ls -li a
合計 1
6 -rw-rw-r-- 1 user user 2  1月 11 01:15 A.txt
7 -rw-rw-r-- 1 user user 2  1月 11 13:35 B.txt
```

次にディレクトリ作成後のファイルシステムイメージをhexdumpでダンプし、変更前のファイルシステムイメージとの差分を取ってみると、以下のようになりました。
ファイル作成時のコメントも残しているので、今回の手順で発生した差分についてはコメント先頭に★をつけています。

```
$ hexdump -C minix.img > minix.img.hex_dir
$ diff minix.img.org.hex minix.img.hex.dir 
 diff minix.img.org.hex minix.img.hex.dir 
 4c4
 < 00000410  8f 13 01 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 ---
 > 00000410  8f 13 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

#0x800=inodeビットマップ
#0xff＝inode区画の0〜7が使用されている
 7c7
 < 00000800  03 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 ---
 > 00000800  ff 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

#0xc00=ゾーンビットマップ
#0x0f＝データ区画の0〜3ブロックが使用されている
 12c12
 < 00000c00  03 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 ---
 > 00000c00  ff 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

#0x1000=inode区画
#0x1000=inode番号1=マウントポイント
#i_zone[0](14,15バイト目)は0x0f=15番目のブロックを指している
 18c18
 < 00001000  ed 41 e8 03 40 00 00 00  2e 4c 37 5c e8 02 0f 00  |.A..@....L7\....|
 ---
 > 00001000  ed 41 e8 03 c0 00 00 00  81 6f 37 5c e8 04 0f 00  |.A.......o7\....|

#0x1020=inode番号2=1.txt
#i_zone[0](14,15バイト目)は0x10=16番目のブロックを指している
 19a20,31
 > 00001020  b4 81 e8 03 06 00 00 00  33 66 37 5c e8 01 10 00  |........3f7\....|
 > 00001030  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

#0x1040=inode番号3=2.txt
#i_zone[0](14,15バイト目)は0x11=17番目のブロックを指している
 > 00001040  b4 81 e8 03 06 00 00 00  36 66 37 5c e8 01 11 00  |........6f7\....|
 > 00001050  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

#★0x1060=inode番号4=aディレクトリ
#★i_zone[0](14,15バイト目)は0x12=18番目のブロックを指している
 > 00001060  fd 41 e8 03 80 00 00 00  2e 1d 38 5c e8 02 12 00  |.A........8\....|
 > 00001070  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

#★0x1080=inode番号5=bディレクトリ
#★i_zone[0](14,15バイト目)は0x13=19番目のブロックを指している
 > 00001080  fd 41 e8 03 40 00 00 00  81 6f 37 5c e8 02 13 00  |.A..@....o7\....|
 > 00001090  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

#★0x10a0=inode番号6=a/A.txt
#★i_zone[0](14,15バイト目)は0x14=20番目のブロックを指している
 > 000010a0  b4 81 e8 03 02 00 00 00  b6 6f 37 5c e8 01 14 00  |.........o7\....|
 > 000010b0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

#★0x10c0=inode番号7=a/B.txt
#★i_zone[0](14,15バイト目)は0x15=21番目のブロックを指している
 > 000010c0  b4 81 e8 03 02 00 00 00  2e 1d 38 5c e8 01 15 00  |..........8\....|
 > 000010d0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

#0x3c00=15番めのブロック=inode番号1のデータ
 25c37
 < 00003c40  00 00 2e 62 61 64 62 6c  6f 63 6b 73 00 00 00 00  |...badblocks....|
 ---

#マウントポイント配下に作成したファイル名とinode番号が保存されている
 > 00003c40  02 00 31 2e 74 78 74 00  00 00 00 00 00 00 00 00  |..1.txt.........|
 26a39,70
 > 00003c60  03 00 32 2e 74 78 74 00  00 00 00 00 00 00 00 00  |..2.txt.........|
 > 00003c70  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 > 00003c80  04 00 61 00 00 00 00 00  00 00 00 00 00 00 00 00  |..a.............|
 > 00003c90  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 > 00003ca0  05 00 62 00 00 00 00 00  00 00 00 00 00 00 00 00  |..b.............|
 > 00003cb0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 > *

#0x4000=16番めのブロック=inode番号2のデータ
 > 00004000  61 69 75 65 6f 0a 00 00  00 00 00 00 00 00 00 00  |aiueo...........|
 > 00004010  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 > *

#0x4400=17番めのブロック=inode番号3のデータ
 > 00004400  31 32 33 34 35 0a 00 00  00 00 00 00 00 00 00 00  |12345...........|
 > 00004410  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 > *

#★0x4800=18番めのブロック=inode番号4のデータ
#2e="."：カレントディレクトリ
 > 00004800  04 00 2e 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 > 00004810  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
#ペアレントディレクトリ
 > 00004820  01 00 2e 2e 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 > 00004830  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
#ディレクトリ配下のファイル
 > 00004840  06 00 41 2e 74 78 74 00  00 00 00 00 00 00 00 00  |..A.txt.........|
 > 00004850  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 > 00004860  07 00 42 2e 74 78 74 00  00 00 00 00 00 00 00 00  |..B.txt.........|
 > 00004870  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 > *

#★0x4c00=19番めのブロック=inode番号5のデータ
#2e="."：カレントディレクトリ
 > 00004c00  05 00 2e 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 > 00004c10  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
#ペアレントディレクトリ
 > 00004c20  01 00 2e 2e 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 > 00004c30  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 > *

#★0x5000=20番めのブロック=inode番号6のデータ
 > 00005000  41 0a 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |A...............|
 > 00005010  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 > *

#★0x5400=21番めのブロック=inode番号7のデータ
 > 00005400  42 0a 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |B...............|
 > 00005410  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
```

新規に作成したディレクトリ、ファイルに対してinode区画の領域が割り当てられ、inodeビットマップが更新されていることがわかります。また、ディレクトリに対してデータ区画のブロックが割り当てられていることもわかります。
mount/a(inode番号4)に対応するinodeを見ると、i_zone[0]はブロック番号18を指しています。ブロック番号18のデータを見てみると、カレントディレクトリ、ペアレントディレクトリ、配下のファイルのinode番号とファイル名がデータとして格納されていることがわかります。また、各データは32バイト単位となっています。
一方、mount/b(inode番号5)に対応するデータ区画(ブロック番号19)を見てみると、配下にファイルがないため、カレントディレクトリ、ペアレントディレクトリの情報のみが格納されています。

以上より、
ディレクトリはデータ区画にデータを持つ＝ファイルと同じようにデータを持つ＝ディレクトリはファイルの一種
ということがファイルシステムのバイナリデータ観点からイメージできるのではないかと思います。

#2. minixファイルシステムのディレクトリの扱いをソースコードから見てみる
次にディレクトリデータを実際に触っている箇所として、ディレクトリに格納されているファイル名を取得するgetdentsのコードを見てみます。
最近のバージョンのLinuxではディレクトリの走査はreaddirではなく、getdentsで行っているようです。(glibcのreaddirの実装がgetdents？)

```
$ strace ls
execve("/bin/ls", ["ls"], [/* 68 vars */]) = 0
...
open(".", O_RDONLY|O_NONBLOCK|O_DIRECTORY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFDIR|0775, st_size=4096, ...}) = 0
getdents(3, /* 15 entries */, 32768)    = 504
getdents(3, /* 0 entries */, 32768)     = 0
...
```

getdents内ではまずコールバック用の構造体(getdents_callback)の設定を行っていますが、これについては後で触れます。
ディレクトリ走査のメインの処理はiterate_dirで行っています。

```C:fs/readdir.c
SYSCALL_DEFINE3(getdents, unsigned int, fd,
		struct linux_dirent __user *, dirent, unsigned int, count)
{
	struct fd f;
	struct linux_dirent __user * lastdirent;
	struct getdents_callback buf = {
		.ctx.actor = filldir,
		.count = count,
		.current_dir = dirent
	};
	int error;

	if (!access_ok(VERIFY_WRITE, dirent, count))
		return -EFAULT;

	f = fdget_pos(fd);
	if (!f.file)
		return -EBADF;

	// ディレクトリ走査のメイン処理
	error = iterate_dir(f.file, &buf.ctx);
	if (error >= 0)
		error = buf.error;
	lastdirent = buf.previous;
	if (lastdirent) {
		if (put_user(buf.ctx.pos, &lastdirent->d_off))
			error = -EFAULT;
		else
			error = count - buf.count;
	}
	fdput_pos(f);
	return error;
}
```

linux_direntの定義は以下の通りです。(man getdentsより)

```
struct linux_dirent {
	unsigned long  d_ino;     /* Inode number */
	unsigned long  d_off;     /* Offset to next linux_dirent */
	unsigned short d_reclen;  /* Length of this linux_dirent */
	char           d_name[];  /* Filename (null-terminated) */
			/* length is actually (d_reclen - 2 -
			   offsetof(struct linux_dirent, d_name)) */
	/*
	   char           pad;       // Zero padding byte
	   char           d_type;    // File type (only since Linux
	// 2.6.4); offset is (d_reclen - 1)
	 */
}
```

iterate_dirの中ではfile_operationsに登録されているiterate_sharedかiterateを実行します。
minixファイルシステムでは以下のようにiterate_sharedが定義されているので、file->f_op->iterate_shared(file, ctx)が実行されます。
iterate_sharedを実行する前にctx->posにfile->f_posの値を設定しています。file->f_posは通常のファイルであれば現在のファイルのアクセス位置を示しますが、ディレクトリでも同様に現在までに走査したディレクトリの位置を保存しています。

```C:fs/minix/dir.c
const struct file_operations minix_dir_operations = {
	.llseek		= generic_file_llseek,
	.read		= generic_read_dir,
	.iterate_shared	= minix_readdir,
	.fsync		= generic_file_fsync,
};
```

```C:fs/readdir.c
int iterate_dir(struct file *file, struct dir_context *ctx)
{
	struct inode *inode = file_inode(file);
	bool shared = false;
	int res = -ENOTDIR;
	if (file->f_op->iterate_shared)
		shared = true;
	else if (!file->f_op->iterate)
		goto out;

	res = security_file_permission(file, MAY_READ);
	if (res)
		goto out;

	if (shared)
		res = down_read_killable(&inode->i_rwsem);
	else
		res = down_write_killable(&inode->i_rwsem);
	if (res)
		goto out;

	res = -ENOENT;
	if (!IS_DEADDIR(inode)) {
		//fileに保存されている現在までに走査したディレクトリ内の位置
		ctx->pos = file->f_pos;
		if (shared)
			//ファイルシステム固有の処理を実行
			res = file->f_op->iterate_shared(file, ctx);
		else
			res = file->f_op->iterate(file, ctx);
		file->f_pos = ctx->pos;
		fsnotify_access(file);
		file_accessed(file);
	}
	if (shared)
		inode_unlock_shared(inode);
	else
		inode_unlock(inode);
out:
	return res;
}
```

file->f_op->iterate_sharedの実体は以下のminix_readdirとなります。
大まかな処理の流れは以下のようになります。

1. 現在までに走査したディレクトリ位置を算出
2. ページキャッシュからディレクトリデータを取得(ページ単位)し、該当する仮想アドレスを算出
3. 現在のディレクトリ位置のファイル名、inode番号を取得
4. ユーザ層へデータ書き込み

ファイルのデータを読み書きする場合、通常は、毎回直接ストレージデバイスにアクセスするのではなく、メモリ上のキャッシュ領域にを通して行います。
ページキャッシュについてはここでは詳細について触れませんが、以下ページで詳しく解説されています。
https://qiita.com/rarul/items/a6688fd2a06d960cb5ea

```C:fs/minix/dir.c
static int minix_readdir(struct file *file, struct dir_context *ctx)
{
	struct inode *inode = file_inode(file);
	struct super_block *sb = inode->i_sb;
	struct minix_sb_info *sbi = minix_sb(sb);

	//sbi->s_dirsize = 32.ディレクトリのサイズ.mount時にminix_fill_superで設定される
	unsigned chunk_size = sbi->s_dirsize;

	//ディレクトリに割り当てられている領域のサイズ(ページ数)
	//1ページは4096バイト
	unsigned long npages = dir_pages(inode);

	//1. 現在のディレクトリ位置
	unsigned long pos = ctx->pos;
	unsigned offset;
	unsigned long n;

	//chunk_size(16バイト)境界に切り上げ
	ctx->pos = pos = ALIGN(pos, chunk_size);
	if (pos >= inode->i_size)
		return 0;

	//ディレクトリ内の次のファイルへのオフセット
	offset = pos & ~PAGE_MASK;
	n = pos >> PAGE_SHIFT;

	//ディレクトリを走査(ページ単位)
	for ( ; n < npages; n++, offset = 0) {
		char *p, *kaddr, *limit;
		//2. ディレクトリデータをページキャッシュから取得
		struct page *page = dir_get_page(inode, n);

		if (IS_ERR(page))
			continue;
		//ページを仮想アドレスに変換
		kaddr = (char *)page_address(page);

		//次のファイル情報の格納されているページ内のアドレスを算出
		p = kaddr+offset;
		limit = kaddr + minix_last_byte(inode, n) - chunk_size;

		//minix_next_entryは次のファイル情報が格納されているアドレスを返す
		for ( ; p <= limit; p = minix_next_entry(p, sbi)) {
			const char *name;
			__u32 inumber;

			//minixファイルシステムには複数のバージョンがある
			if (sbi->s_version == MINIX_V3) {
				minix3_dirent *de3 = (minix3_dirent *)p;
				name = de3->name;
				inumber = de3->inode;
	 		} else {
				minix_dirent *de = (minix_dirent *)p;
				name = de->name;
				inumber = de->inode;
			}
			if (inumber) {
				unsigned l = strnlen(name, sbi->s_namelen);

				//ユーザ層へデータ書き込み
				if (!dir_emit(ctx, name, l,
					      inumber, DT_UNKNOWN)) {
					dir_put_page(page);
					return 0;
				}
			}
			ctx->pos += chunk_size;
		}
		dir_put_page(page);
	}
	return 0;
}
```

ディレクトリ内の次のファイル情報を取得する関数は以下のような実装になっています。ここでsbi->s_dirsizeの値は32です。
ファイルシステムのバイナリデータを見た時にディレクトリデータのサイズが32バイトとなっていましたが、ここでソースコードとつながります。

```C:fs/minix/dir.c
static inline void *minix_next_entry(void *de, struct minix_sb_info *sbi)
{
	return (void*)((char*)de + sbi->s_dirsize);
}
```

ユーザへ返すデータの作成はdir_emitで行っています。ここでctx->actorはgetdentsで設定したコールバック用構造体で設定されていたfilldirです。

```C:include/linux/fs.h
static inline bool dir_emit(struct dir_context *ctx,
			    const char *name, int namelen,
			    u64 ino, unsigned type)
{
	return ctx->actor(ctx, name, namelen, ctx->pos, ino, type) == 0;
}
```

filldirの実体は以下のようになっており、ユーザ層へデータを書き込む処理を行います。

```C:fs/readdir.c
static int filldir(struct dir_context *ctx, const char *name, int namlen,
		   loff_t offset, u64 ino, unsigned int d_type)
{
	struct linux_dirent __user * dirent;
	struct getdents_callback *buf =
		container_of(ctx, struct getdents_callback, ctx);
	unsigned long d_ino;
	int reclen = ALIGN(offsetof(struct linux_dirent, d_name) + namlen + 2,
		sizeof(long));

	buf->error = -EINVAL;	/* only used if we fail.. */
	if (reclen > buf->count)
		return -EINVAL;
	d_ino = ino;
	if (sizeof(d_ino) < sizeof(ino) && d_ino != ino) {
		buf->error = -EOVERFLOW;
		return -EOVERFLOW;
	}
	dirent = buf->previous;
	if (dirent) {
		if (signal_pending(current))
			return -EINTR;
		if (__put_user(offset, &dirent->d_off))
			goto efault;
	}
	dirent = buf->current_dir;
	//__put_userでユーザ層へデータをwrite
	if (__put_user(d_ino, &dirent->d_ino))
		goto efault;
	if (__put_user(reclen, &dirent->d_reclen))
		goto efault;
	if (copy_to_user(dirent->d_name, name, namlen))
		goto efault;
	if (__put_user(0, dirent->d_name + namlen))
		goto efault;
	if (__put_user(d_type, (char __user *) dirent + reclen - 1))
		goto efault;
	buf->previous = dirent;
	dirent = (void __user *)dirent + reclen;
	buf->current_dir = dirent;
	buf->count -= reclen;
	return 0;
efault:
	buf->error = -EFAULT;
	return -EFAULT;
}
```

#おわりに
ディレクトリの実体について、ファイルシステムのバイナリデータ観点と、minixのソースコード観点で見てみました。
ディレクトリ＝ファイルの一種である
ことのイメージを掴んでもらえれば幸いです。
誤り等がありましたらご指摘いただけるとありがたいです。