第三章 System Part2（From3.3 To 3.3.1）

3.內存管理

內存管理是System內部最重要的部分，我單獨拿出來詳細講。不少書里有講內存管理的方法，在沒有遇到UE3之前我大概了解3，4種內存管理方法，不過它們過多過少的都存在著缺陷。

圖3.5 這本書講了一些遊戲關於序列化和遊戲內存管理的，對於初學者還是很後幫助的。

遊戲引擎中之所以要做內存管理，一個是加快內存分配速度,有效的利用內存；另一個就是處理內存泄漏問題，最後是分析各個模塊或者資源的內存佔用統計。每種類型的內存管理器都有自己的功能，下面是內存管理器的基類。

class VSSYSTEM_API VSMemManager{ public: VSMemManager(); virtual ~VSMemManager() = 0; virtual void* Allocate (unsigned int uiSize,unsigned int uiAlignment,bool bIsArray) = 0; virtual void Deallocate (char* pcAddr, unsigned int uiAlignment,bool bIsArray) = 0;};

(1)處理內存泄漏

內存泄漏的處理包括：找到沒有釋放的指針、找到為什麼出現了野指針、找到導致內存不斷增長的原因。

遊戲一旦出現內存泄漏，大部分問題都是上面提到的幾個問題，由於遊戲代碼是多人協作，使用C++寫代碼的時候，很可能某人在不經意間更改了其他人代碼的邏輯，導致了內存泄漏，甚至在特定場合下才出現的那種小的泄漏，更是難以跟蹤判斷，再加上寫代碼的人能力參差不齊，出現內存泄漏幾率更加高。所以有效的預防這種問題的出現比解決問題顯的更加重要。

好多時候直接用系統的new來作為分配空間的函數會導致好多問題出現，如果你是有項目經驗的人，就會知道直接用系統new來開發一個遊戲是多麼危險。我也遇到過項目就是用系統new來開發的，到項目中期出現時不時的奔潰和內存逐漸增加的現象，還好現在有好多第三方的診斷工具能幫助你找到內存泄漏問題（這裡我就不提及了，有心的人自己去網上找找哦，因為這個不是本書的重點）。

所以大部分遊戲引擎都會有一套內存管理機制來診斷那裡出現問題。

對於沒有釋放的指針，我們要找到到底哪個指針申請了內存沒有釋放，具體到那段代碼和堆棧。

對於野指針的出現，一個是什麼時候被釋放了，一個是指針指向的內容被破壞。

對於內存不斷的增長，一個是內存泄漏的增長，一個是沒有內存泄漏，而是由於程序書寫邏輯錯誤導致不斷增長。

我想一個好的內存管理應該具備查找並能解決這些問題的條件，而且在解決過程中，使用還要方便，不至於把程序卡死。

對於那種特定場合才會出現的情況，首先要分析出這個場合出現的條件，這個根據項目不同，方法也不同，更多是考驗你對項目和對應代碼的熟悉程度。我還沒有想到通用的解決方案，去找到出現的條件。但這個條件被找到，就可以復現，那麼問題就很好處理了。

現在大型的c或者c++的項目，沒有一個敢說自己奔潰率為0的，有些也可能非代碼問題，可能是執行環境突然出現異常。

在繼續 講下去之前，我簡單說說重載new操作符，有爭議的地方是要不要重載全局的new，一般重載全局的new，只要用到new的地方就肯定是用重載的方法而且唯一；另一種是不重載全局的new，而是類內重載，這樣只要繼承這個類的都用重載的new，而沒繼承的就不用這個。可能每個人的觀點不太一樣，我個人比較建議使用全局的重載，把申請內存的方法統一起來，你後面看到的，所有都是同一使用一套內存管理方式。

#define VS_NEW new

#define VS_DELETE delete

羅里羅嗦這麼多，現在是揭曉答案的時候了。原理也沒那麼複雜，其實就是把每次分配的內存都管理起來，把關鍵信息都記錄起來，並加上保護。這樣一旦沒有釋放或者被越界寫入，這裡就會報錯。

