ゼロからのOS自作入門 メモ #7

# 前置き
本記事は「ゼロからのOS自作入門」のメモになります。
仕事上OSの知識があってもいいなと思って、取り組むことにしました。
各章に対し、1記事をOutputする予定です。
前記事：https://qiita.com/fuji3195/items/02282cb2714f57c5347d

参考として，以下のように章を学んでいます．
2~3周くらいは読まないと，中身の理解はできないです．
- まず章を全部読む
- 読み返しつつ手を動かして動作確認
- 書籍に載っている部分はプログラムをコメントアウトして書籍のコードを写経する

あと，前回でPCを落とした後に復帰するとき困ったので，うまくいかなかったら試すべきコマンドをいくつか書いておきます．
```
// CPPFLAGSに何か書いてあるか確認する．
$ echo $CPPFLAGS
// CPPFLAGSに何もなければ，以下を実行
$ source /$HOME/osbook/devenv/buildenv.sh

// 該当のgitを使いたいとき
// XXは章を，Zにはabc~を入れる．
$ git checkout osbook_dayXXZ

//　いじったのを戻したいとき
$ git checkout .

// 間違えてedksetup.shを実行してしまった場合
$ vim Conf/target.txt
// 中でPkgを以下のようにする
MikanLoaderPkg/MikanLoaderPkg.dsc

```

# 学ぶこと
- 割り込み
    - 割り込みハンドラと割り込みベクタ (7.1~3)
    - 割り込み記述子 (7.3, 7.4)
    - MSI割込み
- 割り込みハンドラの高速化
    - FIFO
    - Queueの実装
    - Queueを使った高速化

# 割り込み
X86-64での割込みの流れは以下の通り
1. 事前準備
    1. イベント発生時に実行する割り込みハンドラを準備する
    1. 割り込みハンドラをIDT(割り込み記述子テーブル)に登録する
1. イベント発生時
    1. HWがイベントをCPUに通知
    1. CPUは現在の処理を中断し，イベントの種類に応じて登録された割り込みハンドラに処理を移す
        1. 中断したものは別の領域に移しておく
    1. 割り込みハンドラの処理が終わると，中断していた処理を再開する

## 割り込みハンドラ
以下は割り込みハンドラの実装．
最後の`NotifyEndOfInterrupt()`以外は，もともとmain関数で実装されていたものを移植しただけ．
新しく追加した`NotifyEndOfInterrupt()`は割り込みをOffにする役割を持つ．
```C++:割り込みハンドラ
usb::xhci::Controller* xhc;

__attribute__((interrupt))    // 直後に定義される関数が割り込みハンドラであることを示す
void IntHandlerXHCI(InterruptFrame* frame) {
  while (xhc->PrimaryEventRing()->HasFront()) {
    if (auto err = ProcessEvent(*xhc)) {
      Log(kError, "Error while ProcessEvent: %s at %s:%d\n", 
          err.Name(), err.File(), err.Line());
    }
  }
  NotifyEndOfInterrupt();
}
```
```C++:interrupt.cpp
void NotifyEndOfInterrupt() {
    volatile auto end_of_interrupt = reinterpret_cast<uint32_t*>(0xfee000b0);
    *end_of_interrupt = 0;
}
```
Interruptの中の`volatile`修飾子は，最適化禁止を意味する．
これは，レジスタの書き込み作業として必ず行いたい動作を用いるときに使う．

## 割り込みベクタ
IDT (割り込み記述子テーブル : Interrupt Descriptor Table)を実装する．
x86-64の場合，割り込みテーブルの要素数は256個．
すでに使い道が決まっているものもあれば，自由に指定できるものもある．
USBの場合は自由に指定してよい．

