当前位置: 代码迷 >> C语言 >> 自定义malloc 函数错在哪呢?
  详细解决方案

自定义malloc 函数错在哪呢?

热度:575   发布时间:2008-04-10 20:19:57.0
你这个malloc呢局限性比较大,分配效率上不高,还有你没有考虑回收,我举个例子
有个静态区域,大小2k
[                    ]
我分配一个512字节的指针p
[p    ][             ]
然后我又分配了十二个128个字节的指针p1...p12,这样连续的内存空间就被分的很细
现在开始回收
我回收一个128字节的指针p6, 回收512字节的p
这样剩下了640字节空闲
然后我要分配一个590字节的指针,由于回收的两个内存快不在一片连续的区域里面就造成了分配失败,这样造成了空间浪费。
----------------解决方案--------------------------------------------------------
我给一个代码,实现一套malloc和free函数,使用段页式分配方法。
程序代码:

#ifndef _MALLOC_H_
#define _MALLOC_H_

// 块大小,默认规定每个块为2MB,也就是一次分配最大不得超过2MB的空间
#define BLOCK_SIZE                    (1024 * 1024 * 2)
// 页面长度,默认为8
#define PAGE_SIZE                    8
// 每块页面数,也就是将每个块按规定尺寸划分成若干页面组成,为了减少回收时产生的碎片
#define PAGE_PER_BLOCK                (BLOCK_SIZE / PAGE_SIZE)
// 最大块数,默认5,也就是程序保留16MB静态内存进行动态分配使用
#define MAX_BLOCK                    8

// 最多可以做65535次分配,应该足够了吧:)
#define ALLOC_POOL_MAX_PAGE            65535
// 分配池页面大小
#define ALLOC_POOL_PAGE_SIZE        sizeof(ATTR_ALLOC_TABLE)
// 分配池的长度
#define ALLOC_POOL_SIZE                (ALLOC_POOL_MAX_PAGE * ALLOC_POOL_PAGE_SIZE)

#include "def.h"

typedef struct tagAllocTable
{
    UCHAR *alloc_begin;                    // 分配起始地址
    UINT page_id;                        // 分配起始页面号
    UINT page_count;                    // 分配页面数量
    struct tagAllocTable *p_next;
} ATTR_ALLOC_TABLE;

typedef struct tagBlock
{
    UCHAR page_map[PAGE_PER_BLOCK];        // 页面导航图,记录每个页面的使用情况
    UCHAR block[BLOCK_SIZE];            // 分配块(池)
    UCHAR* ubound;                        // 分配上限(即block+BLOCK_SIZE)
    ULONG free_size;                    // 剩余空间
    ATTR_ALLOC_TABLE *alloc_list;        // 分配链
} ATTR_BLOCK;

void  _do_memmgr_init(void);                    // 初始化内存管理器
void* _malloc( ULONG size );                    // 以size为长度动态分配一个存储空间
void* _realloc( void* alloc_ptr, ULONG size);    // 以size为长度,对于之前已分配的指针alloc_ptr进行重新分配
void* _calloc( UINT nitems, ULONG size );        // 以nitems * size为长度进行一个动态分配
void  _free( void* alloc_ptr );                    // 释放一个分配

#define do_memmgr_init()    _do_memmgr_init()
#define malloc(n)            _malloc(n)
#define calloc(n,s)            _calloc(n,s)
#define realloc(p,s)        _realloc(p,s)
#define free(p)                _free(p)

#define zero_page_map(p,s)    memset(p,(UCHAR)0,sizeof(UCHAR)*s)

#endif


程序代码:

#include <string.h>

#include "null.h"
#include "malloc.h"

// 分配池,分配节点导航图及最近一次可用分配的页面号
static UCHAR alloc_pool[ALLOC_POOL_SIZE];
static UCHAR alloc_page_map[ALLOC_POOL_MAX_PAGE];
static UINT  alloc_last_page_id = 0;

// 内存池及初始化标志
static ATTR_BLOCK mem_pool[MAX_BLOCK];
static BOOL init_flag = FALSE;

static void size2hash(ULONG size, UINT* block_id, UINT* page_id, UINT* page_count);
static ATTR_ALLOC_TABLE* addr2hash(void* alloc_ptr, UINT* block_id);
static ATTR_ALLOC_TABLE* new_alloc_ptr(void);
static void delete_alloc_ptr(ATTR_ALLOC_TABLE* alloc_ptr);
static BOOL verify_hash(ULONG size, UINT* block_id, UINT* page_id, UINT* page_count);

