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

作者： 順風車運營研發(fā)團隊 李樂

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

虛擬頁的集合就稱為頁表（pageTable），頁表就是一個頁表條目（page table entry）的數(shù)組；每個頁表條目都包含有效位標志，記錄當前虛擬頁是否分配，當前虛擬頁的訪問控制權限；同時包含物理頁號或磁盤地址；

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

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

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

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

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

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

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

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

3）hugePage

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

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

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

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

當我們訪問虛擬地址時，內(nèi)核會遍歷vm_area_struct鏈表，根據(jù)vm_start和vm_end能夠判斷地址合法性；根據(jù)vm_por能夠判斷地址訪問的合法性；
遍歷鏈表時間性能較差，內(nèi)核會將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)建一個新的虛擬內(nèi)存區(qū)域（注意是新的區(qū)域，和堆是平級關系，即mmap函數(shù)并不是在堆上分配內(nèi)存的，）；最好是從地址addr開始（一般傳null），并將文件描述fd符指定的對象的一個連續(xù)的chunk（大小為len，從文件偏移offset開始）映射到這個新的區(qū)域；當fd傳-1時，可用于申請分配內(nèi)存；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.1結構體

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

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

//省略了結構體中很多字段
struct _zend_mm_heap {
    //統(tǒng)計
    size_t             size;                    /* current memory usage */
    size_t             peak;                    /* peak memory usage */
    //由于“預分配”方案，實際使用內(nèi)存和向操作系統(tǒ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會分配若干chunk，記錄當前主chunk首地址
    zend_mm_chunk     *main_chunk;
     
    //統(tǒng)計chunk數(shù)目
    int                chunks_count;            /* number of alocated chunks */
    int                peak_chunks_count;       /* peak number of allocated chunks for current request */ 
}

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

struct _zend_mm_chunk {
    //指向heap
    zend_mm_heap      *heap;
    //chunk組織為雙向鏈表
    zend_mm_chunk     *next;
    zend_mm_chunk     *prev;
    //當前chunk空閑page數(shù)目
    uint32_t           free_pages;              /* number of free pages */
    //當前chunk最后一個空閑的page位置
    uint32_t           free_tail;               /* number of free pages at the end of chunk */
    //每當申請一個新的chunk時，這個chunk的num會遞增
    uint32_t           num;
    //預留
    char               reserve[64 - (sizeof(void*) * 3 + sizeof(uint32_t) * 3)];
    //指向heap，只有main_chunk使用
    zend_mm_heap       heap_slot;               /* used only in main chunk */
    //記錄512個page的分配情況；0代表空閑，1代表已分配
    zend_mm_page_map   free_map;                /* 512 bits or 64 bytes */
    //記錄每個page的詳細信息，
    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結構體的free_slot數(shù)組上；
30種規(guī)格內(nèi)存如下：

//宏定義：第一列表示序號（稱之為bin_num），第二列表示每個small內(nèi)存的大小（字節(jié)數(shù)）；
//第四列表示每次獲取多少個page；第三列表示將page分割為多少個大小為第一列的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 */

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

上一節(jié)提到PHP將small內(nèi)存分為30種不同大小的規(guī)格；
每種大小規(guī)格的空閑內(nèi)存會組織為鏈表，掛在數(shù)組_zend_mm_heap結構體的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)存鏈表的每個節(jié)點都是一個zend_mm_free_slot結構體，其只有一個next指針字段；

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

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

2.2入口API

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

//可以看出其根據(jù)請求內(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這個宏定義
        
        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計算規(guī)格（bin_num）

我們發(fā)現(xiàn)在調(diào)用zend_mm_alloc_small時，使用到了ZEND_MM_SMALL_SIZE_TO_BIN，其定義了一個函數(shù)，用于將size轉換為bin_num；即請求7字節(jié)時，實際需要分配8字節(jié)，bin_num=1；請求37字節(jié)時，實際需要分配40字節(jié)，bin_num=4；即根據(jù)請求的size計算滿足條件的最小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，腦子里只有一個問題：我是誰，我在哪，這是啥；
    }
}

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

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

