# Linux 核心設計: 第 1 週發展回顧
:::info
由於課程討論區的訊息較多，在此彙整到共筆，歡迎參照並在「延伸閱讀」處參與討論。 --jserv
:::

## 注意事項

* 2019 年 2 月 26 日課堂時間，想訂購 [CS:APP 教科書](https://hackmd.io/c/S1vGugaDQ) 的同學，可拿台幣 750 元給助教，預計三月中旬發書;
* 每週二 19:30 在資訊系舊館一樓 4217 室安排 office hour，請多利用;
* 2019 年 3 月 2 日 `14:00` - `16:00`，在成功大學自強校區電機系館一樓 92185 教室，安排本學期第一次的 PyTorch Tainan 聚會，主題是 "Selective Search for Object Recognition"，是 R-CNN 中也有用到的一個相當重要的物件偵測演算法，歡迎對深度學習、機器視覺有興趣的同學來參加！ ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/308740596510470/)==
* 2019 年 3 月 4 日 14:00，成功大學資訊工程系邀請 Penn State University 的P rof. Vijaykrishnan Narayanan (IEEE Fellow, ACM Fellow) 發表演說，講題是 "Distributed Learning and Inference at the Edge" ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/306565310061332/)==
* 本學期課程會透過 email 傳遞課程公告，請 **選修和旁聽的同學** 協助[填寫表格](https://docs.google.com/forms/d/e/1FAIpQLSckrat5PryUUaX2s5W8XKe5xJj9oW9ilL3Jy_KN-K4fgZ-Sog/viewform)，讓助教得以及時發布課程通知或個別聯繫 (涉及評分事宜，請注意自己的權益)。

## Homework 1 缺失和改進

批閱指定作業 Homework1: lab0 時，發現下列缺失，在此提供給同學們參考，並期望您及早作出對應的改進。如下:

1. 作業要求已提示務必詳閱「[如何寫一個 Git Commit Message](https://blog.louie.lu/2017/03/21/)」，再來提交 commit，但顯然在 commit "Make q_free function available" [3](https://github.com/Noahnut/lab0-c/commit/b6790a027335befa6e2412aac8dd6946bffa060b), [7](https://github.com/wang0630/lab0-c/commit/aa1d4182fa55af785534acb8d2ce143c21781fc5), [8](https://github.com/f26401004/lab0-c/commit/7322e85136402fbfe8504d6591107c0b2c531239) 不符合「偉大 Git commit message的七條規則」的「用內文解釋 what 以及 why vs. how」
* 在作業要求中，q_free 的行為有具體描述，您應該解釋做出這樣改變的原因 —— 事情在改變前為什麼可行 (以及他的錯誤)，他們目前運作的狀況，以及為什麼你決定要以這個方法解決問題;
2. 程式碼不夠簡潔，例如 commit "Implement q_remove_head function" [4](https://github.com/jonaschen/lab0-c/commit/686423ac9c38268d396f6d3df424bca5ae193cf9) 中，可改寫為:

    if (!q || !q->head)
        return false;
    list_ele_t *head = q->head;
    if (sp && head->value) {
        size_t len = strlen(head->value);
        memcpy(sp, head->value, min(len, bufsize -1));
        sp[len] = '\0';
    }
    free(head->value);
    free(head);
    q->head = q->head->next;

3. 不該在 master branch 引入新增功能或錯誤修正以外的 commit，例如 commit "For testingenvirment" [5](https://github.com/z5254215560/lab0-c/commit/2527581ec9f37b927e78a805d8fb951d5ab93e65) 。而且務必確保 Git pre-commit hooks 正確安裝 (只要執行 `make` 就有)，切勿提交不能編譯執行的程式碼，例如 commit "First test" [6] (這完全不符合上述 (1) 規範)
* 當然，你的「第一次」沒什麼好描述，關鍵是如何追蹤版本發展的變遷，例如 commit "Upload the first version of lab" [8](https://github.com/f26401004/lab0-c/commit/7322e85136402fbfe8504d6591107c0b2c531239), [9](https://github.com/manphis/lab0-c/commit/da148acfecba99e28054fdee75e84790c84db61f) 根本就沒資訊量可言，還是砍掉重練吧; 不要隨便說自己 "finish" 或 "done"，只要是軟體，就能持續精進; 如果連小處都做不好，如何指望自己能挑戰兩千多萬行的 Linux 核心呢？
4. 延續上述 (1)，儘量將個別修改縮小到足以表達 functional change，例如 commit "Complete to 100/100" [7](https://github.com/wang0630/lab0-c/commit/aa1d4182fa55af785534acb8d2ce143c21781fc5) 就很不好，請拆開成若干新的 commits，足以逐步符合作業要求，並且充分解釋實作考量;
5. 縮小每個 commit 的內容，儘量完全對應到 commit message 的描述，避免提交不相關的修改，可善用 [.gitignore](https://git-scm.com/docs/gitignore)。commit "Add tail, size in struct, Implement new and free" [10](https://github.com/JulianATA/lab0-c/commit/87b06be6a9bff75d46ca2f359e1c4df25cda4fb5) 就是個不好的案例，包含了自動產生的檔案;
6. 確保每個 commit 剛好只完成一項獨立修改，避免將關聯較低的修改混合一起。例如 commit "Repair some funntion and add q_reverse" [11](https://github.com/z5254215560/lab0-c/commit/775c1b35116082fa486d86015fdaae906a526eff) 雖然標注得很多，但函式 `q_insert_head` 的修改可以不依賴巨集 `min`，而函式 `q_remove_head` 的修改主要是記憶體操作的調整，最後函式 `q_reverse` 的修改也獨立於前兩個函式

請及早改進，授課教師會持續批閱。歡迎善用[討論區](https://www.facebook.com/groups/system.software2019/)

## 成大自動駕駛車實測順利，快上車！

新聞 [台灣首座「智駕測試實驗室」開幕　成大智駕車輛動態實測完美](https://web.ncku.edu.tw/p/406-1000-190167,r2663.php?Lang=zh-tw)

2 月 25 日，科技部在台南沙崙打造首座融入亞太區複雜交通環境的封閉式測試場域「台灣智駕測試實驗室」2月25日由蔡英文總統主持開幕，成大開發的智慧駕駛車輛現場動態實測，紅燈停、綠燈行，轉彎順暢外，遇障礙物會判斷該繞行或煞停不再前進，順利展現研發成果。

成大在 2017 年開發出智慧駕駛車原型車，車體由國外引進，再由成大電機資訊學院、工學院組成的跨領域團隊，自行設計與開發自動駕駛關鍵軟體與技術，目前車輛智慧駕駛分為 5 個等級，最高為 5，成大開發的智慧車輛可以在校園域行駛，具備等級 4 的自駕能力。用到的整合與技術包含導航定位、環境感知、決策規劃與驅動控制等。此外，車輛同時也安裝通訊裝置以回報車輛狀況，並於必要時依循一定程序接受遠端遙控。 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/308651389852724/)==

## 修改 UT 的行為並指定 Valgrind 參數

Naetw 同學透過 Valgrind 檢測 lab0 作業裡頭程式碼的記憶體操作時，發現由於 Valgrind 本質上是透過虛擬機器來模擬每道 x86 指令 (Week4 會詳細探討虛擬機器原理)，進而動態追蹤程式在執行時期的行為，於是這讓原本的自動測試程式所做的假設會有所出入 —— 透過 Valgrind 執行 unit test (UT) 時，可能會遇到超時而觸發是先註冊的 signal handler。

於是 Naetw 提交了一項 pull request，藉由修改 UT 的行為並指定 Valgrind 參數，讓記憶體和執行時期檢測得以繼續。歡迎同學 Git rebase 以使用該特徵。 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/307432736641256/)==

## WasmVM 徵求撰寫測試程式碼

第一週的作業 queue(FIFO), stack(LIFO) 和 list 在 WasmVM 裡也有實作，大家可以參考參考
覺得我們的實作不好的話也可以鞭打鞭打

和作業不同處:
1. 資料都是透過 void* 指標操作，不綁定特定型別
2. 操作用的 function 用 function pointer 封裝在 struct 裡，只有 new 和 free 是 global function，這是為了利用 function pointer 在往後繼承這些 struct 時做到 override 的效果
3. 利用 CMake 的 CTest 搭配 SkyPat 做為自動檢查的架構

目前 queue 和 list 還 ** 沒有 ** 寫測試，這是個很好的機會，可以讓大家把這週學到的東西，直接投入現有的開源專案做貢獻，歡迎到 Issue 頁面上一起討論 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/308203216564208/)==

## UNIX Signal 有關的函式說明

lab0 作業是修改自 CMU CS213 課程的前導作業 (就是在正式課程展開前，就指派給學生，藉由做中學，檢視自己的 C 語言程式設計基礎)，網路上不難找到各式解答，為何我們「偷懶」採用呢？原因很簡單，因為我們不是 **只使用** 自動評分，連同其原理也要探討，這還跟 Linux 核心設計有密切關連，怎麼說呢？

cjwind 同學發現，lab0 程式開發過程中，有時會因為指標操作錯誤，由 qtest 顯示錯誤訊息:
:: Segmentation fault occurred. You dereferenced a NULL or invalid
並且繼續執行，但仔細想想，通常 segmentation fault 時，程式立刻會離開，那這個自動評分程式到底施展了什麼魔法呢？

qtest.c 的 queue_init() 用 signal() 設定 SIGSEGV 以及 SIGALRM 的 signal handler。signal handler 裡 call trigger_exception()。

setjmp(jmp_buf env) 會在 env 裡儲存呼叫此函式端的環境資訊，包含 stack pointer、instruction pointer、signal mask 以及其他 register 的內容。longjmp(jmp_buf env, int val) 使用 env 儲存的資訊來回到 call setjmp() 的地方繼續執行。

呼叫 setjmp() 時它會 return 0，而呼叫l longjmp() 後程式會以「從 setjmp() 返回處」。qtest 在實作例外處理時，就善用 sigsetjmp() 及 siglongjmp() 來保存及恢復 signal mask。 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/307900833261113/)==

鄭珮彣同學針對給定的 lab0 裡頭的自動評分程式，查閱裡頭和 UNIX Signal 有關的函式說明，他發現 exception 的設置目的為「如果程式超過 limit_time ，就會發出錯誤訊息。在處理 exception 的時候用到了 sigsetjmp ，如果 sigsetjmp的值不是 0 ，代表是從 siglongjmp 回來」

> setjmp() and sigsetjmp() return 0 if returning directly, and nonzero when returning from longjmp(3) or siglongjmp(3) using the saved context

如果 limit_time=true，代表程式是有時間限制的，如果在時間限制內沒有呼叫 exception_cancel 的話，就會觸發 trigger_exception 產生錯誤訊息。 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/308178849899978/)==

## 驗證常數時間複雜度

洪培軒 同學針對給定的 lab0 作業，根據 dudect 工具以及提出的對應論文 "Dude, is my code constant time?"，得知了一種以實驗而非理論驗證時間複雜度的方法，這對日後改進自動評分程式或者進行 timing attack 分析，相當有用。

這技巧在於利用 timing attack (精確來說是 timing leakage，因為洩漏的資訊太少不足以完成一項攻擊) 來檢測給定的實作是否時間複雜度為 O(1)。

一種 leakage detection 的方式是 fix-vs-random test。這個方式透過餵給程式固定以及隨機的資料，再比較執行時間的差異。dudect 使用的方法便是這種 fix-vs-random test。在得到執行時間後，利用 t-test 檢查兩種測試資料是否差異。

洪同學目前嘗試取用 dudect 中計算 t-test 的部份，修改後放到 qtest 中。執行 qtest -t 可以測試 q_insert_tail 和 q_size 是否可能非常數時間複雜度。 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/308171676567362/)==

## 改善 buffer overflow 偵測機制

cjwind 同學發現，lab0 內建的自動評分程式對於 buffer overflow 的檢查不充分，於是他著手改進，請見 pull request ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/308139969903866/)==

## 掌握 Linux 核心往往意味著可改善應用程式

可能有些同學是抱持「想變強」而來到這門課，但對於「掌握 Linux 核心」這件事有疑慮，畢竟許多學生從電機資訊學院畢業後，很多是接觸作業核心外圍，就算碰 Linux 核心，可能還是編修前人留下的裝置驅動程式 (如 Mediatek, Realtek, Novatek 工程師的職場日常)。但「掌握 Linux 核心」往往意味著你也可改善應用程式，解決他人難以攻克的障礙，這話怎說？

在老字號的開放原始碼資料庫系統 PostgreSQL，有位工程師 Craig Ringer 於 2018 年 3 月時提交一個嚴重問題：

PostgreSQL 資料庫伺服器服務由一組程式組成，其中呼叫 fsync 系統呼叫 (作用: 要求所有變更的資料更新到硬碟或者類似的儲存裝置中) 是由一個名為 Checkpointer 的程式執行，後者確保儲存空間上資料的一致性，以便在錯誤發生時回復。不過，Checkpointer 不會一直開啟所有的相關檔案，通常只會在呼叫 fsync() 前打開檔案，也就是說， 當 fsync 被呼叫，PostgreSQL會假設所有資料都成功寫入到儲存裝置中，但事實並非總是如此，這樣就造成資料的遺失 (!)

當由硬體錯誤引發的 buffered I/O 寫入失效，檔案系統會作出不同的回應，而這個動作通常包括丟棄受影響的 pages，並將 pages 的資料標示為清空，這意味著，之前寫入資料的區塊可能回傳非預期的內容。

PostgreSQL 開發者對於 Linux 核心後續的處理感到不滿，PostgreSQL 開發者認為，無法寫入的 pages 應該保存在主記憶體內，將狀態標記為 Dirty 並稍後再嘗試，而且相關的 file descriptor 狀態也應該設為永久錯誤，如此，才不會讓 PostgreSQL 誤判。

紛紛擾擾近一年，最近 PostgreSQL 開發者終於推出修正 fsync 問題的錯誤。

PostgreSQL 與作業系統底層的協作問題，長期以來 (將近 20 年) 十分困擾 PostgreSQL 的開發團隊。過去曾向 Linux 核心開發團隊發聲希望處理，但獲得的結果是：

「Linux 核心不會為了單一軟體的需求，提供僅限於一處卻會影響其他軟體的解決方案」

最終，PostgreSQL 開發團隊只好自己動手。 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/307955926588937/)==

## 撰寫「有品味」的程式碼

本次 lab0 作業引入自動評分系統，同學們可逐步檢視自己投入的狀況，進而得知即時回饋 (台灣的高等教育很少這樣做，畢竟很容易就讓一堆學生因此退學)。不過可不要輕易說「完成」，工程挑戰是持續的，我們都該思考如何改善。

Naetw 同學在實作 q_insert_tail 函式時，面對下方程式碼:

if (q->size == 0) { q->head = new_node; }
else { q->tail->next = new_node; }
q->tail = new_node;

他想到 Linus Torvalds 曾在 TED 演說中提及「有品味」的程式碼，於是他將 tail 改成 pointer to pointer to list_ele_t，並在 queue 的建構函式中將 &q->head 指派過去。於是上方程式碼可改寫為下列等價、簡潔，又不失可讀性的實作:

*(q->tail) = new_node;
q->tail = &new_node->next;

很美吧！ ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/307830993268097/)==

## 全世界沒人敢忽略以色列

引述[氣象達人彭啟明](https://www.facebook.com/weatherrisk/)博士的評語：
> 「很難想像這個比台灣領土還要小的國家，比台灣更沒有資源，卻蘊含很多實力，緊密團結的在努力求生存，壯大自己，全世界沒人敢忽略他，如今要登月了!」

SpaceX 獵鷹 9 號火箭 (Falcon 9) 於台灣時間 2 月 22 日上午 9 點 45 分從佛羅里達州發射升空，執行以色列首次登陸月球任務。

以色列此次的無人登陸器名為「創世紀號」(Beresheet)，計劃在 4 月 4 日進入月球軌道，並於 4 月 11 日嘗試在月球北半球軟著陸，對月球磁場進行 2 到 3 天的考察。在這之前，創世紀號將完成 650 萬公里的軌道之旅，而地球直達月球距離約為 38 萬 6242 公里。

創世紀號搭載一台廣角高解析度相機，預計拍攝落月影片和月球表面靜止畫面。 創世紀號體積如洗碗機，由以色列非營利機構 SpaceIL 研發，耗資 1 億美元。如果創世紀號成功登陸月球，以色列將成為繼俄羅斯、美國、中國之後，第 4 個有探測器在月球表面著陸的國家。 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/307786723272524/)==

## 歡迎來到 21 世紀

課堂中授課教師常說「歡迎來到 21 世紀」，這個世紀從 2001 年 1 月 1 日星期一開始，不用 20 年就和人類認知到的典型世界有了巨大差異。Interbrand 就公司財務狀況、品牌形象和作為，和品牌延展度 [1] 等因素，列出 2010 年以來，世界前 15 大品牌的消長。

今日我們熟知的 Apple, Google, Amazon, Microsoft, Samsung, Facebook 等品牌，在十年內，和許多老字號的龍頭產業緊密的交叉，進而大幅拋開後者。

猶如巨人般的公司企業是如此，我們作為工程從業人員當然也該「誠實面對自己」。 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/307810206603509/)==