void _do_memmgr_init(void)
{
    UINT i;
    ATTR_BLOCK* ptr_fix;

    for(i=0;i<MAX_BLOCK;i++)
    {
        ptr_fix = mem_pool+i;
        ptr_fix->free_size = BLOCK_SIZE;
        ptr_fix->ubound = (ptr_fix->block) + BLOCK_SIZE;
        make_null((ptr_fix->alloc_list), ATTR_ALLOC_TABLE);
        zero_page_map(ptr_fix->page_map, PAGE_PER_BLOCK);
    }
    zero_page_map(alloc_page_map, ALLOC_POOL_MAX_PAGE);
    init_flag = TRUE;
}

static void size2hash(ULONG size, UINT* block_id, UINT* page_id, UINT* page_count)
{
    *block_id = size % MAX_BLOCK;
    *page_id = size % PAGE_PER_BLOCK;
    if( size % PAGE_SIZE > 0 )
        *page_count = 1;
    else
        *page_count = 0;
    *page_count += size / PAGE_SIZE;
}

static ATTR_ALLOC_TABLE* addr2hash(void* alloc_ptr, UINT* block_id)
{
    UCHAR *addr = (UCHAR *)alloc_ptr;
    ATTR_BLOCK *ptr_fix;
    ATTR_ALLOC_TABLE *allocator;

    UINT i;

    nullpret(alloc_ptr, ((ATTR_ALLOC_TABLE *)0));
    make_null(allocator,ATTR_ALLOC_TABLE);

    for(i=0;i<MAX_BLOCK;i++)
    {
        ptr_fix = mem_pool+i;
        if( addr >= ptr_fix->block && addr <= ptr_fix->ubound )
        {
            *block_id = i;
            allocator = ptr_fix->alloc_list;
            while(allocator->p_next != NULL)
            {
                if( allocator->alloc_begin == addr )
                {
                    break;
                }
                allocator = allocator->p_next;
            }
            break;
        }
    }
    return allocator;
}

static ATTR_ALLOC_TABLE* new_alloc_ptr(void)
{
    ATTR_ALLOC_TABLE *ret;
    make_null(ret, ATTR_ALLOC_TABLE);
    if( alloc_last_page_id < ALLOC_POOL_MAX_PAGE)
    {
        ret = (ATTR_ALLOC_TABLE *)&alloc_pool[alloc_last_page_id * ALLOC_POOL_PAGE_SIZE];
        alloc_page_map[alloc_last_page_id] = 1;
        alloc_last_page_id++;
    }
    else
    {
        UINT i;
        for(i=0;i<ALLOC_POOL_MAX_PAGE;i++)
        {
            if( alloc_page_map[i] == 0 )
            {
                ret = (ATTR_ALLOC_TABLE *)&alloc_pool[i * ALLOC_POOL_PAGE_SIZE];
                alloc_page_map[i] = 1;
                break;
            }
        }
    }
    return ret;
}

static void delete_alloc_ptr(ATTR_ALLOC_TABLE* alloc_ptr)
{
    UINT page_id;
    page_id = (UINT)(((UCHAR *)(alloc_ptr) - alloc_pool) / ALLOC_POOL_PAGE_SIZE);
    alloc_page_map[page_id] = 0;
    if(page_id == alloc_last_page_id-1)
        alloc_last_page_id = page_id;
}

static BOOL verify_hash(ULONG size, UINT* block_id, UINT* page_id, UINT* page_count)
{
    UINT mir_block_id = *block_id;
    UINT mir_page_id = *page_id;
    UINT mir_page_count = *page_count;
    UINT i;

    // 页面收集器,统计页面时使用
    UINT page_collector = 0;
    // 验证hash获得的连续页面区域是否可用
    UINT flag = 0;

    // hash分配的块号有足够空间可以分配,验证hash获得的页面区域是否可用
    if(mem_pool[mir_block_id].free_size >= size)
    {
        for(i = mir_page_id; i < mir_page_id + mir_page_count; i++)
        {
            if( mem_pool[mir_block_id].page_map[i] == 1 )
            {
                flag = 1;
                break;
            }
        }
        if( flag == 0 )
        {
            return TRUE;
        }
    }

    // hash获得分配块不可用
    if(mem_pool[mir_block_id].free_size < size || flag == 1)
    {
        // 重新寻找可用块
        for(mir_block_id = 0; mir_block_id < MAX_BLOCK; mir_block_id++)
        {
            if(mem_pool[mir_block_id].free_size >= size)
            {
                for(flag = 0, i = mir_page_id; i < mir_page_id + mir_page_count; i++)
                {
                    if( mem_pool[mir_block_id].page_map[i] == 1 )
                    {
                        flag = 1;
                        break;
                    }
                }
                // 找到可用块
                if( flag == 0 )
                {
                    *block_id = mir_block_id;
                    return TRUE;
                }
                else
                {
                    // hash获得的页面区域不可用时,重新在当前块中查找可用的页面区域
                    for( mir_page_id = i = 0; i < PAGE_PER_BLOCK && page_collector != mir_page_count; i++ )
                    {
                        if( mem_pool[mir_block_id].page_map[i] == 1 )
                        {
                            mir_page_id = i+1;
                            // 重置记数器,重新进行统计
                            page_collector = 0;
                        }
                        else
                        {
                            page_collector++;
                        }
                    }
                    if( page_collector == mir_page_count )
                    {
                        // 当前块中拥有符合分配要求的连续区域
                        *block_id = mir_block_id;
                        *page_id = mir_page_id;
                        return TRUE;
                    }
                    // 当前块中没有可分配的区域,恢复hash获得的页面号
                    mir_page_id = *page_id;
                }
            }
        }
    }
    return FALSE;
}

