---
tags: linux2022
---
# 2022q1 Homework3 (quiz3)
contributed by < [`qwe661234`](https://github.com/qwe661234) >
> [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz3)
## 測驗一
GENMASK(h, l) 是用來產生 mask, 而 mask 中 0 開始算起位在 l ~ h 的 bit 會是 1, 而其餘會是 0, 也就是 0 ~ l - 1 以及 h + 1 ~ 63 會是 0。
1. `((~0UL) >> (63 - h))` 使得 0 開始算起位在第 h + 1 ~ 63 的 bit 為 0 其餘是 1
2. `((~0UL) >> (l) << (l))` 使得 0 開始算起位在第 l + 1 ~ 63 以及 0 ~ l - 1 的 bit 為 0 其餘是 1
3. 將兩個結果做 `and` operation 可得 0 ~ l - 1 以及 h + 1 ~ 63 會是 0, l ~ h 的 bit 會是 1 的 mask
```c
#include <stdio.h>
#define GENMASK(h, l) \
(((~0UL) >> (63 - h)) & ((~0UL) >> (l) << (l)))
```
我們可以進一步縮減程式碼為, 因為由以上操作可以發現最終 mask, 0 開始算起位在第 h + 1 ~ 63 的 bit 為 0 是由 `(~0UL) >> (63 - h)`, 因此無需左移 l 。
```c
#include <stdio.h>
#define GENMASK(h, l) \
(((~0UL) >> (63 - h)) & ((~0UL) << (l)))
```
## 比較 Linux 核心 GENMASK 巨集的實作，闡述其額外的考量
```c
#define GENMASK_INPUT_CHECK(h, l) \
(BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
__is_constexpr((l) > (h)), (l) > (h), 0)))
#define __GENMASK(h, l) \
(((~UL(0)) - (UL(1) << (l)) + 1) & \
(~UL(0) >> (BITS_PER_LONG - 1 - (h))))
#define GENMASK(h, l) \
(GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
```
我們可以看到 `__GENMASK(h, l)` 的部分 `(~UL(0) >> (BITS_PER_LONG - 1 - (h))` 對應到 `((~0UL) >> (63 - h))`, 考量到硬體架構, 部分硬體架構的 `long` 是 32 bit, 因此改以 `BITS_PER_LONG`, 而不是直接將 `long` 寫成 64 bit。
`((~UL(0)) - (UL(1) << (l)) + 1)` 對應到 `((~0UL) << (l))`, `(~UL(0)) - (UL(1) << (l))` 可得到除了從 0 開始算起第 l 個 bit 是 0 其他是 1 的 mask, 接著我們可以思考, 31 寫成 2 進位會是 `011111`, 將 31 + 1 就會成為 32, 寫成 2 進位就是 `100000`, 由以上觀察可知, 目前產生的 mask, 從 0 開始算起第 l 個 bit 是 0 而 0 ~ l - 1 的 bit 是 1, 我們如果將 mask 加上 1, 會使得第 l 個 bit 變成 1 而第 0 ~ l - 1 的 bit 變成 0, 最後得到位於 0 ~ l - 1 的 bit 為 0, 其餘為 1 的 mask, 與 `((~0UL) << (l))` 的結果相同。
### GENMASK_INPUT_CHECK(h, l)
Linux 和心中的 GENMASK 還有一個額外的考量
1. 檢查 l > h 是否為 constant expersion, constant expression 會在編譯時期就被評估，而不是在執行時期進行評估。
2. 檢查 l 是否大於 h, 因為 GENMASK 正確輸出的前提是 h >= l 。
```c
#define GENMASK_INPUT_CHECK(h, l) \
(BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
__is_constexpr((l) > (h)), (l) > (h), 0)))
```
#### __builtin_choose_expr(exp, e1, e2)
`builtin_choose_expr` 為 gnu extension, 功能類似 `if-else`, 但他可以在編譯時期決定要使用 `e1` or `e2`, 而非執行時期 。
#### __is_constexpr(x)
`__is_constexpr(x)` 也是 gun extension, 用來判斷巨集的輸入是否為 constant expression。
```c
#define __is_constexpr(x) \
(sizeof(int) == sizeof(*(8 ? ((void *) ((long) (x) *0l)) : (int *) 8)))
```
依據 C11 標準 §6.3.2.3
> An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant.
此處就是 __is_constexpr 巨集的關鍵：constant expression 0 轉型為 (void *) 會導致 null pointer constant。相反地，如果本來不是 constant expression，就算乘以 0，只會得到數值 0，予以轉型後，不會得到 null pointer constant，而是一個內含值為 0 的指標，之後仍有機會變動。
若是將 0 轉型成 void *, 可將其視為 null pointer constant, 因此
```c
8 ? ((void *) ((long) (x) *0l)) : (int *) 8
```
如果 x 是 constant expersion, 上述表示式等價於
```c
8 ? [null pointer constant] : (int *) 8
```
接著, 依據 依據 C11 標準 §6.5.15 Conditional operator
> If both the second and third operands are pointers or one is a null pointer constant and the other is a pointer, the result type is a pointer to a type qualified with all the type qualifiers of the types referenced by both operands. Furthermore, if both operands are pointers to compatible types or to differently qualified versions of compatible types, the result type is a pointer to an appropriately qualified version of the composite type; if one operand is a null pointer constant, the result has the type of the other operand; otherwise, one operand is a pointer to void or a qualified version of void, in which case the result type is a pointer to an appropriately qualified version of void.
也就是說, 如果 x 是 constant expersion, 那 `((void *) ((long) (x) *0l))` 就會成為 null pointer constant, 而 `8 ? ((void *) ((long) (x) *0l)) : (int *) 8` 得出的結果會是 `(int *) 8`, 主要依據
> if one operand is a null pointer constant, the result has the type of the other operand;
反之, 如果 x 不是 constant expersion, 則 `8 ? ((void *) ((long) (x) *0l)) : (int *) 8` 的回傳結果會是 `(void *) 0`, 在 gcc 中，sizeof(void) 為 1, 因此, `sizeof(int) == sizeof(void)` 結果為 0 。
#### BUILD_BUG_ON_ZERO(e)
```c
#define BUILD_BUG_ON_ZERO(e) (sizeof(struct { int:(-!!(e)); }))
```
這個 macro 是用來檢查是否會有 compilation error，e 是 expression，當它經由這個 macro 結果為 true ，則可以在 compile-time 的時候被告知有錯。(因為宣告發生在 compile-time)
!!(e)：對 e 做兩次 NOT，確保結果一定是 0 或 1
-!!(e)：對 !!(e) 乘上 -1，因此結果會是 0 或 -1
因此，當 e 這個判斷式不合法時，即 !!(e) = 1 也就是 -!!(e) = -1，代表宣告一個 structure 中有一個 int ，其中 32 bits 中有 -1 bit 的 bit field。 反之當 e 合法時，則會宣告 int 有 0 bit 的 bit field。
綜合以上, 如果 l > h 是 constant experssion, 那 macro 就會檢查 l 是否大於 h, 如果 l > h 會在 `BUILD_BUG_ON_ZERO(e)` 報錯, 如果不是, 則編譯時期無法檢查, 在 `BUILD_BUG_ON_ZERO(e)` 部份會傳入 0, 因此不會報錯。
### reference:
[Linux 核心原始程式碼巨集: max, min](https://hackmd.io/@sysprog/linux-macro-minmax#%E6%9B%B4%E5%A4%9A%E7%9A%84%E6%AA%A2%E6%9F%A5)
[bit-field](https://hackmd.io/@sysprog/c-bitfield)
## 測驗三
```c
#include <stdint.h>
uint8_t rev8(uint8_t x)
{
x = (x >> 4) | (x << 4);
x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);
x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1);
return x;
}
```
## 測驗四
```c
#include <assert.h>
#define _foreach_no_nullval(i, p, arr) \
assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))
#define foreach_int(i, ...) \
for (unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0); \
_foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int); \
(i) = ((int[]){__VA_ARGS__, 0})[++_foreach_i])
#define foreach_ptr(i, ...) \
for (unsigned _foreach_i = \
(((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \
(i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__, \
NULL})[++_foreach_i], \
_foreach_no_nullval(_foreach_i, i, \
((const void *[]){__VA_ARGS__})))
```
### 分析 foreach_int
```c
unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0)
```
`(int[]){__VA_ARGS__}` 這邊利用 compound literal 的方式初始化整數陣列為傳入的不定參數, 將 i 設為 array 的第 0 個 element, 將 `_foreach_i` 設為 0 。
> C99 [6.5.2.5] Compound literals
>* The type name shall specify an object type or an array of unknown size, but not a variable length array type.
>* A postfix expression that consists of a parenthesized type name followed by a braceenclosed list of initializers is a compound literal. It provides an unnamed object whose value is given by the initializer list.
>* If the type name specifies an array of unknown size, the size is determined by the initializer list as specified in 6.7.8, and the type of the compound literal is that of the completed array type. Otherwise (when the type name specifies an object type), the type of the compound literal is that specified by the type name. In either case, the result is an lvalue.
```c
_foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int);
```
將 `_foreach_i` 的中止條件設為小於 array size
```c
(i) = ((int[]){__VA_ARGS__, 0})[++_foreach_i])
```
由於 for loop 中止條件是 `_foreach_i` 要遞增到等於 array size, 因此答案為 `++_foreach_i`, 將 `_foreach_i` 的值加 1, 並將 i 設為下一個 element
### foreach_ptr
foreach_ptr 的作法和 foreach_int 類似, 只是中止條件改為 ptr 為空指標時停止, 並且 foreach_ptr 會檢查 array 和指標是否為 null
## 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
在 [include/linux/list.h](https://github.com/torvalds/linux/blob/fa2e1ba3e9e39072fa7a6a9d11ac432c505b4ac7/include/linux/list.h) 也就是作業 lab0 使用到的 header file list.h 中, 使用到類似的實做技巧, 將 for loop 以 macro 實作。
```c
#define list_for_each_entry(pos, head, member) \
for (pos = list_first_entry(head, typeof(*pos), member); \
!list_entry_is_head(pos, head, member); \
pos = list_next_entry(pos, member))
```
`list_for_each_entry(pos, head, member)` 走訪 doubly linked-list, 從第一個 node 走訪到一圈回到 head, pos 代表 for loop 目前走訪到的 node, head 即 doubly linked-list 的 head, member 是結構體的成員, 用來回推 node 的起始位置。
透過 macro 實做可以讓程式碼更簡潔, 也可以當成是 API, 使用者只需要 call `list_for_each_entry(pos, head, member)`, 就能走訪 doubly linked-list 中的每個 node 並做對應的操作, 而不需要懂這個 `for_each` API 的實做細節。
## 測驗十
透過四捨五入決定是否進位, 所以當 `x / divisor` 的餘數比 `__d / 2` 大時要進位, 反之, 則不進位。 `x / divisor` 的餘數比 `__d / 2` 大也可以看成 `x / divisor` 的餘數加上 `__d / 2` 比 __d 大時要進位，因此改寫成 `__x + (__d >> 1)` 。
`(typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0` 這邊是用來判斷 x 或 divisor 其中一個是不是 unsigned, 只要其中一個是 unsigned, 另外一個也會轉形成 unsigned, `((__x) > 0) == ((__d) > 0))` 用來判斷 x 和 divisor 是否同號, 如果都成立則代表 x 和 divisor 不同號, x < 0, 因此 `__x + (__d >> 1)` 應改成 `__x - (__d >> 1)`。
```c
#define DIVIDE_ROUND_CLOSEST(x, divisor) \
({ \
typeof(x) __x = x; \
typeof(divisor) __d = divisor; \
(((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \
(((__x) > 0) == ((__d) > 0))) \
? ((__x + (__d >> 1)) / (__d)) \
: ((__x - (__d >> 1)) / (__d)); \
})
```
Sign in with Wallet
Connect another wallet