和大多數內存管理的初衷一致，希望能夠控制內存分配和回收，減少內存碎片，且通常這樣的內存都會預開一段連續內存空間，然后我們自己來管理這段內存。當然通常這樣的需求都很合理，但是實現起來則通常不能完美，比如：效率、算法的選擇、如何減少內存碎片、跟蹤管理內存分配、性能檢測、對系統內存使用的統計、垃圾回收等。下面是我近期實現的一個非常簡陋的程序，甚至可能連基本的要求都無法達到，大家幫忙看看，它究竟有多少缺點需要被注意和改進，哪些是無法容忍的？
基本思路是每次分配4M的內存空間（可配置），總共10個這樣的內存塊，通過鏈表（實際的程序中使用map/multimap來提高效率）來管理內存分塊，然后通過修改節點狀態來管理內存塊。
投石問路：希望能夠實現垃圾回收的機制，最大的問題是如何判斷一個對象已經不再被使用了？初步的想法是通過棧地址，找到其上所指的堆地址，對于不在其列的堆地址，將其從堆中移除（標記為待回收）。對以下幾個問題存在疑問：
- 對于一個int ** pp = xxx的對象，它的判斷行為是什么？
- 對于一個MyClass * pObj = new MyClass; pObj->AnotherObj;，它的判斷行為又是什么？
- // ……
對于垃圾回收以及棧和堆的關系不是太了解，找到的資料也十分有限，希望有經驗的朋友能夠提供幫助。
詳細設計：
內存管理
目的
方法
一、固定堆數量（暫定10份），固定每個堆的內存大小（暫定4M），初始堆1個，如果1個堆分配不下，再延伸一個堆，直到分配結束。可以分配的尺寸不超過單個堆的大小，否則返回NULL，分配失敗。
二、凌駕于多個堆之上的數據結構：所有結構可以反查屬于哪個堆。
a) 內存塊尺寸表，一個用于描述所有堆能夠存放的內存塊（chunk）尺寸，尺寸按順序排列。
每個節點應該包含以下信息：
i. 空閑區塊的尺寸；
ii. 空閑區塊所屬的堆；
為了優化查詢搜索，這里將相同尺寸歸并，并列出對應堆和每個堆上該尺寸的區塊的大小：
multimap<Key : Size, Value : struct(heap, count) >
b) 一個用于存放堆信息的數組，數組的大小為固定堆數量。
每個節點應該包含以下信息：
i. 堆的句柄；
1. 連續內存空間的一塊堆內存，用來存儲數據值。
ii. 堆的最大可用區塊空間；
iii. 堆的最小可用區塊空間；
iv. 用于管理堆的內部區域鏈表：
1. 一個完整堆內區塊鏈表，按照地址升序存放。
鏈表的每個節點，代表每一個獨立的內存區塊，區塊是用戶申請的最小粒度。每個節點應該包含以下信息：
a) 區塊的尺寸；
b) 區塊的狀態（未格式化，空閑，占用）；
c) 區塊的首地址指針；
為了優化查詢搜索，這里也可用map：
Map<Key : Offset, Value : struct (size, status, hHeap, pointer)>
三、內部計數器，用于診斷和性能分析，碎片分析
a) 分配次數計數器
b) 分配成功次數計數器
四、如何快速查找可分配區塊，并分配內存？
輸入：預分配區塊尺寸
輸出：指向預分配區塊的指針
1、 如果預分配尺寸大于單塊固定堆尺寸，返回NULL；
2、 查詢內存塊尺寸表，查找最合適的（尺寸>=預分配尺寸的最接近內存塊，如果是大于的情況）內存塊，返回其所屬的堆句柄；
3、 找到對應堆的內部區域鏈表，順序查找最合適的內存塊（條件和前述相同）；作為調試信息的一部分，判斷，如果查找不到該內存塊，則完全同步一次堆剩余尺寸到區域尺寸映射表（如果該方案的失敗率過高，則應該廢除該方法）
4、 針對找到的內存塊執行后續操作（包括：插入鏈表、修改原始節點尺寸/狀態、將內存塊首地址和對應堆更新到映射表中，更新內存塊尺寸表（根據找到的區塊的尺寸和區塊所屬堆來找，將其更新或移除）等）；
5、 返回對應指針。
五、釋放內存塊
輸入：void*內存塊指針
輸出：BOOL
1、 查表確定該內存塊屬于哪個堆？返回堆句柄；
2、 查找該堆對應的完整列表，找到該堆的節點，修改該節點的狀態為Free；
3、 合并相鄰項，[該步驟的執行導致該鏈表中不存在兩塊連續的Free區塊]。
a) 前項檢測：
前一項如果為Free，將前項size+=當前項size，刪除當前項。
b) 后項檢測：（如果前項檢測無結果）
如果后項為Free，將當前項size=size+后項size，刪除后項。
4、 更新內存尺寸表。
5、 更新內存堆映射表。
源碼：
memory_manager_def.h
/*
說明：定義與內存管理相關的常量
*/
#pragma once
#include "stdafx.h"
#include <map>
/*堆的最大數量*/
const size_t MAX_HEAP_COUNT = 10;
/*每一塊堆的尺寸*/
const size_t HEAP_SIZE ((size_t)( 4 * (1024 /** 1024*/)/*MB*/)); // (M)
const unsigned long FRAGMENT_SIZE = 8; // 當小于byte的時候，被定義為碎片
/*同一塊內存區域之間，兩個指針之間的偏移量*/
typedef unsigned long offset_type;
typedef unsigned char* byte_ptr_type;
typedef enum _CHUNK_STATUS{
Unformated,
Free,
Occupied
} CHUNK_STATUS;
memory_manager.h
/*
說明：定義內存管理接口
*/
#pragma once
#include "stdafx.h"
#include "memory_manager_def.h"
#include "trace.h"
#include <map>
typedef struct _free_chunk
{
_free_chunk():hHeap(0), count(0){}
_free_chunk(HANDLE _hHeap, size_t _count):hHeap(_hHeap), count(_count){}
// _free_chunk(const _free_chunk& rChunk);
/*-----members-----*/
HANDLE hHeap;
size_t count;
} free_chunk;
/*內存尺寸表*/
typedef std::multimap<size_t, free_chunk> free_chunk_table_type;
typedef std::pair<free_chunk_table_type::iterator, free_chunk_table_type::iterator> free_chunk_range_type;
typedef std::map<void*, HANDLE> chunk_heap_table_type;
/*chunk：是指一個內存固定區塊內的一個可分配內存區塊*/
typedef struct _chunk_type
{
_chunk_type():size(0), status(Free), hHeap(0), pHead(0){}
size_t size;
/*當前區塊的狀態*/
CHUNK_STATUS status;
/*當前區塊所屬的堆*/
HANDLE hHeap;
/*當前區塊的首地址*/
void* pHead;
} chunk_type;
typedef std::map<offset_type, chunk_type> block_table_type;
typedef enum _CHUNK_INDEX_TYPE
{
BeyondFirst,
Normal,
BeyondLast,
Undefined
} CHUNK_INDEX_TYPE;
/*block：是指一個內存固定區塊*/
typedef struct _block_type
{
_block_type():hHeap(0)
//, max_free_chunk_size(0),min_free_chunk_size(0)
{}
HANDLE hHeap;
///*當前內存塊中剩余的最大塊尺寸（狀態為Free）*/
//size_t max_free_chunk_size;
///*當前內存塊中剩余的最小塊尺寸*/
//size_t min_free_chunk_size;
size_t size;
block_table_type full_list;
/*當前堆的首地址*/
void* pHead;
} block_type;
class memory_manager
{
public:
memory_manager();
virtual ~memory_manager();
void *allocate(size_t size);
void deallocate(void * ptr);
void debug_snapshot(void);
private:
void heap_list_init(void);
void heap_list_i_init(size_t i);
BOOL heap_create_new_one(void);
inline HANDLE heap_create_base(void);
inline BOOL heap_destroy_base(HANDLE hHeap);
inline void* heap_alloc_base(HANDLE hHeap, size_t size=HEAP_SIZE);
inline BOOL heap_dealloc_base(HANDLE hHeap, LPVOID lpMem);
void heap_query_information(HANDLE hHeap);
size_t heap_index(HANDLE hHeap);
CHUNK_INDEX_TYPE prev_chunk(block_table_type &list, int offset, OUT chunk_type * pChunk);
CHUNK_INDEX_TYPE next_chunk(block_table_type &list, int offset, OUT chunk_type * pChunk);
void remove_chunk(block_table_type &list, int heapIndex, int offset);
void free_chunk_list_add(size_t size, HANDLE hHeap);
void free_chunk_list_remove(size_t size, HANDLE hHeap);
BOOL get_available_chunk(IN size_t size, OUT free_chunk* pChunk);
HANDLE which_heap(void * ptr);
void set_chunk_heap(void * ptr, HANDLE hHeap);
void remove_chunk_heap(void *ptr);
private:
block_type heap_list[MAX_HEAP_COUNT];
/*當從程序里返回內存塊的時候，記錄內存塊與堆的對應關系，當釋放的時候，取出對應的堆*/
chunk_heap_table_type chunk_heap_table;
/*一個用于描述所有堆能夠存放的內存塊（chunk）尺寸，尺寸按順序排列。*/
free_chunk_table_type free_chunk_table;
};
trace.h
#ifndef _GC_TRACE_H
#define _GC_TRACE_H
#ifdef _DEBUG
//#define OUTPUT_TO_CONSOLE
void _Trace(LPCWSTR lpszFmt, ...);
void _Trace(LPCSTR lpszFmt, ...);
#define _TRACE _Trace
#define _W(x) (LPCWSTR)_T(x)
#else
#define _TRACE
#define _W(x) x
#endif
#endif
memory_manager.cpp
/*
說明：定義內存管理的實現部分
*/
#include "stdafx.h"
#include "memory_manager.h"
memory_manager::memory_manager()
{
heap_list_init();
}
memory_manager::~memory_manager()
{
for(size_t i = 0; i < MAX_HEAP_COUNT; ++i)
{
if(heap_list[i].hHeap != 0)
{
heap_list[i].size = 0;
heap_dealloc_base(heap_list[i].hHeap, heap_list[i].pHead);
heap_destroy_base(heap_list[i].hHeap);
}
}
}
void *memory_manager::allocate(size_t size)
{
// 1、 如果預分配尺寸大于單塊固定堆尺寸，返回NULL；
if( size > HEAP_SIZE)
{
_TRACE(_W("申請內存尺寸%d > 單區內存最大尺寸%d.\n"), size, HEAP_SIZE);
return 0;
}
else if(size == 0)
{
_TRACE(_W("申請內存尺寸為%d.\n"), size);
return 0;
}
// 2、 查詢內存塊尺寸表，查找最合適的（尺寸>=預分配尺寸的最接近內存塊，如果是大于的情況）內存塊，返回其所屬的堆句柄；
free_chunk freeChunk;
if( !get_available_chunk(size, &freeChunk) )
{
for(size_t i = 0; i < MAX_HEAP_COUNT; ++i)
{
if(heap_list[i].hHeap == 0)
{
heap_list_i_init(i);
return allocate(size);
}
}
return 0;
}
void* mem;
HANDLE hHeap;
size_t removeSize;
// 3、 找到對應堆的內部區域鏈表，順序查找最合適的內存塊（條件和前述相同）；作為調試信息的一部分，判斷，如果查找不到內存塊該內存塊，則完全同步一次堆剩余尺寸到區域尺寸映射表（如果該方案的失敗率過高，則應該廢除該方法）
int index = heap_index(freeChunk.hHeap);
if(index == -1)
{
#ifdef _DEBUG
_TRACE(_W("找不到該堆信息。\n"));
#endif
}
block_table_type *full_list_ptr = &heap_list[index].full_list;
for (block_table_type::iterator it = full_list_ptr->begin();
it != full_list_ptr->end(); ++it)
{
if(it->second.status == Free && it->second.size >= size)
{
if(it->second.size == size)
{
// 4、 針對找到的內存塊執行后續操作（包括：插入鏈表、修改原始節點尺寸/狀態、將內存塊首地址和對應堆更新到映射表中，更新內存塊尺寸表（根據找到的區塊的尺寸和區塊所屬堆來找，將其更新或移除）等）；
it->second.status = Occupied;
mem = it->second.pHead;
hHeap = it->second.hHeap;
removeSize = it->second.size;
// 從內存塊尺寸表中，移除該塊內存
free_chunk_list_remove(removeSize, hHeap);
}
else /*if(it->second.size > size)*/
{
// 4、 針對找到的內存塊執行后續操作（包括：插入鏈表、修改原始節點尺寸/狀態、將內存塊首地址和對應堆更新到映射表中，更新內存塊尺寸表（根據找到的區塊的尺寸和區塊所屬堆來找，將其更新或移除）等）；
int restSize = it->second.size - size;
int originalSize = it->second.size;
int firstChunkOffset = static_cast<byte_ptr_type>(it->second.pHead) - static_cast<byte_ptr_type>(heap_list[index].pHead);
int secondChunkOffset = static_cast<byte_ptr_type>(it->second.pHead) - static_cast<byte_ptr_type>(heap_list[index].pHead) + restSize;
#ifdef _DEBUG
_TRACE(_W("此塊內存塊大小為%d、即將分配%d、分配完后將剩%d、左側空閑塊偏移%d、右側即將分配的塊偏移%d.\n"), originalSize, size, restSize, firstChunkOffset, secondChunkOffset);
#endif
mem = static_cast<void*>(static_cast<byte_ptr_type>(heap_list[index].pHead) + secondChunkOffset);
hHeap = it->second.hHeap;
chunk_type firstChunk, secondChunk;
firstChunk.size = restSize;
firstChunk.status = Free;
firstChunk.hHeap = heap_list[index].hHeap;
firstChunk.pHead = it->second.pHead;
secondChunk.size = size;
secondChunk.status = Occupied;
secondChunk.hHeap = heap_list[index].hHeap;
secondChunk.pHead = static_cast<byte_ptr_type>(it->second.pHead) + restSize;
full_list_ptr->erase(it);
(*full_list_ptr)[firstChunkOffset] = firstChunk;
(*full_list_ptr)[secondChunkOffset] = secondChunk;
// 從內存塊尺寸表中，
// 1、移除原始尺寸模塊；
// 2、增加新的可用內存塊；
free_chunk_list_remove(originalSize, hHeap);
free_chunk_list_add(restSize, hHeap);
}
break;
}
}
// 將當前選中的內存塊存進映射表中
set_chunk_heap(mem, hHeap);
// 5、 返回對應指針。
return mem;
}
void memory_manager::deallocate(void * ptr)
{
// 1、 查表確定該內存塊屬于哪個堆？返回堆句柄；
HANDLE hHeap = which_heap(ptr);
size_t deallocateSize;
if(hHeap == 0)
{
#ifdef _DEBUG
_TRACE(_W("所訪問指針不在可管理的堆中.\n"));
#endif
}
else
{
// 2、 查找該堆對應的完整列表，找到該堆的節點，修改該節點的狀態為Free；
int index = heap_index(hHeap);
int offset = static_cast<byte_ptr_type>(ptr) - static_cast<byte_ptr_type>(heap_list[index].pHead);
deallocateSize = heap_list[index].full_list[offset].size;
#ifdef _DEBUG
_TRACE(_W("刪除的內存塊偏移為%d.\n"), offset);
if( heap_list[index].full_list[offset].hHeap == 0)
{
_TRACE(_W("所訪問的指針在可管理堆中無記錄.\n"));
return;
}
if(heap_list[index].full_list[offset].status != Occupied)
{
_TRACE(_W("所訪問的指針狀態不是已占用，原則上應該是已占用.\n"));
}
#endif
heap_list[index].full_list[offset].status = Free;
// 3、 合并相鄰項，[該步驟的執行導致該鏈表中不存在兩塊連續的Free區塊]。
remove_chunk(heap_list[index].full_list, index, offset);
// 4、 更新內存尺寸表。
// 已經包含在remove_chunk中
// 5、 更新內存堆映射表。
remove_chunk_heap(ptr);
}
}
/*輸出某一瞬間的各列表信息
*/
void memory_manager::debug_snapshot(void)
{
#ifdef _DEBUG
_TRACE(_W("-----------start snapshot-------------\n"));
_TRACE(_W("內存塊尺寸表：\n"));
free_chunk_table_type::const_iterator cIter = free_chunk_table.begin();
int fragmentCounter = 0;
int totalFreeCounter = 0;
for(; cIter != free_chunk_table.end(); ++cIter)
{
_TRACE(_W(" 在Heap=%8x上有Size=%d的塊%d個.\n"), cIter->second.hHeap, cIter->first, cIter->second.count);
++totalFreeCounter;
if(cIter->first <= FRAGMENT_SIZE)
fragmentCounter+=cIter->second.count;
}
_TRACE(_W(" 從“內存塊尺寸表”來看，總共有%d塊空閑內存，其中碎片（<= %d byte）的內存塊有%d個.\n"), totalFreeCounter, FRAGMENT_SIZE, fragmentCounter);
int heapListItemCounter[MAX_HEAP_COUNT] = {};
int heapListItemTotalCounter = 0;
int heapListItemFreeCounter[MAX_HEAP_COUNT] = {};
int heapListItemTotalFreeCounter = 0;
int heapListItemOccupidCounter[MAX_HEAP_COUNT] = {};
int heapListItemTotalOccupidCounter = 0;
int heapListItemFragmentCounter[MAX_HEAP_COUNT] = {};
int heapListItemTotalFragmentCounter = 0;
for(size_t i = 0; i < MAX_HEAP_COUNT; ++i)
{
if(heap_list[i].hHeap != 0)
{
block_table_type * full_list_ptr = &heap_list[i].full_list;
block_table_type::const_iterator cIterList = full_list_ptr->begin();
for(; cIterList != full_list_ptr->end(); ++cIterList)
{
++heapListItemCounter[i];
if(cIterList->second.status == Free)
++heapListItemFreeCounter[i];
else if(cIterList->second.status == Occupied)
++heapListItemOccupidCounter[i];
// 碎片數量
if(cIterList->second.size <= FRAGMENT_SIZE && cIterList->second.status == Free)
++heapListItemFragmentCounter[i];
}
}
}
_TRACE(_W("完全鏈表：\n"));
for(size_t i = 0; i < MAX_HEAP_COUNT; ++i)
{
if(heapListItemFreeCounter[i] + heapListItemOccupidCounter[i] != heapListItemCounter[i])
_TRACE(_W(" ----------內存完全列表可能存在問題！\n"));
_TRACE(_W(" 第%d塊堆擁有%d空閑內存、%d已占內存、%d碎片\n"), i, heapListItemFreeCounter[i], heapListItemOccupidCounter[i], heapListItemFragmentCounter[i]);
heapListItemTotalFreeCounter += heapListItemFreeCounter[i];
heapListItemTotalOccupidCounter +=heapListItemOccupidCounter[i];
heapListItemTotalFragmentCounter +=heapListItemFragmentCounter[i];
heapListItemTotalCounter += heapListItemCounter[i];
}
_TRACE(_W("所有堆中共有%d內存塊、%d空閑內存、%d已占內存、%d碎片\n"),
heapListItemTotalCounter,
heapListItemTotalFreeCounter,
heapListItemTotalOccupidCounter,
heapListItemTotalFragmentCounter);
_TRACE(_W("------------end snapshot-------------\n"));
#endif
}
/*堆初始化（全部）
策略：
1、設置堆列表中的堆句柄為、最大可用尺寸為、最小可用尺寸為、可分配內存首地址為
*/
void memory_manager::heap_list_init(void)
{
for(size_t i = 0; i < MAX_HEAP_COUNT; ++i)
{
heap_list[i].hHeap = 0;
heap_list[i].pHead = 0;
}
}
/*堆初始化（單個）
策略：
1、初始化堆各個字段，并對堆實行完全內存分配。其中堆尺寸、最大最小可用尺寸均為完全分配尺寸
*/
void memory_manager::heap_list_i_init(size_t index)
{
heap_list[index].hHeap = heap_create_base();
heap_list[index].size = HEAP_SIZE;
heap_list[index].pHead = heap_alloc_base(heap_list[index].hHeap, heap_list[index].size);
free_chunk_list_add(HEAP_SIZE, heap_list[index].hHeap);
chunk_type freeChunk;
freeChunk.hHeap = heap_list[index].hHeap;
freeChunk.pHead = heap_list[index].pHead;
freeChunk.size = heap_list[index].size;
freeChunk.status = Free;
heap_list[index].full_list[0] = freeChunk;
}
BOOL memory_manager::heap_create_new_one(void)
{
for(size_t i = 0; i < MAX_HEAP_COUNT; ++i)
{
if(heap_list[i].hHeap == 0)
{
heap_list_i_init(i);
return TRUE;
}
return FALSE;
}
return FALSE;
}
#pragma region heap func
/*創建堆對象
策略：
1、創建一個固定大小的堆
2、啟用LFH以減小內存碎片（如果允許的話）
*/
inline HANDLE memory_manager::heap_create_base(void)
{
/*The HeapCreate function rounds dwMaximumSize up to the next page boundary, and then reserves a block of that size in the process's virtual address space for the heap. If allocation requests made by the HeapAlloc or HeapReAlloc functions exceed the size specified by dwInitialSize, the system commits additional pages of memory for the heap, up to the heap's maximum size. If dwMaximumSize is not zero, the heap size is fixed and cannot grow. The largest memory block that can be allocated from the heap is slightly less than 0x7FFF8 bytes. Requests to allocate larger blocks fail, even if the maximum size of the heap is large enough to contain the block. */
HANDLE hHeap = HeapCreate(HEAP_CREATE_ENABLE_EXECUTE, HEAP_SIZE, 0/*growable*/);
// 啟用LFH（ms-help://MS.VSCC.v90/MS.MSDNQTR.v90.chs/memory/base/low_fragmentation_heap.htm）
// 以減少內存碎片
#ifdef _DEBUG
heap_query_information(hHeap);
#endif
ULONG HeapFragValue = 2L;
// 如果啟用LFH不成功
if(!HeapSetInformation(hHeap, HeapEnableTerminationOnCorruption, &HeapFragValue, sizeof(HeapFragValue)))
{
_TRACE(_W("LFH is unabled. Error code is %d\n"), GetLastError());
}
#ifdef _DEBUG
heap_query_information(hHeap);
#endif
return hHeap;
}
/*釋放堆對象*/
inline BOOL memory_manager::heap_destroy_base(HANDLE hHeap)
{
return HeapDestroy(hHeap);
}
/*申請內存塊
策略：
*/
inline void* memory_manager::heap_alloc_base(HANDLE hHeap, size_t size)
{
void* mem = HeapAlloc(hHeap, HEAP_ZERO_MEMORY, size);
#ifdef _DEBUG
if(NULL == mem)
{
_TRACE(_W("HeapAlloc error. Error code is %d\n"), GetLastError());
}
#endif
return mem;
}
/*釋放內存塊
參數：
hHeap：堆句柄
lpMem：首地址
*/
inline BOOL memory_manager::heap_dealloc_base(HANDLE hHeap, LPVOID lpMem)
{
return HeapFree(hHeap, 0, lpMem);
}
/*查找某個堆屬于堆列表中的第幾個
*/
size_t memory_manager::heap_index(HANDLE hHeap)
{
for(size_t i = 0; i < MAX_HEAP_COUNT; ++i)
{
if( heap_list[i].hHeap == hHeap )
return i;
}
return -1;
}
CHUNK_INDEX_TYPE memory_manager::prev_chunk(block_table_type &list, int offset, OUT chunk_type * pChunk)
{
if(pChunk == 0)
return Undefined;
if(list[offset].hHeap == 0)
return Undefined;
block_table_type::iterator it = list.find(offset);
if(it == list.begin())
return BeyondFirst;
if(it == list.end())
return Undefined;
block_table_type::iterator itPrev = --it;
++it;
pChunk->hHeap = (itPrev)->second.hHeap;
pChunk->pHead = (itPrev)->second.pHead;
pChunk->size = (itPrev)->second.size;
pChunk->status = (itPrev)->second.status;
return Normal;
}
CHUNK_INDEX_TYPE memory_manager::next_chunk(block_table_type &list, int offset, OUT chunk_type * pChunk)
{
if(pChunk == 0)
return Undefined;
if(list[offset].hHeap == 0)
return Undefined;
block_table_type::iterator it = list.find(offset);
if(it == list.end())
return Undefined;
block_table_type::iterator itNext = ++it;
--it;
if(itNext == list.end())
return BeyondLast;
pChunk->hHeap = (itNext)->second.hHeap;
pChunk->pHead = (itNext)->second.pHead;
pChunk->size = (itNext)->second.size;
pChunk->status = (itNext)->second.status;
return Normal;
}
void memory_manager::remove_chunk(block_table_type &list, int heapIndex, int offset)
{
// a) 前項檢測：
// 前一項如果為Free，將前項size+=當前項size，刪除當前項。
chunk_type prevFreeChunk;
if( prev_chunk(heap_list[heapIndex].full_list, offset, &prevFreeChunk) != BeyondFirst)
{
if(prevFreeChunk.status == Free)
{
int prevOffset = static_cast<byte_ptr_type>(prevFreeChunk.pHead) - static_cast<byte_ptr_type>(heap_list[heapIndex].pHead);
free_chunk_list_remove(heap_list[heapIndex].full_list[prevOffset].size, heap_list[heapIndex].hHeap);
heap_list[heapIndex].full_list[prevOffset].size += heap_list[heapIndex].full_list[offset].size;
free_chunk_list_add(heap_list[heapIndex].full_list[prevOffset].size, heap_list[heapIndex].hHeap);
heap_list[heapIndex].full_list.erase(offset);
#ifdef _DEBUG
_TRACE(_W("執行前項檢測且前項狀態為空閑，可執行合并。前項偏移為%d\n"), prevOffset);
#endif
return;
}
}
chunk_type nextFreeChunk;
// b) 后項檢測：（如果前項檢測無結果）
// 如果后項為Free，將當前項size=size+后項size，刪除后項。
if( next_chunk(heap_list[heapIndex].full_list, offset, &nextFreeChunk) != BeyondLast)
{
if(nextFreeChunk.status == Free)
{
int nextOffset = static_cast<byte_ptr_type>(nextFreeChunk.pHead) - static_cast<byte_ptr_type>(heap_list[heapIndex].pHead);
free_chunk_list_remove(heap_list[heapIndex].full_list[nextOffset].size, heap_list[heapIndex].hHeap);
heap_list[heapIndex].full_list[offset].size += heap_list[heapIndex].full_list[nextOffset].size;
free_chunk_list_add(heap_list[heapIndex].full_list[offset].size, heap_list[heapIndex].hHeap);
heap_list[heapIndex].full_list.erase(nextOffset);
#ifdef _DEBUG
_TRACE(_W("執行后項檢測且后項狀態為空閑，可執行合并。后項偏移為%d\n"), nextOffset);
#endif
return;
}
}
free_chunk_list_add(heap_list[heapIndex].full_list[offset].size, heap_list[heapIndex].hHeap);
}
/*
查詢堆信息，輔助調試，可以查看當前堆的特性
*/
void memory_manager::heap_query_information(HANDLE hHeap)
{
ULONG heapInfo;
SIZE_T returnLength;
if(!HeapQueryInformation(hHeap, HeapCompatibilityInformation, &heapInfo, sizeof(ULONG), &returnLength))
{
_TRACE(_W("HeapInformation:%d, returnLength:%d.Error code is %d\n"), heapInfo, returnLength, GetLastError());
}
else
{
_TRACE(_W("HeapInformation:%d, returnLength:%d.\n"), heapInfo, returnLength);
}
}
#pragma endregion
/*向內存尺寸表中添加尺寸信息
test:
free_chunk_list_add(50, (HANDLE)0);
free_chunk_list_add(50, (HANDLE)0);
free_chunk_list_add(10, (HANDLE)1);
free_chunk_list_add(20, (HANDLE)3);
free_chunk_list_add(20, (HANDLE)0);
free_chunk_list_add(10, (HANDLE)1);
free_chunk_list_add(70, (HANDLE)3);
free_chunk_list_add(50, (HANDLE)2);
*/
void memory_manager::free_chunk_list_add(size_t size, HANDLE hHeap)
{
free_chunk_range_type range = free_chunk_table.equal_range(size);
// if not found.
if(range.first == range.second)
{
free_chunk freeChunk;
freeChunk.count = 1;
freeChunk.hHeap = hHeap;
free_chunk_table.insert(std::make_pair(size, freeChunk)); // copy
return;
}
// if found.
for(free_chunk_table_type::iterator i = range.first; i != range.second; ++i)
{
if(i->second.hHeap == hHeap)
{
i->second.count = i->second.count + 1;
return;
}
}
// 否則如果沒有找到該堆所對應的相同尺寸的信息
free_chunk freeChunk;
freeChunk.count = 1;
freeChunk.hHeap = hHeap;
free_chunk_table.insert(std::make_pair(size, freeChunk)); // copy
}
/*從內存尺寸表中移除尺寸信息
test:
free_chunk_list_remove(50, (HANDLE)0);
free_chunk_list_remove(50, (HANDLE)0);
free_chunk_list_remove(10, (HANDLE)1);
free_chunk_list_remove(20, (HANDLE)3);
free_chunk_list_remove(20, (HANDLE)0);
free_chunk_list_remove(10, (HANDLE)1);
free_chunk_list_remove(70, (HANDLE)3);
free_chunk_list_remove(50, (HANDLE)2);
*/
void memory_manager::free_chunk_list_remove(size_t size, HANDLE hHeap)
{
free_chunk_range_type range = free_chunk_table.equal_range(size);
// if not found.
if(range.first == range.second)
{
#ifdef _DEBUG
_TRACE(_W("從內存尺寸表中查找size=%d的內存時候，無法找到記錄.\n"), size);
#endif // _DEBUG
}
// if found.
for(free_chunk_table_type::iterator i = range.first; i != range.second; ++i)
{
if(i->second.hHeap == hHeap)
{
i->second.count = i->second.count - 1;
if(i->second.count == 0)
{
free_chunk_table.erase(i);
}
return;
}
}
#ifdef _DEBUG
_TRACE(_W("從內存尺寸表中查找size=%d的內存時候，無法找到記錄.\n"), size);
#endif // _DEBUG
}
/*通過可用鏈表查詢可用的內存區塊
策略：
1、遍歷可用區塊鏈表（該鏈表已經按尺寸從小到大順序排列）
2、尋找可用
*/
BOOL memory_manager::get_available_chunk(IN size_t size, OUT free_chunk* pChunk)
{
free_chunk_table_type::iterator fct_iter;
for(fct_iter = free_chunk_table.begin();
fct_iter != free_chunk_table.end(); ++fct_iter)
{
size_t available_size = (*fct_iter).first;
if(available_size >= size)
{
*pChunk = (*fct_iter).second;
return TRUE;
}
else
{
#ifdef _DEBUG
_TRACE(_W("找不到合適大小的內存塊.\n"));
#endif
}
}
return FALSE;
}
/*某個任意指針屬于哪個堆，返回值為表示不是在堆列表中的堆
策略：
1、本設計中存在返回指針以及所屬指針的字典映射
2、通過查表法找出當前指針所屬的堆信息
*/
HANDLE memory_manager::which_heap(void * ptr)
{
HANDLE hHeap = chunk_heap_table[ptr];
if( NULL == hHeap )
{
_TRACE(_W("該指針不屬于任意內存塊.\n"));
return 0;
}
else
{
#ifdef _DEBUG
_TRACE(_W("當前使用的指針來自第%d塊堆.\n"), heap_index(hHeap));
#endif
return hHeap;
}
}
/*將指針和對應堆信息存進字典備查
策略：
1、本設計中存在返回指針以及所屬指針的字典映射
2、以指針作為鍵值，將對應堆句柄作為值
*/
void memory_manager::set_chunk_heap(void * ptr, HANDLE hHeap)
{
#ifdef _DEBUG
if(chunk_heap_table[ptr] != 0)
{
_TRACE(_W("在此之前已經有相同的指針存在于表中，還未釋放.\n"));
return;
}
#endif
chunk_heap_table[ptr] = hHeap;
}
/*將指針和對應堆信息移出字典
策略：
1、本設計中存在返回指針以及所屬指針的字典映射
2、當該指針作廢后，此處移走對應項
*/
void memory_manager::remove_chunk_heap(void *ptr)
{
#ifdef _DEBUG
HANDLE hHeap = which_heap(ptr);
#endif
chunk_heap_table.erase(ptr);
#ifdef _DEBUG
_TRACE(_W("指針%p已經從第%d塊堆中移除.\n"), ptr, heap_index( hHeap ));
#endif
}
memory_manager_main.cpp
// memory_manager.cpp : 定義控制臺應用程序的入口點。
//
#include "stdafx.h"
#include "memory_manager.h"
#include <iostream>
#include <vector>
void run(void)
{
memory_manager mm;
std::vector<void *> pointers;
int totalMemory = 0;
int max = 0;
int curr = 0;
for(int i = 1; i < HEAP_SIZE * 11; i+=(sizeof(int)))
{
_TRACE(_W("開始申請%d大小的內存\n"), i);
void * mem = mm.allocate(sizeof(int));
if(mem != 0)
pointers.push_back(mem);
else
break;
int *p = (int *)mem;
*p = i;
mm.debug_snapshot();
totalMemory += i;
if(max < i)
max = i;
_TRACE(_W("--------%d---------\n"), ++curr);
}
_TRACE(_W("累計申請內存數量%d、申請%d次、申請的最大內存為%d。\n"), totalMemory, curr, max);
mm.debug_snapshot();
_TRACE(_W("====================開始釋放內存。\n"));
std::vector<void *>::const_iterator cIter = pointers.begin();
for(; cIter != pointers.end(); ++cIter)
{
int *p = static_cast<int *>(*cIter);
std::cout << *p << " ";
mm.deallocate(*cIter);
mm.debug_snapshot();
_TRACE(_W("--------%d---------\n"), --curr);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
run();
getchar();
return 0;
}
trace.cpp
#include "stdafx.h"
#include "trace.h"
void _Trace(LPCWSTR lpszFmt, ...)
{
va_list args;
va_start(args, lpszFmt);
int len = _vscwprintf(lpszFmt, args) + 1;
wchar_t* lpszBuf = new wchar_t[len];
vswprintf_s(lpszBuf, len, lpszFmt, args);
va_end(args);
OutputDebugStringW(lpszBuf);
#ifdef OUTPUT_TO_CONSOLE
wprintf(lpszBuf);
#endif
delete[] lpszBuf;
}
void _Trace(LPCSTR lpszFmt, ...)
{
va_list args;
va_start(args, lpszFmt);
int len = _vscprintf(lpszFmt, args) + 1;
char* lpszBuf = new char[len];
vsprintf_s(lpszBuf, len, lpszFmt, args);
va_end(args);
OutputDebugStringA(lpszBuf);
#ifdef OUTPUT_TO_CONSOLE
printf(lpszBuf);
#endif
delete[] lpszBuf;
}