凑热闹贴代码：我的buddy算法实现

ofourme

 由于是在2年多前写的，又没有注释，so，我现在也看不懂啦。感兴趣的同学去网上搜一下buddy算法。           

我的buddy算法实现 2010-04-15

/*////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

types.h

*/

#ifndef __TYPES_H__
#define __TYPES_H__

typedef unsigned char uint8_kt;
typedef signed char sint8_kt;
typedef unsigned short uint16_kt;
typedef signed short sint16_kt;
typedef unsigned long uint32_kt;
typedef signed long sint32_kt;

typedef uint32_kt word_kt;
typedef unsigned int bool_kt;

typedef void* (*pv_w_kf)(word_kt size);
typedef bool_kt (*b_pv_kf)(void* addr);

#define FALSE (0)
#define TRUE (1)

#ifndef NULL
#define NULL (0)
#endif

typedef struct list_ks
{
struct list_ks* prev;
struct list_ks* next;

} list_kt, *list_kp;

typedef struct object_ks
{
list_kt list;
char name[16];

} object_kt;

#endif

/*////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

sys_cfg.h

*/

#ifndef __SYS_CFG_H__
#define __SYS_CFG_H__

#define MAX_ZONE 1
#define PAGE_SHIFT (8)
#define PAGE_SIZE (1<<AGE_SHIFT)
#define PAGE_MASK (PAGE_SIZE-1)

#define ALIGN_HEAD_M(addr, mask) ( ((word_kt)addr+(word_kt)mask) & (~((word_kt)(mask))) )
#define ALIGN_HEAD_N(addr, size) ( ALIGN_HEAD_M( (addr), (size)-1) )
#define ALIGN_HEAD_S(addr, shift) ( ALIGN_HEAD_N( (addr), 1<<(shift) ) )

#define ALIGN_TAIL_M(addr, mask) ( ((word_kt)(addr)) & (~((word_kt)(mask))) )
#define ALIGN_TAIL_N(addr, size) ( ALIGN_TAIL_M( (addr), (size)-1) )
#define ALIGN_TAIL_S(addr, shift) ( ALIGN_TAIL_N( (addr), 1<<(shift) ) )

#endif

/*////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

mem_buddy.h

*/

#ifndef __MEM_BUDDY_H__
#define __MEM_BUDDY_H__

#include "types.h"

typedef struct mem_buddy_ks
{
object_kt o;

word_kt heap_base;
word_kt heap_limit;
word_kt pool_base;
word_kt pool_limit;

list_kt* oarr_free_head; /* array cnt < maxorder, point to free list head*/
// word_kt* oarr_addr_ofst; /*/ array cnt < maxorder, point to address offset for alignment*/
// word_kt* oarr_index_head;
// word_kt* oarr_addr_head;

list_kt* barr_list; /*/ array cnt < block num, point to list array */
uint8_kt* barr_order; /*/ array cnt < block num, point to block size array */
uint8_kt* barr_attri; /*/ array cnt < block num, point to block attribute array */

word_kt page_count;
word_kt page_shift;
word_kt max_order;
uint8_kt arg0;
uint8_kt arg1;

} mem_buddy_kt, *mem_buddy_kp;

bool_kt k_mem_buddy_init(mem_buddy_kp pBdy, word_kt order, word_kt pageshift, void* base, void* limit,pv_w_kf malloc, b_pv_kf free);
void* k_mem_buddy_malloc(mem_buddy_kp pBdy, word_kt size);
bool_kt k_mem_buddy_free(mem_buddy_kp pBdy, void* addr);

#endif

/*////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

mem_buddy.c

*/

#include "mem_buddy.h"
#include "sys_cfg.h"

