chunk.c

测试内存泄露工具

/*
 * Memory chunk low-level allocation 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: chunk.c,v 1.207 2004/10/19 14:50:43 gray Exp $
 */

/*
 * This file contains algorithm level routine for the heap.  They handle the
 * manipulation and administration of chunks of memory.
 */

#include <ctype.h>

#if HAVE_STRING_H
# include <string.h>
#endif
#if HAVE_STDLIB_H
# include <stdlib.h>
#endif

#define DMALLOC_DISABLE

#include "conf.h"

#if LOG_PNT_TIMEVAL
#ifdef TIMEVAL_INCLUDE
# include TIMEVAL_INCLUDE
#endif
#else
# if LOG_PNT_TIME
#  ifdef TIME_INCLUDE
#   include TIME_INCLUDE
#  endif
# endif
#endif

#include "dmalloc.h"

#include "chunk.h"
#include "chunk_loc.h"
#include "compat.h"
#include "debug_tok.h"
#include "dmalloc_loc.h"
#include "dmalloc_rand.h"
#include "dmalloc_tab.h"
#include "error.h"
#include "error_val.h"
#include "heap.h"

/*
 * Library Copyright and URL information for ident and what programs
 */
#if IDENT_WORKS
#ident "@(#) $Copyright: Dmalloc package Copyright 2000 by Gray Watson $"
#ident "@(#) $URL: Source for dmalloc available from http://dmalloc.com/ $"
#else
static	char	*copyright =
  "@(#) $Copyright: Dmalloc package Copyright 2000 by Gray Watson $";
static	char	*source_url =
  "@(#) $URL: Source for dmalloc available from http://dmalloc.com/ $";
#endif

#if LOCK_THREADS
#if IDENT_WORKS
#ident "@(#) $Information: lock-threads is enabled $"
#else
static char *information = "@(#) $Information: lock-threads is enabled $";
#endif
#endif

/*
 * exported variables
 */
/* limit in how much memory we are allowed to allocate */
unsigned long		_dmalloc_memory_limit = 0;

/* total number of bytes that the heap has allocated */
unsigned long		_dmalloc_alloc_total = 0;

/*
 * local variables
 */

/*
 * Skip list of our free list sorted by size in bytes.  Bit of a hack
 * here.  Basically we cannot do a alloc for the structure and we'd
 * like it to be static storage so we allocate an array of them to
 * make sure we have enough forward pointers, when all we need is
 * SKIP_SLOT_SIZE(MAX_SKIP_LEVEL + 1) bytes.
 */
static	skip_alloc_t	skip_free_alloc[MAX_SKIP_LEVEL /* read note ^^ */];
static	skip_alloc_t	*skip_free_list = skip_free_alloc;

/* skip list of all of our allocated blocks sorted by address */
static	skip_alloc_t	skip_address_alloc[MAX_SKIP_LEVEL /* read note ^^ */];
static	skip_alloc_t	*skip_address_list = skip_address_alloc;

/* update slots which we use to update the skip lists */
static	skip_alloc_t	skip_update[MAX_SKIP_LEVEL /* read note ^^ */];

/* linked list of slots of various sizes */
static	skip_alloc_t	*entry_free_list[MAX_SKIP_LEVEL];
/* linked list of blocks of the sizes */
static	entry_block_t	*entry_blocks[MAX_SKIP_LEVEL];
/* linked list of freed blocks on hold waiting for the FREED_POINTER_DELAY */
static	skip_alloc_t	*free_wait_list_head = NULL;
static	skip_alloc_t	*free_wait_list_tail = NULL;

/* administrative structures */
static	char		fence_bottom[FENCE_BOTTOM_SIZE];
static	char		fence_top[FENCE_TOP_SIZE];
static	int		bit_sizes[BASIC_BLOCK]; /* number bits for div-blocks*/

