/* mad.c memory allocate debugger
   Copyright (C) 1996-2000 Paul Sheer

   This program 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 of the License, or
   (at your option) any later version.

   This program 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 program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/********************************************************************/
/* There is a mad.c and mad.h file that comes with other programs.  */
/* This is not the same mad at all. Consider this to be Next        */
/* Generation MAD. It is based on the debauch package.              */
/********************************************************************/

#include "mad.h"

#undef malloc
#undef calloc
#undef strdup
#undef free
#undef realloc
#undef exit

int option_debug_malloc = 0;

#ifndef DEBUG_MALLOC

/* put these here so you don't have to recompiled all sources to turn off mem debugging */

void mad_exit (int status)
{
    exit (status);
}

void *mad_malloc (unsigned desiredsize)
{
    return (void *) malloc (desiredsize);
}

char *mad_strdup (char *s)
{
    char *p;
    p = mad_malloc (strlen (s) + 1);
    strcpy (p, s);
    return p;
}

void mad_free (char *p)
{
    free (p);
}

void *mad_realloc (char *old, unsigned desiredsize)
{
    return (void *) realloc (old, desiredsize);
}

void *mad_calloc (unsigned num, unsigned size)
{
    return (void *) calloc (num, size);
}

#else

/* include this file with your other sources to get a complete memory leak
    reportage with a stack trace for each leak on exit() */

/* taken from mad and put into one file by Paul Sheer <psheer /AT/ icon.co.za> */

/*
 * $XConsortium: fmalloc.c /main/7 1996/11/24 17:42:06 rws $
 * $XFree86: xc/util/memleak/fmalloc.c,v 3.3 1996/12/31 05:02:25 dawes Exp $
 *
Copyright (c) 1992  X Consortium

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Except as contained in this notice, the name of the X Consortium shall not be
used in advertising or otherwise to promote the sale, use or other dealings
in this Software without prior written authorization from the X Consortium.
 *
 * Author:  Keith Packard, MIT X Consortium
 */


/*
 * Leak tracing allocator -- using C lib malloc/free, tracks
 * all allocations.  When requested, performs a garbage-collection
 * style mark/sweep on static memory (data and stack), locating
 * objects referenced therein.  Recursively marks objects.
 * Sweeps through all allocations, warning of possible violations
 * (unreferenced allocated, referenced freed etc).
 */

#include    <signal.h>

/* interface */
void mad_start (void);
void check_memory (void);
void validate_memory (void);
void final_memory_check (void);

void exit (int status);
void *malloc (unsigned desiredsize);
void *calloc (unsigned num, unsigned size);
void *realloc (void *old, unsigned desiredsize);
void free (void *p);


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

/********* begin getretlinux.c **********************/

/*
 * modified from getreti386.c
 *
 * Copyright (c) 1995 Jeffrey Hsu
 * Copyright (c) 1999 Jon A. Christopher
 */

#define get_current_fp(first_local)	((unsigned)&(first_local) + 4)
#define prev_fp_from_fp(fp)		*((unsigned *) fp)
#define ret_addr_from_fp(fp)		*((unsigned *) (fp+4))

static void get_stack_trace (unsigned long *results, int max)
{

    int first_local;
    unsigned long fp, ret_addr;

    fp = get_current_fp (first_local);

    while (fp != 0 && max--) {
	ret_addr = ret_addr_from_fp (fp);
	*results++ = ret_addr;
	fp = prev_fp_from_fp (fp);
    }

}

/********* end getretlinux.c **********************/




/********* begin stackbottom.c **********************/


/*
 * cut and paste from gc 4.4 by Hans-J. Boehm and Alan J. Demers
 *
 * Cutter and Paster:  Jeffrey Hsu
 */

/* $XFree86: xc/util/memleak/stackbottom.c,v 3.1 1996/12/31 05:02:27 dawes Exp $ */

typedef char *ptr_t;		/* A generic pointer to which we can add        */
			/* byte displacements.                          */
			/* Preferably identical to caddr_t, if it       */
			/* exists.                                      */

#ifndef bool
typedef int bool;
#endif

#define VOLATILE volatile

#ifndef STACK_GROWS_UP
#define STACK_GROWS_DOWN
#endif

typedef unsigned long word;

#define TRUE 1

#if defined(__alpha) || defined(__alpha__)
extern __start
#define HEURISTIC2_LIMIT ((ptr_t)((word)(&__start) & ~(getpagesize()-1)))
#endif
void GC_noop ()
{
}

  /* Some tools to implement HEURISTIC2 */
#define MIN_PAGE_SIZE 256	/* Smallest conceivable page size, bytes */
#include <setjmp.h>
static jmp_buf GC_jmp_buf;

static void GC_fault_handler (int sig)
{
    longjmp (GC_jmp_buf, 1);
}

#ifdef __STDC__
typedef void (*handler) (int);
#else
typedef void (*handler) ();
#endif

    /* Return the first nonaddressible location > p (up) or     */
    /* the smallest location q s.t. [q,p] is addressible (!up). */
