原理NVM Express - NVMe Submission Queue & Completion Queue (SQ & CQ)

NVM Express，又簡稱NVMe，他提供了Host Software與non-volatile memory之間的介面規範，讓兩者搭起溝通橋梁，同時提供了優化SSD的方法及標準，並且充分運用PCIe的高頻寬，使得存取速度大幅的提升。本篇文章是基於NVMe Base Specification 1.4c版本的觀點去撰寫，相關的spec可以在NVMe協會網站上取得。

■ Introduction

NVMe spec定義了兩種和NVM Subsystem的溝通方式，分別為(1)NVMe over PCIe和 (2) NVMe over Fabrics(NVMeoF)。NVMe over PCIe顧名思義就是透過PCIe Protocol去存取NVM Subsystem，在OS裡面看到的，就是一個PCIe device。NVMe over Fabrics基本上就是通過網路來存取NVM Subsystem，例如Ethernet, InfiniBand, Fibre Channel等等，本篇文章主要以NVMe over PCIe介紹為主。

NVMe採用的是Submission & Completion queue pair的機制，而且support同時有65535個I/O Queue Pairs平行運作。Submission Queue ，簡稱SQ，為固定slot buffer size，Host Software透過SQ來提交command(指令)給NVMe Controller執行。Completion Queue，簡稱CQ，為固定slot buffer size，Controller透過Completion Queue回報command執行的狀況為何。

Figure 1

NVMe中的Queue使用的是資料結構的Circular Queue的機制(Figure 2)。何謂Circular Queue，以下有一些使用規則:

• Circular Queue有兩個操作方法，分別為add和delete
• 當Queue為淨空的狀態，Head和Tail會指向相同的slot位置(Figure 2左)
• 當有1個新的物件被add到queue後，Tail會向前移動1個slot，圖1右表示Queue裡面add 3個物件，分別編號為1、2和3
• 由於Queue是First-in-First-out(FIFO)，所以最先提交的物件會最先被delete，所以當1號物件被delete後，Head會往前移動一個slot
• 由於是Circular Queue會一直環繞，所以使用上必須注意Queue "Full"的情況下，就不要再提交物件。

Figure 2

NVMe定義了兩種Queue Pair Type，分別為Admin Queue Pair (Admin Submission Queue & Admin Completion Queue ) 和 I/O Queue Pair(I/O Submission Queue & I/O Completion Queue)。Admin Queue主要用來提交"管理和控制Controller行為"的指令，指令集稱之為Admin Command Set。I/O Queue則是用來提交"存取NVM Media(NAND)"的指令，稱為I/O Command Set(或稱NVM Command Set)。一個Controller一定要Support一對Admin Queue Pair(SQ & CQ)，然後根據Controller Type來決定是否Support 一個或多個I/O Queue。

■ Controller type

NVMe spec中定義了三種Controller type，分別為(1) I/O Controller、(2) Administrative Controller和(3) Discovery Controller，要如何知道目前Controller屬於哪種類型呢? 需要透過Admin Command Set中的Identify Command來獲取Controller的Identify Controller Data Structure中的Controller Type欄位得知(如Figure 3所示)，在文章後面都會使用ICDS.CNTRLTYPE來表示。

Figure 3

● I/O Controller (01h): 市面上最常見的就是此種Controller，允許有一個或多個I/O Queue Pair(SQ & CQ)，並且support NVM Command Set，NVM Command Set主要是用來存取non-volatile storage medium(NAND Flash)。Optional support management capabilities，什麼是management capabilities呢?，如下列所示:

• Management Interface
• 透過NVMe-MI Send和NVMe-MI Receive的interface 可以有效的去輪詢NVM subsystem health status(健康狀態)，NVMe-MI是另外一份spec，就不進一步介紹
• Namespace Management
• 透過Namespace Attachment和Namespace commands來管理Namespace的能力
• Virtualization Management
• 透過Virtualization Management command來管理Virtualization功能的能力
• NVM Subsystem Reset
• 透過NSSR register重置NVM subsystem的能力

● Administrative Controller(02h): Support Admin Command Set來管理NVM Subsystem，但是沒有support I/O command來存取logical block data and metadata的功能，此種controller的用途主要可以用來避免host software去存取user data

● Discovery Controller(03h): 這種特殊的Controller只有用在NVMe over Fabrics(NVMeoF)，主要定義在另一份spec，就不多加介紹。

■ Submission Queue & Completion Queue定義

接下來介紹NVMe的SQ和CQ是如何運作的。Spec裡定義了兩個腳色，分別為Submitter和Consumer，運作流程如Figure 4 & 5:

