文章目錄

• ptmalloc
• 設(shè)計(jì)假設(shè)
• Arena
• Chunk
• Bins
• 內(nèi)存分配、釋放流程
• 總結(jié)

---

C++ STL : SGI-STL空間配置器源碼剖析
Linux 內(nèi)存管理 | 物理內(nèi)存管理：物理內(nèi)存、內(nèi)存碎片、伙伴系統(tǒng)、slab分配器
Linux 內(nèi)存管理 | 虛擬內(nèi)存管理：虛擬內(nèi)存空間、虛擬內(nèi)存分配

在之前的幾篇博客中，我曾經(jīng)介紹過(guò)STL空間配置器、BuddySystem、Slab分配器等內(nèi)存管理機(jī)制，也曾經(jīng)簡(jiǎn)單的提及過(guò)linux用戶態(tài)內(nèi)存分配的策略，這一次就來(lái)深入講一講在用戶態(tài)進(jìn)行內(nèi)存分配時(shí)，到底做了什么。

---

ptmalloc

在Linux中，當(dāng)我們申請(qǐng)的內(nèi)存小于128K時(shí)，malloc會(huì)使用sbrk或者brk在堆區(qū)分配內(nèi)存。而當(dāng)我們申請(qǐng)大于128K的大塊空間時(shí)，會(huì)使用mmap在映射區(qū)進(jìn)行分配。

但是由于上述的brk/sbrk/mmap都屬于系統(tǒng)調(diào)用，因此當(dāng)我們每次調(diào)用它們時(shí)，就會(huì)從用戶態(tài)切換至內(nèi)核態(tài)，在內(nèi)核態(tài)完成內(nèi)存分配后再返回用戶態(tài)。

倘若每次申請(qǐng)內(nèi)存都要因?yàn)橄到y(tǒng)調(diào)用而產(chǎn)生大量的CPU開(kāi)銷(xiāo)，那么性能會(huì)大打折扣。并且從上面的圖我們也可以看出來(lái)，堆是從低地址往高地址增長(zhǎng)，如果低地址的內(nèi)存沒(méi)有被釋放，則高地址的內(nèi)存就不能被回收，就會(huì)產(chǎn)生內(nèi)存碎片的問(wèn)題。

那么Linux中的malloc是如何實(shí)現(xiàn)解決這個(gè)問(wèn)題的呢？

這就要提到大名鼎鼎的ptmalloc了，ptmalloc是glibc中默認(rèn)的內(nèi)存管理器。其底層采取了分箱式內(nèi)存管理機(jī)制，也就是實(shí)現(xiàn)了一個(gè)類(lèi)似哈希桶結(jié)構(gòu)的內(nèi)存池，當(dāng)我們通過(guò)malloc和free申請(qǐng)和釋放內(nèi)存的時(shí)候，ptmalloc就會(huì)代替我們將這些內(nèi)存進(jìn)行管理，通過(guò)一系列的內(nèi)存合并、申請(qǐng)策略，來(lái)讓用戶申請(qǐng)和釋放內(nèi)存的時(shí)候更加的高效且安全。

下面就來(lái)詳細(xì)的介紹一下ptmalloc的工作原理

---

設(shè)計(jì)假設(shè)

ptmalloc在設(shè)計(jì)時(shí)集合了高效率、高空間利用率、高可用等目標(biāo)，因此有了如下幾種設(shè)計(jì)假設(shè)

具有長(zhǎng)生命周期的大內(nèi)存分配使用 mmap。

特別大的內(nèi)存分配總是使用 mmap。

具有短生命周期的內(nèi)存分配使用 brk，因?yàn)橛?mmap 映射匿名頁(yè)，當(dāng)發(fā)生缺頁(yè)異常
時(shí)，linux 內(nèi)核為缺頁(yè)分配一個(gè)新物理頁(yè)，并將該物理頁(yè)清 0，一個(gè) mmap 的內(nèi)存塊
需要映射多個(gè)物理頁(yè)，導(dǎo)致多次清 0 操作，很浪費(fèi)系統(tǒng)資源，所以引入了 mmap
分配閾值動(dòng)態(tài)調(diào)整機(jī)制，保證在必要的情況下才使用 mmap 分配內(nèi)存。

盡量只緩存臨時(shí)使用的空閑小內(nèi)存塊，對(duì)大內(nèi)存塊或是長(zhǎng)生命周期的大內(nèi)存塊在釋
放時(shí)都直接歸還給操作系統(tǒng)。

