ofmem.c

open source bios with linux platform, very good and can be reused.

/* 
 *   Creation Date: <1999/11/07 19:02:11 samuel>
 *   Time-stamp: <2004/01/07 19:42:36 samuel>
 *   
 *	<ofmem.c>
 *	
 *	OF Memory manager
 *   
 *   Copyright (C) 1999-2004 Samuel Rydh ([e-mail])
 *   Copyright (C) 2004 Stefan Reinauer
 *   
 *   This program is free software; you can redistribute it and/or
 *   modify it under the terms of the GNU General Public License
 *   as published by the Free Software Foundation
 *   
 */

/* TODO: Clean up MOLisms in a decent way */

#include "openbios/config.h"
#include "openbios/bindings.h"
#include "libc/string.h"
#include "ofmem.h"
#include "kernel.h"
#ifdef I_WANT_MOLISMS
#include "mol/prom.h"
#include "mol/mol.h"
#endif
#include "mmutypes.h"
#include "asm/processor.h"
#ifdef I_WANT_MOLISMS
#include "osi_calls.h"
#endif

#define BIT(n)		(1U<<(31-(n)))

/* called from assembly */
extern void	dsi_exception( void );
extern void	isi_exception( void );
extern void	setup_mmu( ulong code_base, ulong code_size, ulong ramsize );

/****************************************************************
 * Memory usage (before of_quiesce is called)
 *
 *			Physical
 *
 *	0x00000000	Exception vectors	
 *	0x00004000	Free space
 *	0x01e00000	Open Firmware (us)
 *	0x01f00000	OF allocations
 *	0x01ff0000	PTE Hash
 *	0x02000000-	Free space
 *
 * Allocations grow downwards from 0x01e00000 
 *
 ****************************************************************/

#define HASH_SIZE		(2 << 15)
#define SEGR_BASE		0x400		/* segment number range to use */

#define FREE_BASE_1		0x00004000
#define OF_CODE_START		0x01e00000
/* #define OF_MALLOC_BASE	0x01f00000 */
extern char _end[];
#define OF_MALLOC_BASE		_end

#define HASH_BASE		(0x02000000 - HASH_SIZE)
#define FREE_BASE_2		0x02000000

#define RAMSIZE			0x02000000	/* XXXXXXXXXXXXXXXXXXX FIXME XXXXXXXXXXXXXXX */

typedef struct alloc_desc {
	struct alloc_desc 	*next;
	int			size;			/* size (including) this struct */
} alloc_desc_t;

typedef struct mem_range {
	struct mem_range	*next;
	ulong			start;
	ulong			size;
} range_t;

typedef struct trans {
	struct trans		*next;
	ulong			virt;			/* chain is sorted by virt */
	ulong			size;
	ulong			phys;
	int			mode;
} translation_t;

static struct {
	char 			*next_malloc;
	alloc_desc_t		*mfree;			/* list of free malloc blocks */

	range_t			*phys_range;
	range_t			*virt_range;

	translation_t		*trans;			/* this is really a translation_t */
} ofmem;


/************************************************************************/
/*	OF private allocations						*/
/************************************************************************/

void *
malloc( int size ) 
{
	alloc_desc_t *d, **pp;
	char *ret;

	if( !size )
		return NULL;

	if( !ofmem.next_malloc )
		ofmem.next_malloc = (char*)OF_MALLOC_BASE;
	
	if( size & 3 )
		size += 4 - (size & 3);
	size += sizeof(alloc_desc_t);
	
	/* look in the freelist */
	for( pp=&ofmem.mfree; *pp && (**pp).size < size; pp = &(**pp).next )
		;

	/* waste at most 4K by taking an entry from the freelist */
	if( *pp && (**pp).size < size + 0x1000 ) {
		ret = (char*)*pp + sizeof(alloc_desc_t);
		memset( ret, 0, (**pp).size - sizeof(alloc_desc_t) );
		*pp = (**pp).next;
		return ret;
	}

	if( (ulong)ofmem.next_malloc + size > HASH_BASE ) {
		printk("out of malloc memory (%x)!\n", size );
		return NULL;
	}
	d = (alloc_desc_t*) ofmem.next_malloc;
	ofmem.next_malloc += size;

	d->next = NULL;
	d->size = size;

	ret = (char*)d + sizeof(alloc_desc_t);
	memset( ret, 0, size - sizeof(alloc_desc_t) );
	return ret;
}