/* memory tables */
static	mem_table_t	mem_table_alloc[MEM_ALLOC_ENTRIES];
static	int		mem_table_alloc_c = 0;
static	mem_table_t	mem_table_changed[MEM_CHANGED_ENTRIES];
static	int		mem_table_changed_c = 0;

/* memory stats */
static	unsigned long	alloc_current = 0;	/* current memory usage */
static	unsigned long	alloc_maximum = 0;	/* maximum memory usage  */
static	unsigned long	alloc_cur_given = 0;	/* current mem given */
static	unsigned long	alloc_max_given = 0;	/* maximum mem given  */
static	unsigned long	alloc_one_max = 0;	/* maximum at once */
static	unsigned long	free_space_bytes = 0;	/* count the free bytes */

/* pointer stats */
static	unsigned long	alloc_cur_pnts = 0;	/* current pointers */
static	unsigned long	alloc_max_pnts = 0;	/* maximum pointers */
static	unsigned long	alloc_tot_pnts = 0;	/* total pointers */

/* admin counts */
static	unsigned long	heap_check_c = 0;	/* count of heap-checks */
static	unsigned long	user_block_c = 0;	/* count of blocks */
static	unsigned long	admin_block_c = 0;	/* count of admin blocks */

/* alloc counts */
static	unsigned long	func_malloc_c = 0;	/* count the mallocs */
static	unsigned long	func_calloc_c = 0;	/* # callocs, done in alloc */
static	unsigned long	func_realloc_c = 0;	/* count the reallocs */
static	unsigned long	func_recalloc_c = 0;	/* count the reallocs */
static	unsigned long	func_memalign_c = 0;	/* count the memaligns */
static	unsigned long	func_valloc_c = 0;	/* count the veallocs */
static	unsigned long	func_new_c = 0;		/* count the news */
static	unsigned long	func_free_c = 0;	/* count the frees */
static	unsigned long	func_delete_c = 0;	/* count the deletes */

/**************************** skip list routines *****************************/

/*
 * static int random_level
 *
 * DESCRIPTION:
 *
 * Return a random level to be associated with a new free-list entry.
 *
 * RETURNS:
 *
 * Random level from 0 to max_level - 1.
 *
 * ARGUMENTS:
 *
 * max_level -> Maximum level of the free-list.
 */
static	int	random_level(const int max_level)
{
  int	level_c;
  
  for (level_c = 0; level_c < max_level; level_c++) {
    /*
     * Basically we count the number of times that the random number
     * generator returns an odd number in a row.  On average this
     * should return 0 1/2 the time, 1 1/4 of the time, 2 1/8 of a
     * time, and N 1/(2^(N - 1)) of the time.  This is what we want.
     * We could test for this in the configure scripts.
     *
     * Since many machines return random numbers which aren't that
     * random, there may be better ways of doing this.  In the past I
     * had (_dmalloc_rand() % 10000 >= 5000) or something but I'd
     * rather not have the % overhead here.
     */
    if (_dmalloc_rand() & 1) {
      break;
    }
  }
  
  return level_c;
}

/*
 * static skip_alloc_t *find_address
 *
 * DESCRIPTION:
 *
 * Look for a specific address in the skip list.  If it exist then a
 * pointer to the matching slot is returned otherwise NULL.  Either
 * way, the links that were traversed to get there are set in the
 * update slot which has the maximum number of levels.
 *
 * RETURNS:
 *
 * Success - Pointer to the slot which matches the block-num and size
 * pair.
 *
 * Failure - NULL and this will not set dmalloc_errno
 *
 * ARGUMENTS:
 *
 * address -> Address we are looking for.
 *
 * exact_b -> Set to 1 to find the exact pointer.  If 0 then the
 * address could be inside a block.
 *
 * update_p -> Pointer to the skip_alloc entry we are using to hold
 * the update pointers.
 */
