XHCIのINTERRUPT INについて 6

27,割り込みの許可
 アセンブリのsti命令を使用して割り込み許可をする。

[各portについて](20から26までが成功したものだけ)

28,normal trbを発行する。
 slot idと18で取得したendpoint descriptorのnumberとdirectionから計算したdciとslot id用のdci番用のtransfer ringと18で取得したendpoint descriptorのmax packet sizeか26で計算したhid report sizeを使用してnormal trbを発行する。
 (成功時には5でinterrupter register setの0番に設定したevent ringにtransfer event trbがslot idを持って送られる)

[各portについてはここまで](20から26までが成功したものだけ)

[割り込み時または割り込み後]
29,mouseやkeyboardのデータを取得する。
 mouseもしくはkeyboardのデータを26で取得したhid report descriptorをもとに取得する。

30,normal trbを発行する。
 28と同じように、slot idと18で取得したendpoint descriptorのnumberとdirectionから計算したdciとslot id用のdci番用のtransfer ringと18で取得したendpoint descriptorのmax packet sizeか26で計算したhid report sizeを使用してnormal trbを発行する。
 (成功時には5でinterrupter register setの0番に設定したevent ringにtransfer event trbがslot idを持って送られる)

XHCIのINTERRUPT INについて 5

[各portについて](14から19がすべて取得できたものだけ)

20,interrupt inを使用できるように設定する。
 18で取得したendpoint descriptorのnumberとdirectionからendpoint dciを計算する。
 計算したendpoint dciを使用してslot id番号用のinput control contextを設定する。
 slot id番号用のslot contextを設定する。
 slot id番号用でendpoint dci番号用のtransfer ringを作成する。
 slot id番号用のcontext entriesを設定する。
 slot id番号用のendpoint contextの(endpoint dci - 1)番を設定する。(18で取得したendpoint descriptorのintervalとslot id番号用でendpoint dci番号用のtransfer ringとmax packet sizeを使用する)

21,address device command trbを再度発行する。
 13と同じように、5でcrcrに設定したcommand ringとdoorbell register setの0番を使用してaddress device command trbを発行する。(slot idとslot id番号用のinput contextを使用する)
 (成功時には5でinterrupter register setの0番に設定したevent ringにcommand completion event trbがslot idと一緒に送られる)

22,configure endpoint command trbを発行する。
 5でcrcrに設定したcommand ringとdoorbell register setの0番を使用してconfigure endpoint command trbを発行する。(slot idとslot id番号用のinput contextを使用する)
 (成功時には5でinterrupter register setの0番に設定したevent ringにcommand completion event trbがslot idと一緒に送られる)

23,set configurationを発行する。
 slot idと20で設定したtransfer ringとdoor bellregister setのslot id番と20で計算したendpoint dciと16で取得したconfiguration descriptorのconfiguration valueを使用してset_configurationを発行する。
 (成功時には5でinterrupter register setの0番に設定したevent ringにtransfer event trbがslot idと一緒に送られる)

24,set interfaceを発行する。
 slot idと20で設定したtransfer ringとdoor bellregister setのslot id番と20で計算したendpoint dciと17で取得したinterface descriptorのalternate setting、interface numberを使用してset_interfaceを発行する。
 (成功時には5でinterrupter register setの0番に設定したevent ringにtransfer event trbがslot idと一緒に送られる)

25,set protocolを発行する。
 slot idと20で設定したtransfer ringとdoor bellregister setのslot id番と20で計算したendpoint dciと17で取得したinterface descriptorのinterface numberを使用してset_reportのset_protocolを発行する。
 (成功時には5でinterrupter register setの0番に設定したevent ringにtransfer event trbがslot idと一緒に送られる)

26,hid report descriptorを取得する。
 slot idと20で設定したtransfer ringとdoor bellregister setのslot id番と20で計算したendpoint dciと17で取得したinterface descriptorのinterface numberを使用してget_reportを発行する。
 (成功時には5でinterrupter register setの0番に設定したevent ringにtransfer event trbがslot idと一緒に送られる)
 取得したhid report descriptorを解析してhid report sizeを計算する。

