--- tags: linux2024 --- # [2024q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 4 週測驗題 :::info 目的: 檢驗學員對 bitwise 和 [rbtree](https://hackmd.io/@sysprog/linux-rbtree) 的認知 ::: ==[作答表單: 測驗 1-2](https://docs.google.com/forms/d/e/1FAIpQLSe1JKHvdSyEWpkMux5YQ7uReAC4BJw0hp5LykxzF_M6mHwF_A/viewform)== (針對 Linux 核心「設計」課程) ==[作答表單: 測驗 3](https://docs.google.com/forms/d/e/1FAIpQLSfmtwv2i53ID3mlTF3ST4p1kHnP066ooTKc14KyUhY6hmeKtQ/viewform)== (針對 Linux 核心「實作」課程) ### 測驗 `1` [population count](https://en.wikichip.org/wiki/population_count) 簡稱 popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 `1`，在一些場合下很有用，例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 `0` 元素個數、計算兩個字串的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_weight)。Intel 在 2008 年 11 月 Nehalem 架構的處理器 Core i7 引入 SSE4.2 指令集，其中就有 `CRC32` 和 `popcount` 指令，`popcount` 可處理 16-bit, 32-bit, 64-bit 整數。 對應到 C 程式的實作: ```c unsigned popcount_naive(unsigned v) { unsigned n = 0; while (v) v &= (v - 1), n = -(~n); return n; } ``` 函式 `popcount_naive()` 利用不斷清除 LSB 直到輸入的數值 `v` 為 0。 `v &= (v - 1)` 的作用是將 LSB 設為 0 (**reset LSB**) 舉例來說，假設輸入數值為 `20`: ```c 0001 0100 # 20 ; LSB in bit position 2 0001 0011 # 20 - 1 0001 0000 # 20 & (20 - 1) ``` > 類似的操作還有 `x & -x`，將 `x` 的 LSB 取出 (**isolate LSB**) `n = -(~n)` 等同 `n++`，因為在二補數系統中， $-n =\ \sim n + 1$ $-(\sim n) = n + 1$ 因此 `popcount_naive()` 的執行時間取決於輸入數值中 1 (set bit) 的個數。可改寫為以下常數時間複雜度的實作: ```c unsigned popcount_branchless(unsigned v) { unsigned n; n = (v >> 1) & 0x77777777; v -= n; n = (n >> 1) & 0x77777777; v -= n; n = (n >> 1) & 0x77777777; v -= n; v = (v + (v >> 4)) & 0x0F0F0F0F; v *= 0x01010101; return v >> 24; } ``` 對於一個 32 bit 的無號整數，popcount 可以寫成以下數學式: $popcount(x) = x - \left \lfloor{{\dfrac{x}{2}}}\right \rfloor - \left \lfloor{{\dfrac{x}{4}}}\right \rfloor - ... - \left \lfloor{{\dfrac{x}{2^{{31}}}}}\right \rfloor$ 假設 $x = b_{31}...b_3b_2b_1b_0$，先看看 $x[3:0]$ 4 個位元，用以上公式可以計算得: $(2^3b_3 + 2^2b_2 + 2^1b_1 + 2^0b_0) - (2^2b_3 + 2^1b_2 + 2^0b_1) - (2^1b_3 + 2^0b_2) - 2^0b_3$ > $\left \lfloor{{\dfrac{x}{2}}}\right \rfloor$ 相當於 C 表達式中 `x >> 1` 稍微改寫可得到: $(2^3 - 2^2 - 2^1 - 2^0)b_3 + (2^2 - 2^1 - 2^0)b_2 + (2^1 - 2^0)b_1 + 2^0b_0$ 因此 popcount 的一般式可改寫為: $popcount(x) = \sum\limits_{n=0}^{31} {}(2^n - \sum\limits_{i=0}^{n-1} 2^{i})b_n = \sum\limits_{n=0}^{31}b_n$ 因為 $2^n - \sum\limits_{i=0}^{n-1} 2^{i} = 1$，只要對應的 $b_n$ 為 1，這個 bit 就會在 popcount 的總和中加一，剛好對應 `popcount_naive()`，因此映證上述數學式確實可計算出 population count。 且一個 32 位元無號整數最多有 32 個 1 (set bit)，剛好可用一個 byte 表示，所以可分成幾個區塊平行計算，最後再全部加總到一個 byte 中，進行避免檢查 32 次。 `popcount_branchless` 實作一開始以**每 4 個位元 (nibble) 為一個單位**計算 1 的個數，利用最初的公式計算 $x - \left \lfloor{{\dfrac{x}{2}}}\right \rfloor - \left \lfloor{{\dfrac{x}{4}}}\right \rfloor - \left \lfloor{{\dfrac{x}{8}}}\right \rfloor$ 關鍵的程式碼，逐行解釋: ```c= n = (v >> 1) & 0x77777777; v -= n; n = (n >> 1) & 0x77777777; v -= n; n = (n >> 1) & 0x77777777; v -= n; ``` 1. `n = (v >> 1) & 0x77777777` : 將輸入數值 `v` 除以 2，得到 $\left \lfloor{{\dfrac{v}{2}}}\right \rfloor$ ```c b_31 b_30 b_29 b_28 ... b7 b6 b5 b4 b3 b2 b1 b0 // v 0 b_31 b_30 b_29 ... 0 b7 b6 b4 0 b3 b2 b1 // (v >> 1) & 0x77777777 ``` 2. `v -= n` : 計算結果相當於 $v - \left \lfloor{{\dfrac{v}{2}}}\right \rfloor$ 3. `n = (n >> 1) & 0x77777777` : 再對 `n` 除以 2，得到 $\left \lfloor{{\dfrac{v}{4}}}\right \rfloor$ 4. `v -= n` : 計算出 $v - \left \lfloor{{\dfrac{v}{2}}}\right \rfloor - \left \lfloor{{\dfrac{v}{4}}}\right \rfloor$ 5. 和 6. 重複同樣動作 最後這段結束後計算出 $v - \left \lfloor{{\dfrac{v}{2}}}\right \rfloor - \left \lfloor{{\dfrac{v}{4}}}\right \rfloor - \left \lfloor{{\dfrac{v}{8}}}\right \rfloor$，得到每 4 個位元為一個單位中 set bit 的個數 **`v = (v + (v >> 4)) & 0x0F0F0F0F`** : 將每 4 個位元中 set bit 的個數加到 byte 中: 1. 假設 $B_n$ 代表第 n 個 nibble (4 位元) 中的數值 ```c B7 B6 B5 B4 B3 B2 B1 B0 // v 0 B7 B6 B5 B4 B3 B2 B1 // (v >> 4) ``` 2. 加總可得到: ```c // (v + (v >> 4)) B7 (B7+B6) (B6+B5) (B5+B4) (B4+B3) (B3+B2) (B2+B1) (B1+B0) ``` 3. 最後使用 `0x0F0F0F0F` 做 mask 可得 ```c // (v + (v >> 4)) & 0x0F0F0F0F 0 (B7+B6) 0 (B5+B4) 0 (B3+B2) 0 (B1+B0) ``` **`v *= 0x01010101`** : 在最後一道敘述中，將 `v` 乘上 `0x01010101`。寫成直式如下 ``` 0 A6 0 A4 0 A2 0 A0 x 0 1 0 1 0 1 0 1 --------------------------------------------------- 0 A6 0 A4 0 A2 0 A0 0 A6 0 A4 0 A2 0 A0 0 0 A6 0 A4 0 A2 0 A0 0 0 A6 0 A4 0 A2 0 A0 0 --------------------------------------------------- ↑_______________________A6+A4+A2+A0 ``` 我們可發現期望輸出就在原本 $A_6$ 的位置 ($2^7$)，因此將 `v` 右移 24 bits 即為所求，剩下的位數會 overflow ，右移後不影響結果。 * 假設 $A = B_7 + B_6$, $B = B_5 + B_4$, $C = B_3 + B_2$, $D = B_1 + B_0$, 根據分配律可得: ``` v * 0x01010101 = (A + B + C + D) (B + C + D) (C + D) (D) |<-- 1 byte -->|<-- 1 byte -->|<-- 1 byte -->|<-- 1 byte -->| ``` **`return v >> 24`** : 最後得到的結果會放在 Most significant byte 中，因此向右位移 24 位元，即為所求的 popcount 值。 GCC 提供對應的內建函式: > `__builtin_popcount(x)`: 計算 x 的二進位表示中，總共有幾個 `1` 使用示範： ```c int x = 5328; // 00000000000000000001010011010000 printf("%d\n", __builtin_popcount(x)); // 5 ``` 兩個整數間的 Hamming distance 為其二進位的每個位元的差 Example : 1 (0 0 0 1) 4 (0 1 0 0) hamming distance = 2 | A $\oplus$ B | B = 0 | B = 1 | | -------- | -------- | -------- | | A = 0 | 0 | 1 | | A = 1 | 1 | 0 | `A ^ B`　就為二進位中兩數字的每個位元的差，再透過　popcount() 就可以得到答案 ```c int hammingDistance(int x, int y) { return __builtin_popcount(x ^ y); } ``` 針對 [LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)，考慮以下程式碼: ```c int totalHammingDistance(int* nums, int numsSize) { int total = 0;; for (int i = 0;i < numsSize;i++) for (int j = 0; j < numsSize;j++) total += __builtin_popcount(nums[i] ^ nums[j]); return total >> AAAA; } ``` 從 popcount 角度出發，時間複雜度就被限制在 $O(n^{2})$。 以下嘗試從位元展現的樣貌，觀察 Total Hamming Distance 的規則。 ```graphviz digraph A{ b [shape=record fontsize=24 label="{ n 'th bit|input 7| input 5| input 10|input 17 }|{ 4|0| 0| 0|1 }|{ 3|0| 0| 1 |0}|{ 2|1| 1| 0 |0}|{ 1|1| 0| 1 |0}|{ 0|1| 1| 0 |1}"] } ``` 1. 第 0 個 bit 觀察 : 全部都是 1 -> Hamming Distance = 0 2. 第 1 個 bit 觀察 : 1 有一個，其餘皆為 0 可以直接用單個 bit 判斷 Hamming Distance (1)* (numsize - 1) 3. 第 2 個 bit 觀察 : 1 有兩個，其餘皆為 0 Hamming Distance (2)* (numsize - 2) 以 bit 找規則: > 所有 Number 中從第 0 個 bit 開始計算全部該 bit 的 Hamming Distance ，在全部累加起來就是 Total Hamming Distance 請補完程式碼。 :::success 延伸問題： 1. 參照《[Hacker's Delight](https://en.wikipedia.org/wiki/Hacker%27s_Delight)》和 [CS:APP 第二章](https://hackmd.io/@sysprog/CSAPP-ch2)，解釋上述程式碼運作原理。 2. 不依賴 popcount，嘗試以上述歸納的規則，針對 [LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/) 撰寫出更高效的程式碼。 ::: --- ### 測驗 `2` 摘錄自 [Hacker's Delight](https://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf): **Remainder by Summing digits** 如何不使用任何除法就算出某數除以另一個數的餘數呢？若除數符合 $2^k \pm 1$，則可運用以下手法來達成這個目的。 若 $a \equiv b (mod \ \ m)$ 且 $c \equiv d (mod \ \ m)$ ，則 $a + c \equiv b + d (mod \ \ m)$ 且 $ac \equiv bd (mod \ \ m )$ 假設 $$ a = q_a m + r_1, b = q_b m + r_1, c = q_c m + r_2, d = q_d m + r_2 $$ 再進行運算。 以除數為 3 為例， $1 \equiv 1 (mod \ \ 3)$ 且 $2 \equiv -1 (mod \ \ 3)$ ，將後者不斷的乘上前者可得 $$ 2^k \equiv \begin{cases} 1 (mod \ \ 3), \ \ k \ \ even\\ -1 (mod \ \ 3), \ \ k \ \ odd\\ \end{cases} $$ 因此若 n 的二進位表示為 $b_{n-1}b_{n-2}\cdots b_1 b_0$ ，則 $n = \sum_{i=0}^{n-1} b_i\cdot 2^i$ ，由以上的推論可得 $n \equiv \sum_{i=0}^{n-1} b_i\cdot (-1)^i \ \ (mod \ \ 3)$ 。 將每次得到的位元和遞迴的應用上式直到得到一個小於 3 的數即是餘數，若變成負數則要加上 3 的倍數。 位元和通常又可以利用 population count 這類的函式來得到，因此寫成程式的話可以將上式表示為 `n = popcount(n & 0x55555555) - popcount(n & 0xAAAAAAAA)` 。 利用以下定理可以進一步化簡。 $popcount(x \And \overline{m}) - popcount(x \And m) = popcount(x \bigoplus m) - popcount(m)$ 於是 `n = popcount(n & 0x55555555) - popcount(n & 0xAAAAAAAA)` 可以寫為 `n = popcount(n ^ 0xAAAAAAAA) - 16` ，將此式重複應用於得到的 `n` 上直到 `n` 介於 0~2 ，但為了避免 `n` 變成負數，我們要將它加上一個足夠大的 3 的倍數，文中的例子是加上 39 。範例程式如下 ```c int mod3(unsigned n) { n = popcount(n ^ 0xAAAAAAAA) + 23; n = popcount(n ^ 0x2A) - 3; return n + ((n >> 31) & 3); } ``` 另一種變形是利用 lookup table 。 ```c int mod3(unsigned n) { static char table[33] = {2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1 }; n = popcount(n ^ 0xAAAAAAAA); return table[n]; } ``` `tictactoe.c` 程式統計隨機的井字遊戲，參考執行輸出如下: ``` Win probability for first move with random agents: 0.115 0.102 0.116 0.102 0.131 0.101 0.116 0.102 0.116 Player 1 won 584650 times Player 2 won 288379 times 126971 ties 0.047604 seconds 21.006638 million games/sec ``` 程式碼可見: [tictactoe.c](https://gist.github.com/jserv/9088f6f72a35a1fcaaf1c932399a5624) (部分遮蔽) 其中 `BBBB` 是 hex literal，`CCCC` 是十進位整數。以最精簡的形式撰寫。 :::success 延伸問題： 1. 參照《[Hacker's Delight](https://en.wikipedia.org/wiki/Hacker%27s_Delight)》和 [CS:APP 第二章](https://hackmd.io/@sysprog/CSAPP-ch2)，解釋上述程式碼運作原理。 2. 將上述手法應用於[第三次作業](https://hackmd.io/@sysprog/linux2024-ttt)中，追求更有效的賽局判定機制。 ::: --- ### 測驗 `3` > 搭配 [Linux 核心原始程式碼巨集: `container_of`](https://hackmd.io/@sysprog/linux-macro-containerof), [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree) 考慮 XTree^名稱沒特別意思，不用去Google搜尋^ 是個嘗試兼具 AVL tree 和 red-black tree 部分特性的 binary search tree (BST) 實作，著重在快速的 insert/delete 操作且合理的 lookup 速度。 AVL tree 可確保每個節點的左右子樹高相差不超過 `1`，因此每個節點需要儲存目前高度來計算 balance factor 來決定是否需要旋轉 (rotate)。 red-black tree 則藉由以下規則來達到平衡： 1. 不能有兩個紅色節點相連; 2. 所有從該節點走到其子樹下的末端節點 (leaf) 的上之黑色節點數量必定 XTree 的平衡機制與 AVL tree 相似，利用 hint 來評估是否需要做 rotate，然而 xt_node 的 hint 的計算方式是，其左右節點 hint 最大值 +1 並且只有在被呼叫到 xt_update 時才會被更新。 以下是簡化的圖示，不區分左右節點。 ``` 1 ∟———2 ∟———8 ∟———16 ∟———33 ∟———73 ∟———82 ∟———83 ∟———91 ∟———1000 ͱ———95 ``` 假設目前的 XTree 已經有 1000, 1, 2, 8 插入，接著插入 16 來觀察 - [ ] `xt_insert` 前 ```graphviz digraph Tree{ graph[ordering=out] null0 [shape=point][color=white] null1 [shape=point][color=white] null2 [shape=point][color=white] 1 -> 2 1 -> null0[style=invis] 2 -> 1000 2 -> null1[style=invis] 1000 -> null2[style=invis] 1000 -> 8 } ``` - [ ] `xt_update` 前 ```graphviz digraph Tree{ graph[ordering=out] null0 [shape=point][color=white] null1 [shape=point][color=white] null2 [shape=point][color=white] null3 [shape=point][color=white] 1 -> 2 1 -> null0[style=invis] 2 -> 1000 2 -> null1[style=invis] 1000 -> null2[style=invis] 1000 -> 8 8 -> 16 8 -> null3[style=invis] } ``` - [ ] 對 16 進行 `xt_update` 由於 16 沒有左側或右側節點，因此不會做任何動作，但是由於 16 的 hint 為 0，所以會對其親代節點 8 進行更新。 - [ ] 對 8 做 `xt_update` 由於 `xt_balance` 為 1，因此不會做任何動作，但由於 8 的 hint 有經過更改 (0 -> 1) 所以會對其親代節點 1000 做進行更新。 - [ ] 對 1000 做 `xt_update` 旋轉完畢後，由於 1000 的 hint 沒有改變 (1->1)，因此結束。 ```graphviz digraph Tree{ graph[ordering=out] null0 [shape=point][color=white] null1 [shape=point][color=white] null2 [shape=point][color=white] null3 [shape=point][color=white] 1 -> 2 1 -> null0[style=invis] 2 -> 8 2 -> null1[style=invis] 8 -> 1000 8 -> null3[style=invis] 1000 -> null2[style=invis] 1000 -> 16 } ``` 由上可知，由於 hint 本身只要沒有改變且不等於 0，就不會往上更新，代表 XTree 只要更新末端節點時，發生 AVL 的 LR 或是 RL，就不會再往上更新。 參見 [XTree 的程式碼](https://gist.github.com/jserv/7374b3e031ec3a81441b1b93b008c5d2) (部分遮蔽)。 作答規範： * `AAAA`, `BBBB`, `CCCC`, `DDDD`, `EEEE`, `FFFF` 皆為表示式 * `BBBB` 和 `DDDD` 為 `xt_` 開頭的表示式 * 不包含空白，以最精簡的形式撰寫 :::success 延伸問題: 1. 解釋上述程式碼運作原理 2. 指出上述程式碼可改進之處，特別跟 AVL tree 和 red-black tree 相比，並予以實作 > 考慮到循序輸入和亂序輸入的狀況 3. 設計效能評比程式，探討上述程式碼和 Linux 核心 red-black tree 效能落差 :::
Last changed by  
 
