/*
 * alloc.c
 *
 * x-kernel v3.3
 *
 * Copyright (c) 1996,1993,1991,1990  Arizona Board of Regents
 *
 * $Revision: 1.5 $
 * $Date: 1996/06/19 16:23:29 $
 */

#include "platform.h"
#include "trace.h"
#include "xk_debug.h"
#include "x_util.h"
#include "x_libc.h"
#include "event.h"

int	tracemalloc;

/* #define MALLOC_DEBUG  */

#ifdef MALLOC_DEBUG

static int malloc_cnt=0;
static int malloced=0;
static int free_cnt=0;
static int msgdbgMin=255;
static int msgdbgMinCnt=0;
static int msgdbgMinMalloced=0;

struct malldbgst {
  struct malldbgst *next;
  long	who;
  int   mallocCnt;
  int   freeCnt;
  int   malloced;
};

struct top10st {
  struct top10st *next;
  int 	val;
  struct malldbgst *mp;
} Top10[20], *low10;

struct malldbgst *mallArray[4096];

#endif

#ifdef XK_DEBUG_MALLOC

extern int	qsort( char *, int, int, int (*)() );


#define I_MALLOC	i_malloc
#define I_FREE		i_free
#define MALLOC_SCOPE	static


static	char *	I_MALLOC( unsigned );
static  void	I_FREE( char * );
static  int	compareblocks( long **, long ** );
static  void	dumpBlocks( Event, void * );
static	void	fillPCs( long * );
static  void 	lockInit( void );
static  void	xkBreakpoint();

#define verboseDump	TR_DETAILED

#define MALLOC_EXTRAS 	3	/* 2 tags + block index */
#define MALLOC_NPCS	5

#define MALLOC_STUFF	(MALLOC_NPCS + MALLOC_EXTRAS)

/*
 * The number of malloc blocks to store
 */
#define MAXBLOCKS		8192
#define FIRST_MALLOC_TAG	0x441199ee
#define SECOND_MALLOC_TAG	0x55ff0011

#define DUMP_BLOCK_INTERVAL	5 * 1000 * 1000  /* 5 seconds */
#define OCCURANCE_THRESHOLD	10


long		*xkBackTraceArr;

static long 	*blocks[MAXBLOCKS];
static int 	nextblock = 1;
static int	numMallocs = 0;
static int	numFrees = 0;
static struct mutex_t	malloc_mutex;
static int		lockInitialized;

char *
xMalloc(num)
    unsigned int num;
{
    register long *mp;
    int startblock = nextblock;

    if( !lockInitialized ) {
    	lockInit();
    }    
    mutex_lock( &malloc_mutex );
    numMallocs++;
    Trace1(malloc, TR_FUNCTIONAL_TRACE, "xMalloc(%d) called", num);
    mp = (long *) I_MALLOC (num + MALLOC_STUFF * sizeof(long));
    xTrace1(malloc, TR_DETAILED, "xk internal malloc returns %x", mp);
    while (blocks[nextblock]) {
        if (++nextblock >= MAXBLOCKS) nextblock = 1;
	if (nextblock == startblock) {
	    nextblock = 0;
	    xError("malloc debugging block array overflow");
	    break;
	}
    }
    xTrace1(malloc, TR_DETAILED, "xMalloc adding block to index %d",
            nextblock);
    blocks[nextblock] = mp;

    *mp++ = FIRST_MALLOC_TAG;
    *mp++ = SECOND_MALLOC_TAG;

    *mp++ = nextblock;
    /*
     * Allocators PCs
     */
    fillPCs(mp);
    mp += MALLOC_NPCS;

    xAssert( ! ( (int)mp % 4 ) );
    xTrace1(malloc, TR_DETAILED, "xMalloc returns %x", mp);
    mutex_unlock(&malloc_mutex);
    return (char *)mp;
}


static void
tagError(void)
{
    long	pcArray[ MALLOC_NPCS ];
    xError("xFree tag error");
    xError("free stack");
    tracemalloc = TR_FULL_TRACE;
    fillPCs(pcArray);
    xAssert(0);
}


