# 2021q1 Homework3 (quiz3)
contributed by < `XDEv11` >
> [GitHub](https://github.com/XDEv11/Linux_Kernel_Internals/tree/main/homework3/quiz3)
> [第 3 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz3)
### 解釋程式碼並改進
* `(size_t) 1 << x->capacity` 的部分改用 `1UL` 進行位移，確保結果正確。
* `set_bit` 與 `check_bit` 中，用 bitwise 操作取代原本的運算。
* `xs_literal_empty()` 初始化更多成員。
* `xs_allocate_data()` 不需要 `reallocate`，應由 `is_ptr` 來決定。
* `is_ptr` 與 `capacity` 應由記憶體管理相關函數進行維護。
* 新增其他的輔助函數，使得程式架構更簡潔，易於維護。(e.g. `set_size()`)
```cpp
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#define MAX_STR_LEN_BITS (54)
#define MAX_STR_LEN ((1UL << MAX_STR_LEN_BITS) - 1)
#define STACK_SIZE 15
#define LARGE_STRING_LEN 256
```
xs 的聯合 (union) 如下，第一個結構中的 `filler` 並沒有實際作用，只是為了資料對齊，把位置留給 `data` 存放字串；而第二個結構少了四個位元，避免複寫到第一個結構中的標記。
這邊很巧妙的設計是，如果剛好 15 個位元組的字串放在 stack 上，`space_left` 剛好為 `0`，`is_ptr`、`is_large_string` 也為 `0`，`flag2`、`flag3` 目前並無用途，未來擴充用到的話，在這情況下也應該為 `0`，整個 `data` 為一個 null-terminated C-style string。
`capacity` 用了 6 位元表示，最大的長度可到達 $2^{2^6} - 1$，這邊需要特別注意的是，這個數值需要大於 $2^{MAX\_STR\_LEN\_BITS} - 1$，而 `MAX_STR_LEN_BITS` 加上 `capacity` 所佔的位元，在這邊不能大於 $8 * 8 - 4 = 60$。
```
|data____________________________________________________________|
|______________________________________________________|left|flag|
|size________________________________________________|capa..|
```
:::info
由於這部分不好利用 graphviz 進行繪圖，這裡參考了 [RZHuangJeff](https://hackmd.io/@Forward1105/2021q1Hw_quiz3#Structure-Description) 的繪圖方式。
:::
```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[STACK_SIZE + 1];
struct {
uint8_t filler[STACK_SIZE],
/* 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;
```
```cpp
static inline bool xs_is_ptr(const xs *x) { return x->is_ptr; }
```
```cpp
static inline bool xs_is_large_string(const xs *x)
{
return x->is_large_string;
}
```
```cpp
static inline size_t xs_size(const xs *x)
{
return xs_is_ptr(x) ? x->size : 15UL - x->space_left;
}
```
```cpp
static inline void xs_set_size(xs *x, size_t s)
{
if (!xs_is_ptr(x))
x->space_left = STACK_SIZE - s;
else
x->size = s;
}
```
在 `xs_allocate()` 中可看到，
`The extra 4 bytes are used to store the reference count`，因此如果是長字串的話，真正字串會從 `x->ptr+4` 開始。
```cpp
static inline char *xs_data(const xs *x)
{
if (!xs_is_ptr(x))
return (char *) x->data;
else if (xs_is_large_string(x))
return (char *) (x->ptr + 4);
else
return (char *) x->ptr;
}
```
```cpp
static inline size_t xs_capacity(const xs *x)
{
return xs_is_ptr(x) ? ((size_t) 1UL << x->capacity) - 1 : 15;
}
```
:::warning
這邊 `*((int *) ((size_t) x->ptr))` 應當不需要先轉為 `size_t`。
:::
```cpp
static inline void xs_set_refcnt(const xs *x, int val)
{
*((int *) x->ptr) = val;
}
```
```cpp
static inline void xs_inc_refcnt(const xs *x)
{
if (xs_is_large_string(x))
++(*(int *) x->ptr);
}
```
```cpp
static inline int xs_dec_refcnt(const xs *x)
{
if (!xs_is_large_string(x))
return 0;
return --(*(int *) x->ptr);
}
```
```cpp
static inline int xs_get_refcnt(const xs *x)
{
if (!xs_is_large_string(x))
return 0;
return *(int *) x->ptr;
}
```
`xs_literal_empty()` 應初始化更多成員，避免未預期的錯誤出現。
語法可參考 [designator](https://en.cppreference.com/w/c/language/initialization)
```cpp
#define xs_literal_empty() \
(xs) { .data[0] = '\0', .space_left = 15, .is_ptr = 0, .is_large_string = 0 }
```
```cpp
static inline xs *xs_newempty(xs *x)
{
*x = xs_literal_empty();
return x;
}
```
```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);
}
```
`32 - __builtin_clz(n)` 代表這個數字在二進位有幾位數。
```cpp
/* lowerbound (floor log2) */
static inline int ilog2(uint32_t n) { return 32 - __builtin_clz(n) - 1; }
```
`xs_allocate()` 配置記憶體，足夠存放長度為 len 的字串，設定 `is_ptr` 與 `capacity`，如果一開始有記憶體，會先進行釋放。
```cpp
/* Allocate enough memory to store string of size len.
* It will free the previously allocated memory if there is.
*/
static void xs_allocate(xs *x, size_t len)
{
x->capacity = ilog2(len) + 1;
xs_free(x);
if (len <= STACK_SIZE)
x->is_ptr = 0;
else if (len < LARGE_STRING_LEN) {
/* Medium string */
x->ptr = malloc((size_t) 1UL << x->capacity);
x->is_ptr = 1;
} else {
/* Large string */
x->is_large_string = 1;
/* The extra 4 bytes are used to store the reference count */
x->ptr = malloc((size_t)(1UL << x->capacity) + 4);
x->is_ptr = 1;
xs_set_refcnt(x, 1);
}
}
```
先處理字串空間，再透過 `memcpy` 進行字串複製。
```cpp
xs *xs_new(xs *x, const void *p)
{
size_t len = strlen(p);
xs_allocate(x, len);
memcpy(xs_data(x), p, len + 1);
xs_set_size(x, len);
return x;
}
```
這邊用到 comma operator，整個表達式的結果是後者。
```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))
```
先把字串複製進 buf 或是直接把指標取出，增大容量後，再把資料儲存回去。(記得釋放原本的記憶體)
```cpp
/* grow up to specified size */
xs *xs_grow(xs *x, size_t len)
{
char buf[16];
char *backup = (char *) &buf, *f = NULL;
if (len <= xs_capacity(x))
return x;
/* Backup first */
if (xs_is_ptr(x)) {
backup = xs_data(x);
f = x->ptr;
x->is_ptr = 0;
} else {
memcpy(buf, x->data, 16);
}
xs_allocate(x, len);
memcpy(xs_data(x), backup, xs_size(x));
if (f)
free(f);
return x;
}
```
`xs_cow_lazy_copy()` 在有超過一個 `xs` 都參考這個字串的時候，會複製一份放入 `x`。
```cpp
static bool xs_cow_lazy_copy(xs *x)
{
if (xs_get_refcnt(x) <= 1)
return false;
/* Lazy copy */
char *data = xs_data(x);
xs_dec_refcnt(x);
x->is_ptr = 0;
xs_allocate(x, xs_size(x));
memcpy(xs_data(x), data, x->size + 1);
return true;
}
```
```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);
xs_cow_lazy_copy(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);
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;
}
```
這邊 `mask` 為一個長度 256 的 bit array，對應每個 ASCII 字元，先透過 `set_bit()` 把 `trim_set` 中出現過的字元設為 `1`，需要確認時再透過 `check_bit()` 確認。
因為實際上是 32 個 8 位元的 `uint8_t`，先透過 `i / 8` 得到對應的那個數字，再透過 `i % 8` 得到對應的位元。
`i / 8` => `i >> 3`
`i % 8` => `i & 7`
```cpp
xs *xs_trim(xs *x, const char *trimset)
{
if (!trimset[0])
return x;
xs_cow_lazy_copy(x);
char *dataptr = xs_data(x), *orig = dataptr;
/* similar to strspn/strpbrk but it operates on binary data */
uint8_t mask[32] = {0};
#define check_bit(i) (mask[(uint8_t) i >> 3] & 1 << ((uint8_t) i & 7))
#define set_bit(i) (mask[(uint8_t) i >> 3] |= 1 << ((uint8_t) i & 7))
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;
xs_set_size(x, slen);
return x;
#undef check_bit
#undef set_bit
}
```
```cpp
int main(int argc, char *argv[])
{
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));
return 0;
}
```
### 字串複製 (應考慮到 CoW) 的函式實作
先把整個 `xs` 的內容進行複製，如果是長字串，就增加 reference count，否則如果是在 heap 上，就複製出新的一份。
```cpp
static inline xs *xs_cpy(xs *dest, xs *src)
{
xs_free(dest);
*dest = *src;
size_t len = xs_size(src);
if (len >= LARGE_STRING_LEN)
xs_inc_refcnt(src);
else if (len > STACK_SIZE) {
dest->is_ptr = 0;
xs_allocate(dest, len);
memcpy(xs_data(dest), xs_data(src), len + 1);
}
return dest;
}
```
###### tags: `linux2021`
Sign in with Wallet
Connect another wallet