heap.cpp

radius协议源码÷The Radius Stack will connect to a Radius Server. This stack implementation is built upo

// 
// Copyright (C) 2000, Ian Cahoon
//	http://ian.cahoon.com/heap
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Library General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Library General Public License for more details.
//
// You should have received a copy of the GNU Library General Public
// License along with this library; if not, write to the
// Free Software Foundation, Inc., 59 Temple Place - Suite 330,
// Boston, MA 02111-1307, USA.
//

//
// Based on: LeakTracer.cc (c) 1999 Erwin S. Andreasen <[e-mail]>
// Homepage: http://www.andreasen.org/LeakTracer/
//

//
// MT safe
//

//     Tue Mar  7 00:33:57 MST 2000: Only use timeval to keep track of the
// 	    allocation and deletion times. Also, when searching for double
// 	    delete, the most likely culprit is the most recent remembered 
// 	    delete, not necessarily the last one in the list (which indicates 
// 	    that it was allocated most recently).


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <execinfo.h>
#include <assert.h>
#include <malloc.h>

#if defined(Linux)
#include <pthread.h>
typedef		pthread_mutex_t			os_mutex_t;
#define		os_mutex_init(mutex)		pthread_mutex_init(mutex, 0)
#define		os_mutex_destroy		pthread_mutex_destroy
#define		os_mutex_lock			pthread_mutex_lock
#define		os_mutex_trylock		pthread_mutex_trylock
#define		os_mutex_unlock			pthread_mutex_unlock

#elif defined(Solaris)
#include <thread.h>
typedef		mutex_t				os_mutex_t;
#define		os_mutex_init(mutex)		mutex_init(mutex, USYNC_THREAD, 0)
#define		os_mutex_destroy		mutex_destroy
#define		os_mutex_lock			mutex_lock
#define		os_mutex_trylock		mutex_trylock
#define		os_mutex_unlock			mutex_unlock

#elif defined(Unixware)
#include <synch.h>
typedef		mutex_t				os_mutex_t;
#define		os_mutex_init(mutex)		mutex_init(mutex, USYNC_THREAD, 0)
#define		os_mutex_destroy		mutex_destroy
#define		os_mutex_lock			mutex_lock
#define		os_mutex_trylock		mutex_trylock
#define		os_mutex_unlock			mutex_unlock

#else
#error OS not supported.

#endif

#define 	MAX_STACK_SIZE		50


#define 	MEM_ALLOC_PATTERN	0xDE
#define 	MEM_FREE_PATTERN	0xFE

void	write_leaks();

struct HeapEntry
{
    void    *	    Allocate(size_t size_, bool array_);
    void	    Free();

    void    *	    memory;
    size_t 	    size;
    int 	    new_return_addr_size;
    void    *	    new_return_addr[MAX_STACK_SIZE];
    int 	    delete_return_addr_size;
    void    *	    delete_return_addr[MAX_STACK_SIZE];

    #if defined(HEAP_TIME_CHECK)
    timeval	    new_time;
    timeval	    delete_time;
    #endif

    bool	    array;
    bool    	    freed;
    HeapEntry	*   next;
};

void * HeapEntry::Allocate(size_t size_, bool array_)
{
    memory = malloc(size_);

    if ( !memory )
    {
	printf("Heap: out of memory.\n");
	assert(0);
    }
    else
    {
    	memset(memory, MEM_ALLOC_PATTERN, size_);
    }
    size    	    	    = size_;
    new_return_addr_size    = backtrace(new_return_addr, MAX_STACK_SIZE);
    delete_return_addr_size = 0;
    array   		    = array_;
    freed		    = false;
    next		    = 0;

    #if defined(HEAP_TIME_CHECK)
    gettimeofday(&new_time, 0);
    timerclear(&delete_time);
    #endif

    return ( memory );
}

void HeapEntry::Free()
{
    delete_return_addr_size = backtrace(delete_return_addr, MAX_STACK_SIZE);

    memset(memory, MEM_FREE_PATTERN, size);

    freed = true;

    #if defined(HEAP_TIME_CHECK)
    gettimeofday(&delete_time, 0);
    #endif

    free(memory);
}

