Long Story of Block - DISCARD

Concept

introduction to DISCARD

DISCARD 的概念其實來自 SSD 裝置。我們知道由于 flash 存儲媒體的特性，SSD 裝置中的一個 block 隻支援 write、erase 操作，而不支援 overwrite 操作。對于一個已經被 write 過的 block，如果需要向這個 block 寫入新的資料，就必須先對該 block 執行 erase 操作，之後再将新的資料寫入這個 block

正是由于這種特性，SSD 裝置必須盡可能及時地對已經 write 過的、但是使用者不需要了的 block 執行 erase 操作，以作備用，不然等到 free block 用完了才執行 erase 操作，為時晚矣

但是 SSD 裝置并不知道哪些 block 是需要的，哪些是不需要的，這些資訊隻有上層的使用者也就是檔案系統知道。例如檔案系統對一個檔案執行删除或 truncate 操作時，那些被删除的資料占用的 block 就是不再需要的，檔案系統必須通過某種方式将這些資訊告訴底層的 SSD 裝置

block 層通過 DISCARD request 的方式來傳遞這些資訊，檔案系統将這些不再需要了的 sector range 封裝為一個 DISCARD request，裝置驅動在接收到這個 DISCARD request 時，同時也就接收到了需要執行 erase 操作的 sector range

DISCARD request

實際上 block layer 支援的 DISCARD request 隻是一個統稱，其可以細分為以下三種 request

REQ_OP_DISCARD
REQ_OP_WRITE_ZEROES
REQ_OP_WRITE_SAME           

這是因為不同的協定實作有各自不同的指令來實作 DISCARD 操作，這些不同的指令實作的效果又存在細微的差别

DISCARD

ATA 實作有 TRIM 指令，對應于 DISCARD，也就是封裝了需要執行 erase 操作的 sector range，裝置接收到該 request 時就會對指定的 sector range 執行 erase 操作

WRITE_ZERO

nvme 實作有 deallocate 指令，類似于 TRIM 指令，對應于 DISCARD；同時還實作有 write zero 指令，對應于 WRITE_ZERO

WRITE_ZERO 與 DISCARD 都是告訴底層裝置哪些 sector range 是不需要了的，裝置可以對這些 sector range 執行 erase 操作，但是差別在于，DISCARD 傳回後從這些 sector range 讀到的值是 undefined 的，而 WRITE_ZERO 傳回後，會確定從這些 sector range 讀到的值是 0

The Write Zeroes command is used to set a range of logical blocks to zero. After successful completion of this command, the value returned by subsequent reads of logical blocks in this range shall be zeroes until a write occurs to this LBA range.

-- NVMe Spec

WRITE_SAME

SCSI 實作有 UNMAP 指令，類似于 TRIM 指令，相當于 DISCARD；此外還實作有 write same 指令，相當于 WRITE_SAME

WRITE_SAME 指令的本意是對指定的 sector range 重複執行寫操作，寫入的資料由傳入的一個 block 大小的 buffer 指定，這樣 sector range 中的每個 block 都會被寫入同樣的内容

WRITE_SAME 指令中有一個 UNMAP bit，當這個 bit 被置位時，這個 WRITE_SAME 指令實際上相當于是執行 UNMAP 指令，同時輸入的 block 大小的 buffer 的内容必須全為 0，此時會對指定的 sector range 執行 erase 操作，同時當 WRITE_SAME 指令傳回後，會確定從這些 sector range 讀到的值是 0

The WRITE SAME(10) command (see table 236) requests that the device server transfer a single logical block from the Data-Out

Buffer and for each LBA in the specified range of LBAs:

a) perform a write operation using the contents of that logical block; or

b) perform an unmap operation.

-- SCSI spec

SCSI supports the WRITE SAME commands to write a LBA sized buffer to many LBAs.

• If the UNMAP bit is set WRITE SAME ask the device to unmap the blocks covered
• Buffer must be all zeros for the UNMAP bit to work.
• Future reads from the LBAs must return all zeros

DISCARD 和 WRTE_ZERO request 都是沒有 payload 的，即所有 bio 的 bio_vec 數組都是空的，此時這些 bio 隻是描述對應的 sector range

但是 WRTE_SAME request 是有 payload 的，此時每個 bio 内有且隻有一個 bio_vec，同時所有 bio 的 bio_vec 都指向同一個 page，這個 page 實際上就是之前介紹的被重複寫入的“block 大小的 buffer”

physical segment of DISCARD

introduction of physical segment of DISCARD

有些 IO controller 支援在單個 DISCARD request 中同時對多個非連續的 sector range 執行 discard 操作，因而每個 request 需要維護一個字段描述該 request 中 sector range 的數量

DISCARD request 實際上複用了 @nr_phys_segments 字段來描述該 request 包含的 sector range 的數量，對應地也複用了 @bio->bi_phys_segments

struct request {
    /*
     * Number of scatter-gather DMA addr+len pairs after
     * physical address coalescing is performed.
     */
    unsigned short nr_phys_segments;
    ...
};           

struct bio {
    /* Number of segments in this BIO after
     * physical address coalescing is performed.
     */
    unsigned int        bi_phys_segments;
    ...
}           

bio calculation

DISCARD bio 不帶有 payload，其 bio_vec 數組為空，此時一個 bio 就隻是描述一段需要執行 discard 操作的 sector range；一個 bio 隻能描述一段 sector range，因而其 @bi_phys_segments 字段的值隻能為 1

