dmalloc_tab.c

测试内存泄露工具

/*
 * Memory table routines
 *
 * Copyright 2000 by Gray Watson
 *
 * This file is part of the dmalloc package.
 *
 * Permission to use, copy, modify, and distribute this software for
 * any purpose and without fee is hereby granted, provided that the
 * above copyright notice and this permission notice appear in all
 * copies, and that the name of Gray Watson not be used in advertising
 * or publicity pertaining to distribution of the document or software
 * without specific, written prior permission.
 *
 * Gray Watson makes no representations about the suitability of the
 * software described herein for any purpose.  It is provided "as is"
 * without express or implied warranty.
 *
 * The author may be contacted via http://dmalloc.com/
 *
 * $Id: dmalloc_tab.c,v 1.19 2003/06/08 05:53:44 gray Exp $
 */

/*
 * This file contains routines used to maintain and display a memory
 * table by file and line number of memory usage.
 *
 * Inspired by code from PSM.  Thanks much.
 */

#if HAVE_STDLIB_H
# include <stdlib.h>				/* for qsort */
#endif
#if HAVE_STRING_H
# include <string.h>
#endif

#include "conf.h"
#include "chunk.h"
#include "compat.h"
#include "dmalloc.h"
#include "dmalloc_loc.h"
#include "error.h"
#include "error_val.h"

#include "dmalloc_tab.h"
#include "dmalloc_tab_loc.h"

/*
 * static unsigned int hash
 *
 * DESCRIPTION:
 *
 * Hash a variable-length key into a 32-bit value.  Every bit of the
 * key affects every bit of the return value.  Every 1-bit and 2-bit
 * delta achieves avalanche.  About (6 * len + 35) instructions.  The
 * best hash table sizes are powers of 2.  There is no need to use mod
 * (sooo slow!).  If you need less than 32 bits, use a bitmask.  For
 * example, if you need only 10 bits, do h = (h & hashmask(10)); In
 * which case, the hash table should have hashsize(10) elements.
 *
 * By Bob Jenkins, 1996.  You may use this code any way you wish,
 * private, educational, or commercial.  It's free.  See
 * http://ourworld.compuserve.com/homepages/bob_jenkins/evahash.htm
 * Use for hash table lookup, or anything where one collision in 2^^32
 * is acceptable.  Do NOT use for cryptographic purposes.
 *
 * RETURNS:
 *
 * Returns a 32-bit hash value.
 *
 * ARGUMENTS:
 *
 * key - Key (the unaligned variable-length array of bytes) that we
 * are hashing.
 *
 * length - Length of the key in bytes.
 *
 * init_val - Initialization value of the hash if you need to hash a
 * number of strings together.  For instance, if you are hashing N
 * strings (unsigned char **)keys, do it like this:
 *
 * for (i=0, h=0; i<N; ++i) h = hash( keys[i], len[i], h);
 */
static	unsigned int	hash(const unsigned char *key,
			     const unsigned int length,
			     const unsigned int init_val)
{
  const unsigned char	*key_p = key;
  unsigned int		a, b, c, len;
  
  /* set up the internal state */
  a = 0x9e3779b9;	/* the golden ratio; an arbitrary value */
  b = 0x9e3779b9;
  c = init_val;		/* the previous hash value */
  
  /* handle most of the key */
  for (len = length; len >= 12; len -= 12) {
    a += (key_p[0]
	  + ((unsigned int)key_p[1] << 8)
	  + ((unsigned int)key_p[2] << 16)
	  + ((unsigned int)key_p[3] << 24));
    b += (key_p[4]
	  + ((unsigned int)key_p[5] << 8)
	  + ((unsigned int)key_p[6] << 16)
	  + ((unsigned int)key_p[7] << 24));
    c += (key_p[8]
	  + ((unsigned int)key_p[9] << 8)
	  + ((unsigned int)key_p[10] << 16)
	  + ((unsigned int)key_p[11] << 24));
    HASH_MIX(a,b,c);
    key_p += 12;
  }
  
  c += length;
  
  /* all the case statements fall through to the next */
  switch(len) {
  case 11:
    c += ((unsigned int)key_p[10] << 24);
  case 10:
    c += ((unsigned int)key_p[9] << 16);
  case 9:
    c += ((unsigned int)key_p[8] << 8);
    /* the first byte of c is reserved for the length */
  case 8:
    b += ((unsigned int)key_p[7] << 24);
  case 7:
    b += ((unsigned int)key_p[6] << 16);
  case 6:
    b += ((unsigned int)key_p[5] << 8);
  case 5:
    b += key_p[4];
  case 4:
    a += ((unsigned int)key_p[3] << 24);
  case 3:
    a += ((unsigned int)key_p[2] << 16);
  case 2:
    a += ((unsigned int)key_p[1] << 8);
  case 1:
    a += key_p[0];
    /* case 0: nothing left to add */
  }
  HASH_MIX(a, b, c);
  
  return c;
}

