//+++2004-08-31
//    Copyright (C) 2004  Mike Rieker, Beverly, MA USA
//
//    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; version 2 of the License.
//
//    This program is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//    GNU General Public License for more details.
//
//    You should have received a copy of the GNU General Public License
//    along with this program; if not, write to the Free Software
//    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//---2004-08-31

/************************************************************************/
/*									*/
/*  General heap memory allocation routines				*/
/*									*/
/*    The list is composed of an array of varying sized blocks, the 	*/
/*    size of which can be found in .size.  The size and state at the 	*/
/*    beginning of the block should match the size and state at the 	*/
/*    end of the block.							*/
/*									*/
/*    At the very beginning of the list is a block of type END and 	*/
/*    with .size = 1.  This is used to eliminate a special case when 	*/
/*    allocating or freeing the following block.  Since it is of type 	*/
/*    END, it will not merge with either a FREE or ALLOC block.		*/
/*									*/
/*    At the very end is a block of type END with .size 0.		*/
/*									*/
/*    The size includes the ends and the guards and is in units of 	*/
/*    sizeof (Block).							*/
/*									*/
/************************************************************************/

#define _OZ_KNL_MALLOC_C

#include "ozone.h"

#include "oz_knl_hw.h"
#include "oz_knl_malloc.h"
#include "oz_knl_printk.h"
#include "oz_knl_sdata.h"

#define PAGESIZE (1 << OZ_HW_L2PAGESIZE)

typedef enum { STATE_FREE, STATE_BIN, STATE_ALLOC, STATE_END } State;

typedef struct Block Block;
struct Block { OZ_Memsize size;		/* size of this subblock */
               State state;		/* state of the block */
               int physcontig;		/* it is from a phys contig alloc */
               uLong pad1;		/* pad to 16-byte boundary */
             };
#define L2BS 4				/* log2 (sizeof (Block)) */
					/* sizeof Block is the alignment, also */

#define NGUARD 2 /* 0, 1, 2 */	/* number of blocks to use in each guard band */
#define POISON 1 /* 0, 1, 2 */	/* 0: no poison; 1: poison but don't check; 2: poison and check */
#define FULLCHECK 0 /* 0, 1 */	/* full checking every step (very slow) */

#if FULLCHECK			/* if full checking, make sure poison is turned all the way on */
#undef POISON
#define POISON 2
#endif

						/* 1600 bytes because ethernet packets are a little over 1500 */
#define NBINS (1600 >> L2BS)			/* number of bins to have for lookaside list */
						/* bin[0]       = blocks of data size     1<<L2BS bytes */
						/* bin[1]       = blocks of data size     2<<L2BS bytes */
						/* bin[NBINS-1] = blocks of data size NBINS<<L2BS bytes */

struct OZ_Memlist { OZ_Memlist *next;		/* next in chain of areas */
                    Block *base;		/* base address of the memory area */
                    OZ_Memsize size;		/* total size of memory area (in blocks), including both ends */
                    Block *firstfree;		/* lowest addressed block known to be free (and not in a bin) */
					/* The rest of the elements are valid only on the first memlist of a chain of memlists */
                    uLong (*lock) (void *lockprm);
                    void (*unlk) (void *lockprm, uLong lk);
                    void *lockprm;
                    Block *pcbins[NBINS];	/* lookasides that are physically contiguous - atomic updates only */
                    Block *pfbins[NBINS];	/* lookasides that are physically fragmented - atomic updates only */
                  };

static Block *malloctry (OZ_Memlist *memlist, OZ_Memsize ms, int pc);
static void coalesce (OZ_Memlist *memlist);
static void release (OZ_Memsize size, Block *mp);
static void checkfirstfree (OZ_Memlist *memlist);
static void checkguards (Block *mpbeg);
static void storepoison (OZ_Memsize size, Block *mp);
static void checkpoison (OZ_Memsize size, Block *mp);

/************************************************************************/
/*									*/
/*  Free an area of memory of the given size				*/
/*									*/
/*    Input:								*/
/*									*/
/*	memlist = memory listhead or NULL to start			*/
/*	size    = size (in bytes) of memory to be freed			*/
/*	adrs    = address of memory to be freed				*/
/*	lock    = lock routine, eg, oz_hw_smplock_wait			*/
/*	unlk    = unlock routine, eg, oz_hw_smplock_clr			*/
/*	lockprm = parameter to pass to lock/unlk, eg, &oz_s_smplock_np	*/
/*									*/
/*    Output:								*/
/*									*/
/*	oz_freesiz = memlist modified					*/
/*									*/
/*    Note:								*/
/*									*/
/*	The caller should lock the lock before calling this routine 	*/
/*	and unlock it after it returns, so you don't have two threads 	*/
/*	modifying the 'memlist->next' list at the same time.		*/
/*									*/
/************************************************************************/

