Try   HackMD

2022q1 第 3 週測驗題

tags: linux2022

目的: 檢驗學員對 記憶體管理、對齊及硬體特性, 指標, bitwise, 前置處理器 的認知

作答表單: 測驗 1-8 (Linux 核心設計)
作答表單: 測驗 9-11 (Linux 核心實作)

測驗 1

在 Linux 核心原始程式碼，include/linux/bitfield.h 提及一個巨集 GENMASK，其作用是依據給定的範圍，產生連續的 bitmask，例如:

  • GENMASK(6, 4) 產生 011100002
  • GENMASK(39, 21) 產生 0x000000ffffe00000 (64 位元)

已知我們使用的微處理器架構為 64 位元，且 unsigned long 為 8 位元組寬度 (符合 LP64 資料模型)，以下是可能的 GENMASK 巨集的定義:

#define GENMASK(h, l) \
    (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))

請補完，使其行為符合預期。作答規範:

  1. LEFT 和 RIGHT 應以最簡潔的形式撰寫，且符合作業一排版規範 (近似 Linux 核心程式碼排版風格)
  2. LEFT 和 RIGHT 皆為表示式，可能包含常數
  3. LEFT 和 RIGHT 皆不該包含小括號 (即 ( 和 ))

作答區

  • LEFT = ?
  • RIGHT = ?

延伸問題:

  1. 解釋上述程式碼運作原理
  2. 比較 Linux 核心 GENMASK 巨集的實作，闡述其額外的考量
  3. 舉出 Linux 核心原始程式碼中二處 GENMASK 巨集和 include/linux/bitfield.h 的應用案例

測驗 2

考慮以下程式碼:

struct foo;
  
struct fd {
    struct foo *foo;
    unsigned int flags;
};

enum {
    FOO_DEFAULT = 0,
    FOO_ACTION,                           
    FOO_UNLOCK,
} FOO_FLAGS;

static inline struct fd to_fd(unsigned long v)
{
    return (struct fd){EXP1, v & 3};
}

函式 fo_fd 接受指定的地址 v，填入一個 fd 結構體，並確保第一個成員的地址得以依據〈你所不知道的 C 語言：記憶體管理、對齊及硬體特性〉描述，對 4 個位元組進行向下對齊 (即 C++ Boost 描述的 align_down)。其中 struct foo; 運用〈你所不知道的 C 語言：指標篇〉提及的 forward declaration 技巧，可在實作階段才提供具體 struct foo 的定義。

請補完，使其行為符合預期。作答規範:

  1. EXP1 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
  2. EXP1 不得使用 % (modulo) 運算子
  3. 當變數和常數進行運算時，變數應該出現前於常數，例如 v | 1

作答區

  • EXP1 = ?

延伸問題:

  1. 解釋上述程式碼運作原理
  2. 在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說

測驗 3

考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 LeetCode 190. Reverse Bits 的描述。

#include <stdint.h>
uint8_t rev8(uint8_t x)
{
    x = (x >> 4) | (x << 4);               
    x = ((x & 0xCC) >> 2) | (EXP2);
    x = ((x & 0xAA) >> 1) | (EXP3);
    return x;
}

請補完，使其行為符合預期。作答規範:

  1. EXP2 和 EXP3 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
  2. 當變數和常數進行運算時，變數應該出現前於常數，例如 v | 1

作答區

  • EXP2 = ?
  • EXP3 = ?

延伸問題:

  1. 解釋上述程式碼運作原理
  2. 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

測驗 4

延伸〈你所不知道的 C 語言：前置處理器應用篇〉，我們嘗試將 foreach 巨集 予以擴充，使得支援以下寫法:

    int i;
    foreach_int(i, 0, -1, 100, 0, -99) {
        printf("i is %i\n", i);
    }
    const char *p;
    foreach_ptr(p, "Hello", "world") {
        printf("p is %s\n", p);
    }

預期輸出如下:

i is 0
i is -1
i is 100
i is 0
i is -99
p is Hello
p is world

對應的巨集定義:

#include <assert.h>
#define _foreach_no_nullval(i, p, arr) \
    assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))

