談談malloc

? ? 關注、星標公眾號，直達精彩內容
來源：網絡素材

面試的時候經常會被問到 malloc 的實現。從操作系統層面來說，malloc 確實是考察面試者對操作系統底層的存儲管理理解的一個很好的方式，涉及到虛擬內存、分頁/分段等。下面逐個細說。
1. 虛擬內存
首先需要知道的是程序運行起來的話需要被加載的物理內存中，具體到計算機硬件就是內存條。操作系統啟動的時候先把自己加載到物理內存的固定位置（一般為底部），物理內存的其他位置就用來運行用戶程序。程序就是一堆指令，程序運行可以簡單抽象為把指令加載到內存中，然后 CPU 將指令從內存載入執行。
1. 為什么需要虛擬內存？
CPU 對內存的尋址最簡單的方式就是直接使用物理內存地址，這種方式一般叫做物理尋址。早期的 PC 使用物理尋址，而且像數字信號處理器、嵌入式微控制器也使用物理尋址。物理尋址的好處是簡單，壞處也有很多，比如：
不安全：操作系統的地址直接暴露給用戶程序，用戶程序可以破壞操作系統。這種解決方案是采用特殊的硬件保護。
同時運行多個程序比較困難：多個用戶程序如果都直接引用物理地址，很容易互相干擾。那么是不是可以通過不斷交換物理內存和磁盤來保證物理內存某一時間自由一個程序在運行呢？當時是可以的，但是這引入很多不必要和復雜的工作。
用戶程序大小受限：受制于物理內存大小。我們現在的錯覺是應用程序大小都小于物理內存，這主要是因為現在 PC 的物理內存都比較大。實際上只有 1G 物理內存的 PC 是可以運行 2G 的應用程序的。

綜合上面各種缺點，虛擬內存出現了。
2. 虛擬內存概覽
虛擬內存的基本思想是：每個程序擁有獨立的地址空間（也就是虛擬內存地址，或者稱作虛擬地址），互不干擾。地址空間被分割成多個塊，每一塊稱作一頁（page），每一頁有連續的地址范圍。虛擬地址的頁被映射到物理內存（通過 MMU，Memory Management Unit），但是并不是所有的頁都必須在內存中才能運行程序。當程序引用到一部分在物理內存中的地址空間時，由硬件立刻執行必要的映射。當程序引用到一部分不在物理內存中的地址空間時，由操作系統負責將確實的部分裝入物理內存。虛擬地址尋址（也叫做虛擬尋址）的示意圖如下。


3.虛擬內存實現
1.虛擬內存大小
一般是和 CPU 字長相關，比如 32 位對應的虛擬地址空間大小為：0 ~ 2^31。
2. MMU
CPU 將虛擬地址發送給 MMU，然后 MMU 將虛擬地址翻譯成物理地址，再尋址物理內存。那么虛擬地址和物理地址具體是怎么映射的呢？完成映射還需要另一個重要的數據結構的參與：頁表（page table）。頁表完成虛擬地址和物理地址的映射，MMU 每次翻譯的時候都需要讀取頁表。頁表的一種簡單表示如下。


這里頁大小為 p 位。虛擬內存的頁和物理內存的頁大小一樣。虛擬地址的高 n-p 位，又叫做虛擬頁號（Virtual Page Number, VPN），用來索引物理頁號（Physical Page Number，PPN），最后將 PPN 和低 p 位組合在一起就得到了物理地址。
3. 頁表的兩個問題
前面說到用 VPN 來做頁表索引，也就是說頁表的大小為虛擬地址位數 / 頁的大小。比如 32 位機器，頁大小一般為 4K ，則頁表項有 2^32 / 2^12 = 2^20 條目。如果機器字長 64 位，頁表項就更多了。那么怎么解決呢？一般有兩種方法：
倒排頁表。物理頁號做索引，映射到多個虛擬地址。通過虛擬地址查找的時候就需要通過虛擬地址的中間幾位來做索引了。
多級頁表。以兩級頁表為例。一級頁表中的每個 PTE （page table entry）映射虛擬地址空間的一個 4MB 的片，每一片由1024 個連續的頁面組成。一級 PTE 指向二級頁表的基址。這樣 32 位地址空間使用 1024 個一級 PTE 就可以表示。需要的二級頁表總條目還是 2^32 / 2^12 = 2^20 個。這里的關鍵在于如果一級 PTE i 中的頁面都未被分配，一級 PTE 就為空。多級頁面的一個簡單示意圖如下。


