/* my_malloc.c : memory allocation routines with error checking
//

   Written and Copyright (C) 1994-1997 by Michael J. Gourlay

This file 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; either version 2, or (at your option)
any later version.

This file 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 file; see the file LICENSE.  If not, write to
the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.

*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <sys/types.h>


/* Apollo w/ Domain/OS SR10.4.1, BSD 4.3 has no "malloc.h".  Thanks to PW.
//
// Windows NT/95 using the cygwin package already includes "malloc.h".
// Thanks to Geoff Lawler.
*/

#if defined(apollo) || defined(__CYGWIN32__)
#else
#include <malloc.h>
#endif


#include "my_malloc.h"




/* timestamp: embed a string in the object for later perusal */
static const char *timestamp = "Copyright (C) Michael J. Gourlay " __DATE__ ;




/* NAME
//   listAppend: append a new element to the end of a reallocated list
//
//
// DESCRIPTION
//   A list, implemented as an array, is reallocated to have a new
//   element at the end of the original list.  The contents of the
//   original list is kept intact, but the address of the list elements
//   might change due to the realloc.
//
//   The newly appended list element is left uninitialized.
//
//
// ARGUMENTS
//   root (in/out): address of the variable that points to the
//     beginning of the list.  The list is an array of a type whose
//     size is 'size'.  DANGER:  The contents of 'root' might change
//     due to a realloc().
//
//   nmemb (in/out): address of the variable that holds the number of
//     elements in the list.  The contents 'nmemb' will increment to
//     include the newly appended list element.
//
//   size (in): size of an element of the list.
//
//
// RETURN VALUE
//   If the memory allocation for the new list failes, -2 is returned.
//   Otherwise, the index of the new element (which is the same as the
//   number of elements in the new list, minus one) is returned.
//
//
// NOTES
//   The user is responsible for freeing the memory allocated by
//   listAppend, either by calling listDelete for each element in the
//   list, or an explicit call to free().
//
//   This routine uses realloc().  realloc() is DANGEROUS because it can
//   and will reassign the address of the elements of the array pointed
//   to by 'root'.  That means that if you have something other than
//   'root' pointing to any elements in the 'root' array, and you call
//   listAppend, and the realloc() in listAppend reassigns the addresses,
//   the other pointers will point at nonsense.  Use with care.
//
//   The realloc() in this routine is NOT the my_realloc() that does
//   memory checking.  If you create a list with listAppend, then you
//   should not use my_free to eliminate the memory.  This is because
//   listAppend is used by my_realloc to do internal book-keeping.
//
//
// SEE ALSO
//   listDelete()
*/
int
listAppend(void ** root, int *nmemb, int size)
{
  if((*root = realloc(*root, size * (*nmemb + 1))) == NULL) {
    fprintf(stderr, "listAppend: bad alloc: %i\n", *nmemb + 1);
    return -2;
  }

  (*nmemb) ++;
  return *nmemb - 1;
}




/*
// ARGUMENTS
//   index (in): index of the element to delete
//
//
// RETURN VALUES
//   If 'index' is an invalid value, -1 is returned.
//   If the reallocation fails, -2 is returned.
//   Otherwise, 0 is returned.
//
//
// SEE ALSO
//   listAppend()
*/
int
listDelete(void ** root, int *nmemb, int size, int index)
{
  int remainder = *nmemb - index - 1;
  if((index < 0) || (index >= *nmemb)) {
    return -1;
  }

  memmove(((char*)(*root) + index*size), ((char*)(*root) + (index+1)*size),
          remainder * size);

  if(*nmemb > 1) {
    if((*root = realloc(*root, size * (*nmemb - 1))) == NULL) {
      fprintf(stderr, "listDelete: bad alloc: %i\n", *nmemb - 1);
      return -2;
    }
  } else {
    memset(*root, 0, size);
  }

  (*nmemb) --;

  return 0;
}




#ifdef DEBUG
/* MEM_BLOCK_: tokens for tagging MemBlocks */
#define MEM_BLOCK_HEAD_ACTIVE   0xfeedfaceabad1deall
#define MEM_BLOCK_HEAD_INACTIVE 0xdeadbeefabadcafell
#define MEM_BLOCK_TAIL_ACTIVE   0xacc01adeabaddeedll
#define MEM_BLOCK_TAIL_INACTIVE 0xcafef00dbeedeca1ll




