---
# System prepended metadata

title: CAFTL over MQSim
tags: [SSD]

---

# CAFTL over MQSim
###### tags: `SSD`
## Setting
* 為簡化mapping，將`ssdconfig.xml`內的`Ideal_Mapping_Table`設為true
* `workload.xml`只留一個`IO_Flow_Parameter_Set_Trace_Based`，使用`File_Path`讀IO測資路徑

# Observation
## 運行順序
#### 對於每一次write request，會轉化成Flash Transaction，簡稱tr:
1. **`Input_Stream_Manager_NVMe`**::`segment_user_request`: 將LBA轉換成LPA+offset
2. **`Data_Cache_Manager_Flash_Advanced`**::`write_to_destage_buffer`: 更新cache
    * LPA不在cache內直接插入
    * LPA在cache內: bitmap由以下兩者OR的結果去更新
        1. 現在LPA的bitmap
        2. 這個LPA之前進來時的bitmap
        ```cpp=
        Update_data(tr->Stream_id, tr->LPA, content, timestamp, tr->write_sectors_bitmap | slot.State_bitmap_of_existing_sectors);
        ```
3. **`Address_Mapping_Unit_Page_Level`**::`Translate_lpa_to_ppa_and_dispatch`: 對於這些writeback tr做mapping
4. `query_CMT` -> `translate_lpa_to_ppa` -> `allocate_page_in_plane_for_user_write`: 分發page給write
    1. 先透過`translate_lpa_to_ppa`用lpa轉換得出Channel, Chip, Die, Plane的ID
        * `Channel_no`: 8, `Chip_no`: 4, `Die_no`: 2, `Plane_no`: 2
        ```cpp
        targetAddress.ChannelID = domain->Channel_ids[(unsigned int)(lpn % domain->Channel_no)];
        targetAddress.ChipID = domain->Chip_ids[(unsigned int)((lpn / domain->Channel_no) % domain->Chip_no)];
        targetAddress.DieID = domain->Die_ids[(unsigned int)((lpn / (domain->Chip_no * domain->Channel_no)) % domain->Die_no)];
        targetAddress.PlaneID = domain->Plane_ids[(unsigned int)((lpn / (domain->Die_no * domain->Chip_no * domain->Channel_no)) % domain->Plane_no)];
        ```
    2. 取GMT內舊的PPA
        * 如果是NO_PPA(NULL)，代表其為第一次存取
        * 如果不是第一次存取
            1. 先取得之前的page狀態(bitmap): prev_page_status
            2. 將此tr的bitmap與prev_page_status做AND: 得到status_intersection
            3. 看status_intersection與prev_page_status是否一樣
                * 一樣就將old_ppa轉為address，並將此address給block_manager將page標成invalid，並更新Invalid_page_bitmap: `Invalid_page_bitmap[page_address.PageID / 64] |= ((uint64_t)0x1) << (page_address.PageID % 64);`
                    * Invalid_page_bitmap由4個uint64組成的array (256個bit)
                    * Invalidate page 0: 在Invalid_page_bitmap[0]將1 shift left到bit 0的地方
                * 不一樣就要觸發read: update_read_tr
                    1. read_page_bitmap = status_intersection XOR prev_page_status
                    2. 建立*update_read_tr，將LPA, old_ppa, read_page_status也傳進去
                    3. 將old_ppa轉為update_read_tr->Address並更新Invalid_page_bitmap
                    4. 更新tr的RelatedRead成員，代表其會因為partial write觸發read request
                        * Is this read request related to another write request and provides update data (for partial page write)
    3. `Allocate_block_and_page_in_plane_for_user_write`: 
        * 取plane record的BlockID以及PageID (current page write index)
            ```cpp=
            PlaneBookKeepingType *plane_record = &plane_manager[page_address.ChannelID][page_address.ChipID][page_address.DieID][page_address.PlaneID];
            plane_record->Valid_pages_count++;
            plane_record->Free_pages_count--;		
            page_address.BlockID = plane_record->Data_wf[stream_id]->BlockID;
            page_address.PageID = plane_record->Data_wf[stream_id]->Current_page_write_index++;
            ```
        * 並檢查需不需要做GC
            ```cpp=
            if(plane_record->Data_wf[stream_id]->Current_page_write_index == pages_no_per_block) {
                //Assign a new write frontier block
                plane_record->Data_wf[stream_id] = plane_record->Get_a_free_block(stream_id, false);
                gc_and_wl_unit->Check_gc_required(plane_record->Get_free_block_pool_size(), page_address);
            }
            ```
    4. `Convert_address_to_ppa`: 透過address ID算出uint的PPA
        * `chip_no_per_channel`: 4
        * `page_no_per_chip`: 2097152 (2 die/chip)
        * `page_no_per_die`: 1048576 (2 plane/die)
        * `page_no_per_plane`: 524288 (2048 blocks/plane)
        * `pages_no_per_block`: 256
        ```cpp=
        return (PPA_type)this->page_no_per_chip * (PPA_type)(pageAddress.ChannelID * this->chip_no_per_channel + pageAddress.ChipID)
            + this->page_no_per_die * pageAddress.DieID + this->page_no_per_plane * pageAddress.PlaneID
            + this->pages_no_per_block * pageAddress.BlockID + pageAddress.PageID;
        ```
    5. `Update_mapping_info`: 更新GMT內的PPA, WrittenStateBitmap以及TimeStamp
        * WrittenStateBitmap由此tr的bitmap與之前LPA的bitmap做OR得出
        
