linux2023 summer

HW1

ref: 2023 年暑期 Linux 核心課程第 1 次測驗/作業檢討

測驗 α

測驗 α − 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,

e.g:

$aligment(0b00001000)-1=0b00000111$,
此時取 not 後變成 0b11111000, 就可以把不是 aligment 的倍數給去除.

另外考慮到, 如果 sz 不是剛好 aligment 的倍數, 則需多增加 1個 aligment 來處理

假設取完畢 aligment 之後剩下的數字為 n

$(0<=n<=alignment-1)$, 此時若將此數加上 alignment - 1後取餘數, 則

$(n+(alignment-1))\mathrm{\%}alignment=n-1$ 所以加完之後的數字也會落在 0 ~ alignment 之間, 之後再用 mask 將之去除, 就可以得到相對應的 min alignment size.

若非 2 的冪, 則演算法類似, 同樣考慮多增加一個 aligment 處理(+ mask), 之後計算他是 aligment 的幾倍, 在乘上 aligment 來處理, 就可以得出最小值.

e.g:
aligment 5, input sz = 8

$(8+(5-1))=12$

$12/5=2$

$2\ast 5=10$

$\therefore$ 8 的 aligment 是 10

測驗 β - 2

__ALIGN_KERNEL(x, a) : Kernel define macro.

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

slub: 在 cache 機制中, 透過 kmem_cache_create可以用 slub 機制建立 memory cache, 這邊也會計算 alignment.

測驗 γ

使用 thread sanitizer

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