---
tags: linux2021
---
# Linux Final Report
contributed by < `Zxiro` >
> [第 2 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz2)
:::warning
TODO: 改進書寫方式
1. 通用的術語用漢字書寫，如: macro $\to$ 巨集; hash $\to$ 雜湊(值); array $\to$ 陣列; thread $\to$ 執行緒
2. 在探討程式碼之前，應提供高階的描述，導覽整體程式設計的動機、考量、適用場合，及可能的限制等議題
:notes: jserv
:::
## 預計執行內容
- [x] 觀看多執行緒講座
- [x] Part one
- [x] Part two
- [x] Part three
* [Note](https://hackmd.io/T7M7sDgXRHGRiqVj-WfDbg?view)
- [x] 解釋程式碼邏輯
- [x] 描述 string interning 機制以及其實現方式
- [x] 試圖找出現有機制可改善之處
- [ ] 更改程式碼以驗證自身猜測
- [x] 修正程式碼為可供多執行緒進行之環境
- [ ] 閱讀並理解[chriso/intern](https://github.com/chriso/intern)之實現邏輯
- [ ] 嘗試描述兩者之分別
## 摘要
[Wikipedia](https://en.wikipedia.org/wiki/String_interning)
In computer science, string interning is a method of storing only one copy of each distinct string value, which must be immutable.[1] Interning strings makes some string processing tasks more time- or space-efficient at the cost of requiring more time when the string is created or interned. The distinct values are stored in a string intern pool.
The single copy of each string is called its intern and is typically looked up by a method of the string class
字串暫留是一種高效存取字串的方式，透過將字串暫留 (Intern) 在暫留池 (Interning pool) 中，然後用[Hash(雜湊表)](https://zh.wikipedia.org/zh-tw/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8) / [Tries(字典樹)](https://zh.wikipedia.org/wiki/Trie) 等不同[方式](https://loup-vaillant.fr/projects/string-interning/)對應，如果新增一字串就先檢查池中是不是已經有該字串了，若有則用指標指過去就好。如此能夠大幅度降低規劃出新記憶體空間以及從記憶體空間拿出字串的時間與空間成本。
[圖源: What is string interning](https://miafish.wordpress.com/2015/02/05/what-is-string-interning/)
`Only use intern() when it is clear that a string will appear multiple times, and only use it to save memory.`
字串暫留適合用在以下場景
* 大量重複的字串
* e.g. 財務交易資料，每筆交易資料可能會儲存有 `日期`，`幣別`等重複使用的字串。[全世界的`幣別`](https://www.backpackers.com.tw/guide/index.php/%E4%B8%96%E7%95%8C%E5%90%84%E5%9C%8B%E8%B2%A8%E5%B9%A3)少於 1000 筆，但金融機構的每日交易筆數難以估計，若要將每筆交易資料都存入資料庫會需要巨量的儲存空間。
* [Financial application duplicated strings probs](https://stackoverflow.com/questions/10624232/performance-penalty-of-string-intern)
字串暫留帶來的記憶體改善會根據程式中重複與獨特字串的比例發生改變。參考[此篇文章文末](https://www.programmersought.com/article/10074095912/)，該作者在 Java 的運行環境下運行其內建的 `intern()` 函式實測差異，雖然程式運行時間相較於不使用 `intern()` 多了 3 秒，但是其記憶體使用量從 **2.4G** 下降至 **250M**，近十倍的差異顯示出字串暫留對大量重複字串帶來的效益。
## 參考開發者
:::warning
本文用漢語書寫，子項標題應儘量用一致風格。
:notes: jserv
:::
* [XDEv11](https://hackmd.io/@XDEv11/linux2021q1_homework2_quiz2)
* [Julia-chu](https://hackmd.io/@Julian-Chu/2021q1-quiz2)
* [WayneLin1992](https://hackmd.io/@WayneLin1992/SkTJzC3G_)
* [hankluo6](https://hackmd.io/@hankluo6/2021q1quiz2)
* [linD026](https://hackmd.io/@linD026/2021q1_quiz2)
## 以 C 語言實現字串暫留的實作想法
### 不同類型的字串
Made by [Julia Chu](https://hackmd.io/@Julian-Chu/2021q1-quiz2)
* CSTR_ONSTACK
* 可能還會有字串接上來，尚未決定暫留型態的字串。
* CSTR_LITERAL
* 常數字串，使用者或是開發者已經決定好字串內容。
* CSTR_INTERNING
* 符合暫留限制的常數字串
* CSTR_PERMANENT
* 超出暫留限制的常數字串，將會以 `__cstr_data` 的型態留存。
:::warning
測試程式中未能明確指出 `__cstr_data` 中 `ref` 變數的實際功能，個人認為是提供多執行緒的解法。
TODO 驗證想法
:::
### 未定字串暫留
```c=
CSTR_BUFFER(`var`)
```
* 先創造一個大小為 `CSTR_STACK_SIZE` 的字元陣列，作為之後存放字串的空間，並且創造一個 `__cstr_data` 型態的 結構來記錄該字串的相關紀錄。
* 接著創造一個指向該結構的指標名稱為 `var`
* 上述為還未確定要 intern 的字串的方式，也就是說先準備一個空間來存放要 intern 的字串。
### 常數字串暫留
```c=
CSTR_LITERAL(cstring, "STRING")
```
* 使用 `CSTR_LITERAL` 來去 intern 常數字串，已經確定字串內容，直接進行 intern。
* 使用 `cstr_clone` 先判斷該字串是否能夠 intern，若超出限制則以 `__cstr_data` 的形式儲存，`type` 為 `CSTR_PERMANENT`。
* 若符合 interning size 則呼叫 `cstr_interning`，上鎖後呼叫 `interning` 開始將暫留字串。
* 在暫留的過程中會透過**雜湊值**檢查該字串是否已經被留在 `interning pool`，若有就回傳該字串。
:::warning
個人認為能夠在 `cstr_clone` 且符合 `sz < CSTR_INTERNING_SIZE` 就將 `&__cstr_ctx` 上鎖並檢查是否字串重複。
若重複則不需進行該字串雜湊值的計算。
TODO 驗證想法
:::
* 如果上述條件都通過就創建一個新的節點並放入 `interning pool`。
### 字串暫留機制
Made by [Julia Chu](https://hackmd.io/@Julian-Chu/2021q1-quiz2)
引用 [Julia Chu](https://hackmd.io/@Julian-Chu/2021q1-quiz2) 同學所製作的 string interning 關係圖來了解如何完成以及其對應的函式。
string interning 使用 `__cstr_interning `來執行儲存資料的機制。
* `__cstr_interning` 就像實際執行 string interning 的一個場域，裡面提供所有工具來去達成 string interning
* `__cstr_interning` 指向存放字串的 `interning pool`，pool 中存放 `__cstr_data` 型態的暫留字串。`interning_pool` 使用了單向鏈結串列 [方便查找](https://rust-algo.club/collections/linked_list/)。
* `__cstr_interning` 指向雜湊表。`__cstr_data` 中的 `hash_size` 就是其對應的雜湊值。
* 在初始化以及使用量超過 80% 的時候會呼叫 `expand` 來增加雜湊表的大小
其成員作用如下：
* `lock` 防止多執行緒同時處理同樣字串造成錯誤
* `index` 紀錄目前使用到 `pool` 中的第幾個位置
* `size` 紀錄目前雜湊表的容量 (capacity)
* `total` 目前 intern 的字串數量
* `hash` 所有存有 intern 字串的 `__cstr_node` 以此 hash 連結，其內部的 `__cstr_node` 為 `pool` 中的節點
* `pool` 為存放 intern string 的記憶體空間，預先分配足夠的 `__cstr_node` 便不需要頻繁的 malloc，且能讓記憶體更連續防止碎片化
* `pool` 裡面存放的節點是要提供參照的字串資料，而透過 `__cstr_interning` 的雜湊表來去對應 `pool` 裡的節點 來去找的程式需求的字串。
## 程式碼解釋
* [enum](https://opensourcedoc.com/c-programming/enumeration/)
* 根據 [C99 6.7.2.2-2](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
* `The expression that defines the value of an enumeration constant shall be an integer
constant expression that has a value representable as an int`
* 在 enum 裡的變數型態會預設為 `int`
* 如果沒有指定初始值，變數會是上一個變數的值再加一(如果存在的話)
```cpp=
enum {
CSTR_PERMANENT = 1,
CSTR_INTERNING = 2,
CSTR_ONSTACK = 4,
};
```
:::danger
引用 C 語言規格書來說明 `enum`，儘量參照第一手材料
:notes: jserv
:::
* [Define 6.10.3](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
* ```The #define directives define the identifier as a macro, that is they instruct the compiler to replace all successive occurrences of identifier with replacement-list, which can be optionally additionally processed. If the identifier is already defined as any type of macro, the program is ill-formed unless the definitions are identical.```
* 在預處理器內執行 define 語法，真正程式執行時就會代換。
* 其中此 strining interning 有使用到 function-like macros
* ```Function-like macros replace each occurrence of a defined identifier with replacement-list, additionally taking a number of arguments, which then replace corresponding occurrences of any of the parameters in the replacement-list.```
* ```The syntax of a function-like macro invocation is similar to the syntax of a function call: each instance of the macro name followed by a ( as the next preprocessing token introduces the sequence of tokens that is replaced by the replacement-list. The sequence is terminated by the matching ) token, skipping intervening matched pairs of left and right parentheses.```
```The number of arguments must be the same as the number of arguments in the macro definition (parameters) or the program is ill-formed. If the identifier is not in functional-notation, i.e. does not have parentheses after itself, it is not replaced at all.```
* struct 結構 (structure) 是一種複合型別 (derived data type)，用來表達由多個屬性組成的型別
* typedef struct 將這個 struct 定義為一型別，能夠方便呼叫該 struct
```c=
typedef struct __cstr_data {
char *cstr;
uint32_t hash_size;
uint16_t type;
uint16_t ref;
} * cstring;
```
* `##` 相接 Marco 中的 Variable
[## Operator](https://www.ibm.com/docs/en/zos/2.3.0?topic=mdd-operator)
```c=
typedef struct __cstr_buffer {
cstring str;
} cstr_buffer[1];
```
* 將 `cstr_buffer` 宣告成陣列， 藉由陣列的 decay (退化成指向陣列首個元素的特性)，能夠將其變為指向 `__cstr_buffer` 物件的指標``cstr_buffer ptr; ``
:::warning
Buffer 的功能是~~作為一個 hash table(?)存疑 先當作這樣~~
:::
:::info
應是作為一個指標指向 `__cstr_data` 型別的變數
:::
```c=
#define CSTR_BUFFER(var) \
char var##_cstring[CSTR_STACK_SIZE] = {0}; \
struct __cstr_data var##_cstr_data = {var##_cstring, 0, CSTR_ONSTACK, 0}; \
cstr_buffer var; \
var->str = &var##_cstr_data;
```
* 變數類型的 string 透過 `CSTR_BUFFER` 宣告，先建立一個 size 為 `CSTR_STACK_SIZE (128)` 空間的字元陣列用來存放字串，並將 struct `__cstr_data` 內的 cstr 欄位指向該空間，且使用 `cstr_buffer` 內的 str 空間指向這個 structure。
* 此巨集表達創建一個空的雜湊表， ## 為連接的意思 e.g. `CSTR_BUFFER(king)` 表示 king##_cstring 為 king_cstring 。
`bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)`
比較 * ptr 與 oldval 的值，如果兩者相等，則將 newval 更新到 * ptr 並返回 true。
`cstr.c`
```c=
struct __cstr_node {
char buffer[CSTR_INTERNING_SIZE];
struct __cstr_data str;
struct __cstr_node *next;
};
```
* 創造一個字元，大小是要 interning 的字串限制， str 是要存放的字串，型別是 `cstr_data`，含有指向字元的指標， hash_size，type，ref
```c=
struct __cstr_pool {
struct __cstr_node node[INTERNING_POOL_SIZE];
};
```
* 創造一個大小是 `INTERNING_POOL_SIZE` 的陣列，裡面存放的是 `__cstr_node` 型別的物件，是一個放所有節點的記憶體空間。
```c=
struct __cstr_interning {
int lock;
int index;
unsigned size;
unsigned total;
struct __cstr_node **hash;
struct __cstr_pool *pool;
};
static struct __cstr_interning __cstr_ctx;
```
string interning 內部使用 `__cstr_interning` 來執行儲存資料的機制
```c=
#define CSTR_LOCK()({
while (__sync_lock_test_and_set(&(__cstr_ctx.lock), 1)){
}})
```
:::warning
TODO `__cstr_ctx.lock` 初始化是多少?
:::
* `__sync_lock_test_and_set(type *ptr, tpye value)` write value into *ptr and returns the previous contents of *ptr.
* 函式不停回傳 1
```c=
#define CSTR_UNLOCK() ({
__sync_lock_release(&(__cstr_ctx.lock))
})
```
* `__sync_lock_release(*ptr)`This builtin releases the lock acquired by `__sync_lock_test_and_set`. Normally this means writing the constant 0 to *ptr.
* 將 `__sync_lock_test_and_set` 上鎖的 thread 解鎖
```c=
static void *xalloc(size_t n)
{
void *m = malloc(n);
if (!m)
exit(-1);
return m;
}
```
* 分配出記憶體空間
```c=
static inline void insert_node(struct __cstr_node **hash,
int sz,
struct __cstr_node *node)
{
uint32_t h = node->str.hash_size;
int index = h & (sz - 1);
node->next = hash[index];
hash[index] = node;
}
```
```c=
#define CSTR_LITERAL(var, cstr)
// cstring a, cstr = 'String'
static cstring var = NULL;
if (!var) {
cstring tmp = cstr_clone("" cstr, (sizeof(cstr) / sizeof(char)) - 1);
if (tmp->type == 0) {
tmp->type = CSTR_PERMANENT;
tmp->ref = 0;
}
if (!__sync_bool_compare_and_swap(&var, NULL, tmp)) {
if (tmp->type == CSTR_PERMANENT)
free(tmp);
}
}
```
* 常數類型的字串透過 `CSTR_LITERAL` 宣告，透過 `cstr_clone` 建立要進行 intern 字串 (詳見下方 `cstr_clone` 函式)。
* 而當 malloc 失敗 (空間不足) 或是字串過長 (超過 `CSTR_INTERNING_SIZE`）時，tmp->type 被設置為 0，故會將 tmp->type 重新設置為 `CSTR_PERMANENT`。
* 下方的 if 判斷式推測是為了處理多執行緒的問題，當兩個執行緒同時運行 `CSTR_LITERAL` 時，兩者皆進入到 if (!var) 判斷式內部，且剛好此字串長度大於 `CSTR_INTERNING_SIZE` 而配置兩個空間，故一個執行緒在下方的 if 中運行 `__sync_bool_compare_and_swap(&var, NULL, tmp)` 時回傳 true，而之後的執行緒在運行此行時皆會回傳 false，便能刪除多餘的空間。
```c=
static cstring interning(struct __cstr_interning *si,
const char *cstr,
size_t sz,
uint32_t hash)
{
if (!si->hash)
return NULL;
int index = (int) (hash & (si->size - 1));
struct __cstr_node *n = si->hash[index];
while (n) {
if (n->str.hash_size == hash) {
if (!strcmp(n->str.cstr, cstr))
return &n->str;
}
n = n->next;
}
// 80% (4/5) threshold
if (si->total * 5 >= si->size * 4)
return NULL;
if (!si->pool) {
si->pool = xalloc(sizeof(struct __cstr_pool));
si->index = 0;
}
n = &si->pool->node[si->index++];
memcpy(n->buffer, cstr, sz);
n->buffer[sz] = 0;
cstring cs = &n->str;
cs->cstr = n->buffer;
cs->hash_size = hash;
cs->type = CSTR_INTERNING;
cs->ref = 0;
n->next = si->hash[index];
si->hash[index] = n;
return cs;
}
```
* `interning` 函數是用來處理要 intern 的字串
```c=
if (!si->hash)
return NULL;
```
* 檢查有沒有雜湊表的存在，從 `cstr_interning` 知道如果雜湊表不存在，則要呼叫 `expand` 函數分配空間，為求順暢，先將 `interning` 函數講解完畢。
```c=
int index = (int) (hash & (si->size - 1));
struct __cstr_node *n = si->hash[index];
while (n) {
if (n->str.hash_size == hash) {
if (!strcmp(n->str.cstr, cstr))
return &n->str;
}
n = n->next;
}
```
* 計算雜湊值，然後在雜湊表中搜尋各節點的雜湊值(`hash_size`)，若雜湊值存在且字串相等，則直接回傳在雜湊表裡的字串(這也是 string interning 的本意)
```c=
if (si->total * 5 >= si->size * 4) return NULL;
```
* 如果雜湊表的用量超過 4/5 的話，則離開 `interning` 函式並且呼叫 `expand` 函數擴充雜湊表的大小。
```c=
if (!si->pool) {
si->pool = xalloc(sizeof(struct __cstr_pool));
si->index = 0;
}
```
* 初始化存放所有節點的 `interning pool`
```c=
n = &si->pool->node[si->index++];
memcpy(n->buffer, cstr, sz);
n->buffer[sz] = 0;
```
* 因為目前雜湊表中沒有紀錄此字串，故從 `interning pool` 中取一個新的 `__cstr_node` 的位置 n，將字串複製到該結構內的 buffer 中。
```c=
cstring cs = &n->str;
cs->cstr = n->buffer;
cs->hash_size = hash;
cs->type = CSTR_INTERNING;
cs->ref = 0;
```
* 主要要回傳的 cstring 為此節點內的 str 成員位置，而 cstring 的字串則指向此節點的 buffer，並設置對應的 type 及雜湊值方便之後計算。
```c=
n->next = si->hash[index];
si->hash[index] = n;
```
* 將這個新的節點建立與雜湊表的關係。
```c
static cstring cstr_interning(const char *cstr, size_t sz, uint32_t hash)
{
cstring ret;
CSTR_LOCK();
ret = interning(&__cstr_ctx, cstr, sz, hash);
if (!ret) {
expand(&__cstr_ctx);
ret = interning(&__cstr_ctx, cstr, sz, hash);
}
++__cstr_ctx.total;
CSTR_UNLOCK();
return ret;
}
```
* 在寫入時，`CSTR_LOCK()` 會鎖住該執行緒，並在寫完使用 `CSTR_UNLOCK()` 解鎖
```c=
static inline uint32_t hash_blob(const char *buffer, size_t len)
{
const uint8_t *ptr = (const uint8_t *) buffer;
size_t h = len;
size_t step = (len >> 5) + 1;
for (size_t i = len; i >= step; i -= step)
h = h ^ ((h << 5) + (h >> 2) + ptr[i - 1]);
return h == 0 ? 1 : h;
}
```
* 根據字串的長度產生對應的雜湊值
```c=
size_t h = len;
size_t step = (len >> 5) + 1;
for (size_t i = len; i >= step; i -= step)
```
* 透過 bitwise 操作限制不同長度的字串，如果是短字串則每個字元都需要進行雜湊計算(step = 1, 因為碰撞的機率高)，長字串則每 step (大於1) 進行一次運算即可。
`h = h ^ ((h << 5) + (h >> 2) + ptr[i - 1])` 此雜湊計算方式為一變形的[djb2 Hash function](https://api.riot-os.org/group__sys__hashes__djb2.html)
```c=
cstring cstr_clone(const char *cstr, size_t sz)
{
if (sz < CSTR_INTERNING_SIZE)
return cstr_interning(cstr, sz, hash_blob(cstr, sz));
cstring p = xalloc(sizeof(struct __cstr_data) + sz + 1);
if (!p)
return NULL;
void *ptr = (void *) (p + 1);
p->cstr = ptr;
p->type = 0;
p->ref = 1;
memcpy(ptr, cstr, sz);
((char *) ptr)[sz] = 0;
p->hash_size = 0;
return p;
}
```
* `cstr_clone` 為給定一字串，回傳其 cstring。
* 如果其 size 不符合 interning size，則會執行 `cstr_interning`，進行 interning。
* 當 `cstr_grab` 對 stack 上取字串或是創建 `CSTR_LITERAL` 會呼叫。其內容與 `cstr_cat` 的 2, 3 種情況一樣。
```c=
cstring cstr_grab(cstring s)
{
if (s->type & (CSTR_PERMANENT | CSTR_INTERNING))
return s;
if (s->type == CSTR_ONSTACK)
return cstr_clone(s->cstr, s->hash_size);
if (s->ref == 0)
s->type = CSTR_PERMANENT;
else
__sync_add_and_fetch(&s->ref, 1);
return s;
}
```
:::danger
改用 Graphviz 重新製圖
:notes: jserv
:::
Pic made by [Julian-Chu](https://hackmd.io/@Julian-Chu/2021q1-quiz2)
* `cstr_grab` 這個函式決定如何獲得 cstring，如果 type 為 (`PERMANENT` 或 `INTERNING`) 的話代表他們不須或已經執行 interning 直接回傳即可。但如果 type 為 `ONSTACK` 代表還沒有放入 interning pool ，所以要進行 `cstr_clone` 並回傳完成暫留的字串。
* 從 ref == 0 則令為 `PERMANENT` 可知道 `PERMANENT` 是代表因長度超過 interning size 而命名的。
:::warning
TODO type 似乎不會為 0 ，ref 就無法往上加
:::
```c=
void cstr_release(cstring s)
{
if (s->type || !s->ref)
return;
if (__sync_sub_and_fetch(&s->ref, 1) == 0)
free(s);
}
```
* 當 type 不為 0 或 reference count 不為 0 時，直接回傳，否則檢查 reference count 是否只剩一個物件要 release，是的話釋放其空間。
```c=
static size_t cstr_hash(cstring s)
{
if (s->type == CSTR_ONSTACK)
return hash_blob(s->cstr, s->hash_size);
if (s->hash_size == 0)
s->hash_size = hash_blob(s->cstr, strlen(s->cstr));
return s->hash_size;
}
```
* 如果該 cstring s 還沒有進入 interning pool (type 為 `CSTR_ONSTACK`)， `s->hash_size` 為紀錄目前字串長度而非雜湊值，透過 `hash_blob` 計算並回傳。
* `s->hash_size` == 0 時，表示其字串過長不存在雜湊表中，也是額外計算並回傳。
* 若字串已在雜湊表，就直接回傳 `hash_size` (雜湊值) 即可
```c=
int cstr_equal(cstring a, cstring b)
{
if (a == b)
return 1;
if ((a->type == CSTR_INTERNING) && (b->type == CSTR_INTERNING))
return 0;
if ((a->type == CSTR_ONSTACK) && (b->type == CSTR_ONSTACK)) {
if (a->hash_size != b->hash_size)
return 0;
return memcmp(a->cstr, b->cstr, a->hash_size) == 0;
}
uint32_t hasha = cstr_hash(a);
uint32_t hashb = cstr_hash(b);
if (hasha != hashb)
return 0;
return !strcmp(a->cstr, b->cstr);
}
```
* 如果兩個 cstring 相等則回傳 1
* 如果兩個 cstring 都是 interning 的話則回傳 0，因為照理來說，interning pool 的每個節點的 cstring 都應該要是不同的值。
* 如果兩個 type 都是 `CSTR_ONSTACK` 則無法確定，所以先比較長度之後比較內容是否相同
* 之後比較雜湊值是否相同
* 最後即使雜湊值相同，有可能內容不同，再對照字串內容。
```c=
cstring cstr_cat(cstr_buffer sb, const char *str)
{
cstring s = sb->str;
if (s->type == CSTR_ONSTACK) {
int i = s->hash_size;
while (i < CSTR_STACK_SIZE - 1) {
s->cstr[i] = *str;
if (*str == 0)
return s;
++s->hash_size;
++str;
++i;
}
s->cstr[i] = 0;
}
cstring tmp = s;
sb->str = cstr_cat2(tmp->cstr, str);
cstr_release(tmp);
return sb->str;
}
```
* `cstr_cat` 將進行字串與 buffer 的組合
* 如果 buffer 裡的字串沒放入 interning (type = `CSTR_ONSTACK`)，其中 i 是 buffer string 的長度，所以只要未超過 stack size 則將外來的字串接在 buffer string 上。接完就結束
* 如果 type = `CSTR_PERMANENT` 或 `CSTR_INTERNING` 才會執行 `cstr_cat2`
```c=
static cstring cstr_cat2(const char *a, const char *b)
{
size_t sa = strlen(a), sb = strlen(b);
if (sa + sb < CSTR_INTERNING_SIZE) {
char tmp[CSTR_INTERNING_SIZE];
memcpy(tmp, a, sa);
memcpy(tmp + sa, b, sb);
tmp[sa + sb] = 0;
return cstr_interning(tmp, sa + sb, hash_blob(tmp, sa + sb));
}
cstring p = xalloc(sizeof(struct __cstr_data) + sa + sb + 1);
if (!p)
return NULL;
char *ptr = (char *) (p + 1);
p->cstr = ptr;
p->type = 0;
p->ref = 1;
memcpy(ptr, a, sa);
memcpy(ptr + sa, b, sb);
ptr[sa + sb] = 0;
p->hash_size = 0;
return p;
}
```
* 如果兩個 cstring 接起來仍符合 interning size 的限制，就直接宣告新的字元`tmp`並將兩個 cstring 放入後 intern
* 如果超出 interning size 的限制則需要重新 cstring 來去保存，ref 宣告為 1
:::warning
TODO 為何 type = 0 / 直接變成 cstring 不允許串接/ (PERMANENT)?
:::
## 實驗
### 實驗一
#### 欲實驗想法
* 在進行 `cstr_clone` 時是否能夠透過提早檢查雜湊表之值來降低運行時間？
#### 欲實驗方式
* 在進入 `cstr_clone` 後字串條件符合 `CSTR_INTERNING_SIZE` 且 struct `__cstr_interning __cstr_ctx` 存有雜湊表時，先行檢查雜湊表內是否存有該字串
```c=
if (sz < CSTR_INTERNING_SIZE){
if(!&__cstr_ctx.hash)
return cstr_interning(cstr, sz, hash_blob(cstr, sz));
else{
struct __cstr_node *n = &__cstr_ctx.hash[0];
while(n){
if(!strcmp(n->str.cstr, cstr))
return &n->str;
else
n = n->next;
}}
```
#### 實驗結果
* 未考量到多執行緒下不同執行緒對雜湊表的更改。
#### 問題及如何改進
* 擱置實驗一，修正程式碼至 `C11 atomic` 建立可供多執行緒運行之環境並嘗試重現 [linD026](https://hackmd.io/@linD026/2021q1_quiz2) 的實驗。
### 實驗二
* 修正為 `C11 atomic`
* `cstr.c`
```c=
#include <stdatomic.h>
struct __cstr_interning {
volatile atomic_flag lock;
int index;
unsigned size;
unsigned total;
struct __cstr_node **hash;
struct __cstr_pool *pool;
};
#define CSTR_LOCK()
({
while (atomic_flag_test_and_set(&(__cstr_ctx.lock))) {
}
})
#define CSTR_UNLOCK() ({ atomic_flag_clear(&(__cstr_ctx.lock)); })
```
* `cstr.h`
```c=
typedef struct __cstr_data {
char *cstr;
volatile atomic_uint hash_size; // uint32_t
volatile atomic_ushort type; // uint16_t atomic_ushort
volatile atomic_ushort ref; // uint16_t
} * cstring;
```
* [atomic_flag_test_and_set](https://en.cppreference.com/w/c/atomic/atomic_flag_test_and_set)
* `Atomically changes the state of a atomic_flag pointed to by obj to set (true) and returns the previous value.`
* [atomic/atomic_flag_clear](https://en.cppreference.com/w/c/atomic/atomic_flag_clear)
* `Atomically changes the state of a atomic_flag pointed to by obj to clear (false)`
* [atomic_flag](https://en.cppreference.com/w/c/atomic/atomic_flag)
* `atomic_flag is an atomic boolean type. Unlike other atomic types, it is guaranteed to be lock-free`
* 透過將 `lock` 改成 `atomic_flag` 的型態, 當在修改 `__cstr_interning` 時就會變成原子操作（不可分割的操作）。
* 因其具有不可分割的特性，能夠達成 `lock-free` 的操作，進而保證對共用資料的操作不會出錯。
* [lock-free programming](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fconcurrency-lockfree)
#### 問題及如何改進
* 在建置多執行緒環境的時候使用到了 [volatile](https://zh.wikipedia.org/wiki/Volatile%E5%8F%98%E9%87%8F) 型態來儲存共享變數
* 但在閱讀 [volatile](https://en.cppreference.com/w/c/language/volatile) 與多執行緒的相關議題時發現到許多使用 volatile 會造成的問題
* [ atomic和volatile的操作的原子性](https://blog.csdn.net/D_Guco/article/details/74826041) 提到
* volatile 只能保證 2個執行緒之前寫入的值對於另外一個執行緒的可見性
* volatile 不保證原子性
* [Volatile: Almost Useless for Multi-Threaded Programming](http://web.archive.org/web/20190219170904/https://software.intel.com/en-us/blogs/2007/11/30/volatile-almost-useless-for-multi-threaded-programming/)
* C/C++, JAVA 之間的 volatile 所具備之意義也不全相同
* 未來需要進一步了解多執行緒下 volatile 所擔任的角色
Sign in with Wallet
Connect another wallet