static ptr_t GC_find_limit (ptr_t p, bool up)
{
    static VOLATILE ptr_t result;
    /* Needs to be static, since otherwise it may not be    */
    /* preserved across the longjmp.  Can safely be         */
    /* static since it's only called once, with the         */
    /* allocation lock held.                                */

    static handler old_segv_handler, old_bus_handler;
    /* See above for static declaration.                    */

    old_segv_handler = signal (SIGSEGV, GC_fault_handler);
#ifdef SIGBUS
    old_bus_handler = signal (SIGBUS, GC_fault_handler);
#endif
    if (setjmp (GC_jmp_buf) == 0) {
	result = (ptr_t) (((word) (p))
			  & ~(MIN_PAGE_SIZE - 1));
	for (;;) {
	    if (up) {
		result += MIN_PAGE_SIZE;
	    } else {
		result -= MIN_PAGE_SIZE;
	    }
	    GC_noop (*result);
	}
    }
    (void) signal (SIGSEGV, old_segv_handler);
#ifdef SIGBUS
    (void) signal (SIGBUS, old_bus_handler);
#endif
    if (!up) {
	result += MIN_PAGE_SIZE;
    }
    return (result);
}

static ptr_t GC_get_stack_base (void)
{
    word dummy;
    static ptr_t result;

    if (!result) {

#ifdef STACK_GROWS_DOWN
	result = GC_find_limit ((ptr_t) (&dummy), TRUE);
#ifdef HEURISTIC2_LIMIT
	if (result > HEURISTIC2_LIMIT && (ptr_t) (&dummy) < HEURISTIC2_LIMIT) {
	    result = HEURISTIC2_LIMIT;
	}
#endif
#else
	result = GC_find_limit ((ptr_t) (&dummy), FALSE);
#ifdef HEURISTIC2_LIMIT
	if (result < HEURISTIC2_LIMIT && (ptr_t) (&dummy) > HEURISTIC2_LIMIT) {
	    result = HEURISTIC2_LIMIT;
	}
#endif
#endif
    }

    return (result);
}


/********* end stackbottom.c **********************/


/********* begin fmalloc.c **********************/


extern char **environ;
extern int etext;

#define TOP_OF_STACK	GC_get_stack_base()
#define BOTTOM_OF_DATA	&etext
#define HAS_GET_RETURN_ADDRESS

#ifndef FALSE
#define FALSE 0
#endif
#ifndef TRUE
#define TRUE 1
#endif

#if 1
#define NO_ATEXIT
#else
#ifdef X_NOT_POSIX
#define NO_ATEXIT
#endif
#endif

typedef unsigned long mem;

#ifdef HAS_GET_RETURN_ADDRESS
/* was 16, which is too low for debugging complicated libraries */
#define MAX_RETURN_STACK    32
#endif

#define MAX_FREED_MEMORY    (16*1024*1024)

#define ACTIVE_HEAD_MAGIC   0xff1111ff
#define ACTIVE_TAIL_MAGIC   0xee2222ee
#define ACTIVE_DATA_MAGIC   0xdd3333dd
#define FREED_HEAD_MAGIC    0xcc4444cc
#define FREED_TAIL_MAGIC    0xbb5555bb
#define FREED_DATA_MAGIC    0xcc6666cc

/*
 * the marked fields in each head have two bits - one indicating
 * references to the head of the block, and one indicating references
 * to the middle of the block
 */
#define UNREFERENCED	    0
#define REFERENCED_HEAD	    1
#define REFERENCED_MIDDLE   2

typedef struct _head {
    struct _head *left, *right;
    struct _head *next;
    int balance;
#ifdef HAS_GET_RETURN_ADDRESS
    mem return_stack[MAX_RETURN_STACK];
#endif
    mem *from;
    unsigned long alloc_time;
    unsigned long free_time;
    int size;
    int desiredsize;
    int actual_size;
    int marked;
    int head_magic;
} HeadRec, *HeadPtr;

typedef struct _tail {
    int tail_magic;
#if defined(__alpha) || defined(__alpha__)
    int tail_pad;
#endif
} TailRec, *TailPtr;

#define header(p)	((HeadPtr) (((char *) (p)) - sizeof (HeadRec)))
#define data_for_head(h)	((mem *) ((h) + 1))
#define tailer(p)	((TailPtr) (((char *) (p)) + header(p)->size))
#define tail_for_head(h)	(tailer(data_for_head(h)))
#define round_size	(sizeof (mem))
#define round_up(s)	(((s) + round_size - 1) & ~(round_size - 1))
#define total_size(s)	((s) + sizeof (HeadRec) + sizeof (TailRec))
#define check_init()	if (!end_of_static_memory) end_of_static_memory = sbrk(0)
#define block_contains(h,p)  (data_for_head(h) <= (p) && (p) < (mem *) tail_for_head(h))

typedef HeadRec tree;
typedef mem *tree_data;

#define COMPARE_ADDR(a,b,op)	(((unsigned) (a)) op ((unsigned) (b)))
#define COMPARE(a,b,op,s)	((!s) ? \
			 COMPARE_ADDR(a,b,op) :\
			(((a)->actual_size op (b)->actual_size) || \
			 ((a)->actual_size == (b)->actual_size && \
			  COMPARE_ADDR(a,b,op))))


#define LESS_THAN(a,b,s)    COMPARE(a,b,<,s)
#define GREATER_THAN(a,b,s) COMPARE(a,b,>,s)

#define SEARCH(top,result,p) for (result = top; result;) {\
    if ((mem *) (p) < data_for_head(result)) \
	result = result->left; \
    else if ((mem *) tail_for_head(result) < (mem *) (p)) \
	result = result->right; \
    else \
	break; \
}


static tree *active_memory, *freed_memory, *dead_memory;

