気合で動かすオペレーティングシステム

17.1K Views

March 22, 23

スライド概要

2023/3/13「TIER IV Computing System Workshop 2023」
発表者:村上太一

profile-image

TIER IV(ティアフォー)は、「自動運転の民主化」をビジョンとし、Autowareを活用したソフトウェアプラットフォームと統合開発環境を提供しています。 #Autoware #opensource #AutonomousDriving #deeptech

シェア

またはPlayer版

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

たのしいよ 気合いで動かすオペレーティングシステム -なんたらかんたら村上太一 / 30歳 髪の色 / 黒 瞳の色 / 黒 職業 / 修士2年生 : 4回目

2.

本日のテーマ 本日のテーマ 本日のテーマ 本日のテーマ 本日のテーマ 本日のテーマ 本日のテーマ 本日のテーマ OS 本日のテーマ 本日のテーマ 本日のテーマ 本日のテーマ 本日のテーマ 本日のテーマ 本日のテーマ 本日のテーマ

3.

「いや、CPUとか普通作らんやろ jk」「たった40命令ぐらい黙って作れよ」 CPUを作った、まではいいものの... メモリ (4GBぐらい) 最強の CPU メモリの大海原を 読み、実行し、書く ... OS…? 夢のまた夢 ウォォン、俺はまるで チューリングマシンだ! RISC-V ISA (RV32I だけでも) なんだこいつ... クソつまんねぇな... あなた 整数即値 9, 整数 10, 即値 2, 分岐 8 メモリ操作 9, ECALL, EBREAK 計 40 命令 も実装したというのに 一体何が足りないというのか

4.

LINKs ● ● ● ● ● ● ● ● ● riscv isa spec: RISC-V 命令仕様 [PDF] riscv privilege spec: RISC-V 特権仕様 [PDF] platform level interrupt controller spec: RISC-V PLIC (Platform Level Interrupt Controller) 仕様 [Github] advanced core local interrupt spec: RISC-V ACLINT (Advanced Core Local Interrupt) 仕様 [Github] virtio spec: Virtio 仕様 [PDF] uart 16655a spec: http://byterunner.com/16550.html devicetree specification: Github 教材Simulator: https://github.com/harihitode/ladybird/tree/main/sim (ビルド済) Kernel and Disk Images: Google Drive

5.

本日の目標 OSを降臨させるため、CPUではなく Platformを作る最初の一歩を踏み出しましょう なお、OSの解説はほとんどないです。本日のテーマが何だって?しらねぇな

6.

おしながき ● 第一章: ドキ☆ドキ Kernelウォッチング!基礎知識 ELF について ● 第二章: CPUと世界を繋げ!愉快なPeripheralたち (UARTとDISK) ● 第三章: MMU降臨... グッバイ物理世界 ● 第四章: 最後の関門「例外&割り込み」詠唱せよ、システムコール! ● まとめ: 必要だったCSR全解説 ● 第零章: Devicetree Specification そしてLinuxへ

7.

OSとは何か? A. ????

8.

OSとは何か? A. プログラム OSに慣れるためには、とにかく Kernelをビルドしましょう。目標は一日一回 下を参考にすれば、あなたも今日から OSビルダーだ! Linux: http://mcu.cz/images_articles/4980-opdenacker-embedded-linux-45minutes-riscv.pdf (神資料) xv6: https://github.com/harihitode/ladybird-xv6 でmake一発 (この子はclangでもOK) コンパイラやToolchain一式の用意に慣れてなければ、 https://buildroot.org/ が特にオススメ なんもかんも面倒な人向けに、教材としてバイナリを以下に置いておきます Linux: xv6:

9.

ELF (Executable, Linkable Format) ● ● ● エントリポイント (プログラムカウンタ初期値) ロードすべきバイナリの(R/W/E)属性、ロード先メモリアドレス (動的リンクならその情報、リンク可能ならアドレスのリロケーションの情報 ... ごにょごにょ) つまり... プログラムを実行するための全ての情報がつまっている OSとて単なるELF形式のバイナリだ

10.

