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 struct lwkt_token ifnet_token = LWKT_TOKEN_INITIALIZER(ifnet_token); 140 141 static int lwkt_token_spin = 5; 142 SYSCTL_INT(_lwkt, OID_AUTO, token_spin, CTLFLAG_RW, 143 &lwkt_token_spin, 0, "Decontention spin loops"); 144 static int lwkt_token_delay = 0; 145 SYSCTL_INT(_lwkt, OID_AUTO, token_delay, CTLFLAG_RW, 146 &lwkt_token_delay, 0, "Decontention spin delay in ns"); 147 148 /* 149 * The collision count is bumped every time the LWKT scheduler fails 150 * to acquire needed tokens in addition to a normal lwkt_gettoken() 151 * stall. 152 */ 153 SYSCTL_LONG(_lwkt, OID_AUTO, mp_collisions, CTLFLAG_RW, 154 &mp_token.t_collisions, 0, "Collision counter of mp_token"); 155 SYSCTL_LONG(_lwkt, OID_AUTO, pmap_collisions, CTLFLAG_RW, 156 &pmap_token.t_collisions, 0, "Collision counter of pmap_token"); 157 SYSCTL_LONG(_lwkt, OID_AUTO, dev_collisions, CTLFLAG_RW, 158 &dev_token.t_collisions, 0, "Collision counter of dev_token"); 159 SYSCTL_LONG(_lwkt, OID_AUTO, vm_collisions, CTLFLAG_RW, 160 &vm_token.t_collisions, 0, "Collision counter of vm_token"); 161 SYSCTL_LONG(_lwkt, OID_AUTO, vmspace_collisions, CTLFLAG_RW, 162 &vmspace_token.t_collisions, 0, "Collision counter of vmspace_token"); 163 SYSCTL_LONG(_lwkt, OID_AUTO, kvm_collisions, CTLFLAG_RW, 164 &kvm_token.t_collisions, 0, "Collision counter of kvm_token"); 165 SYSCTL_LONG(_lwkt, OID_AUTO, sigio_collisions, CTLFLAG_RW, 166 &sigio_token.t_collisions, 0, "Collision counter of sigio_token"); 167 SYSCTL_LONG(_lwkt, OID_AUTO, tty_collisions, CTLFLAG_RW, 168 &tty_token.t_collisions, 0, "Collision counter of tty_token"); 169 SYSCTL_LONG(_lwkt, OID_AUTO, vnode_collisions, CTLFLAG_RW, 170 &vnode_token.t_collisions, 0, "Collision counter of vnode_token"); 171 172 int tokens_debug_output; 173 SYSCTL_INT(_lwkt, OID_AUTO, tokens_debug_output, CTLFLAG_RW, 174 &tokens_debug_output, 0, "Generate stack trace N times"); 175 176 177 #ifdef DEBUG_LOCKS_LATENCY 178 179 static long tokens_add_latency; 180 SYSCTL_LONG(_debug, OID_AUTO, tokens_add_latency, CTLFLAG_RW, 181 &tokens_add_latency, 0, 182 "Add spinlock latency"); 183 184 #endif 185 186 187 static int _lwkt_getalltokens_sorted(thread_t td); 188 189 /* 190 * Acquire the initial mplock 191 * 192 * (low level boot only) 193 */ 194 void 195 cpu_get_initial_mplock(void) 196 { 197 KKASSERT(mp_token.t_ref == NULL); 198 if (lwkt_trytoken(&mp_token) == FALSE) 199 panic("cpu_get_initial_mplock"); 200 } 201 202 /* 203 * Return a pool token given an address. Use a prime number to reduce 204 * overlaps. 205 */ 206 static __inline 207 lwkt_token_t 208 _lwkt_token_pool_lookup(void *ptr) 209 { 210 u_int i; 211 212 i = (u_int)(uintptr_t)ptr % LWKT_NUM_POOL_TOKENS; 213 return(&pool_tokens[i]); 214 } 215 216 /* 217 * Initialize a tokref_t prior to making it visible in the thread's 218 * token array. 219 */ 220 static __inline 221 void 222 _lwkt_tokref_init(lwkt_tokref_t ref, lwkt_token_t tok, thread_t td, long excl) 223 { 224 ref->tr_tok = tok; 225 ref->tr_count = excl; 226 ref->tr_owner = td; 227 } 228 229 /* 230 * Attempt to acquire a shared or exclusive token. Returns TRUE on success, 231 * FALSE on failure. 232 * 233 * If TOK_EXCLUSIVE is set in mode we are attempting to get an exclusive 234 * token, otherwise are attempting to get a shared token. 235 * 236 * If TOK_EXCLREQ is set in mode this is a blocking operation, otherwise 237 * it is a non-blocking operation (for both exclusive or shared acquisions). 238 */ 239 static __inline 240 int 241 _lwkt_trytokref(lwkt_tokref_t ref, thread_t td, long mode) 242 { 243 lwkt_token_t tok; 244 lwkt_tokref_t oref; 245 long count; 246 247 tok = ref->tr_tok; 248 KASSERT(((mode & TOK_EXCLREQ) == 0 || /* non blocking */ 249 td->td_gd->gd_intr_nesting_level == 0 || 250 panic_cpu_gd == mycpu), 251 ("Attempt to acquire token %p not already " 252 "held in hard code section", tok)); 253 254 if (mode & TOK_EXCLUSIVE) { 255 /* 256 * Attempt to get an exclusive token 257 */ 258 for (;;) { 259 count = tok->t_count; 260 oref = tok->t_ref; /* can be NULL */ 261 cpu_ccfence(); 262 if ((count & ~TOK_EXCLREQ) == 0) { 263 /* 264 * It is possible to get the exclusive bit. 265 * We must clear TOK_EXCLREQ on successful 266 * acquisition. 267 */ 268 if (atomic_cmpset_long(&tok->t_count, count, 269 (count & ~TOK_EXCLREQ) | 270 TOK_EXCLUSIVE)) { 271 KKASSERT(tok->t_ref == NULL); 272 tok->t_ref = ref; 273 return TRUE; 274 } 275 /* retry */ 276 } else if ((count & TOK_EXCLUSIVE) && 277 oref >= &td->td_toks_base && 278 oref < td->td_toks_stop) { 279 /* 280 * Our thread already holds the exclusive 281 * bit, we treat this tokref as a shared 282 * token (sorta) to make the token release 283 * code easier. 284 * 285 * NOTE: oref cannot race above if it 286 * happens to be ours, so we're good. 287 * But we must still have a stable 288 * variable for both parts of the 289 * comparison. 290 * 291 * NOTE: Since we already have an exclusive 292 * lock and don't need to check EXCLREQ 293 * we can just use an atomic_add here 294 */ 295 atomic_add_long(&tok->t_count, TOK_INCR); 296 ref->tr_count &= ~TOK_EXCLUSIVE; 297 return TRUE; 298 } else if ((mode & TOK_EXCLREQ) && 299 (count & TOK_EXCLREQ) == 0) { 300 /* 301 * Unable to get the exclusive bit but being 302 * asked to set the exclusive-request bit. 303 * Since we are going to retry anyway just 304 * set the bit unconditionally. 305 */ 306 atomic_set_long(&tok->t_count, TOK_EXCLREQ); 307 return FALSE; 308 } else { 309 /* 310 * Unable to get the exclusive bit and not 311 * being asked to set the exclusive-request 312 * (aka lwkt_trytoken()), or EXCLREQ was 313 * already set. 314 */ 315 cpu_pause(); 316 return FALSE; 317 } 318 /* retry */ 319 } 320 } else { 321 /* 322 * Attempt to get a shared token. Note that TOK_EXCLREQ 323 * for shared tokens simply means the caller intends to 324 * block. We never actually set the bit in tok->t_count. 325 */ 326 for (;;) { 327 count = tok->t_count; 328 oref = tok->t_ref; /* can be NULL */ 329 cpu_ccfence(); 330 if ((count & (TOK_EXCLUSIVE/*|TOK_EXCLREQ*/)) == 0) { 331 /* XXX EXCLREQ should work */ 332 /* 333 * It is possible to get the token shared. 334 */ 335 if (atomic_cmpset_long(&tok->t_count, count, 336 count + TOK_INCR)) { 337 return TRUE; 338 } 339 /* retry */ 340 } else if ((count & TOK_EXCLUSIVE) && 341 oref >= &td->td_toks_base && 342 oref < td->td_toks_stop) { 343 /* 344 * We own the exclusive bit on the token so 345 * we can in fact also get it shared. 346 */ 347 atomic_add_long(&tok->t_count, TOK_INCR); 348 return TRUE; 349 } else { 350 /* 351 * We failed to get the token shared 352 */ 353 return FALSE; 354 } 355 /* retry */ 356 } 357 } 358 } 359 360 static __inline 361 int 362 _lwkt_trytokref_spin(lwkt_tokref_t ref, thread_t td, long mode) 363 { 364 int spin; 365 366 if (_lwkt_trytokref(ref, td, mode)) { 367 #ifdef DEBUG_LOCKS_LATENCY 368 long j; 369 for (j = tokens_add_latency; j > 0; --j) 370 cpu_ccfence(); 371 #endif 372 return TRUE; 373 } 374 for (spin = lwkt_token_spin; spin > 0; --spin) { 375 if (lwkt_token_delay) 376 tsc_delay(lwkt_token_delay); 377 else 378 cpu_pause(); 379 if (_lwkt_trytokref(ref, td, mode)) { 380 #ifdef DEBUG_LOCKS_LATENCY 381 long j; 382 for (j = tokens_add_latency; j > 0; --j) 383 cpu_ccfence(); 384 #endif 385 return TRUE; 386 } 387 } 388 return FALSE; 389 } 390 391 /* 392 * Release a token that we hold. 393 */ 394 static __inline 395 void 396 _lwkt_reltokref(lwkt_tokref_t ref, thread_t td) 397 { 398 lwkt_token_t tok; 399 long count; 400 401 tok = ref->tr_tok; 402 for (;;) { 403 count = tok->t_count; 404 cpu_ccfence(); 405 if (tok->t_ref == ref) { 406 /* 407 * We are an exclusive holder. We must clear tr_ref 408 * before we clear the TOK_EXCLUSIVE bit. If we are 409 * unable to clear the bit we must restore 410 * tok->t_ref. 411 */ 412 KKASSERT(count & TOK_EXCLUSIVE); 413 tok->t_ref = NULL; 414 if (atomic_cmpset_long(&tok->t_count, count, 415 count & ~TOK_EXCLUSIVE)) { 416 return; 417 } 418 tok->t_ref = ref; 419 /* retry */ 420 } else { 421 /* 422 * We are a shared holder 423 */ 424 KKASSERT(count & TOK_COUNTMASK); 425 if (atomic_cmpset_long(&tok->t_count, count, 426 count - TOK_INCR)) { 427 return; 428 } 429 /* retry */ 430 } 431 /* retry */ 432 } 433 } 434 435 /* 436 * Obtain all the tokens required by the specified thread on the current 437 * cpu, return 0 on failure and non-zero on success. If a failure occurs 438 * any partially acquired tokens will be released prior to return. 439 * 440 * lwkt_getalltokens is called by the LWKT scheduler to re-acquire all 441 * tokens that the thread had to release when it switched away. 442 * 443 * If spinning is non-zero this function acquires the tokens in a particular 444 * order to deal with potential deadlocks. We simply use address order for 445 * the case. 446 * 447 * Called from a critical section. 448 */ 449 int 450 lwkt_getalltokens(thread_t td, int spinning) 451 { 452 lwkt_tokref_t scan; 453 lwkt_token_t tok; 454 455 if (spinning) 456 return(_lwkt_getalltokens_sorted(td)); 457 458 /* 459 * Acquire tokens in forward order, assign or validate tok->t_ref. 460 */ 461 for (scan = &td->td_toks_base; scan < td->td_toks_stop; ++scan) { 462 tok = scan->tr_tok; 463 for (;;) { 464 /* 465 * Only try really hard on the last token 466 */ 467 if (scan == td->td_toks_stop - 1) { 468 if (_lwkt_trytokref_spin(scan, td, scan->tr_count)) 469 break; 470 } else { 471 if (_lwkt_trytokref(scan, td, scan->tr_count)) 472 break; 473 } 474 475 /* 476 * Otherwise we failed to acquire all the tokens. 477 * Release whatever we did get. 478 */ 479 KASSERT(tok->t_desc, 480 ("token %p is not initialized", tok)); 481 strncpy(td->td_gd->gd_cnt.v_lock_name, 482 tok->t_desc, 483 sizeof(td->td_gd->gd_cnt.v_lock_name) - 1); 484 485 if (lwkt_sched_debug > 0) { 486 --lwkt_sched_debug; 487 kprintf("toka %p %s %s\n", 488 tok, tok->t_desc, td->td_comm); 489 } 490 td->td_wmesg = tok->t_desc; 491 ++tok->t_collisions; 492 while (--scan >= &td->td_toks_base) 493 _lwkt_reltokref(scan, td); 494 return(FALSE); 495 } 496 } 497 return (TRUE); 498 } 499 500 /* 501 * Release all tokens owned by the specified thread on the current cpu. 502 * 503 * This code is really simple. Even in cases where we own all the tokens 504 * note that t_ref may not match the scan for recursively held tokens which 505 * are held deeper in the stack, or for the case where a lwkt_getalltokens() 506 * failed. 507 * 508 * Tokens are released in reverse order to reduce chasing race failures. 509 * 510 * Called from a critical section. 511 */ 512 void 513 lwkt_relalltokens(thread_t td) 514 { 515 lwkt_tokref_t scan; 516 517 /* 518 * Weird order is to try to avoid a panic loop 519 */ 520 if (td->td_toks_have) { 521 scan = td->td_toks_have; 522 td->td_toks_have = NULL; 523 } else { 524 scan = td->td_toks_stop; 525 } 526 while (--scan >= &td->td_toks_base) 527 _lwkt_reltokref(scan, td); 528 } 529 530 /* 531 * This is the decontention version of lwkt_getalltokens(). The tokens are 532 * acquired in address-sorted order to deal with any deadlocks. Ultimately 533 * token failures will spin into the scheduler and get here. 534 * 535 * Called from critical section 536 */ 537 static 538 int 539 _lwkt_getalltokens_sorted(thread_t td) 540 { 541 lwkt_tokref_t sort_array[LWKT_MAXTOKENS]; 542 lwkt_tokref_t scan; 543 lwkt_token_t tok; 544 int i; 545 int j; 546 int n; 547 548 /* 549 * Sort the token array. Yah yah, I know this isn't fun. 550 * 551 * NOTE: Recursively acquired tokens are ordered the same as in the 552 * td_toks_array so we can always get the earliest one first. 553 */ 554 i = 0; 555 scan = &td->td_toks_base; 556 while (scan < td->td_toks_stop) { 557 for (j = 0; j < i; ++j) { 558 if (scan->tr_tok < sort_array[j]->tr_tok) 559 break; 560 } 561 if (j != i) { 562 bcopy(sort_array + j, sort_array + j + 1, 563 (i - j) * sizeof(lwkt_tokref_t)); 564 } 565 sort_array[j] = scan; 566 ++scan; 567 ++i; 568 } 569 n = i; 570 571 /* 572 * Acquire tokens in forward order, assign or validate tok->t_ref. 573 */ 574 for (i = 0; i < n; ++i) { 575 scan = sort_array[i]; 576 tok = scan->tr_tok; 577 for (;;) { 578 /* 579 * Only try really hard on the last token 580 */ 581 if (scan == td->td_toks_stop - 1) { 582 if (_lwkt_trytokref_spin(scan, td, scan->tr_count)) 583 break; 584 } else { 585 if (_lwkt_trytokref(scan, td, scan->tr_count)) 586 break; 587 } 588 589 /* 590 * Otherwise we failed to acquire all the tokens. 591 * Release whatever we did get. 592 */ 593 if (lwkt_sched_debug > 0) { 594 --lwkt_sched_debug; 595 kprintf("tokb %p %s %s\n", 596 tok, tok->t_desc, td->td_comm); 597 } 598 td->td_wmesg = tok->t_desc; 599 ++tok->t_collisions; 600 while (--i >= 0) { 601 scan = sort_array[i]; 602 _lwkt_reltokref(scan, td); 603 } 604 return(FALSE); 605 } 606 } 607 608 /* 609 * We were successful, there is no need for another core to signal 610 * us. 611 */ 612 return (TRUE); 613 } 614 615 /* 616 * Get a serializing token. This routine can block. 617 */ 618 void 619 lwkt_gettoken(lwkt_token_t tok) 620 { 621 thread_t td = curthread; 622 lwkt_tokref_t ref; 623 624 ref = td->td_toks_stop; 625 KKASSERT(ref < &td->td_toks_end); 626 ++td->td_toks_stop; 627 cpu_ccfence(); 628 _lwkt_tokref_init(ref, tok, td, TOK_EXCLUSIVE|TOK_EXCLREQ); 629 630 #ifdef DEBUG_LOCKS 631 /* 632 * Taking an exclusive token after holding it shared will 633 * livelock. Scan for that case and assert. 634 */ 635 lwkt_tokref_t tk; 636 int found = 0; 637 for (tk = &td->td_toks_base; tk < ref; tk++) { 638 if (tk->tr_tok != tok) 639 continue; 640 641 found++; 642 if (tk->tr_count & TOK_EXCLUSIVE) 643 goto good; 644 } 645 /* We found only shared instances of this token if found >0 here */ 646 KASSERT((found == 0), ("Token %p s/x livelock", tok)); 647 good: 648 #endif 649 650 if (_lwkt_trytokref_spin(ref, td, TOK_EXCLUSIVE|TOK_EXCLREQ)) 651 return; 652 653 /* 654 * Give up running if we can't acquire the token right now. 655 * 656 * Since the tokref is already active the scheduler now 657 * takes care of acquisition, so we need only call 658 * lwkt_switch(). 659 * 660 * Since we failed this was not a recursive token so upon 661 * return tr_tok->t_ref should be assigned to this specific 662 * ref. 663 */ 664 td->td_wmesg = tok->t_desc; 665 ++tok->t_collisions; 666 logtoken(fail, ref); 667 td->td_toks_have = td->td_toks_stop - 1; 668 669 if (tokens_debug_output > 0) { 670 --tokens_debug_output; 671 spin_lock(&tok_debug_spin); 672 kprintf("Excl Token thread %p %s %s\n", 673 td, tok->t_desc, td->td_comm); 674 print_backtrace(6); 675 kprintf("\n"); 676 spin_unlock(&tok_debug_spin); 677 } 678 679 lwkt_switch(); 680 logtoken(succ, ref); 681 KKASSERT(tok->t_ref == ref); 682 } 683 684 /* 685 * Similar to gettoken but we acquire a shared token instead of an exclusive 686 * token. 687 */ 688 void 689 lwkt_gettoken_shared(lwkt_token_t tok) 690 { 691 thread_t td = curthread; 692 lwkt_tokref_t ref; 693 694 ref = td->td_toks_stop; 695 KKASSERT(ref < &td->td_toks_end); 696 ++td->td_toks_stop; 697 cpu_ccfence(); 698 _lwkt_tokref_init(ref, tok, td, TOK_EXCLREQ); 699 700 #ifdef DEBUG_LOCKS 701 /* 702 * Taking a pool token in shared mode is a bad idea; other 703 * addresses deeper in the call stack may hash to the same pool 704 * token and you may end up with an exclusive-shared livelock. 705 * Warn in this condition. 706 */ 707 if ((tok >= &pool_tokens[0]) && 708 (tok < &pool_tokens[LWKT_NUM_POOL_TOKENS])) 709 kprintf("Warning! Taking pool token %p in shared mode\n", tok); 710 #endif 711 712 713 if (_lwkt_trytokref_spin(ref, td, TOK_EXCLREQ)) 714 return; 715 716 /* 717 * Give up running if we can't acquire the token right now. 718 * 719 * Since the tokref is already active the scheduler now 720 * takes care of acquisition, so we need only call 721 * lwkt_switch(). 722 * 723 * Since we failed this was not a recursive token so upon 724 * return tr_tok->t_ref should be assigned to this specific 725 * ref. 726 */ 727 td->td_wmesg = tok->t_desc; 728 ++tok->t_collisions; 729 logtoken(fail, ref); 730 td->td_toks_have = td->td_toks_stop - 1; 731 732 if (tokens_debug_output > 0) { 733 --tokens_debug_output; 734 spin_lock(&tok_debug_spin); 735 kprintf("Shar Token thread %p %s %s\n", 736 td, tok->t_desc, td->td_comm); 737 print_backtrace(6); 738 kprintf("\n"); 739 spin_unlock(&tok_debug_spin); 740 } 741 742 lwkt_switch(); 743 logtoken(succ, ref); 744 } 745 746 /* 747 * Attempt to acquire a token, return TRUE on success, FALSE on failure. 748 * 749 * We setup the tokref in case we actually get the token (if we switch later 750 * it becomes mandatory so we set TOK_EXCLREQ), but we call trytokref without 751 * TOK_EXCLREQ in case we fail. 752 */ 753 int 754 lwkt_trytoken(lwkt_token_t tok) 755 { 756 thread_t td = curthread; 757 lwkt_tokref_t ref; 758 759 ref = td->td_toks_stop; 760 KKASSERT(ref < &td->td_toks_end); 761 ++td->td_toks_stop; 762 cpu_ccfence(); 763 _lwkt_tokref_init(ref, tok, td, TOK_EXCLUSIVE|TOK_EXCLREQ); 764 765 if (_lwkt_trytokref(ref, td, TOK_EXCLUSIVE)) 766 return TRUE; 767 768 /* 769 * Failed, unpend the request 770 */ 771 cpu_ccfence(); 772 --td->td_toks_stop; 773 ++tok->t_collisions; 774 return FALSE; 775 } 776 777 778 void 779 lwkt_gettoken_hard(lwkt_token_t tok) 780 { 781 lwkt_gettoken(tok); 782 crit_enter_hard(); 783 } 784 785 lwkt_token_t 786 lwkt_getpooltoken(void *ptr) 787 { 788 lwkt_token_t tok; 789 790 tok = _lwkt_token_pool_lookup(ptr); 791 lwkt_gettoken(tok); 792 return (tok); 793 } 794 795 /* 796 * Release a serializing token. 797 * 798 * WARNING! All tokens must be released in reverse order. This will be 799 * asserted. 800 */ 801 void 802 lwkt_reltoken(lwkt_token_t tok) 803 { 804 thread_t td = curthread; 805 lwkt_tokref_t ref; 806 807 /* 808 * Remove ref from thread token list and assert that it matches 809 * the token passed in. Tokens must be released in reverse order. 810 */ 811 ref = td->td_toks_stop - 1; 812 KKASSERT(ref >= &td->td_toks_base && ref->tr_tok == tok); 813 _lwkt_reltokref(ref, td); 814 cpu_sfence(); 815 td->td_toks_stop = ref; 816 } 817 818 void 819 lwkt_reltoken_hard(lwkt_token_t tok) 820 { 821 lwkt_reltoken(tok); 822 crit_exit_hard(); 823 } 824 825 /* 826 * It is faster for users of lwkt_getpooltoken() to use the returned 827 * token and just call lwkt_reltoken(), but for convenience we provide 828 * this function which looks the token up based on the ident. 829 */ 830 void 831 lwkt_relpooltoken(void *ptr) 832 { 833 lwkt_token_t tok = _lwkt_token_pool_lookup(ptr); 834 lwkt_reltoken(tok); 835 } 836 837 /* 838 * Return a count of the number of token refs the thread has to the 839 * specified token, whether it currently owns the token or not. 840 */ 841 int 842 lwkt_cnttoken(lwkt_token_t tok, thread_t td) 843 { 844 lwkt_tokref_t scan; 845 int count = 0; 846 847 for (scan = &td->td_toks_base; scan < td->td_toks_stop; ++scan) { 848 if (scan->tr_tok == tok) 849 ++count; 850 } 851 return(count); 852 } 853 854 /* 855 * Pool tokens are used to provide a type-stable serializing token 856 * pointer that does not race against disappearing data structures. 857 * 858 * This routine is called in early boot just after we setup the BSP's 859 * globaldata structure. 860 */ 861 void 862 lwkt_token_pool_init(void) 863 { 864 int i; 865 866 for (i = 0; i < LWKT_NUM_POOL_TOKENS; ++i) 867 lwkt_token_init(&pool_tokens[i], "pool"); 868 } 869 870 lwkt_token_t 871 lwkt_token_pool_lookup(void *ptr) 872 { 873 return (_lwkt_token_pool_lookup(ptr)); 874 } 875 876 /* 877 * Initialize a token. 878 */ 879 void 880 lwkt_token_init(lwkt_token_t tok, const char *desc) 881 { 882 tok->t_count = 0; 883 tok->t_ref = NULL; 884 tok->t_collisions = 0; 885 tok->t_desc = desc; 886 } 887 888 void 889 lwkt_token_uninit(lwkt_token_t tok) 890 { 891 /* empty */ 892 } 893 894 /* 895 * Exchange the two most recent tokens on the tokref stack. This allows 896 * you to release a token out of order. 897 * 898 * We have to be careful about the case where the top two tokens are 899 * the same token. In this case tok->t_ref will point to the deeper 900 * ref and must remain pointing to the deeper ref. If we were to swap 901 * it the first release would clear the token even though a second 902 * ref is still present. 903 * 904 * Only exclusively held tokens contain a reference to the tokref which 905 * has to be flipped along with the swap. 906 */ 907 void 908 lwkt_token_swap(void) 909 { 910 lwkt_tokref_t ref1, ref2; 911 lwkt_token_t tok1, tok2; 912 long count1, count2; 913 thread_t td = curthread; 914 915 crit_enter(); 916 917 ref1 = td->td_toks_stop - 1; 918 ref2 = td->td_toks_stop - 2; 919 KKASSERT(ref1 >= &td->td_toks_base); 920 KKASSERT(ref2 >= &td->td_toks_base); 921 922 tok1 = ref1->tr_tok; 923 tok2 = ref2->tr_tok; 924 count1 = ref1->tr_count; 925 count2 = ref2->tr_count; 926 927 if (tok1 != tok2) { 928 ref1->tr_tok = tok2; 929 ref1->tr_count = count2; 930 ref2->tr_tok = tok1; 931 ref2->tr_count = count1; 932 if (tok1->t_ref == ref1) 933 tok1->t_ref = ref2; 934 if (tok2->t_ref == ref2) 935 tok2->t_ref = ref1; 936 } 937 938 crit_exit(); 939 } 940 941 #ifdef DDB 942 DB_SHOW_COMMAND(tokens, db_tok_all) 943 { 944 struct lwkt_token *tok, **ptr; 945 struct lwkt_token *toklist[16] = { 946 &mp_token, 947 &pmap_token, 948 &dev_token, 949 &vm_token, 950 &vmspace_token, 951 &kvm_token, 952 &sigio_token, 953 &tty_token, 954 &vnode_token, 955 NULL 956 }; 957 958 ptr = toklist; 959 for (tok = *ptr; tok; tok = *(++ptr)) { 960 db_printf("tok=%p tr_owner=%p t_colissions=%ld t_desc=%s\n", tok, 961 (tok->t_ref ? tok->t_ref->tr_owner : NULL), 962 tok->t_collisions, tok->t_desc); 963 } 964 } 965 #endif /* DDB */ 966