はじめに
本記事は第三回の続きです。前回までの記事を既に見ていることが前提です。
今回はカーネル内の代表的なデータ構造であるリストについて学びます。その過程で、カーネル内においてメモリを動的に割り当てる方法についても学びます。
リストの構造
リストの構造体の定義は次の通り、双方向リストです。
struct list_head { struct list_head *next, *prev; };
見てわかるように、リストそのものには数値、文字列などの実要素を埋め込むようなフィールドは用意されていません。かわりに、リストそのものを構造体に埋め込むという使い方をします。やや使い方に癖がありますが、慣れてくると非常に便利です1。
では、例としてmylistという名前がついた空のリストがあるとします。リストは次のように初期化します。
static LIST_HEAD(mylist);
行頭のstaticは、リストをモジュール内でのみ使う場合に指定します。そうでない場合はつけなくて構いません。他のモジュールに変数を公開する方法についてはあとの章で述べる予定です。
mylistは次の図のような双方向の構造をしています。
このmylistはnという名前の数値のフィールドをひとつ持つとしましょう。この場合、次のように当該リストのエントリ用の構造体を作成します。
struct mylist_entry { struct list_head list; int n; };
データ構造に直接 pref, next などのリンク構造を示すフィールドを用意せずにリスト専用のデータ構造を埋め込むことによって、このリストを使うあらゆるデータ構造に対して、リストを操作するAPIを1つに統一できるという利点があります。
このリストが1という数値を持つエントリをひとつだけ持つ時、リストは次のような構造になります。
同、1,10,100という3つの数値を持つエントリの場合、次のようになります。
いずれのリストも、リストそのものを示すmylistは意味のある値を全く持たないことに注意してください。
最も単純なリストの使用方法
リストの使用方法を学ぶために、次のようなモジュールを作ります。
- 要素に数値を持つリストを作成する
- モジュールロード時に空のリストmylistに次のような操作をする
- 先頭に1を追加
- 先頭に2を追加
- 先頭に3を追加
- 先頭から2つの要素を削除
- 末尾に4を追加
- 先頭から2つの要素を削除して空にする
- 操作するたびにカーネルログに操作内容と操作後のリストの内容を表示する
ソースは次の通りです。
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/list.h>
MODULE_LICENSE("GPL v2");
MODULE_AUTHOR("Satoru Takeuchi <satoru.takeuchi@gmail.com>");
MODULE_DESCRIPTION("an example of list data structure");
static LIST_HEAD(mylist);
struct mylist_entry {
struct list_head list;
int n;
};
static void mylist_add(int n) {
struct mylist_entry *e = kmalloc(sizeof(*e), GFP_KERNEL);
e->n = n;
list_add(&e->list, &mylist);
printk(KERN_ALERT "mylist: %d is added to the head\n", n);
}
static void mylist_add_tail(int n) {
struct mylist_entry *e = kmalloc(sizeof(*e), GFP_KERNEL);
e->n = n;
list_add_tail(&e->list, &mylist);
printk(KERN_ALERT "mylist: %d is added to the head\n", n);
}
static void mylist_del_head(void) {
struct mylist_entry *e = list_first_entry(&mylist, struct mylist_entry, list);
int n = e->n;
list_del(&e->list);
kfree(e);
printk(KERN_ALERT "mylist: %d is deleted from the head\n", n);
}
static void mylist_show(void) {
struct mylist_entry *e;
printk(KERN_ALERT "mylist: show contents\n");
list_for_each_entry(e, &mylist, list) {
printk(KERN_ALERT "\t%d\n", e->n);
}
}
static int mymodule_init(void) {
mylist_show();
mylist_add(1);
mylist_show();
mylist_add(2);
mylist_show();
mylist_add(3);
mylist_show();
mylist_del_head();
mylist_show();
mylist_del_head();
mylist_show();
mylist_add_tail(4);
mylist_show();
mylist_del_head();
mylist_show();
mylist_del_head();
mylist_show();
return 0;
}
static void mymodule_exit(void) {
/* Do nothing */
}
module_init(mymodule_init);
module_exit(mymodule_exit);
重要なポイントは次の通りです。
- kmalloc()によって動的にメモリを獲得する(ユーザプログラムにおけるmalloc()に相当)。第二引数はメモリ獲得時の諸条件を指定するフラグ。通常GFP_KERNEL。現段階ではあまり気にしなくて良い(後の章で説明予定)
- list_add()によって新規エントリをリスト先頭に追加
- list_add_tail()によって新規エントリをリスト末尾に追加
- list_del()によってエントリをリストから追加(本関数にリストそのものは指定しなくてよいことに注意)
- list_for_each()によってリストの全要素にアクセス
- list_for_each_safe()はlist_for_each()とほぼ同じだが、参照中のエントリを削除しても次の要素を安全に辿れる
- list_first_entry()によってlistの最初の要素を得る
このモジュールをロードすると次のようなログが出力されます。
# dmesg ... [ 6010.587046] mylist: show contents [ 6010.588791] mylist: 1 is added to the head [ 6010.590596] mylist: show contents [ 6010.592209] 1 [ 6010.593883] mylist: 2 is added to the head [ 6010.595695] mylist: show contents [ 6010.597318] 2 [ 6010.598625] 1 [ 6010.600152] mylist: 3 is added to the head [ 6010.601875] mylist: show contents [ 6010.603381] 3 [ 6010.604584] 2 [ 6010.605776] 1 [ 6010.606951] mylist: 3 is deleted from the head [ 6010.608662] mylist: show contents [ 6010.610167] 2 [ 6010.611347] 1 [ 6010.612476] mylist: 2 is deleted from the head [ 6010.614083] mylist: show contents [ 6010.615488] 1 [ 6010.617240] mylist: 4 is added to the head [ 6010.618830] mylist: show contents [ 6010.620254] 1 [ 6010.621378] 4 [ 6010.622476] mylist: 1 is deleted from the head [ 6010.624078] mylist: show contents [ 6010.625443] 4 [ 6010.626501] mylist: 4 is deleted from the head [ 6010.628052] mylist: show contents #
リストを使ったスタックの実装
前節のように、モジュールロード時に処理が全て終わってしまうのはあまり面白くないので、以前学んだdebugfsと今回学んだリストを用いて、ユーザから操作できるスタックをカーネル内に実装してみます。仕様は次の通りです。
- /sys/kernel/debugfs/mystack/以下にインターフェイスを持つ(以下このファイルを単にmystack/と表記)
- mystack/ 以下のファイルによって数値を格納するスタックを操作する。初期状態のスタックは空
- mystack/show からスタックの全要素を示す文字列を読み出す。要素間は空白で区切り、文字列の末尾には改行を置く
- mystack/push に数値を示す文字列を書き込むと、スタックの先頭に対応する要素を追加する。一度に追加できる要素の数は1つ
- mystack/pop を先頭から読み出すと、スタックの先頭要素を示す文字列を読み出した上で当該要素を削除する。先頭以外から読み出すと、何もせずに終了
コードは次の通りです。
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/debugfs.h>
MODULE_LICENSE("GPL v2");
MODULE_AUTHOR("Satoru Takeuchi");
MODULE_DESCRIPTION("a stack example implemented with list");
struct mystack_entry {
struct list_head list;
int n;
};
static LIST_HEAD(mystack);
static void mystack_push(int n) {
struct mystack_entry *e = kmalloc(sizeof(*e), GFP_KERNEL);
e->n = n;
list_add(&e->list, &mystack);
}
static int mystack_pop(int *np) {
struct mystack_entry *e;
if (list_empty(&mystack))
return -1;
e = list_first_entry(&mystack, struct mystack_entry, list);
if (np != NULL)
*np = e->n;
list_del(&e->list);
kfree(e);
return 0;
}
static void mystack_clean_out(void) {
while (!list_empty(&mystack)) {
mystack_pop(NULL);
}
}
static struct dentry *mylist_dir;
static struct dentry *showfile;
static struct dentry *pushfile;
static struct dentry *popfile;
static char testbuf[1024];
static ssize_t show_read(struct file *f, char __user *buf, size_t len, loff_t *ppos)
{
char *bufp = testbuf;
size_t remain = sizeof(testbuf);
struct mystack_entry *e;
size_t l;
if (list_empty(&mystack))
return simple_read_from_buffer(buf, len, ppos, "\n", 1);
list_for_each_entry(e, &mystack, list) {
int n;
n = snprintf(bufp, remain, "%d ", e->n);
if (n == 0)
break;
bufp += n;
remain -= n;
}
l = strlen(testbuf);
testbuf[l - 1] = '\n';
return simple_read_from_buffer(buf, len, ppos, testbuf, l);
}
static ssize_t push_write(struct file *f, const char __user *buf, size_t len, loff_t *ppos)
{
ssize_t ret;
int n;
ret = simple_write_to_buffer(testbuf, sizeof(testbuf), ppos, buf, len);
if (ret < 0)
return ret;
sscanf(testbuf, "%20d", &n);
mystack_push(n);
return ret;
}
static ssize_t pop_read(struct file *f, char __user *buf, size_t len, loff_t *ppos)
{
int n;
if (*ppos || mystack_pop(&n) == -1)
return 0;
snprintf(testbuf, sizeof(testbuf), "%d\n", n);
return simple_read_from_buffer(buf, len, ppos, testbuf, strlen(testbuf));
}
static struct file_operations show_fops = {
.owner = THIS_MODULE,
.read = show_read,
};
static struct file_operations push_fops = {
.owner = THIS_MODULE,
.write = push_write,
};
static struct file_operations pop_fops = {
.owner = THIS_MODULE,
.read = pop_read,
};
static int mymodule_init(void)
{
mylist_dir = debugfs_create_dir("mystack", NULL);
if (!mylist_dir)
return -ENOMEM;
showfile = debugfs_create_file("show", 0400, mylist_dir, NULL, &show_fops);
if (!showfile)
goto fail;
pushfile = debugfs_create_file("push", 0200, mylist_dir, NULL, &push_fops);
if (!pushfile)
goto fail;
popfile = debugfs_create_file("pop", 0400, mylist_dir, NULL, &pop_fops);
if (!popfile)
goto fail;
return 0;
fail:
debugfs_remove_recursive(mylist_dir);
return -ENOMEM;
}
static void mymodule_exit(void)
{
debugfs_remove_recursive(mylist_dir);
mystack_clean_out();
}
module_init(mymodule_init);
module_exit(mymodule_exit);
コード量は若干多いですが、これまでに学んだdebugfsとlistの使い方を知っていれば、それほど難しくないです。以下にポイントを示します。
- list_empty()によってリストが空かどうかを確認する。空なら1, そうでなければ0を返す
使用例を以下に示します。
root@packer-qemu:/home/vagrant# ls /sys/kernel/debug/mystack ls: cannot access '/sys/kernel/debug/mystack': No such file or directory root@packer-qemu:/home/vagrant# insmod /vagrant/list2.ko root@packer-qemu:/home/vagrant# ls /sys/kernel/debug/mystack pop push show root@packer-qemu:/home/vagrant# cat /sys/kernel/debug/mystack/show; for ((i=0;i<5;i++)) ; do echo $i >/sys/kernel/debug/mystack/push; cat /sys/kernel/debug/mystack/show; done 0 1 0 2 1 0 3 2 1 0 4 3 2 1 0 root@packer-qemu:/home/vagrant# for ((i=0;i<5;i++)) ; do cat /sys/kernel/debug/mystack/pop; done 4 3 2 1 0 root@packer-qemu:/home/vagrant# cat /sys/kernel/debug/mystack/show root@packer-qemu:/home/vagrant# cat /sys/kernel/debug/mystack/pop root@packer-qemu:/home/vagrant#
うまく動いているようです。他にも自分で色々動かしてみて下さい。
重大バグ
既に気づいたかたがいるかもしれませんが、このスタックはサイズに制限が無いので、ユーザから無制限に値をpushできてしまいます。そのたびにカーネル内の対応するデータ構造をメモリ上に確保します。このようなことをすると、カーネルの空きメモリをゼロになるまで食いつぶそうとするため、その過程でいわゆる Out of Memory(OOM)が発生します。そうするとデフォルトではOOM killerというカーネルの処理が走り、カーネルが選んだ適当なプロセスを殺戮してメモリの空き容量を増やそうとします。
次のようなコマンドの実行中に別のshellからVMのシリアルコンソールを覗いた結果を示します。
root@packer-qemu:/home/vagrant# for ((i=0;i=1000000000;i++)) ; do echo $i >/sys/kernel/debug/mystack/push; done```
コマンドを実行してしばらく経つと、シリアルコンソールに次のようなメッセージが表示されます。
$ virsh console elkdat_ktest ... [94417.067862] Kernel panic - not syncing: Out of memory and no killable processes... [94417.067862] [94417.067864] CPU: 0 PID: 1 Comm: systemd Tainted: G W O 4.9.0-ktest #1 [94417.067864] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.9.3-20161025_171302-gandalf 04/01/2014 [94417.067866] ffffbbfa000d2dd8 ffffffffaa3ffa12 ffffffffaae0e500 ffffffffaac802f8 [94417.067867] ffffbbfa000d2e60 ffffffffaa19bfb8 ffff9e7600000008 ffffbbfa000d2e70 [94417.067868] ffffbbfa000d2e08 00000000fd454624 00000000000000b5 0000000000000000 [94417.067869] Call Trace: [94417.067871] [<ffffffffaa3ffa12>] dump_stack+0x63/0x81 [94417.067874] [<ffffffffaa19bfb8>] panic+0xe4/0x22d [94417.067876] [<ffffffffaa1a2e9b>] out_of_memory+0x33b/0x490 [94417.067877] [<ffffffffaa1a82c4>] ... [94417.067988] [<ffffffffaa22f635>] SyS_write+0x55/0xc0 [94417.067990] [<ffffffffaa243159>] ? SyS_ioctl+0x79/0x90 [94417.067992] [<ffffffffaa84a2bb>] entry_SYSCALL_64_fastpath+0x1e/0xad [94417.068363] Kernel Offset: 0x29000000 from 0xffffffff81000000 (relocation range: 0xffffffff80000000-0xffffffffbfffffff) [94417.947136] ---[ end Kernel panic - not syncing: Out of memory and no killable processes...
メモリ大量獲得の真犯人であるmystackはカーネル内のデータ構造なので、いかなるプロセスを削除しようとも空きメモリ量は回復しません。このため、カーネルはどうすることもできなくなり、パニックしています。これはカーネルの処理に問題があるとシステム全体が正しく動作しなくなるという良い例です。この問題の修正については後述の演習として残しておきます。
演習問題
- mystackの長さを10に制限する。要素数が10の時にmystack/ に書き込むとEINVALを返す(mystack/push の書き込みハンドラが -EINVALを返せばよい)
- mystackの要素を数値ではなく文字列(char *)にする。要素ごとの文字列の長さ(strlen()の戻り値)は最長10
mystackを改造してmyqueueというキューを作成する
/sys/kernel/debug/myqueue(以下 myqueue/ と表記)がキューに対応
- 要素は数値
- キューの長さは最長１０
- myqueue/show を読むことによって現在のリストの一覧を得られる
- myqueue/queue へ書き込んだ文字列に対応する数値(1つ)をキューの末尾に追加する
- myqueue/dequeue を読むことによってキューの先頭要素を得ると共に、当該要素をキューから削除する
おわりに
今回使ったソースはexample/module/list以下に置いています。実はmystackには、リスト長の問題を解決してなお、排他制御という観点から見て重大な問題があります。次回は排他制御の基本について述べます。その過程でこの問題も解決します。
参考資料
- カーネルソースのinclude/linux/list.h: 本章で紹介したもの以外にも沢山のリスト操作関数が定義されている。名前は”list_”で始まる
- LinuxにおけるOOM発生時の挙動
