# 2024q1 課堂教材心得隨筆
contributed by < [`pao0626`](https://github.com/pao0626) >
## [你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)
### bit-wise 運用:
* 不使用 if-else 分支來處理字元，詳見 ASCII code。
* `('A' | ' ')` 轉成小寫得到 a。
* `('a' & '_')` 轉成小寫得到 A。
* `('a' ^ ' ')` 大小寫互換得到 A。
* swap 實作，節省暫存器使用和記憶體空間。
```c
void xorSwap(int *x, int *y) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
```
* Reverse integer bitwise，應用在 LSB <-> MSB 轉換，如開發網路。也可以用於加密。
* XOR 操作可用於圖片加密。
* 巨集 DETECT 偵測 NULL，可以一次比較多個字節，以 32bit 為例
```c
define DETECT(X) (((X) - 0x01010101) & ~(X) & 0x80808080)
```
只有當 $X=0$ 的時候會產生 0x80808080 的結果，只要判斷這個數字是否存在就能找到 ’\0’ 位置。
* 加法實現， `a ^ b` 計算相加但不進位， `(a & b) << 1` 進位但不相加。
其餘可見[你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)。內文提及多種 bitwise 操作，以及兩種位移運算的兩種未定義狀況如下:
* 右移一個負數時，可能是邏輯位移或是算術位移，C 語言標準未定義 (gcc 採算數位移)。
* 左移超過變數長度，其結果未定義;
```cpp
int i=0xFFFFFFFF;
i = i << 32; // 此結果未定義
```
第二種未定義情況在[位元旋轉](https://hackmd.io/@sysprog/bitwise-rotation#%E4%BD%8D%E5%85%83%E6%97%8B%E8%BD%89)中有提到。
```c
static inline __u32 rol32(__u32 word, unsigned int shift) {
return (word << shift) | (word >> (32 - shift));
}
```
當 shift 為 0 時， word >> 32 就會遇到 undefined behavior，因此取代如下:
```c
static inline __u32 rol32(__u32 word, unsigned int shift) {
return (word << shift) | (word >> ((-shift) & 31));
}
```
後續更完善的改進，對 32 位元的 shift 超出 31 時的行為予以調整，採取 mod 操作:
```c
static inline __u32 rol32(__u32 word, unsigned int shift) {
return (word << (shift & 31)) | (word >> ((-shift) & 31));
}
```
需要注意的是，並非所有資料寬度的位元旋轉都要完全遵守上述模式，才可滿足想要的正確性，
考慮 C 語言標準的 integer promotion ，8 bits word 會被提升成 32 bits int 型態，所以可以保持原先寫法:
```c
static inline __u8 rol8(__u8 word, unsigned int shift) {
return (word << shift) | (word >> (8 - shift));
}
```
最後，位元旋轉可被用在 SHA-256 等密碼學上。
### 使用 Count Leading Zero 計算 $log_2 N$。
* gcc 提供 built-in Function 來計算 `clz` ，因此 log2 的程式碼如下:
```c
#define LOG2(X) ((unsigned) \
(8 * sizeof (unsigned long long) - \
__builtin_clzll(X) - 1))
```
其結果等於 8 * 8 - clz - 1，即可得出 64-bit 的 log2 結果。
其中 `sizeof (unsigned long long)` 這個表達式的目的是求得此類型在當前編譯環境中的字節大小。
* `clz` 實作方法有很多種，其中 binary search technique 的方法滿酷的:
```c
int clz(uint32_t x) {
if (x == 0) return 32;
int n = 0;
if (x <= 0x0000FFFF) { n += 16; x <<= 16; }
if (x <= 0x00FFFFFF) { n += 8; x <<= 8; }
if (x <= 0x0FFFFFFF) { n += 4; x <<= 4; }
if (x <= 0x3FFFFFFF) { n += 2; x <<= 2; }
if (x <= 0x7FFFFFFF) { n += 1; x <<= 1; }
return n;
}
```
變數 n 紀錄有幾個 0，以第一個判斷式為例，如果左側 16 bit 皆為 0，將 n 增加 16 後繼續找尋右側 16 bit 還有個 0，反之不做任何處理，往左側找。
* `ffs` 會回傳給定數值的 first bit set 的位置(從右至左)。
## [你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80%EF%BC%9A%E8%A8%98%E6%86%B6%E9%AB%94%E7%AE%A1%E7%90%86%E3%80%81%E5%B0%8D%E9%BD%8A%E5%8F%8A%E7%A1%AC%E9%AB%94%E7%89%B9%E6%80%A7)
### 背景知識
* 指標篇有提過，`void *` 存在的目的就是為了強迫使用者使用顯式 (explicit) 轉型。
* glibc 提供 `mallinfo()`，`malloc_stats()` 和 `malloc_info()` 函式，可顯示 process 的 heap 資訊，前者返回結構體提供動態記憶體分配訊息，次者不需要参数，也不返回任何值，直接打印資訊。後者需要文件指针。
### 記憶體相關
malloc 給 valid pointer，等真正使用時才知道作業系統是否會 OOM。可比喻成一張支票，能不能拿來開等到兌現才知道。以下順便整理一些常見錯誤:
* Segmentation Fault
定義：發生在進程試圖訪問其記憶體段之外的記憶體，或是無權訪問的記憶體區域時。包括訪問未分配的記憶體、對NULL指針的解引用，或試圖寫入只讀記憶體。
結果：操作系統將中止錯誤的程序，通常伴隨一個核心轉儲 (core dump)，有助於開發者後續的調試過程。
* Out of Memory (OOM)
定義：發生在系統無法滿足進程的記憶體分配請求時。在過度分配記憶體或系統可用記憶體耗盡時常見此錯誤。
結果：Linux 等操作系統可能啟動 OOM Killer，選擇並終止占用大量記憶體的進程，以釋放資源並保持系統運行。
* Stack Overflow
定義：發生在進程的呼叫棧 (call stack) 耗盡其為每個線程分配的記憶體空間時。這通常是因為過度的遞歸呼叫或過大的棧分配（如大數組）。
結果：程序也會被操作系統中止。
* 動態配置產生的空間 Heap ，和資料結構的 Heap 無關。
### data alignment
目的: 犧牲記憶體空間，來減少存取次數。
* 使用 `#pragma pack(push, 1)` 和 `#pragma pack(pop)` 來設定範圍內的結構體對齊方式為 1 字節。
* `sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'` 中 `sh -c` 調用 shell 執行一串命令，`echo 3` 清除 pagecache、dentries 及 inodes (1 只清除 pagecache，2 只清除 dentries 和 inodes)，而最後的 `/proc/sys/vm/drop_caches` 是 Linux 實時系統信息目錄下的一個可寫入文件。
* Pagecache: 記憶體中的頁（通常 4KB 大小），使用 LRU 更新。
* Dentries: directory entry 的縮寫，用於快取檔案系統的目錄結構訊息，即檔案名稱與inode之間的映射關係，減少對硬碟的讀取操作。
* Inode: 檔案系統中的重要概念，包含檔案的元數據，如檔案的大小、權限、修改時間、資料區塊位置等。每個檔案或目錄在檔案系統中都對應一個唯一的inode。
* 在 64-bit 的系統下，malloc 會以 16 bytes 進行對齊。
* Compare-and-Swap (CAS) 是一種用於多執行緒編程中的原子操作。
- [ ] 包含三个主要的参数：
1. 記憶體位置（Memory Location）：進行比較和替換操作的記憶體位址。
2. 期望值（Expected Value）：預期在該記憶體位置上找到的值。
3. 新值（New Value）：如果記憶體位置的當前值與期望值相匹配，將要儲存的新值。
- [ ] 執行流程：
1. 檢查目標記憶體位置的目前值是否與期望值相等。
2. 如果相等，將記憶體位置的值更新為新值。
3. 無論更新是否成功，都會傳回記憶體位置的原始值（即操作之前的值）。
* 由於記憶體對齊特性，節點的操作中可以將結構體位址的最後一個 bit 標示為是否刪除，以避免 concurrent 下導致的新增刪除錯誤，詳見[內文](https://hackmd.io/vQgqRmTmSBSbR_Wg-wnu8A?view#%E6%A1%88%E4%BE%8B%E5%88%86%E6%9E%90-concurrent-ll)。
### glibc 的 malloc/free 實作
> 額外參考 [glibc malloc 原理分析](https://www.openeuler.org/zh/blog/wangshuo/Glibc%20Malloc%20Principle/Glibc_Malloc_Principle.html)
* Arena (分配區)：
是一個結構體，每個執行緒在申請記憶體時會取得一個。分為 main Arena 與 thread Arena，前者僅有一個，其餘皆為thread分配區。當新建立的執行緒需要申請記憶體時，將從一個全域的鍊錶中取得一個空閒的分配區，如果沒有得到且分配區數量沒有超過最大值（M_ARENA_MAX），malloc 將會新建一個。
* Main Arena：第一個被初始化和使用的 arena。首先使用 brk() 系統呼叫從作業系統中取得記憶體。當空間不足會使用 brk() 來延伸其邊界，，預設一次 132 KiB。
* Thread Arena：減少多執行緒環境中對 main arena 的競爭，每個執行緒可能會有自己的 arena。通常透過 mmap() 系統呼叫直接映射內存，預設 map 1 MiB，分配給 heap 132 KiB，尚未分配給 heap 的空間設定為不可讀寫，1 MiB 使用完後會再 map 一個 1 MiB 的新 heap。
* malloc_state (Arena Header)：
每個 arena 一個。紀錄 arena 的資訊，包含 bins (free list), top chunk(分裂新 chunk 的地方)等。其中 main arena 的 header 在 data segment(static)，thread 的在 heap 中。
* heap_info (Heap Header)：
每個 thread arena 可能有超過一個 heap。heap_info 在每個 heap 中紀錄前一個heap、所屬的 arena 等。所以 main arena 沒有，thread arena 可能有多個。
* Chunk（塊）:
是記憶體分配中的一個基本單位，是從 heap 中劃分出來。 是 user data 儲存的地方，又依使用狀態分為 free 與 allocated。紀錄 chunk 本身的 size 與型態，以及相鄰的 chunk 資訊。
* Bin：
是紀錄 free chunks 的資料結構(free list)。
* Fast Bin：管理小塊 chunk（64 bytes）的鍊錶。
* Unsorted Bin：fastbin整合的chunk和最近 free 的 small / large chunk，不分大小。
* Small Bin：chunk < 512 bytes。
* Large Bin：chunk >= 512 bytes。
* malloc 流程:
* 調整 malloc size : 加上 overhead 並對齊。
* 從 fastbin 找對應大小。
* 從 smallbin 找對應大小。
* 合併 fastbin 歸入 unsorted bin。
* 從 unsorted bin 找對應大小，若不符合則插入相應的 small / large bin 中。
* 從 large bin 找對應大小。
* 使用 top chunk，若 size 不夠則合併 fastbin，若仍不夠則 system call。
* free 流程:
* 檢查是否為 mmap，若是則 munmap。
* 是否能放入 fastbin，若是則返回。
* 緊鄰 top chunk 則合併。
* 合併相鄰未使用 chunk 後放入 unsorted bin。
* 檢查回收 chunk 是否超過閾值，超過則觸發收縮操作，如果是 main arena 則透過 brk 收縮，否則直接回收整塊 heap 或是收縮 top chunk。
## 課堂討論
float point 如何透過 bit-wise 來乘 2，這需要考慮在C語言中，直接對浮點數的位元模式進行位元操作是不允許的，所以需要先透過指針類型轉換或是 `memcpy` 的方法轉換成 unsigned int 型態。
以下面的打印資訊為例， `40e00000` 的二進制為 `01000000111000000000000000000000`，確實複合 7.0 的 IEEE 754 表示。
```c
#include <stdio.h>
float float_mul2(float x) {
printf("%f\n", x); // 印出 7.00
unsigned int *bits = (unsigned int*)&x;
printf("%x\n", *bits); // 印出 40e00000
*bits += 1 << 23;
printf("%x\n", *bits); // 印出 41600000
return x;
}
int main() {
// Write C code here
float a = 7.0;
printf("%f\n", float_mul2(a)); //印出14.00
return 0;
}
```
Sign in with Wallet
Connect another wallet