void
xFree(p)
    char *p;
{
    long	*baseptr = (long *)p - MALLOC_STUFF;
    long	*lmp;
    long 	block;

    mutex_lock(&malloc_mutex);
    numFrees++;
    if ( baseptr[0] != FIRST_MALLOC_TAG || baseptr[1] != SECOND_MALLOC_TAG ) {
	tagError();
    }
    lmp = baseptr + 2;
    block = *lmp++;
    xAssert( blocks[block] );
    blocks[block] = 0;
    mutex_unlock(&malloc_mutex);
    I_FREE((char *)baseptr);
}


static int
compareblocks(ap, bp)
    long **ap, **bp;
{
    long *a = *ap, *b = *bp;
    int i;
    if (a == b) return 0;
    if (!a) return  1;
    if (!b) return -1;
    
    a += MALLOC_EXTRAS;
    b += MALLOC_EXTRAS;
    for (i = 0; i < MALLOC_NPCS; i++) {
	if (*a < *b) return -1;
	if (*a > *b) return 1;
	a++; b++;
    }
    return 0;
}


static void displayLine( long **b, int i )
{
    int	k;

    if ( b[i] ) {
	printf("%d:\t", i);
	for ( k=0; k < MALLOC_NPCS; k++ ) {
	    printf("%x ", (b[i][MALLOC_EXTRAS + k]));
	}
	if ( b[i][0] != FIRST_MALLOC_TAG || b[i][1] != SECOND_MALLOC_TAG ) {
	    printf("tag violation (%x %x)", b[i][0], b[i][1]);
	}
	printf("\n");
    }
}


static void dumpBlocks(Event ev, void *arg)
{
    int i, j, k;

    long 		last[MALLOC_NPCS], *b;
    static long	*	lblocks[MAXBLOCKS];

    xError("\n\n\nMalloc trace\n");
    mutex_lock(&malloc_mutex);
    bcopy((char *)blocks, (char *)lblocks, sizeof(blocks));
    xIfTrace(malloc, verboseDump) {	
	for ( i=0; i < MAXBLOCKS; i++, j++ ) {
	    displayLine(blocks, i);
	}
	xError("\n\n");
    }
    qsort((char *)lblocks, MAXBLOCKS, sizeof(long *), compareblocks);
    for (i = 0, j = 0; i < MAXBLOCKS; i++, j++) {
	b = lblocks[i];
	xIfTrace(malloc, verboseDump) {	
	    displayLine(lblocks, i);
	}
	if ( ! b || bcmp((char *)(b + MALLOC_EXTRAS), (char *)last,
			 MALLOC_NPCS * sizeof(long)) ) {
	    /* 
	     * Found a different block
	     */
	    if ( j >= OCCURANCE_THRESHOLD ) {
		static char	buf[80];
		static char	smallBuf[10];
		
		sprintf(buf, "%d at ", j);
		for (k = 0; k < MALLOC_NPCS; k++) {
		    sprintf(smallBuf, "%x ", last[k]);
		    strcat(buf, smallBuf);
		}
		xTrace1(malloc, TR_ALWAYS, "%s", buf);
	    }
	    if (b) bcopy((char *)(b + MALLOC_EXTRAS), (char *)last,
			 MALLOC_NPCS * sizeof(long));
	    j = 0;
	}
	if (!b) break;
    }
    xTrace2(malloc, TR_ALWAYS, "%d mallocs, %d frees", numMallocs, numFrees);
    xTrace1(malloc, TR_ALWAYS, "%d malloc debugging slots occupied", i);

    if ( arg ) {
	dumpBlocks(0, 0);
    }
    mutex_unlock( &malloc_mutex );
    evDetach( evSchedule(dumpBlocks, 0, DUMP_BLOCK_INTERVAL) );
}



static void xkBreakpoint(void)
{
}


