MyMSDN

MyMSDN记录开发新知道

[C++]内存管理(1)

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

基本思路是每次分配4M的内存空间(可配置),总共10个这样的内存块,通过链表(实际的程序中使用map/multimap来提高效率)来管理内存分块,然后通过修改节点状态来管理内存块。

投石问路:希望能够实现垃圾回收的机制,最大的问题是如何判断一个对象已经不再被使用了?初步的想法是通过栈地址,找到其上所指的堆地址,对于不在其列的堆地址,将其从堆中移除(标记为待回收)。对以下几个问题存在疑问:

  1. 对于一个int ** pp = xxx的对象,它的判断行为是什么?
  2. 对于一个MyClass * pObj = new MyClass; pObj->AnotherObj;,它的判断行为又是什么?
  3. // ……

对于垃圾回收以及栈和堆的关系不是太了解,找到的资料也十分有限,希望有经验的朋友能够提供帮助。

详细设计:

内存管理

目的

方法

一、固定堆数量(暂定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;  
}

posted on 2010-07-06 22:45 volnet 阅读(3785) 评论(17)  编辑 收藏 引用 所属分类: C/C++

评论

# re: [C++]内存管理(1) 2010-07-06 23:29 OwnWaterloo

请教一下: 这个排版是怎么做的? live writter?  回复  更多评论   

# re: [C++]内存管理(1) 2010-07-06 23:34 volnet

@OwnWaterloo
嗯,样式上,我自己有定义了几个简单的样式。windows live writer+vspaste插件用来贴代码。黄色部分的详细设计,是我之前在Word写好的,直接贴过来,可能样式略有变化。
  回复  更多评论   

# re: [C++]内存管理(1) 2010-07-06 23:34 volnet

源代码下载:
http://www.cppblog.com/Files/mymsdn/memory_manager.rar  回复  更多评论   

# re: [C++]内存管理(1) 2010-07-07 00:08 OwnWaterloo

@volnet
详细设计部分在cppblog上调整过样式吧?
我见过一个白色的页面, 过段时间刷新后, 就变黄色了。
很用心~
  回复  更多评论   

# re: [C++]内存管理(1) 2010-07-07 08:58 volnet

@OwnWaterloo
希望您多指教啊  回复  更多评论   

# re: [C++]内存管理(1) 2010-07-07 09:48 pcm

既然“通过栈地址,找到其上所指的堆地址,对于不在其列的堆地址,将其从堆中移除”,那么就没必要自己管理内存了,程序要用内存的时候直接从栈上分配就行了,也不会有碎片。  回复  更多评论   

# re: [C++]内存管理(1) 2010-07-07 10:18 zuhd

1,“最大的问题是如何判断一个对象已经不再被使用了”
自己分配的内存,自己不知道什么时候释放吗?
2,“初步的想法是通过栈地址,找到其上所指的堆地址,对于不在其列的堆地址,将其从堆中移除(标记为待回收)”
这句话的意思是?  回复  更多评论   

# re: [C++]内存管理(1) 2010-07-07 10:30 volnet

@pcm
我的意思是,在堆中,存放的是一个对象的真实内容,在栈中存在的是存放对象内容的堆的地址,也就是一个int *p,这样,那么如果p的值在已经不在栈中了,也就是我这个管理器中还存有这个地址的相关内存的话,其实这块内存将不再被引用,就被标记为垃圾了。  回复  更多评论   

# re: [C++]内存管理(1) 2010-07-07 10:31 volnet

@zuhd
1、就像new和delete所面临的挑战一样,我们能保证用的时候去分配,但是通常可能因为一些原因忘记去释放这块内存,比如你已经很小心了,但是异常出现的时候,可能delete并没有执行。
2、详见上一条回复  回复  更多评论   

# re: [C++]内存管理(1) 2010-07-07 15:08 volnet

移除prev_chunk,next_chunk,新增near_chunk,修改remove_chunk
方法有更新,更新内容:

