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.22 2005/07/07 20:28:26 hmp Exp $ 35 */ 36 37 #ifdef _KERNEL 38 39 #include <sys/param.h> 40 #include <sys/systm.h> 41 #include <sys/kernel.h> 42 #include <sys/proc.h> 43 #include <sys/rtprio.h> 44 #include <sys/queue.h> 45 #include <sys/thread2.h> 46 #include <sys/sysctl.h> 47 #include <sys/ktr.h> 48 #include <sys/kthread.h> 49 #include <machine/cpu.h> 50 #include <sys/lock.h> 51 #include <sys/caps.h> 52 53 #include <vm/vm.h> 54 #include <vm/vm_param.h> 55 #include <vm/vm_kern.h> 56 #include <vm/vm_object.h> 57 #include <vm/vm_page.h> 58 #include <vm/vm_map.h> 59 #include <vm/vm_pager.h> 60 #include <vm/vm_extern.h> 61 #include <vm/vm_zone.h> 62 63 #include <machine/stdarg.h> 64 #include <machine/ipl.h> 65 #include <machine/smp.h> 66 67 #define THREAD_STACK (UPAGES * PAGE_SIZE) 68 69 #else 70 71 #include <sys/stdint.h> 72 #include <libcaps/thread.h> 73 #include <sys/thread.h> 74 #include <sys/msgport.h> 75 #include <sys/errno.h> 76 #include <libcaps/globaldata.h> 77 #include <machine/cpufunc.h> 78 #include <sys/thread2.h> 79 #include <sys/msgport2.h> 80 #include <stdio.h> 81 #include <stdlib.h> 82 #include <string.h> 83 #include <machine/lock.h> 84 #include <machine/cpu.h> 85 86 #endif 87 88 #define MAKE_TOKENS_SPIN 89 /* #define MAKE_TOKENS_YIELD */ 90 91 #ifndef LWKT_NUM_POOL_TOKENS 92 #define LWKT_NUM_POOL_TOKENS 1024 /* power of 2 */ 93 #endif 94 #define LWKT_MASK_POOL_TOKENS (LWKT_NUM_POOL_TOKENS - 1) 95 96 #ifdef INVARIANTS 97 static int token_debug = 0; 98 #endif 99 100 #ifdef SMP 101 static void lwkt_reqtoken_remote(void *data); 102 #endif 103 104 static lwkt_token pool_tokens[LWKT_NUM_POOL_TOKENS]; 105 106 #define TOKEN_STRING "REF=%p TOK=%p TD=%p" 107 #define CONTENDED_STRING "REF=%p TOK=%p TD=%p (contention started)" 108 #define UNCONTENDED_STRING "REF=%p TOK=%p TD=%p (contention stopped)" 109 #if !defined(KTR_TOKENS) 110 #define KTR_TOKENS KTR_ALL 111 #endif 112 113 KTR_INFO_MASTER(tokens); 114 KTR_INFO(KTR_TOKENS, tokens, try, 0, TOKEN_STRING, sizeof(void *) * 3); 115 KTR_INFO(KTR_TOKENS, tokens, get, 1, TOKEN_STRING, sizeof(void *) * 3); 116 KTR_INFO(KTR_TOKENS, tokens, release, 2, TOKEN_STRING, sizeof(void *) * 3); 117 #ifdef SMP 118 KTR_INFO(KTR_TOKENS, tokens, remote, 3, TOKEN_STRING, sizeof(void *) * 3); 119 KTR_INFO(KTR_TOKENS, tokens, reqremote, 4, TOKEN_STRING, sizeof(void *) * 3); 120 KTR_INFO(KTR_TOKENS, tokens, reqfail, 5, TOKEN_STRING, sizeof(void *) * 3); 121 KTR_INFO(KTR_TOKENS, tokens, drain, 6, TOKEN_STRING, sizeof(void *) * 3); 122 KTR_INFO(KTR_TOKENS, tokens, contention_start, 7, CONTENDED_STRING, sizeof(void *) * 3); 123 KTR_INFO(KTR_TOKENS, tokens, contention_stop, 7, UNCONTENDED_STRING, sizeof(void *) * 3); 124 #endif 125 126 #define logtoken(name, ref) \ 127 KTR_LOG(tokens_ ## name, ref, ref->tr_tok, curthread) 128 129 #ifdef _KERNEL 130 131 #ifdef INVARIANTS 132 SYSCTL_INT(_lwkt, OID_AUTO, token_debug, CTLFLAG_RW, &token_debug, 0, ""); 133 #endif 134 135 #endif 136 137 #ifdef SMP 138 139 /* 140 * Determine if we own all the tokens in the token reference list. 141 * Return 1 on success, 0 on failure. 142 * 143 * As a side effect, queue requests for tokens we want which are owned 144 * by other cpus. The magic number is used to communicate when the 145 * target cpu has processed the request. Note, however, that the 146 * target cpu may not be able to assign the token to us which is why 147 * the scheduler must spin. 148 */ 149 int 150 lwkt_chktokens(thread_t td) 151 { 152 globaldata_t gd = td->td_gd; /* mycpu */ 153 lwkt_tokref_t refs; 154 globaldata_t dgd; 155 lwkt_token_t tok; 156 __uint32_t magic; 157 int r = 1; 158 159 KKASSERT(gd->gd_curthread->td_pri >= TDPRI_CRIT); 160 for (refs = td->td_toks; refs; refs = refs->tr_next) { 161 tok = refs->tr_tok; 162 if ((dgd = tok->t_cpu) != gd) { 163 cpu_ccfence(); /* don't let the compiler reload tok->t_cpu */ 164 r = 0; 165 #ifdef INVARIANTS 166 if ((refs->tr_flags & LWKT_TOKREF_CONTENDED) == 0) { 167 refs->tr_flags |= LWKT_TOKREF_CONTENDED; 168 /* mark token contended */ 169 logtoken(contention_start, refs); 170 } 171 #endif 172 173 /* 174 * Queue a request to the target cpu, exit the loop early if 175 * we are unable to queue the IPI message. The magic number 176 * flags whether we have a pending ipi request queued or not. 177 * It can be set from MAGIC2 to MAGIC1 by a remote cpu but can 178 * only be set from MAGIC1 to MAGIC2 by our cpu. 179 */ 180 magic = refs->tr_magic; 181 cpu_ccfence(); 182 if (magic == LWKT_TOKREF_MAGIC1) { 183 refs->tr_magic = LWKT_TOKREF_MAGIC2; /* MP synched slowreq*/ 184 refs->tr_reqgd = gd; 185 tok->t_reqcpu = gd; /* MP unsynchronized 'fast' req */ 186 187 logtoken(reqremote, refs); 188 189 if (lwkt_send_ipiq_nowait(dgd, lwkt_reqtoken_remote, refs)) { 190 /* failed */ 191 refs->tr_magic = LWKT_TOKREF_MAGIC1; 192 193 logtoken(reqfail, refs); 194 break; 195 } 196 } else if (magic != LWKT_TOKREF_MAGIC2) { 197 panic("lwkt_chktoken(): token ref %p tok %p bad magic %08x\n", 198 refs, refs->tr_tok, magic); 199 } 200 } 201 #ifdef INVARIANTS 202 if (refs->tr_flags & LWKT_TOKREF_CONTENDED) { 203 /* mark token uncontended */ 204 refs->tr_flags &= ~LWKT_TOKREF_CONTENDED; 205 logtoken(contention_stop, refs); 206 } 207 #endif 208 } 209 return(r); 210 } 211 212 #endif 213 214 /* 215 * Check if we already own the token. Return 1 on success, 0 on failure. 216 */ 217 int 218 lwkt_havetoken(lwkt_token_t tok) 219 { 220 globaldata_t gd = mycpu; 221 thread_t td = gd->gd_curthread; 222 lwkt_tokref_t ref; 223 224 for (ref = td->td_toks; ref; ref = ref->tr_next) { 225 if (ref->tr_tok == tok) 226 return(1); 227 } 228 return(0); 229 } 230 231 int 232 lwkt_havetokref(lwkt_tokref_t xref) 233 { 234 globaldata_t gd = mycpu; 235 thread_t td = gd->gd_curthread; 236 lwkt_tokref_t ref; 237 238 for (ref = td->td_toks; ref; ref = ref->tr_next) { 239 if (ref == xref) 240 return(1); 241 } 242 return(0); 243 } 244 245 #ifdef SMP 246 247 /* 248 * Returns 1 if it is ok to give a token away, 0 if it is not. 249 */ 250 static int 251 lwkt_oktogiveaway_token(lwkt_token_t tok) 252 { 253 globaldata_t gd = mycpu; 254 lwkt_tokref_t ref; 255 thread_t td; 256 257 for (td = gd->gd_curthread; td; td = td->td_preempted) { 258 for (ref = td->td_toks; ref; ref = ref->tr_next) { 259 if (ref->tr_tok == tok) 260 return(0); 261 } 262 } 263 return(1); 264 } 265 266 #endif 267 268 /* 269 * Acquire a serializing token 270 */ 271 272 static __inline 273 void 274 _lwkt_gettokref(lwkt_tokref_t ref) 275 { 276 lwkt_tokref_t scan; 277 lwkt_token_t tok; 278 globaldata_t gd; 279 thread_t td; 280 281 gd = mycpu; /* our cpu */ 282 KKASSERT(ref->tr_magic == LWKT_TOKREF_MAGIC1); 283 KKASSERT(gd->gd_intr_nesting_level == 0); 284 td = gd->gd_curthread; /* our thread */ 285 286 /* 287 * Link the request into our thread's list. This interlocks against 288 * remote requests from other cpus, prevents the token from being 289 * given away if our cpu already owns it, and interlocks against 290 * preempting threads which may want the token. This also allows us to 291 * avoid using a critical section. 292 */ 293 ref->tr_next = td->td_toks; 294 cpu_ccfence(); /* prevent compiler reordering */ 295 td->td_toks = ref; 296 tok = ref->tr_tok; 297 298 /* 299 * If we are preempting another thread which owns the token we have to 300 * yield to get out from the preemption because we cannot obtain a token 301 * owned by the thread we are preempting. 302 */ 303 if (td->td_preempted) { 304 while ((td = td->td_preempted) != NULL) { 305 for (scan = td->td_toks; scan; scan = scan->tr_next) { 306 if (scan->tr_tok == tok) { 307 lwkt_yield(); 308 KKASSERT(tok->t_cpu == gd); 309 goto breakout; 310 } 311 } 312 } 313 breakout: ; 314 td = gd->gd_curthread; /* our thread, again */ 315 } 316 317 /* 318 * If our cpu does not own the token then (currently) spin while we 319 * await it. XXX we should yield here but some testing is required 320 * before we do so, there could be some interlock issues with e.g. 321 * softupdates before we can yield. ZZZ 322 */ 323 #ifdef SMP 324 if (tok->t_cpu != gd) { 325 #if defined(MAKE_TOKENS_SPIN) 326 int x = 40000000; 327 int y = 10; 328 crit_enter(); 329 while (lwkt_chktokens(td) == 0) { 330 lwkt_process_ipiq(); 331 lwkt_drain_token_requests(); 332 if (--x == 0) { 333 x = 40000000; 334 printf("CHKTOKEN looping on cpu %d\n", gd->gd_cpuid); 335 #ifdef _KERNEL 336 if (--y == 0) 337 panic("CHKTOKEN looping on cpu %d", gd->gd_cpuid); 338 #endif 339 } 340 splz(); 341 } 342 crit_exit(); 343 #elif defined(MAKE_TOKENS_YIELD) 344 lwkt_yield(); 345 #else 346 #error MAKE_TOKENS_XXX ? 347 #endif 348 KKASSERT(tok->t_cpu == gd); 349 } 350 #endif 351 } 352 353 354 /* 355 * Attempt to acquire a serializing token 356 */ 357 static __inline 358 int 359 _lwkt_trytokref(lwkt_tokref_t ref) 360 { 361 lwkt_token_t tok; 362 globaldata_t gd; 363 thread_t td; 364 365 gd = mycpu; /* our cpu */ 366 KKASSERT(ref->tr_magic == LWKT_TOKREF_MAGIC1); 367 KKASSERT(gd->gd_intr_nesting_level == 0); 368 td = gd->gd_curthread; /* our thread */ 369 370 /* 371 * Link the request into our thread's list. This interlocks against 372 * remote requests from other cpus and prevents the token from being 373 * given away if our cpu already owns it. This also allows us to 374 * avoid using a critical section. 375 * 376 * Force a panic to occur if chktokens is called while the reference 377 * is linked to td_toks but before we have resolved whether we can 378 * keep it. chktokens should never be called on our ref list 379 * preemptively. 380 */ 381 ref->tr_magic = LWKT_TOKREF_MAGIC3; 382 ref->tr_next = td->td_toks; 383 cpu_ccfence(); /* prevent compiler reordering */ 384 td->td_toks = ref; 385 386 /* 387 * If our cpu does not own the token then stop now. 388 * 389 * Otherwise make sure the token is not held by a thread we are 390 * preempting. If it is, stop. 391 */ 392 tok = ref->tr_tok; 393 #ifdef SMP 394 if (tok->t_cpu != gd) { 395 td->td_toks = ref->tr_next; /* remove ref */ 396 ref->tr_magic = LWKT_TOKREF_MAGIC1; 397 return(0); 398 } 399 #endif 400 if (td->td_preempted) { 401 while ((td = td->td_preempted) != NULL) { 402 lwkt_tokref_t scan; 403 for (scan = td->td_toks; scan; scan = scan->tr_next) { 404 if (scan->tr_tok == tok) { 405 td = gd->gd_curthread; /* our thread */ 406 td->td_toks = ref->tr_next; /* remove ref */ 407 ref->tr_magic = LWKT_TOKREF_MAGIC1; 408 return(0); 409 } 410 } 411 } 412 } 413 414 /* 415 * We own the token, legitimize the reference. 416 */ 417 ref->tr_magic = LWKT_TOKREF_MAGIC1; 418 /* 'td' variable no longer valid */ 419 return(1); 420 } 421 422 void 423 lwkt_gettoken(lwkt_tokref_t ref, lwkt_token_t tok) 424 { 425 lwkt_tokref_init(ref, tok); 426 logtoken(get, ref); 427 _lwkt_gettokref(ref); 428 } 429 430 void 431 lwkt_gettokref(lwkt_tokref_t ref) 432 { 433 logtoken(get, ref); 434 _lwkt_gettokref(ref); 435 } 436 437 int 438 lwkt_trytoken(lwkt_tokref_t ref, lwkt_token_t tok) 439 { 440 lwkt_tokref_init(ref, tok); 441 logtoken(try, ref); 442 return(_lwkt_trytokref(ref)); 443 } 444 445 int 446 lwkt_trytokref(lwkt_tokref_t ref) 447 { 448 logtoken(try, ref); 449 return(_lwkt_trytokref(ref)); 450 } 451 452 /* 453 * Release a serializing token 454 */ 455 void 456 lwkt_reltoken(lwkt_tokref *_ref) 457 { 458 lwkt_tokref_t scan; 459 lwkt_tokref *ref; 460 lwkt_tokref **pref; 461 lwkt_token_t tok; 462 globaldata_t gd; 463 thread_t td; 464 int giveaway; 465 466 logtoken(release, _ref); 467 /* 468 * Guard check and stack check (if in the same stack page). We must 469 * also wait for any action pending on remote cpus which we do by 470 * checking the magic number and yielding in a loop. 471 */ 472 ref = _ref; 473 #ifdef INVARIANTS 474 if ((((intptr_t)ref ^ (intptr_t)&_ref) & ~(intptr_t)PAGE_MASK) == 0) 475 KKASSERT((char *)ref > (char *)&_ref); 476 KKASSERT(ref->tr_magic == LWKT_TOKREF_MAGIC1 || 477 ref->tr_magic == LWKT_TOKREF_MAGIC2); 478 #endif 479 480 tok = ref->tr_tok; 481 gd = mycpu; 482 td = gd->gd_curthread; 483 484 KKASSERT(tok->t_cpu == gd); 485 KKASSERT(gd->gd_intr_nesting_level == 0); 486 487 /* 488 * We can only give away the token if we aren't holding it recursively. 489 * Also use the opportunity to locate the link field for the token. 490 * 491 * We do not have to scan preempted threads since by definition we cannot 492 * be holding any token held by a thread we are preempting. 493 */ 494 giveaway = 1; 495 for (pref = &td->td_toks; (ref = *pref) != _ref; pref = &ref->tr_next) { 496 KKASSERT(ref != NULL); 497 if (ref->tr_tok == tok) 498 giveaway = 0; 499 } 500 for (scan = ref->tr_next; scan; scan = scan->tr_next) { 501 if (scan->tr_tok == tok) 502 giveaway = 0; 503 } 504 505 /* 506 * Give the token away (if we can) before removing the interlock. Once 507 * the interlock is removed, the token can be given away by an IPI. 508 */ 509 if (giveaway) 510 tok->t_cpu = tok->t_reqcpu; 511 KKASSERT(*pref == ref); 512 *pref = ref->tr_next; 513 514 /* 515 * If we had gotten the token opportunistically and it still happens to 516 * be queued to a target cpu, we have to wait for the target cpu 517 * to finish processing it. This does not happen very often and does 518 * not need to be optimal. 519 */ 520 while (ref->tr_magic == LWKT_TOKREF_MAGIC2) { 521 #if defined(MAKE_TOKENS_SPIN) 522 crit_enter(); 523 #ifdef SMP 524 lwkt_process_ipiq(); 525 #endif 526 splz(); 527 crit_exit(); 528 #elif defined(MAKE_TOKENS_YIELD) 529 lwkt_yield(); 530 #else 531 #error MAKE_TOKENS_XXX ? 532 #endif 533 } 534 KKASSERT(ref->tr_magic == LWKT_TOKREF_MAGIC1); 535 } 536 537 /* 538 * Pool tokens are used to provide a type-stable serializing token 539 * pointer that does not race against disappearing data structures. 540 * 541 * This routine is called in early boot just after we setup the BSP's 542 * globaldata structure. 543 */ 544 void 545 lwkt_token_pool_init(void) 546 { 547 int i; 548 549 for (i = 0; i < LWKT_NUM_POOL_TOKENS; ++i) 550 lwkt_token_init(&pool_tokens[i]); 551 } 552 553 lwkt_token_t 554 lwkt_token_pool_get(void *ptraddr) 555 { 556 int i; 557 558 i = ((int)(intptr_t)ptraddr >> 2) ^ ((int)(intptr_t)ptraddr >> 12); 559 return(&pool_tokens[i & LWKT_MASK_POOL_TOKENS]); 560 } 561 562 #ifdef SMP 563 564 /* 565 * This is the receiving side of a remote IPI requesting a token. If we 566 * cannot immediately hand the token off to another cpu we queue it. 567 * 568 * NOTE! we 'own' the ref structure, but we only 'own' the token if 569 * t_cpu == mycpu. 570 */ 571 static void 572 lwkt_reqtoken_remote(void *data) 573 { 574 lwkt_tokref_t ref = data; 575 globaldata_t gd = mycpu; 576 lwkt_token_t tok = ref->tr_tok; 577 578 logtoken(remote, ref); 579 /* 580 * We do not have to queue the token if we can give it away 581 * immediately. Otherwise we queue it to our globaldata structure. 582 */ 583 KASSERT(ref->tr_magic == LWKT_TOKREF_MAGIC2, ("ref %p token %p magic %08x", ref, ref->tr_tok, ref->tr_magic)); 584 if (lwkt_oktogiveaway_token(tok)) { 585 if (tok->t_cpu == gd) 586 tok->t_cpu = ref->tr_reqgd; 587 cpu_ccfence(); /* prevent compiler reordering */ 588 ref->tr_magic = LWKT_TOKREF_MAGIC1; 589 } else { 590 ref->tr_gdreqnext = gd->gd_tokreqbase; 591 gd->gd_tokreqbase = ref; 592 } 593 } 594 595 /* 596 * Must be called from a critical section. Satisfy all remote token 597 * requests that are pending on our globaldata structure. The request 598 * does not have to be satisfied with a successful change of ownership 599 * but we do have to acknowledge that we have completed processing the 600 * request by setting the magic number back to MAGIC1. 601 * 602 * NOTE! we 'own' the ref structure, but we only 'own' the token if 603 * t_cpu == mycpu. 604 */ 605 void 606 lwkt_drain_token_requests(void) 607 { 608 globaldata_t gd = mycpu; 609 lwkt_tokref_t ref; 610 611 KKASSERT(gd->gd_curthread->td_pri >= TDPRI_CRIT); 612 while ((ref = gd->gd_tokreqbase) != NULL) { 613 gd->gd_tokreqbase = ref->tr_gdreqnext; 614 logtoken(drain, ref); 615 KKASSERT(ref->tr_magic == LWKT_TOKREF_MAGIC2); 616 if (ref->tr_tok->t_cpu == gd) 617 ref->tr_tok->t_cpu = ref->tr_reqgd; 618 cpu_ccfence(); /* prevent compiler reordering */ 619 ref->tr_magic = LWKT_TOKREF_MAGIC1; 620 } 621 } 622 623 #endif 624 625 /* 626 * Initialize the owner and release-to cpu to the current cpu 627 * and reset the generation count. 628 */ 629 void 630 lwkt_token_init(lwkt_token_t tok) 631 { 632 tok->t_cpu = tok->t_reqcpu = mycpu; 633 } 634 635 void 636 lwkt_token_uninit(lwkt_token_t tok) 637 { 638 /* empty */ 639 } 640