epollのなかみ

よく C10K 問題とかいって epoll(7) の話が出てきて select(2) 遅いね poll(2) 遅いねってなるんだけど、正直なところ、これらのシステムコールを実際に使ってコードを書いてみたひとはどのくらいいるのだろう。ましてや eventpoll が何やってるか知っている人はそんなに多くないんじゃないだろうか。もう O(n) だの O(1) だのって煙に巻かれるのもうんざりだ。

というわけで、2.6.26 の fs/eventpoll.c のコードを読んでみた。正直 Linux カーネルにすごく詳しいわけでもないので、誤りがあったら適宜突っ込んでもらえると幸いです。

前提知識として VFS モジュールがどうなってるかとかは

のソース中のコメントを追ってもらえればと。

登場する構造体

eventpoll.c で使われている構造体のうち、主要なものは次の 3 つ。

struct eventpoll (fs/eventpoll.c で定義)
struct epitem (fs/eventpoll.c で定義)
struct eppoll_entry (fs/eventpoll.c で定義)

この他に、カーネルの他の部分と共有の構造体として次のようなものがある。

struct epoll_event (linux/eventpoll.h で定義)
struct file * (linux/fs.h で定義)
poll_table (linux/poll.h で定義)
wait_queue_t (linux/wait.h で定義)
wait_queue_head_t (linux/wait.h で定義)
struct list_head (linux/list.h で定義)
struct rb_root (linux/rbtree.h で定義)
struct rb_node (linux/rbtree.h で定義)

では、それぞれの構造体の役割をみていこう。

追記: この辺の話はソース見ながらじゃないと多分わかんないので適宜手元にソースを用意してください。

struct list_head

next と prev というメンバがあり、双方向連結リストを表現する。

wait_queue_head_t / wait_queue_t

こいつらは中に struct list_head を持っていて、それぞれリスト自体、とその要素を表している。wake_up() とかその系統の関数 (かマクロ) が呼ばれると、wake_queue_t にセットされたコールバック関数が呼ばれるしくみ。

struct rb_root / struct rb_node

こいつらはそれぞれ赤黒木の根っことノードを表している。

struct eventpoll

/*
 * This structure is stored inside the "private_data" member of the file
 * structure and rapresent the main data sructure for the eventpoll
 * interface.
 */
struct eventpoll {
	/* Protect the this structure access */
	spinlock_t lock;

	/*
	 * This mutex is used to ensure that files are not removed
	 * while epoll is using them. This is held during the event
	 * collection loop, the file cleanup path, the epoll file exit
	 * code and the ctl operations.
	 */
	struct mutex mtx;

	/* Wait queue used by sys_epoll_wait() */
	wait_queue_head_t wq;

	/* Wait queue used by file->poll() */
	wait_queue_head_t poll_wait;

	/* List of ready file descriptors */
	struct list_head rdllist;

	/* RB tree root used to store monitored fd structs */
	struct rb_root rbr;

	/*
	 * This is a single linked list that chains all the "struct epitem" that
	 * happened while transfering ready events to userspace w/out
	 * holding ->lock.
	 */
	struct epitem *ovflist;

	/* The user that created the eventpoll descriptor */
	struct user_struct *user;
};

この構造体は poll 対象となるファイルディスクリプタのリストを保持するもので、epoll_create(2) が呼ばれる度に確保され、新しいファイルディスクリプタに関連付けられる。

この構造体のメンバのうち、ロックなどロジックに関係ないものを省いた 5 つについて説明する。

(wait_queue_head_t) wq
(wait_queue_head_t) poll_wait: 保持しているファイルディスクリプタのうちいずれかにイベントが発生したときに発火される wait queue。2 つある理由については後述。
(struct list_head) rdllist: イベント発生時に、poll 対象となるファイルディスクリプタに対応する struct epitem のインスタンスが追加されるリスト
(struct rb_root) rbr: poll 対象となるファイルディスクリプタに対応する struct epitem のインスタンスが追加される赤黒木。キーは struct file へのポインタと fd 番号の組み合わせ
(struct epitem*) ovflist: epoll_wait(2) の呼び出し時、ユーザ空間に発生したイベントに対応する struct epoll_event をコピーしている間に発生してしまったイベントが追加される単方向連結リスト (FILO)。

struct epitem

/*
 * Each file descriptor added to the eventpoll interface will
 * have an entry of this type linked to the "rbr" RB tree.
 */
struct epitem {
	/* RB tree node used to link this structure to the eventpoll RB tree */
	struct rb_node rbn;

	/* List header used to link this structure to the eventpoll ready list */
	struct list_head rdllink;

	/*
	 * Works together "struct eventpoll"->ovflist in keeping the
	 * single linked chain of items.
	 */
	struct epitem *next;

	/* The file descriptor information this item refers to */
	struct epoll_filefd ffd;

	/* Number of active wait queue attached to poll operations */
	int nwait;

	/* List containing poll wait queues */
	struct list_head pwqlist;

	/* The "container" of this item */
	struct eventpoll *ep;

	/* List header used to link this item to the "struct file" items list */
	struct list_head fllink;

	/* The structure that describe the interested events and the source fd */
	struct epoll_event event;
};

この構造体のインスタンスは、監視対象のファイルディスクリプタ 1 個に対応するエントリとして epoll_ctl(EPOLL_CTL_ADD, ...) が呼ばれる度に確保され、struct eventpoll に追加される。

(struct rb_node) rbn

