/*----------------------------------------------------------------------------
 * (C) 1997-2003 Armin Biere
 *     (original version and improvements)
 *
 *     2001 Fritz Elfert
 *     (fixes for retrieving argv0)
 *     
 *     2000 Henning Moll
 *     (fixes to GDB interface and better library chain detection heuristics)
 *
 *     2000 Ishmael
 *     (only-wasting-alloc)
 *
 *     1998 Johannes Keukelaar
 *     (dont-log-chain, only-log-chain, read-dynlib-with-gdb, fixes)
 *
 *     1998 Remy Didier
 *     (logpid)
 *
 *     $Id: callchain.c,v 1.23 2003/02/03 08:03:54 biere Exp $
 *----------------------------------------------------------------------------
 */

#include "config.h"

/* ------------------------------------------------------------------------ */

#include <assert.h>
#include <ctype.h>
#include <dirent.h>
#include <errno.h>
#include <fcntl.h>
#include <setjmp.h>
#include <signal.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <sys/utsname.h>
#include <time.h>
#include <unistd.h>

/*------------------------------------------------------------------------*/

#include "hash.h"
#include "ccmalloc.h"

/*------------------------------------------------------------------------*/

void libcwrapper_inc_semaphore (void);
void libcwrapper_dec_semaphore (void);
const char *wrapper_stats (void);

/* ------------------------------------------------------------------------ */

typedef struct Symbol
{
  char *name;
  caddr_t addr;
}
Symbol;

/* ------------------------------------------------------------------------ */

/*
 * The allocated data has the following general form:
 *
 *  ccmallocKeepFreeData ?		// only if keep_deallocated_data and
 *					// and not only_count
 *
 *  ccmallocLinks ?			// if not only_count
 *
 *  ccmallocSize
 *
 *  ccmallocMagicAndFlags		// for all allocated data
 *
 *  ccmallocBoundary ?			// for detection of underwrites
 *
 *  ccmallocUserData
 *
 *  ccmallocBoundary ?			// for detection of overwrites
 *
 */
/* ------------------------------------------------------------------------ */

typedef struct CallChain_ *CallChain;

/* ------------------------------------------------------------------------ */

typedef struct ccmallocKeepFreeData
{
  CallChain freed_at;
}
ccmallocKeepFreeData;

/* ------------------------------------------------------------------------ */

typedef struct ccmallocLinks
{
  CallChain callchain;		/* of allocator if allocated and of
				 * deallocator if deallocated
				 */

  struct ccmallocLinks *next, *prev;

  /* doubly linked list of data allocated from
   * same callchain (the callchain above!)
   */

  /*
   * We could use a singly linked list if keep_deallocated_data is true
   * and share the prev field with the freed_at pointer. But this would
   * only save a pointer when keep_deallocated_data is true in which case
   * we waste space anyway.
   */
}
ccmallocLinks;

/* ------------------------------------------------------------------------ */

typedef struct ccmallocSize
{
  int size;			/* If we had an own `malloc' this space
				 * could be saved (the underlying allocator
				 * must store this value anyway)
				 */
}
ccmallocSize;

/* ------------------------------------------------------------------------ */

typedef struct ccmallocMagicAndFlags
{
  unsigned int magic_and_flags;	/* We use some `magic' here to detect
				 * if the user has messed up our data
				 * (see above). It would be better to use
				 * something like mprotect. But then we must
				 * store this data apart from the user data
				 */
}
ccmallocMagicAndFlags;

/* ------------------------------------------------------------------------ */

/* !!! just a comment !!! */

/* #define ccmallocUserData char */

/* ------------------------------------------------------------------------ */

typedef struct ccmallocBoundary
{
  unsigned boundary[0];
}
ccmallocBoundary;

/* ------------------------------------------------------------------------ */

typedef struct CallChainKey
{
  CallChain next;
  caddr_t addr;
}
CallChainKey;

/* ------------------------------------------------------------------------ */

enum AddrDataState
{ NOT_WRITTEN, WRITTEN, FIELDS_ARE_VALID };

/* ------------------------------------------------------------------------ */

typedef struct AddrData
{
  caddr_t key;

  enum AddrDataState state;

  char *name;			/* The name of the function. It can be
				 * found for (at least) all external
				 * functions if the binary is not stripped
				 */

  char *file;			/* Only binaries compiled with */
  int lineno;			/* `-g' have this info ! */

  char *alternative_name;	/* as provided by gdb */
}
AddrData;

/* ------------------------------------------------------------------------ */

typedef struct CallChainStats
{
  long bytes_allocated, bytes_deallocated, num_allocated, num_deallocated;
}
CallChainStats;

/* ------------------------------------------------------------------------ */

typedef struct CCToplevelData
{
  ccmallocLinks *allocations;	/* doubly linked list of data allocated */
  long bytes_wasted;		/* used for sorting */
  struct CCToplevelData *prev, *next;
  CallChainStats *stats;
}
CCToplevelData;

/* ------------------------------------------------------------------------ */

typedef struct CallChain_
{
  CallChainKey key;
  AddrData *addr_data;
  CCToplevelData *toplevel_data;
}
CallChain_;

/*------------------------------------------------------------------------*/
/* Call chains that are not supposed to be logged.
 */

typedef struct FuncOrFile
{
  char *name;			/* File or function name. */
  int line;			/* Optional line number in file or function */
  /* . -1 = ignore. */
}
FuncOrFile;

typedef struct DontLogChain
{
  int num;			/* Number of FuncOrFiles. */
  struct FuncOrFile funcs[1];	/* Actually more than this! See numelem! */
}
DontLogChain;

/* ------------------------------------------------------------------------ */

enum TypeOfLogFile
{ NO_COMPRESSED_LOGFILE, COMPRESS_LOGFILE, GZIP_LOGFILE };

/* ------------------------------------------------------------------------ */
/* This buffer is allocated statically since we do not want to call malloc
 * in the startup phase.
 */

#define MAXBUFFER 50000
static char buffer[MAXBUFFER];	/* used by several parsers below */

/* ------------------------------------------------------------------------ */
/* file names
 */

static char *file_name = 0;	/* of executable */
static const char *startup_file_name = ".ccmalloc";
static int startup_file_lineno = 0;

/* ',' is a valid character for c++ symbol names. so we use ';' instead...
 * (Henning Moll + Armin Biere)
 */
static char CHAIN_DELIMITER = ';';

/* Chains that shouldn't be logged. */
static DontLogChain **dont_log_chains = 0;

/* How many of them there are. */
static int num_dont_log_chains = 0;

/* Chains that should be logged. */
static DontLogChain **only_log_chains = 0;

/* How many of them there are. */
static int num_only_log_chains = 0;

/* ------------------------------------------------------------------------ */
/* global boolean flags accessible by startup file commands
 */

static int align_on_8_byte_boundary = 0;
static int callchain_statistics = 0;
static int chain_length = 0;
static int check_free_space = 0;
static int check_interval = 0;
static int check_overwrites = 0;
static int check_start = 0;
static int check_underwrites = 0;
static int continue_flag = 0;
static int empty_lines = 1;
static int file_info = 1;
static int keep_deallocated_data = 0;
static int library_chains = 0;
static int load_dynlibs_with_gdb = 0;
static int only_count = 0;
static int print_addresses_flag = 0;
static int print_on_one_line = 0;
static int silent_startup = 0;
static int sort_by_size = 1;
static int sort_by_wasted = 1;
static int only_wasting_alloc = 1;
static int check_modulo = 0;
static long check_count = 0;
static long checks_done = 0;
static enum TypeOfLogFile compressed_logfile = NO_COMPRESSED_LOGFILE;
static FILE *logfile = 0;
static char *logfilename = 0;

/*------------------------------------------------------------------------*/

#ifndef NDEBUG
static int debug_flag = 1;
#else
static int debug_flag = 0;
#endif

/* ------------------------------------------------------------------------ */
/* statistics
 */

static long bytes_allocated = 0, num_allocated = 0,
  bytes_deallocated = 0, num_deallocated = 0, bytes_wasted;

/* ------------------------------------------------------------------------ */
/* If a C++ wrapper is used in combination with this library we can
 * statically initialize the library and call 'ccmalloc_report' from a
 * static destructor instead of registering it with 'atexit' to be called on
 * program termination.
 */

static int ccmalloc_ctordtor = 0;

/* ------------------------------------------------------------------------ */
/* sort of inheritance support ;-)
 */

/* for data header ... initialized by ccmalloc_init() */

static int offset = -1;		/* depends on global flags only_count and
				 * keep_deallocated_data which can be set
				 * by the user
				 */

static int ccmallocKeepFreeData_ccmallocLinks_offset = -1;
static int ccmallocLinks_ccmallocMagicAndFlags_offset = -1;
static int ccmallocLinks_ccmallocUserData_offset = -1;
static int ccmallocLinks_ccmallocSize_offset = -1;
static int ccmallocMagicAndFlags_ccmallocUserData_offset = -1;
static int ccmallocSize_ccmallocMagicAndFlags_offset = -1;
static int ccmallocSize_ccmallocUserData_offset = -1;

#define is_allocated_links(links) \
  is_allocated((ccmallocMagicAndFlags*) \
    (((char*)links) + ccmallocLinks_ccmallocMagicAndFlags_offset))

#define is_corrupted_links(links) \
  is_corrupted((ccmallocMagicAndFlags*) \
    (((char*)links) + ccmallocLinks_ccmallocMagicAndFlags_offset))

#define get_size_links(links) \
  (((ccmallocSize*) \
    (((char*)links) + ccmallocLinks_ccmallocSize_offset)) -> size)

/* ------------------------------------------------------------------------ */

/* internal state of this library
 */

enum State
{
  UNINITIALIZED,
  INITIALIZING,
  INITIALIZED,
  FINISHED
};

static enum State state = UNINITIALIZED;
static int tell_about_dtors = 1;

/* ------------------------------------------------------------------------ */

static HashTable strings = 0;
static HashTable addrs = 0;

static int num_symbols = 0;
static Symbol **symbols = 0;	/* sorted by address (zero terminated)  */
static HashTable symtab = 0;	/* fast access through name */

static int num_chains = 0;
static CallChain *chains;	/* zero terminated array of size num_chains */
static HashTable chaintab = 0;

static CallChain empty_call_chain = 0;

static CCToplevelData *toplevels = 0;

/* ------------------------------------------------------------------------ */

#if defined(OS_IS_SOLARIS)
/* `double' has to be 8 Byte aligned in these OS. This means we always have
 * to align on a 8 Byte boundary :-(
 */
# define ALIGN_MASK 7
#else
# define ALIGN_MASK (align_on_8_byte_boundary ? 7 : 3)
#endif

/* ------------------------------------------------------------------------ */

#define isAligned(c) ((((unsigned)c) & ALIGN_MASK) == 0)

#define align(c)					\
{							\
  if(!isAligned(c))					\
    {							\
      *(unsigned*)&c = (((unsigned)c) | ALIGN_MASK);	\
      *(unsigned*)&c = (((unsigned)c) + 1);		\
    }							\
}

/* ------------------------------------------------------------------------ */
/* macros for manipulation of `magic_and_flags'
 */

/* used for randomization of hash value */

#define MAGIC_CHAR ((char)0x42)
#define BASIC_SPELL 0x42424242
#define BASIC_SPELL_STR "0x42424242"

#define IS_ALLOCATED_FLAG	1
#define IS_CORRUPTED_FLAG	2

#define NUMBER_OF_FLAGS		2

#define FLAGS_MASK (IS_ALLOCATED_FLAG | IS_CORRUPTED_FLAG)
#define MAGIC_MASK (~FLAGS_MASK)

#define set_bits(a,bits,mask) \
  ((a) -> magic_and_flags = \
    ((((a) -> magic_and_flags) & (~(mask))) | ((bits) & (mask))))

#define get_bits(a,mask) ((a) -> magic_and_flags & (mask))

/* Before you call `set_magic(p)' you should set the bits below. This also
 * means that after changing one of these bits you have to call `set_magic'
 * again. The same is true for changing the `size' field.
 */

#define set_is_allocated(a) set_bits((a),IS_ALLOCATED_FLAG,IS_ALLOCATED_FLAG)
#define clr_is_allocated(a) set_bits((a),0,IS_ALLOCATED_FLAG)
#define is_allocated(a) get_bits((a),IS_ALLOCATED_FLAG)

#define set_is_corrupted(a) set_bits((a),IS_CORRUPTED_FLAG,IS_CORRUPTED_FLAG)
#define clr_is_corrupted(a) set_bits((a),0,IS_CORRUPTED_FLAG)
#define is_corrupted(a) get_bits((a),IS_CORRUPTED_FLAG)

#define get_size(a) \
  (((ccmallocSize*)(((char*)a) - ccmallocSize_ccmallocMagicAndFlags_offset)) \
    -> size)

/* This macro hashes the `flags', the address and
 * the `size' of the argument into an unsigned number.
 * This can be used to detect manipulation of our data by the user.
 */

#define calculate_spell(a) \
(                                                                   \
  (                                                                 \
    ((unsigned int)(a))                          /* hash address */ \
    ^                                                               \
    (get_bits(a,FLAGS_MASK) << NUMBER_OF_FLAGS)  /* hash flags */   \
    ^                                                               \
    (get_size(a) << NUMBER_OF_FLAGS)             /* hash size */    \
    ^                                                               \
    BASIC_SPELL                                  /* randomize */    \
  )                                                                 \
  &                                                                 \
  MAGIC_MASK                                                        \
)

#define set_magic(a) set_bits((a), calculate_spell(a), MAGIC_MASK)

#define invalidate_magic(a) set_bits((a), ~calculate_spell(a), MAGIC_MASK)

#define is_valid_magic(a) (get_bits((a), MAGIC_MASK) == calculate_spell((a)))

/* ------------------------------------------------------------------------ */

static void
_callchain_msg (const char *fmt, va_list ap)
{
  vfprintf (logfile, fmt, ap);
  fflush (logfile);
}

/* ------------------------------------------------------------------------ */

static void
callchain_msg (const char *fmt, ...)
{
  va_list ap;
  va_start (ap, fmt);
  _callchain_msg (fmt, ap);
  va_end (ap);
}

/* ------------------------------------------------------------------------ */

static void close_logfile (void);

static void
die (void)
{
  fputs ("*** good bye cruel world ...\n", stderr);
  fflush (stderr);

  close_logfile ();

  abort ();
  exit (1);
}

/* ------------------------------------------------------------------------ */

/* fatal error in this library
 */

void
ccmalloc_abort (const char *fmt, ...)
{
  va_list ap;
  va_start (ap, fmt);
  _callchain_msg (fmt, ap);
  va_end (ap);
  die ();
}

/* ------------------------------------------------------------------------ */

/* normal error in this library
 */

static void
callchain_error (const char *fmt, ...)
{
  va_list ap;
  va_start (ap, fmt);
  _callchain_msg (fmt, ap);
  va_end (ap);

  close_logfile ();

  exit (1);
}