readelf で見物 (ヘッダ編) エントリポイントはどうやら 0x80000000からを想定しているらしい ISAとしては、RVC C拡張こみのISAで、F拡張は無しらしい ELF header Program Header バイナリ (TEXT, DATA) Section Header (リンク時に使うので、実行 時は重要では無い )

11.

readelf で見物 (プログラムヘッダ編) ロード対象 (Type == Load) は3区画あり ELFバイナリのOffset位置~FileSizを 物理メモリPhysAddrの位置に配置する FileSiz != MemSizは、残りの領域はゼロ埋め せよ、の意 ELF header Program Header バイナリ (TEXT, DATA) 他にも -s で、シンボルのアドレス情報閲覧はよくやる Section Header (リンク時に使うので、実行 時は重要では無い )

12.

まとめ: つまりOSもプログラム 1. プログラムヘッダを読み、適切にロードする 2. プログラムカウンタをエントリーポイントにセット 3. CPU実行開始 OSが動作する。完。おつかれさまでした

13.

第2章: OSに必要なPeripheral RISC-V OS-A Platformに、CPU以外に必要な”モノ”が定義されている https://github.com/riscv/riscv-platform-specs/blob/main/riscv-platform-spec.adoc 究極的に必要なPeripheralは2つだけ ● UART ○ ● 皆大好きprintf debugもこいつがなければできねぇ。いわゆる COM, シリアルポート DISK ○ WindowsがDOS (Disk OS) だった時代から、 Disk操作はOSの最大の目的の一つ

14.

xv6が”暗黙”に想定するアドレスマップ (in メモリ) 0x0200_0000 ~ 0x02FF_FFFF [PLIC] 外部割り込み 0x0C00_0000 ~ 0x0C00_FFFF [ACLINT] 内部割り込み Memory Mapped I/O 0x1000_0000 ~ 0x1000_0FFF [UART コントローラ] この章の主役 0x1000_1000 ~ 0x1000_1FFF [DISK コントローラ] 0x8000_0000 ~ PHYSTOP [物理RAM] Memory

15.

UART Controller [ns16550a] 名前 #define UART_ADDR_RHR #define UART_ADDR_THR #define UART_ADDR_IER #define UART_ADDR_FCR #define UART_ADDR_ISR #define UART_ADDR_LCR #define UART_ADDR_MCR #define UART_ADDR_LSR #define UART_ADDR_MSR レジスタ位置 0 0 1 2 2 3 4 5 6 0x0200_0000 ~ 0x02FF_FFFF [PLIC] 外部割り込み 0x0C00_0000 ~ 0x0C00_FFFF [ACLINT] 内部割り込み 0x1000_0000 ~ 0x1000_0FFF [UART コントローラ ] 0x1000_1000 ~ 0x1000_1FFF [DISK コントローラ ] 0x8000_0000 ~ PHYSTOP [物理RAM] 誤解を恐れずにいうと 0x1000_0000を読めば Input 0x1000_0000を書けば Output される ただし、Flow Control Registerなどの値によって 0x1000_0000の意味が変わったりするため注意

16.

DISK(Block Device) Controller [virtio-blk mmio] 0x0200_0000 ~ 0x02FF_FFFF [PLIC] 外部割り込み 0x0C00_0000 ~ 0x0C00_FFFF [ACLINT] 内部割り込み 0x1000_0000 ~ 0x1000_0FFF [UART コントローラ ] めちゃくちゃ多機能のため、典型的な READ/WRITE 0x1000_1000 ~ 0x1000_1FFF [DISK コントローラ ] 0x8000_0000 ~ PHYSTOP [物理RAM] RAM上 CPU 命令用メモリ領域 QUEUE 0 (命令) QUEUE 1 (命令) DISC Controller Disk QUEUE 2 (命令) R/W用バッファ領域 QUEUE 3 ちなみに色々ありすぎて QUEUE 4 QUEUE 5 QUEUE 6 QUEUE 7 正直未定義がいっぱいある

17.

第3章: MMU - 仮想メモリ (SV32) とは 仮想 物理 未マップ ゆーざのぺーじ かーねるのぺーじ ゆーざのぺーじ ゆーざのぺーじ 未マップ 4KiBとかで区切る : = これをページ アドレスのことをページナンバーという

18.