``` C++:Interrupt.cpp
std::array<InterruptDescriptor, 256> idt;
```
``` C++:Interrupt.hpp
// 313029 8 7 6 5 4 3 2 1 0 19 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
// +--------------------------------+-------------------------------+
// +       segment_selector         |           offset_low          |
// +--------------------------------+-+---+-+-------+---------+-----+
// +        offset_middle           |P|DPL|0|Type   |0 0 0 0 0| IST |
// +--------------------------------+-+---+-+-------+---------+-----+
// +                           offset_high                          |
// +----------------------------------------------------------------+
// +                            reserved                            |
// +----------------------------------------------------------------+
// DPL : descriptor_privilege_level. 割り込みハンドラの実行権限を設定する．たいていは0を設定すればよい．
// type : 記述子の種別
union InterruptDescriptorAttribute {
  uint16_t data;
  struct {
    uint16_t interrupt_stack_table : 3;
    uint16_t : 5;
    DescriptorType type : 4;
    uint16_t : 1;
    uint16_t descriptor_privilage_level : 2;
    uint16_t present : 1;
  } __attribute__((packed)) bits;
} __attribute__((packed));

struct InterruptDescriptor {
  uint16_t offset_low;
  uint16_t segment_selector;
  InterruptDescriptorAttribute attr;
  uint16_t offset_middle;
  uint32_t offset_high;
  uint32_t reserved;
} __attribute__((packed));
```
unionを使った記述は組み込み系によく使われるイメージで，レジスタの読み書きの際に使われる．
`__attribute__((packed))`は構造体bitを詰めるための設定．
bit単位で細かく役割が決められているため，コンパイラで調整が入るのを防ぐ役目がある．

次にこの割り込みのunionに設定を入れる．
構造体に値をセット-->IDTに登録
IDTに登録するのは，メモリ領域指定が必要なため，アセンブリで記述する必要がある．
``` asm:asmfunc.asm
global LoadIDT  ; void LoadIDT(uint16_t limit, uint64_t offset);
LoadIDT:
    push rbp
    move rbp, rsp
    sub rsp, 10
    mov [rsp], di   ; limit
    mov [rsp + 2], rsi  ; offset
    lidt [rsp]
    mov rsp, rbp
    pop rbp
    ret
```
アセンブリ言語はアドレスをマイナス方向にずらすことで，スタックを行う．
`sub rsp, 10`はrsp (=addressのこと)から-10する命令を意味する．
この10Addressの領域にlimit(2byte)とOffset(8byte)を詰め込む.
詳細なアセンブリの説明は4章のコラムで説明している．

# MSI割り込み
割り込みを発生させる方式の一つ．
MSI : Message Signaled Interrupts
決められたフォーマットの情報を特定のメモリアドレス (=Message Address)に書き込むことで割り込みを発生させる．
メモリアドレスと値のフォーマットはCPUの仕様で規定されていて，x86-64は以下のようになっている．
```
// Message Address register format
31         2019             1211      4   3   2   1  0
+-----------+----------------+---------+----+----+----+
+  0xfee    | Destination ID | reserve | RH | DM | XX |
+-----------+----------------+---------+----+----+----+
RH : Redirection Hint
DM : Destination Mode
Desination ID : 割り込みを通知するCPUコアの番号 (Local APIC ID)
// Message Data register format
31         16 15   14  13      11 10 8 7     0
+-----------+----+----+----------+----+-------+
+  reserved | TM | LV | reserved | DM | vector|
+-----------+----+----+----------+----+-------+
TM : Trigger Mode
LV : Level
DM : Delivery Mode
```
Destination IDを使って，どのコアに割り込みを配送するかの指定ができる．
Redirection Hintは1にすれば，いろいろ柔軟に割り込みの配送ができるが，今回は0で設定する．
DATAの方のVector部分が割り込みベクタ番号の設定になる．
xHCIの割り込みなら，VectorにxHCIと同じ番号を入れればよい．

割り込みベクタの定義は以下のようにしている．
``` C++:interrupt.hpp
class InterruptVector {
 public:
  enum Number {
    kXHCI = 0x40,
  };
};
```