/* ------------------------------------------------------------------------ */

/* `readLine' reads a line from a file into a buffer with size `max' with
 * '\0' and '\n' as line seperators.
 */

static int
readLine (FILE * file, char *buffer, int max)
{
  int i, ch;

  if (feof (file))
    {
      buffer[0] = '\0';
      return 0;
    }
  else
    {
      i = 0;

      for (;;)
	{
	  ch = getc (file);

	  if (ch == EOF || ch == '\0' || ch == '\n')
	    {
	      buffer[i] = '\0';

	      if (i == 0)
		return ch == '\n' || ch == '\0';
	      else
		return 1;
	    }
	  else
	    {
	      if (i < max - 1)
		{
		  if (ch != '\n' && ch != '\0')
		    buffer[i++] = ch;
		}
	      else
		{
		  callchain_error ("buffer exceeded in readLine()\n",
				   logfile);
		}
	    }
	}
    }
}

/* ------------------------------------------------------------------------ */
/* support functions for strings unique table */

static void
freeString (void *p)
{
  free (p);
}

/* ------------------------------------------------------------------------ */

#define cmpStrings ((int(*)(void*,void*)) strcmp)

/* ------------------------------------------------------------------------ */

static char *
find_string (char *s)
{
  void **position;
  char *res;

  if (!strings)
    strings =
      new_HashTable (100, cmpStrings, hashpjw_HashTable, 0, freeString, 0);

  position = get_position_of_key_in_HashTable (strings, s);
  if (!*position)
    {
      res = strcpy ((char *) malloc (strlen (s) + 1), s);
      insert_at_position_into_HashTable (strings, position, res);
    }
  else
    {
      res = (char *) get_data_from_position_in_HashTable (strings, position);
    }

  return res;
}

/* ------------------------------------------------------------------------ */

static AddrData *
new_AddrData (caddr_t key)
{
  AddrData *ad = (AddrData *) malloc (sizeof (AddrData));

  ad->key = key;
  ad->state = NOT_WRITTEN;
  ad->name = 0;
  ad->file = 0;
  ad->lineno = -1;
  ad->alternative_name = 0;

  return ad;
}

/* ------------------------------------------------------------------------ */

static int
cmpAddr (void *k1, void *k2)
{
  AddrData *ad1 = (AddrData *) k1, *ad2 = (AddrData *) k2;
  caddr_t addr1 = ad1->key, addr2 = ad2->key;

  if (addr1 == addr2)
    return 0;
  else if (addr1 < addr2)
    return -1;
  else
    return 1;
}

/* ------------------------------------------------------------------------ */

static void *
getKeyOfAddr (void *d)
{
  AddrData *ad = (AddrData *) d;
  return (void *) &ad->key;
}

/* ------------------------------------------------------------------------ */

static void
freeAddr (void *p)
{
  free (p);
}

/* ------------------------------------------------------------------------ */

static int
hashAddr (void *p)
{
  caddr_t *ad = (caddr_t *) p;
  return (int) *ad;
}

/* ------------------------------------------------------------------------ */

static AddrData *
find_addr (caddr_t key)
{
  void **position;
  AddrData *res;

  if (!key)
    return 0;

  if (!addrs)
    addrs = new_HashTable (100, cmpAddr, hashAddr, getKeyOfAddr, freeAddr, 0);

  position = get_position_of_key_in_HashTable (addrs, &key);
  if (!*position)
    {
      res = new_AddrData (key);
      insert_at_position_into_HashTable (addrs, position, res);
    }
  else
    {
      res =
	(AddrData *) get_data_from_position_in_HashTable (addrs, position);
    }

  return res;
}

/* ------------------------------------------------------------------------ */

static void freeAllocations (ccmallocLinks *);

/* ------------------------------------------------------------------------ */

static CCToplevelData *
new_CCToplevelData (void)
{
  CCToplevelData *res;

  res = (CCToplevelData *) malloc (sizeof (CCToplevelData));

  res->allocations = 0;
  res->bytes_wasted = 0;

  if (callchain_statistics)
    {
      res->stats = (CallChainStats *) malloc (sizeof (CallChainStats));
      res->stats->num_allocated = 0;
      res->stats->num_deallocated = 0;
      res->stats->bytes_allocated = 0;
      res->stats->bytes_deallocated = 0;
    }
  else
    res->stats = 0;		/* defensive */

  return res;
}

/* ------------------------------------------------------------------------ */

static void
free_CCToplevelData (CCToplevelData * td)
{
  if (callchain_statistics)
    {
      assert (td->stats);
      free (td->stats);
    }

  if (td->allocations)
    freeAllocations (td->allocations);

  free (td);
}

/* ------------------------------------------------------------------------ */
/* manipulation of doubly linked list `allocations' in a CallChain_
 */

static void
enqueue (CallChain c, ccmallocLinks * d)
{
  CCToplevelData *td;

  if (!(td = c->toplevel_data))
    {
      td = c->toplevel_data = new_CCToplevelData ();
      assert (td->allocations == 0);
    }

  if (!td->allocations)
    {
      /* enqueue td to toplevels */

      td->next = toplevels;
      if (td->next)
	td->next->prev = td;
      td->prev = 0;

      toplevels = td;
    }

  d->next = td->allocations;
  if (d->next)
    d->next->prev = d;
  d->prev = 0;

  td->allocations = d;
  d->callchain = c;
}

/* ------------------------------------------------------------------------ */

static void
dequeue (ccmallocLinks * d)
{
  CCToplevelData *td;

  CallChain c = d->callchain;
  td = c->toplevel_data;

  assert (td->allocations);

  if (d->prev)
    d->prev->next = d->next;
  else
    {
      assert (td->allocations == d);

      if (!(td->allocations = d->next))
	{
	  /* and dequeue td from toplevels if no more allocations */

	  if (td->prev)
	    td->prev->next = td->next;
	  else
	    {
	      assert (td == toplevels);

	      toplevels = td->next;
	    }

	  if (td->next)
	    td->next->prev = td->prev;
	}
    }

  if (d->next)
    d->next->prev = d->prev;
}

/* ------------------------------------------------------------------------ */

/* deallocated a list of ccmallocLinks 
 */

static void
freeAllocations (ccmallocLinks * a)
{
  while (a)
    {
      ccmallocLinks *tmp = a->next;
      char *b = ((char *) a);

      if (keep_deallocated_data)
	b -= ccmallocKeepFreeData_ccmallocLinks_offset;
      free (b);

      a = tmp;
    }
}


/* ------------------------------------------------------------------------ */
/* functions for `chaintab' hashtable
 */

/* compare first by `next' and then by `addr' */

static int
cmpKeys (void *_a, void *_b)
{
  CallChainKey *a = (CallChainKey *) _a, *b = (CallChainKey *) _b;

  if (a != b)
    {
      if (a->next == b->next)
	{
	  if (a->addr == b->addr)
	    return 0;
	  else if (a->addr < b->addr)
	    return -1;
	  else
	    return 1;
	}
      else
	{
	  if (a->next < b->next)
	    return -1;
	  else
	    return 1;
	}
    }
  else
    return 0;
}

/* ------------------------------------------------------------------------ */

static int
hashKey (void *_a)
{
  CallChainKey *a = (CallChainKey *) _a;
  return ((int) a->next) ^ ((int) a->addr);
}

/* ------------------------------------------------------------------------ */

static void *
getKey (void *a)
{
  return (void *) &((CallChain) a)->key;
}

/* ------------------------------------------------------------------------ */

static void
_freeCallChain (CallChain c)
{
  if (c->toplevel_data)
    free_CCToplevelData (c->toplevel_data);
  free (c);
}

/* wrapper */

#define freeCallChain ((void(*)(void*)) _freeCallChain)

/* ------------------------------------------------------------------------ */

/* We do not delete CallChains until exit of the program.
 * So there are no garbage CallChains at all and we do not
 * need garbage collection (for example with reference
 * counting). All allocated CallChain_'s are stored in
 * the hashtable and can be reclaimed from there.
 */

static CallChain
new_CallChain (CallChain next, caddr_t addr)
{
  CallChainKey key;
  CallChain res;
  void **position;

  key.next = next;
  key.addr = addr;

  if (!chaintab)
    chaintab =
      new_HashTable (100, cmpKeys, hashKey, getKey, freeCallChain, 0);

  position = get_position_of_key_in_HashTable (chaintab, &key);

  if (*position)
    {
      res = (CallChain)
	get_data_from_position_in_HashTable (chaintab, position);
    }
  else
    {
      res = (CallChain) malloc (sizeof (CallChain_));
      insert_at_position_into_HashTable (chaintab, position, res);

      /* and initialized CallChain */

      res->key = key;
      res->addr_data = 0;
      res->toplevel_data = 0;
    }

  return res;
}

/* ------------------------------------------------------------------------ */

/* `backtrace' returns the CallChain of frames above the current
 * and skips an initial amount of frames.
 *
 * The idea for this very important part of code
 * is inspired by the `mpr' memory profiler of
 * taj@intergate.bc.ca (Taj Khattra).
 */

static int have_bounds = 0;

#define is_entry_pc(c) \
  (have_bounds && ((c) < entry_end && (c) >= entry_start))

#define is_library_pc(c) \
  (have_bounds && ((c) < text_start || (c) >= text_end))

static caddr_t entry_start = 0;
static caddr_t entry_end = 0;

static caddr_t text_start = 0;
static caddr_t text_end = 0;

static int exception = 0;
static jmp_buf backtrace_jump;

static void (*old_SEGV_handler) (int) = 0;
static void (*old_BUS_handler) (int) = 0;

static CallChain bt_res = 0;	/* save for longjmp's */

/* ------------------------------------------------------------------------ */

static void
set_exception (int i)
{
  (void) i;
  exception = 1;
  longjmp (backtrace_jump, 1);
}

/* ------------------------------------------------------------------------ */

static void
setup_SEGV_BUS_handlers (void)
{
  exception = 0;
  old_SEGV_handler = signal (SIGSEGV, set_exception);
  old_BUS_handler = signal (SIGBUS, set_exception);
}

/* ------------------------------------------------------------------------ */

static void
restore_SEGV_BUS_handlers (void)
{
  (void) signal (SIGBUS, old_BUS_handler);
  (void) signal (SIGSEGV, old_SEGV_handler);
}

/* ------------------------------------------------------------------------ */
#ifdef X86_BACKTRACE
/* ------------------------------------------------------------------------ */

/* special code for x86 (or just linux ?)
 */

static CallChain
backtrace (int skip)
{
  bt_res = 0;
  assert (skip >= 0);

  if (chain_length == 1)
    return 0;

  setup_SEGV_BUS_handlers ();

  if (setjmp (backtrace_jump) == 0)
    {
      int i = 0, max = skip + chain_length;
      caddr_t pc, *fp = ((caddr_t *) & skip) - 2;	/* x86 */
      exception = 1;

      while (1)
	{
	  /* A simple break means always:
	   * abort this loop with an exception (=1)
	   */

	  caddr_t *new_fp;

	  /* find the frame above fp and check it */

	  if (!fp)
	    break;
	  new_fp = *(caddr_t **) fp;	/* raise signal ?? */

	  /* extract program counter from old frame and check it */

	  pc = ((caddr_t *) fp)[1];	/* raise signal ?? */
	  if (!pc)
	    break;		/* heuristic */
	  if (have_bounds && pc < text_start)
	    break;		/* libraries are above */

	  if (chain_length > 0 && i >= max)
	    break;

	  if (is_entry_pc (pc))
	    {
	      exception = 0;	/* normal exit of this loop */
	      break;
	    }

	  if (!new_fp)
	    break;		/* heuristic */
	  if (new_fp <= fp)
	    break;		/* stack grows downward */

	  if (skip == 0)
	    bt_res = new_CallChain (bt_res, pc);
	  else
	    skip--;

	  /* increment */

	  i++;
	  fp = new_fp;
	}
    }

  restore_SEGV_BUS_handlers ();

  if (exception)
    {
      /* generate a non valid frame with address 0
       * above already generated call chain
       */

      bt_res = new_CallChain (bt_res, 0);	/* is zero ok ? */
    }

  return bt_res;
}

#else

/* ------------------------------------------------------------------------ */

/* This should work with gcc on all platforms but has the drawback
 * of being a little bit slower and of course works only for fixed
 * (at compile time) maximal length of callchains.
 * (because __builtin_return_address expects a constant as argument).
 */

#define MAXCALLCHAINLENGTH 100

/* We have to condition any call to return_address on a call to
 * frame_address for the same level: if the latter returns zero, the former
 * will segfault (rather than returning 0 as claimed by its spec).  This is
 * a bug in gcc 2.95.4 and 3.0.4; maybe fixed more recently.
 *
 * (Edward Welbourne).
 */
#define RA(a) case a: return (caddr_t) \
__builtin_return_address(a) ? __builtin_return_address(a) : (caddr_t) 0;

static caddr_t
return_address (unsigned i)
{
  switch (i)
    {
      RA (0);
      RA (1);
      RA (2);
      RA (3);
      RA (4);
      RA (5);
      RA (6);
      RA (7);
      RA (8);
      RA (9);
      RA (10);
      RA (11);
      RA (12);
      RA (13);
      RA (14);
      RA (15);
      RA (16);
      RA (17);
      RA (18);
      RA (19);
      RA (20);
      RA (21);
      RA (22);
      RA (23);
      RA (24);
      RA (25);
      RA (26);
      RA (27);
      RA (28);
      RA (29);
      RA (30);
      RA (31);
      RA (32);
      RA (33);
      RA (34);
      RA (35);
      RA (36);
      RA (37);
      RA (38);
      RA (39);
      RA (40);
      RA (41);
      RA (42);
      RA (43);
      RA (44);
      RA (45);
      RA (46);
      RA (47);
      RA (48);
      RA (49);
      RA (50);
      RA (51);
      RA (52);
      RA (53);
      RA (54);
      RA (55);
      RA (56);
      RA (57);
      RA (58);
      RA (59);
      RA (60);
      RA (61);
      RA (62);
      RA (63);
      RA (64);
      RA (65);
      RA (66);
      RA (67);
      RA (68);
      RA (69);
      RA (70);
      RA (71);
      RA (72);
      RA (73);
      RA (74);
      RA (75);
      RA (76);
      RA (77);
      RA (78);
      RA (79);
      RA (80);
      RA (81);
      RA (82);
      RA (83);
      RA (84);
      RA (85);
      RA (86);
      RA (87);
      RA (88);
      RA (89);
      RA (90);
      RA (91);
      RA (92);
      RA (93);
      RA (94);
      RA (95);
      RA (96);
      RA (97);
      RA (98);
      RA (99);
      RA (100);
    default:
      return 0;
    }
}

