---
tags: linux2022
---
# 第 1,2 週課堂問答簡記
## `Uduru0522`
Linux 核心的 hash table 實作中，用以處理 hash 數值碰撞的 `hlist_node`:
```cpp
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
**其中 `pprev` 為何要宣告為==指標的指標==？**
探討典型 doubly-linked list delete 會產生的問題。
考慮我們使用典型的 doubly-linked list:
```c
struct dll_node {
struct dll_node *next, *prev;
}
```
> `dll` 是 doubly-linked list 的簡稱
於是資料結構會展現如下圖:
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
list_head[label = "<m>list_head | <n>first"]
node_1[label = "<m>dll_node_1 | {<p>prev | <n>next}", group = list];
node_2[label = "<m>dll_node_2 | {<p>prev | <n>next}", group = list];
node_3[label = "<m>dll_node_3 | {<p>prev | <n>next}", group = list];
NULL_1, NULL_2[shape = plaintext, label = "NULL", group = list]
{rank = "min" list_head NULL_1}
list_head -> node_1:m;
node_1:p -> NULL_1
node_1:n -> node_2:m;
node_2:p -> node_1:m;
node_2:n -> node_3:m;
node_3:p -> node_2:m;
node_3:n -> NULL_2;
}
```
注意：
+ 除了末端，第一個節點的 `prev` 指標內容也是 `NULL`。
+ `prev` 及 `next` 皆指向相鄰的**節點本身**。
嘗試撰寫 `delete_node():`
```c
void dll_delete_node(struct list_head *l, struct dll_node *n)
{
struct dll_node *prev = n->prev,
*next = n->next;
if (next)
next->prev = prev;
// Delete and update where list_head points to,
// which requires the list_head to be passed in.
if (!prev) {
l->first = next;
} else {
prev->next = next;
}
}
```
可發現當我們要移除第一個節點時，必須做出額外的操作來更新 `list_head` 指向的節點，於是除了移除的目標之外，還必須傳入 `list_head`。
當我們用指標的指標改寫上述程式碼，將原本的 `struct dll_node *prev` 變更為 `struct dll_node **pprev`:
```c
struct hlist_node {
struct hlist_node *next, **pprev;
}
```
則會形成以下的結構：
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
list_head[label = "<m>list_head | <n>first"]
node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
node_2[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", group = list];
node_3[label = "<m>hlist_node_3 | {<p>pprev | <n>next}", group = list];
NULL[shape = plaintext, label = "NULL", group = list]
{rank = "min" list_head}
list_head -> node_1 -> node_2 -> node_3[
weight = 10, style = invis
]
list_head:n -> node_1:m;
node_1:p -> list_head:n;
node_1:n -> node_2:m;
node_2:p -> node_1:n;
node_2:n -> node_3:m;
node_3:p -> node_2:n;
node_3:n -> NULL;
}
```
注意：
+ 僅有末端指標內容是 `NULL`。
+ `next` 指向相鄰的**節點本身**，而 `pprev` 指向**指著自身節點的指標**。
則我們便可藉由下方程式碼來撰寫 `delete_node()`：
```c
void hlist_delete_node(struct hlist_node *n)
{
struct hlist_node *next = n->next;
**pprev = n->pprev;
// Since there is always a pointer which points to node n,
// no special case is needed to deal with.
*pprev = next;
if (next)
next->pprev = pprev;
}
```
跟典型 doubly-linked list 的實作做比較，由於該實作的 `prev` 指標必須指向 `struct dll_node` 型別，導致第一個節點會出現指向 `NULL` 的狀況；而將其替換成指標的指標後，便可順利消除這個特例。
至此，我們理解到，hash list 是為雜湊表特製的鏈結串列，儘管雙向鏈結串列亦可實作雜湊表，但由於後者開頭和結尾需要各用 2 個指標，當 bucket 很大時，會增加記憶體開銷。
相較於 `list_head` 的兩個指標，`hlist_head` 僅需要保存一個指標，`hlist_node` 的 `next` 指向下個節點，但 `pprev`（指標的指標) 並不指向上個節點，而是指向上個節點的 `next` 指標，這樣設計的好處是，當要刪除的節點是首個節點，即可藉由 `*pprev = next` 直接修改指標的指向。
延伸閱讀:
* [核心基礎設施: `hlist_head`/`hlist_node` 結構解析](http://linux.laoqinren.net/kernel/hlist/)
* [hlist 資料結構圖示說明](https://zhuanlan.zhihu.com/p/82375193)
---
## `Eddielin0926`
### quiz2-4
先觀察原本函式的功能
- `bitmap` 是要處理的資料，以 64 bits 為區間
- `bitmapsize` 是總共有要處的資料大小
- `out` 是結果存放的位置
在第一層迴圈中 `bitset` 會儲存目前處理資料，第二層的迴圈目的是要找到資料的位元是 1 的位置並且去除掉 1 後，將位置記錄在 `out` 中。
```c
#include <stddef.h>
size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
size_t pos = 0;
for (size_t k = 0; k < bitmapsize; ++k) {
uint64_t bitset = bitmap[k];
size_t p = k * 64;
for (int i = 0; i < 64; i++) {
if ((bitset >> i) & 0x1)
out[pos++] = p + i;
}
}
return pos;
}
```
嘗試一個簡單的[例子](https://onlinegdb.com/qxgIaXhvp)
```
bitmap[0] = 0x11
bitmapsize = 1
```
我們可以得到 `bitmap` 中 1 的數量以及 1 的位置
```
pos = 2
out = {0, 4}
```
接下來透過 [`__builtin_ctzll`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 將函式改寫
`__builtin_ctzll` 用來找到由低位往高位的第一個 1 中間會有幾個 0，因此可以用來取代重複判斷的 `if ((bitset >> i) & 0x1)` ，就能減少分支的次數，在硬體有支援的情況下可以加速運算，再來看 `while` 的條件是 `bitset != 0`，加上 `__builtin_ctzll` 的特性，因此我們可以知道，當我們找到 `bitset` 的 1 時，要將 1 去處除掉，才有辦法利用 `__builtin_ctzll` 計算 1 的位置。
```c
#include <stddef.h>
size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
size_t pos = 0;
uint64_t bitset;
for (size_t k = 0; k < bitmapsize; ++k) {
bitset = bitmap[k];
while (bitset != 0) {
uint64_t t = bitset & -bitset;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
當我們在思考如何去除掉某個位元的 1 時，第一個想法可能會是與一個在對應位置的 0 做 bitwise AND
```c
bitset &= ~(1 << r)
```
<!--
```
bitset = ((bitset >> (r + 1)) << r)
```
-->
但在這邊的做法利用了**二補數**來去除最低位元的 1。
```c
bitset ^= bitset & -bitset
```
在我們剛剛的計算中，我們目標都是 `bitset` 中最低位的 1，例如 XXX**1**00。
當我們對 `bitset` 做二補數計算時，最低位的 1 左邊的位元會是原本的補數，右邊則會與原本一樣。
$$
0110100_2 \xrightarrow{取二補數} 1001100_2 \\
0110100_2 \land 1001100_2 = 0000100_2 \\
0110100_2 \oplus 0000100_2 = 0110000_2
$$
與原本的 `bitset` 做 XOR 就能將最右邊的 1 變成 0 了。
### quiz2-1
對二個無號整數取平均值
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (a & b & 1);
}
```
`a >> 1` 和 `b >> 1` 代表將 a 和 b 個別除以 2，`a & b & 1` 用來檢查兩個數是不是都是奇數。
另一個對二個無號整數取平均值的實作。
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (a & b) + ((a ^ b) >> 1);
}
```
我認為可以想像成全加器除二。
原本是 `(a + b) >> 1`，將 carry 提出來後就變成 `(a & b) + ((a ^ b) >> 1)`。
---
## `william40614`, `millaker`
先分析原程式，參考〈[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)〉一文的「不需要分支的設計」一節提供的程式碼 `min`，改寫為以下程式碼: (其中 `EXP4` 和 `EXP5` 尚未實作)
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
運用 [The XOR trick](https://florian.github.io/xor-trick/) 提及的規律:
* `a ^ a = 0`
* `a ^ 0 = a`
* `a ^ ANY ^ ANY = a`
關於 `EXP5`，只要 `a < b` 成立，也就是 `1`, 加上負號後得到 `-1` (`0xffffffff`)，原本的表示式成為:
* `-1 ＆ (a ^ b) = (a ^ b)`
* `a ^ a ^ b = 0 ^ b = b`
可推得 max 是 b 。相反地，當 `a > b` 成立，後面一整項為 `0`，回傳值就會是 `a`。
---
## `Tcc0403`
第 2 周測驗 3
### 分析程式碼
```c
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
if (!u || !v) return u | v;
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
while (!(u & 1))
u /= 2;
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u<<shift;
}
```
GCD 演算法
1. If both x and y are 0, gcd is zero $gcd(0, 0) = 0$.
2. $gcd(x, 0) = x$ and $gcd(0, y) = y$ because everything divides 0.
3. If x and y are both even, $gcd(x, y)=2 \times gcd(\dfrac{x}{2},\dfrac{y}{2})$ because $2$ is a common divisor. Mulitplication with $2$ can be done with betwise shift operator.
4. If x is even and y is odd, $gcd(x, y) = gcd(\dfrac{x}{2}, y)$.
5. On similar lines, if x is odd and y is even, then $gcd(x, y) = gcd(x, \dfrac{y}{2})$. It is because $2$ is not a common divisor.
以下分段說明：
```c
if (!u || !v) return u | v;
```
$\to$ 對應至 GCD 演算法第 2 點
* $gcd(x,0)=x$ and $gcd(0, y)=y$ because everything divides 0.
若 u 和 v 中其中一數為 0 ，則直接回傳另一數
> `x | 0` 會得到 x
```c
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
$\to$ 對應至 GCD 演算法第 3 點
* If x and y are both even, $gcd(x, y) = 2 \times gcd(\dfrac{x}{2},\dfrac{y}{2})$ because $2$ is a common divisor. Mulitplication with $2$ can be done with betwise shift operator.
先取出`u` 和 `v` 之間屬於 $2^n$ 的公因數，`shift` 即為最大的 $n$
```c
while (!(u & 1))
u /= 2;
```
$\to$ 對應至 GCD 演算法第4 點
* If x is even and y is odd, $gcd(x, y) = gcd(\dfrac{x}{2}, y)$.
當 `u` 為偶數時，可以除以 $2$
```c
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
```
$\to$ 其中 `while(!(v &1)) v /= 2;` 對應至 GCD 演算法第 5 點
* On similar lines, if x is odd and y is even, then $gcd(x, y) = gcd(x, \dfrac{y}{2})$. It is because $2$ is not a common divisor.
可以透過迴圈不變性 (loop invariant) 來幫助解讀程式
* `u` 為被除數
* `v` 為除數
當除數 `v`為 0 時結束迴圈，被除數 `u` 為進入迴圈前 `u` 和 `v` 的最大公因數
:::warning
事實上 `u` 在迴圈前不一定是被除數，因為先前透過 GCD 演算法第 4 點去除不必要的計算
:::
```c
return u << shift;
```
最後回傳最大公因數時，乘上原先取出屬於 $2^n$ 的公因數，可以透過左移達成
### 透過 `__builtin_ctz` 改寫程式
已知除法運算會耗費較多時間，我們可以利用 `__builtin_ctz` (編譯器會產生對應到現代微處理器的專門指令) 搭配上述針對二進位特性調整的演算法，減少除法的使用
改寫之前先透過 perf 分析程式，將一百萬組由 `rand` 函式生成的亂數傳入 `gcd64` 函式執行
```shell
$ gcc -g3 -O0 gcd.c -o gcd
$ perf record ./gcd
$ perf annotate
```
由上圖可以發現，花費 CPU 週期數最多的段落為迴圈當中的 `v /= 2` 運算，佔據約 28%
以下為改寫過後的程式
```c
uint64_t gcd64_ctz(uint64_t u, uint64_t v)
{
if (!u || !v) return u | v;
int shift = __builtin_ctzll(u | v);
u = u >> __builtin_ctzll(u);
do {
v = v >> __builtin_ctzll(v);
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << shift;
}
```
透過 perf 分析前後差異
```shell
$ gcc -g -O0 gcdcmp.c -o gcdcmp
$ perf record ./gcdcmp
$ perf report
```
將同樣一百萬筆由 `rand` 函式所產生的亂數傳入 `gcd64` 和 `gcd64_ctz` 函式比較，發現改寫過後的版本花費時間幾乎是原來的一半
### 改進空間
透過 perf 分析改寫程式
```shell
$ gcc -g -O0 gcd_ctz.c -o gcd_ctz
$ perf record ./gcd_ctz
$ perf annotate
```
佔據花費時間最多的為分支指令 (如 [jne](https://www.aldeid.com/wiki/X86-assembly/Instructions/jnz))，其次是迴圈內部的減法運算
---
## `kdnvt`
為什麼有 `list_for_each_safe` 還需要 `list_for_each`?
`list_for_each` 是 `list.h` 中定義的巨集，用來走訪 linked list 中的各個節點。
以下是實作方式：
```
#define list_for_each(pos, head) \
for (pos = (head)->next; !list_is_head(pos, (head)); pos = pos->next)
```
程式的邏輯十分單純，判斷 `pos` 是不是等於 `head` 來當作結束條件，並在每次迴圈結尾讓 `pos = pos->next` 來走訪。但如果在走訪的過程中，改變了 `pos->next` ，就可能造成不可預期的行為。因此有了 `list_for_each_safe` 。
`list_for_each_safe` 會用到的地方，主要在走訪的過程中，會更改到當前節點（如將當前節點移出）的時候。
想要知道它是如何在更改節點的時候，仍然可以正確的走訪各個節點，就是直接看這個巨集的實作細節：
```
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; \
!list_is_head(pos, (head)); \
pos = n, n = pos->next)
```
可以看到除了當前的節點 `pos` ，它還用了另一個指標 `n` 去指向下一個節點。當目前的節點執行完了，當會在迴圈的結尾讓 `pos = n` ，再讓 `n` 指向 `pos->next` 。如此一來，就算 `pos` 在走訪的過程被移出，也有 `n` 這個指標去暫存下一個節點的位址，所以可以安全的走訪所有節點。
若沒有要改變節點的連接方式，如 `q_size` 中走訪各節點被計算總數，則使用 `list_for_each` 就好。如果在這種情況下還使用 `list_for_each_safe` ，則要額外準備一個指標去暫存下一個節點，然而這個指標在走訪個過程中其實是不需要的。
## `mickey30606`
如何將以下程式碼，修改成取得最接近且小於等於 2 的冪的值。
```clike
uint64_t next_pow2(uint64_t x)
{
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 1;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
return x+1;
}
```
- 方法一：我們只需要將目前最高位的 1 後面位元全部都變成 0 就可以得到我們想要的結果，而原本程式就已經將 `x` 後面位元全部都變成 1 ，所以我們只需要將 `x` 往右推移 1 並與自己進行 XOR 即可得到答案。
```clike
uint64_t next_pow2(uint64_t x)
{
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
return x ^ (x >> 1);
}
```
- 方法二：使用 `__builtin_clzl` 進行改寫，取得最高位的 1 前面有幾個 bit 之後，用 1 進行推移就可以得到答案。
```clike
uint64_t next_pow2(uint64_t x)
{
return 1 << (63 - __builtin_clzl(x));
}
```
Sign in with Wallet
Connect another wallet