sys/kern/lwkt_token.c

   1 /*
   2  * Copyright (c) 2003,2004 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  * $DragonFly: src/sys/kern/lwkt_token.c,v 1.31 2008/05/18 20:57:56 nth Exp $
  35  */
  36
  37 #include <sys/param.h>
  38 #include <sys/systm.h>
  39 #include <sys/kernel.h>
  40 #include <sys/proc.h>
  41 #include <sys/rtprio.h>
  42 #include <sys/queue.h>
  43 #include <sys/sysctl.h>
  44 #include <sys/ktr.h>
  45 #include <sys/kthread.h>
  46 #include <machine/cpu.h>
  47 #include <sys/lock.h>
  48 #include <sys/caps.h>
  49 #include <sys/spinlock.h>
  50
  51 #include <sys/thread2.h>
  52 #include <sys/spinlock2.h>
  53
  54 #include <vm/vm.h>
  55 #include <vm/vm_param.h>
  56 #include <vm/vm_kern.h>
  57 #include <vm/vm_object.h>
  58 #include <vm/vm_page.h>
  59 #include <vm/vm_map.h>
  60 #include <vm/vm_pager.h>
  61 #include <vm/vm_extern.h>
  62 #include <vm/vm_zone.h>
  63
  64 #include <machine/stdarg.h>
  65 #include <machine/smp.h>
  66
  67 #ifndef LWKT_NUM_POOL_TOKENS
  68 #define LWKT_NUM_POOL_TOKENS    1024    /* power of 2 */
  69 #endif
  70 #define LWKT_MASK_POOL_TOKENS   (LWKT_NUM_POOL_TOKENS - 1)
  71
  72 #ifdef INVARIANTS
  73 static int token_debug = 0;
  74 #endif
  75
  76 static lwkt_token       pool_tokens[LWKT_NUM_POOL_TOKENS];
  77
  78 #define TOKEN_STRING    "REF=%p TOK=%p TD=%p"
  79 #define CONTENDED_STRING        "REF=%p TOK=%p TD=%p (contention started)"
  80 #define UNCONTENDED_STRING      "REF=%p TOK=%p TD=%p (contention stopped)"
  81 #if !defined(KTR_TOKENS)
  82 #define KTR_TOKENS      KTR_ALL
  83 #endif
  84
  85 KTR_INFO_MASTER(tokens);
  86 KTR_INFO(KTR_TOKENS, tokens, try, 0, TOKEN_STRING, sizeof(void *) * 3);
  87 KTR_INFO(KTR_TOKENS, tokens, get, 1, TOKEN_STRING, sizeof(void *) * 3);
  88 KTR_INFO(KTR_TOKENS, tokens, release, 2, TOKEN_STRING, sizeof(void *) * 3);
  89 #if 0
  90 KTR_INFO(KTR_TOKENS, tokens, remote, 3, TOKEN_STRING, sizeof(void *) * 3);
  91 KTR_INFO(KTR_TOKENS, tokens, reqremote, 4, TOKEN_STRING, sizeof(void *) * 3);
  92 KTR_INFO(KTR_TOKENS, tokens, reqfail, 5, TOKEN_STRING, sizeof(void *) * 3);
  93 KTR_INFO(KTR_TOKENS, tokens, drain, 6, TOKEN_STRING, sizeof(void *) * 3);
  94 KTR_INFO(KTR_TOKENS, tokens, contention_start, 7, CONTENDED_STRING, sizeof(void *) * 3);
  95 KTR_INFO(KTR_TOKENS, tokens, contention_stop, 7, UNCONTENDED_STRING, sizeof(void *) * 3);
  96 #endif
  97
  98 #define logtoken(name, ref)                                             \
  99         KTR_LOG(tokens_ ## name, ref, ref->tr_tok, curthread)
 100
 101 #ifdef INVARIANTS
 102 SYSCTL_INT(_lwkt, OID_AUTO, token_debug, CTLFLAG_RW, &token_debug, 0, "");
 103 #endif
 104
 105 /*
 106  * Obtain all the tokens required by the specified thread on the current
 107  * cpu, return 0 on failure and non-zero on success.
 108  *
 109  * The preemption code will not allow a target thread holding spinlocks to
 110  * preempt the current thread so we do not have to implement this for UP.
 111  * The only reason why we implement this for UP is that we want to detect
 112  * stale tokens (lwkt_token_is_stale).
 113  *
 114  * lwkt_getalltokens is called by the LWKT scheduler to acquire all
 115  * tokens that the thread had aquired prior to going to sleep.
 116  *
 117  * Called from a critical section.
 118  */
 119 int
 120 lwkt_getalltokens(thread_t td)
 121 {
 122     lwkt_tokref_t refs;
 123 #ifdef SMP
 124     lwkt_tokref_t undo;
 125 #endif
 126     lwkt_token_t tok;
 127
 128     for (refs = td->td_toks; refs; refs = refs->tr_next) {
 129         KKASSERT(refs->tr_state == 0);
 130         tok = refs->tr_tok;
 131         if (tok->t_owner != td) {
 132 #ifdef SMP
 133             if (spin_trylock_wr(&tok->t_spinlock) == 0) {
 134                 /*
 135                  * Release the partial list of tokens obtained and return
 136                  * failure.
 137                  */
 138                 for (undo = td->td_toks; undo != refs; undo = undo->tr_next) {
 139                     tok = undo->tr_tok;
 140                     undo->tr_state = 0;
 141                     if (--tok->t_count == 0) {
 142                         tok->t_owner = NULL;
 143                         spin_unlock_wr(&tok->t_spinlock);
 144                     }
 145                 }
 146                 return (FALSE);
 147             }
 148 #endif
 149             KKASSERT(tok->t_owner == NULL && tok->t_count == 0);
 150             tok->t_owner = td;
 151
 152             /*
 153              * Detect the situation where the token was acquired by
 154              * another thread while the token was released from the
 155              * current thread due to a blocking condition.
 156              * In this case we set t_lastowner to NULL to mark the
 157              * token as stale from the point of view of BOTH threads.
 158              * See lwkt_token_is_stale().
 159              */
 160             if (tok->t_lastowner != tok->t_owner)
 161                 tok->t_lastowner = NULL;
 162         }
 163         ++tok->t_count;
 164         refs->tr_state = 1;
 165     }
 166     return (TRUE);
 167 }
 168
 169 /*
 170  * Release all tokens owned by the specified thread on the current cpu.
 171  *
 172  * Called from a critical section.
 173  */
 174 void
 175 lwkt_relalltokens(thread_t td)
 176 {
 177     lwkt_tokref_t refs;
 178     lwkt_token_t tok;
 179
 180     for (refs = td->td_toks; refs; refs = refs->tr_next) {
 181         if (refs->tr_state) {
 182             refs->tr_state = 0;
 183             tok = refs->tr_tok;
 184             KKASSERT(tok->t_owner == td && tok->t_count > 0);
 185             if (--tok->t_count == 0) {
 186                 tok->t_owner = NULL;
 187 #ifdef SMP
 188                 spin_unlock_wr(&tok->t_spinlock);
 189 #endif
 190             }
 191         }
 192     }
 193 }
 194
 195 /*
 196  * Token acquisition helper function.  Note that get/trytokenref do not
 197  * reset t_lastowner if the token is already held.  Only lwkt_token_is_stale()
 198  * is allowed to do that.
 199  *
 200  * NOTE: On failure, this function doesn't remove the token from the
 201  * thread's token list, so that you have to perform that yourself:
 202  *
 203  *      td->td_toks = ref->tr_next;
 204  */
 205 static __inline
 206 int
 207 _lwkt_trytokref2(lwkt_tokref_t ref, thread_t td)
 208 {
 209 #ifndef SMP
 210     lwkt_tokref_t scan;
 211     thread_t itd;
 212 #endif
 213     lwkt_token_t tok;
 214
 215     KKASSERT(mycpu->gd_intr_nesting_level == 0);
 216     KKASSERT(ref->tr_state == 0);
 217     tok = ref->tr_tok;
 218
 219     /*
 220      * Link the tokref to the thread's list
 221      */
 222     ref->tr_next = td->td_toks;
 223     cpu_ccfence();
 224
 225     /*
 226      * Once td_toks is set to a non NULL value, we can't preempt
 227      * another thread anymore (the scheduler takes care that this
 228      * won't happen). Additionally, we can't get preempted by
 229      * another thread that wants to access the same token (tok).
 230      */
 231     td->td_toks = ref;
 232
 233     if (tok->t_owner != td) {
 234 #ifdef SMP
 235         /*
 236          * Gain ownership of the token's spinlock, SMP version.
 237          */
 238         if (spin_trylock_wr(&tok->t_spinlock) == 0) {
 239             return (FALSE);
 240         }
 241 #else
 242         /*
 243          * Gain ownership of the token, UP version.   All we have to do
 244          * is check the token if we are preempting someone owning the
 245          * same token, in which case we fail to acquire the token.
 246          */
 247         itd = td;
 248         while ((itd = itd->td_preempted) != NULL) {
 249             for (scan = itd->td_toks; scan; scan = scan->tr_next) {
 250                 if (scan->tr_tok == tok) {
 251                     return (FALSE);
 252                 }
 253             }
 254         }
 255 #endif
 256         KKASSERT(tok->t_owner == NULL && tok->t_count == 0);
 257         tok->t_owner = td;
 258         tok->t_lastowner = td;
 259     }
 260     ++tok->t_count;
 261     ref->tr_state = 1;
 262
 263     return (TRUE);
 264 }
 265
 266 static __inline
 267 int
 268 _lwkt_trytokref(lwkt_tokref_t ref)
 269 {
 270     thread_t td = curthread;
 271
 272     if (_lwkt_trytokref2(ref, td) == FALSE) {
 273         /*
 274          * Cleanup. Remove the token from the thread's list.
 275          */
 276         td->td_toks = ref->tr_next;
 277         return (FALSE);
 278     }
 279
 280     return (TRUE);
 281 }
 282
 283 /*
 284  * Acquire a serializing token.  This routine can block.
 285  *
 286  * We track ownership and a per-owner counter.  Tokens are
 287  * released when a thread switches out and reacquired when a thread
 288  * switches back in.
 289  */
 290 static __inline
 291 void
 292 _lwkt_gettokref(lwkt_tokref_t ref)
 293 {
 294   if (_lwkt_trytokref2(ref, curthread) == FALSE) {
 295         /*
 296          * Give up running if we can't acquire the token right now. But as we
 297          * have linked in the tokref to the thread's list (_lwkt_trytokref2),
 298          * the scheduler now takes care to acquire the token (by calling
 299          * lwkt_getalltokens) before resuming execution. As such, when we
 300          * return from lwkt_yield(), the token is acquired.
 301          */
 302         lwkt_yield();
 303   }
 304 }
 305
 306 void
 307 lwkt_gettoken(lwkt_tokref_t ref, lwkt_token_t tok)
 308 {
 309     lwkt_tokref_init(ref, tok);
 310     logtoken(get, ref);
 311     _lwkt_gettokref(ref);
 312 }
 313
 314 void
 315 lwkt_gettokref(lwkt_tokref_t ref)
 316 {
 317     logtoken(get, ref);
 318     _lwkt_gettokref(ref);
 319 }
 320
 321 int
 322 lwkt_trytoken(lwkt_tokref_t ref, lwkt_token_t tok)
 323 {
 324     lwkt_tokref_init(ref, tok);
 325     logtoken(try, ref);
 326     return(_lwkt_trytokref(ref));
 327 }
 328
 329 int
 330 lwkt_trytokref(lwkt_tokref_t ref)
 331 {
 332     logtoken(try, ref);
 333     return(_lwkt_trytokref(ref));
 334 }
 335
 336 /*
 337  * Release a serializing token
 338  */
 339 void
 340 lwkt_reltoken(lwkt_tokref_t ref)
 341 {
 342     struct lwkt_tokref **scanp;
 343     lwkt_token_t tok;
 344     thread_t td;
 345
 346     td = curthread;
 347     tok = ref->tr_tok;
 348
 349     KKASSERT(tok->t_owner == td && ref->tr_state == 1 && tok->t_count > 0);
 350
 351     ref->tr_state = 0;
 352
 353     /*
 354      * Fix-up the count now to avoid racing a preemption which may occur
 355      * after the token has been removed from td_toks.
 356      */
 357     if (--tok->t_count == 0) {
 358         tok->t_owner = NULL;
 359         tok->t_lastowner = NULL;
 360 #ifdef SMP
 361         spin_unlock_wr(&tok->t_spinlock);
 362 #endif
 363      }
 364
 365     /*
 366      * Remove ref from thread's token list.
 367      *
 368      * After removing the token from the thread's list, it's unsafe
 369      * on a UP machine to modify the token, because we might get
 370      * preempted by another thread that wants to acquire the same token.
 371      * This thread now thinks that it can acquire the token, because it's
 372      * no longer in our thread's list. Bang!
 373      *
 374      * SMP: Do not modify token after spin_unlock_wr.
 375      */
 376     for (scanp = &td->td_toks; *scanp != ref; scanp = &((*scanp)->tr_next))
 377         ;
 378     *scanp = ref->tr_next;
 379
 380     logtoken(release, ref);
 381 }
 382
 383 /*
 384  * Pool tokens are used to provide a type-stable serializing token
 385  * pointer that does not race against disappearing data structures.
 386  *
 387  * This routine is called in early boot just after we setup the BSP's
 388  * globaldata structure.
 389  */
 390 void
 391 lwkt_token_pool_init(void)
 392 {
 393     int i;
 394
 395     for (i = 0; i < LWKT_NUM_POOL_TOKENS; ++i)
 396         lwkt_token_init(&pool_tokens[i]);
 397 }
 398
 399 lwkt_token_t
 400 lwkt_token_pool_get(void *ptraddr)
 401 {
 402     int i;
 403
 404     i = ((int)(intptr_t)ptraddr >> 2) ^ ((int)(intptr_t)ptraddr >> 12);
 405     return(&pool_tokens[i & LWKT_MASK_POOL_TOKENS]);
 406 }
 407
 408 /*
 409  * Initialize the owner and release-to cpu to the current cpu
 410  * and reset the generation count.
 411  */
 412 void
 413 lwkt_token_init(lwkt_token_t tok)
 414 {
 415 #ifdef SMP
 416     spin_init(&tok->t_spinlock);
 417 #endif
 418     tok->t_owner = NULL;
 419     tok->t_lastowner = NULL;
 420     tok->t_count = 0;
 421 }
 422
 423 void
 424 lwkt_token_uninit(lwkt_token_t tok)
 425 {
 426     /* empty */
 427 }
 428
 429 int
 430 lwkt_token_is_stale(lwkt_tokref_t ref)
 431 {
 432     lwkt_token_t tok = ref->tr_tok;
 433
 434     KKASSERT(tok->t_owner == curthread && ref->tr_state == 1 &&
 435              tok->t_count > 0);
 436
 437     /* Token is not stale */
 438     if (tok->t_lastowner == tok->t_owner)
 439         return (FALSE);
 440
 441     /*
 442      * The token is stale. Reset to not stale so that the next call to
 443      * lwkt_token_is_stale will return "not stale" unless the token
 444      * was acquired in-between by another thread.
 445      */
 446     tok->t_lastowner = tok->t_owner;
 447     return (TRUE);
 448 }