「30日でできる!OS自作入門」をRustで。13日目

Posted on June 29, 2019 , Tags: OS自作入門, OS, Rust

「30日でできる!OS自作入門 」のC言語の部分をできるだけRustですすめてみる。今回は13日目の内容。

write_with_bg! マクロの導入

本では矩形を描画し、その上に文字を表示する部分をまとめて関数にしていた。
たしかに、Rustのコードでも、矩形と文字描画の部分で、サイズ指定などが重複しており煩わしかったので、マクロでまとめてみる。

引数が長大になってしまったので、あまり見た目はよくないが、少なくともrefreshと矩形領域のサイズのミスは防ぐことができるようになったのでよしとする。

差分はGitHubのdiffを見てもらうのがわかりやすいかと思う。

タイマ用のFIFOをまとめる

現状、タイマごとに別のFIFOを使っていたが、まとめるようにする。

ベンチマークの導入

性能を計測するために、ベンチマークを導入する。
ここでは、エントリポイントとなる関数のloopにカウントアップする変数を仕込み、起動後3秒-10秒で何回ループが発生したかを計測することで、ベンチマークとする。

実行結果

5回実行してみて、結果は以下の通りだった。

結構バラつきがあるが、QEMU上での確認なのでホストマシンの状況にも影響をうけそうだ。

FIFOキューを統一

性能向上のため、割り込みデータを保持するのに使っているFIFOキューをキーボード用、マウス用、タイマ用でわけず、すべて同じFIFOキューを使うようにする。キューにつめこむデータの値の範囲で区別できるようにする。 以下、細かい差分が多いので、おおまかなところの差分だけ載せる。

実行結果

FIFOキューを統一した結果の性能向上を測るため、再度ベンチマークで計測してみた

1.5倍ほど向上してそうだ。

タイマの順番を線形リスト形式で保持するようにする

現状、タイマの順番は配列形式でもっているが、これは先頭がタイムアウトになると後ろを詰めなおす処理がいるので非効率だ。(配列の長さをnとするとO(n)かかる。)
線形リストのように、次の要素のインデックスを要素自身にもたせることで効率化を図る。

各関数も変更する。

//timer.rs
pub extern "C" fn inthandler20() {
    out8(PIC0_OCW2, 0x60); // IRQ-00受付完了をPICに通知
    let mut tm = TIMER_MANAGER.lock();
    tm.count += 1;
    if tm.next_tick > tm.count {
        return;
    }
    let mut timer_index = tm.t0;
    let mut timeout_count = 0;
    for i in 0..tm.counting {
        timeout_count = i;
        if tm.timers_data[timer_index].timeout > tm.count {
            break;
        }
        {
            let mut t_mut = &mut tm.timers_data[timer_index];
            t_mut.flag = TimerFlag::USED;
        }
        {
            let timer = &tm.timers_data[timer_index];
            FIFO_BUF.lock().put(timer.data as u32).unwrap();
            timer_index = timer.next;
        }
    }
    tm.counting -= timeout_count;
    tm.t0 = timer_index;

    if tm.counting > 0 {
        tm.next_tick = tm.timers_data[tm.t0].timeout;
    } else {
        tm.next_tick = 0xffffffff;
    }
}

