1ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 2ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * @file annotate_rwlock.c 3ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * 4ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * @brief Multithreaded test program that triggers various access patterns 5ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * without triggering any race conditions using a reader-writer lock 6ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * implemented via busy-waiting. Annotations are used to tell DRD 7ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * which higher-level rwlock operations are being performed. 8ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 9ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 10ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 11ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define _GNU_SOURCE 1 12ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 13ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include <assert.h> 14ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include <pthread.h> 15ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include <stdio.h> 16ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include <unistd.h> /* usleep() */ 17ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "../../config.h" 18ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "../../drd/drd.h" 19ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 20ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 21ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifndef HAVE_BUILTIN_ATOMIC 22ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#error Sorry, but this test program can only be compiled by a compiler that\ 23ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownhas built-in functions for atomic memory access. 24ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 25ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 26ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 27ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef struct { 28ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown volatile int locked; 29ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown int writer_count; 30ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown int reader_count; 31ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} rwlock_t; 32ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 33ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 34ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic rwlock_t s_rwlock; 35ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic int s_counter; 36ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 37ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 38ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void rwlock_init(rwlock_t* p) 39ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 40ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown DRD_IGNORE_VAR(*p); 41ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p->locked = 0; 42ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p->writer_count = 0; 43ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p->reader_count = 0; 44ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ANNOTATE_RWLOCK_CREATE(p); 45ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 46ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 47ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void rwlock_destroy(rwlock_t* p) 48ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 49ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ANNOTATE_RWLOCK_DESTROY(p); 50ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(p->locked == 0); 51ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(p->writer_count == 0); 52ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(p->reader_count == 0); 53ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 54ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 55ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void rwlock_rdlock(rwlock_t* p) 56ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 57ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (1) 58ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 59ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (__sync_val_compare_and_swap(&p->locked, 0, 1) == 1) 60ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ; 61ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (p->writer_count == 0) 62ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 63ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifndef HAVE_PTHREAD_YIELD 64ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Darwin doesn't have an implementation of pthread_yield(). */ 65ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown usleep(100 * 1000); 66ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#else 67ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pthread_yield(); 68ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 69ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (void) __sync_fetch_and_sub(&p->locked, 1); 70ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 71ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p->reader_count++; 72ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(p->reader_count >= 0); 73ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(p->writer_count >= 0); 74ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(p->reader_count == 0 || p->writer_count == 0); 75ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (void) __sync_fetch_and_sub(&p->locked, 1); 76ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ANNOTATE_READERLOCK_ACQUIRED(p); 77ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 78ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 79ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void rwlock_wrlock(rwlock_t* p) 80ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 81ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (1) 82ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 83ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (__sync_val_compare_and_swap(&p->locked, 0, 1) == 1) 84ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ; 85ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (p->reader_count == 0) 86ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 87ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifndef HAVE_PTHREAD_YIELD 88ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Darwin doesn't have an implementation of pthread_yield(). */ 89ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown usleep(100 * 1000); 90ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#else 91ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pthread_yield(); 92ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 93ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (void) __sync_fetch_and_sub(&p->locked, 1); 94ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 95ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p->writer_count++; 96ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(p->reader_count >= 0); 97ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(p->writer_count >= 0); 98ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(p->reader_count == 0 || p->writer_count == 0); 99ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (void) __sync_fetch_and_sub(&p->locked, 1); 100ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ANNOTATE_WRITERLOCK_ACQUIRED(p); 101ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 102ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 103ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void rwlock_unlock(rwlock_t* p) 104ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 105ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (__sync_val_compare_and_swap(&p->locked, 0, 1) == 1) 106ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ; 107ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (p->reader_count > 0) 108ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 109ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p->reader_count--; 110ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ANNOTATE_READERLOCK_RELEASED(p); 111ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 112ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 113ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 114ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p->writer_count--; 115ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ANNOTATE_WRITERLOCK_RELEASED(p); 116ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 117ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(p->reader_count >= 0); 118ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(p->writer_count >= 0); 119ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(p->reader_count == 0 || p->writer_count == 0); 120ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (void) __sync_fetch_and_sub(&p->locked, 1); 121ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 122ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 123ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void* thread_func(void* arg) 124ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 125ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown int i; 126ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown int sum = 0; 127ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 128ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < 1000; i++) 129ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 130ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown rwlock_rdlock(&s_rwlock); 131ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sum += s_counter; 132ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown rwlock_unlock(&s_rwlock); 133ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown rwlock_wrlock(&s_rwlock); 134ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s_counter++; 135ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown rwlock_unlock(&s_rwlock); 136ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 137ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 138ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 139ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 140ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 141ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownint main(int argc, char** argv) 142ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 143ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const int thread_count = 10; 144ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pthread_t tid[thread_count]; 145ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown int i; 146ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 147ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown rwlock_init(&s_rwlock); 148ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < thread_count; i++) 149ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 150ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pthread_create(&tid[i], 0, thread_func, 0); 151ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 152ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 153ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < thread_count; i++) 154ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown { 155ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pthread_join(tid[i], 0); 156ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 157ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown rwlock_destroy(&s_rwlock); 158ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 159ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown fprintf(stderr, "Finished.\n"); 160ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 161ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 162ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 163