# 2022q1 Homework5 (quiz8)
contributed by < `Kevin-Shih` >

## 測驗 `1`
> [題目描述](https://hackmd.io/@sysprog/linux2022-quiz8/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FHyg5nxO79)
> [完整程式碼: memchr_opt.c](https://gist.github.com/Kevin-Shih/e3b71f3272de6f6123bd59c38aee7655)

**當 length 大於等於 LBLOCKSIZE 時**

unsigned long *asrc = (unsigned long *) src;
unsigned long mask = d << 8 | d;
mask = mask << 16 | mask;
for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
    mask = (mask << i) | mask;

while (length >= LBLOCKSIZE) {
    /* If this word-sized segments contain the search character,
     * then break the loop and resort to the bytewise loop. 
     */
    if (DETECT_CHAR(*asrc, mask))
        break;
    /* If this word-sized segments does not contain the target character,
     * then `asrc` point to next word-sized segments.
     */
    asrc++;
    length -= LBLOCKSIZE;
}

/* If there are fewer than LBLOCKSIZE characters left, then we resort to
 * the bytewise loop.
 */
src = (unsigned char *) asrc;

`asrc` 用於指向欲比較的 `src` 片段，透過轉型為 `unsigned long *` 使其每次只能存取一段 `LBLOCKSIZE` 大小的範圍。 `mask` 則是完全由要偵測的字元 `d` 所構成的 `unsigned long`，for loop 主要是為了產生對應 32-bit 與 64-bit 兩種不同系統的 `mask`。

while loop 顯然是為了每次處理 `LBLOCKSIZE` 大小的關鍵，當該片段中為偵測到目標字元 `d` 時 (`DETECT_CHAR` 回傳 0 時)，`asrc` 會重新指向下個 `LBLOCKSIZE` 大小的片段，由於型態為 `unsigned long *` 故直接加 1 即可移至下個片段的位址，而 `length` 則相應的減去 `LBLOCKSIZE`。

---

## 測驗 `2`
> [題目描述](https://hackmd.io/@sysprog/linux2022-quiz8/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FrkQMKQu7c)

- `DDD` : idx++
next slot, so let idx = idx + 1
- `KKK` : mask + 1
因前面設定 lfr->mask = ringsz - 1 故推論 size = mask +1
- `TTT` : &lfr->ring[tail & mask].idx, __ATOMIC_RELAXED
因前面的 `lfring_enqueue` 有 `lfr->ring[tail & mask].idx = tail;` 的片段，因此推論要檢驗 lfr->ring[tail & mask].idx 與 tail 是否相等。
- `HHH` : head + actual
由 do while loop 中的 Single-consumer 的部份

    if (UNLIKELY(lfr->flags & LFRING_FLAG_SC)) { /* Single-consumer */
        __atomic_store_n(&lfr->head, head + actual, __ATOMIC_RELAXED);
        break;
    }

可知在跳出迴圈前要將 `head + actual` 存入 `&lfr->head`，又依據 `__atomic_compare_exchange_n` 在將 desire (`HHH`) 寫入*ptr (`&lfr->head`) 後會回傳 true ，再加上 `NOT` 後就會跳出 loop，因此 `HHH`= `head + actual`。
> __atomic_compare_exchange_n (type *ptr, type *expected, type desired, bool weak, int success_memorder, int failure_memorder)
> If desired is written into *ptr then true is returned
> --[gcc](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html)

修改後的程式碼：

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 */ idx++;
    }
    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 */ mask + 1;
    
    /* Since we got `lfr->ring[tail & mask].idx = tail;` in the `lfring_enqueue` 
     * function which enqueue elements at tail, so load 
     * `&lfr->ring[tail & mask].idx` which should equal to tail
     */
    while (before(tail, head + size) &&
           /* XXXXX */ __atomic_load_n(&lfr->ring[tail & mask].idx, __ATOMIC_RELAXED) ==
               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 {
        actual = MIN((intptr_t)(tail - head), (intptr_t) n_elems);
        if (UNLIKELY(actual <= 0)) {
            /* Ring buffer is empty, scan for new but unreleased elements */
            tail = find_tail(lfr, head, tail);
            actual = MIN((intptr_t)(tail - head), (intptr_t) n_elems);
            if (actual <= 0)
                return 0;
        }
        for (uint32_t i = 0; i < (uint32_t) actual; i++)
            elems[i] = lfr->ring[(head + i) & mask].ptr;
        smp_fence(LoadStore);                        // Order loads only
        if (UNLIKELY(lfr->flags & LFRING_FLAG_SC)) { /* Single-consumer */
            __atomic_store_n(&lfr->head, head + actual, __ATOMIC_RELAXED);
            break;
        }

        /* else: lock-free multi-consumer */
    } while (!__atomic_compare_exchange_n(
        &lfr->head, &head, /* Updated on failure */
        /* If &lfr->head == &head, then &lfr->head = head + actual 
         * else &head = &lfr->head.
         */
        /* XXXXX */ head + actual,
        /* weak */ false, __ATOMIC_RELAXED, __ATOMIC_RELAXED));
    *index = (uint32_t) head;
    return (uint32_t) actual;
}

此外，`CACHE_LINE` 的大小可透過 `sysconf(_SC_LEVEL1_DCACHE_LINESIZE)` 獲取 L1 dcache line 的大小。
>_SC_LEVEL1_DCACHE_LINESIZE
>Inquire about the line length of the Level 1 data cache.
>On aarch64, the cache line size returned is the minimum data cache line size observable by userspace.
> --[gnu:Constants for sysconf Parameters](http://www.gnu.org/software/libc/manual/html_node/Constants-for-Sysconf.html#index-_005fSC_005fLEVEL1_005fDCACHE_005fLINESIZE)

---

## 測驗 `3`
> [題目描述](https://hackmd.io/@sysprog/linux2022-quiz8/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FBy5JAmOX9)

修改後的 `periodic_routine` 程式碼:

static void periodic_routine(struct work_struct *ws)
{
    if (likely(ws)) // 當 ws 不為 null
        check();
    queue_delayed_work(wq, &dont_trace_task, JIFFIES_DELAY);
    /* 因 dont_trace_init 只呼叫一次 queue_delayed_work ，因此每次執行 periodic_routine
     * 都呼叫一次 queue_delayed_work 來實現重複檢查是否有 process 在 ptracing
     */

kernel 中對於 `task_struct` 成員 `ptraced` 及 `ptrace_entry` 的註釋

/*
 * 'ptraced' is the list of tasks this task is using ptrace() on.
 *
 * This includes both natural children and PTRACE_ATTACH targets.
 * 'ptrace_entry' is this task's link on the p->parent->ptraced list.
 */
struct list_head		ptraced;
struct list_head		ptrace_entry;

結合 `is_tracer()` 的設計以及 `check()` 呼叫時的參數 `&task->ptraced`

/* @return true if the process has tracees */
static bool is_tracer(struct list_head *children)
{
    struct list_head *list;
    list_for_each (list, children) {
        struct task_struct *task =
            list_entry(list, struct task_struct, ptrace_entry);
        if (task)
            return true;
    }
    return false;
}

可以看出迴圈中的 `list` 即是某個 task 的 tracee，`list_entry(list, struct task_struct, ptrace_entry)` 則會回傳該 tracee 對應的 `task_struct` (由註解可知 tracer 的 `ptraced` 會出現在 tracee 的 `ptrace_entry`)。 確認該 tracee 的存在後就可以確定該 task 為 tracer 了。 而在 `kill_tracee()` 中也使用了相同的方式找出該 tracer 所有 tracee 對應的 `task_struct` 並終止該 task。