# 2025-05-14 會議問答記錄

## Q1: [kxo](https://hackmd.io/@sysprog/linux2025-kxo/%2F%40sysprog%2Flinux2025-kxo-a) -> 為何 Linux 核心不傾向使用 FPU？

參考 [Use of floating point in the Linux kernel](https://stackoverflow.com/questions/13886338/use-of-floating-point-in-the-linux-kernel)：
> The real reason is that the kernel doesn't particularly *need* FPU ops and also needs to run on architectures without an FPU at all. Therefore, it simply avoids the complexity and runtime required to manage its own FPU context by not doing ops for which there are always other software solutions.
> It's interesting to note how often the FPU state would have to be saved if the kernel wanted to use FP...every system call, every interrupt, every switch between kernel threads. Even if there was a need for occasional kernel FP, it would probably be faster to do it in software.

因為 FPU 暫存器較大（如：Intel x86 的 YMM 暫存器一個就有 256 bits 寬 [[Source](https://www.cs.uaf.edu/2012/fall/cs301/lecture/11_02_other_float.html)]），且作業系統又需經常進行 Context Switch (如：system call, interrupt, switch between kernel threads)，因此若在 kernel 中使用 FPU 指令，每次都要反覆的「**手動**^[1]^」store 和 restore FPU 暫存器狀態，這會需要更多的 CPU cycle，導致系統效能下降，何況大多數核心程式碼幾乎不會使用浮點數指令，而且 Linux kernel 還得能在缺少 FPU 的硬體（如：較早期的嵌入式處理器）上運行。所以若為這些不常使用 FPU 的行程頻繁 store 和 restore FPU 狀態是非常浪費系統資源的。因此kernel 的浮點數運算改由軟體方法 (如：fixed point) 來取代，雖然軟體方法在浮點數運算的效率沒有直接用 FPU 來的好，但 kernel 少用，所以相比於支援 FPU 的 kernel 來說反而是更快。再者，由於前述的原因，為了減少不必要的 FPU 狀態保存，FPU 支援 lazy state switching 機制，借助此機制可以讓 kernel 在支援 FPU 指令的同時，當發生 Context Switch 時，以 Intel®64 為例，kernel 需將 CR0.TS bit 設為 1 ^[2]^，表示 FPU 暫存器的內容尚未保存，若接手的行程未執行到 FPU 指令，則 FPU 暫存器的內容仍維持上一個行程的 context 的狀態，反之，一但後來的行程一執行到 FPU 指令時，就會因為 CR0.TS bit 為 1 而觸發 trap（Device not Available exception 即 #NM）進入 kernel mode^[實驗]^，此時 #NM exception handler 就會去保存上一個行程的 context 狀態。不過在現今[動態執行](https://en.wikipedia.org/wiki/Out-of-order_execution)^[3]^的 CPU 中，可能沒辦法馬上偵測到 lazy restore mechanisms 中設定的 "FPU not available"，導致在當前行程中，仍可以存取到上一個行程的 FPU 暫存器內容，進而達到攻擊的目的（FPU 暫存器可能是用來暫存加密相關資料）即 [CVE-2018-3665](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2018-3665) 漏洞。基於上述的種種因素，Linux 不傾向使用 FPU 指令。

### 實驗：
Linux kernel module
參考內容：
> 教材：
> - [LKMPG](https://sysprog21.github.io/lkmpg/) Chapter 1 ~ 4
> - [Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)

撰寫 Kernel module 查看在 userspace 執行 fpu 指令後的 CR0.TS bit 狀態：

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/smp.h>

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Jimmy");
MODULE_DESCRIPTION("Check CR0 TS bit on all CPUs");

static void show_cr0_ts(void *info)
{
    unsigned long cr0;
    asm volatile("mov %%cr0, %0" : "=r"(cr0));
    pr_info("CPU %d: CR0 = 0x%lx, TS = %lu\n", smp_processor_id(), cr0, (cr0 >> 3) & 1);
}

static int __init ts_check_init(void)
{
    pr_info("Checking CR0 TS bit on all CPUs...\n");
    on_each_cpu(show_cr0_ts, NULL, 1);
    return 0;
}

static void __exit ts_check_exit(void)
{
    pr_info("CR0 TS bit check module unloaded.\n");
}

module_init(ts_check_init);
module_exit(ts_check_exit);

輸出結果：

$ sudo dmesg | grep CPU
[325258.902427] Checking CR0 TS bit on all CPUs...
[325258.902435] CPU 5: CR0 = 0x80050033, TS = 0
[325258.902436] CPU 1: CR0 = 0x80050033, TS = 0
[325258.902436] CPU 2: CR0 = 0x80050033, TS = 0
[325258.902437] CPU 7: CR0 = 0x80050033, TS = 0
[325258.902437] CPU 6: CR0 = 0x80050033, TS = 0
[325258.902436] CPU 0: CR0 = 0x80050033, TS = 0
[325258.902437] CPU 4: CR0 = 0x80050033, TS = 0
[325258.902436] CPU 3: CR0 = 0x80050033, TS = 0

:::info
經在 Ubuntu 24.04 實驗後，CR0.TS bit 皆為 0。我還不清楚是為什麼？
:::

[1]: 根據 Robert Love 在 [Linux Kernel Development](https://www.amazon.com/Linux-Kernel-Development-Robert-Love/dp/0672329468/) 一書論及浮點運算："Using a floating point inside the kernel requires manually saving and restoring the floating point registers." **以 kernel 的視角來看**，因為 kernel process 不能像 user process 那樣透過 trap 中斷來請自己（kernel）保存當前行程的狀態，因此若 kernel 需要用到 FPU 指令時，就必須自己（kernel）**手動**保存 kernel process 的 FPU 暫存器狀態。
\
[2]: 參考 [Intel®64 and IA-32 Architectures Software Developer’s Manuals Vol.3](https://cdrdv2.intel.com/v1/dl/getContent/671447) 15.4.1 (Vol. 3A 15-7)：
> The TS flag in control register CR0 is provided to allow the operating system to delay saving/restoring the x87 FPU and SSE state until an instruction that actually accesses this state is encountered in a new task. When the TS flag is set, the processor monitors the instruction stream for x87 FPU, MMX, SSE instructions. When the processor detects one of these instructions, it raises a device-not-available exception (#NM) prior to executing the instruction. The #NM exception handler can then be used to save the x87 FPU and SSE state for the previous task (using an FXSAVE, XSAVE, or XSAVEOPT instruction) and load the x87 FPU and SSE state for the current task (using an FXRSTOR or XRSOTR instruction). If the task never encounters an x87 FPU, MMX, or SSE instruction, the device-not-available exception will not be raised and a task state will not be saved/restored unnecessarily.

\
[3]: 讓處理器能同時把多條指令丟進管線，做得了的就先做，以提高Througput，最後再按原本程式順序輸出結果，好像一切仍依序執行一樣。
:::info
待釐清:
- 為什麼要將 FPU 和 SIMD 的 register 一起使用呢？是因為他們的暫存器都需要設計的很大嗎？
- 手動的理解有沒有錯？
:::
### Q2: Assume x is a single-precision floating point (IEEE 754) and always >= 1, calculate square root. No FPU is allowed.
- 利用 `牛頓求根法`
- 說明：
先選擇一個接近函數 $\displaystyle f(x)$ 零點的點 $x_0$。找出穿過點 $(x_0, \displaystyle f(x_0))$ 且斜率為 $\displaystyle f'(x_0)$ 之切線與 $x$ 軸的焦點 $x_1$，透過點斜式得該切線方程式為 $y - \displaystyle f(x_0) = \displaystyle f'(x_0)(x - x_0)$，將點 $(x_1, 0)$ 帶入得 $0 - \displaystyle f(x_0) = \displaystyle f'(x_0)(x_1 - x_0)$，經過移項得：\begin{split} - \cfrac{\displaystyle f(x_0)}{\displaystyle f'(x_0)} = x_1 - x_0 \ \ \ \Rightarrow \ \ \ x_1 = x_0 - \cfrac{\displaystyle f(x_0)}{\displaystyle f'(x_0)}\end{split}依循以上的方法得疊代公式：$x_{n+1} = x_n - \cfrac{\displaystyle f(x_n)}{\displaystyle f'(x_n)}$ 即可逐步求得近似 $f(x)$ 零點的數。

- 求平方根：
因為要求 $N$ 的平方根，故令 $\displaystyle f(x) = x^2 - N$，則 $f(x)$ 的零點即為 $N$ 的平方根。帶入疊代公式 $x_{n+1} = x_n - \cfrac{\displaystyle f(x_n)}{\displaystyle f'(x_n)}$ 經化簡後得：\begin{split}x_{n+1} = x_n - \cfrac{({x_n}^2 - N)}{2x_n} = \cfrac{1}{2}(2x_n - \cfrac{{x_n}^2}{x_n} + \cfrac{N}{x_n}) = \cfrac{1}{2}(x_n + \cfrac{N}{x_n})\end{split}

float my_sqrtf(float x)
{
    if (x == 0.0f)
        return 0.0f;

    float ans = x;
    float tolerance = 1e-5f; // 取到小數點後第五位
    while ((ans * ans - x) > tolerance || (x - ans * ans) > tolerance)
        ans = 0.5f * (ans + x / ans);
    return ans;
}

:::info
當輸入的值為 73 時，會發生無窮迴圈，只能透過增加誤差解決，但看起來是不能用這種方法😢。
> 參考：[math: add faster soft float sqrtf implementation, add rsqrtf #1013](https://github.com/picolibc/picolibc/pull/1013/files)
:::

### Q3: 為何有 accpet 系統呼叫？為何不能直接 read socket fd？
內容部分參考：
> Linux manual page: [accept](https://man7.org/linux/man-pages/man2/accept.2.html), [connect](https://man7.org/linux/man-pages/man2/connect.2.html), [listen](https://man7.org/linux/man-pages/man2/listen.2.html), [read](https://man7.org/linux/man-pages/man2/read.2.html)
>
> CS:APP Chapter 11 重點參考：11.4
>
> Stack overflow:
> - [What things are exactly happening when server socket accept client sockets?](https://stackoverflow.com/questions/29331938/what-things-are-exactly-happening-when-server-socket-accept-client-sockets)
> - [How does the socket API accept() function work?](https://stackoverflow.com/questions/489036/how-does-the-socket-api-accept-function-work)
> - [Socket: How does connect/accept use the 3-way handshake, if they ever do?](https://stackoverflow.com/questions/62468593/socket-how-does-connect-accept-use-the-3-way-handshake-if-they-ever-do)
> - [Does Accept event happen after the three way handshake?](https://stackoverflow.com/questions/18451462/does-accept-event-happen-after-the-three-way-handshake)
> - [About listen(), accept() in network socket programming(3-way handshaking)](https://stackoverflow.com/questions/34676972/about-listen-accept-in-network-socket-programming3-way-handshaking)
>
> 其他參考資料：
> - [TCP SYN Queue and Accept Queue Overflow Explained](https://www.alibabacloud.com/blog/tcp-syn-queue-and-accept-queue-overflow-explained_599203)
> - [TCP Control Block Interdependence](https://www.rfc-editor.org/rfc/rfc9040.pdf)

首先，伺服器端使用 socket() 建立一個 socket，再透過 bind() 將其綁定到特定的 IP 地址與埠號，接著呼叫 listen() 將該 socket 設為監聽狀態，此 socket **僅負責等待客戶端的連線請求，並不會與任何客戶端建立連線**，因為伺服器要同時處理多個客戶端請求，所以要保留原本的 socket 來監聽多個客戶端的連線請求，當有客戶端發送連線請求（客戶端執行 connect()）時，客戶端的 TCP/IP 堆疊就會要發送 SYN 封包給伺服器^[如下圖]^，在發送 SYN 之前，客戶端的 kernel 必須先配置一個臨時埠（[ephemeral port](https://en.wikipedia.org/wiki/Ephemeral_port "Ephemeral port")）用來與伺服器連接，在客戶端發送 SYN 封包後，伺服器的 TCP/IP 堆疊就會在 SYN queue 中建立一個 entry，並回傳 SYN-ACK 封包給客戶端完成第二次握手，此時，客戶端的 connect() 就會回傳 0 表示成功，並再發送 ACK 封包給伺服器完成第三次握手，當伺服器收到 ACK 後，便會把剛剛建立在 SYN queue 中的 entry 移動到 Accept queue 中，伺服器就可以透過 accept() 從 Accept queue 中取出一個客戶端的 socket 資訊，並回傳一個全新的 socket（與負責監聽的 socket 不同），此 socket 負責與該客戶端做資料交換。因此，每當有新的客戶端完成連線時，accept() 就是負責從 Accept queue 中取出一份客戶端的連線資訊，並建立新的 socket，負責與客戶端做資料交換。


回答問題：為何有 accpet 系統呼叫？為何不能直接 read socket fd？
因為**負責監聽的 listen_fd，要接受很多客戶端的連線請求**，為了不讓傳輸的資料都混在一起，伺服器為每一個客戶端建立對應的 socket_fd，因此需要 accept() 去建立新的 socket_fd，以確保每一個 TCP 通訊都是獨立的。

:::info
待釐清:
TCP/IP stack 運行三次握手的細節是？
SYN/Accept queue 中的 entry 內容是什麼？
:::

### Q4: 比照 remove_list_node 撰寫 find_node / reverse_nodes，利用 indirect pointer (no external allocated memory. i.e., constant space complexity)，如何驗證？

bool find_node(List *list, Node *target) 
{
    Node **indirect = &list->head;
    while (*indirect != NULL) {
        if (*indirect == target) {
            return true;
        }
        indirect = &(*indirect)->next;
    }
    return false;
}

void reverse_node(List *list) {
    if (!list || !list->head) {
        return;
    }
    
    Node *cur = list->head;
    Node *prev = NULL;
    Node *next = NULL;

    while (*cur) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }

    list->head = prev;
}

### 追蹤程式碼
- 追蹤 find_node
- 假設 `target` 為 `node2`
- 第 3 行
- 第 4 ~ 9 行
- 假設 `target` 不在鏈結串列中
- 第 3 行
- 第 4 ~ 9 行
- 第 10 行：return FALSE

- 追蹤 reverse_node
- 第 6 ~ 8 行
- 第 10 ~ 15 行
- 第 17 行

### 寫出完整程式碼來驗證
:::spoiler 完整程式碼

#include <stdio.h>
#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node_t;

typedef struct {
    struct Node* head;
} List_t;

bool find_node(List_t *list, Node_t *target) {
    Node_t **indirect = &list->head;
    while (*indirect != NULL) {
        if (*indirect == target) {
            return true;
        }
        indirect = &(*indirect)->next;
    }
    return false;
}

void reverse_node(List_t *list) {
    if (!list || !list->head) {
        return;
    }
    Node_t *cur = list->head;
    Node_t *prev = NULL;
    Node_t *next = NULL;
    while (cur) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    list->head = prev;
}

void print_list(List_t *list) {
    Node_t *cur = list->head;
    while (cur != NULL) {
        printf("%d -> ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

int main() {
    Node_t node4 = {4, NULL};
    Node_t node3 = {3, NULL};
    Node_t node2 = {2, &node3};
    Node_t node1 = {1, &node2};

    List_t list = {.head = &node1};
    printf("list: ");
    print_list(&list);
    printf("Find 2: %s\n", find_node(&list, &node2) ? "Found" : "Not Found");
    printf("Find 4: %s\n", find_node(&list, &node4) ? "Found" : "Not Found");
    
    reverse_node(&list);
    printf("Reverse list: ");
    print_list(&list);

    return 0;
}

:::
- 驗證 find_node
- 1. 建立單向鏈結串列

    node1 -> node2 -> node3 -> NULL

- 2. 額外節點（未列入串列中）

    node4

- 3. 驗證

| 執行方法 | 預期結果 |
| ------------------------ | -------- |
| find_node(&list, &node2) | TRUE |
| find_node(&list, &node4) | FALSE |

- 驗證 reverse_node
- 呼叫 reverse_node(&list)
- 預期結果：

    node3 -> node2 -> node1 -> NULL

- 輸出結果：

jimmy@NEAT:~/linux2025$ ./test_list 
list: 1 -> 2 -> 3 -> NULL
Find 2: Found
Find 4: Not Found
Reverse list: 3 -> 2 -> 1 -> NULL

### Q5: 複雜度 大 $O$、小 $o$ 的定義？
> [楓葉書](https://www.tenlong.com.tw/products/9780262046305?list_name=srh) Page. 47
- 為何有大 $O$ 和小 $o$ 的存在？
- 大 $O$：
- 用來描述函數增長速率的上界，也就是在最壞情況下的時間或空間複雜度。這種表示法讓我們能忽略常數因子，專注於演算法在輸入規模增長時的時間複雜度趨勢。透過這種方式可以更有效的比較不同演算法在處理大規模輸入時的效率表現。例如：$O(nlogn)$ 通常比 $O(n²)$ 更有效率。

- 小 $o$：
- 用來描述一個函數相對於另一個函數的**嚴格上界**，意味著前者的增長速率遠小於後者（即在輸入規模無窮大時，前者對後者的比直趨向於 0）。例如：Dijkstra 演算法，圖有 $V$ 個節點和 $E$ 條邊，並將尚未拜訪的點存於 Binary Heap 中，時間複雜度為 $O(ElogV)$ ，不過在這個演算法中除了主要的 $O(ElogV)$ 開銷外，還有一些額外的預處理操作，例如：
- 建立 Binary Heap：Buttom Up 建立需 $O(V)$。
- 節點標籤初始化：為每個節點設置初始標籤需 $O(V)$。

這些額外操作的時間複雜度 $O(V)$ 相對於 $O(ElogV)$ 是次要的。因此，總時間複雜度可以表示為：$O(ElogV) + o(ElogV)$，這裡的 $o(ElogV)$ 表示所有增長速率遠小於 $ElogV$ 的項，$O(V)$（初始化），因為 $V / (ElogV) → 0$（當 $V$ 和 $E$ 趨進無窮大時，考慮 $E ≥ V - 1$），明確指出 $O(V)$ 的開銷相對於 $O(ElogV)$ 是微不足道的。

- $Big-O$
- **定義**：設 $f,g:\mathbb N \to \mathbb R_{\ge 0}$ 若 $\exists c, n_0\in \mathbb R^+$，使得 $\forall n \ge n_0,\; 0\ \le f(n) \le cg(n)$，則稱 $f(n)=O(g(n))$，寫作 $f(n) \in O(g(n))$

- 例子：試證 $f(n) = 3n + 3$，則 $f(n) = O(n)$
解：$\because \exists c = 4, n_0 = 3$ 使得 $\forall n \ge n_0 = 3,\; 0 \le 3n + 3 \le 4n = cg(n)$
$\therefore f(n) = O(n)$ 得證。

- 也就是說，當 $n$ 大於等於 $3$ 時，可以保證 $f(n)$ 一定會小於 $4\,g(n)$，如下圖，橫軸表示為輸入資料量 $n$，縱軸表示執行時間，只參考第一象限，因為執行時間與輸入資料量不可能為負 (Source: [GeoGebra](https://www.geogebra.org))：

- $Little-o$
- **定義**：設 $f,g:\mathbb N\to\mathbb R_{\ge 0},$ 若 $\forall c \in \mathbb R^+,\;\exists n_0\in\mathbb R^+$，使得 $\forall n \ge n_0,\;0\ \le f(n) \lt cg(n)$，則稱 $f(n)=o(g(n))$，寫作$f(n) \in o(g(n))$

又或者是 $\lim_{n \to \infty} \cfrac{f(n)}{g(n)} = 0 \Leftrightarrow f(n) = o(g(n))$

- 例子：試證 $f(n) = 3n + 3$，則 $f(n) = o(n^2)$
- 解法一：
$3n+3 < cn^2 \Rightarrow 3 < cn^2 -3n \Rightarrow 3c < c^2n^2 - 3cn \Rightarrow 3c + 2.25 < (cn - 1.5)^2$$\therefore \sqrt{3c + 2.25} + 1.5 \lt cn \Rightarrow \cfrac{\sqrt{3c + 2.25} + 1.5}{c} < n$，故當$n > \cfrac{\sqrt{3c + 2.25} + 1.5}{c}$ 時，$f(n) < cn^2$ 成立，得證。

- 解法二：
$\lim_{n \to \infty}\cfrac{3n+3}{n^2} = \lim_{n \to \infty} (\cfrac{3n}{n^2} + \cfrac{3}{n^2}) = \lim_{n \to \infty} (\cfrac{3}{n} + 0) = 0$ 得證。