static	skip_alloc_t	*find_address(const void *address, const int exact_b,
				      skip_alloc_t *update_p)
{
  int		level_c;
  skip_alloc_t 	*slot_p, *found_p = NULL, *next_p;
  
  /* skip_address_max_level */
  level_c = MAX_SKIP_LEVEL - 1;
  slot_p = skip_address_list;
  
  /* traverse list to smallest entry */
  while (1) {
    
    /* next on we are looking for */
    next_p = slot_p->sa_next_p[level_c];
    
    /*
     * sort by address
     */
    
    /* are we are at the end of a row? */
    if (next_p == NULL) {
      /* just go down a level */
    }
    else if (next_p == found_p
	     || (char *)next_p->sa_mem > (char *)address) {
      /* just go down a level */
    }
    else if ((char *)next_p->sa_mem == (char *)address) {
      /* found it and go down a level */
      found_p = next_p;
    }
    /*
     * (char *)next_p->sa_mem < (char *)address
     */
    else if ((! exact_b)
	     && ((char *)next_p->sa_mem + next_p->sa_total_size >
		 (char *)address)) {
      /*
       * if we are doing loose searches and this block contains this
       * pointer then we have a match
       */
      found_p = next_p;
    }
    else {
      /* next slot is less, go right */
      slot_p = next_p;
      continue;
    }
    
    /* we are lowering the level */
    
    update_p->sa_next_p[level_c] = slot_p;
    if (level_c == 0) {
      break;
    }
    level_c--;
  }
  
  return found_p;
}

/*
 * static skip_alloc_t *find_free_size
 *
 * DESCRIPTION:
 *
 * Look for a specific size in the free skip list.  If it exist then a
 * pointer to the matching slot is returned otherwise NULL.  Either
 * way, the links that were traversed to get there are set in the
 * update slot which has the maximum number of levels.
 *
 * RETURNS:
 *
 * Success - Pointer to the slot which matches the size pair.
 *
 * Failure - NULL
 *
 * ARGUMENTS:
 *
 * address -> Address we are looking for.
 *
 * update_p -> Pointer to the skip_alloc entry we are using to hold
 * the update pointers.
 */
static	skip_alloc_t	*find_free_size(const unsigned int size,
					skip_alloc_t *update_p)
{
  int		level_c, cmp;
  skip_alloc_t 	*slot_p, *found_p = NULL, *next_p;
  
  /* skip_free_max_level */
  level_c = MAX_SKIP_LEVEL - 1;
  slot_p = skip_free_list;
  
  /* traverse list to smallest entry */
  while (1) {
    
    /* next on we are looking for */
    next_p = slot_p->sa_next_p[level_c];
    
    /* are we are at the end of a row? */
    if (next_p == NULL
	|| next_p == found_p) {
      /* just go down a level */
    }
    else {
      cmp = next_p->sa_total_size - size;
      if (cmp < 0) {
	/* next slot is less, go right */
	slot_p = next_p;
	continue;
      }
      else if (cmp == 0) {
	/*
	 * we found a match but it may not be the first slot with this
	 * size and we want the first match
	 */
	found_p = next_p;
      }
    }
    
    /* we are lowering the level */
    
    update_p->sa_next_p[level_c] = slot_p;
    if (level_c == 0) {
      break;
    }
    level_c--;
  }
  
  /* space should be free */
  if (found_p != NULL && (! BIT_IS_SET(found_p->sa_flags, ALLOC_FLAG_FREE))) {
    dmalloc_errno = ERROR_ADDRESS_LIST;
    dmalloc_error("find_free_size");
    return NULL;
  }
  
  return found_p;
}

/*
 * static int insert_slot
 *
 * DESCRIPTION:
 *
 * Insert an address entry into a skip list.
 *
 * RETURNS:
 *
 * Success - 1
 *
 * Failure - 0
 *
 * ARGUMENTS:
 *
 * slot_p <-> Slot that we are inserting into the skip list.
 *
 * free_b -> Insert a free address in the free-size list otherwise it
 * will go into the used address list.
 */
