# 2023q1 Homework1 (lab0)
contributed by< [WeiHongWi](https://github.com/WeiHongWi/lab0-c) >
### Reviewed by `zeddyuu`
* 有些貼上來的程式碼沒有經過 `clang-format` 去做排版
* 程式碼說明部份英文跟中文間沒有空白隔開，有點影響閱讀
* `q_merge` 沒有貼上程式碼，只有說明想法
* 缺乏效能分析以及評估
* 程式碼說明以及想法描述得很詳盡
* 可以視覺化表示會更好
* 論文閱讀部份以數學還有物理角度切入，觀察入微
:::danger
詳閱作業書寫規範，留意細節，才得以征服原始程式碼高達三千萬行的 Linux 核心。程式碼的排版務必依循 [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md) 規範，包含下方筆記所參照的程式碼。
:notes: jserv
:::
## 開發環境
```shell
gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i5-11400H @ 2.70GHz
CPU family: 6
Model: 141
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 1
CPU max MHz: 4500.0000
CPU min MHz: 800.0000
BogoMIPS: 5376.00
```
:::warning
`lscpu` 套件內附的中文翻譯品質不佳，在終端機內先執行 `export LC_ALL=C` 再執行 `lscpu`，隨後更新上方輸出。
:notes: jserv
> 已修改
:::
## 佇列的操作
### 結構 element_t 和 queue_contex_t
```c
struct element_t{
char* value;
struct list_head list;
}
```
```c
struct queue_contex_t{
struct list_head *p;
struct list_head chain;
int size;
int id;
}
```
寫 queue_add 時有疑問：為什麼可以只輸入 struct list_head 的 pointer 而不是輸入和 `element_t` 有關的資料型態,這樣 queue 在做 value 有關的操作時要怎麼做處理？
> [name=HongWei][time=Sat,Feb 18, 2023 10:07 AM]
:::warning
請詳閱教材，留意到 Linux 核心的風格。
:notes: jserv
:::
### q_new()
```c
struct list_head* q_new(){
struct list_head* new = malloc(sizeof(list_head));
//Check the result from the malloc() is not the NULL.
if(new!=NULL){
INIT_LIST_HEAD(new);
}
return new;
}
```
利用 malloc() 給予型態為 struct list_head* 的物件 new 記憶體 , 因為使用了 malloc() 也要額外確認是否有正確配置記憶體給物件 new.
:::danger
改進漢語描述。
:notes: jserv
:::
### q_free()
```c
void q_free(struct list_head *l)
{
if (!l||list_empty(l)) {
return;
}
element_t *item = NULL, *is = NULL;
list_for_each_entry_safe (item, is, l, list) {
list_del(&item->list);
q_release_element(item);
}
free(l);
}
```
:::danger
遇到測試案例回報的錯誤，後來才發現在 line 3 我多寫了一個 list_empty(l) ,導致 object l 還沒被釋放我就 return 了
Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
ERROR: Freed queue, but 1 blocks are still allocated
--- trace-05-ops 0/6
:::
#### 正確的版本
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *item = NULL, *is = NULL;
list_for_each_entry_safe (item, is, l, list) {
list_del(&item->list);
q_release_element(item);
}
free(l);
}
```
對 我看了 4 天
:::warning
幻滅是成長的開始。
:notes: jserv
:::
### q_insert_head()
```c
bool q_insert_head(struct list_head *head, char *s)
{
if(head==NULL){
return false;
}
/*Declare the new object with type element_t*/
element_t *new_node = malloc(sizeof(element_t));
/*Check the correctness of the allocation by malloc()*/
if(new_node==NULL){
return false;
}
/*Initial the member list in the object by the function INIT_LIST_HEAD()*/
INIT_LIST_HEAD(&new_node->list);
//Statement char* s is same as the statement char s[]
//Copy the input argument s to the member value in the object new_node
new_node->value = malloc(strlen(s)+1);
if (new_node->value == NULL){
free(new_node);
return false;
}
/*memcpy(dest,source,size_t) from string.h*/
memcpy(new_node->value,s,strlen(s));
new_node->value[strlen(s)] = '\0';
struct list_head* temp_node = &(new_node->list);
new_node->list.prev = head;
new_node->list.next = head->next;
head->next = &new_node->list;
new_node->list.next->prev = &new_node->list;
return true;
}
```
`element_t* new_node = malloc(sizeof(element_t))`一個 type element_t 的 object 的所需記憶體空間,每個 malloc 做完都要接一個 if statement 來判斷 malloc()是否有正確地分配記憶體
再來針對在 element_t 的兩個 member ,分別是**list**,**value**用***INIT_LIST_HEAD***()初始化 list 並把 memebr list 插入 head 和 head->next 之間, value 則是***memcpy***()將 string 的內容 copy 到 value 這個 pointer 上面
> [name=HongWei][time=Sat,Feb 18, 2023 10:27 PM]
:::danger
Todo :
在 line 60 INIT_LIST_HEAD(&new_node->list)我發現其他學生在做 insert_head 和 insert_tail 時都沒有加這一行,但最後的結果都是對的,所以需要思考是否需要加這一行!
:::
### q_remove_head()
```c=
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if(!head || list_empty(head)){
return NULL;
}
//struct list_head* next = (head->next)->next;
element_t* remove_node = list_first_entry(head,element_t,list);
//head->next = next;
//next->prev = head;
if(sp){
strncpy(sp,remove_node->value,bufsize);
sp[bufsize-1] = '\0';
}
list_del(head->next);
return remove_node;
```
發現在 line 6,11,12的功能和list_del()一模一樣,所以為了程式精簡化修改.
> [name=HongWei][time=Tue,Feb 21, 2023 5:33 PM]
再做 q_remove_head()和 q_size()想到若我能夠將 queue_contex_t 中的 member size 考慮進來,也就是 q_insert() 則 size+1, q_remove或 q_delete()則 size-1,這樣能帶來的效益是當需要 q_size()時不用在巡迴整個佇列導致需要 O(n),若能做到 insert, delete, remove,都能追蹤 object queue 的 size 大小,則 q_size()只需要回傳 queue->size 也就是 O(1)
> [name=HongWei][time=Sat,Feb 19, 2023 5:10 PM]
現在想到的做法是
```clike=
queue_contex_t *start_queue = list_entry(head,queue_contex_t,q);
if(start_queue->size>0){
start_queue-=1;
}
```
將 head 當成是 **type queue_contex_t**的 memebr 中的**p**且藉由 list_entry(head,queue_context_t,q) 來得到 object queue 的位址並將其 memeber size減一,但遇到 error
:::danger
initialization of ‘struct list_head * const*’ from incompatible pointer type ‘struct
不熟list_entry(),想要在花點時間排除這個error.
:::
> [name=HongWei][time=Sat,Feb 19, 2023 5:10 PM]
發現在 head 前面加一個 (void*) 能夠消除這個 error ,但const的目的應該就是不想讓別人修改，所以就不多加變動了
> [name=HongWei][time=Sat,Feb 22, 2023 6:10 PM]
### q_size()
```c
int q_size(struct list_head *head)
{
if(head==NULL){
return 0;
}
int count = 0;
struct list_head *start = head;
while(head->next!=start){
count+=1;
head = head->next;
}
return count;
}
```
和 singular linked list 不同,迴圈的中止條件變成 head被尋訪了兩次這樣為巡迴一圈,額外宣告一個 pointer指向 head 所指向的內容.
> [name=HongWei][time=Sat,Feb 18, 2023 2:10 PM]
發現到最後, head 只會停留在原本 head->prev 的位置.
> [name=HongWei][time=Tue,Feb 21, 2023 3:10 AM]
```c
if (!head||list_empty(head)) {
return 0;
}
int count = 0;
element_t *item=NULL,*is=NULL;
list_for_each_entry_safe(item,is,head,list){
count+=1;
}
return count;
```
看教材 quick_sort 遞迴實作時,發現 list_for_each 和 **list_for_each_entry_safe** 會尋訪整個list一遍,count只要隨之遞增
> [name=HongWei][time=Tue,Feb 21, 2023 3:20 AM]
### q_delete_mid()
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if(list_empty(head)){
return false;
}
struct list_head** indirect = &(head);
/*Try to create the same terminal condition as the singular linked list */
struct list_head* last = head->prev;
last->next = NULL;
/*Also,record the previous node*/
struct list_head* prev = NULL;
for(struct list_head* fast=head;fast&&fast->next;fast= fast->next->next){
prev = *indirect;
indirect = &(*indirect)->next;
}
element_t* deleted_node = list_entry(*indirect,element_t,list);
prev->next = (*indirect)->next;
(*indirect)->next->prev = prev;
head->prev->next = head;
free(deleted_node);
return true;
}
```
用教材上教的快慢指標去實作,但不一樣的是中止條件也有變化,因為是**circular** linked list所以中止條件不能再是 fast&&fast->next 不然會導致無限迴圈,所以第一步驟應該逝去構思中止條件.
> [name=HongWei][time=Sat,Feb 18, 2023 7:10 PM]
第一個想法和 q_size()一樣,用一個 pointer start 來紀錄 queue 的起始位置,但和 q_size()不同的地方在於一次需要兩個條件來達成 fast!=start 和 fast->next!=start
> [name=HongWei][time=sun,Feb 19, 2023 7:18 PM]
第二個想法,製造和 singular linked list一樣的情況,也就是最後一個 node->next 為NULL,所以將 head->prev->next = NULL寫入,使得 for(;fast&&fast->next;)還能夠使用,並記得要在最後加回 head->prev->next = head;
> [name=HongWei][time=sun,Feb 19, 2023 9:08 PM]
### q_delete_dup
第一個想法是用 two pointer (start,end) 去實作
> [name=HongWei][time=sun,Feb 19, 2023 9:22 PM]
首先要有兩個 type element_t* 的 object ,如以下
```c
struct list_head *start=head->next;
element_t *curr = container_of(start,element_t,list);
element_t *next = container_of(start->next,element_t,list);
```
再來我們要去考慮的是如何刪除重複的節點,用了一個 do-while loop 去做到這件事情,若 strcmp(curr->value ,next->value) == 0 , 則刪掉 next 這個 object ,並在此之前將 next->list 指向的下個節點記錄下來
```c
if(!strcmp(curr->value,next->value)){
do{
struct list_head* temp = next->list.next;
list_del_init(&next->list);
q_release_element(next);
if(temp==head){
break;
}
next = container_of(temp,element_t,list);
}while(!strcmp(curr->value,next->value));
safe = start->next;
list_del_init(&curr->list);
q_release_element(curr);
}
```
### q_swap
```c
void q_swap(struct list_head *head)
{
if(!head || list_empty(head) || list_is_singular(head)){
return;
}
int count = 1;
int swap_number = q_size(head)/2;
struct list_head *p1=head->next,*p2=head->next->next;
while(count<=swap_number){
/*condition1*/
struct list_head* temp = p1->prev;
p1->prev = p2;
p1->next = p2->next;
p2->prev = temp;
p2->next = p1;
/*condition2*/
p1->next->prev = p1;
p2->prev->next = p2;
/*update the position*/
p1 = p1->next;
p2 = p1->next;
count+=1;
}
}
```
假設互換的 pair 為 node1 , node2 ,且node1->next = node2,node2->prev=node1
情況分兩種,分別是 **node1 和 node2自己的 prev 和 next** ,這組 **pair的左右兩個 node 和 node1,node2 的關係**也要考慮進去,並將 while loop 的中止條件設成需要做幾組的 swap.
> [name=HongWei][time=Mon,Feb 20, 2023 10:45 PM]
### q_reverse
```c
void q_reverse(struct list_head *head) {
if(!head){
return;
}
struct list_head* start = head;
int node_number = q_size(head);
while(node_number>=0){
struct list_head* temp = start->prev;
start->prev = start->next;
start->next = temp;
start = start->next;
node_number-=1;
}
/*head = head->next*/
}
```
從 head 出發,並針對每一個 node 都做一次 prev 和 next的轉換,做 node_number+1次,最後會停在原本的第一個 node,最後要用 head=head->next 將其指回開頭.
> [name=HongWei][time=Sun,Feb 19, 2023 9:22 PM]
### q_reverseK
想法是每隔 k 個 node 反轉一次再連接回 list
> [name=HongWei][time=fri,Feb 23, 2023 10:50 pM]
利用 q_reverse 和 list_cut_position() 來完成這段實作 , 首先若 count 不能夠整除則代表一組該 reverse 的 node還沒有尋訪完 , 則 count+1 直到能夠整除 k, 若能整除 k , 利用 list_cut_position() 讓從開頭的 node 到現在位置的 node 連接到我們的 temp_node ,用 reverse() 反轉,再把他連接到 temp 這個 list 上面, 這裡要注意用 list_split() 而不是 list_split_tail() 是因為這樣順序才會正確：
temp -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 , k=3
list_split( reverse(1->2->3) )
temp -> 3 -> 2 -> 1 -> 4 -> 5 -> 6
但還需要更新 temp 此時的位置,若 temp 位置不變,則
temp -> 3 -> 2 -> 1 -> 4 -> 5 -> 6 , k=3
list_split( reverse(4->5->6) )
temp -> 6 -> 5 -> 4 -> 3 -> 2 -> 1
但答案是
temp -> 3 -> 2 -> 1 -> 4 -> 5 -> 6
所以我們知道 temp 在第二次 split 的位置要是 node 1
所以我們需要 temp = safe->prev , 使得 temp 能夠將位置移到 node 1 上面 讓順序正確
> [name=HongWei][time=fri,Feb 24, 2023 05:50 aM]
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head || k <= 1)
return;
struct list_head *node=head->next;
struct list_head *safe=node->next;
struct list_head *temp=head;
LIST_HEAD(temp_node);
int count = 1;
while(node!=head){
if(count==k){
list_cut_position(&temp_node,temp,node);
q_reverse(&temp_node);
list_splice_init(&temp_node, temp);
count = 0;
temp = safe->prev;
}
count +=1;
node = safe;
safe = node->next;
}
}
```
### q_merge
題目的all queues都為sorted的,所以我們的主要目的就是利用先前所作的 merge_two_list(),來實作,那根據上課教材,可以發現 merge 方式不同,效益也會有所差距.
最直接的方法,就是第一條queue接上剩下的queue,這樣需要 merge n 次.
串接 queue[i] 和 queue[i+interval]
或是頭尾合併也 ok
### q_sort
#### 原本的寫法
```c
void q_sort(struct list_head *head)
{
/*merge sort*/
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
int path = 1;
int middle = q_size(head)/2;
/*left:contain the value from 1 to middle , right: contain the value from middle+1 to head->prev*/
struct list_head *left,*right;
/*left:contain the value from 1 to middle , right: contain the value from middle+1 to head->prev*/
struct list_head *mid = head->next;
INIT_LIST_HEAD(&left);
INIT_LIST_HEAD(&right);
while(path<=middle)
{
mid = mid->next;
path+=1;
}
/*left:(left,head,middle)*/
/*right:(right,head,head->prev)*/
list_cut_position(&left,head,mid);
list_cut_position(&right,head,head->prev);
q_sort(&left);
q_sort(&right);
/*Compare the value between left and right*/
while(list_empty(&left)&&list_empty(&right)){
if(strcmp(list_first_entry(&left,element_t,list)->value,list_first_entry(&right,element_t,list)->value)<=0){
list_move_tail(left.next,head);
}
else{
list_move_tail(right.next,head);
}
}
/*merge the remain part of the right or left*/
list_splice_tail(&left,head);
list_splice_tail(&right,head);
}
```
採取遞迴的方式去實作 merge sort,利用 q_size() 除以2得到 middle 的位置,並用兩個 type list_head* 的 object,分別是 left 和 right,並接著遞迴,最後的迴圈則是將 left 和 right 根據 value 大小 merge 在一起.
> [name=HongWei][time=mon,Feb 20, 2023 8:26 PM]
兩個 for loop 可以改掉,利用 list_cut_position()來得到 left 和 right,且宣告完 left 和 right 不需INIT_LIST_HEAD()來初始化因為在 list_cut_position() 裡也有了
> [name=HongWei][time=mon,Feb 20, 2023 9:01 PM]
找中心點 middle ,方式為利用 q_size(),再用一個 while loop 來尋訪到 middle 的 node ,並利用**list_cut_position**(&left,head,middle) 來將node 放入 obect left 裡 ,且根據 function 的操作我們知道 head->next = middle ->next,所以我們可以繼續用 list_cut_position(&right,head,head->prev) 來將剩下的 node 放置 object right裡.
> [name=HongWei][time=mon,Feb 20, 2023 9:49 PM]
:::danger
錯的,除了開發其他寫法外,還在理解錯的地方
> [name=HongWei][time=mon,Feb 20, 2023 9:49 PM]
:::
---
#### 其他寫法
:::warning
這標題不明確，以下討論的內容並非「寫法」，而是策略和考量因素的落差。
:notes: jserv
:::
參考 [komark06](https://hackmd.io/@komark06/SyCUIEYpj) 和上課教材 [你所不知道的c語言:linked list](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)開始分開實作 merge_two_list() 和 merge_sort().並發現自己想要中間的節點時都沒有運用到快慢指標且指標的指標也沒有運用,只有看卻不會運用需要改善
> [name=HongWei][time=Sat,Feb 20, 2023 00:25 aM]
```c
static struct list_head* mergesort(struct list_head* head)
{
if(!head || !head->next){return head;}
// Use the slow and fast pointer to find out the middle node of the list
struct list_head* fast=head->next,*slow=head;
for(;fast&&fast->next;fast=fast->next->next){
slow = slow->next;
}
//Now,object slow is in the middle of the list.
fast =slow->next; // generate the type list_head* object right
slow->next = NULL; // generate the type list_head* object left = head
return merge_two_list(mergesort(head),mergesort(fast));
}
```
和自己的方法不同的地方就是,用教材上的快慢指標來得到 the middle node of the list,且不需要list_cut_position()的 function 把 head 分開,因為當 while loop 結束時, slow 會停在 middle node,此時只先將 fast = slow->next 來當右半部份 ,再用 slow->next = NULL 使得左半部份也完成
> [name=HongWei][time=tue,Feb 21, 2023 03:58 aM]
```c
struct list_head *merge_two_list(struct list_head *left,
struct list_head *right)
{
struct list_head *head = NULL, **indirect = &head, **cur = NULL;
while (left && right) {
if (strcmp(container_of(left, element_t, list)->value,
container_of(right, element_t, list)->value) >= 0) {
cur = &right;
} else {
cur = &left;
}
*indirect = *cur;
indirect = &(*indirect)->next;
*cur = (*cur)->next;
}
*indirect = (struct list_head *) (void *) ((uintptr_t) (void *) left |
(uintptr_t) (void *) right);
return head;
}
```
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
head->prev->next = NULL;
head->next = mergesort(head->next);
struct list_head *ptr = head;
for (; ptr->next; ptr = ptr->next)
ptr->next->prev = ptr;
ptr->next = head;
head->prev = ptr;
}
```
### q_descend
想法是先reverse()一次,再讓 head->next 當成 pivot ,然後在尋訪整個 list , 若遇到比 pivot->value 小的就 list_del() ,若遇到比 pivot->value 大的就將 pivot 換成 item(也就是尋訪所在的位置),因此只需要 O(n)
```c
int q_descend(struct list_head *head)
{
if(!head||list_empty(head)){
return 0;
}
if(list_is_singular(head)){
return 1;
}
q_reverse(head);
element_t *pivot = list_first_entry(head,element_t,list);
element_t *item=NULL,*is=NULL;
list_for_each_entry_safe(item,is,head,list){
if(strcmp(pivot->value,item->value)>0){
list_del(&item->list);
q_release_element(item);
}
else{
pivot = item;
}
}
q_reverse(head);
return q_size(head);
}
```
> [name=HongWei][time=tue,Feb 21, 2023 09:52 pM]
若沒有加上 q_release_element(item) 會出現
:::danger
ERROR: Freed queue, but 4 blocks are still allocated
:::
因為仔細看 list_del() 的實作的話,被 delete 的 node 還存在,所以需要釋放 element.
> [name=HongWei][time=fri,Feb 24, 2023 05:50 aM]
:::info
test 分數： 95/100
:::
---
## Valgrind + 自動測試程式
### 在 lab0c 執行 valgrind
```shell
$ make valgrind
```
發現大部分的結果都如下
```
==5860== 56 bytes in 1 blocks are still reachable in loss record 2 of 4
==5860== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==5860== by 0x10F1CB: test_malloc (harness.c:133)
==5860== by 0x10F5D0: q_new (queue.c:22)
==5860== by 0x10CCA5: do_new (qtest.c:175)
==5860== by 0x10DEB5: interpret_cmda (console.c:181)
==5860== by 0x10E46A: interpret_cmd (console.c:201)
==5860== by 0x10E86B: cmd_select (console.c:610)
==5860== by 0x10F157: run_console (console.c:705)
==5860== by 0x10D2A7: main (qtest.c:1250)
```
memory-leak 中的 still-reachable: 程式結束時有未釋放的記憶體，不過卻還有指標指著，通常會發生在 global 變數,即便是在所用的函式庫裡頭配置的記憶體，也可偵測到，這也是動態分析手法的優勢。
---
### 自動測試程式
#### 追蹤記憶體位置與釋放
在 lab0-c 所使用的 malloc 和 free 為
```c
#define malloc test_malloc
#define free test_free
```
也就是他和一般的 malloc() 和 free() 不同 , 像 malloc() 的記憶體會紀錄在一個 allocated 的 doubled linked list ,且 allocate 的 type 為以下
```c
typedef struct __block_element {
struct __block_element *next, *prev;
size_t payload_size;
size_t magic_header; /* Marker to see if block seems legitimate */
unsigned char payload[0];
/* Also place magic number at tail of every block */
} block_element_t;
```
其中 payload[0] 是令我想要把這份主題記錄下來的原因 , 該成員利用了 GCC 中的 **array of length zero**. 使得我們可以使用 flexible memory allocation ,實作 test_malloc( size )回傳的記憶體大小為 sizeof(block_element_t)+ sizeof(size_t)+ size, 然而 sizeof(char* payload[0]) = 0 , 為什麼還可以利用額外的 size 來改變分配的記憶體大小 , 根據 [C Struct Hack - Structure with variable length array](http://frankchang0125.blogspot.com/2013/01/c-struct-hack-structure-with-variable.html) 得知, **GNU C compiler 預設不會檢查 Array index out of bound** 的這個問題 , 因此才得以成立.
文中也指出了用這項技巧的弊端,
```c
struct line{
int num;
char content[0];
}
struct lines{
struct line it;
int num1;
}
int main(){
struct lines ls;
strncpy(ls.it.content,"happy",strlen("happy")+1);
}
```
可以發現宣告 structure line ls 時, compiler 給予的記憶體大小為 sizeof(struct line) + sizeof(int) = 8 bytes .也就是如果我們試圖寫入超過 4 byes 就會發生錯誤 stack smashing detected .
> [name=HongWei][time=Sun,Feb 26, 2023 9:50 PM]
---
## 亂數 + 論文閱讀
### qtest 中加入 shuffle 的功能
```c
int len = q_size(head);
/*So, the random number that we generate is between 0 ~ len-1*/
while(len-1>=0){
struct list_head* old=head->next;
/*In order to generate the number between 0~ len-1 , use module %*/
int random_number = rand()%len;
for(;random_number>0;random_number--){
old = old->next;
}
/*Every choice add to the tail of list to generate the random order of queue*/
list_del_init(old);
list_add_tail(old,head);
len-=1;
```
利用 rand() 來產生亂數,並利用 mod 使得範圍產生亂數的範圍能夠在 0 ~ len-1 之間 , 並在最後選的 node 插入 list tail,重複到 len-1=0,使得每個node都被選過了, **len-=1** 和 **list_add_tail**() 讓每一個 iteration 都能確保不會選到已經選過的 node.
> [name=HongWei][time=Sat,Feb 25, 2023 10:54 PM]
```shell
cmd> new
l = []
cmd> it a
l = [a]
cmd> it b
l = [a b]
cmd> it c
l = [a b c]
cmd> it d
l = [a b c d]
cmd> shuffle
l = [b c a d]
cmd> shuffle
l = [d c a b]
cmd> shuffle
l = [d b a c]
cmd> shuffle
l = [a d b c]
cmd>
```
---
### 研讀 Dude, is my code constant time?
#### 何謂 Side Channel Attack?
從數學的角度去出發,電腦中的訊號傳輸就像是一個函數 ,給什麼輸入就會有什麼輸出,但若從物理的角度出發,電腦運作時會產生各式各樣**為了運作而附帶的物理現象**, 時間,功率,聲音等等,在[Hacker Lexicon: What Is a Side Channel Attack?](https://www.wired.com/story/what-is-side-channel-attack/) 也有提到一個例子,有人將可以偵測電磁波的儀器來觀察電腦電磁波的變化以此來獲得此電腦的金鑰 , 其中 timing attack 也屬於 side channel attack的一種 ,在論文[Timing Attacks on Implementations of Die-Hellman, RSA, DSS, and Other Systems](https://paulkocher.com/doc/TimingAttacks.pdf) 有提到 RSA algorithm , 接收方要解密時要用 $y^x mod(n)$ 其中 y 是加密過的 message, x 為 private key , y 可以藉由竊聽來得到,所以 attack 的目的就是為了要得到 private key 以此來聽到message. 原文中提到了這段話
> The necessary information and timing measurements might be obtained by passively eavesdropping on an interactive protocol, since an attacker could record the messages received by the target and measure the amount of time taken to resp ond to each y .
> [name=HongWei][time=Fri,Feb 25, 2023 1:54 AM]
#### dudect
從上述的例子可以得出,我們得盡量避免會造成 secret-dependent 的原因 , 其中此篇論文提到的方法有 Valgrind,可以偵測 secret-dependent path and memory access 的工具都會受限於硬體相關的認知
Sign in with Wallet
Connect another wallet