本文轉載連結:
http://blog.codinglabs.org/articles/a-malloc-tutorial.html
目錄
一. 預備知識
1. 虛拟記憶體位址和實體記憶體位址
2. 頁與位址構成
3. 記憶體頁與磁盤頁
二. Linux程序級記憶體管理
1. 記憶體排布
2. Heap 記憶體模型
3. 堆記憶體管理實作原理
一. 預備知識
1. 虛拟記憶體位址和實體記憶體位址
為了簡單，現代作業系統在處理記憶體位址時，普遍采用虛拟記憶體位址技術。即在彙程式設計式（或機器語言）層面，當涉及記憶體位址時，都是使用虛拟記憶體位址。采用這種技術時，每個程序仿佛自己獨享一片2N位元組的記憶體，其中N是機器位數。例如在64位CPU和64位作業系統下，每個程序的虛拟位址空間為264Byte。
這種虛拟位址空間的作用主要是簡化程式的編寫及友善作業系統對程序間記憶體的隔離管理，真實中的程序不太可能（也用不到）如此大的記憶體空間，實際能用到的記憶體取決于實體記憶體大小。
由于在機器語言層面都是采用虛拟位址，當實際的機器碼程式涉及到記憶體操作時，需要根據目前程序運作的實際上下文将虛拟位址轉換為實體記憶體位址，才能實作對真實記憶體資料的操作。這個轉換一般由一個叫MMU（Memory Management Unit）的硬體完成。
2. 頁與位址構成
在現代作業系統中，不論是虛拟記憶體還是實體記憶體，都不是以位元組為機關進行管理的，而是以頁（Page）為機關。一個記憶體頁是一段固定大小的連續記憶體位址的總稱，具體到Linux中，典型的記憶體頁大小為4096Byte（4K），是以記憶體位址可以分為頁号和頁内偏移量。
上面是虛拟記憶體位址，下面是實體記憶體位址。由于頁大小都是4K，是以頁内便宜都是用低12位表示，而剩下的高位址表示頁号。
MMU映射機關并不是位元組，而是頁，這個映射通過查一個常駐記憶體的資料結構頁表來實作。現在計算機具體的記憶體位址映射比較複雜，為了加快速度會引入一系列緩存和優化，例如TLB等機制。下面給出一個經過簡化的記憶體位址翻譯示意圖，雖然經過了簡化，但是基本原理與現代計算機真實的情況的一緻的
3. 記憶體頁與磁盤頁
一般将記憶體看做磁盤的的緩存，有時MMU在工作時，會發現頁表表明某個記憶體頁不在實體記憶體中，此時會觸發一個缺頁異常（Page Fault），此時系統會到磁盤中相應的地方将磁盤頁載入到記憶體中，然後重新執行由于缺頁而失敗的機器指令。關于這部分，因為可以看做對malloc實作是透明的，是以不再詳細講述，有興趣的可以參考《深入了解計算機系統》相關章節。
二. Linux程序級記憶體管理
1. 記憶體排布
明白了虛拟記憶體和實體記憶體的關系及相關的映射機制，下面看一下具體在一個程序内是如何排布記憶體的。
以Linux 64位系統為例。理論上，64bit記憶體位址可用空間為0x0000000000000000 ~ 0xFFFFFFFFFFFFFFFF，這是個相當龐大的空間，Linux實際上隻用了其中一小部分（256T）。
根據Linux核心相關文檔描述，Linux64位作業系統僅使用低47位，高17位做擴充（隻能是全0或全1）。是以，實際用到的位址為空間為0x0000000000000000 ~ 0x00007FFFFFFFFFFF和0xFFFF800000000000 ~ 0xFFFFFFFFFFFFFFFF，其中前面為使用者空間（User Space），後者為核心空間（Kernel Space）。
對使用者來說，主要關注的空間是User Space。将User Space放大後，可以看到裡面主要分為如下幾段：
Code：這是整個使用者空間的最低位址部分，存放的是指令（也就是程式所編譯成的可執行機器碼）
Data：這裡存放的是初始化過的全局變量
BSS：這裡存放的是未初始化的全局變量
Heap：堆，這是我們本文重點關注的地方，堆自低位址向高位址增長，後面要講到的brk相關的系統調用就是從這裡配置設定記憶體
Mapping Area：這裡是與mmap系統調用相關的區域。大多數實際的malloc實作會考慮通過mmap配置設定較大塊的記憶體區域，本文不讨論這種情況。這個區域自高位址向低位址增長
Stack：這是棧區域，自高位址向低位址增長
2. Heap 記憶體模型
一般來說，malloc所申請的記憶體主要從Heap區域配置設定（本文不考慮通過mmap申請大塊記憶體的情況）。
由上文知道，程序所面對的虛拟記憶體位址空間，隻有按頁映射到實體記憶體位址，才能真正使用。受實體存儲容量限制，整個堆虛拟記憶體空間不可能全部映射到實際的實體記憶體。Linux對堆的管理示意如下：
Linux維護一個break指針，這個指針指向堆空間的某個位址。從堆起始位址到break之間的位址空間為映射好的，可以供程序通路；而從break往上，是未映射的位址空間，如果通路這段空間則程式會報錯。
3. 堆記憶體管理實作原理
Linux通過brk和sbrk系統調用操作break指針。兩個系統調用的原型如下, 見man brk:
#include <unistd.h>
int brk(void *addr);
void *sbrk(intptr_t increment);
brk将break指針直接設定為某個位址，而sbrk将break從目前位置移動increment所指定的增量。brk在執行成功時傳回0，否則傳回-1并設定errno為ENOMEM；sbrk成功時傳回break移動之前所指向的位址，否則傳回(void *)-1。
一個小技巧是，如果将increment設定為0，則可以獲得目前break的位址。
另外需要注意的是，由于Linux是按頁進行記憶體映射的，是以如果break被設定為沒有按頁大小對齊，則系統實際上會在最後映射一個完整的頁，進而實際已映射的記憶體空間比break指向的地方要大一些。但是使用break之後的位址是很危險的（盡管也許break之後确實有一小塊可用記憶體位址）。
系統對每一個程序所配置設定的資源不是無限的，包括可映射的記憶體空間，是以每個程序有一個rlimit表示目前程序可用的資源上限。這個限制可以通過getrlimit系統調用得到, 見 man getrlimit
#include <sys/time.h>
#include <sys/resource.h>
int getrlimit(int resource, struct rlimit *rlim);
int setrlimit(int resource, const struct rlimit *rlim);
struct rlimit {
rlim_t rlim_cur; /* Soft limit */
rlim_t rlim_max; /* Hard limit (ceiling for rlim_cur) */
};
每種資源有軟限制和硬限制，并且可以通過setrlimit對rlimit進行有條件設定。其中硬限制作為軟限制的上限，非特權程序隻能設定軟限制，且不能超過硬限制。
break指針通過在Heap's Start 和 rlimit 之間來回擺動, 來标記記憶體最大占用位置. 因為malloc出來的是一段記憶體塊, 那麼實際使用中在Heap's Start 和 break 之間存在着記憶體碎片, 有什麼方法能更好的利用這些記憶體碎片呢?