sysprog
System Software Programming
1404

Read more

2024 年 Linux 核心設計/實作課程作業 —— ktcp

檢驗學員對 Linux 核心 kthread 和 workqueue 處理機制的認知

4/30/2024
並行程式設計: Lock-Free Programming

Lock-Free 和 Lock-Less 的分野 許多文件、程式碼和技術討論會看到 lock-free 和 lockless 字眼，例如 DPDK Programmer’s Guide 就在一份文件中存在上述二個術語。二者的差異是什麼呢？ lock-free: 強調以系統的觀點來看，只要執行足夠長的時間，至少會有一個執行緒會有進展 (progress) lockless: 避免使用 lock 達到安全無誤地操作共用資料 二者有重疊，但重點的議題不同：lockless 著重在實作層面，即不使用 lock 的前提，該如何確保共用資料的正確呢？但不使用 lock 的程式未必會達到 lock-free。更具體來說，下方 Compare-and-swap 搭配迴圈進行等待的程式碼，屬於是 lockless，但不是 lock-free: // Atomically perform UpperBound =max(UpperBound,y) void RecordMax(int y) {

4/29/2024
建構 User-Mode Linux 的實驗環境

自 Linux 核心原始程式碼編譯出 User-mode Linux 並運用工具來建構實驗所需的檔案系統

4/27/2024
你所不知道的 C 語言: 開發工具和規格標準

Copyright (慣C) 2015, 2017 宅色夫

4/27/2024
Read more from sysprog
Published on HackMD