ls のソースを読んでプログラマになりました - ablog というエントリを書いたが、「ls -f で返ってくるリストは何の順なんだろう？」と思った。ls -f を実行するとライブラリ関数 readdir(3) が呼ばれ、さらに getdents() システムコールが呼ばれ、dirent 構造体が返される。dirent 構造体は連結リストになっていて、次の dirent 構造体へのポインタを辿って行くことになると思われる。ディレクトリにエントリが追加されるたびにディレクトリエントリ（dirent 構造体）が繋がっていくので、たぶんエントリが追加されるときのロジックで決まるんだろうなと想像していた。DBエンジニアには自然な発想だと思う。
Linux や UNIX 関連の書籍はそこそこ揃っていると思っていたが、自宅にある本には書かれていなかった。本屋でふと、この本なら書いてるかもと思って、
- 作者: Michael Kerrisk,千住治郎
- 出版社/メーカー: オライリージャパン
- 発売日: 2012/12/01
- メディア: 大型本
- クリック: 14回
- この商品を含むブログ (7件) を見る
P.371
18.8 ディレクトリの読み取り: opendir()とreaddir()
ディレクトリを読み取るライブラリ関数は内部で実行する getdents() システムコール(SUsv3では定義されていません)よりも利便性が図れています。Linux では同等の機能の readdir(2) システムコール(本節で取り上げる readdir(3) ライブラリ関数とは異なるものです)も実装していますが、現在では使用されていません。
P.372
readdir()が返すファイル名はなんらソートされておらず、単にディレクトリ内で見つかった順で返されます(ファイルシステムがファイルをディレクトリへ追加した順序、またファイル削除後にできたファイル名一覧のすきまを埋める処理に依存します)。ls -f コマンドは readdir() が返した順序そのままでファイル名一覧を表示します。
おまけ
getdents の man のサンプルソースを実行してみた。
#define _GNU_SOURCE #include <dirent.h> /* Defines DT_* constants */ #include <fcntl.h> #include <stdio.h> #include <unistd.h> #include <stdlib.h> #include <sys/stat.h> #include <sys/syscall.h> #define handle_error(msg) \ do { perror(msg); exit(EXIT_FAILURE); } while (0) struct linux_dirent { long d_ino; off_t d_off; unsigned short d_reclen; char d_name[]; }; #define BUF_SIZE 1024 int main(int argc, char *argv[]) { int fd, nread; char buf[BUF_SIZE]; struct linux_dirent *d; int bpos; char d_type; fd = open(argc > 1 ? argv[1] : ".", O_RDONLY | O_DIRECTORY); if (fd == -1) handle_error("open"); for ( ; ; ) { nread = syscall(SYS_getdents, fd, buf, BUF_SIZE); if (nread == -1) handle_error("getdents"); if (nread == 0) break; printf("--------------- nread=%d ---------------\n", nread); printf("i-node# file type d_reclen d_off d_name\n"); for (bpos = 0; bpos < nread;) { d = (struct linux_dirent *) (buf + bpos); printf("%8ld ", d->d_ino); d_type = *(buf + bpos + d->d_reclen - 1); printf("%-10s ", (d_type == DT_REG) ? "regular" : (d_type == DT_DIR) ? "directory" : (d_type == DT_FIFO) ? "FIFO" : (d_type == DT_SOCK) ? "socket" : (d_type == DT_LNK) ? "symlink" : (d_type == DT_BLK) ? "block dev" : (d_type == DT_CHR) ? "char dev" : "???"); printf("%4d %10lld %s\n", d->d_reclen, (long long) d->d_off, d->d_name); bpos += d->d_reclen; } } exit(EXIT_SUCCESS); }
上記のソースを getdents_test.c に保存してコンパイルし、実行可能ファイル getdents_test を作成する。
[yazekats@yazekats-linux work]$ gcc -g -o getdents_test getdents_test.c
tmp ディレクトリに 100 個ファイルを作成し、
[yazekats@yazekats-linux work]$ for i in {1..100}; do touch tmp/$i; done [yazekats@yazekats-linux work]$ ls -f tmp|head -10 . .. 35 77 33 27 12 26 31 34 [yazekats@yazekats-linux work]$ ls -v tmp|wc -l 100
getdents_test で tmp ディレクトリのディレクトリエントリをリストアップしてみると、
[yazekats@yazekats-linux work]$ ./getdents_test tmp --------------- nread=1008 --------------- i-node# file type d_reclen d_off d_name 22937610 directory 24 1 . 20451081 directory 24 20138 .. 22938032 regular 24 26892901 35 22938074 regular 24 57750998 77 22938030 regular 24 78036850 33 22938024 regular 24 101451530 27 22937615 regular 24 101674616 12 22938023 regular 24 102988448 26 22938028 regular 24 107647673 31 22938031 regular 24 117880798 34 22937601 regular 24 159334088 1 22938093 regular 24 180485746 96 22938073 regular 24 181609741 76 22938039 regular 24 184473066 42 22938067 regular 24 194707295 70 22938080 regular 24 217587122 83 22938056 regular 24 234719414 59 22937605 regular 24 239915395 5 22938019 regular 24 240306293 22 22938045 regular 24 261677857 48 22937608 regular 24 288695301 8 22938042 regular 24 331734148 45 22938052 regular 24 347524281 55 22938090 regular 24 352894191 93 22938081 regular 24 374051183 84 22938063 regular 24 424675602 66 22938095 regular 24 434190653 98 22938016 regular 24 469523301 19 22938020 regular 24 644020220 23 22938035 regular 24 652546060 38 22938046 regular 24 658900668 49 22938048 regular 24 696654398 51 22938079 regular 24 714056601 82 22938044 regular 24 719166789 47 22938072 regular 24 745613008 75 22938053 regular 24 774853812 56 22938029 regular 24 792791498 32 22938027 regular 24 797873022 30 22937616 regular 24 809359494 13 22938038 regular 24 820045463 41 22938049 regular 24 862523495 52 22938013 regular 24 866605680 16 --------------- nread=1008 --------------- i-node# file type d_reclen d_off d_name 22938025 regular 24 868460668 28 22938094 regular 24 909414662 97 22938043 regular 24 926883037 46 22938083 regular 24 937295594 86 22938022 regular 24 942806525 25 22938069 regular 24 946884266 72 22937607 regular 24 948747174 7 22938097 regular 24 993300468 100 22938026 regular 24 1001390493 29 22938064 regular 24 1018744485 67 22938040 regular 24 1020457306 43 22938047 regular 24 1065725146 50 22938021 regular 24 1069503964 24 22937609 regular 24 1104127603 9 22937606 regular 24 1158728012 6 22938060 regular 24 1172383969 63 22938050 regular 24 1194033859 53 22938085 regular 24 1203512396 88 22938017 regular 24 1227752526 20 22937603 regular 24 1246235483 3 22938018 regular 24 1292063042 21 22938091 regular 24 1313660479 94 22938061 regular 24 1318573933 64 22938087 regular 24 1326331147 90 22938092 regular 24 1339984934 95 22938015 regular 24 1340105400 18 22938036 regular 24 1404064953 39 22938086 regular 24 1448867565 89 22938033 regular 24 1470861429 36 22937604 regular 24 1479638263 4 22938062 regular 24 1490591414 65 22938088 regular 24 1518412898 91 22938059 regular 24 1532920698 62 22938051 regular 24 1548574494 54 22938066 regular 24 1591216367 69 22938055 regular 24 1618025444 58 22938077 regular 24 1678909752 80 22937602 regular 24 1701612777 2 22938068 regular 24 1733950648 71 22938096 regular 24 1736708191 99 22938089 regular 24 1754629311 92 22938084 regular 24 1772884375 87 --------------- nread=432 --------------- i-node# file type d_reclen d_off d_name 22937618 regular 24 1825605450 15 22938082 regular 24 1842672815 85 22938076 regular 24 1851794400 79 22938041 regular 24 1898867977 44 22937617 regular 24 1987373544 14 22937614 regular 24 1993128090 11 22938014 regular 24 1994397544 17 22938078 regular 24 2000313288 81 22938057 regular 24 2008614391 60 22938037 regular 24 2010495930 40 22937611 regular 24 2024701511 10 22938075 regular 24 2054413899 78 22938058 regular 24 2055545697 61 22938071 regular 24 2059023198 74 22938034 regular 24 2066901834 37 22938065 regular 24 2096940588 68 22938070 regular 24 2146885188 73 22938054 regular 24 2147483647 57
列の意味は以下の通り、
- i-node#: Inode number
- file type: File type
- d_reclen: Length of this linux_dirent
- d_off: Offset to next linux_dirent
- d_name: Filename (null-terminated)
一応、strace もとってみた。
[yazekats@yazekats-linux work]$ strace ./getdents_test tmp 2>&1|grep getdents execve("./getdents_test", ["./getdents_test", "tmp"], [/* 50 vars */]) = 0 getdents(3, /* 42 entries */, 1024) = 1008 getdents(3, /* 42 entries */, 1024) = 1008 getdents(3, /* 18 entries */, 1024) = 432 getdents(3, /* 0 entries */, 1024) = 0
追記(2014/03/18):
- 作者: Andrew S.Tanenbaum,水野忠則
- 出版社/メーカー: ピアソン・エデュケーション・ジャパン
- 発売日: 2004/12/07
- メディア: 単行本
- 購入: 4人 クリック: 99回
- この商品を含むブログ (34件) を見る
P.412
これを速くする一つの方法は, 各ディレクトリにハッシュテーブルを使うことである。テーブルの大きさを n とし, ファイル名をしまうとき, 例えば, 名前を n で割った余りを使うことで, 0 から n-1 の間に名前をハッシュ化する. 別の方法としては, ファイル名を構成するワードの合計を計算して n で割ったり, 同じような別の方法でも良い.
どのような方法を取るにせよ, ハッシュコードに相当するテーブルのエントリが調べられる. ハッシュテーブルの後ろにファイルエントリが複数くる. そのスロットが使用中なら連結リストが作られ, 同じハッシュ値の全エントリをつないだ先頭へのポインタがそこに入れられる.
ファイル検索も同様の手続きで行える. ファイル名がハッシュ化され, ハッシュテーブルのエントリが1つ選ばれる. そのスロットからつながっている全エントリについて, ファイル名と一致するかどうかを調べる. 同じ名前がなければ, そのディレクトリにそのファイルは存在しない.
