---
tags: linux2022
---

# 第 1,2 週課堂問答簡記

## `Uduru0522`

Linux 核心的 hash table 實作中，用以處理 hash 數值碰撞的 `hlist_node`:

struct hlist_node {
    struct hlist_node *next, **pprev;
};

**其中 `pprev` 為何要宣告為==指標的指標==？**
探討典型 doubly-linked list delete 會產生的問題。

考慮我們使用典型的 doubly-linked list:

struct dll_node { 
    struct dll_node *next, *prev;
}

> `dll` 是 doubly-linked list 的簡稱

於是資料結構會展現如下圖:

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():`

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`:

struct hlist_node { 
    struct hlist_node *next, **pprev;
}

則會形成以下的結構：

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()`：

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` 中。

#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 的位置。

#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

bitset &= ~(1 << r)

<!--

bitset = ((bitset >> (r + 1)) << r)

-->

但在這邊的做法利用了**二補數**來去除最低位元的 1。

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

對二個無號整數取平均值

#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` 用來檢查兩個數是不是都是奇數。

另一個對二個無號整數取平均值的實作。

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` 尚未實作)

#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

### 分析程式碼

#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.

以下分段說明：

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

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$

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$

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 點去除不必要的計算
:::

return u << shift;

最後回傳最大公因數時，乘上原先取出屬於 $2^n$ 的公因數，可以透過左移達成

### 透過 `__builtin_ctz` 改寫程式
已知除法運算會耗費較多時間，我們可以利用 `__builtin_ctz` (編譯器會產生對應到現代微處理器的專門指令) 搭配上述針對二進位特性調整的演算法，減少除法的使用

改寫之前先透過 perf 分析程式，將一百萬組由 `rand` 函式生成的亂數傳入 `gcd64` 函式執行

$ gcc -g3 -O0 gcd.c -o gcd
$ perf record ./gcd
$ perf annotate


由上圖可以發現，花費 CPU 週期數最多的段落為迴圈當中的 `v /= 2` 運算，佔據約 28%

以下為改寫過後的程式

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 分析前後差異

$ gcc -g -O0 gcdcmp.c -o gcdcmp
$ perf record ./gcdcmp
$ perf report


將同樣一百萬筆由 `rand` 函式所產生的亂數傳入 `gcd64` 和 `gcd64_ctz` 函式比較，發現改寫過後的版本花費時間幾乎是原來的一半

### 改進空間

透過 perf 分析改寫程式

$ 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 的冪的值。

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 即可得到答案。

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 進行推移就可以得到答案。

uint64_t next_pow2(uint64_t x)
{
    return 1 << (63 - __builtin_clzl(x));
}