Changeset 31660 for trunk/psLib/src/sys/psMemory.c

Timestamp:

Jun 22, 2011, 12:27:33 AM (15 years ago)

Author:

eugene

Message:

merged from eam_branches/ipp-20110505: update memory locking to allow paralled realloc

File:

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

trunk/psLib/src/sys/psMemory.c

@@ -35 +35 @@
 #include "psError.h"    // for psErrorStackPrint() only
 #include "psMemory.h"
+#include "psAbort.h"
 
 // Magic number in psMemBlock header
 #define P_PS_MEMMAGIC (uint32_t)0xdeadbeef
 
+// The psLib memory tools require locking to manipulate the linked list which holds the memory
+// structure.  There are two major options which can be invoked, given below.  
+
+// USE_SPINLOCK replaces the mutex in this code block with a spinlock.  This might be faster in
+// some cases, but probably not enough to matter.  The disadavantages are: (1) programs would
+// need to call the function 'psMemInit' (which they currently do not in general); (2)
+// single-processor machines are poorly set up to use spinlocks; (3) not all compilers /
+// machine combinations support spinlocks.  This option is NOT recommended
+
+// USE_HARDLOCK replaces the per-memBlock locking that is the minimum required to protect the
+// psRealloc function with pure mutex locking that holds the lock during the (possibly
+// expensive) realloc call.  At this point, it does not seem clear that there is a substantial
+// gain in processing speed from using the per-memBlock locking, but more testing may reveal
+// cases where it matters.  
+
+# define USE_SPINLOCK 0
+# define USE_HARDLOCK 0
+
+# if (USE_SPINLOCK) 
+#define MUTEX_LOCK(mutexPtr) \
+if (safeThreads) { \
+    pthread_spin_lock(mutexPtr); \
+}
+#define MUTEX_UNLOCK(mutexPtr) \
+if (safeThreads) { \
+    pthread_spin_unlock(mutexPtr); \
+}
+# else // !USE_SPINLOCK
 #define MUTEX_LOCK(mutexPtr) \
 if (safeThreads) { \
     pthread_mutex_lock(mutexPtr); \
 }
-
 #define MUTEX_UNLOCK(mutexPtr) \
 if (safeThreads) { \
     pthread_mutex_unlock(mutexPtr); \
 }
+# endif // USE_SPINLOCK
 
 // psAbort() calls functions that call psAlloc() so it is *UNSAFE* to use it
@@ -93 +122 @@
 //
 //
+
+# if (USE_SPINLOCK)
+static pthread_spinlock_t memBlockListMutex;
+# else
 static pthread_mutex_t memBlockListMutex = PTHREAD_MUTEX_INITIALIZER;
+# endif
+
+void psMemInit() {
+
+# if (USE_SPINLOCK) 
+    pthread_spin_init(&memBlockListMutex, 0);
+# endif
+
+}
 
 /******** thread safety options management ********/
@@ -325 +367 @@
 }
 
+/** BLOCK_LOCK, BLOCK_UNLOCK, BLOCKSET_LOCK, BLOCKSET_UNLOCK are used to set per-memBlock locks
+ **     to allow psRealloc to release the global lock before performing the expensive system
+ **     call 'realloc'
+ **/
+
+# if (!USE_HARDLOCK)
+static int setLock = 0;
+static int clearLock = 0;
+static int retryLock = 0;
+# endif
+
+# define BLOCK_SLEEP 100
+
+# define MEM_ASSERT(COND,MSG) { if (!(COND)) { fprintf (stderr, MSG); abort(); } }
+
 // pointer to the last mem block that was allocated.
 // This is the root of the entire memory list
 static psMemBlock *lastMemBlockAllocated = NULL;
