2020q2 Homework2 (quiz2)

contributed by <ire33164>

tags: `Linux Kernel`

測驗 `1` & 解釋程式碼

Union 設計

typedef union {
    /* allow strings up to 15 bytes to stay on the stack
     * use the last byte as a null terminator and to store flags
     * much like fbstring:
     * https://github.com/facebook/folly/blob/master/folly/docs/FBString.md
     */
    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;

由 union 的特性可知
xs 的結構體所占的空間會由 union 需要最大空間的成員所決定
因此比較三個成員 :

char data[16];

char data[16] : 需要 16 個 sizeof(char) 的空間 -> 16 bytes

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

需要 15 個 sizeof(uint8_t) (15 bytes) + 4 bits (space_bit) + 4 個 1 bit -> 16 bytes

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

需要 1 個 char * (8 bytes) + 54 bits + 6 bits -> 16 bytes - 4 bits

因此 xs 可使用 16 bytes 的空間
利用 GDB 追蹤記憶體使用空間如下 :

(gdb) b main
Breakpoint 1 at 0x172e: file xs.c, line 321.
(gdb) r
Starting program: /home/chia/Documents/linux2020/Xstring/xs 

Breakpoint 1, main () at xs.c:321
321	{
(gdb) p &string
$1 = (xs *) 0x7fffffffdc80
(gdb) p &string->data
$2 = (char (*)[16]) 0x7fffffffdc80
(gdb) p &string->filter
There is no member named filter.
(gdb) p &string->filler
$3 = (uint8_t (*)[15]) 0x7fffffffdc80
(gdb) p &string->space_left
$4 = (uint8_t *) 0x7fffffffdc8f ""
(gdb) p &string->is_ptr
$5 = (uint8_t *) 0x7fffffffdc8f ""
(gdb) p &string->flag1
$6 = (uint8_t *) 0x7fffffffdc8f ""
(gdb) p &string->flag2
$7 = (uint8_t *) 0x7fffffffdc8f ""
(gdb) p &string->flag3
$8 = (uint8_t *) 0x7fffffffdc8f ""
(gdb) p &string->ptr
$9 = (char **) 0x7fffffffdc80
(gdb) p &string->size
$10 = (size_t *) 0x7fffffffdc88
(gdb) p &string->capacity
$11 = (size_t *) 0x7fffffffdc88

data, filler, ptr 位在相同的記憶體位置
space_left, is_ptr, flag1, flag2, flag3 共用 8 個 bit
size + capacity 共用 60 bit 的話，剩下四個 bit 為 is_ptr, flag1, flag2, flag3

該設計中

char data[16] : 限制 stack 中最多只能放入 15 bytes 的字串
最後一個 byte 用來存放 terminator 其為 null 也是 0
uint8_t filler[15] : 前 15 bytes 是用來存取字串予以保留
space_left : 因 stack 上最多只可放 15 (
$2^{4} - 1$ ) 個 char，因此僅需要用 4 個 bit 來儲存目前 stack 上有多少 free byte (還可以存放幾個字元)，運算方式為 15 - (目前 stack 上的字元數量)
is_ptr : 若字串長度 > 15，即需要使用到 heap 時，設為1其餘都為0，又字串長度 <= 15 時，最後一個 byte 本就會被設為 null 也就是 0，因此也巧妙的設定 is_ptr 為 0
flag1, flag2, flag3 : 未使用
char *ptr : 若使用到 heap 即 is_ptr 為 1 時，用來儲存字串的開始位址
size_t size : 54 : 提供 54 bit 空間儲存字串 size，因此字串最大長度為
$2^{54} - 1$
size_t capacity : 6 : 記錄實際分配到的記憶體空間，使用 6 bit 紀錄是為了要可以裝下 size 的 54 bit，其最多可分配到
$2^{6} - 1$ = 63 的空間，也可以裝下 size 的 54，其中實際分配時是以
$2^{c a p a c i t y}$ 下去分配，也就是會分配到 1 << capacity 大小的空間
預留最後 4 bit 存放 is_ptr, flag1, flag2, flag3

Function `xs *xs_new` 與 AAA

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

上述程式碼是根據儲存的字串長度去初始化一個新的型別為xs的物件

*x = xs_literal_empty();

初始化 x 的 space_left 為 15

size_t len = strlen(p) + 1;

取得字串長度並 + 1

因為 strlen 僅回傳字元 \0 前的個數，因此長度必須再加上 1，給予 \0 空間

if (len > AAA) {

根據字串長度選擇要配置 stack 或 heap 的空間
因 stack 上可存放的字串長度的最大值為 15，因此 len 若大於 16 就代表需配置到 heap 的空間

len = strlen(p) + 1

AAA 為 16

x->size = len - 1;
x->is_ptr = true;
x->ptr = malloc((size_t) 1 << x->capacity);
memcpy(x->ptr, p, len);

需要配置到 heap 空間的情況
capacity 儲存
size 儲存字串長度
is_ptr 設為 1，因配置空間為 heap
利用 memcpy 將指定的字串複製到 ptr 指向的記憶體中

memcpy(x->data, p, len);
x->space_left = 15 - (len - 1);

需要配置到 stack 空間的情況

Function `xs *xs_grow`

xs *xs_grow(xs *x, size_t len)
{
    if (len <= xs_capacity(x))
        return x;
    len = ilog2(len) + 1;
    if (xs_is_ptr(x))
        x->ptr = realloc(x->ptr, (size_t) 1 << len);
    else {
        char buf[16];
        memcpy(buf, x->data, 16);
        x->ptr = malloc((size_t) 1 << len);
        memcpy(x->ptr, buf, 16);
    }
    x->is_ptr = true;
    x->capacity = len;
    return x;
}

用來將 x 的空間增長到一定的 size

if (len <= xs_capacity(x))
    return x;

確定目前配置的空間是否滿足欲增長到的 size

if (xs_is_ptr(x))

根據 x 目前配置的位置做不同的處理

x->ptr = realloc(x->ptr, (size_t) 1 << len);

若原配置在 heap 上，直接增長 ptr 指向的記憶體空間大小至需要的 size

realloc()

The realloc() function changes the size of the memory block pointed to
by ptr to size bytes. The contents will be unchanged in the range from
the start of the region up to the minimum of the old and new sizes. If
the new size is larger than the old size, the added memory will not be
initialized.

即使用 realloc 可以在不修改到內容的情況下，重新設定需要的空間大小

char buf[16];
memcpy(buf, x->data, 16);
x->ptr = malloc((size_t) 1 << len);
memcpy(x->ptr, buf, 16);

若原配置在 stack 上
暫存原字串至 buf[16] 中
利用 malloc 配置需要的記憶體
將原字串利用 memcpy 複製回新 allocate 的空間

Function `xs *xs_concat`

xs *xs_concat(xs *string, const xs *prefix, const xs *suffix)
{
    size_t pres = xs_size(prefix), sufs = xs_size(suffix),
           size = xs_size(string), capacity = xs_capacity(string);

    char *pre = xs_data(prefix), *suf = xs_data(suffix),
         *data = xs_data(string);

    if (size + pres + sufs <= capacity) {
        memmove(data + pres, data, size);
        memcpy(data, pre, pres);
        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);
        xs_free(string);
        *string = tmps;
        string->size = size + pres + sufs;
    }
    return string;
}

將串接三個字串到 string 中，其順序為 prefix + string + suffix

if (size + pres + sufs <= capacity) {

檢查目前 string 配置的空間是否足夠提供串接後所需的空間

memmove(data + pres, data, size);
memcpy(data, pre, pres);
memcpy(data + pres + size, suf, sufs + 1);
string->space_left = 15 - (size + pres + sufs);

目前 string 配置的空間足夠提供串接後所需的空間
因 data + pres 的位址可能與 data 空間 overflap，因此使用 memmove
就是把 data 往後移，預留存放 pres 的空間
複製 pre 到 data 先前預留的空間
複製 suf 到 (data + pres + size) 的位址，長度為 sufs + 1 是因為除了複製字串外還有複製 \0
更新 space_left

memmove

The memmove() function copies n bytes from memory area src to memory
area dest. The memory areas may overlap: copying takes place as though
the bytes in src are first copied into a temporary array that does not
overlap src or dest, and the bytes are then copied from the temporary
array to dest.

memcpy

The memcpy() function copies n bytes from memory area src to memory
area dest. The memory areas must not overlap. Use memmove(3) if the
memory areas do overlap.

兩者的差別在於 memmove 會先將欲複製的空間存到 temporary array
再將 temporary array 的值複製到 dest 中
但 memcpy 是直接複製過去
memcpy 的方式在 dest 和 src 位址有交疊 (overlap) 時會產生錯誤

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);
xs_free(string);
*string = tmps;
string->size = size + pres + sufs;

目前 string 配置的空間並不足以提供串接後所需的空間
直接 create 一個新的 xs
利用 xs_grow 擴充記憶體空間至 (size + pres + sufs)
取得 data 的 ptr 進行跟上述一樣的串接流程
用 tmp 作為新的 string 位址，並釋放原 string 的記憶體空間

Function `xs *xs_trim` & BBB & CCC

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

去除字串中 trimset 的字元

uint8_t mask[BBB] = {0};

用來紀錄哪些字符為 trimset
根據 check_bit 和 set_bit 中 mask[(uint8) byte / 8] 相當於 mask[(uint8) byte >> 3] ，其實也就是實際上只用到 8 - 3 = 5 bit
因此 BBB 最多只會用到
$2^{5}$ 的空間，由此推論 BBB 為 32

BBB 為 32

#define set_bit(byte) (mask[(uint8_t) byte / 8] |= 1 << (uint8_t) byte % 8)

將 trimset 的字元 8 bit 拆成兩部份
- 從左往右數 5 bit 作為 mask 的 index
- 從右往左數 3 bit 為 1 往左 shift 的值，其結果為 mask[index] 的值
例如字元 \ 的 ascii code 為 0101 1100，那麼就將 mask[0000 1011] 的從右邊數來第 4 個 bit 設為 1，代表 \ 是 trimset 的成員，需要被裁剪掉

為何是 5 3 分？
猜測是因 char 為 1 byte 的型別，因此 mask 的 type 為 uint8_t
接著因為每個 mask 都有 8 個 bit 可以使用
也就可以用來標示 8 種狀態 (0 ~ 7) -> (0 ~

2^{3} - 1

)
所以就將 char 的後 3 bit 作為 1 shift 的依據
剩下的 8 - 3 = 5 則當作 mask 的 index
就可以完整表示 8 bit 的 char

#define check_bit(byte) (mask[(uint8_t) byte / 8] CCC 1 << (uint8_t) byte % 8)

用來檢查傳入的字元是否為 trimset 的成員
假如要檢查 \ 是否為 trimset 的成員，就看 mask[0000 1011] 的從右邊數來第 4 個bit 是否為 1，因此 CCC 使用 & 較為合適，將 (指定的 bit & 1) 可以直接得到原本的值，如 1 & 1 == 1, 0 & 1 == 0

CCC 為 &

for (i = 0; i < trimlen; i++)
    set_bit(trimset[i]);

將 trimset 的成員紀錄到 mask 中

for (i = 0; i < slen; i++)
    if (!check_bit(dataptr[i]))
        break;

利用 check_it 從頭逐個檢查字串中的字元是否為 trimset 的成員
將第一個非 trimset 成員的 offset 紀錄到 i 中
i 代表字串中第幾個字元開始不為 trimset 的成員

for (; slen > 0; slen--)
    if (!check_bit(dataptr[slen - 1]))
        break;

利用 check_it 從尾巴開始逐個檢查字串中的字元是否為 trimset 的成員
慢慢減去 slen 的值，直到碰到字串中最後一個不為 trimset 的成員的字元
slen 代表字串中從頭開始數到最後一個不為 trimset 的成員的字元的長度

dataptr += i;
slen -= i;

將 ptr 移到字串中第一個開始不為 trimset 的成員的位置
slen 扣掉前面為 trimset 成員的長度

memmove(orig, dataptr, slen);

將去除頭尾 trimset 成員的字串複製回 orig 中 => 成功去頭去尾

延伸問題

function `xs xs *cpy` (考慮 CoW)

參考 folly::fbstring 中記憶體配置的技巧設計實現 reference count

Reference count

struct Ref_Count {
    size_t RefCount_;
    char data_[1];
};

處理 reference count 的 struct 中包含兩個 member
- size_t RefCount_ : 用來紀錄 reference count
- char data_[0] : 利用宣告長度為 1 的陣列，可以直接紀錄下 struct Ref_Count 真正需要的記憶體空間的尾端，而這個 address 同時也是存放字串開頭的位址
這樣設計主要的技巧在於，字串開頭其實是放在 struct 中的 data_ 中，並讓 xs 的 ptr 指向 data_，因此只要將 ptr 的位址減去下方的 rc_getDataOffset () 即可取得 Ref_Count 並對其操作

static inline size_t rc_getDataOffset ()
{
    return offsetof(struct Ref_Count, data_);
}

利用 offsetof() 取得 struct 中 data_ 與 struct 開頭的 offset，在藉由 data_ 取得 struct Ref_Count 的 address 時會使用到

offsetof

The macro offsetof() returns the offset of the field member from the
start of the structure type.

offsetof 會回傳 struct 開頭與其 member 間隔了多少 bytes

static inline struct Ref_Count* rc_fromData (char *x)
{
    return (struct Ref_Count *)((void *)x - rc_getDataOffset());
}

用來取得 struct Ref_Count 的 address 以利後續對 Ref_Count 的操作
傳入 data_ 的 address，往前扣掉 data_ 與 struct 開頭的 offset 即為 struct Ref_Count 的 address

static inline size_t rc_count (char *x)
{
    return rc_fromData(x)->RefCount_;
}

取得 RefCount

static inline char *rc_create (const void *p, size_t capacity)
{
    struct Ref_Count *result = malloc(rc_getDataOffset() + ((size_t) 1 << capacity));
    result->RefCount_ = 0;
    memcpy(result->data_, p, strlen(p) + 1);
    return result->data_;
}

create struct Ref_Count
因上述 struct Ref_Count 中的技巧，因此這邊 malloc 的空間為 offset + 字串需要的空間

static inline void rc_increment (char *x)
{
    rc_fromData(x)->RefCount_++;
}

RefCount 加 1

static inline void rc_decrement (char *x)
{
    struct Ref_Count *dis = rc_fromData(x);
    if (dis->RefCount_ == 0) {
        free(dis);
    } else {
        dis->RefCount_--;
    }
}

RefCount 減 1
若原本 RefCount 就為 0 的話代表並沒有其他的 xs 與它共用記憶體，因此 decrement 時可以直接釋放掉原本的記憶體

xs_cpy

xs *xs_cpy (xs *dest, const xs *src)
{
    if (xs_is_ptr(src)) {
        /* String on heap */
        dest->ptr = src->ptr;
        dest->size = src->size;
        dest->capacity = src->capacity;
        dest->is_ptr = true;
        rc_increment(xs_data(src));
    } else {
        /* String on stack */
        memcpy(dest->data, src->data, xs_size(src));
        dest->space_left = src->space_left;
        dest->is_ptr = false;
    }

    return dest;
}

字串長度小於 16 就直接複製
字串長度大於 16 則利用 Copy-on-write 的技巧，其利用到 reference count 的技巧
- 將 reference count ++

xs_new

...

x->ptr = rc_create(p, x->capacity);

...

若 new xs 時傳入的字串長度超過 16 ，則 create Ref_Count 並將 ptr 指向 Ref_Count 中的 data_

測試 xs_new 和 xs_cpy

int main()
{
    xs newString = *xs_new(&xs_literal_empty(), "qqqqqqqqqqqqqqqqq");
    printf("[%s] : %2zu\n", xs_data(&newString), xs_size(&newString));
    printf("src's refcount : %ld\n", rc_count(newString.ptr));

    xs copiedString = *xs_cpy(&xs_literal_empty(), &newString);
    printf("[%s] : %2zu\n", xs_data(&copiedString), xs_size(&copiedString));
    printf("src's refcount : %ld\n", rc_count(copiedString.ptr));

    return 0;
}

輸出 :

[qqqqqqqqqqqqqqqqq] : 17
src's refcount : 1
[qqqqqqqqqqqqqqqqq] : 17
src's refcount : 2

refcount 為 2 符合預期

xs_grow

xs *xs_grow(xs *x, size_t len)
{
    if (len <= xs_capacity(x))
        return x;
    len = ilog2(len) + 1;
    if (xs_is_ptr(x))
        x->ptr = realloc(x->ptr, (size_t) 1 << len);
    else {
        char buf[16];
        memcpy(buf, x->data, 16);
        x->ptr = rc_create(xs_data(x), len);
    }
    x->is_ptr = true;
    x->capacity = len;
    return x;
}

因傳入的 x 已經在 xs_concat() 中處理過 cow 的問題，因此若 x 在 heap 上可以直接使用 realloc 重新分配記憶體
若原本在 stack 上，則改成 allocate 到 heap 上並比較長字串辦理，建立 Ref_Count

xs_concat

xs *xs_concat(xs *string, const xs *prefix, const xs *suffix)
{
    if (xs_is_ptr(string)) {
        if (rc_count(xs_data(string)) > 0) {
            rc_decrement(xs_data(string));
            string->ptr = rc_create(xs_data(string), xs_capacity(string));
        }
    }

...
}

處理 COW 的問題
若字串在 heap 上，且該字串有被複製或是複製別人而來，就必須真的複製字串 (因為要修改了)
- 先將 RefCount 減一
- 建立 Ref_Count 使用新 malloc 的記憶體空間

xs_free

static inline xs *xs_free(xs *x)
{
    if (xs_is_ptr(x))
        rc_decrement(xs_data(x));
    return xs_newempty(x);
}

若在 heap 上，就將 RefCount 減一
若在 stack 上，直接把 data 改成空字串

測試 xs_concat & xs_grow & xs_free

#include <stdio.h>

int main()
{
    xs string = *xs_tmp("\n foobarbar \n\n\n");
    xs_trim(&string, "\n ");
    printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));

    xs prefix = *xs_tmp("(((((("), suffix = *xs_tmp("))))))");
    xs_concat(&string, &prefix, &suffix);
    printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));

    xs copiedString = *xs_cpy(&xs_literal_empty(), &string);
    printf("[%s] : %2zu\n", xs_data(&copiedString), xs_size(&copiedString));
    printf("src's refcount : %ld\n", rc_count(string.ptr));
    printf("copiedString's refcount : %ld\n", rc_count(copiedString.ptr));

    xs copiedString2 = *xs_cpy(&xs_literal_empty(), &string);
    printf("src's refcount : %ld\n", rc_count(string.ptr));

    xs_concat(&string, &prefix, &suffix);
    printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));
    printf("src's refcount : %ld\n", rc_count(string.ptr));
    printf("[%s] : %2zu\n", xs_data(&copiedString), xs_size(&copiedString));
    printf("copiedString's refcount : %ld\n", rc_count(copiedString.ptr));

    return 0;
}

