test/testatomic.c
author Sam Lantinga <slouken@libsdl.org>
Thu, 27 Jan 2011 16:46:15 -0800
changeset 5115 427998ff3bcf
parent 5114 e337f792c6a7
child 5116 02b860cbc7ce
permissions -rw-r--r--
Added cache line size info in SDL_cpuinfo.h
I also added an implementation to dynamically query it, but didn't expose it since most x86 CPUs have an L1 cache line size of 64 bytes.
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
/* The number of entries must be a power of 2 */
slouken@5098
   247
#define MAX_ENTRIES 256
slouken@5098
   248
#define WRAP_MASK   (MAX_ENTRIES-1)
slouken@5098
   249
slouken@5098
   250
typedef struct
slouken@5098
   251
{
slouken@5098
   252
    SDL_atomic_t sequence;
slouken@5098
   253
    SDL_Event event;
slouken@5098
   254
} SDL_EventQueueEntry;
slouken@5098
   255
slouken@5098
   256
typedef struct
slouken@5098
   257
{
slouken@5098
   258
    SDL_EventQueueEntry entries[MAX_ENTRIES];
slouken@5098
   259
slouken@5115
   260
    char cache_pad1[SDL_CACHELINE_SIZE-((sizeof(SDL_EventQueueEntry)*MAX_ENTRIES)%SDL_CACHELINE_SIZE)];
slouken@5098
   261
slouken@5098
   262
    SDL_atomic_t enqueue_pos;
slouken@5098
   263
slouken@5115
   264
    char cache_pad2[SDL_CACHELINE_SIZE-sizeof(SDL_atomic_t)];
slouken@5098
   265
slouken@5098
   266
    SDL_atomic_t dequeue_pos;
slouken@5098
   267
slouken@5115
   268
    char cache_pad3[SDL_CACHELINE_SIZE-sizeof(SDL_atomic_t)];
slouken@5098
   269
slouken@5099
   270
#ifdef TEST_SPINLOCK_FIFO
slouken@5099
   271
    SDL_SpinLock lock;
slouken@5099
   272
    SDL_atomic_t rwcount;
slouken@5099
   273
    SDL_atomic_t watcher;
slouken@5099
   274
slouken@5115
   275
    char cache_pad4[SDL_CACHELINE_SIZE-sizeof(SDL_SpinLock)-2*sizeof(SDL_atomic_t)];
slouken@5099
   276
#endif
slouken@5099
   277
slouken@5102
   278
    volatile SDL_bool active;
slouken@5098
   279
slouken@5098
   280
    /* Only needed for the mutex test */
slouken@5098
   281
    SDL_mutex *mutex;
slouken@5098
   282
slouken@5098
   283
} SDL_EventQueue;
slouken@5098
   284
slouken@5098
   285
static void InitEventQueue(SDL_EventQueue *queue)
slouken@5098
   286
{
slouken@5098
   287
    int i;
slouken@5098
   288
slouken@5098
   289
    for (i = 0; i < MAX_ENTRIES; ++i) {
slouken@5098
   290
        SDL_AtomicSet(&queue->entries[i].sequence, i);
slouken@5098
   291
    }
slouken@5098
   292
    SDL_AtomicSet(&queue->enqueue_pos, 0);
slouken@5098
   293
    SDL_AtomicSet(&queue->dequeue_pos, 0);
slouken@5099
   294
#ifdef TEST_SPINLOCK_FIFO
slouken@5099
   295
    queue->lock = 0;
slouken@5099
   296
    SDL_AtomicSet(&queue->rwcount, 0);
slouken@5099
   297
#endif
slouken@5098
   298
    queue->active = SDL_TRUE;
slouken@5098
   299
}
slouken@5098
   300
slouken@5098
   301
