1 /* $NetBSD: rwlock.c,v 1.15 2025/01/26 16:25:38 christos Exp $ */ 2 3 /* 4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 5 * 6 * SPDX-License-Identifier: MPL-2.0 7 * 8 * This Source Code Form is subject to the terms of the Mozilla Public 9 * License, v. 2.0. If a copy of the MPL was not distributed with this 10 * file, you can obtain one at https://mozilla.org/MPL/2.0/. 11 * 12 * See the COPYRIGHT file distributed with this work for additional 13 * information regarding copyright ownership. 14 */ 15 16 /* 17 * Modified C-RW-WP Implementation from NUMA-Aware Reader-Writer Locks paper: 18 * http://dl.acm.org/citation.cfm?id=2442532 19 * 20 * This work is based on C++ code available from 21 * https://github.com/pramalhe/ConcurrencyFreaks/ 22 * 23 * Copyright (c) 2014-2016, Pedro Ramalhete, Andreia Correia 24 * All rights reserved. 25 * 26 * Redistribution and use in source and binary forms, with or without 27 * modification, are permitted provided that the following conditions are met: 28 * 29 * * Redistributions of source code must retain the above copyright 30 * notice, this list of conditions and the following disclaimer. 31 * * Redistributions in binary form must reproduce the above copyright 32 * notice, this list of conditions and the following disclaimer in the 33 * documentation and/or other materials provided with the distribution. 34 * * Neither the name of Concurrency Freaks nor the 35 * names of its contributors may be used to endorse or promote products 36 * derived from this software without specific prior written permission. 37 * 38 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 39 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 40 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 41 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> 42 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 43 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 44 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 45 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 46 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 47 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 48 * THE POSSIBILITY OF SUCH DAMAGE. 49 */ 50 51 /*! \file */ 52 53 #include <inttypes.h> 54 #include <stdbool.h> 55 #include <stddef.h> 56 #include <stdlib.h> 57 #include <unistd.h> 58 59 #include <isc/atomic.h> 60 #include <isc/hash.h> 61 #include <isc/pause.h> 62 #include <isc/rwlock.h> 63 #include <isc/thread.h> 64 #include <isc/tid.h> 65 #include <isc/util.h> 66 67 #include "probes.h" 68 69 static atomic_uint_fast16_t isc__crwlock_workers = 128; 70 71 #define ISC_RWLOCK_UNLOCKED false 72 #define ISC_RWLOCK_LOCKED true 73 74 /* 75 * See https://csce.ucmss.com/cr/books/2017/LFS/CSREA2017/FCS3701.pdf for 76 * guidance on patience level 77 */ 78 #ifndef RWLOCK_MAX_READER_PATIENCE 79 #define RWLOCK_MAX_READER_PATIENCE 500 80 #endif /* ifndef RWLOCK_MAX_READER_PATIENCE */ 81 82 static void 83 read_indicator_wait_until_empty(isc_rwlock_t *rwl); 84 85 #include <stdio.h> 86 87 static void 88 read_indicator_arrive(isc_rwlock_t *rwl) { 89 (void)atomic_fetch_add_release(&rwl->readers_ingress, 1); 90 } 91 92 static void 93 read_indicator_depart(isc_rwlock_t *rwl) { 94 (void)atomic_fetch_add_release(&rwl->readers_egress, 1); 95 } 96 97 static bool 98 read_indicator_isempty(isc_rwlock_t *rwl) { 99 return atomic_load_acquire(&rwl->readers_egress) == 100 atomic_load_acquire(&rwl->readers_ingress); 101 } 102 103 static void 104 writers_barrier_raise(isc_rwlock_t *rwl) { 105 (void)atomic_fetch_add_release(&rwl->writers_barrier, 1); 106 } 107 108 static void 109 writers_barrier_lower(isc_rwlock_t *rwl) { 110 (void)atomic_fetch_sub_release(&rwl->writers_barrier, 1); 111 } 112 113 static bool 114 writers_barrier_israised(isc_rwlock_t *rwl) { 115 return atomic_load_acquire(&rwl->writers_barrier) > 0; 116 } 117 118 static bool 119 writers_lock_islocked(isc_rwlock_t *rwl) { 120 return atomic_load_acquire(&rwl->writers_lock) == ISC_RWLOCK_LOCKED; 121 } 122 123 static bool 124 writers_lock_acquire(isc_rwlock_t *rwl) { 125 return atomic_compare_exchange_weak_acq_rel( 126 &rwl->writers_lock, &(bool){ ISC_RWLOCK_UNLOCKED }, 127 ISC_RWLOCK_LOCKED); 128 } 129 130 static void 131 writers_lock_release(isc_rwlock_t *rwl) { 132 REQUIRE(atomic_compare_exchange_strong_acq_rel( 133 &rwl->writers_lock, &(bool){ ISC_RWLOCK_LOCKED }, 134 ISC_RWLOCK_UNLOCKED)); 135 } 136 137 #define ran_out_of_patience(cnt) (cnt >= RWLOCK_MAX_READER_PATIENCE) 138 139 void 140 isc_rwlock_rdlock(isc_rwlock_t *rwl) { 141 uint32_t cnt = 0; 142 bool barrier_raised = false; 143 144 LIBISC_RWLOCK_RDLOCK_REQ(rwl); 145 146 while (true) { 147 read_indicator_arrive(rwl); 148 if (!writers_lock_islocked(rwl)) { 149 /* Acquired lock in read-only mode */ 150 break; 151 } 152 153 /* Writer has acquired the lock, must reset to 0 and wait */ 154 read_indicator_depart(rwl); 155 156 while (writers_lock_islocked(rwl)) { 157 isc_pause(); 158 if (ran_out_of_patience(cnt++) && !barrier_raised) { 159 writers_barrier_raise(rwl); 160 barrier_raised = true; 161 } 162 } 163 } 164 if (barrier_raised) { 165 writers_barrier_lower(rwl); 166 } 167 168 LIBISC_RWLOCK_RDLOCK_ACQ(rwl); 169 } 170 171 isc_result_t 172 isc_rwlock_tryrdlock(isc_rwlock_t *rwl) { 173 read_indicator_arrive(rwl); 174 if (writers_lock_islocked(rwl)) { 175 /* Writer has acquired the lock, release the read lock */ 176 read_indicator_depart(rwl); 177 178 LIBISC_RWLOCK_TRYRDLOCK(rwl, ISC_R_LOCKBUSY); 179 return ISC_R_LOCKBUSY; 180 } 181 182 /* Acquired lock in read-only mode */ 183 LIBISC_RWLOCK_TRYRDLOCK(rwl, ISC_R_SUCCESS); 184 return ISC_R_SUCCESS; 185 } 186 187 void 188 isc_rwlock_rdunlock(isc_rwlock_t *rwl) { 189 read_indicator_depart(rwl); 190 LIBISC_RWLOCK_RDUNLOCK(rwl); 191 } 192 193 isc_result_t 194 isc_rwlock_tryupgrade(isc_rwlock_t *rwl) { 195 /* Write Barriers has been raised */ 196 if (writers_barrier_israised(rwl)) { 197 LIBISC_RWLOCK_TRYUPGRADE(rwl, ISC_R_LOCKBUSY); 198 return ISC_R_LOCKBUSY; 199 } 200 201 /* Try to acquire the write-lock */ 202 if (!writers_lock_acquire(rwl)) { 203 LIBISC_RWLOCK_TRYUPGRADE(rwl, ISC_R_LOCKBUSY); 204 return ISC_R_LOCKBUSY; 205 } 206 207 /* Unlock the read-lock */ 208 read_indicator_depart(rwl); 209 210 if (!read_indicator_isempty(rwl)) { 211 /* Re-acquire the read-lock back */ 212 read_indicator_arrive(rwl); 213 214 /* Unlock the write-lock */ 215 writers_lock_release(rwl); 216 LIBISC_RWLOCK_TRYUPGRADE(rwl, ISC_R_LOCKBUSY); 217 return ISC_R_LOCKBUSY; 218 } 219 LIBISC_RWLOCK_TRYUPGRADE(rwl, ISC_R_SUCCESS); 220 return ISC_R_SUCCESS; 221 } 222 223 static void 224 read_indicator_wait_until_empty(isc_rwlock_t *rwl) { 225 /* Write-lock was acquired, now wait for running Readers to finish */ 226 while (true) { 227 if (read_indicator_isempty(rwl)) { 228 break; 229 } 230 isc_pause(); 231 } 232 } 233 234 void 235 isc_rwlock_wrlock(isc_rwlock_t *rwl) { 236 LIBISC_RWLOCK_WRLOCK_REQ(rwl); 237 238 /* Write Barriers has been raised, wait */ 239 while (writers_barrier_israised(rwl)) { 240 isc_pause(); 241 } 242 243 /* Try to acquire the write-lock */ 244 while (!writers_lock_acquire(rwl)) { 245 isc_pause(); 246 } 247 248 read_indicator_wait_until_empty(rwl); 249 250 LIBISC_RWLOCK_WRLOCK_ACQ(rwl); 251 } 252 253 void 254 isc_rwlock_wrunlock(isc_rwlock_t *rwl) { 255 writers_lock_release(rwl); 256 LIBISC_RWLOCK_WRUNLOCK(rwl); 257 } 258 259 isc_result_t 260 isc_rwlock_trywrlock(isc_rwlock_t *rwl) { 261 /* Write Barriers has been raised */ 262 if (writers_barrier_israised(rwl)) { 263 LIBISC_RWLOCK_TRYWRLOCK(rwl, ISC_R_LOCKBUSY); 264 return ISC_R_LOCKBUSY; 265 } 266 267 /* Try to acquire the write-lock */ 268 if (!writers_lock_acquire(rwl)) { 269 LIBISC_RWLOCK_TRYWRLOCK(rwl, ISC_R_LOCKBUSY); 270 return ISC_R_LOCKBUSY; 271 } 272 273 if (!read_indicator_isempty(rwl)) { 274 /* Unlock the write-lock */ 275 writers_lock_release(rwl); 276 277 LIBISC_RWLOCK_TRYWRLOCK(rwl, ISC_R_LOCKBUSY); 278 return ISC_R_LOCKBUSY; 279 } 280 281 LIBISC_RWLOCK_TRYWRLOCK(rwl, ISC_R_SUCCESS); 282 return ISC_R_SUCCESS; 283 } 284 285 void 286 isc_rwlock_downgrade(isc_rwlock_t *rwl) { 287 read_indicator_arrive(rwl); 288 289 writers_lock_release(rwl); 290 291 LIBISC_RWLOCK_DOWNGRADE(rwl); 292 } 293 294 void 295 isc_rwlock_init(isc_rwlock_t *rwl) { 296 REQUIRE(rwl != NULL); 297 298 atomic_init(&rwl->writers_lock, ISC_RWLOCK_UNLOCKED); 299 atomic_init(&rwl->writers_barrier, 0); 300 atomic_init(&rwl->readers_ingress, 0); 301 atomic_init(&rwl->readers_egress, 0); 302 LIBISC_RWLOCK_INIT(rwl); 303 } 304 305 void 306 isc_rwlock_destroy(isc_rwlock_t *rwl) { 307 LIBISC_RWLOCK_DESTROY(rwl); 308 /* Check whether write lock has been unlocked */ 309 REQUIRE(atomic_load(&rwl->writers_lock) == ISC_RWLOCK_UNLOCKED); 310 REQUIRE(read_indicator_isempty(rwl)); 311 } 312 313 void 314 isc_rwlock_setworkers(uint16_t workers) { 315 atomic_store(&isc__crwlock_workers, workers); 316 } 317