static CallChain
backtrace (int skip)
{
  bt_res = 0;
  assert (skip >= 0);

  setup_SEGV_BUS_handlers ();

  if (chain_length == 1)
    return 0;

  if (setjmp (backtrace_jump) == 0)
    {
      int i = ++skip, max = skip + chain_length;
      exception = 1;

      while (1)
	{
	  /* a simple break means always abort this loop
	   * with exception == 1
	   */

	  caddr_t pc = return_address (i++);

	  if (!pc)
	    break;
	  if (have_bounds && pc < text_start)
	    break;		/* libraries are above */

	  if (i > MAXCALLCHAINLENGTH || (chain_length > 0 && i >= max))
	    break;

	  if (is_entry_pc (pc))
	    {
	      exception = 0;	/* normal exit of this loop */
	      break;
	    }

	  bt_res = new_CallChain (bt_res, pc);
	}
    }

  restore_SEGV_BUS_handlers ();

  if (exception)
    {
      /* generate a non valid frame with address 0
       * above already generated call chain
       */

      bt_res = new_CallChain (bt_res, 0);	/* is zero ok ? */
    }

  return bt_res;
}

#endif

/* ------------------------------------------------------------------------ */

/* `has_allocated_data' tells us if a `CallChain' has some allocated but not
 * deallocated `ccmallocLinks' associated with it. Depending on the value
 * of `callchain_statistics' and `keep_deallocated_data' the semantic
 * changes!
 */

static int
has_allocated_data (CallChain c)
{
  CCToplevelData *td = c->toplevel_data;

  assert (c);

  if (!td || !td->allocations)
    return 0;

  if (callchain_statistics)
    {
      CallChainStats *stats = td->stats;
      return stats->num_deallocated || stats->num_allocated;
    }
  else
    {
      if (keep_deallocated_data)
	{
	  int found_allocated_data = 0;
	  ccmallocLinks *p;

	  for (p = td->allocations; p; p = p->next)
	    {
	      if (is_allocated_links (p))
		{
		  found_allocated_data = 1;
		  break;
		}
	    }

	  return found_allocated_data;
	}
      else
	{
	  /* In this case we have only garbage on the `allocations' list.
	   */

	  return td->allocations != 0;	/* defensive (== return 1) */
	}
    }
}

/* ------------------------------------------------------------------------ */

/* `name_all_chains' assumes that the symbol array `symbols' is installed
 * and sorted. Then it trys to find a symbol name for all addresses
 * stored in callchains. The search method is a binary search.
 */

static Symbol *
find_symbol_by_address (caddr_t addr)
{
  if (is_library_pc (addr))
    return 0;

  if (num_symbols)
    {
      int l = 0, h = num_symbols - 1;

      while (h - l > 1)		/* binary search */
	{
	  int m = (l + h) / 2;
	  caddr_t maddr = symbols[m]->addr;

	  if (maddr > addr)
	    h = m;
	  else if (maddr < addr)
	    l = m;
	  else
	    l = h = m;		/* does this really happen ? */
	}			/* (first opcode of a function */
      /*  should be no `call') */
      if (h > l)
	{
	  if (symbols[h]->addr <= addr)
	    l = h;
	  else
	    h = l;		/* defensive */
	}

      return symbols[l];
    }
  else
    return 0;
}

/* ------------------------------------------------------------------------ */

static void
name_chain (CallChain c)
{
  while (c)
    {
      caddr_t addr = c->key.addr;

      if (addr)
	{
	  AddrData *ad;
	  if (!c->addr_data)
	    c->addr_data = find_addr (addr);
	  ad = c->addr_data;
	  if (!ad->name)
	    {
	      Symbol *s = find_symbol_by_address (addr);
	      if (s)
		ad->name = s->name;
	    }
	}

      c = c->key.next;
    }
}

/* ------------------------------------------------------------------------ */

static void
name_all_chains (void)
{
  int i;

  fputs ("| retrieving function names for addresses ...", logfile);
  fflush (logfile);

  for (i = 0; i < num_chains; i++)
    name_chain (chains[i]);

  fputs (" done.   |\n", logfile);
  fflush (logfile);
}

/* ------------------------------------------------------------------------ */
/* ------------------------------------------------------------------------ */
/* This part of the code is very unix like:
 * We fork a child that executes gdb and sends us information about the
 * file and line number of addresses.
 */
/* ------------------------------------------------------------------------ */
/* ------------------------------------------------------------------------ */

/* parse an answer from gdb to a `info line' command and insert this info
 * into the given callchain if the answer is valid.
 */

static void
parseGdbInfoLineAnswer (CallChain c, char *buffer)
{
  AddrData *addr_data = c->addr_data;
  assert (addr_data);

  assert (addr_data->state != FIELDS_ARE_VALID);

  if (!(buffer = strtok (buffer, " ")))
    return;

  if (strcmp (buffer, "No") == 0)
    return;			/* "No symbol information" */
  if (strcmp (buffer, "Line") != 0)
    return;			/* be silent otherwise */

  if (!(buffer = strtok (0, " ")))
    return;			/* search for line number */

  addr_data->lineno = atoi (buffer);

  /* skip characters until `"' */

  if (!(buffer = strtok (0, "\"")))
    return;
  if (!(buffer = strtok (0, "\"")))
    return;			/* search for file name */

  addr_data->file = find_string (buffer);

  /* should test range and function name too ... */
}

/* ------------------------------------------------------------------------ */
/* ------------------------------------------------------------------------ */

/* parse a string containing a demangled name with the syntax:
 *
 *        ^ [^'<']* '<' demangled_name '+' .* '>' .* $
 *
 * and insert 
 */

static void
parseGdbDemangledInfo (CallChain c, char *buffer)
{
  size_t len = 0;
  AddrData *addr_data = c->addr_data;
  assert (addr_data);

  if (addr_data->alternative_name)
    return;

  /* if buffer ends with '>' then remove it, because it doesn't
   * belong to the symbols name...
   * (Henning Moll)
   */
  if ((len = strlen (buffer)) > 0 && (buffer[len - 1] == '>'))
    {
      /* this is only neccessary if the demangled_name is NOT 
       * followed by a '+' sign...
       * Don't know if that could ever be the case...
       * (Henning Moll)
       */
      buffer[len - 1] = 0;
    }
  if (!(buffer = strtok (buffer, "<")))
    return;
  /*
   * Since '>' may also be valid for c++-symbols we cannot
   * use it to find the end of demangled_name, so it is
   * removed from the following strtok call...
   * (Henning Moll)
   */
  if (!(buffer = strtok (0, "+")))
    return;

  if (!addr_data->name || strcmp (addr_data->name, buffer) != 0)
    {
      assert (!addr_data->alternative_name);	/* else garbage */
      addr_data->alternative_name = find_string (buffer);
    }
}

static void
dump_chain (FILE * dump_file, CallChain c)
{
  while (c)
    {
      AddrData *ad = c->addr_data;

      if (ad && ad->state == NOT_WRITTEN)
	{
	  if (ad->key == 0 ||
	      (!load_dynlibs_with_gdb && is_library_pc (ad->key)))
	    {
	      ad->state = FIELDS_ARE_VALID;
	      continue;
	    }
	  else
	    {
	      fprintf (dump_file,
		       "info line * 0x%08x\n", (unsigned) ad->key - 1);

	      ad->state = WRITTEN;

#if !defined(NM_DEMANGLES_WELL)
	      if (1)
#else
	      if (is_library_pc (c->key.addr))
#endif
		{
		  fprintf (dump_file, "p (void(*)()) 0x%08x\n",
			   (unsigned) c->key.addr);
		}
	    }
	}

      c = c->key.next;
    }
}

/* ------------------------------------------------------------------------ */

static void
dump_chains (FILE * dump_file)
{
  CallChain *c;
  for (c = chains; *c; c++)
    dump_chain (dump_file, *c);
}

/* ------------------------------------------------------------------------ */
/* return 1 on error */

static int
undump_chain_info (FILE * gdb_pipe, CallChain c)
{
  while (c)
    {
      AddrData *ad = c->addr_data;

      if (ad && ad->state != FIELDS_ARE_VALID)
	{
	  /* OLD: Why does gdb answer on several lines? So we have to merge
	   * several lines before we present it to parseGdbInfoLineAnswer.
	   *
	   * NOW: Since we use 'set width 0' gdb doesn't answer on several
	   * lines anymore. So we can drop the merging. (Henning Moll)
	   */

	  if (readLine (gdb_pipe, buffer, MAXBUFFER))
	    {
	      parseGdbInfoLineAnswer (c, buffer);
	      ad->state = FIELDS_ARE_VALID;
	    }
	  else
	    {
	      fputs (" @$#!|&^              |\n", logfile);
	      callchain_msg ("could not get all info from gdb\n");
	      return 1;
	    }

#if !defined(NM_DEMANGLES_WELL)
	  if (1)
#else
	  if (is_library_pc (c->key.addr))
#endif
	    {
	      if (readLine (gdb_pipe, buffer, MAXBUFFER))
		{
		  parseGdbDemangledInfo (c, buffer);
		}
	    }
	}

      c = c->key.next;
    }

  return 0;
}

/* ------------------------------------------------------------------------ */
/* return 1 on error */

static int
undump_chains_info (FILE * gdb_pipe)
{
  CallChain *c;
  for (c = chains; *c; c++)
    if (undump_chain_info (gdb_pipe, *c))
      return 1;

  return 0;
}

/* ------------------------------------------------------------------------ */
/* If the argument is non zero then only the information for that CallChain
 * is generated. Otherwise line info is generated for all CallChains that
 * have allocated data.
 */

static int
insert_file_info_in_chains_from_pipe (CallChain c)
{
  FILE *dump_file, *gdb_pipe;
  int error = 0;

  char tmp_file_name[200];
  char *cmd;
  char *p;

  sprintf (tmp_file_name, "/tmp/ccmalloc.dump.%d", (int) getpid ());

  dump_file = fopen (tmp_file_name, "w");
  if (!dump_file)
    {
      fputs (" @$#!|&^              |\n", logfile);
      callchain_msg ("could not write to `%s'\n", tmp_file_name);
      return 1;
    }
  /* gdb should not strip lines (Henning Moll) */
  fprintf (dump_file, "set width 0\n");


  if (load_dynlibs_with_gdb)
    /* It Works For Me (tm) (Johannes Keukelaar) */
    fprintf (dump_file, "break _init\nrun\n");
  /* write a sentinel: different gdb versions produce different output
   * for commands 'set width 0', 'b _init' and  'run'
   * sometimes (?) a additional line 'Current language: ...' appears
   * So we need a sentinel to eat up all that stuff... (Henning Moll)
   */
  fprintf (dump_file, "p/x %s\n", BASIC_SPELL_STR);


  if (c)
    dump_chain (dump_file, c);
  else
    dump_chains (dump_file);

  /* write a sentinel for checking that all went right
   */
  fprintf (dump_file, "p/x %s\n", BASIC_SPELL_STR);

  fprintf (dump_file, "quit\n");	/* avoid Broken Pipe message */

  fclose (dump_file);

  cmd = (char *) malloc (strlen (file_name) + 200);
  sprintf (cmd,
	   "gdb -nx -q -batch -x %s %s 2>/dev/null",
	   tmp_file_name, file_name);

  gdb_pipe = popen (cmd, "r");

  /* Now eat up everything until we reach the first sentinel (Henning Moll) */
  while (1)
    {
      if (readLine (gdb_pipe, buffer, MAXBUFFER))
	{
	  if (!(!(p = strtok (buffer, " ")) ||	/* "$1" */
		!(p = strtok (0, " ")) ||	/* "=" */
		!(p = strtok (0, " ")) ||	/* BASIC_SPELL_STR */
		strncmp (p, BASIC_SPELL_STR, strlen (p)) != 0))
	    {
	      break;
	    }
	}
      else
	{
	  callchain_msg
	    ("oops, something went wrong while reading gdb output\n");
	  error = 1;
	  goto SAVE_EXIT_00;
	}
    }
  if (gdb_pipe)
    {
      int error;

      if (c)
	error = undump_chain_info (gdb_pipe, c);
      else
	error = undump_chains_info (gdb_pipe);

      if (error)
	{
	  callchain_msg
	    ("oops, something went wrong while undumping file info\n");
	  error = 1;
	  goto SAVE_EXIT_00;
	}
      else
	{
	  /* try to read sentinel that should be the following line
	   * $1 = BASIC_SPELL_STR
	   */

	  if (!readLine (gdb_pipe, buffer, MAXBUFFER) || !(p = strtok (buffer, " ")) ||	/* "$1" */
	      !(p = strtok (0, " ")) ||	/* "=" */
	      !(p = strtok (0, " ")) ||	/* BASIC_SPELL_STR */
	      strncmp (p, BASIC_SPELL_STR, strlen (p)) != 0)
	    {
	      callchain_msg
		("oops, something went wrong when reading from gdb\n");
	      pclose (gdb_pipe);
	      error = 1;
	      goto SAVE_EXIT_00;
	    }
	}

      pclose (gdb_pipe);
    }
  else
    {
      fputs (" @$#!|&^              |\n", logfile);
      callchain_msg ("could not open pipe to gdb\n");
      error = 1;
      goto SAVE_EXIT_00;
    }

SAVE_EXIT_00:

  remove (tmp_file_name);
  free (cmd);
  return error;
}

static void
insert_file_info_in_chains (void)
{
  int error = 0;

  if (!file_info)
    return;

  fputs ("| reading file info from gdb ...", logfile);

  error = insert_file_info_in_chains_from_pipe (0);

  if (!error)
    fputs (" done.                |\n", logfile);
  fflush (logfile);
}

/* ------------------------------------------------------------------------ */

/* this does the `pretty printing' of callchains'
 */

/* ------------------------------------------------------------------------ */

static void
tab (FILE * file, int t, char c)
{
  int i;
  for (i = 0; i < t; i++)
    putc (c, file);
}