第3章: MMU - 仮想メモリ (SV32) とは [31] ON/OFF [21:0] ASID PPN (22bit) SATP: S-Address Translation and Protection ルートページテーブル [0エントリ目] PPN (Phisical Page Number) = ルートページテーブルのページ番号 1エントリ目 (34bit中上位22bit) 2エントリ目 … 1023エントリ目 テーブルは1024エントリ存在する テーブルエントリは、葉 (Map情報) or 子テーブル 子テーブルがある場合は 2^12 = 4KiBのテーブル ルートページテーブルが即 Map情報だと 2^22 = 4MiB の メガテーブルとなる (なお、Linuxの場合こっちがデフォ ) X == 0 & R == 0 & W == 0の場合は子テーブル のアドレス先

19.

第3章: ATPがONになった瞬間の世界 (Linuxの場合) relocate_enable_mmu (arch/riscv/boot.S) 物理Addr 仮想Addr 80041044 c0001044: 80041048 c0001048: 18051073 00000517 csrw satp,a0 # 仮想化ON auipc a0,0x0 このままだとそのまま PCが進行する つまり、0x80041044 -> 0x80041048 となってしまい、仮想世界に移行できない。困りました! Idea: 意図的にページフォールトを発生させる 1. 2. 3. 0xc0001048を0x80041048にマップし、0x80041048をマップしない、ページディレクトリを作成する トラップベクタを0xc0001048へ設定し、フォールトを発生させる 0x80041044 -> 0xc0001048 のPCの流れとなる

20.

第3章: ATPがONになった瞬間の世界 (Linuxの場合) relocate_enable_mmu (arch/riscv/boot.S) 物理Addr 仮想Addr 8004101a c000101a: 8004101e c000101e: 80041020 c0001020: 80041024 c0001024: 80041028 c0001028: 8004102c c000102c: 80041030 c0001030: 80041032 c0001032: 80041034 c0001034: 80041038 c0001038: 8004103c c000103c: 8004103e c000103e: 80041040 c0001040: 80041044 c0001044: 80041048 c0001048: 03260613 962e 10561073 00c55613 011ae597 b0858593 418 8e4d 018bc517 fcc50513 8131 8d4d 12000073 18051073 00000517 addi a2,a2,50 # c0001048 add a2,a2,a1 csrw stvec,a2 # Exception時: satp直後にPCを移動 srli a2,a0,0xc auipc a1,0x11ae addi a1,a1,-1272 # c11aeb30 <satp_mode> lw a1,0(a1) or a2,a2,a1 auipc a0,0x18bc addi a0,a0,-52 # c18bd000 <trampoline_pg_dir> ページDIR srli a0,a0,0xc or a0,a0,a1 sfence.vma csrw satp,a0 # 仮想化ON auipc a0,0x0 # 80041048は未マップ -> Load Access Fault

21.

第3章: User -> Kernel への移行 (トランポリン) ユーザ世界 トランポリンページ カーネル世界 トランポリンページ SATP を書き換え ちゃうよ 物理メモリ トランポリンページ かーねるのぺーじ … ecall … システムコール処理 ゆーざのぺーじ

22.

第4章: TRAP Code一覧 (左が割り込み、右が例外)

23.

第4章: TRAPException (例外) ● ● ページフォールト ECALL (environment call) Interrupt (割り込み) ソフトウェア割り込み (ACLINT MTIMER) など。いっぱいあるよ! 例外は、それぞれ発生した時の特権モードで 細別される U-Mode-Environment-Call = (ユーザモード ECALL) S-Mode-Load-Access-Fault = (スーパーバイザモード Load Access Fault) M-Mode = (マシンモードふがふが ...) タイマー割り込み (ACLINT MSWI) 外部割り込み (PLIC [UART/DISK])

24.

第4章: TRAP - 例外 [Exception] 編 ACLINT/PLIC ACLINT PLIC タイマー(RTC)の読み込み 目覚まし時計 (mtimecmp)の設定 ペリフェラル (UART/DISK) からの割り込みの設 定 他のコアへの SWI (Software Interrupt) の書き込み 各Hart各特権モード (=context) での 優先度コントロール 割り込みのOn/Off Address Mapは以下で決められてる RISC-V PLIC (Platform Level Interrupt Controller) 仕様 [Github] シングルコアなら M-Mode/S-Modeの 2コンテキスト Address Mapは以下で決められている RISC-V ACLINT (Advanced Core Local Interrupt) 仕様 [Github]

