---
tags: linux2022
---
# 2022q1 Homework3 (quiz3)
contributed by < [ganoliz](https://github.com/ganoliz) >
## 測驗一
在 Linux 核心原始程式碼，[include/linux/bitfield.h](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 提及一個巨集 GENMASK，其作用是依據給定的範圍，產生連續的 bitmask，例如:
* ```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 巨集的定義:
```c
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
請問，
```LEFT``` = ?
```RIGHT``` = ?
我們可以知道 ~0UL 的值是 0 ~ 64 bits 的值都為 1 ，然後我們可以將這個 GENMASK 巨集拆成兩個部分:
```(~0UL) >> (LEFT)``` 與 ```(~0UL) >> (l) << (RIGHT)``` 兩個部分。在假設為"非邏輯位移"的情況下(而且這裡是 unsigned long)，那麼答案為 LEFT = 63 - h RIGHT = l
```c
(((~0UL) >> (63 - (h))) & ((~0UL) >> (l) << (l)))
```
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 比較 Linux 核心 GENMASK 巨集的實作，闡述其額外的考量
3. 舉出 Linux 核心原始程式碼中二處 GENMASK 巨集和 [include/linux/bitfield.h](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 的應用案例
:::
## 測驗二
考慮以下程式碼:
```c
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 ``` 的定義。
請問，
```EXP1```= ?
參考[<jim12312321>](https://hackmd.io/@jim12312321/linux2022-quiz3#%E6%B8%AC%E9%A9%97-2-%EF%BC%9A-%E8%A8%98%E6%86%B6%E9%AB%94%E5%90%91%E4%B8%8B%E5%B0%8D%E9%BD%8A) 對於記憶體對齊的描述:
向上對齊(對 4 bytes 或 8 bytes 對齊):
* 對記憶體的位置最後 2 個 bits 做 clear 的動作才能對齊
* 對記憶體第3個 bit ($2^2$) + 1
```graphviz
digraph test{
Node1[label="{Memory Address|0x0|0x1|0x2|0x3|0x4|0x5|0x6|0x7}|{Data||data|data|data|data|||}",shape=record]
Node2[label="{Memory Address|0x0|0x1|0x2|0x3|0x4|0x5|0x6|0x7}|{Data|||||data|data|data|data}",shape=record]
Node1->Node2
}
```
>未 alignment 前起始位置 : $0x01_{16}$
>alignment 後 : $0x04_{16}$
向下對齊:
* 對記憶體的位置最後 2 個 bits 做 clear 的動作。
```graphviz
digraph test{
Node1[label="{Memory Address|0x0|0x1|0x2|0x3|0x4|0x5|0x6|0x7}|{Data||data|data|data|data|||}",shape=record]
Node2[label="{Memory Address|0x0|0x1|0x2|0x3|0x4|0x5|0x6|0x7}|{Data|data|data|data|data||||}",shape=record]
Node1->Node2
}
```
>未 alignment 前起始位置 : $0x01_{16}$
>alignment 後 : $0x00_{16}$
因此在對齊，我們可以知道(注意向下對齊是往記憶體位置的下面對齊)
```c
//EXP 1 :
return (struct fd){ (struct *foo)(v & ~3), v & 3};
```
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說
:::
## 測驗三
考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 [LeetCode 190. Reverse Bits](https://leetcode.com/problems/reverse-bits/) 的描述。
```c
#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``` = ?
這裡就是老師 C語言 bitwise 講座提到的內容，基本上這段程式碼就是透過shift的方式一對一對的把高低位元交換。首先最高四個位元與最低四個位元交換。接著是 4 bits 的高兩個位元與低兩個位元交換，
因此
```
x = ((x & 0xCC) >> 2 | (x & 0x33) << 2)
x = ((x & 0xaa) >> 1)| (x & 0x55) << 1)
```
## 測驗四
延伸[〈你所不知道的 C 語言：前置處理器應用篇〉](https://hackmd.io/@sysprog/c-preprocessor)，我們嘗試將 [foreach 巨集](https://en.wikipedia.org/wiki/Foreach_loop) 予以擴充，使得支援以下寫法:
```c
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
```
對應的巨集定義:
```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})[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__})))
```
請問，
```EXP4``` = ?
```EXP5``` = ?
根據巨集，我們可以進行拆解，在 foreach_int 迴圈裡， ( i ) = ((int []){__VA_ARGS__})[0] ，就是指目前在 後面參數中的第零個位置的值，因此我們要更新的值是 _foreach_i
```c
...;...; (i) = ((int []){__VA_ARGS__, 0}[++_foreach_i]) // 原本寫 _foreach_i++ 是錯誤的，要先加再賦值
```
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
:::
## 測驗五
針對 [LeetCode 29. Divide Two Integers](https://leetcode.com/problems/divide-two-integers/)，以下是可能的實作:
```c
#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;
}
```
```EXP6``` = ?
```EXP7``` = ?
```c
EXP6: while (dvd > (dvs << shift)) // 原本寫 1 << shift 會有 error 的情況
```
```c
EXP7: dvd -= dvs << shift;
```
:::success
延伸問題:
1. 解釋上述程式碼運作原理，指出可改進之處，並予以實作
2. 在 Linux 核心原始程式碼中找出針對整數/浮點數/[定點數](https://en.wikipedia.org/wiki/Fixed-point_arithmetic)除法特別撰寫的程式碼，並予以討論
:::
## 測驗六
針對 [LeetCode 149. Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)，以下是可能的實作:
```c
#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;
}
```
```EXP8``` = ?
```EXP9``` = ?
:::success
延伸問題:
1. 解釋上述程式碼運作原理，指出可改進之處，並予以實作
2. 擴充 LeetCode 題目，考慮更多座標點的輸入 (例如超過 10 萬個) 時，設計有效的資料結構以降低記憶體開銷，並確保快速的執行
:::
## 測驗七
考慮 ilog32 函式可針對給定的 32 位元無號數，計算扣除開頭的 0，最少需要多少位元才可儲存 (the minimum number of bits required to store an unsigned 32-bit value without any leading zero bits)，以下是一個可能的實作:
```c
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;
}
```
請問，
```EXP10``` = ?
```EXP11``` = ?
```c
EXP10: m = (v > 0x3U) << 1
```
```c
EXP11: ret += (v > 0x1);
```
:::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``` 實作
:::
## 測驗八
考慮以下 C++ 二元搜尋樹的程式:
```c
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 改寫為以下:
```c
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;
}
```
請問，
```EXP12``` = ?
```EXP13``` = ?
```EXP14``` = ?
首先我們看看這個題目，確定找到該點 p 的 data = d 之後，在 if-else裡主要有三種情況。對應於 if (!q->left) 、 else if (!q->right) 、 else 。
```graphviz
digraph test{
node1[label="p"]
node1->p_left
node1->Null
}
```
```graphviz
digraph test{
node1[label="p"]
node1->Null
node1->p_right
}
```
```graphviz
digraph test{
node1[label="p"]
node1->p_left
node1->p_right
}
```
分別為 p 無左子點 、 p 無右子點 、 p 有兩個子點。
首先我們先把簡單的 EXP12 、 EXP13 填上。
```c
EXP12: p = &(*p)->left;
EXP13: p = &(*p)->right;
```
(這裡目前在想改 *p 還是 p 比較好)
```c
EXP14: r = &(*r)->left;
```
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 以 C99 改寫上述程式碼，並寫出更精簡高效的實作，和最初的實作相比，探討效率的提升
3. 研讀 [Static B-Trees](https://en.algorithmica.org/hpc/data-structures/s-tree/)，探討針對記憶體佈局 (memory layout) 的改進策略
:::
## 測驗九
考慮以下進行記憶體地址對齊 (alignment) 的巨集:
```c
/* 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``` = ?
這題的對齊可以先看第二題的概念。
```c
(((x) + MAX_ALIGNMENT - 1 ) & ~(MAX_ALIGNMENT - 1)) //(((x) + MAX_ALIGNMENT - (x << 1) ) & ~(x | 3))
```
原來這題是將位置對齊 MAX_ALIGNMENT 的位置，我一直以為是根據 x 來決定對齊的位置，因此一直想不出來。假如是對齊 MAX_ALIGNMENT 就是將 最 LSB 的 4 個 bits 用反相 & 清為 0 。
:::success
延伸問題:
1. 解釋上述程式碼運作原理，並撰寫出對應 ```ROUND_DOWN``` 巨集
2. 在 Linux 核心找出類似的巨集和程式碼，說明 round-up/down 的應用場合
:::
## 測驗十
考慮以下巨集可得到二個表示式進行整數除法操作時，最接近的整數值:
```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))) \
? ((RRR) / (__d)) \
: ((SSS) / (__d)); \
})
```
注意: 當除數 (即 ```divisor```) 為負值時，行為沒有定義。
參考執行結果:
```DIVIDE_ROUND_CLOSEST(7, 3) = 2```
```DIVIDE_ROUND_CLOSEST(6, 3) = 2```
```DIVIDE_ROUND_CLOSEST(5, 3) = 2```
請問，
```RRR``` = ?
```SSS``` = ?
```c
RRR: __x;
SSS: -__x;
```
本來這樣寫就可以了，但是參考別人的想法，因為 c 語言會無條件捨去，所以我們要四捨五入時就要做補正了。 這裡的 (_d >> 1)/_d 之後會變 0.5 ，因此我們先加完再除的時候就等於補正 0.5 的數值了。
```c
RRR: __x + (_d >> 1)
SSS: -__x - (_d >> 1)
```
:::success
延伸問題:
解釋上述程式碼運作原理
在 Linux 核心找出類似的巨集和程式碼，說明 div round-up/closest 的應用場合
:::
## 測驗十一
考慮以下計算整數開平方根的實作:
```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))```
請問，
```XXX``` = ?
```YYY``` = ?
```ZZZ``` = ?
```c
XXX: b *= b;
YYY: x -= b;
ZZZ: m = m >> 1;
```
我們可以知道 fls() 是找到最少需要儲存的 bits 數(也就是 MSB 的位置)，因此初始 m 比 我們的 x 高一個bits，肯定大於 x 。
:::success
延伸問題:
1. 解釋上述程式碼運作原理，嘗試利用硬體的 clz/ctz 指令改寫
2. 在 Linux 核心找出類似的巨集和程式碼，說明其應用場景
:::
Sign in with Wallet
Connect another wallet