#### `segment_user_request(...)`可能發生一個page大小的sectors可能分到兩個logical pages，又或者是兩個一樣的LPA要進行tr(未寫滿一個page)
* 第一次寫入: 264719034 16 0 (發生partial write)
    |   sLBA    | size(#of sectors) | write/read |
    |:---------:|:-----------------:|:----------:|
    | 264719034 |        16         |     0      |
    * start LBA為264719034
    * sector_per_page為16 (一個page 8KB)
    * LPA: 264719034 / 16 = 16544939
    * offset: 264719034 % 16 = 10
    * 一次的tr size為16-10=6個sectors
    * 代表這個LPA是從此page的第10個sector開始寫，寫6個sectors
    * LPA 16544939的bitmap如下:
        | 1   | 1   | 1   | 1   | 1   | 1   | 0   | 0   | 0   | 0   | 0   | 0   | 0   | 0   | 0   | 0  |
        | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |:---:|
        | 15   | 14   | 13   | 12   | 11   | 10   | 9   | 8  | 7 | 6   | 5  | 4  | 3  | 2  | 1  | 0  |
    * 更新GMT後
        |   LPA    |   PPA    | Bitmap |
        |:--------:|:--------:|:------:|
        | 16544939 | 28311552 | 64512  |
    * 現在的要寫入的LBA為264719034 + 6 = 264719040
    * LPA: 264719040 / 16 = 16544940
    * offset: 0
    * 剩下的10個sectors則從第0個開始寫共10個sectors
    * LPA 16544940的bitmap如下:
        | 0   | 0   | 0   | 0   | 0   | 0   | 1   | 1   | 1   | 1   | 1   | 1   | 1   | 1   | 1   | 1  |
        | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |:---:|
        | 15   | 14   | 13   | 12   | 11   | 10   | 9   | 8  | 7 | 6   | 5  | 4  | 3  | 2  | 1  | 0  |
    * 更新GMT後
        |   LPA    |   PPA    | Bitmap |
        |:--------:|:--------:|:------:|
        | 16544939 | 28311552 | 64512  |
        | 16544940 | 36700160 |  1023  |
* 第二次寫入: 264719024 10 0
    * LPA: 264719024 / 16 = 16544939
    * offset: 264719024 % 16 = 0
    * 此tr中LPA 16544939的bitmap如下:
        | 0   | 0   | 0   | 0   | 0   | 0   | 1   | 1   | 1   | 1   | 1   | 1   | 1   | 1   | 1   | 1  |
        | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |:---:|
        | 15   | 14   | 13   | 12   | 11   | 10   | 9   | 8  | 7 | 6   | 5  | 4  | 3  | 2  | 1  | 0  |
    * 更新GMT
        * 取prev_page_status: 64512
        * 更新bitmap: 1023 OR prev_page_status: 64512 -> 65535
        * 對Block0 Page0觸發read後: 填滿並額外寫入至新的page
        * 將舊的PPA: 28311552用bitmap標成invalid
        * Block manager將page write index加一
    * 更新GMT後:
        |     LPA      |                PPA                |             Bitmap             |
        |:------------:|:---------------------------------:|:------------------------------:|
        | ~~16544939~~ |           ~~28311552~~            |           ~~64512~~            |
        |   16544939   | 2831155<font color="red">3</font> | <font color="red">65535</font> |
        |   16544940   |             36700160              |              1023              |

# Implementation
## MQSim write request 觀察
* 除了首次寫入外，其他有LPA相關request都會觸發舊PPA的invalidation以及mapping
    1. sLBA與length進來剛好滿一個LPA
        * 將full page write寫入至新的PPA並更新mapping
    3. 第一次LPA發生partial write，後續"相同"LPA進來後變成full write
        * 將PPA標成invalid並觸發read
        * 將full page write寫入至新的PPA並更新mapping
    4. 第一次LPA發生full write，後續"相同"LPA (但是為partial write) 進來
        * 將PPA標成invalid並觸發read
        * 與先前bitmap OR完後寫入至新的PPA並更新mapping (依舊是full page)
    5. 第一次LPA不管發生partial write還是full write，若後續LPA進來與之前的bitmap相同:
        * 將PPA標成invalid
        * 寫入至新的PPA並更新mapping (可能是partial page或是full page)
* CAFTL on MQSim: 每發生一次Full page write，就讀一個FP
## Abstraction of Components
* FP table
    | ==FP==  | PPA | ref |
    | --- | --- |:---:|
* Reverse Mapping
    | ==PPA== | FP | LPA | VPA | use_SMT |
    | --- | ---| --- | --- | ------- |
* Primary Mapping Table (PMT or GMT)
    | ==LPA== | VPA/PPA |
    | --- |:-------:|
* Secondary Mapping Table (SMT)
    | ==VPA== | PPA |
    | --- |:---:|
---
### 新增元件:  Deduplicator
```cpp=
struct ChunkInfo//** Append for CAFTL
{
    PPA_type PPA;
    size_t ref;//number of this chunk appear
}; 
```
```cpp=
class Deduplicator//** Append for CAFTL
{
public:
    Deduplicator();
    ~Deduplicator();
    void Update_FPtable(std::pair<std::string, ChunkInfo> FP_entry);
    void Print_FPtable();
    bool In_FPtable(std::string FP);//** Check if this FP exists in hash table
    ChunkInfo GetChunkInfo(std::string FP);

private:
    std::unordered_map<std::string, ChunkInfo> FPtable;
    size_t Total_chunk_no;
    size_t Dup_chunk_no;
    size_t Dedup_rate;
};
```
---
### 新增成員至AddressMappingDomain
```cpp=
class AddressMappingDomain
{
public:
    //...
    GTDEntryType* GlobalTranslationDirectory;
    Cached_Mapping_Table* CMT;
    GMTEntryType* GlobalMappingTable;
    //...
    
    //** Append for CAFTL
    Deduplicator *deduplicator;
    std::map<VPA_type, SMTEntryType> SecondaryMappingTable;//** For CAFTL 2-level mapping while GMT as Primary Mapping Table in CAFTL. It should be inserted as pair <VPA, PPA>
    std::map<PPA_type, RMEntryType> ReverseMapping;//** Simplify read operation for metadata in OOB e.g., FP by using <PPA, FP> structure to update FP table
    void Update_ReverseMapping(std::pair<PPA_type, RMEntryType> cur_rev_pair);
    void Print_ReverseMapping();
    void Print_PMT();
    void Print_SMT();
    bool In_SMT(VPA_type VPA);
    SMTEntryType Get_SMTEntry(VPA_type VPA);
    std::ifstream fp_input_file;//** Append for CAFTL fp input
    FP_type cur_fp;//** Record current fp
    size_t Write_with_fp_no;
    size_t Total_fp_no;//** Total number of fingerprints
    size_t Total_write_page_no;//** Including partial and full write
    size_t Full_write_page_no;//** Not including partial write
};
```
```cpp=
//** GMT equals to Primary Mapping Table in CAFTL
//** CAFTL maintains SMT (Secondary Mapping Table) for VPN-to-PPN mapping
struct SMTEntryType//** Append for CAFTL
{
    PPA_type PPA;
};
```
```cpp=
struct RMEntryType//** Append for CAFTL reverse mapping
{
    FP_type FP;
    LPA_type LPA;
    VPA_type VPA;
    bool use_SMT;//For unique chunk but using two-level mapping (ref decreases to 1)
};
```


## Modification
### RECAP: in Address_Mapping_Unit_Page_Level
1. query_CMT
2. For each write transaction: translate_lpa_to_ppa
    * allocate_plane_for_user_write: 決定寫入哪個plane
    * allocate_page_in_plane_for_user_write: 決定寫入哪個page
        * 這邊才會更新mapping table以及page invalidation的操作


---
### 架構修改
#### 修改page level mapping的==allocate_page_in_plane_for_user_write()== ：區分成兩種page形式
##### Full page &rArr; 更改成CAFTL架構
* GC write
* user write 
##### Partial page &rArr; 照MQSim原本方式
* GC write
* user write
#### 架構code
```cpp=
if (cur_bitmap == pow(2, sector_no_per_page) - 1)// full page
{
    if (is_for_gc)//GC for CAFTL
    {
        if (old_ppa == NO_PPA) //...
        else //...
    }
    else
    {
        if (std::getline(domain->fp_input_file, domain->cur_fp))
        {
            if (old_ppa != NO_PPA)
            {
                /* 1. LPA update write, update FP info */ 
                if (PPA_invalid == true)
                { 
                    /* 2. PPA invalidation */ 
                }
            }
            /* 3. Dedupe */
            /* 4. Update mapping */
            /* 5. Update Reverse Mapping */
        }
        else; // Fingerprint runs out, do nothing
    }
}
else// partial write
{
    //MQSim original implementation
}
```
---
### [Step 1.] LPA update write &rArr; update FP info
* Check if this LPA write before, if not jump to **[Step 3.]**
* If so: 
    1. Get last time PPA, *oldPPA*. 
        * Query PMT
            | LPA | VPA/==PPA==  |
            |:---:|:------------:|
            |     | VPA/*oldPPA* |
        * And SMT (if necessary)
            | VPA | ==PPA==  |
            | --- |:--------:|
            |     | *oldPPA* |
    3. Get *oldFP* used by *oldPPA*. 
        |   PPA    | ==FP==  | LPA | VPA | use_SMT |
        |:--------:|:-------:| --- | --- | ------- |
        | *oldPPA* | *oldFP* |     |     |         |
    5. Decrease ref by 1 of this FP, then if ref = 0 this PPA should be invalid. 
        |   FP    |   PPA    | ==ref== |
        |:-------:|:--------:|:-------:|
        | *oldFP* | *oldPPA* |         |
#### Q1. What about LPA-VPA after erasing VPA-PPA? 
* This updated LPA will overwrite it.
#### Q2. Why not convert it back to LPA-PPA if the PPA changes from duplicate (ref > 1) to unique (ref = 1)?
* To convert LPA-VPA & VPA-PPA to LPA-PPA, we need to derive VPA first and then derive LPA
* The problem is there's no reverse mapping for VPA to LPA, this will be an **1-to-n** mapping (unfixed for num of references)
```cpp=
if (domain->In_SMT(old_ppa))//If this ppa is converted into vpa already
    old_ppa = domain->Get_SMTEntry(old_ppa).PPA;//fetch ppa but not vpa
FP_type old_fp = domain->ReverseMapping[old_ppa].FP;//Get its fingerprint by RM

ChunkInfo old_chunk = domain->deduplicator->GetChunkInfo(old_fp);//For updation of old_fp info in FPtable

old_chunk.ref -= 1;//Assume this LPA will ref to another PPA
if (old_chunk.ref == 0)//Should this PPA got invalid? If it gots multiple LPA ref this PPA, this PPA should not be invalid
    PPA_invalid = true;//PPA should be invalid

std::pair<FP_type, ChunkInfo> target_pair(old_fp, old_chunk);//Create FP pair to update FPtable
domain->deduplicator->Update_FPtable(target_pair);//Update old fp ref, if the ref == 0 after updation this fp entry will be erased
```
#### Update_FPtable
```cpp=
void Deduplicator::Update_FPtable(std::pair<FP_type, ChunkInfo> FP_entry)
{
    std::unordered_map<FP_type, ChunkInfo>::iterator iter = FPtable.find(FP_entry.first);
    if (iter != FPtable.end())//duplicate
    {
        iter->second.ref = FP_entry.second.ref;
        iter->second.PPA = FP_entry.second.PPA;
        if (iter->second.ref == 0)
            FPtable.erase(FP_entry.first);
    }
    else//unique
        FPtable.insert(FP_entry);
}
```
---
### [Step 2.] PPA invalidation
* If PPA got invalid
    * FP table: corresponding FP got erased in **[Step 1.]**
    * SMT should erase this VPA-PPA mapping if its using SMT
        | VPA |   PPA   |
        | --- |:-------:|
        |     | *oldPPA* |
    * RM should erase this PPA entry
        |   PPA   | FP  | LPA | VPA | use_SMT |
        |:-------:| --- | --- | --- | ------- |
        | *oldPPA* |     |     |     |         |
    * PMT will be updated later
        | LPA | VPA/PPA |
        | --- |:-------:|
        |     | *oldPPA* |
```cpp=
if (PPA_invalid == true)
{
    if (domain->ReverseMapping[old_ppa].use_SMT)//If this old_ppa is using SMT
        domain->SecondaryMappingTable.erase(old_ppa);//
    domain->ReverseMapping.erase(old_ppa);//delete old_ppa reverse mapping
```
#### MQSim MQSim invalidation process
``` cpp=+
    page_status_type prev_page_status = domain->Get_page_status(ideal_mapping_table, transaction->Stream_id, transaction->LPA);
    page_status_type status_intersection = transaction->write_sectors_bitmap & prev_page_status;
    //Check if an update read is required
    if (status_intersection == prev_page_status) {
        NVM::FlashMemory::Physical_Page_Address addr;
        Convert_ppa_to_address(old_ppa, addr);
        block_manager->Invalidate_page_in_block(transaction->Stream_id, addr);
    }
    else {
        page_status_type read_pages_bitmap = status_intersection ^ prev_page_status;
        NVM_Transaction_Flash_RD *update_read_tr = new NVM_Transaction_Flash_RD(transaction->Source, transaction->Stream_id,
            count_sector_no_from_status_bitmap(read_pages_bitmap) * SECTOR_SIZE_IN_BYTE, transaction->LPA, old_ppa, transaction->UserIORequest,
            transaction->Content, transaction, read_pages_bitmap, domain->GlobalMappingTable[transaction->LPA].TimeStamp);
        Convert_ppa_to_address(old_ppa, update_read_tr->Address);
        block_manager->Read_transaction_issued(update_read_tr->Address);//Inform block manager about a new transaction as soon as the transaction's target address is determined
        block_manager->Invalidate_page_in_block(transaction->Stream_id, update_read_tr->Address);
        transaction->RelatedRead = update_read_tr;
    }
}
```
---
### [Step 3.] Dedupe
#### **If its not in FP table**
1. Block Manager allocates a *newPPA*
2. Map current LPA to this *newPPA* 
    | LPA | VPA/==PPA== |
    | --- |:-------:|
    |     | *newPPA* |
4. Insert current FP to FP table
    |   FP    |   PPA    | ref |
    |:-------:|:--------:|:-------:|
    | *curFP* | *newPPA* |         | 
#### **If its in FP table, then Dedup**
1. Get *ref_PPA* from current FP
    |   FP    |   PPA    | ref |
    |:-------:|:--------:|:-------:|
    | *curFP* | *refPPA* |       | 
2. *use_SMT* &rarr; true
3. Notice that when ref = 2, these two LPAs should be mapped to VPA
    | LPA | VPA/==PPA== |
    |:---:|:-----------:|
    |  ori  |  *refPPA*   |
4. *refPPA* &rarr; VPA
    | LPA | VPA/==PPA== |
    |:---:|:-----------:|
    |  ori  |  VPA   |
    | cur| VPA
    * If original LPA already maps to VPA
        |   PPA    | FP  | LPA | VPA | ==use_SMT== |
        |:--------:| --- | --- | --- |:-----------:|
        | *refPPA* |     |     |     |      1      |
    * It looks like this, so do nothing
        | LPA | VPA/==PPA== |
        |:---:|:-----------:|
        | ori |     VPA     | 
5. update FP table
    |   FP    |   PPA    |    ==ref==     |
    |:-------:|:--------:|:----------:|
    | *curFP* | *newPPA* | *oldref++* |
```cpp=
std::cout << "Dedupe current fingerprint\n";
if (!domain->deduplicator->In_FPtable(domain->cur_fp))//First time insertion
{
    block_manager->Allocate_block_and_page_in_plane_for_user_write(transaction->Stream_id, transaction->Address);
    transaction->PPA = Convert_address_to_ppa(transaction->Address);
    cur_chunk = { transaction->PPA, 1 };//Insert first chunk of this entry of hash table
}
else//Found duplication
{
    use_SMT = true;
    size_t new_ref = domain->deduplicator->GetChunkInfo(domain->cur_fp).ref + 1;//With ref increases
    PPA_type PPA = domain->deduplicator->GetChunkInfo(domain->cur_fp).PPA;//Get original PPA from FP table
    cur_chunk = {PPA, new_ref};//Update the chunk info to be inserted into hash table
    VPA = PPA ^ (1ULL << (63));//Convert PPA to VPA
    if (new_ref == 2 && domain->ReverseMapping[PPA].use_SMT == false)//Convert PPA-to-VPA and change previous LPA-to-PPA mapping to LPA-to-VPA
    {
        LPA_type old_lpa = domain->ReverseMapping[PPA].LPA;
        domain->Update_mapping_info(ideal_mapping_table, transaction->Stream_id, old_lpa, VPA, domain->Get_page_status(ideal_mapping_table, transaction->Stream_id, old_lpa));
    }
}

FP_entry = { domain->cur_fp, cur_chunk };
domain->deduplicator->Update_FPtable(FP_entry);//If this FP entry already exists deduplicator will update ref and physical address, or it will directly insert into hash table.
```
---
### [Step 4.] Update mapping 
#### **Use SMT if dedup**
* *curLPA* &rArr; VPA
    |     LPA      | ==VPA==/PPA |
    |:------------:|:-----------:|
    | ori (Step 3) | VPA (Step3) |
    |   **cur**    |   **VPA**   |
* VPA &rArr; *refPPA*
    | VPA | ==PPA==  |
    |:---:|:--------:|
    | VPA | *newPPA* |

```cpp=
if(use_SMT)
{
    domain->Update_mapping_info(ideal_mapping_table, transaction->Stream_id, transaction->LPA, VPA, cur_bitmap);//Map current LPA to VPA
    
    SMTEntryType cur_SMTEntry = { domain->deduplicator->GetChunkInfo(domain->cur_fp).PPA };
    std::pair<VPA_type, SMTEntryType> cur_SMTpair(VPA, cur_SMTEntry);
    if (domain->In_SMT(VPA))
        domain->SecondaryMappingTable.erase(VPA);
    domain->SecondaryMappingTable.insert(cur_SMTpair);
}
else
    domain->Update_mapping_info(ideal_mapping_table, transaction->Stream_id, transaction->LPA, cur_chunk.PPA, cur_bitmap);
```
---
### [Step 5.] Update Reverse Mapping
#### Reverse Mapping (RM) simulates metadata (e.g., LPA/VPA, FP) in OOB
| Physical Page |     OOB      |
|:-------------:|:------------:|
|    page n     | LPA, VPA, FP |

#### Data Structure
| PPA | FP | LPA | VPA | use_SMT |
| --- | ---| --- | --- | ------- |

#### Q1. When to use RM?
* When it triggers GC, we will move valid PPAs to new PPAs.
* By accessing those PPAs, we can:
    1. get FP to update PPA in FP table and 
    2. get LPA/VPA to update mapping.
        * Get new PPA &rArr; If it use_SMT &rArr; Get VPA &rArr; Update SMT
        * Get new PPA &rArr; Not use_SMT &rArr; Get LPA &rArr; Udpate PMT
#### Q2. For those PPAs are duplicate (ref > 1), why using only VPA to update mapping (SMT)?
* For a unique PPA, we move it to a new_PPA and simply maps LPA to new_PPA
    | LPA | VPA/PPA |
    |:---:|:-----------:|
    |  0  |     ~~*invalidPPA*~~     |
    |  1  |     ==*newPPA*==     |
* For a referenced PPA, LPAs maps to a VPA and this VPA maps to this PPA. 
    | LPA | VPA/PPA |
    |:---:|:-----------:|
    |  0  |     VPA     |
    |  1  |     VPA     |
* If we move it to a new_PPA it will be LPAs-VPA and **VPA-new_PPA**
    | VPA | PPA  |
    |:---:|:--------:|
    | ~~VPA~~ | ~~*invalidPPA*~~ |
    | VPA | ==*newPPA*==|
#### Special case: unique PPA but still remain VPA: LPA->VPA->PPA
* If duplicate &rArr; using VPA
* If using VPA &rArr; maybe duplicate
* To prevent unique PPA using LPA->VPA->PPA goes wrong, we check if it use_SMT
    * if use_SMT = true, it will never go back to false status
```cpp=
RMEntryType RMEntry = { domain->cur_fp, transaction->LPA, VPA, use_SMT };
std::pair<PPA_type, RMEntryType> cur_RMEntry(cur_chunk.PPA, RMEntry);
domain->Update_ReverseMapping(cur_RMEntry);
```
```cpp=
void AddressMappingDomain::Update_ReverseMapping(std::pair<PPA_type, RMEntryType> cur_rev_pair)
{
    std::map<PPA_type, RMEntryType>::iterator got = ReverseMapping.find(cur_rev_pair.first);
    if (got == ReverseMapping.end())
        ReverseMapping.insert(cur_rev_pair);
    else
    {
        if (cur_rev_pair.second.use_SMT == true)
            got->second.VPA = cur_rev_pair.second.VPA;
        else
        {
            got->second.LPA = cur_rev_pair.second.LPA;
            got->second.VPA = NO_PPA;
        }
        got->second.use_SMT = cur_rev_pair.second.use_SMT;
    }
}
```
---
### Solving Issues
#### 1. GC時選到的victim block其metadata還沒有寫入，導致需要讀取metadata時發生問題
* 在接口: `NVM_PHY_ONFI_NVDDR2`，傳送指令: `Send_command_to_chip()`
    * 接收完transaction後，要將其lpa寫到ppa的metadata
    * 為確保一致性，這邊的lpa都用reverse mapping去取
* 在進入底層`Flash_Chip`時完成指令: `finish_command_execution()`
    * Write: 前面送出的指令已確保lpa是從reverse mapping取的，然後寫進metadata區域
    * Read: 
        1. 為讀到正確的ppa，先看有無在SMT內
        2. 也透過reverse mapping找到正確的lpa
    * Erase: 將metadata的lpa清掉
#### 2. Read before write的情況
* MQSim在read不到此LPA的PPA時會幫其先建立write
    * `online_create_entry_for_reads(...)`, MQSim作法
    ```cpp=
    block_manager->Allocate_block_and_page_in_plane_for_user_write(stream_id, read_address);
    PPA_type ppa = Convert_address_to_ppa(read_address);
    domain->Update_mapping_info(ideal_mapping_table, stream_id, lpa, ppa, read_sectors_bitmap);

	return ppa;
    ```
    * 因有建立write，所以CAFTL也讀一個FP來做dedup，最後能return真正的ppa去read
         
<!--
#### Future goal:
1. latency
2. io performance
3. dedup rate
4. gc(live page copying)
* `Host system`初始化時建立`IO_Flow_Trace_Based`物件，並在每次`IO_Flow_Trace_Based`執行`Execute_Simulator_Event(...)`時讀取一個trace line
    * Host system管理`IO_Flow_Trace_Based`
    * `IO_Flow_Trace_Based`管理
        ```cpp=
        std::string trace_file_path
        std::ifstream trace_file
        vector<string> traceline
        ```
* `NVM_Transaction_Flash_WR`是在`Input_Stream_Manager_NVMe`的`segment_user_request(...)`內write時建立
    * ifstream交由`Input_Stream_Manage_Base`管理
    * 每次建立一次`NVM_Transaction_Flash_WR`時讀一次fingerprint input，再丟給`NVM_Transaction_Flash_WR`內的成員fp
* 新增fingerprint的input，每讀一個trace line轉換成LPA時就讀一行fingerprint
    * 在class `NVM_Transaction_Flash`額外紀錄fp以及VPA (`NVM_Transaction_Flash_WR`會繼承它)
        :::spoiler class `NVM_Transaction_Flash`
        ```cpp=
        class NVM_Transaction_Flash : public NVM_Transaction
        {
        public:
            NVM_Transaction_Flash(Transaction_Source_Type source, Transaction_Type type, stream_id_type stream_id,
                unsigned int data_size_in_byte, LPA_type lpa, PPA_type ppa, User_Request* user_request, IO_Flow_Priority_Class::Priority priority_class);
            NVM_Transaction_Flash(Transaction_Source_Type source, Transaction_Type type, stream_id_type stream_id,
                unsigned int data_size_in_byte, LPA_type lpa, PPA_type ppa, const NVM::FlashMemory::Physical_Page_Address& address, User_Request* user_request, IO_Flow_Priority_Class::Priority priority_class);
            NVM::FlashMemory::Physical_Page_Address Address;
            unsigned int Data_and_metadata_size_in_byte; //number of bytes contained in the request: bytes in the real page + bytes of metadata

            LPA_type LPA;
            PPA_type PPA;

            //** append for CAFTL
            PPA_type VPA;
            std::string fp;//fingerprint

            //...
        };
        ```
        :::
    * `Host_Interface_Base.h`的`Input_Stream_Manager_Base`開檔、關檔
        :::spoiler code
        ```cpp=
        class Input_Stream_Manager_Base
        {
            friend class Request_Fetch_Unit_Base;
            friend class Request_Fetch_Unit_NVMe;
            friend class Request_Fetch_Unit_SATA;
        public:
            Input_Stream_Manager_Base(Host_Interface_Base* host_interface);
            virtual ~Input_Stream_Manager_Base();
            virtual void Handle_new_arrived_request(User_Request* request) = 0;
            virtual void Handle_arrived_write_data(User_Request* request) = 0;
            virtual void Handle_serviced_request(User_Request* request) = 0;
            void Update_transaction_statistics(NVM_Transaction* transaction);
            uint32_t Get_average_read_transaction_turnaround_time(stream_id_type stream_id);//in microseconds
            uint32_t Get_average_read_transaction_execution_time(stream_id_type stream_id);//in microseconds
            uint32_t Get_average_read_transaction_transfer_time(stream_id_type stream_id);//in microseconds
            uint32_t Get_average_read_transaction_waiting_time(stream_id_type stream_id);//in microseconds
            uint32_t Get_average_write_transaction_turnaround_time(stream_id_type stream_id);//in microseconds
            uint32_t Get_average_write_transaction_execution_time(stream_id_type stream_id);//in microseconds
            uint32_t Get_average_write_transaction_transfer_time(stream_id_type stream_id);//in microseconds
            uint32_t Get_average_write_transaction_waiting_time(stream_id_type stream_id);//in microseconds
        protected:
            Host_Interface_Base* host_interface;
            virtual void segment_user_request(User_Request* user_request) = 0;
            std::vector<Input_Stream_Base*> input_streams;
            std::ifstream fp_input_file;//** append for CAFTL fp input
            std::string cur_fp_input;//** record current fp
        };
        ```
        ```cpp=
        Input_Stream_Manager_Base::Input_Stream_Manager_Base(Host_Interface_Base* host_interface) : host_interface(host_interface)
        {
            fp_input_file.open("fp_input.txt");//** append
        }
        ```
        ```cpp=   
        Input_Stream_Manager_Base::~Input_Stream_Manager_Base()
        {
            for (auto &stream : input_streams) {
                delete stream;
            }
            fp_input_file.close();//** append
        }
        ```
        :::
    * 在`Host_Interface_NVMe.cpp`的`segment_user_request(...)`讀取fingerprint
        :::spoiler `Input_Stream_Manager_NVMe`::`segment_user_request`
        ```cpp=
        void Input_Stream_Manager_NVMe::segment_user_request(User_Request *user_request)
        {
            LHA_type lsa = user_request->Start_LBA;
            LHA_type lsa2 = user_request->Start_LBA;
            unsigned int req_size = user_request->SizeInSectors;

            page_status_type access_status_bitmap = 0;
            unsigned int handled_sectors_count = 0;
            unsigned int transaction_size = 0;
            while (handled_sectors_count < req_size)
            {
                //...

                LPA_type lpa = internal_lsa / host_interface->sectors_per_page;

                page_status_type temp = ~(0xffffffffffffffff << (int)transaction_size);
                access_status_bitmap = temp << (int)(internal_lsa % host_interface->sectors_per_page);

                if (user_request->Type == UserRequestType::READ)
                {
                    //...
                }
                else //user_request->Type == UserRequestType::WRITE
                { 
                    //** Write starts here and creats an NVM_Transaction_Flash_WR initialized by LPA
                    NVM_Transaction_Flash_WR *transaction = new NVM_Transaction_Flash_WR(Transaction_Source_Type::USERIO, user_request->Stream_id,
                                                                                         transaction_size * SECTOR_SIZE_IN_BYTE, lpa, user_request, user_request->Priority_class, 0, access_status_bitmap, CurrentTimeStamp);
                    //** append: initialization of write metadata for CAFTL
                    if (!fp_input_file.is_open()) {
                        PRINT_ERROR("Fail to open fingerprint input");
                        return;
                    }
                    cur_fp_input.clear();

                    if (std::getline(fp_input_file, cur_fp_input))
                    {
                        transaction->fp = cur_fp_input;
                        transaction->VPA = 0;

                    }
                    else {//read empty
                        PRINT_ERROR("Not enough fingerprint for trace file");
                    }

			    //** end of append
                    
                    user_request->Transaction_list.push_back(transaction);
                    input_streams[user_request->Stream_id]->STAT_number_of_write_transactions++;
                }

                lsa = lsa + transaction_size;
                handled_sectors_count += transaction_size;
            }
        }
        ```
        :::

##### Line 1~38 的部分沒有修改
* 取出此LPA之前的bitmap，並與現在tr的bitmap比較
* status_intersection = cur_bitmap ^ old_bitmap, status_intersection == old_bitmap?
    * True: 舊的PPA標成invalid
    * False: 將status_intersection(si)與現在的bitmap做XOR，圈出需要讀取出來的部分，發送read req後並將舊的PPA標成invalid
        * 例如: old: 11111111, cur: 00001111 => si = 00001111
        * si ^ old = 11110000，只需要讀左邊4個1，右邊4個1會被新來的LPA覆蓋
```cpp=
void Address_Mapping_Unit_Page_Level::allocate_page_in_plane_for_user_write(NVM_Transaction_Flash_WR* transaction, bool is_for_gc)
{
    AddressMappingDomain* domain = domains[transaction->Stream_id];
    PPA_type old_ppa = domain->Get_ppa(ideal_mapping_table, transaction->Stream_id, transaction->LPA);

    if (old_ppa == NO_PPA)  /*this is the first access to the logical page*/
    {
        if (is_for_gc) {
            PRINT_ERROR("Unexpected mapping table status in allocate_page_in_plane_for_user_write function for a GC/WL write!")
        }
    } else {
        if (is_for_gc) {
            NVM::FlashMemory::Physical_Page_Address addr;
            Convert_ppa_to_address(old_ppa, addr);
            block_manager->Invalidate_page_in_block(transaction->Stream_id, addr);
            page_status_type page_status_in_cmt = domain->Get_page_status(ideal_mapping_table, transaction->Stream_id, transaction->LPA);
            if (page_status_in_cmt != transaction->write_sectors_bitmap)
                PRINT_ERROR("Unexpected mapping table status in allocate_page_in_plane_for_user_write for a GC/WL write!")
        } else {
            page_status_type prev_page_status = domain->Get_page_status(ideal_mapping_table, transaction->Stream_id, transaction->LPA);
            page_status_type status_intersection = transaction->write_sectors_bitmap & prev_page_status;
            //check if an update read is required
            if (status_intersection == prev_page_status) {
                NVM::FlashMemory::Physical_Page_Address addr;
                Convert_ppa_to_address(old_ppa, addr);
                block_manager->Invalidate_page_in_block(transaction->Stream_id, addr);
            } else {
                page_status_type read_pages_bitmap = status_intersection ^ prev_page_status;
                NVM_Transaction_Flash_RD *update_read_tr = new NVM_Transaction_Flash_RD(transaction->Source, transaction->Stream_id,
                    count_sector_no_from_status_bitmap(read_pages_bitmap) * SECTOR_SIZE_IN_BYTE, transaction->LPA, old_ppa, transaction->UserIORequest,
                    transaction->Content, transaction, read_pages_bitmap, domain->GlobalMappingTable[transaction->LPA].TimeStamp);
                Convert_ppa_to_address(old_ppa, update_read_tr->Address);
                block_manager->Read_transaction_issued(update_read_tr->Address);//Inform block manager about a new transaction as soon as the transaction's target address is determined
                block_manager->Invalidate_page_in_block(transaction->Stream_id, update_read_tr->Address);
                transaction->RelatedRead = update_read_tr;
            }
        }
    }
```
##### Line 39-45 初始化
* 取更新後的最終bitmap
* 建立一個Fingerprint Entry等後續插入或更新hash table
    * key為string的fingerprint (40個char)
    * 每個ChunkInfo包含：ref, PPA, LPA
```cpp=+
//** Modified for CAFTL
    //(1)hash table initialization (2)PPN->VPN (3)VPN-to-PPN mapping
    page_status_type cur_bitmap = ((NVM_Transaction_Flash_WR*)transaction)->write_sectors_bitmap | domain->Get_page_status(ideal_mapping_table, transaction->Stream_id, transaction->LPA);
    ChunkInfo cur_chunk;
    std::pair<std::string, ChunkInfo> FP_entry;
    PPA_type VPA = NO_PPA;
    bool doneVPA = false;
```
##### Line 46-70 讀fingerprint input
* 先確定此為full page，再讀一個FP
* 檢查此fp看是否在FPtable內，如果不在就需要allocate新的page
* 附值給要插入至hash table的chunk，ref設為1
* 更新mapping
* 更新FPtable (Line 88)
```cpp=+
    if (cur_bitmap == pow(2, sector_no_per_page) - 1)//If it is a full page write
    {
        if (!domain->fp_input_file.is_open())
        {
            PRINT_ERROR("Fail to open fingerprint input!");
            return;
        }
        if (std::getline(domain->fp_input_file, domain->cur_fp))//Make sure that fingerprints are sufficient for full page write trace
        {
            std::cout << "\nRead trace line no: " << domain->Write_with_fp_no << ", LPA: " << transaction->LPA << ", FP: " << domain->cur_fp << std::endl;
            if (!domain->deduplicator->In_FPtable(domain->cur_fp))//First time insertion
            {
                /*The following lines should not be ordered with respect to the block_manager->Invalidate_page_in_block
                * function call in the above code blocks. Otherwise, GC may be invoked (due to the call to Allocate_block_....) and
                * may decide to move a page that is just invalidated.*/
                if (is_for_gc) {
                    block_manager->Allocate_block_and_page_in_plane_for_gc_write(transaction->Stream_id, transaction->Address);
                }
                else {
                    block_manager->Allocate_block_and_page_in_plane_for_user_write(transaction->Stream_id, transaction->Address);
                }
                transaction->PPA = Convert_address_to_ppa(transaction->Address);
                cur_chunk = { domain->cur_fp, 1, transaction->PPA, transaction->LPA};//Insert first chunk of this entry of hash table
                domain->Update_mapping_info(ideal_mapping_table, transaction->Stream_id, transaction->LPA, cur_chunk.PPA, cur_bitmap);
            }
```
##### Line 71-86: 開始dedup
* 新的ref為hash table內的ref + 1
* 因為此chunk要被dedup，先透過hash table取得最原始的PPA
* 附值給chunk，後續將hash table更新
* 算出VPA
* 當ref==2時，也需要將最原始的PPA更新成VPA
    * 透過FP去取最原始的LPA （如果要透過PPA取metadata會再觸發一個metadata read)
    * 將最原始的LPA map到VPA
* 將進來的LPA map到VPA
##### Line 87-88: 更新FPtable
```cpp=+
            else//Found duplication
            {
                size_t new_ref = domain->deduplicator->GetChunkInfo(domain->cur_fp).ref + 1;//With ref increases
                PPA_type PPA = domain->deduplicator->GetChunkInfo(domain->cur_fp).PPA;//Get original PPA from FP table
                cur_chunk = { domain->cur_fp, new_ref, PPA, transaction->LPA };//Update the chunk info to be inserted into hash table
                VPA = PPA ^ (1ULL << (63));//Convert PPA to VPA
                doneVPA = true;
                if (new_ref == 2)//Convert PPA-to-VPA and change previous LPA-to-PPA mapping to LPA-to-VPA
                {
                    LPA_type target_lpa = domain->deduplicator->GetChunkInfo(domain->cur_fp).LPA;//Get LPA from hash table
                    //If we get PPA from FP table, it triggers a read to get LPA from flash page metadata
                    //Update both previous LPA and current LPA mapping to LPA-to-VPA
                    domain->Update_mapping_info(ideal_mapping_table, transaction->Stream_id, target_lpa, VPA, domain->Get_page_status(ideal_mapping_table, transaction->Stream_id, target_lpa));
                }
                domain->Update_mapping_info(ideal_mapping_table, transaction->Stream_id, transaction->LPA, VPA, cur_bitmap);//Map current LPA to VPA
            }
            FP_entry = { domain->cur_fp, cur_chunk };
            domain->deduplicator->Update_FPtable(FP_entry);//If this FP entry already exists deduplicator updates ref and physical address, or it directly inserts into hash table.
            domain->Write_with_fp_no++;
```
##### Line 90-95: 更新Secondary Mapping Table (SMT)
* SMT由map<VPN, PPN>來管理
* 當ref==2的時候，代表VPA需要map到PPA
    * 透過FP從hash table取PPA
    * 建立VPA-to-PPA的pair來去更新SMT
* 因為SMT是1-to-1 mapping所以只需要插入一次，日後發生重複時，LPA在Primary Mapping Table (PMT)或是GMT內map到VPA即可
```cpp=+
            if (cur_chunk.ref == 2)//Update VPA-to-PPA Secondary Mapping Table
            {
                SMTEntryType cur_SMTEntry = { domain->deduplicator->GetChunkInfo(domain->cur_fp).PPA };
                std::pair<PPA_type, SMTEntryType> cur_SMTpair(VPA, cur_SMTEntry);
                domain->Update_SMT(ideal_mapping_table, transaction->Stream_id, cur_SMTpair);
            }
            domain->deduplicator->Print_FPtable();
            domain->Print_PMT();
            if (doneVPA == true)
                std::cout << "Did VPA convertion: " << VPA << std::endl;
            domain->Print_SMT();
        }
        else;//No fingerprints
        domain->Full_write_page_no++;
    }
```
##### Line 105-115: partial page write照舊MQSim的方法，讓MQSim順利運行
```cpp=+
    else//Partial page write
    {
        if (is_for_gc) {
            block_manager->Allocate_block_and_page_in_plane_for_gc_write(transaction->Stream_id, transaction->Address);
        }
        else {
            block_manager->Allocate_block_and_page_in_plane_for_user_write(transaction->Stream_id, transaction->Address);
        }

        transaction->PPA = Convert_address_to_ppa(transaction->Address);
        domain->Update_mapping_info(ideal_mapping_table, transaction->Stream_id, transaction->LPA, transaction->PPA, cur_bitmap);
    }
    domain->Total_write_page_no++;
}
```
#### SPECIAL CASE: same LPA but different FP
* 不同的FP，但可能為(1)新的FP或(2)被不同FP dedup
* 同LPA但出現新的FP
    * 舊的LPA-PPA會被invalid
    * 
* 過程:
    1. check是否LPA已有mapping
    2. Query FPtable內他FP的LPA
        * 如果一樣: 就是原地更新，並且不更新ref
        * 如果不一樣: 更新此FP entry
            * 並將原本LPA的FP entry資訊更新: ref--
            * 如果ref == 1要轉換成PPA
            * 並且更新SMT，將此VPA-PPA的pair刪除
            * 如果ref == 0則將此FP entry刪除
          
#### Details:
1. 當此FP由2變成1的時候，ref到這個PPA的LPA是否要將VPA-PPA消除
2. RM: 每個PPA對應LPA(unique)或VPA(duplicate)
    * PPA: FP, LPA, VPA, duplicate
    * FP剛插入: ref == 1，duplicate = false，放入LPA
    * FP hit: ref從1變成2，duplicate = true，放入VPA
    * FP hit: ref > 2，duplicate已經是true了，且LPA跟VPA都有值
    * FP更新造成ref減少，ref從2變成1，duplicate = false，將VPA變成NO_PPA
    * ref從1變成0，duplicate已經是false，這個PPA也被invalid了
4. (未修正) 同樣的LPA進來，拿到相同FP的狀況
    * 因為還是ref到原本的PPA，是可以不用invalid PPA以及get free page
    * 但為了方便起見，先將原本的PPA invalid，再換新的PPA新增一次
5. VPA轉回PPA的時機：
    * 此LPA要map到新的PPA，且舊的PPA的ref從2變為1的時候
    * 將舊的VPA-PPA的部分刪掉
6. PPA invalid時機：
    * 此LPA要map到新的PPA，且舊的PPA的ref為0的時候
    * GC的時候透過RM找FP再找FP table
-->