static mem *end_of_static_memory;
static mem *highest_allocated_memory;

static int freed_memory_total;
static int freed_memory_count;
static int active_memory_total;
static int active_memory_count;
static int dead_memory_total;

static int mad_warn_middle_pointers = 0;
static int mad_warn_unreferenced = 0;
static int mad_warn_referenced = 0;
static int mad_check_always = 0;

unsigned long mad_alloc_breakpoint = ~0;
unsigned long mad_free_breakpoint = ~0;
unsigned long mad_error_time;
unsigned long mad_time;

static void mark_active_block ();

static int tree_insert (tree ** treep, tree * new, int by_size);
static int tree_delete (tree ** treep, tree * old, int by_size);

static int inited = FALSE;

void mad_start (void)
/* client programs may call this routine to set error reporting to ignore
   memory allocated or freed before the current time */
{
    mad_error_time = mad_time;
}

static int output_file = 0;

static void output (char *fmt, ...);

static void do_init (void)
{
    char *a;

    write (2, "initialising MAD\n", 17);
    inited = TRUE;

    output_file = creat ("mad.out", 0600);
    if (output_file < 0) {
	perror ("failed to open mad.out for memory debugging\n");
	abort ();
    }

    a = (char *) getenv ("DEBAUCH_WARN_REFERENCED");
    if (a)
	mad_warn_referenced = (int) atoi (a);

    a = (char *) getenv ("DEBAUCH_ERROR_TIME");
    if (a)
	mad_error_time = (long) atol (a);

    a = (char *) getenv ("DEBAUCH_WARN_UNREFERENCED");
    if (a)
	mad_warn_unreferenced = (int) atoi (a);

    a = (char *) getenv ("DEBAUCH_WARN_MIDDLE_POINTERS");
    if (a)
	mad_warn_middle_pointers = (long) atoi (a);

    a = (char *) getenv ("DEBAUCH_ALLOC_BREAKPOINT");
    if (a)
	mad_alloc_breakpoint = (long) atol (a);

    a = (char *) getenv ("DEBAUCH_FREE_BREAKPOINT");
    if (a)
	mad_free_breakpoint = (long) atol (a);

    a = (char *) getenv ("DEBAUCH_CHECK_ALWAYS");
    if (a)
	mad_check_always = (int) atoi (a);

    if (option_debug_malloc >= 2)
	mad_check_always = 1;

#ifndef NO_ATEXIT
    atexit (final_memory_check);
#endif
}


#ifdef HAS_GET_RETURN_ADDRESS
static void print_return_stack (char *m, mem * ra)
{
    int i;

    output ("   %s:", m);
    for (i = 0; i < MAX_RETURN_STACK && ra[i]; i++)
	output (" 0x%lx", ra[i]);
    output ("\n");
}
#endif

static void mem_error (char *s, HeadPtr h, int ourRet)
{
#if 0
    mem *ra;
    int i;
#endif

    /* Silence messages from memory allocated or freed before
       mad_error_time */
    if (mad_error_time) {
	if (h) {
	    if (h->alloc_time && h->alloc_time < mad_error_time)
		return;
	    if (h->free_time && h->free_time < mad_error_time)
		return;
	} else {
	    if (mad_time < mad_error_time)
		return;
	}
    }

    if (h) {
	output ("%s 0x%08lx, size %d (from 0x%lx) AllocTime: %ld FreeTime: %ld\t",
		s, (unsigned long) data_for_head (h), h->desiredsize, (unsigned long) h->from,
		h->alloc_time, h->free_time);
#ifdef HAS_GET_RETURN_ADDRESS
	print_return_stack ("Saved return stack", h->return_stack);
#endif
	if (!ourRet)
	    output ("\n");
    } else
	output ("%s\n", s);
#ifdef HAS_GET_RETURN_ADDRESS
    if (ourRet) {
	mem return_stack[MAX_RETURN_STACK];
	memset (return_stack, 0, sizeof (return_stack));
	if (h)
	    output ("%s 0x%08lx; now at stack address:\t", s, data_for_head (h));
	else
	    output ("%s 0x%08lx; now at stack address:\t", s, 0);
	get_stack_trace (return_stack, MAX_RETURN_STACK);
	print_return_stack ("Current return stack", return_stack);
	output ("\n");
#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
	(void) mad_exit (1);
#else
	exit (1);
#endif
    }
#endif
}

static void mark_memory_region (mem * low, mem * high)
{
    mem **start = (mem **) low, **end = (mem **) high;
    mem *p;

    while (start < end) {
	p = *start;
	if (end_of_static_memory <= p && p < highest_allocated_memory)
	    mark_active_block (p, (mem *) start);
	start++;
    }
}

static void mark_active_block (mem * p, mem * from)
{
    HeadPtr h;
    int marked;
    int oldMarked;

    SEARCH (active_memory, h, p)
	if (h) {
	marked = REFERENCED_HEAD;
	if (p != data_for_head (h))
	    marked = REFERENCED_MIDDLE;
	oldMarked = h->marked;
	if (!(oldMarked & marked)) {
	    h->marked |= marked;
	    h->from = from;
	    if (!oldMarked)
		mark_memory_region (data_for_head (h), (mem *) tail_for_head (h));
	}
	return;
    }
    SEARCH (freed_memory, h, p)
	if (h) {
	marked = REFERENCED_HEAD;
	if (p != data_for_head (h))
	    marked = REFERENCED_MIDDLE;
	if (!(h->marked & marked)) {
	    h->marked |= marked;
	    h->from = from;
	}
	return;
    }
}

