Try   HackMD

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_leftis_ptrflag 剛好會都是 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 佔有的記憶體空間不夠,重新配置一塊
    2lg(len)+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_ 可改為 valcnt,因為實質操作存取次數多,簡潔至上

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

  • 求出 structdata_ 位元組偏移值
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

xs_strtok_r


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


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