[Linux Kernel Class] Homework 1

α − 1

解釋上述程式碼運作原理

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 帶來的開銷。

這邊設計者利用 hint 來追蹤數高，hint 只有在 st_update Node 情況下才會更新
在 Delete Node 會先選擇右子樹最小的 Node 來 replace 如果不存在右節點，則會從左子樹最大的 Node 來 replace
在 st_update() 時候會檢查 balance 如果左右子樹的樹高差距大於 1 則會進行 st_rotate_right() or st_rotate_left()

α − 2

指出上述程式碼可改進之處，特別跟 AVL tree 和 red-black tree 相比，並予以實作

如果在 Insert Node 發生 rotation 時，rotation 的 node 在 update 完恰好 hint 與 previous hint 相同，便不會繼續往 parent node 更新。這會讓 Tree 變成左傾樹或是右傾樹。

Insert Node : 50 -> 1 -> 2 -> 3

因為 S-Tree 只會在 n->hint == 0 or n->hint != prev_hint 條件下才會往 Parent Node 進行更新，所以在這情況下可能會變成 Link List 狀態。Search 的時間複雜度為 O(n)。


if (n->hint == 0 || n->hint != prev_hint)
    st_update(root, p);

α − 3

設計效能評比程式，探討上述程式碼和 red-black tree 效能落差

β - 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);
}

分為兩個 Case:
alignment is power of two -
sz + mask 如果 sz 不會被 mask 整除，則 sz + mask 會進位。此時 & ~mask 可以保留 aligment 的最高位元以後的所有位元，而達到 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 的效果。

β - 2

在 Linux 核心原始程式碼找出類似 align_up 的程式碼，並舉例說明其用法

檢查資料結構大小是否與指定的Size對齊。
kvm/include/test_util.h




static inline void *align_ptr_up(void *x, size_t size)
{
    return (void *)align_up((unsigned long)x, size);
}









/* 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



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);

γ - 1

解釋上述程式碼運作原理

參考原本的 Quick Sort 演算法，會利用 Divide and Conquer 的性質來進行排序，。


















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 來進行。



















/* 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() 讓其進入休眠狀態。





/* 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 來工作。








/* 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));
}

γ - 2

以 Thread Sanitizer 找出上述程式碼的 data race 並著手修正

使用 ThreadSanitizer (aka TSan) 來檢查 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)


if ((c.pool = calloc(maxthreads, sizeof(struct qsort))) == NULL)

c.pool 資料結構分別存在 pthread_mutex_t mtx_st 與 pthread_cond_t cond_st，來做 Data Protect。









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。








/* 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。











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。











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);

γ - 3

研讀專題: lib/sort.c，提出上述程式碼效能改進之規劃並予以實作

參考 Heapsort 使用 Multi-Threads 方式 heapsort-mt.c
下圖表示一般的 Heapsort 在 Elements = 1000000 的效能表現。
下圖表示 Multi-Threads 在 Heapsort 在 Elements = 1000000 的效能表現。
需要再改進優化。

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.