## 新增 strdup 的 hook

洪培軒同學針對給定的 lab0 作業時，他留意到題目要求 q_insert_tail 及 q_size 實作的時間複雜度不該是 𝑂(𝑛)，而是指定的 𝑂(1)

他一開始在實做 insert 時，用了 strdup() 函式，但自動評分程式遇到 q_free 時，一直顯示 "ERROR: Attempted to free unallocated block"，他繼續追下去，搭配 gdb 追蹤程式運作，有以下發現:

1. lab0 裡頭重新定義 free()，透過巨集對應到 test_free (實作於 harness.c 裡頭)，這樣的話程式碼就可以先一步檢查避免程式 crash;

2. 同上，malloc() 也被替換為 test_malloc()，因此，在實作的過程中，我們沒辦法使用 strdup 的原因是需要 test_malloc 進行必要處理 (例如設定 magic_header)，如果沒有做那些特殊處理，在 test_free() 時會警告這段記憶體空間沒有被配置到，即使稍早已經實際分配空間給了。 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/306954966689033/)==

洪同學進行指定的 lab0 作業時，他發現原有的自動評分程式已經 hook 了 malloc() 和 free()，但由於沒 hook 到 strdup()，於是自動評分程式會有不匹配的警告訊息。

洪同學著手提交 pull request 來修正，歡迎透過 Git rebase 存取這修正。 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/307552413295955/)==

