# 2025-06-10/17/24 問答簡記

## [Reinvent the Wheel](https://endler.dev/2025/reinvent-the-wheel/)
Matthias Endler 在〈[Reinvent the Wheel](https://endler.dev/2025/reinvent-the-wheel/)〉中指出，「別重新造輪子」這句箴言往往壓抑好奇心與探索精神。他提醒我們：今日手邊各式精良的「輪子」，正是無數次重新發明與迭代的結晶。

Endler 進一步援引費曼黑板上的名言 "[What I cannot create, I do not understand](http://www.bookzone.com.tw/event/bw1212-14/read-1.asp)"，強調唯有親手打造，即便只是精簡原型，方可揭露表面背後的複雜度並洞悉各種權衡。動手過程中，我們會發現：
1. 即便是字串或路徑這類看似平凡的操作，其背後仍隱藏無窮細節
2. 任何既有工具都是在正確性、效能、可攜性與資源消耗間折衷的結果
3. 只要願意親自嘗試，改進空間永遠存在。

然而，Endler 並非鼓吹盲目捨棄現成方案。他提出的折衷是：「為洞察而重新發明，為影響力而重用」 (Reinvent for insight. Reuse for impact.) 。若目標是深化理解，就勇敢從零構築一次，把握每個設計抉擇；若目標是迅速交付並擴散價值，則善用成熟元件，把時間投注在差異化創新。

這種思維與企業常見的技術策略相呼應：通用元件採購以降低成本，關鍵元件協作以強化生態系統，核心元件自研以維繫技術主導權。理解原理，先造出簡易輪子；趨勢更迭，再造出更先進的輪子。

原型驅動學習不難見，像 [CodeCrafters](https://codecrafters.io/) 強調「從零寫出 Git 或 TCP 伺服器」的課程，正是把「重新發明」系統化為具體學習途徑的典型。

「邊做邊學」的工程文化是培養深度技術能力的要訣。缺乏親手實作，便難以精準評估現有輪子的適用性，更遑論跨越瓶頸、推動下一輪創新。

「從基本定律一步步推導至高層結論」的學習方式，本質上是種創造式學習，將概念牢固植入心中。與此相對的是知道式學習：只求「知其然」，未必「知其所以然」。


教育心理學家 Benjamin Bloom 以其著名的 [Bloom's Taxonomy](https://en.wikipedia.org/wiki/Bloom%27s_taxonomy) 描繪完整學習歷程，分為六級：
* 記憶 (Remember)
* 理解 (Understand)
* 應用 (Apply)
* 分析 (Analyze)
* 評價 (Evaluate)
* 創造 (Create)

資訊爆炸的時代，「我知道了」的滿足感往往偽裝成真正的吸收。若未經深入思考、實作應用、批判反省與再次創造，我們其實仍停留在金字塔的底層。把這座金字塔想像成知識的紀念碑：對個人而言，我們必須親手把石塊一層一層搬上塔尖，才能真正擁有它；對社會而言，則是一代接一代的累積，才得以矗立今日的文明高峰。

費曼的警語提醒我們：唯有創造，才能驗證理解；唯有理解，才配稱為真正的學習。摘錄：
* 「首條原則是：絕不可自欺 —— 最容易受騙的往往正是自己；因此，務必慎之又慎」
> "The first principle is that you must not fool yourself — and you are the easiest person to fool. So you have to be very careful about that."" -- 《Cargo Cult Science》
* 「我們務必為懷疑保留空間；缺乏疑問，便無從進步，也無從學習。要提問，就得先敢於質疑。人們總渴望一錘定音的絕對結論，彷彿釘在木板上般牢不可破，但那種結論並不存在。於是他們恐慌：怎麼能活在世上卻還不知道答案？其實，這不奇怪 —— 我們只以為自己明白。事實上，大多數行動都建立在支離破碎的認知之上：我們不真正知道事情全貌，不明白世界的意義，其餘種種，更未必知曉」
> "We absolutely must leave room for doubt or there is no progress and there is no learning. There is no learning without having to pose a question. And a question requires doubt. People search for certainty. But there is no certainty. People are terrified — how can you live and not know? It is not odd at all. You only think you know, as a matter of fact. And most of your actions are based on incomplete knowledge and you really don’t know what it is all about, or what the purpose of the world is, or know a great deal of other things. It is possible to live and not know." -- 《What Is and What Should Be the Role of Scientific Culture in Modern Society》
* 「最後，再容我一句：我開這門課，並非要替你準備任何考試，更不是為了讓你投身工業或軍事部門。我真正盼望的，是引領你欣賞這個奇妙世界，並體會物理學家觀看世界的方式 —— 我相信這正是現代真正文化的重要一環。或許你不僅會領略其中魅力，甚至會想加入這場人類心智至今最偉大的冒險。」
> "Finally, may I add that the main purpose of my teaching has not been to prepare you for some examination—it was not even to prepare you to serve industry or the military. I wanted most to give you some appreciation of the wonderful world and the physicist’s way of looking at it, which, I believe, is a major part of the true culture of modern times. Perhaps you will not only have some appreciation of this culture; it is even possible that you may want to join in the greatest adventure that the human mind has ever begun." -- 《The Feynman Lectures on Physics》

---

## 從「裝懂」到真正理解
> [出處](https://www.facebook.com/gcsng/posts/pfbid035RLyyjHReiCHgfFuATuf4qN5ewHrWGRhDFxLQc5JwXxQiBhhfkyUG7jV4vUEqCPJl)


學生長期被訓練成考試機器，熟悉題型、擅長答題，卻極少主動追問背後的原理與意義。他們學習的是重點整理和解題技巧，記錄的是關鍵字和標準答案。對多數學生而言，知識不過是應付考試的門票，而非可用來理解世界、解決問題的工具。考試成績成為唯一的努力證明，「考得好」就等同於「學會」。教師在評量上同樣受制度綑綁，只能仰賴分數來評價教學成果。於是，學生靠考卷裝懂，老師靠分數裝教會，教與學淪為一場合演的表面秀，無人揭穿，習以為常。

等到學生進入需要活用知識的情境，例如撰寫報告、說明原理、進行研究，或步入社會時，才驚覺過往死記硬背的內容早已消失殆盡。這不僅僅是「忘記」，而是從未真正記住。某次高年級課堂的經驗令人印象深刻：有學生匿名反映課程太難，進度過深。教師調整教學節奏，安排基礎題目暖身，結果僅有少數人能答對，連基本名詞都模糊不清。這才發現，曾經學過、考過、背過的知識，從未成為腦中的真正資產。

課堂即問的狀況也如出一轍。隨機點名請學生解釋推理脈絡，大多數人或驚慌失措，或答非所問，或詞不達意。這並非學生愚笨或怠惰，而是長期以來從未真正練習過「說清楚一件事」。尷尬的現場反映出學生採用完全違反記憶機制的學習方式，導致大腦根本無法形成穩定的長期記憶。

根據神經科學的研究，記憶的形成並非單靠「輸入」即能長存，而是需要經過嚴謹的歷程。海馬迴在大腦中扮演暫存器的角色，負責初步處理並暫時儲存新資訊。若這些資訊未能經由[重複刺激](https://pmc.ncbi.nlm.nih.gov/articles/PMC3518201/)、[睡眠中的鞏固](https://www.nature.com/articles/nature04286)，以及主動提取和重組等步驟，記憶痕跡往往會在 24 至 48 小時內自然消退，猶如未被儲存的檔案隨時間自動消失。這現象解釋為何學生臨時背誦的內容隔天便遺忘，考前能理解卻無法口頭表達，或平時表現正常但實際應用時卻空白一片。究其原因，正是知識從未經過有效的轉換，未能從海馬迴的快取記憶進入大腦的長期儲存區域。

如今的教育現場中，學生表面上忙碌，實際學習卻流於淺層。他們以關鍵字和標準答案應付任務，逐漸喪失對知識本質的敬畏與探索。真正令人遺憾的，不是學生遺忘什麼，而是從未真正接觸知識的核心。學校長期追求極致效率與高分，教師被要求超綱教學，學生以高難度題目證明自己。這套系統犧牲深度思考和自主探索，學生離開考場後，僅剩零散片段，無法構成可應用的知識結構。

理想的課堂應該鼓勵學生用自己的話重述原理，實際應用於案例，再經過多次提取與變化條件的練習，協助知識沉澱於長期記憶，進而培養靈活運用的能力。這樣的節奏雖然不如刷題快速，卻更契合大腦運作規律，才能打造「帶得走的理解」。

隨堂小考或即時練習，是檢視真實理解的「照妖鏡」，不在於區分強弱，而是即時反映學習盲點，促進師生雙向調整。比起高壓大考，低風險、即時回饋的檢測，更能促進深度學習。

數學學科尤其無法「裝懂」，因為它不像其他科目可依賴語感混過去；唯有真正掌握推理與概念，才能持續前進。當學生只靠死背，遇到變化題型便陷入停滯；而缺乏基本判斷能力者，即使擁有先進科技輔助，也無法質疑或解釋結果，最終只能被動接受、無力應用。

事實上，多數學生選修通識課，未必出於對知識本身的渴望，反而是為輕鬆修課、取得學分或拉高平均成績。要真正推動深化學習，師生都需重新檢視「為何而學、學什麼、如何學」這些根本問題。

殘酷的現實是，相較於深度理解，大多數人其實更傾向於被動接受知識。理解需要主動掙扎，重組舊知識、忍受混亂，付出更多努力；而被動填鴨則只需抄錄、背誦、迎合標準答案，產生「有學」的錯覺。這種傾向並不只出現在學生身上，連成年人在資訊爆炸時代，也常選擇「被餵食」而非自主思考。

教育的成敗不在於分數高低，而在於能否讓學生學會學習、記得久遠、說得明白、用得上手。真正的理解，不是考得高分，而是多年後仍能運用所學解決新問題。教師的任務，不僅是傳授知識，更是協助學生在腦中種下持續成長的種子，為未來面對未知挑戰做好準備。

## 大腦外包
> [出處](https://www.facebook.com/segacheng/posts/pfbid0ngFhuBUcR2YVQNCz3KghW4UDqAz83TMz6pyKVdSVMGMFSbZAyZJb9iLQzdTXnYxrl)
> [Your Brain on ChatGPT: Accumulation of Cognitive Debt when Using an AI Assistant for Essay Writing Task](https://arxiv.org/abs/2506.08872)

麻省理工學院在 6 月 10 日發表研究，為許多人早已隱約感受到的疑慮提供科學佐證。研究人員邀集 54 名參與者，讓他們在 4 個月內撰寫多篇文章，同時配戴腦電圖 (EEG) 裝置以觀測大腦活動。參與者被分為三組：第一組使用 ChatGPT 協助寫作，第二組只能使用傳統搜尋引擎，第三組完全依靠自身思考。結果顯示，長期依賴 ChatGPT 的寫作者，其大腦連結性明顯下降；一旦脫離 AI，他們的腦波圖更像寫作新手而非老練作者，彷彿長期請代駕而忘了如何掌控方向盤。

更令人擔憂的「認知失憶」現象也浮現：高達 83% 的 ChatGPT 使用者，無法準確回憶幾分鐘前在 AI 協助下寫出的句子；純靠自己思考的組別，僅 11% 遇到此困難。研究團隊將這種後果稱為「認知債務」(cognitive debt) ── 用未來的思考力換取眼前的方便，如同過度依賴 GPS 會削弱方向感一樣，只是這次外包的層次提升到「思考」本身。

古老智慧早已提醒我們捷徑的代價。日本武道與茶道的「守・破・離」三階段學習論，正好映照 AI 時代的新挑戰：在「守」階段，學徒必須全然模仿並內化基本功；進入「破」，才開始質疑並突破傳統；最終「離」時，方能開創自我風格。若一開始就讓 AI 生成內容，形同尚未鍛鍊基礎便想直接跳往「破」與「離」，外表也許華麗，根基卻不穩。同樣精神可見於職人文化 ── 壽司學徒花數年只為煮好米飯，因真正的卓越源自對基礎反覆而耐心的錘鍊。

這些文化告誡並非玄談，而是與神經可塑性 (neuroplasticity) 的科學原理相符。大腦遵循「用進廢退」：愈常動用深度思考，相關神經連結愈強；反之長期外包，連結便會弱化。刻意練習 (deliberate practice) 與適度困難 (desirable difficulty) 才是強化連結性的最佳途徑，而 AI 提供的零磨擦便利恰好削去了這段必要的挑戰。

不過 MIT 的同一份研究也帶來希望：參與者若先獨立完成初稿，再用 ChatGPT 潤飾，大腦連結性反而有所增強。關鍵在於先自行承擔認知負荷，再把 AI 視為強化工具。對於正在成長的孩童或任何領域的新手，這點尤其重要：AI 應是潛力無窮的協作者，而非可一股腦外包思考的替身。

從蘇格拉底憂心書寫會損害記憶力，到印刷術、錄音機、電視和 Google 接連引發的「能力退化」恐慌，歷史一再出現類似擔憂。事實上，工具本身並不決定我們是否思考；選擇怎麼使用工具，才是決定性因素。面對 AI，我們真正需要擔心的並非「別人變笨」，而是自己是否善用它來擴張創造力。唯有在保留獨立思考與刻意練習的前提下與 AI 協作，我們才能避免無法償還的認知債務，並持續成為能夠主動思考、富有創見的人。

## 陶哲軒訪談：數學、物理學中最難的問題及人工智慧的未來
> [逐字稿](https://readit.site/a/7qRux/terence-tao-transcript)

## 隱私的保護及拉鋸
> [出處](https://www.facebook.com/ernestchiang/posts/pfbid023nLNiLUxvKUwhmUBi7UnfDt9eyVQaRP9GpAWjnvEnqQjLb1RfHa93j9MBJD3XM4il)

Meta 最近被揭露的「localhost 追蹤」手法，再次證明即使使用者開啟 VPN、無痕模式，甚至清除 Cookie，也難以完全遮蔽自身軌跡。研究人員發現，Facebook 與 Instagram 原生應用程式會在背景悄悄監聽 TCP 埠 12387、12388，以及 UDP 埠 12580–12585；只要手機瀏覽器載入含 Meta Pixel 的網頁，Pixel 便透過 WebRTC 的 STUN 連線，利用「SDP Munging」技巧，把 `_fbp` Cookie 嵌入訊息中送往這些本機埠口，進而直接交付給正在待機的 Meta 應用程式，徹底繞過 Android 的沙盒隔離與瀏覽器端隱私保護 ([theregister.com][1], [localmess.github.io][2])。

此流程可讓 Meta 將瀏覽器中產生的暫時識別碼，與手機 App 內持久的使用者帳號關聯起來，形成跨站且跨應用程式的完整行為檔案。由於發送端是網頁腳本、接收端是裝置同一台機器上的原生 App，傳輸路徑完全不經外網，即便 VPN 或私密視窗都無從攔截 ([citizen8.eu][3])。

規模同樣驚人：調查顯示，全球約 22% 的熱門網站植入 Meta Pixel，累計超過五百萬個網域，足以追蹤數以十億計的 Android 使用者；俄羅斯搜尋引擎 Yandex 的 Metrica 亦長期採用相近技術，顯示此漏洞早已存在多年 ([citizen8.eu][4], [theregister.com][5])。

消息曝光後，多家瀏覽器開始補洞。Chrome 137（2025 年 5 月 26 日）率先封鎖遭濫用的 SDP Munging 與相關本機埠；Firefox 139 也預計跟進，而 Brave 早已內建阻擋機制([cybersecuritynews.com][6])。然而研究團隊指出，任何惡意第三方應用程式，只要搶先佔用相同埠號，就能攔截同樣的本機流量，造成額外隱私風險，顯示 Android 現行的應用程式隔離模型仍有系統級缺口 ([hackaday.com][7])。

在學界與媒體連番質疑後，Meta 於 2025 年 6 月 3 日停止使用該機制，並大幅刪除相關程式碼；Google Play 服務條款亦已表明將禁止此類繞過行為 ([theregister.com][5])。WebRTC 原本是為即時影音溝通而生，卻被包裝成跨 App 的資料隧道；如同《侏羅紀公園》的台詞：「生命總會找到出路」，在隱私保護與商業壓力的角力下，規則終會被鑽出空隙。

[1]: https://www.theregister.com/2025/06/03/meta_pauses_android_tracking_tech/ "Meta Pixel halts Android localhost tracking after disclosure • The Register"
[2]: https://localmess.github.io/?utm_source=chatgpt.com "Covert Web-to-App Tracking via Localhost on Android"
[3]: https://citizen8.eu/localhost-tracking-explained-it-could-cost-meta-32-billion/ "“Localhost tracking” explained. It could cost Meta 32 billion. - Citizen8"
[4]: https://citizen8.eu/localhost-tracking-explained-it-could-cost-meta-32-billion/?utm_source=chatgpt.com "“Localhost tracking” explained. It could cost Meta 32 billion. - Citizen8"
[5]: https://www.theregister.com/2025/06/03/meta_pauses_android_tracking_tech/?utm_source=chatgpt.com "Meta Pixel halts Android localhost tracking after disclosure"
[6]: https://cybersecuritynews.com/track-android-users-covertly/ "Meta Found a New Way to Track Android Users Covertly via Facebook & Instagram"
[7]: https://hackaday.com/2025/06/13/this-week-in-security-the-localhost-bypass-reflections-and-x/?utm_source=chatgpt.com "This Week In Security: The Localhost Bypass, Reflections, And X"

## Google TPU
里昂證券指出，Google TPU v7 (第七代張量處理器) 專案因運算調整需求，下線時程延至 2025 年 9 至 10 月。雖然聯發科提供的 224 G SerDes 與相關 I/O 介面已完成矽驗證，但在與 Google 自研核心進行頻寬與功耗最佳化、封裝協同測試時，仍需要進一步微調。因此，分析師將聯發科 2026 年資料中心 ASIC 營收預估從原先的 24 億美元下修至 16 億美元，卻未調整長期目標價，顯示市場仍對其企業級轉型抱持信心。

此次合作模式採取「Google 自研運算核心 × 聯發科 I/O 模組」的分工，Google 負責張量加速器陣列、晶片網路（NoC）與快取架構，聯發科則輸出 PCIe Gen7 控制器、N3 製程相容的 SerDes PHY，以及與台積電 CoWoS-L 與 RDL-FanOut 封裝整合的 HBM4 高頻寬記憶體解決方案，使板級訊號頻寬可達數十 TB/s。相比過去 TPU v1–v6 項目多由 Broadcom 主導核心設計，這次分工一方面維持與 Broadcom 的長期合作，另一方面透過多元夥伴降低供應鏈風險。

在財務面，Omdia 估計 Google 2024 年對雲端 AI 加速硬體的資本支出約 60 至 90 億美元，下線延後將使晶圓製造、先進封裝、測試與系統組裝的營收認列相應延緩。野村與里昂對此持保守看法，但摩根士丹利表示 TPU v7 I/O 晶片設計定案優於預期，運算核心驗證進入收尾階段，因而重申對聯發科「優於大盤」的評等與最高 1,888 元目標價。

未來市場將進一步關注聯發科在二奈米節點 TPU v9 計畫中的角色，以及透過先進 I/O IP 與封裝技術，持續從智慧型手機 SoC 向企業級、資料中心 ASIC 解決方案的轉型進程。

$\to$ [大摩看好聯發科 TPU 發展 預估新專案將挹注營運成長](https://money.udn.com/money/story/5607/8811343)
$\to$ [Google為何不選博通，改與聯發科聯手？](https://www.storm.mg/lifestyle/5340897)

---

## OSS-NA
在美國丹佛演講，[列表](https://ossna2025.sched.com/speaker/[e-mail])
* Heterogeneous Linux and RTOS Software Architecture for Low-Price RISC-V Cores
* Improve Load Balancing With Machine Learning Techniques Based on the Sched_ext Framework - Jim Huang
* Make Valkey Multi-threaded With Userspace RCU

---

## 簡化的記憶體配置器
測試程式碼:

#include <stdio.h>

#include "myalloc.h"

char buf[1000];

int main()
{
    my_init(buf, sizeof(buf), 10);
    char *x1 = my_malloc(10);
    printf("x1: %p\n", x1);
    char *x2 = my_malloc(20);
    printf("x2: %p\n", x2);
    my_free(x2);
    char *x3 = my_malloc(30);
    printf("x3: %p\n", x3);
    char *x4 = my_malloc(40);
    printf("x4: %p\n", x4);
    my_free(x1);
    my_free(x3);
    char *x5 = my_malloc(50);
    printf("x5: %p\n", x5);
    x5 = my_realloc(x5, 55);
    printf("x5: %p\n", x5);
    my_free(0);
    my_free(x5);
    printf("\n");
    x1 = my_malloc(10);
    for (int i = 0; i < 9; i++) {
        x1[i] = 'A' + i;
    }
    x1[9] = 0;
    x2 = my_realloc(x1, 20);
    printf("[%s]=?[%s]\n", x1, x2);
    my_dump();                                                                                                                                                           
    return 0;
}

補完 [myalloc.h](https://gist.github.com/jserv/ab3a2450238d05547673901dad61869a)

---

## MikazukiHikari

### Q: DAG 是甚麼? 和離散數學中的圖 (graph) 差別最大的地方是?
DAG = 有向無環圖，差別最大的是有所謂的方向性：
離散數學中的圖 (graph)：

### Q: DAG 在 linux kernel 哪裡會用到?
make: build target dependency

make 的根據 `Makefile` 的定義
其核心結構為：

<target>: <dependency>
	$<build commands>

* target：你要建立的東西，例如：`check`,` test`。
* dependency：target 所依賴的檔案，只要其中一個有更新，target 就會重新建置。
* build commands：要執行的「命令」。

整體來說，`make` 會：
* 檢查目標檔案是否存在。
* 檢查 dependency 的時間戳記是否比 target 新。
* 如果有任何 dependency 比 target 新 → 執行對應的建置命令。

### Q: make 與 DAG 的關聯
每個 target + dependency 可以視為圖中的一節點；而邊則是從 dependency 指向 target，表示「要先有這個檔案，才能建出那個檔案」，故整個結構會形成一個 DAG，除此以外，不能有循環相依，否則 make 無法決定建置順序。

舉例：對此 `Makefile` 執行命令 `make modules`

# Makefile for the FUSE filesystem.
#
# Needed for trace events
ccflags-y = -I$(src)
obj-$(CONFIG_FUSE_FS) += fuse.o
obj-$(CONFIG_CUSE) += cuse.o
obj-$(CONFIG_VIRTIO_FS) += virtiofs.o
fuse-y := dev.o dir.o file.o inode.o control.o xattr.o acl.o readdir.o ioctl.o
fuse-y += iomode.o
fuse-$(CONFIG_FUSE_DAX) += dax.o
fuse-$(CONFIG_FUSE_PASSTHROUGH) += passthrough.o
fuse-$(CONFIG_SYSCTL) += sysctl.o
fuse-$(CONFIG_FUSE_IO_URING) += dev_uring.o
virtiofs-y := virtio_fs.o

報錯：

MODPOST fs/fuse/Module.symvers
WARNING: Module.symvers is missing.
         Modules may not have dependencies or modversions.
         You may get many unresolved symbol errors.
         You can set KBUILD_MODPOST_WARN=1 to turn errors into warning
         if you want to proceed at your own risk.
ERROR: modpost: "class_destroy" [fs/fuse/cuse.ko] undefined!
ERROR: modpost: "__ubsan_handle_out_of_bounds" [fs/fuse/cuse.ko] undefined!
ERROR: modpost: "fuse_sync_release" [fs/fuse/cuse.ko] undefined!
ERROR: modpost: "fuse_conn_put" [fs/fuse/cuse.ko] undefined!
ERROR: modpost: "fuse_conn_get" [fs/fuse/cuse.ko] undefined!
ERROR: modpost: "fuse_do_open" [fs/fuse/cuse.ko] undefined!
ERROR: modpost: "fuse_direct_io" [fs/fuse/cuse.ko] undefined!
ERROR: modpost: "__stack_chk_fail" [fs/fuse/cuse.ko] undefined!
ERROR: modpost: "misc_deregister" [fs/fuse/cuse.ko] undefined!
ERROR: modpost: "fuse_do_ioctl" [fs/fuse/cuse.ko] undefined!
WARNING: modpost: suppressed 154 unresolved symbol warnings because there were too many)
make[2]: *** [scripts/Makefile.modpost:145: fs/fuse/Module.symvers] Error 1
make[1]: *** [/home/victor/kernel-build/linux-6.11/Makefile:1878: modpost] Error 2
make: *** [Makefile:224: __sub-make] Error 2

因為嘗試單獨編譯 `kernel module (.ko)`，但這些模組 (像 `cuse.ko`, `virtiofs.ko`) 依賴於其他 kernel symbol 或 `.o`，這些 symbol 並未完整提供，導致報錯。在 linux kernel 中 `make` 所有檔案是有所謂的先後(方向)性的，要先有箝置條件(節點)才能指到下一個節點，如同 DAG 。

## Andrewtangtang
### 假設 mutex lock 的 owner 長期持有 lock 時核心要怎麼處理
mutex 因為擁有了 ownership 的概念，亦即多個執行緒在同一個時間點上，只有一個執行緒可以持有 mutex ，進入 CS 存取資源，然後釋放資源，除此之外，上鎖的執行緒必須自己解鎖後其他的執行緒才能存取該資源，但如果持有 mutex 的執行緒在存取資源時發生 crash 而無法正確釋放資源時，將導致可以被存取的資源逐漸的減少，並讓等待中的其他執行緒無法推進。為了防止這個結果 `POSIX` 規範了 `pthread_mutex_timedlock` 這個函式。根據 [man-pages](https://man7.org/linux/man-pages/man3/pthread_mutex_timedlock.3p.html) 對應的描述
>If the mutex is already locked, the calling thread shall block until the mutex becomes available as in the `pthread_mutex_lock()` function. If the mutex cannot be locked without waiting for another thread to unlock the mutex, this wait shall be terminated when the specified timeout expires.

`pthread_mutex_timedlock()` 在執行緒 acquire 行為上與 `pthread_mutex_lock()` 相同，皆會嘗試取得 mutex，但前者允許設定一個 timeout，在呼叫時需要同時設置一個基於 epoch 創建的 `abstime`，當超過指定的 timeout 時間而該 mutex 仍未被釋放，等待該鎖的其他執行緒將不再繼續等待，而是返回錯誤碼 `ETIMEDOUT` ，等待中的執行緒便可以利用這個錯誤碼來進行錯誤處理。需要特別注意的是`pthread_mutex_timedlock()` 的 timeout 機制僅僅是通知等待中的執行緒，並透過錯誤碼 `ETIMEDOUT` 結束等待。然而這項行為並不會對當前持有 mutex 的執行緒造成任何影響。換句話說，即便某個等待中的執行緒因為超時而退出，mutex 本身仍維持鎖定狀態，如果持有鎖的執行緒因為邏輯錯誤而卡住或異常終止，系統也不會自動釋放這個鎖，而這樣的情況可能會導致想獲取資源的執行緒陷入僵局無法推進。為了提升整體容錯能力，一種更穩健的做法是在建立 mutex 時明確指定 `PTHREAD_MUTEX_ROBUST` 屬性。如此一來，當持鎖的執行緒異常終止時，其他執行緒仍然可以接手該鎖，並進一步對 CS 的資料狀態進行檢查，進而避免因為單一執行緒 crash 導致資源無法正常釋放。

## LeoriumDev

Accelerate memchr using SIMD
:::danger
不要只是「整理」程式碼，實際去驗證已有的程式碼，指出其效益 (當然要實驗)，甚至提出改進方案。程式碼給你，絕對不是拿來背誦和「舉燭」用。
略去無法在你電腦運作的程式碼。
:::

### SWAR

下面這個做法是使用 [SWAR](https://en.wikipedia.org/wiki/SWAR) 技巧來實作，來自[第三周測驗題](https://hackmd.io/@sysprog/linux2025-quiz3)。

利用 bit-wise 運算，去同時比較多個 byte。
把目標字元存放在 `unsigned long` 的每一個 byte，透過 `DETECT_CHAR` 去尋找每一個 byte 是否一樣。
`DETECT_CHAR` 是 XOR `asrc` 和 `mask`。`asrc` 是將 src 轉型成 `unsigned long` 的指標，這麼做的目的是，當 dereference `asrc` 的時候，會一次讀取 4 bytes (如果 aligned)。mask 則是每個 byte 都是目標字元。

#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>

/* Nonzero if X is not aligned on a "long" boundary */
#define UNALIGNED(X) ((long) X & (sizeof(long) - 1))

/* How many bytes are loaded each iteration of the word copy loop */
#define LBLOCKSIZE (sizeof(long))

/* Threshhold for punting to the bytewise iterator */
#define TOO_SMALL(LEN) ((LEN) < LBLOCKSIZE)

#if LONG_MAX == 2147483647L
#define DETECT_NULL(X) (((X) - (0x01010101)) & ~(X) & (0x80808080))
#else
#if LONG_MAX == 9223372036854775807L
/* Nonzero if X (a long int) contains a NULL byte. */
#define DETECT_NULL(X) \
    (((X) - (0x0101010101010101)) & ~(X) & (0x8080808080808080))
#else
#error long int is not a 32bit or 64bit type.
#endif
#endif

/* @return nonzero if (long)X contains the byte used to fill MASK. */
#define DETECT_CHAR(X, mask) DETECT_NULL((X) ^ (mask))

void *memchr_opt(const void *str, int c, size_t len)
{
    const unsigned char *src = (const unsigned char *) str;
    unsigned char d = c;

    while (UNALIGNED(src)) {
        if (!len--)
            return NULL;
        if (*src == d)
            return (void *) src;
        src++;
    }

    if (!TOO_SMALL(len)) {
        /* If we get this far, len is large and src is word-aligned. */

        /* The fast code reads the source one word at a time and only performs
         * a bytewise search on word-sized segments if they contain the search
         * character. This is detected by XORing the word-sized segment with a
         * word-sized block of the search character, and then checking for the
         * presence of NULL in the result.
         */
        unsigned long *asrc = (unsigned long *) src;
        unsigned long mask = d << 8 | d;
        mask |= mask << 16;
        for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
            mask |= mask << i;

        while (len >= LBLOCKSIZE) {
            if (DETECT_CHAR(*asrc, mask))
                break;
            asrc++;
            len -= LBLOCKSIZE;
        }

        /* If there are fewer than LBLOCKSIZE characters left, then we resort to
         * the bytewise loop.
         */
        src = (unsigned char *) asrc;
    }

    while (len--) {
        if (*src == d)
            return (void *) src;
        src++;
    }

    return NULL;
}

### NEON

可以使用 [NEON](https://developer.arm.com/documentation/den0018/a/NEON-Intrinsics/Using-NEON-intrinsics?lang=en) 去加速 [memchr](https://man7.org/linux/man-pages/man3/memchr.3.html) ([linux/lib/string.c](https://github.com/torvalds/linux/blob/master/lib/string.c#L805)) 的實作。

https://github.com/magurosan/strlen_neon

我自己跑的結果 (原程式，秒數單位為 microsecond)： (clang++ -O3 test.cpp && ./a.out)

ave             2      5      7     10     12     16     20     32     64    128    256    512   1024 
memchrANSI  329.7  150.9  105.3   71.7   54.0   39.2   31.7   19.6   10.6    6.0    3.7    2.9    2.6 
memchrNEON  340.2  140.7   98.4   71.0   59.6   45.3   34.9   22.5   12.3    6.5    3.7    2.3    1.8 
memchrAA64  251.7  102.9   71.3   51.7   43.7   33.9   26.9   18.1   10.3    5.7    3.2    2.1    1.8

在這段程式碼裡面，他是呼叫內建的 memchr 函式，我把那段程式碼換成 linux 的 memchr 的結果如下：(clang++ -O3 test.cpp && ./a.out)

ave             2      5      7     10     12     16     20     32     64    128    256    512   1024 
memchrLinux  194.3   78.8   67.5   56.1   55.4   51.5   49.5   44.2   36.7   32.0   28.6   27.8   27.0 
memchrNEON   338.2  139.4   98.0   68.8   58.6   44.2   35.0   22.6   12.0    6.6    3.8    2.5    2.1 
memchrAA64   247.7  100.0   71.0   50.5   43.6   33.5   27.1   18.1   10.0    5.6    3.3    2.1    1.7 

程式邏輯：有一個陣列，每個 element 都有機率從 1 變為 0，是由 `ave` 去決定的，數值越大，0 的 element 就越多；數值越小，0 的 element 就越少。其中，我們就是用 memchr 去找 0 第一次出現的位置。

從上方數據可以發現，當 `ave` 的數值越大，使用 NEON/AA64 優化後的 memchr 效能增加越多。反而是在 `ave` 較小的時候，運行速度最多慢了近兩倍。

為什麼會發生這種情況呢？

在 memchrNEON 及 memchrAA64 函式雖然 `n` 小於 16，都是跳到跟 memchr 類似的程式碼，但速度卻差了最多 143.8 microseconds，我認為這跟 branch misprediction 有關。

還有，為什麼要開到 -O3 才會有顯著的提升效能呢？
下面是沒有開 -O3 的結果：

ave             2      5      7     10     12     16     20     32     64    128    256    512   1024 
memchrLinux  499.6  221.7  177.3  147.7  139.0  122.2  110.5   97.1   88.1   80.6   77.7   76.1   75.5 
memchrNEON  3086.2 1437.5 1106.1  829.9  690.7  519.7  399.8  283.0  179.0  106.6   64.9   43.6   32.9 
memchrAA64  1309.1  544.3  415.6  330.8  299.3  244.1  206.0  140.4   86.1   55.2   36.6   27.4   23.3 

可以看到，NEON 用比不用還慢 (在 `ave` 較小時)。

Arm 的 Developer docs 有提到：
> -O3 . This enables additional optimizations, such as aggressive function inlining and can therefore increase the speed at the expense of image size. Furthermore, this option enables -ftree-vectorize - causing the compiler to attempt to automatically generate NEON code from standard C or C++. ([Arm Developer](https://developer.arm.com/documentation/den0013/d/Optimizing-Code-to-Run-on-ARM-Processors/Compiler-optimizations/GCC-optimization-options))

glibc 實作 NEON 加速的 memchr 的 assembly。
https://github.com/bminor/glibc/blob/master/sysdeps/arm/armv7/multiarch/memchr_neon.S

## liangchingyun
Q: Priority inherence 要做在 Kernel space 還是 User space？
A:
都要
Kernel space 進行排程
User space 判斷 lock 的狀態、持有者

Q: 如何實作 Priority inherence？

提升優先權：搶佔發生之後
還原優先權：釋放資源的當下

## Ian-Yen
futex 是 "fast userspace mutex" 的縮寫，那 futex 快在哪？

每次要做 lock 與 unlock 操作的時候，都需要呼叫 system call，這樣會導致 context swich 需要大量成本。

而 futex 在做 lock 與 unlock 操作的時候，user space 本來就能使用 CAS 的 atomic 操作嘗試取得 lock，如果成功就直接在 user space 完成 lock 與 unlock，不需要進到kernel ，如果失敗的話才會需要用到 system call 來把他放進排程，在 unlock 時，呼叫 futex_wake 喚醒原本正在睡眠的執行緒，然後回到 user space 用 CAS 嘗試取得 lock 。整個取得 lock 的過程，在沒有競爭的情況下，完全不需要進行 system call。這就是 futex 比 mutex 快的地方。

## weiso131
### 課堂中的想法

lock (mutex, owner) {
    while (!CAS(lock, 0, owner))
        Wait(uaddr1=mutex);
}

unlock (mutex, owner) {
    if (CAS(lock, owner, 0)) {
        wake-up(uaddr1=mutex, val=1);
    }    
}
- semaphore 會不會遇到公平問題

### 根據課堂想法實作 lock, unlock
- owner 可以透過 `gettid` 來決定，不需要額外的輸入，但[實作輕量級的 Mutex Lock](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-mutex)到了 `pi_mutex` 才真的實現 owner ，這邊先跳過
- `futex_wait` 與 `futex_wake` 使用[實作輕量級的 Mutex Lock](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-mutex)的實作
- 下方的實作與 spin-lock 的差別只有多了 futex 的操作，可以讓等待的執行序進入睡眠，不用持續佔用 cpu 。然而， futex 之所以會快，是因為它可以藉由使用者端的判斷，在需要的時候才進行 futex 系統呼叫，下方的 `unlock` 會無條件的嘗試由 futex 系統呼叫喚醒一個 thread ，但這在 `wait_queue` 沒東西的時候就會是個無效的操作

static int mutex_lock_naive(struct mutex *mutex)
{
    while (!atomic_bool_cmpxchg(&mutex->futex, 0, 1)) 
        futex_wait(&mutex->futex, 1);  
    return 0;
}

static int mutex_unlock_naive(struct mutex *mutex)
{
    atomic_bool_cmpxchg(&mutex->futex, 1, 0);
    futex_wake(&mutex->futex, 1);
    return 0;
}

### 稍做改進的版本
- 新增 CAS 的狀態 2 ，代表現在 wait_queue 不為空， unlock 時需要進行 wake
- 將 wake 喚醒的最大執行序數量增加為 2 ，這能確保 wait_queue 的元素數量 >= 2 時，其中一個執行序能藉由搶 lock 失敗，將 CAS 狀態設定回 2

static int mutex_lock(struct mutex *mutex)
{
    if (!atomic_bool_cmpxchg(&mutex->futex, 0, 1)) {
        if (atomic_bool_cmpxchg(&mutex->futex, 1, 2))
            goto futex;

        while (!atomic_bool_cmpxchg(&mutex->futex, 0, 1)) {
        futex:
            futex_wait(&mutex->futex, 2);
        }
    }
    return 0;
}

static int mutex_unlock(struct mutex *mutex)
{
    if (atomic_bool_cmpxchg(&mutex->futex, 1, 0))
        return 0;
    if (atomic_bool_cmpxchg(&mutex->futex, 2, 0))
        futex_wake(&mutex->futex, 2);
    return 0;
}

## Hlunlun
Q: 兩個 Thread 哪個會先執行
不一定

Q: Acquire 和 Obtain 的差別？
Acquire 是通過某種技巧獲取，Obtain 是通過努力和計畫得到

Q: 要怎麼避免 deadlock？
兩個鎖的順序要一致

Q: dependency graph 應該要更新什麼資訊
當一個 thread 要加上一個鎖時，找到這個鎖的 id `lid`，檢查已經有的所有鎖 `i`，先檢查 `does_follow(lid, i)` 看有沒有循環，沒有就可以更新 `follows[i][lid]` (代表先鎖了 `i` 再鎖 `lid` )

Q: do_follow 是怎麼偵測有循環的
檢查是否有鎖 a 到鎖 b 有沒有依賴路徑 ( `follows[a][b]` )，DFS 去找 a 有沒有到 b 路徑 ( `follows[a][i]` 與 `follows[i][b]` )，再找有沒有 b 到 a 的路徑 ( `follows[b][a]` )，如果兩個路徑都有找到，代表有循環

## Dingsen-Greenhorn
Q: 何時暫時提升低優先權任務的優先權？再何時釋放提升的優先權 (還原回原本的低優先權) ？

A: 參照，[priority inheritance mutex](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-thread-package#priority-inheritance-mutex-%E5%AF%A6%E9%A9%97) 實驗，那我們知道 priority inheritance 目的是為了避免 Priority Inversion 的發生，為了回答上述問題，何時提升與釋放優先權？必須深入了解 Priority Inversion 的過程，進而可以精準回答問題。

首先，描述使用一般 mutex 發生 priority Inversion 的步驟
根據 [建立相容於 POSIX Thread 的實作](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-thread-package#priority-inheritance-mutex-%E5%AF%A6%E9%A9%97) 畫出示意圖：

digraph PriorityInversion {
    rankdir=TB;
    node [shape=box fontsize=10];

    // Threads
    T1 [label="T1\n(priority: High)"];
    T2 [label="T2\n(priority: Medium)"];
    T3 [label="T3\n(priority: Low)"];

    // Locks
    Lock1 [label="Lock1 (L1)", shape=ellipse, style=filled, fillcolor=lightblue];
    Lock2 [label="Lock2 (L2)", shape=ellipse, style=filled, fillcolor=lightblue];

    // Execution timeline 
    Start -> T3_acquire_L1 [label="T3 acquires Lock1"];
    T3_acquire_L1 -> T3_sleep [label="T3 calls nanosleep"];
    T3_sleep -> T1_try_L1 [label="T1 runs, tries Lock1"];
    T1_try_L1 -> T1_blocked [label="Blocked (Lock1 held)"];

    T1_blocked -> T2_acquire_L2 [label="T2 runs"];
    T2_acquire_L2 -> T2_sleep [label="T2 calls nanosleep"];

    T2_sleep -> Wakeup [label="T2 & T3 wake up (uncertain order)"];

    Wakeup -> T2_runs [label="Case 1: T2 runs first"];
    Wakeup -> T3_runs [label="Case 2: T3 runs first"];

    // Case 1
    T2_runs -> T2_release_L2 [label="T2 releases Lock2"];
    T2_release_L2 -> T3_resume_case1 [label="T3 resumes"];
    T3_resume_case1 -> T3_release_L1 [label="T3 releases Lock1"];
    T3_release_L1 -> T1_resume [label="T1 resumes, gets Lock1"];
    T1_resume -> T1_done [label="T1 completes"];

    // Case 2 (T3 wakes first)
    T3_runs -> T2_preempts_T3 [label="T2 preempts T3"];
    T2_preempts_T3 -> T2_release_L2_case2 [label="T2 releases Lock2"];
    T2_release_L2_case2 -> T3_resume_case2 [label="T3 resumes"];
    T3_resume_case2 -> T3_release_L1_case2 [label="T3 releases Lock1"];
    T3_release_L1_case2 -> T1_resume_case2 [label="T1 resumes"];
    T1_resume_case2 -> T1_done_case2 [label="T1 completes"];

    // Final tasks done
    T2_release_L2 -> Done_T2 [label="T2 done"];
    T3_release_L1 -> Done_T3 [label="T3 done"];
    T1_done -> Done_T1 [label="T1 done"];

    // Case 2 Done
    T2_release_L2_case2 -> Done_T2_case2 [label="T2 done"];
    T3_release_L1_case2 -> Done_T3_case2 [label="T3 done"];
    T1_done_case2 -> Done_T1_case2 [label="T1 done"];

    // Styling priority inversion
    T1 [color=red];
    T2 [color=red];
    T3 [color=red];
    T2_runs -> T3_resume_case1 [style=dashed color=red fontcolor=red label ="Priority Inversion"];
    T2_preempts_T3 -> T3_resume_case2 [style=dashed color=red fontcolor=red label="Priority Inversion"];

    // Final execution order indication
    Done_T2 [label="Task Done: T2", shape=oval, style=filled, fillcolor=lightgrey];
    Done_T3 [label="Task Done: T3", shape=oval, style=filled, fillcolor=lightgrey];
    Done_T1 [label="Task Done: T1", shape=oval, style=filled, fillcolor=lightgrey];

    Done_T2_case2 [label="Task Done: T2", shape=oval, style=filled, fillcolor=lightgrey];
    Done_T3_case2 [label="Task Done: T3", shape=oval, style=filled, fillcolor=lightgrey];
    Done_T1_case2 [label="Task Done: T1", shape=oval, style=filled, fillcolor=lightgrey];

    Done_T2 -> Done_T3 -> Done_T1 [style=bold, label="Actual Order"];
    Done_T2_case2 -> Done_T3_case2 -> Done_T1_case2 [style=bold, label="Actual Order"];
}

T3 擁有 Lock1 並先 sleep：T1 無法繼續，只能等待。

T2 擁有 Lock2 並進入 sleep。

當兩者被喚醒時，若 T2 搶先取得 CPU (或 preempt T3) ，就會導致低優先權的 T3 被延遲，進而延遲高優先權的 T1 發生 priority inversion。

最後的任務完成順序是 T2 → T3 → T1，不符合優先權順序。

接著，就可以實作 Priority ininheritance 出並回答問題，何時提升與釋放優先權？。以下示意圖：

digraph PriorityInheritance {
    rankdir=TB;
    node [shape=box, fontsize=10];

    Start [label="Start"];
    T3_Lock1 [label="T3: acquire Lock1"];
    T3_sleep [label="T3: nanosleep() → sleep\n(yields CPU)"];

    // Highlighted priority inheritance event
    T3_boosted [label="T3 提升優先權 \n T3 boosted", fontcolor=red, color=red, style=bold];

    T1_run [label="T1: tries Lock1 (held by T3)\n→ boosts T3 priority"];
    T1_sleep [label="T1: waits for Lock1 (T3)"];
    T2_Lock2 [label="T2: acquire Lock2"];
    T2_sleep [label="T2: nanosleep() → sleep\n(yields CPU)"];
    
    Wakeup_T3_T2 [label="T3 & T2 wake up\n(interrupt latency affects order)"];

    T2_wake_first [label="T2 wakes first\n→ gets CPU"];
    T3_wake_then [label="T3 wakes\n→ higher priority\n→ preempts T2"];

    T3_wake_first [label="T3 wakes first\n→ gets CPU"];
    T2_wait_after [label="T2 wakes later\n→ waits in runqueue"];

    // Highlighted release of priority
    T3_release_priority [label="T3 task finish\nT3: releases Lock1\n→ priority restored", fontcolor=red, color=red, style=bold];

    T1_resume [label="T1: acquires Lock1\n→ finishes task"];
    T2_resume [label="T2: resumes\n→ finishes task"];

    End [label="Task order: T3 → T1 → T2"];

    Start -> T3_Lock1 -> T3_sleep;
    T3_sleep -> T1_run -> T3_boosted -> T1_sleep;
    T1_sleep -> T2_Lock2 -> T2_sleep;
    T2_sleep -> Wakeup_T3_T2;

    Wakeup_T3_T2 -> T2_wake_first -> T3_wake_then -> T3_release_priority;
    Wakeup_T3_T2 -> T3_wake_first -> T2_wait_after -> T3_release_priority;

    T3_release_priority -> T1_resume -> T2_resume -> End;

    // Visual cluster for both wake-up branches
    subgraph cluster_ordering {
        label="Two Possible Wakeup Orders";
        style=dashed;
        T2_wake_first; T3_wake_then;
        T3_wake_first; T2_wait_after;
    }
}

==TODO==: 援引 Linux 核心和 glibc 原始程式碼進行說明，避免只是「看圖說故事」，不然會陷入「舉燭」的窘境。注意諸多例外狀況。
$\to$ 參閱 [實作輕量級的 Mutex Lock](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-mutex) 和 [建立相容於 POSIX Thread 的實作](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-thread-package)
> 注意: 不要花太多時間 Google 搜尋或者祈求 GPT 賞答案，這種細節很少在公開素材提及，但課程教材的確有探討

:::danger
注意書寫規範：中英文間用一個半形空白字元區隔，正確使用標點符號
:::

---

## NV interview
預計八月離校，三月投簡歷, [NVIDIA career](https://www.nvidia.com/en-us/about-nvidia/careers/)
2020-2022 : COVID-19 政府補貼 (QE 後續)
2022 年下半年：打回原形
power management system SW (firmware)
流程:
HackerRank
OS, CA,
process vs. thread, heap vs. stack, interrupt handling, hazard, pipeline, cache,
Linux kernel
https://hackmd.io/@sysprog/HyQ9UQ2E0 # semu: https://github.com/sysprog21/semu
multi-hart
semu: single hart (RISC-V 的術語, core 的意思, hardware thread)
NVIDIA Tegra SoC
interview
coding interview, LeetCode: easy
1 hr
3 面
DP (dynamic programming), math (X)
linked list in C, binary tree (rbtree?)
[merge sort](https://hackmd.io/@sysprog/c-linked-list) (O)
head count (budget)
2025 Q2
k-th (找出前 k 大的節點): heap sort 的變形
打火 / 多工
https://docs.kernel.org/power/index.html
RSU

## charliechiou
Linux 中斷處理：
1. HW interrupt
2. ISR (interrupt service routine)
3. Linux specific

* voluntary => 呼叫 [sched_yield](https://man7.org/linux/man-pages/man2/sched_yield.2.html)
* preemptive

### HW interrupt
- peripheral (周邊硬體): slow
- CPU: fast
interrupt controller (IC) 會在有「外部」硬體事件到來時，通知 CPU
當 CPU 收到來自 IC 的事件時，會切換到 interrupt 模式 (running -> INT，特權模式的指令)
ISR (中斷處理常式 since 197x) 本質上是軟體，考慮因素:
* interrupt context: 保存原本「中斷發生」前的狀態 (context)
* nested interrupt
* 
* 為何從 B 要回到 C 不能直接回到 A ? -> fairness 的問題，可能會導致 A 任務 wall time 過長。

### ISR

* 離開 ISR 時，會 rescheduling -> ==其中一個會 rescheduling 的時機！！==

ISR 需要考慮的東西 -> 新喚醒的行稱優先權高於正在執行的行程

> [Linux 核心搶佔](https://hackmd.io/@sysprog/linux-preempt)

### [Linux 中斷處理](https://hackmd.io/@sysprog/linux-interrupt)的特色
- 真正的 ISR 用 C 語言撰寫: do_IRQ (in assembly) -> handle_irq_event (in C)
- 區分 **top-half** vs. **bottom-half**: Linux 不支援 nested interrupt，會先處理 hard-IRQ，之後「排程」來執行 softirq
- top-half
- 確認中斷來源：在共享 interrupt line 的情況下，檢查硬體狀態以判斷是否為本裝置觸發的中斷。
- Acknowledgement：向硬體發送確認訊號，表示中斷已被接收，防止重複觸發。
- 排程後續處理：標記需延後處理的任務。
- 其他不可延遲的關鍵任務。
- bottom-half
- softirqs
- tasklets
- workqueues
- 參考 : [2025 年 Linux 核心設計課程作業 —— kxo](https://hackmd.io/@sysprog/linux2025-kxo/%2F%40sysprog%2Flinux2025-kxo-c)

- softirq 透過名叫 ksoftirqd 的 kernel thread 執行，每個 CPU 都有一個這樣的 thread ，可透過以下命令觀察

    $ systemd-cgls -k | grep ksoft

- 在何種狀況，softirq 的執行會被打斷？ -> 其實在問「搶佔何時發生？」
- 只要 Linux 核心設定為 `CONFIG_PREEMPT`，就會安插若干 preemption point
- TTWU (Time to wake up)


preemptive system 的風險/潛在缺點:
* priority inversion
* throughput 下降

- 對時間敏感的適合 preemptive system
- Ex: 高頻交易,天氣預測
- 部份任務用 non-preemptive system 即可
- Ex: 資料庫
## JimmyChongz
> ktcp

### 網頁伺服器 (I/O heavy) 實作在 Linux ==核心== 中，要考慮哪些因素？
* 在 user-space 的 processs/thread (task) 會由 Linux 核心管理資源 (面對 VFS)，反之，khttpd 需要自行呼叫 `kernel_recvmsg`, `kernel_sendmsg`, `kernel_sock_shutdown`, `kernel_accept`，直接對 protocol stack，於是 kernel thread 需要自行處理資源 reclaim
### Q: workqueue 的存在必要性?
- 相比於使用 kthread 來處理 client 連線請求，Workqueue 避免了執行緒無限制增長，如果為每個連線請求都直接建立一個 kthread 來處理，那麼系統中就會有大量的執行緒存在，即使它們大部分時間都在休眠等待 I/O 工作，這會浪費大量的 kernel space 記憶體空間，且每一個 kthread 也會排程，大量的執行緒會讓排程器效率下降，造成 context switch 頻繁、cache 命中率降低；而使用 Workqueue 的核心優勢就是執行緒復用，它提供 worker pool，有固定數量的執行緒，通常等於 CPU 核心數，任務會由這些 worker threads 輪流處理，有效限制了 kthread 的數量。

| Process A
| malloc
| ...
| signal: SIGSEGV
| reclaim

drop-tcp-socket
> In case of being unable to release TCP connections, there is another Linux kernel module, drop-tcp-socket, which allows one to drop specific TCP connections. It is extremely useful for dropping TIME-WAIT sockets.

kernel thread (via `kthread_create` macro), workqueue, Why?

以 CPU scheduler 的觀點:
- kernel thread 會排程
- user process / thread 會排程

以 MMU 的觀點:
每個 process 都有獨立的 address space，但 kernel thread 與核心所有的子系統共用 address space

### Q: 如何得知有效的 kernel thread 總量？ (i.e., 可建立多少 kernel thread)
參考 [Linux kernel Document - threads-max ](https://docs.kernel.org/admin-guide/sysctl/kernel.html#threads-max)
> This value controls the maximum number of threads that can be created using `fork()`.
>
> During initialization the kernel sets this value such that even if the maximum number of threads is created, the thread structures occupy only a part (1/8th) of the available RAM pages.
>
這段說明即使建立最大數量的執行緒，所有的執行緒也只能佔用可用 pages 的 $\cfrac{1}{8}$。
透過以下命令查看系統可容納的最大執行緒數量上限：

$ cat /proc/sys/kernel/threads-max

輸出結果：

126359

為什麼是 $126359$？以記憶體配置的角度來推算系統能配置給 kernel thread 的合理數量：

參考 [Kernel Stacks](https://docs.kernel.org/arch/x86/kernel-stacks.html)
> x86\_64 page size (PAGE\_SIZE) is 4K.
> Like all other architectures, x86\_64 has a kernel stack for every active thread. These thread stacks are THREAD\_SIZE (4*PAGE\_SIZE) big. These stacks contain useful data as long as a thread is alive or a zombie. While the thread is in user space the kernel stack is empty except for the thread\_info structure at the bottom.
:::info
為什麼 THREAD_SIZE 是由 thread stacks 決定？
:::
- 使用以下命令可查看主機的記憶體狀況 (`-k` 是以 KB 為單位)：

    $ free -k

以我電腦的輸出為例：

                   total        used        free      shared  buff/cache   available
    Mem:        16253580     4257188    10870632       74984     1488184    11996392
    Swap:        4194300           0     4194300

- 在 x86_64 架構下的 PAGE_SIZE 為 4KB，所以可以知道這台電腦的記憶體約有 4,063,395 個可用 Pages，且所有執行緒只能佔用可用 Pages 的 $\cfrac{1}{8}$，又一個執行緒佔用 $4$ 個 Page 的空間，所以執行緒只能約有 $126,981$ 個，與 `threads-max` 的值相近。（下方有列計算過程）

    16,253,580 KB / 4 KB = 4,063,395 -> Page 數量
    4,063,395 / 8 ≈ 507,924 -> 所有執行緒能佔用的 Page 數量
    507924 / 4 = 126,981 -> 可容納的最大執行緒數量

[Workqueue 文件](https://docs.kernel.org/core-api/workqueue.html)
> The kernel grew a lot of MT wq users over the years and with the number of CPU cores continuously rising, some systems saturated the default 32k PID space just booting up.

MT 是什麼？ Multi-threaded
saturate 是什麼？ 使...充滿
整句的背景知識：
- 摘自 [ktcp - \(C\)](https://hackmd.io/@sysprog/linux2025-ktcp/%2F%40sysprog%2Flinux2025-ktcp-c)
> MT workqueue 的設計在較多處理器核數的系統上帶來嚴重的資源問題。例如，若建立 100 個 workqueue 且系統有 64 個 CPU，就會產生多達 6400 條 worker threads。由於 Linux PID 空間預設僅有 32K 個行程，一旦系統中啟動大量 MT workqueue，可能在開機過程中就將 PID 耗盡，造成重大問題。

## otischung
> https://github.com/sysprog21/kvm-host

1. Linux KVM 能做什麼？ 在 hardware-assisteted virtualization extension (VT-x, VT-d, etc.) 的基礎之上，提供 cpu/memory virtualization
2. kvm-host 做了什麼？ (利用 KVM API 做了哪些事情，才可達到虛擬化管理？) device virtualization 需要有專門的 VMM (virtual machine monitor) 處理

virtio

QEMU 有許多 device emulation，程式碼龐大
paravirtualization

QEMU vs. KVM

preemption disable 和 enable 之間的區域，是為了保護以下:
* timer interrupt context
* critical section in device driver. spinlock
* internals of CPU scheduler. e.g. CPU migration

spinlock 適合「短的工作」(atomic)，mutex 適合「較長的工作」(sleepable)

> kernel mutexes are sleepable locks

https://github.com/sysprog21/kvm-host/blob/master/src/virtio-net.c
tap/tun : 虛擬的網路裝置
virtqueue: host <--> guest

## Nsly0204
kxo 核心模組中，workqueue 的作用？
> 藉由 workqueue，執行在「不同的 CPU」並模擬二者的對弈
> Q: 如何做到？

1. workqueue 設定的方式 (CPU affinity)
2. 以 CPU 排程器來說，如何確保特定 wq 上的任務是 bound-to-one-CPU

workqueue vs. physical CPU

---

在現代架構 Concurrency Managed Workqueue (CMWQ) 中， worker_pool (圖中 thread_pool) 的概念被提出， wq 作為提供給使用者的介面，透過設定 flag 讓用戶指定建立 per-cpu 或是 unbounded wq，具體的差別在於用戶定義 `work item` 之後，呼叫 `queue_work()` 時會根據 flag 把 `work item` 分配給對應的 worker_pool，分成 per-cpu 和 unbounded worker_pool。

和 cpu 綁定的 worker_pool 可以分成一般的 worker_pool 和高優先級的 worker_pool，也就是說 n 個 cpu 會產生 2n 個和 cpu 綁定的 worker_pools，參照 `workqueue_init_early()` 這些 worker pools 在開機時便已經建立並初始化。

unbounded worker_pool 並沒有在 `workqueue_init_early()` ，但會建立建立預設的 `unbound_std_wq_attrs` 和 `ordered_wq_attrs` ，以供之後的初始化，具體來說 `workqueue_attrs` 包含 `int nice` 、 `cpumask_var_t cpumask` 、 `bool no_numa`。

/**
 * workqueue_init_early - early init for workqueue subsystem
 *
 * This is the first step of three-staged workqueue subsystem initialization and
 * invoked as soon as the bare basics - memory allocation, cpumasks and idr are
 * up. It sets up all the data structures and system workqueues and allows early
 * boot code to create workqueues and queue/cancel work items. Actual work item
 * execution starts only after kthreads can be created and scheduled right
 * before early initcalls.
 */
void __init workqueue_init_early(void)
{
	...

	/* initialize BH and CPU pools */
	for_each_possible_cpu(cpu) {
		struct worker_pool *pool;

		i = 0;
		for_each_bh_worker_pool(pool, cpu) {
			init_cpu_worker_pool(pool, cpu, std_nice[i]);
			pool->flags |= POOL_BH;
			init_irq_work(bh_pool_irq_work(pool), irq_work_fns[i]);
			i++;
		}

		i = 0;
		for_each_cpu_worker_pool(pool, cpu)
			init_cpu_worker_pool(pool, cpu, std_nice[i++]);
	}

	/* create default unbound and ordered wq attrs */
	for (i = 0; i < NR_STD_WORKER_POOLS; i++) {
		struct workqueue_attrs *attrs;

		BUG_ON(!(attrs = alloc_workqueue_attrs()));
		attrs->nice = std_nice[i];
		unbound_std_wq_attrs[i] = attrs;

		/*
		 * An ordered wq should have only one pwq as ordering is
		 * guaranteed by max_active which is enforced by pwqs.
		 */
		BUG_ON(!(attrs = alloc_workqueue_attrs()));
		attrs->nice = std_nice[i];
		attrs->ordered = true;
		ordered_wq_attrs[i] = attrs;
	}

	system_wq = alloc_workqueue("events", 0, 0);
	system_highpri_wq = alloc_workqueue("events_highpri", WQ_HIGHPRI, 0);
	system_long_wq = alloc_workqueue("events_long", 0, 0);
	system_unbound_wq = alloc_workqueue("events_unbound", WQ_UNBOUND,
					    WQ_MAX_ACTIVE);
	system_freezable_wq = alloc_workqueue("events_freezable",
					      WQ_FREEZABLE, 0);
	system_power_efficient_wq = alloc_workqueue("events_power_efficient",
					      WQ_POWER_EFFICIENT, 0);
	system_freezable_power_efficient_wq = alloc_workqueue("events_freezable_pwr_efficient",
					      WQ_FREEZABLE | WQ_POWER_EFFICIENT,
					      0);
	system_bh_wq = alloc_workqueue("events_bh", WQ_BH, 0);
	system_bh_highpri_wq = alloc_workqueue("events_bh_highpri",
					       WQ_BH | WQ_HIGHPRI, 0);
	BUG_ON(!system_wq || !system_highpri_wq || !system_long_wq ||
	       !system_unbound_wq || !system_freezable_wq ||
	       !system_power_efficient_wq ||
	       !system_freezable_power_efficient_wq ||
	       !system_bh_wq || !system_bh_highpri_wq);
}


struct workqueue_struct *alloc_workqueue(const char *fmt,
					 unsigned int flags,
					 int max_active, ...)

所以，3 level workqueue 中，`workqueue_struck` 本身只分只依照 API `alloc_workqueue()` 中的`flag` 參數和 `attrs` 區分，如果我們只討論 `WQ_UNBOUND` 則可以再二分成順序嚴格執行的 oredered type 跟 normal type。

全部的 `workqueue_struck` 共享 `worker_pool` ， `pool_workqueue` 用於整合 `worker_pool`，也可以想成 `pool_workqueue` 把 `workqueue_struck` 中 per-worker_pool 的參數包裝成一個結構體後，以 linked list 的方式掛到 `workqueue_struck` 上。

struct workqueue_struct {
	struct list_head	pwqs;		/* WR: all pwqs of this wq */
	struct list_head	list;		/* PR: list of all workqueues */
    ...
	struct workqueue_attrs	*unbound_attrs;	/* PW: only for unbound wqs */
}

struct pool_workqueue {
	struct worker_pool	*pool;		/* I: the associated pool */
	struct workqueue_struct *wq;		/* I: the owning workqueue */
        
	...
        
	struct workqueue_attrs	*attrs;		/* I: worker attributes */
}

**由以上討論我們知道，若要設定一個 unbounded wq 的 cpu affinity，我們可以**
1. **呼叫 `apply_wokqueue_attrs()` 修改 wq 的 `attrs`。(尚未進行實驗驗證)**
2. **利用 SYSFS 的 wq 直接對 `attrs` 進行更改(尚未進行實驗驗證)**

總結來說如果我們希望把特定的 work item 放到 unbounded wq 但要求在特定的 cpu 上執行，我們需要
1. 宣告 work item
2. 宣告 workqueue with desired `attrs`
3. `queue_work()` 時會根據 unbounded wq 結構體中的 pwqs ，把 work item 放到適合的 worker_pool 裡，在 unbounded wq

由於 worker_pool 本身與 wq 的 `attrs` 掛勾，在 work item 被成工分配的時候就已經確定會在規定的 CPUs 運行。

struct workqueue_attrs {
	int nice;
	cpumask_var_t cpumask;
	cpumask_var_t __pod_cpumask;
	bool affn_strict;
	enum wq_affn_scope affn_scope;
	bool ordered;
};

int apply_workqueue_attrs(struct workqueue_struct *wq,
			  const struct workqueue_attrs *attrs)
{
	int ret;

	mutex_lock(&wq_pool_mutex);
	ret = apply_workqueue_attrs_locked(wq, attrs);
	mutex_unlock(&wq_pool_mutex);

	return ret;
}

## Mike1117
lab0
### Entropy 的定義中，為何有 log?
> 數學推理

若存在這樣一個量稱為「熵（entropy）」的函數 $H(p_1, \dots, p_n)$ ，那他應該滿足以下性質：
1. $H$ 應對所有 $p_i$ 連續。
2. 若所有 $p_i$ 相等，即，則 $H$ 應隨 $n$ 單調增加。
3. 若一個選擇可分為兩個連續的選擇，則原本的 $H$ 應為各部分 $H$ 值的加權平均。

如上圖所示，左側表示三種可能性，
右側則先以各 $\frac{1}{2}$ 的機率，在兩個群組中選一個，若選到下方的群組，再以 $\frac{2}{3}$ 及 $\frac{1}{3}$ 的機率做第二次的選擇，最終的結果機率會與左側相同。
而對於這個例子，我們希望找到一個函式 $H$ 可以滿足
$$
H\left(\frac{1}{2}, \frac{1}{3}, \frac{1}{6}\right) = H\left(\frac{1}{2}, \frac{1}{2}\right) + \frac{1}{2} H\left(\frac{2}{3}, \frac{1}{3}\right)
$$
此處右側第二項的係數為 $\frac{1}{2}$ 是因為第二個選項發生的機率只有一半。

根據上方的`性質 3.` ，我們可以將從 $s^m$ 個等機率的選項中進行一次選擇，拆解為從 $s$ 個等機率的選擇中選擇 $m$ 次，並得到：
$$
A(s^m) = mA(s)
$$
類似的，
$$
A(t^n) = nA(t)
$$

此時我們可以選取一個足夠大的 $n$ ,並找出一個 $m$ 使得
$$
s^m \leq t^n < s^{(m+1)}
$$

兩邊同取 $nlogs$
$$
\frac{m}{n} \leq \frac{\log t}{\log s} \leq \frac{m}{n} + \frac{1}{n}
\quad \text{⇒} \quad
\left| \frac{m}{n} - \frac{\log t}{\log s} \right| < \epsilon
$$
> $\epsilon$ 代表一極小量，因 $n$ 足夠大。

而由於 $A(n)$ 單調遞增，我們可得：
$$
A(s^m) \leq A(t^n) \leq A(s^{m+1})
$$
$$
mA(s) \leq nA(t) \leq (m+1)A(s)
$$
兩邊同除 $nA(s)$ ，得：
$$
\frac{m}{n} \leq \frac{A(t)}{A(s)} \leq \frac{m}{n} + \frac{1}{n}
\quad \text{⇒} \quad
\left| \frac{m}{n} - \frac{A(t)}{A(s)} \right| < \epsilon
$$
$$
\left| \frac{A(t)}{A(s)} - \frac{\log t}{\log s} \right| < 2\epsilon
\quad \quad
A(t) = K \log t
$$
其中 $K$ 為常數，因 `性質 2.` 故必須為正。

---
而現在假設我們有 $n$ 個選項，其機率為可[通約](https://zh.wikipedia.org/zh-tw/%E9%80%9A%E7%B4%84%E6%80%A7)的 $p_i = \frac{n_i}{\sum n_i}$ ，其中 $n_i$ 為整數。
我們可以將從 $\sum n_i$ 個可能中做出選擇，分解為：
先從 $n$ 個選項中按 $p_1, \dots, p_n$ 選一個，再從第 $i$ 個對應的 $n_i$ 個等機率選項中做出選擇。
而根據最開始提及的 `性質 3.` ，兩種選法應產生相同的 Entropy ，即：
$$
K \log \sum n_i = H(p_1, \dots, p_n) + K \sum p_i \log n_i.
$$
因此，
$$
H = K \left[ \sum p_i \log \sum n_i - \sum p_i \log n_i \right]
= -K \sum p_i \log \frac{n_i}{\sum n_i} = -K \sum p_i \log p_i.
$$

Reference: [A Mathematical Theory of Communication, By C. E. SHANNON](https://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf)

---
dudect 論文提及
Curve25519 橢圓曲線: O(1)
### fix-vs-random 是指什麼？
論文的 `Classes definition` 中提及：
>The first class input data is fixed to a constant value,
and the second class input data is chosen at random for each
measurement.

意即 Fix class 會於每次測量時使用一組完全相同的資料作為輸入，而 Random Class 則會於每次測量時使用完全隨機的資料。

## Ian-Yen

static void my_gc()
{
    while ((0 <= last) && heap[last].isFree) {
        hhere = heap[last].ptr;
        heap[last].sz = 0;
        heap[last].ptr = 0;
        last--;
    }
}

fragmentation <-- 會發生
follow-up ::
how to speed up linear scan
tree? => https://hackmd.io/@sysprog/HkNR4RVrn
CS:APP 第 9 章 malloc/free: https://csapp.cs.cmu.edu/3e/README-malloclab

https://www.kernel.org/doc/html/next/core-api/memory-allocation.html
General protection fault (GPF)

除了使用 rbtree 我認為還有一個做法是維護一個雙向 linklist ，並且在每一次使用free的時候檢查前後是不是 `isfree == 1`的地方，如果有就讓他們合起來變成一個比較大的連續空間，這樣應該也可以有效的降低 fragmentation 的程度。

## Nsly0204

malloc(容量)
為何 free() 使用時不用加容量？

若 free(ptr, size) 使用時要指定容量，會有何隱憂？

meta -> 元
metadata 描述資料的資料
為何偏好用 used (reused) ?
- 容量小 ( < 16B, cacheline): cache-friendly
- 容量大 ( >= 4MB = 1K pages ): buddy system: https://hackmd.io/@sysprog/linux-memory

static char *my_reuse(int sz)
{
    MY_ALLOC_T *p = &heap[0];
    for (int i = 0; i <= last; i++) {
        if (heap[i].sz == sz) {
            p = &heap[i];
            return p;
        }
    }
    return 0; /* No suitable block found. */
}

## Max042004
kweb: https://hackmd.io/@sysprog/linux2025-quiz11

SPSC (single-producer/single-consumer)

$ ps aux | grep kweb
root        4815  0.0  0.0      0     0 ?        S    21:15   0:00 [kweb/1]
root        4816  0.0  0.0      0     0 ?        S    21:15   0:00 [kweb/2]
root        4817  0.0  0.0      0     0 ?        S    21:15   0:00 [kweb/3]
root        4818  0.2  0.0      0     0 ?        S    21:15   0:00 [kweb/accept]

            CPU0        CPU1        CPU2        CPU3
            [kweb/1]    [kweb/2]    [kweb/3]    [kweb/accept] (listener) 總機
                                        分機         +
                                                    |
                                                 socket : ring_enqueue (producer: socket)
                                                     |
                                                     +<--- HTTP client
                                                     +<--- HTTP client
                                                     +<--- HTTP client
                                                     +<--- HTTP client
                                                     +<--- HTTP client
                                                     +<--- HTTP client
                            SPSC

很多程式是 CPU bound
網頁伺服器是 I/O bound

worker thread 要呼叫 `kernel_sendmsg`，將 "Hello" (或其他訊息) 傳給 HTTP client

ktcp: CMWQ

kernel_accept 和 accept(2) 的差別

       int accept(int sockfd, struct sockaddr *_Nullable restrict addr,
                  socklen_t *_Nullable restrict addrlen);

worker thread:

Linux kernel (核心)
core (核)
降低 kweb/n 和 kweb/accept 的 migration 的成本: per-cpu runqueue
--> migration 的過程中，vruntime 要重算
Linux 追蹤/紀錄 load (負載) 的機制: PELT

context switch: 3 us (e.g.) vs. migration: 數百 us -> 數百 ms

send 之前要 recv 是 http 處理封包的流程

其他 worker 是 consumer

web server I/O bound 衡量的 throughput 是多少 client 得到訊息

handle cli 程式有沒寫好

process lifecycle 避免佔用資源，然後用其他方法改進這個機制
https://hackmd.io/@sysprog/linux-io-model/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fevent-driven-server
https://hackmd.io/@sysprog/fast-web-server
kernel: softlockup

實驗把 kernel thread 休息的機制拿掉；把 NONBLOCK 拿掉（連線量大時明顯）

---

## 6 月 28 日
https://hackmd.io/@sysprog/linux2025-showcase

---

## otischung
[kvm-host](https://github.com/sysprog21/kvm-host) 的不足/缺陷
- 在 arm64 會因為 `arch/arm64/desc.h` 沒有定義 `VIRTIO_NET_IRQ`，導致編譯失敗。
- 有些 PCI bus 設定不嚴謹，例如 `pci_set_bar()` 一開始只針對 MMIO 做處理，這個在我 fork 的專案的 commit [c4b325e](https://github.com/otischung/kvm-host/blob/c4b325e659e7cceebaed6b39b2eb3d6796b2f5e0/src/pci.c#L145-L156) 有做修正。

KVM API
- create VM
- create VCPU
- run VCPU

| kernel bypassing

virtio-net: guest <--> virtqueue <--> kvm-host <--> tun/tap (用來連線的網路裝置)

guest (Linux)
kvm-host (using KVM APIs. i.e., ioctl)
-------
KVM (as kernel module, part of Linux kernel)
host
TUN/TAP (as builtin, `CONFIG_TUN=y`)

系統的 configuration 可以從 `/boot/config-$(uname -r)` 中找到：

cat /boot/config-`uname -r` | grep -C 5 CONFIG_TAP

CONFIG_NTB_NETDEV=m
CONFIG_RIONET=m
CONFIG_RIONET_TX_SIZE=128
CONFIG_RIONET_RX_SIZE=128
CONFIG_TUN=y
CONFIG_TAP=m
# CONFIG_TUN_VNET_CROSS_LE is not set
CONFIG_VETH=m
CONFIG_VIRTIO_NET=y
CONFIG_NLMON=m
CONFIG_NETKIT=y

`virtio_net_virtq_available_rx` 和 `virtio_net_virtq_available_tx` 使用 poll 系統來檢查 it waits for one of a set of file descriptors to become ready to perform I/O. (本例 TAP)

> Reference: [man7org](https://man7.org/linux/man-pages/man2/poll.2.html)

`virtq_handle_avail` => virtqueue

TODO: 網路連線流程
IRQ handler (SW, running in guest OS)
IRQ chip
Arm GIC (generic interrupt controller)

SGI ?

## qianzsh
[kxo](https://github.com/sysprog21/kxo)
`game_tasklet_func` 如何確保程式碼行為和註解一致？

struct tasklet_struct
{
	struct tasklet_struct *next;
	unsigned long state;
	atomic_t count;
	bool use_callback;
	union {
		void (*func)(unsigned long data);
		void (*callback)(struct tasklet_struct *t);
	};
	unsigned long data;
};

> If tasklet_schedule() is called, then tasklet is guaranteed
to be executed on some cpu at least once after this.

從 `tasklet_schedule` 的程式碼來看，可以發現它只保證變數 state 為 0 的 tasklet 能後續被排進 per-cpu 的 tasklet_vec ， 進而 `__tasklet_schedule_common` 呼叫 `__raise_softirq_irqoff` ， 其中 `or_softirq_pending` 設定 pending bit ，保證 tasklet 之後會被執行。

static inline void tasklet_schedule(struct tasklet_struct *t)
{
	if (!test_and_set_bit(TASKLET_STATE_SCHED, &t->state))
		__tasklet_schedule(t);
}

所以，可以這樣理解： `__tasklet_schedule_common` 被呼叫後，保證這個 tasklet 在之後被執行。

void __tasklet_schedule(struct tasklet_struct *t)
{
	__tasklet_schedule_common(t, &tasklet_vec,
				  TASKLET_SOFTIRQ);
}

static void __tasklet_schedule_common(struct tasklet_struct *t,
				      struct tasklet_head __percpu *headp,
				      unsigned int softirq_nr)
{
	struct tasklet_head *head;
	unsigned long flags;

	local_irq_save(flags);
	head = this_cpu_ptr(headp);
	t->next = NULL;
	*head->tail = t;
	head->tail = &(t->next);
	raise_softirq_irqoff(softirq_nr);
	local_irq_restore(flags);
}

> If the tasklet is already scheduled, but its execution is still not
started, it will be executed only once.

> If this tasklet is already running on another CPU (or schedule is called
from tasklet itself), it is rescheduled for later.

因為 tasklet 被排程前，它的變數 state 會設為 1 ，也就是從 tasklet 被排程到執行期間 state 為 1 ，不會被重新排程。不過 tasklet 執行後 state 重新設為 0 可以被排程，至於相同 tasklet 不同時執行則由 `tasklet_trylock` 保證。以上可以從 `tasklet_action_common` 觀察:

static void tasklet_action_common(struct tasklet_head *tl_head,
				  unsigned int softirq_nr)
{
	struct tasklet_struct *list;

	local_irq_disable();
	list = tl_head->head;
	tl_head->head = NULL;
	tl_head->tail = &tl_head->head;
	local_irq_enable();

	while (list) {
		struct tasklet_struct *t = list;

		list = list->next;

		if (tasklet_trylock(t)) {
			if (!atomic_read(&t->count)) {
				if (tasklet_clear_sched(t)) {
					if (t->use_callback) {
						trace_tasklet_entry(t, t->callback);
						t->callback(t);
						trace_tasklet_exit(t, t->callback);
					} else {
						trace_tasklet_entry(t, t->func);
						t->func(t->data);
						trace_tasklet_exit(t, t->func);
					}
				}
				tasklet_unlock(t);
				continue;
			}
			tasklet_unlock(t);
		}

		local_irq_disable();
		t->next = NULL;
		*tl_head->tail = t;
		tl_head->tail = &t->next;
		__raise_softirq_irqoff(softirq_nr);
		local_irq_enable();
	}
}

CPU0 CPU1 CPU2 CPU3
ksoftirqd/0 ksoftirqd/1 ksoftirqd/2 ksoftirqd/0

tasklet_struct 裡頭的 count 作用是什麼？對照 `softirq_count`
count 可以從上面 `tasklet_action_common` 的函式中觀察，如果為 0 才會執行 tasklet ，另外也可以從 `tasklet_disable` 跟 `tasklet_enable` 中觀察發現 count 決定了 tasklet 是否允許被執行。

static inline void tasklet_disable(struct tasklet_struct *t)
{
	tasklet_disable_nosync(t);
	tasklet_unlock_wait(t);
	smp_mb();
}

static inline void tasklet_enable(struct tasklet_struct *t)
{
	smp_mb__before_atomic();
	atomic_dec(&t->count);
}

TODO: 讓 tasklet 執行較長的時間，觀察排程器的行為
> Q: tasklet 執行中，能否搶佔？

static void my_tasklet_func(unsigned long data) {
  udelay(3);   
    
  tasklet_run_count++;
  if (tasklet_run_count < 2) {
    tasklet_schedule(&my_tasklet);
  }
}

我目前先用以上程式碼觀察排程器的行為，用 ftrace 追蹤的時候發現有三種情況:
- 由原始執行緒 insmod 處理兩次 tasklet 任務
- 由原始執行緒 insmod 處理一次 tasklet 任務，剩下任務交由 ksoftirqd
- 由 ksoftirqd 處理兩次 tasklet 任務

# tracer: function_graph
#
# CPU  TASK/PID         DURATION                  FUNCTION CALLS
# |     |    |           |   |                     |   |   |   |
  2) insmod-2148498 |               |    0xffffffffc493e010() {
  2) insmod-2148498 |   0.851 us    |      __const_udelay();
  2) insmod-2148498 |   0.457 us    |      __tasklet_schedule();
  2) insmod-2148498 |   3.463 us    |    }
 ------------------------------------------
  2) insmod-2148498 =>   ksoftir-32  
 ------------------------------------------

  2)   ksoftir-32   |               |  0xffffffffc493e010() {
  2)   ksoftir-32   |               |    __const_udelay() {
  2)   ksoftir-32   |   0.537 us    |      delay_tsc();
  2)   ksoftir-32   |   0.876 us    |    }
  2)   ksoftir-32   |   1.293 us    |  }

# tracer: function_graph
#
# CPU  TASK/PID         DURATION                  FUNCTION CALLS
# |     |    |           |   |                     |   |   |   |
  1) insmod-2150101 |               |  0xffffffffc493e010() {
  1) insmod-2150101 |               |    __const_udelay() {
  1) insmod-2150101 |   0.567 us    |      delay_tsc();
  1) insmod-2150101 |   1.466 us    |    }
  1) insmod-2150101 |               |    __tasklet_schedule() {
  1) insmod-2150101 |   0.354 us    |      __tasklet_schedule_common();
  1) insmod-2150101 |   0.793 us    |    }
  1) insmod-2150101 |   3.857 us    |  }
  1) insmod-2150101 |               |  0xffffffffc493e010() {
  1) insmod-2150101 |               |    __const_udelay() {
  1) insmod-2150101 |   0.621 us    |      delay_tsc();
  1) insmod-2150101 |   1.084 us    |    }
  1) insmod-2150101 |   1.555 us    |  }

不過在我把 `udelay` 調整成 3000 微秒，並且呼叫三次後，用 ftrace 追蹤出現兩種情況:
- 由原始執行緒 insmod 處理一次 tasklet 任務，剩下任務交由 ksoftirqd
- 由 ksoftirqd 處理兩次 tasklet 任務

我發現如果是 執行緒 insmod 處理 tasklet 任務，儘管這次超時，也會把任務做完，下一次再交由 ksoftirqd 處理。

# tracer: function_graph
#
# CPU  TASK/PID         DURATION                  FUNCTION CALLS
# |     |    |           |   |                     |   |   |   |
  1)   ksoftir-26   |               |  0xffffffffc493e010() {
  1)   ksoftir-26   |               |    __const_udelay() {
  1)   ksoftir-26   | # 3007.827 us |      delay_tsc();
  1)   ksoftir-26   | # 3008.956 us |    }
  1)   ksoftir-26   |               |    __const_udelay() {
  1)   ksoftir-26   | # 3007.854 us |      delay_tsc();
  1)   ksoftir-26   | # 3009.677 us |    }
  1)   ksoftir-26   |               |    __const_udelay() {
  1)   ksoftir-26   | # 3007.864 us |      delay_tsc();
  1)   ksoftir-26   | # 3008.948 us |    }
  1)   ksoftir-26   |               |    __tasklet_schedule() {
  1)   ksoftir-26   |   0.349 us    |      __tasklet_schedule_common();
  1)   ksoftir-26   |   0.791 us    |    }
  1)   ksoftir-26   | # 9031.064 us |  }
  1)   ksoftir-26   |               |  0xffffffffc493e010() {
  1)   ksoftir-26   |               |    __const_udelay() {
  1)   ksoftir-26   | # 3007.811 us |      delay_tsc();
  1)   ksoftir-26   | # 3008.394 us |    }
  1)   ksoftir-26   |               |    __const_udelay() {
  1)   ksoftir-26   | # 3007.815 us |      delay_tsc();
  1)   ksoftir-26   | # 3008.413 us |    }
  1)   ksoftir-26   |               |    __const_udelay() {
  1)   ksoftir-26   | # 3007.780 us |      delay_tsc();
  1)   ksoftir-26   | # 3008.524 us |    }
  1)   ksoftir-26   | # 9026.156 us |  }

