nevrax.org : docs

00001 
+00007 /* Copyright, 2001 Nevrax Ltd.
+00008  *
+00009  * This file is part of NEVRAX NEL.
+00010  * NEVRAX NEL is free software; you can redistribute it and/or modify
+00011  * it under the terms of the GNU General Public License as published by
+00012  * the Free Software Foundation; either version 2, or (at your option)
+00013  * any later version.
+00014 
+00015  * NEVRAX NEL is distributed in the hope that it will be useful, but
+00016  * WITHOUT ANY WARRANTY; without even the implied warranty of
+00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+00018  * General Public License for more details.
+00019 
+00020  * You should have received a copy of the GNU General Public License
+00021  * along with NEVRAX NEL; see the file COPYING. If not, write to the
+00022  * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+00023  * MA 02111-1307, USA.
+00024  */
+00025 
+00026 #ifndef NL_HEAP_ALLOCATOR_H
+00027 #define NL_HEAP_ALLOCATOR_H
+00028 
+00029 /* 
+00030  * Include "nel/misc/types_nl.h" but don't redefine new
+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 // Define this to disable debug features (use to trace buffer overflow and add debug informations in memory headers)
+00044 // #define NL_HEAP_ALLOCATION_NDEBUG
+00045 
+00046 // Define this to activate internal checks (use to debug the heap code)
+00047 // #define NL_HEAP_ALLOCATOR_INTERNAL_CHECKS
+00048 
+00049 // Define this to disable small block optimizations
+00050 //#define NL_HEAP_NO_SMALL_BLOCK_OPTIMIZATION
+00051 
+00052 // Stop when free a NULL pointer
+00053 //#define NL_HEAP_STOP_NULL_FREE
+00054 
+00055 // Mutex to use with the allocator
+00056 typedef CFastMutex CAllocatorMutex;                     // Not fair, non-system, using sleep(), but very fast
+00057 //typedef CFairMutex CAllocatorMutex;           // Fair, fastest system mutex under Windows
+00058 //typedef CUnfairMutex CAllocatorMutex;         // Unfair, slowest system mutex under Windows
+00059 
+00061 
+00062 /*
+00063  * A heap allocator with a lot of functionnality.
+00064  * Used by the NeL memory manager as default allocator.
+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         // Constructor / Destructor
+00123         CHeapAllocator (        uint mainBlockSize=1024*1024*10, 
+00124                         uint blockCount=1, 
+00125                         TBlockAllocationMode blockAllocationMode = Grow, 
+00126                         TOutOfMemoryMode outOfMemoryMode = ThrowException );
+00127         virtual ~CHeapAllocator ();
+00128 
+00129         // Allocation / desallocation
+00130 #ifndef NL_HEAP_ALLOCATION_NDEBUG
+00131         /* Use the NelAlloc macro */
+00132         void                                    *allocate (uint size, const char *sourceFile, uint line, const char *category);
+00133         /* Use the NelRealloc macro */
+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         // Return an allocated block size
+00144         static uint                             getBlockSize (void *block);
+00145 
+00146         // Performance control
+00147 
+00148         // Returns false if the block size choosed i too big (>= 1 Go)
+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         // Heap control
+00159         bool                                    checkHeap (bool stopOnError) const;
+00160 
+00161         uint                                    getAllocatedMemory () const;
+00162 
+00163         /* Return the amount of free memoyr available in the allocator */
+00164         uint                                    getFreeMemory () const;
+00165 
+00166         /* Return the total amount of memory allocated by the allocator */
+00167         uint                                    getTotalMemoryUsed () const;
+00168 
+00169         /* Return the amount of memory used by the small block optimisation */
+00170         uint                                    getSmallBlockMemory () const;
+00171 
+00172         /* Return the amount of allocated system memory */
+00173         static uint                             getAllocatedSystemMemory ();
+00174 
+00175         /* Return the amount of allocated system memory used by the allocator */
+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 /*      void                                    debugAddBreakpoint (uint32 allocateNumber);
+00184         void                                    debugRemoveBreakpoints ();*/
+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         // Heap debug
+00194         void                                    debugReportMemoryLeak ();
+00195 
+00196 #endif // NL_HEAP_ALLOCATION_NDEBUG
+00197 
+00198         // Overridable
+00199         virtual uint8                   *allocateBlock (uint size);
+00200         virtual void                    freeBlock (uint8 *block);
+00201 
+00202 private:
+00203 
+00204         // Constants for freeNode block size
+00205         enum 
+00206         { 
+00207                 FreeNodeBlockSize = 128, 
+00208                 FreeNodeBlockSizeShift = 7, 
+00209                 FreeNodeBlockSizeMask = 0x7f 
+00210         };
+00211 
+00212         // Minimal size and align
+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                 // Flags for the memory node
+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;                                                           // Source line number
+00245                 char            Category[CategoryStringLength];         // Category name
+00246                 const char      *File;                                                          // Source file name pointer
+00247                 CHeapAllocator          *Heap;                                          // Heap holder of this node
+00248                 uint32          *EndMagicNumber;                                        // Pointer on the end magic number
+00249                 uint32          AllocateNumber;                                         // Align structure to 80 bytes
+00250 #endif // NL_HEAP_ALLOCATION_NDEBUG
+00251 
+00252                 uint32          SizeAndFlags;                                           // Size of the user memory zone of 30 bits (1 Go max), and 2 flags (Free/Used and LastBlock)
+00253                 CNodeBegin      *Previous;                                                      // Previous node in large block mode / Small block pointer in small block mode
+00254         };
+00255 
+00256 #ifndef NL_HEAP_ALLOCATION_NDEBUG
+00257         struct CNodeEnd
+00258         {
+00259                 enum    
+00260                 { 
+00261                         MarkerSize=4
+00262                 };
+00263 
+00264                 uint32          MagicNumber;                                            // CRC32 of the node pointer and the node header. Can be move backward to fit the data
+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         /* Integrity check of a single node. Called at each allocation / deallocation when NL_HEAP_ALLOCATION_NDEBUG is not defined.
+00314            Call it inside a critical section. */
+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         // Manage freeNode
+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         // Manage blocks
+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         // Checks
+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         // Performe full integrity check of the heap, free list and smallblock. Call it outside critical sections.
+00358         bool                            internalCheckHeap (bool stopOnError) const;
+00359 
+00360         // Synchronisation
+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         // The Null node
+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         // List of main block.
+00384         CMainBlock                                      *_MainBlockList;
+00385 
+00386         // Members
+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         // std::set<uint32>                     _Breakpoints;
+00395 #endif // NL_HEAP_ALLOCATION_NDEBUG
+00396 
+00397         // *********************************************************
+00398 
+00400 
+00401 public:
+00402         // Small block size
+00403         enum
+00404         {
+00405                 // Small block granularity
+00406                 SmallBlockGranularityShift = 3,
+00407 
+00408                 // Small block granularity
+00409                 SmallBlockGranularity = 1<<SmallBlockGranularityShift,
+00410 
+00411                 // Smallest block size
+00412                 FirstSmallBlock = 8,
+00413 
+00414                 // Largest block size
+00415                 LastSmallBlock = 128,
+00416 
+00417                 // Size of a smallblock pool
+00418                 SmallBlockPoolSize = 20
+00419         };
+00420 
+00421         struct CSmallBlockPool
+00422         {
+00423         public:
+00424                 uint32                          Size;
+00425                 CSmallBlockPool         *Next;
+00426         };
+00427 
+00428 private:
+00429 
+00430         // Some internal methods
+00431 
+00432         /* Integrity check of a single node. Called at each allocation / deallocation when NL_HEAP_ALLOCATION_NDEBUG is not defined.
+00433            Call it inside a critical section. */
+00434         bool            checkNodeSB (const CSmallBlockPool *mainBlock, const CNodeBegin *previous, const CNodeBegin *current, 
+00435                 const CNodeBegin *next, bool stopOnError) const;
+00436 
+00437         // Get a block from a small block
+00438         static CNodeBegin       *getSmallBlock (CSmallBlockPool *smallBlock, uint blockIndex);
+00439 
+00440         // Get next free small block
+00441         static CNodeBegin       *getNextSmallBlock (CNodeBegin *previous);
+00442 
+00443         // Set next free small block
+00444         static void                     setNextSmallBlock (CNodeBegin *previous, CNodeBegin *next);
+00445 
+00446         // Some macros
+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         // The free smallblock array by size
+00452         volatile CNodeBegin                     *_FreeSmallBlocks[NL_SMALLBLOCK_COUNT];
+00453         volatile CSmallBlockPool        *_SmallBlockPool;
+00454 
+00455         mutable CAllocatorMutex         _MutexSB;
+00456 
+00457         // *********************************************************
+00458 
+00460 public:
+00461 
+00462         /* Push the category string. Add the string at the top of the category string stack. The string str must be a static pointer.
+00463          * There is one stack per thread. */
+00464         void    debugPushCategoryString (const char *str);
+00465 
+00466         // Remove the last pushed category string from the category stack
+00467         void    debugPopCategoryString ();
+00468 
+00469 private:
+00470 
+00471         /* Struct for the category stack */
+00472         struct CCategory
+00473         {
+00474                 const char      *Name;
+00475                 CCategory       *Next;
+00476         };
+00477 
+00478         /* Thread dependant storage of category stack */
+00479         CTDS    _CategoryStack;
+00480 };
+00481 
+00483 
+00484 /* Heap macro */
+00485 #ifdef  NL_HEAP_ALLOCATION_NDEBUG
+00486 
+00487 /* NelAlloc: category can be NULL. Then, category string will be the last pushed category string. */
+00488 #define NelAlloc(heap,size,category) ((heap).allocate (size))
+00489 
+00490 /* NelRealloc: category can be NULL. Then, category string will be the last pushed category string. */
+00491 #define NelRealloc(heap,size,ptr,category) (heap.allocate (ptr, size))
+00492 
+00493 #else // NL_HEAP_ALLOCATION_NDEBUG
+00494 
+00495 /* NelAlloc: category can be NULL. Then, category string will be the last pushed category string. */
+00496 #define NelAlloc(heap,size,category) ((heap).allocate (size, __FILE__, __LINE__, category))
+00497 
+00498 /* NelRealloc: category can be NULL. Then, category string will be the last pushed category string. */
+00499 #define NelRealloc(heap,size,ptr,category) (heap.allocate (ptr, size, __FILE__, __LINE__, category))
+00500 
+00501 #endif  //NL_HEAP_ALLOCATION_NDEBUG
+00502 
+00503 } // NLMISC 
+00504 
+00505 #endif // NL_HEAP_ALLOCATOR_H
+
heap_allocator.h
