Unreal3 window下内存管理实现详解
最近组里面同事加入了一个很牛叉的内存管理代码，勾起我对内存管理的强烈欲望，以前也做过内存管理，在没有遇到U3以前看了3，4种算法（C++游戏编程 这本书 里面一个，内存管理这本书 里面讲了3个，我很推荐这2本书，C++游戏编程，讲了游戏基础架构，包括内存管理，智能指针，对象构建，对象序列化等等，内存管理这本书，除了讲了几种内存管理，还讲了2种基于内存的GC方法），总感觉不是很好。
游戏引擎中之所以要做内存管理，一个是加快内存分配速度，另一个就是处理内存泄漏问题。
１.先简单说处理内存泄漏这个问题，一般的引擎在debug 模式下 都有一个记录内存分配的结构体，每分配一段内存就记录这段内存的信息，包括大小，分配时间，是否是数组，前后越界的标记等等吧，其实这些都不是那么重要，因为你只知道这些，一旦泄漏出现，你虽然知道泄漏，但无法定位。unity优化内存与性能。相反如果你知道堆栈的调用信息，就能准确定位。我以前的实现，在debug下，只记录当前调用new的时候的行号和文件，也就是内部的__FILE__ __LINE___.。我看了同事那个能记录堆栈调用过程，简直觉得很牛逼（其实不是调用堆栈，只是打印出调用过程，继续往下看你就知道了），以前自己也想过，但不知道怎么去实现。内存管理包括那几个部分，如果U3里面也加入这个功能，那就更牛叉了。思想很简单，就是核心东西在一个函数，这个是系统函数，提供当前这行指令所在的地址，它会打印出来这行指令的文件名和行号。先详细说下数据在内存的分配
最早的计算机数据段和代码段区分的很严格，现在似乎没有这么严格了！对于全局变量和静态变量它的分配完全在数据段分配，知道运行结束才会收回内存！而对于自动变量（包括函数参数和函数中定义的变量）则在堆栈中分配！一般的分配情形是这样的：从栈下到栈顶依次是函数参数，函数结束后下一条指令的地址，寄存器保护，然后是函数中定义的变量！
例如：
void main()
{
int m=3,n=4,s=0;
s=f(m,n);
}
int f(int a,int b)
{
int c=2;
return a+b+c;
}
我们从s=f(3,4)开始
它的汇编代码大致是这样:
push n
push m
call f
push bp
mov bp sp
push ax //保护寄存器
'
'
'
为c开辟存储空间
计算a+b+c
弹出c的空间
' //弹出寄存器值
'
'
pop ax
pop bp
ret 8
数据存储栈的示意图
_________
|___c___|<--sp
|___'___|
|___'___|
|___'___|
|__ax___|
|__bp___|<--bp
|IP next|
|___m___|
|___n___|
首先压栈m,n，这个压栈的顺序c和c++是从右到左，而PASCAL则是从左到右，其实哪个顺序是无所谓的
接下来是call f这个是让IP指针指到函数的入口地址，这个入口地址是在连接时候完成的
接下来是把BP压入栈中，这里为什么要把BP值压入，因为函数要使用BP这个寄存器，计算机里的寄存器个数是有限的每个函数都使用，可能造成值的丢失，所以先把BP的值保存起来，以免丢失，在弹栈时，把这个值在放回BP中！后面的AX等寄存器压入栈都是这个原理，一般BP用做栈基指针，用来使用栈中当前函数的变量值这个很方便mov bp sp，SP是栈顶指针，这时BP就指向了BP寄存器压入值的位置，BP+4(之所以加4因为整形占4个字节)就指向 IP NEXT(函数返回时，IP要接着函数结束的后一条指令执行，这个地方就存储的这条指令地址)BP+8就指向m，BP-20就指向c
函数执行完后要弹栈，按入栈的反方向弹出，然后IP等于IP NEXT的值，ret 8是告诉系统要把m,n也弹出，8是字节数。内存管理算法，
看明白了函数调用机理，我们把BP取出来，然后让bp + 4个字节，就得到了 函数返回后的下一个代码段地址，把这个传递给函数，SymGetLineFromAddr64
每调用一次内存分配函数的时候，就执行下段代码，每个内存块都保存一个指令地址数组
DWORD _ebp, _esp;
__asm mov _ebp, ebp;
__asm mov _esp, esp;
size_t index = 0;
for(; index < CALLSTACK_NUM; index++)
{
pCallStack[index] = (void*)ULongToPtr(*(((DWORD*)ULongToPtr(_ebp))+1));//先把EBP 转换成4个字节的 然后+１ 就等于加４个字节
_ebp = *(DWORD*)ULongToPtr(_ebp);
if(_ebp == 0 || 0 != (_ebp & 0xFC000000) || _ebp < _esp)
break;
}
for(; index < CALLSTACK_NUM; index++)
{
pCallStack[index] = 0;
}
然后传递给SymGetLineFromAddr64,按顺序打出来就可以。
这样打印出来比较好，会直接输出到Output窗口，鼠标点击就会自动定位（这个是ＶＳ自己实现的，你按照这个方式输出就可以了）
sprintf_s(Temp,BUFFER_SIZE,"%s(%d)\n",szFile,uiLine);
OutputDebugString(Temp);
２.加快内存分配速度。
我的个人理解一个好的内存分配器，１要分配内存块，２要释放内存块，３减少碎片。虚拟内存文件？这３个是起码的，当然你可以加ＧＣ功能，在内存管理这本书里面讲了２个ＧＣ方法（作者应该很牛逼，他说他所有讲的内存管理都是最简单，为说明问题，代码没有一点优化，否则就会晦涩难懂，还好Ｕ３并没有写成这样）
我先说说我以前遇到几种内存管理方法，一个很大的问题，就是当内存申请不够用了的时候，再申请一块的时候，都没讲怎么处理。都是预先分配一个大的，如果不够用了怎么办？还有就是，内存碎片很难处理，因为你做内存整理，牵扯到指针的移动的改变，做这个真是费力不讨好，速度就要有限制，还有有空间来配合做移动。其余的就是速度和空间上的交换了。内存管理的设计与实现。所以这些方法都很难找到平衡点，没有一个最有效折中的方法。
当然Ｕ３也并没有做到你想像的那么好，但它做的比较平衡。性价比高。
先说几个统计性的数据，在游戏中，小于１Ｋ的动态分配数据是最频繁的，而且越小越频繁。相反越大的数据，例如模型ＶＢ，ＩＢ，texture数据等等吧，这些申请和释放频率比较低，很大多数动态分配时间都浪费到小数据的申请和释放上。有２种比较内存管理机制，一个是典型的空间换时间，就是一个内存块，我分成相等的小块，根据某种机制正好要在这个里面分配，那么不管这个小块大于要申请的ｓｉｚｅ多大，都要拿出一个小块。比如我一个内存块是4０，我分成4块，每个大小是１０.我现在要分配６，那么取出一个小块，多出那个４就要被浪费掉了。还有一种机制就是有多大我就分多大的，然后用链表或者树结构管理空间和占用的块。这种方法经过多次申请释放会有很多碎片是不可用的。第一种机制，分配释放都很块，因为这个是等大的可以做类似数组那么用索引来出来，申请释放。而第２种机制申请和释放去查找，比较浪费时间。
Ｕ３方法用的是第一种机制，最重要的是，它巧妙应用了操作系统的特性。如果大块内存也申请释放相对比较频繁的话，可以把大块内存这个用第二种方法处理。但这个频繁要多么频繁，好像很难给出准确数据，因为所有的时间消耗都是小块内存数据申请上，所以我感觉不用也可以。
说了这么多，现在言归正传，详细分析U3在windows下的内存管理，因为U3支持多个平台，每个平台下的内存管理是不一样，这个也是针对不同平台的特性定制的，后面你就会发现，这个Windows下的内存管理，巧妙的运用了windows内部原理。
（这里我改了好几遍，不知道怎么说好，这些说原理吧，首先是不容易说明白，看的人一定也一头雾水，最后还是把代码弄上来，分析代码，这样说的能比较透彻。有unreal代码的自己去找FMallocWindows.h这个文件）
struct FPoolInfo
{
DWORD Bytes; // Bytes allocated for pool.
DWORD OsBytes; // Bytes aligned to page size.
DWORD Taken; // Number of allocated elements in this pool, when counts down to zero can free the entire pool.
BYTE* Mem; // Memory base.
FPoolTable* Table; // Index of pool.
FFreeMem* FirstMem; // Pointer to first free memory in this pool.
FPoolInfo* Next;
FPoolInfo** PrevLink;
void Link( FPoolInfo*& Before )
{
if( Before )
{
Before->PrevLink = &Next;
}
Next = Before;
PrevLink = &Before;
Before = this;
}
void Unlink()
{
if( Next )
{
Next->PrevLink = PrevLink;
}
*PrevLink = Next;
}
};
// Information about a piece of free memory. 8 bytes.
struct FFreeMem
{
FFreeMem* Next; // Next or MemLastPool[], always in order by pool.
DWORD Blocks; // Number of ce起玩过滤词ecutive free blocks here, at least 1.
FPoolInfo* GetPool()
{
return (FPoolInfo*)((INT)this & 0xffff0000);
}
};
// Pool table.
struct FPoolTable
{
FPoolInfo* FirstPool; //所有小块没都分配出去的FPoolInfo列表
FPoolInfo* ExhaustedPool;//所有小块都分配出去的FPoolInfo列表
DWORD BlockSize;//一次申请分配，能分配的内存大小（也就是说小块内存大小）
};
当分配一个大块内存的后，这个大块内存地址会记录到FPoolInfo的 BYTE* Mem这个变量，每个FPoolInfo都要归属于一个FPoolTable，也就是说FPoolTable管理能分配小块内存都等于BlockSize的所有FPoolInfo。开始创建这个大块内存的时候，同时这个FPoolInfo也被创建，进入FPoolInfo* FirstPool列表，如果这个FPoolInfo小块内存（上面讲的第一种机制，大块会切分相等小块，小块就是去分配的，小块的大小是FPoolTable的BlockSize变量）都分配完毕，那么就进去ExhaustedPool链表。
U3采用2种机制来处理，一种是小于MAX_SIZE的就用FPoolTablelai 来管理FPoolInfo，如果大于的话，FPoolInfo就不用管理，直接申请释放。上面说到其实很多时间都是浪费在size小内存申请和释放的时间上，size大的内存申请释放并不频繁。
下面主要分析小size内存分配管理，具体这个大块内存多大，分成多少小块。先说小块个数，当大块内存size固定，是跟小块大小有关系的。
U3 的下面这个数组，
FPoolTable PoolTable[POOL_COUNT]// POOL_COUNT = 42其实应该写TABLE_COUNT更为直观，否则容易让人产生异议
开始的时候初始化FPoolTable 的BlockSize
PoolTable[0].FirstPool = NULL;
PoolTable[0].ExhaustedPool = NULL;
PoolTable[0].BlockSize = 8;
for( DWORD i=1; i<5; i++ )
{
PoolTable.FirstPool = NULL;
PoolTable.ExhaustedPool = NULL;
PoolTable.BlockSize = (8<<((i+1)>>2)) + (2<<i);
}
for( DWORD i=5; i<POOL_COUNT; i++ )
{
PoolTable.FirstPool = NULL;
PoolTable.ExhaustedPool = NULL;
PoolTable.BlockSize = (4+((i+7)&3)) << (1+((i+7)>>2));
}
PoolTable最后一个元素的BlockSize = MAX_SIZE - 1；（上面提到了只有小于MAX_SIZE 的才用PoolTable管理）为每个元素分配BlockSize 大小起码要保证是递增的，然后最后一个大小要是MAX_SIZE - 1，然后这数列最好保证分配浪费最少的内存，也就是说，要分配20字节，你这个列表里面只有16，下一个是32了，那我只能分配32，浪费了12，如果有20拿来分配，只浪费了4。我估计u3这么计算也是有他道理的。
为了每次很块的能找到对应的PoolTable，接下来初始化这个
for( DWORD i=0; i<POOL_MAX; i++ )
{
DWORD Index;
for( Index=0; PoolTable[Index].BlockSize<i; Index++ );
checkSlow(Index<POOL_COUNT);
MemSizeToPoolTable = &PoolTable[Index];
}
也就是说我分配0 到POOL_MAX之间的大小可以直接做为MemSizeToPoolTable的索引，找到对应的PoolTable。至于要用多少的PoolTable这个其实无所谓了，u3 里面为42个。
现在说下U3里面做的最有技巧的东西，大家知道WINDOW32bit下指针是32位，也就是说寻址虚拟内存对大地址是32位，每次分配最小空间是4KB，分配粒度是64KB（其实你在WINDOWS下调用new，分配大小都是4KB对齐的，也就是你分配不足4kb也会给你4kb，这样其实浪费了很多空间。）
为了快速申请和释放内存，它把这32位前16位作为索引，作为FPoolInfo数组的索引，这样可以很快找到这个FPoolInfo。因为Windows32分配都是4kb对齐的，我申请空间是2的16次方字节，也就是说我把32位的后16位都占满了，因为分配粒度保证了64KB，这样所有0x####0000 ----------0x####FFFF地址的都用我这个FPoolInfo来管理。如果直接创建FPoolInfo数组的话，因为前16位做索引，那么要创建2的16次方 × sizeof（FPoolInfo）大小空间，你想想你虚拟内存4GB，32地址能都用了吗？显然是不可能的，直接诶创建这么大空间很浪费的，所以U3做了2级索引，前5位一个级别，后11位一个级别，后面是11是动态创建的，后面选择大于7位其实就可以，因为2的7次方 ×sizeof（FPoolInfo）等于４ＫＢ，至于为什么选择１１和５可能是经验值吧。
FPoolInfo* PoolIndirect[32]; //32 用来表示前5位一级索引，当访问一级索引为空的时候就会调用下面的函数创建出来，这样可以用2级别索引。
FPoolInfo* CreateIndirect()
{
FPoolInfo* Indirect = (FPoolInfo*)VirtualAlloc( NULL, 2048*sizeof(FPoolInfo), MEM_COMMIT, PAGE_READWRITE );
if( !Indirect )
{
OutOfMemory();
}
return Indirect;
}
virtual void* Malloc( DWORD Size, DWORD Alignment )
{
check(Alignment == DEFAULT_ALIGNMENT && "Alignment currently unsupported in Windows");
MEM_TIME(MemTime -= appSeconds());
STAT(CurrentAllocs++);
STAT(TotalAllocs++);
FFreeMem* Free;
if( Size<POOL_MAX ) ／／如果小于一定size就用PoolTable管理
{
//为了快速定位用那个table
FPoolTable* Table = MemSizeToPoolTable[Size];
checkSlow(Size<=Table->BlockSize);
FPoolInfo* Pool = Table->FirstPool;
if( !Pool )//查看当前是否有空闲的FPoolInfo，如果没有创建
{
// Must create a new pool.
DWORD Blocks = 65536 / Table->BlockSize; //看见了吧这里为什么用65536，也就是说Bytes 必然要小于65536 的，但要满 //足4KB对齐 其实系统还是分配65536 大小。我给点建议，就是其实这里在开 //始初始化每个TABLE时候，BlockSize最好可以被65536整除，Bytes 就等于 //65536，保证不会有浪费的。
DWORD Bytes = Blocks * Table->BlockSize;
checkSlow(Blocks>=1);
checkSlow(Blocks*Table->BlockSize<=Bytes);
// Allocate memory.
Free = (FFreeMem*)VirtualAlloc( NULL, Bytes, MEM_COMMIT, PAGE_READWRITE );
if( !Free )
{
OutOfMemory();
}
// Create pool in the indirect table.
FPoolInfo*& Indirect = PoolIndirect[((DWORD)Free>>27)];//先移动5位做一次索引
if( !Indirect )//如果为空则创建
{
Indirect = CreateIndirect();
}
Pool = &Indirect[((DWORD)Free>>16)&2047];//然后做2级别索引
// Init pool. //初始化时这个pool，前面说了每次从系统申请的内存都会交给这个poolInfo来管理，而poolTable管理poolInfo，并且所有
//poolInfo是最小分配内存块都是为BlockSize大小
Pool->Link( Table->FirstPool );//因为当前Table没有空闲的pool所以，把这个pool链接到空闲列表，
Pool->Mem = (BYTE*)Free;
Pool->Bytes = Bytes;
Pool->OsBytes = Align(Bytes,PageSize);
STAT(OsPeak = Max(OsPeak,OsCurrent+=Pool->OsBytes));
Pool->Table = Table;
Pool->Taken = 0;
Pool->FirstMem = Free;
// Create first free item.
Free->Blocks = Blocks;
Free->Next = NULL;
pool会用申请的内存做一个memInfo的列表管理，就是 Pool->FirstMem ，这个列表里面记录所有空闲的小块，我不需要知道不是空闲的小块，毫无意义，可能有人问，那么这个链表记录应该有额外的数据结构把，其实不然，小块最小是8字节，正好是sizeof（memInfo）大小，我只记录没有分配出去，只要这块内存没有分配出去，我内部想怎么用就怎么用，随便记录memInfo信息。开始的时候创建的时候Bytes都可以用，只有一个memInfo，也就说用了Bytes的前sizeof（memInfo）字节大小几率 memInfo信息， 分配的时候每次必然分配出去的只是一小块，后面归还内存块代码你就会知道，只要没有内存归还，一直只有一个memInfo，只不过每次分配的时候他的Blocks在减1，然后NEXT指针一直为空，如果有归还，则就会链接到这个链表上，然后这个归还的memInfo直接会写到这个归还的内存里，Blocks = 1。也就是说出现最糟糕的情况下，一下子全申请出去，然后再一下去归还，就说出现所有memInfo的Blocks 都为1 ，链接到这个链表里面。
}
// Pick first available block and unlink it.
Pool->Taken++;
checkSlow(Pool->FirstMem);
checkSlow(Pool->FirstMem->Blocks>0);
Free = (FFreeMem*)((BYTE*)Pool->FirstMem + --Pool->FirstMem->Blocks * Table->BlockSize);
if( Pool->FirstMem->Blocks==0 )//这个memInfo已经不包含任何小块了
{
Pool->FirstMem = Pool->FirstMem->Next;//用下一个memInfo
if( !Pool->FirstMem )//如果没有下一个memInfo，证明这个pool已经满了
{
// Move to exhausted list.
Pool->Unlink();
Pool->Link( Table->ExhaustedPool );//则放到table的非空闲队列。
}
}
STAT(UsedPeak = Max(UsedPeak,UsedCurrent+=Table->BlockSize));
}
else
{
// Use OS for large allocatie起玩过滤词.//如果大于一定大小
INT AlignedSize = Align(Size,PageSize);//分配4KB对齐的，其实不对齐也无所谓，反正操作系统会分配4KB整数倍的
Free = (FFreeMem*)VirtualAlloc( NULL, AlignedSize, MEM_COMMIT, PAGE_READWRITE );
if( !Free )
{
OutOfMemory();
}
checkSlow(!((SIZE_T)Free&65535));
// Create indirect.
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 = Size;
Pool->OsBytes = AlignedSize;
Pool->Table = &OsTable;
STAT(OsPeak = Max(OsPeak, OsCurrent+=AlignedSize));
STAT(UsedPeak = Max(UsedPeak,UsedCurrent+=Size));
}
MEM_TIME(MemTime += appSeconds());
return Free;
}
//释放
virtual void Free( void* Ptr )
{
if( !Ptr )
{
return;
}
MEM_TIME(MemTime -= appSeconds());
STAT(CurrentAllocs--);
// Windows version.
FPoolInfo* Pool = &PoolIndirect[(DWORD)Ptr>>27][((DWORD)Ptr>>16)&2047];//寻址相应pool
checkSlow(Pool->Bytes!=0);
if( Pool->Table!=&OsTable )//如果是小于MAX_SIZE的pool
{
// If this pool was exhausted, move to available list.
if( !Pool->FirstMem )//如果这个POOL是当前是已经全都分配完了，则现在有一个空闲的，这个pool就有空闲的空间，则进入TABLE的
//的空闲列表
{
Pool->Unlink();
Pool->Link( Pool->Table->FirstPool );
}
// Free a pooled allocation. //把这个memInfo 链接到这个pool的可用的链表里面
FFreeMem* Free = (FFreeMem *)Ptr;
Free->Blocks = 1;
Free->Next = Pool->FirstMem;
Pool->FirstMem = Free;
STAT(UsedCurrent -= Pool->Table->BlockSize);
// Free this pool.
checkSlow(Pool->Taken>=1);
if( --Pool->Taken == 0 )//如果整个pool所有memInfo都空闲，则释放
{
// Free the OS memory.
Pool->Unlink();//从当前所在的Table空闲列表中删除
verify( VirtualFree( Pool->Mem, 0, MEM_RELEASE )!=0 );
STAT(OsCurrent -= Pool->OsBytes);
}
}
else
{
// Free an OS allocation.
checkSlow(!((INT)Ptr&65535));
STAT(UsedCurrent -= Pool->Bytes);
STAT(OsCurrent -= Pool->OsBytes);
verify( VirtualFree( Ptr, 0, MEM_RELEASE )!=0 );
}
MEM_TIME(MemTime += appSeconds());
}
总结
这里有几个要说明的，因为分配粒度是64Kb，用32位的前16位， 所以保证索引PoolInfo的时候是唯一的，只要你利用索引的位数不大于16位都可以，但也毫无意义，因为返回的大于的位数也是0。U3是分配64KB大小每个POOL，我估计这个可能是个经验值，正好匹配那低16位。当然分配大于64K也无所谓。至于MAX_SIZE，U3分配的是32KB，这个也可能是经验值把，其实这个也无所谓的了，只要POOL分配的大小其实大于MAX_SIZE就可以，我的倾向于，每个table的blocksize 最后能整除。
- 本文出自e起玩社区，原文地址：http://www.code175.com/forum.php?mod=viewthread&tid=8286&
