简单的实现内存池管理器

http://vincent.blog.chinaunix.net
这几天，业余的使用链表的方式实现了一个内存池管理器，原理很简单，就是通过一个链表把内存块链接起来，然后再把内存块以动态单元的方式划分出去，动态单元之间使用单链表方式组织，不过没详细的测试过，只是大概的测试一下， 大概实现原理如下图：

图：简单内存管理器，不支持多线程




实现代码如下：
file: mpool.h
========================================================================================

/*
 * author: [e-mail]
 * history:
 * initial @ 2011-08-14
 */

#ifndef _MPOOL_H_
#define _MPOOL_H_

#include "list.h"

#define assert(x)

typedef unsigned int size_t;

#define NULL 0

typedef unsigned int lnk_t;

#define __align_mask(x,mask)    (((x)+(mask))&~(mask))

#ifndef offsetof
#define offsetof(type,member) ((size_t) &((type *)0)->member)
#endif

/* pointer alignment */
#define ptr_align(p,mask) ((void*)(((char*)(p)-(char*)0+(mask))&~(mask)))

/* get the pointer of the first unit */
#define unit_first_ptr(base,mbh,mask)    ((char*)(base)+__align_mask(sizeof(mbh),mask))

/* flag operator */
#define is_free(p) (!(*(lnk_t*)(p)&1))
#define flag_get(p) (*(lnk_t*)(p)&1)
#define flag_set(p) (*(lnk_t*)(p)|=1)
#define flag_clr(p) (*(lnk_t*)(p)&=(~1))

/* offset operator */
#define next_offset_get(p) (*(lnk_t*)(p)>>1)
#define next_offset_set(p,v) (*(lnk_t*)(p)=(((v)<<1)+flag_get(p)))

/* include the linking head */
#define unit_size(p) ((*(lnk_t*)(p)>>1))
/* exclude the linking head */
#define unit_len(p,mask) ((*(lnk_t*)(p)>>1)-__align_mask(sizeof(lnk_t),(mask)))
/* the button of the linking head, but NOTE  */
#define unit_ptr(p,mask) ((char*)(p)+__align_mask(sizeof(lnk_t),(mask)))
/* setting the head of the linking unit */
#define unit_set(p,flag,offset) (*(lnk_t*)(p)=(((flag)&1)|((offset)<<1)))
/* point to the next unit, top of the next linking head */
#define next_ptr(p) ((char*)(p)+next_offset_get(p))
/* pointer of plus (size) bytes, but NOTE  */
#define ptr_add(p,size,mask)  (ptr_align(unit_ptr(p,mask)+(size),(mask)))

/*
 * head: point to the top of first unit.
 * limit: point to the button of last unit.
 */
#define mblocks_for_each(pos, pre, head, limit) \
    for (pre=pos=(char*)(head); pos<limit; \
        pre=pos, pos=next_ptr(pos))

#define FIT_SIZE    0
#define FIT_FIRST   1


typedef struct mblock_s{
    struct list_head list;
    size_t size_block;
}MBLOCK_T;


typedef struct mpool_s{
    struct list_head head;
    int align_mask;
    int tactics;
    void* (*malloc)(struct mpool_s* mpool_p, size_t size);
    void (*free)(struct mpool_s* mpool_p, void *obj_p);
    char* (*grow)(struct mpool_s* mpool_p, char *new_p, size_t size);
    void (*print)(struct mpool_s* mpool_p);
}MPOOL_T;

void mpool_init(MPOOL_T* mpool_p, char *mem_p, size_t size,
                int tactics, unsigned int alignment);

#define mpool_malloc(mp,size) \
        ((mp).malloc(&(mp),size))

#define mpool_free(mp,fp) \
        ((mp).free(&(mp),(fp)))

#define mpool_grow(mp,np,size) \
        ((mp).grow(&(mp),(np),(size)))

#define mpool_print(mp) \
        ((mp).print(&(mp)))

#endif

file: mpool.c
========================================================================================

/*
 * author: [e-mail]
 * history:
 * initial @ 2011-08-14
 */