static void
_print_chain (FILE * file, CallChain c,
	      char *prefix, char *lastprefix, char *lastlastprefix,
	      int first_indent, int other_indent)
{
  if (empty_lines)
    {
      fputs (prefix, file);
      putc ('\n', file);
    }

  if (c == 0)
    {
      if (lastprefix)
	fputs (lastprefix, file);
      tab (file, first_indent, '-');
      fputs ("> 0x????????\n", file);
    }
  else
    {
      int not_first = 0;

      if (c->key.next)
	{
	  if (prefix)
	    fputs (prefix, file);
	  tab (file, first_indent + 2, ' ');
	}
      else
	{
	  if (lastprefix)
	    fputs (lastprefix, file);
	  tab (file, first_indent, '-');
	  fputs ("> ", file);
	}

      do
	{
	  char *name;

	  if (!c->addr_data)
	    name = "???";
	  else if (c->addr_data->alternative_name)
	    name = c->addr_data->alternative_name;
	  else if (c->addr_data->name)
	    name = c->addr_data->name;
	  else
	    name = "???";

	  if (c->key.addr)
	    fprintf (file, "0x%08lx ", (long) c->key.addr);
	  else
	    fputs ("0x???????? ", file);

	  if (!print_on_one_line)
	    fputs ("in ", file);

	  putc ('<', file);
	  fputs (name, file);
	  putc ('>', file);

	  if (c->addr_data && c->addr_data->file)
	    {
	      if (!print_on_one_line)
		{
		  putc ('\n', file);

		  if (c->key.next)
		    {
		      if (prefix)
			fputs (prefix, file);
		    }
		  else
		    {
		      if (lastlastprefix)
			fputs (lastlastprefix, file);
		    }

		  tab (file,
		       (not_first ? other_indent : first_indent) + 2, ' ');

		  /*0x12345678 in */
		  fputs ("           ", file);

		  fprintf (file, "at %s:%d",
			   c->addr_data->file, c->addr_data->lineno);
		}
	      else
		{
		  fprintf (file,
			   " %s:%d", c->addr_data->file,
			   c->addr_data->lineno);
		}
	    }

	  c = c->key.next;

	  if (c)
	    {
	      putc ('\n', file);
	      if (empty_lines)
		{
		  fputs (prefix, file);
		  putc ('\n', file);
		}

	      if (!not_first)
		not_first = 1;

	      if (c->key.next != 0)
		{
		  if (prefix)
		    fputs (prefix, file);
		  tab (file,
		       (not_first ? other_indent : first_indent) + 2, ' ');
		}
	      else
		{
		  if (lastprefix)
		    fputs (lastprefix, file);
		  tab (file, (not_first ? other_indent : first_indent), '-');
		  fputs ("> ", file);
		}
	    }
	}
      while (c);

      putc ('\n', file);
      if (empty_lines)
	{
	  fputs (lastlastprefix, file);
	  putc ('\n', file);
	}
    }
}

/* ------------------------------------------------------------------------ */

/* store a new Symbol_ in the symbol table `symtab'. Do not overwrite
 * already defined symbols.
 */

static void
new_Symbol (char *name, caddr_t addr)
{
  Symbol *symbol = (Symbol *) malloc (sizeof (Symbol));
  symbol->name = name;
  symbol->addr = addr;

  if (insert_into_HashTable (symtab, symbol))
    {
      if (debug_flag)
	{
	  callchain_msg
	    ("multiple occurence of symbol %s at address 0x%08x\n",
	     symbol->name, (unsigned) symbol->addr);
	  free (symbol);
	}
    }
}

/* ------------------------------------------------------------------------ */

/* this is `nm' specifique
 */

static int
is_valid_symbol_type (char *p)
{
  switch (p[0])
    {
    case 't':
    case 'T':
    case 'w':
    case 'W':
      return !p[1];
    default:
      return 0;
    }
}

/* ------------------------------------------------------------------------ */

static int
is_valid_symbol_name (const char *s)
{
  return strchr (s, '.') == NULL;
}

/* ------------------------------------------------------------------------ */

/* `parseNmLine' reads a line from `nm' with the expected syntax mentioned
 * in the function body. If the line conforms to the expected syntax
 * and the symbol described in that line has the right type (as defined
 * by `is_valid_symbol_type' than it is inserted in the symbol table 
 * (symtab) with `new_Symbol'. Otherwise nothing happens. Especially if
 * the line does not conform to the expected syntax than this line is
 * skipped *silently*.
 *
 * On the fly we also check if the symbols belong to currently running
 * program. If we found a counterexample we return false. Otherwise
 * we always return true.
 */

/* Only the symbols `main', `ccmalloc_malloc', and `ccmalloc_free' are
 * tested:
 */

int main (void);
void *ccmalloc_malloc (size_t);
void ccmalloc_free (void *);

#define MAIN            "main"
#define CCMALLOC_MALLOC "ccmalloc_malloc"
#define CCMALLOC_FREE   "ccmalloc_free"

/*------------------------------------------------------------------------*/

static int
symtab_contains_important_symbols (void)
{
  HashTableIterator it;
  int found_main = 0, found_malloc = 0, found_free = 0;

  for (setup_HashTableIterator (symtab, &it);
       !is_done_HashTableIterator (&it); increment_HashTableIterator (&it))
    {
      Symbol *s = (Symbol *) get_data_from_HashTableIterator (&it);

      if (strcmp (s->name, MAIN) == 0)
	found_main = 1;
      else if (strcmp (s->name, CCMALLOC_MALLOC) == 0)
	found_malloc = 1;
      else if (strcmp (s->name, CCMALLOC_FREE) == 0)
	found_free = 1;
    }

  return found_main && found_malloc && found_free;
}

static int
parseNmLine (char *buffer)
{
  /* syntax of a line: ["0x"]<hexnumber><space><string><space><C++-proto> */

  char *p, *name;
  caddr_t addr;

  if (!(p = strtok (buffer, " \t")))
    return 1;
  if (p[0] == '0' && p[1] == 'x')
    p += 2;			/* skip '0x' (defensive) */
  addr = (caddr_t) strtol (p, 0, 16);

  if (!(p = strtok (0, " \t")))
    return 1;
  if (!is_valid_symbol_type (p))
    return 1;
  if (!(p = strtok (0, "")))
    return 1;
  if (!is_valid_symbol_name (p))
    return 1;

  if ((strcmp (p, MAIN) == 0 && addr != (caddr_t) main) ||
      (strcmp (p, CCMALLOC_FREE) == 0 && addr != (caddr_t) ccmalloc_free) ||
      (strcmp (p, CCMALLOC_MALLOC) == 0 && addr != (caddr_t) ccmalloc_malloc))
    return 0;

  name = find_string (p);
  new_Symbol (name, addr);

  return 1;
}

/* ------------------------------------------------------------------------ */

const char *nm_options =
#ifdef OS_IS_SOLARIS		/* SunOS 5.X */
  /* -C   demangle C++ identifiers
   * -p   sparse output like on sunos 4.3.1
   * -x   hexadezimal output with leading '0x'
   *      used because nm for sunos has hexadezimal
   *      output (but without leading '0x')
   */
  "-C -p -x";

#else
#ifdef OS_IS_LINUX
  /* -C               demangle C++ identifiers
   * --defined-only   we do not need external symbols
   *
   *  default for linux is hexadezimal output
   */
  "-C --defined-only";

#else
  /* This is the least denominator. */
  "";

#endif /* OS_IS_LINUX */
#endif /* OS_IS_SOLARIS */

/* ------------------------------------------------------------------------ */

/* Opens a pipe to `nm' with the file name `name' as argument, reads from
 * this pipe all text symbols and stores them in the symbol table `symtab'.
 * It returns true if the file with the given name exists and the symbols
 * in this file match. 
 */

static int
get_symtab (char *name)
{
  FILE *pipe;
  int right_file = 0;

  sprintf (buffer, "nm %s %s 2>/dev/null", nm_options, name);

  if ((pipe = popen (buffer, "r")) == 0)
    ccmalloc_abort ("get_symtab: could not execute `%s'\n", buffer);

  /* prepare symtab */

  while (readLine (pipe, buffer, MAXBUFFER) &&
	 (right_file = parseNmLine (buffer)))
    ;

  pclose (pipe);

  return right_file && symtab_contains_important_symbols ();
}

/* ------------------------------------------------------------------------ */

/* support functions for symbol table `symtab' and sorted array symbols
 */

static int
cmp_symbol_addr_qsort (const void *_a, const void *_b)
{
  Symbol *a = *(Symbol **) _a, *b = *(Symbol **) _b;

  if (a == b)
    return 0;

  if (a->addr != b->addr)
    {
      if (a->addr < b->addr)
	{
	  return -1;
	}
      else
	return 1;
    }
  else
    return strcmp (a->name, b->name);
}

/* ------------------------------------------------------------------------ */

static int
cmp_symbol_names (const void *_a, const void *_b)
{
  Symbol *a = (Symbol *) _a, *b = (Symbol *) _b;
  int cmp;

  if (a == b)
    return 0;

  if (a->name == b->name || (cmp = strcmp (a->name, b->name)) == 0)
    {
      if (a->addr != b->addr)
	{
	  if (a->addr < b->addr)
	    {
	      return -1;
	    }
	  else
	    return 1;
	}
      else
	return 0;
    }
  else
    return cmp;
}

/* ------------------------------------------------------------------------ */

static void
_freeSymbol (Symbol * s)
{
  free (s);
}

/* ------------------------------------------------------------------------ */

static int
_hash_Symbol (Symbol * s)
{
  return hashpjw_HashTable (s->name) ^ ((int) s->addr);
}

/* ------------------------------------------------------------------------ */

/* wrap them in appropriate cast macros */

#define cmpNames ((int(*)(void*,void*)) cmp_symbol_names)
#define hashName ((int(*)(void*))_hash_Symbol)
#define freeSymbol ((void(*)(void*)) _freeSymbol)

/* ------------------------------------------------------------------------ */

/* Initializes the sorted array `symbols' from the symbol table `symtab'.
 * `symbols' is sorted with respect to the address of the symbols.
 * This enables fast access to a symbol through its address
 * (compare with `name_chain').
 */

static void
copy_symtab_into_symbols (void)
{
  HashTableIterator it;
  int pos;

  if (!symtab || !(num_symbols = get_size_of_HashTable (symtab)))
    return;

  symbols = (Symbol **) malloc (sizeof (Symbol *) * (num_symbols + 1));

  for (pos = 0, setup_HashTableIterator (symtab, &it);
       !is_done_HashTableIterator (&it);
       increment_HashTableIterator (&it), pos++)
    {
      Symbol *s = (Symbol *) get_data_from_HashTableIterator (&it);
      symbols[pos] = s;
    }

  assert (pos == num_symbols);
  symbols[pos] = 0;

  qsort (symbols, num_symbols, sizeof (Symbol *), cmp_symbol_addr_qsort);
}

/* ------------------------------------------------------------------------ */

/* Install `entry_start', `entry_end', `text_start', and `text_end'. These
 * addresses are used by `backtrace()' to find the entry point of a
 * callchain with the macro `isEntryPc'.
 */

static void
get_bounds (void)
{
  int i;

  if (symtab && num_symbols > 0)
    {
      for (i = 0; i < num_symbols; i++)
	{
	  if (strcmp (symbols[i]->name, "_start") == 0)
	    {
	      entry_start = symbols[i++]->addr;
	      entry_end = symbols[i]->addr;
	      break;
	    }
	}

      text_start = symbols[0]->addr;
      text_end = symbols[num_symbols - 1]->addr;

      have_bounds = 1;
    }
  else
    have_bounds = 0;
}

/* ------------------------------------------------------------------------ */

static void
test_for_garbage_at_eol (void)
{
  char *buffer;
  if ((buffer = strtok (0, " \t")))
    callchain_error ("%s:%d: garbage at end of line\n",
		     startup_file_name, startup_file_lineno);
}

/* ------------------------------------------------------------------------ */

/* Parses a number argument of a command in the startup file with the
 * given name (for error reporting) and stores the value of the parsed string
 * in the flag. If the buffer is empty then 1 is used.
 */

static void
parseNumberFlag (char *buffer, char *name, int *flag)
{
  (void) name;

  if ((buffer = strtok (0, " \t")))
    {
      *flag = atoi (buffer);
      test_for_garbage_at_eol ();
    }
  else
    *flag = 1;
}

/* ------------------------------------------------------------------------ */

/* Parses a boolean argument of a command in the startup file with the
 * given name (for error reporting) and stores the value of the parsed string
 * in the flag. If the buffer is empty then the flag is set to 1 (true).
 */

static void
parseBooleanFlag (char *buffer, char *name, int *flag)
{
  if (!(buffer = strtok (0, " \t")))
    *flag = 1;
  else
    {
      if (strcmp (buffer, "1") == 0)
	{
	  *flag = 1;
	  test_for_garbage_at_eol ();
	}
      else if (strcmp (buffer, "0") == 0)
	{
	  *flag = 0;
	  test_for_garbage_at_eol ();
	}
      else
	callchain_error ("%s:%d: expected boolean argument for `%s'\n",
			 startup_file_name, startup_file_lineno, name);
    }
}

/* ------------------------------------------------------------------------ */

/* Parses a call chain specification a la dont-log-chain and only-log-chain.
 */
static void
parseCallChain (char *buffer, int *num_chains, DontLogChain *** chains)
{
  char *skip_name, *end_of_name, *colon;
  DontLogChain *chain;
  int num;
  (*num_chains)++;
  if (*num_chains > 1)
    {
      DontLogChain **nw =
	(DontLogChain **) malloc (*num_chains * sizeof (DontLogChain *));
      memcpy (nw, *chains, (*num_chains - 1) * sizeof (DontLogChain *));
      free (*chains);
      *chains = nw;
    }
  else
    {
      *chains = (DontLogChain **) malloc (sizeof (DontLogChain *));
    }
  num = 1;
  skip_name = buffer;
  while ((skip_name = strchr (skip_name, CHAIN_DELIMITER)))
    {
      skip_name++;
      num++;
    }
  (*chains)[*num_chains - 1] =
    (DontLogChain *) malloc (sizeof (DontLogChain) +
			     (num - 1) * sizeof (FuncOrFile));
  chain = (*chains)[*num_chains - 1];
  chain->num = num;
  skip_name = buffer;
  end_of_name = buffer;
  num = 0;
  do
    {
      end_of_name = strchr (end_of_name, CHAIN_DELIMITER);
      if (end_of_name)
	*end_of_name = '\0';
      colon = strchr (skip_name, ':');
      if (colon && colon[1] == ':')
	{
	  /*
	   * ah, we found class symbol name
	   * (Henning Moll)
	   */
	  colon = strchr (colon + 2, ':');
	}
      if (colon)
	{
	  *colon = '\0';
	  colon++;
	  chain->funcs[num].line = atoi (colon);
	}
      else
	chain->funcs[num].line = -1;
      chain->funcs[num].name = find_string (skip_name);
      if (end_of_name)
	end_of_name++;
      skip_name = end_of_name;
      num++;
    }
  while (end_of_name);
}

/* ------------------------------------------------------------------------ */

/* This is the parser of a line read from the startup file.
 */