struct MemBlock {
  long long *head;    /* Address of the block head */
  void      *user;    /* Address of the beginning of client memory */
  long long *tail;    /* Address of the block tail */
  size_t     size;    /* Size (in bytes) of the user portion of this chunk */
  long       nelem;   /* number of elements */
  int        elsize;  /* element size (in bytes) */
  int        line;    /* line in file of caller that requested the memory  */
  char      *file;    /* file of caller that requested the memory */
};




/* mb_list: list of MemBlocks */
static struct MemBlock *mb_list = NULL;

/* mb_num: size of the mb_list array */
static int mb_num = 0;




static int
memBlockAppend(void)
{
  return listAppend((void**)&mb_list, &mb_num, sizeof(struct MemBlock));
}




static int
memBlockDelete(int index)
{
  return listDelete((void**)&mb_list, &mb_num, sizeof(struct MemBlock), index);
}




static void
memBlockPrint(const struct MemBlock * const this)
{
  printf("MemBlock head %p\n", this->head);
  printf("MemBlock user %p\n", this->user);
  printf("MemBlock tail %p\n", this->tail);
  if(this->head != NULL) {
    printf("MemBlock head[0] %llx ", this->head[0]);

    if(this->head[0] != MEM_BLOCK_HEAD_ACTIVE) {
      printf("CORRUPT");
#if (DEBUG >= 1)
      abort();
#endif
    }
    printf("\n");

    if(this->tail != NULL) {
      printf("MemBlock tail[0] %llx ", this->tail[0]);
      if(this->tail[0] != MEM_BLOCK_TAIL_ACTIVE) {
        printf("CORRUPT");
#if (DEBUG >= 1)
        abort();
#endif
      }
      printf("\n");
    }
  }
  printf("MemBlock size %i\n", this->size);
  printf("MemBlock nelem %li\n", this->nelem);
  printf("MemBlock elsize %i\n", this->elsize);
  printf("MemBlock allocated from file '%s' line %i\n", this->file, this->line);
}




void
memBlockInventory(const int all)
{
  int mbi;

  printf("memBlockInventory: ");
  if(all) {
    printf("reporting all blocks:\n");
  } else {
    printf("unfreed blocks:\n");
  }

  for(mbi=0; mbi < mb_num; mbi++) {
    if(all || mb_list[mbi].head != NULL) {
      printf("MemBlock %i:\n", mbi);
      memBlockPrint(&mb_list[mbi]);
      printf("\n");
    }
  }
}




/* NAME
//   memBlockCheck: check MemBlock for corruption
//
// DESCRIPTION
//   The memory in a MemBlock has tags at the beginning and end of the
//   allocated memory chunk.  If the tags do not have one of a small
//   set of valid values then the memory chunk is considered to have
//   been corrupted.  This sort of rudimentary checking will discover
//   most cases of exceeding array boundaries.
*/
static void
memBlockCheck(const struct MemBlock * const this)
{
  if(this->head != NULL) {
    if(   (this->head[0] != MEM_BLOCK_HEAD_ACTIVE)
       && (this->head[0] != MEM_BLOCK_HEAD_INACTIVE))
    {
      fprintf(stderr, "memBlockCheck: corrupt head\n");
      memBlockPrint(this);
    }
    if(this->tail != NULL) {
      if(   (this->tail[0] != MEM_BLOCK_TAIL_ACTIVE)
         && (this->tail[0] != MEM_BLOCK_TAIL_INACTIVE))
      {
        fprintf(stderr, "memBlockCheck: corrupt tail\n");
        memBlockPrint(this);
      }
    }
  }
}




static void
memBlockCheckAll(void)
{
  int mbi;
  for(mbi=0; mbi < mb_num; mbi++) {
    memBlockCheck(&mb_list[mbi]);
  }
}




/* NAME
//   memBlockIndex: Search for pointer in the list of MemBlocks
//
//
// NOTES
//   Search starting from the end of the list of MemBlocks.
//   This is because it is possible (perhaps likely) that the same
//   memory address will be used multiple times between malloc/free
//   calls, and we want to reference the most recently malloced block
//   with the given address.
*/
static int
memBlockIndex(const void * const ptr)
{
  int mbi;

  for(mbi=mb_num-1; mbi >= 0; mbi--) {
    if(ptr == mb_list[mbi].user) {
      /* Found this pointer in memory table */
      return mbi;
    }
  }
  return -1;
}




/* TAG_SIZE: size, in bytes, of the head and tail tags
//
// NOTES
//   TAG_SIZE must also be the size of a memory block alignment for
//   heap allocation.  Usually, this is the same as the wise of a word
//   for the architeture, but can be the size of a double word for a
//   64-bit architecture.  Usually, a "long long" here will suffice.
*/
#define TAG_SIZE sizeof(long long)