static SDL_bool EnqueueEvent_LockFree(SDL_EventQueue *queue, const SDL_Event *event)
slouken@5098
   302
{
slouken@5098
   303
    SDL_EventQueueEntry *entry;
slouken@5098
   304
    unsigned queue_pos;
slouken@5098
   305
    unsigned entry_seq;
slouken@5098
   306
    int delta;
slouken@5099
   307
    SDL_bool status;
slouken@5099
   308
slouken@5099
   309
#ifdef TEST_SPINLOCK_FIFO
slouken@5099
   310
    /* This is a gate so an external thread can lock the queue */
slouken@5099
   311
    SDL_AtomicLock(&queue->lock);
slouken@5099
   312
    SDL_assert(SDL_AtomicGet(&queue->watcher) == 0);
slouken@5099
   313
    SDL_AtomicIncRef(&queue->rwcount);
slouken@5099
   314
    SDL_AtomicUnlock(&queue->lock);
slouken@5099
   315
#endif
slouken@5098
   316
slouken@5098
   317
    queue_pos = (unsigned)SDL_AtomicGet(&queue->enqueue_pos);
slouken@5098
   318
    for ( ; ; ) {
slouken@5098
   319
        entry = &queue->entries[queue_pos & WRAP_MASK];
slouken@5098
   320
        entry_seq = (unsigned)SDL_AtomicGet(&entry->sequence);
slouken@5098
   321
slouken@5098
   322
        delta = (int)(entry_seq - queue_pos);
slouken@5098
   323
        if (delta == 0) {
slouken@5098
   324
            /* The entry and the queue position match, try to increment the queue position */
slouken@5098
   325
            if (SDL_AtomicCAS(&queue->enqueue_pos, (int)queue_pos, (int)(queue_pos+1))) {
slouken@5099
   326
                /* We own the object, fill it! */
slouken@5099
   327
                entry->event = *event;
slouken@5099
   328
                SDL_AtomicSet(&entry->sequence, (int)(queue_pos + 1));
slouken@5099
   329
                status = SDL_TRUE;
slouken@5098
   330
                break;
slouken@5098
   331
            }
slouken@5098
   332
        } else if (delta < 0) {
slouken@5098
   333
            /* We ran into an old queue entry, which means it still needs to be dequeued */
slouken@5099
   334
            status = SDL_FALSE;
slouken@5099
   335
            break;
slouken@5098
   336
        } else {
slouken@5098
   337
            /* We ran into a new queue entry, get the new queue position */
slouken@5098
   338
            queue_pos = (unsigned)SDL_AtomicGet(&queue->enqueue_pos);
slouken@5098
   339
        }
slouken@5098
   340
    }
slouken@5098
   341
slouken@5099
   342
#ifdef TEST_SPINLOCK_FIFO
slouken@5099
   343
    SDL_AtomicDecRef(&queue->rwcount);
slouken@5099
   344
#endif
slouken@5099
   345
    return status;
slouken@5098
   346
}
slouken@5098
   347
slouken@5098
   348
