面試的時候經(jīng)常會被問到 malloc 的實現(xiàn)。從操作系統(tǒng)層面來說，malloc 確實是考察面試者對操作系統(tǒng)底層的存儲管理理解的一個很好的方式，涉及到虛擬內(nèi)存、分頁/分段等。下面逐個細說。

1. 虛擬內(nèi)存

首先需要知道的是程序運行起來的話需要被加載的物理內(nèi)存中，具體到計算機硬件就是內(nèi)存條。操作系統(tǒng)啟動的時候先把自己加載到物理內(nèi)存的固定位置（一般為底部），物理內(nèi)存的其他位置就用來運行用戶程序。程序就是一堆指令，程序運行可以簡單抽象為把指令加載到內(nèi)存中，然后 CPU 將指令從內(nèi)存載入執(zhí)行。

1. 為什么需要虛擬內(nèi)存？

CPU 對內(nèi)存的尋址最簡單的方式就是直接使用物理內(nèi)存地址，這種方式一般叫做物理尋址。早期的 PC 使用物理尋址，而且像數(shù)字信號處理器、嵌入式微控制器也使用物理尋址。物理尋址的好處是簡單，壞處也有很多，比如：

不安全：操作系統(tǒng)的地址直接暴露給用戶程序，用戶程序可以破壞操作系統(tǒng)。這種解決方案是采用特殊的硬件保護。

同時運行多個程序比較困難：多個用戶程序如果都直接引用物理地址，很容易互相干擾。那么是不是可以通過不斷交換物理內(nèi)存和磁盤來保證物理內(nèi)存某一時間自由一個程序在運行呢？當(dāng)時是可以的，但是這引入很多不必要和復(fù)雜的工作。

用戶程序大小受限：受制于物理內(nèi)存大小。我們現(xiàn)在的錯覺是應(yīng)用程序大小都小于物理內(nèi)存，這主要是因為現(xiàn)在 PC 的物理內(nèi)存都比較大。實際上只有 1G 物理內(nèi)存的 PC 是可以運行 2G 的應(yīng)用程序的。

綜合上面各種缺點，虛擬內(nèi)存出現(xiàn)了。

2. 虛擬內(nèi)存概覽

虛擬內(nèi)存的基本思想是：每個程序擁有獨立的地址空間（也就是虛擬內(nèi)存地址，或者稱作虛擬地址），互不干擾。地址空間被分割成多個塊，每一塊稱作一頁（page），每一頁有連續(xù)的地址范圍。虛擬地址的頁被映射到物理內(nèi)存（通過 MMU，Memory Management Unit），但是并不是所有的頁都必須在內(nèi)存中才能運行程序。當(dāng)程序引用到一部分在物理內(nèi)存中的地址空間時，由硬件立刻執(zhí)行必要的映射。當(dāng)程序引用到一部分不在物理內(nèi)存中的地址空間時，由操作系統(tǒng)負責(zé)將確實的部分裝入物理內(nèi)存。虛擬地址尋址（也叫做虛擬尋址）的示意圖如下。

3.虛擬內(nèi)存實現(xiàn)

1.虛擬內(nèi)存大小

一般是和 CPU 字長相關(guān)，比如 32 位對應(yīng)的虛擬地址空間大小為：0 ~ 2^31。

2. MMU

CPU 將虛擬地址發(fā)送給 MMU，然后 MMU 將虛擬地址翻譯成物理地址，再尋址物理內(nèi)存。那么虛擬地址和物理地址具體是怎么映射的呢？完成映射還需要另一個重要的數(shù)據(jù)結(jié)構(gòu)的參與：頁表（page table）。頁表完成虛擬地址和物理地址的映射，MMU 每次翻譯的時候都需要讀取頁表。頁表的一種簡單表示如下。

這里頁大小為 p 位。虛擬內(nèi)存的頁和物理內(nèi)存的頁大小一樣。虛擬地址的高 n-p 位，又叫做虛擬頁號（Virtual Page Number, VPN），用來索引物理頁號（Physical Page Number，PPN），最后將 PPN 和低 p 位組合在一起就得到了物理地址。

3. 頁表的兩個問題

前面說到用 VPN 來做頁表索引，也就是說頁表的大小為虛擬地址位數(shù) / 頁的大小。比如 32 位機器，頁大小一般為 4K ，則頁表項有 2^32 / 2^12 = 2^20 條目。如果機器字長 64 位，頁表項就更多了。那么怎么解決呢？一般有兩種方法：

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

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