多級頁表減少內存占用的關鍵在于：
如果一級頁表中的一個 PTE 為空，那么相應的二級頁表就根本不會存在。這是一種巨大的潛在節約。
只有一級頁表才需要常駐內存。虛擬內存系統可以在需要時創建、頁面調入或者調出二級頁表，從而減輕內存的壓力。
第二個問題是頁表是在內存中，而 MMU 位于 CPU 芯片中，這樣每次地址翻譯可能都需要先訪問一次內存中的頁表（CPU L1,L2,L3 Cache Miss 的時候訪問內存），效率非常低下。對應的解決方案是引入頁表的高速緩存：TLB（Translation Lookaside Buffer）。加入 TLB，整個虛擬地址翻譯的過程如下兩圖所示。



關于虛擬內存還有一些內容比如 page fault 處理，這里就不再贅述了。
2. 分段
1. 分段概述
前面介紹了分頁內存管理，可以說通過多級頁表，TLB 等，分頁內存管理方法已經相當不錯了。那么分頁有什么缺點呢？
共享困難：通過共享頁面來實現共享當然是可以的。這里的問題在于我們要保證頁面上只包含可以共享的內容并不是一件容易的事兒，因為進程空間是直接映射到頁面上的。這樣一個頁面上很可能包含不能共享的內容（比如既包含代碼又包含數據，代碼可以共享，而數據不能共享）。早期的 PDP-11 實現的一種解決方法是為指令和數據設置分離的地址空間，分別稱為 I 空間和 D 空間（其實這已經和分段很像了）。
程序地址空間受限于虛擬地址：我們將程序全部映射到一個統一的虛擬地址的問題在于不好擴張。不如我們程序的地址按先代碼放在一起，然后把數據放在一起，然后再放 XXX，這樣其中某一部分的空間擴張起來都會影響到相鄰的空間，非常不方便。
上面的問題一個比較直觀的解決方法是提供多個獨立的地址空間，也就是段（segment）。每個段的長度視具體的段不同而不同，而且是可以在運行期動態改變的。因為每個段都構成了一個獨立的地址空間，所以它們可以獨立的增長或者減小而不會影響到其他的段。如果一個段比較大，把它整個保存到內存中可能很不方便甚至是不可能的，因此可以對段采用分頁管理，只有那些真正需要的頁面才會被調入內存。


采用分段和分頁結合的方式管理內存，一個地址由兩個部分組成：段和段內地址。段內地址又進一步分為頁號和頁偏移。在進行內存訪問時，過程如下：
根據段號找到段描述符（存放段基址）。
檢查該段的頁表是否在內存中。如果在，則找到它的位置，如果不在，則產生段錯誤。
檢查所請求的虛擬頁面的頁表項，如果該頁面不在內存中則產生缺頁中斷，如果在內存中就從頁表項中取出這個頁面在內存中的起始地址。
將頁面起始地址和偏移量進行拼接得到物理地址，然后完成讀寫。
2. 進程的段
每個 Linux 程序都有一個運行時內存映像，也就是各個段的布局，簡單如下圖所示。


