第 9/10/11/12 週課程問答簡記

測驗 2 中 QUEUE_STRUCT 的 struct member 後面多 padding 用意為何？

使每個 struct member 都佔一個 cacheline 的大小，若是將每個 member 緊湊的擺在同個 cacheline 大小的空間內，每次一有變更就要發一次 cache invalidate 的 bradcast 給所有不共享 cache 的 CPU，cache invalidate broadcast 是很高的成本 (試想有上百個 CPU)，如此 cache 也形同虛設，因為每次都在 invalidate

測驗 2 中第 202 行為何要 pos & queue->cell_mask 而非 pos % cell_count - 1 ?

因為 producer and consumer problem 的可存取空間會改變，所以 mask size 要當成一個結構體成為儲存，讓它可以變動，並用 bitwise and 來達到 mod 的效果

zoanana990

fibdrv

移植原本在 usersapce 的大數運算到 Linux 核心模組時，遇到記憶體管理的問題。策略

降低對 stdio 的使用和依賴：準備若干 test case，使用形如 EXPECT(bn_init(1), 1); 的程式碼來檢驗個別操作的正確性，不用肉眼比對十進位輸出
使用巨集來包裝記憶體相關操作，例如 MALLOC，甚至加入對應的檢查和錯誤訊息

#if define(__KERNEL__)
#define MALLOC(x) kmalloc(x)
#else
#define MALLOC(x) malloc(x)
#endif

留意 realloc 的使用: realloc 若失敗，如何釋放記憶體
善用 printk 和對應的 level，見 Message logging with printk

cantfindagoodname

fibdrv

krealloc 可能對執行時間帶來嚴重影響，改進策略:

先行計算在給定的數值範圍，需要多大的記憶體空間，預先配置
儘量使用預先配置的記憶體，並在 add 和 mul 檢查是否需要額外配置
建立 square 作為 fast doubling 的加速操作，因為事先已知有效位數，可避免額外的比較

Risheng1128

quiz3

測驗 1: 分析巨集函式 GENMASK 在 linux 核心原始碼的實作及考量

quiz2

測驗 1: 分析輸出的組合語言
測驗 3: 使用 gnu extension 改寫，並分析效能提升

hankluo6

quiz6

實作缺失
- 程式有時後會卡住
- Memory Leak

Futex

arthurchang09

quiz8

blueskyson

面試被問到的問題：走訪檔案系統時，需要大量使用 file descriptor，但是在 Linux 系統中，同時可以 open 的 file descriptor 有限，請問如何利用有限的 file descriptor 來走訪深度很深的目錄。

kdnvt

thread sanitizer 說明頁面似乎有重複的句子。
閱讀 hazard pointer 論文理解複數 writer 的情況。

Kevin-Shih

quiz11 的 mpmc_init 為何要檢查 queue 的記憶體地址是否對齊 16 B ?
https://en.wikipedia.org/wiki/False_sharing

ABA 問題和 mpmc
如何改進 mpmc 的測試

SmallHanley

quiz12

dequeue() 中的 batch_size 是做什麼的？以及什麼時候會回傳 SPSC_Q_EMPTY？
如何設計測試程式，來判斷 SPSC_Q_FULL、SPSC_Q_EMPTY 等狀況？

yaohwang99

ktcp
如何確認 CMWQ 是否正確將任務分配至不同執行緒
CMWQ 如何選擇將任務派發至特定 CPU?

send/recv

static int get_request(struct socket *sock, unsigned char *buf, size_t size)
{
    struct msghdr msg;
    struct kvec vec;
    int length;

    /* kvec setting */
    vec.iov_len = size;
    vec.iov_base = buf;

    /* msghdr setting */
    msg.msg_name = 0;
    msg.msg_namelen = 0;
    msg.msg_control = NULL;
    msg.msg_controllen = 0;
    msg.msg_flags = 0;

    /*
     * TODO: during benchmarking, such printk() is useless and lead to worse
     * result. Add a specific build flag for these printk() would be good.
     */
    printk(MODULE_NAME ": start get response\n");
    /* get msg */
    length = kernel_recvmsg(sock, &msg, &vec, size, size, msg.msg_flags);
    printk(MODULE_NAME ": get request = %s\n", buf);

    return length;
}

static int send_request(struct socket *sock, unsigned char *buf, size_t size)
{
    int length;
    struct kvec vec;
    struct msghdr msg;

    msg.msg_name = NULL;
    msg.msg_namelen = 0;
    msg.msg_control = NULL;
    msg.msg_controllen = 0;
    msg.msg_flags = 0;

    vec.iov_base = buf;
    vec.iov_len = strlen(buf);

    printk(MODULE_NAME ": start send request.\n");

    length = kernel_sendmsg(sock, &msg, &vec, 1, size);

    printk(MODULE_NAME ": send request = %s\n", buf);

    return length;
}

send/recv

static int handle_message_from_client(int client, client_list_t **list)
{
    int len;
    char buf[BUF_SIZE];
    memset(buf, 0, BUF_SIZE);
    if ((len = recv(client, buf, BUF_SIZE, 0)) < 0)
        server_err("Fail to receive", list);
    if (len == 0) {
        if (close(client) < 0)
            server_err("Fail to close", list);
        *list = delete_client(list, client);
        printf("After fd=%d is closed, current numbers clients = %d\n", client,
               size_list(*list));
    } else {
        printf("Client #%d :> %s", client, buf);
        if (send(client, buf, BUF_SIZE, 0) < 0)
            server_err("Fail to send", list);
    }
    return len;
}

ray90514

kecho 要如何處理大於 BUF_SIZE 的封包？

steven1lung

ktcp
處理超過 buf_size 大小資料

uduru0522

Bottom-up Heapsort 比較次數分析