Index: /trunk/psLib/src/math/psVectorSmooth.c =================================================================== --- /trunk/psLib/src/math/psVectorSmooth.c (revision 31659) +++ /trunk/psLib/src/math/psVectorSmooth.c (revision 31660) @@ -30,5 +30,5 @@ if (output == input) { psError(PS_ERR_BAD_PARAMETER_VALUE, true, "Cannot smooth vector in-place."); - return false; + return NULL; } @@ -38,4 +38,9 @@ long Nbin = input->n; // Number of elements double factor = -0.5/(sigma*sigma); // Factor for Gaussian + + if (Nbin < Npixel) { + // cannot smooth narrow vector + return NULL; + } #define VECTOR_SMOOTH_CASE(TYPE) \ @@ -60,5 +65,5 @@ /* smooth first Nrange pixels, with renorm */ \ /* XXX need to check that this does not run over end for narrow vectors */ \ - for (long i = 0; i < Nrange; i++, vi++, vo++) { \ + for (long i = 0; i < Nrange; i++, vi++, vo++) { \ ps##TYPE *vr = vi - i; \ ps##TYPE *vg = gauss - i; \ Index: /trunk/psLib/src/sys/psMemory.c =================================================================== --- /trunk/psLib/src/sys/psMemory.c (revision 31659) +++ /trunk/psLib/src/sys/psMemory.c (revision 31660) @@ -35,17 +35,46 @@ #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,5 +122,18 @@ // // + +# 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,7 +367,209 @@ } +/** 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,4 +609,7 @@ // function memBlock->func = func; + + // per-block lock (off by default) + memBlock->inFlight = false; #if defined(PS_MEM_BACKTRACE) && defined(HAVE_BACKTRACE) @@ -394,9 +641,21 @@ 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,5 +674,5 @@ } - MUTEX_UNLOCK(&memBlockListMutex); + BLOCK_UNLOCK (memBlock->nextBlock, true); // And return the user the memory that they allocated @@ -536,8 +795,33 @@ // 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,4 +833,6 @@ 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,5 +868,12 @@ } - 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,4 +894,7 @@ 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,5 +1104,5 @@ // 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,8 +1112,8 @@ 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,5 +1124,5 @@ // 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,9 +1145,18 @@ } + 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() Index: /trunk/psLib/src/sys/psMemory.h =================================================================== --- /trunk/psLib/src/sys/psMemory.h (revision 31659) +++ /trunk/psLib/src/sys/psMemory.h (revision 31660) @@ -73,5 +73,6 @@ psReferenceCount refCounter; ///< how many times pointer is referenced - bool persistent; ///< marks if this non-user persistent data like error stack, etc. + bool persistent; ///< true if this is non-user persistent data like error stack, etc. + bool inFlight; ///< true if a nearby block is being free'ed / realloc'ed (local lock) const uint32_t endblock; ///< initialised to p_psMEMMAGIC } @@ -145,4 +146,7 @@ #endif // ifdef DOXYGEN +// if we decide to use spinlocks for psMemory, it will be necessary to call this function at +// the start of every psLib-based program (spinlocks do not have a static initializer) +void psMemInit(void); /** Set the deallocator routine Index: /trunk/psLib/src/sys/psMemory.txt =================================================================== --- /trunk/psLib/src/sys/psMemory.txt (revision 31660) +++ /trunk/psLib/src/sys/psMemory.txt (revision 31660) @@ -0,0 +1,68 @@ + +2011.05.25 + + notes on the locking needed by psMemory.c: + + The old locking model used a single mutex to block any operations + that affected the memory management data. + + There are a number of operations that are rare, in which case these + locks have almost no performance effect. + + psAlloc and psFree (psMemDecrRefCounter) both are able to perform + the list modification operations (which must be locked) either after + or before the heavy system calls 'alloc' and 'free'. As a result, + these operations do not have a big impact on thread performance. + The big problem is psRealloc. + + 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. + + + psAlloc: + - memBlock is not yet known to any other thread + - outer mutex and marker mutex must be different? + -- this function needs to do a lock & check to grab lastMemBlockAllocated->inFlight + if (lastMemBlockAllocated) { + setLockOnMarker (&lastMemBlockAllocated->inFlight, true); + } else { + set mutex + } + * do stuff + if (memBlock->nextBlock) { + memBlock->nextBlock->inFlight = false; + } + unlock mutex + + psFree: + * setLockOnMarker (&memBlock->inFlight, true); + * initial stuff + * clearLockOnMarker & mutex + + * setLockOnMarkerSet (memBlock, true) + * do stuff + * clearLockOnMarkerSet (memBlock, true)