2021q1 Homework3 (quiz3)

# 2021q1 Homework3 (quiz3) contributed by < `yellow-hank` > ###### tags: `LinuxKernel` ## 測驗`1` :::danger 先拆解程式碼並分析，避免完整列表 :notes: jserv ::: ### 解釋程式碼 ### 解決議題當有許多長字串，且字串內容皆相同，如此一來記憶體開銷會增長，此程式透過參照的方式，進行字串內容的分享，只有在需要修改時，額外產生副本進行修改。 #### 資料結構 ```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; ``` 使用 `union` 創造共享的空間，大小為 16 * 1位元組 = 16 位元組的空間，其中分為兩種方式，第一種是以堆疊的資料結構儲存短字串 (長度為 15 位元組以下)，第二種是透過 `malloc` 函式配置一塊空間，利用一個字元指標去紀錄這塊配置的空間。第一種方式，使用堆疊，是用長度 15 以下的字串 - filler[15] 是用來儲存字串的地方 - space_left 用來記錄還剩下多少空間可以使用，使用此方式是因為如果字串長度剛好是 15 時，最後一個字元可以同時紀錄剩餘空間為 0 ，而且可以當作字串結尾字元 `\0` (二進位表示為 0000 0000)，同時滿足兩種需求，因此 space_left 紀錄剩餘空間 - is_ptr 紀錄這比資料是使用堆疊儲存，還是透過 `malloc` 的空間來儲存 - is_large_string 紀錄這個字串的長度是否超過 256 ，需要透過另一種方式儲存，再額外新增 4 個位元組紀錄有多少指標指向此長字串。第二種方式，使用 `malloc`配置空間，適用長度 $15 < length \leq 2^{54} - 1$ 的字串 - ptr 紀錄由 `malloc` 配置的空間 - size 紀錄字串的長度 - capacity 紀錄配置多少空間，因為最大為 size 的 54 位元，所以只需要 6 個位元就能涵蓋 54 。 - 可以發現到最後 4 個位元沒有定義，為了保留前面定義 is_ptr, is_large_string, flag2, flag3 這些重要的資訊，這些可以共用，所以不在這邊定義 #### 函式 ```cpp static inline bool xs_is_ptr(const xs *x) { return x->is_ptr; } ``` `xs_is_ptr` 回傳資料結構中用來判斷是否為指標，可以用來判斷字串是儲存在堆疊中 ( 值為 0 )，還是儲存在由 `malloc` 配置的空間 ( 值為 1 )。 ```cpp static inline bool xs_is_large_string(const xs *x) { return x->is_large_string; } ``` `xs_is_large_string` 回傳資料結構中用來判斷此字串是否為長字串 ( 長度大於 256 ) ， 1 為長字串， 0 為中短字串。 ```cpp static inline size_t xs_size(const xs *x) { return xs_is_ptr(x) ? x->size : 15 - x->space_left; } ``` `xs_size` 回傳字串長度，這邊分為兩種方式，若是存放在堆疊中，因為堆疊設計為紀錄剩餘空間，所以是用最大長度 15 減去 space_left 。存放在 `malloc` 配置的空間，直接回傳資料結構 size 的部分。 ```cpp 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; } ``` `xs_data` 回傳字串資料，存放在堆疊中直接回傳 data 即可獲得字串，存放在由 `malloc` 配置的空間分為兩種方式，長字串因為前面 4 個位元組是用來紀錄有多少指標指向此長字串，所以需要移動指標的位址 4 個位元組才能獲得字串的位址。另一種中等長度字串，因為沒有設計指標指向計數器，因此直接回傳指標紀錄位址的內容。 ```cpp static inline size_t xs_capacity(const xs *x) { return xs_is_ptr(x) ? ((size_t) 1 << x->capacity) - 1 : 15; } ``` `xs_capacity` 回傳有多少空間存放字串，堆疊最大空間為 15 ，`malloc` 配置的空間為 2^capacity^ - 1。 ```cpp static inline void xs_set_refcnt(const xs *x, int val) { *((int *) ((size_t) x->ptr)) = val; } ``` `xs_set_refcnt` 設定長字串的有多指標指向它的計數器，將計數器設為 val 值。 ```cpp static inline void xs_inc_refcnt(const xs *x) { if (xs_is_large_string(x)) ++(*(int *) ((size_t) x->ptr)); } ``` `xs_inc_refcnt` 如果是長字串，將用來紀錄有多少指標指向的計數器的值加一。 ```cpp static inline int xs_dec_refcnt(const xs *x) { if (!xs_is_large_string(x)) return 0; return --(*(int *) ((size_t) x->ptr)); } ``` `xs_dec_refcnt` 如果是長字串，將用來紀錄有多少指標指向的計數器的值減一，並將計數器的數值回傳。中等長度的字串因為沒有計數器，所以回傳 0。 ```cpp static inline int xs_get_refcnt(const xs *x) { if (!xs_is_large_string(x)) return 0; return *(int *) ((size_t) x->ptr); } ``` `xs_get_refcnt` 回傳長字串的指標指向計數器。中等長度的字串因為沒有計數器，所以回傳 0。 ```cpp #define xs_literal_empty() \ (xs) { .space_left = 15 } ``` 使用巨集產生一個 xs 的資料結構，並初始化堆疊中的剩餘空間為 15。這種方式為 C99 的 compound literals，下面有舉例 - C99 [6.5.2.5.9] **Compound literals** >EXAMPLE 1 The file scope definition int *p = (int []){2, 4}; initializes p to point to the first element of an array of two ints, the first having the value two and the second, four. The expressions in this compound literal are required to be constant. The unnamed object has static storage duration. ```cpp /* lowerbound (floor log2) */ static inline int ilog2(uint32_t n) { return 32 - __builtin_clz(n) - 1; } ``` `ilog2` 回傳數字取 log 後，整數部分的值 ( $2^{k} \leq n < 2^{k+1}$ k值 ) ，這裡不對 n 取 log ，利用 `__builtin_clz(n)` 獲得從最高位元數有幾個 0 直到遇到 1 則停止。例如：在 8 位元中，數字 3 二進位表示為 0000 0011 ，使用 `__builtin_clz(3)` 得到 6 。這裡 n 是 32 位元，32 - `__builtin_clz(3)` 可以拿到最高位元的 1 在第幾個，但是因為是從零開始數，所以還要再減去一獲得正確的值。 ```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_allocate_data` 配置空間給中長等長度字串 - x 為原始字串的資料結構 - len 字串長度 - reallocate 1 為在現有的空間進行擴增，0 為重新配置空間先檢查字串為長字串還是中等字串，中等字串依據 capacity 來配置空間。長字串在配置空間時，依據 capacity 配置空間大小，需要額外配置 4 bytes 當作計數器紀錄多少指標指向它。 ```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; 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 資料結構用來存放由 p 指向的字串 len 為字串長度加一是為了保留最後一個字元給 NULL 字元作為字串終結字元。對於中等長度字串，對於存放空間除了能容納字串還多保留額外空間，用於未來擴增字串使用。 ```cpp /* 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)) ``` `xs_tmp` 這裡的 `_Static_assert` 會在編譯時先檢查字串，對於大小大過 MAX_STR_LEN ，會在編譯時期顯示錯誤，不進行後續的編譯 ```cpp /* 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_grow` 將 xs 存放的空間擴充到 len bytes 的大小資料原本存放在 stack 中，會將其複製到暫存空間，透過 `malloc` 取得在 heap 的空間，將其存放到 heap 上 :::info 第 13 行的 x->is_ptr = true; 應該要放在 return 之上，不然接下來的判斷都會將 xs 判斷為原本是存放在配置空間上，如果原本是存放在堆疊中，那 19 20 行永遠不會被執行到，修正程式碼如下: ```cpp 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->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); } x->is_ptr = true; return x; ``` ::: ```cpp static inline xs *xs_newempty(xs *x) { *x = xs_literal_empty(); return x; } ``` `xs_newempty` 產生一個空的 xs 的資料結構，並且回傳它 ```cpp 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_free` 釋放 xs 的字串存放方式是配置的空間，長字串須額外檢查是否還有指標指向它，才能將空間釋放。 ```cpp 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; } ``` `xs_cow_lazy_copy` 當要變動長字串時，額外製作一個副本，確保 data 紀錄的字串可以進行變更 Copy on write 是在需要變動字串內容時，才進行製作一個副本來變動，其餘的時候是透過參照的方式來共享字串內容。 ```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); 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_concat` 將 prefix 串接在 string 的前面，將 suffix 串接在 string 的後面對於長字串，需要進行 copy on write，來確保更改其內容不會影響到其餘共享的字串。空間不足時，透過 `xs_grow` 進行擴增空間。 ```cpp= 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 } ``` :::info ```cpp #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) ``` 在處理 hash function 使用除法來計算，此處應該使用 shift operator ，還有取餘數的部分可以替換成 bitwise and 來實作。修改程式碼如下： ```cpp #define check_bit(byte) (mask[(uint8_t) byte >> 3] & 1 << ((uint8_t) byte & 0x03 )) #define set_bit(byte) (mask[(uint8_t) byte >> 3] |= 1 << ((uint8_t) byte & 0x03)) ``` ::: `xs_trim` 減去在 xs 資料結構的頭尾中，有在 trimset 的字元 #### mask 的運作原理用 hash function 來尋找需要裁減的字元，ascii code 的總數為 256 個，只需要紀錄是否有此值，所以需要 256 個位元紀錄即可，透過 hash function ( 這裡為 ascii code 值 / 8 )，可以把 256 個位元分成 32 個 8 位元的數。 ```graphviz digraph { node [shape = record] struct1[label="{<f0> 0|<f1>1|<f2>2|<f3>...|<f4>29|<f5>30|<f6>31}"]; struct2[label="{{<f0>0|0|..|0}}"]; struct3[label="{{<f0>0|0|..|0}}"]; struct4[label="{{<f0>0|0|..|0}}"]; struct5[label="{{<f0>0|0|..|0}}"]; struct6[label="{{<f0>0|0|..|0}}"]; struct7[label="{{<f0>0|0|..|0}}"]; struct8[label="{{<f0>0|0|..|0}}"]; struct2:f0 -> struct1:f0; struct3:f0 -> struct1:f1; struct4:f0 -> struct1:f2; struct5:f0 -> struct1:f3; struct6:f0 -> struct1:f4; struct7:f0 -> struct1:f5; struct8:f0 -> struct1:f6; } ``` 加入空白字元 (二進位 0001 0000)，計算此字元 hash 值為 4，將其放入第四個 8 位元數，並將第一個位元設為 1， ```graphviz digraph { node [shape = record] struct1[label="{<f0> 4}"]; struct2[label="{{<f0>0|0|..|1}}"]; struct2:f0 -> struct1:f0; } ``` 之後尋找空白字元是否為需要裁減的字元，只需要算他的 hash 值，就能到 hash table 查詢。優點是只需要查詢一次就能知道結果，hash table 對於沒有排序的資料可以快速尋找到值，最差的情況是O(字串長度)。如果是透過迴圈去確認裁減字元，最差的情況會是 O(需要裁減字元總數 * 字串長度) ### 問題回答 - hash function 在程式中的用途 - 在 `xs_trim` 中的用來存放需要裁減的字元是運用 hash function 來實作 - hash function 的優點是對於沒有排序的資料，可以快速尋找所需要的資料 - string interning 存放在哪邊的時機 - 字串長度小於等於 15 存放在 stack 中，優點是存取快速 - 字串長度大於 15 存放在 heap 中，優點是空間大，缺點是存取時間較長 - 字串長度大於 256 ，額外新增 4 個位元組用來記錄有多少指標指向 - 實作的優點或缺點 - 優點 - 當有許多相同內容的長字串，透過參照的方式可以節省記憶體開銷 - 對於短字串存放在 stack ，存取速度比存放在 heap 中的字串快 - 缺點 - 當長字串的內容無一相同，記憶體開銷沒有減少，反而增加，因為多了許多計數器 - 對於有相同內容的短字串，也會造成記憶體的浪費

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.