00001
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #ifndef NL_HEAP_ALLOCATOR_H
00027 #define NL_HEAP_ALLOCATOR_H
00028
00029
00030
00031
00032 #include "nel/misc/types_nl.h"
00033 #include "nel/misc/mutex.h"
00034 #include "nel/misc/tds.h"
00035
00036 #include <vector>
00037
00038 namespace NLMISC
00039 {
00040
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056 typedef CFastMutex CAllocatorMutex;
00057
00058
00059
00061
00062
00063
00064
00065
00066 class CHeapAllocator
00067 {
00068 public:
00069
00070 enum
00071 {
00072 ReleaseHeaderSize = 8,
00073 CategoryStringLength = 8,
00074 BeginNodeMarkers = '<',
00075 EndNodeMarkers = '>',
00076 UnallocatedMemory = 0xba,
00077 UninitializedMemory = 0xbc,
00078 DeletedMemory = 0xbd,
00079 NameLength = 32
00080 };
00081
00085 enum TBlockAllocationMode
00086 {
00088 Grow,
00089
00091 DontGrow
00092 };
00093
00097 enum TOutOfMemoryMode
00098 {
00100 ThrowException,
00101
00103 ReturnNull
00104 };
00105
00106 typedef char TCategoryString[CategoryStringLength];
00107
00108 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00109
00110 struct CMemoryLeakBlock
00111 {
00112 public:
00113 void *Adress;
00114 uint BlockSize;
00115 const char *SourceFile;
00116 uint Line;
00117 TCategoryString Category;
00118 };
00119
00120 #endif // NL_HEAP_ALLOCATION_NDEBUG
00121
00122
00123 CHeapAllocator ( uint mainBlockSize=1024*1024*10,
00124 uint blockCount=1,
00125 TBlockAllocationMode blockAllocationMode = Grow,
00126 TOutOfMemoryMode outOfMemoryMode = ThrowException );
00127 virtual ~CHeapAllocator ();
00128
00129
00130 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00131
00132 void *allocate (uint size, const char *sourceFile, uint line, const char *category);
00133
00134 void *reallocate (void *ptr, uint size, const char *sourceFile, uint line, const char *category);
00135 #else // NL_HEAP_ALLOCATION_NDEBUG
00136 void *allocate (uint size);
00137 void *realloc (void *ptr, uint size);
00138 #endif // NL_HEAP_ALLOCATION_NDEBUG
00139 void free (void *ptr);
00140 void freeAll ();
00141 void releaseMemory ();
00142
00143
00144 static uint getBlockSize (void *block);
00145
00146
00147
00148
00149 bool setMainBlockSize (uint mainBlockSize);
00150 uint getMainBlockSize () const;
00151 bool setMainBlockCount (uint blockCount);
00152 uint getMainBlockCount () const;
00153 void setBlockAllocationMode (TBlockAllocationMode mode);
00154 TBlockAllocationMode getBlockAllocationMode () const;
00155 void setOutOfMemoryMode (TOutOfMemoryMode mode);
00156 TOutOfMemoryMode getOutOfMemoryMode () const;
00157
00158
00159 bool checkHeap (bool stopOnError) const;
00160
00161 uint getAllocatedMemory () const;
00162
00163
00164 uint getFreeMemory () const;
00165
00166
00167 uint getTotalMemoryUsed () const;
00168
00169
00170 uint getSmallBlockMemory () const;
00171
00172
00173 static uint getAllocatedSystemMemory ();
00174
00175
00176 uint getAllocatedSystemMemoryByAllocator ();
00177
00178 float getFragmentationRatio () const;
00179 void setName (const char* name);
00180 const char *getName () const;
00181
00182 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00183
00184
00185 uint debugGetDebugInfoSize () const;
00186 uint debugGetSBDebugInfoSize () const;
00187 uint debugGetLBDebugInfoSize () const;
00188 uint debugGetAllocatedMemoryByCategory (const char* category) const;
00189 bool debugStatisticsReport (const char* stateFile, bool memoryMap);
00190 void debugAlwaysCheckMemory (bool alwaysCheck);
00191 bool debugIsAlwaysCheckMemory (bool alwaysCheck) const;
00192
00193
00194 void debugReportMemoryLeak ();
00195
00196 #endif // NL_HEAP_ALLOCATION_NDEBUG
00197
00198
00199 virtual uint8 *allocateBlock (uint size);
00200 virtual void freeBlock (uint8 *block);
00201
00202 private:
00203
00204
00205 enum
00206 {
00207 FreeNodeBlockSize = 128,
00208 FreeNodeBlockSizeShift = 7,
00209 FreeNodeBlockSizeMask = 0x7f
00210 };
00211
00212
00213 enum
00214 {
00215 Align = 8,
00216 BlockDataSizeMin = 1<<4
00217 };
00218
00219 struct CNodeBegin;
00220
00221 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00222 struct CNodeEnd;
00223 #endif // NL_HEAP_ALLOCATION_NDEBUG
00224
00225 struct CFreeNode;
00226
00227 struct CNodeBegin
00228 {
00229 enum
00230 {
00231 MarkerSize=6
00232 };
00233
00234
00235 enum
00236 {
00237 Free=0x40000000,
00238 Last=0x80000000,
00239 SizeMask=0x3fffffff,
00240 };
00241
00242 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00243 char BeginMarkers[MarkerSize];
00244 uint16 Line;
00245 char Category[CategoryStringLength];
00246 const char *File;
00247 CHeapAllocator *Heap;
00248 uint32 *EndMagicNumber;
00249 uint32 AllocateNumber;
00250 #endif // NL_HEAP_ALLOCATION_NDEBUG
00251
00252 uint32 SizeAndFlags;
00253 CNodeBegin *Previous;
00254 };
00255
00256 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00257 struct CNodeEnd
00258 {
00259 enum
00260 {
00261 MarkerSize=4
00262 };
00263
00264 uint32 MagicNumber;
00265 char EndMarkers[MarkerSize];
00266 };
00267 #endif // NL_HEAP_ALLOCATION_NDEBUG
00268
00269 #ifdef NL_HEAP_ALLOCATION_NDEBUG
00270
00271 #define NL_HEAP_NODE_END_SIZE 0
00272
00273 #else // NL_HEAP_ALLOCATION_NDEBUG
00274
00275 #define NL_HEAP_NODE_END_SIZE sizeof(CNodeEnd)
00276
00277 #endif // NL_HEAP_ALLOCATION_NDEBUG
00278
00279 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00280 static uint32 evalMagicNumber (const CNodeBegin *node);
00281 #endif // NL_HEAP_ALLOCATION_NDEBUG
00282 static const CNodeBegin *getNextNode (const CNodeBegin *current);
00283 static CNodeBegin *getNextNode (CNodeBegin *current);
00284 static const CFreeNode *getFreeNode (const CNodeBegin *current);
00285 static CFreeNode *getFreeNode (CNodeBegin *current);
00286 static const CNodeBegin *getNode (const CFreeNode *current);
00287 static CNodeBegin *getNode (CFreeNode *current);
00288 static uint getNodeSize (const CNodeBegin *current);
00289 static bool isNodeFree (const CNodeBegin *current);
00290 static bool isNodeUsed (const CNodeBegin *current);
00291 static bool isNodeLast (const CNodeBegin *current);
00292 static bool isNodeSmall (const CNodeBegin *current);
00293 static bool isNodeRed (const CFreeNode *current);
00294 static bool isNodeBlack (const CFreeNode *current);
00295 static void setNodeFree (CNodeBegin *current);
00296 static void setNodeUsed (CNodeBegin *current);
00297 static void setNodeLast (CNodeBegin *current, bool last);
00298 static void setNodeSize (CNodeBegin *current, uint size);
00299 static void setNodeColor (CFreeNode *current, bool red);
00300 static void setNodeRed (CFreeNode *current);
00301 static void setNodeBlack (CFreeNode *current);
00302
00303 struct CMainBlock
00304 {
00305 uint Size;
00306 uint8 *Ptr;
00307 CMainBlock *Next;
00308 };
00309
00310 static const CNodeBegin *getFirstNode (const CMainBlock *mainBlock);
00311 static CNodeBegin *getFirstNode (CMainBlock *mainBlock);
00312
00313
00314
00315 bool checkNodeLB (const CMainBlock *mainBlock, const CNodeBegin *previous,
00316 const CNodeBegin *current, const CNodeBegin *next, bool stopOnError) const;
00317
00318 struct CFreeNode
00319 {
00320 enum
00321 {
00322 Red = 1
00323 };
00324 CFreeNode *Left;
00325 CFreeNode *Right;
00326 CFreeNode *Parent;
00327 uint32 Flags;
00328 };
00329
00330 enum
00331 {
00332 UserDataBlockSizeMin = sizeof(CFreeNode)
00333 };
00334
00335
00336 inline void rotateLeft (CFreeNode *x);
00337 inline void rotateRight (CFreeNode *x);
00338 inline void insert (CFreeNode *x);
00339 inline void erase (CFreeNode *z);
00340 inline CFreeNode *find (uint size);
00341
00342
00343 inline static void mergeNode (CNodeBegin *node);
00344 inline CNodeBegin *splitNode (CNodeBegin *node, uint newSize);
00345 inline void initEmptyBlock (CMainBlock& mainBlock);
00346
00347 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00348 inline static void computeCRC32 (uint32 &crc, const void* buffer, unsigned int count);
00349 #endif // NL_HEAP_ALLOCATION_NDEBUG
00350
00351
00352 bool checkFreeNode (const CFreeNode *current, bool stopOnError, bool recurse) const;
00353 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00354 void checkNode (const CNodeBegin *current, uint32 crc) const;
00355 #endif // NL_HEAP_ALLOCATION_NDEBUG
00356
00357
00358 bool internalCheckHeap (bool stopOnError) const;
00359
00360
00361 void enterCriticalSection () const;
00362 void leaveCriticalSection () const;
00363 void enterCriticalSectionSB () const;
00364 void leaveCriticalSectionSB () const;
00365 void enterCriticalSectionLB () const;
00366 void leaveCriticalSectionLB () const;
00367
00368
00369 struct CNullNode
00370 {
00371 uint8 NodeBeginBuffer[sizeof(CNodeBegin)];
00372 CFreeNode FreeNode;
00373 };
00374
00375 uint _MainBlockSize;
00376 uint _BlockCount;
00377 TBlockAllocationMode _BlockAllocationMode;
00378 TOutOfMemoryMode _OutOfMemoryMode;
00379 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00380 bool _AlwaysCheck;
00381 #endif // NL_HEAP_ALLOCATION_NDEBUG
00382
00383
00384 CMainBlock *_MainBlockList;
00385
00386
00387 CFreeNode *_FreeTreeRoot;
00388 CNullNode _NullNode;
00389 mutable CAllocatorMutex _MutexLB;
00390
00391 char _Name[NameLength];
00392 #ifndef NL_HEAP_ALLOCATION_NDEBUG
00393 uint32 _AllocateCount;
00394
00395 #endif // NL_HEAP_ALLOCATION_NDEBUG
00396
00397
00398
00400
00401 public:
00402
00403 enum
00404 {
00405
00406 SmallBlockGranularityShift = 3,
00407
00408
00409 SmallBlockGranularity = 1<<SmallBlockGranularityShift,
00410
00411
00412 FirstSmallBlock = 8,
00413
00414
00415 LastSmallBlock = 128,
00416
00417
00418 SmallBlockPoolSize = 20
00419 };
00420
00421 struct CSmallBlockPool
00422 {
00423 public:
00424 uint32 Size;
00425 CSmallBlockPool *Next;
00426 };
00427
00428 private:
00429
00430
00431
00432
00433
00434 bool checkNodeSB (const CSmallBlockPool *mainBlock, const CNodeBegin *previous, const CNodeBegin *current,
00435 const CNodeBegin *next, bool stopOnError) const;
00436
00437
00438 static CNodeBegin *getSmallBlock (CSmallBlockPool *smallBlock, uint blockIndex);
00439
00440
00441 static CNodeBegin *getNextSmallBlock (CNodeBegin *previous);
00442
00443
00444 static void setNextSmallBlock (CNodeBegin *previous, CNodeBegin *next);
00445
00446
00447 #define NL_SMALLBLOCK_COUNT (1+(LastSmallBlock - FirstSmallBlock)/SmallBlockGranularity)
00448 #define NL_SIZE_TO_SMALLBLOCK_INDEX(size) ((size-1)>>SmallBlockGranularityShift)
00449 #define NL_ALIGN_SIZE_FOR_SMALLBLOCK(size) (((size) + SmallBlockGranularity-1) & ~(SmallBlockGranularity-1))
00450
00451
00452 volatile CNodeBegin *_FreeSmallBlocks[NL_SMALLBLOCK_COUNT];
00453 volatile CSmallBlockPool *_SmallBlockPool;
00454
00455 mutable CAllocatorMutex _MutexSB;
00456
00457
00458
00460 public:
00461
00462
00463
00464 void debugPushCategoryString (const char *str);
00465
00466
00467 void debugPopCategoryString ();
00468
00469 private:
00470
00471
00472 struct CCategory
00473 {
00474 const char *Name;
00475 CCategory *Next;
00476 };
00477
00478
00479 CTDS _CategoryStack;
00480 };
00481
00483
00484
00485 #ifdef NL_HEAP_ALLOCATION_NDEBUG
00486
00487
00488 #define NelAlloc(heap,size,category) ((heap).allocate (size))
00489
00490
00491 #define NelRealloc(heap,size,ptr,category) (heap.allocate (ptr, size))
00492
00493 #else // NL_HEAP_ALLOCATION_NDEBUG
00494
00495
00496 #define NelAlloc(heap,size,category) ((heap).allocate (size, __FILE__, __LINE__, category))
00497
00498
00499 #define NelRealloc(heap,size,ptr,category) (heap.allocate (ptr, size, __FILE__, __LINE__, category))
00500
00501 #endif //NL_HEAP_ALLOCATION_NDEBUG
00502
00503 }
00504
00505 #endif // NL_HEAP_ALLOCATOR_H