/*
* Author: Hiawui
* Date: 2010/12/06
*/
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "hv_mem_pool.h"
/* Default page size, must be power of 2 */
#define UNIT_SIZE (1<<12)
/*
* Memory block flags
*/
#define HV_MB_FLG_1ST 1 /* indicates if the 1st block in a freeable blcok */
#define HV_MB_FLG_USED 2 /* indicates if this block is used or not */
/*
* Align request size to be multiple of specified size, add in block header
* szie: requested size
* csize: chunk size
*/
#define MEM_ALIGN_BASIC(size, csize) \
(((size) + sizeof(hv_mp_block_t) + ((csize) - 1)) & ~((csize) - 1))
/*
* Align request size to be multiple of memory page size, add in block header
* mp_p: pointer to memory pool
* size: requested size
*/
#define MEM_ALIGN_PS(mp_p, size) \
MEM_ALIGN_BASIC((size), (mp_p)->mp_pagesize)
/*
* Get memory block address
*/
#define MEM_BLOCK_ADDR(fb_p) \
((hv_mp_block_t*)((char*)(fb_p) - sizeof(hv_mp_block_t)))
/*
* Get free address
*/
#define FREE_ADDR(mb_p) \
((hv_free_block_t*)((char*)(mb_p) + sizeof(hv_mp_block_t)))
/*
* size of free block
*/
#define FREE_SIZE(fb_p) \
(MEM_BLOCK_ADDR((fb_p))->mb_size)
/*
* Set value to variable that pointer point to if pointer is not null
* p: the pointer
* val: the value
*/
#define SET_POINTER(p, val) \
do{ \
if((p) != NULL) (*(p)) = (val); \
}while(0)
/*
* Calculate the pages in the size, add in the block header
*/
#define PAGES_IN_SIZE(mp_p, size) \
(((size) + sizeof(hv_mp_block_t) + (mp_p)->mp_pagesize - 1) / (mp_p)->mp_pagesize)
/*
* Set memory block
*/
#define SET_MEM_BLOCK(mb_p, size, next) \
do{ \
(mb_p)->mb_magic0 = MB_MAGIC0; \
(mb_p)->mb_flag = 0; \
(mb_p)->mb_size = (size); \
(mb_p)->mb_next = (next); \
(mb_p)->mb_magic1 = MB_MAGIC1; \
}while(0)
/*
* Test if the memory block struct is correct.
* mb_p: pointer to a memory block
*/
#define MEM_BLOCK_VALID(mb_p) \
(((mb_p)->mb_magic0 == MB_MAGIC0) && ((mb_p)->mb_magic1 == MB_MAGIC1))
/*
* Set a flag to a memory block
*/
#define SET_FLAG(mb_p, flag) \
((mb_p)->mb_flag |= (flag))
/*
* Unset a flag of memory block
*/
#define UNSET_FLAG(mb_p, flag) \
((mb_p)->mb_flag &= ~(flag))
/*
* Test if flag is set to memory block
*/
#define HAS_FLAG(mb_p, flag) \
((mb_p)->mb_flag & (flag))
/*
* Count the bits of a integer
* size: Size of memory
*/
/*
* Previousely I used following function, which has the same output.
* int size2bits(unsigned long size)
* {
* int i = 0;
* while(size)
* {
* i++;
* size >>= 1;
* }
* return i;
* }
* Later I found size2bits is more frequently called and took many time,
* so I changed to use a table to speed up this function.
* The speed of new function is more than 5 times faster than the old function.
*/
static int size2bits(hv_msize_t size)
{
#define XTAB1(a) ((a)>=128?8:(a)>=64?7:(a)>=32?6:(a)>=16?5:(a)>=8?4:(a)>=4?3:(a)>=2?2:(a))
#define XTAB4(a) XTAB1(a+0), XTAB1(a+1), XTAB1(a+2), XTAB1(a+3)
#define XTAB16(a) XTAB4(a+0), XTAB4(a+4), XTAB4(a+8), XTAB4(a+12)
int i = 0;
static const int xtab[] = {
XTAB16(0x00), XTAB16(0x10), XTAB16(0x20), XTAB16(0x30),
XTAB16(0x40), XTAB16(0x50), XTAB16(0x60), XTAB16(0x70),
XTAB16(0x80), XTAB16(0x90), XTAB16(0xA0), XTAB16(0xB0),
XTAB16(0xC0), XTAB16(0xD0), XTAB16(0xE0), XTAB16(0xF0)
};
return size & 0xff000000?24 + xtab[size>>24]:
size & 0x00ff0000?16 + xtab[size>>16]:
size & 0x0000ff00?8 + xtab[size>>8]:
xtab[size];
}
/*
* Attach the free addr to free list
* mp_p: pointer to memory pool
* fb_p: pointer to free block
*/
static int free_pointer(hv_mpool_t* mp_p, hv_free_block_t* fb_p)
{
int i;
hv_mp_block_t* mb_p;
hv_free_block_t fb_h, *p1;
assert(mp_p != NULL && fb_p != NULL);
mb_p = MEM_BLOCK_ADDR(fb_p);
if(!MEM_BLOCK_VALID(mb_p))
return HV_MP_ERR_OVERWRITE;
if(!HAS_FLAG(mb_p, HV_MB_FLG_USED))
return HV_MP_ERR_FREED;
i = size2bits(mb_p->mb_size);
assert(i >= 0 && i <= MAX_INDEX);
/* sort the free block in descending order */
fb_h.fb_next = mp_p->mp_free_list[i];
p1 = &fb_h;
while(p1->fb_next != NULL && FREE_SIZE(p1->fb_next) > FREE_SIZE(fb_p))
{
p1 = p1->fb_next;
}
fb_p->fb_next = p1->fb_next;
p1->fb_next = fb_p;
mp_p->mp_free_list[i] = fb_h.fb_next;
UNSET_FLAG(mb_p, HV_MB_FLG_USED);
return HV_MP_ERR_NONE;
}
/*
* Split a free block
* mp_p: pointer to memory pool structure
* fb_p: pointer to free block
* size: size of user requested memory
*/
static int split_free_block(hv_mpool_t* mp_p, hv_free_block_t* fb_p, hv_msize_t size)
{
hv_mp_block_t *mb_p, *new_mb_p;
int ret, new_size;
assert(fb_p != NULL);
mb_p = MEM_BLOCK_ADDR(fb_p);
if(!MEM_BLOCK_VALID(mb_p))
{
return HV_MP_ERR_OVERWRITE;
}
size = MEM_ALIGN_BASIC(size, UNIT_SIZE);
if(size < (mb_p->mb_size + sizeof(hv_mp_block_t)))
{
/* new_size = mb_p->mb_size + sizeof(hv_mp_block_t) - size - sizeof(hv_mp_block_t); */
new_size = mb_p->mb_size - size;
new_mb_p = (hv_mp_block_t*)((char*)mb_p + size);
SET_MEM_BLOCK(new_mb_p, new_size, mb_p->mb_next);
/* this is not the 1st block */
UNSET_FLAG(new_mb_p, HV_MB_FLG_1ST);
/* set used flag for free */
SET_FLAG(new_mb_p, HV_MB_FLG_USED);
mb_p->mb_size = size - sizeof(hv_mp_block_t);
mb_p->mb_next = new_mb_p;
ret = free_pointer(mp_p, FREE_ADDR(new_mb_p));
if(ret != HV_MP_ERR_NONE)
return ret;
}
return HV_MP_ERR_NONE;
}
/*
* Allocate memory from memory pool
* mp_p: memory pool
* size: size of requested memory
* errno_p: error code
*/
static void* get_space(hv_mpool_t* mp_p, hv_msize_t size, int* errno_p)
{
int i;
hv_free_block_t* free_addr = NULL;
hv_mp_block_t* mb_p;
int ret;
assert(mp_p != NULL);
SET_POINTER(errno_p, HV_MP_ERR_NONE);
if(size < sizeof(hv_free_block_t))
size = sizeof(hv_free_block_t);
i = size2bits(size);
/* size exceeded the max size */
if(i > MAX_INDEX)
{
SET_POINTER(errno_p, HV_MP_ERR_TOO_BIG);
return NULL;
}
/* Try to get from free list 1st */
for(; i <= MAX_INDEX; i++)
{
if(mp_p->mp_free_list[i] != NULL &&
FREE_SIZE(mp_p->mp_free_list[i]) >= size)
{
free_addr = mp_p->mp_free_list[i];
mb_p = MEM_BLOCK_ADDR(free_addr);
if(!MEM_BLOCK_VALID(mb_p))
{
SET_POINTER(errno_p, HV_MP_ERR_OVERWRITE);
return NULL;
}
/* this block is used */
SET_FLAG(mb_p, HV_MB_FLG_USED);
mp_p->mp_free_list[i] = free_addr->fb_next; /* Kick off the free block from free list */
break;
}
}
if(i > MAX_INDEX) /* No avaliable free block */
{
hv_msize_t alloc_size = MEM_ALIGN_PS(mp_p, size);
mb_p = (hv_mp_block_t*)malloc(alloc_size);
if(mb_p == NULL)
{
SET_POINTER(errno_p, HV_MP_ERR_ALLOC);
return NULL;
}
alloc_size = alloc_size - sizeof(hv_mp_block_t); /* size of free block */
SET_MEM_BLOCK(mb_p, alloc_size, mp_p->mp_head);
/* this is the 1st block & used */
SET_FLAG(mb_p, HV_MB_FLG_1ST|HV_MB_FLG_USED);
mp_p->mp_head = mb_p;
free_addr = FREE_ADDR(mb_p);
}
/* split this free block to save memory */
ret = split_free_block(mp_p, free_addr, size);
if(ret != HV_MP_ERR_NONE)
{
SET_POINTER(errno_p, ret);
return NULL;
}
return (void*)free_addr;
}
/*
* Create new memory pool
* errno_p: error code
- 1
- 2
前往页