はじめに
1. ソースコードの入手
2. 最初の一歩?
list head構造体
まとめ
参考文献

はじめに

Linuxユーザーのエンジニアであれば、Linuxがどのように動くのかに興味ありますよね。いつかはLinuxカーネルについて勉強してみたいと思っている方も少なくないのではないでしょうか。

この記事では、Linuxカーネルに入門しようとしている初心者が、割と早いうちに途方に暮れると思われる壁「list_head構造体」について見ていきたいと思います。

この記事は私のブログ https://achiwa912.github.io/ にも載せました。

ソースコードの入手

まずはLinuxカーネルのソースコードを入手しましょう。

Linuxカーネルの開発はずっと続いているので、書籍などで引用されているコードはすでに古くなっています。折角なので、最新版を入手したいですよね。
Linuxカーネルのソースコードをgit cloneして持ってきましょう。

git clone http://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git

20−30分くらいかかります。放置して待ちましょう。

~/git % git clone http://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git
Cloning into 'linux-stable'...
warning: redirecting to https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git/
remote: Enumerating objects: 1189260, done.
remote: Counting objects: 100% (1189260/1189260), done.
remote: Compressing objects: 100% (165947/165947), done.
remote: Total 8680156 (delta 1022459), reused 1186934 (delta 1020762), pack-reused 7490896
Receiving objects: 100% (8680156/8680156), 1.57 GiB | 3.01 MiB/s, done.
Resolving deltas: 100% (7328421/7328421), done.
Updating files: 100% (69365/69365), done.
warning: the following paths have collided (e.g. case-sensitive paths
on a case-insensitive filesystem) and only one from the same
colliding group is in the working tree:

  'include/uapi/linux/netfilter/xt_CONNMARK.h'
  'include/uapi/linux/netfilter/xt_connmark.h'
  'include/uapi/linux/netfilter/xt_DSCP.h'
  'include/uapi/linux/netfilter/xt_dscp.h'
  'include/uapi/linux/netfilter/xt_MARK.h'
  'include/uapi/linux/netfilter/xt_mark.h'
  'include/uapi/linux/netfilter/xt_RATEEST.h'
  'include/uapi/linux/netfilter/xt_rateest.h'
  'include/uapi/linux/netfilter/xt_TCPMSS.h'
  'include/uapi/linux/netfilter/xt_tcpmss.h'
  'include/uapi/linux/netfilter_ipv4/ipt_ECN.h'
  'include/uapi/linux/netfilter_ipv4/ipt_ecn.h'
  'include/uapi/linux/netfilter_ipv4/ipt_TTL.h'
  'include/uapi/linux/netfilter_ipv4/ipt_ttl.h'
  'include/uapi/linux/netfilter_ipv6/ip6t_HL.h'
  'include/uapi/linux/netfilter_ipv6/ip6t_hl.h'
  'net/netfilter/xt_DSCP.c'
  'net/netfilter/xt_dscp.c'
  'net/netfilter/xt_HL.c'
  'net/netfilter/xt_hl.c'
  'net/netfilter/xt_RATEEST.c'
  'net/netfilter/xt_rateest.c'
  'net/netfilter/xt_TCPMSS.c'
  'net/netfilter/xt_tcpmss.c'
  'tools/memory-model/litmus-tests/Z6.0+pooncelock+poonceLock+pombonce.litmus'
  'tools/memory-model/litmus-tests/Z6.0+pooncelock+pooncelock+pombonce.litmus'

おめでとうございます。これで、Linuxカーネルのソースコードを一式入手することができました。意外と簡単ですね。

最初の一歩?

Linuxのカーネルは巨大です。一体、どこから見始めればよいのか検討もつきません。普通は参考文献にあるようなLinuxカーネル本をガイドにするのがよいと思います。ところで、私の場合はVFSに興味があります。inodeとかsuperblockとかのあれです。若干いきなりすぎる感もありますが、superblockのデータ構造を見てみましょう。
linux-stable/include/linux/fs.hにありました。

