ls -f で返ってくるリストは何の順か?


ls のソースを読んでプログラマになりました - ablog というエントリを書いたが、「ls -f で返ってくるリストは何の順なんだろう?」と思った。ls -f を実行するとライブラリ関数 readdir(3) が呼ばれ、さらに getdents() システムコールが呼ばれ、dirent 構造体が返される。dirent 構造体は連結リストになっていて、次の dirent 構造体へのポインタを辿って行くことになると思われる。ディレクトリにエントリが追加されるたびにディレクトリエントリ(dirent 構造体)が繋がっていくので、たぶんエントリが追加されるときのロジックで決まるんだろうなと想像していた。DBエンジニアには自然な発想だと思う。
LinuxUNIX 関連の書籍はそこそこ揃っていると思っていたが、自宅にある本には書かれていなかった。本屋でふと、この本なら書いてるかもと思って、

Linuxプログラミングインタフェース

Linuxプログラミングインタフェース

この鈍器のような本を開いてみたら書かれていた。著者は http://man7.org/ の Michael Kerrisk だった。

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):

モダン オペレーティング システム 原書 第2版

モダン オペレーティング システム 原書 第2版

に設計の一つとしてハッシュテーブルがあると書かれていた。
P.412

これを速くする一つの方法は, 各ディレクトリにハッシュテーブルを使うことである。テーブルの大きさを n とし, ファイル名をしまうとき, 例えば, 名前を n で割った余りを使うことで, 0 から n-1 の間に名前をハッシュ化する. 別の方法としては, ファイル名を構成するワードの合計を計算して n で割ったり, 同じような別の方法でも良い.
どのような方法を取るにせよ, ハッシュコードに相当するテーブルのエントリが調べられる. ハッシュテーブルの後ろにファイルエントリが複数くる. そのスロットが使用中なら連結リストが作られ, 同じハッシュ値の全エントリをつないだ先頭へのポインタがそこに入れられる.
ファイル検索も同様の手続きで行える. ファイル名がハッシュ化され, ハッシュテーブルのエントリが1つ選ばれる. そのスロットからつながっている全エントリについて, ファイル名と一致するかどうかを調べる. 同じ名前がなければ, そのディレクトリにそのファイルは存在しない.