---
tags: linux2024
---
# 2024q1 Homework5 (assessment)
contributed by < `randyuncle` >
## 前 4 週的測驗題選出 3 題改進
* [進行中] 第一週測驗二 -- [Timsort 改進](https://hackmd.io/nsZV7ErKSBewIhls7wgrsQ#%E6%8F%90%E5%87%BA%E6%94%B9%E9%80%B2%E6%96%B9%E6%A1%88%E4%B8%A6%E5%AF%A6%E4%BD%9C%E4%B9%8B)
## CS:APP 第二章閱讀紀錄
>閱讀此章節時也一併參照：
[你所不知道的 C 語言: 數值系統篇](https://hackmd.io/@sysprog/c-numerics#%E6%95%B8%E5%80%BC%E8%A1%A8%E9%81%94%E6%96%B9%E5%BC%8F%E5%92%8C%E9%98%BF%E8%B2%9D%E7%88%BE%E7%BE%A4)
[你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)
[你所不知道的 C 語言: 浮點數運算](https://hackmd.io/@sysprog/c-floating-point)
[你所不知道的 C 語言: 編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization?type=view)
### 2.1 Information Storage
#### Data types
* C standard 不保證 `char` 是 signed 資料。
* 指標會佔有一個資料型態中的所有 word size。
* **Programmers should strive to make thier programs portable across different machines and compilers.**
* One aspect: Making the program **intensitive to the exact sizes** of the different data types.
* In C: The data types defined in `<stdint.h>` -- `int32_t`, `int64_t`, `uint32_t`, `uint64_t`, etc..
* The C standards establish **only the lower bounds on numeric data types**, leaving the upper bounds unset, except with the fixed sizes.
* The hidden word size dependencies in the transition from 32-bit to 64-bit machines.
#### Addressing and Byte Ordering
* 位元組順序（Byte Ordering）在某些場合和應用中是一個必須考量到的事:
* **網路應用**：不同位元組排列法（endian）的機器之間互相傳輸資料的場合。
* 查看代表**整數**的位元序列時。
* 當需要編寫**非常規資料型態**系統的程式時（對應到 C 語言中，為 `union`、`cast` 所定義的結構體）。
#### Shist Operations in C
* C 語言對 shift 操作的是由左到右的方向做讀取及處理。
* 在 C 語言中，`+` 和 `-` 運算子的優先度比 shift 要高。
* 在右移中，可分成 logical shift 和 arithmetic shift 兩種類型的移位。
* 通常來說，logical shift 會應用在 signed numbers；arithmetic shift 則應用在 unsigned numbers。
* logical shift: 左測補 0。
* arithmetic shift: 左側補原二位數之 MST 的值（即為 signed bit）
* **C 語言未準確定義對 signed numbers 的右移應當適用哪種規則。**
* [**[Undefined Behavior]** Shift by k, for large values of k](https://hackmd.io/@sysprog/c-undefined-behavior#%E5%BE%9E-C-%E8%AA%9E%E8%A8%80%E8%A9%A6%E9%A1%8C%E8%AB%87%E8%B5%B7):
* 在 C 語言規範中，**沒有定義當左移的位元數比被移位的位元數更多時的行為**。
* 通常在多種機器來說，應對這個情境的解決方法是，對移位的位元數做**取餘數**的操作。
### 2.2 Integer Representation
```graphviz
digraph _graph_name_ {
rankdir=LR; # 順序由左至右(上下是"TD"
graph [fontname="DFKai-SB"]; # 此三行是設定字型
node [fontname="DFKai-SB"]; # 中文務必指定
edge [fontname="DFKai-SB"]; # 不然可能會出現亂碼
# node
int[label = "Integer", shape=box]
sign[label = "Signed", shape=box] # 不給 label 就會直接用名稱
unsign[label = "Unsigned", shape=box]
positive[label = "Positive Integer"]
zero[label = "Zero"]
negative[label = "Negative Integer"]
# edge
int->sign
int->unsign
sign->positive
sign->zero
sign->negative
unsign->positive
unsign->zero
}
```
#### unsigned encoding
* 每個二位數和無號數是一對一對應的。
#### Two's-complement encoding ( signed encoding )
* 每個二位數和二補數的有號數是一對一對應的。
* 令二補數有號數的最大值為 $TMax_w$、最小值為 $TMin_w$，則其之間有以下關係：
$$| TMax_w | = | TMin_w | + 1$$ 也側面表示 $TMin_w$ 在二補數有號數的表示中沒有其對應的正整數。
* 在 [C23](chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3088.pdf) 標準之前，C 語言之有號數沒有完全採納二補數表示法。
> **ISO/IEC 9899:2023 6.2.6.2 Integer types**
> 6. **NOTE2** The sign representation defined in this document is called two’s complement. Previous revisions of this document additionally allowed other sign representations.
#### Conversions between signed and unsigned
* 在相同位元數轉換的前提下，C 語言基本上是以**原數值**本身的**二進位表示**直接做轉換。
* 假設有以下的 C 程式節錄：
```c
short int v = -12345;
unsigned short int uv = v;
```
`short int` 是一個 16 位元的整數資料型態。
變數 $v$ 的二進位值為 $1100111111000111$，為帶有 signed bit 的二補數表示法。在 C 程式中，在做有號數和無號數的內部赴值**並不會改變其原本的位元表示**。也就是說，變數 $uv$ 的二位數也會是 $1100111111000111$，只是其 MST 的位元並非代表 signed bit，使其最終的變數內容變為 $uv = 53191$。
* 繼上一點，若假設在 $w$ 二進位值，且 MST 位元為 1（也就是其在 signed 整數值為負值）的情況下，無號數的值為 $U_w$，二補數有號數的值為 $T_w$，則有以下的關係存在 $$| U_w | + | T_w | = 2^w。$$
#### signed versus unsigned
* C 語言支援 signed 和 unsigned 之間的顯性（explicit）及隱性（implicity）轉換。
* 在數值的最後加上 `U` 或 `u` 字元，即代表該數為 unsigned 整數值。
* e.g. 12345U、0x0608u。
* 當有**同時涵蓋 signed 以及 unsigned 數值**的操作時，C 會隱性的將**所有的數值以 unsigned 數值**，也就是都以非負整數的角度，去**處理**該操作。
* e.g. 假設有一布林不等式 -2147483647 - 1U < -2147483647 在 32 位元表示的程式中，因有 `1U` 在不等式裡的關係，所以 C 以 unsigned 的角度去處理不等式中的所有數值，最後會回傳 True。
- [ ] [**C 語言中的 $TMin$**](chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://csapp.cs.cmu.edu/3e/waside/waside-tmin.pdf)
在 C 標頭檔 `limits.h` 中，可以發現到 C 的有號數整數值的上下限是這樣定義的：
```c
/* Minimum and maximum values a ‘signed int’ can hold. */
#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX - 1)
```
在對 INT_MIN 的巨集定義中，並沒有直接將其定義為 -2147483648，而是 `(-INT_MAX - 1)`。
在以 32 位元為主的程式中，如果直接定義 INT_MIN 為 -2147483648，因為在 C 語言編譯器中，碰到 `-X` 的場合，會先找符合 `X` 的資料型態，再將其 negative，所以對 -2147483648 的處裡就會先尋找符合 2147483648 的資料型態，再將其 negative。因此，在編譯階段，編譯器會先發現到 2147483648 比常規的 int 來得大，之後就找到 long，但 long 是 32 位元的 signed，所以再接著找到可以容納的目標資料型態 unsigned。又因為 -2147483648 和 2147483648 有相同的二進位表示，所以最終就停止在 unsigned。
不過以上是 C90 的情況，如果在 C99 編譯的場合，編譯器最後找到的目標資料型態為 64 位元的 signed 資料型態 long long。
另一方面，以 64 位元為主的程式中，則會因為其是 64 位元表示，所以它的 long 會是 64 位元的大小。因此，在尋找符合 -2147483648 的資料型態地任務中，會找到 long 資料型態就停止。
換個角度來說，如果編譯 INT_MIN 為十六進位數 0x80000000 的話，那在以 32 位元或 64 位元的程式中，不管是 C90 或 C99 標準，都會找到 unsigned 後，就停止搜尋符合的資料型態。
那這會有什麼問題呢？從以上的描述，可以發現到不同的 C 語言標準，以及不同位元（N-bit）程式，甚至是不同的進位法，會因為 C 語言對數值做隱性轉換的原因，都對數值 -2147483648 **有不同的資料型態定義**，使得 -2147483648 成為[陷阱表示法](https://hackmd.io/@sysprog/CSAPP/https%3A%2F%2Fhackmd.io%2Fs%2FrJoxSsiuG#%E6%95%B8%E5%80%BC%E7%B3%BB%E7%B5%B1)。在這種場合，該程式只能在特定的機器上運行，而不能在所有的機器普遍運作，產生嚴重的錯誤。
在 CS:APP 作者提供的[公開文件](chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://csapp.cs.cmu.edu/3e/waside/waside-tmin.pdf)中，有舉了以下程式碼為例子：
```c
int dpos32 = (-2147483648 > 0);
int hpos32 = (0x80000000 > 0);
```
若將此程式編譯執行後，根據不同的編譯器版本，以及 word size，會得到 dpos 的結果為 0 或 1，表示十進位的數值也可能為 0 或 1；另一方面，十六進位數 hpos 的執行結果，不管編譯器版本和 word size 為哪個，皆穩定為 1。此實驗也突出了，若要定義有號二進位數的常數數值，需要格外的警惕該數值可能造成的影響。
- [ ] **signed 和 unsigned 的混用可能會造成整數溢位**
在 2002 年 FreeBSD 裡一個名叫 `getpeername()` 的 library function，被回報其實作存在安全性問題。其原實作簡化為以下：
```c
#define KSIZE 1024
char kbuf[KSIZE];
int copy_from_kernel(void *user_dest, int maxlen) {
int len = KSIZE < maxlen ? KSIZE : maxlen;
memcpy(user_dest, kbuf, len);
return len;
}
```
其中 `memcpy()` 函式的原始宣告為以下：
```c
void *memcpy(void *dest, void *src, size_t n);
```
乍看之下可能沒感覺到有什麼問題，但如果有工程師惡意的將負數值做為 `maxlen` 引數代入進 `copy_from_kernel()`，會發生什麼事呢？
我們假設 `maxlen` 的數值為負，那在對 `int len` 的賦值中，會因為 `maxlen < KSIZE` 的關係，使得 `maxlen` 的數值賦予給變數 `len`，變數 `len` 成為一個負數值。
接下來，變數 `len` 會被帶入進函式 `memcpy()` 的引數 `n` 中。但是，引數 `n` 的資料型態為 `size_t`，是一個 unsigned 類型的資料型態，因此原來的變數 `len` 會被 C 語言從 signed 隱性轉換為 unsigned，且不會改變其原本的位元表示。
此時，一個很嚴重的問題就出現了：假設此程式運行在 32 位元的裝置，因為變數 `len` 是負數的關係，所以其位元表示中的 sign bit 為 1。若將其隱性轉換為 unsigned 表示的話，則其數值至少為 2^31^，遠遠超過此程式定義的上限 `KSIZE`，使得 `memcpy()` 函式會以該規模的數值，將核心記憶體複製到 user's buffer 中，其中就會複製到只有核心才有權限讀取的記憶體空間，形成資安風險。
#### Expanding and Truncating the Bit Representation of a Number
* 將小的資料型態轉換為較大的資型型態的操作必須永遠成立。
* 對於一個數值的位元表示的**擴增**（Expanding）來說：
* 若該數值是 unsigned，對該數值的 MST 做 zero extension。
* 若為 signed，則對擴增的位元補為原本數值之 MST 的位元表示，此操作稱為 sign extension。
* 對於一個數值的位元表示的**縮減**（Truncating）來說：
* 不管其為 unsigned 或 signed 表示，位元表示的縮減都會直接從 MST 削除多餘的位元，且剩餘的位元表示不會做任何的更動。
* 在做資料型態的轉換時，若該操作**同時涉及到資料型態大小和無號數有號數轉換的場合**，在 C 語言中，會**先**轉換資料型態大小，**再**做無號數有號數之間的轉換。
* e.g. 假如有以下程式碼：
```c
short sx = -12345;
unsigned uy = sx;
```
則在 C 語言中，會先把 `short sx` 轉換成 `int sx`，接著再由 `int sx` 轉成 `unsigned int sx`，最後把結果 assigned 給 `unsigned uy`。
#### Advice on Singed versus Unsigned
* C 語言中對 signed 和 unsigned 之間的隱性類型轉換會使得一些非直覺的行為出現，導致程式出現難以察覺的 bug。
* 有一種避免出現類似的 bug 的方法是直接不採用 unsigned 數值，例如說 Java 就是如此。
* 但 unsigned 有不少的好處，例如說：
* 在系統程式中，可以使用 unsigned 型態紀錄 addresses。
* 包裝 words 為非數值意義的位元表示。
* 實作取餘數和乘法運算的數學模組。
### 2.3 Interger Arithmetic ( To be modified )
#### Unsigned Addition
* 以兩個非負 `w` 位元的整數做加法，會需要 `w + 1` 個位元做表示。
* 以上的這個情況，會導致**整數溢位**的發生。在 C 語言程式裡，整數溢位不會被回報為錯誤，且計算的結果會從 `w + 1` 個位元被縮減回 `w` 個位元。
* 偵測溢位的方式：令有兩非負 `w` 位元的整數 $x$ 和 $y$，兩數值之加法結果為 $s = x + y$，且 $s$ 在被 assigned 後必為 `w` 位元。若 $s < x$ 或 $s < y$，則表示此非負整數的加法出現了溢位。
* 以程式實作的角度，可以用 XOR 檢查是否出現溢位。
```c
unsigned int a, b, x;
x = a + b;
if ((x ^ a) >= 0 || (x ^ b) >= 0)
...
```
#### Two's-Complement Addition
* 和 unsigned 加法相似，以兩個 `w` 位元的整數做加法，會需要 `w + 1` 個位元做表示。
* 假設有兩個 `w` 位元的整數 $x$ 和 $y$，兩數值之加法結果為 $s = x + y$，且 s 在被 assigned 後必為 `w` 位元。則二補數加法的溢位會有以下情況：
* $x > 0$ 和 $y > 0$，且 $s <= 0$：此二補數加法結果是 positive overflow。
* $x < 0$ 和 $y < 0$，且 $s >= 0$：此二補數加法結果是 negative overflow。
* 簡單來說，**若兩數相加後的正負號和原本兩者都不同**，即代表**有整數溢位**的發生。
#### [阿貝爾群（Abelian group）](https://ccjou.wordpress.com/2011/09/16/%E7%B7%9A%E6%80%A7%E4%BB%A3%E6%95%B8%E8%A3%A1%E7%9A%84%E4%BB%A3%E6%95%B8%E7%B5%90%E6%A7%8B/)和群的特性
考慮整數集（$Z$）的情況，若要表示整數加法為群，則兩整數（$x$、$y$）的加法有以下的特性：
1. 封閉性：若 $x$ 和 $y$ 屬於 $Z$，則 $x + y$ 也屬於 $Z$。
2. 結合性：排序固定之三整數之合和其加法執行順序沒有關係。$$(x + y) + z = x + (y + z)$$
3. 存在一整數 0，使得任何整數與其相加皆不變。$$x + 0 = 0 + x = x$$
4. 任意加法都可「回復」，也就是說每一整數皆存在逆元。$$x + (-x) = (-x) + x = 0$$
綜合以上，我們可以稱整數加法為群。
若我們增加以下的條件：
5. 交換性：兩整數之和與其計算位置無關。$$x + y = y + x$$
則我們可以稱整數的加法為－阿貝爾群。
若整數的加法擁有群的特性，則可額外取得以下的特性：
* 每個整數元素是唯一的。
* 每個整數逆元也是唯一的；亦即，對於整數 $x$ 存在一個 $y = -x$，使得 $x + y = 0$。
其中，第二小點的特性，若以整數加法的角度來看，代表說每一組的整數加法，都有一組唯一對應的整數減法。
#### Unsigned and Two's-Complement Multiplication
* 以兩個 `w` 位元的整數做乘法，會需要 `2w` 個位元做表示，並在賦予回指定變數時會被縮減回 `w` 位元。
- [ ] **Multiplication can overflow without any notice being given to the program**
在 2002 年，Sun Microsystem 裡的 External data representation (XDR) library 被回報一件和乘法有關的整數溢位案例。
> [**CA-2002-25**](https://packetstormsecurity.com/files/26509/CA-2002-25.xdr.html)
> The xdr_array() function in the XDR library provided by Sun Microsystems contains an integer overflow that can lead to improperly sized dynamic memory allocation. Subsequent problems like buffer overflows may result, depending on how and where the vulnerable xdr_array() function is used.
以下是與當時實作相似的程式碼：
```c
void *copy_elements(void *ele_src[], int ele_cnt, size_t ele_size) {
void *result = malloc(ele_cnt * ele_size);
if (result==NULL) return NULL;
void *next = result;
for (int i = 0; i < ele_cnt; i++) {
memcpy(next, ele_src[i], ele_size);
next += ele_size;
}
return result;
}
```
在這支程式中需要注意的是關於 `void *result` 指標變數的宣告：
```c
void *result = malloc(ele_cnt * ele_size);
```
假設這支程式運行在 32 位元的裝置中，如果有工程師將 ele_cnt = 2^20^ +1，以及 ele_size = 2^12^ 帶入此條宣告，將會使得**只有 4096 bytes** 的記憶體被 allocated，而非 4,294,971,392 bytes 的記憶體，導致程式在運行到 for 迴圈時，會因為 `void *result` buffer 本身**無法容納**所有的 `void *ele_src[]` 二維陣列的資料，出現損毀其他裝置中的資料結構、裝置崩潰、或以下非預期的行為：
> [**CA-2002-25**](https://packetstormsecurity.com/files/26509/CA-2002-25.xdr.html)
> Exploiting this vulnerability will lead to denial of service, execution of arbitrary code, or the disclosure of sensitive information.
> Specific impacts reported include **the ability to execute arbitrary code with root privileges** (by exploiting dmispd, rpc.cmsd, or kadmind, for example). In addition, intruders who exploit the XDR overflow in MIT KRB5 kadmind may be able to **gain control of a Key Distribution Center (KDC)** and **improperly authenticate to other services within a trusted Kerberos realm**.
所以，在使用**記憶體分配**函式（e.g. `malloc`, `calloc`, etc.）時，必須注意帶入進引數的數值是否會出現溢位，且**不要直接以四則運算做為引數帶入**。
#### Multiplying by Constants
在本書的 2.1 節中，有介紹 C 語言支援 shift operation。通常來說，在 C 語言中，如果直接使用乘法（`*`）和除法（`/`），則會需要使用非常多的 clock cycle 去完成該操作，而若用 bit-level operations、addition、substraction、shifting，則會只要一個 clock cycle。因此，如果想要加速程式的運作，將乘除的程式撰寫思維轉為位元操作是最合適的選擇。
整數的乘法，可以分兩種情況探討：
* 被乘數剛好是 2 的冪（power of two）：直接對該數值使用 left shift。
* 被乘數不是 2 的冪（power of two）：根據被乘數的位元表示分批使用 left shift，並將個別結果相加。
* e.g. 假設要做以下的乘法運算：`x * 14`。在此例子中，被乘數的二位數表示為 14~10~ = 1110~2~，得知其可拆解為 14 = 2^3^ + 2^2^ + 2^1^。因此，我們可以將 `x * 14` 以 `(x << 3) + (x << 2) + (x << 1)` 做為代替。
使用 2 的冪的移位乘法依舊會產生 overflow，但就如同直接使用 `*` operator 一樣，C 程式會直接將多餘的位元做縮回操作。
#### Dividing by Power of 2
整數的除法，
### 2.4 Floating point ( To be modified )
#### IEEE Floating-Point Representation
#### Rounding
#### Floating-Point Operations
#### Floating-Point in C
---
## 文章閱讀及課程心得
---
## 課程教材研讀
### [你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-pointer)
---
## 專題的進度
> TODO:
> - [ ] 建立排序演算法的 Linux kernel module 版本。
> - [ ] 建立測試程式的 Linux kernel module 版本。
> - [ ] 建立以數值比較為主的環境測試排序演算法，以呼應在 kernel module 測試。
> - [ ] 了解亂數產生器並應用進測試中 (lab0-c, integration)。
> - [ ] 了解統計分析方法 (lab0-c)。
---
為何 C 語言的 int 是 signed?
signed vs. unsigned
int do_something()
strcmp - https://man7.org/linux/man-pages/man3/strcmp.3.html 為何有 3 種回傳值？]
equal or not => 只有 2 種
unsigned 的風險？
一個有號數意外結果的例子。
```c
int n = 10;
for (int i = n - 1 ; i - sizeof(char) >= 0; i--)
printf("i: 0x%x\n",i);
```
這個例子會造成無窮迴圈，因為 sizeof 會回傳值是 unsigned int 型態，i 變數也會被轉換為 unsigned 的形式，無號數 0 再減 1 就會變為 0xFFFFFFFF 而產生無窮迴圈。
(integer promotion, C99)
TODO: 第一週測驗二: Timsort 改進
* 測試程式: 涵蓋最佳和最差: https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ
* 改進的策略？
* 標的: circular doubly-linked list => 問：circular doubly-linked list 相較於 singly-linked linked list 有何優勢？
* 準備 Linux kernel module 來測試/驗證 => LKM 可避免 preemption 和 interrupt，且可有較高的時間精度 (high-resolutin timer，可精準到 us, ktime)
* 貢獻？提出針對 Linux 核心 `list_sort.c` 的改進 (show me the code!)
Sign in with Wallet
Connect another wallet