ID管理 lib/idr.c

Linux

1日々更新が続けられる Linux kernel。カーネルですから、他のパッケージに依存するわけにはいきません。しかし、カーネルの中にもいろいろと重複する部分があるわけで。そういうものをまとめて linux/lib 下にカーネル内で使うライブラリがまとめられています。これを知っているときっとカーネル開発も楽になって、 Kernel Hack も身近になるはず! ということで、 lib/* を読んでは記事でも書こうかと思います。

カーネル開発をやってるわけではないので内容の正誤は無保証です。

とりあえず、自分も使いたいところからということで lib/idr.c から。

idr は固有のIDとポインタをひもづける、ID管理のライブラリです。ようするに、数字限定の辞書・連想配列と思って構わないでしょう。 配列のように事前に静的にメモリ領域を確保せず必要に応じてメモリを確保していきます。

サンプル

とりあえず、サンプルモジュールを書いてみました。

http://github.com/naota/linux-kernel-test-module/tree/test-idr

コンパイルして実行してみます。

# insmod test.ko
# FILE=/proc/test_mod_file
# cat ${FILE}
ID      Data

最初はなにも入ってません。

# echo new foo > ${FILE}
# cat ${FILE}
ID      Data
00000   foo
# echo new bar > ${FILE}
# cat ${FILE}
ID      Data
00000   foo
00001   bar
# echo new baz > ${FILE}
# cat ${FILE}
ID      Data
00000   foo
00001   bar
00002   baz

"foo", "bar", "baz" を登録してみました。

# echo on 10 hoge > ${FILE}
# cat ${FILE}
ID      Data
00000   foo
00001   bar
00002   baz
00010   hoge

10番に "hoge" を登録。

# echo rm 10 > ${FILE}
# cat ${FILE}
ID      Data
00000   foo
00001   bar
00002   baz

10番を削除。

# echo rep 0 meech > ${FILE}
# cat ${FILE}
ID      Data
00000   meech
00001   bar
00002   baz

0 番を "meech" に置き換え。

こんな感じの動きをするライブラリです。さて、中身を見てみましょう。

準備/初期化

#include <linux/spinlock.h>
#include <linux/idr.h>

static DEFINE_SPINLOCK(test_lock);
static DEFINE_IDR(test_idr);

IDRのデータ構造 test_idr を定義して初期化します。追加/置換/削除時には lock したほうが良いようなので、 spinlock に使う test_lock も定義しておきます。

ちなみに

struct idr test_idr;

static int test_init(void)
{
	idr_init(&test_idr);
	return 0;
}

のようにしても同じようなことになりますが面倒ですね。 idr_init() は主に動的に idr を作成した場合に使われます。

データ入力

static int test_new_entry(char *str)
{
	int id, ret;

	do {
		if (!idr_pre_get(&test_idr, GFP_KERNEL))
			return -ENOMEM;

		spin_lock(&test_lock);
		ret = idr_get_new(&test_idr, str, &id);
		spin_unlock(&test_lock);
	} while (ret == -EAGAIN);

	if (ret)
		return -ENOMEM;

	return id;
}

"str" で渡された文字列ポインタを "test_idr" に登録します。登録されたもののIDが "id" に返ってきます。 idr から使われている関数は、 "idr_pre_get()" と "idr_get_new()" です。

idr_pre_get
0 メモリ確保失敗
1 メモリ確保成功

"idr_pre_get()" は "idr_get_new()" で使われるであろうメモリを前もって確保します。 "idr_get_new()" は lock の中で行なうため、メモリ確保というブロックしうる作業をその中で行なうべきではないからです。この関数はほんとうにどうしてもメモリがない、という時には 0 を返します。うまくメモリ確保できれば 1 を返します。

idr_get_new
-EAGAIN メモリが足りない (= idr_pre_get() からやりなおせ)
-ENOSPC IDR に領域がない

"idr_get_new()" が実際に IDR にポインタを登録します。ここでは文字列のポインタを登録していますが、任意のポインタを登録することができます。登録されるのはアドレスなので kmalloc でその領域を確保しておくことを忘れずに。

データ取得

	spin_lock(&test_idr);
	ptr = idr_find(&test_idr, id);
	spin_unlock(&test_idr);
	if (ptr == NULL)
		return -EINVAL;
idr_find
NULL データが存在しない (または idr_get_new* で NULL を登録した)
それ以外 登録されているデータ

"idr_find()" は "id" を指定して、そのIDに登録されているデータを取得します。

データ置換

static int test_replace_entry(int id, char *str)
{
	void *old;

	spin_lock(&test_lock);
	old = idr_replace(&test_idr, (void *)str, id);
	spin_unlock(&test_lock);

	if (IS_ERR(old))
		return -EINVAL;
	kfree(old);
	return 0;
}
idr_replace
-ENOENT 指定された ID が見つからない
-EINVAL 指定された ID は IDR のサポートするID範囲外
その他 置換されたポインタ

"idr_replace()" は指定されたIDのエントリを新しいエントリで置き換えます。古いポインタ、またはエラーが返ってきます。IS_ERR で返ってきたのがエラーかどうか判定しましょう。(メモリ空間の最上位1ページは使われない規約を使っています) ちゃんと kfree なり片付けなりしましょうね…。

データ削除

static int test_remove_entry(int id)
{
	char *ptr;

	spin_lock(&test_lock);
	ptr = idr_find(&test_idr, id);
	if (ptr == NULL) {
		spin_unlock(&test_lock);
		return -EINVAL;
	}
	idr_remove(&test_idr, id);
	spin_unlock(&test_lock);

	kfree(ptr);

	return 0;
}
idr_remove

"idr_remove()" は指定されたIDのエントリを削除します。削除されたエントリのポインタが返ってきたらいいのに…。

終了

終了する時にはお片付け。全てのメモリを解放しましょう。

static int test_free_idr_entry(int id, void *p, void *data)
{
	kfree(p);
	return 0;
}

static void test_exit(void)
{
	idr_for_each(&test_idr, test_free_idr_entry, NULL);
	idr_remove_all(&test_idr);
	idr_destroy(&test_idr);
}
idr_for_each

"idr_for_each()" はコールバック関数を取り、全てのエントリに対してその関数を呼び出します。ここでは、 "test_free_idr_entry()" がコールバックになっておりエントリに設定されていたアドレスを解放します。

コールバックが 0 以外を返した場合、そこで "idr_for_each()" は終了します。コールバックが返したものがそのまま "idr_for_each()" の返り値となります。

idr_remove_all

"idr_remove_all()" は全てのエントリを削除します。

idr_destroy

"idr_destroy()" はIDR内部に予約されているメモリ領域を解放します。