Changeset 8525

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:

• trunk/psLib/src/sys/psMemory.c (modified) (12 diffs)

trunk/psLib/src/sys/psMemory.c

@@ -8 +8 @@
 *  @author Robert Lupton, Princeton University
 *
-*  @version $Revision: 1.77 $ $Name: not supported by cvs2svn $
-*  @date $Date: 2006-08-21 21:50:09 $
+*  @version $Revision: 1.78 $ $Name: not supported by cvs2svn $
+*  @date $Date: 2006-08-23 22:53:09 $
 *
 *  Copyright 2004-2005 Maui High Performance Computing Center, University of Hawaii
@@ -36 +36 @@
 #include "psRegion.h"
 
-
 #define P_PS_MEMMAGIC (psPtr )0xdeadbeef   // Magic number in psMemBlock header
 
@@ -46 +45 @@
 static pthread_mutex_t memIdMutex = PTHREAD_MUTEX_INITIALIZER;
 
-static pthread_mutex_t recycleMemBlockListMutex = PTHREAD_MUTEX_INITIALIZER;
-
 //private boolean for enabling/disabling thread safety.  Default = enabled.
 static bool safeThreads = true;
@@ -54 +51 @@
 static bool memory_is_persistent = false;
 
-#define N_RECYCLE_BINS 14  // number of recycle bins
-static const psS32 recycleBins = N_RECYCLE_BINS;
-static const psS32 recycleBinSize[N_RECYCLE_BINS] =
+#ifdef PS_MEM_USE_RECYCLE               // Only use recycling if this is set
+#define N_RECYCLE_BINS 14               // number of recycle bins
+#define MAX_RECYCLE 100                 // Maximum number permitted in a recycle bin
+static pthread_mutex_t recycleMemBlockListMutex = PTHREAD_MUTEX_INITIALIZER; // Mutex for recycle bins
+static const psS32 recycleBinSize[N_RECYCLE_BINS] = // Size of each bin
     {
         8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, P_PS_LARGE_BLOCK_SIZE
     };
-
 // N.B. recycleBinSize should be terminated by P_PS_LARGE_BLOCK_SIZE (simplifies search loops)
-static psMemBlock* recycleMemBlockList[N_RECYCLE_BINS] = {
-            NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL
-        };
+static psS32 recycleBinNums[N_RECYCLE_BINS] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; // Number in each bin
+static psMemBlock* recycleMemBlockList[N_RECYCLE_BINS] = // Contents of the bins
+    { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL };
+#endif // #ifdef PS_MEM_USE_RECYCLE
 
 #ifdef PS_MEM_DEBUG
@@ -80 +79 @@
 static psPtr memExhaustedCallbackDefault(size_t size)
 {
+    #if PS_MEM_USE_RECYCLE
     psPtr ptr = NULL;
     if (safeThreads) {
         pthread_mutex_lock(&recycleMemBlockListMutex);
     }
-    psS32 level = recycleBins - 1;
-
-    while (level >= 0 && ptr == NULL) {
-        while (recycleMemBlockList[level] != NULL && ptr == NULL) {
-            psMemBlock* old = recycleMemBlockList[level];
-
-            recycleMemBlockList[level] = recycleMemBlockList[level]->nextBlock;
+    // Attempt to free up everything I can find so I can alloc my ptr
+    int bin = N_RECYCLE_BINS - 1;       // Recycle bin
+
+    while (bin >= 0 && ptr == NULL) {
+        while (recycleMemBlockList[bin] != NULL && ptr == NULL) {
+            psMemBlock *old = recycleMemBlockList[bin];
+            recycleMemBlockList[bin] = recycleMemBlockList[bin]->nextBlock;
             free(old);
             ptr = malloc(size);
         }
-        level--;
+        bin--;
     }
 
@@ -100 +100 @@
         pthread_mutex_unlock(&recycleMemBlockListMutex);
     }
-
     return ptr;
+    #else  // #ifdef PS_MEM_USE_RECYCLE
+
+    return NULL;
+    #endif // #ifdef PS_MEM_USE_RECYCLE
 }
 
@@ -336 +339 @@
 }
 
