パイプ経由のデータを、連続するhead -n1に読ませるとこうなった

1行16バイト（LF含む）のデータを大量に出力し、連続するheadコマンドにパイプ経由で読み込ませてみました。

$ seq -w 100000000000000 | head -n1
000000000000001
$
$ seq -w 100000000000000 | (head -n1; head -n1)
000000000000001
000000000000513
$ 
$ seq -w 100000000000000 | while :; do head -n1; sleep 1; done
000000000000001
000000000000513
000000000001025
000000000001537
000000000002049
^C
$

結果だけ見ると、8K単位（1行16バイト x 512行）で分割された複数の擬似ファイルに対して、head -n1を適用しているように見えます。

パイプのバッファサイズが関係しているのかな？と思い、パイプに1バイトずつwrite(2)するソースコードを書いて実行したところ…

mypipe.c

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
    int fdp[2];

    if(pipe(fdp)<0){
        perror("pipe\n");
        exit(1);
    }   

    char c='a';
    for(long i=1; ; i++){
        write(fdp[1],&c,1);
        printf("i = %ld\n", i); 
    }   

    return 0;
}

65536バイト（64KB）をwrite(2)した直後のwrite(2)でブロッキングが発生したので、パイプサイズは64KBらしいです。

実行結果

$ gcc -Wall -std=c99 -o mypipe ./mypipe.c; ./mypipe
i = 1
i = 2
i = 3
...
i = 65534
i = 65535
i = 65536
(出力がここでサスペンド)

パイプのバッファサイズはあまり関係なさそう。ということで、headコマンドが内部で8k単位でバッファリングしているのでは？と推測し、headコマンドのソースコードを読んでみることにしました。

まず、使用しているコマンドと同じバージョンのソースを入手する必要があります。おのれの目の前のheadコマンドは、GNU coreutilsの8.23らしい。

head --version
head (GNU coreutils) 8.23
Copyright (C) 2014 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Written by David MacKenzie and Jim Meyering.

Linuxのコマンドのソースコードは、gnu.orgから入手可能です。今回は、coreutils-8.23.tar.xzをダウンロードしました。

head.cを読む

オープンソースのハイレベルなソースコードが、このおんどれに読めるんかい？（オープンソースのコードを読むのは今回がはじめて）とダメ元な気分でしたが、8.23のhead.c単体は1070行と短めなので、カーネルやシェルのソースコードと比べると敷居が低くていいですね。

まず、main関数を見つけて、ほっとします。