static SDL_bool DequeueEvent_LockFree(SDL_EventQueue *queue, SDL_Event *event)
slouken@5098
   349
{
slouken@5098
   350
    SDL_EventQueueEntry *entry;
slouken@5098
   351
    unsigned queue_pos;
slouken@5098
   352
    unsigned entry_seq;
slouken@5098
   353
    int delta;
slouken@5099
   354
    SDL_bool status;
slouken@5099
   355
slouken@5099
   356
#ifdef TEST_SPINLOCK_FIFO
slouken@5099
   357
    /* This is a gate so an external thread can lock the queue */
slouken@5099
   358
    SDL_AtomicLock(&queue->lock);
slouken@5099
   359
    SDL_assert(SDL_AtomicGet(&queue->watcher) == 0);
slouken@5099
   360
    SDL_AtomicIncRef(&queue->rwcount);
slouken@5099
   361
    SDL_AtomicUnlock(&queue->lock);
slouken@5099
   362
#endif
slouken@5098
   363
slouken@5098
   364
    queue_pos = (unsigned)SDL_AtomicGet(&queue->dequeue_pos);
slouken@5098
   365
    for ( ; ; ) {
slouken@5098
   366
        entry = &queue->entries[queue_pos & WRAP_MASK];
slouken@5098
   367
        entry_seq = (unsigned)SDL_AtomicGet(&entry->sequence);
slouken@5098
   368
slouken@5098
   369
        delta = (int)(entry_seq - (queue_pos + 1));
slouken@5098
   370
        if (delta == 0) {
slouken@5098
   371
            /* The entry and the queue position match, try to increment the queue position */
slouken@5098
   372
            if (SDL_AtomicCAS(&queue->dequeue_pos, (int)queue_pos, (int)(queue_pos+1))) {
slouken@5099
   373
                /* We own the object, fill it! */
slouken@5099
   374
                *event = entry->event;
slouken@5099
   375
                SDL_AtomicSet(&entry->sequence, (int)(queue_pos+MAX_ENTRIES));
slouken@5099
   376
                status = SDL_TRUE;
slouken@5098
   377
                break;
slouken@5098
   378
            }
slouken@5098
   379
        } else if (delta < 0) {
slouken@5098
   380
            /* We ran into an old queue entry, which means we've hit empty */
slouken@5099
   381
            status = SDL_FALSE;
slouken@5099
   382
            break;
slouken@5098
   383
        } else {
slouken@5098
   384
            /* We ran into a new queue entry, get the new queue position */
slouken@5098
   385
            queue_pos = (unsigned)SDL_AtomicGet(&queue->dequeue_pos);
slouken@5098
   386
        }
slouken@5098
   387
    }
slouken@5098
   388
slouken@5099
   389
#ifdef TEST_SPINLOCK_FIFO
slouken@5099
   390
    SDL_AtomicDecRef(&queue->rwcount);
slouken@5099
   391
#endif
slouken@5099
   392
    return status;
slouken@5098
   393
}
slouken@5098
   394
slouken@5098
   395
static SDL_bool EnqueueEvent_Mutex(SDL_EventQueue *queue, const SDL_Event *event)
slouken@5098
   396
{
slouken@5098
   397
    SDL_EventQueueEntry *entry;
slouken@5098
   398
    unsigned queue_pos;
slouken@5098
   399
    unsigned entry_seq;
slouken@5098
   400
    int delta;
slouken@5099
   401
    SDL_bool status = SDL_FALSE;
slouken@5098
   402
slouken@5098
   403
    SDL_mutexP(queue->mutex);
slouken@5098
   404
slouken@5098
   405
    queue_pos = (unsigned)queue->enqueue_pos.value;
slouken@5098
   406
    entry = &queue->entries[queue_pos & WRAP_MASK];
slouken@5098
   407
    entry_seq = (unsigned)entry->sequence.value;
slouken@5098
   408
slouken@5098
   409
    delta = (int)(entry_seq - queue_pos);
slouken@5098
   410
    if (delta == 0) {
slouken@5098
   411
        ++queue->enqueue_pos.value;
slouken@5099
   412
slouken@5099
   413
        /* We own the object, fill it! */
slouken@5099
   414
        entry->event = *event;
slouken@5099
   415
        entry->sequence.value = (int)(queue_pos + 1);
slouken@5099
   416
        status = SDL_TRUE;
slouken@5098
   417
    } else if (delta < 0) {
slouken@5098
   418
        /* We ran into an old queue entry, which means it still needs to be dequeued */
slouken@5098
   419
    } else {
slouken@5098
   420
        printf("ERROR: mutex failed!\n");
slouken@5098
   421
    }
slouken@5098
   422
slouken@5098
   423
    SDL_mutexV(queue->mutex);
slouken@5098
   424
slouken@5099
   425
    return status;
slouken@5098
   426
}
slouken@5098
   427
slouken@5098
   428
