h29640
s 00960/00000/00000
d D 3.1 84/11/13 16:28:59 dan 1 0
c date and time created 84/11/13 16:28:59 by dan
e
u
U
t
T
I 1
/*  pool.c -- Dynamic storage (pool) management routines
 *  copyright (c) American Information Systems Corporation
 *	Daniel Steinberg
 *	November, 1984
 *
 *  (see POOL.DOC for a detailed description of pool organization)
 */

#include "viosconf.h"
#include "poolfuncs.h"
#include "iopacket.h"

#define BUFSIZE  ALIGN(sizeof(PHDR))
#define ABUFSIZE (BUFSIZE-1)
#define FRCALIGN(a) (int *)a

#define TOOSMALL (1+BUFSIZE)

#define DONT_COMPRESS 'c'
#define DONT_EXTEND   'e'
#define DO_EXTEND     'd'

/* Define integer-sized offsets into the header of pool blocks */
#define FSIZE 0		/* size of free pool block */
#define FNEXT 1		/* ptr to next free pool block */
#define FPREV 2		/* ptr to previous free pool block */

#define ASIZE 0		/* size of allocated pool block */
#define BPTR  1		/* back pointer to bufptr for allocated pool block */
#define ABLK  2		/* start of data section of allocated pool block */

static PHDR *widen_hole();
static PHDR *shuffle();
static PHDR *morepool();
static PHDR *release();
static PHDR *merge_pool();



_i_pool (bot, top)
    int  *bot;
    int  *top;

/* _i_pool (bot, top) -- Initialize pool management structure
 *
 *	in:	bot		lowest available pool address
 *	in:	top		highest available pool address
 *	return:	(NONE)
 *	thrown:	(NONE)
 *
 *	Initializes system dynamic pool as follows:
 *		1) Allocate bufptrs (ptrs to pool buffers) at the
 *		   bottom of the address range 'bot'-'top'.
 *		   The number of initially allocated bufptrs equals
 *		   1/64 of the total number of ints in the pool.
 *		2) Set the maximum bufptr expansion to
 *		   1/8 of the total number of ints in the pool.
 *		3) Link all the bufptrs together and initialize the listhead.
 *		4) Set the rest of pool to be one free buffer and initialize
 *		   the free-listhead.
 *
 *	In a nutshell, the current pool implementation results in allocation
 *	pointers that are dereferenced one level.  All pool allocations
 *	are expressed in terms of a bufptr that is fixed in memory and
 *	contains, at any given moment, the address of the actual pool
 *	allocation.  However, during memory allocations, ANY previously
 *	allocated pool buffer may be shuffled within pool; bufptrs of
 *	shuffled buffers are updated to remain accurate.
 *
 *	This results in a fully compressible (and potentially expandable)
 *	system dynamic pool.  Given the high degree of variation in size
 *	and duration of pool allocations, compressibility is deemed
 *	important enough to offset the added overhead of pointer dereferencing
 *	(and refreshing, after allocations) so that allocation failures due to
 *	fragmented pool are eliminated.
 *
 *	See pool.doc for more information on the link structure of pool.
 */
{
    register int *p;
    register PHDR *ptop;


#ifdef DEBUG4   /*************************************************************/
    if (UNITSIZE NE sizeof(int))
	error("size of int and ptr don't match!\n", NULL);

    if ( (FRCALIGN(bot) NE bot) OR (FRCALIGN(top) NE top) )
    		error("Bad alignment of args to _i_pool\n", NULL);
#endif /* DEBUG4 *************************************************************/

	/* set initial #bufptrs to  1/64th of total pool */
	/* set maximum #bufptrs to  1/8th of total pool */
    pool.numfptrs = (top-bot) >> 6;
    pool.maxptrs = (top-bot) >> 3;

    pool.low = pool.freeptr = p = bot;
    pool.high = top;
    pool.freebuf = ptop = (PHDR*) (pool.ptrtop = p + pool.numfptrs);
    ptop->bfsize = (pool.freetot = top-(int*)ptop) - ABUFSIZE;

    pool.numfbufs = 1;
    pool.numpkts = pool.numcomps = 0;

					/* Link bufptrs together */
    for ( ; p < (int*)ptop;  p = (int*) (*p = (int)(p+1)) );

					/*  and zero last links */
    pool.pktlist = (PHDR*) (ptop->bfnext = ptop->bfprev = (int*) (*--p = NULL));
}

    char **
_a_pool (nbytes)
    unsigned nbytes;