OZ_Memlist *oz_freesiz (OZ_Memlist *memlist, 
                        OZ_Memsize size, 
                        void *adrs, 
                        uLong (*lock) (void *lockprm), 
                        void (*unlk) (void *lockprm, uLong lk), 
                        void *lockprm)

{
  Block *mp;
  OZ_Memlist *newmemlist;
  OZ_Pointer ptr, ptr0;

#if FULLCHECK
  if (memlist != NULL) oz_mlvalid (memlist);
#endif

  if (size < sizeof *memlist + (4 + 2*NGUARD) * sizeof (Block)) return (memlist);

  newmemlist = adrs;				/* point to and clear memlist */
  memset (newmemlist, 0, sizeof *newmemlist);

  ptr0 = (OZ_Pointer)adrs;			/* point to where we started */
  ptr  = (OZ_Pointer)adrs;
  ptr += sizeof *newmemlist;			/* increment past the memlist header */
  ptr  = ((ptr + sizeof *mp - 1) / sizeof *mp) * sizeof *mp; /* round up to 'rounding' boundary */

  size = (ptr0 + size - ptr) / sizeof *mp;	/* determine size left, in (Block) units */
  mp   = (Block *)ptr;				/* point to the memory block array of 'size' elements */

  newmemlist -> base = mp;			/* save base address of everything */
  newmemlist -> size = size;			/* save size of everything, including both ends */
  newmemlist -> firstfree = mp + 1;		/* first free one will be here */

#if POISON
  storepoison (size, mp);
#endif

  mp[0].size  = 1;				/* set up an 'end' marker */
  mp[0].state = STATE_END;
  mp[1].size  = size - 2;			/* whole size less 2 for the end markers */
  mp[1].state = STATE_FREE;			/* set the big chunk state to FREE */
  mp[size-2].size  = size - 2;			/* set up the same thing at the end */
  mp[size-2].state = STATE_FREE;
  mp[size-1].size  = 0;				/* set up an end tag with size zero */
  mp[size-1].state = STATE_END;			/* and a special state */

#if FULLCHECK
  checkfirstfree (newmemlist);
#endif

  if (memlist == NULL) {			/* if it's the first, ... */
    newmemlist -> lock    = lock;		/* ... save lock/unlock routine stuff */
    newmemlist -> unlk    = unlk;
    newmemlist -> lockprm = lockprm;
#if FULLCHECK
    oz_mlvalid (newmemlist);
#endif
    return (newmemlist);			/* ... and return its pointer */
  }

  newmemlist -> next = memlist -> next;		/* link to keep the first one first */
  memlist -> next = newmemlist;			/* ... becuase it has all the bins in it */
#if FULLCHECK
  oz_mlvalid (memlist);
#endif
  return (memlist);				/* ... the order of the rest don't matter */
}

/************************************************************************/
/*									*/
/*  Allocate memory							*/
/*									*/
/*    Input:								*/
/*									*/
/*	memlist = free memory listhead					*/
/*	size    = number of bytes wanted				*/
/*	pc      = 0 : normal allocation					*/
/*	          1 : physically contiguous (ie, can't cross a page boundary)
/*									*/
/*    Output:								*/
/*									*/
/*	oz_malloc = NULL : no memory available				*/
/*	            else : pointer to memory block			*/
/*	*size_r = caller usable bytes actually allocated		*/
/*									*/
/************************************************************************/

void *oz_malloc (OZ_Memlist *memlist, OZ_Memsize size, OZ_Memsize *size_r, int pc)

