# [2022q1](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 3 週測驗題
###### tags: `linux2022`
:::info
目的: 檢驗學員對 **[記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory), [指標](https://hackmd.io/@sysprog/c-pointer), [bitwise](https://hackmd.io/@sysprog/c-bitwise), [前置處理器](https://hackmd.io/@sysprog/c-preprocessor)** 的認知
:::
==[作答表單: 測驗 1-8](https://docs.google.com/forms/d/e/1FAIpQLSfbr-mp4R9xplIudwb2158R0DQAPuDm-Vut7Bu9eNgSJeGy1w/viewform)== (Linux 核心設計)
==[作答表單: 測驗 9-11](https://docs.google.com/forms/d/e/1FAIpQLSex0NkMP0ZOxTc1vFry891T65EplCKbEpi_l2_xpUjAk_hKyw/viewform)== (Linux 核心實作)
### 測驗 `1`
在 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~2~
* `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` 皆不該包含小括號 (即 `(` 和 `)`)
==作答區==
* LEFT = ?
* RIGHT = ?
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 比較 Linux 核心 `GENMASK` 巨集的實作，闡述其額外的考量
3. 舉出 Linux 核心原始程式碼中二處 `GENMASK` 巨集和 [include/linux/bitfield.h](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 的應用案例
:::
---
### 測驗 `2`
考慮以下程式碼:
```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};
}
```
函式 `fo_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`
==作答區==
* `EXP1` = ?
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說
:::
---
### 測驗 `3`
考慮以下程式碼，能將輸入的 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;
}
```
請補完，使其行為符合預期。作答規範:
1. `EXP2` 和 `EXP3` 應以最簡潔的 C99 形式撰寫，符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範，且不該觸發編譯器警告訊息
2. 當變數和常數進行運算時，變數應該出現前於常數，例如 `v | 1`
==作答區==
* `EXP2` = ?
* `EXP3` = ?
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
:::
---
### 測驗 `4`
延伸〈[你所不知道的 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. 不該出現小括號 (即 `(` 和 `)`)
==作答區==
* `EXP4` = ?
* `EXP5` = ?
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
:::
---
### 測驗 `5`
針對 LeetCode [29. Divide Two Integers](https://leetcode.com/problems/divide-two-integers/)，以下是可能的實作:
```cpp
#include <limits.h>
int divide(int dividend, int divisor)
{
int signal = 1;
unsigned int dvd = dividend;
if (dividend < 0) {
signal *= -1;
dvd = ~dvd + 1;
}
unsigned int dvs = divisor;
if (divisor < 0) {
signal *= -1;
dvs = ~dvs + 1;
}
int shift = 0;
while (dvd > (EXP6))
shift++;
unsigned int res = 0;
while (dvd >= dvs) {
while (dvd < (dvs << shift))
shift--;
res |= (unsigned int) 1 << shift;
EXP7;
}
if (signal == 1 && res >= INT_MAX)
return INT_MAX;
return res * signal;
}
```
請補完，使其行為符合預期。作答規範:
1. `EXP6` 和 `EXP7` 應以最簡潔的 C99 形式撰寫，符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範，且不該觸發編譯器警告訊息
2. 不該出現小括號 (即 `(` 和 `)`)
==作答區==
* `EXP6` = ?
* `EXP7` = ?
:::success
延伸問題:
1. 解釋上述程式碼運作原理，指出可改進之處，並予以實作
2. 在 Linux 核心原始程式碼中找出針對整數/浮點數/[定點數](https://en.wikipedia.org/wiki/Fixed-point_arithmetic)除法特別撰寫的程式碼，並予以討論
:::
---
### 測驗 `6`
針對 LeetCode [149. Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)，以下是可能的實作:
```cpp
#include <stdbool.h>
#include "list.h"
struct Point {
int x, y;
};
struct point_node {
int p1, p2;
struct list_head link;
};
static bool can_insert(struct list_head *head, int p1, int p2)
{
struct point_node *pn;
list_for_each_entry (pn, head, link)
return EXP8;
return true;
}
static int gcd(int x, int y)
{
while (y) {
int tmp = y;
y = x % y;
x = tmp;
}
return x;
}
static int maxPoints(struct Point *points, int pointsSize)
{
if (pointsSize <= 2)
return pointsSize;
int i, j, slope_size = pointsSize * pointsSize / 2 + 133;
int *dup_cnts = malloc(pointsSize * sizeof(int));
int *hori_cnts = malloc(pointsSize * sizeof(int));
int *vert_cnts = malloc(pointsSize * sizeof(int));
int *slope_cnts = malloc(slope_size * sizeof(int));
memset(hori_cnts, 0, pointsSize * sizeof(int));
memset(vert_cnts, 0, pointsSize * sizeof(int));
memset(slope_cnts, 0, slope_size * sizeof(int));
for (i = 0; i < pointsSize; i++)
dup_cnts[i] = 1;
struct list_head *heads = malloc(slope_size * sizeof(*heads));
for (i = 0; i < slope_size; i++)
INIT_LIST_HEAD(&heads[i]);
for (i = 0; i < pointsSize; i++) {
for (j = i + 1; j < pointsSize; j++) {
if (points[i].x == points[j].x)
hori_cnts[i]++, hori_cnts[j]++;
if (points[i].y == points[j].y)
vert_cnts[i]++, vert_cnts[j]++;
if (points[i].x == points[j].x && points[i].y == points[j].y)
dup_cnts[i]++, dup_cnts[j]++;
if (points[i].x != points[j].x && points[i].y != points[j].y) {
int dx = points[j].x - points[i].x;
int dy = points[j].y - points[i].y;
int tmp = gcd(dx, dy);
dx /= tmp;
dy /= tmp;
int hash = dx * dy - 1333 * (dx + dy);
if (hash < 0)
hash = -hash;
hash %= slope_size;
if (can_insert(&heads[hash], i, j)) {
struct point_node *pn = malloc(sizeof(*pn));
pn->p1 = i;
pn->p2 = j;
EXP9;
}
}
}
}
for (i = 0; i < slope_size; i++) {
int index = -1;
struct point_node *pn;
list_for_each_entry (pn, &heads[i], link) {
index = pn->p1;
slope_cnts[i]++;
}
if (index >= 0)
slope_cnts[i] += dup_cnts[index];
}
int max_num = 0;
for (i = 0; i < pointsSize; i++) {
if (hori_cnts[i] + 1 > max_num)
max_num = hori_cnts[i] + 1;
if (vert_cnts[i] + 1 > max_num)
max_num = vert_cnts[i] + 1;
}
for (i = 0; i < slope_size; i++) {
if (slope_cnts[i] > max_num)
max_num = slope_cnts[i];
}
return max_num;
}
```
請補完，使其行為符合預期。作答規範:
1. `EXP8` 和 `EXP9` 應以最簡潔的 C99 形式撰寫，符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範，且不該觸發編譯器警告訊息
2. `EXP8` 不該出現小括號 (即 `(` 和 `)`)
3. `EXP9` 為包含 `list_` 開頭巨集的單一敘述
==作答區==
* `EXP8` = ?
* `EXP9` = ?
:::success
延伸問題:
1. 解釋上述程式碼運作原理，指出可改進之處，並予以實作
2. 擴充 LeetCode 題目，考慮更多座標點的輸入 (例如超過 10 萬個) 時，設計有效的資料結構以降低記憶體開銷，並確保快速的執行
:::
---
### 測驗 `7`
考慮 `ilog32` 函式可針對給定的 32 位元無號數，計算扣除開頭的 `0`，最少需要多少位元才可儲存 (the minimum number of bits required to store an unsigned 32-bit value without any leading zero bits)，以下是一個可能的實作:
```cpp
int ilog32(uint32_t v)
{
int ret = v > 0;
int m = (v > 0xFFFFU) << 4;
v >>= m;
ret |= m;
m = (v > 0xFFU) << 3;
v >>= m;
ret |= m;
m = (v > 0xFU) << 2;
v >>= m;
ret |= m;
m = EXP10;
v >>= m;
ret |= m;
EXP11;
return ret;
}
```
請補完，使其行為符合預期。作答規範:
1. `EXP10` 和 `EXP11` 應以最簡潔的 C99 形式撰寫，符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範，且不該觸發編譯器警告訊息
2. `EXP11` 不該出現小括號 (即 `(` 和 `)`)
3. `EXP10` 和 `EXP11` 皆包含 `>` 運算子
==作答區==
* `EXP10` = ?
* `EXP11` = ?
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 在 Linux 核心原始程式碼找出類似實作並解說其應用場景
3. 研讀論文《[Using de Bruijn Sequences to Index a 1 in a Computer Word](http://supertech.csail.mit.edu/papers/debruijn.pdf)》，探討缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 `ilog`
4. 運用〈[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)〉和〈[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)〉提及的技巧，實作編譯時期 (compile-time) 的 `ilog2` 實作
:::
---
### 測驗 `8`
考慮以下 C++ 二元搜尋樹的程式:
```cpp
typedef struct tnode *tree;
struct tnode {
int data;
tnode *left;
tnode *right;
tnode(int d)
{
data = d;
left = right = 0;
}
};
void remove_data(tree &t, int d)
{
tnode *p = t;
tnode *q;
while (p != 0 && p->data != d) {
if (d < p->data) {
q = p;
p = p->left;
} else {
q = p;
p = p->right;
}
}
if (p != 0) {
if (p->left == 0)
if (p == t)
t = p->right;
else if (p == q->left)
q->left = p->right;
else
q->right = p->right;
else if (p->right == 0)
if (p == t)
t = p->left;
else if (p == q->left)
q->left = p->left;
else
q->right = p->left;
else {
tnode *r = p->right;
while (r->left) {
q = r;
r = r->left;
}
p->data = r->data;
if (r == p->right)
p->right = r->right;
else
q->left = r->right;
p = r;
}
delete p;
}
}
```
函式 `remove_data` 嘗試將指定的資料，自給定的二元搜尋樹移除，但原本的 `remove_data` 過於冗長，於是我們可善用 indirect pointer 改寫為以下:
```cpp
void remove_data(tree &t, int d)
{
tnode **p = &t;
while (*p != 0 && (*p)->data != d) {
if (d < (*p)->data)
EXP12;
else
EXP13;
}
tnode *q = *p;
if (!q)
return;
if (!q->left)
*p = q->right;
else if (!q->right)
*p = q->left;
else {
tnode **r = &q->right;
while ((*r)->left)
r = EXP14;
q->data = (*r)->data;
q = *r;
*r = q->right;
}
delete q;
}
```
請補完，使其行為符合預期。作答規範:
1. `EXP12`, `EXP13` 和 `EXP14` 應以最簡潔的 C99 形式撰寫，符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範，且不該觸發編譯器警告訊息，並善用 indirect pointer 的技巧來撰寫
2. `EXP12`, `EXP13` 和 `EXP14` 皆不該出現 `;`
==作答區==
* `EXP12` = ?
* `EXP13` = ?
* `EXP14` = ?
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 以 C99 改寫上述程式碼，並寫出更精簡高效的實作，和最初的實作相比，探討效率的提升
3. 研讀 [Static B-Trees](https://en.algorithmica.org/hpc/data-structures/s-tree/)，探討針對記憶體佈局 (memory layout) 的改進策略
:::
---
### 測驗 `9`
考慮以下進行記憶體地址對齊 (alignment) 的巨集:
```cpp
/* maximum alignment needed for any type on this platform, rounded up to a
power of two */
#define MAX_ALIGNMENT 16
/* Given a size, round up to the next multiple of sizeof(void *) */
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
(((x) + MAX_ALIGNMENT - MMM) & ~(NNN))
```
作用是向上對齊 (roundup)，請補完程式碼，使其行為符合預期。作答規範:
* `MMM` 是常數
* `NNN` 是表示式
* `MMM` 和 `NNN` 皆不得出現小括號 (即 `(` 和 `)`)
* 符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)的排版和程式碼風格規範
* 以符合 C99 的最精簡形式撰寫
==作答區==
* `MMM` = ?
* `NNN` = ?
:::success
延伸問題:
1. 解釋上述程式碼運作原理，並撰寫出對應 `ROUND_DOWN` 巨集
2. 在 Linux 核心找出類似的巨集和程式碼，說明 round-up/down 的應用場合
:::
---
### 測驗 `10`
考慮以下巨集可得到二個表示式進行整數除法操作時，最接近的整數值:
```cpp
#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))) \
? ((RRR) / (__d)) \
: ((SSS) / (__d)); \
})
```
注意: 當除數 (即 `divisor`) 為負值時，行為沒有定義。
參考執行結果:
* `DIVIDE_ROUND_CLOSEST(7, 3) = 2`
* `DIVIDE_ROUND_CLOSEST(6, 3) = 2`
* `DIVIDE_ROUND_CLOSEST(5, 3) = 2`
作答規範:
* 符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)的排版和程式碼風格規範
* `RRR` 和 `SSS` 為表示式，且都包含 `(__x)` 和 `(__d)` (注意小括號)
* `RRR` 和 `SSS` 限用 `+`, `-`, `>>`, `<<` 這幾個運算子，可搭配小括號，並以符合 C99 的最精簡形式撰寫
* 變數在 `RRR` 和 `SSS` 出現的順序 (從左到右)，必定是 `__x` 先於 `__d`
請補完程式碼，使其行為符合預期。
==作答區==
* `RRR` = ?
* `SSS` = ?
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 在 Linux 核心找出類似的巨集和程式碼，說明 div round-up/closest 的應用場合
:::
---
### 測驗 `11`
考慮以下計算整數開平方根的實作:
```c
static inline unsigned long fls(unsigned long word)
{
int num = 64 - 1;
if (!(word & (~0ul << 32))) {
num -= 32;
word <<= 32;
}
if (!(word & (~0ul << (64 - 16)))) {
num -= 16;
word <<= 16;
}
if (!(word & (~0ul << (64 - 8)))) {
num -= 8;
word <<= 8;
}
if (!(word & (~0ul << (64 - 4)))) {
num -= 4;
word <<= 4;
}
if (!(word & (~0ul << (64 - 2)))) {
num -= 2;
word <<= 2;
}
if (!(word & (~0ul << (64 - 1))))
num -= 1;
return num;
}
unsigned long i_sqrt(unsigned long x)
{
unsigned long b, m, y = 0;
if (x <= 1)
return x;
m = 1UL << (fls(x) & ~1UL);
while (m) {
b = y + m;
XXX;
if (x >= b) {
YYY;
y += m;
}
ZZZ;
}
return y;
}
```
`i_sqrt` 函式的作用等同於 `floor(sqrt(x))`
作答規範:
* 符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)的排版和程式碼風格規範
* `XXX`, `YYY` 和 `ZZZ` 都是敘述，不得呼叫任何函式，且不包含 `;` 字元
* 只能使用 `=`, `+=`, `-=`, `>>=`, `<<=` 等運算子，且不得出現小括號 (即 `(` 和 `)`)
* 以符合 C99 的最精簡形式撰寫
==作答區==
* `XXX` = ?
* `YYY` = ?
* `ZZZ` = ?
:::success
延伸問題:
1. 解釋上述程式碼運作原理，嘗試利用硬體的 clz/ctz 指令改寫
2. 在 Linux 核心找出類似的巨集和程式碼，說明其應用場景
:::
Sign in with Wallet
Connect another wallet