x64マルチプロセッサ環境で他のプロセッサを起動させる方法

# はじめに

こんにちは．[だいみょーじん](https://x.com/Egh2Deywos)です．
この記事は，[第39回自作OSもくもく会](https://osdev-jp.connpass.com/event/318075/)で発表した内容をまとめ，[自作OSアドベントカレンダー2024](https://adventar.org/calendars/10539)の9日目の記事として公開したものです．
私が開発しているRust製の自作OS，[HeliOS](https://github.com/TaiseiIto/HeliOS)における複数プロセッサの起動の方法およびプロセッサ間通信の方法について解説します．
[HeliOS](https://github.com/TaiseiIto/HeliOS)はx64アーキテクチャ上で動作するOSで，以降の説明においてもx64アーキテクチャを想定します．

# 並行処理と並列処理

現代のコンピュータは，ブラウザでネットを閲覧しつつ，メールを書きつつ，エクセルにデータを入力しつつ，というように，複数のアプリケーションを同時に走らせる並行処理の機能を持っています．
並行処理の実現方法として，まずひとつのプロセッサが高速にタスクを切り替えて，あたかも同時に複数のタスクを処理しているように見せかける方法があります．
これは「３０日でできる！OS自作入門」（ISBN 9784839919849）や「ゼロからのOS自作入門」（ISBN 9784839975869）で説明されている方法で，プロセッサがひとつあれば並行処理を実現できる比較的簡単な方法です．
しかし，今どきのコンピュータは大抵複数のプロセッサを持っているわけで，全てのプロセッサを使わないのはもったいないです．
複数のプロセッサを使用して，真に同時に複数のタスクを処理する方法を，並列処理と呼びます．
この記事では，x64アーキテクチャにおける並列処理の第一歩として，複数のプロセッサを起動する方法と，プロセッサ間通信の方法を説明します．

![concurrent_parallel.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354177/706e1c6c-4a31-6ca8-7734-07a4349b7def.png)

# x64におけるマルチプロセッサ

x64のマルチプロセッサの構成は以下の図の通りです．

* 周辺機器からの割込信号はシステム全体の割込コントローラであるI/O APICに集約されます．
* 割込信号はその後各プロセッサの個別の割込コントローラであるLocal APICに分配されます．
* Local APICがプロセッサの窓口として機能しています．
* Local APICにはLocal APIC IDが付与され，プロセッサ自体もLocal APIC IDで識別します．

Intel® 64 and IA-32 Architectures Software Developer's Manual December 2023 Vol3. 図11-3
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354177/a0304706-929a-5a31-a6d2-b4dd323e534b.png)

### BSPとAP

x64のマルチプロセッサ環境には，APとBSPという2種類のプロセッサが存在します．

* BSP (Bootstrap Processor)
    * 電源ボタンを押して最初に起動するプロセッサ
    * 必ずひとつ存在
    * UEFI環境では/EFI/BOOT/BOOTX64.EFIを実行するのがこのプロセッサ
* AP (Application Processor)
    * BSP以外のプロセッサ
    * 0個以上存在
    * 他のプロセッサから起動指示を受けなければ，停止したまま

![bsp_ap.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354177/918416c0-99da-6287-d6a3-1163ca837436.png)

# HeliOSにおけるAP起動手順

x64におけるマルチプロセッサの構造がだいたいつかめたところで，HeliOSにおけるAP起動の流れを見ましょう．

![helios_multiprocessor.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354177/bd4fa37d-4fc8-bd59-2ded-d8427745ac54.png)

### BSPが全プロセッサのLocal APIC IDを列挙

まずBSPはACPI description tableのひとつであるMADT（Multiple APIC Description Table）の中からProcessor Local APIC Structureという構造体を洗い出し，そのLocal APIC IDを列挙します．
HeliOSにおけるMADTのソースコードは[こちら](https://github.com/TaiseiIto/HeliOS/blob/main/kernel/src/acpi/multiple_apic_description.rs)

![list_processors.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354177/ea02c383-473f-6add-1271-a15de8db59a9.png)

Processor Local APIC Structureは以下の表のような構造になっています．
HeliOSにおけるProcessor Local APIC Structureのソースコードは[こちら](https://github.com/TaiseiIto/HeliOS/blob/main/kernel/src/acpi/multiple_apic_description/processor_local_apic.rs)

Advanced Configuration and Power Interface (ACPI) Specification Release 6.5 表5.22
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354177/c455bccb-9b32-5595-915a-d6d9493baa2c.png)

Flagsの中のEnabledというフラグは，そのプロセッサが使用可能かどうかを示しているので，このフラグも確認しておきましょう．

Advanced Configuration and Power Interface (ACPI) Specification Release 6.5 表5.23
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354177/e2a29de1-e4a0-4c85-fac3-24a3d29f9965.png)

HeliOSの動作確認に使用しているGPD MicroPCの場合，この手順によりLocal APIC ID 0,2,4,6が検出されました．

### BSPが自分のLocal APIC IDを確認

プロセッサが自分自身のLocal APIC IDを確認する方法は以下の通りです．
まずはRDMSR命令でIA32_APIC_BASEを取得します．
HeliOSにおけるIA32_APIC_BASEのソースコードは[こちら](https://github.com/TaiseiIto/HeliOS/blob/main/kernel/src/x64/msr/ia32/apic_base.rs)

Intel® 64 and IA-32 Architectures Software Developer's Manual December 2023 Vol4. 表2-2
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354177/fbe02a33-5f56-11b0-7560-e4cc7a60af46.png)

APIC Baseには大抵の場合0xfee00が入っていると思います．
これがLocal APICのアドレスになっていて，以下の表のように様々なレジスタが配置されています．

Intel® 64 and IA-32 Architectures Software Developer's Manual December 2023 Vol3. 表11-1
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354177/4018ee73-3afb-c1cc-b373-e99790abcacc.png)

このテーブルのオフセット0x20，上の表でいえばアドレス0xfee00020に，Local APIC ID Registerがあります．
HeliOSにおけるLocal APIC ID Registerのソースコードは[こちら](https://github.com/TaiseiIto/HeliOS/blob/main/kernel/src/interrupt/apic/local/local_apic_id.rs)

Intel® 64 and IA-32 Architectures Software Developer's Manual December 2023 Vol3. 表11-6
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354177/013039b4-755a-5d4a-5ee9-96ac2fefd401.png)

HeliOSの場合BSPのLocal APIC IDは0だったので，

* BSPのLocal APIC IDは0
* APのLocal APIC IDは2,4,6

ということになります．

### BSPがAPを起動

Local APIC Registerのオフセット0x300にあるICR（Interrupt Command Register）から，他のプロセッサに信号を送ることができます．
HeliOSにおけるICRのソースコードは[こちら](https://github.com/TaiseiIto/HeliOS/blob/main/kernel/src/interrupt/apic/local/interrupt_command.rs)

Intel® 64 and IA-32 Architectures Software Developer's Manual December 2023 Vol3. 表11-12
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354177/d16fc639-1785-be86-540c-1e93b0a5b6d6.png)

BSPからICRを通して起動させたいAPに向けてINIT-SIPI-SIPIという順番で信号を送ると，APが起動します．
INIT信号は，プロセッサを初期化させる信号で，Delivery ModeにINITを指定し，Destination Fieldに送信先のLocal APIC IDを指定します．
SIPI信号は，プロセッサに実行を開始させる信号で，Delivery ModeにStart Upを指定し，Destination Fieldに送信先のLocal APIC IDを指定し，Vectorに実行開始アドレスを0x1000で割った値を指定します．

INIT-SIPI-SIPI信号を送る具体的な手順を以下に示します．

* INIT信号を開始する．（Level=Assert）
* 100マイクロ秒待つ．
* INIT信号を停止する．（Level=De-assert）
* 10ミリ秒待つ．
* 1回目のSIPI信号を送る．
* 200マイクロ秒待つ．
* 2回目のSIPI信号を送る．

HeliOSでは上の手順における時間の測定にHPETを用いています．
HeliOSにおけるHPETのソースコードは[こちら](https://github.com/TaiseiIto/HeliOS/blob/main/kernel/src/timer/hpet.rs)

![hpet.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354177/857b40e4-a105-5c10-9463-057326de3cf8.png)

General Configuration Registerの中にカウンタのスイッチとなるフラグがあるので，そのフラグを立てます．
するとMain Counter Value Registerの値がGeneral Capabilities and ID Registerに記載された周期に従ってインクリメントするので，2時点間のMain Counter Value Registerの差分に周期を掛け算してやれば，経過時間を求めることができます．

### APの起動

HeliOSでは，物理アドレス0x1000以上0x10000未満をAPの起動に利用することにしました．
BSPはAPを起動する前にAPに実行させる命令列boot_loader.binを物理アドレス0x1000を起点に書いておきます．
APの実行開始アドレスは物理アドレス0x1000です．
APのスタックの底は物理アドレス0x10000です．
HeliOSにおけるboot_loader.binのソースコードは[こちら](https://github.com/TaiseiIto/HeliOS/blob/main/processor/boot/main.s)

![processor_boot_loader.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354177/cb0f3e3d-86f1-fff9-95e3-20e1fc42da78.png)

全APが同じ領域をスタックとして使用することになっているので，複数のAPが同時にboot_loader.binを実行してはいけないことに注意が必要です．
これはBSPがAPの起動完了の通知を受け取ってから次のAPの起動に進んでいる理由でもあります．

### APが16ビットモードから32ビットモードへ移行

起動直後のAPは16ビットモードです．
APはまず以下の手順に従って16ビットモードから32ビットモードへ移行します．

* 仮のGDTを設定する．
* 一時的にページングを無効化する．
* 32ビットプロテクトモードを有効化する．
* 32ビットコードセグメントにジャンプする．

```
	# Move to 32bit protected mode.
	lgdt	gdtr
	movl	%cr0,	%edx
	andl	$0x7fffffff,	%edx	# Disable paging,
	orl	$0x00000001,	%edx	# Enable 32bit protected mode.
	movl	%edx,	%cr0
	ljmp	$0x0008,	$main32
```

仮のGDTはこんな感じです．

```
gdt_start:
	# [Intel 64 and IA-32 Architectures Software Developer's Manual December 2023](https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html) Vol.3A 3.4.5 Segment Descriptors, Figure 3-8. Segment Descriptor
segment_descriptor_null:			# 0x00
	.word	0x0000	# Limit 15:00
	.word	0x0000	# Base 15:00
	.byte	0x00	# Base 23:16
	.byte	0x00	# Type, S, DPL, P
	.byte	0x00	# Limit 19:16, AVL, L, D/B, G
	.byte	0x00	# Base 31:24
segment_descriptor_32bit_code:			# 0x08
	.word	0xffff	# Limit 15:00
	.word	0x0000	# Base 15:00
	.byte	0x00	# Base 23:16
	.byte	0x9a	# Type, S, DPL, P
	.byte	0xcf	# Limit 19:16, AVL, L, D/B, G
	.byte	0x00	# Base 31:24
segment_descriptor_32bit_data:			#0x10
	.word	0xffff	# Limit 15:00
	.word	0x0000	# Base 15:00
	.byte	0x00	# Base 23:16
	.byte	0x92	# Type, S, DPL, P
	.byte	0xcf	# Limit 19:16, AVL, L, D/B, G
	.byte	0x00	# Base 31:24
segment_descriptor_64bit_kernel_code:		# 0x18
	.word	0xffff	# Limit 15:00
	.word	0x0000	# Base 15:00
	.byte	0x00	# Base 23:16
	.byte	0x9a	# Type, S, DPL, P
	.byte	0xaf	# Limit 19:16, AVL, L, D/B, G
	.byte	0x00	# Base 31:24
segment_descriptor_64bit_kernel_data:		# 0x20
	.word	0xffff	# Limit 15:00
	.word	0x0000	# Base 15:00
	.byte	0x00	# Base 23:16
	.byte	0x92	# Type, S, DPL, P
	.byte	0xcf	# Limit 19:16, AVL, L, D/B, G
	.byte	0x00	# Base 31:24
segment_descriptor_64bit_application_data:	# 0x28
	.word	0xffff	# Limit 15:00
	.word	0x0000	# Base 15:00
	.byte	0x00	# Base 23:16
	.byte	0xf2	# Type, S, DPL, P
	.byte	0xcf	# Limit 19:16, AVL, L, D/B, G
	.byte	0x00	# Base 31:24
segment_descriptor_64bit_application_code:	# 0x30
	.word	0xffff	# Limit 15:00
	.word	0x0000	# Base 15:00
	.byte	0x00	# Base 23:16
	.byte	0xfa	# Type, S, DPL, P
	.byte	0xaf	# Limit 19:16, AVL, L, D/B, G
	.byte	0x00	# Base 31:24
gdt_end:
	.align	0x4
	.word	0x0000
gdtr:
	.word	gdt_end - gdt_start - 1
	.long	gdt_start
```

### APが32ビットモードから64ビットモードへ移行

続いて，APは以下の手順に従って32ビットモードから64ビットモードへ移行します．

* BSPが用意したAP用のPML4 tableを自身のCR3に設定する．
* 32ビットを超える物理アドレスを使えるようにするため，CR4のPAEフラグを立てる．
* 64ビットモードを有効化するため，IA32_EFERのLMEフラグを立てる．
* 実行不可フラグNXを有効化するため，IA32_EFERのNXEフラグを立てる．
* ページングを有効化するため，CR0のPGフラグを立てる．
* 64ビットコードセグメントにジャンプする．

```
	# Set temporary CR3.
	movl	boot_argument_cr3,	%edx
	andl	$0x00000fff,	%edx
	orl	$temporary_pml4_table,	%edx
	movl	%edx,	%cr3
	# Set PAE.
	movl	%cr4,	%edx
	orl	$0x00000020,	%edx
	movl	%edx,	%cr4
	# Set LME and NXE.
	movl	$0xc0000080,	%ecx
	rdmsr
	orl	$0x00000900,	%eax
	wrmsr
	# Set PG.
	movl	%cr0,	%edx
	orl	$0x80000000,	%edx
	mov	%edx,	%cr0
	# Move to 64bit mode.
	ljmp	$0x0018,	$main64
```

### APがブートローダからカーネルへ移行

続いて，APは今までのアセンブリで書かれたブートローダから，Rustで書かれたカーネルへ実行を移します．
APを起動する前に，BSPがあらかじめ自身のPML4 tableから各AP用のPML4 tableを複製，編集し，下の図のような仮想メモリ空間をあらかじめ準備しておきます．

![multiprocessor_memory_map.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354177/7a692c23-d453-41b5-db48-2bb7fb3935f1.png)

複数のプロセッサが同じ領域を使用しているように見えますが，プロセッサごとに個別の仮想メモリ空間を用意しているので，仮想メモリ空間上ではアドレスが被ってしまっているように見えても，物理メモリ空間上ではちゃんと領域が衝突しないようになっています．
また，書き換え不可領域はプロセッサ間で共有可能なので，物理メモリ空間上でひとつだけ用意して，それを全AP間で共有しています．
APはBSPが指定したPML4 tableのアドレスをCR3に設定し，スタックポインタRSPを0にし，ELFのエントリポイントにジャンプすれば，カーネルに実行を移すことができます．
ここまで行けばAPはアセンブリ製のコードとはおさらばしてRustで書かれたコードを実行することになるので，かなり見通しが良くなります．

# プロセッサ間通信

プロセッサ間通信は，APを起動するINIT-SIPI-SIPIと同様に，Local APIC RegisterのICR（Interrupt Command Register）を使用します．
送信側プロセッサがICRに書き込みを行うと，受信側プロセッサで割込が発生する仕組みです．

Intel® 64 and IA-32 Architectures Software Developer's Manual December 2023 Vol3. 表11-12
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354177/d16fc639-1785-be86-540c-1e93b0a5b6d6.png)

* Delivery ModeにはFixedを指定します．
* Destination Fieldには受信側プロセッサのLocal APIC IDを指定します．
* Vectorに割り込み番号を指定します．

ただし，割り込みを発生させるだけでは情報のやり取りができないので，送信側があらかじめ用意されていたメッセージ領域にメッセージを書き込み，受信側の割込を引き起こし，受信側がメッセージを読み込むことで情報をやり取りします．
HeliOSにおけるBSP側のメッセージのソースコードは[こちら](https://github.com/TaiseiIto/HeliOS/blob/main/kernel/src/processor/message.rs)
HeliOSにおけるAP側のメッセージのソースコードは[こちら](https://github.com/TaiseiIto/HeliOS/blob/main/processor/kernel/src/processor/message.rs)

![interprocessor_message.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2354177/1b390ff3-b560-72c0-63a0-397b6ff26e2a.png)

また，メッセージ領域は送信側プロセッサが書き込み，受信側プロセッサが読み込むので，排他制御を行う必要があります．
Rustによる排他制御は，「詳細 Rustアトミック操作とロック」（ISBN 9784814400515）あたりで勉強するのがおすすめです．
HeliOSにおけるBSP側の排他制御のソースコードは[こちら](https://github.com/TaiseiIto/HeliOS/blob/main/kernel/src/sync/spin.rs)
HeliOSにおけるAP側の排他制御のソースコードは[こちら](https://github.com/TaiseiIto/HeliOS/blob/main/processor/kernel/src/sync/spin.rs)

# まとめ

x64マルチプロセッサ環境で動く自作OSで，複数のプロセッサを起動させる方法について解説しました．

* マルチプロセッサ環境においても，最初に起動するプロセッサはBSPのみで，BSPがその他のプロセッサであるAPを起動する必要があります．
* ACPI description tableのひとつであるMADT（Multiple APIC Description Table）に，プロセッサの一覧が記載されています．
* 自身のLocal APIC IDは，Local APIC RegisterのLocal APIC ID Registerから取得できます．
* BSPからINIT-SIPI-SIPI信号をAPに送信すると，APが起動します．
* APは16ビットモードで起動するので，そこから32ビットモードに移行し，さらに64ビットモードに移行します．
* プロセッサ間通信は，送信側プロセッサがICR（Interrupt Command Register）を通して受信側の割込を引き起こすことで実現します．

# 参考文献

* [３０日でできる！OS自作入門](https://book.mynavi.jp/ec/products/detail/id=22078)
* [ゼロからのOS自作入門](https://book.mynavi.jp/ec/products/detail/id=121220)
* [Intel® 64 and IA-32 Architectures Software Developer's Manual December 2023](https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html)
* [Advanced Configuration and Power Interface (ACPI) Specification Release 6.5](https://uefi.org/sites/default/files/resources/ACPI_Spec_6_5_Aug29.pdf)
* [IA-PC HPET (High Precision Event Timers) Specification](https://access.redhat.com/sites/default/files/attachments/564464_hpet1.pdf)
* [マルチコアプロセッサ対応 - OS自作情報](https://soft.taprix.org/code/os/multicore.html)
* [詳細 Rustアトミック操作とロック](https://www.oreilly.co.jp/books/9784814400515/)