多級頁表減少內(nèi)存占用的關(guān)鍵在于：

如果一級頁表中的一個 PTE 為空，那么相應(yīng)的二級頁表就根本不會存在。這是一種巨大的潛在節(jié)約。

只有一級頁表才需要常駐內(nèi)存。虛擬內(nèi)存系統(tǒng)可以在需要時創(chuàng)建、頁面調(diào)入或者調(diào)出二級頁表，從而減輕內(nèi)存的壓力。

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

關(guān)于虛擬內(nèi)存還有一些內(nèi)容比如 page fault 處理，這里就不再贅述了。

2. 分段

1. 分段概述

前面介紹了分頁內(nèi)存管理，可以說通過多級頁表，TLB 等，分頁內(nèi)存管理方法已經(jīng)相當(dāng)不錯了。那么分頁有什么缺點呢？

共享困難：通過共享頁面來實現(xiàn)共享當(dāng)然是可以的。這里的問題在于我們要保證頁面上只包含可以共享的內(nèi)容并不是一件容易的事兒，因為進程空間是直接映射到頁面上的。這樣一個頁面上很可能包含不能共享的內(nèi)容（比如既包含代碼又包含數(shù)據(jù)，代碼可以共享，而數(shù)據(jù)不能共享）。早期的 PDP-11 實現(xiàn)的一種解決方法是為指令和數(shù)據(jù)設(shè)置分離的地址空間，分別稱為 I 空間和 D 空間（其實這已經(jīng)和分段很像了）。

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

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

采用分段和分頁結(jié)合的方式管理內(nèi)存，一個地址由兩個部分組成：段和段內(nèi)地址。段內(nèi)地址又進一步分為頁號和頁偏移。在進行內(nèi)存訪問時，過程如下：

根據(jù)段號找到段描述符（存放段基址）。

檢查該段的頁表是否在內(nèi)存中。如果在，則找到它的位置，如果不在，則產(chǎn)生段錯誤。

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

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

2. 進程的段

每個 Linux 程序都有一個運行時內(nèi)存映像，也就是各個段的布局，簡單如下圖所示。

注意上圖只是一個相對位置圖，實際上這些段并不是相鄰的。主要的段包括只讀代碼段、讀寫段、運行時堆、用戶棧。在分配棧、堆段運行時地址的時候，鏈接器會使用空間地址空間布局隨機化（ASLR），但是相對位置不會變。上圖中 .data 等是對應(yīng)進程中的不同數(shù)據(jù)的 section ，或者叫做節(jié)。簡介如下。

.text: 已編譯程序的機器代碼。

.rodata: 只讀數(shù)據(jù)。

.data: 已初始化的全局和靜態(tài)變量。局部變量保存在棧上。

.bss: 未初始化的全局和靜態(tài)變量，以及所有被初始化為 0 的全局或者靜態(tài)變量。在目標文件中這個節(jié)不占據(jù)實際的空間，它僅僅是一個占位符。

3. malloc 實現(xiàn)

1. 堆內(nèi)存管理

我們常說的 malloc 函數(shù)是 glibc 提供的庫函數(shù)。glibc 的內(nèi)存管理使用的方法是 ptmalloc，除此之后還有很多其他內(nèi)存管理方案，比如 tcmalloc （golang 使用的就是 tcmalloc）。

ptmalloc 對于申請內(nèi)存小于 128KB 時，分配是在堆段，使用系統(tǒng)調(diào)用 brk() 或者 sbrk()。如果大于 128 KB 的話，分配在映射區(qū)，使用系統(tǒng)調(diào)用 mmap()。

2. brk, sbrk

在堆段申請的話，使用系統(tǒng)調(diào)用 brk 或者 sbrk。

int brk(const void *addr);void *sbrk(intptr_t incr);

brk 將 brk 指針放置到指定地址處，成功返回 0，否則返回 -1。sbrk 將 brk 指針向后移動指定字節(jié)，返回依賴于系統(tǒng)實現(xiàn)，或者返回移動前的 brk 位置，或者返回移動后的 brk 位置。下面使用 sbrk 實現(xiàn)一個巨簡單的 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 系統(tǒng)調(diào)用 mmap 將一個文件或者其它對象映射進內(nèi)存。

?

?

#include void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

