Added a FIFO test to the atomic test suite.
authorSam Lantinga <slouken@libsdl.org>
Tue, 25 Jan 2011 23:23:52 -0800
changeset 5098470ede30189c
parent 5097 b938ad843e52
child 5099 1b3678ac9804
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.
include/SDL_atomic.h
test/testatomic.c
     1.1 --- a/include/SDL_atomic.h	Tue Jan 25 18:02:41 2011 -0800
     1.2 +++ b/include/SDL_atomic.h	Tue Jan 25 23:23:52 2011 -0800
     1.3 @@ -44,6 +44,9 @@
     1.4   * subtle issues that can arise here:
     1.5   * http://msdn.microsoft.com/en-us/library/ee418650%28v=vs.85%29.aspx
     1.6   *
     1.7 + * There's also lots of good information here:
     1.8 + * http://www.1024cores.net/home/lock-free-algorithms
     1.9 + *
    1.10   * These operations may or may not actually be implemented using
    1.11   * processor specific atomic operations. When possible they are
    1.12   * implemented as true processor specific atomic operations. When that
     2.1 --- a/test/testatomic.c	Tue Jan 25 18:02:41 2011 -0800
     2.2 +++ b/test/testatomic.c	Tue Jan 25 23:23:52 2011 -0800
     2.3 @@ -231,10 +231,403 @@
     2.4  /* End atomic operation test */
     2.5  /**************************************************************************/
     2.6  
     2.7 +/**************************************************************************/
     2.8 +/* Lock-free FIFO test */
     2.9 +
    2.10 +#define NUM_READERS 4
    2.11 +#define NUM_WRITERS 4
    2.12 +#define EVENTS_PER_WRITER   1000000
    2.13 +
    2.14 +/* A decent guess for the size of a cache line on this architecture */
    2.15 +#define CACHELINE   64
    2.16 +
    2.17 +/* The number of entries must be a power of 2 */
    2.18 +#define MAX_ENTRIES 256
    2.19 +#define WRAP_MASK   (MAX_ENTRIES-1)
    2.20 +
    2.21 +typedef struct
    2.22 +{
    2.23 +    SDL_atomic_t sequence;
    2.24 +    SDL_Event event;
    2.25 +} SDL_EventQueueEntry;
    2.26 +
    2.27 +typedef struct
    2.28 +{
    2.29 +    SDL_EventQueueEntry entries[MAX_ENTRIES];
    2.30 +
    2.31 +    char cache_pad1[CACHELINE-((sizeof(SDL_EventQueueEntry)*MAX_ENTRIES)%CACHELINE)];
    2.32 +
    2.33 +    SDL_atomic_t enqueue_pos;
    2.34 +
    2.35 +    char cache_pad2[CACHELINE-sizeof(SDL_atomic_t)];
    2.36 +
    2.37 +    SDL_atomic_t dequeue_pos;
    2.38 +
    2.39 +    char cache_pad3[CACHELINE-sizeof(SDL_atomic_t)];
    2.40 +
    2.41 +    SDL_bool active;
    2.42 +
    2.43 +    /* Only needed for the mutex test */
    2.44 +    SDL_mutex *mutex;
    2.45 +
    2.46 +} SDL_EventQueue;
    2.47 +
    2.48 +static void InitEventQueue(SDL_EventQueue *queue)
    2.49 +{
    2.50 +    int i;
    2.51 +
    2.52 +    for (i = 0; i < MAX_ENTRIES; ++i) {
    2.53 +        SDL_AtomicSet(&queue->entries[i].sequence, i);
    2.54 +    }
    2.55 +    SDL_AtomicSet(&queue->enqueue_pos, 0);
    2.56 +    SDL_AtomicSet(&queue->dequeue_pos, 0);
    2.57 +    queue->active = SDL_TRUE;
    2.58 +}
    2.59 +
    2.60 +static SDL_bool EnqueueEvent_LockFree(SDL_EventQueue *queue, const SDL_Event *event)
    2.61 +{
    2.62 +    SDL_EventQueueEntry *entry;
    2.63 +    unsigned queue_pos;
    2.64 +    unsigned entry_seq;
    2.65 +    int delta;
    2.66 +
    2.67 +    queue_pos = (unsigned)SDL_AtomicGet(&queue->enqueue_pos);
    2.68 +    for ( ; ; ) {
    2.69 +        entry = &queue->entries[queue_pos & WRAP_MASK];
    2.70 +        entry_seq = (unsigned)SDL_AtomicGet(&entry->sequence);
    2.71 +
    2.72 +        delta = (int)(entry_seq - queue_pos);
    2.73 +        if (delta == 0) {
    2.74 +            /* The entry and the queue position match, try to increment the queue position */
    2.75 +            if (SDL_AtomicCAS(&queue->enqueue_pos, (int)queue_pos, (int)(queue_pos+1))) {
    2.76 +                break;
    2.77 +            }
    2.78 +        } else if (delta < 0) {
    2.79 +            /* We ran into an old queue entry, which means it still needs to be dequeued */
    2.80 +            return SDL_FALSE;
    2.81 +        } else {
    2.82 +            /* We ran into a new queue entry, get the new queue position */
    2.83 +            queue_pos = (unsigned)SDL_AtomicGet(&queue->enqueue_pos);
    2.84 +        }
    2.85 +    }
    2.86 +
    2.87 +    /* We own the object, fill it! */
    2.88 +    entry->event = *event;
    2.89 +    SDL_AtomicSet(&entry->sequence, (int)(queue_pos + 1));
    2.90 +
    2.91 +    return SDL_TRUE;
    2.92 +}
    2.93 +
    2.94 +static SDL_bool DequeueEvent_LockFree(SDL_EventQueue *queue, SDL_Event *event)
    2.95 +{
    2.96 +    SDL_EventQueueEntry *entry;
    2.97 +    unsigned queue_pos;
    2.98 +    unsigned entry_seq;
    2.99 +    int delta;
   2.100 +
   2.101 +    queue_pos = (unsigned)SDL_AtomicGet(&queue->dequeue_pos);
   2.102 +    for ( ; ; ) {
   2.103 +        entry = &queue->entries[queue_pos & WRAP_MASK];
   2.104 +        entry_seq = (unsigned)SDL_AtomicGet(&entry->sequence);
   2.105 +
   2.106 +        delta = (int)(entry_seq - (queue_pos + 1));
   2.107 +        if (delta == 0) {
   2.108 +            /* The entry and the queue position match, try to increment the queue position */
   2.109 +            if (SDL_AtomicCAS(&queue->dequeue_pos, (int)queue_pos, (int)(queue_pos+1))) {
   2.110 +                break;
   2.111 +            }
   2.112 +        } else if (delta < 0) {
   2.113 +            /* We ran into an old queue entry, which means we've hit empty */
   2.114 +            return SDL_FALSE;
   2.115 +        } else {
   2.116 +            /* We ran into a new queue entry, get the new queue position */
   2.117 +            queue_pos = (unsigned)SDL_AtomicGet(&queue->dequeue_pos);
   2.118 +        }
   2.119 +    }
   2.120 +
   2.121 +    /* We own the object, fill it! */
   2.122 +    *event = entry->event;
   2.123 +    SDL_AtomicSet(&entry->sequence, (int)(queue_pos+MAX_ENTRIES));
   2.124 +
   2.125 +    return SDL_TRUE;
   2.126 +}
   2.127 +
   2.128 +static SDL_bool EnqueueEvent_Mutex(SDL_EventQueue *queue, const SDL_Event *event)
   2.129 +{
   2.130 +    SDL_EventQueueEntry *entry;
   2.131 +    unsigned queue_pos;
   2.132 +    unsigned entry_seq;
   2.133 +    int delta;
   2.134 +
   2.135 +    SDL_mutexP(queue->mutex);
   2.136 +
   2.137 +    queue_pos = (unsigned)queue->enqueue_pos.value;
   2.138 +    entry = &queue->entries[queue_pos & WRAP_MASK];
   2.139 +    entry_seq = (unsigned)entry->sequence.value;
   2.140 +
   2.141 +    delta = (int)(entry_seq - queue_pos);
   2.142 +    if (delta == 0) {
   2.143 +        ++queue->enqueue_pos.value;
   2.144 +    } else if (delta < 0) {
   2.145 +        /* We ran into an old queue entry, which means it still needs to be dequeued */
   2.146 +        SDL_mutexV(queue->mutex);
   2.147 +        return SDL_FALSE;
   2.148 +    } else {
   2.149 +        printf("ERROR: mutex failed!\n");
   2.150 +    }
   2.151 +
   2.152 +    /* We own the object, fill it! */
   2.153 +    entry->event = *event;
   2.154 +    entry->sequence.value = (int)(queue_pos + 1);
   2.155 +
   2.156 +    SDL_mutexV(queue->mutex);
   2.157 +
   2.158 +    return SDL_TRUE;
   2.159 +}
   2.160 +
   2.161 +static SDL_bool DequeueEvent_Mutex(SDL_EventQueue *queue, SDL_Event *event)
   2.162 +{
   2.163 +    SDL_EventQueueEntry *entry;
   2.164 +    unsigned queue_pos;
   2.165 +    unsigned entry_seq;
   2.166 +    int delta;
   2.167 +
   2.168 +    SDL_mutexP(queue->mutex);
   2.169 +
   2.170 +    queue_pos = (unsigned)queue->dequeue_pos.value;
   2.171 +    entry = &queue->entries[queue_pos & WRAP_MASK];
   2.172 +    entry_seq = (unsigned)entry->sequence.value;
   2.173 +
   2.174 +    delta = (int)(entry_seq - (queue_pos + 1));
   2.175 +    if (delta == 0) {
   2.176 +        ++queue->dequeue_pos.value;
   2.177 +    } else if (delta < 0) {
   2.178 +        /* We ran into an old queue entry, which means we've hit empty */
   2.179 +        SDL_mutexV(queue->mutex);
   2.180 +        return SDL_FALSE;
   2.181 +    } else {
   2.182 +        printf("ERROR: mutex failed!\n");
   2.183 +    }
   2.184 +
   2.185 +    /* We own the object, fill it! */
   2.186 +    *event = entry->event;
   2.187 +    entry->sequence.value = (int)(queue_pos + MAX_ENTRIES);
   2.188 +
   2.189 +    SDL_mutexV(queue->mutex);
   2.190 +
   2.191 +    return SDL_TRUE;
   2.192 +}
   2.193 +
   2.194 +static SDL_sem *writersDone;
   2.195 +static SDL_sem *readersDone;
   2.196 +static SDL_atomic_t writersRunning;
   2.197 +static SDL_atomic_t readersRunning;
   2.198 +
   2.199 +typedef struct
   2.200 +{
   2.201 +    SDL_EventQueue *queue;
   2.202 +    int index;
   2.203 +    char padding1[CACHELINE-(sizeof(SDL_EventQueue*)+sizeof(int))%CACHELINE];
   2.204 +    int waits;
   2.205 +    SDL_bool lock_free;
   2.206 +    char padding2[CACHELINE-sizeof(int)-sizeof(SDL_bool)];
   2.207 +} WriterData;
   2.208 +
   2.209 +typedef struct
   2.210 +{
   2.211 +    SDL_EventQueue *queue;
   2.212 +    int counters[NUM_WRITERS];
   2.213 +    int waits;
   2.214 +    SDL_bool lock_free;
   2.215 +    char padding[CACHELINE-(sizeof(SDL_EventQueue*)+sizeof(int)*NUM_WRITERS+sizeof(int)+sizeof(SDL_bool))%CACHELINE];
   2.216 +} ReaderData;
   2.217 +
   2.218 +static int FIFO_Writer(void* _data)
   2.219 +{
   2.220 +    WriterData *data = (WriterData *)_data;
   2.221 +    SDL_EventQueue *queue = data->queue;
   2.222 +    int index = data->index;
   2.223 +    int i;
   2.224 +    SDL_Event event;
   2.225 +
   2.226 +    event.type = SDL_USEREVENT;
   2.227 +    event.user.windowID = 0;
   2.228 +    event.user.code = 0;
   2.229 +    event.user.data1 = data;
   2.230 +    event.user.data2 = NULL;
   2.231 +
   2.232 +    if (data->lock_free) {
   2.233 +        for (i = 0; i < EVENTS_PER_WRITER; ++i) {
   2.234 +            event.user.code = i;
   2.235 +            while (!EnqueueEvent_LockFree(queue, &event)) {
   2.236 +                ++data->waits;
   2.237 +                SDL_Delay(0);
   2.238 +            }
   2.239 +        }
   2.240 +    } else {
   2.241 +        for (i = 0; i < EVENTS_PER_WRITER; ++i) {
   2.242 +            event.user.code = i;
   2.243 +            while (!EnqueueEvent_Mutex(queue, &event)) {
   2.244 +                ++data->waits;
   2.245 +                SDL_Delay(0);
   2.246 +            }
   2.247 +        }
   2.248 +    }
   2.249 +    SDL_AtomicAdd(&writersRunning, -1);
   2.250 +    SDL_SemPost(writersDone);
   2.251 +    return 0;
   2.252 +}
   2.253 +
   2.254 +static int FIFO_Reader(void* _data)
   2.255 +{
   2.256 +    ReaderData *data = (ReaderData *)_data;
   2.257 +    SDL_EventQueue *queue = data->queue;
   2.258 +    SDL_Event event;
   2.259 +    int index;
   2.260 +
   2.261 +    if (data->lock_free) {
   2.262 +        for ( ; ; ) {
   2.263 +            if (DequeueEvent_LockFree(queue, &event)) {
   2.264 +                WriterData *writer = (WriterData*)event.user.data1;
   2.265 +                ++data->counters[writer->index];
   2.266 +            } else if (queue->active) {
   2.267 +                ++data->waits;
   2.268 +                SDL_Delay(0);
   2.269 +            } else {
   2.270 +                /* We drained the queue, we're done! */
   2.271 +                break;
   2.272 +            }
   2.273 +        }
   2.274 +    } else {
   2.275 +        for ( ; ; ) {
   2.276 +            if (DequeueEvent_Mutex(queue, &event)) {
   2.277 +                WriterData *writer = (WriterData*)event.user.data1;
   2.278 +                ++data->counters[writer->index];
   2.279 +            } else if (queue->active) {
   2.280 +                ++data->waits;
   2.281 +                SDL_Delay(0);
   2.282 +            } else {
   2.283 +                /* We drained the queue, we're done! */
   2.284 +                break;
   2.285 +            }
   2.286 +        }
   2.287 +    }
   2.288 +    SDL_AtomicAdd(&readersRunning, -1);
   2.289 +    SDL_SemPost(readersDone);
   2.290 +    return 0;
   2.291 +}
   2.292 +
   2.293 +static void RunFIFOTest(SDL_bool lock_free)
   2.294 +{
   2.295 +    SDL_EventQueue queue;
   2.296 +    WriterData writerData[NUM_WRITERS];
   2.297 +    ReaderData readerData[NUM_READERS];
   2.298 +    Uint32 start, end;
   2.299 +    int i, j;
   2.300 +    int grand_total;
   2.301 + 
   2.302 +    printf("\nFIFO test---------------------------------------\n\n");
   2.303 +    printf("Mode: %s\n", lock_free ? "LockFree" : "Mutex");
   2.304 +
   2.305 +    readersDone = SDL_CreateSemaphore(0);
   2.306 +    writersDone = SDL_CreateSemaphore(0);
   2.307 +
   2.308 +    SDL_memset(&queue, 0xff, sizeof(queue));
   2.309 +
   2.310 +    InitEventQueue(&queue);
   2.311 +    if (!lock_free) {
   2.312 +        queue.mutex = SDL_CreateMutex();
   2.313 +    }
   2.314 +
   2.315 +    start = SDL_GetTicks();
   2.316 + 
   2.317 +    /* Start the readers first */
   2.318 +    printf("Starting %d readers\n", NUM_READERS);
   2.319 +    SDL_zero(readerData);
   2.320 +    SDL_AtomicSet(&readersRunning, NUM_READERS);
   2.321 +    for (i = 0; i < NUM_READERS; ++i) {
   2.322 +        readerData[i].queue = &queue;
   2.323 +        readerData[i].lock_free = lock_free;
   2.324 +        SDL_CreateThread(FIFO_Reader, &readerData[i]);
   2.325 +    }
   2.326 +
   2.327 +    /* Start up the writers */
   2.328 +    printf("Starting %d writers\n", NUM_WRITERS);
   2.329 +    SDL_zero(writerData);
   2.330 +    SDL_AtomicSet(&writersRunning, NUM_WRITERS);
   2.331 +    for (i = 0; i < NUM_WRITERS; ++i) {
   2.332 +        writerData[i].queue = &queue;
   2.333 +        writerData[i].index = i;
   2.334 +        writerData[i].lock_free = lock_free;
   2.335 +        SDL_CreateThread(FIFO_Writer, &writerData[i]);
   2.336 +    }
   2.337 + 
   2.338 +    /* Wait for the writers */
   2.339 +    while (SDL_AtomicGet(&writersRunning) > 0) {
   2.340 +        SDL_SemWait(writersDone);
   2.341 +    }
   2.342 + 
   2.343 +    /* Shut down the queue so readers exit */
   2.344 +    queue.active = SDL_FALSE;
   2.345 +
   2.346 +    /* Wait for the readers */
   2.347 +    while (SDL_AtomicGet(&readersRunning) > 0) {
   2.348 +        SDL_SemWait(readersDone);
   2.349 +    }
   2.350 +
   2.351 +    end = SDL_GetTicks();
   2.352 + 
   2.353 +    SDL_DestroySemaphore(readersDone);
   2.354 +    SDL_DestroySemaphore(writersDone);
   2.355 +
   2.356 +    if (!lock_free) {
   2.357 +        SDL_DestroyMutex(queue.mutex);
   2.358 +    }
   2.359 + 
   2.360 +    printf("Finished in %f sec\n", (end - start) / 1000.f);
   2.361 +
   2.362 +    printf("\n");
   2.363 +    for (i = 0; i < NUM_WRITERS; ++i) {
   2.364 +        printf("Writer %d wrote %d events, had %d waits\n", i, EVENTS_PER_WRITER, writerData[i].waits);
   2.365 +    }
   2.366 +    printf("Writers wrote %d total events\n", NUM_WRITERS*EVENTS_PER_WRITER);
   2.367 +
   2.368 +    /* Print a breakdown of which readers read messages from which writer */
   2.369 +    printf("\n");
   2.370 +    grand_total = 0;
   2.371 +    for (i = 0; i < NUM_READERS; ++i) {
   2.372 +        int total = 0;
   2.373 +        for (j = 0; j < NUM_WRITERS; ++j) {
   2.374 +            total += readerData[i].counters[j];
   2.375 +        }
   2.376 +        grand_total += total;
   2.377 +        printf("Reader %d read %d events, had %d waits\n", i, total, readerData[i].waits);
   2.378 +        printf("  { ");
   2.379 +        for (j = 0; j < NUM_WRITERS; ++j) {
   2.380 +            if (j > 0) {
   2.381 +                printf(", ");
   2.382 +            }
   2.383 +            printf("%d", readerData[i].counters[j]);
   2.384 +        }
   2.385 +        printf(" }\n");
   2.386 +    }
   2.387 +    printf("Readers read %d total events\n", grand_total);
   2.388 +}
   2.389 +
   2.390 +/* End FIFO test */
   2.391 +/**************************************************************************/
   2.392 +
   2.393  int
   2.394  main(int argc, char *argv[])
   2.395  {
   2.396      RunBasicTest();
   2.397      RunEpicTest();
   2.398 +/* This test is really slow, so don't run it by default */
   2.399 +#if 0
   2.400 +    RunFIFOTest(SDL_FALSE);
   2.401 +#endif
   2.402 +    RunFIFOTest(SDL_TRUE);
   2.403      return 0;
   2.404  }
   2.405 +
   2.406 +/* vi: set ts=4 sw=4 expandtab: */