linux2023: doodoodog

# [Linux Kernel Class] Homework 1 ## :pencil:α − 1 :::success 解釋上述程式碼運作原理 ::: S-Tree 繼承了 AVL Tree 的特性，透過 Insert & Rotation 來平衡樹高，此目的可以保證在 Search Node 的時間複雜度維持在 O(log n)，但因為 AVL Tree 存在著過度 Balance 的問題導致在做 Insert or Delete Node 的時候會帶來較大的開銷，此時設計者加入 red-black tree 的特性，也就是不會過度執行 Balance 進而可以平衡掉 AVL Tree 執行 Balance 帶來的開銷。 1. 這邊設計者利用 hint 來追蹤數高，hint 只有在 st_update Node 情況下才會更新 2. 在 Delete Node 會先選擇右子樹最小的 Node 來 replace 如果不存在右節點，則會從左子樹最大的 Node 來 replace 3. 在 `st_update()` 時候會檢查 balance 如果左右子樹的樹高差距大於 1 則會進行 `st_rotate_right()` or `st_rotate_left()` ## :pencil:α − 2 :::success 指出上述程式碼可改進之處，特別跟 AVL tree 和 red-black tree 相比，並予以實作 ::: 如果在 Insert Node 發生 rotation 時，rotation 的 node 在 update 完恰好 hint 與 previous hint 相同，便不會繼續往 parent node 更新。這會讓 Tree 變成左傾樹或是右傾樹。 ``` Insert Node : 50 -> 1 -> 2 -> 3 ``` ![](https://hackmd.io/_uploads/H1jc-HSh3.png) 因為 S-Tree 只會在 `n->hint == 0` or `n->hint != prev_hint` 條件下才會往 Parent Node 進行更新，所以在這情況下可能會變成 Link List 狀態。Search 的時間複雜度為 `O(n)`。 ```程式類型=161 if (n->hint == 0 || n->hint != prev_hint) st_update(root, p); ``` ## :pencil:α − 3 :::success 設計效能評比程式，探討上述程式碼和 red-black tree 效能落差 ::: ## :pencil:β - 1 :::success 說明上述程式碼的運作原理 ::: ```程式類型=1 #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 (sz + mask) & ~mask; } return (((sz + mask) / alignment) * alignment); } ``` <style> .red { color: red; } </style> 分為兩個 Case: **alignment is power of two -** `sz + mask` 如果 `sz` 不會被 `mask` 整除，則 `sz + mask` 會進位。此時 `& ~mask` 可以<span class="red">保留</span> `aligment` 的<span class="red">最高位元以後的所有位元</span>，而達到 align_up。 ``` uintptr_t sz = 12345 size_t alignment = 4 uintptr_t mask = alignment - 1 = 3; (sz + mask) & ~mask; => 0011 0000 0011 1001 + 0011 = 0011 0000 0011 1100 => 0011 0000 0011 1100 & 1111 1111 1111 1100 => 0011 0000 0011 1100 Note: uintptr_t sizeof = 64 (in 64-bit OS), 32 (in 32-bit OS) ``` **alignment isn't power of two -** 如果 `alignment` 不為 2 的冪次方，可以透過 `((sz + mask) / alignment) * alignment)` 來達到 `align_up` 的效果。 ## :pencil:β - 2 :::success 在 Linux 核心原始程式碼找出類似 align_up 的程式碼，並舉例說明其用法 ::: 檢查資料結構大小是否與指定的`Size`對齊。 **kvm/include/test_util.h** ```程式類型=998 static inline void *align_ptr_up(void *x, size_t size) { return (void *)align_up((unsigned long)x, size); } ``` ```程式類型=146 /* Aligns x up to the next multiple of size. Size must be a power of 2. */ static inline uint64_t align_up(uint64_t x, uint64_t size) { uint64_t mask = size - 1; TEST_ASSERT(size != 0 && !(size & (size - 1)), "size not a power of 2: %lu", size); return ((x + mask) & ~mask); } ``` **kvm/lib/kvm_util.c** ```程式類型=998 TEST_ASSERT(!is_backing_src_hugetlb(src_type) || region->mmap_start == align_ptr_up(region->mmap_start, backing_src_pagesz), "mmap_start %p is not aligned to HugeTLB page size 0x%lx", region->mmap_start, backing_src_pagesz); ``` ## :pencil:γ - 1 :::success 解釋上述程式碼運作原理 ::: 參考原本的 Quick Sort 演算法，會利用 Divide and Conquer 的性質來進行排序，。 ```程式類型=1 void quickSort(int number[], int left, int right) { if(left < right) { int s = number[(left+right)/2]; int i = left - 1; int j = right + 1; while(1) { while(number[++i] < s) ; // 向右找 while(number[--j] > s) ; // 向左找 if(i >= j) break; SWAP(number[i], number[j]); } quickSort(number, left, i-1); // 對左邊進行遞迴 quickSort(number, j+1, right); // 對右邊進行遞迴 } } ``` 這邊利用 POSIX Thread 的概念將 Divide 出來的 Task 由 Sub-Thread 來進行。 ```程式類型=200 /* Allocate an idle thread from the pool, lock its mutex, change its state to * work, decrease the number of idle threads, and return a pointer to its data * area. * Return NULL, if no thread is available. */ static struct qsort *allocate_thread(struct common *c) { verify(pthread_mutex_lock(&c->mtx_al)); for (int i = 0; i < c->nthreads; i++) if (c->pool[i].st == ts_idle) { c->idlethreads--; verify(pthread_mutex_lock(&c->pool[i].mtx_st)); c->pool[i].st = ts_work; verify(pthread_mutex_unlock(&c->mtx_al)); return (&c->pool[i]); } verify(pthread_mutex_unlock(&c->mtx_al)); return (NULL); } ``` 該如何管理每個 Thread 的狀態? 首先必須將 Alloc 好的 Thread 利用 `pthread_cond_wait()` 讓其進入休眠狀態。 ```程式類型=341 /* Wait for work to be allocated. */ verify(pthread_mutex_lock(&qs->mtx_st)); while (qs->st == ts_idle) verify(pthread_cond_wait(&qs->cond_st, &qs->mtx_st)); verify(pthread_mutex_unlock(&qs->mtx_st)); ``` 當 Quick Sort Divide 出 Sub-Task 後則可以透過 `pthread_cond_signal()` 喚醒該 Thread 來工作。 ```程式類型=312 /* Now try to launch subthreads. */ if (nl > c->forkelem && nr > c->forkelem && (qs2 = allocate_thread(c)) != NULL) { qs2->a = a; qs2->n = nl; verify(pthread_cond_signal(&qs2->cond_st)); verify(pthread_mutex_unlock(&qs2->mtx_st)); } ``` ## :pencil:γ - 2 :::success 以 Thread Sanitizer 找出上述程式碼的 data race 並著手修正 ::: 使用 [ThreadSanitizer (aka TSan)](https://github.com/google/sanitizers/wiki/ThreadSanitizerCppManual) 來檢查 Race Condition。 ``` $ gcc -Wall -fsanitize=thread -o qsort-mt qsort-mt.c -lpthread $ ./qsort-mt ``` 編譯完後執行可以發現 ``` ThreadSanitizer ``` 檢查到有 Race Condition 產生。 ``` WARNING: ThreadSanitizer: data race (pid=25012) Write of size 4 at 0x7b4000000080 by thread T1 (mutexes: write M0): #0 allocate_thread /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:211 (qsort-mt+0x347a) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) #1 qsort_algo /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:314 (qsort-mt+0x4199) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) #2 qsort_thread /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:351 (qsort-mt+0x45b7) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) Previous read of size 4 at 0x7b4000000080 by thread T2 (mutexes: write M1): #0 qsort_thread /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:343 (qsort-mt+0x44cd) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) Location is heap block of size 256 at 0x7b4000000000 allocated by main thread: #0 calloc ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:701 (libtsan.so.2+0x3c467) (BuildId: 29a32c589768a10ed232cacef24e09c48a66ec41) #1 qsort_mt /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:132 (qsort-mt+0x28fa) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) #2 main /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:503 (qsort-mt+0x5021) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) Mutex M0 (0x7ffda5c5d9a8) created at: #0 pthread_mutex_init ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:1329 (libtsan.so.2+0x3d7b6) (BuildId: 29a32c589768a10ed232cacef24e09c48a66ec41) #1 qsort_mt /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:130 (qsort-mt+0x28dd) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) #2 main /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:503 (qsort-mt+0x5021) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) Mutex M1 (0x7b40000000a8) created at: #0 pthread_mutex_init ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:1329 (libtsan.so.2+0x3d7b6) (BuildId: 29a32c589768a10ed232cacef24e09c48a66ec41) #1 qsort_mt /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:136 (qsort-mt+0x2980) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) #2 main /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:503 (qsort-mt+0x5021) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) Thread T1 (tid=25014, running) created by main thread at: #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:1036 (libtsan.so.2+0x3d189) (BuildId: 29a32c589768a10ed232cacef24e09c48a66ec41) #1 qsort_mt /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:144 (qsort-mt+0x2a8f) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) #2 main /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:503 (qsort-mt+0x5021) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) Thread T2 (tid=25015, running) created by main thread at: #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:1036 (libtsan.so.2+0x3d189) (BuildId: 29a32c589768a10ed232cacef24e09c48a66ec41) #1 qsort_mt /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:144 (qsort-mt+0x2a8f) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) #2 main /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:503 (qsort-mt+0x5021) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) SUMMARY: ThreadSanitizer: data race /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:211 in allocate_thread ================== ThreadSanitizer: reported 1 warnings ``` 這邊我們從這段訊息找到 Race Condition 發生的位置 `0x7b4000000000`，同時也可以知道這塊為動態記憶體配置 `heap block of size 256` ``` Location is heap block of size 256 at 0x7b4000000000 allocated by main thread: #0 calloc ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:701 (libtsan.so.2+0x3c467) (BuildId: 29a32c589768a10ed232cacef24e09c48a66ec41) #1 qsort_mt /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:132 (qsort-mt+0x28fa) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) #2 main /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:503 (qsort-mt+0x5021) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) ``` ```程式類型=132 if ((c.pool = calloc(maxthreads, sizeof(struct qsort))) == NULL) ``` `c.pool` 資料結構分別存在 `pthread_mutex_t mtx_st` 與 `pthread_cond_t cond_st`，來做 Data Protect。 ```程式類型=88 struct qsort { enum thread_state st; /* For coordinating work. */ struct common *common; /* Common shared elements. */ void *a; /* Array base. */ size_t n; /* Number of elements. */ pthread_t id; /* Thread id. */ pthread_mutex_t mtx_st; /* For signalling state change. */ pthread_cond_t cond_st; /* For signalling state change. */ }; ``` 下面分別顯示出兩個 Thread 發生 Race Condition 的時間點。 **Thread 1 -** ``` revious read of size 4 at 0x7b4000000080 by thread T2 (mutexes: write M1): #0 qsort_thread /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:343 (qsort-mt+0x44cd) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) ``` 由此程式碼所示，在讀取某個 `struct qsort` 需要透過 `pthread_mutex_lock(&qs->mtx_st)` 來保證在同一時間點只有一個 Thread 在 Critical Section。 ```程式類型=341 /* Wait for work to be allocated. */ verify(pthread_mutex_lock(&qs->mtx_st)); while (qs->st == ts_idle) verify(pthread_cond_wait(&qs->cond_st, &qs->mtx_st)); verify(pthread_mutex_unlock(&qs->mtx_st)); if (qs->st == ts_term) { return NULL; } ``` **Thread 2 -** ``` Write of size 4 at 0x7b4000000080 by thread T1 (mutexes: write M0): #0 allocate_thread /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:211 (qsort-mt+0x347a) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) #1 qsort_algo /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:314 (qsort-mt+0x4199) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) #2 qsort_thread /home/benjamin/linux_kernel_class/pthread-qsort/qsort-mt.c:351 (qsort-mt+0x45b7) (BuildId: fbed16402f4b10060b3b2eee881e6358c7fff99e) ``` 這邊可以看到 Tread 2 修改了 `struct qsort` 裡的某個變數 `c->pool[i].st = ts_work;` 但是沒有做 mutex_lock，因此在這邊發生了 Read & Write Race Condition。 ```程式類型=207 verify(pthread_mutex_lock(&c->mtx_al)); for (int i = 0; i < c->nthreads; i++) if (c->pool[i].st == ts_idle) { c->idlethreads--; c->pool[i].st = ts_work; verify(pthread_mutex_lock(&c->pool[i].mtx_st)); verify(pthread_mutex_unlock(&c->mtx_al)); return (&c->pool[i]); } verify(pthread_mutex_unlock(&c->mtx_al)); return (NULL); ``` **Solution -** 這邊需要將 `c->pool[i].st = ts_work;` 放至 `mutex_lock` 保護之後，以確保只有一個 Thread 進入到 Critical Section。 ```程式類型=207 verify(pthread_mutex_lock(&c->mtx_al)); for (int i = 0; i < c->nthreads; i++) if (c->pool[i].st == ts_idle) { c->idlethreads--; verify(pthread_mutex_lock(&c->pool[i].mtx_st)); c->pool[i].st = ts_work; verify(pthread_mutex_unlock(&c->mtx_al)); return (&c->pool[i]); } verify(pthread_mutex_unlock(&c->mtx_al)); return (NULL); ``` ## :pencil:γ - 3 :::success 研讀專題: lib/sort.c，提出上述程式碼效能改進之規劃並予以實作 ::: 參考 Heapsort 使用 Multi-Threads 方式 [heapsort-mt.c](https://github.com/doodoodog/linux-kernel-practice/blob/main/heapsort-pthread/heapsort-mt.c) 下圖表示一般的 Heapsort 在 Elements = 1000000 的效能表現。 ![](https://hackmd.io/_uploads/S1Cpm-C23.png) 下圖表示 Multi-Threads 在 Heapsort 在 Elements = 1000000 的效能表現。 ![](https://hackmd.io/_uploads/BkvAXW033.png) 需要再改進優化。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.