+
+// set lock on lastMemBlockAllocated
+void BLOCKLAST_LOCK () {
+
+# if (USE_HARDLOCK) 
+    MUTEX_LOCK(&memBlockListMutex);
+# else
+
+    // if memBlock is not defined, we are just asking for a m
+    if (!lastMemBlockAllocated) {
+        MUTEX_LOCK(&memBlockListMutex);
+        return;
+    }
+        
+    while (true) {
+        // set a lock, then lock this memblock and its neighbors
+        MUTEX_LOCK(&memBlockListMutex);
+    
+        // did we beat the race condition?  is the lock still clear?
+        if (lastMemBlockAllocated->inFlight) {
+            // nope, we need to try again
+            MUTEX_UNLOCK(&memBlockListMutex);
+            retryLock ++;
+            usleep (BLOCK_SLEEP);
+            continue;
+        }
+
+        // the marker is ours!
+        lastMemBlockAllocated->inFlight = true;
+        setLock ++;
+        return;
+    }
+# endif
+}
+
+// memBlock->inFlight is a 'soft' lock.  if true, the lock is set
+void BLOCK_LOCK (psMemBlock *memBlock, bool keepMutex) {
+
+# if (USE_HARDLOCK) 
+    MUTEX_LOCK(&memBlockListMutex);
+# else
+
+    MEM_ASSERT (memBlock || keepMutex, "trying to set a soft lock on a non-existent memBlock\n");
+
+    // if memBlock is not defined, we are just asking for a m
+    if (!memBlock) {
+        MUTEX_LOCK(&memBlockListMutex);
+        return;
+    }
+        
+    while (true) {
+        // set a lock, then lock this memblock and its neighbors
+        MUTEX_LOCK(&memBlockListMutex);
+    
+        // did we beat the race condition?  is the lock still clear?
+        if (memBlock->inFlight) {
+            // nope, we need to try again
+            MUTEX_UNLOCK(&memBlockListMutex);
+            usleep (BLOCK_SLEEP);
+            retryLock ++;
+            continue;
+        }
+
+        // the marker is ours!
+        memBlock->inFlight = true;
+        setLock ++;
+        if (keepMutex) return;
+
+        MUTEX_UNLOCK(&memBlockListMutex);
+        return;
+    }
+# endif
+}
+
+void BLOCK_UNLOCK (psMemBlock *memBlock, bool haveMutex) {
+    
+# if (USE_HARDLOCK)
+    MUTEX_UNLOCK(&memBlockListMutex);
+# else
+
+    MEM_ASSERT (memBlock || haveMutex, "trying to clear a soft lock on a non-existent memBlock\n");
+
+    // if memBlock is not defined, we are just asking for a regular lock
+    if (!memBlock) {
+        MUTEX_UNLOCK(&memBlockListMutex);
+        return;
+    }
+
+    MEM_ASSERT (memBlock->inFlight, "trying to clear an unlocked memBlock\n");
+
+    // need to lock before clearing the marker
+    if (!haveMutex) {
+        MUTEX_LOCK(&memBlockListMutex);
+    }
+    memBlock->inFlight = false;
+    clearLock ++;
+    MUTEX_UNLOCK(&memBlockListMutex);
+    return;
+# endif    
+}
+
+// attempt to grab the markers on the given memBlock and its two neighbors.  the only times the
+// two neighbors do not exist is if we are at the beginning or end of the list (or the list is
+// new).
+void BLOCKSET_LOCK (psMemBlock *memBlock, bool keepMutex) {
+
+# if (USE_HARDLOCK)
+    MUTEX_LOCK(&memBlockListMutex);
+# else
+
+    MEM_ASSERT (memBlock, "trying to set a soft lock on a non-existent memBlock\n");
+
+    while (true) {
+        // we cannot set the lock on the marker while the lock is held
+        // wait until all three markers are clear:
+        // while (memBlock->inFlight) { usleep (BLOCK_SLEEP); }
+        // while (memBlock->nextBlock && memBlock->nextBlock->inFlight) { usleep (BLOCK_SLEEP); }
+        // while (memBlock->previousBlock && memBlock->previousBlock->inFlight) { usleep (BLOCK_SLEEP); }
+
+        // set a lock, then lock this memblock and its neighbors
+        MUTEX_LOCK(&memBlockListMutex);
+    
+        // did we beat the race condition?  are all three locks still clear?
+        if (memBlock->inFlight) {
+            // nope, we need to try again
+            MUTEX_UNLOCK(&memBlockListMutex);
+            usleep (BLOCK_SLEEP);
+            retryLock ++;
+            continue;
+        }
+        if (memBlock->nextBlock && memBlock->nextBlock->inFlight) {
+            // nope, we need to try again
+            MUTEX_UNLOCK(&memBlockListMutex);
+            usleep (BLOCK_SLEEP);
+            retryLock ++;
+            continue;
+        }
+        if (memBlock->previousBlock && memBlock->previousBlock->inFlight) {
+            // nope, we need to try again
+            MUTEX_UNLOCK(&memBlockListMutex);
+            usleep (BLOCK_SLEEP);
+            retryLock ++;
+            continue;
+        }
+
+        // the markers are ours!
+        memBlock->inFlight = true;
+        setLock ++;
+        if (memBlock->nextBlock) {
+            memBlock->nextBlock->inFlight = true;
+        }
+        if (memBlock->previousBlock) {
+            memBlock->previousBlock->inFlight = true;
+        }
+        if (keepMutex) return;
+
+        MUTEX_UNLOCK(&memBlockListMutex);
+        return;
+    }
+# endif
+}
+
+void BLOCKSET_UNLOCK (psMemBlock *memBlock, bool haveMutex) {
+    
+# if (USE_HARDLOCK) 
+    MUTEX_UNLOCK(&memBlockListMutex);
+# else
+
+    // need to lock before clearing the marker
+    if (!haveMutex) {
+        MUTEX_LOCK(&memBlockListMutex);
+    }
+    MEM_ASSERT (memBlock->inFlight, "trying to clear an unlocked memBlock\n");
+    memBlock->inFlight = false;
+    clearLock ++;
+    if (memBlock->nextBlock) {
+        MEM_ASSERT (memBlock->nextBlock->inFlight, "trying to clear an unlocked memBlock\n");
+        memBlock->nextBlock->inFlight = false;
+    }
+    if (memBlock->previousBlock) {
+        MEM_ASSERT (memBlock->previousBlock->inFlight, "trying to clear an unlocked memBlock\n");
+        memBlock->previousBlock->inFlight = false;
+    }
+    MUTEX_UNLOCK(&memBlockListMutex);
+    return;
+# endif
+}
 
 /* Actually allocate memory
@@ -365 +609 @@
     // function
     memBlock->func = func;
+
+    // per-block lock (off by default)
+    memBlock->inFlight = false;
 
     #if defined(PS_MEM_BACKTRACE) && defined(HAVE_BACKTRACE)
@@ -394 +641 @@
     memBlock->refCounter = 1;                   // one user so far
 
+    psMemBlock *last0 = lastMemBlockAllocated;
+    int flight0 = (lastMemBlockAllocated) ? lastMemBlockAllocated->inFlight : 10;
+
     // need exclusive access of the memory block list now...
     // this lock is very frequently called in a given program
-    MUTEX_LOCK(&memBlockListMutex);
-
-    // increment the memory id only after we've grabbed the memBlockListMutex
+    // lastMemBlockAllocated is always true except the first allocation
+    BLOCKLAST_LOCK ();
+
+    psMemBlock *last1 = lastMemBlockAllocated;
+    int flight1 = (lastMemBlockAllocated) ? lastMemBlockAllocated->inFlight : 10;
+
+    if (false) {
+        fprintf (stderr, "last 0 : %lld, last 1 : %lld, flight0: %d, flight1: %d\n", (long long int) last0, (long long int) last1, (int) flight0, (int) flight1);
+    }
+
+    // increment the memory id only after we've grabbed the memBlockListMutex this value is
+    // returned by psMemGetID and psMemGetLastID, but only ever modified here
     *(psMemId* )&memBlock->id = ++memid;
 
@@ -415 +674 @@
     }
 
-    MUTEX_UNLOCK(&memBlockListMutex);
+    BLOCK_UNLOCK (memBlock->nextBlock, true);
 
     // And return the user the memory that they allocated
@@ -536 +795 @@
     // Reallocate the memory
 
-    // we need to lock this whole section because we need to be able to adjust
-    // lastMemBlockAllocated if needed (ie, this IS lastMemBlockAllocated)
-    // this lock is frequently called in a given program
-    MUTEX_LOCK(&memBlockListMutex);
+    /* psRealloc and locks: 
+
+       psRealloc calls 'realloc' to change the size of the memory block.  This call is likely
+       to change the address of the memory block itself.  This is a problem because the address
+       of the memory block is referred to by the neighbor blocks via their memBlock->nextBlock
+       and memBlock->previousBlock elements.  If the current memBlock is the first one, then
+       this issue also applies to 'lastMemBlockAllocated'.  The elements may also be modified
+       by psFree and psAlloc.  Thus, we need to prevent multiple threads from calling psFree,
+       psAlloc, or psRealloc on neighbor memory blocks at the same time.
+
+       Unfortunately, unlike psAlloc and psFree, psRealloc cannot perform the (expensive)
+       system call operation (realloc) first and adjust the pointers in separate step (since
+       the value modified by realloc *is* one of those points.  It is thus necessary to include
+       the realloc call within the locked segement, making psRealloc likely to serialize the
+       thread operations.
+
+       Alternatively, we can recognize that the lock only need be applied to operations which
+       are performed on neighboring memBlocks.  We can thus reduce the contention by having a
+       per-memBlock boolean (inFlight) which says the memBlock or a neighbor is being
+       modified.  If psFree and psAlloc respect that boolean, they will not modify a memBlock
+       which is already being realloced (or its neighbor).  In this way, the 'realloc' call can
+       be performed outside of the locked region.
+
+    */
+
+    // set a lock, then lock this memblock and its neighbors.  at the end of this call,
+    // the global mutex is released, but the memBlock and its neighbors are protected
+    BLOCKSET_LOCK (memBlock, false);
+    // MUTEX_LOCK(&memBlockListMutex);
 
     psMemBlock *nextBlock = memBlock->nextBlock;