## 考慮多樣的異質多核架構

相較於坊間標榜 Linux 裝置驅動程式開發的課程，本學期「Linux 核心設計」探究在關鍵的核心設計機制和 scalability，後者不是僅有降低 lock contention，實質要考慮多樣的異質多核架構。

Arm 近期宣布野心勃勃的 Neoverse平台，跨越上至雲端數據中心、下至終端運算需求的處理器獨立系列解決方案。今年推出 Ares IP 平台、2020 年以 7nm+ 製程推出 Zeus 平台，2021 年以接近 5nm 製程推出 Poseidon 平台。與此相匹配的訊息是，AWS 旗下子公司 Annapurna Labs 藉由 Arm Neoverse 的 Cosmos 平台，開發出自家AWS Gravition 處理器 (對！你沒看錯，雲端公司跳下來開發專屬處理器，已經是常態了)，並嘗試導入 AWS EC2 A1，後者適合應用於橫向擴展的工作負載，例如 container micro-service、網路伺服器應用、暫存主機、開發環境測試。

Arm Neoverse E1 的關鍵特徵:
* Up to 128 cores in a single coherent system
* 64kB L1 instruction and data cache
* Up to 1MB large private L2 cache
* Up to 128MB of shared system level cache through a low-latency
* direct-connect interface to the CMN-600 mesh
* Microarchitecture for large footprint, branch-heavy workloads
* I-cache coherency to enable a broader range of server workloads
* Double the vector and crypto compute bandwidth over
previous generation
* No-compromise, full-frequency, sustainable compute efficiency
managed at runtime
* Server-class virtualization, RAS and code profiling