BOOL memory_manager::near_chunk(block_table_type &list, int offset, OUT chunk_type * prevChunk, OUT chunk_type * nextChunk)
{
block_table_type::iterator itPrev;
block_table_type::iterator itNext;

if(prevChunk == 0 || nextChunk == 0)
return FALSE;
else
{
prevChunk->status = Occupied;
nextChunk->status = Occupied;
}
if(list[offset].hHeap == 0)
return FALSE;
block_table_type::iterator it = list.find(offset);
if(it == list.end())
return FALSE;

itPrev = list.end();
itNext = list.end();

if(it != list.begin())
{
itPrev = --it;
++it;
}

if(it != list.end())
{
itNext = ++it;
--it;
}

if(itPrev != list.end())
{
prevChunk->hHeap = (itPrev)->second.hHeap;
prevChunk->pHead = (itPrev)->second.pHead;
prevChunk->size = (itPrev)->second.size;
prevChunk->status = (itPrev)->second.status;
}

if(itNext != list.end())
{
nextChunk->hHeap = (itNext)->second.hHeap;
nextChunk->pHead = (itNext)->second.pHead;
nextChunk->size = (itNext)->second.size;
nextChunk->status = (itNext)->second.status;
}
if(itPrev != list.end() || itNext != list.end())
return TRUE;
return FALSE;
}
void remove_chunk(int heapIndex, int offset)
{
chunk_type prevFreeChunk, nextFreeChunk;
if( near_chunk(heap_list[heapIndex].full_list, offset, &prevFreeChunk, &nextFreeChunk) )
{
// a) 前项检测:
// 前一项如果为Free,将前项size+=当前项size,删除当前项。
if(prevFreeChunk.status == Free && nextFreeChunk.status != Free)
{
int prevOffset = static_cast(prevFreeChunk.pHead) - static_cast(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);
int eraseSucceed = heap_list[heapIndex].full_list.erase(offset);
#ifdef _DEBUG
// 如果移除偏移不等于1个
if( eraseSucceed != 1)
{
_TRACE(_W("从完全列表中移除对象出现异常,移除offset为%d,移除个数为%d.\n"), offset, eraseSucceed);
}
_TRACE(_W("执行前项检测且前项状态为空闲,可执行合并。前项偏移为%d\n"), prevOffset);
#endif
}

// b) 后项检测:
// 如果后项为Free,将当前项size=size+后项size,删除后项。
else if(prevFreeChunk.status != Free && nextFreeChunk.status == Free)
{
int nextOffset = static_cast(nextFreeChunk.pHead) - static_cast(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);
int eraseSucceed = heap_list[heapIndex].full_list.erase(nextOffset);
#ifdef _DEBUG
// 如果移除偏移不等于1个
if( eraseSucceed != 1)
{
_TRACE(_W("从完全列表中移除对象出现异常,移除nextOffset为%d,移除个数为%d.\n"), nextOffset, eraseSucceed);
}
_TRACE(_W("执行后项检测且后项状态为空闲,可执行合并。后项偏移为%d\n"), nextOffset);
#endif
return;
}

// c) 前后项检测:
else if(prevFreeChunk.status == Free && nextFreeChunk.status == Free)
{
int prevOffset = static_cast(prevFreeChunk.pHead) - static_cast(heap_list[heapIndex].pHead);
int nextOffset = static_cast(nextFreeChunk.pHead) - static_cast(heap_list[heapIndex].pHead);
free_chunk_list_remove(heap_list[heapIndex].full_list[nextOffset].size, heap_list[heapIndex].hHeap);
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[prevOffset].size
+ heap_list[heapIndex].full_list[offset].size
+ heap_list[heapIndex].full_list[nextOffset].size;
free_chunk_list_add(heap_list[heapIndex].full_list[prevOffset].size, heap_list[heapIndex].hHeap);
int eraseSucceed = heap_list[heapIndex].full_list.erase(offset);
eraseSucceed += heap_list[heapIndex].full_list.erase(nextOffset);
#ifdef _DEBUG
// 如果移除偏移不等于2个
if( eraseSucceed != 2)
{
_TRACE(_W("从完全列表中移除对象出现异常,移除offset为%d,移除nextOffset为%d,移除个数为%d.\n"), offset, nextOffset, eraseSucceed);
}
_TRACE(_W("执行前后项检测且前后项状态为空闲,可执行合并。\n"));
#endif
return;
}
// d) 前后项检测:
else if(prevFreeChunk.status == Occupied && nextFreeChunk.status == Occupied)
{
free_chunk_list_add(heap_list[heapIndex].full_list[offset].size, heap_list[heapIndex].hHeap);
}
else
{
_TRACE(_W("该情况不在考虑范围内。\n"));
}
}
else
{
free_chunk_list_add(heap_list[heapIndex].full_list[offset].size, heap_list[heapIndex].hHeap);
}
}  回复  更多评论   

