/***************************************************************************//*                                                                         *//*  ftdbgmem.c                                                             *//*                                                                         *//*    Memory debugger (body).                                              *//*                                                                         *//*  Copyright 2001, 2002, 2003, 2004, 2005, 2006 by                        *//*  David Turner, Robert Wilhelm, and Werner Lemberg.                      *//*                                                                         *//*  This file is part of the FreeType project, and may only be used,       *//*  modified, and distributed under the terms of the FreeType project      *//*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     *//*  this file you indicate that you have read the license and              *//*  understand and accept it fully.                                        *//*                                                                         *//***************************************************************************/#include <ft2build.h>#include FT_CONFIG_CONFIG_H#include FT_INTERNAL_DEBUG_H#include FT_INTERNAL_MEMORY_H#include FT_SYSTEM_H#include FT_ERRORS_H#include FT_TYPES_H#ifdef FT_DEBUG_MEMORY#define  KEEPALIVE /* `Keep alive' means that freed blocks aren't released                    * to the heap.  This is useful to detect double-frees                    * or weird heap corruption, but it uses large amounts of                    * memory, however.                    */#include <stdio.h>#include <stdlib.h>  FT_BASE_DEF( const char* )  _ft_debug_file   = 0;  FT_BASE_DEF( long )         _ft_debug_lineno = 0;  extern void  FT_DumpMemory( FT_Memory  memory );  typedef struct FT_MemSourceRec_*  FT_MemSource;  typedef struct FT_MemNodeRec_*    FT_MemNode;  typedef struct FT_MemTableRec_*   FT_MemTable;#define FT_MEM_VAL( addr )  ((FT_ULong)(FT_Pointer)( addr ))  /*   *  This structure holds statistics for a single allocation/release   *  site.  This is useful to know where memory operations happen the   *  most.   */  typedef struct  FT_MemSourceRec_  {    const char*   file_name;    long          line_no;    FT_Long       cur_blocks;   /* current number of allocated blocks */    FT_Long       max_blocks;   /* max. number of allocated blocks    */    FT_Long       all_blocks;   /* total number of blocks allocated   */    FT_Long       cur_size;     /* current cumulative allocated size */    FT_Long       max_size;     /* maximum cumulative allocated size */    FT_Long       all_size;     /* total cumulative allocated size   */    FT_Long       cur_max;      /* current maximum allocated size */    FT_UInt32     hash;    FT_MemSource  link;  } FT_MemSourceRec;  /*   *  We don't need a resizable array for the memory sources, because   *  their number is pretty limited within FreeType.   */#define FT_MEM_SOURCE_BUCKETS  128  /*   *  This structure holds information related to a single allocated   *  memory block.  If KEEPALIVE is defined, blocks that are freed by   *  FreeType are never released to the system.  Instead, their `size'   *  field is set to -size.  This is mainly useful to detect double frees,   *  at the price of large memory footprint during execution.   */  typedef struct  FT_MemNodeRec_  {    FT_Byte*      address;    FT_Long       size;     /* < 0 if the block was freed */    FT_MemSource  source;#ifdef KEEPALIVE    const char*   free_file_name;    FT_Long       free_line_no;#endif    FT_MemNode    link;  } FT_MemNodeRec;  /*   *  The global structure, containing compound statistics and all hash   *  tables.   */  typedef struct  FT_MemTableRec_  {    FT_ULong         size;    FT_ULong         nodes;    FT_MemNode*      buckets;    FT_ULong         alloc_total;    FT_ULong         alloc_current;    FT_ULong         alloc_max;    FT_ULong         alloc_count;    FT_Bool          bound_total;    FT_ULong         alloc_total_max;    FT_Bool          bound_count;    FT_ULong         alloc_count_max;    FT_MemSource     sources[FT_MEM_SOURCE_BUCKETS];    FT_Bool          keep_alive;    FT_Memory        memory;    FT_Pointer       memory_user;    FT_Alloc_Func    alloc;    FT_Free_Func     free;    FT_Realloc_Func  realloc;  } FT_MemTableRec;#define FT_MEM_SIZE_MIN  7#define FT_MEM_SIZE_MAX  13845163#define FT_FILENAME( x )  ((x) ? (x) : "unknown file")  /*   *  Prime numbers are ugly to handle.  It would be better to implement   *  L-Hashing, which is 10% faster and doesn't require divisions.   */  static const FT_UInt  ft_mem_primes[] =  {    7,    11,    19,    37,    73,    109,    163,    251,    367,    557,    823,    1237,    1861,    2777,    4177,    6247,    9371,    14057,    21089,    31627,    47431,    71143,    106721,    160073,    240101,    360163,    540217,    810343,    1215497,    1823231,    2734867,    4102283,    6153409,    9230113,    13845163,  };  static FT_ULong  ft_mem_closest_prime( FT_ULong  num )  {    FT_UInt  i;    for ( i = 0;          i < sizeof ( ft_mem_primes ) / sizeof ( ft_mem_primes[0] ); i++ )      if ( ft_mem_primes[i] > num )        return ft_mem_primes[i];    return FT_MEM_SIZE_MAX;  }  extern void  ft_mem_debug_panic( const char*  fmt,                      ... )  {    va_list  ap;    printf( "FreeType.Debug: " );    va_start( ap, fmt );    vprintf( fmt, ap );    va_end( ap );    printf( "\n" );    exit( EXIT_FAILURE );  }  static FT_Pointer  ft_mem_table_alloc( FT_MemTable  table,                      FT_Long      size )  {    FT_Memory   memory = table->memory;    FT_Pointer  block;    memory->user = table->memory_user;    block = table->alloc( memory, size );    memory->user = table;    return block;  }  static void  ft_mem_table_free( FT_MemTable  table,                     FT_Pointer   block )  {    FT_Memory  memory = table->memory;    memory->user = table->memory_user;    table->free( memory, block );    memory->user = table;  }  static void  ft_mem_table_resize( FT_MemTable  table )  {    FT_ULong  new_size;    new_size = ft_mem_closest_prime( table->nodes );    if ( new_size != table->size )    {      FT_MemNode*  new_buckets;      FT_ULong     i;      new_buckets = (FT_MemNode *)                      ft_mem_table_alloc( table,                                          new_size * sizeof ( FT_MemNode ) );      if ( new_buckets == NULL )        return;      FT_ARRAY_ZERO( new_buckets, new_size );      for ( i = 0; i < table->size; i++ )      {        FT_MemNode  node, next, *pnode;        FT_ULong    hash;        node = table->buckets[i];        while ( node )        {          next  = node->link;          hash  = FT_MEM_VAL( node->address ) % new_size;          pnode = new_buckets + hash;          node->link = pnode[0];          pnode[0]   = node;          node = next;        }      }      if ( table->buckets )        ft_mem_table_free( table, table->buckets );      table->buckets = new_buckets;      table->size    = new_size;    }  }  static FT_MemTable  ft_mem_table_new( FT_Memory  memory )  {    FT_MemTable  table;    table = (FT_MemTable)memory->alloc( memory, sizeof ( *table ) );    if ( table == NULL )      goto Exit;    FT_ZERO( table );    table->size  = FT_MEM_SIZE_MIN;    table->nodes = 0;    table->memory = memory;    table->memory_user = memory->user;    table->alloc   = memory->alloc;    table->realloc = memory->realloc;    table->free    = memory->free;    table->buckets = (FT_MemNode *)                       memory->alloc( memory,                                      table->size * sizeof ( FT_MemNode ) );    if ( table->buckets )      FT_ARRAY_ZERO( table->buckets, table->size );    else    {      memory->free( memory, table );      table = NULL;    }  Exit:    return table;  }  static void  ft_mem_table_destroy( FT_MemTable  table )  {    FT_ULong  i;    FT_DumpMemory( table->memory );    if ( table )    {      FT_Long   leak_count = 0;      FT_ULong  leaks      = 0;      /* remove all blocks from the table, revealing leaked ones */      for ( i = 0; i < table->size; i++ )      {        FT_MemNode  *pnode = table->buckets + i, next, node = *pnode;        while ( node )        {          next       = node->link;          node->link = 0;          if ( node->size > 0 )          {            printf(              "leaked memory block at address %p, size %8ld in (%s:%ld)\n",              node->address, node->size,              FT_FILENAME( node->source->file_name ),              node->source->line_no );            leak_count++;            leaks += node->size;            ft_mem_table_free( table, node->address );          }          node->address = NULL;          node->size    = 0;          ft_mem_table_free( table, node );          node = next;        }        table->buckets[i] = 0;      }      ft_mem_table_free( table, table->buckets );      table->buckets = NULL;      table->size  = 0;      table->nodes = 0;      /* remove all sources */      for ( i = 0; i < FT_MEM_SOURCE_BUCKETS; i++ )      {        FT_MemSource  source, next;        for ( source = table->sources[i]; source != NULL; source = next )        {          next = source->link;          ft_mem_table_free( table, source );        }        table->sources[i] = NULL;      }      printf(        "FreeType: total memory allocations = %ld\n", table->alloc_total );      printf(        "FreeType: maximum memory footprint = %ld\n", table->alloc_max );      ft_mem_table_free( table, table );      if ( leak_count > 0 )        ft_mem_debug_panic(          "FreeType: %ld bytes of memory leaked in %ld blocks\n",          leaks, leak_count );      printf( "FreeType: No memory leaks detected!\n" );    }  }  static FT_MemNode*  ft_mem_table_get_nodep( FT_MemTable  table,                          FT_Byte*     address )  {    FT_ULong     hash;    FT_MemNode  *pnode, node;    hash  = FT_MEM_VAL( address );    pnode = table->buckets + ( hash % table->size );    for (;;)    {      node = pnode[0];      if ( !node )        break;      if ( node->address == address )        break;      pnode = &node->link;    }    return pnode;  }  static FT_MemSource  ft_mem_table_get_source( FT_MemTable  table )  {    FT_UInt32     hash;    FT_MemSource  node, *pnode;    hash  = (FT_UInt32)(void*)_ft_debug_file +              (FT_UInt32)( 5 * _ft_debug_lineno );    pnode = &table->sources[hash % FT_MEM_SOURCE_BUCKETS];    for ( ;; )    {      node = *pnode;      if ( node == NULL )        break;      if ( node->file_name == _ft_debug_file &&           node->line_no   == _ft_debug_lineno   )        goto Exit;      pnode = &node->link;    }    node = (FT_MemSource)ft_mem_table_alloc( table, sizeof ( *node ) );    if ( node == NULL )      ft_mem_debug_panic(        "not enough memory to perform memory debugging\n" );    node->file_name = _ft_debug_file;    node->line_no   = _ft_debug_lineno;    node->cur_blocks = 0;    node->max_blocks = 0;    node->all_blocks = 0;    node->cur_size   = 0;    node->max_size   = 0;    node->all_size   = 0;    node->cur_max    = 0;    node->link = NULL;    node->hash = hash;