Linux kernel linked list implementation （和訳）

　node.jsでいろいろコーディングをしているときに、process.nextTickの挙動とかが未だに完全にピンときていない状態で、シングルスレッドとか、プロセスがどうだとかいう話もよく聴いていて、そもそも自分がプロセスとスレッドについてよくわかっていないなと思ったので、プロセスとスレッドについていろいろ調べていました。

　OSがどうやってプロセスとスレッドを扱うかを説明している記事がネット上で結構見つかって、特にlinuxカーネルのtask_structとかについてさらに調べていくと、どうやらプロセスの管理をlinked listを使って行っているらしいということがおぼろげながら見えてきました。どんどんぐぐっていったらカーネルのlinked listの実装について書いてある良い記事を見つけました。
時間もあったので、正確に訳しきれてないとこがありますが、和訳してみました。

(この記事に関する参考文献:　「詳解linuxカーネル　第３版」　p95 「双方向リスト」）

###Linux kernel linked list implementation　（和訳）
http://sumanadak.blogspot.jp/2006/09/linux-kernel-linked-list.html

　linked list は多数のデータを効率よく処理することを可能にする重要なデータ構造です。　多くのカーネルのソースコードはこのデータ構造を利用して書かれています。　そのため、多くのカーネルコードとデータ構造の計算量はこのlinked listのデータ構造の実装に由来する物です。　コーディングをする際、悪いコード構造のデザインはパフォーマンスの悪化をもたらします。良いOSというものは、安定性だけでなく、良いパフォーマンスも提供するべきです。そのため、私はlinuxがlinked listをどのように実装しているのかを知りたいと熱望していました。　is it circular singly linked list or doubly linked list or circular double linked list?
　これらのデータ構造に関する関数が宣言されているライブラリファイルはどこにあるのでしょうか。私が調べたところ /usr/src/linux/include/linux/list.h にあるのを見つけました。このデータ構造に関するすべての関数はここで宣言されています。この関数群に関して議論する前に、まずはlinuxカーネルがどのように効率的な実装戦略を選択しているのかお話しするべきだと思います。　循環リンクに対して、リンクを横断したり、nodeをリンクに追加・削除したりする機能を実装している唯一のスタイルがあります。循環リストなので、先頭ノードと終端ノードについて考える必要がありません。単純に、ノードを取り出し、各ノードにあるポインタをたどっていって、また同一のノードが現れるまでたどっていけばいいのです。このアプローチは先頭ノードに対する特殊な実装する必要がありません。各ルーチンはリスト内の単体の要素を指すポインタのみを必要とし、そのポインタはどの要素を指すポインタにもなり得ます。　ここで、実装を実際にみてみたいと思うかもしれません。通常、我々は、linked listを以下のように実装します。

struct my_list{
int data,
struct my_list *prev;
struct my_list *next;
};

しかし、もしlinuxの実装スタイルを採用したいなら、以下のように書くことができます。

struct my_list{
struct list_head list; //linux kernel list implementation//
int data;
};
struct list_head { //Declared in list.h file
struct list_head *next;
struct list_head *prev;
}

　ここで、"list_node"という名前の構造体に注目してください。(http://lwn.net/Articles/237669/)
linuxデベロッパはこの名前をみて、このlistは先頭ノードがないという事実を思い浮かべます。すべてのノードは先頭ノードの様に振る舞います。nextポインタは次の要素をさし、 prevポインタは１つ前のポインタをさすでしょう。linuxの賢いlistの実装に対して感謝しましょう。あなたは先頭ノードと終端ノードに対する考えを忘れることができます。リストを先頭ノードと終端ノードがないおおきなサークルとして比較できます。　各関数においても多くの賢い実装方法が存在します。list.hファイルをみてみましょう。このファイルはしっかりとドキュメントされています。私はこのファイルのドキュメントより良くドキュメントできるとは思えないほどです。list.hの全体をみるのに１時間もかからないと思います。

ここで、いくつかのおおきな質問があります
###1:　自分自身でコーディングしたり、よそからlinked listに関するライブラリを取得できるのに、なぜlinuxカーネルのlinked listの実装を学ぶべきなのでしょうか。

###2: linux linked listのライブラリをどうやって自分のユーザスペースのアプリケーションに利用できるでしょうか。このライブラリを使うことで、どのような利点がもたらされるのでしょうか。

この２つの質問について、回答してみましょう。私の質問に対して満足できないなら、コメントを残してください。

####１に対する回答
#####(1) もしあなたが自分自身を将来のlinuxカーネルハッカーとしてみるならば、このlinked listにみられる戦略を学ばなくてはなりません。著名なカーネルハッカーである Robert Love氏によってかかれた “linux kernel development “ の内容に、良い言葉があります。「すべてのユーザは既存のインターフェースを使うべきです。我々はこの点について非常にシリアスです。車輪の再発明をしないでください。」

#####(2)様々なタイプのデータ構造を作ってみてください。どんなデータ構造でも頭に浮かんでくるようになります。

#####(3)移植性　これがなければ主要なlinuxカーネルのソースツリーに入れることはできません。

#####(4)学習が容易　可読性　学習するのが容易です。あなたはすべての関数を１時間の熱心な学習で学べます。

#####(5)計算量　すべての関数がO(1) (big O notation) の計算時間であることに関心をもつでしょう。O(1)であるということは、リストのサイズに関わらず、定数時間で処理できるということです。

###２に対する回答
list.hに対して小さな修正をほどこして、あなたのユーザスペースのアプリケーションにこのファイルをインクルードさせてください。単一のヘッダーファイルなので扱いやすいです。
修正において、以下のことをする必要があります。
#####(a) #ifdef KERNE と #endif　の部分を削除してください
#####(b) すべての#include行を削除してください
#####(c) rcuに関連するすべての関数を削除してください
私はすでに自分自身ので実装した双方向循環リストと、list.hファイルを利用して、もともとのlinux linked listのものとパフォーマンスを比較してみてください。。。

P.S 　カーネルはlinked listをタスクリストの保持に使っています。　各プロセスのtask_struct　はこのlinked listの要素です。このリンク(http://lxr.linux.no/ident?i=list_add)をみてください。あなたはlist_add関数がどれだけ多くの回数呼び出されているか自然と理解できるでしょう。
参照；私は良質な記事をいくつか読みました。これらの記事をよんで理解しましょう。1　“linux kernel development” Robert Love Appendix A2 linux kernel linked list for user space (http://www.mcs.anl.gov/~kazutomo/list/index.html)3 linux kernel linked list explained ( http://isis.poly.edu/kulesh/stuff/src/klist/)