{
  Block *volatile *binhd, *mp;
  uLong lk;
  OZ_Memsize ms;

  if (memlist == NULL) return (NULL);

#if FULLCHECK
  oz_mlvalid (memlist);
#endif

  /* Convert size to Block size */

  ms = (size + sizeof *mp - 1) / sizeof *mp;
  if (ms == 0) return (NULL);

  /* Maybe it can be found in a lookaside bin.  Only use atomic updates so we don't have to be locked for this stuff. */

  if (ms <= NBINS) {
    mp = NULL;								/* assume it is a physically contig malloc */
    if (!pc) {								/* see if physically contig malloc */
      binhd = memlist -> pfbins + ms - 1;				/* it isn't, try to get from fragmented list */
      do mp = *binhd;
      while ((mp != NULL) && !oz_hw_atomic_setif_ptr ((void *volatile *)binhd, *(Block **)(mp + 1), mp));
    }
    if (mp == NULL) {							/* see if phy contig or frag list was empty */
      binhd = memlist -> pcbins + ms - 1;				/* if so, try to get from contiguous list */
      do mp = *binhd;
      while ((mp != NULL) && !oz_hw_atomic_setif_ptr ((void *volatile *)binhd, *(Block **)(mp + 1), mp));
    }
    if (mp != NULL) {							/* see if we found a binned block */
#if NGUARD > 0
      storepoison (1, mp + 1);						/* if so, poison the first guard (it had the link in it) */
#endif
      mp[0].state = STATE_ALLOC;					/* change its state to 'allocated' */
      mp[ms+2*NGUARD+1].state = STATE_ALLOC;
      goto rtn;								/* return it to caller */
    }
  }

  /* Try to allocate from general population */

  lk = (*(memlist -> lock)) (memlist -> lockprm);			/* this requires external lock */
  mp = malloctry (memlist, ms, pc);					/* try to allocate */
  if (mp == NULL) {
    coalesce (memlist);							/* failed, free everything in bins to general population */
    mp = malloctry (memlist, ms, pc);					/* try to allocate again */
  }
  (*(memlist -> unlk)) (memlist -> lockprm, lk);			/* unlock */
  if (mp == NULL) return (NULL);
  mp -> physcontig = pc;						/* save whether it was a phys contig allocation request */

  /* Return pointer to data area */

#if (POISON == 0) && (NGUARD > 0)
  storepoison (NGUARD, mp + 1);						/* store poison in the guards */
  storepoison (NGUARD, mp + mp -> size - 1 - NGUARD);
#endif

rtn:
#if FULLCHECK
  oz_mlvalid (memlist);
#endif
  if (size_r != NULL) *size_r = (mp -> size - 2 - 2*NGUARD) * sizeof *mp; /* return number of usable bytes to caller */
  return (mp + 1 + NGUARD);						/* return pointer to data area of allocated block */
}

/* Same as oz_malloc, except caller already has memory list locked */

void *oz_malloc_lk (OZ_Memlist *memlist, OZ_Memsize size, OZ_Memsize *size_r, int pc)

{
  Block *volatile *binhd, *mp;
  OZ_Memsize ms;

  if (memlist == NULL) return (NULL);

#if FULLCHECK
  oz_mlvalid (memlist);
#endif

  /* Convert size to Block size */

  ms = (size + sizeof *mp - 1) / sizeof *mp;
  if (ms == 0) return (NULL);

  /* Maybe it can be found in a lookaside bin.  Only use atomic updates so we don't have to be locked for this stuff. */

  if (ms <= NBINS) {
    mp = NULL;								/* assume it is a physically contig malloc */
    if (!pc) {								/* see if physically contig malloc */
      binhd = memlist -> pfbins + ms - 1;				/* it isn't, try to get from fragmented list */
      do mp = *binhd;
      while ((mp != NULL) && !oz_hw_atomic_setif_ptr ((void *volatile *)binhd, *(Block **)(mp + 1), mp));
    }
    if (mp == NULL) {							/* see if phy contig or frag list was empty */
      binhd = memlist -> pcbins + ms - 1;				/* if so, try to get from contiguous list */
      do mp = *binhd;
      while ((mp != NULL) && !oz_hw_atomic_setif_ptr ((void *volatile *)binhd, *(Block **)(mp + 1), mp));
    }
    if (mp != NULL) {							/* see if we found a binned block */
#if NGUARD > 0
      storepoison (1, mp + 1);						/* if so, poison the first guard (it had the link in it) */
#endif
      mp[0].state = STATE_ALLOC;					/* change its state to 'allocated' */
      mp[ms+2*NGUARD+1].state = STATE_ALLOC;
      goto rtn;								/* return it to caller */
    }
  }

  /* Try to allocate from general population */

  mp = malloctry (memlist, ms, pc);					/* try to allocate */
  if (mp == NULL) {
    coalesce (memlist);							/* failed, free everything in bins to general population */
    mp = malloctry (memlist, ms, pc);					/* try to allocate again */
  }
  if (mp == NULL) return (NULL);
  mp -> physcontig = pc;						/* save whether it was a phys contig allocation request */

  /* Return pointer to data area */

#if (POISON == 0) && (NGUARD > 0)
  storepoison (NGUARD, mp + 1);						/* store poison in the guards */
  storepoison (NGUARD, mp + mp -> size - 1 - NGUARD);
#endif

rtn:
#if FULLCHECK
  oz_mlvalid (memlist);
#endif
  if (size_r != NULL) *size_r = (mp -> size - 2 - 2*NGUARD) * sizeof *mp; /* return number of usable bytes to caller */
  return (mp + 1 + NGUARD);						/* return pointer to data area of allocated block */
}

