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

/*                                                                         */

/*  ftdbgmem.c                                                             */

/*                                                                         */

/*    Memory debugger (body).                                              */

/*                                                                         */

/*  Copyright 2001, 2002, 2003, 2004, 2005, 2006, 2009 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 FT_CONFIG_STANDARD_LIBRARY_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_PtrDist)(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_PtrDist  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_PtrDist   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;

    /* cast to FT_PtrDist first since void* can be larger */

    /* than FT_UInt32 and GCC 4.1.1 emits a warning       */

    hash  = (FT_UInt32)(FT_PtrDist)(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;

    *pnode     = node;

  Exit:

    return node;

  }

  static void

  ft_mem_table_set( FT_MemTable  table,

                    FT_Byte*     address,

                    FT_ULong     size,

                    FT_Long      delta )

  {

    FT_MemNode  *pnode, node;

    if ( table )

    {

      FT_MemSource  source;

      pnode = ft_mem_table_get_nodep( table, address );

      node  = *pnode;

      if ( node )

      {

        if ( node->size < 0 )

        {

          /* This block was already freed.  Our memory is now completely */

          /* corrupted!                                                  */