#include "mpool.h"

#ifndef __cplusplus
#define max(a,b)    (((a) > (b)) ? (a) : (b))
#define min(a,b)    (((a) < (b)) ? (a) : (b))
#endif

union fooround{
    long double d;
    void *p;
};

struct fooalign{
    char c;
    union fooround u;
};

#define    DFT_ALIGN (offsetof(struct fooalign, u))

static void *mblock_malloc__(struct mpool_s* mpool_p, MBLOCK_T* mblock_p, size_t size)
{
    char *limit_p, *head_p, *pos_p, *prev_p, *end_p, *next_p, *mark_p=0;
    unsigned int size_mark=(unsigned int)(-1);
    int size_fit, mask;

    assert(mblock_p && mpool_p);
    mask = mpool_p->align_mask;
    head_p = unit_first_ptr(mblock_p, MBLOCK_T, mask);
    limit_p = (char*)mblock_p+mblock_p->size_block;

    mblocks_for_each(pos_p, prev_p, head_p, limit_p)
    {
        if (is_free(pos_p) && (size_fit=unit_len(pos_p,mask)-size)>=0){
            if (mpool_p->tactics==FIT_FIRST || size_fit==0/*matched*/){
                end_p = ptr_add(pos_p,size,mask);
                next_p = next_ptr(pos_p);
                if (end_p < next_p){
                    unit_set(pos_p, 0, end_p-pos_p);
                    unit_set(end_p, 0, next_p-end_p);
                }
                flag_set(pos_p);
                return unit_ptr(pos_p,mask);
            }else{
                if (size_fit<size_mark){ /* pick up the fittest size */
                    size_mark=size_fit;
                    mark_p=pos_p;
                }
            }
        }
    }
    if (mark_p){ /* the fittest size marked */
        end_p = ptr_add(mark_p,size,mask);
        next_p = next_ptr(mark_p);
        if (end_p < next_p){
            unit_set(mark_p, 0, end_p-mark_p);
            unit_set(end_p, 0, next_p-end_p);
        }
        flag_set(mark_p);
        return unit_ptr(mark_p,mask);
    }
    return (void*)0;
}

static void *mpool_malloc__(struct mpool_s* mpool_p, size_t size)
{
    struct list_head *list_p;
    MBLOCK_T *mblock_p;
    void *new_p;
    assert(mpool_p);
    list_for_each(list_p, &mpool_p->head){
        mblock_p = list_entry(list_p, MBLOCK_T, list);
        if(new_p=mblock_malloc__(mpool_p, mblock_p, size))
            return new_p;
    }
    return 0;
}

static void mblock_free__(struct mpool_s* mpool_p, MBLOCK_T* mblock_p, void* free_p)
{
    char *limit_p, *head_p, *pos_p, *prev_p, *next_p;
    unsigned int mask, size_fit, size_mark=(unsigned int)(-1);

    assert(mblock_p && free_p);

    mask = mpool_p->align_mask;

    head_p = unit_first_ptr(mblock_p, MBLOCK_T, mask);
    limit_p = (char*)mblock_p+mblock_p->size_block;

    mblocks_for_each(pos_p, prev_p, head_p, limit_p)
    {
        if (unit_ptr(pos_p,mask)==(char*)free_p) /* matched */
        {
            next_p = next_ptr(pos_p);
            /* look at up to the previous unit */
            if (prev_p != pos_p && is_free(prev_p))
            {
                unit_set(prev_p, 0, next_ptr(pos_p)-prev_p); /* merge up */
                pos_p = prev_p;
            }
            flag_clr(pos_p);
            /* look at down to the next unit */
            if (next_p<limit_p && is_free(next_p))
            {
                unit_set(pos_p, 0, next_ptr(next_p)-pos_p); /* merge down */
            }
            break;
        }
    }
}

