#navi_header|C言語系|

お題：locate(1)がデータファイルを構築する仕組みを追跡せよ。

先に結末：追跡しきれませんでした。bigramや文字列差分を組み合わせた圧縮そして展開のコード、自分の理解力とソース読解力では太刀打ちできませんでした｡ﾟ(ﾟ´Д｀ﾟ)ﾟ｡

#more||

* "/etc/weekly"からlocate用データファイル作成処理をkickするところまで

"man 1 locate"
 SYNOPSIS
      locate [-d dbpath] pattern
 ...
 FILES
      /var/db/locate.database       Default database
      /usr/libexec/locate.updatedb  Script to update database.
 
 SEE ALSO
      find(1), fnmatch(3), weekly.conf(5)

NetBSD1.6の場合、locateによるDB構築自体は "/etc/weekly" で行われる(NetBSD1.6の場合システムのcrontabは/etc/crontabではなく、rootユーザのcrontabとして "/var/cron/tabs/root" に記述されている)。
"/etc/weekly"より：
 if checkyesno rebuild_locatedb; then
         echo ""
         if [ -f /var/db/locate.database ]; then
                 echo "Rebuilding locate database:"
                 chmod 644 /var/db/locate.database
                 chown nobody:nobody /var/db/locate.database
                 nice -5 su -m nobody -c /usr/libexec/locate.updatedb 2>/dev/null
                 chown root:wheel /var/db/locate.database
         else
                 echo "Not rebuilding locate database; no /var/db/locate.database"
         fi
 fi
"rebuild_locatedb"については、"/etc/weekly.conf"にて設定する。システムデフォルトは "/etc/defaults/weekly.conf" でYESに設定されている。BSD系の慣習で、"/etc/weekly.conf"の中では "/etc/defaults/weekly.conf" をまず取り込み、その後デフォルト定義を上書きする形で設定する。詳細は "man 5 weekly.conf" 参照。
とまれ、流れとしては "/etc/weekly" より
 nice -5 su -m nobody -c /usr/libexec/locate.updatedb 2>/dev/null
これにより、nobodyユーザにて "/usr/libexec/locate.updatedb" が実行されることが分かる。

"/usr/libexec/locate.updatedb"はシェルスクリプトになっており、主要部分を抜き出すと次のような流れになる。
#pre||>
SRCHPATHS="/"                           # directories to be put in the database
LIBDIR="/usr/libexec"                   # for subprograms
FCODES="/var/db/locate.database"        # the database

FILELIST=`mktemp -t locate.list` || exit 1

find -s $SRCHPATHS \( \
    ...
    \) -a -prune -o -print \
        >> "$FILELIST"

BIGRAMS=`$LIBDIR/locate.bigram <"$FILELIST"`

if [ -z "$BIGRAMS" ]; then
        echo 'locate: updatedb failed' >&2
else
        $LIBDIR/locate.code "$BIGRAMS" <"$FILELIST" >"$FCODES"
        chmod 644 "$FCODES"
fi
||<
まずmktempでファイル一覧を保存する一時ファイルを作る。
 FILELIST=`mktemp -t locate.list` || exit 1
続いてfindコマンドでシステムのファイル一覧を作成し、FILELISTで指定されたファイル名に出力しておく。

その後、"$LIBDIR/locate.bigram" = "/usr/libexec/locate.bigram" にFILELISTを食わせ、出力をBIGRAMSに保存する。
 BIGRAMS=`$LIBDIR/locate.bigram <"$FILELIST"`

BIGRAMSが空でなければ、"$LIBDIR/locate.code" = "/usr/libexec/locate.code" を実行する。
 $LIBDIR/locate.code "$BIGRAMS" <"$FILELIST" >"$FCODES"
 chmod 644 "$FCODES"
実行結果は"FCODES"、つまり "/var/db/locate.database" に保存される。
ここで "/usr/libexec/locate.updatedb"は"/etc/weekly"によりnobodyユーザで実行されることを思い出す。
すると "/var/db/locate.database" もnobodyユーザで操作出来ねばならない。それが、"/etc/weekly" スクリプトでの次の処理で実現されている。
 chmod 644 /var/db/locate.database
 chown nobody:nobody /var/db/locate.database
 nice -5 su -m nobody -c /usr/libexec/locate.updatedb 2>/dev/null
 chown root:wheel /var/db/locate.database
