逆ポーランド計算機カーネルモジュール(仮)を作ってみる #Linux

遅ればせながらLinux Advent Calendar 2021 3日目の記事です。
今日はカーネル内部で動作する逆ポーランド計算機をカーネルモジュールとして作ってみた話をしようと思います。

サンプルのソースコードはGistに置いてありますので、興味のある方はご覧いただければと思います。

furandon-pig/krpn.c

逆ポーランド記法

ご存知の方も多いと思いますが、まずは簡単に逆ポーランド記法を解説します。
これは演算子を後ろに置いて式を記述する「後置記法」と呼ばれる類の数式記法になります。

逆ポーランド記法

細かい説明はWikipediaを参照してもらうとして、逆ポーランド記法での簡単な数式を示します。
例えば、私たちが普通に記述する数式で (3 + 4) * (1 - 2) は、逆ポーランド記法で 3 4 + 1 2 - * と表現されます。

(3 + 4) * (1 - 2)  # 中置記法(いつも使っている数式の記法)
3 4 + 1 2 - *      # 後置記法(逆ポーランド記法)

後置記法(逆ポーランド記法)の特徴として、カッコを使わなくても演算子の優先順位を示すことができるという点があります。これは数式を処理する際にもメリットがあり、演算結果をスタックに積んで順次処理して行き、最後にスタックに残った値が演算結果となります。このシンプルな演算方法が適用できるため、逆ポーランド記法で計算するプログラムを練習用に書いたことがある人も多いのではないでしょうか。

加えて、中置記法を日本語で読み下すと後置記法(逆ポーランド記法)に変換できるため、(ある意味)サンプルとなる逆ポーランド記法の数式は簡単に用意することができます。

逆ポーランド計算機カーネルモジュール(仮)

さて、この逆ポーランド記法を処理するプログラムですが、ユーザランド上で作ると簡単に作成できてしまうため芸(？)がありません。Linux Advent Calendarということもあり、ここはひとつ、カーネル内で逆ポーランド記法を処理する「逆ポーランド計算機カーネルモジュール(仮)」を作ってみましょう。

まずは設計：どういうインタフェースにする？

カーネルモジュールとして実装するにあたり、どういったインタフェースにするかをあらかじめ考えておくと作業内容が明確になりそうです。先述したように、後置記法ではスタックを用いて処理できるため、スタックへのpush/popと親和性の良いインタフェースを用いるのが良さそうです。

この観点で考えてみると、 /proc ファイルシステムを利用するのがしっくりきます。以下のように、スタックへのpush/popを /proc への書き込み・読み込みとして見せることで、ユーザランド・カーネルランドの双方で無理なくデータのやりとりが可能になります。

スタックの操作	`/proc` で対応させる操作
push	`echo 1 > /proc/krpn`
pop	`cat /proc/krpn`

というワケで /proc への読み書き処理とカーネル内部での逆ポーランド記法計算処理を実装すれば「逆ポーランド計算機カーネルモジュール(仮)」を作ることができそうです。

/procへの書き込み

さっそく /proc への書き込み処理から実装してみます。確か以前のLinux Advent Calendarの記事でカーネルモジュールの作成方法を記事にまとめていたような…、と思いながら見返すと前に以下の記事を書いていたことを思い出しました。

Linuxカーネルモジュールにsysctl変数を追加してみる

が、よく見るとこれは sysctl 変数をカーネルモジュールから扱うというサンプルで、今回実装する「 /proc の読み書き」にはそのまま転用できなさそうです…。
(カーネルモジュールの基本的なひな型としては応用可能)

調べてみたところ、 proc_create() で /proc のインタフェースを作成し、その際に struct proc_ops.proc_write に紐づけた関数が /proc への書き込み時に呼び出されるという流れになっています。

この例では struct proc_ops.proc_write = proc_krpn_write() としており、 proc_krpn_write() の中で copy_from_user() を呼び出すことでユーザランドから渡されてきた値を取得できます。

