a867afa4e6bdf841caa94003f0db50c07df2d1c4
[occt.git] / 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
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     throw Standard_OutOfMemory("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       throw Standard_OutOfMemory("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               throw Standard_OutOfMemory("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               throw Standard_OutOfMemory("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     throw Standard_OutOfMemory("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 }