2024q1 第 10 週測驗題

--- tags: linux2024 --- # [2024q1](https://wiki.csie.ncku.edu.tw/linux/schedule) 第 10 週測驗題 :::info 目的: 檢驗學員對 [Atomics 操作](https://hackmd.io/@sysprog/concurrency-atomics), probabilistic data structure, [Hazard pointer](https://hackmd.io/@sysprog/concurrency-hazard-pointer) 的認知 ::: ==[作答表單: 測驗 1](https://docs.google.com/forms/d/e/1FAIpQLSdIgW3oC-Hvrjk4sbfFoLaXfUyWFbddqukqs5IzuDBydMxj0w/viewform)== (針對 Linux 核心「設計」課程) ==[作答表單: 測驗 2-3](https://docs.google.com/forms/d/e/1FAIpQLSdZW9TeBt7EopY_PcY-yzB4rl0UiTiC9qgkstce-V1NiogVPA/viewform)== (針對 Linux 核心「實作」課程) ### 測驗 `1` 延伸[第 6 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz6)涵蓋的 [bloom filter](https://en.wikipedia.org/wiki/Bloom_filter)，我們想發展得以在並行環境運作的程式碼。理論與實際性能對比，其中 k=2 與 n=2^28，理論錯誤率採用公式 $(1-e^{\dfrac{-k \times n}{b}})^k$ 計算得出。使用 k=2 是因為可將一個 64 位元雜湊分割成兩部分來來實作。要達到約 0.05 的錯誤率，需要設定 $n=2^{28}$。雜湊函數使用 [xxHash](https://github.com/Cyan4973/xxHash) [原始程式碼](https://gist.github.com/jserv/f8faef1dc23ed88f33f72a225271bf5e) (部分遮蔽) 編譯方式: ```shell $ wget https://raw.githubusercontent.com/Cyan4973/xxHash/dev/xxhash.h $ gcc -Wall -std=gnu11 -g -O2 -I. -o bench bench.c bloom.c ``` 參考執行輸出: ``` $ ./bench 50958386 ops/s ``` 作答規範: * AAAA 是以 `atomic_` 開頭的 C11 Atomics 函式 * BBBB 呼叫 `get` 函式 * CCCC 是 signal 名稱 :::success 延伸問題: 1. 解釋上述程式碼運作原理，探討其能否滿足 thread-safe 要求 2. 倘若上述程式碼無法通過 ThreadSanitizer，提出修正 ::: --- ### 測驗 `2` 〈[並行程式設計: Hazard pointer](https://hackmd.io/@sysprog/concurrency-hazard-pointer)〉提到: > 在並行程式設計中，當我們在存取共用的記憶體物件時，需要考慮到其他執行緒是否有可能也正在存取同一個物件，若要釋放該記憶體物件時，不考慮這個問題，會引發嚴重的後果，例如 dangling pointer。 > > 使用 mutex 是最簡單且直觀的方法：存取共用記憶體時，acquire lock 即可保證沒有其他執行緒正在存取同一物件，也就可安全地釋放記憶體。但若我們正在存取的是一種 lock-free 資料結構，當然就不能恣意地使用 lock，因為會違反 lock-free 特性，即無論任何執行緒失敗，其他執行緒都能可繼續執行。於是乎，我們需要某種同為 lock-free 的記憶體物件回收機制。 `lfq` 嘗試實作精簡的並行佇列 (concurrent queue)，運用 hazard pointer 來釋放並行處理過程中的記憶體，[原始程式碼](https://gist.github.com/jserv/128b735e8e73846d38bf1e98ba553607) (部分遮蔽)。在 `lfq.h` 中，先定義二個結構體。 ```c struct lfq_node { void *data; union { struct lfq_node *next; struct lfq_node *free_next; }; bool can_free; }; struct lfq_ctx { alignas(64) struct lfq_node *head; int count; struct lfq_node **HP; /* hazard pointers */ int *tid_map; bool is_freeing; struct lfq_node *fph, *fpt; /* free pool head/tail */ /* FIXME: get rid of struct. Make it configurable */ int MAX_HP_SIZE; /* avoid cacheline contention */ alignas(64) struct lfq_node *tail; }; ``` `struct lfq_node` 是 lock-free queue node 的結構，其中除了資料以及代表能否 free 的一個 bool 以外，還嵌入 union 的型別去儲存 `next` 及 `free_next`，`next` 是佇列中的下一個節點，`free_next` 則是 free pool 中的下個節點。 `struct lfq_ctx` 是 lock-free queue handler 的結構，儲存佇列及 free pool 的頭尾，及 tid 的 map，還有個 bool 型態的變數用來確認是否正在做 free 的動作，此外，也儲存 hazard pointers 和他的最大長度。 `lfq_enqueue` 的功能為推入 (push) 資料進入佇列中，作法是將佇列的尾端替換成 `insert_node`，再將原先舊尾端 `old_tail` 的 `next` 指向 `insert_node`。 `lfq_dequeue` 的功能為將資料從佇列中取出 (pop)，首先，會先透過 `alloc_tid` 取得 tid ，如果順利取得非 `-1` 的值，就會透過 `lfq_dequeue_tid` 去做 pop，在 `lfq_dequeue_tid` 中，會先將要 pop 的 `old_head` 存入 `ctx->HP[tid]` 之中，然後將佇列的 `head` 替換成 `new_head` 也就是 `old_head->next`，完成後再將 `ctx->HP[tid]` 重設回 0，再對 `old_head` 做 `safe_free`。若節點能被 free 且不在 hazard pointers 內，`safe_free` 函式嘗試釋放已配置的資源，否則就藉由 `insert_pool` 只將節點加入 free pool，倘若 `CAS(&ctx->is_freeing, 0, 1)` 操作成功的話，就能確實地釋放節點佔用的記憶體空間，但若失敗，就一樣只將節點加入 free pool，最後呼叫 `free_pool` 以嘗試釋放 free pool 內的節點。編譯方式: ```shell $ gcc -std=gnu99 -O3 -Wall -Wextra -o test_p1c1 -D MAX_PRODUCER=1 -D MAX_CONSUMER=1 lfq.c test.c -lpthread ``` 這個實作應該要能夠支援以下組態: * ` -D MAX_PRODUCER=4 -D MAX_CONSUMER=4` * `-D MAX_PRODUCER=100 -D MAX_CONSUMER=10` * `-D MAX_PRODUCER=10 -D MAX_CONSUMER=100` 預期輸出: ``` Producer thread [140583962404608] exited! Still 0 running... Consumer thread [140583970797312] exited 0 Total push 500000 elements, pop 500000 elements. freelist=1, clean = 0 Test PASS!! ``` 補完程式碼，使其運作符合預期。作答規範: * `AAAA`, `BBBB`, `CCCC` 均為傳入 `atomic_compare_exchange_strong` 的參數，採用作業一規範的程式碼書寫風格延伸閱讀: * [Experiments on Concurrent Queue](https://hackmd.io/@butastur/concurrent-queue) * [concurrent-ll (2022)](https://hackmd.io/@kdnvt/concurrent-ll-2022) :::success 延伸問題: 1. 解釋上述程式碼運作原理，程式碼參照論文〈[A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue](https://drops.dagstuhl.de/opus/volltexte/2019/11335/pdf/LIPIcs-DISC-2019-28.pdf)〉提及的 SCQ (Scalable Circular Queue) 2. 比照 [rcu-list](https://github.com/sysprog21/concurrent-programs/tree/master/rcu-list) 的實作手法，藉由 [thread-rcu](https://github.com/sysprog21/concurrent-programs/tree/master/thread-rcu) 來改寫上述使用到 hazard pointer (HP) 的場景，比較效能落差並解讀 3. 以 [userspace RCU](https://hackmd.io/@sysprog/ry_6RHgS3) 改寫上述程式碼並探討效能表現 4. 綜合上述實驗，提出改進 lfq 效能的方案 5. 在 Linux 核心找出類似 lfq 需求的程式碼和應用場景 ::: --- ### 測驗 `3` > 對應到 [並行程式設計: Thread Pool 實作和改進](https://hackmd.io/@sysprog/concurrency-thread-pool) 和 [Linux 核心設計: 針對事件驅動的 I/O 模型演化](https://hackmd.io/@sysprog/linux-io-model) `httpd` 是個運用 thread pool 和 epoll 系統呼叫的網頁伺服器，[原始程式碼](https://gist.github.com/jserv/ec1475e380517d829187084ae74979e7) (部分遮蔽)。書寫規範： * DDDD 為表示式 * EEEE 為系統呼叫名稱 :::success 延伸問題: 1. 解釋上述程式碼運作原理，探討其能否滿足 thread-safe 要求 2. 倘若上述程式碼無法通過 ThreadSanitizer，提出修正 3. 評估上述 httpd 的性能表現 :::