# tracer: function_graph
#
# CPU  TASK/PID         DURATION                  FUNCTION CALLS
# |     |    |           |   |                     |   |   |   |
  9) insmod-2159266 |               |    0xffffffffc493e010() {
  9) insmod-2159266 | # 3008.092 us |      __const_udelay();
  9) insmod-2159266 | # 3007.888 us |      __const_udelay();
  9) insmod-2159266 | # 3007.853 us |      __const_udelay();
  9) insmod-2159266 |   0.326 us    |      __tasklet_schedule();
  9) insmod-2159266 | # 9027.217 us |    }
 ------------------------------------------
  9) insmod-2159266 =>   ksoftir-74  
 ------------------------------------------

  9)   ksoftir-74   |               |  0xffffffffc493e010() {
  9)   ksoftir-74   |               |    __const_udelay() {
  9)   ksoftir-74   | # 3007.854 us |      delay_tsc();
  9)   ksoftir-74   | # 3008.454 us |    }
  9)   ksoftir-74   |               |    __const_udelay() {
  9)   ksoftir-74   | # 3007.767 us |      delay_tsc();
  9)   ksoftir-74   | # 3008.260 us |    }
  9)   ksoftir-74   |               |    __const_udelay() {
  9)   ksoftir-74   | # 3007.743 us |      delay_tsc();
  9)   ksoftir-74   | # 3008.131 us |    }
  9)   ksoftir-74   | # 9025.632 us |  }