[各portについてはここまで](14から19がすべて取得できたものだけ)

XHCIのINTERRUPT INについて 4

[各portについて](address device command trbが成功したものだけ)

14,device descriptorを取得する。
 12で設定したtransfer ringとdoorbell register setのslot id番とdci=1を使用して、device descriptorを取得する。
 (成功時には5でinterrupter register setの0番に設定したevent ringにtransfer event trbがslot idと一緒に送られる)

15,configure descriptorを9バイト取得する。
 2で設定したtransfer ringとdoorbell register setのslot id番とdci=1を使用して、configure descriptorを9バイトだけ取得する。
 (成功時には5でinterrupter register setの0番に設定したevent ringにtransfer event trbがslot idと一緒に送られる)

16,configure descriptorをすべて取得する。
 2で設定したtransfer ringとdoorbell register setのslot id番とdci=1と15で取得したconfigure descriptorのtotal lengthを使用して、configure descriptorをtotal lengthバイト取得する。
 (成功時には5でinterrupter register setの0番に設定したevent ringにtransfer event trbがslot idと一緒に送られる)

17,interface descriptorを取得する。
 16で取得したconfigure descriptorからinterface descriptorを取得する。

18,endpoint descriptorを取得する。
 16で取得したconfigure descriptorからendpoint descriptorを取得する。

19,hid descriptorを取得する。
 16で取得したconfigure descriptorからhid descriptorを取得する。

[各portについてはここまで](address device command trbが成功したものだけ)

XHCIのINTERRUPT INについて 3

[各portについて](1からcapability registerのmax portsまで)

7,接続しているか確認する。
 port register setの(port id -1)番のportscから接続を確認する。

8,(接続しているportについて)resetする。
 port register setの(port id -1)番のportscを使用してresetする。

9,enabledか確認する。
 port register setの(port id -1)番のportscからenabledを確認する。

10,enable slot command trbを発行する。
 5でcrcrに設定したcommand ringとdoorbell register setの0番を使用してenable slot command trbを発行する。
 (成功時には5でinterrupter register setの0番に設定したevent ringにcommand completion event trbがslot idと一緒に送られる)

11,command completion event trbからslot idを取得する。
 5でinterrupter register setの0番に設定したevent ringの先頭からcommand completion event trbを取得して、slot idを取得する。

12,controlを使えるように設定をする。
 slot id番号用のinput control contextの設定をする。
 slot id番号用のslot contextの設定をする。
 slot id番号用でdci=1のtransfer ringを作成する。
 slot id番号用のendpoint context 0番の設定をする。(slot id番号用でdci=1のtransfer ring、max packet sizeを使用する)
 
13,address device command trbを発行する。
 5でcrcrに設定したcommand ringとdoorbell register setの0番を使用してaddress device command trbを発行する。(slot idとslot id番号用のinput contextを使用する)
 (成功時には5でinterrupter register setの0番に設定したevent ringにcommand completion event trbがslot idと一緒に送られる)

[各portについてはここまで](1からcapability registerのmax portsまで)

XHCIのINTERRUPT INについて 2

1,pciからxhciコントローラを取得する。
 pciのclass codeのbase,sub,interfaceが0x0c,0x03,0x30のものを探して取得する。

2,msiを設定する。
 0xfee00020からlocal apic idを取得する。
 1で取得したpciデバイスとlocal apic idでmsiを設定する。

3,barを取得する。
 1で取得したpciデバイスからbarを取得する。
 barからmmio baseを計算する

4,各種registerを取得する。
 mmio baseから次を取得する。
  capabiliry registers
  operational registers
  runtime registers
  interrupter register set
  port register set
  doorbell register

5,xhc controllerを設定する。
 xhc controllerをリセットする。
 operational registerのdevice context base address array pointerを設定する。
 command ringをcrcrに設定する。
 event ringにinterrupter register setの0番を設定する。
 interrupter register setの0番の設定をする。
 割り込みの設定をする。

6,xhc controllerを開始する。
 xhc controllerの開始の設定をする。

XHCIのINTERRUPT INについて 1