/* _a_pool (nbytes) -- Allocate an n-byte buffer from pool
 *
 *	in:	nbytes		request size in "sizeof" units
 *	return:	(char**)	ptr to the allocated buffer pointer, or NULL
 *	thrown:	(NONE)
 *
 *	Allocate an 'nbytes'-size buffer from pool and return a bufptr to it.
 *	Allocated buffers may be larger than the requested size, but the
 *	requestor must not make use of this fact.  Also, the actual buffer
 *	size and a bufptr back-ptr are stored in memory just before the
 *	allocated buffer and must never be corrupted.  Therefore, allocated
 *	packets may not be divided by releasing parts back into pool.
 *
 *	The allocation algorithm is as follows:
 *		1) Convert 'nbytes' to units of UNITSIZE (== sizeof(int*)).
 *		   This becomes the grain for all pool allocations.
 *		2) Allocate a bufptr for this request.  If there are none
 *		   left, attempt to extend the bufptr space (see ext_ptrs()).
 *		   If this fails, return NULL.
 *		3) If 'nbytes' is equal to the size of an i/o packet and
 *		   there are any 'pre-allocated' i/o packets available,
 *		   delink one and link it to the bufptr and return.
 *		4) If the total free pool is large enough to accomodate the
 *		   request, initiate a first-fit search of the linked
 *		   free buffers.
 *		5) If 3) fails, call morepool() to try to collect enough
 *		   free space into one hole.  If this fails, release the
 *		   bufptr and return NULL.
 *		6) If the size of the located free buffer is within
 *		   TOOSMALL units of the requested size, allocate the entire
 *		   thing and return the bufptr.
 *		7) Otherwise, allocate the buffer from the back (high address
 *		   end) of the hole and return the bufptr.
 *
 *	Since a first-fit/allocate-from-back strategy is employed, allocated
 *	pool should tend to be cycled in clusters roughly according to time of
 *	allocation.  This means that clusters have some time to free up,
 *	minimizing the need for the relatively high-cost data compression.
 *	Also, search time should be short as long as there are not many
 *	very short free blocks located in the front of pool.  If, for instance,
 *	last-fit were employed (searching backward through the free list),
 *	fragmentation in the recently allocated clusters would tend to
 *	slow the search process.
 *
 *	See also morepool() for a description of compression algorithms.
 *
 */
{
    register int    *ptr;	/* ptr to allocated buffer pointer */
    register PHDR      *data;	/* floating ptr into pool data space */
    register unsigned size;	/* corrected allocation size */
    PHDR        *next, *prev;	/* temporary link storage */
    unsigned         dsiz;	/* free data buffer size */

#ifdef DEBUG4   /*************************************************************/
    if (Intstate) error("a_pool at int state\n", NULL);
    if (nbytes EQ 0) error("_a_pool called with size = 0\n", NULL);
    if (pool.low EQ NULL) error("Pool not initialized at _a_pool\n", NULL);
#endif /* DEBUG4 *************************************************************/

    if ( (pool.numfptrs EQ 0) AND (ext_ptrs() EQ 0) ) return(NULL);
    pool.numfptrs--;				/* allocate a bufptr and */
    pool.freeptr = (int*) *(ptr = pool.freeptr);	/* relink free list */

    /* ALIGN call in next statement adjusts nbytes to UNITSIZE units */
    if ( ((size = ALIGN(nbytes)) EQ PKTSIZE) AND
					((data = pool.pktlist) NE NULL) )
	{	/* Return a pre-allocated I/O Packet */

#ifdef DEBUG4   /*************************************************************/
	if ( data->bfsize NE PKTSIZE)
    error("Pre-all packet size corrupted to: %d.\n", data->bfsize);
#endif /* DEBUG4 *************************************************************/

	pool.numpkts--;				/* count 1 less packet held */
	pool.freetot -= (PKTSIZE+ABUFSIZE);	/* subtract size from total */
	*ptr = (int) &data->bfprev;		/* pnt bufptr to data area */
	pool.pktlist = (PHDR*) data->bfnext;	/* relink the free list */
	data->bfnext = ptr;			/* point back to bufptr */
	return ((char**)ptr);
	}

	/* if largest possible hole can fit request, look for it */
    if (size LE ( pool.freetot -
			(pool.numfbufs*ABUFSIZE) -
			(pool.numpkts*(PKTSIZE+ABUFSIZE)) ) )
	{			/* first fit search for a free buffer */
	data = pool.freebuf;
	do  {
	    if ( (dsiz = data->bfsize) GE size )  goto link;
	    }  while( (data = (PHDR*) data->bfnext) NE NULL );
	}

    if ( (data = morepool(size,DO_EXTEND)) EQ NULL )
	{
	pool.numfptrs++;		/* Release bufptr allocated above */
	*ptr = (int) pool.freeptr;	/*   by linking into front of list */
	pool.freeptr = ptr;
	return(NULL);
	}

    dsiz = data->bfsize;

  link:				/* Buffer address: data // Size: dsiz */

    if ( (dsiz -= size) GT TOOSMALL)
	{			/* Allocate from high end of block */
				/* dsiz == old_size - new_data_size */
				/* old_size = dsiz - sizeof(buffer_ptrs) */
	data->bfsize = (dsiz - ABUFSIZE);
				/* data+dsiz points to new buffer block */
	data = (PHDR*) ((int*) data + dsiz);
	data->bfsize = size;
				/* old buffer links (next & prev) are ok */
	}

    else
	{			/* Use whole block, even if a bit bigger */
	pool.numfbufs--;		/* Count one less free buffer */
	next = (PHDR*) data->bfnext;
	prev = (PHDR*) data->bfprev;
	if (prev NE NULL)
	    prev->bfnext = (int*) next;		/* Link next buffer to prev */
	else
	    pool.freebuf = next;	/* link list back up */

	if (next NE NULL)
	    next->bfprev = (int*) prev;		/* Link prev buffer to next */
	}

    pool.freetot -= (data->bfsize + ABUFSIZE);	/* subtract size lost */
    data->bfnext = ptr;			/* set address of bufptr in buffer */
    *ptr = (int) &data->bfprev;		/* point bufptr at data portion */

#ifdef DEBUG4   /*************************************************************/
    chkaddr(ptr);
    chkaddr(data);
    chkaddr(ptr + (pool.high - pool.ptrtop));	/* ptr below ptrtop? */
    chkaddr((int*)data + (pool.low - pool.ptrtop));	/* buf >= ptrtop? */
#endif /* DEBUG4 *************************************************************/

    return ((char**)ptr);
}

    unsigned int
