/*************************************************************************/
/*                                                                       */
/*  Copyright (c) 1994 Stanford University                               */
/*                                                                       */
/*  All rights reserved.                                                 */
/*                                                                       */
/*  Permission is given to use, copy, and modify this software for any   */
/*  non-commercial purpose as long as this copyright notice is not       */
/*  removed.  All other uses, including redistribution in whole or in    */
/*  part, are forbidden without prior written permission.                */
/*                                                                       */
/*  This software is provided with absolutely no warranty and no         */
/*  support.                                                             */
/*                                                                       */
/*************************************************************************/

/* this version guarentees that all blocks are zeroed, and it expects
   that all returned blocks are zero */

EXTERN_ENV

#include "matrix.h"

#define ALIGN 8
#define MAXFAST 16
#define MAXFASTBL (1<<(MAXFAST-1))

#define SIZE(block) (block[-1]) /* in all blocks */
#define HOME(block) (block[-2]) /* in all blocks */
#define NEXTFREE(block) (*((unsigned **) block)) /* in free blocks */

struct MemPool {
	LOCKDEC(memoryLock)
	unsigned *volatile*freeBlock;
	int tally, touched, maxm;
	} *mem_pool;

int mallocP = 1, machineP = 1;

extern struct GlobalMemory *Global;


MallocInit(P)
{
  int p;
  
  mallocP = P;

  mem_pool = (struct MemPool *)
    G_MALLOC((mallocP+1)*sizeof(struct MemPool), 0);
  mem_pool++;
  /****** access to mem_pool[-1] is valid ******/

  for (p = -1; p<mallocP; p++)
    InitOneFreeList(p);
}


InitOneFreeList(p)
{
  int j;

  LOCKINIT(mem_pool[p].memoryLock);
  if (p > 0) {
    mem_pool[p].freeBlock = (unsigned **)
      G_MALLOC((MAXFAST+1)*sizeof(unsigned *), p);
    MigrateMem(mem_pool[p].freeBlock, (MAXFAST+1)*sizeof(unsigned *), p);
  }
  else {
    mem_pool[p].freeBlock = (unsigned **)
      G_MALLOC((MAXFAST+1)*sizeof(unsigned *), 0);
    MigrateMem(mem_pool[p].freeBlock, (MAXFAST+1)*sizeof(unsigned *),
	       DISTRIBUTED);
  }
  for (j=0; j<=MAXFAST; j++)
    mem_pool[p].freeBlock[j] = NULL;
  mem_pool[p].tally = mem_pool[p].maxm = mem_pool[p].touched = 0;
}


MallocStats()
{
  int i;

  printf("Malloc max: ");
  for (i=0; i<mallocP; i++)
    if (mem_pool[i].touched > 0)
      printf("%d* ", mem_pool[i].maxm);
    else
      printf("%d ", mem_pool[i].maxm);
  printf("\n");

}


/* returns first bucket where 2^bucket >= size */

FindBucket(size)
{
  int bucket;

  if (size > MAXFASTBL)
    bucket = MAXFAST;
  else {
    bucket = 1;
    while (1<<bucket < size)
      bucket++;
  }

  return(bucket);
}


/* size is in bytes */

