# 2020q1 Homework2 (quiz2)
contributed by < [Hsuhaoxiang](https://github.com/Hsuhaoxiang/quiz2) >
> 重新回答[第 2 周測驗題](https://hackmd.io/@sysprog/linux2020-quiz2)
## 了解 xs 的設計
```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` 中每個成員皆小於等於 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
:::danger
程式列表應該適度分段，從功能探討起，連帶提及答題思維
:notes: jserv
:::
>好的
### xs_new 與 AAA = ?
```cpp
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
```c
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)
```cpp
#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` 一開始只能初始為短字串再慢慢合併上去。
:::warning
16 這個數字可變更，但取決於結構體的規劃，請對照看 (https://github.com/facebook/folly/blob/master/folly/FBString.h)，並參照 [Cache 原理和實際影響](https://hackmd.io/@sysprog/HkW3Dr1Rb)，考慮到 cache line 空間。
:notes: jserv
:::
### xs_grow
```cpp
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({len})+1}$ 的記憶體空間
### 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;
}
```
* 將 `prefix` , `suffix` 字串到 string 的前後， `capacity` 不夠就使用 `xs_grow()`
---
## 延伸問題
### 以上述程式碼為基礎，提供字串複製 (應考慮到 CoW) 和類似 [strtok](http://man7.org/linux/man-pages/man3/strtok.3.html) 功能的函式實作
> 參考 [folly::fbstring](https://github.com/facebook/folly/blob/master/folly/FBString.h) 中使用 CoW 的技巧
----
### COW
#### struct RefCounted
* 先定義一種結構體 `RefCounted` 有兩個成員
* `refCount` 為多少 `xs` 長字串正在參考原本的字串，只有用 `cow_copy()` 時數字才會增加
* `data_` 為字串開頭的記憶體位置，也是存放長字串的地方宣告成長度為 1 的陣列讓 `data_`表示為記憶體位置而不是資料，我有嘗試過把 `data_[1]` 換成 `char *data` 但最後會有問題，還沒找出原因，不過用這種宣告方式是更省記憶體的，比起我省下了一個指標的空間。
```cpp
typedef struct refcnt {
size_t cnt;
char data_[1];
} refcnt_t;
```
:::warning
`refcounted` 這名稱可縮減為 `refcnt`，對應 typedef 後為 `refcnt_t`。上方的 `refCount_` 可改為 `val` 或 `cnt`，因為實質操作存取次數多，簡潔至上
:notes: jserv
:::
>已改
#### getDataOffset
* 求出 `struct` 中 `data_` 位元組偏移值
```cpp
static size_t getDataOffset() {
return offsetof(refcnt_t, data_);
}
```
#### fromData
* 回傳給定字串的 `refcnt_t` 指標
```cpp
static refcnt_t* fromData(char* p) {
return (refcnt_t*)((void*)(size_t*)((void*) p - getDataOffset()));
}
```
#### refs
* 回傳給定字串的 `cnt` 也就是他被參考的次數
```cpp
static size_t refs(char* p) {
return fromData(p)->cnt;
}
```
#### incrementRefs
* 將 `cnt` 加 1
```cpp
static void incrementRefs(char* p) {
fromData(p)->cnt+=1;
}
```
#### decrementRefs
* 將 `cnt` 減 1 ， 如果沒有其他指標參考這個 `struct` 則釋放記憶體
```cpp
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_` 這個存放字串的記憶體為
```cpp
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
```cpp
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
#### [測試](https://github.com/Hsuhaoxiang/quiz2/blob/master/cow_xs.c)
```cpp
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(©string, &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
```cpp
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
}
```
:::warning
直接對字串進行改動還沒考慮 cow
:::
#### 測試
```cpp
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 案例並解說
Sign in with Wallet
Connect another wallet