對(duì)空閑的小內(nèi)存塊只會(huì)在 malloc 和 free 的時(shí)候進(jìn)行合并，free 時(shí)空閑內(nèi)存塊可能放入 內(nèi)存池中，不一定歸還給操作系統(tǒng)。

收縮堆的條件是當(dāng)前 free 的塊大小加上前后能合并 chunk 的大小大于 64KB、，并且
堆頂?shù)拇笮∵_(dá)到閾值，才有可能收縮堆，把堆最頂端的空閑內(nèi)存返回給操作系統(tǒng)。

需要保持長(zhǎng)期存儲(chǔ)的程序不適合用 ptmalloc 來(lái)管理內(nèi)存。

為了支持多線程，多個(gè)線程可以從同一個(gè)分配區(qū)（arena）中分配內(nèi)存，ptmalloc
假設(shè)線程 A 釋放掉一塊內(nèi)存后，線程 B 會(huì)申請(qǐng)類(lèi)似大小的內(nèi)存，但是 A 釋放的內(nèi)
存跟 B 需要的內(nèi)存不一定完全相等，可能有一個(gè)小的誤差，就需要不停地對(duì)內(nèi)存塊
作切割和合并，這個(gè)過(guò)程中可能產(chǎn)生內(nèi)存碎片。

---

Arena

在老版本的glibc中使用的內(nèi)存分配器是dlmalloc，其底層對(duì)于多線程的支持并不友好，因?yàn)樗芯€程共享同一個(gè)內(nèi)存管理結(jié)構(gòu)。所以當(dāng)多個(gè)線程并發(fā)執(zhí)行malloc時(shí)，為了保證線程安全，其通過(guò)使用互斥鎖進(jìn)行加鎖，使得只能有一個(gè)線程能夠訪問(wèn)臨界資源，因此在并發(fā)環(huán)境下使用dlmalloc時(shí)會(huì)花費(fèi)大量的時(shí)間在互斥鎖的阻塞等待上，因此整個(gè)應(yīng)用的效率極低。

而在ptmalloc中，為了解決多線程并發(fā)爭(zhēng)搶鎖的問(wèn)題， 其設(shè)定了主分配區(qū)main_arean和非主分配區(qū)non_main_arena。

• 每個(gè)進(jìn)程有一個(gè)主分配區(qū)，以及多個(gè)非主分配區(qū)
• 主分配區(qū)可以使用brk和mmap來(lái)分配空間，而非主分配區(qū)只能使用mmap
• 非主分配區(qū)的數(shù)量只能增加，不能減少
• 主分配區(qū)和非主分配區(qū)使用環(huán)形鏈表進(jìn)行管理，并使用互斥鎖保證線程安全

通過(guò)引入多個(gè)非主分配區(qū)，就可以將線程分發(fā)到不同的分配區(qū)中，將原先多個(gè)線程共享一個(gè)分配區(qū)變?yōu)榱硕鄠€(gè)線程共享多個(gè)分配區(qū)，在一定程度上減輕了并發(fā)的壓力。

---

Chunk

和其他內(nèi)存管理機(jī)制一樣，ptmalloc通過(guò)一個(gè)名為chunk的數(shù)據(jù)結(jié)構(gòu)來(lái)管理和組織內(nèi)存單元。為了節(jié)約內(nèi)存，在使用時(shí)它的結(jié)構(gòu)分為空閑的chuck和使用中的chuck兩個(gè)版本

使用中的chuck:

• chuck指針指向chuck的起始地址，mem指針指向用戶使用的內(nèi)存塊的起始地址，而next chunk則指向下一個(gè)chuck。
• 在第二個(gè)域中，最低的一位p表示前一個(gè)chuck是否空閑，主要用于合并內(nèi)存塊的操作。當(dāng)p=1時(shí)代表著上一次chunk正在使用，此時(shí)prev_size無(wú)效。p=0時(shí)代表前一個(gè)chuck空閑，prev_size有效。在ptmalloc分配第一個(gè)chuck時(shí)，總會(huì)將p置為1，防止程序越界訪問(wèn)。
• M用于表示內(nèi)存所處的區(qū)域，當(dāng)M=1時(shí)為mmap映射區(qū)域分配，M=0為heap區(qū)域分配。
• A用于標(biāo)示分配區(qū)，A=1為非主分配區(qū)分配，A=0為主分配區(qū)分配。
  
  

空閑的chuck:

