/*
 *
 * Copyright 1994 FirmWorks, Mountain View CA USA. All rights reserved.
 * Copyright (c) 1995 FirePower Systems, Inc.
 *
 * $RCSfile: vrmalloc.c $
 * $Revision: 1.6 $
 * $Date: 1996/02/17 00:41:29 $
 * $Locker:  $
 *
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * A  "smarter" malloc				William L. Sebok
 *						Sept. 24, 1984
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *	 If n = the size of an area rounded DOWN to the nearest power of two,
 *	all free areas of memory whose length is the same index n is organized
 *	into a chain with other free areas of index n. A request for memory
 *	takes the first item in the chain whose index is the size of the
 *	request rounded UP to the nearest power of two.  If this chain is
 *	empty the next higher chain is examined.  If no larger chain has memory
 *	then new memory is allocated.  Only the amount of new memory needed is
 *	allocated.  Any old free memory left after an allocation is returned
 *	to the free list.  Extra new memory returned because of rounding
 *	to page boundaries is returned to free list.
 *
 *	  All memory areas (free or busy) handled by malloc are also chained
 *	sequentially by increasing address.  When memory is freed it is
 *	merged with adjacent free areas, if any.  If a free area of memory
 *	ends at the end of memory (i.e. at the break),  the break is
 *	contracted, freeing the memory back to the system.
 *
 *	Notes:
 *		ov_length field includes sizeof(struct overhead)
 *		adjacency chain includes all memory, allocated plus free.
 */

#include "veneer.h"

#define	MAGIC_FREE	0x548a934c
#define	MAGIC_BUSY	0xc139569a

#define NBUCKETS	24
#define NALIGN		4

struct qelem {
	struct qelem *q_forw;
	struct qelem *q_back;
};

struct overhead {
	struct qelem	ov_adj;		/* adjacency chain pointers */
	struct qelem	ov_buk;		/* bucket chain pointers */
	long		ov_magic;
	unsigned long	ov_length;
};

char endfree = 0;
struct qelem adjhead = { &adjhead, &adjhead };
struct qelem buckets[NBUCKETS] = {
	&buckets[0],  &buckets[0],
	&buckets[1],  &buckets[1],
	&buckets[2],  &buckets[2],
	&buckets[3],  &buckets[3],
	&buckets[4],  &buckets[4],
	&buckets[5],  &buckets[5],
	&buckets[6],  &buckets[6],
	&buckets[7],  &buckets[7],
	&buckets[8],  &buckets[8],
	&buckets[9],  &buckets[9],
	&buckets[10], &buckets[10],
	&buckets[11], &buckets[11],
	&buckets[12], &buckets[12],
	&buckets[13], &buckets[13],
	&buckets[14], &buckets[14],
	&buckets[15], &buckets[15],
	&buckets[16], &buckets[16],
	&buckets[17], &buckets[17],
	&buckets[18], &buckets[18],
	&buckets[19], &buckets[19],
	&buckets[20], &buckets[20],
	&buckets[21], &buckets[21],
	&buckets[22], &buckets[22],
	&buckets[23], &buckets[23],
};

/*
 * The following macros depend on the order of the elements in struct overhead
 */
#define TOADJ(p)	((struct qelem *)(p))
#define FROMADJ(p)	((struct overhead *)(p))
#define FROMBUK(p)	((struct overhead *)( (char *)p - sizeof(struct qelem)))
#define TOBUK(p)	((struct qelem *)( (char *)p + sizeof(struct qelem)))

#ifndef CURBRK
#define CURBRK	sbrk(0)
#endif CURBRK

STATIC void insque(), remque();

#ifdef	NULL
#undef  NULL
#endif
#define NULL	0
#ifdef debug
# define ASSERT(p,q)	if (!(p)) fatal(q)
#else
# define ASSERT(p,q)
#endif

#define ALIGN(n, granule)  ((n + ((granule)-1)) & ~((granule)-1))

