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