# 藍圖 linux
## 2025 課程準備、企劃、聯絡
重新開始
## Linux 核心就業

[行程總表](https://wiki.csie.ncku.edu.tw/linux/schedule)

[預期目標](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-a)先處理 Fork 舊的資料，對舊的目錄更名為 2022，再依照網頁指示，進行 import repository 導入目錄，完成預備。發現與之前專案有不同的檔案。概念不熟，重試才對。

## 新聞

[AI_ms](https://github.com/sysprog21/lab0-c/pull/236) auto written commmit message by ollama. [A test.](https://www.youtube.com/watch?v=ObksvAZyWdo) In this video, you know how to set up git hooks, in .git/hooks with proper name. There is no extension as hook.

嘗試導入 qwen 到 prehook ，即將檔案放入 .git/hooks 並適當改名，接者依照教材修改 q_size ，因為我另外加一個檔案 git-pull-all.sh 所以結果稍微影響，但成功了。

# ✅Suggested commit messages:
# Add Script to Update Git Branches and Pull Changes
# 
# Automate fetching and pulling of remote branches with new script. Also
# correct minor issue in q_size function to handle empty list gracefully.

### [TODO!!]:
關於這個，Linux Foundation 提供的 LFD103 訓練 (A Beginner’s Guide to Linux Kernel Development) (免費的)，裡面有介紹像是編譯核心或 in-tree modules 等基本的主題。完成之後還會收到認證可以放 LinkedIn (?)
https://training.linuxfoundation.org/....../a-beginne....../
[kernel course](https://trainingportal.linuxfoundation.org/learn/course/a-beginners-guide-to-linux-kernel-development-lfd103/linux-kernel-development-process/linux-kernel-development-process?page=2)

[面試](https://www.youtube.com/watch?v=o9HjvKTET20)凱心琳和 Ian 在 John 解題
[Leetcode Challenge](/48Jiy_x8TziHexUx_uXiHQ)
[linked mess](https://hackmd.io/@sysprog/linux2024-progress?fbclid=IwY2xjawJJZcRleHRuA2FlbQIxMQABHWWqD_aqEivLO6_Kzpp8sSkLlQsZ7rhjg4a-ZeNebMIBVIoxdbKSDuUdQg_ohaem_CPp_Mj4qmWG-sMwBQI4t2w)
[文組翻身](https://medium.com/%E5%B7%A5%E4%BA%BA%E6%99%BA%E6%85%A7/%E6%88%91%E7%9A%84-linux-kerenl-%E5%AD%B8%E7%BF%92%E8%B7%AF%E7%A8%8B-7d507440f473)
[lkml](https://lkml.org/)，找到幾個你主修 subsystem 的重點改動
[chatgpt for interview](https://www.youtube.com/watch?v=t4SMw2XgGiE) YT video and some links of

:::info
[!] Failed to retrieve upstream commit hash from GitHub.
小錯誤，回憶經驗，知道是 GPG 公私鑰設定的問題。
Why is Git always asking for my password?

- deploy keys
- GitHub Apps

根據作業說明後半文字，必須補完程式碼，否則無法通過 git hook 的檢查機制。
:::

:man_dancing:emoji cheat sheet[^emoji_l1]
[^emoji_l1]:[emojilist](https://github.com/ikatyang/emoji-cheat-sheet)
最差就引用22年的專案設計，一定可行。

lab-0 qtest，參考 [hello-algo](https://www.hello-algo.com/zh-hant/) 完成問題

#### [ideas](https://hackmd.io/@sysprog/linux2025-ideas)

[2024 年課程期末展示](https://hackmd.io/@sysprog/linux2024-showcase) 及[完整期末專題列表](https://hackmd.io/@sysprog/linux2024-projects)，搭配 [2024 年課程回顧影片](https://youtu.be/JSUkg8KXx-Q)從去年的期末專題中選出至少 7 項題目，紀錄過程中的認知、遇到的疑惑，以及你認為如何改進。盡可能選我有興趣容易而且有時間且能適當發展。每一項，除了認知、疑惑、改進之外，興趣和難易度和發展時間以及可能性都會被討論。

上半場 可以直接切時間：
場次：4；人次：15 : 鄭樺軒 陳伯儒, <張則佳 P177 = Hot Mercury> 成大資工所114級, <陳榮佑>, <>, <>, <>, <Roy Huang>, <鄭以新 I-Hsin Cheng = var-x> ~44:04

34:03-44:04 var; Sched 25 mins
1:31:27-1:39:04-1:39:19-1:48:16
disk , jason50123
1:39:04 老師訊息留言

1:10:22 葉惟欣 排程書籍

### 作業區
- [lab0作業需求](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-a)
- [lab0 回憶和突破](/_sS3BitpSMuUPvLRAwhlGg)
- [2025q1 Homework1 (lab0) Urbaner](/bqVA0peKTta0jLI0hAbKHg)

* [x] 10+email [作業區~~連結建立~~](https://hackmd.io/@sysprog/linux2025-homework1)

| 使用者名稱 | lab0-c | GitHub | ideas |
| ------ | ------ | ------ | ------ |
| Urbaner3 | [Urbaner](https://hackmd.io/@Urbaner/lab0hw) | [GitHub](https://github.com/Urbaner3/lab0-c) | [ideas](https://hackmd.io/@Urbaner/ideas25)

期末專題: [proj](https://hackmd.io/@sysprog/linux2025-showcase)

#### reverseK
[graph](https://pythontutor.com/visualize.html#mode=edit)

#include <stdio.h>
#include <stdlib.h>

// Define a simple struct to hold an integer value
struct node {
    int data;
    struct node *prev;
    struct node *next;
};

// Function to add a new node to the end of the list
void add_node(struct node **head, int data) {
    struct node *new_node = (struct node *) malloc(sizeof(struct node));
    new_node->data = data;
    new_node->next = NULL;

    if (*head == NULL) {
        *head = new_node;
        new_node->prev = NULL;
    } else {
        struct node *temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = new_node;
        new_node->prev = temp;
    }
}

// Function to print the list
void print_list(struct node *head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

// Function to reverse nodes in groups of k
void q_reverseK(struct node **head, int k) {
    if (!head || !(*head) || k <= 1) {
        return;
    }

    struct node *curr = *head;
    struct node *prev_tail = NULL;
    struct node *new_head = NULL;

    while (curr != NULL) {
        struct node *group_head = curr;
        struct node *prev = NULL;
        int count = 0;

        // Reverse k nodes
        while (curr != NULL && count < k) {
            struct node *next = curr->next;
            curr->next = prev;
            curr->prev = next; // Adjust the prev pointer
            prev = curr;
            curr = next;
            count++;
        }

        // Connect the previous group's tail to the current group's head
        if (prev_tail != NULL) {
            prev_tail->next = prev;
        }

        // Update the new head of the list
        if (new_head == NULL) {
            new_head = prev;
        }

        // Update the tail of the current group
        prev_tail = group_head;
    }

    // Update the head pointer
    if (new_head != NULL) {
        *head = new_head;
    }
}

// Main function
int main() {
    // Create a list and add some nodes
    struct node *head = NULL;
    for (int i = 1; i <= 10; i++) {
        add_node(&head, i);
    }

    // Print original list
    printf("Original list: ");
    print_list(head);

    // Reverse the list in groups of k
    int k = 3;
    q_reverseK(&head, k);

    // Print reversed list
    printf("Reversed list in groups of %d: ", k);
    print_list(head);

    return 0;
}

### 期待攻下伺服器
[希望的var-x](https://hackmd.io/@vax-r/linux2024-homework1#%E6%95%B4%E5%90%88%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8) 得失心不要太重，學習惟欣，穩定常態，而不是追求超然。[作業要求](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-c) 可能改變，也許本來就不穩定，在測試，也只有少數人能體會，不必太過在意。能學會 select 很好，繼續思考伺服器還有什麼可學的。

### AI
[aider](https://www.facebook.com/microjserv/videos/1652231735639264/?idorvanity=1531876370923589)
[ai_commit_help](https://www.facebook.com/groups/system.software2025/permalink/936276488709153/)

### 課前問卷
[2025 linux kernel quiz pre-course](/qXjfKr_eTNq7BPgBsBN9eQ)

### 參考教材
算法心得：高效算法的奥秘[2](https://awesome-programming-books.github.io/algorithms/%E7%AE%97%E6%B3%95%E5%BF%83%E5%BE%97%EF%BC%9A%E9%AB%98%E6%95%88%E7%AE%97%E6%B3%95%E7%9A%84%E5%A5%A5%E7%A7%98%EF%BC%88%E7%AC%AC2%E7%89%88%EF%BC%89.pdf); 計算機程序設計藝術[^ref_bit][whole](https://archive.org/details/codenoart/%5B%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E8%89%BA%E6%9C%AF%5D.%E7%AC%AC3%E5%8D%B7.%E6%8E%92%E5%BA%8F%E4%B8%8E%E6%9F%A5%E6%89%BE/page/n141/mode/2up); <>

[^ref_bit]:S. (2013). Hacker's Delight (2nd ed.). Addison–Wesley Professional. p. 512. ISBN 978-0321842688.; Knuth, Donald E. (2009). The Art of Computer Programming Volume 4, Fascicle 1: }

@提醒 lab0:
[git 介紹](https://hackmd.io/@sysprog/git-with-github)
>git pull deal with other branches
[Git playground](/w7lh_qR6QC-6m7Ybx4p6Xw)

[makefile](https://hackmd.io/@sysprog/SySTMXPvl)
[hackmd_src](https://hackmd.io/features-tw?both) to copy
[chat_word](https://quickref.me/chatgpt)
[git branch](https://gist.github.com/grimzy/a1d3aae40412634df29cf86bb74a6f72) : How to pull all branches in github? Create a git-pull-all.sh can be executed.

### 作業依靠 22,23,24年 有 valgrind 的優先
:::spoiler Hw1
#### hw1
[以新](https://hackmd.io/@vax-r/linux2024-homework1) 是一個有根據、有系統、敢做敢想，有創意的人。所以受人矚目。
惟欣是一個直覺準，自省能力高，說話穩注意觀感的人，但對測試過的理論，就會很快。無法注意別人。
衍傑是一個精神差，無法長時間說話的人
那我科翰是怎樣的人？分心、貪心，敢想敢做隨性的人，常常像個賭徒。會幻想，但也會過度練習、過度解釋。善用敏感直覺。會大量閱讀和模仿。 不能接受別人、但會去演示或是模仿，為達目的不擇手段。 容易走偏，產生邪教。不夠專注，相信成型，奔放，不夠勇敢。堅持。

稍微記錄程式碼數量，想象是在做菜，雖然是多個程式，但步驟是重複的，目標要想辦法讓他明確。先確認 commit 的更新，還有說明文字鐘的目標數量，重複關係，做事順序，或是並行處理。有測資、實作 queue 程式碼、資料結構演算法、自動測試、valgrind 動態分析、指標處理回收清除、Makefile 流程、 sort 排序實作、研究內核 list sort 程式碼、已知條件。得知優化的能力。目錄檔案點算。記憶體位置，電腦運算，編碼，記憶除錯、記憶體設計、完成檢驗。第一次、第二次、第三次測驗。 精準的記憶體分析和除錯、Git pre-commit hook、Git pre-push hook 3=fork, push, passwd。選單界面、linenoise 補完、自動評分程式 2 python, make 再畫圖。ASAN: Address Sanitizer、 seg fault

頁一 API說明、作業目標、過往歷史搜尋。Helloalg 演算法展示。NULL 空和 empty 指標空。 queue.c 實作。17 函數，找出重複寫出計劃。 delete" 和 "remove" 看似都是「刪去」不同：斷開和清空。頭值接節點的結構。編譯環境 ，靜態分析， rebase，開發工具內外。 make: check, test 流程可以推。 scripy:python, hook 兩項 python 編譯配 IDE、[slide_download](https://slidesaver.app/)、/usr/include/linux/ 、前項有 sched.h 應用 list_head、基礎實作：-linked-list#開放原始碼專案中的實作、list.h 在 kernel 裡的哪裡：include/linux/types、 git fetch or pull、q_size 示範、check:size, show, new, size, ih, it, reverse, free, quit；
:::

### 小目標

補回測驗、上課進度

#### 2025q1
[2025q1 第 1 週測驗筆記](/zcxfksKASyaSRRr03A_lmw) ; [題目](https://hackmd.io/@sysprog/linux2025-quiz1) : linked list, double pointer append; memory free block_t tree; Quick sort
week2 [題目](https://hackmd.io/@sysprog/linux2025-quiz2): sort with linux linked list, ;square root 2 with bitwise operation; hash table, two sum leetcode. slice window, sum of subarray.
week3 [題目](https://hackmd.io/@sysprog/linux2025-quiz3): bit operations, setbit, multiplication, module, gcd, test; SIMD within a register , memory, mask; signal , user context;
week4 [題目](https://hackmd.io/@sysprog/linux2025-quiz4): Cyclic Redundancy Check, bitops, rbtree

#### hw4 去年測驗
[M04: quiz3+4](https://hackmd.io/@Urbaner/linux2025-homework4)
回答第 3 周測驗題從測驗一到測驗五和第 4 周測驗題從測
[quiz_try](/vYhoGl0mT-KQi35FbqLmmg) = [2024quiz_try](/vYhoGl0mT-KQi35FbqLmmg)

### lab0 qtest call graph
利用 [egypt](https://lihashgnis.blogspot.com/2016/05/generating-call-graph-of-c-code-linux.html)做圖 , [opt](https://www.youtube.com/watch?v=cd8IYPVRkhI)

## 測驗表單

[連結](https://docs.google.com/forms/d/e/1FAIpQLScCKBf07mQVQaienQtIifg60I3Ihh1WH0XKgn4QU0n7KNLhwQ/formResponse)
[e-mail]
陳科翰
Urbaner3
https://hackmd.io/@Urbaner/linux2025-homework3
在「並行程式設計: 排程器原理」提及可在使用者層級做到搶佔式的 coroutine，這需要 Linux 提供什麼機制？用英語簡述實作手法，以及為了達成搶佔特性，你該如何調整？
signal
〈你所不知道的 C 語言：編譯器和最佳化原理篇〉舉一段程式碼:
int main() { int a = 11, b = 13, c = 5566; int i, result; for (i = 0; i < 10000; i++) result = (a * b + i) / (a * c); return result; } 現在的編譯器最佳化可消弭原本的迴圈和乘法、加法，和除法等運算，最終得到非常簡潔的機械碼？是因為施加哪些一系列最佳化手法？請用英語回答。

〈UNIX 作業系統 fork/exec 系統呼叫的前世今生〉提及 execl 和 execv 系列的系統呼叫在正確執行時，沒有回傳值，即便這些函式原型都指定 int 為回傳型態，為何如此？(英語作答)
*
授課教師講解〈從模除偏差談亂數分布〉時，提過在哪個 Microsoft 主持的開放原始碼專案，針對 arc4random 函式行為和 macOS 潛在的安全議題進行過貢獻並被收錄？(小寫)
*
講解〈以統計觀點看電腦網路傳輸品質〉時，授課教師談及自身近期研究伺服器表現和作業系統核心議題，除了重視 throughput，還特別著重什麼？(小寫)
*

https://hackmd.io/@Urbaner/linux2025-homework4
在「並行程式設計: 排程器原理」提及 neco 是個 C 語言撰寫的函式庫，藉由 coroutine 提供並行處理功能，該專案可與 POSIX Thread 搭配使用，藉此可達成不同於純粹核心或使用者等級的執行緒模型，這稱為什麼？簡述其行為 (小寫，有冒號)
*
在「錯誤更正碼 (ECC) 介紹和實作考量」提及 Linux 核心的 Reed–Solomon error correction，在 Linux 核心原始程式碼中，librs 實作主體位於哪個目錄？ (小寫，有底線)
*
在〈「一切皆為檔案」的理念與解讀〉有款以微核心為基礎的作業系統，將 TCP 連線看待成檔案，允許使用者直接開啟並從而建立 TCP 連線，儘管該作業系統沒有活躍的開發，但仍啟發 Linux 核心的開發 (小寫)
*
在〈你所不知道的 C 語言：連結器和執行檔資訊〉的講解錄影中，提到過往授課為了展現開發作業系統並非困難的事情，授課教師建立一個小型的開放原始碼專案並在該講座探討 linker script 的用法，該專案的名稱是什麼？ (小寫)

https://hackmd.io/@Urbaner/2025q1-homework5

〈Linux 核心設計: 不只挑選任務的排程器〉提及 task_struct 這個相當關鍵的結構體，後者採用哪個結構體來表示任務 (task) 和任務之間的連接關係？
*
list_head
〈Linux 核心設計: 不只挑選任務的排程器〉提及 PID hash table，在 task_struct 中，採用哪個結構體來表示 PID hash table 遇上索引值碰撞時，線性存取 PID 對應的任務節點？
*
hlist_node
〈Linux 核心設計: 不只挑選任務的排程器〉提及 Linux 核心的 switch_to 巨集，在不考慮效能的議題，該巨集在使用者層級可用 C 語言標準函式庫的哪些函式替換？
*

setjmp
〈Linux 核心設計: 不只挑選任務的排程器〉提及 Linux 核心自 v2.6.23 引入 CFS (Completely Fair Scheduler) 作為預設的 CPU 排程器，直到 v6.6 才更換為 EEVDF。CFS 利用哪個資料結構來維護 vruntime 且從中挑選出最小的 vruntime 呢？使用 Linux 核心原始程式碼的用語來作答。
*
rbtree
〈Linux 核心設計: 不只挑選任務的排程器〉提及 Linux 核心一度採用 O(1) scheduler 作為預設的 CPU 排程器，優先權紀錄在由位元構成的陣列中，在 Linux 核心的術語是什麼？(小寫，以 Linux 核心的標頭檔為主)
*
bitmap
延續上題，一旦優先權紀錄於由位元構成的陣列中，若想從低位到高位，尋找指定位元陣列第一個設定為 1 的位元 (即 find first set; ffs)，GCC 提供對應的內建函式是什麼？
*
__builtin_ffs
〈Linux 核心設計: 不只挑選任務的排程器〉提及 Linux 核心採納 CFS 作為預設的 CPU 排程器之前，曾考慮過 Con Kolivas (簡稱 CK) 開發的 SD/RSDL 排程器，不過就算 CK 的成果沒有直接收錄在 Linux 核心，但 CFS 程式碼裡頭仍有其成果並向 CK 致敬，甚至後來移轉到 EEVDF，CK 的成果仍保留。CK 是個傳奇人物，他的主業是專科醫師，請問 CK 是什麼科別的專科醫師？ (中文作答)
*
麻醉科
〈UNIX 作業系統 fork/exec 系統呼叫的前世今生〉提及 Linux 存在一個特別的系統呼叫，可用來建立 thread 和 process，藉此也說明 Linux 核心刻意不區隔二者，該系統呼叫的名稱是什麼？
*
clone