版本 e9ac4e6b998ad4b3d89ba61bc50691b707eb83dd
User/IepIweidieng
IepIweidieng (葉威呈)
國立成功大學醫學檢驗生物技術學系 110 級(2017–2018)- 國立成功大學資訊工程學系 110 級 (2018–)
- GitHub: https://github.com/IepIweidieng
近期專案
- bbslua.lua—在原生 LuaJIT 上執行 BBS-Lua 的平臺 (Lua): https://github.com/IepIweidieng/bbslua.lua
- IID-Heap-Style—在 HackMD 上製作的部落格網頁版面樣式 (CSS3): https://hackmd.io/@IID/IID-Heap
Linux 核心設計 2020q1 自我評量
指派作業
隨堂測驗分析
- quiz6: HackMD
期末專題
認知回顧
對 GNU Toolchain 的掌握度:
是否知曉
gcc
編譯和連結的流程?- Preprocessing (
cpp
/gcc -E
), compilation (gcc -S
), assembling (gcc -c
), linking (ld
/gcc
).
是否使用過
gdb
來追蹤程式?- 是。
- Preprocessing (
使用
perf
工具:是否已透過
perf
來分析程式執行時期的行為?知曉透過
perf
來分析 cache miss 及執行的指令數量?計算機編碼:
為何現代的電腦架構採用 two’s complement 呢?
能否舉出 two’s complement 和 bitwise 操作搭配的案例?
Linux 核心原始程式碼中有哪些 bitwise 操作令你印象深刻?
Linked list:
如何對 singly-linked list 進行排序?
如何評估 linked list 的 cache locality 呢?
如何改善 linked list 的 locality 表現?(如 unrolled linked list 及 splist)
Linux 核心原始程式碼的 linked list 有何特別之處?
C 語言:
是否翻閱過 C99/C11 規格書?
- 翻閱過內容相當於正式版的草稿版本。
正式版本有版權,要使用貨幣購買。
現實中有不少案例是因開發者對於 C 語言規格的掌握不足,致使資訊安全議題,能否舉例說明?
去年初,我遇到了在夢之大地 BBS 閱讀某些看板時會斷線的問題。
這是存在已久的問題,久遠得影響到了其它 MapleBBS 3 系列的 BBS 系統。而 2018 年時已有人使用gdb
研究過這個問題:https://gist.github.com/holishing/a4ee1582947d0adea7e29c8ba01c6ecc。
結論是閱讀紀錄因為不明原因而壞了。最後我使用 `valgrind` 找到了問題的來源。\
因為處理閱讀紀錄的程式,對資料中的重疊的記憶體範圍使用了
memcpy
,造成了 undefined behavior。而 glibc 2.13 (2010 年釋出) 時對memcpy
進行了優化,會導致複製來源與目的重疊時可能出現複製錯誤,所以閱讀紀錄才會壞。
在重疊的記憶體範圍間複製資料時,應該使用memmove
,不該使用memcpy
。
當時發現的問題點:https://github.com/ccns/dreambbs/commit/bc67fbb2200d2071aa78d5c6ffc6576b34fe12b5
而且不只一處:https://github.com/ccns/dreambbs/commit/2f649415299378805bd3ab4931ec07797efc72ca
除了閱讀紀錄以外,還發現了另外 5 處相同的問題點:https://github.com/ccns/dreambbs/commit/e7e99d4161a58658c06e1c2797ba895da48a7366
Alignment 對於程式正確性和效率的影響為何?
在 Linux 核心可見到的
__attribute__((packed))
作用為何?- 各個資料欄位間,無視 alignment 而只依照 size 排列,不留空隙。
bit field 的作用和應用為何?
指標的指標 (a pointer to a pointer) 的使用場景為何?
- 需要在某函式中修改給定指標的值時。
函式呼叫對應的 ABI (application binary interface) 有何考量?
- 函式庫的不同的次要版本間,應維持參數大小及順序的一致。
能否舉例說明 Linux 核心的原始程式碼裡頭用到遞迴函式呼叫的案例?
舉例說明 Linux 核心對於 preprocessor 的使用案例?
能否舉例說明善用
goto
達到更簡潔且正確釋放資源的程式案例?C 語言為何存在 undefined behavior?
- C 語言設計時,電腦硬體差異大,如要求各種操作都要有一致結果,則程式或編譯器無法在某些硬體上有效率地運行。
undefined behavior 的存在對於編譯器最佳化的效益為何?
- 編譯器可以不必理會具有 undefined behavior 的程式的輸出。
C 編譯器和連結器的互動為何?
- 翻閱過內容相當於正式版的草稿版本。
浮點數運算:
能否舉出因為不正確進行浮點數運算,釀造的軟體缺失案例?
Linux 核心內部是否可使用浮點數運算?如果不能,替代方案為何?
Process:
Linux 核心程式碼的
task_struct
結構有哪些欄位令你印象深刻?Linux 核心中 process 和 thread 透過哪些系統呼叫建立?
process 和 thread 對應到
task_struct
結構的關聯為何?fork
系統呼叫所建立的 child process,會在什麼時間點進行排程?Scheduler:
Linux 核心的 \(O(1)\) scheduler 是指哪些操作的時間複雜度為 \(O(1)\) 呢?
排程器和 scalability 的關聯為何?
- Throughput
從單核到多核處理器,scheduler 有哪些考慮議題?
- 不同核心的工作分配、race condition……
Linux Kernel Module (LKM):
能否解釋
insmod
的運作流程?lsmod
輸出結果中的 “Used by” 代表什麼意思?lsmod
的 reference count 如何實作?你開發過哪些 LKM 呢?請說明令你印象最深刻的 LKM 開發經驗
Concurrency:
Linux: 核心內部有哪些同步機制?
- Spinlock、semaphore、mutex、……。
semaphore 和 mutex 的差異為何?
- 概念上,semaphore 可有多狀態,而 mutex 僅有二狀態。實作上,Semaphore 無主,mutex 屬於 thread,……
RCU 的使用時機為何?
- Readers 多,writers 少,且沒有嚴格要求同時進行的 read 之間的資料一致性。
Thread:
User-level threads 的實作考量有哪些?
Linux 的 NPTL 屬於何種 threading model 呢?
clone
系統呼叫能建立 process 和 thread 嗎?若是,兩者有何區隔?thread 和 SMP 之間有何關聯?
thread 和 process 排程的考量點為何?
系統呼叫:
能否解釋
sendfile
,splice
,epoll
等系統呼叫對於高效率 web 伺服器的作用?在 Linux 核心中,“Everything is a file descriptor.” 如何解讀?
- 所有東西都有檔案介面,可用類似檔案的形式互動。
epoll
的工作原理為何?記憶體管理:
Linux 核心中
kmalloc
和slab
配置的記憶體有何特性?從
slab
到slub
有何考量點?mmap
的運作原理為何?為何
packet_mmap
能達到 zero-copy 呢?
自我評量 (0–10 級分)
五級分。
莫名地,這個學期就這麼忽悠地過了,我卻沒能做什麼東西。
不過我仔細閱讀並修正了教材的錯字,也有所收穫。
而最近課程討論區上對於量子電腦的討論,也促使我進行了相關知識的研究。累積了一些論述,之後可以寫個相關的共同筆記。