/*
 * static unsigned int which_bucket
 *
 * DESCRIPTION:
 *
 * Determine the bucket with our file/line and hash function.
 *
 * RETURNS:
 *
 * Bucket number.
 *
 * ARGUMENTS:
 *
 * entry_n -> Number of entries in the memory table.
 *
 * file -> File name or return address of the allocation. 
 *
 * line -> Line number of the allocation.
 */
static	unsigned int	which_bucket(const int entry_n, const char *file,
				     const unsigned int line)
{
  unsigned int	bucket;
  
  if (line == 0) {
    if (file == NULL) {
      bucket = 0;
    }
    else {
      /* we hash on the address in file -- should be a return-address */
      bucket = hash((unsigned char *)&file, sizeof(char *), 0);
    }
  }
  else {
    bucket = hash((unsigned char *)file, strlen(file), 0);
    bucket = hash((unsigned char *)&line, sizeof(line), bucket);
  }
  
  bucket %= entry_n - 1;
  return bucket;
}

/*
 * static int entry_cmp
 *
 * DESCRIPTION:
 *
 * Compare two entries in the memory table for quicksort.
 *
 * RETURNS:
 *
 * -1, 0, or 1 depending if entry1_p is less-than, equal, or
 * greater-than entry2_p.
 *
 * ARGUMENTS:
 *
 * entry1_p -> Pointer to the 1st entry.
 *
 * entry2_p -> Pointer to the 2nd entry.
 */
static	int	entry_cmp(const void *entry1_p, const void *entry2_p)
{
  unsigned long		size1, size2;
  const mem_table_t	*tab1_p = entry1_p, *tab2_p = entry2_p;
  
  /* if the entry is blank then force the size to be 0 */
  if (tab1_p->mt_file == NULL) {
    size1 = 0;
  }
  else {
    size1 = tab1_p->mt_total_size;
  }
  
  /* if the entry is blank then force the size to be 0 */
  if (tab2_p->mt_file == NULL) {
    size2 = 0;
  }
  else {
    size2 = tab2_p->mt_total_size;
  }
  
  /* NOTE: we want the top entries to be ahead so we reverse the sort */
  if (size1 > size2) {
    return -1;
  }
  else if (size1 == size2) {
    return 0;
  }
  else {
    return 1;
  }
}

/*
 * static void swap_bytes
 *
 * DESCRIPTION:
 *
 * Swap the values between two items of a specified size.
 *
 * RETURNS:
 *
 * None.
 *
 * ARGUMENTS:
 *
 * item1_p -> Pointer to the first item.
 *
 * item2_p -> Pointer to the first item.
 *
 * ele_size -> Size of the two items.
 */
static	void	swap_bytes(unsigned char *item1_p, unsigned char *item2_p,
			   int ele_size)
{
  unsigned char	char_temp;
  
  for (; ele_size > 0; ele_size--) {
    char_temp = *item1_p;
    *item1_p = *item2_p;
    *item2_p = char_temp;
    item1_p++;
    item2_p++;
  }
}