#else
#define TAG_SIZE 0
#endif /* DEBUG */




/* NAME
//   my_realloc: memory allocation with debugging
//
//
// ARGUMENTS
//   ptr (in/out): address of the user portion of previously allocated memory
//
//   nelem (in): number of elements to allocate
//
//   elsize (in): size of the element, in bytes
//
//   file (in): name of the file where my_realloc is called from
//
//   line (in): line number of the file where my_realloc is called from
//
//
// DESCRIPTION
//   my_realloc is the workhorse routine for several incarnations of
//   this memory allocation package.  Usually, my_realloc would not be
//   called by the client directly, but instead would be called through
//   one of several calling macros, such as REALLOC, MY_CALLOC or
//   CALLOC, which provide programming interfaces more like the system
//   alloc routines.
//
//   my_realloc sets up and performs memory allocation debugging table
//   entries which can be used to help find array bounds violations and
//   un-freed memory blocks ("memory leaks").
//
//
// NOTES
//   The address "ptr" is searched for in the list of MemBlocks.  If it is
//   found, and if the associated MemBlock is active, then the head of that
//   MemBlock is used as the actual beginning of the memory chunk.  (Note
//   that it is possible for "ptr" to be found in the list of MemBlocks and
//   for that MemBlock to be inactive.  This probably means that the client,
//   at one time, used my_realloc to allocate a memory chunk, freed it using
//   my_free, then used a system alloc routine which coincidentally created
//   another memory chunk which happened to start at the same address as
//   "ptr".)
//
//   If "ptr" is not found in the list of MemBlocks or if "ptr" is found but
//   the MemBlock is inactive, then "ptr" is used as the actual beginning of
//   the memory chunk.  In this situation, it is probably the case that the
//   client used the system alloc routines to allocate the memory chunk, and
//   it using my_realloc instead of realloc.  I.e., the client is mixing use
//   of my_realloc and system alloc routines, which is probably a Bad Idea.
//
//
// SEE ALSO
//   MY_CALLOC, REALLOC, CALLOC, MALLOC, FREE
*/
void *
my_realloc(void * const ptr, const long nelem, const int elsize, const char * const file, const int line)
{
  void *mem = ptr;

#ifdef DEBUG
  int  mbi = memBlockIndex(ptr);   /* Find MemBlock for this chunk */
#endif


#if (VERBOSE >= 2)
  printf("my_realloc: %p %li %i %s %i\n", ptr, nelem, elsize, file, line);
#endif


#ifdef DEBUG
#ifdef SUNOS
  malloc_verify();
#endif

#if defined(sgi)
  /* If this is not resolved at link time, try linking with -lmalloc */
  mallopt(M_DEBUG, 1);
#endif

  memBlockCheckAll();

  /* See if MemBlock was found for this chunk */
  if(mbi >= 0) {
    /* A MemBlock was found for the chunk with user portion at ptr */
    if(    (mb_list[mbi].head != NULL)
        && (mb_list[mbi].head[0] == MEM_BLOCK_HEAD_ACTIVE))
    {
      /* The MemBlock is active so its head is the top of the memory chunk */
      mem = mb_list[mbi].head;
    }
  }
#endif /* DEBUG */


  /* Check the validity of the input parameters */
  if(nelem < 0) {
    fprintf(stderr, "my_realloc: %s: %i: Bad Value: nelem=%li\n",
            file, line, nelem);

#ifdef DEBUG
    abort();
#endif

    return NULL;
  }
  if(elsize < 0) {
    fprintf(stderr, "my_realloc: %s: %i: Bad Value: elsize=%i\n",
            file, line, elsize);

#ifdef DEBUG
    abort();
#endif

    return NULL;
  }

  if(nelem * elsize <= 0) {
    printf("my_realloc: WARNING: allocating no memory\n");
  }


  /* Allocate the client memory:
  // The extra 2 TAG_SIZE elements are for the head and tail tags.
  // One of the extra TAG_SIZE is for aligment.
  */
  if((mem=realloc(mem, (nelem*elsize)+(3 * TAG_SIZE)))==NULL)
  {
    fprintf(stderr, "my_realloc: %s: %i: Bad Alloc: %li x %i\n",
            file, line, nelem, elsize);
  }

#ifdef DEBUG
  else {
    /* Assign the various portions of the memory chunk */
    long long  *head = mem;
    char       *user = (char *)(&head[1]);
    long long  *tail = (long long*)(&user[nelem * elsize]);

    /* Refer mem to the user portion of the memory chunk */
    mem = user;

    /* Avoid a bus error by finding an address with proper alignment
       for the user and tail.  This is a big hack and makes some
       assumptions about word allignment requirements of a machine --
       specifically that the word size is smaller than or equal to a
       "long long integer", and that alignment is an even multiple of
       the size of a long long.  If this causes problems for your
       architecture, then turn memory debugging off, or comment out the
       tail reference lines throughout this module.  Also, report the
       error to the authors.

    */

    {
      unsigned long align = (long)tail;
      align = ((align + (sizeof(long long)-1)) / sizeof(long long)) * sizeof(long long);

#if (VERBOSE >= 2)
      printf("tail was=%p  align=%li\n", tail, align);
#endif
      tail = (long long *)align;

#if (VERBOSE >= 2)
      printf("tail is=%p\n", tail);
#endif

    }


    /* Tag the memory chunk */
    head[0] = MEM_BLOCK_HEAD_ACTIVE;
    tail[0] = MEM_BLOCK_TAIL_ACTIVE;

    /* Clear new portion of the memory chunk */
    if((ptr == NULL) || (mbi >= 0)) {
      /* By default, clear the entire memory chunk */
      char *new = mem;
      int new_size = nelem * elsize;

      /* If this is really a realloc, only clear new portion */
      if(mbi >= 0) {
        int old_size = mb_list[mbi].size;
        new = &user[old_size];
        new_size = nelem * elsize - old_size;
      }

#if (DEBUG >= 3)
      printf("my_realloc: %s: %i: setting %i bytes at %p\n",
             file, line, new_size, new);
      memset(new, 1, new_size);
#else
      memset(new, 0, new_size);
#endif
    }

    /* If there was no MemBlock associated with this chunk, try to make one */
    if(mbi < 0) {
      mbi = memBlockAppend();
    }

    if(mbi >= 0) {
      /* Assign the MemBlock members */
      mb_list[mbi].head = head;
      mb_list[mbi].user = user;
      mb_list[mbi].tail = tail;
      mb_list[mbi].size = nelem*elsize;
      mb_list[mbi].nelem = nelem;
      mb_list[mbi].elsize = elsize;
      mb_list[mbi].line = line;
      mb_list[mbi].file = strdup(file);
      if(mb_list[mbi].file == NULL) {
      fprintf(stderr,"my_realloc: %s: %i: bad interal alloc: file\n",file,line);
      }
    }
  }

#ifdef SUNOS
  malloc_verify();
#endif

  memBlockCheckAll();

#endif /* DEBUG */


#if (VERBOSE >= 2)
  printf("my_realloc:%s:%i:allocated %li at %p\n", file,line,nelem*elsize,mem);
#endif

  return mem;
}