static void clear_tree (tree * t)
{
    if (!t)
	return;
    clear_tree (t->left);
    t->marked = 0;
    t->from = 0;
    clear_tree (t->right);
}

static void sweep_active_tree (tree * t)
{
    if (!t)
	return;
    sweep_active_tree (t->left);
    if (!t->marked) {
	if (mad_warn_unreferenced)
	    mem_error ("Unreferenced allocated", t, FALSE);
    } else if (!(t->marked & REFERENCED_HEAD))
	mem_error ("Referenced allocated middle", t, FALSE);
    sweep_active_tree (t->right);
}

static void report_leaks_in_tree (tree * t)
{
    if (!t)
	return;
    report_leaks_in_tree (t->left);
    mem_error ("Leaked Memory", t, FALSE);
    report_leaks_in_tree (t->right);
}

/*
 * run a thread through the tree at the same time
 * - the thread runs 
 *
 * root -> left_child ... -> right_child ... -> null
 */

static tree *sweep_freed_tree (tree * t)
{
    tree *left_last, *right_last;

    if (!t)
	return 0;

    left_last = sweep_freed_tree (t->left);
    if (t->marked) {
	if (t->marked & REFERENCED_HEAD) {
	    if (mad_warn_referenced)
		mem_error ("Referenced freed base", t, FALSE);
	} else if (mad_warn_middle_pointers)
	    mem_error ("Referenced freed middle", t, FALSE);
    }
    right_last = sweep_freed_tree (t->right);

    if (t->left)
	t->next = t->left;
    else
	t->next = t->right;
    if (left_last)
	left_last->next = t->right;
    if (!right_last)
	right_last = left_last;
    if (!right_last)
	right_last = t;
    return right_last;
}

static void sweep_freed_memory (void)
{
    tree *t, *n;
    int count, shouldCount;

    (void) sweep_freed_tree (freed_memory);
    count = 0;
    shouldCount = freed_memory_count;
    for (t = freed_memory; t; t = n) {
	n = t->next;
	count++;
	if (!t->marked) {
	    (void) tree_delete (&freed_memory, t, FALSE);
	    freed_memory_total -= t->desiredsize;
	    freed_memory_count--;
	    tree_insert (&dead_memory, t, TRUE);
	}
    }
    if (count != shouldCount)
	abort ();
}

static int validate_tree (tree * head, mem head_magic, mem tail_magic, mem body_magic, char *mesg,
			  int check_only)
{
    TailPtr tail;
    mem *p;
    int i, r = 0;

    if (!head)
	return r;
    r |= validate_tree (head->left, head_magic, tail_magic, body_magic, mesg, check_only);
    tail = tail_for_head (head);
    if (head->head_magic != head_magic) {
	if (!check_only)
	    mem_error (mesg, head, FALSE);
	r = 1;
    }
    if (tail->tail_magic != tail_magic) {
	if (!check_only)
	    mem_error (mesg, head, FALSE);
	r = 1;
    }
    if (body_magic) {
	i = head->size / sizeof (mem);
	p = data_for_head (head);
	while (i--) {
	    if (*p++ != body_magic) {
		if (!check_only)
		    mem_error (mesg, head, FALSE);
		r = 1;
	    }
	}
    }
    r |= validate_tree (head->right, head_magic, tail_magic, body_magic, mesg, check_only);
    return r;
}

static int validate_active_memory (int check_only)
{
    return validate_tree (active_memory, ACTIVE_HEAD_MAGIC, ACTIVE_TAIL_MAGIC,
			  0, "Store outside of active memory", check_only);
}

static int validate_freed_memory (int check_only)
{
    return validate_tree (freed_memory, FREED_HEAD_MAGIC, FREED_TAIL_MAGIC,
			  FREED_DATA_MAGIC, "Store into freed memory", check_only);
}

static void add_active_block (HeadPtr h)
{
    TailPtr t = tail_for_head (h);
    mem *p;
    int i;

    tree_insert (&active_memory, h, FALSE);
    if ((mem *) t > highest_allocated_memory)
	highest_allocated_memory = (mem *) t;

    /*
     * Breakpoint position - assign mad_alloc_breakpoint with
     * debugger and set a breakpoint in the conditional clause below
     */
    if (mad_time == mad_alloc_breakpoint)
	h->head_magic = ACTIVE_HEAD_MAGIC;	/* set breakpoint here */

    h->alloc_time = mad_time++;

    h->head_magic = ACTIVE_HEAD_MAGIC;
    t->tail_magic = ACTIVE_TAIL_MAGIC;
    i = h->size / sizeof (mem);
    p = data_for_head (h);
    while (i--)
	*p++ = ACTIVE_DATA_MAGIC;
    active_memory_total += h->desiredsize;
    active_memory_count++;
}

static void remove_active_block (HeadPtr h)
{
    active_memory_total -= h->desiredsize;
    active_memory_count--;
    tree_delete (&active_memory, h, FALSE);
}

