摘要：分頁管理先說說虛擬內(nèi)存的概念。每個(gè)存在的虛擬頁面都保存在某個(gè)區(qū)域中，不屬于任何一個(gè)區(qū)域的虛擬頁是不存在的，不能被進(jìn)程使用內(nèi)核為系統(tǒng)中的每個(gè)進(jìn)程維護(hù)一個(gè)多帶帶的任務(wù)結(jié)構(gòu)，任務(wù)中的一個(gè)字段指向，他描述了虛擬內(nèi)存的當(dāng)前狀態(tài)。

作者： 順風(fēng)車運(yùn)營研發(fā)團(tuán)隊(duì) 李樂

程序是代碼和數(shù)據(jù)的集合，進(jìn)程是運(yùn)行著的程序；操作系統(tǒng)需要為進(jìn)程分配內(nèi)存；進(jìn)程運(yùn)行完畢需要釋放內(nèi)存；內(nèi)存管理就是內(nèi)存的分配和釋放；

分段最早出現(xiàn)在8086系統(tǒng)中，當(dāng)時(shí)只有16位地址總線，其能訪問的最大地址是64k；當(dāng)時(shí)的內(nèi)存大小為1M；如何利用16位地址訪問1M的內(nèi)存空間呢？

于是提出了分段式內(nèi)存管理；
將內(nèi)存地址分為段地址與段偏移，段地址會(huì)存儲(chǔ)在寄存器中，段偏移即程序?qū)嶋H使用的地址；當(dāng)CPU需要訪問內(nèi)存時(shí)，會(huì)將段地址左移4位，再加上段偏移，即可得到物理內(nèi)存地址；
即內(nèi)存地址=段地址*16+段偏移地址。

后來的IA-32在內(nèi)存中使用一張段表來記錄各個(gè)段映射的物理內(nèi)存地址，CPU只需要為這個(gè)段表提供一個(gè)記錄其首地址的寄存器就可以了；如下圖所示：

進(jìn)程包含多個(gè)段：代碼段，數(shù)據(jù)段，鏈接庫等；系統(tǒng)需要為每個(gè)段分配內(nèi)存；
一種很自然地想法是，根據(jù)每個(gè)段實(shí)際需要的大小進(jìn)行分配，并記錄已經(jīng)占用的空間和剩余空間：
當(dāng)一個(gè)段請(qǐng)求內(nèi)存時(shí)，如果有內(nèi)存中有很多大小不一的空閑位置，那么選擇哪個(gè)最合理？

a）首先適配：空閑鏈表中選擇第一個(gè)位置(優(yōu)點(diǎn)：查表速度快) 
b）最差適配：選擇一個(gè)最大的空閑區(qū)域 
c）最佳適配：選擇一個(gè)空閑位置大小和申請(qǐng)內(nèi)存大小最接近的位置，比如申請(qǐng)一個(gè)40k內(nèi)存，而恰巧內(nèi)存中有一個(gè)50k的空閑位置；

內(nèi)存分段管理具有以下優(yōu)點(diǎn)：

a）內(nèi)存共享： 對(duì)內(nèi)存分段，可以很容易把其中的代碼段或數(shù)據(jù)段共享給其他程序；
b）安全性： 將內(nèi)存分為不同的段之后，因?yàn)椴煌蔚膬?nèi)容類型不同，所以他們能進(jìn)行的操作也不同，比如代碼段的內(nèi)容被加載后就不應(yīng)該允許寫的操作，因?yàn)檫@樣會(huì)改變程序的行為
c）動(dòng)態(tài)鏈接： 動(dòng)態(tài)鏈接是指在作業(yè)運(yùn)行之前，并不把幾個(gè)目標(biāo)程序段鏈接起來。要運(yùn)行時(shí)，先將主程序所對(duì)應(yīng)的目標(biāo)程序裝入內(nèi)存并啟動(dòng)運(yùn)行，當(dāng)運(yùn)行過程中又需要調(diào)用某段時(shí)，才將該段(目標(biāo)程序)調(diào)入內(nèi)存并進(jìn)行鏈接。

盡管分段管理的方式解決了內(nèi)存的分配與釋放，但是會(huì)帶來大量的內(nèi)存碎片；即盡管我們內(nèi)存中仍然存在很大空間，但全部都是一些零散的空間，當(dāng)申請(qǐng)大塊內(nèi)存時(shí)會(huì)出現(xiàn)申請(qǐng)失敗；為了不使這些零散的空間浪費(fèi)，操作系統(tǒng)會(huì)做內(nèi)存緊縮，即將內(nèi)存中的段移動(dòng)到另一位置。但明顯移動(dòng)進(jìn)程是一個(gè)低效的操作。

先說說虛擬內(nèi)存的概念。CPU訪問物理內(nèi)存的速度要比磁盤快的多，物理內(nèi)存可以認(rèn)為是磁盤的緩存，但物理內(nèi)存是有限的，于是人們想到利用磁盤空間虛擬出的一塊邏輯內(nèi)存
（這部分磁盤空間Windows下稱之為虛擬內(nèi)存，Linux下被稱為交換空間（Swap Space））；

虛擬內(nèi)存和真實(shí)的物理內(nèi)存存在著映射關(guān)系；

為了解決分段管理帶來的碎片問題，操作系統(tǒng)將虛擬內(nèi)存分割為虛擬頁，相應(yīng)的物理內(nèi)存被分割為物理頁；而虛擬頁和物理頁的大小默認(rèn)都是4K字節(jié)；

操作系統(tǒng)以頁為單位分配內(nèi)存：假設(shè)需要3k字節(jié)的內(nèi)存，操作系統(tǒng)會(huì)直接分配一個(gè)4K頁給進(jìn)程
，這就產(chǎn)生了內(nèi)部碎片（浪費(fèi)率優(yōu)于分段管理）

前面說過，物理內(nèi)存可以認(rèn)為是磁盤的緩存；虛擬頁首先需要分配給進(jìn)程并創(chuàng)建與物理頁的映射關(guān)系，然后才能將磁盤數(shù)據(jù)載入內(nèi)存供CPU使用；由此可見，虛擬內(nèi)存系統(tǒng)必須能夠記錄一個(gè)虛擬頁是否已經(jīng)分配給進(jìn)程；是否已經(jīng)將磁盤數(shù)據(jù)載入內(nèi)存，對(duì)應(yīng)哪個(gè)物理頁；假如沒有載入內(nèi)存，這個(gè)虛擬頁存放在磁盤的哪個(gè)位置；
于是虛擬頁可以分為三種類型：已分配，未緩存，已緩存；

當(dāng)訪問沒有緩存的虛擬頁時(shí)，系統(tǒng)會(huì)在物理內(nèi)存中選擇一個(gè)犧牲頁，并將虛擬頁從磁盤賦值到物理內(nèi)存，替換這個(gè)犧牲頁；而如果這個(gè)犧牲頁已經(jīng)被修改，則還需要寫回磁盤；這個(gè)過程就是所謂的缺頁中斷；

虛擬頁的集合就稱為頁表（pageTable），頁表就是一個(gè)頁表?xiàng)l目（page table entry）的數(shù)組；每個(gè)頁表?xiàng)l目都包含有效位標(biāo)志，記錄當(dāng)前虛擬頁是否分配，當(dāng)前虛擬頁的訪問控制權(quán)限；同時(shí)包含物理頁號(hào)或磁盤地址；

進(jìn)程所看到的地址都是虛擬地址；在訪問虛擬地址時(shí)，操作系統(tǒng)需要將虛擬地址轉(zhuǎn)化為實(shí)際的物理地址；而虛擬地址到物理地址的映射是存儲(chǔ)在頁表的；

將虛擬地址分為兩部分：虛擬頁號(hào)，記錄虛擬頁在頁表中的偏移量（相當(dāng)于數(shù)組索引）；頁內(nèi)偏移量；而頁表的首地址是存儲(chǔ)在寄存器中；

對(duì)于32位系統(tǒng)，內(nèi)存為4G，頁大小為4K，假設(shè)每個(gè)頁表項(xiàng)4字節(jié)；則頁表包含1M個(gè)頁表項(xiàng)，占用4M的存儲(chǔ)空間，頁表本身就需要分配1K個(gè)物理頁；
頁表?xiàng)l目太大時(shí)，頁表本身需要占用更多的物理內(nèi)存，而且其內(nèi)存還必須是連續(xù)的；

