# 2021q1 Homework5 (quiz5)
contributed by < `hankluo6` >
> [第 5 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz5)
## 測驗 `1`
:::spoiler 參考解答
#### `VV1 = ?`
- [x] `(e) !(s & (s - 1))`
#### `VV2 = ?`
- [x] `(a) v.size -= 1`
#### `VV3 = ?`
- [x] `(b) elemsize * (size_t) 1 << ++v->capacity`
:::
### 運作原理
```cpp
#define STRUCT_BODY(type) \
struct { \
size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1, \
flag3 : 1; \
type *ptr; \
}
```
宣告一個 structure 用來取得 Vector 內資訊，其中 `size_t` 的大小儲存 size, capacity 及是否在 heap 等資訊，`type *` 的指標指向真正存放資料的位置。
```c=
#define v(t, s, name, ...) \
(void) ((struct { \
_Static_assert(s <= 8, "it is too big"); \
int dummy; \
}){1}); \
union { \
STRUCT_BODY(t); \
struct { \
size_t filler; \
t buf[NEXT_POWER_OF_2(s)]; \
}; \
} name __attribute__((cleanup(vec_free))) = {.buf = {__VA_ARGS__}}; \
name.size = sizeof((__typeof__(name.buf[0])[]){0, __VA_ARGS__}) / \
sizeof(name.buf[0]) - \
1; \
name.capacity = sizeof(name.buf) / sizeof(name.buf[0])
```
宣告一個 vector，其中 `t` 為對應的 type；`s` 為 size；`name` 為變數名字；而最後方的 `...` 則為初始化的值，利用 [Variadic Macros](https://gcc.gnu.org/onlinedocs/cpp/Variadic-Macros.html) 實現。
2 ~ 3 行檢查大小是否小於 8，並宣告一個 union，內部 structure 的前 64 bits 存放 Vector 資訊，在第二個 struct 中用 `filler` 防止覆蓋資料，而 Vector 真正的資料則存在 `buf` 中。當資料需要存放在 heap 時，改以 `ptr` 紀錄其位置。宣告的 union 使用 GCC 的 [cleanup attribute](https://gcc.gnu.org/onlinedocs/gcc/Common-Variable-Attributes.html) 來達成自動回收的機制，並將初始值賦值給 `buf`。
>cleanup (cleanup_function)
>
>The cleanup attribute runs a function when the variable goes out of scope. This attribute can only be applied to auto function scope variables; it may not be applied to parameters or variables with static storage duration. The function must take one parameter, a pointer to a type compatible with the variable. The return value of the function (if any) is ignored.
第 13 行計算 Vector 初始的大小，`__typeof__(name.buf[0])[]` 宣告一個以 `name.buf[0]` 的 type 之陣列，並給予初始值 `{0, __VA_ARGS__}`，也就是 0 加上 user 給予的初始值，`sizeof` 回傳這整個陣列的大小，除上 `sizeof(name.buf[0])` 即為 user 給予的初始值大小再加上 1 (設定初始值時多放置一個 0)，故最後 size 即為所得再減 1。
TODO:
直接透過 `sizeof((__typeof__(name.buf[0])[]){__VA_ARGS__}) / sizeof(name.buf[0]);` 好像也能取得大小？
第 16 行為計算陣列宣告的大小。
```c
#define vec_size(v) v.size
#define vec_capacity(v) \
(v.on_heap ? (size_t) 1 << v.capacity : sizeof(v.buf) / sizeof(v.buf[0]))
#define vec_data(v) (v.on_heap ? v.ptr : v.buf) /* always contiguous buffer */
#define vec_elemsize(v) sizeof(v.buf[0])
#define vec_pos(v, n) vec_data(v)[n] /* lvalue */
#define vec_reserve(v, n) __vec_reserve(&v, n, vec_elemsize(v), vec_capacity(v))
#define vec_push_back(v, e) \
__vec_push_back(&v, &(__typeof__(v.buf[0])[]){e}, vec_elemsize(v), \
vec_capacity(v))
#define vec_pop_back(v) (void) (v.size -= 1)
#define NON_NULL __attribute__((nonnull))
```
宣告 Marco 用來處理對應的函式。其中 `nonnull` 會讓 compiler 對 null parameter 提出警告。
>nonnull (arg-index, ...)
>
>The nonnull attribute specifies that some function parameters should be non-null pointers.
>If no argument index list is given to the nonnull attribute, all pointer arguments are marked as non-null.
```c
static NON_NULL void vec_free(void *p)
{
STRUCT_BODY(void) *s = p;
if (s->on_heap)
free(s->ptr);
}
```
當 Vector 資料處存在 heap 上時，才需要釋放空間，此函數在宣告 Vector 時已經以 attribute 的方式加入到 cleanup 中，會在變數超出範圍時自動執行，故不需要手動釋放空間。
另外在 `vec_free` 內部 `s` 可以直接宣告為 `STRUCT_BOFY` 而非 `union {...} *s = p` 是因為參數 `void *p` 為要釋放的變數空間 (此例為 `v(t, s, name, ...)` 宣告產生的 `name`)，即得 `p = &name`，而 `STRUCT_BODY` 與 `union {...}` 的前面 64 bits 存放的內容一樣，故可以直接利用 `STRUCT_BODY` 取得 `on_heap` 變數。
```c
static NON_NULL void __vec_reserve(void *vec,
size_t n,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(void);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (n > capacity) {
if (v->on_heap) {
v->ptr = realloc(v->ptr,
elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
} else {
void *tmp =
malloc(elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
}
}
}
```
如果原本 Vector 存放在 stack 中，則在 heap 上分配新的空間，如果本來就在 heap 上，則透過 `realloc` 重新分配空間。
```c
static NON_NULL void __vec_push_back(void *restrict vec,
void *restrict e,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (v->on_heap) {
if (v->size == 1 << capacity)
v->ptr = realloc(v->ptr, elemsize * (size_t) 1 << ++v->capacity);
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else {
if (v->size == 1 << capacity) {
void *tmp =
malloc(elemsize * (size_t) 1 << (v->capacity = capacity + 1));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else
memcpy(&v->buf[v->size++ * elemsize], e, elemsize);
}
}
```
push 檢查大小是否超過 capacity，超過則需要增加 Vector 的大小，如果本來在 stack 中，遍會在 heap 上新增大小，最後在將資料複製到 Vector 中。
### 改進
#### Growth Factor
根據 [folly:fbvector](https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md) 內提到 growth factor 為 2 時產生的問題來改進。當 growth factor = 2 時，假設 vector 初始 capacity 為 1，則第 n 次的 reallocation 必須產生 $2^n$ 大小的空間，而先前產生的總空間為 $2^0 + 2^1 + \dots + 2^{n-1}=2^n - 1$，這使得新分配的空間不能使用之前已經分配的空間，而是必須重新尋找一塊 $2^n$ 大小的空間來使用。
growth factor 在 C++ 中為 implementation define，我們可以透過不同編譯器的實作來觀察 growth factor 對 Vector 的影響。
使用以下程式碼測試：
```cpp
int main()
{
vector<int64_t> x;
for (int i = 0; i < 50; ++i) {
printf("%lu %p\n", x.capacity(), x.data());
x.push_back(0);
}
}
```
運行結果：
```
msvc 14.27 | mingw 8.1.0 | gcc 9.3.0
(windows) (windows) (linux)
capacity address | capacity address | capacity address
--------------------------------------------------------------------------
0 00000000 | 0 000000000000000 | 0 (nil)
1 00D3F498 | 1 000000000f43e50 | 1 0x563b776302c0
2 00D36420 | 2 000000000f43e90 | 2 0x563b776302e0
3 00D35A78 | 4 000000000f43ed0 | 4 0x563b77630300
4 00D36420 | 4 000000000f43ed0 | 4 0x563b77630300
6 00D35A78 | 8 000000000f43e50 | 8 0x563b77630330
6 00D35A78 | 8 000000000f43e50 | 8 0x563b77630330
9 00D357A0 | 8 000000000f43e50 | 8 0x563b77630330
9 00D357A0 | 8 000000000f43e50 | 8 0x563b77630330
9 00D357A0 | 16 000000000f43ed0 | 16 0x563b77630380
13 00D358E0 | 16 000000000f43ed0 | 16 0x563b77630380
13 00D358E0 | 16 000000000f43ed0 | 16 0x563b77630380
13 00D358E0 | 16 000000000f43ed0 | 16 0x563b77630380
13 00D358E0 | 16 000000000f43ed0 | 16 0x563b77630380
19 00D3ACE0 | 16 000000000f43ed0 | 16 0x563b77630380
19 00D3ACE0 | 16 000000000f43ed0 | 16 0x563b77630380
19 00D3ACE0 | 16 000000000f43ed0 | 16 0x563b77630380
19 00D3ACE0 | 32 000000000de24b0 | 32 0x563b77630410
19 00D3ACE0 | 32 000000000de24b0 | 32 0x563b77630410
19 00D3ACE0 | 32 000000000de24b0 | 32 0x563b77630410
28 00D40EF0 | 32 000000000de24b0 | 32 0x563b77630410
28 00D40EF0 | 32 000000000de24b0 | 32 0x563b77630410
28 00D40EF0 | 32 000000000de24b0 | 32 0x563b77630410
28 00D40EF0 | 32 000000000de24b0 | 32 0x563b77630410
28 00D40EF0 | 32 000000000de24b0 | 32 0x563b77630410
28 00D40EF0 | 32 000000000de24b0 | 32 0x563b77630410
28 00D40EF0 | 32 000000000de24b0 | 32 0x563b77630410
28 00D40EF0 | 32 000000000de24b0 | 32 0x563b77630410
28 00D40EF0 | 32 000000000de24b0 | 32 0x563b77630410
42 00D41000 | 32 000000000de24b0 | 32 0x563b77630410
42 00D41000 | 32 000000000de24b0 | 32 0x563b77630410
42 00D41000 | 32 000000000de24b0 | 32 0x563b77630410
42 00D41000 | 32 000000000de24b0 | 32 0x563b77630410
42 00D41000 | 64 000000000de25e0 | 64 0x563b77630520
42 00D41000 | 64 000000000de25e0 | 64 0x563b77630520
42 00D41000 | 64 000000000de25e0 | 64 0x563b77630520
42 00D41000 | 64 000000000de25e0 | 64 0x563b77630520
42 00D41000 | 64 000000000de25e0 | 64 0x563b77630520
42 00D41000 | 64 000000000de25e0 | 64 0x563b77630520
42 00D41000 | 64 000000000de25e0 | 64 0x563b77630520
42 00D41000 | 64 000000000de25e0 | 64 0x563b77630520
42 00D41000 | 64 000000000de25e0 | 64 0x563b77630520
42 00D41000 | 64 000000000de25e0 | 64 0x563b77630520
63 00D41180 | 64 000000000de25e0 | 64 0x563b77630520
63 00D41180 | 64 000000000de25e0 | 64 0x563b77630520
63 00D41180 | 64 000000000de25e0 | 64 0x563b77630520
63 00D41180 | 64 000000000de25e0 | 64 0x563b77630520
63 00D41180 | 64 000000000de25e0 | 64 0x563b77630520
63 00D41180 | 64 000000000de25e0 | 64 0x563b77630520
63 00D41180 | 64 000000000de25e0 | 64 0x563b77630520
```
在 Visual C++ 中，growth factor 為 1.5，而在 GCC 中則為 2，可以發現兩者的 capacity 增長的範圍不同。另外可發現在 Mingw 中，有些位址有重複，但在 Visual C++ 中卻沒有，這是因為在上面分析時，我們假設分配的記憶體空間為連續分配，兩次重新分配的空間中不會有間隔，但在實際應用上，兩次分配的空間間隔並不為 $2 \times \text{sizeof (int64_t)}=8 \text{ bytes}$，所以實際可用空間其實會比分配給 Vector 內 data 的記憶體空間還大，故是有可能會有重複利用空間的可能發生，而要不要重複利用該記憶體空間，則是由 OS 來決定，像此例中 Visual C++ 便沒有利用到重覆的記憶體空間。
:::info
這邊測試中 Vector 內的 type 設定為 64 bits integer，這是為了要對應 64 位元電腦的資料對齊，假如使用大小相對較小的型別 (如 `char`)，則 OS 為了要對齊資料，Vector 中兩次的 reallocation 一樣會產生間隔，此時，因 Vector 內的 data 所需要的資料空間較小，便能更有效利用這些 memory fragments，所以記憶體重複利用的機會便會升高。
:::
>[你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory?type=view)
使用以下程式碼測試：
```cpp
int main()
{
vector<intXX_t> x;
vector<intXX_t *> pointer;
size_t times = 0;
for (int64_t i = 0; i < 4000000; ++i) {
const int before = x.capacity();
x.push_back(0);
const int after = x.capacity();
if (before != after) {
if (find(pointer.begin(), pointer.end(), x.data()) == pointer.end()) {
pointer.push_back(x.data());
printf("new address on %lld\n", i);
}
times++;
}
}
printf("reallocate: %lu reuse: %lu\n", pointer.size(), times - pointer.size());
}
```
參考輸出：
* Visual C++
| Reallocation | Reuse | Data Size |
|--------------|-------|-----------|
| 31 | 8 | 8 bits |
| 33 | 6 | 16 bits |
| 34 | 5 | 32 bits |
| 35 | 4 | 64 bits |
| 36 | 3 | 128 bits |
* Mingw
| Reallocation | Reuse | Data Size |
|--------------|-------|-----------|
| 17 | 6 | 8 bits |
| 18 | 5 | 16 bits |
| 19 | 4 | 32 bits |
| 20 | 3 | 64 bits |
| 21 | 2 | 128 bits |
* GCC
| Reallocation | Reuse | Data Size |
|--------------|-------|-----------|
| 21 | 2 | 8 bits |
| 22 | 1 | 16 bits |
| 23 | 0 | 32 bits |
| 23 | 0 | 64 bits |
| 23 | 0 | 128 bits |
可以發現當 Data size 越小，記憶體重複利用的次數便會升高，印證了上方能利用越多 memory fragments 的假設。
且可以看到使用 Mingw 編譯時，在 capacity 增長為 4 -> 8, 256 -> 512, 1024 -> 2048 當中都不會重新分配空間，而就算再將 `push` 的個數增加也不會再出現利用分配過記憶體的情形，從這個數列可以推測，當 Vector 內資料越多，因硬體架構而產生的 memory fragments 就越難容納所需要的空間，所以重新利用空間的機率就越低。另外在 linux 系統下使用 GCC 測試，每次 Vector 重新分配的空間間距較接近 (可參考上方 Mingw 與 GCC 分配的記憶體空間間隔)，所以能重新利用的空間數比其他兩者更少。
而在 Visual C++ 當中，因為分配空間時的 growth factor 較小，再加上上面的分析，故重新利用記憶體的可能性就比較高，但相對地必須負擔頻繁 `reverse()` 所產生的效能。
所以在 [folly::fbvector](https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md) 中提到的無法重新利用以分配的空間，事實上只存在於當每次分配的空間皆為連續分配，但在實務上，作業系統並沒有保證每次分配的空間皆為連續的，故就算 growth factor 為 2，也能有機會利用到原先分配的記憶體空間，但與 growth factor 為 1.5 比較，可能性就較低。
> 引述 [nnethercote](https://github.com/servo/rust-smallvec/issues/80) 在 [rust-smallvec](https://github.com/servo/rust-smallvec) 中的回覆：
>
> I don't buy the argument that 1.5x is better, because "assuming all previous allocations are adjacent" features critically in the argument, and real allocators don't put allocations of varying sizes next to each other. 2x is simple and good.
關於 growth factor 還有許多討論：
* [Wikipedia](https://en.wikipedia.org/wiki/Dynamic_array#Growth_factor)
* [Rust](https://github.com/rust-lang/rust/issues/4961)
* [vector growth factor of 1.5](https://groups.google.com/g/comp.lang.c++.moderated/c/asH_VojWKJw)
在 [folly:fbvector](https://github.com/facebook/folly/blob/6ea76266cb268c9c1e83804a3f6e4168ff8c2a7c/folly/FBVector.h#L1151) 中也不是使用 1.5 來當作 growth factor，而是依照當前容量來決定：
```cpp
size_type computePushBackCapacity() const {
if (capacity() == 0) {
return std::max(64 / sizeof(T), size_type(1));
}
if (capacity() < folly::jemallocMinInPlaceExpandable / sizeof(T)) {
return capacity() * 2;
}
if (capacity() > 4096 * 32 / sizeof(T)) {
return capacity() * 2;
}
return (capacity() * 3 + 1) / 2;
}
```
#### 程式修改
對於作業說明中的 `ilog_factor(float n)` 可以加以改進：
$$
log_{1.5}(n)=\frac{log_2(n)}{log_2(1.5)}=\frac{log_2(n)}{log_2(3)-1}
$$
這樣便能先計算出 $log_2(3)$ 並利用 bitwise 運算及來快速求出 $log_{1.5}(n)$ 的值。
```c
#define FACTOR 1.5
#define CHUNK_SIZE 4
#define i_log3 1.58
static inline int ilog_factor(size_t n) /* log1.5(n) = log2(n)/log2(1.5)*/
{
return ilog2(n) / (i_log3 - 1);
}
```
而損失的精度是可以容忍的，因此函式是用於 `vec_reserve` 時分配的空間，並不影響程式正確性。
次方也能改為 bitwise 運算：
$$
1.5^n=(\frac{3}{2})^n=3^n>>n
$$
`vec_capacity` 與 `__vec_push_back` 做對應的修改：
```diff
#define vec_capacity(v) \
- (v.on_heap ? (size_t) 1 << v.capacity : sizeof(v.buf) / sizeof(v.buf[0]))
+ (v.on_heap ? (size_t) pow(3, v.capacity) >> v.capacity : \
+ sizeof(v.buf) / sizeof(v.buf[0]))
static NON_NULL void __vec_push_back(void *restrict vec,
void *restrict e,
size_t elemsize,
size_t capacity)
{
...
if (v->on_heap) {
if (v->size == capacity)
- v->ptr = realloc(v->ptr, elemsize * (size_t) 1 << ++v->capacity);
+ v->ptr = realloc(v->ptr, elemsize * (size_t) pow(3, ++v->capacity) >> v->capacity);
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else {
if (v->size == capacity) {
void *tmp =
- malloc(elemsize * (size_t) 1 << (v->capacity = capacity + 1));
+ malloc(elemsize * (size_t) pow(3, (v->capacity = capacity + 1)) >> v->capacity);
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else
memcpy(&v->buf[v->size++ * elemsize], e, elemsize);
}
}
```
但此實作還是有用到 `pow` 運算，較浪費效能，如果 `capacity` 直接儲存所需要的空間，增加空間時直接以 `capacity * 3 >> 1` 做運算較好，也較符合 [folly:fbvector::capacity()](https://github.com/facebook/folly/blob/6ea76266cb268c9c1e83804a3f6e4168ff8c2a7c/folly/FBVector.h#L935) 的做法。
#### `insert`
```c
#define vec_insert(v, p, e) \
__vec_insert(&v, &(__typeof__(v.buf[0])[]){e}, p, vec_elemsize(v), \
vec_capacity(v))
static NON_NULL void __vec_insert(void *restrict vec,
void *restrict e,
size_t position,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (position > v->size) { /* insert error */
return;
}
if (v->on_heap) {
if (v->size == capacity)
v->ptr = realloc(v->ptr, elemsize * (size_t) pow(3, ++v->capacity) >> v->capacity);
memmove(&v->ptr[(position + 1) * elemsize], &v->ptr[position * elemsize], (capacity - position) * elemsize);
memcpy(&v->ptr[position * elemsize], e, elemsize);
v->size++;
} else {
if (v->size == capacity) {
void *tmp =
malloc(elemsize * (size_t) pow(3, (v->capacity = capacity + 1)) >> v->capacity);
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
memmove(&v->ptr[(position + 1) * elemsize], &v->ptr[position * elemsize], (capacity - position) * elemsize);
memcpy(&v->ptr[position * elemsize], e, elemsize);
} else {
memmove(&v->ptr[(position + 1) * elemsize], &v->ptr[position * elemsize], (capacity - position) * elemsize);
memcpy(&v->ptr[position * elemsize], e, elemsize);
}
}
}
```
`p` 為要插入的位置，`e` 為要插入的元素。與 `vec_push` 類似，差別在於需要將插入的元素後方往後移一個位置，要注意的是必須使用 `memmove` 而非 `memcpy`，因為我們要移動的空間會有重疊的部份，而 `memcpy` 沒有保證在此情況下能正確執行。
#### `erase`
```c
#define vec_erase(v, p) \
__vec_erase(&v, p, vec_elemsize(v), \
vec_capacity(v))
static NON_NULL void __vec_erase(void *restrict vec,
size_t position,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (position > v->size) {
return;
}
memmove(&v->ptr[(position - 1) * elemsize], &v->ptr[position * elemsize], (capacity - position) * elemsize);
v->size--;
}
```
`vec_erase` 與 `vec_pop` 不同的地方一樣在於記憶體需要移動，因後續插入的元素會覆蓋原本尾端元素，故不需要特別做移除的動作。
## 測驗 2
:::spoiler 參考解答
#### `WWW = ?`
- [x] `(b) !cr_queue_empty(in)`
#### `LLL = ?`
- [x] `(d) !cr_queue_full(out)`
:::
### 運作原理
> [nc(1) - Linux man page](https://linux.die.net/man/1/nc)
>
> **-l** Used to specify that nc should listen for an incoming connection rather than initiate a connection to a remote host. It is an error to use this option in conjunction with the -p, -s, or -z options. Additionally, any timeouts specified with the -w option are ignored.
```
nc -l 127.0.0.1 1234 < /etc/lsb-release
```
將 `/etc/lsb-release` 的檔案內容傳到 port `1234` 上，也會接收從 port `1234` 傳來的資料。
```c=141
int main(int argc, char *argv[])
{
if (argc != 3) {
fprintf(stderr, "USAGE: %s <ip> <port>\n", argv[0]);
return 1;
}
char *host = argv[1];
int port = atoi(argv[2]);
int fd = socket(AF_INET, SOCK_STREAM, 0);
if (fd < 0) {
perror("socket()");
return 1;
}
if (nonblock(fd) < 0) {
perror("nonblock() socket");
return 1;
}
if (nonblock(STDIN_FILENO) < 0) {
perror("nonblock() stdin");
return 1;
}
if (nonblock(STDOUT_FILENO) < 0) {
perror("nonblock() stdout");
return 1;
}
struct sockaddr_in addr = {
.sin_family = AF_INET,
.sin_addr =
{
.s_addr = inet_addr(host),
},
.sin_port = htons(port),
};
connect(fd, (struct sockaddr *) &addr, sizeof(struct sockaddr_in));
struct cr cr_stdin = cr_init();
struct cr cr_socket_read = cr_init();
struct cr cr_socket_write = cr_init();
byte_queue_t queue = cr_queue_init();
while (cr_status(&cr_stdin) == CR_BLOCKED &&
cr_status(&cr_socket_read) == CR_BLOCKED) {
if (cr_queue_empty(&queue)) {
fd_set fds;
FD_ZERO(&fds);
FD_SET(STDIN_FILENO, &fds);
FD_SET(fd, &fds);
select(fd + 1, &fds, NULL, NULL, NULL);
}
socket_read_loop(&cr_socket_read, fd);
socket_write_loop(&cr_socket_write, fd, &queue);
stdin_loop(&cr_stdin, &queue);
}
close(fd);
return 0;
}
```
第 151 行利用 `socket()` 建立溝通的端點，`AF_INET` 指定使用伺服器端的通訊，`SOCK_STREAM` 以資料流的方式傳遞資料，最後一個參數設 0 讓 kernel 決定該使用的 protocol。
>[SOCKET(2)](https://man7.org/linux/man-pages/man2/socket.2.html)
>
>socket() creates an endpoint for communication and returns a file
descriptor that refers to that endpoint. The file descriptor
returned by a successful call will be the lowest-numbered file
descriptor not currently open for the process.
>
> AF_INET IPv4 Internet protocols
>
> SOCK_STREAM
Provides sequenced, reliable, two-way, connection-based
byte streams. An out-of-band data transmission mechanism
may be supported.
接著 `nonblock()` 函數將 socket、stdin、stdout 的 file descriptor 設定為 non blocking。
```c
static int nonblock(int fd)
{
int flags = fcntl(fd, F_GETFL, 0);
if (flags == -1)
return -1;
return fcntl(fd, F_SETFL, flags | O_NONBLOCK);
}
```
[`fcntl()`](https://man7.org/linux/man-pages/man2/fcntl.2.html) 為 Linux 中用來操控 file descriptor 的函數，透過 `F_GETFL` 取得 fd 的 flags，再利用 `F_SETFL` 設定 fd 的 flags，設定時將 `O_NONBLOCK` non blocking 新增到 flags 中。
利用 `sockaddr_in` 結構紀錄伺服端的資訊 (ip address, port)，再利用 [`connect()`](https://man7.org/linux/man-pages/man2/connect.2.html) 即完成與伺服端的連接。
```c
struct cr {
void *label;
int status;
void *local; /* private local storage */
};
```
紀錄 Coroutine 內資訊的結構。
```c
#define cr_init() \
{ \
.label = NULL, .status = CR_BLOCKED \
}
```
初始化 Coroutine 狀態。
```c
#define cr_begin(o) \
do { \
if ((o)->status == CR_FINISHED) \
return; \
if ((o)->label) \
goto *(o)->label; \
} while (0)
```
當 `struct cr` 已完成時，直接回傳；而 `label` 有紀錄時，則利用 `goto` 跳到上次中斷的地方。
```c
#define __cr_line3(name, line) _cr_##name##line
#define __cr_line2(name, line) __cr_line3(name, line)
#define __cr_line(name) __cr_line2(name, __LINE__)
#define cr_label(o, stat) \
do { \
(o)->status = (stat); \
__cr_line(label) : (o)->label = &&__cr_line(label); \
} while (0)
```
設定 `status` 並宣告一個 label，並將 `cr->label` 指向該位置。用於要退出函式前，紀錄當前運行到的位置。
`__LINE__` 回傳此程式碼在 source file 中所在的行數，`__cr_line` 將 label 名字與對應的行數組合成一獨立的字串。
```c
#define cr_end(o) cr_label(o, CR_FINISHED)
```
與 `cr_begin` 做對應，指示 Coroutine 結束，下次進入該函式時，經過 `cr_begin` 後便會跳到此位置。
```c
#define cr_status(o) (o)->status
```
回傳 `cr->status`。
```c
#define cr_wait(o, cond) \
do { \
cr_label(o, CR_BLOCKED); \
if (!(cond)) \
return; \
} while (0)
```
`cr_wait` 為當 Coroutine 需要等待事件發生時，先讓出 CPU 使用權給其他行程，每次進入此函式時，檢查 `cond` 是否成立，如果為否則跳出函式並繼續等待。
```c
#define cr_exit(o, stat) \
do { \
cr_label(o, stat); \
return; \
} while (0)
```
`cr_exit` 與 `cr_end` 相似，但前者能自行設定 `status`。
```c
#define cr_sys(o, call) \
cr_wait(o, (errno = 0) || !(((call) == -1) && \
(errno == EAGAIN || errno == EWOULDBLOCK || \
errno == EINPROGRESS || errno == EINTR)))
```
將 `cr_wait` 包裝，在做 `call` 的時候檢查是否產生錯誤。在運行時，因為 `||` 為 left associative，所以會先執行 `(errno = 0)`，而此表達式會回傳 0，導致 `||` 右方的表達式也會執行。而 `&&` 也為 left associative，故先執行完 `(call == -1)` 後，會在檢查 `errno` 是否被設置，進而判斷有無產生錯誤。
```c
#define cr_queue(T, size) \
struct { \
T buf[size]; \
size_t r, w; \
}
#define cr_queue_init() \
{ \
.r = 0, .w = 0 \
}
#define cr_queue_len(q) (sizeof((q)->buf) / sizeof((q)->buf[0]))
#define cr_queue_cap(q) ((q)->w - (q)->r)
#define cr_queue_empty(q) ((q)->w == (q)->r)
#define cr_queue_full(q) (cr_queue_cap(q) == cr_queue_len(q))
#define cr_queue_push(q, el) \
(!cr_queue_full(q) && ((q)->buf[(q)->w++ % cr_queue_len(q)] = (el), 1))
#define cr_queue_pop(q) \
(cr_queue_empty(q) ? NULL : &(q)->buf[(q)->r++ % cr_queue_len(q)])
```
```c
static void stdin_loop(struct cr *o, byte_queue_t *out)
{
static uint8_t b;
static int r;
cr_begin(o);
for (;;) {
cr_sys(o, r = read(STDIN_FILENO, &b, 1));
if (r == 0) {
cr_wait(o, cr_queue_empty(out));
cr_exit(o, 1);
}
cr_wait(o, LLL);
cr_queue_push(out, b);
}
cr_end(o);
}
static void socket_write_loop(struct cr *o, int fd, byte_queue_t *in)
{
static uint8_t *b;
cr_begin(o);
for (;;) {
cr_wait(o, WWW);
b = cr_queue_pop(in);
cr_sys(o, send(fd, b, 1, 0));
}
cr_end(o);
}
static void socket_read_loop(struct cr *o, int fd)
{
static uint8_t b;
static int r;
cr_begin(o);
for (;;) {
cr_sys(o, r = recv(fd, &b, 1, 0));
if (r == 0)
cr_exit(o, 1);
cr_sys(o, write(STDOUT_FILENO, &b, 1));
}
cr_end(o);
}
```
三個 Coroutine 主要函式：
* `stdin_loop` 從 standard input 中讀取資料，並將讀到的資料存入 queue 中
* `socket_write_loop` 從 queue 中讀出資料，並將讀到的資料送到 server 端
* `socket_read_loop` 從 server 端取得資料，並將讀到的資料送到 standard output
程式運行的關聯為下圖：
```graphviz
digraph ER{
node[shape=box];
stdin_loop;
socket_write_loop;
socket_read_loop;
"/etc/lsb-release";
"tinync.c"
{rank=same;stdin,stdout}
{rank=same;client,server}
stdin_loop->socket_write_loop[dir="forward", label="queue"];
"/etc/lsb-release"->server
server->socket_read_loop[dir="forward", label=" recv"];
"tinync.c"->stdin
socket_write_loop->server[dir="forward", label=" send"];
stdin->client[arrowhead=none]
stdout->client[arrowhead=none]
socket_read_loop->stdout[dir="forward", label=" write"];
stdin->stdin_loop[label=" read"]
}
```
而每個函式皆需要等待前一個函式的資料準備完成，故使用 Coroutine 達到等待並讓出 CPU 使用權的效果。
### 新增功能
```c
#define cr_restart(o) \
do { \
(o)->label = NULL; \
return; \
} while (0) \
#define cr_yield(o) \
do { \
(o)->label = &&__cr_line(label); \
return; \
__cr_line(label):; \
} while (0)
```
參考 [coroutine.h](https://in4lio.github.io/ev3dev-c/coroutine_8h_source) 實作 yield 以及 restart。
使用以下程式進行測試：
```c
void print_number_coro(struct cr *o)
{
static int first_time = 1;
static int i;
cr_begin(o);
for (i = 0; i < 10; ++i) {
if (i == 5)
cr_yield(o);
if (first_time && i == 9) {
first_time = 0;
cr_restart(o);
}
printf("%d\n", i);
}
cr_end(o);
}
int main(int argc, char *argv[])
{
struct cr cr_test = cr_init();
print_number_coro(&cr_test);
printf("yield\n");
print_number_coro(&cr_test);
printf("restart\n");
print_number_coro(&cr_test);
printf("yield\n");
print_number_coro(&cr_test);
}
```
預期輸出：
```
0
1
2
3
4
yield
6
7
8
restart
0
1
2
3
4
yield
6
7
8
9
```
要特別注意 `cr_restart` 不會重新初始化 `static` 變數，可以讓 `cr_restart` 接收一參數用以初始化：
```c
#define cr_restart(o, ...) \
do { \
(o)->label = NULL; \
__VA_ARGS__; \
return; \
} while (0) \
// test
cr_restart(o, i = 3);
```
###### tags: `linux2021`
Sign in with Wallet
Connect another wallet