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() */ 14422b779a97b15e92a2fe84ed21103c1bc0c3b88bbart#include <unistd.h> /* usleep() */ 15ea2a03ce907b2a34a24032a6c76551efb7455dc2bart#include "../../drd/drd.h" 160ccdc4a1e148ce89d99a4593b777c0fd9192bce0bart#include "../../config.h" 17ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 18ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 19ec2e1465487b4747961d9cc1f872066e8c671237bart#define BARRIER_SERIAL_THREAD -1 20ec2e1465487b4747961d9cc1f872066e8c671237bart 21ec2e1465487b4747961d9cc1f872066e8c671237bart 22ea2a03ce907b2a34a24032a6c76551efb7455dc2bart/* Local datatypes. */ 23ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 24ea2a03ce907b2a34a24032a6c76551efb7455dc2barttypedef struct 25ea2a03ce907b2a34a24032a6c76551efb7455dc2bart{ 26ea2a03ce907b2a34a24032a6c76551efb7455dc2bart /* 27ea2a03ce907b2a34a24032a6c76551efb7455dc2bart * number of threads that must call barrier_wait() before any of them 28ea2a03ce907b2a34a24032a6c76551efb7455dc2bart * successfully return from the call. 29ea2a03ce907b2a34a24032a6c76551efb7455dc2bart */ 30ea2a03ce907b2a34a24032a6c76551efb7455dc2bart unsigned thread_count; 31ea2a03ce907b2a34a24032a6c76551efb7455dc2bart /* number of barrier_wait() calls since last barrier. */ 32ea2a03ce907b2a34a24032a6c76551efb7455dc2bart volatile unsigned wait_count; 33ea2a03ce907b2a34a24032a6c76551efb7455dc2bart /* 34ea2a03ce907b2a34a24032a6c76551efb7455dc2bart * barrier count. Only the least significant bit matters -- a single bit 35ea2a03ce907b2a34a24032a6c76551efb7455dc2bart * counter would be sufficient. 36ea2a03ce907b2a34a24032a6c76551efb7455dc2bart */ 37ea2a03ce907b2a34a24032a6c76551efb7455dc2bart volatile unsigned barrier_count; 38ea2a03ce907b2a34a24032a6c76551efb7455dc2bart} barrier_t; 39ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 40ea2a03ce907b2a34a24032a6c76551efb7455dc2bartstruct threadinfo 41ea2a03ce907b2a34a24032a6c76551efb7455dc2bart{ 42422b779a97b15e92a2fe84ed21103c1bc0c3b88bbart int thread_num; 43ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barrier_t* b; 44ea2a03ce907b2a34a24032a6c76551efb7455dc2bart pthread_t tid; 45ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int* array; 46ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int iterations; 47ea2a03ce907b2a34a24032a6c76551efb7455dc2bart}; 48ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 49ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 50ea2a03ce907b2a34a24032a6c76551efb7455dc2bart/* Local variables. */ 51ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 52ea2a03ce907b2a34a24032a6c76551efb7455dc2bartstatic int s_silent; 53ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 54ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 55ea2a03ce907b2a34a24032a6c76551efb7455dc2bart/* Local functions. */ 56ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 57ea2a03ce907b2a34a24032a6c76551efb7455dc2bartstatic void barrier_init(barrier_t* b, unsigned count) 58ea2a03ce907b2a34a24032a6c76551efb7455dc2bart{ 59ea2a03ce907b2a34a24032a6c76551efb7455dc2bart b->thread_count = count; 60ea2a03ce907b2a34a24032a6c76551efb7455dc2bart b->wait_count = 0; 61ea2a03ce907b2a34a24032a6c76551efb7455dc2bart b->barrier_count = 0; 62ea2a03ce907b2a34a24032a6c76551efb7455dc2bart ANNOTATE_BARRIER_INIT(b, count, 0); 63ea2a03ce907b2a34a24032a6c76551efb7455dc2bart} 64ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 65ea2a03ce907b2a34a24032a6c76551efb7455dc2bartstatic void barrier_destroy(barrier_t* b) 66ea2a03ce907b2a34a24032a6c76551efb7455dc2bart{ 67ea2a03ce907b2a34a24032a6c76551efb7455dc2bart ANNOTATE_BARRIER_DESTROY(b); 68ea2a03ce907b2a34a24032a6c76551efb7455dc2bart memset(b, 0, sizeof(*b)); 69ea2a03ce907b2a34a24032a6c76551efb7455dc2bart} 70ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 71ea2a03ce907b2a34a24032a6c76551efb7455dc2bartstatic int barrier_wait(barrier_t* b) 72ea2a03ce907b2a34a24032a6c76551efb7455dc2bart{ 73ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int res; 74ea2a03ce907b2a34a24032a6c76551efb7455dc2bart unsigned barrier_count; 75ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 76ea2a03ce907b2a34a24032a6c76551efb7455dc2bart res = 0; 77ea2a03ce907b2a34a24032a6c76551efb7455dc2bart ANNOTATE_BARRIER_WAIT_BEFORE(b); 78ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barrier_count = b->barrier_count; 79ea2a03ce907b2a34a24032a6c76551efb7455dc2bart if (__sync_add_and_fetch(&b->wait_count, 1) == b->thread_count) 80ea2a03ce907b2a34a24032a6c76551efb7455dc2bart { 81ea2a03ce907b2a34a24032a6c76551efb7455dc2bart __sync_sub_and_fetch(&b->wait_count, b->thread_count); 82ea2a03ce907b2a34a24032a6c76551efb7455dc2bart __sync_add_and_fetch(&b->barrier_count, 1); 83ec2e1465487b4747961d9cc1f872066e8c671237bart res = BARRIER_SERIAL_THREAD; 84ea2a03ce907b2a34a24032a6c76551efb7455dc2bart } 85ea2a03ce907b2a34a24032a6c76551efb7455dc2bart else 86ea2a03ce907b2a34a24032a6c76551efb7455dc2bart { 87ea2a03ce907b2a34a24032a6c76551efb7455dc2bart while (b->barrier_count == barrier_count) 889ec8b073a6ebdd109ac45bd46b702750338e49a3bart { 890ccdc4a1e148ce89d99a4593b777c0fd9192bce0bart#ifndef HAVE_PTHREAD_YIELD 909ec8b073a6ebdd109ac45bd46b702750338e49a3bart /* Darwin doesn't have an implementation of pthread_yield(). */ 919ec8b073a6ebdd109ac45bd46b702750338e49a3bart usleep(100 * 1000); 929ec8b073a6ebdd109ac45bd46b702750338e49a3bart#else 93ea2a03ce907b2a34a24032a6c76551efb7455dc2bart pthread_yield(); 949ec8b073a6ebdd109ac45bd46b702750338e49a3bart#endif 959ec8b073a6ebdd109ac45bd46b702750338e49a3bart } 96ea2a03ce907b2a34a24032a6c76551efb7455dc2bart } 97ea2a03ce907b2a34a24032a6c76551efb7455dc2bart ANNOTATE_BARRIER_WAIT_AFTER(b); 98ea2a03ce907b2a34a24032a6c76551efb7455dc2bart return res; 99ea2a03ce907b2a34a24032a6c76551efb7455dc2bart} 100ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 101ea2a03ce907b2a34a24032a6c76551efb7455dc2bart/* 102ea2a03ce907b2a34a24032a6c76551efb7455dc2bart * Single thread, which touches p->iterations elements of array p->array. 103ea2a03ce907b2a34a24032a6c76551efb7455dc2bart * Each modification of an element of p->array is a data race. 104ea2a03ce907b2a34a24032a6c76551efb7455dc2bart */ 105ea2a03ce907b2a34a24032a6c76551efb7455dc2bartstatic void* threadfunc(struct threadinfo* p) 106ea2a03ce907b2a34a24032a6c76551efb7455dc2bart{ 107ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int i; 108ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int* const array = p->array; 109ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barrier_t* const b = p->b; 110ea2a03ce907b2a34a24032a6c76551efb7455dc2bart if (! s_silent) 111422b779a97b15e92a2fe84ed21103c1bc0c3b88bbart printf("thread %d iteration 0\n", p->thread_num); 112ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barrier_wait(b); 113ea2a03ce907b2a34a24032a6c76551efb7455dc2bart for (i = 0; i < p->iterations; i++) 114ea2a03ce907b2a34a24032a6c76551efb7455dc2bart { 115ea2a03ce907b2a34a24032a6c76551efb7455dc2bart if (! s_silent) 116422b779a97b15e92a2fe84ed21103c1bc0c3b88bbart printf("thread %d iteration %d; writing to %p\n", 117422b779a97b15e92a2fe84ed21103c1bc0c3b88bbart p->thread_num, i + 1, &array[i]); 118ea2a03ce907b2a34a24032a6c76551efb7455dc2bart array[i] = i; 119ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barrier_wait(b); 120ea2a03ce907b2a34a24032a6c76551efb7455dc2bart } 121ea2a03ce907b2a34a24032a6c76551efb7455dc2bart return 0; 122ea2a03ce907b2a34a24032a6c76551efb7455dc2bart} 123ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 124ea2a03ce907b2a34a24032a6c76551efb7455dc2bart/* Actual test, consisting of nthread threads. */ 125ea2a03ce907b2a34a24032a6c76551efb7455dc2bartstatic void barriers_and_races(const int nthread, const int iterations) 126ea2a03ce907b2a34a24032a6c76551efb7455dc2bart{ 1279e7188556ee1a1fe8ca26f05f75e184d57f00514bart const struct timespec delay = { 0, 100 * 1000 * 1000 }; 128ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int i; 129ea2a03ce907b2a34a24032a6c76551efb7455dc2bart struct threadinfo* t; 130ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barrier_t b; 131ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int* array; 132ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 133ea2a03ce907b2a34a24032a6c76551efb7455dc2bart t = malloc(nthread * sizeof(struct threadinfo)); 134ea2a03ce907b2a34a24032a6c76551efb7455dc2bart array = malloc(iterations * sizeof(array[0])); 135ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 136ea2a03ce907b2a34a24032a6c76551efb7455dc2bart if (! s_silent) 137ea2a03ce907b2a34a24032a6c76551efb7455dc2bart printf("&array[0] = %p\n", array); 138ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 139ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barrier_init(&b, nthread); 140ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 141ea2a03ce907b2a34a24032a6c76551efb7455dc2bart for (i = 0; i < nthread; i++) 142ea2a03ce907b2a34a24032a6c76551efb7455dc2bart { 143422b779a97b15e92a2fe84ed21103c1bc0c3b88bbart t[i].thread_num = i + 1; 144ea2a03ce907b2a34a24032a6c76551efb7455dc2bart t[i].b = &b; 145ea2a03ce907b2a34a24032a6c76551efb7455dc2bart t[i].array = array; 146ea2a03ce907b2a34a24032a6c76551efb7455dc2bart t[i].iterations = iterations; 147ea2a03ce907b2a34a24032a6c76551efb7455dc2bart pthread_create(&t[i].tid, 0, (void*(*)(void*))threadfunc, &t[i]); 1489e7188556ee1a1fe8ca26f05f75e184d57f00514bart nanosleep(&delay, 0); 149ea2a03ce907b2a34a24032a6c76551efb7455dc2bart } 150ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 151ea2a03ce907b2a34a24032a6c76551efb7455dc2bart for (i = 0; i < nthread; i++) 152ea2a03ce907b2a34a24032a6c76551efb7455dc2bart pthread_join(t[i].tid, 0); 153ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 154ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barrier_destroy(&b); 155ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 156ea2a03ce907b2a34a24032a6c76551efb7455dc2bart free(array); 157ea2a03ce907b2a34a24032a6c76551efb7455dc2bart free(t); 158ea2a03ce907b2a34a24032a6c76551efb7455dc2bart} 159ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 160ea2a03ce907b2a34a24032a6c76551efb7455dc2bartint main(int argc, char** argv) 161ea2a03ce907b2a34a24032a6c76551efb7455dc2bart{ 162ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int nthread; 163ea2a03ce907b2a34a24032a6c76551efb7455dc2bart int iterations; 164ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 165ea2a03ce907b2a34a24032a6c76551efb7455dc2bart nthread = (argc > 1) ? atoi(argv[1]) : 2; 166ea2a03ce907b2a34a24032a6c76551efb7455dc2bart iterations = (argc > 2) ? atoi(argv[2]) : 3; 167ea2a03ce907b2a34a24032a6c76551efb7455dc2bart s_silent = (argc > 3) ? atoi(argv[3]) : 0; 168ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 169ea2a03ce907b2a34a24032a6c76551efb7455dc2bart barriers_and_races(nthread, iterations); 170ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 171ea2a03ce907b2a34a24032a6c76551efb7455dc2bart fprintf(stderr, "Done.\n"); 172ea2a03ce907b2a34a24032a6c76551efb7455dc2bart 173ea2a03ce907b2a34a24032a6c76551efb7455dc2bart return 0; 174ea2a03ce907b2a34a24032a6c76551efb7455dc2bart} 175