malloc 背後的虛擬內存 和 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 位，頁表項就更多了。那麼怎麼解決呢？一般有兩種方法：

1. 倒排頁表。物理頁號做索引，映射到多個虛擬地址。通過虛擬地址查找的時候就需要通過虛擬地址的中間幾位來做索引了。

2. 多級頁表。以兩級頁表爲例。一級頁表中的每個 PTE （page table entry）映射虛擬地址空間的一個 4MB 的片，每一片由 1024 個連續的頁面組成。一級 PTE 指向二級頁表的基址。這樣 32 位地址空間使用 1024 個一級 PTE 就可以表示。需要的二級頁表總條目還是 2^32 / 2^12 = 2^20 個。這裏的關鍵在於如果一級 PTE i 中的頁面都未被分配，一級 PTE 就爲空。多級頁面的一個簡單示意圖如下。

多級頁表減少內存佔用的關鍵在於：

1. 如果一級頁表中的一個 PTE 爲空，那麼相應的二級頁表就根本不會存在。這是一種巨大的潛在節約。

2. 只有一級頁表才需要常駐內存。虛擬內存系統可以在需要時創建、頁面調入或者調出二級頁表，從而減輕內存的壓力。

第二個問題是頁表是在內存中，而 MMU 位於 CPU 芯片中，這樣每次地址翻譯可能都需要先訪問一次內存中的頁表（CPU L1,L2,L3 Cache Miss 的時候訪問內存），效率非常低下。對應的解決方案是引入頁表的高速緩存：TLB（Translation Lookaside Buffer）。加入 TLB，整個虛擬地址翻譯的過程如下兩圖所示。

關於虛擬內存還有一些內容比如 page fault 處理，這裏就不再贅述了。

2. 分段

1. 分段概述

前面介紹了分頁內存管理，可以說通過多級頁表，TLB 等，分頁內存管理方法已經相當不錯了。那麼分頁有什麼缺點呢？

1. 共享困難：通過共享頁面來實現共享當然是可以的。這裏的問題在於我們要保證頁面上只包含可以共享的內容並不是一件容易的事兒，因爲進程空間是直接映射到頁面上的。這樣一個頁面上很可能包含不能共享的內容（比如既包含代碼又包含數據，代碼可以共享，而數據不能共享）。早期的 PDP-11 實現的一種解決方法是爲指令和數據設置分離的地址空間，分別稱爲 I 空間和 D 空間（其實這已經和分段很像了）。

2. 程序地址空間受限於虛擬地址：我們將程序全部映射到一個統一的虛擬地址的問題在於不好擴張。不如我們程序的地址按先代碼放在一起，然後把數據放在一起，然後再放 XXX，這樣其中某一部分的空間擴張起來都會影響到相鄰的空間，非常不方便。

上面的問題一個比較直觀的解決方法是提供多個獨立的地址空間，也就是段（segment）。每個段的長度視具體的段不同而不同，而且是可以在運行期動態改變的。因爲每個段都構成了一個獨立的地址空間，所以它們可以獨立的增長或者減小而不會影響到其他的段。如果一個段比較大，把它整個保存到內存中可能很不方便甚至是不可能的，因此可以對段採用分頁管理，只有那些真正需要的頁面纔會被調入內存。

採用分段和分頁結合的方式管理內存，一個地址由兩個部分組成：段和段內地址。段內地址又進一步分爲頁號和頁偏移。在進行內存訪問時，過程如下：

1. 根據段號找到段描述符（存放段基址）。

2. 檢查該段的頁表是否在內存中。如果在，則找到它的位置，如果不在，則產生段錯誤。

3. 檢查所請求的虛擬頁面的頁表項，如果該頁面不在內存中則產生缺頁中斷，如果在內存中就從頁表項中取出這個頁面在內存中的起始地址。

4. 將頁面起始地址和偏移量進行拼接得到物理地址，然後完成讀寫。

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 <sys/mman.h>

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 定義如下：

struct malloc_chunk {  
  INTERNAL_SIZE_T      prev_size;    /* Size of previous chunk (if free).  */  
  INTERNAL_SIZE_T      size;         /* Size in bytes, including overhead. */  
  
  struct malloc_chunk* fd;           /* double links -- used only if free. */  
  struct malloc_chunk* bk;  
  
  /* Only used for large blocks: pointer to next larger size.  */  
  struct malloc_chunk* fd_nextsize;      /* double links -- used only if free. */  
  struct malloc_chunk* bk_nextsize; 
};

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 被殺死掉。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/kJq03LoTLb7Uit1c6Z_VzQ