static SDL_bool DequeueEvent_Mutex(SDL_EventQueue *queue, SDL_Event *event)
slouken@5098
   429
{
slouken@5098
   430
    SDL_EventQueueEntry *entry;
slouken@5098
   431
    unsigned queue_pos;
slouken@5098
   432
    unsigned entry_seq;
slouken@5098
   433
    int delta;
slouken@5099
   434
    SDL_bool status = SDL_FALSE;
slouken@5098
   435
slouken@5098
   436
    SDL_mutexP(queue->mutex);
slouken@5098
   437
slouken@5098
   438
    queue_pos = (unsigned)queue->dequeue_pos.value;
slouken@5098
   439
    entry = &queue->entries[queue_pos & WRAP_MASK];
slouken@5098
   440
    entry_seq = (unsigned)entry->sequence.value;
slouken@5098
   441
slouken@5098
   442
    delta = (int)(entry_seq - (queue_pos + 1));
slouken@5098
   443
    if (delta == 0) {
slouken@5098
   444
        ++queue->dequeue_pos.value;
slouken@5099
   445
slouken@5099
   446
        /* We own the object, fill it! */
slouken@5099
   447
        *event = entry->event;
slouken@5099
   448
        entry->sequence.value = (int)(queue_pos + MAX_ENTRIES);
slouken@5099
   449
        status = SDL_TRUE;
slouken@5098
   450
    } else if (delta < 0) {
slouken@5098
   451
        /* We ran into an old queue entry, which means we've hit empty */
slouken@5098
   452
    } else {
slouken@5098
   453
        printf("ERROR: mutex failed!\n");
slouken@5098
   454
    }
slouken@5098
   455
slouken@5098
   456
    SDL_mutexV(queue->mutex);
slouken@5098
   457
slouken@5099
   458
    return status;
slouken@5098
   459
}
slouken@5098
   460
slouken@5098
   461
static SDL_sem *writersDone;
slouken@5098
   462
static SDL_sem *readersDone;
slouken@5098
   463
static SDL_atomic_t writersRunning;
slouken@5098
   464
static SDL_atomic_t readersRunning;
slouken@5098
   465
slouken@5098
   466
typedef struct
slouken@5098
   467
{
slouken@5098
   468
    SDL_EventQueue *queue;
slouken@5098
   469
    int index;
slouken@5115
   470
    char padding1[SDL_CACHELINE_SIZE-(sizeof(SDL_EventQueue*)+sizeof(int))%SDL_CACHELINE_SIZE];
slouken@5098
   471
    int waits;
slouken@5098
   472
    SDL_bool lock_free;
slouken@5115
   473
    char padding2[SDL_CACHELINE_SIZE-sizeof(int)-sizeof(SDL_bool)];
slouken@5098
   474
} WriterData;
slouken@5098
   475
slouken@5098
   476
typedef struct
slouken@5098
   477
{
slouken@5098
   478
    SDL_EventQueue *queue;
slouken@5098
   479
    int counters[NUM_WRITERS];
slouken@5098
   480
    int waits;
slouken@5098
   481
    SDL_bool lock_free;
slouken@5115
   482
    char padding[SDL_CACHELINE_SIZE-(sizeof(SDL_EventQueue*)+sizeof(int)*NUM_WRITERS+sizeof(int)+sizeof(SDL_bool))%SDL_CACHELINE_SIZE];
slouken@5098
   483
} ReaderData;
slouken@5098
   484
slouken@5098
   485