impl TimerManager {
    // 省略
        pub fn set_time(&mut self, timer_index: usize, timeout: u32) {
        {
            let mut timer = &mut self.timers_data[timer_index];
            timer.timeout = timeout + self.count;
            timer.flag = TimerFlag::COUNTING;
        }
        let eflags = load_eflags();
        cli();
        self.counting += 1;
        if self.counting == 1 {
            let mut timer = &mut self.timers_data[timer_index];
            self.t0 = timer_index;
            timer.next = 0;
            self.next_tick = timer.timeout;
            store_eflags(eflags);
            return;
        }
        let mut t_index = self.t0;
        if &self.timers_data[timer_index].timeout <= &self.timers_data[t_index].timeout {
            // 先頭に入れる
            let mut timer = &mut self.timers_data[timer_index];
            self.t0 = timer_index;
            timer.next = t_index;
            self.next_tick = timer.timeout;
            store_eflags(eflags);
            return;
        }
        let mut old_t_index = t_index;
        // 間に入るところを探す
        loop {
            old_t_index = t_index;
            t_index = self.timers_data[t_index].next;
            if t_index == 0 {
                break;
            }
            if self.timers_data[timer_index].timeout <= self.timers_data[t_index].timeout {
                {
                    let mut s = &mut self.timers_data[old_t_index];
                    s.next = timer_index;
                }
                {
                    let mut timer = &mut self.timers_data[timer_index];
                    timer.next = t_index;
                }
                store_eflags(eflags);
                return;
            }
        }
        // 入るところが見つからなかったので、最後に入れる
        {
            let mut s = &mut self.timers_data[old_t_index];
            s.next = timer_index;
        }
        {
            let mut timer = &mut self.timers_data[timer_index];
            timer.next = 0;
        }

        store_eflags(eflags);
    }
    // 省略

所有権の問題回避でカッコが多いが、やっていることはそこまで難しくない。

実行結果

本の通り、これだけではあまり速くならなかった。

長さではなく番兵で判定するようにする

上記に加えて、有効なタイマの長さベースで管理するのではなく、最初からタイマの順番用配列に番兵となるようなデータを入れておくことで判定ロジックを簡単にする

// timer.rs

impl TimerManager {
    pub fn new() -> TimerManager {
        let mut tm = TimerManager {
            count: 0,
            next_tick: 0xffffffff,
            t0: Some(MAX_TIMER - 1),
            timers_data: [Timer::new(); MAX_TIMER],
        };
        // 番兵
        tm.timers_data[MAX_TIMER - 1] = Timer {
            timeout: 0xffffffff,
            flag: TimerFlag::COUNTING,
            data: 0,
            next: None,
        };
        tm
    }

    pub fn set_time(&mut self, timer_index: usize, timeout: u32) {
        {
            let mut timer = &mut self.timers_data[timer_index];
            timer.timeout = timeout + self.count;
            timer.flag = TimerFlag::COUNTING;
        }
        if self.t0.is_none() {
            return;
        }
        let eflags = load_eflags();
        cli();
        let mut t_index = self.t0.unwrap();
        if &self.timers_data[timer_index].timeout <= &self.timers_data[t_index].timeout {
            // 先頭に入れる
            let mut timer = &mut self.timers_data[timer_index];
            self.t0 = Some(timer_index);
            timer.next = Some(t_index);
            self.next_tick = timer.timeout;
            store_eflags(eflags);
            return;
        }
        let mut old_t_index: usize;
        // 挿入できるインデックスをさがす
        loop {
            old_t_index = t_index;
            if self.timers_data[t_index].next.is_none() {
                store_eflags(eflags);
                break;
            }
            t_index = self.timers_data[t_index].next.unwrap();
            if self.timers_data[timer_index].timeout <= self.timers_data[t_index].timeout {
                {
                    let mut s = &mut self.timers_data[old_t_index];
                    s.next = Some(timer_index);
                }
                {
                    let mut timer = &mut self.timers_data[timer_index];
                    timer.next = Some(t_index);
                }
                store_eflags(eflags);
                return;
            }
        }
    }
    // 省略
}

pub extern "C" fn inthandler20() {
    out8(PIC0_OCW2, 0x60); // IRQ-00受付完了をPICに通知
    let mut tm = TIMER_MANAGER.lock();
    tm.count += 1;
    if tm.next_tick > tm.count {
        return;
    }
    let mut timer_index = tm.t0;
    loop {
        if timer_index.is_none() {
            return;
        }
        let t_index = timer_index.unwrap();
        if tm.timers_data[t_index].timeout > tm.count {
            break;
        }
        let mut timer = &mut tm.timers_data[t_index];
        timer.flag = TimerFlag::USED;
        FIFO_BUF.lock().put(timer.data as u32).unwrap();
        timer_index = timer.next;
    }
    tm.t0 = timer_index;
    if let Some(t_index) = timer_index {
        tm.next_tick = tm.timers_data[t_index].timeout;
    }
}

実行結果

少し速くなったようだ。

13日目は以上となる。ここまでの内容のコードはyoshitsugu/hariboteos_in_rustのday13としてタグを打ってある。