void
free( void *ptr )
{
	alloc_desc_t **pp, *d;

	/* it is legal to free NULL pointers (size zero allocations) */
	if( !ptr )
		return;
	
	d = (alloc_desc_t*)(ptr - sizeof(alloc_desc_t));
	d->next = ofmem.mfree;

	/* insert in the (sorted) freelist */
	for( pp=&ofmem.mfree; *pp && (**pp).size < d->size ; pp = &(**pp).next )
		;
	d->next = *pp;
	*pp = d;
}

void *
realloc( void *ptr, size_t size ) 
{
	alloc_desc_t *d = (alloc_desc_t*)(ptr - sizeof(alloc_desc_t));
	char *p;
	
	if( !ptr )
		return malloc( size );
	if( !size ) {
		free( ptr );
		return NULL;
	}
	p = malloc( size );
	memcpy( p, ptr, MIN(d->size - sizeof(alloc_desc_t),size) );
	free( ptr );
	return p;
}


/************************************************************************/
/*	debug 								*/
/************************************************************************/

#if 0
static void
print_range( range_t *r, char *str )
{
	printk("--- Range %s ---\n", str );
	for( ; r; r=r->next )
		printk("%08lx - %08lx\n", r->start, r->start + r->size -1 );
	printk("\n");
}

static void
print_phys_range() 
{
	print_range( ofmem.phys_range, "phys" );
}

static void
print_virt_range() 
{
	print_range( ofmem.virt_range, "virt" );
}

static void
print_trans( void )
{
	translation_t *t = ofmem.trans;

	printk("--- Translations ---\n");
	for( ; t; t=t->next )
		printk("%08lx -> %08lx [size %lx]\n", t->virt, t->phys, t->size );
	printk("\n");
}
#endif


/************************************************************************/
/*	misc								*/
/************************************************************************/

static inline int
def_memmode( ulong phys )
{
	/* XXX: Guard bit not set as it should! */
	if( phys < 0x80000000 || phys >= 0xffc00000 )
		return 0x02;	/*0xa*/	/* wim GxPp */
	return 0x6a;		/* WIm GxPp, I/O */
}


/************************************************************************/
/*	client interface						*/
/************************************************************************/

static int
is_free( ulong ea, ulong size, range_t *r )
{
	if( size == 0 )
		return 1;
	for( ; r ; r=r->next ) {
		if( r->start + r->size - 1 >= ea && r->start <= ea )
			return 0;
		if( r->start >= ea && r->start <= ea + size - 1 )
			return 0;
	}
	return 1;
}

static void
add_entry_( ulong ea, ulong size, range_t **r )
{
	range_t *nr;
	
	for( ; *r && (**r).start < ea; r=&(**r).next )
		;
	nr = (range_t*)malloc( sizeof(range_t) );
	nr->next = *r;
	nr->start = ea;
	nr->size = size;
	*r = nr;
}

static int
add_entry( ulong ea, ulong size, range_t **r )
{
	if( !is_free( ea, size, *r ) ) {
		printk("add_entry: range not free!\n");
		return -1;
	}
	add_entry_( ea, size, r );
	return 0;
}

static void
join_ranges( range_t **rr )
{
	range_t *n, *r = *rr;
	while( r ) {
		if( !(n=r->next) )
			break;

		if( r->start + r->size - 1 >= n->start -1 ) {
			int s = n->size + (n->start - r->start - r->size);
			if( s > 0 )
				r->size += s;
			r->next = n->next;
			free( n );
			continue;
		}
		r=r->next;
	}
}

static void
fill_range( ulong ea, int size, range_t **rr )
{
	add_entry_( ea, size, rr );
	join_ranges( rr );
}

static ulong
find_area( ulong align, ulong size, range_t *r, ulong min, ulong max, int reverse )
{
	ulong base = min;
	range_t *r2;
	
	if( (align & (align-1)) ) {
		printk("bad alignment %ld\n", align);
		align = 0x1000;
	}
	if( !align )
		align = 0x1000;
	
	base = reverse ? max - size : min;
	r2 = reverse ? NULL : r;
	
	for( ;; ) {
		if( !reverse ) {
			base = (base + align - 1) & ~(align-1);
			if( base < min )
				base = min;
			if( base + size - 1 >= max -1 )
				break;
		} else {
			if( base > max - size )
				base = max - size;
			base -= base & (align-1);
		}
		if( is_free( base, size, r ) )
			return base;

		if( !reverse ) {
			if( !r2 )
				break;
			base = r2->start + r2->size;
			r2 = r2->next;
		} else {
			range_t *rp;
			for( rp=r; rp && rp->next != r2 ; rp=rp->next )
				;
			r2 = rp;
			if( !r2 )
				break;
			base = r2->start - size;