00001
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032 #include "heap_allocator.h"
00033
00034 #include <stdio.h>
00035
00036 #ifdef NL_OS_WINDOWS
00037 #include <windows.h>
00038 #endif // NL_OS_WINDOWS
00039
00040 namespace NLMEMORY
00041 {
00042
00043
00044 #include "heap_allocator_inline.h"
00045
00046 #define NL_HEAP_SB_CATEGORY "_SmlBlk"
00047 #define NL_HEAP_CATEGORY_BLOCK_CATEGORY "_MemCat"
00048 #define NL_HEAP_MEM_DEBUG_CATEGORY "_MemDb"
00049 #define NL_HEAP_UNKNOWN_CATEGORY "Unknown"
00050
00051 void CHeapAllocatorOutputError (const char *str)
00052 {
00053 fprintf (stderr, str);
00054 #ifdef NL_OS_WINDOWS
00055 OutputDebugString (str);
00056 #endif // NL_OS_WINDOWS
00057 }
00058
00059
00060
00061
00062
00063 CHeapAllocator::CHeapAllocator (uint mainBlockSize, uint blockCount, TBlockAllocationMode blockAllocationMode,
00064 TOutOfMemoryMode outOfMemoryMode)
00065 {
00066
00067 enterCriticalSection ();
00068
00069
00070 _Name[0] = 0;
00071
00072
00073 internalAssert ((sizeof (CNodeBegin) & (Align-1)) == 0);
00074 internalAssert ((NL_HEAP_NODE_END_SIZE & (Align-1)) == 0);
00075 internalAssert ((sizeof (CFreeNode) & (Align-1)) == 0);
00076
00077
00078 internalAssert ((FirstSmallBlock&(SmallBlockGranularity-1)) == 0);
00079 internalAssert ((LastSmallBlock&(SmallBlockGranularity-1)) == 0);
00080
00081 _MainBlockList = NULL;
00082 _MainBlockSize = mainBlockSize;
00083 _BlockCount = blockCount;
00084 _BlockAllocationMode = blockAllocationMode;
00085 _OutOfMemoryMode = outOfMemoryMode;
00086 _FreeTreeRoot = &_NullNode.FreeNode;
00087 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00088 _AlwaysCheck = false;
00089 #endif // NL_HEAP_ALLOCATION_NDEBUG
00090
00091 _NullNode.FreeNode.Left = &_NullNode.FreeNode;
00092 _NullNode.FreeNode.Right = &_NullNode.FreeNode;
00093 _NullNode.FreeNode.Parent = NULL;
00094
00095 setNodeBlack (&_NullNode.FreeNode);
00096
00097 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00098 _AllocateCount = 0;
00099 #endif // NL_HEAP_ALLOCATION_NDEBUG
00100
00101
00102
00103
00104
00105
00106 const uint smallBlockSizeCount = NL_SMALLBLOCK_COUNT;
00107 uint smallBlockSize;
00108 for (smallBlockSize=0; smallBlockSize<smallBlockSizeCount; smallBlockSize++)
00109 {
00110 _FreeSmallBlocks[smallBlockSize] = NULL;
00111 }
00112
00113
00114 _SmallBlockPool = NULL;
00115
00116 leaveCriticalSection ();
00117 }
00118
00119
00120
00121 CHeapAllocator::~CHeapAllocator ()
00122 {
00123
00124 releaseMemory ();
00125 }
00126
00127
00128
00129 void CHeapAllocator::insert (CHeapAllocator::CFreeNode *x)
00130 {
00131 CHeapAllocator::CFreeNode *current, *parent;
00132
00133
00134 current = _FreeTreeRoot;
00135 parent = NULL;
00136 while (current != &_NullNode.FreeNode)
00137 {
00138 parent = current;
00139 current = (getNodeSize (getNode (x)) <= getNodeSize (getNode (current)) ) ? current->Left : current->Right;
00140 }
00141
00142
00143 x->Parent = parent;
00144 x->Left = &_NullNode.FreeNode;
00145 x->Right = &_NullNode.FreeNode;
00146 setNodeRed (x);
00147
00148
00149 if (parent)
00150 {
00151 if(getNodeSize (getNode (x)) <= getNodeSize (getNode (parent)))
00152 parent->Left = x;
00153 else
00154 parent->Right = x;
00155 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (parent);
00156 }
00157 else
00158 {
00159 _FreeTreeRoot = x;
00160 }
00161
00162 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x);
00163
00164
00165
00166
00167
00168 while (x != _FreeTreeRoot && isNodeRed (x->Parent))
00169 {
00170
00171 if (x->Parent == x->Parent->Parent->Left)
00172 {
00173 CHeapAllocator::CFreeNode *y = x->Parent->Parent->Right;
00174 if (isNodeRed (y))
00175 {
00176
00177 setNodeBlack (x->Parent);
00178 setNodeBlack (y);
00179 setNodeRed (x->Parent->Parent);
00180
00181
00182 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (y);
00183 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x->Parent);
00184 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x->Parent->Parent);
00185
00186 x = x->Parent->Parent;
00187 }
00188 else
00189 {
00190
00191 if (x == x->Parent->Right)
00192 {
00193
00194 x = x->Parent;
00195 rotateLeft(x);
00196 }
00197
00198
00199 setNodeBlack (x->Parent);
00200 setNodeRed (x->Parent->Parent);
00201
00202 rotateRight (x->Parent->Parent);
00203
00204
00205 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x->Parent);
00206 }
00207 }
00208 else
00209 {
00210
00211 CHeapAllocator::CFreeNode *y = x->Parent->Parent->Left;
00212 if (isNodeRed (y))
00213 {
00214
00215 setNodeBlack (x->Parent);
00216 setNodeBlack (y);
00217 setNodeRed (x->Parent->Parent);
00218
00219
00220 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (y);
00221 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x->Parent);
00222 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x->Parent->Parent);
00223
00224 x = x->Parent->Parent;
00225 }
00226 else
00227 {
00228
00229 if (x == x->Parent->Left)
00230 {
00231 x = x->Parent;
00232 rotateRight(x);
00233 }
00234 setNodeBlack (x->Parent);
00235 setNodeRed (x->Parent->Parent);
00236
00237 rotateLeft (x->Parent->Parent);
00238
00239
00240 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x->Parent);
00241 }
00242 }
00243 }
00244 setNodeBlack (_FreeTreeRoot);
00245
00246
00247 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (_FreeTreeRoot);
00248 }
00249
00250
00251
00252 void CHeapAllocator::erase (CHeapAllocator::CFreeNode *z)
00253 {
00254 CFreeNode *x, *y;
00255 if (z->Left == &_NullNode.FreeNode || z->Right == &_NullNode.FreeNode)
00256 {
00257
00258 y = z;
00259 }
00260 else
00261 {
00262
00263 y = z->Right;
00264 while (y->Left != &_NullNode.FreeNode)
00265 y = y->Left;
00266 }
00267
00268
00269 if (y->Left != &_NullNode.FreeNode)
00270 x = y->Left;
00271 else
00272 x = y->Right;
00273
00274
00275 x->Parent = y->Parent;
00276
00277 if (y->Parent)
00278 {
00279 if (y == y->Parent->Left)
00280 y->Parent->Left = x;
00281 else
00282 {
00283 internalAssert (y == y->Parent->Right);
00284 y->Parent->Right = x;
00285 }
00286 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (y->Parent);
00287 }
00288 else
00289 _FreeTreeRoot = x;
00290
00291 bool yRed = isNodeRed (y);
00292
00293 if (y != z)
00294 {
00295
00296 *y = *z;
00297 setNodeColor (y, isNodeRed (z));
00298 if (y->Parent)
00299 {
00300 if (y->Parent->Left == z)
00301 {
00302 y->Parent->Left = y;
00303 }
00304 else
00305 {
00306 internalAssert (y->Parent->Right == z);
00307 y->Parent->Right = y;
00308 }
00309 }
00310 else
00311 {
00312 internalAssert (_FreeTreeRoot == z);
00313 _FreeTreeRoot = y;
00314 }
00315
00316 if (y->Left)
00317 {
00318 internalAssert (y->Left->Parent == z);
00319 y->Left->Parent = y;
00320
00321 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (y->Left);
00322 }
00323 if (y->Right)
00324 {
00325 internalAssert (y->Right->Parent == z);
00326 y->Right->Parent = y;
00327
00328 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (y->Right);
00329 }
00330 }
00331
00332 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x);
00333 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (y);
00334 if (y->Parent)
00335 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (y->Parent);
00336
00337 if (!yRed)
00338 {
00339
00340
00341 while (x != _FreeTreeRoot && isNodeBlack (x))
00342 {
00343 if (x == x->Parent->Left)
00344 {
00345 CFreeNode *w = x->Parent->Right;
00346 if (isNodeRed (w))
00347 {
00348 setNodeBlack (w);
00349 setNodeRed (x->Parent);
00350 rotateLeft (x->Parent);
00351
00352 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (w);
00353
00354 w = x->Parent->Right;
00355 }
00356 if (isNodeBlack (w->Left) && isNodeBlack (w->Right))
00357 {
00358 setNodeRed (w);
00359 x = x->Parent;
00360
00361 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (w);
00362 }
00363 else
00364 {
00365 if (isNodeBlack (w->Right))
00366 {
00367 setNodeBlack (w->Left);
00368 setNodeRed (w);
00369 rotateRight (w);
00370 w = x->Parent->Right;
00371 }
00372 setNodeColor (w, isNodeRed (x->Parent));
00373 setNodeBlack (x->Parent);
00374 setNodeBlack (w->Right);
00375 rotateLeft (x->Parent);
00376
00377 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (w);
00378 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (w->Right);
00379
00380 x = _FreeTreeRoot;
00381 }
00382 }
00383 else
00384 {
00385 CFreeNode *w = x->Parent->Left;
00386 if (isNodeRed (w))
00387 {
00388 setNodeBlack (w);
00389 setNodeRed (x->Parent);
00390 rotateRight (x->Parent);
00391
00392 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (w);
00393
00394 w = x->Parent->Left;
00395 }
00396 if ( isNodeBlack (w->Right) && isNodeBlack (w->Left) )
00397 {
00398 setNodeRed (w);
00399 x = x->Parent;
00400
00401 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (w);
00402 }
00403 else
00404 {
00405 if ( isNodeBlack (w->Left) )
00406 {
00407 setNodeBlack (w->Right);
00408 setNodeRed (w);
00409 rotateLeft (w);
00410 w = x->Parent->Left;
00411 }
00412 setNodeColor (w, isNodeRed (x->Parent) );
00413 setNodeBlack (x->Parent);
00414 setNodeBlack (w->Left);
00415
00416 rotateRight (x->Parent);
00417
00418 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (w);
00419 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (w->Left);
00420
00421 x = _FreeTreeRoot;
00422 }
00423 }
00424 }
00425 setNodeBlack (x);
00426 NL_UPDATE_MAGIC_NUMBER_FREE_NODE (x);
00427 }
00428 }
00429
00430
00431
00432
00433
00434 CHeapAllocator::CNodeBegin *CHeapAllocator::splitNode (CNodeBegin *node, uint newSize)
00435 {
00436
00437 internalAssert (newSize <= getNodeSize (node));
00438
00439
00440 uint allignedSize = (newSize&~(Align-1)) + (( (newSize&(Align-1))==0 ) ? 0 : Align);
00441 if (allignedSize <= UserDataBlockSizeMin)
00442 allignedSize = UserDataBlockSizeMin;
00443
00444 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00445
00446 node->EndMagicNumber = (uint32*)((uint8*)node + newSize + sizeof (CNodeBegin));
00447 #endif // NL_HEAP_ALLOCATION_NDEBUG
00448
00449
00450 if ( getNodeSize (node) - allignedSize < UserDataBlockSizeMin + sizeof (CNodeBegin) + NL_HEAP_NODE_END_SIZE )
00451
00452 return NULL;
00453
00454
00455 CNodeBegin *newNode = (CNodeBegin*)((uint8*)node + sizeof (CNodeBegin) + allignedSize + NL_HEAP_NODE_END_SIZE );
00456
00457
00458
00459
00460 setNodeSize (newNode, getNodeSize (node) - allignedSize - sizeof (CNodeBegin) - NL_HEAP_NODE_END_SIZE);
00461
00462
00463 setNodeFree (newNode);
00464
00465
00466 newNode->Previous = node;
00467
00468
00469 setNodeLast (newNode, isNodeLast (node));
00470
00471 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00472
00473 memset (newNode->BeginMarkers, BeginNodeMarkers, CNodeBegin::MarkerSize-1);
00474 newNode->BeginMarkers[CNodeBegin::MarkerSize-1] = 0;
00475
00476
00477 newNode->EndMagicNumber = (uint32*)((uint8*)newNode + getNodeSize (newNode) + sizeof (CNodeBegin));
00478
00479
00480 CNodeEnd *endNode = (CNodeEnd*)((uint8*)newNode + getNodeSize (newNode) + sizeof (CNodeBegin));
00481 memset (endNode->EndMarkers, EndNodeMarkers, CNodeEnd::MarkerSize-1);
00482 endNode->EndMarkers[CNodeEnd::MarkerSize-1] = 0;
00483
00484
00485 newNode->File = NULL;
00486 newNode->Line = 0xffff;
00487 node->AllocateNumber = 0xffffffff;
00488 memset (newNode->Category, 0, CategoryStringLength);
00489
00490
00491 newNode->Heap = this;
00492 #endif // NL_HEAP_ALLOCATION_NDEBUG
00493
00494
00495 CNodeBegin *next = getNextNode (node);
00496 if (next)
00497 {
00498
00499 next->Previous = newNode;
00500
00501 NL_UPDATE_MAGIC_NUMBER (next);
00502 }
00503
00504
00505 internalAssert (getNodeSize (newNode) >= UserDataBlockSizeMin);
00506
00507
00508 setNodeSize (node, allignedSize);
00509
00510
00511 setNodeLast (node, false);
00512
00513
00514 return newNode;
00515 }
00516
00517
00518
00519 void CHeapAllocator::mergeNode (CNodeBegin *node)
00520 {
00521
00522 CNodeBegin *previous = node->Previous;
00523 internalAssert (getNextNode (previous) == node);
00524 internalAssert (previous);
00525 internalAssert (isNodeFree (previous));
00526
00527
00528 setNodeSize (previous, getNodeSize (previous) + getNodeSize (node) + sizeof (CNodeBegin) + NL_HEAP_NODE_END_SIZE);
00529
00530 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00531
00532 previous->EndMagicNumber = (uint32*)((uint8*)previous + getNodeSize (previous) + sizeof (CNodeBegin));
00533 #endif // NL_HEAP_ALLOCATION_NDEBUG
00534
00535
00536 CNodeBegin *next = getNextNode (node);
00537 if (next)
00538 {
00539
00540 next->Previous = previous;
00541
00542 NL_UPDATE_MAGIC_NUMBER (next);
00543 }
00544
00545
00546 setNodeLast (previous, isNodeLast (node));
00547
00548 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00549
00550
00551
00552
00553 memset (((uint8*)node + getNodeSize (node) + sizeof (CNodeBegin)), DeletedMemory, NL_HEAP_NODE_END_SIZE);
00554 memset (node, DeletedMemory, sizeof (CNodeBegin));
00555 #endif // NL_HEAP_ALLOCATION_NDEBUG
00556 }
00557
00558
00559
00560
00561
00562
00563
00564
00565
00566
00567
00568 void CHeapAllocator::initEmptyBlock (CMainBlock& mainBlock)
00569 {
00570
00571 CNodeBegin *node = getFirstNode (&mainBlock);
00572
00573
00574 internalAssert ((uint32)node - (uint32)mainBlock.Ptr >= 0);
00575 uint allocSize = mainBlock.Size - ((uint32)node - (uint32)mainBlock.Ptr);
00576
00577
00578
00579
00580 setNodeSize (node, allocSize-sizeof (CNodeBegin)-NL_HEAP_NODE_END_SIZE);
00581
00582
00583 setNodeFree (node);
00584
00585
00586 setNodeLast (node, true);
00587
00588
00589 node->Previous = NULL;
00590
00591
00592 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00593
00594 node->EndMagicNumber = (uint32*)((uint8*)node + getNodeSize (node) + sizeof (CNodeBegin));
00595
00596
00597 memset (node->BeginMarkers, BeginNodeMarkers, CNodeBegin::MarkerSize-1);
00598 node->BeginMarkers[CNodeBegin::MarkerSize-1] = 0;
00599
00600
00601 CNodeEnd *endNode = (CNodeEnd*)node->EndMagicNumber;
00602 memset (endNode->EndMarkers, EndNodeMarkers, CNodeEnd::MarkerSize-1);
00603 endNode->EndMarkers[CNodeEnd::MarkerSize-1] = 0;
00604
00605
00606 memset ((uint8*)node + sizeof(CNodeBegin), UnallocatedMemory, getNodeSize (node) );
00607
00608
00609 memset (node->Category, 0, CategoryStringLength);
00610 node->File = NULL;
00611 node->Line = 0xffff;
00612 node->AllocateNumber = 0xffffffff;
00613
00614
00615 node->Heap = this;
00616
00617 NL_UPDATE_MAGIC_NUMBER (node);
00618 #endif // NL_HEAP_ALLOCATION_NDEBUG
00619 }
00620
00621
00622
00623 uint CHeapAllocator::getBlockSize (void *block)
00624 {
00625
00626 CNodeBegin *node = (CNodeBegin*) ((uint)block - sizeof (CNodeBegin));
00627
00628 return getNodeSize (((CNodeBegin*) ((uint)block - sizeof (CNodeBegin))));
00629 }
00630
00631
00632
00633 #ifdef NL_HEAP_ALLOCATION_NDEBUG
00634 void *CHeapAllocator::allocate (uint size)
00635 #else // NL_HEAP_ALLOCATION_NDEBUG
00636 void *CHeapAllocator::allocate (uint size, const char *sourceFile, uint line, const char *category)
00637 #endif // NL_HEAP_ALLOCATION_NDEBUG
00638 {
00639
00640 if (size != 0)
00641 {
00642 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00643
00644 if (category == NULL)
00645 {
00646
00647 CCategory *cat = (CCategory*)_CategoryStack.getPointer ();
00648 if (cat)
00649 {
00650 category = cat->Name;
00651 }
00652 else
00653 {
00654
00655 category = NL_HEAP_UNKNOWN_CATEGORY;
00656 }
00657 }
00658
00659
00660 if (_AlwaysCheck)
00661 {
00662
00663 internalCheckHeap (true);
00664 }
00665
00666
00667
00668
00669
00670
00671
00672
00673
00674
00675
00676 #endif // NL_HEAP_ALLOCATION_NDEBUG
00677
00678
00679 #ifdef NL_HEAP_NO_SMALL_BLOCK_OPTIMIZATION
00680 if (0)
00681 #else // NL_HEAP_NO_SMALL_BLOCK_OPTIMIZATION
00682 if (size <= LastSmallBlock)
00683 #endif// NL_HEAP_NO_SMALL_BLOCK_OPTIMIZATION
00684 {
00685
00686
00687
00688
00689 enterCriticalSectionSB ();
00690
00691
00692 CNodeBegin **freeNode = (CNodeBegin **)_FreeSmallBlocks+NL_SIZE_TO_SMALLBLOCK_INDEX (size);
00693
00694
00695 if (*freeNode == NULL)
00696 {
00697 leaveCriticalSectionSB ();
00698
00699
00700 uint alignedSize = NL_ALIGN_SIZE_FOR_SMALLBLOCK (size);
00701
00702
00703 CSmallBlockPool *smallBlock = (CSmallBlockPool *)NelAlloc (*this, sizeof(CSmallBlockPool) + SmallBlockPoolSize * (sizeof(CNodeBegin) + alignedSize +
00704 NL_HEAP_NODE_END_SIZE), NL_HEAP_SB_CATEGORY);
00705
00706 enterCriticalSectionSB ();
00707
00708
00709 smallBlock->Size = alignedSize;
00710 smallBlock->Next = (CSmallBlockPool*)_SmallBlockPool;
00711 _SmallBlockPool = smallBlock;
00712
00713
00714 uint pool;
00715 CNodeBegin *nextNode = *freeNode;
00716 for (pool=0; pool<SmallBlockPoolSize; pool++)
00717 {
00718
00719 CNodeBegin *node = getSmallBlock (smallBlock, pool);
00720
00721
00722 node->SizeAndFlags = alignedSize;
00723
00724
00725 setNextSmallBlock (node, nextNode);
00726 nextNode = node;
00727
00728
00729 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00730
00731 setNodeFree (node);
00732
00733
00734 node->EndMagicNumber = (uint32*)(CNodeEnd*)((uint8*)node + getNodeSize (node) + sizeof (CNodeBegin));
00735
00736
00737 memset (node->BeginMarkers, BeginNodeMarkers, CNodeBegin::MarkerSize-1);
00738 node->BeginMarkers[CNodeBegin::MarkerSize-1] = 0;
00739
00740
00741 CNodeEnd *endNode = (CNodeEnd*)((uint8*)node + getNodeSize (node) + sizeof (CNodeBegin));
00742 memset (endNode->EndMarkers, EndNodeMarkers, CNodeEnd::MarkerSize-1);
00743 endNode->EndMarkers[CNodeEnd::MarkerSize-1] = 0;
00744
00745
00746 memset ((uint8*)node + sizeof(CNodeBegin), UnallocatedMemory, getNodeSize (node) );
00747
00748
00749 memset (node->Category, 0, CategoryStringLength);
00750 node->File = NULL;
00751 node->Line = 0xffff;
00752 node->AllocateNumber = 0xffffffff;
00753
00754
00755 node->Heap = this;
00756
00757 NL_UPDATE_MAGIC_NUMBER (node);
00758
00759 #endif // NL_HEAP_ALLOCATION_NDEBUG
00760 }
00761
00762
00763 *freeNode = nextNode;
00764 }
00765
00766
00767 internalAssert (*freeNode);
00768
00769
00770 CNodeBegin *node = *freeNode;
00771
00772
00773 internalAssert (size <= getNodeSize (node));
00774 internalAssert ((NL_SIZE_TO_SMALLBLOCK_INDEX (size)) < (NL_SMALLBLOCK_COUNT));
00775
00776
00777 *freeNode = getNextSmallBlock (node);
00778
00779 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00780
00781 checkNode (node, evalMagicNumber (node));
00782
00783
00784 setNodeUsed (node);
00785
00786
00787 strncpy (node->Category, category, CategoryStringLength-1);
00788
00789
00790 node->File = sourceFile;
00791
00792
00793 node->Line = line;
00794
00795
00796 node->AllocateNumber = _AllocateCount++;
00797
00798
00799 node->EndMagicNumber = (uint32*)((uint8*)node + size + sizeof (CNodeBegin));
00800
00801
00802 memset ((uint8*)node + sizeof(CNodeBegin), UninitializedMemory, (uint32)(node->EndMagicNumber) - ( (uint32)node + sizeof(CNodeBegin) ) );
00803
00804
00805 NL_UPDATE_MAGIC_NUMBER (node);
00806 #endif // NL_HEAP_ALLOCATION_NDEBUG
00807
00808 leaveCriticalSectionSB ();
00809
00810
00811 return (void*)((uint)node + sizeof (CNodeBegin));
00812 }
00813 else
00814 {
00815
00816
00817
00818
00819
00820 if ( (size & ~CNodeBegin::SizeMask) != 0)
00821 {
00822
00823
00824
00825
00826
00827 NL_ALLOC_STOP
00828
00829
00830 if (_OutOfMemoryMode == ReturnNull)
00831 return NULL;
00832 else
00833 throw 0;
00834 }
00835
00836 enterCriticalSectionLB ();
00837
00838
00839 CHeapAllocator::CFreeNode *freeNode = CHeapAllocator::find (size);
00840
00841
00842 CNodeBegin *node;
00843
00844
00845 if (freeNode == NULL)
00846 {
00847
00848 if ((_BlockAllocationMode == DontGrow) && (_MainBlockList != NULL))
00849 {
00850
00851 if (_OutOfMemoryMode == ReturnNull)
00852 return NULL;
00853 else
00854 throw 0;
00855 }
00856
00857
00858 uint8 *buffer;
00859
00860
00861 uint allocSize;
00862
00863
00864 uint allignedSize = (size&~(Align-1)) + (( (size&(Align-1))==0 ) ? 0 : Align);
00865 if (allignedSize < BlockDataSizeMin)
00866 allignedSize = BlockDataSizeMin;
00867
00868
00869 if (allignedSize > (_MainBlockSize-sizeof (CNodeBegin)-NL_HEAP_NODE_END_SIZE))
00870
00871 allocSize = allignedSize + sizeof (CNodeBegin) + NL_HEAP_NODE_END_SIZE;
00872 else
00873
00874 allocSize = _MainBlockSize;
00875
00876
00877 buffer = allocateBlock (allocSize+Align);
00878
00879
00880 CMainBlock *mainBlock = (CMainBlock*)allocateBlock (sizeof(CMainBlock));
00881 mainBlock->Size = allocSize+Align;
00882 mainBlock->Ptr = buffer;
00883 mainBlock->Next = _MainBlockList;
00884 _MainBlockList = mainBlock;
00885
00886
00887 initEmptyBlock (*mainBlock);
00888
00889
00890 node = getFirstNode (mainBlock);
00891 }
00892 else
00893 {
00894
00895 node = getNode (freeNode);
00896
00897
00898 erase (freeNode);
00899 }
00900
00901 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00902
00903 checkNode (node, evalMagicNumber (node));
00904 #endif // NL_HEAP_ALLOCATION_NDEBUG
00905
00906
00907 CNodeBegin *rest = splitNode (node, size);
00908
00909
00910
00911
00912 setNodeUsed (node);
00913
00914 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00915
00916 strncpy (node->Category, category, CategoryStringLength-1);
00917
00918
00919 node->File = sourceFile;
00920
00921
00922 node->Line = line;
00923
00924
00925 node->AllocateNumber = _AllocateCount++;
00926
00927
00928 NL_UPDATE_MAGIC_NUMBER (node);
00929
00930
00931 memset ((uint8*)node + sizeof(CNodeBegin), UninitializedMemory, (uint32)(node->EndMagicNumber) - ( (uint32)node + sizeof(CNodeBegin) ) );
00932 #endif // NL_HEAP_ALLOCATION_NDEBUG
00933
00934
00935 if (rest)
00936 {
00937
00938
00939
00940 freeNode = getFreeNode (rest);
00941
00942
00943 insert (freeNode);
00944
00945
00946 NL_UPDATE_MAGIC_NUMBER (rest);
00947 }
00948
00949
00950 internalAssert ( size <= getNodeSize (node) );
00951 internalAssert ( std::max ((uint)BlockDataSizeMin, size + (uint)Align) + sizeof (CNodeBegin) + sizeof (CNodeEnd) + sizeof (CNodeBegin) + sizeof (CNodeEnd) + BlockDataSizeMin >= getNodeSize (node) );
00952
00953
00954 internalAssert (((uint32)node&(Align-1)) == 0);
00955 internalAssert (((uint32)((char*)node + sizeof(CNodeBegin))&(Align-1)) == 0);
00956
00957
00958 internalAssert ((uint32)node->EndMagicNumber <= (uint32)((uint8*)node+sizeof(CNodeBegin)+getNodeSize (node) ));
00959 internalAssert ((uint32)node->EndMagicNumber > (uint32)(((uint8*)node+sizeof(CNodeBegin)+getNodeSize (node) ) - BlockDataSizeMin - BlockDataSizeMin - sizeof(CNodeBegin) - sizeof(CNodeEnd)));
00960
00961 leaveCriticalSectionLB ();
00962
00963
00964 return (void*)((uint)node + sizeof (CNodeBegin));
00965 }
00966 }
00967 else
00968 {
00969
00970
00971
00972
00973
00974 NL_ALLOC_STOP;
00975 return NULL;
00976 }
00977 }
00978
00979
00980
00981 void CHeapAllocator::free (void *ptr)
00982 {
00983
00984 if (ptr == NULL)
00985 {
00986
00987
00988
00989
00990
00991 #ifdef NL_HEAP_STOP_NULL_FREE
00992 NL_ALLOC_STOP;
00993 #endif // NL_HEAP_STOP_NULL_FREE
00994 }
00995 else
00996 {
00997 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00998
00999 if (_AlwaysCheck)
01000 {
01001
01002 internalCheckHeap (true);
01003 }
01004
01005
01006 CNodeBegin *node = (CNodeBegin*) ((uint)ptr - sizeof (CNodeBegin));
01007
01008
01009 enterCriticalSectionSB ();
01010 enterCriticalSectionLB ();
01011 checkNode (node, evalMagicNumber (node));
01012 leaveCriticalSectionLB ();
01013 leaveCriticalSectionSB ();
01014 #endif // NL_HEAP_ALLOCATION_NDEBUG
01015
01016
01017 #ifdef NL_HEAP_ALLOCATION_NDEBUG
01018 uint size = (((CNodeBegin*) ((uint)ptr - sizeof (CNodeBegin))))->SizeAndFlags;
01019 #else // NL_HEAP_ALLOCATION_NDEBUG
01020 uint size = getNodeSize (((CNodeBegin*) ((uint)ptr - sizeof (CNodeBegin))));
01021 #endif // NL_HEAP_ALLOCATION_NDEBUG
01022 if (size <= LastSmallBlock)
01023 {
01024
01025
01026
01027
01028
01029 if (isNodeFree (node))
01030 {
01031
01032
01033
01034
01035
01036
01037
01038 NL_ALLOC_STOP;
01039 }
01040 else
01041 {
01042 enterCriticalSectionSB ();
01043
01044 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01045
01046 memset ((uint8*)node + sizeof(CNodeBegin), DeletedMemory, size );
01047
01048
01049 node->EndMagicNumber = (uint32*)((uint8*)node + size + sizeof (CNodeBegin));
01050
01051
01052 setNodeFree (node);
01053 #endif // NL_HEAP_ALLOCATION_NDEBUG
01054
01055
01056 CNodeBegin **freeNode = (CNodeBegin **)_FreeSmallBlocks+NL_SIZE_TO_SMALLBLOCK_INDEX (size);
01057 ((CNodeBegin*) ((uint)ptr - sizeof (CNodeBegin)))->Previous = *freeNode;
01058 *freeNode = ((CNodeBegin*) ((uint)ptr - sizeof (CNodeBegin)));
01059
01060
01061 NL_UPDATE_MAGIC_NUMBER (node);
01062
01063 leaveCriticalSectionSB ();
01064 }
01065 }
01066 else
01067 {
01068 #ifdef NL_HEAP_ALLOCATION_NDEBUG
01069
01070 size = getNodeSize (((CNodeBegin*) ((uint)ptr - sizeof (CNodeBegin))));
01071 #endif // NL_HEAP_ALLOCATION_NDEBUG
01072
01073
01074 CNodeBegin *node = (CNodeBegin*) ((uint)ptr - sizeof (CNodeBegin));
01075
01076
01077 if (isNodeFree (node))
01078 {
01079
01080
01081
01082
01083
01084
01085
01086 NL_ALLOC_STOP;
01087 }
01088 else
01089 {
01090 enterCriticalSectionLB ();
01091
01092 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01093
01094 memset ((uint8*)node + sizeof(CNodeBegin), DeletedMemory, size );
01095
01096
01097 node->EndMagicNumber = (uint32*)((uint8*)node + size + sizeof (CNodeBegin));
01098 #endif // NL_HEAP_ALLOCATION_NDEBUG
01099
01100
01101 setNodeFree (node);
01102
01103
01104
01105
01106
01107
01108 CHeapAllocator::CFreeNode *freeNode = NULL;
01109
01110
01111 CNodeBegin *previous = node->Previous;
01112 if (previous)
01113 {
01114 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01115
01116 checkNode (previous, evalMagicNumber (previous));
01117 #endif // NL_HEAP_ALLOCATION_NDEBUG
01118
01119
01120 if (isNodeFree (previous))
01121 {
01122
01123 mergeNode (node);
01124
01125
01126 erase (getFreeNode (previous));
01127
01128
01129 node = previous;
01130 }
01131 }
01132
01133
01134 setNodeFree (node);
01135
01136
01137 CNodeBegin *next = getNextNode (node);
01138 if (next)
01139 {
01140 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01141
01142 checkNode (next, evalMagicNumber (next));
01143 #endif // NL_HEAP_ALLOCATION_NDEBUG
01144
01145
01146 if (isNodeFree (next))
01147 {
01148
01149 erase (getFreeNode (next));
01150
01151
01152 mergeNode (next);
01153 }
01154 }
01155
01156
01157 insert (getFreeNode (node));
01158
01159 NL_UPDATE_MAGIC_NUMBER (node);
01160
01161 leaveCriticalSectionLB ();
01162 }
01163 }
01164 }
01165 }
01166
01167
01168
01169
01170
01171 uint CHeapAllocator::getAllocatedMemory () const
01172 {
01173 enterCriticalSection ();
01174
01175
01176 uint memory = 0;
01177
01178
01179 CSmallBlockPool *currentSB = (CSmallBlockPool *)_SmallBlockPool;
01180 while (currentSB)
01181 {
01182
01183 uint block;
01184 for (block=0; block<SmallBlockPoolSize; block++)
01185 {
01186
01187 const CNodeBegin *current = getSmallBlock (currentSB, block);
01188
01189
01190 if (isNodeUsed (current))
01191 memory += getNodeSize (current) + ReleaseHeaderSize;
01192 }
01193
01194
01195 currentSB = currentSB->Next;
01196 }
01197
01198
01199 CMainBlock *currentBlock = _MainBlockList;
01200 while (currentBlock)
01201 {
01202
01203 const CNodeBegin *current = getFirstNode (currentBlock);
01204 while (current)
01205 {
01206 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01207
01208 checkNode (current, evalMagicNumber (current));
01209 #endif // NL_HEAP_ALLOCATION_NDEBUG
01210
01211
01212 if (isNodeUsed (current) && (strcmp (current->Category, NL_HEAP_SB_CATEGORY) != 0))
01213 memory += getNodeSize (current) + ReleaseHeaderSize;
01214
01215
01216 current = getNextNode (current);
01217 }
01218
01219
01220 currentBlock = currentBlock->Next;
01221 }
01222
01223 leaveCriticalSection ();
01224
01225
01226 return memory;
01227 }
01228
01229
01230
01231 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01232 uint CHeapAllocator::debugGetAllocatedMemoryByCategory (const char* category) const
01233 {
01234 enterCriticalSection ();
01235
01236
01237 uint memory = 0;
01238
01239
01240 CSmallBlockPool *currentSB = (CSmallBlockPool *)_SmallBlockPool;
01241 while (currentSB)
01242 {
01243
01244 uint block;
01245 for (block=0; block<SmallBlockPoolSize; block++)
01246 {
01247
01248 const CNodeBegin *current = getSmallBlock (currentSB, block);
01249
01250
01251 if ((isNodeUsed (current)) && (strcmp (current->Category, category)==0))
01252 memory += getNodeSize (current);
01253
01254 memory += getNodeSize (current);
01255 }
01256
01257
01258 currentSB = currentSB->Next;
01259 }
01260
01261
01262 CMainBlock *currentBlock = _MainBlockList;
01263 while (currentBlock)
01264 {
01265
01266 const CNodeBegin *current = getFirstNode (currentBlock);
01267 while (current)
01268 {
01269
01270 if ((isNodeUsed (current)) && (strcmp (current->Category, category)==0))
01271 memory += getNodeSize (current);
01272
01273
01274 current = getNextNode (current);
01275 }
01276
01277
01278 currentBlock = currentBlock->Next;
01279 }
01280
01281 leaveCriticalSection ();
01282
01283
01284 return memory;
01285 }
01286 #endif // NL_HEAP_ALLOCATION_NDEBUG
01287
01288
01289
01290 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01291 uint CHeapAllocator::debugGetDebugInfoSize () const
01292 {
01293
01294 return debugGetSBDebugInfoSize () + debugGetLBDebugInfoSize ();
01295 }
01296
01297 uint CHeapAllocator::debugGetLBDebugInfoSize () const
01298 {
01299 enterCriticalSection ();
01300
01301
01302 uint memory = 0;
01303
01304
01305 CMainBlock *currentBlock = _MainBlockList;
01306 while (currentBlock)
01307 {
01308
01309 const CNodeBegin *current = getFirstNode (currentBlock);
01310 while (current)
01311 {
01312
01313 memory += sizeof(CNodeBegin) - ReleaseHeaderSize + sizeof(CNodeEnd);
01314
01315
01316 current = getNextNode (current);
01317 }
01318
01319
01320 currentBlock = currentBlock->Next;
01321 }
01322
01323 leaveCriticalSection ();
01324
01325
01326 return memory;
01327 }
01328
01329 uint CHeapAllocator::debugGetSBDebugInfoSize () const
01330 {
01331 enterCriticalSection ();
01332
01333
01334 uint memory = 0;
01335
01336
01337 CSmallBlockPool *pool = (CSmallBlockPool*)_SmallBlockPool;
01338 while (pool)
01339 {
01340 memory += SmallBlockPoolSize * (sizeof(CNodeBegin) - ReleaseHeaderSize + sizeof(CNodeEnd));
01341
01342
01343 pool = pool->Next;
01344 }
01345
01346 leaveCriticalSection ();
01347
01348
01349 return memory;
01350 }
01351 #endif // NL_HEAP_ALLOCATION_NDEBUG
01352
01353
01354
01355 void fprintf_int (uint value)
01356 {
01357
01358 }
01359
01360
01361
01362 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01363
01364 class CCategoryMap
01365 {
01366 public:
01367 CCategoryMap (const char *name, CCategoryMap *next)
01368 {
01369 Name = name;
01370 BlockCount = 0;
01371 Size = 0;
01372 Min = 0xffffffff;
01373 Max = 0;
01374 Next = next;
01375 }
01376
01377 static CCategoryMap *find (CCategoryMap *cat, const char *name)
01378 {
01379 while (cat)
01380 {
01381 if (strcmp (name, cat->Name) == 0)
01382 break;
01383 cat = cat->Next;
01384 }
01385 return cat;
01386 }
01387
01388 static CCategoryMap *insert (const char *name, CCategoryMap *next)
01389 {
01390 return new CCategoryMap (name, next);
01391 }
01392
01393 const char *Name;
01394 uint BlockCount;
01395 uint Size;
01396 uint Min;
01397 uint Max;
01398 CCategoryMap *Next;
01399 };
01400
01401 bool CHeapAllocator::debugStatisticsReport (const char* stateFile, bool memoryMap)
01402 {
01403
01404 bool status = false;
01405
01406 debugPushCategoryString (NL_HEAP_MEM_DEBUG_CATEGORY);
01407
01408
01409 FILE *file = fopen (stateFile, "wt");
01410
01411
01412 CCategoryMap *catMap = NULL;
01413
01414
01415 if (file)
01416 {
01417
01418
01419
01420 uint smallBlockCount = 0;
01421 uint largeBlockCount = 0;
01422 CSmallBlockPool *currentSB = (CSmallBlockPool *)_SmallBlockPool;
01423 while (currentSB)
01424 {
01425
01426 uint block;
01427 for (block=0; block<SmallBlockPoolSize; block++)
01428 {
01429
01430 const CNodeBegin *current = getSmallBlock (currentSB, block);
01431
01432
01433 if (isNodeUsed (current))
01434 {
01435
01436 CCategoryMap *cat = CCategoryMap::find (catMap, (const char*)current->Category);
01437
01438
01439 if (cat == NULL)
01440 {
01441 catMap = CCategoryMap::insert (current->Category, catMap);
01442 cat = catMap;
01443 }
01444 uint size = getNodeSize (current) + ReleaseHeaderSize;
01445 cat->BlockCount++;
01446 cat->Size += size;
01447 if (size < cat->Min)
01448 cat->Min = size;
01449 if (size > cat->Max)
01450 cat->Max = size;
01451 }
01452
01453
01454 smallBlockCount++;
01455 }
01456
01457
01458 currentSB = currentSB->Next;
01459 }
01460
01461
01462 CMainBlock *currentBlock = _MainBlockList;
01463 while (currentBlock)
01464 {
01465
01466 const CNodeBegin *current = getFirstNode (currentBlock);
01467 while (current)
01468 {
01469
01470 if (isNodeUsed (current))
01471 {
01472
01473 CCategoryMap *cat = CCategoryMap::find (catMap, (const char*)current->Category);
01474
01475
01476 if (cat == NULL)
01477 {
01478 catMap = CCategoryMap::insert (current->Category, catMap);
01479 cat = catMap;
01480 }
01481 uint size = getNodeSize (current) + ReleaseHeaderSize;
01482 cat->BlockCount++;
01483 cat->Size += size;
01484 if (size < cat->Min)
01485 cat->Min = size;
01486 if (size > cat->Max)
01487 cat->Max = size;
01488 }
01489
01490
01491 current = getNextNode (current);
01492 largeBlockCount++;
01493 }
01494
01495
01496 currentBlock = currentBlock->Next;
01497 }
01498
01499
01500 fprintf (file, "HEAP STATISTICS\n");
01501 fprintf (file, "HEAP, TOTAL MEMORY USED, ALLOCATED MEMORY, FREE MEMORY, FRAGMENTATION RATIO, MAIN BLOCK SIZE, MAIN BLOCK COUNT\n");
01502
01503 fprintf (file, "%s, %d, %d, %d, %f%%, %d, %d\n", _Name, getTotalMemoryUsed (),
01504 getAllocatedMemory (), getFreeMemory (), 100.f*getFragmentationRatio (), getMainBlockSize (), getMainBlockCount ());
01505
01506 fprintf (file, "\n\nHEAP BLOCKS\n");
01507 fprintf (file, "SMALL BLOCK MEMORY, SMALL BLOCK COUNT, LARGE BLOCK COUNT\n");
01508
01509 fprintf (file, "%d, %d, %d\n", getSmallBlockMemory (), smallBlockCount, largeBlockCount);
01510
01511 fprintf (file, "\n\nHEAP DEBUG INFOS\n");
01512 fprintf (file, "SB DEBUG INFO, LB DEBUG INFO, TOTAL DEBUG INFO\n");
01513
01514 fprintf (file, "%d, %d, %d\n", debugGetSBDebugInfoSize (), debugGetLBDebugInfoSize (), debugGetDebugInfoSize ());
01515
01516
01517
01518
01519 uint systemMemory = getAllocatedSystemMemory ();
01520 uint nelSystemMemory = getAllocatedSystemMemoryByAllocator ();
01521
01522 fprintf (file, "\n\nSYSTEM HEAP STATISTICS\n");
01523 fprintf (file, "TOTAL ALLOCATED MEMORY, NEL ALLOCATED MEMORY, OTHER ALLOCATED MEMORY\n");
01524 fprintf (file, "%d, %d, %d\n", systemMemory, nelSystemMemory, systemMemory-nelSystemMemory);
01525
01526
01527 fprintf (file, "\n\n\nCATEGORY STATISTICS\n");
01528 fprintf (file, "CATEGORY, BLOCK COUNT, MEMORY ALLOCATED, MIN BLOCK SIZE, MAX BLOCK SIZE, AVERAGE BLOCK SIZE, SB COUNT 8, SB COUNT 16, SB COUNT 24, SB COUNT 32, SB COUNT 40, SB COUNT 48, SB COUNT 56, SB COUNT 64, SB COUNT 72, SB COUNT 80, SB COUNT 88, SB COUNT 96, SB COUNT 104, SB COUNT 112, SB COUNT 120, SB COUNT 128\n");
01529
01530 CCategoryMap *cat = catMap;
01531 while (cat)
01532 {
01533 CCategoryMap *next = cat->Next;
01534
01535
01536 uint smallB[NL_SMALLBLOCK_COUNT];
01537
01538
01539 uint smallBlock;
01540 for (smallBlock=0; smallBlock<NL_SMALLBLOCK_COUNT; smallBlock++)
01541 {
01542 smallB[smallBlock] = 0;
01543 }
01544
01545
01546 currentSB = (CSmallBlockPool *)_SmallBlockPool;
01547 while (currentSB)
01548 {
01549
01550 uint block;
01551 for (block=0; block<SmallBlockPoolSize; block++)
01552 {
01553
01554 const CNodeBegin *current = getSmallBlock (currentSB, block);
01555
01556
01557 if (isNodeUsed (current))
01558 {
01559
01560 if (strcmp (current->Category, cat->Name) == 0)
01561 {
01562
01563 uint index = NL_SIZE_TO_SMALLBLOCK_INDEX (getNodeSize (current));
01564
01565
01566 smallB[index]++;
01567 }
01568 }
01569 }
01570
01571
01572 currentSB = currentSB->Next;
01573 }
01574
01575
01576 uint average = cat->Size / cat->BlockCount;
01577
01578
01579 fprintf (file, "%s, %d, %d, %d, %d, %d", cat->Name, cat->BlockCount, cat->Size,
01580 cat->Min, cat->Max, average);
01581
01582
01583 for (smallBlock=0; smallBlock<NL_SMALLBLOCK_COUNT; smallBlock++)
01584 {
01585 fprintf (file, ", %d", smallB[smallBlock]);
01586 }
01587
01588 fprintf (file, "\n");
01589
01590 delete cat;
01591 cat = next;
01592 }
01593
01594
01595
01596
01597 fprintf (file, "\n\n\nSMALL BLOCK STATISTICS\n");
01598 fprintf (file, "SIZE, BLOCK COUNT, BLOCK FREE, BLOCK USED, TOTAL MEMORY USED\n");
01599
01600
01601 uint count[NL_SMALLBLOCK_COUNT];
01602 uint free[NL_SMALLBLOCK_COUNT];
01603
01604 uint smallBlock;
01605 for (smallBlock=0; smallBlock<NL_SMALLBLOCK_COUNT; smallBlock++)
01606 {
01607 count[smallBlock] = 0;
01608 free[smallBlock] = 0;
01609 }
01610
01611
01612 currentSB = (CSmallBlockPool *)_SmallBlockPool;
01613 while (currentSB)
01614 {
01615
01616 uint block;
01617 for (block=0; block<SmallBlockPoolSize; block++)
01618 {
01619
01620 const CNodeBegin *current = getSmallBlock (currentSB, block);
01621
01622
01623 uint index = NL_SIZE_TO_SMALLBLOCK_INDEX (getNodeSize (current));
01624
01625
01626 count[index]++;
01627
01628
01629 if (isNodeFree (current))
01630 {
01631
01632 free[index]++;
01633 }
01634
01635
01636 current = getNextNode (current);
01637 }
01638
01639
01640 currentSB = currentSB->Next;
01641 }
01642
01643
01644 for (smallBlock=0; smallBlock<NL_SMALLBLOCK_COUNT; smallBlock++)
01645 {
01646 uint size = (smallBlock+1)*SmallBlockGranularity;
01647 fprintf (file,"%d, %d, %d, %d, %d\n",size, count[smallBlock], free[smallBlock],
01648 count[smallBlock]-free[smallBlock], count[smallBlock]*(sizeof (CNodeBegin) + size + NL_HEAP_NODE_END_SIZE));
01649 }
01650
01651
01652
01653
01654 if (memoryMap)
01655 {
01656 fprintf (file, "\n\n\nHEAP LARGE BLOCK DUMP\n");
01657 fprintf (file, "ADDRESS, SIZE, CATEGORY, HEAP, STATE, SOURCE, LINE\n");
01658
01659
01660 currentBlock = _MainBlockList;
01661 while (currentBlock)
01662 {
01663
01664 const CNodeBegin *current = getFirstNode (currentBlock);
01665 while (current)
01666 {
01667
01668 fprintf (file, "0x%08x, %d, %s, %s, %s, %s, %d\n", (uint)current + sizeof(CNodeBegin),
01669 getNodeSize (current), current->Category, _Name,
01670 isNodeFree (current)?"free":"used", current->File, current->Line);
01671
01672
01673 current = getNextNode (current);
01674 }
01675
01676
01677 currentBlock = currentBlock->Next;
01678 }
01679 }
01680
01681
01682 status = true;
01683 }
01684
01685
01686 if (file)
01687 fclose (file);
01688
01689 debugPopCategoryString ();
01690
01691 return status;
01692 }
01693 #endif // NL_HEAP_ALLOCATION_NDEBUG
01694
01695
01696
01697 uint CHeapAllocator::getFreeMemory () const
01698 {
01699 enterCriticalSection ();
01700
01701
01702 uint memory = 0;
01703
01704
01705 CSmallBlockPool *currentSB = (CSmallBlockPool *)_SmallBlockPool;
01706 while (currentSB)
01707 {
01708
01709 uint block;
01710 for (block=0; block<SmallBlockPoolSize; block++)
01711 {
01712
01713 const CNodeBegin *current = getSmallBlock (currentSB, block);
01714
01715
01716 if (isNodeFree (current))
01717 memory += getNodeSize (current) + ReleaseHeaderSize;
01718
01719
01720 current = getNextNode (current);
01721 }
01722
01723
01724 currentSB = currentSB->Next;
01725 }
01726
01727
01728 CMainBlock *currentBlock = _MainBlockList;
01729 while (currentBlock)
01730 {
01731
01732 const CNodeBegin *current = getFirstNode (currentBlock);
01733 while (current)
01734 {
01735 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01736
01737 checkNode (current, evalMagicNumber (current));
01738 #endif // NL_HEAP_ALLOCATION_NDEBUG
01739
01740
01741 if (isNodeFree (current))
01742 memory += getNodeSize (current) + ReleaseHeaderSize;
01743
01744
01745 current = getNextNode (current);
01746 }
01747
01748
01749 currentBlock = currentBlock->Next;
01750 }
01751
01752 leaveCriticalSection ();
01753
01754
01755 return memory;
01756 }
01757
01758
01759
01760 uint CHeapAllocator::getTotalMemoryUsed () const
01761 {
01762 enterCriticalSection ();
01763
01764
01765 uint memory = 0;
01766
01767
01768 CMainBlock *currentBlock = _MainBlockList;
01769 while (currentBlock)
01770 {
01771
01772 memory += currentBlock->Size;
01773
01774
01775 memory += sizeof (CMainBlock);
01776
01777
01778 currentBlock = currentBlock->Next;
01779 }
01780
01781 leaveCriticalSection ();
01782
01783
01784 return memory;
01785 }
01786
01787
01788
01789 uint CHeapAllocator::getSmallBlockMemory () const
01790 {
01791 enterCriticalSection ();
01792
01793
01794 uint memory = 0;
01795
01796
01797 CSmallBlockPool *currentSB = (CSmallBlockPool *)_SmallBlockPool;
01798 while (currentSB)
01799 {
01800
01801 memory += sizeof(CSmallBlockPool) + SmallBlockPoolSize * (sizeof(CNodeBegin) + currentSB->Size +
01802 NL_HEAP_NODE_END_SIZE);
01803
01804
01805 currentSB = currentSB->Next;
01806 }
01807
01808 leaveCriticalSection ();
01809
01810
01811 return memory;
01812 }
01813
01814
01815
01816 float CHeapAllocator::getFragmentationRatio () const
01817 {
01818 enterCriticalSection ();
01819
01820
01821 float free = 0;
01822 float used = 0;
01823
01824
01825 CMainBlock *currentBlock = _MainBlockList;
01826 while (currentBlock)
01827 {
01828
01829 const CNodeBegin *current = getFirstNode (currentBlock);
01830 while (current)
01831 {
01832
01833 if (isNodeUsed (current))
01834 used++;
01835 else
01836 free++;
01837
01838
01839 current = getNextNode (current);
01840 }
01841
01842
01843 currentBlock = currentBlock->Next;
01844 }
01845
01846 leaveCriticalSection ();
01847
01848
01849 if (used != 0)
01850 return free / used;
01851 else
01852 return 0;
01853 }
01854
01855
01856
01857 void CHeapAllocator::freeAll ()
01858 {
01859 enterCriticalSection ();
01860
01861
01862 uint memory = 0;
01863
01864
01865 _FreeTreeRoot = &_NullNode.FreeNode;
01866
01867
01868 CMainBlock *currentBlock = _MainBlockList;
01869 while (currentBlock)
01870 {
01871
01872 initEmptyBlock (*currentBlock);
01873
01874
01875 CNodeBegin *node = getFirstNode (currentBlock);
01876
01877
01878 insert (getFreeNode (node));
01879
01880 NL_UPDATE_MAGIC_NUMBER (node);
01881
01882
01883 currentBlock = currentBlock->Next;
01884 }
01885
01886 leaveCriticalSection ();
01887 }
01888
01889
01890
01891 void CHeapAllocator::releaseMemory ()
01892 {
01893 enterCriticalSection ();
01894
01895
01896 _FreeTreeRoot = &_NullNode.FreeNode;
01897
01898
01899 CMainBlock *currentBlock = _MainBlockList;
01900 while (currentBlock)
01901 {
01902 freeBlock (currentBlock->Ptr);
01903
01904
01905 CMainBlock *toDelete = currentBlock;
01906 currentBlock = toDelete->Next;
01907 ::free (toDelete);
01908 }
01909
01910
01911 _MainBlockList = NULL;
01912
01913 leaveCriticalSection ();
01914 }
01915
01916
01917
01918 #ifndef NL_HEAP_ALLOCATION_NDEBUG
01919
01920 class CLeak
01921 {
01922 public:
01923
01924 CLeak (const char *name, CLeak *next)
01925 {
01926 Name = new char[strlen (name)+1];
01927 strcpy (Name, name);
01928 Count = 0;
01929 Memory = 0;
01930 Next = next;
01931 }
01932
01933 ~CLeak ()
01934 {
01935 delete [] Name;
01936 if (Next)
01937 delete Next;
01938 }
01939
01940 static CLeak *find (CLeak *cat, const char *name)
01941 {
01942 while (cat)
01943 {
01944 if (strcmp (name, cat->Name) == 0)
01945 break;
01946 cat = cat->Next;
01947 }
01948 return cat;
01949 }
01950
01951 static CLeak *insert (const char *name, CLeak *next)
01952 {
01953 return new CLeak (name, next);
01954 }
01955
01956 uint Count;
01957 uint Memory;
01958 char *Name;
01959 CLeak *Next;
01960 };
01961
01962
01963
01964 void CHeapAllocator::debugReportMemoryLeak ()
01965 {
01966 debugPushCategoryString (NL_HEAP_MEM_DEBUG_CATEGORY);
01967
01968
01969 uint memory = 0;
01970
01971
01972 CLeak *leakMap = NULL;
01973
01974
01975 char report[2048];
01976 sprintf (report, "Report Memory leak for allocator \"%s\"\n", _Name);
01977 CHeapAllocatorOutputError (report);
01978
01979
01980 CMainBlock *currentBlock = _MainBlockList;
01981 while (currentBlock)
01982 {
01983
01984 const CNodeBegin *current = getFirstNode (currentBlock);
01985 while (current)
01986 {
01987
01988 checkNode (current, evalMagicNumber (current));
01989
01990
01991 if (isNodeUsed (current) && ( (current->Category == NULL) || (current->Category[0] != '_')) )
01992 {
01993
01994 sprintf (report, "%s(%d)\t: \"%s\"", current->File, current->Line, current->Category);
01995
01996
01997 CLeak *ite = CLeak::find (leakMap, report);
01998
01999
02000 if (ite == NULL)
02001 {
02002 ite = CLeak::insert (report, leakMap);
02003 leakMap = ite;
02004 ite->Count = 0;
02005 ite->Memory = 0;
02006 }
02007
02008
02009 ite->Count++;
02010 ite->Memory += getNodeSize (current);
02011
02012 memory += getNodeSize (current);
02013 }
02014
02015
02016 current = getNextNode (current);
02017 }
02018
02019
02020 currentBlock = currentBlock->Next;
02021 }
02022
02023
02024 CSmallBlockPool *currentSB = (CSmallBlockPool *)_SmallBlockPool;
02025 while (currentSB)
02026 {
02027
02028 uint block;
02029 for (block=0; block<SmallBlockPoolSize; block++)
02030 {
02031
02032 const CNodeBegin *current = getSmallBlock (currentSB, block);
02033
02034 checkNode (current, evalMagicNumber (current));
02035
02036
02037 if (isNodeUsed (current) && ( (current->Category == NULL) || (current->Category[0] != '_')) )
02038 {
02039
02040 sprintf (report, "%s(%d)\t: \"%s\"", current->File, current->Line, current->Category);
02041
02042
02043 CLeak *ite = CLeak::find (leakMap, report);
02044
02045
02046 if (ite == NULL)
02047 {
02048 ite = CLeak::insert (report, leakMap);
02049 leakMap = ite;
02050 ite->Count = 0;
02051 ite->Memory = 0;
02052 }
02053
02054
02055 ite->Count++;
02056 ite->Memory += getNodeSize (current);
02057
02058 memory += getNodeSize (current);
02059 }
02060 }
02061
02062
02063 currentSB = currentSB->Next;
02064 }
02065
02066
02067 CLeak *ite = leakMap;
02068 while (ite)
02069 {
02070
02071 sprintf (report, "%s,\tLeak count : %d,\tMemory allocated : %d\n", ite->Name, ite->Count, ite->Memory);
02072
02073
02074 CHeapAllocatorOutputError (report);
02075
02076 ite = ite->Next;
02077 }
02078
02079
02080 if (memory)
02081 {
02082 sprintf (report, "%d byte(s) found\n", memory);
02083 }
02084 else
02085 {
02086 sprintf (report, "No memory leak\n");
02087 }
02088 CHeapAllocatorOutputError (report);
02089
02090
02091 if (leakMap)
02092 delete leakMap;
02093
02094 debugPopCategoryString ();
02095 }
02096 #endif // NL_HEAP_ALLOCATION_NDEBUG
02097
02098
02099
02100 bool CHeapAllocator::checkHeap (bool stopOnError) const
02101 {
02102 bool res = internalCheckHeap (stopOnError);
02103
02104 return res;
02105 }
02106
02107
02108
02109 uint8 *CHeapAllocator::allocateBlock (uint size)
02110 {
02111 #undef malloc
02112 return (uint8*)::malloc (size);
02113 }
02114
02115
02116
02117 void CHeapAllocator::freeBlock (uint8 *block)
02118 {
02119 ::free (block);
02120 }
02121
02122
02123
02124 bool CHeapAllocator::internalCheckHeap (bool stopOnError) const
02125 {
02126 enterCriticalSection ();
02127
02128
02129 CSmallBlockPool *pool = (CSmallBlockPool*)_SmallBlockPool;
02130 while (pool)
02131 {
02132
02133 uint smallBlock;
02134 CNodeBegin *previous = NULL;
02135 for (smallBlock=0; smallBlock<SmallBlockPoolSize; smallBlock++)
02136 {
02137
02138 CNodeBegin *node = getSmallBlock (pool, smallBlock);
02139 CNodeBegin *next = (smallBlock+1<SmallBlockPoolSize) ? getSmallBlock (pool, smallBlock+1) : NULL;
02140
02141
02142 checkNodeSB (pool, previous, node, next, stopOnError);
02143
02144 previous = node;
02145 }
02146
02147
02148 pool = pool->Next;
02149 }
02150
02151
02152 CMainBlock *currentBlock = _MainBlockList;
02153 while (currentBlock)
02154 {
02155
02156 const CNodeBegin *previous = NULL;
02157 const CNodeBegin *current = getFirstNode (currentBlock);
02158 internalAssert (current);
02159 const CNodeBegin *next;
02160
02161
02162 while (current)
02163 {
02164
02165 next = getNextNode (current);
02166
02167
02168 if (!checkNodeLB (currentBlock, previous, current, next, stopOnError))
02169 return false;
02170
02171
02172 previous = current;
02173 current = next;
02174 }
02175
02176
02177 currentBlock = currentBlock->Next;
02178 }
02179
02180
02181 if (!checkFreeNode (_FreeTreeRoot, stopOnError, true))
02182 return false;
02183
02184 leaveCriticalSection ();
02185
02186
02187 return true;
02188 }
02189
02190
02191
02192 #ifndef NL_HEAP_ALLOCATION_NDEBUG
02193 void CHeapAllocator::debugAlwaysCheckMemory (bool alwaysCheck)
02194 {
02195 _AlwaysCheck = alwaysCheck;
02196 }
02197 #endif // NL_HEAP_ALLOCATION_NDEBUG
02198
02199
02200
02201 #ifndef NL_HEAP_ALLOCATION_NDEBUG
02202 bool CHeapAllocator::debugIsAlwaysCheckMemory (bool alwaysCheck) const
02203 {
02204 return _AlwaysCheck;
02205 }
02206 #endif // NL_HEAP_ALLOCATION_NDEBUG
02207
02208
02209
02210 void CHeapAllocator::setName (const char* name)
02211 {
02212 enterCriticalSection ();
02213
02214 strncpy (_Name, name, NameLength-1);
02215
02216 leaveCriticalSection ();
02217 }
02218
02219
02220
02221
02222
02223 void CHeapAllocator::debugPushCategoryString (const char *str)
02224 {
02225
02226 CCategory *last = (CCategory*)_CategoryStack.getPointer ();
02227
02228
02229 CCategory *_new = (CCategory *)NelAlloc (*this, sizeof(CCategory), NL_HEAP_CATEGORY_BLOCK_CATEGORY);
02230 _new->Name = str;
02231 _new->Next = last;
02232
02233
02234 _CategoryStack.setPointer (_new);
02235 }
02236
02237
02238
02239 void CHeapAllocator::debugPopCategoryString ()
02240 {
02241
02242 CCategory *last = (CCategory*)_CategoryStack.getPointer ();
02243
02244 if (last)
02245 {
02246 CCategory *next = last->Next;
02247
02248
02249 free (last);
02250
02251
02252 _CategoryStack.setPointer (next);
02253 }
02254 }
02255
02256
02257
02258 #ifndef NL_HEAP_ALLOCATION_NDEBUG
02259
02260 #ifdef NL_OS_WINDOWS
02261 #pragma optimize( "", off )
02262 #endif // NL_OS_WINDOWS
02263
02264 void CHeapAllocator::checkNode (const CNodeBegin *node, uint32 crc) const
02265 {
02266
02267 if (crc != *(node->EndMagicNumber))
02268 {
02269
02270
02271
02272
02273
02274
02275
02276 NL_ALLOC_STOP;
02277 }
02278
02279
02280 if (node->Heap != this)
02281 {
02282
02283
02284
02285
02286
02287
02288
02289 NL_ALLOC_STOP;
02290 }
02291 }
02292
02293 #ifdef NL_OS_WINDOWS
02294 #pragma optimize( "", on )
02295 #endif // NL_OS_WINDOWS
02296
02297 #endif // NL_HEAP_ALLOCATION_NDEBUG
02298
02299
02300
02301 uint CHeapAllocator::getAllocatedSystemMemory ()
02302 {
02303 uint systemMemory = 0;
02304 #ifdef NL_OS_WINDOWS
02305
02306 HANDLE hHeap[100];
02307 DWORD heapCount = GetProcessHeaps (100, hHeap);
02308
02309 uint heap;
02310 for (heap = 0; heap < heapCount; heap++)
02311 {
02312 PROCESS_HEAP_ENTRY entry;
02313 entry.lpData = NULL;
02314 while (HeapWalk (hHeap[heap], &entry))
02315 {
02316 if (entry.wFlags & PROCESS_HEAP_ENTRY_BUSY)
02317 {
02318 systemMemory += entry.cbData + entry.cbOverhead;
02319 }
02320 }
02321 }
02322 #endif // NL_OS_WINDOWS
02323 return systemMemory;
02324 }
02325
02326
02327
02328 class CPointerEntry
02329 {
02330 public:
02331 CPointerEntry (void *pointer, CPointerEntry *entry)
02332 {
02333 Pointer = pointer;
02334 Next = entry;
02335 }
02336 static CPointerEntry *find (CPointerEntry *cat, void *pointer)
02337 {
02338 while (cat)
02339 {
02340 if (pointer == cat->Pointer)
02341 break;
02342 cat = cat->Next;
02343 }
02344 return cat;
02345 }
02346 void *Pointer;
02347 CPointerEntry *Next;
02348 };
02349
02350 uint CHeapAllocator::getAllocatedSystemMemoryByAllocator ()
02351 {
02352 uint nelSystemMemory = 0;
02353
02354
02355 CPointerEntry *entries = NULL;
02356
02357
02358 CMainBlock *currentBlock = _MainBlockList;
02359 while (currentBlock)
02360 {
02361
02362 entries = new CPointerEntry ((void*)currentBlock, entries);
02363 entries = new CPointerEntry ((void*)currentBlock->Ptr, entries);
02364
02365
02366 currentBlock = currentBlock->Next;
02367 }
02368
02369 #ifdef NL_OS_WINDOWS
02370
02371 HANDLE hHeap[100];
02372 DWORD heapCount = GetProcessHeaps (100, hHeap);
02373
02374 uint heap;
02375 for (heap = 0; heap < heapCount; heap++)
02376 {
02377 PROCESS_HEAP_ENTRY entry;
02378 entry.lpData = NULL;
02379 while (HeapWalk (hHeap[heap], &entry))
02380 {
02381 if (entry.wFlags & PROCESS_HEAP_ENTRY_BUSY)
02382 {
02383
02384 if ( CPointerEntry::find (entries, (void*)((char*)entry.lpData)) ||
02385 CPointerEntry::find (entries, (void*)((char*)entry.lpData+32) ) )
02386 nelSystemMemory += entry.cbData + entry.cbOverhead;
02387 }
02388 }
02389 }
02390 #endif // NL_OS_WINDOWS
02391
02392 return nelSystemMemory;
02393 }
02394
02395
02396
02397 }