# 記憶體管理、對齊及硬體特性
contributed by < `colinyoyo26` >

## Data alignment
- data alignment 為 data 的 address 對齊 2 的冪次方

- CPU 會一次從 memory 抓取多個連續的 bytes
- 所以沒有對齊會造成更多的 memory access 造成效能降低

- struct 會自動對齊最大 size 的 type 設計以下實驗進行驗證

struct s1 {
    int a;
    char b[5];
};

struct s2 {
    char c[5];
};

struct s3 {
    double e;
    int f;
};

int main(void) {
    return 0;
}

(gdb) p sizeof(struct s1)
$1 = 12
(gdb) p sizeof(struct s2)
$2 = 5
(gdb) p sizeof(struct s3)
$3 = 16
(gdb) p sizeof(int)
$4 = 4
(gdb) p sizeof(char)
$5 = 1
(gdb) p sizeof(double)
$6 = 8

> 從 GDB 可以看出三個 struct 各自對齊 size 最大的 type

- malloc 會對配置的記憶體做對齊，

#include <stdlib.h>

int main(void) {
    void *ptr;
    for (int i = 0; i < 1000; i++)
        ptr = (void *) malloc(i * sizeof(char));
    return 0;
}

(gdb) p ptr
$4 = (void *) 0x602010
(gdb) p ptr
$6 = (void *) 0x602030
(gdb) p ptr
$8 = (void *) 0x602050

> 可以發現記憶體位址對齊 16 bytes

(gdb) p ptr
$2 = (void *) 0x602030
(gdb) x /16gx ptr-48
0x602000:	0x0000000000000000	0x0000000000000021
0x602010:	0x0000000000000000	0x0000000000000000
0x602020:	0x0000000000000000	0x0000000000000021
0x602030:	0x0000000000000000	0x0000000000000000
0x602040:	0x0000000000000000	0x0000000000020fc1
0x602050:	0x0000000000000000	0x0000000000000000
0x602060:	0x0000000000000000	0x0000000000000000
0x602070:	0x0000000000000000	0x0000000000000000

因為要對齊 16 bytes 所以回傳時包含給 user 的 16 bytes + 16bytes 的 chunk header 其中 chunk header 中的資訊 0x21 代表 allocate 32 bytes chunk 以及 prev chunk 正在使用
:::info
0x0000000000020fc1 目前不清楚作用為何，找出原因後再補上
:::

---
## glibc 的 malloc/free 實作
### 基本認識
- glibc 使用 ptmalloc2
- ptmalloc2 支援 multithread
- 多個 threads 同時 call malloc 會立即被分配因為每個 thread 都有自己的 heap segment

- malloc 會掉用 brk() 或是 mmap() system call
- mmap 在 heap 和 stack 間找一塊連續空間 （可以單獨釋放)
- 大於 128KB 時使用 （default）
- 因為虛擬空間對應的實體空間還沒分配，所以第一次 access 會產生 page fault

- 以下用 gdb 進行驗證大於 128KB 會用 mmap
- 只有第三次 malloc 是大於 128KB

Breakpoint 1, main () at t.c:6
6	    ptr1 = (char *) malloc(sizeof(char) * 128);
(gdb) p getpid()
$1 = 7137
(gdb) n
7	    ptr2 = (char *) malloc(sizeof(char) * 128 * (1 << 10));
(gdb) p ptr1
$2 = 0x602010 ""
(gdb) n
8	    ptr3 = (char *) malloc(sizeof(char) * 128 * (1 << 10) + 1);
(gdb) p ptr2
$3 = 0x6020a0 ""
(gdb) n
9	    return 0;
(gdb) p ptr3
$4 = 0x7ffff7fb5010 ""

明顯可以看出 address 的差別
以下是執行 cat /proc/7137/maps 的結果 (擷取 heap 部份)

00602000-00623000 rw-p 00000000 00:00 0     [heap]
7ffff7fb5000-7ffff7fd9000 rw-p 00000000 00:00 0 

### Arena
- malloc 得到的連記憶體空間稱為 arena
- main thread 的 arena 稱為 main arena
- 其他 thread 的 arena 稱為 thread arena （mmap 得到）
- arena 數量
- For 32 bit systems:
- Number of arena = 2 * number of cores + 1.
- For 64 bit systems:
- Number of arena = 8 * number of cores + 1.
- 超過總限制 threads 會開始共用 arena
- 做以下實驗

#include <stdlib.h>
#include <pthread.h>

