Initial commit, includes Lua with broken Luabind as a backup for branching purposes

[terrastrategy.git] / src / memory / mmgr.cpp

//
//  Copyright (C) 2008 by Martin Moracek
//
//  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.
//
//  This program 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 General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//

// ----------------------------------------------------------------------------
// Originally created on 12/22/2000 by Paul Nettle
//
// Copyright 2000, Fluid Studios, Inc., all rights reserved.
//
// For more information, visit HTTP://www.FluidStudios.com
// ----------------------------------------------------------------------------

/**
 *  @file mmgr.cpp
 *
 *  Contains implementation of memory management.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <time.h>
#include <iomanip>

#include "vfs/logfile.h"

#include "platform.h"
#include "assertion.h"
#include "types.h"
#include "config.h"

#ifdef MEM_MANAGER_ON

#include "memory/mmgr.h"

#include "mem_off.h"

// May be used for debuggin purposes in the future.

// #define TEST_MEMORY_MANAGER

// Enable this sucker if you really want to stress-test your app's
// memory usage, or to help find hard-to-find bugs

// #define STRESS_TEST

// Enable this sucker if you want to stress-test your app's error-handling.
// Set RANDOM_FAIL to the percentage of failures you want to test
// with (0 = none, >100 = all failures).

// #define RANDOM_FAILURE 10.0

namespace tre {

  namespace {

    struct AllocUnit {
      size_t actualSize;
      size_t reportedSize;
      void * actualAddress;
      void * reportedAddress;
      char srcFile[40];
      char srcFunc[40];
      uint srcLine;
      ::tre::AllocType allocType;
      bool breakOnDealloc;
      bool breakOnRealloc;
      uint allocNumber;

      AllocUnit * next;
      AllocUnit * prev;
    };

   /*
    *  Locals -- modify these flags to suit your needs
    */
    #ifdef STRESS_TEST
      const uint hashBits = 12;
      bool randomWipe = true;
      bool alwaysValidateAll = true;
      bool alwaysLogAll = true;
      bool alwaysWipeAll = true;
      bool cleanupLogOnFirstRun = true;
      const uint paddingSize = 1024; // An extra 8K per allocation!
    #else /* STRESS_TEST */
      const uint hashBits = 12;
      bool randomWipe = false;
      bool alwaysValidateAll = false;
      bool alwaysLogAll = false;
      bool alwaysWipeAll = true;
      bool cleanupLogOnFirstRun = true;
      const uint paddingSize = 4;
    #endif /* STRESS_TEST */

   /*
    *  These values will be used to fill unused and deallocated RAM,
    */
    uint32 prefixPattern = 0xbaadf00d;
    uint32 postfixPattern = 0xdeadc0de;
    uint32 unusedPattern = 0xfeedface;
    uint32 releasedPattern = 0xdeadbeef;

   /*
    *  Other locals
    */
    const unsigned hashSize = 1 << hashBits;
    const char * allocationTypes[] = {"unknown", "new", "new[]", "malloc",
      "calloc", "realloc", "delete", "delete[]", "free"};

    AllocUnit * hashTable[hashSize];
    AllocUnit * reservoir;
    uint currentAllocationCount = 0;  // tracked allocations only
    uint breakOnAllocationCount = 0;
    MemStats stats;
    const char * sourceFile = "??";
    const char * sourceFunc = "??";
    uint sourceLine = 0;
    AllocUnit ** reservoirBuffer = NULL;
    uint reservoirBufferSize = 0;

    bool released = false;      // do not allocate any more resources

   /*
    *  Local functions only
    */
    const char * SourceFileStripper(const char * file)
    {
      const char * ptr = strrchr(file, '\\');
      if(ptr)
        return ptr + 1;
      ptr = strrchr(file, '/');
      if(ptr)
        return ptr + 1;
      return file;
    }

    const char * OwnerString(const char * srcFile,
      unsigned srcLine, const char * srcFunc)
    {
      static char str[90];
      memset(str, 0, sizeof(str));

      sprintf(str, "%s(%05d)::%s", SourceFileStripper(srcFile),
        srcLine, srcFunc);
      return str;
    }

    const char * InsertCommas(unsigned value)
    {
      static char str[30];
      memset(str, 0, sizeof(str));
      sprintf(str, "%u", value);
      if(strlen(str) > 3)
      {
        memmove(&str[strlen(str) - 3], &str[strlen(str) - 4], 4);
        str[strlen(str) - 4] = ',';
      }
      if(strlen(str) > 7)
      {
        memmove(&str[strlen(str) - 7], &str[strlen(str) - 8], 8);
        str[strlen(str) - 8] = ',';
      }
      if(strlen(str) > 11)
      {
        memmove(&str[strlen(str) - 11], &str[strlen(str) - 12], 12);
        str[strlen(str) - 12] = ',';
      }
      return str;
    }

    const char * MemorySizeString(unsigned long size)
    {
      static char str[90];
      if(size > (1024 * 1024))
        sprintf(str, "%10s (%7.2fM)", InsertCommas(size),
          static_cast<float>(size) / (1024.0f * 1024.0f));
      else if (size > 1024)
        sprintf(str, "%10s (%7.2fK)", InsertCommas(size),
          static_cast<float>(size) / 1024.0f);
      else
        sprintf(str, "%10s bytes     ", InsertCommas(size));
      return str;
    }

    AllocUnit * FindAllocUnit(const void * address)
    {
      // Just in case...
      BREAK_ASSERT(address != NULL);

      // Use the address to locate the hash index. Note that we shift off
      // the lower four bits. This is because most allocated addresses will be
      // on four-, eight- or even sixteen-byte boundaries. If we didn't do
      // this, the hash index would not have very good coverage.
      uint hashIndex = (reinterpret_cast<uptr>(
        address) >> 4) & (hashSize - 1);
      AllocUnit * ptr = hashTable[hashIndex];

      while(ptr) {
        if (ptr->reportedAddress == address)
          return ptr;
        ptr = ptr->next;
      }
      return NULL;
    }

    size_t CalcActualSize(size_t reportedSize)
    {
      return reportedSize + paddingSize * sizeof(int32) * 2;
    }

    size_t CalcReportedSize(const size_t actualSize)
    {
      return actualSize - paddingSize * sizeof(int32) * 2;
    }

    void * GetReportedAddress(const void * actualAddress)
    {
      // We allow this...
      if(!actualAddress)
        return NULL;

      // Just account for the padding
      return const_cast<byte*>(reinterpret_cast<const byte*>(actualAddress))
        + sizeof(int32) * paddingSize;
    }

    void WipeWithPattern(AllocUnit * allocUnit, int32 pattern,
      uint origReportedSize = 0)
    {
      // For a serious test run, we use wipes of random a random value. However,
      // if this causes a crash, we don't want it to crash in a differnt place
      // each time, so we specifically DO NOT call srand. If, by chance your
      // program calls srand(), you may wish to disable that when running with
      // a random wipe test. This will make any crashes more consistent so they
      // can be tracked down easier.
      if(randomWipe) {
        pattern = ((rand() & 0xff) << 24) | ((rand() & 0xff) << 16)
          | ((rand() & 0xff) << 8) | (rand() & 0xff);
      }

      //  We should wipe with 0's if we're not in debug mode, so we can help
      // hide bugs if possible when we release the product. So uncomment the
      // following line for releases.

      // Note that the "alwaysWipeAll" should be turned on for this to have
      // effect, otherwise it won't do much good. But we'll leave it this way
      // (as an option) because this does slow things down.
  //     pattern = 0;

      // This part of the operation is optional
      if(alwaysWipeAll && allocUnit->reportedSize > origReportedSize) {
        // Fill the bulk
        int32 * lptr = reinterpret_cast<int32*>(allocUnit->reportedAddress)
          + origReportedSize;
        int length = static_cast<int>(allocUnit->reportedSize
          - origReportedSize);

        for (int i = 0; i < (length >> 2); ++i, ++lptr) {
          *lptr = pattern;
        }

        // Fill the remainder
        uint shiftCount = 0;
        char * cptr = reinterpret_cast<char *>(lptr);
        for(int i = 0; i < (length & 0x3); ++i, ++cptr, shiftCount += 8) {
          *cptr = static_cast<char>(
            (pattern & (0xff << shiftCount)) >> shiftCount);
        }
      }

      // Write in the prefix/postfix bytes
      int32 * pre = reinterpret_cast<int32*>(allocUnit->actualAddress);
      int32 * post = reinterpret_cast<int32*>(reinterpret_cast<byte*>(
        allocUnit->actualAddress) + allocUnit->actualSize
        - paddingSize * sizeof(int32));
      for(uint i = 0; i < paddingSize; ++i, ++pre, ++post) {
        *pre = prefixPattern;
        *post = postfixPattern;
      }
    }

    uint CalcUnused(const AllocUnit * allocUnit)
    {
      const uint32 * ptr =
        reinterpret_cast<const uint32*>(allocUnit->reportedAddress);
      uint count = 0;

      for(uint i = 0; i < allocUnit->reportedSize;
          i += sizeof(int32), ++ptr) {
        if(*ptr == unusedPattern)
          count += sizeof(int32);
      }
      return count;
    }

    uint CalcLeaks(void)
    {
      uint res = 0;
      for (uint i = 0; i < hashSize; ++i) {
        AllocUnit * ptr = hashTable[i];
        while(ptr) {
          // skip external allocations
          if(ptr->srcLine)
            ++res;
          ptr = ptr->next;
        }
      }
      return res;
    }

    void DumpAllocations(std::ostream & out)
    {
      out << "Alloc.   Addr       Size       Addr       Size               "
            "       BreakOn BreakOn              \n"
          << "Number Reported   Reported    Actual     Actual    Unused   "
            "Method  Dealloc Realloc Allocated by \n"
          << "------ ---------- --------- ---------- --------- --------- "
            "-------- ------- ------- --------------------------------"
            "-------------- \n";

      for (uint i = 0; i < hashSize; ++i) {
        AllocUnit * ptr = hashTable[i];
        while(ptr) {
          // skip external allocations
          if(ptr->srcLine) {
            out << std::setw(6) << ptr->allocNumber
                << " " << std::hex << std::setw(10)
                << ptr->reportedAddress << " "
                << std::setw(9) << ptr->reportedSize << " "
                << std::setw(10) << ptr->actualAddress << " "
                << std::setw(9) << ptr->actualSize << " "
                << std::setw(9) << CalcUnused(ptr) << " "
                << std::left << std::setw(8)
                << allocationTypes[ptr->allocType] << "    "
                << (ptr->breakOnDealloc ? "Y" : "N") << "       "
                << (ptr->breakOnRealloc ? "Y" : "N") << "    "
                << OwnerString(ptr->srcFile, ptr->srcLine, ptr->srcFunc)
                << "\n" << std::dec << std::right;
          }
          ptr = ptr->next;
        }
      }
    }

    void DumpLeakReport(void)
    {
      // Any leaks?
      uint leaks = CalcLeaks();
      if(leaks == 0) {
        vLog << "No memory leaks found." << std::endl;
        return;
      }

      // Header
      time_t t = time(NULL);
      struct tm * tme = localtime(&t);

      vLog << "\n-----------------------------------------------------------"
              "---------------------\n"
           << "                 Memory leak report for: " << asctime(tme)
           << "-----------------------------------------------------------"
              "---------------------\n\n";

      vLog << leaks << " memory leak"  << (leaks == 1 ? "" : "s")
           << " found:\n\n";

      DumpAllocations(vLog);
      vLog.flush();
    }

    void ResetGlobals(void)
    {
      sourceFile = "??";
      sourceLine = 0;
      sourceFunc = "??";
    }

    void DumpAllocUnit(const AllocUnit * allocUnit, const char *prefix)
    {
      vLog << fac(lfMemory)
        << "[I] " << prefix << "Address (reported): "
        << std::setw(10) << std::hex << allocUnit->reportedAddress
        << "\n[I] " << prefix << "Address (actual)  : "
        << std::setw(10) << allocUnit->actualAddress
        << "\n[I] " << prefix << "Size (reported)   : "
        << std::setw(10) << allocUnit->reportedSize
        << " (" << MemorySizeString(allocUnit->reportedSize) << ")"
        << "\n[I] " << prefix << "Size (actual)     : "
        << std::setw(10) << allocUnit->actualAddress
        << std::setw(10) << allocUnit->actualSize
        << " (" << MemorySizeString(allocUnit->actualSize) << ")"
        << "\n[I] " << prefix << "Owner             : "
        << allocUnit->srcFile << allocUnit->srcLine << allocUnit->srcFunc
        << "\n[I] " << prefix << "Allocation type   : "
        << allocationTypes[allocUnit->allocType]
        << "\n[I] " << prefix << "Allocation number : "
        << allocUnit->allocNumber << std::endl;
    }

  }

  bool ValidateAllocUnit(const AllocUnit * allocUnit)
  {
    // Make sure the padding is untouched
    uint32 * pre = reinterpret_cast<uint32*>(allocUnit->actualAddress);
    uint32 * post = reinterpret_cast<uint32*>(static_cast<byte*>(
      allocUnit->actualAddress) + allocUnit->actualSize
      - paddingSize * sizeof(int32));
    bool errorFlag = false;

    for(unsigned i = 0; i < paddingSize; ++i, ++pre, ++post) {
      if(*pre != prefixPattern) {
        vLog << fac(lfMemory)
             << "[!] A memory allocation unit was corrupt because "
                "of an underrun:" << std::endl;
        DumpAllocUnit(allocUnit, "  ");
        errorFlag = true;
      }

      // If you hit this assert, then you should know that this allocation
      // unit has been damaged. Something (possibly the owner?) has underrun
      // the allocation unit (modified a few bytes prior to the start). You
      // can interrogate the variable 'allocUnit' to see statistics and
      // information about this damaged allocation unit.
      BREAK_ASSERT(*pre == prefixPattern);

      if(*post != postfixPattern) {
        vLog << fac(lfMemory)
             << "[!] A memory allocation unit was corrupt because "
                "of an overerrun:" << std::endl;
        DumpAllocUnit(allocUnit, "  ");
        errorFlag = true;
      }

      // If you hit this assert, then you should know that this allocation
      // unit has been damaged. Something (possibly the owner?) has overrun
      // the allocation unit (modified a few bytes after the end). You can
      // interrogate the variable 'allocUnit' to see statistics and
      // information about this damaged allocation unit.
      BREAK_ASSERT(*post == postfixPattern);
    }

    // Return the error status (we invert it, because a return
    // of 'false' means error)
    return !errorFlag;
  }

 /*
  * Init functions
  */
  bool InitializeMemoryManager(const char * buildName)
  {
    // Log this function to be called upon program shut down.
    atexit(ReleaseMemoryManager);

#ifdef LOG_SINGLETONS
    vLog << "Initializing memory manager." << std::endl;
#endif /* LOG_SINGLETONS */

    char tmpstr[40];

    DEBUG_ASSERT(strlen(buildName) < 32);
    strcpy(tmpstr, buildName);
    strcat(tmpstr, "-mem.log");

    vLog.AddOutput(lfMemory, ltFile, tmpstr, cleanupLogOnFirstRun);

    if (cleanupLogOnFirstRun) {
      cleanupLogOnFirstRun = false;

      // Print a header for the log
      vLog << fac(lfMemory)
           << "This file contains a log of all memory operations performed"
        " during the last run.\n\nInterrogate this file to track errors or "
        "to help track down memory-related\nissues. You can do this by tracing "
        "the allocations performed by a specific\nowner or by tracking a "
        "specific address through a series of allocations\nand reallocations.\n"
        "\nThere is a lot of useful information here which, when used "
        "creatively, can be\nextremely helpful.\n\nNote that the following \n"
        "guides are used throughout this file:\n\n";

      vLog << "   [!] - Error\n"
           << "   [+] - Allocation\n"
           << "   [~] - Reallocation\n"
           << "   [-] - Deallocation'n"
           << "   [I] - Generic information\n"
           << "   [F] - Failure induced for the purpose of "
              "stress-testing your application\n"
           << "   [D] - Information used for debugging \n"
              "this memory manager\n\n";

      vLog << "...so, to find all errors in the file, search for \"[!]\"";

      vLog << "\n--------------------------------------------------"
              "------------------------------" << std::endl;
    }
    return true;
  }

  void ReleaseMemoryManager(void)
  {
#ifdef LOG_SINGLETONS
    vLog << "Releasing memory manager." << std::endl;
#endif /* LOG_SINGLETONS */

    DumpLeakReport();

    // We can finally free up our own memory allocations
    if(reservoirBuffer) {
      for(uint i = 0; i < reservoirBufferSize; ++i) {
        free(reservoirBuffer[i]);
      }
      free(reservoirBuffer);
      reservoirBuffer = 0;
      reservoirBufferSize = 0;
      reservoir = NULL;
    }
    // deinitialized
    released = true;
  }

 /*
  *  Config functions
  */
  void SetAlwaysValidateAll(bool st)
  {
    // Force a validation of all allocation units each time
    // we enter this software
    alwaysValidateAll = st;
  }

  void SetAlwaysLogAll(bool st)
  {
    // Force a log of every allocation & deallocation into memory.log
    alwaysLogAll = st;
  }

  void SetAlwaysWipeAll(bool st)
  {
    // Force this software to always wipe memory with a pattern when
    // it is being allocated/dallocated
    alwaysWipeAll = st;
  }

  void SetRandomWipe(bool st)
  {
    // Force this software to use a random pattern when wiping memory
    // -- good for stress testing
    randomWipe = true;
  }

  void SetBreakOnRealloc(void * address, bool st)
  {
    // Locate the existing allocation unit
    AllocUnit * au = FindAllocUnit(address);

    // If you hit this assert, you tried to set a breakpoint on reallocation
    // for an address that doesn't exist. Interrogate the stack frame or
    // the variable 'au' to see which allocation this is.
    BREAK_ASSERT(au != NULL);

    // If you hit this assert, you tried to set a breakpoint on reallocation
    // for an address that wasn't allocated in a way that is compatible
    // with reallocation.
    BREAK_ASSERT(au->allocType == atMalloc ||
                 au->allocType == atCalloc ||
                 au->allocType == atRealloc);

    au->breakOnRealloc = st;
  }

  void BreakOnDealloc(void * address, bool st)
  {
    // Locate the existing allocation unit
    AllocUnit * au = FindAllocUnit(address);

    // If you hit this assert, you tried to set a breakpoint on deallocation
    // for an address that doesn't exist. Interrogate the stack frame or the
    // variable 'au' to see which allocation this is.
    BREAK_ASSERT(au != NULL);

    au->breakOnDealloc = st;
  }

  void BreakOnAllocation(unsigned int count)
  {
    breakOnAllocationCount = count;
  }

 /*
  *  Used by macros
  */
  void SetOwner(const char * file, unsigned line, const char * func)
  {
    if(sourceLine && alwaysLogAll) {
      vLog << fac(lfMemory)
           <<  "[I] NOTE! Possible destructor chain: previous owner is "
           << OwnerString(sourceFile, sourceLine, sourceFunc) << std::endl;
    }

    // Okay... save this stuff off so we can keep track of the caller
    sourceFile = file;
    sourceLine = line;
    sourceFunc = func;
  }

 /*
  *  Allocate memory and track it
  */
  void * Allocator(const char * file, unsigned line,
    const char * func, AllocType type, size_t size)
  {
    try {
      // requesting memory at the program cleanup?
      BREAK_ASSERT(!released);

      // Increase our allocation count
      if(line)
        ++currentAllocationCount;

      // Log the request
      if(line && alwaysLogAll) {
        vLog << fac(lfMemory)
             << "[+] " << std::setw(5)
             << currentAllocationCount << " " << std::setw(8)
             << allocationTypes[type]
             << " of size " << std::hex << std::setw(8)
             << size << std::dec << "("
             << std::setw(8) << size << ") by "
             << OwnerString(file, line, func) << std::endl;
      }

      // If you hit this assert, you requested a breakpoint on
      // a specific allocation count
      BREAK_ASSERT(!line || currentAllocationCount != breakOnAllocationCount);

      // If necessary, grow the reservoir of unused allocation units
      if(!reservoir) {
        // Allocate 256 reservoir elements
        reservoir = (AllocUnit *) malloc(sizeof(AllocUnit) * 256);

        // If you hit this assert, then the memory manager failed to allocate
        // internal memory for tracking the allocations
        BREAK_ASSERT(reservoir != NULL);

        // Danger Will Robinson!
        if(reservoir == NULL)
          throw "Unable to allocate RAM for internal memory tracking data";

        // Build a linked-list of the elements in our reservoir
        memset(reservoir, 0, sizeof(AllocUnit) * 256);
        for (unsigned int i = 0; i < 256 - 1; ++i) {
          reservoir[i].next = &reservoir[i + 1];
        }

        // Add this address to our reservoirBuffer so we can free it later
        AllocUnit ** temp = (AllocUnit **) realloc(reservoirBuffer,
          (reservoirBufferSize + 1) * sizeof(AllocUnit *));

        BREAK_ASSERT(temp);
        if(temp) {
          reservoirBuffer = temp;
          reservoirBuffer[reservoirBufferSize++] = reservoir;
        }
      }

      // Logical flow says this should never happen...
      BREAK_ASSERT(reservoir != NULL);

      // Grab a new allocaton unit from the front of the reservoir
      AllocUnit * au = reservoir;
      reservoir = au->next;

      // Populate it with some real data
      memset(au, 0, sizeof(AllocUnit));
      au->actualSize = CalcActualSize(size);
#ifdef RANDOM_FAILURE
      double a = rand();
      double b = RAND_MAX / 100.0 * RANDOM_FAILURE;
      if (a > b) {
        au->actualAddress = malloc(au->actualSize);
      } else {
        vLog << fac(lfMemory) << "[F] Random faiure" << std::endl;
        au->actualAddress = NULL;
      }
#else /* RANDOM_FAILURE */
      au->actualAddress = malloc(au->actualSize);
#endif /* RANDOM_FAILURE */
      au->reportedSize = size;
      au->reportedAddress = GetReportedAddress(au->actualAddress);
      au->allocType = type;
      au->srcLine = line;
      au->allocNumber = currentAllocationCount;

      if(file)
        strncpy(au->srcFile, SourceFileStripper(file),
          sizeof(au->srcFile) - 1);
      else
        strcpy(au->srcFile, "??");

      if(func)
        strncpy(au->srcFunc, func, sizeof(au->srcFunc) - 1);
      else
        strcpy(au->srcFunc, "??");

      // We don't want to assert with random failures, because we want
      //  the application to deal with them.
#ifndef RANDOM_FAILURE
      // If you hit this assert, then the requested allocation simply failed
      // (you're out of memory.) Interrogate the variable 'au' or the stack
      // frame to see what you were trying to do.
      BREAK_ASSERT(au->actualAddress != NULL);
#endif /* RANDOM_FAILURE */

      if (au->actualAddress == NULL) {
        throw "Request for allocation failed. Out of memory.";
      }

      // If you hit this assert, then this allocation was made from a source
      // that isn't setup to use this memory tracking software, use the stack
      // frame to locate the source and include our H file.
      BREAK_ASSERT(type != atUnknown);

      // Insert the new allocation into the hash table
      unsigned hashIndex = (reinterpret_cast<uptr>(
        au->reportedAddress) >> 4) & (hashSize - 1);
      if(hashTable[hashIndex])
        hashTable[hashIndex]->prev = au;
      au->next = hashTable[hashIndex];
      au->prev = NULL;
      hashTable[hashIndex] = au;

      // Account for the new allocation unit in our stats
      stats.totalReportedMemory += static_cast<unsigned int>(au->reportedSize);
      stats.totalActualMemory += static_cast<unsigned int>(au->actualSize);
      ++stats.totalAllocUnitCount;

      if(stats.totalReportedMemory > stats.peakReportedMemory)
        stats.peakReportedMemory = stats.totalReportedMemory;
      if(stats.totalActualMemory > stats.peakActualMemory)
        stats.peakActualMemory = stats.totalActualMemory;
      if(stats.totalAllocUnitCount > stats.peakAllocUnitCount)
        stats.peakAllocUnitCount = stats.totalAllocUnitCount;

      stats.accumReportedMemory += static_cast<unsigned int>(au->reportedSize);
      stats.accumActualMemory += static_cast<unsigned int>(au->actualSize);
      ++stats.accumAllocUnitCount;

      // Prepare the allocation unit for use (wipe it with recognizable garbage)
      WipeWithPattern(au, unusedPattern);

      // calloc() expects the reported memory
      // address range to be filled with 0's
      if(type == atCalloc) {
        memset(au->reportedAddress, 0, au->reportedSize);
      }

      // Validate every single allocated unit in memory
      if(alwaysValidateAll)
        ValidateAllAllocUnits();

      // Log the result
      if(line && alwaysLogAll) {
        vLog << fac(lfMemory) << "[+] ---->             addr "
             << std::hex << std::setw(8)
             << au->reportedAddress << std::dec << std::endl;
      }

      // Resetting the globals insures that if at some later time, somebody
      // calls our memory manager from an unknown source (i.e. they didn't
      // include our H file) then we won't think it was the last allocation.
      ResetGlobals();

      // Return the (reported) address of the new allocation unit
      return au->reportedAddress;
    } catch(const char *err) {
      // Deal with the errors
      vLog << fac(lfMemory) << "[!] " << err << std::endl;

      ResetGlobals();
      return NULL;
    }
  }

 /*
  *  Reallocate memory and track it
  */
  void * Reallocator(const char * file, unsigned line,
    const char * func, AllocType type, size_t size, void * address)
  {
    try {
      // Calling realloc with a NULL should force same operations as a malloc
      if (!address) {
        void * res = Allocator(file, line, func, type, size ? size : 1);
        return res;
      }

      if(size == 0) {
        Deallocator(file, line, func, atRealloc, address);
        return NULL;
      }

      // requesting memory at the program cleanup?
      BREAK_ASSERT(!released);

      // Increase our allocation count
      if(line)
        ++currentAllocationCount;

      // If you hit this assert, you requested a breakpoint
      // on a specific allocation count
      BREAK_ASSERT(currentAllocationCount != breakOnAllocationCount);

      // Log the request
      if (line && alwaysLogAll) {
        vLog << fac(lfMemory)
             << "[+] " << std::setw(5)
             << currentAllocationCount << " " << std::setw(8)
             << allocationTypes[type] << " of size "
             << std::hex << std::setw(8) << size << std::dec << "("
             << std::setw(8) << size << ") by "
             << OwnerString(file, line, func) << std::endl;
      }

      // Locate the existing allocation unit
      AllocUnit * au = FindAllocUnit(address);

      // If you hit this assert, you tried to reallocate RAM that
      // wasn't allocated by this memory manager.
      BREAK_ASSERT(au != NULL);
      if(au == NULL)
        throw "Request to reallocate RAM that was never allocated";

      // If you hit this assert, then the allocation unit that is about to
      // be reallocated is damaged. But you probably already know that from
      // a previous assert you should have seen in validateAllocUnit() :)
      BREAK_ASSERT(ValidateAllocUnit(au));

      // If you hit this assert, then this reallocation was made from
      // a source that isn't setup to use this memory tracking software,
      // use the stack frame to locate the source and include our H file.
      BREAK_ASSERT(type != atUnknown);

      // If you hit this assert, you were trying to reallocate RAM that
      // was not allocated in a way that is compatible with
      // realloc. In other words, you have a allocation/reallocation mismatch.
      BREAK_ASSERT(au->allocType == atMalloc ||
                   au->allocType == atCalloc ||
                   au->allocType == atRealloc);

      // If you hit this assert, then the "break on realloc" flag for this
      // allocation unit is set (and will continue to be set until you
      // specifically shut it off. Interrogate the 'au' variable to
      // determine information about this allocation unit.
      BREAK_ASSERT(au->breakOnRealloc == false);

      // Keep track of the original size
      unsigned origReportedSize = static_cast<unsigned int>(au->reportedSize);

      if(line && alwaysLogAll)
        vLog << fac(lfMemory) << "[+] ---->             addr "
             << std::hex << std::setw(8)
             << origReportedSize << std::dec << "(" << std::setw(8)
             << origReportedSize << ")" << std::endl;

      // Do the reallocation
      void * oldReportedAddress = address;
      size_t newActualSize = CalcActualSize(size);
      void * newActualAddress = NULL;
#ifdef RANDOM_FAILURE
      double a = rand();
      double b = RAND_MAX / 100.0 * RANDOM_FAILURE;
      if (a > b) {
        newActualAddress = realloc(au->actualAddress, newActualSize);
      } else {
        vLog << fac(lfMemory) << "[F] Random faiure" << std::endl;
      }
#else /* RANDOM_FAILURE */
      newActualAddress = realloc(au->actualAddress, newActualSize);
#endif /* RANDOM_FAILURE */

      // We don't want to assert with random failures, because we want
      // the application to deal with them.

#ifndef RANDOM_FAILURE
      // If you hit this assert, then the requested allocation simply
      // failed (you're out of memory) Interrogate the variable 'au' to see
      // the original allocation. You can also query 'newActualSize' to see
      // the amount of memory trying to be allocated. Finally, you can query
      // 'reportedSize' to see how much memory was requested by the caller.
      BREAK_ASSERT(newActualAddress);
#endif /* RANDOM_FAILURE */

      if(!newActualAddress)
        throw "Request for reallocation failed. Out of memory.";

      // Remove this allocation from our stats (we'll add the
      // new reallocation again later)
      stats.totalReportedMemory -= static_cast<unsigned int>(au->reportedSize);
      stats.totalActualMemory -= static_cast<unsigned int>(au->actualSize);

      // Update the allocation with the new information

      au->actualSize = newActualSize;
      au->actualAddress = newActualAddress;
      au->reportedSize = CalcReportedSize(newActualSize);
      au->reportedAddress = GetReportedAddress(newActualAddress);
      au->allocType = type;
      au->srcLine = line;
      au->allocNumber = currentAllocationCount;

      if(file)
        strncpy(au->srcFile, SourceFileStripper(file), sizeof(au->srcFile) - 1);
      else
        strcpy(au->srcFile, "??");

      if(func)
        strncpy(au->srcFunc, func, sizeof(au->srcFunc) - 1);
      else
        strcpy(au->srcFunc, "??");

      // The reallocation may cause the address to change, so we
      // should relocate our allocation unit within the hash table
      if(oldReportedAddress != au->reportedAddress) {
        // Remove this allocation unit from the hash table
        unsigned hashIndex = (reinterpret_cast<uptr>(
          oldReportedAddress) >> 4) & (hashSize - 1);
        if(hashTable[hashIndex] == au) {
          hashTable[hashIndex] = hashTable[hashIndex]->next;
        } else {
          if(au->prev)
            au->prev->next = au->next;
          if(au->next)
            au->next->prev = au->prev;
        }

        // Re-insert it back into the hash table
        hashIndex = (reinterpret_cast<uptr>(
          au->reportedAddress) >> 4) & (hashSize - 1);
        if(hashTable[hashIndex])
          hashTable[hashIndex]->prev = au;
        au->next = hashTable[hashIndex];
        au->prev = NULL;
        hashTable[hashIndex] = au;
      }

      // Account for the new allocatin unit in our stats
      stats.totalReportedMemory += static_cast<unsigned int>(au->reportedSize);
      stats.totalActualMemory += static_cast<unsigned int>(au->actualSize);

      if (stats.totalReportedMemory > stats.peakReportedMemory)
        stats.peakReportedMemory = stats.totalReportedMemory;
      if(stats.totalActualMemory > stats.peakActualMemory)
        stats.peakActualMemory = stats.totalActualMemory;

      int deltaReportedSize = static_cast<int>(
        size - origReportedSize);

      if(deltaReportedSize > 0) {
        stats.accumReportedMemory += deltaReportedSize;
        stats.accumActualMemory += deltaReportedSize;
      }

      // Prepare the allocation unit for use (wipe it with recognizable garbage)
      WipeWithPattern(au, unusedPattern, origReportedSize);

      // If you hit this assert, then something went wrong, because
      // the allocation unit was properly validated PRIOR to the reallocation.
      // This should not happen.
      BREAK_ASSERT(ValidateAllocUnit(au));

      // Validate every single allocated unit in memory
      if (alwaysValidateAll)
        ValidateAllAllocUnits();

      // Log the result
      if(line && alwaysLogAll) {
        vLog << fac(lfMemory) << "[+] ---->             addr "
             << std::hex << std::setw(8)
             << reinterpret_cast<uptr>(au->reportedAddress)
             << std::dec << std::endl;
      }

      // Resetting the globals insures that if at some later time, somebody
      // calls our memory manager from an unknown source (i.e. they didn't
      // include our H file) then we won't think it was the last allocation.
      ResetGlobals();

      // Return the (reported) address of the new allocation unit
      return au->reportedAddress;
    } catch(const char *err) {
      // Deal with the errors
      vLog << fac(lfMemory) << "[!] " << err << std::endl;

      ResetGlobals();
      return NULL;
    }
  }

 /*
  *  Deallocate memory and track it
  */
  void Deallocator(const char * file, unsigned line,
    const char * func, AllocType type, const void * address)
  {
    try {
      // determine the allocator, since stack may get confused
      AllocUnit * au = NULL;
      if(address)
        au = FindAllocUnit(address);

      // it's an external allocation
      if(!line && !au)
          return;

      // Log the request
      if(au && au->srcLine && alwaysLogAll) {
        vLog << fac(lfMemory)
             << "[-] ----- " << std::setw(8)
             << allocationTypes[type] << " of addr "
             << std::hex << std::setw(8) << address
             << "           by " << std::dec
             << OwnerString(file, line, func)
             << std::endl;
      }

      // We should only ever get here with a null pointer if they try to do
      // so with a call to free() (delete[] and delete will both bail before
      // they get here.) So, since ANSI allows free(NULL), we'll not bother
      // trying to actually free the allocated memory or track it any further.
      if(address) {
        // If you hit this assert, you tried to deallocate RAM that
        // wasn't allocated by this memory manager.
        // HACK: Wave somehow manages to avoid our overloaded new operators
        BREAK_ASSERT(au != NULL || line == 0);
        if(au == NULL)
          throw "Request to deallocate RAM that was never allocated";

        // If you hit this assert, then the allocation unit that is about to
        // be deallocated is damaged. But you probably already know that from
        // a previous assert you should have seen in validateAllocUnit() :)
        BREAK_ASSERT(ValidateAllocUnit(au));

        // If you hit this assert, then this deallocation was made from a
        // source that isn't setup to use this memory tracking software, use
        // the stack frame to locate the source and include our H file.
        BREAK_ASSERT(type != atUnknown);

        // If you hit this assert, you were trying to deallocate RAM that was
        // not allocated in a way that is compatible with the deallocation
        // method requested. In other words, you have
        // a allocation/deallocation mismatch.
        BREAK_ASSERT((type == atDelete && atNew) ||
          (type == atDeleteArray && au->allocType == atNewArray) ||
          (type == atFree && au->allocType == atMalloc) ||
          (type == atFree && au->allocType == atCalloc) ||
          (type == atFree && au->allocType == atRealloc) ||
          (type == atRealloc && au->allocType == atMalloc) ||
          (type == atRealloc && au->allocType == atCalloc) ||
          (type == atRealloc && au->allocType == atRealloc) ||
          (type == atUnknown));

        // If you hit this assert, then the "break on dealloc" flag for this
        // allocation unit is set. Interrogate the 'au' variable to determine
        // information about this allocation unit.
        BREAK_ASSERT(au->breakOnDealloc == false);

        // Wipe the deallocated RAM with a new pattern. This doen't actually
        // do us much good in debug mode under WIN32, because Microsoft's
        // memory debugging & tracking utilities will wipe it right after
        // we do. Oh well.
        WipeWithPattern(au, releasedPattern);

        // Do the deallocation
        free(au->actualAddress);

        // Remove this allocation unit from the hash table
        unsigned hashIndex = (reinterpret_cast<uptr>(
          au->reportedAddress) >> 4) & (hashSize - 1);
        if(hashTable[hashIndex] == au) {
          hashTable[hashIndex] = au->next;
        } else {
          if (au->prev) au->prev->next = au->next;
          if (au->next) au->next->prev = au->prev;
        }

        // Remove this allocation from our stats
        stats.totalReportedMemory
          -= static_cast<unsigned int>(au->reportedSize);
        stats.totalActualMemory
          -= static_cast<unsigned int>(au->actualSize);
        stats.totalAllocUnitCount--;

        // Add this allocation unit to the front of our
        // reservoir of unused allocation units
        memset(au, 0, sizeof(AllocUnit));
        au->next = reservoir;
        reservoir = au;
      }

      // Resetting the globals insures that if at some later time, somebody
      // calls our memory manager from an unknown source (i.e. they didn't
      // include our H file) then we won't think it was the last allocation.
      ResetGlobals();

      // Validate every single allocated unit in memory
      if (alwaysValidateAll)
        ValidateAllAllocUnits();
    } catch(const char *err) {
      // Deal with errors
      vLog << fac(lfMemory) << "[!] " << err << std::endl;
      ResetGlobals();
    }
  }

 /*
  *  The following utilitarian allow you to become proactive in tracking your
  *  own memory, or help you narrow in on those tough bugs.
  */
  bool ValidateAddress(const void * address)
  {
    // Just see if the address exists in our allocation routines
    return FindAllocUnit(address) != NULL;
  }

  bool ValidateAllAllocUnits(void)
  {
    // Just go through each allocation unit in the hash table and 
    // count the ones that have errors
    unsigned errors = 0;
    unsigned allocCount = 0;

    for (unsigned i = 0; i < hashSize; ++i) {
      AllocUnit * ptr = hashTable[i];
      while(ptr) {
        ++allocCount;
        if(!ValidateAllocUnit(ptr))
          ++errors;
        ptr = ptr->next;
      }
    }

    // Test for hash-table correctness
    if(allocCount != stats.totalAllocUnitCount) {
      vLog << fac(lfMemory)
           << "[!] Memory tracking hash table corrupt!" << std::endl;
      ++errors;
    }

    // If you hit this assert, then the internal memory (hash table) used by
    // this memory tracking software is damaged! The best way to track this
    // down is to use the alwaysLogAll flag in conjunction with STRESS_TEST
    // macro to narrow in on the offending code. After running the application
    // with these settings (and hitting this assert again), interrogate the
    // memory.log file to find the previous successful operation. The
    // corruption will have occurred between that point and this assertion.
    BREAK_ASSERT(allocCount == stats.totalAllocUnitCount);

    // If you hit this assert, then you've probably already been notified that
    // there was a problem with a allocation unit in a prior call to
    // validateAllocUnit(), but this assert is here just to make sure you
    // know about it. :)
    BREAK_ASSERT(errors == 0);

    // Log any errors
    if(errors)
      vLog << fac(lfMemory)
           << "[!] While validating all allocation units, " << errors
           << " allocation unit(s) were found to have problems" << std::endl;

    // Return the error status
    return errors != 0;
  }

 /*
  *  Unused RAM calculation routines. Use these to determine how
  *  much of your RAM is unused (in bytes)
  */
  unsigned CalcAllUnused(void)
  {
    // Just go through each allocation unit in the hash
    // table and count the unused RAM

    unsigned total = 0;
    for (unsigned i = 0; i < hashSize; ++i) {
      AllocUnit * ptr = hashTable[i];
      while(ptr) {
        total += CalcUnused(ptr);
        ptr = ptr->next;
      }
    }
    return total;
  }

 /*
  *  The following functions are for logging and statistics reporting.
  */
  void DumpLogReport(std::ostream & out)
  {
    time_t t = time(NULL);
    struct tm * tme = localtime(&t);

    // logging into the default facility on purpose
    out << "\n-----------------------------------------------------------"
           "---------------------\n"
        << "                 Memory leak report for: " << asctime(tme)
        << "-----------------------------------------------------------"
           "---------------------\n\n";

    // Report summary
    out << "                     T O T A L  M E M O R Y  U S A G E\n"
        << "-----------------------------------------------------------"
            "---------------------\n"
        << "              Allocation unit count: "
        << std::setw(10) << InsertCommas(stats.totalAllocUnitCount);
    out << "\n            Reported to application: "
        << MemorySizeString(stats.totalReportedMemory);
    out << "\n         Actual total memory in use: "
        << MemorySizeString(stats.totalActualMemory);
    out << "\n           Memory tracking overhead: "
        << MemorySizeString(stats.totalActualMemory
          - stats.totalReportedMemory) << "\n\n";

    out << "                      P E A K  M E M O R Y  U S A G E\n"
        << "-----------------------------------------------------------"
            "---------------------\n"
        << "              Allocation unit count: "
        << std::setw(10) << InsertCommas(stats.peakAllocUnitCount);
    out << "\n            Reported to application: "
        << MemorySizeString(stats.peakReportedMemory);
    out << "\n                             Actual: "
        << MemorySizeString(stats.peakActualMemory);
    out << "\n           Memory tracking overhead: "
        << MemorySizeString(stats.peakActualMemory
          - stats.peakReportedMemory) << "\n\n";

    out << "                  A C C U M U L A T E D  M E M O R Y  U S A G E\n"
        << "-----------------------------------------------------------"
            "---------------------\n"
        << "              Allocation unit count: "
        << std::setw(10) << InsertCommas(stats.accumAllocUnitCount);
    out << "\n            Reported to application: "
        << MemorySizeString(stats.accumReportedMemory);
    out << "\n                             Actual: "
        << MemorySizeString(stats.accumActualMemory) << "\n\n";

    uint unused = CalcAllUnused();
    float unused_perc = (float)unused / stats.totalReportedMemory;

    out << "                          U N U S E D  M E M O R Y\n"
        << "-----------------------------------------------------------"
            "---------------------\n"
        << "  Percentage of allocated memory actually used: "
        << std::setw(10) << std::setprecision(2)
        << (1.0f - unused_perc) * 100.0f << " %\n"
        << "       Percentage of allocated memory not used: "
        << std::setw(10) << std::setprecision(2)
        << unused_perc * 100.0f << " %\n"
        << "        Memory allocated but not actually used: "
        << MemorySizeString(unused) << "\n\n";
  }

  MemStats GetMemoryStatistics(void)
  {
    return stats;
  }

}

