/*
 |  Memory management mechanisms
 |  This is entirely MAPUX: no UZI here
*/

#include <sys/unix.h>
#include <sys/memman.h>
#include <sys/extern.h>

memblk *addtoblk();
void memmanMoveBlks();

/* These are essentially inline functions and should help speed things
   up a bit */

#define addtoblk(a)		(&(memmap[(int)a/BLKSIZE]))
#define blktoadd(a)		((char*)((((int)a-(int)memmap)/sizeof(memblk))*BLKSIZE))
#define wholeblks(a)		((a+BLKSIZE-1)/BLKSIZE)
#define memmanFindFree()	(freelist.next)
#define memmanIsValid(a)	(a->vaddr==blktoadd(a))
#define memmanPartOf(l,b)	(b->home==l)


 /*
 |  This needs to be called as soon as possable
*/
void memmanInit()
{
	memblk	*blk;
	memblk	*last;
	char	*addr;

	/* This will need to be changed, expanded or possibly automated for
	   Amigas with different memory organisations */

	/* Start by constructing the deadlist (memory used by system) */
	last = &deadlist;
	last->prev = 0;
	for(addr=0;addr<(char*)KERTOP;addr+=BLKSIZE)
	{
		blk = last->next = addtoblk(addr);
		blk->vaddr = addr;
		blk->prev = last;
		blk->home = &deadlist;
		last = blk;
	}
	last->next = 0;

	/* Next, all the rest of memory becomes the freelist */
	last = &freelist;
	last->prev = 0;
	for(addr=(char*)KERTOP;addr<(char*)MEMSIZE;addr+=BLKSIZE)
	{
		blk = last->next = addtoblk(addr);
		blk->vaddr = addr;
		blk->prev = last;
		blk->home = &freelist;
		last = blk;
	}
	last->next = 0;

	freemem = MEMSIZE - KERTOP;

	return;
}


 /*
 |  Returns the amount of overrun (in blocks) of a memory area blks long
 |  from the block here
*/
int memmanGetOverrun( here, blks )
memblk	*here;
int	blks;
{
	int	res = 0;
	while( here && (++res<blks) )
		here = here->next;
	return( blks - res );
}


 /*
 |  Calculates the length of a list
*/
int memmanListLen( list )
memblk	*list;
{
	int	count = 0;
	while( list )
	{
		count++;
		list = list->next;
	}
	return( count );
}


 /*
 |  Try to allocate a brand new piece of memory.
 |  It is added to the memory list of a particular process identified by the
 |  pararmeter.
*/
char *memmanAlloc( list, size, addr, resv )
memblk	*list;
int	size;
char	*addr;
int	resv;
{
	int	nblks = wholeblks( size );
	memblk	*this, *freeb, *start, *bstart;
	int	num, tot, bestlen, back, i;
	char	*base, *proposed;
	int	lastmove;

	if( nblks == 0 )
	{
		warning( "Tried to memmanNew(x,0)\n" );
		return( -1 );
	}

	/* If a specific address has been requested (for a fork() persumably),
	   try to return that piece of physical memory (should never work?) */
	if( addr && memmanPartOf(&freelist,addtoblk(addr)) && 
	    (memmanGetOverrun(&freelist,nblks)==0) )
	{
		bstart = addtoblk(addr);
		goto mapper;
	}

	/* The second thing is to find a contiguous free area we can use */
	this = bstart = start = memmanFindFree();
	bestlen = 1;

	num = 1;
	tot = 0;
	while( this )
	{
		tot++;
		if( this->next == this+1 )
		{
			if( ++num >= nblks )
			{
				bstart = start;
				break;
			}
		}
		else
		{
			if( num > bestlen )
			{
				bestlen = num;
				bstart = start;
			}
			num = 1;
			start = this->next;
		}
		this = this->next;
	}

	/* Out of memory */
	if( tot+1 < nblks )
		return(0);

	/* Proposed virtual address - coincides with first physical */
	proposed = blktoadd(bstart);

	/* Found a suitable contiguous lump */
	if( num >= nblks )
		goto mapper;
	
	 /*
	 |  Space, but it's dotted about.
	*/

	/* Move back if longest area is too near the end */
	/* Note we move far enough to fit in the reserved bit too */
	back = memmanGetOverrun( bstart, nblks+resv );
	while( back && (bstart->prev) )
		bstart = bstart->prev;

	 /*
	 |  One extra thing: virtual address must not clash.  This may be an
	 |  unsoluble problem.  Knickers if it is - call fails.
	*/
	kprintf("<memman check %x>",proposed); 
	/* This stops infinite up/down/up/down loops */
	lastmove = 0;
	while(1)
	{
		int	hit = 0;
		char	*lowhit = (char*)MEMSIZE,
			*tophit = (char*)0,
			*gapend;
		this = list->next;
		while( this )
		{
			/* Check the block itself */
			if( (this->vaddr>proposed) &&
			    (this->vaddr<(proposed+(BLKSIZE*nblks))) )
			{
				hit = 1;
				if( this->vaddr < lowhit )
					lowhit = this->vaddr;
				if( this->vaddr > tophit )
					tophit = this->vaddr;
			}
			/* Also check a possible reserved area attached */
			gapend = this->vaddr+(this->gap*BLKSIZE);
			if( ( gapend > proposed ) && 
			    ( gapend < (proposed+(nblks*BLKSIZE)) ) )
			{
				hit = 1;
				if( gapend < lowhit )	/* Is this line right? */
					lowhit = this->vaddr;
				if( gapend > tophit )
					tophit = this->vaddr;
			}
			this = this->next;
		}
		/* No clash, continue */
		if( hit == 0 )
			break;
		/* There is a clash, so try to fix it by moving the new one down */
		if( (((int)lowhit-(nblks*BLKSIZE)) >= KERTOP) && (lastmove != 1) )
		{
			lastmove = -1;
			proposed = lowhit-(nblks*BLKSIZE);
			continue;
		}
		/* Alternatively move the new vitual address up */
		if( (((int)tophit+(nblks*BLKSIZE)) < MEMSIZE) && (lastmove != -1) )
		{
			lastmove = 1;
			proposed = tophit+(nblks*BLKSIZE);
			continue;
		}
		/* If we get here then we couldn't resolve the conflict */
		warning("memmanAlloc failedi (vaddr conflict)");
		return( 0 );	/* Whole call fails */
	}


	/* Move the blocks from the freelist and create an address mapping */
mapper:
	memmanMoveBlks( &freelist, list, bstart, nblks );
	base = addr ? addr : proposed;
	for( this=bstart, i=0; i<nblks; i++, base+=BLKSIZE )
	{
		qzero( blktoadd(this), BLKSIZE/4 );
		this->vaddr = base;
		this = this->next;
	}

	this->prev->gap = resv;

	return( bstart->vaddr );
}


 /*
 |  Moves num blocks from the slist to the dlist starting with block first
*/
void memmanMoveBlks( slist, dlist, first, num )
memblk	*slist,
	*dlist,
	*first;
