Try   HackMD

linux2023: zoo868e

測驗
α−1

  • st_rotate_left: 旋轉左子樹變平衡
  • st_rotate_right: 旋轉右子樹變平衡
  • st_balance: 左子樹高度-右子樹高度
  • st_max_hint: 樹的高度
  • st_update: st_balance < -1，代表右子樹太重，所以要st_rotate_right，反之，要st_rotate_left。在st_update的最後會檢查hint是否改變，若是改變，親代的hint就可能改變，因此要向上更新。另外，由於rotate的操作只有在update中會發生，所以也只有在st_update中需要更新hint
  • st_insert: 需要提供root, parent, node和dir。root是整棵樹的根，parent代表node的親代，dir則代表node是在parent的左邊還是右邊。實作方法直觀，將node附值給parent的dir，將parent設為node的親代，st_update樹的parent這個節點，因為可能需要rotate，這會更新整棵樹。
  • st_replace_[left/right]: 用l/r節點覆寫n節點
  • st_remove: 刪除節點del。如果有右子樹會先用右子樹的最小值複寫del，若沒有右子樹則會用左子樹的最大值覆寫del。若沒有子樹則直接刪除即可。當我們把least/most節點移動到del時，我們需要更新他原本的親代的hint，同時，如果因為移動導致不平衡，需要旋轉成平衡子樹。
void st_remove(struct st_node **root, struct st_node *del)
{
    if (st_right(del)) {
        struct st_node *least = st_first(st_right(del));
        if (del == *root)
            *root = least;

        st_replace_right(del, st_first(least));
        st_update(root, st_parent(del));
        return;
    }

    if (st_left(del)) {
        struct st_node *most = st_last(st_left(del));
        if (del == *root)
            *root = most;

        st_replace_left(del, st_last(most));
        st_update(root, st_parent(del));
        return;
    }

    if (del == *root) {
        *root = 0;
        return;
    }

    /* empty node */
    struct st_node *parent = st_parent(del);

    if (st_left(parent) == del)
        st_left(parent) = 0;
    else
        st_right(parent) = 0;

    st_update(root, parent);
}
  • container_of: 透過offsetof取得類別成員在記憶體中，在pack中的相對位置，再用該成員的記憶體位置減去該相對位置，從而得到該類的記憶體位置

測驗
α−2

在st_remove中會先檢查是否有右子樹，若沒有右子樹則會檢查左子樹。由於這是一個平衡樹，且左右子樹高度差不大於1，所以在沒有右子樹的時候，即便有左子樹也只會有一個節點。所以我們不需要再去找左子樹中的最大值，可以省略st_last。並且，由於st_replace_left之後，del不會再有子代，所以直接更新del即可。

if (st_left(del)) {
    if (del == *root)
        *root = st_left(del);

    st_replace_left(del, st_left(del));
    st_update(root, st_parent(del));
    return;
}

測驗
α−3

根據doc/Documentation/rbtree.txt比較rbtree與S-Tree的效能。使用Uftrace比較兩者在Insert以及Remove時，所使用的旋轉次數以及耗費時間。

  1. Insert
    • 無序
    • 有序
  2. Search
    • 無序
    • 有序
  3. Remove
    • 無序
    • 有序

測驗
β−1

觀察alignment = 4 = 0100的情況

118 = 01110110 --align_up--> 1111000
119 = 01110111 --align_up--> 1111000
120 = 01111000 --align_up--> 1111000
121 = 01111001 --align_up--> 1111100
122 = 01111010 --align_up--> 1111100

可以發現align_up做的事情就是在第一、二個位元有1的時候，將其清空，並且加上alignment。再觀察alignment = 8 = 1000的情況

62 = 00111110 --align_up--> 01000000
63 = 00111111 --align_up--> 01000000
64 = 01000000 --align_up--> 01000000
65 = 01000001 --align_up--> 01001000
66 = 01000010 --align_up--> 01001000

跟alignment = 4時的狀況相似，只是多了第三的位元。所以我們根據觀察寫出第一個版本的align_up。












static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
    uintptr_t mask = alignment - 1;
    if ((alignment & mask) == 0) {
        uintptr_t ret = sz;
        if (sz & mask)
            return (sz & ~mask) + mask + 1;
        return sz;
    }
    return (((sz + mask) / alignment) * alignment);
}

但是我們希望不要使用if來完成align_up。再觀察一次align_up的步驟

sz = 119 = 01110111
alignment = 4 = 00000100
mask = 00000011, ~mask = 11111100
sz & mask = 00000011
sz & ~mask = 01110100
(sz & ~mask) + mask + 1 = 1110100 + 0100

再觀察align_up之後會是一樣的數，可以發現在需要進行上述步驟的數值都是即便-1之後再做一樣的步驟還是會有一樣的結果。同時，已經對其的數值(116)在-1之後，如果做同樣的步驟，也會得到相同的結果

alignment = 4 = 00000100
113 = 01110001 --align_up--> 01111100
114 = 01110010 --align_up--> 01111100
115 = 01110011 --align_up--> 01111100
116 = 01111100 --align_up--> 01111100

所以先將sz-1，就不需要判斷是否需要對齊









static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
    uintptr_t mask = alignment - 1;
    if ((alignment & mask) == 0) {
        return ((sz - 1) & ~mask) + mask + 1;
    }
    return (((sz + mask) / alignment) * alignment);
}

由於經過(sz - 1) & ~mask之後，+ mask等價於| mask，所以我們可以改寫成這樣

static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
    uintptr_t mask = alignment - 1;
    if ((alignment & mask) == 0) {
        return ((sz - 1) & ~mask | mask) + 1;
    }
    return (((sz + mask) / alignment) * alignment);
}

