2020q1 Homework2 (quiz2)

contributed by < kylekylehaha >

tags: linux2020

第二週測驗題
作業說明

測試題分析

先研究 xs 的結構：

• 字串長度

  $\le$ 15 時，被歸為「短字串」
  * 「短字串」存於 stack 中
  * 字串長度 = 15 - space_left，其中space_left 為字串右邊存在多少 0

• 字串

  $>$ 15
  * is_ptr 設為 1 ，用來辨識此 xs 為 「長字串」
  * 字串儲存於 heap
  * 字串起點為 ptr
  * capacity 為儲存字串的大小，為 2 的次方。

思考上述的 15 是如何被定義？是否能夠反映出硬體特性？

jserv

stack alginment 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。

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

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，代表兩者為相同的字元，故要移除。

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

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;
}

測試一下

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

printf("string %p\ncopy %p",string.ptr, copy.ptr);

輸出結果

string 0x61627261626f6f66
copy   0x61627261626f6f66 

• 為了實作出 CoW ，我們必須接入 reference count，用來記錄該共享記憶體有多少人共用著。
• 採用在 strcut 加入新的結構 int *refcnt，並修改一下之前的 xs_cpy，來符合我們的 reference count

struct {
        char *ptr;
        size_t size : 54,
        capacity : 6;
        int *refcnt;
    };

• 我們利用 *refcnt 指標，指向共同的記憶體，也就是 src->refcnt。

...
if (!src->refcnt) {
    dest->refcnt = src->refcnt = (int*)malloc(sizeof(int));
    *(dest->refcnt) = 1;
} else {
    dest->refcnt = src->refcnt;
    *(dest->refcnt) += 1;
}
...

接著來修改 xs_concat
這邊我將問題切成兩種：串上後字元

$<$ 16 & 串上後字元

$\ge$ 16

• 串上後字元
  $<$ 16: create 一個新的 space ，來達到 CoW 的效果。
• 串上後字元
  $\ge$ 16: 因為已經 create 一個新的 space(在 xs_grow 內)，故只須注意是否還有其他人仍然使用著共享記憶體，故不能隨便 free 掉。

 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 掉。

...
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;
        }
    }
...

測試

    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));

輸出結果

[hahahahahafoobarbar)))))] : 24
[(((((hahahahahafoobarbar)))))] : 29

xs_strtok

• 功能: 和 strtok 相同，都是切割字串。
• strspn
• strpbrk

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;
}

測試一下

    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");

結果

haha kyle hello 

設計實驗，確認上述字串處理最佳化 (針對空間效率) 帶來的效益，應考慮到 locality of reference

• 可以從 cache miss 來判斷是否有 locality of reference
• 我們採用 strncpy 來當作這次實驗的對照組。
• 實驗中，我們重複複製 50000 次，來讓兩者差距較明顯。

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;
}

  /* 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

valgrind --tool=cachegrind ./xstring_COW

一開始，我們先用 ori_cpy 得到以下結果

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 來實驗。

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 來觀察 cache misses

sudo perf stat -e cache-misses ./xstring_COW

以下分別為 ori_cpy 以及 xs_cpy

ori_cpy

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

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

其中在作業系統，為了避免程式 fork 完後立刻 exec，因此採用 CoW 的機制。利用 parrent & children 共用未寫入的記憶體，來增加 children 的建立速度。

此外，若 children 第一時間就 exec 的話，也可以因為 CoW 的機制不會浪費記憶體空間以及時間了。

因此，我們研究 linux/fork.c，並參考 where is the source for fork() call in linux

• 我們發現在利用 syscall 呼叫 fork() 時，會去呼叫 do_fork

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
• 一開始， do_fork 會先檢查是哪個 system call

/*
	 * 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

p = copy_process(NULL, trace, NUMA_NO_NODE, args);

• 在 copy_prcoess 中，又去呼叫 dup_taskstruct`, which creates new kernel stack, thread_info and task_struct structures for the new process，也就是真正創建 children process 的位置。
• current 為目前運行程式的 pointer

p = dup_task_struct(current, node);

• copy_process 完成後，會去喚醒 childen

wake_up_new_task(p);

• 如果是 vfork 的話，必須等 children 呼叫 exec 或離開

if (clone_flags & CLONE_VFORK) {
		p->vfork_done = &vfork;
		init_completion(&vfork);
		get_task_struct(p);
	}

而 CoW 實現在 copy_process 內的 copy_mm。

retval = copy_mm(clone_flags, p);

參考同學的整理

• copy_mm 中， vfork 會直接進入條件式，因為呼叫 vfork 時 args.flags 會被設成 CLONE_VFORK | CLONE_VM，故直接共用一個mm_struct。
• 然而 fork 則會直接呼叫 dup_mm 來複製 parent 的 mm_struct。

...
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;
...