執筆者 : 小田　逸郎

※ 「新Linuxカーネル解読室落穂拾い」連載記事一覧はこちら

はじめに

今回から、コードの解説を行っていきたいと思います。Linuxのコードを読んでいると、最初は分からないことだらけで、いろいろ調べて行くうちにどんどん発散してしまって収拾が付かなくなることが良くあると思います。調べて見ると、あまり処理の本質に関係なくて、そんなに調べる必要なかったということも良くあります。本ブログでは、コードを読んでいて、あれ、これなんだろうと思うような事項に関し、あまり深く考える必要がなくなるような情報提供を心掛けたいと思っています。コードを読んでいく中で処理の本質に関係ない部分に費やす時間が短くなれば、コードを読む際の精神的負担も軽減されるのではないかと思います。

likely

最初はほんの小ネタです。コードを読んでいると、よく以下のコードのように、if文の条件部分にlikely関数(?)が出てくることがあります。

if (likely(tsk->mm == mm)) {

同様にunlikelyというのも出てきます。これは一体何なんでしょう。これは、関数ではなくて、include/linux/compiler.h に定義があります。

# define likely(x)   __builtin_expect(!!(x), 1)
# define unlikely(x)    __builtin_expect(!!(x), 0)

また新たな謎が出てきました。__builtin_expectとは何者でしょう。答えを言ってしまうと、これは、gccのビルトイン関数といって、gccが内部的に持っている関数です。今でこそ、Linuxをclangでビルドすることもできます*1が、従来は、gccのみでしたし、現在でもgccを使う方が主流です。何か怪しげな関数、特に「__」で始まるものが出てきたら、gccのビルトイン関数ではないかと疑ってみましょう。これに限らず、Linuxは、gccの拡張機能を使っているので、gccのドキュメントは必携です。gccのドキュメントは以下にあります。

https://gcc.gnu.org/onlinedocs/gcc/

ビルトイン関数に関しては、目次から、探したい関数に辿り着くのは結構大変なので、インデックス(下記)から探すのがお勧めです*2。

https://gcc.gnu.org/onlinedocs/gcc/Concept-and-Symbol-Index.html

そうやって、__builtin_expectの説明に辿り着いて、読んでみると、要するに条件が成立する可能性をコンパイラに知らせるためのものであることが分かります。いや、それにしても、デフォルトでは、確率90%の扱いで、確率を明に指定できるって、一体何にどう使うんだい、と思いますけど。それはさておき、likely(x)は、xが真になる可能性が高い、unlikely(x)は、xが偽になる可能性が高いということを意味します。なお、__builtin_expect関数の復帰値は、第一引数自身です。__builtin_expect関数の引数は整数なので、「!!(x)」は、if文の条件部分を強制的に整数(0か1)に変換するものです。

コードの内容だけ考えると、likelyやunlikelyは、無視して差し支えありません。前記のコードは、以下だと思っていいのです。

if (tsk->mm == mm) {

それでは、likely/unlikelyを付けることにより、どんな効果があるかということですが、コンパイラが生成するアセンブリコードに影響が出てきます。コンパイラは、この指定をヒントに、条件付き分岐命令の実行時にジャンプする可能性が少なくなるようにコードを生成します。ここではあまり詳細には立ち入りませんが、筆者が少し試してみた結果を補足資料に置いてあるので参考にしてください。結局のところ、likely/unlikelyは、性能的な配慮と言うことです。分岐が発生すると、CPUのパイプラインが切れて性能的なペナルティが発生するので、分岐がないに越したことはありません。ただ、ハードウェアはハードウェアで分岐予測を行って、パイプラインが切れないような工夫をしています。コンパイラはコンパイラで最適化を頑張っているし、ハードウェアはハードウェアで最適化を頑張っています(まあ、コンパイラが最適化した方がハードウェアの最適化も効き易そうな気はしますが)。OS側としては、一応、likely/unlikelyとおまじないを掛けてみて、性能が上がる(下がらない)ことを祈るのみといった感じで、実際のところ、実機で動かして見ないと効果のほどは分からないと思います。

これで、likely/unlikelyが出てきても、自然に無視できるようになったかと思います。実際のところ、分かってしまえば、何てことないのですが、知らない間は、何か気になってしまって、喉に小骨が刺さった気分で精神衛生上良くないです。とは言え、一々調べていたらいくら時間があっても足りませんし、今回の例のように調べてみたら、本質的な処理の内容には全く関係なく、がっかりするケースも多いかと思います。本ブログでは、詳細には踏み込みませんが、一応、詳しく調べたい人のために、そのためのポイントを示しつつも、皆さんが気持ちよく無視できるような情報を出して行きたいと思ってます。コードを読む際の精神的負荷を下げられれば幸いです。

likely/unlikelyに関しては、コードを信用するのであれば、その条件が成り立つ方が普通なのか、成り立たない方が普通なのかの判断に使えそうです。コードを読む際のヒントにできるかもしれませんね。likely/unlikelyは、山のように出てきますが、それでもif文の全体からしたら、ほんの氷山の一角に過ぎません。実のところ、どういった場合に付けるのか、判断基準を明確に示したドキュメントは見つけられませんでした。好意的に解釈すると、付ける・付けないで性能差が大きい場合に付けていると考えられますが、筆者は、そこまでは信用してません。適当に付けてるんじゃないですかね。

リンクリスト

Linuxで使用している基本的なデータ構造について見ていきたいと思います。第一弾は、リンクリストです。まずは、一旦、Linuxに限らず、リンクリストの基本的なパターンについておさらいしましょう。

まずは、単方向の単純なリストです(下図)。

LIFO(Last In, First Out)の操作を実現するためには、この単純な構造で十分です。リストへの挿入(put)と取り出し(get)のコードは、以下のようになります。

struct hoge {
        struct hoge *next;
        /* 他のメンバー */
};

struct hoge *head = NULL;

void put(struct hoge *e)
{
        e->next = head;
        head = e;
}

/* 要素がない場合は、NULLを返す。*/
struct hoge *get(void)
{
        struct hoge *e = head;
        if (e != NULL) {
                head = e->next;
        }
        return e;
}

FIFO(First In, First Out)の操作を実現するためには、最後の要素を指すポインタ(tail)を追加すればよいです(下図)。

put、getのコードは以下のようになります。

struct hoge *head = NULL;
struct hoge *tail = NULL;

void put(struct hoge *e)
{
        e->next = NULL;
        if (tail == NULL) {
                head = tail = e;
        } else {
                tail->next = e;
                tail = e;
        }
}

struct hoge *get(void)
{
        struct hoge *e = head;
        if (e != NULL) {
                head = e->next;
                if (e == tail) {
                        tail = NULL;
                }
        }
        return e;
}

次は双方向にリンクされたリストを見てみましょう(下図)。

これの利点は、(要素がリストのどの位置にあっても)要素の取り外しが容易なことです。予め、要素は分かっているとして、それをリストから取り外したいとします。単方向リストでは、その要素の前の要素を知るためには、リストを走査する必要があります。双方向リストであれば、その要素だけで処理が完結します。要素の取り外し(del)のコードは以下のようになります。

struct hoge {
        struct hoge *next;
        struct hoge *prev;
        /* 他のメンバー */
};

void del(struct hoge *e)
{
        if (e->prev != NULL) {
                e->prev->next = e->next;
        }
        if (e->next != NULL) {
                e->next->prev = e->prev;
        }
}

リンクのためのポインタを独立した構造体(list_head)として扱うことが考えられます(下図)。いっそのこと、head自体をlist_headにしてしまい、循環させる形にすれば、リストの最後へのアクセスも楽になります。

list_headに対する各種操作のコードは以下のようになります。

struct list_head {
        struct list_head *next;
        struct list_head *prev;
};

void init_head(struct list_head *head)
{
        head->next = head;
        head->prev = head;
}

void del(struct list_head *e)
{
        e->prev->next = e->next;
        e->next->prev = e->prev;
}

void is_empty(struct list_head *head)
{
        return head->next == head;
        /* head->next == head の場合、必ず、head->prev == head でもある。*/
}

/* this の次に new を挿入 */
void put_next(struct list_head *this, struct list_head *new)
{
        new->next = this->next;
        new->prev = this;
        this->next->prev = new;
        this->next = new;
}

/* this の前に new を挿入 */
void put_prev(struct list_head *this, struct list_head *new)
{
        new->next = this;
        new->prev = this->prev;
        this->prev->next = new;
        this->prev = new;
}

/* リストの先頭に new を繋ぐ */
void put_head(struct list_head *head, struct list_head *new)
{
        put_next(head, new);
}

/* リストの最後に new を繋ぐ */
void put_tail(struct list_head *head, struct list_head *new)
{
        put_prev(head, new);
}

headの初期状態としては、next、prevとも自分自身を指しておくようにします。リストが空かどうかは、headのnext(or prev)が自分自身であるかどうかで判断することになります。循環するようにしたので、NULLチェックが要らなくなってコードがシンプルになっています(ex. del)。リストに新しい要素を繋ぐ際は、前か後ろの要素が分かれば繋げます。上記コードでは、put_next、put_prev がそれに当たります。リストの先頭に繋ぐか、最後に繋ぐかは、headの次に繋ぐか、headの前に繋ぐかと言い換えることができます(put_head、put_tail)。

list_head 構造体は、実際の構造体の中に埋め込んで使うことになります。

struct hoge {
        /* 他のメンバーがある場合もあり */
        struct list_head list;
        /* 他のメンバー */
};

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)   /* これで、MEMBERの構造体内のオフセットが求まる */
/* gcc の__builtin_offsetof を使ってもよい。 */

// struct list_head * p;
/* このマクロは、struct hoge 専用 */
#define list_to_entry(p) (struct hoge *)((void *)p - offsetof(struct hoge, list))
/* リストのポインタから、オフセット分引けば、要素の先頭ポインタが求まる */

よくやるのは、listを構造体の先頭に置くことで、そうすると、listのポインタを単にキャストするだけで、要素へのポインタとなります。listが構造体の先頭でなくても、上記リスト(list_to_entry)のようなマクロを定義することにより、listのポインタから要素のポインタを求めることができます。Linuxの場合、container_of (include/linux/container_of.h)という汎用的なマクロが用意されています。

さて、いよいよ、Linuxの話をすると、最も良く使われているのは、最後に紹介した循環式の双方向リストです。上で定義した struct list_head と同じものが include/linux/types.h に定義されています。また、リストに関する関数やマクロが、include/linux/list.h に大量に定義されています。ここで本題ですが、コードを読んでいると、良く以下のようなコードが出てくるのではないでしょうか。

// struct list_head *pos;

list_for_each(pos, head) {
        ...
}

こんな文は、C言語の文法にないし、何かマクロで定義されているのか、と思われるかもしれませんが、その通りです。include/linux/list.h に以下のように定義されています。

static inline int list_is_head(const struct list_head *list, const struct list_head *head)
{
    return list == head;
}

#define list_for_each(pos, head) \
    for (pos = (head)->next; !list_is_head(pos, (head)); pos = pos->next)

リストの構造(上方の図)を思い浮かべれば、コードでやっていることは明らかで、特に難しいことはありません。コードの文字数を減らし、読みやすくするためのマクロですね。分かってしまえば何てことありませんが、初見では、何だこれ、となるでしょう。「list_」で始まるものは、list.hに定義された関数かマクロで、だいたい名前から想像は付くと思いますが、曖昧なときは、ヘッダを確認すればすぐに分かる、と覚えておきましょう*3。これで、また余分なことに気を回す必要がなくなり、精神的負担が軽くなりましたね。list_headほど使われてはいませんが、Linuxには、循環式ではない双方向リストもありますので、紹介しておきましょう。こちらもlist_head同様、独立の構造体として、include/linux/types.hに定義してあります。

struct hlist_head {
        struct hlist_node *first;
};

struct hlist_node {
        struct hlist_node *next, **pprev;
};

ヘッドが別構造体になっているのと、prevではなく、pprev(struct hlist_node **)になっているのが目を引きます。

図にすると、上のような具合で、先に紹介した双方向リストとの違いは、先頭のノードのpprevがNULLではなく、ヘッドをポイントしているところです。pprevになっているのは、リンクの追加・削除時にヘッドを特別扱いしないための工夫ということです。pprevには、前方のnextメンバ(or firstメンバ)のアドレスが入ることになります。実際の値としては、前方のhlist_node(hlist_head)構造体のアドレスと等しいです(まさに上図のとおりということ)。hlist_head/hlist_nodeに関しても、list_head同様、include/linux/list.h に一杯マクロが定義されています。リンクの操作を行う場合は、それらマクロを使用することになります。一度、参照してみてください。

リンクリストは構造が単純で良いのですが、何か要素を検索する際は、先頭から順に見ていく必要があるので、要素数が多いと時間が掛かります(要素数に対して線形に増加)。最も単純な対策は、ヘッドを複数用意し、なんらかのハッシュ関数でどのヘッドに繋げるか選択するというものです。コードで示すと以下のような感じです。

#define NUM_HEAD 64
struct hoge *hoge_head[NUM_HEAD];

int hoge_hash(struct hoge *)
{
        /* struct hoge のメンバー等をキーとして、何らかのハッシュ値(0～NUM_HEAD)を計算する。*/
        /* ハッシュ値を返す */
}

void put(struct hoge *e)
{
        struct hoge *head = &hoge_head[hoge_hash(e)];

        /* e をheadに繋ぐ */
}

うまく分散してくれれば、リストの長さが NUM_HEAD 分の1くらいになるだろうという寸法です。include/linux/list.h内のコメントによると、hlist_head/hlist_nodeの方は、このハッシュ化リストでの使用を想定しているとのことです。ヘッドが複数になるので、list_headを使うよりもヘッド領域の節約になります。なお、hlist_head/hlist_nodeの弱点は、最後尾のメンバがすぐに分からないことですので、その点に注意が必要です。

少し内容としては簡単過ぎましたかね。ただ、ここで話した内容は、OSをやり始めた頃に先輩からレクチャーを受けた内容で、基本的な話なので、初学者には大事な話かと思います。昔のOSは、単純なデータ構造しか使っておらず、アルゴリズムの本に出てくるような複雑なデータ構造は使っていませんでした。上に説明した範囲で事足りていたのです。しかしながら、最近(でもないか)のLinuxでは、取り扱うデータが大量になってきたため、アルゴリズムの本に出てくるような複雑なデータ構造も使うようになっています。それらの紹介もおいおいやっていきます。