malloc
- 2021 年 11 月 13 日
- 筆記
本文（簡要地）介紹進程的記憶體鏡像，以及 malloc 的實現。
如無特別說明，本文程式碼均在 Ubuntu16 下運行，gcc 版本為 9.0，使用 -m32 參數編譯。
Process in Memory
預備知識：
- 進程的虛擬地址空間 (Virtual Address Space)
- 列印各個 segment 的地址
Virtual Address Space
一張經典的圖片：進程的虛擬地址空間 (Virtual Address Space) ，在 32 位機器下：
- 可執行程式碼 (ELF, Excutable and Linkable Format) 放在
.text段，32 位機器下，起始地址是0x8048000（64 位機器下是0x400000）。 .data段存放已初始化的static變數和已初始化的全局變數。.bss(Block Started by Symbol) 段存放未初始化的static變數和未初始化的全局變數。
為什麼需要區分
.bss段和.data段，統一把.bss的變數清零，然後合併為一個.data段不行嗎？區分可執行文件與進程 2 個概念。因為
.bss段中的變數，在可執行文件中，只記錄變數名（實質上是一個地址，並且是可重定向的地址），而不會分配真實的磁碟空間，這一點可降低可執行文件的大小。但在實際的進程當中，OS 會將.bss所有變數清零，並分配記憶體，即在進程中，.bss的變數依舊佔用記憶體（但在可執行文件中，不佔用磁碟）。
- 注意到有 2 個偏移
Random brk offset和Random stack offset，可執行文件載入到記憶體時，程式碼段和數據段的大小都是固定的，為什麼需要加入隨機的偏移呢？
參考 linux memory management - how to get "Random xxx offset"?
The randomization is just to make it harder to hack, so the hacker doesn't know exactly where to look to read things from your stack or heap.
- 對於棧和堆中間的地址，用於各種動態鏈接庫的映射，或者調用
mmap()申請共享記憶體用於 IPC。
如果一個進程的 PID = 17137，那麼可以通過
cat /proc/17137/maps查看映射的內容：> cat /proc/17137/maps 08048000-08049000 r-xp 00000000 08:01 56623614 /home/sinkinben/a.out 08049000-0804a000 r--p 00000000 08:01 56623614 /home/sinkinben/a.out 0804a000-0804b000 rw-p 00001000 08:01 56623614 /home/sinkinben/a.out 090df000-09101000 rw-p 00000000 00:00 0 [heap] f74d6000-f74f3000 r--p 00000000 08:01 49283078 /lib32/libc-2.31.so f74f3000-f764b000 r-xp 0001d000 08:01 49283078 /lib32/libc-2.31.so f764b000-f76bb000 r--p 00175000 08:01 49283078 /lib32/libc-2.31.so f76bb000-f76bd000 r--p 001e4000 08:01 49283078 /lib32/libc-2.31.so f76bd000-f76bf000 rw-p 001e6000 08:01 49283078 /lib32/libc-2.31.so f76bf000-f76c1000 rw-p 00000000 00:00 0 f76d6000-f76d8000 rw-p 00000000 00:00 0 f76d8000-f76db000 r--p 00000000 00:00 0 [vvar] f76db000-f76dd000 r-xp 00000000 00:00 0 [vdso] f76dd000-f76de000 r--p 00000000 08:01 49283074 /lib32/ld-2.31.so f76de000-f76fc000 r-xp 00001000 08:01 49283074 /lib32/ld-2.31.so f76fc000-f7707000 r--p 0001f000 08:01 49283074 /lib32/ld-2.31.so f7708000-f7709000 r--p 0002a000 08:01 49283074 /lib32/ld-2.31.so f7709000-f770a000 rw-p 0002b000 08:01 49283074 /lib32/ld-2.31.so ffd5e000-ffd7f000 rw-p 00000000 00:00 0 [stack]其實我們的
prinf函數就是通過鏈接libc.so來調用的。
Segment
先看一段程式碼：
#include <stdio.h>
extern end;
extern edata;
extern etext;
int I;
static int inited = -1;
int main(int argc, char **argv)
{
int i;
int *ii;
printf("&etext = 0x%lx\n", &etext);
printf("&edata = 0x%lx\n", &edata);
printf("&end = 0x%lx\n", &end);
printf("\n");
ii = (int *) malloc(sizeof(int));
printf("main = 0x%lx\n", main);
printf("&I = 0x%lx\n", &I);
printf("&i = 0x%lx\n", &i);
printf("&argc = 0x%lx\n", &argc);
printf("&ii = 0x%lx\n", &ii);
printf("ii = 0x%lx\n", ii);
printf("&inited= 0x%lx\n", &inited);
}
在上述程式碼中：etext, edata, end 是鏈接器 ld 保留的字元，它們分別會指向 .text, .data, .bss 這三個 Segment 的結束位置。
因為我們的教材都是講 32 位機器的，所以我們把它編譯位 32 位的機器碼：
gcc -m32 testaddr.c
運行結果：
&etext = 0x8048714
&edata = 0x804a02c
&end = 0x804a034
main = 0x8048542
&I = 0x804a030
&i = 0xffec5cc4
&argc = 0xffec5cf0
&ii = 0xffec5cc8
ii = 0xa0165b0
&inited= 0x804a028
可以看出：
argc, i, ii這 3 個變數都是在棧上的，地址偏大。ii指向的位置在堆上。main在.text，因此其地址小於etext。I在.bss，因此其地址大於edata，小於end，在這個例子中，I的結束位置也是end。inited在.data，因此其地址大於etext，小於edata，在這個例子中，inited的結束位置也是edata。
編譯為 64 位的可執行文件，結果如下：
&etext = 0x400865
&edata = 0x60104c
&end = 0x601058
main = 0x4006b2
&I = 0x601050
&i = 0x7ffcfeb0cf3c
&argc = 0x7ffcfeb0cf2c
&ii = 0x7ffcfeb0cf40
ii = 0x175d6b0
&inited= 0x601048
眾所周知，數據段（bss 和 data）的可讀可寫，但程式碼段 text 是只讀。
#include <stdio.h>
extern end;
extern etext;
int main()
{
char *s;
char c;
printf("&etext = 0x%lx\n", &etext);
printf("&end = 0x%lx\n", &end);
printf("\n");
printf("Enter memory location in hex (start with 0x): ");
fflush(stdout);
scanf("0x%x", &s);
printf("Reading 0x%x: ", s);
fflush(stdout);
c = *s;
printf("%d\n", c);
printf("Writing %d back to 0x%x: ", c, s);
fflush(stdout);
*s = c;
printf("ok\n");
}
比如：
&etext = 0x80487a4
&end = 0x804a038
Enter memory location in hex (start with 0x): 0x80487a0
Reading 0x80487a0: -60
Writing -60 back to 0x80487a0: Segmentation fault (core dumped)
輸入一個 text 段的地址，當寫回時發生 Segmentation fault 。如果操作的地址是 0x80487a8，它是否能覆蓋某個數據段段變數值呢？
&etext = 0x80487a4
&end = 0x804a038
Enter memory location in hex (start with 0x): 0x80487a8
Reading 0x80487a8: 1
Writing 1 back to 0x80487a8: Segmentation fault (core dumped)
很奇怪？這是因為 OS 對進程的記憶體鏡像是按頁管理的，因此雖然程式碼段在 etext 結束，但 etext 後面的一部分記憶體雖然沒用到（此處是 4K 頁，即 [etext, 0x8049000) 這一區間），這也屬於程式碼段，上面的地址 0x80487a8 就是屬於頁對齊範圍內的地址。
使用
getconf PAGESIZE可以查看 OS 的記憶體頁大小。
類似地，如果我們對 end 往後的地址寫，理論上也是可以的，因為 [end, 0x804b000) 在頁對齊之後，都屬於數據段。
$ ./a.out
&etext = 0x80487a4
&end = 0x804a038
Enter memory location in hex (start with 0x): 0x804a01c
Reading 0x804a01c: -16
Writing -16 back to 0x804a01c: ok
$ ./a.out
&etext = 0x80487a4
&end = 0x804a038
# 需要注意的是，此處的程式碼是僅讀取一個位元組，如果 char *s 改為 int *s, 那麼此處也會讀失敗。
Enter memory location in hex (start with 0x): 0x804afff
Reading 0x804afff: 0
Writing 0 back to 0x804afff: ok
$ ./a.out
&etext = 0x80487a4
&end = 0x804a038
Enter memory location in hex (start with 0x): 0x804b000
Reading 0x804b000: Segmentation fault (core dumped)
Heap
一個進程中，Heap 的結束位置由 Program Break 記錄，在 Unix 環境下，我們可以通過 sbrk(0) 去獲取該地址。
sbrk(val)的作用是將 Program Break 往上增加val，並返回增加後的結果。brk(addr)的作用是將 Program Break 的值調整為addr, 成功返回 0 ，失敗返回 -1 。
例如：
#include <stdio.h>
extern end;
extern etext;
int main()
{
char *s;
char c;
printf("&etext = 0x%lx\n", &etext);
printf("&end = 0x%lx\n", &end);
printf("sbrk(0)= 0x%lx\n", sbrk(0));
printf("&c = 0x%lx\n", &c);
printf("\n");
printf("Enter memory location in hex (start with 0x): ");
fflush(stdout);
scanf("0x%x", &s);
printf("Reading 0x%x: ", s);
fflush(stdout);
c = *s;
printf("%d\n", c);
printf("Writing %d back to 0x%x: ", c, s);
fflush(stdout);
*s = c;
printf("ok\n");
}
運行結果：
&etext = 0x8048814
&end = 0x804a03c
sbrk(0)= 0x990b000
&c = 0xffe299a7
為什麼 sbrk(0) 和 end 差這麼多呢？這是由於加入了上述的 Random Brk Offset 的結果。
Stack
使用 ulimit -a 可以看到 OS 給每個進程默認分配的棧大小：
> ulimit -a
...
stack size (kbytes, -s) 8192
...
此處是 8MB ，如果我們在棧上的局部變數過大，那麼會引發 Segmentation fault ，例如下面程式碼：
#include <stdio.h>
int main()
{
char data[8192 * 1024] = {'\0'};
}
運行命令：
> cat /proc/{pid}/maps
...
ffd42000-ffd63000 rw-p 00000000 00:00 0 [stack]
可以發現 [0xffd42000, 0xffd63000) 這一區間是上述程式的初始棧，大小為 0x21000 = 33 * 4096 。為什麼不是 8MB 呢？個人理解是因為初始狀態並不需要預分配 8MB / 4096 = 2048 這麼多個頁。 [0xffd42000, 0xffd63000) 這個虛擬地址區間應該對應 33 個在記憶體中的物理頁。
Malloc
glibc 的 malloc 的源程式碼：
- //code.woboq.org/userspace/glibc/malloc/malloc.c.html#1059
- //code.woboq.org/userspace/glibc/malloc/memusage.c.html#malloc
malloc 的實現策略與 OS 和採用的 C 標準庫有關，但一般而言，可以歸結為：
- 預分配若干個 PAGE ，初始化空閑鏈表和已使用鏈表。
- 分配的單位是一個 chuck，一個 chuck 包括
<bookeeping, user's memory>2 部分 ，所有的 chunk 組織為鏈表。 - 每次調用
malloc，取出一塊符合要求的 chunk 記憶體塊（「取」的演算法視乎 OS 和 C 標準庫的具體實現），返回起始地址，並加入已使用鏈表。 - 調用
free時，將這一塊記憶體加入空閑鏈表（可能需要與其他空閑記憶體塊進行合併）。
Overview
上一節提到，我們可以通過 sbrk(0) 獲取堆的結束位置。
#include <stdio.h>
#include <sys/types.h>
int main()
{
int *i1, *i2;
printf("sbrk(0) before malloc(4): 0x%x\n", sbrk(0));
i1 = (int *) malloc(4);
printf("sbrk(0) after `i1 = (int *) malloc(4)': 0x%x\n", sbrk(0));
i2 = (int *) malloc(4);
printf("sbrk(0) after `i2 = (int *) malloc(4)': 0x%x\n", sbrk(0));
printf("i1 = 0x%x, i2 = 0x%x\n", i1, i2);
}
運行輸出：
sbrk(0) before malloc(4): 0x843e000
sbrk(0) after `i1 = (int *) malloc(4)': 0x8460000
sbrk(0) after `i2 = (int *) malloc(4)': 0x8460000
i1 = 0x843e5b0, i2 = 0x843e5c0
可以發現，當第二次調用 malloc 時，並沒有改變 sbrk(0) 的值，而是從預分配的 Buffer 中返回 4 位元組的記憶體。預分配記憶體的大小為 0x8460000 - 0x843e000 = 0x22000 ，一共 34 個 PAGE 。
注意到 i1, i2 之間一共差了 16 個位元組，這是由於 Bookeeping 頭部資訊的結果（後續的內容會提到）。
如果使用 malloc 分配一塊很大的記憶體，根據 OS 和 C 標準庫的記憶體管理策略的不同，可能並不是通過 malloc 去分配，而是通過 memory mapping，例如在 Ubuntu 下：
int main()
{
printf("sbrk(0) = %p\n", sbrk(0));
char *small = (char*)malloc(4);
printf("small = %p\n", small);
printf("sbrk(0) = %p\n", sbrk(0));
char *large = (char *)malloc(0x22000);
printf("large = %p\n", large);
printf("sbrk(0) = %p\n", sbrk(0));
while (1) ;
}
運行輸出：
sbrk(0) = 0x8aa3000
small = 0x8aa35b0
sbrk(0) = 0x8ac5000 # 調用 malloc(4) 後, sbrk(0) += 0x22000
large = 0xf74bf010
sbrk(0) = 0x8ac5000 # 調用 malloc(0x22000) 後, sbrk(0) 不變
第二次申請，按道理 malloc 應該會再次申請一個 Buffer，為什麼會不變呢？
# PID(a.out) = 19619
> cat /proc/19619/maps
...
08aa3000-08ac5000 rw-p 00000000 00:00 0 [heap]
f74bf000-f74e2000 rw-p 00000000 00:00 0
...
可以看到，虛擬地址 f74bf000-f74e2000 屬於 memory mapping 的地址範圍，而 large = 0xf74bf010 正好處於這一區間的開始位置，前 16 個位元組是該記憶體塊的 Bookeeping 。
Bookeeping
參考：GLIBC malloc implementation bookkeeping
樣例程式碼：
#include <stdio.h>
#include <sys/types.h>
main()
{
int *buf;
int i, sz;
i = 1000;
printf("sbrk(0) = 0x%x\n", sbrk(0));
for (sz = 4; sz < 32; sz += 4) {
buf = (int *) malloc(sz);
buf[0] = i;
i++;
printf("Allocated %d bytes. buf = 0x%x, buf[-1] = %d, buf[-2] = %d, buf[0] = %d\n",
sz, buf, buf[-1], buf[-2], buf[0]);
}
sz = 100;
buf = (int *) malloc(sz);
buf[0] = i;
i++;
printf("Allocated %d bytes. buf = 0x%x, buf[-1] = %d, buf[-2] = %d, buf[0] = %d\n",
sz, buf, buf[-1], buf[-2], buf[0]);
printf("sbrk(0) = 0x%x\n", sbrk(0));
}
運行輸出：
sbrk(0) = 0x8f69000
Allocated 4 bytes. buf = 0x8f695b0, buf[-1] = 17, buf[-2] = 0, buf[0] = 1000
Allocated 8 bytes. buf = 0x8f695c0, buf[-1] = 17, buf[-2] = 0, buf[0] = 1001
Allocated 12 bytes. buf = 0x8f695d0, buf[-1] = 17, buf[-2] = 0, buf[0] = 1002
Allocated 16 bytes. buf = 0x8f695e0, buf[-1] = 33, buf[-2] = 0, buf[0] = 1003
Allocated 20 bytes. buf = 0x8f69600, buf[-1] = 33, buf[-2] = 0, buf[0] = 1004
Allocated 24 bytes. buf = 0x8f69620, buf[-1] = 33, buf[-2] = 0, buf[0] = 1005
Allocated 28 bytes. buf = 0x8f69640, buf[-1] = 33, buf[-2] = 0, buf[0] = 1006
Allocated 100 bytes. buf = 0x8f69660, buf[-1] = 113, buf[-2] = 0, buf[0] = 1007
sbrk(0) = 0x8f8b000
為什麼是 17, 33, 113 這樣「奇怪」的數字呢，直覺上，如果考慮位元組對齊，Bookeeping 這樣的因素，buf[-1] 理應是一個偶數。為什麼會這樣呢？
先看 malloc 中，一個 chunk 的數據結構：
struct malloc_chunk {
INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T mchunk_size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};
在這一數據結構當中，除了 mchunk_prev_size, mchunk_size 這 2 個成員，其他 4 個當且僅當這個 chuck 是空閑的時候才有意義。
同時，以上述的 malloc_chunk 作為鏈表節點， malloc 需要維護已使用鏈表和空閑鏈表。
此外，上面的程式碼 chuck 最小為 16 位元組的原因：
Chunks always begin on even word boundaries, so the
memportion (which is returned to the user) is also on an even word boundary, and thus at least double-word (8 bytes) aligned.
Allocated List
對於已使用鏈表：
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk, if unallocated (P clear) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk, in bytes |A|M|P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| User data starts here... .
. .
. (malloc_usable_size() bytes) .
. |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (size of chunk, but used for application data) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of next chunk, in bytes |A|0|1|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
如果一個 chunk 已被分配出去，那麼這時候，mchunk_prev_size 這個成員也不需要了，因此這 4 位元組可提供給前一個 chuck 的 User Memory 使用。
AMP 是 3 個標記位，分別表示：
A: non main arena chunk.M: chunk ismmaped.P: previous chunk is in use (i.e. not free).
為什麼在上述的程式碼中，buf[-1] 總是一個奇數呢？這是因為標記位 P = 1 。
在 Bookeeping 一節的程式碼中，堆記憶體的狀態如下：
+-----------+ 0x8f695a8
| prev size |
|-----------|
| size |
a --> |-----------| 0x8f695b0
| user data |
| |
+-----------+ 0x8f695b8
| prev size |
|-----------|
| size |
b --> |-----------| 0x8f695c0
| user data |
| |
+-----------+ 0x8f695c8
| prev size |
|-----------|
| size |
c --> |-----------| 0x8f695d0
| user data |
| |
+-----------+ 0x8f695d8
| prev size | <-------- used for user data
|-----------| 0x8f695dc
| size |
d --> |-----------| 0x8f695e0
| user data |
| ... |
Free List
對於空閑鏈表：
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk, if unallocated (P clear) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`head:' | Size of chunk, in bytes |A|0|P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Forward pointer to next chunk in list |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Back pointer to previous chunk in list |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unused space (may be 0 bytes long) .
. .
. |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`foot:' | Size of chunk, in bytes |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of next chunk, in bytes |A|0|0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
每當調用 free 回收記憶體時，被回收的 chunk 插入空閑鏈表時，需要填入 forward, back 兩個地址，記錄前後的空閑 chunk ，如果空閑鏈表中有多個地址是連續的 chunk，需要合併為一個。
Fragmentation
參考：Internal and external fragmentation
本節的內容是記憶體碎片 (Fragmentation) ，分為內部碎片 (internal) 和外部碎片 (external) 。
對於上文提及的內容，又涉及 2 個層面的記憶體管理：
- 庫函數
malloc對預申請 Heap Buffer 的記憶體管理（堆記憶體管理），這是在用戶空間層面的記憶體管理，在申請與回收堆記憶體時，會產生 chunk 碎片。 - OS 對真實物理記憶體的管理，物理記憶體的分配單位是 PAGE，在申請與回收物理頁的過程中，同樣會產生頁碎片。
不論採用什麼樣的記憶體管理策略，碎片的產生都是不可避免的，而 external 和 internal 其實是相對於進程而言的。
假設載入某個進程到記憶體需要 N 位元組，那麼需要分配 k = N / PAGE_SIZE + (k % PAGE_SIZE) != 0 個物理頁，這時候就會產生 PAGE_SIZE - N % PAGE_SIZE 的碎片，這種叫外部碎片。
而在某個進程的記憶體中，malloc 預分配一塊記憶體，但又沒有被用戶申請使用，這些記憶體是內部碎片。
| Internal | External |
|---|---|
 |
 |
Summary
一些無關重要的總結。
通常「面試八股文」所說的 「記憶體管理」 ，正常人的理解應該是指 Linux 內核層面的記憶體管理（即 buddy 和 slab 這 2 個演算法），一般來說是指：
- Buddy 是對真實的物理記憶體（即 DRAM）進行管理，管理的單位是 PAGE 。
- 在 Linux 內核中，如果只能按頁分配，那麼碎片會非常大，假設一個結構體只有 20 bytes , 這時當然希望能夠按位元組分配，所以才會有 slab allocator 。
對於 buddy 和 slab ，可以參考：
References
- [1] //web.eecs.utk.edu/~huangj/cs360/lecture_notes.html
- [2] //manybutfinite.com/post/anatomy-of-a-program-in-memory/
- [3] glibc - malloc
