面試官：你好，請先做自我介紹

我：巴拉巴拉，我喜歡打籃球……

面試官：請解釋下malloc的實現(xiàn)原理

我：我不會

面試官：那就先這樣，我們就不浪費大家的時間了。

=====

在開發(fā)c或c++時，經(jīng)常需要分配內(nèi)存，如今常用的分配內(nèi)存函數(shù)為malloc,tcmalloc,jemalloc,其中屬于malloc使用最平常，因為屬于c標(biāo)準(zhǔn)庫函數(shù)，但是網(wǎng)上有有實驗證明另外兩個效率比malloc高，這篇文章主要還是分析malloc，因為經(jīng)常用到malloc來分配內(nèi)存，而且大家也知道這malloc分配的內(nèi)存是從堆中分配的。

要了解malloc之前，我們需要有一定的內(nèi)存基礎(chǔ)知識。

linux系統(tǒng)向用戶提供申請的內(nèi)存有brk(sbrk)和mmap函數(shù)，我們就從這兩個函數(shù)開始說起。

首先再次給出linux進程的內(nèi)存模型

brk()和sbrk()函數(shù)

這兩個函數(shù)的定義如下：

這兩個函數(shù)的作用主要是擴展heap的上界brk。

第一個函數(shù)的參數(shù)為設(shè)置的新的brk上界地址，如果成功返回0，失敗返回-1。

第二個函數(shù)的參數(shù)為需要申請的內(nèi)存的大小，然后返回heap新的上界brk地址。如果sbrk的參數(shù)為0，則返回的為原來的brk地址。

mmap函數(shù)

mmap和munmap函數(shù)定義如下：

mmap函數(shù)第一種用法是映射磁盤文件到內(nèi)存中；而malloc使用的mmap函數(shù)的第二種用法，即匿名映射，匿名映射不映射磁盤文件，而是向映射區(qū)申請一塊內(nèi)存。

munmap函數(shù)是用于釋放內(nèi)存，第一個參數(shù)為內(nèi)存首地址，第二個參數(shù)為內(nèi)存的長度。

接下來看下mmap函數(shù)的參數(shù)。

prot:期望的內(nèi)存保護標(biāo)志,不能與文件的打開模式?jīng)_突。是以下的某個值,可以通過 or 運算合理地組合在一起。PROT_EXEC(頁內(nèi)容可以被執(zhí)行);PROT_READ(頁內(nèi)容可以被讀取);PROT_WRITE(頁可以被寫入);PROT_NONE(頁不可訪問).

flags:指定映射對象的類型,映射選項和映射頁是否可以共享。它的值可以是一個或者多個以下位的組合體

MAP_FIXED //使用指定的映射起始地址，如果由start和len參數(shù)指定的內(nèi)存區(qū)重疊于現(xiàn)存的映射空間，重疊部分將會被丟棄。如果指定的起始地址不可用，操作將會失敗。并且起始地址必須落在頁的邊界上。

MAP_SHARED //與其它所有映射這個對象的進程共享映射空間。對共享區(qū)的寫入，相當(dāng)于輸出到文件。直到msync()或者munmap()被調(diào)用，文件實際上不會被更新。

MAP_PRIVATE //建立一個寫入時拷貝的私有映射。內(nèi)存區(qū)域的寫入不會影響到原文件。這個標(biāo)志和以上標(biāo)志是互斥的，只能使用其中一個。

MAP_LOCKED //鎖定映射區(qū)的頁面，從而防止頁面被交換出內(nèi)存。

MAP_ANONYMOUS //匿名映射，映射區(qū)不與任何文件關(guān)聯(lián)。

fd為映射的文件，如果是匿名映射，可以設(shè)為-1；

offset為被映射文件內(nèi)容的起點偏移；

malloc函數(shù)使用MAP_ANONYMOUS匿名映射，length為申請內(nèi)存塊大小，返回內(nèi)存塊的首地址；

當(dāng)申請小內(nèi)存的時，malloc使用sbrk分配內(nèi)存；當(dāng)申請大內(nèi)存時，使用mmap函數(shù)申請內(nèi)存；但是這只是分配了虛擬內(nèi)存，還沒有映射到物理內(nèi)存，當(dāng)訪問申請的內(nèi)存時，才會因為缺頁異常，內(nèi)核分配物理內(nèi)存。