static void add_freed_block (HeadPtr h)
{
    TailPtr t = tail_for_head (h);
    int i;
    mem *p;

    tree_insert (&freed_memory, h, FALSE);

    /*
     * Breakpoint position - assign mad_free_breakpoint with
     * debugger and set a breakpoint in the conditional clause below
     */
    if (mad_time == mad_free_breakpoint)
	h->head_magic = FREED_HEAD_MAGIC;	/* set breakpoint here */

    h->free_time = mad_time++;

    h->head_magic = FREED_HEAD_MAGIC;
    t->tail_magic = FREED_TAIL_MAGIC;
    i = h->size / sizeof (mem);
    p = data_for_head (h);
    while (i--)
	*p++ = FREED_DATA_MAGIC;
    freed_memory_total += h->desiredsize;
    freed_memory_count++;
    /* GC if we've got piles of unused memory */
    if (freed_memory_total - dead_memory_total >= MAX_FREED_MEMORY)
	validate_memory ();
}

/*
 * Entry points:
 *
 *  check_memory ()		--	Verifies heap
 *  final_memory_check ()	--	Verifies heap, reporting any leaks
 *  malloc (size)		--	Allocates memory
 *  free (old)			--	Deallocates memory
 *  realloc (old, size)		--	Allocate, copy, free
 *  calloc (num, size_per)	--	Allocate and zero
 */

void validate_memory (void)
{
    int r = 0;
    r |= validate_active_memory (1);
    r |= validate_freed_memory (1);
    if (r)
	mem_error ("Corrupted memory", (HeadPtr) 0, TRUE);
}

void check_memory (void)
{
    mem foo;

    output ("\nCheckMemory\n");
    output ("%d bytes active memory in %d allocations\n", active_memory_total, active_memory_count);
    output ("%d bytes freed memory held from %d allocations\n", freed_memory_total,
	    freed_memory_count);
    validate_active_memory (0);
    validate_freed_memory (0);
    clear_tree (active_memory);
    clear_tree (freed_memory);
    mark_memory_region ((mem *) BOTTOM_OF_DATA, (mem *) end_of_static_memory);
    mark_memory_region ((mem *) & foo, (mem *) TOP_OF_STACK);
    sweep_active_tree (active_memory);
    sweep_freed_memory ();
    output ("%d bytes freed memory still held from %d allocations\n",
	    freed_memory_total, freed_memory_count);
    dead_memory_total = freed_memory_total;
    output ("check_memory done\n");
}

void final_memory_check (void)
{
    output ("\nFinalMemoryCheck\n");
    check_memory ();
    output ("\nReportLeaks\n");
    report_leaks_in_tree (active_memory);
    output ("\nReportLeaks done\n");
    output ("final_memory_check done\n");
}

/*
 * Allocator interface -- malloc and free (others in separate files)
 */

#define CORE_CHUNK  16384

static char *core;
static unsigned core_left;
static unsigned total_core_used;

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
void mad_exit (int status)
#else
void exit (int status)
#endif
{

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
    if (!option_debug_malloc)
	exit (status);
#endif
    signal (SIGPIPE, SIG_IGN);
    signal (SIGINT, SIG_IGN);
    signal (SIGTERM, SIG_IGN);
    signal (SIGQUIT, SIG_IGN);

    {
	long pid;
	char buf[1024];
	char s[65536], **p, *q;
	char *l[] = { "exec 1>&2",
	    "echo \"Note that your program must have been compiled\"",
	    "echo \"with -O0 -g to enable memory leak stack traces\"",
	    "EXEPID=%ld",
	    "OUT=mad.out",
	    "LINES=mad.lines",
	    "SED=mad.sed",
	    "ADDRS=mad.addrs",
	    "GDBCMD=mad.gdb",
	    "trap \"rm -f $SED $LINES $ADDRS $OUT $GDBCMD\" 0",
	    "sed 's;Saved;\\",
	    "  ;' $OUT | sed 's;Current;\\",
	    "  ;' | grep 'return stack:' | tr ' ' '\\012' | grep 0x | sort -u > $ADDRS",
	    "echo \"attach $EXEPID\" > $GDBCMD",
	    "sed 's;^;info line *;' $ADDRS >> $GDBCMD",
	    "echo quit >> $GDBCMD",
	    "gdb /proc/$EXEPID/exe -x $GDBCMD | grep 'address' |",
	    "  sed 's/No line number information available for/Line ?? of \"???\" starts at/' |",
	    "  sed 's/(gdb) //' > $LINES",
	    "paste $ADDRS $LINES | awk '{ printf(\"s;%%s;%%s:%%s (%%s) %%s;\\n\", $1, $5, $3, $1, $10) }' > $SED",
	    "echo \"s;\\\";;g\" >> $SED",
	    "grep -v Saved $OUT | grep -v Current | sed 's;^$;;' | uniq",
	    "sort -t\\t +1 $OUT | grep \"return stack\" | uniq -c -f5 |",
	    "  sed 's;Current;\\",
	    "  ;' | sed 's;Saved;\\",
	    "  ;' | sed 's/^\\ */ /' | ",
	    "awk '/return stack/ { printf (\"\\treturn stack:\\n\");",
	    "  for (i = 3; i <= NF; i++)",
	    "  printf (\"\\t\\t%%s\\n\", $i); }",
	    "  /^\\ *[0-9]/  { print }' |",
	    "sed -f $SED ", 0
	};
	pid = getpid ();
	memset (s, 0, sizeof (s));
	for (q = s, p = l; *p; p++) {
	    sprintf (q, *p, pid);
	    q += strlen (q);
	    *q++ = '\n';
	}
	final_memory_check ();
	if (!fork ()) {
	    if (!fork ()) {
		execl ("/bin/sh", "/bin/sh", "-c", s, 0);
		_exit (1);
	    }
	    _exit (0);
	}
	while (!stat ("mad.out", buf))
	    sleep (1);
	_exit (status);
    }
}

