#ifndef __rcs_id__
#ifndef __rcs_id_util_memdebug_c__
#define __rcs_id_util_memdebug_c__
static const char __rcs_id_util_memdebug_c[] = "$Id: memdebug.c,v 1.2 2000/01/04 06:29:54 stephensk Exp $";
#endif
#endif /* __rcs_id__ */

#ifdef MEMDEBUG
#undef MEMDEBUG
#endif

#include "memdebug.h"

#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <string.h>
#include <assert.h>
#include <unistd.h> /* getpid() */

#ifdef malloc
#undef malloc
#endif

#ifdef realloc
#undef realloc
#endif

#ifdef free
#undef free
#endif

#ifdef calloc
#undef calloc
#endif

/************************************************************************/

#ifdef MEMDEBUG_INTERLOPER
/*
** Compile MEMDEBUG_INTERLOPER in here redefining it to something
** that memdebug_* can call for allocation.
*/
#define malloc _mdi_malloc
#define _real_malloc _mdi_malloc
#define realloc _mdi_realloc
#define _real_realloc _mdi_realloc
#define free _mdi_free
#define _real_free _mdi_free
#define calloc _mdi_calloc
#define memalign _mdi_memalign
#define valloc _mdi_valloc

/* For gmalloc.c */
#define _MALLOC_INTERNAL
#ifdef __STDC__
#undef __STDC__
#define __STDC__ 1
#endif

#ifndef MEMDEBUG_INTERLOPER_C
#include "gmalloc.c"
#else
#include MEMDEBUG_INTERLOPER_C
#endif

/*
** memdebug_* now uses MEMDEBUG_INTERLOPER for allocation
*/
#ifdef malloc
#undef malloc
#endif
#ifdef realloc
#undef realloc
#endif
#ifdef free
#undef free
#endif
#ifdef calloc
#undef calloc
#endif
#ifdef memalign
#undef memalign
#endif
#ifdef valloc
#undef valloc
#endif

/*
** Make memdebug_malloc malloc, etc.
*/
#define memdebug_malloc malloc
#define memdebug_realloc realloc
#define memdebug_free free
#define memdebug_calloc calloc
#define memdebug_valloc valloc
#define memdebug_memalign memalign

#endif

#ifdef const
#undef const
#endif

#ifndef _real_malloc
#define _real_malloc malloc
#endif
#ifndef _real_free
#define _real_free free
#endif
#ifndef _real_realloc
#define _real_realloc realloc
#endif

/************************************************************************/

size_t memdebug_blocks = 0;
size_t memdebug_bytes = 0;
size_t memdebug_blocks_total = 0;
size_t memdebug_bytes_total = 0;
size_t memdebug_blocks_max = 0;
size_t memdebug_bytes_max = 0;

typedef struct line_info {
  const char *file;
  unsigned short line;
} line_info;

typedef struct memdebug_blk {
  struct memdebug_blk *next, *prev;
  line_info li;
  unsigned char in_use;
  unsigned char stop_on_error;
  unsigned short routine;
  unsigned long id;
  size_t size;
  unsigned long hash;
  double data[1];
/*unsigned long hash_after*/
} memdebug_blk;

#define memdebug_blk_PTR(b) ((char*)((b)->data))
#define memdebug_blk_OFFSET ((size_t)&((memdebug_blk*)0)->data)
#define memdebug_blk_SIZE (memdebug_blk_OFFSET+sizeof(unsigned long))
#define PTR_memdebug_blk(p)  ((void*)(((char*) ptr) - memdebug_blk_OFFSET))

#define memdebug_blk_HASH(b,X) (((unsigned long)(b) << 3) ^ ((unsigned long)(b) >> 7) ^ (b->size) ^ (X))

#define memdebug_blk_BEFORE(b) (b)->hash
#define memdebug_blk_AFTER(b) (*(unsigned long*) (memdebug_blk_PTR(b) + (b)->size))

#define memdebug_blk_IS_FREE(b) (! (b)->in_use)

#define memdebug_blk_INIT(b,SIZE) \
(b)->size = (SIZE); \
(b)->li.file = file; \
(b)->li.line = line; \
(b)->stop_on_error = 0; \
memdebug_blk_BEFORE(b) = memdebug_blk_HASH(b,0); \
{ unsigned long h = memdebug_blk_HASH(b, (b)->size); \
  memcpy(&memdebug_blk_AFTER(b), &h, sizeof(h)); }

static memdebug_blk live_blocks = { &live_blocks, &live_blocks };
static memdebug_blk free_blocks = { &free_blocks, &free_blocks };