自作osを作っている間に作ったxhciのinterrupt inについてプログラムの流れを載せたいと思います。

まず大枠の流れについて書きます。
1,pciからxhciコントローラを取得する。
2,msiを設定する。
3,barを取得する。
4,各種registerを取得する。
5,xhc controllerを設定する。
6,xhc controllerを開始する。

[各portについて](1からcapability registerのmax portsまで)
7,接続しているか確認する。
8,(接続しているportについて)resetする。
9,enabledか確認する。
10,enable slot command trbを発行する。
11,command completion event trbからslot idを取得する。
12,controlを使えるように設定をする。
13,address device command trbを発行する。
[各portについてはここまで](1からcapability registerのmax portsまで)

[各portについて](address device command trbが成功したものだけ)
14,device descriptorを取得する。
15,configure descriptorを9バイト取得する。
16,configure descriptorをすべて取得する。
17,interface descriptorを取得する。
18,endpoint descriptorを取得する。
19,hid descriptorを取得する。
[各portについてはここまで](address device command trbが成功したものだけ)

[各portについて](14から19がすべて取得できたものだけ)
20,interrupt inを使用できるように設定する。
21,address device command trbを再度発行する。
22,configure endpoint command trbを発行する。
23,set configurationを発行する。
24,set interfaceを発行する。
25,set protocolを発行する。
26,hid report descriptorを取得する。
[各portについてはここまで](14から19がすべて取得できたものだけ)

27,割り込みの許可

[各portについて](20から26までが成功したものだけ)
28,normal trbを発行する。
[各portについてはここまで](20から26までが成功したものだけ)

[割り込み時または割り込み後]
29,mouseやkeyboardのデータを取得する。
30,normal trbを発行する。

余分なものもあるかもしれませんが、これが大枠の流れになります。
ただし、virtualboxではデータを取得できましたが、qemuではデータを取得できませんでした。

カーソルを使ったAA木の実現

平衡2分探索木の一種であるAA木をカーソルで実現したソースコードです。

wikipediaのAA木の記事にある疑似コードをほぼそのまま写しています。

AIZU ONLINE JUDGEのITP2_8_B「Map:Delete」でAcceptedになったRustのソースコードです。

use std::cmp::min;
use std::fmt::Display;

#[derive(Copy, Clone)]
struct Node<T1, T2> {
    left_child: usize,
    right_child: usize,
    level: usize,
    value: std::option::Option<(T1, T2)>,
}
impl<T1, T2> Node<T1, T2> {
    fn new() -> Self {
        Node {
            left_child: 0,
            right_child: 0,
            level: 0,
            value: None,
        }
    }
}

const SIZE: usize = 60_0000;

struct AATree<T1, T2> {
    size: usize,
    space: [Node<T1, T2>; SIZE],
    available: usize,
}

