HI ,all
I am working on a research project relate to rtlinux . I write a simple
buddy memory allocator,and it works very well under rtlinux-2.0. I alloc a
big junk of memory , and use
buddy algorithm to alloc/free it when need. It is really simple and maybe
stupid,
but it fullfill my need.
Now I want to port it to rtlinux-2.2, but it cause system crash.
Below is my poor code .
Anybody can point out the where the problems are? Thanks.
#include <linux/module.h>
#include <asm/smplock.h>
#include <asm/uaccess.h>
#include <asm/processor.h>
#include <linux/fs.h>
#include <linux/mm.h>
#include <rtl_sync.h>
#ifdef __DEBUG
static unsigned long alloc_addr[100]; /* hope it enough */
static unsigned long alloc_map[100]; /* 32*MIN_UNIT */
static int alloc_size[100];
static int alloc_i[100];
static int pointer;
static int count;
#endif
#define RTL_BUDDY_POOL_ORDER 5 /*32 pages pool, hope it enough*/
#define BUDDY_UNIT_MIN 4
#define BUDDY_UNIT_MAX 10 /*Can alloc 16 - 1K byte, is it ok?*/
#define BUDDY_ORDER (BUDDY_UNIT_MAX - BUDDY_UNIT_MIN + 1)
/*for the buddy system*/
void * rtl_buddy_pool = NULL;
void * rtl_buddy_map = NULL;
unsigned long buddy_header[BUDDY_ORDER];
int buddy_map_size;
spinlock_t rtl_buddy_lock = SPIN_LOCK_UNLOCKED;
/*
* a simple version buddy system, _no_ priority(need it?)
*/
#define BUDDY_NEXT(x) (*((unsigned long *) (x)))
#define BUDDY_PREV(x) (*((unsigned long *) (x) + 1))
#define delete(x) \
do {\
BUDDY_NEXT( BUDDY_PREV(x) ) = BUDDY_NEXT(x);\
if( BUDDY_NEXT(x) != 0 )\
BUDDY_PREV( BUDDY_NEXT(x) ) = BUDDY_PREV(x);\
} while(0)
#define insert( head , addr)\
do { \
BUDDY_NEXT( addr ) = BUDDY_NEXT( head );\
BUDDY_PREV( addr ) = head; \
if( BUDDY_NEXT(addr) != 0 ) \
BUDDY_PREV( BUDDY_NEXT( addr ) ) = addr;\
BUDDY_NEXT( head ) = addr;\
} while (0)
#define clear_str( st_addr, idx, size) \
do { int i ;\
for ( i = 0; i < size ; i ++)\
clear_bit( idx + i , st_addr); \
} while (0)
#define set_str( st_addr, idx, size) \
do {\
int i;\
for ( i = 0; i < size ; i ++) \
set_bit( idx + i , st_addr);\
} while (0)
int test_empty(unsigned long st_addr, unsigned long idx, unsigned long size)
{
int i;
for( i = 0; i < size ; i ++)
if ( test_bit(idx + i, ( void * ) st_addr)) {
return 0;
}
return 1;
}
int test_full(unsigned long st_addr, unsigned long idx, unsigned long size)
{
int i;
for( i = 0; i < size ; i ++)
if ( !test_bit(idx + i, ( void * ) st_addr)) {
return 0;
}
return 1;
}
#define TEMP_DEBUG 1
#ifdef __DEBUG
unsigned long get_map(unsigned long addr)
{
unsigned long ret;
int i;
int map_index = (addr - (unsigned long )rtl_buddy_pool) >> BUDDY_UNIT_MIN
;
for ( i = 0 ; i < sizeof(unsigned long)*8 ; i ++ )
if (test_bit(map_index + i, rtl_buddy_map) )
set_bit(i, &ret);
return ret ;
}
void output_map(void)
{
int i = 0;
while( alloc_addr[i] != 0 ) {
rtl_printf("address %x, map %x, size %x, i %d", alloc_addr[i],\
alloc_map[i],alloc_size[i], alloc_i[i]);
i ++;
}
rtl_printf("\ntotal %d alloc , %d free",i, count);
}
#endif
unsigned long rtl_kmalloc(int size)
{
int index , cur_index, i, result = 1;
unsigned long area, intr_flag;
int map_index;
/* Sanity check first*/
if ( size <= 0 ) return 0;
for ( i = BUDDY_UNIT_MIN; i <= BUDDY_UNIT_MAX; i ++ )
if ( (result = (size >> i)) == 0) { size = (1 << i); break; }
if ( result != 0 ) { rtl_error("size mismatch\n"); return 0;}
cur_index = index = i - BUDDY_UNIT_MIN;
rtl_spin_lock_irqsave(&rtl_buddy_lock, intr_flag);
while ( buddy_header[index] == 0 && index < BUDDY_ORDER)
index ++;
if ( index == BUDDY_ORDER)
{ rtl_error("kmalloc out of memory\n"); goto error_out; }
area = buddy_header[index];
delete(area);
while ( index > cur_index ) {
insert( (unsigned long)&buddy_header[ index - 1 ], area);
area += 1 << ( ( -- index ) + BUDDY_UNIT_MIN);
}
map_index = (area - (unsigned long )rtl_buddy_pool) >> BUDDY_UNIT_MIN ;
set_str(rtl_buddy_map, map_index, 1 << index);
#ifdef __DEBUG
rtl_printf(test_full( (unsigned long )rtl_buddy_map, map_index, 1 <<
index)?"full":"not full");
#endif
rtl_spin_unlock_irqrestore(&rtl_buddy_lock, intr_flag);
#ifdef __DEBUG
alloc_addr[pointer] = area;
alloc_size[pointer] = size;
alloc_map[pointer] = get_map(area);
alloc_i[pointer] = i;
pointer ++;
#endif
return area;
error_out:
rtl_spin_unlock_irqrestore(&rtl_buddy_lock, intr_flag);
return 0;
}
int rtl_kfree( void * ptr, int size)
{
unsigned long addr = (unsigned long ) ptr;
int result, order, map_index, i;
unsigned long buddy, intr_flag;
#ifdef __DEBUG
count ++;
#endif
if ( size <= 0 || addr == 0 ) return -1;
for( i = BUDDY_UNIT_MIN; i <= BUDDY_UNIT_MAX; i ++ )
if ( (result = (size >> i)) == 0) { size = 1 << i; break;}
if ( result != 0 ) { rtl_error("size mismatch\n"); return -1;}
if( (addr & (~((~0) << i) ) ) != 0)
{ rtl_printf("buggy address %x ", addr); return -1;}
order = i - BUDDY_UNIT_MIN;
map_index = (addr - (unsigned long )rtl_buddy_pool) >> BUDDY_UNIT_MIN ;
#ifdef __DEBUG
rtl_printf("about to clear str index %d, order%d\n", map_index, order);
if (!test_full((unsigned long)rtl_buddy_map, map_index, 1 << order ))
rtl_printf("!!!!Bit map error! addr =%x 1<<order = %d\n",addr,1<< order);
#endif
rtl_spin_lock_irqsave(&rtl_buddy_lock, intr_flag);
clear_str( rtl_buddy_map , map_index, 1 << order );
while( i < BUDDY_UNIT_MAX )
buddy = addr ^ ( 1 << i );
map_index = (buddy - (unsigned long)rtl_buddy_pool) >> BUDDY_UNIT_MIN;
if (! test_empty((unsigned long)rtl_buddy_map, map_index, 1 << order ))
break;
#ifdef __DEBUG
rtl_printf(test_empty((unsigned long)rtl_buddy_map, map_index, 1 <<
(order) )?"empty":"!empty");
rtl_printf("buddy is %x prev %x, next %x\n", buddy, BUDDY_PREV(buddy),
BUDDY_NEXT(buddy));
#endif
delete(buddy);
order ++; i ++;
addr &= (~0) << i;
#ifdef __DEBUG
rtl_printf("merge to %d\n", i);
#endif
}
insert( (unsigned long)&buddy_header[order], addr );
rtl_spin_unlock_irqrestore(&rtl_buddy_lock, intr_flag);
return 0;
}
#if TEMP_DEBUG
void output_buddy( void )
{
int i , header ;
for ( i = 0; i < BUDDY_ORDER; i ++) {
int t = 0;
header = buddy_header[i] ;
rtl_printf("order %d", i + BUDDY_UNIT_MIN );
while ( header != 0) {
t ++;
rtl_printf( " %x", header);
header = BUDDY_NEXT(header);
}
rtl_printf("\ntotal: %d\n", t);
}
/*
for ( i = 0; i < BUDDY_ORDER; i ++) {
int t = 0;
header = buddy_header[i] ;
printk("order %x", i + BUDDY_UNIT_MIN );
while ( header != 0) {
t ++;
printk( " %x", header);
printk( " next %x", BUDDY_NEXT(header) );
printk( " prev %x", BUDDY_PREV(header) );
header = BUDDY_NEXT(header);
}
printk("\ntotal: %d\n", t);
}
*/
}
#endif
void test_mf(void)
{
unsigned long addr1, addr2;
addr1 = rtl_kmalloc(500);
addr2 = rtl_kmalloc(10);
rtl_kfree(addr1, 500);
rtl_kfree(addr2, 10);
addr1 = rtl_kmalloc(500);
addr2 = rtl_kmalloc(10);
rtl_kfree(addr1, 500);
rtl_kfree(addr2, 10);
addr1 = rtl_kmalloc(500);
addr2 = rtl_kmalloc(10);
rtl_kfree(addr1, 500);
rtl_kfree(addr2, 10);
addr1 = rtl_kmalloc(500);
addr2 = rtl_kmalloc(10);
rtl_kfree(addr1, 500);
rtl_kfree(addr2, 10);
addr1 = rtl_kmalloc(500);
addr2 = rtl_kmalloc(10);
rtl_kfree(addr1, 500);
rtl_kfree(addr2, 10);
addr1 = rtl_kmalloc(500);
addr2 = rtl_kmalloc(10);
rtl_kfree(addr1, 500);
rtl_kfree(addr2, 10);
output_buddy();
output_map();
}
int init_module(void)
{
int i;
unsigned long addr;
rtl_buddy_pool =(void *) __get_free_pages(GFP_KERNEL|GFP_DMA,
RTL_BUDDY_POOL_ORDER);
rtl_buddy_start_addr = ( unsigned long )rtl_buddy_pool;
rtl_buddy_end_addr = rtl_buddy_start_addr + \
(1 << ( RTL_BUDDY_POOL_ORDER + PAGE_SHIFT ));
if ( rtl_buddy_pool == NULL) {
rtl_error("buddy memory allocate failed \n");
goto alloc_fail_out;
}
memset(rtl_buddy_pool, 0 , PAGE_SIZE << RTL_BUDDY_POOL_ORDER);
rtl_printf("buddy pool %p\n",rtl_buddy_pool);
buddy_map_size = (PAGE_SIZE << RTL_BUDDY_POOL_ORDER) >> BUDDY_UNIT_MIN;
buddy_map_size = (buddy_map_size + 7)/ 8;
buddy_map_size = ((buddy_map_size + 3)/4) * 4; /*4 byte aligned*/
rtl_printf("the result of map size now is %d",buddy_map_size);
rtl_buddy_map = kmalloc(buddy_map_size, GFP_KERNEL);
if (rtl_buddy_map == NULL) {
rtl_error("buddy map allocate fail");
goto map_fail_out;
}
rtl_printf("map pointer %p",rtl_buddy_map);
memset(rtl_buddy_map, 0 , buddy_map_size); /*all free now*/
addr = (unsigned long)rtl_buddy_pool;
for( i = 0 ; i < BUDDY_ORDER - 1; i ++)
buddy_header[i] = 0;
/* chain all of them on the link of biggest chunk*/
while((void *)addr < rtl_buddy_pool + \
(PAGE_SIZE << RTL_BUDDY_POOL_ORDER) ) {
insert( (unsigned long) &buddy_header[BUDDY_ORDER - 1], addr);
addr += 1 << BUDDY_UNIT_MAX;
}
test_mf();
return 0;
map_fail_out :
free_pages( (int) rtl_buddy_pool, RTL_BUDDY_POOL_ORDER);
alloc_fail_out:
return 0;
}
void cleanup_module( void )
{
if ( rtl_buddy_map != NULL)
kfree( rtl_buddy_map );
if ( rtl_buddy_pool != NULL )
free_pages( (int) rtl_buddy_pool, RTL_BUDDY_POOL_ORDER);
}
-- [rtl] ---
To unsubscribe:
echo "unsubscribe rtl" | mail [EMAIL PROTECTED] OR
echo "unsubscribe rtl <Your_email>" | mail [EMAIL PROTECTED]
---
For more information on Real-Time Linux see:
http://www.rtlinux.org/rtlinux/
