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_BRLOCK_H 28 #define CK_BRLOCK_H 29 30 /* 31 * Big reader spinlocks provide cache-local contention-free read 32 * lock acquisition in the absence of writers. This comes at the 33 * cost of O(n) write lock acquisition. They were first implemented 34 * in the Linux kernel by Ingo Molnar and David S. Miller around the 35 * year 2000. 36 * 37 * This implementation is thread-agnostic which comes at the cost 38 * of larger reader objects due to necessary linkage overhead. In 39 * order to cut down on TLB pressure, it is recommended to allocate 40 * these objects on the same page. 41 */ 42 43 #include <ck_pr.h> 44 #include <ck_stdbool.h> 45 #include <ck_stddef.h> 46 47 struct ck_brlock_reader { 48 unsigned int n_readers; 49 struct ck_brlock_reader *previous; 50 struct ck_brlock_reader *next; 51 }; 52 typedef struct ck_brlock_reader ck_brlock_reader_t; 53 54 #define CK_BRLOCK_READER_INITIALIZER {0} 55 56 struct ck_brlock { 57 struct ck_brlock_reader *readers; 58 unsigned int writer; 59 }; 60 typedef struct ck_brlock ck_brlock_t; 61 62 #define CK_BRLOCK_INITIALIZER {NULL, false} 63 64 CK_CC_INLINE static void 65 ck_brlock_init(struct ck_brlock *br) 66 { 67 68 br->readers = NULL; 69 br->writer = false; 70 ck_pr_barrier(); 71 return; 72 } 73 74 CK_CC_INLINE static void 75 ck_brlock_write_lock(struct ck_brlock *br) 76 { 77 struct ck_brlock_reader *cursor; 78 79 /* 80 * As the frequency of write acquisitions should be low, 81 * there is no point to more advanced contention avoidance. 82 */ 83 while (ck_pr_fas_uint(&br->writer, true) == true) 84 ck_pr_stall(); 85 86 ck_pr_fence_atomic_load(); 87 88 /* The reader list is protected under the writer br. */ 89 for (cursor = br->readers; cursor != NULL; cursor = cursor->next) { 90 while (ck_pr_load_uint(&cursor->n_readers) != 0) 91 ck_pr_stall(); 92 } 93 94 ck_pr_fence_lock(); 95 return; 96 } 97 98 CK_CC_INLINE static void 99 ck_brlock_write_unlock(struct ck_brlock *br) 100 { 101 102 ck_pr_fence_unlock(); 103 ck_pr_store_uint(&br->writer, false); 104 return; 105 } 106 107 CK_CC_INLINE static bool 108 ck_brlock_write_trylock(struct ck_brlock *br, unsigned int factor) 109 { 110 struct ck_brlock_reader *cursor; 111 unsigned int steps = 0; 112 113 while (ck_pr_fas_uint(&br->writer, true) == true) { 114 if (++steps >= factor) 115 return false; 116 117 ck_pr_stall(); 118 } 119 120 /* 121 * We do not require a strict fence here as atomic RMW operations 122 * are serializing. 123 */ 124 ck_pr_fence_atomic_load(); 125 126 for (cursor = br->readers; cursor != NULL; cursor = cursor->next) { 127 while (ck_pr_load_uint(&cursor->n_readers) != 0) { 128 if (++steps >= factor) { 129 ck_brlock_write_unlock(br); 130 return false; 131 } 132 133 ck_pr_stall(); 134 } 135 } 136 137 ck_pr_fence_lock(); 138 return true; 139 } 140 141 CK_CC_INLINE static void 142 ck_brlock_read_register(struct ck_brlock *br, struct ck_brlock_reader *reader) 143 { 144 145 reader->n_readers = 0; 146 reader->previous = NULL; 147 148 /* Implicit compiler barrier. */ 149 ck_brlock_write_lock(br); 150 151 reader->next = ck_pr_load_ptr(&br->readers); 152 if (reader->next != NULL) 153 reader->next->previous = reader; 154 ck_pr_store_ptr(&br->readers, reader); 155 156 ck_brlock_write_unlock(br); 157 return; 158 } 159 160 CK_CC_INLINE static void 161 ck_brlock_read_unregister(struct ck_brlock *br, struct ck_brlock_reader *reader) 162 { 163 164 ck_brlock_write_lock(br); 165 166 if (reader->next != NULL) 167 reader->next->previous = reader->previous; 168 169 if (reader->previous != NULL) 170 reader->previous->next = reader->next; 171 else 172 br->readers = reader->next; 173 174 ck_brlock_write_unlock(br); 175 return; 176 } 177 178 CK_CC_INLINE static void 179 ck_brlock_read_lock(struct ck_brlock *br, struct ck_brlock_reader *reader) 180 { 181 182 if (reader->n_readers >= 1) { 183 ck_pr_store_uint(&reader->n_readers, reader->n_readers + 1); 184 return; 185 } 186 187 for (;;) { 188 while (ck_pr_load_uint(&br->writer) == true) 189 ck_pr_stall(); 190 191 #if defined(__x86__) || defined(__x86_64__) 192 ck_pr_fas_uint(&reader->n_readers, 1); 193 194 /* 195 * Serialize reader counter update with respect to load of 196 * writer. 197 */ 198 ck_pr_fence_atomic_load(); 199 #else 200 ck_pr_store_uint(&reader->n_readers, 1); 201 202 /* 203 * Serialize reader counter update with respect to load of 204 * writer. 205 */ 206 ck_pr_fence_store_load(); 207 #endif 208 209 if (ck_pr_load_uint(&br->writer) == false) 210 break; 211 212 ck_pr_store_uint(&reader->n_readers, 0); 213 } 214 215 ck_pr_fence_lock(); 216 return; 217 } 218 219 CK_CC_INLINE static bool 220 ck_brlock_read_trylock(struct ck_brlock *br, 221 struct ck_brlock_reader *reader, 222 unsigned int factor) 223 { 224 unsigned int steps = 0; 225 226 if (reader->n_readers >= 1) { 227 ck_pr_store_uint(&reader->n_readers, reader->n_readers + 1); 228 return true; 229 } 230 231 for (;;) { 232 while (ck_pr_load_uint(&br->writer) == true) { 233 if (++steps >= factor) 234 return false; 235 236 ck_pr_stall(); 237 } 238 239 #if defined(__x86__) || defined(__x86_64__) 240 ck_pr_fas_uint(&reader->n_readers, 1); 241 242 /* 243 * Serialize reader counter update with respect to load of 244 * writer. 245 */ 246 ck_pr_fence_atomic_load(); 247 #else 248 ck_pr_store_uint(&reader->n_readers, 1); 249 250 /* 251 * Serialize reader counter update with respect to load of 252 * writer. 253 */ 254 ck_pr_fence_store_load(); 255 #endif 256 257 if (ck_pr_load_uint(&br->writer) == false) 258 break; 259 260 ck_pr_store_uint(&reader->n_readers, 0); 261 262 if (++steps >= factor) 263 return false; 264 } 265 266 ck_pr_fence_lock(); 267 return true; 268 } 269 270 CK_CC_INLINE static void 271 ck_brlock_read_unlock(struct ck_brlock_reader *reader) 272 { 273 274 ck_pr_fence_unlock(); 275 ck_pr_store_uint(&reader->n_readers, reader->n_readers - 1); 276 return; 277 } 278 279 #endif /* CK_BRLOCK_H */ 280