預期輸出 :

[foobarbar] : 9
[((((((foobarbar))))))] : 21
[((((((foobarbar))))))] : 21
src's refcount : 1
copiedString's refcount : 1
src's refcount : 2
[((((((((((((foobarbar))))))))))))] : 33
src's refcount : 0
[((((((foobarbar))))))] : 21
copiedString's refcount : 1

實際輸出 :

Memory leak 問題
跑跑看 valgrind 來偵測是否有 memory leak 的問題

valgrind -q --leak-check=full ./xs

輸出 :

==6750== 40 bytes in 1 blocks are definitely lost in loss record 1 of 2
==6750==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6750==    by 0x108A06: rc_create (in /home/chia/Documents/linux2020/Xstring/xs)
==6750==    by 0x108CB5: xs_grow (in /home/chia/Documents/linux2020/Xstring/xs)
==6750==    by 0x108F8C: xs_concat (in /home/chia/Documents/linux2020/Xstring/xs)
==6750==    by 0x109596: main (in /home/chia/Documents/linux2020/Xstring/xs)

在 function rc_create 中存在 memory leak 的問題
但目前找不到問題所在
決定先把其他項作業要求完成

後來發現原來是 main 裡的 xs 忘記 free 阿，真的很白痴 = =

xs_trim

xs *xs_trim(xs *x, const char *trimset)
{
    ...
    
    /* 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.
     */
    if (xs_is_ptr(x) & slen != xs_size(x)) {
        if (rc_count(xs_data(x)) > 0) {
            rc_decrement(xs_data(x));
            x->ptr = rc_create(xs_data(x), xs_capacity(x));
            orig = xs_data(x);
        }
    }
    memmove(orig, dataptr, slen);
    
    ...
    
}