static void
fillPCs(long *arr)
{
    int	i;

    xkBackTraceArr = arr;
    arr[0] = 0;
    xkBreakpoint();
    /* 
     * GDB should have inserted the backtrace at this point
     */
    xAssert( arr[0] );
    xIfTrace( malloc, TR_DETAILED ) {
	static char	buf[80];
	static char	smallBuf[10];
	
	buf[0] = 0;
	for ( i=0; i < MALLOC_NPCS; i++ ) {
	    sprintf(smallBuf, "%x ", arr[i]);
	    strcat(buf, smallBuf);
	}
	xTrace1(malloc, TR_ALWAYS, "%s", buf);
    }
}


static void
lockInit(void)
{
    lockInitialized = 1;
    mutex_init( &malloc_mutex, USYNC_THREAD, 0 );  
}

#else    XK_DEBUG_MALLOC

#define MALLOC_SCOPE	/* exported */
#define I_MALLOC	xMalloc
#define I_FREE		xFree
#define I_REALLOC       xRealloc

#endif	XK_DEBUG_MALLOC




/* 
 * Careful -- allocations can happen before xMallocInit is called.
 */
void
xMallocInit(void)
{
    xTrace0(malloc, TR_GROSS_EVENTS, "xkernel malloc init");
#ifdef XK_DEBUG_MALLOC
    if ( ! lockInitialized ) {
        lockInit();
    }
    evDetach( evSchedule(dumpBlocks, 0, DUMP_BLOCK_INTERVAL) );
#endif    
}


/* 
 * The actual allocation/freeing routines.  These are either called
 * directly as xMalloc / xFree or are called by the wrapper debugging
 * functions above.
 */

MALLOC_SCOPE
char *
I_MALLOC( unsigned s )
{
    char *p;
#ifdef MALLOC_DEBUG
    register unsigned long ra asm("26");
    struct malldbgst *mp;
    int k;
#endif

    xTrace1(malloc, TR_EVENTS, "malloc %u bytes", s);
    xIfTrace(malloc, TR_MAJOR_EVENTS)
      { if (s > 4096 && tracemalloc < TR_EVENTS)
	  printf("malloc %u bytes", s);
      }
    if ( p = (char *)malloc(s) ) {
#ifdef XK_MEMORY_THROTTLE
    memory_unused -= s;
    xAssert((memory_unused > 0));
    xAssert((((int *)p)[-1]) == s);
    xIfTrace(memoryusage, TR_EVENTS) {
      if (!(report_count++ % XK_MEMORY_REPORT_INTERVAL))
	printf("malloc: memory available %d\n", memory_unused);
    }
#endif XK_MEMORY_THROTTLE

#ifdef MALLOC_DEBUG
    malloc_cnt++;
    malloced += s;
    if (s > msgdbgMin) {
      k = ra >> 2;
      mp = mallArray[k%4096];
      while (mp != NULL  &&  mp->who != ra)
        mp = mp->next;
      if (mp == NULL) {
        mp = (struct malldbgst *) malloc(sizeof(struct malldbgst));
        mp->who = ra;
        mp->mallocCnt = 0;
        mp->freeCnt = 0;
        mp->malloced = 0;
        mp->next = mallArray[k%4096];
        mallArray[k%4096] = mp;
      }
      mp->malloced += s;
      mp->mallocCnt++;
    }
    else
      msgdbgMinMalloced += s, msgdbgMinCnt++;
#endif

	return p;
  }
    Kabort("malloc failed");
    return 0;
}

