---
tags: linux2024
---

# [2024q1](http://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) (部分遮蔽)

編譯方式:

$ 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 名稱

---

### 測驗 `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` 中，先定義二個結構體。

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 內的節點。

編譯方式:

$ 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 為系統呼叫名稱