Home | History | Annotate | Download | only in src 
      1 /*M///////////////////////////////////////////////////////////////////////////////////////
      2 //
      3 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
      4 //
      5 //  By downloading, copying, installing or using the software you agree to this license.
      6 //  If you do not agree to this license, do not download, install,
      7 //  copy or use the software.
      8 //
      9 //
     10 //                           License Agreement
     11 //                For Open Source Computer Vision Library
     12 //
     13 // Copyright (C) 2000-2008, Intel Corporation, all rights reserved.
     14 // Copyright (C) 2009, Willow Garage Inc., all rights reserved.
     15 // Third party copyrights are property of their respective owners.
     16 //
     17 // Redistribution and use in source and binary forms, with or without modification,
     18 // are permitted provided that the following conditions are met:
     19 //
     20 //   * Redistribution's of source code must retain the above copyright notice,
     21 //     this list of conditions and the following disclaimer.
     22 //
     23 //   * Redistribution's in binary form must reproduce the above copyright notice,
     24 //     this list of conditions and the following disclaimer in the documentation
     25 //     and/or other materials provided with the distribution.
     26 //
     27 //   * The name of the copyright holders may not be used to endorse or promote products
     28 //     derived from this software without specific prior written permission.
     29 //
     30 // This software is provided by the copyright holders and contributors "as is" and
     31 // any express or implied warranties, including, but not limited to, the implied
     32 // warranties of merchantability and fitness for a particular purpose are disclaimed.
     33 // In no event shall the Intel Corporation or contributors be liable for any direct,
     34 // indirect, incidental, special, exemplary, or consequential damages
     35 // (including, but not limited to, procurement of substitute goods or services;
     36 // loss of use, data, or profits; or business interruption) however caused
     37 // and on any theory of liability, whether in contract, strict liability,
     38 // or tort (including negligence or otherwise) arising in any way out of
     39 // the use of this software, even if advised of the possibility of such damage.
     40 //
     41 //M*/
     42 
     43 #include "precomp.hpp"
     44 
     45 #define CV_USE_SYSTEM_MALLOC 1
     46 
     47 namespace cv
     48 {
     49 
     50 static void* OutOfMemoryError(size_t size)
     51 {
     52     CV_Error_(CV_StsNoMem, ("Failed to allocate %lu bytes", (unsigned long)size));
     53     return 0;
     54 }
     55 
     56 #if CV_USE_SYSTEM_MALLOC
     57 
     58 #if defined WIN32 || defined _WIN32
     59 void deleteThreadAllocData() {}
     60 #endif
     61 
     62 void* fastMalloc( size_t size )
     63 {
     64     uchar* udata = (uchar*)malloc(size + sizeof(void*) + CV_MALLOC_ALIGN);
     65     if(!udata)
     66         return OutOfMemoryError(size);
     67     uchar** adata = alignPtr((uchar**)udata + 1, CV_MALLOC_ALIGN);
     68     adata[-1] = udata;
     69     return adata;
     70 }
     71 
     72 void fastFree(void* ptr)
     73 {
     74     if(ptr)
     75     {
     76         uchar* udata = ((uchar**)ptr)[-1];
     77         CV_DbgAssert(udata < (uchar*)ptr &&
     78                ((uchar*)ptr - udata) <= (ptrdiff_t)(sizeof(void*)+CV_MALLOC_ALIGN));
     79         free(udata);
     80     }
     81 }
     82 
     83 #else //CV_USE_SYSTEM_MALLOC
     84 
     85 #if 0
     86 #define SANITY_CHECK(block) \
     87     CV_Assert(((size_t)(block) & (MEM_BLOCK_SIZE-1)) == 0 && \
     88         (unsigned)(block)->binIdx <= (unsigned)MAX_BIN && \
     89         (block)->signature == MEM_BLOCK_SIGNATURE)
     90 #else
     91 #define SANITY_CHECK(block)
     92 #endif
     93 
     94 #define STAT(stmt)
     95 
     96 #ifdef WIN32
     97 #if (_WIN32_WINNT >= 0x0602)
     98 #include <synchapi.h>
     99 #endif
    100 
    101 struct CriticalSection
    102 {
    103     CriticalSection()
    104     {
    105 #if (_WIN32_WINNT >= 0x0600)
    106         InitializeCriticalSectionEx(&cs, 1000, 0);
    107 #else
    108         InitializeCriticalSection(&cs);
    109 #endif
    110     }
    111     ~CriticalSection() { DeleteCriticalSection(&cs); }
    112     void lock() { EnterCriticalSection(&cs); }
    113     void unlock() { LeaveCriticalSection(&cs); }
    114     bool trylock() { return TryEnterCriticalSection(&cs) != 0; }
    115 
    116     CRITICAL_SECTION cs;
    117 };
    118 
    119 void* SystemAlloc(size_t size)
    120 {
    121     void* ptr = malloc(size);
    122     return ptr ? ptr : OutOfMemoryError(size);
    123 }
    124 
    125 void SystemFree(void* ptr, size_t)
    126 {
    127     free(ptr);
    128 }
    129 #else //WIN32
    130 
    131 #include <sys/mman.h>
    132 
    133 struct CriticalSection
    134 {
    135     CriticalSection() { pthread_mutex_init(&mutex, 0); }
    136     ~CriticalSection() { pthread_mutex_destroy(&mutex); }
    137     void lock() { pthread_mutex_lock(&mutex); }
    138     void unlock() { pthread_mutex_unlock(&mutex); }
    139     bool trylock() { return pthread_mutex_trylock(&mutex) == 0; }
    140 
    141     pthread_mutex_t mutex;
    142 };
    143 
    144 void* SystemAlloc(size_t size)
    145 {
    146     #ifndef MAP_ANONYMOUS
    147     #define MAP_ANONYMOUS MAP_ANON
    148     #endif
    149     void* ptr = 0;
    150     ptr = mmap(ptr, size, (PROT_READ | PROT_WRITE), MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
    151     return ptr != MAP_FAILED ? ptr : OutOfMemoryError(size);
    152 }
    153 
    154 void SystemFree(void* ptr, size_t size)
    155 {
    156     munmap(ptr, size);
    157 }
    158 #endif //WIN32
    159 
    160 struct AutoLock
    161 {
    162     AutoLock(CriticalSection& _cs) : cs(&_cs) { cs->lock(); }
    163     ~AutoLock() { cs->unlock(); }
    164     CriticalSection* cs;
    165 };
    166 
    167 const size_t MEM_BLOCK_SIGNATURE = 0x01234567;
    168 const int MEM_BLOCK_SHIFT = 14;
    169 const size_t MEM_BLOCK_SIZE = 1 << MEM_BLOCK_SHIFT;
    170 const size_t HDR_SIZE = 128;
    171 const size_t MAX_BLOCK_SIZE = MEM_BLOCK_SIZE - HDR_SIZE;
    172 const int MAX_BIN = 28;
    173 
    174 static const int binSizeTab[MAX_BIN+1] =
    175 { 8, 16, 24, 32, 40, 48, 56, 64, 80, 96, 128, 160, 192, 256, 320, 384, 480, 544, 672, 768,
    176 896, 1056, 1328, 1600, 2688, 4048, 5408, 8128, 16256 };
    177 
    178 struct MallocTables
    179 {
    180     void initBinTab()
    181     {
    182         int i, j = 0, n;
    183         for( i = 0; i <= MAX_BIN; i++ )
    184         {
    185             n = binSizeTab[i]>>3;
    186             for( ; j <= n; j++ )
    187                 binIdx[j] = (uchar)i;
    188         }
    189     }
    190     int bin(size_t size)
    191     {
    192         assert( size <= MAX_BLOCK_SIZE );
    193         return binIdx[(size + 7)>>3];
    194     }
    195 
    196     MallocTables()
    197     {
    198         initBinTab();
    199     }
    200 
    201     uchar binIdx[MAX_BLOCK_SIZE/8+1];
    202 };
    203 
    204 MallocTables mallocTables;
    205 
    206 struct Node
    207 {
    208     Node* next;
    209 };
    210 
    211 struct ThreadData;
    212 
    213 struct Block
    214 {
    215     Block(Block* _next)
    216     {
    217         signature = MEM_BLOCK_SIGNATURE;
    218         prev = 0;
    219         next = _next;
    220         privateFreeList = publicFreeList = 0;
    221         bumpPtr = endPtr = 0;
    222         objSize = 0;
    223         threadData = 0;
    224         data = (uchar*)this + HDR_SIZE;
    225     }
    226 
    227     ~Block() {}
    228 
    229     void init(Block* _prev, Block* _next, int _objSize, ThreadData* _threadData)
    230     {
    231         prev = _prev;
    232         if(prev)
    233             prev->next = this;
    234         next = _next;
    235         if(next)
    236             next->prev = this;
    237         objSize = _objSize;
    238         binIdx = mallocTables.bin(objSize);
    239         threadData = _threadData;
    240         privateFreeList = publicFreeList = 0;
    241         bumpPtr = data;
    242         int nobjects = MAX_BLOCK_SIZE/objSize;
    243         endPtr = bumpPtr + nobjects*objSize;
    244         almostEmptyThreshold = (nobjects + 1)/2;
    245         allocated = 0;
    246     }
    247 
    248     bool isFilled() const { return allocated > almostEmptyThreshold; }
    249 
    250     size_t signature;
    251     Block* prev;
    252     Block* next;
    253     Node* privateFreeList;
    254     Node* publicFreeList;
    255     uchar* bumpPtr;
    256     uchar* endPtr;
    257     uchar* data;
    258     ThreadData* threadData;
    259     int objSize;
    260     int binIdx;
    261     int allocated;
    262     int almostEmptyThreshold;
    263     CriticalSection cs;
    264 };
    265 
    266 struct BigBlock
    267 {
    268     BigBlock(int bigBlockSize, BigBlock* _next)
    269     {
    270         first = alignPtr((Block*)(this+1), MEM_BLOCK_SIZE);
    271         next = _next;
    272         nblocks = (int)(((char*)this + bigBlockSize - (char*)first)/MEM_BLOCK_SIZE);
    273         Block* p = 0;
    274         for( int i = nblocks-1; i >= 0; i-- )
    275             p = ::new((uchar*)first + i*MEM_BLOCK_SIZE) Block(p);
    276     }
    277 
    278     ~BigBlock()
    279     {
    280         for( int i = nblocks-1; i >= 0; i-- )
    281             ((Block*)((uchar*)first+i*MEM_BLOCK_SIZE))->~Block();
    282     }
    283 
    284     BigBlock* next;
    285     Block* first;
    286     int nblocks;
    287 };
    288 
    289 struct BlockPool
    290 {
    291     BlockPool(int _bigBlockSize=1<<20) : pool(0), bigBlockSize(_bigBlockSize)
    292     {
    293     }
    294 
    295     ~BlockPool()
    296     {
    297         AutoLock lock(cs);
    298         while( pool )
    299         {
    300             BigBlock* nextBlock = pool->next;
    301             pool->~BigBlock();
    302             SystemFree(pool, bigBlockSize);
    303             pool = nextBlock;
    304         }
    305     }
    306 
    307     Block* alloc()
    308     {
    309         AutoLock lock(cs);
    310         Block* block;
    311         if( !freeBlocks )
    312         {
    313             BigBlock* bblock = ::new(SystemAlloc(bigBlockSize)) BigBlock(bigBlockSize, pool);
    314             assert( bblock != 0 );
    315             freeBlocks = bblock->first;
    316             pool = bblock;
    317         }
    318         block = freeBlocks;
    319         freeBlocks = freeBlocks->next;
    320         if( freeBlocks )
    321             freeBlocks->prev = 0;
    322         STAT(stat.bruttoBytes += MEM_BLOCK_SIZE);
    323         return block;
    324     }
    325 
    326     void free(Block* block)
    327     {
    328         AutoLock lock(cs);
    329         block->prev = 0;
    330         block->next = freeBlocks;
    331         freeBlocks = block;
    332         STAT(stat.bruttoBytes -= MEM_BLOCK_SIZE);
    333     }
    334 
    335     CriticalSection cs;
    336     Block* freeBlocks;
    337     BigBlock* pool;
    338     int bigBlockSize;
    339     int blocksPerBigBlock;
    340 };
    341 
    342 BlockPool mallocPool;
    343 
    344 enum { START=0, FREE=1, GC=2 };
    345 
    346 struct ThreadData
    347 {
    348     ThreadData() { for(int i = 0; i <= MAX_BIN; i++) bins[i][START] = bins[i][FREE] = bins[i][GC] = 0; }
    349     ~ThreadData()
    350     {
    351         // mark all the thread blocks as abandoned or even release them
    352         for( int i = 0; i <= MAX_BIN; i++ )
    353         {
    354             Block *bin = bins[i][START], *block = bin;
    355             bins[i][START] = bins[i][FREE] = bins[i][GC] = 0;
    356             if( block )
    357             {
    358                 do
    359                 {
    360                     Block* next = block->next;
    361                     int allocated = block->allocated;
    362                     {
    363                     AutoLock lock(block->cs);
    364                     block->next = block->prev = 0;
    365                     block->threadData = 0;
    366                     Node *node = block->publicFreeList;
    367                     for( ; node != 0; node = node->next )
    368                         allocated--;
    369                     }
    370                     if( allocated == 0 )
    371                         mallocPool.free(block);
    372                     block = next;
    373                 }
    374                 while( block != bin );
    375             }
    376         }
    377     }
    378 
    379     void moveBlockToFreeList( Block* block )
    380     {
    381         int i = block->binIdx;
    382         Block*& freePtr = bins[i][FREE];
    383         CV_DbgAssert( block->next->prev == block && block->prev->next == block );
    384         if( block != freePtr )
    385         {
    386             Block*& gcPtr = bins[i][GC];
    387             if( gcPtr == block )
    388                 gcPtr = block->next;
    389             if( block->next != block )
    390             {
    391                 block->prev->next = block->next;
    392                 block->next->prev = block->prev;
    393             }
    394             block->next = freePtr->next;
    395             block->prev = freePtr;
    396             freePtr = block->next->prev = block->prev->next = block;
    397         }
    398     }
    399 
    400     Block* bins[MAX_BIN+1][3];
    401 
    402 #ifdef WIN32
    403 #ifdef WINCE
    404 #   define TLS_OUT_OF_INDEXES ((DWORD)0xFFFFFFFF)
    405 #endif //WINCE
    406 
    407     static DWORD tlsKey;
    408     static ThreadData* get()
    409     {
    410         ThreadData* data;
    411         if( tlsKey == TLS_OUT_OF_INDEXES )
    412             tlsKey = TlsAlloc();
    413         data = (ThreadData*)TlsGetValue(tlsKey);
    414         if( !data )
    415         {
    416             data = new ThreadData;
    417             TlsSetValue(tlsKey, data);
    418         }
    419         return data;
    420     }
    421 #else //WIN32
    422     static void deleteData(void* data)
    423     {
    424         delete (ThreadData*)data;
    425     }
    426 
    427     static pthread_key_t tlsKey;
    428     static ThreadData* get()
    429     {
    430         ThreadData* data;
    431         if( !tlsKey )
    432             pthread_key_create(&tlsKey, deleteData);
    433         data = (ThreadData*)pthread_getspecific(tlsKey);
    434         if( !data )
    435         {
    436             data = new ThreadData;
    437             pthread_setspecific(tlsKey, data);
    438         }
    439         return data;
    440     }
    441 #endif //WIN32
    442 };
    443 
    444 #ifdef WIN32
    445 DWORD ThreadData::tlsKey = TLS_OUT_OF_INDEXES;
    446 
    447 void deleteThreadAllocData()
    448 {
    449     if( ThreadData::tlsKey != TLS_OUT_OF_INDEXES )
    450         delete (ThreadData*)TlsGetValue( ThreadData::tlsKey );
    451 }
    452 
    453 #else //WIN32
    454 pthread_key_t ThreadData::tlsKey = 0;
    455 #endif //WIN32
    456 
    457 #if 0
    458 static void checkList(ThreadData* tls, int idx)
    459 {
    460     Block* block = tls->bins[idx][START];
    461     if( !block )
    462     {
    463         CV_DbgAssert( tls->bins[idx][FREE] == 0 && tls->bins[idx][GC] == 0 );
    464     }
    465     else
    466     {
    467         bool gcInside = false;
    468         bool freeInside = false;
    469         do
    470         {
    471             if( tls->bins[idx][FREE] == block )
    472                 freeInside = true;
    473             if( tls->bins[idx][GC] == block )
    474                 gcInside = true;
    475             block = block->next;
    476         }
    477         while( block != tls->bins[idx][START] );
    478         CV_DbgAssert( gcInside && freeInside );
    479     }
    480 }
    481 #else
    482 #define checkList(tls, idx)
    483 #endif
    484 
    485 void* fastMalloc( size_t size )
    486 {
    487     if( size > MAX_BLOCK_SIZE )
    488     {
    489         size_t size1 = size + sizeof(uchar*)*2 + MEM_BLOCK_SIZE;
    490         uchar* udata = (uchar*)SystemAlloc(size1);
    491         uchar** adata = alignPtr((uchar**)udata + 2, MEM_BLOCK_SIZE);
    492         adata[-1] = udata;
    493         adata[-2] = (uchar*)size1;
    494         return adata;
    495     }
    496 
    497     {
    498     ThreadData* tls = ThreadData::get();
    499     int idx = mallocTables.bin(size);
    500     Block*& startPtr = tls->bins[idx][START];
    501     Block*& gcPtr = tls->bins[idx][GC];
    502     Block*& freePtr = tls->bins[idx][FREE], *block = freePtr;
    503     checkList(tls, idx);
    504     size = binSizeTab[idx];
    505     STAT(
    506         stat.nettoBytes += size;
    507         stat.mallocCalls++;
    508         );
    509     uchar* data = 0;
    510 
    511     for(;;)
    512     {
    513         if( block )
    514         {
    515             // try to find non-full block
    516             for(;;)
    517             {
    518                 CV_DbgAssert( block->next->prev == block && block->prev->next == block );
    519                 if( block->bumpPtr )
    520                 {
    521                     data = block->bumpPtr;
    522                     if( (block->bumpPtr += size) >= block->endPtr )
    523                         block->bumpPtr = 0;
    524                     break;
    525                 }
    526 
    527                 if( block->privateFreeList )
    528                 {
    529                     data = (uchar*)block->privateFreeList;
    530                     block->privateFreeList = block->privateFreeList->next;
    531                     break;
    532                 }
    533 
    534                 if( block == startPtr )
    535                     break;
    536                 block = block->next;
    537             }
    538 #if 0
    539             avg_k += _k;
    540             avg_nk++;
    541             if( avg_nk == 1000 )
    542             {
    543                 printf("avg search iters per 1e3 allocs = %g\n", (double)avg_k/avg_nk );
    544                 avg_k = avg_nk = 0;
    545             }
    546 #endif
    547 
    548             freePtr = block;
    549             if( !data )
    550             {
    551                 block = gcPtr;
    552                 for( int k = 0; k < 2; k++ )
    553                 {
    554                     SANITY_CHECK(block);
    555                     CV_DbgAssert( block->next->prev == block && block->prev->next == block );
    556                     if( block->publicFreeList )
    557                     {
    558                         {
    559                         AutoLock lock(block->cs);
    560                         block->privateFreeList = block->publicFreeList;
    561                         block->publicFreeList = 0;
    562                         }
    563                         Node* node = block->privateFreeList;
    564                         for(;node != 0; node = node->next)
    565                             --block->allocated;
    566                         data = (uchar*)block->privateFreeList;
    567                         block->privateFreeList = block->privateFreeList->next;
    568                         gcPtr = block->next;
    569                         if( block->allocated+1 <= block->almostEmptyThreshold )
    570                             tls->moveBlockToFreeList(block);
    571                         break;
    572                     }
    573                     block = block->next;
    574                 }
    575                 if( !data )
    576                     gcPtr = block;
    577             }
    578         }
    579 
    580         if( data )
    581             break;
    582         block = mallocPool.alloc();
    583         block->init(startPtr ? startPtr->prev : block, startPtr ? startPtr : block, (int)size, tls);
    584         if( !startPtr )
    585             startPtr = gcPtr = freePtr = block;
    586         checkList(tls, block->binIdx);
    587         SANITY_CHECK(block);
    588     }
    589 
    590     ++block->allocated;
    591     return data;
    592     }
    593 }
    594 
    595 void fastFree( void* ptr )
    596 {
    597     if( ((size_t)ptr & (MEM_BLOCK_SIZE-1)) == 0 )
    598     {
    599         if( ptr != 0 )
    600         {
    601             void* origPtr = ((void**)ptr)[-1];
    602             size_t sz = (size_t)((void**)ptr)[-2];
    603             SystemFree( origPtr, sz );
    604         }
    605         return;
    606     }
    607 
    608     {
    609     ThreadData* tls = ThreadData::get();
    610     Node* node = (Node*)ptr;
    611     Block* block = (Block*)((size_t)ptr & -(int)MEM_BLOCK_SIZE);
    612     assert( block->signature == MEM_BLOCK_SIGNATURE );
    613 
    614     if( block->threadData == tls )
    615     {
    616         STAT(
    617         stat.nettoBytes -= block->objSize;
    618         stat.freeCalls++;
    619         float ratio = (float)stat.nettoBytes/stat.bruttoBytes;
    620         if( stat.minUsageRatio > ratio )
    621             stat.minUsageRatio = ratio;
    622         );
    623 
    624         SANITY_CHECK(block);
    625 
    626         bool prevFilled = block->isFilled();
    627         --block->allocated;
    628         if( !block->isFilled() && (block->allocated == 0 || prevFilled) )
    629         {
    630             if( block->allocated == 0 )
    631             {
    632                 int idx = block->binIdx;
    633                 Block*& startPtr = tls->bins[idx][START];
    634                 Block*& freePtr = tls->bins[idx][FREE];
    635                 Block*& gcPtr = tls->bins[idx][GC];
    636 
    637                 if( block == block->next )
    638                 {
    639                     CV_DbgAssert( startPtr == block && freePtr == block && gcPtr == block );
    640                     startPtr = freePtr = gcPtr = 0;
    641                 }
    642                 else
    643                 {
    644                     if( freePtr == block )
    645                         freePtr = block->next;
    646                     if( gcPtr == block )
    647                         gcPtr = block->next;
    648                     if( startPtr == block )
    649                         startPtr = block->next;
    650                     block->prev->next = block->next;
    651                     block->next->prev = block->prev;
    652                 }
    653                 mallocPool.free(block);
    654                 checkList(tls, idx);
    655                 return;
    656             }
    657 
    658             tls->moveBlockToFreeList(block);
    659         }
    660         node->next = block->privateFreeList;
    661         block->privateFreeList = node;
    662     }
    663     else
    664     {
    665         AutoLock lock(block->cs);
    666         SANITY_CHECK(block);
    667 
    668         node->next = block->publicFreeList;
    669         block->publicFreeList = node;
    670         if( block->threadData == 0 )
    671         {
    672             // take ownership of the abandoned block.
    673             // note that it can happen at the same time as
    674             // ThreadData::deleteData() marks the blocks as abandoned,
    675             // so this part of the algorithm needs to be checked for data races
    676             int idx = block->binIdx;
    677             block->threadData = tls;
    678             Block*& startPtr = tls->bins[idx][START];
    679 
    680             if( startPtr )
    681             {
    682                 block->next = startPtr;
    683                 block->prev = startPtr->prev;
    684                 block->next->prev = block->prev->next = block;
    685             }
    686             else
    687                 startPtr = tls->bins[idx][FREE] = tls->bins[idx][GC] = block;
    688         }
    689     }
    690     }
    691 }
    692 
    693 #endif //CV_USE_SYSTEM_MALLOC
    694 
    695 }
    696 
    697 CV_IMPL void* cvAlloc( size_t size )
    698 {
    699     return cv::fastMalloc( size );
    700 }
    701 
    702 CV_IMPL void cvFree_( void* ptr )
    703 {
    704     cv::fastFree( ptr );
    705 }
    706 
    707 
    708 /* End of file. */
    709