annotate_barrier.c revision ec2e1465487b4747961d9cc1f872066e8c671237
1ea2a03ce907b2a34a24032a6c76551efb7455dc2bart/* 2ea2a03ce907b2a34a24032a6c76551efb7455dc2bart * Test whether all data races are detected in a multithreaded program with 3ea2a03ce907b2a34a24032a6c76551efb7455dc2bart * user-annotated barriers. See also pth_barrier.c. 4ea2a03ce907b2a34a24032a6c76551efb7455dc2bart */ 5ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 6ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 7ea2a03ce907b2a34a24032a6c76551efb7455dc2bart#define _GNU_SOURCE 8ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 9ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 10ea2a03ce907b2a34a24032a6c76551efb7455dc2bart#include <pthread.h> /* pthread_create() */ 11ea2a03ce907b2a34a24032a6c76551efb7455dc2bart#include <stdio.h> /* fprintf() */ 12ea2a03ce907b2a34a24032a6c76551efb7455dc2bart#include <stdlib.h> /* atoi() */ 13ea2a03ce907b2a34a24032a6c76551efb7455dc2bart#include <string.h> /* memset() */ 14ea2a03ce907b2a34a24032a6c76551efb7455dc2bart#include "../../drd/drd.h" 15ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 16ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 17ec2e1465487b4747961d9cc1f872066e8c671237bart#define BARRIER_SERIAL_THREAD -1 18ec2e1465487b4747961d9cc1f872066e8c671237bart 19ec2e1465487b4747961d9cc1f872066e8c671237bart 20ea2a03ce907b2a34a24032a6c76551efb7455dc2bart/* Local datatypes. */ 21ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 22ea2a03ce907b2a34a24032a6c76551efb7455dc2barttypedef struct 23ea2a03ce907b2a34a24032a6c76551efb7455dc2bart{ 24ea2a03ce907b2a34a24032a6c76551efb7455dc2bart /* 25ea2a03ce907b2a34a24032a6c76551efb7455dc2bart * number of threads that must call barrier_wait() before any of them 26ea2a03ce907b2a34a24032a6c76551efb7455dc2bart * successfully return from the call. 27ea2a03ce907b2a34a24032a6c76551efb7455dc2bart */ 28ea2a03ce907b2a34a24032a6c76551efb7455dc2bart unsigned thread_count; 29ea2a03ce907b2a34a24032a6c76551efb7455dc2bart /* number of barrier_wait() calls since last barrier. */ 30ea2a03ce907b2a34a24032a6c76551efb7455dc2bart volatile unsigned wait_count; 31ea2a03ce907b2a34a24032a6c76551efb7455dc2bart /* 32ea2a03ce907b2a34a24032a6c76551efb7455dc2bart * barrier count. Only the least significant bit matters -- a single bit 33ea2a03ce907b2a34a24032a6c76551efb7455dc2bart * counter would be sufficient. 34ea2a03ce907b2a34a24032a6c76551efb7455dc2bart */ 35ea2a03ce907b2a34a24032a6c76551efb7455dc2bart volatile unsigned barrier_count; 36ea2a03ce907b2a34a24032a6c76551efb7455dc2bart} barrier_t; 37ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 38ea2a03ce907b2a34a24032a6c76551efb7455dc2bartstruct threadinfo 39ea2a03ce907b2a34a24032a6c76551efb7455dc2bart{ 40ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barrier_t* b; 41ea2a03ce907b2a34a24032a6c76551efb7455dc2bart pthread_t tid; 42ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int* array; 43ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int iterations; 44ea2a03ce907b2a34a24032a6c76551efb7455dc2bart}; 45ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 46ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 47ea2a03ce907b2a34a24032a6c76551efb7455dc2bart/* Local variables. */ 48ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 49ea2a03ce907b2a34a24032a6c76551efb7455dc2bartstatic int s_silent; 50ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 51ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 52ea2a03ce907b2a34a24032a6c76551efb7455dc2bart/* Local functions. */ 53ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 54ea2a03ce907b2a34a24032a6c76551efb7455dc2bartstatic void barrier_init(barrier_t* b, unsigned count) 55ea2a03ce907b2a34a24032a6c76551efb7455dc2bart{ 56ea2a03ce907b2a34a24032a6c76551efb7455dc2bart b->thread_count = count; 57ea2a03ce907b2a34a24032a6c76551efb7455dc2bart b->wait_count = 0; 58ea2a03ce907b2a34a24032a6c76551efb7455dc2bart b->barrier_count = 0; 59ea2a03ce907b2a34a24032a6c76551efb7455dc2bart ANNOTATE_BARRIER_INIT(b, count, 0); 60ea2a03ce907b2a34a24032a6c76551efb7455dc2bart} 61ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 62ea2a03ce907b2a34a24032a6c76551efb7455dc2bartstatic void barrier_destroy(barrier_t* b) 63ea2a03ce907b2a34a24032a6c76551efb7455dc2bart{ 64ea2a03ce907b2a34a24032a6c76551efb7455dc2bart ANNOTATE_BARRIER_DESTROY(b); 65ea2a03ce907b2a34a24032a6c76551efb7455dc2bart memset(b, 0, sizeof(*b)); 66ea2a03ce907b2a34a24032a6c76551efb7455dc2bart} 67ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 68ea2a03ce907b2a34a24032a6c76551efb7455dc2bartstatic int barrier_wait(barrier_t* b) 69ea2a03ce907b2a34a24032a6c76551efb7455dc2bart{ 70ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int res; 71ea2a03ce907b2a34a24032a6c76551efb7455dc2bart unsigned barrier_count; 72ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 73ea2a03ce907b2a34a24032a6c76551efb7455dc2bart res = 0; 74ea2a03ce907b2a34a24032a6c76551efb7455dc2bart ANNOTATE_BARRIER_WAIT_BEFORE(b); 75ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barrier_count = b->barrier_count; 76ea2a03ce907b2a34a24032a6c76551efb7455dc2bart if (__sync_add_and_fetch(&b->wait_count, 1) == b->thread_count) 77ea2a03ce907b2a34a24032a6c76551efb7455dc2bart { 78ea2a03ce907b2a34a24032a6c76551efb7455dc2bart __sync_sub_and_fetch(&b->wait_count, b->thread_count); 79ea2a03ce907b2a34a24032a6c76551efb7455dc2bart __sync_add_and_fetch(&b->barrier_count, 1); 80ec2e1465487b4747961d9cc1f872066e8c671237bart res = BARRIER_SERIAL_THREAD; 81ea2a03ce907b2a34a24032a6c76551efb7455dc2bart } 82ea2a03ce907b2a34a24032a6c76551efb7455dc2bart else 83ea2a03ce907b2a34a24032a6c76551efb7455dc2bart { 84ea2a03ce907b2a34a24032a6c76551efb7455dc2bart while (b->barrier_count == barrier_count) 85ea2a03ce907b2a34a24032a6c76551efb7455dc2bart pthread_yield(); 86ea2a03ce907b2a34a24032a6c76551efb7455dc2bart } 87ea2a03ce907b2a34a24032a6c76551efb7455dc2bart ANNOTATE_BARRIER_WAIT_AFTER(b); 88ea2a03ce907b2a34a24032a6c76551efb7455dc2bart return res; 89ea2a03ce907b2a34a24032a6c76551efb7455dc2bart} 90ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 91ea2a03ce907b2a34a24032a6c76551efb7455dc2bart/* 92ea2a03ce907b2a34a24032a6c76551efb7455dc2bart * Single thread, which touches p->iterations elements of array p->array. 93ea2a03ce907b2a34a24032a6c76551efb7455dc2bart * Each modification of an element of p->array is a data race. 94ea2a03ce907b2a34a24032a6c76551efb7455dc2bart */ 95ea2a03ce907b2a34a24032a6c76551efb7455dc2bartstatic void* threadfunc(struct threadinfo* p) 96ea2a03ce907b2a34a24032a6c76551efb7455dc2bart{ 97ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int i; 98ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int* const array = p->array; 99ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barrier_t* const b = p->b; 100ea2a03ce907b2a34a24032a6c76551efb7455dc2bart if (! s_silent) 101ea2a03ce907b2a34a24032a6c76551efb7455dc2bart printf("thread %lx iteration 0\n", pthread_self()); 102ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barrier_wait(b); 103ea2a03ce907b2a34a24032a6c76551efb7455dc2bart for (i = 0; i < p->iterations; i++) 104ea2a03ce907b2a34a24032a6c76551efb7455dc2bart { 105ea2a03ce907b2a34a24032a6c76551efb7455dc2bart if (! s_silent) 106ea2a03ce907b2a34a24032a6c76551efb7455dc2bart printf("thread %lx iteration %d; writing to %p\n", 107ea2a03ce907b2a34a24032a6c76551efb7455dc2bart pthread_self(), i + 1, &array[i]); 108ea2a03ce907b2a34a24032a6c76551efb7455dc2bart array[i] = i; 109ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barrier_wait(b); 110ea2a03ce907b2a34a24032a6c76551efb7455dc2bart } 111ea2a03ce907b2a34a24032a6c76551efb7455dc2bart return 0; 112ea2a03ce907b2a34a24032a6c76551efb7455dc2bart} 113ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 114ea2a03ce907b2a34a24032a6c76551efb7455dc2bart/* Actual test, consisting of nthread threads. */ 115ea2a03ce907b2a34a24032a6c76551efb7455dc2bartstatic void barriers_and_races(const int nthread, const int iterations) 116ea2a03ce907b2a34a24032a6c76551efb7455dc2bart{ 117ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int i; 118ea2a03ce907b2a34a24032a6c76551efb7455dc2bart struct threadinfo* t; 119ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barrier_t b; 120ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int* array; 121ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 122ea2a03ce907b2a34a24032a6c76551efb7455dc2bart t = malloc(nthread * sizeof(struct threadinfo)); 123ea2a03ce907b2a34a24032a6c76551efb7455dc2bart array = malloc(iterations * sizeof(array[0])); 124ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 125ea2a03ce907b2a34a24032a6c76551efb7455dc2bart if (! s_silent) 126ea2a03ce907b2a34a24032a6c76551efb7455dc2bart printf("&array[0] = %p\n", array); 127ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 128ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barrier_init(&b, nthread); 129ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 130ea2a03ce907b2a34a24032a6c76551efb7455dc2bart for (i = 0; i < nthread; i++) 131ea2a03ce907b2a34a24032a6c76551efb7455dc2bart { 132ea2a03ce907b2a34a24032a6c76551efb7455dc2bart t[i].b = &b; 133ea2a03ce907b2a34a24032a6c76551efb7455dc2bart t[i].array = array; 134ea2a03ce907b2a34a24032a6c76551efb7455dc2bart t[i].iterations = iterations; 135ea2a03ce907b2a34a24032a6c76551efb7455dc2bart pthread_create(&t[i].tid, 0, (void*(*)(void*))threadfunc, &t[i]); 136ea2a03ce907b2a34a24032a6c76551efb7455dc2bart } 137ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 138ea2a03ce907b2a34a24032a6c76551efb7455dc2bart for (i = 0; i < nthread; i++) 139ea2a03ce907b2a34a24032a6c76551efb7455dc2bart pthread_join(t[i].tid, 0); 140ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 141ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barrier_destroy(&b); 142ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 143ea2a03ce907b2a34a24032a6c76551efb7455dc2bart free(array); 144ea2a03ce907b2a34a24032a6c76551efb7455dc2bart free(t); 145ea2a03ce907b2a34a24032a6c76551efb7455dc2bart} 146ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 147ea2a03ce907b2a34a24032a6c76551efb7455dc2bartint main(int argc, char** argv) 148ea2a03ce907b2a34a24032a6c76551efb7455dc2bart{ 149ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int nthread; 150ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int iterations; 151ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 152ea2a03ce907b2a34a24032a6c76551efb7455dc2bart nthread = (argc > 1) ? atoi(argv[1]) : 2; 153ea2a03ce907b2a34a24032a6c76551efb7455dc2bart iterations = (argc > 2) ? atoi(argv[2]) : 3; 154ea2a03ce907b2a34a24032a6c76551efb7455dc2bart s_silent = (argc > 3) ? atoi(argv[3]) : 0; 155ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 156ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barriers_and_races(nthread, iterations); 157ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 158ea2a03ce907b2a34a24032a6c76551efb7455dc2bart fprintf(stderr, "Done.\n"); 159ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 160ea2a03ce907b2a34a24032a6c76551efb7455dc2bart return 0; 161ea2a03ce907b2a34a24032a6c76551efb7455dc2bart} 162