static	int	insert_slot(skip_alloc_t *slot_p, const int free_b)
{
  skip_alloc_t	*adjust_p, *update_p;
  int		level_c;
  
  update_p = skip_update;
  
  if (free_b) {
    (void)find_free_size(slot_p->sa_total_size, update_p);
    /*
     * NOTE: we can get a new_p because there might be other blocks of
     * the same size which we will be inserting before.
     */
  }
  else if (find_address(slot_p->sa_mem, 1 /* exact */, update_p) != NULL) {
    /*
     * we should not have found it since that means that someone has
     * the same size and block-num
     */
    dmalloc_errno = ERROR_ADDRESS_LIST;
    dmalloc_error("insert_slot");
    return 0;
  }
  
  /* update the block skip list */
  for (level_c = 0; level_c <= slot_p->sa_level_n; level_c++) {
    /*
     * We are inserting our new slot after each of the slots in the
     * update array.  So for each level, we get the slot we are
     * adjusting, we take it's next pointers and set them in the new
     * slot, and we point its next pointers to the new slot.
     */
    adjust_p = update_p->sa_next_p[level_c];
    slot_p->sa_next_p[level_c] = adjust_p->sa_next_p[level_c];
    adjust_p->sa_next_p[level_c] = slot_p;
  }
  
  return 1;
}

/*
 * static int alloc_slots
 *
 * DESCRIPTION:
 *
 * Allocate a block of new slots of a certain size and add them to the
 * free list.  If there are none in the linked list then we will
 * allocate a block of the size.
 *
 * RETURNS:
 *
 * Success - Valid pointer to a single block that was allocated for
 * the slots.
 *
 * Failure - NULL
 *
 * ARGUMENTS:
 *
 * level_n -> Number of the level we are looking for.  Set to 0 to
 * have it be chosen at random.
 */
static	void	*alloc_slots(const int level_n)
{
  skip_alloc_t	*new_p;
  entry_block_t	*block_p;
  unsigned int	*magic3_p, magic3;
  int		size, new_c;
  
  if (BIT_IS_SET(_dmalloc_flags, DEBUG_LOG_ADMIN)) {
    dmalloc_message("need a block of slots for level %d", level_n);
  }
  
  /* we need to allocate a new block of the slots of this level */
  block_p = _dmalloc_heap_alloc(BLOCK_SIZE);
  if (block_p == NULL) {
    /* error code set in _dmalloc_heap_alloc */
    return NULL;
  }
  memset(block_p, 0, BLOCK_SIZE);
  admin_block_c++;
  
  /* intialize the block structure */
  block_p->eb_magic1 = ENTRY_BLOCK_MAGIC1;
  block_p->eb_level_n = level_n;
  block_p->eb_magic2 = ENTRY_BLOCK_MAGIC2;
  
  /* add the block on the entry block linked list */
  block_p->eb_next_p = entry_blocks[level_n];
  entry_blocks[level_n] = block_p;
  
  /* put the magic3 at the end of the block */
  magic3_p = (unsigned int *)((char *)block_p + BLOCK_SIZE -
			      sizeof(*magic3_p));
  magic3 = ENTRY_BLOCK_MAGIC3;
  memcpy(magic3_p, &magic3, sizeof(*magic3_p));
  
  /* get the size of the slot */
  size = SKIP_SLOT_SIZE(level_n);
  
  /* add in all of the unused slots to the linked list */
  new_c = 1;
  for (new_p = &block_p->eb_first_slot;
       (char *)new_p + size < (char *)magic3_p;
       new_p = (skip_alloc_t *)((char *)new_p + size)) {
    new_p->sa_level_n = level_n;
    new_p->sa_next_p[0] = entry_free_list[level_n];
    entry_free_list[level_n] = new_p;
    new_c++;
  }