#include <signal.h>
#include <stdarg.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/file.h>

#include "defs.h"
#include "config.h"
#include "strings.h"
#include "externs.h"
#include "unused-arg.h"

/* #define MALTRACE /**/
#define USE_MAGIC /**/
#define RECORD_CALLER /**/
/* #define DO_FILLS /**/
/* #define RECORD_BUSY /**/
#define ALIGNMENT 8
#define PANIC_POOL 65536

#define OFFSET ((((sizeof(int)-1)/ALIGNMENT)+1)*ALIGNMENT)

#undef malloc
#undef malloc_roundup
#undef realloc
#undef calloc
#undef free
#undef cfree

#if defined(MMMALLOC)
#include <mmmalloc.h>
#define NEED_malloc_roundup
#elif defined(NeXT)
#define malloc         bsd_malloc
#define malloc_roundup bsd_malloc_roundup
#define realloc        bsd_realloc
#define free           bsd_free
extern void *bsd_malloc(unsigned long int);
extern void *bsd_malloc_roundup(unsigned long int, int *);
extern void bsd_free(void *);
extern void *bsd_realloc(void *, unsigned long int);
#else
#define NEED_malloc_roundup
#endif

#ifdef NEED_malloc_roundup
#undef NEED_malloc_roundup
void *malloc_roundup(int, int *);
void *malloc_roundup(int nb, int *rnbp)
{
 *rnbp = nb;
 return(malloc(nb));
}
#endif

static char panic_pool[PANIC_POOL];
static int panicked = 0;
static int used = 0;

static void malabort(const char *msg)
{
 write(2,msg,strlen(msg));
 abort();
}

void setpanicmalloc(void)
{
 panicked = 1;
}

static void chkused(void)
{
 if (used > PANIC_POOL) malabort("out of panic memory\n");
}

static void *panic_malloc(int nb)
{
 if (! panicked) return(malloc(nb));
 if (nb == 0) return(0);
 nb = (((nb-1)/ALIGNMENT)+1)*ALIGNMENT;
 used += nb + OFFSET;
 chkused();
 *((int *)&panic_pool[used-nb-OFFSET]) = nb;
 return(&panic_pool[used-nb]);
}

static void *panic_malloc_roundup(int nb, int *sp)
{
 if (! panicked) return(malloc_roundup(nb,sp));
 if (nb == 0)
  { *sp = 0;
    return(0);
  }
 nb = (((nb-1)/ALIGNMENT)+1)*ALIGNMENT;
 *sp = nb;
 used += nb + OFFSET;
 chkused();
 *((int *)&panic_pool[used-nb-OFFSET]) = nb;
 return(&panic_pool[used-nb]);
}

static void *panic_realloc(void *old, int newnb)
{
 int oldnb;

 if (! panicked) return(realloc(old,newnb));
 if (old == 0) return(panic_malloc(newnb));
 if (((char *)old < &panic_pool[0]) || ((char *)old >= &panic_pool[PANIC_POOL]))
  { malabort("bad panic realloc\n");
  }
 oldnb = *(int *)(((char *)old)-OFFSET);
 newnb = (((newnb-1)/ALIGNMENT)+1)*ALIGNMENT;
 if (((char *)old)+oldnb == &panic_pool[used])
  { used += newnb - oldnb;
    chkused();
    *(int *)(((char *)old)-OFFSET) = newnb;
    return(old);
  }
 else
  { void *new;
    new = panic_malloc(newnb);
    bcopy(old,new,(oldnb<newnb)?oldnb:newnb);
    return(new);
  }
}

static void panic_free(void *obj)
{
 if (! panicked)
  { free(obj);
    return;
  }
}

#undef malloc
#undef malloc_roundup
#undef realloc
#undef free
#define malloc(nb)            panic_malloc(nb)
#define malloc_roundup(nb,sp) panic_malloc_roundup(nb,sp)
#define realloc(old,nb)       panic_realloc(old,nb)
#define free(old)             panic_free(old)