@@ -549 +833 @@
     bool isBlockLast = (memBlock == lastMemBlockAllocated);
 
+    // do the expensive system call.  other threads can continue to modify other memBlocks
+    // except this one and its two neighbors
     memBlock = (psMemBlock *)realloc(memBlock, sizeof(psMemBlock) + size + sizeof(void *));
     if (memBlock == NULL) {
@@ -582 +868 @@
     }
 
-    MUTEX_UNLOCK(&memBlockListMutex);
+    // all of the list modifications are done; set the lock and clear the per-memBlock locks
+    BLOCKSET_UNLOCK(memBlock, false);
+    // MUTEX_UNLOCK(&memBlockListMutex);
+
+    // XXX these are not actually guaranteed : another thread may already grab them before we get here
+    // psAssert (!memBlock->inFlight, "unreleased lock?");
+    // psAssert (!nextBlock || !nextBlock->inFlight, "unreleased lock?");
+    // psAssert (!previousBlock || !previousBlock->inFlight, "unreleased lock?");
 
     return memBlock + 1;                    // usr memory
@@ -601 +894 @@
     psS32 j = 0;
     psMemBlock *topBlock = lastMemBlockAllocated;
+
+    // XXX move this elsewhere?
+    fprintf (stderr, "set %d locks, cleared %d locks, retry on %d locks (memID %ld)\n", setLock, clearLock, retryLock, memid);
 
     // make sure that the memblock list is free of corruption before we crawl
