カーネルモジュール作成によるlinuxカーネル開発入門 - 第五回 排他制御

前回作成したスタックは、手元の端末でみなさんが対話的に操作しているうちは何も問題が起きません。しかし、このスタックを複数の処理が同時に操作した場合は問題が発生します。今回は、前回作成したスタックにどのような問題が存在しているのか、および、それを排他制御という仕組みによって解決する方法について述べます。

まずは今回用いるスタック作成モジュール用のソースを次に示します。前回作成したlist2.cのものに加えて、スタックのサイズを最大10に制限しています。

#include <linux/module.h>
#include <linux/slab.h>
#include <linux/debugfs.h>

MODULE_LICENSE("GPL v2");
MODULE_AUTHOR("Satoru Takeuchi");
MODULE_DESCRIPTION("a example of mutual exclusion by using mutex");

struct mystack_entry {
    struct list_head list;
    int n;
};

#define MYSTACK_MAX_LEN 10

static LIST_HEAD(mystack);
static int mystack_len;

static void mystack_push(int n) {
    struct mystack_entry *e;

    if (mystack_len >= MYSTACK_MAX_LEN) {
        return;
    }
    e = kmalloc(sizeof(*e), GFP_KERNEL);
    INIT_LIST_HEAD(&e->list);
    e->n = n;
    list_add(&e->list, &mystack);
    ++mystack_len;
}

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);
    --mystack_len;
    kfree(e);

    return 0;
}

static void mystack_clean_out(void) {
    while (!list_empty(&mystack)) {
        mystack_pop(NULL);
        --mystack_len;
    }
}

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;
    ssize_t ret;

    if (list_empty(&mystack)) {
        ret = simple_read_from_buffer(buf, len, ppos, "\n", 1);
        return ret;
    }

    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';
    ret =  simple_read_from_buffer(buf, len, ppos, testbuf, l);

    return ret;
}

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;
    ssize_t ret;
    
    if (*ppos || mystack_pop(&n) == -1) {
        return 0;
    }
    snprintf(testbuf, sizeof(testbuf), "%d\n", n);
    ret = simple_read_from_buffer(buf, len, ppos, testbuf, strlen(testbuf));
    return ret;
}

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);

次に示すのは、大量のプロセスが同時に、かつ適当にスタックを操作するという拷問プログラムです。

#!/bin/bash

TOPDIR=/sys/kernel/debug/mystack

for ((i=0;j<10000;j++)) ; do
    echo 0 >${TOPDIR}/push &
    cat ${TOPDIR}/show >/dev/null &
    cat ${TOPDIR}/pop >/dev/null &
done

別の端末上でVMのシリアルコンソールに接続します。

shell-session:
$ virsh console elkdat_ktest
Connected to domain elkdat_ktest
Escape character is ^]


Ubuntu 16.04.1 LTS packer-qemu ttyS0

packer-qemu login:

lock1.koをロードした状態で、拷問プログラムを動作させます。

...
root@packer-qemu:/home/vagrant# insmod /vagrant/list2.ko
root@packer-qemu:/home/vagrant# /vagrant/lock-torture
root@packer-qemu:/home/vagrant#
...

このとき次のようなメッセージがシリアルコンソール上に大量に表示されます。

