シンプルそうな問題でありながら、実は手強いネタで、背後にいろんな理由が工夫やあるのだな〜と非常におもしろかったです.

この手の調査では strace を取ってシステムコールを追いかけたくなる。find(1) が呼び出す getdents(2) がどんな風に動作するのか、あるいは mv、つまり、rename(2) と併用したケースなど調べようとすらしたことなかったなと思い実験をした

このエントリで取り扱うお題

getdents(2) で 1ディレクトリエントリずつ読み出して rename(2) していくと、ファイルシステムによってどんな違いがでるか?

先のブログで書かれていた find(1) + mv(1) あるいは readdir(3), fts_read(3) ではなく、システムコールを直接呼び出して実験する.

コマンドやライブラリの実装レイヤをすっ飛ばすことで、ファイルシステムの生の挙動を把握しやすくなるだろう
1ディレクトリエントリ= getdents(2) で扱いうる最小単位で実験して結果を観察することで、それよりもエントリ数が多い場合の挙動を演繹して考えることが可能になるだろう

POSIX を確認する

This is not a bug; the POSIX specification explicitly allows this
behavior.  If a filename is renamed during a readdir() session of a
directory, it is undefined where that neither, either, or both of the
new and old filenames will be returned.

readdir() nonatomicity (Theodore Ts'o)

同ブログで引用されていた ML を読むと、readdir(3) している最中に rename(2) した場合は POSIX 仕様でも未定義らしい. getdents(2) でも同様と考えてよいだろう

先にまとめ

XFS と Btrfs が面白いことになります

f:id:hiboma:20180323194843g:plain

f:id:hiboma:20180323194849g:plain

f:id:hiboma:20180322182444g:plain

続きを読んでね

システムコールの理解

man 2 getdents

getdents(2) で 1ディレクトリエントリずつ読み出す方法 を調べる。システムコールのインタフェースは下記の通りである

int getdents(unsigned int fd, struct linux_dirent *dirp,
             unsigned int count);

注: このシステムコールには glibc のラッパー関数は存在しない。「注意」の節を参照。

Man page of GETDENTS

man に記載されているように getdents(2) は readdir(3) でラップされているのでシステムコール単体で扱う機会は、ほとんど、無い (もし、あなたが libc の開発者ならば話は別だろうが 🤗 )

glibc から使えないのは面倒だな ... と思ったが、幸いなことに上記の man ページに直接システムコールを呼び出すコードが書かれている。これを拝借して後述する試験コードとに転用した

count 引き数はそのバッファーのサイズを示す。

インタフェースには count とあるが実はバッファのサイズである。このバッファサイズを極力小さくすることで 1ディレクトリエントリずつ読み出しができた。

実装は後述のコードを見ていただきたい。

find のバッファサイズ

find コマンドは count = バッファサイズを 32768 としている。 strace で確かめることができる

$ strace -egetdents find 2>&1 | grep getdents | head
getdents(4, /* 23 entries */, 32768)    = 832
getdents(4, /* 0 entries */, 32768)     = 0
getdents(6, /* 3 entries */, 32768)     = 88
getdents(6, /* 0 entries */, 32768)     = 0
getdents(6, /* 57 entries */, 32768)    = 1864
getdents(6, /* 0 entries */, 32768)     = 0
getdents(6, /* 228 entries */, 32768)   = 7448
getdents(6, /* 0 entries */, 32768)     = 0
getdents(6, /* 7 entries */, 32768)     = 208
getdents(6, /* 0 entries */, 32768)     = 0

なお、ユーザランドツールは CentOS7.4 ベースを使用しており findutils のバージョンは下記の通り

$ rpm -qf $(which find)
findutils-4.5.11-5.el7.x86_64

man 2 rename

rename(2) のインタフェースもおさらいしておく

#include <stdio.h>

int rename(const char *oldpath, const char *newpath);

Man page of RENAME

man をみると renameat(2) や renameat2(2) もあるが、今回は使わない

実験

プロトタイプを書いて試してみてから、以下のようにまとめた

実験の設計

getdents(2) + rename(2) を観察するのと、 getdents(2) がファイルシステムの実装に依存するのかどうかを確かめるべく複数のファイルシステムを用意した上で、試験コードを実行して比較する

ファイルシステムは mkfs.* で用意できた以下のリストを対象に選び出した

ext2
ext3
ext4
tmpfs
minix
xfs
btrfs

Vagrant 上の VM で作業したいのでループバックデバイス/ループデバイスを用いてファイルシステムを作成する.

blog.amedama.jp

qiita.com

上記のエントリを参考にした。感謝です!

実験のコード

以下のようなロジックを走らせる

対象のファイルシステム上の、任意のディレクトリに 0 〜 9 の連番でファイルを作る (注: シェルスクリプトで準備する)
1のディレクトリから getdents(2) で 1ディレクトリエントリ だけ読みだす
2のディレクトリエントリを別名に rename(2) する (元のファイル名の末尾に + を付記したものを別名とする)
2-3 をループする

man getdents に掲載されていたサンプルコードをベースに実装した.

https://raw.githubusercontent.com/hiboma/getdents-rename-testing/master/getdents.c

#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>
#include <errno.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[];
};

void change_name(char *prefix, struct linux_dirent * d) {
    char old[PATH_MAX+1];
    char new[PATH_MAX+1];

    sprintf(old, "%s/%s",  prefix, d->d_name);
    sprintf(new, "%s/%s+", prefix, d->d_name);
    if (rename(old, new) == -1)
      handle_error("rename");

    struct stat st;
    if (stat(new, &st) == -1)
      handle_error("stat");

    fprintf(stderr ,"rename(2): %-10ld -> %-10ld : %-20s -> %-20s\n", d->d_ino, st.st_ino, old, new);
} 

