IPv4のFIB lookupにTRIEが使えるようになってた

タイトルの通り。いつ頃から使えるのか追いかけていないけど、2.6.21ではIP_ADVANCED_ROUTERが有効になっているときにTRIEかHASHかを選べるようになってる。
TRIE自体については高林さんの記事が日本語の文書としてはわかり易い。
FIBというのはForwarding Information Baseの略で、ようするにルーティングテーブルのカーネル内での内部表現。いわゆるレイヤ3スイッチというのはこのFIBを索く処理とパケットのコピーの処理がハードウェア処理されている装置の事を指す(Ciscoで言うところのハードウェアCEF)。ただしコアルータなどの大型ルータなども同じようにハードウェアでFIBを索くが、これらの装置をスイッチとは(慣習的に)呼ばない。FIBはハードウェア実装のTCAM(Ternary CAM)というのに保持されるので、検索時間はO(1)。但し、通常のメモリー上にソフトウェアで構造を作っているのではなく、ハードウェアによって実現しているため大きさが決め打ち。例えば、Cat65kのSUP-720ではIPv4とIPv6共用で250kまでしか保持できない(ちょい疎覚え)。それ以上ルーティングテーブルに保持しようとするとCPU処理となって実用には耐えないぐらいのスピードになってしまう。
閑話休題。Linuxの実装ではヘルプにある通り、非常に大きなルーティングテーブルを持つときに有効だけどメモリーは喰うし複雑なので一般的なユーザにはFIB_HASHで十分だとある。赤悪魔本にはこの辺の実装の詳細が記載されていたと思ったが、今部屋を探したら本が見当らなかった。Linuxのカーネル本はオライリーとソフトバンクの本を見たが、後者がFIBの構造に触れているぐらいで前者はネットワーク周りの処理自体に言及がなかった。
ハッシュのときの実装ではfn_zoneというnetmask長ごと配列があって、その先がハッシュテーブルになっているという構造。索くときはマスク長の長い方から手繰っていって探す。以下がその中心となる関数。

static int
fn_hash_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
{
        int err;
        struct fn_zone *fz;
        struct fn_hash *t = (struct fn_hash*)tb->tb_data;

        read_lock(&fib_hash_lock);
        for (fz = t->fn_zone_list; fz; fz = fz->fz_next) {
                struct hlist_head *head;
                struct hlist_node *node;
                struct fib_node *f;
                __be32 k = fz_key(flp->fl4_dst, fz);

                head = &fz->fz_hash[fn_hash(k, fz)];
                hlist_for_each_entry(f, node, head, fn_hash) {
                        if (f->fn_key != k)
                                continue;

                        err = fib_semantic_match(&f->fn_alias,
                                                 flp, res,
                                                 f->fn_key, fz->fz_mask,
                                                 fz->fz_order);
                        if (err <= 0)
                                goto out;
                }
        }
        err = 1;
out:
        read_unlock(&fib_hash_lock);
        return err;
}

forループはFIB ZONE同士のリストを手繰る処理をしながら辿るループ。各マスク長ごとのリストへの要素数33個の配列もあるけど、そのマスク長に対応するエントリーが無い場合もあるのでエントリー同士のリストを手繰った方が少しだけ安いのかも。
fz_keyはinline指定のある関数で、以下の通り。

static inline __be32 fz_key(__be32 dst, struct fn_zone *fz)
{
        return dst & FZ_MASK(fz);
}

ようするにそのマスク長のビットマップとANDをとって比較するべきビットパターンを採り出す。あとはそのゾーン内にあるハッシュと個別に比較しながら探索。hlist_for_each_entry()というのはマクロでLKH-jpのWikiに詳しい。ようするにカーネル内で汎用的に使えるハッシュリストの探索ループ*1。
と、ここまで読んでいて思ったが、これってIPv4のlonges matchを効率良く探索できるような構造になってはいるものの線形探索と変らないな。実際にはルートキャッシュがあるので、一般的なホストではこの処理が頻繁に実行されるわけではないはずだけど。
肝心のTRIEの方は気力が切れたの断念。まぁ、BSDと同じですよ、多分。ただ、ciscoが効率のよいTRIE構造を使ったルックアップのアルゴリズムを特許取得しているとかで、Linuxはその実装を使えないと聞いたことがある。ソースの先頭に論文のURLが記載されているので、最近の研究で別のいいアルゴリズムが開発されたのかもしれない。
[あとで読む]っと。

*1:一瞬ブロック渡しの関数かと思った