#define foreach_int(i, ...)                                            \
    for (unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0); \
         _foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int);      \
         (i) = ((int[]){__VA_ARGS__, 0})[EXP4])

#define foreach_ptr(i, ...)                                                 \
    for (unsigned _foreach_i =                                              \
             (((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \
         (i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__,            \
                                                    NULL})[EXP5],   \
                  _foreach_no_nullval(_foreach_i, i,                        \
                                      ((const void *[]){__VA_ARGS__})))

請補完，使其行為符合預期。作答規範:

  1. EXP4 和 EXP5 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
  2. 不該出現小括號 (即 ( 和 ))

作答區

  • EXP4 = ?
  • EXP5 = ?

延伸問題:

  1. 解釋上述程式碼運作原理
  2. 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

測驗 5

針對 LeetCode 29. Divide Two Integers，以下是可能的實作:

#include <limits.h>
int divide(int dividend, int divisor)
{
    int signal = 1;
    unsigned int dvd = dividend;
    if (dividend < 0) {
        signal *= -1;
        dvd = ~dvd + 1;
    }

    unsigned int dvs = divisor;
    if (divisor < 0) {
        signal *= -1;
        dvs = ~dvs + 1;
    }

    int shift = 0;
    while (dvd > (EXP6))
        shift++;

    unsigned int res = 0;
    while (dvd >= dvs) {
        while (dvd < (dvs << shift))
            shift--;                         
        res |= (unsigned int) 1 << shift;
        EXP7;
    }

    if (signal == 1 && res >= INT_MAX)
        return INT_MAX;
    return res * signal;
}

請補完，使其行為符合預期。作答規範:

  1. EXP6 和 EXP7 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
  2. 不該出現小括號 (即 ( 和 ))

作答區

  • EXP6 = ?
  • EXP7 = ?

延伸問題:

  1. 解釋上述程式碼運作原理，指出可改進之處，並予以實作
  2. 在 Linux 核心原始程式碼中找出針對整數/浮點數/定點數除法特別撰寫的程式碼，並予以討論

測驗 6

針對 LeetCode 149. Max Points on a Line，以下是可能的實作:

#include <stdbool.h>
#include "list.h"

struct Point {
    int x, y;
};

struct point_node {
    int p1, p2;
    struct list_head link;
};

static bool can_insert(struct list_head *head, int p1, int p2)
{
    struct point_node *pn;
    list_for_each_entry (pn, head, link)
        return EXP8;
    return true;
}

static int gcd(int x, int y)
{
    while (y) {
        int tmp = y;
        y = x % y;
        x = tmp;
    }
    return x;
}

static int maxPoints(struct Point *points, int pointsSize)
{
    if (pointsSize <= 2)
        return pointsSize;

    int i, j, slope_size = pointsSize * pointsSize / 2 + 133;
    int *dup_cnts = malloc(pointsSize * sizeof(int));
    int *hori_cnts = malloc(pointsSize * sizeof(int));
    int *vert_cnts = malloc(pointsSize * sizeof(int));
    int *slope_cnts = malloc(slope_size * sizeof(int));
    memset(hori_cnts, 0, pointsSize * sizeof(int));
    memset(vert_cnts, 0, pointsSize * sizeof(int));
    memset(slope_cnts, 0, slope_size * sizeof(int));

    for (i = 0; i < pointsSize; i++)
        dup_cnts[i] = 1;

    struct list_head *heads = malloc(slope_size * sizeof(*heads));
    for (i = 0; i < slope_size; i++)
        INIT_LIST_HEAD(&heads[i]);

    for (i = 0; i < pointsSize; i++) {
        for (j = i + 1; j < pointsSize; j++) {
            if (points[i].x == points[j].x)
                hori_cnts[i]++, hori_cnts[j]++;

            if (points[i].y == points[j].y)
                vert_cnts[i]++, vert_cnts[j]++;

            if (points[i].x == points[j].x && points[i].y == points[j].y)
                dup_cnts[i]++, dup_cnts[j]++;

            if (points[i].x != points[j].x && points[i].y != points[j].y) {
                int dx = points[j].x - points[i].x;
                int dy = points[j].y - points[i].y;
                int tmp = gcd(dx, dy);
                dx /= tmp;
                dy /= tmp;
                int hash = dx * dy - 1333 * (dx + dy);
                if (hash < 0)
                    hash = -hash;
                hash %= slope_size;
                if (can_insert(&heads[hash], i, j)) {
                    struct point_node *pn = malloc(sizeof(*pn));
                    pn->p1 = i;
                    pn->p2 = j;
                    EXP9;
                }
            }
        }
    }

    for (i = 0; i < slope_size; i++) {
        int index = -1;
        struct point_node *pn;
        list_for_each_entry (pn, &heads[i], link) {
            index = pn->p1;
            slope_cnts[i]++;
        }
        if (index >= 0)
            slope_cnts[i] += dup_cnts[index];
    }

    int max_num = 0;
    for (i = 0; i < pointsSize; i++) {
        if (hori_cnts[i] + 1 > max_num)
            max_num = hori_cnts[i] + 1;
        if (vert_cnts[i] + 1 > max_num)
            max_num = vert_cnts[i] + 1;
    }
    for (i = 0; i < slope_size; i++) {
        if (slope_cnts[i] > max_num)
            max_num = slope_cnts[i];
    }

    return max_num;
}

請補完，使其行為符合預期。作答規範:

  1. EXP8 和 EXP9 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
  2. EXP8 不該出現小括號 (即 ( 和 ))
  3. EXP9 為包含 list_ 開頭巨集的單一敘述

作答區

  • EXP8 = ?
  • EXP9 = ?

延伸問題:

  1. 解釋上述程式碼運作原理，指出可改進之處，並予以實作
  2. 擴充 LeetCode 題目，考慮更多座標點的輸入 (例如超過 10 萬個) 時，設計有效的資料結構以降低記憶體開銷，並確保快速的執行

測驗 7

考慮 ilog32 函式可針對給定的 32 位元無號數，計算扣除開頭的 0，最少需要多少位元才可儲存 (the minimum number of bits required to store an unsigned 32-bit value without any leading zero bits)，以下是一個可能的實作:

int ilog32(uint32_t v)
{
    int ret = v > 0;
    int m = (v > 0xFFFFU) << 4;
    v >>= m;
    ret |= m;
    m = (v > 0xFFU) << 3;
    v >>= m;
    ret |= m;
    m = (v > 0xFU) << 2;
    v >>= m;
    ret |= m;
    m = EXP10;
    v >>= m;
    ret |= m;
    EXP11;
    return ret;
}

請補完，使其行為符合預期。作答規範:

  1. EXP10 和 EXP11 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
  2. EXP11 不該出現小括號 (即 ( 和 ))
  3. EXP10 和 EXP11 皆包含 > 運算子

作答區

  • EXP10 = ?
  • EXP11 = ?

延伸問題:

  1. 解釋上述程式碼運作原理
  2. 在 Linux 核心原始程式碼找出類似實作並解說其應用場景
  3. 研讀論文《Using de Bruijn Sequences to Index a 1 in a Computer Word》，探討缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 ilog
  4. 運用〈你所不知道的 C 語言：前置處理器應用篇〉和〈你所不知道的 C 語言：數值系統篇〉提及的技巧，實作編譯時期 (compile-time) 的 ilog2 實作

測驗 8

考慮以下 C++ 二元搜尋樹的程式:

typedef struct tnode *tree;                   
struct tnode {
    int data;   
    tnode *left;
    tnode *right;
    tnode(int d)
    {       
        data = d;
        left = right = 0;
    }           
};

void remove_data(tree &t, int d)
{
    tnode *p = t;
    tnode *q;
    while (p != 0 && p->data != d) {
        if (d < p->data) {
            q = p;
            p = p->left;
        } else {
            q = p;
            p = p->right;
        }
    }
    if (p != 0) {
        if (p->left == 0)
            if (p == t)
                t = p->right;
            else if (p == q->left)
                q->left = p->right;
            else
                q->right = p->right;
        else if (p->right == 0)
            if (p == t)
                t = p->left;
            else if (p == q->left)
                q->left = p->left;
            else
                q->right = p->left;
        else {
            tnode *r = p->right;
            while (r->left) {
                q = r;
                r = r->left;
            }
            p->data = r->data;
            if (r == p->right)
                p->right = r->right;
            else
                q->left = r->right;
            p = r;
        }
        delete p;
    }
}

函式 remove_data 嘗試將指定的資料，自給定的二元搜尋樹移除，但原本的 remove_data 過於冗長，於是我們可善用 indirect pointer 改寫為以下:

void remove_data(tree &t, int d)
{
    tnode **p = &t;
    while (*p != 0 && (*p)->data != d) {
        if (d < (*p)->data)
            EXP12;
        else
            EXP13;
    }
    tnode *q = *p;
    if (!q)
        return;

    if (!q->left)
        *p = q->right;
    else if (!q->right)
        *p = q->left;
    else {
        tnode **r = &q->right;
        while ((*r)->left)
            r = EXP14;
        q->data = (*r)->data;
        q = *r;
        *r = q->right;
    }
    delete q;
}

請補完，使其行為符合預期。作答規範:

  1. EXP12, EXP13 和 EXP14 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息，並善用 indirect pointer 的技巧來撰寫
  2. EXP12, EXP13 和 EXP14 皆不該出現 ;

作答區

  • EXP12 = ?
  • EXP13 = ?
  • EXP14 = ?

延伸問題:

  1. 解釋上述程式碼運作原理
  2. 以 C99 改寫上述程式碼，並寫出更精簡高效的實作，和最初的實作相比，探討效率的提升
  3. 研讀 Static B-Trees，探討針對記憶體佈局 (memory layout) 的改進策略

測驗 9

考慮以下進行記憶體地址對齊 (alignment) 的巨集:

/* maximum alignment needed for any type on this platform, rounded up to a
   power of two */
#define MAX_ALIGNMENT 16

/* Given a size, round up to the next multiple of sizeof(void *) */
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
    (((x) + MAX_ALIGNMENT - MMM) & ~(NNN))

作用是向上對齊 (roundup)，請補完程式碼，使其行為符合預期。作答規範:

  • MMM 是常數
  • NNN 是表示式
  • MMM 和 NNN 皆不得出現小括號 (即 ( 和 ))
  • 符合作業一的排版和程式碼風格規範
  • 以符合 C99 的最精簡形式撰寫

作答區

  • MMM = ?
  • NNN = ?

延伸問題:

  1. 解釋上述程式碼運作原理，並撰寫出對應 ROUND_DOWN 巨集
  2. 在 Linux 核心找出類似的巨集和程式碼，說明 round-up/down 的應用場合

測驗 10

考慮以下巨集可得到二個表示式進行整數除法操作時，最接近的整數值:

#define DIVIDE_ROUND_CLOSEST(x, divisor)                       \
    ({                                                         \
        typeof(x) __x = x;                                     \
        typeof(divisor) __d = divisor;                         \
        (((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \
         (((__x) > 0) == ((__d) > 0)))                         \
            ? ((RRR) / (__d))                  \
            : ((SSS) / (__d));                 \
    })

注意: 當除數 (即 divisor) 為負值時，行為沒有定義。
參考執行結果:

  • DIVIDE_ROUND_CLOSEST(7, 3) = 2
  • DIVIDE_ROUND_CLOSEST(6, 3) = 2
  • DIVIDE_ROUND_CLOSEST(5, 3) = 2

作答規範:

  • 符合作業一的排版和程式碼風格規範
  • RRR 和 SSS 為表示式，且都包含 (__x) 和 (__d) (注意小括號)
  • RRR 和 SSS 限用 +, -, >>, << 這幾個運算子，可搭配小括號，並以符合 C99 的最精簡形式撰寫
  • 變數在 RRR 和 SSS 出現的順序 (從左到右)，必定是 __x 先於 __d

請補完程式碼，使其行為符合預期。

作答區

  • RRR = ?
  • SSS = ?

延伸問題:

  1. 解釋上述程式碼運作原理
  2. 在 Linux 核心找出類似的巨集和程式碼，說明 div round-up/closest 的應用場合

測驗 11

考慮以下計算整數開平方根的實作:

static inline unsigned long fls(unsigned long word)
{
    int num = 64 - 1;
        
    if (!(word & (~0ul << 32))) {
        num -= 32;
        word <<= 32;
    }
    if (!(word & (~0ul << (64 - 16)))) {
        num -= 16;
        word <<= 16;
    }
    if (!(word & (~0ul << (64 - 8)))) {
        num -= 8;
        word <<= 8;
    }
    if (!(word & (~0ul << (64 - 4)))) {
        num -= 4;
        word <<= 4;
    }   
    if (!(word & (~0ul << (64 - 2)))) {
        num -= 2;
        word <<= 2;
    }   
    if (!(word & (~0ul << (64 - 1))))
        num -= 1;
    return num;
} 

unsigned long i_sqrt(unsigned long x)
{
    unsigned long b, m, y = 0;

    if (x <= 1)
        return x;

    m = 1UL << (fls(x) & ~1UL);
    while (m) {
        b = y + m;
        XXX;

        if (x >= b) {
            YYY;
            y += m;
        }
        ZZZ;
    }

    return y;
}

i_sqrt 函式的作用等同於 floor(sqrt(x))

作答規範:

  • 符合作業一的排版和程式碼風格規範
  • XXX, YYY 和 ZZZ 都是敘述，不得呼叫任何函式，且不包含 ; 字元
  • 只能使用 =, +=, -=, >>=, <<= 等運算子，且不得出現小括號 (即 ( 和 ))
  • 以符合 C99 的最精簡形式撰寫

作答區

  • XXX = ?
  • YYY = ?
  • ZZZ = ?

延伸問題:

  1. 解釋上述程式碼運作原理，嘗試利用硬體的 clz/ctz 指令改寫
  2. 在 Linux 核心找出類似的巨集和程式碼，說明其應用場景
Last changed by 
 
sysprog
System Software Programming
2
3668

Read more

並行程式設計: Atomics 操作

本文回顧微處理器的 atomic 指令及軟硬體設計考量、memory ordering 及 memory barrier、C11 標準的 &lt;stdatomic.h&gt; 及 Linux 核心介面，和探討經典 lock-free 資料結構和演算法案例。

Apr 26, 2025
你所不知道的 C 語言: linked list 和非連續記憶體

無論是作業系統核心、C 語言函式庫內部、程式開發框架，到應用程式，都不難見到 linked list 的身影，包含多種針對效能和安全議題所做的 linked list 變形，又還要考慮到應用程式的泛用性 (generic programming)，是很好的進階題材。

Apr 25, 2025
Linux 核心設計: 不只挑選任務的排程器

排程器 (scheduler) 是任何一個多工作業系統核心都具備的機制，但彼此落差極大，考量點不僅是演算法，還有當應用規模提升時 (所謂的 scalability) 和涉及即時處理之際，會招致不可預知的狀況 (non-determinism)，不僅即時系統在意，任何建構在 Linux 核心之上的大型服務都會深受衝擊。為此，Linux 核心的排程器經歷多次變革，已非僅是挑選下一個可執行的行程 (process)，而是顧及公平 (fairness)、交互反應 (interactiveness)、多核處理器的負載平衡、進階電源管理、即時處理能力等議題。

Apr 25, 2025
歐拉數 e: 描述連續變化的基石

你一定聽過圓周率 ，但你知道在數學和科學領域中，還有個同等重要的常數 —— 歐拉數 (e) 嗎？之所以如此重要，是因為 e 是用來描述連續變化的常數。試想銀行利息不斷複利累積、熱咖啡逐漸變涼、乃至於病毒在人群中擴散等等現象背後的數學模型，都有 e 的身影。 本文回顧 e 的起源，一探數學家如何定義它、發現它的奇妙性質 (例如 e^x 的導數仍是自身)，及它何以稱為「自然對數」的底。讀者也將理解 e 在微積分、金融、機率統計、物理領域所奠定的根基，並探討其在嵌入式系統、人工智慧等資訊系統中的應用。讀者最終會體會到，e 如何優雅地幫助我們理解這個世界的運作。

Apr 24, 2025
Read more from sysprog
Published on HackMD