From 4e72e7d79730ea4e137d60e0307b5ba109c3d4a0 Mon Sep 17 00:00:00 2001 From: Sam Lantinga Date: Sun, 16 Jan 2011 15:16:39 -0800 Subject: [PATCH] Added native atomic operations for Windows, Mac OS X, and gcc compiler intrinsics. Changed the CAS return value to bool, so it's efficient with OSAtomicCompareAndSwap32Barrier() Added an atomic test adapted from code by Michael Davidsaver --- .../SDLTest/SDLTest.xcodeproj/project.pbxproj | 7 + configure.in | 28 ++- include/SDL_atomic.h | 65 ++++++- include/SDL_config.h.in | 1 + include/SDL_config_iphoneos.h | 2 + src/atomic/SDL_atomic.c | 61 +++---- src/atomic/SDL_spinlock.c | 27 +-- test/testatomic.c | 172 +++++++++++++++++- 8 files changed, 301 insertions(+), 62 deletions(-) diff --git a/Xcode/SDLTest/SDLTest.xcodeproj/project.pbxproj b/Xcode/SDLTest/SDLTest.xcodeproj/project.pbxproj index bb95f7aae..c27f4a47d 100755 --- a/Xcode/SDLTest/SDLTest.xcodeproj/project.pbxproj +++ b/Xcode/SDLTest/SDLTest.xcodeproj/project.pbxproj @@ -3985,7 +3985,14 @@ isa = PBXProject; buildConfigurationList = 001B5A0C08BDB826006539E9 /* Build configuration list for PBXProject "SDLTest" */; compatibilityVersion = "Xcode 3.0"; + developmentRegion = English; hasScannedForEncodings = 1; + knownRegions = ( + English, + Japanese, + French, + German, + ); mainGroup = 08FB7794FE84155DC02AAC07 /* SDLTest */; projectDirPath = ""; projectReferences = ( diff --git a/configure.in b/configure.in index 4c1ebae16..e682a4613 100644 --- a/configure.in +++ b/configure.in @@ -181,7 +181,7 @@ if test x$enable_dependency_tracking = xyes; then DEPENDENCY_TRACKING_OPTIONS="-MMD -MT \$@" fi fi - + dnl See whether we are allowed to use the system C library AC_ARG_ENABLE(libc, AC_HELP_STRING([--enable-libc], [Use the system C library [[default=yes]]]), @@ -285,6 +285,32 @@ if test x$have_inttypes != xyes; then AC_DEFINE(uintptr_t, unsigned long) fi +dnl See whether we can use gcc atomic operations on this architecture +AC_ARG_ENABLE(gcc-atomics, +AC_HELP_STRING([--enable-gcc-atomics], + [Use gcc builtin atomics [[default=yes]]]), + , enable_gcc_atomics=yes) +if test x$enable_gcc_atomics = xyes; then + have_gcc_atomics=no + AC_MSG_CHECKING(for GCC builtin atomic operations) + AC_TRY_LINK([ + ],[ + int a; + void *x, *y, *z; + __sync_lock_test_and_set(&a, 4); + __sync_fetch_and_add(&a, 1); + __sync_bool_compare_and_swap(&a, 5, 10); + __sync_bool_compare_and_swap(&x, y, z); + ],[ + have_gcc_atomics=yes + ]) + AC_MSG_RESULT($have_gcc_atomics) + + if test x$have_gcc_mmd_mt = xyes; then + AC_DEFINE(HAVE_GCC_ATOMICS) + fi +fi + # Standard C sources SOURCES="$SOURCES $srcdir/src/*.c" SOURCES="$SOURCES $srcdir/src/audio/*.c" diff --git a/include/SDL_atomic.h b/include/SDL_atomic.h index df80c3c68..1c8cf28e6 100644 --- a/include/SDL_atomic.h +++ b/include/SDL_atomic.h @@ -108,7 +108,62 @@ extern DECLSPEC void SDLCALL SDL_AtomicUnlock(SDL_SpinLock *lock); /*@}*//*SDL AtomicLock*/ /* Platform specific optimized versions of the atomic functions */ -/* None yet... */ +#if defined(__WIN32__) +#define WIN32_LEAN_AND_MEAN +#include + +#define SDL_AtomicSet(a, v) InterlockedExchange(&(a)->value, v) +#define SDL_AtomicGet(a) ((a)->value) +#define SDL_AtomicAdd(a, v) InterlockedAdd(&(a)->value, v) +#define SDL_AtomicCAS(a, oldval, newval) (InterlockedCompareExchange(&(a)->value, newval, oldval) == (oldval)) +#define SDL_AtomicSetPtr(a, v) InterlockedExchangePointer(a, v) +#define SDL_AtomicGetPtr(a) (*(a)) +#define SDL_AtomicCASPtr(a, oldval, newval) (InterlockedCompareExchangePointer(a, newval, oldval) == (oldval)) + +#elif defined(__MACOSX__) +#include + +#define SDL_AtomicSet(a, v) \ +({ \ + int oldvalue; \ + \ + do { \ + oldvalue = (a)->value; \ + } while (!OSAtomicCompareAndSwap32Barrier(oldvalue, v, &(a)->value)); \ + \ + oldvalue; \ +}) +#define SDL_AtomicGet(a) ((a)->value) +#define SDL_AtomicAdd(a, v) \ +({ \ + int oldvalue; \ + \ + do { \ + oldvalue = (a)->value; \ + } while (!OSAtomicCompareAndSwap32Barrier(oldvalue, oldvalue+v, &(a)->value)); \ + \ + oldvalue; \ +}) +#define SDL_AtomicCAS(a, oldval, newval) OSAtomicCompareAndSwap32Barrier(oldval, newval, &(a)->value) +#define SDL_AtomicSetPtr(a, v) (*(a) = v, OSMemoryBarrier()) +#define SDL_AtomicGetPtr(a) (*(a)) +#if SIZEOF_VOIDP == 4 +#define SDL_AtomicCASPtr(a, oldval, newval) OSAtomicCompareAndSwap32Barrier((int32_t)(oldval), (int32_t)(newval), (int32_t*)(a)) +#elif SIZEOF_VOIDP == 8 +#define SDL_AtomicCASPtr(a, oldval, newval) OSAtomicCompareAndSwap64Barrier((int64_t)(oldval), (int64_t)(newval), (int64_t*)(a)) +#endif + +#elif defined(HAVE_GCC_ATOMICS) + +#define SDL_AtomicSet(a, v) __sync_lock_test_and_set(&(a)->value, v) +#define SDL_AtomicGet(a) ((a)->value) +#define SDL_AtomicAdd(a, v) __sync_fetch_and_add(&(a)->value, v) +#define SDL_AtomicCAS(a, oldval, newval) __sync_bool_compare_and_swap(&(a)->value, oldval, newval) +#define SDL_AtomicSetPtr(a, v) (*(a) = v, __sync_synchronize()) +#define SDL_AtomicGetPtr(a) (*(a)) +#define SDL_AtomicCASPtr(a, oldval, newval) __sync_bool_compare_and_swap(a, oldval, newval) + +#endif /** * \brief A type representing an atomic integer value. It is a struct @@ -163,12 +218,12 @@ extern DECLSPEC SDL_bool SDLCALL SDL_AtomicDecRef(SDL_atomic_t *a); /** * \brief Set an atomic variable to a new value if it is currently an old value. * - * \return The previous value of the atomic variable + * \return SDL_TRUE if the atomic variable was set, SDL_FALSE otherwise. * * \note If you don't know what this function is for, you shouldn't use it! */ #ifndef SDL_AtomicCAS -extern DECLSPEC int SDLCALL SDL_AtomicCAS(SDL_atomic_t *a, int oldval, int newval); +extern DECLSPEC SDL_bool SDLCALL SDL_AtomicCAS(SDL_atomic_t *a, int oldval, int newval); #endif /** @@ -188,12 +243,12 @@ extern DECLSPEC void* SDLCALL SDL_AtomicGetPtr(void** a); /** * \brief Set a pointer to a new value if it is currently an old value. * - * \return The previous value of the pointer + * \return SDL_TRUE if the pointer was set, SDL_FALSE otherwise. * * \note If you don't know what this function is for, you shouldn't use it! */ #ifndef SDL_AtomicCASPtr -extern DECLSPEC void* SDLCALL SDL_AtomicCASPtr(void **a, void *oldval, void *newval); +extern DECLSPEC SDL_bool SDLCALL SDL_AtomicCASPtr(void **a, void *oldval, void *newval); #endif /* Ends C function definitions when using C++ */ diff --git a/include/SDL_config.h.in b/include/SDL_config.h.in index f99ecb763..1cff0dc69 100644 --- a/include/SDL_config.h.in +++ b/include/SDL_config.h.in @@ -58,6 +58,7 @@ #undef SIZEOF_VOIDP #undef SDL_HAS_64BIT_TYPE +#undef HAVE_GCC_ATOMICS /* Comment this if you want to build without any C library requirements */ #undef HAVE_LIBC diff --git a/include/SDL_config_iphoneos.h b/include/SDL_config_iphoneos.h index 5b27790c0..bc3d876fc 100644 --- a/include/SDL_config_iphoneos.h +++ b/include/SDL_config_iphoneos.h @@ -43,6 +43,8 @@ typedef unsigned long uintptr_t; #define SDL_HAS_64BIT_TYPE 1 +#define HAVE_GCC_ATOMICS 1 + #define HAVE_ALLOCA_H 1 #define HAVE_SYS_TYPES_H 1 #define HAVE_STDIO_H 1 diff --git a/src/atomic/SDL_atomic.c b/src/atomic/SDL_atomic.c index 320c1dd71..50cc7da36 100644 --- a/src/atomic/SDL_atomic.c +++ b/src/atomic/SDL_atomic.c @@ -23,6 +23,12 @@ #include "SDL_atomic.h" +/* Note that we undefine the atomic operations here, in case they are + defined as compiler intrinsics while building SDL but the library user + doesn't have that compiler. That way we always have a working set of + atomic operations built into the library. +*/ + /* If any of the operations are not provided then we must emulate some of them. That means we need a nice implementation of spin locks @@ -51,20 +57,20 @@ static SDL_SpinLock locks[32]; static __inline__ void enterLock(void *a) { - uintptr_t index = ((((uintptr_t)a) >> 3) & 0x1f); + uintptr_t index = ((((uintptr_t)a) >> 3) & 0x1f); - SDL_AtomicLock(&locks[index]); + SDL_AtomicLock(&locks[index]); } static __inline__ void leaveLock(void *a) { - uintptr_t index = ((((uintptr_t)a) >> 3) & 0x1f); + uintptr_t index = ((((uintptr_t)a) >> 3) & 0x1f); - SDL_AtomicUnlock(&locks[index]); + SDL_AtomicUnlock(&locks[index]); } -#ifndef SDL_AtomicSet +#undef SDL_AtomicSet int SDL_AtomicSet(SDL_atomic_t *a, int value) { @@ -77,9 +83,8 @@ SDL_AtomicSet(SDL_atomic_t *a, int value) return oldvalue; } -#endif -#ifndef SDL_AtomicGet +#undef SDL_AtomicGet int SDL_AtomicGet(SDL_atomic_t *a) { @@ -88,9 +93,8 @@ SDL_AtomicGet(SDL_atomic_t *a) */ return a->value; } -#endif -#ifndef SDL_AtomicAdd +#undef SDL_AtomicAdd int SDL_AtomicAdd(SDL_atomic_t *a, int value) { @@ -103,53 +107,48 @@ SDL_AtomicAdd(SDL_atomic_t *a, int value) return oldvalue; } -#endif -#ifndef SDL_AtomicIncRef +#undef SDL_AtomicIncRef void SDL_AtomicIncRef(SDL_atomic_t *a) { SDL_AtomicAdd(a, 1); } -#endif -#ifndef SDL_AtomicDecRef +#undef SDL_AtomicDecRef SDL_bool SDL_AtomicDecRef(SDL_atomic_t *a) { return SDL_AtomicAdd(a, -1) == 1; } -#endif -#ifndef SDL_AtomicCAS -int +#undef SDL_AtomicCAS +SDL_bool SDL_AtomicCAS(SDL_atomic_t *a, int oldval, int newval) { - int prevval; + SDL_bool retval = SDL_FALSE; enterLock(a); - prevval = a->value; - if (prevval == oldval) { + if (a->value == oldval) { a->value = newval; + retval = SDL_TRUE; } leaveLock(a); - return prevval; + return retval; } -#endif -#ifndef SDL_AtomicSetPtr +#undef SDL_AtomicSetPtr void SDL_AtomicSetPtr(void** a, void* value) { void *prevval; do { prevval = *a; - } while (SDL_AtomicCASPtr(a, prevval, value) != prevval); + } while (!SDL_AtomicCASPtr(a, prevval, value)); } -#endif -#ifndef SDL_AtomicGetPtr +#undef SDL_AtomicGetPtr void* SDL_AtomicGetPtr(void** a) { @@ -158,22 +157,20 @@ SDL_AtomicGetPtr(void** a) */ return *a; } -#endif -#ifndef SDL_AtomicCASPtr -void* SDL_AtomicCASPtr(void **a, void *oldval, void *newval) +#undef SDL_AtomicCASPtr +SDL_bool SDL_AtomicCASPtr(void **a, void *oldval, void *newval) { - void *prevval; + SDL_bool retval = SDL_FALSE; enterLock(a); - prevval = *a; if (*a == oldval) { *a = newval; + retval = SDL_TRUE; } leaveLock(a); - return prevval; + return retval; } -#endif /* vi: set ts=4 sw=4 expandtab: */ diff --git a/src/atomic/SDL_spinlock.c b/src/atomic/SDL_spinlock.c index d0631f835..9fbbfd448 100644 --- a/src/atomic/SDL_spinlock.c +++ b/src/atomic/SDL_spinlock.c @@ -44,24 +44,22 @@ SDL_AtomicTryLock(SDL_SpinLock *lock) #elif defined(__MACOSX__) return OSAtomicCompareAndSwap32Barrier(0, 1, lock); -#elif defined(__GNUC__) -#if defined(__arm__) -#ifdef __ARM_ARCH_5__ +#elif defined(HAVE_GCC_ATOMICS) + return (__sync_lock_test_and_set(lock, 1) == 0); + +#elif defined(__GNUC__) && defined(__arm__) && defined(__ARM_ARCH_5__) int result; __asm__ __volatile__ ( "swp %0, %1, [%2]\n" : "=&r,&r" (result) : "r,0" (1), "r,r" (lock) : "memory"); return (result == 0); -#else + +#elif defined(__GNUC__) && defined(__arm__) int result; __asm__ __volatile__ ( "ldrex %0, [%2]\nteq %0, #0\nstrexeq %0, %1, [%2]" : "=&r" (result) : "r" (1), "r" (lock) : "cc", "memory"); return (result == 0); -#endif -#else - return (__sync_lock_test_and_set(lock, 1) == 0); -#endif #else /* Need CPU instructions for spinlock here! */ @@ -81,19 +79,8 @@ SDL_AtomicLock(SDL_SpinLock *lock) void SDL_AtomicUnlock(SDL_SpinLock *lock) { -#if defined(__WIN32__) + /* Assuming atomic assignment operation and full memory barrier in lock */ *lock = 0; - -#elif defined(__MACOSX__) - *lock = 0; - -#elif defined(__GNUC__) && !defined(__arm__) - __sync_lock_release(lock); - -#else - /* Assuming memory barrier in lock and integral assignment operation */ - *lock = 0; -#endif } /* vi: set ts=4 sw=4 expandtab: */ diff --git a/test/testatomic.c b/test/testatomic.c index 85f7b567e..bf845d129 100644 --- a/test/testatomic.c +++ b/test/testatomic.c @@ -1,11 +1,13 @@ #include #include "SDL.h" +#include "SDL_assert.h" /* Absolutely basic tests just to see if we get the expected value after calling each function. */ +static char * tf(SDL_bool tf) { @@ -20,8 +22,8 @@ tf(SDL_bool tf) return f; } -int -main(int argc, char *argv[]) +static +void RunBasicTest() { int value; SDL_SpinLock lock = 0; @@ -58,11 +60,173 @@ main(int argc, char *argv[]) printf("AtomicDecRef() tfret=%s val=%"PRIu32"\n", tf(tfret), SDL_AtomicGet(&v)); SDL_AtomicSet(&v, 10); - tfret = (SDL_AtomicCAS(&v, 0, 20) != 0); + tfret = (SDL_AtomicCAS(&v, 0, 20) == SDL_FALSE); printf("AtomicCAS() tfret=%s val=%"PRIu32"\n", tf(tfret), SDL_AtomicGet(&v)); value = SDL_AtomicGet(&v); - tfret = (SDL_AtomicCAS(&v, value, 20) == value); + tfret = (SDL_AtomicCAS(&v, value, 20) == SDL_TRUE); printf("AtomicCAS() tfret=%s val=%"PRIu32"\n", tf(tfret), SDL_AtomicGet(&v)); +} + +/* Atomic operation test, adapted from code by Michael Davidsaver at: + http://bazaar.launchpad.net/~mdavidsaver/epics-base/atomic/revision/12105#src/libCom/test/epicsAtomicTest.c +*/ + +/* Tests semantics of atomic operations. Also a stress test + * to see if they are really atomic. + * + * Serveral threads adding to the same variable. + * at the end the value is compared with the expected + * and with a non-atomic counter. + */ + +/* Number of concurrent incrementers */ +#define NThreads 2 +#define CountInc 100 +#define VALBITS (sizeof(atomicValue)*8) + +#define atomicValue int +#define CountTo ((atomicValue)((unsigned int)(1<<(VALBITS-1))-1)) +#define NInter (CountTo/CountInc/NThreads) +#define Expect (CountTo-NInter*CountInc*NThreads) + +SDL_COMPILE_TIME_ASSERT(size, CountTo>0); /* check for rollover */ + +static SDL_atomic_t good = { 42 }; + +static atomicValue bad = 42; + +static SDL_atomic_t threadsRunning; + +static SDL_sem *threadDone; + +static +int adder(void* junk) +{ + unsigned long N=NInter; + printf("Thread subtracting %d %lu times\n",CountInc,N); + while (N--) { + SDL_AtomicAdd(&good, -CountInc); + bad-=CountInc; + } + SDL_AtomicAdd(&threadsRunning, -1); + SDL_SemPost(threadDone); + return 0; +} + +static +void runAdder(void) +{ + Uint32 start, end; + int T=NThreads; + + start = SDL_GetTicks(); + + threadDone = SDL_CreateSemaphore(0); + + SDL_AtomicSet(&threadsRunning, NThreads); + + while (T--) + SDL_CreateThread(adder, NULL); + + while (SDL_AtomicGet(&threadsRunning) > 0) + SDL_SemWait(threadDone); + + SDL_DestroySemaphore(threadDone); + + end = SDL_GetTicks(); + + printf("Finished in %f sec\n", (end - start) / 1000.f); +} + +static +void RunEpicTest() +{ + int b; + atomicValue v; + + printf("\nepic test---------------------------------------\n\n"); + printf("Size asserted to be >= 32-bit\n"); + SDL_assert(sizeof(atomicValue)>=4); + + printf("Check static initializer\n"); + v=SDL_AtomicGet(&good); + SDL_assert(v==42); + + SDL_assert(bad==42); + + printf("Test negative values\n"); + SDL_AtomicSet(&good, -5); + v=SDL_AtomicGet(&good); + SDL_assert(v==-5); + + printf("Verify maximum value\n"); + SDL_AtomicSet(&good, CountTo); + v=SDL_AtomicGet(&good); + SDL_assert(v==CountTo); + + printf("Test compare and exchange\n"); + + b=SDL_AtomicCAS(&good, 500, 43); + SDL_assert(!b); /* no swap since CountTo!=500 */ + v=SDL_AtomicGet(&good); + SDL_assert(v==CountTo); /* ensure no swap */ + + b=SDL_AtomicCAS(&good, CountTo, 44); + SDL_assert(!!b); /* will swap */ + v=SDL_AtomicGet(&good); + SDL_assert(v==44); + + printf("Test Add\n"); + + v=SDL_AtomicAdd(&good, 1); + SDL_assert(v==44); + v=SDL_AtomicGet(&good); + SDL_assert(v==45); + + v=SDL_AtomicAdd(&good, 10); + SDL_assert(v==45); + v=SDL_AtomicGet(&good); + SDL_assert(v==55); + + printf("Test Add (Negative values)\n"); + + v=SDL_AtomicAdd(&good, -20); + SDL_assert(v==55); + v=SDL_AtomicGet(&good); + SDL_assert(v==35); + + v=SDL_AtomicAdd(&good, -50); /* crossing zero down */ + SDL_assert(v==35); + v=SDL_AtomicGet(&good); + SDL_assert(v==-15); + + v=SDL_AtomicAdd(&good, 30); /* crossing zero up */ + SDL_assert(v==-15); + v=SDL_AtomicGet(&good); + SDL_assert(v==15); + + printf("Reset before count down test\n"); + SDL_AtomicSet(&good, CountTo); + v=SDL_AtomicGet(&good); + SDL_assert(v==CountTo); + + bad=CountTo; + SDL_assert(bad==CountTo); + + printf("Counting down from %d, Expect %d remaining\n",CountTo,Expect); + runAdder(); + + v=SDL_AtomicGet(&good); + printf("Atomic %d Non-Atomic %d\n",v,bad); + SDL_assert(v==Expect); + SDL_assert(bad!=Expect); +} + +int +main(int argc, char *argv[]) +{ + RunBasicTest(); + RunEpicTest(); return 0; }