...
[ 2186.660837] BUG: unable to handle kernel NULL pointer dereference at 0000000000000010
[ 2186.661890] IP: [<ffffffffc02910d5>] show_read+0x65/0x110 [lock1]
[ 2186.662618] PGD 1cce9067 [ 2186.662958] PUD 1cce8067 
PMD 0 [ 2186.663438] 
[ 2186.663643] Oops: 0000 [#1] SMP
[ 2186.664082] Modules linked in: lock1(O) crct10dif_pclmul crc32_pclmul ppdev aesni_intel aes_x86_64 glue_helper lrw gf128mul ablk_helper cryptd input_leds joydev serio_raw parport_pc parport mac_hid i2c_piix4 sunrpc autofs4 cirrus drm_kms_helper syscopyarea sysfillrect sysimgblt fb_sys_fops psmouse floppy ttm drm pata_acpi [last unloaded: lock1]
[ 2186.668308] CPU: 1 PID: 7243 Comm: cat Tainted: G           O    4.9.0-ktest #1
[ 2186.669215] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Ubuntu-1.8.2-1ubuntu1 04/01/2014
[ 2186.670379] task: ffff8d3dd7c563c0 task.stack: ffffa0f3c1534000
[ 2186.671118] RIP: 0010:[<ffffffffc02910d5>]  [<ffffffffc02910d5>] show_read+0x65/0x110 [lock1]
[ 2186.672246] RSP: 0018:ffffa0f3c1537dd0  EFLAGS: 00010203
[ 2186.672981] RAX: 0000000000000002 RBX: 00000000000003fe RCX: 0000000000000000
[ 2186.673801] RDX: 0000000000000001 RSI: ffffffffc0292029 RDI: 0000000000000000
[ 2186.674598] RBP: ffffa0f3c1537e00 R08: 0000000000000000 R09: 0000000000000000
[ 2186.675396] R10: 000000000000037b R11: ffffffffc0293681 R12: 0000000000020000
[ 2186.676193] R13: ffffa0f3c1537f18 R14: 0000000000000000 R15: ffffffffc0293682
[ 2186.677004] FS:  00007f94815eb700(0000) GS:ffff8d3ddfd00000(0000) knlGS:0000000000000000
[ 2186.677910] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[ 2186.678566] CR2: 0000000000000010 CR3: 000000001ba56000 CR4: 00000000000406e0
[ 2186.679360] Stack:
[ 2186.679640]  00007f94815c9000 ffff8d3ddd2e7d80 0000000000000001 ffffffffc0293200
[ 2186.680561]  ffff8d3dde0add00 0000000000020000 ffffa0f3c1537e48 ffffffff893deeb4
[ 2186.681554]  00007f94815c9000 ffffa0f3c1537f18 ffff8d3dde0add00 ffffa0f3c1537f18
[ 2186.682540] Call Trace:
[ 2186.682930]  [<ffffffff893deeb4>] full_proxy_read+0x54/0x90
[ 2186.683636]  [<ffffffff8922bd27>] __vfs_read+0x37/0x150
[ 2186.684292]  [<ffffffff894bea7b>] ? security_file_permission+0x9b/0xc0
[ 2186.685037]  [<ffffffff8922cf03>] vfs_read+0x93/0x130
[ 2186.685659]  [<ffffffff8922e405>] SyS_read+0x55/0xc0
[ 2186.686239]  [<ffffffff8906c807>] ? trace_do_page_fault+0x37/0xe0
[ 2186.686933]  [<ffffffff899a24bb>] entry_SYSCALL_64_fastpath+0x1e/0xad
[ 2186.687658] Code: bb 00 04 00 00 49 c7 c7 80 36 29 c0 49 81 fe f0 32 29 c0 75 16 eb 2e 4d 8b 36 48 98 49 01 c7 48 29 c3 49 81 fe f0 32 29 c0 74 1a <41> 8b 4e 10 48 c7 c2 26 20 29 c0 48 89 de 4c 89 ff e8 15 1e 2d 
[ 2186.690753] RIP  [<ffffffffc02910d5>] show_read+0x65/0x110 [lock1]
[ 2186.691475]  RSP <ffffa0f3c1537dd0>
[ 2186.691913] CR2: 0000000000000010
[ 2186.695397] ---[ end trace 83771c8afec0d8dc ]---
....

上記ログの中でとくに注目すべきは次の部分です。

...
[ 2186.660837] BUG: unable to handle kernel NULL pointer dereference at 0000000000000010    # ... (1)
[ 2186.661890] IP: [<ffffffffc02910d5>] show_read+0x65/0x110 [lock1]              # ... (2)
...
[ 2186.682540] Call Trace:
[ 2186.682930]  [<ffffffff893deeb4>] full_proxy_read+0x54/0x90
[ 2186.683636]  [<ffffffff8922bd27>] __vfs_read+0x37/0x150
[ 2186.684292]  [<ffffffff894bea7b>] ? security_file_permission+0x9b/0xc0
[ 2186.685037]  [<ffffffff8922cf03>] vfs_read+0x93/0x130
[ 2186.685659]  [<ffffffff8922e405>] SyS_read+0x55/0xc0                       # ... (3)
[ 2186.686239]  [<ffffffff8906c807>] ? trace_do_page_fault+0x37/0xe0
[ 2186.686933]  [<ffffffff899a24bb>] entry_SYSCALL_64_fastpath+0x1e/0xad
...

ここから次のことがわかります。

  • read()システムコールを発行した延長で(ログ内の(2)の部分)、show_read()関数の実行中に問題が発生した(ログ内の(2)の部分)
  • カーネルがNULLポインタにアクセスした(ログ内の(1)の部分)にアクセスした

このようなことが起きた理由は、lock1.koが提供しているスタックの実装に使っているmystackに複数の処理が同時にアクセスしたものの、mystackは同時アクセスに耐えない作りになっていることです。これが具体的にどういうことなのかを、これから明らかにしています。

空のmystackにa, bという2つの要素をpushする場合を考えます。このとき、カーネルの中では次に示すlist_add()が二回呼ばれます1。

...
static inline void list_add(struct list_head *new, struct list_head *head)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next, new;
}
...
static list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}
...

