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