malloc實現(xiàn)原理

chunk簡介

由于brk/sbrk/mmap屬于系統(tǒng)調(diào)用，如果每次申請內(nèi)存，都調(diào)用這三個函數(shù)中的一個，那么每次都要產(chǎn)生系統(tǒng)調(diào)用開銷，這是非常影響性能的；其次，這樣申請的內(nèi)存容易產(chǎn)生碎片，因為堆是從低地址到高地址，如果低地址的內(nèi)存沒有被釋放，高地址的內(nèi)存就不能被回收。

鑒于此，malloc采用的是內(nèi)存池的實現(xiàn)方式，malloc內(nèi)存池實現(xiàn)方式更類似于STL分配器和memcached的內(nèi)存池，先申請一大塊內(nèi)存，然后將內(nèi)存分成不同大小的內(nèi)存塊，然后用戶申請內(nèi)存時，直接從內(nèi)存池中選擇一塊相近的內(nèi)存塊即可。

malloc利用chunk結(jié)構(gòu)來管理內(nèi)存塊，malloc就是由不同大小的chunk鏈表組成的。

一個使用中的chunk的結(jié)構(gòu)如下圖:

malloc會給用戶分配的空間的前后加上一些控制信息，用這樣的方法來記錄分配的信息，以便完成分配和釋放工作。chunk指針指向chunk開始的地方,圖中的mem指針才是真正返回給用戶的內(nèi)存指針。

1 Chunk?的第二個域的最低一位為 P,它表示前一個塊是否在使用中,P 為 0 則表示前一個 chunk 為空閑,這時chunk的第一個域 prev_size 才有效,prev_size 表示前一個 chunk 的 size,程序可以使用這個值來找到前一個 chunk 的開始地址。當(dāng) P 為 1 時,表示前一個 chunk 正在使用中,prev_size程序也就不可以得到前一個 chunk 的大小。不能對前一個 chunk 進行任何操作。malloc分配的第一個塊總是將 P 設(shè)為 1,以防止程序引用到不存在的區(qū)域。

2 Chunk 的第二個域的倒數(shù)第二個位為 M,他表示當(dāng)前 chunk 是從哪個內(nèi)存區(qū)域獲得的虛擬內(nèi)存。M 為 1 表示該 chunk 是從 mmap 映射區(qū)域分配的,否則是從 heap 區(qū)域分配的。

3 Chunk 的第二個域倒數(shù)第三個位為 A,表示該 chunk 屬于主分配區(qū)或者非主分配區(qū),如果屬于非主分配區(qū),將該位置為 1,否則置為 0。

以下圖是一個空閑的chunk在內(nèi)存中的結(jié)構(gòu):

當(dāng)chunk空閑時，其M狀態(tài)是不存在的，只有AP狀態(tài)，原本是用戶數(shù)據(jù)區(qū)的地方存儲了四個指針，指針fd指向后一個空閑的chunk,而bk指向前一個空閑的chunk，malloc通過這兩個指針將大小相近的chunk連成一個雙向鏈表。在large bin中的空閑chunk，還有兩個指針，fd_nextsize和bk_nextsize，用于加快在large bin中查找最近匹配的空閑chunk。不同的chunk鏈表又是通過bins或者fastbins來組織的。

chunk容器bins

malloc將內(nèi)存分成了大小不同的chunk，然后通過bins來組織起來，

先來看下bin結(jié)構(gòu):

malloc將相似大小的chunk用雙向鏈表鏈接起來，這樣一個鏈表被稱為一個bin。malloc一共維護了128個bin，并使用一個數(shù)組來存儲這些bin。數(shù)組中第一個為unsorted bin,數(shù)組從2開始編號，前64個bin為small bins，同一個small bin中的chunk具有相同的大小，兩個相鄰的small bin中的chunk大小相差8bytes。small bins后面的bin被稱作large bins。large bins中的每一個bin分別包含了一個給定范圍內(nèi)的chunk，其中的chunk按大小序排列。large bin的每個bin相差64字節(jié)。