まずは正しく動作する、2つのpush処理A, Bが順番に動くケースについて記載します。コードで表現すると、次のようになります。

処理A         処理B
==================================================
mystack->prev = a;
a->next = mystack;
a->prev = mystack;
mystack->next, a;
            a->prev = b;
            b->next = a;
            b->prev = mystack;
            mystack->next, b;

図で書くと次のようになります。

f:id:satoru_takeuchi:20200329052929p:plain

ややわかりにくいですが、こちらは正しく動作しています。mystackからnextをたどっていくとmystack->b->a->mystackと循環しており、かつ、prevをたどっていくと、mystack->a->b->mystackと循環していることがわかります。

続いて2つのpushが同時に動くケースについて記載します。コードで表現すると、次のようになります。

処理A         処理B
=================================================
mystack->prev = a;
            mystack->prev = b;
a->next = mystack;
            b->next = mystack;
a->prev = mystack;
            b->prev = mystack;
mystack->next, a;
            mystack->next, b;

図で書くと次のようになります。

f:id:satoru_takeuchi:20200329052943p:plain

これはmystack内のリンク関係が無茶苦茶になっています。mystackにはbしか繋がっていない状態です。mystackからnextをたどっていくと、mystack->b->mystackと循環しており、かつ、prevをたどっていくと、mystack->b->mystackと循環しています。その一方でaはprevもnextもmystackを指しており、自分ではmystackに繋がっているつもりになっています。この後何が起きても不思議では無い状態です。拷問プログラムの動作時において、この問題はNULLポインタへのアクセスという障害として顕在化しました。

「同時に複数の処理が動く」と一口に言っても、その組み合わせは様々です。その上、list2.koではlist_add()とlist_del()以外にもlist_empty()などの他の処理も同時多発的に動きますので、拷問プログラムにおいて実際にどのように問題が顕在化するのかは毎回異なります。したがって、みなさんの環境では、冒頭で示したものとは異なるスタックトレースが見えるかもしれません。

ここでの問題の本質は、mystackに同時にアクセスしてしまったことです。これを避けるために、クリティカルセクションと呼ばれる特定のコード領域には、ただ1つの処理しか同時に侵入できないようにします。これを排他制御と呼びます(ようやく今回のタイトルの文言が出てきました)。

排他制御をする方法にはいろいろありますが、ここではmutextという方法を使います。mutexを使うには、次のような手順を踏みます。

  1. クリティカルセクションを定義する。ここではmystackを操作する箇所全てが該当する。それに加えて、testbufを操作する箇所も含める。これまで述べなかったが、testbufも複数処理から同時に更新されるとユーザからの入出力値が不正なものになる可能性がある。
  2. クリティカルセクションを保護するためのmutex(struct mutex型の変数)を定義する。ここではmystack_mutexとする。
  3. クリティカルセクションの前後に必ずmutexを獲得/開放する。

1は済んでいますから、2以降をコードに落としましょう。まずは2のmutexの定義から。

static DEFINE_MUTEX(mystack_mutex);

続いて3のmutexを使用するコードを書きます。例としてmystackに新要素をpushするpush_write()関数内を、mutexを用いて排他制御するように変更します。

...
static ssize_t push_write(struct file *f, const char __user *buf, size_t len, loff_t *ppos)
{
    ssize_t ret;
    int n;

    mutex_lock(&mystack_mutex);
    ret = simple_write_to_buffer(testbuf, sizeof(testbuf), ppos, buf, len);
    if (ret < 0) {
        mutex_unlock(&mystack_mutex);
        return ret;
    }
    sscanf(testbuf, "%20d", &n);
    mystack_push(n);
    mutex_unlock(&mystack_mutex);

    return ret;
}
...

