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