# 2021q1 Homework3 (quiz3)
contributed by < [`toastcheng`](https://github.com/toastcheng) >
###### tags: `linux2021`
## 進度
- [x] 1. 程式碼運作原理
- [x] 2. 改進方案
- [x] 3. 字串複製 (CoW) 的函式實作
- [ ] 4. 分析字串處理最佳化的空間效益
- [x] 5. 整合 string interning
- [x] 6. Linux 中的 SSO、CoW 案例
---
## Q1: Small String Optimization
### 1. 程式碼運作原理
```cpp
typedef union {
char data[16];
struct {
uint8_t filler[15],
space_left : 4,
is_ptr : 1,
is_large_string : 1,
flag2 : 1,
flag3 : 1;
};
struct {
char *ptr;
size_t size : 54,
capacity : 6;
};
} xs;
```
透過 `xs` 使用 `union` 的方式可以看出 `xs` 總共佔用 16 bytes (128 bits) 的記憶體空間，因為不同情境可能為 `char data[16]` 或另外兩種 `struct`。
#### `xs_data` 回傳字串的開頭
```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 */ 4);
return (char *) x->ptr;
}
```
從程式的分支邏輯對應 `xs` 的三種 layout，可以看出依照不同情境，字串的開頭可能分別在：
1. short string: `x->data` 指向的位置
字串長度小於 16，直接存放在 stack。
2. large string: `x->ptr` 後 4 個 byte 的位置
字串長度大於 `LARGE_STRING_LEN` (256)，會利用前 `x->ptr` 指向位置的前 4 個 byte 存放 reference count，因此真正存放資料的位置在 `x->ptr + 4`。與 `xs_allocate_data` 的邏輯相呼應，其依照字串長度做不同記憶體配置。
3. middle string: `x->ptr` 指向的位置
若是大於或等於 16，並且小於 `LARGE_STRING_LEN`，則一樣分配在 heap，並由 `x->ptr` 指向其位址，與 large string 差別在於不另外紀錄 reference count。
有趣的是 `x->data` 及 `x->ptr` 應是在相同的位置，這個部分應該可以改善，可見 [改進方案](https://hackmd.io/twR8uo8KT7G0rIXbiBfDiQ#2-%E6%94%B9%E9%80%B2%E6%96%B9%E6%A1%88)。
#### `xs_size` 回傳字串的長度
```cpp
static inline size_t xs_size(const xs *x)
{
return xs_is_ptr(x) ? x->size : 15 - x->space_left;
}
```
從這個函式可以看出字串的長度如何儲存在 `xs`，如果是 short string，其內容完全儲存在 stack，可以由 `space_left` 知道還有多少空間，因此將 `15 - x->space_left` 就能得到大小；而 medium string、large string 因為是動態配置，所以其大小另外存在 `x->size` 中。
#### `xs_capacity`
```cpp
static inline size_t xs_capacity(const xs *x)
{
return xs_is_ptr(x) ? ((size_t) 1 << x->capacity) - 1 : 15;
}
```
如果為 short string，容量固定為 15，而 medium string 及 large string 則透過 `capacity` 紀錄，而 `capacity` 則是在 `xs_new` 中決定的，會分配一個比字串長度還大的 power of 2 為其值。
#### `xs_*_refcnt`
```cpp
static inline void xs_set_refcnt(const xs *x, int val)
{
*((int *) ((size_t) x->ptr)) = val;
}
static inline void xs_inc_refcnt(const xs *x)
{
if (xs_is_large_string(x))
++(*(int *) ((size_t) x->ptr));
}
static inline int xs_dec_refcnt(const xs *x)
{
if (!xs_is_large_string(x))
return 0;
return --(*(int *) ((size_t) x->ptr));
}
static inline int xs_get_refcnt(const xs *x)
{
if (!xs_is_large_string(x))
return 0;
return *(int *) ((size_t) x->ptr);
}
```
對長字串的 reference count 做操作的函式，可以發現唯獨 `xs_set_refcnt` 並沒有確保字串為長字串，可見[改進方案](https://hackmd.io/twR8uo8KT7G0rIXbiBfDiQ#2-%E6%94%B9%E9%80%B2%E6%96%B9%E6%A1%88)。
#### `ilog2` 取對數
```cpp
static inline int ilog2(uint32_t n) { return /* LLL */ 32 - __builtin_clz(n) - 1; }
```
透過 `__builtin_clz` 的使用，找到最高位非 0 bit 的位置（從右算起），根據對數的定義該位置 - 1 便是 `n` 的對數的整數部分。
#### `xs_allocate_data` 配置記憶體
```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` 針對 medium、large string 做記憶體配置，在此判斷如果長度大於 `LARGE_STRING_LEN` 就要多配置 4 個 bytes 以供紀錄 reference count。
#### `xs_new`
```cpp
xs *xs_new(xs *x, const void *p)
{
*x = xs_literal_empty();
size_t len = strlen(p) + 1;
if (len > /* NNN */ 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`，針對是否是 short string 決定是否要利用 `xs_allocate_data` 動態配置記憶體，在 `xs_allocate_data` 中會再針對 medium string 或 large string 做不同的配置。
#### `xs_grow`
```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->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` 所配置的記憶體空間至 `len`，並更新 `capacity`，並且處理字串種類的變化，但只涵蓋從 short string 成長為 medium string 的情況，仔細觀察也會發現若是成長為 large string，並沒有相對應的處理，改進可見[改進方案](https://hackmd.io/twR8uo8KT7G0rIXbiBfDiQ#2-%E6%94%B9%E9%80%B2%E6%96%B9%E6%A1%88)。
#### `xs_cow_lazy_copy`
```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;
}
```
這個函式意義上應是將字串 `data` 的內容複製到 `x`，先考慮 reference count > 1 的情況：
1. 相同內容的長字串因為共用同一段記憶體空間，因此當要將 `data` 的內容更改為 `x`，勢必無法繼續共用原本的記憶體空間，因此在更改之前呼叫 `xs_dec_refcnt`（`x` 不再引用到這個記憶體空間）
2. 呼叫 `xs_allocate_data` 重新分配記憶體空間
3. 利用 `memcpy` 進行複製
而如果 reference count <= 1，
在最初的檢查 `x` 會直接回傳 false 並且完全沒有執行到 `memcpy`，亦即沒有真的進行複製。對於這樣的行為思考許久，為什麼不必複製？
搜尋使用的情境發現呼叫 `xs_cow_lazy_copy` 的方式都是對相同的內容進行複製，共有兩處。
`xs_concat`：
```cpp
char *data = xs_data(string);
xs_cow_lazy_copy(string, &data);
```
以及 `xs_trim`:
```cpp
char *dataptr = xs_data(x), *orig = dataptr;
if (xs_cow_lazy_copy(x, &dataptr))
orig = dataptr;
```
或許這兩處使用 `xs_cow_lazy_copy` 是因為它們將要改動原本的內容，因此先複製到別的位置。但 `xs_cow_lazy_copy` 較符合預期的行為應該還是要複製 reference count <= 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);
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;
}
```
回傳一個 `prefix + string + suffix` 的字串。
#### `xs_trim`
```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 */ mask[(uint8_t) byte / 8] & 1 << (uint8_t) byte % 8)
#define set_bit(byte) (/* SSS */ 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
}
```
將 `x` 開頭及結尾含有 `trimset` 內的字元的部分截去。
### 2. 改進方案
#### union 中多餘的 data type
程式碼中可以看到 `xs` 所代表的字串有分為短中長三種，但這三種並不是一一對應 `xs` 的三種排列，短字串對應的是：
```cpp
struct {
uint8_t filler[15],
space_left : 4,
is_ptr : 1,
is_large_string : 1,
flag2 : 1,
flag3 : 1;
};
```
長字串則是：
```cpp
struct {
char *ptr;
size_t size : 54,
capacity : 6;
};
```
可以發現 `char data[16];` 是多餘的，其功能可以由 `filler` 代替，因為它們指向相同的記憶體位址，雖然 `filler` 的大小為 15 個 bytes，但當字串長度包含 `\0` 為 16 時，`space_left` 為 0、後面 4 個 flag 也因為是 short string 而為 0，因此 `filler` 後的最後一個 byte 也會是 `\0`。
但這樣設計要成立需要確保編譯器沒有為了避免 unaligned memory access 做 padding。
根據 ISO/IEC 9899:201x 6.7.2.1 p.113
> If enough space remains, a bit-field that immediately follows another bit-field in a structure shall be packed into adjacent bits of the same unit
以 1 word = 4 byte 來說，`filler` 佔據了 3 個 word 又 3 bytes，最後一個 word 恰好可以讓剩下的 bit fields 補齊，因此沒有 padding 發生。
```cpp
struct {
uint8_t filler[15],
space_left : 4,
is_ptr : 1,
is_large_string : 1,
flag2 : 1,
flag3 : 1;
};
```
做一個實驗來看看每個 bitfield 的位置是否不必加額外的 pack 也不會有多餘的 padding：
```cpp
typedef struct {
uint8_t filler[15],
space_left : 4,
is_ptr : 1, is_large_string : 1, flag2 : 1, flag3 : 1;
} s_t;
int main() {
s_t s;
printf("filler: %p\n", &s.filler);
printf("space_left: %p\n", s.space_left);
printf("is_ptr: %p\n", &s.is_ptr);
printf("is_large_string: %p\n", &s.is_large_string);
printf("flag2: %p\n", &s.flag2);
printf("flag3: %p\n", &s.flag3);
}
```
但很顯然 bit field 無法被 address of：
```shell
padding_test.c:17:42: error: cannot take address of bit-field 'space_left'
17 | printf("space_left: %p\n", ((char *) &s.space_left));
| ^
```
因為 bit field 的單位是 bit，比指標指向的單位 (byte) 還要細。
在 ISO/IEC 9899:201x 6.7.2.1 p.112 提到：
> The unary & (address-of) operator cannot be applied to a bit-field object; thus, there are no pointers to
or arrays of bit-field objects.
所以改由觀察整個 struct 所佔據的記憶體空間，使用 `sizeof` 來看是否大於 16：
```cpp
int main() {
printf("size: %lu\n", sizeof(s_t));
}
```
> 預期輸出：
> ```
> size: 16
> ```
結果顯示確實沒有額外的 padding。
參考資料
[Unaligned Memory Accesses](https://www.kernel.org/doc/Documentation/unaligned-memory-access.txt#:~:text=Unaligned%20memory%20accesses%20occur%20when,be%20an%20unaligned%20memory%20access.)
#### `xs_set_refcnt` checking
`xs_set_refcnt` 並沒有防止使用者對 short string、middle string 指派 reference count。
```cpp
static inline void xs_set_refcnt(const xs *x, int val)
{
if (xs_is_large_string(x))
*((int *) ((size_t) x->ptr)) = val;
}
```
#### `xs_allocate_data`
考慮將已分配為 large string 重新分配成 medium string 的長度，應把 `is_large_string` 這個 flag 設為 0。
```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);
x->is_large_string = 0;
return;
}
```
#### `xs_grow` 邏輯錯誤
`xs_grow` 有許多明顯的問題：
1. 在 short string 成長為 medium/large string 的情況，先更改了 `is_ptr` 才在後續判斷原本是否為 short string （利用 `xs_is_ptr`）
2. 沒有考慮增長為 large string 的情況
用一個簡單的測試就能看到程式的問題：
```cpp
int main(int argc, char *argv[])
{
xs *string = xs_new(&xs_literal_empty(), "12345");
printf("type should be short (0): %d, capcity: %ld\n", xs_type(string), xs_capacity(string));
xs_grow(string, 16);
printf("type should be medium (1): %d, capcity: %ld\n", xs_type(string), xs_capacity(string));
xs_grow(string, 256);
printf("type should be large (2): %d, capcity: %ld\n", xs_type(string), xs_capacity(string));
return 0;
}
```
> 預期輸出：
> ```shell
> type should be short (0): 0, capcity: 15
> Segmentation fault
> ```
修改程式碼如下：
```cpp
xs *xs_grow(xs *x, size_t len)
{
// 將成長前的 is_ptr 保存起來
bool is_ptr = x->is_ptr;
x->is_ptr = true;
if (len < LARGE_STRING_LEN) {
if (is_ptr) {
xs_allocate_data(x, len, 1);
} else {
xs_allocate_data(x, len, 0);
memcpy(xs_data(x), buf, 16);
}
} else {
// 增長為 large string 的情況
x->is_large_string = true;
if (is_ptr) {
xs_allocate_data(x, len, 1);
} else {
xs_allocate_data(x, len, 0);
memcpy(xs_data(x) + 4, buf, 16);
}
}
return x;
}
```
> 預期輸出：
> ```shell
> type should be short (0): 0, capcity: 15
> type should be medium (1): 1, capcity: 31
> type should be large (2): 2, capcity: 511
> ```
### 3. 字串複製 (CoW) 的函式實作
參照 [5. 整合 string interning](https://hackmd.io/twR8uo8KT7G0rIXbiBfDiQ#5-%E6%95%B4%E5%90%88-string-interning) 的部分，將 `xs_cow_lazy_copy` 改寫，主要需要考量若 `x` 為 large string，那複製 `data` 到 `x` 時，必須一併處理 reference count，在複製前，應將 reference count 減一，然後再為 `x` 配置新的記憶體空間。
```cpp
static void xs_cow_lazy_copy(xs *x, char **data)
{
if (!x->is_large_string) {
memcpy(xs_data(x), *data, strlen(*data));
return;
} else if (xs_get_refcnt(x) > 1) {
/* Lazy copy */
xs_dec_refcnt(x);
xs_interning_nontrack(x, *data, x->size, 0);
}
if (data) {
memcpy(xs_data(x), *data, x->size);
}
/* Update the newly allocated pointer */
*data = xs_data(x);
return;
}
```
考量到在 string interning 中的實作，會對比字串的 hash 是否跟 pool 中存在的 string 相同，若有則進一步比對，若確定與現存的 string 重複，則使用同一段記憶體空間。
但在 `xs_cow_lazy_copy` 的使用情境不同，即便字串相同，但可能即將被 `concat` 或 `trim` 等方式修改內容，所以會希望它被存在不同的記憶體空間，即使內容重複，因此實作 `xs_interning_nontrack`，將記憶體配置，而不透過 string interning 紀錄其值，也不會計算 hash。
```cpp
static void xs_interning_nontrack(xs *x, const void *p, size_t len, bool reallocate)
{
x->ptr = reallocate ? realloc(x->ptr, (size_t) 1 << x->capacity + 4)
: malloc((size_t) 1 << x->capacity + 4);
memcpy(xs_data(x), p, len);
xs_set_refcnt(x, 1);
}
```
而在 `concat` 及 `trim` 完成對字串的更動之後，加上這一個操作，將該記憶體位置加入 string interning 的紀錄。
```cpp
if (string->is_large_string)
add_interning_address(string->ptr);
```
`add_interning_address` 的實作如下，跟 `add_interning` 雷同，差別在於它直接接受一個位於 `heap` 的字串位址，不必再分配記憶體，而 `add_interning` 則是需要自行配置記憶體，再將該記憶體位址回傳給呼叫的函式，該函式需要負責將位址指派到 `xs_data(xs)`。
```cpp
void add_interning_address(char *data)
{
XS_LOCK();
int len = strlen(data);
uint32_t hash = hash_blob(data, len);
if (!__intern_ctx.pool) {
__intern_ctx.pool = malloc(sizeof(struct __xs_pool));
}
struct xs_node **n = &__intern_ctx.pool->node[hash];
while (*n) {
if (strcmp((*n)->data + 4, data) == 0) {
++(*(int *) ((size_t) (*n)->data));
XS_UNLOCK();
return;
}
n = &((*n)->next);
}
*n = malloc(sizeof(struct xs_node));
(*n)->data = data;
XS_UNLOCK();
return;
}
```
### 4. 分析字串處理最佳化的空間效益
:::success
應考慮到 locality of reference，善用 GDB 追蹤和分析，確認字串的確符合預期地配置於 stack 或 heap;
:::
`// TODO 補完分析和實驗`
#### `xs` 空間效率
針對 1000 個 short+medium 的字串做初始化：
`xs`
```
KB
46.84^ #
| @@#
| @@::@@#
| @@@@ : @@#
| @@@@@ @ : @@#
| :@@ @@@ @ : @@#
| :::@:@@ @@@ @ : @@#
| @@@: :@:@@ @@@ @ : @@#
| @@@@@@ : :@:@@ @@@ @ : @@#
| @@@ @@@@ : :@:@@ @@@ @ : @@#
| @@@@ @ @@@@ : :@:@@ @@@ @ : @@#
| :@@@@ @ @ @@@@ : :@:@@ @@@ @ : @@#
| @@:@ @@ @ @ @@@@ : :@:@@ @@@ @ : @@#
| @@::@ :@ @@ @ @ @@@@ : :@:@@ @@@ @ : @@#
| @@:@ : @ :@ @@ @ @ @@@@ : :@:@@ @@@ @ : @@#
| @@@@@:@ : @ :@ @@ @ @ @@@@ : :@:@@ @@@ @ : @@#
| @@@@@ @@:@ : @ :@ @@ @ @ @@@@ : :@:@@ @@@ @ : @@#
| :: @@@@@@@ @@:@ : @ :@ @@ @ @ @@@@ : :@:@@ @@@ @ : @@#
| : ::@ @@@@@ @@:@ : @ :@ @@ @ @ @@@@ : :@:@@ @@@ @ : @@#
| : ::@ @@@@@ @@:@ : @ :@ @@ @ @ @@@@ : :@:@@ @@@ @ : @@#
0 +----------------------------------------------------------------------->ki
0 486.2
```
`std::string`
```
KB
77.54^ #
| #:::::::@::
| #:::::::@::
| #:::::::@::
| #:::::::@::
| #:::::::@::
| #:::::::@::
| #:::::::@::
| #:::::::@::
| #:::::::@::
| #:::::::@::
| #:::::::@::
| #:::::::@::
| #:::::::@::
| #:::::::@::
| #:::::::@::
| #:::::::@::
| #:::::::@::
| #:::::::@::
|@ #:::::::@::
0 +----------------------------------------------------------------------->Mi
0 2.430
```
### 5. 整合 string interning
嘗試用簡易的方式來追蹤程式中的 large string，加入 `intern.[ch]` 來為 `xs` 擴充。
大部分的 struct 為 `cstr` 的簡化：
```cpp
struct xs_node {
char *data;
struct xs_node *next;
};
struct __xs_interning {
int lock;
struct __xs_pool *pool;
};
struct __xs_pool {
struct xs_node *node[INTERNING_POOL_SIZE];
};
static struct __xs_interning __intern_ctx;
```
實作 `add_interning`，該函式主要會被 `xs_new` 呼叫，若是使用者新增了一個 large string，便會透過此函式分配記憶體，並計算 hash，放進 pool 中。
```cpp
struct xs_node *add_interning(const char *str)
{
XS_LOCK();
int len = strlen(str);
uint32_t hash = hash_blob(str, len);
if (!__intern_ctx.pool) {
__intern_ctx.pool = malloc(sizeof(struct __xs_pool));
}
struct xs_node **n = &__intern_ctx.pool->node[hash];
while (*n) {
if (strcmp((*n)->data + 4, str) == 0) {
++(*(int *) ((size_t) (*n)->data));
XS_UNLOCK();
return *n;
}
n = &((*n)->next);
}
*n = malloc(sizeof(struct xs_node));
(*n)->data = malloc(sizeof(char) * len + 4);
memcpy(((*n)->data + 4), str, len);
XS_UNLOCK();
return (*n);
}
```
修改過後的 `xs_new`，直接負責處理不同長度字串的邏輯，而 `xs_allocate_data` 也簡化為處理 middle string 的記憶體分配：
```cpp
xs *xs_new(xs *x, const void *p)
{
*x = xs_literal_empty();
size_t len = strlen(p) + 1;
if (len > LARGE_STRING_LEN) {
x->capacity = ilog2(len) + 1;
x->size = len - 1;
x->is_ptr = true;
x->is_large_string = true;
xs_interning(x, p, x->size, 0);
} else if (len > /* NNN */ MIDDLE_STRING_LEN) {
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;
}
```
large string 的記憶體分配以及 string interning 紀錄則改由 `xs_interning` 來負責：
```cpp
static void xs_interning(xs *x, const void *p, size_t len, bool reallocate)
{
// the allocation and set refcnt is handled at interning
struct xs_node *n = add_interning(p);
x->ptr = n->data;
}
```
作為測試，新增三個長度超過 `LARGE_STRING_LEN` 的相同字串，並用 `xs_data` （效果同 `string->ptr + 4`）並用 `%p` 觀察是否有共用同一段記憶體位址。
```cpp
#include "../xs.h"
int main(int argc, char *argv[])
{
xs *string1 = xs_new(&xs_literal_empty(), "1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890");
xs *string2 = xs_new(&xs_literal_empty(), "1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890");
xs *string3 = xs_new(&xs_literal_empty(), "1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890");
printf("string1: %p\n", xs_data(string1));
printf("string2: %p\n", xs_data(string2));
printf("string3: %p\n", xs_data(string3));
}
```
> 預期輸出:
> ```
> string1: 0x55a42c2332d4
> string2: 0x55a42c2332d4
> string3: 0x55a42c2332d4
> ```
詳細實作可見 [GitHub](https://github.com/ToastCheng/linux-2021q1/blob/main/week3/q3/intern.c)（TODO: 優化實作）。
### 6. Linux 中的 SSO、CoW 案例
CoW 的設計應該會有兩個情境：
1. 不修改內容時，**不複製**使用共享的資料
2. 預期會修改內容時，複製資料至新分配的記憶體空間
觀察 `sk_buff`，為代表 socket buffer 的 struct，有對應的函式 `skb_copy`、`skb_clone`：
#### `skb_copy`
```cpp
/**
* skb_copy - create private copy of an sk_buff
* @skb: buffer to copy
* @gfp_mask: allocation priority
*
* Make a copy of both an &sk_buff and its data. This is used when the
* caller wishes to modify the data and needs a private copy of the
* data to alter. Returns %NULL on failure or the pointer to the buffer
* on success. The returned buffer has a reference count of 1.
*
* As by-product this function converts non-linear &sk_buff to linear
* one, so that &sk_buff becomes completely private and caller is allowed
* to modify all the data of returned buffer. This means that this
* function is not recommended for use in circumstances when only
* header is going to be modified. Use pskb_copy() instead.
*/
struct sk_buff *skb_copy(const struct sk_buff *skb, gfp_t gfp_mask)
{
int headerlen = skb_headroom(skb);
unsigned int size = skb_end_offset(skb) + skb->data_len;
struct sk_buff *n = __alloc_skb(size, gfp_mask,
skb_alloc_rx_flag(skb), NUMA_NO_NODE);
if (!n)
return NULL;
/* Set the data pointer */
skb_reserve(n, headerlen);
/* Set the tail pointer and length */
skb_put(n, skb->len);
BUG_ON(skb_copy_bits(skb, -headerlen, n->head, headerlen + skb->len));
skb_copy_header(n, skb);
return n;
}
```
註解提到：
> Make a copy of both an &sk_buff and its data. This is used when the caller wishes to modify the data and needs a private copy of the data to alter.
很明顯地這是 CoW 的情境，在預期會修改內容的情況複製，並將 reference count 設為 1。
#### `skb_clone`
```cpp
/**
* skb_clone - duplicate an sk_buff
* @skb: buffer to clone
* @gfp_mask: allocation priority
*
* Duplicate an &sk_buff. The new one is not owned by a socket. Both
* copies share the same packet data but not structure. The new
* buffer has a reference count of 1. If the allocation fails the
* function returns %NULL otherwise the new buffer is returned.
*
* If this function is called from an interrupt gfp_mask() must be
* %GFP_ATOMIC.
*/
struct sk_buff *skb_clone(struct sk_buff *skb, gfp_t gfp_mask)
{
struct sk_buff_fclones *fclones = container_of(skb,
struct sk_buff_fclones,
skb1);
struct sk_buff *n;
if (skb_orphan_frags(skb, gfp_mask))
return NULL;
if (skb->fclone == SKB_FCLONE_ORIG &&
refcount_read(&fclones->fclone_ref) == 1) {
n = &fclones->skb2;
refcount_set(&fclones->fclone_ref, 2);
} else {
if (skb_pfmemalloc(skb))
gfp_mask |= __GFP_MEMALLOC;
n = kmem_cache_alloc(skbuff_head_cache, gfp_mask);
if (!n)
return NULL;
n->fclone = SKB_FCLONE_UNAVAILABLE;
}
return __skb_clone(n, skb);
}
```
註解提到：
> The new one is not owned by a socket. Both copies share the same packet data but not structure. The new buffer has a reference count of 1.
透過 `skb_clone` 複製的 socket buffer 會跟原本的 `sk_buffer` 共享 packet data (`unsigned char *data`)，並將 reference count 設為 1，可見 `__skb_clone`，在 `sk_buff` 中 reference count 紀錄在 `refcount_t users` 中：
```cpp
static struct sk_buff *__skb_clone(struct sk_buff *n, struct sk_buff *skb)
{
// ...
refcount_set(&n->users, 1);
// ...
}
```
這和純粹的共享資料有點不同，可以注意到 `skb_clone` 依然將 reference count 設為 1，照 string interning 的邏輯，如果要重複使用相同的字串，應該要將 reference count 加一。
那增加 reference count 的情境應該是本來預期的共享資料，因此用 `refcount_inc\(&[a-zA-Z]+->users\)` 搜尋，但並沒有特定的函式負責管理，而是每個函式在接收到 `sk_buff` 的指標副本後負責增減 reference count，各自管理。
#### `skb_unshare`
```cpp
/*
* Copy shared buffers into a new sk_buff. We effectively do COW on
* packets to handle cases where we have a local reader and forward
* and a couple of other messy ones. The normal one is tcpdumping
* a packet thats being forwarded.
*/
/**
* skb_unshare - make a copy of a shared buffer
* @skb: buffer to check
* @pri: priority for memory allocation
*
* If the socket buffer is a clone then this function creates a new
* copy of the data, drops a reference count on the old copy and returns
* the new copy with the reference count at 1. If the buffer is not a clone
* the original buffer is returned. When called with a spinlock held or
* from interrupt state @pri must be %GFP_ATOMIC
*
* %NULL is returned on a memory allocation failure.
*/
static inline struct sk_buff *skb_unshare(struct sk_buff *skb,
gfp_t pri)
{
might_sleep_if(gfpflags_allow_blocking(pri));
if (skb_cloned(skb)) {
struct sk_buff *nskb = skb_copy(skb, pri);
/* Free our shared copy */
if (likely(nskb))
consume_skb(skb);
else
kfree_skb(skb);
skb = nskb;
}
return skb;
}
```
另外還有 `skb_unshare` 這樣的函式，先用 `skb_cloned` 來判斷拿到的 `skb` 是否為透過 `skb_clone` 得到的，如果是就重新呼叫 `skb_copy` 斷開兩者共享的 packet data。
Sign in with Wallet
Connect another wallet