---
title: 記憶體管理、對齊及硬體特性
tags: C 語言筆記
---
## 記憶體管理、對齊及硬體特性
### 複習指標
* void * 的設計，是為了強制開發者必須透過 explicit (顯式) 或強制轉型，才能存取最終的 object，否則就會丟出編譯器的錯誤訊息，從而避免危險的指標操作
### Data Alignment: address of a data can be evenly divisible by 1, 2, 4, 8 or any power of 2 byte
* 因為 cpu 抓資料是一次一個 chunk 的，所以有可能會有以下狀況導致本來只需要讀一次變成要讀兩次
* Structure Member Alignment.
* 規則:
* 前面的地址必須是後面的地址正數倍,不是就補齊
* 整個Struct的地址必須是最大字節的整數倍
* 範例一:
```c=
struct C
{
char b;
double a;
short c;
};
// sizoof(C) = 24 byte，Alignment = 8 byte
```
* 範例二:
* #pragma pack 是用來指定資料的對齊方式
* #pragma pack (n): 按照 n byte 對齊
* #pragma pack (): 還原之前的設定
* #pragma pack (push,n): 是指把原來對齊方式設放入 stack，並設定新的對齊方式，這邊是 n byte
* #pragma pack(pop): 回到上一個對齊方式
```C=
#pragma pack(2)
#pragma pack(push, 1)
typedef struct S6 {
char m1; // 1-byte
double m2; // 8-byte
}s6;
#pragma pack(pop)
typedef struct S7 {
char m1; // 1-byte
// padding 1-byte space here
double m2; // 8-byte
}s7;
printf("%d\n", sizeof(s6));
printf("%d\n", sizeof(s7));
```
* 範例三
* [bit-field](https://zhuanlan.zhihu.com/p/354232756): 可以節省儲存空間
* 即使整個 box 只有 8 bits，但是 C 的基本單位是 4 byte(x86)，所以 box 的 大小是 4 byte
```c=
struct box
{
unsigned int a: 1;
unsigned int : 3;
unsigned int b: 4;
};
// sizeof(box) is 4 byte
```
* bit-filed 對齊: struct 的成員不允許跨越兩個unsigned int 的邊界
* field1 + field2 = 34 Bits，超出 32 Bits, 編譯器會將 field2 移位至下一個 unsigned int 單元存放，field1 和 field2 之間會留下一個 2 Bits 的空隙，field3 ==緊跟在 field2 之後==，該結構現在大小為2 * 32 = 64 Bits
```c=
struct stuff
{
unsigned int field1: 30;
unsigned int field2: 4;
unsigned int field3: 3;
};
```
* 可以用 0 來 padding
* 這裡 field1 與 field2 之間有一個 2 Bits 的空隙，field3 則存儲在下一個 unsigned int 中，該結構現在大小為 3 * 32 = 96 Bits
```c=
struct stuff
{
unsigned int field1: 30;
unsigned int : 2;
unsigned int field2: 4;
unsigned int : 0;
unsigned int field3: 3;
};
```
### Memory locality
* temporal locality：使用之前使用過的資料
* spatial locality：使用附近的資料
* 範例一
* good locality
```c=
int sum_array_rows(int a[M][N])
{
int i, j, sum = 0;
for (i = 0; i < M; i++)
for (j = 0; j < N; j++)
sum += a[i][j];
return sum;
}
```
* bad locality
```c=
int sum_array_cols(int a[M][N])
{
int i, j, sum = 0;
for (j = 0; j < N; j++)
for (i = 0; i < M; i++)
sum += a[i][j];
return sum;
}
```
* 範例二
* struct
```c=
#define N 1000
typedef struct {
int vel[3];
int acc[3];
} point;
point p[N];
```
* good locality
```c=
// good locality
void clear1(point *p, int n)
{
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < 3; j++)
p[i].vel[j] = 0;
for (j = 0; j < 3; j++)
p[i].acc[j] = 0;
}
}
```
* bad locality
```c=
void clear2(point *p, int n)
{
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < 3; j++) {
p[i].vel[j] = 0;
p[i].acc[j] = 0;
}
}
}
```
### glibc 的 malloc/free
#### arena and thread
* arena 即為 malloc 從系統取得的連續記憶體區域，分為 **main arena** 與 **thread arena** 兩種:
* main arena: 主執行緒第一次呼叫 malloc 或 new 之後，系統會呼叫 brk() 給程式分配 132kb 的 heap 空間，這 132kb 的空間叫做 Arena ，因為由主執行緒分配的所以叫做 main arena
* thread arena:
* 在 main 裡面又呼叫了一個子程序作為 new thread ，這時這位 thread 先生才會創立屬於自己的 thread arena。
* 使用 mmap() 取得新記憶體，預設 map 1 MB，分配給 heap 132 KB，尚未分配給 heap 的空間設定為不可讀寫，1 MB 使用完後會再 map 一個 1 MB 的新 heap，但 arena 的總數有限制，超過時 threads 會開始共用 arena
* 可能有多個 heap
* Three Heap data structures
* malloc_state (Arena Header) :
* 每個 arena 只有一個
* 紀錄 arena 的資訊，包含 bins (free list), top chunk, last remainder chunk 等等 allocation/free 需要的資訊
* main arena 的 header 在 data segment(static)
* thread arena 的 header 在 heap 中
* heap_info (Heap Header) :
* 在 thread arena 中，每個 arena 可能有超過一個 heap。紀錄前一個heap、所屬的 arena、已使用/未使用的 size
* 在thread arena的低地址
當 thread arena 的空間不夠用時，他會去 malloc 一塊並且讓它與 thread arena 相連結
main arena 不用這種方式擴充記憶體，故沒有 heap_info
* malloc_chunk (Chunk Header) :
* 一個 heap 被分為許多區段，稱為 chunk，是 user data 儲存的地方，又依使用狀態分為 free 與 allocated。紀錄 chunk 本身的 size 與型態
Main arena vs Thread arena :
* malloc_chunk 代表 每個 chunk 的 Header
Multiple heap Thread arena :
* Segment 2 的 heap_info 有 ptr 指向 前一個 heap (Segment 2)
* Top 指向最新的的 heap 的 top chunk
#### Chunk
對照上圖可以發現 chunk 有分種類
chunk 的大小在 32 bit 下最小 16 bytes，對齊 8 bytes；64 bit 下最小 32 bytes，對齊 16 bytes
需要至少4個 word 作為 free chunk 時的 field
* Allocated chunk:
* prev_size : 如果前一個 chunk 是 free chunk，包含前一個 chunk 的 size，若是 allocated，則包含 user data
* size : 此 chunk 的大小，最後 3 bit 作為 flag 使用
* PREV_INUSE ( P ) : 前一個 chunk 是 allocated
* IS_MMAPPED (M) : 當前的 heap 是透過 mmap 取得的獨立區塊
* NON_MAIN_ARENA (N) : 若當前 arena 為 thread arena 則設為1
* Free chunk
* allocated chunk 釋放記憶體空間後會變成的 chunk
* prev_size : 沒有兩個free chunk可以相鄰，因為兩個 free chunk 會合併，所以 prev_size 只會出現在 fast bin 的情況下
* 下一個 chunk 的 PREV_INUSE flag 平時是不 set 的(因為下一個 chunk 一定是 allocated，而 allocated chunk 的 size 是已經知道的了，所以不用特別去記)
* fd(Forward pointer) : 指向在同一個 bin 中的下一個 chunk
* bk(Backward pointer) : 指向在同一個 bin 中的上一個 chunk
* 每個 free chunk 都可以看到四個 feature，prev_chunk、next_chunk、fd、bk，前兩個是記憶體中相鄰的 chunk，避免記憶體太過碎裂化所以我們需要紀錄並且合併，fd、bk則是 bin 中的
* Top chunk
* 放在 arena 頂端剩下未分配用的 chunk，所以 malloc 可以用 top chunk 夠不夠用來判斷要不要向 kernel 呼叫多餘的空間
* 不屬於任何 bin，只會在 bin 中沒有適合的 free chunk 時才服務，但是如果 user 要求的空間也大於 top chunk，top chunk 就會利用 sbrk 或 mmap 等函式作 syscall
* top chunk 會盡可能地跟其他 chunk 合併，如果有個緊鄰 top chunk 的 chunk 被 free，就會合併到 top chunk 中，因此 top chunk 的 PREV_INUSE 一定是 1，因為如果前一個被 free，一定會被合併進來
* Last Remainder Chunk
* 最近一次分割的 large chunk，被用來滿足 small request 所剩下的部分
* 如果申請的 size 屬於 small bin 的，但是又不能精確找到合適 chunk 的情況下，也就是採用 best fit（剛好符合的大小），這樣會 split chunk 成兩部分，一部分當作 return chunk，另一部分形成 last remainder chunk，插入到 unsorted bin 中
* 在使用 fast bin 和 small bin 分配失敗後，會嘗試從 unsorted bin 中分配，這時候如果滿足下面幾個條件：
* 申請的 size 在 small bin 的範圍內
* unsorted bin 僅有一個 free chunk
* the only free chunk 是 last_remainder
* the only free chunk size 滿足進行 split
* 如果以上四個條件同時滿足，那麼就將 the only free chunk 進行 split，一部分當 return chunk，剩餘的部分作為新的 last remainder chunk，插入到 unsorted bin 中
#### Bins
* 主執行緒呼叫 free 之後，程式的 heap 空間並不會被釋放掉，而是由 glibc 的malloc函式庫管理，依 chunk size 將釋放的 chunk 新增到 main arena 中對應的 bin
* 要做 malloc 時會透過 bin 的 list data structure 加速選擇適合的 chunk
* bins 是紀錄 free chunks 的資料結構(freelist)，依據其大小和特性分成4種
* Fast Bin:
* 在這個 bin 中，heap 的分配以及釋放為最快速的
* 大約有 10 個
* 使用 single link lisk，malloc 時 allocate 最後一項(pop from top)，也就是 **LIFO**
* chunk 大小在16~最大80(可設定，預設64) byte 之間
* size : 每個 bin 差8 bytes
* 不執行合併 : 所以在 free 時不會清除下一個 chunk 的 PREV_INUSE flag
* malloc: 一開始若 binlist 為空，malloc 時 fast bin 不會提供任何服務，而後 binlist 不為空時就會從對應 size 的 binlist 取出最前面(top)的 chunk
* free: 放入相對的大小 index，chunk 被加入在 binlist 的最前端。不取消下個 inuse bit，也是因為 fastbin 裡面的 chunk 不會互相合併
* Consolidate(fastbin 唯一會合併 chunk 的時機):
* 想像一隻程式 malloc 了極多的小空間後又 free 掉,此時 fastbin 串接了非常多的小 size 的 chunk
接著程式又 malloc 了一塊很大的空間，這些小 freed chunk 無法被使用，但 top chunk 也不夠大到能夠分配這塊大空間，此時只好向 kernel 要求更多空間，但其實目前 heap 中絕大多數的 chunk 都是freed
這樣造成極度浪費 memory 空間，因此 glibc 使用 consolidate 這套機制來處理這樣的問題
* 當一個 large bin chunk 被 malloc 時,會先檢查 fastbin 中有沒有連續的 chunk，將他們組合起來丟到 unsorted bin 中
* Unsorted Bin:
* 佔據 bin 1 的位置
* circular double link list，先釋放的會先被拿到，即是 **FIFO**
* 最近 free 的 small / large chunk，摻雜不同大小的 chunk。換句話說，normal chunk 釋放後不會馬上還給系統，而是放入 unsorted bin
* 重複使用 chunks 以加速 allocation
* 若找到適合的 chunk，binlist 前面的成員(不適合條件的 chunk)也會被 unlink，並且放到相對應大小的 bin 中
* Small bin:
* circular double link list
* size 小於 512 bytes 的 chunk。佔據 bin2~bin63 的位置，總共 62 個
* size : 每個 bin 差8 bytes
* 兩個相鄰的 free chunk 會互相合併，減少 fragmentation
* Large Bin:
* circular double link list
* size 大於等於 512 bytes 的 chunk。佔據 bin64~bin126 的位置，總共 63 個
* size : 每個 bin 差距不同
* 前 32 個 bin 差 64 bytes (n=1)
* 再$2^{(6-n)}$ 個 bin 差 $8^{(n+1)}$ bytes
* n=6 : 1 個 bin 262144 bytes
* 剩最後一個 bin 存放所有更大的 chunk
* bin 裡的 chunk 依大小排序(因 size 差距不再是最小單位)，allocate 時需搜尋最適大小
#### malloc流程
* 調整 malloc size : 加上 overhead 並對齊，若 < 32 byte(64bit 最小 size，4 pointers)則補上
* 檢查 fastbin : 若對應 bin size 有符合 chunk 即 return chunk
* 檢查 smallbin : 若對應 bin size 有符合 chunk 即 return chunk
* 合併(consolidate) fastbin : (若 size 符合 large bin 或前項失敗)呼叫 malloc_consolidate 進行 fastbin 的合併(取消下一 chunk 的 PREV_INUSE)，並將合併的 bin 歸入 unsorted
* 處理 unsorted bin :
* 若 unsorted bin 中只有 last_remainder 且大小足夠，分割 last_remainder 並 return chunk。剩下的空間則成為新的 last_remainder
* loop 每個 unsorted bin chunk，若大小剛好則 return，否則將此 chunk 放至對應 size 的 bin 中。此過程直到 unsorted bin 為空或 loop 10000次為止
* 在 small / large bin 找 best fit，若成功則 return 分割的 chunk，剩下的放入 unsorted bin（成為 last remainder chunk）；若無，則繼續 loop unsorted bin，直到其為空
* 使用 top chunk : 分割 top chunk，若仍不夠則 system call
#### free流程
* 檢查 pointer 位址、alignment、flag 等等，以確認是可 free 的 memory
* 合併(consolidate)
* fastbin size : 不進行合併
* 其他 :
* 檢查前一 chunk，若未使用則合併
* 檢查後一 chunk，若是 top chunk 則整塊併入 top chunk，若否但未使用，則合併
* 將合併結果放入 unsorted bin
### 參考
https://ithelp.ithome.com.tw/articles/10263066
https://rafaelchen.wordpress.com/2017/10/16/heap-malloc-or-free/
https://rafaelchen.wordpress.com/2017/10/17/heap-come-to-my-size/
https://rafaelchen.wordpress.com/2017/10/22/malloc-workflow/
https://hackmd.io/@sysprog/c-memory#glibc-%E7%9A%84-mallocfree-%E5%AF%A6%E4%BD%9C
https://hackmd.io/@minyeon/HJOnEqaTw
Sign in with Wallet
Connect another wallet