# [2021q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 5 週測驗題
###### tags: `linux2021`
:::info
目的: 檢驗學員對 **[bitwise operation](https://hackmd.io/@sysprog/c-bitwise)**, **[bit-field](https://hackmd.io/@sysprog/c-bitfield)**, **[C 語言：記憶體管理](https://hackmd.io/@sysprog/c-memory)**, **small string/buffer optimization**, **[coroutine](https://en.wikipedia.org/wiki/Coroutine)** 的認知
:::
==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSed45lVa_TWWQqvEeXsxvO1y3YPfLv3Ap6so3gJuj6bshYjZA/viewform)==
### 測驗 `1`
考慮到一個針對空間處理最佳化的 vector 實作
支援以下操作:
* `vec_push_back` : 新增元素至 vector 的尾端，必要時會進行記憶體配置;
* `vec_pop_back()` : 刪除 vector 最尾端的元素;
每個 vector 都有兩個重要的屬性:
* 容量 (capacity) : 是這個 vector 擁有的空間。
* 長度 (size): 實際儲存了元素的空間大小。capacity 永遠不小於 size
使用示範:
```cpp
int main()
{
v(float, 3, vec1);
v(int, 2, vec2, 13, 42);
printf("pos(vec2,0)=%d, pos(vec2,1)=%d\n", vec_pos(vec2, 0),
vec_pos(vec2, 1));
vec_push_back(vec2, 88);
vec_reserve(vec2, 100);
printf("capacity(vec1)=%zu, capacity(vec2)=%zu\n", vec_capacity(vec1),
vec_capacity(vec2));
printf("pos(vec2,2)=%d\n", vec_pos(vec2, 2));
#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)
display(vec1);
vec_push_back(vec1, 0.0);
display(vec1);
vec_push_back(vec1, 1.1);
display(vec1);
vec_push_back(vec1, 2.2);
display(vec1);
vec_push_back(vec1, 3.3);
display(vec1);
vec_push_back(vec1, 4.4);
display(vec1);
vec_push_back(vec1, 5.5);
display(vec1);
vec_pop_back(vec1);
display(vec1);
vec_pop_back(vec1);
display(vec1);
vec_pop_back(vec1);
display(vec1);
vec_pop_back(vec1);
display(vec1);
vec_pop_back(vec1);
display(vec1);
vec_pop_back(vec1);
display(vec1);
return 0;
}
```
預期輸出:
```
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
```
`STRUCT_BODY` 與 `v` 巨集實作 [C++ vector (STL)](https://zh.wikipedia.org/wiki/Vector_(STL)) 雛形。
* `STRUCT_BODY`: 紀錄 metadata 與存放資料的起始位址。
* `size`: 紀錄 vector 已存放的資料個數。
* `on_heap`: vector 的資料是否存放在 `heap`。
* `capacity`: vector 可容納資料的總個數。
* `ptr`: 資料若存放在 `heap`，`ptr` 用以紀錄起始位址。若存放在 `stack`，其起始位址為 `buf` 成員。
* `v`: 此巨集宣告一個新 vector 變數。由於，vector 存放的資料有可能會在 `heap`，因此需要一個機制將分配到的記憶體空間釋放，進而避免 `memory leak`。所以當 vector 變數不在宣告此變數的作用範圍 (scope) 內 (譬如: 在某一函式宣告 vector 變數，當此函式程式執行完畢準備返回時)，可使用 GNU extension [cleanup](https://gcc.gnu.org/onlinedocs/gcc/Common-Variable-Attributes.html) 屬性自行定義 `cleanup function` 用以釋放記憶體空間。
* 使用 `v` 宣告新的 vector 變數，其資料預設存放空間位於 `stack` 。當使用 `vec_push_back` 或 `vec_reserve`，如有需要擴充 vector capacity大小，則使用 `malloc` 配置記憶體空間 (也就是存放空間改為 `heap`)。
本體的實作程式如下:
```cpp
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* vector with small buffer optimization */
#define STRUCT_BODY(type) \
struct { \
size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1, \
flag3 : 1; \
type *ptr; \
}
#define NEXT_POWER_OF_2(s) \
VV1 ? s : (size_t) 1 << (64 - __builtin_clzl(s))
#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])
#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) (VV2)
/* 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))
static NON_NULL void vec_free(void *p)
{
STRUCT_BODY(void) *s = p;
if (s->on_heap)
free(s->ptr);
}
static inline int ilog2(size_t n)
{
return 64 - __builtin_clzl(n) - ((n & (n - 1)) == 0);
}
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;
}
}
}
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, 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);
}
}
```
請補完程式碼，使其執行符合預期。
> 參閱 [你所不知道的C語言：技巧篇](https://hackmd.io/@sysprog/c-trick) 以得知 GCC extension: attribute cleanup 使用技巧。
[folly::fbvector](https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md) 提到配置動態記憶體大小使用的 growth factor 會影響效能，其中 2 是一個不建議的數值，因為任何新配置的記憶體大小一定會大於之前配置過的記憶體的總和，造成 vector 無法重新利用曾經配置的空間。這點可以由下式驗證，例如欲配置的空間大小是 $2^4$ 時，過去已配置的空間總和是 $2^5 - 1$
$$
2^0 + 2^1 + 2^2 + 2^3 + ... 2^n = 2^{n+1} - 1
$$
以下嘗試設定 `1.5` 作為 growth factor，以資料筆數做為計算的依據，而非使用實際配置的記憶體空間，考量點：
* 不是每個數字都適合成為記憶體大小，例如說 91 bytes
* 可以用一套一樣的邏輯管理不同資料型態的 vector
* 程式碼的更動比較少
在實做更動以前，須先完成相關的輔助函式
```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));
}
```
> :warning: 這份實作程式碼的執行成本相當高，應予以改進
* 根據容量計算最接近的 capacity 比較麻煩，無法像以 2 為底進行計算時單純使用 bitwise shift
* 根據 $log_{1.5}(n) = \frac{log_{2}(n)}{log_{2}(1.5)}$ 進行計算，並嘗試全部都用標準函式庫來實作
* 最大可用資料數量為 $chunk\ size\times1.5^{capacity}$ (我選定的初始 chunk size 為 4 筆資料)
```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;
}
```
以 `CHUNK_SIZE = 4` `FACTOR = 1.5` 為例，修改後的資料筆數會以如下方式成長
```
4 6 9 13 20 30 45 ...
```
==作答區==
VV1 = ?
* `(a)` `s`
* `(b)` `s - 1`
* `(c)` `s & (s - 1)`
* `(d)` `(s & (s - 1))`
* `(e)` `!(s & (s - 1))`
VV2 = ?
* `(a)` `v.size -= 1`
* `(b)` `v.capacity--`
VV3 = ?
* `(a)` `(size_t) 1 << ++v->capacity`
* `(b)` `elemsize * (size_t) 1 << ++v->capacity`
* `(c)` `elemsize`
* `(d)` `elemsize + (size_t) 1 << ++v->capacity`
:::success
延伸問題:
1. 解釋上述程式運作的原理，比照 [第 3 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz3) 進行效率分析;
2. 指出上述實作的限制並提出改進方案，務必參照 [folly::fbvector](https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md) 文件和對應原始程式碼
3. 以上述程式為基礎，實作 vector 經典操作，如 insert 和 erase
:::
---
### 測驗 `2`
Donald E. Knuth 的經典著作《The Art of Computer Programming》提到 [coroutine](https://en.wikipedia.org/wiki/Coroutine) 這個自 1960 年代即現身的程式交錯執行技巧。[nc](https://linux.die.net/man/1/nc) 是個泛 UNIX 系統的工具程式，可用來檢測網路連線，詳見 [nc: 網路管理者工具實用範例](https://blog.gtwang.org/linux/linux-utility-netcat-examples/)。我們嘗試透過 [coroutine](https://en.wikipedia.org/wiki/Coroutine) 來實作精簡的 [nc](https://linux.die.net/man/1/nc) 命令。GCC 針對 C 語言進行擴充，提供 [Labels as Values](https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html)，因此我們能取得 label 的地址並透過 `goto` 敘述跳躍到指定的 label，從而落實 [coroutine](https://en.wikipedia.org/wiki/Coroutine)。
> 搭配閱讀 [你所不知道的C語言: goto 和流程控制篇](https://hackmd.io/@sysprog/c-control-flow)
以下是實作程式碼: (檔名: `tinync.c`)
```cpp
#include <stddef.h>
/* coroutine status values */
enum {
CR_BLOCKED = 0,
CR_FINISHED = 1,
};
/* 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__)
struct cr {
void *label;
int status;
void *local; /* private local storage */
};
#define cr_init() \
{ \
.label = NULL, .status = CR_BLOCKED \
}
#define cr_begin(o) \
do { \
if ((o)->status == CR_FINISHED) \
return; \
if ((o)->label) \
goto *(o)->label; \
} while (0)
#define cr_label(o, stat) \
do { \
(o)->status = (stat); \
__cr_line(label) : (o)->label = &&__cr_line(label); \
} while (0)
#define cr_end(o) cr_label(o, CR_FINISHED)
#define cr_status(o) (o)->status
#define cr_wait(o, cond) \
do { \
cr_label(o, CR_BLOCKED); \
if (!(cond)) \
return; \
} while (0)
#define cr_exit(o, stat) \
do { \
cr_label(o, stat); \
return; \
} while (0)
#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)])
/* 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)))
#include <arpa/inet.h>
#include <errno.h>
#include <fcntl.h>
#include <netinet/in.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/select.h>
#include <sys/socket.h>
#include <unistd.h>
typedef cr_queue(uint8_t, 4096) byte_queue_t;
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);
}
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);
}
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;
}
```
測試方式為，建立兩個終端機視窗，為了方便後面描述，我們分別稱為 `T1` 和 `T2`。首先在 `T1` 終端機執行以下命令: (在 GNU/Linux 作業系統中)
```shell
nc -l 127.0.0.1 1234 < /etc/lsb-release
```
在 `T2` 終端機執行:
```shell
./tinync 127.0.0.1 1234 < tinync.c
```
這時會在 `T1` 終端機看到 `tinync.c` 檔案內容，而在 `T2` 終端機看到 `/etc/lsb-release` 檔案內容。
請補完程式碼，使其符合預期地運作。
==作答區==
WWW = ?
* `(a)` `cr_queue_empty(in)`
* `(b)` `!cr_queue_empty(in)`
* `(c)` `cr_queue_full(in)`
* `(d)` `!cr_queue_full(in)`
LLL = ?
* `(a)` `cr_queue_empty(out)`
* `(b)` `!cr_queue_empty(out)`
* `(c)` `cr_queue_full(out)`
* `(d)` `!cr_queue_full(out)`
:::success
延伸問題:
1. 解釋上述程式運作的原理，可搭配 Simon Tatham 的文章 [Coroutines in C](https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html) 來解讀
2. 指出上述實作的限制並提出改進方案
3. 學習 EV3 子計畫 [Coroutines in C](https://in4lio.github.io/ev3dev-c/group__coro.html)，在上述程式碼的基礎上，實作 yield 和 restart 一類經典 [coroutine](https://en.wikipedia.org/wiki/Coroutine) 操作
:::
---
Sign in with Wallet
Connect another wallet