1. Submitter是Host Software的腳色，負責提交command到SQ，並且會透過寫入新的值到SQ Tail Doorbell register來告知Controller有新的command被提交。 
2. Consumer是Controller的腳色，負責消耗SQ裡的command，當Controller提取command來執行後，Controller會更新SQ Head pointer的值。
3. Controller會提交Command Completion到CQ，並且把Phase Tag的欄位設置為1，目的是為了讓Host Software知道，這是一個新的completion entry。
4. 之後，Controller會發出interrupt(MSI or MSI-X)告知CPU有新的completion被提交到CQ。
• P.S. CQ Tail Pointer只有在Controller內部所使用，對於Host Software來說是不可見的。
5. 當Host收到interrupt之後，會去查看CQ裡面那些是新提交的entry(by Phase Tag)，當completion回報指令執行成功，Host Software會結束掉相對應的事件，並寫入新值到Completion Queue Head Doorbell 。

Figure 4

Figure 5

■ Submission Queue 格式

I/O SQ & CQ可以分配的最高slot entry定義在NVMe的Controller Capabilities register裡的Maximum Queue Entries Supported field (簡寫為CAP.MQES)，最小的Queue Entry Size為2 Slots，最大為64 Ki Slots。Admin  SQ & CQ最大則是4 Ki slots。

Figure 6 為每個SQ Command Entry基本格式，會根據不同的Command才會出現其他CDW(Command Dword)欄位，一個Command Entry總共為64 bytes，byte 0~3簡稱為CDW0，byte 4~7簡稱為CDW1以此類推，接下來介紹每個CDW的欄位的意義:

Figure 6. SQ Command Layout

CDW0.OPC: Opcode，代表每個command獨特的編碼，主要用來識別各個不同command，Opcode for Admin Command和NVM Command的編碼如下表格所示。

Figure 7. SQ Command Layout

CDW0.FUSE: Fused Operation，將兩個Command融合在一起提交，此欄位用來表達當前command為第一個(First)或者是第二個(Second)，編碼如Figure 8。

Figure 8. Fused Operation Field

CDW0.PSDT: PRP or SGL for Data Transfer，此欄位用來決定CDW6~9是PRP List or SGL List，編碼如Figure 9

Figure 9. PSDT Field

CDW0.CID: Command Identifier， Host Software所分配的ID號碼，目的是用來讓Controller知道哪個SQ command entry對應到哪個CQ Completion Entry。

CDW1.NSID: Namespace ID，指定這個Command要apply到哪個Namespace上，將此欄位填上所指定的Namespace ID，如果沒有需要指定Namespace，須將這個欄位填為0h。有些Command允許將此欄位填為FFFFFFFFh，代表此筆command要apply到所有的Namespace。

CDW4.MPTR: Metadata Pointer，有別於PRP or SGL，他是額外的data，最常見的範例就是End-to-end Data Protection，Metadate會用來存放CRC or Checksum for Logical Block Data。

CDW6.DPTR:  Data Pointer，用來指向存放data buffer的memory address，如果PSDT欄位為00b則為PRP List pointer，如果PSDT欄位為01b or 10b，則此欄位為SGL List pointer

■ Completion Queue Entry 格式

Figure 10 為每個CQ Entry基本格式，會根據不同的Completion而有不同的CDW0欄位，CQ Entry總共為16 bytes，byte 0~3簡稱為CDW0，byte 0~4簡稱為CDW1以此類推，接下來介紹每個CDW的欄位的意義:

Figure 10.  Completion Queue Entry Layout

CDW2.SQHD: SQ Head Pointer，為當前的SQ Head pointer的位置(參考Figure 4)，目的是為了讓Host Software清楚知道目前指令已經處裡到哪了。

CDW2.SQID: SQ Identifier，用來表示此completion是對應到哪個SQ裡所提交的command，通常只有在多個SQ使用同一個CQ的情況才需要此欄位。

CDW3.CID: Command Identifier，此欄位與SQ entry裡的CID欄位內容相同，Controller在提交completion的時候會從SQ entry CID欄位複製過來，目的是為了讓Host Software去辨別此completion對應到哪個提交到SQ的command。

CDW3.P:  Phase Tag，用來給Host Software去辨識此completion是否是新提交的，為1可以解釋為Host Software仍尚未處裡。

CDW3.SF:  Status Field，表示此command執行的狀況，此欄位占用15 bits，可以進一部細分為:

