# 2026-03-03 問答簡記

:::info
:information_source: 注意須知
1. 在下方填入你的 GitHub 帳號 (務必確保有效)、題目，和你的答覆及相關討論
2. 流程: 問 → 答 → 複問 → 總結回答 → 課後檢討補充並發送信件，完成此循環才算完成測驗
> 課後檢討的內容需要更新在本頁面，應提及答覆提問所需要的 C 語言規格描述、Linux 核心原始程式碼、推論、數學分析、可完整執行的程式碼 (放於 GitHub/gist，在此列出超連結和關鍵部分)、實驗、測試，和對應的討論
> 信件標題: `Linux2026/Week2: 法定姓名`，寄送到 `[e-mail]`，信件內文註明你的 GitHub 帳號並簡述自身在課程的付出狀況，以及對於期末專題的期許和規劃
> 信件內容不要有任何客套話，也不該提「您」或者無助於溝通、假裝 有禮貌的詞彙 $\to$ 真正的「禮貌」是把事情做好，且互利共惠
> 可將問答過程加入[第一份作業](https://hackmd.io/@sysprog/linux2026-warmup)中
3. 務必以第一手材料 (教材、規格書、Linux 核心原始程式碼及其 git log，以及你自己的實驗) 為主
:::

:::success
速查單
* Linux 核心風格的鏈結串列: [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h)
* Linux 核心的系統負載統計: [loadavg.c](https://github.com/torvalds/linux/blob/master/kernel/sched/loadavg.c)
* Linux 核心原始程式碼的符號檢索: [LXR](https://elixir.bootlin.com)
:::

## What I cannot create, I do not understand

美國理論物理學家費曼 (Richard Feynman) 在辦公室黑板書寫以下話語:
* What I cannot create, I do not understand. (我所不能創造的東西，我就不瞭解)
* Know how to solve every problem that has been solved. (知道如何解出每個已被解過的問題)

## 畢業前就該證明自己能解決工程難題
當舉薦與任用充斥流弊，個人能力難以被客觀辨識，於是以科舉所代表的學歷制度，成為相對可檢驗、可比較的衡量機制。

當高等教育普及，學位不再稀缺，文憑所承載的訊號強度隨之下降，社會開始轉而重視作品、專案經驗與可量化的實績。

當 GenAI 能在極短時間內大量產出程式碼、設計稿與文章，作品本身的稀缺性再次被削弱，單純「產出」已不足以構成差異化優勢。

在校生若僅滿足於取得一紙文憑，或僅止於準時完成課程指定作業，實則仍停留在上個世代評量框架之中。更前瞻的思維應該是：在畢業之前，如何已經能對真實世界的問題給出可驗證的解法？如何讓他人不必透過學歷推測能力，而能直接從你的貢獻與影響看見實力？

如今參與開放原始碼協作正是有效的途徑。開放原始碼社群以實際程式碼與公開審查為核心，所有討論、修正與改進皆可被追溯。這種透明機制，使能力不再依賴頭銜背書，而是透過問題定位、架構設計、效能分析與長期維護等實質貢獻來體現。它同時要求溝通能力、跨文化協作與對品質的自我約束，這些特質往往比單一作品更具辨識度。
> 有效「溝通」變得更關鍵

文憑或許仍是起點，但不應是終點。學習如何學習。

## Meta 台北開缺
> [Meta Careers](https://www.metacareers.com/jobsearch?offices[0]=Taipei%2C%20Taiwan)

Software Engineer, OS
* 2+ years' Software Engineering experience in the following: device driver development, embedded systems, or operating systems
* 2+ years’ experience working on systems software in a large-scale C/C++ code base
* Experience with Software Development processes including: source control, bug tracking, and design documentation.
* Experience in hardware bring up using interfaces like ADC, GPIO, SPI, I2C, etc
* Experience in one or more of the following areas: SoC BSP/Board Support Package, Operating Systems, Android OS, RTOS/Zephyr, Bootloader, Power Management, Linux, Graphics and Display Drivers, MCU (Microcontroller)

## ascodeasice

> 鏈結串列在 Linux 核心中用在哪些地方

> 為什麼 process 要用鏈結串列儲存資訊

> 參考以下 struct，設計一個用來排序鏈結串列的 sort 函式型別

typedef struct list_item {
        int value;
        struct list_item *next;
} list_item_t;

typedef struct {
        list_item_t *head;
} list_t;

typedef int (*list_cmp_func_t)(const list_item_t *, const list_item_t *);

void sort(list_item_t *head, list_cmp_func_t cmp);

> 為什麼使用 `list_t` 作為 `sort` 函式的參數型別會比使用 `list_item_t *` 更好

> comparator 的功能是什麼、回傳值會有哪幾種情況？

comparator 是用來比較兩筆資料大小並回傳結果的函式，回傳值可能會有正整數、0、負整數，分別表示第一筆資料大於、等於、小於第二筆資料的情況。

> 為什麼 `sort` 函式要有 comparator 作為參數？

為了能重複使用 `sort` 函式的程式碼。將 comparator 作為 function pointer 傳入 `sort` 函式後，可以透過

> 如果我們想對鏈結串列做 descending 排序，應該如何設計 comparator 與 function pointer 的型別？

typedef int (*list_cmp_func_t)(void *, const list_item_t *, const list_item_t head *);

int cmp_descending(const list_item_t *a, const list_item_t *b){
    // NOTE: might overflow/underflow
    return b->value - a->value;
}

> 目前實作中的 comparator 會遇到什麼問題？

因為 value 的型別為 32-bit signed int，目前的 comparator 在 a 與 b 的 value 為一正一負時，可能會造成 integer overflow 或 underflow。

補充： <!-- TODO: 修正問題 -->

> 你會怎麼實作 merge sort？

補充：問答中有提到 merge sort 並沒有一定將資料分割成兩半，而 Linux 核心中的 `list_sort` 考量到快取 <!-- TODO: 補充程式碼 -->

> 你的 merge sort 的遞迴式是什麼？（與程式實作）

void sort(list_t *list, list_cmp_func_t cmp)
    // - stable
// - O(n log n)
// 
// comparator

    /*
     * head, if head has 0 or 1 node
     * merge(sort(first half of list),
     * sort(second half of list)), otherwise 
     *  */
    if(!list->head || !list->head->next){
        return head;
    }

    left=sort(list->head, cmp);
    right=sort(split(list->head), cmp);

    return merge(left, right);
}

> 我們該如何驗證這個程式是對的、merge sort 有哪些特性？

> 為什麼 stable 是 sorting 中一個重要的特性？

<!-- TODO: 補充：如何驗證 stable -->

> 如何使用程式驗證程式的時間複雜度是 $O(nlogn)$？

> 操作數量與時間複雜度的數學關係是什麼？

## PinkNekoFist
> Quick sort 的策略是什麼

選一個 Pivot，然後將鏈結串列的所有元素對比 Pivot 的大小分成兩部分，再對兩部分作 Quick sort，然後重複遞迴直到鏈結串列大小為1。
> 該如何選擇 Pivot

選最左邊的元素作為 Pivot，優點為方便實作，缺點是 unstable，worst case 時間複雜度為 $log(n^2)$。

// Properties:
// - unstable
void sort(list_t *list, list_cmp_func_t cmp) {
    if (!list || !list->head) return;
    list_item_t *pivot = list->head;
    list_t *left_list, *right_list;
    
    /* split list to left and right */ 
    /* add tail in struct */
    list_item_t *curr = head->next;
    while (curr) {
        if (cmp(curr, pivot) > 0) {
            left_list->tail->next = curr;
            left_list->tail = curr;
        } else {
            right_list->tail->next = curr;
            right_list->tail = curr;
        }
        curr = curr->next;
    }
    
    left_list->tail->next = NULL;
    right_list->tail->next = NULL;
    
    sort(left_list, cmp);
    sort(right_list, cmp);
    
    left_list->tail->next = pivot;
    pivot->next = right_list->head;
    list->head = left_list->head;
    list->tail - right_list->tail;
}
// 考慮以下鏈結串列：
// 1'    2    9    4    3    3'
// 選 1 作為 pivot，比 pivot 小的鏈結串列長度為 0 (worst case)
// *以上程式碼有許多問題，在下方有修正後的程式碼
// 1. 未對 left_list, right_list 初始化, 存取 left_list->tail left_list->tail->next 時會發生 segmentation fault
// 2. 未對遞迴結束設定條件，

- quick sort 為什麼 unstable，該如何修改成 stable ，為什麼要 stable
- 遞迴的缺點，在 Linux 核心中為什麼不是遞迴，不用遞迴如何實作？
- 如何驗證 stable

## [Eason0729](https://github.com/Eason0729/)

> 找到 linked list 中的元素

你的答覆

// find target in list
// return NULL if target is NULL or list is NULL
// return pointer to NULL if not found
list_item_t** find(list_t* l, list_item_t* target){
    if (target==NULL)
        return NULL;
    
    if(l==NULL)
        return NULL;
    
    list_item_t** indirect_head=&l->head;
    while(*indirect_head!=NULL){
        if((*indirect_head)->value==target->value)
            break;
        indirect_head=&(*indirect_head)->next;
    }
    return indirect_head;
}

> 刪除 linkedlist 中的元素

你的答覆

// delete
// return true if success
bool delete(list_t* l, list_item_t* target, void(* destructor)(/* 有加 const 和沒加的差別 */ const void *))
{
    list_item_t** to_delete = find(l, target);
    if (to_delete==NULL)
        return false;
    if (*to_delete==NULL)
        return false;
    
    list_item_t* next = (*to_delete)->next;
    
    destructor(*to_delete);
    
    *to_delete=next;

    return true;
}

> 實驗：有加 const 和沒加的差別

...

## [illdoCc](https://github.com/illdoCc)

> 下列的 min function 要怎麼加上 underflow 及 overflow 的判斷式，並且以 branchless 的方法實作

你的答覆

const float pi = 3.14;
const *kmt = &float;
*kmt = 3;

`gcc -S`

    int32_t min(int32_t a, int32_t b)
    {
        // TODO: branchless 實作
        if(a < 0 && b > 0){
            return a;
        }
        
        
        int32_t diff = a - b;
        return b + (diff & (diff >> 31));
    }
    // a - b < INT32_MIN

以下是不用到 if else 的操作方式，不過這樣的 code 很沒有品味，可讀性差，並且使用到 && 跟 || 也不能算 branchless。

int32_t min(int32_t a, int32_t b)
{
    // 利用該變數檢查是否有 overflow 的情形(underflow 也算在內)
    int32_t overflow_case = 0;
    // underflow
    overflow_case = a < 0 && b > 0 && (a - b) > 0;
    // overflow
    overflow_case = overflow_case || (a > 0 && b < 0 && (a - b) < 0);

    // 先 left shift 再 right shift，把 1(0x00000001) 變為 -1(0xFFFFFFFF)，0 不變
    overflow_case <<= 31; overflow_case >>= 31;

    int32_t diff = a - b;
    return overflow_case & (a - (diff & (diff >> 31))) | ~overflow_case & (b + (diff & (diff >> 31)));
}

    uint32_t select(uint32_t cond, uint32_t a, uint32_t b)
    {
        uint32_t mask = -cond;  // 0 → 0x00000000, 1 → 0xFFFFFFFF
        return (a & mask) | (b & ~mask);
    }

> 在運行 1000 萬次 context switch 並測量其耗費時間時，期間可能會有其他程式產生的中斷，導致測量出的時間不準確，要用哪種統計概念才有辦法統計出確切時間?

## [sakinu](https://github.com/sakinu/)

> 下列程式有沒有哪裡寫得不好或可以精簡？

    void remove_if(list_t *l, int value)
    {
        list_item_t **p = &l->head;
        while (*p) {
            if ((*p)->value == value) {
                list_item_t *del = *p;
                *p = (*p)->next;
                free(del);
            } else {
                p = &(*p)->next;
            }
        }
    }

其中指標的指標，幫助了第 7 行可以直接指向下一個 node，若該節點該被 delete，則當前指向的指標指向其下一個節點，若該節點不該被 delete，則直接指向下一個節點
難點在於要合併第 7 與 10 行，變成同樣的操作，因為在 delete 節點時，還是要維持整體的連續
思考一下指標的指標能做什麼操作在重新思考並意識到我原先只是記得指標的指標的定義，而沒有真實理解其使用場景。

* 第 7 行：將 p 指向的指標設為 p 指向的指標指向的 item 的 next，在此情境下等同將 p 原本指向的指標指向的 node 移出 list
* 第 10 行：將 p 設為 p 指向的指標指向的 node 的 next 的 address，在此情境下等同將 p 與 p 指向的指標，都向著 list 的 next 方向多走一步

理論上一定要有 Branch 去釋放符合條件的 node，所以可能有品味的改動，是將第 7 與第 10 行合併並移除 else 的部分。

如何證明無法更有品味或至少證明兩行無法合併？

這份程式中，指標的指標 p 逐一走訪 linked list 上的每個節點，此時能維持指標的指標結構的最小單位操作就是將 p 指向 &(*p)->next 或者將 *p 指向 (*p)->next

若要把兩行合併，則其中有一行必定是每次迴圈都要執行的。
但是

> 有品味的程式是什麼？

在思考的過程中想出了以下這份程式，雖然行數變少了，但顯然沒有比較有品味。顯示出有品味與行數也未必相等~~甚至有 bug~~

    void remove_if(list_t *l, int value)
    {
        list_item_t **p = &l->head;
        for(; *p; p = &(*p)->next) {
            while(*p && (*p)->value == value) {
                list_item_t *del = *p;
                *p = (*p)->next;
                free(del);
            }
        }
    }

## I3IRI3IR
>求 linked list 中第 $k$ 大的元素

可以隨機找一個標準值 $x$，然後區分鏈結串鍊中元素的大小重排在標準值的左右，如果大於 $x$ 的一邊元素數量 $g$ $\geq k$ 個，則答案在較大的一邊的第 $k$ 大，否則在較小的一邊的第 $k-g$ 大。

## x807x

#include <stdint.h>
#include <stdio.h>
    struct packet {
        uint32_t len;
        uint8_t data[1];
    };

int main()
{
        printf("%ld\n", sizeof(struct packetg));
}
// flexible array member

C99
sizeof() is an operator
4 + 8 (pointer)

## rota1001
為什麼網路封包不一定是完整的？
怎麼定義一個網路封包是由解析者決定的，譬如說在傳輸層可以以 TCP 或 UDP 的封包格式去將一段資料解析成一個封包。而對於更底層的協定來說，上層的協定是沒有意義的，對它來說只是一段資料而已，所以根本不需要去理會一段連續的資料是否有截斷上層的封包。

## deantee

  // 方式 A: union type punning
  union { float f; uint32_t u; } pun;
  pun.f = 3.14f;
  uint32_t bits_a = pun.u;
  // 方式 B: memcpy
  float f = 3.14f;
  uint32_t bits_b;
  memcpy(&bits_b, &f, sizeof(bits_b));

- Issue 1: method A is unsafe (alignment of union is compiler dependent)
- Issue 2: float might not be **exactly** 4 bytes (by the standards, it's **at least** 4 bytes)

// C99 6.5 §7 的 allowed access
// portability
// MISRA-C

Memory operations like `memset` and `memcpy` are byte-addressed

MISRA-C: a separate set of C standards from ISO C standards

RMW = Read, Modify, Write
- Both read and write operations might induce segmentation fault (reading from NULL or writing from NULL)

Circular linked list with a dummy node
- No special case of empty list
- R/W first and last element in O(1)
- Applications of 'circular' of circular linked list in Linux kernel?