static void mpool_free__(struct mpool_s* mpool_p, void *obj_p)
{
    struct list_head *list_p;
    MBLOCK_T *mblock_p;
    int offset;
    void *new_p;
    assert(obj_p);
    list_for_each(list_p, &mpool_p->head){
        mblock_p = list_entry(list_p, MBLOCK_T, list);
        if (mblock_p){
            offset = (char*)obj_p-(char*)mblock_p;
            if (offset>0 && offset < mblock_p->size_block)
                return mblock_free__(mpool_p, mblock_p, obj_p);
        }
    }
}

static char* mblock_init__(struct mpool_s* mpool_p, char *new_p, size_t size)
{
    MBLOCK_T *mblock_p;
    char *base_p, *limit_p, *fp;

    assert(mpool_p && new_p);

    if (size < sizeof(MBLOCK_T)+max(sizeof(lnk_t),DFT_ALIGN))
        return (char*)0;

    base_p = ptr_align(new_p, mpool_p->align_mask);
    limit_p = ptr_align(new_p+size, mpool_p->align_mask);

    mblock_p = (MBLOCK_T*)base_p;
    mblock_p->size_block = limit_p-base_p;

    fp = unit_first_ptr(base_p, MBLOCK_T, mpool_p->align_mask);

    unit_set(fp, 0, limit_p-fp);
    return base_p;
}

static int mpool_grow__(struct mpool_s* mpool_p, char *new_p, size_t size)
{
    char *bp;
    assert(mpool_p && new_p);
    bp = mblock_init__(mpool_p, new_p, size);
    if (!bp) return -1;
    list_add(&((MBLOCK_T*)bp)->list, &mpool_p->head);
    return 0;
}

void mpool_print__(struct mpool_s* mpool_p)
{
    struct list_head *list_p;
    MBLOCK_T *mblock_p;
    char *limit_p, *head_p, *pos_p, *prev_p;
    int mask, num_block=0;

    assert(mpool_p);
    mask = mpool_p->align_mask;

    list_for_each(list_p, &mpool_p->head){
        mblock_p = list_entry(list_p, MBLOCK_T, list);
        if (mblock_p){
            printf("block(%d): memory=%p, size=%d ===\n",
                num_block++, mblock_p, mblock_p->size_block);
            head_p = unit_first_ptr(mblock_p, MBLOCK_T, mask);
            limit_p = (char*)mblock_p+mblock_p->size_block;
            mblocks_for_each(pos_p, prev_p, head_p, limit_p)
            {
                printf("[addr=%p flag=%d offset=%d room=%d]-->\n",
                        unit_ptr(pos_p, mask),
                        flag_get(pos_p),
                        unit_size(pos_p),
                        unit_len(pos_p, mask));
            }
        }
    }
}

extern void mpool_init(MPOOL_T* mpool_p, char *mem_p, size_t size,
                       int tactics, unsigned int alignment)
{
    assert(mpool_p && mem_p);

    INIT_LIST_HEAD(&mpool_p->head);

    mpool_p->align_mask=
        alignment?(alignment-1):(DFT_ALIGN-1);

    if (tactics==FIT_FIRST)
        mpool_p->tactics = tactics;
    else
        mpool_p->tactics = FIT_SIZE;

    *(mpool_p->malloc) = mpool_malloc__;
    *(mpool_p->free) = mpool_free__;
    *(mpool_p->grow) = mpool_grow__;
    *(mpool_p->print) = mpool_print__;
    mpool_p->grow(mpool_p, mem_p, size);
}

file: main.c
========================================================================================

/*
 * author: [e-mail]
 * history:
 * initial @ 2011-08-14
 */

#include "mpool.h"

#include <stdlib.h>
#include <time.h>

#define PROMPT_FAILED "mpool malloc failed!\n"

#define MAX_HANDLES 20