還是先看看二進制吧：

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

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

//計算當前size屬于哪一組；也就是計算比特序列長度；也就是計算最高位是1的位置；
 
//從低到高位查找也行，O(n)復雜度；使用二分查號，復雜度log（n）
 
//size最大為3072（不知道的回去看small內(nèi)存宏定義）；將size的二進制看成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)存會形成鏈表，掛在zen_mm_heap字段free_slot[bin_num]上；

最初請求分配時，free_slot[bin_num]可能還沒有初始化，指向null；此時需要向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ù)結構記錄每塊內(nèi)存的屬性；分析發(fā)現(xiàn)PHP每個page的所有內(nèi)存塊屬性都是相同的；且存儲在zend_mm_chunk結構體的map字段（512個int）
    //bin即頁的首地址；需要計算bin是當前chunk的第幾頁：1）得到chunk首地址；2）得到bin相對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;
     
    //記錄頁屬性；后面分析（對于分配的每個頁都要記錄屬性）
    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)存相關數(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）對任意地址p，如何計算頁號？

地址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)計算偏移量或chunk首地址時，需要兩個參數(shù)：size，地址p；alignment，調(diào)用時傳的是ZEND_MM_CHUNK_SIZE（2M）；

其實PHP在申請chunk時，額外添加了一個條件：chunk首地址2M字節(jié)對齊；

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

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

//chunk大小為size 2M；chunk首地址對齊方式 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對齊，直接返回
        return ptr;
    } else {
        size_t offset;
 
        //沒有2M對齊，先釋放，再重新分配2M+2M-4K空間
        //重新分配大小為2M+2M也是可以的（減4K是因為操作系統(tǒng)分配內(nèi)存按頁分配的，頁大小4k）
        //此時總能定位一段2M的內(nèi)存空間，且首地址2M對齊
        zend_mm_munmap(ptr, size);
        ptr = zend_mm_mmap(size + alignment - REAL_PAGE_SIZE);
 
        //分配了2M+2M-4K空間，需要釋放前面、后面部分空間。只保留中間按2M字節(jié)對齊的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;
    }
}
//理論分析，申請2M空間，能直接2M字節(jié)對齊的概率很低；但是實驗發(fā)現(xiàn)，概率還是蠻高的，這可能與內(nèi)核分配內(nèi)存有關；

2）每個頁都需要記錄哪些屬性？

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

//29-31比特表示當前頁分配為small還是large
//當前頁用于large內(nèi)存分配
#define ZEND_MM_IS_LRUN                  0x40000000
//當前頁用于small內(nèi)存分配
#define ZEND_MM_IS_SRUN                  0x80000000
 
//對于large內(nèi)存，0-9比特表示分配的頁數(shù)目
#define ZEND_MM_LRUN_PAGES_MASK          0x000003ff
#define ZEND_MM_LRUN_PAGES_OFFSET        0
 
//對于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)存占了多少個頁
#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時，需要分配大于1個頁；此時不僅需要記錄bin_num，還需要記錄其對應的頁數(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
 
//當前頁分配為small內(nèi)存；0-4比特存儲bin_num；16-25存儲當前規(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比特表示同時屬于small內(nèi)存和large內(nèi)存；0-4比特存儲bin_num；16-25存儲偏移量
//對于bin_num=29，需要分配3個頁，假設為10，11，12號頁
//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個空閑的頁；zend_mm_chunk結構體的free_map為512個比特，記錄著每個頁空閑還是已分配；