static int buffer_size = 32;

int
main(int argc, char *argv[])
{
    char *dir = argv[1];

    char *buf = malloc(buffer_size);
    if (buf == NULL)
        handle_error("malloc");
  
    int fd = open(argc > 1 ? argv[1] : ".", O_RDONLY | O_DIRECTORY);
    if (fd == -1)
        handle_error("open");

    for ( ; ; ) {
        int nread = syscall(SYS_getdents, fd, buf, buffer_size);
        if (nread == -1) {

            if (errno == EINVAL) { 
              fprintf(stderr, "getdents(2) returned EINVAL. Try to allocate a bigger buffer\n");
              buffer_size++;
          buf = realloc(buf, buffer_size);
              if (buf == NULL)
                  handle_error("realloc");

              usleep(1000 * 50);
              continue;
            }  

            handle_error("getdents");
        }

        if (nread == 0) { 
            fprintf(stderr, "[DONE] getdents(2) returned 0\n");
            break;
        }

        for (int bpos = 0; bpos < nread;) {
            struct linux_dirent *d;
            d = (struct linux_dirent *) (buf + bpos);

            bpos += d->d_reclen;
            if (d->d_name[0] == '.')  
              continue;

            change_name(dir, d);
            //usleep(1000 * 50);
        }
    }

    exit(EXIT_SUCCESS);
}

設計とか抽象とか再利用とかは試験のスコープを外れた話題なので、深くつっこまないでほしい.

実験する VM

ユーザランドは CentOS7.4 ベースの VM で、カーネルだけ新しいものにしている

$ uname -a
Linux localhost.localdomain 4.16.0-rc6 #1 SMP Wed Mar 21 15:24:00 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

実験の実施手順

Makefille に手順をまとめている

セットアップ

$ git clone https://github.com/hiboma/getdents-rename-testing
$ cd getdents-rename-testing
$ sudo su
# make device
# make mkfs
# make mount

実行

環境が整ったら以下の手順でファイルシステムごとに実験を行える. 繰り返し実行してもかまわない

# make test filesystem=ext2
# make test filesystem=ext3
# make test filesystem=ext4
# make test filesystem=tmpfs
# make test filesystem=minix
# make test filesystem=btrfs
# make test filesystem=xfs

注意: ファイルが消し飛んでも大丈夫な VM や Docker 等で検証してください. コードの不備で何かが消し飛んでらごめんね.ごめんね

実験結果

以下、ファイルシステムごとの実験結果を乗せていく

ext2

👈 以下の出力が試験コードの STDERR である.

