# 2021q1 Homework5 (quiz5)
contributed by < [`WayneLin1992`](https://github.com/WayneLin1992) >
###### tags: `linux2021`
## 延伸問題
測驗1
- [x] 解釋上述程式運作的原理
- [x] 比照 第 3 週測驗題 進行效率分析
- [ ] 務必參照 [folly::fbvector](https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md) 文件和對應原始程式碼
- [x] 指出上述實作的限制並提出改進方案，
- [ ] 以上述程式為基礎，實作 vector 經典操作，如 insert 和 erase
## 測驗1
#### `STRUCT_BODY`
```cpp
#define STRUCT_BODY(type) \
struct { \
size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1, \
flag3 : 1; \
type *ptr; \
}
```
bit-field
`size` : 54 bits
`on_heap` : 1 bit
`capacity` : 6 bits
`flag1` : 1 bit
`flag2` : 1 bit
`flag3` : 1 bit
ptr: 資料若存放在 heap，ptr 用以紀錄起始位址。若存放在 stack，其起始位址為 buf 成員。
#### `NEXT_POWER_OF_2(s)`
```cpp
#define NEXT_POWER_OF_2(s) \
!(s & (s - 1)) ? s : (size_t) 1 << (64 - __builtin_clzl(s)) //VV1
```
將 next power of two 當 s 為 2 的冪，就回傳，下一個 2 的冪，但要注意 0 時會回傳什麼，有可能 0 或 64 。
**這邊之後可以改進留** `(size_t) 1 << (64 - __builtin_clzl(s))` 即可。
#### `v(t, s, name, ...)`
```cpp
#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])
```
觀察 main 部分 vector 宣告
```cpp
v(float, 3, vec1);
v(int, 2, vec2, 13, 42);
```
`_Static_assert` 在編譯前 會檢查 s <= 8
union 會在兩個結構中挑較大的空間當 `struct` 以結構來看 `filler` 和 `buf` 使用較大空間比 `STRUCT_BODY(t)` 大。
t 將會是 array 的 data type， s 為代入 power of two 的數值， name 為 vector 的名子， ... 為不定參數，避免超出設定 parameters 會出現的警告。
`name __attribute__` 為 auto free vector 。
`name.size` 為使用的空間
`(__typeof__(name.buf[0])` 將知道 vector 內存取的 data type 。
`name.capacity` 為容量，也就是最大使用空間為 2^n^ 中的 n。
`filler` 將保存 bit-field 的結構，避免被複寫到，所以要注意 size_t 在 windows 和 linux 都為 8 bytes ，觀察 bit-field 也剛好不超過 8 bytes 大小。
:::info
`__VA_ARGS__` 為 variadic macro
實驗
```cpp
#define debug1(format, ...) printf(format, __VA_ARGS__)
#define debug2(format, args ...) printf(format, args)
int main() {
debug1("Hello %s\n", "World");
debug2("Hello %s\n", "World");
}
```
>Hello World
Hello World
參考資料:
[Variadic macros](https://www.ibm.com/docs/en/xl-c-and-cpp-linux/13.1.5?topic=compatibility-variadic-macros)
:::
有此可以知道 `{.buf = {__VA_ARGS__}` 將 member 填入數值。
:::info
`__attribute__((cleanup()))` GCC extension 將會在程式結束時自動釋放記憶體。
實驗:檢查是否會自動 free vector 。
```shell
==2739== HEAP SUMMARY:
==2739== in use at exit: 0 bytes in 0 blocks
==2739== total heap usage: 3 allocs, 3 frees, 1,664 bytes allocated
==2739==
==2739== All heap blocks were freed -- no leaks are possible
```
當程式結束也成功將 vector 自動 free 掉。
:::
#### `vec_size`
`#define vec_size(v) v.size`
vector size 的 macro。
#### `vec_capacity`
```cpp
#define vec_capacity(v) \
(v.on_heap ? (size_t) 1 << v.capacity : sizeof(v.buf) / sizeof(v.buf[0]))
```
先判斷 heap 還是在 buf 中。
vector capacity 的 macro。
#### `vec_data`
`#define vec_data(v) (v.on_heap ? v.ptr : v.buf) /* always contiguous buffer */`
先判斷在 heap 還是 buf 中
vector data 的 macro。
#### `vec_elemsize`
`#define vec_elemsize(v) sizeof(v.buf[0])`
得到單位元素的大小，會對應到 data type。
#### `vec_pos`
`#define vec_pos(v, n) vec_data(v)[n] /* lvalue */`
位置所對應的 data 。
#### `vec_reserve`
```cpp
#define vec_reserve(v, n) __vec_reserve(&v, n, vec_elemsize(v), vec_capacity(v))
```
其中 `__vec_reserve` 為 linux 命名方式代表內部實作，而外部 `vec_reserve(v, n)` 進行操作，所以 `vec_reserve` ~~**為之後必須要實做的部分**~~
#### `vec_push_back`
```cpp
#define vec_push_back(v, e) \
__vec_push_back(&v, &(__typeof__(v.buf[0])[]){e}, vec_elemsize(v), \
vec_capacity(v))
```
其中 `__vec_push_back` 應該要在之後有實作
#### `vec_pop_back`
`#define vec_pop_back(v) (void) (v.size -= 1) // VV2`
直接 `size - 1` 來達到 pop 的實作
#### `__attribute__`
```cpp
/* This function attribute specifies function parameters that are not supposed
* to be null pointers. This enables the compiler to generate a warning on
* encountering such a parameter.
*/
#define NON_NULL __attribute__((nonnull))
```
`__attribute__((nonnull))` 代表不能空 parameters
#### `vec_free`
```cpp
static NON_NULL void vec_free(void *p)
{
STRUCT_BODY(void) *s = p;
if (s->on_heap)
free(s->ptr);
}
```
將 vec 所使用空間釋放出去
#### `ilog2`
```cpp
static inline int ilog2(size_t n)
{
return 64 - __builtin_clzl(n) - ((n & (n - 1)) == 0);
}
```
要注意 v.capacity 為位移數，不過這部分**可以修改成** `64 - __builtin_clzl(n)`
:::info
:bell: `64 - __builtin_clzl(n)` n 為 unsign long int 在 windows long int 為 4 bytes ， Linux long int 為 8 bytes ，所以 `NEXT_POWER_OF_2(s)` 也需要注意所使用的作業系統，這裡我改成 `__builtin_clzll(n)` 為 long long 的形式， long long 在 linux 及 windows 皆為 8 bytes。
參考資料:
[資料類型範圍](https://docs.microsoft.com/zh-tw/cpp/cpp/data-type-ranges?view=msvc-160)
[standard data type](https://www.ibm.com/docs/en/ibm-mq/9.0?topic=platforms-standard-data-types-unix-linux-windows)
:::
#### `__vec_reserve`
```cpp
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;
}
}
}
```
這 `__vec_reserve` 為上面 `vec_reserve` 的實作，跟記憶體要一個空間，存入 heap 當中。
要注意其中 v.capacity 為 2 的次方項，所以實際大小要在 shift 。
#### `__vec_push_back`
```cpp
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 == capacity)
v->ptr = realloc(v->ptr, elemsize * (size_t) 1 << ++v->capacity); //VV3
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else {
if (v->size == 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);
}
}
```
stack 和 heap 輸入的 capacity 不一樣，需要對應 vec_capacity() 才可以知道，這是需要注意的地方。
#### `display`
```cpp
#define display(v) \
do { \
for (size_t i = 0; i < vec_size(v); i++) \
printf("%.2f ", vec_pos(v, i)); \
puts(v.on_heap ? "heap" : "stack"); \
} while (0)
```
為顯示出結果， puts 將會自動換行，並顯示其中文字。
### 實際執行結果
>pos(vec2,0)=13, pos(vec2,1)=42
capacity(vec1)=4, capacity(vec2)=128
pos(vec2,2)=88
stack
0.00 stack
0.00 1.10 stack
0.00 1.10 2.20 stack
0.00 1.10 2.20 3.30 stack
0.00 1.10 2.20 3.30 4.40 heap
0.00 1.10 2.20 3.30 4.40 5.50 heap
0.00 1.10 2.20 3.30 4.40 heap
0.00 1.10 2.20 3.30 heap
0.00 1.10 2.20 heap
0.00 1.10 heap
0.00 heap
heap
## 進行效率分析
建立 C++ vector 並使用 gdb 觀察了解 C++ vector。
```cpp
vector<float> vec1;
cout << vec1.capacity() <<endl;
vector<int>vec2{13,42};
cout << vec2.capacity() <<endl;
vec2.push_back(88);
cout << vec2.size() <<endl;
cout << vec2.capacity() <<endl;
vec2.reserve(100);
cout << vec2.capacity() <<endl;
```
>0
>2
>3
>4
>100
觀察 gdb vector 在 `std::allocator<int>` 存取著字串位置 `_M_start 0x1c3ab0` `_M_finish 0x1c3abc` `_M_end_of_storage 0x1c3c40`
int 為 4 bytes 所以 start to finish 12 bytes 代表其中存入 3 int ， start to end_of_storage 400 bytes 代表 capacity 能存取 100 int。
而 &vec2 0x62fd30 有觀察較少元素時， `std::vector` 所存取的元素空間皆為 heap ，而且他的 capacity 的增加也是以 power of two 方式增加。
觀察所使用的記憶體
- [ ] [vector.c](https://github.com/WayneLin1992/linux2021_week5/blob/main/vector_test.c)
```shell
==2808== Command: ./vector_test_c
==2808==
==2808==
==2808== HEAP SUMMARY:
==2808== in use at exit: 0 bytes in 0 blocks
==2808== total heap usage: 1 allocs, 1 frees, 128 bytes allocated
==2808==
==2808== All heap blocks were freed -- no leaks are possible
```
- [ ] [vector.cpp](https://github.com/WayneLin1992/linux2021_week5/blob/main/vector_test.cpp)
```shell
==2439== Command: ./vector_test_cpp
==2439==
==2439==
==2439== HEAP SUMMARY:
==2439== in use at exit: 0 bytes in 0 blocks
==2439== total heap usage: 5 allocs, 5 frees, 72,764 bytes allocated
==2439==
==2439== All heap blocks were freed -- no leaks are possible
```
- [ ] vector.c
```shell
Performance counter stats for './vector_test_c' (6 runs):
16,218 cache-misses # 27.963 % of all cache refs ( +- 3.76% )
57,997 cache-references ( +- 3.87% )
681,050 instructions # 0.70 insn per cycle ( +- 0.59% )
977,904 cycles ( +- 6.95% )
14,311 L1-dcache-load-misses ( +- 5.30% )
0.0011930 +- 0.0000726 seconds time elapsed ( +- 6.09% )
```
- [ ] vector.cpp
```shell
Performance counter stats for './vector_test_cpp' (6 runs):
34,698 cache-misses # 23.614 % of all cache refs ( +- 1.73% )
146,935 cache-references ( +- 4.92% )
3,336,708 instructions # 1.22 insn per cycle ( +- 0.20% )
2,745,936 cycles ( +- 2.88% )
35,664 L1-dcache-load-misses ( +- 3.89% )
0.002739 +- 0.000136 seconds time elapsed ( +- 4.96% )
```
由上可以看到 `vector`: 128 bytes 比 `std::vector` : 72,764 bytes 較省空間， `std::vector` 中的 member 也比較多。
`vector` 在而且在 cache masses 和執行時間表現都較好。
### growth factor
```cpp
#define FACTOR 1.5
#define CHUNK_SIZE 4
static inline float ilog_factor(float n) /* log1.5(n) = log2(n)/log2(1.5)*/
{
return ceilf(log2f(n)/log2f(FACTOR));
}
```
除法的成本比乘法的成本高，所以可以將倒數直接算出來直接代入。
$\log_{2}{1.5}\approx0.584962$
$\frac{1}{\log_{2}{1.5}}\approx1.70951$
$\log_{1.5}{n}\approx 1.70951\log_{2}{n}$
```cpp
#define FACTOR 1.5
#define CHUNK_SIZE 4
static inline float ilog_factor_1(float n) /* log1.5(n) = 1.70951 * log2(n)*/
{
return ceilf(1.70951 * log2f(n));
}
```
當然還可以建立一個表格，照理會更快。
```cpp
static int ilog_factor_2(int n){
if (n <= 7) return 5;
if (n <= 11) return 6;
if (n <= 17) return 7;
if (n <= 25) return 8;
if (n <= 38) return 9;
if (n <= 57) return 10;
if (n <= 86) return 11;
if (n <= 129) return 12;
if (n <= 194) return 13;
if (n <= 291) return 14;
if (n <= 438) return 15;
if (n <= 656) return 16;
if (n <= 985) return 17;
if (n <= 1167) return 18;
}
```
:::info
[ilog2.c](https://github.com/WayneLin1992/linux2021_week5/blob/main/ilog2.c)
- [ ] ilog_factor
```shell
Performance counter stats for './ilog2' (6 runs):
17,433 cache-misses # 25.363 % of all cache refs ( +- 2.19% )
68,736 cache-references ( +- 2.88% )
803,296 instructions # 1.03 insn per cycle ( +- 0.63% )
780,131 cycles ( +- 2.87% )
17,986 L1-dcache-load-misses ( +- 4.74% )
0.0011077 +- 0.0000803 seconds time elapsed ( +- 7.25% )
```
- [ ] ilog_factor_1
```shell
Performance counter stats for './ilog2' (6 runs):
16,530 cache-misses # 24.642 % of all cache refs ( +- 2.48% )
67,080 cache-references ( +- 1.76% )
804,778 instructions # 1.01 insn per cycle ( +- 0.71% )
797,174 cycles ( +- 6.19% )
17,080 L1-dcache-load-misses ( +- 5.43% )
0.001101 +- 0.000108 seconds time elapsed ( +- 9.80% )
```
將除法改成乘法，在執行時間上有進展，但在指令方面也沒有比較輕鬆，可能是因為 float 的乘法也沒有很容易的關係。
- [ ] ilog_factor_2
```shell
Performance counter stats for './ilog2' (6 runs):
14,656 cache-misses # 26.664 % of all cache refs ( +- 1.73% )
54,964 cache-references ( +- 0.93% )
591,813 instructions # 1.01 insn per cycle ( +- 0.94% )
588,824 cycles ( +- 4.38% )
14,151 L1-dcache-load-misses ( +- 1.47% )
0.0008575 +- 0.0000759 seconds time elapsed ( +- 8.85% )
```
不管在指令數量還是執行時間都獲得提昇。
:::
#### vec_capacity 的修改
```cpp
#define vec_capacity(v) __vec_capacity(&v)
static size_t inline __vec_capacity(void *vec)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (v->on_heap)
return (size_t) (pow(1.5, v->capacity) * CHUNK_SIZE);
return CHUNK_SIZE;
}
```
```cpp
if (v->on_heap){
if(v->capacity == 0) return 4;
if(v->capacity == 1) return 6;
if(v->capacity == 2) return 9;
if(v->capacity == 3) return 13;
if(v->capacity == 4) return 20;
if(v->capacity == 5) return 30;
if(v->capacity == 6) return 45;
if(v->capacity == 7) return 68;
if(v->capacity == 8) return 102;
if(v->capacity == 9) return 153;
if(v->capacity == 10) return 230;
if(v->capacity == 11) return 345;
if(v->capacity == 12) return 518;
if(v->capacity == 13) return 778;
if(v->capacity == 14) return 1167;
return (size_t) (pow(1.5, v->capacity) * CHUNK_SIZE);
}
```
表格方面不需要把全部都建立起來，把最常使用的建立出來就能享受到效能上的優化。
調整後的結果
- [ ] [vector.h](https://github.com/WayneLin1992/linux2021_week5/blob/main/vector_ilog.h)
>pos(vec2,0)=13, pos(vec2,1)=42
capacity(vec1)=4, capacity(vec2)=102
pos(vec2,2)=88
stack
0.00 stack
0.00 1.10 stack
capacity(vec1)=4, capacity(vec2)=102
0.00 1.10 2.20 stack
0.00 1.10 2.20 3.30 stack
0.00 1.10 2.20 3.30 4.40 heap
0.00 1.10 2.20 3.30 4.40 5.50 heap
capacity(vec1)=6, capacity(vec2)=102
0.00 1.10 2.20 3.30 4.40 heap
0.00 1.10 2.20 3.30 heap
0.00 1.10 2.20 heap
0.00 1.10 heap
0.00 heap
heap
---
## 延伸問題
測驗2
- [x] 解釋上述程式運作的原理
- [x] 可搭配 Simon Tatham 的文章 [Coroutines in C](https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html) 來解讀
- [ ] 指出上述實作的限制並提出改進方案
- [ ] 學習 EV3 子計畫 Coroutines in C，在上述程式碼的基礎上
- [ ] 實作 yield 和 restart 一類經典 coroutine 操作
## 測驗2
nc 功能
nc 網路工具 necat 網路 檔案 連接
#### coroutine status
```cpp
/* coroutine status values */
enum {
CR_BLOCKED = 0,
CR_FINISHED = 1,
};
```
#### macro generate
```cpp
/* Helper macros to generate unique labels */
#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__)
```
` __LINE__` 為目前所在的行數
#### `struct cr`
```cpp
struct cr {
void *label;
int status;
void *local; /* private local storage */
};
```
`label` 要 goto 的 label
`status` 目前的狀態
`local`
#### `cr_init`
```cpp
#define cr_init() \
{ \
.label = NULL, .status = CR_BLOCKED \
}
```
將 cr 初始化。
#### `cr_begin`
```cpp
#define cr_begin(o) \
do { \
if ((o)->status == CR_FINISHED) \
return; \
if ((o)->label) \
goto *(o)->label; \
} while (0)
```
goto 達到 coroutine ， goto 將會跳至 label 。
do while 避免 dangling else 語意不清的情況
#### `cr_label`
```cpp
#define cr_label(o, stat) \
do { \
(o)->status = (stat); \
__cr_line(label) : (o)->label = &&__cr_line(label); \
} while (0)
```
設定 label 及 更新 status。
=&& labels as values 可以將 `__cr_line(label)` 地址存入 `(o)->label`
#### `cr_end`
`#define cr_end(o) cr_label(o, CR_FINISHED)`
end 時，更新 statues
#### `cr_status`
`#define cr_status(o) (o)->status`
表示出 status 。
#### `cr_wait`
```cpp
#define cr_wait(o, cond) \
do { \
cr_label(o, CR_BLOCKED); \
if (!(cond)) \
return; \
} while (0)
```
當 cond 時就需要 wait。
#### `cr_exit`
```cpp
#define cr_exit(o, stat) \
do { \
cr_label(o, stat); \
return; \
} while (0)
```
cr_exit 由設定 cr_label 來實作。
#### `cr_queue`
```cpp
#define cr_queue(T, size) \
struct { \
T buf[size]; \
size_t r, w; \
}
```
cr_queue struct queue
#### `cr_queue_init`
```cpp
#define cr_queue_init() \
{ \
.r = 0, .w = 0 \
}
```
初始化 queue
#### `cr_queue_xx`
```cpp
#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)])
```
queue 的基本操作，而且是 circular queue 只需要移動 r w 指標來控制開頭及結尾。
#### `cr_sys`
```cpp
/* Wrap system calls and other functions that return -1 and set errno */
#define cr_sys(o, call) \
cr_wait(o, (errno = 0) || !(((call) == -1) && \
(errno == EAGAIN || errno == EWOULDBLOCK || \
errno == EINPROGRESS || errno == EINTR)))
```
system call
`EAGAIN` 代表資源短暫被使用中 `EWOULDBLOCK` 壅塞 `EINPROGRESS` 正在被使用中 `EINTR` 中斷 function call
由 `cr_wait` 來作
#### `byte_queue_t`
`typedef cr_queue(uint8_t, 4096) byte_queue_t;`
其中 _t 為 typedef 命名法。
queue 其中能存取 4096 type 為 uint8_t
#### `stdin_loop`
```cpp
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, !cr_queue_full(out)); //LLL
cr_queue_push(out, b);
}
cr_end(o);
}
```
由 macro cr_wait 來達到 coroutine queue in
`ssize_t read(int fildes, void *buf, size_t nbyte)`
>`fildes` 要讀取的 File descriptor `buf` 緩衝區 `nbyte` 要讀取的 bytes
:::info
資料來源:
[read](https://man7.org/linux/man-pages/man2/read.2.html)
:::
#### `socket_write_loop`
```cpp
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, !cr_queue_empty(in)); //www
b = cr_queue_pop(in);
cr_sys(o, send(fd, b, 1, 0));
}
cr_end(o);
}
```
queue pop
`ssize_t send(int sockfd, const void *buf, size_t len, int flags);`
>The send() call may be used only when the socket is in a
>connected state (so that the intended recipient is known). The
only difference between send() and write(2) is the presence of
flags.
>將 fb 寫入 b 當中。
:::info
資料來源:
[send](https://man7.org/linux/man-pages/man2/send.2.html)
:::
#### `socket_read_loop`
```cpp
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);
}
```
recv : 從 socket 接收訊息
`ssize_t recv(int sockfd, void *buf, size_t len, int flags);`
>They may be used to receive data on both
connectionless and connection-oriented sockets. This page first
describes common features of all three system calls, and then
describes the differences between the calls.
The only difference between recv() and read(2) is the presence of
flags. With a zero flags argument, recv() is generally
equivalent to read(2) (but see NOTES).
>socket_descriptor
(Input) The socket descriptor that is to be read from.
buffer
(Input) The pointer to the buffer in which the data that is to be read is stored.
buffer_length
(Input) The length of the buffer.
`ssize_t write(int fd, const void *buf, size_t count);`
write : write to a file descriptor
>STDOUT_FILENO 標準輸入至 &b
:::info
資料來源:
[recv](https://man7.org/linux/man-pages/man2/recv.2.html)
[recv ibm](https://www.ibm.com/docs/en/i/7.4?topic=ssw_ibm_i_74/apis/recv.htm)
[write](https://man7.org/linux/man-pages/man2/write.2.html)
[STDOUT_FILENO](https://www.quora.com/What-is-the-file-descriptor-What-are-STDIN_FILENO-STDOUT_FILENO-and-STDERR_FILENO)
:::
由此可以知道 recv 與 read 相似，send 與 write 相似，差別就是有 flag 的設立，但這裡都設為0。
#### `nonblock`
```cpp
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` 操作 File descriptor
>`F_SETFL` 為設定檔案狀態
`arg` 為 `O_NONBLOCK` 由 `F_SETFL` 設定 `O_NONBLOCK` 為 no delay。
`return` 成功將回傳 -1 以外的值。
:::info
資料來源:
[fcntl](https://man7.org/linux/man-pages/man2/fcntl.2.html)
[fcntl ibm](https://www.ibm.com/docs/en/aix/7.2?topic=f-fcntl-dup-dup2-subroutine)
:::
#### `main`
```cpp
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;
}
```
```cpp
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);
}
```
`int fd = socket(AF_INET, SOCK_STREAM, 0);`
`int socket(int *domain, int type, int protocol);`
>The socket() function creates an endpoint for communication and returns a socket descriptor representing the endpoint. Different types of sockets provide different communication services.
domain
The address domain requested, either AF_INET, AF_INET6, AF_UNIX, or AF_RAW.
type
The type of socket created, either SOCK_STREAM, SOCK_DGRAM, or SOCK_RAW.
protocol
The protocol requested. Some possible values are 0, IPPROTO_UDP, or IPPROTO_TCP.
:::info
資料來源:
[socket](https://www.ibm.com/docs/en/zos/2.1.0?topic=functions-socket-create-socket)
:::
當 `cr_status` == `CR_BLOCKED` 為 0 ， `cr_queue_init()` `.r = 0, .w = 0`
FD_SET This function adds a file descriptor to a file descriptor set
>`FD_SET(STDIN_FILENO, &fds);` 將 `STDIN_FILENO` 加入 fds
`FD_SET(fd, &fds);` 將 fd 加入 fds
Select 監視 socket looking for sockets ready for reading, writing or pending
>`int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds,
struct timeval *timeout)`
`int nfds`The number of socket descriptors to be checked.This value should be one greater than the greatest number of sockets to be checked. 所以 fd + 1 。
`fd_set *readfds` Points to a bit set of descriptors to check for reading
:::info
資料來源:
[FD_SET](https://linux.die.net/man/3/fd_set)
[FD_SET](https://www.ibm.com/docs/en/ztpf/2020?topic=apis-fd-setadd-file-descriptor-file-descriptor-set)
:::
### 解讀 [Coroutines in C](https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html)
C 語言，由 stack 的方式，呼叫及返回，由 The Art of Computer Programming Donald Knuth 的想法，可以透過非 stack 的方式來完成 coroutine ，可以透過 goto 來轉移至程式的位置方式達到，可以使用下列方式來存取要 goto 的行數
```cpp
#define crReturn(x) do { state=__LINE__; return x; \
case __LINE__:; } while (0)
```
### 提出需要改進的地方
應該在 loop 中增加 goto 使其中能夠讀一個寫一個方式進行。
可以在 `socket_read_loop` 及 `socket_write_loop` 中增加 `cr_wait` 使他能夠跳出這迴圈 function 。
使用 gdb 觀察是否能如預期 yield 出資源出來。
:::info
由 switch case 來達到 coroutine
- [ ] [cortest.c](https://github.com/WayneLin1992/linux2021_week5/blob/main/cortest.c)
```cpp
#define cr_start() \
int __s = 0; \
switch(__s){ \
case 0:
#define cr_yield{ \
__s = __LINE__;\
usleep(THREAD_INTERVAL); \
return; \
case __LINE__:; \
}
#define cr_end() \
} \
__s = 0;
```
因此可以得出 yield 能成功跳出迴圈，就是因為有 return 在 macro 當中，可以注意到 yield end 都被包在 switch case 當中。
參考資料:
[使用 coroutine 實做 user-level thread](http://blog.linux.org.tw/~jserv/archives/001848.html)
:::
Sign in with Wallet
Connect another wallet