void
my_free(void * const ptr, const char * const file, const int line)
{
#if (VERBOSE >= 2)
  printf("my_free: %s: %i: %p\n", file, line, ptr);
  fflush(stdout);
#endif

#ifdef DEBUG
#ifdef SUNOS
  malloc_verify();
#endif

  memBlockCheckAll();

  {
    int mbi;

    if((mbi = memBlockIndex(ptr)) >= 0) {

      /* Check to see whether this block is okay */
      if(NULL == mb_list[mbi].head) {
        fprintf(stderr, "my_free: %s: %i: empty block\n", file, line);
        return;
      } else {
        if(   (MEM_BLOCK_HEAD_INACTIVE == mb_list[mbi].head[0])
           && (MEM_BLOCK_TAIL_INACTIVE == mb_list[mbi].tail[0]))
        {
          fprintf(stderr, "my_free: block already freed?\n");
        }
      }

#if (VERBOSE >= 3)
      printb("my_free: %s: %i: found ptr at index %i\n", file, line, mbi);
      memBlockPrint(&mb_list[mbi]);
#endif

      /* Fill the old memory chunk */
      memset(ptr, 0xfe, mb_list[mbi].size);

      /* Tag this block as inactive */
      mb_list[mbi].head[0] = MEM_BLOCK_HEAD_INACTIVE;
      mb_list[mbi].tail[0] = MEM_BLOCK_TAIL_INACTIVE;
    }

    if(mbi < 0) {
      /* Did not find pointer in the list of MemBlocks */
      fprintf(stderr, "my_free: %s: %i: freeing unknown pointer\n", file, line);

#if (DEBUG >= 3)
      abort();
#endif

      free(ptr);

    } else {
      free(mb_list[mbi].head);
      mb_list[mbi].head = NULL;

#if (DEBUG <= 1)
      /* Note that a DEBUG level of greater than 1 will result in a
      // record of every allocation done through these routines to
      // be kept, which could result is extremely slow performance.
      */
      memBlockDelete(mbi);
#endif
    }
  }

#ifdef SUNOS
  malloc_verify();
#endif
#else
  free(ptr);

#endif /* DEBUG */

  return;
}








