---
# System prepended metadata

title: 2020q1 Homework2 (quiz2)
tags: [linux2020]

---

# 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(&copy, &string);
    printf("[%s], %2zu\n",xs_data(&string), xs_size(&string));
    printf("[%s], %2zu\n",xs_data(&copy), xs_size(&copy));
}
```
預期結果
```
[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)

![](https://i.imgur.com/zjw71ml.png)


其中在作業系統，為了避免程式 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;
...
```
