BitVisorのlist.h, spinlock.h, token.hの説明です。

BitVisorのソースコードは https://bitbucket.org/bitvisor/bitvisor からダウンロードできます。

list.h

list.hはリスト操作の実装が入っているのですが、4つあります:

$ hg locate list.h
boot/login/minios_init/idmaninc/common/list.h
core/list.h
include/common/list.h
include/core/list.h

boot/login/minios_init/idmaninc/common/list.hは中身なし、core/list.hはinclude/core/list.hをincludeするだけです。

include/common/list.hとinclude/core/list.hにはそれぞれ異なるリストの実装があります。マクロでごちゃごちゃ宣言されていますので、引数に変数を変更するような演算子 (++, +=など) を含めないようにしてください。

include/common/list.h

ここにあるのは、nextポインターだけを持つもっともシンプルな単方向リストの実装です。nextポインターがvoid *型のため、型の誤りがコンパイル時に警告されないことに注意が必要です。

LIST_DEFINE(listname)

listnameという名前で、nextポインターを持つ構造体struct listの変数を宣言します。リストに入れたい構造体の中にこれを書きます。

LIST_DEFINE_HEAD(listname)

リストの先頭を表す変数を宣言します。変数名はlistnameの末尾に_headをつけたものになります。これもstruct listで、NULLで初期化されます。listnameはLIST_DEFINEに指定する名前と同じものです。

LIST_INSERT(listname, new)

リストの先頭を表す変数を書き換えて、先頭に要素newを挿入します。{ ... }形式の文に展開されますので、関数のように,演算子などを使用することはできません。

LIST_APPEND(listname, new)

リストの末尾に要素newを追加します。先頭から線形探索で末尾の要素を見つけて追加処理を行うため、実行時間はリストに入っている要素の数に比例します。{ ... }形式の文に展開されますので、関数のように,演算子などを使用することはできません。

LIST_FOREACH(listname, p)

リストの要素を先頭から順に変数pに入れてループするfor文です。

LIST_NEXT(listname, current)

リストの要素の次の要素を表します。

LIST_HEAD(listname)

リストの先頭の要素を表します。

include/core/list.h

ここには4種類のリストの実装が含まれます。

LIST1: シンプルな単方向リストで、LISTとは異なり削除ができ、末尾への追加でも線形探索が不要なもの
LIST2: LIST1とほぼ同じだが同一の構造体に複数のリストを持てるようにしたもの
LIST3: 配列の要素を対象とした双方向リスト (ただし単方向リストと同等のマクロしか定義されていない) で、ポインターの代わりに配列の添字を利用してメモリー使用量を削減したもの (先頭・末尾はポインターを用いる)
LIST4: 双方向リスト

LIST1およびLIST2は、次の要素を指すnextポインターと、前の要素のnextを指すpnextポインターを使用します。LIST3とLIST4は、次の要素を指すnextポインターと、前の要素を指すprevポインターを使用します。

ポインターはリストに入る構造体の型となっており、型の誤りがコンパイル時に指摘される場合があります。しかし、挿入・削除操作ではvoid *型を使用しているため、必ずしも指摘されるとは限りません。

LIST1_DEFINE(type)
LIST2_DEFINE(type, sx)
LIST3_DEFINE(type, sx, inttype)
LIST3_DEFINE_BIT (type, sx, inttype, nbits)
LIST4_DEFINE(type, sx)

nextポインター等を宣言します。リストに入れたい構造体の中にこれを書きます。typeには構造体の型を書きます。sxは、複数のリストに入れたい時にそれらを区別するための名前を指定するもので、見た目上、型の後ろに指定することからsuffixの略としてsxとなっています。

inttypeは配列の添字を表すのに使用する符号付き整数型を指定します。nbitsはビット構造体にしてメモリー使用量を削減するためのもので、ビット数を指定します。

LIST1_DEFINE_HEAD(type, name)
LIST2_DEFINE_HEAD(name, type, sx)
LIST3_DEFINE_HEAD(name, type, sx)
LIST4_DEFINE_HEAD(name, type, sx)