_f_pool (ptr)
    register int *ptr;

/* _f_pool -- Deallocate a pool buffer and bufptr
 *
 *	in:	ptr		Allocated bufptr to free, or NULL
 *	return:	(unsigned)	New size of free pool, in "sizeof" units
 *	thrown:	(NONE)
 *
 *	Frees the pool buffer referenced by the bufptr at 'ptr', returning
 *	the updated total free pool count, in "sizeof" units (bytes).
 *	If 'ptr' is NULL, returns the total free pool count.
 *
 *	The deallocation algorithm is:
 *		1) Free the bufptr, linking it into the freelist.
 *		2) If the buffer is the size of an i/o packet,
 *		   re-link it into the 'pre-allocated' packet list.
 *		3) Otherwise, call release() to release the buffer and
 *		   merge it with any surrounding free buffers.
 *
 *	Note that 'ptr' MUST be a valid bufptr, or NULL.
 */
{
    register PHDR *data;		/* address of data buffer */
    register unsigned i;

    if (ptr NE NULL)
	{
	data = (PHDR*) ((int*)(*ptr)-ABUFSIZE);	/* point to buffer header */

#ifdef DEBUG4   /*************************************************************/
    if (Intstate) error("f_pool at int state\n", NULL);
    if ( data->bfnext NE ptr )
	error("Ptr at %x points to corrupted pool buffer (_f_pool)\n", ptr);
    chkaddr(ptr);
    chkaddr(data);
    chkaddr(ptr + (pool.high - pool.ptrtop));		/* bufptr < ptrtop? */
    chkaddr((int*) data + (pool.low - pool.ptrtop));	/* buf >= ptrtop? */
#endif /* DEBUG4 *************************************************************/

	pool.numfptrs++;		/* count another free bufptr */
	pool.freetot += (data->bfsize + ABUFSIZE);	/* add in space */
	*ptr = (int) pool.freeptr;	/* link bufptr to front of freelist */
	pool.freeptr = ptr;		/* re-link free list header */

	if ( data->bfsize EQ PKTSIZE )
	    {
	    pool.numpkts++;	/* count another pre-allocated I/O packet */
	    data->bfnext = (int*) pool.pktlist;	/* link pkt to free list */
	    pool.pktlist = data;		/* re-link free list header */
	    }
	else
	    release (data);		/* release data buffer into pool */
	} /*if*/
    /* return total free space */
    return( (i=pool.freetot) ? ((i-ABUFSIZE) * UNITSIZE) : 0);
}

    static int
ext_ptrs ()