## thwuedwin
kxo 的 wq (workqueue) 用途
AI 演算法執行在不同的 CPU <-- 作業要求

AI-1 AI-2
CPU1 CPU2

static int __init kxo_init(void)
{
    ...
    /* Create the workqueue */
    kxo_workqueue = alloc_workqueue("kxod", WQ_UNBOUND, WQ_MAX_ACTIVE);
    if (!kxo_workqueue) {
        ret = -ENOMEM;
        goto error_workqueue;
    }
    ...
}

unbound ==> 沒有綁定 (bind) 在特定的 CPU (亦即可以 task migration, load balancing)

`WQ_BH` (BH 就是 bottom-half)
BH workqueues can be considered a convenience interface to softirq. BH workqueues are always per-CPU and all BH work items are executed in the queueing CPU’s softirq context in the queueing order.

All BH workqueues must have 0 max_active and WQ_HIGHPRI is the only allowed additional flag.

BH work items cannot sleep. All other features such as delayed queueing, flushing and canceling are supported.
$\to$ `WQ_BH` 適合什麼場景？對於延遲敏感 (latency-sensitive) 的應用情境，如高速網路 (40+ Gbps)
100/1000 Mbps <-- 一般的網路裝置
Why spell as "queueing" instead of "queuing"?
"BH work items cannot sleep" 指 BH 所在的 CPU 和 context 不能有 kernel preemption

