2020q1 Homework2 (quiz2)

contributed by < Hsuhaoxiang >

重新回答第 2 周測驗題

了解 xs 的設計

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 中每個成員皆小於等於 16 byte sizeof(xs) = 16
char *data 為存放短字串的地方
第一個 struct 中記錄了 xs 是長短字串的相關資訊， filler[15]佔用15 byte 是為了不讓後面存放資訊位置的地方改寫到短字串 data 的內容。
space_left 用了 struct 中的 bit-field 佔 4 bit ，is_ptr, flag 等共佔 1 byte
space_left 不紀錄長度，而是紀錄「最大短字串長度減去現在長度」，如此一來當短字串放滿 15 byte 後，最後的 space_left 、 is_ptr 、 flag 剛好會都是 0 也就是 \0 不影響短字串的 terminator，沒想到字串結尾的 1 個 byte 藉由 union 以及 bit-field 還能存下這些資訊！
第二個 struct 就是存放長字串的地方了 char* ptr 佔 8 個 byte ， size 放的是長字串所佔空間，扣掉 null character 就會都是 2 的指數次方減一，而 capacity 則是分配的記憶體大小裡面存的值為對數，所以還要再做指數運算才算得出大小，且保留最後 4-bit 讓 is_ptr, flag 的值不會被動到。

xs.c

程式列表應該適度分段，從功能探討起，連帶提及答題思維

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

好的

xs_new 與 AAA = ?

xs *xs_new(xs *x, const void *p)
{
    *x = xs_literal_empty();
    size_t len = strlen(p) + 1;
    if (len > 16) {
        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_new 判斷要建立的字串是長字串還是短字串做出對應的操作
從 xs_new 區分長短字串的判斷與題目 (len > AAA) 相同，其中 len = strlen(p) + 1

答案為 (c) 16

xs_trim

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
}

xs_trim 用來去除 x 的頭尾在 trimset 出現的字元
用 set_bit(x) 與 check_bit(x) 這兩個 macro 對字串頭尾進行切割
xs_trim 是負責去掉頭尾多餘的字串，如果本來是長字串，也就是使用 ptr 的字串如果變成小或等於 16 個字串還是會用 ptr 而不是 data[16] ，並且進行 xs_concat 時會因為 capacity 讓串接後的字串大小讓串接後的字串大小有問題，必須要再修改！

BBB = ?

uint8_t mask[BBB] = {0} 中 mask 用於下兩行的 macro check_bit(byte) 與 set_bit(byte)
uint_8 最大可到 255 ，(uint8_t) byte / 8 最大為 31

答案為 (a) 32

CCC = ?

利用 set_bit() 與 check_bit() 來找出需要被修剪的字元，因此 mask[index] 中放的是 trimset 字元的 ascii code % 8 之後的值，index 為 ascii code 除以 8。
了解之後就能發現 check_bit() 所要做的運算是 &

答案為 (b) &

xs_tmp(x)

#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 這個 macro 我其實我不知道為何需要特別去檢查 xs_new 中的 x 有沒有小或等於 16 個字元？這樣豈不是讓 xs 一開始只能初始為短字串再慢慢合併上去。

16 這個數字可變更，但取決於結構體的規劃，請對照看 (https://github.com/facebook/folly/blob/master/folly/FBString.h)，並參照 Cache 原理和實際影響，考慮到 cache line 空間。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

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 佔有的記憶體空間不夠，重新配置一塊
$2^{\lg (l e n) + 1}$ 的記憶體空間

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

將 prefix , suffix 字串到 string 的前後， capacity 不夠就使用 xs_grow()

延伸問題

以上述程式碼為基礎，提供字串複製 (應考慮到 CoW) 和類似 strtok 功能的函式實作

參考 folly::fbstring 中使用 CoW 的技巧

COW

struct RefCounted

先定義一種結構體 RefCounted 有兩個成員
refCount 為多少 xs 長字串正在參考原本的字串，只有用 cow_copy() 時數字才會增加
data_ 為字串開頭的記憶體位置，也是存放長字串的地方宣告成長度為 1 的陣列讓 data_表示為記憶體位置而不是資料，我有嘗試過把 data_[1] 換成 char *data 但最後會有問題，還沒找出原因，不過用這種宣告方式是更省記憶體的，比起我省下了一個指標的空間。

typedef struct refcnt {
    size_t cnt;
    char data_[1];
} refcnt_t;

refcounted 這名稱可縮減為 refcnt，對應 typedef 後為 refcnt_t。上方的 refCount_ 可改為 val 或 cnt，因為實質操作存取次數多，簡潔至上

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

已改

getDataOffset

求出 struct 中 data_ 位元組偏移值

static size_t getDataOffset() {
    return offsetof(refcnt_t, data_);
}

fromData

回傳給定字串的 refcnt_t 指標

static refcnt_t* fromData(char* p) {
    return (refcnt_t*)((void*)(size_t*)((void*) p - getDataOffset()));
}

refs

回傳給定字串的 cnt 也就是他被參考的次數

static size_t refs(char* p) {
    return fromData(p)->cnt;
}

incrementRefs

將 cnt 加 1

static void incrementRefs(char* p) {
    fromData(p)->cnt+=1;
}

decrementRefs

將 cnt 減 1 ，如果沒有其他指標參考這個 struct 則釋放記憶體

static void decrementRefs(char* p) {
    refcnt_t *dis = fromData(p);
    size_t oldcnt = (dis->cnt--);
    if (oldcnt == 1) {
        free(dis);
    }
}

create

當需要建立長字串 ( xs_new , xs_grow ), 改寫長字串 ( xs_concat ) 時分配記憶體給 refcn_t 並將回傳 data_ 這個存放字串的記憶體為

static char *create(const char* data, size_t size) {
    refcnt_t *result =malloc(getDataOffset() + (size + 1) * sizeof(char));
    result->cnt = 0;
    memcpy(result->data_, data, strlen(data)+1);
    return result->data_;
}

cow_cpy

xs *cow_cpy(xs *dst, xs *src){
    if (xs_is_ptr(src)){
        dst->is_ptr = true;
        dst->ptr = src->ptr;
        dst->size = src->size;
        dst->capacity = src->capacity;;
        incrementRefs(xs_data(src));
    }
    else{
        dst->is_ptr = false;
        dst->space_left = src->space_left;
        memcpy(dst->data , src->data, xs_size(src));
    }
    return dst;
}

對於長字串使用 CoW (copy on write) 這種最佳化手法，短字串直接進行 copy

測試

int main()
{
    xs string = *xs_tmp("()string()");
    printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));
    xs_trim(&string, ")(");
    printf("\n\n");
    printf("trim\n");
    printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));
    xs prefix = *xs_tmp("^^^^^^^^"), suffix = *xs_tmp("^^^^^^^^");
    xs_concat(&string, &prefix, &suffix);
    printf("\n\n");
    printf("string concat\n");
    printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));
    printf("string refcnt: %ld\n", refs(string.ptr));
    printf("\n\n");
    printf("cow_cpy\n");
    xs copystring = *cow_cpy(&xs_literal_empty(), &string);
    printf("string refcnt : %ld\n", refs(string.ptr));
    printf("copystring's refcnt : %ld\n", refs(copystring.ptr));
    xs_concat(&copystring, &prefix, &suffix);
    printf("\n\n");
    printf("copystring concat\n");
    printf("string refcnt : %ld\n", refs(string.ptr));
    printf("copystring's refcnt : %ld\n", refs(copystring.ptr));
    return 0;
}