bio->bi_phys_segments 字段的值在 bio split 路徑中初始化，其初始值為 1

blk_mq_make_request
    blk_queue_split
        blk_bio_discard_split
            *nsegs = 1           

request calculation

在 bio 封裝為 request 的過程中，DISCARD request 的 @nr_phys_segments 字段被初始化為 1

blk_mq_make_request
    blk_mq_bio_to_request
        blk_init_request_from_bio
            blk_rq_bio_prep
                rq->nr_phys_segments = 1           

前面介紹過，有些 IO controller 支援在單個 DISCARD request 中同時對多個非連續的 sector range 執行 discard 操作，@limits.max_discard_segments 參數就描述了這一限制，即單個 DISCARD request 可以包含的 sector range 數量的上限；如果該參數為 1，則說明單個 DISCARD request 中隻能包含一段連續的 sector range

@limits.max_discard_segments 參數的不同，直接導緻了 request 合并（包括 bio 與 request 合并、requests 之間的合并）過程中行為的差異

@max_discard_segments > 1

首先介紹 @max_discard_segments 大于 1 時的行為，此時一個 request 可以包含多個非連續的 sector range，同時不會對相鄰的兩個 bio 的 sector range 進行合并，而無論這兩個 bio 描述的 sector range 是否連續，此時 req->nr_phys_segments 的值就等同于該 request 中包含的 bio 的數量

為什麼不把 sector range 連續的兩個 bio 合并為一個 sector range 呢？

我想是因為 DISCARD IO 與普通的 READ/WRITE IO 存在差異。普通的 READ/WRITE IO 可能存在比較多的小 IO，将其中實體位址連續的小 IO 合并為一個 physical segment 對于性能提升是有益的；而 DISCARD IO 在下發下來的時候，通常就已經是一個 sector 位址連續的單個的大 IO，此時再嘗試将多個連續的 sector range 合并為一個 sector range，可能受益不大

此外當 @limits.max_discard_segments 參數大于 1 時，IO controller 本身就支援單個 DISCARD request 中包含多個非連續的 sector range，由于 DISCARD IO 通常都是 sector 位址連續的大 IO，因而即使将一個 bio 就視為一個獨立的 sector range，一個 DISCARD request 中包含的 bio 的數量可能都小于 @limits.max_discard_segments 參數的值，因而這個時候執行 sector range 的合并操作，的确受益不大

bio & request merge

此時 request 與 bio 合并過程中，req->nr_phys_segments 的值總是直接加 1，而無論新合入的 bio 描述的 sector range 是否與之前的 sector range 相連續

blk_mq_bio_list_merge
    bio_attempt_discard_merge
        req->nr_phys_segments += 1           

同時當 @limits.max_discard_segments 參數大于 1 時，對于 DISCARD request 來說，是不存在 requests 之間的合并的

@max_discard_segments == 1

而當 @max_discard_segments 參數等于 1 時，其行為就複雜很多。此時一個 request 仍然可以包含多個 bio，但是這些 bio 的 sector range 必須是連續的，即多個 bio 仍然組成一個連續的 sector range，也就是說這個時候是會對相鄰的兩個 bio 的 sector range 進行合并操作的

為什麼會存在這種差異呢？我認為主要是 @max_discard_segments 參數等于 1 時，一個 DISCARD request 隻能包含一個連續的 sector range，相當于是 "sector range" 資源比較匮乏，這個時候将 sector 位址連續的多個 bio 合并為一個連續的 sector range，相當于是一種優化

此時 request 與 bio 合并過程中，@req->nr_phys_segments 字段會加上合并的 @bio->bi_phys_segments 的值，由于 DISCARD bio 的 @bi_phys_segments 字段的值均為 1，因而 @req->nr_phys_segments 字段的值實際上也就是加 1

blk_mq_bio_list_merge
    bio_attempt_back_merge
        ll_back_merge_fn
            ll_new_hw_segment
                req->nr_phys_segments += bio->bi_phys_segments           

因而需要注意的是，無論 @max_discard_segments 參數是否大于 1，request->nr_phys_segments 的值實際上都會随着 request 中包含的 bio 數量的增加而增加，因而嚴格意義上 @req->nr_phys_segments 并不是描述 request 中包含的非連續 sector range 的數量

requests merge

值得一提的是，當 @max_discard_segments 參數等于 1 時，bio 與 request 的合并走的是 normal READ/WRITE request 合并的路徑，也就是 front/back merge 的路徑，這也就直接導緻了會走到 requests 合并的路徑

在 4.19 版本核心中，兩個 DISCARD requests 合并過程中，合并後的 @req->nr_phys_segments 會減 1，這也就直接導緻了合并後 @req->nr_phys_segments 的值比 request 中包含的 bio 的數量小 1

ll_merge_requests_fn
    total_phys_segments = req->nr_phys_segments + next->nr_phys_segments
    if (blk_phys_contig_segment()) total_phys_segments--
    req->nr_phys_segments = total_phys_segments           

device driver calculation

需要注意的是，以上描述的 @req->nr_phys_segments 的計算規則都是 block layer 的行為

而 nvme/virtio-blk driver 在處理 DISCARD request 時，會期待 @req->nr_phys_segments 的值與 request 中包含的 bio 數量相等

virtio_queue_rq
    virtblk_setup_discard_write_zeroes
        segments = blk_rq_nr_discard_segments(req)
        range = kmalloc_array(segments, ...)
        __rq_for_each_bio(bio, req) {
            range[n].sector = ;
            ...
        }