#define memdebug_blk_LOOP(e,b) do{ memdebug_blk *_##b = (e)->next; while ( _##b != (e) ) { memdebug_blk *b = _##b; _##b = _##b->next; {
#define memdebug_blk_LOOP_END }}}while(0)

/********************************************************************/

enum memdebug_routines {
  mdr_malloc = 0,
  mdr_free,
  mdr_realloc,
  mdr_calloc,
  mdr_memalign,
  mdr_valloc,
  mdr_operator_new,
  mdr_operator_delete,
  mdr_operator_new_A,
  mdr_operator_delete_A,
  mdr_LAST
};

static char *memdebug_routine_names[] = {
  "malloc",
  "free",
  "realloc",
  "calloc",
  "memalign",
  "valloc",
  "operator new",
  "operator delete",
  "operator new[]",
  "operator delete[]",
  0
};

/********************************************************************/

int memdebug_keep_free_blocks = 0;

static
void memdebug_blk_insert_after(memdebug_blk *b, memdebug_blk *e)
{
  e->next->prev = b;
  b->prev = e;
  b->next = e->next;
  e->next = b;
}

static
void memdebug_blk_remove(memdebug_blk *b)
{
  b->prev->next = b->next;
  b->next->prev = b->prev;
}

static
void memdebug_blk_HASH_FREE(memdebug_blk *b)
{
  size_t i;
  
  for ( i = sizeof(line_info); i + sizeof(unsigned long) <= b->size ; i += sizeof(unsigned long) ) {
    *(unsigned long*) (memdebug_blk_PTR(b) + i) = memdebug_blk_HASH(b, i);
  }
}

/********************************************************************/
/* logging */

FILE *memdebug_output = 0; /* stderr */
const char *memdebug_output_prefix = "\tMEMDEBUG: ";
int memdebug_log_procid = 1;

static
void vssprintf(char **s, const char *format, va_list *vap)
{
  vsprintf(*s, format, *vap);
  *s = strchr(*s, '\0');
}

static
void ssprintf(char **s, const char *format, ...)
{
  va_list(vap);
  va_start(vap, format);
  vssprintf(s, format, &vap);
  va_end(vap);
}

static
void msg(memdebug_blk *b, const char *format, ...)
{
  char buf[1024];
  char *_s = buf, **s = &_s;

  va_list(vap);

  if ( format[0] == '\n' ) {
    ssprintf(s, "\n");
    format ++;
  }
  
  ssprintf(s, "%s", memdebug_output_prefix);

  if ( memdebug_log_procid ) 
    ssprintf(s, "%d: ", getpid());
  
  if ( b ) {
    ssprintf(s, "%lu: ",
	    (unsigned long) b->id);

    ssprintf(s, "%p[%lu]: ", 
    	b->data, b->size);
	
    if ( b->li.line ) {
      ssprintf(s, "%s:%d: ", 
	b->li.file ? b->li.file : "<unknown>" , b->li.line);
    } else {
      ssprintf(s, "%p: ", 
	b->li.file);
    }
    
    ssprintf(s, "%s: ",
	b->routine < mdr_LAST ?  memdebug_routine_names[b->routine] : "<unknown>"
    );

    if ( ! b->in_use ) {
      line_info *li = (void*) memdebug_blk_PTR(b);
      ssprintf(s, "freed at ");
      if ( li->line ) {
	ssprintf(s, "%s:%d: ", li->file ? li->file : "<unknown>", li->line);
      } else {
	ssprintf(s, "%p: ", li->file);
      }
    }
  }

  va_start(vap, format);
  vssprintf(s, format, &vap);
  va_end(vap);

  if ( ! memdebug_output ) {
    memdebug_output = stderr;
  }

  fwrite(buf, 1, strlen(buf), memdebug_output);
  fflush(memdebug_output);
}

int memdebug_log_each_alloc = 0;

/********************************************************************/
/* block validation */

/* Set a debugger breakpoint here to catch all blk with bounds overwritten */
void memdebug_blk_invalid(memdebug_blk *b)
{
   /* Nothing */
}

/* Set a debugger breakpoint here to catch freed blks that are modified. */
void memdebug_free_blk_modified(memdebug_blk *b)
{
   /* Nothing */
}


