1 /* 2 * Copyright 2010-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_BYTELOCK_H 28 #define CK_BYTELOCK_H 29 30 /* 31 * The implementations here are derived from the work described in: 32 * Dice, D. and Shavit, N. 2010. TLRW: return of the read-write lock. 33 * In Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms 34 * and Architectures (Thira, Santorini, Greece, June 13 - 15, 2010). 35 * SPAA '10. ACM, New York, NY, 284-293. 36 */ 37 38 #include <ck_cc.h> 39 #include <ck_md.h> 40 #include <ck_pr.h> 41 #include <ck_stdbool.h> 42 #include <ck_stddef.h> 43 #include <ck_limits.h> 44 45 struct ck_bytelock { 46 unsigned int owner; 47 unsigned int n_readers; 48 uint8_t readers[CK_MD_CACHELINE - sizeof(unsigned int) * 2] CK_CC_ALIGN(8); 49 }; 50 typedef struct ck_bytelock ck_bytelock_t; 51 52 #define CK_BYTELOCK_INITIALIZER { 0, 0, {0} } 53 #define CK_BYTELOCK_UNSLOTTED UINT_MAX 54 55 CK_CC_INLINE static void 56 ck_bytelock_init(struct ck_bytelock *bytelock) 57 { 58 unsigned int i; 59 60 bytelock->owner = 0; 61 bytelock->n_readers = 0; 62 for (i = 0; i < sizeof bytelock->readers; i++) 63 bytelock->readers[i] = false; 64 65 ck_pr_barrier(); 66 return; 67 } 68 69 #ifdef CK_F_PR_LOAD_64 70 #define CK_BYTELOCK_LENGTH sizeof(uint64_t) 71 #define CK_BYTELOCK_LOAD ck_pr_load_64 72 #define CK_BYTELOCK_TYPE uint64_t 73 #elif defined(CK_F_PR_LOAD_32) 74 #define CK_BYTELOCK_LENGTH sizeof(uint32_t) 75 #define CK_BYTELOCK_LOAD ck_pr_load_32 76 #define CK_BYTELOCK_TYPE uint32_t 77 #else 78 #error Unsupported platform. 79 #endif 80 81 CK_CC_INLINE static void 82 ck_bytelock_write_lock(struct ck_bytelock *bytelock, unsigned int slot) 83 { 84 CK_BYTELOCK_TYPE *readers = (void *)bytelock->readers; 85 unsigned int i; 86 87 /* Announce upcoming writer acquisition. */ 88 while (ck_pr_cas_uint(&bytelock->owner, 0, slot) == false) 89 ck_pr_stall(); 90 91 /* If we are slotted, we might be upgrading from a read lock. */ 92 if (slot <= sizeof bytelock->readers) 93 ck_pr_store_8(&bytelock->readers[slot - 1], false); 94 95 /* 96 * Wait for slotted readers to drain out. This also provides the 97 * lock acquire semantics. 98 */ 99 ck_pr_fence_atomic_load(); 100 101 for (i = 0; i < sizeof(bytelock->readers) / CK_BYTELOCK_LENGTH; i++) { 102 while (CK_BYTELOCK_LOAD(&readers[i]) != false) 103 ck_pr_stall(); 104 } 105 106 /* Wait for unslotted readers to drain out. */ 107 while (ck_pr_load_uint(&bytelock->n_readers) != 0) 108 ck_pr_stall(); 109 110 ck_pr_fence_lock(); 111 return; 112 } 113 114 #undef CK_BYTELOCK_LENGTH 115 #undef CK_BYTELOCK_LOAD 116 #undef CK_BYTELOCK_TYPE 117 118 CK_CC_INLINE static void 119 ck_bytelock_write_unlock(struct ck_bytelock *bytelock) 120 { 121 122 ck_pr_fence_unlock(); 123 ck_pr_store_uint(&bytelock->owner, 0); 124 return; 125 } 126 127 CK_CC_INLINE static void 128 ck_bytelock_read_lock(struct ck_bytelock *bytelock, unsigned int slot) 129 { 130 131 if (ck_pr_load_uint(&bytelock->owner) == slot) { 132 ck_pr_store_8(&bytelock->readers[slot - 1], true); 133 ck_pr_fence_strict_store(); 134 ck_pr_store_uint(&bytelock->owner, 0); 135 return; 136 } 137 138 /* Unslotted threads will have to use the readers counter. */ 139 if (slot > sizeof bytelock->readers) { 140 for (;;) { 141 ck_pr_inc_uint(&bytelock->n_readers); 142 ck_pr_fence_atomic_load(); 143 if (ck_pr_load_uint(&bytelock->owner) == 0) 144 break; 145 ck_pr_dec_uint(&bytelock->n_readers); 146 147 while (ck_pr_load_uint(&bytelock->owner) != 0) 148 ck_pr_stall(); 149 } 150 151 ck_pr_fence_lock(); 152 return; 153 } 154 155 slot -= 1; 156 for (;;) { 157 #ifdef CK_F_PR_FAA_8 158 ck_pr_fas_8(&bytelock->readers[slot], true); 159 ck_pr_fence_atomic_load(); 160 #else 161 ck_pr_store_8(&bytelock->readers[slot], true); 162 ck_pr_fence_store_load(); 163 #endif 164 165 /* 166 * If there is no owner at this point, our slot has 167 * already been published and it is guaranteed no 168 * write acquisition will succeed until we drain out. 169 */ 170 if (ck_pr_load_uint(&bytelock->owner) == 0) 171 break; 172 173 ck_pr_store_8(&bytelock->readers[slot], false); 174 while (ck_pr_load_uint(&bytelock->owner) != 0) 175 ck_pr_stall(); 176 } 177 178 ck_pr_fence_lock(); 179 return; 180 } 181 182 CK_CC_INLINE static void 183 ck_bytelock_read_unlock(struct ck_bytelock *bytelock, unsigned int slot) 184 { 185 186 ck_pr_fence_unlock(); 187 188 if (slot > sizeof bytelock->readers) 189 ck_pr_dec_uint(&bytelock->n_readers); 190 else 191 ck_pr_store_8(&bytelock->readers[slot - 1], false); 192 193 return; 194 } 195 196 #endif /* CK_BYTELOCK_H */ 197