IPP Software Navigation Tools IPP Links Communication Pan-STARRS Links

Ignore:
Timestamp:
Aug 23, 2006, 12:53:09 PM (20 years ago)
Author:
Paul Price
Message:

See bugs 801, 803. The recycling mechanism assumed that the spectrum
of memory sizes is flat in log space. When this assumption is
violated (e.g., by continually demanding a certain size that is not
returned as the same size: psAlloc, psRealloc to different recycle bin
size, psFree all in a tight loop), then all bets are off, and the
memory footprint will keep expanding. I enforce this assumption by
setting a maximum limit to the number in any recycle bin. The
previous fix to this problem (having psRealloc to use psAlloc and
copying the memory over) is slow. I also did some benchmarks (ten
million psAllocs followed by psFree, with and without recycling) and
found that the use of the recycle bins really don't help in terms of
time expended. This means that the system malloc (at least, on my
linux box) is better at recycling than the PS memory system, so we can
just trust that. Therefore, I have #ifdef-ed out the recycling code.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/psLib/src/sys/psMemory.c

    r8440 r8525  
    88*  @author Robert Lupton, Princeton University
    99*
    10 *  @version $Revision: 1.77 $ $Name: not supported by cvs2svn $
    11 *  @date $Date: 2006-08-21 21:50:09 $
     10*  @version $Revision: 1.78 $ $Name: not supported by cvs2svn $
     11*  @date $Date: 2006-08-23 22:53:09 $
    1212*
    1313*  Copyright 2004-2005 Maui High Performance Computing Center, University of Hawaii
    … …  
    3636#include "psRegion.h"
    3737
    38 
    3938#define P_PS_MEMMAGIC (psPtr )0xdeadbeef   // Magic number in psMemBlock header
    4039
    … …  
    4645static pthread_mutex_t memIdMutex = PTHREAD_MUTEX_INITIALIZER;
    4746
    48 static pthread_mutex_t recycleMemBlockListMutex = PTHREAD_MUTEX_INITIALIZER;
    49 
    5047//private boolean for enabling/disabling thread safety.  Default = enabled.
    5148static bool safeThreads = true;
    … …  
    5451static bool memory_is_persistent = false;
    5552
    56 #define N_RECYCLE_BINS 14  // number of recycle bins
    57 static const psS32 recycleBins = N_RECYCLE_BINS;
    58 static const psS32 recycleBinSize[N_RECYCLE_BINS] =
     53#ifdef PS_MEM_USE_RECYCLE               // Only use recycling if this is set
     54#define N_RECYCLE_BINS 14               // number of recycle bins
     55#define MAX_RECYCLE 100                 // Maximum number permitted in a recycle bin
     56static pthread_mutex_t recycleMemBlockListMutex = PTHREAD_MUTEX_INITIALIZER; // Mutex for recycle bins
     57static const psS32 recycleBinSize[N_RECYCLE_BINS] = // Size of each bin
    5958    {
    6059        8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, P_PS_LARGE_BLOCK_SIZE
    6160    };
    62 
    6361// N.B. recycleBinSize should be terminated by P_PS_LARGE_BLOCK_SIZE (simplifies search loops)
    64 static psMemBlock* recycleMemBlockList[N_RECYCLE_BINS] = {
    65             NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL
    66         };
     62static psS32 recycleBinNums[N_RECYCLE_BINS] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; // Number in each bin
     63static psMemBlock* recycleMemBlockList[N_RECYCLE_BINS] = // Contents of the bins
     64    { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL };
     65#endif // #ifdef PS_MEM_USE_RECYCLE
    6766
    6867#ifdef PS_MEM_DEBUG
    … …  
    8079static psPtr memExhaustedCallbackDefault(size_t size)
    8180{
     81    #if PS_MEM_USE_RECYCLE
    8282    psPtr ptr = NULL;
    8383    if (safeThreads) {
    8484        pthread_mutex_lock(&recycleMemBlockListMutex);
    8585    }
    86     psS32 level = recycleBins - 1;
    87 
    88     while (level >= 0 && ptr == NULL) {
    89         while (recycleMemBlockList[level] != NULL && ptr == NULL) {
    90             psMemBlock* old = recycleMemBlockList[level];
    91 
    92             recycleMemBlockList[level] = recycleMemBlockList[level]->nextBlock;
     86    // Attempt to free up everything I can find so I can alloc my ptr
     87    int bin = N_RECYCLE_BINS - 1;       // Recycle bin
     88
     89    while (bin >= 0 && ptr == NULL) {
     90        while (recycleMemBlockList[bin] != NULL && ptr == NULL) {
     91            psMemBlock *old = recycleMemBlockList[bin];
     92            recycleMemBlockList[bin] = recycleMemBlockList[bin]->nextBlock;
    9393            free(old);
    9494            ptr = malloc(size);
    9595        }
    96         level--;
     96        bin--;
    9797    }
    9898
    … …  
    100100        pthread_mutex_unlock(&recycleMemBlockListMutex);
    101101    }
    102 
    103102    return ptr;
     103    #else  // #ifdef PS_MEM_USE_RECYCLE
     104
     105    return NULL;
     106    #endif // #ifdef PS_MEM_USE_RECYCLE
    104107}
    105108
    … …  
    336339}
    337340
     341#ifdef PS_MEM_USE_RECYCLE
     342// Return the appropriate recycle bin number
     343static int getRecycleBin(size_t size)
     344{
     345    if (size >= P_PS_LARGE_BLOCK_SIZE) {
     346        return N_RECYCLE_BINS;
     347    }
     348    int binNum = 0;                     // Recycle bin number
     349    while (size > recycleBinSize[binNum]) {
     350        binNum++;
     351    }
     352    return binNum;
     353}
     354
     355// Push a pointer onto the recycle bin
     356static void recyclePush(psMemBlock *mb, // Pointer to push
     357                        int bin         // Recycling bin
     358                       )
     359{
     360    assert(mb);
     361    assert(bin < N_RECYCLE_BINS);
     362
     363    mb->previousBlock = NULL;
     364
     365    if (safeThreads) {
     366        pthread_mutex_lock(&recycleMemBlockListMutex);
     367    }
     368
     369    mb->nextBlock = recycleMemBlockList[bin];
     370    if (recycleMemBlockList[bin] != NULL) {
     371        recycleMemBlockList[bin]->previousBlock = mb;
     372    }
     373    recycleMemBlockList[bin] = mb;
     374    recycleBinNums[bin]++;
     375
     376    if (safeThreads) {
     377        pthread_mutex_unlock(&recycleMemBlockListMutex);
     378    }
     379
     380    return;
     381}
     382
     383// Pop a pointer from the recycle bin
     384static psMemBlock *recyclePop(int bin   // Recycling bin
     385                             )
     386{
     387    if (bin >= N_RECYCLE_BINS) {
     388        return NULL;
     389    }
     390
     391    if (safeThreads) {
     392        pthread_mutex_lock(&recycleMemBlockListMutex);
     393    }
     394
     395    psMemBlock *mb = recycleMemBlockList[bin]; // Pointer popped from recycle bin
     396
     397    if (mb) {
     398        // We pull it off the list
     399        recycleMemBlockList[bin] = mb->nextBlock;
     400        if (recycleMemBlockList[bin] != NULL) {
     401            recycleMemBlockList[bin]->previousBlock = NULL;
     402        }
     403        recycleBinNums[bin]--;
     404    }
     405
     406    if (safeThreads) {
     407        pthread_mutex_unlock(&recycleMemBlockListMutex);
     408    }
     409
     410    return mb;
     411}
     412#endif // #ifdef PS_MEM_USE_RECYCLE
     413
    338414/*
    339415 * Actually allocate memory
    … …  
    344420{
    345421
    346     psMemBlock* ptr = NULL;
    347 
    348     size = (size < recycleBinSize[0]) ? recycleBinSize[0] : size; // set the minimum size to allocate
    349 
    350     // memory is of the size I want to bother recycling?
    351     if (size < P_PS_LARGE_BLOCK_SIZE) {
    352         // find the bin we need.
    353         psS32 level = 0;
    354 
    355         while (size > recycleBinSize[level]) {
    356             level++;
    357         }
    358         // Are we in one of the bins
    359         if (level < recycleBins) {
    360 
    361             size = recycleBinSize[level];  // round-up size to next sized bin.
    362 
    363             if (safeThreads) {
    364                 pthread_mutex_lock(&recycleMemBlockListMutex);
    365             }
    366 
    367             if (recycleMemBlockList[level] != NULL) {
    368                 ptr = recycleMemBlockList[level];
    369                 recycleMemBlockList[level] = ptr->nextBlock;
    370                 if (recycleMemBlockList[level] != NULL) {
    371                     recycleMemBlockList[level]->previousBlock = NULL;
    372                 }
    373                 size = ptr->userMemorySize;
    374             }
    375 
    376             if (safeThreads) {
    377                 pthread_mutex_unlock(&recycleMemBlockListMutex);
    378             }
    379         }
    380     }
     422    psMemBlock *ptr = NULL;
     423
     424    #ifdef PS_MEM_USE_RECYCLE
     425    // Are we in one of the recycle bins?
     426    int bin = getRecycleBin(size);
     427    if (bin < N_RECYCLE_BINS) {
     428        size = recycleBinSize[bin];     // round-up size to next sized bin.
     429        ptr = recyclePop(bin);          // grab out of the recycle bin
     430    }
     431    #endif // #ifdef PS_MEM_USE_RECYCLE
    381432
    382433    if (ptr == NULL) {
    … …  
    443494                  unsigned int lineno)
    444495{
    445     size = (size < recycleBinSize[0]) ? recycleBinSize[0] : size; // set the minimum size to allocate
    446 
    447496    if (vptr == NULL) {
    448497        return p_psAlloc(size, file, lineno);
    449     } else {
    450         psMemBlock* ptr = ((psMemBlock* ) vptr) - 1;
    451         psBool isBlockLast = false;
    452 
    453         if (checkMemBlock(ptr, __func__) != 0) {
    454             memProblemCallback(ptr, file, lineno);
    455             psAbort(file, "Realloc detected a memory corruption (id %lu @ %s:%d).",
    456                     (unsigned long)ptr->id, ptr->file, ptr->lineno);
    457         }
    458 
    459         if (size <= ptr->userMemorySize) {
    460             ;    // nothing to do
    461         } else {
    462             isBlockLast = (ptr == lastMemBlockAllocated);
    463 
    464             psPtr *nvptr = p_psAlloc(size, file, lineno);
    465             psMemBlock *nptr = ((psMemBlock *)nvptr) - 1;
    466             memcpy(nvptr, vptr, ptr->userMemorySize < size ? ptr->userMemorySize : size);
    467             *(psMemId *)&nptr->id = ptr->id;
    468             nptr->persistent = ptr->persistent;
    469 
    470             psFree(vptr);
    471             ptr = nptr;
    472         }
    473 
    474         // Did the user ask to be informed about this allocation?
    475         if (ptr->id == p_psMemAllocID) {
    476             p_psMemAllocID += memAllocCallback(ptr);
    477         }
    478 
    479         return ptr + 1;                    // usr memory
    480     }
     498    }
     499
     500    psMemBlock *ptr = ((psMemBlock*)vptr) - 1;
     501
     502    if (checkMemBlock(ptr, __func__) != 0) {
     503        memProblemCallback(ptr, file, lineno);
     504        psAbort(file, "Realloc detected a memory corruption (id %lu @ %s:%d).",
     505                (unsigned long)ptr->id, ptr->file, ptr->lineno);
     506    }
     507
     508    #ifdef PS_MEM_USE_RECYCLE
     509    // Ensure the size matches that of the recycle bin
     510    int bin = getRecycleBin(size);
     511    if (bin < N_RECYCLE_BINS) {
     512        size = recycleBinSize[bin];     // round-up size to next sized bin.
     513    }
     514    #endif // #ifdef PS_MEM_USE_RECYCLE
     515
     516    if (size == ptr->userMemorySize) {
     517        // Nothing to do
     518        return vptr;
     519    }
     520
     521    // Reallocate the memory
     522
     523    if (safeThreads) {
     524        pthread_mutex_lock(&memBlockListMutex);
     525    }
     526
     527    bool isBlockLast = (ptr == lastMemBlockAllocated); // Is this the last block we allocated?
     528    ptr = (psMemBlock *)realloc(ptr, sizeof(psMemBlock) + size + sizeof(psPtr));
     529    if (ptr == NULL) {
     530        ptr = memExhaustedCallback(size);
     531        if (ptr == NULL) {
     532            psAbort(__func__, "Failed to reallocate %ld bytes at %s:%d", size, file, lineno);
     533        }
     534    }
     535
     536    ptr->userMemorySize = size;
     537    *(psPtr *)((int8_t *) (ptr + 1) + size) = P_PS_MEMMAGIC;
     538
     539    if (isBlockLast) {
     540        lastMemBlockAllocated = ptr;
     541    }
     542
     543    // the block location may have changed, so fix the linked list addresses.
     544    if (ptr->nextBlock != NULL) {
     545        ptr->nextBlock->previousBlock = ptr;
     546    }
     547    if (ptr->previousBlock != NULL) {
     548        ptr->previousBlock->nextBlock = ptr;
     549    }
     550
     551    if (safeThreads) {
     552        pthread_mutex_unlock(&memBlockListMutex);
     553    }
     554
     555    // Did the user ask to be informed about this allocation?
     556    if (ptr->id == p_psMemAllocID) {
     557        p_psMemAllocID += memAllocCallback(ptr);
     558    }
     559
     560    return ptr + 1;                    // usr memory
    481561}
    482562
    … …  
    728808        }
    729809
    730         // do we need to recycle?
    731         if (ptr->userMemorySize < P_PS_LARGE_BLOCK_SIZE) {
    732 
    733             psS32 level = 1;
    734 
    735             while (ptr->userMemorySize >= recycleBinSize[level]) {
    736                 level++;
    737             }
    738             level--;
    739 
     810        #ifdef PS_MEM_USE_RECYCLE
     811        // do we recycle?
     812        int bin = getRecycleBin(ptr->userMemorySize);
     813        if (bin < N_RECYCLE_BINS && recycleBinNums[bin] < MAX_RECYCLE) {
    740814            ptr->refCounter = 0;
    741             ptr->previousBlock = NULL;
    742 
    743             if (safeThreads) {
    744                 pthread_mutex_lock(&recycleMemBlockListMutex);
    745             }
    746             ptr->nextBlock = recycleMemBlockList[level];
    747             if (recycleMemBlockList[level] != NULL) {
    748                 recycleMemBlockList[level]->previousBlock = ptr;
    749             }
    750             recycleMemBlockList[level] = ptr;
    751             if (safeThreads) {
    752                 pthread_mutex_unlock(&recycleMemBlockListMutex);
    753             }
    754 
    755         } else {
    756             // memory is larger than I want to recycle.
    757             #ifdef PS_MEM_DEBUG
    758             (void)p_psRealloc(vptr, 0, file, lineno);
    759             ptr->previousBlock = NULL;
    760             ptr->nextBlock = deadBlockList;
    761             if (deadBlockList != NULL) {
     815            recyclePush(ptr, bin);
     816        } else
     817            #endif  // #ifdef PS_MEM_USE_RECYCLE
     818            {
     819                // memory is larger than I want to recycle.
     820                #ifdef PS_MEM_DEBUG
     821                (void)p_psRealloc(vptr, 0, file, lineno);
     822                ptr->previousBlock = NULL;
     823                ptr->nextBlock = deadBlockList;
     824                if (deadBlockList != NULL) {
    762825                deadBlockList->previous = ptr;
    763826            }
    764             deadBlockList = ptr;
    765             #else // #ifdef PS_MEM_DEBUG
    766 
    767             if (safeThreads) {
    768                 pthread_mutex_destroy(&ptr->refCounterMutex);
     827        deadBlockList = ptr;
     828        #else // #ifdef PS_MEM_DEBUG
     829
     830        if (safeThreads) {
     831            pthread_mutex_destroy(&ptr->refCounterMutex);
    769832            }
    770833            free(ptr);
    … …  
    12011264    *freelist = 0;
    12021265    int nblock_tot = 0;
    1203     for (int i = 0; ; i++) {
    1204         if (recycleBinSize[i] == P_PS_LARGE_BLOCK_SIZE) {
    1205             break;
    1206         }
     1266    #ifdef PS_MEM_USE_RECYCLE
     1267
     1268    for (int i = 0; recycleBinSize[i] < P_PS_LARGE_BLOCK_SIZE; i++) {
    12071269        size_t bin_contents = 0;
    12081270        size_t nblock = 0;
    … …  
    12181280        }
    12191281    }
     1282    #endif // #ifdef PS_MEM_USE_RECYCLE
     1283
    12201284    if (print) {
    12211285        printf("Freelist   %6s  %10d %8d\n", "", *freelist, nblock_tot);
    12221286    }
    12231287
     1288
    12241289    if (safeThreads) {
    12251290        pthread_mutex_unlock(&memBlockListMutex);
Note: See TracChangeset for help on using the changeset viewer.