struct Heap
{
    public:
	void		Initialize();
	void	*	Allocate(size_t size, bool array);
	void		Free(void * memory, bool array);
	void		Dump(FILE * file = stderr, 
			     bool   active_only	= true,
			     bool   gdb_format	= true,
			     bool   concise = false); 
	void		Summary(FILE * 	file = stderr);

    private:
	long		active_allocated_objects;
	long		cumulative_allocated_objects;
	long		max_allocated_objects;
	size_t		active_allocated_bytes;
	size_t		cumulative_allocated_bytes;
	size_t		max_allocated_bytes;
	HeapEntry   *	first;
	HeapEntry   *	last;

	os_mutex_t	mutex;
};

void	    	Heap::Initialize()
{
    active_allocated_objects = 0;
    cumulative_allocated_objects = 0;
    max_allocated_objects = 0;
    active_allocated_bytes = 0;
    cumulative_allocated_bytes = 0;
    max_allocated_bytes = 0;
    first = 0;
    last = 0;

    os_mutex_init(&mutex);
}

void	*	Heap::Allocate(size_t size, bool array) 
{
    os_mutex_lock(&mutex);

    active_allocated_objects++;
    cumulative_allocated_objects++;
    active_allocated_bytes 	+= size;
    cumulative_allocated_bytes 	+= size;

    if ( active_allocated_objects > max_allocated_objects )
    {
        max_allocated_objects = active_allocated_objects;
    }
    if ( active_allocated_bytes > max_allocated_bytes )
    {
    	max_allocated_bytes = active_allocated_bytes;
    }

    HeapEntry	* new_entry = (HeapEntry *)malloc(sizeof(HeapEntry));

    if ( !new_entry )
    {
	printf("Heap: out of memory.\n");
	assert(0);
    }

    if ( last == 0 )
    {
    	first = last = new_entry;
    }
    else
    {
	last->next = new_entry;
	last = new_entry;
    }

    void *  memory = new_entry->Allocate(size, array);

    os_mutex_unlock(&mutex);

    return ( memory );
}

#if defined(HEAP_TIME_CHECK)
static	char	*   	print_time(timeval & tv)
{
    static  char    buffer[32];
	    char    time_buffer[10];

    tm	    t;

    localtime_r(&tv.tv_sec, &t);

    strftime(time_buffer, 9, "%T", &t);
    sprintf(buffer, "%s.%.3ld", time_buffer, (long)tv.tv_usec/1000);

    return ( buffer );
}
#endif

