MyMSDN

[C++]內(nèi)存管理（1）

和大多數(shù)內(nèi)存管理的初衷一致，希望能夠控制內(nèi)存分配和回收，減少內(nèi)存碎片，且通常這樣的內(nèi)存都會(huì)預(yù)開一段連續(xù)內(nèi)存空間，然后我們自己來(lái)管理這段內(nèi)存。當(dāng)然通常這樣的需求都很合理，但是實(shí)現(xiàn)起來(lái)則通常不能完美，比如：效率、算法的選擇、如何減少內(nèi)存碎片、跟蹤管理內(nèi)存分配、性能檢測(cè)、對(duì)系統(tǒng)內(nèi)存使用的統(tǒng)計(jì)、垃圾回收等。下面是我近期實(shí)現(xiàn)的一個(gè)非常簡(jiǎn)陋的程序，甚至可能連基本的要求都無(wú)法達(dá)到，大家?guī)兔纯矗烤褂卸嗌偃秉c(diǎn)需要被注意和改進(jìn)，哪些是無(wú)法容忍的？

基本思路是每次分配4M的內(nèi)存空間（可配置），總共10個(gè)這樣的內(nèi)存塊，通過鏈表（實(shí)際的程序中使用map/multimap來(lái)提高效率）來(lái)管理內(nèi)存分塊，然后通過修改節(jié)點(diǎn)狀態(tài)來(lái)管理內(nèi)存塊。

投石問路：希望能夠?qū)崿F(xiàn)垃圾回收的機(jī)制，最大的問題是如何判斷一個(gè)對(duì)象已經(jīng)不再被使用了？初步的想法是通過棧地址，找到其上所指的堆地址，對(duì)于不在其列的堆地址，將其從堆中移除（標(biāo)記為待回收）。對(duì)以下幾個(gè)問題存在疑問：

1. 對(duì)于一個(gè)int ** pp = xxx的對(duì)象，它的判斷行為是什么？
2. 對(duì)于一個(gè)MyClass * pObj = new MyClass; pObj->AnotherObj;，它的判斷行為又是什么？
3. // ……

對(duì)于垃圾回收以及棧和堆的關(guān)系不是太了解，找到的資料也十分有限，希望有經(jīng)驗(yàn)的朋友能夠提供幫助。

詳細(xì)設(shè)計(jì)：

源碼：

memory_manager_def.h

/*
說(shuō)明：定義與內(nèi)存管理相關(guān)的常量
*/

#pragma once

#include "stdafx.h"
#include <map>

/*堆的最大數(shù)量*/
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; // 當(dāng)小于byte的時(shí)候，被定義為碎片

/*同一塊內(nèi)存區(qū)域之間，兩個(gè)指針之間的偏移量*/
typedef unsigned long offset_type;
typedef unsigned char* byte_ptr_type;

typedef enum _CHUNK_STATUS{ 
    Unformated,
    Free,
    Occupied
} CHUNK_STATUS;

memory_manager.h

/*
說(shuō)明：定義內(nèi)存管理接口
*/

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

