第三章 System Part3（3.3.2）

(2)unreal3的內存分配

上一個debug模式下的分配器，做到了定位和查找內存泄漏，統計內存分配情況。那麼release模式下就是加快內存的分配和釋放。我看過一些開源的內存分配器，一般管理內存分配有三種機制，一個是典型的空間換時間，就是一個內存塊A，我分成相等的小塊，根據某種機制正好要在這個A裡面分配，那麼不管A分成的小塊多出要申請的size多少，都要拿出一個小塊。比如我一個內存塊是40，我分成4塊，每個大小是10.我現在要分配6，那麼取出一個小塊，多出那個4就要被浪費掉了，這種機制分配釋放都很快，因為這種方法內存塊是等大的，可以做類似數組並用索引方式找出來，申請釋放，但它浪費了一些不必要的空間。還有一種機制就是申請多大就分多大的，然後用鏈表或者樹結構管理，這種機制經過多次申請釋放會有很多碎片是不可用的，要花時間去合併碎片，並且申請和釋放要去查找，比較浪費時間。說實話只有unreal3的內存分配是一種相對完美的辦法，值得仔細的來講一講，有少量的內存浪費，但速度快，它的演算法很巧妙，所以讀懂它並不是那麼容易，接下來我盡量圖文並茂的把它說清楚，讓大家都能理解它的工作原理。

其實unreal3的內存分配有點和Windows操作系統管理虛擬內存方式差不多。

a暴風雨來臨的前奏

不知道你是否還記得在上一個章節中，我做了一項內存統計，就是以2的n次冪的形式統計一個遊戲在運行過程中內存分配的大小（這裡要強調下是遊戲程序，不同的非遊戲程序統計的結果不太一樣）。在遊戲中，小於1k的動態分配數據是最頻繁的，而且越小越頻繁。相反越大的數據，例如模型VB、IB、texture數據等等吧，這些申請和釋放頻率比較低，大多數動態分配時間都浪費到小數據的申請和釋放上。所以上面的數據統計其實就是這個目的，讓你知道遊戲程序分配頻率最高的都是集中在那一個區域。

UE3就是利用windows操作系統的特性完美的運用了上面提到的兩種機制。申請小於MAXSIZE，就用這種機制管理；申請大於MAXSIZE的，就直接分配，因為大內存申請釋放不頻繁，小內存申請釋放很頻繁，管理起來才更有意義。

從現在開始你一定要集中注意力，我要放大招了，哈哈！

根據上面我說的這些，你應該知道unreal3內存分配大體要用什麼方法，並且為什麼和windows操作系統有關，準確的說是32位操作系統。

Windows操作系統下面有幾個重要的概念需要大家明確，這個你搞不懂，後面很難理解。

先說物理內存和虛擬內存：

大家都知道在32位windows操作系統（以下簡稱win32）中指針是32位的，也就是說虛擬內存最大定址空間是4GB,不管你真實的內存夠不夠4GB，它都會虛擬映射成4GB，不夠的用硬碟來回調度。

這裡說的真實的內存就是我說的物理內存，也就是你買的內存條真實的大小。Win32每次分配的最小虛擬空間為4kb（也叫頁面），其實你在win32下申請空間，分配大小都是4kb對齊的，你申請的不足4kb也給你分配4kb，這樣其實浪費了很多空間。Win32下分配粒度是64kb，win32每次分配給一個進程的空間都是64kb為單位的，這也就保證了如果同一個進程的兩個指針高16位如果相同，那麼他們肯定在同一個分配粒度里。當你進程啟動第一次申請空間的時候，如果申請是3kb，win32也會拿出64kb空間給這個進程，這64kb裡面有16個4kb，也就是16個頁面，它給你一個頁面來使用，當然這頁面要有1kb被浪費掉，其餘15個頁面先留著，如果你再申請的時候，再給你用，如果你釋放這3bk，也就是還給了win32，下次還可以使用，這裡面哪些被使用哪些沒被使用，怎麼分配給你都是win32有一套機制再管理。

上面所說的分配空間不是指咱們經常用的malloc和new函數，而是win32下提供的API函數VirtualAlloc, 是window用虛擬內存和物理內存建立聯繫的函數，上面提到的都是它的分配規則，這個函數是最底層的函數，而malloc和new是語言層面。

