memory_util.c

关于遗传算法的一些见地。特别是关于简单遗传程序设计的实现。

/**********************************************************************
  memory_util.c
 **********************************************************************

  memory_util - Usage control wrapper around standard malloc() etc.
  Copyright ©1999-2005, Stewart Adcock <[e-mail]>
  All rights reserved.

  The latest version of this program should be available at:
  http://gaul.sourceforge.net/

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.  Alternatively, if your project
  is incompatible with the GPL, I will probably agree to requests
  for permission to use the terms of any other license.

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY WHATSOEVER.

  A full copy of the GNU General Public License should be in the file
  "COPYING" provided with this distribution; if not, see:
  http://www.gnu.org/

 **********************************************************************

  Synopsis:	memory_util.c is intended as a general purpose,
		portable, memory tracking package that replaces the
		system calls realloc, calloc and realloc and
		free with "safer" routines while keeping track of all
		the memory currently allocated.
		Additional facilities to enable array overflow checks
		are included.

		The neat thing about all this is that it can sit over
		the top of any other memory debugging library which
		replaces the standard malloc routines, transparently.

		Has an easy-to-use memory chunk implementation.
		(see memory_chunk.c)
		Chunks are created/destroyed using
		mem_chunk_new() and mem_chunk_destroy().
		Individual atoms are created/destroyed using
		mem_chunk_alloc() and mem_chunk_free().

		Compile the code with MEMORY_ALLOC_SAFE for simple
		wrappers around the standard system allocation memory
		routines.  Compile with MEMORY_ALLOC_DEBUG for fully
		auditing wrappers.  Compile with neither for the
		standard routines only.  When MEMORY_ALLOC_DEBUG is
		defined or MEMORY_CHUNKS_MIMIC is not defined, my AVL
		tree implementation is required.

		The tree lookup key (AVLKey) must be capable of
		storing any arbitrary memory address on your machine.

		FAQ:
		Q. Why not just use Purify?
		A. I can't afford it.
		Q. Well, ElectricFence is free - so why not use that?
		A. It is horrendously slow, and a huge memory hog.

		For OpenMP code, USE_OPENMP must be defined and 
		memory_init_openmp() must be called prior to any
		other function.

  To do:	A lot!

		Record mem_chunk allocations in the same way as xalloc allocations.

		Don't really deallocate memory - reuse later.  This would enable the possibility of detecting memory access after it has been free-ed.
		Need memory_final_clearup() to deallocate all memory -and- the memory table!
		Use random number generator which does not interfere with system random number generator.
		Code for low memory simulation.  i.e. impose limit on memory allocation.  (I currently use the shell's built-in resource limit for this)

		Need shortened version of check_mptr() - check_new_mptr()
		Use my helga_log functions for logging? (a) would work okay with MP/MT code, and (b) enable logging to a file.

		memory_diagnostics()
		Compile as libmemory.so

		Adapt padding so alignment isn't broken on Alpha processors.

	???	Optional automatic garbage collection.

	*->	Use helga_log functions for logging.
	*->	Rewrite padding - arbitrary sizes.

	*->	Reintroduce random padding.

		alloca() like function.

		s_malloc0() etc. would be useful.

  Bugs:		Padding causes data to become misaligned on alpha processors.
		These function names aren't strictly allowed under ISO C99!

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

#include "gaul/memory_util.h"

/*
 * The memory table structure.
 */
typedef struct mem_record_t
  {
  void		*mptr;		/* the pointer value for this block of memory (may not be real start of memory block) */
  size_t	mem;		/* the total number of bytes in this block (the actual amount incl. padding) */
  size_t	rmem;		/* the amount of memory the calling routine requested, note: rmem<=mem */
  char		label[64];	/* the variable/label name associated with this memory */
  char  	func[64];	/* the function the original allocation routine was from */
  char		file[64];	/* file of memory allocation request  */
/* Get rid of [64]! use pointer instead.  Will also save use of strcpy() */
  int		line;		/* line of memory allocation request */
  char		pad_high[8];	/* chars added to test for overflow */
  char		pad_low[8];	/*  - " -             - " -   underflow */
  size_t	pad_ls;		/* amount of pre-padding */
  size_t	pad_hs;		/* amount of post-padding */
  } mem_record;