藉由 Neoverse E1，比現有 Arm Cortex-A72 在下述應用情境帶來顯著加速:

Arm found Neoverse N1 to be significantly faster than Arm Cortex A72 in typical server workloads:
* 2.5x NGINX performance
* 1.7x OpenJDK
* 2.5x MemcacheD
1.6x MySQL
* 6x DeepBench
* Up to 2x DPDK
* 1.6x OvS ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/307093283341868/)==

## 自動測試程式運作機制

Fernando Lin 同學探討自動測試程式，以下標注重點:
1. 在 harness.h 標頭檔對 malloc/free 的包裝，以便實作出記憶體使用追蹤機制;
2. 所有因呼叫 test_malloc 得來的記憶體，實際上是紀錄在一個名為 allocated 的一個 doubly-linked list 中。該 linked list 結點的結構為 block_ele_t，定義在 harness.c 中

    typedef struct BELE {
    ...
    unsigned char payload[0];
    } block_ele_t;

在這個結構體中，最後一個成員 payload[0] 是實際給呼叫者使用的記憶體開頭。該成員使用到的 GCC 中 Array of Length Zero 特徵。該功能簡便處在於：若結構體中的最後一個成員是大小為 0 的陣列，那麼可以透過 malloc(sizeof(block_ele_t) + 希望 payload 後面接著多少記憶體) 來達成「最後一個成員大小可以任意指定」的效果（另外一個好處是 malloc 跟 free 一次就可以完成，不用替 payload 開頭的記憶體再 malloc 一次）。
3. 位於記憶體之前的 magic number，實際上就是結構體中 magic_header 這個成員，其值會在 test_malloc 中被指定為 MAGICHEADER，也就是 0xdeadbeef ; 在記憶體尾端的 size_t 整數，數值必定為 MAGICFOOTER，也就是 0xbeefdead;
4. 因為要回傳給使用者的指標實際上是 payload 的位置，因在程式中另外有 find_footer 跟 find_header 這兩個函式作為輔助。前這傳入 block_ele_t *，回傳位於 payload 尾端 magic number 的位址;
5. 若順利找到該記憶體所屬的節點，接著檢驗尾端的 magic number 是否仍為 MAGICFOOTER，作為記憶體有沒有被越界存取等狀況的判斷依據。若比對結果發現不合，也會發出該區段記憶體損壞的警告。若確認結果無誤，則將記憶體區段前後的 magic number 都設成 MAGICFREE。並且將記憶體內容都用 FHILLCHAR 填充。最後移出 allocated 這個 doubly-linked list。

