src/NCollection/NCollection_IncAllocator.cxx

   1 // Created on: 2002-04-12
   2 // Created by: Alexander GRIGORIEV
   3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 #include <NCollection_IncAllocator.hxx>
  17 #include <NCollection_DataMap.hxx>
  18 #include <NCollection_Map.hxx>
  19 #include <Standard_Mutex.hxx>
  20 #include <Standard_OutOfMemory.hxx>
  21 #include <stdio.h>
  22 #include <fstream>
  23 #include <iomanip>
  24
  25 IMPLEMENT_STANDARD_HANDLE  (NCollection_IncAllocator,NCollection_BaseAllocator)
  26 IMPLEMENT_STANDARD_RTTIEXT (NCollection_IncAllocator,NCollection_BaseAllocator)
  27
  28 namespace
  29 {
  30
  31   inline size_t IMEM_SIZE (const size_t theSize)
  32   {
  33     return (theSize - 1) / sizeof(NCollection_IncAllocator::aligned_t) + 1;
  34   }
  35
  36   inline size_t IMEM_ALIGN (const void* theAddress)
  37   {
  38     return sizeof(NCollection_IncAllocator::aligned_t) * IMEM_SIZE (size_t(theAddress));
  39   }
  40
  41   #define IMEM_FREE(p_bl) (size_t(p_bl->p_end_block - p_bl->p_free_space))
  42
  43 #ifdef OCCT_DEBUG
  44   // auxiliary dummy function used to get a place where break point can be set
  45   inline void place_for_breakpoint() {}
  46 #endif
  47 }
  48
  49 #define MaxLookup 16
  50
  51 static Standard_Boolean IS_DEBUG = Standard_False;
  52
  53 //=======================================================================
  54 /**
  55  * Static data map (address -> AllocatorID)
  56  */
  57 //=======================================================================
  58 static NCollection_DataMap<Standard_Address, Standard_Size>& StorageIDMap()
  59 {
  60   static NCollection_DataMap<Standard_Address, Standard_Size> TheMap;
  61   return TheMap;
  62 }
  63
  64 //=======================================================================
  65 /**
  66  * Static map (AllocatorID)
  67  */
  68 //=======================================================================
  69 static NCollection_Map<Standard_Size>& StorageIDSet()
  70 {
  71   static NCollection_Map<Standard_Size> TheMap;
  72   return TheMap;
  73 }
  74
  75 //=======================================================================
  76 //function : IncAllocator_SetDebugFlag
  77 //purpose  : Turn on/off debugging of memory allocation
  78 //=======================================================================
  79
  80 Standard_EXPORT void IncAllocator_SetDebugFlag(const Standard_Boolean theDebug)
  81 {
  82   IS_DEBUG = theDebug;
  83 }
  84
  85 #ifdef OCCT_DEBUG
  86
  87 //=======================================================================
  88 /**
  89  * Static value of the current allocation ID. It provides unique
  90  * numbering of allocators.
  91  */
  92 //=======================================================================
  93 static Standard_Size CurrentID = 0;
  94 static Standard_Size CATCH_ID = 0;
  95
  96 //=======================================================================
  97 //function : Debug_Create
  98 //purpose  : Store the allocator address in the internal maps
  99 //=======================================================================
 100
 101 static void Debug_Create(Standard_Address theAlloc)
 102 {
 103   static Standard_Mutex aMutex;
 104   aMutex.Lock();
 105   StorageIDMap().Bind(theAlloc, ++CurrentID);
 106   StorageIDSet().Add(CurrentID);
 107   if (CurrentID == CATCH_ID)
 108     place_for_breakpoint();
 109   aMutex.Unlock();
 110 }
 111
 112 //=======================================================================
 113 //function : Debug_Destroy
 114 //purpose  : Forget the allocator address from the internal maps
 115 //=======================================================================
 116
 117 static void Debug_Destroy(Standard_Address theAlloc)
 118 {
 119   static Standard_Mutex aMutex;
 120   aMutex.Lock();
 121   if (StorageIDMap().IsBound(theAlloc))
 122   {
 123     Standard_Size anID = StorageIDMap()(theAlloc);
 124     StorageIDSet().Remove(anID);
 125     StorageIDMap().UnBind(theAlloc);
 126   }
 127   aMutex.Unlock();
 128 }
 129
 130 #endif /* OCCT_DEBUG */
 131
 132 //=======================================================================
 133 //function : IncAllocator_PrintAlive
 134 //purpose  : Outputs the alive numbers to the file inc_alive.d
 135 //=======================================================================
 136
 137 Standard_EXPORT void IncAllocator_PrintAlive()
 138 {
 139   if (StorageIDSet().IsEmpty())
 140   {
 141     return;
 142   }
 143
 144   std::ofstream aFileOut ("inc_alive.d", std::ios_base::trunc | std::ios_base::out);
 145   if (!aFileOut.is_open())
 146   {
 147     std::cout << "failure writing file inc_alive.d" << std::endl;
 148     return;
 149   }
 150   aFileOut.imbue (std::locale ("C"));
 151   aFileOut << std::fixed << std::setprecision(1);
 152
 153   aFileOut << "Alive IncAllocators (number, size in Kb)\n";
 154   Standard_Size    aTotSize = 0;
 155   Standard_Integer nbAlloc  = 0;
 156   for (NCollection_DataMap<Standard_Address, Standard_Size>::Iterator itMap (StorageIDMap());
 157        itMap.More(); itMap.Next())
 158   {
 159     const NCollection_IncAllocator* anAlloc = static_cast<NCollection_IncAllocator*>(itMap.Key());
 160     Standard_Size anID  = itMap.Value();
 161     Standard_Size aSize = anAlloc->GetMemSize();
 162     aTotSize += aSize;
 163     nbAlloc++;
 164     aFileOut << std::setw(20) << anID << ' '
 165              << std::setw(20) << (double(aSize) / 1024.0)
 166              << '\n';
 167   }
 168   aFileOut << "Total:\n"
 169            << std::setw(20) << nbAlloc << ' '
 170            << std::setw(20) << (double(aTotSize) / 1024.0)
 171            << '\n';
 172   aFileOut.close();
 173 }
 174
 175 //=======================================================================
 176 //function : NCollection_IncAllocator()
 177 //purpose  : Constructor
 178 //=======================================================================
 179
 180 NCollection_IncAllocator::NCollection_IncAllocator (const size_t theBlockSize)
 181 {
 182 #ifdef ALLOC_TRACK_USAGE
 183   printf ("\n..NCollection_IncAllocator: Created (%x)\n",this);
 184 #endif
 185 #ifdef OCCT_DEBUG
 186   if (IS_DEBUG)
 187     Debug_Create(this);
 188 #endif
 189   const size_t aDefault = DefaultBlockSize;
 190   const size_t aSize = IMEM_SIZE(sizeof(IBlock)) +
 191       IMEM_SIZE((theBlockSize > 2*sizeof(IBlock)) ? theBlockSize : aDefault);
 192   IBlock * const aBlock = (IBlock *) malloc (aSize * sizeof(aligned_t));
 193   myFirstBlock = aBlock;
 194   mySize = aSize - IMEM_SIZE(sizeof(IBlock));
 195   myMemSize = aSize * sizeof(aligned_t);
 196   if (aBlock == NULL)
 197     Standard_OutOfMemory::Raise("NCollection_IncAllocator: out of memory");
 198   aBlock -> p_free_space = (aligned_t *) IMEM_ALIGN (&aBlock[1]);
 199   aBlock -> p_end_block  = ((aligned_t *) aBlock) + aSize;
 200   aBlock -> p_next       = NULL;
 201 }
 202
 203 //=======================================================================
 204 //function : ~NCollection_IncAllocator
 205 //purpose  : Destructor
 206 //=======================================================================
 207
 208 NCollection_IncAllocator::~NCollection_IncAllocator ()
 209 {
 210 #ifdef OCCT_DEBUG
 211   if (IS_DEBUG)
 212     Debug_Destroy(this);
 213 #endif
 214   Clean();
 215   free (myFirstBlock);
 216 }
 217
 218 //=======================================================================
 219 //function : Allocate
 220 //purpose  : allocate a memory
 221 //remark   : returns NULL if allocation fails
 222 //=======================================================================
 223
 224 void * NCollection_IncAllocator::Allocate (const size_t aSize)
 225 {
 226   aligned_t * aResult = NULL;
 227   const size_t cSize = aSize ? IMEM_SIZE(aSize) : 0;
 228
 229   if (cSize > mySize) {
 230     /* If the requested size exceeds normal allocation size, allocate
 231        a separate block and place it as the head of the list              */
 232     aResult = (aligned_t *) allocateNewBlock (cSize+1);
 233     if (aResult)
 234       myFirstBlock -> p_free_space = myFirstBlock -> p_end_block;
 235     else
 236       Standard_OutOfMemory::Raise("NCollection_IncAllocator: out of memory");
 237   } else
 238     if (cSize <= IMEM_FREE(myFirstBlock)) {
 239       /* If the requested size fits into the free space in the 1st block  */
 240       aResult = myFirstBlock -> allocateInBlock (cSize);
 241     } else {
 242       /* Search for a block in the list with enough free space            */
 243       int aMaxLookup = MaxLookup;   /* limit the number of blocks to query */
 244       IBlock * aCurrentBlock = myFirstBlock -> p_next;
 245       while (aCurrentBlock && aMaxLookup--) {
 246         if (cSize <= IMEM_FREE(aCurrentBlock)) {
 247           aResult = aCurrentBlock -> allocateInBlock (cSize);
 248           break;
 249         }
 250         aCurrentBlock = aCurrentBlock -> p_next;
 251       }
 252       if (aResult == NULL) {
 253         /* There is no available block with enough free space. Create a new
 254            one and place it in the head of the list                       */
 255         aResult = (aligned_t *) allocateNewBlock (mySize);
 256         if (aResult)
 257           myFirstBlock -> p_free_space = aResult + cSize;
 258         else
 259         {
 260           const size_t aDefault = IMEM_SIZE(DefaultBlockSize);
 261           if (cSize > aDefault)
 262               Standard_OutOfMemory::Raise("NCollection_IncAllocator: out of memory");
 263           else
 264           {
 265             aResult = (aligned_t *) allocateNewBlock (aDefault);
 266             if (aResult)
 267               myFirstBlock -> p_free_space = aResult + cSize;
 268             else
 269               Standard_OutOfMemory::Raise("NCollection_IncAllocator: out of memory");
 270           }
 271         }
 272       }
 273     }
 274   return aResult;
 275 }
 276
 277 //=======================================================================
 278 //function : Reallocate
 279 //purpose  :
 280 //=======================================================================
 281
 282 void * NCollection_IncAllocator::Reallocate (void         * theAddress,
 283                                              const size_t oldSize,
 284                                              const size_t newSize)
 285 {
 286 // Check that the dummy parameters are OK
 287   if (theAddress == NULL || oldSize == 0)
 288     return Allocate (newSize);
 289   const size_t cOldSize = IMEM_SIZE(oldSize);
 290   const size_t cNewSize = newSize ? IMEM_SIZE(newSize) : 0;
 291   aligned_t * anAddress = (aligned_t *) theAddress;
 292
 293 // We check only the LAST allocation to do the real extension/contraction
 294   if (anAddress + cOldSize == myFirstBlock -> p_free_space) {
 295     myFirstBlock -> p_free_space = anAddress;
 296 // If the new size fits into the memory block => OK
 297 // This also includes any case of contraction
 298     if (cNewSize <= IMEM_FREE(myFirstBlock)) {
 299       myFirstBlock -> p_free_space += cNewSize;
 300       return anAddress;
 301     }
 302   }
 303 // In case of contraction of non-terminating allocation, do nothing
 304   else if (cOldSize >= cNewSize)
 305     return anAddress;
 306 // Extension of non-terminated allocation if there is enough room in the
 307 // current memory block
 308   if (cNewSize <= IMEM_FREE(myFirstBlock)) {
 309     aligned_t * aResult = myFirstBlock -> allocateInBlock (cNewSize);
 310     if (aResult)
 311       for (unsigned i = 0; i < cOldSize; i++)
 312         aResult[i] = anAddress[i];
 313     return aResult;
 314   }
 315
 316 // This is either of the cases:
 317 //   - extension of non-terminating allocation, or
 318 //   - extension of terminating allocation when the new size is too big
 319 // In both cases create a new memory block, allocate memory and copy there
 320 // the reallocated memory.
 321   size_t cMaxSize = mySize > cNewSize ? mySize : cNewSize;
 322   aligned_t * aResult = (aligned_t *) allocateNewBlock (cMaxSize);
 323   if (aResult) {
 324     myFirstBlock -> p_free_space = aResult + cNewSize;
 325     for (unsigned i = 0; i < cOldSize; i++)
 326       aResult[i] = anAddress[i];
 327   }
 328   else
 329   {
 330     Standard_OutOfMemory::Raise("NCollection_IncAllocator: out of memory");
 331   }
 332   return aResult;
 333 }
 334
 335 //=======================================================================
 336 //function : Free
 337 //purpose  :
 338 //=======================================================================
 339
 340 void NCollection_IncAllocator::Free (void *)
 341 {}
 342
 343 //=======================================================================
 344 //function : Clean
 345 //purpose  :
 346 //=======================================================================
 347
 348 void NCollection_IncAllocator::Clean ()
 349 {
 350 #ifdef ALLOC_TRACK_USAGE
 351   printf ("\n..NCollection_IncAllocator: Memory size to clean:%8.1f kB (%x)\n",
 352            double(GetMemSize())/1024, this);
 353 #endif
 354   IBlock * aBlock = myFirstBlock;
 355   if (aBlock) {
 356     aBlock -> p_free_space = (aligned_t *) &aBlock[1];
 357     aBlock = aBlock -> p_next;
 358     while (aBlock) {
 359       IBlock * aNext = aBlock -> p_next;
 360       free (aBlock);
 361       aBlock = aNext;
 362     }
 363     myFirstBlock -> p_next = NULL;
 364   }
 365   myMemSize = 0;
 366 }
 367
 368 //=======================================================================
 369 //function : Reset
 370 //purpose  :
 371 //=======================================================================
 372
 373 void NCollection_IncAllocator::Reset (const Standard_Boolean doReleaseMem)
 374 {
 375   if (doReleaseMem)
 376     Clean();
 377   else {
 378     Standard_Integer aBlockCount(0);
 379     IBlock * aBlock = myFirstBlock;
 380     while (aBlock)
 381       if (aBlockCount++ < MaxLookup) {
 382         aBlock -> p_free_space = (aligned_t *) &aBlock[1];
 383         if (aBlockCount < MaxLookup)
 384           aBlock = aBlock -> p_next;
 385         else {
 386           IBlock * aNext = aBlock -> p_next;
 387           aBlock -> p_next = NULL;
 388           aBlock = aNext;
 389         }
 390       } else {
 391         IBlock * aNext = aBlock -> p_next;
 392         myMemSize -= (aBlock -> p_end_block - (aligned_t *) aBlock) * sizeof (aligned_t);
 393         free (aBlock);
 394         aBlock = aNext;
 395       }
 396   }
 397 }
 398
 399 //=======================================================================
 400 //function : GetMemSize
 401 //purpose  : diagnostic utility
 402 //=======================================================================
 403
 404 size_t NCollection_IncAllocator::GetMemSize () const
 405 {
 406 //   size_t aResult = 0;
 407 //   IBlock * aBlock = myFirstBlock;
 408 //   while (aBlock) {
 409 //     aResult += (aBlock -> p_end_block - (aligned_t *) aBlock);
 410 //     aBlock = aBlock -> p_next;
 411 //   }
 412 //   return aResult * sizeof (aligned_t);
 413   return myMemSize;
 414 }
 415
 416 //=======================================================================
 417 //function : allocateNewBlock
 418 //purpose  :
 419 //=======================================================================
 420
 421 void * NCollection_IncAllocator::allocateNewBlock (const size_t cSize)
 422 {
 423   aligned_t * aResult = 0L;
 424   const size_t aSz = cSize + IMEM_SIZE(sizeof(IBlock));
 425   IBlock * aBlock = (IBlock *) malloc (aSz * sizeof(aligned_t));
 426   if (aBlock) {
 427     aBlock -> p_end_block  = ((aligned_t *)aBlock) + aSz;
 428     aBlock -> p_next = myFirstBlock;
 429     myFirstBlock = aBlock;
 430     aResult = (aligned_t *) IMEM_ALIGN(&aBlock[1]);
 431     myMemSize += aSz * sizeof(aligned_t);
 432   }
 433   return aResult;
 434 }