---
# System prepended metadata

title: 2021q1 Homework3 (quiz3)
tags: [sysprog2021]

---

# 2021q1 Homework3 (quiz3)
contributed by < `wiasliaw` >

###### tags: `sysprog2021`

## 進度

- [ ] 解釋上述程式碼運作原理，並提出改進方案

## 測驗

先看資料結構，如下

```cpp
typedef union {
    char data[16];

    struct {
        uint8_t filler[15], // 120 bits
        space_left : 4,
        is_ptr : 1,
        is_large_string : 1,
        flag2 : 1,
        flag3 : 1;
    };

    struct {
        char *ptr; // 64 bits
        size_t size : MAX_STR_LEN_BITS, // 54 bits
        capacity : 6;
    };
} xs;
```

可以知道 xs 大小為 16 bytes，heap 與 stack 的 對應的 bit 如表格所見。

| Union    | data[0-7]   | data[8-14]          | data[15][7-4] | data[15][3-0]                         |
| -------- | --------    | --------            | --------      | --------                              |
| stack    | filler[0-7] | filler[8-14]        | space_left    | is_ptr, is_large_string, flag2, flag3 |
| heap     | ptr         | size, capacity[5-4] | capacity[3-0] | is_ptr, is_large_string, flag2, flag3 |


### get flag or status of xs

* `xs_is_ptr` & `xs_is_large_string`
    * 回傳 `is_ptr` 和 `is_large_string` 兩個 flag
    * 如果 `is_ptr` 是 true，代表 xs 存入中或長字串在 heap 裡面
    * 如果 `is_large_string` 是 true，代表 xs 存入長字串在 heap 裡面

* `xs_size`
    * 回傳存入的字串長度
        * 如果是中長字串，取出 size
        * 如果是短字串，計算總容量 (15 bytes) 減去剩餘量 (space_left)

* `xs_is_capacity`
    * 回傳最大容量
        * 如果是短字串，此時字串儲存在 stack，最大容量固定為 15 bytes
        * 如果是長字串，此時字串儲存在 heap，最大容量為 $2^{capacity}$ bytes

```cpp
static inline bool xs_is_ptr(const xs *x) { return x->is_ptr; }

static inline bool xs_is_large_string(const xs *x)
{
    return x->is_large_string;
}

static inline size_t xs_size(const xs *x)
{
    return xs_is_ptr(x) ? x->size : 15 - x->space_left;
}

static inline size_t xs_capacity(const xs *x)
{
    return xs_is_ptr(x) ? ((size_t) 1 << x->capacity) - 1 : 15;
}
```

### xs function or macro

###### xs macro