檢查是否在 heap 上且此字串確定要修改
將 RefCount 減 1 (因為要對複製的字串寫入了)
建立 Ref_Count 使用新 malloc 的記憶體空間
把 orig 指向新的 ptr

測試 xs_trim & xs_cpy

#include <stdio.h>

int main()
{
    xs string = *xs_tmp("\n foobarbar \n\n\n");
    xs_trim(&string, "\n ");
    printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));

    xs prefix = *xs_tmp("(((((("), suffix = *xs_tmp("))))))");
    xs_concat(&string, &prefix, &suffix);
    printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));
    xs cpy = *xs_cpy(&xs_literal_empty(), &string);
    printf("[%s] : %2zu\n", xs_data(&cpy), xs_size(&cpy));
    printf("Ref count of string : %ld\n", rc_count(xs_data(&string)));

    xs_trim(&string, "()");
    printf("After trim : [%s] : %2zu\n", xs_data(&string), xs_size(&string));
    printf("Ref count of string : %ld\n", rc_count(xs_data(&string)));
    printf("Ref count of cpy : %ld\n", rc_count(xs_data(&cpy)));
    return 0;
}

預期輸出 :

[foobarbar] :  9
[((((((foobarbar))))))] : 21
[((((((foobarbar))))))] : 21
Ref count of string : 1
After trim : [foobarbar] :  9
Ref count of string : 0
Ref count of cpy : 0

