Linux Kernel: List構造を操作するためのAPI(Listの使い方)

前書き

C言語は、言語としてList構造およびList操作APIをサポートしていません。ここでのList構造とは、「次のデータ(前のデータ)へのポインタ」を意味します。本記事では、データとList構造(nextポインタ、prevポインタ)をセットにした状態をノードと呼びます。

List操作APIが無い状態では、大規模なデータ管理が困難になりやすいです。そのため、Linux Kernelは独自のLinked Lists APIを持ちます。Kernel開発を行う上で、List操作の知識は最低限必要な知識です。本記事では、Kernel内部のLinked Lists APIの使い方を以下の順番で説明します。

Linux Kernel Linked Listsの説明順
  • 一般的なList構造とその欠点
  • Linux KernelのList構造
  • List構造の初期化(動的)
  • List構造の初期化(静的)
  • List構造に要素を追加
  • List構造から要素を削除
  • List構造からデータを参照
  • List構造のシーケンシャル探索(for文)

                                     

一般的なList構造とその欠点

KernelのList構造に触れる前に、一般的なList構造について説明します。C言語の参考書では、List構造は「データ」と密結合の場合が多いです。以下にコード例として、NUM_LIST構造体を示します。NUM_LIST構造体は、List構造(nextポインタ)として、NUM_LIST構造体のポインタを持ちます。

NUM_LIST構造体をLinkさせた図は、以下の通りです。3個のノードが結ばれた状態です。

このような密結合のList構造における欠点は、「データ毎(構造体毎)にList操作用のAPIを実装しなければならない」という事です。例えば、NUM_LIST構造体に対して、要素を追加する関数add_num_list(以下)を作成したとします。list_add_num()がNUM_LIST構造体にしか使用できない事は、C言語経験者であれば容易に想像できると思います。

例えば、”char data[256];”を持つCHAR_LIST構造体を実装した場合、API(上記の例では、list_add_num)の再実装が必要です。この点が、密結合のLink構造の欠点(面倒臭さ)と言えます。

                                  

Linux KernelのList構造

Linux KernelのList構造は、データと分離されており、粗結合の状態です。定義は、$(Linux Kernel Top Directory)/include/linux/types.hに存在し、以下のような実装です。List構造(list_head構造体)へのnextポインタ、prevポインタを持つだけのシンプルな内容です。

「一般的なList構造とその欠点」で説明したNUM_LIST構造体をKernel方式に実装し直すと、以下のような形式になります。基本的には、データ構造(構造体)の中に、List構造(list_head構造体)を追加する形となります。

Linux Kernel形式でNUM_LIST構造体をLinkさせた図(単方向のみLinkさせた図)は、以下の通りです。

Linux Kenel形式のList構造の利点は、データ構造(構造体)に応じて、List操作APIを再実装する必要性が無い事です。この利点は、データ構造とList構造が互いに影響しない事(粗結合である事)によって、実現されています。

勘の良い方は、「List構造をnext->next->…と辿れるけど、肝心のデータにアクセスできないのではないか」と考えたかもしれません。Linux Kernelは、「List構造のポインタ」から「List構造を含むデータ構造体の先頭ポインタ」を得るマクロが用意されています(後述)。そのため、List構造ポインタからデータにアクセス可能です。

                                  

List構造の初期化(動的)

Linux Kernel内で、動的にList構造を初期化する場合、INIT_LIST_HEADマクロを使用します。初期化例は、以下の通りです。

INIT_LIST_HEADの定義は、$(Linux Kernel Top Directory)/include/linux/list.hにあり、以下の通りです。list_head構造体のnextポインタ、prevポインタの指すアドレスを初期化対象のlist_head構造体自身にします。

実装中のWRITE_ONCEマクロは、GCC最適化によってコードが意図せぬ結果にならないよう、実装段階で防止するAPIです。Stack overflowに、この点に関する回答があります。以下に引用・和訳します。

Read/write “tearing” : replacing a single memory access with many smaller ones. GCC may (and does!) in certain situations replace something like p = 0x01020304; with two 16-bit store-immediate instructions -instead of presumably placing the constant in a register and then a memory access, and so forth. WRITE_ONCE would allow us to say to GCC, “don’t do that”, like so: WRITE_ONCE(p, 0x01020304);

(和訳)

Read/write処理が”引き裂かれる(分割される)”: 単一のメモリアクセスを多数の小さなメモリアクセスに置き換えます。p=0x01020304のような値を置き換える状況下で、GCCはレジスタの中に定数を格納した後にメモリアクセスする等の代わりに、2つの16bit store immediate命令に置き換える事ができます(そして、そうします!)。WRITE_ONCEマクロは、私達がGCCに”余計な事をするな!”と言う事ができます。例えば、WRITE_ONCE(p, 0x01020304);と書く事によって。

                              

List構造の初期化(静的)

