HackMD
2024q1 Homework1 (lab0)
conftributed by < jason50123 >
Reviewed by jimmy01240397
if (!head)
return NULL;
- else {
INIT_LIST_HEAD(head);
return head;
- }
- q_remove_head and q_remove_tail：依據 glibc 2.36 的實作，沒必要額外計算字串長度後再後面添加
'\0'
char *
STRNCPY (char *s1, const char *s2, size_t n)
{
size_t size = __strnlen (s2, n);
if (size != n)
memset (s1 + size, '\0', n - size);
return memcpy (s1, s2, size);
}
- size_t copy_size;
- if (strlen(tmp->value) < (bufsize)) {
- copy_size = strlen(tmp->value);
- } else {
- copy_size = bufsize - 1;
- }
- strncpy(sp, tmp->value, copy_size);
- sp[copy_size] = '\0';
+ strncpy(sp, tmp->value, bufsize - 1);
+ sp[bufsize - 1] = '\0';
- 善用巨集展開以減少重複的程式碼，例如：
#define q_remove_base(head, sp, bufsize, from) \ if (!head || list_empty(head)) \ return NULL; \ element_t *tmp = list_##from##_entry(head, element_t, list); \ if (sp) { \ size_t copy_size; \ if (strlen(tmp->value) < (bufsize)) { \ copy_size = strlen(tmp->value); \ } else { \ copy_size = bufsize - 1; \ } \ strncpy(sp, tmp->value, copy_size); \ sp[copy_size] = '\0'; \ } \ list_del(&tmp->list); \ return tmp; element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { q_remove_base(head, sp, bufsize, first); } element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { q_remove_base(head, sp, bufsize, last); }- q_insert_head
- q_insert_tail
- q_remove_head
- q_remove_tail
- q_delete_mid：沒必要多做一次
q_size進行遍歷? 來取得長度且請避免非必要的浮點數，可以參考「你所不知道的 C 語言: linked list 和非連續記憶體」，善用快慢指標解決取得中間節點的問題。 - q_delete_dup：可使用變數儲存比較結果來減少多餘的分支
+ bool dup = false, now_dup = false;
+ now_dup = &safe->list != head && !strcmp(tmp->value, safe->value);
+ if(now_dup || dup) {
- if(&safe->list != head && !strcmp(tmp->value, safe->value)) {
list_del(&tmp->list);
q_release_element(tmp);
+ dup = now_dup;
- dup = true;
- } else if (dup) {
- list_del(&tmp->list);
- q_release_element(tmp);
- dup = false;
}
merge_two_queues: 刪除非必要的分支
int merge_two_queues(struct list_head *q1, struct list_head *q2, bool descend)
{
element_t *entry, *safe;
struct list_head *q1_head, *q2_head;
q1_head = q1;
q2_head = q2;
int count = q_size(q1) + q_size(q2);
+ long long key = &&ret ^ &&conti;
+ goto (list_empty(q2) * key) ^ &&conti;
+conti:
- if (list_empty(q2)) {
- return count;
- }
q2 = q2->next;
list_for_each_entry_safe (entry, safe, q1, list) {
- if (descend) {
- while (strcmp(entry->value,
+ while (((!!descend) * 2 - 1) * strcmp(entry->value,
list_entry(q2, element_t, list)->value) < 0) {
- if (q2->next == q2_head) {
q2 = q2->next;
list_move(q2->prev, entry->list.prev);
+ key = &&out ^ &&whi;
+ goto (onout * key) ^ &&whi;
+whi:
- goto out;
- } else {
- q2 = q2->next;
- list_move(q2->prev, entry->list.prev);
- }
}
- } else {
- while (strcmp(entry->value,
- list_entry(q2, element_t, list)->value) > 0) {
- if (q2->next == q2_head) {
- q2 = q2->next;
- list_move(q2->prev, entry->list.prev);
- goto out;
- } else {
- q2 = q2->next;
- list_move(q2->prev, entry->list.prev);
- }
- }
- }
}
out:
list_splice_tail_init(q2_head, q1_head);
+ret:
return count;
}
量化分析上述更動到底可省下多少次分支，工程人員說話要有證據。
jserv
開發環境
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$lscpu
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): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i7-11700 @ 2.50GHz
CPU family: 6
Model: 167
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 1
CPU max MHz: 4900.0000
CPU min MHz: 800.0000
BogoMIPS: 4992.00
指定佇列的操作
q_new
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
這邊使用 malloc() 來先配置一個 struct list_head 的記憶體空間，並用指標 head 去記錄他的位置。
- 先判斷使否有
malloc()成功，有則運用INIT_LIST_HEAD()來把head的 prev、next 指到自己。
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
else {
INIT_LIST_HEAD(head);
return head;
}
}
q_free
運用 list_for_each_entry_safe() 來存取整條 list_head 的結構，且因為會有 remove 掉當前節點的動作，所以必須使用 list_for_each_entry_safe() 而非 list_for_each_entry() ，參考以下註解得到此結論。
- 透過
list_for_each_entry_safe()存取完整條鏈結串列的過程中，運用q_release_element()去 free 掉struct element_t這個結構，而非將struct list_head()從鏈結串列 free 掉而已，重複此步驟來達到 q_free() 的效果。
list_for_each_entry - Iterate over list entries
* The nodes and the head of the list must be kept unmodified while
* iterating through it. Any modifications to the the list will cause undefined
* behavior.
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list)
q_release_element(entry);
free(l);
}
q_insert_head, q_insert_tail
這邊在試著用 strcpy() 的方式把原本的 input 複製到自己所 malloc 出的節點中，但在 git-push 的時候發現該方法並不安全，引述自 CERN Computer Security
- The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp.
避免非必要的項目縮排 (即 * 或 - )，以清晰、明確，且流暢的漢語書寫。
也因為這樣所以改用 strndup() 來實作
bool q_insert_head(struct list_head *head, char *s)
{
...
- size_t size = strlen(s)+1;
- node ->value = malloc(sizeof(size));
- strcpy(node->value, s);
+ node->value = strndup(s, strlen(s));
list_add(&node->list, head);
return true;
}
最後又試著用 strncpy() 來完成
bool q_insert_head(struct list_head *head, char *s)
{
...
- node->value = strndup(s, strlen(s));
+ strncpy(node->value, s, strlen(s));
+ node->value[strlen(s)] = '\0';
list_add(&node->list, head);
return true;
}
q_remove_head and q_remove_tail
原本的想法是直接透過 list_first_entry() 來拿到整條鏈結串列中的第一個 struct element_t ，並將他的 char *value 直接透過 strlen() 取得該字串的長度並直接 malloc 一塊記憶體空間給他，但後來發現在執行測試的時候會出現 core dump 的警告，也因此作了以下修改。
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
...
if (sp) {
size_t copy_size;
- copy_size = strlen(tmp ->value);
+ if (strlen(tmp->value) < (bufsize)) {
+ copy_size = strlen(tmp->value);
+ } else {
+ copy_size = bufsize - 1;
+ }
strncpy(sp, tmp->value, copy_size);
sp[copy_size] = '\0';
}
list_del(&tmp->list);
return tmp;
}
可以改進的地方: q_remove_tail() 可以用 q_remove_head(head ->prev) 來完成就可以
q_delete_mid
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
運用q_size()求出整個鏈結串列的長度，再用 for loop 讓 pointer 可以走到對的位置並 delete 掉該點
- 此處由於是要做 delete ，而不是只有 remove ，所以我除了將該 element 中的
struct list_head用list_del()移除後，再使用queue_release_element()把該點 free 掉
q_delete_dup
在遍歷鏈結串列的過程中，運用 strcmp() 去比較目前的節點的值是否跟下一個節點的值相同，若有則先將 bool dup 設成 true ，並將下面的節點進行刪除後，再回過頭將目前的 node 刪除
bool q_delete_dup(struct list_head *head){
...
list_for_each_entry_safe (tmp, safe, head, list) {
if (&safe->list != head && !strcmp(tmp->value, safe->value)) {
list_del(&tmp->list);
q_release_element(tmp);
dup = true;
} else if (dup) {
list_del(&tmp->list);
q_release_element(tmp);
dup = false;
}
}
}
q_swap
總共紀錄4個點，分別是 slow ->prev, slow, fast, fast->next ，每次去修改這四個點的 prev 以及 next ，此處應該使用 macro 將程式碼改得更為精簡。
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
struct list_head *fast, *slow, *fasttmp, *slowtmp;
slow = head->next;
fast = slow->next;
while (fast != head && slow != head) {
slowtmp = slow->prev;
fasttmp = fast->next;
slow->next = fast->next;
slow->prev = fast;
fast->prev = slowtmp;
fast->next = slow;
slowtmp->next = fast;
fasttmp->prev = slow;
slow = fasttmp;
fast = slow->next;
}
}
q_reverse
每次修改 current 以及前後 node 的 pointer
q_reverseK
先運用 q_size() 去除以 input "K" 來得到總共有幾個 groups ，並且在每個迴圈中做完的時候去把 count++ ，藉此來計算已經 reverse 了幾個 groups，然後在每一個小的 group 自己要做reverse時候，將 current node 透過 list_move() 來把它移到 group head 來達到 reverse 的效果。
改進你的漢語表達。
void q_reverseK(struct list_head *head, int k)
{
list_for_each (first, head) {
struct list_head *tmp;
tmp = first->prev;
if (count < groups) {
for (int i = 1; i < k; i++) {
second = first->next;
list_move(second, tmp);
}
}
count++;
}
}
q_merge
- q : pointer to element_t, 也就是排序過的佇列
- chain : 串了多個佇列, 也就是可能會有多條的佇列
- size : q 有幾個 element
- id : unique id
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
q_sort()
運用 merge sort 去實現
sol:
- 找到中間的節點
- 切斷 list 製作出兩個出兩個獨立的 list
- 遞迴 1
- merge
參考 link list 實作 merge sort, 和這篇文章不同的點是在 merge 以及 split 兩條 list 的時候，我們切出來的兩條 link list 會有額外的struct list_head需要去處理。
TODO:把他先處理成單向的 link list 在做處理。
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
研讀並引入lib/list_sort.c
參考 marvin0102
在研讀 list_sort 的時候法現有像以下的程式碼，但不知道他的意思，所以就去查閱了相關資料 Function-Attributes，才知道除了 packed 、 aligned 此種對記憶體管理的 function 外，還有這些像是下面的 nonnull ，可以對哪幾個傳入的參數進行非空的限制．
typedef int __attribute__((nonnull(2,3))) (*cmp_func)(void *,
struct list_head const *, struct list_head const *);
且經過閱讀程式碼後發現， list_sort 裡面的 *priv 主要是用來當 counter 且可以不用傳值進去的，所以也就在這邊把它拿掉。
- void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
+ void list_sort(struct list_head *head, list_cmp_func_t cmp)
然後在引入的過程中會發現缺少一些相關的標頭檔以及巨集，所以要在這邊將他補上。
#list_sort.c
- #include <linux/kernel.h>
- #include <linux/bug.h>
- #include <linux/compiler.h>
- #include <linux/export.h>
- #include <linux/string.h>
- #include <linux/list_sort.h>
- #include <linux/list.h>
+ #include "./list_sort.h"
#list_sort.h
+#define likely(x) __builtin_expect(!!(x), 1)
+#define unlikely(x) __builtin_expect(!!(x), 0)
+typedef unsigned char u8;
並在 q_test.c 裡面加上新的 command lsort 來提供給使用者呼叫
+ ADD_COMMAND(lsort, "Do list_sort", "");
補上對應的 git commit 超連結，並確認已進行 rebase
亂數
在 trace code 的過程中可以先找到原本我們加了 RAND 參數後， ./qtest 會透過 strcmp() 來把 need_rand 變數修改成 true ， 並在後續透過 fill_rand_string() 來產生亂數，所以以下模仿這樣的寫法，新增一個 Xorshift 的選項。
if (!strcmp(inserts, "RAND")) {
need_rand = true;
inserts = randstr_buf;
}
+ if (!strcmp(inserts, "XORS")) {
+ need_xor = true;
+ inserts = randstr_buf;
+ }
研讀 Xorshift 後發現這個方法是 Linear-feedback shift register (LFSR) 的子集合，藉由閱讀以上文獻，目前對於 LFSR 的理解為:移動前一個 bit 的 output 來當成下一個 bit 的 input，而其中 Xorshift 有一段範例程式碼，如下所示，還沒有辦法理解為什麼要左移以及右移這樣數量的 bit 。
struct xorshift32_state {
uint32_t a;
};
/* The state must be initialized to non-zero */
uint32_t xorshift32(struct xorshift32_state *state)
{
/* Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs" */
uint32_t x = state->a;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return state->a = x;
}
實驗步驟 :
透過一個 global buffer 來把每一次的 RAND、XORS 生成的亂數都存下來，然後再使用 ent 來做分析。而且在這之前我想先知道原本 用 ent 實驗中的範例linux 內建的 PRNG /dev/random 所生成出來的格式和內容是甚麼所以我就去執行了一遍。
$ head -c 100 /dev/random
B�#�!��d��]>��-��Z��5g�BKOe���_fi��d��\�KV�o�;Ϊ��������lų�̒㤛�C��`e-��P]G���(���%
結果就像上面得到了一坨的亂碼，查閱了相關資料後發現 terminal 會自己試著用 UTF-8 的方式把內容印出來，但這些字符沒有辦法以這樣的方式輸出，所以要透過16進制的方式把它印出來，也就成功印出了以下的數據
$ head -c 10 /dev/random |xxd -p
5f9c103b79ab75bb34b8
但也從這邊可以看到原本實驗的 ent 的範例 input 是沒有任何的空白鍵的，但我們目前 ./qtest 所產生的亂數，中間還會有空白鍵做分割，可能會影響到實驗效果，所以這邊做了一下比較。
#RAND 所生成的20組亂數並放到 ent 裡面的內容(有空白鍵)
mlmjir wajxqc isdrnfsj oblprodt lqixigdc ccdvnx lohhvovvs tdwoqm yeqbynkq irobrrjjc gditoxm zlppbgwon kljkaebpg auqit cxzghwghz dkxryaa hscsjgm nyhvbyxpp nrlekvurf asrjo
# ent 實驗的輸出
$ ent random_data.txt
Entropy = 4.594609 bits per byte.
Optimum compression would reduce the size
of this 170 byte file by 42 percent.
#去掉空白鍵之後
$ ent random_data.txt
Entropy = 4.641885 bits per byte.
Optimum compression would reduce the size
of this 151 byte file by 41 percent.
可以從上述的內容發現將空白鍵刪除後確實會讓亂數更亂，所以些接下來實驗就會以沒有空白鍵的亂數作為輸入值。
但在上面的結果我發現我們的 entropy 值，會比我們預期的值要小的很多，所以這中間可能是生成出來的亂數並不夠亂，所以這邊我就針對我們生成亂數的 charset 進行改動，並做了相對應的實驗，來證明說在charset裡面可以加入大小寫以及數字來讓亂數更亂。
TODO : 這邊應該可以加入其他特殊符號來讓亂數更亂
- static const char charset[] = "abcdefghijklmnopqrstuvwxyz";
+static const char charset[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
#原本 charset 的結果(只有大小寫)
$ent random_data.txt
Entropy = 4.699479 bits per byte.
#加入數字的實驗結果
$ ent random_data.txt
Entropy = 5.159285 bits per byte.
#加入大小寫跟數字
$ ent random_data.txt
Entropy = 5.949377 bits per byte.
從這邊的實驗結果可以得到 charset 應使用有大小寫英文字母以及數字來進行後續實驗可以得到較好的entropy值。
後續用 Xorshift 、RAND 各生成亂數並做比較會發現 RAND 方法產生的亂數的 entropy 會比 Xorshift 來的高一點。
#Xorshift
Entropy = 4.483300 bits per byte.
Optimum compression would reduce the size
of this 501603 byte file by 43 percent.
Chi square distribution for 501603 samples is 5509651.63, and randomly
would exceed this value less than 0.01 percent of the times.
Arithmetic mean value of data bytes is 87.2729 (127.5 = random).
Monte Carlo value for Pi is 4.000000000 (error 27.32 percent).
Serial correlation coefficient is 0.016055 (totally uncorrelated = 0.0).
#RAND
Entropy = 5.949742 bits per byte.
Optimum compression would reduce the size
of this 501789 byte file by 25 percent.
Chi square distribution for 501789 samples is 1583614.88, and randomly
would exceed this value less than 0.01 percent of the times.
Arithmetic mean value of data bytes is 87.4574 (127.5 = random).
Monte Carlo value for Pi is 4.000000000 (error 27.32 percent).
Serial correlation coefficient is 0.001818 (totally uncorrelated = 0.0).
這邊將輸出的文字檔用 python 分析後發現每個音文字母的出現次數確實沒有均勻分佈，目前還在嘗試如何解決該問題
web
本部分與 HotMercury 協作
中間修改過程看到 select, accept 等系統呼叫，但完全不知道這些系統呼叫的運作原理，所以又找了一些參考資料來閱讀，打算先理解 TCP Client/Server 的原理，參考資料，而且在閱讀這些 Linux manual page 的時候看到後面都有不同的數字，因此去查閱了 man-pages 才發現這些參數代表了許多涵義。
1 User commands (Programs)
Commands that can be executed by the user from within a
shell.
2 System calls
Functions which wrap operations performed by the kernel.
3 Library calls
All library functions excluding the system call wrappers
(Most of the libc functions).
為何不閱讀第一手材料，像是 Linux man pages 和電腦網路的教科書呢？
jason50123 感謝老師提醒，已經試著去閱讀第一手的資料，並從中獲得有效資訊
先找到整個 command line 運行的過程，會看到從 qtest.c 中的 main 呼叫 run_console ，並從 run_console 的註解中可以知道他會 run command loop 所以這邊就先看一下 run_console 會做什麼事。
而從程式碼中可以看到，裡面會先去看 use_linenoise 與否，如果沒有用的話則會跳去執行 cmd_select，且從以下程式碼可以看到，在原本程式中執行 do_web 之後，就會將 line_noise 關閉。
static bool do_web(int argc, char *argv[])
{
...
web_fd = web_open(port);
int flags = fcntl(web_fd, F_GETFL);
fcntl(web_fd, F_SETFL, flags | O_NONBLOCK);
if (web_fd > 0) {
printf("listen on port %d, fd is %d\n", port, web_fd);
use_linenoise = false;
...
}
在作業指引中可以看到要使用 select 來處理 stdin、socket ，而在參閱了 Select man-page 後才了解到，我們要先用 FD_SET 來初始化 file descriptor set ，並在後續用 FD_SET 來把對應的 Fd 加到此 set 裡面，在看完跟 select 相關的文件後，接著繼續看 do_web 裡面用到的 function call， 發現會用 web_open 去處理跟 socket 相關的內容。
從 tcp(7) 可以得知 web_open 裡面如何完成 tcp socket ，其中在呼叫 web_open 的時候，會先透過 socket() 來建立一個 tcp socket，接著透過 setsocketopt() 來設定和 socket 相關的參數，然後透過 bind() 把 socket 跟local socket address 綁在一起，最後透過 listen() 來讓 socket 可以接受新的連線。
嘗試先從 console.c 修改，透過作業指引了解到將 socket 改成 non-blocking ，會跟fcntl() 有關係，因此先去找 fcntl 如何使用 fcntl(2)
int flags = fcntl(listenfd, F_GETFL);
fcntl(listenfd, F_SETFL, flags | O_NONBLOCK);
//把 listenfd 設成 non-blocking
F_SETFL (int) : 透過此 F_SETFL 將 file descroptor 的 flag 設置成不同 access mode 、 file creation flag 。
接著 run_console 就會進到 linenoise() 裡面，而 linenoise() 主要的流程會像 linenoise()->linenoiseRaw()->linenoiseEdit()。
整合 socket 以及 linenoise 套件
改進書寫和處理授課教師要求的改正，從小處做起！
引入 tic-toc-toe
依照作業要求提示可以知道要先找到 zobrist.ch 裡面用到的 hlist 相關內容並擷取 linux/hlist 的部分程式碼，並獨立成 hlist.h。
並在 qtest.c 中先新增一個 command
+ ADD_COMMAND(ttt, "tic-tac-toe", "");
查看 ttt/Makefile 來把 ttt 需要的檔案複製到 lab-0c 專案資料夾 中，並把原本的 ttt/main.c 改為 ttt/ttt.c。
directory 是「目錄」，而非「檔案夾」(folder)
而在要著手修改 mcts 的時候，會發現在 make 的時候產生以下錯誤
/usr/bin/ld: ttt.o: in function `ttt':
/home/shrimp/linux2024/lab0-c/ttt.c:139: undefined reference to `mcts'
collect2: error: ld returned 1 exit status
make: *** [Makefile:54：qtest] 錯誤 1
後來發現這個錯誤是因為編譯器無法找到 mcts 的相關定義，從而導致了 "undefined reference to mcts" 的錯誤，所以在 makefile 內作了以下更動
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o
...
+ agents/mcts.o
且在準備將目前進度做 git-commit 的時候會發現有許多 null pointer 以及 variable scope 的相關問題須做修正，修正的相關 commit 如下
而在 trace mcts() 的過程中會發現裡面的 calculate_win_value()、simulate()、uct_score()都會用到浮點數運算，但根據作業要求告訴我們要把這些運算都改為固定精度表示，所以這邊找了 c library 提供的 libfixmatrix
不！你該自行實作 fixed point 操作，避免使用現有的函式庫，考慮因素是:
- 針對場景設計符合自身需求、兼顧精度和空間效率的實作
- 你該自己先實作過，才去比較其他實作的落差
jserv