/* Try to malloc the block from the general population */

static Block *malloctry (OZ_Memlist *memlist, OZ_Memsize ms, int pc)

{
  Block *mp, *mpbeg, *mpend;
  OZ_Memlist *mlbest;
  OZ_Memsize bs, bytesize, roundup, size;
  OZ_Pointer byteaddr;

  size = ms * sizeof *mp;

  /* Add two for the overhead of the first and last boundary tags */
  /* Plus extra blocks for the guard bands at beginning and end   */

  ms += 2 + 2*NGUARD;

  if (pc) goto phycontig;

  /* Look for an element that will hold the requested size */

  mpbeg = NULL;								/* no 'best fit' found so far */
  do {
    mpend = NULL;							/* haven't found first free yet */
    for (mp = memlist -> firstfree; (bs = mp -> size) != 0; mp += bs) {	/* scan the list starting with lowest free block */
      if (mp -> state != STATE_FREE) continue;				/* skip if block is not free */
      if (mpend == NULL) mpend = mp;					/* save address of first free block in list */
      if (bs < ms) continue;						/* skip if block is too small */
      if (bs == ms) goto foundvar;					/* stop scanning if the exact size */
      if ((mpbeg == NULL) || (bs < mpbeg -> size)) { mpbeg = mp; mlbest = memlist; } /* save if it is the best fit so far */
    }
    if (mpend == NULL) mpend = mp;					/* if all memory is allocated, point first free at end */
    memlist -> firstfree = mpend;					/* save address of first free (or pointer to end of list) */
#if FULLCHECK
    checkfirstfree (memlist);
#endif
    memlist = memlist -> next;						/* try next list */
  } while (memlist != NULL);
  if (mpbeg == NULL) return (NULL);					/* if no best fit found, return failure status */
  mp = mpbeg;								/* ok, use the best fit */
  bs = mpbeg -> size;
  memlist = mlbest;
  goto foundvar_nosetff;
foundvar:
  if (mpend == NULL) mpend = mp;					/* if no free element found yet, start here next time */
  memlist -> firstfree = mpend;						/* update pointer to first free in list (or close to it) */
#if FULLCHECK
  checkfirstfree (memlist);
#endif
foundvar_nosetff:
  mpend = mp + bs - 1;							/* point to end of the whole thing */

  /* Before we give (part of) it away, make sure it is still poisoned */

  if (mpend -> state != STATE_FREE) {
    oz_crash ("oz_malloc: end state %d", mpend -> state);
  }
  if (mpend -> size != bs) {
    oz_crash ("oz_malloc: end size %u not %u", mpend -> size, bs);
  }
#if POISON > 1
  checkpoison (mp -> size - 2, mp + 1);
#endif

allocvar:

  /* If it takes the whole thing, change state and return pointer */

  if (bs <= ms + 4) mpend -> state = mp -> state = STATE_ALLOC;

  /* It only takes part of it, return the lowest addressed part */
  /* Use the lowest end because the pc alloc expects that       */

  else {
    mpbeg = mp + ms - 1;				/* point to end of part we alloc */

    mpbeg -> size  = mp -> size  = ms;			/* set up size of block we allocate */
    mpbeg -> state = mp -> state = STATE_ALLOC;		/* set its state to 'allocated' */

    mpend -> size  = mpbeg[1].size = mpend - mpbeg;	/* set up size of what's left over */
    mpbeg[1].state = STATE_FREE;			/* set its state to 'free' */
  }

  return (mp);

  /**********************************/
  /* Physically contiguous allocate */
  /**********************************/

phycontig:
  if (size > PAGESIZE) return (NULL);

  do {
    mpend = NULL;							/* haven't found first free yet */
    for (mp = memlist -> firstfree; (bs = mp -> size) != 0; mp += bs) {	/* scan the list starting with lowest known free block */
      if (mp -> state != STATE_FREE) continue;
      if (mpend == NULL) mpend = mp;					/* save address of first free memory block */
      if (bs < ms) continue;
      bytesize  = (bs - 2 - 2*NGUARD) * sizeof *mp;			/* size of data area in bytes */
      byteaddr  = (OZ_Pointer)(mp + 1 + NGUARD);			/* address of data area */
      roundup   = ((PAGESIZE - 1) & ~ byteaddr) + 1;			/* bytes to end of page */
      if (roundup >= size) goto foundvar;				/* if it fits before end of page, use it as is */
      if (roundup < (3 + NGUARD) * sizeof *mp) roundup = (3 + NGUARD) * sizeof *mp; /* must be enough room to split */
      if (bytesize <= roundup) continue;
      bytesize -= roundup;						/* move to beg of page */
      byteaddr += roundup;
      if (bytesize < size) continue;
      roundup = ((PAGESIZE - 1) & ~ byteaddr) + 1;			/* bytes to end of page */
      if (roundup >= size) goto pc_foundvar;				/* if still room, use it */
    }
    if (mpend == NULL) mpend = mp;					/* if all memory is allocated, point first free at end */
    memlist -> firstfree = mpend;					/* save address of first free (or pointer to end of list) */
#if FULLCHECK
    checkfirstfree (memlist);
#endif
    memlist = memlist -> next;						/* try next list */
  } while (memlist != NULL);
  return (NULL);

pc_foundvar:
  if (mpend == NULL) mpend = mp;					/* if no free element found yet, start here next time */
  memlist -> firstfree = mpend;						/* update pointer to first free in list (or close to it) */
#if FULLCHECK
  checkfirstfree (memlist);
#endif
  mpend = mp + bs - 1;							/* point to end of the whole thing */

  /* Before we give part of it away, make sure it is still poisoned */

  if (mpend -> state != STATE_FREE) {
    oz_crash ("oz_malloc: end state %d", mpend -> state);
  }
  if (mpend -> size != bs) {
    oz_crash ("oz_malloc: end size %u not %u", mpend -> size, bs);
  }
#if POISON > 1
  checkpoison (mp -> size - 2, mp + 1);
#endif

  /* Allocate memory such that we return 'byteaddr' as the user data pointer  */
  /* We know there is enough room between mp and byteaddr to make a new block */
  /* We also know byteaddr is 'mp' aligned                                    */

  if (byteaddr & (sizeof *mp - 1)) oz_crash ("oz_malloc: byteaddr %x not aligned", byteaddr);

  mpbeg  = (Block *)byteaddr;		/* point to beg of area to alloc */
  mpbeg -= 1 + NGUARD;

  if (mpbeg - mp < 2) oz_crash ("oz_malloc: not enough room to split");
  if (mpend + 1 < mpbeg + ms) oz_crash ("oz_malloc: not enough room left");

  mpbeg[-1].state = STATE_FREE;		/* free off little block before us */
  mp -> size = mpbeg[-1].size = mpbeg - mp;

  bs -= mpbeg - mp;			/* reduce what's left by that much */
  mp  = mpbeg;				/* point to what's left */
  mp -> state = STATE_FREE;		/* make it look nice for allocvar and validate call */
  mpend -> size = mp -> size = bs;

#if FULLCHECK
  oz_mlvalid (memlist);
#endif

  goto allocvar;			/* allocate from there */
}