/*
 * Global state variables.
 */

THREAD_LOCK_DEFINE_STATIC(memory_mem_record_chunk);
THREAD_LOCK_DEFINE_STATIC(memory_memtree);
#if USE_OPENMP == 1
static boolean memory_openmp_initialised = FALSE;
#endif

static MemChunk *mem_record_chunk=NULL;	/* the memory record buffer. */
static AVLTree	*memtree=NULL;		/* the global memory allocation tree. */
static int	num_mem;		/* the number of entries in the memory table. */
static int	max_mem;		/* the current size of the memory table. */
static int	allocated_mem;		/* the total memory currently allocated. */
static int	most_mem;		/* record of maximum allocated memory. */
static int	memory_verbose=1;	/* level of reporting. */
static int	memory_strict=3;	/* level of strictness for uninitialized memory. */
static int	memory_bounds=0;	/* level of automatic bound checking. */
static int	memory_padding=0;	/* variables for memory padding FIXME: replace with pad_size_low and pad_size_high. */
static int	memory_reset_bv=1;	/* reset padding after memory violations detected. */
static int	memory_count_bv=0;	/* count total number of bounds violations encountered. */
static int	memory_count_if=0;	/* count total number of invalid free calls. */
static size_t	memory_size_pad=sizeof(char)*8;	/* Amount of padding to use. */

static FILE	*memory_log_file=NULL;	/* File handle for log file */
static long	memory_count_malloc=0;	/* count total number of s_malloc() calls. */
static long	memory_count_calloc=0;	/* count total number of s_calloc() calls. */
static long	memory_count_realloc=0;	/* count total number of s_realloc() calls. */
static long	memory_count_strdup=0;	/* count total number of s_strdup() calls. */
static long	memory_count_free=0;	/* count total number of s_free() calls. */

static int	node_count=0;		/* counting tree nodes for debugging. */

/*
 * This function must be called before any other functions is OpenMP
 * code is to be used.  Can be safely called when OpenMP code is not
 * being used, and can be safely called more than once.
 */
void memory_init_openmp(void)
  {

#if USE_OPENMP == 1
  if (memory_openmp_initialised == FALSE)
    {
    omp_init_lock(&memory_mem_record_chunk);
    omp_init_lock(&memory_memtree);
    memory_openmp_initialised = TRUE;
    }
#endif

  return;
  }


/*
 * avltree.c replacements to avoid usage of the local
 * malloc functions.
 */

static AVLKey key_func(constvpointer data)
  {
  return (AVLKey) (((mem_record *)data)->mptr);
  }

/*
static AVLTree *replacement_avltree_new(void)
  {
  AVLTree	*tree;

  if ( !(tree = malloc(sizeof(AVLTree))) )
    die("Unable to malloc memory!");

  tree->root = NULL;
  tree->key_generate_func = key_func;

  return tree;
  }
*/

/*
 * Allocating/Deallocating mem_record structures.
 */

static mem_record *mem_record_new(void)
  {
  mem_record *mr;

  THREAD_LOCK(memory_mem_record_chunk);
  if (!mem_record_chunk) mem_record_chunk = mem_chunk_new(sizeof(mem_record), 1024);

  mr = (mem_record *)mem_chunk_alloc(mem_record_chunk);
  THREAD_UNLOCK(memory_mem_record_chunk);

  num_mem++;

  return mr;
  }


static void mem_record_free(mem_record *mr)
  {
  mem_chunk_free(mem_record_chunk, (vpointer) mr);

  num_mem--;

  return;
  }


static void memtree_new(void)
  {
  if (memtree) die("Memory tree already exists.");

  THREAD_LOCK(memory_memtree);
/*
  memtree = replacement_avltree_new();
*/
  memtree = avltree_new(key_func);
  THREAD_UNLOCK(memory_memtree);

  return;
  }


/*
static void memtree_destroy(void)
  {
  if (!memtree) die("Unable to destroy non-existant tree.");

  THREAD_LOCK(memory_memtree);
  avltree_destroy(memtree);
  THREAD_UNLOCK(memory_memtree);

  return;
  }
*/


/**********************************************************************
  void memory_open_log()
  synopsis:	Write messages to log file.
  parameters:   const char *fname	File name for logfile.
  return:	none
  last updated: 04/01/00
 **********************************************************************/

