軟體與硬體的距離

你是否對於作業系統與其他外接硬體的溝通方式感到好奇？ 又或者會否好奇 xv6 作業系統是如何透過虛擬機順利讀取到硬碟？甚至是讀取到鍵盤輸入的字元? 本篇文章將會帶讀者探討 Virtio 以及作業系統如何處理各種中斷，順利的與外部設備進行溝通。

KVM / QEMU 的效能瓶頸

QEMU 與 KVM 屬於完全虛擬化的解決方案，在沒有硬體加速輔助的情況下，所有的工作都必須透過軟體模擬，這樣一來會造成模擬器的效能低落(尤其是 device I/O 的部分)。 一般來說，模擬器的 I/O request 的完整操作會經過流程：

• I/O Trap

Trap 的中文有陷阱的意思，閱讀過先前的異常與中斷文章便會知道，不論是 Exceptions 或是 Interrupt ，其處理機制都是前去中斷向量表找出對應的 ISR 。 這樣的動作就好比跳入提前設下陷阱一樣，所以稱為 Trap 。

• 將處理結果丟到 I/O sharing page

• 通知 QEMU process 來取得 I/O 資訊，並交由 QEMU I/O Emulation Code 來模擬 I/O request

• 完成後將結果放回 I/O sharing page

• 通知 KVM module 中的 I/O trap 將處理結果取回並回傳給 virtual machine

從上面複雜的步驟不難看出模擬器的 I/O 為何會效率不彰，除了每次 I/O request 處理的流程繁複之外，過多的 VMEntry, VMExit, context switch，也都是拖垮 QEMU 效能的原因。

Virtio

圖片取自該連結。

Virio 協定提供一個與虛擬裝置溝通的渠道，像是: block device (HDD), input device (鍵盤滑鼠)等等。

Block device driver in Xv6

+-------------+
| File system |
+-------------+
|    VirtIO   |
+-------------+
|     HDD     |
+-------------+

Xv6 實作了 mkfs 這個系統呼叫，當虛擬機啟動時便會自動讀取/新增虛擬的 IDE 硬碟，順序大概如下:

1. 呼叫 mkfs 讀取 fs.img 中的資訊，如果 fs.img 不存在就創建一個。
2. 使用 Virtio 構建的 Block device driver 開始初始化並讀取 Device 的相關資訊。
3. 待作業系統初始化完成， Block device driver 會負責檔案系統與硬碟之間的溝通。

Virtio 可視為硬體的抽象，提供了健全的應用程式介面。這樣一來，作業系統就能透過 API ，支援 Network 、 Block 、 Balloon 等 I/O 裝置。

Descriptor

Descriptor 包含這些訊息: 地址，地址長度，某些 flag 和其他信息。 使用 Descriptor ，我們可以將設備指向 RAM 中任何緩衝區的內存位址。

struct virtq_desc
{
  uint64 addr;
  uint32 len;
  uint16 flags;
  uint16 next;
};

• addr: 我們可以在 64-bit 內存地址內的任何位置告訴設備存儲位置。
• len: 讓 Device 知道有多少內存可用。
• flags: 用於控制 descriptor 。
• next: 告訴 Device 下一個描述符的 Index 。如果指定了 VIRTQ_DESC_F_NEXT， Device 僅讀取該字段。否則無效。

AvailableRing

用來存放 Descriptor 的索引，當 Device 收到通知時，它會檢查 AvailableRing 確認需要讀取哪些 Descriptor 。

需要注意的是: Descriptor 和 AvailableRing 都存儲在 RAM 中。

struct virtq_avail
{
  uint16 flags;     // always zero
  uint16 idx;       // driver will write ring[idx] next
  uint16 ring[NUM]; // descriptor numbers of chain heads
  uint16 unused;
};

UsedRing

UsedRing 讓 Device 能夠向 OS 發送訊息，因此， Device 通常使用它來告知 OS 它已完成先前通知的請求。 AvailableRing 與 UsedRing 非常相似，差別在於: OS 需要查看 UsedRing 得知哪個 Descriptor 已經被服務。

