# 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

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 位元情境）

#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 的結果會是二補數中的負數，再與零比較作範圍判斷。

/* 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