目前有三種優(yōu)化技術(shù)：

1）多級(jí)頁表
一級(jí)頁表中的每個(gè)PTE負(fù)責(zé)映射虛擬地址空間中一個(gè)4M的片（chunk），每一個(gè)片由1024個(gè)連續(xù)的頁面組成；二級(jí)頁表的每個(gè)PTE都映射一個(gè)4K的虛擬內(nèi)存頁面；

優(yōu)點(diǎn)：節(jié)約內(nèi)存（假如一級(jí)頁表中的PTE為null，則其指向的二級(jí)頁表就不存在了，而大多數(shù)進(jìn)程4G的虛擬地址空間大部分都是未分配的；只有一級(jí)頁表才總是需要在主存中，系統(tǒng)可以在需要的時(shí)候創(chuàng)建、調(diào)入、調(diào)出二級(jí)頁表）
缺點(diǎn)：虛擬地址到物理地址的翻譯更復(fù)雜了

2）TLB
多級(jí)頁表可以節(jié)約內(nèi)存，但是對(duì)于一次地址翻譯，增加了內(nèi)存訪問次數(shù)，k級(jí)頁表，需要訪問k次內(nèi)存才能完成地址的翻譯；

由此出現(xiàn)了TLB：他是一個(gè)更小，訪問速度更快的虛擬地址的緩存；當(dāng)需要翻譯虛擬地址時(shí)，先在TLB查找，命中的話就可以直接完成地址的翻譯；沒命中再頁表中查找；

3）hugePage

因?yàn)閮?nèi)存大小是固定的，為了減少映射表的條目，可采取的辦法只有增加頁的尺寸。hugePage便因此而來，使用大頁面2m,4m,16m等等。如此一來映射條目則明顯減少。

linux為每個(gè)進(jìn)程維護(hù)一個(gè)多帶帶的虛擬地址空間，進(jìn)程都以為自己獨(dú)占了整個(gè)內(nèi)存空間，如圖所示：

linux將內(nèi)存組織為一些區(qū)域（段）的集合，如代碼段，數(shù)據(jù)段，堆，共享庫段，以及用戶棧都是不同的區(qū)域。每個(gè)存在的虛擬頁面都保存在某個(gè)區(qū)域中，不屬于任何一個(gè)區(qū)域的虛擬頁是不存在的，不能被進(jìn)程使用；

內(nèi)核為系統(tǒng)中的每個(gè)進(jìn)程維護(hù)一個(gè)多帶帶的任務(wù)結(jié)構(gòu)task_struct，任務(wù)中的一個(gè)字段指向mm_struct，他描述了虛擬內(nèi)存的當(dāng)前狀態(tài)。其中包含兩個(gè)字段：pgd指向第一級(jí)頁表的基址（當(dāng)內(nèi)核運(yùn)行這個(gè)進(jìn)程時(shí)，就將pgd的內(nèi)容存儲(chǔ)在cr3控制寄存器中）；mmap指向一個(gè)vm_area_struct區(qū)域結(jié)構(gòu)的鏈表；區(qū)域結(jié)構(gòu)主要包括以下字段：
vm_start：區(qū)域的起始地址；
vm_end：區(qū)域的結(jié)束地址；
vm_port：指向這個(gè)區(qū)域所包含頁的讀寫許可權(quán)限；
vm_flags：描述這個(gè)區(qū)域是與其他進(jìn)程共享的，還是私有的等信息；

當(dāng)我們訪問虛擬地址時(shí)，內(nèi)核會(huì)遍歷vm_area_struct鏈表，根據(jù)vm_start和vm_end能夠判斷地址合法性；根據(jù)vm_por能夠判斷地址訪問的合法性；
遍歷鏈表時(shí)間性能較差，內(nèi)核會(huì)將vm_area_struct區(qū)域組織成一棵樹；

說到這里就不得不提一下系統(tǒng)調(diào)用mmap，其函數(shù)聲明為

void* mmap ( void * addr , size_t len , int prot , int flags , int fd , off_t offset )

函數(shù)mmap要求內(nèi)核創(chuàng)建一個(gè)新的虛擬內(nèi)存區(qū)域（注意是新的區(qū)域，和堆是平級(jí)關(guān)系，即mmap函數(shù)并不是在堆上分配內(nèi)存的，）；最好是從地址addr開始（一般傳null），并將文件描述fd符指定的對(duì)象的一個(gè)連續(xù)的chunk（大小為len，從文件偏移offset開始）映射到這個(gè)新的區(qū)域；當(dāng)fd傳-1時(shí)，可用于申請(qǐng)分配內(nèi)存；

參數(shù)port描述這個(gè)區(qū)域的訪問控制權(quán)限，可以取以下值：

PROT_EXEC //頁內(nèi)容可以被執(zhí)行
PROT_READ //頁內(nèi)容可以被讀取
PROT_WRITE //頁可以被寫入
PROT_NONE //頁不可訪問

參數(shù)flags由描述被映射對(duì)象類型的位組成，如MAP_SHARED 表示與其它所有映射這個(gè)對(duì)象的進(jìn)程共享映射空間；MAP_PRIVATE 表示建立一個(gè)寫入時(shí)拷貝的私有映射，內(nèi)存區(qū)域的寫入不會(huì)影響到原文件。

php在分配2M以上大內(nèi)存時(shí)，就是直接使用mmap申請(qǐng)的；

malloc是c庫函數(shù)，用于在堆上分配內(nèi)存；操作系統(tǒng)給進(jìn)程分配的堆空間是若干個(gè)頁，我們再調(diào)用malloc向進(jìn)程請(qǐng)求分配若干字節(jié)大小的內(nèi)存；
malloc就是一種內(nèi)存分配器，負(fù)責(zé)堆內(nèi)存的分配與回收；

同樣我們可以使用mmap和munmap來創(chuàng)建和刪除虛擬內(nèi)存區(qū)域，以達(dá)到內(nèi)存的申請(qǐng)與釋放；

觀察第一章第三小節(jié)中的虛擬地址空間描述圖，每個(gè)進(jìn)程都有一個(gè)稱為運(yùn)行時(shí)堆的虛擬內(nèi)存區(qū)域，操作系統(tǒng)內(nèi)核維護(hù)著一個(gè)變量brk，指向了堆的頂部；并提供系統(tǒng)調(diào)用brk(void* addr)和sbrk(incr)來修改變量brk的值，從而實(shí)現(xiàn)堆內(nèi)存的擴(kuò)張與收縮；

brk函數(shù)將brk指針直接設(shè)置為某個(gè)地址，而sbrk函數(shù)將brk從當(dāng)前位置移動(dòng)incr所指定的增量；（如果將incr設(shè)置為0，則可以獲得當(dāng)前brk指向的地址）

因此我們也可以使用brk()或sbrk()來動(dòng)態(tài)分配/釋放內(nèi)存塊；

需要注意的一點(diǎn)是：系統(tǒng)為每一個(gè)進(jìn)程所分配的資源不是無限的，包括可映射的內(nèi)存空間，即堆內(nèi)存并不是無限大的；所以當(dāng)調(diào)用malloc將堆內(nèi)存都分配完時(shí)，malloc會(huì)使用mmap函數(shù)額外再申請(qǐng)一個(gè)虛擬內(nèi)存區(qū)域（由此發(fā)現(xiàn)，使用malloc申請(qǐng)的內(nèi)存也并不一定是在堆上）

內(nèi)存分配器用于處理堆上的內(nèi)存分配或釋放請(qǐng)求；

要實(shí)現(xiàn)分配器必須考慮以下幾個(gè)問題：

1.空閑塊組織：如何記錄空閑塊；如何標(biāo)記內(nèi)存塊是否空閑；
2.分配：如何選擇一個(gè)合適的空閑塊來處理分配請(qǐng)求；
3.分割：空閑塊一般情況會(huì)大于實(shí)際的分配請(qǐng)求，我們?nèi)绾翁幚磉@個(gè)空閑塊中的剩余部分；
4.回收：如何處理一個(gè)剛剛被釋放的塊；