static int FIFO_Writer(void* _data)
slouken@5098
   486
{
slouken@5098
   487
    WriterData *data = (WriterData *)_data;
slouken@5098
   488
    SDL_EventQueue *queue = data->queue;
slouken@5098
   489
    int index = data->index;
slouken@5098
   490
    int i;
slouken@5098
   491
    SDL_Event event;
slouken@5098
   492
slouken@5098
   493
    event.type = SDL_USEREVENT;
slouken@5098
   494
    event.user.windowID = 0;
slouken@5098
   495
    event.user.code = 0;
slouken@5098
   496
    event.user.data1 = data;
slouken@5098
   497
    event.user.data2 = NULL;
slouken@5098
   498
slouken@5098
   499
    if (data->lock_free) {
slouken@5098
   500
        for (i = 0; i < EVENTS_PER_WRITER; ++i) {
slouken@5098
   501
            event.user.code = i;
slouken@5098
   502
            while (!EnqueueEvent_LockFree(queue, &event)) {
slouken@5098
   503
                ++data->waits;
slouken@5098
   504
                SDL_Delay(0);
slouken@5098
   505
            }
slouken@5098
   506
        }
slouken@5098
   507
    } else {
slouken@5098
   508
        for (i = 0; i < EVENTS_PER_WRITER; ++i) {
slouken@5098
   509
            event.user.code = i;
slouken@5098
   510
            while (!EnqueueEvent_Mutex(queue, &event)) {
slouken@5098
   511
                ++data->waits;
slouken@5098
   512
                SDL_Delay(0);
slouken@5098
   513
            }
slouken@5098
   514
        }
slouken@5098
   515
    }
slouken@5098
   516
    SDL_AtomicAdd(&writersRunning, -1);
slouken@5098
   517
    SDL_SemPost(writersDone);
slouken@5098
   518
    return 0;
slouken@5098
   519
}
slouken@5098
   520
slouken@5098
   521
static int FIFO_Reader(void* _data)
slouken@5098
   522
{
slouken@5098
   523
    ReaderData *data = (ReaderData *)_data;
slouken@5098
   524
    SDL_EventQueue *queue = data->queue;
slouken@5098
   525
    SDL_Event event;
slouken@5098
   526
slouken@5098
   527
    if (data->lock_free) {
slouken@5098
   528
        for ( ; ; ) {
slouken@5098
   529
            if (DequeueEvent_LockFree(queue, &event)) {
slouken@5098
   530
                WriterData *writer = (WriterData*)event.user.data1;
slouken@5098
   531
                ++data->counters[writer->index];
slouken@5098
   532
            } else if (queue->active) {
slouken@5098
   533
                ++data->waits;
slouken@5098
   534
                SDL_Delay(0);
slouken@5098
   535
            } else {
slouken@5098
   536
                /* We drained the queue, we're done! */
slouken@5098
   537
                break;
slouken@5098
   538
            }
slouken@5098
   539
        }
slouken@5098
   540
    } else {
slouken@5098
   541
        for ( ; ; ) {
slouken@5098
   542
            if (DequeueEvent_Mutex(queue, &event)) {
slouken@5098
   543
                WriterData *writer = (WriterData*)event.user.data1;
slouken@5098
   544
                ++data->counters[writer->index];
slouken@5098
   545
            } else if (queue->active) {
slouken@5098
   546
                ++data->waits;
slouken@5098
   547
                SDL_Delay(0);
slouken@5098
   548
            } else {
slouken@5098
   549
                /* We drained the queue, we're done! */
slouken@5098
   550
                break;
slouken@5098
   551
            }
slouken@5098
   552
        }
slouken@5098
   553
    }
slouken@5098
   554
    SDL_AtomicAdd(&readersRunning, -1);
slouken@5098
   555
    SDL_SemPost(readersDone);
slouken@5098
   556
    return 0;
slouken@5098
   557
}
slouken@5098
   558
slouken@5099
   559
#ifdef TEST_SPINLOCK_FIFO
slouken@5099
   560
/* This thread periodically locks the queue for no particular reason */
slouken@5099
   561
