# Linux 核心實作上課筆記與疑惑
## 第二週
### [C 語言: 數值系統](https://hackmd.io/@sysprog/c-numerics)
**運用 bit-wise operator**
- `x & (x - 1) == 0` 在 C 語言中表示：
- power of two
e.g. $4_{10} = 1\ 0\ 0_2$ , $3_{10} = 0\ 1\ 1_2$ , $1\ 0\ 0_2$ & $0\ 1\ 1_2 = 0\ 0\ 0_2$
- signed v.s. unsigned
- 將字元轉成小寫: 免除使用分支
- ' '(空格)的 [ASCII碼](https://zh.wikipedia.org/zh-tw/ASCII) 為 $32_{10} = 1\ 0\ 0\ 0\ 0\ 0_2$
- A = $0\ 1\ 0\ 0\ 0\ 0\ 0\ 1_2$ , a = $0\ 1\ 1\ 0\ 0\ 0\ 0\ 1_2$
- 英文大寫和小寫的 ASCII 剛好差 32 ，因此利用`\ ' '` 即可讓代表 32 的位元設為 1 ，達到大寫轉小寫的作用。
- 同理，也可利用 `& '_'` （ _ = $0\ 1\ 0\ 1\ 1\ 1\ 1\ 1\ 1_2$）, `^ ' '` 來分別達到將字元轉為大寫和大小寫互轉
```c
('a' | ' ') // 得到 'a'
('A' | ' ') // 得到 'a'
```
- Count Leading Zero 疑問
::: info
不明白為何 lookup table 的內容是這樣設計，也不了解為何是乘上0x07C4ACDD 並向右位移 27 位元，想請老師幫忙解惑
:::
``` c
const int tab32[32] = {
0, 9, 1, 10, 13, 21, 2, 29,
11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7,
19, 27, 23, 6, 26, 5, 4, 31
};
int log2_32 (uint32_t value)
{
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
return tab32[(uint32_t)(value*0x07C4ACDD) >> 27];
}
```
### [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)
**常見雜湊函數作法**：
1. Division method
2. Mid-square
3. Folding addition
4. Multiplication Method
:::warning
TODO
想比照比較同頁面下方 "golden ratio 與非 golden ratio" 的實驗方法，觀察這四值種 hash function 在輸入為亂數時發生碰撞的情形
:::
---
## 第三週
### [你所不知道的 C 語言：遞迴呼叫篇](https://hackmd.io/@sysprog/c-recursion#Fibonacci-sequence)
- C 語言命名慣例
- 大寫結構體: 和作業系統、所屬環境有關
- 小寫結構體: 在文件中有定義的話就可以將它的成員取出來做特定操作
### [你所不知道的 C 語言：技巧篇](https://hackmd.io/@sysprog/c-trick)
- C 語言中會將程式模組化，將程式分為 .h 檔 (header file) 和 .c 檔
- 編譯器一次只編譯一個檔案，每個檔案都是一個編譯單元，會有個別對應的 scope ，若 function 前面加上 `static` 表示該 function 的有效範圍僅在同一個檔案內，避免到時候 linking 的時候有多個檔案擁有相同的函式名稱，造成重複定義。
## 第七週
### [Linux 核心設計: 不僅是個執行單元的 Process](https://hackmd.io/@sysprog/linux-process)
Threads
- 建立 threads 的成本比建立 process 更低
- multitasking
- 切換成本較 process 低
- Linux Thread State Transition
### [Linux 核心設計: 淺談同步機制](https://hackmd.io/@sysprog/linux-sync)
- mutex 和 semophore 的比較
- mutex 確保數個 process 在一個時間點上，只能有一個 process 存取單項資源
- semaphore 讓數個 producer 與數個 consumer 在計數器的基礎上進行合作
| | mutex | semophore |
| -------- | -------- | -------- |
| 出現時間 | 較晚 (2.6.16版) | 較早
| 解鎖 | 只能由上鎖的 thread 解鎖 | 可由原本的 thread 或是另外一個 thread 解開 |
| 可進入 critical section 之 thread 數量 | 1個 | 多個
| 應用場景 | 常使用在 critical section 只能有一個 thread 進入，而且要避免 priority inversion 的時候 | 常用在同步兩個 thread 或功能上面，因為 Semaphore 實際上使用的是 signal 的 up 與 down，讓 Semaphore 可以變成是一種 notification 的作用，例如 A thread 執行到某個地方時 B thread 才能繼續下去
| priority inversion | 無 | 有
### [並行和多執行緒程式設計-POSIX Thread](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fposix-threads)
- thread-local storage (tls): 給 thread 一個專屬的空間 (不和其他 thread 共享)
- 例如可記錄 errno (error number)
- 硬體協助
- 無硬體協助
- Native POSIX Thread Library (NPTL): 一對一
- semophore
- sysv semaphore
- posix semaphore (現在系統, sem_ 開頭)
- 用 semaphore 控制總量、 mutex 控制 mutual exclusion
- 利用 Atomic Compare and Exchange 指令來實作 semaphore 和 mutex
- atomic functions 分為 strong 和 weak : strong guarantee the success or failure while weak may fail
- [condition variables 範例](https://github.com/angrave/SystemProgramming/wiki/Synchronization%2C-Part-5%3A-Condition-Variables)
- Threads sleeping inside a condition variable are woken up by calling `pthread_cond_broadcast` (wake up all) or `pthread_cond_signal` (wake up one)
- **Condition variables are always used with a mutex lock.**
-
Before calling wait, the mutex lock must be locked and wait must be wrapped with a loop.
Tips: 如果 `N` 為二的冪， `i % N` 可以改成 `(i++) & (N-1)` bitwise 操作
### [2024q1 第 9 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz9)
#### 測驗 1
如何確保 fork 程式有東西可以合併?
mmap: 作業系統中讓多個行程存取同一個記憶體空間
```c
int main(int argc, char **argv)
{
rand_context_t r;
rand_init(&r, (uintptr_t) &main ^ getpid());
/* shared by forked processes */
int *arr = mmap(NULL, N_ITEMS * sizeof(int), PROT_READ | PROT_WRITE,
MAP_SHARED | MAP_ANONYMOUS, 0, 0);
for (int i = 0; i < N_ITEMS; ++i)
arr[i] = iabs((int) rand_next(&r));
merge_sort(arr, N_ITEMS);
for (int i = 1; i < N_ITEMS; ++i) {
if (arr[i] < arr[i - 1]) {
fprintf(stderr, "Ascending order is expected.\n");
exit(1);
}
}
printf("OK!\n");
return 0;
}
```
- sudo sysctl -w kernel.sched_child_runs_first=1，以便要求 Linux 排程器 (CFS) 讓 child process 優先於 parent process 執行
- 遞迴時呼叫 fork 會更耗費成本
- 如何改進此程式?
- 避免使用遞迴，降低 fork 成本
- 預先 fork (pre-forking)
- copy_form_user 會有 cpu mode switch
#### 測驗 2
- ioctl : 和核心內裝置溝通
- if page 太大， page fault 的成本會太大 (可參考 CS:APP ch9)
### 第十二周 5/9
多核處理器
- 手機開機只先開一核作為管理者
- WFI、WFE指令
- work load 計算，會有 decay，因為最重要的資訊是當下資訊，越久之前的資料重要性越低
- CPU Isolation: 開機時指定某一核不主動參與排程，除非使用 set affinity 將任務指定給該核
Pthread barrier: 讓快的 thread 等慢的 thread
time stamp counter (TSC): 可接露 CPU 週期數，只要 CPU 開著，周期數必為單調遞增
### 第 13 週
增加取餘數效率的小技巧:
如果是對 2 的冪**取餘數**， **等於對 2 的冪 - 1 做 &**
- 如: X % 16 = X & (16 - 1)
- 所以可以將 ring buffer 的大小設定為 2 的冪
[zero-copy](https://hackmd.io/@sysprog/linux2020-zerocopy)
[alignof c11](https://en.cppreference.com/w/c/language/_Alignof)
page alignment: 因為 page 是記憶體操作的最小單元，必須保證有 align，才能避免非預期結果
FUTEX_WAIT
FUTEX_WAKE
第十六周
在現代查表可能比 CPU 運算還慢約 50 倍，因此要避免查表
要學會懷疑、推理並做實驗驗證
- [展頻](https://zh.wikipedia.org/zh-tw/%E6%89%A9%E9%A2%91)
- [調變 (modulation)](https://zh.wikipedia.org/zh-tw/%E8%AA%BF%E8%AE%8A)
- [OFDM](https://zh.wikipedia.org/zh-tw/%E6%AD%A3%E4%BA%A4%E9%A0%BB%E5%88%86%E5%A4%8D%E7%94%A8)
面試要展現對公司的利益!
為何需要 boot loader?
因為 Linux kernel 太大，需要先初始化 DRAM。所以需要在 ROM 中初始化 SRAM，之後才能初始化 DRAM
> [millaker](https://hackmd.io/@sysprog/HyjiP43N0)
[SD/MMC](https://wiki.csie.ncku.edu.tw/embedded/SDIO)
# 6/13
- mmap 和 mmap2其實功能差不多，只是 mmap2是給系統實作用
- 編譯器最佳化
- constant propagation: 傳遞常數
- constant folding: 先計算常數再展開
- Static Single Assignment (SSA): 靜態單賦值，讓每個變數都只有出現過一次
- bitwise AND 和 logical AND比較
logical AND 左側的 operator 是 false，右側的 operator 不會 evaluate (left-to-right evaluation)
biteise AND 則會左、右側 operator都會 evaluate
- Redis
- 適合寫入少但讀取多的情境
- in-memory cache
- RCU
- 讀多寫少的情境，可以做到 lock-free (只要執行足夠長的時間，至少會有一個執行緒會有進展)
Sign in with Wallet
Connect another wallet