struct virtq_used_elem
{
  uint32 id; // index of start of completed descriptor chain
  uint32 len;
};

struct virtq_used
{
  uint16 flags; // always zero
  uint16 idx;   // device increments when it adds a ring[] entry
  struct virtq_used_elem ring[NUM];
};

系統如何處理中斷

在更先前的章節中，筆者已經介紹過 RISC-V 的異常與中斷處理，當時有提到 CSR 寄存器與 CSR 指令，本篇文章會接續著介紹作業系統是如何針對中斷進行處理以做到搶佔式多工、讀入鍵盤輸入的字元等等。

中斷向量表

中斷向量表是由作業系統程式所維護，維基百科上是這麼描述的:

每一個表項紀錄一個中斷處理程式 (ISR，Interrupt Service Routine) 的位址。

在 RISC-V 架構上的作業系統，我們會將中斷向量表的位置寫進入 CSR 暫存器: mtvec 中

// 在作業系統初始化的時候，需要先將中斷向量表建立完成:
w_mtvec((reg_t)trap_vector);

當中斷或是異常發生時， Program counter 就會跳入 mtvec 所指向的地方開始執行:

.globl trap_vector
# the trap vector base address must always be aligned on a 4-byte boundary
.align 4
trap_vector:
	# save context(registers).
	csrrw	t6, mscratch, t6	# swap t6 and mscratch
	reg_save t6
	csrw	mscratch, t6

	# call the C trap handler in trap.c
	csrr	a0, mepc
	csrr	a1, mcause
	call	trap_handler

	# trap_handler will return the return address via a0.
	csrw	mepc, a0

	# restore context(registers).
	csrr	t6, mscratch
	reg_restore t6

	# return to whatever we were doing before trap.
	mret

上面的範例中， trap_vector 先將 mscratch 的內容進行保存，在保存之後進行了一個很關鍵的操作:

csrr	a0, mepc
csrr	a1, mcause
call	trap_handler

補充: mscratch 是一個 MXLEN 位寬可讀寫的暫存器，一般來說，它用來保存 hart-local 上下文空間的 pointer ，並在進入 machine 模式 trap 處理程序時與通用暫存器交換。

當我們在 call function 時， RISC-V 會將 a0 與 a1 暫存器做為 function 的參數，所以我們把 mepc 與 mcause 作為參數塞給 trap_handler() 並呼叫它:

reg_t trap_handler(reg_t epc, reg_t cause)
{
	reg_t return_pc = epc;
	reg_t cause_code = cause & 0xfff;
	
	if (cause & 0x80000000) {
		/* Asynchronous trap - interrupt */
		switch (cause_code) {
		case 3:
			uart_puts("software interruption!\n");
			break;
		case 7:
			uart_puts("timer interruption!\n");
			break;
		case 11:
			uart_puts("external interruption!\n");
			external_interrupt_handler();
			break;
		default:
			uart_puts("unknown async exception!\n");
			break;
		}
	} else {
		/* Synchronous trap - exception */
		printf("Sync exceptions!, code = %d\n", cause_code);
		panic("OOPS! What can I do!");
		//return_pc += 4;
	}

	return return_pc;
}

跳到 trap_handler() 之後，它會針對不同類型的中斷呼叫不同的 handler ，所以我們可以將它視為一個中斷的派發任務中繼站:

                         +----------------+
                         | soft_handler() |
                 +-------+----------------+
                 |
+----------------+-------+-----------------+
| trap_handler() |       | timer_handler() |
+----------------+       +-----------------+
                 |
                 +-------+-----------------+
                         | exter_handler() |
                         +-----------------+

由於 UART 中斷也是屬於外部中斷的，所以在 external_handler() 我們可以看到它又做了更細一步的判斷:

