# [2022q1](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 8 週測驗題
###### tags: `linux2022`

### 測驗 `2`

考慮 `lfring` 是個 lock-free ring buffer 實作，並支援 multiple-producer/multiple-consumer (MPMC) 的情境。測試程式的參考輸出:

$ ./lfring 
testing MPMC lock-free ring
testing MPSC lock-free ring
testing SPMC lock-free ring
testing SPSC lock-free ring

執行過程不會觸發任何 `assert` 失敗。

`lfring` 目前只支援 x86-64 架構，可在 Linux 和 macOS 執行，程式碼可見 [gist](https://gist.github.com/jserv/f810c45ad4423f406f9e0dbe9dabadc9) (部分程式碼隱蔽)

需要補完的函式列表: (留意 `DDD`, `KKK`, `TTT`, `HHH` 等處)

static inline ringidx_t cond_reload(ringidx_t idx, const ringidx_t *loc)
{
    ringidx_t fresh = __atomic_load_n(loc, __ATOMIC_RELAXED);
    if (before(idx, fresh)) { /* fresh is after idx, use this instead */
        idx = fresh;
    } else { /* Continue with next slot */
	/* XXXXX */ DDD;
    }
    return idx;
}

static inline ringidx_t find_tail(lfring_t *lfr, ringidx_t head, ringidx_t tail)
{
    if (lfr->flags & LFRING_FLAG_SP) /* single-producer enqueue */
        return __atomic_load_n(&lfr->tail, __ATOMIC_ACQUIRE);

    /* Multi-producer enqueue.
     * Scan ring for new elements that have been written but not released.
     */
    ringidx_t mask = lfr->mask;
    ringidx_t size = /* XXXXX */ KKK;
    while (before(tail, head + size) &&
           __atomic_load_n(/* XXXXX */ TTT) ==
               tail)
        tail++;
    tail = cond_update(&lfr->tail, tail);
    return tail;
}

uint32_t lfring_dequeue(lfring_t *lfr,
                        void **restrict elems,
                        uint32_t n_elems,
                        uint32_t *index)
{
    ringidx_t mask = lfr->mask;
    intptr_t actual;
    ringidx_t head = __atomic_load_n(&lfr->head, __ATOMIC_RELAXED);
    ringidx_t tail = __atomic_load_n(&lfr->tail, __ATOMIC_ACQUIRE);
    do { /* skipped */
    } while (!__atomic_compare_exchange_n(
        &lfr->head, &head, /* Updated on failure */
        /* XXXXX */ HHH,
        /* weak */ false, __ATOMIC_RELAXED, __ATOMIC_RELAXED));
    *index = (uint32_t) head;
    return (uint32_t) actual;
}

請補完程式碼，使得執行符合預期。作答規範:
* 儘量以最精簡的程式碼撰寫
* 儘量撰寫程式註解

延伸閱讀:
* [An introduction to lockless algorithms](https://lwn.net/Articles/844224/)
* [Lockless algorithms for mere mortals](https://lwn.net/Articles/827180/)
* [Lockless patterns: an introduction to compare-and-swap](https://lwn.net/Articles/847973/)

:::success
延伸問題:
1. 解釋上述程式碼運作原理，搭配閱讀 [DPDK: Ring Library](https://doc.dpdk.org/guides/prog_guide/ring_lib.html) 解說，儘量引入圖解和強調 MPMC 的考量
2. 提出改進策略並著手實作
3. 研讀 Linux 核心 [kfifo](https://www.kernel.org/doc/htmldocs/kernel-api/kfifo.html) 文件，搭配 [kfifo-examples](https://github.com/sysprog21/kfifo-examples) 測試，以 git 取得 [linux](https://github.com/torvalds/linux) 程式碼工作副本，觀察 `git log include/linux/kfifo.h lib/kfifo.c` 並觀察修改記錄
* 留意 `spin_unlock_irqrestore` 的使用
* 解釋 commit 7e10505 的 race condition 成因
4. 將 `lfring` 移植到 Linux 核心，並提供對應的測試及效能評比程式
:::