つまり一旦所有者とグループをnobodyにchownして locate.updatedb を実行し、終了後rootオーナ, wheelグループに戻している。

ここでlocateのデータベースを作成するプログラムを特定出来たので、ソースコードの探索に進む。

 $ locate locate.bigram
 /usr/libexec/locate.bigram
 /usr/src/usr.bin/locate/bigram/locate.bigram.c
 $ locate locate.code
 /usr/libexec/locate.code
 /usr/src/usr.bin/locate/code/locate.code.c

* "locate.bigram"によるファイルリストのbigram上位抽出

"/usr/src/usr.bin/locate/" ディレクトリの構成は次のようになっている。
 /usr/src/usr.bin/locate/
     Makefile
     Makefile.inc
     bigram/
         Makefile
         locate.bigram.c
     code/
         Makefile
         locate.code.c
     locate/
         Makefile
         locate.1
         locate.c
         locate.h
         pathnames.h
         updatedb.sh

まずは順番通り、locate.bigram.cを見てみる。

・・・ここで詳しく自力で解説を書いてみようとしたが、bigramの処理部分など解説を書くのが大変・・・というか理解し切れたか不安な箇所が多数あるので、ソースコードの解説については「デーモン君のソース探検」にお譲りします。

処理内容としては、
 /usr/bin/foobar
 /usr/bin/barbaz
 /usr/lib/xxxyyy
 ...
というようなファイル名のリストを一行ずつ読み込み、直前に読んだ行との差分を抽出、そこから2文字ずつ切り出していき、頻出する上位128位までの2文字を標準出力に出力している。

頑張って理解出来た範囲で解説を試みると・・・

 char *cp;
 char *oldpath = buf1, *path = buf2;
 struct bigram *bg;
 int i;
メイン関数の冒頭でまずバッファなどを初期化している。buf1, buf2というのはlocate.bigram.c内でのグローバルシンボルで、以下のように定義されている。
 static char buf1[MAXPATHLEN] = " ";
 static char buf2[MAXPATHLEN];
つまり、初期状態では
 char *path = buf2;
 char *oldpath = buf1 = " "(空白文字一字の文字列へのポインタ)
となっている。(whileループの中でややこしくなるので、あえて初期状態を整理しておいた。)

 struct bigram *bg
についてはbigramを表現する構造体へのポインタ。この辺は本を参照。

メインとなるwhileループを見てみる。
#pre||>
while ( fgets ( path, sizeof(buf2), stdin ) != NULL ) {

    /* skip longest common prefix */
    for ( cp = path; *cp == *oldpath; cp++, oldpath++ )
        if ( *oldpath == '\0' )
            break;

    /*
     * output post-residue bigrams only
     */
    for(; cp[0] != '\0' && cp[1] != '\0'; cp += 2)
        add_bigram((u_char)cp[0], (u_char)cp[1]);

    if (path == buf1)               /* swap pointers */
        path = buf2, oldpath = buf1;
    else
        path = buf1, oldpath = buf2;
}
||<
まず標準入力から1行読み、pathに格納する。一番最初は、path = buf2なのでbuf2に格納されている。
続いてこのforループ：、
    for ( cp = path; *cp == *oldpath; cp++, oldpath++ )
        if ( *oldpath == '\0' )
            break;
2回目以降のループでは後述の通り、oldpathは一つ前で読んだバッファへのポインタになる。従って、今回読んだバッファと、前回読んだバッファとを比較し、違う箇所が出てくるまで cp ポインタを進める、という処理になっている。
 oldbuf = "ABCDE"
 path   = "ABCDEFG"
だったら、"F"の文字までcpが進むことになる。

"locate.bigram.c"独特（？）なのが次のforループ：
 for(; cp[0] != '\0' && cp[1] != '\0'; cp += 2)
     add_bigram((u_char)cp[0], (u_char)cp[1]);
cpは前の行と異なる箇所まで進んでいる。そしてこのNULL文字判定は、異なる箇所から2文字続いていた時にadd_bigram()を呼ぶようになっている。
 例1:
 oldbuf = "abc"
 path   = "abcd"
 → cpは"d"まで進む。cp[0] != '\0', しかし cp[1] == '\0' になるので、add_bigramは通らない。
 
 例2:
 oldbuf = "abc"
 path   = "abcde"
 → cpは"d"まで進む。cp[0] != '\0', cp[1] != '\0' になるので、add_bigramは通る。