malloc除了有unsorted bin，small bin,large bin三個bin之外，還有一個fast bin。一般的情況是,程序在運行時會經(jīng)常需要申請和釋放一些較小的內(nèi)存空間。當(dāng)分配器合并了相鄰的幾個小的 chunk 之后,也許馬上就會有另一個小塊內(nèi)存的請求,這樣分配器又需要從大的空閑內(nèi)存中切分出一塊,這樣無疑是比較低效的,故而,malloc 中在分配過程中引入了 fast bins,不大于 max_fast(默認(rèn)值為 64B)的 chunk 被釋放后,首先會被放到 fast bins中,fast bins 中的 chunk 并不改變它的使用標(biāo)志 P。

這樣也就無法將它們合并,當(dāng)需要給用戶分配的 chunk 小于或等于 max_fast 時,malloc 首先會在 fast bins 中查找相應(yīng)的空閑塊,然后才會去查找 bins 中的空閑 chunk。在某個特定的時候,malloc 會遍歷 fast bins 中的 chunk,17將相鄰的空閑 chunk 進行合并,并將合并后的 chunk 加入 unsorted bin 中,然后再將 usorted bin 里的 chunk 加入 bins 中。

unsorted bin 的隊列使用 bins 數(shù)組的第一個,如果被用戶釋放的 chunk 大于 max_fast,或者 fast bins 中的空閑 chunk 合并后,這些 chunk 首先會被放到 unsorted bin 隊列中,在進行 malloc 操作的時候,如果在 fast bins 中沒有找到合適的 chunk,則malloc 會先在 unsorted bin 中查找合適的空閑 chunk,然后才查找 bins。如果 unsorted bin 不能滿足分配要求。malloc便會將 unsorted bin 中的 chunk 加入 bins 中。然后再從 bins 中繼續(xù)進行查找和分配過程。從這個過程可以看出來,unsorted bin 可以看做是 bins 的一個緩沖區(qū),增加它只是為了加快分配的速度。

除了上述四種bins之外，malloc還有三種內(nèi)存區(qū)。

1 當(dāng)fast bin和bins都不能滿足內(nèi)存需求時，malloc會設(shè)法在top chunk中分配一塊內(nèi)存給用戶；top chunk為在mmap區(qū)域分配一塊較大的空閑內(nèi)存模擬sub-heap。

2 當(dāng)chunk足夠大，fast bin和bins都不能滿足要求，甚至top chunk都不能滿足時，malloc會從mmap來直接使用內(nèi)存映射來將頁映射到進程空間，這樣的chunk釋放時，直接解除映射，歸還給操作系統(tǒng)。

3 Last remainder是另外一種特殊的chunk，就像top chunk和mmaped chunk一樣，不會在任何bins中找到這種chunk。當(dāng)需要分配一個small chunk,但在small bins中找不到合適的chunk，如果last remainder chunk的大小大于所需要的small chunk大小，last remainder chunk被分裂成兩個chunk，其中一個chunk返回給用戶，另一個chunk變成新的last remainder chunk。

malloc內(nèi)存分配

一開始時，brk和start_brk是相等的，這時實際heap大小為0；如果第一次用戶請求的內(nèi)存大小小于mmap分配閾值，則malloc會申請(chunk_size+128kb) align 4kb大小的空間作為初始的heap。初始化heap之后，第二次申請的內(nèi)存如果還是小于mmap分配閾值時，malloc會先查找fast bins,如果不能找到匹配的chunk，則查找small bins。若還是不行，合并fast bins,把chunk 加入到unsorted bin，在unsorted bin中查找，若還是不行，把unsorted bin中的chunk全加入large bins中，并查找large bins。在fast bins和small bins中查找都需要精確匹配，而在large bins中查找時，則遵循"smalest-first,best-fit"的原則，不需要精確匹配。

若以上都失敗了，malloc則會考慮使用top chunk。若top chunk也不能滿足分配，且所需的chunk大小大于mmap分配閾值，則使用mmap進行分配。否則增加heap，增加top chunk，以滿足分配要求。