Linux Kernel内で、静的にList構造を初期化する場合、LIST_HEADマクロを使用します。ここでの静的とは、List構造(list_head構造体)の変数宣言時という意味です。LIST_HEADマクロをコールすると、新しいlist_head構造体(list)が作成され、初期化済みの状態になります。初期化例は、以下の通りです。

LIST_HEADマクロの定義は、$(Linux Kernel Top Directory)/include/linux/list.hにあり、以下の通りです。list_head構造体の2つの変数(nextポインタ、prevポインタ)に対して、初期化対象のlist_head構造体アドレスを渡しています。

                                        

List構造に要素を追加

List構造に要素を追加する場合、list_add()か、list_add_tail()を使用します。まず、関数list_add()の使用例を以下に示します。

list_add()には、第一引数に追加対象の要素(list_head構造体)、第二引数にList構造(list_head構造体)を指定します。要素の追加先は、第二引数で指定したList構造の次になります。

list_add()の実装は、$(Linux Kernel Top Directory)/include/linux/list.hに存在します。list_add()自体はラッパーであり、次に呼ぶ__list_add()の中でポインタ操作をします。

list_add_tail()には、list_add()と同じように、第一引数に追加対象の要素(list_head構造体)、第二引数にList構造(list_head構造体)を指定します。要素の追加先は、第二引数で指定したList構造の前(=Listの最後尾)になります。使用例は、以下の通りです。

list_add_tail()の実装は、以下の通りです。list_add()と渡しているポインタが異なるだけで、内部的な作りは、殆ど同じです。

                                    

List構造から要素を削除

List構造から要素を削除する場合、list_del()を使用します。使用方法は、削除対象のList構造(list_head構造体)を引数として渡すだけです。しかし、削除と言いつつ、ポインタの連結を変更しているだけなので、データ構造が確保していたメモリは解放されません。そのため、list_del()を呼ぶ前に、データ構造が使用したメモリを解放しなければいけません。

以下、list_del()の使用例です。

list_del()の実装は、$(Linux Kernel Top Directory)/include/linux/list.hに存在します。list_add()と同じく、list_del()自体はラッパーであり、次に呼ぶ__list_del()の中でポインタ操作をします。実装中のLIST_POISON1/LIST_POISON2は、誤って削除済みのList構造にアクセスした際に気づく事ができるよう、削除済みのList構造が持つポインタにNULL以外のアドレスを代入しています。

                                    

List構造からデータを参照

List構造からデータを参照するには、list_entry()を使用します。list_entry()は、「List構造(list_head構造体)のポインタ」から「List構造を含むデータ構造体の先頭ポインタ(例:前述のNUM_LIST構造体の先頭ポインタ)」を得る事ができます。

以下に、使用例(疑似コードチック)を示します。

list_entry()の実装は、$(Linux Kernel Top Directory)/include/linux/list.hに存在します。以下に示す通り、list_entryはcontainer_ofマクロを呼ぶためのラッパーです。第一引数ptrには構造体のメンバポインタ、第二引数typeには第一引数ptrが指す構造体メンバを含む構造体名、第三引数memberには第一引数ptrが指す構造体メンバの名称を渡します。

container_ofマクロの仕様に関しては、別記事で詳細に記載しています。

Linux Kernel: 構造体メンバポインタから構造体の先頭ポインタを得るcontainer_ofマクロ

                                                     

List構造のシーケンシャル探索(for文)

List構造のシーケンシャル探索(for文)には、list_for_each_entry()を使用します。List構造用のfor文は複数個ありますが、今回は一つだけの紹介とします。

以下に使用例(疑似コードチック)を示します。

list_for_each_entry()の実装は、$(Linux Kernel Top Directory)/include/linux/list.hに存在します。以下に示す通り、第一引数posにはループカーソル(iterator)となるデータ構造体ポインタ、第二引数にはList構造のhead(先頭)、第三引数にはデータ構造体に含まれるList構造(list_head構造体)の名称を渡します。

list_for_each_entry()は、for文を作成しているだけです。前提として、C言語のfor文は、”for (初期化; 条件式; 変化式)”で表されます。

まず、for文の初期化部分は、list_first_entry()でList構造(list_head構造体)の先頭ポインタ(iterator)を取得しています。次に、条件式は「データ構造が持つList構造が指すポインタ」!=「List構造体の先頭ポインタ」です。最後に、変化式はlist_next_entry()で、iteratorを次のList構造ポインタに変更しています。

                                        

最後に

本記事で説明した内容で、Linked Listを用いたDevice Driverを作成しています。Listの使い方をより具体的に知りたい場合は、以下の記事を確認して下さい。

Linux Kernelの簡単なCharacter Deviceを作成する方法(Linked List APIの使用方法サンプル)

本記事が説明しているLinux KernelのList操作APIは、必要最低限な内容のみです。他にも、Linux Kernelには、List操作用のAPIが定義されています。今後、List操作APIの第二弾として、別記事を作成予定です。

                                          

あわせて読みたい

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です