思考1：空閑塊組織
內(nèi)存分配與釋放請(qǐng)求時(shí)完全隨機(jī)的，最終會(huì)造成堆內(nèi)存被分割為若干個(gè)內(nèi)存小塊，其中有些處于已分配狀態(tài)，有些處于空閑狀態(tài)；我們需要額外的空間來標(biāo)記內(nèi)存狀態(tài)以及內(nèi)存塊大??；
下圖為malloc設(shè)計(jì)思路：

注：圖中顯示額外使用4字節(jié)記錄當(dāng)前內(nèi)存塊屬性，其中3比特記錄是否空閑，29比特記錄內(nèi)存塊大小；實(shí)際malloc頭部格式可能會(huì)根據(jù)版本等調(diào)整；不論我們使用malloc分配多少字節(jié)的內(nèi)存，實(shí)際malloc分配的內(nèi)存都會(huì)多幾個(gè)字節(jié)；
注：空閑內(nèi)存塊可能會(huì)被組織為一個(gè)鏈表結(jié)構(gòu)，由此可以遍歷所有空閑內(nèi)存塊，直到查找到一個(gè)滿足條件的為止；

思考2：如何選擇合適的空閑塊
在處理內(nèi)存分配請(qǐng)求時(shí)，需要查找空閑內(nèi)存鏈表，找到一個(gè)滿足申請(qǐng)條件的空閑內(nèi)存塊，選擇什么查找算法；而且很有可能存在多個(gè)符合條件的空閑內(nèi)存塊，此時(shí)如何選擇？
目前有很多比較成熟的算法，如首次適配，最佳適配，最差適配等；

思考3：如何分配
在查找到滿足條件的空閑內(nèi)存塊時(shí)，此內(nèi)存一般情況會(huì)比實(shí)際請(qǐng)求分配的內(nèi)存空間要大；全部分配給用戶，浪費(fèi)空間；因此一般會(huì)將此空閑內(nèi)存塊切割為兩個(gè)小塊內(nèi)存，一塊分配給用戶，一塊標(biāo)記為新的空閑內(nèi)存

思考4：如何回收：
當(dāng)用戶調(diào)用free()函數(shù)釋放內(nèi)存時(shí)，需要將此塊內(nèi)存重新標(biāo)記為空閑內(nèi)存，并且插入空閑鏈表；然而需要注意的是，此塊內(nèi)存可能能夠與其他空閑內(nèi)存拼接為更大的空閑內(nèi)存；此時(shí)還需要算法來處理空閑內(nèi)存的合并；

思考5：內(nèi)存分配效率問題：
用戶請(qǐng)求分配內(nèi)存時(shí)，需要遍歷空閑內(nèi)存鏈表，直到查找到一個(gè)滿足申請(qǐng)條件的空閑內(nèi)存；由此可見，算法復(fù)雜度與鏈表長度成正比；
我們可以將空閑內(nèi)存按照空間大小組織為多個(gè)空閑鏈表，內(nèi)存大小相近的形成一個(gè)鏈表；此時(shí)只需要根據(jù)申請(qǐng)內(nèi)存大小查找相應(yīng)空閑鏈表即可；
更進(jìn)一步的，空閑內(nèi)存只會(huì)被切割為固定大小，如2^n字節(jié)，每種字節(jié)大小的空閑內(nèi)存形成一個(gè)鏈表；（用戶實(shí)際分配的內(nèi)存是2^n字節(jié)，大于用戶實(shí)際請(qǐng)求）

總結(jié)：任何內(nèi)存分配器都需要額外的空間（數(shù)據(jù)結(jié)構(gòu)）記錄每個(gè)內(nèi)存塊大小及其分配狀態(tài)；

C/C++下內(nèi)存管理是讓幾乎每一個(gè)程序員頭疼的問題，分配足夠的內(nèi)存、追蹤內(nèi)存的分配、在不需要的時(shí)候釋放內(nèi)存——這個(gè)任務(wù)相當(dāng)復(fù)雜。而直接使用系統(tǒng)調(diào)用malloc/free、new/delete進(jìn)行內(nèi)存分配和釋放，有以下弊端：

調(diào)用malloc/new，系統(tǒng)需要根據(jù)“最先匹配”、“最優(yōu)匹配”或其他算法在內(nèi)存空閑塊表中查找一塊空閑內(nèi)存，調(diào)用free/delete，系統(tǒng)可能需要合并空閑內(nèi)存塊，這些都會(huì)產(chǎn)生額外的開銷；
頻繁使用時(shí)會(huì)產(chǎn)生大量內(nèi)存碎片，從而降低程序運(yùn)行效率；
容易造成內(nèi)存泄漏；

內(nèi)存池（memory pool)是代替直接調(diào)用malloc/free、new/delete進(jìn)行內(nèi)存管理的常用方法，當(dāng)我們申請(qǐng)內(nèi)存空間時(shí)，首先到我們的內(nèi)存池中查找合適的內(nèi)存塊，而不是直接向操作系統(tǒng)申請(qǐng)，優(yōu)勢在于：

比malloc/free進(jìn)行內(nèi)存申請(qǐng)/釋放的方式快
不會(huì)產(chǎn)生或很少產(chǎn)生堆碎片
可避免內(nèi)存泄漏

內(nèi)存池一般會(huì)組織成如下結(jié)構(gòu)：
結(jié)構(gòu)中主要包含block、list 和pool這三個(gè)結(jié)構(gòu)體，block結(jié)構(gòu)包含指向?qū)嶋H內(nèi)存空間的指針，前向和后向指針讓block能夠組成雙向鏈表；list結(jié)構(gòu)中free指針指向空閑 內(nèi)存塊組成的鏈表，used指針指向程序使用中的內(nèi)存塊組成的鏈表，size值為內(nèi)存塊的大小，list之間組成單向鏈表；pool結(jié)構(gòu)記錄list鏈表的頭和尾。

當(dāng)用戶申請(qǐng)內(nèi)存時(shí)，只需要根據(jù)所申請(qǐng)內(nèi)存的大小，遍歷list鏈表，查看是否存在相匹配的size；

PHP并沒有直接使用現(xiàn)有的malloc/free來管理內(nèi)存的分配和釋放，而是重新實(shí)現(xiàn)了一套內(nèi)存管理方案；

PHP采取“預(yù)分配方案”，提前向操作系統(tǒng)申請(qǐng)一個(gè)chunk（2M，利用到hugepage特性），并且將這2M內(nèi)存切割為不同規(guī)格（大?。┑娜舾蓛?nèi)存塊，當(dāng)程序申請(qǐng)內(nèi)存時(shí)，直接查找現(xiàn)有的空閑內(nèi)存塊即可；

PHP將內(nèi)存分配請(qǐng)求分為3種情況：

huge內(nèi)存：針對(duì)大于2M-4K的分配請(qǐng)求，直接調(diào)用mmap分配；

large內(nèi)存：針對(duì)小于2M-4K，大于3K的分配請(qǐng)求，在chunk上查找滿足條件的若干個(gè)連續(xù)page；

small內(nèi)存：針對(duì)小于3K的分配請(qǐng)求；PHP拿出若干個(gè)頁切割為8字節(jié)大小的內(nèi)存塊，拿出若干個(gè)頁切割為16字節(jié)大小的內(nèi)存塊，24字節(jié)，32字節(jié)等等，將其組織成若干個(gè)空閑鏈表；每當(dāng)有分配請(qǐng)求時(shí)，只在對(duì)應(yīng)的空閑鏈表獲取一個(gè)內(nèi)存塊即可；

1.1結(jié)構(gòu)體

PHP需要記錄申請(qǐng)的所有chunk，需要記錄chunk中page的使用情況，要記錄每種規(guī)格內(nèi)存的空閑鏈表，要記錄使用mmap分配的huge內(nèi)存，等等…………

于是有了以下兩個(gè)結(jié)構(gòu)體：
_zend_mm_heap記錄著內(nèi)存管理器所需的所有數(shù)據(jù)：

//省略了結(jié)構(gòu)體中很多字段
struct _zend_mm_heap {
    //統(tǒng)計(jì)
    size_t             size;                    /* current memory usage */
    size_t             peak;                    /* peak memory usage */
    //由于“預(yù)分配”方案，實(shí)際使用內(nèi)存和向操作系統(tǒng)申請(qǐng)的內(nèi)存大小是不一樣的；
    size_t             real_size;               /* current size of allocated pages */
    size_t             real_peak;               /* peak size of allocated pages */
 