void	 	Heap::Free(void * memory_, bool array_)
{
    if ( !memory_ )
    {
    	return;
    }

    os_mutex_lock(&mutex);

    // See if we are freeing active memory.
    //
    bool	    	active = false;

    HeapEntry	*	heapPrevious = 0,
	    	*	current = first;
	
    while ( current )
    {
	if ( current->memory == memory_ && !current->freed )
	{
	    active = true;
	    break;
	}

	heapPrevious = current;
	current = current->next;
    }
	
    // See if we have a double delete.
    //
    if ( !active )
    {
	#if defined(HEAP_TIME_CHECK)

	// last holds the pointer to the last object allocated / freed
	// for this emmory
	//
	HeapEntry	*	last = 0,
		    	*	last_by_time = 0;

	// Find the last object.
	//
	for ( HeapEntry	* pcurrent = first; pcurrent; pcurrent = pcurrent->next )
	{
	    if ( pcurrent->memory == memory_ )
	    {
		last = pcurrent;
		if 	(   !last_by_time
			||  timercmp(&last->delete_time, 
				     &last_by_time->delete_time, 
				     >=) 
			)
		{
	    	    last_by_time = last;
		}
	    }
	}

	// If we have a last (or last_by_time) object, we have a double delete.
	// The object deleted last, by time, is probably the culprit.
	//
	if ( last_by_time )
	{
	    fprintf(stderr, 
	    	    "-><-><-><- HEAP::Free: double delete. Previous delete:\n"
    	    	    "\tMemory: %p, Size: %ld\n"
	            "\tNew:    %s, %8p, %8p\n"
	            "\tDelete: %s, %8p, %8p\n",
		    last_by_time->memory, (long)(last_by_time->size),
		    print_time(last_by_time->new_time),
		    last_by_time->new_return_addr[0],
		    last_by_time->new_return_addr[1],
		    print_time(last_by_time->delete_time),
		    last_by_time->delete_return_addr[0],
		    last_by_time->delete_return_addr[1]);

	    fflush(stderr);

	    return;
	}

	fprintf(stderr, "-><-><-><- HEAP: deleteing memory that was never newed.\n");

    	#else

	fprintf(stderr, "-><-><-><- HEAP: deleteing unallocated memory.\n");

	#endif // defined(HEAP_TIME_CHECK)

	assert(0);
    }

    // Otherwise free it.
    //
    active_allocated_objects--;
    active_allocated_bytes -= current->size;

    current->Free();

    if ( current->array != array_ )
    {
	fprintf(stderr, "-><-><-><- HEAP ERROR: array allocation mismatch. Line: %8p, %8p. -><-><-><-\n",
		current->new_return_addr[0], current->new_return_addr[0]);
    }

    #if !defined(HEAP_DONT_FREE)

    if ( heapPrevious == 0 )
    {
    	first = current->next;
    }
    else
    {
    	heapPrevious->next = current->next;
    }

    if ( last == current )
    {
    	last = heapPrevious;
    }

    free(current);

    #endif // !defined(HEAP_DONT_FREE)
	
    os_mutex_unlock(&mutex);
}

void	Heap::Dump(FILE * fp, bool active_only, bool gdb_format, bool concise)
{
    os_mutex_lock(&mutex);

    if ( gdb_format )
    {
	fprintf(fp, "set prompt\n");
	fprintf(fp, "set listsize 1\n");
	fprintf(fp, "break main\n");
	fprintf(fp, "run\n");

    	for ( HeapEntry * current = first; current; current = current->next )
	{
	    if ( !current->freed )
	    {
	    	if ( !concise )
		{
    	    	    fprintf(fp, "echo \\n\n");
	    	    fprintf(fp, "echo Memory: %p \\n\n", current->memory);
		    fprintf(fp, "echo Size:   %ld\\n\n", (long)(current->size));
		    #if defined(HEAP_TIME_CHECK)
	    	    fprintf(fp, "echo New: %s\\n\n", print_time(current->new_time));
		    #endif
    	    	    for ( int i = 3; i < current->new_return_addr_size; i++ )
		    {
			fprintf(fp, "list *%8p\n", current->new_return_addr[i]);
	    	    }
	            fprintf(fp, "echo \\n\n\n");
		}
		else
		{
    	    	    fprintf(fp, "list *%8p\n", current->new_return_addr[3]);
		}

	    }
	}

    	if ( !concise )
	{
    	    fprintf(fp, 
		    "echo Bytes leaked:          %d, Objects leaked:          %ld\\n\n"
		    "echo Total bytes allocated: %d, Total objects allocated: %ld\\n\n" 
		    "echo Max bytes allocated:   %d, Max objects allocated:   %ld\\n\n", 
		    active_allocated_bytes,     active_allocated_objects,
		    cumulative_allocated_bytes, cumulative_allocated_objects,
		    max_allocated_bytes,	    max_allocated_objects);
	}
	else
	{
	    malloc_stats();
	}

	fflush(fp);
    }
    else
    {
    	fprintf(fp, "Heap::Dump\n");
    	for ( HeapEntry * current = first; current; current = current->next )
	{
	    if ( active_only )
	    {
	    	if ( current->freed )
	    	{
		    continue;
		}

	        fprintf(fp, 
			"Memory: %p, Size: %ld\n"
			"\tNew:    "
			#if defined(HEAP_TIME_CHECK)
			"%s,"
			#endif
			" %8p, %8p\n",
			current->memory, 
			(long)(current->size),
			#if defined(HEAP_TIME_CHECK)
			print_time(current->new_time),
			#endif
			( current->new_return_addr_size > 0 
			    ? current->new_return_addr[0]
			    : 0 ),
			( current->new_return_addr_size > 1
			    ? current->new_return_addr[1]
			    : 0 )
			);
	    }

	    else
	    {
		fprintf(fp, 
			"Memory: %p, Size: %ld\n"
			"\tNew:    "
			#if defined(HEAP_TIME_CHECK)
			"%s,"
			#endif
			" %8p, %8p\n"
			"\tDelete: "
			#if defined(HEAP_TIME_CHECK)
			"%s,"
			#endif
			" %8p, %8p\n",
			current->memory, (long)(current->size),
			#if defined(HEAP_TIME_CHECK)
			print_time(current->new_time),
			#endif
			( current->new_return_addr_size > 0 
			    ? current->new_return_addr[0]
			    : 0 ),
			( current->new_return_addr_size > 1
			    ? current->new_return_addr[1]
			    : 0 ),
			#if defined(HEAP_TIME_CHECK)
			print_time(current->delete_time),
			#endif
			( current->delete_return_addr_size > 0 
			    ? current->delete_return_addr[0]
			    : 0 ),
			( current->delete_return_addr_size > 0 
			    ? current->delete_return_addr[0]
			    : 0 )
    	    	    	);
    	    }   
    	}

    	Summary(fp);
    }

    os_mutex_unlock(&mutex);
}

