# linux-2023-summer: costoxff > [題目連結](https://hackmd.io/@sysprog/linux2023-summer-quiz0) ## α - 1 > 簡短複習 [AVL Tree](https://oi-wiki.org/ds/avl/), [RB Tree](https://oi-wiki.org/ds/rbtree/) 先來觀察節點結構與指標操作 ```cpp struct st_node { short hint; struct st_node *parent; struct st_node *left, *right; }; ``` ```graphviz digraph st_node { // config node[shape=record]; graph[rankdir=LR] // node n [ label="<f0> hint | <f1> *parent | {*left | *right}" ]; } ``` > [Record-based Nodes](https://graphviz.org/doc/info/shapes.html#record) 可嵌入到自定義的結構，並搭配 [container_of](https://hackmd.io/@sysprog/linux-macro-containerof) ```cpp struct st_data { void *data; struct st_node; } ``` ```graphviz digraph st_data { graph[rankdir=LR] node[shape=record]; subgraph cluster { data[label="*data"] n [ label="hint |<f1> *parent | {<f2> *left | <f3> *right}" ]; label = "st_data"; } nil[label="null"] nil1[label="null"] nil2[label="null"] n:f1 -> nil n:f2 -> nil2 n:f3 -> nil1 } ``` ```cpp #define st_root(r) (r->root) #define st_left(n) (n->left) #define st_right(n) (n->right) #define st_rparent(n) (st_right(n)->parent) #define st_lparent(n) (st_left(n)->parent) #define st_parent(n) (n->parent) ``` 使用巨集來代替繁瑣的指標操作。 展開巨集`st_rparent(n)`，變成`n->left->parent`。 取得透過 n 節點指向 left 節點的指標，再指向 left 節點的 parenet 指標。 > 注意，巨集取得的是指標，不是節點本身。 ### Function of S-Tree (1) 簡單的說明 ```cpp struct st_node *st_first(struct st_node *n); struct st_node *st_last(struct st_node *n); void st_rotate_left(struct st_node *n); void st_rotate_right(struct st_node *n); int st_balance(struct st_node *n); int st_max_hint(struct st_node *n); ``` #### `st_first` / `st_last` 以傳入的節點當作初始點，向左指標查找節點是否存在，如果存在，就呼叫自己，將當前節點的左指標傳入，遞迴查找，否則回傳當前節點指標。`st_last`則是向右的版本。 #### `st_rotate_left/right` 如同 BST 中的旋轉，參照 [Tree rotation](https://en.wikipedia.org/wiki/Tree_rotation) ![file missing](https://upload.wikimedia.org/wikipedia/commons/3/31/Tree_rotation_animation_250x250.gif) > 取自 [https://en.wikipedia.org/wiki/Tree_rotation](https://en.wikipedia.org/wiki/Tree_rotation#/media/File:Tree_rotation_animation_250x250.gif) #### `st_balance` 用來判斷節點中，左、右子樹的 hint 差值。回傳值像是 AVL Tree 的 balance factor，大於 0 代表左子樹 hint 大於右子樹，小於 0 則是相反。 #### `st_max_hint` 比較左、右子樹的 hint 並回傳最大值。用於將值附於當前節點的 hint ，可用於判斷當前節點下最長的節點連接數。 ### Function of S-Tree (2) ```cpp void st_update(struct st_node **root, struct st_node *n); void st_insert(struct st_node **root, struct st_node *p, struct st_node *n, enum st_dir d) void st_replace_right(struct st_node *n, struct st_node *r); void st_replace_left(struct st_node *n, struct st_node *l); void st_remove(struct st_node **root, struct st_node *del); ``` 為何要以 **root 傳入，詳見[指標篇](https://hackmd.io/@sysprog/c-prog/%2Fs%2FHyBPr9WGl#%E6%B2%92%E6%9C%89%E3%80%8C%E9%9B%99%E6%8C%87%E6%A8%99%E3%80%8D%E5%8F%AA%E6%9C%89%E3%80%8C%E6%8C%87%E6%A8%99%E7%9A%84%E6%8C%87%E6%A8%99%E3%80%8D) #### `st_upgdate` 以傳入的 n 節點為起點，先以`st_balance(n)`計算 hint 差值，小於 1 代表向右傾，所以進行右旋。大於 1 則是左傾，進行左旋。接著，會以`st_max_hint(n)`更新當前節點的 hint。 當更新後的 hint 等於 0 ，或更新前的 hint (prev_hint) 不等於更新後的，就沿著親代節點做遞迴式更新。 #### `st_insert` 單純的選擇要將 n 節點新增到 p 節點的左邊或右邊。 #### `st_remove` `st_replace_left\right` [Deletion in BST](https://alrightchiu.github.io/SecondRound/binary-search-tree-sortpai-xu-deleteshan-chu-zi-liao.html#delete) 節點的刪除 ### S-Tree 最後，了解對節點的操作，剩下的就可以自己針對樹的操作進行設計。 以下是[檔案](https://gist.github.com/jserv/4dfaf78cf516cc20f4bc55ce388c195d)裡提供的方法，當然也可以自己設計、改寫結構。 ```cpp struct treeint { int value; struct st_node st_n; }; int treeint_init(); int treeint_destroy(); struct treeint *treeint_insert(int); struct treeint *treeint_find(int); int treeint_remove(int); ``` ## α - 2 ## α - 3 ## β - 1 ```cpp= #include <stdint.h> static inline uintptr_t align_up(uintptr_t sz, size_t alignment) { uintptr_t mask = alignment - 1; if ((alignment & mask) == 0) { /* power of two? */ return MMMM; } return (((sz + mask) / alignment) * alignment); } ``` > MMMM = sz + mask & ~mask ### 原理分析 #### 取整函數 得出結論的想法來自於[上取整函數(ceiling function)](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions)。電腦科學中一般記作 $ceil(x)$，表示不小於x的整數中最小的一個。 $[x] = min \{ n \in \mathbb Z \ |\ x \leq n \}$ 為了方便說明，設計兩個取整的 ceiling function，一個是取整到個位數，另一個取整到十位數。 ```cpp /* function one */ int ceil(float num) { return (int) (((num + 0.9) / 1) * 1); } /* function two */ int ceil2tens(int num) { return (((num + 9) / 10) * 10); } ``` 相信大家在初學C語言時對於這樣的取整函數做法非常熟悉，第一種無疑就是加上0.9，在利用轉型(type-casting)捨去個位數後的部份。或是像第二種，利用整數除法作為捨去十位數後數字的手段。 我認為關鍵點在於兩點，**==進位==** 的條件，以及 **==捨去==** 不需要的部份。 初看上取整函數，不難看出當小數部份不為 0 時個位數加 1 (進位)，否則就保持原來的數。 同樣的做法也可以套用到相鄰的兩個數位(digit)。 而函式`ceil2tens`與題目第 9 行`(((sz + mask) / alignment) * alignment);`這段程式碼，概念上其實是相近的操作。 所以如果 alignment = 4 就用 4 進位制的方式去看待數字，其他進位制也一樣。 #### power of two? [How to check if a number is a power of 2](https://stackoverflow.com/a/600306) alignment 與 mask 的關係無非是相差 1，但如果以 2 進位的角度思考，當 alignment 為 2 的冪時，列出以下表格 | alignment | | mask | | | -------- | -------- | -------- | -------- | | $10_{(2)}$ | $2_{(10)}$ | $01_{(2)}$ | $1_{(10)}$ | | $100_{(2)}$ | $4_{(10)}$ | $011_{(2)}$ | $3_{(10)}$ | | $1000_{(2)}$ | $8_{(10)}$ | $0111_{(2)}$ | $7_{(10)}$ | | $10000_{(2)}$ | $16_{(10)}$ | $01111_{(2)}$ | $15_{(10)}$ | 2的冪情況下，alignment 只有唯一一個位元會是 1 其他都是 0。 將 alignment 那個唯一的位元 1 的位元位置記為 $n$，可發現在 mask 最低有效位(LSB)到 $n - 1$ 位的位元全都是 1，正如表格所示。 若今天需要判斷某個數 a 是否為 2 的冪，可透過 ```cpp (a & (a - 1)) == 0) ``` 來進行判斷，或是 ```cpp (a & -a) == a ``` ### `sz + mask & ~mask` 的操作 ```cpp= align_up(120, 4) = 120 align_up(121, 4) = 124 align_up(122, 4) = 124 align_up(123, 4) = 124 align_up(124, 4) = 124 ``` 以題目的範例說明，現在給出一個記憶體位置，需要以 4 進行對齊。 #### `sz + mask` 以 mask 進行 __"上取整"__ ```cpp= 120 + 3 = 123 121 + 3 = 124 122 + 3 = 125 123 + 3 = 126 124 + 3 = 127 ``` #### `~mask` ```cpp= ~mask = (-mask - 1) = -3 - 1 = -4 ``` $-4$ 在這裡的二進制為 $1111...1111000_{(2)}$ 共有 61 個 1 加上後 3 個 0 利用這點對 **==捨去==** 進行改寫。 ```cpp / alignment * alignment ``` 變成 ```cpp & ~mask ``` > 參考 [Mask (computing)](https://en.wikipedia.org/wiki/Mask_(computing)) #### `sz + mask & ~mask` 由於現在 ~mask 其他位元為1，後3位為0，利用 bitwise AND 進行**捨去**。 ```cpp= 123 & -4 = 120 124 & -4 = 124 125 & -4 = 124 126 & -4 = 124 127 & -4 = 124 ``` ## β - 2 ## γ - 1 ### code tracing 先列出容易觀察到的 function 間的調用關係，由上至下。 CMP 巨集會展開成 med 裡的 function point: __*cmp__ ```cpp #define CMP(t, x, y) (cmp((x), (y))) char *med3(char *a, char *b, char *c, cmp_t *cmp, void *thunk) ``` ```graphviz digraph { node[shape=box] qsort_mt->pthread_create pthread_create[color=green] pthread_create->qsort_thread qsort_thread->qsort_algo qsort_algo->med qsort_algo->allocate_thread CMP[label="CMP(macro)"] med->CMP qsort_algo->swap qsort_algo->vecswap swapfunc->swapcode swap->swapfunc vecswap->swapfunc } ``` 追蹤 `qsort-mt`，對 thread pool 配置記憶體， mutex cond 初始化，建立執行序。 而 label f3 f2 f1 做資源的釋放。 執行序建立後，多個執行序會先在 `qsort_thread` 裡的 `pthread_cond_wait` 等待第一次的 signal。 ## γ - 2 以 [Thread Sanitizer](https://github.com/google/sanitizers/wiki/ThreadSanitizerCppManual) 進行編譯並執行。 ```shell gcc -g -Wall -fsanitize=thread -o qsort qsort-mt.c -lpthread ./qsort ``` 也可以將執行結果導向到文件 ```shell ./qsort 2> report.txt ``` 得到錯誤訊息 ``` ================== WARNING: ThreadSanitizer: data race (pid=121156) Write of size 4 at 0x7b4000000080 by thread T1 (mutexes: write M0): #0 allocate_thread /home/nocmos/codespace/linux2023smhw1/qsortmt/qsort-mt.c:211 (qsort+0x3bc1) #1 qsort_algo /home/nocmos/codespace/linux2023smhw1/qsortmt/qsort-mt.c:314 (qsort+0x3bc1) #2 qsort_thread /home/nocmos/codespace/linux2023smhw1/qsortmt/qsort-mt.c:352 (qsort+0x4008) Previous read of size 4 at 0x7b4000000080 by thread T2 (mutexes: write M2): #0 qsort_thread /home/nocmos/codespace/linux2023smhw1/qsortmt/qsort-mt.c:343 (qsort+0x3fca) Location is heap block of size 256 at 0x7b4000000000 allocated by main thread: #0 calloc ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:672 (libtsan.so.0+0x31edc) #1 qsort_mt /home/nocmos/codespace/linux2023smhw1/qsortmt/qsort-mt.c:132 (qsort+0x4408) #2 main /home/nocmos/codespace/linux2023smhw1/qsortmt/qsort-mt.c:505 (qsort+0x2ab7) Mutex M0 (0x7ffed69559a8) created at: #0 pthread_mutex_init ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:1227 (libtsan.so.0+0x4bee1) #1 qsort_mt /home/nocmos/codespace/linux2023smhw1/qsortmt/qsort-mt.c:130 (qsort+0x43e9) #2 main /home/nocmos/codespace/linux2023smhw1/qsortmt/qsort-mt.c:505 (qsort+0x2ab7) Mutex M2 (0x7b40000000a8) created at: #0 pthread_mutex_init ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:1227 (libtsan.so.0+0x4bee1) #1 qsort_mt /home/nocmos/codespace/linux2023smhw1/qsortmt/qsort-mt.c:136 (qsort+0x44d2) #2 main /home/nocmos/codespace/linux2023smhw1/qsortmt/qsort-mt.c:505 (qsort+0x2ab7) Thread T1 (tid=121158, running) created by main thread at: #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:969 (libtsan.so.0+0x605b8) #1 qsort_mt /home/nocmos/codespace/linux2023smhw1/qsortmt/qsort-mt.c:144 (qsort+0x4490) #2 main /home/nocmos/codespace/linux2023smhw1/qsortmt/qsort-mt.c:505 (qsort+0x2ab7) Thread T2 (tid=121159, running) created by main thread at: #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:969 (libtsan.so.0+0x605b8) #1 qsort_mt /home/nocmos/codespace/linux2023smhw1/qsortmt/qsort-mt.c:144 (qsort+0x4490) #2 main /home/nocmos/codespace/linux2023smhw1/qsortmt/qsort-mt.c:505 (qsort+0x2ab7) SUMMARY: ThreadSanitizer: data race /home/nocmos/codespace/linux2023smhw1/qsortmt/qsort-mt.c:211 in allocate_thread ================== ThreadSanitizer: reported 1 warnings ``` 可發現資源競爭出現在 function `allocate_thread()` 中的 `c->pool[i].st = ts_work;` 由 [NOVBobLee](https://hackmd.io/@sysprog/SkmKiSfh2#NOVBobLee) 提及，應該從 thread pool 獲取 thread 並改變狀態前，先行獲得 mutex。 ### 圖解 ## γ - 3