void* _malloc(ULONG size)
{
    UCHAR *ret;
    UINT page_id, page_count, block_id;

    ATTR_ALLOC_TABLE *alloc_node;

    make_null(ret,UCHAR);
    make_null(alloc_node, ATTR_ALLOC_TABLE);

    if(size <= 0 || size > BLOCK_SIZE || init_flag == FALSE)
        return (void *)ret;
    
    // 计算hash
    size2hash(size, &block_id, &page_id, &page_count);
    
    // 查询hash获得的块是否有足够空间分配
    if( verify_hash( size, &block_id, &page_id, &page_count ) == FALSE )
    {
        return (void *)ret;
    }
    
    // 根据调整以后的块号,页面号进行分配操作
    // 获得分配地址
    ret = &(mem_pool[block_id].block[page_id*PAGE_SIZE]);
    // 创建分配节点
    alloc_node = new_alloc_ptr();
    nullpret(alloc_node, ((void *)0));
    alloc_node->alloc_begin = ret;
    alloc_node->page_id = page_id;
    alloc_node->page_count = page_count;
    // 将节点添加到当前块管理链中
    alloc_node->p_next = mem_pool[block_id].alloc_list;
    mem_pool[block_id].alloc_list = alloc_node;
    // 填充导航图
    memset(&(mem_pool[block_id].page_map[page_id]), (UCHAR)1, sizeof(UCHAR) * page_count);
    // 计算分配块剩余空间
    mem_pool[block_id].free_size -= size;
    // 分配成功后,返回分配到的指针
    return (void *)ret;
}

void* _calloc(UINT nitems, ULONG size)
{
    ULONG alloc_size = size * nitems;
    return _malloc(alloc_size);
}

void* _realloc(void* alloc_ptr, ULONG size)
{
    UINT block_id, page_id, page_count;
    UINT new_block_id, new_page_id, new_page_count;

    ULONG old_size;

    ATTR_ALLOC_TABLE *alloc_node;

    if(size <= 0 || size > BLOCK_SIZE || init_flag == FALSE)
        return (void *)0;

    //nullpret(alloc_ptr, ((void *)0));

    // 获得原先分配的分配节点与hash号
    alloc_node = addr2hash(alloc_ptr, &block_id);
    //nullpret(alloc_node, ((void *)0));
    if( alloc_node == NULL ) // 指针没有分配
    {
        return _malloc(size);
    }
    page_id = alloc_node->page_id;
    page_count = alloc_node->page_count;

    // 计算原始分配长度
    old_size = page_count * PAGE_SIZE;

    if(old_size >= size)
    {
        UINT recycle_page;
        // 分配缩减,则不用重新选择新的分配地址,进行区域缩减
        alloc_node->page_count = size / PAGE_SIZE;
        recycle_page = page_count - (alloc_node->page_count);
        // 缩减区域进行回收(原先内容将被截断)
        zero_page_map(&(mem_pool[block_id].page_map[page_id+recycle_page]), recycle_page);
        mem_pool[block_id].free_size += recycle_page * PAGE_SIZE;
    }
    else
    {
        ATTR_ALLOC_TABLE *p_prev, *p_trv;
        make_null(p_prev, ATTR_ALLOC_TABLE);
        // 新分配区域大于原先分配区域
        // 寻找新的分配hash
        size2hash(size, &new_block_id, &new_page_id, &new_page_count);
        // 校核区域
        if( verify_hash( size, &new_block_id, &new_page_id, &new_page_count ) == FALSE )
        {
            return (void *)0;
        }
        // 复制原先分配区域内的内容
        memcpy(
            &(mem_pool[new_block_id].block[new_page_id*PAGE_SIZE]),
            &(mem_pool[block_id].block[page_id*PAGE_SIZE]),
            sizeof(UCHAR) * page_count * PAGE_SIZE
            );
        // 旧区域回收
        zero_page_map(&(mem_pool[block_id].page_map[page_id]), page_count);
        mem_pool[block_id].free_size += page_count * PAGE_SIZE;
        // 新区域分配
        memset(&(mem_pool[new_block_id].page_map[new_page_id]), (UCHAR)1, sizeof(UCHAR)*new_page_count);
        mem_pool[new_block_id].free_size += new_page_count * PAGE_SIZE;
        
        // 分配节点转移
        // 查找旧区域分配节点的前驱节点
        p_trv = mem_pool[block_id].alloc_list;
        while( p_trv->p_next != NULL )
        {
            if( p_trv == alloc_node )
                break;
            else
            {
                p_prev = p_trv;
                p_trv = p_trv->p_next;
            }
        }
        // 该节点为表首
        if( p_prev == NULL )
        {
            // 确立新的表首
            mem_pool[block_id].alloc_list = alloc_node->p_next;
        }
        // 该节点为表尾
        else if( alloc_node->p_next == NULL )
        {
            p_prev->p_next = NULL;
        }
        else
        {
            p_prev->p_next = alloc_node->p_next;
        }
        // 重置分配节点
        alloc_node->alloc_begin = &(mem_pool[new_block_id].block[new_page_id*PAGE_SIZE]);
        alloc_node->page_count = new_page_count;
        alloc_node->page_id = new_page_id;
        // 连接到新块中
        alloc_node->p_next = mem_pool[new_block_id].alloc_list;
        mem_pool[new_block_id].alloc_list = alloc_node;
    }
    return (void *)(alloc_node->alloc_begin);
}

