---
# System prepended metadata

title: 記憶體管理、對齊及硬體特性
tags: [C 語言筆記]

---

---
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 的，所以有可能會有以下狀況導致本來只需要讀一次變成要讀兩次
![](https://i.imgur.com/VmVExZM.png)
* 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
![](https://i.imgur.com/6FIJDmd.png)

Multiple heap Thread arena : 
* Segment 2 的 heap_info 有 ptr 指向 前一個 heap (Segment 2)
* Top 指向最新的的 heap 的 top chunk
![](https://i.imgur.com/UvEaudH.png)


#### 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
![](https://i.imgur.com/7TZ6d2X.png)

* 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 中的
![](https://i.imgur.com/4HeNOsz.png)

* 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 時需搜尋最適大小

![](https://i.imgur.com/P2XlPDB.png)

#### 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

![](https://i.imgur.com/2Tcj8Lr.png)

#### 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