src/head.c#main()

 901 int
 902 main (int argc, char **argv)
 903 {
 904   enum header_mode header_mode = multiple_files;
 905   bool ok = true;
 906   int c;
 907   size_t i;
 908 
 909   /* Number of items to print. */
 910   uintmax_t n_units = DEFAULT_NUMBER;
 911 
 912   /* If true, interpret the numeric argument as the number of lines.
 913      Otherwise, interpret it as the number of bytes.  */
 914   bool count_lines = true;
 915 
 916   /* Elide the specified number of lines or bytes, counting from
 917      the end of the file.  */
 918   bool elide_from_end = false;
 919 
 920   /* Initializer for file_list if no file-arguments
 921      were specified on the command line.  */
 922   static char const *const default_file_list[] = {"-", NULL};
 923   char const *const *file_list;
...
1056   file_list = (optind < argc
1057                ? (char const *const *) &argv[optind]
1058                : default_file_list);
...

ファイルリストの作成

count_lines（914行目）はフラグ変数で、オプションで行数指定（-nNumber）された場合はtrue、バイト数指定（-cNumber）された場合はfalseがセットされます。今回はtrueですね。

file_list（1056 - 1058行目）には、オプション指定の後続で指定されたファイルパス（の先頭のファイルパスの先頭文字を指すポインタへの）ポインタが代入されます。ファイルパスが指定されていない場合は、default_file_listが代入されます。

今回は、ファイルパスを指定せずパイプ経由で読み込んだため、ファイルリストには、default_file_list（以下）が使用されます。先頭エントリの「-」（ハイフン）は、標準入力を意味します。

src/head.c#main()

 920   /* Initializer for file_list if no file-arguments
 921      were specified on the command line.  */
 922   static char const *const default_file_list[] = {"-", NULL};

file_listの各エントリに対して、head_file()を適用しています。今回は、エントリは「-」のみです。

src/head.c#main()

1063   for (i = 0; file_list[i]; ++i)
1064     ok &= head_file (file_list[i], n_units, count_lines, elide_from_end);

オプション解析は長いので飛ばしましたが、n_unitsには、オプション-nNumberで指定したNumberが代入されます。

前述したようにcount_linesはフラグ変数で、オプション-nNumerを指定された場合にtrueがセットされます（count_linesって名前、行数っぽいよな…）。

elide_from_endもフラグ変数で、-n-Numberのように負数を指定された場合にtrueとなります。負数を指定すると、「最後のNumber行を除いた、すべての行」を出力します。

$ printf "aaa\nbbb\nccc\n" | head -n-1
aaa
bbb
$

src/head.c#main()

1064     ok &= head_file (file_list[i], n_units, count_lines, elide_from_end);

戻り値を変数okに代入していますが、複合代入演算子&=を使用しているので、複数のファイルリストを処理する中で、1件でもエラーが発生した場合、コマンドの終了ステータスをエラーとするようですね。

head_file()

ここではファイル内容の解析はやらずに、ファイルを開いてファイルディスクリプタを取得し、ファイルディスクリプタを解析部のhead()に渡すようです。

src/head.c#head_file()

 834 static bool
 835 head_file (const char *filename, uintmax_t n_units, bool count_lines,
 836            bool elide_from_end)
 837 {
 838   int fd;
 839   bool ok;
 840   bool is_stdin = STREQ (filename, "-");
 841 
 842   if (is_stdin)
 843     {
 844       have_read_stdin = true;
 845       fd = STDIN_FILENO;
 846       filename = _("standard input");
 847       if (O_BINARY && ! isatty (STDIN_FILENO))
 848         xfreopen (NULL, "rb", stdin);
 849     }
 850   else
 851     {
 852       fd = open (filename, O_RDONLY | O_BINARY);
 853       if (fd < 0)
 854         {
 855           error (0, errno, _("cannot open %s for reading"), quote (filename     ));
 856           return false;
 857         }
 858     }
 859 
 860   ok = head (filename, fd, n_units, count_lines, elide_from_end);
 861   if (!is_stdin && close (fd) != 0)
 862     {
 863       error (0, errno, _("failed to close %s"), quote (filename));
 864       return false;
 865     }
 866   return ok;
 867 }

上位から渡されたファイル名は「-」ですが、STREQマクロで「"-"」と比較した結果をis_stdinに代入します。やはり、「-」は標準入力を意味するようです。bashの「-」が標準入力を示す記号であるのと一致しますね。

src/head.c#head_file()

 840   bool is_stdin = STREQ (filename, "-");

STREQマクロは、strcmp(3)のラッパです。

src/system.h

#define STREQ(a, b) (strcmp (a, b) == 0)

head()

elide_from_end == falseなので、804～827行は読み飛ばします。count_linesは、オプション-nNumberが指定された時にtrueなので、head_lines()（829行目）を呼び出します。

src/head.c#head()

 796 static bool
 797 head (const char *filename, int fd, uintmax_t n_units, bool count_lines,
 798       bool elide_from_end)
 799 {
 800   if (print_headers)
 801     write_header (filename);
 802 
 803   if (elide_from_end)
 804     {
...
 827     }
 828   if (count_lines)
 829     return head_lines (filename, fd, n_units);
 830   else
 831     return head_bytes (filename, fd, n_units);
 832 }

head_lines()

核心に近づいてきました。

src/head.c#head_lines()

 759 static bool
 760 head_lines (const char *filename, int fd, uintmax_t lines_to_write)
 761 {
 762   char buffer[BUFSIZ];
 763 
 764   while (lines_to_write)
 765     {
 766       size_t bytes_read = safe_read (fd, buffer, BUFSIZ);
 767       size_t bytes_to_write = 0;
 768 
 769       if (bytes_read == SAFE_READ_ERROR)
 770         {
 771           error (0, errno, _("error reading %s"), quote (filename));
 772           return false;
 773         }
 774       if (bytes_read == 0)
 775         break;
 776       while (bytes_to_write < bytes_read)
 777         if (buffer[bytes_to_write++] == '\n' && --lines_to_write == 0)
 778           {
 779             off_t n_bytes_past_EOL = bytes_read - bytes_to_write;
 780             /* If we have read more data than that on the specified number
 781                of lines, try to seek back to the position we would have
 782                gotten to had we been reading one byte at a time.  */
 783             if (lseek (fd, -n_bytes_past_EOL, SEEK_CUR) < 0)
 784               {
 785                 struct stat st;
 786                 if (fstat (fd, &st) != 0 || S_ISREG (st.st_mode))
 787                   elseek (fd, -n_bytes_past_EOL, SEEK_CUR, filename);
 788               }
 789             break;
 790           }
 791       xwrite_stdout (buffer, bytes_to_write);
 792     }
 793   return true;
 794 }

おそらく、以下のbufferが、headコマンドの内部バッファではないか。パイプからの読み込み時は、このBUFSIZ単位で読み込んでいるのではとアタリをつけます。このBUFSIZが8192であれば、推測通りなのですが。

src/head.c#head_lines()

 762   char buffer[BUFSIZ];

似たような変数名が多いので、整理しますと

• bytes_read　... 入力元から読み込んだバイトサイズ（変化しない）
• bytes_to_write　...　これから標準出力するバイトサイズ（0からインクリメントする）
• lines_to_write　...　オプション-nNumberのNumber行数（Numberからデクリメントする）

なるほど、O_to_Verbは、「これからVerbするO」という意味の命名なのですね。その反対、「すでにVerbしたO」は、日本人的にはO_already_受動態が分かりやすいかなあ。bytes_already_writtenのような。それは置いといて。

制御構造を分かりやすくするため、フォーカスポイント以外を畳んでしまいます。

src/head.c#head_lines()

 764   while (lines_to_write)
 765     {
 766       size_t bytes_read = safe_read (fd, buffer, BUFSIZ);
 767       size_t bytes_to_write = 0;
...
 774       if (bytes_read == 0)
 775         break;
 776       while (bytes_to_write < bytes_read)
 777         if (buffer[bytes_to_write++] == '\n' && --lines_to_write == 0)
 778           {
...
 789             break;
 790           }
 791       xwrite_stdout (buffer, bytes_to_write);
 792     }
 793   return true;

入力元からBUFSIZサイズ分を中間バッファに読み込み、lines_to_writeの行数分のデータを、まるごとxwrite_stdout()に渡すイメージでしょうか。

head.c#head_lines()

 777         if (buffer[bytes_to_write++] == '\n' && --lines_to_write == 0)

ここがキモですが、改行を見つけるたびにlines_to_writeをデクリメントしています。つまり、「指定行数番目の最後の改行」を見つけた時点で、このwhileループを抜けるようです。これはまさに、headコマンドの行数指定時の挙動ですよね。

気になったのは、最終行の改行を見つけた時に、読み込むデータがまだバッファ内に残っている場合、lseek(2)でファイルポインタのオフセット位置を、write用カーソル位置に同期していることです。

src/head.c#head_lines()

 779             off_t n_bytes_past_EOL = bytes_read - bytes_to_write;
 780             /* If we have read more data than that on the specified number
 781                of lines, try to seek back to the position we would have
 782                gotten to had we been reading one byte at a time.  */
 783             if (lseek (fd, -n_bytes_past_EOL, SEEK_CUR) < 0)
 784               {
 785                 struct stat st;
 786                 if (fstat (fd, &st) != 0 || S_ISREG (st.st_mode))
 787                   elseek (fd, -n_bytes_past_EOL, SEEK_CUR, filename);
 788               }

後続処理を見てみると、fdに対する操作は、以下でclose(2)するだけだし。

src/head.c#head_file()

 861   if (!is_stdin && close (fd) != 0)

コメントを訳してみます。仮定法過去完了の条件節の倒置（ifの省略）って、懐かしいんですけど…。

/* If we have read more data than that on the specified number
   of lines, try to seek back to the position we would have
   gotten to had we been reading one byte at a time.  */

（訳：指定行数より多くの行を読み込んだ場合は、ファイル位置を、1バイトずつ読み込んだ時に到達するべき位置と同じ位置に戻しておくこと）

えーと、理由が書いてない...。

safe_read()

次に進む前に、標準入力からの読み込む処理、head.c766行目のsafe_read()の定義を確認します。safe_rwという識別子がコンパイル時に置換されたのがsafe_readという識別子です。

lib/safe-read.c#safe_read()

 46 # define safe_rw safe_read
 47 # define rw read
 48 # undef const
 49 # define const /* empty */
 50 #endif
 51 
 52 /* Read(write) up to COUNT bytes at BUF from(to) descriptor FD, retrying if
 53    interrupted.  Return the actual number of bytes read(written), zero for E    OF,
 54    or SAFE_READ_ERROR(SAFE_WRITE_ERROR) upon error.  */
 55 size_t
 56 safe_rw (int fd, void const *buf, size_t count)
 57 {
 58   /* Work around a bug in Tru64 5.1.  Attempting to read more than
 59      INT_MAX bytes fails with errno == EINVAL.  See
 60      <http://lists.gnu.org/archive/html/bug-gnu-utils/2002-04/msg00010.html>    .
 61      When decreasing COUNT, keep it block-aligned.  */
 62   enum { BUGGY_READ_MAXIMUM = INT_MAX & ~8191 };
 63 
 64   for (;;)
 65     {
 66       ssize_t result = rw (fd, buf, count);
 67 
 68       if (0 <= result)
 69         return result;
 70       else if (IS_EINTR (errno))
 71         continue;
 72       else if (errno == EINVAL && BUGGY_READ_MAXIMUM < count)
 73         count = BUGGY_READ_MAXIMUM;
 74       else
 75         return result;
 76     }
 77 }

これは、指定バイトサイズ分、read(2)するラッパ関数ですね（rwという識別子もコンパイル時にreadに置換されます）。

72～73行。(7FFFE000 INT_MAX & ~8191)は、16進数で0x7fffe000ですが、EINVAL検知時、指定バイトサイズが0x7fffe000を超えていた場合、0x7fffe000（2^31-1の下位13ビットを落とした値）に調整されるようです。2^13=8Kの倍数となりますが、この手のアラインメントの即値については、考えても仕方ないので、まあそういうものなんだなと受け入れるしかないですね。

diff 2.8 large file read fails for Tru64 5.1

xwrite_stdout()

whileループ内で呼び出されている、バッファの内容を標準出力する関数です。

src/head.c#xwrite_stdout()

 167 /* Write N_BYTES from BUFFER to stdout.
 168    Exit immediately on error with a single diagnostic.  */
 169 
 170 static void
 171 xwrite_stdout (char const *buffer, size_t n_bytes)
 172 {
 173   if (n_bytes > 0 && fwrite (buffer, 1, n_bytes, stdout) < n_bytes)
 174     {
 175       clearerr (stdout); /* To avoid redundant close_stdout diagnostic.  */
 176       error (EXIT_FAILURE, errno, _("error writing %s"),
 177              quote ("standard output"));
 178     }
 179 }

bufferで指定したバッファの先頭から、1バイト*n_bytes個分のデータ（つまりn_bytesバイトのデータ）をfwrite(3)しています。

BUFSIZ

headコマンドの固定長の内部バッファは、サイズがBUFSIZでしたが、これのサイズを突き止めるのが今回の本題でした。

ここからがgrep祭り。

/usr/include/stdio.h

125 /* Default buffer size.  */
126 #ifndef BUFSIZ
127 # define BUFSIZ _IO_BUFSIZ
128 #endif

/usr/include/libio.h

 43 #define _IO_BUFSIZ _G_BUFSIZ

/usr/include/_G_config.h

 56 #define _G_BUFSIZ 8192

ありました。最初の読み通り、headコマンドの内部バッファのサイズは8192バイトのようです。

まとめ

GNU Coreutilesのソースコードリーディングは、コード行数が少なめなのと、日常的に使用しているプログラムなので動作がイメージしやすいので、コードリーディング入門の素材として使えますね。オープンソースのコードを読んだという自信もつきます。