struct eventpoll の赤黒木のノードに対応する。ノードを表す情報が構造体に埋め込まれている、と考えるといいかも。

(struct list_head) rdllink

イベント発生時に、poll 対象となるファイルディスクリプタに対応する struct epitem のインスタンスが追加されるリストの要素となるために必要

(struct epitem*) next

struct eventpoll の ovflist の要素となるために必要なポインタ。

(struct epoll_filefd) ffd

対応する struct file とファイルディスクリプタ番号のペアを格納している

struct epoll_filefd {
	struct file *file;
	int fd;
};

(int) nwait

pwqlist のエントリの数。一時的にエラー状態を示すフラグとしても使われる。

(struct list_heada) pwalist

このインスタンスに対応する wait queue のエントリを格納する struct eppoll_entry を保持するリスト

(struct eventpoll *) ep

このインスタンスを保持する struct eventpoll へのポインタ

(struct list_head) fllink

このインスタンスに対応する struct file が保持している、対応するすべての struct epitem のリスト (f_ep_links) の要素となるために必要

(struct epoll_event) event

このインスタンスの関心のあるイベントを表す。epoll_wait() 成功時に、ユーザ定義データと合わせてまるごとユーザ空間に転送される。

struct eppoll_entry

/* Wait structure used by the poll hooks */
struct eppoll_entry {
	/* List header used to link this structure to the "struct epitem" */
	struct list_head llink;

	/* The "base" pointer is set to the container "struct epitem" */
	void *base;

	/*
	 * Wait queue item that will be linked to the target file wait
	 * queue head.
	 */
	wait_queue_t wait;

	/* The wait queue head that linked the "wait" wait queue item */
	wait_queue_head_t *whead;
};

この構造体のインスタンスは、VFS モジュールの poll 操作が自分の保持している wait_queue_head_t に呼び出し元の wait_queue_t を追加させるためにコールバック関数を呼び出す度に作られる。調べた限りでは 1 回の poll 操作で複数の wait queue に追加しようとする実装はあってもまれ、ということのようなので、事実上 struct epitem とこの構造体は1対1で対応していると考えてしまっていいようだ。

(struct list_head) llink: struct epitem の pwqlist の要素となるために必要
(void *) base: 対応する epitem へのポインタ
(wait_queue_t) wait: VFS モジュールの側で struct file のインスタンス毎に保持している wait queue に追加される
(wait_queue_head_t *) whead: VFS モジュールの側で保持している wait queue へのポインタ

以上、説明した構造体を図にしてみると次のようになる。

「??? (private_data)」というのは struct file 構造体の private_data メンバの指し示す先の「曖昧な」*1 構造体を表している。大抵の実装ではこの構造体の中に poll 操作用の wait_queue_head_t が格納されており、これを図に入れたほうがわかりやすくなるので入れてある。

実際にこれらの構造体がどう参照しあうのかを表現したのが下の図だ。ここでは例として、2 つの struct eventpoll があり、片方には 2 つの struct file が、もう片方には 1 つの struct file が関連付けられていて、かつ、2 つ目の struct eventpoll に関連付けられた struct file は、1 つ目にも関連付けられている、という状況を想定している。

ところで、struct eventpoll になぜ同じタイミングで発火される wait queue が 2 つあるのか、という話だけど、これは epoll 自体がユーザランドではファイルディスクリプタとして表現され、poll 可能であるので、循環参照をつくることができる。そうするとイベントが発生したタイミングで無限ループに突入してしまうのでそれを防ぐような仕組みを入れる必要があり、その仕組みと本来 epoll_wait() で必要な wait queue を分離するために epoll 自体の poll 用の wait queue も用意しているというわけ。

epoll に対する各操作の内訳

epoll_ctl(EPOLL_CTL_ADD) が呼ばれるとどうなるか

基本的には以下のダイアグラムの通り。

何も難しいことはない。

poll 操作ハンドラが呼んでくるコールバック関数の動作もいたってシンプルだ。

レディキューと書いたのは eventpoll の rdllist のこと。

イベントが発生したときどうなるか

ep_poll_callback() という関数が呼ばれる。この関数の中でやっていることは以下の通り。

epoll_wait() が呼ばれるとどうなるか

こんな感じ。

ep_send_events() 中に発生し、ovflist に追加されたイベントは、ep_send_events() から戻る直前で rdllist に追加される。つまり、次回の event_poll() でそれらのイベントが返ってくるということになる。

まとめ

epoll_wait(2) では、実際に待つ wait queue は一つだけ。
一方…select(2) は…内部構造について詳しく説明しなくても、以上のことが理解できていれば、次のような説明でいいはずなんだけど…select(2) の場合は、システムコールのたびに wait_queue を構築しては poll して破棄するということを繰り返すので監視対象のファイルディスクリプタが多くなればなるほど遅くなる。
しかも epoll_wait(2) ではイベントが発生したファイルディスクリプタの情報のみを返す。一方、select(2) はすべてのファイルディスクリプタの情報を返す。
以上の事実を踏まえると、少なくとも非常に少ない頻度でしかイベントが発生しない状況、たとえば同時接続数が 10,000 あるサーバを考えたとき、1 秒間に多くて 50 回程度しか受信イベントが発生しないというような場合では、1 回の poll 操作で返ってくるファイルディスクリプタの数は、多くて数個ということになり *2、残りのディスクリプタの分のデータまで毎度ユーザ空間に転送するのは極めて無駄ということになる。
なので epoll(7) すげーね、ってところか。