static int FIFO_Watcher(void* _data)
slouken@5099
   562
{
slouken@5099
   563
    SDL_EventQueue *queue = (SDL_EventQueue *)_data;
slouken@5099
   564
slouken@5099
   565
    while (queue->active) {
slouken@5099
   566
        SDL_AtomicLock(&queue->lock);
slouken@5099
   567
        SDL_AtomicIncRef(&queue->watcher);
slouken@5099
   568
        while (SDL_AtomicGet(&queue->rwcount) > 0) {
slouken@5099
   569
            SDL_Delay(0);
slouken@5099
   570
        }
slouken@5099
   571
        /* Do queue manipulation here... */
slouken@5099
   572
        SDL_AtomicDecRef(&queue->watcher);
slouken@5099
   573
        SDL_AtomicUnlock(&queue->lock);
slouken@5099
   574
slouken@5099
   575
        /* Wait a bit... */
slouken@5099
   576
        SDL_Delay(1);
slouken@5099
   577
    }
slouken@5099
   578
    return 0;
slouken@5099
   579
}
slouken@5099
   580
#endif /* TEST_SPINLOCK_FIFO */
slouken@5099
   581
slouken@5098
   582
static void RunFIFOTest(SDL_bool lock_free)
slouken@5098
   583
{
slouken@5098
   584
    SDL_EventQueue queue;
slouken@5098
   585
    WriterData writerData[NUM_WRITERS];
slouken@5098
   586
    ReaderData readerData[NUM_READERS];
slouken@5098
   587
    Uint32 start, end;
slouken@5098
   588
    int i, j;
slouken@5098
   589
    int grand_total;
slouken@5098
   590
 
slouken@5098
   591
    printf("\nFIFO test---------------------------------------\n\n");
slouken@5098
   592
    printf("Mode: %s\n", lock_free ? "LockFree" : "Mutex");
slouken@5098
   593
slouken@5098
   594
    readersDone = SDL_CreateSemaphore(0);
slouken@5098
   595
    writersDone = SDL_CreateSemaphore(0);
slouken@5098
   596
slouken@5098
   597
    SDL_memset(&queue, 0xff, sizeof(queue));
slouken@5098
   598
slouken@5098
   599
    InitEventQueue(&queue);
slouken@5098
   600
    if (!lock_free) {
slouken@5098
   601
        queue.mutex = SDL_CreateMutex();
slouken@5098
   602
    }
slouken@5098
   603
slouken@5098
   604
    start = SDL_GetTicks();
slouken@5098
   605
 
slouken@5099
   606
#ifdef TEST_SPINLOCK_FIFO
slouken@5099
   607
    /* Start a monitoring thread */
slouken@5099
   608
    if (lock_free) {
slouken@5099
   609
        SDL_CreateThread(FIFO_Watcher, &queue);
slouken@5099
   610
    }
slouken@5099
   611
#endif
slouken@5099
   612
slouken@5098
   613
    /* Start the readers first */
slouken@5098
   614
    printf("Starting %d readers\n", NUM_READERS);
slouken@5098
   615
    SDL_zero(readerData);
slouken@5098
   616
    SDL_AtomicSet(&readersRunning, NUM_READERS);
slouken@5098
   617
    for (i = 0; i < NUM_READERS; ++i) {
slouken@5098
   618
        readerData[i].queue = &queue;
slouken@5098
   619
        readerData[i].lock_free = lock_free;
slouken@5098
   620
        SDL_CreateThread(FIFO_Reader, &readerData[i]);
slouken@5098
   621
    }
slouken@5098
   622
slouken@5098
   623
    /* Start up the writers */
slouken@5098
   624
    printf("Starting %d writers\n", NUM_WRITERS);
slouken@5098
   625
    SDL_zero(writerData);
slouken@5098
   626
    SDL_AtomicSet(&writersRunning, NUM_WRITERS);
slouken@5098
   627
    for (i = 0; i < NUM_WRITERS; ++i) {
slouken@5098
   628
        writerData[i].queue = &queue;
slouken@5098
   629
        writerData[i].index = i;
slouken@5098
   630
        writerData[i].lock_free = lock_free;
slouken@5098
   631
        SDL_CreateThread(FIFO_Writer, &writerData[i]);
slouken@5098
   632
    }
slouken@5098
   633
 
slouken@5098
   634
    /* Wait for the writers */
slouken@5098
   635
    while (SDL_AtomicGet(&writersRunning) > 0) {
slouken@5098
   636
        SDL_SemWait(writersDone);
slouken@5098
   637
    }
slouken@5098
   638
 
slouken@5098
   639
    /* Shut down the queue so readers exit */
slouken@5098
   640
    queue.active = SDL_FALSE;
slouken@5098
   641
slouken@5098
   642
    /* Wait for the readers */
slouken@5098
   643
    while (SDL_AtomicGet(&readersRunning) > 0) {
slouken@5098
   644
        SDL_SemWait(readersDone);
slouken@5098
   645
    }
slouken@5098
   646
slouken@5098
   647
    end = SDL_GetTicks();
slouken@5098
   648
 
slouken@5098
   649
    SDL_DestroySemaphore(readersDone);
slouken@5098
   650
    SDL_DestroySemaphore(writersDone);
slouken@5098
   651
slouken@5098
   652
    if (!lock_free) {
slouken@5098
   653
        SDL_DestroyMutex(queue.mutex);
slouken@5098
   654
    }
slouken@5098
   655
 
slouken@5098
   656
    printf("Finished in %f sec\n", (end - start) / 1000.f);
slouken@5098
   657
slouken@5098
   658
    printf("\n");
slouken@5098
   659
    for (i = 0; i < NUM_WRITERS; ++i) {
slouken@5098
   660
        printf("Writer %d wrote %d events, had %d waits\n", i, EVENTS_PER_WRITER, writerData[i].waits);
slouken@5098
   661
    }
slouken@5098
   662
    printf("Writers wrote %d total events\n", NUM_WRITERS*EVENTS_PER_WRITER);
slouken@5098
   663
slouken@5098
   664
    /* Print a breakdown of which readers read messages from which writer */
slouken@5098
   665
    printf("\n");
slouken@5098
   666
    grand_total = 0;
slouken@5098
   667
    for (i = 0; i < NUM_READERS; ++i) {
slouken@5098
   668
        int total = 0;
slouken@5098
   669
        for (j = 0; j < NUM_WRITERS; ++j) {
slouken@5098
   670
            total += readerData[i].counters[j];
slouken@5098
   671
        }
slouken@5098
   672
        grand_total += total;
slouken@5098
   673
        printf("Reader %d read %d events, had %d waits\n", i, total, readerData[i].waits);
slouken@5098
   674
        printf("  { ");
slouken@5098
   675
        for (j = 0; j < NUM_WRITERS; ++j) {
slouken@5098
   676
            if (j > 0) {
slouken@5098
   677
                printf(", ");
slouken@5098
   678
            }
slouken@5098
   679
            printf("%d", readerData[i].counters[j]);
slouken@5098
   680
        }
slouken@5098
   681
        printf(" }\n");
slouken@5098
   682
    }
slouken@5098
   683
    printf("Readers read %d total events\n", grand_total);
slouken@5098
   684
}
slouken@5098
   685
slouken@5098
   686
/* End FIFO test */
slouken@5098
   687
/**************************************************************************/
slouken@5098
   688
slouken@5004
   689
int
slouken@5004
   690
main(int argc, char *argv[])
slouken@5004
   691
{
slouken@5004
   692
    RunBasicTest();
slouken@5004
   693
    RunEpicTest();
slouken@5098
   694
/* This test is really slow, so don't run it by default */
slouken@5098
   695
#if 0
slouken@5098
   696
    RunFIFOTest(SDL_FALSE);
slouken@5098
   697
#endif
slouken@5098
   698
    RunFIFOTest(SDL_TRUE);
slouken@5004
   699
    return 0;
slouken@5004
   700
}
slouken@5098
   701
slouken@5098
   702
/* vi: set ts=4 sw=4 expandtab: */