1309260Scognet/* 2309260Scognet * Copyright 2011-2015 Samy Al Bahra. 3309260Scognet * All rights reserved. 4309260Scognet * 5309260Scognet * Redistribution and use in source and binary forms, with or without 6309260Scognet * modification, are permitted provided that the following conditions 7309260Scognet * are met: 8309260Scognet * 1. Redistributions of source code must retain the above copyright 9309260Scognet * notice, this list of conditions and the following disclaimer. 10309260Scognet * 2. Redistributions in binary form must reproduce the above copyright 11309260Scognet * notice, this list of conditions and the following disclaimer in the 12309260Scognet * documentation and/or other materials provided with the distribution. 13309260Scognet * 14309260Scognet * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15309260Scognet * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16309260Scognet * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17309260Scognet * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18309260Scognet * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19309260Scognet * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20309260Scognet * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21309260Scognet * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22309260Scognet * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23309260Scognet * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24309260Scognet * SUCH DAMAGE. 25309260Scognet */ 26309260Scognet 27309260Scognet#ifndef CK_RWLOCK_H 28309260Scognet#define CK_RWLOCK_H 29309260Scognet 30309260Scognet#include <ck_elide.h> 31309260Scognet#include <ck_pr.h> 32309260Scognet#include <ck_stdbool.h> 33309260Scognet#include <ck_stddef.h> 34309260Scognet 35309260Scognetstruct ck_rwlock { 36309260Scognet unsigned int writer; 37309260Scognet unsigned int n_readers; 38309260Scognet}; 39309260Scognettypedef struct ck_rwlock ck_rwlock_t; 40309260Scognet 41309260Scognet#define CK_RWLOCK_INITIALIZER {0, 0} 42309260Scognet 43309260ScognetCK_CC_INLINE static void 44309260Scognetck_rwlock_init(struct ck_rwlock *rw) 45309260Scognet{ 46309260Scognet 47309260Scognet rw->writer = 0; 48309260Scognet rw->n_readers = 0; 49309260Scognet ck_pr_barrier(); 50309260Scognet return; 51309260Scognet} 52309260Scognet 53309260ScognetCK_CC_INLINE static void 54309260Scognetck_rwlock_write_unlock(ck_rwlock_t *rw) 55309260Scognet{ 56309260Scognet 57309260Scognet ck_pr_fence_unlock(); 58309260Scognet ck_pr_store_uint(&rw->writer, 0); 59309260Scognet return; 60309260Scognet} 61309260Scognet 62309260ScognetCK_CC_INLINE static bool 63309260Scognetck_rwlock_locked_writer(ck_rwlock_t *rw) 64309260Scognet{ 65309260Scognet bool r; 66309260Scognet 67309260Scognet r = ck_pr_load_uint(&rw->writer); 68309260Scognet ck_pr_fence_acquire(); 69309260Scognet return r; 70309260Scognet} 71309260Scognet 72309260ScognetCK_CC_INLINE static void 73309260Scognetck_rwlock_write_downgrade(ck_rwlock_t *rw) 74309260Scognet{ 75309260Scognet 76309260Scognet ck_pr_inc_uint(&rw->n_readers); 77309260Scognet ck_rwlock_write_unlock(rw); 78309260Scognet return; 79309260Scognet} 80309260Scognet 81309260ScognetCK_CC_INLINE static bool 82309260Scognetck_rwlock_locked(ck_rwlock_t *rw) 83309260Scognet{ 84309260Scognet bool l; 85309260Scognet 86309260Scognet l = ck_pr_load_uint(&rw->n_readers) | 87309260Scognet ck_pr_load_uint(&rw->writer); 88309260Scognet ck_pr_fence_acquire(); 89309260Scognet return l; 90309260Scognet} 91309260Scognet 92309260ScognetCK_CC_INLINE static bool 93309260Scognetck_rwlock_write_trylock(ck_rwlock_t *rw) 94309260Scognet{ 95309260Scognet 96309260Scognet if (ck_pr_fas_uint(&rw->writer, 1) != 0) 97309260Scognet return false; 98309260Scognet 99309260Scognet ck_pr_fence_atomic_load(); 100309260Scognet 101309260Scognet if (ck_pr_load_uint(&rw->n_readers) != 0) { 102309260Scognet ck_rwlock_write_unlock(rw); 103309260Scognet return false; 104309260Scognet } 105309260Scognet 106309260Scognet ck_pr_fence_lock(); 107309260Scognet return true; 108309260Scognet} 109309260Scognet 110309260ScognetCK_ELIDE_TRYLOCK_PROTOTYPE(ck_rwlock_write, ck_rwlock_t, 111309260Scognet ck_rwlock_locked, ck_rwlock_write_trylock) 112309260Scognet 113309260ScognetCK_CC_INLINE static void 114309260Scognetck_rwlock_write_lock(ck_rwlock_t *rw) 115309260Scognet{ 116309260Scognet 117309260Scognet while (ck_pr_fas_uint(&rw->writer, 1) != 0) 118309260Scognet ck_pr_stall(); 119309260Scognet 120309260Scognet ck_pr_fence_atomic_load(); 121309260Scognet 122309260Scognet while (ck_pr_load_uint(&rw->n_readers) != 0) 123309260Scognet ck_pr_stall(); 124309260Scognet 125309260Scognet ck_pr_fence_lock(); 126309260Scognet return; 127309260Scognet} 128309260Scognet 129309260ScognetCK_ELIDE_PROTOTYPE(ck_rwlock_write, ck_rwlock_t, 130309260Scognet ck_rwlock_locked, ck_rwlock_write_lock, 131309260Scognet ck_rwlock_locked_writer, ck_rwlock_write_unlock) 132309260Scognet 133309260ScognetCK_CC_INLINE static bool 134309260Scognetck_rwlock_read_trylock(ck_rwlock_t *rw) 135309260Scognet{ 136309260Scognet 137309260Scognet if (ck_pr_load_uint(&rw->writer) != 0) 138309260Scognet return false; 139309260Scognet 140309260Scognet ck_pr_inc_uint(&rw->n_readers); 141309260Scognet 142309260Scognet /* 143309260Scognet * Serialize with respect to concurrent write 144309260Scognet * lock operation. 145309260Scognet */ 146309260Scognet ck_pr_fence_atomic_load(); 147309260Scognet 148309260Scognet if (ck_pr_load_uint(&rw->writer) == 0) { 149309260Scognet ck_pr_fence_lock(); 150309260Scognet return true; 151309260Scognet } 152309260Scognet 153309260Scognet ck_pr_dec_uint(&rw->n_readers); 154309260Scognet return false; 155309260Scognet} 156309260Scognet 157309260ScognetCK_ELIDE_TRYLOCK_PROTOTYPE(ck_rwlock_read, ck_rwlock_t, 158309260Scognet ck_rwlock_locked_writer, ck_rwlock_read_trylock) 159309260Scognet 160309260ScognetCK_CC_INLINE static void 161309260Scognetck_rwlock_read_lock(ck_rwlock_t *rw) 162309260Scognet{ 163309260Scognet 164309260Scognet for (;;) { 165309260Scognet while (ck_pr_load_uint(&rw->writer) != 0) 166309260Scognet ck_pr_stall(); 167309260Scognet 168309260Scognet ck_pr_inc_uint(&rw->n_readers); 169309260Scognet 170309260Scognet /* 171309260Scognet * Serialize with respect to concurrent write 172309260Scognet * lock operation. 173309260Scognet */ 174309260Scognet ck_pr_fence_atomic_load(); 175309260Scognet 176309260Scognet if (ck_pr_load_uint(&rw->writer) == 0) 177309260Scognet break; 178309260Scognet 179309260Scognet ck_pr_dec_uint(&rw->n_readers); 180309260Scognet } 181309260Scognet 182309260Scognet /* Acquire semantics are necessary. */ 183309260Scognet ck_pr_fence_load(); 184309260Scognet return; 185309260Scognet} 186309260Scognet 187309260ScognetCK_CC_INLINE static bool 188309260Scognetck_rwlock_locked_reader(ck_rwlock_t *rw) 189309260Scognet{ 190309260Scognet 191309260Scognet ck_pr_fence_load(); 192309260Scognet return ck_pr_load_uint(&rw->n_readers); 193309260Scognet} 194309260Scognet 195309260ScognetCK_CC_INLINE static void 196309260Scognetck_rwlock_read_unlock(ck_rwlock_t *rw) 197309260Scognet{ 198309260Scognet 199309260Scognet ck_pr_fence_load_atomic(); 200309260Scognet ck_pr_dec_uint(&rw->n_readers); 201309260Scognet return; 202309260Scognet} 203309260Scognet 204309260ScognetCK_ELIDE_PROTOTYPE(ck_rwlock_read, ck_rwlock_t, 205309260Scognet ck_rwlock_locked_writer, ck_rwlock_read_lock, 206309260Scognet ck_rwlock_locked_reader, ck_rwlock_read_unlock) 207309260Scognet 208309260Scognet/* 209309260Scognet * Recursive writer reader-writer lock implementation. 210309260Scognet */ 211309260Scognetstruct ck_rwlock_recursive { 212309260Scognet struct ck_rwlock rw; 213309260Scognet unsigned int wc; 214309260Scognet}; 215309260Scognettypedef struct ck_rwlock_recursive ck_rwlock_recursive_t; 216309260Scognet 217309260Scognet#define CK_RWLOCK_RECURSIVE_INITIALIZER {CK_RWLOCK_INITIALIZER, 0} 218309260Scognet 219309260ScognetCK_CC_INLINE static void 220309260Scognetck_rwlock_recursive_write_lock(ck_rwlock_recursive_t *rw, unsigned int tid) 221309260Scognet{ 222309260Scognet unsigned int o; 223309260Scognet 224309260Scognet o = ck_pr_load_uint(&rw->rw.writer); 225309260Scognet if (o == tid) 226309260Scognet goto leave; 227309260Scognet 228309260Scognet while (ck_pr_cas_uint(&rw->rw.writer, 0, tid) == false) 229309260Scognet ck_pr_stall(); 230309260Scognet 231309260Scognet ck_pr_fence_atomic_load(); 232309260Scognet 233309260Scognet while (ck_pr_load_uint(&rw->rw.n_readers) != 0) 234309260Scognet ck_pr_stall(); 235309260Scognet 236309260Scognet ck_pr_fence_lock(); 237309260Scognetleave: 238309260Scognet rw->wc++; 239309260Scognet return; 240309260Scognet} 241309260Scognet 242309260ScognetCK_CC_INLINE static bool 243309260Scognetck_rwlock_recursive_write_trylock(ck_rwlock_recursive_t *rw, unsigned int tid) 244309260Scognet{ 245309260Scognet unsigned int o; 246309260Scognet 247309260Scognet o = ck_pr_load_uint(&rw->rw.writer); 248309260Scognet if (o == tid) 249309260Scognet goto leave; 250309260Scognet 251309260Scognet if (ck_pr_cas_uint(&rw->rw.writer, 0, tid) == false) 252309260Scognet return false; 253309260Scognet 254309260Scognet ck_pr_fence_atomic_load(); 255309260Scognet 256309260Scognet if (ck_pr_load_uint(&rw->rw.n_readers) != 0) { 257309260Scognet ck_pr_store_uint(&rw->rw.writer, 0); 258309260Scognet return false; 259309260Scognet } 260309260Scognet 261309260Scognet ck_pr_fence_lock(); 262309260Scognetleave: 263309260Scognet rw->wc++; 264309260Scognet return true; 265309260Scognet} 266309260Scognet 267309260ScognetCK_CC_INLINE static void 268309260Scognetck_rwlock_recursive_write_unlock(ck_rwlock_recursive_t *rw) 269309260Scognet{ 270309260Scognet 271309260Scognet if (--rw->wc == 0) { 272309260Scognet ck_pr_fence_unlock(); 273309260Scognet ck_pr_store_uint(&rw->rw.writer, 0); 274309260Scognet } 275309260Scognet 276309260Scognet return; 277309260Scognet} 278309260Scognet 279309260ScognetCK_CC_INLINE static void 280309260Scognetck_rwlock_recursive_read_lock(ck_rwlock_recursive_t *rw) 281309260Scognet{ 282309260Scognet 283309260Scognet ck_rwlock_read_lock(&rw->rw); 284309260Scognet return; 285309260Scognet} 286309260Scognet 287309260ScognetCK_CC_INLINE static bool 288309260Scognetck_rwlock_recursive_read_trylock(ck_rwlock_recursive_t *rw) 289309260Scognet{ 290309260Scognet 291309260Scognet return ck_rwlock_read_trylock(&rw->rw); 292309260Scognet} 293309260Scognet 294309260ScognetCK_CC_INLINE static void 295309260Scognetck_rwlock_recursive_read_unlock(ck_rwlock_recursive_t *rw) 296309260Scognet{ 297309260Scognet 298309260Scognet ck_rwlock_read_unlock(&rw->rw); 299309260Scognet return; 300309260Scognet} 301309260Scognet 302309260Scognet#endif /* CK_RWLOCK_H */ 303