1 /* 2 * Copyright (c) 2003,2004,2009 The DragonFly Project. All rights reserved. 3 * 4 * This code is derived from software contributed to The DragonFly Project 5 * by Matthew Dillon <dillon@backplane.com> 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * 3. Neither the name of The DragonFly Project nor the names of its 18 * contributors may be used to endorse or promote products derived 19 * from this software without specific, prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 */ 34 35 /* 36 * lwkt_token - Implement soft token locks. 37 * 38 * Tokens are locks which serialize a thread only while the thread is 39 * running. If the thread blocks all tokens are released, then reacquired 40 * when the thread resumes. 41 * 42 * This implementation requires no critical sections or spin locks, but 43 * does use atomic_cmpset_ptr(). 44 * 45 * Tokens may be recursively acquired by the same thread. However the 46 * caller must be sure to release such tokens in reverse order. 47 */ 48 #include <sys/param.h> 49 #include <sys/systm.h> 50 #include <sys/kernel.h> 51 #include <sys/proc.h> 52 #include <sys/rtprio.h> 53 #include <sys/queue.h> 54 #include <sys/sysctl.h> 55 #include <sys/ktr.h> 56 #include <sys/kthread.h> 57 #include <machine/cpu.h> 58 #include <sys/lock.h> 59 #include <sys/spinlock.h> 60 61 #include <sys/thread2.h> 62 #include <sys/spinlock2.h> 63 #include <sys/mplock2.h> 64 65 #include <vm/vm.h> 66 #include <vm/vm_param.h> 67 #include <vm/vm_kern.h> 68 #include <vm/vm_object.h> 69 #include <vm/vm_page.h> 70 #include <vm/vm_map.h> 71 #include <vm/vm_pager.h> 72 #include <vm/vm_extern.h> 73 #include <vm/vm_zone.h> 74 75 #include <machine/stdarg.h> 76 #include <machine/smp.h> 77 78 #include "opt_ddb.h" 79 #ifdef DDB 80 #include <ddb/ddb.h> 81 #endif 82 83 extern int lwkt_sched_debug; 84 85 #ifndef LWKT_NUM_POOL_TOKENS 86 #define LWKT_NUM_POOL_TOKENS 4001 /* prime number */ 87 #endif 88 89 static lwkt_token pool_tokens[LWKT_NUM_POOL_TOKENS]; 90 struct spinlock tok_debug_spin = SPINLOCK_INITIALIZER(&tok_debug_spin, "tok_debug_spin"); 91 92 #define TOKEN_STRING "REF=%p TOK=%p TD=%p" 93 #define TOKEN_ARGS lwkt_tokref_t ref, lwkt_token_t tok, struct thread *td 94 #define CONTENDED_STRING TOKEN_STRING " (contention started)" 95 #define UNCONTENDED_STRING TOKEN_STRING " (contention stopped)" 96 #if !defined(KTR_TOKENS) 97 #define KTR_TOKENS KTR_ALL 98 #endif 99 100 KTR_INFO_MASTER(tokens); 101 KTR_INFO(KTR_TOKENS, tokens, fail, 0, TOKEN_STRING, TOKEN_ARGS); 102 KTR_INFO(KTR_TOKENS, tokens, succ, 1, TOKEN_STRING, TOKEN_ARGS); 103 #if 0 104 KTR_INFO(KTR_TOKENS, tokens, release, 2, TOKEN_STRING, TOKEN_ARGS); 105 KTR_INFO(KTR_TOKENS, tokens, remote, 3, TOKEN_STRING, TOKEN_ARGS); 106 KTR_INFO(KTR_TOKENS, tokens, reqremote, 4, TOKEN_STRING, TOKEN_ARGS); 107 KTR_INFO(KTR_TOKENS, tokens, reqfail, 5, TOKEN_STRING, TOKEN_ARGS); 108 KTR_INFO(KTR_TOKENS, tokens, drain, 6, TOKEN_STRING, TOKEN_ARGS); 109 KTR_INFO(KTR_TOKENS, tokens, contention_start, 7, CONTENDED_STRING, TOKEN_ARGS); 110 KTR_INFO(KTR_TOKENS, tokens, contention_stop, 7, UNCONTENDED_STRING, TOKEN_ARGS); 111 #endif 112 113 #define logtoken(name, ref) \ 114 KTR_LOG(tokens_ ## name, ref, ref->tr_tok, curthread) 115 116 /* 117 * Global tokens. These replace the MP lock for major subsystem locking. 118 * These tokens are initially used to lockup both global and individual 119 * operations. 120 * 121 * Once individual structures get their own locks these tokens are used 122 * only to protect global lists & other variables and to interlock 123 * allocations and teardowns and such. 124 * 125 * The UP initializer causes token acquisition to also acquire the MP lock 126 * for maximum compatibility. The feature may be enabled and disabled at 127 * any time, the MP state is copied to the tokref when the token is acquired 128 * and will not race against sysctl changes. 129 */ 130 struct lwkt_token mp_token = LWKT_TOKEN_INITIALIZER(mp_token); 131 struct lwkt_token pmap_token = LWKT_TOKEN_INITIALIZER(pmap_token); 132 struct lwkt_token dev_token = LWKT_TOKEN_INITIALIZER(dev_token); 133 struct lwkt_token vm_token = LWKT_TOKEN_INITIALIZER(vm_token); 134 struct lwkt_token vmspace_token = LWKT_TOKEN_INITIALIZER(vmspace_token); 135 struct lwkt_token kvm_token = LWKT_TOKEN_INITIALIZER(kvm_token); 136 struct lwkt_token sigio_token = LWKT_TOKEN_INITIALIZER(sigio_token); 137 struct lwkt_token tty_token = LWKT_TOKEN_INITIALIZER(tty_token); 138 struct lwkt_token vnode_token = LWKT_TOKEN_INITIALIZER(vnode_token); 139 140 static int lwkt_token_spin = 5; 141 SYSCTL_INT(_lwkt, OID_AUTO, token_spin, CTLFLAG_RW, 142 &lwkt_token_spin, 0, "Decontention spin loops"); 143 static int lwkt_token_delay = 0; 144 SYSCTL_INT(_lwkt, OID_AUTO, token_delay, CTLFLAG_RW, 145 &lwkt_token_delay, 0, "Decontention spin delay in ns"); 146 147 /* 148 * The collision count is bumped every time the LWKT scheduler fails 149 * to acquire needed tokens in addition to a normal lwkt_gettoken() 150 * stall. 151 */ 152 SYSCTL_LONG(_lwkt, OID_AUTO, mp_collisions, CTLFLAG_RW, 153 &mp_token.t_collisions, 0, "Collision counter of mp_token"); 154 SYSCTL_LONG(_lwkt, OID_AUTO, pmap_collisions, CTLFLAG_RW, 155 &pmap_token.t_collisions, 0, "Collision counter of pmap_token"); 156 SYSCTL_LONG(_lwkt, OID_AUTO, dev_collisions, CTLFLAG_RW, 157 &dev_token.t_collisions, 0, "Collision counter of dev_token"); 158 SYSCTL_LONG(_lwkt, OID_AUTO, vm_collisions, CTLFLAG_RW, 159 &vm_token.t_collisions, 0, "Collision counter of vm_token"); 160 SYSCTL_LONG(_lwkt, OID_AUTO, vmspace_collisions, CTLFLAG_RW, 161 &vmspace_token.t_collisions, 0, "Collision counter of vmspace_token"); 162 SYSCTL_LONG(_lwkt, OID_AUTO, kvm_collisions, CTLFLAG_RW, 163 &kvm_token.t_collisions, 0, "Collision counter of kvm_token"); 164 SYSCTL_LONG(_lwkt, OID_AUTO, sigio_collisions, CTLFLAG_RW, 165 &sigio_token.t_collisions, 0, "Collision counter of sigio_token"); 166 SYSCTL_LONG(_lwkt, OID_AUTO, tty_collisions, CTLFLAG_RW, 167 &tty_token.t_collisions, 0, "Collision counter of tty_token"); 168 SYSCTL_LONG(_lwkt, OID_AUTO, vnode_collisions, CTLFLAG_RW, 169 &vnode_token.t_collisions, 0, "Collision counter of vnode_token"); 170 171 int tokens_debug_output; 172 SYSCTL_INT(_lwkt, OID_AUTO, tokens_debug_output, CTLFLAG_RW, 173 &tokens_debug_output, 0, "Generate stack trace N times"); 174 175 176 #ifdef DEBUG_LOCKS_LATENCY 177 178 static long tokens_add_latency; 179 SYSCTL_LONG(_debug, OID_AUTO, tokens_add_latency, CTLFLAG_RW, 180 &tokens_add_latency, 0, 181 "Add spinlock latency"); 182 183 #endif 184 185 186 static int _lwkt_getalltokens_sorted(thread_t td); 187 188 /* 189 * Acquire the initial mplock 190 * 191 * (low level boot only) 192 */ 193 void 194 cpu_get_initial_mplock(void) 195 { 196 KKASSERT(mp_token.t_ref == NULL); 197 if (lwkt_trytoken(&mp_token) == FALSE) 198 panic("cpu_get_initial_mplock"); 199 } 200 201 /* 202 * Return a pool token given an address. Use a prime number to reduce 203 * overlaps. 204 */ 205 static __inline 206 lwkt_token_t 207 _lwkt_token_pool_lookup(void *ptr) 208 { 209 u_int i; 210 211 i = (u_int)(uintptr_t)ptr % LWKT_NUM_POOL_TOKENS; 212 return(&pool_tokens[i]); 213 } 214 215 /* 216 * Initialize a tokref_t prior to making it visible in the thread's 217 * token array. 218 */ 219 static __inline 220 void 221 _lwkt_tokref_init(lwkt_tokref_t ref, lwkt_token_t tok, thread_t td, long excl) 222 { 223 ref->tr_tok = tok; 224 ref->tr_count = excl; 225 ref->tr_owner = td; 226 } 227 228 /* 229 * Attempt to acquire a shared or exclusive token. Returns TRUE on success, 230 * FALSE on failure. 231 * 232 * If TOK_EXCLUSIVE is set in mode we are attempting to get an exclusive 233 * token, otherwise are attempting to get a shared token. 234 * 235 * If TOK_EXCLREQ is set in mode this is a blocking operation, otherwise 236 * it is a non-blocking operation (for both exclusive or shared acquisions). 237 */ 238 static __inline 239 int 240 _lwkt_trytokref(lwkt_tokref_t ref, thread_t td, long mode) 241 { 242 lwkt_token_t tok; 243 lwkt_tokref_t oref; 244 long count; 245 246 tok = ref->tr_tok; 247 KASSERT(((mode & TOK_EXCLREQ) == 0 || /* non blocking */ 248 td->td_gd->gd_intr_nesting_level == 0 || 249 panic_cpu_gd == mycpu), 250 ("Attempt to acquire token %p not already " 251 "held in hard code section", tok)); 252 253 if (mode & TOK_EXCLUSIVE) { 254 /* 255 * Attempt to get an exclusive token 256 */ 257 for (;;) { 258 count = tok->t_count; 259 oref = tok->t_ref; /* can be NULL */ 260 cpu_ccfence(); 261 if ((count & ~TOK_EXCLREQ) == 0) { 262 /* 263 * It is possible to get the exclusive bit. 264 * We must clear TOK_EXCLREQ on successful 265 * acquisition. 266 */ 267 if (atomic_cmpset_long(&tok->t_count, count, 268 (count & ~TOK_EXCLREQ) | 269 TOK_EXCLUSIVE)) { 270 KKASSERT(tok->t_ref == NULL); 271 tok->t_ref = ref; 272 return TRUE; 273 } 274 /* retry */ 275 } else if ((count & TOK_EXCLUSIVE) && 276 oref >= &td->td_toks_base && 277 oref < td->td_toks_stop) { 278 /* 279 * Our thread already holds the exclusive 280 * bit, we treat this tokref as a shared 281 * token (sorta) to make the token release 282 * code easier. 283 * 284 * NOTE: oref cannot race above if it 285 * happens to be ours, so we're good. 286 * But we must still have a stable 287 * variable for both parts of the 288 * comparison. 289 * 290 * NOTE: Since we already have an exclusive 291 * lock and don't need to check EXCLREQ 292 * we can just use an atomic_add here 293 */ 294 atomic_add_long(&tok->t_count, TOK_INCR); 295 ref->tr_count &= ~TOK_EXCLUSIVE; 296 return TRUE; 297 } else if ((mode & TOK_EXCLREQ) && 298 (count & TOK_EXCLREQ) == 0) { 299 /* 300 * Unable to get the exclusive bit but being 301 * asked to set the exclusive-request bit. 302 * Since we are going to retry anyway just 303 * set the bit unconditionally. 304 */ 305 atomic_set_long(&tok->t_count, TOK_EXCLREQ); 306 return FALSE; 307 } else { 308 /* 309 * Unable to get the exclusive bit and not 310 * being asked to set the exclusive-request 311 * (aka lwkt_trytoken()), or EXCLREQ was 312 * already set. 313 */ 314 cpu_pause(); 315 return FALSE; 316 } 317 /* retry */ 318 } 319 } else { 320 /* 321 * Attempt to get a shared token. Note that TOK_EXCLREQ 322 * for shared tokens simply means the caller intends to 323 * block. We never actually set the bit in tok->t_count. 324 */ 325 for (;;) { 326 count = tok->t_count; 327 oref = tok->t_ref; /* can be NULL */ 328 cpu_ccfence(); 329 if ((count & (TOK_EXCLUSIVE/*|TOK_EXCLREQ*/)) == 0) { 330 /* XXX EXCLREQ should work */ 331 /* 332 * It is possible to get the token shared. 333 */ 334 if (atomic_cmpset_long(&tok->t_count, count, 335 count + TOK_INCR)) { 336 return TRUE; 337 } 338 /* retry */ 339 } else if ((count & TOK_EXCLUSIVE) && 340 oref >= &td->td_toks_base && 341 oref < td->td_toks_stop) { 342 /* 343 * We own the exclusive bit on the token so 344 * we can in fact also get it shared. 345 */ 346 atomic_add_long(&tok->t_count, TOK_INCR); 347 return TRUE; 348 } else { 349 /* 350 * We failed to get the token shared 351 */ 352 return FALSE; 353 } 354 /* retry */ 355 } 356 } 357 } 358 359 static __inline 360 int 361 _lwkt_trytokref_spin(lwkt_tokref_t ref, thread_t td, long mode) 362 { 363 int spin; 364 365 if (_lwkt_trytokref(ref, td, mode)) { 366 #ifdef DEBUG_LOCKS_LATENCY 367 long j; 368 for (j = tokens_add_latency; j > 0; --j) 369 cpu_ccfence(); 370 #endif 371 return TRUE; 372 } 373 for (spin = lwkt_token_spin; spin > 0; --spin) { 374 if (lwkt_token_delay) 375 tsc_delay(lwkt_token_delay); 376 else 377 cpu_pause(); 378 if (_lwkt_trytokref(ref, td, mode)) { 379 #ifdef DEBUG_LOCKS_LATENCY 380 long j; 381 for (j = tokens_add_latency; j > 0; --j) 382 cpu_ccfence(); 383 #endif 384 return TRUE; 385 } 386 } 387 return FALSE; 388 } 389 390 /* 391 * Release a token that we hold. 392 */ 393 static __inline 394 void 395 _lwkt_reltokref(lwkt_tokref_t ref, thread_t td) 396 { 397 lwkt_token_t tok; 398 long count; 399 400 tok = ref->tr_tok; 401 for (;;) { 402 count = tok->t_count; 403 cpu_ccfence(); 404 if (tok->t_ref == ref) { 405 /* 406 * We are an exclusive holder. We must clear tr_ref 407 * before we clear the TOK_EXCLUSIVE bit. If we are 408 * unable to clear the bit we must restore 409 * tok->t_ref. 410 */ 411 KKASSERT(count & TOK_EXCLUSIVE); 412 tok->t_ref = NULL; 413 if (atomic_cmpset_long(&tok->t_count, count, 414 count & ~TOK_EXCLUSIVE)) { 415 return; 416 } 417 tok->t_ref = ref; 418 /* retry */ 419 } else { 420 /* 421 * We are a shared holder 422 */ 423 KKASSERT(count & TOK_COUNTMASK); 424 if (atomic_cmpset_long(&tok->t_count, count, 425 count - TOK_INCR)) { 426 return; 427 } 428 /* retry */ 429 } 430 /* retry */ 431 } 432 } 433 434 /* 435 * Obtain all the tokens required by the specified thread on the current 436 * cpu, return 0 on failure and non-zero on success. If a failure occurs 437 * any partially acquired tokens will be released prior to return. 438 * 439 * lwkt_getalltokens is called by the LWKT scheduler to re-acquire all 440 * tokens that the thread had to release when it switched away. 441 * 442 * If spinning is non-zero this function acquires the tokens in a particular 443 * order to deal with potential deadlocks. We simply use address order for 444 * the case. 445 * 446 * Called from a critical section. 447 */ 448 int 449 lwkt_getalltokens(thread_t td, int spinning) 450 { 451 lwkt_tokref_t scan; 452 lwkt_token_t tok; 453 454 if (spinning) 455 return(_lwkt_getalltokens_sorted(td)); 456 457 /* 458 * Acquire tokens in forward order, assign or validate tok->t_ref. 459 */ 460 for (scan = &td->td_toks_base; scan < td->td_toks_stop; ++scan) { 461 tok = scan->tr_tok; 462 for (;;) { 463 /* 464 * Only try really hard on the last token 465 */ 466 if (scan == td->td_toks_stop - 1) { 467 if (_lwkt_trytokref_spin(scan, td, scan->tr_count)) 468 break; 469 } else { 470 if (_lwkt_trytokref(scan, td, scan->tr_count)) 471 break; 472 } 473 474 /* 475 * Otherwise we failed to acquire all the tokens. 476 * Release whatever we did get. 477 */ 478 KASSERT(tok->t_desc, 479 ("token %p is not initialized", tok)); 480 strncpy(td->td_gd->gd_cnt.v_lock_name, 481 tok->t_desc, 482 sizeof(td->td_gd->gd_cnt.v_lock_name) - 1); 483 484 if (lwkt_sched_debug > 0) { 485 --lwkt_sched_debug; 486 kprintf("toka %p %s %s\n", 487 tok, tok->t_desc, td->td_comm); 488 } 489 td->td_wmesg = tok->t_desc; 490 ++tok->t_collisions; 491 while (--scan >= &td->td_toks_base) 492 _lwkt_reltokref(scan, td); 493 return(FALSE); 494 } 495 } 496 return (TRUE); 497 } 498 499 /* 500 * Release all tokens owned by the specified thread on the current cpu. 501 * 502 * This code is really simple. Even in cases where we own all the tokens 503 * note that t_ref may not match the scan for recursively held tokens which 504 * are held deeper in the stack, or for the case where a lwkt_getalltokens() 505 * failed. 506 * 507 * Tokens are released in reverse order to reduce chasing race failures. 508 * 509 * Called from a critical section. 510 */ 511 void 512 lwkt_relalltokens(thread_t td) 513 { 514 lwkt_tokref_t scan; 515 516 /* 517 * Weird order is to try to avoid a panic loop 518 */ 519 if (td->td_toks_have) { 520 scan = td->td_toks_have; 521 td->td_toks_have = NULL; 522 } else { 523 scan = td->td_toks_stop; 524 } 525 while (--scan >= &td->td_toks_base) 526 _lwkt_reltokref(scan, td); 527 } 528 529 /* 530 * This is the decontention version of lwkt_getalltokens(). The tokens are 531 * acquired in address-sorted order to deal with any deadlocks. Ultimately 532 * token failures will spin into the scheduler and get here. 533 * 534 * Called from critical section 535 */ 536 static 537 int 538 _lwkt_getalltokens_sorted(thread_t td) 539 { 540 lwkt_tokref_t sort_array[LWKT_MAXTOKENS]; 541 lwkt_tokref_t scan; 542 lwkt_token_t tok; 543 int i; 544 int j; 545 int n; 546 547 /* 548 * Sort the token array. Yah yah, I know this isn't fun. 549 * 550 * NOTE: Recursively acquired tokens are ordered the same as in the 551 * td_toks_array so we can always get the earliest one first. 552 */ 553 i = 0; 554 scan = &td->td_toks_base; 555 while (scan < td->td_toks_stop) { 556 for (j = 0; j < i; ++j) { 557 if (scan->tr_tok < sort_array[j]->tr_tok) 558 break; 559 } 560 if (j != i) { 561 bcopy(sort_array + j, sort_array + j + 1, 562 (i - j) * sizeof(lwkt_tokref_t)); 563 } 564 sort_array[j] = scan; 565 ++scan; 566 ++i; 567 } 568 n = i; 569 570 /* 571 * Acquire tokens in forward order, assign or validate tok->t_ref. 572 */ 573 for (i = 0; i < n; ++i) { 574 scan = sort_array[i]; 575 tok = scan->tr_tok; 576 for (;;) { 577 /* 578 * Only try really hard on the last token 579 */ 580 if (scan == td->td_toks_stop - 1) { 581 if (_lwkt_trytokref_spin(scan, td, scan->tr_count)) 582 break; 583 } else { 584 if (_lwkt_trytokref(scan, td, scan->tr_count)) 585 break; 586 } 587 588 /* 589 * Otherwise we failed to acquire all the tokens. 590 * Release whatever we did get. 591 */ 592 if (lwkt_sched_debug > 0) { 593 --lwkt_sched_debug; 594 kprintf("tokb %p %s %s\n", 595 tok, tok->t_desc, td->td_comm); 596 } 597 td->td_wmesg = tok->t_desc; 598 ++tok->t_collisions; 599 while (--i >= 0) { 600 scan = sort_array[i]; 601 _lwkt_reltokref(scan, td); 602 } 603 return(FALSE); 604 } 605 } 606 607 /* 608 * We were successful, there is no need for another core to signal 609 * us. 610 */ 611 return (TRUE); 612 } 613 614 /* 615 * Get a serializing token. This routine can block. 616 */ 617 void 618 lwkt_gettoken(lwkt_token_t tok) 619 { 620 thread_t td = curthread; 621 lwkt_tokref_t ref; 622 623 ref = td->td_toks_stop; 624 KKASSERT(ref < &td->td_toks_end); 625 ++td->td_toks_stop; 626 cpu_ccfence(); 627 _lwkt_tokref_init(ref, tok, td, TOK_EXCLUSIVE|TOK_EXCLREQ); 628 629 #ifdef DEBUG_LOCKS 630 /* 631 * Taking an exclusive token after holding it shared will 632 * livelock. Scan for that case and assert. 633 */ 634 lwkt_tokref_t tk; 635 int found = 0; 636 for (tk = &td->td_toks_base; tk < ref; tk++) { 637 if (tk->tr_tok != tok) 638 continue; 639 640 found++; 641 if (tk->tr_count & TOK_EXCLUSIVE) 642 goto good; 643 } 644 /* We found only shared instances of this token if found >0 here */ 645 KASSERT((found == 0), ("Token %p s/x livelock", tok)); 646 good: 647 #endif 648 649 if (_lwkt_trytokref_spin(ref, td, TOK_EXCLUSIVE|TOK_EXCLREQ)) 650 return; 651 652 /* 653 * Give up running if we can't acquire the token right now. 654 * 655 * Since the tokref is already active the scheduler now 656 * takes care of acquisition, so we need only call 657 * lwkt_switch(). 658 * 659 * Since we failed this was not a recursive token so upon 660 * return tr_tok->t_ref should be assigned to this specific 661 * ref. 662 */ 663 td->td_wmesg = tok->t_desc; 664 ++tok->t_collisions; 665 logtoken(fail, ref); 666 td->td_toks_have = td->td_toks_stop - 1; 667 668 if (tokens_debug_output > 0) { 669 --tokens_debug_output; 670 spin_lock(&tok_debug_spin); 671 kprintf("Excl Token thread %p %s %s\n", 672 td, tok->t_desc, td->td_comm); 673 print_backtrace(6); 674 kprintf("\n"); 675 spin_unlock(&tok_debug_spin); 676 } 677 678 lwkt_switch(); 679 logtoken(succ, ref); 680 KKASSERT(tok->t_ref == ref); 681 } 682 683 /* 684 * Similar to gettoken but we acquire a shared token instead of an exclusive 685 * token. 686 */ 687 void 688 lwkt_gettoken_shared(lwkt_token_t tok) 689 { 690 thread_t td = curthread; 691 lwkt_tokref_t ref; 692 693 ref = td->td_toks_stop; 694 KKASSERT(ref < &td->td_toks_end); 695 ++td->td_toks_stop; 696 cpu_ccfence(); 697 _lwkt_tokref_init(ref, tok, td, TOK_EXCLREQ); 698 699 #ifdef DEBUG_LOCKS 700 /* 701 * Taking a pool token in shared mode is a bad idea; other 702 * addresses deeper in the call stack may hash to the same pool 703 * token and you may end up with an exclusive-shared livelock. 704 * Warn in this condition. 705 */ 706 if ((tok >= &pool_tokens[0]) && 707 (tok < &pool_tokens[LWKT_NUM_POOL_TOKENS])) 708 kprintf("Warning! Taking pool token %p in shared mode\n", tok); 709 #endif 710 711 712 if (_lwkt_trytokref_spin(ref, td, TOK_EXCLREQ)) 713 return; 714 715 /* 716 * Give up running if we can't acquire the token right now. 717 * 718 * Since the tokref is already active the scheduler now 719 * takes care of acquisition, so we need only call 720 * lwkt_switch(). 721 * 722 * Since we failed this was not a recursive token so upon 723 * return tr_tok->t_ref should be assigned to this specific 724 * ref. 725 */ 726 td->td_wmesg = tok->t_desc; 727 ++tok->t_collisions; 728 logtoken(fail, ref); 729 td->td_toks_have = td->td_toks_stop - 1; 730 731 if (tokens_debug_output > 0) { 732 --tokens_debug_output; 733 spin_lock(&tok_debug_spin); 734 kprintf("Shar Token thread %p %s %s\n", 735 td, tok->t_desc, td->td_comm); 736 print_backtrace(6); 737 kprintf("\n"); 738 spin_unlock(&tok_debug_spin); 739 } 740 741 lwkt_switch(); 742 logtoken(succ, ref); 743 } 744 745 /* 746 * Attempt to acquire a token, return TRUE on success, FALSE on failure. 747 * 748 * We setup the tokref in case we actually get the token (if we switch later 749 * it becomes mandatory so we set TOK_EXCLREQ), but we call trytokref without 750 * TOK_EXCLREQ in case we fail. 751 */ 752 int 753 lwkt_trytoken(lwkt_token_t tok) 754 { 755 thread_t td = curthread; 756 lwkt_tokref_t ref; 757 758 ref = td->td_toks_stop; 759 KKASSERT(ref < &td->td_toks_end); 760 ++td->td_toks_stop; 761 cpu_ccfence(); 762 _lwkt_tokref_init(ref, tok, td, TOK_EXCLUSIVE|TOK_EXCLREQ); 763 764 if (_lwkt_trytokref(ref, td, TOK_EXCLUSIVE)) 765 return TRUE; 766 767 /* 768 * Failed, unpend the request 769 */ 770 cpu_ccfence(); 771 --td->td_toks_stop; 772 ++tok->t_collisions; 773 return FALSE; 774 } 775 776 777 void 778 lwkt_gettoken_hard(lwkt_token_t tok) 779 { 780 lwkt_gettoken(tok); 781 crit_enter_hard(); 782 } 783 784 lwkt_token_t 785 lwkt_getpooltoken(void *ptr) 786 { 787 lwkt_token_t tok; 788 789 tok = _lwkt_token_pool_lookup(ptr); 790 lwkt_gettoken(tok); 791 return (tok); 792 } 793 794 /* 795 * Release a serializing token. 796 * 797 * WARNING! All tokens must be released in reverse order. This will be 798 * asserted. 799 */ 800 void 801 lwkt_reltoken(lwkt_token_t tok) 802 { 803 thread_t td = curthread; 804 lwkt_tokref_t ref; 805 806 /* 807 * Remove ref from thread token list and assert that it matches 808 * the token passed in. Tokens must be released in reverse order. 809 */ 810 ref = td->td_toks_stop - 1; 811 KKASSERT(ref >= &td->td_toks_base && ref->tr_tok == tok); 812 _lwkt_reltokref(ref, td); 813 cpu_sfence(); 814 td->td_toks_stop = ref; 815 } 816 817 void 818 lwkt_reltoken_hard(lwkt_token_t tok) 819 { 820 lwkt_reltoken(tok); 821 crit_exit_hard(); 822 } 823 824 /* 825 * It is faster for users of lwkt_getpooltoken() to use the returned 826 * token and just call lwkt_reltoken(), but for convenience we provide 827 * this function which looks the token up based on the ident. 828 */ 829 void 830 lwkt_relpooltoken(void *ptr) 831 { 832 lwkt_token_t tok = _lwkt_token_pool_lookup(ptr); 833 lwkt_reltoken(tok); 834 } 835 836 /* 837 * Return a count of the number of token refs the thread has to the 838 * specified token, whether it currently owns the token or not. 839 */ 840 int 841 lwkt_cnttoken(lwkt_token_t tok, thread_t td) 842 { 843 lwkt_tokref_t scan; 844 int count = 0; 845 846 for (scan = &td->td_toks_base; scan < td->td_toks_stop; ++scan) { 847 if (scan->tr_tok == tok) 848 ++count; 849 } 850 return(count); 851 } 852 853 /* 854 * Pool tokens are used to provide a type-stable serializing token 855 * pointer that does not race against disappearing data structures. 856 * 857 * This routine is called in early boot just after we setup the BSP's 858 * globaldata structure. 859 */ 860 void 861 lwkt_token_pool_init(void) 862 { 863 int i; 864 865 for (i = 0; i < LWKT_NUM_POOL_TOKENS; ++i) 866 lwkt_token_init(&pool_tokens[i], "pool"); 867 } 868 869 lwkt_token_t 870 lwkt_token_pool_lookup(void *ptr) 871 { 872 return (_lwkt_token_pool_lookup(ptr)); 873 } 874 875 /* 876 * Initialize a token. 877 */ 878 void 879 lwkt_token_init(lwkt_token_t tok, const char *desc) 880 { 881 tok->t_count = 0; 882 tok->t_ref = NULL; 883 tok->t_collisions = 0; 884 tok->t_desc = desc; 885 } 886 887 void 888 lwkt_token_uninit(lwkt_token_t tok) 889 { 890 /* empty */ 891 } 892 893 /* 894 * Exchange the two most recent tokens on the tokref stack. This allows 895 * you to release a token out of order. 896 * 897 * We have to be careful about the case where the top two tokens are 898 * the same token. In this case tok->t_ref will point to the deeper 899 * ref and must remain pointing to the deeper ref. If we were to swap 900 * it the first release would clear the token even though a second 901 * ref is still present. 902 * 903 * Only exclusively held tokens contain a reference to the tokref which 904 * has to be flipped along with the swap. 905 */ 906 void 907 lwkt_token_swap(void) 908 { 909 lwkt_tokref_t ref1, ref2; 910 lwkt_token_t tok1, tok2; 911 long count1, count2; 912 thread_t td = curthread; 913 914 crit_enter(); 915 916 ref1 = td->td_toks_stop - 1; 917 ref2 = td->td_toks_stop - 2; 918 KKASSERT(ref1 >= &td->td_toks_base); 919 KKASSERT(ref2 >= &td->td_toks_base); 920 921 tok1 = ref1->tr_tok; 922 tok2 = ref2->tr_tok; 923 count1 = ref1->tr_count; 924 count2 = ref2->tr_count; 925 926 if (tok1 != tok2) { 927 ref1->tr_tok = tok2; 928 ref1->tr_count = count2; 929 ref2->tr_tok = tok1; 930 ref2->tr_count = count1; 931 if (tok1->t_ref == ref1) 932 tok1->t_ref = ref2; 933 if (tok2->t_ref == ref2) 934 tok2->t_ref = ref1; 935 } 936 937 crit_exit(); 938 } 939 940 #ifdef DDB 941 DB_SHOW_COMMAND(tokens, db_tok_all) 942 { 943 struct lwkt_token *tok, **ptr; 944 struct lwkt_token *toklist[16] = { 945 &mp_token, 946 &pmap_token, 947 &dev_token, 948 &vm_token, 949 &vmspace_token, 950 &kvm_token, 951 &sigio_token, 952 &tty_token, 953 &vnode_token, 954 NULL 955 }; 956 957 ptr = toklist; 958 for (tok = *ptr; tok; tok = *(++ptr)) { 959 db_printf("tok=%p tr_owner=%p t_colissions=%ld t_desc=%s\n", tok, 960 (tok->t_ref ? tok->t_ref->tr_owner : NULL), 961 tok->t_collisions, tok->t_desc); 962 } 963 } 964 #endif /* DDB */ 965