• 空閑的chuck會(huì)被放到空閑的鏈表bins上，當(dāng)用戶申請(qǐng)內(nèi)存時(shí)，其會(huì)先去bins上查找是否存在合適的內(nèi)存。
• 對(duì)于空閑的chuck，為了方便其在空閑鏈表上快速查找合適大小的chuck，他有指向上一個(gè)和下一個(gè)空閑chuck的指針，同時(shí)還有指向上一個(gè)和下一個(gè)空閑chuck的內(nèi)存大小的指針。

---

Bins

對(duì)于空閑的shunk，ptmalloc采用分箱式內(nèi)存管理，通過(guò)bins來(lái)維護(hù)這些空閑的chunk。ptmalloc一共維護(hù)了128個(gè)bin，同時(shí)每個(gè)bin中又維護(hù)了一個(gè)大小相近的chunk鏈表，如下圖

根據(jù)chunk的大小以及狀態(tài)不同，bins又分為以下四個(gè)種類(lèi)

• fast bins：fast bins是small bins的高速緩沖區(qū)，享有最快的內(nèi)存分配、釋放速度。當(dāng)用戶釋放一塊小于等于MAX_FAST(默認(rèn)為64字節(jié))的chunk時(shí)，會(huì)默認(rèn)將其存放到fast bins中。當(dāng)用戶需要分配小內(nèi)存時(shí)，會(huì)首先查看fast bins中是否存在合適的內(nèi)存塊，如果有則直接返回，如果沒(méi)有才會(huì)去查看small bins上的空閑chunk。同時(shí)，ptmalloc會(huì)遍歷fast bins，查看是否有合適的chunk需要合并，則將其合并后放入unsorted bin中
• unsorted bin：unsorted bin只有一個(gè)，是bins的第一個(gè)位置。當(dāng)用戶釋放的內(nèi)存大雨MAX_FAST或者fast bins合并后的chunk都會(huì)進(jìn)入unsorted bin上，當(dāng)用戶malloc的時(shí)候會(huì)先到unsorted bin上查找是否存在合適的bin，如果沒(méi)有合適的bin，ptmalloc則會(huì)將unsorted bin傷的chunk放入bins上，然后再到bins上查找合適的空閑chunk。
• small bins：用于存放固定大小的chunk，總共有64個(gè)bin，bin的大小從16字節(jié)開(kāi)始，以8字節(jié)不斷遞增。當(dāng)我們需要分配小內(nèi)存塊時(shí)，會(huì)采用精確匹配的方式從small bins中查找到合適的chunk。
• large bins：用于存放大于512字節(jié)的空閑chunk，共有64個(gè)bin，bin按照順序不定長(zhǎng)升序排列，同時(shí)每個(gè)bin中的chunk按照大小降序排列

從上面我們可以得出以下結(jié)論

• fast bins相當(dāng)于small bins的cache，用于提高小內(nèi)存的分配、釋放效率，但也同時(shí)可能加劇內(nèi)存碎片化
• unsorted bin其實(shí)就是最近釋放的內(nèi)存集合，它會(huì)保留最近釋放的chunk，從而消除了尋找合適的bin的時(shí)間開(kāi)銷(xiāo)，提高了內(nèi)存分配和釋放的效率
• small bins和large bins可以合并相鄰的空閑chunk，減輕了內(nèi)存碎片化，但也同時(shí)降低了效率

當(dāng)然，如果在上面的任何一個(gè)bin中都沒(méi)辦法找到合適的內(nèi)存塊，ptmalloc中還預(yù)留了其他的一些后備方式。

• top chunk：在分配區(qū)中最頂部的chunk被稱(chēng)為top chunk，它不屬于任何一個(gè)bin。當(dāng)所有bin中都沒(méi)有合適的內(nèi)存時(shí)，就由它來(lái)響應(yīng)用戶請(qǐng)求。當(dāng)用戶申請(qǐng)的內(nèi)存小于top chunk的內(nèi)存時(shí)，其會(huì)將自己分割為兩部分，一部分返回，另一部分則成為新的top chunk。如果用戶申請(qǐng)的內(nèi)存大于top chunk的內(nèi)存，則top chunk會(huì)根據(jù)分配區(qū)的不同，分別調(diào)用sbrk或者mmap來(lái)進(jìn)行擴(kuò)容。
• last remainder chunk：即最后一次small request中因分割而得到的剩余部分，它有利于改進(jìn)局部性，當(dāng)在small bins中找不到合適的chunk時(shí)，如果last remainded chunk的大小大于所需要的small chunk大小時(shí)，其就會(huì)將用戶需要的那一部分分出去，剩余的部分則成為新的last remainded chunk，因此后續(xù)請(qǐng)求的chunk最終將被分配得彼此接近。
• mmaped chunk：當(dāng)分配的內(nèi)存非常大的時(shí)候（大于128K），此時(shí)就需要通過(guò)mmap來(lái)申請(qǐng)內(nèi)存，通過(guò)mmap申請(qǐng)的內(nèi)存會(huì)被放到mmaped chunk上。同時(shí)，在釋放的時(shí)候會(huì)通過(guò)判斷chunk中的M是否為1來(lái)判斷是否屬于mmaped chunk，如果是則直接將內(nèi)存交還給操作系統(tǒng)