25.

第4章: TRAP実現の機序 基本は有効TRAP (例外/割り込み) チェック -> 優先順位にもとづき選択 -> EPCに次PCにセット -> PCにTVECをセット -> (基本は)M-Modeへ (例外が移譲) MRET(SRET) 発生 -> PCにEPCをセット 注意 (一番注意が必要) 移譲 (M-Modeで本来うけるTRAPをS-Modeでも)うける Delegation のルール (RISC-V スペックより) (a) if either the current privilege mode is M and the MIE bit in the mstatus register is set, or the current privilege mode has less privilege than M-mode (b) interrupt bit is set in both mip and mie (c) interrupt is not set in mideleg https://github.com/harihitode/ladybird/blob/main/sim/csr.c <- で実装してるけど、かなり闇 ...

26.

必要な全CSRプチ解説 (xv6カーネル実行時の登場順) CSR ADDR 名前 意味 コメント 0x341 mepc MRET時に復帰する プログラムカウンタ 通常は例外発生 PCの次 main関数のAddressをセット -> MRET すると、 main関数がSupervisor Modeで実行される 0xF14 hartid HART (Hardware Thread) 0返せばいいじゃん 0x300 mstatus M-Modeにおける各種 Status 割り込み(Pending, 有効化)等 真面目に実装しなくても動く 少なくとも割り込みは実装してあげて 0x180 satp Address Translation & Protection 花形。うまく動くとキモチイイ M-Modeには無い

27.

必要な全CSRプチ解説 (xv6カーネル実行時の登場順) CSR ADDR 名前 意味 コメント 0x302 medeleg M Mode用例外をS Modeでも 処理できるようする移譲 解説の時に話した通り、めちゃややこい 0x303 mideleg 上の割り込み版 こいつもそう。説明が合ってるか不安 0x104 sie 割り込み有効 真面目に実装しなくても動く 少なくとも割り込みは実装してあげて 0x3b0 mpmpaddr0 PMP (Physical Memory Protection) PMPはなくてもよい 0x3a0 mpmpcfg0 PMPはなくてもよい

28.

必要な全CSRプチ解説 (xv6カーネル実行時の登場順) CSR ADDR 名前 意味 コメント 0x340 mscratch 汎用レジスタ (M Trap用) 多目的に使用される 0x305 mtvec トラップ時飛び先 PC (M-mode) 0x304 mie 割り込み有効 (M-Mode) 元締め 0x100 sstatus Status (S-Mode) 真面目に実装しなくても動く 少なくとも割り込みは実装してあげて 0x105 stvec トラップ時飛び先 PC (S-mode) PMPはなくてもよい

29.

必要な全CSRプチ解説 (xv6カーネル実行時の登場順) CSR ADDR 名前 意味 コメント 0xc00 ucycle サイクルカウンタ クロック毎にUP 0xc01 utime 時計 今回10MHzぐらいで動作している想定 0xc02 uinstret 実行命令数カウンタ 0xc80 ucycleh サイクルカウンタ 上位32bit クロック毎にUP 0xc81 utimeh 時計 上位32bit 今回10MHzぐらいで動作している想定 0xc82 uinstreth 実行命令数カウンタ 上位32bit

30.

必要な全CSRプチ解説 (xv6カーネル実行時の登場順) CSR ADDR 名前 意味 コメント 0x344 mip 割り込み(ペンディング中 ) M-Mode ビットフィールドは TRAP_CODEに対応して いる 0x144 sip 割り込み(ペンディング中 ) S-Mode 0x141 sepc SRET時復帰先PC システムコールの時はこいつ 0x142 scause トラップ原因 トラップ原因システムコール時は 0x00000009 0x143 stval トラップ時 多目的レジスタ 例えばロード失敗の時はそのアドレス 0x140 sscratch 多目的レジスタ (S-Mode) 多目的

31.

