# 2025q1 Homework1 (lab0)
contributed by < Brianpan >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## Queue API Implementations
- [x] q_new
- [x] q_free
- [x] q_insert_head
- [x] q_insert_tail
- [x] q_remove_head
- [x] q_remove_tail
- [x] q_size
- [x] q_delete_mid
- [x] q_delete_dup
- [x] q_swap
- [x] q_reverse
- [x] q_reverseK
- [x] q_sort
- [x] q_ascend
- [x] q_descend
- [x] q_merge
### q_new
要確認malloc是否成功
```cpp!
if (h != NULL)
INIT_LIST_HEAD(h);
```
### q_free
移除queue的時候要連所包含的內容一起釋放
所以要使用list_for_each_safe api
### q_insert_head / q_insert_tail
插入新元素要考慮是否有成功分配空間
```cpp!
element_t *new_ele = malloc(sizeof(element_t));
// malloc fails
if (new_ele == NULL)
return false;
// can not dup str
char *dup_str = strdup(s);
if (dup_str == NULL) {
// free element's malloc
free(new_ele);
return false;
}
```
除此之外,這兩者的差別只在list_add, list_add_tail的api使用
### q_remove_head
一開始使用間接指標去memcpy 發現 case-07過不了
```cpp!
/* Copy element var */
void copy_to_buf(char **dst, char **src, size_t bufsize)
{
size_t end = bufsize - 1;
if (strlen(*src) >= end) {
memcpy(*dst, *src, end);
*dst[end] = '\0';
return;
}
memcpy(*dst, *src, bufsize);
}
```
改進後 [commit]([6de1cf2070cc8a72b9970fb446a6411f312f1ad6](https://github.com/Brianpan/lab0-c/commit/6de1cf2070cc8a72b9970fb446a6411f312f1ad6)) 參考同學的實作改用strncpy去避免這樣的情況
```cpp!
if (sp) {
strncpy(sp, e->value, bufsize -1);
sp[bufsize - 1] = '\0';
}
```
### q_remove_tail
這裡埰用間接的方式去實作,我們把head->prev->prev指標當作q_remove_head的head,
其實就是q_remove_head
```cpp!
q_remove_head(head->prev->prev, sp, bufsize)
```
### q_size
[commit](c15b1d7eeb1306f51673fef38fcc2eeb2a45a2a0)
### q_delete_mid
我們採用快慢指標的做法,這裡要確認兩個條件
- n % 2 == 0: 兩個元素的時候跑一次迴圈slow指標在第一個元素,fast指標在第二個元素,n = 2k 一樣是對的因為可以拆成k個2個長度的串列
- n % 2 == 1: 一個元素的時候會跑一次迴圈,slow指標會停在head->next, fast指標會停在head, 剩下的狀態就是1 + 2x,我們知道偶數的狀態是對的,故奇數也是
```cpp!
do {
slow = slow->next;
fast = fast->next->next;
} while (fast != head && fast->next != head);
```
### q_delete_dup
[commit](https://github.com/Brianpan/lab0-c/commit/710f534e7c92ad24ba7cf45c5a67701c7d2ddbf1)
這邊的思路是用兩層迴圈去判定是否需要重複的元素需要刪除,因為已經假定是排序過後的儲列所以重複的會串接在一起,我們我們用兩個指標start, curr去表示這之間的元素是重複的
```cpp!
struct list_head *start = *indirect;
struct list_head *curr = *indirect;
// compare element to find end
while (curr->next != head) {
element_t *ele = list_entry(curr, element_t, list);
element_t *ele_next = list_entry(curr->next, element_t, list);
if (strcmp(ele->value, ele_next->value) == 0) {
dup = true;
curr = curr->next; // can use goto
} else
break;
}
```
之後透過dup判定有重複的話就使用list_cut_position去去移除[start, curr]指標之間的元素,值得一題這邊因為是要使用list head當作參數,所以我們要我們要傳入start->prev當作list head
```cpp!
list_cut_position(tmp_head, start->prev, curr);
```
### q_swap
[commit](https://github.com/Brianpan/lab0-c/commit/710f534e7c92ad24ba7cf45c5a67701c7d2ddbf1)
交換採取一個while迴圈確認是否停在倒數第二個元素
```cpp!
while (*indirect != head && (*indirect)->next != head)
```
並且交換的指標更新是交換後的first指標的next
```cpp!
// move to original b's next ptr
indirect = &first->next;
```
### q_reverse
[commit](https://github.com/Brianpan/lab0-c/commit/710f534e7c92ad24ba7cf45c5a67701c7d2ddbf1)
這邊的思路是元素從第二個開始,我們一直把元素往head指標之後插入
這個就是reverseK當k=2的情況
### q_reverseK
[commit](https://github.com/Brianpan/lab0-c/commit/710f534e7c92ad24ba7cf45c5a67701c7d2ddbf1)
reverseK的思路則是把reverse的點子延伸,多跑一層while迴圈去分群k個元素的交換
這裡用group_head代表一個分群的head指標
```cpp!
// 第一個元素
first = group_head->next;
// 從第二個元素開始往group_head後面插入
struct list_head *cur = first->next;
int inner_k = k - 1;
// 這裡其實就是q_reverse
while (inner_k > 0) {
struct list_head *next = cur->next;
group_head->next->prev = cur;
cur->next = group_head->next;
cur->prev = group_head;
group_head->next = cur;
cur = next;
inner_k--;
}
```
這個實作需要考慮一個情況,當串列的個數是k的倍數,我們必需更新head->prev指標成最後一輪的first指標
```cpp!
if (sz == 0)
head->prev = first;
```
思考怎麼用指標的指標優化
### q_sort
[commit](https://github.com/sysprog21/lab0-c/commit/bfc7db434c4c9724a5613620cd2b225a2b391c75)
這個實作學習使用以下API:
- list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node): 從head_from分割node指標開始的串列到head_to串列
並且用最常用的merge sort方法實作
具體作法有參考同學和[非連續記憶體講座](https://hackmd.io/@sysprog/c-linked-list)
具體操作是：
- 分割步驟: 使用快慢指標找到中點slow指標
- 合併步驟: q_merge_two中依序把元素插入tmp_head的串列,只是多了用一個flag判斷是遞增或是遞減,再來把剩餘的加入tmp_head串列,最後再把tmp_head放回first指標當中
### q_ascend, q_descend
[commit](https://github.com/sysprog21/lab0-c/commit/bfc7db434c4c9724a5613620cd2b225a2b391c75)
兩個的做法只差在排序上面, 所以實作細節放在同一個函式q_remove_nodes(struct list_head *head, bool descend)
主要思路是從尾部往回看如果是遞減排序代表最後一個一定是最小的,只要前面比它更小的元素就刪除
### q_merge
[commit](https://github.com/sysprog21/lab0-c/commit/bfc7db434c4c9724a5613620cd2b225a2b391c75)
這裡一開始有點不懂怎麼找到串列的串列,有參考同學的資料後知道是使用
```cpp!
/**
* queue_contex_t - The context managing a chain of queues
* @q: pointer to the head of the queue
* @chain: used by chaining the heads of queues
* @size: the length of this queue
* @id: the unique identification number
*/
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
之後就是採取[非連續記憶體講座](https://hackmd.io/@sysprog/c-linked-list)的頭尾合併方法,中間的優化有參考同學的實作
思路是跑兩個迴圈:
外迴圈是合併終止條件end指標是head->next
內迴圈是首尾合併並且利用q_merge實作
至於為什麼是使用end指標則是分奇數偶數個數討論
偶數個數下end指標會跑到最後一個start指標指到的位置
奇數個數下end指標是最中間都沒合併到的元素
目前還有最後一個測試沒有通過
## q_shuffle
[commit](https://github.com/Brianpan/lab0-c/commit/80f8d265aa233f38923ae7be533bb5bb19284640)
### 統計方法驗證 `shuffle`
[Pearson's chi-squared test](https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test) 能檢驗虛無假說（Null hypothesis），即某特定事件在樣本中觀察到的頻率分佈與特定理論分佈一致，事件必須是互斥且機率為 1。
如果要 shuffle 三個不同的數字，會出現六種可能的結果，彼此是互斥的，且發生機率加起來為 1。那假設 shuffle 是公平的（六種結果發生的機率相同），並遵守 Uniform distribution，那虛無假說為：
+ $H_0$（虛無假說）: shuffle 的結果發生的機率相同，遵守 Uniform distribution
+ $H_1$（對立假說）: shuffle 的結果發生的機率至少有一個不同
接下來透過 Pearson's chi-squared test 來驗證 shuffle 三個數字的頻率是符合 Uniform distribution:
#### 1. 先計算 chi-squared test statistic $X^2$
$$
X^2 = \sum_{i=1}^n {(O_i - E_i)^2 \over E_i}
$$
+ $X^2$: Pearson's cumulative test statistic
+ $O_i$: the number of observations of type i
+ $E_i$: the expected count of type i
根據[測試程式](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F)跑出的結果
```
Expectation: 41666
Observation: {'1234': 42063, '1243': 41617, '1324': 41777, '1342': 41467, '1423': 41990, '1432': 41620, '2134': 41597, '2143': 41619, '2314': 41483, '2341': 41749, '2413': 41587, '2431': 41333, '3124': 41587, '3142': 41535, '3214': 41867, '3241': 41682, '3412': 41593, '3421': 41697, '4123': 41804, '4132': 41554, '4213': 41431, '4231': 41992, '4312': 41778, '4321': 41578}
chi square sum: 18.413766620265925
```
自由度: 4! - 1 = 23
根據這個[網站](https://www.scribbr.com/statistics/chi-square-distribution-table/)提供的chi-squre表格
18.41的chi-square值介於$alpha$為0.9 - 0.1之間也就是p值是介在0.9-0.1
因為p值大於我們假設的顯著水準0.05
所以我們無法拒絕虛無假設
代表這個分佈是平均的
#### 理解p值
在我們假設$H_0$為真的情況,實際實驗觀測到這個可能發生的機率,
換句話說當p值越小,我們預期這個狀況發生的情況很小
如果我們觀測的樣本出現p值很小的情況 < 顯著水準
直觀的意義是$H_0$正確的話出現機率只有p
但是好死不死被我們碰上了
所以可能我們的假設有錯,不然怎麼這麼低的機率都會發生
## 整合網頁伺服器
### trace code 學到的API
- [fflush(FILE *_Nullable stream)](https://man7.org/linux/man-pages/man3/fflush.3.html): 把user buffer裡面的資料寫到stream中
- i/o multiplexing中的[select](https://man7.org/linux/man-pages/man2/select.2.html)系統呼叫,select的限制是只有至多FD_SETSIZE (1024)個file descriptor可以被監視, 並且是使用檢查位元方式去確認哪個file descriptor可以執行相應的動作(讀,寫,例外),此外手冊說明除了準備好的fd之外的位元會被清除,代表每一輪都要重設狀態.
```cpp!
#include <sys/select.h>
typedef /* ... */ fd_set;
// return value is number of file descriptors contained in the three returned descriptor sets
// nfds是最大fd值+1
int select(int nfds, fd_set *_Nullable restrict readfds,
fd_set *_Nullable restrict writefds,
fd_set *_Nullable restrict exceptfds,
struct timeval *_Nullable restrict timeout);
// 位元處理操作
void FD_CLR(int fd, fd_set *set);
int FD_ISSET(int fd, fd_set *set);
void FD_SET(int fd, fd_set *set);
void FD_ZERO(fd_set *set);
```
- rio: robust I/O API讀寫經過一層自訂的user buffer,想起很像FILE結構內部有類似的實作,
以前去facebook面試的時候,程式題就是考類似的東西,此外這個實作讓我想起這句話
> Any problem in computer science can be solved by another layer of indirection
> David Wheeler
可以多加一層實作去解決任何問題
```cpp!
typedef struct {
int fd; /* descriptor for this buf */
int count; /* unread byte in this buf */
char *bufptr; /* next unread byte in this buf */
char buf[BUFSIZE]; /* internal buffer */
} rio_t;
static void rio_readinitb(rio_t *rp, int fd)
{
rp->fd = fd;
rp->count = 0;
rp->bufptr = rp->buf;
}
static ssize_t rio_read(rio_t *rp, char *usrbuf, size_t n)
{
int cnt;
while(rp->count <= 0) { /* interrupted by sig handler return */
rp->count = read(rp->fd, rp->buf, sizeof((rp->buf)));
if (rp->count < 0) {
if (errno != EINTR)
return -1;
} else if(rp->count == 0) // EOF
return 0;
else
rp->bufptr = rp->buf; // reset buffer ptr
}
cnt = 0;
if (rp->count < n)
cnt = rp->count;
memcpy(usrbuf, rp->bufptr, cnt);
rp->bufptr += cnt;
rp->count -= cnt;
return cnt;
}
// write to fd directly
static ssize_t written(int fd, void *usrbuf, size_t n)
{
size_t nleft = n;
char *bufp = usrbuf;
while (nleft > 0) {
ssize_t nwritten = write(fd, bufp, nleft);
if (nwritten <= 0) {
if (errno == EINTR) {
nwritten = 0;
} else
return -1;
}
nleft -= nwritten;
bufp += written;
}
return n;
}
static ssize_t rio_readlineb(rio_t *rp, void *userbuf, size_t maxlen)
{
char c, *bufp = usrbuf;
int n;
for(n = 1; n < maxlen; n++) {
int rc;
if ((rc = rio_read(rp, &c, 1)) == 1) {
*bufp++ = c;
if (c =='\n')
break;
} else if (rc == 0) {
if (n == 1)
return 0; /* EOF, no data read */
break;
} else
return -1;
}
*bufp = 0; // last char is terminator
return n;
}
```
bool run_console(char *infile_name): console進入函式
主要要關注的是cmd_select(): 這裡認為是模擬一個簡單的select, 測試在web模式和cmd模式下
buf_stack->fd都是STDIN_FILENO, 問題來了web模式怎麼把資料寫入buffer的
```cpp!
bool run_console(char *infile_name)
{
if (!push_file(infile_name)) {
report(1, "ERROR: Could not open source file '%s'", infile_name);
return false;
}
if (!has_infile) {
char *cmdline;
while (use_linenoise && (cmdline = linenoise(prompt))) {
interpret_cmd(cmdline);
line_history_add(cmdline); /* Add to the history. */
line_history_save(HISTORY_FILE); /* Save the history on disk. */
line_free(cmdline);
while (buf_stack && buf_stack->fd != STDIN_FILENO)
cmd_select(0, NULL, NULL, NULL, NULL);
has_infile = false;
}
if (!use_linenoise) {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
return err_cnt == 0;
}
static int cmd_select(int nfds,
fd_set *readfds,
fd_set *writefds,
fd_set *exceptfds,
struct timeval *timeout)
{
fd_set local_readset;
if (cmd_done())
return 0;
if (!block_flag) {
int infd;
/* Process any commands in input buffer */
if (!readfds)
readfds = &local_readset;
/* Add input fd to readset for select */
infd = buf_stack->fd;
FD_ZERO(readfds);
FD_SET(infd, readfds);
/* If web_fd is available, add to readfds */
if (web_fd != -1)
FD_SET(web_fd, readfds);
if (infd == STDIN_FILENO && prompt_flag) {
char *cmdline = linenoise(prompt);
if (cmdline)
interpret_cmd(cmdline);
fflush(stdout);
prompt_flag = true;
} else if (infd != STDIN_FILENO) {
char *cmdline = readline();
if (cmdline)
interpret_cmd(cmdline);
}
}
return 0;
}
```
回頭看do_web, 先透過web_open去完成一個網頁伺服器端的必要操作
> socket->bind->listen
緊接著註冊一個回呼函數
```cpp!
line_set_eventmux_callback(web_eventmux);
```
> For example, the main
> loop of this package can only deal with standard input file descriptor
> originally. When this callback function is invoked, it allows the main loop
> of this package to deal with multiple file descriptors from different input
> alongside with the origin feature to deal with the standard input.
簡單來說就是允許從stdin之外的fd去讀取輸入
web_eventmux的函式類型是
```cpp!
typedef int(line_eventmux_callback_t)(char *);
```
這個相當於傳入一個將來要被讀取的buffer
然後伺服器的功能是透過select確認有請求可以被讀取後呼叫accept系統呼叫
接著在web_recv中再呼叫parse_request以rio方式取得輸入內容
最後把結果寫回buffer
```cpp!
int web_eventmux(char *buf)
{
fd_set listenset;
FD_ZERO(&listenset);
FD_SET(STDIN_FILENO, &listenset);
int max_fd = STDIN_FILENO;
if (server_fd > 0) {
FD_SET(server_fd, &listenset);
max_fd = max_fd > server_fd ? max_fd : server_fd;
}
int result = select(max_fd + 1, &listenset, NULL, NULL, NULL);
if (result < 0)
return -1;
if (server_fd > 0 && FD_ISSET(server_fd, &listenset)) {
FD_CLR(server_fd, &listenset);
struct sockaddr_in clientaddr;
socklen_t clientlen = sizeof(clientaddr);
int web_connfd =
accept(server_fd, (struct sockaddr *) &clientaddr, &clientlen);
char *p = web_recv(web_connfd, &clientaddr);
char *buffer = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n";
web_send(web_connfd, buffer);
strncpy(buf, p, strlen(p) + 1);
free(p);
close(web_connfd);
return strlen(buf);
}
FD_CLR(STDIN_FILENO, &listenset);
return 0;
}
```
之後這個buffer就可以透過linenoise()函式取得內容
達到qtest可以同時接收伺服器請求
## 研讀論文〈Dude, is my code constant time?〉
### 實驗條件
- 不限制硬體條件
- 使用類似side channel attack的方式去比較是否是常數時間
### 實驗步驟
#### 將比較兩個分類 fixed vs random
論文說明fixed class可以是極端條件的一種
#### post-processing
- Cropping: 去除某個百分位的極端值, 理解為受當時其他條件影響的值該被剔除
- High-order preprocessing: centered product
#### 使用統計檢定比較結果
- t-test
計算$t = \frac{\bar{X_0} - \bar{X_1}}{\sqrt{\frac{Var_0}{N_0} + \frac{Var_1}{N_1}}}$值的p value是否小於特定顯著水準$\alpha$
- 無母數分析
### lab0-c實作
目前根據ttest.c裡面的描述是使用差值的方式動態更新平均
```cpp!
void t_push(t_context_t *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]);
}
```
主要呼叫的方式是透過巨集呼叫fixture.c中的test_const的函式,test_const再呼叫doit去執行實際的測試邏輯
```cpp!
// mode is either
// DUT_insert_head, DUT_remove_head, DUT_insert_tail, DUT_remove_tail
static bool doit(int mode)
{
int64_t *before_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
int64_t *after_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
int64_t *exec_times = calloc(N_MEASURES, sizeof(int64_t));
uint8_t *classes = calloc(N_MEASURES, sizeof(uint8_t));
uint8_t *input_data = calloc(N_MEASURES * CHUNK_SIZE, sizeof(uint8_t));
if (!before_ticks || !after_ticks || !exec_times || !classes ||
!input_data) {
die();
}
prepare_inputs(input_data, classes);
bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
update_statistics(exec_times, classes);
ret &= report();
free(before_ticks);
free(after_ticks);
free(exec_times);
free(classes);
free(input_data);
return ret;
}
```
目前實作有時跑過有時失敗,可能原因在沒有剔除極端值,因為實驗環境是在lxc虛擬機器或是digital ocean提供的kvm虛擬機中, 同時可能和多個工作競爭資源
### 實作percentile
[commit](https://github.com/Brianpan/lab0-c/commit/037938be32c762a358c6c69c09c14993a2c9d125)
根據論文[程式碼](https://github.com/oreparaz/dudect/blob/dc269651fb2567e46755cfb2a13d3875592968b5/src/dudect.h#L221)
```cpp!
static int64_t percentile(int64_t *a_sorted, double which, size_t size) {
size_t array_position = (size_t)((double)size * (double)which);
assert(array_position < size);
return a_sorted[array_position];
}
/*
set different thresholds for cropping measurements.
the exponential tendency is meant to approximately match
the measurements distribution, but there's not more science
than that.
*/
static void prepare_percentiles(dudect_ctx_t *ctx) {
qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
ctx->percentiles[i] = percentile(
ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)),
ctx->config->number_measurements);
}
}
```
得知他的去除極端值是兩個class合在一起看,本來的想法是應該要分成class 0和class 1再個別去除,或許是他假設如果兩個class是constant time 應該是放在同個母體剔除？
實作採取類似原始程式碼的方式,差別在於[原始程式](https://github.com/oreparaz/dudect/blob/dc269651fb2567e46755cfb2a13d3875592968b5/src/dudect.h#L430)用第一輪來計算百分位數,而這裡使用每輪結束後剔除,這樣的缺點是會多跑很多次排序,但是這樣剔除極端值會比只採用一輪好
此外,論文的百分位數公式是使用指數百分位數
$percentile(i) = 1 - 0.5^{10 * (i+1)/100}$
代表函數以指數方式成長百分位數越大差距越明顯
```cpp!
static void prepare_percentile(int64_t *exec_times,
uint8_t *classes,
int64_t *percentiles)
{
qsort(exec_times, N_MEASURES, sizeof(int64_t), compare_int64);
for (size_t i = 0; i < N_PERCENTILE; i++) {
percentiles[i] = percentile(
exec_times, 1 - (pow(0.5, 10 * (double)(i+1) / N_PERCENTILE)),
N_MEASURES);
}
}
```
Sign in with Wallet
Connect another wallet