# 2021q1 Homework3 (quiz3)
contributed by < `YoLinTsai` >
###### tags: `linux2021-hw`
> [題目](https://hackmd.io/@sysprog/linux2021-quiz3)
:::success
延伸問題:
- [x] 解釋上述程式碼運作原理，並提出改進方案;
- [x] 以上述程式碼為基礎，提供字串複製 (應考慮到 CoW) 的函式實作;
- [x] 設計實驗，確認上述字串處理最佳化 (針對空間效率) 帶來的效益，應考慮到 [locality of reference](https://en.wikipedia.org/wiki/Locality_of_reference)，善用 GDB 追蹤和分析，確認字串的確符合預期地配置於 stack 或 heap;
- [ ] 嘗試將 [quiz2](https://hackmd.io/@sysprog/linux2021-quiz2) 提到的 [string interning](https://en.wikipedia.org/wiki/String_interning) 機制整合，提出對空間高度最佳化的字串處理工具函式庫
- [ ] 在 Linux 核心原始程式碼中，找出類似手法的 SSO 或 CoW 案例並解說;
:::
- 先來看最重要的這段 union 結構，我的理解是， union 是共享一塊記憶體，根據 assign 進來的變數改變記憶體內容，利用這樣的特性，即便我們宣告了數種不同的 struct 結構，透過巧妙的記憶體空間安排，我們可以有效的**共用**一些記憶體的內容。
```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, 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;
```
- 以下是記憶體安排的示意圖，特別注意這樣巧妙的安排，可以使不同的方式都能安全的調用 flag ，回顧 fbstring 中的特性，比方說我們把 filler 填滿，最後一個字元剛好是```0x00```， flag 的意義仍然正確。
### xs_new
```cpp=
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;
}
```
- ```xs_new```是 xs 剛宣告時會被呼叫來 allocate 記憶體的 function，如下段所示
```cpp=
#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))
```
- ```NNN``` 為16的理由是當字串長度超過16時， xs 才會用 large_string 的 policy，接著來看```ilog2```：
```cpp
static inline int ilog2(uint32_t n) { return 32 - __builtin_clz(n) - 1; } //LLL
```
- ```ilog2``` 是為了找最接近但不出過 n 的 2^k ， 這裡用```clz```來找 32 bits integer 中從右邊數過來第一個 1 之前有幾個 0，接著```2^(ilog2(len) + 1)```即是 large_string 應該要 allocate 的記憶體空間。
### xs_trim
- 如同 quiz3 中的說明， ```xs_trim``` 的用途是**將字串前後指定的字元刪除**，我們先看判斷和刪除的部份
```cpp=
uint8_t mask[32] = {0};
#define check_bit(byte) (mask[(uint8_t) byte / 8] & 1 << (uint8_t) byte % 8) //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);
```
- 這裡的手法是做兩次 iteration ，一次從頭一次從尾，判斷好 trim 完的邊界後用 ```memmove``` 修剪完成。
- 值得注意的是這裡用來判斷是否為需要刪除字元的手法相當細緻，在 ascii 的編碼下，字元的值可能是 0~255，如此一來我們可以用一個 256 bits 的 mask 去表達哪幾個字元是要被刪除的。
- 我們假設指定刪除字元為 x:
```set_bit(x): mask[ascii(x)] = 1```
```check_bit(x): return mask[ascii(x)] == 1```
而 CCC 和 SSS 的 bit operation 正符合上述的邏輯。
## xs_allocate_data
這段是當 ```xs_new``` 判斷字串長度超過 16 時，便會改成用 medium/large string 的 struct 去儲存，同時也會用 ```xs_allocate_data``` 去 malloc 記憶體，同時我們可以發現，當字串長度超過 ```LARGE_STRING_LEN (256)``` 時，會多申請 4 個 bits 用來紀錄 **reference count**。
```cpp=
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);
}
```
## xs_copy
- 這裡同時會解釋 **CoW** 和 **Reference Count**
```cpp=
void *xs_copy(xs *dst, xs *src)
{
xs_free(dst);
//*dst = xs_literal_empty();
size_t len = xs_size(src);
if(len > 16){
dst->capacity = src->capacity;
dst->size = len;
dst->is_ptr = true;
if(len > LARGE_STRING_LEN) {
dst->ptr = src->ptr;
dst->is_large_string = true;
xs_inc_refcnt(src);
} else {
xs_allocate_data(dst, dst->size, 0);
memcpy(xs_data(dst), xs_data(src), len);
}
}else{
dst->is_ptr = false;
memcpy(dst->data, xs_data(src), len);
dst->space_left = 15 - len;
}
}
```
- 首先 reference count 在的意義是： 有幾個 pointer 指著這塊記憶體，在 sso 當中的意含就是有幾個 Large String 的 ptr 指向同一塊記憶體。
- 那為什麼會發上述情形呢？因為 Copy on Write 的設計導致會有上述狀況， CoW 的使用情境是這樣：當我想 copy 一塊記憶體的時候，如果我接著沒有馬上要用，那我在 copy 的當下就去 allocate 似乎是個有點浪費空間和時間的作法
- 取而代之的，我們可以偷偷的把 pointer 指向被複製的 address ，一旦發現我真的要改他的時候，而且有複數個 pointer 指向該記憶體，再去申請一塊新的記憶體。
- 如上面那段 code ，我們先判斷是否為長字串，接著判斷是否為 large_string ，如果為真就用 CoW ，並調整 reference count (refcnt)。
## gdb檢驗
```c=
xs string = *xs_tmp(longString);
xs copyString;
xs_copy(©String, &string);
xs prefix = *xs_tmp("((("), suffix = *xs_tmp(")))");
xs_concat(©String, &prefix, &suffix);
```
- vmmap
```
0x000055555555a000 0x000055555557b000 rw-p [heap]
0x00007ffffffde000 0x00007ffffffff000 rw-p [stack]
```
- print string
```json=
{
ptr = 0x55555555a2a0 "\002",
size = 0x10e,
capacity = 0x9
}
```
- print copyString
```json=
{
ptr = 0x55555555a2a0 "\002",
size = 0x10e,
capacity = 0x9
}
```
- print copyString (after trim)
```json=
{
ptr = 0x55555555a8c0 "\001",
size = 0x114,
capacity = 0x9
}
```
- 這邊檢查了 ptr 有正確指向 heap 位置，同時檢測 CoW 前後是否有確實 malloc 新的記憶體並將 ptr 指向新的位置，此外一併檢查了 refcnt 的正確性。
## 設計實驗
- 我們實做的 xs_cpy w CoW:
```
Performance counter stats for './bench 10000 0':
24,279 cache-misses # 44.099 % of all cache refs
55,056 cache-references
0.002458456 seconds time elapsed
0.002419000 seconds user
0.000000000 seconds sys
```
- 對比 strncpy 每次 copy 都去 malloc 一塊
```
Performance counter stats for './bench 10000 1':
65,038 cache-misses # 55.951 % of all cache refs
116,242 cache-references
0.001360883 seconds time elapsed
0.001375000 seconds user
0.000000000 seconds sys
```
- 可以發現 CoW 的手法會讓 cache-misses 的數量下降許多，其實這也符合 CoW 設計的手法，同時我們也可以發現 CoW 所花的時間是比較長的。**(待確認原因)**
- massif
Sign in with Wallet
Connect another wallet