Linux 核心程式碼
ksoftirqd => d 就是 daemon (背景程式)
`kernel/softirq.c`

wake_up_process 的參數是 `struct task_struct *p` --> 會被 CPU 排程器執行

tasklet 有無 `task_struct` ? 沒有！

tasklet 的實作主要在 `kernel/softirq.c`，本質上是鏈結串列管理的 function pointer

include/linux/interrupt.h

struct tasklet_struct
{
	struct tasklet_struct *next;
	unsigned long state;
	atomic_t count;
	bool use_callback;
	union {
		void (*func)(unsigned long data);
		void (*callback)(struct tasklet_struct *t);
	};
	unsigned long data;
};

tasklet 沒有排程，只有排隊 (先來先處理)，對於 CPU 沒有認知，執行在 ksoftirqd，後者可排程，per-cpu

如何降低 workqueue 的 scheduling latency?
WQ_HIGHPRI
Work items of a highpri wq are queued to the highpri worker-pool of the target cpu. Highpri worker-pools are served by worker threads with elevated nice level.

Note that normal and highpri worker-pools don’t interact with each other. Each maintains its separate pool of workers and implements concurrency management among its workers.

[ 電梯 ]
[ 一般等候區 ] [ 優先等候區 ]

highpri 和 cpu 排程器的 priority 不同
https://en.wikipedia.org/wiki/Packet_forwarding

TODO: delayed queueing

nested interrupt

AAAAAAAA (ISR) AAAA
--BBBBBBB (ISR) BBBBBB
---CCCCCCC (ISR)

--------------------------------> time

defer (重視執行者) vs. delay (重視結果)
deferred work
針對共用資源，仍然要用 spinlock 一類的同步處理機制來保護

[--- WQ_BH -----------------]
BBBBBBBBBBBBBBBBBBBBBBBBBBBBB
* *
\ /
spinlock

---------------------------> time

fairness: unfair

## tsaiiuo
neco: coroutine (M:N threading)
perf ==> instruction, cache
perf 沒辦法反映 I/O
perf top

Redis/ValKey/bluebox: frequent I/O
epoll