實際輸出 :

TODO :
考慮到 race condition 的問題
要將 Ref_Count 中的 RefCount 改成利用 atomic 實做

`strtok` 功能實作

char *strtok(char *str, const char *delim)
- str : 欲被分割的字串，若為 NULL 則延續前一次的 str
- delim : 用來分割的字串
- return : str 中第一個被分割下來的字串

char *xs_strtok (xs *x, const const char *delim)
{
    /* Stored the stop pointer */
    static char *remain_str = NULL;

    /* Assign string to remain_str first call.
     * Don't need to change remain_str If x is NULL
     */
    if (x)
        remain_str = xs_data(x);
    
/* similar to strspn/strpbrk but it operates on binary data */
    uint8_t mask[32] = {0};

#define check_bit(byte) (mask[(uint8_t) byte / 8] & 1 << (uint8_t) byte % 8)
#define set_bit(byte) (mask[(uint8_t) byte / 8] |= 1 << (uint8_t) byte % 8)

    size_t start_token_idx, end_token_idx, slen = strlen(remain_str), trimlen = strlen(delim);

    for (size_t i = 0; i < trimlen; i++)
        set_bit(delim[i]);
    for (start_token_idx = 0; start_token_idx < slen; start_token_idx++)
        if (!check_bit(remain_str[start_token_idx])) {
            break;
        }
    for (end_token_idx = start_token_idx + 1; end_token_idx < slen; end_token_idx++)
        if (check_bit(remain_str[end_token_idx])) {
            break;
        }

    size_t cpylen = end_token_idx - start_token_idx;
    /* Not found delimit or only contain delimit in string */
    if (cpylen == slen || start_token_idx == slen)
        return NULL;

    char *result = malloc(cpylen * sizeof(char) + 1);
    memcpy(result, remain_str + start_token_idx, cpylen);
    /* Add null at the end of string */
    result[cpylen + 1] = '\0';
    remain_str += end_token_idx;

    return result;
#undef check_bit
#undef set_bit
}