但自動測試程式不只做了記憶體追蹤，還實作了超時及 Segmentattion fault 的檢測 (程式都要當掉了，怎麼還能追蹤呢？！)，這怎麼做呢？就涉及到 UNIX Signal 的運用，當某個 signal handler 被觸發時，該訊號會在執行 signal handler 時會被遮罩住，並在 signal handler 回傳時恢復; 而在裡面使用 longjmp 時，解除訊號遮照的行為有可能不會發生(是否解除則依照實作決定)。為了保證在非區域跳躍後能夠恢復，所以規範了另一個能在 signal handler 中呼叫的 sigsetjmp 跟 siglongjmp; ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/307440269973836/)==

## 八皇后問題的非遞迴解法

陳奕熹提出的[解法](https://hackmd.io/s/S1DHQ3KrE)

具體實做的觀念其實類似遞迴，一樣都是要找「不能下的位置」，但是因為走到死路時需要手動回復棋譜狀態，因此不像小考中的作法紀錄 major_conflict/ minor_conflict，我的非遞迴解法以紀錄整份棋譜目前下子狀態為主，需要下子的時候再根據棋譜動態算出 conflict 的位置。

很多人對遞迴存有偏見，特別在台灣以「培養考試作為主要技能」的教育環境，有些人就會認定「遞迴效率就是差，不建議用」，但遞迴的思維其實是「遞迴讓你直覺地表示特定模式」。一如 陳奕熹 同學在共筆提及，遞迴程式邏輯是用二進位記成 current_pos = 0b10000000，以最上方的格子作為 Most Significant Bit (MSB)，當要下第二個棋子時，我們需要知道「什麼地方是可以下的」，透過我們剛剛下的第一個棋子，我們可以推出下一個上下行「什麼地方是不行的」，這樣就能實作出程式碼。

非遞迴的概念與遞迴概念相似，都要考慮到「上下直行哪邊可以下」跟「什麼時候找到全部解」這兩件事。不過非遞迴需要額外考慮「怎麼回朔回上個狀態」，因為遞迴在函式呼叫結束後會自動根據 call stack 改變執行流程，像是遮罩這種變數因為每層遞迴會維護一個相對獨立不會被污染，但是在非遞迴的狀態下，我們必須手動維護這樣的變數狀態關係。換言之，要一開始就實作出 iterative 解法，不容易確保正確，程式開發本來就是演化的過程，只是多數人通常看到最終的表現。

像這樣子把 row 的資料從一維陣列降維到一個整數的方法
以二進位去解讀的辦法只限「一個格子只能有兩種狀態」

在這個例子就是「有子/沒子」「能下/不能下」類似 bool 的狀態，因為我們不會用到 int 除了 0/1 以外的值我們才能「壓縮」成新的表示法

如果今天的狀態突然變多，像是變成「有黑子/ 有白子/沒子」更多狀態，以三種狀態來說代表說需要用兩 bit 才能表示，那麼整體運算又需要重新設計 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/307277226656807/)==

