# 2024q1 Homework6 (integration)
contributed by < [`weihsinyeh`](https://github.com/weihsinyeh) >
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 142
Model name: Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz
Stepping: 12
CPU MHz: 2100.000
CPU max MHz: 4200.0000
CPU min MHz: 400.0000
BogoMIPS: 4199.88
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-7
$ uname -r
5.15.0-102-generic
```
## 可用的工具
### Perf
分析執行檔與設定的參數的效能
```shell
$ sudo perf stat -d ./false_sharing --nofalse-sharing
```
## 開發紀錄
### Linux 核心模組-前期準備
#### 解釋 insmod
在目錄裡面要有 module 的 c 檔案 `filename.c` 與 `Makefile`。下命令 `make` 相當於
```shell
$ make -C /lib/modules/5.15.0-102-generic/build M=/home/weihsin/develop/kernel/hello-2 modules
```
> make -C: Change to directory (**/lib/modules/5.15.0-102-generic/build**) dir before reading the makefiles or doing anything else.
經過這一行後會是執行 `/lib/modules/5.15.0-102-generic/build` 這個路徑下面的 `Makefile` 。其中有很多目標包含 `modules` 跟 `clean` 。 `clean` 會把用 modules 建立的檔案如下刪掉。`-M` 是用來讓 `Makefile` 知道要建立的目標 module 是在哪個目錄裡。建立時會出現這些檔案：
`hello-1.ko` -> `.hello-1.ko.cmd`
`hello-1.mod` -> `.hello-1.mod.cmd`
`hello-1.mod.o` -> `.hello-1.mod.o.cmd`
`hello-1.o` -> `.hello-1.o.cmd`
`modules.order` -> `.modules.order.cmd`
`Module.symvers` -> `.Module.symvers.cmd`
`hello-1.mod.c` 發現每個都會有隱藏檔案且副檔名為 cmd 。沒有印象有看過這種檔案。
接下來將兩個 c 檔案都變成 module 是在原先自己製作的 make file 中加入 `obj-m += hello-2.o` 。再loading 這些 module。
```shell
$ sudo insmod hello-1.ko
$ sudo insmod hello-2.ko
```
讀《The Linux Kernel Module Programming Guide》時候看到 0xbffff978 ，就開始很好奇這個神奇的數字是如何來的。
> The processes would be accessing an index named 0xbffff978 which points to some kind of offset into the region of memory set aside for that particular process.
> TODO : 這跟 register pagefault handler.exeception handler. 把暫存器的內容印出來。 task_struct 印出來。特別地址要改進 kernel 追蹤機制。
在 `insmod` 後會執行 `module_init(simrupt_init);` 在 `init function` 中呼叫 `blk_init_queue()`
參見 [Request queues](https://linux-kernel-labs.github.io/refs/pull/222/merge/labs/block_device_drivers.html) 但這個 API 現在已經移除了。透過 request queue 去儲存 block I/O requests。這裡面存的request 可能是對不同的 block device 操作的。"Each item in the request queue is a request represented by the struct request structure."
> Request queues implement an interface that allows the use of multiple I/O schedulers. A scheduler must sort the requests and present them to the driver in order to maximize performance. The scheduler also deals with the combination of adjacent requests (which refer to adjacent sectors of the disk)."
Linux 在第 5 版本後改為讓使用者自己去建立 request queue ，因此在 `simrupt_init()` `simrupt_exit` 函式中有
```c
device_create(simrupt_class, NULL, MKDEV(major, 0), NULL, DEV_NAME);
...
device_destroy(simrupt_class, dev_id);
```
`init_function()` 會呼叫兩個函式 `device_create()` 用來建立 request queue 與 `add_disk()`是在 `simrupt` 是用 `register_chrdev_region()` 來註冊 Character device drivers 參考 [Character device drivers 在 linux kernel labs 的解釋](https://linux-kernel-labs.github.io/refs/heads/master/labs/device_drivers.html) 。
> The registration/unregistration of a device is made by specifying the major and minor. The dev_t type is used to keep the identifiers of a device (both major and minor) and can be obtained using the MKDEV macro.
> For the static assignment and unallocation of device identifiers, the register_chrdev_region and unregister_chrdev_region functions are used.
所以可以繼續閱讀可以看到當註冊完 Character device drivers 後就會執行初使化與增加識別。透過在 `/linux/cdev.h` 的兩個函式 `cdev_init` 與 `cdev_add`。
初始化：`cdev_init(struct cdev *cdev, struct file_operations *fops);` Character Device Driver 。讓 cdev 這個空間透過 data pointer 指向操作列表 `simrupt_fops` 。
增加識別：`int cdev_add(struct cdev *dev, dev_t num, unsigned int count);` 讓 Kernel 可找到 Character Device Driver 即結構體 `struct cdev simrupt_cdev` 。到這裡 insmod 做了下面這些事情。
```graphviz
digraph structs {
rankdir = LR
node[shape=plaintext];
insmod [fontcolor="black"];
node[shape=box];
init_function [label= "init_function()"];
add_disk [label= "register_chrdev_region()" ];
character_device
fops [label= "simrupt fops" ];
request_queue [label = "X : request queue\n O : Add to disk"]
{
insmod-> init_function
insmod-> add_disk
add_disk-> character_device
character_device -> fops [label = "cdev_init()"]
character_device -> request_queue [label = "cdev_add()"]
}
}
```
原先認為會有一個 request queue ，但在 Character Device Driver 都找不到相關的說明，後來重新思考了為何要分 Block 與 Characer Device Driver ，重看一次《The Linux Kernel Module Programming Guide》5.6 Device Drivers 發現之前沒讀懂。
Block devices 有 request queue，因為同時對不同的 device driver 的操作都會存在 request queue。而 request queue 自己會有一個schedule 用來分配哪個 request 要先做還是後做。這與 storage devices 的 sectors 有關係，如果比較近的 secotor 讀寫就會比較快。而 Character Device 則沒有 request queue ，因為它沒有要寫到較近或較遠的 sectors 所以不需要分配哪個 request 要先做 ，要與 userspace 互動時就時寫入一個 kfifo (First In First Out) 的 buffer。"Most devices in the world are character, because they don’t need this type of buffering, and they don’t operate with a fixed block size."
#### 實驗函式傳遞參數使用的暫存器數量
看[lib/kfifo.c#L122](https://github.com/torvalds/linux/blob/master/lib/kfifo.c#L122)這一行的時候覺得很奇怪，為什麼他要特別傳遞第四個參數，像是在編譯器最佳化的時候說多傳遞參數會有可能不夠暫存器用，而需要配置記憶體。
```c
kfifo_copy_in(fifo, buf, len, fifo->in);
```
就算看到[lib/kfifo.c#L446](https://github.com/torvalds/linux/blob/master/lib/kfifo.c#L446)也可以在呼叫函式前就修改。
```c
kfifo_copy_in(fifo, buf, len, fifo->in + recsize);
```
但後來知道就算多寫出來少一個參數在呼叫函式時傳遞影響並不大。所以做實驗寫一個函式需要傳遞 4 個參數，另一個函式要傳遞 10 個參數。之所以選 10 個參數。是因為參考 [Guide to x86-64](https://web.stanford.edu/class/archive/cs/cs107/cs107.1166/guide_x86-64.html) 回憶上組合語言有學過 caller-saved 與 callee-saved 的暫存器。並且有 9 個 caller-saved 的暫存器。因此我就寫了一個函式需要 10 個參數。
```shell
$ gcc -S register_test.c
movl $1, -40(%rbp)
movl $2, -36(%rbp)
movl $3, -32(%rbp)
movl $4, -28(%rbp)
movl $5, -24(%rbp)
movl $6, -20(%rbp)
movl $7, -16(%rbp)
movl $8, -12(%rbp)
movl $9, -8(%rbp)
movl $10, -4(%rbp)
movl -28(%rbp), %ecx
movl -32(%rbp), %edx
movl -36(%rbp), %esi
movl -40(%rbp), %eax
movl %eax, %edi
call reg4
...
movl -20(%rbp), %r9d
movl -24(%rbp), %r8d
movl -28(%rbp), %ecx
movl -32(%rbp), %edx
movl -36(%rbp), %esi
movl -40(%rbp), %eax
movl -4(%rbp), %edi
pushq %rdi
movl -8(%rbp), %edi
pushq %rdi
movl -12(%rbp), %edi
pushq %rdi
movl -16(%rbp), %edi
pushq %rdi
movl %eax, %edi
call reg10
```
在呼叫 `reg4` 的函式時傳遞參數會先放到暫存器 `%ecx`, `%edx`, `%esi`, `%eax` 中。如果是 `reg10` 則會用到 `pushq` 。
> **《CSAPP Ch3. Machine-Level Representation of Programs》**
> the pushq instruction indicates that the contents of register %rbx should be pushed onto the program stack.
因為有存取到 program stack 所以就會用到記憶體。但上面的程式碼只用到 `%eax` `%esi` `%edx` `%ecx` `%r8d` `%r9d` 這六個暫存器前六個參數，然後用 `%edi` 暫存器來存其他參數從 program stack 拿到的後四個參數。
#### Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)
在 `/proc/kallsyms` 裡面存放symbols ，user可以使用。
> man 5 proc
> This holds the kernel exported symbol definitions used by the modules(X) tools to dynamically link and bind loadable modules.
>
> modules are object files whose symbols get resolved upon running insmod or modprobe. The definition for the symbols comes from the kernel itself; the only external functions you can use are the ones provided by the kernel.
所以當將 modules insert 到 kernel 前會先 `make` 產生一個檔案 `simrupt.mod.c` 裡面定義了 simrupt 這個 module 會用到哪些 symbol 與這些kernel 會在記憶體的哪些位置。但這裡跟在 `/proc/kallsyms` 的記憶體位址不一樣，因為用 KASLR (Kernel Address Space Layout Randomization) 減少資安問題。
user 跟 kernel 溝通的管道是檔案。先寫到 kernel space 的檔案。而kernel module 在讀寫這個檔案。最後user space 的程式再來讀這個 kener module 寫入到檔案的內容。
> **The Linux Kernel Module Programming Guide (§ 6.2 The file structure**)
> Each device is represented in the kernel by a file structure.It represents an abstract open ‘file’, not a file on a disk, which is represented by a structure named inode.
提到 `inode`。 所以當要 kernel 使用 kernel module 的時候會使用 `insmod` 是 "insert modules into the kernel" 然後 module 透過 file 也就是 inode 跟 device 互動。
> **The Linux Kernel Module Programming Guide (§ 6.3 Registering A Device**)
> Char devices are accessed through device files, usually located in /dev.
> Adding a driver to your system means registering it with the kernel. This is synonymous with assigning it a major number during the module’s initialization. You do this by using the register_chrdev function, defined by include/linux/fs.h.
insert simrupt modules into the kernel 後 `/proc/devices` 則可以出現 simrupt 的 device 。
#### MODULE_LICENSE 巨集指定的授權條款
MODULE_LICENSE 這個巨集裡的內容包含 LICENSE AUTHOR DESCRIPTION 會展開並紀錄在 `simrupt.ko` 中。巨集展開的方式在 **[〈Linux 核心模組運作原理〉](https://hackmd.io/@sysprog/linux-kernel-module)** 提到「 繼續將 `__UNIQUE_ID` 展開，`__COUNTER__` 這個巨集由 GCC 自動更新，每當遇到使用到 `__COUNTER__` 就會將其值加一。」。 GCC 會自動更新 UNIQUE_ID 是因為在編譯的時候會有很多相同名稱的變數，要將他們分為不一樣以識別。
```
$ objdump -s simrupt.ko
Contents of section .modinfo:
0000 64657363 72697074 696f6e3d 41206465 description=A de
0010 76696365 20746861 74207369 6d756c61 vice that simula
0020 74657320 696e7465 72727570 74730061 tes interrupts.a
0030 7574686f 723d4e61 74696f6e 616c2043 uthor=National C
0040 68656e67 204b756e 6720556e 69766572 heng Kung Univer
0050 73697479 2c205461 6977616e 006c6963 sity, Taiwan.lic
0060 656e7365 3d447561 6c204d49 542f4750 ense=Dual MIT/GP
0070 4c007372 63766572 73696f6e 3d453135 L.srcversion=E15
0080 36333634 36333236 34374533 45414133 6364632647E3EAA3
0090 36333235 00646570 656e6473 3d007265 6325.depends=.re
00a0 74706f6c 696e653d 59006e61 6d653d73 tpoline=Y.name=s
00b0 696d7275 70740076 65726d61 6769633d imrupt.vermagic=
00c0 352e3135 2e302d31 30352d67 656e6572 5.15.0-105-gener
00d0 69632053 4d50206d 6f645f75 6e6c6f61 ic SMP mod_unloa
00e0 64206d6f 64766572 73696f6e 732000 d modversions .
```
之所以要做這件事對核心的影響參考 **《[Linux Device Driver 3/e](https://static.lwn.net/images/pdf/LDD3/ch01.pdf)》CH1**：
> The GPL allows anybody to redistribute, and even sell, a product covered by the GPL, as long as the recipient has access to the source and is able to exercise the same rights. Additionally, any software product derived from a product covered by the GPL must, if it is redistributed at all, be released under the GPL.
由於這個版權每個人都可以修改基於 GPL License 的程式。
> TODO: (GPL 與否對於可用的符號列表有關)
---
#### [Linux 核心虛擬化系統](https://hackmd.io/@sysprog/linux-virtme)
進入[virtme-ng](https://github.com/arighi/virtme-ng)的python 環境後
```shell
$ conda activate virtme
$ cd virtme-ng
$ make ARCH=x86 CROSS_COMPILE=x86_64-linux-gnu- -j$(nproc)
$ cd ../linux
```
在 virtime-ng 虛擬機器中啟動 Linux 核心:
```shell
$ virtme-run --kdir . --mods=auto
```
在宿主 host 建立的檔案在虛擬機器上會是 `Read-only file system`
strace insmod 看到先有 `exevce` insmod kernel module `read` `write`
```shell
$ git diff
index ccde19e7275f..de239a6cd358 100644
--- a/init/main.c
+++ b/init/main.c
@@ -1535,6 +1535,7 @@ static int __ref kernel_init(void *unused)
do_sysctl_args();
+ *(char *) NULL = 0;
if (ramdisk_execute_command) {
ret = run_init_process(ramdisk_execute_command);
if (!ret)
```
編譯 linux
```shell
$ cd linux
$ make ARCH=x86 CROSS_COMPILE=x86_64-linux-gnu-
```
啟動 linux 核心
```shell
$ cd linux
$ virtme-run --kimg arch/x86/boot/bzImage
[ 0.472787] note: swapper/0[1] exited with irqs disabled
[ 0.473078] Kernel panic - not syncing: Attempted to kill init! exitcode=0x00000009
[ 0.473659] Kernel Offset: 0xf600000 from 0xffffffff81000000 (relocation range: 0xffffffff80000000-0xffffffffbfffffff)
[ 0.474371] ---[ end Kernel panic - not syncing: Attempted to kill init! exitcode=0x00000009 ]---
```
#### [workqueue](https://www.kernel.org/doc/html/latest/core-api/workqueue.html)
```c
struct workqueue_struct *alloc_workqueue(const char *fmt,
unsigned int flags,
int max_active, ...)
```
> **C99/C11 Standard (§ 6.7.5.3 Function declarators (including prototypes))**
> If the list terminates with an ellipsis (, ...), no information about the number or types of the parameters after the comma is supplied.
[workqueue.c#L81](https://github.com/torvalds/linux/blob/master/kernel/workqueue.c#L81)
```c
POOL_BH = 1 << 0, /* is a BH pool */
```
MT thread wq : CPU 的數量 $\times$ (workqueue 中 worker 的數量) $=$ worker thread 的總量。與 ST thread wq 相比能夠提昇並行，然而因為在系統開始就建立所有的執行緒，PID space 會被用光。所以總量仍有數量限制。
此外 MT thread 也不能將 workder thread 移動到其他 CPU 的 workqueue 上。所以並行化並未很好的實現，因此才有 CMWQ。
### simrupt
從程式被 insert 進 kernel 後就會執行 `simrupt_init` 的函式後建立 workqueue。 每個 worker 負責執行函式指標指向的函式。`simrupt` 中此函式就是 `simrupt_work_func` 透過 `produce_data` 不斷將字元寫入 `rx_fifo` 指標所指向的 kfifo buffer ，其中資料存取方式顧名思義：first in first out，再透過`kfifo_len(&rx_fifo)` 來知道能讀/寫多少解決生產者消費者問題。[kfifo.h#L233](https://github.com/torvalds/linux/blob/master/include/linux/kfifo.h#L233)
```
* kfifo_len - returns the number of used elements in the fifo
* @fifo: address of the fifo to be used
```
這件事情在 insert module 到 remove module 的期間都會不斷進行。而使用者是如何看到寫到 kfifo buffer 的資料，是用 `kfifo_to_user` 但這裡會傳遞一個寫到 userspace 的指標 ： `void __user *to` 。但其實看到這個東西很奇怪，因為void 本身是一個型態了，但在只標前面的都是一個型態所以 `__user` 也會是型態的一部分。
同樣的 getcpu 會得到不同的值。 CMWQ 可以由 kernel 來自己決定 CPU，或可以自己綁定行程要在哪個 CPU 。兩個 worker 要互動。
#### Circular buffer
[linux/circ_buf.h](https://github.com/torvalds/linux/blob/f03359bca01bf4372cf2c118cd9a987a5951b1c8/include/linux/circ_buf.h) 提供一個管理一個 buffer 的 API buffer 的空間由使用者自己定義。所以在 simrupt_init 會先配置一個這個 buffer 有一個 PAGE 的大小。 `fast_buf.buf = vmalloc(PAGE_SIZE);` 將buffer 的虛擬記憶體位址存在 `fast_buf.buf` 。我在思考這個 vmalloc 是要用 PAGE size 的原因，也在想是否 `vmalloc` 是讓它變成 faster buffer 的原因？但是 `vmalloc` 也只有分配一個實體記憶體中 PAGE size。
```graphviz
digraph structs {
rankdir = LR
node[shape=plaintext]
node[shape=ellipse]
main [label= "main thread"]
worker1 [label = "worker thread"]
worker2 [label = "worker thread"]
worker3 [label = "worker thread"]
node[shape=box];
kfifo [label = "kfifo\n(1 PAGESIZE)"];
buffer [label = "buffer\n(1 PAGESIZE)"];
{
main->buffer [label = "put data"]
buffer->worker1 [label = "get data" color="blue"]
worker1->kfifo [label = "put data" color="blue"]
buffer->worker2 [label = "get data" color="blue"]
worker2->kfifo [label = "put data" color="blue"]
buffer->worker3 [label = "get data" color="blue"]
worker3->kfifo [label = "put data" color="blue"]
kfifo->userspace [label ="kfifo_to_user()"]
}
}
```
main thread 會放更新的字元到 buffer 中，而每個 worker thread 則是使用函式 `fast_buf_get()` 從 buffer 拿出資料後，透過 `produce_data()` 放到 kfifo。kfifo 這個 buffer 是 `rx_fifo`指標的位址。但kfifo 也是一個 PAGE 的大小 `if (kfifo_alloc(&rx_fifo, PAGE_SIZE))`
接著透過 `kfifo_to_user()` 將資料從 kfifo 寫到 userspace，但這裡其實是用 file_operations 中 `read` 來讀取 Character Device Driver 中。 但是在程式碼未看初始化的情況下直接傳遞參數，同時因為 file_operations 是在 `cdev_init()` 被建構讓kernel 知道可以用哪些函式來與 Character Device Driver 互動，因此我先推論在 `cdev_init()` 會宣告此指標 `char __user` 指向的 userspace。
```c
static ssize_t simrupt_read(struct file *file,
char __user *buf,
size_t count,
loff_t *ppos)
```
但仔細去看 [`cdev_init()`](https://github.com/torvalds/linux/blob/master/fs/char_dev.c#L658) 與 `cdev_add()` 都沒有發現宣告 userspace 的地方。最後我就直接在 `include/linux/compiler_types.h` 所以 `__user ` 是在告訴編譯器 `char*` 存放記憶體位址的屬性為 `__user` 的 address_space 。
```c
# define __user __attribute__((noderef, address_space(__user)))
```
至此雖更了解 Character Device Driver，但仍無法說明 circular buffer 存在的原因。
```graphviz
digraph structs {
rankdir = LR
node[shape=plaintext]
node[shape=ellipse]
main [label= "main thread"]
node[shape=box];
kfifo [label = "kfifo\n(1 PAGESIZE)"];
{
main->kfifo [label = "put data"]
kfifo->userspace [label ="kfifo_to_user()"]
}
}
```
為何不是上面這張圖？以 buffer 的存在意義推理： main thread 存取 kfifo 的速度較 fast_buf 慢。情境是 main thread 放資料到 buffer (3 個/秒)，而對 kfifo 存取資料 (1 個/秒)，所以透過 3 個 worker 其工作為從 buffer 拿資料(1 個/秒)，存到 kfifo (1 個/秒)。就可以改善「原本整體效能會限制在 kfifo 的存取速率」的效能瓶頸。但這個推理要如何實驗才能說明。要確定存取 fast_buf 的速度是否比 kfifo 快。此外還要確定多個 worker 的機制是 [Scalability](https://en.wikipedia.org/wiki/Scalability)。 所以才會要探討 simrupt 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 lock-free。
#### mutex lock 改寫為 lock-free
要改成 lock-free (這裡是指沒有 lock)的原因是：workers 如果要去存取共享資源必須等待其中一個 worker unlock。那其他 workers 就是得等待，形成阻塞式同步。因此我原本認為是要用 Atomic 操作因為它是非阻塞式同步的基石，但因為閱讀完的理解是把對 lock 的操作變成硬體的指令而不是用程式碼，但就算變成指令仍然會需要等一個 atomic 的物件。如同下面:
這裡是程式碼用到 lock 的地方在每個 worker thread 從 buffer 拿出資料，還有寫到 kfifo 。也就是多個 worker thread 在從分別是共享資源 (buffer) 「取」與「存」到共享資源 (kfifo) 中會需要 lock (藍色箭頭的操作）。
所以先把 mutex lock 拿掉後，將 fast_buf_get 改為只有一個執行緒會在一個時間點做讀 ring buffer 的 tail 以及增加 ring buffer 的 tail 的值。
```c
static int fast_buf_get(void)
{
struct circ_buf *ring = &fast_buf;
/* prevent the compiler from merging or refetching accesses for tail */
unsigned long head = READ_ONCE(ring->head), tail = ring->tail;
int ret;
if (unlikely(!CIRC_CNT(head, tail, PAGE_SIZE)))
return -ENOENT;
/* read index before reading contents at that index */
smp_rmb();
/* extract item from the buffer */
ret = ring->buf[tail];
/* finish reading descriptor before incrementing tail */
smp_mb();
/* increment the tail pointer */
ring->tail = (tail + 1) & (PAGE_SIZE - 1);
return ret;
}
```
#### 探討 READ_ONCE 的意義
首先在 `fast_buf_put` 這個函式裡面 `head = READ_ONCE(ring->head)` 這裡的操作根據 [memory-barriers](https://www.kernel.org/doc/Documentation/memory-barriers.txt) 的說明為:
`head = LOAD ring->head` , `MEMORY_BARRIER`
但因為不知道 memory barrier 在組語的用途，所以做了一個實驗。
```c=
#define __READ_ONCE(x) (*(const volatile int *) &(x))
#define mb() __asm__ __volatile__ ("" : : : "memory")
int a, b;
int i, j;
void foo()
{
a = __READ_ONCE(i);
mb();
b = __READ_ONCE(j) / 16;
}
```
發現有沒有第 8 行 memory barrier 轉成組合語言都一樣，代表 READ_ONCE 有 memory barrier。再來改成沒有 memory barrier 。組合語言的變化：
```diff
movl i(%rip), %eax
movl %eax, a(%rip)
- leaq j(%rip), %rax
- movl (%rax), %eax
+ movl j(%rip), %eax
```
```c=8
mb();
b = __READ_ONCE(j) / 16;
mb();
c = i;
```
> 根據 **CSAPP (§ 3.4.3 Data Movement Example )**
```
long exchange(long *xp, long y)
xp in %rdi, y in %rsi
1 exchange:
2 movq (%rdi), %rax Get x at xp. Set as return value.
3 movq %rsi, (%rdi) Store y at xp.
4 ret Return.
```
第 2 個指令是將從 memory `(%rdi)` 讀到的值存到暫存器 `%rax`。第 3 個指令是將從 暫存器 `%rsi` 讀到的值存到 memory `(%rdi)`。因此由此可知 `(%暫存器名稱)` 為讀取 memory 的值。
回去解釋組合語言為 : 先從 memory `j(%rip)` 讀到的值存到暫存器 `%rax` 再從 memory `(%rax)` 讀到的值存到 `%eax` 暫存器中。
> [並行程式設計: Atomics 操作](https://hackmd.io/@sysprog/concurrency-atomics)
> READ_ONCE 不是 compiler barrier ，不能把 a = i 和 b = j / 16 完全隔離，因此用 `__READ_ONCE` 能保證的也只是 i 和 j 的讀取順序。
所以看到 READ_ONCE 是告訴編譯器要做的事情確保從 LOAD 的讀取順序 compiler barrier，所以看到組語的時候是已經做完順序的保證了。而從組合語言的意義可看出它也會去記憶體讀取資料。
所以在 simrupt 的時候可以不用 `head = READ_ONCE(ring->head)` 也行。
#### 探討 lock-free 能否在 worker 從 ring buffer 取資料 :
接下來回到原本的程式，就是把原先確保在讀取 `ring->tail` 後將其值存到 `tail` ，這個值跟最後指定`(tail + 1) & (PAGE_SIZE - 1)` 給 `ring->tail`前的 `ring->tail` 與 `tail` 是一樣的。這表示在過程中確保在一個執行緒取 buffer ring 的一個資料時，沒有其他執行緒同時也在取同一份資料。
#### 探討 lock-free 能否在 worker 放資料入 kfifo :
接著是修改 worker 到 kfifo_in 的地方，這裡因為沒有像 Ring Buffer 有指標指向現在 kfifo 要放入的位址。而是直接用 kfifo 的位址 `&rx_fifo` ，所以不能像上面程式那樣用 atmoic 修改。我原本想看 kfifo 有沒有提供指標，但就看到裡面 [include/linux/kfifo.h](https://github.com/torvalds/linux/blob/master/include/linux/kfifo.h#L516C1-L517C60) 說單一 reader 跟 writer 不用額外的 lock，代表其他情況就要。我沒看懂下面的程式碼，但是他不用像是 ring buffer 那樣提供 reader 與 writer 的作用的位址，讓我不知道為什麼故意要把操作包裝起來的用意是甚麼。kfifo 之所以要用 lock 的是因為 lock 實作簡單。
```c
* Note that with only one concurrent reader and one concurrent
* writer, you don't need extra locking to use these macro.
*/
#define kfifo_in(fifo, buf, n) \
({ \
typeof((fifo) + 1) __tmp = (fifo); \
typeof(__tmp->ptr_const) __buf = (buf); \
unsigned long __n = (n); \
const size_t __recsize = sizeof(*__tmp->rectype); \
struct __kfifo *__kfifo = &__tmp->kfifo; \
(__recsize) ?\
__kfifo_in_r(__kfifo, __buf, __n, __recsize) : \
__kfifo_in(__kfifo, __buf, __n); \
})
```
但其實 [include/linux/kfifo.h](https://github.com/torvalds/linux/blob/master/include/linux/kfifo.h#L541C9-L541C28) 也有提供 `kfifo_in_spinlocked()` 的操作，回想之前不用 lock 的原因是有些執行緒可能原先拿著lock，但在他還未釋放的時候被中斷了，導致其他執行緒還在等 unlock。而 kfifo 是因為 lock，才會讓它變比較慢，所以才會需要有 ring buffer 作為中介，讓很多執行緒並行事，然而就算他們並行取資料，放資料的時候還是因為 kfifo 的實作讓執行緒必須單一放資料。那這樣 ring buffer 就失去其原本要達成的效果了。就跟 main_thread 自己 produce data 後放到 kfifo 是一樣的。
#### Ring buffer 的存在意義:
ring buffer 在 Linux kernel 被廣泛應用，它的優點是固定空間。然而在 simrupt 中不一定要用 ring buffer。因為 ring buffer 在 simrupt 是作為中間者暫放資料再透過 worker 轉傳。因為 main thread 自己也可以直接將資料放到 kfifo。如果透過 worker 轉傳，效能同樣限制在 worker 放資料到 kfifo ，這是由於實作使得只能使單一執行緒放入資料。因此在 worker 與 ring buffer 的機制要在存取資料都要允許並行是 lock free 確保執行緒有進展才有用。
---
## 課程回顧
### 4/18
polymorphism操作是同一個動作。每一個裝置或 linux 模組只要註冊正確的操作就是多型。
ioctl
4KB trade off 不會很頻繁地做資料讀取，不用建一個很大的page，資料剛好塞進一個空間。從virtual machine 找到特定的page。
huge TLB 遇到某些情況，有一段空間可以直接對應到一大段空間。
虛擬記憶體page to 實體記憶體(多對一)。
mmap 是一個解法。
work steal 讓cpu 資源更好的分配。
userspace 到 kernelspace 成本 : mode switch 與 context switch。
TLB 本身就是 cache 要做flush(更新)資料內容。
多個系統呼叫拼成一個系統呼叫，就可以提升成本。
data hazard / ambiguous
現代的處理器要搭配現代編譯器才能解決問題。
### 4/23-25
printk 的時間戳記是紀錄時間點開始還是結束。
shannon entropy 應用在壓縮資料上面，在有很多的壓縮演算法上面，要挑出一個壓縮率最好的（能夠用較少的儲存空間表示壓縮前傳遞的資料），通常都要每一個壓縮演算法都壓縮過一次再來比較。然而透過先計算壓縮過後的資訊量也就是資料壓縮後的entropy。entropy 低代表壓縮品質好資訊量仍很高，entropy 高代表壓縮品質不好資訊量低。像是 Hamming code 就是一種壓縮方式。透過先計算（對數與除法的運算）則可以直接選擇要用哪個演算法。
資安問題 ： [LLL lattice basis reduction algorithm](https://blog.gslin.org/archives/2024/04/23/11752/lll-lattice-basis-reduction-algorithm/) 發現像是PRNG 製造隨機數會用到類似線性同餘器(LCG)週期的概念，也就是隨機數經過一個週期後又會重複，之所以會讓人難以察覺是因為週期很長，然而現在的攻擊可以不需要經過一個週期就能夠找到算隨機數的規律、 xz 被植入後門的事件發生在打包套件時的新的測試資料（埋在很深入的地方）為新的攻擊手法。像是當客戶在用Putty的時候可能是用以前的加密方式做 ssh 連線的。但如果沒有跟進防禦最新攻擊手法的方式，過往很好的加密方式可能仍不堪一擊。
[CSPNG](https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator) hash function 要快（在少的CPU cycle 下完成運算）同時又要達到 Uniform 不然會有資安問題。
TCP sequence number
file descriptor
hazard-pointer 可達到3 效果："lock free", 並行」 ,釋放記憶體時，thread 也可以讀。
```shell
$ numaclt -s
```
知道哪些cpu 是一組，migrate 就盡量是在同一個區域。
```shell
$ numaclt -h
```
schedule domain hierache
worker 數量要比 CPU 少，不然會需要 migrate 這會有代價。
一個 worker 負責一個連線
監控很多 skcket_data_t sd 就要設定
nfds 在何時被設定。
`while(!stop_received)` 是 `main loop` 所以大部分的時間都在這裡執行。
epoll wait 是 blocking 不然會得不到完整的清單。大部分的系統呼叫都是 blockng 。其中的 event trigger 與 level trigger 是從電子電路來的。 client-server 的架構中 server socket 要設定選項。http1.x is stateless，每一次的操作資訊要額外去描述，要先說資料有多長，資料的型態，資料的內容。不能把一些型態丟掉(向下相容)，增加檔案的型態就要增加分支。hash function + switch case 來查詢檔案回傳。用perfect hash function generator可以依據資料產生 hash function。Apple 的 webkit gperf，網頁有很多顏色對應到數值。如果沒有 hash function 就不是常數時間差詢，那網頁瀏覽器就會越來越慢。所以就將資料給 hash function generator 來產生 hash function 。
註冊 signal handler 。`SIGTERM/SIGINT` terminal process 舉例用 ctrl + C。 client 跟 server 會在網頁瀏覽器等到自己主動斷線，這是因為 http 是 stateless 。所以 server 要去關閉現有的連線。epoll 要依依處理找到有效的連線。
ftrace 可以動態追蹤作業系統的行為。
Greg KH 如何做 kernel debug。
workqueue, tasklet的程式要先去跑一次，從跑得動的程式去做實驗修改。kernel oops很多還能動，但功能不能執行。trace code 要有domain knowledge 才知道意義。debug 要知道 bug 在哪。
在 Unix 看 shebang 用哪個程式去執行。在 windows 看副檔名。擋掉 `/..` 避免駭客存取到某些檔案。資安問題
Gmail 網址一樣但大家開起來的畫面卻不一樣。URL rewriting。建一個狀態機用 session 去描述。
tasklet : deferred task(將一件事情交給別人作決定)可排序的task 。電位的變化連接到 ISR 要連動很多事情(軟體 wake up process，螢幕顯示要有內容 且 userspace 也要可以用)，因此不能只靠一個ISR，避免做這件事情被人打斷。所以趕快做的task 跟晚點做的task，晚點做的task 可以被排程。bh ISR soft, tasklet, CMWQ 要花比較多時間去執行，有可能會被中斷。每個kernel thread 不需要跟其他kernel trhead 同步 ksoftirqd 。tasklet 是 softirq的包裝。
Linux 以前支援 nested interrupt。現在不支援因為要支援狀態的一致很難。所以就放棄了。現在有 interrupt 就直接先回到原先的task，再到新的 interrupt。
### 4/30
推理在意 bandwidth。加速 AI 的推理，從 CPU 傳遞到 GPU 再傳遞到 CPU 希望一次傳遞的資訊量比較多。B16float不通用但運算量很大，但無法精準表達3.14。但可以應用在 AI 裡面。
補測試程式，因為像 linux 的排序就沒有測試程式。
確保在不同 CPU 。建構在 softirq 上。tasklet 畫棋盤要 A 跟 B 都下完才能畫。所以改成 CMWQ 讓 A 與 B 分別在各自的 CPU 上跑。但也可以將任務綁定在特定 CPU 上。
不要只有用 mutex lock 。 READ once 跟 WRITE once 是 volatile 會直接從記憶體讀取且是 sequential consistency。
Pipeline 跟 cache 。 cache miss 有代價。 cache snoop 遠大於乘/除法的成本。
CPU memory barrier。
降低 CPU 時脈。 CPU 時脈增加，需要解決散熱問題。 load 跟 store 分離，有對共享資源的控管用 memory barrier，kernel space 的時間比較敏感。
### 5/02
lvalue : resource allocator. 要操作記憶體的某個位址，就要用有型態的指標。
value of / address of.
記憶體位址 Memory Map I/O.
sig_atomic_t，註冊 alarm。
SPSC Single Producer Single Consumer。
P1, P2, P3 FIFO dmesg。
### 5/07
mode switch 花成本。
binary semaphore 可用 mutex (有 ownership，解決問題有適當的場景) 實作。semaphore (數學上 counter)
PI: priority inherence 要解決 priority inversionon。
在太空位元會反轉，訊號會變弱。
Low priority 被 Med priority 搶佔， High priority 就一直在等。Priority Inversion 的問題。最需要被防範的無止境的 Priority Inversion 。用 Priority Inheritance (PI) 去解決。持有 mutex lock 是低優先權的任務，就把低優先權任務的 mutex lock 移成高優先權。
mutex 有 ownership，lock unlock 需要 condition variable。喚醒重新排程。
acquire（獨占）跟 get（可以很多人都有）是不一樣。
spinlock 裝忙的原因是為了不要一直等待 invalid ack。
spinlock 不睡覺，mutexlock 可以睡覺就是可以排程，但是 Linux 不是這樣。RT preempt 提高 Linux 的效率，當即時處理是最重要的考量，讓所有任務都可以被搶佔，所以讓 spinlock 可以睡覺，高的可以搶佔低的。
CPU 在有 deadlock 的時候一直去搶 lock，有 progress 。
RCU 在讀取端是沒有 lock。
#### [第12週測驗題 : 測驗題二](https://hackmd.io/ptJEWCwDSpep58aH-TjJLA)
##### 問題 1 : `chan_recv_unbuf()` 函式目的?
```c=1
if (atomic_fetch_sub_explicit(&ch->send_ftx, 1, memory_order_acquire) ==
CHAN_WAITING)
futex_wake(&ch->send_ftx, 1);
} else {
if (atomic_fetch_add_explicit(&ch->recv_ftx, 1, memory_order_acquire) ==
CHAN_NOT_READY) {
do {
futex_wait(&ch->recv_ftx, CHAN_WAITING);
} while (atomic_load_explicit(
&ch->recv_ftx, memory_order_acquire) == CHAN_WAITING);
```
第 1 ~ 3 行:
接受者從 pipe 取走資料 `fetch_sub` 的過程 `CHAN_WAITING`。
因為還沒取完接受者要求傳送者 "Wait." 。
接受者取走完成後，喚醒傳送者去放資料。
第 5 ~ 10 行:
傳送者放資料入 pipe 中 `fetch_add` 的過程是 `CHAN_NOT_READY`。
因為還沒放完所以傳送者跟接受者說 "Not Ready." 。
傳送者放入完成後，等待接受者去取資料。
> 呼應程式碼的註解也更明白變數的命名由來
> /* For unbuffered channels, these futexes start from 1 (CHAN_NOT_READY).
* They are incremented to indicate that a thread is waiting.
* They are decremented to indicate that data exchange is done.
*
* For buffered channels, these futexes represent credits for a reader or
* write to retry receiving or sending.
*/
_Atomic uint32_t send_ftx, recv_ftx;
接受者收到一個傳送者的資料，就減少一個正在 wait 的 thread 也就是傳送者。
`atomic_fetch_sub_explicit(&ch->send_ftx, 1, memory_order_acquire)`
所以當接受者還沒拿完才會叫傳送者繼續 "Wait."
傳送者在放資料時，就會增加一個資料。
`atomic_fetch_add_explicit(&ch->recv_ftx, 1, memory_order_acquire)`
所以當資料還沒放好，傳送者就跟接受者說 "Not Ready."
##### 問題 2 : 取資料時先等待再喚醒 `futex_wake(&ch->send_ftx, 1);` 的原因?
```
-----------
sender -> pipe -> receiver
-----------
```
有兩個行程一個會扮演傳送者 (sender) ，另一個為接受者 (receiver)。傳送者確認傳送一個資料到 pipeline 後且 pipeline 的指標已經更新了(這件事情wait) ，確認完成後就喚醒接受者，讓接受者可以開始收資料了。
##### 問題 3 : 能否用來量測 context switch 的運作時間?
這件事情可以計算 context switch 的成本參考 [Arm-Linux](https://wiki.csie.ncku.edu.tw/embedded/arm-linux)。
隨著行程的數量增加，$\frac{time}{number\ of\ process}$ 會變小，這是因為 cache miss 就會變小。因為行程都已經到 cache 了，所以每次一個行程送完資料要切換到其他行程去接收資料時，因為 cache miss 降低，所以幾乎不用等其他行程進到 cache 裡面了，這個「變動的時間成本」會降低。所以當在最簡單的情況時，傳送者與接受者的數量比例接近，要在行程多的時候去統計測量「固定的時間成本」也就是 context switch 的成本會比較精準，不會將「會變動的時間成本」計算進來。這樣就減少不確定的因素發生的機率。
然後像是雲端與客戶端的比例不一樣的時候，就不能在統計測量的時候直接 $\frac{time}{number\ of\ process}$。因為這是當傳送者與接受者的數量接近 $number\ of\ process$。但雲端還有客戶端虛擬機器彼此間也會 context switch。
### 5/14
zstandard 壓縮。
hibernation image 開機就存在。F2FS 針對 flash
SAS single address space。沒有MMU與micro controller。
供電 1.8V boot loader。Linux 與 IOS 作業系統需要 3.3V 去啟動。
video ram 來做顯示，non-linear。 不連續是叫非線性。
有虛擬記憶體就從non-linear 記憶體變成 linear。
slob 針對多核處理器，小記憶體。
slab 對 cache 友善的記憶體配置，工作站
1991 Linux -> 2001 NPTL 多執行緒 -> 2004 dual 處理器。
memfd_create
UNIX : Everything is a file.
Linux : Everything is fd(file 檔案 descriptor 描述子)，所有 descriptor 都是數值(號碼牌)，不會有指標型態。文件是 document 。
Camera -> NPU 50 張挑出一張 前景與背景區隔。
I/O 排程器，CPU 排程器。
### 5/16
MQTT
雖然沒有 pthread 但還是多工，因為有 publisher 跟 subscriber
dmseg 是 ring buffer。
cpu sync printk_cpu_sync_try_get() reentrant lock。 reentrant mutex。
time_lock 有些lock 持有太久就直接解開。但這樣讓程式碼的行為不確定，執行不一定正確卻因為時間到了自動解開，而讓資源被釋放。 mutex 有不同情境，有ownership。mutex 是linux 預設的。
Publisher 先寫 `Msg:` 入 buffer。Subscriber 會印 Publisher 寫入的 `Msg:` 以及自己也會印出 `Msg:` 。因此會印 `Msg: Msg:` 會印。
Publisher 要明確共享記憶體的空間 (buf size 1MB),(msg size 1KB),(SPMS_RING_HEADER_LENGTH 128B)。實作細節用config就好。動態執行時去讀 config。
Subscriber只要去讀記憶體的空間，不需要知道 config。
因為 ring buffer 超過要取餘數。所以用 `＆ mask 2 的冪減一` 就可以達到取餘數的功能，所以用 2 的冪。ring buffer 在並行的程式很常見，給生產者消費者用 zero copy。
subscriber 只要知道 index 去讀資料就好。
slab buddy system.
[zero copy](https://hackmd.io/@sysprog/linux2020-zerocopy) : kernel 讀檔案傳到 socket。
linux shared memory 與 virtual memory 有很大的關聯。virtual memory 跟 virtual machine 建立關聯 [vosyshmem](http://www.virtualopensystems.com/en/products/vosyshmem-zerocopy/)。讀取資料也是成本，但是是在同一個 pysical page。memory copy 是 VM1 copy 資料到 VM2，因此要建立兩個記憶體空間。而 zero copy 是要求作業系統配置一個記憶體空間。
`_Alignof` C11 (大寫) 加入的 operator
`_Bool` C99 true false 是巨集定義的。
保證記憶體要做到 page-aligned。針對 page 虛擬記憶體最小的單元做alignment。`mem % alignof(max_align_t) != 0` 用到共享記憶體是多個行程互動。
等待的操作如何落實
```
A B C
acquire lock +- try lock +- try lock
|
XXXX
|
release lock
```
避免一直 try lock。所以要有通知。且由kernel 來通知。CPU scheduler 的責任。Publisher 寫完時要 wake ，跟別人說我寫完了。Subscriber 是想要讀資料，一直在 wait。futex_word 用 `*tail` 來識別 value reference。kernel 不會給地址，因為給address 也是給kernel space的address，linux 也不會將記憶體位址揭露。 `copy_to_user` 將kernel space 的東西移到user_space，因為kernel 不會把所有記憶體都跟 user 共用。除非是一個固定的空間。除非是 mmap 將記憶體映射過去 virtual address，這是zero copy，但每個process 看到的 virtual address 都不一樣。
`SHM_OPEN` POSIX 要求提供 return value 都是 file descriptor。
page-aligned 看系統目前設定的狀況 page 是 32K 或 64K。
reentrent lock: callback 不知道何時lock 就用recursive lock，但不要一直使用。 printk 不希望 ring buffer lock 很大影響效能，希望用 lock free()。non-block console，印出訊息的當下，也有新的訊息更新了。所以印出的時候是某個時間點以前的訊息。printk 以前是 blocking，因此有些地方不能用 printk。但現在希望做到 non-blocking。探討console 何時會被 lock。
要寫出有效率的程式是很困難的。
### 5/21
執行舊的軟體，用虛擬化。 ARM 如何作到虛擬化， VMM virtual machine monitor管不同執行的虛擬機器。guest 與 host 是相對。guest OS host OS 。彼此都有中斷系統呼叫都要處理，很快就遇到性能問題。CTSS 分時多工系統 1961 年。Multics 1965 年出現。
AWS EC2 : elastic compute 。
1. Full virtualization 完整的虛擬化：x86 ring 0 priviliedge 最高 可以執行virtual machine monitor。 TLB flash 模式切換 一整個狀態還原代價都很高。
2. Para Virtualization 一部分的虛擬化： 完整的系統性能會折損，Xen windows 執行在上面只有 3% 性能折損。如果沒有特別標 KVM 就會標 Xen。
3. Hardware Assisted Virtualization : KVM 2006 針對硬體的虛擬化，後來才出現。KVM 會成功跟 cloud computing 要如何知道付得錢多的人享有更多的資源。
AMD Intel Linux virtualization。
link register 做 function call。
SVC banked out 是會被屏蔽的。 FIQ 是快速中斷，很多暫存器都不能用。
HYP arm 處理器特別虛擬化的模式。硬體協助的虛擬化，用特定的路徑去優化。
硬體要將虛擬機器最後時間抽出來。
VMM at higher priviledge level than VMs 。
1. CPU virtualization
2. Memory virtualization
MMU
VM->IPA->PA
3. device virtualization 沒有硬體解法。
網路卡只有一張。
pkvm android 自己的虛擬機器。
android virtualization mechanism 。
需要有完整的虛擬化，可以隨著linux 改版就直接將 linux 升級上去。
第一代虛擬化 CPU virtualization 第二代虛擬化 Memory Virtualzation。
第三代虛擬化：兩個裝置都有音效卡，兩個裝置可以跑遊戲。
用host 端的網路來上網，有兩個 IP address。
Virt IO，針對虛擬機器的 IO 通訊。
手機支付 (生理資訊) 就存在 Third Privilege，不能被破解。但是開放的手機可以被破解。智慧裝置的挑戰。
big.Little big class 與 little class 切換中需要 migrate。
做手機升級不能打電話不能上網。一邊升級韌體，一邊維持基本功能就可以用虛擬化的技術。
### 5/28
zero-copy sockets
security enhanced linux
AF_UNIX
local communication
paradigm
iptables
pcb dump
SCU (Snoop Control Unit)
DMA (direct memory access)
GIC
mcs_spinlock
https://hackmd.io/@sysprog/linux-spinlock-scalability
### 6/04
kswap
PID=1 -> init
PID=0 -> 不能輕易被使用 scheduler (以前叫swapper)
scheduler 以前在 Unix 叫 swapper
Data Centor
chiplet AMD
多核處理器的設計 - Reduce Sharing
ccNUMA
RCU 在 linux 被發揚光大。
Fast path 一些 lock 可以不用用
Flex SC
Migrating Tasks 難度很高，不是排程，比 context switch 成本高很多。migrate 不能排程，搬家就是要等。把任務固定在特定 CPU 上 isolated CPU 。
fairness ， CFS load balancing 。 Schedule Domain
DVFS Dynamic Voltage and Frequency Scailing
CPU gate
為了雲端運算 : Group / Entity Hierarchy。
CPU bandwidth / quota
sre engineering
cycles per second
### 6/11
ticketless kernel. 週期不一樣。timer 10ms, 20ms
clock_get_time (micro second 的精度)
API 提供 nano second，但不一定保證做得到。
clock （時間有往前走）跟 timer（特化的 clock ）的差別。
clock monotonic 嚴格遞增，可以調整時間跟校正時間。（保證時間是精準）
系統很多還是 32 位元 API。所以不能直接改成 64 位元。
ARM IRQ FIQ
deterministic 不是小就好，要有預期。有時有 jitter 沒有 jitter。目標是可預測的。延遲對系統有不可預期的結果。消弭延遲。
real time 在意時限。
Non-Realtime Interrupts, bottom-half are threaded to reduce the duration of non preemptible.
https://eci.intel.com/docs/2.6/development/rt_scheduling.html
ksortirqd.
(kernel) soft 可排程。irq interrupt d
100% preemptible 中斷處理的前半段不能搶佔。
低優先權任務會被犧牲。
futex 避免優先權反轉。
RCU 同步處理機制。grace period (GP 寬限期)
RTOS 低延遲
co-kernel。針對兩套程式碼維護。要升級改版難度增加。
綠色是 userspace 才能搶佔，增加 preemtption points 就可以支援搶佔。mutex lock 不能加 preemption point。
Linux 是即時系統 soft real time 。
大部分的延遲在 5ms 下。
System on Chip，紙張無人機不被雷達偵測到。
Remote processor Messaging，系統重啟，一邊跑步一邊紀錄步數。
OpenAMP 跨越處理器間的通訊。google 也投入自駕車。
### 6/13
lock free 不代表沒有 lock。write 的時候也要其它lock 來實作。
ordinary compiler gcc / llvm
Cross compiler
stage 0 不會去讀 c.c 檔案。stage1 產生 "_syscall_" 字串。host 不會看這個檔案，而是給 target 看的，搭配 RISC-V ARM 去執行。
freelist
mmap2 想要自己去配置 page size。平常用 mmap。
要如何知道編譯器是否知道有最佳化的能力。只要是常數就會在編譯的時候就算好，觀察產生的 machine code。
SHA constant propagation / folding，根本不會產生程式碼。
單賦值，為了做constant propagation。x86 產生 arm 的執行檔。 arm 在產生 arm 的執行檔，兩個 arm 的執行檔要相同。
bitwise and : x 跟 y 都要evaluate。
logical and : 只要 x 是 false， y 不要 evaluate。
Redis 降低 database 的負擔。Redis 有 get 跟 set 大量操作。Redis in-memory cache，要去 dist 找。要低延遲。key-value store，hash map，透過 key 找到 value。get 跟 set 有很大比例差異。RCU 適合用在讀多寫少。
為什麼在 userspace 要有不同RCU 的 favor。希望可以執行在不同的作業系統上，linux 的 userspace 可能為不同的作業系統。
### 6/18
Preempt RT
spin lock 轉換成 mutex lock。polling prremtable。有些部份不能被搶佔 nodelay。半導體，沒辦法送真空管上去太空，太空帶動半導體產業的發展。
品質是價值跟尊嚴的起點
dual kernel
multi kernel 可執行多個作業系統
multi core
multi kernel 可執行在 multi core 上
memory barrier 的場景要能夠運行正確有很多複雜的例子。
Flagship Example : 會有重排因為兩個指令不相關，會重排。
```
CPU 0 CPU 1
A = 1 B = 1
X = B Y = A
```
instruction scheduling，現代編譯器。
data hazards。
[Memory Barriers in the Linux Kernel](https://elinux.org/images/a/ab/Bueso.pdf)
引入 memory consistency 。deterministic 事情的發生是可預期且必然發生的。
coherent : cache coherence ，每個 CPU 都有獨立的 L1 cache (獨自的電路) 就由 MESI 確保得到新的資料。存取 overall rationality（全貌）。發送 IPI 照著 MESI protocal。coherence 是對等的，比較窄的。
Most modern multicore systems are coherent but not consistent.
consistency : 文法時態要一致。database consistency，memory consistency。cache consistency，用在 I/O device driver。Economics Consistency, Data Flow consistency.
rob re-oder buffer out of memory : 指令重排會丟入一個 buffer，但把資料寫回去的時候是 in-order 否則結果會是錯的。
CPU is not aware if application is single or multi-threaded. When optimizing, it only ensures single threaded correctness.
(底限)Sequential Consistency
TSO total store order
x86 1986 intel 推出並叫 iA-32，但指令集非 intel 發明。
x86-64 AMD 發明執行在intel 處理器上。
裡面都 RISC 外面包一層 CISC 的皮。TSO 最低限度做到 reorder。
memory relaxation cpu，TSO 打開才能做 instruction reorder。
```
CPU 0 CPU 1
A = 1 B = 1
<MB> <MB> memory barrier /fence
X = B Y = A
```
看哪個等級 compiler barrier, memory barrier。
在 kernel 裡有 data dependency barrier。（Document)
在 x86 加個 lock 就可以變成 atomic。
implicit Barriers.
Scheduler function，排程幫你處理 barrier 的指令。
Locking functions.
kernel preemptive 的時候，也會加 barrier。
追求更高的性能，要加 barrier 去掉。
```shell
$ greb "mb("
```
Redis 是 baseline。
不能用 kernel 的 lock，架空 linux kernel。應用在更低成本部署 cache server 。
Paul 爺爺寫的 memory barrier
注重高性能的公司
應用在database 不能有大量的lock
寫 linux 的module lttng 寫程式要細緻
驗證程式碼的正確性。
linux kernel 很難驗證程式碼正確性。
DMA CPU 不要進去很慢的 IO ，裝置間只要失敗才會通知CPU，CPU 不介入。但還是要有人去更新 cache。 就是 ACP 。
RUST 程式語言一定要學 memory-safety security。
safety 預期是等於結果（必然）。安全帶，符合預期的保護。但不代表能夠保護不受傷。security 被動的，contract 該是如何存取就如何存取。Undefined Behavior 存在的意義是讓編譯器最佳化可以去執行。 A / B * B => A (編譯器原本膽小，害怕 B 為 0，且 * B 不會 overflow)。但這件事情 ( assume B != 0 )，GCC assume 5 / 2 * 2 (int)
patch __attribute__(assume bug)
java inner function， C 語言不能做，因為編譯器很難寫。
abort 是 library code，signal 觸發 abort。
UAF (use after free)
out of tree 在 nvidia open gpu kernel module
in tree 在 linux source code
ThisModuel 給 C 語言看的。
### 6/20
bitmap
viewport
render
clip region
沒有畫完，更新速度慢。 video ram 。可以跑在 linux frame buffer 上
scailing factor ，幾位是存小數， 32 位元定點數
```c
# if 0
n = 217
uint8_t x = 0111 1001 // 121
uint8_t D = 0000 0011 // 3
#define M((unit16_t)(UINT16_C(0xFFFF) / (D) + 1)) //65535 / 3 = 21845 = 21845+1 = 21846
=>
0x3FFF 某種 bit mask 值
unit8_t quotient = ((unit16_t) M *n) >> 8;
// 21846 * 217 = 4740582 >> 8 = 18517
```
Linux specialize
jemalloc meta 記憶體配置
malloc 記憶體配置
除法分不同的 bin (桶子)
jemalloc 做不同的設計，少不了有不一樣的 device 操作。
div_compute ，分區 slab 。
`regind = div_compute(div_info,diff);`
先把已經知道的數值計算出來。
不是為了取代除法，是為了特定的場景出現。
ops 的意義，今天要用哪一種手段。
short cut 知道要 shift = 42 U
A > 0 && A <= B
用 bitmask 來簡化操作
(x - minx) | (maxx - x) >= 0 互補
```ruby
/* Range check
* For any variable range checking:
* if (x >= minx && x <= maxx) ...
x < minx (X)
x > maxx (X)
* it is faster to use bit operation:
* if ((signed)((x - minx) | (maxx - x)) >= 0) ...
*/
```
ulog2 不是只是單純對數，建構新的 mask
範圍較大，跳過某些 bit，用一些手段。
隨時準備好給人家問問題。
sched_ext 對 linux 技術社群的影響？
-> Meta 得到的好處：azure k8s scheduler (Kube Scheduler)
-> Netflex 得到的好處：
（有沒有特化的需求）想要對於不同 workload 去調整，提出最適合自己的。
Meta 有 Database 的需求。
early Linux sched -> O(n) -> O(1) -> CFS -> EEVDF
microservice ， work load 特定的
一台伺服器通包（通用電腦） vs. 多台主機分工(microservice)。
多台主機有跑 Redis 或是 Database
Database 跟這個狀況不同。
為何引入機器學習對排程器有好處？
過去排程只看歷史紀錄 PELT EWMA (看太多反而排程成本提高），deterministic 行為
透過機器學習來 predict 任務的行為。
跑 Reddis，把排程的行為紀錄下來。overfit 是好事，因為可以跟據 task 的行為給它最好的 workload 。
如何蒐集到排程的時間， stress-ng，自己創造出不同 work load 。在極端情況下，才能發揮排程的表現。
測試在user space，不會破壞 kernel 。migration 是 schedulter 自己定的門檻。嘗試降低 migration 的數量，不能只看這個指標，要看有沒有善用硬體的資源。migration 次數最多，migration 更加保守，在這個情境下 locality 比 load balance 更加重要。
多核是很基本的配置，以前的東西很保守，避免顧此失彼，已經確定 workload ，就讓機器學習一直學習這些 pattern 。不僅可以預測，還可以蒐集資料，避免不必要的浪費在通用的情境。要配置怎樣的系統，怎樣的硬體來因應去調整。
---
### Bloom Filter
[第 10 週測驗題](https://hackmd.io/_JpNYTkkRXKBJmQBqowKaw) 與 [第 6 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz6)
Bloom Filter 為一種 Probability Data Structure。[HyperLogLog](https://en.wikipedia.org/wiki/HyperLogLog) 包含 Bloom filter 與 Skip List 。
一個陣列有 $m$ 個位元。每次加入一個鍵(key)時會計算 $K$ 個 hash function 。當插入 $N$ 個鍵後計算一個位元沒被設為 1 的機率。
原先，一個位元被設為 1 的機率 : $\frac{1}{m}$ 。
反之，一個位元沒被設為 1 的機率 : $1 - \frac{1}{m}$。
計算 $K$ 個 hash function 後，一個位元沒被設為 1 的機率 : $(1 - \frac{1}{m})^K$。
插入 $N$ 個鍵後，一個位元沒被設為 1 的機率 : $(1 - \frac{1}{m})^{K \times N}$
[Taylor series wikipedia](https://en.wikipedia.org/wiki/Taylor_series) : $e^x \approx 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\dots+\frac{x^n}{n!}$
而 $1+x \approx e^x$ 會在 $x \to 0$ 的時候越接近。
所以 bloom filter 做此近似的前提是已經假設 $m$ 很大了。因為只有在當 $m$ 大的時候 $x=-\frac{1}{m}$ 才會接近 0 符合 $x \to 0$ 的前提。
如此一來， $1-\frac{1}{m} \approx e^{-\frac{1}{m}}$ ，則不會有近似誤差太大。也因此當等號左右兩邊都做 $K \times N$ 的冪，也就是 $(1-\frac{1}{m})^{K \times N} \approx e^{-\frac{1}{m} \times K \times N}$ ，也不會有誤差太大的問題。
再插入 $N$ 個鍵後，再插入一個鍵後，而此鍵不存在在集合中，卻被視為存在的機率為 $((1 - \frac{1}{m})^{K \times N})^K$ 因為有 $K$ 個hash function 計算得到 $K$ 個 index。
將這個新的考慮也納入上面的近似數學式子裡面變成 : $((1-\frac{1}{m})^{K \times N })^K \approx (e^{-\frac{1}{m} \times K \times N})^K$
因為推算到 $((1 - \frac{1}{m})^{K \times N})^K$ 的前提為各 hash function 彼此為獨立事件。所以數學式(一) $\equiv$ 數學式(二)的前提： $A_{rr}[h_1(key)]$、$A_{rr}[h_2(key)]$、$\dots$、$A_{rr}[h_k(key)]$ 都為獨立事件。
(一) : $P(A_{rr}[h_1(key)]=A_{rr}[h_2(key)]=\dots=A_{rr}[h_k(key)]=1)$
(二) : $P(A_{rr}[h_1(key)]=1) \times P(A_{rr}[h_2(key)]=1) \times \dots \times P(A_{rr}[h_k(key)]=1)$
> 根據 **[COMPSCI 514: Algorithms for Data Science](https://people.cs.umass.edu/~cmusco/CS514F20/slides/lecture6/lecture6Compressed.pdf)**
> To avoid dependence issue, condition on the event that the A has t zeros in it after n insertions, for some t <= m.
也就是原本有 $m$ 個位元都為 $0$ ，插入 n 次鍵(key)後勢必有些位元被設為 $1$，而有些位元保留為 $0$ 的數量為 $t$。因此 $t<=m$。
這句話目前看起來沒有任何資訊。只是新增了一個變數 $t$ 使其表示為插入 n 次鍵(key)後剩餘有多少位元仍保留為 $0$。接下來這一段話用到變數 $t$
> Conditioned on this event, for any $j$, since $h_j$ is a fully random hash function, $P(A_{rr}[h_1(key)]=1) = \frac{t}{m}$.
但這句話寫錯應該要是 $P(A_{rr}[h_1(key)]=0) = \frac{t}{m}$。
接下來要來算 false positive 「不存在卻被視為存在的機率」，其實就是計算一個鍵經過 $K$ 個 hash fucntion 後得到的陣列的 index 其值都為 1 的機率: $(1-\frac{t}{m})^k$，從此看出上面真的寫錯了。因此現在 false positive 有兩個算法，第一個為錯的，第二個為對的。
(一)、$((1-\frac{1}{m})^{K \times N })^K \approx (e^{-\frac{1}{m} \times K \times N})^K$ 錯的
(二)、$(1-\frac{t}{m})^K$ 對的
插入 $N$ 個鍵後，一個位元沒被設為 1 的機率 : $(1 - \frac{1}{m})^{K \times N}\approx e^{-\frac{1}{m} \times K \times N}$
接下來計算一個位元未被設為 1 的期望值 $E[\frac{t}{m}] = \frac{1}{m}\Sigma^{m}_{i=1}P(A[i] = 0) \approx e^{\frac{-kn}{m}}$
因此 false positive rate : $(1-\frac{t}{m})^K \approx (1 - e^{\frac{-kn}{m}})^k$ 才是正確的。接下來要找 $(1 - e^{\frac{-kn}{m}})^k$ 的最小值。參考 [bloom_filters_pub](https://www.cs.jhu.edu/~langmea/resources/lecture_notes/115_bloom_filters_pub.pdf)
$\frac{d}{d\ k}(1 - e^{\frac{-nk}{m}})^k = \frac{d}{d\ k}e^{ln((1 - e^{\frac{-nk}{m}})^k)}=\frac{d}{d\ ln((1 - e^{\frac{-nk}{m}})^k)}e^{ln((1 - e^{\frac{-nk}{m}})^k)} \times \frac{d\ ln((1 - e^{\frac{-nk}{m}})^k)}{d\ k}$
$=e^{ln((1 - e^{\frac{-nk}{m}})^k)} \times \frac{d\ ln((1 - e^{\frac{-nk}{m}})^k)}{d\ k}$
所以接下來算 $\frac{d\ ln((1 - e^{\frac{-nk}{m}})^k)}{d\ k}$ 的最小值。$\frac{d\ (k \times ln(1 - e^{\frac{-nk}{m}}))}{d\ k}$
$=(ln(1 - e^{\frac{-nk}{m}})) +(k \times \frac{d\ ln(1 - e^{\frac{-nk}{m}})}{d\ k})$
個別計算 : $\frac{d\ ln(1 - e^{\frac{-nk}{m}})}{d\ k} = \frac{d\ ln(1 - e^{\frac{-nk}{m}})}{d\ (1 - e^{\frac{-nk}{m}})} \times \frac{d\ (1 - e^{\frac{-nk}{m}})}{d\ k}$
$= \frac{1}{(1 - e^{\frac{-nk}{m}})} \times \frac{d\ -e^{\frac{-nk}{m}}}{d\ \frac{-nk}{m}}\times \frac{d\ \frac{-nk}{m}}{d\ k}=\frac{1}{(1 - e^{\frac{-nk}{m}})} \times e^{\frac{-nk}{m}} \times \frac{n}{m}$
因此 $=ln(1 - e^{\frac{-nk}{m}}) +(k \times \frac{d\ ln(1 - e^{\frac{-nk}{m}})}{d\ k}) =(ln(1 - e^{\frac{-nk}{m}})) + (\frac{k}{(1 - e^{\frac{-nk}{m}})} \times e^{\frac{-nk}{m}} \times \frac{n}{m})$
當 $k = ln2 \frac{m}{n}$ 上面的微分為 0 。但是看到這個數學式子還是很難直接推到 $k = ln2 \frac{m}{n}$，所以接下來會一直將變數簡化來看。
$ln(1 - e^{\frac{-nk}{m}}) + (\frac{k}{(1 - e^{\frac{-nk}{m}})} \times e^{\frac{-nk}{m}} \times \frac{n}{m})=0$
將 $\frac{nk}{m}$ 先換作 $x$ ，變成下面這個式子
$\to ln(1 - e^{-x}) + (\frac{1}{(1 - e^{-x})} \times e^{-x} \times {x})=0$
$\to ln(1 - e^{-x}) = (\frac{1}{(1 - e^{-x})} \times e^{-x} \times {-x})$
$\to ln(1 - e^{-x}) = (\frac{1}{(1 - e^{-x})} \times e^{-x} \times ln(e^{-x}))$
$\to (1 - e^{-x})\ ln(1 - e^{-x}) = e^{-x} \ ln(e^{-x})$
$\to ln(1 - e^{-x})^{1 - e^{-x}} = ln(e^{-x})^{e^{-x}}$
$\to(1 - e^{-x})^{1 - e^{-x}} = (e^{-x})^{e^{-x}}$
將 $e^{-x}$ 先換作 $a$ ，變成下面這個式子
$\to(1 - a)^{1 - a} = a^a \to a = \frac{1}{2} \to e^{-x} = \frac{1}{2} \to x=ln(2) \to \frac{nk}{m} = ln(2)$
#### [kernel/bpf/bloom_filter.c](https://github.com/torvalds/linux/blob/9d1ddab261f3e2af7c384dc02238784ce0cf9f98/kernel/bpf/bloom_filter.c#L15) 中的 bloom filter
> For the bloom filter, the optimal bit array size that minimizes the
false positive probability is n * k / ln(2) where n is the number of
expected entries in the bloom filter and k is the number of hash
functions. We use 7 / 5 to approximate 1 / ln(2). 這裡是因為定點數不用浮點數。
Linux 預設 hash function 數量為 5 ， $K = 5$ 。 $n$ 為插入幾次鍵值。 $m$ : the optimal bit array size 。
而 Linux 的目標是找到在有 $K$ 個 hash function 下，插入 $n$ 次鍵值後需要多少個位元才能讓 false positive probability 最小，因此 $\frac{nk}{m} = ln(2) \to m = \frac{nk}{ln(2)}$
因此下方這段 [kernel/bpf/bloom_filter#L127](https://github.com/torvalds/linux/blob/9d1ddab261f3e2af7c384dc02238784ce0cf9f98/kernel/bpf/bloom_filter.c#L127) 程式碼目的是在當 `n = max_entries` 在插入達到鍵值的次數達到上限時，且有 `K = nr_hash_funcs` 個 hash function 下，需要多少個位元數。三個因素相互影響。
```c
if (check_mul_overflow(attr->max_entries, nr_hash_funcs, &nr_bits) ||
check_mul_overflow(nr_bits / 5, (u32)7, &nr_bits) ||
nr_bits > (1UL << 31)) {
/* The bit array size is 2^32 bits but to avoid overflowing the
* u32, we use U32_MAX, which will round up to the equivalent
* number of bytes
*/
bitset_bytes = BITS_TO_BYTES(U32_MAX);
bitset_mask = U32_MAX;
} else {
if (nr_bits <= BITS_PER_LONG)
nr_bits = BITS_PER_LONG;
else
nr_bits = roundup_pow_of_two(nr_bits);
bitset_bytes = BITS_TO_BYTES(nr_bits);
bitset_mask = nr_bits - 1;
}
```
而在配置 bloom filter 的需要用到的位元數的時候，`attr` 變數可以調整最大的插入次數以及 hash function的數量。如果計算出來的 bloom filter 需要的位元數大過 2^32 bits 則用 2^32 bits。然而由「最多插入次數」以及「hash function 的數量」計算最佳的「位元數量」來降低 false positive probability 只是 bloom filter 的第一個要考量。這三個因素的關係不只透過 $m = \frac{nk}{ln(2)}$ 這個數學式子相互影響。還有 hash function 要如何設計才能避免 collision 。雖然降低 false positive probability 降低碰撞的問題。
但是上面的前提 $P(A_{rr}[h_1(key)]=1) \times P(A_{rr}[h_2(key)]=1) \times \dots \times P(A_{rr}[h_k(key)]=1)$ 讓彼此為獨立事件就是關係到 hash function 如何設計。而之所以得到前面的數學式子也是透過期望值，統計得到的。所以回到最一開始的問題就是要讓 hash function 產生的能夠達到 Uniform distribution 也就是 entropy 高，不然根本沒辦法用統計得到期望值。而 hash function 要 Uniform distribution 此事情跟位元的數量有關係。[測驗題的程式碼](https://gist.github.com/jserv/f8faef1dc23ed88f33f72a225271bf5e#file-bloom-c-L59)可以看到一個鍵會設定位元兩次，卻只用一個 hash fucntion， $P(A_{rr}[high\ part\ of\ hash(key)])$ 與 $P(A_{rr}[low\ part\ of\ hash(key)])$，來達成有兩個 hash function 的效果增加 $K=2$ 的數量。
原先 [xxhash](https://github.com/Cyan4973/xxHash/blob/dev/xxhash.h) 的 XXH3_64bits 函式提供的 high entropy 的特性(達到 SOTA )是讓不同鍵 (key) 產生的結果是 Uniform distribution 這個目的是為了要減少不同鍵值經由 hash function 能產生一樣的結果的機率。
但是上面算偽陽性的數學式子前提是讓不同的hash function 彼此事件獨立。測驗題中「不同的 hash function 計算鍵 (key) 產生結果」是用「同個 hash function 產生結果取上半部 $P(A_{rr}[high\ part\ of\ hash(key)])$ 與下半部 $P(A_{rr}[low\ part\ of\ hash(key)])$」來做，那這樣$P(A_{rr}[h_1(key)]=1)$ $P(A_{rr}[h_2(key)]=1)$則沒有事件獨立，因此 false positive 的機率就不能用上面的數學式子期望值的方式去計算。
從而也說明 「hash function 如何設計以減少collision」以及 「hash function 彼此如何事件獨立」也跟 false positive 的機率有關係。false positive 的機率並不只被三個「最多插入次數」、「hash function 的數量」、「位元數量」所影響。
補充說明 hash function 有兩個特質像是要 Uniform distribution 或是很快也就是在 CPU cycle 少的情況下計算完。然而當要考慮資安問題的時候通常是要計算一個特定的值出來，像是 lab-0 中要計算出隨機的數，這是一個數值，所以駭客可以通過這些明確的數字預測做出攻擊。而在 Bloom Filter 中其實更在乎的是是否有快，因為它可能會被用來判斷檔案系統是否有檔案存在，而因為 Probability Data Structure，它給的是一個機率不是一個數值，所以這裡就不用考慮資安問題。
#### Kernel 的 Bloom Filter
在 kernel 中 [kernel/bpf/bloom_filter.c](https://github.com/torvalds/linux/blob/master/kernel/bpf/bloom_filter.c) 中 `bloom_map_peek_elem()` 與 `bloom_map_push_elem()` 會分別用 `hash()` 計算的值去 `set_bit()` 以及`test_bit()`。
```c
static long bloom_map_peek_elem(struct bpf_map *map, void *value)
{
struct bpf_bloom_filter *bloom =
container_of(map, struct bpf_bloom_filter, map);
u32 i, h;
for (i = 0; i < bloom->nr_hash_funcs; i++) {
h = hash(bloom, value, map->value_size, i);
if (!test_bit(h, bloom->bitset))
return -ENOENT;
}
return 0;
}
```
```c
static long bloom_map_push_elem(struct bpf_map *map, void *value, u64 flags)
{
struct bpf_bloom_filter *bloom =
container_of(map, struct bpf_bloom_filter, map);
u32 i, h;
if (flags != BPF_ANY)
return -EINVAL;
for (i = 0; i < bloom->nr_hash_funcs; i++) {
h = hash(bloom, value, map->value_size, i);
set_bit(h, bloom->bitset);
}
return 0;
}
```
其中用的 `hash()` 函式來自 [include/linux/jhash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/jhash.h) 的 jhash 函式。
這裡有錯字 `arbitray -> arbitrary`
```c
/* jhash - hash an arbitrary key
* @k: sequence of bytes as key
* @length: the length of the key
* @initval: the previous hash, or an arbitray value
*
* The generic version, hashes an arbitrary sequence of bytes.
* No alignment or length assumptions are made about the input key.
*
* Returns the hash value of the key. The result depends on endianness.
*/
static inline u32 jhash(const void *key, u32 length, u32 initval)
{
u32 a, b, c;
const u8 *k = key;
/* Set up the internal state */
a = b = c = JHASH_INITVAL + length + initval;
/* All but the last block: affect some 32 bits of (a,b,c) */
while (length > 12) {
a += __get_unaligned_cpu32(k);
b += __get_unaligned_cpu32(k + 4);
c += __get_unaligned_cpu32(k + 8);
__jhash_mix(a, b, c);
length -= 12;
k += 12;
}
/* Last block: affect all 32 bits of (c) */
/* All the case statements fall through */
switch (length) {
case 12: c += (u32)k[11]<<24;
case 11: c += (u32)k[10]<<16;
case 10: c += (u32)k[9]<<8;
case 9: c += k[8];
case 8: b += (u32)k[7]<<24;
case 7: b += (u32)k[6]<<16;
case 6: b += (u32)k[5]<<8;
case 5: b += k[4];
case 4: a += (u32)k[3]<<24;
case 3: a += (u32)k[2]<<16;
case 2: a += (u32)k[1]<<8;
case 1: a += k[0];
__jhash_final(a, b, c);
case 0: /* Nothing left to add */
break;
}
return c;
}
```
為了理解這些數字怎麼來的，我就去看了 [burtleburtle 的 hash 網頁](https://burtleburtle.net/bob/hash/) ，其中提到他選擇這些常數來自用他寫的程式碼 [avalanche](https://burtleburtle.net/bob/hash/avalanche.html) 算出來最好的。
##### [論文閱讀-Hash Functions for Hash Table Lookup](http://burtleburtle.net/bob/hash/evahash.html)
> if a hash function maps 30-byte keys into a 32-bit output, it maps $2^{8\times 30}$ possible keys into $2^{32}$ possible hash values. Less than $2^{32}$ actual keys will be used. With a ratio of $2^{8\times 30-32}=2^{208}$ possible keys per hash value, it is impossible to guarantee that the actual keys will have no collisions.
> If the actual keys being hashed were uniformly distributed, selecting the first v bits of the input to be the v-bit hash value would make a wonderful hash function. It is fast and it hashes an equal number of possible keys to each hash value. Unfortunately, the actual keys supplied by humans and computers are seldom uniformly distributed. Hash functions must be more clever than that.
##### Funneling
$K$ keys 是一個集合裡面的值都為 k-bits ，且有 $V$ (hash values) 是一個集合裡面的值都為 v-bit。hash function $h : K \to V$。然後在$1 \to k$ 中第 $i$ 個位元會影響 $1 \to v$ 中第 $j$ 個位元。因此變化第 $i$ 個位元會變化 $50%$ 的機率會影響 $1 \to v$ 中第 $j$ 個位元。
### RCU 同步機制
lock free 是 lock 跟 lock 之間不會競爭。仍然有 lock。
$\frac{N}{1+\alpha(N-1)+\beta N(N-1)}$ $\alpha$ : 資源搶奪 $\beta$ :等待共享資源
資料如何存是用 snapshop 存，資料需要很長時間去 warm up 。
http://opic.rocks/
https://backendless.com/redis-what-it-is-what-it-does-and-why-you-should-care/
### [並行程式設計: Lock-Free Programming](https://hackmd.io/@sysprog/concurrency-lockfree)
> Lock-Free 要求整個程式都是 lock-free 是極為困難的，通常 lock-free 會應用在一些特定的資料結構上，例如為 lock-free queue 實作 lock-free 版本的 push, pop, isEmpty 等。
> lock-free 不代表沒有 lock，lock-free 的意義是 lock 間不會使程式碼沒有進度。
> lockless 沒有 lock，但不代表程式碼就一定有進度。
lock-free 為何會有[Memory Reordering](https://preshing.com/20120625/memory-ordering-at-compile-time/) 的問題？首先 lock 的用途是為了不要讓多個執行緒修改同一個資料。所以會要考慮 lock-free 是在 lock 應用在多個執行緒下面，仍然可以有進度。重新看下面這個圖表，所以 lock_free 要做到多個執行緒共享資料還是需要 lock。
```graphviz
digraph structs {
rankdir = LR
node[shape=plaintext];
process [fontcolor="black"];
node[shape=box];
multi_thread
shared_data[label="shared_data need lock"]
progress
lock_less
{
process -> multi_thread
multi_thread-> shared_data
shared_data-> progress
progress -> lock_less
}
}
```
而 Memory Reordering 分為以下二個：
一、Compiler Reordering :
發生在編譯器最佳化時產生。
解決 Compiler Reordering 有 2 個方法 :
(1)：Compiler Barrier 的指令 `asm volatile("" ::: "memory");`
(2)：C++ 的 atmoic 操作也是一個 Compiler Barrier 。這兩個方法可以避免在單一 Thread 發生 Memory Reordering。所以從這裡就知道跟 lock-free 的應用場景沒有關係。因為 Compiler Reordering 跟程式為單或多執行緒執行沒有關係。
```c
asm volatile("" ::: "memory"); // prevent compiler ordering
```
二、CPU Reordering :
發生在 $(a)$ lock-free 的程式在 $(b)$ 多核且 $(c)$ 不保證 sequential consistency。
解決 CPU Reordering 有 2 個方法:
(1)：讓二個 Thread 在同一個 CPU 下運行。
(2)：使用 CPU 的 memory barrier 。
```c
asm volatile("mfence" ::: "memory"); // prevent CPU ordering
```
Memory Reordering 根據 [memory-reordering-caught-in-the-act](https://preshing.com/20120515/memory-reordering-caught-in-the-act/) 是源自於 processor 可以將 load 與 store 的指令延後執行。延後執行有兩個原因：
**原因(1)** 一個 Processor 將自己的指令 reorder
> Intel x86/64 processors, like most processor families, are allowed to reorder the memory interactions of machine instructions according to certain rules, as long it never changes the execution of a single-threaded program.
```
int x =0,y =0;
(case1) (case2)
Processor1 |Processor2 Processor1 |Processor2
mov [x],1 |mov [y],1 --> mov r1,[y] |mov r2,[x]
mov r1,[y] |mov r2,[x] mov [x],1 |mov [y],1
```
case1 $\to$ case2：
如果每個 processor 都將前後指令顛倒順序，結果 `r1 == 0 && r2 == 0`。執行錯誤。
case1 $\to$ case2：
而一個執行緒在執行的時後仍要避免指令 reorder 因為為了 $(c)$ 保證 sequential，所以還要在 critical section 裡面加上 Compiler Barrier 的指令 `asm volatile("" ::: "memory");` 。
**原因(2)**
> 多個 Processor 傳輸指令的時間點不一樣。讓各自的指令交錯。
> 參考 〈[並行程式設計: Atomics 操作 cache-coherence-對程式效能的衝擊](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-atomics#cache-coherence-%E5%B0%8D%E7%A8%8B%E5%BC%8F%E6%95%88%E8%83%BD%E7%9A%84%E8%A1%9D%E6%93%8A)〉。
> x86 和 Arm 處理器中均引入 Non-Temporal 的載入和儲存操作，這些操作不會經由 cache，而是直接針對外部記憶體控制器進行存取。而它們的存取順序就是典型的 weak memory order，因為即便在匯流排上，都會有各種不同情況發生。所以在匯流排上面傳送的指令並非哪個指令先開始傳輸就會最先開始被執行。
而在第一個原因 CPU reorder 是因為在一個 Thread 執行下結果正確，就算 reorder 指令並不影響結果，但如果在多個 Thread 交錯執行時，則可能結果不正確。所以這裡說明滿足$(b)$ 多核且 $(c)$ 不保證 sequential 。然後$(a)$ lock-free 舉個例子說明。
```
int x =0,y =0;
(case1) (case3)
Processor1 |Processor2 Processor1 |Processor2
mov [x],1 |mov [y],1 --> load x |load x
mov r1,[y] |mov r2,[x] load y |load y
write x |write y
mov r1,[y]|mov r2,[x]
```
case1 $\to$ case3：
因為執行 `mov r1,[y]` `mov r2,[x]` 的時候用的 `[x]` 與 `[y]` 是之前load 的。要預防這件事情的話，就要用 Store Load : 所有寫入的指令都會在 memory barrier 前面執行完，而讀取的指令會在 memory barrier 後面做。因為最基本的規則是 "never modify the behavior of a single-threaded program"。也就是 store 跟 load 的指令不能交換執行順序都為：`STORE_{t1}` `STORE_{t2}` `barrier` `WRITE_{t2}` `WRITE_{t1}`。
而這件事情應用在 case 3 會變成執行 `mov r2,[x]` `mov r1,[y]` 也就是 Load `[x]` 與 `[y]` 一定要再 `write x` 與 `write y` 之後。也就是 Store 跟 Load 間有一個 barrier，讓 Load 的時候一定看得到所有最新的值。然而這件事情在單執行緒的時候只要確保不要有 compiler reorder 用 一個 Barrier就好，但在多執行緒要建立兩個執行緒間共同的 barrier 卻很困難。
**方法(2)**：在下面的[程式碼](https://github.com/shishougang/blog_multithreading/blob/master/memory_reordering/memory_reordering.cc) `asm volatile("mfence" ::: "memory");` 防止 CPU reordering ，也就是防止原因 2 的發生。如果沒有的話在我的電腦 100個 interation 至少會出現一個。
```c
void *ThreadFunc1(void *param) {
MersenneTwister random(1);
for (;;) {
sem_wait(&begin_sem1);
// random delay
while (random.Integer() % 8 != 0) {
}
X = 1;
#if USE_CPU_FENCE
asm volatile("mfence" ::: "memory"); // prevent CPU ordering
#else
asm volatile("" ::: "memory"); // prevent compiler ordering
#endif
r1 = Y;
sem_post(&end_sem);
}
return NULL;
}
```
**方法(1)**：限制在 CPU 0。我原本是用命令 `taskset -cp 0 15694` 將正在執行的程式移到 CPU 0。但這件事將行程限制在 CPU 0上。兩個執行緒還是在不同的 CPU 上執行，導致仍會有 Memory Redorder，沒辦法連同行程一起搬遷，所以改為從一開始行程與執行緒都在 CPU 0 執行。
```shell
$ taskset 0x1 ./memory_reordering
```
想到這裡我才想通，像是 `asm volatile("" ::: "memory"); // prevent compiler ordering` 因為在一個程式碼轉指令到真正執行，都是循序的，所以可以只要 compiler 能確定執行順序的正確性，執行也會是正確的，也就是會在 Load 前做完所有 Store 。
然而在多個執行緒下面，每個程式碼即便compiler 能確定執行的順序，到pipleline，因為多個執行緒傳輸指令的時間不同，所以並無法保證，多個執行緒的執行部會交錯，因此才要用 `asm volatile("mfence" ::: "memory"); // prevent CPU ordering`。
對照 「CPU Reordering 是發生在 $(a)$ lock-free 的程式在 $(b)$ 多核且 $(c)$ 不保證 sequential consistency。」把這句話想成沒有 lock ，像是lock-free 的 [Ring buffer](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-ringbuffer)，就沒有 lock 。
「如果程式並非 lock-free（應該為 lock-less，也就是程式有 lock），那 critical section 的指令會因為有 lock 而被 block 住，也保證了執行的正確性」。這跟 lock 有關係的原因是 lock 就是一個 memory barrier 放在對的位置程式就可以被 blcok 住，每次只讓一個執行緒執行，就可以避免 Reordering。
而 CPU reorder 有兩個一個是多個 CPU 將指令寫入匯流排的時候交錯，另一個可能從 CPU 有 `asm volatile("mfence" ::: "memory"); // prevent CPU ordering` 這件事情思考，這一行是會給 CPU instruction scheduler 去做 memory barrier。但在 local instruction scheduler 的時候只是將 `asm volatile("mfence" ::: "memory");` 指令寫入，到 global instruction scheduler 的時候才會排。
cache coherence 是確保 cache 的資料一致並沒有同步，同步是有快的 CPU 會停下來等慢的，快的 CPU 的效能會被犧牲，也因此同步的代價很大。但是一致是一直更新，這也是為何單個 CPU 的 local instruction scheduler 也會自己 reorder，因為它要讓資料一致，同時維持效能，那就是持續執行指令，不過把跟 cache 的資料無關的指令先做，跟 cache 的資料有關的等每個 CPU 的 cache 資料一致再做，這就是 reorder。
> Release semantics : 在 write 前的指令不能重排。
#### 整理 mutex 與 lock 與 atomic 的關係
mutex (一個lock) 保證 (1)lock 的運作是可行的，(2)只有一個執行緒或行程在一個時間執行 critical section 中的操作與 (3) 通知其他執行緒或行程 wake 的機制也可行。mutex 的優點是寫法很簡單。mutex 的操作也會包含 atomic，只是 mutex 會要保證更大的範圍。而 semaphore 跟 mutex 的 wake 機制可能不同。同時 lock 形式也不同，semaphore 是一個計數器。
atomic 是由幾個操作去實現「檢查一個變數的值，並改變變數的值」。除了實現這個功能外，atomic 確保這幾個操作是一體的，只有「完成變數的值」以及「像是沒做任何事情，不改變變數的值」兩種可能。
lock free 用迴圈去實現一個目的 : atomic 操作即便失敗，也會再次嘗試直到有進展。
因為一個執行緒或行程在 atomic 的操作失敗，代表有一個執行緒或行程已經成功了。這樣的機制確保是有進展的。
用塞車的方式比較好想像 :
mutex 是確保一個路口相當於 critical section，這時候車子就是依據紅綠燈的規則，需要等紅燈的車子就是在等 lock，等到綠燈的車子就像是被 wake。而紅綠燈也需要被規範，像是不同方向的紅綠燈都亮綠色。所以像是紅綠燈這個 lock 要用一個最小的東西 atomic 的機制去規範。因為紅綠燈的顏色被改變的過程要是一體的。像是當黃燈在路口的車子如果還沒離開，燈突然變紅色，就容易與不同方向的綠燈行車子撞到。
lock free 的例子就是塞車的時候，很多車子都會擠在路上，但塞車總有一台車子會移動，當他一移動，最接近他的車子，或是最快發現那裏有空位的車子就會擠進去。
雖然 mutex 會讓一些行程或執行緒原本拿著 lock，因故發生而沒有釋放造成沒有用的等候，除非有系統管理者介入。會讓我想把所有的 mutex 都改成 lock free。有些情況用 mutex 跟用 lock free 都沒有差別，所以會用簡單實作的 mutex 。但像是會影響效能的
像是 printk 就在討論要不要改成 lock free。
https://lpc.events/event/4/contributions/290/attachments/276/463/lpc2019_jogness_printk.pdf
### False Sharing
```diff
struct atomic_float {
volatile atomic_flag flag;
- int padding; /* avoid false sharing */
alignas(16) float value;
};
```
`printBinary(&x);`
```diff
_1101_0000_1000_1101_1100_0000_0100_0000_1101_0000_1000_1101_1100_0000_0100_0000
_1101_0000_1000_1101_1100_0000_0100_0100_1101_0000_1000_1101_1100_0000_0100_0100
_1101_0000_1000_1101_1100_0000_0101_0000_1101_0000_1000_1101_1100_0000_0101_0000
```
以下印出地址的 16 進位。
```
the atomic_float_obj.flag address =0x55e2d08dc040
the atomic_float_obj.padding address =0x55e2d08dc044
the atomic_float_obj.value address =0x55e2d08dc050
```
alignment 的作用是讓最後 4 個位元為 `0000` ，但如果是 padding 的話最後 1 個位元不為 `0`。代表處理這個值，需要 combine 。
:::info
〈[你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)〉提到 struct 會自動做 alignment，這裡卻沒有做，因為最後 1 個位元不為 `0`。
:::
避免 false sharing 目的是要讓兩個變數他們可能會被不同 cache line 存取，為了避免為了 cache 的一致性而頻繁更新。所以讓這兩個變數在不同的位元組，上面的例子就算有沒有拿掉 padding 都沒有差別。其可能原因一：64 位元電腦 cache line 一次讀 64 個位元，這裡的 padding 太小了，沒有辦法將 value 的起始位址放到下一個位元組。原因二：執行的次數太少次了，不是每一次都一定會出現剛好兩個起始位址在同一個位元組。
### [MESI protocol](https://hackmd.io/@sysprog/concurrency-atomics#MESI-protocol)
原先看到 MESI 的 For any given pair of caches, the permitted states of a given cache line are as follows:
| | M | E | S | I |
| - | - | - | - | - |
| M | X | X | X | V |
| E | X | X | X | V |
| S | X | X | V | V |
| I | V | V | V | V |
無法理解縱軸與橫軸之間的關係，我推斷是在說兩個 cache 的相對關係，相對關係包含兩個 Cache$_0$ Cache$_1$ 是否可以允許對方的 Bus request 。此 Bus 是來自其它 Cache ，不是來自自己的 CPU 。 Bus 有二種功能：
> BusRead: Snooped request that indicates there is a read request to a Cache block requested by another processor.
> BusWrite: 包含 cache 收到 bus 需要它的資料的所有相關操作，例如需要這份資料傳遞資料的分式要寫回主記憶體，或是在 cache bus 傳遞。
縱軸為 Cache$_0$ 的狀態，橫軸為 Cache$_1$ 的狀態。
當 Cache$_0$ (狀態 I)，就可接受 Cache$_1$ (可為任何狀態) 來的 BusRead 或 BusWrite。
當 Cache$_1$ (狀態 M 或 I) 想更新 Invalid 的資料，Cache$_0$ (狀態 I) 就要接受 BusWrite 。
當 Cache$_1$ (可為任何狀態)，可接受Cache$_0$ (狀態 I) 來的 BusRead。
當 Cache$_0$ (狀態 S)，根據(狀態 S)的定義：[MESI wikipedia](https://en.wikipedia.org/wiki/MESI_protocol)
> Indicates that this cache line may be stored in other caches of the machine and is clean - it matches the main memory. The line may be discarded (changed to the Invalid state) at any time.
所以當 Cache$_0$ 對 Cache$_1$ 而言是 (狀態 S)，則 Cache$_0$ 與 Cache$_1$ 與 main memory 的資料一致。則 Cache$_1$ 對 Cache$_0$ 也一定為 (狀態 S)。那這樣資料一致無論是 BusRead 或 BusWrite 都沒有影響。BusWrite 的情況發生在 Cache$_0$ 發廣播跟所有 Cache 說要 Write 新資料時，Cache$_1$ 就算跟 Cache$_0$ 一樣也收到 BusWrite。
到此說明完 Cache$_0$ 與 Cache$_1$ 為 (狀態 S,I) 的關係了。接下來說明左上角四個 (X)
根據定義：[MESI wikipedia](https://en.wikipedia.org/wiki/MESI_protocol)，因此兩個 Cache 不可能彼此為 (M) 或 (E) 。
> Modified (M) : The cache line is present only in the current cache, and is dirty
> Exclusive (E) : The cache line is present only in the current cache
Cache$_0$ Cache$_1$ 不可能在同一份資料上彼此互為 (狀態 M, E)，這個關係不存在。
雖然後來我對表格有更簡單的理解，表格就是在說明情況：「Cache$_0$ 為縱軸的哪個狀態下，Cache$_1$為橫軸的哪個狀態」是否能夠發生。但我很喜歡上面在我還不知道表格真的意思時的推理過程。
下面的「CPU 對自己的 Cache 下請求的狀態圖」與「收到其他 CPU 上的 Cache 下請求的狀態圖」是在說明一個 Cache 收到「來自自己 CPU 的 Bus 」或「其它來自其他 Cache 的 Bus 」後的狀態如何改變。維基百科把這兩張圖整合成一種圖。這是在說明自己的狀態。
MESI 除了說明了一個 Cache 自身狀態改變，以及發生改變是因為別人(自身的 CPU 或其他 Cache)做了哪些事情，還描述了 Cache 間彼此的關係。在想這些的過程，我不斷地很驚訝這 4 個狀態可以描述所有 Cache 之間的關係，MESI protocol 真是一個很聰明的方法。
接下來的 valid bit、dirty bit 和 shared bit 的表格又恰好搭配上面 4 個狀態的簡述。雖然四個狀態可以 2 個位元就表示完。但這三個位元分別對應一個狀態的 3 種特性。
(狀態 I) 就是 valid bit (0)
(狀態 S) 是 valid bit (1), shared bit (1)
(狀態 E) 是 valid bit (1), dirty bit (0) $\to$ 在主記憶體中的這份資料和 cache 中存有的這份資料是一樣的 shared bit (0)
(狀態 M) 是 valid bit (1) dirty bit (1) $\to$ 在主記憶體中的這份資料是過時的, shared bit (0)。
MOESI 是將(狀態 S) 又分為 dirty bit (1) (狀態 O，不用寫回主記憶體，自己的是最新的)與 dirty bit (0)(狀態 S，要讀主記憶體最新的資料)。因此如果(狀態 O) 要寫資料給其他 cache 不用通過先寫回主記憶體，其他 cache 在用主記憶體的資料來更新。而是 (狀態 O) 可以直接用 bus 傳遞新的資料給其他 cache 來更新。
Sign in with Wallet
Connect another wallet