---
tags: linux2022
---
# 2022q1 Homework2 (quiz2)
contributed by < [ShiaoLin](https://github.com/ShiaoLin) >
[作業要求](https://hackmd.io/@sysprog/linux2022-homework2#%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)
## 測驗 `1`
### 解釋程式碼運作的原理
對二個無號整數取平均值的程式碼，我們可改寫為以下等價的實作:
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
`a` 與 `b` 皆為無號數，向右邏輯位移 `1` 位乍看之下等同於兩數的一半相加，在算術上的邏輯是成立的，但是考量到 `bits` 的表達方式，`a` 與 `b` 各自向右移位會導致 `bit 0` 被忽略掉，在此之上要補回對於 `bit 0` 的運算。
以下以無號數 4 位元簡單表示：
| | Raw | shift right|
| ------ | ------- | ------- |
| a | 1 0 0 1 | 0 1 0 0 |
| b | 1 0 0 0 | 0 1 0 0 |
| result | x | 1 0 0 0 |
上述表格透過直接右移一位於結果來說沒有問題，但是下面表格就會出現錯誤了
| | Raw | shift right|
| ------ | ------- | ------- |
| a | 1 0 0 1 | 0 1 0 0 |
| b | 1 0 0 1 | 0 1 0 0 |
| result | x | 1 0 0 0 |
可以看到我們預期 `a` 與 `b` 的平均結果應該是 `1001`，所以我們必須對於 `bit 0` 進行修正，也就是加上 `a & b & 1` 去檢查兩數 `bit 0` 的狀況
我們再次改寫為以下等價的實作:
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
我們可以透過 `a + b` = ` (a & b) << 1 + a ^ b` 進行操作，也就將 `(a + b)` 進行邏輯右移取得平均值，也就是 `a & b + (a ^ b) >> 1`
### 比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出
使用指令進行編譯器最佳化的觀察
```
gcc -S -Og filename.c
```
會得到 `filename.s` 這個編譯到一半的檔案，其中可以觀察各程式轉變為組合語言的指令對應
首先觀察最一開始的取平均做法
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a + b) / 2;
}
```
會得到如下的結果
```
average:
.LFB0:
.cfi_startproc
endbr64
leal (%rdi,%rsi), %eax
shrl %eax
ret
.cfi_endproc
```
`endbr64` 的解釋[What does the endbr64 instruction actually do?](https://stackoverflow.com/questions/56905811/what-does-the-endbr64-instruction-actually-do)
`leal (%rdi,%rsi), %eax`，表示將 `(%rdi,%rsi)` 處理完後的地址加載到 `%eax` 這個地址去，`lea` 指令不儘可以處理加法也可以處理乘法，相較於 `add` 或 `mul` 來說節省了一道後續 `mov` 指令，可以在大量的組合語言中看到 `lea` 的使用
`shrl %eax` 則是將 `%eax` 做右移一位的處理，等同於將值除以 `2` 的操作
接下來觀察改寫後的操作
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
會得到下列結果
```
average:
.LFB0:
.cfi_startproc
endbr64
movl %edi, %eax
shrl %eax
movl %esi, %edx
shrl %edx
addl %edx, %eax
andl %esi, %edi
andl $1, %edi
addl %edi, %eax
ret
.cfi_endproc
```
得到了相對多於上述操作的組合語言指令，雖然指令上使用的較多，但是是相對獲得防止 `overflow` 的作法
同樣觀察下列操作的組合語言
```
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a & b) + ((a ^ b) >> 1);
}
```
```
average:
.LFB0:
.cfi_startproc
endbr64
movl %edi, %eax
andl %esi, %eax
xorl %esi, %edi
shrl %edi
addl %edi, %eax
ret
```
同樣防止溢位，此次操作又比上述的操作少了一些指令
### 研讀 Linux 核心原始程式碼 [include/linux/average.h](https://github.com/torvalds/linux/blob/master/include/linux/average.h)，探討其 [Exponentially weighted moving average (EWMA) ](https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average)實作，以及在 Linux 核心的應用
根據[移動平均](https://zh.wikipedia.org/wiki/%E7%A7%BB%E5%8B%95%E5%B9%B3%E5%9D%87)的定義，相較於一般的平均數的操作，移動平均會對於新加入的值提升權重，使新值影響移動平均較大，以下是核心定義設時間 $t$ 的實際數值為 $Y_t$，而時間 $t$ 的 `EMA` 則為$S_t$；時間 $t-1$ 的 `EMA` 則為 $S_{t-1}$，計算時間 $t≥2$ 是方程式為
$S_t = α * Y_t + (1 - α)Y_{t-1}$
接下來觀察 `linux` 中相關的 `EMA` 程式碼，透過 `macro` 宣告包含初始化結構體、讀取結構體的值以及增加新值至原先結構體的方法
```
#define DECLARE_EWMA(name, _precision, _weight_rcp)
```
這邊有 `3` 個參數， `name` 表示結構體的命名， `_precision` 表示用多少 `bits` 儲存值的小數部分，`_weight_rcp` 表示為加權數，這邊為 $α$ 的倒數
這邊觀察到程式碼內大量使用的以下的錯誤檢查式
```
BUILD_BUG_ON(!__builtin_constant_p(_precision));
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));
BUILD_BUG_ON((_precision) > 30);
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);
```
其中 `BUILD_BUG_ON` 表示括號內的表達數如果出現 `false` 則強制讓編譯器出現錯誤，`BUILD_BUG_ON` 的原定義來自於 `BUILD_BUG_ON_ZERO`，相關操作可參[bit-field](https://hackmd.io/@sysprog/c-bitfield#Linux-%E6%A0%B8%E5%BF%83-BUILD_BUG_ON_ZERO)的說明
```c
static inline void ewma_##name##_add(struct ewma_##name *e, \
unsigned long val) \
{ \
unsigned long internal = READ_ONCE(e->internal); \
unsigned long weight_rcp = ilog2(_weight_rcp); \
unsigned long precision = _precision; \
\
BUILD_BUG_ON(!__builtin_constant_p(_precision)); \
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp)); \
BUILD_BUG_ON((_precision) > 30); \
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp); \
\
WRITE_ONCE(e->internal, internal ? \
(((internal << weight_rcp) - internal) + \
(val << precision)) >> weight_rcp : \
(val << precision)); \
}
```
`READ_ONCE` 以及 `WRITE_ONCE` 是為了避免不同 `thread` 同時進行操作導致數值存取錯誤的問題發生，`ilog2` 則是返回某數以 `2` 為底的整數部分，以利後續使用位移進行快速操作方便，這段程式碼的關鍵就在於 `WRITE_ONCE` 中的參數其中的分支，若 `internal` 為 `0`，則 `e->internal = val << precision`，等同於$S_t = α * Y_t$，而 `internal` 不為 `0` 時，等同於完整的表達式$S_t = α * Y_t + (1 - α)Y_{t-1}$
## 測驗 `2`
### 解釋程式碼運作原理
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
利用 `XOR` 的特性思考：
* `a ^ 0 = a`
* `a ^ a = 0`
* `a ^ (a ^ b)` 因具備結合律等同於 `(a ^ a) ^ b = b`
假設 `EXP4` 為 `a ^ b`，則 `-(EXP5)` 則必須具備表達 `a` 與 `b` 的大小關係式
進一步假設如果 `EXP5` 為 `a > b` 或 `a >= b` 時：
* 當 `a >= b` 為真， `return a ^ ((a ^ b) & -1)` 其結果為 `return b`，假設與結果不符
* 當 `a < b` 為真， `return a ^ ((a ^ b) & 0)` 其結果為 `return a`，同樣假設與結果不符
故得知 `EXP5` 的正確表達式為 `a < b`
### 針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作
參考[不需要分支的設計](https://hackmd.io/@sysprog/binary-representation#%E4%B8%8D%E9%9C%80%E8%A6%81%E5%88%86%E6%94%AF%E7%9A%84%E8%A8%AD%E8%A8%88)將有 32 位有號數較小值的函式作修改
```c
int32_t max(int32_t a, int32_t b) {
int32_t diff = (a - b);
return a - (diff & (diff >> 31));
}
```
### 請在 Linux 核心原始程式碼中，找出更多類似的實作手法
## 測驗 `3`
### 解釋程式運作原理
```c
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
根據備註 3. If x and y are both even, gcd(x,y)=2∗gcd(x2,y2) because 2 is a common divisor. Multiplication with 2 can be done with bitwise shift operator.
若 `u` `v` 兩數皆為偶數則先共同約去 `2`，用 `shift` 紀錄約去的次數
```c
while (!(u & 1))
u /= 2;
```
根據備註 4. If x is even and y is odd, gcd(x,y)=gcd(x2,y).
如果 `u` 為偶數，則可先約去 `2` 的冪部份，因為與奇數的最大公因數不會有 `2` 的冪存在
```c
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (COND);
return RET;
```
根據備註 5. On similar lines, if x is odd and y is even, then gcd(x,y)=gcd(x,y2). It is because 2 is not a common divisor.
同樣的，對 `v` 進行備註 4 的處理方式後，就可以就剩下的數字進行最大公因數的尋找，這邊參考[輾轉相除法](https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95)，而輾轉相除法的停止條件是餘數為零，也就是 `u - v` 的結果，故 `COND = v`，而最後回傳值除了剩餘的 `u` 之外，還要包含上方若有對 `2` 進行約分的部份，也就是 `RET = u << shift`
### 在 x86_64 上透過 `__builtin_ctz` 改寫 GCD，分析對效能的提升
### Linux 核心中也內建 GCD (而且還不只一種實作)，例如 [lib/math/gcd.c](https://github.com/torvalds/linux/blob/master/lib/math/gcd.c)，請解釋其實作手法和探討在核心內的應用場景
## 測驗 `4`
```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 = EXP6;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
思考 `-bitwise` 的特性，`-bitwise = ~bitwise + 1`，所以當 `bitwise & -bitwise` 時會留下 `bitwise` 最靠近右端的 `1`，最後再透過 `bitwise ^= t` 去掉最右端的 `1`
`EXP6` 為 `bitset & -bitset`
## 測驗 `5`
```c
/* Using a map to record all of reminders and their position.
* if the reminder appeared before, which means the repeated loop begin,
*/
char *decimal = malloc(size);
memset(decimal, 0, size);
char *q = decimal;
size = 1333;
struct list_head *heads = malloc(size * sizeof(*heads));
for (int i = 0; i < size; i++)
INIT_LIST_HEAD(&heads[i]);
for (int i = 0; remainder; i++) {
int pos = find(heads, size, remainder);
if (pos >= 0) {
while (PPP > 0)
*p++ = *decimal++;
*p++ = '(';
while (*decimal != '\0')
*p++ = *decimal++;
*p++ = ')';
*p = '\0';
return result;
}
struct rem_node *node = malloc(sizeof(*node));
node->key = remainder;
node->index = i;
MMM(&node->link, EEE);
*q++ = (remainder * 10) / d + '0';
remainder = (remainder * 10) % d;
}
```
在 `hash table` 中的元素建立資料，第一次進入 `for` 迴圈時由於 `pos` 從 `find` 的回傳值為 `-1`，所以會進行新增節點的動作，故 `MMM` 為 `list_add`，而節點的插入點 `EEE` 為 `&heads[remainder % size]`
而 `PPP` 與 `pos` 相關，當循環小數不從小數點後一位開始時， `*p++ = *decimal++;` 會先記錄循環小數開始前的數字，故 `PPP` 為 `pos--`
## 測驗 `6`
```c
#define ALIGNOF(t) \
((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X)
```
參考 `container_of` 的巨集，以 `char*` 指針形式回傳的 `struct { char c; t _h; } *` 結構體指針，透過 `0` 指針指向 `t` 型態的地址，再減去作為開頭 `char* 0` 的偏移量，故 `M = _h`，`X = 0`
## 測驗 `7`
```c
string literal: "fizzbuzz%u"
offset: 0 4 8
```
根據 `string literal` 的長度思考：
| | 字串長度 | `Offset` |
| --------------| -------- | -------- |
| `3`非`5`的數 | 4 | 0 |
| `5`非`3`的數 | 4 | 4 |
| `3`且`5`的數 | 8 | 0 |
| 非`3`非`5`的數 | 2 | 8 |
觀察結果發現不論是字串長度與 `Offset` 皆為 `2` 的冪，所以剛好符合 `KK1 = div3` 及 `KK2 = div5`
再來關於 `(9 >> div5) >> (KK3)` 的部份，套入上表格可得到
| | 字串長度 | `(9 >> div5) >> (KK3)` | `KK3` |
| -------------- | -------- | ---------------------- | --- |
| `3`非`5`的數 | 4 | 0 | 3 |
| `5`非`3`的數 | 4 | 4 | 0 |
| `3`且`5`的數 | 8 | 0 | 2 |
| 非`3`非`5`的數 | 2 | 8 | 0 |
題目有誤，應修正為 `(8 >> div5) >> (KK3)` 且 `KK3 = div3 <<2`
Sign in with Wallet
Connect another wallet