# 2021q1 Homework3 (quiz3)
contributed by < `chiehen` >
###### tags:`linux2021`

## Check List

- [x] 解釋上述程式碼運作原理，並提出改進方案;
- [x] 以上述程式碼為基礎，提供字串複製 (應考慮到 CoW) 的函式實作;
- [ ] 設計實驗，確認上述字串處理最佳化 (針對空間效率) 帶來的效益，應考慮到 locality of reference，善用 GDB 追蹤和分析，確認字串的確符合預期地配置於 stack 或 heap;
- [ ] 嘗試將 quiz2 提到的 string interning 機制整合，提出對空間高度最佳化的字串處理工具函式庫
- [ ] 在 Linux 核心原始程式碼中，找出類似手法的 SSO 或 CoW 案例並解說;

## 解釋程式碼

為了有效利用字串儲存空間，自行定義結構 xs 將短字串儲存於 stack 而中長字串儲存於 Heap ，並以將指向此空間的指標儲存於結構中

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, is_large_string : 1, flag2 : 1, flag3 : 1;
    };

    /* heap allocated */
    struct {
        char *ptr;
        /* supports strings up to 2^MAX_STR_LEN_BITS - 1 bytes */
        size_t size : MAX_STR_LEN_BITS,
                      /* capacity is always a power of 2 (unsigned)-1 */
                      capacity : 6;
        /* the last 4 bits are important flags */
    };
} xs;

將定義出此種結構：
<table>
<thead><tr><th colspan="100">union xs</th></tr></thead>
<tbody>
<tr><td colspan="100">char data[16] </td></tr>
<tr>
<td colspan="4">char filter[15]</td>
<td colspan="1">space_left</td>
<td colspan="1">flags(4 bits)</td>
</tr>
<tr>
<td colspan="2">char *ptr</td>
<td colspan="2">size</td>
<td colspan="1">capacity</td>
<td colspan="1">(4 bits)</td>
</tr>
<tr style="display:none">
<td></td><td></td><td></td><td></td><td></td><td></td>
</tr>
</tbody>
</table>

其中 capacity 並沒有完全對齊 space_left, 但第二個結構中的 4 bits 有與 flags 對齊

而在此結構中各成員分別代表這意義
* for 短字串
* data: 儲存最長 15 bytes 的字串
* space_left: 剩餘的可使用空間 （15 - 字串長度）
* is_ptr: 標示是否為中長字串（存於 heap）
* is_large_string: 長度大於 LARGE_STRING_LEN 的字串, 會進行 Cow 的處理
* for 中長字串
* ptr: 儲存中長字串在 heap 上的地址
* size: 字串的長度
* capacity: 在 heap 上所配置的記憶體大小

這裡可以注意到因為短字串的大小是以剩餘空間定義, 因此當字串長度為 15 時，後面須接著 null terminator `'\0'`, 其 ASCII 編碼為 0x00 , 因此在 space_left 及其他 flag 上也仍是正確的值。

因為 C99 6.5.2.3 Structure and union members 中提到的例外規定:
> One special guarantee is made in order to simplify the use of unions: if a union contains several structures that share a common initial sequence (see below), and if the union object currently contains one of these structures, it is permitted to inspect the common initial part of any of them anywhere that a declaration of the complete type of the union is visible. Two structures share a common initial sequence if corresponding members have compatible types (and, for bit-fields, the same widths) for a sequence of one or more initial members.

可以發現只要 struct 間的相對成員是 compatible types, 是允許任意查看這些區域的。因此在即使使用 ptr 儲存字串, 仍可查看 is_ptr 等 flag

### 函式解釋
在主程式中主要對函做了三種操作：
* xs_new: 建立一個 xs
* xs_trim: 將有頭尾的特定符號裁掉
* xs_concate: 進行字串串接

以下將依序解釋:
#### xs_new
在實際建立物件時, 檢查使用者欲儲存的是否太大, 如果太大則拒絕, 不然則進入 xs_new 進行字串建立

/* Memory leaks happen if the string is too long but it is still useful for
 * short strings.
 */
#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))

:::warning
不太知道 xs_literal_empty()
> 不知道就說不知，不要裝可愛說「不太知道」，後者對討論無益
> :notes: jserv
:::

* 若字串長度大於 15 （不含 '\0') 則透過 `xs_allocate_data` 配置 heap 上的記憶體, 反之則將內容複製在至 data (在 stack 上)
* 2^capacity^ bytes 為實際利用 malloc 配置於 heap 的容量, 大於字串的長度, 最多為字串大小的兩倍