クリティカルセクションに入る前にmutex_lock()によってmutextを獲得し、そこを抜けたらmutex_unlock()によってmutexを開放しています。mutex_lock()の中では

  1. mutexが未獲得なら、獲得して先に進む
  2. mutexが獲得済みならmutexが開放されるまで待つ

という処理をします。これによって、複数の処理が同時にクリティカルセクションに入れなくなります。例えばリストへの同時アクセスだけに注目してみると、処理の流れが次のようになるためにmystackの破壊は防げます。

処理A             処理B
==========================================================================
mutex_lock(&mystack_mutex); #   mutex獲得
mystack->prev = a;
                mutex_lock(mystack_mutex);
a->next = mystack;       ... # ここからmutex獲得待ち
a->prev = mystack;       ...
mystack->next, a;        ...
mutex_unlock(&mystack_mutex);   ... # ここでmutex獲得
                mystack->prev = b;
                b->next = mystack;
                b->prev = mystack;
                mystack->next, b;
                mutex_unlock(&mystack_mutex);

mutexを用いてlock1.cを書き直したものが次のリストです。

#include <linux/module.h>
#include <linux/slab.h>
#include <linux/debugfs.h>

MODULE_LICENSE("GPL v2");
MODULE_AUTHOR("Satoru Takeuchi");
MODULE_DESCRIPTION("a example of mutual exclusion by using mutex");

struct mystack_entry {
    struct list_head list;
    int n;
};

#define MYSTACK_MAX_LEN 10

static LIST_HEAD(mystack);
static int mystack_len;
static DEFINE_MUTEX(mystack_mutex);

static void mystack_push(int n) {
    struct mystack_entry *e;

    if (mystack_len >= MYSTACK_MAX_LEN) {
        return;
    }
    e = kmalloc(sizeof(*e), GFP_KERNEL);
    INIT_LIST_HEAD(&e->list);
    e->n = n;
    list_add(&e->list, &mystack);
    ++mystack_len;
}

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);
    --mystack_len;
    kfree(e);

    return 0;
}

static void mystack_clean_out(void) {
    mutex_lock(&mystack_mutex);
    while (!list_empty(&mystack)) {
        mystack_pop(NULL);
        --mystack_len;
    }
    mutex_unlock(&mystack_mutex);
}

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;
    ssize_t ret;

    mutex_lock(&mystack_mutex);
    if (list_empty(&mystack)) {
        ret = simple_read_from_buffer(buf, len, ppos, "\n", 1);
        mutex_unlock(&mystack_mutex);
        return ret;
    }

    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';
    ret =  simple_read_from_buffer(buf, len, ppos, testbuf, l);
    mutex_unlock(&mystack_mutex);

    return ret;
}

static ssize_t push_write(struct file *f, const char __user *buf, size_t len, loff_t *ppos)
{
    ssize_t ret;
    int n;

    mutex_lock(&mystack_mutex);
    ret = simple_write_to_buffer(testbuf, sizeof(testbuf), ppos, buf, len);
    if (ret < 0) {
        mutex_unlock(&mystack_mutex);
        return ret;
    }
    sscanf(testbuf, "%20d", &n);
    mystack_push(n);
    mutex_unlock(&mystack_mutex);

    return ret;
}

static ssize_t pop_read(struct file *f, char __user *buf, size_t len, loff_t *ppos)
{
    int n;
    ssize_t ret;
    
    mutex_lock(&mystack_mutex);
    if (*ppos || mystack_pop(&n) == -1) {
        mutex_unlock(&mystack_mutex);
        return 0;
    }
    snprintf(testbuf, sizeof(testbuf), "%d\n", n);
    ret = simple_read_from_buffer(buf, len, ppos, testbuf, strlen(testbuf));
    mutex_unlock(&mystack_mutex);
    return ret;
}

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);

これをロードした後にlock-tortureを実行しても問題は発生しません。試してみてください。

演習問題

  • 第三回の debugfs3.c にも排他制御にまつわる問題があります。これについて、何が問題なのかを明らかにして、mutexを用いて問題が発生しないようにする。

おわりに

排他制御にはmutex以外にも様々な種類がありますが、すべてを紹介するにはまだ早いので、まずはここまで。ここでは、mutexの概念と、それを使用するために必要な手順だけを覚えていただければよいです。次回は多分デバイスドライバもどきを作成する予定です。

本章で作成したソースと同じものをexample/module/lock以下に配置しています。

  1. 実際のものはデバッグ用のコードが入っていたりしてもう少し複雑ですが、ここでは簡略化しています。↩