@@ -808 +1104 @@
     // if we have multiple references, just decrement the count and return.
     // we need a MUTEX_LOCK here: otherwise, two functions can race on refCounter--;
-    MUTEX_LOCK(&memBlockListMutex);
+    BLOCK_LOCK (memBlock, true);
     if (memBlock->refCounter > 1) {
         memBlock->refCounter--;
@@ -816 +1112 @@
             memFreeID += memFreeCallback(memBlock);
         }
-        MUTEX_UNLOCK(&memBlockListMutex);
+        BLOCK_UNLOCK(memBlock, true);
         return ptr;
     }
-    MUTEX_UNLOCK(&memBlockListMutex);
+    BLOCK_UNLOCK(memBlock, true);
 
     // we can't invoke freeFunc() while we're holding memBlockListMutex as it
@@ -828 +1124 @@
 
     // this lock is frequently set in a given program
-    MUTEX_LOCK(&memBlockListMutex);
+    BLOCKSET_LOCK (memBlock, true);
 
     // Did the user ask to be informed about this deallocation?
@@ -849 +1145 @@
     }
 
+    BLOCKSET_UNLOCK (memBlock, true);
+
+    // XXX keep this?
+    psAssert (memBlock->nextBlock == nextBlock, "unexpected rearrangement");
+    psAssert (memBlock->previousBlock == previousBlock, "unexpected rearrangement");
+
     // NULL out the refs so no one can get confused
     memBlock->nextBlock = NULL;
     memBlock->previousBlock = NULL;
 
-    MUTEX_UNLOCK(&memBlockListMutex);
+    // XXX these are not actually guaranteed : another thread may already grab them before we get here
+    // psAssert (!memBlock->inFlight, "unreleased lock?");
+    // psAssert (!nextBlock || !nextBlock->inFlight, "unreleased lock?");
+    // psAssert (!previousBlock || !previousBlock->inFlight, "unreleased lock?");
 
     // invoke free only after we've released the block list lock as free()