/*內(nèi)存尺寸表*/
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：是指一個(gè)內(nèi)存固定區(qū)塊內(nèi)的一個(gè)可分配內(nèi)存區(qū)塊*/
typedef struct _chunk_type
{
    _chunk_type():size(0), status(Free), hHeap(0), pHead(0){}
    size_t size;
    /*當(dāng)前區(qū)塊的狀態(tài)*/
    CHUNK_STATUS status;
    /*當(dāng)前區(qū)塊所屬的堆*/
    HANDLE hHeap;
    /*當(dāng)前區(qū)塊的首地址*/
    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：是指一個(gè)內(nèi)存固定區(qū)塊*/
typedef struct _block_type
{
    _block_type():hHeap(0)
        //, max_free_chunk_size(0),min_free_chunk_size(0)
    {}
    HANDLE hHeap;
    ///*當(dāng)前內(nèi)存塊中剩余的最大塊尺寸（狀態(tài)為Free）*/
    //size_t max_free_chunk_size;
    ///*當(dāng)前內(nèi)存塊中剩余的最小塊尺寸*/
    //size_t min_free_chunk_size;
    size_t size;
    block_table_type full_list;
    /*當(dāng)前堆的首地址*/
    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];
    /*當(dāng)從程序里返回內(nèi)存塊的時(shí)候，記錄內(nèi)存塊與堆的對(duì)應(yīng)關(guān)系，當(dāng)釋放的時(shí)候，取出對(duì)應(yīng)的堆*/
    chunk_heap_table_type chunk_heap_table;
    /*一個(gè)用于描述所有堆能夠存放的內(nèi)存塊（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

/*
說(shuō)明：定義內(nèi)存管理的實(shí)現(xiàn)部分
*/
#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、    如果預(yù)分配尺寸大于單塊固定堆尺寸，返回NULL；
    if( size > HEAP_SIZE)
    {
        _TRACE(_W("申請(qǐng)內(nèi)存尺寸%d > 單區(qū)內(nèi)存最大尺寸%d.\n"), size, HEAP_SIZE);
        return 0;
    }
    else if(size == 0)
    {
        _TRACE(_W("申請(qǐng)內(nèi)存尺寸為%d.\n"), size);
        return 0;
    }

    // 2、    查詢內(nèi)存塊尺寸表，查找最合適的（尺寸>=預(yù)分配尺寸的最接近內(nèi)存塊，如果是大于的情況）內(nèi)存塊，返回其所屬的堆句柄；
    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、    找到對(duì)應(yīng)堆的內(nèi)部區(qū)域鏈表，順序查找最合適的內(nèi)存塊（條件和前述相同）；作為調(diào)試信息的一部分，判斷，如果查找不到內(nèi)存塊該內(nèi)存塊，則完全同步一次堆剩余尺寸到區(qū)域尺寸映射表（如果該方案的失敗率過高，則應(yīng)該廢除該方法）
    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、    針對(duì)找到的內(nèi)存塊執(zhí)行后續(xù)操作（包括：插入鏈表、修改原始節(jié)點(diǎn)尺寸/狀態(tài)、將內(nèi)存塊首地址和對(duì)應(yīng)堆更新到映射表中，更新內(nèi)存塊尺寸表（根據(jù)找到的區(qū)塊的尺寸和區(qū)塊所屬堆來(lái)找，將其更新或移除）等）；
               
                it->second.status = Occupied;
                mem = it->second.pHead;
                hHeap = it->second.hHeap;
                removeSize = it->second.size;

                // 從內(nèi)存塊尺寸表中，移除該塊內(nèi)存
                free_chunk_list_remove(removeSize, hHeap);
            }
            else /*if(it->second.size > size)*/
            {
                // 4、    針對(duì)找到的內(nèi)存塊執(zhí)行后續(xù)操作（包括：插入鏈表、修改原始節(jié)點(diǎn)尺寸/狀態(tài)、將內(nèi)存塊首地址和對(duì)應(yīng)堆更新到映射表中，更新內(nèi)存塊尺寸表（根據(jù)找到的區(qū)塊的尺寸和區(qū)塊所屬堆來(lái)找，將其更新或移除）等）；
                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("此塊內(nèi)存塊大小為%d、即將分配%d、分配完后將剩%d、左側(cè)空閑塊偏移%d、右側(cè)即將分配的塊偏移%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;

                // 從內(nèi)存塊尺寸表中，
                // 1、移除原始尺寸模塊；
                // 2、增加新的可用內(nèi)存塊；
                free_chunk_list_remove(originalSize, hHeap);
                free_chunk_list_add(restSize, hHeap);
            }
            break;
        }
    }

    // 將當(dāng)前選中的內(nèi)存塊存進(jìn)映射表中
    set_chunk_heap(mem, hHeap);

    // 5、    返回對(duì)應(yīng)指針。
    return mem;
}

