# 2024-06-11,13,20 討論簡記
> [課程期末專題](https://hackmd.io/@sysprog/linux2024-projects)
### 第 17 週測驗 `1`
問題 : 如何避免 [ABA](https://en.wikipedia.org/wiki/ABA_problem) 問題?
Thread~1~ 寫 A 入 stack 後，stack 的top 為 A。
Thread~2~ 搶佔再寫入 B 又寫入 A 入 stack 後。
Thread~1~ 繼續工作，檢查 stack 的 top 值發現仍然是 A ，但其實這個 A 並非 Thread~1~ 一開始寫入的 A 。
#### stack `push` 的操作 :
step 0: Thread~2~ 要 push 變數 `node C`
step 1: Thread~2~ 先看了 stack 的頂端 `head orig`，發現現在頂端為 `node B` ，`aba=1`。
step 2: Thread~2~ 也準備了一個 `head next` 將其 `aba` 設為 2。
step 3: 接下來將 `node C` 的 的 next 指向 `node B` 。
step 4: 再將 `node C` 存到 `head next` 的 node 。
step 5: 再將 `head next` 與 `head orig` 交換即可。
所以 lstack_head 就是像一個套子，其功能是包 `aba` 變數。因此在 step 5 交換套子的時候需檢查，交換的那一刻 是否 `head orig` 的 `aba:1` 也就是 `head next` 的 `aba:2` 編號少一。如果不是則這次在 Thread~2~ step0 到 step5 的過程有其它執行緒將 `head orig` 交換了 。如此一來就可以達到沒有操作時不需要有 lock 。
```
head next
|------------|
| aba : 2 |
| | _________
| | | node C |
| | ---------
|------------| |
|
head orig | next (step 3)
|------------| |
| aba : 1 | |
__________ next| _________ | |
| node A | <---- | node B | <-----|
---------- | --------- |
|------------|
```
#### stack `pop` 的操作 :
step 0: Thread~2~ 要 pop 變數
step 1: Thread~2~ 先看了 stack 的頂端 `head orig`，發現現在頂端為 `node B` ，`aba=1`。
step 2: Thread~2~ 也準備了一個 `head next` 將其 `aba` 設為 2。
step 3: 將 `node A` 放入 `head next`。
step 4: 再將 `head next` 與 `head orig` 交換即可。如此一來新的 `head orig` 也就是 stack 的頂端存的就是 `node A` 。
所以在交換的那一刻也就是 step 4 只要確認 `head orig` 的 `aba:1` 也就是`head next` 的 `aba:2` 編號少一，就可以確保沒有其它執行緒在 step 0 到 step 4 的過程中對 stack 頂端操作。
```
head next
|------------|
| aba : 2 |
| |
| |
| |
|------------|
head orig
|------------|
| aba : 1 |
__________ next| _________ |
| node A | <---- | node B | |
---------- | --------- |
|------------|
```
問題 : `lstack->free` 的作用?
`lstack->free` 這個代表有一個空間可以給執行緒做 push 變數時候使用。
當 Thread~2~ 要 push 先將變數放到 `lstack->free` 這個 node 裡面。所以`node C` 原先就是 free node
---
## 第 17 週測驗 `2`
一種會發生 deadlock 的執行路徑
```
[ Task A ] [ Task B ]
mutex_lock(&mutex1);
mutex_lock(&mutex2);
mutex_lock(&mutex2);
mutex_lock(&mutex1);
```
為何 `does_follow` 可追蹤 lock dependency graph？
follows 紀錄是否發生 directed cycles
follows[i][j] i -> j -> k
follows[j][k]
在測驗題裡面是用深度優先去搜尋是否會有 directed cycles。先去知道 acquire 的 lock 是被哪個 pid 所持有(hold)。接下來看自己所持有(hold) 的 lock 是否被其它 pid acquire。如果有，且該 pid 持有自己 acquire 的 lock 則出現 directed cycles。有 dead lock 發生。
```
my_pid
lock 1 <- pid:x acquire。
lock 2 <- my_pid acquire
```
因此偵測這些 dead lock 的方式會用到離散數學跟演算法的方式，看如何可以快速的找到 directed cycles。但 linux 裡面 [/kernel/locking/lockdep.c](https://github.com/torvalds/linux/blob/master/kernel/locking/lockdep.c) 是用廣度優先的方式璇找 lock dependency，因為它想要快速偵測到 deadlock，一旦偵測到就系統就關閉。
問題 : Linux 是如何實作 lock dependency 的 ?
> weihsinyeh
在 [Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module) 提到的 [BUG_ON](https://kernelnewbies.org/FAQ/BUG) 如果真的偵測到錯誤 kernel 會直接關機，不像 assert 只是不再繼續執行程式，並將程式運行的錯誤印出來。將 `BUG_ON` 打開，就會用 mutex 的 API 來重新包裝真正 lock 實作 e.g., debug_mutex_lock_common 。
在 [kernel/locking/mutex-debug.c](https://github.com/torvalds/linux/blob/master/kernel/locking/mutex-debug.c) 的 debug_mutex_wake_waiter 就像 futex 的功能。
Linux 還有 `WARN_ON` 來 trap 錯誤。
linux 的追蹤不同的 lock 有不同的方法。因為有些 lock 特化出新的功能，像 irq 現在也有新的 spin lock ，但雖然複雜的 lock，本質上追蹤 lock dependency 的方式是相同的。
## [RISC-V 最佳化編譯器實作](https://hackmd.io/@sysprog/H11Da3FQA)
self-hosting
Old compiler (O) ->
newer compiler (written in C)
use old compiler to compile newer compiler
-> binary for newer compiler
-> compile newer compilers
bootstrapping
- stage0 : 用既有的 C 編譯器，得到 x86-64 的執行檔
- stage1 : 用 stage0 得到的 x86-64 執行檔「編譯自己」，得到 Arm 的執行檔
- stage2 : 用 stage1 得到的 Arm 執行檔「編譯自己」
(cross compiler)
如何用 mmap 系統呼叫來實作 malloc
```c
int x = 0, y = 13;
/* bitwise AND */
if (x & y) /* instruction: and -> x 和 y 都會 evaluate */
return 0;
/* logical AND */
if (x && y) /* 只要是 x 是 false (0)，y 「不要」 evaluate */
return 0;
```
bitwise AND 的運算元 evaluate 順序未指定；logical AND 則保證為由左至右，如果左運算元為 false 右運算元不會 evaluate。
shecc 要如何驗證 code transformation 是正確的？目前只有看到測試，但是測試不見得涵蓋所有改寫的行為。
> [C-Reduce](https://github.com/csmith-project/creduce) is a tool that takes a large C or C++ program that has a property of interest (such as triggering a compiler bug) and automatically produces a much smaller C/C++ program that has the same property.
defs.h 裡面有原始碼大小上限，如果 shecc 本身超過這個上限不就沒辦法 bootstrap 了？
> 屆時再做調整？
> 我的想法是，為了避免動態配置空間，一樣是先靜態配置，不過分 A, B 兩個空間，大小一樣沿用原本的大小。A 放滿了就放 B，當 parse 到 B 時把 A 清空繼續把原始碼放到 A，交替使用直到 parsing 完畢
> 聽起來像是 ring buffer 的概念，是一種解決方案沒錯。
## [運用並行處理來強化既有的應用場景: Redis](https://hackmd.io/@sysprog/B1W2HKTER)
為什麼要分五種 flavor?
為了要在不同的作業系統或是處理器架構上執行，例如有可能作業系統不支援 `sys_membarrier()` 系統呼叫，所以沒辦法使用 RCU using sys_membarrier() system call (`liburcu`) ，這時就要換另外一種 flavor ，必須要使用 Memory-barrier-based RCU (`liburcu-mb`) 。
---
[全向量視窗系統實作](https://hackmd.io/@sysprog/B13GqdgQ0)
clip region
double buffering
video RAM (DRAM)
## 第 18 週測驗 `1`
`x / 128` ==> `x >> 7`
log_2(128) = 7
* 為何 `#define M ((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF) / (D) + 1))` ?
> 因為計算商數時，需要處理 ${\lceil {2^{64} \over d} \rceil}$ 的數學運算。而若用 C 語言來實作，可以先使用除法運算將其無條件捨去，再加一變成無條件進位，而 $2^{64} -1$ 則是要應對 $d$ 為二的冪時的例外狀況。
Assume 8-bit arith,
n = 217
D = 3
uint8_t x = 0111 1001
uint8_t D = 0000 0011
#define M ((uint16_t)(UINT16_C(0xFFFF) / (D) + 1))
=> `0x5556` or `21846`
uint8_t quotient = ((uint16_t) M * n) >> 8;
=> `1`
### 方法說明
程式碼實作 模三運算（16 位元情境）
```c
#include <stdio.h>
#include <stdint.h>
const uint8_t D = 3;
#define M ((uint16_t)(UINT16_C(0xFFFF) / (D) + 1))
/* compute (n mod d) given precomputed M */
uint8_t quickmod(uint8_t n)
{ uint16_t quotient = ((uint16_t) M * n) >> 16;
return n - quotient * D;
}
int main (){
uint8_t n = 217;
uint8_t result = quickmod(217);
printf("output: %u, %u", M, result);
}
```
```
output: 21846, 1
```
在這個 8 位元的處理器上，我們要計算任意正整數 $N$ 模三之結果， 但是模數會使用到除法運算，為了避免大量時脈週期運算，我們會將整數的模運算簡化為乘法以及位移運算，概念如下所述：
首先模數 $mod$ 可以運算方式為 $mod =$ $n$ $\times$ ${\lfloor {n \over d} \rfloor}$ $\times$ $d$ ，其中 ${\lfloor {n \over d} \rfloor}$ 為商數，我們可以再將商數轉化為 ${\lfloor {n \over d} \rfloor} =$ $n$ $\times$ ${\lceil {{2^{16}} \over d} \rceil}$ $\times$ ${1 \over {2^{16}}}$ ，而其中的 ${\lceil {{2^{16}} \over d} \rceil}$ 就是上面程式中的 $M$ 巨集，除了 $M$ 以外的商數運算已經轉化為乘法以及位移運算。
接著我們來探討 $M$ 的巨集實作，也就是 ${\lceil {2^{16} \over d} \rceil}$ 的數學運算，我們將其轉化為 ${\lfloor {{2^{16} -1} \over d} \rfloor} + 1$ 。若用 C 語言來實作，就是使用除法運算將其無條件捨去，再加一變成無條件進位，而 $2^{16} -1$ 則是要應對 $d$ 為二的冪時的例外狀況。雖然最後還是會使用到除法運算，但是在編譯器最佳化的情況下（使用 constant propagation），預處理階段已經將 $M$ 轉化為常數，因此實際在執行時也不會有除法運算。
---
1, 2, 3, ..., FASTDIV_SAFEMAX (256)
bound > 0U && bound <= FASTDIV_SAFEMAX
short-circuit
pre-compute ：
原先的範圍確認需要兩次比較，但是我們可以使用二補數的特性 （自然數 $N$ 之最重要位元 ${MSB}$ 為零 、 負數 ${MSB}$ 為一） ， 確認上界與 X 之差以及 X 與下界之差皆大於零，若有一者不符合，則 bitwise OR 的結果會是二補數中的負數，再與零比較作範圍判斷。
```ruby
/* Range check
* For any variable range checking:
* if (x >= minx && x <= maxx) ...
* it is faster to use bit operation:
* if ((signed)((x - minx) | (maxx - x)) >= 0) ...
*/
```
---
[CPU 排程器研究](https://hackmd.io/@sysprog/BJdyxvxX0)
sched_ext 對 Linux 技術社群的影響？
-> Meta
-> Netflix
演化
early Linux sched -> O(n) -> O(1) -> CFS -> EEVDF
(通用的路線) 缺點/限制
特定的 workload <--
一台伺服器通包 vs. 多台主機分工 (microservices)
Redis
Database
=> predict
machine learning
feature extraction
Sign in with Wallet
Connect another wallet