mmap 的 flags 可選多種參數(shù)，當(dāng)選擇 MAP_ANONYMOUS 時，不需要傳入文件描述符，malloc 使用的就是 MAP_ANONYMOUS 模式。mmap 申請的內(nèi)存在操作系統(tǒng)的映射區(qū)。比如 32 位系統(tǒng)，映射區(qū)從 3G 虛擬地址粗向下生長，但是因為程序的其他段也會占用空間（比如代碼段必須以特定的地址開始），所以并不能申請 3G 的大小。

4. malloc 和物理內(nèi)存有關(guān)系嗎？

可以說沒關(guān)系，malloc 申請的地址是線性地址，申請的時候并沒有進行映射。訪問到的時候觸發(fā)缺頁異常，這個時候才會進行物理地址映射。

5. ptmalloc

Malloc實現(xiàn)原理：

因為brk、sbrk、mmap都屬于系統(tǒng)調(diào)用，若每次申請內(nèi)存，都調(diào)用這三個，那么每次都會產(chǎn)生系統(tǒng)調(diào)用，影響性能；其次，這樣申請的內(nèi)存容易產(chǎn)生碎片，因為堆是從低地址到高地址，如果高地址的內(nèi)存沒有被釋放，低地址的內(nèi)存就不能被回收。

所以malloc采用的是內(nèi)存池的管理方式（ptmalloc），Ptmalloc 采用邊界標記法將內(nèi)存劃分成很多塊，從而對內(nèi)存的分配與回收進行管理。為了內(nèi)存分配函數(shù)malloc的高效性，ptmalloc會預(yù)先向操作系統(tǒng)申請一塊內(nèi)存供用戶使用，當(dāng)我們申請和釋放內(nèi)存的時候，ptmalloc會將這些內(nèi)存管理起來，并通過一些策略來判斷是否將其回收給操作系統(tǒng)。這樣做的最大好處就是，使用戶申請和釋放內(nèi)存的時候更加高效，避免產(chǎn)生過多的內(nèi)存碎片。

chunk 內(nèi)存塊的基本組織單元

在 ptmalloc 的實現(xiàn)源碼中定義結(jié)構(gòu)體 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 的定義相當(dāng)簡單明了，對各個域做一下簡單介紹 :

prev_size: 如果前一個 chunk 是空閑的，該域表示前一個 chunk 的大小，如果前一個 chunk 不空閑，該域無意義。

size ：當(dāng)前 chunk 的大小，并且記錄了當(dāng)前 chunk 和前一個 chunk 的一些屬性，包括前一個 chunk 是否在使用中，當(dāng)前 chunk 是否是通過 mmap 獲得的內(nèi)存，當(dāng)前 chunk 是否屬于非主分配區(qū)。

fd 和 bk ：指針 fd 和 bk 只有當(dāng)該 chunk 塊空閑時才存在，其作用是用于將對應(yīng)的空閑 chunk 塊加入到空閑chunk 塊鏈表中統(tǒng)一管理，如果該 chunk 塊被分配給應(yīng)用程序使用，那么這兩個指針也就沒有用（該 chunk 塊已經(jīng)從空閑鏈中拆出）了，所以也當(dāng)作應(yīng)用程序的使用空間，而不至于浪費。

fd_nextsize 和 bk_nextsize: 當(dāng)當(dāng)前的 chunk 存在于 large bins 中時， large bins 中的空閑 chunk 是按照大小排序的，但同一個大小的 chunk 可能有多個，增加了這兩個字段可以加快遍歷空閑 chunk ，并查找滿足需要的空閑 chunk ， fd_nextsize 指向下一個比當(dāng)前 chunk 大小大的第一個空閑 chunk ， bk_nextszie 指向前一個比當(dāng)前 chunk 大小小的第一個空閑 chunk 。如果該 chunk 塊被分配給應(yīng)用程序使用，那么這兩個指針也就沒有用（該chunk 塊已經(jīng)從 size 鏈中拆出）了，所以也當(dāng)作應(yīng)用程序的使用空間，而不至于浪費。

chunk的結(jié)構(gòu)

chunk的結(jié)構(gòu)可以分為使用中的chunk和空閑的chunk。使用中的chunk和空閑的chunk數(shù)據(jù)結(jié)構(gòu)基本項同，但是會有一些設(shè)計上的小技巧，巧妙的節(jié)省了內(nèi)存。

使用中的chunk：

說明：

1、 chunk指針指向chunk開始的地址；mem指針指向用戶內(nèi)存塊開始的地址。