#if defined(MALTRACE) || defined(RECORD_BUSY)
#define fmt_dec(bp,i) (void)fmt_aux(bp,i,10)
#define fmt_hex(bp,i) (void)fmt_aux(bp,i,16)
static char *fmt_aux(char *bp, unsigned long int n, int b)
{
 if (n < b)
  { *bp++ = "0123456789abcdef"[n];
  }
 else
  { bp = fmt_aux(bp,n/b,b);
    bp = fmt_aux(bp,n%b,b);
  }
 *bp = '\0';
 return(bp);
}
#endif

#ifdef USE_MAGIC
#define MMAGIC 0xc4fe6541U
#endif

#ifdef RECORD_BUSY
static unsigned long int busy[BUSY_SIZE];
static int busy_fill = 0;
#endif

#ifdef RECORD_BUSY
static void record_busy(unsigned long int p)
{
 char buf[128];
 register int l;
 register int m;
 register int h;
 register unsigned long int v;

 l = -1;
 h = busy_fill;
 if (h >= BUSY_SIZE) malabort("malloc busy table overflow!\n");
 while (h-l > 1)
  { m = (h + l) / 2;
    v = busy[m];
    if (v <= p) l = m;
    if (v >= p) h = m;
  }
 if (l == h)
  { strcpy(&buf[0],"malloc returned 0x");
    fmt_hex(&buf[strlen(&buf[0])],(int)p);
    strcpy(&buf[strlen(&buf[0])],"twice!\n");
    malabort(&buf[0]);
  }
 if (h < busy_fill)
  { bcopy((char *)&busy[h],(char *)&busy[h+1],(busy_fill-h)*sizeof(busy[0]));
  }
 busy[h] = p;
 busy_fill ++;
}
#endif

#ifdef RECORD_BUSY
static void record_unbusy(unsigned long int p)
{
 char buf[128];
 register int l;
 register int m;
 register int h;
 register unsigned long int v;

 l = -1;
 h = busy_fill;
 if (h < 1) malabort("malloc busy table underflow!\n");
 while (h-l > 1)
  { m = (h + l) / 2;
    v = busy[m];
    if (v <= p) l = m;
    if (v >= p) h = m;
  }
 if (l != h)
  { strcpy(&buf[0],"freeing unallocated 0x");
    fmt_hex(&buf[strlen(&buf[0])],(int)p);
    strcpy(&buf[strlen(&buf[0])],"!\n");
    malabort(&buf[0]);
  }
 busy_fill --;
 if (h < busy_fill)
  { bcopy((char *)&busy[h+1],(char *)&busy[h],(busy_fill-h)*sizeof(busy[0]));
  }
}
#endif

#ifdef DO_FILLS
/* fill pattern: if byte value is abcdefgh, a=msb, h=lsb, then:
	a = 0
	b = 1
	c = 0 except for last byte of filled area, where c = 1
	d,e,f,g = magic number identifying which fill() call this is
	h = one bit of byte count
   given N bytes to fill, the low bit of N are stored in h of the first
   byte filled, the next bit h of the second byte filled, etc.  Note
   that we always run out of nonzero bits of N no later than we run out
   of bytes to store them in.
*/
static void fill(char *p, int n, int i)
{
 unsigned int l;

 if (n < 0) malabort("invalid fill call");
 if (n == 0) return;
 i = 0x40 + (i << 1);
 l = n;
 for (;n>0;n--)
  { *p++ = i + (l & 1);
    l >>= 1;
  }
 p[-1] |= 0x20;
}
#endif

#define XOFF0 0

#if defined(RECORD_CALLER) || defined(DO_FILLS)
#define BLK_NB(p) (*(int *)((p)+(XOFF0*ALIGNMENT)))
#define XOFF1 (XOFF0+1)
#else
#define XOFF1 (XOFF0)
#endif

