sys/kern/lwkt_token.c

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