Try   HackMD

2025q1 第 2 週測驗題

目的: 檢驗學員對鏈結串列、雜湊表，及位元操作的認知

作答表單: 測驗 1 和測驗 2
作答表單: 測驗 3

測驗 1

我們使用 Linux 核心風格 List API 的簡化標頭檔 list.h 來開發快速排序程式碼。

首先定義結構體和比較用的函式：

#include <stdint.h>

struct listitem {
    uint16_t i;
    struct list_head list;
};

static inline int cmpint(const void *p1, const void *p2)
{
    const uint16_t *i1 = (const uint16_t *) p1;
    const uint16_t *i2 = (const uint16_t *) p2;

    return *i1 - *i2;
}

預期開發的快速排序函式的原型宣告如下：

static void list_quicksort(struct list_head *head);

接著準備測試用的輔助函式：

#define ARRAY_SIZE(x) (sizeof(x) / sizeof(x[0]))

static uint16_t values[256];

static inline uint8_t getnum(void)
{
    static uint16_t s1 = UINT16_C(2);
    static uint16_t s2 = UINT16_C(1);
    static uint16_t s3 = UINT16_C(1);

    s1 *= UINT16_C(171);
    s1 %= UINT16_C(30269);

    s2 *= UINT16_C(172);
    s2 %= UINT16_C(30307);

    s3 *= UINT16_C(170);
    s3 %= UINT16_C(30323);

    return s1 ^ s2 ^ s3;
}

static uint16_t get_unsigned16(void)
{
    uint16_t x = 0;
    size_t i;

    for (i = 0; i < sizeof(x); i++) {
        x <<= 8;
        x |= getnum();
    }

    return x;
}

static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
    for (uint16_t i = 0; i < len; i++) {
        /* WARNING biased shuffling */
        uint16_t j = get_unsigned16() % (i + 1);
        operations[i] = operations[j];
        operations[j] = i;
    }
}

以下是測試程式：

int main(void)
{
    struct list_head testlist;
    struct listitem *item, *is = NULL;
    size_t i;

    random_shuffle_array(values, (uint16_t) ARRAY_SIZE(values));

    INIT_LIST_HEAD(&testlist);

    assert(list_empty(&testlist));

    for (i = 0; i < ARRAY_SIZE(values); i++) {
        item = (struct listitem *) malloc(sizeof(*item));
        assert(item);
        item->i = values[i];
        list_add_tail(&item->list, &testlist);
    }

    assert(!list_empty(&testlist));

    qsort(values, ARRAY_SIZE(values), sizeof(values[0]), cmpint);
    list_quicksort(&testlist);

    i = 0;
    list_for_each_entry_safe (item, is, &testlist, list) {
        assert(item->i == values[i]);
        list_del(&item->list);
        free(item);
        i++;
    }

    assert(i == ARRAY_SIZE(values));
    assert(list_empty(&testlist));

    return 0;
}

預期執行時期不會遇到 assert 錯誤。

相較於尋常的快速排序程式碼，我們希望排序結果是符合 stable sorting，以下是 list_quicksort 的程式碼 (部分遮蔽)：

{
    struct list_head list_less, list_greater;
    struct listitem *pivot;
    struct listitem *item = NULL, *is = NULL;

    if (list_empty(head) || list_is_singular(head))
        return;

    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

    pivot = AAAA(head, struct listitem, list);
    BBBB(&pivot->list);

    list_for_each_entry_safe (item, is, head, list) {
        if (cmpint(&item->i, &pivot->i) < 0)
            list_move_tail(&item->list, &list_less);
        else
            CCCC(&item->list, &list_greater);
    }

    list_quicksort(&list_less);
    list_quicksort(&list_greater);

    DDDD(&pivot->list, head);
    EEEE(&list_less, head);
    FFFF(&list_greater, head);
}

