Mercurial > sdl-ios-xcode

comparison test/testatomic.c @ 5100:470ede30189c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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.
author Sam Lantinga <slouken@libsdl.org>
date Tue, 25 Jan 2011 23:23:52 -0800
parents 342b158efbbe
children 1b3678ac9804
comparison
equal deleted inserted replaced
5099:b938ad843e52 5100:470ede30189c
229 } 229 }
230 230
231 /* End atomic operation test */ 231 /* End atomic operation test */
232 /**************************************************************************/ 232 /**************************************************************************/
233 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
234 int 620 int
235 main(int argc, char *argv[]) 621 main(int argc, char *argv[])
236 { 622 {
237 RunBasicTest(); 623 RunBasicTest();
238 RunEpicTest(); 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);
239 return 0; 630 return 0;
240 } 631 }
632
633 /* vi: set ts=4 sw=4 expandtab: */