2、 p=0時，表示前一個chunk為空閑，prev_size才有效

3、p=1時，表示前一個chunk正在使用，prev_size無效 p主要用于內(nèi)存塊的合并操作；ptmalloc 分配的第一個塊總是將p設(shè)為1, 以防止程序引用到不存在的區(qū)域

4、M=1 為mmap映射區(qū)域分配；M=0為heap區(qū)域分配

5、 A=0 為主分配區(qū)分配；A=1 為非主分配區(qū)分配。

空閑的chunk：

說明：

1、當(dāng)chunk空閑時，其M狀態(tài)是不存在的，只有AP狀態(tài)，

２、原本是用戶數(shù)據(jù)區(qū)的地方存儲了四個指針，

指針fd指向后一個空閑的chunk,而bk指向前一個空閑的chunk，malloc通過這兩個指針將大小相近的chunk連成一個雙向鏈表。

在large bin中的空閑chunk，還有兩個指針，fd_nextsize和bk_nextsize，用于加快在large bin中查找最近匹配的空閑chunk。不同的chunk鏈表又是通過bins或者fastbins來組織的。

空閑鏈表bins

當(dāng)用戶使用free函數(shù)釋放掉的內(nèi)存，ptmalloc并不會馬上交還給操作系統(tǒng)，而是被ptmalloc本身的空閑鏈表bins管理起來了，這樣當(dāng)下次進程需要malloc一塊內(nèi)存的時候，ptmalloc就會從空閑的bins上尋找一塊合適大小的內(nèi)存塊分配給用戶使用。這樣的好處可以避免頻繁的系統(tǒng)調(diào)用，降低內(nèi)存分配的開銷。

malloc將相似大小的chunk用雙向鏈表鏈接起來，這樣一個鏈表被稱為一個bin。ptmalloc一共維護了128bin。每個bins都維護了大小相近的雙向鏈表的chunk?；赾hunk的大小，有下列幾種可用bins：

1、Fast bin

2、Unsorted bin

3、Small bin

4、Large bin　

保存這些bin的數(shù)據(jù)結(jié)構(gòu)為：

fastbinsY：這個數(shù)組用以保存fast bins。

bins：這個數(shù)組用以保存unsorted、small以及l(fā)arge bins，共計可容納126個：

當(dāng)用戶調(diào)用malloc的時候，能很快找到用戶需要分配的內(nèi)存大小是否在維護的bin上，如果在某一個bin上，就可以通過雙向鏈表去查找合適的chunk內(nèi)存塊給用戶使用。

1. fast bins。

程序在運行時會經(jīng)常需要申請和釋放一些較小的內(nèi)存空間。當(dāng)分配器合并了相鄰的幾個小的 chunk 之后,也許馬上就會有另一個小塊內(nèi)存的請求,這樣分配器又需要從大的空閑內(nèi)存中切分出一塊,這樣無疑是比較低效的,故而,malloc 中在分配過程中引入了 fast bins,

fast bins是bins的高速緩沖區(qū)，大約有10個定長隊列。每個fast bin都記錄著一條free chunk的單鏈表（稱為binlist ，采用單鏈表是出于fast bin中鏈表中部的chunk不會被摘除的特點），增刪chunk都發(fā)生在鏈表的前端。fast bins 記錄著大小以8字節(jié)遞增的bin鏈表。

當(dāng)用戶釋放一塊不大于max_fast（默認值64B）的chunk的時候，會默認會被放到fast bins上。當(dāng)需要給用戶分配的 chunk 小于或等于 max_fast 時,malloc 首先會到fast bins上尋找是否有合適的chunk，

除非特定情況，兩個毗連的空閑chunk并不會被合并成一個空閑chunk。不合并可能會導(dǎo)致碎片化問題，但是卻可以大大加速釋放的過程！

分配時，binlist中被檢索的第一個chunk將被摘除并返回給用戶。free掉的chunk將被添加在索引到的binlist的前端。

2. unsorted bin。

unsorted bin 的隊列使用 bins 數(shù)組的第一個，是bins的一個緩沖區(qū)，加快分配的速度。當(dāng)用戶釋放的內(nèi)存大于max_fast或者fast bins合并后的chunk都會首先進入unsorted bin上。chunk大小 – 無尺寸限制，任何大小chunk都可以添加進這里。這種途徑給予 ‘glibc malloc’ 第二次機會以重新使用最近free掉的chunk，這樣尋找合適bin的時間開銷就被抹掉了，因此內(nèi)存的分配和釋放會更快一些。

