1 /* $NetBSD: kern_timeout.c,v 1.45 2010/12/18 01:36:19 rmind Exp $ */ 2 3 /*- 4 * Copyright (c) 2003, 2006, 2007, 2008, 2009 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Jason R. Thorpe, and by Andrew Doran. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 /* 33 * Copyright (c) 2001 Thomas Nordin <nordin@openbsd.org> 34 * Copyright (c) 2000-2001 Artur Grabowski <art@openbsd.org> 35 * All rights reserved. 36 * 37 * Redistribution and use in source and binary forms, with or without 38 * modification, are permitted provided that the following conditions 39 * are met: 40 * 41 * 1. Redistributions of source code must retain the above copyright 42 * notice, this list of conditions and the following disclaimer. 43 * 2. Redistributions in binary form must reproduce the above copyright 44 * notice, this list of conditions and the following disclaimer in the 45 * documentation and/or other materials provided with the distribution. 46 * 3. The name of the author may not be used to endorse or promote products 47 * derived from this software without specific prior written permission. 48 * 49 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, 50 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY 51 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL 52 * THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 53 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 54 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 55 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 56 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 57 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 58 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 59 */ 60 61 #include <sys/cdefs.h> 62 __KERNEL_RCSID(0, "$NetBSD: kern_timeout.c,v 1.45 2010/12/18 01:36:19 rmind Exp $"); 63 64 /* 65 * Timeouts are kept in a hierarchical timing wheel. The c_time is the 66 * value of c_cpu->cc_ticks when the timeout should be called. There are 67 * four levels with 256 buckets each. See 'Scheme 7' in "Hashed and 68 * Hierarchical Timing Wheels: Efficient Data Structures for Implementing 69 * a Timer Facility" by George Varghese and Tony Lauck. 70 * 71 * Some of the "math" in here is a bit tricky. We have to beware of 72 * wrapping ints. 73 * 74 * We use the fact that any element added to the queue must be added with 75 * a positive time. That means that any element `to' on the queue cannot 76 * be scheduled to timeout further in time than INT_MAX, but c->c_time can 77 * be positive or negative so comparing it with anything is dangerous. 78 * The only way we can use the c->c_time value in any predictable way is 79 * when we calculate how far in the future `to' will timeout - "c->c_time 80 * - c->c_cpu->cc_ticks". The result will always be positive for future 81 * timeouts and 0 or negative for due timeouts. 82 */ 83 84 #define _CALLOUT_PRIVATE 85 86 #include <sys/param.h> 87 #include <sys/systm.h> 88 #include <sys/kernel.h> 89 #include <sys/callout.h> 90 #include <sys/lwp.h> 91 #include <sys/mutex.h> 92 #include <sys/proc.h> 93 #include <sys/sleepq.h> 94 #include <sys/syncobj.h> 95 #include <sys/evcnt.h> 96 #include <sys/intr.h> 97 #include <sys/cpu.h> 98 #include <sys/kmem.h> 99 100 #ifdef DDB 101 #include <machine/db_machdep.h> 102 #include <ddb/db_interface.h> 103 #include <ddb/db_access.h> 104 #include <ddb/db_sym.h> 105 #include <ddb/db_output.h> 106 #endif 107 108 #define BUCKETS 1024 109 #define WHEELSIZE 256 110 #define WHEELMASK 255 111 #define WHEELBITS 8 112 113 #define MASKWHEEL(wheel, time) (((time) >> ((wheel)*WHEELBITS)) & WHEELMASK) 114 115 #define BUCKET(cc, rel, abs) \ 116 (((rel) <= (1 << (2*WHEELBITS))) \ 117 ? ((rel) <= (1 << WHEELBITS)) \ 118 ? &(cc)->cc_wheel[MASKWHEEL(0, (abs))] \ 119 : &(cc)->cc_wheel[MASKWHEEL(1, (abs)) + WHEELSIZE] \ 120 : ((rel) <= (1 << (3*WHEELBITS))) \ 121 ? &(cc)->cc_wheel[MASKWHEEL(2, (abs)) + 2*WHEELSIZE] \ 122 : &(cc)->cc_wheel[MASKWHEEL(3, (abs)) + 3*WHEELSIZE]) 123 124 #define MOVEBUCKET(cc, wheel, time) \ 125 CIRCQ_APPEND(&(cc)->cc_todo, \ 126 &(cc)->cc_wheel[MASKWHEEL((wheel), (time)) + (wheel)*WHEELSIZE]) 127 128 /* 129 * Circular queue definitions. 130 */ 131 132 #define CIRCQ_INIT(list) \ 133 do { \ 134 (list)->cq_next_l = (list); \ 135 (list)->cq_prev_l = (list); \ 136 } while (/*CONSTCOND*/0) 137 138 #define CIRCQ_INSERT(elem, list) \ 139 do { \ 140 (elem)->cq_prev_e = (list)->cq_prev_e; \ 141 (elem)->cq_next_l = (list); \ 142 (list)->cq_prev_l->cq_next_l = (elem); \ 143 (list)->cq_prev_l = (elem); \ 144 } while (/*CONSTCOND*/0) 145 146 #define CIRCQ_APPEND(fst, snd) \ 147 do { \ 148 if (!CIRCQ_EMPTY(snd)) { \ 149 (fst)->cq_prev_l->cq_next_l = (snd)->cq_next_l; \ 150 (snd)->cq_next_l->cq_prev_l = (fst)->cq_prev_l; \ 151 (snd)->cq_prev_l->cq_next_l = (fst); \ 152 (fst)->cq_prev_l = (snd)->cq_prev_l; \ 153 CIRCQ_INIT(snd); \ 154 } \ 155 } while (/*CONSTCOND*/0) 156 157 #define CIRCQ_REMOVE(elem) \ 158 do { \ 159 (elem)->cq_next_l->cq_prev_e = (elem)->cq_prev_e; \ 160 (elem)->cq_prev_l->cq_next_e = (elem)->cq_next_e; \ 161 } while (/*CONSTCOND*/0) 162 163 #define CIRCQ_FIRST(list) ((list)->cq_next_e) 164 #define CIRCQ_NEXT(elem) ((elem)->cq_next_e) 165 #define CIRCQ_LAST(elem,list) ((elem)->cq_next_l == (list)) 166 #define CIRCQ_EMPTY(list) ((list)->cq_next_l == (list)) 167 168 static void callout_softclock(void *); 169 170 struct callout_cpu { 171 kmutex_t *cc_lock; 172 sleepq_t cc_sleepq; 173 u_int cc_nwait; 174 u_int cc_ticks; 175 lwp_t *cc_lwp; 176 callout_impl_t *cc_active; 177 callout_impl_t *cc_cancel; 178 struct evcnt cc_ev_late; 179 struct evcnt cc_ev_block; 180 struct callout_circq cc_todo; /* Worklist */ 181 struct callout_circq cc_wheel[BUCKETS]; /* Queues of timeouts */ 182 char cc_name1[12]; 183 char cc_name2[12]; 184 }; 185 186 static struct callout_cpu callout_cpu0; 187 static void *callout_sih; 188 189 static inline kmutex_t * 190 callout_lock(callout_impl_t *c) 191 { 192 struct callout_cpu *cc; 193 kmutex_t *lock; 194 195 for (;;) { 196 cc = c->c_cpu; 197 lock = cc->cc_lock; 198 mutex_spin_enter(lock); 199 if (__predict_true(cc == c->c_cpu)) 200 return lock; 201 mutex_spin_exit(lock); 202 } 203 } 204 205 /* 206 * callout_startup: 207 * 208 * Initialize the callout facility, called at system startup time. 209 * Do just enough to allow callouts to be safely registered. 210 */ 211 void 212 callout_startup(void) 213 { 214 struct callout_cpu *cc; 215 int b; 216 217 KASSERT(curcpu()->ci_data.cpu_callout == NULL); 218 219 cc = &callout_cpu0; 220 cc->cc_lock = mutex_obj_alloc(MUTEX_DEFAULT, IPL_SCHED); 221 CIRCQ_INIT(&cc->cc_todo); 222 for (b = 0; b < BUCKETS; b++) 223 CIRCQ_INIT(&cc->cc_wheel[b]); 224 curcpu()->ci_data.cpu_callout = cc; 225 } 226 227 /* 228 * callout_init_cpu: 229 * 230 * Per-CPU initialization. 231 */ 232 void 233 callout_init_cpu(struct cpu_info *ci) 234 { 235 struct callout_cpu *cc; 236 int b; 237 238 CTASSERT(sizeof(callout_impl_t) <= sizeof(callout_t)); 239 240 if ((cc = ci->ci_data.cpu_callout) == NULL) { 241 cc = kmem_zalloc(sizeof(*cc), KM_SLEEP); 242 if (cc == NULL) 243 panic("callout_init_cpu (1)"); 244 cc->cc_lock = mutex_obj_alloc(MUTEX_DEFAULT, IPL_SCHED); 245 CIRCQ_INIT(&cc->cc_todo); 246 for (b = 0; b < BUCKETS; b++) 247 CIRCQ_INIT(&cc->cc_wheel[b]); 248 } else { 249 /* Boot CPU, one time only. */ 250 callout_sih = softint_establish(SOFTINT_CLOCK | SOFTINT_MPSAFE, 251 callout_softclock, NULL); 252 if (callout_sih == NULL) 253 panic("callout_init_cpu (2)"); 254 } 255 256 sleepq_init(&cc->cc_sleepq); 257 258 snprintf(cc->cc_name1, sizeof(cc->cc_name1), "late/%u", 259 cpu_index(ci)); 260 evcnt_attach_dynamic(&cc->cc_ev_late, EVCNT_TYPE_MISC, 261 NULL, "callout", cc->cc_name1); 262 263 snprintf(cc->cc_name2, sizeof(cc->cc_name2), "wait/%u", 264 cpu_index(ci)); 265 evcnt_attach_dynamic(&cc->cc_ev_block, EVCNT_TYPE_MISC, 266 NULL, "callout", cc->cc_name2); 267 268 ci->ci_data.cpu_callout = cc; 269 } 270 271 /* 272 * callout_init: 273 * 274 * Initialize a callout structure. This must be quick, so we fill 275 * only the minimum number of fields. 276 */ 277 void 278 callout_init(callout_t *cs, u_int flags) 279 { 280 callout_impl_t *c = (callout_impl_t *)cs; 281 struct callout_cpu *cc; 282 283 KASSERT((flags & ~CALLOUT_FLAGMASK) == 0); 284 285 cc = curcpu()->ci_data.cpu_callout; 286 c->c_func = NULL; 287 c->c_magic = CALLOUT_MAGIC; 288 if (__predict_true((flags & CALLOUT_MPSAFE) != 0 && cc != NULL)) { 289 c->c_flags = flags; 290 c->c_cpu = cc; 291 return; 292 } 293 c->c_flags = flags | CALLOUT_BOUND; 294 c->c_cpu = &callout_cpu0; 295 } 296 297 /* 298 * callout_destroy: 299 * 300 * Destroy a callout structure. The callout must be stopped. 301 */ 302 void 303 callout_destroy(callout_t *cs) 304 { 305 callout_impl_t *c = (callout_impl_t *)cs; 306 307 /* 308 * It's not necessary to lock in order to see the correct value 309 * of c->c_flags. If the callout could potentially have been 310 * running, the current thread should have stopped it. 311 */ 312 KASSERT((c->c_flags & CALLOUT_PENDING) == 0); 313 KASSERT(c->c_cpu->cc_lwp == curlwp || c->c_cpu->cc_active != c); 314 KASSERT(c->c_magic == CALLOUT_MAGIC); 315 c->c_magic = 0; 316 } 317 318 /* 319 * callout_schedule_locked: 320 * 321 * Schedule a callout to run. The function and argument must 322 * already be set in the callout structure. Must be called with 323 * callout_lock. 324 */ 325 static void 326 callout_schedule_locked(callout_impl_t *c, kmutex_t *lock, int to_ticks) 327 { 328 struct callout_cpu *cc, *occ; 329 int old_time; 330 331 KASSERT(to_ticks >= 0); 332 KASSERT(c->c_func != NULL); 333 334 /* Initialize the time here, it won't change. */ 335 occ = c->c_cpu; 336 c->c_flags &= ~(CALLOUT_FIRED | CALLOUT_INVOKING); 337 338 /* 339 * If this timeout is already scheduled and now is moved 340 * earlier, reschedule it now. Otherwise leave it in place 341 * and let it be rescheduled later. 342 */ 343 if ((c->c_flags & CALLOUT_PENDING) != 0) { 344 /* Leave on existing CPU. */ 345 old_time = c->c_time; 346 c->c_time = to_ticks + occ->cc_ticks; 347 if (c->c_time - old_time < 0) { 348 CIRCQ_REMOVE(&c->c_list); 349 CIRCQ_INSERT(&c->c_list, &occ->cc_todo); 350 } 351 mutex_spin_exit(lock); 352 return; 353 } 354 355 cc = curcpu()->ci_data.cpu_callout; 356 if ((c->c_flags & CALLOUT_BOUND) != 0 || cc == occ || 357 !mutex_tryenter(cc->cc_lock)) { 358 /* Leave on existing CPU. */ 359 c->c_time = to_ticks + occ->cc_ticks; 360 c->c_flags |= CALLOUT_PENDING; 361 CIRCQ_INSERT(&c->c_list, &occ->cc_todo); 362 } else { 363 /* Move to this CPU. */ 364 c->c_cpu = cc; 365 c->c_time = to_ticks + cc->cc_ticks; 366 c->c_flags |= CALLOUT_PENDING; 367 CIRCQ_INSERT(&c->c_list, &cc->cc_todo); 368 mutex_spin_exit(cc->cc_lock); 369 } 370 mutex_spin_exit(lock); 371 } 372 373 /* 374 * callout_reset: 375 * 376 * Reset a callout structure with a new function and argument, and 377 * schedule it to run. 378 */ 379 void 380 callout_reset(callout_t *cs, int to_ticks, void (*func)(void *), void *arg) 381 { 382 callout_impl_t *c = (callout_impl_t *)cs; 383 kmutex_t *lock; 384 385 KASSERT(c->c_magic == CALLOUT_MAGIC); 386 KASSERT(func != NULL); 387 388 lock = callout_lock(c); 389 c->c_func = func; 390 c->c_arg = arg; 391 callout_schedule_locked(c, lock, to_ticks); 392 } 393 394 /* 395 * callout_schedule: 396 * 397 * Schedule a callout to run. The function and argument must 398 * already be set in the callout structure. 399 */ 400 void 401 callout_schedule(callout_t *cs, int to_ticks) 402 { 403 callout_impl_t *c = (callout_impl_t *)cs; 404 kmutex_t *lock; 405 406 KASSERT(c->c_magic == CALLOUT_MAGIC); 407 408 lock = callout_lock(c); 409 callout_schedule_locked(c, lock, to_ticks); 410 } 411 412 /* 413 * callout_stop: 414 * 415 * Try to cancel a pending callout. It may be too late: the callout 416 * could be running on another CPU. If called from interrupt context, 417 * the callout could already be in progress at a lower priority. 418 */ 419 bool 420 callout_stop(callout_t *cs) 421 { 422 callout_impl_t *c = (callout_impl_t *)cs; 423 struct callout_cpu *cc; 424 kmutex_t *lock; 425 bool expired; 426 427 KASSERT(c->c_magic == CALLOUT_MAGIC); 428 429 lock = callout_lock(c); 430 431 if ((c->c_flags & CALLOUT_PENDING) != 0) 432 CIRCQ_REMOVE(&c->c_list); 433 expired = ((c->c_flags & CALLOUT_FIRED) != 0); 434 c->c_flags &= ~(CALLOUT_PENDING|CALLOUT_FIRED); 435 436 cc = c->c_cpu; 437 if (cc->cc_active == c) { 438 /* 439 * This is for non-MPSAFE callouts only. To synchronize 440 * effectively we must be called with kernel_lock held. 441 * It's also taken in callout_softclock. 442 */ 443 cc->cc_cancel = c; 444 } 445 446 mutex_spin_exit(lock); 447 448 return expired; 449 } 450 451 /* 452 * callout_halt: 453 * 454 * Cancel a pending callout. If in-flight, block until it completes. 455 * May not be called from a hard interrupt handler. If the callout 456 * can take locks, the caller of callout_halt() must not hold any of 457 * those locks, otherwise the two could deadlock. If 'interlock' is 458 * non-NULL and we must wait for the callout to complete, it will be 459 * released and re-acquired before returning. 460 */ 461 bool 462 callout_halt(callout_t *cs, void *interlock) 463 { 464 callout_impl_t *c = (callout_impl_t *)cs; 465 struct callout_cpu *cc; 466 struct lwp *l; 467 kmutex_t *lock, *relock; 468 bool expired; 469 470 KASSERT(c->c_magic == CALLOUT_MAGIC); 471 KASSERT(!cpu_intr_p()); 472 473 lock = callout_lock(c); 474 relock = NULL; 475 476 expired = ((c->c_flags & CALLOUT_FIRED) != 0); 477 if ((c->c_flags & CALLOUT_PENDING) != 0) 478 CIRCQ_REMOVE(&c->c_list); 479 c->c_flags &= ~(CALLOUT_PENDING|CALLOUT_FIRED); 480 481 l = curlwp; 482 for (;;) { 483 cc = c->c_cpu; 484 if (__predict_true(cc->cc_active != c || cc->cc_lwp == l)) 485 break; 486 if (interlock != NULL) { 487 /* 488 * Avoid potential scheduler lock order problems by 489 * dropping the interlock without the callout lock 490 * held. 491 */ 492 mutex_spin_exit(lock); 493 mutex_exit(interlock); 494 relock = interlock; 495 interlock = NULL; 496 } else { 497 /* XXX Better to do priority inheritance. */ 498 KASSERT(l->l_wchan == NULL); 499 cc->cc_nwait++; 500 cc->cc_ev_block.ev_count++; 501 l->l_kpriority = true; 502 sleepq_enter(&cc->cc_sleepq, l, cc->cc_lock); 503 sleepq_enqueue(&cc->cc_sleepq, cc, "callout", 504 &sleep_syncobj); 505 sleepq_block(0, false); 506 } 507 lock = callout_lock(c); 508 } 509 510 mutex_spin_exit(lock); 511 if (__predict_false(relock != NULL)) 512 mutex_enter(relock); 513 514 return expired; 515 } 516 517 #ifdef notyet 518 /* 519 * callout_bind: 520 * 521 * Bind a callout so that it will only execute on one CPU. 522 * The callout must be stopped, and must be MPSAFE. 523 * 524 * XXX Disabled for now until it is decided how to handle 525 * offlined CPUs. We may want weak+strong binding. 526 */ 527 void 528 callout_bind(callout_t *cs, struct cpu_info *ci) 529 { 530 callout_impl_t *c = (callout_impl_t *)cs; 531 struct callout_cpu *cc; 532 kmutex_t *lock; 533 534 KASSERT((c->c_flags & CALLOUT_PENDING) == 0); 535 KASSERT(c->c_cpu->cc_active != c); 536 KASSERT(c->c_magic == CALLOUT_MAGIC); 537 KASSERT((c->c_flags & CALLOUT_MPSAFE) != 0); 538 539 lock = callout_lock(c); 540 cc = ci->ci_data.cpu_callout; 541 c->c_flags |= CALLOUT_BOUND; 542 if (c->c_cpu != cc) { 543 /* 544 * Assigning c_cpu effectively unlocks the callout 545 * structure, as we don't hold the new CPU's lock. 546 * Issue memory barrier to prevent accesses being 547 * reordered. 548 */ 549 membar_exit(); 550 c->c_cpu = cc; 551 } 552 mutex_spin_exit(lock); 553 } 554 #endif 555 556 void 557 callout_setfunc(callout_t *cs, void (*func)(void *), void *arg) 558 { 559 callout_impl_t *c = (callout_impl_t *)cs; 560 kmutex_t *lock; 561 562 KASSERT(c->c_magic == CALLOUT_MAGIC); 563 KASSERT(func != NULL); 564 565 lock = callout_lock(c); 566 c->c_func = func; 567 c->c_arg = arg; 568 mutex_spin_exit(lock); 569 } 570 571 bool 572 callout_expired(callout_t *cs) 573 { 574 callout_impl_t *c = (callout_impl_t *)cs; 575 kmutex_t *lock; 576 bool rv; 577 578 KASSERT(c->c_magic == CALLOUT_MAGIC); 579 580 lock = callout_lock(c); 581 rv = ((c->c_flags & CALLOUT_FIRED) != 0); 582 mutex_spin_exit(lock); 583 584 return rv; 585 } 586 587 bool 588 callout_active(callout_t *cs) 589 { 590 callout_impl_t *c = (callout_impl_t *)cs; 591 kmutex_t *lock; 592 bool rv; 593 594 KASSERT(c->c_magic == CALLOUT_MAGIC); 595 596 lock = callout_lock(c); 597 rv = ((c->c_flags & (CALLOUT_PENDING|CALLOUT_FIRED)) != 0); 598 mutex_spin_exit(lock); 599 600 return rv; 601 } 602 603 bool 604 callout_pending(callout_t *cs) 605 { 606 callout_impl_t *c = (callout_impl_t *)cs; 607 kmutex_t *lock; 608 bool rv; 609 610 KASSERT(c->c_magic == CALLOUT_MAGIC); 611 612 lock = callout_lock(c); 613 rv = ((c->c_flags & CALLOUT_PENDING) != 0); 614 mutex_spin_exit(lock); 615 616 return rv; 617 } 618 619 bool 620 callout_invoking(callout_t *cs) 621 { 622 callout_impl_t *c = (callout_impl_t *)cs; 623 kmutex_t *lock; 624 bool rv; 625 626 KASSERT(c->c_magic == CALLOUT_MAGIC); 627 628 lock = callout_lock(c); 629 rv = ((c->c_flags & CALLOUT_INVOKING) != 0); 630 mutex_spin_exit(lock); 631 632 return rv; 633 } 634 635 void 636 callout_ack(callout_t *cs) 637 { 638 callout_impl_t *c = (callout_impl_t *)cs; 639 kmutex_t *lock; 640 641 KASSERT(c->c_magic == CALLOUT_MAGIC); 642 643 lock = callout_lock(c); 644 c->c_flags &= ~CALLOUT_INVOKING; 645 mutex_spin_exit(lock); 646 } 647 648 /* 649 * callout_hardclock: 650 * 651 * Called from hardclock() once every tick. We schedule a soft 652 * interrupt if there is work to be done. 653 */ 654 void 655 callout_hardclock(void) 656 { 657 struct callout_cpu *cc; 658 int needsoftclock, ticks; 659 660 cc = curcpu()->ci_data.cpu_callout; 661 mutex_spin_enter(cc->cc_lock); 662 663 ticks = ++cc->cc_ticks; 664 665 MOVEBUCKET(cc, 0, ticks); 666 if (MASKWHEEL(0, ticks) == 0) { 667 MOVEBUCKET(cc, 1, ticks); 668 if (MASKWHEEL(1, ticks) == 0) { 669 MOVEBUCKET(cc, 2, ticks); 670 if (MASKWHEEL(2, ticks) == 0) 671 MOVEBUCKET(cc, 3, ticks); 672 } 673 } 674 675 needsoftclock = !CIRCQ_EMPTY(&cc->cc_todo); 676 mutex_spin_exit(cc->cc_lock); 677 678 if (needsoftclock) 679 softint_schedule(callout_sih); 680 } 681 682 /* 683 * callout_softclock: 684 * 685 * Soft interrupt handler, scheduled above if there is work to 686 * be done. Callouts are made in soft interrupt context. 687 */ 688 static void 689 callout_softclock(void *v) 690 { 691 callout_impl_t *c; 692 struct callout_cpu *cc; 693 void (*func)(void *); 694 void *arg; 695 int mpsafe, count, ticks, delta; 696 lwp_t *l; 697 698 l = curlwp; 699 KASSERT(l->l_cpu == curcpu()); 700 cc = l->l_cpu->ci_data.cpu_callout; 701 702 mutex_spin_enter(cc->cc_lock); 703 cc->cc_lwp = l; 704 while (!CIRCQ_EMPTY(&cc->cc_todo)) { 705 c = CIRCQ_FIRST(&cc->cc_todo); 706 KASSERT(c->c_magic == CALLOUT_MAGIC); 707 KASSERT(c->c_func != NULL); 708 KASSERT(c->c_cpu == cc); 709 KASSERT((c->c_flags & CALLOUT_PENDING) != 0); 710 KASSERT((c->c_flags & CALLOUT_FIRED) == 0); 711 CIRCQ_REMOVE(&c->c_list); 712 713 /* If due run it, otherwise insert it into the right bucket. */ 714 ticks = cc->cc_ticks; 715 delta = c->c_time - ticks; 716 if (delta > 0) { 717 CIRCQ_INSERT(&c->c_list, BUCKET(cc, delta, c->c_time)); 718 continue; 719 } 720 if (delta < 0) 721 cc->cc_ev_late.ev_count++; 722 723 c->c_flags = (c->c_flags & ~CALLOUT_PENDING) | 724 (CALLOUT_FIRED | CALLOUT_INVOKING); 725 mpsafe = (c->c_flags & CALLOUT_MPSAFE); 726 func = c->c_func; 727 arg = c->c_arg; 728 cc->cc_active = c; 729 730 mutex_spin_exit(cc->cc_lock); 731 KASSERT(func != NULL); 732 if (__predict_false(!mpsafe)) { 733 KERNEL_LOCK(1, NULL); 734 (*func)(arg); 735 KERNEL_UNLOCK_ONE(NULL); 736 } else 737 (*func)(arg); 738 mutex_spin_enter(cc->cc_lock); 739 740 /* 741 * We can't touch 'c' here because it might be 742 * freed already. If LWPs waiting for callout 743 * to complete, awaken them. 744 */ 745 cc->cc_active = NULL; 746 if ((count = cc->cc_nwait) != 0) { 747 cc->cc_nwait = 0; 748 /* sleepq_wake() drops the lock. */ 749 sleepq_wake(&cc->cc_sleepq, cc, count, cc->cc_lock); 750 mutex_spin_enter(cc->cc_lock); 751 } 752 } 753 cc->cc_lwp = NULL; 754 mutex_spin_exit(cc->cc_lock); 755 } 756 757 #ifdef DDB 758 static void 759 db_show_callout_bucket(struct callout_cpu *cc, struct callout_circq *bucket) 760 { 761 callout_impl_t *c; 762 db_expr_t offset; 763 const char *name; 764 static char question[] = "?"; 765 int b; 766 767 if (CIRCQ_EMPTY(bucket)) 768 return; 769 770 for (c = CIRCQ_FIRST(bucket); /*nothing*/; c = CIRCQ_NEXT(&c->c_list)) { 771 db_find_sym_and_offset((db_addr_t)(intptr_t)c->c_func, &name, 772 &offset); 773 name = name ? name : question; 774 b = (bucket - cc->cc_wheel); 775 if (b < 0) 776 b = -WHEELSIZE; 777 db_printf("%9d %2d/%-4d %16lx %s\n", 778 c->c_time - cc->cc_ticks, b / WHEELSIZE, b, 779 (u_long)c->c_arg, name); 780 if (CIRCQ_LAST(&c->c_list, bucket)) 781 break; 782 } 783 } 784 785 void 786 db_show_callout(db_expr_t addr, bool haddr, db_expr_t count, const char *modif) 787 { 788 CPU_INFO_ITERATOR cii; 789 struct callout_cpu *cc; 790 struct cpu_info *ci; 791 int b; 792 793 db_printf("hardclock_ticks now: %d\n", hardclock_ticks); 794 db_printf(" ticks wheel arg func\n"); 795 796 /* 797 * Don't lock the callwheel; all the other CPUs are paused 798 * anyhow, and we might be called in a circumstance where 799 * some other CPU was paused while holding the lock. 800 */ 801 for (CPU_INFO_FOREACH(cii, ci)) { 802 cc = ci->ci_data.cpu_callout; 803 db_show_callout_bucket(cc, &cc->cc_todo); 804 } 805 for (b = 0; b < BUCKETS; b++) { 806 for (CPU_INFO_FOREACH(cii, ci)) { 807 cc = ci->ci_data.cpu_callout; 808 db_show_callout_bucket(cc, &cc->cc_wheel[b]); 809 } 810 } 811 } 812 #endif /* DDB */ 813