---
tags: NCKU Linux Kernel Internals
---
# quiz4
## Material
> * [2020q1 第 4 週測驗題](https://hackmd.io/@sysprog/linux2020-quiz4)
> * [2021q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz2)
> * [Github](https://github.com/RinHizakura/bitcpy)
## bitcopy
:::danger
注意到測驗題裡的原始程式似乎有寫錯的地方？後面會仔細討論此部份
:::
### 實作原理
bitcpy 的用途是把 `_src` 從指定的位置 `_read` 開始， 從 `_dest` 的 `_write` 開始寫 `_count` 個 bit。
複製是 8 個 bits 為單位處理的，又因為允許不按照 alignment 存取，因此需要位移來處理。`read_lhs = _read & 7` 即是 `read_lhs = _read % 8`，如果我們要從 `_src` 中取出不對齊的資料，以下圖為例，如果目標是黃框中跨越兩個 bytes 的 8 bits。則讀出來步驟會是:
* 先讀出 byte 1 到 `data`，然後 `data` 左移 5 bits
* 讀出 byte 0 後右移 3 bits 後跟 `data` or 運算後存回 `data`
例子中的 5 bits / 3 bits 就是需要被推算的 `read_lhs`、`read_rhs`。write 的推算也是同理，因此 `KK1` = ( g )7
取出後，再透過 bitsize 推算出前幾位數需要被複製，到這步驟，loop 這一輪需要的 8 bits `data` 就被準備好了，這就是到下面一段程式所做的事。
```c
while (_count > 0) {
data = *source++;
bitsize = (_count > 8) ? 8 : _count;
if (read_lhs > 0) {
data <<= read_lhs;
if (bitsize > read_rhs)
data |= (*source >> read_rhs);
}
if (bitsize < 8)
data &= read_mask[bitsize];
...
```
調整寫入位置的方法很類似，不過再稍微複雜一些。在 ` _dest
` 非 align 的情境下，有兩個狀況要考慮:
* 如果要寫入 bit 數包含接續在後面的 bytes (`if (bitsize > write_rhs)`)，則先把當前 bytes 的部分寫進去，再前進到下個 byte 補完。
* 需要寫入的量如果不包含後面的 bytes，把當前 bytes 的部分寫好就可以。
```c
original = *dest;
if (write_lhs > 0) {
mask = read_mask[write_lhs];
if (bitsize > write_rhs) {
*dest++ = (original & mask) | (data >> write_lhs);
original = *dest & write_mask[bitsize - write_rhs];
*dest = original | (data << write_rhs);
} else {
if ((bitsize - write_lhs) > 0)
mask = mask | write_mask[8 - (bitsize - write_lhs)];
*dest++ = (original & mask) | (data >> write_lhs);
}
}
```
`_dest` 是 align 的話，如果要寫 8 bits 直接放進去，如果少於 8 bits 就把要寫的地方用 mask 清掉，再把 `data` 放進去即可。
```c
else {
if (bitsize < 8)
data = data | (original & write_mask[bitsize]);
*dest++ = data;
}
_count -= KK2;
}
```
因為每一次都處理掉 bitsize 大小的數據，因此 `KK2` = ( d ) bitsize。
### 改寫為更精簡且等效的程式碼
#### 錯誤？
程式的此部份邏輯有點奇怪：
```c
else {
if ((bitsize - write_lhs) > 0)
mask = mask | write_mask[8 - (bitsize - write_lhs)];
*dest++ = (original & mask) | (data >> write_lhs);
}
```
這個 else 的目的應該是當 bitsize 小於 `write_rhs` 時，要避免把 dest 的部份覆蓋掉而去調整 mask，因此感覺應該要修正成：
```c
else {
mask |= write_mask[8 - (write_rhs - bitsize)];
*dest++ = (original & mask) | (data >> write_lhs);
}
```
又 `8 - write_rhs` 實際上就是 `write_lhs`，所以可以等價修正成
```c
else {
mask |= write_mask[write_lhs + bitsize)];
*dest++ = (original & mask) | (data >> write_lhs);
}
```
同時也透過概念相似的 python code 來檢驗結果(用一個 int 來存 1 bit，所以比較容易撰寫，也因此應該不太會出錯，詳細請參考 Github)。如果沒有誤會 `bitcpy` 的功能的話，把輸出結果用 `diff` 來檢查，更改後的結果應該才是正確的。
:::warning
因為測驗題原本給程式的是全零的 `output` 和全一的 `input`，某些程度上錯誤的程式也可能導致正確的結果(因為 pattern 太單一)，所以在檢驗正確性的時候需要小心。
:::
#### 進一步簡化程式
確認了正確的結果為何後，我們就可以放心的調整程式，再檢驗輸出來確定結果是否正確。
通過把 special case 融合成 general case，修改後的程式為:
```c
.../* */
while (_count > 0) {
data = *source++;
bitsize = (_count > 8) ? 8 : _count;
data <<= read_lhs;
data |= (bitsize > read_rhs) ? (*source >> read_rhs) : 0;
data &= read_mask[bitsize];
original = *dest;
int idx = bitsize > write_rhs ? 8 : 8 - (write_rhs - bitsize);
*dest++ = (original & (read_mask[write_lhs] | write_mask[idx])) |
(data >> write_lhs);
idx = bitsize < write_rhs ? 0 : bitsize - write_rhs;
*(dest) = (*dest & write_mask[idx]) | (data << write_rhs);
_count -= bitsize;
}
```
:::warning
雖然我知道 `? : ` 不會減少分支，不過至少讓程式看起來乾淨一點...嗎?
:::
### 改寫為執行效率更高的程式碼
原始的程式為了可以做到儘量以最大 8 bits 來操作，因此需要繁瑣的 branch ，且沒有很好的考慮到 align 問題導致需要一直在非 align 的狀況下處理 bitstring。
修改後的程式如下，其中 `bitcpy_naive` 就是前面改為更精簡的版本。我們的方法其實是把 bitcpy 切成3個部份:
* 一開始先檢查 dest 是否有 align 好，如果沒有就先只處理沒 align 的第 1 部份
* dest 從有 align 的地方開始處理，直到最後一個不到 8 bits 的部份
* 把最後的部份 copy 完
注意到程式用比較簡單的方式設計，透過呼叫可以處理所有狀況的 `bitcpy_naive` 把特例處理掉讓程式撰寫比較簡單，但如果考慮只針對 special case 的話應該可以簡化某些運算避免使用 general 的方法。(但是我爛，寫出來都怪怪的QQ ，所以暫時以這種比較笨的方法)
```c
if (write_lhs != 0 && _count >= write_rhs) {
bitcpy_naive(_dest, _write, _src, _read, write_rhs);
if (write_rhs > read_rhs)
source++;
_write += write_rhs;
_read += write_rhs;
_count -= write_rhs;
dest++;
read_lhs = _read & 7;
read_rhs = 8 - read_lhs;
/* No update is ok because we dont need this after
write_lhs = _write & 7;
write_rhs = 8 - write_lhs; */
}
int iter_cnt = _count >> 3;
int iter = _count >> 3;
_count &= 7;
while (--iter_cnt >= 0) {
*dest++ = (*source << read_lhs) | ((*(source + 1) >> read_rhs));
source++;
}
bitcpy_naive(_dest, _write + (iter << 3), _src, _read + (iter << 3), _count);
```
可以看到考慮到 align 讓執行的時間有明顯的減少。
### Linux 核心中的 bitcpy
- [ ] 觀察 [linux/bitops.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/bitops.h) 裡頭巨集在原始程式碼的運用狀況
## vector
VV1 = ( d ) `(s & (s - 1)) == 0`
VV2 = ( a ) `v.size -= 1`
### 實作原理
#### `v`
```c=
#define v(t, s, name, ...) \
union { \
STRUCT_BODY(t); \
struct { \
size_t filler; \
t buf[NEXT_POWER_OF_2(s)]; \
}; \
} name __attribute__((cleanup(vec_free))) = {.buf = {__VA_ARGS__}}; \
name.size = sizeof((__typeof__(name.buf[0])[]){0, __VA_ARGS__}) / \
sizeof(name.buf[0]) - 1; \
name.capacity = sizeof(name.buf) / sizeof(name.buf[0])
```
* 在 Union 中有兩種 struct。一種是透過 `STRUCT_BODY` 定義的。一種是有一個 `size_t` 的成員 `filter`，和 `NEXT_POWER_OF_2(s)` 大小的 `t` 型態 array。
* 根據 [cleanup (cleanup_function)](https://gcc.gnu.org/onlinedocs/gcc/Common-Variable-Attributes.html) `__attribute__((cleanup(vec_free)))` 會在變數離開 stack 時自動呼叫 `vec_free`。
* 根據 [Variadic Macros](https://gcc.gnu.org/onlinedocs/cpp/Variadic-Macros.html)，把 `name` 以後的參數對應到 `__VA_ARGS__`，用來初始化 `buf` 裡的內容。
* `size` 計算 vector 目前儲存的數量，透過 `(__typeof__(name.buf[0]))` 得到 buf 的型別，再用此型別去建立一個成員有 `{0, __VA_ARGS__}` 的 literal，則 vector 大小即是這個 literal 需要的儲存空間除以單個元素的儲存空間再減 1(扣掉 0)
* 需要多放一個 0，是避免沒有 `__VA_ARGS__` 時 buf[0] 不會出錯
* `capacity` 是 vector 可以容納的數量
#### `STRUCT_BODY`
這個 macro 用來宣告 struct 結構，其中 `type` 是結構中 pointer 的型態。前面的 size_t 則是透過在 [C 語言：bit-field](https://hackmd.io/@RinHizakura/Hk1CYv1kv/%2F5B7s4KiaQOmS0Ud6Px6Cww) 提到的技巧，把 `size_t` 的 64 位元分配給不同的 struct member。
```c=
#define STRUCT_BODY(type) \
struct { \
size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1, \
flag3 : 1; \
type *ptr; \
}
```
#### `NEXT_POWER_OF_2(s)`
```c=
#define NEXT_POWER_OF_2(s) \
VV1 \
? s \
: (size_t) 1 << (64 - __builtin_clzl(s)) /* next power of 2 */
```
求出比 `s` 大且最接近 `s` 的 2^n 次方(n 為整數)。因此 VV1 應該是 ( d )`(s & (s - 1)) == 0` (可以參閱 [C 語言：數值系統篇](https://hackmd.io/9tGfpJtLTwyyOzDvlyJS2w?view#x-amp-x---1--0))，如果 s 本身就是 2^n 次方則直接是 s，否則透過 `64 - __builtin_clzl` 求出 s 從左邊數來第 1 個 1 在哪，位移那個量可以得到所求。
#### `NON_NULL`
```c=
#define NON_NULL __attribute__((nonnull))
```
[__attribute__((nonnull))](https://www.keil.com/support/man/docs/armcc/armcc_chr1359124976631.htm) 告訴編譯器這個 function 不能接受 NULL pointer，否則會在編譯時期產生警告。
#### `vec_free`
```c=
static NON_NULL void vec_free(void *p)
{
STRUCT_BODY(void) *s = p;
if (s->on_heap)
free(s->ptr);
}
```
檢查 vector 是否是用 heap 來儲存，是的話要透過 free 來釋放。
#### `vec_size`
```c=
#define vec_size(v) v.size
```
如你所見，不解釋。
#### `vec_capacity`
```c=
#define vec_capacity(v) \
(v.on_heap ? (size_t) 1 << v.capacity : sizeof(v.buf) / sizeof(v.buf[0]))
```
檢查 vector 是否額外使用 heap 儲存資料，如果是，$2^{v.capacity}$ 為實際的容量大小，否則就是 `sizeof(v.buf) / sizeof(v.buf[0]))`。
#### `vec_data`
```c=
#define vec_data(v) (v.on_heap ? v.ptr : v.buf) /* always contiguous buffer */
```
針對是否使用 heap 存取的 member 不同。
#### `vec_elemsize`
```c=
#define vec_elemsize(v) sizeof(v.buf[0])
```
如你所見。
#### `vec_pos`
```c=
#define vec_pos(v, n) vec_data(v)[n] /* lvalue */
```
用來取 vector 的第 n 個值
#### `vec_reserve`
```c=
#define vec_reserve(v, n) __vec_reserve(&v, n, vec_elemsize(v), vec_capacity(v))
```
#### `__vec_reserve`
```c=
static NON_NULL void __vec_reserve(void *vec,
size_t n,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(void);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (n > capacity) {
if (v->on_heap) {
v->ptr = realloc(v->ptr,
elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
} else {
void *tmp =
malloc(elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
}
}
}
```
透過 heap 擴大 vector 的 capacity
#### `ilog2`
```c=
static inline int ilog2(size_t n)
{
return 64 - __builtin_clzl(n) - ((n & (n - 1)) == 0);
}
```
求出 k，k 滿足比 n 大且最接近的 $2^k$(k 為整數)
#### `vec_push_back`
```c=
#define vec_push_back(v, e) \
__vec_push_back(&v, &(__typeof__(v.buf[0])[]){e}, vec_elemsize(v), \
vec_capacity(v))
```
#### `__vec_push_back`
```c=
static NON_NULL void __vec_push_back(void *restrict vec,
void *restrict e,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (v->on_heap) {
if (v->size == capacity)
v->ptr = realloc(v->ptr, elemsize * (size_t) 1 << ++v->capacity);
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else {
if (v->size == capacity) {
void *tmp =
malloc(elemsize * (size_t) 1 << (v->capacity = capacity + 1));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else
memcpy(&v->buf[v->size++ * elemsize], e, elemsize);
}
}
```
push 進一個元素，必要的時候要增加 capacity。
#### `vec_pop_back`
```c=
#define vec_pop_back(v) (void) (VV2)
```
拿出一個元素，所以 `VV2` 是 (a )`v.size -= 1`
### 實作限制與改進方案
#### `vec_pop_back`
```c=
#define vec_pop_back(v) assert(v.size > 0); v.size -= 1
```
原本的 `vec_pop_back` 僅僅是把 `size -= 1`，對於空的 vector 的 pop 應該要反映出問題，因此修改為此。
#### `vec_pos`
透過 assert 檢查超出邊界的存取，詳細請參閱 Github。
#### `v`
透過 [Static Assertion](https://en.wikichip.org/wiki/c/static_assertion) 避免初始化 void 型別的 vector，需注意到 static assertion 的檢查只能接受 [Constant Expressions](https://www.cs.auckland.ac.nz/references/unix/digital/AQTLTBTE/DOCU_066.HTM) 而不能執行 function，不過我們可以透過 GCC builtin 來完成字串比對。
```c=
_Static_assert(__builtin_strncmp(#t, "void", 4), "error type");
```
詳情請參閱 Github。
#### 記憶體配置
在 [folly::fbvector](https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md) 提到記憶體配置原則的重要性。當 vector 需要更多空間時，一次 malloc(realloc) 要重新要多少空間是很關鍵的議題，如果要的太少，會導致頻繁呼叫 malloc 產生的時間成本，但是如果要的太多又會有空間浪費的問題。
空間的成長幅度稱為 growth factor，在原始程式中，growth factor 為 2，也就是當空間不足時，就把 heap 空間擴大成兩倍。但是在文章中指出此設計不好的地方。假如初始一塊大小為 C 的空間，則 growth factor = k，下一次需要的空間是原本的 K 倍：
$C$, $C * k$, $C * k^2$, $C * k^3$, ...
在 k = 2 的狀況下，因為 $C$ + $C * k$ + $C * k^2$ + ... $C * k^{n-1}$ < $C * k^n$ 恆成立，因此每次重新配置的空間都比之前配置過的總和大，導致每一次配置就真的需要多要記憶體，而沒辦法重新利用之前配置的空間(如果新的所需空間總和小於之前，則有機會從 pool 裡拿出之前配置的空間來使用就足夠)。
需注意到 allocator 實際上是怎麼分配會影響到實作的策略，不過 k = 2 不論如何都是理論上最差的選擇。而 fbvector 與 jemalloc 搭配，使用 growth factor 1.5 得到最佳效能。
- [ ] 研究如何設計使用者定義的 allocator，搭配記憶體的配置策略得到更佳的效能
### 實現經典 vector 操作
#### `front` / `back`
```c=
#define vec_front(v) vec_pos(v, 0)
#define vec_back(v) vec_pos(v, v.size-1)
```
透過 `vec_pos` 去存取也可以確保錯誤使用時(例如空 vector 時用 `vec_front`)被 assert 擋下來。
#### `insert`
C++ 中的 insert 根據參數功能會有點差異，其中最基本的功能是可以把指定的 element `e` 插入到 `p` 位置。
```c=
#define vec_insert(v, p, e) \
do { \
assert(p >= 0 && p < v.size); \
__typeof__(v.buf[0]) __tmp; \
for (int i = 0; i < (signed) v.size; i++) { \
if (i == p) { \
__tmp = vec_pos(v, i); \
vec_pos(v, i) = e; \
} else if (i > p) { \
__typeof__(v.buf[0]) __t; \
__t = __tmp; \
__tmp = vec_pos(v, i); \
vec_pos(v, i) = __t; \
} \
} \
vec_push_back(v, __tmp); \
} while (0)
```
```c=
#define vec_insert_n(v, p, n, e) \
do { \
assert(p >= 0 && p < v.size); \
assert(n > 0); \
__typeof__(v.buf[0]) *__tmp = \
malloc(sizeof(__typeof__(v.buf[0])) * (v.size - p)); \
int cnt = 0; \
for (int i = 0; i < (signed) v.size; i++) { \
if (i >= p) { \
__tmp[cnt++] = vec_pos(v, i); \
} \
} \
for (int i = 0; i < (signed) v.size - p; i++) \
vec_pop_back(v); \
vec_reserve(v, v.size + n + cnt); \
for (int i = 0; i < n; i++) \
vec_push_back(v, e); \
for (int i = 0; i < cnt; i++) \
vec_push_back(v, __tmp[i]); \
free(__tmp); \
} while (0)
```
作法稍微有點暴力，尤其是 `vec_insert_n`，可以實作出相同效果的方法有許多種，需要考量到效率去做改進。
:::warning
雖然用 macro 可以減少轉型，讓對 vector 的操作比較簡單，不過也因此如果認真要做 assert 可以有很多需要檢查的(在 int 的 vector 插入 float element? `vec_insert_n` 如果 insert 的數量是 float?)。如果要增加實用性的話，需要對這些層面去改善(真的 assert 去檢查？或者換成 function 型式讓 compiler 去檢查)。
:::
#### erase
Sign in with Wallet
Connect another wallet