必要な全CSRプチ解説 (xv6カーネル実行時の登場順) CSR ADDR 名前 意味 コメント 0x342 mcause トラップ原因 タイマーとかで登場かなぁ (あやふや) 0x343 mtval トラップ時多目的レジスタ 出てきたっけこいつ (あやふや) 計28レジスタ! この他にもVendor IDとかいっぱいあるけど、必要に応じて入れていこう

32.

xv6の実行挙動 起動~ ls コマンドまで xv6 kernel is booting が見えた瞬間めちゃくちゃ興奮する これだからやめられないぜ 御自身の手元でやってみる場合 カーネルとDISK (fs.img) のパスを適宜直してください 嘘のような本当の話ですが、 SRAI (即値算術右シフト ) を未実装だったのですが、なんか動きました (笑)

33.

おまけ: Devicetree Specification (DTS) Devicetreeとは... ● 「アドレスマップ」と「割り込み結合網」の定義である (なんとなくTreeっぽい...?) xv6では既知であった以下 を、DTB (Devicetree Blob) の形で保持し、 OSに渡すもの DTSはDevicetree CompilerでDTBにコンパイルされる メモリマップ 割り込み結合網 0x0200_0000 ~ 0x02FF_FFFF [PLIC] 外部割り込み 0x0C00_0000 み ~ 0x0C00_FFFF [ACLINT] 内部割り込 0x1000_0000 ~ 0x1000_0FFF [UART コントローラ] 0x1000_1000 ~ 0x1000_1FFF [DISK コントローラ] タイマー割り込み CPU ソフトウェア割り込み PLIC: 外部割り込み 0x8000_0000 ~ PHYSTOP [物理RAM] DISK (1番) UART (10番)

34.
[beta]
おまけ: Devicetree Specification (DTS)
/dts-v1/;
/{
#address-cells = <1>;
#size-cells = <1>;
model="harihitode,ladybird";
chosen {
bootargs = "console=ttyS0 rw root=/dev/vda";
stdout-path = &serial0;
};
virtio0: virtio@10001000 {
compatible = "virtio,mmio";
interrupt-parent = <&plic0>;
interrupts = <0x1>;
reg = <0x10001000 0x1000>;
reg-shift = <2>;
};
…

address-cells, size-cells はメモリマップの表記の際の
それぞれのBlockの幅
メモリマップは <アドレス, サイズ> となる
例えば 下のvirtio0の、reg (メモリマップ) の場合
仮に #address-cells = <2>, #size-cells = <1> であれば
reg = <0x00000000 0x10001000 0x1000>; となる
chosenのbootargsは、Linux Kernelが自主的にひろって
くれる。
stdout-pathはearlycon (boot時) のearlycon用
modelは比較的自由にかいていいので、 (たぶん)
model=”RISC-Vプラットフォームでございますわ! ”
とか書いておくと、面白いものが見られるゾ☆

35.
[beta]
おまけ: Devicetree Specification (DTS)
serial0: serial@10000000 {
clock-frequency = <0x10000000>;
compatible = "ns16550a";
current-speed = <115200>;
device_type = "serial";
interrupt-parent = <&plic0>;
interrupts = <0xa>;
reg = <0x10000000 0x1000>;
reg-shift = <0>;
};

基本的にノードは以下のような書き方となる
エイリアス: 名前@アドレス先頭 {
compatible = “使用させたいドライバ ”;
device_type = “デバイスの属性 ”;
reg = <アドレス 領域サイズ>;
interrupt-parent = <RISC-Vの場合は大抵 PLIC>;
interrupts = <割り込み番号 >;
}
ちなみにreg-shiftは
0を設定しておくと
0, 1, 2, 3… のようなアドレッシング
2を設定すると
0, 4, 8, c… のようなアドレッシングとなる
xv6はuartだけ0, 1, 2, 3… でアクセスする

36.
[beta]
おまけ: Devicetree Specification (DTS)
cpus {
#address-cells = <1>;
#size-cells = <0>;
timebase-frequency = <10000000>;

階層っぽくかくことができる
(今回シングルなので階層感はない )
CPUについてはお約束な感じのものが多い

cpu0: cpu@0 {
device_type = "cpu";
i-cache-size = <32768>;
d-cache-size = <32768>;
compatible = "riscv";
mmu-type = "riscv,sv32";
clock-frequency = <100000000>;
reg = <0>;
riscv,isa = "rv32imac";
status = "okay";
cpu0_intc: interrupt-controller {
#interrupt-cells = <1>;
compatible = "riscv,cpu-intc";
interrupt-controller;
};
};
};

Interrupt Controllerは割り込み網で頻繁に登場する

CPUs

CPU

Interrupt
Controller

37.
[beta]
おまけ: Devicetree Specification (DTS)
plic0: interrupt-controller@c000000 {
compatible = "riscv,plic0";
#interrupt-cells = <1>;
interrupt-controller;
interrupts-extended = <&cpu0_intc 11 &cpu0_intc 9>;
riscv,ndev=<10>; (割り込みデバイス最大数)
reg = <0x0c000000 0x02000000>;
};
memory0: memory@80000000 {
device_type = "memory";
#address-cells = <1>;
#size-cells = <1>;
reg = <0x80000000 0x08000000>;
};
mtimer0: mtimer@2000000 {
compatible = "riscv,aclint-mtimer";
interrupts-extended = <&cpu0_intc 7>;
reg = <0x02000000 0x8 0x02007ff8 0x8>;
};

mswi0: mswi@2008000 {
compatible = "riscv,aclint-mswi";
#interrupt-cells = <1>;
reg = <0x02008000 0x8>;
interrupts-extended = <&cpu0_intc 3>;
interrupt-controller;
};
htif {
compatible = "ucb,htif0";
};
};

