# 2024q1 Homework4 (quiz3+4) contributed by < [`SuNsHiNe-75`](https://github.com/SuNsHiNe-75) > ## 第三週測驗題 ### 測驗`1` #### 解釋程式碼運作原理 ```c int i_sqrt(int x) { if (x <= 1) /* Assume x is always positive */ return x; int z = 0; for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= AAAA) { int b = z + m; z >>= BBBB; if (x >= b) x -= b, z += m; } return z; } ``` AAAA 是 `2`；BBBB 則為 `1`。 該實作的核心思想是一直調整一「猜測值」，來**逐步逼近整數 `x` 的平方根**。 在迴圈中，先計算 `m` 的初始值（對應到公式，即首項 $d_n = (2^n)^2$）。之後將 `z` 與 `m` 相加得到 `b`，`z` 則右移一位。這表示要猜測的平方根 `z` 左移一位。如果 `x` 大於等於 `b`，則表示該猜測值「低於實際的平方根」，所以要把 `x` 減 `b`，然後將 `z` 與 `m` 相加，以調整猜測值。重複此過程，一直到 `m` 變為 `0` 為止。 #### 用 ffs 取代 `__builtin_clz` 使用到 [第 `2` 週－測驗 `3`](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-3) 中定義 `__ffs` 函式來實現 `__builtin_clz` 的取代。 分支版本： ```c int i_sqrt_ffs(int x) { if (x <= 1) return x; int z = 0; for (int m = 1UL << ((31 - __ffs(x)) & ~1UL); m; m >>= 2) { int b = z + m; z >>= 1; if (x >= b) x -= b, z += m; } return z; } ``` 無分支版本： ```c int i_sqrt_ffs_branchless(int x) { if (x <= 1) return x; int z = 0; int m = 1UL << ((31 - __ffs(x)) & ~1UL); while (m) { int b = z + m; int mask = -(x >= b); x -= b & mask; z += m & mask; m >>= 2; } return z; } ``` 為了避免使用分支，這邊使用了一個 `mask` 變數來檢查是否滿足「`x` 大於等於 `b`」，如果滿足則更新 `x` 和 `z` 的值。 --- ### 測驗`2` ```c void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod) { uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */ uint32_t q = (x >> 4) + x; x = q; q = (q >> 8) + x; q = (q >> 8) + x; q = (q >> 8) + x; q = (q >> 8) + x; *div = (q >> CCCC); *mod = in - ((q & ~0x7) + (*div << DDDD)); } ``` CCCC 是 `2`；DDDD 則為 `1`。 --- ### 測驗`3` #### 解釋程式碼運作原理 考慮 $ilog2$ 可計算以 2 為底的對數，先來解釋 [第 3 週測驗題－測驗`3`](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-3) 中提到的版本二及版本三之對數函式實作，並重新填空。 版本二： ```c static size_t ilog2(size_t i) { size_t result = 0; while (i >= AAAA) { result += 16; i >>= 16; } while (i >= BBBB) { result += 8; i >>= 8; } while (i >= CCCC) { result += 4; i >>= 4; } while (i >= 2) { result += 1; i >>= 1; } return result; } ``` AAAA 為 `65536`、BBBB 為 `256`，而 CCCC 則是 `16`。 比起版本一，該版本程式碼透過 [Bit Manipulation](https://en.wikipedia.org/wiki/Bit_manipulation) 實作 $ilog2$，以加快程式執行速度。 以「第一個 `while`」為例，首先檢查傳入的數字是否 $\geq$ 65536，如果是，就將結果 $+$ 16，然後將該數字**右移 16 位**來將數字縮小範圍，以便後續更快地計算對數。 > 從 $2^{16}$ 開始除，接著 $2^8$、$2^4$... 而不是一直除 $2$，時間複雜度太高。 版本三： ```c int ilog32(uint32_t v) { return (31 - __builtin_clz(DDDD)); } ``` DDDD 為 `v | 1`。 參照 [Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)。 該段程式碼用來計算「32-bit 無符號整數 `v` 的二進制表示」中最高位（最左邊的位元為 1）的位置的索引。其用到了 GCC 內建函數 `__builtin_clz`，其會回傳「從參數的二進制表示開始的位元中，連續的 0-bit」的個數。 > `__builtin_clz`：Returns the number of leading 0-bits in `x`, starting at the most significant bit position. If `x` is `0`, the result is undefined. 所以，這裡的 `(v | 1)` 會確保即使 `v` 是 `0`，`__builtin_clz` 則會是 `31`（因為連續 31 個 `0`），所以最後會回傳 `0`。 總結一下，此函式就是在找「`1` 的最高位」的位置，即是某整數 $log_2$ 後並取整數的結果。 #### Linux 核心中，$log_2$ 相關程式碼分析 參照 [linux/kernel/trace/trace_events_hist.c](https://github.com/torvalds/linux/blob/39cd87c4eb2b893354f3b850f916353f2658ae6f/kernel/trace/trace_events_hist.c#L276) 中的 `hist_field_log2`，是有關 hlist 的資料數值操作函式；而其回傳值就有呼叫到 `ilog2` 函式。 ```c static u64 hist_field_log2(struct hist_field *hist_field, struct tracing_map_elt *elt, struct trace_buffer *buffer, struct ring_buffer_event *rbe, void *event) { struct hist_field *operand = hist_field->operands[0]; u64 val = hist_fn_call(operand, elt, buffer, rbe, event); return (u64) ilog2(roundup_pow_of_two(val)); } ``` 該 `ilog2` 函式定義在 [linux/tools/testing/selftests/mm/thuge-gen.c](https://github.com/torvalds/linux/blob/master/tools/testing/selftests/mm/thuge-gen.c#L51) 中，如下： ```c int ilog2(unsigned long v) { int l = 0; while ((1UL << l) < v) l++; return l; } ``` 與版本二/三的實作方法不同，此 `ilog2` 函式的關鍵在其 `while` 迴圈，`(1UL << l)` 會把 `1` 左移 `l` 位，即在計算「`2` 的 `l` 次方」。所以該迴圈就是在說－當 `(1UL << l)` 所代表的 `2` 的冪次方小於傳入數字 `v` 時，迴圈就繼續執行。換句話說，該函式在找一數字 `l`，其為「比傳入數字 `v` 大」的最小的 `2` 的冪次方。即為 `ilog2` 的邏輯。 --- ### 測驗`4` #### 解釋程式碼運作原理 首先需要先理解 Exponentially Weighted Moving Average (EWMA) 為何，可參照 [Wiki - Exponential moving average](https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average) 及 [第 `3` 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-4)。 可以理解成一每筆資料都「附有權重」的取平均方程式，而「時間越久」則「權重比重低」。 觀察 EWMA 的可能實作程式碼，其包含了用於來計算 EWMA 的通用函數。其中有一 `ewma` 結構，包含了 EWMA 參數以及平均值的縮放內部表示，旨在**最小化四捨五入誤差**。 - `factor`：內部值表示的縮放因子。最高可達到的平均值如此公式決定：`ULONG_MAX / (factor * weight)`。為了優化性能，`factor` 必須是 2 的冪次方。 - `weight`：指數權重，也稱為衰減率，決定了舊值影響力減弱的速度。為了效率，`weight` 也必須設置為 2 的冪次方。 ```c void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight) { if (!is_power_of_2(weight) || !is_power_of_2(factor)) assert(0 && "weight and factor have to be a power of two!"); avg->weight = ilog2(weight); avg->factor = ilog2(factor); avg->internal = 0; } ``` 實作需透過 `ewma_init` 函式來**初始化縮放因子和指數加權**。 > 內部會使用到 [測驗 `3`](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-3) 的 `ilog2` 函式。 ```c struct ewma *ewma_add(struct ewma *avg, unsigned long val) { avg->internal = avg->internal ? (((avg->internal << EEEE) - avg->internal) + (val << FFFF)) >> avg->weight : (val << avg->factor); return avg; } ``` EEEE 為 `avg->weight`；FFFF 為 `avg->factor`。 此函式是 EWMA 實作的核心，其核心思想是**對「過去的資料」賦予指數衰減的權重，從而使得「最新的樣本值」對整個平均值的影響最大**，而過去的數據則有較小的影響，從而達到平滑序列數據的效果。 因此該段程式碼可如下解析： - `internal` 未初始化：直接將值左移 `avg->factor` 來調整權重。 - `internal` 已作過運算：對於每筆新的資料，首先將「之前的加權平均值」左移 `avg->weight` 位，以增加其衰減效果，並從中減去這個值；然後加上「新的加權樣本值」以完成對加權平均值的更新。最後，要將計算出的新的加權平均值右移 `avg->weight` 位，來調整整體權重。 ```c unsigned long ewma_read(const struct ewma *avg) { return avg->internal >> avg->factor; } ``` 最後，`ewma_read` 只是將計算平均值「還原縮放」，以獲取其真正的平均值。 #### Linux 核心中，EWMA 相關程式碼分析 參照 [linux/drivers/net/wireless/ath/ath9k/dynack.c](https://github.com/torvalds/linux/blob/39cd87c4eb2b893354f3b850f916353f2658ae6f/drivers/net/wireless/ath/ath9k/dynack.c#L50)，該檔案是 Atheros AR9000 無線網路設備的 **Dynamic Adaptive Noise and Channel adaptation（DYNACK）** 功能的實現。而該檔案就涉及了使用 EWMA 來根據環境條件調整傳輸功率和通道。 > 其旨在改善無線連接的穩定性和性能，提供了在不同環境條件下自動調整傳輸功率和選擇最佳通道的能力。 細讀發現，在 `ath_dynack_compute_to` 函式中，呼叫了 `ath_dynack_ewma` 等有關 EWMA 計算的函式。其是用於計算 STA (Station) 的 ACK (Acknowledgement) 超時時間 (ACK Timeout)，以動態調整 STA 的 ACK 超時時間，來優化無線傳輸的效能。 重點在此段程式碼： ```c=173 sta = ieee80211_find_sta_by_ifaddr(ah->hw, dst, src); if (sta) { an = (struct ath_node *)sta->drv_priv; an->ackto = ath_dynack_ewma(an->ackto, ackto); ``` 主要先透過 `dst` 和 `src` 來找對應的無線站點（STA）。然後從 STA 的驅動私有數據中取得相關的 ATH 節點（`ath_node`），而後就使用到了 EWMA 相關函式 `ath_dynack_ewma` 來計算新的 ACK 超時時間。 > 這個新的超時時間是根據「舊的超時時間和最新的 ACK 接收時間之間的加權平均值」。其有助於跟蹤 ACK 超時時間的變化。 `ath_dynack_ewma` 函式實作如下： ```c static inline int ath_dynack_ewma(int old, int new) { if (old > 0) return (new * (EWMA_DIV - EWMA_LEVEL) + old * EWMA_LEVEL) / EWMA_DIV; else return new; } ``` --- ### 測驗`5` #### 解釋程式碼運作原理 此段程式碼是用來計算 $\lceil log_2(x) \rceil$ 的。 > 其中 `x` 必大於 `0`。 ```c= int ceil_ilog2(uint32_t x) { uint32_t r, shift; x--; r = (x > 0xFFFF) << 4; x >>= r; shift = (x > 0xFF) << 3; x >>= shift; r |= shift; shift = (x > 0xF) << 2; x >>= shift; r |= shift; shift = (x > 0x3) << 1; x >>= shift; return (r | shift | x > GGGG) + 1; } ``` GGGG 為 `1`。 考慮到二進制對數的定義，如果 `x` 本身是 `2` 的冪次方，那**大於或等於 `x` 的二進制對數**就是 `x` 的二進制表示中的 `1` 的個數；反之，如果 `x` 不是 `2` 的冪次方，而是介於兩個 `2` 的冪次方之間的數，那麼**大於或等於 `x` 的二進制對數**就是「`x` 的二進制表示中最高位 `1` 的位置」加 `1`。 鑒於此，此函式會先 `x--`，來確保不會計算大於 `x` 的二進制對數。 第 6 行，如果 `x` 大於 `65535`，則將 `r` 設為 `16`，否則為 `0`；並在第 7 行將 `x` 右移 `r` 位，若先前有將 `r` 設為 `16`，則此步的目的就是要將 `x` 的大小範圍縮小到 `16` 位以下。 下面 8-10、11-13 和 14-15 行同理，都是在透過位操作來計算大於或等於 `x` 的二進制對數的整數部分。