+#ifdef PS_MEM_USE_RECYCLE
+// Return the appropriate recycle bin number
+static int getRecycleBin(size_t size)
+{
+    if (size >= P_PS_LARGE_BLOCK_SIZE) {
+        return N_RECYCLE_BINS;
+    }
+    int binNum = 0;                     // Recycle bin number
+    while (size > recycleBinSize[binNum]) {
+        binNum++;
+    }
+    return binNum;
+}
+
+// Push a pointer onto the recycle bin
+static void recyclePush(psMemBlock *mb, // Pointer to push
+                        int bin         // Recycling bin
+                       )
+{
+    assert(mb);
+    assert(bin < N_RECYCLE_BINS);
+
+    mb->previousBlock = NULL;
+
+    if (safeThreads) {
+        pthread_mutex_lock(&recycleMemBlockListMutex);
+    }
+
+    mb->nextBlock = recycleMemBlockList[bin];
+    if (recycleMemBlockList[bin] != NULL) {
+        recycleMemBlockList[bin]->previousBlock = mb;
+    }
+    recycleMemBlockList[bin] = mb;
+    recycleBinNums[bin]++;
+
+    if (safeThreads) {
+        pthread_mutex_unlock(&recycleMemBlockListMutex);
+    }
+
+    return;
+}
+
+// Pop a pointer from the recycle bin
+static psMemBlock *recyclePop(int bin   // Recycling bin
+                             )
+{
+    if (bin >= N_RECYCLE_BINS) {
+        return NULL;
+    }
+
+    if (safeThreads) {
+        pthread_mutex_lock(&recycleMemBlockListMutex);
+    }
+
+    psMemBlock *mb = recycleMemBlockList[bin]; // Pointer popped from recycle bin
+
+    if (mb) {
+        // We pull it off the list
+        recycleMemBlockList[bin] = mb->nextBlock;
+        if (recycleMemBlockList[bin] != NULL) {
+            recycleMemBlockList[bin]->previousBlock = NULL;
+        }
+        recycleBinNums[bin]--;
+    }
+
+    if (safeThreads) {
+        pthread_mutex_unlock(&recycleMemBlockListMutex);
+    }
+
+    return mb;
+}
+#endif // #ifdef PS_MEM_USE_RECYCLE
+
 /*
  * Actually allocate memory
@@ -344 +420 @@
 {
 
-    psMemBlock* ptr = NULL;
-
-    size = (size < recycleBinSize[0]) ? recycleBinSize[0] : size; // set the minimum size to allocate
-
-    // memory is of the size I want to bother recycling?
-    if (size < P_PS_LARGE_BLOCK_SIZE) {
-        // find the bin we need.
-        psS32 level = 0;
-
-        while (size > recycleBinSize[level]) {
-            level++;
-        }
-        // Are we in one of the bins
-        if (level < recycleBins) {
-
-            size = recycleBinSize[level];  // round-up size to next sized bin.
-
-            if (safeThreads) {
-                pthread_mutex_lock(&recycleMemBlockListMutex);
-            }
-
-            if (recycleMemBlockList[level] != NULL) {
-                ptr = recycleMemBlockList[level];
-                recycleMemBlockList[level] = ptr->nextBlock;
-                if (recycleMemBlockList[level] != NULL) {
-                    recycleMemBlockList[level]->previousBlock = NULL;
-                }
-                size = ptr->userMemorySize;
-            }
-
-            if (safeThreads) {
-                pthread_mutex_unlock(&recycleMemBlockListMutex);
-            }
-        }
-    }
+    psMemBlock *ptr = NULL;
+
+    #ifdef PS_MEM_USE_RECYCLE
+    // Are we in one of the recycle bins?
+    int bin = getRecycleBin(size);
+    if (bin < N_RECYCLE_BINS) {
+        size = recycleBinSize[bin];     // round-up size to next sized bin.
+        ptr = recyclePop(bin);          // grab out of the recycle bin
+    }
+    #endif // #ifdef PS_MEM_USE_RECYCLE
 
     if (ptr == NULL) {
@@ -443 +494 @@
                   unsigned int lineno)
 {
-    size = (size < recycleBinSize[0]) ? recycleBinSize[0] : size; // set the minimum size to allocate
-
     if (vptr == NULL) {
         return p_psAlloc(size, file, lineno);
-    } else {
-        psMemBlock* ptr = ((psMemBlock* ) vptr) - 1;
-        psBool isBlockLast = false;
-
-        if (checkMemBlock(ptr, __func__) != 0) {
-            memProblemCallback(ptr, file, lineno);
-            psAbort(file, "Realloc detected a memory corruption (id %lu @ %s:%d).",
-                    (unsigned long)ptr->id, ptr->file, ptr->lineno);
-        }
-
-        if (size <= ptr->userMemorySize) {
-            ;    // nothing to do
-        } else {
-            isBlockLast = (ptr == lastMemBlockAllocated);
-
-            psPtr *nvptr = p_psAlloc(size, file, lineno);
-            psMemBlock *nptr = ((psMemBlock *)nvptr) - 1;
-            memcpy(nvptr, vptr, ptr->userMemorySize < size ? ptr->userMemorySize : size);
-            *(psMemId *)&nptr->id = ptr->id;
-            nptr->persistent = ptr->persistent;
-
-            psFree(vptr);
-            ptr = nptr;
-        }
-
-        // Did the user ask to be informed about this allocation?
-        if (ptr->id == p_psMemAllocID) {
-            p_psMemAllocID += memAllocCallback(ptr);
-        }
-
-        return ptr + 1;                    // usr memory
-    }
+    }
+
+    psMemBlock *ptr = ((psMemBlock*)vptr) - 1;
+
+    if (checkMemBlock(ptr, __func__) != 0) {
+        memProblemCallback(ptr, file, lineno);
+        psAbort(file, "Realloc detected a memory corruption (id %lu @ %s:%d).",
+                (unsigned long)ptr->id, ptr->file, ptr->lineno);
+    }
+
+    #ifdef PS_MEM_USE_RECYCLE
+    // Ensure the size matches that of the recycle bin
+    int bin = getRecycleBin(size);
+    if (bin < N_RECYCLE_BINS) {
+        size = recycleBinSize[bin];     // round-up size to next sized bin.
+    }
+    #endif // #ifdef PS_MEM_USE_RECYCLE
+
+    if (size == ptr->userMemorySize) {
+        // Nothing to do
+        return vptr;
+    }
+
+    // Reallocate the memory
+
+    if (safeThreads) {
+        pthread_mutex_lock(&memBlockListMutex);
+    }
+
+    bool isBlockLast = (ptr == lastMemBlockAllocated); // Is this the last block we allocated?
+    ptr = (psMemBlock *)realloc(ptr, sizeof(psMemBlock) + size + sizeof(psPtr));
+    if (ptr == NULL) {
+        ptr = memExhaustedCallback(size);
+        if (ptr == NULL) {
+            psAbort(__func__, "Failed to reallocate %ld bytes at %s:%d", size, file, lineno);
+        }
+    }
+
+    ptr->userMemorySize = size;
+    *(psPtr *)((int8_t *) (ptr + 1) + size) = P_PS_MEMMAGIC;
+
+    if (isBlockLast) {
+        lastMemBlockAllocated = ptr;
+    }
+
+    // the block location may have changed, so fix the linked list addresses.
+    if (ptr->nextBlock != NULL) {
+        ptr->nextBlock->previousBlock = ptr;
+    }
+    if (ptr->previousBlock != NULL) {
+        ptr->previousBlock->nextBlock = ptr;
+    }
+
+    if (safeThreads) {
+        pthread_mutex_unlock(&memBlockListMutex);
+    }
+
+    // Did the user ask to be informed about this allocation?
+    if (ptr->id == p_psMemAllocID) {
+        p_psMemAllocID += memAllocCallback(ptr);
+    }
+
+    return ptr + 1;                    // usr memory
 }
 
@@ -728 +808 @@
         }
 
-        // do we need to recycle?
-        if (ptr->userMemorySize < P_PS_LARGE_BLOCK_SIZE) {
-
-            psS32 level = 1;
-
-            while (ptr->userMemorySize >= recycleBinSize[level]) {
-                level++;
-            }
-            level--;
-
+        #ifdef PS_MEM_USE_RECYCLE
+        // do we recycle?
+        int bin = getRecycleBin(ptr->userMemorySize);
+        if (bin < N_RECYCLE_BINS && recycleBinNums[bin] < MAX_RECYCLE) {
             ptr->refCounter = 0;
-            ptr->previousBlock = NULL;
-
-            if (safeThreads) {
-                pthread_mutex_lock(&recycleMemBlockListMutex);
-            }
-            ptr->nextBlock = recycleMemBlockList[level];
-            if (recycleMemBlockList[level] != NULL) {
-                recycleMemBlockList[level]->previousBlock = ptr;
-            }
-            recycleMemBlockList[level] = ptr;
-            if (safeThreads) {
-                pthread_mutex_unlock(&recycleMemBlockListMutex);
-            }
-
-        } else {
-            // memory is larger than I want to recycle.
-            #ifdef PS_MEM_DEBUG
-            (void)p_psRealloc(vptr, 0, file, lineno);
-            ptr->previousBlock = NULL;
-            ptr->nextBlock = deadBlockList;
-            if (deadBlockList != NULL) {
+            recyclePush(ptr, bin);
+        } else
+            #endif  // #ifdef PS_MEM_USE_RECYCLE
+            {
+                // memory is larger than I want to recycle.
+                #ifdef PS_MEM_DEBUG
+                (void)p_psRealloc(vptr, 0, file, lineno);
+                ptr->previousBlock = NULL;
+                ptr->nextBlock = deadBlockList;
+                if (deadBlockList != NULL) {
                 deadBlockList->previous = ptr;
             }
-            deadBlockList = ptr;
-            #else // #ifdef PS_MEM_DEBUG
-
-            if (safeThreads) {
-                pthread_mutex_destroy(&ptr->refCounterMutex);
+        deadBlockList = ptr;
+        #else // #ifdef PS_MEM_DEBUG
+
+        if (safeThreads) {
+            pthread_mutex_destroy(&ptr->refCounterMutex);
             }
             free(ptr);
@@ -1201 +1264 @@
     *freelist = 0;
     int nblock_tot = 0;
-    for (int i = 0; ; i++) {
-        if (recycleBinSize[i] == P_PS_LARGE_BLOCK_SIZE) {
-            break;
-        }
+    #ifdef PS_MEM_USE_RECYCLE
+
+    for (int i = 0; recycleBinSize[i] < P_PS_LARGE_BLOCK_SIZE; i++) {
         size_t bin_contents = 0;
         size_t nblock = 0;
@@ -1218 +1280 @@
         }
     }
+    #endif // #ifdef PS_MEM_USE_RECYCLE
+
     if (print) {
         printf("Freelist   %6s  %10d %8d\n", "", *freelist, nblock_tot);
     }
 
+
     if (safeThreads) {
         pthread_mutex_unlock(&memBlockListMutex);