# 2024q1 Homework2 (quiz1+2)
contributed by < [Ackerman666](https://github.com/Ackerman666) >

## 第二週測驗題

### [測驗 `3`](https://hackmd.io/@sysprog/linux2024-quiz2)

### 程式碼運作原理

#### `__ffs`
尋找 `word` 的 first set (位元從右至左，第一個為1的位置)

程式邏輯會將尚未檢查的 bits 之下半部做 mask
1. 如果結果為 0 ，代表 first set bit會出現在上半部 -> 將 `num` 增加，並對 `word` 做 right shift
> 如 word = 0xf000000000000000，在做第一次檢查 `word & 0xffffffff` 結果為 0
> 因此得知 first set bit 在上半部，因此將 `num += 32` and `word >>= 32`
> 之後再將位移過後的 `word` 做後續相同的檢查
2. 如果結果不為 0 ，代表 first set bit出現在下半部，則再繼續往下半部的下半部來檢查

static inline unsigned long __ffs(unsigned long word)
{
    int num = 0;

#if BITS_PER_LONG == 64
    if ((word & 0xffffffff) == 0) {
        num += 32;
        word >>= 32;
    }
#endif
    if ((word & 0xffff) == 0) {
        num += 16;
        word >>= 16;
    }
    if ((word & 0xff) == 0) {
        num += 8;
        word >>= 8;
    }
    if ((word & 0xf) == 0) {
        num += 4;
        word >>= 4;
    }
    if ((word & 0x3) == 0) {
        num += 2;
        word >>= 2;
    }
    if ((word & 0x1) == 0)
        num += 1;
    return num;
}

:::warning
TODO: 改寫成其他形式。
> Done
:::

可將多個判別式濃縮在同個迴圈處理來簡化程式篇幅
迴圈內的處理邏輯和原版程式差不多

講解如何形成 `mask`
> 假設現在迴圈中 `i` 值為 4，那麼 `(1 << i)` 會得10000$_2$ 也就是16
> `(1UL << (1 << i)) - 1` 就會得到 0xffff 的 `mask`
> 以此類推當 i = 3 時就會得到 0xff 的 `mask`

static inline unsigned long __ffs(unsigned long word)
{
    int num = 0;

#if BITS_PER_LONG == 64
    if ((word & 0xffffffff) == 0) {
        num += 32;
        word >>= 32;
    }
#endif

    for (int i = 4; i >= 0; i--) {
        unsigned long mask = (1UL << (1 << i)) - 1;
        if ((word & mask) == 0) {
            num += (1 << i);
            word >>= (1 << i);
        }
    }

    return num;
}

#### `__clear_bit`
用於將 `addr` 所指向數值的第 `nr` 個 bit 做 clear (即 1 -> 0)

**解釋會用到的巨集**

`BIT_MASK` 會對 `nr` 產生對應的 mask
> BIT_MASK(8) 會產生 0x0000000000000100 的 mask

#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))

`BIT_WORD` 會根據 `nr` 算出 offset

#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)

首先透過 `BIT_MASK` 得到對應的 mask
而 `addr` 本身可能指向到一個陣列，所以可透過加 offset 方式來指到指定位置
最後透過 `*p &= ~mask` 達到將 `addr` 所指向之數值的特定的 bit 做 clear

static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
    unsigned long mask = BIT_MASK(nr);
    unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);

    *p &= ~mask;
}

#### `fns`

用來找到第 N'th set bit

透過 `__ffs` 找到第一個 set bit 的位置，並判斷是否已找到 n 個 set bit
若還未找到，會透過 `__clear_bit` 將當前的第一個 set bit 給 clear 掉，並繼續執行迴圈

static inline unsigned long fns(unsigned long word, unsigned int n)
{
    while (word) {
        unsigned int bit = __ffs(word);
        if (n-- == 0)
            return bit;
        __clear_bit(bit, &word);
    }

    return BITS_PER_LONG;
}

:::danger
注意用語。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

然而這個 <s>function</s> 有一點不直觀，當我執行以下程式
回傳的 `ans` 結果會是 3，但直觀上第 3 個 set bit 應該是要在第 2 個位置

    unsigned int word = 0xf, ans;
    ans = fns(word, 3);

:::warning
TODO: 參照 Linux 核心的文件 (不要用 Google 搜尋，核心原始程式碼就有)，揣摩上述用法的考量。
:::

#### `find_nth_bit`
從 `addr` 指向的地方開始，在給定的記憶體範圍內，找到第 N 個 set bit

**解釋會用到的巨集**

`small_const_nbits`
判斷 `nbits` 是否為 const，且 0 < `nbits` < 64，是則回傳 1，反之回傳 0

#define small_const_nbits(nbits) \
    (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)`

`GENMASK`
給定連續的範圍，得到特定的 bitmask
> 以GENMASK(3, 0)舉例 會得 00001111$_2$
> 左式 `((~0UL) - (1UL << (l)) + 1)` 會得到 0xffff 0xffff 0xffff 0xffff
> 右式 `(~0UL >> (BITS_PER_LONG - 1 - (h)))` 會得到 0x0000 0x0000 0x0000 0x000f
> 兩者做 and 運算後會得到 0x0000 0x0000 0x0000 0x000f
> 即得到 0x000000000000000f 的 mask

#define GENMASK(h, l) \
    (((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))

當 `if (small_const_nbits(size))` 為真時
會透過 `GENMASK` 產生對應 mask，並對 `addr` 做 and 運算
得到的值 `val` 就能確保只會有 `size` 數量的 bits 被 set
最後 `fns` 就會從 `size` 數量的 bits 中找到第 N 個 set bit

static inline unsigned long find_nth_bit(const unsigned long *addr,
                                           unsigned long size,
                                           unsigned long n)
{
    if (n >= size)
        return size;

    if (small_const_nbits(size)) {
        unsigned long val = *addr & GENMASK(size - 1, 0);

        return val ? fns(val, n) : size;
    }

    return FIND_NTH_BIT(addr[idx], size, n);
}

### Linux 核心 `find_nth_bit` 應用範例

[cpumask.h](https://github.com/torvalds/linux/blob/master/include/linux/cpumask.h) 中有相關應用存在
在 Linux 核心中，使用 struct cpumask 來表示 CPU 的狀態
狀態是以 bitmap 形式來呈現，每一個位元即代表一個 CPU

#### `cpumask_nth`
該函式用來找到在 cpumask 中的第 N 個CPU
因為狀態是用 bitmap 表示，因此可以利用 `find_nth_bit` 直接尋找

/**
 * cpumask_nth - get the Nth cpu in a cpumask
 * @srcp: the cpumask pointer
 * @cpu: the Nth cpu to find, starting from 0
 *
 * Return: >= nr_cpu_ids if such cpu doesn't exist.
 */
static inline unsigned int cpumask_nth(unsigned int cpu, const struct cpumask *srcp)
{
	return find_nth_bit(cpumask_bits(srcp), small_cpumask_bits, cpumask_check(cpu));
}