これらを踏まえて，main.cpp内でMSIの設定を行う．
```C++:main.cpp
  const uint8_t bsp_local_apic_id =
    *reinterpret_cast<const uint32_t*>(0xfee00020) >> 24;
  pci::ConfigureMSIFixedDestination(
      *xhc_dev, bsp_local_apic_id,
      pci::MSITriggerMode::kLevel, pci::MSIDeliveryMode::kFixed,
      InterruptVector::kXHCI, 0);
```
`bsp_local_apic_id`は最初に動くコア(Bootstrap Processor)のコアの番号を示す．
上記の例でいうと，0xfee00020番地の31:24番地の値が該当する．
この番号をもとに，`pci::ConfigureMSIFixedDestination()`でMSIの設定をしている．
```C++:pci.cpp
  Error ConfigureMSIFixedDestination(
      const Device& dev, uint8_t apic_id,
      MSITriggerMode trigger_mode, MSIDeliveryMode delivery_mode,
      uint8_t vector, unsigned int num_vector_exponent) {
    uint32_t msg_addr = 0xfee00000u | (apic_id << 12);
    uint32_t msg_data = (static_cast<uint32_t>(delivery_mode) << 8) | vector;
    if (trigger_mode == MSITriggerMode::kLevel) {
      msg_data |= 0xc000;
    }
    return ConfigureMSI(dev, msg_addr, msg_data, num_vector_exponent);
  }
```
Message AddressとMessage Dataを用意し，MSI Configの設定を行う．
Destination ID : 今回はapic idが該当
delivery mode : Level割り込みの場合は`MSITriggerMode::kLevel`を指定
vector : 割り込み番号指定．今回は0を指定している．
`ConfigureMSI()`は先をたどると，MSI / MSIXの分岐 --> MSI Capabilityの読み込み / 書き込み --> レジスタ書き込み，というようにたどれる．

# FIFOを使った割り込み高速化
割り込みハンドラは一般的になるべく処理時間がかからないように作る必要がある．
割り込み処理中はほかの割り込み処理を受け付けられないため．

## FIFO
First In First Outの略．
入れていった順番に出力するイメージ．
OSによるメモリ管理が実装されていないので，リングバッファを用いて自力で実装する．
```C++:queue.hpp
template <typename T> class ArrayQueue {
  public:
    template <size_t N> ArrayQueue(std::array<T, N>& buf);
    ArrayQueue(T* buf, size_t size);
    Error Push(const T& value);
    Error Pop();
    size_t Count() const;
    size_t Capacity() const;
    const T& Front() const;

  private:
    T* data_;
    size_t read_pos_, write_pos_, count_; // 読み出しの位置，書き込みの位置，データ保持数
    const size_t capacity_; // 最大保持数．リングバッファの大きさ．
};

// 1引数コンストラクタ．
// array型をもとに，2引数コンストラクタに役割を委譲している．
template <typename T> template <size_t N>
ArrayQueue<T>::ArrayQueue(std::array<T, N>& buf) : ArrayQueue(buf.data(), N) {}

// 2引数コンストラクタ
// 配列とサイズを引数にわたし，リングバッファとして格納している．
template <typename T> ArrayQueue<T>::ArrayQueue(T* buf, size_t size)
  : data_{buf}, read_pos_{0}, write_pos_{0}, count_{0}, capacity_{size} {}

// Push (要素を追加するメソッド)
// count数とwrite_posをインクリメントする．
// write_positionがcapacityと同じになったら0に戻す．(リングのつなぎ合わせの部分)
// 要素がcapacityを超えたらエラーを返す．
template <typename T> Error ArrayQueue<T>::Push(const T& value) {
  if (count__ == capacity_) return MAKE_ERROR(Error::kFull);

  data_[write_pos_] = value;
  ++count_;
  ++write_pos_;
  if (write_pos_ == capacity_) write_pos_ = 0;
  return MAKE_ERROR(Error::kSuccess);
}

// Pop (要素を前から削除するメソッド)
// count数をデクリメント，read_posをインクリメントする．
// read_positionがcapacityと同じになったら0に戻す．(リングのつなぎ合わせの部分)
// 要素がcapacityを超えたらエラーを返す．
template <typename T> Error ArrayQueue<T>::Pop() {
  if (count_ == 0) return MAKE_ERROR(Error::kEmpty);

  --count_;
  ++read_pos_;
  if (read_pos_ == capacity_) read_pos_ = 0;
  return MAKE_ERROR(Error::kSuccess);
}

// countを返すだけ
template <typename T>
size_t ArrayQueue<T>::Count() const {
  return count_;
}

// capacityを返すだけ
template <typename T>
size_t ArrayQueue<T>::Capacity() const {
  return capacity_;
}

// 先頭を取り出すだけ
template <typename T> const T& ArrayQueue<T>::Front() const {
  return data_[read_pos_];
}
```
templateを使うことで，型とbuffer数をある程度自由に制御できるようにしている．
PushするときはWriteの位置をインクリメントする．
PopするときはReadの位置をインクリメントする．
両方ともbufのsizeになったときに0に戻す．
これにより，先頭と最後の位置をぐるぐる動かす仕組み．