char *
malloc(nbytes)
	unsigned nbytes;
{
	register struct overhead *p, *q;
	register int surplus = 0;
	register struct qelem *bucket;
	nbytes = ALIGN(nbytes, NALIGN) + sizeof(struct overhead);
	bucket = &buckets[log2(nbytes-1) + 1];	/* log2 rounded up */
	for (p = NULL; bucket < &buckets[NBUCKETS]; bucket++) {
		if (bucket->q_forw != bucket) {
			/*  remove from bucket chain */
			p = FROMBUK(bucket->q_forw);
			ASSERT(p->ov_magic == MAGIC_FREE, "\nmalloc: Entry \
not marked FREE found on Free List!\n");
			remque(TOBUK(p));
			surplus = p->ov_length - nbytes;
			break;
		}
	}
	if (p == NULL) {
#ifdef USE_SBRK
		register int i;
		p = (struct overhead *)CURBRK;
		if ((int)p == -1) {
			return(NULL);
		}
		if (i = (int)p&(NALIGN-1)) {
			sbrk(NALIGN-i);
		}
		p = (struct overhead *)sbrk(nbytes);
		if ((int)p == -1) {
			return(NULL);
		}
		q = (struct overhead *)CURBRK;
		if ((int)q == -1) {
			return(NULL);
		}
		p->ov_length = (char *)q - (char *)p;
		surplus = p->ov_length - nbytes;
		/* add to end of adjacency chain */
		ASSERT((FROMADJ(adjhead.q_back)) < p, "\nmalloc: Entry in \
adjacency chain found with address lower than Chain head!\n" );
		insque(TOADJ(p),adjhead.q_back);
#else
		struct qelem *pp;
		int alloc_size = ALIGN(nbytes, PAGE_SIZE);

		p = (struct overhead *)alloc(alloc_size, NALIGN);
		if ((int)p == -1) {
			return(NULL);
		}
		p->ov_length = alloc_size;
		surplus = p->ov_length - nbytes;

		/* add to adjacency chain in the correct place */
		for (pp = adjhead.q_forw; pp != &adjhead; pp = pp->q_forw) {
			if (p < FROMADJ(pp)) {
				break;
			}
		}
		ASSERT(pp == &adjhead || (p < FROMADJ(pp)),
		       "\nmalloc: Bogus insertion in adjacency list\n");
		insque(TOADJ(p),pp->q_back);
#endif
	}
	if (surplus > sizeof(struct overhead)) {
		/* if big enough, split it up */
		q = (struct overhead *)( (char *)p + nbytes);
		q->ov_length = surplus;
		p->ov_length = nbytes;
		q->ov_magic = MAGIC_FREE;
		/* add surplus into adjacency chain */
		insque(TOADJ(q),TOADJ(p));
		/* add surplus into bucket chain */
		insque(TOBUK(q),&buckets[log2(surplus)]);
	}
	p->ov_magic = MAGIC_BUSY;
	return((char*)p + sizeof(struct overhead));
}

void
free(mem)
register char *mem;
{
	register struct overhead *p, *q;
	if (mem == NULL) {
		return;
	}
	p = (struct overhead *)(mem - sizeof(struct overhead));
	if (p->ov_magic == MAGIC_FREE) {
		return;
	}
	if (p->ov_magic != MAGIC_BUSY) {
		fatal("attempt to free memory not allocated with malloc!\n");
	}
	q = FROMADJ((TOADJ(p))->q_back);
	if (q != FROMADJ(&adjhead)) {	/* q is not the first list item */
		ASSERT(q < p, "\nfree: While trying to merge a free area with \
a lower adjacent free area,\n addresses were found out of order!\n");
		/* If lower segment can be merged */
		if ((q->ov_magic == MAGIC_FREE) &&
							((char *)q + q->ov_length == (char *)p) ) {

			/* remove lower address area from bucket chain */
			remque(TOBUK(q));
			/* remove upper address area from adjacency chain */
			remque(TOADJ(p));
			q->ov_length += p->ov_length;
			p->ov_magic = NULL;
			p = q;
		}
	}
	q = FROMADJ((TOADJ(p))->q_forw);
	if (q != FROMADJ(&adjhead)) {	/* q is not the last list item */
		/* upper segment can be merged */
		ASSERT(q > p, "\nfree: While trying to merge a free area with \
a higher adjacent free area,\n addresses were found out of order!\n");
		if ( 	(q->ov_magic == MAGIC_FREE) &&
							((char *)p + p->ov_length == (char *)q) ) {

			/* remove upper from bucket chain */
			remque(TOBUK(q));
			/* remove upper from adjacency chain */
			remque(TOADJ(q));
			p->ov_length += q->ov_length;
			q->ov_magic = NULL;
		}
	}
#ifdef USE_SBRK
	/* freed area is at end of memory */
	if ((endfree && adjhead.q_back == TOADJ(p)) &&
						((char*)p + p->ov_length == (char *)CURBRK) ) {

		/* remove from end of adjacency chain */
		remque(adjhead.q_back);
		/* release memory to system */
		sbrk( -((int)(p->ov_length)));
		return;
	}
#endif
	p->ov_magic = MAGIC_FREE;
	/* place in bucket chain */
	insque(TOBUK(p),&buckets[log2(p->ov_length)]);
	return;
}

