1/* 2 * Copyright 2011-2015 Samy Al Bahra. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 */ 26 27#ifndef CK_RWLOCK_H 28#define CK_RWLOCK_H 29 30#include <ck_elide.h> 31#include <ck_pr.h> 32#include <ck_stdbool.h> 33#include <ck_stddef.h> 34 35struct ck_rwlock { 36 unsigned int writer; 37 unsigned int n_readers; 38}; 39typedef struct ck_rwlock ck_rwlock_t; 40 41#define CK_RWLOCK_INITIALIZER {0, 0} 42 43CK_CC_INLINE static void 44ck_rwlock_init(struct ck_rwlock *rw) 45{ 46 47 rw->writer = 0; 48 rw->n_readers = 0; 49 ck_pr_barrier(); 50 return; 51} 52 53CK_CC_INLINE static void 54ck_rwlock_write_unlock(ck_rwlock_t *rw) 55{ 56 57 ck_pr_fence_unlock(); 58 ck_pr_store_uint(&rw->writer, 0); 59 return; 60} 61 62CK_CC_INLINE static bool 63ck_rwlock_locked_writer(ck_rwlock_t *rw) 64{ 65 bool r; 66 67 r = ck_pr_load_uint(&rw->writer); 68 ck_pr_fence_acquire(); 69 return r; 70} 71 72CK_CC_INLINE static void 73ck_rwlock_write_downgrade(ck_rwlock_t *rw) 74{ 75 76 ck_pr_inc_uint(&rw->n_readers); 77 ck_rwlock_write_unlock(rw); 78 return; 79} 80 81CK_CC_INLINE static bool 82ck_rwlock_locked(ck_rwlock_t *rw) 83{ 84 bool l; 85 86 l = ck_pr_load_uint(&rw->n_readers) | 87 ck_pr_load_uint(&rw->writer); 88 ck_pr_fence_acquire(); 89 return l; 90} 91 92CK_CC_INLINE static bool 93ck_rwlock_write_trylock(ck_rwlock_t *rw) 94{ 95 96 if (ck_pr_fas_uint(&rw->writer, 1) != 0) 97 return false; 98 99 ck_pr_fence_atomic_load(); 100 101 if (ck_pr_load_uint(&rw->n_readers) != 0) { 102 ck_rwlock_write_unlock(rw); 103 return false; 104 } 105 106 ck_pr_fence_lock(); 107 return true; 108} 109 110CK_ELIDE_TRYLOCK_PROTOTYPE(ck_rwlock_write, ck_rwlock_t, 111 ck_rwlock_locked, ck_rwlock_write_trylock) 112 113CK_CC_INLINE static void 114ck_rwlock_write_lock(ck_rwlock_t *rw) 115{ 116 117 while (ck_pr_fas_uint(&rw->writer, 1) != 0) 118 ck_pr_stall(); 119 120 ck_pr_fence_atomic_load(); 121 122 while (ck_pr_load_uint(&rw->n_readers) != 0) 123 ck_pr_stall(); 124 125 ck_pr_fence_lock(); 126 return; 127} 128 129CK_ELIDE_PROTOTYPE(ck_rwlock_write, ck_rwlock_t, 130 ck_rwlock_locked, ck_rwlock_write_lock, 131 ck_rwlock_locked_writer, ck_rwlock_write_unlock) 132 133CK_CC_INLINE static bool 134ck_rwlock_read_trylock(ck_rwlock_t *rw) 135{ 136 137 if (ck_pr_load_uint(&rw->writer) != 0) 138 return false; 139 140 ck_pr_inc_uint(&rw->n_readers); 141 142 /* 143 * Serialize with respect to concurrent write 144 * lock operation. 145 */ 146 ck_pr_fence_atomic_load(); 147 148 if (ck_pr_load_uint(&rw->writer) == 0) { 149 ck_pr_fence_lock(); 150 return true; 151 } 152 153 ck_pr_dec_uint(&rw->n_readers); 154 return false; 155} 156 157CK_ELIDE_TRYLOCK_PROTOTYPE(ck_rwlock_read, ck_rwlock_t, 158 ck_rwlock_locked_writer, ck_rwlock_read_trylock) 159 160CK_CC_INLINE static void 161ck_rwlock_read_lock(ck_rwlock_t *rw) 162{ 163 164 for (;;) { 165 while (ck_pr_load_uint(&rw->writer) != 0) 166 ck_pr_stall(); 167 168 ck_pr_inc_uint(&rw->n_readers); 169 170 /* 171 * Serialize with respect to concurrent write 172 * lock operation. 173 */ 174 ck_pr_fence_atomic_load(); 175 176 if (ck_pr_load_uint(&rw->writer) == 0) 177 break; 178 179 ck_pr_dec_uint(&rw->n_readers); 180 } 181 182 /* Acquire semantics are necessary. */ 183 ck_pr_fence_load(); 184 return; 185} 186 187CK_CC_INLINE static bool 188ck_rwlock_locked_reader(ck_rwlock_t *rw) 189{ 190 191 ck_pr_fence_load(); 192 return ck_pr_load_uint(&rw->n_readers); 193} 194 195CK_CC_INLINE static void 196ck_rwlock_read_unlock(ck_rwlock_t *rw) 197{ 198 199 ck_pr_fence_load_atomic(); 200 ck_pr_dec_uint(&rw->n_readers); 201 return; 202} 203 204CK_ELIDE_PROTOTYPE(ck_rwlock_read, ck_rwlock_t, 205 ck_rwlock_locked_writer, ck_rwlock_read_lock, 206 ck_rwlock_locked_reader, ck_rwlock_read_unlock) 207 208/* 209 * Recursive writer reader-writer lock implementation. 210 */ 211struct ck_rwlock_recursive { 212 struct ck_rwlock rw; 213 unsigned int wc; 214}; 215typedef struct ck_rwlock_recursive ck_rwlock_recursive_t; 216 217#define CK_RWLOCK_RECURSIVE_INITIALIZER {CK_RWLOCK_INITIALIZER, 0} 218 219CK_CC_INLINE static void 220ck_rwlock_recursive_write_lock(ck_rwlock_recursive_t *rw, unsigned int tid) 221{ 222 unsigned int o; 223 224 o = ck_pr_load_uint(&rw->rw.writer); 225 if (o == tid) 226 goto leave; 227 228 while (ck_pr_cas_uint(&rw->rw.writer, 0, tid) == false) 229 ck_pr_stall(); 230 231 ck_pr_fence_atomic_load(); 232 233 while (ck_pr_load_uint(&rw->rw.n_readers) != 0) 234 ck_pr_stall(); 235 236 ck_pr_fence_lock(); 237leave: 238 rw->wc++; 239 return; 240} 241 242CK_CC_INLINE static bool 243ck_rwlock_recursive_write_trylock(ck_rwlock_recursive_t *rw, unsigned int tid) 244{ 245 unsigned int o; 246 247 o = ck_pr_load_uint(&rw->rw.writer); 248 if (o == tid) 249 goto leave; 250 251 if (ck_pr_cas_uint(&rw->rw.writer, 0, tid) == false) 252 return false; 253 254 ck_pr_fence_atomic_load(); 255 256 if (ck_pr_load_uint(&rw->rw.n_readers) != 0) { 257 ck_pr_store_uint(&rw->rw.writer, 0); 258 return false; 259 } 260 261 ck_pr_fence_lock(); 262leave: 263 rw->wc++; 264 return true; 265} 266 267CK_CC_INLINE static void 268ck_rwlock_recursive_write_unlock(ck_rwlock_recursive_t *rw) 269{ 270 271 if (--rw->wc == 0) { 272 ck_pr_fence_unlock(); 273 ck_pr_store_uint(&rw->rw.writer, 0); 274 } 275 276 return; 277} 278 279CK_CC_INLINE static void 280ck_rwlock_recursive_read_lock(ck_rwlock_recursive_t *rw) 281{ 282 283 ck_rwlock_read_lock(&rw->rw); 284 return; 285} 286 287CK_CC_INLINE static bool 288ck_rwlock_recursive_read_trylock(ck_rwlock_recursive_t *rw) 289{ 290 291 return ck_rwlock_read_trylock(&rw->rw); 292} 293 294CK_CC_INLINE static void 295ck_rwlock_recursive_read_unlock(ck_rwlock_recursive_t *rw) 296{ 297 298 ck_rwlock_read_unlock(&rw->rw); 299 return; 300} 301 302#endif /* CK_RWLOCK_H */ 303