Linux IO

Buffered IO, Direct IO, mmap

Buffered IO

Page Cache 頁緩存

• Page Cache: 是在內存的一塊區域，儲存文件IO，可能隨時被 OS Evict 掉，但如果讀的 chunk 在 cache 的話，就不用去 disk access，可以得到 DRAM throughput (>20GB/s)。
• 有幾種情況資料會存在 Page Cache，一個是不久之前曾經讀取過，另外一個是主動調用 readahead()。
• 一般為了提高讀寫效率，會採用頁緩存，在讀取文件時，需要先將文件從 disk 搬到頁緩存中，但頁緩存屬於 kernel space，所以用戶不能夠直接 access，所以需要再把頁緩存搬到內存對應的用戶空間，造成了兩次複製，而 mmap 只需要一次。
• 可以用 echo 3 > drop_cache 把 cache/buffer 清除。

readahead()

• readahead 是 Linux 核心的 system call，可以觸發把文件 prefetch 到 Page Cache 中。如果在 read 之前，先提前調用 readahead，可以大大增加 read 的 performance。

read_ahead_kb

• This setting controls how much extra data the operating system reads from disk when performing I/O operations.
• OS 會根據 heuristic readahead algorithm 來決定到多讀多少 page 但最大就是頂到 read_ahead_kb。
• 即便是 read() or mmap()，readahead 還是會起作用，手機一般預設 RA 是 128KB，RA 太大有機會導致 memory 負擔而且可能會和 disk 多發不必要的 request。

read/fread

• Read: 如果要 user space 要讀 data，要先從 disk 到 page cache，再進系內存複製到 vm 對應的 physical address，如下圖：

read() source

• 低級IO：open/read/write 是 system call 直接調用 INT，每次都會進行 user/kernel space 的切換，沒有緩衝(Unbuffered)，使用的是 int 型態的 file descriptor，定義在 fcntl.h，只能讀 binary，且可以開 dev 設備文件。
• 高級IO：fopen/fread/write 是 c 的函數，內建緩衝，不會每次都會呼叫 system call，使用的是 FILE 型態的 file pointer，定義在 sdtio.h。
• 如果用 read，速度取決於 chunk 的大小，如果 chunk 很小，每次都要從 進 kernel space 並從 disk 讀出。
• 如果用 fread，系統會在內存自動 buffer，可以減少訪問 disk 的次數，但會增加內存的用量。
• 理論上，在 Sequential access 的條件下，fread 會比 read 快不少，但在 chunk 很大的情況下，兩者效能差異不大，Random access 時，fread 有可能 load 很多不必要的 data 到內存。
• 如果 read 很大的 chunks，那 OS read_ahead_kb 的功效就會不顯著，例如每次讀 2MB chunks，RA 128kb 和 4096kb 實測起來的 bandwidth 就差不多。因為 ufs 的 packet size 就是 512kb (sda/queue/max_sector_kb)，所以如果都送 512kb，而且有把 ufs內的 32 個 read command queue 塞滿，那就可以達到很高的 bandwidth。

ifstream

• ifs 是 C++ std 的函數庫，效能和 fread 差不多，但比較像 object-oriented flavor。
• ifstreambug_iterator 會 byte by byte 的讀檔，即便實作可能有 buffer 但效能還是極差。

Direct IO (O_DIRECT)

• 在 open 時下的參數，允許用戶直接繞過 Linux kernel’s caches (Page Cache) 直接從用戶空間傳遞接收 data 到 disk。
• 優點：可以減少複製。
• 缺點：可能降低性能，kernel 對於緩存做的優化像是 read_ahead 就不會起作用。

Source

• O_DIRECT 需要 address alignmen，如果是 16 bytes aligment，那 address 用 hex 表示結尾必定是 0，如果是 4096 bytes aligment，那後三位必定是 0，可以透過 posix_memalign 或是自行對齊。除了 buffer 要 alignment，連 read size 都需要 alignment。

int pagesize = getpagesize();
char *realbuff = malloc(BUFFER_SIZE + pagesize);
char *alignedbuff = ((((int unsigned)realbuff + pagesize - 1) / pagesize) * pagesize);

mmap

• mmap() 可以直接對 page cache 進行操作，直接透過 pointer 讀寫 page cache，減少系統調用和內存複製，如下圖：

mmap() source

