ptmalloc内存分配和回收详解（文字版）
ptmalloc內存分配和回收詳解（文字版）
進程默認內存布局（x86）
從進程的內存布局可知，.bss段之上的這塊分配給用戶程序的空間被稱之為heap，start_brk指向heap的開始，而brk指向heap的頂部。可以使用系統調用brk()和sbrk()來增加表示heap頂部的brk值，從而線性的增加分配給用戶的heap空間。在使用malloc之前，brk的值等于start_brk，也就是說，heap大小為0。
ptmalloc在開始時，若請求的空間小于mmap分配閾值（mmap threshold， 默認值為128KB）時，主分配區會調用sbrk()增加一塊大小為（128KB + chunk_size）align 4KB的空間作為heap，非主分配區會調用mmap映射一塊大小為HEAP_MAX_SIZE（32位1MB，64位64MB）的空間作為sub-heap。這就是ptmalloc所維護的分配空間。
ptmalloc內存管理設計假設
1、具有長生命周期的大內存分配使用mmap。
2、特別大的內存分配總是使用mmap。
3、具有短生命周期的內存分配使用brk，因為用mmap映射匿名頁，當發生缺頁異常時，linux內核為缺頁分配一個新的物理頁，導致多次清零操作，很浪費系統資源，所以引入了mmap分配閾值動態調整機制，保證在必要的情況下才使用mmap分配內存。
4、盡量只緩存臨時使用的空閑小內存塊，對大內存快或是長生命周期的大內存塊在釋放時都直接歸還給操作系統。
5、對空閑的小內存塊只會在malloc和free的時候進行合并，free時空閑內存塊可能放入bin中，不一定歸還給操作系統。
6、收縮堆的條件是當前free的塊大小加上前后能合并chunk的大小大于64KB，并且堆頂的大小達到閾值，才有可能收縮堆，把堆最頂端的空閑內存返回給操作系統。
7、需要長期存儲的程序不適合用ptmalloc來管理內存。
8、為了支持多線程，多個線程可以從同一個分配區中分配內存，ptmalloc假設線程A釋放掉一塊內存后，線程B會申請類似大小的內存，但是A釋放的內存跟B需要的內存不一定完全相等，可能有稍許誤差，就需要不停的對內存塊進行切割和合并，這個過程可能產生內存碎片。
內存分配
1、獲取分配區的鎖，為了防止多個線程同時訪問同一個分配區，在進行分配之前需要取得分配區域的鎖。先查看線程私有實例中是否已經存在一個分配區，如果存在嘗試對該分配區加鎖，如果加鎖成功，使用該分配區分配內存，否則該線程搜索分配區循環鏈表試圖獲得一個空閑（沒有加鎖）的分配區。如果所有的分配區都已經加鎖，那么ptmalloc會開辟一個新的分配區，把該分配區加入到全局分配區循環鏈表和線程的私有實例中并加鎖，然后使用該分配區進行分配操作。開辟出來的新分配區一定為非主分配區，因為主分配區是從父進程那里繼承來的。開辟非主分配區時會調用mmap()創建一個sub-heap，并設置好top chunk；
每一個進程只有一個主分配區(main_arena)和若干非主分配區(non_main_arena)，各arena通過一個循環鏈表來管理，通過互斥鎖(mutex)使線程對于該分配區的訪問互斥。
通過chunk倒數第三個標志位區分是否為非主分配區。
2、將用戶的請求大小轉換為實際需要分配的chunk空間大小
加上chunk頭部，并進行字節對齊，默認8字節對齊。
事實上，由于chunk的空間復用，例如32位系統，實際的chunk大小=（用戶請求大小 + 8 - 4） align to 8B
3、判斷所需分配chunk的大小是否滿足<=max_fast（32位默認為64B），如果是，則轉下一步，否則跳到第五步。
4、首先嘗試在fast bin中取一個所需大小的chunk分配給用戶。如果可以找到，則分配結束，否則轉下一步。
fast bins的分配遵循后進先出（LIFO）原則，類似于棧。
fast bins包含10個bin，大小從16B到88B，相鄰bin相差8B，其中只有前七個作為空閑chunk鏈使用。
fast bins中的chunk不會修改最后一個標志位，因此fast bin中的chunk不會合并。
5、判斷所需大小是否處在small bin中，即判斷chunk_size < 512B是否成立。如果chunk大小處在small bins中，則轉下一步，否則轉到第6步。
ptmalloc維護了一個bin數組，共有128項，其中序號為2-63的62項為small bin。
small bin中每個bin中的塊大小相同，相鄰bin相差8B，最小的16B，最大的504B，每個bin中都是雙向循環鏈表。
分配時按照“small-first， best-fit”原則。
6、根據所需分配的chunk的大小，找到具體所在的某個small bin，從該bin的尾部摘取一個恰好滿足大小的chunk。若成功，則分配結束，否則轉下一步。
7、到了這一步，說明需要分配的是一塊大的內存，或者small bins中找不到合適的chunk。于是，ptmalloc首先會遍歷fast bins中的chunk，將相鄰的chunk進行合并，并鏈接到unsorted bin中，然后遍歷unsorted bin中的chunk，如果unsorted bin只有一個chunk，并且這個chunk在上次分配時被使用過，并且所需分配的大小屬于small bins，并且chunk的大小大于等于需要分配的大小，這種情況下就直接將該chunk進行切割，分配結束，否則將根據chunk的空間大小將其放入small bins或是large bins中，遍歷完成后，轉入下一步。
ptmalloc中的bins數組第一個就是unsorted bin，序號為1。
雙向鏈表管理空閑chunk，不排序，當釋放chunk時，大小大于max_fast的首先鏈入unsorted bin中。
可看作是small bins和large bins的cache。
8、到了這一步，說明需要分配的是一塊大的內存，或者small bins和unsorted bin中都找不到合適的chunk，并且fast bins和unsorted bin中所有的chunk都清除干凈了。從large bins按照“small-first， best-fit”原則，找到一個合適的chunk，從中劃分一塊所需大小的chunk，并將剩下的部分鏈接回bins中。若操作成功，則分配結束，否則轉下一步。
bins數組序號為64-126的63個bin為large bins。
large bins中的chunk鏈大小并不是一個固定公差的等差數列，而是分成6組bins，每組bins是一個固定的等差數列，每組的bin數目依次是32、16、8、4、2、1，公差依次是64B、512B、4096B、32768B、262144B等。
9、如果搜索fast bins和bins都沒有找到合適的chunk，那么就需要操作top chunk來進行分配了。判斷top chunk大小是否滿足所需chunk的大小，如果是，則從top chunk中分出一塊來，否則轉下一步。
chunk中有三種并非按照bins結構存儲，分別是top chunk、mmaped chunk、last remainder。
top chunk：對于非主分配區會預先分配一塊較大的空閑內存模擬sub-heap，通過管理sub-heap來響應用戶的需求，因為內存是按地址從高到底進行分配的，在空閑區的最高處，必然存在一塊空閑chunk，叫做top chunk；由于主分配區是唯一能夠映射到進程heap區域的分配區，它可以通過sbrk()來增大或是收縮進程heap的大小，ptmalloc在開始時會預先分配一塊較大的空閑內存（heap）。
mmaped chunk： 當需要分配的chunk足夠大，而且fast bins和bins都不能滿足要求，甚至top chunk本身也不能滿足要求時，ptmalloc會使用mmap來直接使用內存映射來將頁映射到進程空間。這樣分配的chunk在被free時，將直接解除映射，于是就將內存歸還給了操作系統。
last remainder： 不存在于任何bins中，當需要分配一個small chunk時，但在small bins中找不到合適的chunk，如果last remainder chunk的大小大于所需的small chunk大小，last remainder chunk被分裂為兩個，其中一個chunk返回給用戶，另一個變成新的last remainder chunk。
10、到了這一步，說明top chunk也不能滿足分配要求，所以，于是就有了兩個選擇：如果是主分配區，調用sbrk()，增加top chunk大小；如果是非主分配區，調用mmap來分配一個新的sub-heap，增加top chunk大小；或者使用mmap來直接分配。在這里，需要依靠chunk的大小來決定到底使用哪種方法。判斷所需分配的chunk大小是否大于等于mmap分配閾值，如果是的話，則轉下一步，調用mmap分配，否則跳到第12步，增加top chunk的大小。
對于非主分配區，當bins和fast bins都不能滿足分配的需要，ptmalloc會設法在top chunk分出一塊內存給用戶，如果top chunk本身不夠大，分配程序會重新分配一個sub-heap，并將top chunk遷移到新的sub-heap上，新的sub-heap與已有的sub-heap用單鏈表連接起來，然后在新的top chunk上分配。
11、使用mmap系統調用為程序的內存空間映射一塊chunk_size align 4KB大小的空間，然后將內存指針返回給用戶。
12、判斷是否為第一次調用malloc，若是主分配區，則需要進行一次初始化工作，分配一塊大小為（chunk_size + 128KB）align 4KB大小的空間作為初始的heap。若已經初始化過了，主分配區則調用sbrk()增加heap空間，非主分配區則在top chunk中切出一個chunk，使之滿足分配需求，并將內存指針返回給用戶。
內存回收
1、free()函數同樣首先需要獲取分配區的鎖，來保證線程安全。
2、判斷傳入的指針是否為0，若為0，則什么都不做，直接return，否則轉下一步。
3、判斷所需釋放的chunk是否為mmaped chunk，如果是，則調用munmap()釋放mmaped chunk，解除內存空間映射，該空間不再有效。如果開啟了mmap分配閾值的動態調整機制，并且當前回收的chunk大小大于mmap分配閾值，將mmap分配閾值設置為該chunk的大小，將mmap收縮閾值設定為mmap分配閾值的2倍，釋放完成。否則下一步。
4、判斷chunk的大小和所處的位置，若chunk_size<=max_fast，并且chunk不位于heap頂部，也就是說并不與top chunk相鄰，則轉到下一步，否則跳到第6步。（因為與top chunk相鄰的小chunk也和top chunk進行合并，所以這里不僅需要判斷大小，還需要判斷相鄰情況）
5、將chunk放到fast bins中，chunk放入到fast bins中時，并不修改該chunk使用狀態位P。也不與相鄰的chunk進行合并。只是放進去，釋放結束，返回。
6、判斷前一個chunk是否處在使用中，如果前一個塊也是空閑塊，則合并，并轉下一步。
7、判斷當前釋放塊的下一個塊是否為top chunk，如果是，轉第9步，否則轉下一步。
8、判斷下一個chunk是否處在使用中，如果下一個chunk也是空閑的，則合并，并將合并后的chunk放到unsorted bin中。注意，這里在合并的過程中，要更新chunk的大小，以反映合并后的chunk的大小，并轉到10步。
9、如果執行到這一步，說明釋放了一個與top chunk相鄰的chunk。則無論它有多大，都將它與top chunk合并，并更新top chunk的大小等信息，轉下一步。
10、判斷合并后的chunk的大小是否大小FASTBIN_CONSOLIDATION_THRESHOLD（默認64KB），如果是的話，則會觸發進行fast bins的合并操作，fast bins中的chunk將被遍歷，并與相鄰的空間chunk進行合并，合并后的chunk會被放到unsorted bin中。fast bins將變空，操作完成轉下一步。
11、判斷top chunk的大小是否大于mmap的收縮閾值（默認為128KB），如果是的話，對于主分配區，則會試圖歸還top chunk中的一部分給操作系統。但是最先分配的128KB是不會歸還的，ptmalloc會一直管理這部分內存，用于響應用戶的分配請求；如果為非主分配區，會進行sub-heap收縮，將top chunk的一部分返回給操作系統，如果top chunk為整個sub-heap，會把整個sub-heap還回給操作系統。做完這一步后，釋放結束，返回。可以看出，收縮堆的條件是當前free的chunk大小加上前后能合并chunk的大小大于64KB，并且要top chunk的大小要達到mmap收縮閾值，才有可能收縮堆。
轉載于:https://www.cnblogs.com/clingyu/p/8620764.html
總結
以上是生活随笔為你收集整理的ptmalloc内存分配和回收详解（文字版）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： codefroces 297E Myst
- 下一篇： 练习 3.16