--- tag: linux2022 --- # 2022q1 Homework1 (lab0) contributed by < happyjack91630 > ### Reviewed by `kevinshieh0225` - `q_free` 逐一拜訪可用 `list_for_each_safe` - 根據 `list.h` : `#define list_entry(node, type, member) container_of(node, type, member)` - 函式標題打錯很多字喔 - `q_delete_mid` 將 `do-while` 改為 `while` 可使的若佇列長度為 1 時，少做一次指派。 - `q_shuffle` 可用 `list_move_tail` 取代字串操作。 ## 實驗環境 ```shell $ gcc --version gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian Address sizes: 39 bits physical, 48 bits virtual CPU(s): 8 On-line CPU(s) list: 0-7 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 142 Model name: Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz Stepping: 12 CPU MHz: 1800.000 CPU max MHz: 3900.0000 CPU min MHz: 400.0000 BogoMIPS: 3600.00 Virtualization: VT-x L1d cache: 128 KiB L1i cache: 128 KiB L2 cache: 1 MiB L3 cache: 6 MiB NUMA node0 CPU(s): 0-7 ``` ## [作業要求](https://hackmd.io/@sysprog/linux2022-lab0) * 詳細閱讀 [lab0](https://hackmd.io/@sysprog/linux2022-lab0) 說明，依據指示著手修改 queue.[c] 和連帶的檔案，測試後用 Git 管理各項修改。 - [x] `q_new`: 建立新的「空」佇列 - [x] `q_free`: 釋放佇列所佔用的記憶體 - [x] `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則) - [x] `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則) - [x] `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點 - [x] `q_release_element`: 釋放特定節點的記憶體空間 - [x] `q_size`: 計算目前佇列的節點總量 - [x] `q_delete_mid`: 移走佇列中間的節點 - [x] `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點 - [x] `q_swap`: 交換佇列中鄰近的節點 - [x] `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點 - [x] `q_sort`: 以==遞增順序==來排序鏈結串列的節點 * 在 qtest 提供新的命令 shuffle - [x] Fisher–Yates shuffle 演算法 ## 針對佇列的操作 ### 結構體說明 ```c= struct list_head { struct list_head *prev; struct list_head *next; }; ``` `struct list_head`為 `list.h` 中定義的結構，經由`prev`與`next`分別指向前一個和下一個節點，便能實作circular double-linked-list。 ```c= typedef struct { char *value; struct list_head list; } element_t; ``` `struct element_`為 `queue.h` 中定義的結構，這結構裡面存了一組 char array 和 `list_head`用來記錄前後節點。 ![](https://i.imgur.com/1z2jjlm.png) > 圖修改自[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) ## 針對佇列的操作 ### q_new 建立新的「空」佇列，若沒有配置指定大小的記憶體，則回傳 NULL。 ```c= struct list_head *q_new() { struct list_head *new = malloc(sizeof(struct list_head)); if (!new) { return NULL; // malloc fail } INIT_LIST_HEAD(new); return new; } ``` 建立新的「空」佇列，就是要將`prev`與`next`指標指向自己，可以利用`list.h`裡的`INIT_LIST_HEAD`此巨集函式來處理。 ![](https://i.imgur.com/L7vOD6Z.png) ### q_free 釋放佇列所佔用的記憶體 ```c= void q_free(struct list_head *l) { if (l == NULL) { return; } struct list_head *tmp = l->next; while (tmp != l) { element_t *del = container_of(tmp, element_t, list); tmp = tmp->next; free(del->value); free(del); } free(tmp); } ``` 為了要先避免`l`為空，要先判斷是否為`NULL`，如果不是才執行迴圈。 這裡要使用到`container_of`此巨集函式，用來獲得包含此`list_head`的`elemet_t`的地址，進一步將此`element_t`裡的`value`以及此`element_t`釋放掉。 ```c= //#define container_of(node, type, member) element_t *del = container_of(tmp, element_t, list); //container of便是通過list_head的地址(tmp)計算得到element_t(Node 0)的起始位置 ``` ![](https://i.imgur.com/qNre0jS.png) #### :memo: 小問題 `container of`和`list_entry`這兩個巨集函式都是利用member的地址(node)計算得到type的起始位置。不太明白這兩個函式的差異性? ### q_inset_head 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則) ```c= bool q_insert_head(struct list_head *head, char *s) { if (head == NULL) { return false; } element_t *new = malloc(sizeof(element_t)); if (new == NULL) { return false; } int char_size = strlen(s); new->value = malloc(char_size + 1); if (new->value == NULL) { free(new); return false; } memcpy(new->value, s, char_size); //memcpy(dst,src,size); new->value[char_size] = '\0'; list_add(&new->list, head); return true; } ``` 要先`malloc`出`element_t`可用的地址空間`(new)`，如果`malloc`失敗則直接return false，反之則利用`strlen`算出`s`的字元數`char_size`，用來`malloc`出`new->value`此字元串列所需的空間，這邊要小心，由於必須多儲存一個空字元`\0`，所以要創`char_size + 1`的空間。只要有使用`malloc`，要檢查是否有創立成功，如果沒有則必須連同前面創的`new`釋放掉，才不會造成memory leak。利用`memcpy`來將`s`複製進`new->value`空間裡。最後在使用`list_add`此函式將`new`插入到head。 ### q_inset_tail 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則) ```c= bool q_insert_tail(struct list_head *head, char *s) { if (head == NULL) { return false; } element_t *new = malloc(sizeof(element_t)); if (new == NULL) { return false; } int char_size = strlen(s); new->value = malloc(char_size + 1); if (new->value == NULL) { free(new); return false; } memcpy(new->value, s, char_size); new->value[char_size] = '\0'; list_add_tail(&new->list, head); return true; } ``` 與前一個function`q_insert_head`操作邏輯一樣，只是將`list_add`換成`list_add_tail`，就能將new插入到queue的尾巴了。 ### q_remove_head 在佇列開頭 (head) 移去 (remove) 給定的節點 ```c= element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (head == NULL || list_empty(head)) { return NULL; } element_t *remove_head = list_first_entry(head, element_t, list); // for head entry if (remove_head == NULL) { return NULL; } list_del(&remove_head->list); if (sp) { memcpy(sp, remove_head->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return remove_head; } ``` 要移去開頭的節點，必須得知開頭節點以及對應的`element_t`的地址，這時可以使用跟`container of`一樣功能的巨集函式，就是`list_first_entry`，差別在於`list_first_entry`是專門用在找到開頭節點資訊的函式。remove的要求是斷開與其他節點的連結，所以只需要用`list_del`就能斷開了，不需要`free`掉其對應的`element_t`的資訊。最後再將`head`的`value`放進`sp`裡面(要注意的是如果`value`的大小超過了`bufsize`，那只需要放入`bufsize`容量的`value`即可)。 ### q_remove_tail 在佇列開頭 (head) 移去 (remove) 給定的節點 ```c= element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (head == NULL || list_empty(head)) { return NULL; } element_t *remove_tail = list_last_entry(head, element_t, list); // for tail entry if (remove_tail == NULL) { return NULL; } list_del(&remove_tail->list); if (sp) { memcpy(sp, remove_tail->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return remove_tail; } ``` 與前一個function`q_remove_head`操作邏輯一樣，只需要使用`list_last_entry`，就能取得`tail`對應的`element_t`的地址資訊了。 ### q_release_element 釋放特定節點的記憶體空間 ```c= void q_release_element(element_t *e) { free(e->value); free(e); } ``` ### q_szie 計算目前佇列的節點總量 ```c= int q_size(struct list_head *head) { if (head == NULL) { return 0; } int length = 0; struct list_head *node; list_for_each (node, head) { length++; } return length; } ``` 在不更改原有存在的結構體，必須遍歷所有的queue節點，才能算出queue的長度為何。這裡可以使用`list_for_each`此巨集函式，來幫助我們遍歷所有的節點，進而計算出長度。 ### q_delete_mid 移走佇列中間的節點 ```c= bool q_delete_mid(struct list_head *head) { if (head == NULL || list_empty(head)) { return false; } struct list_head *slow_ptr = head; struct list_head *fast_ptr = head; do { slow_ptr = slow_ptr->next; fast_ptr = fast_ptr->next->next; } while (fast_ptr->next != head && fast_ptr != head); element_t *mid_node = list_entry(slow_ptr, element_t, list); // slow_ptr will be the middle list_del(slow_ptr); free(mid_node->value); free(mid_node); return true; } ``` ![](https://i.imgur.com/OqJe3gf.png) > 圖取自[GeeksforGeeks - Find the middle of a given linked list](https://www.geeksforgeeks.org/write-a-c-function-to-print-the-middle-of-the-linked-list/) 利用類似single link-list找middle node的原理運用在double circular link-list，一個`slow_ptr`每次只往前進一步，一個`fast_ptr`每次往前進兩步 只要`fast_ptr`或者`fast_ptr->next`到了`head`，則此時的`slow_ptr`就會是整條link-list的中間點了。這題要注意題目為q_**delete**_mid，所以不只要斷開連結，也要將該節點的`element_t`的所有資訊都刪掉。 ### q_delete_dup(還要再優化) 在已經排序的狀況，移走佇列中具備重複內容的節點 ```c= bool q_delete_dup(struct list_head *head) { if (head == NULL || list_empty(head)) { return false; } struct list_head *cur = head->next; element_t *cur_e; bool flag = false; // record is cur duplicate ? while (cur->next != head) { cur_e = list_entry(cur, element_t, list); element_t *cur_next_e = list_entry(cur->next, element_t, list); if (strcmp(cur_e->value, cur_next_e->value) == 0) { struct list_head *cur_next_next = cur->next->next; cur->next = cur_next_next; cur_next_next->prev = cur; free(cur_next_e->value); free(cur_next_e); flag = true; // cur_e->value == cur_next_e->value, so cur is duplicate } else { if (flag) { // cur is duplicate so need to be delete cur->next->prev = cur->prev; cur->prev->next = cur->next; cur = cur->next; free(cur_e->value); free(cur_e); } else { cur = cur->next; flag = false; } } } if (flag) { // queue only left one item(cur) and this item also duplicate cur->next->prev = cur->prev; cur->prev->next = cur->next; // cur = cur->next; free(cur_e->value); free(cur_e); } return true; } ``` 一開始先設一個`flag`，用來判斷每次的`cur`是否為重複`value`的一員。 :::info ```c= if (strcmp(cur_e->value, cur_next_e->value) == 0) { struct list_head *cur_next_next = cur->next->next; cur->next = cur_next_next; cur_next_next->prev = cur; free(cur_next_e->value); free(cur_next_e); flag = true; // cur_e->value == cur_next_e->value, so cur is duplicate ``` 檢查`cur_e->value`和`cur_next_e->value`是否一樣，一樣的話就把`cur_next`刪掉，且`cur`為重複`value`的一員，所以`flag`變成`true`。 ![](https://i.imgur.com/VNpttOz.png) ::: :::info ```c= if (flag) { // cur is duplicate so need to be delete cur->next->prev = cur->prev; cur->prev->next = cur->next; cur = cur->next; free(cur_e->value); free(cur_e); } else { cur = cur->next; flag = false; } ``` 如果`flag`為`true`，則要將目前的`cur`刪掉，反之`cur`就保留，往下個節點前進。 ![](https://i.imgur.com/zytf6eK.png) ::: :::info ```c= if (flag) { // queue only left one item(cur) and this item also duplicate cur->next->prev = cur->prev; cur->prev->next = cur->next; // cur = cur->next; free(cur_e->value); free(cur_e); } ``` 這個條件式會成立的場景為，全部節點只剩下`cur`一點，而且此節點為重複的一員`(flag =true)`，所以也要將`cur`刪掉。 ![](https://i.imgur.com/3pCoSoZ.png) ::: ### q_swap(還要再優化) 交換佇列中鄰近的節點 ```c= void q_swap(struct list_head *head) { // https://leetcode.com/problems/swap-nodes-in-pairs/ if (head == NULL) { return; } struct list_head *cur = head->next; struct list_head *prev = head; struct list_head *next = cur->next; while (cur->next != head && cur != head) { cur->next = next->next; next->next->prev = cur; cur->prev = next; next->next = cur; next->prev = prev; prev->next = next; // prev->prev =cur; prev = cur; cur = cur->next; next = cur->next; } } ``` 此題參考[leetcode 24.Swap Node in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/discuss/222534/C-0ms)的做法，只是要再考慮`prev`如何連接就好了。 ### q_reverse 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點 ```c= void q_reverse(struct list_head *head) { if (head == NULL || list_empty(head)) { return; } struct list_head *cur = head; struct list_head *tmp; do { tmp = cur->prev; cur->prev = cur->next; cur->next = tmp; cur = cur->prev; } while (cur != head); } ``` 此題參考[GeeksforGeeks - Reverse a link list](https://www.geeksforgeeks.org/reverse-a-linked-list/)的做法，只是我是從tail端reverse回來，且必須多考慮`prev`的方向變化。 ### q_sort > 參考 kevinshieh0225 以遞增順序來排序鏈結串列的節點 ```c= struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2) { struct list_head *head = NULL, **ptr = &head, **cur; for (cur = NULL; L1 && L2; *cur = (*cur)->next) { // compare accending pair by pair element_t *node1 = container_of(L1, element_t, list); element_t *node2 = container_of(L2, element_t, list); cur = (strcmp(node1->value, node2->value) <= 0) ? &L1 : &L2; *ptr = *cur; ptr = &(*ptr)->next; } *ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2); return head; } static struct list_head *mergesort_list(struct list_head *head) { if (!head || !head->next) { return head; } struct list_head *slow = head; for (struct list_head *fast = head->next; fast && fast->next; fast = fast->next->next) { slow = slow->next; } struct list_head *mid = slow->next; slow->next = NULL; struct list_head *left = mergesort_list(head); struct list_head *right = mergesort_list(mid); return mergeTwoLists(left, right); } void q_sort(struct list_head *head) { if (head == NULL || list_empty(head)) { return; } head->prev->next = NULL; // circular to non-circular head->next = mergesort_list(head->next); struct list_head *ptr = head; while (ptr->next) { // reconstruct circular link list (prev) ptr->next->prev = ptr; ptr = ptr->next; } ptr->next = head; head->prev = ptr; } ``` 此題雖然要使用circular double link-list做merge sort，但是其實我們可以先把circular變成non-circular`(head->prev->next = NULL)`就會容易許多。在副程式`mergesort_list`，也是使用`slow_ptr`和`fast_ptr`來切出link-list的middle node，就能拿middle node的左邊(含middle node)和右邊去做排序`mergeTwoLists`。`mergeTwoLists`就是參考了[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)裡的**Merge Sort的實作**。要注意得是要使用`uintptr_t(typedef unsigned long int uintptr_t)`這項型態是必須多`#include <stdint.h>`才能使用。 ## qtest 新功能實作：Fisher-Yates shuffle > 參考 kevinshieh0225 先在`qtest.c`裡找到一個`console_init`的function是專門用來放`./qtest`所打的command，所以在這裏面加上一行等等所需要用的shufle。 ```c= static void console_init() { ..... ADD_COMMAND(shuffle, " | shuffle by Fisher-Yates shuffle"); ..... } ``` Fisher-Yates shuffle則是參考了[【筆記】洗牌演算法：Fisher-Yates Shuffle](https://medium.com/@globelex65/%E7%AD%86%E8%A8%98-%E6%B4%97%E7%89%8C%E6%BC%94%E7%AE%97%E6%B3%95-fisher-yates-shuffle-c9feeb463154)實做出來。 ```c= void q_shuffle(struct list_head *head) { if (head == NULL || list_empty(head)) { return; } int q_length = q_size(head); if (q_length == 1) { return; } struct list_head *cur; for (cur = head->next; cur->next != head; cur = cur->next) { int target; do { target = rand() % q_length; } while (target == 0); // prevent target = cur struct list_head *target_list = cur; for (int i = 0; i < target; i++) { target_list = target_list->next; } element_t *cur_e = list_entry(cur, element_t, list); element_t *target_list_e = list_entry(target_list, element_t, list); char *tmp = cur_e->value; cur_e->value = target_list_e->value; target_list_e->value = tmp; q_length--; } } ``` 一開始本來想將`q_shuffle`定義在`queue.c`裡，同時也要將`q_shuffle`定義在`queue.h`，但是如果這樣做，在`git commiat -a`因為無法修改`queue.h`而報錯，所以只能將`q_shuffle`放在`qtest.c`裡面。 ```c= static bool do_shuffle(int argc, char *argv[]) { if (argc != 1) { report(1, "%s takes no arguments", argv[0]); return false; } if (!l_meta.l) report(3, "Warning: Calling shuffle on null queue"); error_check(); set_noallocate_mode(true); if (exception_setup(true)) q_shuffle(l_meta.l); exception_cancel(); set_noallocate_mode(false); show_queue(3); return !error_check(); } ``` 最後在實作能被`ADD_COMMAND`呼叫到的function，此function參考了`do_reverse`所寫的。
Last changed by  
 
于乃喆
386

Read more

Linux 核心實作 hankmd 筆記

GitHub 2022q1 Homework1 (lab0) 2022q1 Homework1 (quiz1) 2022q1 Homework2 (quiz2) 2022q1 Homework3 (fibdrv)

7/4/2022
2022q1 Project (cpumemory)

contributed by ??? 目標 [ ] 閱讀 Ulrich Drepper 於 2007 年撰寫的論文《 [What Every Programmer Should Know About Memory] [ ] SRAM DRAM 讀取差異 [ ] Virtual Memory [ ] TLB 作用 [ ] Cache Line Sharing 成本 [ ] MESI

6/29/2022
2022-04-04

contributed by < happyjack91630 > happyjack91630 GitHub 測驗 1 利用上述 SIMD within a register (SWAR) 的技巧，我們可改寫為以下 memchr_opt 函式: #include <stddef.h> #include <stdint.h> #include <limits.h> #include <string.h>

4/5/2022
2022q1 Homework4 (quiz4)

contributed by < happyjack91630 > 作業需求 :::danger 注意書寫規範和使用通順的漢語。 :notes: jserv ::: 測驗 1 : $\lceil log_2(x) \rceil$

4/5/2022
Read more from 于乃喆
Published on HackMD