/*
 *  Global new/new[] - These are the standard new/new[] operators. They are
 *  merely interface functions that operate like normal new/new[], but use our
 *  memory tracking routines.
 */
void * operator new (size_t size) throw(std::bad_alloc)
{
  // Save these off...
  const char * file = tre::sourceFile;
  unsigned line = tre::sourceLine;
  const char * func = tre::sourceFunc;

  // ANSI says: allocation requests of 0 bytes will still return a valid value
  if(size == 0)
    size = 1;

  // ANSI says: loop continuously because the error handler
  // could possibly free up some memory

  for(;;) {
    // Try the allocation
    void * ptr = tre::Allocator(file, line, func, tre::atNew, size);
    if(ptr) {
      return ptr;
    }

    // There isn't a way to determine the new handler, except through
    // setting it. So we'll just set it to NULL, then set it back again.
    std::new_handler nh = std::set_new_handler(0);
    std::set_new_handler(nh);

    // If there is an error handler, call it
    if(nh) {
      (*nh)();

    // Otherwise, throw the exception
    } else {
      throw std::bad_alloc();
    }
  }
}

void * operator new [] (size_t size) throw(std::bad_alloc)
{
  // Save these off...
  const char * file = tre::sourceFile;
  unsigned line = tre::sourceLine;
  const char * func = tre::sourceFunc;

  // The ANSI standard says that allocation requests of 0 bytes will still
  // return a valid value
  if(size == 0)
    size = 1;

  // ANSI says: loop continuously because the error handler could
  // possibly free up some memory
  for(;;) {
    // Try the allocation
    void * ptr = tre::Allocator(file, line, func, tre::atNewArray, size);
    if(ptr) {
      return ptr;
    }

    // There isn't a way to determine the new handler, except through setting
    // it. So we'll just set it to NULL, then set it back again.

    std::new_handler nh = std::set_new_handler(0);
    std::set_new_handler(nh);

    // If there is an error handler, call it
    if(nh) {
      (*nh)();
    // Otherwise, throw the exception
    } else {
      throw std::bad_alloc();
    }
  }
}

