malloc/free簡化實現；malloc 和 sbrk 關系；虛擬內存機制。?

一個內存管理 C 語言部分講，UNIX部分講，Linux部分還講，死磕到底！！

一、mallc/free簡化實現

上篇文章已經講解了動態內存分配/釋放函數，參看：UNIX再學習 – 內存管理?
下面來講一下，它的自定義函數實現，其中有三個部分：

1、內存控制塊

內存控制塊用于管理每次分配的內存塊，記錄該內存塊的字節大小、忙閑狀態，以及相關內存控制塊的首地址。

代碼如下所示

typedef struct mem_control_block {size_t size; //本塊大小bool free; //空閑狀態struct mem_control_block *next; //后塊指針 }MCB; MCB *g_top = NULL; //棧頂指針

講解

上述代碼中：?
定義了一個結構體 mem_control_block，別名為 MCB。?
定義結構體成員 size，用于保存申請分配的內存塊的字節數。?
定義結構體成員 free，用于保存該內存是否被分配給進程。?
定義結構體成員 next，用于保存下一個鏈表節點的地址。?
定義鏈表棧的棧頂指針 g_top。

2、分配內存

遍歷內存控制塊鏈表，若有大小足夠的空閑塊，則重用該塊，否則分配新的足量內存并將其控制塊壓入鏈表棧。

代碼如下所示：

void* my_malloc (size_t size) {MCB* mcb;for (mcb = g_top; mcb; mcb = mcb->next)if (mcb->free && mcb->size >= size)break;if (! mcb) {mcb = sbrk (sizeof (MCB) + size);if (mcb == (void*)-1) return NULL;mcb->size = size;mcb->next = g_top;g_top = mcb; }mcb->free = false;return mcb + 1; }

講解

上述代碼中，以下代碼： void* my_malloc (size_t size) 函數的形參size代表要申請的存儲空間的字節數。
上述代碼中，以下代碼： MCB* mcb;for (mcb = g_top; mcb; mcb = mcb->next)if (mcb->free && mcb->size >= size)break; 遍歷內存控制塊鏈表，尋找大小足夠的空閑塊進行分配。其中，g_top是內存控制塊鏈表第一個結點的指針，而以下代碼： if (mcb->free && mcb->size >= size)break; 當mcb->free為真時，代表該內存控制塊沒有被進程使用。當mcb->size >= size為真時，代表該內存控制塊內的空間字節數大于等于所申請的空間字節數。當兩個條件同時為真時，表示該內存控制塊內的空間可以被分配給進程使用。
上述代碼中，以下代碼： if (! mcb) {mcb = sbrk (sizeof (MCB) + size);if (mcb == (void*)-1) return NULL;mcb->size = size;mcb->next = g_top;g_top = mcb; } 當內存控制塊鏈表中找不到大小足夠的空閑塊進行分配時，分配新的足量內存并將其控制塊壓入鏈表棧。其中，以下代碼： mcb = sbrk (sizeof (MCB) + size);if (mcb == (void*)-1) return NULL; 使用sbrk函數分配新的足量內存。
上述代碼中，以下代碼： mcb->free = false; 將mcb指向的內存控制塊聲明為已被分配。
上述代碼中，以下代碼： return mcb + 1; mcb + 1等效于mcb + 1 * sizeof(MCB)，即跳過內存控制塊所占的空間，返回可以使用的空間地址。

3、釋放內存

先將被釋放內存塊標記為空閑，然后遍歷內存控制塊鏈表，將靠近棧頂的連續空閑塊及其內存控制塊一并釋放。

代碼如下所示

void my_free (void* ptr) {if (ptr) {MCB* mcb = (MCB*)ptr - 1;mcb->free = true;for (mcb = g_top; mcb->next; mcb = mcb->next)if (! mcb->free) break;if (mcb->free) {g_top = mcb->next;brk (mcb); }else if (mcb != g_top) {g_top = mcb;brk ((void*)mcb + sizeof (MCB) + mcb->size); }} } 上述代碼中，以下代碼： void my_free (void* ptr) 函數形參為要釋放的存儲空間地址。

上述代碼中，以下代碼：

if (ptr)

如果該地址為空，則什么都不做，直接退出。
上述代碼中，以下代碼： MCB* mcb = (MCB*)ptr - 1; (MCB*)ptr - 1等效于(MCB*)ptr – 1 * sizeof(MCB)，即指向內存控制塊的第一個字節的地址。
上述代碼中，以下代碼： mcb->free = true; 將該內存控制塊標記為空閑，即進程不再使用它了。
上述代碼中，以下代碼： for (mcb = g_top; mcb->next; mcb = mcb->next)if (! mcb->free) break; 遍歷內存控制塊鏈表。其中，g_top是內存控制塊鏈表第一個結點的指針，而以下代碼： if (! mcb->free) break; 在內存控制塊鏈表中找到進程正在使用的第一個內存控制塊結點。
上述代碼中，以下代碼： if (mcb->free) {g_top = mcb->next;brk (mcb); } 當內存控制塊鏈表中只有一個結點時，刪除該節點。
上述代碼中，以下代碼： else if (mcb != g_top) {g_top = mcb;brk ((void*)mcb + sizeof (MCB) + mcb->size); } 將靠近棧頂的連續空閑塊及其內存控制塊一并釋放。

4、完整代碼

#include <stdio.h> #include <stdbool.h> #include <unistd.h>//內存控制塊 typedef struct mem_control_block {size_t size; // 本塊大小bool free; // 空閑標志struct mem_control_block* next; // 后塊指針 } MCB;//單向鏈表棧 MCB* g_top = NULL;//棧頂指針//malloc 函數的實現 void* my_malloc (size_t size) {MCB* mcb;for (mcb = g_top; mcb; mcb = mcb->next)if (mcb->free && mcb->size >= size)break;if (! mcb) {mcb = sbrk (sizeof (MCB) + size);if (mcb == (void*)-1) return NULL;mcb->size = size;mcb->next = g_top;g_top = mcb; }mcb->free = false;return mcb + 1; } //free 函數的實現 void my_free (void* ptr) {if (ptr) {MCB* mcb = (MCB*)ptr - 1;mcb->free = true;for (mcb = g_top; mcb->next; mcb = mcb->next)if (! mcb->free) break;if (mcb->free) {g_top = mcb->next;brk (mcb); }else if (mcb != g_top) {g_top = mcb;brk ((void*)mcb + sizeof (MCB) + mcb->size); }} }int main() {int *p = my_malloc(sizeof(int));*p = 10;printf("%d\n", *p);my_free(p);return 0; } 輸出結果： 10

擴展部分?

參看：Linux實驗心得——內存管理?
參看：malloc的實現原理學習（2）?

二、malloc 和 sbrk 關系

1、首先我想講一個函數 malloc_usable_size

參看：MALLOC_USABLE_SIZE 講解

#include <malloc.h> size_t malloc_usable_size (void *ptr); 1

這個函數返回調用 malloc 后實際分配的可用內存的大小，如果ptr 為NULL，則為 0

舉個例子

#include <stdio.h> #include <stdlib.h>int alloc_memory (char *p, int size) {p = (char*)malloc (size);if (NULL == p)perror ("malloc"), exit (1);printf ("%d\n", malloc_usable_size (p)); }int main (void) {char *p = NULL;alloc_memory (p, 0);alloc_memory (p, 10);alloc_memory (p, 20);return 0; } 通過這個示例說明，使用malloc申請內存空間，正常情況下系統會返回至少 12B 的空間。

2、分析 malloc 和 sbrk

通過上面 malloc 函數的簡化實現，可以看到，當內存控制塊鏈表中找不到大小足夠的空閑塊進行分配時，分配新的足量內存并將其控制塊壓入鏈表棧。其中，以下代碼： mcb = sbrk (sizeof (MCB) + size);if (mcb == (void*)-1) return NULL; 使用sbrk函數分配新的足量內存。
sbrk 實現虛擬內存到內存的映射，是系統調用，是Unix/Linux系統提供的接口（只能在Unix/Linux系統下才能用的）。而malloc是標準c函數在，所以在Unix/Linux和windows下都能用。?
在Unix/Linux下，malloc 底層實現就是通過系統調用sbrk實現的；在windows下malloc則是通過調用windows系統提供的接口實現。

描述：

這部分，在 UNIX環境高級編程第 7 章，也有講到。?
雖然 sbrk 可以擴充或縮小進程的存儲空間，但是大多數 malloc 和 free 的實現都不減小進程的存儲空間。釋放的空間可共以后再分配，但將它們保持在 malloc 池中而不返回給內核。?
大多數實現所分配的存儲空間比所要求的要稍大一些，額外的空間用來記錄管理信息 – 分配塊的長度、指向下一個分配塊的指針等。這就意味著，如果超過一個已分配區的尾端或者在已分配區起始位置之前進行寫操作，則會改寫另一塊管理記錄信息。這種類型的錯誤是災難性的，但是因為這種錯誤不會很快就暴露出來，所以也就很難發現。

舉個例子說明：

#include <stdio.h> #include <stdlib.h> #include <unistd.h> int main (void) { void *cur = sbrk (0); printf ("cur 1 = %p\n", cur); void *ptr = malloc (100); void *ptr1 = malloc (100);cur = sbrk (0); printf ("cur 2 = %p\n", cur); printf ("ptr = %p\n", ptr); printf ("ptr1 = %p\n", ptr1); free (ptr); free (ptr1); cur = sbrk (0); printf ("cur 3 = %p\n", cur); printf ("ptr = %p\n", ptr); printf ("ptr1 = %p\n", ptr1); return 0; } 輸出結果： cur 1 = 0x8f17000 cur 2 = 0x8f38000 ptr = 0x8f17008 ptr1 = 0x8f17070 cur 3 = 0x8f38000 ptr = 0x8f17008 ptr1 = 0x8f17070

示例總結

參看：自己動手寫malloc?

參看：UNIX再學習 – 內存管理?

可以看出，malloc 所申請的空間的起始地址，第一次，比一開始的堆末尾地址向后移動了 8 個字節。第二次，后移了112個字節。這 8 個字節應該就是，用來記錄管理信息的額外空間 – 分配塊的長度、指向下一個分配塊的指針等。而我們采用的是 8 字節對齊，申請 100 個字節，經過對齊，應為 104 個字節，再加上 8 個額外空間，即 112 個字節。
而堆尾地址變為 0x8f38000，增加了 0x21000，十六進制 0x21000 轉換成 十進制為 135168 = 33 * 4096 上面講到當前系統內存頁的大小為 4Kb。malloc 申請內存，系統會一次映射 33 個內存頁。

三、虛擬內存機制

參看：linux內存管理?

1、為什么需要使用虛擬內存

??? 大家都知道，進程需要使用的代碼和數據都放在內存中，比放在外存中要快很多。問題是內存空間太小了，不能滿足進程的需求，而且現在都是多進程，情況更加糟糕。所以提出了虛擬內存，使得每個進程用于3G的獨立用戶內存空間和共享的1G內核內存空間。（每個進程都有自己的頁表，才使得3G用戶空間的獨立）這樣進程運行的速度必然很快了。而且虛擬內存機制還解決了內存碎片和內存不連續的問題。為什么可以在有限的物理內存上達到這樣的效果呢？

2、虛擬內存的實現機制

??? 首先呢，提一個概念，交換空間（swap space），這個大家應該不陌生，在重裝系統的時候，會讓你選擇磁盤分區，就比如說一個硬盤分幾個部分去管理。其中就會分一部分磁盤空間用作交換，叫做swap space。其實就是一段臨時存儲空間，內存不夠用的時候就用它了，雖然它也在磁盤中，但省去了很多的查找時間啊。當發生進程切換的時候，內存與交換空間就要發生數據交換一滿足需求。所以啊，進程的切換消耗是很大的，這也說明了為什么自旋鎖比信號量效率高的原因。

??? 那么我們的程序里申請的內存的時候，linux內核其實只分配一個虛擬內存（?線性地址），并沒有分配實際的物理內存。只有當程序真正使用這塊內存時，才會分配物理內存。這就叫做延遲分配和請頁機制。釋放內存時，先釋放線性區對應的物理內存，然后釋放線性區；"請頁機制"將物理內存的分配延后了，這樣是充分利用了程序的局部性原來，節約內存空間，提高系統吞吐；就是說一個函數可能只在物理內存中呆了一會，用完了就被清除出去了，雖然在虛擬地址空間還在。（不過虛擬地址空間不是事實上的存儲，所以只能說這個函數占據了一段虛擬地址空間，當你訪問這段地址時，就會產生缺頁處理，從交換區把對應的代碼搬到物理內存上來）

3、物理內存與虛擬內存的布局

左邊是物理地址分配，與實際的CPU相關。4KB的這些都是一些控制器所占有，比如lcdc sd卡，他們的寄存器地址就是這樣定死的。但是呢，我們要訪問這些寄存器的時候，還是不能直接用，要使用內存管理的規則，使用虛擬地址去訪問它，所以在驅動等內核程序中需要使用虛擬地址訪問寄存器。如果有人直接使用物理地址訪問寄存器，那么唯一的解釋就是沒有開mmu。不過這樣你的進程就沒有4G內存可以用了。

物理地址分布：

這是偷的別人的圖啦，物理地址有896M直接映射到虛擬地址的內存空間，這是一一對應的映射，只有起始地址不一樣，偏移是一樣的。這個大小大多是固定的，哪怕你的內存超過一個G，太小了就另外說了。注意：用戶區的代碼也是放在這段物理地址里面的，就是說物理地址可以進行二次映射。但不管怎么樣，這段物理地址都是受內核管理。當你內存很大的時候，超過896M時，剩余的那些內存怎么辦呢？這多出來的叫做高端內存，如果你使用vmalloc申請空間，就會在高端內存中分配，如果你使用kmalloc申請空間，就會在小于896的內存中分配。所以還是很講究的啊！！如果你的程序需要使用高端內存，就要調用內核API來分配，所以高端內存并不是想用就能用的哦。不過通過系統把一些應用常住在高端內存到是個好注意。不過前提是你的內存灰常大啊。

為什么要這樣做呢？先看看這里面放些什么？

虛擬地址分布：

關于0-3G用戶空間內存的分布：

談到段式分布，就要說說邏輯地址，線性地址與物理地址的關系：

linux通過段機制把邏輯地址轉換為虛擬地址（就是線性地址），再通過頁機制把虛擬地址轉換為物理地址。所謂分段就是基址不同，偏移一樣，比如說32位，一般程序里面都不會使用這么多的位，可以把前12位用作基址，后20位用作偏移，這樣在特定段就可以只使用偏移尋址了。尋址很方便，不過linux頁基址做的更好。

最后呢再說幾個點：

1 線性地址空間：指linux系統中的虛擬地址空間。

2 cpu尋址是屬于物理地址。所以在使用cpu尋址前要把地址轉換好。

3 物理內存中的高端內存是DDR減去896M后多出來的那一段。虛擬地址里面的高端內存是指用于映射高端內存的虛擬地址空間。不過高端內存被映射到用戶空間，那就是另外一回事了吧。

4 內核空間是可以訪問用戶空間的，級別高就是好啊。不過不是通過虛擬地址直接訪問的。

四、總結

我有種預感，我在 CSND 寫博客有點寫不下去了，編輯器太爛了。初嘗 Markdown 編輯器，字體超小，看著都傷眼睛。HTML 編譯器，插入代碼，各種字體沖突。美化文章布局上，就用去了很多時間。

CSND 博客故障處理，占用工作時間，也就算了。這個一直在用的編輯器這的讓人頭痛。

總結

以上是生活随笔為你收集整理的UNIX再学习 -- 死磕内存管理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。