void	Heap::Summary(FILE * fp)
{
    os_mutex_lock(&mutex);

    fprintf(fp, 
	    "Bytes active:          %d, Objects active:          %ld\n"
	    "Total bytes allocated: %d, Total objects allocated: %ld\n" 
	    "Max bytes allocated:   %d, Max objects allocated:   %ld\n",
	    active_allocated_bytes, 	active_allocated_objects,
	    cumulative_allocated_bytes,	cumulative_allocated_objects,
	    max_allocated_bytes,	max_allocated_objects);

    fflush(fp);

    os_mutex_unlock(&mutex);
}

static Heap	*	heap = 0;

void	create_heap()
{
    heap = (Heap *)malloc(sizeof(Heap));
    heap->Initialize();

    atexit(write_leaks);
}

void * 	operator new(size_t size) 
{
    if ( !heap ) create_heap();
    return ( heap->Allocate(size, false) );
}

void * 	operator new[] (size_t size) 
{
    if ( !heap ) create_heap();
    return ( heap->Allocate(size, true) );
}

void 	operator delete (void * memory) 
{
    if ( !heap ) create_heap();
    return ( heap->Free(memory, false) );
}

void 	operator delete[] (void * memory) 
{
    if ( !heap ) create_heap();
    return ( heap->Free(memory, true) );
}

void	HeapDump(
    FILE    * 	file		= stderr, 
    bool 	active_only	= true,
    bool 	gdb_format	= true,
    bool    	concise     	= false
)	
{
    if ( !heap ) create_heap();
    heap->Dump(file, active_only, gdb_format, concise);
}

void	HeapDumpGDBFormat(FILE * file = stderr)
{
    if ( !heap ) create_heap();
    heap->Dump(file, true, true, false);
}

void	HeapSummary()
{
    if ( !heap ) create_heap();
    heap->Summary();
}

// This ought to run at the very end. It requires it to be put last on the 
// linker line.
//
void	write_leaks() __attribute__((destructor));
void	write_leaks() 
{
    if ( !heap )
    {
    	return;
    }
	
    const char *filename = getenv("LEAKTRACE_FILE") ? : "leak.out";
    FILE * fp = 0;
    
    if ( !(fp = fopen(filename, "w")) )
    {
    	fprintf(stderr, "Heap: Could not open %s: %%m\n", filename);
    	return;
    }

    fprintf(fp, "echo # Command: gdb -q -n -batch <filename> -x %s\\n\necho #\\n\n", filename);
    heap->Dump(fp, true, true);

    fclose(fp);
}