# 2024-03-26 / 04-02,04,09,11 討論簡記
> 回顧[第 5 週討論](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ)

## fennecJ
> [quiz1+2](https://hackmd.io/@fennecJ/linux2024-q1q2)

針對鏈結串列的 Timsort, Adaptive Shivers Sort, PowerSort 實作評估

## weihsinyeh
> [lab0](https://hackmd.io/@weihsinyeh/SJUVTnEn6)

LCG (Linear congruential generator) 亂數產生器。
統計方法驗證 shuffle

從 `srand(time(NULL))` 到 `srand(os_random(getpid() ^ getppid()))`

## willsonbo
aligned 的作用，為何沒有*memchr_opt 後跑出來的結果還是一樣

## marvin0102
> [2024q1 第 7 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz7)

unsigned long *asrc = (unsigned long *) src;

> 上述資料型別的定義是否必要？

是，因為如此才能定義指標位移的長度

        unsigned long mask = d << 8 | d;
        mask |= mask << 16;
        for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
            mask |= BBBB;

>上述程式碼的作用是什麼？

製作過濾器，使程式可一次比對 64 位元長度的字串

        unsigned long mask = d << 8 | d;
        mask |= mask << 16;
-       for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
-           mask |= BBBB;
+       mask |= mask << 32;

可以將程式簡化為上面這種形式

while (len >= LBLOCKSIZE) {
            if (DETECT_CHAR(CCCC, mask))
                break;
            asrc++;
            len -= LBLOCKSIZE;
        }

>上述程式碼的作用是什麼？

對字串進行比對，當遇到 '\0' 時跳出迴圈，當比對的 64 位元字串出現字元 `d` 時，可以透過巨集 `DETECT_CHAR` 判斷後跳出迴圈

---

## idoleat
在 [\[RFC/PATCH\] doc: volatile considered evil](https://lwn.net/Articles/233482/) 中 Linus 提到
> In C, it's "data" that is volatile, but that is insane. Data
isn't volatile - _accesses_ are volatile. So it may make sense to say
"make this particular _access_ be careful", but not "make all accesses to
this data use some random strategy".
>
> So the only thing "volatile" is potentially useful for is:
>
> - actual accessor functions can use it in a _cast_ to make one particular
access follow the rules of "don't cache this one dereference". That is
useful as part of a _bigger_ set of rules about that access (i.e., it
might be the internal implementation of a "readb()", for example).
>
> - for "random number generation" data locations, where you literally
don't _have_ any rules except "it's a random number". The only really
valid example of this is the "jiffy" timer tick.
>
> Any other use of "volatile" is almost certainly a bug, or just useless.

Linux kernel 中 `WRITE_ONCE` 和 `READ_ONCE` 的定義有兩種
第一種：

#define WRITE_ONCE(x, val)				\
({							\
	union { typeof(x) __val; char __c[1]; } __u =	\
		{ .__val = (val) }; 			\
	__write_once_size(&(x), __u.__c, sizeof(x));	\
	__u.__val;					\
})

定義於 `tools/include/linux/compiler.h` 及 `tools/virtio/ringtest/main.h` 中

第二種：

#define WRITE_ONCE(x, val) ((*(volatile typeof(x) *) &(x)) = (val))

定義於 `include/asm-generic/rwonce.h`, `samples/bpf/xdp_sample.bpf.h`, `tools/testing/selftests/bpf/bpf_arena_common.h`, `tools/testing/selftests/bpf/progs/map_kptr.c` 及 `tools/virtio/linux/compiler.h` 中。最常被使用的 `include/linux/compiler.h` 中 include 了第一個

* 關於 Data isn't volatile - accesses are volatile，第二種定義的方式是使用一個 volatile pointer 指向要寫入的物件的地址再取值做寫入，這樣算是 volatile access 的表現？
* 對於重複定義多次，是否可以統一都使用同一個定義，移除其他的？
* `rwonce.h` 的有加 `do{}while(0);` ，不過這邊沒有需要 dangling else 要用此方法避免？

### Concurrency Primer
* 與 `cmpxchg` 此可能花費上百週期的指令相比，`LL` 與 `SC` 之間可以被中斷，這是否意味著使用 `LL` 與 `SC` 達成 atomic 語意有比較多的 preemption point?

---

[第 8 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz8)

## vax-r

(第三週) task_sched.c 的缺點

stackful vs. stackless
本次 (quiz8) 為 stackful
cleanup

[SSE](https://en.wikibooks.org/wiki/X86_Assembly/SSE) 在 x64 ABI 是必要規範 (意味著強制使用 FPU)
soft-fp
GPR -> FPU register -> GPR
hardfp

https://github.com/sysprog21/cserv/blob/master/src/coro/switch.c

已註冊的 cleanup 函式依據什麼順序執行？

為何用 C11 Atomics?
> 可與 pthread 並存

https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-atomics
atomic RMW (read-modify-write)

no interleaving => 強制讓 A 先執行再執行 B (one of solutions)

恐龍書: test-and-set (tas)
compare-and-swap (cas)

* relaxed memory order 不能保證多執行緒的 synchronized-with 關係是因為他只保證對應指令的 atomic 特性，但允許各種 store/load 的重排而造成共享變數的改動不一定可見 (visible) 嗎？
* 如果 atomic CAS 指令流程被打斷 (X)，有其他執行緒介入改寫記憶體內容，但是改寫的值和原先相同 (e.g. 1 改成 1 這樣)， CAS 指令能否偵測到，或者說這是否合法？
* 如果 atomic ops 執行到一半，發生 (硬體) 中斷
* [Atomic 操作: 非阻塞式同步的基石](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-atomics#Atomic-%E6%93%8D%E4%BD%9C%EF%BC%9A%E9%9D%9E%E9%98%BB%E5%A1%9E%E5%BC%8F%E5%90%8C%E6%AD%A5%E7%9A%84%E5%9F%BA%E7%9F%B3) 提到 CAS 的實作，當中依舊有用到 `lock` ，那這樣還算是非阻塞式同步嗎？
> TODO: 標註虛擬碼的限制

RISC-V
addi 只在 register file 上操作
jalr

## LIAO-JIAN-PENG
merge sort 可否平行？
(show me the code, using pthread)

為何 lib/list_sort.c 要 in-place?

### in-place algorithm
in-place algorithm 直接在原始資料結構進行操作，不需要增加額外存儲空間，這種操作也是只對原始資料結構進行修改，不會新增或複製一份新的資料。由於使用 inplace algorithm 不需要額外的儲存空間，因此在大型資料處理時的效果會更加明顯，特別是在嚴格限制記憶體使用量的情況下(如 Linux kernel)。
> [wiki: In-palce algorithm](https://en.wikipedia.org/wiki/In-place_algorithm)

> [In-Memory Layout of a Program (Process)](https://gabrieletolomei.wordpress.com/miscellanea/operating-systems/in-memory-layout/)

### sort 使用 malloc 的風險
對於在函式中使用 malloc 動態配置記憶體，然後在函式外部釋放的情況，確實存在一些風險和不穩定性。這主要涉及到不同的記憶體配置方式(如 first-fit 和 best-fit)以及在函式內部不知道何處釋放記憶體的問題。

**不同的記憶體配置方式**： 動態分配記憶體的時間不穩定主要是由於不同的記憶體配置方式導致不同的性能表現。例如，使用first-fit方式，系統會從記憶體池中找到第一個滿足分配要求的空間分配給新的內存塊，這可能會導致內存碎片化問題。而best-fit方式則會在記憶體池中找到最接近要求大小的空間，但這可能需要額外的搜索時間。因此，不同的配置方式會讓運算時間不穩定。

**釋放記憶體位置不明**： 在函式內部動態分配記憶體後，由於函式內部並不知道何時或何處釋放記憶體，可能導致記憶體泄漏的問題。如果忘記在函式外部釋放已分配的記憶體，則該內存將無法被回收，從而導致系統的內存消耗不斷增加，最終可能導致系統性能下降或崩潰。

綜合以上兩點，使用malloc在函式中動態分配記憶體，然後在函式外部釋放，存在著時間不穩定性和內存泄漏的風險。

參考資料: [First-fit](https://www.geeksforgeeks.org/first-fit-allocation-in-operating-systems/), [Best-fit](https://www.geeksforgeeks.org/best-fit-allocation-in-operating-system/?ref=lbp)
> Memory Allocation Matters: [Deterministic Memory Allocation for Mission-Critical Linux](https://static.sched.com/hosted_files/ossna2017/cf/Deterministic%20Memory%20Allocation%20for%20Mission-Critical%20Linux.pdf)

## millaker
https://en.wikipedia.org/wiki/ABA_problem