/*
 * static void insert_sort
 *
 * DESCRIPTION:
 *
 * Do an insertion sort which is faster for small numbers of items and
 * better if the items are already sorted.
 *
 * RETURNS:
 *
 * None.
 *
 * ARGUMENTS:
 *
 * first_p <-> Start of the list that we are splitting.
 *
 * last_p <-> Last entry in the list that we are splitting.
 *
 * holder_p <-> Location of hold area we can store an entry.
 *
 * ele_size -> Size of the each element in the list.
 */
static	void	insert_sort(unsigned char *first_p, unsigned char *last_p,
			    unsigned char *holder_p,
			    const unsigned int ele_size)
{
  unsigned char	*inner_p, *outer_p;
  
  for (outer_p = first_p + ele_size; outer_p <= last_p; ) {
    
    /* look for the place to insert the entry */
    for (inner_p = outer_p - ele_size;
	 inner_p >= first_p && entry_cmp(outer_p, inner_p) < 0;
	 inner_p -= ele_size) {
    }
    inner_p += ele_size;
    
    /* do we need to insert the entry in? */
    if (outer_p != inner_p) {
      /*
       * Now we shift the entry down into its place in the already
       * sorted list.
       */
      memcpy(holder_p, outer_p, ele_size);
      memmove(inner_p + ele_size, inner_p, outer_p - inner_p);
      memcpy(inner_p, holder_p, ele_size);
    }
    
    outer_p += ele_size;
  }
}

/*
 * static void split
 *
 * DESCRIPTION:
 *
 * This sorts an array of longs via the quick sort algorithm (it's
 * pretty quick)
 *
 * RETURNS:
 *
 * None.
 *
 * ARGUMENTS:
 *
 * first_p -> Start of the list that we are splitting.
 *
 * last_p -> Last entry in the list that we are splitting.
 *
 * ele_size -> Size of the each element in the list.
 */
static	void	split(unsigned char *first_p, unsigned char *last_p,
		      const unsigned int ele_size)
{
  unsigned char	*left_p, *right_p, *pivot_p, *left_last_p, *right_first_p;
  unsigned char	*firsts[MAX_QSORT_SPLITS], *lasts[MAX_QSORT_SPLITS];
  mem_table_t	pivot;
  unsigned int	width, split_c = 0, min_qsort_size, size1, size2;
  
  min_qsort_size = MAX_QSORT_PARTITION * ele_size;
  
  while (1) {
    
    /* find the left, right, and mid point */
    left_p = first_p;
    right_p = last_p;
    /* is there a faster way to find this? */
    width = (last_p - first_p) / ele_size;
    pivot_p = first_p + ele_size * (width >> 1);
    
    /*
     * Find which of the left, middle, and right elements is the
     * median (Knuth vol3 p123).
     */
    if (entry_cmp(first_p, pivot_p) > 0) {
      swap_bytes(first_p, pivot_p, ele_size);
    }
    if (entry_cmp(pivot_p, last_p) > 0) {
      swap_bytes(pivot_p, last_p, ele_size);
      if (entry_cmp(first_p, pivot_p) > 0) {
	swap_bytes(first_p, pivot_p, ele_size);
      }
    }
    
    /*
     * save our pivot so we don't have to worry about hitting and
     * swapping it elsewhere while we iterate across the list below.
     */
    memcpy(&pivot, pivot_p, ele_size);
    
    do {
      
      /* shift the left side up until we reach the pivot value */
      while (entry_cmp(left_p, &pivot) < 0) {
	left_p += ele_size;
      }
      /* shift the right side down until we reach the pivot value */
      while (entry_cmp(&pivot, right_p) < 0) {
	right_p -= ele_size;
      }
      
      /* if we met in the middle then we are done */
      if (left_p == right_p) {
	left_p += ele_size;
	right_p -= ele_size;
	break;
      }
      else if (left_p < right_p) {
	/*
	 * swap the left and right since they both were on the wrong
	 * size of the pivot and continue
	 */
	swap_bytes(left_p, right_p, ele_size);
	left_p += ele_size;
	right_p -= ele_size;
      }
    } while (left_p <= right_p);
    
    /* Rename variables to make more sense.  This will get optimized out. */
    right_first_p = left_p;
    left_last_p = right_p;
    
    /* determine the size of the left and right hand parts */
    size1 = left_last_p - first_p;