void *foo(void *arg) {
    char *ptr2;
    ptr2 = (char *) malloc(sizeof(char));
}

int main(void) {
    pthread_t thread[9];
    char *ptr1;
    ptr1 = (char *) malloc(sizeof(char));
    for (int i = 0; i < 9; i++) {
        pthread_create(&thread[i], NULL, foo, NULL);
    }
    return 0;
}

- 用 cat /proc/PID/maps 觀察 heap

# main thread malloc 之後
00602000-00623000 rw-p 00000000 00:00 0                                  [heap]

# 第一個 thread malloc
00602000-00623000 rw-p 00000000 00:00 0                                  [heap]
7ffff0000000-7ffff0021000 rw-p 00000000 00:00 0 
7ffff0021000-7ffff4000000 ---p 00000000 00:00 0 
7ffff6fef000-7ffff6ff0000 ---p 00000000 00:00 0 
7ffff6ff0000-7ffff77f0000 rw-p 00000000 00:00 0 

# 第二個
00602000-00623000 rw-p 00000000 00:00 0                                  [heap]
7ffff0000000-7ffff0021000 rw-p 00000000 00:00 0 
7ffff0021000-7ffff4000000 ---p 00000000 00:00 0 
7ffff67ee000-7ffff67ef000 ---p 00000000 00:00 0 
7ffff67ef000-7ffff6fef000 rw-p 00000000 00:00 0 
7ffff6fef000-7ffff6ff0000 ---p 00000000 00:00 0 
7ffff6ff0000-7ffff77f0000 rw-p 00000000 00:00 0 

# 第三個
00602000-00623000 rw-p 00000000 00:00 0                                  [heap]
7ffff0000000-7ffff0021000 rw-p 00000000 00:00 0 
7ffff0021000-7ffff4000000 ---p 00000000 00:00 0 
7ffff5fed000-7ffff5fee000 ---p 00000000 00:00 0 
7ffff5fee000-7ffff67ee000 rw-p 00000000 00:00 0 
7ffff67ee000-7ffff67ef000 ---p 00000000 00:00 0 
7ffff67ef000-7ffff6fef000 rw-p 00000000 00:00 0 
7ffff6fef000-7ffff6ff0000 ---p 00000000 00:00 0 
7ffff6ff0000-7ffff77f0000 rw-p 00000000 00:00 0 

.......
# 第九個
00602000-00623000 rw-p 00000000 00:00 0                                  [heap]
7fffee7fd000-7fffee7fe000 ---p 00000000 00:00 0 
7fffee7fe000-7fffeeffe000 rw-p 00000000 00:00 0 
7fffeeffe000-7fffeefff000 ---p 00000000 00:00 0 
7fffeefff000-7fffef7ff000 rw-p 00000000 00:00 0 
7fffef7ff000-7fffef800000 ---p 00000000 00:00 0 
7fffef800000-7ffff0000000 rw-p 00000000 00:00 0 
7ffff0000000-7ffff0021000 rw-p 00000000 00:00 0 
7ffff0021000-7ffff4000000 ---p 00000000 00:00 0 
7ffff47ea000-7ffff47eb000 ---p 00000000 00:00 0 
7ffff47eb000-7ffff4feb000 rw-p 00000000 00:00 0 
7ffff4feb000-7ffff4fec000 ---p 00000000 00:00 0 
7ffff4fec000-7ffff57ec000 rw-p 00000000 00:00 0 
7ffff57ec000-7ffff57ed000 ---p 00000000 00:00 0 
7ffff57ed000-7ffff5fed000 rw-p 00000000 00:00 0 
7ffff5fed000-7ffff5fee000 ---p 00000000 00:00 0 
7ffff5fee000-7ffff67ee000 rw-p 00000000 00:00 0 
7ffff67ee000-7ffff67ef000 ---p 00000000 00:00 0 
7ffff67ef000-7ffff6fef000 rw-p 00000000 00:00 0 
7ffff6fef000-7ffff6ff0000 ---p 00000000 00:00 0 
7ffff6ff0000-7ffff77f0000 rw-p 00000000 00:00 0 

- <s>可以看到其中允許 read write 的區域就是 per thread arena</s>s>
:::info
這裡不太懂從一開始救出現在最下面的 7ffff6ff0000-7ffff77f0000 rw-p 00000000 00:00 0 這段可讀可寫的空間作用為何
:::