リストの先頭と、LIST1とLIST2では末尾の要素のnext、双方向の場合は末尾を指す変数を宣言します。LIST1とそれ以外ではnameの位置が異なっていますが、LIST2以降はLIST1の実装後しばらくしてから追加されたもので、その際typeとsxを一貫した順番で並べるためにそのようになっています。たぶん。

LIST1_DEFINE_HEAD_INIT(type, name)
LIST2_DEFINE_HEAD_INIT(name, type, sx)
LIST3_DEFINE_HEAD_INIT(name, type, sx)
LIST4_DEFINE_HEAD_INIT(name, type, sx)

初期化を伴う宣言です。自動変数やグローバル変数などで使用できますが、構造体の中に書く場合には使用できません。

LIST1_HEAD_INIT(name)
LIST2_HEAD_INIT(name, sx)
LIST3_HEAD_INIT(name, sx)
LIST4_HEAD_INIT(name, sx)

初期化を行います。構造体の中に書く場合にはこれを用いて初期化します。特に、LIST1とLIST2に関しては、pnextポインターがNULLにならないため、構造体を0クリアしたまま初期化をし忘れて使用すると、NULLポインターにアクセスしてしまいます。

LIST1_ADD(head, data)
LIST2_ADD(head, sx, data)
LIST3_ADD(head, sx, data)
LIST4_ADD(head, sx, data)

リストの末尾に要素newを追加します。

LIST1_INSERT(head, nextd, data)
LIST2_INSERT(head, sx, nextd, data)
LIST3_INSERT(head, sx, nextd, data)
LIST4_INSERT(head, sx, nextd, data)

リストの要素nextdの直前に要素dataを挿入します。nextdがNULLの場合は末尾に追加します。

LIST4_INSERTNEXT(head, sx, prevd, data)

リストの要素prevdの直後に要素dataを挿入します。prevdがNULLの場合は先頭に挿入します。

LIST1_PUSH(head, data)
LIST2_PUSH(head, sx, data)
LIST3_PUSH(head, sx, data)
LIST4_PUSH(head, sx, data)

リストの先頭に要素dataを挿入します。

LIST1_DEL(head, data)
LIST2_DEL(head, sx, data)
LIST3_DEL(head, sx, data)
LIST4_DEL(head, sx, data)

リストから要素dataを削除し、dataを返します。

LIST1_POP(head)
LIST2_POP(head, sx)
LIST3_POP(head, sx)
LIST4_POP(head, sx)

リストの先頭の要素を削除して返します。

LIST1_FOREACH(head, var)
LIST2_FOREACH(head, sx, var)
LIST3_FOREACH(head, sx, var)
LIST4_FOREACH(head, sx, var)

リストの要素を先頭から順に変数varに入れてループするfor文です。

LIST1_FOREACH_DELETABLE(head, var, varn)
LIST2_FOREACH_DELETABLE(head, sx, var, varn)
LIST3_FOREACH_DELETABLE(head, sx, var, varn)
LIST4_FOREACH_DELETABLE(head, sx, var, varn)

リストの要素を先頭から順に変数varに入れて、かつ、その要素が削除されても大丈夫なよう、varnにその次の要素を入れてループするfor文です。

LIST4_NEXT(var, sx)
LIST4_PREV(var, sx)
LIST4_HEAD(head, sx)
LIST4_TAIL(head, sx)

それぞれ次の要素、前の要素、先頭の要素、末尾の要素を返します。

spinlock.h

include/core/spinlock.hには以下の3種類のスピンロックの実装があります。

spinlock: シンプルなスピンロック
rw_spinlock: 共有ロック
ticketlock: チケットロック

spinlock

void spinlock_init (spinlock_t *l);
void spinlock_lock (spinlock_t *l);
void spinlock_unlock (spinlock_t *l);
SPINLOCK_INITIALIZER

spinlock_initで初期化、spinlock_lockとspinlock_unlockでロック・アンロックします。spinlock_initの呼び出しの代わりにSPINLOCK_INITIALIZERを初期値として設定することもできます。

spinlockは様々な場所で使用されています。

rw_spinlock