/* ext_ptrs () -- Extend bufptr space, if possible
 *
 *	return:		number of bufptrs added, or zero
 *	thrown:	(NONE)
 *
 *	Attempt to extend the bufptr space in system dynamic pool by
 *	the larger of (1/256 total pool) and (1/16 maximum bufptrs).
 *	Does not allow pool to be extended by the Hyper-Exec just to
 *	make room for a bufptr.  If extension is successful, returns
 *	the number of bufptrs added into the free-list.  Otherwise,
 *	returns zero (FALSE).
 */
{
    int extn;				/* buffer pointer extension size */
    int tmp1, tmp2;			/* temporary variables */
    register int *ptr;
    register int size;
    register int *ptop;

    ptop = pool.ptrtop;		/* pointer to first pool data addr */

    /* set bufptr extension size to the greater of
     *   (total pool/256) and (maxptrs/16), except that
     * it may not exceed maxptrs or available pool
     */
    tmp1 = ((pool.high-pool.low) >> 8) + 1;
    tmp2 = pool.maxptrs >> 4;
    tmp1 = MAX( tmp1,tmp2 );
    tmp2 = pool.maxptrs - (ptop - pool.low);
    if ( (extn = MIN( tmp1,tmp2 )) LE 0) return(0);

    /* If not enough pool, reduce extension size to what may be found */
    if ( (extn GT (tmp1 = pool.freetot-ABUFSIZE)) AND
		((extn=tmp1) LE 0) ) return(0);

    while (pool.freebuf NE (PHDR*)ptop)	/* loop until lowest pool is free */
	{				/* release packets until gone */
	if (morepool(PKTSIZE, DONT_COMPRESS) NE NULL) continue;
		/* move allocated pool up to make room for bufptrs */
	shuffle (ptop, widen_hole(pool.freebuf,extn));

#ifdef DEBUG3   /*************************************************************/
	if (pool.freebuf NE (PHDR*)ptop)
		error ("Ext_ptrs found lowest hole at %x\n", pool.freebuf);
#endif /* DEBUG3 *************************************************************/

	}

    if ( ((size = ((PHDR*)ptop)->bfsize) + ABUFSIZE - extn)  LE TOOSMALL )
	{
	pool.numfbufs--;		/* extend thru all of this hole */
	extn = size + ABUFSIZE;		/* include buffer management words */
	if ((pool.freebuf = (PHDR*) ((PHDR*)ptop)->bfnext) NE NULL)
		pool.freebuf->bfprev = NULL;	/* fix free ptr links */
	}
    else
	{
					/* point to where hole will be */
	pool.freebuf = (PHDR*) (ptr = (ptop + extn));
	((PHDR*)ptr)->bfprev = NULL;		/* link it to nowhere */

				/* link next (if any) prev-link to current */
	if ((((PHDR*)ptr)->bfnext = ((PHDR*)ptop)->bfnext) NE NULL)
		((PHDR*)(((PHDR*)ptr)->bfnext))->bfprev = ptr;
	((PHDR*)ptr)->bfsize = size-extn;	/* set new reduced freesize */
	}

    pool.freetot -= extn;		/* subtract this extension size */

    /* extn extra ptrs are now allocated at ptop ... initialize them */
    ptr = (int*) &pool.freeptr;
    while (*ptr NE NULL)  ptr=(int*)*ptr;	/* find bufptr freelist end */

    for (size=0; size<extn; size++)	/* link current to next, update ptr */
	ptr = (int*) (*ptr = (int) (ptop++));

    *ptr = NULL;			/* zero last link */
    pool.numfptrs += extn;		/* count the extras */
    pool.ptrtop = ptop;			/* set new ptrtop */
    if ( (size=pool.ptrtop-pool.low) > pool.maxptrs)  pool.maxptrs = size;
    return(extn);
}

    static PHDR *
widen_hole (hole, size)
    register PHDR *hole;
    unsigned size;

/* widen_hole (hole, size) -- Compress pool space at a particular hole
 *
 *	in:	hole		Ptr to hole to widen
 *	in:	size		Target size to make it
 *	return:	(PHDR *)	pointer to the widened hole
 *	thrown:	(NONE)
 *
 *	Widens a given free pool buffer (at 'hole) to be large enough to
 *	accomodate 'size' units (of UNITSIZE bytes).  Widen_hole() works
 *	by shuffling the allocations on either side of 'hole' until it
 *	is large enough.  The decision of which side of 'hole' to shuffle
 *	is made each time in order to shuffle the smallest amount of data
 *	at a given time.  Hopefully, this will occur infrequently enough
 *	and with enough fragmentation that multiple shuffles of the same
 *	data do not occur often nor take longer than a more sophisticated
 *	calculation of the cheapest set of shuffles needed to achieve the
 *	desired result.  The highest cost will usually be when the least
 *	total free pool is available.
 *
 *	There must be enough free pool available to perform the operation.
 *
 *	Actual widening operations are performed by shuffle().
 */
{
    int *bufabove;		/* ptr to next higher allocation */
    int *bufbelow;		/* ptr to previous allocation */
    register unsigned sizeabove;	/* size of higher block */
    register unsigned sizebelow;	/* size of previous block */

#ifdef DEBUG2   /*************************************************************/
    if ( (hole EQ NULL) OR  (hole NE ((hole->bfprev NE NULL) ?
				    (PHDR*) ((PHDR*)(hole->bfprev))->bfnext :
							pool.freebuf)) )
	error ("Bad hole linkage at widen_hole...hole address: %x\n", hole);
    if ( (size+50 < 50) OR ((pool.freetot - ABUFSIZE) LT size) )
	error("Size too big at widen_hole: %d.\n", size);
#endif /* DEBUG2 *************************************************************/

    while (hole->bfsize LT size)
	{
	sizeabove = ( (hole->bfnext EQ NULL) ? ~0 :
		(hole->bfnext -
			(bufabove = (int*)hole + hole->bfsize + ABUFSIZE)));

	sizebelow = ( (hole->bfprev EQ NULL) ? ~0 :
		((int*) hole -
			(bufbelow = hole->bfprev +
				((PHDR*)(hole->bfprev))->bfsize + ABUFSIZE)) );

	if (sizebelow LT sizeabove)
	    hole = shuffle(bufbelow, hole->bfprev);
	else
	    {
#ifdef DEBUG3   /*************************************************************/
	if (sizeabove EQ ~0) error("No holes to widen_hole at %x\n", hole);
#endif /* DEBUG3 *************************************************************/

	    hole = shuffle(bufabove, hole->bfnext);
	    }
	}  /*while*/
    return(hole);
}

    static PHDR *