static void
parseStartupFileLine (char *buffer)
{
  startup_file_lineno++;

  if (!(buffer = strtok (buffer, " \t")))
    return;			/* just skip empty lines */

  if (buffer[0] == '%' || buffer[0] == '#')
    return;			/* skip comments */

  if (strcmp (buffer, "file") == 0)
    {
      if (!(buffer = strtok (0, " \t")))
	callchain_msg ("%s:%d: argument to `file' is missing\n",
		       startup_file_name, startup_file_lineno);
      else
	{
	  file_name = find_string (buffer);
	  test_for_garbage_at_eol ();
	}
    }
  else if (strcmp (buffer, "log") == 0)
    {
      if (logfilename)
	callchain_msg ("%s:%d: Use only one of log or logpid\n",
		       startup_file_name, startup_file_lineno);

      if (!(buffer = strtok (0, " \t")))
	callchain_msg ("%s:%d: argument to `log' is missing\n",
		       startup_file_name, startup_file_lineno);
      else
	{
	  int l = strlen (buffer);

	  if (l >= 3 && strcmp (buffer + l - 3, ".gz") == 0)
	    compressed_logfile = GZIP_LOGFILE;
	  else if (l >= 2 && strcmp (buffer + l - 2, ".Z") == 0)
	    compressed_logfile = COMPRESS_LOGFILE;
	  else
	    compressed_logfile = NO_COMPRESSED_LOGFILE;

	  logfilename = find_string (buffer);
	  test_for_garbage_at_eol ();
	}
    }
  else if (strcmp (buffer, "logpid") == 0)
    {
      if (logfilename)
	callchain_msg ("%s:%d: Use only one of log or logpid\n",
		       startup_file_name, startup_file_lineno);

      if (!(buffer = strtok (0, " \t")))
	callchain_msg ("%s:%d: argument to `logpid' is missing\n",
		       startup_file_name, startup_file_lineno);
      else
	{
	  int l = strlen (buffer);
	  char *pid_buf;

	  if (l >= 3 && strcmp (buffer + l - 3, ".gz") == 0)
	    compressed_logfile = GZIP_LOGFILE;
	  else if (l >= 2 && strcmp (buffer + l - 2, ".Z") == 0)
	    compressed_logfile = COMPRESS_LOGFILE;
	  else
	    compressed_logfile = NO_COMPRESSED_LOGFILE;

	  pid_buf = find_string (buffer);
	  l = strlen (pid_buf);
	  /* pid < 9 digits ! */
	  logfilename = (char *) malloc ((l + 10) * sizeof (char));
	  strcpy (logfilename, pid_buf);
	  sprintf (pid_buf, ".%d", (int) getpid ());

	  switch (compressed_logfile)
	    {
	    case GZIP_LOGFILE:
	      strcpy (logfilename + l - 3, pid_buf);
	      strcat (logfilename, ".gz");
	      break;
	    case COMPRESS_LOGFILE:
	      strcpy (logfilename + l - 2, pid_buf);
	      strcat (logfilename, ".Z");
	      break;
	    default:
	      strcat (logfilename, pid_buf);
	      break;
	    }

	  test_for_garbage_at_eol ();
	}
    }
  else if (strcmp (buffer, "only-log-chain") == 0)
    {
      if (!(buffer = strtok (0, "")))
	{
	  /* No arguments! */
	  parseCallChain ("", &num_only_log_chains, &only_log_chains);
	}
      else
	{
	  //ignore leading whitespace
	  buffer = buffer + strspn (buffer, " \t");
	  parseCallChain (buffer, &num_only_log_chains, &only_log_chains);
	  test_for_garbage_at_eol ();
	}
    }
  else if (strcmp (buffer, "dont-log-chain") == 0)
    {
      if (!(buffer = strtok (0, "")))
	{
	  /* No arguments! */
	  parseCallChain ("", &num_dont_log_chains, &dont_log_chains);
	}
      else
	{
	  //ignore leading whitespace
	  buffer = buffer + strspn (buffer, " \t");
	  parseCallChain (buffer, &num_dont_log_chains, &dont_log_chains);
	  test_for_garbage_at_eol ();
	}
    }
  else if (strcmp (buffer, "set") == 0)
    {
      if (!(buffer = strtok (0, " \t")))
	callchain_error ("%s:%d: argument to `set' is missing\n",
			 startup_file_name, startup_file_lineno);
      else
	{
	  if (strcmp (buffer, "keep-deallocated-data") == 0)
	    parseBooleanFlag (buffer,
			      "keep-deallocated-data",
			      &keep_deallocated_data);
	  else if (strcmp (buffer, "load-dynlibs") == 0)
	    parseBooleanFlag (buffer, "load-dynlibs", &load_dynlibs_with_gdb);
	  else if (strcmp (buffer, "align-8-byte") == 0)
	    parseBooleanFlag (buffer, "align-8-byte",
			      &align_on_8_byte_boundary);
	  else if (strcmp (buffer, "statistics") == 0)
	    parseBooleanFlag (buffer, "statistics", &callchain_statistics);
	  else if (strcmp (buffer, "only-count") == 0)
	    parseBooleanFlag (buffer, "only-count", &only_count);
	  else if (strcmp (buffer, "silent") == 0)
	    parseBooleanFlag (buffer, "silent", &silent_startup);
	  else if (strcmp (buffer, "print-on-one-line") == 0)
	    parseBooleanFlag (buffer, "print-on-one-line",
			      &print_on_one_line);
	  else if (strcmp (buffer, "additional-line") == 0)
	    parseBooleanFlag (buffer, "additional-line", &empty_lines);
	  else if (strcmp (buffer, "chain-length") == 0)
	    parseNumberFlag (buffer, "chain-length", &chain_length);
	  else if (strcmp (buffer, "sort-by-size") == 0)
	    parseBooleanFlag (buffer, "sort-by-size", &sort_by_size);
	  else if (strcmp (buffer, "sort-by-wasted") == 0)
	    parseBooleanFlag (buffer, "sort-by-wasted", &sort_by_wasted);
	  else if (strcmp (buffer, "print-addresses") == 0)
	    parseBooleanFlag (buffer, "print-addresses",
			      &print_addresses_flag);
	  else if (strcmp (buffer, "check-overwrites") == 0)
	    parseNumberFlag (buffer, "check-overwrites", &check_overwrites);
	  else if (strcmp (buffer, "check-underwrites") == 0)
	    parseNumberFlag (buffer, "check-underwrites", &check_underwrites);
	  else if (strcmp (buffer, "check-free-space") == 0)
	    parseBooleanFlag (buffer, "check-free-space", &check_free_space);
	  else if (strcmp (buffer, "check-start") == 0)
	    parseNumberFlag (buffer, "check-start", &check_start);
	  else if (strcmp (buffer, "check-interval") == 0)
	    parseNumberFlag (buffer, "check-interval", &check_interval);
	  else if (strcmp (buffer, "file-info") == 0)
	    parseBooleanFlag (buffer, "file-info", &file_info);
	  else if (strcmp (buffer, "debug") == 0)
	    parseBooleanFlag (buffer, "debug", &debug_flag);
	  else if (strcmp (buffer, "library-chains") == 0)
	    parseBooleanFlag (buffer, "library-chains", &library_chains);
	  else if (strcmp (buffer, "continue") == 0)
	    parseBooleanFlag (buffer, "continue", &continue_flag);
	  else if (strcmp (buffer, "only-wasting-alloc") == 0)
	    parseBooleanFlag (buffer, "only-wasting-alloc",
			      &only_wasting_alloc);
	  else
	    callchain_msg ("%s:%d: unknown flag `%s' for `set'\n",
			   startup_file_name, startup_file_lineno, buffer);
	}
    }
  else
    callchain_msg ("%s:%d: unknown command `%s'\n",
		   startup_file_name, startup_file_lineno, buffer);
}

/* ------------------------------------------------------------------------ */

static void
open_logfile (void)
{
  if (compressed_logfile == NO_COMPRESSED_LOGFILE)
    {
      if (logfilename)
	{
	  if (strcmp (logfilename, "-") == 0 ||
	      strcmp (logfilename, "stdout") == 0)
	    {
	      logfile = stdout;
	    }
	  else
	    {
	      logfile = fopen (logfilename, "w");
	      if (!logfile)
		{
		  callchain_msg ("could not open `%s' as log file\n",
				 logfilename);
		  logfile = stderr;
		}
	    }
	}
      else
	logfile = stderr;
    }
  else
    {
      char *cmd_buffer;
      const char *compress_cmd;

      if (compressed_logfile == GZIP_LOGFILE)
	compress_cmd = "gzip -c";
      else
	compress_cmd = "compress";

      assert (logfilename);

      cmd_buffer = (char *) malloc (strlen (logfilename) + 30);
      sprintf (cmd_buffer, "%s > %s", compress_cmd, logfilename);

      logfile = popen (cmd_buffer, "w");
      if (!logfile)
	{
	  callchain_msg ("could not open `%s' (using stderr)\n", cmd_buffer);
	  logfile = stderr;
	  compressed_logfile = NO_COMPRESSED_LOGFILE;
	}

      free (cmd_buffer);
    }
}

/* ------------------------------------------------------------------------ */

static void
close_logfile (void)
{
  if (compressed_logfile == NO_COMPRESSED_LOGFILE)
    {
      if (logfile != stderr && logfile != stdout)
	fclose (logfile);
    }
  else
    pclose (logfile);
}

/* ------------------------------------------------------------------------ */
/* `read_startup_file' is the first function executed by this library.
 */

static void
read_startup_file (void)
{
  FILE *startup_file;

  startup_file = fopen (startup_file_name, "r");

  if (!startup_file)
    {
      char *home = getenv ("HOME");

      if (!home)
	return;

      if (strlen (home) + strlen (startup_file_name) + 2 >= MAXBUFFER)
	return;

      strcpy (buffer, home);
      strcat (buffer, "/");
      strcat (buffer, startup_file_name);

      startup_file = fopen (buffer, "r");

      if (!startup_file)
	{
	  startup_file_name = ".ccmalloc (but not found)";
	}
      else
	startup_file_name = "~/.ccmalloc";
    }

  if (startup_file)
    {
      while (readLine (startup_file, buffer, MAXBUFFER))
	parseStartupFileLine (buffer);

      fclose (startup_file);
    }

  open_logfile ();
}

/* ------------------------------------------------------------------------ */

static void
banner (void)
{
  char *lfn, *date_str, *osinfo_str;
  time_t t;
  struct utsname osinfo;

  lfn = (char *) (logfilename ? logfilename : "stderr");

  (void) time (&t);
  date_str = strtok (ctime (&t), "\n");

  uname (&osinfo);
  osinfo_str = (char *) malloc (strlen (osinfo.sysname) + 1 +
				strlen (osinfo.release) + 1 +
				strlen (osinfo.machine) + 1 +
				strlen ("on") + 1 +
				strlen (osinfo.nodename) + 1);

  sprintf (osinfo_str, "%s %s %s on %s",
	   osinfo.sysname, osinfo.release, osinfo.machine, osinfo.nodename);

  fputs
    (".--------------------------------------------------------------------------.\n"
     "|================ ccmalloc-" VERSION
     " (C) 1997-2003 Armin Biere ================|\n"
     "+--------------------------------------------------------------------------+\n",
     logfile);
  fprintf (logfile, "| executable       = %-53s |\n",
	   file_name ? file_name : "a.out");
  fprintf (logfile, "| startup file     = %-53s |\n", startup_file_name);
  fprintf (logfile, "| log file         = %-53s |\n", lfn);
  fprintf (logfile, "| start time       = %-53s |\n", date_str);
  fprintf (logfile, "| operating system = %-53s |\n", osinfo_str);

  free (osinfo_str);

  fprintf (logfile,
	   "+--------------------------------------------------------------------------+\n");
  fprintf (logfile,
	   "| only-count        = %-11d  keep-deallocated-data = %-15d |\n",
	   only_count, keep_deallocated_data);
  fprintf (logfile,
	   "| check-interval    = %-11d  check-free-space      = %-15d |\n",
	   check_interval, check_free_space);
  fprintf (logfile,
	   "| check-start       = %-11d  file-info             = %-15d |\n",
	   check_start, file_info);
  fprintf (logfile,
	   "| chain-length      = %-11d  additional-line       = %-15d |\n",
	   chain_length, empty_lines);
  fprintf (logfile,
	   "| check-underwrites = %-11d  print-addresses       = %-15d |\n",
	   check_underwrites, print_addresses_flag);
  fprintf (logfile,
	   "| check-overwrites  = %-11d  print-on-one-line     = %-15d |\n",
	   check_overwrites, print_on_one_line);
  fprintf (logfile,
	   "| sort-by-wasted    = %-11d  sort-by-size          = %-15d |\n",
	   sort_by_wasted, sort_by_size);
  fprintf (logfile,
	   "| # only-log-chain  = %-11d  continue              = %-15d |\n",
	   num_only_log_chains, continue_flag);
  fprintf (logfile,
	   "| # dont-log-chain  = %-11d  statistics            = %-15d |\n",
	   num_dont_log_chains, callchain_statistics);
  fprintf (logfile,
	   "| debug             = %-11d  library-chains        = %-15d |\n",
	   debug_flag, library_chains);
  fprintf (logfile,
	   "| load-dynlibs      = %-11d  align-8-byte          = %-15d |\n",
	   load_dynlibs_with_gdb, align_on_8_byte_boundary);
  fprintf (logfile,
	   "| only-wasting-alloc= %-11d                                          |\n",
	   only_wasting_alloc);
  fputs
    ("`--------------------------------------------------------------------------'\n",
     logfile);
}

/* ------------------------------------------------------------------------ */

static void
search_cwd_for_executable (void)
{
  /* search current directory for matching executable */

  DIR *dir;
  callchain_msg ("trying to find executable in current directory ...\n");
  dir = opendir (".");

  for (;;)
    {
      struct dirent *e;

      if ((e = readdir (dir)) == NULL)
	{
	  closedir (dir);
	  free_HashTable (symtab);
	  symtab = 0;
	  break;
	}
      else
	{
	  struct stat s;
	  stat (e->d_name, &s);
	  if (!(S_ISDIR (s.st_mode)))
	    {
	      if ((s.st_mode & S_IFREG) &&
		  (s.st_mode & S_IREAD) && (s.st_mode & S_IEXEC))
		{
		  free_HashTable (symtab);
		  symtab =
		    new_HashTable (100, cmpNames, hashName, 0, freeSymbol, 0);

		  if (get_symtab (e->d_name))
		    {
		      copy_symtab_into_symbols ();
		      file_name = find_string (e->d_name);
		      closedir (dir);
		      if (silent_startup)
			callchain_msg ("using symbols from `%s'\n",
				       file_name);
		      break;
		    }
		}
	    }
	}

    }

  /* as the call to `search_cwd_for_executable' should always be the last
   * option we can report a failure here
   */

  if (symtab)
    {
      assert (file_name);

      callchain_msg ("(to speed up this search specify `file %s'\n",
		     file_name);
      callchain_msg (" in the startup file `%s')\n", startup_file_name);
    }
  else
    {
      callchain_msg ("Could not find an executable with valid symbols\n");
      callchain_msg ("Specify it with the `file' command\n");
      callchain_msg ("in the startup file `%s'\n", startup_file_name);
      callchain_msg ("or link `a.out' to this executable!\n");
    }
}

/* ------------------------------------------------------------------------ */
#ifdef CAN_GET_ARGV0
/* ------------------------------------------------------------------------ */
#ifdef OS_IS_LINUX
/* ------------------------------------------------------------------------ */
/* !!!!!uses the global buffer!!!!!
 */