struct super_block {
    struct list_head        s_list;         /* Keep this first */
    dev_t                   s_dev;          /* search index; _not_ kdev_t */
    unsigned char           s_blocksize_bits;
    unsigned long           s_blocksize;
    loff_t                  s_maxbytes;     /* Max file size */
    struct file_system_type *s_type;
    const struct super_operations   *s_op;
    const struct dquot_operations   *dq_op;
    const struct quotactl_ops       *s_qcop;
    const struct export_operations *s_export_op;
    unsigned long           s_flags;
    unsigned long           s_iflags;       /* internal SB_I_* flags */
    unsigned long           s_magic;
    struct dentry           *s_root;
    struct rw_semaphore     s_umount;
    int                     s_count;
    atomic_t                s_active;
<snip>

これが、superblockのデータ構造です。中身はさっぱりわかりませんが。。。
構造体の中の1行目に着目します。

struct list_head        s_list;         /* Keep this first */

これです。list head構造体。こいつが、カーネルのソースコードを少しでも読もうとする私のような初心者を突き放す、手強いやつなのです。しかも、やたらとたくさん出てきます。今回の記事では、これが何を意味するのかについて見ていきたいと思います。

list head構造体

背景

LinuxカーネルはC言語で書かれています。C言語には、よりモダンなプログラミング言語と違って、サポートするデータ構造は貧弱で、オブジェクト指向の仕組みも入っていません。例えば、Python等にあるリスト構造(['abc', 'def']みたいなやつ)はとても便利で、無くてはかったるくてプログラムなど書いていられないほどですが、C言語にリストはありません。同様にC言語にはクラスもありません。あるのは構造体のみ。

Linuxカーネル開発者達はこれらのモダンなデータ構造を、ユニークなやり方で実現しています。その一つが、リスト構造を実現するlist head構造体です。

list head構造体の定義

では、list head構造体の定義を見てみましょう。
linux-stable/include/linux/types.hにあります。

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

拍子抜けするほど単純ですね。前方、後方の、自身と同じlist head構造体へのポインタが入っているだけでした。なるほど、双方向リンクトリストなのですね。こういったやつです。(厳密には、循環双方向リンクトリストです)

+------+     +------+------+------+     +------+-----+------+     +------+
| null | <-> | prev |  ... | next | <-> | prev | ... | next | <-> | null |
+------+     +------+------+------+     +------+-----+------+     +------+

Linuxカーネルでの使われ方

いや、ちょっと待ってください。リストって、前後のポインタだけ入っていても意味が無いです。リストを構成する各ノードのデータが入っていないと。例えばinodeをリンクトリストで持つ場合、inodeはinode自身のデータをたくさん持っているはずです。ファイル名とか、オーナーとか、パーミッションとか。上の図で言うと・・・の部分です。

実は、list head構造体は、それを他の構造体に埋め込むことで、埋め込まれたペアレント構造体をリンクトリスト化できる便利なやつなのです。すごい！発想の転換です。

そう言えば、superblockの構造体は、list head構造体をメンバーとして持っていました。

struct super_block {
    struct list_head        s_list;         /* Keep this first */
    dev_t                   s_dev;          /* search index; _not_ kdev_t */
    unsigned char           s_blocksize_bits;
<snip>

こうすることで、superblockがリンクトリストのノードになっているのです。

更に、いくつものlist_head構造体を埋め込むことで、複数のリンクトリストに同時に登録することも可能です。構造体の定義を見ただけで、これは何と何と何のリンクトリストに含まれるかもわかります(コメントが書いてあるので)。これはPythonのリンクには真似ができませんね。

ペアレント構造体へのポインタを得る

リストを持たないC言語でリンクトリストを実現するため、という目的はわかりましたが、一つ問題が残っています。リストヘッド構造体は、同じリストヘッド構造体同士を結びつけるだけなのですが、本当に欲しいのはそれを埋め込んだペアレント構造体へのポインタです。ペアレント構造体をリンクトリスト化したいのですから。

それをするための関数が定義されています。

/**
 * list_entry - get the struct for this entry
 * @ptr:        the &struct list_head pointer.
 * @type:       the type of the struct this is embedded in.
 * @member:     the name of the list_head within the struct.
 */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

list_entry()関数です。この3つの引数は、

ptr: このlist_head構造体へのポインタ
type: list_headを埋め込んであるペアレント構造体のタイプ(上の例ではsuper_block)
member: このlist_head構造体の、ペアレント構造体内のメンバー名(上の例ではs_list)

であり、ペアレント構造体へのポインタを返します。

よかった、よかった。ですが、list_entry()関数の定義内容が気になります。
container_of()って何でしょうか。
grepで探したところ、linux-stable/include/linux/kernel.hに定義がありました。

/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr:        the pointer to the member.
 * @type:       the type of the container struct this is embedded in.
 * @member:     the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({                              \
    void *__mptr = (void *)(ptr);                                   \
    BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) &&   \
             !__same_type(*(ptr), void),                    \
             "pointer type mismatch in container_of()");    \
    ((type *)(__mptr - offsetof(type, member))); })

ポイントだけ抜き出します。

#define container_of(ptr, type, member) ({                              \
        void *__mptr = (void *)(ptr);                                   \
        ((type *)(__mptr - offsetof(type, member))); })

まずは、voidへのポインタ__mptrに、list_head構造体へのポインタptrをvoidへのポインタにキャストして代入しています。list_head構造体へのポインタのままだと使えないですからね。

次の行で、__mptrを、offsetof(type, member)分前にずらしているようです。offsetof(type, member)は上の例の場合、super_block構造体の中でのメンバーstruct list_head s_listのオフセットです。つまり、ペアレントであるsuper_block構造体へのポインタに変換しているのでした。そしてこれを、super_block構造体へのポインタにキャストしています。

まとめると、

list_head構造体をvoidへのポインタにキャストして扱いやすくする
作ったポインタを手前にずらして、ペアレント構造体の先頭を指すようにする
最後に、ペアレント構造体へのポインタにキャストする

ということでした。

なお、container_ofについては、参考文献のLinux Kernel Developmentの中では次のように定義されていました。

#define container_of(ptr, type, member) ({ \
    const typeof( ((type *)0)->member ) *__mptr = (ptr); \
    (type *)( (char *)__mptr - offsetof(type,member) );})

これを見て、「((type *)0)->memberって何だ? これは一体何をしているんだ???」と相当悩んだことがこの記事を書く動機だったのですが、最新のソースでは、若干わかりやすくなっていました。

まとめ

Linuxカーネルで定義するデータ構造においｔ、list_head構造体が埋め込まれた構造体があったら、それは何かのリンクトリストに含まれるということがわかりましたね。ソースのコメントを読めば、大抵は何のリンクトリストかが書いてあります。

list_entry()関数を使って、list_head構造体のポインタから、それが埋め込まれたペアレント構造体へのポインタに変換できます。そして、Linuxカーネルでのlist_entry() - contaier_of()の実装を少し見てみました。

参考文献

Linux Kernel Development 3rd Edition, Robert Love

Linuxカーネルに入門したいのだけどlist head構造体って何するもの?

Table of Contents