char *
realloc(mem,nbytes)
register char *mem; unsigned nbytes;
{
	register char *newmem;
	register struct overhead *p, *q;
	register int surplus;
	if (mem == NULL) {
		return(malloc(nbytes));
	}
	if(mem > (char*)FROMADJ(adjhead.q_back) + sizeof(struct overhead)) {
		return(NULL);
	}
	
	p = (struct overhead *)(mem - sizeof(struct overhead));
	nbytes = (nbytes + (NALIGN-1)) & (~(NALIGN-1));
	if (  (p->ov_magic == MAGIC_BUSY) && (q = FROMADJ(adjhead.q_back)) != p
	   && (q->ov_magic != MAGIC_FREE || (FROMADJ(q->ov_adj.q_back) != p)) ) {

		free(mem);
	}
	if( (p->ov_magic == MAGIC_BUSY || p->ov_magic == MAGIC_FREE)
	 && (surplus = p->ov_length - nbytes - sizeof(struct overhead)) >= 0 ) {
		if (surplus > sizeof(struct overhead)) {
			/*  return surplus to free list */
			nbytes += sizeof(struct overhead);
#ifdef USE_SBRK
			/* freed area is at end of memory */
			if ( endfree && adjhead.q_back == TOADJ(p)
			  &&	(char*)p + p->ov_length == (char *)CURBRK ) {
				/* release memory to system */
				sbrk(-surplus);
			} else
#endif
			{
				q = (struct overhead *)( (char *)p + nbytes);
				q->ov_length = surplus;
				q->ov_magic = MAGIC_FREE;
				insque(TOADJ(q),TOADJ(p));
				insque(TOBUK(q),&buckets[log2(surplus)]);
			}
			p->ov_length = nbytes;
		}
		if (p->ov_magic == MAGIC_FREE) {
			remque(TOBUK(p));
			p->ov_magic = MAGIC_BUSY;
		}
		return(mem);
	}
	newmem = malloc(nbytes);
	if (newmem != mem && newmem != NULL) {
		register unsigned n;
		if (p->ov_magic == MAGIC_BUSY || p->ov_magic == MAGIC_FREE) {
			n = p->ov_length - sizeof(struct overhead);
			nbytes = (nbytes < n) ? nbytes : n ;
		}
		bcopy(mem,newmem,nbytes);
	}
	if (p->ov_magic == MAGIC_BUSY) {
		free(mem);
	}
	return(newmem);
}

log2(n)
register int n;
{
	register int i = 0;
	while ((n >>= 1) > 0) {
		i++;
	}
	return(i);
}

void
insque(item,queu)
register struct qelem *item, *queu;
{
	register struct qelem *pueu;
	pueu = queu->q_forw;
	item->q_forw = pueu;
	item->q_back = queu;
	queu->q_forw = item;
	pueu->q_back = item;
}

void
remque(item)
register struct qelem *item;
{
	register struct qelem *queu, *pueu;
	pueu = item->q_forw;
	queu = item->q_back;
	queu->q_forw = pueu;
	pueu->q_back = queu;
}