void rw_spinlock_init (rw_spinlock_t *l);
void rw_spinlock_lock_sh (rw_spinlock_t *l);
void rw_spinlock_unlock_sh (rw_spinlock_t *l);
void rw_spinlock_lock_ex (rw_spinlock_t *l);
rw_spinlock_t rw_spinlock_trylock_ex (rw_spinlock_t *l);
void rw_spinlock_unlock_ex (rw_spinlock_t *l);

rw_spinlock_initで初期化します。共有ロック (他に排他ロックを保持しているものがいなければロック可能) にはrw_spinlock_lock_shとrw_spinlock_unlock_shを使用します。排他ロックにはrw_spinlock_lock_exとrw_spinlock_unlock_exを使用します。

rw_spinlock_trylock_exは排他ロックが取れるまでループしない関数で、0が返されればロックが取れています。

読み取りは頻繁に行われるが書き込みはめったにない、といった用途に向いています。ただし、共有ロックが頻繁すぎると排他ロックがなかなか取れないかも知れません。

rw_spinlockの使用例として代表的なものは、core/mmio.cがあります。mmioのハンドラーの登録・登録解除 (書き込み) はめったに行われず、ハンドラーの呼び出し (読み取り) は頻繁に行われることから、ハンドラーの呼び出しがなるべくスムーズに動作するよう、rw_spinlockを使用しています。

ticketlock

void ticketlock_lock (ticketlock_t *l);
void ticketlock_unlock (ticketlock_t *l);
void ticketlock_init (ticketlock_t *l);

ticketlock_initで初期化、ticketlock_lockとticketlock_unlockでロック・アンロックします。

金融機関の窓口にあるような番号札システムで、他にロック待ちのスレッドがある時に、それに割り込むことなく、順番にロックが取れるのが特徴です。spinlockでは、アンロックしてすぐにロックする処理を繰り返すと、他のスレッドが10秒以上にわたってロック待ち状態になることがあります。そのような場合にきちんと処理が回るようにするために有用です。

ticketlockはcore/thread.cが使用しています。schedule関数を頻繁に呼び出して変数の値の変化を待つ処理を実行したところ、その処理がロックを連続して取ってしまい、他のCPUのschedule関数が動かなくなってしまったことから、その対策として使用しています。

token.h

include/token.hにはvmm.driver.pciなどの構文解釈やワイルドカードの処理を補助する実装があります。以下の構造体を使います。

include/token.h

struct token {
        char *start, *end, *next;
};

文字列からひとつのトークン (記号がなければ単語、""などの記号があればそれでくくられたひとつの単位を表します) を取り出すにはget_token関数を使用します。

char get_token (char *p, struct token *t);

この関数は、pの先頭から、空白をスキップして、先頭の文字のアドレスをstartに、トークンの最後の次の文字のアドレスをendに入れます。トークンの後ろの空白をスキップした次の文字を返り値として、それが終端文字の場合はそのアドレス、それ以外の場合はそのさらに次の文字のアドレスをnextに入れます。

startとendが等しいか、startがNULLの場合は何らかの構文エラーを表します。

以下に例を示します。

   foo=bar|hoge,bar=foo\0
   p
=  s  en 
       p
,      s       en
                p
=               s  en
                    p
\0                  s  e

1行目が文字列とし、2行目以降はget_tokenを呼び出す時のポインターpの位置と、start, end, nextの指す位置をそれぞれp, s, e, nで表し、行頭に返り値の文字を示しています。最後の\0については、endとnextは同じとなります。

処理としては、startおよびendが異常を示していないかのチェック、返り値が期待される値であるかどうかのチェックと、次に示すmatch_token関数を用いた値比較が中心となります。

int match_token (char *str, struct token *t);

get_token関数で取得したstartおよびendが示す文字列とstrを比較し、一致していたら1、一致していなければ0を返します。

単なる文字列比較ではなく、トークンに含まれるワイルドカードの*記号と?記号の他、\記号、"記号や|記号の解釈も行います。例えば、startからendの直前までの文字列がbar|hogeのときは、strが"bar"または"hoge"であれば1を返します。

token.hの使用例として代表的なものは、drivers/pci_match.cがあります。