最後にバッファの入れ替えとなる。
    if (path == buf1)               /* swap pointers */
        path = buf2, oldpath = buf1;
    else
        path = buf1, oldpath = buf2;
最初は
 oldpath = buf1
 path    = buf2 (fgetsで読み込んだ最初の行)
なのでelse節を通る。
 → oldpath = buf2 (fgetsで読み込んだ最初の行)
 → path    = buf1
ここでwhileの先頭に戻り、pathに対してfgetsされ、次の状態になる。
 oldpath = buf2 (fgetsで読み込んだ最初の行)
 path    = buf1 (fgetsで読み込んだ2行目)
２回目はpath == buf1なので、if節を通る。
 → oldpath = buf1 (fgetsで読み込んだ2行目)
 → path    = buf2 (fgetsで読み込んだ最初の行)
そしてwhileの先頭に戻りfgetsされると・・・
 oldpath = buf1 (fgetsで読み込んだ2行目)
 path    = buf2 (fgetsで読み込んだ3行目)
となり、これによりbuf1/buf2を使い回しつつ、path/oldpathで「現在読み込んだ行」「一つ前に読み込んだ行」にアクセスすることが出来るようになっている。

ここまで解析した時点で、実際にファイル一覧に相当するテキストファイルを手作りして、処理させてみる。

まず、前の行との差分以降が1文字しか異ならない、あるいは前の行より短いデータを用意する。
 $ cat nobigram.dat
 a
 ab
 abc
 abcd
 h
 hi
 hij
 hijk
 hijkl
 hijk
 hij
 hi
 h
差分以降が2文字以上無いとbigramとして検出されない。よって、予想ではこのデータでは1文字もbigramとして検出されないはずである。
 $ /usr/libexec/locate.bigram < nobigram.dat
 $ echo $?
 0
予想通り1文字も出力されていない=bigramとして検出されていない。念のためプロセスの戻り値も見てみたが、正常である。

続いて差分以降が2文字以上あるデータファイルを用意してみる。
 $ cat bigram.dat
 a
 abc
 abcd
 abcdefg
 abcDE
 hi
予想では、"bc", "ef", "DE", さらに"hi"も検出されるはずである。
 abcDE
 hi
 → 差分の位置は0文字目になるので、そこから2文字 → "hi"が検出されるはず。
実行してみる。
 $ /usr/libexec/locate.bigram  < bigram.dat
 hiefbcDE
 $ echo $?
 0
予想通りとなった。なお、"echo"のコマンドプロンプトを改行して表記しているが、実際は改行コードは出力されていない為
 hiefbcDE$ echo $?
 0
のように表示されている。

locate独自のbigram検出プログラムである locate.bigram.c の解析はここまでにし、続いて locate.code.c の解析に進む。

* "locate.code"によるファイルリストの圧縮→理解不能、挫折。

進む。

