test/testatomic.c
author Sam Lantinga <slouken@libsdl.org>
Tue, 25 Jan 2011 23:23:52 -0800
changeset 5098 470ede30189c
parent 5018 342b158efbbe
child 5099 1b3678ac9804
permissions -rw-r--r--
Added a FIFO test to the atomic test suite.
This is really useful because we might be able to use something like this
for the SDL event queue.
     1 #include <stdio.h>
     2 
     3 #include "SDL.h"
     4 #include "SDL_atomic.h"
     5 #include "SDL_assert.h"
     6 
     7 /*
     8   Absolutely basic tests just to see if we get the expected value
     9   after calling each function.
    10 */
    11 
    12 static
    13 char *
    14 tf(SDL_bool tf)
    15 {
    16     static char *t = "TRUE";
    17     static char *f = "FALSE";
    18 
    19     if (tf)
    20     {
    21        return t;
    22     }
    23 
    24     return f;
    25 }
    26 
    27 static
    28 void RunBasicTest()
    29 {
    30     int value;
    31     SDL_SpinLock lock = 0;
    32 
    33     SDL_atomic_t v;
    34     SDL_bool tfret = SDL_FALSE;
    35 
    36     printf("\nspin lock---------------------------------------\n\n");
    37 
    38     SDL_AtomicLock(&lock);
    39     printf("AtomicLock                   lock=%d\n", lock);
    40     SDL_AtomicUnlock(&lock);
    41     printf("AtomicUnlock                 lock=%d\n", lock);
    42 
    43     printf("\natomic -----------------------------------------\n\n");
    44      
    45     SDL_AtomicSet(&v, 0);
    46     tfret = SDL_AtomicSet(&v, 10) == 0;
    47     printf("AtomicSet(10)        tfret=%s val=%d\n", tf(tfret), SDL_AtomicGet(&v));
    48     tfret = SDL_AtomicAdd(&v, 10) == 10;
    49     printf("AtomicAdd(10)        tfret=%s val=%d\n", tf(tfret), SDL_AtomicGet(&v));
    50 
    51     SDL_AtomicSet(&v, 0);
    52     SDL_AtomicIncRef(&v);
    53     tfret = (SDL_AtomicGet(&v) == 1);
    54     printf("AtomicIncRef()       tfret=%s val=%d\n", tf(tfret), SDL_AtomicGet(&v));
    55     SDL_AtomicIncRef(&v);
    56     tfret = (SDL_AtomicGet(&v) == 2);
    57     printf("AtomicIncRef()       tfret=%s val=%d\n", tf(tfret), SDL_AtomicGet(&v));
    58     tfret = (SDL_AtomicDecRef(&v) == SDL_FALSE);
    59     printf("AtomicDecRef()       tfret=%s val=%d\n", tf(tfret), SDL_AtomicGet(&v));
    60     tfret = (SDL_AtomicDecRef(&v) == SDL_TRUE);
    61     printf("AtomicDecRef()       tfret=%s val=%d\n", tf(tfret), SDL_AtomicGet(&v));
    62 
    63     SDL_AtomicSet(&v, 10);
    64     tfret = (SDL_AtomicCAS(&v, 0, 20) == SDL_FALSE);
    65     printf("AtomicCAS()          tfret=%s val=%d\n", tf(tfret), SDL_AtomicGet(&v));
    66     value = SDL_AtomicGet(&v);
    67     tfret = (SDL_AtomicCAS(&v, value, 20) == SDL_TRUE);
    68     printf("AtomicCAS()          tfret=%s val=%d\n", tf(tfret), SDL_AtomicGet(&v));
    69 }
    70 
    71 /**************************************************************************/
    72 /* Atomic operation test
    73  * Adapted with permission from code by Michael Davidsaver at:
    74  *  http://bazaar.launchpad.net/~mdavidsaver/epics-base/atomic/revision/12105#src/libCom/test/epicsAtomicTest.c
    75  * Original copyright 2010 Brookhaven Science Associates as operator of Brookhaven National Lab
    76  * http://www.aps.anl.gov/epics/license/open.php
    77  */
    78 
    79 /* Tests semantics of atomic operations.  Also a stress test
    80  * to see if they are really atomic.
    81  *
    82  * Serveral threads adding to the same variable.
    83  * at the end the value is compared with the expected
    84  * and with a non-atomic counter.
    85  */
    86  
    87 /* Number of concurrent incrementers */
    88 #define NThreads 2
    89 #define CountInc 100
    90 #define VALBITS (sizeof(atomicValue)*8)
    91  
    92 #define atomicValue int
    93 #define CountTo ((atomicValue)((unsigned int)(1<<(VALBITS-1))-1))
    94 #define NInter (CountTo/CountInc/NThreads)
    95 #define Expect (CountTo-NInter*CountInc*NThreads)
    96  
    97 SDL_COMPILE_TIME_ASSERT(size, CountTo>0); /* check for rollover */
    98  
    99 static SDL_atomic_t good = { 42 };
   100  
   101 static atomicValue bad = 42;
   102  
   103 static SDL_atomic_t threadsRunning;
   104 
   105 static SDL_sem *threadDone;
   106  
   107 static
   108 int adder(void* junk)
   109 {
   110     unsigned long N=NInter;
   111     printf("Thread subtracting %d %lu times\n",CountInc,N);
   112     while (N--) {
   113         SDL_AtomicAdd(&good, -CountInc);
   114         bad-=CountInc;
   115     }
   116     SDL_AtomicAdd(&threadsRunning, -1);
   117     SDL_SemPost(threadDone);
   118     return 0;
   119 }
   120  
   121 static
   122 void runAdder(void)
   123 {
   124     Uint32 start, end;
   125     int T=NThreads;
   126  
   127     start = SDL_GetTicks();
   128  
   129     threadDone = SDL_CreateSemaphore(0);
   130 
   131     SDL_AtomicSet(&threadsRunning, NThreads);
   132 
   133     while (T--)
   134         SDL_CreateThread(adder, NULL);
   135  
   136     while (SDL_AtomicGet(&threadsRunning) > 0)
   137         SDL_SemWait(threadDone);
   138  
   139     SDL_DestroySemaphore(threadDone);
   140 
   141     end = SDL_GetTicks();
   142  
   143     printf("Finished in %f sec\n", (end - start) / 1000.f);
   144 }
   145  
   146 static
   147 void RunEpicTest()
   148 {
   149     int b;
   150     atomicValue v;
   151  
   152     printf("\nepic test---------------------------------------\n\n");
   153 
   154     printf("Size asserted to be >= 32-bit\n");
   155     SDL_assert(sizeof(atomicValue)>=4);
   156  
   157     printf("Check static initializer\n");
   158     v=SDL_AtomicGet(&good);
   159     SDL_assert(v==42);
   160  
   161     SDL_assert(bad==42);
   162  
   163     printf("Test negative values\n");
   164     SDL_AtomicSet(&good, -5);
   165     v=SDL_AtomicGet(&good);
   166     SDL_assert(v==-5);
   167  
   168     printf("Verify maximum value\n");
   169     SDL_AtomicSet(&good, CountTo);
   170     v=SDL_AtomicGet(&good);
   171     SDL_assert(v==CountTo);
   172  
   173     printf("Test compare and exchange\n");
   174  
   175     b=SDL_AtomicCAS(&good, 500, 43);
   176     SDL_assert(!b); /* no swap since CountTo!=500 */
   177     v=SDL_AtomicGet(&good);
   178     SDL_assert(v==CountTo); /* ensure no swap */
   179  
   180     b=SDL_AtomicCAS(&good, CountTo, 44);
   181     SDL_assert(!!b); /* will swap */
   182     v=SDL_AtomicGet(&good);
   183     SDL_assert(v==44);
   184  
   185     printf("Test Add\n");
   186  
   187     v=SDL_AtomicAdd(&good, 1);
   188     SDL_assert(v==44);
   189     v=SDL_AtomicGet(&good);
   190     SDL_assert(v==45);
   191  
   192     v=SDL_AtomicAdd(&good, 10);
   193     SDL_assert(v==45);
   194     v=SDL_AtomicGet(&good);
   195     SDL_assert(v==55);
   196  
   197     printf("Test Add (Negative values)\n");
   198  
   199     v=SDL_AtomicAdd(&good, -20);
   200     SDL_assert(v==55);
   201     v=SDL_AtomicGet(&good);
   202     SDL_assert(v==35);
   203  
   204     v=SDL_AtomicAdd(&good, -50); /* crossing zero down */
   205     SDL_assert(v==35);
   206     v=SDL_AtomicGet(&good);
   207     SDL_assert(v==-15);
   208  
   209     v=SDL_AtomicAdd(&good, 30); /* crossing zero up */
   210     SDL_assert(v==-15);
   211     v=SDL_AtomicGet(&good);
   212     SDL_assert(v==15);
   213  
   214     printf("Reset before count down test\n");
   215     SDL_AtomicSet(&good, CountTo);
   216     v=SDL_AtomicGet(&good);
   217     SDL_assert(v==CountTo);
   218  
   219     bad=CountTo;
   220     SDL_assert(bad==CountTo);
   221  
   222     printf("Counting down from %d, Expect %d remaining\n",CountTo,Expect);
   223     runAdder();
   224  
   225     v=SDL_AtomicGet(&good);
   226     printf("Atomic %d Non-Atomic %d\n",v,bad);
   227     SDL_assert(v==Expect);
   228     SDL_assert(bad!=Expect);
   229 }
   230 
   231 /* End atomic operation test */
   232 /**************************************************************************/
   233 
   234 /**************************************************************************/
   235 /* Lock-free FIFO test */
   236 
   237 #define NUM_READERS 4
   238 #define NUM_WRITERS 4
   239 #define EVENTS_PER_WRITER   1000000
   240 
   241 /* A decent guess for the size of a cache line on this architecture */
   242 #define CACHELINE   64
   243 
   244 /* The number of entries must be a power of 2 */
   245 #define MAX_ENTRIES 256
   246 #define WRAP_MASK   (MAX_ENTRIES-1)
   247 
   248 typedef struct
   249 {
   250     SDL_atomic_t sequence;
   251     SDL_Event event;
   252 } SDL_EventQueueEntry;
   253 
   254 typedef struct
   255 {
   256     SDL_EventQueueEntry entries[MAX_ENTRIES];
   257 
   258     char cache_pad1[CACHELINE-((sizeof(SDL_EventQueueEntry)*MAX_ENTRIES)%CACHELINE)];
   259 
   260     SDL_atomic_t enqueue_pos;
   261 
   262     char cache_pad2[CACHELINE-sizeof(SDL_atomic_t)];
   263 
   264     SDL_atomic_t dequeue_pos;
   265 
   266     char cache_pad3[CACHELINE-sizeof(SDL_atomic_t)];
   267 
   268     SDL_bool active;
   269 
   270     /* Only needed for the mutex test */
   271     SDL_mutex *mutex;
   272 
   273 } SDL_EventQueue;
   274 
   275 static void InitEventQueue(SDL_EventQueue *queue)
   276 {
   277     int i;
   278 
   279     for (i = 0; i < MAX_ENTRIES; ++i) {
   280         SDL_AtomicSet(&queue->entries[i].sequence, i);
   281     }
   282     SDL_AtomicSet(&queue->enqueue_pos, 0);
   283     SDL_AtomicSet(&queue->dequeue_pos, 0);
   284     queue->active = SDL_TRUE;
   285 }
   286 
   287 static SDL_bool EnqueueEvent_LockFree(SDL_EventQueue *queue, const SDL_Event *event)
   288 {
   289     SDL_EventQueueEntry *entry;
   290     unsigned queue_pos;
   291     unsigned entry_seq;
   292     int delta;
   293 
   294     queue_pos = (unsigned)SDL_AtomicGet(&queue->enqueue_pos);
   295     for ( ; ; ) {
   296         entry = &queue->entries[queue_pos & WRAP_MASK];
   297         entry_seq = (unsigned)SDL_AtomicGet(&entry->sequence);
   298 
   299         delta = (int)(entry_seq - queue_pos);
   300         if (delta == 0) {
   301             /* The entry and the queue position match, try to increment the queue position */
   302             if (SDL_AtomicCAS(&queue->enqueue_pos, (int)queue_pos, (int)(queue_pos+1))) {
   303                 break;
   304             }
   305         } else if (delta < 0) {
   306             /* We ran into an old queue entry, which means it still needs to be dequeued */
   307             return SDL_FALSE;
   308         } else {
   309             /* We ran into a new queue entry, get the new queue position */
   310             queue_pos = (unsigned)SDL_AtomicGet(&queue->enqueue_pos);
   311         }
   312     }
   313 
   314     /* We own the object, fill it! */
   315     entry->event = *event;
   316     SDL_AtomicSet(&entry->sequence, (int)(queue_pos + 1));
   317 
   318     return SDL_TRUE;
   319 }
   320 
   321 static SDL_bool DequeueEvent_LockFree(SDL_EventQueue *queue, SDL_Event *event)
   322 {
   323     SDL_EventQueueEntry *entry;
   324     unsigned queue_pos;
   325     unsigned entry_seq;
   326     int delta;
   327 
   328     queue_pos = (unsigned)SDL_AtomicGet(&queue->dequeue_pos);
   329     for ( ; ; ) {
   330         entry = &queue->entries[queue_pos & WRAP_MASK];
   331         entry_seq = (unsigned)SDL_AtomicGet(&entry->sequence);
   332 
   333         delta = (int)(entry_seq - (queue_pos + 1));
   334         if (delta == 0) {
   335             /* The entry and the queue position match, try to increment the queue position */
   336             if (SDL_AtomicCAS(&queue->dequeue_pos, (int)queue_pos, (int)(queue_pos+1))) {
   337                 break;
   338             }
   339         } else if (delta < 0) {
   340             /* We ran into an old queue entry, which means we've hit empty */
   341             return SDL_FALSE;
   342         } else {
   343             /* We ran into a new queue entry, get the new queue position */
   344             queue_pos = (unsigned)SDL_AtomicGet(&queue->dequeue_pos);
   345         }
   346     }
   347 
   348     /* We own the object, fill it! */
   349     *event = entry->event;
   350     SDL_AtomicSet(&entry->sequence, (int)(queue_pos+MAX_ENTRIES));
   351 
   352     return SDL_TRUE;
   353 }
   354 
   355 static SDL_bool EnqueueEvent_Mutex(SDL_EventQueue *queue, const SDL_Event *event)
   356 {
   357     SDL_EventQueueEntry *entry;
   358     unsigned queue_pos;
   359     unsigned entry_seq;
   360     int delta;
   361 
   362     SDL_mutexP(queue->mutex);
   363 
   364     queue_pos = (unsigned)queue->enqueue_pos.value;
   365     entry = &queue->entries[queue_pos & WRAP_MASK];
   366     entry_seq = (unsigned)entry->sequence.value;
   367 
   368     delta = (int)(entry_seq - queue_pos);
   369     if (delta == 0) {
   370         ++queue->enqueue_pos.value;
   371     } else if (delta < 0) {
   372         /* We ran into an old queue entry, which means it still needs to be dequeued */
   373         SDL_mutexV(queue->mutex);
   374         return SDL_FALSE;
   375     } else {
   376         printf("ERROR: mutex failed!\n");
   377     }
   378 
   379     /* We own the object, fill it! */
   380     entry->event = *event;
   381     entry->sequence.value = (int)(queue_pos + 1);
   382 
   383     SDL_mutexV(queue->mutex);
   384 
   385     return SDL_TRUE;
   386 }
   387 
   388 static SDL_bool DequeueEvent_Mutex(SDL_EventQueue *queue, SDL_Event *event)
   389 {
   390     SDL_EventQueueEntry *entry;
   391     unsigned queue_pos;
   392     unsigned entry_seq;
   393     int delta;
   394 
   395     SDL_mutexP(queue->mutex);
   396 
   397     queue_pos = (unsigned)queue->dequeue_pos.value;
   398     entry = &queue->entries[queue_pos & WRAP_MASK];
   399     entry_seq = (unsigned)entry->sequence.value;
   400 
   401     delta = (int)(entry_seq - (queue_pos + 1));
   402     if (delta == 0) {
   403         ++queue->dequeue_pos.value;
   404     } else if (delta < 0) {
   405         /* We ran into an old queue entry, which means we've hit empty */
   406         SDL_mutexV(queue->mutex);
   407         return SDL_FALSE;
   408     } else {
   409         printf("ERROR: mutex failed!\n");
   410     }
   411 
   412     /* We own the object, fill it! */
   413     *event = entry->event;
   414     entry->sequence.value = (int)(queue_pos + MAX_ENTRIES);
   415 
   416     SDL_mutexV(queue->mutex);
   417 
   418     return SDL_TRUE;
   419 }
   420 
   421 static SDL_sem *writersDone;
   422 static SDL_sem *readersDone;
   423 static SDL_atomic_t writersRunning;
   424 static SDL_atomic_t readersRunning;
   425 
   426 typedef struct
   427 {
   428     SDL_EventQueue *queue;
   429     int index;
   430     char padding1[CACHELINE-(sizeof(SDL_EventQueue*)+sizeof(int))%CACHELINE];
   431     int waits;
   432     SDL_bool lock_free;
   433     char padding2[CACHELINE-sizeof(int)-sizeof(SDL_bool)];
   434 } WriterData;
   435 
   436 typedef struct
   437 {
   438     SDL_EventQueue *queue;
   439     int counters[NUM_WRITERS];
   440     int waits;
   441     SDL_bool lock_free;
   442     char padding[CACHELINE-(sizeof(SDL_EventQueue*)+sizeof(int)*NUM_WRITERS+sizeof(int)+sizeof(SDL_bool))%CACHELINE];
   443 } ReaderData;
   444 
   445 static int FIFO_Writer(void* _data)
   446 {
   447     WriterData *data = (WriterData *)_data;
   448     SDL_EventQueue *queue = data->queue;
   449     int index = data->index;
   450     int i;
   451     SDL_Event event;
   452 
   453     event.type = SDL_USEREVENT;
   454     event.user.windowID = 0;
   455     event.user.code = 0;
   456     event.user.data1 = data;
   457     event.user.data2 = NULL;
   458 
   459     if (data->lock_free) {
   460         for (i = 0; i < EVENTS_PER_WRITER; ++i) {
   461             event.user.code = i;
   462             while (!EnqueueEvent_LockFree(queue, &event)) {
   463                 ++data->waits;
   464                 SDL_Delay(0);
   465             }
   466         }
   467     } else {
   468         for (i = 0; i < EVENTS_PER_WRITER; ++i) {
   469             event.user.code = i;
   470             while (!EnqueueEvent_Mutex(queue, &event)) {
   471                 ++data->waits;
   472                 SDL_Delay(0);
   473             }
   474         }
   475     }
   476     SDL_AtomicAdd(&writersRunning, -1);
   477     SDL_SemPost(writersDone);
   478     return 0;
   479 }
   480 
   481 static int FIFO_Reader(void* _data)
   482 {
   483     ReaderData *data = (ReaderData *)_data;
   484     SDL_EventQueue *queue = data->queue;
   485     SDL_Event event;
   486     int index;
   487 
   488     if (data->lock_free) {
   489         for ( ; ; ) {
   490             if (DequeueEvent_LockFree(queue, &event)) {
   491                 WriterData *writer = (WriterData*)event.user.data1;
   492                 ++data->counters[writer->index];
   493             } else if (queue->active) {
   494                 ++data->waits;
   495                 SDL_Delay(0);
   496             } else {
   497                 /* We drained the queue, we're done! */
   498                 break;
   499             }
   500         }
   501     } else {
   502         for ( ; ; ) {
   503             if (DequeueEvent_Mutex(queue, &event)) {
   504                 WriterData *writer = (WriterData*)event.user.data1;
   505                 ++data->counters[writer->index];
   506             } else if (queue->active) {
   507                 ++data->waits;
   508                 SDL_Delay(0);
   509             } else {
   510                 /* We drained the queue, we're done! */
   511                 break;
   512             }
   513         }
   514     }
   515     SDL_AtomicAdd(&readersRunning, -1);
   516     SDL_SemPost(readersDone);
   517     return 0;
   518 }
   519 
   520 static void RunFIFOTest(SDL_bool lock_free)
   521 {
   522     SDL_EventQueue queue;
   523     WriterData writerData[NUM_WRITERS];
   524     ReaderData readerData[NUM_READERS];
   525     Uint32 start, end;
   526     int i, j;
   527     int grand_total;
   528  
   529     printf("\nFIFO test---------------------------------------\n\n");
   530     printf("Mode: %s\n", lock_free ? "LockFree" : "Mutex");
   531 
   532     readersDone = SDL_CreateSemaphore(0);
   533     writersDone = SDL_CreateSemaphore(0);
   534 
   535     SDL_memset(&queue, 0xff, sizeof(queue));
   536 
   537     InitEventQueue(&queue);
   538     if (!lock_free) {
   539         queue.mutex = SDL_CreateMutex();
   540     }
   541 
   542     start = SDL_GetTicks();
   543  
   544     /* Start the readers first */
   545     printf("Starting %d readers\n", NUM_READERS);
   546     SDL_zero(readerData);
   547     SDL_AtomicSet(&readersRunning, NUM_READERS);
   548     for (i = 0; i < NUM_READERS; ++i) {
   549         readerData[i].queue = &queue;
   550         readerData[i].lock_free = lock_free;
   551         SDL_CreateThread(FIFO_Reader, &readerData[i]);
   552     }
   553 
   554     /* Start up the writers */
   555     printf("Starting %d writers\n", NUM_WRITERS);
   556     SDL_zero(writerData);
   557     SDL_AtomicSet(&writersRunning, NUM_WRITERS);
   558     for (i = 0; i < NUM_WRITERS; ++i) {
   559         writerData[i].queue = &queue;
   560         writerData[i].index = i;
   561         writerData[i].lock_free = lock_free;
   562         SDL_CreateThread(FIFO_Writer, &writerData[i]);
   563     }
   564  
   565     /* Wait for the writers */
   566     while (SDL_AtomicGet(&writersRunning) > 0) {
   567         SDL_SemWait(writersDone);
   568     }
   569  
   570     /* Shut down the queue so readers exit */
   571     queue.active = SDL_FALSE;
   572 
   573     /* Wait for the readers */
   574     while (SDL_AtomicGet(&readersRunning) > 0) {
   575         SDL_SemWait(readersDone);
   576     }
   577 
   578     end = SDL_GetTicks();
   579  
   580     SDL_DestroySemaphore(readersDone);
   581     SDL_DestroySemaphore(writersDone);
   582 
   583     if (!lock_free) {
   584         SDL_DestroyMutex(queue.mutex);
   585     }
   586  
   587     printf("Finished in %f sec\n", (end - start) / 1000.f);
   588 
   589     printf("\n");
   590     for (i = 0; i < NUM_WRITERS; ++i) {
   591         printf("Writer %d wrote %d events, had %d waits\n", i, EVENTS_PER_WRITER, writerData[i].waits);
   592     }
   593     printf("Writers wrote %d total events\n", NUM_WRITERS*EVENTS_PER_WRITER);
   594 
   595     /* Print a breakdown of which readers read messages from which writer */
   596     printf("\n");
   597     grand_total = 0;
   598     for (i = 0; i < NUM_READERS; ++i) {
   599         int total = 0;
   600         for (j = 0; j < NUM_WRITERS; ++j) {
   601             total += readerData[i].counters[j];
   602         }
   603         grand_total += total;
   604         printf("Reader %d read %d events, had %d waits\n", i, total, readerData[i].waits);
   605         printf("  { ");
   606         for (j = 0; j < NUM_WRITERS; ++j) {
   607             if (j > 0) {
   608                 printf(", ");
   609             }
   610             printf("%d", readerData[i].counters[j]);
   611         }
   612         printf(" }\n");
   613     }
   614     printf("Readers read %d total events\n", grand_total);
   615 }
   616 
   617 /* End FIFO test */
   618 /**************************************************************************/
   619 
   620 int
   621 main(int argc, char *argv[])
   622 {
   623     RunBasicTest();
   624     RunEpicTest();
   625 /* This test is really slow, so don't run it by default */
   626 #if 0
   627     RunFIFOTest(SDL_FALSE);
   628 #endif
   629     RunFIFOTest(SDL_TRUE);
   630     return 0;
   631 }
   632 
   633 /* vi: set ts=4 sw=4 expandtab: */