> [linux2023 summer](https://github.com/RoyWFHuang/linux2023_summer)
# HW1
> [ref: 2023 年暑期 Linux 核心課程第 1 次測驗/作業檢討](https://hackmd.io/@sysprog/SkmKiSfh2#RinHizakura)
## 測驗 α
### 測驗 α − 1
## 測驗 β
### 測驗 β - 1

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); /* MMMM is here */
    }
    return (((sz + mask) / alignment) * alignment);
}

首先取得 mask, 如果 aligment 是 2 的冪, aligment - 1 則可以取得此 aligment 完整的 mask,
:::success
e.g:
$aligment(0b00001000) - 1 = 0b00000111$,
此時取 not 後變成 0b11111000, 就可以把不是 aligment 的倍數給去除.
:::
另外考慮到, 如果 sz 不是剛好 aligment 的倍數, 則需多增加 1個 aligment 來處理

:::success
假設取完畢 aligment 之後剩下的數字為 n $( 0 <= n <= alignment - 1)$, 此時若將此數加上 alignment - 1後取餘數, 則 $(n + (alignment - 1)) \% alignment = n - 1$ 所以加完之後的數字也會落在 0 ~ alignment 之間, 之後再用 mask 將之去除, 就可以得到相對應的 min alignment size.
:::

若非 2 的冪, 則演算法類似, 同樣考慮多增加一個 aligment 處理(+ mask), 之後計算他是 aligment 的幾倍, 在乘上 aligment 來處理, 就可以得出最小值.
:::success
e.g:
aligment 5, input sz = 8
$(8 + (5 -1)) = 12$
$12 / 5 = 2$
$2 * 5 = 10$
$\therefore$ 8 的 aligment 是 10
:::

### 測驗 β - 2
[__ALIGN_KERNEL(x, a)](https://elixir.bootlin.com/linux/v6.4.8/source/include/uapi/linux/const.h#L31) : Kernel define macro.

[fs/ext4](https://elixir.bootlin.com/linux/v6.4.8/source/fs/ext4/file.c), 最近剛好在看 file system的資料, 其中 ext4 在write blk 的時候, 就有使用到對齊這個特性, 如此就可以一次按照 data bus 的寬度, 直接寫入 disk blk 中, 可以避免一筆資料寫入時跨兩個 block 的狀態.

[slub](https://elixir.bootlin.com/linux/v6.4.8/source/mm/slub.c#L4456): 在 cache 機制中, 透過 [kmem_cache_create](https://elixir.bootlin.com/linux/v6.4.8/source/mm/slab_common.c#L392)可以用 slub 機制建立 memory cache, 這邊也會計算 alignment.

## 測驗 γ
使用 [thread sanitizer](https://github.com/google/sanitizers/wiki/ThreadSanitizerCppManual)

ubuntu@maturing-mammal:/home/roy/src-code/github/roy/linux2023_summer$ ./qsort_mt.out -v
==================
WARNING: ThreadSanitizer: data race (pid=14800)
  Write of size 4 at 0x7b4000000080 by thread T1 (mutexes: write M0):
    #0 allocate_thread /home/roy/src-code/github/roy/linux2023_summer/qsort_mt.c:211 (qsort_mt.out+0x347a) (BuildId: 196c580c3003480e1d098369c8d09e7a6aaa9580)
    #1 qsort_algo /home/roy/src-code/github/roy/linux2023_summer/qsort_mt.c:315 (qsort_mt.out+0x4199) (BuildId: 196c580c3003480e1d098369c8d09e7a6aaa9580)
    #2 qsort_thread /home/roy/src-code/github/roy/linux2023_summer/qsort_mt.c:353 (qsort_mt.out+0x45b7) (BuildId: 196c580c3003480e1d098369c8d09e7a6aaa9580)

  Previous read of size 4 at 0x7b4000000080 by thread T2 (mutexes: write M1):
    #0 qsort_thread /home/roy/src-code/github/roy/linux2023_summer/qsort_mt.c:344 (qsort_mt.out+0x44cd) (BuildId: 196c580c3003480e1d098369c8d09e7a6aaa9580)

  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/roy/src-code/github/roy/linux2023_summer/qsort_mt.c:132 (qsort_mt.out+0x28fa) (BuildId: 196c580c3003480e1d098369c8d09e7a6aaa9580)
    #2 main /home/roy/src-code/github/roy/linux2023_summer/qsort_mt.c:505 (qsort_mt.out+0x5021) (BuildId: 196c580c3003480e1d098369c8d09e7a6aaa9580)

  Mutex M0 (0x7ffd6ef7b4a8) created at:
    #0 pthread_mutex_init ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:1329 (libtsan.so.2+0x3d7b6) (BuildId: 29a32c589768a10ed232cacef24e09c48a66ec41)
    #1 qsort_mt /home/roy/src-code/github/roy/linux2023_summer/qsort_mt.c:130 (qsort_mt.out+0x28dd) (BuildId: 196c580c3003480e1d098369c8d09e7a6aaa9580)
    #2 main /home/roy/src-code/github/roy/linux2023_summer/qsort_mt.c:505 (qsort_mt.out+0x5021) (BuildId: 196c580c3003480e1d098369c8d09e7a6aaa9580)

  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/roy/src-code/github/roy/linux2023_summer/qsort_mt.c:136 (qsort_mt.out+0x2980) (BuildId: 196c580c3003480e1d098369c8d09e7a6aaa9580)
    #2 main /home/roy/src-code/github/roy/linux2023_summer/qsort_mt.c:505 (qsort_mt.out+0x5021) (BuildId: 196c580c3003480e1d098369c8d09e7a6aaa9580)

  Thread T1 (tid=14802, 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/roy/src-code/github/roy/linux2023_summer/qsort_mt.c:144 (qsort_mt.out+0x2a8f) (BuildId: 196c580c3003480e1d098369c8d09e7a6aaa9580)
    #2 main /home/roy/src-code/github/roy/linux2023_summer/qsort_mt.c:505 (qsort_mt.out+0x5021) (BuildId: 196c580c3003480e1d098369c8d09e7a6aaa9580)

  Thread T2 (tid=14803, 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/roy/src-code/github/roy/linux2023_summer/qsort_mt.c:144 (qsort_mt.out+0x2a8f) (BuildId: 196c580c3003480e1d098369c8d09e7a6aaa9580)
    #2 main /home/roy/src-code/github/roy/linux2023_summer/qsort_mt.c:505 (qsort_mt.out+0x5021) (BuildId: 196c580c3003480e1d098369c8d09e7a6aaa9580)

SUMMARY: ThreadSanitizer: data race /home/roy/src-code/github/roy/linux2023_summer/qsort_mt.c:211 in allocate_thread
==================
ThreadSanitizer: reported 1 warnings

可以發現 ==qsort_mt.c:211== 在 write 的時候, 另一個 thread 在 ==sort_mt.c:344== 時候會 read, 兩個 thread 操作的變數是 struct qsort->st, 而這個變數因為兩個 thread 都會進行操作, 所以必須用 lock 將之保護, 開始看哪個 st 是沒有保護的.

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--;
            c->pool[i].st = ts_work; /* here need to protect */
            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);
}

c->pool[i].st = ts_work; 這邊變動的時候 沒有進行 lock 保護, 所以將之移入 lock 保護

--- a/qsort_mt.c
+++ b/qsort_mt.c
@@ -208,9 +208,8 @@ static struct qsort *allocate_thread(struct common *c)
     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));
+            c->pool[i].st = ts_work; /* move to here */
             verify(pthread_mutex_unlock(&c->mtx_al));
             return (&c->pool[i]);
         }