void _free(void* alloc_ptr)
{
    ATTR_ALLOC_TABLE *alloc_node;
    ATTR_ALLOC_TABLE *p_prev, *p_trv;
    UINT block_id;

    if( init_flag == FALSE )
        return;

    nullpo(alloc_ptr);

    alloc_node = addr2hash(alloc_ptr, &block_id);
    nullpo(alloc_node);
    make_null(p_prev, ATTR_ALLOC_TABLE);

    // 回收hash函数获得的分配区域
    zero_page_map(&(mem_pool[block_id].page_map[alloc_node->page_id]), (alloc_node->page_count));
    mem_pool[block_id].free_size += (alloc_node->page_count) * PAGE_SIZE;

    // 回收分配节点
    p_trv = mem_pool[block_id].alloc_list;
    while( p_trv->p_next != NULL )
    {
        if(p_trv == alloc_node)
            break;
        else
        {
            p_prev = p_trv;
            p_trv = p_trv->p_next;
        }
    }
    if( p_prev == NULL )
    {
        mem_pool[block_id].alloc_list = alloc_node->p_next;
    }
    else if( alloc_node->p_next == NULL )
    {
        p_prev->p_next = NULL;
    }
    else
    {
        p_prev->p_next = alloc_node->p_next;
    }
    delete_alloc_ptr(alloc_node);
}

----------------解决方案--------------------------------------------------------
一些数据类型的定义在这里
程序代码:

#ifndef _DEF_H_
#define _DEF_H_

typedef unsigned char    UCHAR;
typedef unsigned int    UINT;
typedef unsigned long    ULONG;

#define BOOL            UCHAR

#ifndef TRUE
#define TRUE            0xFF
#endif

#ifndef FALSE
#define FALSE            0x00
#endif

#define MAX_THREADS        5

// 保留1MB内存给文件缓冲
#define BUFFER_SIZE        (1024 * 1024)

#endif

----------------解决方案--------------------------------------------------------
这个是null.h
程序代码:

#ifndef _NULL_H_
#define _NULL_H_

#ifndef NULL
#define NULL        (void *)0
#endif

#define nullpo(p)            if(p == NULL) return;
#define nullpret(p,r)        if(p == NULL) return r;
#define make_null(p,t)        p = (t *)0

#endif

----------------解决方案--------------------------------------------------------
楼上兄弟代码很经典..看来楼主看了后又可以提高了....
----------------解决方案--------------------------------------------------------
啊...晕...
----------------解决方案--------------------------------------------------------
好长啊....有得研究了
----------------解决方案--------------------------------------------------------
函数的返回值类型不是void吗?怎么还有return啊?
----------------解决方案--------------------------------------------------------
char *a=all;    // define a
void * mall(int s)
{
    static char *a=all;// define a
    if(s>0&&a+s<=all+M)
多个地方定义A ,你想干什么
----------------解决方案--------------------------------------------------------
回复 13# 的帖子
这么长,自己写的 ?
----------------解决方案--------------------------------------------------------
  相关解决方案