注意上圖只是一個相對位置圖，實際上這些段并不是相鄰的。主要的段包括只讀代碼段、讀寫段、運行時堆、用戶棧。在分配棧、堆段運行時地址的時候，鏈接器會使用空間地址空間布局隨機化（ASLR），但是相對位置不會變。上圖中 .data 等是對應進程中的不同數據的 section ，或者叫做節。簡介如下。
.text: 已編譯程序的機器代碼。
.rodata: 只讀數據。
.data: 已初始化的全局和靜態變量。局部變量保存在棧上。
.bss: 未初始化的全局和靜態變量，以及所有被初始化為 0 的全局或者靜態變量。在目標文件中這個節不占據實際的空間，它僅僅是一個占位符。
3. malloc 實現
1. 堆內存管理
我們常說的 malloc 函數是 glibc 提供的庫函數。glibc 的內存管理使用的方法是 ptmalloc，除此之后還有很多其他內存管理方案，比如 tcmalloc （golang 使用的就是 tcmalloc）。
ptmalloc 對于申請內存小于 128KB 時，分配是在堆段，使用系統調用 brk() 或者 sbrk()。如果大于 128 KB 的話，分配在映射區，使用系統調用 mmap()。
2. brk, sbrk
在堆段申請的話，使用系統調用 brk 或者 sbrk。
int brk(const void *addr);
void *sbrk(intptr_t incr);
brk 將 brk 指針放置到指定地址處，成功返回 0，否則返回 -1。sbrk 將 brk 指針向后移動指定字節，返回依賴于系統實現，或者返回移動前的 brk 位置，或者返回移動后的 brk 位置。下面使用 sbrk 實現一個巨簡單的 malloc。
void *malloc(size_t size) {

    void *p = sbrk(0);

    void *request = sbrk(size);

    if (request == (void*) -1) {

        return NULL; // sbrk failed.

    } else {

        assert(p == request); // Not thread safe.

        return p;

    }

}
3. mmap
linux 系統調用 mmap 將一個文件或者其它對象映射進內存。
#include 

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
mmap 的 flags 可選多種參數，當選擇 MAP_ANONYMOUS 時，不需要傳入文件描述符，malloc 使用的就是 MAP_ANONYMOUS 模式。mmap 申請的內存在操作系統的映射區。比如 32 位系統，映射區從 3G 虛擬地址粗向下生長，但是因為程序的其他段也會占用空間（比如代碼段必須以特定的地址開始），所以并不能申請 3G 的大小。
4. malloc 和物理內存有關系嗎？
可以說沒關系，malloc 申請的地址是線性地址，申請的時候并沒有進行映射。訪問到的時候觸發缺頁異常，這個時候才會進行物理地址映射。
5. ptmalloc
Malloc實現原理：
因為brk、sbrk、mmap都屬于系統調用，若每次申請內存，都調用這三個，那么每次都會產生系統調用，影響性能；其次，這樣申請的內存容易產生碎片，因為堆是從低地址到高地址，如果高地址的內存沒有被釋放，低地址的內存就不能被回收。
所以malloc采用的是內存池的管理方式（ptmalloc），Ptmalloc 采用邊界標記法將內存劃分成很多塊，從而對內存的分配與回收進行管理。為了內存分配函數malloc的高效性，ptmalloc會預先向操作系統申請一塊內存供用戶使用，當我們申請和釋放內存的時候，ptmalloc會將這些內存管理起來，并通過一些策略來判斷是否將其回收給操作系統。這樣做的最大好處就是，使用戶申請和釋放內存的時候更加高效，避免產生過多的內存碎片。
chunk 內存塊的基本組織單元
在 ptmalloc 的實現源碼中定義結構體 malloc_chunk 來描述這些塊。malloc_chunk 定義如下：
1.struct malloc_chunk {  
2.  INTERNAL_SIZE_T      prev_size;    /* Size of previous chunk (if free).  */  
3.  INTERNAL_SIZE_T      size;         /* Size in bytes, including overhead. */  
4.  
5.  struct malloc_chunk* fd;           /* double links -- used only if free. */  
6.  struct malloc_chunk* bk;  
7.  
8.  /* Only used for large blocks: pointer to next larger size.  */  
9.  struct malloc_chunk* fd_nextsize;      /* double links -- used only if free. */  
10.  struct malloc_chunk* bk_nextsize; 
11.};
chunk 的定義相當簡單明了，對各個域做一下簡單介紹 :
prev_size: 如果前一個 chunk 是空閑的，該域表示前一個 chunk 的大小，如果前一個 chunk 不空閑，該域無意義。
size ：當前 chunk 的大小，并且記錄了當前 chunk 和前一個 chunk 的一些屬性，包括前一個 chunk 是否在使用中，當前 chunk 是否是通過 mmap 獲得的內存，當前 chunk 是否屬于非主分配區。
fd 和 bk ：指針 fd 和 bk 只有當該 chunk 塊空閑時才存在，其作用是用于將對應的空閑 chunk 塊加入到空閑chunk 塊鏈表中統一管理，如果該 chunk 塊被分配給應用程序使用，那么這兩個指針也就沒有用（該 chunk 塊已經從空閑鏈中拆出）了，所以也當作應用程序的使用空間，而不至于浪費。
fd_nextsize 和 bk_nextsize: 當當前的 chunk 存在于 large bins 中時， large bins 中的空閑 chunk 是按照大小排序的，但同一個大小的 chunk 可能有多個，增加了這兩個字段可以加快遍歷空閑 chunk ，并查找滿足需要的空閑 chunk ， fd_nextsize 指向下一個比當前 chunk 大小大的第一個空閑 chunk ， bk_nextszie 指向前一個比當前 chunk 大小小的第一個空閑 chunk 。如果該 chunk 塊被分配給應用程序使用，那么這兩個指針也就沒有用（該chunk 塊已經從 size 鏈中拆出）了，所以也當作應用程序的使用空間，而不至于浪費。
chunk的結構
chunk的結構可以分為使用中的chunk和空閑的chunk。使用中的chunk和空閑的chunk數據結構基本項同，但是會有一些設計上的小技巧，巧妙的節省了內存。
使用中的chunk：