一点注意が必要なのでは、ユーザランドからは echo 1 > /proc/krpn といった形で /proc に書き込むと思いますが、改行文字がついてくるので、データを受け取ったカーネル側で必要に応じて改行文字を除去する必要があります。

static struct proc_ops seq_file_krpn_fops = {
...
    .proc_write   = proc_krpn_write,
...
};

static ssize_t proc_krpn_write(struct file *filp, const char __user *buf, size_t count, loff_t *f_pos)
{
    char str[32];
...
    if (copy_from_user(str, buf, count)) {
        return -EFAULT;
    }
...
}

static int krpn_init(void)
{
    struct proc_dir_entry *entry = NULL;
    entry = proc_create(PROC_KRPN_NAME, S_IRUGO | S_IWUGO, NULL, &seq_file_krpn_fops);
    return 0;
}

static void krpn_exit(void)
{
    remove_proc_entry(PROC_KRPN_NAME, NULL);
}

/procからの読み込み

次は /proc からの読み込み(というか、カーネル側から見たらユーザランドへの書き込み)です。 /proc からのデータは copy_from_user() で受け取れるので、その逆操作を行う copy_to_user() みたいな関数が用意されているのだろうか…？と思ったのですが、ユーザランドへの書き込みは思いのほか手間がかかるものでした…。

struct proc_ops.proc_read には seq_read() という関数を指定していますが、これはLinuxカーネルの fs/seq_file.c:seq_read() で提供されています。

static struct proc_ops seq_file_krpn_fops = {
...
    .proc_read    = seq_read,
    .proc_write   = proc_krpn_write,
...
};

どうやら seq_read() から呼び出されてくる関数群を用意し、それを struct seq_operations に設定しておくようです。

static struct seq_operations seq_file_krpn_seq_ops = {
    .start = seq_file_krpn_start,
    .stop  = seq_file_krpn_stop,
    .next  = seq_file_krpn_next,
    .show  = seq_file_krpn_show,
};

seq_operations.show = seq_file_krpn_show() で指定した関数の中で seq_printf() を呼ぶことでユーザランドにデータを返すことができます。 struct seq_file のデータはひとかたまりのバッファではなく、小さな固定長バッファをリストの形で管理しており、 struct seq_operations に指定した関数でリスト操作を行うような実装になります。

static int seq_file_krpn_show(struct seq_file *m, void *v)
{
    char stack_state_str[128];
...
    seq_printf(m, "%s\n", stack_state_str);
    return 0;
}

ただ、実装・動作まではできたのですが、この部分はmasami256さんのlinux: seq_fileの使い方めもの内容をコピペする感じで作ったので、もうちょっとしっかりと理解する必要がありそうです…。

逆ポーランド記法での数式処理を実装

/proc の読み書き処理が作成できたので、残るは逆ポーランド記法での数式処理部分です。
…といっても、これはユーザランド側で作成・デバッグしておいたコードをカーネルモジュールに組み込むだけなので、特に難しいものではありません。

気を付ける部分があるとすれば、カーネル内での実装になるため、 libc の関数が利用できない点でしょうか。例えば、以下のコードでは、数字の判定を isdigit() ではなく、一文字ずつチェックしていたり、 atoi() が提供されていないため、 simple_strtol() に置き換える等しています。

#define KRPN_STACK_SIZE 128
static int krpn_stack[KRPN_STACK_SIZE];
static int krpn_index = 0;
...

