# Home    # nevrax.com   
Nevrax
Nevrax.org
#News
#Mailing-list
#Documentation
#CVS
#Bugs
#License
Docs
 
Documentation  
Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Related Pages   Search  

heap_allocator.h

Go to the documentation of this file.
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