#ifdef MALLOC_DEBUG
int printMallocDbg()
{
  struct malldbgst *mp;
  struct top10st *tp, *tp2;
  int k;

  printf("malloc_cnt: %d, malloced: %d, msgdbgMinCnt: %d, msgdbgMinMalloced: %d\n",
         malloc_cnt, malloced, msgdbgMinCnt, msgdbgMinMalloced);

  for (k=0; k<19; k++)
    Top10[k].next = &Top10[k+1], Top10[k].mp = NULL;
  Top10[19].next = NULL;
  Top10[19].mp = (struct malldbgst *) malloc(sizeof(struct malldbgst));
  Top10[19].mp->malloced = 900000000;
  low10 = &Top10[0];

  for (k=0; k<4096; k++)
    while ((mp=mallArray[k]) != NULL) {
      if (low10->mp == NULL  ||  mp->malloced > low10->mp->malloced) {
        tp = low10;
        while (tp->next->mp == NULL  ||  mp->malloced > tp->next->mp->malloced)
          tp = tp->next;
        if (tp->mp == NULL)
          tp->mp = mp;
        else {
          low10->mp = mp;
          tp2 = tp->next;
          tp->next = low10;
          low10 = low10->next;
          tp->next->next = tp2;
        }
      }
      mp = mp->next;
    }
  for (tp = low10; tp != NULL; tp=tp->next) {
    if (tp->mp == NULL)
      continue;
    printf("%lx  mallocCnt: %d, malloced: %d\n", tp->mp->who, 
           tp->mp->mallocCnt, tp->mp->malloced);
  }
  return 0;
}
#endif

MALLOC_SCOPE
void
I_FREE( p )
    char	*p;
{
#ifdef MALLOC_DEBUG
    register unsigned long ra asm("26");
    int k;
    struct malldbgst *mp;

    free_cnt++;
/*    k = ((long) p)>>2;
    mp = mallArray[k%4096];
*/
#endif

    free(p);
}

MALLOC_SCOPE
char *
I_REALLOC( p , newsize )
    char *p;
    unsigned int newsize;
{
  char *q;

  q = (char *)realloc(p, newsize);
  if ( newsize && q == NULL )
    Kabort("malloc failed");
  return q;
}

extern int TrafficConvCnt;
/* extern int BtcpSessionCnt; -- only available if linked with btcp_x.c */

#ifdef XMEMTRACK

#define TRACK_SIZE 128

struct trackSt {
  long alloc;
  long allocCnt;
  long free;
  long freeCnt;
  char name[32];
} TrackArray[TRACK_SIZE];

static int TrackArrayN=1;

int TrackGetId(char *name)
{
  if (TrackArrayN < (TRACK_SIZE-1)) {
    if (strlen(name) > 30)
      strncpy(TrackArray[TrackArrayN].name, name, 30);
    else
      strcpy(TrackArray[TrackArrayN].name, name);
    return TrackArrayN++;
  }
  else {
    strcpy(TrackArray[TrackArrayN].name, "Last Track ID");
    return TrackArrayN;
  }
}

int TrackPrint()
{
  int k, used=0;

  for (k=0; k<TrackArrayN; k++) {
    printf("%3d  %14s  alloc:%5dK, aCnt:%3dK, free:%5dK, fCnt:%3dK (%5dK)\n",
           k, TrackArray[k].name, TrackArray[k].alloc/1024, 
	   TrackArray[k].allocCnt/1000,
	   TrackArray[k].free/1024, TrackArray[k].freeCnt/1000,
	   (TrackArray[k].alloc - TrackArray[k].free)/1024);
    used += TrackArray[k].alloc - TrackArray[k].free;
  }
  /* printf("Total Alloc: %dK, TrafficConvCnt: %d, BtcpSessionCnt: %d\n", 
         used/1024, TrafficConvCnt, BtcpSessionCnt); */
  return 0;
}

char *xMallocTrack(unsigned s, int id)
{
  TrackArray[id].alloc += s;
  TrackArray[id].allocCnt++;
  return xMalloc(s);
}

void xFreeTrack(char *p, unsigned len, int id)
{
  TrackArray[id].free += len;
  TrackArray[id].freeCnt++;
  xFree(p);
}

char *xMallocZeroTrack(unsigned s, int id)
{
  char *cp;

  TrackArray[id].alloc += s;
  TrackArray[id].allocCnt++;
  cp =  xMalloc(s);
  bzero(cp, s);
  return cp;
}

#endif