---
tags: linux2022
---
# 第 4, 5, 6 週課堂問答簡記
## jim12312321
>$\log_2 x$ 的英文
the logarithm x to the base 2.
## kdnvt
> 為什麼 list_sort 中串列大小的比例差距限制是二比一
因為目的是為了避免合併差距過大，因此使用二比一而不是更大三比一、四比一很合理。需要考慮的是為什麼不用三比二或四比三這種比例。
先簡述一下 list_sort 的演算法：
第一階段：
將節點一個一個讀取，如果確定合併的大小不會超過整體的特定比例，就將之前的串列合併。因為本質還是 bottom up merge sort ，所以此階段的合併都是同大小，所有子串列也都會是二的冪。
第二階段：
當所有節點都讀進並盡可能的同大小合併後，就來到必須合併不同大小的階段。這個階段會將子串列由小大到一個接一個合併。
從以上兩階段可以看出，因為第一階段都是二的冪，在維持 $2m : 2m+1$ 比例的情況下，第一階段結束時最大的子串列就是 $2^{\lfloor log_22mn/{(2m+1)} \rfloor}$ 。
在第二篇論文 [The cost distribution of queue-mergesort, optimal mergesorts, and
power-of-two rules](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.5380) 中看到以下這段話：
>Note that $2^{\lfloor log_22n/3 \rfloor}$ is the unique power of two lying between $n/3$ and $2n/3$ and that the choice of rationals other than $2/3$ will not be more balanced. For example, if $2^{\lfloor log_2n/2 \rfloor}$ or $2^{\lfloor log_25n/9 \rfloor}$ then the sizes of two subproblems are $(2,5)$ for $n = 7$ while the balanced power-of-two gives $(3,4)$.
這段話其實沒有很精準，因為當 $n = 3\times 2^k$ 時， 在包括的情況下介於 $n/3$ 以及 $2n/3$ 的二的冪會有兩個，再不包括的情況下卻又會不存在。如果是寫成
$n/3 < 2^{\lfloor log_22n/3 \rfloor} \leq 2n/3$
就符合這段話的描述。
而這段敘述講述了一件事， $2^{\lfloor log_22n/3 \rfloor}$ 可以找到最接近 $n/2$ 的二的冪。
如果今天是用 $2^{\lfloor log_23n/5 \rfloor}$ 去求 $2^k$ ，則當 $n = 13$ 時，$2^{\lfloor log_23n/5 \rfloor} = 4$，而最接近 $13/2$ 的二的冪卻是 $8$ 。
這代表如果在第一階段用 $3:2$ 的比例去限制，在第二階段合併中，最後一次合併會是 $9:4$ ，這個比例差距已經超過第一階段的 $3:2$ ，而同樣的反例在 $2m:2m+1 ,m>2$ 中也都會發生。因此這樣的演算法只能用在 $2:1$ 的情況。
#### 證明 list_sort 的演算法是 optimal mergesort：
optimal merge sort 定義：在最差的情況下，比較次數小於等於所有其他 mergesort 。
對所有 mergesort ，都可以繪製出一個 merge tree 來表示其合併的順序及長度，每一個節點的權重代表當下的串列長度。方形的是 external node (leaf) ，圓形的是 internal node 。如下圖所示：
```graphviz
digraph BST {
node [fontname="Arial" ];
l1 [ label = "5" ];
l21 [ label = "3" ];
l22 [ label = "2" ];
l31 [ label = "2" ];
l32 [shape=rect label = "1" ];
l33 [shape=rect label = "1" ];
l34 [shape=rect label = "1" ];
l41 [shape=rect label = "1" ];
l42 [shape=rect label = "1" ];
l1 -> { l21 l22 };
l21 -> { l31 l32 };
l22 -> { l33 l34 };
l31 -> { l41 l42 };
}
```
>[graphviz參考連結](https://stackoverflow.com/questions/41194837/how-to-get-graphviz-dot-to-represent-binary-tree-correctly)
internal node 的數量為 leaf 數減一。在最差的情況下，合併 (x,y) 的次數為 x+y-1 ，因此最差情況下總共的比較次數就是
$\sum\limits_{v}^{T}({w(v)} - 1) = \sum\limits_{v}^{T}{w(v)} - (n-1)$
其中 $n$ 為這次排序的節點總數，也是 leaf 的總數。而 $v$ 為所有的 internal node 。$w(v)$ 為該 internal node 的權重（也就是長度）。在這邊因為對所有 合併排序 n - 1 都是固定的，所以只要看 $\sum\limits_{v}^{T}{w(v)}$ 就好。
引述論文 [Queue-Mergesort](https://www.sciencedirect.com/science/article/pii/002001909390088Q?via%3Dihub) 中以下段落：
>We use the fact that the weight of a merge tree is equal to its external path length. The height h(f) of a node I in a tree is the distance of a path from 1 to the root. The external path length of a tree T’ is the sum E(T’) = $\sum\limits_{l\ a\ leaf\ of\ T'}{h(l)}$
以及以下段落：
>Thus a merge tree T describes an optimal merge-sort on n items if and only if T has minimum external path length $\sum\limits_{l\ a\ leaf}{h(l)}$. It is known that this occurs if and only if the following condition is satisfied: all of T’s leaves are located on its bottom two levels.
因此我們可以得知，只要證明 list_sort 的 merge tree 符合所有 leaf 都在最下面兩層這個條件，就可以證明它是 optimal merge sort 。
分析 list_sort 的演算法，可以得出以下兩點：
第一點：在合併的過程中，最多只有一個子串列不是二的冪（第二階段排最後的子串列）。
第二點：在合併的過程中，兩者差異不大於兩倍。
**證明合併過程中對所有長度 n 的子串列，其 merge tree 的所有 leaf 都在最下面兩層。**
**證明過程：**
第一階段所有合併皆為二的冪，符合命題。
**用數學歸納法證明第二階段：**
最小端的子串列只可能是 (1,1) 或 (1,2)，兩者合併都符合命題。
對第二階段過程中的任意合併，假設其兩個子串列都符合命題。
則合併的過程中，由第一點可知，其中一個子串列一定為二的冪，因此其 merge tree 為 full binary tree ，所有 leaf 都在最底層。另其長度為 $2^{k_1}$ ，則 merge tree 的高度為 $k_1$ 。
當另一個子串列如果也是二的冪，因為第二點中兩者差異不大於兩倍，因此其大小只可能是 $2^{k_1-1}$ 或 $2^{k_1+1}$ 。 merge tree 的高度 $k_2 = k_1\pm1$，符合命題。
當第二的子串列不為二的冪，那根據假設，此串列的 merge tree 所有 leaf 都在最下面兩層，而其中一層就是 $k_1$ ，否則會違反第二點兩者差異不大於兩倍的描述，因此也符合命題。
根據數學歸納法，對第二階段過程中的任意合併，其 merge tree 的所有 leaf 都在最下面兩層。所以可以得出最後一次合併所產生的 merge tree 也符合命題。
根據論文中所述，可得知 list_sort 中的演算法也是 optimal merge sort 。
## Uduru0522
[第 4 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz4) 題目 1 當 `x = 0`，答案錯誤
## idoleat
> list_sort 是怎麼減少 cmp 的函式呼叫？每次呼叫的成本是什麼？
在 [lib/sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c) 和 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 中 `cmp` 是讓使用者自訂排序方式的函式指標，需要傳入三個 arguments：
一個 `cmp` 函式呼叫至少會有以下指令的執行 (以 x86 為例)：
```
push rbp
mov rbp,rsp
mov DWORD PTR [rbp-4], edi # args
mov DWORD PTR [rbp-8], esi
mov DWORD PTR [rbp-12], edx
# 使用 rbp-4, rbp-8 和 rbp-12 進行比較
pop rbp
ret
```
由於現代處理器架構複雜，可能會有 pipeline, out-of-order execution 等機制，沒辦法直接估算所需的 cycle 數量，但是
記憶體上一個 stack frame 會使用以下空間：
* return address
* old `rbp`
* local variables
(WIP)
## Nomad1230
[第 4 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz4)題目 `2`:
```c
#define BITS_PER_BYTE 8
#define BITS_PER_LONG (sizeof(unsigned long) * BITS_PER_BYTE)
#include <stddef.h>
static inline size_t ffs(unsigned long x)
{
if (x == 0)
return 0;
size_t o = 1;
unsigned long t = ~0UL;
size_t shift = BITS_PER_LONG;
shift >>= 1;
t >>= shift;
while (shift) {
if ((x & t) == 0) {
x >>= shift;
o += shift;
}
shift >>= 1;
t >>= shift;
}
return o;
}
```
此函式的功能是找出變數的 bit pattern 中最低位元的 1 位於哪個位置，例如 `ffs(0xF0)` 其值為 4 。
此演算法採用 binary search，在檢查 bit pattern 時會將其切成兩半並檢查其中一邊，再從尚未檢查的那一邊再切一半，以此類推去計數，以 `0xFF00000` 為例，示意圖如下:
```graphviz
digraph G{
rankdir = LR
label = "step 1\nx & t == 0\no += 16"
subgraph cluster_0 {
node [shape = record]
style = filled
color = white
struct0 [label = "{0|0|0|0|F|F|F|F}", color = red, fontcolor = red]
fontcolor = red
label = "t"
}
subgraph cluster_1 {
node [shape = record]
style = filled
color = white
struct1 [label = "{F|F|0|0|0|0|0|0}", color = blue, fontcolor = blue]
fontcolor = blue
label = "x"
}
}
```
```graphviz
digraph G{
rankdir = LR
label = "step 2\nx & t == 0\no += 8"
subgraph cluster_0 {
node [shape = record]
style = filled
color = white
struct0 [label = "{0|0|F|F}", color = red, fontcolor = red]
fontcolor = red
label = "t"
}
subgraph cluster_1 {
node [shape = record]
style = filled
color = white
struct1 [label = "{F|F|0|0}", color = blue, fontcolor = blue]
fontcolor = blue
label = "x"
}
}
```
```graphviz
graph G{
label = ".\n.\n."
}
```
```graphviz
digraph G{
rankdir = LR
label = "step 5\nx & t != 0\no += 0"
subgraph cluster_0 {
node [shape = record]
style = filled
color = white
struct0 [label = "{1}", color = red, fontcolor = red]
fontcolor = red
label = "t"
}
subgraph cluster_1 {
node [shape = record]
style = filled
color = white
struct1 [label = "{1}", color = blue, fontcolor = blue]
fontcolor = blue
label = "x"
}
}
```
`t` 變數為 bit mask ，每次迴圈都遮住 `x` 的 bit pattern 的左半邊，若右半邊皆為 0 則將 `o` 加上 `shift` ，最後將 `o` 回傳。
## ray90514
[第 4 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz4) `1`
```c
int ceil_log2(uint32_t x)
{
uint32_t r, shift;
x--;
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
return (EXP1) + 1;
}
```
對於 x 的二進位表示如下 $x_k, ..., x_1, x_0$ ， $x_k$ 為最高位的 1 ，也可以寫成以下形式， $2^k + x_{k-1}2^{k_1} + ... + x_12^1 + x_02^0$ ，求 $log_2$ 其實就是在找最高位的 1 ，因為是向上取整所以最後將結果加一。 2 的冪不需要加一，所以一開始會將 x 減一，但這個方法不適用於 x = 0 的情況。
每次將 x 分成高位和低位的兩半邊，如果最高位的 1 在高位的半邊，代表 x 會大於低位的半邊全為 1 的值，如果在高位的半邊，就將 x 向右位移一半，這樣不管是在高位還低位，接下來都只要看低位。
`r` 負責紀錄 $log_2$ 的結果，如果最高位在高位的半邊，代表 $log_2$ 至少有位數的一半，就將該值加入至 `r`。
依照以上的邏輯，上述程式還缺少三行，而 `EXP1` 為計算 $log_2$ 的結果。
```c
r |= shift;
shift = (x > 0x1) << 0;
r |= shift;
```
若合併這三行也就是 `EXP1` ，因為 x 最後只剩下兩位，看第二位就可以知有沒有大於一。
```c
r | shift | x > 0x1
r | shift | x >> 1
```
## idoleat
> 即便在一整個 CPU 都被一個 process 使用了，還有什麼事情會影響效能
minor page fault
TLB
:construction:
> Context switch 發生在什麼時候
1. 在 **preamptive** schedular 切換 tasks 的時候
2. 在 Interrupt **之後** (恢復到原本的工作)
不可以只背課本上的定義，需要知道詳細的使用場景
:construction:
> mode switch 不等於 context switch
**Mode switch:** 當一個 user process 想要執行 privileged 的操作時，需透過 system call，也就是已經小心設計好給使用者的功能。早期 UNIX system call 有二十多個，現代作業系統則常有上百個，詳情可見 POSIX 標準。
OSTEP Ch6: Limited Direct Execution Protocol
trap instruction
return-from-trap instruction
trap table
trap handlers
:construction:
**Context switch:**
:construction:
> 為了減少 mode switch 有沒有可能把 kernel mode 的 tasks 累積到一定數量再一次做完？
mode switch 的成本因為要防禦各種 CPU side-channel attack 手段而變高。於是，System call aggregation 就將多個系統呼叫合併成一個來做，從而縮減系統呼叫整體的成本，參見 Open Source Summit Japan 2021 的演講 [Reduce System Call Overhead for Event-Driven Servers](https://ossalsjp21.sched.com/event/peeF)
---
Google 的 M:N threading model 研究 "[ghOSt: Fast & Flexible User-Space Delegation of Linux Scheduling](https://dl.acm.org/doi/10.1145/3477132.3483542)"
---
## freshLiver
> 為什麼 `clone` 參數中的 `parent_tid` 以及 `child_tid` 需要傳入 address 而不是 TID value 而已
### `clone()` Prototype
```c
/* Prototype for the glibc wrapper function */
#define _GNU_SOURCE
#include <sched.h>
int clone(int (*fn)(void *),
void *stack,
int flags,
void *arg,
...
/*
* pid_t *parent_tid,
* void *tls,
* pid_t *child_tid
*/
);
```
### 說明
在呼叫 `clone()` 時給的 flags 中包含 `CLONE_PARENT_SETTID` 與 `CLONE_CHILD_CLEARTID`。而根據 [`clone()` 的 Man Page 中對於 Flags 的說明](https://man7.org/linux/man-pages/man2/clone.2.html#DESCRIPTION)，可以知道：
1. 當 Flags 中包含 `CLONE_PARENT_SETTID` 時：
在建立執行緒時，會將 `clone()` 參數中的 `parent_tid` 的值**修改**成新建立的執行緒的 Thread ID。
2. 當 Flags 中包含 `CLONE_CHILD_CLEARTID` 時：
當建立的執行緒結束時，會將 `clone()` 時傳送的參數 `child_tid` 的值**修改**為 0。
因此若不是傳送建立執行緒時新增的 `node *` 物件 `insertedNode` 中的 `tid` 的話，就無法在 `thread_kill()` 或是 `killAllThreads()` 函式中透過檢查 `tid` 來確認執行緒是否已經結束。
## 2020leon
> 偵測 unsigned addition 的 overflow
> https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html
- 在無號整數加法之**前**偵測溢位
```c
bool add_overflow(uint32_t a, uint32_t b, uint32_t *c)
{
if (UINT32_MAX - a < b) {
return true;
} else {
*c = a + b;
return false;
}
}
```
對應的最佳化組合語言如下（ Intel syntax ）。
```asm
add_overflow1:
mov ecx, edi
mov al, 1
not ecx
cmp ecx, esi
jb .L4
add edi, esi
xor eax, eax
mov DWORD PTR [rdx], edi
.L4:
ret
```
- 在無號整數加法之**後**偵測溢位
```c
bool add_overflow(uint32_t a, uint32_t b, uint32_t *c)
{
*c = a + b;
return *c < a;
}
```
```c
bool add_overflow(uint32_t a, uint32_t b, uint32_t *c)
{
return __builtin_uadd_overflow(a, b, c);
}
```
對應的最佳化組合語言如下（ Intel syntax ）。
```asm
add_overflow:
add edi, esi
mov DWORD PTR [rdx], edi
setc al
ret
```
其中 `setc` 指令即 Set if carry ，便是將 carry bit 存入指定的暫存器中。
## kevinshieh0225
降低 GCD 的 branch 數量
TODO: REACTO for gcd
Sign in with Wallet
Connect another wallet