#ifdef RECORD_CALLER
#define BLK_FL(p) (*(void **)            ((p)+((XOFF1  )*ALIGNMENT)))
#define BLK_BL(p) (*(void **)            ((p)+((XOFF1+1)*ALIGNMENT)))
#define BLK_FN(p) (*(const char **)      ((p)+((XOFF1+2)*ALIGNMENT)))
#define BLK_LN(p) (*(int *)              ((p)+((XOFF1+3)*ALIGNMENT)))
#define BLK_TM(p) (*(time_t *)           ((p)+((XOFF1+4)*ALIGNMENT)))
#define XOFF2 (XOFF1+5)
static char *malloc_root = 0;
#else
#define XOFF2 (XOFF1)
#endif

#ifdef USE_MAGIC
#define BLK_MG(p) (*(unsigned long int *)((p)+(XOFF2*ALIGNMENT)))
#define XOFF3 (XOFF2+1)
#else
#define XOFF3 (XOFF2)
#endif

#define EXTRABYTES (XOFF3*ALIGNMENT)

#ifdef BLK_FL

static void malloc_link(char *p)
{
 BLK_FL(p) = malloc_root;
 BLK_BL(p) = 0;
 if (malloc_root)
  {
#ifdef BLK_MG
    if (BLK_MG(malloc_root) != MMAGIC) malabort("malloc_link: bad magic number\n");
#endif
    BLK_BL(malloc_root) = p;
  }
 malloc_root = p;
}

static void malloc_unlink(char *p)
{
 char *f;
 char *b;

 f = BLK_FL(p);
 b = BLK_BL(p);
 if (f)
  {
#ifdef BLK_MG
    if (BLK_MG(f) != MMAGIC) malabort("malloc_unlink: bad magic number f\n");
#endif
    BLK_BL(f) = b;
  }
 if (b)
  {
#ifdef BLK_MG
    if (BLK_MG(b) != MMAGIC) malabort("malloc_unlink: bad magic number b\n");
#endif
    BLK_FL(b) = f;
  }
 if (! b) malloc_root = f;
 BLK_FL(p) = 0;
 BLK_BL(p) = 0;
}

#else

#define malloc_link(x)
#define malloc_unlink(x)

#endif

#ifdef MALTRACE
static void maltrace_write(const char *s)
{
 static int maltrace_fd = -1;

 if (maltrace_fd < 0)
  { maltrace_fd = open("maltrace",O_WRONLY|O_CREAT|O_TRUNC,0666);
    if (maltrace_fd < 0) return;
  }
 write(maltrace_fd,s,strlen(s));
}
#endif

void *muck_malloc(int nb, UNUSED_ARG(const char *file), UNUSED_ARG(int line))
{
 char *p;
#ifdef MALTRACE
 char buf[128];
#endif

#ifdef MALTRACE
 strcpy(&buf[0],"[malloc ");
 fmt_dec(&buf[strlen(&buf[0])],nb);
 strcpy(&buf[strlen(&buf[0])]," (\"");
 strcpy(&buf[strlen(&buf[0])],file);
 strcpy(&buf[strlen(&buf[0])],"\", line ");
 fmt_dec(&buf[strlen(&buf[0])],line);
 strcpy(&buf[strlen(&buf[0])],") -> ");
 maltrace_write(&buf[0]);
#endif
 p = malloc(nb+EXTRABYTES);
#ifdef RECORD_BUSY
 record_busy((unsigned long int)p);
#endif
#ifdef BLK_NB
 BLK_NB(p) = nb;
#endif
 malloc_link(p);
#ifdef BLK_FN
 BLK_FN(p) = file;
#endif
#ifdef BLK_LN
 BLK_LN(p) = line;
#endif
#ifdef BLK_TM
 BLK_TM(p) = curtm();
#endif
#ifdef BLK_MG
 BLK_MG(p) = MMAGIC;
#endif
 p += EXTRABYTES;
#ifdef DO_FILLS
 fill(p,nb,0);
#endif
#ifdef MALTRACE
 fmt_hex(&buf[0],(unsigned long int)p);
 strcpy(&buf[strlen(&buf[0])],"]\n");
 maltrace_write(&buf[0]);
#endif
 return(p);
}

