1 /* 2 * Copyright (c) 2003,2004,2009 The DragonFly Project. All rights reserved. 3 * 4 * This code is derived from software contributed to The DragonFly Project 5 * by Matthew Dillon <dillon@backplane.com> 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * 3. Neither the name of The DragonFly Project nor the names of its 18 * contributors may be used to endorse or promote products derived 19 * from this software without specific, prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 */ 34 35 /* 36 * lwkt_token - Implement soft token locks. 37 * 38 * Tokens are locks which serialize a thread only while the thread is 39 * running. If the thread blocks all tokens are released, then reacquired 40 * when the thread resumes. 41 * 42 * This implementation requires no critical sections or spin locks, but 43 * does use atomic_cmpset_ptr(). 44 * 45 * Tokens may be recursively acquired by the same thread. However the 46 * caller must be sure to release such tokens in reverse order. 47 */ 48 #include <sys/param.h> 49 #include <sys/systm.h> 50 #include <sys/kernel.h> 51 #include <sys/proc.h> 52 #include <sys/rtprio.h> 53 #include <sys/queue.h> 54 #include <sys/sysctl.h> 55 #include <sys/ktr.h> 56 #include <sys/kthread.h> 57 #include <machine/cpu.h> 58 #include <sys/lock.h> 59 #include <sys/caps.h> 60 #include <sys/spinlock.h> 61 62 #include <sys/thread2.h> 63 #include <sys/spinlock2.h> 64 #include <sys/mplock2.h> 65 66 #include <vm/vm.h> 67 #include <vm/vm_param.h> 68 #include <vm/vm_kern.h> 69 #include <vm/vm_object.h> 70 #include <vm/vm_page.h> 71 #include <vm/vm_map.h> 72 #include <vm/vm_pager.h> 73 #include <vm/vm_extern.h> 74 #include <vm/vm_zone.h> 75 76 #include <machine/stdarg.h> 77 #include <machine/smp.h> 78 79 #ifndef LWKT_NUM_POOL_TOKENS 80 #define LWKT_NUM_POOL_TOKENS 1024 /* power of 2 */ 81 #endif 82 #define LWKT_MASK_POOL_TOKENS (LWKT_NUM_POOL_TOKENS - 1) 83 84 #ifdef INVARIANTS 85 static int token_debug = 0; 86 #endif 87 88 static lwkt_token pool_tokens[LWKT_NUM_POOL_TOKENS]; 89 90 #define TOKEN_STRING "REF=%p TOK=%p TD=%p" 91 #define CONTENDED_STRING "REF=%p TOK=%p TD=%p (contention started)" 92 #define UNCONTENDED_STRING "REF=%p TOK=%p TD=%p (contention stopped)" 93 #if !defined(KTR_TOKENS) 94 #define KTR_TOKENS KTR_ALL 95 #endif 96 97 KTR_INFO_MASTER(tokens); 98 KTR_INFO(KTR_TOKENS, tokens, fail, 0, TOKEN_STRING, sizeof(void *) * 3); 99 KTR_INFO(KTR_TOKENS, tokens, succ, 1, TOKEN_STRING, sizeof(void *) * 3); 100 #if 0 101 KTR_INFO(KTR_TOKENS, tokens, release, 2, TOKEN_STRING, sizeof(void *) * 3); 102 KTR_INFO(KTR_TOKENS, tokens, remote, 3, TOKEN_STRING, sizeof(void *) * 3); 103 KTR_INFO(KTR_TOKENS, tokens, reqremote, 4, TOKEN_STRING, sizeof(void *) * 3); 104 KTR_INFO(KTR_TOKENS, tokens, reqfail, 5, TOKEN_STRING, sizeof(void *) * 3); 105 KTR_INFO(KTR_TOKENS, tokens, drain, 6, TOKEN_STRING, sizeof(void *) * 3); 106 KTR_INFO(KTR_TOKENS, tokens, contention_start, 7, CONTENDED_STRING, sizeof(void *) * 3); 107 KTR_INFO(KTR_TOKENS, tokens, contention_stop, 7, UNCONTENDED_STRING, sizeof(void *) * 3); 108 #endif 109 110 #define logtoken(name, ref) \ 111 KTR_LOG(tokens_ ## name, ref, ref->tr_tok, curthread) 112 113 #ifdef INVARIANTS 114 SYSCTL_INT(_lwkt, OID_AUTO, token_debug, CTLFLAG_RW, &token_debug, 0, ""); 115 #endif 116 117 /* 118 * Global tokens. These replace the MP lock for major subsystem locking. 119 * These tokens are initially used to lockup both global and individual 120 * operations. 121 * 122 * Once individual structures get their own locks these tokens are used 123 * only to protect global lists & other variables and to interlock 124 * allocations and teardowns and such. 125 * 126 * The UP initializer causes token acquisition to also acquire the MP lock 127 * for maximum compatibility. The feature may be enabled and disabled at 128 * any time, the MP state is copied to the tokref when the token is acquired 129 * and will not race against sysctl changes. 130 */ 131 struct lwkt_token pmap_token = LWKT_TOKEN_UP_INITIALIZER; 132 struct lwkt_token dev_token = LWKT_TOKEN_UP_INITIALIZER; 133 struct lwkt_token vm_token = LWKT_TOKEN_UP_INITIALIZER; 134 struct lwkt_token vmspace_token = LWKT_TOKEN_UP_INITIALIZER; 135 struct lwkt_token kvm_token = LWKT_TOKEN_UP_INITIALIZER; 136 struct lwkt_token proc_token = LWKT_TOKEN_UP_INITIALIZER; 137 struct lwkt_token tty_token = LWKT_TOKEN_UP_INITIALIZER; 138 struct lwkt_token vnode_token = LWKT_TOKEN_UP_INITIALIZER; 139 140 SYSCTL_INT(_lwkt, OID_AUTO, pmap_mpsafe, 141 CTLFLAG_RW, &pmap_token.t_flags, 0, ""); 142 SYSCTL_INT(_lwkt, OID_AUTO, dev_mpsafe, 143 CTLFLAG_RW, &dev_token.t_flags, 0, ""); 144 SYSCTL_INT(_lwkt, OID_AUTO, vm_mpsafe, 145 CTLFLAG_RW, &vm_token.t_flags, 0, ""); 146 SYSCTL_INT(_lwkt, OID_AUTO, vmspace_mpsafe, 147 CTLFLAG_RW, &vmspace_token.t_flags, 0, ""); 148 SYSCTL_INT(_lwkt, OID_AUTO, kvm_mpsafe, 149 CTLFLAG_RW, &kvm_token.t_flags, 0, ""); 150 SYSCTL_INT(_lwkt, OID_AUTO, proc_mpsafe, 151 CTLFLAG_RW, &proc_token.t_flags, 0, ""); 152 SYSCTL_INT(_lwkt, OID_AUTO, tty_mpsafe, 153 CTLFLAG_RW, &tty_token.t_flags, 0, ""); 154 SYSCTL_INT(_lwkt, OID_AUTO, vnode_mpsafe, 155 CTLFLAG_RW, &vnode_token.t_flags, 0, ""); 156 157 /* 158 * The collision count is bumped every time the LWKT scheduler fails 159 * to acquire needed tokens in addition to a normal lwkt_gettoken() 160 * stall. 161 */ 162 SYSCTL_LONG(_lwkt, OID_AUTO, pmap_collisions, 163 CTLFLAG_RW, &pmap_token.t_collisions, 0, ""); 164 SYSCTL_LONG(_lwkt, OID_AUTO, dev_collisions, 165 CTLFLAG_RW, &dev_token.t_collisions, 0, ""); 166 SYSCTL_LONG(_lwkt, OID_AUTO, vm_collisions, 167 CTLFLAG_RW, &vm_token.t_collisions, 0, ""); 168 SYSCTL_LONG(_lwkt, OID_AUTO, vmspace_collisions, 169 CTLFLAG_RW, &vmspace_token.t_collisions, 0, ""); 170 SYSCTL_LONG(_lwkt, OID_AUTO, kvm_collisions, 171 CTLFLAG_RW, &kvm_token.t_collisions, 0, ""); 172 SYSCTL_LONG(_lwkt, OID_AUTO, proc_collisions, 173 CTLFLAG_RW, &proc_token.t_collisions, 0, ""); 174 SYSCTL_LONG(_lwkt, OID_AUTO, tty_collisions, 175 CTLFLAG_RW, &tty_token.t_collisions, 0, ""); 176 SYSCTL_LONG(_lwkt, OID_AUTO, vnode_collisions, 177 CTLFLAG_RW, &vnode_token.t_collisions, 0, ""); 178 179 /* 180 * Return a pool token given an address 181 */ 182 static __inline 183 lwkt_token_t 184 _lwkt_token_pool_lookup(void *ptr) 185 { 186 int i; 187 188 i = ((int)(intptr_t)ptr >> 2) ^ ((int)(intptr_t)ptr >> 12); 189 return(&pool_tokens[i & LWKT_MASK_POOL_TOKENS]); 190 } 191 192 /* 193 * Initialize a tokref_t prior to making it visible in the thread's 194 * token array. 195 * 196 * As an optimization we set the MPSAFE flag if the thread is already 197 * holding the MP lock. This bypasses unncessary calls to get_mplock() and 198 * rel_mplock() on tokens which are not normally MPSAFE when the thread 199 * is already holding the MP lock. 200 */ 201 static __inline 202 void 203 _lwkt_tokref_init(lwkt_tokref_t ref, lwkt_token_t tok, thread_t td) 204 { 205 ref->tr_tok = tok; 206 ref->tr_owner = td; 207 ref->tr_flags = tok->t_flags; 208 #ifdef SMP 209 if (td->td_mpcount) 210 #endif 211 ref->tr_flags |= LWKT_TOKEN_MPSAFE; 212 } 213 214 /* 215 * Obtain all the tokens required by the specified thread on the current 216 * cpu, return 0 on failure and non-zero on success. If a failure occurs 217 * any partially acquired tokens will be released prior to return. 218 * 219 * lwkt_getalltokens is called by the LWKT scheduler to acquire all 220 * tokens that the thread had acquired prior to going to sleep. 221 * 222 * The scheduler is responsible for maintaining the MP lock count, so 223 * we don't need to deal with tr_flags here. We also do not do any 224 * logging here. The logging done by lwkt_gettoken() is plenty good 225 * enough to get a feel for it. 226 * 227 * Called from a critical section. 228 */ 229 int 230 lwkt_getalltokens(thread_t td) 231 { 232 lwkt_tokref_t scan; 233 lwkt_tokref_t ref; 234 lwkt_token_t tok; 235 236 /* 237 * Acquire tokens in forward order, assign or validate tok->t_ref. 238 */ 239 for (scan = &td->td_toks_base; scan < td->td_toks_stop; ++scan) { 240 tok = scan->tr_tok; 241 for (;;) { 242 /* 243 * Try to acquire the token if we do not already have 244 * it. 245 * 246 * NOTE: If atomic_cmpset_ptr() fails we have to 247 * loop and try again. It just means we 248 * lost a cpu race. 249 */ 250 ref = tok->t_ref; 251 if (ref == NULL) { 252 if (atomic_cmpset_ptr(&tok->t_ref, NULL, scan)) 253 break; 254 continue; 255 } 256 257 /* 258 * Test if ref is already recursively held by this 259 * thread. We cannot safely dereference tok->t_ref 260 * (it might belong to another thread and is thus 261 * unstable), but we don't have to. We can simply 262 * range-check it. 263 */ 264 if (ref >= &td->td_toks_base && ref < td->td_toks_stop) 265 break; 266 267 /* 268 * Otherwise we failed to acquire all the tokens. 269 * Undo and return. 270 */ 271 atomic_add_long(&tok->t_collisions, 1); 272 lwkt_relalltokens(td); 273 return(FALSE); 274 } 275 } 276 return (TRUE); 277 } 278 279 /* 280 * Release all tokens owned by the specified thread on the current cpu. 281 * 282 * This code is really simple. Even in cases where we own all the tokens 283 * note that t_ref may not match the scan for recursively held tokens, 284 * or for the case where a lwkt_getalltokens() failed. 285 * 286 * The scheduler is responsible for maintaining the MP lock count, so 287 * we don't need to deal with tr_flags here. 288 * 289 * Called from a critical section. 290 */ 291 void 292 lwkt_relalltokens(thread_t td) 293 { 294 lwkt_tokref_t scan; 295 lwkt_token_t tok; 296 297 for (scan = &td->td_toks_base; scan < td->td_toks_stop; ++scan) { 298 tok = scan->tr_tok; 299 if (tok->t_ref == scan) 300 tok->t_ref = NULL; 301 } 302 } 303 304 /* 305 * Token acquisition helper function. The caller must have already 306 * made nref visible by adjusting td_toks_stop and will be responsible 307 * for the disposition of nref on either success or failure. 308 * 309 * When acquiring tokens recursively we want tok->t_ref to point to 310 * the outer (first) acquisition so it gets cleared only on the last 311 * release. 312 */ 313 static __inline 314 int 315 _lwkt_trytokref2(lwkt_tokref_t nref, thread_t td) 316 { 317 lwkt_token_t tok; 318 lwkt_tokref_t ref; 319 320 KKASSERT(td->td_gd->gd_intr_nesting_level == 0); 321 322 /* 323 * Make sure the compiler does not reorder prior instructions 324 * beyond this demark. 325 */ 326 cpu_ccfence(); 327 328 /* 329 * Attempt to gain ownership 330 */ 331 tok = nref->tr_tok; 332 for (;;) { 333 /* 334 * Try to acquire the token if we do not already have 335 * it. 336 */ 337 ref = tok->t_ref; 338 if (ref == NULL) { 339 /* 340 * NOTE: If atomic_cmpset_ptr() fails we have to 341 * loop and try again. It just means we 342 * lost a cpu race. 343 */ 344 if (atomic_cmpset_ptr(&tok->t_ref, NULL, nref)) 345 return (TRUE); 346 continue; 347 } 348 349 /* 350 * Test if ref is already recursively held by this 351 * thread. We cannot safely dereference tok->t_ref 352 * (it might belong to another thread and is thus 353 * unstable), but we don't have to. We can simply 354 * range-check it. 355 */ 356 if (ref >= &td->td_toks_base && ref < td->td_toks_stop) 357 return(TRUE); 358 359 /* 360 * Otherwise we failed. 361 */ 362 return(FALSE); 363 } 364 } 365 366 /* 367 * Acquire a serializing token. This routine does not block. 368 */ 369 static __inline 370 int 371 _lwkt_trytokref(lwkt_tokref_t ref, thread_t td) 372 { 373 if ((ref->tr_flags & LWKT_TOKEN_MPSAFE) == 0) { 374 if (try_mplock() == 0) 375 return (FALSE); 376 } 377 if (_lwkt_trytokref2(ref, td) == FALSE) { 378 /* 379 * Cleanup, deactivate the failed token. 380 */ 381 --td->td_toks_stop; 382 if ((ref->tr_flags & LWKT_TOKEN_MPSAFE) == 0) 383 rel_mplock(); 384 return (FALSE); 385 } 386 return (TRUE); 387 } 388 389 /* 390 * Acquire a serializing token. This routine can block. 391 */ 392 static __inline 393 void 394 _lwkt_gettokref(lwkt_tokref_t ref, thread_t td) 395 { 396 if ((ref->tr_flags & LWKT_TOKEN_MPSAFE) == 0) 397 get_mplock(); 398 if (_lwkt_trytokref2(ref, td) == FALSE) { 399 /* 400 * Give up running if we can't acquire the token right now. 401 * 402 * Since the tokref is already active the scheduler now 403 * takes care of acquisition, so we need only call 404 * lwkt_yield(). 405 * 406 * Since we failed this was not a recursive token so upon 407 * return tr_tok->t_ref should be assigned to this specific 408 * ref. 409 */ 410 atomic_add_long(&ref->tr_tok->t_collisions, 1); 411 logtoken(fail, ref); 412 lwkt_yield(); 413 logtoken(succ, ref); 414 KKASSERT(ref->tr_tok->t_ref == ref); 415 } 416 } 417 418 void 419 lwkt_gettoken(lwkt_token_t tok) 420 { 421 thread_t td = curthread; 422 lwkt_tokref_t ref; 423 424 ref = td->td_toks_stop; 425 KKASSERT(ref < &td->td_toks_end); 426 _lwkt_tokref_init(ref, tok, td); 427 ++td->td_toks_stop; 428 _lwkt_gettokref(ref, td); 429 } 430 431 lwkt_token_t 432 lwkt_getpooltoken(void *ptr) 433 { 434 thread_t td = curthread; 435 lwkt_token_t tok; 436 lwkt_tokref_t ref; 437 438 ref = td->td_toks_stop; 439 KKASSERT(ref < &td->td_toks_end); 440 tok = _lwkt_token_pool_lookup(ptr); 441 _lwkt_tokref_init(ref, tok, td); 442 ++td->td_toks_stop; 443 _lwkt_gettokref(ref, td); 444 return(tok); 445 } 446 447 int 448 lwkt_trytoken(lwkt_token_t tok) 449 { 450 thread_t td = curthread; 451 lwkt_tokref_t ref; 452 453 ref = td->td_toks_stop; 454 KKASSERT(ref < &td->td_toks_end); 455 _lwkt_tokref_init(ref, tok, td); 456 ++td->td_toks_stop; 457 return(_lwkt_trytokref(ref, td)); 458 } 459 460 /* 461 * Release a serializing token. 462 * 463 * WARNING! All tokens must be released in reverse order. This will be 464 * asserted. 465 */ 466 void 467 lwkt_reltoken(lwkt_token_t tok) 468 { 469 thread_t td = curthread; 470 lwkt_tokref_t ref; 471 472 /* 473 * Remove ref from thread token list and assert that it matches 474 * the token passed in. Tokens must be released in reverse order. 475 */ 476 ref = td->td_toks_stop - 1; 477 KKASSERT(ref >= &td->td_toks_base && ref->tr_tok == tok); 478 td->td_toks_stop = ref; 479 480 /* 481 * If the token was not MPSAFE release the MP lock. 482 */ 483 if ((ref->tr_flags & LWKT_TOKEN_MPSAFE) == 0) 484 rel_mplock(); 485 486 /* 487 * Make sure the compiler does not reorder the clearing of 488 * tok->t_ref. 489 */ 490 cpu_ccfence(); 491 492 /* 493 * Only clear the token if it matches ref. If ref was a recursively 494 * acquired token it may not match. 495 */ 496 if (tok->t_ref == ref) 497 tok->t_ref = NULL; 498 } 499 500 /* 501 * Pool tokens are used to provide a type-stable serializing token 502 * pointer that does not race against disappearing data structures. 503 * 504 * This routine is called in early boot just after we setup the BSP's 505 * globaldata structure. 506 */ 507 void 508 lwkt_token_pool_init(void) 509 { 510 int i; 511 512 for (i = 0; i < LWKT_NUM_POOL_TOKENS; ++i) 513 lwkt_token_init(&pool_tokens[i], 1); 514 } 515 516 lwkt_token_t 517 lwkt_token_pool_lookup(void *ptr) 518 { 519 return (_lwkt_token_pool_lookup(ptr)); 520 } 521 522 /* 523 * Initialize a token. If mpsafe is 0, the MP lock is acquired before 524 * acquiring the token and released after releasing the token. 525 */ 526 void 527 lwkt_token_init(lwkt_token_t tok, int mpsafe) 528 { 529 tok->t_ref = NULL; 530 tok->t_flags = mpsafe ? LWKT_TOKEN_MPSAFE : 0; 531 tok->t_collisions = 0; 532 } 533 534 void 535 lwkt_token_uninit(lwkt_token_t tok) 536 { 537 /* empty */ 538 } 539 540 #if 0 541 int 542 lwkt_token_is_stale(lwkt_tokref_t ref) 543 { 544 lwkt_token_t tok = ref->tr_tok; 545 546 KKASSERT(tok->t_owner == curthread && ref->tr_state == 1 && 547 tok->t_count > 0); 548 549 /* Token is not stale */ 550 if (tok->t_lastowner == tok->t_owner) 551 return (FALSE); 552 553 /* 554 * The token is stale. Reset to not stale so that the next call to 555 * lwkt_token_is_stale will return "not stale" unless the token 556 * was acquired in-between by another thread. 557 */ 558 tok->t_lastowner = tok->t_owner; 559 return (TRUE); 560 } 561 #endif 562