隨堂測驗之所以拿經典的「八皇后問題」，是因為稍早我看到這份東京藝大學生小野澤峻的畢業作品，於是把原本課程進度的 bit-wise operation 結合進去。

在小野澤峻的作品 Movement Act 中，將 16 個球體放在星型平台上，其中球體會不斷走動，但特別的是它們都剛剛好不會撞上，各自在路上行走，成為一個流暢的美麗畫面。背後的原理，就跟「八皇后問題」相仿，並更有藝術感。

我們學工程的人，或許無法一開始就思忖到這樣的創作，但該用自身的訓練，逐步導入軟硬體的調整，像是透過 bit-wise operation 和後續課程會提及的最佳化技巧，一點一滴地改善整個系統。 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/306536500064213/)==

## 不要說千萬行看不懂，10 行也可以嚇死你

另一個連 20 行不到的原始程式碼也可以把你嚇到吃手手的案例：取自 PuTTY，是個支援 Telnet, SSH, rlogin、純 TCP 以及序列通訊的軟體，主體程式碼大約 10 行，不太容易一眼就看出其作用。

這到底是什麼？功能是 Run-length encoding (RLE) 的解碼程式。RLE 可以很簡單，比方說看到輸入是 "AAABBBBCCCCC"，就編碼為 "A3B4C5"，但這裡的程式碼更複雜，透過 coroutine 實作出交錯執行的程式碼。