static
int memdebug_blk_CHECK(memdebug_blk *b)
{
  int faults = 0;
  
  if ( memdebug_blk_BEFORE(b) != memdebug_blk_HASH(b,0) ) {
    msg(b, "invalid before hash\n");
    memdebug_blk_invalid(b);
    faults ++;
  }

  if ( ! (memdebug_blk_IS_FREE(b) && b->size < sizeof(line_info)) ) {
    unsigned long h = memdebug_blk_HASH(b,(b)->size);

    if ( memcmp(&memdebug_blk_AFTER(b), &h, sizeof(h)) != 0 ) { 
      msg(b, "invalid after hash\n");
      memdebug_blk_invalid(b);
      faults ++;
    }
  }

  if ( memdebug_keep_free_blocks && memdebug_blk_IS_FREE(b) ) {
    size_t i;
    int lfaults = 0;

    for ( i = sizeof(line_info); i + sizeof(unsigned long) <= b->size; i += sizeof(unsigned long) ) {
      if ( *(unsigned long*) (memdebug_blk_PTR(b) + i) != memdebug_blk_HASH(b, i) ) {
	msg(b, "modified at %lu\n", i);
        lfaults ++;
      }
    }
    if ( lfaults ) {
      memdebug_free_blk_modified(b);
    }
    faults += lfaults;
  }

  return faults;
}


/********************************************************************/
/* Pointer validation */

unsigned long memdebug_stop_on_id = 0;
size_t memdebug_stop_on_size_limit = 0;

/* Set a debugger breakpoint here to catch all bad pointers */
void memdebug_stop(memdebug_blk *b)
{
}


int memdebug_validate_ptrs = 1;

/* Set a debugger breakpoint here to catch all bad pointers */
void memdebug_ptr_invalid(void *ptr)
{
   /* Nothing */
}

int memdebug_ptr_valid(void *ptr, const char *routine)
{
    memdebug_blk_LOOP(&live_blocks, b);
    {
      memdebug_blk_CHECK(b);

      if ( memdebug_blk_PTR(b) == ptr ) {
        return 0;
      }
      if ( memdebug_blk_PTR(b) < (char*) ptr && (char*) ptr < memdebug_blk_PTR(b) + b->size ) {
        msg(b, "\n%s: Interior ptr %p\n", routine, ptr);
	memdebug_ptr_invalid(ptr);
	return 1;
      }
    }
    memdebug_blk_LOOP_END;
    msg(0, "\n%s: Bad ptr %p\n", routine, ptr);
    memdebug_ptr_invalid(ptr);
    return 2;
}

int memdebug_check_live_always = 1;
int memdebug_stats_every_checks = 0;

void memdebug_check_live()
{
  static unsigned long nchecks = 0;
  int faults = 0;
  
  ++ nchecks;
  if ( memdebug_stats_every_checks && (nchecks % memdebug_stats_every_checks == 0) ) {
    msg(0, "\ncheck id %lu", nchecks);
    memdebug_stats();
  } else {
    memdebug_blk_LOOP(&live_blocks, b);
    {
      faults += memdebug_blk_CHECK(b);
    }
    memdebug_blk_LOOP_END;
    
    memdebug_blk_LOOP(&free_blocks, b);
    {
      faults += memdebug_blk_CHECK(b);
    }
    memdebug_blk_LOOP_END;
    if ( faults ) {
      msg(0, " %lu faults.\n\n", faults);
    }
  }
}

/********************************************************************/
/* free list allocation */

int memdebug_use_free_list = 1;

memdebug_blk *memdebug_free_list_alloc(size_t s)
{
    memdebug_blk_LOOP(&free_blocks, b);
    {
      memdebug_blk_CHECK(b);
      if ( b->size == s ) {
        memdebug_blk_remove(b);
        return b;
      }
    }
    memdebug_blk_LOOP_END;
    
    return 0;
}

/********************************************************************/
/* init */

static void memdebug_atexit()
{
  msg(0, "\nat exit()");
  memdebug_stats();
}

static int memdebug_inited = 0;
static void memdebug_init_()
{
   memdebug_inited ++;
   atexit(memdebug_atexit);
}

#define memdebug_init() if ( ! memdebug_inited ) { memdebug_init_(); }

/********************************************************************/
/* internal malloc/free */
static unsigned long memdebug_alloc_id = 0;