すす・・・もうとしたんですが、code/locate.code.cとか、DBを読み込む locate/locate.c は自分の頭では全て理解することができませんでした　｡･ﾟ･(ﾉД`)

細かい所は殆ど解析出来ず、以降は大雑把なメモ兼駄文になります。正確な解説については「デーモン君のソース探検」を参照して下さい。

"bigram/locate.bigram.c" は単純にファイルリストからbigramを抽出するプログラムです。
実際に、そのbigramのリストとファイルリストからlocate独自のDBファイルを生成するのが "code/locate.code.c" になります。
"locate/locate.c"が実際のlocate(1)コマンドのソースで、locate独自のDBファイルを探索するプログラムになります。

この"locate独自のDBファイル"というのが、bigramとファイルリストの各行の近似を数値化したデータの組み合わせで構成されています。
ファイルリストというのは
 /usr/src/foobar
 /usr/src/barbaz
 ...
のように、前後行で同じ部分が沢山存在します。なので、同じ部分の文字列長をうまく使えば、データを大幅に圧縮出来ます。・・・それとbigramを組み合わせたりする処理が難しくて理解しきれなかった訳です。
一応 "code/locate.code.c" の冒頭に、コメントで仕組みが解説されてはいます。
#pre||>
/*
 * PURPOSE:     sorted list compressor (works with a modified 'find'
 *              to encode/decode a filename database)
 *
 * USAGE:       bigram < list > bigrams
 *              process bigrams (see updatedb) > common_bigrams
 *              code common_bigrams < list > squozen_list
 *
 * METHOD:      Uses 'front compression' (see ";login:", Volume 8, Number 1
 *              February/March 1983, p. 8).  Output format is, per line, an
 *              offset differential count byte followed by a partially bigram-
 *              encoded ascii residue.  A bigram is a two-character sequence,
 *              the first 128 most common of which are encoded in one byte.
 *
 * EXAMPLE:     For simple front compression with no bigram encoding,
 *              if the input is...              then the output is...
 *
 *              /usr/src                         0 /usr/src
 *              /usr/src/cmd/aardvark.c          8 /cmd/aardvark.c
 *              /usr/src/cmd/armadillo.c        14 armadillo.c
 *              /usr/tmp/zoo                     5 tmp/zoo
 *
 *      The codes are:
 *
 *      0-28    likeliest differential counts + offset to make nonnegative
 *      30      switch code for out-of-range count to follow in next word
 *      128-255 bigram codes (128 most common, as determined by 'updatedb')
 *      32-127  single character (printable) ascii residue (ie, literal)
 *
 * SEE ALSO:    updatedb.csh, bigram.c
 *
 * AUTHOR:      James A. Woods, Informatics General Corp.,
 *              NASA Ames Research Center, 10/82
 */
||<
が、これと実際のコードだけでは自分のオツムでは理解出来ませんでした・・・。
 $ cat filelist
 /bin/prog1
 /bin/prog2
 /usr/bin/prog1
 /usr/bin/prog2
 /usr/bin/prog3abc
 /usr/bin/prog4
 $ /usr/libexec/locate.bigram < filelist
 usror/progn/ing1bibc3a/p/b
 $ /usr/libexec/locate.code usror/progn/ing1bibc3a/p/b < filelist > result
 $ od -h result
 0000000     7375    6f72    2f72    7270    676f    2f6e    6e69    3167
 0000020     6962    6362    6133    702f    622f    0000    0000    0000
 0000040     0000    0000    0000    0000    0000    0000    0000    0000
 *
 0000400     8c0e    8b86    8781    3217    8006    8882    8385    3184
 0000420     321a    8a0e    0e89    0034
 0000427
 $ od -a result
 0000000    u   s   r   o   r   /   p   r   o   g   n   /   i   n   g   1
 0000020    b   i   b   c   3   a   /   p   /   b nul nul nul nul nul nul
 0000040  nul nul nul nul nul nul nul nul nul nul nul nul nul nul nul nul
 *
 0000400   so  8c  86  8b  81  87 etb   2 ack  80  82  88  85  83  84   1
 0000420  sub   2  so  8a  89  so   4
 0000427
他の実験結果から、先頭256バイトまでが "locate.bigram" が生成したbigramデータ、それ以降が差分長とbigramを組み合わせた圧縮データになっているようです。

このデータを "locate/locate.c" が処理します。細かい処理は分かりませんでしたが、大枠の流れが以下のようになっているところまでは分かりました。
+ データファイルのリストを生成する。(":"区切りのLOCATE_PATH環境変数、およびコマンドライン引数、locate/pathnames.h中でのハードコード定義をマージする)
+ コマンドラインで指定された検索キーワード毎に、データファイルのリストを探索していく。データファイルのFILEポインタがfastfind()に渡される。
++ fastfind()の中では、最初にデータファイル先頭のbigramデータが内部バッファにロードされる。
++ 続いてキーワードにパターンマッチ用の文字が入っていれば、patprep()関数で前処理を行う。
++ データファイルを1文字ずつ読んでいく。都度復号化し、キーワードまたはパターンにマッチするかチェックしていく。

理解出来たのはここまでで・・・結局一番重要なデータファイルの構築や解析部分はお手上げでした・・・。


今回のお題については、ここまで。

「デーモン君のソース探検」でもデーモンパパの台詞として「昔はディスク容量も小さくて高価だったので、苦労して圧縮を行っていた」とありますが、過去の偉人の苦労が良くわかるソース探検でした。

自分はWebアプリがメインでしたので、HTMLを整えたりRDBに対してSQLを発行したり、あとは共通部分をうまくライブラリ化したりなどに注力してきた為、今回のようなアルゴリズムが全面に出てくるソースは殆ど書いたことが無かったです。
同じ「プログラマ」でも、住んでる場所・時間により随分と力量差がついてしまうものなんですね・・・。

#navi_footer|C言語系|