# KVM: Linux 虛擬化基礎建設
> 貢獻者: RinHizakura, ray90514, jserv

## 用詞

virtual machine 應翻譯為「虛擬機器」，而非簡略的「虛擬機」，用來區分 motor/engine (發動機) 在漢語常見的翻譯詞「機」。

## 虛擬化概況
> 簡報:〈[Embedded Virtualization applied in Mobile Devices](https://www.slideshare.net/jserv/mobile-virtualization)〉

> 出處: [Xen Directions](http://www-archive.xenproject.org/files/xensummit_germany09/IanPratt.pdf), 2009

> 出處: [Overview of Xen for ARM Servers](https://www.slideshare.net/linaroorg/lcu14-308-xen-project-for-arm-servers)

:::warning
Xen problem:
support for running as Host (Dom0) or Guest (DomU) was out-of-tree
:::

2017 年第四季，AWS 支援 KVM 作為虛擬化架構，自此 KVM 可說是席捲 Linux 虛擬化技術生態。在 AWS 啟動的 2006 年，Xen 是當時最成熟、開放原始碼的 Linux 虛擬化引擎技術。因此，AWS 在早期採用 Xen，成為其 [EC2](https://aws.amazon.com/ec2/) 的底層基礎。

KVM 全名是 Kernel-based Virtual Machine，最早是以色列新創公司 [Qumranet](https://en.wikipedia.org/wiki/Qumranet) (創立於 2005 年) 發表的開放原始碼專案，在 2006 年下半收錄於 Linux 核心，自此大幅強化 KVM 的影響力。

2008 年，Red Hat 以 1 億 7 百萬美元收購 KVM 背後的 Qumranet 公司，藉此擴展 Red Hat 對於虛擬技術的支援。得益於 KVM 的活躍發展，2011 年啟動的 Google Cloud 從一開始就採用 KVM 引擎。Qumranet 核心人物 Avi Kivity 在公司成功賣給 Red Hat 後，沒閒著，後來開創新一代的分散式資料庫技術公司 [ScyllaDB](https://www.scylladb.com/)。

世界上前幾大的資訊科技公司不約而同，選擇在以色列設立研發中心，且成果卓著，例如，Intel x86 家族中為人所知的 CPU 微架構: Sandy Bridge 和 Ivy Bridge 都由 Intel 以色列的研發中心研發，藍色巨人 IBM 也早在 1970 年代就在以色列設立龐大的研發中心，成果斐然。

虛擬化技術歷史悠久，早在 1967 年，第一代的硬體虛擬化技術就由 IBM 提出。在大型主機中實作以 CP/CMS 為代表的虛擬化技術，直到 2006 年，Intel 和 AMD 才分別在各自的處理器中加入「有限」的硬體虛擬化特性，分別稱為，Intel VT-x 和 AMD-V。與大型機所採用的專為虛擬化設計的處理器不同，從 PC 起家者以 Intel 為代表的 x86 家族的處理器生來就不是為虛擬化設計。要在 x86 家族處理器上完全向後相容的同時加入硬體虛擬化特性，無疑成為一個挑戰，硬體層面實作較為困難，導致軟體層面的實作複雜度也隨之水漲船高。

Linux 核心中，虛擬化相關程式碼，x86 架構部分的程式碼數量是 S390 架構的 7 倍、PPC 架構的 8 倍、Arm 架構的 4 倍，其複雜度之高從中可見一斑。

Avi Kivity 提出的方案非常清晰且巧妙：聚焦於 Linux 核心，至於 User space 部分交給穩定可靠的 QEMU，採用後者作為其使用者層級的入口，而且 KVM 僅實作 HVM 功能。以 Avi Kivity 為主的工程師僅僅用不到一年時間，就讓 Linux 社群接受 KVM 的設計方案並通過程式碼審查，最終於 2006 年 10 月合併進入 Linux `v2.6.20`。

:::warning
why did KVM succeed?
1. KVM had a better, more flexible, and future-proof design built into Linux, not underneath it
2. reuse things already there that suited Linux more and left it in control which obviously is in the interest of Linux developers
:::
> 註: underneath 語意與 under 相近，但更強烈

[Cloud-Hypervisor](https://github.com/cloud-hypervisor/cloud-hypervisor) 是 Intel 以 KVM 為基礎，開發出來的嶄新 Virtual Machine Monitor (VMM)，這項虛擬化建設著眼於資源配置侷限但又廣泛部署的雲端運算環境，採用 Rust 程式語言打造。Cloud-Hypervisor 由於自身定位，不考慮舊有通行的硬體支援，相反地，主要支援 VirtIO 為基礎的 para-virtualized device。

其他實作:
* [xvisor](https://wiki.csie.ncku.edu.tw/embedded/xvisor)

## Hypervisor 的分類

[Hypervisor](https://en.wikipedia.org/wiki/Hypervisor) 是作業系統與硬體之間的中間層，這允許多個作業系統可以作為獨立的 virtual machine(VM)，運行於一個實體的電腦之上。Hypervisor 則管理硬體資源使這些 VM 可以共享之。它會在邏輯上將 VM 彼此分開，然後為每個 VM 指派本身的一部分基礎運算處理能力、記憶體和儲存容量，防止 VM 之間相互干擾。

Hypervisor 可以分為兩大類型，其一是 type-1 hypervisor，其直接運行在硬體之上，如下圖是比較經典的設計。它的優點是效率很高，因為可以直接存取硬體。這也增加了安全和穩定性，因為 type-1 hypervisor 和 CPU 之間不存在額外的作業系統層，因此較為單純而不容易被介入。

Type-2 hypervisor 則不直接在硬體上執行，而是作為應用程式執行在主作業系統(host)環境上執行，如下圖所展示的。因為 type-2 hypervisor 必須透過 host作業系統存取資源，因而會引發延遲問題而相對 type-1 效能較差。

> [Using Linux as Hypervisor with KVM](https://indico.cern.ch/event/39755/attachments/797208/1092716/slides.pdf)

## QEMU

QEMU 本身也是為一個 hypervisor，不過其主要都是用軟體去模擬指令的執行、一些 device 的 IO，並沒有使用 Hardware-assisted virtualization，因此執行速度相較緩慢。然而他的好處是擴充性高，使用者只需要使用 Qemu 提供的 API，就能迅速模擬出一個 device 讓 guest OS 做存取，

QEMU 使用的軟體模擬技術為 DBT (Dynamic Binary Translation)，QEMU 本身實作出的工具稱作 TCG (Tiny Code Generator)
DBT 的輸入為要模擬的一整塊 basic block 的指令，且指令可以是 hypervisor 本身所支援的指令集；輸出為 host 本身的指令集的指令。

TCG 會在輸入與輸出中間加上一層 IR，亦即 input $\to$ IR $\to$ output，這樣可以減去指令轉換的成本
QEMU-KVM 結合 KVM 以及 QEMU 的優點，首先 KVM 已處理 memory mapping 及 instruction emulation，之後由 QEMU 來提供硬體 I/O 虛擬化，並透過 ioctl() /dev/kvm 裝置和 KVM 互動。

而 QEMU-KVM 相比原生 QEMU 的改動：
* 原生的 QEMU 藉由 DBT 實作 CPU 的 full-virtualization，但修改後的 QEMU-KVM 會呼叫 ioctl() 來運用 KVM 模組
* 原本的 QEMU 是單執行緒，QEMU-KVM 採多執行緒

## KVM

[KVM](https://en.wikipedia.org/wiki/Kernel-based_Virtual_Machine) 是個 Linux 核心模組/子系統，可將 Linux 轉為 type-2 hypervisor，結合硬體的虛擬化支援，使得 host machine 上可以執行多個獨立的虛擬環境，稱為 guest 或者 virtual machine。由於 KVM 直接提供 CPU 和記憶體的虛擬化，guest os 的 CPU 指令不需要額外經過軟體的 decode，而是直接交給硬體進行處理，因此可以有效的提高運行速度。而結合軟體(例如 KVM 搭配 QEMU)模擬 CPU 和記憶體以外的裝置之後，guest OS 便可以被完整的支援在 host OS 上載入並良好的運行。

KVM 提供的功能有：
* 支援 CPU 和 memory Overcommit
Overcommit 代表可以要求超過實際可以 handle 的 memory，實際上在使用到才會為其分配 physical memory
* 支援半虛擬化 I/O (virtio)
* 支援熱插拔 (cpu, block device, network device 等)
* 支援對稱多處理 (Symmetric Multi-Processing，縮寫爲 SMP)
* 支援 Live Migration
* 支援 PCI device 直接分配和單根 I/O 虛擬化 (SR-IOV)
SR-IOV - single-root IO virtualization
* 支援 KSM (kernel samepage merging)
* 支援 NUMA

對於 Linux KVM 相關 API 的基本操作，以下是有助於入門的材料:
* [sysprog21/kvm-host](https://github.com/sysprog21/kvm-host)
* [Using the KVM API](https://lwn.net/Articles/658511/)

### 範例

> [KVM API Documentation](https://www.kernel.org/doc/Documentation/virtual/kvm/api.txt)

[sysprog21/kvm-host](https://github.com/sysprog21/kvm-host) 展示一個使用 Linux 的 kernel-based virtual machine，達成可載入 Linux 核心的系統級虛擬機器 (system virtual machine)的極小化實作。雖然目前的實作只能部份的啟動 Linux，但精簡的程式碼很適合作為入門 Linux KVM 相關 API 的材料，以下概略的解析程式碼的行為:

#### `vm_init`

KVM for x86 在開啟 `/dev/kvm` 並透過 `KVM_CREATE_VM` 建立之後，初始化時分別需要設定:
1. `KVM_SET_TSS_ADDR`: 定義 3 個 page 的 physical address 範圍以設定 [Task State Segment](https://en.wikipedia.org/wiki/Task_state_segment)
2. `KVM_SET_IDENTITY_MAP_ADDR`: 定義 1 個 page 的 physical address 範圍以設定 identity map (page table)
3. `KVM_CREATE_IRQCHIP`: 建立虛擬的 [PIC](https://en.wikipedia.org/wiki/Programmable_interrupt_controller)
4. `KVM_CREATE_PIT2`: 建立虛擬的 [PIT](https://en.wikipedia.org/wiki/Programmable_interval_timer)
5. `KVM_SET_USER_MEMORY_REGION`: 為 VM 建立記憶體，將 guest physical memory 通過 host OS 的一段在 virtual 連續的空間(在 host 的 physical 不一定連續)來進行模擬
> [KVM MMU Virtualization](https://events.static.linuxfound.org/slides/2011/linuxcon-japan/lcj2011_guangrong.pdf)
6. `KVM_CREATE_VCPU`: 為 VM 建立 CPU

暫存器的部份也需要根據需求進行相應的初始化:
1. `KVM_GET_SREGS` / `KVM_SET_SREGS`: 設定 x86 中的 [segment register](https://en.wikipedia.org/wiki/X86_memory_segmentation)，被用來指定 code / data / stack 等記憶體內容的定址範圍，包含:
* Code Segment (CS): Pointer to the code
* Data Segment (DS): Pointer to the data.
* Extra Segment (ES). Pointer to extra data ('E' stands for 'Extra').
* F Segment (FS): Pointer to more extra data ('F' comes after 'E').
* G Segment (GS): Pointer to still more extra data ('G' comes after 'F').
* Stack Segment (SS). Pointer to the stack.
> 
> [x86 Segmentation for the 15-410 Student](https://www.cs.cmu.edu/~410/doc/segments/segments.html)
> * [x86 Assembly/X86 Architecture](https://en.wikibooks.org/wiki/X86_Assembly/X86_Architecture)
2. 設定 `cr0` 以開啟 protected mode
3. `KVM_GET_REGS` / `KVM_SET_REGS`:
* 設定 `rflags`: bit 1 恆為 1
* 設定 `rip`: `rip` 儲存下個要執行的 CPU 指令，因此需指向核心被擺放的記憶體位置
* 設定 `rsp`: `rsp` 則需設定在 boot paramters 的位置
> When using bzImage, the protected-mode kernel was relocated to 0x100000 (“high memory”), and the kernel real-mode block (boot sector, setup, and stack/heap) was made relocatable to any address between 0x10000 and end of low memory.

最後，需要設虛擬的 CPU(VCPU):
1. `KVM_GET_SUPPORTED_CPUID`: 取得一個 `struct kvm_cpuid2` 的結構單元，準備用來建立 cpuid information
2. 對於 `function` 為 `KVM_CPUID_SIGNATURE` 的 entry 進行設定
* [KVM CPUID bits](https://www.kernel.org/doc/html/latest/virt/kvm/cpuid.html)
3. 最後使用 `KVM_SET_CPUID2` 將 entry 設定回 KVM 之中

struct kvm_cpuid_entry {
	__u32 function;
	__u32 eax;
	__u32 ebx;
	__u32 ecx;
	__u32 edx;
	__u32 padding;
};

struct kvm_cpuid2 {
	__u32 nent;
	__u32 padding;
	struct kvm_cpuid_entry2 entries[0];
};

#### `vm_load_image` / `vm_load_initrd`

要載入 bzImage / initrd 到模擬的記憶體中，我們需要先對 Linux 開機流程的 memory map 有足夠的認識，以及 bzImage / initrd 應該放在相應的哪個位置 (在此範例程式之中，`X == 0x10000`):

Reg   PhysAddr                            Binary image
              |  Protected-mode kernel |
RIP   100000  +------------------------+  bzImage [+ (setup_sects + 1) * 512]
              |  I/O memory hole       |
      0A0000  +------------------------+
              |  Reserved for BIOS     |      
              ~                        ~
              |  Command line          |      
      X+10000 +------------------------+      
              |  Stack/heap            |      
      X+08000 +------------------------+
              |  Kernel setup          |      
              |  Kernel boot sector    |      
RSI   X       +------------------------+  bzImage [+ 0]
              |  Boot loader           |     
      001000  +------------------------+      
              |  Reserved for MBR/BIOS |
      000800  +------------------------+
              |  Typically used by MBR |
      000600  +------------------------+
              |  BIOS use only         |
      000000  +------------------------+
     
... where the address X is as low as the design of the boot loader permits.

`vm_load_image` 所做即為設定一些必要的 `boot_params` 後，按照此 memory map 將 bzImage 載入到相對應的位置。此外，還需要設定 e820 table 以確保 initrd 所在位址是可以被合法使用的。需要設定哪些 memory address 可以為 OS 所用，而哪些要留給 bios / memory-mapped device 等:
* 設定兩個 `struct boot_e820_entry`，type 皆為 `E820_RAM` 表示 availible，簡單的把 `ISA_START_ADDRESS` 到 `ISA_END_ADDRESS` 以外的位置都設定成可用

`vm_load_initrd` 則載入 initrd。`boot_params` 的 `initrd_addr_max` 會記錄 initrd 會允許載入的最高位置，我們可以根據 `initrd_addr_max`、initrd 本身的大小、以及我們所模擬的 VM 擁有的記憶體大小來找到合適的載入位置。
* 並通過設定 `ramdisk_image` 和 `ramdisk_size` 使 booting 可以正確運作

#### `vm_run`

在進行必要的設定並且載入 image 後，就可以透過 `KVM_RUN` ioctl 來執行 guest virtual cpu 了。關於指令的 decode、execute、和對記憶體的存取操作將會在 KVM 中進行，我們所設計的虛擬機器不需要實作相關的模擬。我們只需要處理會使得 `KVM_RUN` ioctl 返回的特殊事件(大部分是 I/O 設備操作的模擬)。

## Linux 核心啟動流程

> [The Linux/x86 Boot Protocol](https://www.kernel.org/doc/html/latest/x86/boot.html)

相傳在十八世紀，德國 Baron Münchhausen 男爵常誇大吹噓自己的英勇事蹟，其中一項是「拉著自己的頭髮，將自己從受陷的沼澤中提起」，此事後來收錄於德國《吹牛大王歷險記》，則改寫為「用拔靴帶把自己從海中拉起來」，這裡的「拔靴帶」(bootstrap) 指的是長統靴靴筒頂端後方的小環帶，是用以輔助穿長統靴。這種有違物理原理的誇大動作，卻讓不同領域的人們獲得靈感，Robert A. Heinlein 發表於 1941 年的短文〈[By His Bootstraps](https://en.wikipedia.org/wiki/By_His_Bootstraps)〉收錄典故並給予多種延伸想法；滑鼠發明人 Doug Engelbart 博士甚至在 1989 年以此命名其研究機構「Bootstrap 學院」，並擔任該院主任。在商業上，bootstrapping 則被引申為一種創業模式，也就是初期投入少量的啟動資本，然後在創業過程中主要依靠從客戶得來的銷售收入，形成一個良好的正現金流。在電腦資訊領域，因為開機過程是環環相扣，先透過簡單的程式讀入記憶體，執行後又載入更多磁區、程式碼來執行，直到作業系統完全載入為止，所以開機過程也被稱為 bootstrapping，簡稱 "boot"。
> boot loader 也可很精簡，例如 [afboot-stm32](https://github.com/afaerber/afboot-stm32) 僅用 400 餘行，就能在 STM32 微控制器上載入 Linux 核心
> 延伸閱讀:〈[Qi -- Lightweight Boot Loader Applied in Mobile and Embedded Devices](https://www.slideshare.net/jserv/qi-lightweight-boot-loader-applied-in-mobile-and-embedded-devices)〉

要讓 kvm-host 可以啟動 Linux 並開啟與使用者互動的介面，涉及了幾個關鍵的設施。

### bzImage

引用自 [vmlinux](https://en.wikipedia.org/wiki/Vmlinux)：
> As the Linux kernel matured, the size of the kernels generated by users grew beyond the limits imposed by some architectures, where the space available to store the compressed kernel code is limited. The bzImage (big zImage) format was developed to overcome this limitation by splitting the kernel over non-contiguous memory regions

因應 Linux kernel 的大小的日益增加，bzImage 因此被設計以將 kernel 切割成多段不連續的記憶體區塊，而得以分段載入記憶體之中，包含了 object file `bootsect.o` + `setup.o` + `misc.o` + `piggy.o`，其中 `piggy.o` 的 data section 中就放著壓縮後的 vmlinux 檔(編譯出的原始 kernel image)。

### initrd

檔案系統在 UNIX-based 的作業系統具有關鍵的地位。其中，為了讓 kernel 在完成開機後，可以進入 user mode 執行使用者程式，或者新增新的 file system，[root filesystem](https://en.wikipedia.org/wiki/Root_directory) 的存在是必要的。

而 initrd 是 [initial ramdisk](https://en.wikipedia.org/wiki/Initial_ramdisk) 的縮寫，它借用了 RAM 空間建立暫時的 root file system (簡稱 rootfs)。當 Linux 核心載入並執行時，由於 initrd 所在的空間存在檔案系統，且通常會包含 init 等程式，故可用以掛入某些特別的驅動程式，比方說 SCSI，完成階段性目標後，kernel 會將真正的 rootfs 掛載，並執行 /sbin/init 程式。總而言之，initrd 提供「兩階段開機」的支援。

為何需要此等迂迴的開機途徑呢？原因是，rootfs 可能所存在於非本機的外部儲存裝置。另一方面，如果要將所有裝置驅動程式直接編譯到核心中，儲存裝置很可能極難尋找。比方說 SCSI 裝置就需要複雜且耗時的程序，若用 RAID 系統更是需要看配置情況而定，同樣的問題也發生在 USB storage 上，因為 kernel 得花上更長的等待與配置時間，或說遠端掛載 rootfs，不僅得處理網路裝置的問題，甚至還得考慮相關的伺服器認證、通訊往返時間等議題。我們會希望 rootfs 的裝置驅動程式能具有像是 udevd 的工具可以實作自動載入。但是這裡就存在矛盾，udevd 是一個 executable file，因此在 rootfs 被掛載前，是不可能執行 udevd 的，但是如果 udevd 沒有啟動，那就無法自動載入 rootfs 存在裝置的驅動程式了。

initrd 的出現得以解決這個矛盾。第一階段啟動的 initrd 提供了初步啟動 user space 程式的環境，然後其中可以確定最後真正 rootfs 所在裝置究竟為何，因此 initrd 可以把負責啟動該 rootfs 的 driver 載入。最後再掛到真正的 root 去把其他 init 給完成。

更重要的是，我們可在 initrd 放置基礎的工具，一來作為掛載 rootfs 作準備，比方說硬體初始化、解密、解壓縮等等，二來提示使用者或系統管理員目前的狀態，這對於消費性電子產品來說，有很大的意義。

### UART
* [Serial UART information](https://www.lammertbies.nl/comm/info/serial-uart)
* [arch/x86/include/asm/msr-index.h](https://elixir.bootlin.com/linux/latest/source/arch/x86/include/asm/msr-index)
* [include/uapi/linux/serial_reg.h](https://elixir.bootlin.com/linux/latest/source/include/uapi/linux/serial_reg.h)

### KVMTOOL

* [kvmtool/kvm.c](https://github.com/kvmtool/kvmtool/blob/master/kvm.c)
* [hw/serial.c](https://github.com/kvmtool/kvmtool/blob/master/hw/serial.c)

### QEMU
* [qemu-kvm - `kvm_run`](https://github.com/ceph/qemu-kvm/blob/master/kvm/libkvm/libkvm.c#L934)
* [qemu-kvm - QEMU 16550A UART emulation](https://github.com/ceph/qemu-kvm/blob/master/hw/serial.c)

## Virtio

Virtio 是 IO 請求溝通的標準，架構如下圖所示，有一個前端和後端，前端通常作為驅動存在被 Guest OS 使用，後端則是在 Guest OS 被視為裝置的一種，後端可以是軟體模擬出來的裝置也可以是支援 Virtio 的實體裝置。

以 Hypervisor 實作的後端來說，前端將 IO 請求傳給後端，後端會將請求傳給實際的裝置，等 IO 處理完成後傳回給前端，後端的這過程也就是裝置的模擬。前後端使用 Virtqueue 作為資料交換的機制

對於前述 kvm 對 io 的處理流程，Virtio 的機制使得模式切換的次數減少，以及若 Virtqueue 用共享記憶體實作，則可以減少資料複製的開銷，提升虛擬化下 IO 的效能。

一個 Virtio 裝置包含以下幾個部分
- Device status field
- Feature bits
- Notifications
- Device Configuration space
- One or more virtqueues

### Device Status Field

用來指示裝置的狀態，通常由驅動寫入，在初始化階段使用

ACKNOWLEDGE (1)
DRIVER (2)
FAILED (128)
FEATURES_OK (8)
DRIVER_OK (4)
DEVICE_NEEDS_RESET (64)

### Feature Bits

用來指示裝置所支援的特性
> 0 to 23 Feature bits for the specific device type
24 to 37 Feature bits reserved for extensions to the queue and feature negotiation mechanisms
38 and above Feature bits reserved for future extensions.

### Notification

通知包含以下三種，第一種是配置改變時由裝置發起的通知，後兩種與 Virtqueue 相關。
通知的實作為 transport specific ，對於 Virtio-pci 驅動到裝置的通知由寫入特定的記憶體區域觸發 vm-exit 完成，裝置到驅動的通知則由 interrupt 完成
- configuration change notification
- available buffer notification
- used buffer notification

### Device Configuration Space

Virtio 支援三種 Bus 來探查及初始化 Virtio 裝置， PCI, MMIO, Channel I/O ，裝置會有根據 bus 定義的配置空間，其中包含上述所提到的 Feature bits 和 Device Status Field。
Virtio-pci 也就是基於 PCI 實作的 Virtio

### Virtqueues

裝置和驅動共享的資料結構，用於驅動與裝置 IO 請求的溝通
目前 Virtio 1.1 有以下兩種 Virtqueue ，目前實作的是 Packed Virtqueues
- Split Virtqueues
- Packed Virtqueues

### Device Initialization

通常會依照以下步驟初始化裝置
1. 重設裝置
2. Guest OS 探查到裝置後會設定　`ACNOWLEDGE (1)`
3. 確立裝置的驅動後設定 `DRIVER (2)`
4. 讀取裝置的 Feature bits ，根據驅動所能提供的特性寫入一個裝置 Feature 的 subset
5. 設定 `FEATURES_OK (8)` ，裝置在此之後不再接受 Feature
6. 讀取裝置的狀態，若仍是 `FEATURES_OK (8)` 代表 Feature 協商成功，若不是則裝置不可用
7. 執行特定於裝置的初始化
8. 一切正常就設定 `DRIVER_OK (4)` 否則設定 `FAILED (128)`

若裝置運作的過程遇到錯誤，會主動設定 `DEVICE_NEEDS_RESET (64)`

### Virtio-blk

Virtio-blk 也就是支援 Virtio 的 block device ，我們要引入的 Virtio-blk 建構於 Virtio-pci 之上

## Packed Virtqueues

Split Virtqueues 的結構如下圖，驅動要發起 IO 請求會將 descriptors 填入 Descriptor Table
完成後會將 descriptors 的位置寫入 Avail Ring ，然後向裝置發起 vailable buffer notification
裝置收到通知後，會根據 Avail Ring 找出對應的 descriptors，然後依照 buffer 內容處理 IO 請求，完成後會寫入 Used Ring 及向驅動發起 used buffer notification


Packed Virtqueues 是 Virtio 1.1 提出的新的 Virtqueue 結構
基本概念與 Split Virtqueues 相似，只是將 Descriptor Table 、 Avail Ring 、 Used Ring 合併為一個 Descriptor Ring ，以有效利用 Cache。
除此之外，原本的 Device Area 與 Driver Area 變為由 Device Event Suppression 和 Driver Event Suppression 來使用， Event Suppression 用來讓裝置或驅動抑制對方的通知
這三個 Area 都位於 Guest OS 的 physical memory 上


Descriptor 結構體如下

struct pvirtq_desc {
    /* Element Address. */
    le64 addr;
    /* Element Length. */
    le32 len;
    /* Buffer ID. */
    le16 id;
    /* The flags depending on descriptor type. */
    le16 flags;
};

每一個 IO 請求關聯一個 Buffer ，每一個 Buffer 可以由多段連續的記憶體組成，每一段為一個 Element ，由一個 Descriptor 表示，每次發起通知可以有多組 Buffer

::: warning
在 Specification ， "buffer" 有時是指一段連續的記憶體也就是 element，有時是指多個 element 組合後的整體， "request" 則是指發起一次通知
:::

裝置及其驅動程式內部會各自維護一個值為 1 或 0 的 wrap counter ，初始值為 1 ， wrap counter 設計使得要從頭存取時，不會存取到該次通知已經存取過的。

write flag 的作用是標示該段記憶體是 write-only 還是 read-only
indirect flag 標示該 descriptor 指向的是一個 descriptor table ，需要協商 Feature VIRTQ_DESC_F_INDIRECT
裝置接收 avail buffer 的流程如下
- 收到 avail buffer notification
- 接續上一次讀取的位置，讀取 descriptor
- 若 flags 的 avail 與裝置 wrap counter 相同且 used 與裝置 wrap counter 相反則該 descriptor avail
- 若 flags 的 next 被設定，則 buffer 由多個 element 組成，繼續讀取下一個 descriptor ，直到 next 被設定為 0 就是 buffer 的最後一個
- 若讀入的是 Decriptor Ring 最後一個，則將 wrap counter 反轉，然後從頭讀入
- 處理完 IO 請求後寫入 used descriptor ，其 used flag 設定為與 wrap counter 相同
- 若有 used buffer 可以發起 used buffer notification

裝置讀取 buffer 依照驅動寫入的順序，若有多個請求則依照請求完成的順序寫入 Descriptor Ring
同一次通知內的請求，第一個 buffer 的 used flag 要最後寫入
若 buffer 由多個 element 組成，則只需寫入第一個 descriptor

## PCI

因為要實作 Virtio-pci ，我們得先了解 PCI ，參考 [PCI](https://wiki.osdev.org/PCI)

一個 PCI 架構如下， Host bridge 負責連接 CPU 和管理所有的 PCI 裝置及 Bus ，裝置又分為一般裝置和 Bridge ， Bridge 用來連接兩個 Bus

一個 PCI 邏輯裝置提供 256 bytes 的 Configuration Space ，用以完成裝置的設定與初始化， CPU 不能直接存取這個空間，需要透過 PCI 的 Host Bridge 提供特殊的機制，讓 CPU 完成配置空間的存取
這個機制藉由 CF8 、 CFC 這兩個 IO Port，先是在 CF8 寫入要存取的配置空間暫存器的位址，然後寫入或讀出 CFC 就可以完成對該暫存器的操作

Bus Number 搭配 Device Number 可以用來識別實際上的 PCI 裝置，每個裝置可以提供不同的功能，每個功能被視為一個邏輯裝置，用 Bus Number : Device Number : Function Number 來分辨每一個邏輯裝置
256 bytes 的配置空間由 64 個 32 bits 的暫存器組成，以 Register Offset 來決定

PCI 配置空間的前 64 bytes 是每個裝置共通的，而剩下的 128 bytes 則由裝置各自定義，共通的部份如下圖所示
* Vendor ID: 識別製造商的 ID， Virtio 為 0x1AF4
* Device ID: 裝置的 ID， 對於 Virtio-blk 是 0x1042
* Command: 用於操作裝置的設定，可寫
* Status: 裝置的狀態
* Class Code: 裝置的種類
* Base Address Register (BAR): 裝置內部空間所映射到的位址，可寫


BAR 的組成如下， Base Address 是裝置內部的記憶體映射到 CPU 定址空間的起始位址，在裝置初始化階段由 Driver 寫入，最低位址是空間的種類，Type 指示位址長度為 32 bits 或 64 bits
Base Address 對齊裝置內部空間的大小，根據這個大小低位不可寫


自定義的部份由 Capability List 組成， Status 的 Bit 4 會告知該裝置有沒有 Capability List ， Capability List​開頭的位址固定在 0x34
每一個 Capability 的第一個 Byte 為 規定好的 ID ，第二個 Byte 為下一個 Capability 的開頭位址，接下來是 Capability 的內容


## Virtio-pci

Virtio-pci 的 Capibility 定義如下，每一個 cap 對應裝置的一種配置空間。該空間在 Guest OS 映射的開頭位址可由 `base_address_reg[cap.bar] + cap.offset` 得知

struct virtio_pci_cap {
    u8 cap_vndr; /* Generic PCI field: PCI_CAP_ID_VNDR */
    u8 cap_next; /* Generic PCI field: next ptr. */
    u8 cap_len; /* Generic PCI field: capability length */
    u8 cfg_type; /* Identifies the structure. */
    u8 bar; /* Where to find it. */
    u8 padding[3]; /* Pad to full dword. */
    le32 offset; /* Offset within bar. */
    le32 length; /* Length of the structure, in bytes. */
};

`cfg_type` 為 cap 的種類

/* Common configuration */
#define VIRTIO_PCI_CAP_COMMON_CFG 1
/* Notifications */
#define VIRTIO_PCI_CAP_NOTIFY_CFG 2
/* ISR Status */
#define VIRTIO_PCI_CAP_ISR_CFG 3
/* Device specific configuration */
#define VIRTIO_PCI_CAP_DEVICE_CFG 4
/* PCI configuration access */
#define VIRTIO_PCI_CAP_PCI_CFG 5

Common configuration 的結構如下
完整的 Feature bits 是 64 bits ，目前實作的 Feature 為 `VIRTIO_F_VERSION_1(32)` 和 `VIRTIO_F_RING_PACKED(34)`
- `feature_select` 用來選擇呈現的 Feature 是高 32 位還是低 32位
- `device_status` 為前述之 Device Status Field
- `num_queues` 為 Virtqueue 的數量
- `queue_select` 寫入後，存取帶有 `queue_` 的欄位會存取對應的 queue 的資訊，若`queue_select` 無效則 `queue_size` 必須為 0
- `queue_desc` Descriptor Area 在 Guest OS 的位址
- `queue_driver` Driver Area 在 Guest OS 的位址
- `queue_device` Device Area 在 Guest OS 的位址

struct virtio_pci_common_cfg {
    /* About the whole device. */
    le32 device_feature_select; /* read-write */
    le32 device_feature; /* read-only for driver */
    le32 driver_feature_select; /* read-write */
    le32 driver_feature; /* read-write */
    le16 msix_config; /* read-write */
    le16 num_queues; /* read-only for driver */
    u8 device_status; /* read-write */
    u8 config_generation; /* read-only for driver */
    /* About a specific virtqueue. */
    le16 queue_select; /* read-write */
    le16 queue_size; /* read-write */
    le16 queue_msix_vector; /* read-write */
    le16 queue_enable; /* read-write */
    le16 queue_notify_off; /* read-only for driver */
    le64 queue_desc; /* read-write */
    le64 queue_driver; /* read-write */
    le64 queue_device; /* read-write */
};

notification cap 會在共通的 cap 結構後附加資料

struct virtio_pci_notify_cap {
    struct virtio_pci_cap cap;
    le32 notify_off_multiplier; /* Multiplier for queue_notify_off. */
};

裝置驅動程式發起 avail buffer notification 時會寫入一個記憶體位置，用這個 cap 先計算相對於 BAR 的偏移量，偏移量由以下算式取得
每個 queue 有各自的 `queue_notify_off` ，由 Common configuration 提供

cap.offset + queue_notify_off * notify_off_multiplier

ISR status cap 用來指示 INT#x interrupt 的狀態，要求至少 single byte 的空間，當驅動讀取這個空間時會將值重設為 0 ，裝置發起 virtqueue 相關的通知時會設定 bit 1

| Bits | 0 | 1 | 2 to 31 |
| ------- | --------------- | ----------------------------- | -------- |
| Purpose | Queue Interrupt | Device Configuration Interrup | Reserved |

PCI configuration access capability 也是直接在原有的 cap 後面附加資料，提供額外存取 BAR 空間的機制

- `cap.bar`: 指示要存取的 BAR 空間
- `cap.offset`: 指示要存取的位址對於 BAR 的偏移量
- `cap.length`: 為存取的長度
- `pci_cfg_data`: 為對應的資料

struct virtio_pci_cfg_cap {
    struct virtio_pci_cap cap;
    u8 pci_cfg_data[4]; /* Data for BAR access. */
};

Device-specific configuration 由各裝置定義

## Virtio-Blk

Virtio-Blk 的 Device configuration 如下，除了 `capacity` 其他欄位需要對應的 Feature 才會使用到

- `capacity` : Block Device 的大小，以 512 bytes 的 sector 為單位

struct virtio_blk_config {
    le64 capacity;
    le32 size_max;
    le32 seg_max;
    struct virtio_blk_geometry {
        le16 cylinders;
        u8 heads;
        u8 sectors;
    } geometry;
    le32 blk_size;
    struct virtio_blk_topology {
        // # of logical blocks per physical block (log2)
        u8 physical_block_exp;
        // offset of first aligned logical block
        u8 alignment_offset;
        // suggested minimum I/O size in blocks
        le16 min_io_size;
        // optimal (suggested maximum) I/O size in blocks
        le32 opt_io_size;
    } topology;
    u8 writeback;
    u8 unused0[3];
    le32 max_discard_sectors;
    le32 max_discard_seg;
    le32 discard_sector_alignment;
    le32 max_write_zeroes_sectors;
    le32 max_write_zeroes_seg;
    u8 write_zeroes_may_unmap;
    u8 unused1[3];
};

### Feature bits

### Device Operation

request 的格式如下，一個 request buffer 會被分為以下:

struct virtio_blk_req {
    le32 type;
    le32 reserved;
    le64 sector;
    u8 data[];
    u8 status;
};

- `type`: request 的種類

#define VIRTIO_BLK_T_IN 0
#define VIRTIO_BLK_T_OUT 1
#define VIRTIO_BLK_T_FLUSH 4
#define VIRTIO_BLK_T_DISCARD 11
#define VIRTIO_BLK_T_WRITE_ZEROES 13

- `sector`: 相對於裝置開頭的偏移量，以 sector 為單位
- `data`: request 需要的資料
- `status`: request 的狀態，由裝置寫入

#define VIRTIO_BLK_S_OK 0
#define VIRTIO_BLK_S_IOERR 1
#define VIRTIO_BLK_S_UNSUPP 2

對於 `VIRTIO_BLK_T_IN` 和 `VIRTIO_BLK_T_OUT` ， `data[]` 是讀寫操作資料的存取處

## 實作

### bus
> [bus.c](https://github.com/sysprog21/kvm-host/blob/master/src/bus.c)

用來處理位址與裝置的映射關係，使用鏈結串列管理裝置

struct dev {
    uint64_t base;
    uint64_t len;
    void *owner;
    dev_io_fn do_io;
    struct dev *next;
};

struct bus {
    uint64_t dev_num;
    struct dev *head;
};

使用以下函式將 `dev` 註冊到 `bus` 上

void bus_register_dev(struct bus *bus, struct dev *dev);

使用以下函式對 `bus` 發起 IO 請求，根據 `dev` 的 `base` 和 `len` 找出目標裝置，然後呼叫 `do_io` 這個 callback
`owner` 是指向擁有這個 `dev` 的結構體，用於 callback 的參數

void bus_handle_io(struct bus *bus, void* data, uint8_t is_write, uint64_t addr, uint8_t size);

實作中有 `io_bus` 和 `mmio_bus` 處理 `KVM_EXIT` 的事件，以及一個 `pci_bus` 處理 pci 裝置的配置空間

### pci
> [pci.c](https://github.com/sysprog21/kvm-host/blob/master/src/pci.c)

首先註冊這兩個裝置到 io_bus ， `pci_addr_dev` 位於 CF8 ，而 `pci_bus_dev` 位於 CFC

bus_register_dev(io_bus, &pci->pci_addr_dev);
bus_register_dev(io_bus, &pci->pci_bus_dev);

`pci_bus_dev` 的 callback 會去 `pci_bus` 找到我們註冊的 virtio-blk 裝置，完成對 PCI裝置配置空間的讀寫操作

static void pci_data_io(void *owner, void *data, uint8_t is_write, uint64_t offset, uint8_t size)
{
    struct pci *pci = (struct pci *) owner;
    uint64_t addr = pci->pci_addr.value | offset;
    bus_handle_io(&pci->pci_bus, data, is_write, addr, size);
}

當 Guest OS 寫入 pci 配置空間的 command 時，低兩位是用來開啟或關閉記憶體映射的，此時將 bar 的位址註冊到對應的 bus 上

static inline void pci_activate_bar(struct pci_dev *dev, uint8_t bar, struct bus *bus)
{
    if (!dev->bar_active[bar] && dev->hdr.bar[bar])
        bus_register_dev(bus, &dev->space_dev[bar]);
    dev->bar_active[bar] = true;
}

static void pci_command_bar(struct pci_dev *dev)
{
    bool enable_io = dev->hdr.command & PCI_COMMAND_IO;
    bool enable_mem = dev->hdr.command & PCI_COMMAND_MEMORY;
    for (int i = 0; i < PCI_CFG_NUM_BAR; i++) {
        struct bus *bus = dev->bar_is_io_space[i] ? dev->io_bus : dev->mmio_bus;
        bool enable = dev->bar_is_io_space[i] ? enable_io : enable_mem;

        if(enable)
            pci_activate_bar(dev, i, bus);
        else
            pci_deactivate_bar(dev, i, bus);
    }
}

此時 Guest OS 可以存取到 virtio-pci 的配置空間

pci 0000:00:00.0: BAR 0: assigned [mem 0x40000000-0x400000ff]

### virtio-pci
> [virtio-pci.c](https://github.com/sysprog21/kvm-host/blob/master/src/virtio-pci.c)

負責初始化 pci 裝置的配置空間及 virtio-pci 裝置的配置空間
之前註冊到 `mmio_bus` 或 `io_bus` 的 bar 裝置也是由 virtio-pci 負責初始化，其 callback 除了普通的讀寫操作，還有完成 feature select 、 queue select 等機制

virtio-pci 0000:00:00.0: enabling device (0000 -> 0002)

目前的實作將 virtio-pci 的四個 capability 的配置空間放在同一個 bar

struct virtio_pci_config {
    struct virtio_pci_common_config common_config;
    struct virtio_pci_isr_cap isr_cap;
    struct virtio_pci_notify_data notify_data;
    void *dev_config;
};

裝置驅動程式通知裝置的方式是透過寫入某個位址，實作中是寫入 `notify_data`
收到通知後使用 virtq 的 `virtq_handle_avail` 處理通知

if (offset == offsetof(struct virtio_pci_config, notify_data))
    virtq_handle_avail(&dev->vq[dev->config.notify_data.vqn]);

### virtq
> [virtq.c](https://github.com/sysprog21/kvm-host/blob/master/src/virtq.c)

`virtq_handle_avail` 實作如下

void virtq_handle_avail(struct virtq *vq)
{
    struct virtq_event_suppress *driver_event_suppress =
        (struct virtq_event_suppress *) vq->info.driver_addr;

    if (!vq->info.enable)
        return;
    virtq_complete_request(vq);
    if (driver_event_suppress->flags == RING_EVENT_FLAGS_ENABLE)
        virtq_notify_used(vq);
}

目前共有三種由裝置實作的操作，包括 `virtq_complete_request` 和 `virtq_notify_used`
- `enable_vq` 用於 Guest OS 寫入 common config 的 `queue_enable` 時，啟用 virtqueue
- `complete_request` 組裝收到的 element ，並對實際的裝置發起 IO 請求
- `virtq_notify_used` 則是通知驅動有 used buffer 可用

struct virtq_ops {
    void (*complete_request)(struct virtq *vq);
    void (*enable_vq)(struct virtq *vq);
    void (*notify_used)(struct virtq *vq);
};

`virtq` 的核心在 `virtq_get_avail` ，這個函式會根據前述之 packed virtqueues 的規定，回傳下一個 avail 的 descriptor

union virtq_desc *virtq_get_avail(struct virtq *vq)
{
    union virtq_desc *desc_ring = (union virtq_desc *) vq->info.desc_addr;
    union virtq_desc *desc = &desc_ring[vq->next_avail_idx];
    uint16_t flags = desc->pdesc.flags;
    bool avail = flags & VIRTQ_DESC_F_AVAIL;
    bool used = flags & VIRTQ_DESC_F_USED;

    if (avail != vq->used_wrap_count || used == vq->used_wrap_count) {
        return NULL;
    }
    vq->next_avail_idx++;
    if (vq->next_avail_idx >= vq->info.size) {
        vq->next_avail_idx -= vq->info.size;
        vq->used_wrap_count ^= 1;
    }
    return desc;
}

### virtio-blk
> [virtio-blk.c](https://github.com/sysprog21/kvm-host/blob/master/src/virtio-blk.c)

`virtio-blk` 負責 `virtq` 與 `virtio-pci` 的初始化，以及提供 device-specific config 和實作 `virtq_ops`

static struct virtq_ops ops = {
    .enable_vq = virtio_blk_enable_vq,
    .complete_request = virtio_blk_complete_request,
    .notify_used = virtio_blk_notify_used,
};

- `virtio_blk_enable_vq` 將 Guest OS 填入的 virtq 位址轉成 kvm-host 可存取的位址
- `virtio_blk_complete_request` 使用 `virtq_get_avail` 取得 element 並根據 `struct virtio_blk_req` 組合 element ，然後依照 request 的內容發起對 block device 的讀寫
- `virtio_blk_notify_used` 目前僅是使用 `vm_irq_trigger` 透過 kvm 對 Guest OS 發起 interrupt

實作使用 disk image 作為 block device ， `virtio-blk` 發起的讀寫請求也就是對該檔案的讀寫

## 改進

### eventfd

參考 [eventfd(2)](https://man7.org/linux/man-pages/man2/eventfd.2.html)
eventfd 用於程式間的溝通機制，對 eventfd 寫入相當於發起通知，對 eventfd 讀取相當於等待通知

### irqfd

參考 [kvm: add support for irqfd](https://lwn.net/Articles/332924/) 及 [qemu-kvm的irqfd机制](https://www.cnblogs.com/haiyonghao/p/14440723.html)
irqfd 是 kvm 提供用於透過 eventfd 發起 interrupt 的機制
首先透過 `ioctl` 將 eventfd 跟 interrupt 綁定

void vm_ioeventfd_register(vm_t *v,
                           int fd,
                           unsigned long long addr,
                           int len,
                           int flags)
{
    struct kvm_ioeventfd ioeventfd = {
        .fd = fd, .addr = addr, .len = len, .flags = flags};

    if (ioctl(v->vm_fd, KVM_IOEVENTFD, &ioeventfd) < 0)
        throw_err("Failed to set the status of IOEVENTFD");
}

原先使用 `ioctl` 發送 interrupt 現在改為 `write`

static void virtio_blk_notify_used(struct virtq *vq)
{
    struct virtio_blk_dev *dev = (struct virtio_blk_dev *) vq->dev;
    uint64_t n = 1;

    if (write(dev->irqfd, &n, sizeof(n)) < 0)
        throw_err("Failed to write the irqfd");
}

### ioeventfd

參考 [KVM: add ioeventfd support](https://patchwork.kernel.org/project/kvm/patch/[e-mail]/)

ioeventfd 為 KVM 提供用於透過 eventfd 通知 IO 事件發生的機制
當 Guest 進行 IO 操作觸發 vm-exit 時， kvm 會先判斷該位址是否有註冊 eventfd ，若有則透過 eventfd 通知，然後讓 Guest 繼續執行
用於某些實際上不傳輸資料僅作為通知的 IO 請求，可以減少時間的開銷，如 virtio-pci 的 avail buffer notification
首先將 eventfd 註冊為 ioeventfd

uint64_t addr = virtio_pci_get_notify_addr(&dev->virtio_pci_dev, vq);
vm_ioeventfd_register(v, dev->ioeventfd, addr,
                      dev->virtio_pci_dev.notify_len, 0);

然後建立一個執行緒，用以等待 ioeventfd 的通知

pthread_create(&dev->vq_avail_thread, NULL, virtio_blk_vq_avail_handler,
               (void *) vq);

static void *virtio_blk_vq_avail_handler(void *arg)
{
    struct virtq *vq = (struct virtq *) arg;
    struct virtio_blk_dev *dev = (struct virtio_blk_dev *) vq->dev;
    uint64_t n;
    while (read(dev->ioeventfd, &n, sizeof(n))) {
        virtq_handle_avail(vq);
    }
    return NULL;
}

完成後當 Guest 寫入該位址， kvm 會通知這個 ioeventfd ，然後執行 `virtq_handle_avail`

### Linux Kernel vhost

[linux/drivers/vhost/](https://github.com/torvalds/linux/tree/master/drivers/vhost)

irqfd 與 ioeventfd 實際上多用於 vhost 與 kvm 的溝通， vhost 也就是負責處理 virtqueue 的 avail buffer 與實際發送 IO 請求的這部分
若 vhost 實作在 kernel space ，可以減少從 kernel space 來回切換到 user space 的開銷

但目前 Linux Kernel 沒有 vhost-blk，Asias He 發過 patch 但未被採納 [vhost-blk: Add vhost-blk support v6](https://patchwork.ozlabs.org/project/netdev/patch/[e-mail]/)
可以參考 [linux/drivers/vhost/blk.c](https://github.com/asias/linux/blob/blk.vhost-blk/drivers/vhost/blk.c)

## VirtIO 測試

若要在 Guest Linux 使用 EXT4 ，得開啟以下編譯選項

CONFIG_EXT4_FS=y

在 Linux 使用以下命令建立一個 ext4 的 disk image

$ dd if=/dev/zero of=./virtio_blk.img bs=1M count=8
mkfs.ext4 ./virtio_blk.img

使用參數 `-d virtio_blk.img` 執行 kvm-host ，確認 Guest Linux 有以下訊息

virtio_blk virtio0: [vda] 16384 512-byte logical blocks (8.39 MB/8.00 MiB)

使用以下命令在 Guest Linux 掛載裝置

$ mkdir disk
$ mount /dev/vda disk

使用 `$ cat /proc/mounts` 確認是否有掛載成功

/dev/vda /disk ext4 rw,relatime 0 0

嘗試在 `/disk` 建立檔案，並確保檔案有被寫入

$ touch /disk/test
$ sync

使用 `ls /disk` 可以看到 `test` 已被建立

lost+found  test

退出 kvm-host ，嘗試掛載 virtio_blk.img ，使用 `losetup` 可以查看 loop device 的編號

$ sudo losetup -f virtio_blk.img
$ mkdir /tmp/disk
$ sudo mount /dev/loop19 /tmp/disk

掛載成功後，使用 `ls /tmp/disk` 查看裡面的內容

lost+found  test

至此確認 virtio-blk 的存取正常運作

## 雲端公司對於 KVM 的採納

AWS: [The Nitro System journey](https://docs.aws.amazon.com/whitepapers/latest/security-design-of-aws-nitro-system/the-nitro-system-journey.html)

[Deep dive on the AWS Nitro System](https://d1.awsstatic.com/events/Summits/reinvent2022/CMP301_Powering-Amazon-EC2-Deep-dive-on-the-AWS-Nitro-System.pdf) / [video](https://youtu.be/jAaqfeyvvSE) (2022 年)
> [中文介紹](https://aws.amazon.com/tw/ec2/nitro/)

GCP: [About nested virtualization](https://cloud.google.com/compute/docs/instances/nested-virtualization/overview)

Android: [AVF architecture](https://source.android.com/docs/core/virtualization/architecture?hl=en)
> [在 Google Pixel 6 成功跑起 Win11 虛擬機器](https://www.techbang.com/posts/94185-android-13-meritorious-service-google-pixel-6-successfully)