#ifdef TEST_MY_MALLOC

void
test1(void)
{
  {
    int *ip;

    ip = MY_CALLOC(3, int);
    printf("ip = %i %i %i ?= 16843009\n", ip[0], ip[1], ip[2]);
    ip[0] = 1;
    ip[1] = 2;
    ip[2] = 3;
    FREE(ip);

    printf("\nshould err: unknown pointer or empty block\n");
    FREE(ip);

    printf("\n");
    ip = MY_CALLOC(3, int);
    ip[-1] = -1;  /* corrupt the head */
    ip[0] = 1;
    ip[1] = 2;
    ip[2] = 3;
    printf("should err:    corrupt head\n");
    FREE(ip);

    printf("\n-=-\n");
    ip = MY_CALLOC(3, int);
    ip[0] = 1;
    ip[1] = 2;
    ip[2] = 3;
    /* Should be okay */
    FREE(ip);
    printf("-=-\n");

    /* Mix system alloc and my_realloc */
    printf("\n");
    ip = calloc(3, sizeof(int));
    ip[0] = 1;
    ip[1] = 2;
    ip[2] = 3;

    /* Test realloc */
    ip = REALLOC(ip, sizeof(int)*5);
    printf("---\n");
    memBlockPrint(&mb_list[memBlockIndex(ip)]);
    ip[3] = 4;
    ip[4] = 5;
    /* Should be okay */
    FREE(ip);

    printf("\n");
    ip = MY_CALLOC(3, int);
    ip[0] = 1;
    ip[1] = 2;
    ip[2] = 3;
    ip[3] = 4;  /* corrupt tail */
    printf("should err:    corrupt tail\n");
    FREE(ip);

    printf("\n");
    ip = MY_CALLOC(3, int);
    ip[0] = 1;
    ip[1] = 2;
    ip[2] = 3;
    /* Leaving block without freeing memory -- should create warning */
  }

  {
    float *fp;

    printf("\n\n\n\n-=-=-=-=-\n");

    fp = MY_CALLOC(3, float);
    printf("fp = %15g %15g %15g ?= 2.36943e-38\n", fp[0], fp[1], fp[2]);
    fp[0] = 1.0;
    fp[1] = 2.0;
    fp[2] = 3.0;
    FREE(fp);

    printf("\nshould err: empty block\n");
    FREE(fp);

    printf("\n");
    fp = MY_CALLOC(3, float);
    fp[-1] = -1;  /* corrupt the head */
    fp[0] = 1.0;
    fp[1] = 2.0;
    fp[2] = 3.0;
    printf("should err:    corrupt head\n");
    FREE(fp);

    printf("\n-=-\n");
    fp = MY_CALLOC(3, float);
    fp[0] = 1.0;
    fp[1] = 2.0;
    fp[2] = 3.0;
    printf("-=-\n");

    /* Test realloc */
    memBlockPrint(&mb_list[memBlockIndex(fp)]);
    fp = REALLOC(fp, sizeof(float)*5);
    printf("---\n");
    memBlockPrint(&mb_list[memBlockIndex(fp)]);
    fp[3] = 4.0;
    fp[4] = 5.0;
    /* Should be okay */
    FREE(fp);

    printf("\n");
    fp = MY_CALLOC(3, float);
    fp[0] = 1.0;
    fp[1] = 2.0;
    fp[2] = 3.0;
    fp[3] = 4.0;  /* corrupt tail */
    printf("should err:    corrupt tail\n");
    FREE(fp);

    printf("\n");
    fp = MY_CALLOC(3, float);
    fp[0] = 1.0;
    fp[1] = 2.0;
    fp[2] = 3.0;
    fp[3] = 4.0;  /* corrupt tail */
    /* Leaving block without freeing memory -- should create warning */
  }
}




int
main()
{
  test1();

#ifdef DEBUG
#if (VERBOSE >= 2)
  printf("\n\n\n\n------------");
  memBlockInventory(1);
  printf("------------\n\n\n\n");
#endif

  printf("\n\n\n\n========\n");
  memBlockInventory(0);
#endif

  return 0;
}
#endif /* TEST_MY_MALLOC */