impl<T1: Copy + PartialOrd + Display, T2: Copy> AATree<T1, T2> {
    fn debug(&self, cursor: usize) {
        if cursor == 0 {
            if self.space[cursor].left_child == 0 {
                return;
            } else {
                self.debug(self.space[cursor].left_child);
            }
        } else {
            if let Some((key, _)) = self.space[cursor].value {
                println!("{}, {}", cursor, key);
            }
            if self.space[cursor].left_child != 0 {
                self.debug(self.space[cursor].left_child);
            }
            if self.space[cursor].right_child != 0 {
                self.debug(self.space[cursor].right_child);
            }
        }
    }
    fn skew(&mut self, cursor: usize, parent_cursor: usize, left_or_right: bool) -> usize {
        if cursor == 0 {
            return 0;
        } else if self.space[cursor].left_child == 0 {
            return cursor;
        } else if self.space[self.space[cursor].left_child].level == self.space[cursor].level {
            let l = self.space[cursor].left_child;
            self.space[cursor].left_child = self.space[l].right_child;
            self.space[l].right_child = cursor;
            if left_or_right {
                self.space[parent_cursor].left_child = l;
            } else {
                self.space[parent_cursor].right_child = l;
            }
            return l;
        } else {
            return cursor;
        }
    }
    fn split(&mut self, cursor: usize, parent_cursor: usize, left_or_right: bool) -> usize {
        if cursor == 0 {
            return 0;
        } else if self.space[cursor].right_child == 0
            || self.space[self.space[cursor].right_child].right_child == 0
        {
            return cursor;
        } else if self.space[cursor].level
            == self.space[self.space[self.space[cursor].right_child].right_child].level
        {
            let r = self.space[cursor].right_child;
            self.space[cursor].right_child = self.space[r].left_child;
            self.space[r].left_child = cursor;
            self.space[r].level += 1;
            if left_or_right {
                self.space[parent_cursor].left_child = r;
            } else {
                self.space[parent_cursor].right_child = r;
            }
            return r;
        } else {
            return cursor;
        }
    }
    fn move_list_for_insert(
        &mut self,
        key: T1,
        x: T2,
        _cursor: usize,
        parent_cursor: usize,
        left_or_right: bool,
    ) {
        let old_available = self.available;
        self.available = self.space[old_available].left_child;
        self.space[old_available].left_child = 0;
        self.space[old_available].right_child = 0;
        self.space[old_available].value = Some((key, x));

        if left_or_right {
            self.space[parent_cursor].left_child = old_available;
        } else {
            self.space[parent_cursor].right_child = old_available;
        }
    }
    fn inside_insert(
        &mut self,
        key: T1,
        x: T2,
        mut cursor: usize,
        parent_cursor: usize,
        left_or_right: bool,
    ) {
        if cursor == 0 {
            if parent_cursor == 0 && self.space[cursor].left_child != 0 {
                self.inside_insert(key, x, self.space[cursor].left_child, cursor, true);
                return;
            }
            self.size += 1;
            self.move_list_for_insert(key, x, cursor, parent_cursor, left_or_right);
            return;
        } else {
            if let Some((node_key, _)) = &self.space[cursor].value {
                if key < *node_key {
                    self.inside_insert(key, x, self.space[cursor].left_child, cursor, true);
                } else if key > *node_key {
                    self.inside_insert(key, x, self.space[cursor].right_child, cursor, false);
                } else {
                    self.space[cursor].value = Some((key, x));
                }
            }
        }
        cursor = self.skew(cursor, parent_cursor, left_or_right);
        self.split(cursor, parent_cursor, left_or_right);
    }
    pub fn insert(&mut self, key: T1, x: T2) {
        self.inside_insert(key, x, 0, 0, true);
    }

