2021q1 Homework5 (quiz5)

contributed by < hankluo6 >

第 5 週測驗題

測驗 1

參考解答

VV1 = ?

• (e) !(s & (s - 1))

VV2 = ?

• (a) v.size -= 1

VV3 = ?

• (b) elemsize * (size_t) 1 << ++v->capacity

運作原理

#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 * 的指標指向真正存放資料的位置。

#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 實現。

2 ~ 3 行檢查大小是否小於 8，並宣告一個 union，內部 structure 的前 64 bits 存放 Vector 資訊，在第二個 struct 中用 filler 防止覆蓋資料，而 Vector 真正的資料則存在 buf 中。當資料需要存放在 heap 時，改以 ptr 紀錄其位置。宣告的 union 使用 GCC 的 cleanup attribute 來達成自動回收的機制，並將初始值賦值給 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 行為計算陣列宣告的大小。

#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.

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 變數。

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 重新分配空間。

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 內提到 growth factor 為 2 時產生的問題來改進。當 growth factor = 2 時，假設 vector 初始 capacity 為 1，則第 n 次的 reallocation 必須產生

$2^n$ 大小的空間，而先前產生的總空間為

$2^0+2^1+\cdots +2^{n-1}=2^n-1$，這使得新分配的空間不能使用之前已經分配的空間，而是必須重新尋找一塊

$2^n$ 大小的空間來使用。

growth factor 在 C++ 中為 implementation define，我們可以透過不同編譯器的實作來觀察 growth factor 對 Vector 的影響。

使用以下程式碼測試：

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++ 便沒有利用到重覆的記憶體空間。

這邊測試中 Vector 內的 type 設定為 64 bits integer，這是為了要對應 64 位元電腦的資料對齊，假如使用大小相對較小的型別 (如 char)，則 OS 為了要對齊資料，Vector 中兩次的 reallocation 一樣會產生間隔，此時，因 Vector 內的 data 所需要的資料空間較小，便能更有效利用這些 memory fragments，所以記憶體重複利用的機會便會升高。

你所不知道的 C 語言：記憶體管理、對齊及硬體特性

使用以下程式碼測試：

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 中提到的無法重新利用以分配的空間，事實上只存在於當每次分配的空間皆為連續分配，但在實務上，作業系統並沒有保證每次分配的空間皆為連續的，故就算 growth factor 為 2，也能有機會利用到原先分配的記憶體空間，但與 growth factor 為 1.5 比較，可能性就較低。

引述 nnethercote 在 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
• Rust
• vector growth factor of 1.5

在 folly:fbvector 中也不是使用 1.5 來當作 growth factor，而是依照當前容量來決定：

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) 可以加以改進：

$$lo{g}_{1.5}(n)=\frac{lo{g}_2(n)}{lo{g}_2(1.5)}=\frac{lo{g}_2(n)}{lo{g}_2(3)-1}$$
這樣便能先計算出

$lo{g}_2(3)$ 並利用 bitwise 運算及來快速求出

$lo{g}_{1.5}(n)$ 的值。

#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 做對應的修改：

#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() 的做法。

insert

#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

#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

參考解答

WWW = ?

• (b) !cr_queue_empty(in)

LLL = ?

• (d) !cr_queue_full(out)

運作原理

nc(1) - Linux man page

-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 傳來的資料。

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)

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。

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() 為 Linux 中用來操控 file descriptor 的函數，透過 F_GETFL 取得 fd 的 flags，再利用 F_SETFL 設定 fd 的 flags，設定時將 O_NONBLOCK non blocking 新增到 flags 中。

利用 sockaddr_in 結構紀錄伺服端的資訊 (ip address, port)，再利用 connect() 即完成與伺服端的連接。

struct cr {
    void *label;
    int status;
    void *local; /* private local storage */
};

紀錄 Coroutine 內資訊的結構。

#define cr_init()                           \
    {                                       \
        .label = NULL, .status = CR_BLOCKED \
    }

初始化 Coroutine 狀態。

#define cr_begin(o)                     \
    do {                                \
        if ((o)->status == CR_FINISHED) \
            return;                     \
        if ((o)->label)                 \
            goto *(o)->label;           \
    } while (0)

當 struct cr 已完成時，直接回傳；而 label 有紀錄時，則利用 goto 跳到上次中斷的地方。

#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 名字與對應的行數組合成一獨立的字串。

#define cr_end(o) cr_label(o, CR_FINISHED)

與 cr_begin 做對應，指示 Coroutine 結束，下次進入該函式時，經過 cr_begin 後便會跳到此位置。

#define cr_status(o) (o)->status

回傳 cr->status。

#define cr_wait(o, cond)         \
    do {                         \
        cr_label(o, CR_BLOCKED); \
        if (!(cond))             \
            return;              \
    } while (0)

cr_wait 為當 Coroutine 需要等待事件發生時，先讓出 CPU 使用權給其他行程，每次進入此函式時，檢查 cond 是否成立，如果為否則跳出函式並繼續等待。

#define cr_exit(o, stat)   \
    do {                   \
        cr_label(o, stat); \
        return;            \
    } while (0)

cr_exit 與 cr_end 相似，但前者能自行設定 status。

#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 是否被設置，進而判斷有無產生錯誤。

#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)])

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

程式運行的關聯為下圖：

而每個函式皆需要等待前一個函式的資料準備完成，故使用 Coroutine 達到等待並讓出 CPU 使用權的效果。

新增功能

#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 實作 yield 以及 restart。

使用以下程式進行測試：

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 接收一參數用以初始化：

#define cr_restart(o, ...)         \
    do {                           \
        (o)->label = NULL;         \
        __VA_ARGS__;               \
        return;                    \
    } while (0)                    \

// test
cr_restart(o, i = 3);

tags: linux2021