/* Release everything in all bins to the general population, merging with neighbors as much as possible */

static void coalesce (OZ_Memlist *memlist)

{
  Block *mp;
  Block *volatile *bp;
  OZ_Memlist *ml;
  OZ_Memsize bs;

#if FULLCHECK
  oz_mlvalid (memlist);
#endif

  for (bp = memlist -> pfbins;; bp = memlist -> pcbins) {	/* do fragmented then contiguous lists */
    for (bs = 0; bs < NBINS; bs ++) {				/* do each blocksize within each list */
      while ((mp = *bp) != NULL) {				/* repeat as long as there are blocks in the list */
        if (oz_hw_atomic_setif_ptr ((void *volatile *)bp, *(Block **)(mp + 1), mp)) { /* try to unlink the binned block */
#if POISON
          storepoison (1, mp + 1);				/* fix that 1st guard to be all poison */
#endif
          release (bs + 3 + 2*NGUARD, mp);			/* release block to the general population */
        }
      }
      bp ++;							/* increment to next bin listhead */
    }
    if (bp == memlist -> pcbins + NBINS) break;			/* stop if we have done both sets of bins */
  }

  for (ml = memlist; ml != NULL; ml = ml -> next) {		/* reset all firstfree's */
    ml -> firstfree = ml -> base + 1;				/* point to first element in list as the first free */
#if FULLCHECK
    checkfirstfree (ml);
#endif
  }								/* it will get fixed when the allocate re-scans the list */

#if FULLCHECK
  oz_mlvalid (memlist);
#endif
}

