---
# System prepended metadata

title: 記憶體管理、對齊及硬體特性

---

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

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

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

- struct 會自動對齊最大 size 的 type 設計以下實驗進行驗證 
```cpp
struct s1 {
    int a;
    char b[5];
};

struct s2 {
    char c[5];
};

struct s3 {
    double e;
    int f;
};

int main(void) {
    return 0;
}
```

```shell
(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 會對配置的記憶體做對齊，
```cpp
#include <stdlib.h>

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

```shell
(gdb) p ptr
$4 = (void *) 0x602010
(gdb) p ptr
$6 = (void *) 0x602030
(gdb) p ptr
$8 = (void *) 0x602050
```
> 可以發現記憶體位址對齊 16 bytes

```shell
(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

```shell
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 部份)
```shell
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
-   做以下實驗
```cpp
#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)