2022q1 第 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 (部分程式碼隱蔽)

需要補完的函式列表: (留意 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
• Lockless algorithms for mere mortals
• Lockless patterns: an introduction to compare-and-swap

延伸問題:

1. 解釋上述程式碼運作原理，搭配閱讀 DPDK: Ring Library 解說，儘量引入圖解和強調 MPMC 的考量
2. 提出改進策略並著手實作
3. 研讀 Linux 核心 kfifo 文件，搭配 kfifo-examples 測試，以 git 取得 linux 程式碼工作副本，觀察 git log include/linux/kfifo.h lib/kfifo.c 並觀察修改記錄
   • 留意 spin_unlock_irqrestore 的使用
   • 解釋 commit 7e10505 的 race condition 成因
4. 將 lfring 移植到 Linux 核心，並提供對應的測試及效能評比程式