/************************************************************************/
/*									*/
/*  Validate an area of memory previously allocated by oz_malloc	*/
/*									*/
/*    Input:								*/
/*									*/
/*	memlist = free memory listhead					*/
/*	adrs    = address of memory to be validated as returned by 	*/
/*	          oz_malloc						*/
/*									*/
/*    Output:								*/
/*									*/
/*	oz_valid = number of bytes that are allocated			*/
/*									*/
/************************************************************************/

OZ_Memsize oz_valid (OZ_Memlist *memlist, void *adrs)

{
  Block *mp;

  mp  = adrs;
  mp -= 1 + NGUARD;

  checkguards (mp);

#if FULLCHECK
  oz_mlvalid (memlist);
#endif

  /* Return size (same value that corresponding oz_malloc returned) */

  return ((mp -> size - 2 - 2*NGUARD) * sizeof *mp);
}

/************************************************************************/
/*									*/
/*  Free an area of memory previously allocated by oz_malloc		*/
/*									*/
/*    Input:								*/
/*									*/
/*	memlist = free memory listhead					*/
/*	adrs    = address of memory to be freed as returned by 		*/
/*	          oz_malloc						*/
/*									*/
/*    Output:								*/
/*									*/
/*	*memlist = updated to include the given memory			*/
/*	oz_free = number of bytes that were released			*/
/*									*/
/************************************************************************/

OZ_Memsize oz_free (OZ_Memlist *memlist, void *adrs)

{
  Block *mp, *mpend;
  Block *volatile *binhd;
  uLong lk;
  OZ_Memlist *ml;
  OZ_Memsize size;
  OZ_Pointer mp1, mp2;

  mp  = adrs;
  mp -= 1 + NGUARD;

  checkguards (mp);					/* poison should still be in guards */

#if FULLCHECK
  oz_mlvalid (memlist);
#endif

  size = mp -> size;					/* get inclusive size in Block units */

#if POISON
  storepoison (size - 2 - 2*NGUARD, mp + 1 + NGUARD);	/* poison the data area, leave size/state blocks alone */
							/* we know the guards are still poison from the 'checkguards' call */
#endif

  /* If it fits in a bin, just put it in the bin (physically contiguous or fragmented) */

  if (size <= NBINS + 2 + 2*NGUARD) {			/* see if it fits in a bin */
    mp[0].state = STATE_BIN;				/* change state to 'in bin' */
    mp[size-1].state = STATE_BIN;
    size -= 2 + 2*NGUARD;				/* get size of data portion */
    binhd = memlist -> pfbins + size - 1;		/* assume we will put block on fragmented list */
							/* (that way they all get used an equal amount) */
							/* (if caller subsequently does a pc malloc and there is no memory, */
							/*  a coalesce will be done which will reset the bins) */
    if (mp -> physcontig) {				/* see if it was a physically contiguous allocation */
      binhd = memlist -> pcbins + size - 1;		/* if so, assume it is contiguous */
    }
    do *(Block **)(mp + 1) = *binhd;			/* link block to bin's list */
    while (!oz_hw_atomic_setif_ptr ((void *volatile *)binhd, mp, *(Block **)(mp + 1)));
#if FULLCHECK
    oz_mlvalid (memlist);
#endif
    return (size * sizeof *mp);
  }

  /* Doesn't fit in a bin, release to the general population */

  lk = (*(memlist -> lock)) (memlist -> lockprm);
  release (size, mp);

  /* Maybe update the firstfree to include the freed block */

  for (ml = memlist;; ml = ml -> next) if ((mp > ml -> base) && (mp < ml -> base + ml -> size)) break;
  if (ml -> firstfree > mp) ml -> firstfree = mp;
#if FULLCHECK
  checkfirstfree (ml);
#endif
  (*(memlist -> unlk)) (memlist -> lockprm, lk);

#if FULLCHECK
  oz_mlvalid (memlist);
#endif

  /* Return size freed off (same value that corresponding oz_malloc returned) */

  return ((size - 2 - 2*NGUARD) * sizeof *mp);
}