    fn move_list_for_delete(&mut self, cursor: usize, parent_cursor: usize, left_or_right: bool) {
        let old_available = self.available;
        self.available = cursor;
        self.space[cursor].left_child = old_available;
        self.space[cursor].right_child = 0;
        self.space[cursor].value = None;

        if left_or_right {
            self.space[parent_cursor].left_child = 0;
        } else {
            self.space[parent_cursor].right_child = 0;
        }
    }
    fn successor(&self, mut cursor: usize) -> (usize, usize, bool) {
        let mut parent_cursor = cursor;
        cursor = self.space[cursor].right_child;
        let mut left_or_right = false;
        while self.space[cursor].left_child != 0 {
            parent_cursor = cursor;
            cursor = self.space[cursor].left_child;
            left_or_right = true;
        }
        return (cursor, parent_cursor, left_or_right);
    }
    fn predecessor(&self, mut cursor: usize) -> (usize, usize, bool) {
        let mut parent_cursor = cursor;
        cursor = self.space[cursor].left_child;
        let mut left_or_right = true;
        while self.space[cursor].right_child != 0 {
            parent_cursor = cursor;
            cursor = self.space[cursor].right_child;
            left_or_right = false;
        }
        return (cursor, parent_cursor, left_or_right);
    }
    fn decrease_level(&mut self, cursor: usize) -> usize {
        let should_be = min(
            self.space[self.space[cursor].left_child].level,
            self.space[self.space[cursor].right_child].level,
        ) + 1;
        if should_be < self.space[cursor].level {
            self.space[cursor].level = should_be;
            if should_be < self.space[self.space[cursor].right_child].level {
                self.space[self.space[cursor].right_child].level = should_be;
            }
        }
        return cursor;
    }
    fn inside_delete(
        &mut self,
        key: T1,
        mut cursor: usize,
        parent_cursor: usize,
        left_or_right: bool,
    ) {
        if cursor == 0 {
            if parent_cursor == 0 {
                if self.space[cursor].left_child != 0 {
                    self.inside_delete(key, self.space[cursor].left_child, cursor, true);
                }
            }
            return;
        } else {
            if let Some((node_key, _)) = &self.space[cursor].value {
                if key < *node_key {
                    self.inside_delete(key, self.space[cursor].left_child, cursor, true);
                } else if key > *node_key {
                    self.inside_delete(key, self.space[cursor].right_child, cursor, false);
                } else {
                    if self.space[cursor].left_child == 0 && self.space[cursor].right_child == 0 {
                        self.move_list_for_delete(cursor, parent_cursor, left_or_right);
                        return;
                    } else if self.space[cursor].left_child == 0 {
                        let (l, _parent_l, _left_or_right) = self.successor(cursor);
                        if let Some((l_key, l_x)) = self.space[l].value {
                            self.inside_delete(
                                l_key,
                                self.space[cursor].right_child,
                                cursor,
                                false,
                            );
                            self.space[cursor].value = Some((l_key, l_x));
                        }
                    } else {
                        let (l, _parent_l, _left_or_right) = self.predecessor(cursor);
                        if let Some((l_key, l_x)) = self.space[l].value {
                            self.inside_delete(l_key, self.space[cursor].left_child, cursor, true);
                            self.space[cursor].value = Some((l_key, l_x));
                        }
                    }
                }
            }
        }

        cursor = self.decrease_level(cursor);
        cursor = self.skew(cursor, parent_cursor, left_or_right);
        self.skew(self.space[cursor].right_child, cursor, false);
        if self.space[cursor].right_child != 0 {
            self.skew(
                self.space[self.space[cursor].right_child].right_child,
                self.space[cursor].right_child,
                false,
            );
        }
        cursor = self.split(cursor, parent_cursor, left_or_right);
        self.split(self.space[cursor].right_child, cursor, false);
    }
    pub fn delete(&mut self, key: T1) {
        self.inside_delete(key, 0, 0, true);
    }
    pub fn get(&self, key: T1) -> Option<T2> {
        if self.space[0].left_child == 0 {
            return None;
        }
        let mut cursor = self.space[0].left_child;
        loop {
            if let Some((node_key, node_x)) = self.space[cursor].value {
                if key < node_key {
                    if self.space[cursor].left_child == 0 {
                        return None;
                    } else {
                        cursor = self.space[cursor].left_child;
                        continue;
                    }
                } else if key > node_key {
                    if self.space[cursor].right_child == 0 {
                        return None;
                    } else {
                        cursor = self.space[cursor].right_child;
                        continue;
                    }
                } else {
                    return Some(node_x);
                }
            }
        }
    }
    pub fn new() -> Self {
        let mut space = [Node::<T1, T2>::new(); SIZE];
        for i in 1..space.len() - 1 {
            space[i].left_child = i + 1;
        }
        Self {
            size: 0,
            space: space,
            available: 1,
        }
    }
}

fn main() {
    let stdin = std::io::read_to_string(std::io::stdin()).unwrap();
    let stdin: Vec<&str> = stdin.split_whitespace().collect();

    let mut aa_tree = AATree::<&str, u32>::new();

    let mut i = 1;
    loop {
        if i >= stdin.len() {
            break;
        }
        let q = stdin[i].parse::<u32>().unwrap();
        if q == 0 {
            let key = stdin[i + 1];
            let x = stdin[i + 2].parse::<u32>().unwrap();
            aa_tree.insert(key, x);
            i += 3;
        } else if q == 1 {
            let key = stdin[i + 1];
            if let Some(x) = aa_tree.get(key) {
                println!("{}", x);
            } else {
                println!("0");
            }
            i += 2;
        } else if q == 2 {
            let key = stdin[i + 1];
            aa_tree.delete(key);
            i += 2;
        }
    }
}