因為跟 xs_trim() 都有使用到字串位元的比較，因此沿用 check_bit 和 set_bit
利用 static variable 去儲存前一次字串切到的位置
- 用來實做 strtok() 中傳入 NULL 後可以從上次切的字串符開始切
若傳入的 x 為 NULL，則沿用先前的 remain_str
start_token_idx : 紀錄欲回傳的字串開頭的 idx
end_token_idx : 紀錄欲回傳的字串結尾的 idx + 1
若字串中找不到 delimit 或字串只包含 delimit 就回傳 NULL
malloc 需要的空間並利用 memcpy 複製指定位置的 string
將 remain_str 指向取下字串的下一個字元

這樣的方式在呼叫 xs_strtok() 回傳的字串在使用完後是需要利用 free() 來釋放記憶體的
但其實有另外的方式可以不用特別 free() 那就是要直接去改動原 xs 中的字串

直接將字串用 '\0' 切開

但這會牽涉到 CoW 的使用，根據我的寫法也是須另外 malloc() 出空間
因此想說既然都要 malloc() 那就先實做不牽涉到 CoW 也就是維持原字串值
而需要 free() 的版本

測試 xs_strtok

int main()
{
    xs string = *xs_tmp("\n foobarbar \n\n\n");
    xs_trim(&string, "\n ");
    printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));

    xs prefix = *xs_tmp("(((((("), suffix = *xs_tmp("))))))");
    xs_concat(&string, &prefix, &suffix);
    printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));

    char *str = xs_strtok(&string, "bar");
    while (str != NULL) {
        printf("str : %s\n", str);
        free(str);
        str = xs_strtok(NULL, "bar");
    }
    
    xs_free(&string);
    return 0;
}