之後我們談及 process & thread，會探討到 coroutine，屆時同學們應該就可理解。在這之前，請持續精進自己的程式設計基礎。 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/307194219998441/)==

## 多大的空間才能表示 IPv4 地址?

課堂提及需要多大的空間才能表示 IPv4 地址呢？也許會有人想，一個合法的 IP 地址長得像是 "140.116.246.180"，加上最後的 null terminator 後，需要宣告 char ipaddr[16]，不過實際上這只是浪費空間。

熟悉 bit-wise operation 的同學不難發現，只需要 4 bytes 即可表示 IPv4 地址。你可以試著在終端機內輸入 ping 167772162 指令，然後 ping 會很「聰明」地轉換為 10.0.0.2 這個 IP 地址，但為什麼呢？因為 IP 地址本身就是一個數字。

要將前述的 4 bytes 轉成人類可讀的形式，可用以下程式碼:

void ipaddr_to_string(in_addr_t ip, char * buf) {
    unsigned char bytes[4];
    bytes[0] = ip & 0xFF;
    bytes[1] = (ip >> 8) & 0xFF;
    bytes[2] = (ip >> 16) & 0xFF;
    bytes[3] = (ip >> 24) & 0xFF;
    sprintf(buf, "%d.%d.%d.%d", bytes[3], bytes[2], bytes[1], bytes[0]);
}

==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/307189559998907/)==

## 編譯器技術對於核心開發的重要性

據 GitStats 顯示，截至 2018 年 12 月 31 日，Linux 核心原始程式碼已經超越 2 千 6 百萬行 (!)，而倘若你缺乏足夠穩固的根基，不要說 2 千萬行，可能連 20 行 C 程式都搞不懂 (看我們的隨堂測驗就知道...)。

那該怎麼辦呢？總不能永遠都在「舉燭」吧？上週一位華為的工程師透過 Kernel Address Sanitizer (KASAN)，找出一個潛藏在 Linux 核心多年的漏洞，藉由 use-after-free，網路子系統的 sockfs 可能會讓有惡意的程式碼得以被執行。

這樣的缺失很難透過眾人的肉眼在早期發現，從而一路存在自 Linux 2.6 早期版本到 4.20 版 (!)，換言之，這案例說明為何我們要熟悉編譯器技術，不僅要知道最佳化操作的原理和輸出，還要善用 KSAN 一類的 sanitizer，讓開發者精準地找出問題。 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/307165490001314/)==

## 沒有基礎，修這門課程會不會很累/跟不上呢？

開學前後，授課教師總是會收到頗多類似這樣的信件：
「我是醫工/數學/物理/水利/材料/航太/資源系的學生，沒有基礎，修這門課程會不會很累/跟不上呢？」

那又如何？好歹你們都修過微積分和基本數理訓練，之前我們課程還有成大政治系的學生來選課呢！只是起點不一樣，重點是你能否全力以赴地追求自我成就。