/* Release a block of memory (allocated or binned) to the general population.  Merge with neighbors where possible. */

static void release (OZ_Memsize size, Block *mp)

{
  Block *mpend;

  mpend = mp + size - 1;				/* point to end (inclusize) */

#if POISON
  storepoison (1, mp);					/* poison the headers */
  storepoison (1, mpend);
#endif

  if (mp[-1].state == STATE_FREE) {			/* if one before is free, back up to include it */
    size = mp[-1].size;
#if POISON
    storepoison (1, mp - 1);
#endif
    mp -= size;
  }
  if (mpend[1].state == STATE_FREE) {			/* if one after is free, advance to include it */
    size = mpend[1].size;
#if POISON
    storepoison (1, mpend + 1);
#endif
    mpend += size;
  }

  mpend -> size  = mp -> size  = mpend + 1 - mp;	/* set up new headers */
  mpend -> state = mp -> state = STATE_FREE;
}

/************************************************************************/
/*									*/
/*  Validate an entire memory list					*/
/*									*/
/************************************************************************/

void oz_mlvalid (OZ_Memlist *memlist)

{
  Block **bp, *mpbeg, *mpend;
  int foundfirstfree;
  uLong lk;
  OZ_Memlist *ml;
  OZ_Memsize nbinned, bs;

  lk = (*(memlist -> lock)) (memlist -> lockprm);

  nbinned = 0;
  for (ml = memlist; ml != NULL; ml = ml -> next) {

    /* Scan the list from beginning to end */

    foundfirstfree = 0;
    for (mpbeg = ml -> base; (bs = mpbeg -> size) != 0; mpbeg = mpend + 1) {

      if (bs >= ml -> size) oz_crash ("oz_mlvalid: block size %u bigger than list size %u", bs, ml -> size);

      /* Maybe we have found the first free block */

      if (mpbeg == ml -> firstfree) foundfirstfree = 1;

      /* Point to end of block (inclusive) */

      mpend = mpbeg + bs - 1;

      /* The states and sizes for both ends of block should match */

      if (mpend -> state != mpbeg -> state) {
        oz_crash ("oz_mlvalid: %p beg state %d, %p end state %d", mpbeg, mpbeg -> state, mpend, mpend -> state);
      }
      if (mpend -> size != bs) {
        oz_crash ("oz_mlvalid: %p beg size %u, %p end size %u", mpbeg, bs, mpend, mpend -> size);
      }

      /* Do other checking based on state */

      switch (mpbeg -> state) {

        /* Free's should have everything in the middle poison */

        case STATE_FREE: {
#if POISON
          checkpoison (bs - 2, mpbeg + 1);
#endif
          break;
        }

        /* Allocated should have good guards */

        case STATE_ALLOC: {
          checkguards (mpbeg);
          break;
        }

        /* Binned should have poison everywhere except the first pointer worth of the first guard */

        case STATE_BIN: {
#if POISON
          checkpoison (bs - 3, mpbeg + 2);
#endif
          nbinned ++;
          break;
        }

        /* This should only show up at the beginning and have size 1 */

        case STATE_END: {
          if (bs != 1) {
            oz_crash ("oz_mlvalid: beginning marker size %u", bs);
          }
          if (mpbeg != ml -> base) {
            oz_crash ("oz_mlvalid: beginning marker at %p", mpbeg);
          }
          break;
        }

        /* Don't know what this is */

        default: {
          oz_crash ("oz_mlvalid: unknown state %d", mpbeg -> state);
        }
      }
    }

    /* The last one should be a state END and should be at the end of the memory area */

    if (mpbeg -> state != STATE_END) oz_crash ("oz_mlvalid: size 0 block state %d", mpbeg -> state);
    if (mpbeg != ml -> base + ml -> size - 1) oz_crash ("oz_mlvalid: end %p not at %p", mpbeg, ml -> base + ml -> size - 1);

    /* Make sure we found the first free block in there somewhere */

    if (!foundfirstfree && (ml -> firstfree != mpbeg)) {
      oz_crash ("oz_mlvalid: didn't find firstfree %p, base %p, end %p", ml -> firstfree, ml -> base, mpbeg);
    }
  }

  /* Make sure all the blocks marked as 'binned' are actually in a bin */

  for (bp = memlist -> pfbins;; bp = memlist -> pcbins) {
    for (bs = 1; bs <= NBINS; bs ++) {
      for (mpbeg = bp[bs-1]; mpbeg != NULL; mpbeg = *(Block **)(mpbeg + 1)) {
        mpend = mpbeg + bs + 2 + 2*NGUARD - 1;
        if (mpbeg -> state != STATE_BIN) oz_crash ("oz_mlvalid: block on bin list %u has beg state %d", bs, mpbeg -> state);
        if (mpend -> state != STATE_BIN) oz_crash ("oz_mlvalid: block on bin list %u has end state %d", bs, mpend -> state);
        if (mpbeg -> size  != bs + 2 + 2*NGUARD) oz_crash ("oz_mlvalid: block on bin list %u has beg size %u", bs, mpbeg -> size);
        if (mpend -> size  != bs + 2 + 2*NGUARD) oz_crash ("oz_mlvalid: block on bin list %u has beg size %u", bs, mpend -> size);
        if (nbinned == 0) oz_crash ("oz_mlvalid: loop in bin list %u", bs);
        nbinned --;
      }
    }
    if (bp == memlist -> pcbins) break;
  }
  if (nbinned != 0) oz_crash ("oz_mlvalid: couldn't find %u binned blocks", nbinned);

  (*(memlist -> unlk)) (memlist -> lockprm, lk);
}

