「Linux核心設計/實作」
課程說明 (2024年)
Jim Huang (黃敬群) <jserv.tw@gmail.com>
台灣國立成功大學資訊工程系
警告：kernel有毒
在傳統新年期間重播的《後宮甄嬛傳》中，劇中角色安陵容所食用的杏仁果，實際上是來自於扁桃樹的種仁，其英文名稱為almond，這種杏仁是安全的，不會致命。然而，造成危險的是苦杏仁，英文名稱為apricot kernel，學名為Prunus armeniaca Linne var. ansu Maximowicz，它含有高量的氰化物，這是其毒性的來源。
Source: https://www.facebook.com/groups/system.software2024/posts/1545860499525176/
其實我是單口相聲演員
先看FAQ
注意事項
Linux系統軟體開發經驗談
中央流行疫情指揮中心公告，第二劑和第三劑COVID-19疫苗間需間隔12週。Linux核心大約每10到12週就會發布新的主要版本，換言之，Linux改版比你打疫苗還快。
我是誰？
「爸爸，我要休學」
「真正的教育是能給學生足夠的支撐力量，足夠的表現機會，足夠的信心和歡樂」
我不知如何教書，跟著學生一同開發軟硬體
第一位學生曾讓我很挫折，但他現在是我的精神支柱
納稅人為什麼要把辛苦錢交給大學？不就是對年輕人有期許，栽培他們，使他們有能力、有勇氣去面對產業乃至於整個大環境的變革嗎？
課程著重議題
我們關注什麼？
透過Linux重新認識這世界
782487 commits, 19009 authors, 61725 files, 25584633 lines
著重於21世紀對於大規模應用、大量資料分析，以及各式高效能系統的設計，並從小處著手
本學期嘗試回顧電腦科學軟體、硬體，及數學等基礎知識，帶領學生以專業解決真實世界的各項難題。
我一直相信：教育的使命之一，是讓畢業生真正被這社會需要，從而創造新的需求
透過Linux重新認識這世界
Dominic Walliman製作的〈Map of Computer Science〉短片(具備繁體中文字幕)，簡潔且深刻地探討電腦科學的多個面向，諸如電腦網路、圖形處理、抽象機器及理論(如Turing machine)、NP-Complete問題、計算機架構、排序演算法、資料壓縮、現代密碼學、形式化方法、作業系統排程、異質多核運算、編譯器，和程式語言等等。
上述議題幾乎涵蓋在今日的Linux核心中，換言之，Linux核心已不只是個「核心」，應看待為資訊科技的「基礎建設」，因此，電腦科學的子學科幾乎都可反映在Linux核心中。
Source: https://youtu.be/SzJ46YA_RaA
誠實面對自己
軟體缺失肇因於對電腦系統認知的不足
延伸閱讀: 軟體缺失導致的危害
光是Linked List就充斥著大量你未曾思考過的議題
過去concurrency(並行)和parallelism(平行)議題貌似遙遠，但已是常態
在軟硬體技術高速發展的今日，哪裡有異質多核的環境呢？有，就在你我每天使用的智慧型手機中
我們將思考concurrent資料結構操作，這是許多雲端運算背後的原理
Scalability: 當服務規模(設備數量、自動化操作次數)的負載增長時，系統能被擴展來滿足需求(彈性擴展服務能力)，且不降低服務品質
你沒注意到的浮點數
考慮以下程式碼：
#include <stdio.h>
int main() {
float sum = 0.0f;
for (int i = 0; i < 10000; i++) sum += i + 1;
printf("Sum: %f\n", sum);
return 0;
}
你覺得會輸出什麼？
1 + 2 + 3 + … + 10000 = 10000 * (10000 + 1) / 2 = 50005000
William Kahan教授和IEEE 754
#include <stdio.h>
int main() {
float sum = 0.0f, corr = 0.0f; /* corrective value for rounding error */
for (int i = 0; i < 10000; i++) {
float y = (i + 1) - corr; /* add the correction to specific item */
float t = sum + y; /* bits might be lost */
corr = (t - sum) - y; /* recover lost bits */
sum = t;
}
printf("Sum: %f\n", sum);
return 0;
}
NaN (Not a Number)
IEEE 754可能比你想得更難
考慮以下程式碼：
#include <assert.h>
int main() {
assert(0. == -0.);
assert(1./0. == 1./-0.);
}
你認為執行結果為何？
相當於
IEEE 754
以下程式碼：
#include <assert.h>
int main() {
assert(0. == -0.);
assert(1./0. == 1./-0.);
}
執行結果:
數學和規格書是讓我們從愚昧中獲得救贖的良方
不用急著搜尋關鍵字，你可能沒學會C語言
考慮以下程式碼：
#include <stdio.h>
int main() { return (*******puts)("Hello"); }
能否編譯並執行呢？若可，為什麼呢？
為了解釋前述程式，我們需要重新學習C99規格！
從第一手資料學習：大文豪寫作都不免要查字典，庸俗的軟體開發者如我們，難道不需要翻閱語言規格書嗎？難道不需要搞懂術語定義和規範嗎？
誠實面對自己，從現代C語言開始學
但許多人往往不談object，而急著談論pointer，殊不知，這兩者其實是一體兩面。
依據C99 [6.2.5] Types
“Array, function, and pointer types are collectively called derived declarator types. “
什麼？！array, function, pointer這三者竟有關連?
安全高效率且可延展
if ((codec->capabilities & CODEC_CAP_LOSSLESS) &&
av_get_sample_fmt_name(st->codec->sample_fmt) >
av_get_sample_fmt_name(codec->sample_fmts[0]))
av_log(NULL, AV_LOG_ERROR, "Convertion will not be lossless'\n");
"When two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object.”
C語言可不是只有語法
#include <stdint.h>� uint32_t func(uint32_t x) {� uint32_t n = x;� n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16);� n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);� n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);� n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);� n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);� return n;� }
/*� * Helpers for hash table generation of ethernet nics:� *� * Ethernet sends the least significant bit of a byte first, thus crc32_le� * is used. The output of crc32_le is bit reversed [most significant bit� * is in bit nr 0], thus it must be reversed before use. Except for� * nics that bit swap the result internally...� */� #define ether_crc(length, data) bitrev32(crc32_le(~0, data, length))� #define ether_crc_le(length, data) crc32_le(~0, data, length)
逐字翻譯為C語言不等於Programming!
#include <stdint.h>
int32_t abs(int32_t x) {
int32_t mask = (x >> 31);
return (x + mask) ^ mask;
}
C/C++語言安全和技巧
千萬不要說學校只教理論(1)
千萬不要說學校只教理論(2)
(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))
誠實面對自己！
https://twitter.com/StoryInPicture/status/680983964094300160
背景知識對於理解Linux核心的必要
21世紀的軟體開發均已規模化，絕非「有就好」，而是持續演化和重構，code review是免不了的訓練。Charles-Axel Dein認為好的程式碼應該要:
「需求」層次: 正確 → 安全 → 可讀 → 優雅 → 利他
動腦時間: 空間效率
LeetCode風格題目
Given two numbers say a and b, mark the multiples of 2 and 5 between a and b using less than O(|b – a|) space and output each of the multiples. We have to mark the multiples i.e save (key, value) pairs in memory such that each key either have value as 1 or 0 representing as multiple of 2 or 5 or not respectively.
Examples :
Input : 2 10
Output : 2 4 5 6 8 10
Input: 60 95
Output: 60 62 64 65 66 68 70 72 74 75 76 78
80 82 84 85 86 88 90 92 94 95
解題策略
Approach 1 (simple):
Hash the indices in an array from a to b and mark each of the indices as 1 or 0.
Space complexity : O(max(a, b))
Approach 2 (better than simple):
Save memory, by translating a to 0th index and b to (b-a)th index.
Space complexity : O(|b-a|).
解題策略
Save memory, by translating a to 0th index and b to (b-a)th index.
#include <stdio.h>
#include <stdlib.h>
int main() {
int a = 2, b = 10;
int size = abs(b - a) + 1;
int array[size];
/* Iterate through a to b, If it’s a multiple of 2 or 5, mark index in array as 1 */
for (int i = a; i <= b; i++)
if (i % 2 == 0 || i % 5 == 0)
array[i - a] = 1;
for (int i = a; i <= b; i++)
if (array[i - a] == 1)
printf("%d ", i);
printf("\n");
return 0;
}
持續改進
Size of int in LP64 is 4 bytes. ⇒ an integer in memory is represented by 32 bit positions.
these 32 bit positions can be used instead of just one index to hash binary values.
運用bitwise降低空間開銷的策略
#include <bits/stdc++.h>
using namespace std;
// index >> 5 corresponds to dividing index by 32
// index & 31 corresponds to modulo operation of index by 32
// Function to check value of bit position whether it’s 0 or 1.
bool checkbit(int array[], int index) {
return array[index >> 5] & (1 << (index & 31));
}
// Sets value of bit for corresponding index
void setbit(int array[], int index) {
array[index >> 5] |= (1 << (index & 31));
}
int main() {
int a = 2, b = 10, size = abs(b - a) + 1;
// Size that will be used is actual_size/32
// ceil is used to initialize the array with
// positive number
size = ceil((double) size/32);
// Array is dynamically initialized as
// we are calculating size at run time
int *array = new int[size];
// Iterate through every index from a to b and
// call setbit() if it is a multiple of 2 or 5
for (int i = a; i <= b; i++)
if (i % 2 == 0 || i % 5 == 0)
setbit(array, i - a);
for (int i = a; i <= b; i++)
if (checkbit(array, i - a))
cout << i << " ";
return 0;
}
編譯器最佳化和其陷阱
編譯器最佳化的陷阱:
學習程式語言，若停留在語法，卻沒有深入編譯器和相對應的執行環境，往往事倍功半
編譯器最佳化起於IR
常見編譯器最佳化策略(1)
無論x的值如何變化，f(x)的值必為222x + 282
常見編譯器最佳化策略(2)
因add函式指令很少，因此編譯器會直接將其展開為加法運算，於是sub函式的內容就變成x+(-y)，簡化後就是x—y
降低迴圈中的運算強度，例如乘法改為加法、除法改為乘法，從而累積效益
常見編譯器最佳化策略(3)
若不滿足x*x<10000就跳離迴圈，而x*x<10000等同x<100
降低CPU在branch prediction出錯的次數
常見編譯器最佳化策略(4)
為減少這類有規律的大量運算，編譯器自動進行公式推導，像sum_to_x經編譯後會轉變為return x*(x-1)/2 + x，簡化後就會變成梯形面積公式x*(x+1)/2
這世界不會等你
iPhone X在單核效能評比已超越內建Intel Core-i5的MacBook Pro (2017)
iPhone 7單核效能和內建Intel Core-i7的MacBook Pro只差8%
可是你連處理器都不懂呀！究竟要拿什麼東西來戰文組呢？
承認吧，你只是當年數學考試分數較高，對電腦的認知仍非常有限
https://thenextweb.com/apple/2017/09/12/apples-new-iphone-x-already-destroying-android-devices-g/
這世界不會等你
採用7奈米製程的A12 Bionic處理器，Apple(和它的代工廠台積電)塞進了將近70億個電晶體，讓A12成為整個手機晶片最強大的處理器
A12 Bionic處理器驅動著最新一代 iPhone XS 和 XR，是Apple秋季新品發佈會的主角之一
CPU(6核)、GPU(4核)和一個神經網絡協處理器Neural Engine(8核)，效能比前代A11高了一半左右
Neural engine是款 FPGA (Field-Programmable Gate Array)，針對機器學習去訂製
… (當你讀報導時，有沒有發現自己有如「文組」，即便到資訊工程系所進修呢？) ...
這世界不會等你
採用第二代7奈米製程的A13 Bionic處理器，Apple塞進85億個電晶體(比A11多出約23%)，讓A13成為手機晶片界最強的處理器。A13延續2組高效能核(core) + 4組省電核的64位元Fusion架構設計。2組高效能核可比以往更快地處理複雜任務，預計功耗降低30%；4顆省電核負責處理日常任務，功耗降低40%。
2019年8月，Apple及Qualcomm大和解的同期，Apple以10億美元收購Intel的modem業務的「大多數」
Source: https://bangqu.com/x3728Q.html
凡事我不能創造的東西，我就不理解
美國理論物理學家費曼(Richard Feynman)在辦公室黑板書寫以下話語:
費曼的確認真地實踐上述理念，《費曼物理學講義》這三大卷書便是最清楚的證據。
物理學雖可分為粒子物理、凝態物理、流體力學、原子物理、天文物理等領域，但這些在費曼心中，其實是融合為一，這些學科合起來才可完整呈現大自然，任何只偏愛其中一門的人，就無法欣賞大自然美妙的全貌，換言之，費曼是「知道如何解出每個已被解過的問題」。在書中可見費曼對於每個問題都有獨到的說法，唯有如此，他才會覺得是他所「創造的東西」，也才會認定自己瞭解那些概念。
30年始終默默支持你我生活的Arm
Arm公司授權給全球各式廠商的ARM處理器出貨量達到860億。
以年份對應的出貨量來說，1997年約為900萬，而2014年則是120億，隔年則持續成長到150億。
https://yourstory.com/2016/07/arm-holdings-story/
還有無所不在的Linux，屆滿32歲
1991年8月25日，時年21歲的赫爾辛基大學學生Linus Torvalds在新聞組貼出訊息，表示自己正在開發一款免費的作業系統，同年9月17日發布Linux核心的0.01版Linux。
Linux源自80386個人電腦，扣除桌面系統以外的領域，幾乎都獲得巨大成功，舉凡手機、伺服器、超級電腦、防火牆、路由器、火星探測器、娛樂影音設備，甚至ARRC也採用Linux作為火箭控制系統的基礎。
Linux核心程式碼超過3千7百萬行，每日新增5000行，每小時收錄8個程式修補，10到12周即推出新版Linux核心。全球有來自1300多家公司、超過13500名開發人員貢獻Linux核心的開發。
https://www.facebook.com/itsfoss/photos/a.182637675210341.43761.115098615297581/
758109827663120/
我們該做什麼？
蔡志浩博士：
回顧資訊科技產業
Source:
https://twitter.com/iingwen/status/900711672733507585
策略：擁抱開放原始碼技術和積極展現實力
實際產出
超級電腦在許多領域改變世界
用於需要大量運算的工作，例如天氣預報、地球模擬、運算化學、分子模型、天體物理、密碼分析、機械模擬、基因定序、高頻交易等等。
富岳(Fugaku)超級電腦
直到我看到軟體清單
雖然連簡介都看不懂，但裡頭的詞彙太嚇人:
詞彙提示
這些軟體原已針對x86最佳化，為何還要支援Arm架構呢？
Source: https://community.arm.com/developer/tools-software/hpc/b/hpc-blog/posts/optimizing-genomics-and-the-bwa-aligner-for-arm-servers
無心插柳：SSE2NEON已用於超級電腦
胡適：「發表是最好的記憶」(1)
(下方為參與過系列課程學生部分列表，其中多數在大學畢業前就躍上國際舞臺)
胡適：「發表是最好的記憶」(2)
(下方為參與過系列課程學生部分列表，其中多數在大學畢業前就躍上國際舞臺)
雖然課名是Linux，但可解讀為電腦科學「總複習」
回顧(或說「重新學習」)電腦科學背景知識
只有耐心圓滿完成簡單工作的人，才得以習得輕易完成困難工作的技巧。
Only those who have the patience to do simple things perfectly ever acquire the skill to do difficult things easily.
18世紀德語劇作家兼詩人 Friedrich Schiller
Source: https://twitter.com/WarrenWhitlock/status/876025077178957824
課程終極目標
我連Linux上的應用程式都沒寫過，可學習嗎？
嚴格來說，Linux只是作業系統的核心，其上可運作多種程式，搭配不同的程式開發框架更讓應用程式變得目不暇給。反過來說，作為依循POSIX這項IEEE規範的作業系統核心，Linux提供(絕大多數)有明確規範的系統呼叫，儘管變革快速，但始終堅持這項原則。Linus Torvalds在2001年10月說過：
From a technical standpoint,I believe the kernel will be"more of the same" and that all the _really_interesting stuff will be going out in user space.”
「Linux核心設計」課程的定位是帶著學員探索Linux核心的奧秘，其中不免會接觸到經典的系統呼叫，例如fork和mmap。為免去「舉燭」，我們安排大量的實作和分析訓練，引導學員從使用者層級(user mode)到核心層級均有一定掌握度。抱持「做中學」的態度進行即可。
現代微處理器和Linux核心的機制
A task must run 30% of its time on a big CPU when boosted 15%
Linux核心原始程式碼充斥各式數學(1)
Linux核心原始程式碼充斥各式數學(2)
echo chanscan > /sys/kernel/debug/ieee80211/phy0/ath9k/spectral_scan_ctl
Linux核心原始程式碼充斥各式數學(3)
特別聲明(1)
我的教學技能只有兩個，請不要期待太高：
基礎知識你本該知道，我當然不會教你，但我會指出不足和認知錯誤之處：
特別聲明(2)
寫作業才是主體！
不建議選修的學生族群
Source: https://twitter.com/TweetMe4Moji/status/777333082839842816
踏實
I'm now a 10X programmer.
Source: https://twitter.com/RichRogersIoT/status/807644258165395457
時間和地點
課程密度
「Linux核心實作」課程在週四晚間
「Linux核心設計」課程在週二下午
為何不拆成 (上)/(下) 二門課？
例如Rust程式語言，在 Linux v6.1已正式支援，近期甚至某些GPU裝置驅動程式就用Rust開發，科技大廠也投入可觀開發資源，於是近期重新調整授課比重，但這樣的調整需要數年
評分方式
Source: https://twitter.com/HistoricalPics/status/844164254093770755
修過本課程的校友：莊彥宣
「若當初沒有上過這堂課，一定沒有現在的機運，同學們要好好珍惜，不要退選」
雖然起步較晚(研究所才開始學習C語言程式設計)，但莊彥宣用行動說明，只要把握機會並聚焦，在3年的時間中維護Linux核心無線網路驅動程式，從而成為Linux核心的裝置驅動程式維護者之一。有強度的作品，一個就夠，例如這個目錄就是他維護的，代表Realtek去面對Linux核心技術社群
修過本課程的校友：魏聖儒
「『你終究要面對現實的，何不一開始就面對現實』工程師的面試/篩選是很實打實的一個過程，jserv的課程讓我見識到了什麼是真正的工程問題；在課程內容裡我學習到如何的思考、定性定量分析、修正、驗證的過程，為工程師未來打好基礎。勉勵大家用力地從中汲取養分，去真正的瞭解未來工作的需要跟挑戰。」
修過本課程的校友：郭至軒
「我很推薦jserv的課程，雖然電腦科學有無數的領域可以學習，但我認為對系統程式的了解程度可以決定一個工程師的天花板在哪。畢竟不論前端後端，這些程式都是跑在系統軟體上，如果你/妳想成為解決困難問題的工程師，最終還是會碰到系統程式的。想對學弟妹說：想投 Google 的話，履歷記得寄給我」
修過本課程的校友：周曠宇
「jserv的課程可很好地把內功練好，痛苦過後，會讓你的人生選擇更多。譬如Google和Microsoft這些公司的面試，對待資歷較淺的工程師會考察演算法等基礎知識，而非業務相關的經驗。他們號稱要招募『最聰明』的工程師，我相信能進入成大的同學都不笨，何謂『聰明』呢？至少需要有扎實的工程底子和清晰的思維邏輯，然後做好至少一個專案。非常推薦jserv的課程，勝讀十年盲目摸索」
修過本課程的校友：沈宗穎
「上過jserv的課程可以早點接觸到業界的技術及人脈，這些都是未來找工作時很好的武器。系統軟體也是現在台灣大公司徵才的重點，同學們修課可以盡早領先其他人累積經驗。」
修過本課程的社會人士：Vector
「非常推薦jserv的課程，內容非常的札實，絕對對軟體工程師的職涯非常有幫助。這幾年來硬體的進步快速，Linux核心也不斷地在各方面進步，要對Linux核心入門，並不斷跟上新議題有一定的難度。jserv除了教導各議題的來龍去脈，讓有意願鑽研的學生有方向依循，也透過作業的設計，讓學生可以掌握根基，有能力與勇氣去探索沒碰過的領域。雖然個人只上過一期暑期課程，除了學到很多東西外，更重要的是知道還有很多什麼需要學與實作的。jserv不斷強調的 『誠實面對自己』，對我來說也是這課程給予我的一個重要精華。」
課程資料
近期新增
歡迎選修和旁聽，沒有特別的限制
記得寫作業！
「一律同意」背後的故事
選修學生的權益
來信時，不要說自己「非本科」
不要牽拖「自己電腦慢」
避免非必要的詞彙
有效且直接的溝通
開始挑戰前，請思考這席話
「夢想到底是什麼？有的時候，我覺得夢想遭到濫用。而夢想和白日夢的差別又在哪裡？對我來說，夢想，缺乏一個步步為營、量力而為的態度，以至於夢想一直都像夢一樣，你實在說不出一個所以然，也不知道如何實現他，你也沒有實際的目標，遇到抉擇的時候，你還是選擇玩樂，以至於，夢想就真的成為了一個夢想」 -- c9s