alloc.cpp

00001 /*M///////////////////////////////////////////////////////////////////////////////////////
00002 //
00003 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
00004 //
00005 //  By downloading, copying, installing or using the software you agree to this license.
00006 //  If you do not agree to this license, do not download, install,
00007 //  copy or use the software.
00008 //
00009 //
00010 //                           License Agreement
00011 //                For Open Source Computer Vision Library
00012 //
00013 // Copyright (C) 2000-2008, Intel Corporation, all rights reserved.
00014 // Copyright (C) 2009, Willow Garage Inc., all rights reserved.
00015 // Third party copyrights are property of their respective owners.
00016 //
00017 // Redistribution and use in source and binary forms, with or without modification,
00018 // are permitted provided that the following conditions are met:
00019 //
00020 //   * Redistribution's of source code must retain the above copyright notice,
00021 //     this list of conditions and the following disclaimer.
00022 //
00023 //   * Redistribution's in binary form must reproduce the above copyright notice,
00024 //     this list of conditions and the following disclaimer in the documentation
00025 //     and/or other materials provided with the distribution.
00026 //
00027 //   * The name of the copyright holders may not be used to endorse or promote products
00028 //     derived from this software without specific prior written permission.
00029 //
00030 // This software is provided by the copyright holders and contributors "as is" and
00031 // any express or implied warranties, including, but not limited to, the implied
00032 // warranties of merchantability and fitness for a particular purpose are disclaimed.
00033 // In no event shall the Intel Corporation or contributors be liable for any direct,
00034 // indirect, incidental, special, exemplary, or consequential damages
00035 // (including, but not limited to, procurement of substitute goods or services;
00036 // loss of use, data, or profits; or business interruption) however caused
00037 // and on any theory of liability, whether in contract, strict liability,
00038 // or tort (including negligence or otherwise) arising in any way out of
00039 // the use of this software, even if advised of the possibility of such damage.
00040 //
00041 //M*/
00042 
00043 #include "precomp.hpp"
00044 
00045 #define CV_USE_SYSTEM_MALLOC 1
00046 //#define DEBUG_HEAP
00047 namespace cv
00048 {
00049 
00050 static void* OutOfMemoryError(size_t size)
00051 {
00052     CV_Error_(CV_StsNoMem, ("Failed to allocate %lu bytes", (unsigned long)size));
00053     return 0;
00054 }
00055 
00056 #if CV_USE_SYSTEM_MALLOC
00057 
00058 #if defined WIN32 || defined _WIN32
00059 void deleteThreadAllocData() {}
00060 #endif
00061 
00062 void* fastMalloc( size_t size )
00063 {
00064     uchar* udata = (uchar*)malloc(size + sizeof(void*) + CV_MALLOC_ALIGN);
00065 #ifdef DEBUG_HEAP
00066         static int checkprint = 0;
00067         if (size == 768000)
00068         {
00069             //printf("allocated: %d - 0x%8x \n", size, udata);
00070             checkprint = 1;
00071         }
00072         if (checkprint)
00073         {
00074             printf("%d - 0x%8x \n", size, udata);
00075             //printf("%d \n", size);
00076         }
00077 #endif
00078     if(!udata)
00079         return OutOfMemoryError(size);
00080     uchar** adata = alignPtr((uchar**)udata + 1, CV_MALLOC_ALIGN);
00081     adata[-1] = udata;
00082     return adata;
00083 }
00084 
00085 void fastFree(void* ptr)
00086 {
00087     if(ptr)
00088     {
00089         uchar* udata = ((uchar**)ptr)[-1];
00090         CV_DbgAssert(udata < (uchar*)ptr &&
00091                ((uchar*)ptr - udata) <= (ptrdiff_t)(sizeof(void*)+CV_MALLOC_ALIGN));
00092         free(udata);
00093     }
00094 }
00095 
00096 #else //CV_USE_SYSTEM_MALLOC
00097 
00098 #if 0
00099 #define SANITY_CHECK(block) \
00100     CV_Assert(((size_t)(block) & (MEM_BLOCK_SIZE-1)) == 0 && \
00101         (unsigned)(block)->binIdx <= (unsigned)MAX_BIN && \
00102         (block)->signature == MEM_BLOCK_SIGNATURE)
00103 #else
00104 #define SANITY_CHECK(block)
00105 #endif
00106 
00107 #define STAT(stmt)
00108 
00109 #ifdef WIN32
00110 #if (_WIN32_WINNT >= 0x0602)
00111 #include <synchapi.h>
00112 #endif
00113 
00114 struct CriticalSection
00115 {
00116     CriticalSection()
00117     {
00118 #if (_WIN32_WINNT >= 0x0600)
00119         InitializeCriticalSectionEx(&cs, 1000, 0);
00120 #else
00121         InitializeCriticalSection(&cs);
00122 #endif
00123     }
00124     ~CriticalSection() { DeleteCriticalSection(&cs); }
00125     void lock() { EnterCriticalSection(&cs); }
00126     void unlock() { LeaveCriticalSection(&cs); }
00127     bool trylock() { return TryEnterCriticalSection(&cs) != 0; }
00128 
00129     CRITICAL_SECTION cs;
00130 };
00131 
00132 void* SystemAlloc(size_t size)
00133 {
00134     void* ptr = malloc(size);
00135     return ptr ? ptr : OutOfMemoryError(size);
00136 }
00137 
00138 void SystemFree(void* ptr, size_t)
00139 {
00140     free(ptr);
00141 }
00142 #else //WIN32
00143 
00144 #include <sys/mman.h>
00145 
00146 struct CriticalSection
00147 {
00148     CriticalSection() { pthread_mutex_init(&mutex, 0); }
00149     ~CriticalSection() { pthread_mutex_destroy(&mutex); }
00150     void lock() { pthread_mutex_lock(&mutex); }
00151     void unlock() { pthread_mutex_unlock(&mutex); }
00152     bool trylock() { return pthread_mutex_trylock(&mutex) == 0; }
00153 
00154     pthread_mutex_t mutex;
00155 };
00156 
00157 void* SystemAlloc(size_t size)
00158 {
00159     #ifndef MAP_ANONYMOUS
00160     #define MAP_ANONYMOUS MAP_ANON
00161     #endif
00162     void* ptr = 0;
00163     ptr = mmap(ptr, size, (PROT_READ | PROT_WRITE), MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
00164     return ptr != MAP_FAILED ? ptr : OutOfMemoryError(size);
00165 }
00166 
00167 void SystemFree(void* ptr, size_t size)
00168 {
00169     munmap(ptr, size);
00170 }
00171 #endif //WIN32
00172 
00173 struct AutoLock
00174 {
00175     AutoLock(CriticalSection& _cs) : cs(&_cs) { cs->lock(); }
00176     ~AutoLock() { cs->unlock(); }
00177     CriticalSection* cs;
00178 };
00179 
00180 const size_t MEM_BLOCK_SIGNATURE = 0x01234567;
00181 const int MEM_BLOCK_SHIFT = 14;
00182 const size_t MEM_BLOCK_SIZE = 1 << MEM_BLOCK_SHIFT;
00183 const size_t HDR_SIZE = 128;
00184 const size_t MAX_BLOCK_SIZE = MEM_BLOCK_SIZE - HDR_SIZE;
00185 const int MAX_BIN = 28;
00186 
00187 static const int binSizeTab[MAX_BIN+1] =
00188 { 8, 16, 24, 32, 40, 48, 56, 64, 80, 96, 128, 160, 192, 256, 320, 384, 480, 544, 672, 768,
00189 896, 1056, 1328, 1600, 2688, 4048, 5408, 8128, 16256 };
00190 
00191 struct MallocTables
00192 {
00193     void initBinTab()
00194     {
00195         int i, j = 0, n;
00196         for( i = 0; i <= MAX_BIN; i++ )
00197         {
00198             n = binSizeTab[i]>>3;
00199             for( ; j <= n; j++ )
00200                 binIdx[j] = (uchar)i;
00201         }
00202     }
00203     int bin(size_t size)
00204     {
00205         assert( size <= MAX_BLOCK_SIZE );
00206         return binIdx[(size + 7)>>3];
00207     }
00208 
00209     MallocTables()
00210     {
00211         initBinTab();
00212     }
00213 
00214     uchar binIdx[MAX_BLOCK_SIZE/8+1];
00215 };
00216 
00217 MallocTables mallocTables;
00218 
00219 struct Node
00220 {
00221     Node* next;
00222 };
00223 
00224 struct ThreadData;
00225 
00226 struct Block
00227 {
00228     Block(Block* _next)
00229     {
00230         signature = MEM_BLOCK_SIGNATURE;
00231         prev = 0;
00232         next = _next;
00233         privateFreeList = publicFreeList = 0;
00234         bumpPtr = endPtr = 0;
00235         objSize = 0;
00236         threadData = 0;
00237         data = (uchar*)this + HDR_SIZE;
00238     }
00239 
00240     ~Block() {}
00241 
00242     void init(Block* _prev, Block* _next, int _objSize, ThreadData* _threadData)
00243     {
00244         prev = _prev;
00245         if(prev)
00246             prev->next = this;
00247         next = _next;
00248         if(next)
00249             next->prev = this;
00250         objSize = _objSize;
00251         binIdx = mallocTables.bin(objSize);
00252         threadData = _threadData;
00253         privateFreeList = publicFreeList = 0;
00254         bumpPtr = data;
00255         int nobjects = MAX_BLOCK_SIZE/objSize;
00256         endPtr = bumpPtr + nobjects*objSize;
00257         almostEmptyThreshold = (nobjects + 1)/2;
00258         allocated = 0;
00259     }
00260 
00261     bool isFilled() const { return allocated > almostEmptyThreshold; }
00262 
00263     size_t signature;
00264     Block* prev;
00265     Block* next;
00266     Node* privateFreeList;
00267     Node* publicFreeList;
00268     uchar* bumpPtr;
00269     uchar* endPtr;
00270     uchar* data;
00271     ThreadData* threadData;
00272     int objSize;
00273     int binIdx;
00274     int allocated;
00275     int almostEmptyThreshold;
00276     CriticalSection cs;
00277 };
00278 
00279 struct BigBlock
00280 {
00281     BigBlock(int bigBlockSize, BigBlock* _next)
00282     {
00283         first = alignPtr((Block*)(this+1), MEM_BLOCK_SIZE);
00284         next = _next;
00285         nblocks = (int)(((char*)this + bigBlockSize - (char*)first)/MEM_BLOCK_SIZE);
00286         Block* p = 0;
00287         for( int i = nblocks-1; i >= 0; i-- )
00288             p = ::new((uchar*)first + i*MEM_BLOCK_SIZE) Block(p);
00289     }
00290 
00291     ~BigBlock()
00292     {
00293         for( int i = nblocks-1; i >= 0; i-- )
00294             ((Block*)((uchar*)first+i*MEM_BLOCK_SIZE))->~Block();
00295     }
00296 
00297     BigBlock* next;
00298     Block* first;
00299     int nblocks;
00300 };
00301 
00302 struct BlockPool
00303 {
00304     BlockPool(int _bigBlockSize=1<<20) : pool(0), bigBlockSize(_bigBlockSize)
00305     {
00306     }
00307 
00308     ~BlockPool()
00309     {
00310         AutoLock lock(cs);
00311         while( pool )
00312         {
00313             BigBlock* nextBlock = pool->next;
00314             pool->~BigBlock();
00315             SystemFree(pool, bigBlockSize);
00316             pool = nextBlock;
00317         }
00318     }
00319 
00320     Block* alloc()
00321     {
00322         AutoLock lock(cs);
00323         Block* block;
00324         if( !freeBlocks )
00325         {
00326             BigBlock* bblock = ::new(SystemAlloc(bigBlockSize)) BigBlock(bigBlockSize, pool);
00327             assert( bblock != 0 );
00328             freeBlocks = bblock->first;
00329             pool = bblock;
00330         }
00331         block = freeBlocks;
00332         freeBlocks = freeBlocks->next;
00333         if( freeBlocks )
00334             freeBlocks->prev = 0;
00335         STAT(stat.bruttoBytes += MEM_BLOCK_SIZE);
00336         return block;
00337     }
00338 
00339     void free(Block* block)
00340     {
00341         AutoLock lock(cs);
00342         block->prev = 0;
00343         block->next = freeBlocks;
00344         freeBlocks = block;
00345         STAT(stat.bruttoBytes -= MEM_BLOCK_SIZE);
00346     }
00347 
00348     CriticalSection cs;
00349     Block* freeBlocks;
00350     BigBlock* pool;
00351     int bigBlockSize;
00352     int blocksPerBigBlock;
00353 };
00354 
00355 BlockPool mallocPool;
00356 
00357 enum { START=0, FREE=1, GC=2 };
00358 
00359 struct ThreadData
00360 {
00361     ThreadData() { for(int i = 0; i <= MAX_BIN; i++) bins[i][START] = bins[i][FREE] = bins[i][GC] = 0; }
00362     ~ThreadData()
00363     {
00364         // mark all the thread blocks as abandoned or even release them
00365         for( int i = 0; i <= MAX_BIN; i++ )
00366         {
00367             Block *bin = bins[i][START], *block = bin;
00368             bins[i][START] = bins[i][FREE] = bins[i][GC] = 0;
00369             if( block )
00370             {
00371                 do
00372                 {
00373                     Block* next = block->next;
00374                     int allocated = block->allocated;
00375                     {
00376                     AutoLock lock(block->cs);
00377                     block->next = block->prev = 0;
00378                     block->threadData = 0;
00379                     Node *node = block->publicFreeList;
00380                     for( ; node != 0; node = node->next )
00381                         allocated--;
00382                     }
00383                     if( allocated == 0 )
00384                         mallocPool.free(block);
00385                     block = next;
00386                 }
00387                 while( block != bin );
00388             }
00389         }
00390     }
00391 
00392     void moveBlockToFreeList( Block* block )
00393     {
00394         int i = block->binIdx;
00395         Block*& freePtr = bins[i][FREE];
00396         CV_DbgAssert( block->next->prev == block && block->prev->next == block );
00397         if( block != freePtr )
00398         {
00399             Block*& gcPtr = bins[i][GC];
00400             if( gcPtr == block )
00401                 gcPtr = block->next;
00402             if( block->next != block )
00403             {
00404                 block->prev->next = block->next;
00405                 block->next->prev = block->prev;
00406             }
00407             block->next = freePtr->next;
00408             block->prev = freePtr;
00409             freePtr = block->next->prev = block->prev->next = block;
00410         }
00411     }
00412 
00413     Block* bins[MAX_BIN+1][3];
00414 
00415 #ifdef WIN32
00416 #ifdef WINCE
00417 #   define TLS_OUT_OF_INDEXES ((DWORD)0xFFFFFFFF)
00418 #endif //WINCE
00419 
00420     static DWORD tlsKey;
00421     static ThreadData* get()
00422     {
00423         ThreadData* data;
00424         if( tlsKey == TLS_OUT_OF_INDEXES )
00425             tlsKey = TlsAlloc();
00426         data = (ThreadData*)TlsGetValue(tlsKey);
00427         if( !data )
00428         {
00429             data = new ThreadData;
00430             TlsSetValue(tlsKey, data);
00431         }
00432         return data;
00433     }
00434 #else //WIN32
00435     static void deleteData(void* data)
00436     {
00437         delete (ThreadData*)data;
00438     }
00439 
00440     static pthread_key_t tlsKey;
00441     static ThreadData* get()
00442     {
00443         ThreadData* data;
00444         if( !tlsKey )
00445             pthread_key_create(&tlsKey, deleteData);
00446         data = (ThreadData*)pthread_getspecific(tlsKey);
00447         if( !data )
00448         {
00449             data = new ThreadData;
00450             pthread_setspecific(tlsKey, data);
00451         }
00452         return data;
00453     }
00454 #endif //WIN32
00455 };
00456 
00457 #ifdef WIN32
00458 DWORD ThreadData::tlsKey = TLS_OUT_OF_INDEXES;
00459 
00460 void deleteThreadAllocData()
00461 {
00462     if( ThreadData::tlsKey != TLS_OUT_OF_INDEXES )
00463         delete (ThreadData*)TlsGetValue( ThreadData::tlsKey );
00464 }
00465 
00466 #else //WIN32
00467 pthread_key_t ThreadData::tlsKey = 0;
00468 #endif //WIN32
00469 
00470 #if 0
00471 static void checkList(ThreadData* tls, int idx)
00472 {
00473     Block* block = tls->bins[idx][START];
00474     if( !block )
00475     {
00476         CV_DbgAssert( tls->bins[idx][FREE] == 0 && tls->bins[idx][GC] == 0 );
00477     }
00478     else
00479     {
00480         bool gcInside = false;
00481         bool freeInside = false;
00482         do
00483         {
00484             if( tls->bins[idx][FREE] == block )
00485                 freeInside = true;
00486             if( tls->bins[idx][GC] == block )
00487                 gcInside = true;
00488             block = block->next;
00489         }
00490         while( block != tls->bins[idx][START] );
00491         CV_DbgAssert( gcInside && freeInside );
00492     }
00493 }
00494 #else
00495 #define checkList(tls, idx)
00496 #endif
00497 
00498 void* fastMalloc( size_t size )
00499 {
00500     if( size > MAX_BLOCK_SIZE )
00501     {
00502         size_t size1 = size + sizeof(uchar*)*2 + MEM_BLOCK_SIZE;
00503         uchar* udata = (uchar*)SystemAlloc(size1);
00504         uchar** adata = alignPtr((uchar**)udata + 2, MEM_BLOCK_SIZE);
00505         adata[-1] = udata;
00506         adata[-2] = (uchar*)size1;
00507         return adata;
00508     }
00509 
00510     {
00511     ThreadData* tls = ThreadData::get();
00512     int idx = mallocTables.bin(size);
00513     Block*& startPtr = tls->bins[idx][START];
00514     Block*& gcPtr = tls->bins[idx][GC];
00515     Block*& freePtr = tls->bins[idx][FREE], *block = freePtr;
00516     checkList(tls, idx);
00517     size = binSizeTab[idx];
00518     STAT(
00519         stat.nettoBytes += size;
00520         stat.mallocCalls++;
00521         );
00522     uchar* data = 0;
00523 
00524     for(;;)
00525     {
00526         if( block )
00527         {
00528             // try to find non-full block
00529             for(;;)
00530             {
00531                 CV_DbgAssert( block->next->prev == block && block->prev->next == block );
00532                 if( block->bumpPtr )
00533                 {
00534                     data = block->bumpPtr;
00535                     if( (block->bumpPtr += size) >= block->endPtr )
00536                         block->bumpPtr = 0;
00537                     break;
00538                 }
00539 
00540                 if( block->privateFreeList )
00541                 {
00542                     data = (uchar*)block->privateFreeList;
00543                     block->privateFreeList = block->privateFreeList->next;
00544                     break;
00545                 }
00546 
00547                 if( block == startPtr )
00548                     break;
00549                 block = block->next;
00550             }
00551 #if 0
00552             avg_k += _k;
00553             avg_nk++;
00554             if( avg_nk == 1000 )
00555             {
00556                 printf("avg search iters per 1e3 allocs = %g\n", (double)avg_k/avg_nk );
00557                 avg_k = avg_nk = 0;
00558             }
00559 #endif
00560 
00561             freePtr = block;
00562             if( !data )
00563             {
00564                 block = gcPtr;
00565                 for( int k = 0; k < 2; k++ )
00566                 {
00567                     SANITY_CHECK(block);
00568                     CV_DbgAssert( block->next->prev == block && block->prev->next == block );
00569                     if( block->publicFreeList )
00570                     {
00571                         {
00572                         AutoLock lock(block->cs);
00573                         block->privateFreeList = block->publicFreeList;
00574                         block->publicFreeList = 0;
00575                         }
00576                         Node* node = block->privateFreeList;
00577                         for(;node != 0; node = node->next)
00578                             --block->allocated;
00579                         data = (uchar*)block->privateFreeList;
00580                         block->privateFreeList = block->privateFreeList->next;
00581                         gcPtr = block->next;
00582                         if( block->allocated+1 <= block->almostEmptyThreshold )
00583                             tls->moveBlockToFreeList(block);
00584                         break;
00585                     }
00586                     block = block->next;
00587                 }
00588                 if( !data )
00589                     gcPtr = block;
00590             }
00591         }
00592 
00593         if( data )
00594             break;
00595         block = mallocPool.alloc();
00596         block->init(startPtr ? startPtr->prev : block, startPtr ? startPtr : block, (int)size, tls);
00597         if( !startPtr )
00598             startPtr = gcPtr = freePtr = block;
00599         checkList(tls, block->binIdx);
00600         SANITY_CHECK(block);
00601     }
00602 
00603     ++block->allocated;
00604     return data;
00605     }
00606 }
00607 
00608 void fastFree( void* ptr )
00609 {
00610     if( ((size_t)ptr & (MEM_BLOCK_SIZE-1)) == 0 )
00611     {
00612         if( ptr != 0 )
00613         {
00614             void* origPtr = ((void**)ptr)[-1];
00615             size_t sz = (size_t)((void**)ptr)[-2];
00616             SystemFree( origPtr, sz );
00617         }
00618         return;
00619     }
00620 
00621     {
00622     ThreadData* tls = ThreadData::get();
00623     Node* node = (Node*)ptr;
00624     Block* block = (Block*)((size_t)ptr & -(int)MEM_BLOCK_SIZE);
00625     assert( block->signature == MEM_BLOCK_SIGNATURE );
00626 
00627     if( block->threadData == tls )
00628     {
00629         STAT(
00630         stat.nettoBytes -= block->objSize;
00631         stat.freeCalls++;
00632         float ratio = (float)stat.nettoBytes/stat.bruttoBytes;
00633         if( stat.minUsageRatio > ratio )
00634             stat.minUsageRatio = ratio;
00635         );
00636 
00637         SANITY_CHECK(block);
00638 
00639         bool prevFilled = block->isFilled();
00640         --block->allocated;
00641         if( !block->isFilled() && (block->allocated == 0 || prevFilled) )
00642         {
00643             if( block->allocated == 0 )
00644             {
00645                 int idx = block->binIdx;
00646                 Block*& startPtr = tls->bins[idx][START];
00647                 Block*& freePtr = tls->bins[idx][FREE];
00648                 Block*& gcPtr = tls->bins[idx][GC];
00649 
00650                 if( block == block->next )
00651                 {
00652                     CV_DbgAssert( startPtr == block && freePtr == block && gcPtr == block );
00653                     startPtr = freePtr = gcPtr = 0;
00654                 }
00655                 else
00656                 {
00657                     if( freePtr == block )
00658                         freePtr = block->next;
00659                     if( gcPtr == block )
00660                         gcPtr = block->next;
00661                     if( startPtr == block )
00662                         startPtr = block->next;
00663                     block->prev->next = block->next;
00664                     block->next->prev = block->prev;
00665                 }
00666                 mallocPool.free(block);
00667                 checkList(tls, idx);
00668                 return;
00669             }
00670 
00671             tls->moveBlockToFreeList(block);
00672         }
00673         node->next = block->privateFreeList;
00674         block->privateFreeList = node;
00675     }
00676     else
00677     {
00678         AutoLock lock(block->cs);
00679         SANITY_CHECK(block);
00680 
00681         node->next = block->publicFreeList;
00682         block->publicFreeList = node;
00683         if( block->threadData == 0 )
00684         {
00685             // take ownership of the abandoned block.
00686             // note that it can happen at the same time as
00687             // ThreadData::deleteData() marks the blocks as abandoned,
00688             // so this part of the algorithm needs to be checked for data races
00689             int idx = block->binIdx;
00690             block->threadData = tls;
00691             Block*& startPtr = tls->bins[idx][START];
00692 
00693             if( startPtr )
00694             {
00695                 block->next = startPtr;
00696                 block->prev = startPtr->prev;
00697                 block->next->prev = block->prev->next = block;
00698             }
00699             else
00700                 startPtr = tls->bins[idx][FREE] = tls->bins[idx][GC] = block;
00701         }
00702     }
00703     }
00704 }
00705 
00706 #endif //CV_USE_SYSTEM_MALLOC
00707 
00708 }
00709 
00710 CV_IMPL void* cvAlloc( size_t size )
00711 {
00712     return cv::fastMalloc( size );
00713 }
00714 
00715 CV_IMPL void cvFree_( void* ptr )
00716 {
00717     cv::fastFree( ptr );
00718 }
00719 
00720 
00721 /* End of file. */
00722