ext/OGDF/src/basic/PoolMemoryAllocator.cpp

   1 /*
   2  * $Revision: 2549 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-04 23:09:19 +0200 (Mi, 04. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of memory manager for more efficiently
  11  *        allocating small pieces of memory
  12  *
  13  * \author Carsten Gutwenger
  14  *
  15  * \par License:
  16  * This file is part of the Open Graph Drawing Framework (OGDF).
  17  *
  18  * \par
  19  * Copyright (C)<br>
  20  * See README.txt in the root directory of the OGDF installation for details.
  21  *
  22  * \par
  23  * This program is free software; you can redistribute it and/or
  24  * modify it under the terms of the GNU General Public License
  25  * Version 2 or 3 as published by the Free Software Foundation;
  26  * see the file LICENSE.txt included in the packaging of this file
  27  * for details.
  28  *
  29  * \par
  30  * This program is distributed in the hope that it will be useful,
  31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33  * GNU General Public License for more details.
  34  *
  35  * \par
  36  * You should have received a copy of the GNU General Public
  37  * License along with this program; if not, write to the Free
  38  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  39  * Boston, MA 02110-1301, USA.
  40  *
  41  * \see  http://www.gnu.org/copyleft/gpl.html
  42  ***************************************************************/
  43
  44
  45 #include <ogdf/basic/basic.h>
  46
  47
  48 namespace ogdf {
  49
  50
  51 struct PoolMemoryAllocator::PoolVector
  52 {
  53         MemElemPtr m_pool[ePoolVectorLength];
  54         PoolVector *m_prev;
  55 };
  56
  57 struct PoolMemoryAllocator::PoolElement
  58 {
  59         PoolVector *m_currentVector;
  60         MemElemPtr m_restHead;
  61         MemElemPtr m_restTail;
  62         __int16 m_index;
  63         __int16 m_restCount;
  64 };
  65
  66 struct PoolMemoryAllocator::BlockChain
  67 {
  68         char m_fill[eBlockSize-sizeof(void*)];
  69         BlockChain *m_next;
  70 };
  71
  72
  73 PoolMemoryAllocator::PoolElement PoolMemoryAllocator::s_pool[eTableSize];
  74 PoolMemoryAllocator::MemElemPtr PoolMemoryAllocator::s_freeVectors;
  75 PoolMemoryAllocator::BlockChainPtr PoolMemoryAllocator::s_blocks;
  76
  77 #ifdef OGDF_MEMORY_POOL_NTS
  78 PoolMemoryAllocator::MemElemPtr PoolMemoryAllocator::s_tp[eTableSize];
  79 #elif defined(OGDF_NO_COMPILER_TLS)
  80 CriticalSection *PoolMemoryAllocator::s_criticalSection;
  81 pthread_key_t PoolMemoryAllocator::s_tpKey;
  82 #else
  83 CriticalSection *PoolMemoryAllocator::s_criticalSection;
  84 OGDF_DECL_THREAD PoolMemoryAllocator::MemElemPtr PoolMemoryAllocator::s_tp[eTableSize];
  85 #endif
  86
  87
  88 void PoolMemoryAllocator::init()
  89 {
  90 #ifndef OGDF_MEMORY_POOL_NTS
  91 #ifdef OGDF_NO_COMPILER_TLS
  92         pthread_key_create(&s_tpKey,NULL);
  93 #endif
  94         s_criticalSection = new CriticalSection(500);
  95 #endif
  96         initThread();
  97 }
  98
  99
 100 void PoolMemoryAllocator::initThread() {
 101 #if !defined(OGDF_MEMORY_POOL_NTS) && defined(OGDF_NO_COMPILER_TLS)
 102                 pthread_setspecific(s_tpKey,calloc(eTableSize,sizeof(MemElemPtr)));
 103 #endif
 104 }
 105
 106
 107 void PoolMemoryAllocator::cleanup()
 108 {
 109         BlockChainPtr p = s_blocks;
 110         while(p != 0) {
 111                 BlockChainPtr pNext = p->m_next;
 112                 free(p);
 113                 p = pNext;
 114         }
 115
 116 #ifndef OGDF_MEMORY_POOL_NTS
 117 #ifdef OGDF_NO_COMPILER_TLS
 118         pthread_key_delete(s_tpKey);
 119 #endif
 120         delete s_criticalSection;
 121 #endif
 122 }
 123
 124
 125 bool PoolMemoryAllocator::checkSize(size_t nBytes) {
 126         return nBytes < eTableSize;
 127 }
 128
 129
 130 void *PoolMemoryAllocator::allocate(size_t nBytes) {
 131 #if !defined(OGDF_MEMORY_POOL_NTS) && defined(OGDF_NO_COMPILER_TLS)
 132         MemElemPtr *pFreeBytes = ((MemElemPtr*)pthread_getspecific(s_tpKey))+nBytes;
 133 #else
 134         MemElemPtr *pFreeBytes = s_tp+nBytes;
 135 #endif
 136         if (OGDF_LIKELY(*pFreeBytes != 0)) {
 137                 MemElemPtr p = *pFreeBytes;
 138                 *pFreeBytes = p->m_next;
 139                 return p;
 140         } else {
 141                 return fillPool(*pFreeBytes,__uint16(nBytes));
 142         }
 143 }
 144
 145
 146 void PoolMemoryAllocator::deallocate(size_t nBytes, void *p) {
 147 #if !defined(OGDF_MEMORY_POOL_NTS) && defined(OGDF_NO_COMPILER_TLS)
 148         MemElemPtr *pFreeBytes = ((MemElemPtr*)pthread_getspecific(s_tpKey))+nBytes;
 149 #else
 150         MemElemPtr *pFreeBytes = s_tp+nBytes;
 151 #endif
 152         MemElemPtr(p)->m_next = *pFreeBytes;
 153         *pFreeBytes = MemElemPtr(p);
 154 }
 155
 156
 157 void PoolMemoryAllocator::deallocateList(size_t nBytes, void *pHead, void *pTail) {
 158 #if !defined(OGDF_MEMORY_POOL_NTS) && defined(OGDF_NO_COMPILER_TLS)
 159         MemElemPtr *pFreeBytes = ((MemElemPtr*)pthread_getspecific(s_tpKey))+nBytes;
 160 #else
 161         MemElemPtr *pFreeBytes = s_tp+nBytes;
 162 #endif
 163         MemElemPtr(pTail)->m_next = *pFreeBytes;
 164         *pFreeBytes = MemElemPtr(pHead);
 165 }
 166
 167
 168 PoolMemoryAllocator::MemElemExPtr
 169 PoolMemoryAllocator::collectGroups(
 170         __uint16 nBytes,
 171         MemElemPtr &pRestHead,
 172         MemElemPtr &pRestTail,
 173         int &nRest)
 174 {
 175         int n = slicesPerBlock(nBytes);
 176         pRestHead = 0;
 177
 178 #if !defined(OGDF_MEMORY_POOL_NTS) && defined(OGDF_NO_COMPILER_TLS)
 179         MemElemPtr p = ((MemElemPtr*)pthread_getspecific(s_tpKey))[nBytes];
 180 #else
 181         MemElemPtr p = s_tp[nBytes];
 182 #endif
 183         MemElemExPtr pStart = 0, pLast = 0;
 184         while(p != 0)
 185         {
 186                 int i = 0;
 187                 MemElemPtr pHead = p, pTail;
 188                 do {
 189                         pTail = p;
 190                         p = p->m_next;
 191                 } while(++i < n && p != 0);
 192
 193                 pTail->m_next = 0;
 194                 if(i == n) {
 195                         if(pStart == 0)
 196                                 pStart = MemElemExPtr(pHead);
 197                         else
 198                                 pLast->m_down = MemElemExPtr(pHead);
 199                         pLast = MemElemExPtr(pHead);
 200
 201                 } else {
 202                         pRestHead = pHead;
 203                         pRestTail = pTail;
 204                         nRest = i;
 205                 }
 206         }
 207         if (pLast)
 208                 pLast->m_down = 0;
 209
 210         return pStart;
 211 }
 212
 213
 214 void PoolMemoryAllocator::flushPoolSmall(__uint16 nBytes)
 215 {
 216         int n = slicesPerBlock(nBytes < eMinBytes ? eMinBytes : nBytes);
 217         PoolElement &pe = s_pool[nBytes];
 218
 219 #if !defined(OGDF_MEMORY_POOL_NTS) && defined(OGDF_NO_COMPILER_TLS)
 220         MemElemPtr p = ((MemElemPtr*)pthread_getspecific(s_tpKey))[nBytes];
 221 #else
 222         MemElemPtr p = s_tp[nBytes];
 223 #endif
 224         if(pe.m_restHead != 0) {
 225                 pe.m_restTail->m_next = p;
 226                 p = pe.m_restHead;
 227                 pe.m_restHead = 0;
 228         }
 229
 230         while(p != 0)
 231         {
 232                 int i = 0;
 233                 MemElemPtr pHead = p, pTail;
 234                 do {
 235                         pTail = p;
 236                         p = p->m_next;
 237                 } while(++i < n && p != 0);
 238
 239                 if(i == n) {
 240                         incVectorSlot(pe);
 241                         pe.m_currentVector->m_pool[pe.m_index] = pHead;
 242
 243                 } else {
 244                         pe.m_restHead = pHead;
 245                         pe.m_restTail = pTail;
 246                         pe.m_restCount = i;
 247                 }
 248         }
 249 }
 250
 251
 252 void PoolMemoryAllocator::incVectorSlot(PoolElement &pe)
 253 {
 254         if(pe.m_currentVector == 0 || ++pe.m_index == ePoolVectorLength) {
 255                 if(s_freeVectors == 0)
 256                         s_freeVectors = allocateBlock(sizeof(PoolVector));
 257
 258                 PoolVector *pv = (PoolVector *)s_freeVectors;
 259                 s_freeVectors = MemElemPtr(pv)->m_next;
 260                 pe.m_currentVector = pv;
 261                 pe.m_index = 0;
 262         }
 263 }
 264
 265
 266 void PoolMemoryAllocator::flushPool(__uint16 nBytes)
 267 {
 268 #ifndef OGDF_MEMORY_POOL_NTS
 269         if(nBytes >= sizeof(MemElemEx)) {
 270                 MemElemPtr pRestHead, pRestTail;
 271                 int nRest;
 272                 MemElemExPtr pStart = collectGroups(nBytes, pRestHead, pRestTail, nRest);
 273
 274                 s_criticalSection->enter();
 275                 PoolElement &pe = s_pool[nBytes];
 276
 277                 while(pStart != 0) {
 278                         incVectorSlot(pe);
 279                         pe.m_currentVector->m_pool[pe.m_index] = MemElemPtr(pStart);
 280                         pStart = pStart->m_down;
 281                 }
 282                 if(pRestHead != 0) {
 283                         int n = slicesPerBlock(nBytes);
 284                         pRestTail->m_next = pe.m_restTail;
 285                         int nTotal = nRest + pe.m_restCount;
 286                         if(nTotal >= n) {
 287                                 MemElemPtr p = pe.m_restHead;
 288                                 int i = n-nRest;
 289                                 while(--i > 0)
 290                                         p = p->m_next;
 291                                 pe.m_restHead = p->m_next;
 292                                 pe.m_restCount = nTotal-n;
 293                                 incVectorSlot(pe);
 294                                 pe.m_currentVector->m_pool[pe.m_index] = pRestHead;
 295                         } else {
 296                                 pe.m_restHead = pRestHead;
 297                                 pe.m_restCount = nTotal;
 298                         }
 299                 }
 300                 s_criticalSection->leave();
 301
 302         } else {
 303                 s_criticalSection->enter();
 304                 flushPoolSmall(nBytes);
 305                 s_criticalSection->leave();
 306         }
 307 #endif
 308 }
 309
 310
 311 void PoolMemoryAllocator::flushPool()
 312 {
 313 #ifndef OGDF_MEMORY_POOL_NTS
 314         for(__uint16 nBytes = 1; nBytes < eTableSize; ++nBytes) {
 315 #ifdef OGDF_NO_COMPILER_TLS
 316         MemElemPtr p = ((MemElemPtr*)pthread_getspecific(s_tpKey))[nBytes];
 317 #else
 318         MemElemPtr p = s_tp[nBytes];
 319 #endif
 320                 if(p != 0)
 321                         flushPool(nBytes);
 322         }
 323 #endif
 324 }
 325
 326
 327 void *PoolMemoryAllocator::fillPool(MemElemPtr &pFreeBytes, __uint16 nBytes)
 328 {
 329 #ifdef OGDF_MEMORY_POOL_NTS
 330         pFreeBytes = allocateBlock(nBytes);
 331 #else
 332
 333         s_criticalSection->enter();
 334
 335         PoolElement &pe = s_pool[nBytes];
 336         if(pe.m_currentVector != 0) {
 337                 pFreeBytes = pe.m_currentVector->m_pool[pe.m_index];
 338                 if(--pe.m_index < 0) {
 339                         PoolVector *pV = pe.m_currentVector;
 340                         pe.m_currentVector = pV->m_prev;
 341                         pe.m_index = ePoolVectorLength-1;
 342                         MemElemPtr(pV)->m_next = s_freeVectors;
 343                         s_freeVectors = MemElemPtr(pV);
 344                 }
 345                 s_criticalSection->leave();
 346
 347         } else {
 348                 s_criticalSection->leave();
 349                 pFreeBytes = allocateBlock(nBytes);
 350         }
 351 #endif
 352
 353         MemElemPtr p = pFreeBytes;
 354         pFreeBytes = p->m_next;
 355         return p;
 356 }
 357
 358
 359 // __asm __volatile ("":::"memory")      GLIBC
 360
 361
 362 PoolMemoryAllocator::MemElemPtr
 363 PoolMemoryAllocator::allocateBlock(__uint16 nBytes)
 364 {
 365         if(nBytes < eMinBytes)
 366                 nBytes = eMinBytes;
 367
 368         MemElemPtr pBlock = (MemElemPtr) malloc(eBlockSize);
 369
 370         // we altogether create nSlices slices
 371         int nWords;
 372         int nSlices = slicesPerBlock(nBytes,nWords);
 373
 374         MemElemPtr pHead = MemElemPtr(pBlock);
 375         BlockChainPtr(pBlock)->m_next = s_blocks;
 376         s_blocks = BlockChainPtr(pBlock);
 377
 378         do {
 379                 pBlock = pBlock->m_next = pBlock+nWords;
 380         } while(--nSlices > 1);
 381         MemElemPtr(pBlock)->m_next = 0;
 382
 383         return pHead;
 384 }
 385
 386
 387 size_t PoolMemoryAllocator::memoryAllocatedInBlocks()
 388 {
 389 #ifndef OGDF_MEMORY_POOL_NTS
 390         s_criticalSection->enter();
 391 #endif
 392
 393         size_t nBlocks = 0;
 394         for (BlockChainPtr p = s_blocks; p != 0; p = p->m_next)
 395                 ++nBlocks;
 396
 397 #ifndef OGDF_MEMORY_POOL_NTS
 398         s_criticalSection->leave();
 399 #endif
 400
 401         return nBlocks * eBlockSize;
 402 }
 403
 404
 405 size_t PoolMemoryAllocator::memoryInGlobalFreeList()
 406 {
 407 #ifndef OGDF_MEMORY_POOL_NTS
 408         s_criticalSection->enter();
 409 #endif
 410
 411         size_t bytesFree = 0;
 412         for (int sz = 1; sz < eTableSize; ++sz)
 413         {
 414                 const PoolElement &pe = s_pool[sz];
 415                 PoolVector *pv = pe.m_currentVector;
 416                 for(; pv != 0; pv = pv->m_prev)
 417                         bytesFree += ePoolVectorLength*sz;
 418                 if(pe.m_restHead != 0)
 419                         bytesFree += pe.m_restCount;
 420         }
 421
 422 #ifndef OGDF_MEMORY_POOL_NTS
 423         s_criticalSection->leave();
 424 #endif
 425
 426         return bytesFree;
 427 }
 428
 429
 430 size_t PoolMemoryAllocator::memoryInThreadFreeList()
 431 {
 432         size_t bytesFree = 0;
 433         for (int sz = 1; sz < eTableSize; ++sz)
 434         {
 435 #if !defined(OGDF_MEMORY_POOL_NTS) && defined(OGDF_NO_COMPILER_TLS)
 436                 MemElemPtr p = ((MemElemPtr*)pthread_getspecific(s_tpKey))[sz];
 437 #else
 438                 MemElemPtr p = s_tp[sz];
 439 #endif
 440                 for(; p != 0; p = p->m_next)
 441                         bytesFree += sz;
 442         }
 443
 444         return bytesFree;
 445 }
 446
 447
 448 }