void *muck_malloc_roundup(int nb, int *sp, UNUSED_ARG(const char *file), UNUSED_ARG(int line))
{
 char *p;
 int realsize;
#ifdef MALTRACE
 char buf[128];
#endif

#ifdef MALTRACE
 strcpy(&buf[0],"[malloc_roundup ");
 fmt_dec(&buf[strlen(&buf[0])],nb);
 strcpy(&buf[strlen(&buf[0])]," (\"");
 strcpy(&buf[strlen(&buf[0])],file);
 strcpy(&buf[strlen(&buf[0])],"\", line ");
 fmt_dec(&buf[strlen(&buf[0])],line);
 strcpy(&buf[strlen(&buf[0])],") -> ");
 maltrace_write(&buf[0]);
#endif
 p = malloc_roundup(nb+EXTRABYTES,&realsize);
 nb = realsize - EXTRABYTES;
 *sp = nb;
#ifdef RECORD_BUSY
 record_busy((unsigned long int)p);
#endif
#ifdef BLK_NB
 BLK_NB(p) = nb;
#endif
 malloc_link(p);
#ifdef BLK_FN
 BLK_FN(p) = file;
#endif
#ifdef BLK_LN
 BLK_LN(p) = line;
#endif
#ifdef BLK_TM
 BLK_TM(p) = curtm();
#endif
#ifdef BLK_MG
 BLK_MG(p) = MMAGIC;
#endif
 p += EXTRABYTES;
#ifdef DO_FILLS
 fill(p,nb,1);
#endif
#ifdef MALTRACE
 fmt_hex(&buf[0],(unsigned long int)p);
 strcpy(&buf[strlen(&buf[0])],"]\n");
 maltrace_write(&buf[0]);
#endif
 return(p);
}