---

內(nèi)存分配、釋放流程

分配流程：

獲取分配區(qū)的鎖

計(jì)算出需要分配內(nèi)存的chunk大小

判斷chunk的大小，如果小于MAX_FAST則到fast_bins上查找，如果小于512字節(jié)，則到small bins上查找

如果還沒(méi)有找到，此時(shí)則進(jìn)入unsorted bin上查找，如果找到合適的chunk并進(jìn)行分配后還有剩余的空間，則根據(jù)其空間大小將其放入small bins或者large bins中。

進(jìn)入large bins中查找，找到合適的bin后反向進(jìn)行遍歷，找到第一個(gè)大小滿足的chunk進(jìn)行分配，如果chunk分配完后還有剩余的空間，則將其放入unsorted bin中。

如果查找了所有的bin都沒(méi)有找到合適的chunk，此時(shí)就需要操作top chunk來(lái)進(jìn)行分配，如果滿足大小小于top chunk，則切割top chunk來(lái)進(jìn)行分配。如果大小大于top chunk，則此時(shí)會(huì)申請(qǐng)內(nèi)存來(lái)滿足分配需求。

釋放流程：

獲取分配區(qū)的鎖

判斷free的參數(shù)是否為空節(jié)點(diǎn)，如果是則什么都不做

判斷當(dāng)前chunk是否是mmap映射出的大塊內(nèi)存（M=1），如果是的話直接munmap釋放掉

判斷當(dāng)前chunk是否和top chunk連續(xù)，如果連續(xù)則直接和top chunk合并

判斷chunk大小是否大于MAX_FAST，如果大于則放入unsorted bin中，并檢查是否能夠進(jìn)行合并，如果不能合并則直接free，如果能則進(jìn)入步驟8

如果chunk大小小于MAX_FAST，則放入fast bins中，并判斷是否有合并的情況，如果沒(méi)有合并則free，如果有則進(jìn)入下一步驟

在fast bin中，如果當(dāng)前當(dāng)前chunk能夠進(jìn)行合并，則將合并后的chunk放入unsorted bin中。

判斷top chunk的大小是否大于mmap收縮閾值，如果滿足則試圖歸還多出的那一部分給操作系統(tǒng)

---

總結(jié)

從上面的內(nèi)容我們可以看出，ptmalloc雖然能夠很好的進(jìn)行內(nèi)存管理，但是仍然存在著一系列的小問(wèn)題，如：

• 由于ptmalloc收縮內(nèi)存是從top chunk開(kāi)始，如果與top chunk相鄰的chunk不能夠釋放，則top chunk以下的chunk都無(wú)法釋放（即使后分配的內(nèi)存先釋放，也無(wú)法及時(shí)歸還給系統(tǒng)）
• 每個(gè)chunk至少為8字節(jié)（可能導(dǎo)致內(nèi)存內(nèi)碎片）
• 雖然采用了主分配區(qū)+非主分配區(qū)的策略來(lái)優(yōu)化多線程環(huán)境下的并發(fā)問(wèn)題，但是在內(nèi)存分配和釋放的時(shí)候仍會(huì)首先進(jìn)行加鎖（影響性能）
• 由于采用了非主分配區(qū)，導(dǎo)致內(nèi)存不能在不同分配區(qū)間移動(dòng)，內(nèi)存使用不均衡（內(nèi)存浪費(fèi)）
• 不定期分配長(zhǎng)生命周期的內(nèi)存（不利于回收，容易導(dǎo)致內(nèi)存碎片）

所以后來(lái)各大廠商為了能夠提升效率，開(kāi)發(fā)出了如tcmalloc、jemalloc等內(nèi)存分配器，但作為linux默認(rèn)內(nèi)存管理器的ptmalloc，以其穩(wěn)定性始終占據(jù)著一席之地。

總結(jié)

以上是生活随笔為你收集整理的Linux glibc内存管理：用户态内存分配器——ptmalloc实现原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。