# 2020q1 Homework2 (quiz2)
contributed by < `kylekylehaha` >
###### tags: `linux2020`
[第二週測驗題](https://hackmd.io/@sysprog/linux2020-quiz2)
[作業說明](https://hackmd.io/@sysprog/BJXNYx5NL)
## 測試題分析
先研究 xs 的結構：
* 字串長度 $\leq$ 15 時，被歸為「短字串」
* 「短字串」存於 `stack` 中
* 字串長度 = 15 - `space_left`，其中`space_left` 為字串右邊存在多少 0
* 字串 $\gt$ 15
* `is_ptr` 設為 1 ，用來辨識此 xs 為 「長字串」
* 字串儲存於 `heap`
* 字串起點為 `ptr`
* `capacity` 為儲存字串的大小，為 2 的次方。
:::danger
思考上述的 `15` 是如何被定義？是否能夠反映出硬體特性？
:notes: jserv
:::
:::info
[stack alginment matters](https://research.csiro.au/tsblog/debugging-stories-stack-alignment-matters/)
文章中有提到
`The compiler is maintaining a 16-byte alignment of the stack pointer when a function is called, adding padding to the stack as necessary.`，因此我們理應選 16 bytes 來避免需要 `padding`，但因為字串需要結束字元 `\0` ，故我們必須 -1。
:::
```cpp
typedef union {
char data[16];
struct {
uint8_t filler[15],
space_left : 4,
is_ptr : 1, flag1 : 1, flag2 : 1, flag3 : 1;
};
/* heap allocated */
struct {
char *ptr;
size_t size : 54,
capacity : 6;
};
} xs;
```
### Q1
這題出現在 `xs_new` function 上。
一開始，我們可以從命名來猜，猜測這是一個具有 create 的 function。
我們已知道當字串長度小於 `15` 時，會直接把字串存於 `data` 中，而當字串大於 `15` 時，會將字串存於 `heap` 中。
而 `len = strlen(p) + 1` 中的 `+1`，是為了加上 `\0`，故可以得知 `len` 為包含 `\0` 後的長度，因此 `AAA` = 16
```cpp
xs *xs_new(xs *x, const void *p)
{
*x = xs_literal_empty();
size_t len = strlen(p) + 1;
if (len > AAA) {
x->capacity = ilog2(len) + 1;
x->size = len - 1;
x->is_ptr = true;
x->ptr = malloc((size_t) 1 << x->capacity);
memcpy(x->ptr, p, len);
} else {
memcpy(x->data, p, len);
x->space_left = 15 - (len - 1);
}
return x;
}
```
### Q2 & Q3
`BBB` & `CCC` 位於 `xs_trim` function 中。
由 output 可以得知，此 function 用於刪除頭尾特定的字元，特定字元藉由 `*trimset` 傳入 function。
`BBB`
* `set_bit` 的功能是將目標字元設為 1，其操作原理有點 hash function 的味道。
* 由於 ASCII 的值為 0 ~ 255，有256個，故 `256/8 = 32` 即為 `mask` 所需的大小，故 `BBB` = `32`
* e.g. X 的 ASCII code 為 88，故 `mask[88/8]` 會被設為 `mask[88/8] |= 1 << (88%8)`，也就是 `mask[88/8] |= 1` ，等於 `mask[88/8] = xxxxxxx1`
`CCC`
* `check_bit`: 將 `*dataptr` 內的字元在 `mask` 上設為 1 ，並與之前已經 `set_bit` 的 `mask` 做比較。由於是做比較的效果，因此我認為此題 `CCC` = `&`
* e.g. 接續上面例子，因為已經做過 `set_bit`，故 X 的 `mask` 值為 `xxxxxxx1`。這時將 X 丟入 `check_bit`時，會發現兩者 `&` 後會得到 1，代表兩者為相同的字元，故要移除。
```cpp
xs *xs_trim(xs *x, const char *trimset)
{
if (!trimset[0])
return x;
char *dataptr = xs_data(x), *orig = dataptr;
/* similar to strspn/strpbrk but it operates on binary data */
uint8_t mask[BBB] = {0};
#define check_bit(byte) (mask[(uint8_t) byte / 8] CCC 1 << (uint8_t) byte % 8)
#define set_bit(byte) (mask[(uint8_t) byte / 8] |= 1 << (uint8_t) byte % 8)
size_t i, slen = xs_size(x), trimlen = strlen(trimset);
for (i = 0; i < trimlen; i++)
set_bit(trimset[i]);
for (i = 0; i < slen; i++)
if (!check_bit(dataptr[i]))
break;
for (; slen > 0; slen--)
if (!check_bit(dataptr[slen - 1]))
break;
dataptr += i;
slen -= i;
/* reserved space as a buffer on the heap.
* Do not reallocate immediately. Instead, reuse it as possible.
* Do not shrink to in place if < 16 bytes.
*/
memmove(orig, dataptr, slen);
/* do not dirty memory unless it is needed */
if (orig[slen])
orig[slen] = 0;
if (xs_is_ptr(x))
x->size = slen;
else
x->space_left = 15 - slen;
return x;
#undef check_bit
#undef set_bit
}
```
## 提供字串複製 (應考慮到 CoW) 和類似 strtok 功能的函式實作
### xs_copy
* 為了實作 CoW ，我們用 `flag1` 來記錄此為共享記憶體，當有寫入更改時，會額外配置新的記憶體，並將 `flag1` 清除。
* 當字串為短字串時，直接將字元放入 `dest->data[i]`
* 當字串超過16字元時，將 `dest->ptr` 指向 `src->ptr`
```cpp
xs *xs_copy(xs *dest, xs *src)
{
if (xs_is_ptr(src)) {
/* string is on heap */
dest->is_ptr = 1;
dest->ptr = src->ptr;
dest->flag1 = 1;
dest->size = xs_size(src);
} else {
/* string is on stack */
for (int i = 0;i < 16; i++) {
dest->data[i] = src->data[i];
}
dest->is_ptr = 0;
dest->flag1 = 0;
dest->space_left = 15 - xs_size(src);
}
return dest;
}
```
測試一下
```cpp
int main()
{
xs string = *xs_tmp("foobarbar test");
xs prefix = *xs_tmp("(((((");
xs suffix = *xs_tmp(")))))");
xs copy = *xs_copy(©, &string);
printf("[%s], %2zu\n",xs_data(&string), xs_size(&string));
printf("[%s], %2zu\n",xs_data(©), xs_size(©));
}
```
預期結果
```
[foobarbar test], 14
[foobarbar test], 14
```
印出兩者的位置，來確認是否為 copy
```cpp
printf("string %p\ncopy %p",string.ptr, copy.ptr);
```
輸出結果
```
string 0x61627261626f6f66
copy 0x61627261626f6f66
```
* 為了實作出 CoW ，我們必須接入 reference count，用來記錄該共享記憶體有多少人共用著。
* 採用在 strcut 加入新的結構 `int *refcnt`，並修改一下之前的 `xs_cpy`，來符合我們的 reference count
```cpp
struct {
char *ptr;
size_t size : 54,
capacity : 6;
int *refcnt;
};
```
* 我們利用 `*refcnt` 指標，指向共同的記憶體，也就是 `src->refcnt`。
```cpp
...
if (!src->refcnt) {
dest->refcnt = src->refcnt = (int*)malloc(sizeof(int));
*(dest->refcnt) = 1;
} else {
dest->refcnt = src->refcnt;
*(dest->refcnt) += 1;
}
...
```
接著來修改 `xs_concat`
這邊我將問題切成兩種：串上後字元 $\lt$ 16 & 串上後字元 $\geq$ 16
* 串上後字元 $\lt$ 16: create 一個新的 space ，來達到 CoW 的效果。
* 串上後字元 $\geq$ 16: 因為已經 create 一個新的 space(在 `xs_grow` 內)，故只須注意是否還有其他人仍然使用著共享記憶體，故不能隨便 `free` 掉。
```cpp
if (size + pres + sufs <= 16) {
data = string->ptr = (char*)malloc(sizeof(char) * 16);
memcpy(data, pre, pres);
memcpy(data + pres, data, size);
memcpy(data + pres + size, suf, sufs + 1);
string->space_left = 15 - (size + pres + sufs);
} else {
xs tmps = xs_literal_empty();
xs_grow(&tmps, size + pres + sufs);
char *tmpdata = xs_data(&tmps);
memcpy(tmpdata + pres, data, size);
memcpy(tmpdata, pre, pres);
memcpy(tmpdata + pres + size, suf, sufs + 1);
if(string->flag1 && string->refcnt && *(string->refcnt) > 0){
*(string->refcnt) -= 1;
if(*(string->refcnt) == 0){
free(string->refcnt);
string->refcnt = NULL;
}
}else {
xs_free(string);
}
tmps.flag1 = false;
*string = tmps;
string->size = size + pres + sufs;
}
}
```
最後，來修改 `xs_trim`
* 為了實現 CoW，當有修改時就必須 create a new space。
* 並且也和之前的想法一樣，必須都沒有人 reference 時，才可 `free` 掉。
```cpp
...
if (x->flag1 && x->refcnt && *(x->refcnt) > 0) {
x->ptr = orig = (char*)malloc(sizeof(char) * strlen(x->ptr) + 1);
*(x->refcnt) -= 1;
if (*(x->refcnt) == 0) {
free(x->refcnt);
x->refcnt = NULL;
}
}
...
```
測試
```cpp
xs prefix = *xs_tmp("((((("), suffix = *xs_tmp(")))))");
xs string = *xs_new(&string,"hahahahahafoobarbar");
xs_concat(&string, &prefix, &suffix);
xs string_cpy = *xs_cpy(&xs_literal_empty(),&string);
xs_trim(&string_cpy, "(");
printf("[%s] : %2zu\n", xs_data(&string_cpy), xs_size(&string_cpy));
printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));
```
輸出結果
```cpp
[hahahahahafoobarbar)))))] : 24
[(((((hahahahahafoobarbar)))))] : 29
```
### xs_strtok
* 功能: 和 [strtok](http://tw.gitbook.net/c_standard_library/c_function_strtok.html) 相同，都是切割字串。
* [strspn](http://tw.gitbook.net/c_standard_library/c_function_strspn.html)
* [strpbrk](http://tw.gitbook.net/c_standard_library/c_function_strpbrk.html)
```cpp
char *xs_strtok(char *x, const char *delimit)
{
static char *lastToken = NULL;
char *tmp;
/* skipped first delimit */
if (x == NULL) {
x = lastToken;
if (x == NULL) /* End of stroy */
return NULL;
} else {
x += strspn(x, delimit);
}
tmp = strpbrk(x, delimit);
if (tmp) {
/* Find next token */
*tmp = '\0';
lastToken = tmp + 1;
} else {
/* Last segment, remember that. */
lastToken = NULL;
}
return x;
}
```
測試一下
```cpp
xs str = *xs_new(&str, ":haha:kyle:hello:");
char *token = xs_strtok(xs_data(&str), ":");
while (token != NULL) {
printf ("%s ", token);
token = xs_strtok (NULL, ":");
}
printf("\n");
```
結果
```cpp
haha kyle hello
```
## 設計實驗，確認上述字串處理最佳化 (針對空間效率) 帶來的效益，應考慮到 locality of reference
* 可以從 cache miss 來判斷是否有 locality of reference
* 我們採用 `strncpy` 來當作這次實驗的對照組。
* 實驗中，我們重複複製 50000 次，來讓兩者差距較明顯。
```cpp
static void ori_cpy(char **dest, char **src)
{
int len = strlen(*src);
*dest = (char*)malloc(sizeof(char) * (len + 1));
strncpy(*dest, *src, len+1);
return;
}
```
```cpp
/* ori_cpy */
int n = 50000;
char *test1 = "kylehahakylehaha";
char *test2;
printf("ori_cpy\n");
while(n > 0) {
ori_cpy(&test2, &test1);
memset(test2, 0, sizeof(test2));
n--;
}
/* xs_cpy */
xs xs_test1 = *xs_new(&xs_test1, "kylehahakylehaha");
xs xs_test2;
printf("xs_cpy\n");
while(n > 0) {
xs_test2 = *xs_cpy(&xs_test2, &xs_test1);
n--;
}
```
`Valgind`
接著利用 valgrind 來檢查 cache miss [Using valgrind to measure cache misses](https://stackoverflow.com/questions/32542164/using-valgrind-to-measure-cache-misses)
```cpp
valgrind --tool=cachegrind ./xstring_COW
```
一開始，我們先用 `ori_cpy` 得到以下結果
```cpp
ori_cpy
==15428==
==15428== I refs: 20,247,391
==15428== I1 misses: 1,047
==15428== LLi misses: 1,032
==15428== I1 miss rate: 0.01%
==15428== LLi miss rate: 0.01%
==15428==
==15428== D refs: 6,260,458 (3,998,528 rd + 2,261,930 wr)
==15428== D1 misses: 28,357 ( 2,693 rd + 25,664 wr)
==15428== LLd misses: 27,631 ( 2,069 rd + 25,562 wr)
==15428== D1 miss rate: 0.5% ( 0.1% + 1.1% )
==15428== LLd miss rate: 0.4% ( 0.1% + 1.1% )
==15428==
==15428== LL refs: 29,404 ( 3,740 rd + 25,664 wr)
==15428== LL misses: 28,663 ( 3,101 rd + 25,562 wr)
==15428== LL miss rate: 0.1% ( 0.0% + 1.1% )
```
緊接著，我們用 `xs_cpy` 來實驗。
```cpp
xs_cpy
==15445==
==15445== I refs: 6,495,234
==15445== I1 misses: 1,051
==15445== LLi misses: 1,034
==15445== I1 miss rate: 0.02%
==15445== LLi miss rate: 0.02%
==15445==
==15445== D refs: 3,509,672 (2,347,995 rd + 1,161,677 wr)
==15445== D1 misses: 3,181 ( 2,555 rd + 626 wr)
==15445== LLd misses: 2,628 ( 2,066 rd + 562 wr)
==15445== D1 miss rate: 0.1% ( 0.1% + 0.1% )
==15445== LLd miss rate: 0.1% ( 0.1% + 0.0% )
==15445==
==15445== LL refs: 4,232 ( 3,606 rd + 626 wr)
==15445== LL misses: 3,662 ( 3,100 rd + 562 wr)
==15445== LL miss rate: 0.0% ( 0.0% + 0.0% )
```
可以發現 `D1 misses` 兩者有明顯的差距。
`Perf`
接著，我們利用另一種工具 [perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) 來觀察 cache misses
```cpp
sudo perf stat -e cache-misses ./xstring_COW
```
以下分別為 `ori_cpy` 以及 `xs_cpy`
`ori_cpy`
```cpp
ori_cpy
Performance counter stats for './xstring_COW':
389,967 cache-misses
0.029485423 seconds time elapsed
0.029564000 seconds user
0.000000000 seconds sys
```
`xs_cpy`
```cpp
xs_cpy
Performance counter stats for './xstring_COW':
16,984 cache-misses
0.010601564 seconds time elapsed
0.010667000 seconds user
0.000000000 seconds sys
```
## 在 Linux 核心原始程式碼中，找出類似手法的 或 CoW 案例並解說
在 linux 中，以下為 process 進行 fork 的流程圖。參考[What is a process](https://bash.cyberciti.biz/guide/What_is_a_Process%3F)
其中在作業系統，為了避免程式 fork 完後立刻 exec，因此採用 CoW 的機制。利用 parrent & children 共用未寫入的記憶體，來增加 children 的建立速度。
此外，若 children 第一時間就 exec 的話，也可以因為 CoW 的機制不會浪費記憶體空間以及時間了。
因此，我們研究 [linux/fork.c](https://github.com/torvalds/linux/blob/master/kernel/fork.c)，並參考 [where is the source for fork() call in linux](https://stackoverflow.com/questions/34871103/where-is-the-source-for-the-fork-call-in-linux/34871795)
* 我們發現在利用 syscall 呼叫 fork() 時，會去呼叫 `do_fork`
```cpp
SYSCALL_DEFINE0(fork)
{
#ifdef CONFIG_MMU
struct kernel_clone_args args = {
.exit_signal = SIGCHLD,
};
return _do_fork(&args);
#else
/* can not support in nommu mode */
return -EINVAL;
#endif
}
```
* `do_fork` 出現在 [linux/fork.c](https://github.com/torvalds/linux/blob/master/kernel/fork.c)
* 一開始， `do_fork` 會先檢查是哪個 system call
```cpp
/*
* Determine whether and which event to report to ptracer. When
* called from kernel_thread or CLONE_UNTRACED is explicitly
* requested, no event is reported; otherwise, report if the event
* for the type of forking is enabled.
*/
if (!(clone_flags & CLONE_UNTRACED)) {
if (clone_flags & CLONE_VFORK)
trace = PTRACE_EVENT_VFORK;
else if (args->exit_signal != SIGCHLD)
trace = PTRACE_EVENT_CLONE;
else
trace = PTRACE_EVENT_FORK;
if (likely(!ptrace_event_enabled(current, trace)))
trace = 0;
}
```
* 接著呼叫 `copy_process` ,which sets up the process descriptor and any other kernel data structure required for child 's execution
```cpp
p = copy_process(NULL, trace, NUMA_NO_NODE, args);
```
* 在 `copy_prcoess` 中，又去呼叫 `dup_task`struct`, which creates new kernel stack, thread_info and task_struct structures for the new process，也就是真正創建 children process 的位置。
* `current` 為目前運行程式的 pointer
```cpp
p = dup_task_struct(current, node);
```
* `copy_process` 完成後，會去喚醒 childen
```cpp
wake_up_new_task(p);
```
* 如果是 `vfork` 的話，必須等 children 呼叫 `exec` 或離開
```cpp
if (clone_flags & CLONE_VFORK) {
p->vfork_done = &vfork;
init_completion(&vfork);
get_task_struct(p);
}
```
而 CoW 實現在 `copy_process` 內的 `copy_mm`。
```cpp
retval = copy_mm(clone_flags, p);
```
[參考同學的整理](https://hackmd.io/@colinyoyo26/xs#copy_mm)
* `copy_mm` 中， `vfork` 會直接進入條件式，因為`呼叫 vfork 時 args.flags 會被設成 CLONE_VFORK | CLONE_VM`，故直接共用一個`mm_struct`。
* 然而 `fork` 則會直接呼叫 `dup_mm` 來複製 parent 的 `mm_struct`。
```cpp
...
if (clone_flags & CLONE_VM) {
mmget(oldmm);
mm = oldmm;
goto good_mm;
}
retval = -ENOMEM;
mm = dup_mm(tsk, current->mm);
if (!mm)
goto fail_nomem;
...
```
Sign in with Wallet
Connect another wallet