---
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])
```
Sign in with Wallet
Connect another wallet