shuffle (from,to)
    register int *from;
    register int *to;

/* shuffle -- Compress pool space
 *
 *	in:	from		Allocated buffer block to shuffle
 *	in:	to		Free buffer to move and relink
 *	return:	(PHDR *)	pointer to the new hole
 *	thrown:	(NONE)
 *
 *	Shuffle all contiguous allocated pool blocks starting at 'from'
 *	and continuing until the first hole or the end of pool to fill the
 *	space occupied by the free buffer at 'to'.  Update all the
 *	bufptrs of the affected pool blocks.  Data may be shuffled up
 *	or down, depending on the relative locations of 'from' and 'to'.
 *
 *	This routine uses ENA_INTS and DIS_INTS to ensure that no
 *	interrupt routines access any bufptrs that might not be accurate.
 */
{
    register int *ptr;
    int **tmpptr;
    int *newfree;		/* ptr to new hole location */
    int offset;
    int size;
    int *next;
    int *last;

#ifdef DEBUG1   /*************************************************************/
    errpri("\nShuffling from %x to ",from);
    errpri("%x\n",to);
#endif /* DEBUG1 *************************************************************/

#ifdef DEBUG2   /*************************************************************/
    if ( *(((PHDR*)from)->bfnext) NE (int)(from+ABUFSIZE))
	error ("Can't shuffle from %x -- poor allocated buf linkage\n", from);

    if (pool.numpkts NE 0)
	error ("Can't shuffle when numpkts = %d.\n", pool.numpkts);

    if ( to NE ((((PHDR*)to)->bfprev NE NULL) ?
				(((PHDR*)(((PHDR*)to)->bfprev))->bfnext) :
						(int*) pool.freebuf) )
	error ("Can't shuffle to %x -- poor free-buffer linkage\n", to);
#endif /* DEBUG2 *************************************************************/

    ptr = from;		/* start accumulating allocated buffers */
    offset = ((size = ((PHDR*)to)->bfsize) + ABUFSIZE) * (to>from ? 1 : -1);

    DIS_INTS;		/**** DISABLE INTERRUPTS ****/

    /* First, modify the bufptrs of all the buffers to be shuffled */

    while ( (ptr LT pool.high) AND
			((tmpptr = (int**) ((PHDR*)ptr)->bfnext) NE NULL) AND
					((int*) tmpptr LT pool.ptrtop) )
	{
	*tmpptr += offset;	/* set bufptr to where buffer will go */
	ptr += ((PHDR*)ptr)->bfsize + ABUFSIZE;	/* update dest ptr */
	}

    /* Next, link in what will be the new hole */
						/* find addr of new hole */
    newfree = to - ( (ptr - from) * sign(offset) );
						/* link into free list */
    if ((next = ((PHDR*)to)->bfnext) NE NULL)  ((PHDR*)next)->bfprev = newfree;
    if ((last = ((PHDR*)to)->bfprev) NE NULL)
	((PHDR*)last)->bfnext = newfree;
    else
	pool.freebuf = (PHDR*) newfree;

    /* Next, shuffle the data down or up */

    if (offset GT 0)	for (to += offset; ptr GT from; *--to = *--ptr);
    else		for (            ; from LT ptr; *to++ = *from++);

    ENA_INTS;		/**** ENABLE INTERRUPTS ****/

    ((PHDR*)newfree)->bfsize = size;	/* restore old free buffer values */
    ((PHDR*)newfree)->bfnext = next;
    ((PHDR*)newfree)->bfprev = last;
    pool.numcomps++;

#ifdef DEBUG1   /*************************************************************/
    errpri("After shuffle...new hole at %x\n", newfree);
#endif /* DEBUG1 *************************************************************/

    return(merge_pool(newfree));	/* merge shuffled hole */
}

    static PHDR *
morepool (target, flag)
    register unsigned target;
    char flag;