char *MyMalloc(size, home)
int size, home;
{
  int i, bucket, leftover, alloc_size;
  unsigned *d, *result, *prev, *freespace, *freelast;
  unsigned int block_size;
  extern int MyNum;

  if (size < ALIGN)
    size = ALIGN;

  if (home == DISTRIBUTED)
    home = -1;

  bucket = FindBucket(size);

  if (bucket < MAXFAST)
    alloc_size = 1<<bucket;
  else
    alloc_size = ((size+ALIGN-1)/ALIGN)*ALIGN;

  result = NULL;

  if (bucket < MAXFAST) {
    if (mem_pool[home].freeBlock[bucket]) {
      LOCK(mem_pool[home].memoryLock)
      result = mem_pool[home].freeBlock[bucket];
      if (result)
	mem_pool[home].freeBlock[bucket] = NEXTFREE(result);
      UNLOCK(mem_pool[home].memoryLock)
    }
  }

  if (!result) {
    LOCK(mem_pool[home].memoryLock)
    prev = NULL;
    d = mem_pool[home].freeBlock[MAXFAST];
    while (d) {

      block_size = SIZE(d);

      if (block_size >= alloc_size) {  /* Found one! */

	leftover = block_size - alloc_size - 2*sizeof(unsigned);
        result = d + (leftover/sizeof(unsigned)) + 2;
	SIZE(result) = alloc_size;
	HOME(result) = home;

	if (leftover > MAXFASTBL) {
	  SIZE(d) = leftover;
	}
	else {
	  /* don't leave a block */

	  /* unlink 'd' */
	  if (prev)
	    NEXTFREE(prev) = NEXTFREE(d);
	  else
	    mem_pool[home].freeBlock[MAXFAST] = NEXTFREE(d);

	  if (leftover > 0) {
	    SIZE(d) = leftover;
	    MyFreeNow(d);
	  }
	}
        break;
      }

      prev = d;
      d = NEXTFREE(d);
    }

    UNLOCK(mem_pool[home].memoryLock)

  }

  if (result) {
    NEXTFREE(result) = 0;  /* in case it was set earlier */
  }
  else {
    /* grab a big block, free it, then retry request */
    block_size = max(alloc_size, 4*(1<<MAXFAST));
    LOCK(Global->memLock);
    freespace = (unsigned *) G_MALLOC(block_size+2*sizeof(unsigned),
					   home);
    MigrateMem(freespace, block_size+2*sizeof(unsigned), home);

    mem_pool[home].touched++;
    UNLOCK(Global->memLock);
    freespace+=2;
    SIZE(freespace) = block_size;
    HOME(freespace) = home;
    for (i=0; i<block_size/sizeof(unsigned); i++)
      freespace[i] = 0;
    if (block_size == alloc_size)
      result = freespace;
    else {
      mem_pool[home].tally += SIZE(freespace);
      if (mem_pool[home].tally > mem_pool[home].maxm) {
	mem_pool[home].maxm = mem_pool[home].tally;
      }
      MyFree(freespace);
      result = (unsigned *) MyMalloc(alloc_size, home);
    }
  }

  mem_pool[home].tally += SIZE(result);
  if (mem_pool[home].tally > mem_pool[home].maxm) {
    mem_pool[home].maxm = mem_pool[home].tally;
  }

  if (SIZE(result) < size)
    printf("*** Bad size from malloc %d, %d\n", size, SIZE(result));

  return((char *) result);

}


MigrateMem(start, length, home)
unsigned int *start;
int length, home;
{
  unsigned int *finish;
  unsigned int currpage, endpage;
  int i;
  int j;

/* POSSIBLE ENHANCEMENT:  Here is where one might distribute the memory
   pages across physically distributed memories as desired.

   One way to do this is as follows:

   finish = (unsigned int *) (((char *) start) + length);

   currpage = (unsigned int) start;
   endpage = (unsigned int) finish;
   if ((home == DISTRIBUTED) || (home < 0) || (home >= mallocP)) {
     j = 0;
     while (currpage < endpage) {

       Place all addresses x such that
         (currpage <= x < currpage + PAGE_SIZE) on node j

       j++;
       currpage += PAGE_SIZE;
     }
   } else {
     Place all addresses x such that
       (currpage <= x < endpage) on node home
   }  
*/
}
    

MyFree(block)
unsigned *block;
{
  int home;

  home = HOME(block);
  LOCK(mem_pool[home].memoryLock)
  MyFreeNow(block);
  UNLOCK(mem_pool[home].memoryLock)
}


MyFreeNow(block)
unsigned *block;
{
  int bucket, size, home;
  extern int MyNum;

  size = SIZE(block);
  home = HOME(block);

  if (size <= 0) {
    printf("Bad size %d\n", size);
    exit(-1);
  }
  if (home < -1 || home >= mallocP) {
    printf("Bad home %d\n", home);
    exit(-1);
  }

  if (size > MAXFASTBL)
    bucket = MAXFAST;
  else {
    bucket = FindBucket(size);
    if (size < 1<<bucket)
      bucket--;
  }

  /* throw away tiny blocks */
  if (bucket == 0)
    return;

  NEXTFREE(block) = (unsigned *) mem_pool[home].freeBlock[bucket];
  mem_pool[home].freeBlock[bucket] = block;
  mem_pool[home].tally -= size;

}