clistのカーネル版を作りました

前回このブログに書いた循環リストのライブラリのカーネル版の実装を作りました。

本体はここ（github）にあるので、ヘッダファイルをさらしておきます。

clist.h

#include <linux/spinlock_types.h>	/* spinlock_t */

#define CLIST_STATE_COLD	0
#define CLIST_STATE_HOT	1
#define CLIST_STATE_END	2


#define CLIST_IS_HOT(ctl)	(ctl->state == CLIST_STATE_HOT ? 1 : 0)
#define CLIST_IS_COLD(ctl)	(ctl->state == CLIST_STATE_COLD ? 1 : 0)
#define CLIST_IS_END(ctl)	(ctl->state == CLIST_STATE_END ? 1 : 0)


#define clist_wlen(ctl)	ctl->pull_wait_length
#define objs_to_byte(ctl, n)	(ctl->object_size * n)
#define byte_to_objs(ctl, byte)	(byte / ctl->object_size)


/* 循環リストのノード */
struct clist_node{
	void *data;		/* ここにメモリを確保する */
	struct clist_node *next_node;

	void *curr_ptr;	/* dataに次に格納するべきアドレス */
};

/* 循環リスト管理用構造体 */
struct clist_controller{
	int state;		/* CLIST_STATE_COLD:循環リストに対しての入出力禁止 CLIST_STATE_HOT:循環リストに対しての入出力可能*/

	int pull_wait_length;	/* pull待ちのnodeの数 */
	int nr_node, node_len;
	int nr_composed, object_size;

	spinlock_t lock;	/* クリティカルセクションで使用 */

	struct clist_node *nodes;

	/*
		w_curr:書き込み中のclist_nodeのアドレス
		r_curr:読み込み中のclist_nodeのアドレス
	*/
	struct clist_node *w_curr, *r_curr;
};

/* プロトタイプ宣言 */
int clist_pullable_objects(const struct clist_controller *clist_ctl, int *n_first, int *n_burst);
int clist_pushable_objects(const struct clist_controller *clist_ctl, int *n_first, int *n_burst);

/* データ構造のalloc/free */
struct clist_controller *clist_alloc(int nr_node, int nr_composed, int object_size);
void clist_free(struct clist_controller *clist_ctl);

/* 循環リストにデータを書き込む/読み込む関数 */

/* 単一オブジェクト版 */
int clist_push_one(const void *data, struct clist_controller *clist_ctl);
int clist_pull_one(void *data, struct clist_controller *clist_ctl);
/* 複数オブジェクト版 */
int clist_push_order(const void *data, int n, struct clist_controller *clist_ctl);
int clist_pull_order(void *data, int n, struct clist_controller *clist_ctl);

/* 最後にデータを読みきる関数 */
int clist_set_end(struct clist_controller *clist_ctl, int *n_first, int *n_burst);
int clist_pull_end(void *data, struct clist_controller *clist_ctl);

カーネル版実装にあたって、1オブジェクト入出力用のclist_push_one()/clist_pull_one()を追加しました。それに伴って従来のclist_push()/clist_pull()は名前を変更して、clist_push_order()/clist_pull_order()としました。

少数もしくは単発の入出力ならclist_push_one()/clist_pull_one()の方がオーバーヘッドが少なくて高速です。

インストール方法は以前このブログに書いた方法を参考にしました。カーネルコンフィグの名前はCONFIG_GENERIC_CLISTにしました。

#cp clist.c /usr/src/linux-source-3.0.0/lib
#cp clist.h /usr/src/linux-source-3.0.0/include/linux

ただ、ファイルの配置先がkernel-tree/drivers/charではなくkernel-tree/libにしているのでMakefileの書き方が若干異なってます。

/usr/src/linux-source-3.0.0/lib/Makefile

#
# Makefile for some libs needed in the kernel.
#

ifdef CONFIG_FUNCTION_TRACER
ORIG_CFLAGS := $(KBUILD_CFLAGS)
KBUILD_CFLAGS = $(subst -pg,,$(ORIG_CFLAGS))
endif

lib-y := ctype.o string.o vsprintf.o cmdline.o \
	 rbtree.o radix-tree.o dump_stack.o timerqueue.o\
	 idr.o int_sqrt.o extable.o prio_tree.o \
	 sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \
	 proportions.o prio_heap.o ratelimit.o show_mem.o \
	 is_single_threaded.o plist.o decompress.o find_next_bit.o

lib-$(CONFIG_GENERIC_CLIST) += clist.o		←追加

lib-$(CONFIG_MMU) += ioremap.o
lib-$(CONFIG_SMP) += cpumask.o

今回ハマった箇所としては、Kconfigファイルのtristateは書かないといけないということ。これがないとビルドシステムがファイルを認識してくれませんでした。helpは無くても大丈夫です。helpだけでもダメでした。tristateの項は絶対に必要なようです。加えてtristateの行は1行で書かないといけない、ということも分かりました。

＃そもそもtristateの意味って何でしょう？Webで調べると「3状態」とか出てくるんですが、ここではどういう意味で使っているか分かりません。ご存知の方教えてください。

/usr/src/linux-source-3.0.0/lib/Kconfig

#
# Library configuration
#

config BINARY_PRINTF
	def_bool n

menu "Library routines"

config GENERIC_CLIST
	tristate "generic circularly-linked list library"	←必要
        help
		@shimada__k

config RAID6_PQ
		tristate

カーネル側の実装ということで、一応スピンロックでmemcpyとリストをつなぎ変える部分を保護していますが、競合＆割り込みに対しての対策としてはアマアマです。ちょっとした実験で使うレベルで落ちなければいいかなあ、という程度です。

このライブラリを実際に使ってみる例は後日書こうと思います。