最後，可以發現先& ~mask再| mask等價於| mask，因此答案應該是這樣

static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
    uintptr_t mask = alignment - 1;
    if ((alignment & mask) == 0) {
        return ((sz - 1) | mask) + 1;
    }
    return (((sz + mask) / alignment) * alignment);
}

測驗
β−2

測驗
γ−1

觀察後發現HHHH是發生在狀態改變為ts_idle的時候，只有在做完qsort-algo之後才會改變為ts_idle的狀態。所以再來要做的事情應該是等待ts_term。查找當狀態改變為ts_term時的行為，可以看到在f3以及JJJJ之前都會改變狀態為ts_term，由於JJJJ是我們要寫的作業，因此推測這裡的行為跟f3是一樣的，都需要發送訊號給qs->cond_st。

測驗
γ−2

透過ThreadSanitizer檢查data race的問題

  1. 先用clang編譯qsort-mt.c
clang -fsanitize=thread -O2 qsort-mt.c -o qsort -g
  1. 執行qsort得到ThreadSanitizer的報告，發現有一個data race的問題






































==================
WARNING: ThreadSanitizer: data race (pid=49080)
  Write of size 4 at 0x7b4000000080 by thread T1 (mutexes: write M0):
    #0 allocate_thread /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:201:21 (qsort+0xd184a) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
    #1 qsort_algo /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:301:14 (qsort+0xd184a)
    #2 qsort_thread /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:338:3 (qsort+0xcc91a) (BuildId: 4651c84b87659265877e79949d900d74d464d177)

  Previous read of size 4 at 0x7b4000000080 by thread T2 (mutexes: write M1):
    #0 qsort_thread /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:329:14 (qsort+0xcc8c7) (BuildId: 4651c84b87659265877e79949d900d74d464d177)

  Location is heap block of size 256 at 0x7b4000000000 allocated by main thread:
    #0 calloc <null> (qsort+0x4be67) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
    #1 qsort_mt /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:124:17 (qsort+0xcc1f6) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
    #2 main /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c (qsort+0xcd0f2) (BuildId: 4651c84b87659265877e79949d900d74d464d177)

  Mutex M0 (0x7ffc84940bb0) created at:
    #0 pthread_mutex_init <null> (qsort+0x4ec1f) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
    #1 qsort_mt /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:122:7 (qsort+0xcc1bd) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
    #2 main /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c (qsort+0xcd0f2) (BuildId: 4651c84b87659265877e79949d900d74d464d177)

  Mutex M1 (0x7b40000000a8) created at:
    #0 pthread_mutex_init <null> (qsort+0x4ec1f) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
    #1 qsort_mt /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:128:9 (qsort+0xcc254) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
    #2 main /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c (qsort+0xcd0f2) (BuildId: 4651c84b87659265877e79949d900d74d464d177)

  Thread T1 (tid=49088, running) created by main thread at:
    #0 pthread_create <null> (qsort+0x4d41d) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
    #1 qsort_mt /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:136:9 (qsort+0xcc2c0) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
    #2 main /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c (qsort+0xcd0f2) (BuildId: 4651c84b87659265877e79949d900d74d464d177)

  Thread T2 (tid=49089, running) created by main thread at:
    #0 pthread_create <null> (qsort+0x4d41d) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
    #1 qsort_mt /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:136:9 (qsort+0xcc2c0) (BuildId: 4651c84b87659265877e79949d900d74d464d177)
    #2 main /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c (qsort+0xcd0f2) (BuildId: 4651c84b87659265877e79949d900d74d464d177)

SUMMARY: ThreadSanitizer: data race /home/matt_jan/LinuxSummer2023/W1/gamma/qsort-mt.c:201:21 in allocate_thread
==================
ThreadSanitizer: reported 1 warnings

測驗
γ−3

Last changed by 
 
Matt Jan
0
183

Read more

Google L4 embedded 面試分享

感謝朋友 R 的幫忙，在 mock interview 時常常會崩潰，但他都會情緒穩定的開導我。也感謝家人跟女朋友的鼓勵及支持。

Mar 23, 2025
Netlink

第1章討論了 Linux 核心網絡子系統的角色及其運作的三個層次。Netlink socket 介面首次出現在 2.2 版的 Linux 核心中，作為 AF_NETLINK socket。它被創建為比笨拙的 IOCTL 通訊方法更靈活的替代方案。IOCTL 處理程序無法從核心向用戶空間發送非同步消息，而 netlink sockets 則可以。使用 IOCTL 還有另一層複雜性：需要定義 IOCTL 編號。Netlink 的操作模型相當簡單：使用者在 userspace 使用 socket API 打開並註冊一個 netlink socket，這個 netlink socket 處理與核心 netlink socket 的雙向通信，通常用於發送消息來配置各種系統設置並從核心獲取回應。本章描述了 netlink 協議的實現和 API，並討論了其優缺點。本書還介紹了新的通用 netlink 協議，討論了其實現和優點，並給出了一些使用 libnl 庫的示例。最後，討論了 socket 監控介面。

Jun 8, 2024
ICMP

本章將重點介紹位於 ISO 模型第7層的 ICMP 協定，並詳細解析該協定的數據包在系統內核中的處理過程。在用戶空間層面，使用者能夠通過 socket API 來傳送 ICMP 數據包，其中，ping 命令是一個廣為人知且常用的例子。

Jun 5, 2024
Learning the Linux Kernel with tracing

source:

May 27, 2024
Read more from Matt Jan
Published on HackMD