
平台论坛博客文库

› 论坛 › 程序设计 › C/C++ › 基于用户程序buffer的内存分配

基于用户程序buffer的内存分配 [复制链接]

mik

荣誉版主

论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2006-01-18 15:11 |只看该作者 |倒序浏览

这是,早时,我在写我的x86-64汇编语言编译器a64时,模拟C库函数malloc及free()的一个小函数

balloc(): buffer- alloc 基于用户的缓冲区的分配方案.
bfree(): 对应于balloc().
写这两个函数,当时只是想用在少量的动态分配方案上, 又想避免在系统的堆空间分配内存.这样不会
因为一点点的动态分配而造成系统内存的丢失.

代码很少:
头文件 "balloc.h"

#ifndef _BALLOC_H_
#define _BALLOC_H_
typedef struct mem_link_struct {
unsigned int size;
void *head_ptr;
void *tail_ptr;
unsigned char used; /* is used ? */
struct mem_link_struct *next, *prev;
} mem_link_t;
typedef struct alloc_heap_struct {
unsigned int total_size;
unsigned int free_size;
mem_link_t *free_link;
mem_link_t *used_link;
void *heap;
} alloc_heap_t;
typedef unsigned int memlink_size_t;
/* free-heap-link total value type, it's a 32-bit type */
typedef unsigned int free_link_size_t;
/* used-heap-link total value type, it's a 32-bit type */
typedef unsigned int used_link_size_t;
/* default user-program buffer pool 64K */
#define POOLSIZE 65536
#define LINKSIZE 256
#define FREELINKSIZE 256
#define USEDLINKSIZE 256
#define EOK 0
#define EINIT -1
#define EFULLNESS -2
#define ENOMEM -3
#define EERROR -4
/*
char *e_msg[] = {
"initialize error",
"the buffer pool fullness",
"the buffer pool not enough",
0
};
*/
int init_bheap(unsigned int size, void *ptr);
void *balloc(unsigned int size);
int bfree(void *ptr);
#endif

复制代码

以下是: balloc.c

