2026-04-21/23 問答簡記

# 2026-04-21/23 問答簡記 :::warning :warning: 4 月 23 日晚間起，不使用 YouTube 直播，而是改用 Google Meet 跟學員討論 (視作隨堂測驗)，若前 8 週測驗狀況不理想的學員，務必把握問答並在下方登記 ::: ## 登記 4 月 23 日晚間問答 > 在此填入你的 GitHub 帳號名稱 * You ## 貢獻 Linux 核心的第一手經驗 > 分享人: 邱冠維 ([Kuan-Wei Chiu](https://www.linkedin.com/in/visitorckw/)) > [筆記](https://hackmd.io/@visitor-ckw/linux-2026-sharing/edit) 在 Google Pixel 開發團隊考慮到智慧型手機的功耗，需要動態調整頻率和記憶體頻寬自製 CPU，需要處理 boot loader, bring-up Google intern 時期 (實習轉正，與目前任職單位同)，投入 Arm mailbox (異質多核之間的通訊) AMD intern: 參與 PSP 安全處理器和 GPU 通訊的開發近期除了 Linux, glibc, newlib，也貢獻 u-boot 專案 (也擔任 m68k 處理器架構的維護人) Linux 核心的 min heap API 用於 perf，而且每次 context switch 都會用到 min heap，因此直接影響效能，因此投入相關的改進 ### 問答 > :warning: 舉手發問的學員，務必更新本筆記，提及你的問題和後續追蹤，並標注 GitHub 帳號名稱 1. 我現在的研究主題圍繞在 AI，儘管仍會接觸到 Linux，但僅限於安裝工具一類的 CLI，離 Linux 核心很遠，但我仍想探索 Linux，建議從哪裡下手？我已經學習 perf 和 gdb 的使用 > 你會什麼，從你會的地方開始延伸。 > 光是 perf 本身就相當複雜，涉及 perf_events, PMU (event monitoring) 2. 在研究Linux kernel的期間有甚麼技能或是經驗是在工作期間經常用到的嗎? > 第一個想到的是寫 commit message。code 能動是很基本的事情，但是要說服 maintainer 接受你的程式碼。 > 公司內部有 AI 規範，AI 只是輔助工具，需要本人擔保。 3. 當多個方案技術皆正確，但設計考量不同時(可維護性、擴展性、性能...等)，學長衡量的準則為何?以及針對『決定方向』，是否意味著需要預判未來軟硬體的趨勢，又該如何評估並決定方向? > 在實際硬體出來之前，就會在模擬器上先開發 > 晶片需要先有架構師設計跟驗證，軟體寫 driver, bootloader 4. 想請問學長從碩士班到成為 Google 軟體工程師、甚至成為 Linux 核心維護人的這段路，您認為在碩士階段，除了完成實驗室的論文發表之外，最應該投資時間培養的核心能力或工程習慣是什麼？ [Github帳號：CharlieZhangXY] > 先 maintain Linux 再去 Google > 寫很多作業，怎樣的 code 是好 maintain 的，怎麼從 commit 裡發現需求與原因(為什麼要這麼寫) > 學到怎麼溝通、說服別人 > 但作業不會有 co-worker，助教頂多只評分 > 套用到工作上 > watchdog > 在以往作 user space 的東西不會注意 kernel 需要注意的地方，如不用浮點數 5. 想請問學長，如果我的提案與 Linux 核心維護人的見解不一致，但在已有數據支持論點的情況下，除了持續溝通，還有哪些有效管道或策略可以化解分歧？[Github帳號：RayYang421] > 即使有數據還是會被問這個程式碼哪裡重要？要知道對方在意什麼，針對對方想知道的回答，只堅持自己的理論不是溝通 > 會被提問在這地方上面改進有什麼用，不提出點 use case 會有點危險 > Linux 核心的 min heap 有二種 API: inline vs. function call 6. 現在生成式 AI 和強化學習 RL 在許多問題上表現亮眼。從核心維護者的角度來看，您認為未來有沒有機會將機器學習模型（比如輕量級的 RL 演算法）直接整合進官方 Linux 核心的子系統（例如動態資源分配或記憶體管理）中？還是這類任務依然適合留在 User Space 處理？(好像 Oracle 的 bpftune 是一種) [Github帳號：CharlieZhangXY] > [KML](https://github.com/sbu-fsl/kernel-ml): A Machine Learning Framework for Operating Systems & Storage Systems / [paper](https://arxiv.org/abs/2111.11554) > 問題：Linux kernel 強調 deterministic 需求、Linux 原則上禁用浮點數 -> AI/ML 模型高度依賴，無法使用 > 現有研究：聯發科 CPU Machine Learning、聯詠 7. 想請問目前 Google 內部對於 MGLRU 的後續方向是什麼？還有我注意到目前 MGLRU 的部份 Maintainer 與 Reviewer 在 2024 年 10 月後就沒有在這個 subsystem 進行貢獻。我理解 Maintainer 們對於 upstream linux 不是首要任務，不過還是想知道對於長期不活躍的 Maintainer 是否會有處置措施？[Github帳號：c8763yee] > 維護者的結構是樹狀的, 所以底下的 maintainer/reviewer 不再活躍時 upstream maintainer 有權力將他們移除. > :notes: visitorckw > 追問：如果之後工作想往 MGLRU 這個方向做的話可以看哪些 Group 的工作？ 8. 想請問學長，在經歷過初期的 minor fixes 後，若想要往 sub system 做開發，要怎麼確定核心對於改動的接受度，為了避免投入大量時間開發卻被 Maintainer 認為方向錯誤而拒絕，是要先在 lkml 向 maintenir 討論，還是直接先行開發再提出數據並發 RFC 去討論及佐證改動的可行性，但這又要如何確定自己改動的方向是可被接受的呢？ > 發送 RFC 討論自然是相當好的方法! > 盡量有一些具體的東西來跟其他開發者討論更容易讓討論順利些. > :notes: visitorckw 9. 對於一個學習速度比較慢的人來說，想問學長推薦學習 linux 核心中多個主題，還是說深入研究某個感興趣的主題比較好？ > 不覺得學習速度會影響這題的答案. > 無論是誰我通常比較建議後者, Linux codebase 過於龐大, 即使花數十年的時間想要全部精通依然是非常不現實的事情. > :notes: visitorckw 10. 請問學長當 Patch 被 Maintainer 拒絕，你會如何處理？有沒有過技術觀點不一致的情況？ > 嘗試解釋 or 放棄二選一 > 當然會遇到技術觀點不一致的情況 > 這也是為什麼我會提及溝通相當重要, 只是讓 code 能動可能是相對非常簡單的事情. > :notes: visitorckw 11. 學長特別提到，用 LLM 時「容易引起維護者強烈反感」，你自己現在寫 patch 時會怎麼用 LLM ？（哪些事情會、哪些事情絕對不會？）以及你目前在寫 code 時，使用 LLM 的方式為何？ [Github帳號：Xalestar] > 最常用的是在寫 commit message（先自己寫 commit message 再讓 LLM 協助修改），寫 code 方面會在快速掌握很新的東西用，但還是要自己細讀，真的寫 code 比較少用，用在 review 找小 bug 較多 > 有些 Linux 的 macro、API 並沒有官方的 document 等，這時可能會用 LLM 幫助自己進入狀況 > 與 maintainer 溝通時反而不太會用（修改文法錯誤除外），因為對方也看得出來（有時反而會無助於溝通） 12. 想問學長據說現在 Google 面試除了 Coding 白板題之外，公司還會給一個本地端小模型來生成程式碼，然後面試者必須要具備挑錯改進的能力，現在在準備面試的方面也需要準備這塊嗎？另外 Coffe chat 可以怎麼樣跨出邀請的那一步去認識人脈？以及該如何降低 AI 時代 Junior 工程師職缺的焦慮？每天固定刷題、跟著 Jserv 老師的課程？ > 我自己尚未聽說或是經歷過你所說的面試模式, 抱歉. > 我自己也沒有 Coffee chat 過所以不是很清楚 > 降低焦慮這點我覺得並非 AI 時代才會有的問題, 不變的是工程師本質上就是在解決問題, 所以我覺得解決問題的能力會是關鍵. > :notes: visitorckw 13. 想問學長以初學者來說，目前只修過計算機結構，實驗室研究方向與韌體領域沒有直接關係，如果未來想進入韌體部門，在這樣的背景下，是比較建議以論文選擇韌體相關題目，還是專注於累積 side project，對求職比較有幫助。[Github帳號：kstoko02] > 不同主管對這個問題可能會有不同偏好與答案. > 如果是我自己挑人的話, 我會更偏好看到後者. > :notes: visitorckw 14. 想請教學長如果未來的求職目標是尋找韌體開發或系統軟體相關的職缺，會建議在參與 Linux Kernel 貢獻時，刻意挑選與這些職缺相關的子系統（例如特定的驅動程式或架構）作為切入點嗎？另外，想請問如何在履歷上展現這些專案，才能讓主管看見並轉化為面試邀約？在挑選專案或 issue 時，會建議以解決特定領域的實務痛點出發，還是以專案的廣泛應用性為主比較有優勢？ > 以新人來說的話我覺得有做出成果讓主管覺得你的確有解決問題的能力而不是拿一個很水的東西來唬爛他會是最重要的事情. 相關性來說當然越相關自然越有優勢, 但我覺得不論是瞄準特定架構或是廣泛應用都可以. 做出有深度的東西自然就會有機會. > :notes: visitorckw 15. 想請問學長現在 Google 做的工作內容是之前在成大或碩班就有做過的嗎？還是進去才開始學的呢？[Github帳號：Kai5088] > 我不是很確定怎麼定義這裡的 "做過". > 廣義來說我的工作是 Linux kernel 相關所以在我碩班自己玩 upstream Linux 的期間就算是有做過了, 儘管作為學生我幾乎沒寫過 driver 與目前的工作依然有不小的落差. > 另外我是實習轉正並且與實習的時候是相同的部門, 因此實習的時候應該也算做過 (? > :notes: visitorckw 16. 想問學長轉系是基於熱情還是基於現實？實習跟實驗室如何兼顧？請問你的實驗室主要在做哪個零域呢？ > 1. 當時主要是唸工資管時覺得自己還是更想要多寫一點程式比較好玩, 但其實我當時很搖擺不定到底要不要轉系. > 2. 實習與實驗室如何兼顧: 確定你被交辦的任務都能準時繳出來, 沒有什麼很特別的技巧與魔法. > 3. 實驗室主要在做資訊安全的領域. > :notes: visitorckw 17. 請問 google 內部會禁止使用其他公司的 LLM 嗎?如：claude... > 會, 多數公司都會禁止隨意使用公司允許以外的 LLM 以免機密資料外洩. > :notes: visitorckw 18. 想請問學長，有哪些能力是在學校裡不容易被訓練到，但進業界後卻非常重要的？ > 面對一個龐大的專案時如何有效率的分工與溝通 > :notes: visitorckw 19. 學長有提到你在面試的時候常常被主管 challenge 你的相關的修課成績不夠理想，想請問學長遇到這種狀況通常是如何證明自己在這個方面的能力，或是用 side project 就足以彌補。 > 每個主管在意的東西不盡相同. 如果他就是真的很在意成績那自然你怎麼說明解釋都不會有用. 能做的就是盡量展現自己有的與別人不同的東西. > :notes: visitorckw 20. 請問學長在 bootloader 或是 uboot 的研究是因爲在 logi 實習的影響嗎，在在學期間似乎很少有機會去寫到這類的特製化和硬體密切東西，頂多就寫個樹莓派的 bootloader 之類的，和現實bootloader開發也天差地別，還有聽到你反而去維護一個老架構 m68k 這個議題，是爲何去選題的？[Github帳號：frank0988] > 跟羅技不太有關連, u-boot 是我在碩士班畢業後單純好奇 bootloader 裡頭都在做些什麼才開始看的. 其實我沒有特別選擇 m68k, 而是當時留意到 U-Boot 不支援 qemu m68k virt 因而打算動手嘗試試看看, 對我來說是個學習 u-boot 開機流程的很好的機會. > :notes: visitorckw 21. 想進外商公司一定都要有很厚的程式底子也都要持續地刷題，請問學長當時的刷題策略跟頻率是如何呢？ > 其實當時沒什麼想過自己會去 Google 上班, 所以我其實沒有真的為了面試而特別去刷題過. 最早是我的大一室友發現我雖然不是資工系的學生(當時我尚未轉系)但是卻能跟他討論演算法有關的議題而拉我陪他一起寫 leetcode. 而後來我陸續當成茶餘飯後偶爾想到就寫個幾題的遊戲這樣. 當時的我覺得自己畢業後可能就是去台機電上班. > :notes: visitorckw 22. 學長剛剛提到，選擇優化的問題需要有明確動機，例如針對特定 user 或 workflow 中的痛點進行分析。想請問學長當初開始貢獻 Linux kernel 時，是如何發現這些值得優化的問題？通常會從哪些管道尋找？ > 最早是鎖定 lib/ 目錄底下的 library code. min heap 來說的話由於當時 perf 有關的開發者也在討論當中, 因此他們有幫我解釋為什麼 min heap 對於 perf 來說效率很重要. 其他場景可能就需要靠自己研究相關的 user 有誰以及怎麼使用. > :notes: visitorckw 23. 想請問學長，目前 linux kernel 幾乎都是使用 C 語言寫成的，但是最近也有提出使用 rust 取代 C 語言，那目前用 rust 取代 C 語言可能性大嗎? 有需要去學習 rust 嗎? > 目前來說社群中的 top level maintainer 的共識並不是 "取代" C 語言而是與 C 並存. 是否需要學習 rust 這個要看你的目的是想要做什麼. 就如同我不確定應該怎麼回覆 "是否應該要學習 kernel ?" 這樣的問題. 顯然不會每個人都需要但會有些人很需要. > :notes: visitorckw 24. 學長在大學、碩班都有很多實習的經驗。想知道你在不同階段的實習面試以前，你本身已經具備了什麼能力、在實習完以後你獲得了什麼能力；另外，還想請問學長你覺得實習和正職最大的不同是什麼？ > That's a long story. 我盡量簡短 (?) > 第一份實習是在 yahoo global search team 寫網頁後端, 加入前受益於我曾經 AInimal (在做交友軟體的新創) 做網頁後端的經驗而對網頁有一些了解並且受到青睞而獲得 offer, 那是我第一次體驗到原來公司是這樣開會討論的以及體驗到了龐大的 codebase. > 第二份實習在羅技做了一年半, 有趣的事情大概是第一次需要跟 architect 一起開會討論定規格並且我需要從 developer 的角度給出回饋清楚讓對方知道哪些事情做得到哪些不行. > 第三份是去 Google 如同前面提及在這之前做了一些 upstream Linux 的貢獻. 學到了很多比如說 kernel tracepoint, debugfs 等知識 > 第四份是在 AMD, 老實說不是很肯定學了什麼 xD 但體驗到了不同公司文化與做事方式可以有很大的區別. > 實習和正職最大的不同應該是專案的性質, 實習生通常會被給予萬一你完全搞炸了對團隊不至於有過於毀滅影響的專案. 很可能是一些基於現有專案不影響其他人做事擴充出來的東西之類的. 正職自然就是要上戰場做 production 的東西了. 但其他方面來說我覺得差異不會到真的太多. > :notes: visitorckw 25. 聽學長說曾想做 Web 最後卻轉向 Google Silicon，想請問那個關鍵轉折點是什麼？我目前研究 AI 但對系統底層也有熱忱，在面臨『產業工作選擇』時，建議該優先看重工作的發展性，還是個人的實作興趣？ > 關鍵可能是我在碩班做 Linux 的時候帶給我很多成就感 > 另外很感謝我在 Google 實習的 intern host Eric 把我撈起來 > 我是從到 Google 實習並且意識到他是因為看到 Linux 的經驗選擇我時才開始很認真的覺得也許我會把這個當成職業 > :notes: visitorckw 26. 想請教學長，以您目前在 Google 從事 Linux kernel 相關工作的經驗來看，，如果以台灣就業市場、尤其外商研發團隊的職缺分布而言，對即將就業的 new grad 來說，現階段最值得往 Linux kernel 哪些方向精進，會更符合公司對需求？ > 以我自己的經驗來說 new grad 有任何 Linux kernel 經驗的人其實相當少. 所以我覺得只要你能夠說明你對 Linux kernel 任一的子系統有足夠的了解或是做出不錯的成果我相信都已經很符合公司需求. > :notes: visitorckw 27. 學長好，想請問 glibc / newlib 那幾個 CVE 當初是怎麼發現的？跑 fuzzer、讀 code 看出來、還是 debug 別的問題時撞到?以及怎麼判斷一個 bug 該投 CVE 而不是普通 patch? > 當時是在開發 rv32emu 模擬器的時候留意到時間有關的系統呼叫沒有符合預期. 因此嘗試反組譯去看執行了哪些指令去推測問題. 後來發現 libc 當中有著奇怪的單位轉換而去找對應的 source code 而發現的確是時間單位轉換寫錯並且會有 integer overflow 的問題. > :notes: visitorckw 28. 在提交效能優化相關 patch 時，Maintainer 通常最看重哪些效能數據，像是除了 throughput, tail latency 之外，是否會另外要求在多種處理器架構下的 profiling 報告？ > 這個非常取決於特定場景而有不同的答案 > 以 lib/string.c 來說就很可能被要求, 因為很多架構有自己的組合語言實做 > 但是像是以 lib/sort.c 來說就不太會 > :notes: visitorckw 29. 請問你剛剛說的晶片設計下線跟驗證目前是美國還是台灣這邊在做的 > 應該都有 (?) > 甚至印度那邊應該也有 > :notes: visitorckw 30. 想請問學長，你那時候在找工作時，面試官比較常追問修課背景，還是比較在意你實際做過的專案？ > 後者明顯占多數. > 而且我通常甚至不會主動提及我的專題或是碩論, 多數也不太會追問我的專題或碩論, 更不太會問成績, 有問的是少數. > :notes: visitorckw 31. 學長在學生時期對 Linux 與底層開發展現了極大的熱情。我想請問，當最大的興趣變成每天必須面對的日常工作時，熱情會不會被消磨？在 Google 這樣高標準的環境下，你是如何維持工作動力，又同時保有私生活的品質？ > 雖然名義上來說都是 Linux 開發. 但工作所做的事情與我在 open source 貢獻到 Linux 所做的事情依然非常不同. 所以對我自己的感受上來說他們然仍是兩個切很開截然不同的東西. 現況來說不太有你所提及的狀況. > 不過我思考過如果 upstream Linux 變成一個我有領錢的全職開發工作, 我覺得非常有可能出現你所提及的狀況, 會是個對我來說壓力極大的事情. 現在做 open source 我做不出來就可以隨意丟掉不做了而且不會有任何 timeline 想做就做不想做就不做還是有非常巨大的區別的. > 至於第二個問題, 其實我覺得跟我還是學生相同, 如果這件事情會帶給你足夠多的成就感並且不會有讓你感到想要逃避的壓力自然就會很有動力持續下去並保持熱情. > :notes: visitorckw 32. 請問學長在維護這種數量的 kernel 程式碼下，跟工作的時間分配比例大概是什麼樣子 [Github帳號：nyraa] > 目前大概 50%/50%，如工作 8 小時，工作外 8 小時，但是不要學（謹慎學），但總之維護 kernel 也是精進 C 語言能力，也能減少工作出錯。 33. 學長您好，以台灣學生想投外商韌體職缺來說，履歷上哪些經歷最有辨識度，最容易讓面試官願意往下看？ > 我自己的經驗是我看了相當大量的各種精通 AI/LLM 的履歷 > 所以任何 embedded 或是 RTOS/OS 相關的專案會很容易吸引到我的注意 > :notes: visitorckw 35. 平常怎麼 trace code 的 > 可以用 LLM 知道大概往哪裡看、程式碼在哪個目錄，然後花時間追，沒有什麼捷徑，但也不用完全看完整個 kernel 的 code，在意哪裡就深入細節追蹤，公司要的是知道細節的人，不是只有知道概況的 36. 最近我有一個知名外商為期一年的實習offer，剛好學長也有長期實習的經歷，想問在時間允許的情況下，去學年實習是值得的嗎？(**基本薪資**、**大筆時間成本**和**發展性**的權衡) --- ## zz1888 k 個 linked list (assume singly-linked), merge k lists (sorted) interviewer vs. interviewee (先透過提問來展現自身對給定領域的認知) sorted : 如何排序？小到大 linked list 是否 circular? non-circular in place? https://en.wikipedia.org/wiki/In-place_algorithm => in-place HEAD0, TAIL0 HEAD1, TAIL1 HEAD2, TAIL2 ... 案例探討: LeetCode 21. Merge Two Sorted Lists ## patata0717 給定一個 linked list (輸入 head)，如何偵測 circular? struct singly-linked vs. doubly-linked time complexity circular list 何以對 exceptional/special case 有益？ ==> 該回答「不用」circular list，在何種狀況會出錯或有危機？ | 舉出linux kernel的例子來回答何時用circular、何時不用不要憑感覺回答弔胃口 "NULL" 高來來去 FIFO 量化 assume k nodes, ... https://hackmd.io/@sysprog/ry8NwAMvT Concurrency (並行) vs. Parallelism (平行) https://github.com/sysprog21/zhtw-mcp ## MAX990ck bitwise ops (bitops) 背後的應用: Linux device driver, embedded system, ML kernel, ... population count (popcount) 題目敘述: 對於給定的數組，在這裡為 8 位元，求給定數組裡有幾個 1。範例: 00000000 -> 0 01000000 -> 1 00001001 -> 2 (integer) Assume integer is 8 bit range => 8-bit signness -> U complexity -> O(1) constraints X ```c int popcount(uint8_t in) { int num = in; int ans = 0; for(int i=0;i<7;i++){ ans += num&1; num>>=1; } return ans; }// 2 bit for i=0 i<1; i++ //3 ``` > bitmask & binary search ``` 01000000 / \ 0100 0000 / \ / \ 01 00 00 00 ``` 程式碼 ```c int popcount(uint8_t in) { int table[4] = {0, 1, 1, 2}; ans = table[in&3]+table[(in>>2)&3]+table[(in>>4)&3]+table[(in>>6)&3]; return ans; } ``` binary search 8-bit : 4 -> 32-bit : 16 次加法 [漢明權重](https://en.wikipedia.org/wiki/Hamming_weight) 5 => 0101 3 => 0011 https://hackmd.io/@0xff07/MUDAMUDAMUDA ## deantee ### 關於 Hash Tables > Applications of Hash Tables in Linux - Lookup Table (LUT) - Network Addresses (?) - ... > Hash Table Properties and Implementation Consideration - Key (Hash) $\rightarrow$ Value - Bucket list 是指向 linked list 的 head 節點的 list，故此在記憶體中連續 - Perfect Hash Function: 平均上產生最少 Hash Conflict 的 Hash Function (?) - 處理 Hash Conflicts 的方法 - Open-Addressing - Separate Chaining (多數用 linked list -- `hlist`)   > Linux 核心選用 `hlist` 而非 `list` 的動機？在無法保証 hash function 品質的情況下，buckets 不能開太少，否則會 degenerate 成一個 linked list，所以需開較多 bucket 來避免這個情況，而這會增加記憶體開銷。 Linux 核心會積極節省記憶體開銷，一是 kernel stack 記憶體非常有限，不像 user stack 有 8 MiB 的空間，它在 x86-64 上只有 16 KiB，在 x86 (32-bit) 上只有 8 KiB；二是儘可能為 user space 預留記憶體空間。但是 bucket 開得多就自然會有空的 bucket，為了儘可能節省記憶體開銷，所以選擇在每個 bucket 的 head 使用另一種 struct `hlist_head`（與 `list_node` 的區別在於沒有 `prev`，故此這個做法可以為 hash table 中每個 bucket 分別省下 `sizeof(uintptr_t)`（個 bytes）的記憶體開銷。 ### 關於網路 > 網路操作哪用到 hash table? - IP Address 有可能會重複的 IP 地址 - Local LAN: 192.168.0.1 - WAN - WWW - Linux 核心會將路徑上的 IP 地址都加入 hash 的過程中以產生一個獨特的 hash value (?) - routing > TCP vs. UDP - TCP 遇到錯誤會重新傳輸, UDP 不會 - HTTP - HTTP/1 用 TCP - HTTP/2 用 TCP - HTTP/3 用 UDP (95% 的網頁) ## yushiuan9499 process vs. thread 資源分享的程度「分享」？ AS, FD, signal handler, I/O context man clone signal => IPC clone() => pthread_create flag CLONE_VM CLONE_PID CLONE_THREAD CLONE_FILES CLONE_FS CLONE_SIGHAND CLONE_SYSVSEM CLONE_SETTLS CLONE_PARENT_SETTID CLONE_CHILD_CLEARTID MMU/mapping TGID(getpid) 為何區分 CLONE_FILES vs. CLONE_FS CLONE_FS 共享了哪些資訊？ mount 對於每個行程，所能看到的檔案系統可能會不同？ container: namespace/cgroup TODO: 作實驗 open(parent)-close(child)-read/write ```c parent fd=123 (open"ed") \ \ child : close(123) ``` ```c void *close_file(void *fd) { close(*(int *)fd); return NULL; } int main() { int fd; fd = open("test_fork.txt", O_WRONLY | O_CREAT); write(fd, "Hello ", 6); pthread_t thread_id; pthread_create(&thread_id, NULL, (void *)close_file, &fd); pthread_join(thread_id, NULL); write(fd, "world\n", 6); close(fd); return 0; } ``` `test_clone.txt` 的內容 ``` Hello ``` 用 `strace` 查看最後的寫入發生了什麼 ```strace write(3, "world\n", 6) = -1 EBADF (Bad file descriptor) ``` dup, dup2, dup3 ## nyraa 找梗 tail-call optimization `__builtin_ctzl` ```c= unsigned long gcd(unsigned long a, unsigned long b) { unsigned long r = a | b; if (!a || !b) return r; // b >>= __builtin_ctzl(b); if (b == 1) return r & -r; for (;; a -= b) { a >>= __builtin_ctzl(a); if (a == 1) return r & -r; if (a == b) return a << __builtin_ctzl(r); if (a < b) { unsigned long t = a; a = b; b = t; } } } ``` TODO: `a | b;` `return r & -r;` 想做什麼 `r = a | b` 目的是 `r & -r` 為計算出一個數值，只有 `r` 中最低的一個為 1 的位元是 1，代表找出 `r` 也就是 `a` 和 `b` 中最大的共同 2 的冪。從捷徑先看的話，第五行 `b >>= __builtin_ctzl(b); if (b == 1)` 成立的話表示 `b` 是 $2^{n}$，將 `a` 看待為 $k \times 2^{m}$，其中 $k$ 必定是奇數，兩者最大能被同除的數是 $2^{\min(n, m)}$，也就是 `a` 和 `b` 中最大的共同 2 的冪，可以從 `r & -r` 計算得出。 ## ericlin1231 回覆 [gcd 問題](https://hackmd.io/gdgKXMGYRdaNUgsEBKaypg?both=&stext=13569%3A387%3A0%3A1776994445%3AquDhtS) `r = a | b` 將所有 `a` 和 `b` 位元排列中為 1 的部份取出，`if (!a || !b)` 判斷 argument 是否有其中一個數值為 0，比如 `a = 0` 則回傳值 `r = (a | b) = b`，`b >>= __builtin_ctzl(b)` 對 `b` 進行除法，回顧無號數在數學形式上的表示，以 32-bit 無號數為範例。 $$ \sum^{31}_{i = 0}x_{i}2^i, \text{ where } x_i \in \{0, 1\} $$ 當無號數的低 $k$ 個位元為 0 時，上述數學式可以簡化為，這個簡化的步驟就是 `b >>= __builtin_ctzl(b)` 的動作。 $$ \begin{align*} &\sum^{31}_{i = 0} x_i 2^i, \text{ where } x_i = \begin{cases} 0,1 : i > k \\ 1 : i = k \\ 0 : i < k \\ \end{cases} \\ &\sum^{31}_{i = 0} x_i 2^i =\sum^{31}_{i = k}x_i 2^i, \text{ where } x_i \in \{0, 1\} \end{align*} $$ 經由上述簡化的數學式得知，無號數若有低 $k$ 個位元為 0 則 $c \times 2^k$ 可以表示此無號數，因為在 $\sum^{31}_{i = k} x_i 2^i$ 中當 $i \neq k$ 時 $2^i$ 都可以表示為 $2^k$ 乘上 $2$ 的冪。當 `b == 1` 時表示 `b` 的數學表示 $c \times 2^k$ 中 $c = 1$，回傳值為 `r & -r`，若負號運用在無號數上，依據 C99 $\S$ 6.5.3.3 (3) 取負號就是讓數值本身的表示變成負數版本，但是對於無號數來無法表示負數，再依據 C99 $\S$ 6.2.5 (9) 當無號數無法表示結果時，需要將數值取模，注意這個動作和有號數取二補數是相同概念，因此又可以將 `-r` 寫成 `~r + 1`。 $$ (2^{32} - r) \ mod \ 2^{32} $$ 回到前面無號數的數學形式，令 `r` 的低 $k$ 個位元為 0，`~r` 可以讓每個位元翻轉，所以原本的數學形式中 $i \leq k$ 的位元翻轉，而 $i \gt k$ 的位元是 0 還是 1 並不重要。 $$ \sum^{31}_{i = 0} x_i 2^i, \text{ where } x_i = \begin{cases} 0,1 : i > k \\ 0 : i = k \\ 1 : i < k \\ \end{cases} $$ 將 `~r + 1` 之後低 $k$ 個位元會進位到 $i = k$ 的位元，所以 `~r + 1` 可表示為下列數學式，當 `r` 的低 $k$ 個位元為 0 時，`-r` 可以使 $i = k$ 的位元為 1，低 $k$ 個位元為 0。 $$ \sum^{31}_{i = 0} x_i 2^i, \text{ where } x_i = \begin{cases} 0,1 : i > k \\ 1 : i = k \\ 0 : i < k \\ \end{cases} $$ 依據上述數學表示，`-r` 只會進位到 $i = k$ 的位元而不影響 $i \gt k$ 的位元，因為 `-r` 中 $i \gt k$ 部份的位元自 `r` 翻轉過來後並沒有被修改過，所以 `r & -r` 會將 $i > k$ 的位元全部變成 0，而前面令 `r` 為低 $k$ 個位元為 0 的無號數，因此其 $i = k$ 的位元為 1 而 $i \lt k$ 的位元為 0，而 `-r` 的結果亦同，綜合以上，在 `r` 的低 $k$ 個位元為 0 的條件下，`r & -r` 會使結果只有 $i = k$ 的位元為 1。問題是 `r | -r` 計算得出的 $i = k$ 的位元為 1 其來自 `a` 還是 `b`，總共會有三種情況。 1. `a` 中 $i = k$ 的位元為 1 而 `b` 中 $i = k$ 的位元為 0 2. `b` 中 $i = k$ 的位元為 1 而 `a` 中 $i = k$ 的位元為 0 3. `a` 和 `b` 同時在 $i = k$ 的位元為 1 根據先前 `r` 的低 $k$ 個位元為 0 的假設，首先探討第一個情況，根據條件，`a` 和 `b` 的低 $k$ 個位元也應為 0，加上 `b` 中 $i = k$ 個位元為 0 使 `b` 中 $i \leq k$ 個位元都為 0，最終 `r & -r` 得出的 $i = k$ 的位元為 1 來自 `a`，故 `a` 可以表示為 $c \times 2^k$ 而 `b` 可以表示為 $p \times 2^t$ 其中 $t \gt k$ 故 `b` 可以被表示為 $2^k$ 乘上 $2$ 的冪，而 $2^k$ 就是 `a` 和 `b` 的 gcd，第二種情況就是 `a` 和 `b` 對調的情況，就不加贅述，再來探討第三種情況，既然 `r` 的低 $k$ 個位元都是 0，且 `a` 和 `b` 同時在 $i = k$ 的位元為 1，故 `a` 和 `b` 都可以表示為 $2^k$ 乘上 $2$ 的冪，因此驗證 fast path 計算結果的正確性。討論中提到的程式碼對應到 Linux 核心中 [binary_gcd](https://github.com/torvalds/linux/blob/27d128c1cff64c3b8012cc56dd5a1391bb4f1821/lib/math/gcd.c#L20-L39)。 ```c static unsigned long binary_gcd(unsigned long a, unsigned long b) { unsigned long r = a | b; b >>= __ffs(b); if (b == 1) return r & -r; for (;;) { a >>= __ffs(a); if (a == 1) return r & -r; if (a == b) return a << __ffs(r); if (a < b) swap(a, b); a -= b; } } ``` 當程式碼在 `b >>= __ffs(b)` 驗證 `b` 不會使 gcd 計算存在 fast path 時就會進入迴圈，第一次進入迴圈檢查 `a` 是否使計算 gcd 存在 fast path，所以 `binary_gcd` 在置換 `a` 和 `b` 之前會分別檢查 `a` 和 `b` 是否可以使 gcd 計算存在 fast path，若有其中一個 argument 的數學表示為 $1 \times 2^k$ 且另一個 argument 的數學表示為 $c \times 2^t$ 其中 $t \geq k$ 則 $2^k$ 就是此兩個 argument 的 gcd。假設原 argument `a` 和 `b` 的數學表示為 $c \times 2^m$ 和 $d \times 2^n$，試證明第一次抵達 `if (a == b)` 之後在迴圈的運算最終都可以正確的計算出 gcd，會到達這個 statement 代表目前不存在 fast path，此時 `a` 和 `b` 分別為 $c$ 和 $d$，原始的 `a` 和 `b` 分別被去除低 $m$ 個和 $n$ 個為 0 的位元，而 `r` 目前的低 $k$ 個位元為 0，其中 $k = \min(m, n)$，到達 `if (a == b)` 的時候若 $c = d$ 則回傳 $c \times 2^k$，因為 $k \geq n$ 因此 $d \times 2^n$ 可以表示為 $c \times 2^k$ 乘上 $2$ 的冪，故 $c \times 2^k$ 是最大公因數。用 loop invariant 證明 binary gcd 的正確性，定義輸入為 $A = c \times 2^m$, $B = d \times 2^n$, $k = \min(m, n)$，得 $r = 2^k$，定義 $a_i$ 和 $b_i$ 為經過 `__ffs` 運算的結果，故 $a_0 = c$, $b_0 = d$ 且 $a_i$ 和 $b_i$ 為奇數，此程式碼的迴圈開始是從第一次到達 `a -= b` 開始，設定 loop invariant 有兩個條件，首先 $a_i$ 和 $b_i$ 為奇數，其二是 $gcd(a_i, b_i) = gcd(a_i - b_i, b_i) = gcd(c, d)$。在 `if(a < b) swap(a, b)` 後 $a \geq b$，從 `a -= b` 開始，因為 $a$ 和 $b$ 都為奇數，所以 $a - b$ 為偶數，$b$ 依然為奇數不變，回到 `for` 開頭，`a >>= __ffs(a)` 後 $a$ 又變回奇數，滿足 loop invariant 第一個條件，此時有兩種情況會使計算中止並回傳 gcd。 - $a = 1$ : 由 loop invariant 第二個條件 $gcd(a, b) = gcd(1, b) = gcd(c, d)$，回傳 gcd 為 $gcd(1, b) \times 2^k = 1 \times 2^k = 2^k$ - $a = b$ : 由 loop invariant 第二個條件 $gcd(a, b) = gcd(a, a) = gcd(c, d)$，回傳 gcd 為 $gcd(a, a) \times 2^k = gcd(c, d) \times 2^k = a \times 2^k$ 即使目前的 $a$ 和 $b$ 不符合中止條件，重新回到迴圈開頭計算依然符號 loop invariant 因此該演算法的實做為正確。 :TODO 計算 binary gcd 實際的執行時間，不使用 big O notation 而是需要計算出係數

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.