輸出 :

[foobarbar] :  9
[((((((foobarbar))))))] : 21
str : ((((((foo
str : ))))))

測試 memory leak :

$ valgrind -q --leak-check=full ./xs

結果 : 沒問題!!

字串處理最佳化 (針對空間效率) 帶來的效益

觀測有使用 copy-on-write 與沒使用 copy-on-write 兩種情況的記憶體使用情況與效能差距

實做一個不使用 copy-on-write，直接複製字串的 function 作為實驗的對照組

xs *xs_cpy_without_cow (xs *dest, const xs *src) {
    if (xs_is_ptr(src)) {
        /* String on heap */
        dest->ptr = src->ptr;
        dest->size = src->size;
        dest->capacity = src->capacity;
        dest->is_ptr = true;
        dest->ptr = malloc((size_t) 1 << dest->capacity);
        memcpy(dest->ptr, src->ptr, xs_size(src) + 1);
    } else {
        /* String on stack */
        memcpy(dest->data, src->data, xs_size(src));
        dest->space_left = src->space_left;
        dest->is_ptr = false;
    }

    return dest;
}

分別使用 xs_cpy() 和 xs_cpy_without_cow() 做 1000000 次的字串複製

記憶體使用量

使用 Valgrind 觀察 :

$ valgrind --tool=massif ./xs
$ ms_print massif.out.xxxxx

