--- tags: linux2022 --- # 2022q1 Homework3 (quiz3) contributed by < `yyyyuwen` > ## 測驗 1 : [GENMASK](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-1) :::info - [x] 解釋上述程式碼運作原理 - [ ] 比較 Linux 核心 GENMASK 巨集的實作,闡述其額外的考量 - [ ] 舉出 Linux 核心原始程式碼中二處 GENMASK 巨集和 include/linux/bitfield.h 的應用案例 ::: ### 題目 在 Linux 核心原始程式碼,[include/linux/bitfield.h](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 提及一個巨集 `GENMASK`,其作用是依據給定的範圍,產生連續的 [bitmask](https://en.wikipedia.org/wiki/Mask_(computing)),例如: * `GENMASK(6, 4)` 產生 01110000<sub>2</sub> * `GENMASK(39, 21)` 產生 0x000000ffffe00000 (64 位元) 已知我們使用的微處理器架構為 64 位元,且 `unsigned long` 為 8 位元組寬度 (符合 [LP64](https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models) 資料模型),以下是可能的 `GENMASK` 巨集的定義: ```cpp #define GENMASK(h, l) \ (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT))) ``` 請補完,使其行為符合預期。作答規範: 1. `LEFT` 和 `RIGHT` 應以最簡潔的形式撰寫,且符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範 (近似 Linux 核心程式碼排版風格) 2. `LEFT` 和 `RIGHT` 皆為表示式,可能包含常數 3. `LEFT` 和 `RIGHT` 皆不該包含小括號 (即 `(` 和 `)`) ### 作答區 :::info #### Common bitmask function **maskng bit to 1** -> **OR** * To make sure the bit is **on**, `OR` can be set with **1**. * To leave the bit unchanged, `OR` can be set with **0**. Example: Masking ***on*** the higher nibble (bits 4, 5, 6, 7) while leaving the lower nibble (bits 0, 1, 2, 3) unchanged. ``` 10010101 10100101 OR 11110000 11110000 ----------------------- = 11110101 11110101 ``` **Masking bits to 0** -> **AND** More often in practice, bits are "**masked off**" (or **masked to 0**) than "masked on" (or masked to 1) * To make the result always be 0, `AND` can be set with **0**. * To leave other bits as they are originally, `AND` can be set with **1**. Example Masking ***off*** the higher nibble (bits 4, 5, 6, 7) while leaving the lower nibble (bits 0, 1, 2, 3) unchanged. ``` 10010101 10100101 AND 00001111 00001111 ----------------------- = 00000101 00000101 ``` **Querying the status of a bit** -> **AND** To use bitmask to check the state of individual bits regardless of the other bits. -> 將要檢查的設定成1,其餘的設0。 Example Querying the status of the 4th bit ``` 10011101 10010101 AND 00001000 00001000 ----------------------- = 00001000 00000000 ``` **Toggling bit values** -> **XOR** 更多的應用是關於 **XOR** **XOR** 又可以解釋成 "A or B, but not, A and B" ::: 首先透過 `GENMASK(6, 4)` 所產生的 01110000<sub>2</sub> 來討論。 * `(((~0UL) >> (LEFT))` :是將 `~0(all 1)` 的 unsigned long 往右移,所以推測位移後高位都會是**0**,低位都會是**1**。 * `((~0UL) >> (l) << (RIGHT))` :會先把 `~0` 往右位移 `l` 個bits,再往左移 `RIGHT` 個bits,推測位移後應該是 **高位與低位都是0而中間是1的型態** 利用 `GENMASK(6, 4)` 來代入得知 ```c //先右移57格再左移4格 GENMASK(6, 4) = 01110000 (0x0000000000000070) (~0UL) >> (4) = 00001111 // 推測該式子應該是將 h 往右移到 l 為止,前面0的個數應該要為 63-h (~0UL) >> (LEFT) = 0x000000000000007f // 因為最後是 AND 的操作,因此要確保的是 l 的右邊都要為0 ((~0UL) >> (4) << (RIGHT)) = 0x0fffffffffffffff << (RIGHT) = 0xfffffffffffffff0 (~0UL) >> (LEFT) & ((~0UL) >> (4) << (RIGHT)) = 0x000000000000007f 0xfffffffffffffff0 & -------------------------- 0x0000000000000070 ``` * `LEFT` = 63 - h * `RIGHT` = l :::warning 提問:是否可將 `((~0UL) >> (4) << (RIGHT))` 更改為 `((~0UL) << (l))`? > 列出你的推測和實驗 > :notes: jserv ::: * [include/linux/bits.h](https://elixir.bootlin.com/linux/latest/source/include/linux/bits.h#L37) --- ## 測驗 2 : [Align down](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-2) :::info 延伸問題: - [x] 解釋上述程式碼運作原理 - [ ] 在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說 ::: ### 題目 考慮以下程式碼: ```cpp struct foo; struct fd { struct foo *foo; unsigned int flags; }; enum { FOO_DEFAULT = 0, FOO_ACTION, FOO_UNLOCK, } FOO_FLAGS; static inline struct fd to_fd(unsigned long v) { return (struct fd){EXP1, v & 3}; } ``` 函式 `to_fd` 接受指定的地址 `v`,填入一個 `fd` 結構體,並確保第一個成員的地址得以依據〈[你所不知道的 C 語言:記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)〉描述,對 4 個位元組進行向下對齊 (即 C++ Boost 描述的 [align_down](https://www.boost.org/doc/libs/1_78_0/doc/html/align/reference.html#align.reference.functions.align_down))。其中 `struct foo;` 運用〈[你所不知道的 C 語言:指標篇](https://hackmd.io/@sysprog/c-pointer)〉提及的 forward declaration 技巧,可在實作階段才提供具體 `struct foo` 的定義。 請補完,使其行為符合預期。作答規範: 1. `EXP1` 應以最簡潔的 C99 形式撰寫,符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範,且不該觸發編譯器警告訊息 2. `EXP1` 不得使用 `%` (modulo) 運算子 3. 當變數和常數進行運算時,變數應該出現前於常數,例如 `v | 1` <mark>作答區</mark> * `EXP1` = ? ### 作答區 先去了解 **data alignment** ,可以知道其作用就是讓記憶體內的資料落在 4 個 bytes 或是 8 個 btyes 的倍數位置(看電腦規格,主要為$2^n$)。 而 data alignment 又可分為 **align down** 以及 **align up**。 #### Align up [include/uapi/linux/const.h](https://elixir.bootlin.com/linux/latest/source/include/uapi/linux/const.h) ```c #define __ALIGN_KERNEL(x, a) __ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1) #define __ALIGN_KERNEL_MASK(x, mask) (((x) + (mask)) & ~(mask)) ``` * `__ALIGN_KERNEL` : 指的是使 `x` 以 `a` 為邊界來對齊 ```graphviz digraph G { rankdir = LR; splines = false; node[shape = "record"] address[label ="<h>Memory address|<a1>0x04|<a2>0x05|<a3>0x06|<a4>0x07|<a5>0x08|<a6>0x09|<a7>0x0a|<a8>0x0b"] before[label ="<h>before align|||<d1>data|<d2>data|<d3>data|<d4>data||",width = 1.5] after[label ="<h>after align|||||<d1>data|<d2>data|<d3>data|<d4>data",width = 1.5] address->before->after } ``` 假設今天的 data 在 $0x06$ ,要將它對 align 於每4個bytes當中,即 $0x04$, $0x08$, $0x0c$, $0x10$。 此時的 `Align value = 4 (byte)` 若今天採取的方法為 Align up ,則 $0x06$ 將會對齊於 $0x08$ 的位置。 這時候 `mask` 為 `(typeof(x))(a) - 1` 意思就是 $2^n - 1$,以 4 byte 為例, `mask` 此時是 $0x03$ * `((x) + (mask))` 是為了讓數字不小於 `x` 並且不大於下一個倍數。 * `((x) + (mask)) & ~(mask)` 是為了將低位的 bit 清成零。 以此題來說 ```c // 以二進位表示 ((x) + (mask)) = 00000110 + 00000011 = 00001001 (((x) + (mask)) & ~(mask)) = 00001001 & 00001100 = 00001000 ``` 而若是 alignment 不為 $2^n$ 時,需改寫成乘除運算的形式 即 ```c (x + mask) & ~mask = (x + (mask - 1)) - ((x + (mask - 1)) % (mask)) = ((x + (mask - 1))/(mask)) * (mask) ``` #### Align down Align down 指的是向下對齊記憶體位址 [include/linux/align.h](https://elixir.bootlin.com/linux/latest/source/include/linux/align.h#L10)中提到 ```c /* @a is a power of 2 value */ #define ALIGN(x, a) __ALIGN_KERNEL((x), (a)) #define ALIGN_DOWN(x, a) __ALIGN_KERNEL((x) - ((a) - 1), (a)) #define __ALIGN_MASK(x, mask) __ALIGN_KERNEL_MASK((x), (mask)) #define PTR_ALIGN(p, a) ((typeof(p))ALIGN((unsigned long)(p), (a))) #define PTR_ALIGN_DOWN(p, a) ((typeof(p))ALIGN_DOWN((unsigned long)(p), (a))) #define IS_ALIGNED(x, a) (((x) & ((typeof(x))(a) - 1)) == 0) ``` 與 Align up 不同的是在 `__ALIGN_KERNEL` 中所傳的值為 `((x) - ((a) - 1), (a))` 其作用是要讓值往上移到上4 byte 後再進行 mask 的操作。 ```graphviz digraph G { rankdir = LR; splines = false; node[shape = "record"] address[label ="<h>Memory address|<a1>0x04|<a2>0x05|<a3>0x06|<a4>0x07|<a5>0x08|<a6>0x09|<a7>0x0a|<a8>0x0b"] before[label ="<h>before align|||<d1>data|<d2>data|<d3>data|<d4>data||",width = 1.5] after[label ="<h>after align|<d1>data|<d2>data|<d3>data|<d4>data||||",width = 1.5] address->before->after } ``` 題目程式為 ```c= struct fd { struct foo *foo; unsigned int flags; }; static inline struct fd to_fd(unsigned long v) { return (struct fd){EXP1, v & 3}; } ``` 由於 `ALIGN_DOWN(v, mask) = (v) & ~mask` (`mask = size - 1`), 而題目要求是要做 4 byte 的 align ,因此 `mask` = 3。 最後根據 `forward declaration` 的定義,我們要將回傳格式轉成 `(struct foo *)` * `EXP = (struct foo *) (v & ~3)` ## 測驗 3 : [Reverse Bits](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-3) :::info 延伸問題: - [x] 解釋上述程式碼運作原理 - [ ] 在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說 ::: ### 題目 考慮以下程式碼,能將輸入的 8 位元無號整數逐一位元反轉,如同 [LeetCode 190. Reverse Bits](https://leetcode.com/problems/reverse-bits/) 的描述。 ```cpp= #include <stdint.h> uint8_t rev8(uint8_t x) { x = (x >> 4) | (x << 4); x = ((x & 0xCC) >> 2) | (EXP2); x = ((x & 0xAA) >> 1) | (EXP3); return x; } ``` 請補完,使其行為符合預期。作答規範: EXP2 和 EXP3 應以最簡潔的 C99 形式撰寫,符合作業一排版規範,且不該觸發編譯器警告訊息 當變數和常數進行運算時,變數應該出現前於常數,例如 v | 1 作答區 EXP2 = ? EXP3 = ? ### 作答區 此行代表的是 4 位元的前後反轉。 `x` 先分別往右以及往左 4 位元,最後再做 `OR` 的動作,而因為是uint,所以都是補 `0`。 ```c=4 x = (x >> 4) | (x << 4); ``` e.g. ```c x = 10000111 (x >> 4) = 00001000 (x << 4) = 01110000 (x >> 4) | (x << 4) = 01111000 ``` 再來是做兩兩位移, $0xCC$ 代表是 $11001100b$。 * `((x & 0xCC) >> 2)` 是將每 4 bits 高位元的 2 bits 做兩兩置換,這邊是先留下前面兩個 bits 將後面的捨去掉。 * `EXP2` 推測應該是要置換每 4 bits 中低位元的部分,即 $00110011b$ ,最後再做 `OR` 合併。 ```c=5 x = ((x & 0xCC) >> 2) | (EXP2); ``` e.g. ```c x = 01111000 (x & 0xCC) = 01001000 ((x & 0xCC) >> 2) = 00010010 EXP2 = ((x & 0x33) << 2) = 00110000 << 2 = 11000000 ((x & 0xCC) >> 2) | ((x & 0x33) << 2) = 11010010 ``` 最後是做每一個 bit 的置換, $0xAA$ 代表的是 $10101010$ * `((x & 0xAA) >> 1)` 對於每兩個 bits 中,將前一個留下而後一個拿掉,同時將式子往右移一個 bit ,是為了後許將值變成是低位的 bit。 * `EXP3` 因此對於這邊則是相反,留下後面的並拿掉前面的一個 bit ,並往左移一個 bit ,轉換每兩個 bit 的高低位元,推測應該是要用 $01010101b$ 也就是 $0x55$ 。 ```c=6 x = ((x & 0xAA) >> 1) | (EXP3); ``` ```c x = 11010010 (x & 0xAA) = 10000010 ((x & 0xAA) >> 1) = 01000001 EXP3 = ((x & 0x55) << 1) = 01010000 << 1 = 10100000 ((x & 0xAA) >> 1) | ((x & 0x55) << 1) = 11100001 ``` * `EXP2` = ((x & 0x33) << 2) * `EXP3` = ((x & 0x55) << 1) ## 測驗4 : [foreach 巨集](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-4) :::info 延伸問題: - [x] 解釋上述程式碼運作原理 - [ ] 在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說 ::: ### 題目 延伸〈[你所不知道的 C 語言:前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)〉,我們嘗試將 [foreach 巨集](https://en.wikipedia.org/wiki/Foreach_loop) 予以擴充,使得支援以下寫法: ```cpp int i; foreach_int(i, 0, -1, 100, 0, -99) { printf("i is %i\n", i); } const char *p; foreach_ptr(p, "Hello", "world") { printf("p is %s\n", p); } ``` 預期輸出如下: ``` i is 0 i is -1 i is 100 i is 0 i is -99 p is Hello p is world ``` 對應的巨集定義: ```cpp #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})[EXP4]) #define foreach_ptr(i, ...) \ for (unsigned _foreach_i = \ (((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \ (i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__, \ NULL})[EXP5], \ _foreach_no_nullval(_foreach_i, i, \ ((const void *[]){__VA_ARGS__}))) ``` 請補完,使其行為符合預期。作答規範: 1. `EXP4` 和 `EXP5` 應以最簡潔的 C99 形式撰寫,符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範,且不該觸發編譯器警告訊息 2. 不該出現小括號 (即 `(` 和 `)`) <mark>作答區</mark> * `EXP4` = ? * `EXP5` = ? ### 作答區 ```c= #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})[EXP4]) ```