# 2020q1 Homework1 (lab0)
contributed by < `zxcvbnm04987` >
## 環境
```shell
$ uname -a
Linux kali 5.4.0-kali3-amd64 #1 SMP Debian 5.4.13-1kali1 (2020-01-20) x86_64 GNU/Linux
$ gcc --version | head -n 1
gcc (Debian 9.2.1-28) 9.2.1 20200203
```
## 補完 queue.[ch]
* [`queue_t`](#queue_t): queue 物件型別
* [`q_new`](#q_new): 建立新的 empty queue
* [`q_free`](#q_free): 釋放 queue 所佔用的記憶體
* [`q_insert_head`](#q_insert_head): 在 queue 的 head 插入給定的新元素
* [`q_insert_tail`](#q_insert_tail): 在 queue 的 tail 插入給定的新元素
* [`q_remove_head`](#q_remove_head): 在 queue 的 head 移除給定的元素
* [`q_size`](#q_size): 計算 queue 中的元素數量
* [`q_reverse`](#q_reverse): 以反向順序重新排列 linked list
* [`q_sort`](#q_sort): 以遞增順序來排序 linked list 的元素
### queue_t
```cpp
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int len; /* Length of the queue */
} queue_t;
```
新增 `tail` 紀錄 queue 的尾端讓 `q_insert_tail` 的時間複雜度可以達到 $O(1)$
### q_new
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return NULL;
q->head = q->tail = NULL;
q->len = 0;
return q;
}
```
加上 `if` 來避免在 malloc 無法配置記憶體並回傳 NULL 時初始化 queue 的 member data 而造成 Segmentation fault。
### q_remove_head
在 `q_remove_head` 的註解中提到：
> If sp is non-NULL and an element is removed, copy the removed string to *sp
> (up to a maximum of bufsize-1 characters, plus a null terminator.)
因此可以使用 `<string.h>` 中的 `strcpy` 函式。
但在[作業說明](https://hackmd.io/JSFDnHn0Rpe0V7d-AqLAXA?view#-%E6%94%B9%E5%AF%AB%E8%87%AA-CMU-%E8%A8%88%E7%AE%97%E6%A9%9F%E6%A6%82%E8%AB%96%E7%9A%84%E4%BD%9C%E6%A5%AD)中有提到：
> 依據 CERN [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml) 建議而移除 gets / sprintf / strcpy 等不安全的函式;
將 `strcpy` 刪除並改為使用 `strlcpy` 並得到以下程式碼
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
list_ele_t *tmp;
if (!q || !q->head)
return false;
if (sp)
strlcpy(sp, q->head->value, bufsize);
tmp = q->head;
q->head = q->head->next;
if (tmp == p->tail)
q->tail = NULL;
free(tmp->value);
free(tmp);
return true;
}
```
執行測試：
```shell
$ make test
CC queue.o
queue.c: In function ‘q_remove_head’:
queue.c:82:9: error: implicit declaration of function ‘strlcpy’; did you mean ‘strncpy’? [-Werror=implicit-function-declaration]
82 | strlcpy(sp, q->head->value, bufsize);
| ^~~~~~~
| strncpy
cc1: all warnings being treated as errors
make: *** [Makefile:39: queue.o] Error 1
```
出現 Compile error ，錯誤訊息顯示沒有 `strlcpy` 函式，後來發現 [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml) 中有提到：
> The best way to mitigate this issue is to use strlcpy if it is readily available (which is only the case on BSD systems)
`strlcpy` 只在 BSD 系統中才有，不過可以利用 macro 來定義 `strlcpy`
加入以下 macro 後便可以成功編譯及測試：
```cpp
#ifndef strlcpy
#define strlcpy(dst,src,sz) snprintf((dst), (sz), "%s", (src))
#endif
```
### q_free
```cpp
void q_free(queue_t *q)
{
if (!q)
return;
/* Free the list elements and the strings */
while (q_remove_head(q, NULL, 0))
;
/* Free queue structure */
free(q);
}
```
`q_remove_head` 註解中提到：
> Return true if successful.
> Return false if queue is NULL or empty.
因此可以利用此特性來簡化 `while` 迴圈的程式碼。
### q_insert_head
```cpp
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
if (!q)
return false;
/* Allocate space for new head */
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
/* Allocate space for string */
int len = strlen(s) + 1; // Including the terminating '\x00'
newh->value = malloc(len);
if (!newh->value) {
free(newh);
return false;
}
strlcpy(newh->value, s, len);
/* Link elements */
if (!q->tail)
q->tail = newh;
newh->next = q->head;
q->head = newh;
++q->len;
return true;
}
```
### q_insert_tail
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newt;
int len;
if (!q)
return false;
/* Allocate space for new tail */
newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;
/* Allocate space for string */
len = strlen(s) + 1; // Including terminating '\x00'
newt->value = malloc(len);
if (!newt->value) {
free(newt);
return false;
}
strlcpy(newt->value, s, len);
/* Link elements */
newt->next = NULL;
if (!q->head) // When q->head equals to NULL, q->tail must equals to NULL
q->head = newt;
else
q->tail->next = newt;
q->tail = newt;
++q->len;
return true;
}
```
`q_insert_head` 以及 `q_insert_tail` 兩者的作法非常相似，都需要判斷 `q` 是否為 empty queue，以及 `malloc()` 是否成功分配空間。
而時間複雜度也因為在 [`queue_t`](#queue_t) 中新增的 `tail` 變數而有辦法達到 $O(1)$ 。
### q_size
```cpp
int q_size(queue_t *q)
{
if (!q || !q->head)
return 0;
return q->len;
}
```
因為 [`queue_t`](#queue_t) 新增了代表 queue 長度的變數 `len` 而達到 $O(1)$ 的複雜度。
### q_reverse
```cpp
void q_reverse(queue_t *q)
{
if (!q || !q->head)
return;
q->tail = q->head;
list_ele_t *l, *r;
l = NULL;
do {
r = l;
l = q->head;
q->head = q->head->next;
l->next = r;
} while (q->head);
q->head = l;
}
```
此實作的概念是讓第二個元素指向第一個元素，之後再讓第三個元素指向 (原本的) 第二個元素，以此類推，最後完成整個 linked list 的反轉。
### q_sort
參考[題目說明](https://hackmd.io/JSFDnHn0Rpe0V7d-AqLAXA?view#-%E6%94%B9%E5%AF%AB%E8%87%AA-CMU-%E8%A8%88%E7%AE%97%E6%A9%9F%E6%A6%82%E8%AB%96%E7%9A%84%E4%BD%9C%E6%A5%AD)中提供的 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 以及[第 1 周隨堂練習](https://hackmd.io/@sysprog/linux2020-quiz1)中的程式碼來實作出 merge sort。
```cpp
list_ele_t *mergeSort(list_ele_t *head)
{
list_ele_t *fast, *slow;
if (!head->next)
return head;
fast = head->next;
slow = head;
/* Split */
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
/* Sort */
slow = mergeSort(head); // left list
fast = mergeSort(fast); // right list
/* Merge */
for (list_ele_t *merge = NULL; slow || fast;) {
if (!fast || (slow && strcmp(fast->value, slow->value) >= 0)) {
if (!merge)
head = merge = slow;
else {
merge->next = slow;
merge = merge->next;
}
slow = slow->next;
} else {
if (!merge)
head = merge = fast;
else {
merge->next = fast;
merge = merge->next;
}
fast = fast->next;
}
}
return head;
}
void q_sort(queue_t *q)
{
if (!q || !q->head)
return;
q->head = mergeSort(q->head);
}
```
#### 簡化 `q_sort` 中不必要的操作
```cpp
diff --git a/queue.c b/queue.c
index 3dbf39a..cf29256 100644
--- a/queue.c
+++ b/queue.c
@@ -196,8 +196,9 @@ list_ele_t *mergeSort(list_ele_t *head)
fast = mergeSort(fast); // right list
/* Merge */
- for (list_ele_t *merge = NULL; slow || fast;) {
- if (!fast || (slow && strcmp(fast->value, slow->value) >= 0)) {
+ list_ele_t *merge;
+ for (merge = NULL; slow && fast;) {
+ if (strcmp(fast->value, slow->value) >= 0) {
if (!merge)
head = merge = slow;
else {
@@ -215,6 +216,10 @@ list_ele_t *mergeSort(list_ele_t *head)
fast = fast->next;
}
}
+ if (slow)
+ merge->next = slow;
+ if (fast)
+ merge->next = fast;
return head;
}
```
在合併的過程中，其中一個 linked list 一定會先變為 empty queue，而原本的作法是繼續將一個一個元素串連起來。
而其實可以改為將已合併完的 linked list 的最後一個元素指向未合併的 non-empty queue ，如此一來就可以減少迴圈的迭代次數。
### Natural sort
閱讀完 natural sort 的 [README](https://github.com/sourcefrog/natsort) 後得知只需要 strnatcmp.[ch] 即可使用裡面的 `strnatcmp` 函式來以 natural order 的方式來排序。
#### 新增 strnatcmp.[ch]
將 strnatcmp.[ch] 放進主目錄並對 queue.c 進行以下修改：
```cpp
diff --git a/queue.c b/queue.c
index cf29256..dc3369a 100644
--- a/queue.c
+++ b/queue.c
@@ -4,6 +4,7 @@
#include "harness.h"
#include "queue.h"
+#include "strnatcmp.h"
#ifndef strlcpy
#define strlcpy(dst, src, sz) snprintf((dst), (sz), "%s", (src))
@@ -198,7 +199,7 @@ list_ele_t *mergeSort(list_ele_t *head)
/* Merge */
list_ele_t *merge;
for (merge = NULL; slow && fast;) {
- if (strcmp(fast->value, slow->value) >= 0) {
+ if (strnatcmp(fast->value, slow->value) >= 0) {
if (!merge)
head = merge = slow;
else {
```
修改 Makefile 讓 strnatcmp.[ch] 有被編譯到。
```
diff --git a/Makefile b/Makefile
index 0356a37..46accb3 100644
--- a/Makefile
+++ b/Makefile
@@ -26,7 +26,7 @@ $(GIT_HOOKS):
@echo
OBJS := qtest.o report.o console.o harness.o queue.o \
- random.o dudect/constant.o dudect/fixture.o dudect/ttest.o
+ random.o dudect/constant.o dudect/fixture.o dudect/ttest.o strnatcmp.o
deps := $(OBJS:%.o=.%.o.d)
qtest: $(OBJS)
```
#### 測試
```shell
$ ./scripts/driver.py -t 16
--- Trace Points
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-16-perf 6/6
--- TOTAL 6/6
```
得到滿分，雖然看起來很好，但是實際上是有問題的。
在排序完後都會檢查所有的元素是否為**由小到大**排列，而原本的由小到大是指 [Lexicographic order](https://en.wikipedia.org/wiki/Lexicographical_order) ，在換成 Natural order 後測試不應該得到滿分，因為元素排列的順序會不一樣。
#### 尋找原因
兩種 order 的差別在於對數字部份的比較大小方式不同，而其他字元則是以相同的方式比較，因此我懷疑自動產生的隨機字串可能沒有數字。
在 qtest.c 中可以找到產生隨機字串的函式 `fill_rand_string` ：
```cpp
/*
* TODO: Add a buf_size check of if the buf_size may be less
* than MIN_RANDSTR_LEN.
*/
static void fill_rand_string(char *buf, size_t buf_size)
{
size_t len = 0;
buf_size = buf_size < MIN_RANDSTR_LEN ? MIN_RANDSTR_LEN : buf_size;
while (len < MIN_RANDSTR_LEN)
len = rand() % buf_size;
for (size_t n = 0; n < len; n++) {
buf[n] = charset[rand() % (sizeof charset - 1)];
}
buf[len] = '\0';
}
```
可以看到字串產生的方法為從 `charset` 中隨機取出字元並存進 `buf` 中，並且可以找到 `charset` 的定義如下：
```cpp
static const char charset[] = "abcdefghijklmnopqrstuvwxyz";
```
只有英文字，符合先前的猜測。
#### 解決問題
解決問題的方法很簡單，只需要把數字加進 `charset` 裡面就好。
```shell
$ make
CC qtest.o
LD qtest
$ ./scripts/driver.py -t 16
--- Trace Points
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
Error limit exceeded. Stopping command execution
--- trace-16-perf 0/6
--- TOTAL 0/6
```
#### 檢查 `q_sort` 是否正確
只要把在 qtest.c 中檢查 queue 是否排列正確的地方的比較函式換成 `strnatcmp` 就可以自動檢查。
```cpp
diff --git a/qtest.c b/qtest.c
index e2a225d..225ed3a 100644
--- a/qtest.c
+++ b/qtest.c
@@ -23,6 +23,9 @@
/* How much padding should be added to check for string overrun? */
#define STRINGPAD MAXSTRING
+/* Sorting in natural order */
+#include "strnatcmp.h"
+
@@ -60,7 +63,7 @@ static int string_length = MAXSTRING;
#define MIN_RANDSTR_LEN 5
#define MAX_RANDSTR_LEN 10
-static const char charset[] = "abcdefghijklmnopqrstuvwxyz";
+static const char charset[] = "0123456789abcdefghijklmnopqrstuvwxyz";
/* Forward declarations */
static bool show_queue(int vlevel);
@@ -168,6 +171,7 @@ static bool do_free(int argc, char *argv[])
static void fill_rand_string(char *buf, size_t buf_size)
{
size_t len = 0;
+ buf_size = buf_size < MIN_RANDSTR_LEN ? MIN_RANDSTR_LEN : buf_size;
while (len < MIN_RANDSTR_LEN)
len = rand() % buf_size;
@@ -558,7 +562,7 @@ bool do_sort(int argc, char *argv[])
for (list_ele_t *e = q->head; e && --cnt; e = e->next) {
/* Ensure each element in ascending order */
/* FIXME: add an option to specify sorting order */
- if (strcasecmp(e->value, e->next->value) > 0) {
+ if (strnatcasecmp(e->value, e->next->value) > 0) {
report(1, "ERROR: Not sorted in ascending order");
ok = false;
break;
```
```shell
$ make
CC qtest.o
LD qtest
$ ./scripts/driver.py -t 16
--- Trace Points
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-16-perf 6/6
--- TOTAL 6/6
```
關於 ==FIXME== 的作法暫時還沒想到好的寫法所以先直接把 `strcasecmp` 改為 `strnatcasecmp` 。
## 使用 Massif 來視覺化記憶體的使用情形
```shell
$ valgrind --tool=massif ./qtest
```
使用以下測資來觀察記憶體變化︰
```
option fail 0
option malloc 0
new
ih aa 10000
it bb 10000
reverse
sort
free
```
產生圖表：
雖然看不太清楚，不過最後其實還有記憶體殘留，並沒有回到 0 KiB
雖然有試著利用 valgrind 來偵測哪裡有未釋放的記憶體，不過 valgrind 並沒有顯示任何錯誤訊息。
## "simulation" 模式如何透過實驗而非理論來驗證時間複雜度
### 參考工具： [dudect](https://github.com/oreparaz/dudect)
讀了 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) 這篇論文後，了解到 [dudect](https://github.com/oreparaz/dudect) 這個工具是透過機率與統計的方法來驗證程式碼是否以常數時間執行。
論文中提到的方法有 t-test 以及 Non-parametric tests ，而這次 [lab-0](https://hackmd.io/@sysprog/linux2020-lab0) 則是應用其中跟 *t-test* 有關的部份來驗證。
### 理論： t-test
t-test 有分非常多種，比較常見的是 [Student's t-test](https://en.wikipedia.org/wiki/Student%27s_t-test) 而 [dudect](https://github.com/oreparaz/dudect) 使用的是 [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) 。
[Student's t-test](https://en.wikipedia.org/wiki/Student%27s_t-test) 是基於 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-test) 的驗證方法。
* [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-test)
可以根據數量少的樣本來估計呈 [Normal distribution](https://en.wikipedia.org/wiki/Normal_distribution) 且變異數未知的整體平均值。
而當變異數為已知時，則應該用 [Normal distribution](https://en.wikipedia.org/wiki/Normal_distribution) 來估算。
* [Student's t-test](https://en.wikipedia.org/wiki/Student%27s_t-test)
以 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-test) 為基礎，用來檢驗兩群獨立且來自 [Normal distribution](https://en.wikipedia.org/wiki/Normal_distribution) 的樣本的期望值是否相等。
* [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test)
跟 [Student's t-test](https://en.wikipedia.org/wiki/Student%27s_t-test) 一樣可以檢測兩群樣本的期望值是否相等。
兩者的差別在於 [Student's t-test](https://en.wikipedia.org/wiki/Student%27s_t-test) 假設這兩群樣本的變異數相等，而 [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) 則可以應用在變異數不相等的情況。
從以上敘述可以知道，需要有兩組測資來當作樣本，一組為固定值，另一組為亂數。
統計這兩組測資的執行時間並拿去做 [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) 後，如果兩組樣本的平均時間夠接近，則時間複雜度就有很高的機率為 $O(1)$ 。
### 程式實作
以 "insert tail" 為例。
首先先尋找 qtest.c 裡跟 "simulation" 模式有關的程式碼，發現 `do_insert_tail` 呼叫 `is_insert_tail_const` 後便得知結果，因此分析的程式碼應該都在 `is_insert_tail_const` 裡。
* `is_insert_tail_const`
```cpp
bool is_insert_tail_const(void)
{
bool result = false;
t = malloc(sizeof(t_ctx));
for (int cnt = 0; cnt < test_tries; ++cnt) {
printf("Testing insert_tail...(%d/%d)\n\n", cnt, test_tries);
init_once();
for (int i = 0;
i <
enough_measurements / (number_measurements - drop_size * 2) + 1;
++i)
result = doit(0);
printf("\033[A\033[2K\033[A\033[2K");
if (result == true)
break;
}
free(t);
return result;
}
```
從上面程式碼可以看到每次迴圈都會呼叫一次 `init_once` 來初始化 `t` 和 `q` 。
`t` 指向一個 `t_ctx` 物件，裡面存有 Welch's test 所需要的資料。
`q` 指向一個 queue ，而前面在 queue.c 中實作的函式就會作用這個 queue 上。
之後 `doit` 函式就會開始統計時間並分析，最後回傳檢測結果。
* `doit`
```cpp
static bool doit(int mode)
{
int64_t *before_ticks = calloc(number_measurements + 1, sizeof(int64_t));
int64_t *after_ticks = calloc(number_measurements + 1, sizeof(int64_t));
int64_t *exec_times = calloc(number_measurements, sizeof(int64_t));
uint8_t *classes = calloc(number_measurements, sizeof(uint8_t));
uint8_t *input_data =
calloc(number_measurements * chunk_size, sizeof(uint8_t));
if (!before_ticks || !after_ticks || !exec_times || !classes ||
!input_data) {
die();
}
prepare_inputs(input_data, classes);
measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
update_statistics(exec_times, classes);
bool ret = report();
free(before_ticks);
free(after_ticks);
free(exec_times);
free(classes);
free(input_data);
return ret;
}
```
從函數的名字可以知道， `doit` 會先準備好要輸入的資料 (一組定值、一組亂數) ，然後再去測量執行時間並更新，最後再回報是否通過檢測。
* `prepare_inputs`
用亂數將 `input_data` 填滿，並將亂數的 0 和 1 填入 `classes` 。
`classes` 的值代表他被分配到哪一組，如果 `classes[idx]` 為 0 ，則 `input_data[idx * chunk_size]` 就是被分到 0 這組，反之亦然。
在實作中是把分到 0 這組的數字全都設為 0 。
* `measure`
測量開始與結束的時間，並分別存入 `before_ticks` 和 `after_ticks` 。
時間的單位為 [CPU cycles](https://en.wikipedia.org/wiki/Instruction_cycle)
* `differentiate`
算出每次的 `q_insert_tail` 需要幾個 [CPU cycles](https://en.wikipedia.org/wiki/Instruction_cycle) ，也就是 `after_ticks` 減去 `before_ticks` ，並將結果存進 `exec_times` 。
* `update_statistics`
更新 `t` 裡面的資料，這裡使用 `t_push` 函式來更新。
* `t_push`
```cpp
void t_push(t_ctx *ctx, double x, uint8_t class)
{
assert(class == 0 || class == 1);
ctx->n[class]++;
/* Welford method for computing online variance
* in a numerically stable way.
*/
double delta = x - ctx->mean[class];
ctx->mean[class] = ctx->mean[class] + delta / ctx->n[class];
ctx->m2[class] = ctx->m2[class] + delta * (x - ctx->mean[class]);
}
```
這裡的更新使用的是 [Welford's online algorithm](https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Welford's_online_algorithm) 來計算，原因是如果按照原本的公式去算的話，很可能會因為數字太大而造成 overflow 。
在程式碼中 `delta` 就代表 $x_n - \bar{x}_{n - 1}$ 。
$$ \bar{x}_n = \frac{(n - 1)\bar{x}_{n-1} + x_n}{n} = \bar{x}_{n - 1} + \frac{x_n - \bar{x}_{n - 1}}{n} \\ M_{2, n} = M_{2, n - 1} + (x_n - \bar{x}_{n - 1})(x_n - \bar{x}_n) $$
程式碼最後一行的 `ctx->mean[class]` 為更新過後的平均值，所以是 $\bar{x}_n$ ，可以發現最後兩行程式碼就跟上面的兩個公式一模一樣。
* `t_compute`
依照下列公式算出最終的值。
$$ s^2_n = \frac{M_{2, n}}{n - 1} \\ t = \frac{\bar{X}_1 - \bar{X}_2}{\sqrt{\frac{s^2_1}{N_1} + \frac{s^2_2}{N_2}}} $$
注意第一個式子中的 $s^2_n$ 的下標跟第二個式子中的 $s^2_1$ 的下標的意義不一樣。
前者是代表更新的次數，後者是代表屬於哪組測資。
* `report`
判斷是否為 constant time 。
利用 `t-compute` 得到值之後取絕對值，存進 `max_t` 中。
最後只要這個 `max_t` 夠小 (< threshold) 就代表 constant time 。
## `select` 系統呼叫在本程式的使用方式
### `select` 簡介
`select` 是一種 [system call](https://en.wikipedia.org/wiki/System_call) ，他可以幫我們監控多個 [file descriptors](https://en.wikipedia.org/wiki/File_descriptor) ，並且告訴我們哪些是已經準備好可以運作的。
在 [Linux Programmer's Manual](http://man7.org/linux/man-pages/man2/select.2.html) 中可以找到 `select` 的 prototype 如下：
```cpp
int select(int nfds, fd_set *readfds, fd_set *writefds,
fd_set *exceptfds, struct timeval *timeout);
```
`fd_set` 是 [file descriptor](https://en.wikipedia.org/wiki/File_descriptor) 的集合。
> 以下將 file descriptor 簡稱為 fd
從 prototype 中可以看到呼叫 `select` 時需要給他三個集合，分別是 `readfds` 、 `writefds` 和 `exceptfds` ，這三個集合也個別對應到不同的 I/O operation 。
> `readfds` 對應到輸入， `writefds` 對應到輸出， `exceptfds` 則是對應到例外狀況。
`nfds` 的值應該被設為三個集合中數字最大的 fd 再加 1 ，因為在 `select` 中只會檢查 0 ~ `nfds` - 1 這些 fd 有沒有在給定的三個集合中。
`timeout` 則是設定等待的時間，如果時間結束時還沒有任何 fd 準備好對應的 I/O operation 的話則直接跳出函式。
相反的，就算時間還沒結束，但是只要三個集合中有任何一個 fd 是已經準備好的，也會直接跳出函式。
> `timeout` 設為 NULL 代表等待無限長的時間。
`select` 執行完畢後，集合裡面的值會被修改，只留下已經準備好的 fd ，其餘都會被移除。
因此呼叫完之後只要確認 set 有哪些值就可以知道哪些 fd 是可以用的。
### 本程式的使用方式
在 qtest.c 中， `select` 只關心跟輸入有關的 fd 。
1. 首先在 `main` 裡面決定輸入來源是 `stdin` 還是其他檔案。
2. 決定了之後再將其 fd 丟進 `buf_stack` 這個 stack 裡。
`buf_stack` 中的每個元素都是一個 `struct RIO_ELE` 物件，此物件可以儲存 fd 、將來自 fd 的輸入暫存進 buffer ，以及紀錄下次輸入時要從哪個位置開始。
利用此物件可以先一次讀取大量的資料並存進 buffer ，之後需要資料時只要從 buffer 裡面取就可以了。
用這個方法可以加速緩慢的 I/O operation 。([這篇文章](https://blog.kuoe0.tw/posts/2013/02/22/acm-icpc-about-io/)有更詳細的解釋)
3. 要讀取資料時，都會先看 buffer 裡有沒有一句完整的指令 (以 '\n' 結尾的字串) ，如果有就將那句指令丟給 `interpret_cmd` 執行，沒有的話就利用 `select` 來等 fd 準備好輸入後將資料讀進 buffer 並再次確認有沒有指令可以執行。
Sign in with Wallet
Connect another wallet