本文介紹malloc的實現(xiàn)及其malloc在進行堆擴展操作，并分析了虛擬地址到物理地址是如何實現(xiàn)映射關系。 ordeder原創(chuàng)，原文鏈接： http://blog.csdn.net/ordeder/article/details/41654509
該結構是由進程task_struct.mm_struct進行管理的mm_struct的定義如下：
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 */ ... //描述用戶空間的段分布：數(shù)據(jù)段，代碼段，堆棧段 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描述了進程用戶空間數(shù)據(jù)段的所在地址。對于堆空間而言，start_brk是堆空間的起始地址，堆是向上擴展的。對于進程堆空間的擴展，brk來記錄堆的頂部位置。而進程動態(tài)申請的空間的已經(jīng)使用到的地址空間（正在使用的變量）是被映射的，這些地址空間記錄于鏈表struct vm_area_struct * mmap中。
虛擬地址和物理地址的映射 ： http://blog.csdn.net/ordeder/article/details/41630945
malloc用于用戶空間堆擴展的函數(shù)接口。該函數(shù)是C庫，屬于封裝了相關系統(tǒng)調(diào)用（brk()）的glibc庫函數(shù)。而不是系統(tǒng)調(diào)用（系統(tǒng)可沒有sys_malloc()。如果談及malloc函數(shù)涉及的系統(tǒng)內(nèi)核的那些操作，那么總體可以分為用戶空間層面和內(nèi)核空間層面來討論。
malloc 的源碼可見 http://repo.or.cz/w/glibc.git/blob/HEAD:/malloc/malloc.c
Malloc和free是在用戶層工作的，該接口為用戶提供一個比較方便管理堆的接口。它的主要工作是維護一個空閑的堆空間緩沖區(qū)鏈表。該緩沖區(qū)可以用如下數(shù)據(jù)結構表述：
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; };簡化版的空閑緩沖區(qū)鏈表如下所示，圖中head即為上述的malloc_chunk結構。而緊接著的size大小的內(nèi)存區(qū)間是該chunk對應的數(shù)據(jù)區(qū)。 
【malloc】 每當進程調(diào)用malloc，首先會在該堆緩沖區(qū)尋找足夠大小的內(nèi)存塊分配給進程（選擇緩沖區(qū)中的那個塊就有首次命中和最佳命中兩種算法）。如果freechunklist已無法滿足需求的chunk時，那么malloc會通過調(diào)用系統(tǒng)調(diào)用brk()將進程空間的堆進行擴展，在新擴展的堆空間上建立一個新的chunk并加入到freelist中，這個過程相當于進程批量想系統(tǒng)申請一塊內(nèi)存（大小可能比實際需求大得多）。
malloc返回的地址是chunk的中用于存儲數(shù)據(jù)的首地址，即： chunk + sizeof（chunk）
一個簡單的首次命中malloc的偽代碼：
chunk free_list malloc(size) foreach(chuck in freelist) if(chunk.size >size) return chunk + sizeof(chunk) //空閑緩沖區(qū)無法滿足需求，那么像系統(tǒng)批發(fā)內(nèi)存 add = sys_brk(brk+(size +sizeof(chunk))) newchunk = (chunk)add; newchunk.size = size; ... return newchunk + sizeof(newchunk)【free】 free操作是對堆空間的回收，回收的區(qū)塊并不是立即返還給內(nèi)核。而是將區(qū)塊對應的chunk“標記”為空閑，加入空閑隊列中。當然，如果空閑隊列中出現(xiàn)相鄰地址的chunk，那么可以考慮合并，已解決內(nèi)存的碎片化，一遍滿足之后的大內(nèi)存申請的需求。 一個簡單的free偽代碼：將釋放的地址空間加入空閑鏈表中
free(add) pchunk = add - sizeof(chunk) insert_to_freelist(pchunk)上文中，malloc的空閑chunk列表無法滿足用戶的需求，那么要通過sys_brk()進行堆的擴展，這時候才真正算得上進入內(nèi)核空間。 sys_brk()涉及的主要操作有： 1. 在mm_struct中的堆上界brk延伸到newbrk：即申請一塊vma，vma.start=brk vma.end=newbrk 2. 為該虛擬區(qū)間塊進行物理內(nèi)存的映射：從虛擬空間vma.start~vma.end中的每個內(nèi)存頁進行映射：
addr = vma.start do{ handle_mm_fault(mm,vma,addr,...) addr += PAGESIZE }while(addr< vma.end)函數(shù)handle_mm_fault為addr所在的內(nèi)存頁映射物理頁面。實現(xiàn)虛擬空間到物理空間的換算和映射。
通過alloc_page申請一個物理頁面；換算addr在進程pdg映射中所在的pte地址；將addr對應的pte設置為物理頁面的首地址。
當進程讀取堆空間的地址vaddr時，虛擬地址vaddr到物理頁面的映射如下圖所示。 
內(nèi)核源碼情景分析 http://blog.csdn.net/kobbee9/article/details/7397010 http://www.open-open.com/lib/view/open1409716051963.html
新聞熱點
疑難解答
