# 2025q1 Homework1 (lab0)
contributed by < `devarajabc` >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
此篇筆記延續自 [linux2024-homework1](https://hackmd.io/@devaraja/linux2024-homework1)
## 修正 queue.c
### `q_ascend`/`q_descend`
在 [linux2024-homework1](https://hackmd.io/@devaraja/linux2024-homework1#q_ascendq_descend:~:text=%E5%8E%BB%E6%B7%AC%E9%8D%8A%E3%80%82-,q_ascend/q_descend,-%E7%95%99%E6%84%8F%E8%B3%87%E8%A8%8A%E7%A7%91%E6%8A%80)中提及的 `q_ascend` 和 `q_descend` 是錯誤的，雖然僥倖通過測資，但其實該實作並不符合程式的要求，以下面例子來說
```shell
l = [zzz yyy xxx aaa bbb ccc ddd]
cmd> ascend
l = [aaa]
```
預期應為 [aaa bbb ccc ddd] 而非 [aaa]，於是我在 [Commit dfce5a5](https://github.com/devarajabc/lab0-c/commit/dfce5a5bb7853637a115f03d16f2cb5e05bca341) 中修正。
### `q_merge`
目前在 [Commit 1cb1b4b](https://github.com/devarajabc/lab0-c/commit/1cb1b4b78b1e11036d2dd889ad804fb071209382)所使用的方式是第一條串列接上剩下的串列，但多數的情況下合併速度會愈來愈慢，於是我參考 [Queue-Merge](https://sedgewick.io/wp-content/themes/sedgewick/papers/1993Queue.pdf)
## 研讀 Linux 核心原始程式碼的 lib/list_sort.c
為何不在一開始就判斷 `Zero or one elements` ?
```c
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
if (list == head->prev) /* Zero or one elements */
return;
```
>Thus, it will avoid cache thrashing as long as $3*2^k$ elements can fit into the cache.
為什麼？
>Each time we increment "count", we set one bit (bit k) and clear bits k-1 .. 0.
```c
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
```
## 自動測試
### 如何偵測程式非預期的終止 (如 Segmentation fault)
### 如何知道程式是否執行超時
### qtest 命令直譯器的實作
以 gdb 觀察以下命令是如何被執行的
```
>cmd new
```
```gdb
#0 q_new () at queue.c:9
#1 0x0000555555559160 in do_new (argc=<optimized out>, argv=<optimized out>)
at qtest.c:155
#2 0x000055555555a75e in interpret_cmda (argc=argc@entry=1,
argv=argv@entry=0x55555556b1f0) at console.c:183
#3 0x000055555555ad25 in interpret_cmd (
cmdline=cmdline@entry=0x5555555655a0 <linebuf> "new\n") at console.c:203
#4 0x000055555555afbd in cmd_select (nfds=nfds@entry=0,
readfds=0x7fffffffd6f0, readfds@entry=0x0, writefds=writefds@entry=0x0,
exceptfds=exceptfds@entry=0x0, timeout=timeout@entry=0x0) at console.c:595
#5 0x000055555555b89e in run_console (
infile_name=infile_name@entry=0x7fffffffd890 "traces/trace-01-ops.cmd")
at console.c:675
#6 0x0000555555559b4d in main (argc=3, argv=<optimized out>) at qtest.c:1444
```
觀察 `cmd_element_t`
### 追蹤記憶體配置和釋放的狀況
## 在 qtest 提供新的命令 shuffle
利用 Fisher–Yates shuffle 演算法來實作洗牌（shuffle）
1. 指標 `old` 指向 `head->prev`
1. 先用 `q_size` 取得 `queue` 的大小 `len`。
2. 隨機從 0 ~ (len - 1) 中抽出一個數字 `random`
3. 利用 `hash_table` 獲得指向 `random` 的指標 `new`
5. 將 old 和 new 交換，再將 `len` - 1。
隨著 len 大小變小，已經被抽到過，並交換值到 queue 後面的會愈來愈多，直到所有的節點都已經被抽到過，shuffle 就結束
這時可以用 `list_move` 和 `list_move_tail`
```c
void q_shuffle(struct list_head* head){
int size =
}
```
floating point execeotion
如何新增命令？ console_init 是如何運作的？
### 驗證
## 在 qtest 中執行 option entropy 1
## 研讀論文〈Dude, is my code constant time?〉
在 [dudect](https://github.com/oreparaz/dudect?tab=readme-ov-file) 中提到如何檢查程式的執行時間是否為常數
1. Copy dudect.h to your include directories
2. Add #include "dudect.h" from your source files.
3. write the following functions:
- do_one_computation(),
- prepare_inputs() and
- call dudect_main() from your main function.
[lab0-c](https://github.com/devarajabc/lab0-c/tree/master/dudect) 已包含大部分 [dudect](https://github.com/oreparaz/dudect?tab=readme-ov-file)的內容
```c
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);
}
}
```
原本的寫法有什麼問題？
> TODO 原本的流程：
```c
static void update_statistics(const int64_t *exec_times, uint8_t *classes)
{
for (size_t i = 0; i < N_MEASURES; i++) {
int64_t difference = exec_times[i];
/* CPU cycle counter overflowed or dropped measurement */
if (difference <= 0)
continue;
/* do a t-test on the execution time */
t_push(t, difference, classes[i]);
}
}
```
通過 dudect 的測試就代表程式的執行時間一定是常數嗎？
>Absolutely not. The test implemented is perhaps the simplest form of leakage detection. For serious assessment, you should also run many other tests, with specially crafted input vectors. The test harness implemented here is not yet that comprehensive. You're encourage to submit an implementation that is not constant time yet passes the test--in that way we can improve the test suite. The more you know about the implementation, the better you can design input vectors. For inspiration, see these RSA test vectors.
### simulation 運作
可以注意到在 `trace-17-complexity.cmd` 中有使用 `option simulation 1` 進入 `simulation mode` ，而這 `simulation mode` 是什麼呢？
利用 gbd 觀察期運作流程：
```
$ gdb --args ./qtest -f trace/trace-17-complexity
```
並將中斷點設在 `test_const`
```gdb
#0 test_const (text=text@entry=0x55555556071d "insert_tail",
mode=mode@entry=1) at dudect/fixture.c:155
#1 0x000055555555d093 in is_insert_tail_const () at dudect/fixture.c:180
#2 0x0000555555558c79 in queue_insert (pos=pos@entry=POS_TAIL,
argc=<optimized out>, argv=0x55555556b2f0) at qtest.c:191
#3 0x00005555555590a1 in do_it (argc=<optimized out>, argv=<optimized out>)
at qtest.c:288
#4 0x000055555555a75e in interpret_cmda (argc=argc@entry=1,
argv=argv@entry=0x55555556b2f0) at console.c:183
#5 0x000055555555ad25 in interpret_cmd (
cmdline=cmdline@entry=0x5555555655a0 <linebuf> "it\n") at console.c:203
#6 0x000055555555afbd in cmd_select (nfds=nfds@entry=0,
readfds=0x7fffffffd6f0, readfds@entry=0x0, writefds=writefds@entry=0x0,
exceptfds=exceptfds@entry=0x0, timeout=timeout@entry=0x0) at console.c:595
#7 0x000055555555b89e in run_console (
infile_name=infile_name@entry=0x7fffffffd890 "traces/trace-17-complexity.cmd") at console.c:675
#8 0x0000555555559b4d in main (argc=3, argv=<optimized out>) at qtest.c:1444
```
其中 `is_insert_tail_const` 是藉由巨集來定義，此處利用了前置處理器的技巧:
>延續「物件導向程式設計篇」的思考，我們可善用前置處理器，讓程式碼更精簡、更容易維護，從而提昇程式設計思考的層面
`#`: Stringification/Stringizing (字串化): 讓一個表示式變成字串，在 assert 巨集用到
`##`: concatenation (連結，接續)
```c
#define DUT_FUNC_IMPL(op) \
bool is_##op##_const(void) \
{ \
return test_const(#op, DUT(op)); \
}
```
從上述程式碼可以看出`intert`, `insert_tail`, `remove`, `remove_tail` 的測量的方式皆是透過 `test_const`
其中 `DUT` 是指什麼呢？
```c
static bool test_const(char *text, int mode)
{
bool result = false;
t = malloc(sizeof(t_context_t));
for (int cnt = 0; cnt < TEST_TRIES; ++cnt) {
printf("Testing %s...(%d/%d)\n\n", text, cnt, TEST_TRIES);
init_once();
for (int i = 0; i < ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1;
++i)
result = doit(mode);
printf("\033[A\033[2K\033[A\033[2K");
if (result)
break;
}
free(t);
return result;
}
```
```c
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;
}
```
Sign in with Wallet
Connect another wallet