    //small內(nèi)存分為30種；free_slot數(shù)組長度為30；數(shù)組索引上掛著內(nèi)存空閑鏈表
    zend_mm_free_slot *free_slot[ZEND_MM_BINS]; /* free lists for small sizes */
 
    //內(nèi)存限制
    size_t             limit;                   /* memory limit */
    int                overflow;                /* memory overflow flag */
 
    //記錄已分配的huge內(nèi)存
    zend_mm_huge_list *huge_list;               /* list of huge allocated blocks */
 
    //PHP會(huì)分配若干chunk，記錄當(dāng)前主chunk首地址
    zend_mm_chunk     *main_chunk;
     
    //統(tǒng)計(jì)chunk數(shù)目
    int                chunks_count;            /* number of alocated chunks */
    int                peak_chunks_count;       /* peak number of allocated chunks for current request */ 
}

_zend_mm_chunk記錄著當(dāng)前chunk的所有數(shù)據(jù)

struct _zend_mm_chunk {
    //指向heap
    zend_mm_heap      *heap;
    //chunk組織為雙向鏈表
    zend_mm_chunk     *next;
    zend_mm_chunk     *prev;
    //當(dāng)前chunk空閑page數(shù)目
    uint32_t           free_pages;              /* number of free pages */
    //當(dāng)前chunk最后一個(gè)空閑的page位置
    uint32_t           free_tail;               /* number of free pages at the end of chunk */
    //每當(dāng)申請(qǐng)一個(gè)新的chunk時(shí)，這個(gè)chunk的num會(huì)遞增
    uint32_t           num;
    //預(yù)留
    char               reserve[64 - (sizeof(void*) * 3 + sizeof(uint32_t) * 3)];
    //指向heap，只有main_chunk使用
    zend_mm_heap       heap_slot;               /* used only in main chunk */
    //記錄512個(gè)page的分配情況；0代表空閑，1代表已分配
    zend_mm_page_map   free_map;                /* 512 bits or 64 bytes */
    //記錄每個(gè)page的詳細(xì)信息，
    zend_mm_page_info  map[ZEND_MM_PAGES];      /* 2 KB = 512 * 4 */
};

1.2small內(nèi)存

前面講過small內(nèi)存分為30種規(guī)格，每種規(guī)格的空閑內(nèi)存都掛在_zend_mm_heap結(jié)構(gòu)體的free_slot數(shù)組上；
30種規(guī)格內(nèi)存如下：

//宏定義：第一列表示序號(hào)（稱之為bin_num），第二列表示每個(gè)small內(nèi)存的大?。ㄗ止?jié)數(shù)）；
//第四列表示每次獲取多少個(gè)page；第三列表示將page分割為多少個(gè)大小為第一列的small內(nèi)存；
#define ZEND_MM_BINS_INFO(_, x, y) 
    _( 0,    8,  512, 1, x, y) 
    _( 1,   16,  256, 1, x, y) 
    _( 2,   24,  170, 1, x, y) 
    _( 3,   32,  128, 1, x, y) 
    _( 4,   40,  102, 1, x, y) 
    _( 5,   48,   85, 1, x, y) 
    _( 6,   56,   73, 1, x, y) 
    _( 7,   64,   64, 1, x, y) 
    _( 8,   80,   51, 1, x, y) 
    _( 9,   96,   42, 1, x, y) 
    _(10,  112,   36, 1, x, y) 
    _(11,  128,   32, 1, x, y) 
    _(12,  160,   25, 1, x, y) 
    _(13,  192,   21, 1, x, y) 
    _(14,  224,   18, 1, x, y) 
    _(15,  256,   16, 1, x, y) 
    _(16,  320,   64, 5, x, y) 
    _(17,  384,   32, 3, x, y) 
    _(18,  448,    9, 1, x, y) 
    _(19,  512,    8, 1, x, y) 
    _(20,  640,   32, 5, x, y) 
    _(21,  768,   16, 3, x, y) 
    _(22,  896,    9, 2, x, y) 
    _(23, 1024,    8, 2, x, y) 
    _(24, 1280,   16, 5, x, y) 
    _(25, 1536,    8, 3, x, y) 
    _(26, 1792,   16, 7, x, y) 
    _(27, 2048,    8, 4, x, y) 
    _(28, 2560,    8, 5, x, y) 
    _(29, 3072,    4, 3, x, y)
 
#endif /* ZEND_ALLOC_SIZES_H */

只有這個(gè)宏定義有些功能不好用程序?qū)崿F(xiàn)，比如bin_num=15時(shí)，獲得此種small內(nèi)存的字節(jié)數(shù)？分配此種small內(nèi)存時(shí)需要多少page呢？
于是有了以下3個(gè)數(shù)組的定義：

//bin_pages是一維數(shù)組，數(shù)組大小為30，數(shù)組索引為bin_num，
//數(shù)組元素為ZEND_MM_BINS_INFO宏中的第四列
#define _BIN_DATA_PAGES(num, size, elements, pages, x, y) pages,
static const uint32_t bin_pages[] = {
  ZEND_MM_BINS_INFO(_BIN_DATA_PAGES, x, y)
};

//bin_elements是一維數(shù)組，數(shù)組大小為30，數(shù)組索引為bin_num，
//數(shù)組元素為ZEND_MM_BINS_INFO宏中的第三列
#define _BIN_DATA_ELEMENTS(num, size, elements, pages, x, y) elements,
static const uint32_t bin_elements[] = {
  ZEND_MM_BINS_INFO(_BIN_DATA_ELEMENTS, x, y)
};

//bin_data_size是一維數(shù)組，數(shù)組大小為30，數(shù)組索引為bin_num，
//數(shù)組元素為ZEND_MM_BINS_INFO宏中的第二列
#define _BIN_DATA_SIZE(num, size, elements, pages, x, y) size,
static const uint32_t bin_data_size[] = {
  ZEND_MM_BINS_INFO(_BIN_DATA_SIZE, x, y)
};

2.1設(shè)計(jì)思路

上一節(jié)提到PHP將small內(nèi)存分為30種不同大小的規(guī)格；
每種大小規(guī)格的空閑內(nèi)存會(huì)組織為鏈表，掛在數(shù)組_zend_mm_heap結(jié)構(gòu)體的free_slot[bin_num]索引上；

回顧下free_slot字段的定義：

zend_mm_free_slot *free_slot[ZEND_MM_BINS];
 
struct zend_mm_free_slot {
    zend_mm_free_slot *next_free_slot;
};

可以看出空閑內(nèi)存鏈表的每個(gè)節(jié)點(diǎn)都是一個(gè)zend_mm_free_slot結(jié)構(gòu)體，其只有一個(gè)next指針字段；

思考：對(duì)于8字節(jié)大小的內(nèi)存塊，其next指針就需要占8字節(jié)的空間，那用戶的數(shù)據(jù)存儲(chǔ)在哪里呢？
答案：free_slot是small內(nèi)存的空閑鏈表，空閑指的是未分配內(nèi)存，此時(shí)是不需要存儲(chǔ)其他數(shù)據(jù)的；當(dāng)分配給用戶時(shí)，此節(jié)點(diǎn)會(huì)從空閑鏈表刪除，也就不需要維護(hù)next指針了；用戶可以在8字節(jié)里存儲(chǔ)任何數(shù)據(jù)；