/* morepool (target, flag) -- Attempt to recover/compress pool space
 *
 *	in:	target		Target buffer size
 *	in:	flag		DONT_COMPRESS / DONT_EXTEND / DO_EXTEND
 *	return:	(PHDR *)	pointer to a big enough hole, or NULL
 *	thrown:	(NONE)
 *
 *	Attempt to assemble enough contiguous pool space to accomodate an
 *	allocation of at least 'target' units (of UNITSIZE).  If successful,
 *	return a pointer to the hole; otherwise, return NULL.
 *
 *	Pool compression is governed by 'flag' as follows:
 *		1) Free any "pre-allocated" i/o packets one at a time,
 *		   returning if the 'target' size is reached.
 *		2) If 'flag' == DONT_COMPRESS, quit at this point.
 *		3) If there is enough non-contiguous free space in pool to
 *		   satisfy 'target', find the largest free buffer and widen
 *		   it until it is big enough  (see widen_hole()).
 *		4) If 'flag' == DONT_EXTEND, quit at this point.
 *		5) Otherwise, request a pool extension from the Hyper_Exec.
 *
 *		*** POOL EXTENSION NOT YET IMPLEMENTED ***
 */
{
    register PHDR *ptr;
    register PHDR *biggest;	/* ptr to biggest hole */

    while ( (ptr=pool.pktlist) NE NULL)
	{
	pool.numpkts--;
	pool.pktlist = (PHDR*) ptr->bfnext;

	/* 1) deallocate one I/O packet
	 * 2) point to the merged, free buffer
	 * 3) get the size out of it
	 * 4) return it if it's big enough
	 */
	if ( (ptr = release(ptr))->bfsize GE target)
	    return(ptr);
	}

    if (flag EQ DONT_COMPRESS) return(NULL);

    /* If compressing won't be enough and extending is out, don't bother */
    if ( (target + ABUFSIZE) GT pool.freetot )
	{
	if (flag EQ DONT_EXTEND) return(NULL);
	return(NULL);	/* DUMMY extension routine */
	}

    /* Pool compression: find biggest hole and widen it */
    ptr = biggest = pool.freebuf;
    while (ptr NE NULL)
	{
	if (ptr->bfsize GE target) return (ptr);
	if (ptr->bfsize GT biggest->bfsize) biggest=ptr;
	ptr = (PHDR*) ptr->bfnext;
	}
    return(widen_hole(biggest,target));
}

    static PHDR *
release (buf)
    register PHDR *buf;

/* release (buf) -- Release and merge a buffer into pool
 *
 *	in:	buf		Address of buffer to release
 *	return:	(PHDR *)	Ptr to the new hole
 *	thrown:	(NONE)
 *
 *	Release the buffer at 'buf' into the free dynamic pool, linking
 *	it with the free buffers around it.  Then call merge_pool() to
 *	merge it with the free buffers on either side, if they are contiguous.
 *	Returns a pointer to the new free buffer (used, for instance, by
 *	morepool() to see if an i/o packet release creates a big enough hole).
 *
 *	The free buffer list is a doubly-linked list of free buffers, sorted
 *	by increasing address.
 */
{
    register PHDR *ptr;
    register PHDR *lastptr;

    pool.numfbufs++;				/* assume this makes a hole */

    if ( (ptr = pool.freebuf) EQ NULL)		/* if no other holes... */
	{
	buf->bfnext = buf->bfprev = NULL;		/* clear links */
	return(pool.freebuf = buf);		/* return ptr to buffer */
	}

    lastptr = NULL;
    do  {			/* search for correct spot in linked list */
	if (ptr > buf) break;
	}  while ( (ptr = (PHDR*) (lastptr = ptr)->bfnext) NE NULL);
				/* ptr =     NULL or new next buffer */
				/* lastptr = NULL or new previous buffer */

    /* link current to next and, if there is one, link it to current */
    if ( (buf->bfnext = (int*) ptr) NE NULL)  ptr->bfprev = (int*) buf;

    /* link current to previous and, if there is one, link it to current */
    if ( (buf->bfprev = (int*) lastptr) NE NULL)
	lastptr->bfnext = (int*) buf;
    else
	pool.freebuf = buf;	/* if no previous, set list head ptr */

    return(merge_pool(buf));	/* merge freed buffer into any around it */
}

    static PHDR *
merge_pool (buf)
    register PHDR *buf;