• 直接 map 文件或設備到 process 的虛擬記憶體上的 system call，可以不用透過 read/write system call 就可以直接 access 文件。
• mmap 的缺點是在 loading data 時會觸發 page fault，也是額外的開銷，所以性能不一定會比 read 好，因為內存複製的時間其實也很快；並且建立 mapping table 也會造成開銷。
• mmap 只會創造對應關係，並沒有把文件複製到內存，當 process 對這塊 vm 進行 access，觸發 page fault，才會將文件內容複製到內存中。
• 透過內存讀寫取代 I/O 讀寫，提高文件讀寫的效率。
• mmap 映射的內存，可以跨 process 共用，但是有可能產生 race condition，所以必須在 user space 自行加鎖解決。

https://zhuanlan.zhihu.com/p/67894878

• 如果是 MAP_PRIVATE 時，如果其他用戶要讀取，則會透過 Copy On Write (COW) 的機制，當進程要修改 page 的內容，則會觸發 copy 一份到內存給其他 process 使用，而 page cache 的修改也不會被寫回 disk。Linux Dynamic Loading 就是透過 mmap(MAP_PRIVATE) 來實作的。

https://zhuanlan.zhihu.com/p/67894878

• 透過 msync() 可以將內存的內容寫回硬碟，munmap() 可以將內存的記憶體釋放。

mmap 補充

• 通常來說(沒下 MAP_POPULATE prefault)，只會分配一段 VMA (Virutal memory area)，紀錄 VMA 和檔案的關係，並不會進行實際的 mapping，後續的分配 physical page、copy file data、創建 MMU mapping，這些是在 page fault 觸發時才會進行。
• VMA 就是 process 裡面的一段連續的 virtual memory area block (每個 process address 都是獨立的)，一個 process 可以有多個 VMAs，分別存 code / lib / file 等等。連續的是 VM 不是物理頁。
• 一段 VMA 裡面包含多個 Pages，Page (物理頁) 是 kenerl memory 管理的最小單位 (常見 4 or 8 KiB )，每個 Page 都被記錄 Page Table 裡面的 Entry (PTE)，所以一個 VMA 包含多個 PTEs。
• VMA 創建後會被插入到 mm->mm_rb 紅黑樹和 mm->mmap 鏈表中。

MMU mapping

• MMU 是一個硬體，提供 CPU 訪問 memory，MMU 會建立 Process Page Table in RAM，然後用一個 pointer register (PTPR) 指向 table 起點，Virtual Address 分成兩部分 (Table Index 和 Offset)，Offset 和 Page Table Entry 需要的 bit 相同 (12bit)，所以在 32bit 的系統中就有 20bit 的 entry (4KB 連續物理記憶體)。轉換後的 physical address 後半 offset 直接從 virtual address 貼上。

https://www.youtube.com/watch?v=AKGtJAi4wGo

可以變成 2 Level Page Translate，這樣 4KB 的 Page Table memory 就不用連續。

https://www.youtube.com/watch?v=AKGtJAi4wGo

Page Fault

https://www.geeksforgeeks.org/page-fault-handling-in-operating-system/

Storage Stack

https://www.thomas-krenn.com/en/wiki/Linux_Storage_Stack_Diagram

Source

Buffer 宣告

std::string

• std 的 capacity 和 size 的定義是，capacity 是 realloc 前可用空間，size 是容器真實戰用的空間。reserve() 可以調整 capacity，resize() 可以調整 size。
• 實際測試std::string data(BUFF_SIZE, 0)和std::string data; data.resize(BUFF_SIZE)會真的占用 physical memory。
• std::string data; data.reserve(BUFF_SIZE)要等到真的開始寫之後才會開始占用記憶體。
• 如果 std::string 一開始不先指定大小，如果讀一個超大的檔案，有可能會需要 realloc 更大的空間，記憶體搬動會影響效能。

char *data = (char*)malloc(BUFF_SIZE);

• 在 malloc 時，其實 logical memory 不會開始占用 physical memory，而是等到真的開始寫入的時，才會開始使用，但不需要重新搬移。

Reference

• https://www.twblogs.net/a/5b7d35a42b71770a43de45b3
• https://lemire.me/blog/2012/06/26/which-is-fastest-read-fread-ifstream-or-mmap/
• https://kknews.cc/zh-tw/news/4xyqyx2.html
• https://www.thomas-krenn.com/en/wiki/Linux_Storage_Stack_Diagram
• https://zhuanlan.zhihu.com/p/67894878
• https://www.0xffffff.org/2017/05/01/41-linux-io/