思考：假設(shè)調(diào)用 void*ptr=emalloc(8)分配了一塊內(nèi)存；調(diào)用efree(ptr)釋放內(nèi)存時(shí)，PHP如何知道這塊內(nèi)存的字節(jié)數(shù)呢？如何知道這塊內(nèi)存應(yīng)該插入哪個(gè)空閑鏈表呢？
思考1：第二章指出，任何內(nèi)存分配器都需要額外的數(shù)據(jù)結(jié)構(gòu)來標(biāo)志其管理的每一塊內(nèi)存：空閑/已分配，內(nèi)存大小等；PHP也不例外；可是我們發(fā)現(xiàn)使用emalloc(8)分配內(nèi)存時(shí)，其分配的就只是8字節(jié)的內(nèi)存，并沒有額外的空間來存儲(chǔ)這塊內(nèi)存的任何屬性；
思考2：觀察small內(nèi)存宏定義ZEND_MM_BINS_INFO；我們發(fā)現(xiàn)對(duì)于每一個(gè)page，其只可能被分配為同一種規(guī)格；不可能存在一部分分割為8字節(jié)大小，一部分分割為16字節(jié)大?。灰簿褪钦f每一個(gè)page的所有small內(nèi)存塊屬性是相同的；那么只需要記錄每一個(gè)page的屬性即可；
思考3：large內(nèi)存是同樣的思路；申請(qǐng)large內(nèi)存時(shí)，可能需要占若干個(gè)page的空間；但是同一個(gè)page只會(huì)屬于一個(gè)large內(nèi)存，不可能將一個(gè)page的一部分分給某個(gè)large內(nèi)存；
答案：不管page用于small內(nèi)存還是large內(nèi)存分配，只需要記錄每一個(gè)page的屬性即可，PHP將其記錄在zend_mm_chunk結(jié)構(gòu)體的zend_mm_page_info map[ZEND_MM_PAGES]字段；長度為512的int數(shù)組；對(duì)任一塊內(nèi)存，只要能計(jì)算出屬于哪一個(gè)頁，就能得到其屬性（內(nèi)存大小）；

2.2入口API

//內(nèi)存分配對(duì)外統(tǒng)一入口API為_emalloc；函數(shù)內(nèi)部直接調(diào)用zend_mm_alloc_heap，
//其第一個(gè)參數(shù)就是zend_mm_heap結(jié)構(gòu)體（全局只有一個(gè)），第二個(gè)參數(shù)就是請(qǐng)求分配內(nèi)存大小
void*  _emalloc(size_t size)
{
    return zend_mm_alloc_heap(AG(mm_heap), size);
}

//可以看出其根據(jù)請(qǐng)求內(nèi)存大小size判斷分配small內(nèi)存還是large內(nèi)存，還是huge內(nèi)存
static void *zend_mm_alloc_heap(zend_mm_heap *heap, size_t size)
{
    void *ptr;
 
    if (size <= ZEND_MM_MAX_SMALL_SIZE) {
        
        ptr = zend_mm_alloc_small(heap, size, ZEND_MM_SMALL_SIZE_TO_BIN(size));   
        //注意ZEND_MM_SMALL_SIZE_TO_BIN這個(gè)宏定義
        
        return ptr;
    } else if (size <= ZEND_MM_MAX_LARGE_SIZE) {
        ptr = zend_mm_alloc_large(heap, size);
        return ptr;
    } else {
        return zend_mm_alloc_huge(heap, size);
    }
}
 
 //使用到的宏定義如下
#define ZEND_MM_CHUNK_SIZE (2 * 1024 * 1024)               /* 2 MB  */
#define ZEND_MM_PAGE_SIZE  (4 * 1024)                      /* 4 KB  */
#define ZEND_MM_PAGES      (ZEND_MM_CHUNK_SIZE / ZEND_MM_PAGE_SIZE)  /* 512 */
#define ZEND_MM_FIRST_PAGE (1)
#define ZEND_MM_MAX_SMALL_SIZE      3072
#define ZEND_MM_MAX_LARGE_SIZE      (ZEND_MM_CHUNK_SIZE - (ZEND_MM_PAGE_SIZE * ZEND_MM_FIRST_PAGE))

2.3計(jì)算規(guī)格（bin_num）

我們發(fā)現(xiàn)在調(diào)用zend_mm_alloc_small時(shí)，使用到了ZEND_MM_SMALL_SIZE_TO_BIN，其定義了一個(gè)函數(shù)，用于將size轉(zhuǎn)換為bin_num；即請(qǐng)求7字節(jié)時(shí)，實(shí)際需要分配8字節(jié)，bin_num=1；請(qǐng)求37字節(jié)時(shí)，實(shí)際需要分配40字節(jié)，bin_num=4；即根據(jù)請(qǐng)求的size計(jì)算滿足條件的最小small內(nèi)存規(guī)格的bin_num；

#define ZEND_MM_SMALL_SIZE_TO_BIN(size)  zend_mm_small_size_to_bin(size)
 
static zend_always_inline int zend_mm_small_size_to_bin(size_t size)
{
 
    unsigned int t1, t2;
 
    if (size <= 64) {
        /* we need to support size == 0 ... */
        return (size - !!size) >> 3;
    } else {
        t1 = size - 1;
        t2 = zend_mm_small_size_to_bit(t1) - 3;
        t1 = t1 >> t2;
        t2 = t2 - 3;
        t2 = t2 << 2;
        return (int)(t1 + t2);
        //看到這一堆t1，t2，腦子里只有一個(gè)問題：我是誰，我在哪，這是啥；
    }
}

1）先分析size小于64情況：看看small內(nèi)存前8組大小定義，8，16，24，32，48，56，64；很簡單，就是等差數(shù)列，遞增8；所以對(duì)于每個(gè)size只要除以8就可以了（右移3位）；但是對(duì)于size=8，16，24，32，40，48，56，64這些值，需要size-1然后除以8才滿足；考慮到size=0的情況，于是有了(size - !!size) >> 3這個(gè)表達(dá)式；

2）當(dāng)size大于64時(shí)，情況就復(fù)雜了：small內(nèi)存的字節(jié)數(shù)變化為，64，80，96，112，128，160，192，224，256，320，384，448，512……；遞增16，遞增32，遞增64……；

還是先看看二進(jìn)制吧：

我們將size每4個(gè)分為一組，第一組比特序列長度為7，第二組比特序列長度為8，……；（即我們可以根據(jù)比特序列長度獲得sise屬于哪一組；思考一下，遞增16，32時(shí)，為什么只會(huì)加四次呢？）

那我們可以這么算：1）計(jì)算出size屬于第幾組；2）計(jì)算size在組內(nèi)的偏移量；3）計(jì)算組開始位置。思路就是這樣，但是計(jì)算方法并不統(tǒng)一，只要找規(guī)律計(jì)算出來即可。

//計(jì)算當(dāng)前size屬于哪一組；也就是計(jì)算比特序列長度；也就是計(jì)算最高位是1的位置；
 
//從低到高位查找也行，O(n)復(fù)雜度；使用二分查號(hào)，復(fù)雜度log（n）
 
//size最大為3072（不知道的回去看small內(nèi)存宏定義）；將size的二進(jìn)制看成16比特的序列；
//先按照8二分，再按照4或12二分，再按照2/6/10/16二分……
 
//思路：size與255比較（0xff）比較，如果小于，說明高8位全是0，只需要在低8位查找即可；
//…………
 
/* higher set bit number (0->N/A, 1->1, 2->2, 4->3, 8->4, 127->7, 128->8 etc) */
static zend_always_inline int zend_mm_small_size_to_bit(int size)
{
    int n = 16;
    if (size <= 0x00ff) {n -= 8; size = size << 8;}
    if (size <= 0x0fff) {n -= 4; size = size << 4;}
    if (size <= 0x3fff) {n -= 2; size = size << 2;}
    if (size <= 0x7fff) {n -= 1;}
    return n;
}

2.4開始分配了

前面說過small空閑內(nèi)存會(huì)形成鏈表，掛在zen_mm_heap字段free_slot[bin_num]上；

最初請(qǐng)求分配時(shí)，free_slot[bin_num]可能還沒有初始化，指向null；此時(shí)需要向chunk分配若干頁，將頁分割為大小相同的內(nèi)存塊，形成鏈表，掛在free_slot[bin_num]