* `xs_tmp`
    * 在初始化前，針對字串大小作檢查
    * [\_Static\_assert](https://en.cppreference.com/w/c/language/_Static_assert)
* `xs_literal_empty`
    * 初始化 xs 並設定 `space_left` 為 15

```c=
#define xs_tmp(x)                                                   \
    ((void) ((struct {                                              \
         _Static_assert(sizeof(x) <= MAX_STR_LEN, "it is too big"); \
         int dummy;                                                 \
     }){1}),                                                        \
     xs_new(&xs_literal_empty(), x)

#define xs_literal_empty() \
    (xs) { .space_left = 15 }
```

###### xs utility

* `ilog2`
    * 用於計算分配空間的大小
    * 假設字串長度為 X，如果 $X > 2^n$，則需要分配 $2^{n+1}$ 的空間
    * 為了方便描述，以下以 `uint8_t` 為例
        * 假設原本字串長度為 $5$ (= $00000101_{(2)}$)，需要分配 $8$ ($2^{2} < 5 < 2^{3}$，$n$ 為 $2$) 個 bytes
        * `__builtin_clz` 可以得到從 MSB 向低位數到第一個 1 之前有幾個 0，與 8 相減，可以得到第一個 1 是從 LSB 數過來的第幾位，這個位數加一即是需要分配空間的大小。

* `xs_new`
    * 根據字串長度建立 xs 的物件並回傳指標
    * 如果字串長度小於或等於 16，字串會複製進 stack，並更新 space_left
    * 如果字串長度大於 16，需要計算分配 heap 空間的大小並分配空間，最後將字串複製進 heap

* `xs_newempty`
    * 透過 `xs_tmp` 建立只有設定 space_left 的 xs 指標

* `xs_allocate_data`
    * 針對中長字串分配 heap 空間
    * 如果是長字串，先設定 is_large_string 為真，然後初始額外配置 4 給 reference counter，並設置 counter 數為 1

* `xs_data`
    * 根據 is_ptr 和 is_large_string 兩個 flag 回傳字串起始的位置

* `xs_free`
    * 釋放掉 xs 存入的字串
    * 如果是 heap 且引用計數器為零，則釋放掉分配在 heap 的空間
    * 最後利用 `xs_newempty` 回傳新的空的 xs 指標

:::danger
如果是長字串且引用計數器大於零，不應對 x 做任何事情，並回報為何不能釋放記憶體。但是回傳 `xs_newempty`，會更新原本 x 指標的位置，會造成迷途指標。

**製造一個長字串，並設定 reference counter 最後執行釋放**
```c=
xs A = *xs_tmp("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
xs_set_refcnt(&A, 10);
xs_free(&A);
```
**valgrind 檢查**
```bash=
valgrind --leak-check=full /path/to/main
```
**log**
```=
==12380== HEAP SUMMARY:
==12380==     in use at exit: 516 bytes in 1 blocks
==12380==   total heap usage: 2 allocs, 1 frees, 1,540 bytes allocated
==12380== 
==12380== 516 bytes in 1 blocks are definitely lost in loss record 1 of 1
==12380==    at 0x4C31ECB: malloc (vg_replace_malloc.c:307)
==12380==    by 0x108B4A: xs_allocate_data (in /home/leewei/Desktop/sysprog/quiz3-c/bin/main)
==12380==    by 0x108C66: xs_new (in /home/leewei/Desktop/sysprog/quiz3-c/bin/main)
==12380==    by 0x109684: main (in /home/leewei/Desktop/sysprog/quiz3-c/bin/main)
==12380== 
==12380== LEAK SUMMARY:
==12380==    definitely lost: 516 bytes in 1 blocks
==12380==    indirectly lost: 0 bytes in 0 blocks
==12380==      possibly lost: 0 bytes in 0 blocks
==12380==    still reachable: 0 bytes in 0 blocks
==12380==         suppressed: 0 bytes in 0 blocks
==12380== 
==12380== For lists of detected and suppressed errors, rerun with: -s
==12380== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
```
:::

* `xs_concat`
    * 將字串連接， prefix 接在目標字串之前， suffix 接在字串之後
    * 如果字串總長度(prefix, 目標字串, suffix 字串長度總和) 小於 capacity，不需要重新分配空間，利用 `memmove` 移動出 prefix 的空間，將 prefix 複製進去，最後將 suffix 從目標字串後複製進去。

* `xs_grow`
    * 改變 xs 的 capacity 到特定大小
    * 計算大小方式透過 `ilog2`
    * 如果是短字串需要增加空間，則要先資料利用額外的 `char[16]` 存起來，原先的空間會被改來存 heap 的指標位置。
    * 透過 `xs_allocate_data` 重新分配記憶體位置

* `xs_trim`
    * TODO
* `xs_cow_lazy_copy`
    * TODO

:::info
Copy on Write 是一種對記憶體管理的最佳化手段，如果請求的資源重複則不需要複製整個資源給請求者，只需要給請求者資源的指標，一直資源有被修改，系統才會複製另外一份副本。

以爬蟲為例，需要對 URL 作處理並發送請求以得到網頁內容，假設針對同樣一個域名例如 `https://example.com` 爬蟲並使用 multi thread 做平行處理（假定每次爬蟲都獨立，執行結果不會因為執行順序先後而改變），每次初始化一個 thread 都需要複製整個網址，能以 CoW 降低複製的成本。

* TODO: 模擬
    * 每次初始化 thread 都是以 `memcpy` 進行
    * 每次初始化 thread 都是以 `xs` 進行
:::

```cpp=
static inline int ilog2(uint32_t n) { return 32 - __builtin_clz(n) - 1; }

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;
        xs_allocate_data(x, x->size, 0);
        memcpy(xs_data(x), p, len);
    } else {
        memcpy(x->data, p, len);
        x->space_left = 15 - (len - 1);
    }
    return x;
}

static inline xs *xs_newempty(xs *x)
{
    *x = xs_literal_empty();
    return x;
}

static void xs_allocate_data(xs *x, size_t len, bool reallocate)
{
    /* Medium string */
    if (len < LARGE_STRING_LEN) {
        x->ptr = reallocate ? realloc(x->ptr, (size_t) 1 << x->capacity)
                            : malloc((size_t) 1 << x->capacity);
        return;
    }

    /* Large string */
    x->is_large_string = 1;

    /* The extra 4 bytes are used to store the reference count */
    x->ptr = reallocate ? realloc(x->ptr, (size_t)(1 << x->capacity) + 4)
                        : malloc((size_t)(1 << x->capacity) + 4);

    xs_set_refcnt(x, 1);
}

static inline char *xs_data(const xs *x)
{
    if (!xs_is_ptr(x))
        return (char *) x->data;

    if (xs_is_large_string(x))
        return (char *) (x->ptr + 4);
    return (char *) x->ptr;
}

static inline xs *xs_free(xs *x)
{
    if (xs_is_ptr(x) && xs_dec_refcnt(x) <= 0)
        free(x->ptr);
    return xs_newempty(x);
}

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

    xs_cow_lazy_copy(string, &data);

    if (size + pres + sufs <= capacity) {
        memmove(data + pres, data, size);
        memcpy(data, pre, pres);
        memcpy(data + pres + size, suf, sufs + 1);

        if (xs_is_ptr(string))
            string->size = size + pres + sufs;
        else
            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;
}

xs *xs_grow(xs *x, size_t len)
{
    char buf[16];

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

    /* Backup first */
    if (!xs_is_ptr(x))
        memcpy(buf, x->data, 16);

    x->is_ptr = true;
    x->capacity = ilog2(len) + 1;

    if (xs_is_ptr(x)) {
        xs_allocate_data(x, len, 1);
    } else {
        xs_allocate_data(x, len, 0);
        memcpy(xs_data(x), buf, 16);
    }
    return x;
}

xs *xs_trim(xs *x, const char *trimset)
{
    if (!trimset[0])
        return x;

    char *dataptr = xs_data(x), *orig = dataptr;

    if (xs_cow_lazy_copy(x, &dataptr))
        orig = dataptr;

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

static bool xs_cow_lazy_copy(xs *x, char **data)
{
    if (xs_get_refcnt(x) <= 1)
        return false;

    /* Lazy copy */
    xs_dec_refcnt(x);
    xs_allocate_data(x, x->size, 0);

    if (data) {
        memcpy(xs_data(x), *data, x->size);

        /* Update the newly allocated pointer */
        *data = xs_data(x);
    }
    return true;
}
```

### reference counter

:::info
reference counter 是一個計數器，用於紀錄資源被參照的次數。使用情境有 garbage collection，如果某個變數儲存的資源沒有被其他程式參照或是使用時，reference counter 應為 0，gc 就能以此回收不需要的空間。Rust 則是用於多重所有權，以追蹤資源有沒有被使用。
:::

:::warning
TODO: 討論 reference counting 的考量，特別是適用場景，接著才列出原始程式碼。
:notes: jserv
:::

* 當 xs 存入長字串時，會在 `x->ptr` 預留 `size_t + 4` 的空間儲存 reference count。下方四個 function 用於對 reference counter 操作
    * `xs_set_refcnt`: 指派值給 reference counter
    * `xs_inc_refcnt`: counter 計數加一
    * `xs_dec_refcnt`: counter 計數減一
    * `xs_get_refcnt`: 取得 counter 的值

```cpp
static inline void xs_set_refcnt(const xs *x, int val)
{
    *((int *) ((size_t) x->ptr)) = val;
}

static inline void xs_inc_refcnt(const xs *x)
{
    if (xs_is_large_string(x))
        ++(*(int *) ((size_t) x->ptr));
}

static inline int xs_dec_refcnt(const xs *x)
{
    if (!xs_is_large_string(x))
        return 0;
    return --(*(int *) ((size_t) x->ptr));
}

static inline int xs_get_refcnt(const xs *x)
{
    if (!xs_is_large_string(x))
        return 0;
    return *(int *) ((size_t) x->ptr);
}
```