Gao Zhiyuan 同學來自中國華中地區，到台灣成功大學註冊為政治系學生，本著對資訊科技的熱情，兩年前他選修我開的課程 (自從我發現台文系的學生也跑來旁聽後，就不再大驚小怪)，去年他去北京成為 SUSE Linux 的實習生，接著即將到韓國首爾大學攻讀電腦科學，挑戰作業系統相關的研究。

王爾德說過：
> 「世界上只有一件事比被人議論還要糟糕，那就是不被議論。」

千萬不要怕被議論而不放手做，起步慢又如何？勇敢往前邁進就好！ ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/307021426682387/)==

## 親身實踐和體驗

課程介紹提過親身實踐和體驗，對於理解像 Linux 核心這麼巨大的軟體的重要，比方說透過 Google 搜尋，我們可能會看到有人提及 Linux 核心的 context switch 成本約 1 microseconds，但也有不同的數字，到底該相信哪個說法呢？其實，就該設計實驗，並且著手在特定的硬體及軟體組態下進行測量 (稍後課程就有此要求)。

當然，你也許會質疑：「我們重複他人已經做過的實驗，到底有何意義？」回答此問題前，先來看諾貝爾物理學獎得主李政道博士，在美國受費米指導時期 (1946 年到 1950 年) 發生的一則軼事：費米問李政道太陽中心溫度為何，後者一開始說約一千萬度左右，費米追問是否核算過，李政道以兩個關聯方程來回答，大致呼應一開始的數據，不過費米表示「你不能依靠别人的計算结果，你必須自己核算」，並建議透過計算尺查證，之後師生就一同打造木製計算尺，從而計算出符合推論的數據。

試想，在費米指導李政道之前，費米在第二次世界大戰期間參與曼哈頓計劃。費米領導他的團隊設計並建造了芝加哥 1 號堆。這個反應爐 1942 年 12 月 2 日進行臨界試驗，完成了首次人工自持續連鎖反應，奠定日後位於洛斯阿拉莫斯國家實驗室、利用熱核反應的「超級核彈」的成功。1945 年 7 月 16 日，費米參與了三位一體核試，並利用自己的方法估算了爆炸當量。之後的故事大家都知道，原子彈永久地改變人類的歷史。

已是物理泰斗的費米，面對一位從中國上海留學的學生，竟不忘以身教提醒李政道，面對統計物理的相變以及凝聚體物理學的極化子的研究之前，追求真善美境界並親身體驗的態度，才是一切的根本。 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/307012533349943/)==

## 使用 valgrind 測試記憶體的問題

Naetw 在進行指定的 lab0 作業時，除了透過原本的 unit test 外，試著跑了 valgrind 來檢查有沒有記憶體相關問題，分析 qtest 單次執行，測試第 14 筆關於效能的分析時，遇到以下問題:

$ ./qtest -v 1 -f ./traces/trace-14-perf.cmd
==18229==
# Test performance of size
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)

但是單純執行指令時不會發生問題：

$ ./qtest -v 1 -f ./traces/trace-14-perf.cmd
# Test performance of size

他推論這是因為 valgrind 分析時會插入自己的指令來獲得資料，因此超過了 qtest 本身預期的時間限制。檢閱原始程式碼，在 qtest.c:493 指定了 SIGALRM，並在 harness.c:53 設定時間限制，將其數值提高便能正常使用 valgrind 測試記憶體的問題。 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/306943716690158/)==

## 你不知道的 AAAAAAAA

最近在 批踢踢實業坊(Ptt.cc) 八卦板關於 "AAAAAAAA" 的討論頗多 (不解釋)，從資訊科技的角度來說，0xAAAAAAAA 是個常見的 bit mask，給定一個 32-bit unsigned integer "x"，那麼:

// Get all even bits of x 
unsigned int even_bits = x & 0xAAAAAAAA;

同理:

// Get all odd bits of x 
unsigned int odd_bits = x & 0x55555555;

若要將 x 裡所有偶數位元和奇數位元互換，只要額外做

(even_bits >>= 1) | (odd_bits <<= 1)

是不是好神奇 AAAAAAAA!

另外，依據 RFC3596，IPv6 位址在域名系統中為執行正向解析表示為 AAAA 記錄 (即所謂 4A 記錄)。IPv4 表示為 A 記錄 (A record)。 ==[...延伸閱讀](https://www.facebook.com/groups/system.software2019/permalink/306566723394524/)==