int	num;
{
	memblk	*nlink, *after, *ofirst;
	int	i;

	if( num==0 )
		return;

	/* A useful number: the address of the block following the segment */
	/* Also updates the blocks owner (optimisation only) and eliminates
	   reserved gaps */
	i = num;
	after = first;
	while( after && i-- )
	{
		after->home = dlist;
		after->gap = 0;
		after = after->next;
		if( dlist == &freelist )
			freemem += BLKSIZE;
		if( slist == &freelist )
			freemem -= BLKSIZE;
	}

	/* This will be overwritten unless the operation is a simple join */
	if( after )
		after->prev->next = 0;

	/* This removes the segment from the orginal list */
	first->prev->next = after;
	if( after )
		after->prev = first->prev;

	/* The additional list segment and the destination list may be interleaaved */
	while( 1 )
	{
		if( dlist->next == 0 )
		{
			dlist->next = first;
			first->prev = dlist;
			break;
		}
		if( dlist->next < first )
			dlist = dlist->next;
		else if( dlist->next > first )
		{
			nlink = dlist->next;
			dlist->next = first;
			first->prev = dlist;
			while( first->next && (first->next<nlink) && --num )
				first = first->next;
			num--;
			if( num == 0 )
			{
				first->next = nlink;
				nlink->prev = first;
				break;
			}
			ofirst = first->next;
			first->next = nlink;
			nlink->prev = first;
			first = ofirst;
			dlist = nlink;
		}
		else if( dlist->next == first )
			panic( "Memory list collision\n");
	}
	return;
}


 /*
 |  Moves blocks about to validate a memory list
*/
int memmanValidate( list )
memblk	*list;
{
	memblk	*here,
		*oblk;

	here = list->next;

	while( here )
	{
		memblk	*nxt = here->next;
		if( memmanIsValid(here)==0 )
		{
			/* di() */
			qswap( blktoadd(here), here->vaddr, BLKSIZE/4 );
			oblk = addtoblk(here->vaddr);
			memmanMoveBlks( list, oblk->home, here, 1 );
			memmanMoveBlks( oblk->home, list, oblk, 1 );
			/* ei() */
		}
		here = nxt;
	}
	return( 1 );
}


 /*
 |  Frees a process memory blocks
*/
memmanFree( list )
memblk	*list;
{
	if( list->next != 0 )
	{
		memmanMoveBlks( list, &freelist, list->next, memmanListLen(list->next) );
		list->next = 0;
	}
}


 /*
 |  Creates a copy of a given list
 |  This can easily fail because of lack of memory
 |  Note list is a pointer to the first block in the source, but dest
 |  is a pointer to a root block
*/
int memmanDupList( list, dest )
memblk	*list,
	*dest;
{
	dest->next = 0;
	if( memmanAlloc( dest, memmanListLen(list)*BLKSIZE, list->vaddr ) )
	{
		memblk	*new  = dest->next,
			*here = list;
		while( here )
		{
			new->vaddr = here->vaddr;
			qcopy( blktoadd(here), blktoadd(new), BLKSIZE/4 );
			new = new->next;
			here = here->next;
		}
		return( 1 );
	}
	return( 0 );
}