void *memdebug_malloc__ (size_t s, const char *file, int line, int routine)
{
  memdebug_blk *b = 0;

  memdebug_init();
  
  if ( memdebug_check_live_always ) {
    memdebug_check_live();
  }

  /* accounting */	
  memdebug_blocks ++;
  if ( memdebug_blocks_max < memdebug_blocks )
    memdebug_blocks_max = memdebug_blocks;
  memdebug_blocks_total ++;
  memdebug_bytes += s;
  if ( memdebug_bytes_max < memdebug_bytes )
    memdebug_bytes_max = memdebug_bytes;
  memdebug_bytes_total += s;

  if ( memdebug_stop_on_size_limit && s > memdebug_stop_on_size_limit ) {
    memdebug_stop(0);
  }

  if ( memdebug_use_free_list ) {
    b = memdebug_free_list_alloc(s);
  }
  
  if ( ! b ) {
    b = (void*) _real_malloc ((s > sizeof(line_info) ? s : sizeof(line_info)) + memdebug_blk_SIZE);
  }
  
  b->in_use = 1;
  b->routine = routine;
  b->id = ++ memdebug_alloc_id;

  memdebug_blk_INIT(b, s);
  memdebug_blk_insert_after(b, &live_blocks);

  if ( memdebug_log_each_alloc ) {
    msg(b, "ALLOC\n");
  }

  if ( b->id == memdebug_stop_on_id ) {
    memdebug_stop(b);
  }

  return b->data;
}

void memdebug_free__ (void *ptr, const char *file, int line, int routine)
{
  line_info *li = ptr;
  memdebug_blk *b;

  memdebug_init();
  
  if ( memdebug_check_live_always ) {
    memdebug_check_live();
  }
	
  if ( ! ptr ) {
    return;
  }

  if ( memdebug_validate_ptrs ) {
    if ( memdebug_ptr_valid(ptr, "free") )
      return;
  }
  
  b = PTR_memdebug_blk(ptr);

  if ( b->id == memdebug_stop_on_id ) {
    memdebug_stop(b);
  }

  if ( ! b->in_use ) {
    msg(b, "already freed\n");
    abort();
  }

  memdebug_blk_CHECK(b);

  if ( memdebug_log_each_alloc ) {
    msg(b, "DEALLOC\n");
  }

  /* accounting */	
  assert(memdebug_blocks > 0);
  memdebug_blocks --;
  assert(memdebug_bytes >= b->size);
  memdebug_bytes -= b->size;

  b->in_use = 0;
  li->file = file;
  li->line = line;
  memdebug_blk_remove(b);
  
  if ( memdebug_keep_free_blocks || memdebug_use_free_list ) {
    memdebug_blk_HASH_FREE(b);
    memdebug_blk_insert_after(b, &free_blocks);
  } else {
    _real_free (b);
  }
}

/********************************************************************/
/* Versions with line_info */

void *memdebug_malloc_ (size_t s, const char *file, int line)
{
  return memdebug_malloc__(s, file, line, mdr_malloc);
}

void memdebug_free_ (void *ptr, const char *file, int line)
{
  memdebug_free__ (ptr, file, line, mdr_free);
}

void *memdebug_realloc_ (void *ptr, size_t s, const char *file, int line)
{
  memdebug_blk *b = PTR_memdebug_blk(ptr);
  unsigned long prev_id;

  if ( ! ptr )
    return memdebug_malloc__ (s, file, line, mdr_realloc);

  prev_id = b->id;

  if ( memdebug_check_live_always ) {
    memdebug_check_live();
  }

  if ( memdebug_validate_ptrs ) {
    if ( memdebug_ptr_valid(ptr, "realloc") )
      return memdebug_malloc_(s, file, line);
  }
  	
  memdebug_blk_CHECK(b);

  assert(memdebug_blocks > 0);
  memdebug_blocks --;
  assert(memdebug_bytes >= b->size);
  memdebug_bytes -= b->size;

  memdebug_blk_remove(b);

  memdebug_bytes_total -= b->size;
  
  b = (void*) _real_realloc (b, (s > sizeof(line_info) ? s : sizeof(line_info)) + memdebug_blk_SIZE);

  memdebug_blocks ++;
  memdebug_bytes += s;
  memdebug_bytes_total += s;

  b->in_use = 1;
  b->id = prev_id;
  memdebug_blk_INIT(b, s);
  memdebug_blk_insert_after(b, &live_blocks);

  if ( memdebug_log_each_alloc ) {
    msg(b, "REALLOC\n");
  }

  return b->data;
}

void *memdebug_calloc_ (size_t s1, size_t s2, const char *file, int line)
{
  void *p;
  s1 *= s2;
  p = memdebug_malloc__ (s1, file, line, mdr_calloc);
  memset(p, 0, s1);
  return p;
}

void *memdebug_memalign_ (size_t s1, size_t s2, const char *file, int line)
{
  abort();
  return 0;
}

