---
# System prepended metadata

title: OpenSSD Cosmos+ Firmware - GreedyFTL

---

# OpenSSD Cosmos+ Firmware - GreedyFTL

## Abbreviations / Aliases

### FTL

- BBT (Bad Block Table)
- FB (Free Block)
- LUN (Plane)
- LBA/LBN (Logical Block Address/Number)
- PBA/PBN (Physical Block Address/Number)
- LSA (Logical Slice Address)
- VSA (Virtual Slice Address, Location Vector)
- MBS (Main Block Space)
- TBS (Total Block Space)
- Llr (Low-level Scheduler)

### NVMe


- CPL (Complete)

### Flash

- NSC (Nand Storage Controller)
- NFC (Nand Flash Controller)

---

## Overview

![](https://i.imgur.com/9Q7BUNE.png)

:::warning
雖然能夠設定 SLC 或 MLC Mode，但 SLC 其實只是用 MLC 的 LSB Page 而已。
:::

:::danger
新的 Flash Module 似乎只支援 SLC mode。
:::

---

## Request and Data Buffer

### Request

:::info
NVMe Command 主要分成 Admin Command 與 IO（NVM）Command 兩種，以下的內容以 IO（NVM）Command 為主。
:::

在目前的 FW 實作中，大致上將請求（Request）分類成兩大類：

1. Slice Request：

    從 Host 傳來的 NVM Command 不一定會剛好要對一個 Page 進行讀寫，所以 FW 在收到 NVM Command 時就會將每個 NVM Command 切成數個 Slice Request 以便 FW 進行處理。
    
    例如：一個 NVMe Read 的 NVM Command 可能一次想讀 10 個 Page，這時候這個 NVM Command 就會被切成 10 個 Slice Request 分別處理這 10 個 Page。

2. NVMe DMA Request 與 NAND Request：

    Slice Request 只是將 NVM Command 切成以 Page Size 為單位的數個請求而已，所以 Slice Request 基本上還是用來表示 NVMe Read、NVMe Flush 等較上層的操作。
    
    但硬體通常沒辦法直接處理這些上層的操作，所以會將 Slice Request 再細分成硬體能夠處理的子請求，例如：NVMe Write 可能會被切成 NAND Read + NVMe DMA Rx + NAND Write 三個子操作來處理。
    
    而 FW 會根據這些子請求的目標是 Host 還是 NAND 再細分成 NVMe DMA Request 與 NAND Request 兩類，但這兩類子請求基本上都還是 Slice Request 的子請求而已。

![](https://i.imgur.com/Okxakws.png)

而這兩大類請求在 FW 中都是以 `SSD_REQ_FORMAT` 這個結構體來管理：

```c
typedef struct _SSD_REQ_FORMAT
{
    unsigned int reqType           : 4;
    unsigned int reqQueueType      : 4;
    unsigned int reqCode           : 8;
    unsigned int nvmeCmdSlotTag    : 16;
    unsigned int logicalSliceAddr;

    REQ_OPTION reqOpt;
    DATA_BUF_INFO dataBufInfo;
    NVME_DMA_INFO nvmeDmaInfo;
    NAND_INFO nandInfo;

    unsigned int prevReq           : 16;
    unsigned int nextReq           : 16;
    unsigned int prevBlockingReq   : 16;
    unsigned int nextBlockingReq   : 16;
} SSD_REQ_FORMAT, *P_SSD_REQ_FORMAT;
```

:::danger
`nvmeCmdSlotTag` 應該是用來代表該請求源自於哪個 NVM Command，基本上都是用來處理 NVMe DMA 相關的操作，在 FTL 的運作中幾乎沒有用到。
:::

每個 `SSD_REQ_FORMAT` 的實例（instance）都代表一個 Request Entry，而這個結構體中的成員 `reqType` 被用來代表這個 Request Entry 對應的是 Slice Request、NVMe Request 還是 NAND Request：

```c=
// request_format.h
#define REQ_TYPE_SLICE    0x0
#define REQ_TYPE_NAND     0x1
#define REQ_TYPE_NVME_DMA 0x2
```

而當請求的類型是 NVMe DMA Request 或 NAND Request 時，另一個成員 `reqCode` 則會被用來表示這個請求實際上對應到哪個操作：

```c=
// request_format.h
#define REQ_CODE_WRITE         0x00
#define REQ_CODE_READ          0x08
#define REQ_CODE_READ_TRANSFER 0x09
#define REQ_CODE_ERASE         0x0C
#define REQ_CODE_RESET         0x0D
#define REQ_CODE_SET_FEATURE   0x0E
#define REQ_CODE_FLUSH         0x0F
#define REQ_CODE_RxDMA         0x10
#define REQ_CODE_TxDMA         0x20
```

### Request Queue

但是這些請求在 FW 中被使用的時機不同，例如 Scheduling 時不會處理 Slice Request，因為那些請求基本上已經被切成 NVMe DMA Request 或 NAND Request 了。

因此，為了有效的管理這些不同類型的請求，目前的 FW 實作中定義多種請求佇列（Request Queue）來儲存不同類型的 Request Entry：

```c=
// request_queue.h
typedef struct _REQUEST_QUEUE
{
    unsigned int headReq : 16;
    unsigned int tailReq : 16;
    unsigned int reqCnt : 16;
    unsigned int reserved0 : 16;
} REQUEST_QUEUE, *P_REQUEST_QUEUE;

typedef REQUEST_QUEUE FREE_REQUEST_QUEUE;
typedef REQUEST_QUEUE SLICE_REQUEST_QUEUE;
typedef REQUEST_QUEUE BLOCKED_BY_BUFFER_DEPENDENCY_REQUEST_QUEUE;
typedef REQUEST_QUEUE BLOCKED_BY_ROW_ADDR_DEPENDENCY_REQUEST_QUEUE
typedef REQUEST_QUEUE NVME_DMA_REQUEST_QUEUE;
typedef REQUEST_QUEUE NAND_REQUEST_QUEUE;
```

:::warning
目前的 FW 中其實是定義多個結構完全相同的結構體代表不同的請求佇列，這邊為了方便說明，直接簡化成一個 base structure 加上多個 `typedef`。
:::

因此另一個成員 `reqQueueType` 就是用來代表這個 Request Entry 目前位於哪個請求佇列中：

```c=
// request_format.h
#define REQ_QUEUE_TYPE_NONE                    0x0
#define REQ_QUEUE_TYPE_FREE                    0x1
#define REQ_QUEUE_TYPE_SLICE                   0x2
#define REQ_QUEUE_TYPE_BLOCKED_BY_BUF_DEP      0x3
#define REQ_QUEUE_TYPE_BLOCKED_BY_ROW_ADDR_DEP 0x4
#define REQ_QUEUE_TYPE_NVME_DMA                0x5
#define REQ_QUEUE_TYPE_NAND                    0x6
```

:::warning
`BLOCKED_BY_BUF_DEP` 與 `BLOCKED_BY_ROW_ADDR_DEP` 應該算是 `REQ_QUEUE_TYPE_NAND` 的子類，主要用於 Scheduling。
:::

並在 `request_allocation.c` 中實作各個請求佇列的 enqueue 及 qequeue 操作，例如 `PutToFreeReqQ()` 與 `GetFromFreeReqQ()` 就分別用來處理 `FREE_REQUEST_QUEUE` 的 enqueue 及 dequeue 操作。

:::info
若是搭配上面提到的 `REQUEST_QUEUE` 觀察 enqueue 以及 dequeue 的實作的話，會發現這些請求佇列其實只管理了頭尾兩個 Request Entry 的索引值而已，而頭尾之間的節點則是透過 `SSD_REQ_FORMAT` 中的 `prevReq` 與 `nextReq` 兩個成員來達成類似雙向鏈結串列（Doubly Linked List）的操作。

目前的 FW 實作中大量使用了類似的技巧來管理各種串列以及佇列，而不是像一般的鏈結串列直接使用指標將指向其他節點。
:::

### Data Buffer

:::success
在說明 Blocking Request 相關的成員以及操作之前，必須先說明 Data Buffer。
:::

由於 Request Entry 能夠提供不同類型的請求使用，而並不是每種請求都需要分配空間以便進行讀寫，所以 Request Entry 的結構體中並不直接包含用來存放 Page 資料的空間，而是以 `SSD_REQ_FORMAT` 結構體中的成員 `dataBufInfo` 指向對應的 Buffer Entry。

```c=
typedef struct _DATA_BUF_INFO
{
    union
    {
        uintptr_t addr;     // real buffer address
        unsigned int entry; // data buffer entry index
    };
} DATA_BUF_INFO, *P_DATA_BUF_INFO;
```

而在目前的實作中，這些 Buffer Entry 被定義在由 `DATA_BUFFER_BASE_ADDR` 指向的記憶體位置開始的 `AVAILABLE_DATA_BUFFER_ENTRY_COUNT * 16384` 位元組的空間，其中 `AVAILABLE_DATA_BUFFER_ENTRY_COUNT` 的預設值為 `16 * USER_DIES`，因此預設的 Data Buffer 共佔用 16 MiB 的 DRAM 空間。

這些 Data Buffer 會在發出請求（`IssueNandReq()` 與 `IssueNvmeDmaReq()`）時透過呼叫 `GenerateDataBufAddr()` 進行分配，而這個分配規則分成兩類：

- 根據這個請求設定的 entry index 進行分配

    當 Request Entry 的 `DATA_BUF_INFO::dataBufFormat` 被設定為 `REQ_OPT_DATA_BUF_ENTRY` 時，代表 `SSD_REQ_FORMAT::DATA_BUF_INFO` 中存的資訊是預計要使用的 Buffer Entry 的 index，因此只要簡單的將 `SSD_REQ_FORMAT::DATA_BUF_INFO::entry` 作為 index 存取對應的 Buffer Entry，並以對應 Buffer Entry 的起始位址作為這個請求的 Buffer 的起始位址就可以了。
    
    :::warning
    需要注意的是，每個 Buffer Entry 的空間是 16 KiB，與 Page Size 相同，但在 GreedyFTL 的設定中，NVMe Block 的大小是 4 KiB，這代表 NVMe 請求中的 LBA 可能不會剛好對應到每個 Page 的開頭。
    
    因此在透過 `ReqTransNvmeToSlice()` 將 NVMe 請求切成 Slice Requests 時，需要為切出來的第一個 Slice Request 設定偏移量（`SSD_REQ_FORMAT::NVME_DMA_INFO::nvmeBlockOffset`），避免 LBA 與 VBA 的對齊出現問題。
    
    而由於 Flash 只會從 Buffer 的起始位址開始存取資料，因此從 Flash Memory 資料到 Data Buffer 時，也需要根據偏移量調整 Buffer 的起始位址。
    :::

- 根據這個請求設定的 buffer address 進行分配

    若 Request Entry 的 `DATA_BUF_INFO::dataBufFormat` 被設定為 `REQ_OPT_DATA_BUF_ADDR` 時，則會直接拿 `SSD_REQ_FORMAT::DATA_BUF_INFO::addr` 指向的位址作為 Buffer。
    

由於在 `GenerateDataBufAddr()` 中處理 NVMe 請求時有限定 `DATA_BUF_INFO::dataBufFormat` 必須為 `REQ_OPT_DATA_BUF_ENTRY`，所以在目前的實作中，只有在處理 Bad Block 的時候才會直接指定要用哪塊空間當作 Buffer，其餘的讀寫請求都是在處理 Slice Request 時就直接分配 Buffer Entry Index 了。

#### Spare Data Buffer

當在處理 NAND 請求時，由於每個 Page 都有一小塊 Spare Region，所以也需要額外分配空間用來存放這些資料，而分配空間的函式為 `GenerateSpareDataBufAddr()`。

`GenerateSpareDataBufAddr()` 的概念與 `GenerateDataBufAddr()` 相似，一樣分成 `REQ_OPT_DATA_BUF_ENTRY` 與 `REQ_OPT_DATA_BUF_ADDR` 兩類，只是在 Spare Data Buffer 的 Buffer Entry 大小為 256 位元組，且起始地址是 `SPARE_DATA_BUFFER_BASE_ADDR`。

:::danger
目前的實作中有在 `GenerateSpareDataBufAddr()` 處理 NVMe 請求，但應該不需要為 NVMe 請求分配 Spare Region 才對。
:::

#### Temp Buffer and Reserved Buffer

在上面有提到 FW 中的請求大多都是分配 Buffer Entry Index，並為請求分配一個 Data Buffer Entry 來存取資料。

但在目前的實作中其實還包含兩類特殊的 Buffer 用來處理特殊的讀寫請求：

- TEMPORARY: 專門給 GC 的讀寫操作使用的空間
- RESERVED: 有些請求不會進行讀寫，所以只要分配一個沒在用的位址即可

#### Data Buffer Entry

而為了管理這些 Buffer Entry，目前的 FW 透過 `DATA_BUF_MAP` 結構體維護了一個 Buffer Map：

```c=
// data_buffer.h
typedef struct _DATA_BUF_ENTRY
{
    unsigned int logicalSliceAddr;
    unsigned int prevEntry         : 16;
    unsigned int nextEntry         : 16;
    unsigned int blockingReqTail   : 16;
    unsigned int hashPrevEntry     : 16;
    unsigned int hashNextEntry     : 16;
    unsigned int dirty             : 1;
    unsigned int reserved0         : 15;
} DATA_BUF_ENTRY, *P_DATA_BUF_ENTRY;

typedef struct _DATA_BUF_MAP
{
    DATA_BUF_ENTRY dataBuf[AVAILABLE_DATA_BUFFER_ENTRY_COUNT];
} DATA_BUF_MAP, *P_DATA_BUF_MAP;
```

這個 Buffer Map 的每個欄位都對應到一個 Data Buffer Entry，也因此數量與 Data Buffer Entry 的數量相同，但 Buffer Map Entry 並不直接指向對應的 Data Buffer Entry。

在初始化的過程中，FW 會建立一個列表來管理空的 Buffer Entry，當要發出讀寫請求時，就透過 `AllocateDataBuf()` 選擇 Buffer Entry 來使用。

一開始所有的 Buffer Entry 都是空的，但隨著讀寫次數的增加，可能會出現所有 Buffer Entry 都有資料的情況，這時候 FW 會選擇將 LRU Entry 拿來重複使用，而目前的實作中是透過 `DATA_BUF_LRU_LIST` 結構體將 Buffer Entry 以 LRU List 的形式進行管理：

```c=
// data_buffer.h
typedef struct _DATA_BUF_LRU_LIST
{
    unsigned int headEntry : 16; // entry index of MRU buffer entry
    unsigned int tailEntry : 16; // entry index of LRU buffer entry
} DATA_BUF_LRU_LIST, *P_DATA_BUF_LRU_LIST;
```

但這個結構體其實只紀錄了 LRU List 的頭尾兩端的索引值，也就是 MRU Entry 與 LRU Entry 的索引值而已，中間的 Buffer Entry 都是透過 `DATA_BUF_ENTRY` 結構體中的 `prevEntry` 與 `nextEntry` 兩個成員形成一個雙向的串列。

前面有提到「FW 會建立一個列表來管理空的 Buffer Entry」，而實際上這個列表其實跟這邊講到的 LRU List 是相同的，只是因為一開始所有 Buffer Entry 都會是空的，所以這個 LRU List 就相當於空的 Buffer Entry 的列表。但其實每當呼叫 `AllocateDataBuf()` 來分配空間給讀寫請求時時，被選中的 Buffer Entry 就會被移動到 LRU List 的開頭。

而這些 Buffer Entry 不只用來存放準備要寫入到 NAND 或回傳給 Host 的資料而已，它們其實也會被拿來作為 Read Cache 與 Write Buffer 使用：

- Read Cache:

    若處理讀取請求時，目標 LPA 之前有被讀取過，且資料仍被某個 Buffer Entry 所保有的話，處理這個讀取請求時就可以跳過從 NAND 讀取資料到 DRAM Buffer 中的過程。

- Write Buffer:

    FW 在處理 Host 發出寫入請求時，需要先分配一個 Data Buffer 用來接受 Host 傳來的資料，然後才會再透過 Flash DMA 將 Data Buffer 中的資料寫入到 Flash Memory 中。
    
    但若每次都馬上將從 Host 傳來的資料寫入到 Flash Memory 的話，容易有寫入放大的問題，特別是在**資料大小小於 Page Size** 與**頻繁修改特定 Page** 的時候。因此，為了減緩這個問題，FW 在收到 Host 傳來的資料後，不會馬上將資料傳到 Flash Memory 並完成寫入，而是會先將資料透過 Data Buffer 作為快取，若太久沒被存取到的話，才會被 Flush 到 Flash Memory 中完成真正的寫入。
    
    如此一來，當資料被更新時，就可以直接更新快取，而不是重新寫入到新的 Page 中。


而為了避免每次在處理讀寫操作時都要走訪整個 LRU List 來檢查目標的 LPA 的資料是否有緩存在 Buffer Entry 中，目前的 FW 中使用了一個雜湊表 `DATA_BUF_HASH_TABLE` 來管理些 Buffer Entry，以便快速的檢查目標 LPA 的資料是否有在 Buffer 中：

```c=
// data_buffer.h
#define FindDataBufHashTableEntry(lsa) ((lsa) % AVAILABLE_DATA_BUFFER_ENTRY_COUNT)

typedef struct _DATA_BUF_HASH_TABLE
{
    DATA_BUF_HASH_ENTRY dataBufHash[AVAILABLE_DATA_BUFFER_ENTRY_COUNT];
} DATA_BUF_HASH_TABLE, *P_DATA_BUF_HASH_TABLE;

typedef struct _DATA_BUF_HASH_ENTRY
{
    unsigned int headEntry : 16;
    unsigned int tailEntry : 16;
} DATA_BUF_HASH_ENTRY, *P_DATA_BUF_HASH_ENTRY
```

### Blocking Request

#### Data buffer Dependency

#### Row Address Dependency

---

## Address Translation and Flash Management

### Flash Geometry

1 Module = 4 Channels = 4 x 8 Ways = 4 x 8 Dies

![](https://i.imgur.com/BZl59hk.png)

### Block Spaces 

在當前的實作中，Physical Block 被分成 User blocks 與 Reserved Blocks：
   
- User Blocks (`USER_BLOCKS_PER_LUN`):

    實際上會被用來儲存資料的 Physical Blocks，預設會分配每個 Plane 的前 `USER_BLOCKS_PER_LUN` 個 block 作為 User Blocks，從可以透過修改定義在 `ftl_config.h` 中的 `USER_BLOCKS_PER_LUN` 來調整每個 Plane 要用來儲存資料的 block 數量，預設使用 2048 個 Physical Blocks，也就是每個 Plane 的前 2048 個 Physical Block 會被拿來儲存資料。

- Reserved/Extended Blocks (`TOTAL_BLOCKS_PER_LUN - USER_BLOCKS_PER_LUN`):

    非 User Blocks 的 Physical Block 都屬於 Reserved Block。
    
    由於 User Blocks 中很可能會包含 bad blocks，所以在初始化時會將 User Blocks 中的 bad blocks 重新指向到 Reserved Blocks 中的 Free Blocks。

:::info
在 FW 中，除了以 User/Reserved Blocks 來區分 Physical Blocks 之外，也會用 Main Block Space 或 Total Block Space：

- Main Block Space (MBS)：用來儲存資料的 Physical Blocks，即 User Blocks
- Total Block Space (TBS)：所有 Physical Blocks，即 User Blocks + Reserved Blocks
:::


### Bad Block Management

每個 die 都有一個 Bad Block Table (BBT) 紀錄該 die 中的每個 block 是否為 bad block，預設存在該 die 中第一個 block 的第一個 LSB page (MLC mode)：

![](https://i.imgur.com/zAaxdew.png)

### Recover BBTs from flash (during `InitFTL()`)

:::danger
TODO:
![](https://i.imgur.com/RaDASeB.png)

![](https://i.imgur.com/EAZQBfa.png)
:::

### Physical Block <-> Virtual Block

一般 FTL 的 L2P table 的 Physical block 在目前的 FW 中是以 Virtual block 來稱呼。

不將其稱為 Physical block 的原因是因為在初始化階段時，有些 Physical block 可能會是 bad block，而這些 bad block 會以 Reserved block 進行替換，並在 FTL 中以 Virtual block 的形式與 Logical block 保持一對一的 Mapping。

:::warning
因為實際上會被 Reserved block 替換的 Physical block 有限，所以 Virtual to Physical 的 Mapping 大致上是呈現 Static Mapping 的感覺。
:::

![](https://i.imgur.com/58tx0HS.png)

而在 GreedyFTL 中，Physical Block 與 Virtual Block 是透過以下結構體來管理：

```c=
// address_translation.h

typedef struct _PHY_BLOCK_MAP
{
    PHY_BLOCK_ENTRY phyBlock[USER_DIES][TOTAL_BLOCKS_PER_DIE];
} PHY_BLOCK_MAP, *P_PHY_BLOCK_MAP;

typedef struct _PHY_BLOCK_ENTRY
{
    unsigned int remappedPhyBlock : 16;
    unsigned int bad : 1;
    unsigned int reserved0 : 15;
} PHY_BLOCK_ENTRY, *P_PHY_BLOCK_ENTRY;

typedef struct _VIRTUAL_BLOCK_MAP
{
    VIRTUAL_BLOCK_ENTRY block[USER_DIES][USER_BLOCKS_PER_DIE];
} VIRTUAL_BLOCK_MAP, *P_VIRTUAL_BLOCK_MAP;

typedef struct _VIRTUAL_BLOCK_ENTRY
{
    unsigned int bad : 1;
    unsigned int free : 1;
    unsigned int invalidSliceCnt : 16;
    unsigned int reserved0 : 10;
    unsigned int currentPage : 16;
    unsigned int eraseCnt : 16;
    unsigned int prevBlock : 16;
    unsigned int nextBlock : 16;
} VIRTUAL_BLOCK_ENTRY, *P_VIRTUAL_BLOCK_ENTRY;
```

每個 die 都有對應的 virtual/physical block list，而 virtual 與 physical 的對應關係會在 FW 啟動時呼叫 `InitBlockDieMap()` 建立。

在 `InitBlockDieMap()` 中，主要可以分成 4 個部份：

1. 初始化 Block Mapping
2. 重建 BBT (Bad Block Table)

    嘗試從特定的 Physical Block 讀取上次儲存的 BBT，若 BBT 不存在的話則需要檢查每個 Physical Block 來確定各個 Physical Block 的狀態（free or bad）。
    
    而在重建 BBT 的過程中，除了更新 BBT 相關的資料結構之外，也會更新各個 Physical Block 的 `bad` 變數。

3. 替換 Bad Blocks

    在 BBT 完成重建後，FW 已經知道有哪些 block 是 bad block，因此接下來需要決定該用哪些 physical blocks 取代 bad blocks。
    
    目前的替換策略會依序檢查所有 User Blocks，每當發現有 User Block 時，就拿當前可用的第一個 Reserved Block 來取代 bad user block，並將被取代的 bad user block 的 `remappedPhyBlock` 指向被分配到的 non-bad reserved block。
    
4. 建立 V2P Mapping

    由於管理 Virtual Block 的結構體中並不包含指向對應 Physical Block 的成員，所以在初始化與使用時只會透過巨集進行簡單的 VBA to PBA 的轉換：

    ```c=
    // address_translation.h
    #define Vblock2PblockOfTbsTranslation(blk) \
        (\
            ((blk) / (USER_BLOCKS_PER_LUN)) * (TOTAL_BLOCKS_PER_LUN)\
            + ((blk) % (USER_BLOCKS_PER_LUN))\
        )
    // alias `VBA2PBA` for convenience in later cases
    ```

    這個巨集不會將 VBA 轉換成 remap 後的 Physical Block 的 PBA，也就是只會轉換成前面提到的 Ideal V2P 的 Physical Address，所以在初始化和使用時還需要透過 Physical Block 的成員 `remappedPhyBlock` 找到這個 Virtual Block 實際對應的 Physical Block。

    ```c=
    // address_translation.c
    void InitBlockMap() // pseudo code
    {
        foreach (die in dies)
        {
            foreach (vblk in die.vblks)
            {
                // find corresponding physical block
                pblk = die.pblks[VBA2PBA(vblk.vba)].remappedPhyBlock;
                
                // assign the remapped block's status
                vblk.bad = pblk.bad;
                
                // reset vblk
                vblk.free = true;
                vblk.eraseCnt = 0;
                vblk.invalidCnt = 0;
                vblk.currentPage = 0;
                
                // if the remapped block is not bad block
                if (!vblk.bad)
                    die.free_blocks.append(vblk);
            }
        }
    }
    ```

### Logical Slice (Page) <-> Virtual Slice

在 GreedyFTL 的 FW 中，Slice 基本上就是 Flash Page，而 FW 為了處理 overwrite 的問題，會用 L2P Table 來管理 Logical Address 與 Physical Address 的對應關係，而在 GreedyFTL 中用以下結構體來管理 page-level 的 **L2V** Table：

```c=
// address_translation.h

typedef struct _LOGICAL_SLICE_ENTRY
{
    unsigned int virtualSliceAddr;
} LOGICAL_SLICE_ENTRY, *P_LOGICAL_SLICE_ENTRY;

typedef struct _LOGICAL_SLICE_MAP
{
    LOGICAL_SLICE_ENTRY logicalSlice[SLICES_PER_SSD];
} LOGICAL_SLICE_MAP, *P_LOGICAL_SLICE_MAP;
```

由於目前的 FW 實作不會儲存 Mapping Table 到 Flash Memory 中，所以在 FW 初始化時只會重設 L2V Mapping，並在處理寫入操作時透過 `AddrTransWrite()` 分配一個 Virtual Address 給對應的 Logical Address。


:::warning
一般來說，FTL 只需要 L2P 就足夠了，P2L 只在啟動 FW 時用來復原 Mapping Table，但在 GreedyFTL 中也包含了 P2L，並透過以下結構體管理：

```c=
// address_translation.h

typedef struct _VIRTUAL_SLICE_ENTRY
{
    unsigned int logicalSliceAddr;
} VIRTUAL_SLICE_ENTRY, *P_VIRTUAL_SLICE_ENTRY;

typedef struct _VIRTUAL_SLICE_MAP
{
    VIRTUAL_SLICE_ENTRY virtualSlice[SLICES_PER_SSD];
} VIRTUAL_SLICE_MAP, *P_VIRTUAL_SLICE_MAP;
```

:::

---

## Garbage Collection

---

## Scheduling

#### Request States

request types: 4

- Read_Trigger
- Read_Transfer
- Write
- Erase

#### Lists

每個 channel 都有 7 個 list 管理該 channel 上的 dies:

![](https://i.imgur.com/ZcAYg3v.png)

scheduler 會根據 pending request 的狀況決定該 channel 的 dies 要放在哪個 list 中，若 scheduler 發現有一個 read request 要在 die 4 上執行且 die 4 位於 idle list 的話，scheduler 就會把 die 4 移動到 read_trigger list：


![](https://i.imgur.com/sgutzHB.png)

但由於 channel 可能正好位於 busy 的狀態，所以 die 4 被加入到對應的 list 後不會馬上被執行。等到這個 read_trigger request 被正式執行（issue）後，die 4 會被移動到 status_check list：

![](https://i.imgur.com/oVqu9Na.png)

scheduler 會在每次呼叫 schedule function 時檢查 status_check list 中的 dies 的執行情況，若發現 request 完成的話，就會將對應的 die 移回 idle list，否則移到 status_report list 等待下次檢查 status_report list：

![](https://i.imgur.com/buDOV5A.png)

### Die States

![](https://i.imgur.com/r1C4Mxa.png)

### Scheduling Flow

![](https://i.imgur.com/I2v5v9M.png)

---