static char *
find_argv0 (void)
{
  char my_cmdline_args_name[200];
  int linklen;

  sprintf (my_cmdline_args_name, "/proc/%d/exe", getpid ());
  linklen = readlink (my_cmdline_args_name, buffer, MAXBUFFER);
  if (linklen < 0)
    {
      callchain_msg ("could not readlink `%s'\n", my_cmdline_args_name);
      return 0;
    }
  /* readlink does not append a 0 */
  buffer[linklen] = '\0';
  return find_string (buffer);
}

/* ------------------------------------------------------------------------ */
#else
#ifdef OS_IS_SOLARIS
/* ------------------------------------------------------------------------ */

#include <fcntl.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>

#include <sys/types.h>
#include <sys/signal.h>
#include <sys/fault.h>
#include <sys/syscall.h>
#include <sys/procfs.h>

static struct prpsinfo procfs_info;

static char *
find_argv0 (void)
{
  char procfs_name[200];
  int fd;
  pid_t pid = getpid ();
  sprintf (procfs_name, "/proc/%d", (int) pid);
  fd = open (procfs_name, O_RDONLY);
  if (fd == -1)
    {
      callchain_msg ("could not open `%s'\n", procfs_name);
      return 0;
    }

  if (ioctl (fd, PIOCPSINFO, &procfs_info) == -1)
    {
      callchain_msg ("could not get argv[0]' from `%s'\n", procfs_name);
      close (fd);
      return 0;
    }

  close (fd);
  if (!procfs_info.pr_argv[0] || strlen (procfs_info.pr_argv[0]) == 0)
    return 0;
  else
    return find_string (procfs_info.pr_argv[0]);
}

/* ------------------------------------------------------------------------ */
#endif /* OS_IS_SOLARIS */
#endif /* OS_IS_LINUX */
#endif /* CAN_GET_ARGV0 */
/* ------------------------------------------------------------------------ */

static void
init_CallChain (void)
{
  symtab = new_HashTable (100, cmpNames, hashName, 0, freeSymbol, 0);

# ifdef CAN_GET_ARGV0
  {
    int match;
    char *argv0 = find_argv0 ();

    /* now test if `argv0' and `file_name' match */

    if (argv0)
      {
	if (file_name)
	  {
	    if (argv0[0] == '/' && file_name[0] == '/')
	      {
		/* `match=(argv0==file_name)' is not defensive */

		match = (strcmp (argv0, file_name) == 0);
	      }
	    else
	      {
		char *p = strrchr (argv0, '/');
		char *q = strrchr (file_name, '/');

		if (p)
		  p++;
		else
		  p = argv0;
		if (q)
		  q++;
		else
		  q = file_name;

		match = (strcmp (p, q) == 0);

		/* preference to absolut path names */

		if (match && argv0[0] == '/')
		  file_name = argv0;
	      }
	  }
	else
	  {
	    /* make them match */

	    match = 1;
	    file_name = argv0;
	  }
      }
    else
      match = 1;		/* argv0 == 0 */

    if (match)
      {
	if (get_symtab (file_name))
	  copy_symtab_into_symbols ();
	else
	  search_cwd_for_executable ();
      }
    else
      {
	callchain_msg ("\n  file-name=%s and\n"
		       "  argv[0]=%s\n"
		       "  do not match (trying argv[0])\n", file_name, argv0);

	if (get_symtab (argv0))
	  {
	    file_name = argv0;
	    copy_symtab_into_symbols ();
	  }
	else
	  {
	    callchain_msg ("argv[0]=%s does not contain valid symbols\n"
			   "trying to use file-name=%s\n", argv0, file_name);

	    if (get_symtab (file_name))
	      copy_symtab_into_symbols ();
	    else
	      {
		callchain_msg
		  ("file-name=%s does not contain valid symbols *too*\n",
		   file_name);
		search_cwd_for_executable ();
	      }
	  }
      }
  }
# else
  {
    if (!file_name)
      file_name = find_string ("a.out");

    if (get_symtab (file_name))
      copy_symtab_into_symbols ();
    else
      {
	callchain_msg ("file-name=%s does not contain valid symbols\n",
		       file_name);
	search_cwd_for_executable ();
      }
  }
# endif

  get_bounds ();

  /* `empty_call_chain' is used if we can not generate a callchain with
   * `backtrace' ( <=> backtrace(..) == 0 ).
   */

  empty_call_chain = new_CallChain (0, 0);
}

/* ------------------------------------------------------------------------ */

/* In a program that trys to find memory leaks we should also be very
 * careful with reclaiming allocated memory -- at least from a moral point
 * of view ;-).
 */

static void
exit_CallChain (void)
{
  int i;
  if (debug_flag)
    {
      if (symtab)
	callchain_msg ("[symtab: %s]\n",
		       get_statistics_for_HashTable (symtab));
      if (chaintab)
	callchain_msg ("[chaintab: %s]\n",
		       get_statistics_for_HashTable (chaintab));
      if (addrs)
	callchain_msg ("[addrs: %s]\n", get_statistics_for_HashTable (addrs));
      if (strings)
	callchain_msg ("[strings: %s]\n",
		       get_statistics_for_HashTable (strings));
    }

  if (chaintab)
    free_HashTable (chaintab);
  if (chains)
    free (chains);
  if (addrs)
    free_HashTable (addrs);
  if (symtab)
    free_HashTable (symtab);
  if (symbols)
    free (symbols);
  if (strings)
    free_HashTable (strings);
  if (dont_log_chains)
    {
      for (i = 0; i < num_dont_log_chains; i++)
	{
	  free (dont_log_chains[i]);
	}
      free (dont_log_chains);
    }
  if (only_log_chains)
    {
      for (i = 0; i < num_only_log_chains; i++)
	{
	  free (only_log_chains[i]);
	}
      free (only_log_chains);
    }

  if (debug_flag)
    callchain_msg ("[internal: %s]\n", wrapper_stats ());
}

/* ------------------------------------------------------------------------ */

static void
report_percent (float f)
{
  int a = (int) f, b = (int) ((f - (float) a) * 10.0 + 0.5);
  fprintf (logfile, "%3d.%01d%%", a, b);
}

/* ------------------------------------------------------------------------ */

static void
report_bytes (long n)
{
  float f = n;

  assert (n >= 0);

  if (n < 10240)
    {
      /*XXXXX Bytes */

      fprintf (logfile, "%ld Bytes", n);
    }
  else if (n < 1024 * 1024)
    {
      /*XXX.X KB   */

      fprintf (logfile, "%.1f KB", f / (float) 1024);
    }
  else if (n < 1024 * 1024 * 1024)
    {
      /*XXX.X MB   */

      fprintf (logfile, "%.1f MB", f / (float) (1024 * 1024));
    }
  else
    {
      /*XXX.X GB   */

      fprintf (logfile, "%.1f GB", f / (float) (1024 * 1024 * 1024));
    }
}

/* ------------------------------------------------------------------------ */

static long
count_allocated (ccmallocLinks * q)
{
  long res;

  for (res = 0; q; q = q->next)
    if (is_allocated_links (q))
      res += get_size_links (q);

  return res;
}

/* ------------------------------------------------------------------------ */

static void
print_addresses (FILE * file, ccmallocLinks * q, const char *prefix)
{
  int i = 0;

  while (q)
    {
      if (i == 5)
	{
	  fprintf (file, "\n%s", prefix);
	  i = 1;
	}
      else
	i++;

      fprintf (file, "%c0x%08x", is_allocated_links (q) ? '+' : '-',
	       (unsigned) (((char *) q) +
			   ccmallocLinks_ccmallocUserData_offset));
      if ((q = q->next))
	putc (',', file);
    }
}

/* ------------------------------------------------------------------------ */

/* count number of allocations and deallocations */

static int
count_and_report_allocations (CallChain c)
{
  int num_reported = 1;

  long _bytes_deallocated = 0, _bytes_allocated = 0,
    _num_allocated = 0, _num_deallocated = 0, _bytes_wasted = 0;

  ccmallocLinks *p;
  CCToplevelData *td = c->toplevel_data;

  assert (td);

  _bytes_wasted = td->bytes_wasted;

  for (p = td->allocations; p; p = p->next)
    {
      _num_allocated++;
      _bytes_allocated += get_size_links (p);

      if (!is_allocated_links (p))
	{
	  _num_deallocated++;
	  _bytes_deallocated += get_size_links (p);
	}
    }

#ifndef NDEBUG
  if (callchain_statistics)
    {
      /* We also need the number of allocations ... so we
       * had to count again!
       */

      assert (_bytes_wasted == _bytes_allocated - _bytes_deallocated);
    }
#endif


  if (_bytes_allocated > 0 || callchain_statistics)
    {
      double percent = 0.0;
      long num_allocated_to_report = _num_allocated;

      if (keep_deallocated_data)
	num_allocated_to_report -= _num_deallocated;

      if (bytes_wasted != 0)
	percent = 100.0 * ((float) _bytes_wasted) / ((float) bytes_wasted);

      if (only_wasting_alloc && (_bytes_wasted == 0))
	num_reported = 0;
      else
	{
	  if (percent >= 10.0)
	    fputs ("*", logfile);
	  else
	    fputs ("|", logfile);

	  report_percent (percent);
	  fputs (" = ", logfile);
	  report_bytes (_bytes_wasted);

	  fprintf (logfile, " of garbage allocated in %ld allocation%s\n",
		   num_allocated_to_report,
		   num_allocated_to_report != 1 ? "s" : "");
	}
    }
  return num_reported;
}

/* ------------------------------------------------------------------------ */

static void
report_callchain (CallChain c)
{
  static int first_reported_callchain = 1;
  int num_reported = 0;

  CCToplevelData *td = c->toplevel_data;

  assert (td);

  if (first_reported_callchain)
    {
      fputs ("=======================================================\n",
	     logfile);

      if (empty_lines)
	fputs ("|\n", logfile);

      first_reported_callchain = 0;
    }

  if (callchain_statistics)
    {
      /* In this case we also can report the total number of allocations
       * and deallocations for this `CallChain'.
       */

      CallChainStats *stats = td->stats;

      num_reported = count_and_report_allocations (c);
      if (num_reported > 0)
	{

	  if (stats->num_allocated != 0)
	    {
	      fprintf (logfile,
		       "|       | %ld allocated (%ld Bytes = %3.1f%% of total allocated)\n",
		       stats->num_allocated, stats->bytes_allocated,
		       100.0 * ((float) stats->bytes_allocated) /
		       ((float) bytes_allocated));
	    }

	  /* at least for the `empty_call_chain' we have both ... */

	  if (stats->num_deallocated != 0)
	    {
	      fprintf (logfile,
		       "|       | %ld deallocated (%ld Bytes = %3.1f%% of total allocated)\n",
		       stats->num_deallocated, stats->bytes_deallocated,
		       100.0 * ((float) stats->bytes_deallocated) /
		       ((float) bytes_allocated));
	    }
	}
    }
  else
    num_reported = count_and_report_allocations (c);

  if (num_reported > 0)
    {
      if (print_addresses_flag && td->allocations)
	{
	  if (empty_lines)
	    fputs ("|       |\n", logfile);
	  fputs ("|       @ [ ", logfile);
	  if (empty_lines)
	    fputs ("\n|       |   ", logfile);
	  print_addresses (logfile, td->allocations, "|       |   ");
	  if (empty_lines)
	    fputs ("\n|       | ]\n", logfile);
	  else
	    fputs (" ]\n", logfile);
	}

      _print_chain (logfile, c, "|       |", "|       `", "|        ", 5, 5);
    }
}

/* ------------------------------------------------------------------------ */

static int
cmp_strings (const char *a, const char *b)
{
  if (a && b)
    {
      return strcmp (a, b);
    }
  else if (a)
    return -1;
  else if (b)
    return 1;
  else
    return 0;
}

static int
cmp_CallChains_by_BytesWasted_for_Qsort (const void *_a, const void *_b)
{
  CallChain a = *(CallChain *) _a, b = *(CallChain *) _b;
  CCToplevelData *tda = a->toplevel_data, *tdb = b->toplevel_data;

  long m, n;

  assert (tda);
  assert (tdb);

  m = tda->bytes_wasted;
  n = tdb->bytes_wasted;

  if (m == n)
    {
      while (a && b)
	{
	  if (a->addr_data && b->addr_data)
	    {
	      if ((n = cmp_strings (a->addr_data->name, b->addr_data->name)))
		return n;
	      if ((n = cmp_strings (a->addr_data->file, b->addr_data->file)))
		return n;
	      if ((n = cmp_strings (a->addr_data->alternative_name,
				    b->addr_data->alternative_name)))
		return n;
	      if (a->addr_data->lineno < b->addr_data->lineno)
		return -1;
	      if (a->addr_data->lineno > b->addr_data->lineno)
		return 1;
	    }
	  else if (a->addr_data)
	    return -1;
	  else if (a->addr_data)
	    return 1;
	  if (a->key.addr < b->key.addr)
	    return -1;
	  if (b->key.addr < a->key.addr)
	    return 1;

	  a = a->key.next;
	  b = b->key.next;
	}
      if (a)
	return -1;
      if (b)
	return 1;
      return 0;
    }
  else
    return m < n ? 1 : -1;
}

/* ------------------------------------------------------------------------ */

static int
cmp_CallChains_by_Size_for_Qsort (const void *_a, const void *_b)
{
  CallChain a = *(CallChain *) _a, b = *(CallChain *) _b;
  CallChainStats *s, *t;
  long m, n;

  assert (callchain_statistics);
  assert (a->toplevel_data);
  assert (b->toplevel_data);

  s = a->toplevel_data->stats;
  t = b->toplevel_data->stats;

  m = s->bytes_allocated;
  n = t->bytes_allocated;

  if (m == n)
    {
      while (a && b)
	{
	  if (a->addr_data && b->addr_data)
	    {
	      if ((n = cmp_strings (a->addr_data->name, b->addr_data->name)))
		return n;
	      if ((n = cmp_strings (a->addr_data->file, b->addr_data->file)))
		return n;
	      if ((n = cmp_strings (a->addr_data->alternative_name,
				    b->addr_data->alternative_name)))
		return n;
	      if (a->addr_data->lineno < b->addr_data->lineno)
		return -1;
	      if (a->addr_data->lineno > b->addr_data->lineno)
		return 1;
	    }
	  else if (a->addr_data)
	    return -1;
	  else if (a->addr_data)
	    return 1;
	  if (a->key.addr < b->key.addr)
	    return -1;
	  if (b->key.addr < a->key.addr)
	    return 1;

	  a = a->key.next;
	  b = b->key.next;
	}
      if (a)
	return -1;
      if (b)
	return 1;
      return 0;
    }
  else
    return m < n ? 1 : -1;
}

/* ------------------------------------------------------------------------ */

