和大多数内存管理的初衷一致，希望能够控制内存分配和回收，减少内存碎片，且通常这样的内存都会预开一段连续内存空间，然后我们自己来管理这段内存。当然通常这样的需求都很合理，但是实现起来则通常不能完美，比如：效率、算法的选择、如何减少内存碎片、跟踪管理内存分配、性能检测、对系统内存使用的统计、垃圾回收等。下面是我近期实现的一个非常简陋的程序，甚至可能连基本的要求都无法达到，大家帮忙看看，它究竟有多少缺点需要被注意和改进，哪些是无法容忍的？
基本思路是每次分配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;
}