大學裡面大家都學過操作系統課程，管理物理內存是操作系統的重要任務，虛擬內存的方法保證了在物理內存不夠的情況下，能夠跑多個進程。多任務的win32系統，如果你只有一個CPU，你也可以邊看網頁，邊聽歌，同一個CPU執行2個進程，這是win32並發過程；如果你有兩個CPU，一個CPU用來看網頁，一個CPU用來聽歌，這是win32的並行過程。無論是並發還是並行，在物理內存有限的情況下，並不是每個進程每時每刻物理內存都被佔用，優先順序高的或者活躍的進程會得到多的物理內存資源，而其他優先順序低或者不活躍的被掛起等待，在物理內存不夠的情況下，它內存的數據被暫時保存在硬碟裡面，一旦喚醒運行，就把當時保存在硬碟裡面的數據還原會到內存中。即使就一個進程申請的內存超過了真實的物理內存，win32也會用這種策略，把不常用的放到硬碟上，來回的調度。至於win32如何管理CPU、管理物理內存和虛擬內存關係的，恐怕要看到它的代碼才能知道了，不過好在linux和antroid是開源的，大家可以看看了解下。

Win32提供幾個管理虛擬內存和真實物理內存函數，比如你可以申請虛擬內存空間，但不分配真實物理內存，當你真正要使用的時候再由系統分配，你還可以鎖定物理內存，不被其他進程使用。

下面再說堆：

堆大家都不陌生，這裡簡單提一下，一般我們編程存在5種類型的數據：局部變數、常量、全局變數 、靜態變數，動態內存空間。局部變數是在棧空間；常量、全局變數、靜態變數在程序的數據區域，在編譯階段就已經確定；動態內存空間在一個區域，就是我們所說的堆。一般操作系統有規定棧的空間大小，都是分配粒度的整數倍，同理靜態數據區域也是分配粒度的整數倍，所以剩下的動態分配空間也是分配粒度整數倍。

動態分配的空間（後面都用「堆」代替）其實調用底層的VirtualAlloc，但因為VirtualAlloc分配規則都是4kb對齊，並且以分配粒度64kb為單位，如果沒有一套好的內存演算法，一般人都用不好VirtualAlloc這個函數，於是window又誕生了堆的幾個函數HeapCreate、HeapAlloc。為了減少空間浪費，堆的管理演算法為用戶提供方便內存分配使用，而我們最常用的new和malloc則是調用的HeapCreate和HeapAlloc，至於你掉用free和delete釋放內存，其實未必真的把物理內存給釋放了。至於win32怎麼管理的，用什麼數據結構，它沒開源也無從考證。

大家如果想詳細了解，堆和虛擬內存可以訪問下面微軟MSDN地址：

https://msdn.microsoft.com/en-us/library/aa366711(v=vs.85).aspx

https://msdn.microsoft.com/en-us/library/aa366916(v=vs.85).aspx

裡面提到了一些關於win32系統知識，具體細節我還建議大家讀一讀圖3.4那本《window核心編程第5版》，裡面講的很詳細，什麼虛擬內存了，哪些地址空間給系統用，哪些地址空間給用戶用，進程之間的調度，windows是如何管理內存和磁碟的，等等吧。上面說到的頁面大小是由cpu決定的，不同cpu可以不同，分配粒度是由操作系統定的，這本書裡面都有講。

圖3.15表示了頁面和分配粒度的關係，紅色部分是內存已經被佔用的，其中16個4bk頁面，裡面有些被全部佔用，有些被部分佔用，有些沒有被佔用。被全佔用的可能是分配的時候正好4bk，也可能是大於4kb；部分佔用的，申請的空間肯定不是4kb的倍數導致的；沒有被佔用的，可能是釋放歸還的，也可能是剩下的幾個頁面不夠申請導致，分配到下一個粒度上。虛擬內存分配方式，它根本不管碎片的，而堆管理是盡量去減少碎片，但來回的分配和釋放，難免有大量碎片，但win32也不去合併它們。多個分配粒度在內存肯定是不可能都連續的，win32簡單管理辦法就是大於64kb的肯定要連續，小於64kb沒必要連續，這樣用戶訪問的時候不會出錯，否則win32還要維護一套機制，處理邏輯上連續，實際上不連續情況，這種也十分麻煩。

圖3.15 頁面與分配粒度

b關鍵性的比喻

現在我假設，記住是假設，經過一系列的統計，每次申請的大小大約在1kb-2kb之間，如果每次都用默認的win32來分配，它每次都會給我分配4kb，這樣每次至少都有2kb的內存就要被浪費掉，如果這樣的申請達到1000次，那麼大約2M的內存就被浪費。