/* merge_pool (buf) -- Merge a free buffer into adjacent pool buffers
 *
 *	in:	buf		Address of free buffer
 *	return:	(PHDR *)	Pointer to the merged hole
 *	thrown:	(NONE)
 *
 *	Merge the free buffer at 'buf' with the adjacent free buffers,
 *	if they are contiguous in memory.  'Buf' should already be linked
 *	into the free list before merge_pool() is called, in order that
 *	it may locate the adjacent buffers quickly.  Returns a pointer
 *	to the resultant free buffer.
 *
 *	The routine mrg_buf() does the actual buffer merging.
 */
{
    register PHDR *ptr;		/* ptr to next free buffer */
    register PHDR *lastptr;	/* ptr to prev free buffer */

    ptr = (PHDR*) buf->bfnext;
    lastptr = (PHDR*) buf->bfprev;

    if ( ((int*) &buf->bfprev + buf->bfsize) EQ (int*) ptr )
	mrg_buf (buf, ptr);		/* merge current and next */

    if (lastptr NE NULL)
	if ( ((int*) &lastptr->bfprev + lastptr->bfsize) EQ (int*) buf )
	    {
	    mrg_buf (lastptr, buf);	/* merge previous and current */
	    buf = lastptr;		/* and update current ptr */
	    }

    return (buf);		/* return ptr to merged buffer */
}

    static
mrg_buf (lowb, highb)
    register PHDR *lowb;
    register PHDR *highb;

/* mrg_buf (lowb, highb) -- Merge two adjacent pool buffers
 *
 *	in:	lowb		address of lower buffer
 *	in:	highb		address of adjacent higher buffer
 *	return:	(NONE)
 *	thrown:	(NONE)
 *
 *	Merge together to free pool buffers that are:
 *		1) Known to be adjacent.
 *		2) Already linked into the free buffer list.
 */
{
    register PHDR *next;		/* addr of successor to highb */

	/* This code assumes that lowb and highb are already correctly */
	/*   linked into the pool free buffer list  */

    pool.numfbufs--;		/* one less hole now */

    lowb->bfsize += highb->bfsize + ABUFSIZE;	/* update data size */

    if ( (next = (PHDR*) (lowb->bfnext = highb->bfnext)) NE NULL)
	next->bfprev = (int*) lowb;		/* link high's successor */
}

    BOOLEAN
chk_pool (bptr)
    register int **bptr;

/* chk_pool (bptr) -- Verify that a bufptr/buffer combination is in pool
 *
 *	in:	bptr		Address of bufptr to test
 *	return: (BOOLEAN)	returns TRUE if valid bufptr / FALSE if not
 *	thrown:	(NONE)
 *
 *	Check if 'bptr' is a valid allocated pool bufptr.  Criteria are:
 *		1) 'Bptr' is in the bufptr address space.
 *		2) '*Bptr' is in the dynamic pool address space.
 *
 *	An additional criterion exists, but is not checked, since its
 *	falsehood would consititute a corruption of the pool structure:
 *		3) The pool buffer at '*bptr' points back to 'bptr'.
 */
{
    if ( (pool.low LE (int*) bptr) AND ((int*) bptr LT pool.ptrtop) AND
	    (pool.ptrtop LE *bptr) AND (*bptr LT pool.high) )
	return(TRUE);
    else
	return(FALSE);	/* invalid bufptr */
}

#ifdef DEBUG_MAP   /***********************************************************/


#define MARK(addr,char)  mark(map,addr,char)


_map_pool (map, msize)
    register char map[];
    unsigned msize;

/* _map_pool (map, msize) -- Construct bytemap of pool structure
 *
 *	mod:	map		array of chars...one per int of pool
 *	in:	msize		size of map...to make sure it's big enough
 *	return:	(NONE)
 *	thrown:	(NONE)
 *
 *	1) Initialize the bytemap at 'map' to all ASCII question marks (?).
 *	2) Mark all free bufptrs with an up-arrow (^).
 *	3) Mark all allocated bufptrs with an ampersand (@).
 *	4) Mark all "pre-allocated" i/o packets with:  "io...."
 *	5) Mark all free pool buffers with:  "fr...."
 *
 *	See also _map_add() and mark().
 */
{
    register int *ptr, *optr;
    register unsigned cnt;
    unsigned i, j, ctr, total;

    cnt = pool.high-pool.low;	/* keep count of all slots marked */
    if (msize < cnt) error("*Fatal* Bitmap array requires %d. chars\n", cnt);

    for (i=0; i<cnt; i++)  map[i] = '?';	/* init bitmap */

    cnt = pool.numfptrs;
    total = ctr = 0;
    errpri("...marking %d. buffer pointers...\n", cnt);
    ptr = (int*) &pool.freeptr;
    while ( (ptr = (int*) *ptr) NE NULL)
	{
	errpri("%d.\r", ++ctr);
	chkaddr(ptr);
	cnt--;
	MARK(ptr, '^');
	}
    if (cnt NE 0) errpri("Bad remainder pointer count: %d.\n", cnt);

    cnt = pool.numpkts;
    ctr = 0;
    errpri("...marking %d. pre-allocated I/O packets...\n", cnt);
    ptr = (int*) &pool.pktlist;
    while ( (ptr = (int*) *ptr) NE NULL)
	{
	errpri("%d.\r", ++ctr);
	chkaddr(ptr);
	cnt--;
	total += ABUFSIZE + (j = ((PHDR*)ptr)->bfsize);
	MARK(ptr+ASIZE, 'i');
	if (j NE PKTSIZE) errpri("\nIncorrect packet size: %d.\n", j);
	MARK(ptr+FNEXT, 'o');
	ptr += ABUFSIZE;
	for (i=0; i < j; i++)  MARK(ptr+i, '.');
	ptr += (FNEXT - ABUFSIZE);
	}
    if (cnt NE 0) errpri("Bad remainder packet count: %d.\n", cnt);

    cnt = pool.numfbufs;
    ctr = 0;
    errpri("...marking %d. free pool buffers...\n", cnt);
    ptr = (int*) &pool.freebuf;
    optr = NULL;
    while ( (ptr = (int*) *ptr) NE NULL)
	{
	errpri("%d.\r", ++ctr);
	chkaddr(ptr);
	cnt--;
	total += ABUFSIZE + (j = ((PHDR*)ptr)->bfsize);
	MARK(ptr+FSIZE, 'f');
	MARK(ptr+FNEXT, 'r');
	MARK(ptr+FPREV, '.');
	if ( ((PHDR*)ptr)->bfprev NE optr )
	    errpri("\nBad previous buffer pointer: %x\n",((PHDR*)ptr)->bfprev);
	optr = ptr;
	ptr += BUFSIZE;
	for (i=0; i < j-1; i++)  MARK(ptr+i, '.');
	ptr += (FNEXT-BUFSIZE);
	}
    if (cnt NE 0) errpri("Bad remainder buffer count: %d.\n", cnt);
    errpri("      Total available pool: %d.\n", (total ? total-ABUFSIZE : 0));
    if (total NE pool.freetot)
	errpri("Bad pool.freetot value: %d.\n", pool.freetot-ABUFSIZE);
}


