---
tags: linux2023
---
# Linux kernel
# 數值系統
主要的問題是：為什麼 `1-0.1 = 0.9` 但是 `0.1-0.01 = 0.09000000000000001 ` 呢?
跳過的炫技章節
- 電腦不只有二進位，還有三進位(balanced ternary)
- 阿貝爾群
- 各種 integer overflow 的案例
需要特別去了解的是
- IEEE 754 浮點數相關的運算
- bitwise 的操作
## 二補數
怎麼樣在數值系統中表現負數的概念呢？一般正常人先想到的應該是
假設我們有 `3bit` 的空間
**方法一**：拿一個 bit 作為正負號。
```
000 = +0
100 = -0
001 = +1
101 = -1
```
缺點：這樣 +1 + (-1) 並不會等於零。
**方法二**：希望+1 跟 -1 加起來是 0
最好是用補數的概念去設定，如下。這樣 +1 + -1 就會是 -0(111)
```
001 = +1
110 = -1
000 = +0
111 = -0
```
優點：這樣加法就直接是把兩個數的 bit 相加就可以。
缺點：還是有兩個 0 的定義。
應用：訊號傳輸的時候可以使用補數的概念作驗證碼
**方法三**：二補數，現在電腦都用這種，下面開一個章節介紹
### 什麼是二補數
大概念是，我不在乎溢位的部分，希望加起來就真的是 +1 + -1 真的是零，那這樣子的話 `+1(001b)` 一定是這樣，那就應該是 `-1(111b)`
```
001 = +1
111 = -1
------
[1]000 = 0
```
那我們從零出發，我希望
`1 + (-1) = 1000b`
`2 + (-2) = 1000b`
```
000 = 0 ...
001 = 1 ... -1 = 111 = 7
010 = 2 ... -2 = 110 = 6
011 = 3 ... -3 = 101 = 5
100 = 4 ... -4 = 100 ??
```
問題是：那 100b 到底是 +4 還是 -4 ?
答案是 +4 但我不知道為什麼
- **有趣的性質(1)**: -3 跟 +5 的意思一樣：
由於 2 +(-3) 跟 2 + 5 的定義一樣(都是 010 +011 = 111)，所以
```
+4 = -4 效果一樣
+5 = -3 效果一樣
+6 = -2 效果一樣
+7 = -1 效果一樣
```
- **有趣的性質(2)**: 數字的所有bit 反過來，然後+1 就會是他的負數：
例如 `2(010b)` 的 coml 是 `-3(101b)`， -3 +1 = -2
- **有趣的性質(3)**: 承上， a - b = a + ~b +1
也就是 -2 = ~(+2) + 1 ，這個可以應用在電路上，加法器跟減法器就只需要共用同一個電路。
- **有趣的性質(4)**: 剛好，最高位數如果是 1, 那這個數字就是負數
綜合以上幾點，取絕對值在c語言中可以這樣寫
```c
#include <stdint.h>
int32_t abs(int32_t x) {
int32_t mask = (x >> 31);
return (x + mask) ^ mask;
}
```
解釋：
1. `x>>31` 如果 x 是有號數(負數)，他前面會幫忙補 1, mask = 0xFFFF_FFFF = -1
3. `x>>31` 如果 x 是無號數，他前面會幫忙補 0, mask = 0x0000_0000 = 0
4. `a ^ 0xFFFF` 的意思就是 `~a` 就是把所有 bit 都反過來的意思
### 那電腦怎麼知道 (1111_1111) 是 255 還是 -1 ?
答案是電腦也不知道。反正對電腦來說計算方式都一樣。所以看你的定義，如果是無號數，那電腦就會顯示 255 ，如果是有號數，那電腦就會顯示 -1。唯一電腦計算需要判斷的時候就是，當你 8bit 要變成 16bit 的時候。他要幫你判斷：
- unsigned: 幫你補成 0000_0000_1111_1111 還是 255
- signed: 幫你補成 1111_1111_1111_1111 還是 -1
補充，在 intel x86 系統資料搬移指令 (Data Transfer Instructions)有三種：
- mov: 搬移兩個等寬的記憶體資料
- mov des, src (把 src 上面的資料搬到 des 上)
- movzx: 搬移窄的資料到寬的上，前面補零，給無號整數用
- movzx r32, r/m8 (把 r/m8 8bit的資料搬到 r32 上)
- movsx: 搬移窄的資料到寬的上，前面補 1，給有號整數用
- movsx r32, r/m16 (把 r/m16 16bit的資料搬到 r32 上)
### 資訊安全上的應用
#### 案例一，有號數傳給無號數
根據 [linux man memcpy](https://man7.org/linux/man-pages/man3/memcpy.3.html) `len` 這個參數應該是一個無號數，如果輸入負數，就可以略過這個大小檢查。
```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;
}
```
#### 案例二，無號數相乘
2002 年 External data representation (XDR)
如果帶入 `ele_cnt = 2^20 +1`, `ele_size = 2^12` 相乘之後就會 overflow 。但是我有檢查 null 阿，有什麼問題？
根據 [malloc](https://man7.org/linux/man-pages/man3/malloc.3.html) 的說明:
> The malloc(), calloc(), realloc(), and reallocarray() functions
return a pointer to the allocated memory, which is suitably
aligned for any type that fits into the requested size or less.
On error, these functions return NULL and set errno. Attempting
to allocate more than PTRDIFF_MAX bytes is considered an error,
as an object that large could cause later pointer subtraction to
overflow.
就算發生問題的時候，
```c
void *copy_elements(void *ele_src[], int ele_cnt, int 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;
}
```
### Bitwise 操作
#### 案例一: (a + b) /2
風險： `(a+b)/2` 會 overflow
解決方法： `(a-b)/2+b` 這樣就不會 overflow 了
也可以使用：
```c
result = (a+b)/2
= (a+b)>>1 // 除以2 跟 >>1 是一樣的意思
= ((a^b)+(a&b)<<1)>>1 // a^b 是加法，a&b 是進位
= (a&b) + ((a^b) >>1)
```
解釋
```c
(0101)b = 5 = x
(0110)b = 6 = y
(0011) = x^y // 加法的概念
(0100) = x&y // 進位的概念
(1000) = (x&y)<<1 // 進位的概念
(0011) = x^y
(1000) = (x&y)<<1
------------
(1011) = (x^y) + ((x&y)<<1) = x+y = 11
```
#### 案例二：更快速的 strcpy
這邊：[newlib/newlib/libc/string/strcpy.c](https://github.com/eblot/newlib/blob/master/newlib/libc/string/strcpy.c)
```c
#if LONG_MAX == 2147483647L
#define DETECT(X) \
(((X) - 0x01010101) & ~(X) & 0x80808080)
#else
#if LONG_MAX == 9223372036854775807L
#define DETECT(X) \
(((X) - 0x0101010101010101) & ~(X) & 0x8080808080808080)
#else
#error long int is not a 32bit or 64bit type.
#endif
#endif
```
先利用 `<limits.h>` 中的 `LONG_MAX` 檢查系統是 32bit 還是 64bit 系統，定義 `DETECT(X)` 這個功能
但這個我根本看不懂。他可以找到 `\0` 的位置，但我看不懂，影片也沒講[QM]
https://hackmd.io/@sysprog/c-numerics
理解過程
((X) - 0x01) & ~(X) & 0x80)
- `x-1 : bit7 = 1 (if x>=0x81 or x=0) `
- `x-1 : bit7 = 0 (if x<=0x80) `
- `~(X) & 0x80 : bit7 = 1 (if 0 <= x <0x79)`
- `~(X) & 0x80 : bit7 = 0 (if x>= 0x80)`
- `-> if = 1 , only x = 0`
# 還沒想到標題
名詞說明：
- LKM: Linux loadable kernel module
## Character Device Drivers
在UNIX中，用戶通過特殊的設備文件(file)訪問硬件設備。這些文件被分組存放在/dev目錄下，而系統呼叫（如open、read、write、close、lseek、mmap等）讓作業系統與物理設備互動。
### Device 有兩種
字符設備(character device)
- 通常用在傳輸 user 應用程式的資料
- 它們的行為類似管道(pipe)或串行端口(stram)，也就是可以逐個字符的方式讀取或寫入字節。
- 這個是許多典型的驅動程序框架，例如序列通信（serial communications）、獲取影音所需的驅動程序。
- 另外一種 device 的選擇是 block devices
Block device
- 行為方式跟類似文件
- 可以允許緩衝數據查找操作（讀、寫、查詢(seeks)）
兩種 device 都可以透過連結到 file system tree 來訪問，也就是直接去`dev/ebbchar` 之類的地方就可以訪問到你的 device
```bash=
elmer@elmer-lab:/dev$ ls -l /dev/nvme0
crw------- 1 root root 239, 0 九 12 21:30 /dev/nvme0
```
接下來會描述一個簡單的字符驅動，可以在Linux用戶空間和核心模組之間傳遞信息。我們會用 C 寫一段程式（當然是用戶空間上的應用程式），傳一個字串給核心模組，然後模組會回傳這個字串本身，跟這個字串有幾個字母這樣。
後面講到同步問題，我們稍後會用互斥鎖(mutex)來解決。
在描述本文中驅動程序的源代碼之前，需要討論一些概念，如設備驅動程序的主要和次要號碼，以及文件操作數據結構。
### 主要號碼跟次要號碼
設備驅動程式傳統上，擁有一組唯一的主要號碼和次要號碼。
- 主要號碼識別設備類型(IDE硬盤、SCSI硬盤、串行端口之類的)
- 次要號碼識別由該驅動程序提供服務的每個物理設備。
- 一般來說，一個驅動程序將有一個關聯的主要號碼，並負責該主要號碼關聯的所有次要號碼。
``` bash=
/dev$ ls -l |grep nvme
crw------- 1 root root 239, 0 九 12 21:30 nvme0
brw-rw---- 1 root disk 259, 0 九 12 21:30 nvme0n1
brw-rw---- 1 root disk 259, 1 九 12 21:30 nvme0n1p1
brw-rw---- 1 root disk 259, 2 九 12 21:30 nvme0n1p2
brw-rw---- 1 root disk 259, 3 九 12 21:30 nvme0n1p3
```
例如： /dev/nvme0 的主要號碼是 239，`/dev/nvme0n1` 的主要號碼是 259
- 主要號碼由核心用於在訪問設備時識別正確的設備驅動程序。
- 次要號碼的角色取決於設備，並在驅動程序內部處理。
- 我們可以在 /dev 這個資料夾下查看大家的號碼
- 第二行的 crw 的 c 代表字符設備。
- 第三行的 brw 的 b 代表 block device
`mknod /dev/mycdev c 42 0`
`mknod /dev/mybdev b 240 0`
### 字符設備的數據結構
在核心中，字符類型的 device 由`struct cdev`表示。大多數驅動程序操作使用三個重要的結構：
- struct file_operations
- struct file
- struct inode
#### file_operations
剛剛有提到，用戶會以 device-type file 的方式，傳遞訊息給 cdev driver 。所以，實作 cdev 驅動就是實作與文件特定的系統調用：open、close、read、write、lseek、mmap等。
這些操作在struct file_operations結構的字段中描述：
```c=
#include <linux/fs.h>
struct file_operations {
struct module *owner;
loff_t (*llseek) (struct file *, loff_t, int);
ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);
[...]
long (*unlocked_ioctl) (struct file *, unsigned int, unsigned long);
[...]
int (*open) (struct inode *, struct file *);
int (*flush) (struct file *, fl_owner_t id);
int (*release) (struct inode *, struct file *);
[...]
```
我們會注意到，這些函數簽章（function signature）與用戶使用的系統呼叫不同。作業系統位於用戶和設備驅動程序之間，簡化設備驅動程序中的實作。
- open 這個函式，不接收路徑參數或控制文件打開模式的各種參數。
- 同樣，read、write、release、ioctl、lseek等操作不接收文件描述符(file descriptor)作為參數。
- 相反，這些函式的參數是兩個結構：
- file
- inode
- 這兩個結構都代表一個文件（但是是不同的角度）。
大部分的參數都有一個簡單明瞭的含義：
- file 和 inode 識別設備類型文件(device type file)；
- size是要讀取或寫入的字節數；
- offset是要讀取或寫入的偏移量（需要相應更新）；
- user_buffer是從中讀取/寫入的用戶緩衝區；
- whence 是查找(seek)的方式（搜尋的開始位置）；
- cmd和arg是使用者發送給ioctl調用（IO控制）的參數。
#### inode 和 file 結構
inode
- 從檔案系統的角度來看，inode 代表一個文件。
- inode 的屬性包括大小、權限、與被存取的次數等。
- inode 只會對應到檔案系統中唯一的那個檔案
file
- file 這個結構也是一個檔案，但比較接近 user 的角度
- file 這個結構的屬性有 inode、文件名、文件打開屬性、文件位置。
- 在任何時間，所有被打開的文件都有一個關聯的 file 結構。
為了理解 inode 和 file 之間的區別，使用物件導向的比喻：如果我們把 inode 當作 class ，那麼文件就是 object，也就是 class inode 的實例。inode 代表文件的靜態形象（inode沒有狀態），而文件代表文件的動態形象（文件具有狀態）。
話說回來，那個驅動程式，這兩個實體幾乎總是標準的使用方式：inode 用於確定執行操作的設備的主要號碼和次要號碼，而文件用於確定打開文件時使用的標誌，還用於保存和訪問（以後）私有數據。
文件結構包含許多 fields，包括：
- `f_mode`，指定讀（`FMODE_READ`）或寫(`FMODE_WRITE`)
- `f_flags`，指定文件打開標誌（`O_RDONLY`、`O_NONBLOCK`、`O_SYNC`、`O_APPEND`、`O_TRUNC等`
- `f_op`，指定與文件關聯的操作（指向 file_operations 結構的指針
- `private_data`，一個指針，可以使用它來存儲設備特定的數據；指針將由寫程式的人分配的內存位置初始化。
- `f_pos`，文件內的偏移量
inode結構包含許多信息，其中包括一個i_cdev字段，該字段是指向定義 cdev 的結構的指針（當inode對應到字符設備時）。
參考資料
- https://linux-kernel-labs.github.io/refs/heads/master/labs/device_drivers.html
Sign in with Wallet
Connect another wallet