Unreal3 window下内存管理实现详解

左手的ㄟ右手 2022-08-18 00:38 13阅读 0赞

Unreal3 window下内存管理实现详解  
  
  
　　　　最近组里面同事加入了一个很牛叉的内存管理代码，勾起我对内存管理的强烈欲望，以前也做过内存管理，在没有遇到U3以前看了3，4种算法（C++游戏编程 这本书 里面一个，内存管理这本书 里面讲了3个，我很推荐这2本书，C++游戏编程，讲了游戏基础架构，包括内存管理，智能指针，对象构建，对象序列化等等，内存管理这本书，除了讲了几种内存管理，还讲了2种基于内存的GC方法），总感觉不是很好。  
　　　　游戏引擎中之所以要做内存管理，一个是加快内存分配速度，另一个就是处理内存泄漏问题。  
　　　　１.先简单说处理内存泄漏这个问题，一般的引擎在debug 模式下 都有一个记录内存分配的结构体，每分配一段内存就记录这段内存的信息，包括大小，分配时间，是否是数组，前后越界的标记等等吧，其实这些都不是那么重要，因为你只知道这些，一旦泄漏出现，你虽然知道泄漏，但无法定位。相反如果你知道堆栈的调用信息，就能准确定位。我以前的实现，在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&