1 /*- 2 * Copyright (c) 2007 Stephan Uphoff <ups@FreeBSD.org> 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 * 3. Neither the name of the author nor the names of any co-contributors 14 * may be used to endorse or promote products derived from this software 15 * without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 */ 29 30 /* 31 * Machine independent bits of reader/writer lock implementation. 32 */ 33 34 #include <sys/cdefs.h> 35 __FBSDID("$FreeBSD$"); 36 37 #include "opt_ddb.h" 38 39 #include <sys/param.h> 40 #include <sys/systm.h> 41 42 #include <sys/kernel.h> 43 #include <sys/ktr.h> 44 #include <sys/lock.h> 45 #include <sys/mutex.h> 46 #include <sys/proc.h> 47 #include <sys/rmlock.h> 48 #include <sys/sched.h> 49 #include <sys/smp.h> 50 #include <sys/systm.h> 51 #include <sys/turnstile.h> 52 #include <sys/lock_profile.h> 53 #include <machine/cpu.h> 54 55 #ifdef DDB 56 #include <ddb/ddb.h> 57 #endif 58 59 #define RMPF_ONQUEUE 1 60 #define RMPF_SIGNAL 2 61 62 /* 63 * To support usage of rmlock in CVs and msleep 64 * yet another list for the priority tracker 65 * would be needed. 66 * Using this lock for cv and msleep also does 67 * not seem very useful 68 */ 69 70 static __inline void compiler_memory_barrier(void) { 71 __asm __volatile("":::"memory"); 72 } 73 74 static void assert_rm(struct lock_object *lock, int what); 75 static void lock_rm(struct lock_object *lock, int how); 76 static int unlock_rm(struct lock_object *lock); 77 78 struct lock_class lock_class_rm = { 79 .lc_name = "rm", 80 .lc_flags = LC_SLEEPLOCK | LC_RECURSABLE, 81 .lc_assert = assert_rm, 82 #if 0 83 #ifdef DDB 84 .lc_ddb_show = db_show_rwlock, 85 #endif 86 #endif 87 .lc_lock = lock_rm, 88 .lc_unlock = unlock_rm, 89 }; 90 91 static void 92 assert_rm(struct lock_object *lock, int what) 93 { 94 95 panic("assert_rm called"); 96 } 97 98 static void 99 lock_rm(struct lock_object *lock, int how) { 100 panic("lock_rm called"); 101 } 102 103 static int 104 unlock_rm(struct lock_object *lock) { 105 panic("unlock_rm called"); 106 } 107 108 static struct mtx rm_spinlock; 109 110 MTX_SYSINIT(rm_spinlock, &rm_spinlock, "rm_spinlock", MTX_SPIN); 111 112 /* 113 * Add or remove tracker from per cpu list. 114 * The per cpu list can be traversed at any time in forward 115 * direction from an interrupt on the *local* cpu. 116 */ 117 118 static void inline 119 rm_tracker_add(struct pcpu *pc, struct rm_priotracker* tracker) { 120 struct rm_queue* next; 121 /* Initialize all tracker pointers */ 122 tracker->rmp_cpuQueue.rmq_prev = &pc->pc_rm_queue; 123 next = pc->pc_rm_queue.rmq_next; 124 tracker->rmp_cpuQueue.rmq_next = next; 125 /* rmq_prev is not used during froward traversal */ 126 next->rmq_prev = &tracker->rmp_cpuQueue; 127 /* Update pointer to first element */ 128 pc->pc_rm_queue.rmq_next = &tracker->rmp_cpuQueue; 129 } 130 131 132 static void inline 133 rm_tracker_remove(struct pcpu *pc, struct rm_priotracker* tracker) { 134 struct rm_queue *next, *prev; 135 next = tracker->rmp_cpuQueue.rmq_next; 136 prev = tracker->rmp_cpuQueue.rmq_prev; 137 /* Not used during forward traversal */ 138 next->rmq_prev = prev; 139 /* Remove from list */ 140 prev->rmq_next = next; 141 } 142 143 144 145 146 static void rm_cleanIPI(void *arg) { 147 struct pcpu *pc; 148 struct rmlock* rm = arg; 149 struct rm_priotracker *tracker; 150 struct rm_queue* queue; 151 pc = pcpu_find(curcpu); 152 153 for(queue = pc->pc_rm_queue.rmq_next; 154 queue != &pc->pc_rm_queue; 155 queue = queue->rmq_next) { 156 tracker = (struct rm_priotracker *) queue; 157 if(tracker->rmp_rmlock == rm && tracker->rmp_flags == 0 ) { 158 tracker->rmp_flags = RMPF_ONQUEUE; 159 mtx_lock_spin(&rm_spinlock); 160 LIST_INSERT_HEAD(&rm->rm_activeReaders,tracker, 161 rmp_qentry); 162 mtx_unlock_spin(&rm_spinlock); 163 } 164 } 165 return; 166 } 167 168 169 170 void 171 rm_init(struct rmlock *rm, const char *name, int opts) 172 { 173 rm->rm_noreadtoken = 1; 174 LIST_INIT(&rm->rm_activeReaders); 175 mtx_init(&rm->rm_lock, name, "RM_MTX",MTX_NOWITNESS); 176 lock_init(&rm->lock_object, &lock_class_rm, name, NULL, (opts & LO_RECURSABLE)| LO_WITNESS); 177 178 } 179 180 void 181 rm_destroy(struct rmlock *rm) 182 { 183 mtx_destroy(&rm->rm_lock); 184 lock_destroy(&rm->lock_object); 185 } 186 187 int 188 rm_wowned(struct rmlock *rm) 189 { 190 191 return (mtx_owned(&rm->rm_lock)); 192 } 193 194 void 195 rm_sysinit(void *arg) 196 { 197 struct rm_args *args = arg; 198 rm_init(args->ra_rm, args->ra_desc, args->ra_opts); 199 } 200 201 202 static void 203 _rm_rlock_hard(struct rmlock *rm, struct rm_priotracker* tracker) 204 { 205 struct pcpu *pc; 206 struct rm_queue *queue; 207 struct rm_priotracker* atracker; 208 209 critical_enter(); 210 pc = pcpu_find(curcpu); 211 212 /* Check if we just need to do a proper critical_exit */ 213 if (0 == rm->rm_noreadtoken) { 214 critical_exit(); 215 return; 216 } 217 218 /* Remove our tracker from the per cpu list */ 219 rm_tracker_remove(pc,tracker); 220 221 /* Check to see if the IPI granted us the lock after all */ 222 if(tracker->rmp_flags) { 223 /* Just add back tracker - we hold the lock */ 224 rm_tracker_add(pc,tracker); 225 critical_exit(); 226 return; 227 } 228 229 230 231 /* 232 * We allow readers to aquire a lock even if a writer 233 * is blocked if the lock is recursive and the reader 234 * already holds the lock 235 */ 236 237 if ((rm->lock_object.lo_flags & LO_RECURSABLE) != 0) { 238 /* 239 * Just grand the lock if this thread already have a tracker 240 * for this lock on the per cpu queue 241 */ 242 243 for(queue = pc->pc_rm_queue.rmq_next; 244 queue != &pc->pc_rm_queue; 245 queue = queue->rmq_next) { 246 atracker = (struct rm_priotracker *) queue; 247 if (( atracker->rmp_rmlock == rm) && 248 ( atracker->rmp_thread == tracker->rmp_thread )) { 249 mtx_lock_spin(&rm_spinlock); 250 LIST_INSERT_HEAD(&rm->rm_activeReaders,tracker, 251 rmp_qentry); 252 tracker->rmp_flags = RMPF_ONQUEUE; 253 mtx_unlock_spin(&rm_spinlock); 254 rm_tracker_add(pc,tracker); 255 critical_exit(); 256 return; 257 } 258 } 259 } 260 261 262 sched_unpin(); 263 critical_exit(); 264 265 mtx_lock(&rm->rm_lock); 266 rm->rm_noreadtoken = 0; 267 critical_enter(); 268 269 pc = pcpu_find(curcpu); 270 rm_tracker_add(pc,tracker); 271 sched_pin(); 272 critical_exit(); 273 274 mtx_unlock(&rm->rm_lock); 275 return; 276 } 277 278 void 279 _rm_rlock(struct rmlock *rm, struct rm_priotracker* tracker) 280 { 281 struct thread *td = curthread; 282 struct pcpu *pc; 283 284 tracker->rmp_flags = 0; 285 tracker->rmp_thread = td; 286 tracker->rmp_rmlock = rm; 287 288 td->td_critnest++; /* critical_enter(); */ 289 290 compiler_memory_barrier(); 291 292 pc = cpuid_to_pcpu[td->td_oncpu]; /* pcpu_find(td->td_oncpu); */ 293 294 rm_tracker_add(pc,tracker); 295 296 td->td_pinned++; /* sched_pin(); */ 297 298 compiler_memory_barrier(); 299 300 td->td_critnest--; 301 302 /* 303 * Fast path to combine two common conditions 304 * into a single conditional jump 305 */ 306 307 if (0 == (td->td_owepreempt | rm->rm_noreadtoken)) { 308 return; 309 } 310 311 /* We do not have a read token and need to acquire one */ 312 _rm_rlock_hard(rm,tracker); 313 } 314 315 316 static void 317 _rm_unlock_hard(struct thread *td,struct rm_priotracker* tracker) 318 { 319 320 if (td->td_owepreempt) { 321 td->td_critnest++; 322 critical_exit(); 323 } 324 325 if (!tracker->rmp_flags) { 326 return; 327 } 328 329 330 mtx_lock_spin(&rm_spinlock); 331 LIST_REMOVE(tracker,rmp_qentry); 332 333 if (tracker->rmp_flags & RMPF_SIGNAL) { 334 struct rmlock *rm; 335 struct turnstile* ts; 336 337 rm = tracker->rmp_rmlock; 338 339 turnstile_chain_lock(&rm->lock_object); 340 mtx_unlock_spin(&rm_spinlock); 341 342 ts = turnstile_lookup(&rm->lock_object); 343 344 turnstile_signal(ts, TS_EXCLUSIVE_QUEUE); 345 turnstile_unpend(ts, TS_EXCLUSIVE_LOCK); 346 turnstile_chain_unlock(&rm->lock_object); 347 348 349 } else 350 mtx_unlock_spin(&rm_spinlock); 351 352 } 353 354 void 355 _rm_runlock(struct rmlock *rm, struct rm_priotracker* tracker) 356 { 357 struct pcpu *pc; 358 struct thread *td = tracker->rmp_thread; 359 360 td->td_critnest++; /* critical_enter(); */ 361 pc = cpuid_to_pcpu[td->td_oncpu]; /* pcpu_find(td->td_oncpu); */ 362 rm_tracker_remove(pc,tracker); 363 td->td_critnest--; 364 td->td_pinned--; /* sched_unpin(); */ 365 366 if (0 == (td->td_owepreempt | tracker->rmp_flags)) 367 return; 368 369 370 _rm_unlock_hard(td,tracker); 371 372 373 } 374 375 376 void 377 _rm_wlock(struct rmlock *rm) 378 { 379 struct rm_priotracker *prio; 380 struct turnstile *ts; 381 382 mtx_lock(&rm->rm_lock); 383 384 if (rm->rm_noreadtoken == 0) { 385 /* Get all read tokens back */ 386 387 rm->rm_noreadtoken = 1; 388 389 /* 390 * Assumes rm->rm_noreadtoken update is visible 391 * on other CPUs before rm_cleanIPI is called 392 */ 393 #ifdef SMP 394 smp_rendezvous(smp_no_rendevous_barrier, 395 rm_cleanIPI, 396 smp_no_rendevous_barrier 397 ,rm); 398 399 #else 400 rm_cleanIPI(rm); 401 #endif 402 403 404 mtx_lock_spin(&rm_spinlock); 405 406 while((prio = LIST_FIRST(&rm->rm_activeReaders)) != NULL) { 407 ts = turnstile_trywait(&rm->lock_object); 408 prio->rmp_flags = RMPF_ONQUEUE | RMPF_SIGNAL; 409 mtx_unlock_spin(&rm_spinlock); 410 turnstile_wait(ts,prio->rmp_thread, 411 TS_EXCLUSIVE_QUEUE); 412 mtx_lock_spin(&rm_spinlock); 413 414 } 415 416 mtx_unlock_spin(&rm_spinlock); 417 } 418 419 } 420 421 422 void 423 _rm_wunlock(struct rmlock *rm) 424 { 425 mtx_unlock(&rm->rm_lock); 426 } 427 428 429 #ifdef LOCK_DEBUG 430 431 void _rm_wlock_debug(struct rmlock *rm, const char *file, int line) 432 { 433 434 435 WITNESS_CHECKORDER(&rm->lock_object, LOP_NEWORDER | LOP_EXCLUSIVE, 436 file, line); 437 438 _rm_wlock(rm); 439 440 LOCK_LOG_LOCK("RMWLOCK", &rm->lock_object, 0, 0, file, line); 441 442 WITNESS_LOCK(&rm->lock_object, LOP_EXCLUSIVE, file, line); 443 444 curthread->td_locks++; 445 446 } 447 448 void _rm_wunlock_debug(struct rmlock *rm, const char *file, int line) 449 { 450 curthread->td_locks--; 451 WITNESS_UNLOCK(&rm->lock_object, LOP_EXCLUSIVE, file, line); 452 LOCK_LOG_LOCK("RMWUNLOCK", &rm->lock_object, 0, 0, file, line); 453 _rm_wunlock(rm); 454 } 455 456 457 void 458 _rm_rlock_debug(struct rmlock *rm, struct rm_priotracker *tracker, 459 const char *file, int line) 460 { 461 462 463 WITNESS_CHECKORDER(&rm->lock_object, LOP_NEWORDER , file, line); 464 465 _rm_rlock(rm, tracker); 466 467 LOCK_LOG_LOCK("RMRLOCK", &rm->lock_object, 0, 0, file, line); 468 469 WITNESS_LOCK(&rm->lock_object, 0 , file, line); 470 471 curthread->td_locks++; 472 } 473 474 void 475 _rm_runlock_debug(struct rmlock *rm, struct rm_priotracker *tracker, 476 const char *file, int line) { 477 curthread->td_locks--; 478 WITNESS_UNLOCK(&rm->lock_object, 0 , file, line); 479 LOCK_LOG_LOCK("RMRUNLOCK", &rm->lock_object, 0, 0, file, line); 480 _rm_runlock(rm, tracker); 481 } 482 483 484 485 486 #else 487 /* 488 * Just strip out file and line arguments if no lock debugging is enabled 489 * in the kernel - we are called from a kernel module. 490 */ 491 492 493 void _rm_wlock_debug(struct rmlock *rm, const char *file, int line) 494 { 495 _rm_wlock(rm); 496 } 497 498 void _rm_wunlock_debug(struct rmlock *rm, const char *file, int line) 499 { 500 _rm_wunlock(rm); 501 } 502 503 void 504 _rm_rlock_debug(struct rmlock *rm, struct rm_priotracker *tracker, 505 const char *file, int line) 506 { 507 _rm_rlock(rm, tracker); 508 } 509 510 void 511 _rm_runlock_debug(struct rmlock *rm, struct rm_priotracker *tracker, 512 const char *file, int line) { 513 _rm_runlock(rm, tracker); 514 } 515 516 #endif 517