用戶malloc時，如果在 fast bins 中沒有找到合適的 chunk,則malloc 會先在 unsorted bin 中查找合適的空閑 chunk，如果沒有合適的bin，ptmalloc會將unsorted bin上的chunk放入bins上，然后到bins上查找合適的空閑chunk。

3. small bins

大小小于512字節(jié)的chunk被稱為small chunk，而保存small chunks的bin被稱為small bin。數(shù)組從2開始編號，前64個bin為small bins，small bin每個bin之間相差8個字節(jié)，同一個small bin中的chunk具有相同大小。

每個small bin都包括一個空閑區(qū)塊的雙向循環(huán)鏈表（也稱binlist）。free掉的chunk添加在鏈表的前端，而所需chunk則從鏈表后端摘除。

兩個毗連的空閑chunk會被合并成一個空閑chunk。合并消除了碎片化的影響但是減慢了free的速度。

分配時，當(dāng)samll bin非空后，相應(yīng)的bin會摘除binlist中最后一個chunk并返回給用戶。在free一個chunk的時候，檢查其前或其后的chunk是否空閑，若是則合并，也即把它們從所屬的鏈表中摘除并合并成一個新的chunk，新chunk會添加在unsorted bin鏈表的前端。

4.large bins

大小大于等于512字節(jié)的chunk被稱為large chunk，而保存large chunks的bin被稱為large bin，位于small bins后面。large bins中的每一個bin分別包含了一個給定范圍內(nèi)的chunk，其中的chunk按大小遞減排序，大小相同則按照最近使用時間排列。

兩個毗連的空閑chunk會被合并成一個空閑chunk。

分配時，遵循原則“smallest-first , best-fit”,從頂部遍歷到底部以找到一個大小最接近用戶需求的chunk。一旦找到，相應(yīng)chunk就會分成兩塊User chunk（用戶請求大小）返回給用戶。

Remainder chunk（剩余大小添加到unsorted bin。free時和small bin 類似。

并不是所有chunk都按照上面的方式來組織，有三種列外情況。top chunk，mmaped chunk 和last remainder chunk

1. Top chunk

top chunk相當(dāng)于分配區(qū)的頂部空閑內(nèi)存，當(dāng)bins上都不能滿足內(nèi)存分配要求的時候，就會來top chunk上分配。

當(dāng)top chunk大小比用戶所請求大小還大的時候，top chunk會分為兩個部分：User chunk（用戶請求大小）和Remainder chunk（剩余大?。?。其中Remainder chunk成為新的top chunk。

當(dāng)top chunk大小小于用戶所請求的大小時，top chunk就通過sbrk（main arena）或mmap（thread arena）系統(tǒng)調(diào)用來擴容。

2. mmaped chunk

當(dāng)分配的內(nèi)存非常大（大于分配閥值，默認128K）的時候，需要被mmap映射，則會放到mmaped chunk上，當(dāng)釋放mmaped chunk上的內(nèi)存的時候會直接交還給操作系統(tǒng)。

3、Last remainder chunk

Last remainder chunk是另外一種特殊的chunk，就像top chunk和mmaped chunk一樣，不會在任何bins中找到這種chunk。當(dāng)需要分配一個small chunk,但在small bins中找不到合適的chunk，如果last remainder chunk的大小大于所需要的small chunk大小，last remainder chunk被分裂成兩個chunk，其中一個chunk返回給用戶，另一個chunk變成新的last remainder chunk。

sbrk與mmap

在堆區(qū)中， start_brk 指向 heap 的開始，而 brk 指向 heap 的頂部?？梢允褂孟到y(tǒng)調(diào)用 brk()和 sbrk()來增 加標識 heap 頂部的 brk 值，從而線性的增加分配給用戶的 heap 空間。在使 malloc 之前，brk 的值等于 start_brk，也就是說 heap 大小為 0。

ptmalloc 在開始時，若請求的空間小于 mmap 分配閾值（mmap threshold，默認值為 128KB）時，主分配區(qū)會調(diào)用 sbrk()增加一塊大小為 (128 KB + chunk_size) align 4KB 的空間作為 heap。非主分配區(qū)會調(diào)用 mmap 映射一塊大小為 HEAP_MAX_SIZE（32 位系統(tǒng)上默認為 1MB，64 位系統(tǒng)上默認為 64MB）的空間作為 sub-heap。這就是前面所說的 ptmalloc 所維護的分配空間;　　　

