面試官：你好，請(qǐng)先做自我介紹

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

面試官：請(qǐng)解釋下malloc的實(shí)現(xiàn)原理

我：我不會(huì)

面試官：那就先這樣，我們就不浪費(fèi)大家的時(shí)間了。

=====

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

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

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

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

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

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

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

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

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

mmap函數(shù)

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

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

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

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

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

flags:指定映射對(duì)象的類型,映射選項(xiàng)和映射頁(yè)是否可以共享。它的值可以是一個(gè)或者多個(gè)以下位的組合體

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

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

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

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

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

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

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

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

當(dāng)申請(qǐng)小內(nèi)存的時(shí)，malloc使用sbrk分配內(nèi)存；當(dāng)申請(qǐng)大內(nèi)存時(shí)，使用mmap函數(shù)申請(qǐng)內(nèi)存；但是這只是分配了虛擬內(nèi)存，還沒(méi)有映射到物理內(nèi)存，當(dāng)訪問(wèn)申請(qǐng)的內(nèi)存時(shí)，才會(huì)因?yàn)槿表?yè)異常，內(nèi)核分配物理內(nèi)存。

malloc實(shí)現(xiàn)原理

chunk簡(jiǎn)介

由于brk/sbrk/mmap屬于系統(tǒng)調(diào)用，如果每次申請(qǐng)內(nèi)存，都調(diào)用這三個(gè)函數(shù)中的一個(gè)，那么每次都要產(chǎn)生系統(tǒng)調(diào)用開(kāi)銷，這是非常影響性能的；其次，這樣申請(qǐng)的內(nèi)存容易產(chǎn)生碎片，因?yàn)槎咽菑牡偷刂返礁叩刂罚?strong>如果低地址的內(nèi)存沒(méi)有被釋放，高地址的內(nèi)存就不能被回收。

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

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

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

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

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

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

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

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

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

chunk容器bins

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

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

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

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

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

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

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

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

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

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

malloc內(nèi)存分配

一開(kāi)始時(shí)，brk和start_brk是相等的，這時(shí)實(shí)際heap大小為0；如果第一次用戶請(qǐng)求的內(nèi)存大小小于mmap分配閾值，則malloc會(huì)申請(qǐng)(chunk_size+128kb) align 4kb大小的空間作為初始的heap。初始化heap之后，第二次申請(qǐng)的內(nèi)存如果還是小于mmap分配閾值時(shí)，malloc會(huì)先查找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中查找時(shí)，則遵循"smalest-first,best-fit"的原則，不需要精確匹配。

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