contributed by < chiehen
>
linux2021
當 cache miss 發生時, cache 會將 cache line 大小的資料從 memory 移到 cache,將變數做 cache line alignment 可減少 cache miss,進而增進效能。
使用 __attribute__
進行 alignment
根據 gcc 文件
The keyword attribute allows you to specify special properties of variables, function parameters, or structure, union, and, in C++, class members.
The aligned attribute specifies a minimum alignment for the variable or structure field, measured in bytes.
For example, the declaration: int x attribute ((aligned (16))) = 0; causes the compiler to allocate the global variable x on a 16-byte boundary.
因此透過 attribute ((aligned (n))) 可以讓編譯器對變數依我們指定的大小自動做 alignment。
為了做 cache alignment 將配置的記憶體大小調整為 cache line 的倍數,因此將原本的大小進位到 cache line 的倍數
加數的部份可計算出val
到下一個倍數的差
從二進位來看, 差為原本的數在小於 align 的 bit 為 0 的地方須為 1,並再加 1。
假設 val = 10 = 10102, align = 8 = 10002:
則要關心的 bit 為後三個 bit , 而進行 & align -1
可以達成此目標,
而 val 在後三個 bit 為 010 可以看出要進位到 16 = 100002 需要 1012 + 0012, 而利用二補數-x = ~x+1
, 則可以計算出到下一個倍數的差在這個例子為 1102 = 6
另一個進位的方法:
使用平台
移除 cache alignment 相關程式碼,觀看記憶體的配置差別
沒有 cacheline aligment:
ringbuffer 位址
可看出 prod與 cons, cons 與 ring 相差了 20 bytes, ring size 也並非 cache line(64) 的倍數
有 cacheline aligment:
可發現結構間相距 64 bytes, 而 ring size 也是 cache line 的倍數
比較兩者效能差異
使用 perf 察看執行時間及 cache miss 等表現
不如預期,數字上並沒有看出有顯著差異。
當 object enqueue 後會超過 water mark 時, 回傳 Quota exceeded 的 error code
((mask + 1) - free_entries + n) 計算這次 enqueue 後所被使用的 entries 數量,如果超過則回傳 -EDQUOT
猜測 Quota exceeded 是為了重新配置 ringbuffer
經過與老師的討論後,發現原本的猜想並不正確,並不符合原先使用 circular buffer 這種資料結構的使用情境。
這篇 The design and implementation of a lock-free ring-buffer with contiguous reservations 便講解了 circular buffer 在實際世界中的角色和 watermark 的作用。
在 embedded systems 中因為記憶體特別有限,通常不會使用 heap 來配置記憶體,而是會靜態配置或使用 stack 配置。而Circular Buffer 可以事先確定大小的特性便很適合在這種系統,並且在這些系統中也常用為模擬動態記憶體空間。
因此可知道 watermark 如果是為了在執行時期改變 ringuffer 的大小是不符合使用情境的。
實際上,watermark 的作用是為了能讓一段資料能以連續的方式放入記憶體。而 Direct Memory access(DMA) 這個常見嵌入式系統的機制就需要這個特性。DMA 是外部裝置 (Peripheral) 不透過 CPU 能自動讀寫主記憶體的行為,這個行為可以節省大量的 CPU 時間,對於通常是單核的嵌入式系統特別重要。但因為 DMA 傳輸只認得資料起始位置及資料長度,並不能理解 circular buffer 中 wrap around 的機制,因此需要 watermark 協助。
當要放入的資料長度大(藍色區域)於 circular buffer 尾段的空間
則用 watermark 標註 valid data 的位置,將資料從 buffer 開頭開始放入,如下圖所示:
在 dequeue 時計算:
在 enqueue 時,
如下圖
(以下示範 index 為 unsigned 16-bit integers)
used_entries:
已使剩餘空間為用空間為綠色區域,因此很明顯的便是 producer tail(pt) - consumer head(ch)
。
使用 producer tail 才可確保元素已被放入 buffer。
free_entries:
從圖片上來看,可知剩餘空間為該圓角矩形剩下的黃色區域,因此將 consumer tail(ct) + mask
可得到在下個圓角矩形的相對位置,所以再將此數減去 producer head(ch)
便可以得到兩段黃色區域的長度,也就是剩餘空間的長度。
使用 consumer tail 才可確保元素已被拿出 buffer,使用 producer head 才能得到這個 producer 要操作的正確位置。
以下解說 16-bit modulo
C99 §6.2.5/9:
A computation involving unsigned operands can never overflow,because a result that cannot be represented by the resulting unsigned integer type is reduced modulo to the number that is one greater than the largest value that can be represented by the resulting type.
因此當進行計算時, 如果結果無法以這個型態儲存, 則會對其進行 Modular arithmetic, 則
UINT_MAX + 1 == 0
0 - 1 == UINT_MAX
因此在下圖範例中
當進行 pt - ch
時,會將結果自動 modulo 216
利用 size 及 4 是 2 的冪:
第 4 行中prod_head & mask
相當於 prod_head % size
第 7 行n & ((~(unsigned) 0x3
等同 floor(n/4)
第 14 行n & 0x3
為 n%4
常見的 circular buffer 只儲存 (size - 1) 個物件,當 start(consumer) - end(producer) == 1 時,代表 buffer 已滿。當 start 小於 end 時, 會進行 32-bit modulo, 因此要做 mod size, 計算出的值才會在 [0-size] 之間。
當 buffer 的 start 跟 end 指向同個位置時代表 buffer 是空的。
不明白為何在測試程式的部份, 先將要放入值 casting void** 再做 dereference
因此將程式改為
結果發現程式放入的便不會如預期的為 [0,1…63]的地址
使用 gdb 查看發現更改動的程式
在每次的迴圈中, 放入的都為值 0x7fffffffdcd0
而原來的程式, 經過 casting 與 deference 實際放入的值為遞增
將原有碼程式擴展為 single producer + multiple consumer (SPMC)
利用 consumer 的 head 和 tail 達到多個 consumer的 concurrency, 複製前先更新 head 標注將要複製, 複製後更新 tail 標示完成複製
參考DPDK Ring Library
測試程式 pc-test.c:
執行結果:
在 75 行時回傳值不為 0, 代表函式回傳 -ENOENT, 也就是 n > entries
有可能是因為有大於 ringbuffer 中 entries 數量的 consumer 通過第 71 行
更改測試程式 pc_test.c:
確認不會有兩個拿同個號碼牌(consumer_count)的 thread 執行 dequeue
執行結果:
依然在在 75 行時回傳值不為 0
現在的問題為拿不同 consumer_count 的 thread 同時通過 ringbuf_is_empty 的檢查。
如何保證 !ringbuf_is_empty 在 dequeue 時仍成立