/*
*
* the file for mik's assmbler: a64 poject;
*
*
*/
#include "balloc.h"
/* free-memory-link buffer */
static mem_link_t free_link_buf[FREELINKSIZE];
/* used-memory-link buffer */
static mem_link_t used_link_buf[USEDLINKSIZE];
/* default buffer-heap for balloc() */
static char buf_heap[POOLSIZE];
/* alloc-heap-struct for balloc() */
static alloc_heap_t alloc_heap, *alloc_heap_ptr = &alloc_heap;
/*
* this function for test....
*/
void print_alloc_heap()
{
mem_link_t *free_link = alloc_heap_ptr->free_link;
mem_link_t *used_link = alloc_heap_ptr->used_link;
int i = 1;
printf("\nfree_link_buf is %x\n", free_link_buf);
printf("used_link_buf is %x\n", used_link_buf);
printf("buffer heap is %x\n\n", alloc_heap_ptr->heap);
printf(" free buffer-heap-link: \n");
printf("--------------------------------------------------\n");
printf("no.\tsize\thead\ttail\tused\n");
while (free_link) {
printf("%d\t%d\t%x\t%x\t%d\n", i++, free_link->size,
free_link->head_ptr, free_link->tail_ptr,
free_link->used);
free_link = free_link->next;
}
puts("\n");
puts(" used buffer-heap-link: ");
puts("------------------------------------------------------");
printf("no.\tsize\thead\ttial\tused\n");
i = 1;
while (used_link) {
printf("%d\t%d\t%x\t%x\t%d\n", i++, used_link->size,
used_link->head_ptr, used_link->tail_ptr,
used_link->used);
used_link = used_link->next;
}
}
__inline__ void init_mem_link()
{
memset(free_link_buf, 0, sizeof(free_link_buf));
memset(used_link_buf, 0, sizeof(used_link_buf));
}
int init_alloc_heap(unsigned int size, void *bufptr)
{
unsigned int poolsize;
/* initialize the free_link_buf & used_link_buf */
init_mem_link();
/* the buffer pool already initialize */
if (alloc_heap_ptr->heap && alloc_heap_ptr->heap == bufptr)
return EOK;
if (!bufptr) {
/* default buffer heap for user */
alloc_heap_ptr->heap = (void *)buf_heap;
poolsize = POOLSIZE;
} else {
if (!size)
return EINIT;
alloc_heap_ptr->heap = (void *)bufptr;
poolsize = size;
}
memset(alloc_heap_ptr->heap, 0, poolsize);
alloc_heap_ptr->total_size = poolsize;
alloc_heap_ptr->free_size = poolsize;
alloc_heap_ptr->used_link = 0;
alloc_heap_ptr->free_link = &free_link_buf[0];
/* free-heap-link initialize */
free_link_buf[0].size = alloc_heap_ptr->free_size;
free_link_buf[0].head_ptr = (void *)alloc_heap_ptr->heap;
free_link_buf[0].tail_ptr = (void *)alloc_heap_ptr->heap + poolsize;
free_link_buf[0].used = 1;
free_link_buf[0].next = 0;
free_link_buf[0].prev = 0;
/* successed */
return EOK;
}
/* allocate a mem-link */
unsigned int alloc_memlink(mem_link_t *mem_link)
{
int i = 0;
int linksize =
mem_link == free_link_buf ? FREELINKSIZE : USEDLINKSIZE;
while (i < linksize) {
if (mem_link[i].used == 0) /* free */
return i;
i++;
}
return -1;
}
__inline__ unsigned int alloc_free_memlink()
{
return alloc_memlink(free_link_buf);
}
__inline__ unsigned int alloc_used_memlink()
{
return alloc_memlink(used_link_buf);
}
/**********************************************************************/
unsigned int mount_link(mem_link_t *link, mem_link_t *new)
{
int is_free_link = link == alloc_heap_ptr->free_link ? 1 : 0;
while (link) {
if (is_free_link) {
if ((link->tail_ptr + 1 == new->head_ptr)
&& (link->next->head_ptr == new->tail_ptr + 1))
{
link->tail_ptr += new->size + link->next->size;
link->next = link->next->next;
link->size += new->size + link->next->size;
memset(link->next, 0, sizeof(mem_link_t));
memset(new, 0, sizeof(mem_link_t));
return EOK;
} else if (link->tail_ptr + 1 == new->head_ptr) {
link->tail_ptr += new->size;
link->size += new->size;
memset(new, 0, sizeof(mem_link_t));
return EOK;
} else if (link->head_ptr == new->tail_ptr + 1) {
link->head_ptr -= new->size;
link->size += new->size;
memset(new, 0, sizeof(mem_link_t));
return EOK;
}
}
if (!link->next) break;
link = link->next;
}
link->next = new;
link->next->next = 0;
link->next->prev = link;
return EOK;
}
/* the function: mount the free memory link */
unsigned int mount_free_link(void *ptr, unsigned int size)
{
int number = alloc_free_memlink();
if (number == -1) return -1;
free_link_buf[number].used = 1;
free_link_buf[number].head_ptr = ptr;
free_link_buf[number].tail_ptr = ptr + size - 1;
free_link_buf[number].size = size;
if (alloc_heap_ptr->free_link)
return mount_link(alloc_heap_ptr->free_link,
&free_link_buf[number]);
free_link_buf[number].next = 0;
free_link_buf[number].prev = 0;
alloc_heap_ptr->free_link = &free_link_buf[number];
return EOK;
}
/* the function: mount the used memory link */
unsigned int mount_used_link(void *ptr, unsigned int size)
{
int number = alloc_used_memlink();
if (number == -1) return -1;
used_link_buf[number].used = 1; /* used by alloc */
used_link_buf[number].size = size;
used_link_buf[number].head_ptr = ptr;
used_link_buf[number].tail_ptr = ptr + size - 1;
if (alloc_heap_ptr->used_link)
return mount_link(alloc_heap_ptr->used_link,
&used_link_buf[number]);
/* no used and full free */
used_link_buf[number].next = 0;
used_link_buf[number].prev = 0;
alloc_heap_ptr->used_link = &used_link_buf[number];
return EOK;
}
/***********************************************************************/
__inline__ void do_umount_link(mem_link_t *old)
{
if (old->prev)
old->prev->next = old->next;
if (old->next)
old->next->prev = old->prev;
}
void umount_free_link(mem_link_t *old, unsigned int size)
{
old->used = 0;
alloc_heap_ptr->free_size -= size;
if (!old->prev && !old->next) {
/* only 1-node */
if (alloc_heap_ptr->free_size == 0)
alloc_heap_ptr->free_link = 0;
else {
old->used = 1;
old->size -= size;
old->head_ptr += size;
}
} else if (!old->prev) {
alloc_heap_ptr->free_link = old->next;
old->next->prev = 0;
} else
do_umount_link(old);
}
void umount_used_link(mem_link_t *old)
{
old->used = 0;
alloc_heap_ptr->free_size += old->size;
if (!old->prev && !old->next)
if (alloc_heap_ptr->free_size == alloc_heap_ptr->total_size) {
alloc_heap_ptr->used_link = 0;
} else {
old->used = 1;
}
else if (!old->prev) {
alloc_heap_ptr->used_link = old->next;
old->next->prev = 0;
} else
do_umount_link(old);
}
/***********************************************************************/
/* the function same as C malloc */
void *balloc(unsigned int size)
{
mem_link_t *free_link = alloc_heap_ptr->free_link;
mem_link_t *used_link = alloc_heap_ptr->used_link;
while (free_link && (alloc_heap_ptr->free_size >= size)) {
if (free_link->size >= size) { /* OK */
void *ret = free_link->head_ptr;
/* mount at used link */
if (mount_used_link(ret, size) == -1) {
return 0;
}
/* umount the free link */
umount_free_link(free_link, size);
return ret;
}
free_link = free_link->next;
}
return 0;
}
/* the function same as C free */
int bfree(void *ptr)
{
if (!ptr) return EOK;
mem_link_t *used_link = alloc_heap_ptr->used_link;
mem_link_t *free_link = alloc_heap_ptr->free_link;
while (used_link) {
if ((ptr >= used_link->head_ptr) &&
(ptr <= used_link->tail_ptr))
{
/* umount used link, so the memory block is free */
umount_used_link(used_link);
/* mount at free link*/
mount_free_link(ptr, used_link->size);
return EOK;
}
used_link = used_link->next;
}
return EERROR;
}

复制代码

文库|博客

mik

荣誉版主

论坛徽章:: 0

2楼 [报告]

发表于 2006-01-18 15:12 |只看该作者

代码很简单,思想是:预先用固定分配的buffer模拟malloc()
不同的,malloc()在系统堆空间分配内存, balloc()在用户buffer分配内存.

balloc()函数很简单,只在是free链里查找空闲的内存空间,找到了,将内存块挂在used链里.
找不到返回0,
bfree()函数,作balloc()的反操作,在used链里查找被分配过的内存,然后,将它挂回空闲链(free_link).

整个代码只是维护着两条链, free_link 及 used_link.

事实上,这段代码还是不完善,还有不少些毛病和缺陷. 在实际应用上,我已经修改过...