#include "../h/local.h"

#ifdef  SCCS_ID
static char SCCS_ID [] = "@(#)malloc.c    	3.4	 12:36:47 - 82/02/04 ";
#endif  SCCS_ID

#include "../h/param.h"
#include "../h/systm.h"
#include "../h/map.h"
#ifdef  UCB_METER
#include "../h/vm.h"
#endif  UCB_METER

#ifdef  CHKMAP
#define ppanic(z) printf ("return address = %x\n", retaddr);
#define retad(x) (((int *) &(x))[-1])
#endif  CHKMAP

/*
 * Allocate 'size' units from the given
 * map. Return the base of the allocated
 * space.
 * In a map, the addresses are increasing and the
 * list is terminated by a 0 size.
 * The core map unit is 64 bytes; the swap map unit
 * is 512 bytes.
 * Algorithm is first-fit.
 */
malloc(mp, size)
struct map *mp;
{
	register unsigned int a;
	register struct map *bp;

#ifdef  CHKMAP
	if (mp == swapmap && size == 0)
		printf ("mallocing size 0\n");
	mverify (mp, retad (mp));
#endif  CHKMAP
	for (bp=mp; bp->m_size; bp++) {
		if (bp->m_size >= size) {
			a = bp->m_addr;
			bp->m_addr += size;
			if ((bp->m_size -= size) == 0) {
				do {
					bp++;
					(bp-1)->m_addr = bp->m_addr;
				} while ((bp-1)->m_size = bp->m_size);
			}
#ifdef  UCB_METER
			if (mp == coremap)
				freemem -= size;
#endif  UCB_METER
			return(a);
		}
	}
	return(0);
}

/*
 * Free the previously allocated space aa
 * of size units into the specified map.
 * Sort aa into map and combine on
 * one or both ends if possible.
 */
mfree(mp, size, a)
struct map *mp;
register int a;
{
	register struct map *bp;
	register unsigned int t;
#ifdef  CHKMAP
	int *retaddr;

	retaddr = retad(mp);
	if (mp == swapmap && size == 0)
		printf ("mfreeing size 0\n");
	/* make sure mfree addr not out of range */
	if (mp == swapmap && a + size > nswap + CLSIZE) {
		printf ("mfree: out of range %d %d\n", a, size);
		prmap (mp);
		ppanic ("");
		return;
	}
#endif  CHKMAP
	if ((bp = mp)==coremap && runin) {
		runin = 0;
		wakeup((caddr_t)&runin);	/* Wake scheduler when freeing core */
	}
#ifdef  UCB_METER
	if (mp == coremap)
		freemem += size;
#endif  UCB_METER
#ifdef  CHKMAP
	mverify (mp, retaddr);
#endif  CHKMAP
#ifdef  USTEST
	for (; USTOI(bp->m_addr) <= a && bp->m_size!=0; bp++)
#else   USTEST
	for (; bp->m_addr<=a && bp->m_size!=0; bp++)
#endif  USTEST
		continue;
#ifdef  CHKMAP
	if (bp>mp) {
		register int prevtop;
		prevtop = (bp-1)->m_addr+(bp-1)->m_size;
		if (mp == swapmap && prevtop > a) {
			printf ("mfree: inside already free segment %d %d\n",
				a, size);
			prmap (mp);
			ppanic ("");
			return;
		}
		if (prevtop < a)
			goto insert;
#else   CHKMAP
	if (bp>mp && (bp-1)->m_addr+(bp-1)->m_size == a) {
#endif  CHKMAP
		/* coalesce with a lower entry */
		(bp-1)->m_size += size;
#ifdef  USTEST
		if (a+size == USTOI(bp->m_addr)) {
#else   USTEST
		if (a+size == bp->m_addr) {
#endif  USTEST
			(bp-1)->m_size += bp->m_size;
			while (bp->m_size) {
				bp++;
				(bp-1)->m_addr = bp->m_addr;
				(bp-1)->m_size = bp->m_size;
			}
		}
	} else {
#ifdef  CHKMAP
 insert:
#endif  CHKMAP
#ifdef  USTEST
		if (a+size == USTOI(bp->m_addr) && bp->m_size) {
#else   USTEST
		if (a+size == bp->m_addr && bp->m_size) {
#endif  USTEST
			bp->m_addr -= size;
			bp->m_size += size;
		} else if (size) {
#ifdef  CHKMAP
			if (   mp == swapmap
			    && a + size > USTOI(bp->m_addr)
			    && bp->m_size) {
				printf ("mfree: overlaps %d %d\n", a, size);
				prmap (mp);
				ppanic ("");
				return;
			}
#endif  CHKMAP
			do {
				t = bp->m_addr;
				bp->m_addr = a;
				a = t;
				t = bp->m_size;
				bp->m_size = size;
				bp++;
			} while (size = t);
		}
	}
/* CGL BUG FIX...mfree did not check for map overflow  1jul81 */
	if (bp >= &mp[mp == coremap ? cmapsiz - 1 : smapsiz - 1])
		panic("mfree map not big enough");
/* end */
}

#ifdef  CHKMAP
/*
 * Verify that the map is not all hosed up.
 * In a map, the addresses are increasing and the
 * list is terminated by a 0 size.
 */
mverify (mp, retaddr)
struct map *mp;
int *retaddr;
{
	register struct map *bp;
	register int max;

	if (mp != swapmap)
		return;
	max = nswap + CLSIZE;
	if (mp->m_size)
		for (bp = mp; (&bp[1])->m_size; bp++) {
			if (bp->m_addr + bp->m_size > max) {
				printf ("mverify: entry out of range: %d\n",
					 bp->m_addr);
				prmap (mp);
				ppanic ("");
			}
			else if (bp->m_addr + bp->m_size
				 >= USTOI((&bp[1])->m_addr)) {
				printf ("mverify: overlap: %d\n",
					 bp->m_addr);
				prmap (mp);
				ppanic ("");
			}
		}
	return;
}

/* print out the swapmap */
prmap (map)
struct map *map;
{
	register int tmp;
	register int ltmp;

	for (tmp = 0; tmp < smapsiz && map[tmp].m_size; tmp += 4) {
		for(ltmp = 0; ltmp < 4; ++ltmp)
			printf("%d\t%d%s",
			       map[tmp + ltmp].m_size,
			       map[tmp + ltmp].m_addr, ltmp == 3 ? "" : "\t");
		printf("\n");
	}
	return;
}
#endif  CHKMAP