好了，為了不浪費內存，我一次性向win32申請足夠大內存M，如果不夠大，我再申請M, 這個M究竟要多大呢？至少是4kb的整數倍，例如我申請個10kb，win32要給我分配12kb，浪費了2kb。其次要是2的n次冪，如果有內存要釋放，這樣我可以很快的定位到，這段內存在我預分配好的空間的位置(後面會詳細講)。你不能把M設的太小，否則頻繁申請，也不能設置太大，否則也用不了會產生浪費，這個就是一個經驗數字了，那麼我就取個32kb，大家想一想這個內存分配演算法要怎麼寫呢？其實方法很多，我這裡介紹一種，我認為實現複雜度算是比較簡單的。

首先我定義2個數據結構 ：

//鏈表struct PoolInfo{ PoolInfo * Pre; //指向自己前一個節點 PoolInfo * Next; //指向自己的後一個節點 PoolTable * Owner; //屬於哪個鏈表管理者 void * Mem; //指向win32分配空間的首地址 unsigned int Taken; //每分配一次就加1，釋放一次就減1，如果釋放後為0，那麼就把Mem指向的內存空間還給win32 佔位4個位元組，具體用法後面揭曉 //這4個位元組用途我現在還不想揭示出來，後面我再給出};//鏈表管理類struct PoolTable{ unsigned int TableSize; //每個分配單元的大小 PoolInfo * ExhaustedPool; //分配滿的poolinfo鏈表頭指針 PoolInfo * FirstPool; //沒有分配滿的poolinfo鏈表的頭指針};

看到這2個結構，大家大概能知道應該是一個什麼樣的方式，我現在把示意圖給大家貼出來，大家會更加直觀了。

圖3.16 複雜示意圖

圖3.17 簡單示意圖

結合這2張圖我想大家應該能知道個所以然。PoolTable管理2個PoolInfo鏈表，PoolInfo * FirstPool是沒有分配完的，PoolInfo * ExhaustedPool是分配完的。PoolInfo而裡面維護了鏈表的前後指針和win32分配的內存空間地址void * Mem，而且還有指向所屬的PoolTable——PoolTable * Owner。每次分配的大小就是上面咱們規定的32kb，而每個PoolInfo裡面又分配了很多小塊，因為上面假設分配大小都在1kb-2kb之間，所以每個小塊大小都分配2kb。PoolTable裡面的unsigned int TableSize就是2kb（2048）。

大家應該對所有的一切有了進一步的了解了。咱們繼續，在極限的情況下，win32下定址4G空間，可以申請到的內存是4G，但其實看過windows核心編程的人都知道win32一般會拿出2G的定址空間給應用程序，如果開啟了3GB模式，會拿出3GB空間給應用程序。根據《windows核心編程》裡面介紹win32下用戶可用的定址空間是0x00010000——0xBFFEFFFF算了一下其實是3145600kb，不到3G。上面給出的例子中，我們只知道用戶申請大小在1kb-2kb之間，但是總共要申請多大，我們不知道，所以就要按照最大3G空間來申請分配。一個PoolInfo管理32kb，那麼要管理3G（3145728kb）總大小就要有98304個PoolInfo，而PoolInfo的數據結構大小為24byte（算上我還沒用揭示用途的那4個位元組），總共就要申請2359296byte（2304kb），因為win32要最少分配4kb，也就是4kb位元組對齊，實際分配空間為2359296byte（2304kb）。現在到比較關鍵的地方，我是直接分配2304kb嗎？記得我上面我給M的大小一定要是2的n次方，這裡就是揭示答案的地方了：因為98304個PoolInfo是第一次申請動態內存，win32給的首地址肯定是64kb對齊的，那麼接下來第一次申請的內存就是第一個PoolInfo管理的內存空間，為了加快內存歸還和釋放，要很快知道釋放的內存地址在哪個PoolInfo裡面，我要滿足的98304個PoolInfo內存大小是M個位元組對齊的，這就是為什麼M一定要是2的n次方，所以我們不能直接分配2304kb，要計算2304kb和32kb的數據對齊值，計算結果是2304kb，要釋放的指針，根據高17位就能定位到所在的PoolInfo。

還記得我前面說的棧空間，靜態數據空間和動態數據空間嗎？他們都是分配粒度的整數倍。

接下來所有分配都是圍繞著32kb來進行的，並且所有的分配都是連續的。

圖3.18 PoolInfo管理自己32kb

到這裡就還有一個過程沒有講述了，那就是PoolInfo內部的內存管理，每個PoolInfo管理32kb，每次分配大小是1kb-2kb，我以2kb為一個單元，這樣PoolInfo裡面管理16個單元。那要怎麼管理呢？現在那個神秘的4個位元組就可以露面目來了，並且引出新的的數據結構：