static zend_always_inline void *zend_mm_alloc_small(zend_mm_heap *heap, size_t size, int bin_num)
{
    //空閑鏈表不為null，直接分配
    if (EXPECTED(heap->free_slot[bin_num] != NULL)) {
        zend_mm_free_slot *p = heap->free_slot[bin_num];
        heap->free_slot[bin_num] = p->next_free_slot;
        return (void*)p;
    } else {
    //先分配頁
        return zend_mm_alloc_small_slow(heap, bin_num;
    }
}

//分配頁；切割；形成鏈表
static zend_never_inline void *zend_mm_alloc_small_slow(zend_mm_heap *heap, uint32_t bin_num)
{
    zend_mm_chunk *chunk;
    int page_num;
    zend_mm_bin *bin;
    zend_mm_free_slot *p, *end;
 
    //分配頁（頁數(shù)目是small內(nèi)存宏定義第四列）；放在下一節(jié)large內(nèi)存分配講解
    bin = (zend_mm_bin*)zend_mm_alloc_pages(heap, bin_pages[bin_num]);
 
    if (UNEXPECTED(bin == NULL)) {
        /* insufficient memory */
        return NULL;
    }
     
    //之前提過任何內(nèi)存分配器都需要額外的數(shù)據(jù)結(jié)構(gòu)記錄每塊內(nèi)存的屬性；分析發(fā)現(xiàn)PHP每個(gè)page的所有內(nèi)存塊屬性都是相同的；且存儲(chǔ)在zend_mm_chunk結(jié)構(gòu)體的map字段（512個(gè)int）
    //bin即頁的首地址；需要計(jì)算bin是當(dāng)前chunk的第幾頁：1）得到chunk首地址；2）得到bin相對(duì)chunk首地址偏移量；3）除以頁大小
    chunk = (zend_mm_chunk*)ZEND_MM_ALIGNED_BASE(bin, ZEND_MM_CHUNK_SIZE);
    page_num = ZEND_MM_ALIGNED_OFFSET(bin, ZEND_MM_CHUNK_SIZE) / ZEND_MM_PAGE_SIZE;
     
    //記錄頁屬性；后面分析（對(duì)于分配的每個(gè)頁都要記錄屬性）
    chunk->map[page_num] = ZEND_MM_SRUN(bin_num);
    if (bin_pages[bin_num] > 1) {
        uint32_t i = 1;
 
        do {
            chunk->map[page_num+i] = ZEND_MM_NRUN(bin_num, i);
            i++;
        } while (i < bin_pages[bin_num]);
    }
 
    //切割內(nèi)存；形成鏈表（bin_data_size，bin_elements是上面介紹過的small內(nèi)存相關(guān)數(shù)組）
    end = (zend_mm_free_slot*)((char*)bin + (bin_data_size[bin_num] * (bin_elements[bin_num] - 1)));
    heap->free_slot[bin_num] = p = (zend_mm_free_slot*)((char*)bin + bin_data_size[bin_num]);
    do {
        p->next_free_slot = (zend_mm_free_slot*)((char*)p + bin_data_size[bin_num]);
        p = (zend_mm_free_slot*)((char*)p + bin_data_size[bin_num]);
    } while (p != end);
 
    /* terminate list using NULL */
    p->next_free_slot = NULL;
 
    /* return first element */
    return (char*)bin;
}

2.5說說記錄頁屬性的map

1）對(duì)任意地址p，如何計(jì)算頁號(hào)？

地址p減去chunk首地址獲得偏移量；偏移量除4K即可；問題是如何獲得chunk首地址？我們看看源碼：

chunk = (zend_mm_chunk*)ZEND_MM_ALIGNED_BASE(bin, ZEND_MM_CHUNK_SIZE);
page_num = ZEND_MM_ALIGNED_OFFSET(bin, ZEND_MM_CHUNK_SIZE) / ZEND_MM_PAGE_SIZE;
 
#define ZEND_MM_ALIGNED_OFFSET(size, alignment) 
    (((size_t)(size)) & ((alignment) - 1))
#define ZEND_MM_ALIGNED_BASE(size, alignment) 
    (((size_t)(size)) & ~((alignment) - 1))
#define ZEND_MM_SIZE_TO_NUM(size, alignment) 
    (((size_t)(size) + ((alignment) - 1)) / (alignment))

我們發(fā)現(xiàn)計(jì)算偏移量或chunk首地址時(shí)，需要兩個(gè)參數(shù)：size，地址p；alignment，調(diào)用時(shí)傳的是ZEND_MM_CHUNK_SIZE（2M）；

其實(shí)PHP在申請(qǐng)chunk時(shí)，額外添加了一個(gè)條件：chunk首地址2M字節(jié)對(duì)齊；

如圖，2M字節(jié)對(duì)齊時(shí)，給定任意地址p，p的低21位即地址p相對(duì)于chunk首地址的偏移量；

那如何保證chunk首地址2M字節(jié)對(duì)齊呢？分析源碼：

//chunk大小為size 2M；chunk首地址對(duì)齊方式 2M
static void *zend_mm_chunk_alloc_int(size_t size, size_t alignment)
{
    void *ptr = zend_mm_mmap(size);
 
    if (ptr == NULL) {
        return NULL;
    } else if (ZEND_MM_ALIGNED_OFFSET(ptr, alignment) == 0) { //2M對(duì)齊，直接返回
        return ptr;
    } else {
        size_t offset;
 
        //沒有2M對(duì)齊，先釋放，再重新分配2M+2M-4K空間
        //重新分配大小為2M+2M也是可以的（減4K是因?yàn)椴僮飨到y(tǒng)分配內(nèi)存按頁分配的，頁大小4k）
        //此時(shí)總能定位一段2M的內(nèi)存空間，且首地址2M對(duì)齊
        zend_mm_munmap(ptr, size);
        ptr = zend_mm_mmap(size + alignment - REAL_PAGE_SIZE);
 
        //分配了2M+2M-4K空間，需要釋放前面、后面部分空間。只保留中間按2M字節(jié)對(duì)齊的chunk即可
        offset = ZEND_MM_ALIGNED_OFFSET(ptr, alignment);
        if (offset != 0) {
            offset = alignment - offset;
            zend_mm_munmap(ptr, offset);
            ptr = (char*)ptr + offset;
            alignment -= offset;
        }
        if (alignment > REAL_PAGE_SIZE) {
            zend_mm_munmap((char*)ptr + size, alignment - REAL_PAGE_SIZE);
        }
        return ptr;
    }
}
//理論分析，申請(qǐng)2M空間，能直接2M字節(jié)對(duì)齊的概率很低；但是實(shí)驗(yàn)發(fā)現(xiàn)，概率還是蠻高的，這可能與內(nèi)核分配內(nèi)存有關(guān)；

2）每個(gè)頁都需要記錄哪些屬性？

chunk里的某個(gè)頁，可以分配為large內(nèi)存，large內(nèi)存連續(xù)占多少個(gè)頁；可以分配為small內(nèi)存，對(duì)應(yīng)的是哪種規(guī)格的small內(nèi)存（bin_num）

//29-31比特表示當(dāng)前頁分配為small還是large
//當(dāng)前頁用于large內(nèi)存分配
#define ZEND_MM_IS_LRUN                  0x40000000
//當(dāng)前頁用于small內(nèi)存分配
#define ZEND_MM_IS_SRUN                  0x80000000
 
//對(duì)于large內(nèi)存，0-9比特表示分配的頁數(shù)目
#define ZEND_MM_LRUN_PAGES_MASK          0x000003ff
#define ZEND_MM_LRUN_PAGES_OFFSET        0
 
//對(duì)于small內(nèi)存，0-4比特表示bin_num
#define ZEND_MM_SRUN_BIN_NUM_MASK        0x0000001f
#define ZEND_MM_SRUN_BIN_NUM_OFFSET      0
 
//count即large內(nèi)存占了多少個(gè)頁
#define ZEND_MM_LRUN(count)              (ZEND_MM_IS_LRUN | ((count) << ZEND_MM_LRUN_PAGES_OFFSET))
#define ZEND_MM_SRUN(bin_num)            (ZEND_MM_IS_SRUN | ((bin_num) << ZEND_MM_SRUN_BIN_NUM_OFFSET))

再回顧一下small內(nèi)存30種規(guī)格的宏定義，bin_num=16、17、20-29時(shí)，需要分配大于1個(gè)頁；此時(shí)不僅需要記錄bin_num，還需要記錄其對(duì)應(yīng)的頁數(shù)目

#define ZEND_MM_SRUN_BIN_NUM_MASK        0x0000001f
#define ZEND_MM_SRUN_BIN_NUM_OFFSET      0
 
#define ZEND_MM_SRUN_FREE_COUNTER_MASK   0x01ff0000
#define ZEND_MM_SRUN_FREE_COUNTER_OFFSET 16
 
#define ZEND_MM_NRUN_OFFSET_MASK         0x01ff0000
#define ZEND_MM_NRUN_OFFSET_OFFSET       16
 
//當(dāng)前頁分配為small內(nèi)存；0-4比特存儲(chǔ)bin_num；16-25存儲(chǔ)當(dāng)前規(guī)格需要分配的頁數(shù)目；
#define ZEND_MM_SRUN_EX(bin_num, count)  (ZEND_MM_IS_SRUN | ((bin_num) << ZEND_MM_SRUN_BIN_NUM_OFFSET) |
        ((count) << ZEND_MM_SRUN_FREE_COUNTER_OFFSET))
 