void external_interrupt_handler()
{
	int irq = plic_claim();

	if (irq == UART0_IRQ){
      		uart_isr();
	} else if (irq) {
		printf("unexpected interrupt irq = %d\n", irq);
	}
	
	if (irq) {
		plic_complete(irq);
	}
}

如果 IRQ 是屬於 UART 的 IRQ ， Handler 就可以呼叫 uart_getc() 等函式取得鍵盤輸入的字元。 並且，等到 Handler 執行完成後， trap_vector 會恢復 mscratch 的數值並把 Program counter 修正到原來的位置繼續執行系統程式。

為 mini-riscv-os 添增 Block device driver

在實現外部中斷的機制以後，我們已經在先前的 Lab 中加入了 UART 的 ISR，為了讓作業系統能夠讀取磁碟資料，我們必須加入 VirtIO 的 ISR :

void external_handler()
{
  int irq = plic_claim();
  if (irq == UART0_IRQ)
  {
    lib_isr();
  }
  else if (irq == VIRTIO_IRQ)
  {
    virtio_disk_isr();
  }
  else if (irq)
  {
    lib_printf("unexpected interrupt irq = %d\n", irq);
  }

  if (irq)
  {
    plic_complete(irq);
  }
}

external_handler() 會透過 IRQ 識別中斷的外部來源，再交給其他 ISR 做處理。 在看到 VirtIO 的 ISR 實作前，我們先來看一下讀寫請求是如何產生的吧!

發送 Block request

宣告 req 的結構:

struct virtio_blk_req *buf0 = &disk.ops[idx[0]];

因為磁碟有讀寫操作之分，為了讓 qemu 知道要讀還是要寫，我們要在請求中的 type 成員中寫入 flag :

if(write)
  buf0->type = VIRTIO_BLK_T_OUT; // write the disk
else
  buf0->type = VIRTIO_BLK_T_IN; // read the disk
buf0->reserved = 0; // The reserved portion is used to pad the header to 16 bytes and move the 32-bit sector field to the correct place.
buf0->sector = sector; // specify the sector that we wanna modified.

填充 Descriptor

到了這一步，我們已經分配好 Descriptor 與 req 的基本資料了，接著我們可以對這三個 Descriptor 做資料填充:

disk.desc[idx[0]].addr = buf0;
  disk.desc[idx[0]].len = sizeof(struct virtio_blk_req);
  disk.desc[idx[0]].flags = VRING_DESC_F_NEXT;
  disk.desc[idx[0]].next = idx[1];

  disk.desc[idx[1]].addr = ((uint32)b->data) & 0xffffffff;
  disk.desc[idx[1]].len = BSIZE;
  if (write)
    disk.desc[idx[1]].flags = 0; // device reads b->data
  else
    disk.desc[idx[1]].flags = VRING_DESC_F_WRITE; // device writes b->data
  disk.desc[idx[1]].flags |= VRING_DESC_F_NEXT;
  disk.desc[idx[1]].next = idx[2];

  disk.info[idx[0]].status = 0xff; // device writes 0 on success
  disk.desc[idx[2]].addr = (uint32)&disk.info[idx[0]].status;
  disk.desc[idx[2]].len = 1;
  disk.desc[idx[2]].flags = VRING_DESC_F_WRITE; // device writes the status
  disk.desc[idx[2]].next = 0;

  // record struct buf for virtio_disk_intr().
  b->disk = 1;
  disk.info[idx[0]].b = b;

  // tell the device the first index in our chain of descriptors.
  disk.avail->ring[disk.avail->idx % NUM] = idx[0];

  __sync_synchronize();

  // tell the device another avail ring entry is available.
  disk.avail->idx += 1; // not % NUM ...

  __sync_synchronize();

  *R(VIRTIO_MMIO_QUEUE_NOTIFY) = 0; // value is queue number

  // Wait for virtio_disk_intr() to say request has finished.
  while (b->disk == 1)
  {
  }

  disk.info[idx[0]].b = 0;
  free_chain(idx[0]);

