我给一个代码，实现一套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);
}
2008-04-10 20:19
