本文介紹malloc的實現及其malloc在進行堆擴展操作，並分析了虛擬地址到物理地址是如何實現映射關系。

ordeder原創，原文鏈接： http://blog.csdn.net/ordeder/article/details/41654509

1背景知識

1.1 進程的用戶空間

 

 

圖1：來源 http://www.open-open.com/lib/view/open1409716051963.html

 

該結構是由進程task_struct.mm_struct進行管理的mm_struct的定義如下：

 

? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 struct mm_struct {     struct vm_area_struct * mmap;   /* list of VMAs */     ...     pgd_t * pgd;                //用於地址映射     atomic_t mm_users;          /* How many users with user space? */     atomic_t mm_count;          /* How many references to "struct mm_struct" (users count as 1) */     int map_count;              /* number of VMAs */     ...     //描述用戶空間的段分布：數據段，代碼段，堆棧段     unsigned long start_code, end_code, start_data, end_data;     unsigned long start_brk, brk, start_stack;     unsigned long arg_start, arg_end, env_start, env_end;     unsigned long rss, total_vm, locked_vm;     ... };

 

結構中的startxxx與endxxx描述了進程用戶空間數據段的所在地址。對於堆空間而言，start_brk是堆空間的起始地址，堆是向上擴展的。對於進程堆空間的擴展，brk來記錄堆的頂部位置。而進程動態申請的空間的已經使用到的地址空間（正在使用的變量）是被映射的，這些地址空間記錄於鏈表struct vm_area_struct * mmap中。

1.2 地址映射

虛擬地址和物理地址的映射 ： http://blog.csdn.net/ordeder/article/details/41630945

 

2 malloc 和free

malloc用於用戶空間堆擴展的函數接口。該函數是C庫，屬於封裝了相關系統調用（brk()）的glibc庫函數。而不是系統調用（系統可沒有sys_malloc()。如果談及malloc函數涉及的系統內核的那些操作，那麼總體可以分為用戶空間層面和內核空間層面來討論。

2.1 用戶層

 

malloc 的源碼可見 http://repo.or.cz/w/glibc.git/blob/HEAD:/malloc/malloc.c

Malloc和free是在用戶層工作的，該接口為用戶提供一個比較方便管理堆的接口。它的主要工作是維護一個空閒的堆空間緩沖區鏈表。該緩沖區可以用如下數據結構表述：

 

? 1 2 3 4 5 6 7 8 9 struct malloc_chunk {     INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */     INTERNAL_SIZE_T 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; };

 

簡化版的空閒緩沖區鏈表如下所示，圖中head即為上述的malloc_chunk結構。而緊接著的size大小的內存區間是該chunk對應的數據區。

【malloc】

每當進程調用malloc，首先會在該堆緩沖區尋找足夠大小的內存塊分配給進程（選擇緩沖區中的那個塊就有首次命中和最佳命中兩種算法）。如果freechunklist已無法滿足需求的chunk時，那麼malloc會通過調用系統調用brk()將進程空間的堆進行擴展，在新擴展的堆空間上建立一個新的chunk並加入到freelist中，這個過程相當於進程批量想系統申請一塊內存（大小可能比實際需求大得多）。

malloc返回的地址是chunk的中用於存儲數據的首地址，即： chunk + sizeof（chunk）

一個簡單的首次命中malloc的偽代碼：