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