void memory_open_log(const char *fname)
  {
  if (memory_log_file) fclose(memory_log_file);

  memory_log_file = fopen(fname, "a");

  memory_write_log("Log file opened.");

  return;
  }


/**********************************************************************
  void memory_write_log()
  synopsis:	Write messages to log file, if logfile has been opened.
  parameters:   const char *text	String to write to log file.
  return:	none
  last updated: 04/01/00
 **********************************************************************/

void memory_write_log(const char *text)
  {
  if (memory_log_file)
    {
    time_t t = time(NULL);
    fprintf(memory_log_file, "%s: %s\n", ctime(&t), text);
    }

  return;
  }


/**********************************************************************
  void memory_fwrite_log()
  synopsis:	Write formatted messages to log file, if logfile
		has been opened.
  parameters:   const char *format, args...	Stuff to write to log file.
  return:	none
  last updated: 04/01/00
 **********************************************************************/

void memory_fwrite_log(const char *format, ...)
  {
  va_list	args;
  char		text[2048];
  int		len;

  if (memory_log_file)
    {
    time_t t = time(NULL);

    va_start(args, format);
    vsnprintf(text, 2047, format, args);	/* 2047 so tacking on newline doesn't cause overflow */
    va_end(args);

/* Was it an empty format? */
    if (*text == '\0') return;

/* Tack on a '\n' if necessary. */
    len = strlen(text)-1;
    if (text[len] != '\n')
      {
      text[len++] = '\n';
      text[len] = '\0';
      }

    fprintf(memory_log_file, "%s: %s\n", ctime(&t), text);
    }

  return;
  }


static boolean table_traverse(AVLKey key, vpointer data, vpointer userdata)
  {
  mem_record	*mr=data;

  node_count++;

  printf("%d: ", node_count);

/* check. */
/*
  if (key != (AVLKey) mr->mptr)
    printf("key failure (%p %p) ", (vpointer) key, (vpointer) ((AVLKey)mr->mptr));
*/

/*  printf(" %s\t %s\t %s\t %d\t %Zd\t %Zd\t (%p)\n",mr->label,mr->func,mr->file,mr->line,mr->mem,mr->rmem,mr->mptr);*/
  printf(" %s\t %s\t %s\t %d\t %lu\t %lu\t (%p)\n",mr->label,mr->func,mr->file,mr->line,(unsigned long)mr->mem,(unsigned long)mr->rmem,mr->mptr);

  return FALSE;
  }


static boolean bounds_traverse(AVLKey key, vpointer data, vpointer userdata)
  {
  mem_record	*mr=data;

  node_count++;

/* check. */
/*
  if (key != (AVLKey) mr->mptr)
    printf("key failure (%p %p) ", (vpointer) key, (vpointer) ((AVLKey)mr->mptr));
*/

  if (memory_check_bounds(mr->mptr)!=0)
    printf("violation! %s\t %s\t %s\t %d\t %lu\t %lu\t (%p)\n",mr->label,mr->func,mr->file,mr->line,(unsigned long)mr->mem,(unsigned long)mr->rmem,mr->mptr);

/*    printf("violation! %s\t %s\t %s\t %d\t %Zd\t %Zd\t (%p)\n",mr->label,mr->func,mr->file,mr->line,mr->mem,mr->rmem,mr->mptr);*/

  return FALSE;
  }


/**********************************************************************
  match_mptr()
  synopsis:	This is the fundamental memory table check.  Returns
		the pointer to the relevant structure, or NULL.
  parameters:   
  return:
  last updated:	30/12/00
 **********************************************************************/

static mem_record *match_mptr(void *mptr)
  {
  return (mem_record *)avltree_lookup_key(memtree, (AVLKey) mptr);
  }


/**********************************************************************
  check_mptr()
  synopsis:	This is the function for validating a new pointer.
		Note that passing current as NULL indicates
		that this pointer is not expected to have a entry,
		i.e. it is new or outside the table scope, e.g. its
		the memory table itself.
		TRUE is returned if pointer's records seem okay.
  parameters:   
  return:
  last updated: 01/12/98
 **********************************************************************/

static int check_mptr(void *mptr, mem_record *current)
  {
  mem_record	*i;