void *muck_realloc(void *old, int nb, UNUSED_ARG(const char *file), UNUSED_ARG(int line))
{
#ifdef BLK_NB
 int onb;
#endif
 char *p;
#ifdef MALTRACE
 char buf[128];
#endif

#ifdef MALTRACE
 strcpy(&buf[0],"[realloc ");
 fmt_hex(&buf[strlen(&buf[0])],(unsigned long int)old);
 strcpy(&buf[strlen(&buf[0])],",");
 fmt_dec(&buf[strlen(&buf[0])],nb);
 strcpy(&buf[strlen(&buf[0])]," (\"");
 strcpy(&buf[strlen(&buf[0])],file);
 strcpy(&buf[strlen(&buf[0])],"\", line ");
 fmt_dec(&buf[strlen(&buf[0])],line);
 strcpy(&buf[strlen(&buf[0])],") -> ");
 maltrace_write(&buf[0]);
#endif
 if (old == 0)
  { p = malloc(nb+EXTRABYTES);
#ifdef RECORD_BUSY
    record_busy((unsigned long int)p);
#endif
#ifdef DO_FILLS
    fill(p+EXTRABYTES,nb,2);
#endif
  }
 else
  { p = ((char *)old) - EXTRABYTES;
#ifdef BLK_MG
    if (BLK_MG(p) != MMAGIC) malabort("realloc: bad magic number\n");
    BLK_MG(p) = ~MMAGIC;
#endif
#ifdef BLK_NB
    onb = BLK_NB(p);
#endif
    malloc_unlink(p);
    p = realloc(p,nb+EXTRABYTES);
     { /* just opening a new scope, not part of control structure */
#if defined(RECORD_BUSY) || defined(DO_FILLS)
       char *oldbeg;
       char *newbeg;
#ifdef DO_FILLS
       char *oldend;
       char *newend;
#endif
       oldbeg = ((char *)old) - EXTRABYTES;
       newbeg = p;
#ifdef DO_FILLS
       oldend = oldbeg + onb + EXTRABYTES;
       newend = p + nb + EXTRABYTES;
#endif
#endif
#ifdef RECORD_BUSY
       if (newbeg != oldbeg)
	{ record_unbusy((unsigned long int)oldbeg);
	  record_busy((unsigned long int)newbeg);
	}
#endif
#ifdef DO_FILLS
/*
	We want to fill (a) any old areas that are not part of the new area
	and (b) if nb>onb, nb-onb bytes at end of new area.

	For (a), there are 13 conceivable cases we have to deal with:

	case A	case B	case C	case D	case E	case F	case G
	xxx....	xxx...	xxx..	xxxxx	xxxxx	xxx..	xxxx
	....yyy	...yyy	..yyy	..yyy	.yyy.	yyyyy	yyyy

	case H	case I	case J	case K	case L	case M
	xxxxx	.xxx.	..xxx	..xxx	...xxx	....xxx
	yyy..	yyyyy	yyyyy	yyy..	yyy...	yyy....

	Some of these can be treated identically.
	ABLM	fill [oldbeg,oldend)
	CD	fill [oldbeg,newbeg)
	E	fill [oldbeg,newbeg) and [newend,oldend)
	FGIJ	fill nothing
	HK	fill [newend,oldend)
*/
       if ((newbeg >= oldend) || (newend <= oldbeg)) /* A, B, L, M */
	{ fill(oldbeg,oldend-oldbeg,3);
	}
       else
	{ if ((newbeg > oldbeg) && (newbeg < oldend)) /* C, D, E */
	   { fill(oldbeg,newbeg-oldbeg,4);
	   }
	  if ((newend > oldbeg) && (newend < oldend)) /* E, H, K */
	   { fill(newend,oldend-newend,5);
	   }
	}
       if (nb > onb) fill(newbeg+onb+EXTRABYTES,nb-onb,6);
#endif
     }
  }
 malloc_link(p);
#ifdef BLK_NB
 BLK_NB(p) = nb;
#endif
#ifdef BLK_FN
 BLK_FN(p) = file;
#endif
#ifdef BLK_LN
 BLK_LN(p) = line;
#endif
#ifdef BLK_TM
 BLK_TM(p) = curtm();
#endif
#ifdef BLK_MG
 BLK_MG(p) = MMAGIC;
#endif
 p += EXTRABYTES;
#ifdef MALTRACE
 fmt_hex(&buf[0],(unsigned long int)p);
 strcpy(&buf[strlen(&buf[0])],"]\n");
 maltrace_write(&buf[0]);
#endif
 return(p);
}

void *muck_calloc(UNUSED_ARG(int siz), UNUSED_ARG(int n), UNUSED_ARG(const char *file), UNUSED_ARG(int line))
{
 malabort("[calloc]\n");
 return(0);
}

void *free_break = 0; /* for debugger patching */

#ifdef MALTRACE
void muck_free(void *obj, const char *file, int line)
#else
void muck_free(void *obj, UNUSED_ARG(const char *file), UNUSED_ARG(int line))
#endif
{
 char *p;
#ifdef MALTRACE
 char buf[128];
#endif

#ifdef MALTRACE
 strcpy(&buf[0],"[free ");
 fmt_hex(&buf[strlen(&buf[0])],(unsigned long int)obj);
 strcpy(&buf[strlen(&buf[0])]," (\"");
 strcpy(&buf[strlen(&buf[0])],file);
 strcpy(&buf[strlen(&buf[0])],"\", line ");
 fmt_dec(&buf[strlen(&buf[0])],line);
 strcpy(&buf[strlen(&buf[0])],")]\n");
 maltrace_write(&buf[0]);
#endif
 if (obj == 0) return;
 if (obj == free_break) kill(getpid(),SIGINT);
 p = ((char *)obj) - EXTRABYTES;
#ifdef BLK_MG
 if (BLK_MG(p) == ~MMAGIC) malabort("free: dup free");
 if (BLK_MG(p) != MMAGIC) malabort("free: bad magic number\n");
 BLK_MG(p) = ~MMAGIC;
#endif
 malloc_unlink(p);
#ifdef DO_FILLS
 fill(p,BLK_NB(p)+EXTRABYTES,7);
#endif
#ifdef RECORD_BUSY
 record_unbusy((unsigned long int)p);
#endif
 free(p);
}

