Linux Malloc分析-從用戶空間到內核空間? 本文介紹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的定義如下：
?
[cpp] view plaincopyprint?
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;?? ????...?? };?? 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是在用戶層工作的，該接口為用戶提供一個比較方便管理堆的接口。它的主要工作是維護一個空閑的堆空間緩沖區鏈表。該緩沖區可以用如下數據結構表述：
?
[cpp] view plaincopyprint?
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;?? };?? 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的偽代碼：
[cpp] view plaincopyprint?
chunk?free_list?? malloc(size)?? ??foreach(chuck?in?freelist)?? ????if(chunk.size?>size)?? ??????return?chunk?+?sizeof(chunk)?? ??//空閑緩沖區無法滿足需求，那么像系統批發內存 ?? ??add?=?sys_brk(brk+(size?+sizeof(chunk)))?? ??newchunk?=?(chunk)add;?? ??newchunk.size?=?size;?? ??...?? ??return?newchunk?+?sizeof(newchunk)?? chunk free_list malloc(size) foreach(chuck in freelist) if(chunk.size >size) return chunk + sizeof(chunk) //空閑緩沖區無法滿足需求，那么像系統批發內存 add = sys_brk(brk+(size +sizeof(chunk))) newchunk = (chunk)add; newchunk.size = size; ... return newchunk + sizeof(newchunk)
【free】
??????? free操作是對堆空間的回收，回收的區塊并不是立即返還給內核。而是將區塊對應的chunk“標記”為空閑，加入空閑隊列中。當然，如果空閑隊列中出現相鄰地址的chunk，那么可以考慮合并，已解決內存的碎片化，一遍滿足之后的大內存申請的需求。
一個簡單的free偽代碼：將釋放的地址空間加入空閑鏈表中
?
[cpp] view plaincopyprint?
free(add)?? ??pchunk?=?add?-?sizeof(chunk)?? ??insert_to_freelist(pchunk)?? free(add) pchunk = add - sizeof(chunk) insert_to_freelist(pchunk)
2.2 內核層 ?
上文中，malloc的空閑chunk列表無法滿足用戶的需求，那么要通過sys_brk()進行堆的擴展，這時候才真正算得上進入內核空間。
sys_brk()涉及的主要操作有：
1. 在mm_struct中的堆上界brk延伸到newbrk：即申請一塊vma，vma.start=brk vma.end=newbrk
2. 為該虛擬區間塊進行物理內存的映射：從虛擬空間vma.start~vma.end中的每個內存頁進行映射：
[cpp] view plaincopyprint?
addr?=?vma.start?? do{?? ??handle_mm_fault(mm,vma,addr,...)?? ??addr?+=?PAGESIZE?? }while(addr<?vma.end)?? addr = vma.start do{ handle_mm_fault(mm,vma,addr,...) addr += PAGESIZE }while(addr< vma.end)
?
函數handle_mm_fault為addr所在的內存頁映射物理頁面。實現虛擬空間到物理空間的換算和映射。
1.通過alloc_page申請一個物理頁面；
2.換算addr在進程pdg映射中所在的pte地址；
3.將addr對應的pte設置為物理頁面的首地址。
2.3 虛擬地址與物理地址 ?
當進程讀取堆空間的地址vaddr時，虛擬地址vaddr到物理頁面的映射如下圖所示。
?
1. 用戶空間的虛擬地址vaddr通過MMU（pgd，pmd，pte）找到對應的頁表項pte記錄的物理地址paddr
?
3 總結 ?
1 Malloc 和 free 怎么看著就是個用戶空間的內存池。特別free的實現。
2 堆的擴展依據brk的移動。Vm_area記錄了虛擬空間中已使用的地址塊。
3 每個進程的虛擬地址到物理地址的映射是有進程mm.pgd決定的，在該結構中記錄了虛擬頁號到物理頁號的映射關系。
參考 內核源碼情景分析
http://blog.csdn.net/kobbee9/article/details/7397010
http://www.open-open.com/lib/view/open1409716051963.html
附錄 ?
[cpp] view plaincopyprint?
#define?pgd_offset(mm,?address)?((mm)->pgd?+?pgd_index(address)) ?? int?handle_mm_fault(struct?mm_struct?*mm,?struct?vm_area_struct?*?vma,?? ????unsigned?long?address,?int?write_access)?? {?? ????int?ret?=?-1;?? ????pgd_t?*pgd;?? ????pmd_t?*pmd;?? ?? ????pgd?=?pgd_offset(mm,?address);?? ????pmd?=?pmd_alloc(pgd,?address);?? ?? ????if?(pmd)?{?? ????????pte_t?*?pte?=?pte_alloc(pmd,?address);?//pmd是空的，所以返回的是pgd[address]的pte項目 ?? ????????if?(pte)?? ????????????ret?=?handle_pte_fault(mm,?vma,?address,?write_access,?pte);?? ????}?? ????return?ret;?? }?? ?? //32位地址，pmd沒有意義 ?? extern?inline?pmd_t?*?pmd_alloc(pgd_t?*?pgd,?unsigned?long?address)?? {?? ????return?(pmd_t?*)?pgd;?? }?? ?? //為address地址所在的頁構建pte索引項 ?? extern?inline?pte_t?*pte_alloc(pmd_t?*pmd,?unsigned?long?address)?? {?? ????address?=?(address?>>?PAGE_SHIFT)?&?(PTRS_PER_PTE?-?1);?? ????if?(pmd_none(*pmd))?{?? ????????pte_t?*page?=?get_pte_fast();?? ?? ????????if?(!page)?? ????????????return?get_pte_slow(pmd,?address);?? ????????pmd_set(pmd,page);?? ????????return?page?+?address;?? ????}?? ????if?(pmd_bad(*pmd))?{?? ????????__bad_pte(pmd);?? ????????return?NULL;?? ????}?? ????return?(pte_t?*)__pmd_page(*pmd)?+?address;?? }?? ?? //為address對應的頁面分配物理頁面 ?? static?inline?int?handle_pte_fault(struct?mm_struct?*mm,?? ????struct?vm_area_struct?*?vma,?unsigned?long?address,?? ????int?write_access,?pte_t?*?pte)?? {?? ????pte_t?entry;?? ????entry?=?*pte;?? ????if?(!pte_present(entry))?{?? ????????...?? ????????if?(pte_none(entry))?? ????????????return?do_no_page(mm,?vma,?address,?write_access,?pte);//缺頁，分配物理頁 ?? ????????...?? ????}?? ????...?? ????return?1;?? }?? ?? ?? static?int?do_no_page(struct?mm_struct?*?mm,?struct?vm_area_struct?*?vma,?? ????unsigned?long?address,?int?write_access,?pte_t?*page_table)?? {?? ????struct?page?*?new_page;?? ????pte_t?entry;?? ????//匿名（對于虛擬存儲空間而言）的物理映射 ?? ????if?(!vma->vm_ops?||?!vma->vm_ops->nopage)?? ????????return?do_anonymous_page(mm,?vma,?page_table,?write_access,?address);?? ?? ??//一下是文件的缺頁處理，在此不表 ?? ????...?? }?? ?? //通過page指針，即可計算page的物理地址：?物理地址?=?(page指針?-?mem_map)*?頁大小?+?物理內存起始地址 ?? /*? ?*?匿名映射，用于虛存到物理內存? ?*/?? static?int?do_anonymous_page(struct?mm_struct?*?mm,?struct?vm_area_struct?*?vma,?pte_t?*page_table,?int?write_access,?unsigned?long?addr)?? {?? ????struct?page?*page?=?NULL;?? ????pte_t?entry?=?pte_wrprotect(mk_pte(ZERO_PAGE(addr),?vma->vm_page_prot));?? ????if?(write_access)?{?? ????????page?=?alloc_page(GFP_HIGHUSER);?//從高端內存中分配內存 ?? ????????if?(!page)?? ????????????return?-1;?? ????????clear_user_highpage(page,?addr);?? ????????entry?=?pte_mkwrite(pte_mkdirty(mk_pte(page,?vma->vm_page_prot)));?? ????????mm->rss++;?? ????????flush_page_to_ram(page);?? ????}?? ????set_pte(page_table,?entry);?//?*page_table?=?entry; ?? ????/*?No?need?to?invalidate?-?it?was?non-present?before?*/?? ????update_mmu_cache(vma,?addr,?entry);?? ????return?1;???/*?Minor?fault?*/?? }?? ?? #define?__MEMORY_START??????CONFIG_MEMORY_START?//物理內存中用于動態分配使用的起始地址 ?? void?flush_page_to_ram(struct?page?*pg)?? {?? ????unsigned?long?phys;?? ?? ????/*?Physical?address?of?this?page?*/?? ????phys?=?(pg?-?mem_map)*PAGE_SIZE?+?__MEMORY_START;?? ????__flush_page_to_ram(phys_to_virt(phys));?? }?? ?? #define?__virt_to_phys(vpage)?((vpage)?-?PAGE_OFFSET?+?PHYS_OFFSET) ?? #define?__phys_to_virt(ppage)?((ppage)?+?PAGE_OFFSET?-?PHYS_OFFSET)?? #define pgd_offset(mm, address) ((mm)->pgd + pgd_index(address)) int handle_mm_fault(struct mm_struct *mm, struct vm_area_struct * vma, unsigned long address, int write_access) { int ret = -1; pgd_t *pgd; pmd_t *pmd; pgd = pgd_offset(mm, address); pmd = pmd_alloc(pgd, address); if (pmd) { pte_t * pte = pte_alloc(pmd, address); //pmd是空的，所以返回的是pgd[address]的pte項目 if (pte) ret = handle_pte_fault(mm, vma, address, write_access, pte); } return ret; } //32位地址，pmd沒有意義 extern inline pmd_t * pmd_alloc(pgd_t * pgd, unsigned long address) { return (pmd_t *) pgd; } //為address地址所在的頁構建pte索引項 extern inline pte_t *pte_alloc(pmd_t *pmd, unsigned long address) { address = (address >> PAGE_SHIFT) & (PTRS_PER_PTE - 1); if (pmd_none(*pmd)) { pte_t *page = get_pte_fast(); if (!page) return get_pte_slow(pmd, address); pmd_set(pmd,page); return page + address; } if (pmd_bad(*pmd)) { __bad_pte(pmd); return NULL; } return (pte_t *)__pmd_page(*pmd) + address; } //為address對應的頁面分配物理頁面 static inline int handle_pte_fault(struct mm_struct *mm, struct vm_area_struct * vma, unsigned long address, int write_access, pte_t * pte) { pte_t entry; entry = *pte; if (!pte_present(entry)) { ... if (pte_none(entry)) return do_no_page(mm, vma, address, write_access, pte);//缺頁，分配物理頁 ... } ... return 1; } static int do_no_page(struct mm_struct * mm, struct vm_area_struct * vma, unsigned long address, int write_access, pte_t *page_table) { struct page * new_page; pte_t entry; //匿名（對于虛擬存儲空間而言）的物理映射 if (!vma->vm_ops || !vma->vm_ops->nopage) return do_anonymous_page(mm, vma, page_table, write_access, address); //一下是文件的缺頁處理，在此不表 ... } //通過page指針，即可計算page的物理地址： 物理地址 = (page指針 - mem_map)* 頁大小 + 物理內存起始地址 /* * 匿名映射，用于虛存到物理內存 */ static int do_anonymous_page(struct mm_struct * mm, struct vm_area_struct * vma, pte_t *page_table, int write_access, unsigned long addr) { struct page *page = NULL; pte_t entry = pte_wrprotect(mk_pte(ZERO_PAGE(addr), vma->vm_page_prot)); if (write_access) { page = alloc_page(GFP_HIGHUSER); //從高端內存中分配內存 if (!page) return -1; clear_user_highpage(page, addr); entry = pte_mkwrite(pte_mkdirty(mk_pte(page, vma->vm_page_prot))); mm->rss++; flush_page_to_ram(page); } set_pte(page_table, entry); // *page_table = entry; /* No need to invalidate - it was non-present before */ update_mmu_cache(vma, addr, entry); return 1; /* Minor fault */ } #define __MEMORY_START CONFIG_MEMORY_START //物理內存中用于動態分配使用的起始地址 void flush_page_to_ram(struct page *pg) { unsigned long phys; /* Physical address of this page */ phys = (pg - mem_map)*PAGE_SIZE + __MEMORY_START; __flush_page_to_ram(phys_to_virt(phys)); } #define __virt_to_phys(vpage) ((vpage) - PAGE_OFFSET + PHYS_OFFSET) #define __phys_to_virt(ppage) ((ppage) + PAGE_OFFSET - PHYS_OFFSET)
?
轉載于:https://www.cnblogs.com/onlyforcloud/articles/4465942.html
總結
以上是生活随笔 為你收集整理的Linux Malloc分析-从用户空间到内核空间 的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網站內容還不錯，歡迎將生活随笔 推薦給好友。