void memory_manager::deallocate(void * ptr)
{
    // 1、    查表確定該內(nèi)存塊屬于哪個(gè)堆？返回堆句柄；
    HANDLE hHeap = which_heap(ptr);
    size_t deallocateSize;
    if(hHeap == 0)
    {
#ifdef _DEBUG
        _TRACE(_W("所訪問指針不在可管理的堆中.\n"));
#endif
    }
    else
    {
        // 2、    查找該堆對(duì)應(yīng)的完整列表，找到該堆的節(jié)點(diǎn)，修改該節(jié)點(diǎn)的狀態(tài)為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("刪除的內(nèi)存塊偏移為%d.\n"), offset);

        if( heap_list[index].full_list[offset].hHeap == 0)
        {
            _TRACE(_W("所訪問的指針在可管理堆中無(wú)記錄.\n"));
            return;
        }
        if(heap_list[index].full_list[offset].status != Occupied)
        {
            _TRACE(_W("所訪問的指針狀態(tài)不是已占用，原則上應(yīng)該是已占用.\n"));
        }
#endif
        heap_list[index].full_list[offset].status = Free;
        
        // 3、    合并相鄰項(xiàng)，[該步驟的執(zhí)行導(dǎo)致該鏈表中不存在兩塊連續(xù)的Free區(qū)塊]。
        remove_chunk(heap_list[index].full_list, index, offset);

        // 4、    更新內(nèi)存尺寸表。
        // 已經(jīng)包含在remove_chunk中

        // 5、 更新內(nèi)存堆映射表。
        remove_chunk_heap(ptr);
    }
}

/*輸出某一瞬間的各列表信息
*/
void memory_manager::debug_snapshot(void)
{
#ifdef _DEBUG
    _TRACE(_W("-----------start snapshot-------------\n"));
    _TRACE(_W("內(nèi)存塊尺寸表：\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個(gè).\n"), cIter->second.hHeap, cIter->first, cIter->second.count);
        ++totalFreeCounter;
        if(cIter->first <= FRAGMENT_SIZE)
            fragmentCounter+=cIter->second.count;
    }
    _TRACE(_W("    從“內(nèi)存塊尺寸表”來(lái)看，總共有%d塊空閑內(nèi)存，其中碎片（<= %d byte）的內(nèi)存塊有%d個(gè).\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];
                // 碎片數(shù)量
                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èi)存完全列表可能存在問題！\n"));
        _TRACE(_W("    第%d塊堆擁有%d空閑內(nèi)存、%d已占內(nèi)存、%d碎片\n"), i, heapListItemFreeCounter[i], heapListItemOccupidCounter[i], heapListItemFragmentCounter[i]);

        heapListItemTotalFreeCounter += heapListItemFreeCounter[i];
        heapListItemTotalOccupidCounter +=heapListItemOccupidCounter[i];
        heapListItemTotalFragmentCounter +=heapListItemFragmentCounter[i];
        heapListItemTotalCounter += heapListItemCounter[i];
    }
    _TRACE(_W("所有堆中共有%d內(nèi)存塊、%d空閑內(nèi)存、%d已占內(nèi)存、%d碎片\n"), 
        heapListItemTotalCounter,
        heapListItemTotalFreeCounter,  
        heapListItemTotalOccupidCounter,
        heapListItemTotalFragmentCounter);

    _TRACE(_W("------------end  snapshot-------------\n"));
#endif
}

/*堆初始化（全部）
策略：
    1、設(shè)置堆列表中的堆句柄為、最大可用尺寸為、最小可用尺寸為、可分配內(nèi)存首地址為
    */
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;
    }
}

/*堆初始化（單個(gè)）
策略：
    1、初始化堆各個(gè)字段，并對(duì)堆實(shí)行完全內(nèi)存分配。其中堆尺寸、最大最小可用尺寸均為完全分配尺寸
*/
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
/*創(chuàng)建堆對(duì)象
策略：
    1、創(chuàng)建一個(gè)固定大小的堆
    2、啟用LFH以減小內(nèi)存碎片（如果允許的話）
*/
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）
    // 以減少內(nèi)存碎片
#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;
}

/*釋放堆對(duì)象*/
inline BOOL memory_manager::heap_destroy_base(HANDLE hHeap)
{
    return HeapDestroy(hHeap);
}
/*申請(qǐng)內(nèi)存塊
策略：
*/
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;
}

/*釋放內(nèi)存塊
參數(shù)：
    hHeap：堆句柄
    lpMem：首地址
*/
inline BOOL memory_manager::heap_dealloc_base(HANDLE hHeap, LPVOID lpMem)
{
    return HeapFree(hHeap, 0, lpMem);
}

/*查找某個(gè)堆屬于堆列表中的第幾個(gè)
*/
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)    前項(xiàng)檢測(cè)：
    // 前一項(xiàng)如果為Free，將前項(xiàng)size+=當(dāng)前項(xiàng)size，刪除當(dāng)前項(xiàng)。
    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("執(zhí)行前項(xiàng)檢測(cè)且前項(xiàng)狀態(tài)為空閑，可執(zhí)行合并。前項(xiàng)偏移為%d\n"), prevOffset);
