---
tags: NCKU Linux Kernel Internals
---
# quiz2
[2020q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2020-quiz2)
完整的程式內容請參考: [Github](https://github.com/RinHizakura/quiz2)
## Trace code: xs.c
### `struct xs`
```c=
typedef union {
char data[16];
struct {
uint8_t filler[15],
/* how many free bytes in this stack allocated string
* same idea as fbstring
*/
space_left : 4,
/* if it is on heap, set to 1 */
is_ptr : 1, flag1 : 1, flag2 : 1, flag3 : 1;
};
/* heap allocated */
struct {
char *ptr;
/* supports strings up to 2^54 - 1 bytes */
size_t size : 54,
/* capacity is always a power of 2 (unsigned)-1 */
capacity : 6;
/* the last 4 bits are important flags */
};
} xs;
```
* `char data[16]` 用來存放短字串。
* 第一個 struct 用來記錄此資料結構是放置長字串或短字串。其中 `filter` 是用來填滿前面的15 bytes，`space left` 記錄**最大短字串長度減去現在長度**，`is_ptr` 則記錄此結構是放長字串或短字串。
* 第二個struct `*ptr` 用來放長字串的 pointer，`size` 記錄該字串的長度。而 `capacity` 則是長度取log2 + 1 後的結果，紀錄malloc多少空間(之後如果要把字串加長，檢查 capacity 就可以知道需不需要多要)。保留最後 4-bit 讓 is_ptr, flag 的值不會被動到。
### `xs_tmp`
`main`中的
```c=
xs string = *xs_tmp("\n foobarbar \n\n\n");
```
展開會變成
```c=
xs string = *((void) ((struct { _Static_assert(sizeof("\n foobarbar \n\n\n") <= 16, "it is too big"); int dummy; }){1}), xs_new(&(xs) { .space_left = 15 }, "" "\n foobarbar \n\n\n"));
```
```c=
#define xs_tmp(x) \
((void) ((struct { \
_Static_assert(sizeof(x) <= 16, "it is too big"); \
int dummy; \
}){1}), \
xs_new(&xs_literal_empty(), "" x))
```
xs_tmp首先檢查x長度是否<=16，然後使用xs_new初始化字串
:::danger
:question: 有點搞不清這語法QQ 先擱置著回頭再研究
:::
### `xs_new`
* `xs_literal_empty()` 先把 x 當成空的短字串初始化(把 `space_left` 設為 15，其他設為 0)，接著去判斷x的長度。(因此題目中的`AAA = 16`)
:::warning
:question: xs_literal_empty 在 xs_tmp 時已經呼叫過，這樣是不是多用了一次？
:::
* 如果 >16 為長字串，則調整紀錄長字串的 member，並透過指標紀錄，malloc 把字串放在 heap。
* 否則為短字串，放在 `data`，長度則透過 `space_left` 紀錄。
* 短字串理論上應該也要設定`is_ptr`，但因為一開始已經初始成0，除非短字串長度是16否則不會更改到。而如果剛好字串長度為16，`\0`會使 space_left 跟 is_ptr 也會正好是0。
### `xs_trim`
* `xs_trim` 是用來刪除字串前後含的`trimset`。
* `set_bit` 根據trimset中的char對應的ASCII設定mask。ASCII的表達範圍是0~255，因此mask需要256個bits來紀錄，所以`BBB`應該是 `256 / 8 = 32`。
* `check_bit` 是與 mask 對應看x中的是否有要修剪的char，因此 `CCC = ＆`
### `xs_concat`
* `xs_concat` 把 `prefix` 和 `suffix` 串在 x 的前後。
* 檢查 capacity，看看如果直接把 prefix 和 suffix 加進去是否足夠容納，如果足夠，直接把memory copy進去即可。
* 如果不夠，則初始一個新的 xs 物件，並當成短字串初始化，再將其透過 `xs_grow` 使新的 xs 可以容納 prefix + suffix + 原字串的長度
* memmove 可以處理 source 跟 destination 的重疊
:::warning
:question: concat 的時候如果 capacity 不夠，是直接產生新 xs，把舊的 free 掉。但字串中其實有重複的內容，是否有更好的作法？
:::
### `xs_grow`
* 如果x的capacity不夠，則透過 `xs_grow` 增加可容納的字元數量。
* 如果已經是長字串，透過 `realloc` 增加空間
* 如果是短->長，則透過 malloc 改成把字串放在 heap
* 觀察 `capacity` 的更新就知道，字串可容納的大小是 2^N 次方成長的。
## Copy on Write
參考 [folly::fbstring](https://github.com/facebook/folly/blob/master/folly/FBString.h)
為了實現 Copy on write 機制，因此我們需要讓 ptr 使用的空間容納 reference count + 字串本身，需要對原本的函式做一些調整。
### `xs_new`
```c=
#define OFFSET sizeof(size_t)
```
* `OFFSET` 是擺放 reference count 需要的空間，也是從 `ptr` 推回 reference count 的 offset
```c=
x->ptr = malloc((size_t)1 << x->capacity + OFFSET) + OFFSET;
```
```
XS_INIT_REFCNT(x);
```
* 因此我們在要空間時，要多要一個offset的大小，並且把 ptr 指到 offset 擺放字串，以及初始化reference count。
### `xs_grow`
跟 xs_new 類似，在malloc / realloc 時需要調整空間大小。
### `xs_cpy`
* `xs_cpy` 把 src 複製到 dest，首先要先透過 XS_GET_REFCNT(dest)確認 dest 原先是否reference 其他。如果是，XS_DECR_REFCNT(dest)將reference count減一。
* 接著判斷 src 是長字串或者短字串
* 如果是短字串，調整 dest 的資料結構，然後直接複製 src 的字串過去即可。
* 如果是長字串，增加 src 的 reference count，並且使 dest 和 src 指到相同位置。
### `xs_cow`
```c=
void xs_cow(xs *x) {
size_t ref = XS_GET_REFCNT(x);
if (ref > 1) {
XS_DECR_REFCNT(x);
xs_new(x, xs_data(x));
}
}
```
* 檢查x是否為copy on write，如果是，將reference count減一，並且複製另一份出來。
:::warning
if 敘述不能寫成 `if (XS_GET_REFCNT(x) > 1)` ！
仔細思考 macro 展開就會明白原因
:::
### `xs_concat` and `xs_trim`
* 在處理 string 之前，先透過 `xs_cow()` 檢查。
### `xs_free`
```c=
static inline xs *xs_free(xs *x)
{
int ref = XS_GET_REFCNT(x);
if (ref > 1){
XS_DECR_REFCNT(x);
}
else if (xs_is_ptr(x)) {
free(xs_data(x) - OFFSET);
}
return xs_newempty(x);
}
```
* 先判斷是否是 reference，如果還有其他人 reference，僅清空 x 並將 reference count 減一，但不釋放。
* 如果是長字串且為唯一一份，則調整地址回開頭，並且釋放。
## 實作 xs_tok
參考[glibc](https://code.woboq.org/userspace/glibc/string/strtok_r.c.html#__strtok_r)的 source code來實作，使 tok 的行為一致。
* 在操作 x 前，先檢查 x 是否是 reference string ，如果先透過 `xs_cow()` 並做相應的處理。因為 `xs_tok` 會調整到 x 的內容。
* 利用和 `xs_trim` 相同的概念，透過建立的 mask 後找到第一個 delimiter，並把delimiter 設成 '\0'。
* 因為會把 delimiter 設成 '\0'，輸入的 x 長度需要被調整。
* 和strtok相同的概念，把 `save_ptr` 指向要處理的字串。
:::warning
發現老師在其他同學的筆記中有提到多執行緒的 tok 議題，需要再思考自己的實作在多執行緒下的正確性，並且加以修改。
:::
## COW 的效益
為了可以測試使用 COW 與否的差別，使用 `NOCOW` 的 flag 來編譯程式。並透過使用 [perf](https://perf.wiki.kernel.org/index.php/Main_Page) 來觀察對於 cache 的行為差異。測試的函式請參考 Github 中的 `test_perf()`
> perf stat -e cache-misses,cache-references ./xs
使用 COW 的版本:
```
Mode COW, using time 0.002744
Performance counter stats for './xs':
146,001 cache-misses # 45.669 % of all cache refs
319,692 cache-references
0.006344529 seconds time elapsed
0.006343000 seconds user
0.000000000 seconds sys
```
無 COW 的版本:
```
Mode NO COW, using time 0.025074
Performance counter stats for './xs':
1,153,296 cache-misses # 84.331 % of all cache refs
1,367,575 cache-references
0.029098245 seconds time elapsed
0.020737000 seconds user
0.008294000 seconds sys
```
可以看到，COW的使用大幅的減少 cache miss，因為沒有額外的 copy，花費的時間也相較之下也更少。
## Linux 核心中的 SSO / CoW
待補
Sign in with Wallet
Connect another wallet