補完程式碼，使其符合預期。
作答規範:

  • AAAA, BBBB, CCCC, DDDD, EEEE, FFFF` 均為 list.h 定義的巨集或行內展開函式 (inline function) 名稱，可能的選項：
    • list_add
    • list_add_tail
    • list_del
    • list_for_each_entry_reverse
    • list_for_each_entry
    • list_first_entry
    • list_move
    • list_move_tail
    • list_splice
    • list_splice_tail
    • list_cut_position
  • 以最精簡的方式撰寫，不包含空白

延伸問題：

  • 解釋上方程式碼運作原理，改進 random_shuffle_array 也探討 list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting
  • 將程式碼整合進 lab0 提及的 qtest，並探討環狀雙向鏈結串列的排序效能，並善用 perf 一類的效能分析工具，探討包含 Linux 核心 list_sort 在內排序實作的效能表現並充分解釋

測驗 2

以下針對 從 √2 的存在談開平方根的快速運算，嘗試開發整數的開平方根運算。

首先是 clz2 函式，其作用是藉由遞迴呼叫以計算 count leading zero (clz)。每次呼叫 clz2() 函式時，代表將目前關注的位元（bits）「切成一半」，以檢查 leading zero 的數量。以下藉由一個數值（0x0001F000）來說明其步驟：

0x0001F000 = 0000 0000 0000 0001 1111 0000 0000 0000 ~2~
  • Step 1

將此數值等分為兩部分：較高位（upper）與較低位（lower）。

Upper Lower
0000 0000 0000 0001 1111 0000 0000 0000
  • Step 2

此時，依據 upper 的數值判斷下一次遞迴呼叫應該處理哪一部分，以累計 leading zero 的數量。

  • 若 upper 等於 0，則下一次遞迴呼叫應檢查 lower 部分，並用計數器（counter）記錄目前已累計的 leading zero（等於 upper 位元數）。
  • 若 upper 不等於 0，則下一次遞迴呼叫應繼續檢查 upper 部分。
upper = 0000 0000 0000 0001

由於 upper 不為 0，下一次遞迴呼叫將繼續檢查 upper 部分的 leading zero。

  • Step 3

遞迴呼叫 clz2() 函式，直到僅剩 2 位元（bits）需要檢查 leading zero，然後回傳結果。

clz2 函式的實作如下： (部分遮蔽)

static const int mask[] = {0, 8, 12, GGGG};
static const int magic[] = {HHHH, 1, 0, IIII};

unsigned clz2(uint32_t x, int c)
{
    if (!x && !c)
        return 32;

    uint32_t upper = (x >> (16 >> c));
    uint32_t lower = (x & (0xFFFF >> mask[c]));
    if (c == JJJJ)
        return upper ? magic[upper] : KKKK + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);
}

及其對應的操作巨集：

#define clz32(x) clz2(x, 0)

參考執行輸出:

  • 輸入: 0x00000F00，其 clz32 為 20
  • 輸入: 0x00000001，其 clz32 為 31

我們可運用 clz32 建構 clz64:

static inline int clz64(uint64_t x)
{
    /* If the high 32 bits are nonzero, count within them.
     * Otherwise, count in the low 32 bits and add 32.
     */
    return (x >> 32) ? clz32((uint32_t) (x >> 32)) : clz32((uint32_t) x) + 32;
}

最後實作整數開平方根： (部分遮蔽)

uint64_t sqrti(uint64_t x)
{
    uint64_t m, y = 0;
    if (x <= 1)
        return x;

    int total_bits = 64;

    /* clz64(x) returns the count of leading zeros in x.
     * (total_bits - 1 - clz64(x)) gives the index of the highest set bit.
     * Rounding that index down to an even number ensures our starting m is a
     * power of 4.
     */
    int shift = (total_bits - 1 - clz64(x)) & MMMM;
    m = 1ULL << shift;

    while (m) {
        uint64_t b = y + m;
        y >>= NNNN;
        if (x >= b) {
            x -= b;
            y += m;
        }
        m >>= PPPP;
    }
    return y;
}

參考執行結果：

  • 輸入: 63，得到 7
  • 輸入: 220，得到 1024

補完程式碼，使其符合預期。
作答規範:

  • GGGG, HHHH, …, LLLL 均為整數
  • MMMM, NNNN 和 PPPP 為有效的 C 語言表示式，以最精簡的形式書寫

延伸問題：

  1. 解釋上述程式碼，並探討擴充為 ⌈x)⌉ (向上取整數) 實作，該如何調整並保持只用整數加減及位元操作
  2. 參照計算機結構測驗題 C 及其注釋，以 C 語言 (搭配 GNU extension) 撰寫不依賴除法指令的 sqrtf，確保符合 IEEE 754 規格。對照 sqrtf, rsqrt, reciprocal implementations in Arm assembly
  3. 參照從 √2 的存在談開平方根的快速運算提到的「藉由查表的平方根運算」，以 C 語言實作，並比較不同手法的整數開平方根效能
    • 一旦發現效能改進的機會，可準備提交改進 int_sqrt 程式碼到 Linux 核心

測驗 3

檢測學員對於 Linux 核心的 hash table 實作的認知。

LeetCode 編號 1 的題目 Two Sum，貌似簡單，作為 LeetCode 的開篇之題，乃是經典中的經典，正所謂「平生不識 Two Sum，刷盡 LeetCode 也枉然」，就像英語單詞書的第一個單詞總是 Abandon 一樣，很多沒有毅力堅持的人就只能記住這一個單詞，所以通常情況下單詞書就前幾頁有翻動的痕跡，後面都是嶄新如初，道理不需多講，雞湯不必多灌，明白的人自然明白。

以上說法取自 Two Sum 兩數之和
mint condition: "mint" 除了薄荷的意思，還可指鑄幣廠，"mint condition" 裡的 “mint” 就與鑄幣廠有關。有些人收集錢幣會在錢幣剛開始發行時收集，因爲這樣的錢幣看起來很新，他們會用 "mint condition" 來形容這種錢幣的狀況，強調「像剛從鑄幣廠出來」，後來衍伸出「有如新一樣的二手商品」的意涵。

題意是給定一個陣列 nums 和一個目標值 target，求找到 nums 的 2 個元素相加會等於 target 的索引值。題目確保必為單一解，且回傳索引的順序沒差異。例如給定輸入 nums = [2, 7, 11, 15], target = 9，相加變成 9 的元素僅有 2 及 7，因此回傳這二個元素的索引值 [0, 1]

考慮以下 C 語言實作:

#include <stdlib.h>
static int cmp(const void *lhs, const void *rhs) {
    if (*(int *) lhs == *(int *) rhs)
        return 0;
    return *(int *) lhs < *(int *) rhs ? -1 : 1;
}

static int *alloc_wrapper(int a, int b, int *returnSize) {
    *returnSize = 2;
    int *res = (int *) malloc(sizeof(int) * 2);
    res[0] = a, res[1] = b;
    return res;
}

int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    *returnSize = 2;
    int arr[numsSize][2];  /* {value, index} pair */
    for (int i = 0; i < numsSize; ++i) {
        arr[i][0] = nums[i];
        arr[i][1] = i;
    }
    qsort(arr, numsSize, sizeof(arr[0]), cmp);
    for (int i = 0, j = numsSize - 1; i < j; ) {
        if (arr[i][0] + arr[j][0] == target)
            return alloc_wrapper(arr[i][1], arr[j][1], returnSize);
        if (arr[i][0] + arr[j][0] < target)
            ++i;
        else
            --j;
    }
    *returnSize = 0;
    return NULL;
}

若用暴力法，時間複雜度為 O(n2)，顯然不符合期待。我們可改用 hash table (以下簡稱 HT) 記錄缺少的那一個值 (即 target - nums[i]) 和對應的索引。考慮以下案例:

nums = [2, 11, 7, 15]：

對應的步驟:

  1. nums[0] 是 2，HT[2] 不存在，於是建立 HT[9 - 2] = 0
  2. nums[1]是 11， HT[11] 不存在，於是建立 HT[9 - 11] = 1
  3. nums[2] 是 7，HT[7] 存在 (設定於步驟 1)，於是回傳 [2, HT[7]] = [2, 0]

hlist 用於 hash table 的實作，它的資料結構定義在 include/linux/types.h 中:

struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next, **pprev;
};

示意如下:

hlist 的操作與 list 一樣定義於 include/linux/list.h，以 hlist_ 開頭。hlist_head 和 hlist_node 用於 hash table 中 bucket 的實作，具有相同 hash value 的節點會放在同一條 hlist 中。 為了節省空間，hlist_head 只使用一個 first 指標指向 hlist_node，沒有指向串列尾節點的指標。

hash table 主要是由一個 hlist_head 的動態陣列所構成，每個 entry 指向一個由 struct hlist_node 構成的非環狀 doubly linked list ，hash table 長度依照 bits 給定，可知大小為 2 的冪。

而可以發現 struct hlist_head 只有一個 struct hlist_node * 的成員; 而 struct hlist_node 型態卻包含一個 struct hlist_node * 及 struct hlist_node ** ，其中一個原因為 hash table 指向的為非環狀的 linked list ，因此只需指向 list 的一端點，若單純使用 struct hlist_node 當作 head ，無用的 "pprev" 會造成大量的記憶體空間浪費，因此將 head 與 node 分開來實作。

而 struct hlist_node 中的 pprev 為何使用「指標的指標」而非「指標」？ 回答這個問題前可以先參考 Linux 原始碼中 type.h ：

struct list_head {
	struct list_head *next, *prev;
};

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};

可知在 type.h 中有兩種 list 的結構：

struct list_head 在 Linux 中實作為環狀 doubly-linked list，且可以在行程管理 (process scheduling) 的相關實作上看到，如 sched.h 中有約 20 處使用到此結構，因可快速存取到頭以及尾的節點（時間複雜度 O(1)） 故有較好的效能，適用於行程管理這種對時間要求嚴謹的部分做使用。

引用自 linux sched.h









struct sched_entity {
    /* For load-balancing: */
    struct load_weight  load;
    struct rb_node      run_node;
    struct list_head    group_node;
    unsigned int        on_rq;
    ...
}

struct hlist_head 搭配 hlist_node。在 Linux 核心中專門為了 hash table 而使用，hlist_head 的設計也省去了 list 起始端 pprev 的存放空間、在初始狀態就省去了一半的記憶體容量。而且同時 hash table 不會特別需要存取到 list 的尾端，並且走訪 list 相對沒那麼講求效率（因為 hash 的設計理念就是講求 hash collision rate 要低、因此一個 list 若太長比較需要改進的為 hash function 的設計而非改進整個資料結構）。綜合上述所說單向 list 已滿足 hash table 的需求。

pprev 為何是「指標的指標」？若和 list_head 一樣使用單純的指標( hlist_node *)，則考慮到 list 有方向性，delete node 時需要額外檢查其是否為 list 的 head 或是 NULL 等等，有較冗餘的程式碼必須實作，因此使用 hlist_node **pprev 直接存取上一個 node 所在的位址。Linux 為求程式碼簡潔故以 pointer to pointer 的方式用 pprev 直接指向前一個元素的記憶體位址本身。

以下是引入 hash table 的實作，學習 Linux 核心程式碼風格: (省略 hlist_{node,head} 及 container_of 的定義)

首先是結構體:

typedef struct {
    int bits;
    struct hlist_head *ht;
} map_t;

struct hash_key {
    int key;
    void *data;
    struct hlist_node node;
};

初始化操作:

map_t *map_init(int bits)
{
    map_t *map = malloc(sizeof(map_t));
    if (!map)
        return NULL;

    map->bits = bits;
    map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
    if (map->ht) {
        for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
            (map->ht)[i].first = NULL;
    } else {
        free(map);
        map = NULL;
    }
    return map;
}

雜湊函數:

#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits)
{
    /* High bits are more random, so use them. */
    return (val * GOLDEN_RATIO_32) >> (32 - bits);
}

對應的檢索程式碼: (部分遮蔽)

static struct hash_key *find_key(map_t *map, int key)
{
    struct hlist_head *head = &(map->ht)[hash(key, AAAA)];
    for (struct hlist_node *p = head->first; p; p = p->next) {
        struct hash_key *kn = container_of(p, struct hash_key, node);
        if (kn->key == key)
            return kn;
    }
    return NULL;
}

void *map_get(map_t *map, int key)
{
    struct hash_key *kn = find_key(map, key);
    return kn ? kn->data : NULL;
}

新增操作： (部分遮蔽)

void map_add(map_t *map, int key, void *data)
{
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;

    kn = malloc(sizeof(struct hash_key));
    kn->key = key, kn->data = data;

    struct hlist_head *h = &map->ht[hash(key, BBBB)];
    struct hlist_node *n = &kn->node, *first = h->first;

    n->next = first;
    if (first)
        CCCC = &n->next;
    h->first = n;
    DDDD = &h->first;
}

釋放記憶體的操作:

void map_deinit(map_t *map)
{
    if (!map)
        return;

    for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
        struct hlist_head *head = &map->ht[i];
        for (struct hlist_node *p = head->first; p;) {
            struct hash_key *kn = container_of(p, struct hash_key, node);
            struct hlist_node *n = p;
            p = p->next;

            if (!n->pprev) /* unhashed */
                goto bail;

            struct hlist_node *next = n->next, **pprev = EEEE;
            *pprev = next;
            if (next)
                next->pprev = pprev;
            n->next = NULL, n->pprev = NULL;

        bail:
            free(kn->data);
            free(kn);
        }
    }
    free(map);
}

主體程式碼:

int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    map_t *map = map_init(10);
    *returnSize = 0;
    int *ret = malloc(sizeof(int) * 2);
    if (!ret)
        goto bail;

    for (int i = 0; i < numsSize; i++) {
        int *p = map_get(map, target - nums[i]);
        if (p) { /* found */
            ret[0] = i, ret[1] = *p;
            *returnSize = 2;
            break;
        }

        p = malloc(sizeof(int));
        *p = i;
        map_add(map, nums[i], p);
    }

bail:
    map_deinit(map);
    return ret;
}

補完程式碼，使其運作符合預期。作答規範：

  • AAAA, BBBB, CCCC, DDDD, EEEE 皆為有效的 C 語言表示式
  • 以最精簡的形式書寫，不包含空白

延伸問題：

  • 解釋上述程式碼運作原理，應提供測試程式碼

    針對 Linux 核心的 hash table 實作，提供更多圖例並揣摩 Linux 核心開發者

  • 進行《The Art of Computer Programming》(vol 3) 一書section 6.4 的 exercise 8，也就是證明 Theorem S

    注意: Linux 核心內部大量使用 hash table，但並非每處的雜湊函數都滿足減少碰撞及避免 clustering 現象的原則，也就是存在若干改進空間

  • 探討 Linux 核心中使用 hash table 的應用案例，至少二項，應當列出原始程式碼並分析，斟酌搭配 git log 以得知 Linux 核心開發者變更程式碼的考量因素
Last changed by 
 
sysprog
System Software Programming
1
2327
Published on HackMD