xs *xs_new(xs *x, const void *p)
{
    *x = xs_literal_empty();
    size_t len = strlen(p) + 1;
    if (len > 16) { // NNN
        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;
}

在配置長字串時預留 4 bytes (int 的大小)作為 reference counter
在建立長字串也將 reference counter 設為 1
:::warning
需要討論 reference counting 的設計考量
:notes: jserv
:::

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

#### xs_trim

:::warning
「與其他 string 共用記憶體」此描述可能會誤導讀者，應聲明為，指向同一份記憶體空間，「共用」(share) 隱含的意思和該函式實際行為不同。
:notes: jserv
:::

* 在進行 memory 變動前, 透過 xs_cow_lazy_copy 將與其他 string 共用記憶體的長字串, 進行實際的 copy（再配置出另一份記憶體）
* 透過 set_bit 將欲裁切字元以 mask 的方式表示, 以便後續能以 bitwise 的方式比對字元, 此種編碼方式能在比對時對多種欲裁切字元一次比對，以下以字元 `'\n'` (0x0A), 而欲比較對象為 `'A'` (0x41) 舉例說明:
1. `set_bit('\n')` 將 mask[1] 的第 3 個位元(LSB 為第 1 個位元) 設成 1
2. `check_bit('A')` 將比對 mask[8] 的第 2 個位元 (即 'A' 在 mask 上的編碼) 是否為 1
* char 的 大小為 1 byte, 因此總共有 2^8^ = 256 種可能, 為了將每一種字元都能對應至某個 mask 上的某一個 bit 且不重複, 需要有 256 / 8 = 32 個 mask
* 利用兩個 for 迴圈分別從頭尾兩端比對, 找到裁切後字串的開始位址與長度
* 將裁切後字串內容移至原先的字串開頭, 並更新 xs 資訊

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) (CCC)
#define set_bit(byte) (mask[(uint8_t) byte / 8] |= 1 << (uint8_t) byte % 8) // SSS
    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_concat
* 同 xs_trim, 在進行 memory 變動前, 透過 xs_cow_lazy_copy 將與其他 string 共用記憶體的長字串, 進行實際的 copy（再配置出另一份記憶體）
* 檢查是否串接後字串所需大小, 超過目前所持有的記憶體大小, 如果沒有則直接將資料複製至記憶體。
* memmove 在實作上會先將被複製的資料先複製一份至暫存區, 因此在複製 data 至新位置這種新舊資料可能重疊的情況下, 需使用此函式, 反之, 則可使用 memcpy
* 如果超過現有記憶體大小不足，則創立新字串, 並用 xs_grow 取得適當大小的記憶體，接著將原本的字串複製至新的字串，並釋放原本字串的記憶體。
:::warning
* 在 xs_grow 中因為 13 行將 is_ptr 設為 true, 所以基本上 18 的 else 是不會執行的, 但執行 xs_allocate_data 時, 標記為使用 realloc 也很奇怪，因為其實 ptr 是空的。

> 路見不平，拿 patch 來填！
> :notes: jserv
:::

/* grow up to specified size */
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_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;
}

### 改善程式碼
1. 並未對 realloc, malloc 失敗的情況處理
-> 改呼叫自定義函式 xmalloc, xremalloc, 在回傳 NULL 時輸出錯誤訊息並退出程式

void *xmalloc(size_t size)                              
{
    void *p = malloc(size);
    if (!p) {
        fprintf(stderr, "*** xmalloc: malloc failure (returned NULL), exiting. ***\n");
        exit(1);
    }   
    return p;
}

void *xrealloc(void *ptr ,size_t size)
{
    ptr = realloc(ptr, size);
    if (!ptr) {
        fprintf(stderr, "xrealloc: realloc failure (return NULL), exiting. ***\n");
        exit(1);
    }   
    return ptr;
}

---

## 字串複製實作

參考 [C++ 再探 string 之 eager-copy, COW 和 SSO 方案](https://www.cnblogs.com/cthon/p/9181979.html)
對不同長度的字串做不同程度的拷貝: 長字串做 CoW, 其他做深度拷貝

xs *xs_copy(xs *x, const xs *p) {
  *x = xs_literal_empty();
  if (!xs_is_large_string(p)) {
      x = xs_new(x, xs_data(p));
  } else {
      memcpy(x, p, 16);
      xs_inc_refcnt(x);
  }
  return x;
}     

將 `LARGE_STRING_LEN` 改為 `30` 進行測試
* string: is_ptr=0, is_large_string=0
* medium_str: is_ptr=1, is_large_string=0
* long_str: is_ptr=1, is_large_string=1

(gdb) p xs_data(&string)
$2 = 0x7fffffffdbe0 "foobarbar"
(gdb) p xs_data(&copyed1)
$3 = 0x7fffffffdc80 "foobarbar"

(gdb) p xs_data(&medium_str)
$5 = 0x55555555a6b0 "(((12345678901234)))"
(gdb) p xs_data(&copyed2)
$6 = 0x55555555a730 "(((12345678901234)))"

gdb) p xs_data(&long_str)
$8 = 0x55555555a6e4 "(((this a long string exceed 16.)))"
(gdb) p xs_data(&copyed3)
$9 = 0x55555555a6e4 "(((this a long string exceed 16.)))"

可以發現因為對長字串使用 copy on write, 所以 data 地址相同

## 確認字串處理最佳化

## 整合 string interning
## 找出 Linux kernal 中的 SSO 或 CoW