//29-31比特表示同時(shí)屬于small內(nèi)存和large內(nèi)存；0-4比特存儲(chǔ)bin_num；16-25存儲(chǔ)偏移量
//對(duì)于bin_num=29，需要分配3個(gè)頁，假設(shè)為10，11，12號(hào)頁
//map[10]=ZEND_MM_SRUN_EX(29,3);map[11]=ZEND_MM_NRUN(29,1);map[12]=ZEND_MM_NRUN(29,2);
#define ZEND_MM_NRUN(bin_num, offset)    (ZEND_MM_IS_SRUN | ZEND_MM_IS_LRUN | ((bin_num) << ZEND_MM_SRUN_BIN_NUM_OFFSET) |
        ((offset) << ZEND_MM_NRUN_OFFSET_OFFSET))

需要從chunk中查找連續(xù)pages_count個(gè)空閑的頁；zend_mm_chunk結(jié)構(gòu)體的free_map為512個(gè)比特，記錄著每個(gè)頁空閑還是已分配；

以64位機(jī)器為例，free_map又被分為8組；每組64比特，看作uint32_t類型；

#define ZEND_MM_CHUNK_SIZE (2 * 1024 * 1024)               /* 2 MB  */
#define ZEND_MM_PAGE_SIZE  (4 * 1024)                      /* 4 KB  */
#define ZEND_MM_PAGES      (ZEND_MM_CHUNK_SIZE / ZEND_MM_PAGE_SIZE)  /* 512 */
 
typedef zend_ulong zend_mm_bitset;    /* 4-byte or 8-byte integer */
 
#define ZEND_MM_BITSET_LEN      (sizeof(zend_mm_bitset) * 8)       /* 32 or 64 */
#define ZEND_MM_PAGE_MAP_LEN    (ZEND_MM_PAGES / ZEND_MM_BITSET_LEN) /* 16 or 8 */