# re: [C++]内存管理(1) 2010-07-07 15:15 volnet

已经更新下载代码中的测试用例,现在的测试更加复杂,更具有一般性,欢迎大家下载体验,程序有些许改动,详见上一条回复:
[移除prev_chunk,next_chunk,新增near_chunk,修改remove_chunk]
源代码下载地址不变。
源代码下载:
http://www.cppblog.com/Files/mymsdn/memory_manager.rar  回复  更多评论   

# re: [C++]内存管理(1) 2010-07-08 10:51 zuhd

@volnet
1,那你说的这个是智能指针,貌似与你的主题有点偏离,好吧,就算加入智能指针,那么你要自己写这个智能指针了,以为你的析构并不是把内存回收给系统,而是回收到池。
2,在堆中分配内存的地址,你保存到哪里不重要,只是个数据而已。重要的是你想做智能指针,那么你就要做引用计数,参考vczh的一片文章吧。
另:参考SGI的stl的allocator,对你有帮助的  回复  更多评论   

# re: [C++]内存管理(1) 2010-07-08 11:07 volnet

@zuhd
感谢您的回复。
1、我和智能指针要解决的应该是相同的问题,另外我还希望能够解决一些碎片相关的问题,虽然现在还没有做具体的代码和设计。但是如果我接管了new或者部分new的话,我就有办法去管理它们,并且动一点手脚了。现在关于是否每个分配都有正确的释放,这一点我暂时不做太多考虑了,我们现在基本用shared_ptr来做,这里就有一个问题了,我希望用我的内存分配机制去替换shared_ptr的对象存储。考虑下面的代码shared_ptr sp_(new MyClass()); 其实内存还是通过默认的operator new去分配的内存,这个内存通常是直接向操作系统去调用的,我现在希望有一块较大的内存,然后所有小块的内存分配我都希望自己来管理,而不用每次都向操作系统申请。但是现在shared_ptr在发挥作用前就已经通过new去做了内存分配,显然我自造shared_ptr是无法解决这个问题的。我不知道有没有办法转存那块内存,并立即释放掉,比如在内部通过memmove将向系统new出来的部分拷贝到我的构造中,然后将它们释放,这样我就不用替换全局的new来管理与shared_ptr有关的内存了。因为我们的代码中大部分用到了shared_ptr,所以此法能解决比较多的问题。
2、是否有其他的建议呢?  回复  更多评论   

# re: [C++]内存管理(1) 2010-07-08 11:08 volnet

@zuhd
因为我的代码用到STL的东西,所以现在替换全局new,似乎还有问题……悲剧  回复  更多评论   

# re: [C++]内存管理(1) 2010-07-08 14:11 立清

SGI STL memory allocator源码对memory pool有很好的实现。  回复  更多评论   

# re: [C++]内存管理(1) 2010-07-09 10:34 zuhd

@volnet
但是现在shared_ptr在发挥作用前就已经通过new去做了内存分配,显然我自造shared_ptr是无法解决这个问题的。

So....?
1,从系统获得的内存你来管理,不管是申请还是释放
2,你实现一个智能指针,他暴露出来的仅仅是智能,也就是说他的内存释放是不用关心的,至于智能指针的内存是从系统获得的还是从你的池中获得的,别于外面是不可知的,也是无需关心的
所以这两个概念不能搞混淆了,也许你最终实现的是一个在内存池的基础上造一个智能指针

  回复  更多评论   

# re: [C++]内存管理(1) 2010-08-29 17:29 evening dresses

的机制,最大的问题是如何判断一个对象已经不再被使用了?初步的想法是通过栈地址,找到其上所指的堆地址,对于不在其列的堆地址,将其从堆中移除(标记为待回收)。对以下几个问题存在疑问:  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


特殊功能