以64位機器為例，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;
 
    //其實就是最佳適配算法
    while (1) {
        //free_pages記錄當前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實際每次遞增64；
            //最佳適配算法;查找到滿足條件的間隙，空閑頁數(shù)目大于pages_count；
            //best記錄間隙首位置；best_len記錄間隙空閑頁數(shù)目
            while (1) {
                //注意：(zend_mm_bitset)-1，表示將-1強制類型轉換為64位無符號整數(shù)，即64位全1（表示當前組的頁全被分配了）
                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++); //當前組的所有頁都分配了，遞增到下一組
                }
                //每一個空閑間隙，肯定有若干個比特0，查找第一個比特0的位置：
                //假設當前tmp=01111111（低7位全1，高位全0）；則zend_mm_bitset_nts函數(shù)返回8
                page_num = i + zend_mm_bitset_nts(tmp); 函數(shù)實現(xiàn)后面分析
                 
                //tmp+1->10000000;  tmp&(tmp+1)  其實就是把tmp的低8位全部置0，只保留高位
                tmp &= tmp + 1;
                 
                //如果此時tmp == 0，說明從第個頁page_num到當前組最后一個頁，都是未分配的；
                //否則，需要找出這個空閑間隙另外一個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 {  //當前空閑間隙頁不滿足條件
                              
                            chunk->free_tail = page_num;
                            if (best > 0) { //之前有查找到空閑間隙符合分配條件
                                page_num = best;
                                goto found;
                            } else {  //之前沒有查找到空閑頁滿足條件，說明失敗
                                goto not_found;
                            }
                        }
                    }
                    tmp = *(bitset++); //遍歷下一組
                }
                 
                //假設最初tmp=1111000001111000111111，tmp&=tmp+1后，tmp=1111000001111000 000000
                //上面while循環(huán)進不去；且page_num=7+i；
                //此時需從低到高位查找第一個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;
                    }
                }
                 
                //上面計算后tmp=1111000001111000 000000；發(fā)現(xiàn)這一組還有一個空閑間隙，擁有5個空閑頁，下一個循環(huán)肯定需要查找出來；
                //而目前低10比特其實已經(jīng)查找過了，那么需要將低10比特全部置1，以防再次查找到；
                //tmp-1:1111000001110111 111111; tmp |= tmp - 1:1111000001111111 111111
                tmp |= tmp - 1;
            }
        }
 
not_found:
        ………………
found:
     
    //查找到滿足條件的連續(xù)頁，設置從page_num開始pages_count個頁為已分配
    chunk->free_pages -= pages_count;
    zend_mm_bitset_set_range(chunk->free_map, page_num, pages_count);
    //標志當前頁用于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;
    }
    //返回當前第一個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位機器才會執(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)))
 
//會將size擴展為2M字節(jié)的整數(shù)倍；直接調(diào)用分配chunk的函數(shù)申請內(nèi)存
//huge內(nèi)存以n*2M字節(jié)對齊的
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)
{
    //計算當前地址ptr相對于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 {
        //計算chunk首地址
        zend_mm_chunk *chunk = (zend_mm_chunk*)ZEND_MM_ALIGNED_BASE(ptr, ZEND_MM_CHUNK_SIZE);
        //計算頁號
        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);
             //將頁標記為空閑
            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有一個全局唯一的zend_mm_heap，其是zend_mm_chunk一個字段；

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

這兩個結構體其實是存儲在chunk的第一個頁，即chunk的第一個頁始終是分配的，且用戶不能申請的；

申請的多個chunk之間是形成雙向鏈表的；如下圖所示：

static zend_mm_heap *zend_mm_init(void)
{
    //將分配的2M空間，強制轉換為zend_mm_chunk*；并初始化zend_mm_chunk結構體
    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虛擬機什么時候初始化內(nèi)管理器呢？heap與chunk又是什么時候初始化呢？
下圖為PHP內(nèi)存管理器初始化流程；
有興趣同學可以在相關函數(shù)處加斷點，跟蹤內(nèi)存管理器初始化流程；

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

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

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

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

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

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

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

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

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

同時歡迎關注微博：