Engine/source/platform/platformMemory.cpp

   1 //-----------------------------------------------------------------------------
   2 // Copyright (c) 2012 GarageGames, LLC
   3 //
   4 // Permission is hereby granted, free of charge, to any person obtaining a copy
   5 // of this software and associated documentation files (the "Software"), to
   6 // deal in the Software without restriction, including without limitation the
   7 // rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
   8 // sell copies of the Software, and to permit persons to whom the Software is
   9 // furnished to do so, subject to the following conditions:
  10 //
  11 // The above copyright notice and this permission notice shall be included in
  12 // all copies or substantial portions of the Software.
  13 //
  14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  19 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  20 // IN THE SOFTWARE.
  21 //-----------------------------------------------------------------------------
  22
  23 #include "platform/platformMemory.h"
  24 #include "console/dynamicTypes.h"
  25 #include "console/engineAPI.h"
  26 #include "core/stream/fileStream.h"
  27 #include "core/strings/stringFunctions.h"
  28 #include "console/console.h"
  29 #include "platform/profiler.h"
  30 #include "platform/threads/mutex.h"
  31 #include "core/module.h"
  32
  33 // If profile paths are enabled, disable profiling of the
  34 // memory manager as that would cause a cyclic dependency
  35 // through the string table's allocation stuff used by the
  36 // profiler (talk about a long sentence...)
  37
  38 #ifdef TORQUE_ENABLE_PROFILE_PATH
  39 #  undef PROFILE_START
  40 #  undef PROFILE_END
  41 #  undef PROFILE_SCOPE
  42 #  define PROFILE_START( x )
  43 #  define PROFILE_END()
  44 #  define PROFILE_SCOPE( x )
  45 #endif
  46
  47 #ifdef TORQUE_MULTITHREAD
  48 void * gMemMutex = NULL;
  49 #endif
  50
  51 //-------------------------------------- Make sure we don't have the define set
  52 #ifdef new
  53 #undef new
  54 #endif
  55
  56 enum MemConstants : U32
  57 {
  58    Allocated            = BIT(0),
  59    Array                = BIT(1),
  60    DebugFlag            = BIT(2),
  61    Reallocated          = BIT(3),      /// This flag is set if the memory has been allocated, then 'realloc' is called
  62    GlobalFlag           = BIT(4),
  63    StaticFlag           = BIT(5),
  64    AllocatedGuard       = 0xCEDEFEDE,
  65    FreeGuard            = 0x5555FFFF,
  66    MaxAllocationAmount  = 0xFFFFFFFF,
  67    TreeNodeAllocCount   = 2048,
  68 };
  69
  70 inline U32 flagToBit( Memory::EFlag flag )
  71 {
  72    using namespace Memory;
  73
  74    U32 bit = 0;
  75    switch( flag )
  76    {
  77    case FLAG_Debug:  bit = DebugFlag; break;
  78    case FLAG_Global: bit = GlobalFlag; break;
  79    case FLAG_Static: bit = StaticFlag; break;
  80    }
  81    return bit;
  82 }
  83
  84 enum RedBlackTokens {
  85    Red = 0,
  86    Black = 1
  87 };
  88
  89 static U32 MinPageSize = 8 * 1024 * 1024;
  90
  91 #if !defined(TORQUE_SHIPPING) && defined(TORQUE_DEBUG_GUARD)
  92 #define LOG_PAGE_ALLOCS
  93 #endif
  94
  95 U32 gNewNewTotal = 0;
  96 U32 gImageAlloc = 0;
  97
  98 //---------------------------------------------------------------------------
  99
 100 namespace Memory
 101 {
 102
 103 ConsoleFunctionGroupBegin( Memory, "Memory manager utility functions.");
 104
 105 struct FreeHeader;
 106
 107 /// Red/Black Tree Node - used to store queues of free blocks
 108 struct TreeNode
 109 {
 110    U32 size;
 111    TreeNode *parent;
 112    TreeNode *left;
 113    TreeNode *right;
 114    U32 color;
 115    FreeHeader *queueHead;
 116    FreeHeader *queueTail;
 117    U32 unused;
 118 };
 119
 120 struct Header
 121 {
 122    // doubly linked list of allocated and free blocks -
 123    // contiguous in memory.
 124 #ifdef TORQUE_DEBUG_GUARD
 125    U32 preguard[4];
 126 #endif
 127    Header *next;
 128    Header *prev;
 129    dsize_t size;
 130    U32 flags;
 131 #ifdef TORQUE_DEBUG_GUARD
 132    #ifdef TORQUE_ENABLE_PROFILE_PATH
 133    U32 unused[5];
 134    #else
 135    U32 unused[4];
 136    #endif
 137    U32 postguard[4];
 138 #endif
 139 };
 140
 141 struct AllocatedHeader
 142 {
 143 #ifdef TORQUE_DEBUG_GUARD
 144    U32 preguard[4];
 145 #endif
 146    Header *next;
 147    Header *prev;
 148    dsize_t size;
 149    U32 flags;
 150
 151 #ifdef TORQUE_DEBUG_GUARD
 152    // an allocated header will only have this stuff if TORQUE_DEBUG_GUARD
 153    U32 line;
 154    U32 allocNum;
 155    const char *fileName;
 156    #ifdef TORQUE_ENABLE_PROFILE_PATH
 157       const char * profilePath;
 158    #endif
 159    U32 realSize;
 160    U32 postguard[4];
 161 #endif
 162
 163    void* getUserPtr()
 164    {
 165       return ( this + 1 );
 166    }
 167 };
 168
 169 struct FreeHeader
 170 {
 171 #ifdef TORQUE_DEBUG_GUARD
 172    U32 preguard[4];
 173 #endif
 174    Header *next;
 175    Header *prev;
 176    dsize_t size;
 177    U32 flags;
 178
 179 // since a free header has at least one cache line (16 bytes)
 180 // we can tag some more stuff on:
 181
 182    FreeHeader *nextQueue;  // of the same size
 183    FreeHeader *prevQueue;  // doubly linked
 184    TreeNode *treeNode; // which tree node we're coming off of.
 185    U32 guard;
 186 #ifdef TORQUE_DEBUG_GUARD
 187    #ifdef TORQUE_ENABLE_PROFILE_PATH
 188       U32 unused;
 189    #endif
 190    U32 postguard[4];
 191 #endif
 192 };
 193
 194 struct PageRecord
 195 {
 196    dsize_t allocSize;
 197    PageRecord *prevPage;
 198    Header *headerList;  // if headerList is NULL, this is a treeNode page
 199    void *basePtr;
 200    U32 unused[4];  // even out the record to 32 bytes...
 201                    // so if we're on a 32-byte cache-line comp, the tree nodes
 202                    // will cache better
 203 };
 204
 205 PageRecord *gPageList = NULL;
 206 TreeNode nil;
 207 TreeNode *NIL = &nil;
 208 TreeNode *gFreeTreeRoot = &nil;
 209 TreeNode *gTreeFreeList = NULL;
 210
 211 U32  gInsertCount = 0;
 212 U32  gRemoveCount = 0;
 213 U32  gBreakAlloc = 0xFFFFFFFF;
 214 U32  gCurrAlloc = 0;
 215 char gLogFilename[256] = "memlog.txt";
 216 bool gEnableLogging = false;
 217 bool gNeverLogLeaks = 0;
 218 bool gAlwaysLogLeaks = 0;
 219 U32 gBytesAllocated = 0;
 220 U32 gBlocksAllocated = 0;
 221 U32 gPageBytesAllocated = 0;
 222
 223 struct HeapIterator
 224 {
 225    PageRecord*    mCurrentPage;
 226    Header*        mCurrentHeader;
 227    bool           mAllocatedOnly;
 228
 229    HeapIterator( bool allocatedOnly = true )
 230       : mCurrentPage( gPageList ),
 231         mAllocatedOnly( allocatedOnly ),
 232         mCurrentHeader( NULL )
 233    {
 234       if( mCurrentPage )
 235       {
 236          mCurrentHeader = mCurrentPage->headerList;
 237          while( !mCurrentHeader && mCurrentPage )
 238          {
 239             mCurrentPage = mCurrentPage->prevPage;
 240             mCurrentHeader = mCurrentPage->headerList;
 241          }
 242
 243          if( mCurrentHeader && mAllocatedOnly && !( mCurrentHeader->flags & Allocated ) )
 244             ++ ( *this ); // Advance to first allocated record.
 245       }
 246    }
 247
 248    bool isValid() const
 249    {
 250       return ( mCurrentHeader != NULL );
 251    }
 252    HeapIterator& operator ++()
 253    {
 254       do
 255       {
 256          if( !mCurrentHeader )
 257          {
 258             if( mCurrentPage )
 259                mCurrentPage = mCurrentPage->prevPage;
 260
 261             if( !mCurrentPage )
 262                break;
 263             mCurrentHeader = mCurrentPage->headerList;
 264          }
 265          else
 266             mCurrentHeader = mCurrentHeader->next;
 267       }
 268       while( !mCurrentHeader || ( mAllocatedOnly && !( mCurrentHeader->flags & Allocated ) ) );
 269
 270       return *this;
 271    }
 272    operator Header*() const
 273    {
 274       return mCurrentHeader;
 275    }
 276    Header* operator *() const
 277    {
 278       return mCurrentHeader;
 279    }
 280    Header* operator ->() const
 281    {
 282       return mCurrentHeader;
 283    }
 284 };
 285
 286 #ifdef TORQUE_DEBUG_GUARD
 287
 288 static bool checkGuard(Header *header, bool alloc)
 289 {
 290    U32 guardVal = alloc ? AllocatedGuard : FreeGuard;
 291    for(U32 i = 0; i < 4; i++)
 292       if(header->preguard[i] != guardVal || header->postguard[i] != guardVal)
 293       {
 294          Platform::debugBreak();
 295          return false;
 296       }
 297
 298    return true;
 299 }
 300
 301 #if !defined(TORQUE_DISABLE_MEMORY_MANAGER)
 302 static void setGuard(Header *header, bool alloc)
 303 {
 304    U32 guardVal = alloc ? AllocatedGuard : FreeGuard;
 305    for(U32 i = 0; i < 4; i++)
 306       header->preguard[i] = header->postguard[i] = guardVal;
 307 }
 308 #endif // !defined(TORQUE_DISABLE_MEMORY_MANAGER)
 309
 310 #endif // TORQUE_DEBUG_GUARD
 311
 312 static void memoryError()
 313 {
 314    // free all the pages
 315    PageRecord *walk = gPageList;
 316    while(walk) {
 317       PageRecord *prev = walk->prevPage;
 318       dRealFree(walk);
 319       walk = prev;
 320    }
 321    AssertFatal(false, "Error allocating memory! Shutting down.");
 322    Platform::AlertOK("Torque Memory Error", "Error allocating memory. Shutting down.\n");
 323    Platform::forceShutdown(-1);
 324 }
 325
 326 PageRecord *allocPage(dsize_t pageSize)
 327 {
 328    pageSize += sizeof(PageRecord);
 329    void* base = dRealMalloc(pageSize);
 330    if (base == NULL)
 331       memoryError();
 332
 333    PageRecord *rec = (PageRecord *) base;
 334    rec->basePtr = (void *) (rec + 1);
 335    rec->allocSize = pageSize;
 336    rec->prevPage = gPageList;
 337    gPageList = rec;
 338    rec->headerList = NULL;
 339    return rec;
 340 }
 341
 342 TreeNode *allocTreeNode()
 343 {
 344    if(!gTreeFreeList)
 345    {
 346       PageRecord *newPage = allocPage(TreeNodeAllocCount * sizeof(TreeNode));
 347       TreeNode *walk = (TreeNode *) newPage->basePtr;
 348       U32 i;
 349       gTreeFreeList = walk;
 350       for(i = 0; i < TreeNodeAllocCount - 1; i++, walk++)
 351          walk->parent = walk + 1;
 352       walk->parent = NULL;
 353    }
 354    TreeNode *ret = gTreeFreeList;
 355    gTreeFreeList = ret->parent;
 356    return ret;
 357 }
 358
 359 void freeTreeNode(TreeNode *tn)
 360 {
 361    tn->parent = gTreeFreeList;
 362    gTreeFreeList = tn;
 363 }
 364
 365
 366 static U32 validateTreeRecurse(TreeNode *tree)
 367 {
 368    if(tree == NIL)
 369       return 1;
 370    // check my left tree
 371    S32 lcount, rcount, nc = 0;
 372
 373    if(tree->color == Red)
 374    {
 375       if(tree->left->color == Red || tree->right->color == Red)
 376          Platform::debugBreak();
 377    }
 378    else
 379       nc = 1;
 380
 381    FreeHeader *walk = tree->queueHead;
 382    if(!walk)
 383       Platform::debugBreak();
 384
 385    FreeHeader *prev = NULL;
 386    while(walk)
 387    {
 388       if(walk->prevQueue != prev)
 389          Platform::debugBreak();
 390       if(walk->treeNode != tree)
 391          Platform::debugBreak();
 392       if(walk->size != tree->size)
 393          Platform::debugBreak();
 394       if(!walk->nextQueue && walk != tree->queueTail)
 395          Platform::debugBreak();
 396       prev = walk;
 397       walk = walk->nextQueue;
 398    }
 399
 400    lcount = validateTreeRecurse(tree->left);
 401    rcount = validateTreeRecurse(tree->right);
 402    if(lcount != rcount)
 403       Platform::debugBreak();
 404    return lcount + nc;
 405 }
 406
 407 static void validateParentageRecurse(TreeNode *tree)
 408 {
 409    if(tree->left != NIL)
 410    {
 411       if(tree->left->parent != tree)
 412          Platform::debugBreak();
 413
 414       if(tree->left->size > tree->size)
 415          Platform::debugBreak();
 416       validateParentageRecurse(tree->left);
 417    }
 418    if(tree->right != NIL)
 419    {
 420       if(tree->right->parent != tree)
 421          Platform::debugBreak();
 422
 423       if(tree->right->size < tree->size)
 424          Platform::debugBreak();
 425       validateParentageRecurse(tree->right);
 426    }
 427 }
 428
 429 static void validateTree()
 430 {
 431    if(gFreeTreeRoot == NIL)
 432       return;
 433    validateParentageRecurse(gFreeTreeRoot);
 434    validateTreeRecurse(gFreeTreeRoot);
 435 }
 436
 437 void validate()
 438 {
 439 #ifdef TORQUE_MULTITHREAD
 440    if(!gMemMutex)
 441       gMemMutex = Mutex::createMutex();
 442
 443    Mutex::lockMutex(gMemMutex);
 444 #endif
 445
 446
 447    // first validate the free tree:
 448    validateTree();
 449    // now validate all blocks:
 450    for(PageRecord *list = gPageList; list; list = list->prevPage)
 451    {
 452       Header *prev = NULL;
 453       for(Header *walk = list->headerList; walk; walk = walk->next)
 454       {
 455 #ifdef TORQUE_DEBUG_GUARD
 456          checkGuard(walk, walk->flags & Allocated);
 457 #endif
 458          if(walk->prev != prev)
 459             Platform::debugBreak();
 460          prev = walk;
 461          if(walk->next && ((const char *)(walk->next) != (const char *)(walk) + sizeof(Header) + walk->size))
 462             Platform::debugBreak();
 463       }
 464    }
 465
 466 #ifdef TORQUE_MULTITHREAD
 467    Mutex::unlockMutex(gMemMutex);
 468 #endif
 469 }
 470
 471 #if !defined(TORQUE_DISABLE_MEMORY_MANAGER)
 472 static void rotateLeft(TreeNode *hdr)
 473 {
 474    TreeNode *temp = hdr->right;
 475    hdr->right = temp->left;
 476    if(temp->left != NIL)
 477       temp->left->parent = hdr;
 478    temp->parent = hdr->parent;
 479    if(temp->parent == NIL)
 480       gFreeTreeRoot = temp;
 481    else if(hdr == hdr->parent->left)
 482       hdr->parent->left = temp;
 483    else
 484       hdr->parent->right = temp;
 485    temp->left = hdr;
 486    hdr->parent = temp;
 487 }
 488 #endif
 489
 490 #if !defined(TORQUE_DISABLE_MEMORY_MANAGER)
 491 static void rotateRight(TreeNode *hdr)
 492 {
 493    TreeNode *temp = hdr->left;
 494    hdr->left = temp->right;
 495    if(temp->right != NIL)
 496       temp->right->parent = hdr;
 497    temp->parent = hdr->parent;
 498    if(temp->parent == NIL)
 499       gFreeTreeRoot = temp;
 500    else if(hdr == hdr->parent->left)
 501       hdr->parent->left = temp;
 502    else
 503       hdr->parent->right = temp;
 504    temp->right = hdr;
 505    hdr->parent = temp;
 506 }
 507 #endif
 508
 509 #if !defined(TORQUE_DISABLE_MEMORY_MANAGER)
 510 static void treeInsert(FreeHeader *fhdr)
 511 {
 512 #ifdef TORQUE_DEBUG_GUARD
 513    checkGuard((Header *) fhdr, true); // check to see that it's got allocated guards
 514    setGuard((Header *) fhdr, false);
 515 #endif
 516    //gInsertCount++;
 517
 518    TreeNode *newParent = NIL;
 519    TreeNode *walk = gFreeTreeRoot;
 520    while(walk != NIL)
 521    {
 522       newParent = walk;
 523       if(fhdr->size < walk->size)
 524          walk = walk->left;
 525       else if(fhdr->size > walk->size)
 526          walk = walk->right;
 527       else // tag it on the end of the queue...
 528       {
 529          // insert it on this header...
 530          walk->queueTail->nextQueue = fhdr;
 531          fhdr->prevQueue = walk->queueTail;
 532          walk->queueTail = fhdr;
 533          fhdr->nextQueue = NULL;
 534          fhdr->treeNode = walk;
 535          return;
 536       }
 537    }
 538    TreeNode *hdr = allocTreeNode();
 539    hdr->size = fhdr->size;
 540    hdr->queueHead = hdr->queueTail = fhdr;
 541    fhdr->nextQueue = fhdr->prevQueue = NULL;
 542    fhdr->treeNode = hdr;
 543
 544    hdr->left = NIL;
 545    hdr->right = NIL;
 546
 547    hdr->parent = newParent;
 548
 549    if(newParent == NIL)
 550       gFreeTreeRoot = hdr;
 551    else if(hdr->size < newParent->size)
 552       newParent->left = hdr;
 553    else
 554       newParent->right = hdr;
 555
 556    // do red/black rotations
 557    hdr->color = Red;
 558    while(hdr != gFreeTreeRoot && (hdr->parent->color == Red))
 559    {
 560       TreeNode *parent = hdr->parent;
 561       TreeNode *pparent = hdr->parent->parent;
 562
 563       if(parent == pparent->left)
 564       {
 565          TreeNode *temp = pparent->right;
 566          if(temp->color == Red)
 567          {
 568             parent->color = Black;
 569             temp->color = Black;
 570             pparent->color = Red;
 571             hdr = pparent;
 572          }
 573          else
 574          {
 575             if(hdr == parent->right)
 576             {
 577                hdr = parent;
 578                rotateLeft(hdr);
 579                parent = hdr->parent;
 580                pparent = hdr->parent->parent;
 581             }
 582             parent->color = Black;
 583             pparent->color = Red;
 584             rotateRight(pparent);
 585          }
 586       }
 587       else
 588       {
 589          TreeNode *temp = pparent->left;
 590          if(temp->color == Red)
 591          {
 592             parent->color = Black;
 593             temp->color = Black;
 594             pparent->color = Red;
 595             hdr = pparent;
 596          }
 597          else
 598          {
 599             if(hdr == parent->left)
 600             {
 601                hdr = parent;
 602                rotateRight(hdr);
 603                parent = hdr->parent;
 604                pparent = hdr->parent->parent;
 605             }
 606             parent->color = Black;
 607             pparent->color = Red;
 608             rotateLeft(pparent);
 609          }
 610       }
 611    }
 612    gFreeTreeRoot->color = Black;
 613    //validateTree();
 614 }
 615 #endif
 616
 617 #if !defined(TORQUE_DISABLE_MEMORY_MANAGER)
 618 static void treeRemove(FreeHeader *hdr)
 619 {
 620 #ifdef TORQUE_DEBUG_GUARD
 621    checkGuard((Header *) hdr, false);
 622    setGuard((Header *) hdr, true);
 623 #endif
 624    //validateTree();
 625    //gRemoveCount++;
 626
 627    FreeHeader *prev = hdr->prevQueue;
 628    FreeHeader *next = hdr->nextQueue;
 629
 630    if(prev)
 631       prev->nextQueue = next;
 632    else
 633       hdr->treeNode->queueHead = next;
 634
 635    if(next)
 636       next->prevQueue = prev;
 637    else
 638       hdr->treeNode->queueTail = prev;
 639
 640    if(prev || next)
 641       return;
 642
 643    TreeNode *z = hdr->treeNode;
 644
 645    nil.color = Black;
 646
 647    TreeNode *y, *x;
 648    if(z->left == NIL || z->right == NIL)
 649       y = z;
 650    else
 651    {
 652       y = z->right;
 653       while(y->left != NIL)
 654          y = y->left;
 655    }
 656    if(y->left != NIL)
 657       x = y->left;
 658    else
 659       x = y->right;
 660
 661    x->parent = y->parent;
 662    if(y->parent == NIL)
 663       gFreeTreeRoot = x;
 664    else if(y == y->parent->left)
 665       y->parent->left = x;
 666    else
 667       y->parent->right = x;
 668
 669    U32 yColor = y->color;
 670    if(y != z)
 671    {
 672       // copy y's important fields into z (since we're going to free y)
 673       if(z->parent->left == z)
 674          z->parent->left = y;
 675       else if(z->parent->right == z)
 676          z->parent->right = y;
 677       y->left = z->left;
 678       y->right = z->right;
 679       if(y->left != NIL)
 680          y->left->parent = y;
 681       if(y->right != NIL)
 682          y->right->parent = y;
 683       y->parent = z->parent;
 684       if(z->parent == NIL)
 685          gFreeTreeRoot = y;
 686       y->color = z->color;
 687       if(x->parent == z)
 688          x->parent = y;
 689       //validateTree();
 690    }
 691    freeTreeNode(z);
 692
 693    if(yColor == Black)
 694    {
 695       while(x != gFreeTreeRoot && x->color == Black)
 696       {
 697          TreeNode *w;
 698          if(x == x->parent->left)
 699          {
 700             w = x->parent->right;
 701             if(w->color == Red)
 702             {
 703                w->color = Black;
 704                x->parent->color = Red;
 705                rotateLeft(x->parent);
 706                w = x->parent->right;
 707             }
 708             if(w->left->color == Black && w->right->color == Black)
 709             {
 710                w->color = Red;
 711                x = x->parent;
 712             }
 713             else
 714             {
 715                if(w->right->color == Black)
 716                {
 717                   w->left->color = Black;
 718                   rotateRight(w);
 719                   w = x->parent->right;
 720                }
 721                w->color = x->parent->color;
 722                x->parent->color = Black;
 723                w->right->color = Black;
 724                rotateLeft(x->parent);
 725                x = gFreeTreeRoot;
 726             }
 727          }
 728          else
 729          {
 730             w = x->parent->left;
 731             if(w->color == Red)
 732             {
 733                w->color = Black;
 734                x->parent->color = Red;
 735                rotateRight(x->parent);
 736                w = x->parent->left;
 737             }
 738             if(w->left->color == Black && w->right->color == Black)
 739             {
 740                w->color = Red;
 741                x = x->parent;
 742             }
 743             else
 744             {
 745                if(w->left->color == Black)
 746                {
 747                   w->right->color = Black;
 748                   rotateLeft(w);
 749                   w = x->parent->left;
 750                }
 751                w->color = x->parent->color;
 752                x->parent->color = Black;
 753                w->left->color = Black;
 754                rotateRight(x->parent);
 755                x = gFreeTreeRoot;
 756             }
 757          }
 758       }
 759       x->color = Black;
 760    }
 761    //validateTree();
 762 }
 763 #endif
 764
 765 #if !defined(TORQUE_DISABLE_MEMORY_MANAGER)
 766 static FreeHeader *treeFindSmallestGreaterThan(dsize_t size)
 767 {
 768    TreeNode *bestMatch = NIL;
 769    TreeNode *walk = gFreeTreeRoot;
 770    while(walk != NIL)
 771    {
 772       if(size == walk->size)
 773          return walk->queueHead;
 774       else if(size > walk->size)
 775          walk = walk->right;
 776       else // size < walk->size
 777       {
 778          bestMatch = walk;
 779          walk = walk->left;
 780       }
 781    }
 782    //validateTree();
 783    if(bestMatch != NIL)
 784       return bestMatch->queueHead;
 785
 786    return NULL;
 787 }
 788 #endif
 789
 790 /// Trigger a breakpoint if ptr is not a valid heap pointer or if its memory guards
 791 /// have been destroyed (only if TORQUE_DEBUG_GUARD is enabled).
 792 ///
 793 /// @note This function does not allow interior pointers!
 794
 795 void checkPtr( void* ptr )
 796 {
 797    for( HeapIterator iter; iter.isValid(); ++ iter )
 798    {
 799       AllocatedHeader* header = ( AllocatedHeader* ) *iter;
 800       if( header->getUserPtr() == ptr )
 801       {
 802 #ifdef TORQUE_DEBUG_GUARD
 803          char buffer[ 1024 ];
 804          if( !checkGuard( *iter, true ) )
 805          {
 806             dSprintf( buffer, sizeof( buffer ), "0x%x is a valid heap pointer but has its guards corrupted", ptr );
 807             Platform::outputDebugString( buffer );
 808             return;
 809          }
 810          //dSprintf( buffer, sizeof( buffer ), "0x%x is a valid heap pointer", ptr );
 811          //Platform::outputDebugString( buffer );
 812 #endif
 813          return;
 814       }
 815    }
 816
 817    char buffer[ 1024 ];
 818    dSprintf( buffer, sizeof( buffer ), "0x%x is not a valid heap pointer", ptr );
 819    Platform::outputDebugString( buffer );
 820
 821    Platform::debugBreak();
 822 }
 823
 824 /// Dump info on all memory blocks that are still allocated.
 825 /// @note Only works if TORQUE_DISABLE_MEMORY_MANAGER is not defined; otherwise this is a NOP.
 826
 827 void ensureAllFreed()
 828 {
 829 #ifndef TORQUE_DISABLE_MEMORY_MANAGER
 830
 831    U32 numLeaks      = 0;
 832    U32 bytesLeaked   = 0;
 833
 834    for( HeapIterator iter; iter.isValid(); ++ iter )
 835    {
 836       AllocatedHeader* header = ( AllocatedHeader* ) *iter;
 837       if( !( header->flags & GlobalFlag ) )
 838       {
 839          // Note: can't spill profile paths here since they by
 840          //  now are all invalid (they're on the now freed string table)
 841
 842 #ifdef TORQUE_DEBUG_GUARD
 843          Platform::outputDebugString( "MEMORY LEAKED: 0x%x %i %s %s:%i = %i (%i)",
 844             header->getUserPtr(),
 845             header->allocNum,
 846             ( header->flags & StaticFlag ? "(static)" : "" ),
 847             header->fileName, header->line, header->realSize, header->size );
 848          numLeaks ++;
 849          bytesLeaked += header->size;
 850 #endif
 851       }
 852    }
 853
 854    if( numLeaks )
 855       Platform::outputDebugString( "NUM LEAKS: %i (%i bytes)", numLeaks, bytesLeaked );
 856 #endif
 857 }
 858
 859 struct MemDumpLog
 860 {
 861    U32 size;
 862    U32 count;
 863    U32 depthTotal;
 864    U32 maxDepth;
 865    U32 minDepth;
 866 };
 867
 868 void logDumpTraverse(MemDumpLog *sizes, TreeNode *header, U32 depth)
 869 {
 870    if(header == NIL)
 871       return;
 872    MemDumpLog *mySize = sizes;
 873    while(mySize->size < header->size)
 874       mySize++;
 875
 876    U32 cnt = 0;
 877    for(FreeHeader *walk = header->queueHead; walk; walk = walk->nextQueue)
 878       cnt++;
 879    mySize->count += cnt;
 880    mySize->depthTotal += depth * cnt;
 881    mySize->maxDepth = depth > mySize->maxDepth ? depth : mySize->maxDepth;
 882    mySize->minDepth = depth < mySize->minDepth ? depth : mySize->minDepth;
 883    logDumpTraverse(sizes, header->left, depth + 1);
 884    logDumpTraverse(sizes, header->right, depth + 1);
 885 }
 886
 887 #ifdef TORQUE_DEBUG
 888 DefineConsoleFunction( validateMemory, void, ( ),,
 889    "@brief Used to validate memory space for the game.\n\n"
 890    "@ingroup Debugging" )
 891 {
 892    validate();
 893 }
 894 #endif
 895
 896 DefineConsoleFunction( freeMemoryDump, void, ( ),,
 897    "@brief Dumps some useful statistics regarding free memory.\n\n"
 898    "Dumps an analysis of \'free chunks\' of memory. "
 899    "Does not print how much memory is free.\n\n"
 900    "@ingroup Debugging" )
 901 {
 902    U32 startSize = 16;
 903    MemDumpLog memSizes[20];
 904    U32 i;
 905    for(i = 0; i < 20; i++)
 906    {
 907       memSizes[i].size = startSize << i;
 908       memSizes[i].count = 0;
 909       memSizes[i].depthTotal = 0;
 910       memSizes[i].maxDepth = 0;
 911       memSizes[i].minDepth = 1000;
 912    }
 913    memSizes[19].size = MaxAllocationAmount;
 914    logDumpTraverse(memSizes, gFreeTreeRoot, 1);
 915    MemDumpLog fullMem;
 916    fullMem.count = 0;
 917    fullMem.depthTotal = 0;
 918    fullMem.maxDepth = 0;
 919    fullMem.minDepth = 1000;
 920
 921    for(i = 0; i < 20; i++)
 922    {
 923       if(memSizes[i].count)
 924          Con::printf("Size: %d - Free blocks: %d  Max Depth: %d  Min Depth: %d  Average Depth: %g",
 925                memSizes[i].size, memSizes[i].count, memSizes[i].maxDepth, memSizes[i].minDepth,
 926                F32(memSizes[i].depthTotal) / F32(memSizes[i].count));
 927
 928       fullMem.count += memSizes[i].count;
 929       fullMem.depthTotal += memSizes[i].depthTotal;
 930       fullMem.maxDepth = memSizes[i].maxDepth > fullMem.maxDepth ? memSizes[i].maxDepth : fullMem.maxDepth;
 931       fullMem.minDepth = memSizes[i].minDepth < fullMem.minDepth ? memSizes[i].minDepth : fullMem.minDepth;
 932    }
 933    Con::printf("Total free blocks: %d  Max Depth: %d  Min Depth: %d  Average Depth: %g",
 934          fullMem.count, fullMem.maxDepth, fullMem.minDepth, F32(fullMem.depthTotal) / F32(fullMem.count));
 935 }
 936
 937 #ifdef TORQUE_DEBUG_GUARD
 938
 939 void flagCurrentAllocs( EFlag flag )
 940 {
 941 #ifdef TORQUE_ENABLE_PROFILE_PATH
 942    if (gProfiler && !gProfiler->isEnabled())
 943    {
 944       gProfiler->enable(true);
 945       // warm it up
 946       //gProfiler->dumpToConsole();
 947    }
 948 #endif
 949
 950    U32 bit = flagToBit( flag );
 951    for( HeapIterator iter; iter.isValid(); ++ iter )
 952       iter->flags |= bit;
 953 }
 954
 955 DefineEngineFunction(flagCurrentAllocs, void, (),,
 956         "@brief Flags all current memory allocations.\n\n"
 957         "Flags all current memory allocations for exclusion in subsequent calls to dumpUnflaggedAllocs(). "
 958         "Helpful in detecting memory leaks and analyzing memory usage.\n\n"
 959         "@ingroup Debugging" )
 960 {
 961    flagCurrentAllocs();
 962 }
 963
 964 void dumpUnflaggedAllocs(const char *file, EFlag flag)
 965 {
 966    countUnflaggedAllocs(file, NULL, flag);
 967 }
 968
 969 S32 countUnflaggedAllocs(const char * filename, S32 *outUnflaggedRealloc, EFlag flag)
 970 {
 971    S32 unflaggedAllocCount = 0;
 972    S32 unflaggedReAllocCount = 0;
 973
 974    FileStream fws;
 975    bool useFile = filename && *filename;
 976    if (useFile)
 977       useFile = fws.open(filename, Torque::FS::File::Write);
 978    char buffer[1024];
 979
 980    U32 bit = flagToBit( flag );
 981
 982    PageRecord* walk;
 983    for (walk = gPageList; walk; walk = walk->prevPage)
 984    {
 985       for(Header *probe = walk->headerList; probe; probe = probe->next)
 986       {
 987          if (probe->flags & Allocated)
 988          {
 989             AllocatedHeader* pah = (AllocatedHeader*)probe;
 990             if (!(pah->flags & bit))
 991             {
 992                // If you want to extract further information from an unflagged
 993                // memory allocation, do the following:
 994                // U8 *foo = (U8 *)pah;
 995                // foo += sizeof(Header);
 996                // FooObject *obj = (FooObject *)foo;
 997                dSprintf(buffer, 1023, "%s%s\t%d\t%d\t%d\r\n",
 998                   pah->flags & Reallocated ? "[R] " : "",
 999                   pah->fileName != NULL ? pah->fileName : "Undetermined",
1000                   pah->line, pah->realSize, pah->allocNum);
1001
1002                if( pah->flags & Reallocated )
1003                   unflaggedReAllocCount++;
1004                else
1005                   unflaggedAllocCount++;
1006
1007                if (useFile)
1008                {
1009                   fws.write(dStrlen(buffer), buffer);
1010                   fws.write(2, "\r\n");
1011                }
1012                else
1013                {
1014                   if( pah->flags & Reallocated )
1015                      Con::warnf(buffer);
1016                   else
1017                      Con::errorf(buffer);
1018                }
1019
1020 #ifdef TORQUE_ENABLE_PROFILE_PATH
1021                static char line[4096];
1022                dSprintf(line, sizeof(line), "   %s\r\nreal size=%d",
1023                   pah->profilePath ? pah->profilePath : "unknown",
1024                   pah->realSize);
1025
1026                if (useFile)
1027                {
1028                   fws.write(dStrlen(line), line);
1029                   fws.write(2, "\r\n");
1030                }
1031                else
1032                {
1033                   if( pah->flags & Reallocated )
1034                      Con::warnf(line);
1035                   else
1036                      Con::errorf(line);
1037                }
1038 #endif
1039
1040             }
1041          }
1042       }
1043    }
1044
1045    if (useFile)
1046       fws.close();
1047
1048    if( outUnflaggedRealloc != NULL )
1049       *outUnflaggedRealloc = unflaggedReAllocCount;
1050
1051    return unflaggedAllocCount;
1052 }
1053
1054 DefineEngineFunction(dumpUnflaggedAllocs, void, ( const char* fileName ), ( "" ),
1055    "@brief Dumps all unflagged memory allocations.\n\n"
1056    "Dumps all memory allocations that were made after a call to flagCurrentAllocs(). "
1057    "Helpful when used with flagCurrentAllocs() for detecting memory leaks and analyzing general memory usage.\n\n"
1058    "@param fileName Optional file path and location to dump all memory allocations not flagged by flagCurrentAllocs(). "
1059    "If left blank, data will be dumped to the console.\n\n"
1060    "@tsexample\n"
1061    "dumpMemSnapshot(); // dumps info to console\n"
1062    "dumpMemSnapshot( \"C:/Torque/profilerlog1.txt\" ); // dumps info to file\n"
1063    "@endtsexample\n\n"
1064    "@note Available in debug builds only. "
1065    "In torqueConfig.h, TORQUE_DISABLE_MEMORY_MANAGER must be undefined to use this function.\n\n"
1066    "@ingroup Debugging" )
1067 {
1068    dumpUnflaggedAllocs(fileName);
1069 }
1070
1071 static void initLog()
1072 {
1073    static const char* sInitString = " --- INIT MEMORY LOG (ACTION): (FILE) (LINE) (SIZE) (ALLOCNUMBER) ---\r\n";
1074
1075    FileStream fws;
1076    fws.open(gLogFilename, Torque::FS::File::Write);
1077    fws.write(dStrlen(sInitString), sInitString);
1078    fws.close();
1079 }
1080
1081 #if !defined(TORQUE_DISABLE_MEMORY_MANAGER)
1082 static void logAlloc(const AllocatedHeader* hdr, S32 memSize)
1083 {
1084    FileStream fws;
1085    fws.open(gLogFilename, Torque::FS::File::ReadWrite);
1086    fws.setPosition(fws.getStreamSize());
1087
1088    char buffer[1024];
1089    dSprintf(buffer, 1023, "alloc: %s %d %d %d\r\n",
1090             hdr->fileName != NULL ? hdr->fileName : "Undetermined",
1091             hdr->line, memSize, hdr->allocNum);
1092    fws.write(dStrlen(buffer), buffer);
1093    fws.close();
1094 }
1095 #endif
1096
1097 #if !defined(TORQUE_DISABLE_MEMORY_MANAGER)
1098 static void logRealloc(const AllocatedHeader* hdr, S32 memSize)
1099 {
1100    FileStream fws;
1101    fws.open(gLogFilename, Torque::FS::File::ReadWrite);
1102    fws.setPosition(fws.getStreamSize());
1103
1104    char buffer[1024];
1105    dSprintf(buffer, 1023, "realloc: %s %d %d %d\r\n",
1106             hdr->fileName != NULL ? hdr->fileName : "Undetermined",
1107             hdr->line, memSize, hdr->allocNum);
1108    fws.write(dStrlen(buffer), buffer);
1109    fws.close();
1110 }
1111 #endif
1112
1113 #if !defined(TORQUE_DISABLE_MEMORY_MANAGER)
1114 static void logFree(const AllocatedHeader* hdr)
1115 {
1116    FileStream fws;
1117    fws.open(gLogFilename, Torque::FS::File::ReadWrite);
1118    fws.setPosition(fws.getStreamSize());
1119
1120    char buffer[1024];
1121    dSprintf(buffer, 1023, "free:  %s %d %d\r\n",
1122             hdr->fileName != NULL ? hdr->fileName : "Undetermined",
1123             hdr->line, hdr->allocNum);
1124    fws.write(dStrlen(buffer), buffer);
1125    fws.close();
1126 }
1127 #endif // !defined(TORQUE_DISABLE_MEMORY_MANAGER)
1128
1129 #endif
1130
1131 void enableLogging(const char* fileName)
1132 {
1133    dStrcpy(gLogFilename, fileName);
1134    if (!gEnableLogging)
1135    {
1136       gEnableLogging = true;
1137 #ifdef TORQUE_DEBUG_GUARD
1138       initLog();
1139 #endif
1140    }
1141 }
1142
1143 void disableLogging()
1144 {
1145    gLogFilename[0] = '\0';
1146    gEnableLogging = false;
1147 }
1148
1149 // CodeReview - this is never called so commented out to save warning.
1150 // Do we want to re-enable it?  Might be nice to get leak tracking on
1151 // exit...or maybe that is just a problematical feature we shouldn't
1152 // worry about.
1153 //static void shutdown()
1154 //{
1155 //#ifdef TORQUE_MULTITHREAD
1156 //   Mutex::destroyMutex(gMemMutex);
1157 //   gMemMutex = NULL;
1158 //#endif
1159 //
1160 //#ifdef TORQUE_DEBUG_GUARD
1161 //
1162 //   // write out leaks and such
1163 //   const U32 maxNumLeaks = 1024;
1164 //   U32 numLeaks = 0;
1165 //
1166 //   AllocatedHeader* pLeaks[maxNumLeaks];
1167 //   for (PageRecord * walk = gPageList; walk; walk = walk->prevPage)
1168 //      for(Header *probe = walk->headerList; probe; probe = probe->next)
1169 //         if ((probe->flags & Allocated) && ((AllocatedHeader *)probe)->fileName != NULL)
1170 //            pLeaks[numLeaks++] = (AllocatedHeader *) probe;
1171 //
1172 //   if (numLeaks && !gNeverLogLeaks)
1173 //   {
1174 //      if (gAlwaysLogLeaks || Platform::AlertOKCancel("Memory Status", "Memory leaks detected.  Write to memoryLeaks.log?") == true)
1175 //      {
1176 //         char buffer[1024];
1177 //         FileStream logFile;
1178 //         logFile.open("memoryLeaks.log", Torque::FS::File::Write);
1179 //
1180 //         for (U32 i = 0; i < numLeaks; i++)
1181 //         {
1182 //            dSprintf(buffer, 1023, "Leak in %s: %d (%d)\r\n", pLeaks[i]->fileName, pLeaks[i]->line, pLeaks[i]->allocNum);
1183 //            logFile.write(dStrlen(buffer), buffer);
1184 //         }
1185 //         logFile.close();
1186 //      }
1187 //   }
1188 //#endif
1189 //
1190 //   // then free all the memory pages
1191 //   for (PageRecord * walk = gPageList; walk; )
1192 //   {
1193 //      PageRecord *prev = walk->prevPage;
1194 //      dRealFree(walk);
1195 //      walk = prev;
1196 //   }
1197 //}
1198
1199 #if !defined(TORQUE_DISABLE_MEMORY_MANAGER)
1200 static Header *allocMemPage(dsize_t pageSize)
1201 {
1202    pageSize += sizeof(Header);
1203    if(pageSize < MinPageSize)
1204       pageSize = MinPageSize;
1205    PageRecord *base = allocPage(pageSize);
1206
1207    Header* rec = (Header*)base->basePtr;
1208    base->headerList = rec;
1209
1210    rec->size = pageSize - sizeof(Header);
1211    rec->next = NULL;
1212    rec->prev = NULL;
1213    rec->flags = 0;
1214 #ifdef TORQUE_DEBUG_GUARD
1215    setGuard(rec, true);
1216 #endif
1217
1218 #ifdef LOG_PAGE_ALLOCS
1219    gPageBytesAllocated += pageSize;
1220    // total bytes allocated so far will be 0 when TORQUE_DEBUG_GUARD is disabled, so convert that into more meaningful string
1221    const U32 StrSize = 256;
1222    char strBytesAllocated[StrSize];
1223    if (gBytesAllocated > 0)
1224       dSprintf(strBytesAllocated, sizeof(strBytesAllocated), "%i", gBytesAllocated);
1225    else
1226       dStrncpy(strBytesAllocated,"unknown - enable TORQUE_DEBUG_GUARD", StrSize);
1227
1228 #ifndef TORQUE_MULTITHREAD // May deadlock.
1229    // NOTE: This code may be called within Con::_printf, and if that is the case
1230    // this will infinitly recurse. This is the reason for the code in Con::_printf
1231    // that sets Con::active to false. -patw
1232    if (Con::isActive())
1233       Con::errorf("PlatformMemory: allocating new page, total bytes allocated so far: %s (total bytes in all pages=%i)",strBytesAllocated,gPageBytesAllocated);
1234 #endif
1235 #endif
1236    return rec;
1237 }
1238 #endif
1239
1240 #if !defined(TORQUE_DISABLE_MEMORY_MANAGER)
1241 static void checkUnusedAlloc(FreeHeader *header, U32 size)
1242 {
1243    //validate();
1244    if(header->size >= size + sizeof(Header) + 16)
1245    {
1246       U8 *basePtr = (U8 *) header;
1247       basePtr += sizeof(Header);
1248       FreeHeader *newHeader = (FreeHeader *) (basePtr + size);
1249       newHeader->next = header->next;
1250       newHeader->prev = (Header *) header;
1251       header->next = (Header *) newHeader;
1252       if(newHeader->next)
1253          newHeader->next->prev = (Header *) newHeader;
1254       newHeader->flags = 0;
1255       newHeader->size = header->size - size - sizeof(Header);
1256       header->size = size;
1257 #ifdef TORQUE_DEBUG_GUARD
1258       setGuard((Header *) newHeader, true);
1259 #endif
1260       treeInsert(newHeader);
1261    }
1262 }
1263 #endif
1264
1265 #if defined(TORQUE_MULTITHREAD) && !defined(TORQUE_DISABLE_MEMORY_MANAGER)
1266 static bool gReentrantGuard = false;
1267 #endif
1268
1269 #if !defined(TORQUE_DISABLE_MEMORY_MANAGER)
1270 static void* alloc(dsize_t size, bool array, const char* fileName, const U32 line)
1271 {
1272    AssertFatal(size < MaxAllocationAmount, "Memory::alloc - tried to allocate > MaxAllocationAmount!");
1273
1274 #ifdef TORQUE_MULTITHREAD
1275    if(!gMemMutex && !gReentrantGuard)
1276    {
1277       gReentrantGuard = true;
1278       gMemMutex = Mutex::createMutex();
1279       gReentrantGuard = false;
1280    }
1281
1282    if(!gReentrantGuard)
1283       Mutex::lockMutex(gMemMutex);
1284
1285 #endif
1286
1287    AssertFatal(size < MaxAllocationAmount, "Size error.");
1288    //validate();
1289    if (size == 0)
1290    {
1291 #ifdef TORQUE_MULTITHREAD
1292       if(!gReentrantGuard)
1293          Mutex::unlockMutex(gMemMutex);
1294 #endif
1295       return NULL;
1296    }
1297
1298 #ifndef TORQUE_ENABLE_PROFILE_PATH
1299    // Note: will cause crash if profile path is on
1300    PROFILE_START(MemoryAlloc);
1301 #endif
1302
1303 #ifdef TORQUE_DEBUG_GUARD
1304    // if we're guarding, round up to the nearest DWORD
1305    size = ((size + 3) & ~0x3);
1306 #else
1307    // round up size to nearest 16 byte boundary (cache lines and all...)
1308    size = ((size + 15) & ~0xF);
1309 #endif
1310
1311    FreeHeader *header = treeFindSmallestGreaterThan(size);
1312    if(header)
1313       treeRemove(header);
1314    else
1315       header = (FreeHeader *) allocMemPage(size);
1316
1317    // ok, see if there's enough room in the block to make another block
1318    // for this to happen it has to have enough room for a header
1319    // and 16 more bytes.
1320
1321    U8 *basePtr = (U8 *) header;
1322    basePtr += sizeof(Header);
1323
1324    checkUnusedAlloc(header, size);
1325
1326    AllocatedHeader *retHeader = (AllocatedHeader *) header;
1327    retHeader->flags = array ? (Allocated | Array) : Allocated;
1328
1329 #ifdef TORQUE_DEBUG_GUARD
1330    retHeader->line = line;
1331    retHeader->fileName = fileName;
1332    retHeader->allocNum = gCurrAlloc;
1333    retHeader->realSize = size;
1334 #ifdef TORQUE_ENABLE_PROFILE_PATH
1335    retHeader->profilePath = gProfiler ? gProfiler->getProfilePath() : "pre";
1336 #endif
1337    gBytesAllocated += size;
1338    gBlocksAllocated ++;
1339    //static U32 skip = 0;
1340    //if ((++skip % 1000) == 0)
1341    //   Con::printf("new=%i, newnew=%i, imagenew=%i",gBytesAllocated,gNewNewTotal,gImageAlloc);
1342    if (gEnableLogging)
1343       logAlloc(retHeader, size);
1344 #endif
1345    if(gCurrAlloc == gBreakAlloc && gBreakAlloc != 0xFFFFFFFF)
1346       Platform::debugBreak();
1347    gCurrAlloc++;
1348 #ifndef TORQUE_ENABLE_PROFILE_PATH
1349    PROFILE_END();
1350 #endif
1351    //validate();
1352
1353 #ifdef TORQUE_DEBUG
1354    // fill the block with the fill value.  although this is done in free(), that won't fill
1355    // newly allocated MM memory (which hasn't been freed yet).  We use a different fill value
1356    // to diffentiate filled freed memory from filled new memory; this may aid debugging.
1357    #ifndef TORQUE_ENABLE_PROFILE_PATH
1358       PROFILE_START(stompMem1);
1359    #endif
1360    dMemset(basePtr, 0xCF, size);
1361    #ifndef TORQUE_ENABLE_PROFILE_PATH
1362       PROFILE_END();
1363    #endif
1364 #endif
1365
1366    if(gCurrAlloc == gBreakAlloc && gBreakAlloc != 0xFFFFFFFF)
1367       Platform::debugBreak();
1368
1369    gCurrAlloc++;
1370
1371 #ifdef TORQUE_MULTITHREAD
1372    if(!gReentrantGuard)
1373       Mutex::unlockMutex(gMemMutex);
1374 #endif
1375
1376    return basePtr;
1377 }
1378 #endif
1379
1380 #if !defined(TORQUE_DISABLE_MEMORY_MANAGER)
1381 static void free(void* mem, bool array)
1382 {
1383    // validate();
1384
1385    if (!mem)
1386       return;
1387
1388 #ifdef TORQUE_MULTITHREAD
1389    if(!gMemMutex)
1390       gMemMutex = Mutex::createMutex();
1391
1392    if( mem != gMemMutex )
1393       Mutex::lockMutex(gMemMutex);
1394    else
1395       gMemMutex = NULL;
1396 #endif
1397
1398    PROFILE_START(MemoryFree);
1399    AllocatedHeader *hdr = ((AllocatedHeader *)mem) - 1;
1400
1401    AssertFatal(hdr->flags & Allocated, avar("Not an allocated block!"));
1402    AssertFatal(((bool)((hdr->flags & Array)==Array))==array, avar("Array alloc mismatch. "));
1403
1404    gBlocksAllocated --;
1405 #ifdef TORQUE_DEBUG_GUARD
1406    gBytesAllocated -= hdr->realSize;
1407    if (gEnableLogging)
1408       logFree(hdr);
1409 #endif
1410
1411    hdr->flags = 0;
1412
1413    // fill the block with the fill value
1414
1415 #ifdef TORQUE_DEBUG
1416    #ifndef TORQUE_ENABLE_PROFILE_PATH
1417       PROFILE_START(stompMem2);
1418    #endif
1419    dMemset(mem, 0xCE, hdr->size);
1420    #ifndef TORQUE_ENABLE_PROFILE_PATH
1421       PROFILE_END();
1422    #endif
1423 #endif
1424
1425    // see if we can merge hdr with the block after it.
1426
1427    Header* next = hdr->next;
1428    if (next && next->flags == 0)
1429    {
1430       treeRemove((FreeHeader *) next);
1431       hdr->size += next->size + sizeof(Header);
1432       hdr->next = next->next;
1433       if(next->next)
1434          next->next->prev = (Header *) hdr;
1435    }
1436
1437    // see if we can merge hdr with the block before it.
1438    Header* prev = hdr->prev;
1439
1440    if (prev && prev->flags == 0)
1441    {
1442       treeRemove((FreeHeader *) prev);
1443       prev->size += hdr->size + sizeof(Header);
1444       prev->next = hdr->next;
1445       if (hdr->next)
1446          hdr->next->prev = prev;
1447
1448       hdr = (AllocatedHeader *) prev;
1449    }
1450
1451    // throw this puppy into the tree!
1452    treeInsert((FreeHeader *) hdr);
1453    PROFILE_END();
1454
1455 //   validate();
1456
1457 #ifdef TORQUE_MULTITHREAD
1458    Mutex::unlockMutex(gMemMutex);
1459 #endif
1460 }
1461 #endif
1462
1463 #if !defined(TORQUE_DISABLE_MEMORY_MANAGER)
1464 static void* realloc(void* mem, dsize_t size, const char* fileName, const U32 line)
1465 {
1466    //validate();
1467    if (!size) {
1468       free(mem, false);
1469       return NULL;
1470    }
1471    if(!mem)
1472       return alloc(size, false, fileName, line);
1473
1474 #ifdef TORQUE_MULTITHREAD
1475    if(!gMemMutex)
1476       gMemMutex = Mutex::createMutex();
1477
1478    Mutex::lockMutex(gMemMutex);
1479 #endif
1480
1481    AllocatedHeader* hdr = ((AllocatedHeader *)mem) - 1;
1482 #ifdef TORQUE_DEBUG_GUARD
1483    checkGuard( ( Header* ) hdr, true );
1484 #endif
1485
1486    AssertFatal((hdr->flags & Allocated) == Allocated, "Bad block flags.");
1487
1488    size = (size + 0xF) & ~0xF;
1489
1490    U32 oldSize = hdr->size;
1491    if(oldSize == size)
1492    {
1493 #ifdef TORQUE_MULTITHREAD
1494       Mutex::unlockMutex(gMemMutex);
1495 #endif
1496       return mem;
1497    }
1498    PROFILE_START(MemoryRealloc);
1499
1500    FreeHeader *next = (FreeHeader *) hdr->next;
1501
1502 #ifdef TORQUE_DEBUG_GUARD
1503    // adjust header size and allocated bytes size
1504    hdr->realSize   += size - oldSize;
1505    gBytesAllocated += size - oldSize;
1506    if (gEnableLogging)
1507       logRealloc(hdr, size);
1508
1509    // Add reallocated flag, note header changes will not persist if the realloc
1510    // decides tofree, and then perform a fresh allocation for the memory. The flag will
1511    // be manually set again after this takes place, down at the bottom of this fxn.
1512    hdr->flags |= Reallocated;
1513
1514    // Note on Above ^
1515    // A more useful/robust implementation can be accomplished by storing an additional
1516    // AllocatedHeader* in DEBUG_GUARD builds inside the AllocatedHeader structure
1517    // itself to create a sort of reallocation history. This will be, essentially,
1518    // a allocation header stack for each allocation. Each time the memory is reallocated
1519    // it should use dRealMalloc (IMPORTANT!!) to allocate a AllocatedHeader* and chain
1520    // it to the reallocation history chain, and the dump output changed to display
1521    // reallocation history. It is also important to clean up this chain during 'free'
1522    // using dRealFree (Since memory for the chain was allocated via dRealMalloc).
1523    //
1524    // See patw for details.
1525 #endif
1526    if (next && !(next->flags & Allocated) && next->size + hdr->size + sizeof(Header) >= size)
1527    {
1528       // we can merge with the next dude.
1529       treeRemove(next);
1530       hdr->size += sizeof(Header) + next->size;
1531       hdr->next = next->next;
1532       if(next->next)
1533          next->next->prev = (Header *) hdr;
1534
1535       checkUnusedAlloc((FreeHeader *) hdr, size);
1536       //validate();
1537       PROFILE_END();
1538 #ifdef TORQUE_MULTITHREAD
1539       Mutex::unlockMutex(gMemMutex);
1540 #endif
1541       return mem;
1542    }
1543    else if(size < oldSize)
1544    {
1545       checkUnusedAlloc((FreeHeader *) hdr, size);
1546       PROFILE_END();
1547 #ifdef TORQUE_MULTITHREAD
1548       Mutex::unlockMutex(gMemMutex);
1549 #endif
1550       return mem;
1551    }
1552 #ifdef TORQUE_DEBUG_GUARD
1553    // undo above adjustment because we're going though alloc instead
1554    hdr->realSize   -= size - oldSize;
1555    gBytesAllocated -= size - oldSize;
1556 #endif
1557    void* ret = alloc(size, false, fileName, line);
1558    dMemcpy(ret, mem, oldSize);
1559    free(mem, false);
1560    PROFILE_END();
1561
1562    // Re-enable the 'Reallocated' flag so that this allocation can be ignored by
1563    // a non-strict run of the flag/dumpunflagged.
1564    hdr = ((AllocatedHeader *)ret) - 1;
1565    hdr->flags |= Reallocated;
1566
1567 #ifdef TORQUE_MULTITHREAD
1568    Mutex::unlockMutex(gMemMutex);
1569 #endif
1570    return ret;
1571 }
1572 #endif
1573
1574 dsize_t getMemoryUsed()
1575 {
1576    U32 size = 0;
1577
1578    PageRecord* walk;
1579    for (walk = gPageList; walk; walk = walk->prevPage) {
1580       for(Header *probe = walk->headerList; probe; probe = probe->next)
1581          if (probe->flags & Allocated) {
1582             size += probe->size;
1583          }
1584    }
1585
1586    return size;
1587 }
1588
1589 #ifdef TORQUE_DEBUG_GUARD
1590 DefineEngineFunction( dumpAlloc, void, ( S32 allocNum ),,
1591                                 "@brief Dumps information about the given allocated memory block.\n\n"
1592                                 "@param allocNum Memory block to dump information about."
1593                                 "@note Available in debug builds only. "
1594                                 "In torqueConfig.h, TORQUE_DISABLE_MEMORY_MANAGER must be undefined to use this function.\n\n"
1595                                 "@ingroup Debugging")
1596 {
1597    PageRecord* walk;
1598    for( walk = gPageList; walk; walk = walk->prevPage )
1599       for( Header* probe = walk->headerList; probe; probe = probe->next )
1600          if( probe->flags & Allocated )
1601          {
1602             AllocatedHeader* pah = ( AllocatedHeader* ) probe;
1603             if( pah->allocNum == allocNum )
1604             {
1605                Con::printf( "file: %s\n"
1606                             "line: %i\n"
1607                             "size: %i\n"
1608                             "allocNum: %i\n"
1609                             "reallocated: %s",
1610                         pah->fileName != NULL ? pah->fileName : "Undetermined",
1611                         pah->line,
1612                         pah->realSize,
1613                         pah->allocNum,
1614                         pah->flags & Reallocated ? "yes" : "no"
1615                );
1616
1617                // Dump the profile path, if we have one.
1618
1619                #ifdef TORQUE_ENABLE_PROFILE_PATH
1620                if( pah->profilePath && pah->profilePath[ 0 ] )
1621                   Con::printf( "profilepath: %s", pah->profilePath );
1622                #endif
1623             }
1624          }
1625 }
1626
1627 DefineEngineFunction( dumpMemSnapshot, void, ( const char* fileName ),,
1628                                 "@brief Dumps a snapshot of current memory to a file.\n\n"
1629                                 "The total memory used will also be output to the console.\n"
1630                                 "This function will attempt to create the file if it does not already exist.\n"
1631                                 "@param fileName Name and path of file to save profiling stats to. Must use forward slashes (/)\n"
1632                                 "@tsexample\n"
1633                                 "dumpMemSnapshot( \"C:/Torque/ProfilerLogs/profilerlog1.txt\" );\n"
1634                                 "@endtsexample\n\n"
1635                                 "@note Available in debug builds only. "
1636                                 "In torqueConfig.h, TORQUE_DISABLE_MEMORY_MANAGER must be undefined to use this function.\n\n"
1637                                 "@ingroup Debugging")
1638 {
1639    FileStream fws;
1640    fws.open(fileName, Torque::FS::File::Write);
1641    char buffer[ 2048 ];
1642
1643    PageRecord* walk;
1644    for (walk = gPageList; walk; walk = walk->prevPage) {
1645       for(Header *probe = walk->headerList; probe; probe = probe->next)
1646          if (probe->flags & Allocated) {
1647             AllocatedHeader* pah = (AllocatedHeader*)probe;
1648
1649             dSprintf( buffer, sizeof( buffer ), "%s%s\t%d\t%d\t%d\r\n",
1650                      pah->flags & Reallocated ? "[R] " : "",
1651                      pah->fileName != NULL ? pah->fileName : "Undetermined",
1652                      pah->line, pah->realSize, pah->allocNum);
1653             fws.write(dStrlen(buffer), buffer);
1654
1655             // Dump the profile path, if we have one.
1656
1657             #ifdef TORQUE_ENABLE_PROFILE_PATH
1658             if( pah->profilePath )
1659             {
1660                dSprintf( buffer, sizeof( buffer ), "%s\r\n\r\n", pah->profilePath );
1661                fws.write( dStrlen( buffer ), buffer );
1662             }
1663             #endif
1664          }
1665    }
1666
1667    Con::errorf("total memory used: %d",getMemoryUsed());
1668    fws.close();
1669 }
1670 #endif
1671
1672 dsize_t getMemoryAllocated()
1673 {
1674    return 0;
1675 }
1676
1677 void getMemoryInfo( void* ptr, Info& info )
1678 {
1679    #ifndef TORQUE_DISABLE_MEMORY_MANAGER
1680
1681    AllocatedHeader* header = ( ( AllocatedHeader* ) ptr ) - 1;
1682
1683    info.mAllocSize      = header->size;
1684    #ifdef TORQUE_DEBUG_GUARD
1685    info.mAllocNumber    = header->allocNum;
1686    info.mLineNumber     = header->line;
1687    info.mFileName       = header->fileName;
1688    #endif
1689    info.mIsArray        = header->flags & Array;
1690    info.mIsGlobal       = header->flags & GlobalFlag;
1691    info.mIsStatic       = header->flags & StaticFlag;
1692
1693    #endif
1694 }
1695
1696 void setBreakAlloc(U32 breakAlloc)
1697 {
1698    gBreakAlloc = breakAlloc;
1699 }
1700
1701 ConsoleFunctionGroupEnd( Memory );
1702
1703 } // namespace Memory
1704
1705 void setMinimumAllocUnit(U32 allocUnit)
1706 {
1707    AssertFatal(isPow2(allocUnit) && allocUnit > (2 << 20),
1708                "Error, allocunit must be a power of two, and greater than 2 megs");
1709
1710    MinPageSize = allocUnit;
1711 }
1712
1713 //---------------------------------------------------------------------------
1714
1715 //---------------------------------------------------------------------------
1716
1717 #if !defined(TORQUE_DISABLE_MEMORY_MANAGER)
1718
1719 // Manage our own memory, add overloaded memory operators and functions
1720
1721 void* FN_CDECL operator new(dsize_t size, const char* fileName, const U32 line)
1722 {
1723    return Memory::alloc(size, false, fileName, line);
1724 }
1725
1726 void* FN_CDECL operator new[](dsize_t size, const char* fileName, const U32 line)
1727 {
1728    return Memory::alloc(size, true, fileName, line);
1729 }
1730
1731 void* FN_CDECL operator new(dsize_t size)
1732 {
1733    return Memory::alloc(size, false, NULL, 0);
1734 }
1735
1736 void* FN_CDECL operator new[](dsize_t size)
1737 {
1738    return Memory::alloc(size, true, NULL, 0);
1739 }
1740
1741 void FN_CDECL operator delete(void* mem)
1742 {
1743    Memory::free(mem, false);
1744 }
1745
1746 void FN_CDECL operator delete[](void* mem)
1747 {
1748    Memory::free(mem, true);
1749 }
1750
1751 void* dMalloc_r(dsize_t in_size, const char* fileName, const dsize_t line)
1752 {
1753    return Memory::alloc(in_size, false, fileName, line);
1754 }
1755
1756 void dFree(void* in_pFree)
1757 {
1758    Memory::free(in_pFree, false);
1759 }
1760
1761 void* dRealloc_r(void* in_pResize, dsize_t in_size, const char* fileName, const dsize_t line)
1762 {
1763    return Memory::realloc(in_pResize, in_size, fileName, line);
1764 }
1765
1766 AFTER_MODULE_INIT( Sim )
1767 {
1768    Con::addVariable( "$Memory::numBlocksAllocated", TypeS32, &Memory::gBlocksAllocated,
1769       "Total number of memory blocks currently allocated.\n\n"
1770       "@ingroup Debugging" );
1771    Con::addVariable( "$Memory::numBytesAllocated", TypeS32, &Memory::gBytesAllocated,
1772       "Total number of bytes currently allocated.\n\n"
1773       "@ingroup Debugging" );
1774 }
1775
1776 #else
1777
1778 // Don't manage our own memory
1779 void* dMalloc_r(dsize_t in_size, const char* fileName, const dsize_t line)
1780 {
1781    return malloc(in_size);
1782 }
1783
1784 void dFree(void* in_pFree)
1785 {
1786    free(in_pFree);
1787 }
1788
1789 void* dRealloc_r(void* in_pResize, dsize_t in_size, const char* fileName, const dsize_t line)
1790 {
1791    return realloc(in_pResize,in_size);
1792 }
1793
1794 #endif