# 2020q2 Homework2 (quiz2)
contributed by <_`ire33164`_>
###### tags: `Linux Kernel`
==[第二週測驗題](https://hackmd.io/@sysprog/linux2020-quiz2)==
==[作業說明](https://hackmd.io/@sysprog/BJXNYx5NL)==
---
## 測驗 `1` & 解釋程式碼
### Union 設計
```cpp
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` 需要最大空間的成員所決定
因此比較三個成員 :
```c
char data[16];
```
* `char data[16]` : 需要 16 個 `sizeof(char)` 的空間 -> ==16 bytes==
```c
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==
```c
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^{capacity}$== 下去分配，也就是會分配到 `1 << capacity` 大小的空間
* 預留最後 4 bit 存放 `is_ptr`, `flag1`, `flag2`, `flag3`
---
### Function `xs *xs_new` 與 AAA
```c
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`的物件
```c
*x = xs_literal_empty();
```
* 初始化 `x` 的 `space_left` 為 15
```c
size_t len = strlen(p) + 1;
```
* 取得字串長度並 + 1
> 因為 `strlen` 僅回傳字元 `\0` 前的個數，因此長度必須再加上 1，給予 `\0` 空間
```c
if (len > AAA) {
```
* 根據字串長度選擇要配置 stack 或 heap 的空間
* 因 stack 上可存放的字串長度的最大值為 15，因此 `len` 若大於 16 就代表需配置到 heap 的空間
> len = `strlen(p)` + 1
:::success
AAA 為 16
:::
```c
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 指向的記憶體中
```c
memcpy(x->data, p, len);
x->space_left = 15 - (len - 1);
```
* 需要配置到 stack 空間的情況
---
### Function `xs *xs_grow`
```c
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
```c
if (len <= xs_capacity(x))
return x;
```
* 確定目前配置的空間是否滿足欲增長到的 size
```c
if (xs_is_ptr(x))
```
* 根據 `x` 目前配置的位置做不同的處理
```c
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** 可以在不修改到內容的情況下，重新設定需要的空間大小
```cpp
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`
```cpp
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`
```cpp
if (size + pres + sufs <= capacity) {
```
* 檢查目前 `string` 配置的空間是否足夠提供串接後所需的空間
```cpp
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.
:::info
兩者的差別在於 **memmove** 會先將欲複製的空間存到 temporary array
再將 temporary array 的值複製到 dest 中
但 **memcpy** 是直接複製過去
**memcpy** 的方式在 dest 和 src 位址有交疊 (overlap) 時會產生錯誤
:::
```cpp
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
```cpp
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` 的字元
```c
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
:::success
BBB 為 32
:::
```c
#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` 的成員，需要被裁剪掉
:::info
**為何是 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`
:::
```c
#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`
:::success
CCC 為 &
:::
```c
for (i = 0; i < trimlen; i++)
set_bit(trimset[i]);
```
* 將 `trimset` 的成員紀錄到 `mask` 中
```c
for (i = 0; i < slen; i++)
if (!check_bit(dataptr[i]))
break;
```
* 利用 `check_it` 從頭逐個檢查字串中的字元是否為 `trimset` 的成員
* 將第一個非 `trimset` 成員的 offset 紀錄到 `i` 中
* `i` 代表字串中第幾個字元開始不為 `trimset` 的成員
```c
for (; slen > 0; slen--)
if (!check_bit(dataptr[slen - 1]))
break;
```
* 利用 `check_it` 從尾巴開始逐個檢查字串中的字元是否為 `trimset` 的成員
* 慢慢減去 `slen` 的值，直到碰到字串中最後一個不為 `trimset` 的成員的字元
* `slen` 代表字串中從頭開始數到最後一個不為 `trimset` 的成員的字元的長度
```c
dataptr += i;
slen -= i;
```
* 將 ptr 移到字串中第一個開始不為 `trimset` 的成員的位置
* slen 扣掉前面為 `trimset` 成員的長度
```c
memmove(orig, dataptr, slen);
```
* 將去除頭尾 `trimset` 成員的字串複製回 `orig` 中 => 成功去頭去尾
---
## 延伸問題
### function `xs xs *cpy` (考慮 CoW)
> 參考 [folly::fbstring](https://github.com/facebook/folly/blob/master/folly/FBString.h) 中記憶體配置的技巧設計實現 **reference count**
#### Reference count
```c
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 並對其操作
---
```cpp
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
---
```cpp
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
---
```cpp
static inline size_t rc_count (char *x)
{
return rc_fromData(x)->RefCount_;
}
```
* 取得 RefCount
---
```c
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` + 字串需要的空間
---
```c
static inline void rc_increment (char *x)
{
rc_fromData(x)->RefCount_++;
}
```
* RefCount 加 1
---
```c
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 時可以直接釋放掉原本的記憶體
:::success
處理完麻煩的 Reference count 後
接下來就剩應用了
* [x] xs_cpy
* [x] xs_new
* [x] xs_concat
* [x] xs_trim
* [x] xs_grow
:::
#### xs_cpy
```c
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
```c
...
x->ptr = rc_create(p, x->capacity);
...
```
* 若 new `xs` 時傳入的字串長度超過 16 ，則 create Ref_Count 並將 ptr 指向 Ref_Count 中的 `data_`
:::success
**測試 xs_new 和 xs_cpy**
```c
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
```c
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
```c
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
```c
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` 改成空字串
:::success
**測試 xs_concat & xs_grow & xs_free**
```c
#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;
}
```
預期輸出 :
```c
[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
```
實際輸出 :
:::
:::danger
**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
```cpp
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`
:::success
**測試 xs_trim & xs_cpy**
```c
#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
```
實際輸出 :
:::
:::warning
TODO :
考慮到 race condition 的問題
要將 Ref_Count 中的 RefCount 改成利用 atomic 實做
:::
---
### [`strtok`](http://man7.org/linux/man-pages/man3/strtok.3.html) 功能實作
* `char *strtok(char *str, const char *delim)`
* `str` : 欲被分割的字串，若為 `NULL` 則延續前一次的 `str`
* `delim` : 用來分割的字串
* `return` : `str` 中第一個被分割下來的字串
```c
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` 指向取下字串的下一個字元
:::info
這樣的方式在呼叫 **xs_strtok()** 回傳的字串在使用完後是需要利用 **free()** 來釋放記憶體的
但其實有另外的方式可以不用特別 **free()** 那就是要直接去改動原 `xs` 中的字串
> 直接將字串用 '\0' 切開
但這會牽涉到 **CoW** 的使用，根據我的寫法也是須另外 **malloc()** 出空間
因此想說既然都要 **malloc()** 那就先實做不牽涉到 **CoW** 也就是維持原字串值
而需要 **free()** 的版本
:::
:::success
**測試 xs_strtok**
```cpp
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 :
```shell
$ valgrind -q --leak-check=full ./xs
```
結果 : 沒問題!!
:::
---
### 字串處理最佳化 (針對空間效率) 帶來的效益
:::info
觀測有使用 ==copy-on-write== 與==沒使用 copy-on-write== 兩種情況的記憶體使用情況與效能差距
:::
實做一個不使用 copy-on-write，直接複製字串的 function 作為實驗的對照組
```cpp
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;
}
```
:::info
分別使用 **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
```
:::success
根據這次使用 **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% )
```
:::success
根據這次 perf stat 的結果可以明顯發現使用 **Copy-on-Write** 後
* `cache-miss` : 從 `1062942` 降到 `7993`
* `cache-reference` : 從 `1,212,514` 降到 `51,188`
* 執行時間降為原本的三分之一
:::
---
### 在 Linux 核心原始程式碼中，找出類似手法的 SSO 或 CoW 案例並解說
[linux/rmap.h](https://github.com/torvalds/linux/blob/6f0d349d922ba44e4348a17a78ea51b7135965b1/include/linux/rmap.h)
Sign in with Wallet
Connect another wallet