/*
 *  Other global new/new[] - These are the standard new/new[] operators as
 *  used by Microsoft's memory tracker. We don't want them interfering with
 *  our memory tracking efforts. Like the previous versions, these are merely
 *  interface functions that operate like normal new/new[], but use
 *  our memory tracking routines.
 */
void * operator new(size_t size,
  const char * file, int line) throw(std::bad_alloc)
{
  // The ANSI standard says that allocation requests of 0 bytes will
  // still return a valid value
  if(size == 0)
    size = 1;

  // ANSI says: loop continuously because the error handler could
  // possibly free up some memory
  for(;;) {
    // Try the allocation
    void * ptr = tre::Allocator(file, line, "??", tre::atNew, size);
    if(ptr) {
      return ptr;
    }

    // There isn't a way to determine the new handler, except through setting
    // it. So we'll just set it to NULL, then set it back again.
    std::new_handler nh = std::set_new_handler(0);
    std::set_new_handler(nh);

    // If there is an error handler, call it
    if(nh) {
      (*nh)();
    // Otherwise, throw the exception
    } else {
      throw std::bad_alloc();
    }
  }
}

void * operator new [] (size_t size,
  const char * file, int line) throw(std::bad_alloc)
{
  // The ANSI standard says that allocation requests of 0 bytes will
  // still return a valid value
  if(size == 0)
    size = 1;

  // ANSI says: loop continuously because the error handler could
  // possibly free up some memory
  for(;;) {
    // Try the allocation
    void * ptr = tre::Allocator(file, line, "??", tre::atNewArray, size);
    if(ptr) {
      return ptr;
    }

    // There isn't a way to determine the new handler, except through
    // setting it. So we'll just set it to NULL, then set it back again.
    std::new_handler nh = std::set_new_handler(0);
    std::set_new_handler(nh);

    // If there is an error handler, call it
    if(nh) {
      (*nh)();

    // Otherwise, throw the exception
    } else {
      throw std::bad_alloc();
    }
  }
}