static ssize_t proc_krpn_write(struct file *filp, const char __user *buf, size_t count, loff_t *f_pos)
{
    int is_number = 1;
    int i;
    char str[32];
    char *c;
    char stack_state_str[128];
    char *s = stack_state_str;

...
    if (copy_from_user(str, buf, count)) {
        return -EFAULT;
    }
    str[count] = '\0';

    for (c = str; *c; c++) {
        if (*c == '\n') { *c = '\0'; }
    }
    for (c = str; *c; c++) {
        if (*c != '0'
              && *c != '1'
              && *c != '2'
              && *c != '3'
              && *c != '4'
              && *c != '5'
              && *c != '6'
              && *c != '7'
              && *c != '8'
              && *c != '9'
        ) {
            is_number = 0;
        }
    }

    c = str;
    if(*c == '+' || *c == '-' || *c == '*' || *c == '/') {
        int x, y;
        y = krpn_stack[--krpn_index];
        x = krpn_stack[--krpn_index];
        switch (*c) {
            case '+': krpn_stack[krpn_index++] = x + y; break;
            case '-': krpn_stack[krpn_index++] = x - y; break;
            case '*': krpn_stack[krpn_index++] = x * y; break;
            case '/': krpn_stack[krpn_index++] = x / y; break;
        }
    } else if (is_number == 1 && *c != '\0') {
        krpn_stack[krpn_index++] = (int)simple_strtol(str, NULL, 10);
    }


    s = stack_state_str;
    *s = '\0';
    for (i = 0; i < krpn_index; i++) {
        s += sprintf(s, "%d ", krpn_stack[i]);
    }
    printk("krpn stack: %s\n", stack_state_str);

    return count;
}

あとは普通にカーネルモジュールとしてビルドするだけです。

# make -C /usr/src/linux-5.15.2/ M=$PWD
make: ディレクトリ '/usr/src/linux-5.15.2'　に入ります
  CC [M]  /usr/src/linux-5.15.2/samples/krpn/krpn.o
  MODPOST /usr/src/linux-5.15.2/samples/krpn/Module.symvers
  LD [M]  /usr/src/linux-5.15.2/samples/krpn/krpn.ko
make: ディレクトリ '/usr/src/linux-5.15.2' から出ます
#
# file krpn.ko
krpn.ko: ELF 64-bit LSB relocatable, x86-64, version 1 (SYSV), BuildID[sha1]=4a47374550b3ae1778fc30789eeb8e550512db92, not stripped

逆ポーランド計算機カーネルモジュール(仮)を動かしてみる

作成した「逆ポーランド計算機カーネルモジュール(仮)」を動かしてみましょう。
カーネルモジュールをロードした後は、 echo [数字|四則演算子] > /proc/krpn でスタックに値をプッシュ・演算し、 cat /proc/krpn で現在のスタックの内容を表示(ユーザ側にデータを返してくる)します。

# cd /usr/src/samples/krpn/
# ls
Kbuild          krpn.c   krpn.mod    krpn.mod.o  modules.order
Module.symvers  krpn.ko  krpn.mod.c  krpn.o
# insmod ./krpn.ko
# lsmod
Module                  Size  Used by
krpn                   16384  0
#
# # 3 4 + 1 2 - * => -7 となる例。
# echo 3   > /proc/krpn ; cat /proc/krpn
3
# echo 4   > /proc/krpn ; cat /proc/krpn
3 4
# echo '+' > /proc/krpn ; cat /proc/krpn
7
# echo 1   > /proc/krpn ; cat /proc/krpn
7 1
# echo 2   > /proc/krpn ; cat /proc/krpn
7 1 2
# echo '-' > /proc/krpn ; cat /proc/krpn
7 -1
# echo '*' > /proc/krpn ; cat /proc/krpn
-7

dmesg -w を表示させながら実行すると、ユーザランド側とカーネル側での動作が垣間見えます。

まとめ

「逆ポーランド計算機カーネルモジュール(仮)」を作成してみました。ユーザランドとカーネル間でデータをやり取りする方法は sysctl や /proc など様々ありますが、カーネル側からユーザランドにデータを受け渡す場合はもう一段踏み込んだお作法が必要となっていました。
カーネルモジュールのサンプル試したりしていると、ユーザ側からデータを書き込めただけで満足する場合がありますが、読み込み・書き込みの両方の手順を調べておかないとイザという時にハマるということを痛感しました。

逆ポーランド計算機カーネルモジュール(仮)を作ってみる