# 2021q1 Homework3 (quiz3)
contribute by < `jameshuang890902` >
## 延伸問題:
1. 解釋上述程式碼運作原理，並提出改進方案;
2. 以上述程式碼為基礎，提供字串複製 (應考慮到 CoW) 的函式實作;
3. 設計實驗，確認上述字串處理最佳化 (針對空間效率) 帶來的效益，應考慮到 locality of reference，善用 GDB 追蹤和分析，確認字串的確符合預期地配置於 stack 或 heap;
4. 嘗試將 quiz2 提到的 string interning 機制整合，提出對空間高度最佳化的字串處理工具函式庫
5. 在 Linux 核心原始程式碼中，找出類似手法的 SSO 或 CoW 案例並解說;
## 重新回答第三週測驗題目
### Q1: OFF = ?
```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 + OFF);
return (char *) x->ptr;
}
```
- **想法**
下面是擷取第三週測驗說明中的案例應用：
```c=
xs string = *xs_tmp(" foobarbar \n\n");
xs_trim(&string, "\n ");
printf("[%s] : %2zu\n", xs_data(&string), xs_size(&string));
```
其輸出為：
```
[foobarbar] : 9
```
可以得知 `xs_tmp` 的用途為將一個 `xs` 型態的字串轉為 string 的型態輸出。
再回來看 `xs_tmp` 的實作：
```c=
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 + OFF);
return (char *) x->ptr;
}
```
這個實作對應到以下三種不同情況：
1. `if (!xs_is_ptr(x))` ：在 `xs_is_ptr(x) == false` 時執行，表示此時 x 不是以 heap 方式儲存，即是存在 stack 中。 以`return (char *) x->data;` 獲取字串。
2. `if (xs_is_large_string(x))`：在 `xs_is_large_string(x) == true` 時執行，表示此時 x 是以 heap 方式儲存。 以`return (char *) (x->ptr + OFF);` 獲取字串。
:::info
此處 `return (char *) (x->ptr + OFF);` 中的 `OFF = 4`。其原因理解中。
> 可用 GDB 觀察，避免「舉燭」
> :notes: jserv
:::
3. 非上面兩種情況為： `xs_is_ptr(x) == false && xs_is_large_string(x) == false` ，以`return (char *) x->data;` 獲取字串。
:::warning
:question: `xs_is_ptr(x) == false && xs_is_large_string(x) == false` 代表什麼情況？
:::
### Q2: LLL = ?
```cpp
/* lowerbound (floor log2) */
static inline int ilog2(uint32_t n) { return LLL; }
```
### Q3: NNN = ?
```cpp
xs *xs_new(xs *x, const void *p)
{
*x = xs_literal_empty();
size_t len = strlen(p) + 1;
if (len > 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;
}
```
### Q4: CCC = ? Q5: SSS = ?
```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) (CCC)
#define set_bit(byte) (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);
/* 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
}
```
## 程式碼運作原理
### 資料結構
```c=
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 中的 `char data[16];` 定義 `xs` 的資料長度為 16 個位元組。
```graphviz
digraph {
node [fontname="Arial"]; node_A[shape=record,label="data[0]|data[1]|data[2]|data[3]|data[4]|data[5]|data[6]|data[7]|data[8]|data[9]|data[10]|data[11]|data[12]|data[13]|data[14]|data[15]"];
}
```
:::warning
修改視覺呈現方式，避免擠在同一行
:notes: jserv
:::
- 當字串長度小於或等於 15 個位元組，則用下面的方式存放在 stack，同時也是下面結構中的 `filler` 。最後一個位元組以 bit-field 的技巧切分給 `space_left`, `is_ptr`, `flag1`, `flag 2` 與 `flag3`。 （順序為上到下）。
- filler: 15 個位元組，用來儲存長度小於或等於 15 個位元組的字串。
- space_left: 4 個位元，用來記錄沒被字串佔用到的 `filler` 位元組個數。
- is_ptr: 1 個位元，如果字串存在 heap ，令 `is_ptr = 1` 。
- flag1, flag2, flag3
```graphviz
digraph {
node [fontname="Arial"]; node_A[shape=record,label="filler[0]|filler[1]|filler[2]|filler[3]|filler[4]|filler[5]|filler[6]|filler[7]|filler[8]|filler[9]|filler[10]|filler[11]|filler[12]|filler[13]|filler[14]|{spaceleft|spaceleft|spaceleft|spaceleft|is_ptr|flag1|flag2|flag3}"];
}
```
- 當字串長度大於或等於 16 個位元組，則放在 heap (透過 malloc 系統呼叫配置所需字串大小)。
- ptr: 8 個位元組的指標，指向字串儲存的位置。
- size: 字串長度。因定義 54 位元，故最大字串長度為 $2^{54}-1$ 。
- capacity: 從 heap 配置的空間大小，其單位為 $2^{capacity}$，故用 6 個位元即可涵蓋 size 長度。
- 有 4 個位元沒有定義，是為了避免覆寫另一結構成員: `is_ptr`, `flag1`, `flag 2` 與 `flag3`。
```graphviz
digraph {
node [fontname="Arial"]; node_A[shape=record,label="ptr[0]|ptr[1]|ptr[2]|ptr[3]|ptr[4]|ptr[5]|ptr[6]|ptr[7]|size[8]|size[9]|size[10]|size[11]|size[12]|size[13]|{size|size|size|size|size|size|capacity|capacity}|{capacity|capacity|capacity|capacity|is_ptr|flag1|flag2|flag3}"];
}
```
### `xs.c`
```c=
#define MAX_STR_LEN_BITS (54)
#define MAX_STR_LEN ((1UL << MAX_STR_LEN_BITS) - 1)
#define LARGE_STRING_LEN 256
```
```c=
static inline bool xs_is_ptr(const xs *x) { return x->is_ptr; }
```
```c=
static inline bool xs_is_large_string(const xs *x)
{
return x->is_large_string;
}
```
```c=
static inline size_t xs_size(const xs *x)
{
return xs_is_ptr(x) ? x->size : 15 - x->space_left;
}
```
```c=
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 + OFF);
return (char *) x->ptr;
}
```
```c=
static inline size_t xs_capacity(const xs *x)
{
return xs_is_ptr(x) ? ((size_t) 1 << x->capacity) - 1 : 15;
}
```
```c=
static inline void xs_set_refcnt(const xs *x, int val)
{
*((int *) ((size_t) x->ptr)) = val;
}
```
```c=
static inline void xs_inc_refcnt(const xs *x)
{
if (xs_is_large_string(x))
++(*(int *) ((size_t) x->ptr));
}
```
```c=
static inline int xs_dec_refcnt(const xs *x)
{
if (!xs_is_large_string(x))
return 0;
return --(*(int *) ((size_t) x->ptr));
}
```
```c=
static inline int xs_get_refcnt(const xs *x)
{
if (!xs_is_large_string(x))
return 0;
return *(int *) ((size_t) x->ptr);
}
```
```c=
#define xs_literal_empty() \
(xs) { .space_left = 15 }
```
```c=
/* lowerbound (floor log2) */
static inline int ilog2(uint32_t n) { return LLL; }
```
```c=
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);
}
```
```c=
xs *xs_new(xs *x, const void *p)
{
*x = xs_literal_empty();
size_t len = strlen(p) + 1;
if (len > 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_tmp(x)**
```c=
/* 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))
```
```c=
/* 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;
}
```
```c=
static inline xs *xs_newempty(xs *x)
{
*x = xs_literal_empty();
return x;
}
```
```c=
static inline xs *xs_free(xs *x)
{
if (xs_is_ptr(x) && xs_dec_refcnt(x) <= 0)
free(x->ptr);
return xs_newempty(x);
}
```
```c=
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;
}
```
```c=
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;
}
```
```c=
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) (CCC)
#define set_bit(byte) (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);
/* 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
}
```
```c=
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;
}
```
## 重點
- bitfill
## 程式碼學習筆記
### 編譯方式
```
$ gcc -o xs -std=gnu11 xs.c
```
從 [2 Language Standards Supported by GCC](https://gcc.gnu.org/onlinedocs/gcc/Standards.html) 中的
> By default, GCC provides some extensions to the C language that, on rare occasions conflict with the C standard. See Extensions to the C Language Family. Some features that are part of the C99 standard are accepted as extensions in C90 mode, and some features that are part of the C11 standard are accepted as extensions in C90 and C99 modes. Use of the -std options listed above disables these extensions where they conflict with the C standard version selected. You may also select an extended version of the C language explicitly with -std=gnu90 (for C90 with GNU extensions), -std=gnu99 (for C99 with GNU extensions) or -std=gnu11 (for C11 with GNU extensions).
得知是為了使用 GCC extensions 所以使用 `-std=gnu11` (for C11 with GNU extensions) 。
---
### `# undef` 使用
- e.g.
```c=
#define FOO 4
x = FOO; → x = 4;
#undef FOO
x = FOO; → x = FOO;
```
- e.g.
```c=
#define FOUR (2 + 2)
#define FOUR ( 2+2 )
#define FOUR (2 * 2)
#define FOUR(score,and,seven,years,ago) (2 + 2)
```
> If a macro is redefined with a definition that is not effectively the same as the old one, the preprocessor issues a warning and changes the macro to use the new definition. If the new definition is effectively the same, the redefinition is silently ignored. This allows, for instance, two different headers to define a common macro. The preprocessor will only complain if the definitions do not match.
> https://gcc.gnu.org/onlinedocs/cpp/Undefining-and-Redefining-Macros.html
Sign in with Wallet
Connect another wallet