-bash-4.2$ sudo make test filesystem=ext2
ls         /mnt/ext2 >/dev/null
rm -rf     /mnt/ext2/*
touch      /mnt/ext2/{0..9}
./getdents /mnt/ext2
rename(2): 14         -> 14         : /mnt/ext2/3          -> /mnt/ext2/3+ 👈
rename(2): 16         -> 16         : /mnt/ext2/5          -> /mnt/ext2/5+
rename(2): 19         -> 19         : /mnt/ext2/8          -> /mnt/ext2/8+
rename(2): 12         -> 12         : /mnt/ext2/1          -> /mnt/ext2/1+
rename(2): 15         -> 15         : /mnt/ext2/4          -> /mnt/ext2/4+
rename(2): 16         -> 16         : /mnt/ext2/5+         -> /mnt/ext2/5++
rename(2): 20         -> 20         : /mnt/ext2/9          -> /mnt/ext2/9+
rename(2): 13         -> 13         : /mnt/ext2/2          -> /mnt/ext2/2+
rename(2): 17         -> 17         : /mnt/ext2/6          -> /mnt/ext2/6+
rename(2): 19         -> 19         : /mnt/ext2/8+         -> /mnt/ext2/8++
rename(2): 15         -> 15         : /mnt/ext2/4+         -> /mnt/ext2/4++
rename(2): 13         -> 13         : /mnt/ext2/2+         -> /mnt/ext2/2++
rename(2): 18         -> 18         : /mnt/ext2/7          -> /mnt/ext2/7+
rename(2): 14         -> 14         : /mnt/ext2/3+         -> /mnt/ext2/3++
rename(2): 16         -> 16         : /mnt/ext2/5++        -> /mnt/ext2/5+++ 🔥
rename(2): 11         -> 11         : /mnt/ext2/0          -> /mnt/ext2/0+
rename(2): 15         -> 15         : /mnt/ext2/4++        -> /mnt/ext2/4+++
rename(2): 20         -> 20         : /mnt/ext2/9+         -> /mnt/ext2/9++
[DONE] getdents(2) returned 0

rename(2) 前後の inode 番号とディレクトリエントリ名を出力している

+ の数が rename(2) された回数を指す
複数回 rename(2) されているディレクトリエントリが確認できる. 🔥 が 3回 rename されている、つまり、getdents(2) が 3回読み取っている

その他

rename(2) 前後で inode 番号は変わらない (先のブログでも検証済みですね)
ext2 で getdents(2) が返す inode の順番は降順/昇順でソートされてはいない
- 試験スクリプトは何度か実行しても同じ inode 順で結果を返す
- 「ランダム」と書くのも正確では無いだろう

ext3

-bash-4.2$ sudo make test filesystem=ext3
ls         /mnt/ext3 >/dev/null
rm -rf     /mnt/ext3/*
touch      /mnt/ext3/{0..9}
./getdents /mnt/ext3
rename(2): 19         -> 19         : /mnt/ext3/8          -> /mnt/ext3/8+
rename(2): 18         -> 18         : /mnt/ext3/7          -> /mnt/ext3/7+
rename(2): 14         -> 14         : /mnt/ext3/3          -> /mnt/ext3/3+
rename(2): 12         -> 12         : /mnt/ext3/1          -> /mnt/ext3/1+
rename(2): 13         -> 13         : /mnt/ext3/2          -> /mnt/ext3/2+
rename(2): 14         -> 14         : /mnt/ext3/3+         -> /mnt/ext3/3++
rename(2): 16         -> 16         : /mnt/ext3/5          -> /mnt/ext3/5+
rename(2): 19         -> 19         : /mnt/ext3/8+         -> /mnt/ext3/8++
rename(2): 17         -> 17         : /mnt/ext3/6          -> /mnt/ext3/6+
rename(2): 20         -> 20         : /mnt/ext3/9          -> /mnt/ext3/9+
rename(2): 13         -> 13         : /mnt/ext3/2+         -> /mnt/ext3/2++
rename(2): 14         -> 14         : /mnt/ext3/3++        -> /mnt/ext3/3+++ 🔥
rename(2): 18         -> 18         : /mnt/ext3/7+         -> /mnt/ext3/7++
rename(2): 17         -> 17         : /mnt/ext3/6+         -> /mnt/ext3/6++
rename(2): 11         -> 11         : /mnt/ext3/0          -> /mnt/ext3/0+
rename(2): 15         -> 15         : /mnt/ext3/4          -> /mnt/ext3/4+
rename(2): 12         -> 12         : /mnt/ext3/1+         -> /mnt/ext3/1++
[DONE] getdents(2) returned 0

ext2 と似ている結果を返す

ext4

-bash-4.2$ sudo make test filesystem=ext4
ls         /mnt/ext4 >/dev/null
rm -rf     /mnt/ext4/*
touch      /mnt/ext4/{0..9}
./getdents /mnt/ext4
rename(2): 14         -> 14         : /mnt/ext4/3          -> /mnt/ext4/3+
rename(2): 11         -> 11         : /mnt/ext4/0          -> /mnt/ext4/0+
rename(2): 15         -> 15         : /mnt/ext4/4          -> /mnt/ext4/4+
rename(2): 17         -> 17         : /mnt/ext4/6          -> /mnt/ext4/6+
rename(2): 14         -> 14         : /mnt/ext4/3+         -> /mnt/ext4/3++
rename(2): 20         -> 20         : /mnt/ext4/9          -> /mnt/ext4/9+
rename(2): 18         -> 18         : /mnt/ext4/7          -> /mnt/ext4/7+
rename(2): 17         -> 17         : /mnt/ext4/6+         -> /mnt/ext4/6++
rename(2): 13         -> 13         : /mnt/ext4/2          -> /mnt/ext4/2+
rename(2): 11         -> 11         : /mnt/ext4/0+         -> /mnt/ext4/0++
rename(2): 16         -> 16         : /mnt/ext4/5          -> /mnt/ext4/5+
rename(2): 18         -> 18         : /mnt/ext4/7+         -> /mnt/ext4/7++
rename(2): 17         -> 17         : /mnt/ext4/6++        -> /mnt/ext4/6+++ 🔥
rename(2): 19         -> 19         : /mnt/ext4/8          -> /mnt/ext4/8+
rename(2): 14         -> 14         : /mnt/ext4/3++        -> /mnt/ext4/3+++ 🔥 
rename(2): 12         -> 12         : /mnt/ext4/1          -> /mnt/ext4/1+
[DONE] getdents(2) returned 0

ext2, ext3 と似ている

やっぱり同じ系列のファイルシステムだからかなぁ. ファイル数変えたりしたら違いがでるだろうか

tmpfs

-bash-4.2$ sudo make test filesystem=tmpfs
ls         /mnt/tmpfs >/dev/null
rm -rf     /mnt/tmpfs/*
touch      /mnt/tmpfs/{0..9}
./getdents /mnt/tmpfs
rename(2): 23105      -> 23105      : /mnt/tmpfs/9         -> /mnt/tmpfs/9+
rename(2): 23104      -> 23104      : /mnt/tmpfs/8         -> /mnt/tmpfs/8+
rename(2): 23103      -> 23103      : /mnt/tmpfs/7         -> /mnt/tmpfs/7+
rename(2): 23102      -> 23102      : /mnt/tmpfs/6         -> /mnt/tmpfs/6+
rename(2): 23101      -> 23101      : /mnt/tmpfs/5         -> /mnt/tmpfs/5+
rename(2): 23100      -> 23100      : /mnt/tmpfs/4         -> /mnt/tmpfs/4+
rename(2): 23099      -> 23099      : /mnt/tmpfs/3         -> /mnt/tmpfs/3+
rename(2): 23098      -> 23098      : /mnt/tmpfs/2         -> /mnt/tmpfs/2+
rename(2): 23097      -> 23097      : /mnt/tmpfs/1         -> /mnt/tmpfs/1+
rename(2): 23096      -> 23096      : /mnt/tmpfs/0         -> /mnt/tmpfs/0+
[DONE] getdents(2) returned 0

tmpfs は全く違う挙動となった!

tmpfs は複数回 rename(2) されるディレクトリエントリがでてこない.
tmpfs で getdents(2) が返すエントリは、inode 番号を降順にソートした順番である

tmpfs はページキャッシュを利用して作られたファイルシステムなので、ブロックデバイスのファイルシステムとは全然違う戦略で inode (dentry) が管理されていることが推測できる

あとでソースを読もう

minix

-bash-4.2$ sudo make test filesystem=minix
gcc -std=c99 -Werror -Wall -O2 getdents.c -o getdents
ls         /mnt/minix >/dev/null
rm -rf     /mnt/minix/*
touch      /mnt/minix/{0..9}
./getdents /mnt/minix
rename(2): 2          -> 2          : /mnt/minix/0         -> /mnt/minix/0+
rename(2): 3          -> 3          : /mnt/minix/1         -> /mnt/minix/1+
rename(2): 4          -> 4          : /mnt/minix/2         -> /mnt/minix/2+
rename(2): 5          -> 5          : /mnt/minix/3         -> /mnt/minix/3+
rename(2): 6          -> 6          : /mnt/minix/4         -> /mnt/minix/4+
rename(2): 7          -> 7          : /mnt/minix/5         -> /mnt/minix/5+
rename(2): 8          -> 8          : /mnt/minix/6         -> /mnt/minix/6+
rename(2): 9          -> 9          : /mnt/minix/7         -> /mnt/minix/7+
rename(2): 10         -> 10         : /mnt/minix/8         -> /mnt/minix/8+
rename(2): 11         -> 11         : /mnt/minix/9         -> /mnt/minix/9+
rename(2): 2          -> 2          : /mnt/minix/0+        -> /mnt/minix/0++ 🔥
[DONE] getdents(2) returned 0

getdents(2) が返す結果は inode 番号の昇順でソートされている
0 だけ二度 rename(2) されている

readdir() nonatomicity (Theodore Ts'o) に linked-list での実装とあるから、そこらの実装がうっすら見える気がする

驚くべき結果を示した XFS

盛り上がりをみせる

f:id:hiboma:20180323194843g:plain

-bash-4.2$ sudo make test filesystem=xfs
ls         /mnt/xfs >/dev/null
rm -rf     /mnt/xfs/*
touch      /mnt/xfs/{0..9}
./getdents /mnt/xfs
rename(2): 67         -> 67         : /mnt/xfs/0           -> /mnt/xfs/0+
rename(2): 68         -> 68         : /mnt/xfs/1           -> /mnt/xfs/1+
rename(2): 69         -> 69         : /mnt/xfs/2           -> /mnt/xfs/2+
rename(2): 70         -> 70         : /mnt/xfs/3           -> /mnt/xfs/3+
rename(2): 71         -> 71         : /mnt/xfs/4           -> /mnt/xfs/4+
rename(2): 72         -> 72         : /mnt/xfs/5           -> /mnt/xfs/5+
rename(2): 73         -> 73         : /mnt/xfs/6           -> /mnt/xfs/6+
rename(2): 74         -> 74         : /mnt/xfs/7           -> /mnt/xfs/7+
rename(2): 75         -> 75         : /mnt/xfs/8           -> /mnt/xfs/8+
rename(2): 76         -> 76         : /mnt/xfs/9           -> /mnt/xfs/9+
rename(2): 67         -> 67         : /mnt/xfs/0+          -> /mnt/xfs/0++
rename(2): 68         -> 68         : /mnt/xfs/1+          -> /mnt/xfs/1++
rename(2): 69         -> 69         : /mnt/xfs/2+          -> /mnt/xfs/2++
rename(2): 70         -> 70         : /mnt/xfs/3+          -> /mnt/xfs/3++
rename(2): 71         -> 71         : /mnt/xfs/4+          -> /mnt/xfs/4++
rename(2): 72         -> 72         : /mnt/xfs/5+          -> /mnt/xfs/5++
rename(2): 73         -> 73         : /mnt/xfs/6+          -> /mnt/xfs/6++
rename(2): 74         -> 74         : /mnt/xfs/7+          -> /mnt/xfs/7++
rename(2): 75         -> 75         : /mnt/xfs/8+          -> /mnt/xfs/8++
rename(2): 76         -> 76         : /mnt/xfs/9+          -> /mnt/xfs/9++
rename(2): 67         -> 67         : /mnt/xfs/0++         -> /mnt/xfs/0+++
rename(2): 68         -> 68         : /mnt/xfs/1++         -> /mnt/xfs/1+++
rename(2): 69         -> 69         : /mnt/xfs/2++         -> /mnt/xfs/2+++
rename(2): 70         -> 70         : /mnt/xfs/3++         -> /mnt/xfs/3+++
rename(2): 71         -> 71         : /mnt/xfs/4++         -> /mnt/xfs/4+++
rename(2): 72         -> 72         : /mnt/xfs/5++         -> /mnt/xfs/5+++
rename(2): 73         -> 73         : /mnt/xfs/6++         -> /mnt/xfs/6+++
rename(2): 74         -> 74         : /mnt/xfs/7++         -> /mnt/xfs/7+++
rename(2): 75         -> 75         : /mnt/xfs/8++         -> /mnt/xfs/8+++
rename(2): 76         -> 76         : /mnt/xfs/9++         -> /mnt/xfs/9+++
rename(2): 67         -> 67         : /mnt/xfs/0+++        -> /mnt/xfs/0++++
rename(2): 68         -> 68         : /mnt/xfs/1+++        -> /mnt/xfs/1++++
rename(2): 69         -> 69         : /mnt/xfs/2+++        -> /mnt/xfs/2++++

... 略

rename(2): 74         -> 74         : /mnt/xfs/7+++++++++++ -> /mnt/xfs/7++++++++++++
rename(2): 75         -> 75         : /mnt/xfs/8+++++++++++ -> /mnt/xfs/8++++++++++++
rename(2): 76         -> 76         : /mnt/xfs/9+++++++++++ -> /mnt/xfs/9++++++++++++
getdents(2) returned EINVAL. Try to allocate a bigger buffer
getdents(2) returned EINVAL. Try to allocate a bigger buffer
getdents(2) returned EINVAL. Try to allocate a bigger buffer
getdents(2) returned EINVAL. Try to allocate a bigger buffer
getdents(2) returned EINVAL. Try to allocate a bigger buffer
getdents(2) returned EINVAL. Try to allocate a bigger buffer
getdents(2) returned EINVAL. Try to allocate a bigger buffer
getdents(2) returned EINVAL. Try to allocate a bigger buffer
rename(2): 67         -> 67         : /mnt/xfs/0++++++++++++ -> /mnt/xfs/0+++++++++++++
rename(2): 68         -> 68         : /mnt/xfs/1++++++++++++ -> /mnt/xfs/1+++++++++++++
rename(2): 69         -> 69         : /mnt/xfs/2++++++++++++ -> /mnt/xfs/2+++++++++++++
rename(2): 70         -> 70         : /mnt/xfs/3++++++++++++ -> /mnt/xfs/3+++++++++++++
rename(2): 71         -> 71         : /mnt/xfs/4++++++++++++ -> /mnt/xfs/4+++++++++++++
rename(2): 72         -> 72         : /mnt/xfs/5++++++++++++ -> /mnt/xfs/5+++++++++++++
rename(2): 73         -> 73         : /mnt/xfs/6++++++++++++ -> /mnt/xfs/6+++++++++++++
rename(2): 74         -> 74         : /mnt/xfs/7++++++++++++ -> /mnt/xfs/7+++++++++++++

... 略

rename(2): 73         -> 73         : /mnt/xfs/6+++++++++++++++ -> /mnt/xfs/6++++++++++++++++ 🔥
rename(2): 74         -> 74         : /mnt/xfs/7+++++++++++++++ -> /mnt/xfs/7++++++++++++++++ 🔥
rename(2): 75         -> 75         : /mnt/xfs/8+++++++++++++++ -> /mnt/xfs/8++++++++++++++++ 🔥
rename(2): 76         -> 76         : /mnt/xfs/9+++++++++++++++ -> /mnt/xfs/9++++++++++++++++ 🔥
rename(2): 67         -> 67         : /mnt/xfs/0++++++++++++++++ -> /mnt/xfs/0+++++++++++++++++ 🔥
[DONE] getdents(2) returned 0

おやぁ 🔥🔥🔥 明らかに「何度も読み込まれている」のがわかる結果

XFS で getdents(2) が返す inode 番号は inode が昇順でソートされている
何度も 0 〜 9 を繰り返し読み出すパターンを持つ

その他

getdents(2) returned EINVAL. Try to allocate a bigger buffer のログを出しているが検証コードに仕込んだデバッグログである. getdents(2) を呼ぶ際、事前に malloc(3) であてたバッファのサイズが小さい場合に出す

さらに驚くべき結果を示した Btrfs

あー !!!1

f:id:hiboma:20180323194849g:plain

-bash-4.2$ sudo make test filesystem=btrfs
ls         /mnt/btrfs >/dev/null
rm -rf     /mnt/btrfs/*
touch      /mnt/btrfs/{0..9}
./getdents /mnt/btrfs
rename(2): 257        -> 257        : /mnt/btrfs/0         -> /mnt/btrfs/0+
rename(2): 258        -> 258        : /mnt/btrfs/1         -> /mnt/btrfs/1+
rename(2): 259        -> 259        : /mnt/btrfs/2         -> /mnt/btrfs/2+
rename(2): 260        -> 260        : /mnt/btrfs/3         -> /mnt/btrfs/3+
rename(2): 261        -> 261        : /mnt/btrfs/4         -> /mnt/btrfs/4+
rename(2): 262        -> 262        : /mnt/btrfs/5         -> /mnt/btrfs/5+
rename(2): 263        -> 263        : /mnt/btrfs/6         -> /mnt/btrfs/6+
rename(2): 264        -> 264        : /mnt/btrfs/7         -> /mnt/btrfs/7+
rename(2): 265        -> 265        : /mnt/btrfs/8         -> /mnt/btrfs/8+
rename(2): 266        -> 266        : /mnt/btrfs/9         -> /mnt/btrfs/9+
rename(2): 257        -> 257        : /mnt/btrfs/0+        -> /mnt/btrfs/0++
rename(2): 258        -> 258        : /mnt/btrfs/1+        -> /mnt/btrfs/1++
rename(2): 259        -> 259        : /mnt/btrfs/2+        -> /mnt/btrfs/2++
rename(2): 260        -> 260        : /mnt/btrfs/3+        -> /mnt/btrfs/3++
rename(2): 261        -> 261        : /mnt/btrfs/4+        -> /mnt/btrfs/4++
rename(2): 262        -> 262        : /mnt/btrfs/5+        -> /mnt/btrfs/5++
rename(2): 263        -> 263        : /mnt/btrfs/6+        -> /mnt/btrfs/6++
rename(2): 264        -> 264        : /mnt/btrfs/7+        -> /mnt/btrfs/7++
rename(2): 265        -> 265        : /mnt/btrfs/8+        -> /mnt/btrfs/8++
rename(2): 266        -> 266        : /mnt/btrfs/9+        -> /mnt/btrfs/9++
rename(2): 257        -> 257        : /mnt/btrfs/0++       -> /mnt/btrfs/0+++
rename(2): 258        -> 258        : /mnt/btrfs/1++       -> /mnt/btrfs/1+++
rename(2): 259        -> 259        : /mnt/btrfs/2++       -> /mnt/btrfs/2+++
rename(2): 260        -> 260        : /mnt/btrfs/3++       -> /mnt/btrfs/3+++
rename(2): 261        -> 261        : /mnt/btrfs/4++       -> /mnt/btrfs/4+++
rename(2): 262        -> 262        : /mnt/btrfs/5++       -> /mnt/btrfs/5+++
rename(2): 263        -> 263        : /mnt/btrfs/6++       -> /mnt/btrfs/6+++
rename(2): 264        -> 264        : /mnt/btrfs/7++       -> /mnt/btrfs/7+++
rename(2): 265        -> 265        : /mnt/btrfs/8++       -> /mnt/btrfs/8+++
rename(2): 266        -> 266        : /mnt/btrfs/9++       -> /mnt/btrfs/9+++
rename(2): 257        -> 257        : /mnt/btrfs/0+++      -> /mnt/btrfs/0++++
rename(2): 258        -> 258        : /mnt/btrfs/1+++      -> /mnt/btrfs/1++++
rename(2): 259        -> 259        : /mnt/btrfs/2+++      -> /mnt/btrfs/2++++
rename(2): 260        -> 260        : /mnt/btrfs/3+++      -> /mnt/btrfs/3++++
rename(2): 261        -> 261        : /mnt/btrfs/4+++      -> /mnt/btrfs/4++++
rename(2): 262        -> 262        : /mnt/btrfs/5+++      -> /mnt/btrfs/5++++
rename(2): 263        -> 263        : /mnt/btrfs/6+++      -> /mnt/btrfs/6++++
rename(2): 264        -> 264        : /mnt/btrfs/7+++      -> /mnt/btrfs/7++++
rename(2): 265        -> 265        : /mnt/btrfs/8+++      -> /mnt/btrfs/8++++
rename(2): 266        -> 266        : /mnt/btrfs/9+++      -> /mnt/btrfs/9++++
rename(2): 257        -> 257        : /mnt/btrfs/0++++     -> /mnt/btrfs/0+++++
rename(2): 258        -> 258        : /mnt/btrfs/1++++     -> /mnt/btrfs/1+++++
rename(2): 259        -> 259        : /mnt/btrfs/2++++     -> /mnt/btrfs/2+++++
rename(2): 260        -> 260        : /mnt/btrfs/3++++     -> /mnt/btrfs/3+++++
rename(2): 261        -> 261        : /mnt/btrfs/4++++     -> /mnt/btrfs/4+++++
rename(2): 262        -> 262        : /mnt/btrfs/5++++     -> /mnt/btrfs/5+++++
rename(2): 263        -> 263        : /mnt/btrfs/6++++     -> /mnt/btrfs/6+++++
rename(2): 264        -> 264        : /mnt/btrfs/7++++     -> /mnt/btrfs/7+++++
rename(2): 265        -> 265        : /mnt/btrfs/8++++     -> /mnt/btrfs/8+++++
rename(2): 266        -> 266        : /mnt/btrfs/9++++     -> /mnt/btrfs/9+++++
rename(2): 257        -> 257        : /mnt/btrfs/0+++++    -> /mnt/btrfs/0++++++
rename(2): 258        -> 258        : /mnt/btrfs/1+++++    -> /mnt/btrfs/1++++++
rename(2): 259        -> 259        : /mnt/btrfs/2+++++    -> /mnt/btrfs/2++++++
rename(2): 260        -> 260        : /mnt/btrfs/3+++++    -> /mnt/btrfs/3++++++
rename(2): 261        -> 261        : /mnt/btrfs/4+++++    -> /mnt/btrfs/4++++++
rename(2): 262        -> 262        : /mnt/btrfs/5+++++    -> /mnt/btrfs/5++++++
rename(2): 263        -> 263        : /mnt/btrfs/6+++++    -> /mnt/btrfs/6++++++
rename(2): 264        -> 264        : /mnt/btrfs/7+++++    -> /mnt/btrfs/7++++++
rename(2): 265        -> 265        : /mnt/btrfs/8+++++    -> /mnt/btrfs/8++++++
rename(2): 266        -> 266        : /mnt/btrfs/9+++++    -> /mnt/btrfs/9++++++
rename(2): 257        -> 257        : /mnt/btrfs/0++++++   -> /mnt/btrfs/0+++++++
rename(2): 258        -> 258        : /mnt/btrfs/1++++++   -> /mnt/btrfs/1+++++++
rename(2): 259        -> 259        : /mnt/btrfs/2++++++   -> /mnt/btrfs/2+++++++
rename(2): 260        -> 260        : /mnt/btrfs/3++++++   -> /mnt/btrfs/3+++++++
rename(2): 261        -> 261        : /mnt/btrfs/4++++++   -> /mnt/btrfs/4+++++++
rename(2): 262        -> 262        : /mnt/btrfs/5++++++   -> /mnt/btrfs/5+++++++
rename(2): 263        -> 263        : /mnt/btrfs/6++++++   -> /mnt/btrfs/6+++++++
rename(2): 264        -> 264        : /mnt/btrfs/7++++++   -> /mnt/btrfs/7+++++++
rename(2): 265        -> 265        : /mnt/btrfs/8++++++   -> /mnt/btrfs/8+++++++
rename(2): 266        -> 266        : /mnt/btrfs/9++++++   -> /mnt/btrfs/9+++++++
rename(2): 257        -> 257        : /mnt/btrfs/0+++++++  -> /mnt/btrfs/0++++++++
rename(2): 258        -> 258        : /mnt/btrfs/1+++++++  -> /mnt/btrfs/1++++++++
rename(2): 259        -> 259        : /mnt/btrfs/2+++++++  -> /mnt/btrfs/2++++++++
rename(2): 260        -> 260        : /mnt/btrfs/3+++++++  -> /mnt/btrfs/3++++++++
rename(2): 261        -> 261        : /mnt/btrfs/4+++++++  -> /mnt/btrfs/4++++++++
rename(2): 262        -> 262        : /mnt/btrfs/5+++++++  -> /mnt/btrfs/5++++++++
rename(2): 263        -> 263        : /mnt/btrfs/6+++++++  -> /mnt/btrfs/6++++++++
rename(2): 264        -> 264        : /mnt/btrfs/7+++++++  -> /mnt/btrfs/7++++++++
rename(2): 265        -> 265        : /mnt/btrfs/8+++++++  -> /mnt/btrfs/8++++++++
rename(2): 266        -> 266        : /mnt/btrfs/9+++++++  -> /mnt/btrfs/9++++++++
rename(2): 257        -> 257        : /mnt/btrfs/0++++++++ -> /mnt/btrfs/0+++++++++
rename(2): 258        -> 258        : /mnt/btrfs/1++++++++ -> /mnt/btrfs/1+++++++++
rename(2): 259        -> 259        : /mnt/btrfs/2++++++++ -> /mnt/btrfs/2+++++++++
rename(2): 260        -> 260        : /mnt/btrfs/3++++++++ -> /mnt/btrfs/3+++++++++
rename(2): 261        -> 261        : /mnt/btrfs/4++++++++ -> /mnt/btrfs/4+++++++++
rename(2): 262        -> 262        : /mnt/btrfs/5++++++++ -> /mnt/btrfs/5+++++++++
rename(2): 263        -> 263        : /mnt/btrfs/6++++++++ -> /mnt/btrfs/6+++++++++
rename(2): 264        -> 264        : /mnt/btrfs/7++++++++ -> /mnt/btrfs/7+++++++++
rename(2): 265        -> 265        : /mnt/btrfs/8++++++++ -> /mnt/btrfs/8+++++++++
rename(2): 266        -> 266        : /mnt/btrfs/9++++++++ -> /mnt/btrfs/9+++++++++
rename(2): 257        -> 257        : /mnt/btrfs/0+++++++++ -> /mnt/btrfs/0++++++++++
rename(2): 258        -> 258        : /mnt/btrfs/1+++++++++ -> /mnt/btrfs/1++++++++++
rename(2): 259        -> 259        : /mnt/btrfs/2+++++++++ -> /mnt/btrfs/2++++++++++
rename(2): 260        -> 260        : /mnt/btrfs/3+++++++++ -> /mnt/btrfs/3++++++++++
rename(2): 261        -> 261        : /mnt/btrfs/4+++++++++ -> /mnt/btrfs/4++++++++++
rename(2): 262        -> 262        : /mnt/btrfs/5+++++++++ -> /mnt/btrfs/5++++++++++
rename(2): 263        -> 263        : /mnt/btrfs/6+++++++++ -> /mnt/btrfs/6++++++++++
rename(2): 264        -> 264        : /mnt/btrfs/7+++++++++ -> /mnt/btrfs/7++++++++++
rename(2): 265        -> 265        : /mnt/btrfs/8+++++++++ -> /mnt/btrfs/8++++++++++
rename(2): 266        -> 266        : /mnt/btrfs/9+++++++++ -> /mnt/btrfs/9++++++++++
rename(2): 257        -> 257        : /mnt/btrfs/0++++++++++ -> /mnt/btrfs/0+++++++++++
rename(2): 258        -> 258        : /mnt/btrfs/1++++++++++ -> /mnt/btrfs/1+++++++++++
rename(2): 259        -> 259        : /mnt/btrfs/2++++++++++ -> /mnt/btrfs/2+++++++++++
rename(2): 260        -> 260        : /mnt/btrfs/3++++++++++ -> /mnt/btrfs/3+++++++++++
rename(2): 261        -> 261        : /mnt/btrfs/4++++++++++ -> /mnt/btrfs/4+++++++++++
rename(2): 262        -> 262        : /mnt/btrfs/5++++++++++ -> /mnt/btrfs/5+++++++++++
rename(2): 263        -> 263        : /mnt/btrfs/6++++++++++ -> /mnt/btrfs/6+++++++++++
rename(2): 264        -> 264        : /mnt/btrfs/7++++++++++ -> /mnt/btrfs/7+++++++++++
rename(2): 265        -> 265        : /mnt/btrfs/8++++++++++ -> /mnt/btrfs/8+++++++++++
rename(2): 266        -> 266        : /mnt/btrfs/9++++++++++ -> /mnt/btrfs/9+++++++++++
rename(2): 257        -> 257        : /mnt/btrfs/0+++++++++++ -> /mnt/btrfs/0++++++++++++
rename(2): 258        -> 258        : /mnt/btrfs/1+++++++++++ -> /mnt/btrfs/1++++++++++++
rename(2): 259        -> 259        : /mnt/btrfs/2+++++++++++ -> /mnt/btrfs/2++++++++++++
rename(2): 260        -> 260        : /mnt/btrfs/3+++++++++++ -> /mnt/btrfs/3++++++++++++
rename(2): 261        -> 261        : /mnt/btrfs/4+++++++++++ -> /mnt/btrfs/4++++++++++++
rename(2): 262        -> 262        : /mnt/btrfs/5+++++++++++ -> /mnt/btrfs/5++++++++++++
rename(2): 263        -> 263        : /mnt/btrfs/6+++++++++++ -> /mnt/btrfs/6++++++++++++
rename(2): 264        -> 264        : /mnt/btrfs/7+++++++++++ -> /mnt/btrfs/7++++++++++++
rename(2): 265        -> 265        : /mnt/btrfs/8+++++++++++ -> /mnt/btrfs/8++++++++++++ 
rename(2): 266        -> 266        : /mnt/btrfs/9+++++++++++ -> /mnt/btrfs/9++++++++++++ 
getdents(2) returned EINVAL. Try to allocate a bigger buffer
getdents(2) returned EINVAL. Try to allocate a bigger buffer
getdents(2) returned EINVAL. Try to allocate a bigger buffer
getdents(2) returned EINVAL. Try to allocate a bigger buffer
getdents(2) returned EINVAL. Try to allocate a bigger buffer
getdents(2) returned EINVAL. Try to allocate a bigger buffer
getdents(2) returned EINVAL. Try to allocate a bigger buffer
getdents(2) returned EINVAL. Try to allocate a bigger buffer
rename(2): 257        -> 257        : /mnt/btrfs/0++++++++++++ -> /mnt/btrfs/0+++++++++++++ 
rename(2): 258        -> 258        : /mnt/btrfs/1++++++++++++ -> /mnt/btrfs/1+++++++++++++ 

... 略

rename(2): 259        -> 259        : /mnt/btrfs/2+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -> /mnt/btrfs/2++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
rename(2): 260        -> 260        : /mnt/btrfs/3+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -> /mnt/btrfs/3++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
rename(2): 261        -> 261        : /mnt/btrfs/4+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -> /mnt/btrfs/4++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
rename(2): 262        -> 262        : /mnt/btrfs/5+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -> /mnt/btrfs/5++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
rename(2): 263        -> 263        : /mnt/btrfs/6+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -> /mnt/btrfs/6++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
rename(2): 264        -> 264        : /mnt/btrfs/7+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -> /mnt/btrfs/7++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
rename(2): 265        -> 265        : /mnt/btrfs/8+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -> /mnt/btrfs/8++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
rename(2): 266        -> 266        : /mnt/btrfs/9+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -> /mnt/btrfs/9++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
rename: File name too long 🔥
make: *** [test] エラー 1

XFS と似た挙動を示すがループは止まらず rename(2) が ENAMETOOLONG = File name too long で止まる
- + が増えすぎてディレクトリエントリの最大ファイル名長 (≠ パスの長さ) を超えているためだ
getdents(2) が返す inode は昇順にソートされている

やってくれるじゃないか

Btrfs の追試

もしかして、ファイル名の長さを変えないように rename(2) すると File name too long を回避して、無限ループするんでなかろか? と思い別の実装でテストしたところ ...

f:id:hiboma:20180322182444g:plain

あららーループしたね. Btrfs だと find + mv で無限ループ起こせる?

まとめ

getdents(2) の最中に rename(2) するとファイルシステムの実装に依存した挙動をを示すことは、実験結果の比較をもって明らかにできた。POSIXで未定義ってのはこういうことか
各ファイルシステムでのディレクトリエントリの実装がまで追えるといいんだけど、力尽きているので。次の回にしよう
実験のパラメータとして考慮しなかったものがあり、挙動を変えうるかどうか検討していない
- mkfs や mount オプションに手を入れていない
- ファイル数を変えた場合
- ファイル以外の場合 (ディレクトリ、ソケット等)

大前提として getdents(2) のバッファサイズを恣意的に小さくした特異なケースだったことを忘れないでほしい

感想

Btrfs は後から追加したのだけど「えーまさか 😮」という結果となった
恣意的かつ特殊なエッジケースではあるが、システムコールの呼び出しレベルで「重複した読み出し」は発生しうるので、上位のライブラリ・アプリケーションで回避策を講じなければ同様の現象に遭遇しうるだろう
readdir(3) は 「ディレクトリエントリをストリームとして扱う」 という、にんげんのメンタルモデルに優しい抽象化したインタフェースを提供してくれているが、抽象化の覆いがはずれて、中の実装がぽろりしてしまうようなことあるんだなと勉強になった. 「未定義」というのはさもあらん
find(1) も同様に思う

hibomaの日記

ディレクトリを getdents(2) しつつ rename(2) を繰り返す実験

このエントリで取り扱うお題

POSIX を確認する

先にまとめ

システムコールの理解

man 2 getdents

find のバッファサイズ

man 2 rename

実験

実験の設計

実験のコード

実験する VM

実験の実施手順

セットアップ

実行

実験結果

ext2

ext3

ext4

tmpfs

minix

驚くべき結果を示した XFS

さらに驚くべき結果を示した Btrfs

Btrfs の追試

まとめ

感想

このエントリで取り扱うお題

POSIX を確認する

先にまとめ

システムコールの理解

man 2 getdents

find のバッファサイズ

man 2 rename

実験

実験の設計

実験のコード

実験する VM

実験の実施手順

セットアップ

実行

実験結果

ext2

ext3

ext4

tmpfs

minix

驚くべき結果を示した XFS

さらに驚くべき結果を示した Btrfs

Btrfs の 追試

まとめ

感想

Btrfs の追試