static void *zend_mm_alloc_pages(zend_mm_heap *heap, uint32_t pages_count)
{
    //獲取main_chunk
    zend_mm_chunk *chunk = heap->main_chunk;
    uint32_t page_num, len;
    int steps = 0;
 
    //其實(shí)就是最佳適配算法
    while (1) {
        //free_pages記錄當(dāng)前chunk的空閑頁數(shù)目
        if (UNEXPECTED(chunk->free_pages < pages_count)) {
            goto not_found;
        } else {
            /* Best-Fit Search */
            int best = -1;
            uint32_t best_len = ZEND_MM_PAGES;
 
            //從free_tail位置開始，后面得頁都是空閑的
            uint32_t free_tail = chunk->free_tail;
            zend_mm_bitset *bitset = chunk->free_map;
            zend_mm_bitset tmp = *(bitset++);
            uint32_t i = 0;
            //從第一組開始遍歷；查找若干連續(xù)空閑頁；i實(shí)際每次遞增64；
            //最佳適配算法;查找到滿足條件的間隙，空閑頁數(shù)目大于pages_count；
            //best記錄間隙首位置；best_len記錄間隙空閑頁數(shù)目
            while (1) {
                //注意：(zend_mm_bitset)-1，表示將-1強(qiáng)制類型轉(zhuǎn)換為64位無符號(hào)整數(shù)，即64位全1（表示當(dāng)前組的頁全被分配了）
                while (tmp == (zend_mm_bitset)-1) {
                    i += ZEND_MM_BITSET_LEN;
                    if (i == ZEND_MM_PAGES) {
                        if (best > 0) {
                            page_num = best;
                            goto found;
                        } else {
                            goto not_found;
                        }
                    }
                    tmp = *(bitset++); //當(dāng)前組的所有頁都分配了，遞增到下一組
                }
                //每一個(gè)空閑間隙，肯定有若干個(gè)比特0，查找第一個(gè)比特0的位置：
                //假設(shè)當(dāng)前tmp=01111111（低7位全1，高位全0）；則zend_mm_bitset_nts函數(shù)返回8
                page_num = i + zend_mm_bitset_nts(tmp); 函數(shù)實(shí)現(xiàn)后面分析
                 
                //tmp+1->10000000;  tmp&(tmp+1)  其實(shí)就是把tmp的低8位全部置0，只保留高位
                tmp &= tmp + 1;
                 
                //如果此時(shí)tmp == 0，說明從第個(gè)頁page_num到當(dāng)前組最后一個(gè)頁，都是未分配的；
                //否則，需要找出這個(gè)空閑間隙另外一個(gè)0的位置，相減才可以得出空閑間隙頁數(shù)目
                while (tmp == 0) {
                    i += ZEND_MM_BITSET_LEN; //i+64,如果超出free_tail或者512，說明從page_num開始后面所有頁都是空閑的；否則遍歷下一組
                    if (i >= free_tail || i == ZEND_MM_PAGES) {
                        len = ZEND_MM_PAGES - page_num;
                        if (len >= pages_count && len < best_len) {   //從page_num處開始后面頁都空閑，且剩余頁數(shù)目小于已經(jīng)查找到的連續(xù)空閑頁數(shù)目，直接分配
                            chunk->free_tail = page_num + pages_count;
                            goto found;
                        } else {  //當(dāng)前空閑間隙頁不滿足條件
                              
                            chunk->free_tail = page_num;
                            if (best > 0) { //之前有查找到空閑間隙符合分配條件
                                page_num = best;
                                goto found;
                            } else {  //之前沒有查找到空閑頁滿足條件，說明失敗
                                goto not_found;
                            }
                        }
                    }
                    tmp = *(bitset++); //遍歷下一組
                }
                 
                //假設(shè)最初tmp=1111000001111000111111，tmp&=tmp+1后，tmp=1111000001111000 000000
                //上面while循環(huán)進(jìn)不去；且page_num=7+i；
                //此時(shí)需從低到高位查找第一個(gè)1比特位置，為11，11+i-（7+i）=4，即是連續(xù)空閑頁數(shù)目
                len = i + zend_ulong_ntz(tmp) - page_num;
                if (len >= pages_count) { //滿足分配條件，記錄
                    if (len == pages_count) {
                        goto found;
                    } else if (len < best_len) {
                        best_len = len;
                        best = page_num;
                    }
                }
                 
                //上面計(jì)算后tmp=1111000001111000 000000；發(fā)現(xiàn)這一組還有一個(gè)空閑間隙，擁有5個(gè)空閑頁，下一個(gè)循環(huán)肯定需要查找出來；
                //而目前低10比特其實(shí)已經(jīng)查找過了，那么需要將低10比特全部置1，以防再次查找到；
                //tmp-1:1111000001110111 111111; tmp |= tmp - 1:1111000001111111 111111
                tmp |= tmp - 1;
            }
        }
 
not_found:
        ………………
found:
     
    //查找到滿足條件的連續(xù)頁，設(shè)置從page_num開始pages_count個(gè)頁為已分配
    chunk->free_pages -= pages_count;
    zend_mm_bitset_set_range(chunk->free_map, page_num, pages_count);
    //標(biāo)志當(dāng)前頁用于large內(nèi)存分配，分配數(shù)目為pages_count
    chunk->map[page_num] = ZEND_MM_LRUN(pages_count);
    //更新free_tail
    if (page_num == chunk->free_tail) {
        chunk->free_tail = page_num + pages_count;
    }
    //返回當(dāng)前第一個(gè)page的首地址
    return ZEND_MM_PAGE_ADDR(chunk, page_num);
}
 
//4K大小的字節(jié)數(shù)組
struct zend_mm_page {
    char               bytes[ZEND_MM_PAGE_SIZE];
};
 
//偏移page_num*4K
#define ZEND_MM_PAGE_ADDR(chunk, page_num) 
    ((void*)(((zend_mm_page*)(chunk)) + (page_num)))

看看PHP是如何高效查找0比特位置的：依然是二分查找

static zend_always_inline int zend_mm_bitset_nts(zend_mm_bitset bitset)
{
    int n=0;
//64位機(jī)器才會(huì)執(zhí)行
#if SIZEOF_ZEND_LONG == 8
    if (sizeof(zend_mm_bitset) == 8) {
        if ((bitset & 0xffffffff) == 0xffffffff) {n += 32; bitset = bitset >> Z_UL(32);}
    }
#endif
    if ((bitset & 0x0000ffff) == 0x0000ffff) {n += 16; bitset = bitset >> 16;}
    if ((bitset & 0x000000ff) == 0x000000ff) {n +=  8; bitset = bitset >>  8;}
    if ((bitset & 0x0000000f) == 0x0000000f) {n +=  4; bitset = bitset >>  4;}
    if ((bitset & 0x00000003) == 0x00000003) {n +=  2; bitset = bitset >>  2;}
    return n + (bitset & 1);
}

//
#define ZEND_MM_ALIGNED_SIZE_EX(size, alignment) 
    (((size) + ((alignment) - Z_L(1))) & ~((alignment) - Z_L(1)))
 
//會(huì)將size擴(kuò)展為2M字節(jié)的整數(shù)倍；直接調(diào)用分配chunk的函數(shù)申請(qǐng)內(nèi)存
//huge內(nèi)存以n*2M字節(jié)對(duì)齊的
static void *zend_mm_alloc_huge(zend_mm_heap *heap, size_t size)
{
    size_t new_size = ZEND_MM_ALIGNED_SIZE_EX(size, MAX(REAL_PAGE_SIZE, ZEND_MM_CHUNK_SIZE));
     
    void *ptr = zend_mm_chunk_alloc(heap, new_size, ZEND_MM_CHUNK_SIZE);
    return ptr;
}

ZEND_API void ZEND_FASTCALL _efree(void *ptr)
{
    zend_mm_free_heap(AG(mm_heap), ptr);
}
 
static zend_always_inline void zend_mm_free_heap(zend_mm_heap *heap, void *ptr)
{
    //計(jì)算當(dāng)前地址ptr相對(duì)于chunk的偏移
    size_t page_offset = ZEND_MM_ALIGNED_OFFSET(ptr, ZEND_MM_CHUNK_SIZE);
 
    //偏移為0，說明是huge內(nèi)存，直接釋放
    if (UNEXPECTED(page_offset == 0)) {
        if (ptr != NULL) {
            zend_mm_free_huge(heap, ptr);
        }
    } else {
        //計(jì)算chunk首地址
        zend_mm_chunk *chunk = (zend_mm_chunk*)ZEND_MM_ALIGNED_BASE(ptr, ZEND_MM_CHUNK_SIZE);
        //計(jì)算頁號(hào)
        int page_num = (int)(page_offset / ZEND_MM_PAGE_SIZE);
        //獲得頁屬性信息
        zend_mm_page_info info = chunk->map[page_num];
 
        //small內(nèi)存
        if (EXPECTED(info & ZEND_MM_IS_SRUN)) {
            zend_mm_free_small(heap, ptr, ZEND_MM_SRUN_BIN_NUM(info));
        }
        //large內(nèi)存
        else /* if (info & ZEND_MM_IS_LRUN) */ {
            int pages_count = ZEND_MM_LRUN_PAGES(info);
             //將頁標(biāo)記為空閑
            zend_mm_free_large(heap, chunk, page_num, pages_count);
        }
    }
}

static zend_always_inline void zend_mm_free_small(zend_mm_heap *heap, void *ptr, int bin_num)
{
    zend_mm_free_slot *p;
    //插入空閑鏈表頭部即可
    p = (zend_mm_free_slot*)ptr;
    p->next_free_slot = heap->free_slot[bin_num];
    heap->free_slot[bin_num] = p;
}

PHP有一個(gè)全局唯一的zend_mm_heap，其是zend_mm_chunk一個(gè)字段；

zend_mm_chunk至少需要空間2k+；和zend_mm_chunk存儲(chǔ)在哪里？

這兩個(gè)結(jié)構(gòu)體其實(shí)是存儲(chǔ)在chunk的第一個(gè)頁，即chunk的第一個(gè)頁始終是分配的，且用戶不能申請(qǐng)的；

申請(qǐng)的多個(gè)chunk之間是形成雙向鏈表的；如下圖所示：

static zend_mm_heap *zend_mm_init(void)
{
    //將分配的2M空間，強(qiáng)制轉(zhuǎn)換為zend_mm_chunk*；并初始化zend_mm_chunk結(jié)構(gòu)體
    zend_mm_chunk *chunk = (zend_mm_chunk*)zend_mm_chunk_alloc_int(ZEND_MM_CHUNK_SIZE, ZEND_MM_CHUNK_SIZE);
    zend_mm_heap *heap;
 
    heap = &chunk->heap_slot;
    chunk->heap = heap;
    chunk->next = chunk;
    chunk->prev = chunk;
    chunk->free_pages = ZEND_MM_PAGES - ZEND_MM_FIRST_PAGE;
    chunk->free_tail = ZEND_MM_FIRST_PAGE;
    chunk->num = 0;
    chunk->free_map[0] = (Z_L(1) << ZEND_MM_FIRST_PAGE) - 1;
    chunk->map[0] = ZEND_MM_LRUN(ZEND_MM_FIRST_PAGE);
    heap->main_chunk = chunk;
    heap->cached_chunks = NULL;
    heap->chunks_count = 1;
    heap->peak_chunks_count = 1;
    heap->cached_chunks_count = 0;
    heap->avg_chunks_count = 1.0;
    heap->last_chunks_delete_boundary = 0;
    heap->last_chunks_delete_count = 0;
    heap->huge_list = NULL;
    return heap;
}

PHP虛擬機(jī)什么時(shí)候初始化內(nèi)管理器呢？heap與chunk又是什么時(shí)候初始化呢？
下圖為PHP內(nèi)存管理器初始化流程；
有興趣同學(xué)可以在相關(guān)函數(shù)處加斷點(diǎn)，跟蹤內(nèi)存管理器初始化流程；

1）需要明白一點(diǎn)：任何內(nèi)存分配器都需要額外的數(shù)據(jù)結(jié)構(gòu)來記錄內(nèi)存的分配情況；

2）內(nèi)存池是代替直接調(diào)用malloc/free、new/delete進(jìn)行內(nèi)存管理的常用方法；內(nèi)存池中空閑內(nèi)存塊組織為鏈表結(jié)果，申請(qǐng)內(nèi)存只需要查找空閑鏈表即可，釋放內(nèi)存需要將內(nèi)存塊重新插入空閑鏈表；

3）PHP采用預(yù)分配內(nèi)存策略，提前向操作系統(tǒng)分配2M字節(jié)大小內(nèi)存，稱為chunk；同時(shí)將內(nèi)存分配請(qǐng)求根據(jù)字節(jié)大小分為small、huge、large三種；

4）small內(nèi)存，采用“分離存儲(chǔ)”思想；將空閑內(nèi)存塊按照字節(jié)大小組織為多個(gè)空閑鏈表；

5）large內(nèi)存每次回分配連續(xù)若干個(gè)頁，采用最佳適配算法；

6）huge內(nèi)存直接使用mmap函數(shù)向操作系統(tǒng)申請(qǐng)內(nèi)存（申請(qǐng)大小是2M字節(jié)整數(shù)倍）；

7）chunk中的每個(gè)頁只會(huì)被切割為相同規(guī)格的內(nèi)存塊；所以不需要再每個(gè)內(nèi)存塊添加頭部，只需要記錄每個(gè)頁的屬性即可；

8）如何方便根據(jù)地址計(jì)算當(dāng)前內(nèi)存塊屬于chunk中的哪一個(gè)頁？PHP分配的chunk都是2M字節(jié)對(duì)齊的，任意地址的低21位即是相對(duì)chunk首地址，除以頁大小則可獲得頁號(hào)；

本文首先簡單介紹了計(jì)算機(jī)操作系統(tǒng)內(nèi)存相關(guān)知識(shí)，然后描述了malloc內(nèi)存分配器設(shè)計(jì)思路，以及內(nèi)存池的簡單理論；最后從源碼層面詳細(xì)分析了PHP內(nèi)存管理器的實(shí)現(xiàn)；相信通過這篇文章，大家對(duì)內(nèi)存管理頁有了一定的了解；
對(duì)于PHP源碼有興趣的同學(xué)，歡迎加入我們的微信群，我們可以一起探討與學(xué)習(xí)；

同時(shí)歡迎關(guān)注微博：