文章目錄
- ptmalloc
- 設計假設
- Arena
- Chunk
- Bins
- 記憶體配置設定、釋放流程
- 總結
C++ STL : SGI-STL空間配置器源碼剖析
Linux 記憶體管理 | 實體記憶體管理：實體記憶體、記憶體碎片、夥伴系統、slab配置設定器
Linux 記憶體管理 | 虛拟記憶體管理：虛拟記憶體空間、虛拟記憶體配置設定
在之前的幾篇部落格中，我曾經介紹過STL空間配置器、BuddySystem、Slab配置設定器等記憶體管理機制，也曾經簡單的提及過linux使用者态記憶體配置設定的政策，這一次就來深入講一講在使用者态進行記憶體配置設定時，到底做了什麼。
ptmalloc
在Linux中，當我們申請的記憶體小于
128K
時，
malloc
會使用
sbrk
或者
brk
在堆區配置設定記憶體。而當我們申請大于128K的大塊空間時，會使用
mmap
在映射區進行配置設定。
但是由于上述的
brk/sbrk/mmap
都屬于系統調用，是以當我們每次調用它們時，就會從使用者态切換至核心态，在核心态完成記憶體配置設定後再傳回使用者态。
倘若每次申請記憶體都要因為系統調用而産生大量的CPU開銷，那麼性能會大打折扣。并且從上面的圖我們也可以看出來，堆是從低位址往高位址增長，如果低位址的記憶體沒有被釋放，則高位址的記憶體就不能被回收，就會産生記憶體碎片的問題。
那麼Linux中的malloc是如何實作解決這個問題的呢？
這就要提到大名鼎鼎的
ptmalloc
了，
ptmalloc
是glibc中預設的記憶體管理器。其底層采取了分箱式記憶體管理機制，也就是實作了一個類似哈希桶結構的記憶體池，當我們通過
malloc
和
free
申請和釋放記憶體的時候，
ptmalloc
就會代替我們将這些記憶體進行管理，通過一系列的記憶體合并、申請政策，來讓使用者申請和釋放記憶體的時候更加的高效且安全。
下面就來詳細的介紹一下
ptmalloc
的工作原理
設計假設
ptmalloc
在設計時集合了高效率、高空間使用率、高可用等目标，是以有了如下幾種設計假設
- 具有長生命周期的大記憶體配置設定使用
mmap
- 特别大的記憶體配置設定總是使用
mmap
- 具有短生命周期的記憶體配置設定使用
brk
mmap
映射匿名頁，當發生缺頁異常
時，linux 核心為缺頁配置設定一個新實體頁，并将該實體頁清 0，一個
mmap
的記憶體塊
需要映射多個實體頁，導緻多次清 0 操作，很浪費系統資源，是以引入了
mmap
mmap
-
盡量隻緩存臨時使用的空閑小記憶體塊，對大記憶體塊或是長生命周期的大記憶體塊在釋
放時都直接歸還給作業系統。
- 對空閑的小記憶體塊隻會在
malloc
free
free
-
收縮堆的條件是目前 free 的塊大小加上前後能合并 chunk 的大小大于 64KB、，并且
堆頂的大小達到門檻值，才有可能收縮堆，把堆最頂端的空閑記憶體傳回給作業系統。
- 需要保持長期存儲的程式不适合用
ptmalloc
- 為了支援多線程，多個線程可以從同一個配置設定區（arena）中配置設定記憶體，
ptmalloc
假設線程 A 釋放掉一塊記憶體後，線程 B 會申請類似大小的記憶體，但是 A 釋放的内
存跟 B 需要的記憶體不一定完全相等，可能有一個小的誤差，就需要不停地對記憶體塊
作切割和合并，這個過程中可能産生記憶體碎片。
Arena
在老版本的glibc中使用的記憶體配置設定器是
dlmalloc
，其底層對于多線程的支援并不友好，因為所有線程共享同一個記憶體管理結構。是以當多個線程并發執行
malloc
時，為了保證線程安全，其通過使用互斥鎖進行加鎖，使得隻能有一個線程能夠通路臨界資源，是以在并發環境下使用
dlmalloc
時會花費大量的時間在互斥鎖的阻塞等待上，是以整個應用的效率極低。
而在
ptmalloc
中，為了解決多線程并發争搶鎖的問題， 其設定了主配置設定區
main_arean
和非主配置設定區
non_main_arena
。
- 每個程序有一個主配置設定區，以及多個非主配置設定區
- 主配置設定區可以使用
brk
mmap
mmap
- 非主配置設定區的數量隻能增加，不能減少
- 主配置設定區和非主配置設定區使用環形連結清單進行管理，并使用互斥鎖保證線程安全
通過引入多個非主配置設定區，就可以将線程分發到不同的配置設定區中，将原先多個線程共享一個配置設定區變為了多個線程共享多個配置設定區，在一定程度上減輕了并發的壓力。
Chunk
和其他記憶體管理機制一樣，
ptmalloc
通過一個名為
chunk
的資料結構來管理群組織記憶體單元。為了節約記憶體，在使用時它的結構分為空閑的chuck和使用中的chuck兩個版本
使用中的chuck:
- chuck指針指向chuck的起始位址，mem指針指向使用者使用的記憶體塊的起始位址，而next chunk則指向下一個chuck。
- 在第二個域中，最低的一位p表示前一個chuck是否空閑，主要用于合并記憶體塊的操作。當p=1時代表着上一次chunk正在使用，此時prev_size無效。p=0時代表前一個chuck空閑，prev_size有效。在ptmalloc配置設定第一個chuck時，總會将p置為1，防止程式越界通路。
- M用于表示記憶體所處的區域，當M=1時為mmap映射區域配置設定，M=0為heap區域配置設定。
- A用于标示配置設定區，A=1為非主配置設定區配置設定，A=0為主配置設定區配置設定。
空閑的chuck:
- 空閑的chuck會被放到空閑的連結清單bins上，當使用者申請記憶體時，其會先去bins上查找是否存在合适的記憶體。
- 對于空閑的chuck，為了友善其在空閑連結清單上快速查找合适大小的chuck，他有指向上一個和下一個空閑chuck的指針，同時還有指向上一個和下一個空閑chuck的記憶體大小的指針。
Bins
對于空閑的shunk，ptmalloc采用分箱式記憶體管理，通過bins來維護這些空閑的chunk。ptmalloc一共維護了128個bin，同時每個bin中又維護了一個大小相近的chunk連結清單，如下圖
根據chunk的大小以及狀态不同，bins又分為以下四個種類
- fast bins：fast bins是small bins的高速緩沖區，享有最快的記憶體配置設定、釋放速度。當使用者釋放一塊小于等于MAX_FAST(預設為64位元組)的chunk時，會預設将其存放到fast bins中。當使用者需要配置設定小記憶體時，會首先檢視fast bins中是否存在合适的記憶體塊，如果有則直接傳回，如果沒有才會去檢視small bins上的空閑chunk。同時，ptmalloc會周遊fast bins，檢視是否有合适的chunk需要合并，則将其合并後放入unsorted bin中
- unsorted bin：unsorted bin隻有一個，是bins的第一個位置。當使用者釋放的記憶體大雨MAX_FAST或者fast bins合并後的chunk都會進入unsorted bin上，當使用者malloc的時候會先到unsorted bin上查找是否存在合适的bin，如果沒有合适的bin，ptmalloc則會将unsorted bin傷的chunk放入bins上，然後再到bins上查找合适的空閑chunk。
- small bins：用于存放固定大小的chunk，總共有64個bin，bin的大小從16位元組開始，以8位元組不斷遞增。當我們需要配置設定小記憶體塊時，會采用精确比對的方式從small bins中查找到合适的chunk。
- large bins：用于存放大于512位元組的空閑chunk，共有64個bin，bin按照順序不定長升序排列，同時每個bin中的chunk按照大小降序排列
從上面我們可以得出以下結論
- fast bins相當于small bins的cache，用于提高小記憶體的配置設定、釋放效率，但也同時可能加劇記憶體碎片化
- unsorted bin其實就是最近釋放的記憶體集合，它會保留最近釋放的chunk，進而消除了尋找合适的bin的時間開銷，提高了記憶體配置設定和釋放的效率
- small bins和large bins可以合并相鄰的空閑chunk，減輕了記憶體碎片化，但也同時降低了效率
當然，如果在上面的任何一個bin中都沒辦法找到合适的記憶體塊，ptmalloc中還預留了其他的一些後備方式。
- top chunk：在配置設定區中最頂部的chunk被稱為top chunk，它不屬于任何一個bin。當所有bin中都沒有合适的記憶體時，就由它來響應使用者請求。當使用者申請的記憶體小于top chunk的記憶體時，其會将自己分割為兩部分，一部分傳回，另一部分則成為新的top chunk。如果使用者申請的記憶體大于top chunk的記憶體，則top chunk會根據配置設定區的不同，分别調用
sbrk
mmap
- last remainder chunk：即最後一次small request中因分割而得到的剩餘部分，它有利于改進局部性，當在small bins中找不到合适的chunk時，如果last remainded chunk的大小大于所需要的small chunk大小時，其就會将使用者需要的那一部分分出去，剩餘的部分則成為新的last remainded chunk，是以後續請求的chunk最終将被配置設定得彼此接近。
- mmaped chunk：當配置設定的記憶體非常大的時候（大于128K），此時就需要通過
mmap
記憶體配置設定、釋放流程
配置設定流程：
- 擷取配置設定區的鎖
- 計算出需要配置設定記憶體的chunk大小
- 判斷chunk的大小，如果小于
MAX_FAST
- 如果還沒有找到，此時則進入unsorted bin上查找，如果找到合适的chunk并進行配置設定後還有剩餘的空間，則根據其空間大小将其放入small bins或者large bins中。
- 進入large bins中查找，找到合适的bin後反向進行周遊，找到第一個大小滿足的chunk進行配置設定，如果chunk配置設定完後還有剩餘的空間，則将其放入unsorted bin中。
- 如果查找了所有的bin都沒有找到合适的chunk，此時就需要操作top chunk來進行配置設定，如果滿足大小小于top chunk，則切割top chunk來進行配置設定。如果大小大于top chunk，則此時會申請記憶體來滿足配置設定需求。
釋放流程：
- 擷取配置設定區的鎖
- 判斷free的參數是否為空節點，如果是則什麼都不做
- 判斷目前chunk是否是
mmap
munmap
- 判斷目前chunk是否和top chunk連續，如果連續則直接和top chunk合并
- 判斷chunk大小是否大于
MAX_FAST
free
- 如果chunk大小小于
MAX_FAST
- 在fast bin中，如果目前目前chunk能夠進行合并，則将合并後的chunk放入unsorted bin中。
- 判斷top chunk的大小是否大于
mmap
總結
從上面的内容我們可以看出，ptmalloc雖然能夠很好的進行記憶體管理，但是仍然存在着一系列的小問題，如：
- 由于ptmalloc收縮記憶體是從top chunk開始，如果與top chunk相鄰的chunk不能夠釋放，則top chunk以下的chunk都無法釋放（即使後配置設定的記憶體先釋放，也無法及時歸還給系統）
- 每個chunk至少為8位元組（可能導緻記憶體内碎片）
- 雖然采用了主配置設定區+非主配置設定區的政策來優化多線程環境下的并發問題，但是在記憶體配置設定和釋放的時候仍會首先進行加鎖（影響性能）
- 由于采用了非主配置設定區，導緻記憶體不能在不同配置設定區間移動，記憶體使用不均衡（記憶體浪費）
- 不定期配置設定長生命周期的記憶體（不利于回收，容易導緻記憶體碎片）
是以後來各大廠商為了能夠提升效率，開發出了如
tcmalloc
、
jemalloc
等記憶體配置設定器，但作為linux預設記憶體管理器的
ptmalloc
，以其穩定性始終占據着一席之地。