_map_add (map, ptr, mchar)
    register char map[];
    register int  **ptr;
    char mchar;

/* _map_add (map, ptr, mchar) -- Add allocated buffer info to pool bytemap
 *
 *	mod:	map		array of chars...one per int of pool
 *	in:	ptr		address of bufptr for allocated block
 *	in:	mchar		mark character
 *	return:	(NONE)
 *	thrown:	(NONE)
 *
 *	1) Mark the bufptr with an ampersand (@).
 *	2) Mark the allocated buffer with:  "ALxxxx"
 *		where "x" is the ASCII character 'mchar'.
 *
 *	See also mark().
 */
{
    register PHDR *data;
    unsigned i, j;

    if (ptr EQ NULL) return;	/* allow a NULL ptr to be passed */
    chkaddr(ptr);		/* verify that bufptr is in pool */
    MARK(ptr, '@');		/* mark the bufptr */
    data = (PHDR*) ((*ptr) - ABUFSIZE);	/* get ptr to data buffer */
    chkaddr(data);		/*    and check it */
    j = data->bfsize;		/* get size of buffer */
    MARK(&data->bfsize, 'A');	/* and mark header area */
    MARK(&data->bfnext, 'L');

    if ( data->bfnext NE (int*) ptr )
	errpri("\nAllocated buffer does not point to its bufptr: %x\n", *ptr);

    data = (PHDR*) &data->bfprev;
    for (i=0; i < j; i++)  MARK((int*)data+i, mchar);
}

    static
mark (map, addr, x)
    register char map[];
    int *addr;
    char x;

/* mark (map, addr, x) -- Mark pool address in bytemap with character
 *
 *	mod:	map		ASCII bytemap (array of chars)
 *	in:	addr		Pool address to mark
 *	in:	x		Mark character
 *	return:	(NONE)
 *	thrown:	(NONE)
 *
 *	Mark the byte in pool bytemap 'map' that corresponds with the
 *	pool address 'addr', with the ASCII character 'x'.
 *
 *	Error message printed and mark not performed if the location in 'map'
 *	is already marked (not "?"), indicating duplicate pool allocation.
 */
{
    unsigned mrk;		/* used to index map */

    chkaddr(addr);
    if (map[(mrk=(addr-pool.low))] NE '?' )
	errpri("\nDuplicate allocation at offset %d.\n", mrk);
    else map[mrk] = x;
}

#endif /* DEBUG_MAP ***********************************************************/

#ifdef DEBUG4 | DEBUG_MAP   /**************************************************/

    static
chkaddr (adr)
    int *adr;

/* chkaddr (adr) -- Check that address lies within the bounds of pool
 *
 *	in:	adr		Pool address to check
 *	return:	(NONE)
 *	thrown:	(NONE)
 *
 *	Crash the VIOS if 'adr' is not within the bounds of system pool.
 */
{
    if ( (adr LT pool.low) OR (adr GE pool.high) )
	error("\n*Fatal* Pool address %x out of bounds\n", adr);
}

#endif /* DEBUG4 | DEBUG_MAP *************************************************/

E 1