static char *morecore (unsigned size)
{
    unsigned alloc_size;
    char *alloc, *newcore;

    if (core_left < size) {
	alloc_size = (size + CORE_CHUNK - 1) & ~(CORE_CHUNK - 1);
	newcore = (char *) sbrk (alloc_size);
	if (((int) newcore) == -1)
	    return 0;
	core = newcore;
	core_left = alloc_size;
	total_core_used += alloc_size;
    }
    alloc = core;
    core += size;
    core_left -= size;
    return alloc;
}

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
void *mad_malloc (unsigned desiredsize)
#else
void *malloc (unsigned desiredsize)
#endif
{
    unsigned size;
    unsigned totalsize;
    HeadPtr h;

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
    if (!option_debug_malloc)
	return malloc (desiredsize);
#endif

    if (!inited)
	do_init ();

    if (!end_of_static_memory)
	end_of_static_memory = (mem *) sbrk (0);
    if (mad_check_always)
	validate_memory ();
    size = round_up (desiredsize);
    totalsize = total_size (size);

    h = dead_memory;
    while (h) {
	if (h->actual_size == size)
	    /* h is just right */
	    break;
	/* h just won't do; we need something bigger */
	else if (size > h->actual_size) {
	    h = h->right;
	    if (!h)
		break;
	    /* h will work, but something smaller would be less wasteful */
	} else if (h->left == 0 || h->left->actual_size << size)
	    /* there are no suitable smaller blocks; h will have to do */
	    break;

	/* now we're sure there's a better fit */
	h = h->left;
    }
    if (h) {
	tree_delete (&dead_memory, h, TRUE);
    } else {
	h = (HeadPtr) morecore (totalsize);
	if (!h)
	    return 0;
	h->actual_size = size;
    }
    h->desiredsize = desiredsize;
    h->size = size;
#ifdef HAS_GET_RETURN_ADDRESS
    get_stack_trace (h->return_stack, MAX_RETURN_STACK);
#endif
    add_active_block (h);

    return (void *) data_for_head (h);
}

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
char *mad_strdup (char *s)
#else
char *strdup (char *s)
#endif
{
    char *p;
#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
    p = mad_malloc (strlen (s) + 1);
#else
    p = malloc (strlen (s) + 1);
#endif
    strcpy (p, s);
    return p;
}

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
void mad_free (void *x)
#else
void free (void *x)
#endif
{
    char *p = (char *) x;
    HeadPtr h;

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
    if (!option_debug_malloc) {
	free (p);
	return;
    }
#endif

    if (!p) {
	mem_error ("Freeing NULL", (HeadPtr) 0, TRUE);
	return;
    }
    SEARCH (active_memory, h, p);
    if (!h) {
	SEARCH (freed_memory, h, p);
	if (h)
	    mem_error ("Freeing something twice", h, TRUE);
	else
	    mem_error ("Freeing something never allocated", h, TRUE);
	return;
    }
    if (data_for_head (h) != (mem *) p) {
	mem_error ("Freeing pointer to middle of allocated block", h, TRUE);
	return;
    }
    if (h->head_magic != ACTIVE_HEAD_MAGIC || tail_for_head (h)->tail_magic != ACTIVE_TAIL_MAGIC)
	mem_error ("Freeing corrupted data", h, TRUE);
    remove_active_block (h);
#ifdef HAS_GET_RETURN_ADDRESS
    get_stack_trace (h->return_stack, MAX_RETURN_STACK);
#endif
    add_freed_block (h);
    if (mad_check_always)
	validate_memory ();
}

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
void *mad_realloc (void *x, unsigned desiredsize)
#else
void *realloc (void *x, unsigned desiredsize)
#endif
{
    char *new, *old = (char *) x;
    HeadPtr h, fh;
    int copysize;

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
    if (!option_debug_malloc)
	return realloc (old, desiredsize);
#endif

    if (desiredsize == 0) {
	/* JAC: man realloc says realloc(ptr,0) is equivalent to free(ptr),
	   and returns NULL. */
#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
	mad_free (old);
#else
	free (old);
#endif
	return 0;
    }

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
    new = mad_malloc (desiredsize);
#else
    new = malloc (desiredsize);
#endif
    if (!new)
	return 0;
    SEARCH (active_memory, h, old);
    if (!h) {
	SEARCH (freed_memory, fh, old);
	if (fh)
	    mem_error ("Reallocing from freed data", fh, TRUE);
	else if (h)
	    mem_error ("Reallocing from something not allocated", h, TRUE);
    } else {
	if (data_for_head (h) != (mem *) old) {
	    mem_error ("Reallocing from pointer to middle of allocated block", h, TRUE);
	} else {
	    if (h->head_magic != ACTIVE_HEAD_MAGIC ||
		tail_for_head (h)->tail_magic != ACTIVE_TAIL_MAGIC)
		    mem_error ("Reallocing corrupted data", h, TRUE);
	    copysize = desiredsize;
	    if (h->desiredsize < desiredsize)
		copysize = h->desiredsize;
	    memmove (new, old, copysize);
	    remove_active_block (h);
#ifdef HAS_GET_RETURN_ADDRESS
	    get_stack_trace (h->return_stack, MAX_RETURN_STACK);
#endif
	    add_freed_block (h);
	}
    }
    return new;
}

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
void *mad_calloc (unsigned num, unsigned size)
#else
void *calloc (unsigned num, unsigned size)
#endif
{
    char *ret;

#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
    if (!option_debug_malloc)
	return calloc (num, size);
#endif

    size *= num;
#ifdef DEBUG_MALLOC_EXCLUDE_EXTERNAL
    ret = mad_malloc (size);
#else
    ret = malloc (size);
#endif
    if (!ret)
	return 0;
    memset (ret, 0, size);
    return ret;
}