static void cfree_(int i, ...)
{
 va_list ap;
 void *old;
 const char *file;
 int line;

 va_start(ap,i);
 old = va_arg(ap,void *);
 file = va_arg(ap,const char *);
 line = va_arg(ap,int);
 muck_free(old,file,line);
 va_end(ap);
}

void muck_cfree(const void *obj, const char *file, int line)
{
 cfree_(0,obj,file,line);
}

#ifdef RECORD_CALLER

static FILE *mlcfile = 0;

static void mlcprintf(const char *fmt, ...)
{
 va_list ap;

 if (! mlcfile)
  { mlcfile = fopen("mlcfile","w");
    if (mlcfile == 0) return;
  }
 va_start(ap,fmt);
 vfprintf(mlcfile,fmt,ap);
 va_end(ap);
}

static void mlcflush(void)
{
 if (mlcfile) fflush(mlcfile);
}

#endif

#ifdef RECORD_CALLER
static void printbytes(char *bytes, int nb)
{
 int i;
 int c;
 int nbin;
 const char *trailer;

 if (nb > 25)
  { nb = 25;
    trailer = " ...";
  }
 else
  { trailer = "";
  }
 nbin = 0;
 for (i=0;i<nb;i++)
  { c = ((unsigned char *)bytes)[i];
    if ( (c > 126) ||
	 ( (c < 32) &&
	   (c != '\t') &&
	   (c != '\n') &&
	   (c != '\r') ) ) nbin ++;
  }
 if ((nbin > 1) || ((nbin == 1) && (bytes[nb-1] != '\0')))
  { for (i=0;i<nb;i++)
     { mlcprintf(" %02x",((unsigned char *)bytes)[i]);
     }
  }
 else
  { mlcprintf(" ");
    for (i=0;i<nb;i++)
     { c = ((unsigned char *)bytes)[i];
       switch (c)
	{ case '\0': mlcprintf("\\0"); break;
	  case '\r': mlcprintf("\\r"); break;
	  case '\t': mlcprintf("\\t"); break;
	  case '\n': mlcprintf("\\n"); break;
	  default: mlcprintf("%c",c);
	}
     }
  }
 mlcprintf("%s\n",trailer);
}
#endif

void malloc_leakcheck(void)
{
#ifdef RECORD_CALLER
 char *p;
 char *p2;
 int flip;

 mlcprintf("[Unfreed blocks follow]\n");
 p = malloc_root;
 p2 = malloc_root;
 flip = 0;
 while (p)
  { mlcprintf("\"%s\", line %d: 0x%lx: %d byte%s at %.24s\n",
	BLK_FN(p),
	BLK_LN(p),
	(unsigned long int)p,
	BLK_NB(p), (BLK_NB(p)==1)?"":"s",
	ctime(&BLK_TM(p)) );
    printbytes(p+EXTRABYTES,BLK_NB(p));
    p = BLK_FL(p);
    if (flip)
     { p2 = BLK_FL(p2);
     }
    else
     { if (p == p2)
	{ mlcprintf("BLK_FL loop\n");
	  break;
	}
     }
    flip = ! flip;
  }
 mlcprintf("[Done]\n");
 mlcflush();
#endif
}