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