static int
cmp_CallChains_by_NumAllocated_for_Qsort (const void *_a, const void *_b)
{
  CallChain a = *(CallChain *) _a, b = *(CallChain *) _b;
  CallChainStats *s, *t;
  long m, n;

  assert (callchain_statistics);
  assert (a->toplevel_data);
  assert (b->toplevel_data);

  s = a->toplevel_data->stats;
  t = b->toplevel_data->stats;

  m = s->num_allocated;
  n = t->num_allocated;

  if (m == n)
    {
      while (a && b)
	{
	  if (a->addr_data && b->addr_data)
	    {
	      if ((n = cmp_strings (a->addr_data->name, b->addr_data->name)))
		return n;
	      if ((n = cmp_strings (a->addr_data->file, b->addr_data->file)))
		return n;
	      if ((n = cmp_strings (a->addr_data->alternative_name,
				    b->addr_data->alternative_name)))
		return n;
	      if (a->addr_data->lineno < b->addr_data->lineno)
		return -1;
	      if (a->addr_data->lineno > b->addr_data->lineno)
		return 1;
	    }
	  else if (a->addr_data)
	    return -1;
	  else if (a->addr_data)
	    return 1;
	  if (a->key.addr < b->key.addr)
	    return -1;
	  if (b->key.addr < a->key.addr)
	    return 1;

	  a = a->key.next;
	  b = b->key.next;
	}
      if (a)
	return -1;
      if (b)
	return 1;
      return 0;
    }
  else
    return m < n ? 1 : -1;
}

/* ------------------------------------------------------------------------ */
/* We only use the simple heuristic that at least 3 frames of c must contain
 * a valid address. Otherwise c is assumed to be an library call chain
 *
 * Special case for Linux (and others?)
 * The first function in a CallChain is not main but 
 * __libc_start_main, for which the test is_library_pc(...) is always true.
 * So we must reduce the limit from 3 to 2 ... (Henning Moll)
 */

static int
is_library (CallChain c)
{
  if (c->key.addr && !is_library_pc (c->key.addr))
    return 0;
  else
    {
      int num_zero = 0, length = 0;

      for (; c; c = c->key.next)
	{
	  if (!c->key.addr || is_library_pc (c->key.addr))
	    num_zero++;
	  length++;
	}
#ifdef OS_IS_LINUX
      return length - num_zero < 2;
#else
#endif
      return length - num_zero < 3;
    }
}

/* ------------------------------------------------------------------------ */

static int
check_log_chains_match (CallChain c, int num_chains, DontLogChain ** chains)
{
  int i, j, match;
  CallChain d;

  /* Loop through all the chains to be checked for a match. */
  for (i = 0; i < num_chains; i++)
    {
      match = 1;
      /* Walk down both chains while we're still matching. */
      for (j = 0, d = c; j < chains[i]->num && d && match;
	   j++, d = d->key.next)
	{
	  if (d->addr_data)
	    {
	      char *name = d->addr_data->alternative_name;
	      char *matchname = chains[i]->funcs[j].name;
	      char *file;
	      int lineno = d->addr_data->lineno;
	      int matchline = chains[i]->funcs[j].line;
	      if (!name)
		name = d->addr_data->name;
	      file = d->addr_data->file;

	      if (!name && !file && !matchname[0])
		match = 1;
	      else if ((name && strcmp (name, matchname) == 0) ||
		       (file && strcmp (file, matchname) == 0))
		{
		  match = lineno == -1 || matchline == -1 ||
		    lineno == matchline;
		}
	      else
		match = 0;
	    }
	  else
	    match = chains[i]->funcs[j].name[0] == '\0';
	}
      if (match && j == chains[i]->num)
	return 1;
    }
  return 0;
}

static int
check_dont_log_chain (CallChain c)
{
  const char *name;
  AddrData *data;
  int match, i;
  CallChain d;

  for (d = c; d; d = d->key.next)
    {
      data = d->addr_data;

      if (data)
	{
	  for (i = 0; i < 2; i++)
	    {
	      name = i ? data->alternative_name : data->name;
	      if (name && !strcmp (name, "ccmalloc_init"))
		return 1;
	    }
	}
    }

  if (only_log_chains)
    {
      d = c;
      match = 0;
      /* Walk through the whole chain, checking for a match. */
      while (d && !match)
	{
	  if (check_log_chains_match
	      (d, num_only_log_chains, only_log_chains))
	    {
	      match = 1;
	    }
	  d = d->key.next;
	}
      /* If we didn't find a match anywhere, dont log it. */
      if (!match)
	return 1;
    }

  if (dont_log_chains)
    {
      d = c;
      /* Try at every position in the call chain. */
      while (d)
	{
	  if (check_log_chains_match
	      (d, num_dont_log_chains, dont_log_chains))
	    return 1;
	  d = d->key.next;
	}
    }

  /* Well, as default, log it! */
  return 0;
}

/* ------------------------------------------------------------------------ */

static void
copy_chaintab_into_chains (void)
{
  HashTableIterator it;
  int i;

  num_chains = 0;

  for (setup_HashTableIterator (chaintab, &it);
       !is_done_HashTableIterator (&it); increment_HashTableIterator (&it))
    {
      CallChain c = (CallChain) get_data_from_HashTableIterator (&it);

      if (c)
	{
	  if (has_allocated_data (c))
	    {
	      if (is_library (c))
		{
		  if (library_chains)
		    num_chains++;
		}
	      else
		num_chains++;
	    }
	}
    }

  chains = (CallChain *) malloc ((num_chains + 1) * sizeof (CallChain));

  for (i = 0, setup_HashTableIterator (chaintab, &it);
       !is_done_HashTableIterator (&it); increment_HashTableIterator (&it))
    {
      CallChain c = (CallChain) get_data_from_HashTableIterator (&it);
      if (c &&
	  has_allocated_data (c) &&
	  (library_chains || (!library_chains && !is_library (c))))
	{
	  CCToplevelData *td = c->toplevel_data;
	  assert (td);
	  chains[i++] = c;
	  td->bytes_wasted = count_allocated (td->allocations);
	}
    }

  assert (i == num_chains);
  chains[i] = 0;
}

static void
sort_chains (void)
{
  int (*cmp) (const void *, const void *);
  const char *prestr, *poststr;

  if (sort_by_wasted || !callchain_statistics)
    {
      prestr = "| sorting by number of not reclaimed bytes ...";
      poststr = " done.  |\n";
      cmp = cmp_CallChains_by_BytesWasted_for_Qsort;
    }
  else if (sort_by_size)
    {
      prestr = "| sorting by number of allocated bytes ...";
      poststr = " done.      |\n";
      cmp = cmp_CallChains_by_Size_for_Qsort;
    }
  else
    {
      prestr = "| sorting by number of allocations ...";
      poststr = " done.          |\n";
      cmp = cmp_CallChains_by_NumAllocated_for_Qsort;
    }

  fputs (prestr, logfile);
  fflush (logfile);

  qsort (chains, num_chains, sizeof (CallChain), cmp);

  fputs (poststr, logfile);
  fflush (logfile);
}

/* ------------------------------------------------------------------------ */

static void
report_callchain_counts (void)
{
  HashTableIterator it;
  int count_library_chains = 0;
  int count_unlogged_chains = 0;
  int rep_num_chains = 0;

  for (setup_HashTableIterator (chaintab, &it);
       !is_done_HashTableIterator (&it); increment_HashTableIterator (&it))
    {
      CallChain c = (CallChain) get_data_from_HashTableIterator (&it);

      if (c)
	{
	  if (has_allocated_data (c))
	    {
	      if (check_dont_log_chain (c))
		{
		  count_unlogged_chains++;
		}
	      else if (is_library (c))
		{
		  count_library_chains++;
		  if (library_chains)
		    rep_num_chains++;
		}
	      else
		rep_num_chains++;
	    }
	}
    }

  fprintf (logfile, "| number of call chains: %-28d |\n", num_chains);
  fprintf (logfile, "| number of ignored call chains: %-20d |\n",
	   count_unlogged_chains);
  fprintf (logfile, "| number of reported call chains: %-19d |\n",
	   rep_num_chains);
  fprintf (logfile, "| number of internal call chains: %-19d |\n",
	   rep_num_chains - (library_chains ? count_library_chains : 0));
  fprintf (logfile, "| number of library call chains: %-20d |\n",
	   count_library_chains);
}

/* ------------------------------------------------------------------------ */

static void
report_callchains (void)
{
  int i;

  bytes_wasted = bytes_allocated - bytes_deallocated;

  for (i = 0; i < num_chains; i++)
    if (!check_dont_log_chain (chains[i]))
      report_callchain (chains[i]);
}

/* ------------------------------------------------------------------------ */

static void
print_callchain (CallChain c)
{
  if (state == INITIALIZED)
    {
      name_chain (c);
      assert (c);
      insert_file_info_in_chains_from_pipe (c);
    }

  _print_chain (logfile, c, "***   |", "***   `", "***    ", 3, 3);
}

/* ------------------------------------------------------------------------ */

static void
check_error_exit (ccmallocLinks * links)
{
  if (continue_flag)
    {
      ccmallocMagicAndFlags *mf = (ccmallocMagicAndFlags *)
	(((char *) links) + ccmallocLinks_ccmallocMagicAndFlags_offset);

      set_is_corrupted (mf);
      set_magic (mf);
    }
  else
    die ();
}

/* ------------------------------------------------------------------------ */

static void
_check_for_overwrite (ccmallocLinks * links)
{
  char *user_data = ((char *) links) + ccmallocLinks_ccmallocUserData_offset;

  ccmallocBoundary *b =
    (ccmallocBoundary *) (user_data + get_size_links (links));

  char *end_of_user_data = (char *) b;
  int ok = 1;

  align (b);
  while (end_of_user_data < (char *) b)
    {
      ok = (*end_of_user_data ==
	    (char) (((unsigned) end_of_user_data) ^ MAGIC_CHAR));

      if (ok)
	end_of_user_data++;
      else
	break;
    };

  if (ok)
    {
      int i = 0;

      while (i < check_overwrites)
	{
	  ok = ((b->boundary[i] ^ BASIC_SPELL) == (unsigned) user_data);
	  if (ok)
	    i++;
	  else
	    break;
	}

      if (!ok)
	{
	  fprintf (logfile,
		   "*** check-count=%ld: end of block at 0x%08x of size %d changed\n"
		   "*** the %d. word (0x%08x) after the block changed\n",
		   check_count,
		   (unsigned) user_data,
		   get_size_links (links), i + 1, (unsigned) &b->boundary[i]);

	  fflush (logfile);	/* sometimes print_callchain crashes ... */

	  if (!only_count)
	    {
	      fputs ("*** it was allocated at\n", logfile);
	      print_callchain (links->callchain);
	    }

	  check_error_exit (links);
	}
    }
  else
    {
      fprintf (logfile,
	       "*** check-count=%ld: end of block at 0x%08x of size %d changed\n"
	       "*** the %d. byte (0x%08x) in the word where the block ends changed\n",
	       check_count,
	       (unsigned) user_data,
	       get_size_links (links),
	       (end_of_user_data - user_data) - get_size_links (links) + 1,
	       (unsigned) end_of_user_data);

      fflush (logfile);		/* sometimes print_callchain crashes ... */

      if (!only_count)
	{
	  fputs ("*** it was allocated at\n", logfile);
	  print_callchain (links->callchain);
	}

      check_error_exit (links);
    }
}

/* ------------------------------------------------------------------------ */

static void
_check_for_underwrite (ccmallocLinks * links)
{
  char *user_data = ((char *) links) + ccmallocLinks_ccmallocUserData_offset;
  ccmallocBoundary *b = (ccmallocBoundary *)
    (user_data - sizeof (unsigned) * check_underwrites);

  int ok = 1, i = check_underwrites - 1;

  while (i >= 0)
    {
      ok = ((b->boundary[i] ^ BASIC_SPELL) == (unsigned) user_data);
      if (ok)
	i--;
      else
	break;
    }

  if (!ok)
    {
      fprintf (logfile,
	       "*** check-count=%ld: start of block at 0x%08x of size %d changed\n"
	       "*** the %d. word (0x%08x) before the block changed\n",
	       check_count,
	       (unsigned) user_data,
	       get_size_links (links), check_underwrites - 1 - i + 1,
	       /* start                - current_value  + 1 (only CS people start
	        *                                            counting from zero ;-)
	        */
	       (unsigned) &b->boundary[i]);

      fflush (logfile);		/* sometimes print_callchain crashes ... */

      if (!only_count)
	{
	  fputs ("*** it was allocated at\n", logfile);
	  print_callchain (links->callchain);
	}

      check_error_exit (links);
    }
}

/* ------------------------------------------------------------------------ */

static void
_check_for_free_space_integrity (ccmallocLinks * links)
{
  int i, sz = get_size_links (links);
  char *user_data = ((char *) links) + ccmallocLinks_ccmallocUserData_offset;

  for (i = 0; i < sz; i++)
    {
      if (user_data[i] != MAGIC_CHAR)
	{
	  ccmallocKeepFreeData *keep_free_data = (ccmallocKeepFreeData *)
	    (((char *) links) - ccmallocKeepFreeData_ccmallocLinks_offset);

	  fprintf (logfile,
		   "*** check-count=%ld: byte at 0x%08x changed but lies\n",
		   check_count, (unsigned) (user_data + i));

	  fprintf (logfile,
		   "*** in block at 0x%08x of size %d that was allocated at\n",
		   (unsigned) user_data, sz);

	  fflush (logfile);	/* sometimes print_callchain crashes ... */

	  print_callchain (links->callchain);

	  fflush (logfile);	/* sometimes print_callchain crashes ... */

	  fputs ("*** and was already freed at\n", logfile);
	  print_callchain (keep_free_data->freed_at);

	  check_error_exit (links);
	}
    }
}

/* ------------------------------------------------------------------------ */

/* this is a very expensive routine especially if keep-deallocated-data
 * is set to 1
 */

static void
_check_for_integrity (void)
{
  CCToplevelData *p;

  checks_done++;

  for (p = toplevels; p; p = p->next)
    {
      ccmallocLinks *links;

      for (links = p->allocations; links; links = links->next)
	{
	  if (1)		/* !is_corrupted_links(links)) */
	    {
	      if (is_allocated_links (links))
		{
		  if (check_overwrites)
		    _check_for_overwrite (links);
		  if (check_underwrites)
		    _check_for_underwrite (links);
		}
	      else
		{
		  if (check_free_space)
		    _check_for_free_space_integrity (links);
		}
	    }
	}
    }
}

/* ------------------------------------------------------------------------ */

static void
check_for_integrity (void)
{
  if (!only_count &&
      (check_free_space || check_overwrites) && check_interval > 0)
    {
      if (check_count >= (long) check_start)
	{
	  if (check_modulo == 0)
	    _check_for_integrity ();
	  check_modulo = (check_modulo + 1) % check_interval;
	}
    }

  check_count++;
}