:::warning
搭配 [Linux 核心設計: 記憶體管理](https://hackmd.io/@sysprog/rJBXOchtE) 參照，查證範圍 `7ffff6ff0000-7ffff77f0000` 在 Linux 核心的規範為何？
:notes: jserv
:::
- 先更正原本內容，後來在 func 內加入以下 code print 出變數 address 以及 malloc 回傳指標以觀察 stack 和 heap 重新用 gdb 追蹤

   printf("stack: %lx\n heap: %lx\n", (uint64_t) &arg, (uint64_t) ptr2);

- 得到以下輸出

# thread 1
[New Thread 0x7ffff77ef700 (LWP 23917)]
stack: 7ffff77eef38
heap: 7ffff00008c0
[Thread 0x7ffff77ef700 (LWP 23917) exited]

# thread 2
[New Thread 0x7ffff6fee700 (LWP 23928)]
stack: 7ffff6fedf38
heap: 7ffff0000cf0
[Thread 0x7ffff6fee700 (LWP 23928) exited]

# thread 3
[New Thread 0x7ffff67ed700 (LWP 23943)]
stack: 7ffff67ecf38
heap: 7ffff0000d10
[Thread 0x7ffff67ed700 (LWP 23943) exited]

......

- 從實驗結果推論，除了 7ffff0000000-7ffff0021000 這段區域，其他可讀可寫的區域根本就是 per thread stack
- 推論前面的 thread 已經離開所以後面的 thread 直接接管這個 arena
- 驗證以上推論，在 function 內加入 `getchar()` 防止 thread terminate

# thread 1
[New Thread 0x7ffff77ef700 (LWP 24191)]
addr: 7ffff77eef38
heap: 7ffff00008c0 

# thread 2
[New Thread 0x7ffff6fee700 (LWP 24192)]
addr: 7ffff6fedf38
heap: 7fffe80008c0

# thread 3
[New Thread 0x7ffff67ed700 (LWP 24197)]
addr: 7ffff67ecf38
heap: 7fffec0008c0

$ cat /proc/24190/maps
# after 3 threads malloc

00602000-00623000 rw-p 00000000 00:00 0                                  [heap]
7fffe8000000-7fffe8021000 rw-p 00000000 00:00 0 
7fffe8021000-7fffec000000 ---p 00000000 00:00 0 
7fffec000000-7fffec021000 rw-p 00000000 00:00 0 
7fffec021000-7ffff0000000 ---p 00000000 00:00 0 
7ffff0000000-7ffff0021000 rw-p 00000000 00:00 0 
7ffff0021000-7ffff4000000 ---p 00000000 00:00 0 
7ffff5fed000-7ffff5fee000 ---p 00000000 00:00 0 
7ffff5fee000-7ffff67ee000 rw-p 00000000 00:00 0 
7ffff67ee000-7ffff67ef000 ---p 00000000 00:00 0 
7ffff67ef000-7ffff6fef000 rw-p 00000000 00:00 0 
7ffff6fef000-7ffff6ff0000 ---p 00000000 00:00 0 
7ffff6ff0000-7ffff77f0000 rw-p 00000000 00:00 0 

- 可以發現其中有三個可讀可寫的區域是 per thread arena 其他三個是 per thread stack
### Chunk
- heap 被切成多個 Chunk
- 32位元下最小 16 bytes 且為 8-bytes alignment
- 64位元下最小 32 bytes 且為 16-bytes alignment
- 分為 allocated 和 free chunk
- 會多分配 16 bytes 的 chunk header 出來紀錄 size 以及 flag
- 因為最後 3 bits 用不到拿來當 flag 由左到右分別為
- N 若為 1 代表 non main arena
- M 若為 1 代表是用 mmapp 開出來的空間
- P 若為 1 代表 prev chunk 正在使用
### Bin
- 紀錄 free chunks 的資料結構 (freelist) 稱為 Bin
- 會先在 bin 找可用空間，找不到空間才會 call system call
- 由大小分為
- Fast bin
- Unsorted bin
- Small bin
- Large bin

---

## 參考資料
* [你所不知道的C語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/BkuMDQ9K7)
* [Linux内存分配小结--malloc、brk、mmap](https://blog.csdn.net/gfgdsg/article/details/42709943)
* [heap學習紀錄 malloc初始化和chunk簡介](http://look3little.blogspot.com/2017/05/heap-mallocchunk.html)
* [深入理解glibc malloc](http://pwn4.fun/2016/04/11/%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3glibc-malloc/)
* [linux heap堆分配](https://www.itread01.com/content/1550489961.html)
* [100個 gdb 小技巧](https://wizardforcel.gitbooks.io/100-gdb-tips/attach-process.html)