當(dāng)用戶請求內(nèi)存分配時，首先會在這個區(qū)域內(nèi)找一塊合適的 chunk 給用戶。當(dāng)用戶釋放了 heap 中的 chunk 時，ptmalloc 又會使用 fastbins 和 bins 來組織空閑 chunk。以備用戶的下一次分配。

若需要分配的 chunk 大小小于 mmap分配閾值，而 heap 空間又不夠，則此時主分配區(qū)會通過 sbrk()調(diào)用來增加 heap 大小，非主分配區(qū)會調(diào)用 mmap 映射一塊新的 sub-heap，也就是增加 top chunk 的大小，每次 heap 增加的值都會對齊到 4KB。當(dāng)用戶的請求超過 mmap 分配閾值，并且主分配區(qū)使用 sbrk()分配失敗的時候，或是非主分配區(qū)在 top chunk 中不能分配到需要的內(nèi)存時，ptmalloc 會嘗試使用 mmap()直接映射一塊內(nèi)存到進程內(nèi)存空間。使用 mmap()直接映射的 chunk 在釋放時直接解除映射，而不再屬于進程的內(nèi)存空間。任何對該內(nèi)存的訪問都會產(chǎn)生段錯誤。而在 heap 中或是 sub-heap 中分配的空間則可能會留在進程內(nèi)存空間內(nèi)，還可以再次引用（當(dāng)然是很危險的）。

內(nèi)存分配malloc流程

獲取分配區(qū)的鎖，防止多線程沖突。

計算出實際需要分配的內(nèi)存的chunk實際大小。

判斷chunk的大小，如果小于max_fast（64Ｂ），則嘗試去fast bins上取適合的chunk，如果有則分配結(jié)束。否則，下一步；

判斷chunk大小是否小于512B，如果是，則從small bins上去查找chunk，如果有合適的，則分配結(jié)束。否則下一步；

ptmalloc首先會遍歷fast bins中的chunk，將相鄰的chunk進行合并，并鏈接到unsorted bin中然后遍歷 unsorted bins。如果unsorted bins上只有一個chunk并且大于待分配的chunk，則進行切割，并且剩余的chunk繼續(xù)扔回unsorted bins；如果unsorted bins上有大小和待分配chunk相等的，則返回，并從unsorted bins刪除；如果unsorted bins中的某一chunk大小 屬于small bins的范圍，則放入small bins的頭部；如果unsorted bins中的某一chunk大小 屬于large bins的范圍，則找到合適的位置放入。若未分配成功，轉(zhuǎn)入下一步；

從large bins中查找找到合適的chunk之后，然后進行切割，一部分分配給用戶，剩下的放入unsorted bin中。

如果搜索fast bins和bins都沒有找到合適的chunk，那么就需要操作top chunk來進行分配了

當(dāng)top chunk大小比用戶所請求大小還大的時候，top chunk會分為兩個部分：User chunk（用戶請求大?。┖蚏emainder chunk（剩余大小）。其中Remainder chunk成為新的top chunk。

當(dāng)top chunk大小小于用戶所請求的大小時，top chunk就通過sbrk（main arena）或mmap（thread arena）系統(tǒng)調(diào)用來擴容。

到了這一步，說明 top chunk 也不能滿足分配要求，所以，于是就有了兩個選擇: 如 果是主分配區(qū)，調(diào)用 sbrk()，增加 top chunk 大??；如果是非主分配區(qū)，調(diào)用 mmap 來分配一個新的 sub-heap，增加 top chunk 大??；或者使用 mmap()來直接分配。在 這里，需要依靠 chunk 的大小來決定到底使用哪種方法。判斷所需分配的 chunk 大小是否大于等于 mmap 分配閾值，如果是的話，則轉(zhuǎn)下一步，調(diào)用 mmap 分配， 否則跳到第 10 步，增加 top chunk 的大小。

使用 mmap 系統(tǒng)調(diào)用為程序的內(nèi)存空間映射一塊 chunk_size align 4kB 大小的空間。然后將內(nèi)存指針返回給用戶。