/*------------------------------------------------------------------------*/

void
ccmalloc_atexit (void (*f) (void))
{
#ifdef HAVE_ATEXIT
  atexit (f);
#else
  ccmalloc_abort ("unsupported platform/compiler: atexit() missing!\n");
#endif
}

/* ------------------------------------------------------------------------ */

static void
ccmalloc_init (void)
{
  if (state == UNINITIALIZED)
    {
      state = INITIALIZING;

      libcwrapper_inc_semaphore ();

      logfile = stderr;
      read_startup_file ();	/* make sure `malloc' is called */
      /* (see comment to banner() below */
      {
	ccmallocMagicAndFlags_ccmallocUserData_offset =
	  sizeof (ccmallocMagicAndFlags) +
	  sizeof (unsigned) * check_underwrites;

	align (ccmallocMagicAndFlags_ccmallocUserData_offset);

	ccmallocSize_ccmallocMagicAndFlags_offset = sizeof (ccmallocSize);
	align (ccmallocSize_ccmallocMagicAndFlags_offset);

	ccmallocSize_ccmallocUserData_offset =
	  ccmallocSize_ccmallocMagicAndFlags_offset +
	  ccmallocMagicAndFlags_ccmallocUserData_offset;

	assert (isAligned (ccmallocSize_ccmallocUserData_offset));

	ccmallocLinks_ccmallocSize_offset = sizeof (ccmallocLinks);
	align (ccmallocLinks_ccmallocSize_offset);

	ccmallocLinks_ccmallocMagicAndFlags_offset =
	  ccmallocLinks_ccmallocSize_offset +
	  ccmallocSize_ccmallocMagicAndFlags_offset;

	assert (isAligned (ccmallocLinks_ccmallocMagicAndFlags_offset));

	ccmallocLinks_ccmallocUserData_offset =
	  ccmallocLinks_ccmallocMagicAndFlags_offset +
	  ccmallocMagicAndFlags_ccmallocUserData_offset;

	assert (isAligned (ccmallocLinks_ccmallocUserData_offset));

	ccmallocKeepFreeData_ccmallocLinks_offset = sizeof (ccmallocLinks);
	align (ccmallocKeepFreeData_ccmallocLinks_offset);
      }

      if (only_count)
	{
	  offset = ccmallocSize_ccmallocUserData_offset;
	}
      else
	{
	  init_CallChain ();

	  offset = ccmallocLinks_ccmallocUserData_offset;

	  if (keep_deallocated_data)
	    offset += ccmallocKeepFreeData_ccmallocLinks_offset;

	  assert (isAligned (offset));
	}

      /* Only necessary if we are not in C++ mode.
       */
      if (!ccmalloc_ctordtor)
	ccmalloc_atexit (ccmalloc_report);

      if (!silent_startup)
	banner ();		/* now malloc has already been called */
      /* and any underlying memory profiler */
      /* has reported its banner */
      /*
       * IMO the state should change after calling banner()...
       * (Henning Moll)
       */
      libcwrapper_dec_semaphore ();
      state = INITIALIZED;
    }
}

/* ------------------------------------------------------------------------ */

static void *
_ccmalloc_malloc (size_t number_of_bytes)
{
  char *data, *user_data;
  ccmallocMagicAndFlags *mf;
  ccmallocSize *sz;
  size_t n;

  check_for_integrity ();

  if (number_of_bytes < 1)	/* works for signed *and* unsigned size_t */
    {
      callchain_msg ("*** malloc(%d)\n", number_of_bytes);
      if (continue_flag)
	return 0;
      else
	die ();
    }

  n = offset + number_of_bytes;

  if (check_overwrites)
    {
      align (n);
      n += sizeof (unsigned) * check_overwrites;
    }

  data = (char *) malloc (n);
  data += offset;
  user_data = data;

  if (check_underwrites)
    {
      ccmallocBoundary *b = (ccmallocBoundary *)
	(user_data - sizeof (unsigned) * check_underwrites);

      int i;

      for (i = 0; i < check_underwrites; i++)
	b->boundary[i] = BASIC_SPELL ^ ((unsigned) user_data);
    }

  /* Now we initialize all components of the header in reverse order.
   */

  data -= ccmallocMagicAndFlags_ccmallocUserData_offset;
  mf = (ccmallocMagicAndFlags *) data;

  sz = (ccmallocSize *) (data - ccmallocSize_ccmallocMagicAndFlags_offset);
  sz->size = number_of_bytes;

  set_is_allocated (mf);
  set_magic (mf);		/* may depend on `sz -> size' */

  if (check_overwrites)
    {
      int i;
      ccmallocBoundary *b =
	(ccmallocBoundary *) (user_data + number_of_bytes);
      char *end_of_user_data = (char *) b;

      align (b);
      while (end_of_user_data < (char *) b)
	{
	  *end_of_user_data =
	    (char) (((unsigned) end_of_user_data) ^ MAGIC_CHAR);
	  end_of_user_data++;
	};

      for (i = 0; i < check_overwrites; i++)
	b->boundary[i] = BASIC_SPELL ^ ((unsigned) user_data);
    }

  if (!only_count)
    {
      CallChain c;
      ccmallocLinks *links;

      data -= ccmallocLinks_ccmallocMagicAndFlags_offset;
      links = (ccmallocLinks *) data;

      if (!(c = backtrace (2)))
	c = empty_call_chain;
      enqueue (c, links);

      if (callchain_statistics)
	{
	  CallChainStats *stats;

	  stats = c->toplevel_data->stats;
	  stats->num_allocated++;
	  stats->bytes_allocated += number_of_bytes;
	}

      if (keep_deallocated_data)
	{
	  /* it's defensive to initialize freed_at */

	  ccmallocKeepFreeData *fd;
	  data -= ccmallocKeepFreeData_ccmallocLinks_offset;
	  fd = (ccmallocKeepFreeData *) data;
	  fd->freed_at = 0;
	}
    }

  return user_data;
}

/* ------------------------------------------------------------------------ */

static void
_ccmalloc_free (void *_data)
{
  char *data, *user_data;
  ccmallocMagicAndFlags *mf;

  check_for_integrity ();

  if (!_data)
    return;

  data = user_data = (char *) _data;
  data -= ccmallocMagicAndFlags_ccmallocUserData_offset;
  mf = (ccmallocMagicAndFlags *) data;

  if (is_valid_magic (mf))
    {
      int i;
      ccmallocSize *sz;

      if (!is_allocated (mf))
	{
	  ccmallocLinks *links = (ccmallocLinks *)
	    (user_data - ccmallocLinks_ccmallocUserData_offset);

	  fprintf (logfile,
		   "*** free() called twice for block at 0x%08x of size %d\n",
		   (unsigned) user_data, get_size_links (links));

	  fflush (logfile);	/* print_callchain crashes sometimes */

	  if (!only_count)
	    {
	      fputs ("*** it was allocated at\n", logfile);

	      print_callchain (links->callchain);
	      fflush (logfile);

	      if (keep_deallocated_data)
		{
		  ccmallocKeepFreeData *keep_free_data =
		    (ccmallocKeepFreeData *)
		    (((char *) links) -
		     ccmallocKeepFreeData_ccmallocLinks_offset);

		  fputs ("*** and already freed at\n", logfile);
		  print_callchain (keep_free_data->freed_at);
		}
	    }

	  if (continue_flag)
	    return;
	  else
	    die ();
	}

      data -= ccmallocSize_ccmallocMagicAndFlags_offset;
      sz = (ccmallocSize *) data;

      if (check_underwrites)
	{
	  ccmallocLinks *links = (ccmallocLinks *)
	    (user_data - ccmallocLinks_ccmallocUserData_offset);

	  if (!is_corrupted (mf))
	    _check_for_underwrite (links);
	}

      if (check_overwrites)
	{
	  ccmallocLinks *links = (ccmallocLinks *)
	    (user_data - ccmallocLinks_ccmallocUserData_offset);

	  if (!is_corrupted (mf))
	    _check_for_overwrite (links);
	}

      bytes_deallocated += sz->size;
      num_deallocated++;

      if (only_count)
	{
	  assert (data + offset == user_data);
	}
      else
	{
	  ccmallocLinks *links;

	  data -= ccmallocLinks_ccmallocSize_offset;
	  links = (ccmallocLinks *) data;

	  if (callchain_statistics)
	    {
	      CallChainStats *stats;

	      stats = links->callchain->toplevel_data->stats;
	      stats->num_deallocated++;
	      stats->bytes_deallocated += sz->size;
	    }

	  if (keep_deallocated_data)
	    {
	      CallChain c;
	      ccmallocKeepFreeData *keep_free_data;
	      data -= ccmallocKeepFreeData_ccmallocLinks_offset;
	      keep_free_data = (ccmallocKeepFreeData *) data;

	      if (!(c = backtrace (2)))
		c = empty_call_chain;
	      keep_free_data->freed_at = c;
	    }
	  else
	    dequeue (links);
	}

      /* Try to invalidate deallocated data! */

      for (i = 0; i < sz->size; i++)
	user_data[i] = MAGIC_CHAR;

      if (keep_deallocated_data)
	{
	  clr_is_allocated (mf);
	  set_magic (mf);
	}
      else
	{
	  /* Here we should invalidate the magic because the underlying
	   * memory allocator may corrupt the ccmalloc data like
	   * the pointer to the callchain.
	   */

	  invalidate_magic (mf);
	  free (data);
	}
    }
  else
    {
      fprintf (logfile,
	       "*** can not free non valid data at 0x%08x\n",
	       (unsigned) user_data);


      if (keep_deallocated_data)
	fputs ("*** (perhaps an `under'write occured)\n", logfile);
      else
	{
	  fputs
	    ("*** (Perhaps an `under'write occured or data has already been freed\n"
	     "***  You should enable `keep-deallocated-data' to test the last case!)\n",
	     logfile);
	}

      if (continue_flag)
	return;
      else
	die ();
    }
}

/* ------------------------------------------------------------------------ */

static void
_ccmalloc_report (void)
{
  libcwrapper_inc_semaphore ();

  fprintf (logfile,
	   "\n"
	   ".---------------.\n"
	   "|ccmalloc report|\n"
	   "=======================================================\n"
	   "| total # of|   allocated | deallocated |     garbage |\n"
	   "+-----------+-------------+-------------+-------------+\n"
	   "|      bytes|%12ld |%12ld |%12ld |\n"
	   "+-----------+-------------+-------------+-------------+\n"
	   "|allocations|%12ld |%12ld |%12ld |\n",
	   bytes_allocated, bytes_deallocated,
	   bytes_allocated - bytes_deallocated,
	   num_allocated, num_deallocated, num_allocated - num_deallocated);

  if (!only_count)
    {
      fputs ("+-----------------------------------------------------+\n",
	     logfile);

      _check_for_integrity ();
      fprintf (logfile,
	       "| number of checks: %-34ld|\n"
	       "| number of counts: %-34ld|\n", checks_done, check_count);

      copy_chaintab_into_chains ();
      name_all_chains ();

      assert (file_name);

      insert_file_info_in_chains ();
      sort_chains ();
      report_callchain_counts ();
      report_callchains ();
    }

  fputs ("`------------------------------------------------------\n",
	 logfile);

  fflush (logfile);		/* defensive ... */
  exit_CallChain ();		/* cleanup */

  libcwrapper_dec_semaphore ();
}

/*---------------------------------------------------------------------------.
 | Here starts the part of external functions                                |
 `---------------------------------------------------------------------------*/

void
ccmalloc_report (void)
{
  if (state == INITIALIZED)
    {
      _ccmalloc_report ();
      state = FINISHED;
    }
  else
    callchain_error ("ccmalloc_report() called in non valid state\n");
}

/* ------------------------------------------------------------------------ */

void *
ccmalloc_malloc (size_t number_of_bytes)
{
  void *res;

  switch (state)
    {
    default:
      ccmalloc_abort ("non valid state in malloc\n");

      /* will never be here */
      return 0;

    case FINISHED:

      res = malloc (number_of_bytes);
      break;

    case UNINITIALIZED:

      ccmalloc_init ();

      /*!!!!!!!! no break -> fall through !!!!!!!!! */

    case INITIALIZED:

      res = _ccmalloc_malloc (number_of_bytes);
      break;
    }

  if (number_of_bytes > 0)	/* ok if size_t is unsigned *or* signed */
    {
      bytes_allocated += number_of_bytes;
      num_allocated++;
    }

  return res;
}

/* ------------------------------------------------------------------------ */

void
ccmalloc_free (void *_data)
{
  switch (state)
    {
    case UNINITIALIZED:

      ccmalloc_abort ("free() without any malloc in uninitialized state\n");
      assert (0);
      exit (1);
      break;

    default:

      ccmalloc_abort ("non valid state in free()\n");
      break;

    case FINISHED:

      callchain_msg ("free(0x%08x) after reporting\n", (unsigned) _data);
      if (tell_about_dtors)
	{
	  callchain_msg ("  (This can happen with static destructors.\n");

	  if (ccmalloc_ctordtor)
	    {
	      callchain_msg
		("   When linking put `ccmalloc.o' at the end (for gcc) or\n");
	      callchain_msg ("   in front of the list of object files.)\n");
	    }
	  else
	    callchain_msg
	      ("   Link with ccmalloc.o instead of -lccmalloc!)\n");

	  tell_about_dtors = 0;
	}
      break;

    case INITIALIZED:

      _ccmalloc_free (_data);
      break;
    }
}

/* ------------------------------------------------------------------------ */

int
ccmalloc_size (void *_data, size_t * size_ptr)
{
  char *data;
  ccmallocMagicAndFlags *mf;

  if (!_data)
    {
      fprintf (logfile, "*** internal error in ccmalloc_size\n");
      die ();
    }

  data = (char *) _data;
  data -= ccmallocMagicAndFlags_ccmallocUserData_offset;
  mf = (ccmallocMagicAndFlags *) data;

  if (is_valid_magic (mf))
    {
      ccmallocSize *sz;
      data -= ccmallocSize_ccmallocMagicAndFlags_offset;
      sz = (ccmallocSize *) data;
      *size_ptr = sz->size;
      return 1;
    }
  else
    return 0;
}

/* ------------------------------------------------------------------------ */

void
ccmalloc_die_or_continue (char *fmt, ...)
{
  va_list ap;
  va_start (ap, fmt);
  vfprintf (logfile, fmt, ap);
  va_end (ap);
  if (!continue_flag)
    die ();
}

/* ------------------------------------------------------------------------ */
/* give the user a chance to force a check at will */

void
ccmalloc_check_for_integrity (void)
{
  libcwrapper_inc_semaphore ();
  check_count++;
  _check_for_integrity ();
  libcwrapper_dec_semaphore ();
}

/* ------------------------------------------------------------------------ */

void
ccmalloc_static_initialization (void)
{
  ccmalloc_ctordtor = 1;
  ccmalloc_init ();
}
