Zig版ASP3カーネルのPrioBitmap
こんにちは、めのんです！
前回はタスクに関する本当にこまごました内容をざっと見ていきました。 今回はその中で登場したレディキューサーチのためのビットマップに使用していたPrioBitmap関数を見ていくことにします。
まずは前回のおさらいで、レディキューサーチのためのビットマップの定義から見ていきましょう。 定義はkernel/task.zigにあります。
/// /// レディキューサーチのためのビットマップ /// /// レディキューのサーチを効率よく行うために，優先度ごとのタスクキュー /// にタスクが入っているかどうかを示すビットマップを用意している．ビッ /// トマップを使うことで，メモリアクセスの回数を減らすことができるが， /// ビット操作命令が充実していないプロセッサで，優先度の段階数が少な /// い場合には，ビットマップ操作のオーバーヘッドのために，逆に効率が /// 落ちる可能性もある． /// var ready_primap: prio_bitmap.PrioBitmap(TNUM_TPRI) = undefined;
このPrioBitmap関数の定義はlibrary/prio_bitmap.zigにあります。
/// 優先度ビットマップ
pub fn PrioBitmap(comptime level: comptime_int) type {
if (level <= 1) {
@compileError("priority level must be larger than 1.");
}
else if (level <= 32) {
// 32レベル以下の場合は1段のビットマップで実装
return OneLevelBitmap(level);
}
else if (level <= 1024) {
// 1024レベル以下の場合は2段のビットマップで実装
return TwoLevelBitmap(level);
}
else {
@compileError("unsuppored priority levels.");
}
}
PrioBitmap関数の内容を見ると、32レベル以下の場合と1024レベル以下の場合で別の関数を呼び出していますね。 C版では16ビット符合無し整数を使ったサーチしかやっていませんでしたので、Zig版はこのあたりかなりパワーアップしたんだと思います。
32レベル以下の場合、私の想像では32ビット整数をMSBからかLSBからかわかりませんが探索して最初に1が立っているビットを調べるんだと思います。 Zigの場合は最大65535ビット整数まで扱えるのですが、32レベルを超える場合はC版と同じように2段階に分けたんだと思います。
それでは、32レベル以下に対応したOneLevelBitmap関数から見ていきますね。
/// 1段のビットマップでの実装
fn OneLevelBitmap(comptime level: comptime_int) type {
const Prio = PrioType(level);
const Bitmap = BitmapType(level);
return struct {
bitmap: Bitmap,
/// 優先度ビットマップの初期化
pub fn initialize(p_self: *@This()) void {
p_self.bitmap = 0;
}
/// 優先度ビットマップのセット
pub fn set(p_self: *@This(), prio: Prio) void {
assert(prio < level);
p_self.bitmap |= (@as(Bitmap, 1) << prio);
}
/// 優先度ビットマップのクリア
pub fn clear(p_self: *@This(), prio: Prio) void {
assert(prio < level);
p_self.bitmap &= ~(@as(Bitmap, 1) << prio);
}
/// 優先度ビットマップがセットされているかのチェック
pub fn isSet(self: @This(), prio: Prio) bool {
assert(prio < level);
return (self.bitmap & (@as(Bitmap, 1) << prio)) != 0;
}
/// 優先度ビットマップが空かのチェック
pub fn isEmpty(self: @This()) bool {
return self.bitmap == 0;
}
/// 優先度ビットマップのサーチ
pub fn search(self: @This()) Prio {
assert(self.bitmap != 0);
return @intCast(Prio, @ctz(Bitmap, self.bitmap));
}
/// 優先度ビットマップの整合性検査
pub fn bitCheck(self: @This()) bool {
return (self.bitmap & ~@as(Bitmap, (1 << level) - 1)) == 0;
}
};
}
C版ではそれぞれ個別の関数が用意されていましたが、Zig版では関連する関数をまとめた構造体を組み立ててそれを返しています。
それぞれを関数を見ていくとビルトイン関数がたくさん使われていますね。 せっかくなのでひとつひとつ見ていくことにします。
まずは@This関数です。 この関数を呼び出したときのもっとも内側の構造体、共用体、列挙型の型を返します。 他の言語ではthisというとオブジェクトのポインタや参照になるんですけど、Zigでは型を返すんですね。
次は@as関数です。 これは型変換を行うビルトイン関数のようです。 @as(Bitmap, 1) と書けば、1をBitmap型に型変換するという意味だと理解しました。
そして今回の目玉となる@ctz関数です。 これはLSBから連続した0のビット数を数えるための関数です。 いいかえると最初に1が現れるビット位置を返すということになります。 ちなみにMSBから調べるのは@clz関数になります。
@ctz関数や@clz関数のようなものはアセンブリ言語の命令として備わっているCPUはそれなりにあるんですけどCにはないので、Cの場合はインラインアセンブラを使わないといけなかったんですよ。 Zigにはビルトイン関数として備わっているの便利です。 でも、CPUのアーキテクチャによってはソフトウェアでエミュレーションすることになるので決して早いとはいえないのでしょうね。
ビルトイン関数以外は取り立てて見るべきポイントはないのでこれぐらいにしておきます。
TwoLevelBitmap関数も念のため貼っておきますが、複雑にはなりましたがZigという言語を学ぶ上で見るべきポイントはとくにないようです。
/// 2段のビットマップでの実装
fn TwoLevelBitmap(comptime level: comptime_int) type {
const Prio = PrioType(level);
const upper_level = (level + 31) / 32;
const UpperPrio = PrioType(upper_level);
const LowerPrio = PrioType(32);
return struct {
upper_bitmap: OneLevelBitmap(upper_level),
lower_bitmap: [upper_level]OneLevelBitmap(32),
/// 優先度ビットマップの初期化
pub fn initialize(p_self: *@This()) void {
p_self.upper_bitmap.initialize();
for (p_self.lower_bitmap) |*bitmap| {
bitmap.bitmap = 0;
}
}
/// 優先度ビットマップのセット
pub fn set(p_self: *@This(), prio: Prio) void {
assert(prio < level);
p_self.lower_bitmap[prio / 32].set(@intCast(LowerPrio, prio % 32));
p_self.upper_bitmap.set(@intCast(UpperPrio, prio / 32));
}
/// 優先度ビットマップのクリア
pub fn clear(p_self: *@This(), prio: Prio) void {
assert(prio < level);
p_self.lower_bitmap[prio / 32].clear(@intCast(LowerPrio,
prio % 32));
if (p_self.lower_bitmap[prio / 32].bitmap == 0) {
p_self.upper_bitmap.clear(@intCast(UpperPrio, prio / 32));
}
}
/// 優先度ビットマップが空かのチェック
pub fn isEmpty(self: @This()) bool {
return self.upper_bitmap.isEmpty();
}
/// 優先度ビットマップのサーチ
pub fn search(self: @This()) Prio {
const upper_prio: Prio = self.upper_bitmap.search();
return upper_prio * 32 + self.lower_bitmap[upper_prio].search();
}
/// 優先度ビットマップの整合性検査
pub fn bitCheck(self: @This()) bool {
if (!self.upper_bitmap.bitCheck()) {
return false;
}
if (self.lower_bitmap[(level - 1) / 32].bitmap
& ~@as(BitmapType(32),
(1 << ((level - 1) % 32 + 1)) - 1) != 0) {
return false;
}
// upper_bitmapとlower_bitmapの整合性の検査
for (self.lower_bitmap) |*bitmap, upper_prio| {
if (bitmap.bitmap == 0) {
if (self.upper_bitmap.isSet(@intCast(UpperPrio,
upper_prio))) {
return false;
}
}
else {
if (!self.upper_bitmap.isSet(@intCast(UpperPrio,
upper_prio))) {
return false;
}
}
}
return true;
}
};
}
それでは今回はこれぐらいにしておきます。 次回は何にするかまだ決めていませんので、今夜までに考えておきます。
それでは！！