割り込み接続網はこんな感じで表現される
cpu0_intcのそれぞれ
PLICは、11: M-Mode 外部割り込み 9: S-Mode 外部割り込み
MSWIは、3: M-Mode ソフトウェア割り込み
TIMERは、7: M-Mode タイマー割り込み
htif実装していれば入れておく

38.

おまけ: Hardware Target Interface (UCB-HTIF) HOST Target Interface クリティカルに必要なシステムコールを、お手軽にエミュレーションする機能 例 ● ● Write (コンソールへの出力とか ) Exit (プログラムの終了、 Shutdownとか) アドレスTOHOSTに、Magic Memory (システムコールの番号 /引数が連続で格納されている ) の アドレスを格納 TOHOSTに何かかきこまれたかを検知 -> 当該System Callをエミュレーション FROMHOSTに完了を通知 -> Simulationに戻る UARTとかのHW実装をシミュレーションするのが究極に面倒 ... というときに使える (実質Sim限定)

39.

Linuxの実行画面 (失敗... くやしいのう、くやしいのう...)

40.

Linuxにまつわるエトセトラ http://mcu.cz/images_articles/4980-opdenacker-embedded-linux-45minutes-riscv.pdf OpenSBI ● M-Mode ~ S-Mode 担当 ● HW抽象化API (BIOS機能) を提供 Linux S-Mode以降担当 ● ● ● ● ● xv6はM-Mode系も一緒にやっていた LinuxはOpenSBIの繭にくるまれている なお、OpenSBIを実行する時 ● A0レジスタにはHART-ID ● A1レジスタにはDTB (Devicetree Blob)格納アドレス を予め与えてあげる必要がある kernel_command_lineに渡す文字列を忘れずに。 (console=ttyS rw root=/dev/vda) ○ console=ttySを指定すると、 earlyconをserialで初期化してくれるよ まずは死に物狂いで UART or HTIF (printk, early_console) への画面出力をめざそう 不足しているCSRを実装していこう BUG_ON, WARN_ONなどで printf デバッグだ! カーネルを読もう (真顔)

41.

まとめ ● UART (ns16550a), DISK (virtio blk) 相当のペリフェラル実装 ○ ● ACLINT ○ ● システムコール等 MMU (SV32) ○ ● ペリフェラル割り込み (UARTからのInput, Diskからの読み書き完了通知 ) ECALL (TRAP) にまつわる各種CSR ○ ● SW割り込み (複数コア間の通信 )、Timer割り込み (スケジューラ) PLIC ○ ● あるいは別に自作の UART, DISK相当のデバドラを書けばよい HW Page Walkの実装 (特にLinux等、より一般向けにはDTS, HTIFは用意すると嬉しい)