FreeBSD 11.1R: TAILQ

FreeBSD 11.1R では、カーネル内で構造体の動的なチェーンを扱うときには TAILQ_xxx() マクロが利用されることが多いです。TAILQ_xxx() は、構造体どうしで一対多の親子関係があって、子が動的に追加されたり削除されたりする場合に、とても便利なマクロです。

『親』の構造体では、例えば次のように宣言します。

TAILQ_HEAD(, socket) so_comp;

すると次のように展開されます（『子』の構造体の先頭と末尾を指しています）。

struct {
    struct socket *tqh_first;   /* first element */
    struct socket **tqh_last;   /* addr of last next element */
} so_comp;

そして『子』の構造体では、例えば次のように宣言します。

TAILQ_ENTRY(socket) so_list;

すると次のように展開されます（次と前の『子』の構造体を指しています）

struct {
    struct socket *tqe_next;    /* next element */
    struct socket **tqe_prev;   /* address of previous next element */
} so_list;

TAILQ を扱うための TAILQ_FIRST(), TAILQ_NEXT() をはじめとしたマクロ関数の使い方はとても直感的なので、カーネルのソースコードで利用例を見ればすぐにわかると思います。また「man 3 queue」でマニュアルを読むこともできます。

TAILQ_xxx() は sys/sys/queue.h で定義されています。とてもよく練られたマクロで、20年くらい前に初めて読んだときはとても感動しました。当時は手作業でマクロを展開しながらドキドキしながら読みました。できれば自分でウンウン唸りながら読んだ方が楽しいと思います。ポイントは tqh_last と tqe_prev がポインタのポインタになっているところです。しかし事前に解説記事を読みたい方は、下記記事が参考になるかもしれません。

• TAILQ のソースを読んで C のポインタをマスターする。 (こせきの技術日記, 2012-01-05)

ところで、およそ20年ぶりに読んでみると、sys/sys/queue.h は大きく進化しているようでした。操作用のマクロが増えたような気がします。C++ でも使えるようになり、構造体だけでなくクラスでも使えるようになっています。デバッグ機能が追加されてました。QUEUE_MACRO_DEBUG が定義されている場合には QMD_xxx() というマクロ関数を使ってデバッグ用のコードが追加されるようです。

それから、TAILQ_REMOVE() はチェーンから削除した構造体の TAILQ_ENTRY() の再初期化をしないのですね。チェーンから削除した構造体は free されることが多いからではないかと思います。ですからもしも、チェーンから削除しても使い続ける場合はゴミが残ります。ゴミが不安な場合は、QUEUE_MACRO_DEBUG を定義すると (void*)-1 が代入されるので、バグがあればすぐに見つかると思います。ゴミを消しておきたい場合は明示的に値を代入する必要があります。