說明：
1、 chunk指針指向chunk開始的地址；mem指針指向用戶內存塊開始的地址。
2、 p=0時，表示前一個chunk為空閑，prev_size才有效
3、p=1時，表示前一個chunk正在使用，prev_size無效 p主要用于內存塊的合并操作；ptmalloc 分配的第一個塊總是將p設為1, 以防止程序引用到不存在的區域
4、M=1 為mmap映射區域分配；M=0為heap區域分配
5、 A=0 為主分配區分配；A=1 為非主分配區分配。
空閑的chunk：


說明：
1、當chunk空閑時，其M狀態是不存在的，只有AP狀態，
２、原本是用戶數據區的地方存儲了四個指針，
指針fd指向后一個空閑的chunk,而bk指向前一個空閑的chunk，malloc通過這兩個指針將大小相近的chunk連成一個雙向鏈表。
在large bin中的空閑chunk，還有兩個指針，fd_nextsize和bk_nextsize，用于加快在large bin中查找最近匹配的空閑chunk。不同的chunk鏈表又是通過bins或者fastbins來組織的。
空閑鏈表bins
當用戶使用free函數釋放掉的內存，ptmalloc并不會馬上交還給操作系統，而是被ptmalloc本身的空閑鏈表bins管理起來了，這樣當下次進程需要malloc一塊內存的時候，ptmalloc就會從空閑的bins上尋找一塊合適大小的內存塊分配給用戶使用。這樣的好處可以避免頻繁的系統調用，降低內存分配的開銷。
malloc將相似大小的chunk用雙向鏈表鏈接起來，這樣一個鏈表被稱為一個bin。ptmalloc一共維護了128bin。每個bins都維護了大小相近的雙向鏈表的chunk。基于chunk的大小，有下列幾種可用bins：
1、Fast bin
2、Unsorted bin
3、Small bin
4、Large bin　
保存這些bin的數據結構為：
fastbinsY：這個數組用以保存fast bins。
bins：這個數組用以保存unsorted、small以及large bins，共計可容納126個：
當用戶調用malloc的時候，能很快找到用戶需要分配的內存大小是否在維護的bin上，如果在某一個bin上，就可以通過雙向鏈表去查找合適的chunk內存塊給用戶使用。

1. fast bins。
程序在運行時會經常需要申請和釋放一些較小的內存空間。當分配器合并了相鄰的幾個小的 chunk 之后,也許馬上就會有另一個小塊內存的請求,這樣分配器又需要從大的空閑內存中切分出一塊,這樣無疑是比較低效的,故而,malloc 中在分配過程中引入了 fast bins,
fast bins是bins的高速緩沖區，大約有10個定長隊列。每個fast bin都記錄著一條free chunk的單鏈表（稱為binlist ，采用單鏈表是出于fast bin中鏈表中部的chunk不會被摘除的特點），增刪chunk都發生在鏈表的前端。fast bins 記錄著大小以8字節遞增的bin鏈表。
當用戶釋放一塊不大于max_fast（默認值64B）的chunk的時候，會默認會被放到fast bins上。當需要給用戶分配的 chunk 小于或等于 max_fast 時,malloc 首先會到fast bins上尋找是否有合適的chunk，
除非特定情況，兩個毗連的空閑chunk并不會被合并成一個空閑chunk。不合并可能會導致碎片化問題，但是卻可以大大加速釋放的過程！
分配時，binlist中被檢索的第一個chunk將被摘除并返回給用戶。free掉的chunk將被添加在索引到的binlist的前端。