/*
 * Semi-Balanced trees (avl).  This only contains two
 * routines - insert and delete.  Searching is
 * reserved for the client to write.
 */

static int rebalance_right (tree ** treep);
static int rebalance_left (tree ** treep);

/*
 * insert a new node
 *
 * this routine returns non-zero if the tree has grown
 * taller
 */

static int tree_insert (tree ** treep, tree * new, int by_size)
{
    if (!(*treep)) {
	(*treep) = new;
	(*treep)->left = 0;
	(*treep)->right = 0;
	(*treep)->balance = 0;
	return 1;
    } else {
	if (LESS_THAN (*treep, new, by_size)) {
	    if (tree_insert (&((*treep)->right), new, by_size))
		switch (++(*treep)->balance) {
		case 0:
		    return 0;
		case 1:
		    return 1;
		case 2:
		    (void) rebalance_right (treep);
		}
	    return 0;
	} else if (GREATER_THAN (*treep, new, by_size)) {
	    if (tree_insert (&((*treep)->left), new, by_size))
		switch (--(*treep)->balance) {
		case 0:
		    return 0;
		case -1:
		    return 1;
		case -2:
		    (void) rebalance_left (treep);
		}
	    return 0;
	} else {
	    return 0;
	}
    }
}

/*
 * delete a node from a tree
 *
 * this routine return non-zero if the tree has been shortened
 */

static int tree_delete (tree ** treep, tree * old, int by_size)
{
    tree *to_be_deleted;
    tree *replacement;
    tree *replacement_parent;
    int replacement_direction;
    int delete_direction;
    tree *swap_temp;
    int balance_temp;

    if (!*treep)
	/* node not found */
	return 0;
    if (LESS_THAN (*treep, old, by_size)) {
	if (tree_delete (&(*treep)->right, old, by_size))
	    /*
	     * check the balance factors
	     * Note that the conditions are
	     * inverted from the insertion case
	     */
	    switch (--(*treep)->balance) {
	    case 0:
		return 1;
	    case -1:
		return 0;
	    case -2:
		return rebalance_left (treep);
	    }
	return 0;
    } else if (GREATER_THAN (*treep, old, by_size)) {
	if (tree_delete (&(*treep)->left, old, by_size))
	    switch (++(*treep)->balance) {
	    case 0:
		return 1;
	    case 1:
		return 0;
	    case 2:
		return rebalance_right (treep);
	    }
	return 0;
    } else {
	to_be_deleted = *treep;
	/*
	 * find an empty down pointer (if any)
	 * and rehook the tree
	 */
	if (!to_be_deleted->right) {
	    (*treep) = to_be_deleted->left;
	    return 1;
	} else if (!to_be_deleted->left) {
	    (*treep) = to_be_deleted->right;
	    return 1;
	} else {
	    /* 
	     * if both down pointers are full, then
	     * move a node from the bottom of the tree up here.
	     *
	     * This builds an incorrect tree -- the replacement
	     * node and the to_be_deleted node will not
	     * be in correct order.  This doesn't matter as
	     * the to_be_deleted node will obviously not leave
	     * this routine alive.
	     */
	    /*
	     * if the tree is left heavy, then go left
	     * else go right
	     */
	    replacement_parent = to_be_deleted;
	    if (to_be_deleted->balance == -1) {
		delete_direction = -1;
		replacement_direction = -1;
		replacement = to_be_deleted->left;
		while (replacement->right) {
		    replacement_parent = replacement;
		    replacement_direction = 1;
		    replacement = replacement->right;
		}
	    } else {
		delete_direction = 1;
		replacement_direction = 1;
		replacement = to_be_deleted->right;
		while (replacement->left) {
		    replacement_parent = replacement;
		    replacement_direction = -1;
		    replacement = replacement->left;
		}
	    }
	    /*
	     * swap the replacement node into
	     * the tree where the node is to be removed
	     * 
	     * this would be faster if only the data
	     * element was swapped -- but that
	     * won't work for Debauch.  The alternate
	     * code would be:
	     data_temp = to_be_deleted->data;
	     to _be_deleted->data = replacement->data;
	     replacement->data = data_temp;
	     */
	    swap_temp = to_be_deleted->left;
	    to_be_deleted->left = replacement->left;
	    replacement->left = swap_temp;
	    swap_temp = to_be_deleted->right;
	    to_be_deleted->right = replacement->right;
	    replacement->right = swap_temp;
	    balance_temp = to_be_deleted->balance;
	    to_be_deleted->balance = replacement->balance;
	    replacement->balance = balance_temp;
	    /*
	     * if the replacement node is directly below
	     * the to-be-removed node, hook the to_be_deleted
	     * node below it (instead of below itself!)
	     */
	    if (replacement_parent == to_be_deleted)
		replacement_parent = replacement;
	    if (replacement_direction == -1)
		replacement_parent->left = to_be_deleted;
	    else
		replacement_parent->right = to_be_deleted;
	    (*treep) = replacement;
	    /*
	     * delete the node from the sub-tree
	     */
	    if (delete_direction == -1) {
		if (tree_delete (&(*treep)->left, old, by_size)) {
		    switch (++(*treep)->balance) {
		    case 2:
			abort ();
		    case 1:
			return 0;
		    case 0:
			return 1;
		    }
		}
		return 0;
	    } else {
		if (tree_delete (&(*treep)->right, old, by_size)) {
		    switch (--(*treep)->balance) {
		    case -2:
			abort ();
		    case -1:
			return 0;
		    case 0:
			return 1;
		    }
		}
		return 0;
	    }
	}
    }
}