struct FreeMem{ FreeMem* Next; // 在同一個PoolInfo中，下一個可用的單元 DWORD Blocks; //還剩下多少可用單元 PoolInfo* GetPool();};PoolInfo* FreeMem::GetPool(){ return (PoolInfo*)((INT)this & 0xffff8000); //在PoolInfo中的任意一個地址取出高17位就能定位這個PoolInfo}struct PoolInfo{ PoolInfo * Pre; //指向自己前一個節點 PoolInfo * Next; //指向自己的後一個節點 PoolTable * Owner; //屬於哪個鏈表管理者 void * Mem; //指向win32分配空間的首地址 unsigned int Taken; //每分配一次就加1，釋放一次就減1，如果釋放後為0，那麼就把Mem指向的內存空間還給win32 FreeMem * FreeMem; //指向可用的數據單元（神秘的4位元組） void Link( FPoolInfo*& Head ) //傳入頭指針，PoolTable的FirstPool或者ExhaustedPool { if(Head) //頭指針不為空 { Before->Pre = this } Next = Head; //將這個節點插入，並讓頭指針指向它 Head = this; Pre = NULL; } void Unlink(FPoolInfo*& Head) //傳入頭指針，PoolTable的FirstPool或者ExhaustedPool { if( Next )//將這個節點從當前鏈表中移除，如果Pre為空則證明是頭指針指向的節點 { Next->Prev = Prev; } if(Prev) { Prev->Next = Next; Pre = NULL; } else { Head = Next } Next = NULL; }};

FreeMem的用途是管理連續可用的數據單元，剛剛申請空間的時候管理16個可用單元，此時就只有一個FreeMem，所以它的是Blocks是16，由於不斷的申請和釋放很可能最後出現1個單元是被佔用的（如果釋放後，發現16個單元都可以，則把這個PoolInfo歸還給win32，所以最極限可能是1個單元被佔用，15個空餘），其他15個可用空單元各被一個FreeMem管理。

可見這個FreeMem的大小是8個位元組，用創建FreeMem鏈表嗎？其實不用，因為每個單元是2kb，一個FreeMem管理最多16個單元，最少管理1個單元，2kb足以和一個FreeMem共用。

其實你也可以不用FreeMem這個數據結構，直接用指針管理，也就是說每個單元的前4個位元組指向下一個可用的單元，PoolInfo裡面FreeMem指針可以替換成普通指針。

圖3.19 FreeMem鏈表管理

現在我開始大體描述一下演算法：

初始化：

PoolTable poolTable; poolTable.ExhaustedPool = NULL; poolTable.FirstPool = NULL; poolTable.TableSize = 2kb; PoolInfo pPoolInfo = 分配(98304 * sizeof(PoolInfo) )先4kb對齊，再32kb對齊

申請大小為size(1kb-2kb)：

PoolInfo* Pool = poolTable.FirstPool; if (Pool == NULL) //判讀pool是否為空 { FreeMem * p =分配(32kb); //分配32kb，當前只有一個FreeMem管理 p->Blocks = 16; //初始化FreeMem p->Next = NULL; //win32裡面0x00010000之後才是用戶內存使用區域 FreeMem * p1= p - 0x00010000; //32kb是2的15次方，取高17位得到pool PoolInfo *Pool = pPoolInfo[p1 >> 15]; Pool->Link(poolTable.FirstPool); //初始化Pool Pool->Mem = p; Pool->FirstMem = p; } Pool->Taken++; //每分配一次就加1 //從後向前分配2kb，MemInfo的Blocks減1 void * Free = (FreeMem*)((BYTE*)Pool->FirstMem + --Pool->FirstMem->Blocks * poolTable.TableSize); //當前Pool的第一個MemInfo的Block為0，證明這個MemInfo滿了 if (Pool->FirstMem->Blocks == 0) { Pool->FirstMem = Pool->FirstMem->Next; //那麼就指向下一個MemInfo if (!Pool->FirstMem) //如果下一個不存在，證明這個Pool已經滿了 { Pool->Unlink(poolTable.FirstPool);//從PoolTable空閑列表中移除 //鏈接到PoolTable的非空閑列表 Pool->Link(poolTable->ExhaustedPool); } } return Free;

釋放指針p指向的內存：

p = p - 0x00010000; //減去非用戶空間的偏移 PoolInfo *Pool = pPoolInfo[p >> 15]; //找到對應pool if (!Pool->FirstMem) //如果PoolFirst為空證明它在PoolTable的非空閑列表 { Pool->Unlink(poolTable->ExhaustedPool);//從PoolTable的非空閑列表移除 Pool->Link(pPoolTable->FirstPool); //加入到PoolTable的空閑列表 } FreeMem* Free = (FreeMem *)p; //這個地址直接就是poolInfo的某個單元塊地址 Free->Blocks = 1; /FreeMem管理當前就1個單元塊 Free->Next = Pool->FirstMem; //鏈接到PoolInfo第一個可用FirstMem Pool->FirstMem = Free; if (--Pool->Taken == 0)//如果當前PoolInfo16個單元塊都是空閑的，則把它歸還給操作系統 { Pool->Unlink(pPoolTable->FirstPool); //從PoolTable空閑列表上移除 Pool->Mem 歸還給操作系統 Pool->Mem = NULL; }

以上的邏輯，是unreal3 win32下演算法的核心（實現上稍有不同），我希望你能看明白，如果還沒看明白，我就模擬的講解一次。

還是上面的假設，我模擬一遍，

如果是下面的序列：

申請1.2k 標記為A

申請1.5k標記為B

申請1.6K標記為C

申請1.7k標記為D

申請1.12k標記為E，

申請1.03k標記為F，

申請1.94k標記為G，

申請1.83k標記為H，

申請1.34k標記為I，

申請1.55k標記為J，

申請1.31k標記為K，

釋放E

申請1.88k標記為L，

申請1.93k標記為M，

申請1.83k標記為N，

申請1.67k標記為O

釋放H

申請1.17k標記為P

申請1.55k標記為Q

申請1.9k標記為R

申請1.47k標記為S

釋放B

釋放P

釋放L

釋放C

釋放G

釋放A

釋放N

釋放M

釋放D

釋放I

釋放P

釋放G

釋放T

釋放R

釋放F

釋放J

圖3.20 內存管理示意圖1

圖3.21 內存管理示意圖2

圖3.22 內存管理示意圖3

圖3.23 內存管理示意圖4

圖3.24 內存管理示意圖5

圖3.25 內存管理示意圖6

圖3.26 內存管理示意圖7

圖3.27 內存管理示意圖8

圖3.28 內存管理示意圖9

圖3.29 內存管理示意圖10

圖3.30 內存管理示意圖11

圖3.31 內存管理示意圖12

圖3.32 內存管理示意圖13

上面的演算法是unreal3的在win32下內存分配的精髓，如果你把這個看懂了，可以說，下面詳細講解你可以很容易就理解，所以我希望看到這裡，你還能跟的上，如果上面的演算法模稜兩可，我建議你還是回頭再仔細研究一下，直到你懂了為止，好嗎？

希望大家不要浪費我10幾個小時的時間，為了專門講解好unreal3的內存分配演算法，我思考和畫圖花了好長時間，而且是帶著病工作的，仔細把它看明白吧

c原來如此

你相信我，離勝利不遠了。Unreal和我上面講的很多不同的地方，但精髓都是一樣的，下面我就來慢慢分析unreal和我上面例子有哪些不同。

不同1：基於不同的內存分配額度創建不同的PoolTable。

上面的例子是我假設的——每次分配都在1kb-2kb之間，但實際上一個遊戲分配內存是不可能這樣，你不知道它到底分配多少，所以unreal就創建了很多不同的PoolTable。

enum {POOL_COUNT = 42 }; FPoolTable PoolTable[POOL_COUNT], OsTable;

他創建了43個PoolTable，其中OsTable是給申請分配大於MAXSIZE使用的，後面我會詳細來說。至於Pool_Count的42個PoolTable，每個Size都是不同的。

OsTable.FirstPool = NULL;OsTable.ExhaustedPool = NULL;OsTable.BlockSize = 0;PoolTable[0].FirstPool = NULL;PoolTable[0].ExhaustedPool = NULL;PoolTable[0].BlockSize = 8;for( DWORD i=1; i<5; i++ ){ PoolTable[i].FirstPool = NULL; PoolTable[i].ExhaustedPool = NULL; PoolTable[i].BlockSize = (8<<((i+1)>>2)) + (2<<i);}for( DWORD i=5; i<POOL_COUNT; i++ ){ PoolTable[i].FirstPool = NULL; PoolTable[i].ExhaustedPool = NULL; PoolTable[i].BlockSize = (4+((i+7)&3)) << (1+((i+7)>>2));}

這個就是創建42個PoolTable代碼，具體數值我給大家列出來，前面是索引i的值，後面是對應PoolTable的BlockSize（也就是我上面例子中TableSize）大小，i為0時，我沒有給出，因為代碼一目了然，不用算了。至於為什麼取這些數值來做TableSize大小，我也不太明白，也許是個經驗值，不過我覺得你也可以根據你項目來定義不同的遞增值。

這裡給大家留一個習題，為什麼i為0的時候，TableSize要為8呢？不可以是其他數字嗎？然後再一次遞增？

圖3.33 PoolTable管理PoolInfo中每個單元塊的大小

為了快速查找到要分配的內存位於哪個PoolTable上，unreal建立了一個索引用來快速查找。42個PoolTable的TableSize基本上包含了1到32768byte之間分配的管理，Table0管理1到8byte，Table1管理9到16byte，以此類推，Table41管理28672+1到32768。這樣索引就可以很容易建立出來。

for( DWORD i=0; i < POOL_MAX; i++ ){ DWORD Index; for( Index=0; PoolTable[Index].BlockSize<i; Index++ ); VSMAC_ASSERT(Index < POOL_COUNT); MemSizeToPoolTable[i] = &PoolTable[Index];}.....................................

這段代碼我不想多解釋了，很簡單的映射。

不同2：MAXSIZE和PoolInfo管理Size大小

在上面可以看見POOL_MAX這個枚舉定義，也就是說大於這值的都被認為大內存，不參與管理。上一節我假設的例子中PoolInfo管理內存大小是32kb，而unreal所有的PoolTable下PoolInfo都管理的是65536byte（(POOL_MAX-1)*2），正好一個分配粒度，所以每個PoolInfo下面的小單元個數也不一樣，PoolTable41的一個PoolInfo下面只有2個小單元，如果不夠就又要向win32要65536byte。至於定義POOL_MAX為什麼定義為32768+1，這個我也無從考證，我認為這個數夠用了，一次性申請這麼大空間的基本也少有。

是否咱們自己可以改變這個數值呢？當然可以，後面我再和你慢慢分析，先來看看unreal是怎麼根據指針地址索引到想要的PoolInfo的，記得我上一個小節的例子嗎？管理3G（3145728kb）總大小就要有98304個PoolInfo，而PoolInfo的數據結構大小為24byte，總共就要申請2359296byte（2304kb），因為win32要最少分配4kb，也就是4kb位元組對齊，實際分配空間為2359296byte（2304kb），每個PoolInfo管理內存大小是32kb，又要和32kb進行對齊，最後申請的大小就是2359296byte（2304kb），也就是98304*24byte。Unreal沒有考慮象我上面那麼細緻，直接拿win32最大定址空間4G來做管理，所以就沒有必要還要減去0x00010000，雖然你不可能分配到0x00000000-0x00010000，但也一起管理了。這樣unreal要有多少個PoolInfo就很好算了，首先咱們知道PoolInfo管理大小是65536byte也就是2的16次方byte，要管理4G內存，很顯然需要2的16次方65536個PoolInfo，這樣高16位就可以直接找到PoolInfo。

不同的是unreal做了兩級索引，高16位，分開了前5位和後11位，前5位作為一級索引，後11位作為2級索引。

FPoolInfo* PoolIndirect[32]

然後每個PoolIndirect[i]指針又去申請了2的11次方的PoolInfo，也就相當於

FPoolInfo PoolIndirect[32][2048];

Unreal這麼做估計也是為了減少內存佔用，不是每個PoolIndirect[i]都有機會分配到2048個PoolInfo的。

struct FPoolInfo{ DWORD Bytes; DWORD OsBytes; DWORD Taken; BYTE* Mem; FPoolTable* Table; FFreeMem* FirstMem; FPoolInfo* Next ; FPoolInfo** PrevLink;}

我們算算2048*sizeof(FPoolInfo) = 2048 * 32 正好和65536byte位元組對齊的，準確的說他們相等，unreal這麼設計更加精妙在於每次分配都是一個分配粒度即64kb。這個也是兩級索引為什麼分成5和11的原因。根據上一個小節，其實大家也知道，不是一個分配粒度其實也無所謂，反正win32都分配好了。

至於PreLink為什麼是指針的指針，其實和我假設例子差不多，都是實現鏈表，大家可以看看代碼就知道，只是實現方式不一樣，它這種方式，從一個鏈表中刪除，無需知道當前鏈表的頭指針。

void Link( FPoolInfo*& Before ){ if( Before ) { Before->PrevLink = &Next; } Next = Before; PrevLink = &Before; Before = this;}void Unlink(){ if( Next ) { Next->PrevLink = PrevLink; } *PrevLink = Next;}

剩下最後一個大於MAXSIZE的情況，unreal裡面MAXSIZE是65536byte即64kb，正好是win32的一個分配粒度，大於它的都不在管理，直接分配，那釋放的時候怎麼知道它是大於64kb的。這個就是我前面提到但沒有仔細說的OsTable，所有大於64kb的PoolInfo都管理者Table都是OsTable，每次通過高16位兩級索引找到PoolInfo，然後在找PoolTable，如果是OsTable，那麼就是大於64kb的，然後就直接釋放。

d代碼剖析

接下來我拿著具體代碼來剖析裡面的具體過程。

先看構造函數初始化：

VSMemWin32::VSMemWin32(){ PageSize = 0 ; //得到win32頁面大小，windows核心編程裡面提到，這個一般由cpu來決定，但大部分intel和AMD的都是4kb SYSTEM_INFO SI; GetSystemInfo( &SI ); PageSize = SI.dwPageSize; VSMAC_ASSERT(!(PageSize&(PageSize-1))); // 初始化PoolTable //這個是留給大於maxsize用的 OsTable.FirstPool = NULL; OsTable.ExhaustedPool = NULL; OsTable.BlockSize = 0; //下面0-41是留給小於maxsize //記得我留給大家的問題了嗎?為什麼最小的是8位元組? PoolTable[0].FirstPool = NULL; PoolTable[0].ExhaustedPool = NULL; PoolTable[0].BlockSize = 8; for( DWORD i=1; i<5; i++ ) { PoolTable[i].FirstPool = NULL; PoolTable[i].ExhaustedPool = NULL; PoolTable[i].BlockSize = (8<<((i+1)>>2)) + (2<<i); } for( DWORD i=5; i<POOL_COUNT; i++ ) { PoolTable[i].FirstPool = NULL; PoolTable[i].ExhaustedPool = NULL; PoolTable[i].BlockSize = (4+((i+7)&3)) << (1+((i+7)>>2)); } //建立從0-32768byte映射到PoolTable的表 for( DWORD i=0; i < POOL_MAX; i++ ) { DWORD Index; for( Index=0; PoolTable[Index].BlockSize<i; Index++ ); VSMAC_ASSERT(Index < POOL_COUNT); MemSizeToPoolTable[i] = &PoolTable[Index]; } //清空32個一級索引 for( DWORD i=0; i < 32 ; i++ ) { PoolIndirect[i] = NULL; } VSMAC_ASSERT(POOL_MAX-1==PoolTable[POOL_COUNT-1].BlockSize);}

再看分配過程：

void* VSMemWin32::Allocate (unsigned int uiSize,unsigned int uiAlignment,bool bIsArray){ // 內存鎖，防止2個線程同時申請內存，後面講多線程時候會詳細講 ms_MemLock.Lock(); FFreeMem* Free; // 如果小於maxsize if( uiSize<POOL_MAX ) { // 根據0-32768byte映射表找到對應的PoolTable FPoolTable* Table = MemSizeToPoolTable[uiSize]; VSMAC_ASSERT(uiSize<=Table->BlockSize); // 查看PoolTable的PoolInfo，是否有可用內存 FPoolInfo* Pool = Table->FirstPool; //沒有可用的PoolInfo if( !Pool ) { // 創建PoolInfo，每個PoolInfo管理64kb內存，根據當前PoolTable管理每個單元大小，計算出總塊數 DWORD Blocks = 65536 / Table->BlockSize; //下面這句計算其實多餘，Bytes其實小於65536的，但win32分配還是64kb DWORD Bytes = Blocks * Table->BlockSize; VSMAC_ASSERT(Blocks>=1); VSMAC_ASSERT(Blocks*Table->BlockSize<=Bytes); // 分配內存，unreal內存分配管理，裡面一共從win32申請3類內存，第一類就是這個，申請PoolInfo，即使Bytes小於64kb，但win32分配還是64kb Free = (FFreeMem*)VirtualAlloc( NULL, Bytes, MEM_COMMIT, PAGE_READWRITE ); if( !Free ) { return NULL; } // 通過一級索引查找二級索引 FPoolInfo*& Indirect = PoolIndirect[((DWORD)Free>>27)]; if( !Indirect ) //二級索引為空，則創建二級索引，2048個PoolInfo，正好是64kb { //這是第二類分配內存，也正好是win32的一個分配粒度 Indirect = CreateIndirect(); } //根據二級索引找到對應的PoolInfo Pool = &Indirect[((DWORD)Free>>16)&2047]; // 連接到對應PoolTable Pool->Link( Table->FirstPool ); Pool->Mem = (BYTE*)Free; //下面這2個變數其實多此一舉，根本沒用，估計是為了湊數，讓2048個PoolInfo正好是64k Pool->Byte = Bytes; Pool->OsBytes= Align(Bytes,PageSize); // 下面的初始化過程和我上面講的例子就一樣了 Pool->Table = Table; Pool->Taken = 0; Pool->FirstMem= Free; Free->Blocks = Blocks; Free->Next = NULL; } // 下面的過程也和我講的例子中一樣，不多講了。 Pool->Taken++; VSMAC_ASSERT(Pool->FirstMem); VSMAC_ASSERT(Pool->FirstMem->Blocks>0); Free = (FFreeMem*)((BYTE*)Pool->FirstMem + --Pool->FirstMem->Blocks * Table->BlockSize); if( Pool->FirstMem->Blocks==0 ) { Pool->FirstMem = Pool->FirstMem->Next; if( !Pool->FirstMem ) { // Move to exhausted list. Pool->Unlink(); Pool->Link( Table->ExhaustedPool ); } } } else { //大於64kb分配，這是第三類從win32分配內存，算不算位元組對齊都無所謂了，前兩類每次其實分配都是64kb，第三類分配大於64kb多出來的餘數，其實也用不上了。 INT AlignedSize = Align(uiSize,PageSize); Free = (FFreeMem*)VirtualAlloc( NULL, AlignedSize, MEM_COMMIT, PAGE_READWRITE ); if( !Free ) { return NULL; } VSMAC_ASSERT(!((SIZE_T)Free&65535)); FPoolInfo*& Indirect = PoolIndirect[((DWORD)Free>>27)]; if( !Indirect ) { Indirect = CreateIndirect(); } // Init pool. FPoolInfo* Pool = &Indirect[((DWORD)Free>>16)&2047]; Pool->Mem = (BYTE*)Free; Pool->Bytes = uiSize; Pool->OsBytes = AlignedSize; //指向OsTable Pool->Table = &OsTable; } ms_MemLock.Unlock(); return Free;}FPoolInfo* CreateIndirect(){ FPoolInfo* Indirect = (FPoolInfo*)VirtualAlloc( NULL, 2048*sizeof(FPoolInfo), MEM_COMMIT, PAGE_READWRITE ); if( !Indirect ) { return NULL; } return Indirect;}void VSMemWin32::Deallocate (char* pcAddr, unsigned int uiAlignment,bool bIsArray){ ms_MemLock.Lock(); if( !pcAddr ) { return; } //通過兩級索引找到對應的PoolInfo FPoolInfo* Pool = &PoolIndirect[(DWORD)pcAddr>>27][((DWORD)pcAddr>>16)&2047]; VSMAC_ASSERT(Pool->Bytes!=0); //小於MaxSize的，具體細節和前面例子一樣不詳細說了 if( Pool->Table!=&OsTable ) { if( !Pool->FirstMem ) { Pool->Unlink(); Pool->Link( Pool->Table->FirstPool ); } FFreeMem* Free = (FFreeMem *)pcAddr; Free->Blocks = 1; Free->Next = Pool->FirstMem; Pool->FirstMem = Free; VSMAC_ASSERT(Pool->Taken>=1); if( --Pool->Taken == 0 ) { Pool->Unlink(); VirtualFree( Pool->Mem, 0, MEM_RELEASE ); Pool->Mem = NULL; } } else { VirtualFree( pcAddr, 0, MEM_RELEASE ); Pool->Mem = NULL; } ms_MemLock.Unlock();}

這裡面有地方需要具體解釋下：

就是VirtualAlloc，這個函數win32底層分配內存函數，咱們用的new或者malloc在win32上其實都是調用VirtualAlloc，不同的是你的進程第一次分配，肯定是64kb對齊的，也就是0Xxxxx0000這種形式，然後再分配如果沒有超過64kb還在這裡繼續分配，如果超出，就再起一個分配粒度，分配的地址也是0Xxxxx0000。所以上面的內存分配3類調用VirtualAlloc，第一類分配PoolInfo管理的內存可能小於64kb，但不會小於一個頁面4kb，所以最後win32還是分配64kb，第二類分配第2級索引PoolInfo時候就是64kb，第三類是大於64kb的，所以說這3類分配內存的地址都是0Xxxxx0000，這樣高16位索引管理查找刪除都很方便。但如果你用new或者malloc有額外的數據結構，並且調用了heap分配函數導致返回地址是無規律的。

最後一個想說的是TableSize大小，unreal給出的並不是所有的都被64kb所整除，大家可以試試其他的，也不一定要42個。

總結下，這種方法其實也會產生大量碎片，唯一的好處就是速度快，相對於new和malloc，它們申請和釋放所產生的碎片相對不可預測，而這種方法碎片多少起碼可以預測到。