void random_test(MPOOL_T *mpool_p, void *arr_malloc[], size_t count, int times)
{
    int index, rand_bytes, i;
    assert(mpool_p && arr_malloc)
    memset(arr_malloc, 0, count*sizeof(void*));
    srand ((unsigned)time(NULL));
    i=0;
    while (times--)
    {
        printf("---------------------------------------------------\n");
        index=rand()%count;
        rand_bytes = rand()%150;
        printf("[%d]test: index=%d rand_bytes=%d\n", i++, index, rand_bytes);
        if (arr_malloc[index])
            mpool_free(*mpool_p, arr_malloc[index]);
        arr_malloc[index]=mpool_malloc(*mpool_p, rand_bytes);
        if (!arr_malloc[index])
            printf("%s\n", PROMPT_FAILED);
        else
            memset(arr_malloc[index], 5,rand_bytes);
        mpool_print(*mpool_p);
    }
    i=0;
    while(i < count)
    {
        mpool_free(*mpool_p, arr_malloc[i++]);
    }
    mpool_print(*mpool_p);
}

void lining_test(MPOOL_T *mpool_p, void *arr_malloc[], size_t count)
{
    int index, bytes, i, max_bytes;
    assert(mpool_p && arr_malloc);
    memset(arr_malloc, 0, count*sizeof(void*));
    index = 0;
    bytes = 0;
    i = 0;
    max_bytes = 10;
    while(bytes < max_bytes)
    {
        printf("---------------------------------------------------\n");
        index = i % count;
        printf("[%d]test: index=%d bytes=%d\n", i++, index, bytes);
        if (arr_malloc[index])
            mpool_free(*mpool_p, arr_malloc[index]);
        arr_malloc[index]=mpool_malloc(*mpool_p, bytes);
        if (!arr_malloc[index])
            printf("%s\n", PROMPT_FAILED);
        else
            memset(arr_malloc[index], 5,bytes);
        mpool_print(*mpool_p);
        bytes++;
    }
    i=0;
    while(i < count)
    {
        mpool_free(*mpool_p, arr_malloc[i++]);
    }
    mpool_print(*mpool_p);
}

void fixing_test(MPOOL_T *mpool_p, void *arr_malloc[], size_t count)
{
    int index, i, fix_bytes;
    assert(mpool_p && arr_malloc);
    memset(arr_malloc, 0, count*sizeof(void*));
    index = 0;
    i = 0;
    fix_bytes = 33;
    while(i++ < 50)
    {
        printf("---------------------------------------------------\n");
        index = i % count;
        printf("[%d]test: index=%d bytes=%d\n", i++, index, fix_bytes);
        if (arr_malloc[index])
            mpool_free(*mpool_p, arr_malloc[index]);
        arr_malloc[index]=mpool_malloc(*mpool_p, fix_bytes);
        if (!arr_malloc[index])
            printf("%s\n", PROMPT_FAILED);
        else
            memset(arr_malloc[index], 5, fix_bytes);
        mpool_print(*mpool_p);
    }
    i=0;
    while(i < count)
    {
        mpool_free(*mpool_p, arr_malloc[i++]);
    }
    mpool_print(*mpool_p);
}


void main()
{
    MPOOL_T mpool;
    int i=20;
    char *new_p1, *new_p2, *new_p3;
    void* arr_malloc[MAX_HANDLES];
    char mem_1[500];
    char mem_2[300];
    mpool_init(&mpool, mem_1, sizeof(mem_1), 0, 4);
    new_p1 = mpool_malloc(mpool, 10);
    mpool_print(mpool);
    if (!new_p1) printf("%s", PROMPT_FAILED);

    mpool_grow(mpool,mem_2, sizeof(mem_2));
    mpool_print(mpool);

    new_p2 = mpool_malloc(mpool, 32);
    if (!new_p2) printf("%s", PROMPT_FAILED);
    mpool_free(mpool, new_p2);
    mpool_print(mpool);
    new_p3 = mpool_malloc(mpool, 12);
    mpool_print(mpool);
    if (!new_p3) printf("%s", PROMPT_FAILED);
    mpool_free(mpool, new_p1);
    mpool_print(mpool);
    mpool_free(mpool, new_p2);
    mpool_print(mpool);
    mpool_free(mpool, new_p3);
    mpool_print(mpool);
    random_test(&mpool, arr_malloc, MAX_HANDLES, 10);
    lining_test(&mpool, arr_malloc, MAX_HANDLES);
    fixing_test(&mpool, arr_malloc, MAX_HANDLES);
}

附件：  mpool.rar  
========================================================================================