---
tags: linux2022
---

# 2022q1 Homework8 (quiz8)
2022-04-04
contributed by < `bebo1010` >
[Github repository link](https://github.com/bebo1010/linux2022-quiz8)
## 測驗一
實際行為應該和 [lib/string.c](https://github.com/torvalds/linux/blob/master/lib/string.c) 中的 [memchr](https://man7.org/linux/man-pages/man3/memchr.3.html) 相同，要能做到找出第一個相符的字元位置。
我大致上讀了一下程式碼後，看到了 mask 的做法，就意識到應該是一次比對多個 byte 是否與 mask (目標字元) 相同。
實際上再去了解後，發現做法是一次比對 8 個字元是否和目標字元相同。

以下內容是我的實作，使用 DETECT_CHAR macro 幫我找出是否這 8 個字元中含有目標字元
* 如果有找到的話，在這八個字元中用 linear scan 的方式從頭開始找起字元的實際位置
* 如果沒有找到的話，把指標頭往後移動八個字元，並把剩餘要找的字元數減八

while (length >= LBLOCKSIZE) {
      /* XXXXX: Your implementation should appear here */
      if (DETECT_CHAR(*asrc, mask) != 0) { // char in mask detected
        for (int i = 0; i < 8; i++) {      // linear scan in this 8 characters
          if (*(src + i) == d)
            return (void *)(src + i);
        }
      } else { // char in mask not detected
        src = src + 8;
        asrc = (unsigned long *)src;
        length = length - 8;
      }
    }

## 測驗二
看了許久後，還是看不出個所以然來，我也不確定這份程式碼是要做出什麼東西。
我目前猜測這個 `struct lfring` 應該是一個暫存的區塊，存放從 producer 跑出的東西給 consumer 用掉。
但是這個 struct 並不是一個 linked list，那這個 struct 是如何去記錄目前的每一個東西?
裡面有個 function 是 `before()`，可是我很困惑這個 `before()` 放入的 index 值有沒有意義，如果 `struct lfring` 有被宣告為陣列那這個 index 才可能有意義做比較

後來很像看到了 `struct lfring` 中有個 `struct element`，而 `struct element` 有 `void *ptr`，這部分就是 linked list 嗎? 那為何存取 `ptr` 時都會用到 `& mask` 的部分?

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 */ return cond_reload(fresh, &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 */ lfr->tail;
  while (before(tail, head + size) &&
         __atomic_load_n(/* XXXXX */ &lfr->tail, __ATOMIC_ACQUIRE) == 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 */
      /* XXXXX */ &mask, // desired position, write here if equal
      /* weak */ false, __ATOMIC_RELAXED, __ATOMIC_RELAXED));
  *index = (uint32_t)head;
  return (uint32_t)actual;
}

## 測驗三
我嘗試著去看懂這個程式碼，但我看不懂 `periodic_routine` 的目的到底是什麼
`periodic_routine` 中的 `if(likely(X))` 是假設 `X` 是很容易發生的事情，但是這個 `X` 我找不到一個可能填入的東西，要找到這個 process 是不是 tracer 只能從 `task_struct` 內找，而不是 `work_struct`。
在前面的條件成立後就會呼叫 `check()`，而 `check()` 的目的似乎是找出每個 `process` 是否是 tracer，如果是 tracer 的話就把底下的 tracee 全部 kill 掉後再把自己 kill 掉。
剩下的部分我已經找不出線索可以繼續找答案了，也很有可能是我錯過了什麼線索。