# 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出現在下半部，則再繼續往下半部的下半部來檢查 ```c 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` ```c 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 ```c #define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) ``` `BIT_WORD` 會根據 `nr` 算出 offset ```c #define BIT_WORD(nr) ((nr) / BITS_PER_LONG) ``` 首先透過 `BIT_MASK` 得到對應的 mask 而 `addr` 本身可能指向到一個陣列，所以可透過加 offset 方式來指到指定位置 最後透過 `*p &= ~mask` 達到將 `addr` 所指向之數值的特定的 bit 做 clear ```c 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 掉，並繼續執行迴圈 ```c 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 ```c #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 ```c #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 ```c 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` 直接尋找 ```c /** * 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)); } ```