xs_cpy_without_cow

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 80    162,844,350       38,737,912       30,990,312     7,747,600            0
 81    164,693,694       39,178,232       31,342,568     7,835,664            0
 82    166,543,038       39,618,552       31,694,824     7,923,728            0

xs_cpy

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
  0              0                0                0             0            0
  1        145,422               56               40            16            0

根據這次使用 valgrind massif 分析的結果可以明顯看到使用 copy-on-write 的記憶體使用量遠小於直接複製的結果

cache-misses (locality reference)

使用 perf 觀察 :

$ perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./xs

xs_cpy_without_cow

 Performance counter stats for './xs' (5 runs):

         1,062,942      cache-misses              #   87.664 % of all cache refs      ( +-  0.20% )
         1,212,514      cache-references                                              ( +-  0.32% )
       392,861,932      instructions              #    2.02  insn per cycle           ( +-  0.02% )
       194,458,813      cycles                                                        ( +-  0.08% )

       0.064151306 seconds time elapsed                                          ( +-  2.17% )

xs_cpy

Performance counter stats for './xs' (5 runs):

             7,993      cache-misses              #   15.615 % of all cache refs      ( +- 47.47% )
            51,188      cache-references                                              ( +-  3.24% )
       136,703,400      instructions              #    2.12  insn per cycle           ( +-  0.01% )
        64,623,243      cycles                                                        ( +-  0.11% )

       0.021895735 seconds time elapsed                                          ( +-  1.79% )

根據這次 perf stat 的結果可以明顯發現使用 Copy-on-Write 後

cache-miss : 從 1062942 降到 7993
cache-reference : 從 1,212,514 降到 51,188
執行時間降為原本的三分之一

在 Linux 核心原始程式碼中，找出類似手法的 SSO 或 CoW 案例並解說

linux/rmap.h

2020q2 Homework2 (quiz2)

tags: Linux Kernel

測驗 1 & 解釋程式碼

Union 設計

Function xs *xs_new 與 AAA

Function xs *xs_grow

Function xs *xs_concat

Function xs *xs_trim & BBB & CCC

延伸問題

function xs xs *cpy (考慮 CoW)

Reference count

xs_cpy

xs_new

xs_grow

xs_concat

xs_free

xs_trim

strtok 功能實作

字串處理最佳化 (針對空間效率) 帶來的效益

記憶體使用量

cache-misses (locality reference)

在 Linux 核心原始程式碼中，找出類似手法的 SSO 或 CoW 案例並解說

Read more

2020q1 Homework1 (lab0)

Clock-driven scheduling

Deploy nodejs server to Heroku

2020q1 Homework4 (khttpd)

tags: `Linux Kernel`

測驗 `1` & 解釋程式碼

Function `xs *xs_new` 與 AAA

Function `xs *xs_grow`

Function `xs *xs_concat`

Function `xs *xs_trim` & BBB & CCC

function `xs xs *cpy` (考慮 CoW)

`strtok` 功能實作