2. unsorted bin。
unsorted bin 的隊列使用 bins 數組的第一個，是bins的一個緩沖區，加快分配的速度。當用戶釋放的內存大于max_fast或者fast bins合并后的chunk都會首先進入unsorted bin上。chunk大小 – 無尺寸限制，任何大小chunk都可以添加進這里。這種途徑給予 ‘glibc malloc’ 第二次機會以重新使用最近free掉的chunk，這樣尋找合適bin的時間開銷就被抹掉了，因此內存的分配和釋放會更快一些。
用戶malloc時，如果在 fast bins 中沒有找到合適的 chunk,則malloc 會先在 unsorted bin 中查找合適的空閑 chunk，如果沒有合適的bin，ptmalloc會將unsorted bin上的chunk放入bins上，然后到bins上查找合適的空閑chunk。
3. small bins
大小小于512字節的chunk被稱為small chunk，而保存small chunks的bin被稱為small bin。數組從2開始編號，前64個bin為small bins，small bin每個bin之間相差8個字節，同一個small bin中的chunk具有相同大小。
每個small bin都包括一個空閑區塊的雙向循環鏈表（也稱binlist）。free掉的chunk添加在鏈表的前端，而所需chunk則從鏈表后端摘除。
兩個毗連的空閑chunk會被合并成一個空閑chunk。合并消除了碎片化的影響但是減慢了free的速度。
分配時，當samll bin非空后，相應的bin會摘除binlist中最后一個chunk并返回給用戶。在free一個chunk的時候，檢查其前或其后的chunk是否空閑，若是則合并，也即把它們從所屬的鏈表中摘除并合并成一個新的chunk，新chunk會添加在unsorted bin鏈表的前端。
4.large bins
大小大于等于512字節的chunk被稱為large chunk，而保存large chunks的bin被稱為large bin，位于small bins后面。large bins中的每一個bin分別包含了一個給定范圍內的chunk，其中的chunk按大小遞減排序，大小相同則按照最近使用時間排列。
兩個毗連的空閑chunk會被合并成一個空閑chunk。
分配時，遵循原則“smallest-first , best-fit”,從頂部遍歷到底部以找到一個大小最接近用戶需求的chunk。一旦找到，相應chunk就會分成兩塊User chunk（用戶請求大小）返回給用戶。
Remainder chunk（剩余大小添加到unsorted bin。free時和small bin 類似。
并不是所有chunk都按照上面的方式來組織，有三種列外情況。top chunk，mmaped chunk 和last remainder chunk
1. Top chunk
top chunk相當于分配區的頂部空閑內存，當bins上都不能滿足內存分配要求的時候，就會來top chunk上分配。
當top chunk大小比用戶所請求大小還大的時候，top chunk會分為兩個部分：User chunk（用戶請求大小）和Remainder chunk（剩余大小）。其中Remainder chunk成為新的top chunk。
當top chunk大小小于用戶所請求的大小時，top chunk就通過sbrk（main arena）或mmap（thread arena）系統調用來擴容。
2. mmaped chunk
當分配的內存非常大（大于分配閥值，默認128K）的時候，需要被mmap映射，則會放到mmaped chunk上，當釋放mmaped chunk上的內存的時候會直接交還給操作系統。
3、Last remainder chunk
Last remainder chunk是另外一種特殊的chunk，就像top chunk和mmaped chunk一樣，不會在任何bins中找到這種chunk。當需要分配一個small chunk,但在small bins中找不到合適的chunk，如果last remainder chunk的大小大于所需要的small chunk大小，last remainder chunk被分裂成兩個chunk，其中一個chunk返回給用戶，另一個chunk變成新的last remainder chunk。
sbrk與mmap
在堆區中， start_brk 指向 heap 的開始，而 brk 指向 heap 的頂部。可以使用系統調用 brk()和 sbrk()來增 加標識 heap 頂部的 brk 值，從而線性的增加分配給用戶的 heap 空間。在使 malloc 之前，brk 的值等于 start_brk，也就是說 heap 大小為 0。
ptmalloc 在開始時，若請求的空間小于 mmap 分配閾值（mmap threshold，默認值為 128KB）時，主分配區會調用 sbrk()增加一塊大小為 (128 KB + chunk_size) align 4KB 的空間作為 heap。非主分配區會調用 mmap 映射一塊大小為 HEAP_MAX_SIZE（32 位系統上默認為 1MB，64 位系統上默認為 64MB）的空間作為 sub-heap。這就是前面所說的 ptmalloc 所維護的分配空間;　　　
當用戶請求內存分配時，首先會在這個區域內找一塊合適的 chunk 給用戶。當用戶釋放了 heap 中的 chunk 時，ptmalloc 又會使用 fastbins 和 bins 來組織空閑 chunk。以備用戶的下一次分配。
若需要分配的 chunk 大小小于 mmap分配閾值，而 heap 空間又不夠，則此時主分配區會通過 sbrk()調用來增加 heap 大小，非主分配區會調用 mmap 映射一塊新的 sub-heap，也就是增加 top chunk 的大小，每次 heap 增加的值都會對齊到 4KB。當用戶的請求超過 mmap 分配閾值，并且主分配區使用 sbrk()分配失敗的時候，或是非主分配區在 top chunk 中不能分配到需要的內存時，ptmalloc 會嘗試使用 mmap()直接映射一塊內存到進程內存空間。使用 mmap()直接映射的 chunk 在釋放時直接解除映射，而不再屬于進程的內存空間。任何對該內存的訪問都會產生段錯誤。而在 heap 中或是 sub-heap 中分配的空間則可能會留在進程內存空間內，還可以再次引用（當然是很危險的）。
內存分配malloc流程
獲取分配區的鎖，防止多線程沖突。
計算出實際需要分配的內存的chunk實際大小。
判斷chunk的大小，如果小于max_fast（64Ｂ），則嘗試去fast bins上取適合的chunk，如果有則分配結束。否則，下一步；
判斷chunk大小是否小于512B，如果是，則從small bins上去查找chunk，如果有合適的，則分配結束。否則下一步；
ptmalloc首先會遍歷fast bins中的chunk，將相鄰的chunk進行合并，并鏈接到unsorted bin中然后遍歷 unsorted bins。如果unsorted bins上只有一個chunk并且大于待分配的chunk，則進行切割，并且剩余的chunk繼續扔回unsorted bins；如果unsorted bins上有大小和待分配chunk相等的，則返回，并從unsorted bins刪除；如果unsorted bins中的某一chunk大小 屬于small bins的范圍，則放入small bins的頭部；如果unsorted bins中的某一chunk大小 屬于large bins的范圍，則找到合適的位置放入。若未分配成功，轉入下一步；
從large bins中查找找到合適的chunk之后，然后進行切割，一部分分配給用戶，剩下的放入unsorted bin中。
如果搜索fast bins和bins都沒有找到合適的chunk，那么就需要操作top chunk來進行分配了
當top chunk大小比用戶所請求大小還大的時候，top chunk會分為兩個部分：User chunk（用戶請求大小）和Remainder chunk（剩余大小）。其中Remainder chunk成為新的top chunk。
當top chunk大小小于用戶所請求的大小時，top chunk就通過sbrk（main arena）或mmap（thread arena）系統調用來擴容。
到了這一步，說明 top chunk 也不能滿足分配要求，所以，于是就有了兩個選擇: 如 果是主分配區，調用 sbrk()，增加 top chunk 大小；如果是非主分配區，調用 mmap 來分配一個新的 sub-heap，增加 top chunk 大小；或者使用 mmap()來直接分配。在 這里，需要依靠 chunk 的大小來決定到底使用哪種方法。判斷所需分配的 chunk 大小是否大于等于 mmap 分配閾值，如果是的話，則轉下一步，調用 mmap 分配， 否則跳到第 10 步，增加 top chunk 的大小。
使用 mmap 系統調用為程序的內存空間映射一塊 chunk_size align 4kB 大小的空間。然后將內存指針返回給用戶。
判斷是否為第一次調用 malloc，若是主分配區，則需要進行一次初始化工作，分配 一塊大小為(chunk_size + 128KB) align 4KB 大小的空間作為初始的 heap。若已經初 始化過了，主分配區則調用 sbrk()增加 heap 空間，分主分配區則在 top chunk 中切 割出一個 chunk，使之滿足分配需求，并將內存指針返回給用戶。
簡而言之：獲取分配區(arena)并加鎖–> fast bin –> unsorted bin –> small bin –> large bin –> top chunk –> 擴展堆
內存回收流程
獲取分配區的鎖，保證線程安全。
如果free的是空指針，則返回，什么都不做。
判斷當前chunk是否是mmap映射區域映射的內存，如果是，則直接munmap()釋放這塊內存。前面的已使用chunk的數據結構中，我們可以看到有M來標識是否是mmap映射的內存。
判斷chunk是否與top chunk相鄰，如果相鄰，則直接和top chunk合并（和top chunk相鄰相當于和分配區中的空閑內存塊相鄰）。轉到步驟8
如果chunk的大小大于max_fast（64b），則放入unsorted bin，并且檢查是否有合并，有合并情況并且和top chunk相鄰，則轉到步驟8；沒有合并情況則free。
如果chunk的大小小于 max_fast（64b），則直接放入fast bin，fast bin并沒有改變chunk的狀態。沒有合并情況，則free；有合并情況，轉到步驟7
在fast bin，如果當前chunk的下一個chunk也是空閑的，則將這兩個chunk合并，放入unsorted bin上面。合并后的大小如果大于64B，會觸發進行fast bins的合并操作，fast bins中的chunk將被遍歷，并與相鄰的空閑chunk進行合并，合并后的chunk會被放到unsorted bin中，fast bin會變為空。合并后的chunk和topchunk相鄰，則會合并到topchunk中。轉到步驟8
判斷top chunk的大小是否大于mmap收縮閾值（默認為128KB），如果是的話，對于主分配區，則會試圖歸還top chunk中的一部分給操作系統。free結束。
使用注意事項
為了避免Glibc內存暴增，需要注意：
1. 后分配的內存先釋放，因為ptmalloc收縮內存是從top chunk開始，如果與top chunk相鄰的chunk不能釋放，top chunk以下的chunk都無法釋放。
2. Ptmalloc不適合用于管理長生命周期的內存，特別是持續不定期分配和釋放長生命周期的內存，這將導致ptmalloc內存暴增。
3. 不要關閉 ptmalloc 的 mmap 分配閾值動態調整機制，因為這種機制保證了短生命周期的 內存分配盡量從 ptmalloc 緩存的內存 chunk 中分配，更高效，浪費更少的內存。
4. 多線程分階段執行的程序不適合用ptmalloc，這種程序的內存更適合用內存池管理
5. 盡量減少程序的線程數量和避免頻繁分配/釋放內存。頻繁分配，會導致鎖的競爭，最終導致非主分配區增加，內存碎片增高，并且性能降低。
6. 防止內存泄露，ptmalloc對內存泄露是相當敏感的，根據它的內存收縮機制，如果與top chunk相鄰的那個chunk沒有回收，將導致top chunk一下很多的空閑內存都無法返回給操作系統。
7. 防止程序分配過多的內存，或是由于glibc內存暴增，導致系統內存耗盡，程序因為OOM被系統殺掉。預估程序可以使用的最大物理內存的大小，配置系統的/proc/sys/vm/overcommit_memory ,/proc/sys/vm/overcommit_ratio,以及使用ulimit -v限制程序能使用的虛擬內存的大小，防止程序因OOM被殺死掉。

版權聲明：本文來源網絡，免費傳達知識，版權歸原作者所有。如涉及作品版權問題，請聯系我進行刪除。
???????????????? ?END ????????????????
關注我的微信公眾號，回復“加群”按規則加入技術交流群。
點擊“閱讀原文”查看更多分享，歡迎點分享、收藏、點贊、在看。