• CDW3.SF.DNR: Do Not Retry，Bit 31，如果被清為0表示當command 回報為Fail，可以透過retry來修正。如果為1表示此command不要retry。
• CDW3.SF.M: More，Bit 30，如果設置為1表示有一些額外的error資訊，可以從Get Log Page command with LID 01h(Error Information)中所report的Error Log Page中得到。
• CDW3.SF.CRD: Command Retry Delay，Bit[29:28]，當DNR欄位被清0且Advanced Command Retry Enable (ACRE) 欄位為1h的話，這裡面的值會影響Retry要delay多久。
• CDW3.SF.SCT: Status Code Type，Bit[27:25]，欄位描述如Figure 11，可以分為Generic Command Status、Command Specific Status、Media and Data Integrity Errors和Path Related Status，然後又可以根據不同的SCT field又細分為不同的Status Code。
• CDW3.SF.SC: Status Code，Bit[24:17]，進一步表示error的種類，Figure 12為Generic Command Status的error號碼和其error的描述，由於太多所以只有張貼部分，詳細請參考spec。

Figure 11.  Status Code Type Values

Figure 12.  Status Code – Generic Command Status Values

■ Controller Register

Controller registers位於PCIe Configureation Space裡的MLBAR/MUBAR registers (BAR0 and BAR1)，以Memory-mapped I/O(MMIO)的方式mapping到memory，所以Host Software可以透過Memory Read/Write來access Controller Registers，Controller Registers的定義描述如Figure 13，由於Offset 38h~E1Bh的register為optional，所以暫時不介紹。

Figure 13.  Controller Registers

CAP: Controller Capabilities Register，用來描述Controller的能力，register layout如下圖。

Figure 14.  Controller Capabilities Register

INTMS & INTMC: Interrupt Vector Mask Set和Interrupt Vector Mask Clear，spec建議Host Software可以使用INTMS register來遮罩CPU正在處裡的相對應的interrupt vector ISR，可以避免Controller重複發送相同vector的interrupt。當CPU處裡完ISR後，Host Software在使用INTMC去清除對應的interrupt vector。

Figure 15.  INTMS & INTMC Register

CC: Controller Configuration，主要控制Controller的行為，register layout如下圖。

Figure 16.  Controller Configuration Register

CSTS: Controller Status，用來反映一些Controller狀態，register layout如下圖。

Figure 17.  Controller Status Register

NSSR: NVM Subsystem Reset，朝這個register寫入4E564D65h的值即可觸發NVM Subsystem Reset。

AQA: Admin Queue Attributes，用來決定Admin SQ&CQ Entry Size為何，最小值為2，最大值為4096個entries。

Figure 18.  Admin Queue Attributes Register

ASQ & ACQ: Admin Submission Queue Base & Admin Completion Queue Base Address，當Host Software準備好Admin Queue的memory buffer後，需將memory base address填入這兩個 register來告知Controller。bit[11:0]的值為Reserved，因此Host Software分配的memory必須是4k alignment。

Figure 19.  Admin Queue Base Address Register

SQyTDBL & CQyHDBL: Submission Queue y Tail Doorbell和Completion Queue y Head

Doorbell，如上面所提到，此兩個register是用來讓Host Software與Controller溝通目前的Tail和Head pointer當前的位置。

Figure 20.  SQyTDBL & CQyHDBL Register

■ Initialization

接下來用簡單的動畫來解釋整個Host Software與Controller的溝通示意流程:

1. Host Software準備好Admin CQ Buffer後，將base address填入ACQ register。Spec有規範Admin CQ create的順序必需在Admin SQ之前
2. Host Software準備好Admin SQ Buffer後，將base address填入ASQ register
3. Host Software決定I/O SQ and I/O CQ的size後，寫入CC register的IOCQES和IOSQES field
4. Host Software提交一個Identify Command來獲得Identify Controller Data Structure(ICDS)
5. Host Software敲響Admin SQ Doorbell register
6. Controller回報Identify Controller Data Structure(ICDS)給Host
7. Host Software提交一個Identify Command來獲得Identify Namespace Data Structure(INDS)
8. Controller回報Identify Namespace Data Structure(INDS)
9. Host Software透過ICDS和INDS來決定要create多少的I/O Queues，提交Set Feature Command - Number Of Queues(FID 07h)給Controller。
10. Controller根據Host Software的要求來allocate I/O Queues，並回報allocate的I/O Queue數量
11. Host Software提交Create I/O Completion Queue command來create I/O CQ。這邊和Admin Queue一樣，I/O CQ create的順序必需在I/O SQ之前
12. Host Software提交Create I/O Submission Queue command來create I/O SQ

至此Admin Queue和I/O Queue都已經創建完成。

Reference: NVM Express Base Specification Revision 1.4c