void *memdebug_valloc_ (size_t s1, const char *file, int line)
{
  abort();
  return 0;
}

void *memdebug_operator_new_ (size_t s, const char *file, int line)
{
  return memdebug_malloc__(s, file, line, mdr_operator_new);
}

void memdebug_operator_delete_ (void *ptr, const char *file, int line)
{
  memdebug_free__ (ptr, file, line, mdr_operator_delete);
}

void *memdebug_operator_new_A_ (size_t s, const char *file, int line)
{
  return memdebug_malloc__(s, file, line, mdr_operator_new_A);
}

void memdebug_operator_delete_A_ (void *ptr, const char *file, int line)
{
  memdebug_free__ (ptr, file, line, mdr_operator_delete_A);
}

/*********************************************************************/
/* Versions without line_info */

#ifndef __ptr_t
#define __ptr_t void *
#endif

#ifdef SOLARIS
/* SAVED_FP RETURN_ADDR s SECOND_ARG ... */
#define GET_RETURN_ADDR(s) ((void**)&s)[-2]
#endif
#ifndef GET_RETURN_ADDR
/* SAVED_FP RETURN_ADDR s SECOND_ARG ... */
#define GET_RETURN_ADDR(s) ((void**)&s)[-1]
#endif

__ptr_t memdebug_malloc (size_t s)
{
  return memdebug_malloc_ (s, GET_RETURN_ADDR(s), 0);
}

void memdebug_free (__ptr_t p)
{
  memdebug_free_ (p, GET_RETURN_ADDR(p), 0);
}

__ptr_t memdebug_realloc (__ptr_t p, size_t s)
{
  return memdebug_realloc_ (p, s, GET_RETURN_ADDR(p), 0);
}

__ptr_t memdebug_calloc (size_t s1, size_t s2)
{
  return memdebug_calloc_ (s1, s2, GET_RETURN_ADDR(s1), 0);
}

__ptr_t memdebug_memalign (size_t s1, size_t s2)
{
  return memdebug_memalign_ (s1, s2, GET_RETURN_ADDR(s1), 0);
}

__ptr_t memdebug_valloc (size_t s1)
{
  return memdebug_valloc_ (s1, GET_RETURN_ADDR(s1), 0);
}

__ptr_t memdebug_operator_new (size_t s)
{
  return memdebug_operator_new_ (s, GET_RETURN_ADDR(s), 0);
}

void memdebug_operator_delete (__ptr_t p)
{
  memdebug_operator_delete_ (p, GET_RETURN_ADDR(p), 0);
}

__ptr_t memdebug_operator_new_A (size_t s)
{
  return memdebug_operator_new_A_ (s, GET_RETURN_ADDR(s), 0);
}

void memdebug_operator_delete_A (__ptr_t p)
{
  memdebug_operator_delete_A_ (p, GET_RETURN_ADDR(p), 0);
}


/**********************************************************************/
/* statistics */

void memdebug_stats()
{
  int faults = 0;
  
  msg(0, "\nblocks %lu, bytes %lu: bytes/block %g in use\n", (unsigned long) memdebug_blocks, (unsigned long) memdebug_bytes, (double) memdebug_bytes / (double) memdebug_blocks);

  msg(0, "blocks %lu, bytes %lu: bytes/block %g max\n", (unsigned long) memdebug_blocks_max, (unsigned long) memdebug_bytes_max, (double) memdebug_bytes_max / (double) memdebug_blocks_max);

  msg(0, "blocks %lu, bytes %lu: bytes/block %g total\n", (unsigned long) memdebug_blocks_total, (unsigned long) memdebug_bytes_total, (double) memdebug_bytes_total / (double) memdebug_blocks_total);

  fflush(memdebug_output);

  {
    unsigned long n;
    size_t s;

    msg(0, "scanning live blocks:\n");

    s = n = 0;
    memdebug_blk_LOOP(&live_blocks, b);
    {
      faults += memdebug_blk_CHECK(b);
      n ++;
      s += b->size;
    }
    memdebug_blk_LOOP_END;

    msg(0, " %lu (%lu bytes) DONE.\n", n, s);

    msg(0, "scanning free blocks:\n");

    n = s = 0;
    memdebug_blk_LOOP(&free_blocks, b);
    {
      faults += memdebug_blk_CHECK(b);
      n ++;
      s += b->size;
    }
    memdebug_blk_LOOP_END;

    msg(0, " %lu (%lu bytes) DONE.\n", n, s);
  }
  
  msg(0, " %lu faults.\n\n", faults);
}

/**********************************************************************/
/* EOF */