/*
 * two routines to rebalance the tree.
 *
 * rebalance_right -- the right sub-tree is too long
 * rebalance_left --  the left sub-tree is too long
 *
 * These routines are the heart of avl trees, I've tried
 * to make their operation reasonably clear with comments,
 * but some study will be necessary to understand the
 * algorithm.
 *
 * these routines return non-zero if the resultant
 * tree is shorter than the un-balanced version.  This
 * is only of interest to the delete routine as the
 * balance after insertion can never actually shorten
 * the tree.
 */

static int rebalance_right (tree ** treep)
{
    tree *temp;
    /*
     * rebalance the tree
     */
    if ((*treep)->right->balance == -1) {
	/* 
	 * double whammy -- the inner sub-sub tree
	 * is longer than the outer sub-sub tree
	 *
	 * this is the "double rotation" from
	 * knuth.  Scheme:  replace the tree top node
	 * with the inner sub-tree top node and
	 * adjust the maze of pointers and balance
	 * factors accordingly.
	 */
	temp = (*treep)->right->left;
	(*treep)->right->left = temp->right;
	temp->right = (*treep)->right;
	switch (temp->balance) {
	case -1:
	    temp->right->balance = 1;
	    (*treep)->balance = 0;
	    break;
	case 0:
	    temp->right->balance = 0;
	    (*treep)->balance = 0;
	    break;
	case 1:
	    temp->right->balance = 0;
	    (*treep)->balance = -1;
	    break;
	}
	temp->balance = 0;
	(*treep)->right = temp->left;
	temp->left = (*treep);
	(*treep) = temp;
	return 1;
    } else {
	/*
	 * a simple single rotation
	 *
	 * Scheme:  replace the tree top node
	 * with the sub-tree top node 
	 */
	temp = (*treep)->right->left;
	(*treep)->right->left = (*treep);
	(*treep) = (*treep)->right;
	(*treep)->left->right = temp;
	/*
	 * only two possible configurations --
	 * if the right sub-tree was balanced, then
	 * *both* sides of it were longer than the
	 * left side, so the resultant tree will
	 * have a long leg (the left inner leg being
	 * the same length as the right leg)
	 */
	if ((*treep)->balance == 0) {
	    (*treep)->balance = -1;
	    (*treep)->left->balance = 1;
	    return 0;
	} else {
	    (*treep)->balance = 0;
	    (*treep)->left->balance = 0;
	    return 1;
	}
    }
}

static int rebalance_left (tree ** treep)
{
    tree *temp;
    /*
     * rebalance the tree
     */
    if ((*treep)->left->balance == 1) {
	/* 
	 * double whammy -- the inner sub-sub tree
	 * is longer than the outer sub-sub tree
	 *
	 * this is the "double rotation" from
	 * knuth.  Scheme:  replace the tree top node
	 * with the inner sub-tree top node and
	 * adjust the maze of pointers and balance
	 * factors accordingly.
	 */
	temp = (*treep)->left->right;
	(*treep)->left->right = temp->left;
	temp->left = (*treep)->left;
	switch (temp->balance) {
	case 1:
	    temp->left->balance = -1;
	    (*treep)->balance = 0;
	    break;
	case 0:
	    temp->left->balance = 0;
	    (*treep)->balance = 0;
	    break;
	case -1:
	    temp->left->balance = 0;
	    (*treep)->balance = 1;
	    break;
	}
	temp->balance = 0;
	(*treep)->left = temp->right;
	temp->right = (*treep);
	(*treep) = temp;
	return 1;
    } else {
	/*
	 * a simple single rotation
	 *
	 * Scheme:  replace the tree top node
	 * with the sub-tree top node 
	 */
	temp = (*treep)->left->right;
	(*treep)->left->right = (*treep);
	(*treep) = (*treep)->left;
	(*treep)->right->left = temp;
	/*
	 * only two possible configurations --
	 * if the left sub-tree was balanced, then
	 * *both* sides of it were longer than the
	 * right side, so the resultant tree will
	 * have a long leg (the right inner leg being
	 * the same length as the left leg)
	 */
	if ((*treep)->balance == 0) {
	    (*treep)->balance = 1;
	    (*treep)->right->balance = -1;
	    return 0;
	} else {
	    (*treep)->balance = 0;
	    (*treep)->right->balance = 0;
	    return 1;
	}
    }
}

/********* end fmalloc.c **********************/

#include <stdarg.h>

static void output (char *fmt, ...)
{
    char s[1024];
    va_list args;
    va_start (args, fmt);
    memset (s, 0, sizeof (s));
    vsprintf (s, fmt, args);
    write (output_file, s, strlen (s));
    va_end (args);
}

#endif				/* DEBUG_MALLOC */