#endif
            return;
        }
    }

    chunk_type nextFreeChunk;
    // b)    后項(xiàng)檢測(cè)：（如果前項(xiàng)檢測(cè)無(wú)結(jié)果）
    // 如果后項(xiàng)為Free，將當(dāng)前項(xiàng)size=size+后項(xiàng)size，刪除后項(xiàng)。
    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("執(zhí)行后項(xiàng)檢測(cè)且后項(xiàng)狀態(tài)為空閑，可執(zhí)行合并。后項(xiàng)偏移為%d\n"), nextOffset);
#endif
            return;
        }
    }
    free_chunk_list_add(heap_list[heapIndex].full_list[offset].size, heap_list[heapIndex].hHeap);
}

/*
查詢堆信息，輔助調(diào)試，可以查看當(dāng)前堆的特性
*/
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

/*向內(nèi)存尺寸表中添加尺寸信息
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;
        }
    }

    // 否則如果沒有找到該堆所對(duì)應(yīng)的相同尺寸的信息
    free_chunk freeChunk;
    freeChunk.count = 1;
    freeChunk.hHeap = hHeap;

    free_chunk_table.insert(std::make_pair(size, freeChunk)); // copy 
}

/*從內(nèi)存尺寸表中移除尺寸信息
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("從內(nèi)存尺寸表中查找size=%d的內(nèi)存時(shí)候，無(wú)法找到記錄.\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("從內(nèi)存尺寸表中查找size=%d的內(nèi)存時(shí)候，無(wú)法找到記錄.\n"), size);
#endif // _DEBUG
}

/*通過可用鏈表查詢可用的內(nèi)存區(qū)塊
策略：
    1、遍歷可用區(qū)塊鏈表（該鏈表已經(jīng)按尺寸從小到大順序排列）
    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èi)存塊.\n"));
#endif
        }
    }

    return FALSE;
}

/*某個(gè)任意指針屬于哪個(gè)堆，返回值為表示不是在堆列表中的堆
策略：
1、本設(shè)計(jì)中存在返回指針以及所屬指針的字典映射
2、通過查表法找出當(dāng)前指針?biāo)鶎俚亩研畔?
*/
HANDLE memory_manager::which_heap(void * ptr)
{
    HANDLE hHeap = chunk_heap_table[ptr];
    if( NULL == hHeap )
    {
        _TRACE(_W("該指針不屬于任意內(nèi)存塊.\n"));
        return 0;
    }
    else
    {
#ifdef _DEBUG
        _TRACE(_W("當(dāng)前使用的指針來(lái)自第%d塊堆.\n"), heap_index(hHeap));
#endif
        return hHeap;
    }
}

/*將指針和對(duì)應(yīng)堆信息存進(jìn)字典備查
策略：
1、本設(shè)計(jì)中存在返回指針以及所屬指針的字典映射
2、以指針作為鍵值，將對(duì)應(yīng)堆句柄作為值
*/
void memory_manager::set_chunk_heap(void * ptr, HANDLE hHeap)
{
#ifdef _DEBUG
    if(chunk_heap_table[ptr] != 0)
    {
        _TRACE(_W("在此之前已經(jīng)有相同的指針存在于表中，還未釋放.\n"));
        return;
    }
#endif  
    chunk_heap_table[ptr] = hHeap;
}

/*將指針和對(duì)應(yīng)堆信息移出字典
策略：
1、本設(shè)計(jì)中存在返回指針以及所屬指針的字典映射
2、當(dāng)該指針作廢后，此處移走對(duì)應(yīng)項(xiàng)
*/
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已經(jīng)從第%d塊堆中移除.\n"), ptr, heap_index( hHeap ));
#endif  
}

memory_manager_main.cpp

// memory_manager.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//

#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("開始申請(qǐng)%d大小的內(nèi)存\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("累計(jì)申請(qǐng)內(nèi)存數(shù)量%d、申請(qǐng)%d次、申請(qǐng)的最大內(nèi)存為%d。\n"), totalMemory, curr, max);

    mm.debug_snapshot();
    _TRACE(_W("====================開始釋放內(nèi)存。\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 閱讀(3834) 評(píng)論(17)  編輯 收藏 引用 所屬分類: C/C++