static void checkfirstfree (OZ_Memlist *memlist)

{
  Block *mp;
  OZ_Memsize bs;

  for (mp = memlist -> base; (bs = mp -> size) != 0; mp += bs) if (memlist -> firstfree == mp) return;
  if (memlist -> firstfree != mp) {
    oz_crash ("oz_knl_malloc checkfirstfree: cant find firstfree %p in %p end %p", memlist -> firstfree, memlist -> base, memlist -> base + memlist -> size);
  }
}

/************************************************************************/
/*									*/
/*  Check the guards on an allocated block of memory			*/
/*									*/
/************************************************************************/

static void checkguards (Block *mpbeg)

{
  Block *mpend;

  mpend = mpbeg + mpbeg -> size - 1;
  if (mpbeg -> state != STATE_ALLOC) {
    oz_crash ("oz_mlvalid: mpbeg state %d found in alloc sub-block", mpbeg -> state);
  }
  if (mpend -> state != STATE_ALLOC) {
    oz_crash ("oz_mlvalid: mpend state %d found in alloc sub-block", mpend -> state);
  }
  if (mpend -> size != mpbeg -> size) {
    oz_crash ("oz_mlvalid: alloc mpbeg size %u ne mpend size %u", mpbeg -> size, mpend -> size);
  }

  checkpoison (NGUARD, mpbeg + 1);
  checkpoison (NGUARD, mpend - NGUARD);
}

/************************************************************************/
/*									*/
/*  Store poison pattern in memory block				*/
/*									*/
/************************************************************************/

static void storepoison (OZ_Memsize size, Block *mp)

{
#ifdef __386__
  asm ("cld ; rep ; stosl" : : "a" (0xDEADBEEF), "c" (size * sizeof *mp / sizeof (uLong)), "D" (mp) : "memory");
#else
  uLong *lp;
  OZ_Memsize i;

  lp = (uLong *)mp;
  for (i = size * sizeof *mp / sizeof (uLong); i > 0; -- i) {
    *(lp ++) = 0xDEADBEEF;
  }
#endif
}

/************************************************************************/
/*									*/
/*  Make sure a block is still poisoned					*/
/*									*/
/************************************************************************/

static void checkpoison (OZ_Memsize size, Block *mp)

{
#ifdef __386__
  uByte bad;
  uLong *lp;

  asm ("cld ; repe ; scasl ; setne %0" : "=g" (bad), "=D" (lp)  : "a" (0xDEADBEEF), "c" (size * sizeof *mp / sizeof (uLong)), "D" (mp) : "memory");
  if (bad) oz_crash ("oz_malloc checkpoison: poison missing at %p", -- lp);
#else
  uLong *lp;
  OZ_Memsize i;

  lp = (uLong *)mp;
  for (i = size * sizeof *mp / sizeof (uLong); i > 0; -- i) {
    if (*(lp ++) != 0xDEADBEEF) {
      oz_crash ("oz_malloc checkpoison: poison missing at %p", -- lp);
    }
  }
#endif
}