## 割り込みの高速化
Queueを使うデータはMessage型を定義する．
割り込みハンドラからメイン関数に対して送信するための専用のメッセージ構造体で，内部にtype値を持つ．
現時点ではxHCIのみだが，後々追加していく．
割り込みハンドラでは，Message型をPushするだけになる．

あとはこれを`kernalMain()`の内部でのwhile loopで逐次処理すればよい．
以下にコード例を示す．
```C++:main.cpp
// Message型の定義
struct Message {
  // type型を用意
  enum Type {
    kInterruptXHCI,
  } type;
};
// queueを宣言
ArrayQueue<Message>* main_queue;

// 割り込みハンドラを定義．
// queueにMessage Queueを追加し，割り込み終了を通知する．
__attribute__((interrupt)) void IntHandlerXHCI(InterruptFrame* frame) {
  main_queue->Push(Message{Message::kInterruptXHCI});
  NotifyEndOfInterrupt();
};

KernelMain() {
...
  // 割り込み情報のQueueを用意．
  std::array<Message, 32> main_queue_data;
  ArrayQueue<Message> main_queue{main_queue_data};
  ::main_queue = &main_queue;
...
...
...
  while (true) {
    // inlineアセンブラで割り込みフラグ(RFLAGSレジスタにあるフラグ)を0にする．
    // Queue操作中に割り込みが入るのを阻止するため．
    __asm("cli");
    if (!main_queue.Count()) {
      // 割り込みフラグを1にして，省電力モードに移行する．
      // 割り込みが入った場合は省電力モードから抜け出し，次へ進む．
      __asm__("sti\n\thlt");
      continue;
    }
    // Message Queueの先頭要素を取り出し，割り込みフラグを1にする．
    Message msg = main_queue.Front();
    main_queue.Pop();
    __asm__("sti");

    switch (msg.type) {
      case Message::kInterruptXHCI:
        while (xhc.PrimaryEventRing()->HasFront()) {
          if (auto err = ProcessEvent(xhc)) Log(kError, "Error while ProcessEvent: %s at %s:%d\n", err.Name(), err.File(), err.Line());
        }
        break;
      default:
      Log(kError, "Unknown message type: %d\n", msg.type);
    }
  }
  
```

一通り写経してから動かしたのだが，なぜか下のようにQEMUの表示がバグってしまった．
マウスは一切動かず，完全に詰んだ．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/405454/8655109d-1964-9b6b-a513-815c317416de.png)
gitの状態をもとに戻したり，edkのセットアップをやり直したりしたのだが，にっちもさっちもいかず...
6章のgitをcheckoutしても，前回動いていたPollingでのマウス操作も動かなくなっているため，原因はgitのコードではなさそうだと思う.
誰か，原因分かる人教えて下さい...


# まとめ
- 割り込みによるマウス操作の実装を行った
    - MSIを使って，マウス操作時に割り込みハンドラを実行するイメージ
    - 割り込みはベクタの中にハンドラのポインタを置いておく
- FIFOを自分で作成し，マウス操作を高速化した
    - 割り込み中の割り込みなどを阻止するため割り込みハンドラはなるべく短くする
    - 割り込みの際には変化をFIFOに入れておいて，mainのループで反映させると高速化できる
    - 割り込みフラグをDisableにするは`cli`命令，Enableにする場合は`sti`命令をインラインアセンブラで使う

なぜかQEMUから出てくるWindowがバグっているので，次の章でも何も起きなかったら，いったんUbuntu再インストールからスタートする予定．
--> Windowsの再起動を行ったら画面化けは治りました．ただし，マウスはちょっとだけ動いてからハングします．
たぶん割り込みがうまくいっていないのでは？と思うのですが，原因はまだわかっていません．