bool_kt k_mem_buddy_init(mem_buddy_kp pBdy, word_kt order, word_kt pageshift, void* base, void* limit,pv_w_kf malloc, b_pv_kf free)
{
word_kt pagecnt, pageaddr, index, i;

if( pBdy==NULL || base>limit )
{
return FALSE;
}

// init control block
pBdy->heap_base = (word_kt)base;
pBdy->heap_limit = (word_kt)limit;
pBdy->pool_base = (word_kt)ALIGN_HEAD_S((word_kt)base,PAGE_SHIFT);

// get order and pagecnt for malloc control space
pagecnt = ((word_kt)limit-(word_kt)base)>>AGE_SHIFT;

if(order == 0)
{
i = 1;
while( i < pagecnt )
{
order++;
i <<= 1;
}
order++;
}
pBdy->max_order = order;
// malloc control space for mem management
if(malloc && free)
{
// malloc control space from ext
puts("malloc control space from ext");
// if( pBdy->oarr_index_head = malloc(sizeof(word_kt)*order) )
{
if( pBdy->oarr_free_head = malloc(sizeof(list_kt)*order) )
{
if( pBdy->barr_list = malloc(sizeof(list_kt)*pagecnt) )
{
if( pBdy->barr_order = malloc(sizeof(uint8_kt)*pagecnt) )
{
if( pBdy->barr_attri = malloc(sizeof(uint8_kt)*pagecnt) )
{
pBdy->pool_limit = ALIGN_TAIL_S((word_kt)limit,PAGE_SHIFT);
pBdy->page_count = pagecnt;
goto _loop;
}
free(pBdy->barr_order);
}
free(pBdy->barr_list);
}
free(pBdy->oarr_free_head);
}
// free(pBdy->oarr_index_head);
}
return FALSE; // mem not enough for management

}
else
{
puts("malloc control space from heap");
// malloc control space from heap
pBdy->oarr_free_head = (void*)ALIGN_TAIL_M( (word_kt)limit-(word_kt)(sizeof(list_kt)*order), 7); // alignment = 7+1
pBdy->barr_list = (void*)ALIGN_TAIL_M( (word_kt)pBdy->oarr_free_head-(word_kt)(sizeof(list_kt)*pagecnt), 7);
pBdy->barr_order = (void*)ALIGN_TAIL_M( (word_kt)pBdy->barr_list-(word_kt)(sizeof(uint8_kt)*pagecnt), 7);
pBdy->barr_attri = (void*)ALIGN_TAIL_M( (word_kt)pBdy->barr_order-(word_kt)(sizeof(uint8_kt)*pagecnt), 7);

// init control block
pBdy->pool_limit = ALIGN_TAIL_S((word_kt)pBdy->barr_attri,PAGE_SHIFT);
pagecnt = pBdy->page_count = (pBdy->pool_limit - pBdy->pool_base)>>AGE_SHIFT;

}

_loop:

if( (word_kt)base > pBdy->pool_base || pBdy->pool_base > pBdy->pool_limit || pBdy->pool_limit > (word_kt)limit )
{
// pool_base might overflow because alignment
// pool_limit might use up the heap or overflow because malloc space from heap
// although ( base <= limit ) had been check before, it's ensure here

return FALSE;
}

// init control space
for(i=0; i<pagecnt; i++)
{
pBdy->barr_order = 0xff; // invalid this area
pBdy->barr_attri = 0xff; // invalid this area
pBdy->barr_list.prev = NULL;
pBdy->barr_list.next = NULL;
}
for(i=0; i<order; i++)
{
pBdy->oarr_free_head.prev = NULL;
pBdy->oarr_free_head.next = NULL;
}

// init control space
index = 0;
pageaddr = ((pBdy->pool_base)>>AGE_SHIFT);
while( index<pagecnt )
{
// get max alignment for this page addr
// i = blocksize
// pageaddr = cur page addr
// max_order>0 because index<pagecnt
order = pBdy->max_order;
do
{
order--;
i = 1<<order;
}while(pageaddr&(i-1));

// get max block size for this addr
while(index+i>pagecnt)
{
order--;
i = 1<<order;
}

pBdy->barr_order[index] = (uint8_kt)order;
pBdy->barr_attri[index] = 1; // could be free
k_mem_buddy_free(pBdy, (void*)(pBdy->pool_base+(index<<AGE_SHIFT)) );

pageaddr += i;
index += i;
}

return TRUE;
}

void* k_mem_buddy_malloc(mem_buddy_kp pBdy, word_kt size)
{
word_kt order, i, index;
list_kt* pList, *pLHead;

if( size == 0) return NULL;

// get suitable num(2^order) of page for this size
order = PAGE_SHIFT;
while( ((word_kt)1<<order) < size)
{
order++;
}
order -= PAGE_SHIFT;

for(i = order; i<pBdy->max_order; i++)
{
pLHead = &pBdy->oarr_free_head;
pList = pLHead->next;
if( pList ) // has space to malloc
{
// delet from free list
pBdy->oarr_free_head.next = pList->next;
if(pList->next)
{
pList->next->prev = pLHead;;
}

// get block index
index = pList - pBdy->barr_list;
while(i>order) // get little block from the tail of big block
{
i--;
// add 1st. half to the free list
pLHead = &pBdy->oarr_free_head;
pList->next = pLHead->next;
pLHead->next = pList;

if( pList->next )
{
pList->next->prev = pList;
}
pList->prev = pLHead;

// must clean to prevent refree
pBdy->barr_attri[index] = 0;
pBdy->barr_order[index] = (uint8_kt)i;

index += (1<<i);
pList += (1<<i);
}
pBdy->barr_attri[index] = 1;
pBdy->barr_order[index] = (uint8_kt)i;

return (void*)(pBdy->pool_base+(index<<AGE_SHIFT));
}
}

return NULL;
}

