# 2021q1 Homework2 (quiz2)
contributed by < `XDEv11` >
> [GitHub](https://github.com/XDEv11/Linux_Kernel_Internals/tree/main/homework2/quiz2)
> [第 2 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz2)
## 測驗 `1`
### 程式碼解說
透過 [`__extension__`](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html) 來明確表示要使用 GNU C extensions，並避免在某些情況下產生警告。
> -pedantic and other options cause warnings for many GNU C extensions. You can prevent such warnings within one expression by writing __extension__ before the expression. __extension__ has no effect aside from this.
[`({})`](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html) 有點類似於 `,` 運算子，藉此達到類似於函式回傳值的效果。
> The last thing in the compound statement should be an expression followed by a semicolon; the value of this subexpression serves as the value of the entire construct.
[`__typeof__()`](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 可得到變數的型態。
> If you are writing a header file that must work when included in ISO C programs, write `__typeof__` instead of typeof.
[`offsetof()`](https://man7.org/linux/man-pages/man3/offsetof.3.html) 得到某個成員的位置偏移量。
```cpp
/**
* container_of() - Calculate address of object that contains address ptr
* @ptr: pointer to member variable
* @type: type of the structure containing ptr
* @member: name of the member variable in struct @type
*
* Return: @type pointer of object containing ptr
*/
#ifndef container_of
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#endif
```
doubly-linked list 的鏈結，納入新結構的成員中即可。
```cpp
/**
* struct list_head - Head and node of a doubly-linked list
* @prev: pointer to the previous node in the list
* @next: pointer to the next node in the list
*/
struct list_head {
struct list_head *prev, *next;
};
```
```cpp
/**
* LIST_HEAD - Declare list head and initialize it
* @head: name of the new object
*/
#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}
```
```cpp
/**
* INIT_LIST_HEAD() - Initialize empty list head
* @head: pointer to list head
*/
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head; head->prev = head;
}
```
```cpp
/**
* list_add_tail() - Add a list node to the end of the list
* @node: pointer to the new node
* @head: pointer to the head of the list
*/
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
```
```cpp
/**
* list_del() - Remove a list node from the list
* @node: pointer to the node
*/
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next, *prev = node->prev;
next->prev = prev; prev->next = next;
}
```
```cpp
/**
* list_empty() - Check if list head has no nodes attached
* @head: pointer to the head of the list
*/
static inline int list_empty(const struct list_head *head)
{
return (head->next == head);
}
```
```cpp
/**
* list_is_singular() - Check if list head has exactly one node attached
* @head: pointer to the head of the list
*/
static inline int list_is_singular(const struct list_head *head)
{
return (!list_empty(head) && head->prev == head->next);
}
```
把 `list` 接到 `node` 的尾端。
```cpp
/**
* list_splice_tail() - Add list nodes from a list to end of another list
* @list: pointer to the head of the list with the node entries
* @head: pointer to the head of the list
*/
static inline void list_splice_tail(struct list_head *list,
struct list_head *head)
{
struct list_head *head_last = head->prev;
struct list_head *list_first = list->next, *list_last = list->prev;
if (list_empty(list))
return;
head->prev = list_last;
list_last->next = head;
list_first->prev = head_last;
head_last->next = list_first;
}
```
把串列從 `node` 的地方切開，前半部分接到 `head_to`，後半部分留在 `head_from`。
```cpp
/**
* list_cut_position() - Move beginning of a list to another list
* @head_to: pointer to the head of the list which receives nodes
* @head_from: pointer to the head of the list
* @node: pointer to the node in which defines the cutting point
*/
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
```
假設自己定義的 `struct S`，裡面有一個 `list_head list`，可以透過 `list_entry(node, S, list)` 得到整個物件的指標 `struct S *`。
```cpp
/**
* list_entry() - Calculate address of entry that contains list node
* @node: pointer to list node
* @type: type of the entry containing the list node
* @member: name of the list_head member variable in struct @type
*/
#define list_entry(node, type, member) container_of(node, type, member)
```
```cpp
/**
* list_first_entry() - get first entry of the list
* @head: pointer to the head of the list
* @type: type of the entry containing the list node
* @member: name of the list_head member variable in struct @type
*/
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
```
```cpp
/**
* list_for_each - iterate over list nodes
* @node: list_head pointer used as iterator
* @head: pointer to the head of the list
*/
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
運用上述程式碼實作 merge sort。
`list_ele_t` 中的 `next` 與 `queue_t` 中的 `head` 和 `tail` 都不需要。
`list_ele_t` 與 `queue_t` 中都有一個 `struct list_head` 即可形成 circular doubly-linked list。
這邊進一步改進，將 `struct list_head` 放在結構中的第一個成員，存取整個物件時，只需把 `struct list_head *` 轉型為 `list_ele_t *`，而不需要使用 `list_entry()` (`container_of()`) 這個 macro，不只讓操作更便利以外，也節省運算指標位置的減法 (`- offsetof(type, member))`)。
:::warning
`container_of` 用到 `offsetof`，後者是編譯時期的操作。在結構體中的第一個成員 `struct list_head list;` 需要特別標注其位置，也該考慮到 padding，例如 [Typical alignment of C structs on x86](https://en.wikipedia.org/wiki/Data_structure_alignment#Typical_alignment_of_C_structs_on_x86) 所及，第二個成員實際的記憶體位置可能會因 padding 調整
:::
:::success
根據 [C11 standard](http://open-std.org/JTC1/SC22/WG14/www/docs/n1570.pdf) 6.7.2.1 Structure and union specifiers 中第 15 點，對於第一個成員的位置是有規範的。
> Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared. A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning.
:::
```cpp
typedef struct __element {
struct list_head list;
/* Put struct list_head in the initial(first) member */
char *value;
} list_ele_t;
```
:::warning
程式碼精簡後，不難發現 `queue_t` 根本就是多餘的結構，應該一併調整。這是設計題目時，讓同學們得以進一步重構 (refactor) 的空間。
:notes: jserv
:::
:::success
已經進行重構，把多餘的結構去除並改寫程式碼！
:::
回傳值改為 `list_head *`，會比較好進行串列的操作。需要時，也可透過 `list_entry()` 得到整個物件。
```cpp
static struct list_head *get_middle(struct list_head *head)
{
struct list_head *fast = head->next, *slow = head->next;
while (fast->next != head && fast->next->next != head) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
```
```cpp
static void list_merge(struct list_head *lhs,
struct list_head *rhs,
struct list_head *head)
{
INIT_LIST_HEAD(head);
while (!list_empty(lhs) && !list_empty(rhs)) {
char *lv = ((list_ele_t *)lhs->next)->value;
char *rv = ((list_ele_t *)rhs->next)->value;
struct list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next;
list_del(tmp);
list_add_tail(tmp, head);
}
list_splice_tail(list_empty(lhs) ? rhs : lhs, head);
}
```
```cpp
void list_merge_sort(struct list_head *q)
{
if (list_empty(q) || list_is_singular(q))
return;
struct list_head left, sorted;
INIT_LIST_HEAD(&left);
list_cut_position(&left, q, get_middle(q));
list_merge_sort(&left);
list_merge_sort(q);
list_merge(&left, q, &sorted);
INIT_LIST_HEAD(q);
list_splice_tail(&sorted, q);
}
```
測試程式碼
```cpp
static bool validate(struct list_head *q)
{
struct list_head *node;
for (node = q->next; node->next != q; node = node->next) {
if (strcmp(((list_ele_t *)node)->value,
((list_ele_t *)node->next)->value) > 0)
return false;
}
return true;
}
```
```cpp
static struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
if (!q) return NULL;
INIT_LIST_HEAD(q);
return q;
}
```
```cpp
static void q_free(struct list_head *q)
{
struct list_head *current = q->next;
while (current != q) {
struct list_head *tmp = current;
current = current->next;
free(((list_ele_t *)tmp)->value);
free((list_ele_t *)tmp);
}
free(q);
}
```
這邊可以利用 `list_add_tail` 把他接到第一個元素 (`q->next`) 的前面。
```cpp
bool q_insert_head(struct list_head *q, char *s)
{
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
char *new_value = strdup(s);
if (!new_value) {
free(newh);
return false;
}
newh->value = new_value;
list_add_tail((struct list_head *)newh, q->next);
return true;
}
```
```cpp
static void q_show(struct list_head *q)
{
struct list_head *node;
list_for_each (node, q) {
printf("%s", ((list_ele_t *)node)->value);
}
}
```
```cpp
int main(void)
{
FILE *fp = fopen("cities.txt", "r");
if (!fp) {
perror("failed to open cities.txt");
exit(EXIT_FAILURE);
}
struct list_head *q = q_new();
char buf[256];
while (fgets(buf, 256, fp))
q_insert_head(q, buf);
fclose(fp);
list_merge_sort(q);
q_show(q);
assert(validate(q));
q_free(q);
return 0;
}
```
---
## 測驗 `2`
### 程式碼解說
```cpp
uint16_t func(uint16_t N) {
/* change all right side bits to 1 */
N |= N >> 1;
N |= N >> 2;
N |= N >> 4;
N |= N >> 8;
return (N + 1) >> 1;
}
```
`N |= N >> 1;` 會讓第一個 `1` 的位元的下一個位元變成 `1`，接著 `N |= N >> 2;` 會讓第一個 `1` 的位元開始的四個位元都變成 `1`，以此類推。
```graphviz
digraph {
num0 [shape="record", label="0|0|0|0|0|0|1|?|?|?|?|?|?|?|?|?"];
num1 [shape="record", label="0|0|0|0|0|0|1|1|?|?|?|?|?|?|?|?"];
num2 [shape="record", label="0|0|0|0|0|0|1|1|1|1|?|?|?|?|?|?"];
num2 [shape="record", label="0|0|0|0|0|0|1|1|1|1|?|?|?|?|?|?"];
num3 [shape="record", label="0|0|0|0|0|0|1|1|1|1|1|1|1|1|?|?"];
num4 [shape="record", label="0|0|0|0|0|0|1|1|1|1|1|1|1|1|1|1"];
num0 -> num1;
num1 -> num2;
num2 -> num3;
num3 -> num4;
}
```
最後得到一個第一個 `1` 的位元以下皆為 `1` 的數字，加上 1 後往左位移，即可得到第一個 `1` 的位元以下皆為 `0` 的數字。
程式碼最後一行應該改為 `return (N >> 1) + 1;`，避免 msb 為 `1` 的數字會溢位。
特別注意的是 `func(0)` 會從 `0` 變為 `1`，不過 小於或等於 `0` 的 power-of-2 本身就是未定義的，這邊就不管它了。
不過因為這邊型別是 16 位元的無號整數，利用 gdb 去看組合語言。
```
0x000000000000118a <+65>: add $0x1,%eax
0x000000000000118d <+68>: sar %eax
0x000000000000118f <+70>: pop %rbp
0x0000000000001190 <+71>: retq
```
可以發現 `return (N + 1) >> 1;` 是用 32 位元的暫存器 (`%eax`) 做運算，所以不會有整數溢位的問題。
如果把寫法改成，
```
...
N += 1;
return N >> 1;
```
就會得到，
```
0x0000000000001186 <+61>: addw $0x1,-0x4(%rbp)
0x000000000000118b <+66>: movzwl -0x4(%rbp),%eax
0x000000000000118f <+70>: shr %ax
0x0000000000001192 <+73>: pop %rbp
0x0000000000001193 <+74>: retq
```
可以發現程式碼會使用 16 位元的暫存器做運算，
或是改成 32 位元的無號整數版本，都會產生整數溢位的問題。
:::success
根據 [C11 standard](http://open-std.org/JTC1/SC22/WG14/www/docs/n1570.pdf) 6.3.1 Arithmetic operands 6.3.1.1 Boolean, characters, and integers 中第 2 點，
> If an int can represent all values of the original type (as restricted by the width, for abit-field), the value is converted to an int; otherwise, it is converted to an unsigned int. These are called the integer promotions. All other types are unchanged by the integer promotions.
`return (N + (uint16_t)1) >> 1;` 在這邊一樣是用 `int` 做運算，並不會有整數溢位的問題。
:::
---
## 測驗 `3`
### 程式碼解說
要從某個位元開始存取資料時，當前的位元組往左位移 `_read_lhs` 與下一個位元組往右移 `_read_rhs` 後，進行 bitwise or 運算，即可得到一整個位元組大小的資料。
寫入時則剛好相反，整個位元組往右位移 `_write_lhs` 寫入當前的位元組，往左位移 `_write_rhs` 則寫入下一個位元組。
`_*_rhs` 的值剛好也是代表當前位元組佔了幾個位元，所以要判斷有沒有跨越位元組時，可以用 `bitsize` 與 `_*_rhs` 進行比較。
下圖為 `_read_lhs` 等於 `3` 時的示意圖。
```graphviz
digraph {
rankdir=LR
byte [shape="record", label="{*|*|*|*|*|#|#|#}"];
equal [shape="plain", label="="];
byteR [shape="record", label="{#|#|#|4|3|2|1|0}"];
plus [shape="plain", label="+"];
byteL [shape="record", label="{7|6|5|*|*|*|*|*}"];
}
```
`_read / 8` 即可得知從第幾個位元組開始操作，而 `_read & 7` 則是計算從此位元組的第幾個位元開始，(`_read / 8` 可用 `_read >> 3` 替代)。
`_write` 部分的操作與 `_read` 同理。
這邊做了一些小修改，
* `>> 3` 替代 `/ 8`
* 去除 `origin` 這個變數，直接用 `*dest` 表示
* 去除一些不必要的條件判斷
* 將 `read_mask` 與 `write_mask` 改名，使其更易理解。
* `left_mask[b]` 代表位元 b 左邊為 `1`
* `right_mask[b]` 代表位元 b 右邊及本身為 `1`
```cpp=
void bitcpy(void *_dest, /* Address of the buffer to write to */
size_t _write, /* Bit offset to start writing to */
const void *_src, /* Address of the buffer to read from */
size_t _read, /* Bit offset to start reading from */
size_t count)
{
static const uint8_t left_mask[] = {
0x00, /* == 0 00000000b */
0x80, /* == 1 10000000b */
0xC0, /* == 2 11000000b */
0xE0, /* == 3 11100000b */
0xF0, /* == 4 11110000b */
0xF8, /* == 5 11111000b */
0xFC, /* == 6 11111100b */
0xFE, /* == 7 11111110b */
0xFF /* == 8 11111111b */
};
static const uint8_t right_mask[] = {
0xFF, /* == 0 11111111b */
0x7F, /* == 1 01111111b */
0x3F, /* == 2 00111111b */
0x1F, /* == 3 00011111b */
0x0F, /* == 4 00001111b */
0x07, /* == 5 00000111b */
0x03, /* == 6 00000011b */
0x01, /* == 7 00000001b */
0x00 /* == 8 00000000b */
};
size_t read_lhs = _read & 7;
size_t read_rhs = 8 - read_lhs;
const uint8_t *source = (const uint8_t *) _src + (_read >> 3);
size_t write_lhs = _write & 7;
size_t write_rhs = 8 - write_lhs;
uint8_t *dest = (uint8_t *) _dest + (_write >> 3);
while (count > 0) {
size_t bitsize = (count > 8) ? 8 : count;
uint8_t data = *source++;
if (read_lhs > 0) {
data <<= read_lhs;
data |= (*source >> read_rhs);
}
data &= left_mask[bitsize];
uint8_t mask = left_mask[write_lhs];
if (bitsize > write_rhs) {
/* Cross multiple bytes */
*dest = (*dest & mask) | (data >> write_lhs);
++dest;
*dest = (*dest & right_mask[bitsize - write_rhs]) | (data << write_rhs);
} else {
// Since write_lhs + bitsize is never >= 8, no out-of-bound access.
mask |= right_mask[write_lhs + bitsize];
*dest = (*dest & mask) | (data >> write_lhs);
++dest;
}
count -= bitsize;
}
}
```
第 39 行開始，先把下一個位元組大小的資料放入 `data` 中，44 行再把多餘的位元利用 `left_mask` 去除。
下面用了一些遮罩，為了保存頭尾我們沒有要寫入的部分 ，取用 `left_mask` 以及 `right_mask` 的引索意義如下，
* `write_lhs` 代表從當前位元組的第幾個位元開始
* `write_lhs + bitsize` 代表寫到當前位元組的第幾個位元
* `bitsize - write_rhs` 代表寫到下一位元組的第幾個位元 (上述說過，`write_rhs` 也代表在當前位元組佔了多少位元，所以 `bitsize` 扣除它後，剩下的就是在下一位元組。)
如果 `bitsize <= write_rhs`，代表寫入的部分不需要跨位元，54 行後，`mask` 示意圖如下，以 `write_lhs` 為 `3`，`bitsize` 為 `4` 為例。
```graphviz
digraph {
rankdir=LR
byte [shape="record", label="{1|1|1|0|0|0|0|1}"];
}
```
如果 `bitsize > write_rhs`，`mask` 右側一定都為 `0`，下圖以 `write_lhs` 為 `3`，`bitsize` 為 `7` 為例。
```graphviz
digraph {
rankdir=LR
byte [shape="record", label="{1|1|1|0|0|0|0|0}"];
}
```
51 行的 `right_mask[bitsize - write_rhs]` 則得到另一個 mask，
```graphviz
digraph {
rankdir=LR
byte [shape="record", label="{0|0|1|1|1|1|1|1}"];
}
```
### 效率更高的實作
中間的部分，每次剛好複製 `source` 的一個位元組，可降低讀取時的運算量。
```cpp
void bitcpy_opt(void *_dest, /* Address of the buffer to write to */
size_t _write, /* Bit offset to start writing to */
const void *_src, /* Address of the buffer to read from */
size_t _read, /* Bit offset to start reading from */
size_t count)
{
static const uint8_t left_mask[] = {
0x00, /* == 0 00000000b */
0x80, /* == 1 10000000b */
0xC0, /* == 2 11000000b */
0xE0, /* == 3 11100000b */
0xF0, /* == 4 11110000b */
0xF8, /* == 5 11111000b */
0xFC, /* == 6 11111100b */
0xFE, /* == 7 11111110b */
0xFF /* == 8 11111111b */
};
static const uint8_t right_mask[] = {
0xFF, /* == 0 11111111b */
0x7F, /* == 1 01111111b */
0x3F, /* == 2 00111111b */
0x1F, /* == 3 00011111b */
0x0F, /* == 4 00001111b */
0x07, /* == 5 00000111b */
0x03, /* == 6 00000011b */
0x01, /* == 7 00000001b */
0x00 /* == 8 00000000b */
};
const uint8_t *source = (const uint8_t *) _src + (_read >> 3);
_read &= 7;
uint8_t *dest = (uint8_t *) _dest + (_write >> 3);
_write &= 7;
// first byte in source
size_t bitsize = count < 8 - _read ? count : 8 - _read;
uint8_t data = (*source++ << _read) & left_mask[bitsize];
uint8_t mask = left_mask[_write] | (_write + bitsize < 8 ? right_mask[_write + bitsize] : 0x00);
*dest = (*dest & mask) | (data >> _write);
if (_write + bitsize >= 8) {
++dest;
size_t remain = _write + bitsize - 8;
if (_write)
*dest = (*dest & right_mask[remain]) | (data << (8 - _write));
}
count -= bitsize;
_write = (_write + bitsize) & 7;
while (count >= 8) {
data = *source++;
*dest = (*dest & left_mask[_write]) | (data >> _write);
++dest;
if (_write)
*dest = (*dest & right_mask[_write]) | data << (8 - _write);
count -= 8;
}
// last byte in source
data = *source++ & left_mask[count];
mask = left_mask[_write] | (_write + count < 8 ? right_mask[_write + count] : 0x00);
*dest = (*dest & mask) | (data >> _write);
if (count > 8 - _write) {
++dest;
size_t remain = count - (8 - _write);
*dest = (*dest & right_mask[remain]) | (data << (8 - _write));
}
}
```
---
## 測驗 `4`
### 程式碼解說
`cstr.h`
```cpp
#pragma once
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
```
分別用 2 的冪次代表，可以透過 `|` (bitwise or) 進行聯集形成集合。
```cpp
enum {
CSTR_PERMANENT = 1,
CSTR_INTERNING = 2,
CSTR_ONSTACK = 4,
};
```
```cpp
#define CSTR_INTERNING_SIZE (32)
#define CSTR_STACK_SIZE (128)
```
```cpp
typedef struct __cstr_data {
char *cstr;
uint32_t hash_size;
uint16_t type;
uint16_t ref;
} * cstring;
```
這邊定義 `cstr_buffer` 為 `__cstr_buffer[1]`，在大多時候，array 會退化 (decay) 成一個 pointer，
這邊的功能類似 `__cstr_buffer*`，但在使用時，卻不用寫成
```cpp
__cstr_buffer obj;
cstr_buffer ptr = &obj;
```
而是
```cpp
cstr_buffer ptr;
```
，即可在 stack 上有一個 `__cstr_buffer` 的物件，而名稱可以當作指標使用。
可參考 [Everything you need to know about pointers in C](https://boredzo.org/pointers/#arrays)
```cpp
typedef struct __cstr_buffer {
cstring str;
} cstr_buffer[1];
```
```cpp
#define CSTR_S(s) ((s)->str)
```
把 `var` 中的 `str` 初始成一個字串放在 stack 上的 `__cstr_data`。
```cpp
#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;
```
初使化一個靜態的 `cstring`，並透過 [`__sync_bool_compare_and_swap()`](https://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Atomic-Builtins.html) 確保在多執行緒的環境下能夠正確執行。
```cpp
#define CSTR_LITERAL(var, cstr) \
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); \
} \
}
```
`do { } while(0)` 可參考 [ multi-line macro: do/while(0) vs scope block](https://stackoverflow.com/questions/1067226/c-multi-line-macro-do-while0-vs-scope-block);
```cpp
#define CSTR_CLOSE(var) \
do { \
if (!(var)->str->type) \
cstr_release((var)->str); \
} while (0)
```
```cpp
/* Public API */
cstring cstr_grab(cstring s);
cstring cstr_clone(const char *cstr, size_t sz);
cstring cstr_cat(cstr_buffer sb, const char *str);
int cstr_equal(cstring a, cstring b);
void cstr_release(cstring s);
```
`cstr.c`
```cpp
#include <errno.h>
#include <stdarg.h>
#include <stdio.h>
#include <string.h>
#include "cstr.h"
#define INTERNING_POOL_SIZE 1024
#define HASH_START_SIZE 16 /* must be power of 2 */
```
```cpp
struct __cstr_node {
char buffer[CSTR_INTERNING_SIZE];
struct __cstr_data str;
struct __cstr_node *next;
};
```
```cpp
struct __cstr_pool {
struct __cstr_node node[INTERNING_POOL_SIZE];
};
```
```cpp
struct __cstr_interning {
int lock;
int index;
unsigned size;
unsigned total;
struct __cstr_node **hash;
struct __cstr_pool *pool;
};
```
```cpp
static struct __cstr_interning __cstr_ctx;
```
```cpp
/* FIXME: use C11 atomics */
#define CSTR_LOCK() \
({ \
while (__sync_lock_test_and_set(&(__cstr_ctx.lock), 1)) { \
} \
})
#define CSTR_UNLOCK() ({ __sync_lock_release(&(__cstr_ctx.lock)); })
```
進行 `malloc`，失敗則直接中止程式。
```cpp
static void *xalloc(size_t n)
{
void *m = malloc(n);
if (!m)
exit(-1);
return m;
}
```
將物件放入雜湊表。
```cpp
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;
}
```
將 `si` 中的雜湊表 (`hash`) 擴大一倍。
```cpp
static void expand(struct __cstr_interning *si)
{
unsigned new_size = si->size * 2;
if (new_size < HASH_START_SIZE)
new_size = HASH_START_SIZE;
struct __cstr_node **new_hash =
xalloc(sizeof(struct __cstr_node *) * new_size);
memset(new_hash, 0, sizeof(struct __cstr_node *) * new_size);
for (unsigned i = 0; i < si->size; ++i) {
struct __cstr_node *node = si->hash[i];
while (node) {
struct __cstr_node *tmp = node->next;
insert_node(new_hash, new_size, node);
node = tmp;
}
}
free(si->hash);
si->hash = new_hash;
si->size = new_size;
}
```
嘗試進行字串駐留，若 `si` 本身為空，或是裡面的物件多於雜湊表大小的 `80%` 時，則失敗。
```cpp
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;
}
```
進行字串駐留，若失敗了，則拓展雜湊表，再進行一次。
```cpp
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;
}
```
真正的雜湊函數。
```cpp
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;
}
```
這邊 `void *ptr = (void *) (p + 1);` 應為 `char *ptr = (char *)(p + sizeof(struct __cstr_data));`，在一個 `struct __cstr_data` 之後，才是配置給字串的空間。
如果字串長度小於 `CSTR_INTERNING_SIZE`，就進行字串駐留，否則的話，直接配置一個新的 `cstring`。
```cpp
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;
char *ptr = (char *)(p + sizeof(struct __cstr_data));
p->cstr = ptr;
p->type = 0;
p->ref = 1;
memcpy(ptr, cstr, sz);
ptr[sz] = 0;
p->hash_size = 0;
return p;
}
```
```cpp
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;
}
```
對字串進行記憶體釋放，這邊使用 [sync_sub_and_fetch](https://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Atomic-Builtins.html) 來確保在多執行緒的環境下能夠正確運作。
```cpp
void cstr_release(cstring s)
{
if (s->type || !s->ref)
return;
if (__sync_sub_and_fetch(&s->ref, 1) == 0)
free(s);
}
```
如果 `s` 是放在 stack 上，`hash_size` 是它的長度，否則的話，確認是否計算過雜湊值。 (回傳值應改為 `uint32_t `)
```cpp
static uint32_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;
}
```
如果 `a` 與 `b` 都是被駐留的字串，那只有當指標相同時才會是一樣的字串；如果字串在 stack 上，可以先用字串長度 (`hash_size`) 判斷一下，否則也可以先用雜湊值判斷一下。
```cpp
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;
}
if (cstr_hash(a) != cstr_hash(b))
return 0;
return !strcmp(a->cstr, b->cstr);
}
```
這邊 `char *ptr = (char *) (p + 1);` 應為 `char *ptr = (char *)(p + sizeof(struct __cstr_data));`，理由同上。
如果 `a` 與 `b` 的長度小於 `CSTR_INTERNING_SIZE`，會進行字串駐留，否則的話就另外配置一個 `cstring`。
```cpp
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 + sizeof(struct __cstr_data));
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;
}
```
先看看原本 `sb` 中的字串是不是放在 stack，是的話嘗試把 `str` 也放入，不行的話就呼叫 `cstr_cat2` 去進行記憶體配置並完成字串連接。
```cpp
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.h` 中可以看到，會得到 `cstring` 的有 `cstr_grab()` 、 `cstr_clone()` 與 `cstr_cat()`，還有 `CSTR_BUFFER` 與 `CSTR_LITERAL` 二個巨集。
可以歸納出處理字串的行為，如果字串長度小於 `CSTR_INTERNING_SIZE` 的話，就會進行字串駐留， `type` 為 `CSTR_INTERNING`，`hash_size` 中保存它的雜湊值，否則的話，就直接放在一個 `cstring` 中而已，`type` 為 `0`，`hash_size` 也為 `0`；比較特別的是，透過 `CSTR_BUFFER` 宣告的變數，其中的 `cstring` 一開始是指向放在 `stack` 上的記憶體，最多可以存放 `CSTR_STACK_SIZE - 1` 長度的字串，`type` 為 `CSTR_ONSTACK`，`hash_size` 為字串長度。
另外，`CSTR_LITERAL` 中透過 `cstr_clone()` 得到的 `cstring`，如果沒有進行字串駐留，`type` 則會變成 `CSTR_PERMANENT`，`ref` 則為 `0`。
:::info
程式碼中，會減少 `ref` 的只有 `cstr_release()`，但是當它變為 `0` 後，又會直接釋放記憶體，另一邊 `cstr_grab()` 的地方則是在 `ref` 為 `0` 時會把 `type` 轉為 `CSTR_PERMANENT`。
這邊對於 `ref` 這個成員以及 `CSTR_PERMANENT` 這樣的 `cstring`，看起來並沒有太多應用，也不太完整，或許是為了未來開發作保留的。
:::
###### tags: `linux2021`
Sign in with Wallet
Connect another wallet