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