結果

[()string()] : 10


trim
[string] :  6


string concat
[^^^^^^^^string^^^^^^^^] : 22
string refcnt: 0


cow_cpy
string refcnt : 1
copystring's refcnt : 1


copystring concat
string refcnt : 0
copystring's refcnt : 0

符合預期，在進行 cow_cpy 之後refcnt會加 1 ，將 copy 來的 string 跟 prefix , suffix 進行串接表示發生改寫需要進行真正的「複製」，所以refcnt必須減 1

xs_strtok

char *xs_strtok(xs *x, const char *delim)
{   
    char static *nextok;
    char *dataptr;
    if (!delim[0])
        return x;
    
    if (x){
        dataptr = xs_data(x);
    }
    else{
        if (!nextok)
            return NULL;
        dataptr = nextok;
    }
    /* similar to strspn/strpbrk but it operates on binary data */
    uint8_t mask[32] = {0};
//CCC 
#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 i,j, slen = strlen(dataptr), trimlen = strlen(delim);

    for (i = 0; i < trimlen; i++)
        set_bit(delim[i]);
    for (i = 0; i < slen; i++)
        if (!check_bit(dataptr[i]))
            break;
    dataptr += i;
    slen -= i;
    for (j = 0; j < slen; j++)
        if (check_bit(dataptr[j]))
            break;

    *(dataptr + j) = '\0';
    nextok = dataptr + j + 1;
    if(j + 1 >= slen){
        nextok = NULL;
    }
    return dataptr;
#undef check_bit
#undef set_bit
}

直接對字串進行改動還沒考慮 cow

測試

int main()
{
    xs string;
    char delim[8] = ", ", *tmp;
    xs_new(&string, "If a delimiter byte is found, it is overwritten with a null byte to terminate the current token");
    printf("delim: %s\n", delim);
    printf("string: %s\n\n", xs_data(&string));

    printf("%s\n", xs_strtok(&string, delim));
    while(tmp = xs_strtok(NULL, delim))
        printf("%s\n", tmp);
    return 0;
}

結果

delim: , 
string: If a delimiter byte is found, it is overwritten with a null byte to terminate the current token

If
a
delimiter
byte
is
found
it
is
overwritten
with
a
null
byte
to
terminate
the
current
token

2020q1 Homework2 (quiz2)

了解 xs 的設計

xs.c

xs_new 與 AAA = ?

xs_trim

BBB = ?

CCC = ?

xs_tmp(x)

xs_grow

xs_concat

延伸問題

以上述程式碼為基礎，提供字串複製 (應考慮到 CoW) 和類似 strtok 功能的函式實作

COW

struct RefCounted

getDataOffset

fromData

refs

incrementRefs

decrementRefs

create

cow_cpy

測試

結果

xs_strtok

測試

結果

xs_strtok_r

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

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