當 Descriptor 被填充完畢，*R(VIRTIO_MMIO_QUEUE_NOTIFY) = 0; 會提醒 VIRTIO 接收我們的 Block request。

此外，while (b->disk == 1) 可以確保作業系統收到 Virtio 發出的外部中斷後再繼續執行下面的程式碼。

實作 VirtIO 的 ISR

當系統程式接收到外部中斷，會根據 IRQ Number 判斷中斷是由哪一個外部設備發起的 (VirtIO, UART...)。

void external_handler()
{
  int irq = plic_claim();
  if (irq == UART0_IRQ)
  {
    lib_isr();
  }
  else if (irq == VIRTIO_IRQ)
  {
    lib_puts("Virtio IRQ\n");
    virtio_disk_isr();
  }
  else if (irq)
  {
    lib_printf("unexpected interrupt irq = %d\n", irq);
  }

  if (irq)
  {
    plic_complete(irq);
  }
}

如果是 VirtIO 發起的中斷，便會轉派給 virtio_disk_isr() 進行處理。

void virtio_disk_isr()
{

  // the device won't raise another interrupt until we tell it
  // we've seen this interrupt, which the following line does.
  // this may race with the device writing new entries to
  // the "used" ring, in which case we may process the new
  // completion entries in this interrupt, and have nothing to do
  // in the next interrupt, which is harmless.
  *R(VIRTIO_MMIO_INTERRUPT_ACK) = *R(VIRTIO_MMIO_INTERRUPT_STATUS) & 0x3;

  __sync_synchronize();

  // the device increments disk.used->idx when it
  // adds an entry to the used ring.

  while (disk.used_idx != disk.used->idx)
  {
    __sync_synchronize();
    int id = disk.used->ring[disk.used_idx % NUM].id;

    if (disk.info[id].status != 0)
      panic("virtio_disk_intr status");

    struct blk *b = disk.info[id].b;
    b->disk = 0; // disk is done with buf
    disk.used_idx += 1;
  }

}

virtio_disk_isr() 主要工作會將 disk 的狀態改下，告訴系統先前發出的讀寫操作已經被順利執行了。 其中 b->disk = 0;，可以讓先前提到的 while (b->disk == 1) 順利跳出，釋放 disk 中的自旋鎖。

int os_main(void)
{
	os_start();
	disk_read();
	int current_task = 0;
	while (1)
	{
		lib_puts("OS: Activate next task\n");
		task_go(current_task);
		lib_puts("OS: Back to OS\n");
		current_task = (current_task + 1) % taskTop; // Round Robin Scheduling
		lib_puts("\n");
	}
	return 0;
}

由於 mini-riscv-os 並沒有實作能夠休眠的鎖，所以筆者將 disk_read() 這個測試函式在開機時執行一次，若要向上實現更高層的檔案系統，就會需要使用 sleep lock，以避免當有多個任務嘗試取用硬碟資源時造成 deadlock 的情況發生。

總結

本篇提到了 VirtIO 與中斷向量表，有些讀者可能會不明白兩者個關聯性，其實我們透過 virtio 操作 block device 時，也會發送各種中斷(軟體中斷或是外部中斷)， 了解系統程式如何處理中斷後，我們就可以依樣畫葫蘆的為作業系統添加不同的功能。 最後，本篇的外部中斷程式範例參考了 《从头写一个RISC-V OS》课程 ，在筆者閱讀多個不同的 RISC-V 作業系統後，發現這些作業系統都是這樣處理中斷的，如果讀者想看簡單的 Timer Interrupt ，可以參考 mini-riscv-os 的說明文件，本文便不對此多做介紹。

Reference

• xv6-riscv
• 小信豬的原始部落
• RISC-V OS using Rust
• What role do QEMU and KVM play in virtual machine I/O?
• 《从头写一个RISC-V OS》课程
• Lecture: Virtual I/O Protocol Operating Systems Stephen Marz
• Implementing a virtio-blk driver in my own operating system
• xv6-rv32