/*
 *  Global delete/delete[] - These are the standard delete/delete[] operators.
 *  They are merely interface functions that operate like normal delete/delete[],
 *  but use our memory tracking routines.
 */
void operator delete(void * address) throw()
{
  // ANSI says: delete & delete[] allow NULL pointers (they do nothing)
  if(address)
    tre::Deallocator(tre::sourceFile, tre::sourceLine,
      tre::sourceFunc, tre::atDelete, address);
  else if(tre::alwaysLogAll)
    tre::vLog << tre::fac(tre::lfMemory) << "[-] ----- "
              << tre::allocationTypes[tre::atDelete]
              << " of NULL                      by " << tre::OwnerString(
                tre::sourceFile, tre::sourceLine, tre::sourceFunc) << std::endl;

  // Resetting the globals insures that if at some later time, somebody
  // calls our memory manager from an unknown source (i.e. they didn't include
  // our H file) then we won't think it was the last allocation.
  tre::ResetGlobals();
}

void operator delete [] (void * address) throw()
{
  // ANSI says: delete & delete[] allow NULL pointers (they do nothing)
  if(address)
    tre::Deallocator(tre::sourceFile, tre::sourceLine, tre::sourceFunc,
      tre::atDeleteArray, address);
  else if(tre::alwaysLogAll)
    tre::vLog << tre::fac(tre::lfMemory) << "[-] ----- "
              << tre::allocationTypes[tre::atDeleteArray]
              << " of NULL                      by "
              << tre::OwnerString(tre::sourceFile,
                  tre::sourceLine, tre::sourceFunc);

  // Resetting the globals insures that if at some later time, somebody
  // calls our memory manager from an unknown source (i.e. they didn't include
  // our H file) then we won't think it was the last allocation.
  tre::ResetGlobals();
}

// These routines should never get called, unless an error occures during the
// allocation process. These need to be defined to make Visual C++ happy
// If there was an allocation problem these method would be called
// automatically by  the operating system.  C/C++ Users Journal (Vol. 19
// No. 4 -> April 2001 pg. 60) has an excellent explanation of what is going
// on here.
/// Make compiler happy!
void operator delete(void * address, const char *, int) throw()
{
  free(address);
}

/// Make compiler happy!
void operator delete[](void * address, const char *, int) throw()
{
  free(address);
}

#endif /* MEM_MANAGER_ON */