我用一個鏈表管理分配所有的空間，每一個節點都存儲了一些信息，可以看下面的類。

class Block{ public: Block() { for (unsigned int i = 0; i < CALLSTACK_NUM; i++) { pAddr[i] = NULL; } m_pPrev = NULL; m_pNext = NULL; } void * pAddr[CALLSTACK_NUM]; //申請內存時候的調用堆棧信息 unsigned int m_uiStackInfoNum; //堆棧層數 unsigned int m_uiSize; //申請空間的大小 bool m_bIsArray; //是否是數組 bool m_bAlignment; //是否位元組對齊 Block * m_pPrev; //前一個節點 Block * m_pNext; //後一個節點};

看圖3.11，我想大家應該一目了然，每個block結構（紅色部分）管理著被申請的一塊內存（綠色部分），而且前後有2個mask（灰色和藍色）作為保護這段內存的標誌位，這些都被block內部的兩個Pre和Next指針鏈接起來，形成了一個鏈表。

圖3.11 內存管理鏈表

內存管理器裡面只需要維護鏈表頭和尾的兩個指針，就能管理整個鏈表了。

不熟悉數據結構鏈表的，我建議還是回去好好研讀數據結構這本書，是的，下面又到了新書推薦的時候了，如果你實在不想回讀大學學那本數據結構（寫的簡直太糟糕了），那麼這本書你看了之後會愛不離手的，它的執行示例簡直太生動了，我認為這樣的書才值得做教材。

圖3.12 遊戲數據結構，這本書我真的不想說太多，一般人我都不告訴

好，下面是揭示具體細節的時候了，啥也不說看代碼吧。

class VSSYSTEM_API VSDebugMem : public VSMemManager{ public: VSDebugMem(); ~VSDebugMem(); virtual void* Allocate (unsigned int uiSize,unsigned int uiAlignment,bool bIsArray); virtual void Deallocate (char* pcAddr, unsigned int uiAlignment,bool bIsArray); private: enum { BEGIN_MASK = 0xDEADC0DE, END_MASK = 0xDEADC0DE, RECORD_NUM = 32, //必須大於2 CALLSTACK_NUM = 32 }; Block* m_pHead; Block* m_pTail; unsigned int m_uiNumNewCalls; //調用new的次數 unsigned int m_uiNumDeleteCalls; //調用delete次數 unsigned int m_uiNumBlocks; //當前有多少內存塊 unsigned int m_uiNumBytes; //當前有多少位元組 unsigned int m_uiMaxNumBytes; //最大申請多少位元組 unsigned int m_uiMaxNumBlocks; //最大多少個內存塊 //記錄在2的n次方範圍內內存申請次數 unsigned int m_uiSizeRecord[RECORD_NUM]; void InsertBlock (Block* pBlock); void RemoveBlock (Block* pBlock);};

這個debug內存管理器，除了重載了Allocate、Deallocate，這裡面還做了很多統計，比如記錄了申請和釋放的次數、當前申請多少個內存塊和當前多少位元組、最大多少內存塊、最大多少位元組，這些對於一個項目來說作為統計數據是很有意義的，更重要的是m_uiSizeRecord這個記錄的內存申請次數，看上面的注釋你很難理解，直接看每次申請內存的代碼吧。

unsigned int uiTwoPowerI = 1; int i; for (i = 0; i <= RECORD_NUM - 2 ; i++, uiTwoPowerI <<= 1) { if (uiSize <= uiTwoPowerI) { m_uiSizeRecord[i]++; break; } } if (i == RECORD_NUM - 1) { m_uiSizeRecord[i]++; }

uiSize是這次申請的位元組數，上面這段代碼會根據uiSize落到2的n次方的哪個範圍內來做統計。比如我申請位元組數15，i等於4的時候，uiTwoPowerI等於16，15小於16，它落在2的3次方和2的4次方之間，這樣就可以統計出以2為次數不同大小內存分配情況，這裡的RECORD_NUM在32位操作系統下大於32是沒有意義的，也就是4GB，其實大於100MB也都沒有意義，因為很少有申請內存一次申請100MB空間的，所以你可以看見當i大於20之後，就很少有內存分布落在這裡，這裡統計這個，其實我是想買個關子，後面我會揭示秘密的，嘿嘿。

除了這些最重要的就是申請內存塊的前後mask標誌位了，一旦有其他指針訪問寫越界，就會把mask覆蓋的，即使沒把mask覆蓋也會把block信息覆蓋，這樣必然導致釋放的時候出錯。

至於mask為什麼設置這個值，請大家去維基百科https://en.wikipedia.org/wiki/Hexspeak#Notable_magic_numbers這個網站去查找答案吧

void* VSDebugMem::Allocate (unsigned int uiSize,unsigned int uiAlignment,bool bIsArray){ //申請總大小空間 unsigned int uiExtendedSize = sizeof(Block)+ sizeof(unsigned int) + uiSize + sizeof(unsigned int); char* pcAddr = (char*)malloc(uiExtendedSize); if(!pcAddr) return NULL; //填寫block信息 Block* pBlock = (Block*)pcAddr; pBlock->m_uiSize = uiSize; pBlock->m_bIsArray = bIsArray; bool bAlignment = (uiAlignment > 0) ? true : false; pBlock->m_bAlignment = bAlignment; //插入節點 InsertBlock(pBlock); pcAddr += sizeof(Block); //填寫頭標識 unsigned int * pBeginMask = (unsigned int *)(pcAddr); *pBeginMask = BEGIN_MASK; pcAddr += sizeof(unsigned int); //填寫尾標識 unsigned int * pEndMask = (unsigned int *)(pcAddr + uiSize); *pEndMask = END_MASK; return (void*)pcAddr;}void VSDebugMem::Deallocate (char* pcAddr,unsigned int uiAlignment, bool bIsArray){ if (!pcAddr) { return; } //判斷頭標識 pcAddr -= sizeof(unsigned int); unsigned int *pBeginMask = (unsigned int *)(pcAddr); VSMAC_ASSERT(*pBeginMask == BEGIN_MASK); pcAddr -= sizeof(Block); Block* pBlock = (Block*)pcAddr; VSMAC_ASSERT(pBlock->m_bIsArray == bIsArray); bool bAlignment = (uiAlignment > 0) ? true : false; VSMAC_ASSERT(pBlock->m_bAlignment == bAlignment); //判斷尾標識 unsigned int * pEndMask = (unsigned int *)(pcAddr + sizeof(Block) + sizeof(unsigned int) + pBlock->m_uiSize); VSMAC_ASSERT( *pEndMask == END_MASK); //刪除節點 RemoveBlock(pBlock); free(pcAddr);}void VSDebugMem::InsertBlock (Block* pBlock){ if (m_pTail) { pBlock->m_pPrev = m_pTail; pBlock->m_pNext = 0; m_pTail->m_pNext = pBlock; m_pTail = pBlock; } else { pBlock->m_pPrev = 0; pBlock->m_pNext = 0; m_pHead = pBlock; m_pTail = pBlock; }}void VSDebugMem::RemoveBlock (Block* pBlock){ if (pBlock->m_pPrev) { pBlock->m_pPrev->m_pNext = pBlock->m_pNext; } else { m_pHead = pBlock->m_pNext; } if (pBlock->m_pNext) { pBlock->m_pNext->m_pPrev = pBlock->m_pPrev; } else { m_pTail = pBlock->m_pPrev; }}

插入和刪除節點的代碼我不寫注釋了，很標準的鏈表代碼，看不懂我就要鄙視你了，我給出的申請和釋放內存代碼裡面省略了一些，比如統計數據的代碼，還有多線程訪問的鎖，還是那句話如果我把所有代碼都貼在這本書上，你可能要罵死我，要想看完整版的，還是去看源代碼把。

至今為止，還有一個重要的我沒有講，即使發現錯誤怎麼定位的？怎麼跟蹤到是哪一行代碼？怎麼跟蹤到堆棧信息呢？

這就要依靠微軟的dbhelp這個dll，這個dll裡面包含了可以根據當前指令所在代碼段中的地址列印出這行代碼所在的行數和文件路徑的函數（一行代碼可能對於多條彙編指令），我把這個dll放在了exe可執行目錄下面。

VSStrcat(szDbgName,MAX_PATH,_T("\dbghelp.dll")); // 查找當前目錄的DLL s_DbgHelpLib = LoadLibrary(szDbgName); if(s_DbgHelpLib == NULL) { // 使用系統的DLL s_DbgHelpLib = LoadLibrary(_T("dbghelp.dll")); if(s_DbgHelpLib == NULL) return false; } fnMiniDumpWriteDump = (tFMiniDumpWriteDump)GetProcAddress(s_DbgHelpLib, "MiniDumpWriteDump"); fnSymInitialize = (tFSymInitialize)GetProcAddress(s_DbgHelpLib, "SymInitialize"); fnStackWalk64 = (tFStackWalk64)GetProcAddress(s_DbgHelpLib, "StackWalk64"); fnSymFromAddr = (tFSymFromAddr)GetProcAddress(s_DbgHelpLib, "SymFromAddr"); fnSymGetLineFromAddr64 = (tFSymGetLineFromAddr64)GetProcAddress(s_DbgHelpLib, "SymGetLineFromAddr64"); fnSymGetOptions = (tFSymGetOptions)GetProcAddress(s_DbgHelpLib, "SymGetOptions"); fnSymSetOptions = (tFSymSetOptions)GetProcAddress(s_DbgHelpLib, "SymSetOptions"); fnSymFunctionTableAccess64 = (tFSymFunctionTableAccess64)GetProcAddress(s_DbgHelpLib, "SymFunctionTableAccess64"); fnSymGetModuleBase64 = (tFSymGetModuleBase64)GetProcAddress(s_DbgHelpLib, "SymGetModuleBase64");

上面這些從dll裡面取出的函數其實都很有用，這裡面我只用到了幾個，其他幾個你可以參考MSDN文檔或者去網上搜索，它們到底是幹什麼的。

//得到當前進程static HANDLE s_Process = NULL;DWORD ProcessID = GetCurrentProcessId();s_Process = OpenProcess(PROCESS_ALL_ACCESS, FALSE, ProcessID);fnSymInitialize(s_Process, ".", TRUE);//通過fnSymGetLineFromAddr64得到IMAGEHLP_LINE64的FileName得到函數調用所在的行數和文件名，pAddress是函數地址IMAGEHLP_LINE64 Line;Line.SizeOfStruct = sizeof(Line);VSMemset(&Line, 0, sizeof(Line));DWORD Offset = 0; if(fnSymGetLineFromAddr64(s_Process, (DWORD64)pAddress, &Offset, &Line)) {#ifdef _UNICODE VSMbsToWcs(szFile,MAX_PATH,Line.FileName,MAX_PATH);#else VSStrCopy(szFile, MAX_PATH,Line.FileName);#endif line = Line.LineNumber; }

為了跟蹤代碼調用過程，我不得不扒一扒彙編了，這樣你才知道，代碼在彙編裡面是怎麼調用的，你才知道，上面函數具體有什麼用，也不至於我那段「這個dll裡面包含了可以根據當前指令所在代碼段中的地址列印出這行代碼所在的行數和文件路徑的函數」把你嚇著，是的這句話十分拗口，我不打算分解它了，考考你的語文能力，其實我語文能力也很差。

大家看下面這個函數：

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;}

如果我讓你把上面這段代碼用彙編的形式寫出來，沒有學會用彙編寫代碼的人可能很難辦到，但至少你要知道幾個寄存器以及一些原理，下面我講的才不至於說的是天書，實在想研究明白的，自己找本好點彙編書看看，最好是16位的彙編，再最好有個彙編代碼開發環境，自己練習寫個遞歸函數，基本上你就可以掌握彙編的精髓了(不過vs開發環境支持內嵌彙編，用那個練習也可以，現在都是32位的，很難讓你找到當時dos系統下的感覺)。

我們從s=f(3,4)開始,它的彙編代碼大致是這樣（這是我自己手寫的和彙編編譯的不太一樣，只要基本道理一樣即可）:

push n push mcall fpush bp mov bp sp//保護一系列寄存器，因為算a+b+c的時候要用到這些寄存器，我不能把當前寄存器的值弄//丟了，所以要先存起來，等函數結束後，在把當前值還原回去push bx,cx,dxmov bx [bp+8]mov cx [bp+12]mov dx,2add dx,bxadd dx,cx//編譯器約定俗成的把ax做成返回值，其實如果dx在函數外面沒有用到的話，下面//這句完全可以不寫，然後直接取出dx值 mov ax,dx //彈出一系列寄存器值，還原寄存器原理的值pop dx,cx,bx pop bpret 8

首先壓棧m,n，這個壓棧的順序c和c++是從右到左，而PASCAL則是從左到右，其實哪個順序是無所謂的，每一次壓棧SP都會增加，其實就是棧頂指針。

接下來是call f是讓IP指針(IP裡面存的就是當前運行指令的地址)指到函數的入口地址，這個入口地址是在鏈接時候完成的。

然後是把BP壓入棧中，這裡為什麼要把BP值壓入，一般BP用做棧基指針，因為要使用BP這個寄存器，計算機里的寄存器個數是有限，不保存起來，可能造成值的丟失，所以先把BP的值保存起來，以免丟失，在彈棧時，把這個值在放回BP中，後面的BX等寄存器壓入棧都是這個原理。

圖3.13數據存儲棧的示意圖

mov bp sp，SP是棧頂指針，這時BP就指向了BP寄存器壓入值的位置，就用BP的值來訪問棧里的數據變數，BP+4(之所以加4因為整形佔4個位元組)就指向調用這個函數時候指令IP地址 (函數返回時，IP要接著函數結束的後一條指令執行，這個地方就存儲的這條指令地址)，BP+8就指向m。

函數執行完後要彈棧，按入棧的反方向彈出，然後IP等於調用f函數時候指令的地址，ret 8是告訴系統要把m,n也彈出，8是位元組數。

現在我要做的就是把每次調用函數的指令地址取出來，以上面的例子就是bp+4

那bp指向的寄存器是什麼呢？如果bp沒有被做其他用途，一直做棧基指針（實際上確實如此，這個是約定俗成的）那麼bp指向的寄存器裡面的值，其實就是調用當前函數f的那個函數main的棧基地址，所以*bp+4，就是調用main的指令地址。

DWORD _ebp, _esp; __asm mov _ebp, ebp; __asm mov _esp, esp; for(unsigned int index = 0; index < CALLSTACK_NUM; index++) { void * pAddr = (void*)ULongToPtr(*(((DWORD*)ULongToPtr(_ebp))+1)); if (!pAddr) { break; } pBlock->pAddr[index] = pAddr; pBlock->m_uiStackInfoNum++; _ebp = *(DWORD*)ULongToPtr(_ebp); if(_ebp == 0 || 0 != (_ebp & 0xFC000000) || _ebp < _esp) break; }

圖3.14函數調用的棧基地址

這段代碼唯一需要解釋的是因為程序是32位的，ebp和esp其實表示是32位寄存器，微軟編譯器支持c和c++內嵌彙編，ULongToPtr(_ebp))+1其實和例子裡面+4是一個道理，在32位系統裡面就是加了4個位元組。

通過這種方法，就可以獲得當前調用堆棧代碼地址，根據代碼地址調用fnSymGetLineFromAddr64函數就可以獲得堆棧代碼所在文件的行數和所在文件的名稱。

一旦出現內存泄漏，這樣就可以準確的找到泄漏的整個調用過程。這種查找內存泄漏最好用debug模式。