bool_kt k_mem_buddy_free(mem_buddy_kp pBdy, void* addr)
{
word_kt index, index_bdy, index_head, i, order, pageaddr, pagecnt;
list_kt* pList;

if((word_kt)addr < pBdy->pool_base || (word_kt)addr >= pBdy->pool_limit || ((word_kt)addr & PAGE_MASK) )
{
return FALSE;
}

index = ((word_kt)addr-(word_kt)pBdy->pool_base)>>AGE_SHIFT;

if( pBdy->barr_attri[index] != 1 ) // could not be free
{
return FALSE;
}

order = pBdy->barr_order[index];
pageaddr = (word_kt)addr>>AGE_SHIFT;
pagecnt = pBdy->page_count;
while( order<pBdy->max_order-1 ) // 超过 max_order则不应合并
{
i = 1<<order;
if(pageaddr&i) // not align for higher order
{
index_bdy = index - i;
index_head = index_bdy;
}
else
{
index_bdy = index + i;
index_head = index;
}
if( index_bdy>=pagecnt || pBdy->barr_attri[index_bdy]!=0 || pBdy->barr_order[index_bdy]!=order )
{
break;
}
// delet buddy from the free list
pList = &pBdy->barr_list[index_bdy];
pList->prev->next = pList->next;
if( pList->next )
{
pList->next->prev = pList->prev;
}
order++;
index = index_head;
pBdy->barr_attri[index+i] = 0xff; // invalid this area
}

// add to the free list
pBdy->barr_attri[index] = 0;
pBdy->barr_order[index] = (uint8_kt)order;

pBdy->barr_list[index].next = pBdy->oarr_free_head[order].next;
pBdy->barr_list[index].prev = &pBdy->oarr_free_head[order];

pBdy->oarr_free_head[order].next = &pBdy->barr_list[index];
if( pBdy->barr_list[index].next )
{
pBdy->barr_list[index].next->prev = &pBdy->barr_list[index];
}

return TRUE;
}

/*////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

main_test_buddy.c

*/

#include <stdio.h>
#include <stdlib.h>

#include "types.h"
#include "mem_buddy.h"

char* pHeap1;
word_kt nHeap1;

mem_buddy_kt Buddy_0;
mem_buddy_kt* pBdy;

word_kt k_mem_init(void)
{
word_kt i,j;

pBdy = &Buddy_0;

nHeap1 = 1024*4*8;
pHeap1 = malloc(nHeap1);
if(pHeap1 == NULL)
{
nHeap1 = 0;
}
printf("堆1 size: %lu, addr: %lu\n",(uint32_kt)nHeap1,(uint32_kt)pHeap1);
if(pHeap1)
{
i = (word_kt)pHeap1;
j = (word_kt)pHeap1+nHeap1;
printf("buttom: %lu, top: %lu----\n",(uint32_kt)i,(uint32_kt)j);
k_mem_buddy_init(pBdy,10,12,i,j,0,0);
return 1;
}
return 0;
}

void buddy_info(void)
{
word_kt i, index, j;
list_kt * pList;
char ch;

printf("\nbase:%lu-0x%lx, limit:%lu-0x%lx, page_count:%lu, max_order:%lu\n",
(uint32_kt)pBdy->pool_base,
(uint32_kt)pBdy->pool_base,
(uint32_kt)pBdy->pool_limit,
(uint32_kt)pBdy->pool_limit,
(uint32_kt)pBdy->page_count,
(uint32_kt)pBdy->max_order);

for(i=0; i<pBdy->max_order; i++)
{
printf("List[%lu]",i);
j=0;
pList = pBdy->oarr_free_head.next;
while(pList)
{
index = (pList - pBdy->barr_list);
printf(" -> [%lu]^%lu-%lu",(uint32_kt)index,(uint32_kt)pBdy->barr_order[index],(uint32_kt)pBdy->barr_attri[index]);
pList = pList->next;
j++;
}
printf(" -> (%lu)\n",(uint32_kt)j);
}
for(i=0; i<pBdy->page_count; i++)
{
if( pBdy->barr_attri==0 )
{
printf("%lu",(word_kt)(1<<pBdy->barr_order));
ch = '_';
}
else if( pBdy->barr_attri==1 )
{
printf("%lu",(word_kt)(1<<pBdy->barr_order));
ch = '#';
}
putchar(ch);

}
putch('\n');
}

void test_buddy(void)
{
#define NUM 1000

word_kt mf, num, i, j, k;
void *p;
void *pArr[NUM];

srand( (unsigned)time( NULL ) );
num = 0;
j=0;
while(1)
{
printf("%lu\n",j++);
mf = rand()%3;
if(mf) //malloc
{
if(num<NUM)
{
i = rand()%nHeap1;
p = k_mem_buddy_malloc(pBdy, i);
if(p)
{
pArr[num++] = p;
}
}
}
else // free
{
if(num)
{
i = rand()%num; // block to free
p = pArr;
k_mem_buddy_free(pBdy, p);
pArr = pArr[num-1];
num--;
}
}
buddy_info();
}
}

int main(void)
{
if(k_mem_init())
{
//test_stack();
test_buddy();
}
else
{
puts("heap init error!\n");
}
getch();
return 0;
}

正点原子

百度了下，科普了：buddy算法是用来做内存管理的经典算法，目的是为了解决内存的外碎片。