判斷是否為第一次調(diào)用 malloc，若是主分配區(qū)，則需要進行一次初始化工作，分配 一塊大小為(chunk_size + 128KB) align 4KB 大小的空間作為初始的 heap。若已經(jīng)初 始化過了，主分配區(qū)則調(diào)用 sbrk()增加 heap 空間，分主分配區(qū)則在 top chunk 中切 割出一個 chunk，使之滿足分配需求，并將內(nèi)存指針返回給用戶。

簡而言之：獲取分配區(qū)(arena)并加鎖–> fast bin –> unsorted bin –> small bin –> large bin –> top chunk –> 擴展堆

內(nèi)存回收流程

獲取分配區(qū)的鎖，保證線程安全。

如果free的是空指針，則返回，什么都不做。

判斷當(dāng)前chunk是否是mmap映射區(qū)域映射的內(nèi)存，如果是，則直接munmap()釋放這塊內(nèi)存。前面的已使用chunk的數(shù)據(jù)結(jié)構(gòu)中，我們可以看到有M來標識是否是mmap映射的內(nèi)存。

判斷chunk是否與top chunk相鄰，如果相鄰，則直接和top chunk合并（和top chunk相鄰相當(dāng)于和分配區(qū)中的空閑內(nèi)存塊相鄰）。轉(zhuǎn)到步驟8

如果chunk的大小大于max_fast（64b），則放入unsorted bin，并且檢查是否有合并，有合并情況并且和top chunk相鄰，則轉(zhuǎn)到步驟8；沒有合并情況則free。

如果chunk的大小小于 max_fast（64b），則直接放入fast bin，fast bin并沒有改變chunk的狀態(tài)。沒有合并情況，則free；有合并情況，轉(zhuǎn)到步驟7

在fast bin，如果當(dāng)前chunk的下一個chunk也是空閑的，則將這兩個chunk合并，放入unsorted bin上面。合并后的大小如果大于64B，會觸發(fā)進行fast bins的合并操作，fast bins中的chunk將被遍歷，并與相鄰的空閑chunk進行合并，合并后的chunk會被放到unsorted bin中，fast bin會變?yōu)榭?。合并后的chunk和topchunk相鄰，則會合并到topchunk中。轉(zhuǎn)到步驟8

判斷top chunk的大小是否大于mmap收縮閾值（默認為128KB），如果是的話，對于主分配區(qū)，則會試圖歸還top chunk中的一部分給操作系統(tǒng)。free結(jié)束。

使用注意事項

為了避免Glibc內(nèi)存暴增，需要注意：

1. 后分配的內(nèi)存先釋放，因為ptmalloc收縮內(nèi)存是從top chunk開始，如果與top chunk相鄰的chunk不能釋放，top chunk以下的chunk都無法釋放。

2. Ptmalloc不適合用于管理長生命周期的內(nèi)存，特別是持續(xù)不定期分配和釋放長生命周期的內(nèi)存，這將導(dǎo)致ptmalloc內(nèi)存暴增。

3. 不要關(guān)閉 ptmalloc 的 mmap 分配閾值動態(tài)調(diào)整機制，因為這種機制保證了短生命周期的 內(nèi)存分配盡量從 ptmalloc 緩存的內(nèi)存 chunk 中分配，更高效，浪費更少的內(nèi)存。

4. 多線程分階段執(zhí)行的程序不適合用ptmalloc，這種程序的內(nèi)存更適合用內(nèi)存池管理

5. 盡量減少程序的線程數(shù)量和避免頻繁分配/釋放內(nèi)存。頻繁分配，會導(dǎo)致鎖的競爭，最終導(dǎo)致非主分配區(qū)增加，內(nèi)存碎片增高，并且性能降低。

6. 防止內(nèi)存泄露，ptmalloc對內(nèi)存泄露是相當(dāng)敏感的，根據(jù)它的內(nèi)存收縮機制，如果與top chunk相鄰的那個chunk沒有回收，將導(dǎo)致top chunk一下很多的空閑內(nèi)存都無法返回給操作系統(tǒng)。

7. 防止程序分配過多的內(nèi)存，或是由于glibc內(nèi)存暴增，導(dǎo)致系統(tǒng)內(nèi)存耗盡，程序因為OOM被系統(tǒng)殺掉。預(yù)估程序可以使用的最大物理內(nèi)存的大小，配置系統(tǒng)的/proc/sys/vm/overcommit_memory ,/proc/sys/vm/overcommit_ratio,以及使用ulimit -v限制程序能使用的虛擬內(nèi)存的大小，防止程序因OOM被殺死掉。

　審核編輯：湯梓紅