1 /* $NetBSD: timer.c,v 1.14 2024/09/22 00:14:08 christos Exp $ */ 2 3 /* 4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 5 * 6 * SPDX-License-Identifier: MPL-2.0 7 * 8 * This Source Code Form is subject to the terms of the Mozilla Public 9 * License, v. 2.0. If a copy of the MPL was not distributed with this 10 * file, you can obtain one at https://mozilla.org/MPL/2.0/. 11 * 12 * See the COPYRIGHT file distributed with this work for additional 13 * information regarding copyright ownership. 14 */ 15 16 /*! \file */ 17 18 #include <stdbool.h> 19 20 #include <isc/app.h> 21 #include <isc/condition.h> 22 #include <isc/heap.h> 23 #include <isc/log.h> 24 #include <isc/magic.h> 25 #include <isc/mem.h> 26 #include <isc/once.h> 27 #include <isc/print.h> 28 #include <isc/refcount.h> 29 #include <isc/result.h> 30 #include <isc/task.h> 31 #include <isc/thread.h> 32 #include <isc/time.h> 33 #include <isc/timer.h> 34 #include <isc/util.h> 35 36 #include "timer_p.h" 37 38 #ifdef ISC_TIMER_TRACE 39 #define XTRACE(s) fprintf(stderr, "%s\n", (s)) 40 #define XTRACEID(s, t) fprintf(stderr, "%s %p\n", (s), (t)) 41 #define XTRACETIME(s, d) \ 42 fprintf(stderr, "%s %u.%09u\n", (s), (d).seconds, (d).nanoseconds) 43 #define XTRACETIME2(s, d, n) \ 44 fprintf(stderr, "%s %u.%09u %u.%09u\n", (s), (d).seconds, \ 45 (d).nanoseconds, (n).seconds, (n).nanoseconds) 46 #define XTRACETIMER(s, t, d) \ 47 fprintf(stderr, "%s %p %u.%09u\n", (s), (t), (d).seconds, \ 48 (d).nanoseconds) 49 #else /* ifdef ISC_TIMER_TRACE */ 50 #define XTRACE(s) 51 #define XTRACEID(s, t) 52 #define XTRACETIME(s, d) 53 #define XTRACETIME2(s, d, n) 54 #define XTRACETIMER(s, t, d) 55 #endif /* ISC_TIMER_TRACE */ 56 57 #define TIMER_MAGIC ISC_MAGIC('T', 'I', 'M', 'R') 58 #define VALID_TIMER(t) ISC_MAGIC_VALID(t, TIMER_MAGIC) 59 60 struct isc_timer { 61 /*! Not locked. */ 62 unsigned int magic; 63 isc_timermgr_t *manager; 64 isc_mutex_t lock; 65 /*! Locked by timer lock. */ 66 isc_time_t idle; 67 ISC_LIST(isc_timerevent_t) active; 68 /*! Locked by manager lock. */ 69 isc_timertype_t type; 70 isc_time_t expires; 71 isc_interval_t interval; 72 isc_task_t *task; 73 isc_taskaction_t action; 74 void *arg; 75 unsigned int index; 76 isc_time_t due; 77 LINK(isc_timer_t) link; 78 }; 79 80 #define TIMER_MANAGER_MAGIC ISC_MAGIC('T', 'I', 'M', 'M') 81 #define VALID_MANAGER(m) ISC_MAGIC_VALID(m, TIMER_MANAGER_MAGIC) 82 83 struct isc_timermgr { 84 /* Not locked. */ 85 unsigned int magic; 86 isc_mem_t *mctx; 87 isc_mutex_t lock; 88 /* Locked by manager lock. */ 89 bool done; 90 LIST(isc_timer_t) timers; 91 unsigned int nscheduled; 92 isc_time_t due; 93 isc_condition_t wakeup; 94 isc_thread_t thread; 95 isc_heap_t *heap; 96 }; 97 98 void 99 isc_timermgr_poke(isc_timermgr_t *manager); 100 101 static inline isc_result_t 102 schedule(isc_timer_t *timer, isc_time_t *now, bool signal_ok) { 103 isc_timermgr_t *manager; 104 isc_time_t due; 105 106 /*! 107 * Note: the caller must ensure locking. 108 */ 109 110 REQUIRE(timer->type != isc_timertype_inactive); 111 112 manager = timer->manager; 113 114 /* 115 * Compute the new due time. 116 */ 117 if (timer->type != isc_timertype_once) { 118 isc_result_t result = isc_time_add(now, &timer->interval, &due); 119 if (result != ISC_R_SUCCESS) { 120 return (result); 121 } 122 if (timer->type == isc_timertype_limited && 123 isc_time_compare(&timer->expires, &due) < 0) 124 { 125 due = timer->expires; 126 } 127 } else { 128 if (isc_time_isepoch(&timer->idle)) { 129 due = timer->expires; 130 } else if (isc_time_isepoch(&timer->expires)) { 131 due = timer->idle; 132 } else if (isc_time_compare(&timer->idle, &timer->expires) < 0) 133 { 134 due = timer->idle; 135 } else { 136 due = timer->expires; 137 } 138 } 139 140 /* 141 * Schedule the timer. 142 */ 143 144 if (timer->index > 0) { 145 /* 146 * Already scheduled. 147 */ 148 int cmp = isc_time_compare(&due, &timer->due); 149 timer->due = due; 150 switch (cmp) { 151 case -1: 152 isc_heap_increased(manager->heap, timer->index); 153 break; 154 case 1: 155 isc_heap_decreased(manager->heap, timer->index); 156 break; 157 case 0: 158 /* Nothing to do. */ 159 break; 160 } 161 } else { 162 timer->due = due; 163 isc_heap_insert(manager->heap, timer); 164 manager->nscheduled++; 165 } 166 167 XTRACETIMER("schedule", timer, due); 168 169 /* 170 * If this timer is at the head of the queue, we need to ensure 171 * that we won't miss it if it has a more recent due time than 172 * the current "next" timer. We do this either by waking up the 173 * run thread, or explicitly setting the value in the manager. 174 */ 175 176 if (timer->index == 1 && signal_ok) { 177 XTRACE("signal (schedule)"); 178 SIGNAL(&manager->wakeup); 179 } 180 181 return (ISC_R_SUCCESS); 182 } 183 184 static inline void 185 deschedule(isc_timer_t *timer) { 186 isc_timermgr_t *manager; 187 188 /* 189 * The caller must ensure locking. 190 */ 191 192 manager = timer->manager; 193 if (timer->index > 0) { 194 bool need_wakeup = false; 195 if (timer->index == 1) { 196 need_wakeup = true; 197 } 198 isc_heap_delete(manager->heap, timer->index); 199 timer->index = 0; 200 INSIST(manager->nscheduled > 0); 201 manager->nscheduled--; 202 if (need_wakeup) { 203 XTRACE("signal (deschedule)"); 204 SIGNAL(&manager->wakeup); 205 } 206 } 207 } 208 209 static void 210 timerevent_unlink(isc_timer_t *timer, isc_timerevent_t *event) { 211 REQUIRE(ISC_LINK_LINKED(event, ev_timerlink)); 212 ISC_LIST_UNLINK(timer->active, event, ev_timerlink); 213 } 214 215 static void 216 timerevent_destroy(isc_event_t *event0) { 217 isc_timer_t *timer = event0->ev_destroy_arg; 218 isc_timerevent_t *event = (isc_timerevent_t *)event0; 219 220 LOCK(&timer->lock); 221 if (ISC_LINK_LINKED(event, ev_timerlink)) { 222 /* The event was unlinked via timer_purge() */ 223 timerevent_unlink(timer, event); 224 } 225 UNLOCK(&timer->lock); 226 227 isc_mem_put(timer->manager->mctx, event, event0->ev_size); 228 } 229 230 static void 231 timer_purge(isc_timer_t *timer) { 232 isc_timerevent_t *event = NULL; 233 234 while ((event = ISC_LIST_HEAD(timer->active)) != NULL) { 235 timerevent_unlink(timer, event); 236 bool purged = isc_task_purgeevent(timer->task, 237 (isc_event_t *)event); 238 UNLOCK(&timer->lock); 239 #if defined(UNIT_TESTING) 240 usleep(100); 241 #endif 242 if (purged) { 243 isc_event_free((isc_event_t **)&event); 244 } else { 245 /* 246 * The event was processed while we were trying to 247 * purge it. The event's action is responsible for 248 * calling isc_event_free(), which in turn will call 249 * event->ev_destroy() (timerevent_destroy() here), 250 * which will unlink and destroy it. 251 */ 252 } 253 LOCK(&timer->lock); 254 } 255 } 256 257 isc_result_t 258 isc_timer_create(isc_timermgr_t *manager, isc_timertype_t type, 259 const isc_time_t *expires, const isc_interval_t *interval, 260 isc_task_t *task, isc_taskaction_t action, void *arg, 261 isc_timer_t **timerp) { 262 REQUIRE(VALID_MANAGER(manager)); 263 REQUIRE(task != NULL); 264 REQUIRE(action != NULL); 265 266 isc_timer_t *timer; 267 isc_result_t result; 268 isc_time_t now; 269 270 /* 271 * Create a new 'type' timer managed by 'manager'. The timers 272 * parameters are specified by 'expires' and 'interval'. Events 273 * will be posted to 'task' and when dispatched 'action' will be 274 * called with 'arg' as the arg value. The new timer is returned 275 * in 'timerp'. 276 */ 277 if (expires == NULL) { 278 expires = isc_time_epoch; 279 } 280 if (interval == NULL) { 281 interval = isc_interval_zero; 282 } 283 REQUIRE(type == isc_timertype_inactive || 284 !(isc_time_isepoch(expires) && isc_interval_iszero(interval))); 285 REQUIRE(timerp != NULL && *timerp == NULL); 286 REQUIRE(type != isc_timertype_limited || 287 !(isc_time_isepoch(expires) || isc_interval_iszero(interval))); 288 289 /* 290 * Get current time. 291 */ 292 if (type != isc_timertype_inactive) { 293 TIME_NOW(&now); 294 } else { 295 /* 296 * We don't have to do this, but it keeps the compiler from 297 * complaining about "now" possibly being used without being 298 * set, even though it will never actually happen. 299 */ 300 isc_time_settoepoch(&now); 301 } 302 303 timer = isc_mem_get(manager->mctx, sizeof(*timer)); 304 305 timer->manager = manager; 306 307 if (type == isc_timertype_once && !isc_interval_iszero(interval)) { 308 result = isc_time_add(&now, interval, &timer->idle); 309 if (result != ISC_R_SUCCESS) { 310 isc_mem_put(manager->mctx, timer, sizeof(*timer)); 311 return (result); 312 } 313 } else { 314 isc_time_settoepoch(&timer->idle); 315 } 316 317 timer->type = type; 318 timer->expires = *expires; 319 timer->interval = *interval; 320 timer->task = NULL; 321 isc_task_attach(task, &timer->task); 322 timer->action = action; 323 /* 324 * Removing the const attribute from "arg" is the best of two 325 * evils here. If the timer->arg member is made const, then 326 * it affects a great many recipients of the timer event 327 * which did not pass in an "arg" that was truly const. 328 * Changing isc_timer_create() to not have "arg" prototyped as const, 329 * though, can cause compilers warnings for calls that *do* 330 * have a truly const arg. The caller will have to carefully 331 * keep track of whether arg started as a true const. 332 */ 333 DE_CONST(arg, timer->arg); 334 timer->index = 0; 335 isc_mutex_init(&timer->lock); 336 ISC_LINK_INIT(timer, link); 337 338 ISC_LIST_INIT(timer->active); 339 340 timer->magic = TIMER_MAGIC; 341 342 LOCK(&manager->lock); 343 344 /* 345 * Note we don't have to lock the timer like we normally would because 346 * there are no external references to it yet. 347 */ 348 349 if (type != isc_timertype_inactive) { 350 result = schedule(timer, &now, true); 351 } else { 352 result = ISC_R_SUCCESS; 353 } 354 if (result == ISC_R_SUCCESS) { 355 *timerp = timer; 356 APPEND(manager->timers, timer, link); 357 } 358 359 UNLOCK(&manager->lock); 360 361 if (result != ISC_R_SUCCESS) { 362 timer->magic = 0; 363 isc_mutex_destroy(&timer->lock); 364 isc_task_detach(&timer->task); 365 isc_mem_put(manager->mctx, timer, sizeof(*timer)); 366 return (result); 367 } 368 369 return (ISC_R_SUCCESS); 370 } 371 372 isc_result_t 373 isc_timer_reset(isc_timer_t *timer, isc_timertype_t type, 374 const isc_time_t *expires, const isc_interval_t *interval, 375 bool purge) { 376 isc_time_t now; 377 isc_timermgr_t *manager; 378 isc_result_t result; 379 380 /* 381 * Change the timer's type, expires, and interval values to the given 382 * values. If 'purge' is true, any pending events from this timer 383 * are purged from its task's event queue. 384 */ 385 386 REQUIRE(VALID_TIMER(timer)); 387 manager = timer->manager; 388 REQUIRE(VALID_MANAGER(manager)); 389 390 if (expires == NULL) { 391 expires = isc_time_epoch; 392 } 393 if (interval == NULL) { 394 interval = isc_interval_zero; 395 } 396 REQUIRE(type == isc_timertype_inactive || 397 !(isc_time_isepoch(expires) && isc_interval_iszero(interval))); 398 REQUIRE(type != isc_timertype_limited || 399 !(isc_time_isepoch(expires) || isc_interval_iszero(interval))); 400 401 /* 402 * Get current time. 403 */ 404 if (type != isc_timertype_inactive) { 405 TIME_NOW(&now); 406 } else { 407 /* 408 * We don't have to do this, but it keeps the compiler from 409 * complaining about "now" possibly being used without being 410 * set, even though it will never actually happen. 411 */ 412 isc_time_settoepoch(&now); 413 } 414 415 LOCK(&manager->lock); 416 LOCK(&timer->lock); 417 418 if (purge) { 419 timer_purge(timer); 420 } 421 timer->type = type; 422 timer->expires = *expires; 423 timer->interval = *interval; 424 if (type == isc_timertype_once && !isc_interval_iszero(interval)) { 425 result = isc_time_add(&now, interval, &timer->idle); 426 } else { 427 isc_time_settoepoch(&timer->idle); 428 result = ISC_R_SUCCESS; 429 } 430 431 if (result == ISC_R_SUCCESS) { 432 if (type == isc_timertype_inactive) { 433 deschedule(timer); 434 result = ISC_R_SUCCESS; 435 } else { 436 result = schedule(timer, &now, true); 437 } 438 } 439 440 UNLOCK(&timer->lock); 441 UNLOCK(&manager->lock); 442 443 return (result); 444 } 445 446 isc_timertype_t 447 isc_timer_gettype(isc_timer_t *timer) { 448 isc_timertype_t t; 449 450 REQUIRE(VALID_TIMER(timer)); 451 452 LOCK(&timer->lock); 453 t = timer->type; 454 UNLOCK(&timer->lock); 455 456 return (t); 457 } 458 459 isc_result_t 460 isc_timer_touch(isc_timer_t *timer) { 461 isc_result_t result; 462 isc_time_t now; 463 464 /* 465 * Set the last-touched time of 'timer' to the current time. 466 */ 467 468 REQUIRE(VALID_TIMER(timer)); 469 470 LOCK(&timer->lock); 471 472 /* 473 * We'd like to 474 * 475 * REQUIRE(timer->type == isc_timertype_once); 476 * 477 * but we cannot without locking the manager lock too, which we 478 * don't want to do. 479 */ 480 481 TIME_NOW(&now); 482 result = isc_time_add(&now, &timer->interval, &timer->idle); 483 484 UNLOCK(&timer->lock); 485 486 return (result); 487 } 488 489 void 490 isc_timer_purge(isc_timer_t *timer) { 491 REQUIRE(VALID_TIMER(timer)); 492 493 LOCK(&timer->lock); 494 timer_purge(timer); 495 UNLOCK(&timer->lock); 496 } 497 498 void 499 isc_timer_destroy(isc_timer_t **timerp) { 500 isc_timer_t *timer = NULL; 501 isc_timermgr_t *manager = NULL; 502 503 REQUIRE(timerp != NULL && VALID_TIMER(*timerp)); 504 505 timer = *timerp; 506 *timerp = NULL; 507 508 manager = timer->manager; 509 510 LOCK(&manager->lock); 511 512 LOCK(&timer->lock); 513 timer_purge(timer); 514 deschedule(timer); 515 UNLOCK(&timer->lock); 516 517 UNLINK(manager->timers, timer, link); 518 519 UNLOCK(&manager->lock); 520 521 isc_task_detach(&timer->task); 522 isc_mutex_destroy(&timer->lock); 523 timer->magic = 0; 524 isc_mem_put(manager->mctx, timer, sizeof(*timer)); 525 } 526 527 static void 528 timer_post_event(isc_timermgr_t *manager, isc_timer_t *timer, 529 isc_eventtype_t type) { 530 isc_timerevent_t *event; 531 XTRACEID("posting", timer); 532 533 event = (isc_timerevent_t *)isc_event_allocate( 534 manager->mctx, timer, type, timer->action, timer->arg, 535 sizeof(*event)); 536 537 ISC_LINK_INIT(event, ev_timerlink); 538 ((isc_event_t *)event)->ev_destroy = timerevent_destroy; 539 ((isc_event_t *)event)->ev_destroy_arg = timer; 540 541 event->due = timer->due; 542 543 LOCK(&timer->lock); 544 ISC_LIST_APPEND(timer->active, event, ev_timerlink); 545 UNLOCK(&timer->lock); 546 547 isc_task_send(timer->task, ISC_EVENT_PTR(&event)); 548 } 549 550 static void 551 dispatch(isc_timermgr_t *manager, isc_time_t *now) { 552 bool done = false, post_event, need_schedule; 553 isc_eventtype_t type = 0; 554 isc_timer_t *timer; 555 isc_result_t result; 556 bool idle; 557 558 /*! 559 * The caller must be holding the manager lock. 560 */ 561 562 while (manager->nscheduled > 0 && !done) { 563 timer = isc_heap_element(manager->heap, 1); 564 INSIST(timer != NULL && timer->type != isc_timertype_inactive); 565 if (isc_time_compare(now, &timer->due) >= 0) { 566 if (timer->type == isc_timertype_ticker) { 567 type = ISC_TIMEREVENT_TICK; 568 post_event = true; 569 need_schedule = true; 570 } else if (timer->type == isc_timertype_limited) { 571 int cmp; 572 cmp = isc_time_compare(now, &timer->expires); 573 if (cmp >= 0) { 574 type = ISC_TIMEREVENT_LIFE; 575 post_event = true; 576 need_schedule = false; 577 } else { 578 type = ISC_TIMEREVENT_TICK; 579 post_event = true; 580 need_schedule = true; 581 } 582 } else if (!isc_time_isepoch(&timer->expires) && 583 isc_time_compare(now, &timer->expires) >= 0) 584 { 585 type = ISC_TIMEREVENT_LIFE; 586 post_event = true; 587 need_schedule = false; 588 } else { 589 idle = false; 590 591 LOCK(&timer->lock); 592 if (!isc_time_isepoch(&timer->idle) && 593 isc_time_compare(now, &timer->idle) >= 0) 594 { 595 idle = true; 596 } 597 UNLOCK(&timer->lock); 598 if (idle) { 599 type = ISC_TIMEREVENT_IDLE; 600 post_event = true; 601 need_schedule = false; 602 } else { 603 /* 604 * Idle timer has been touched; 605 * reschedule. 606 */ 607 XTRACEID("idle reschedule", timer); 608 post_event = false; 609 need_schedule = true; 610 } 611 } 612 613 if (post_event) { 614 timer_post_event(manager, timer, type); 615 } 616 617 timer->index = 0; 618 isc_heap_delete(manager->heap, 1); 619 manager->nscheduled--; 620 621 if (need_schedule) { 622 result = schedule(timer, now, false); 623 if (result != ISC_R_SUCCESS) { 624 UNEXPECTED_ERROR( 625 "couldn't schedule timer: %s", 626 isc_result_totext(result)); 627 } 628 } 629 } else { 630 manager->due = timer->due; 631 done = true; 632 } 633 } 634 } 635 636 static isc_threadresult_t 637 run(void *uap) { 638 isc_timermgr_t *manager = uap; 639 isc_time_t now; 640 isc_result_t result; 641 642 LOCK(&manager->lock); 643 while (!manager->done) { 644 TIME_NOW(&now); 645 646 XTRACETIME("running", now); 647 648 dispatch(manager, &now); 649 650 if (manager->nscheduled > 0) { 651 XTRACETIME2("waituntil", manager->due, now); 652 result = WAITUNTIL(&manager->wakeup, &manager->lock, 653 &manager->due); 654 INSIST(result == ISC_R_SUCCESS || 655 result == ISC_R_TIMEDOUT); 656 } else { 657 XTRACETIME("wait", now); 658 WAIT(&manager->wakeup, &manager->lock); 659 } 660 XTRACE("wakeup"); 661 } 662 UNLOCK(&manager->lock); 663 664 return ((isc_threadresult_t)0); 665 } 666 667 static bool 668 sooner(void *v1, void *v2) { 669 isc_timer_t *t1, *t2; 670 671 t1 = v1; 672 t2 = v2; 673 REQUIRE(VALID_TIMER(t1)); 674 REQUIRE(VALID_TIMER(t2)); 675 676 if (isc_time_compare(&t1->due, &t2->due) < 0) { 677 return (true); 678 } 679 return (false); 680 } 681 682 static void 683 set_index(void *what, unsigned int index) { 684 isc_timer_t *timer; 685 686 REQUIRE(VALID_TIMER(what)); 687 timer = what; 688 689 timer->index = index; 690 } 691 692 isc_result_t 693 isc__timermgr_create(isc_mem_t *mctx, isc_timermgr_t **managerp) { 694 isc_timermgr_t *manager; 695 696 /* 697 * Create a timer manager. 698 */ 699 700 REQUIRE(managerp != NULL && *managerp == NULL); 701 702 manager = isc_mem_get(mctx, sizeof(*manager)); 703 704 manager->magic = TIMER_MANAGER_MAGIC; 705 manager->mctx = NULL; 706 manager->done = false; 707 INIT_LIST(manager->timers); 708 manager->nscheduled = 0; 709 isc_time_settoepoch(&manager->due); 710 manager->heap = NULL; 711 isc_heap_create(mctx, sooner, set_index, 0, &manager->heap); 712 isc_mutex_init(&manager->lock); 713 isc_mem_attach(mctx, &manager->mctx); 714 isc_condition_init(&manager->wakeup); 715 isc_thread_create(run, manager, &manager->thread); 716 isc_thread_setname(manager->thread, "timer"); 717 718 *managerp = manager; 719 720 return (ISC_R_SUCCESS); 721 } 722 723 void 724 isc_timermgr_poke(isc_timermgr_t *manager) { 725 REQUIRE(VALID_MANAGER(manager)); 726 727 SIGNAL(&manager->wakeup); 728 } 729 730 void 731 isc__timermgr_destroy(isc_timermgr_t **managerp) { 732 isc_timermgr_t *manager; 733 734 /* 735 * Destroy a timer manager. 736 */ 737 738 REQUIRE(managerp != NULL); 739 manager = *managerp; 740 REQUIRE(VALID_MANAGER(manager)); 741 742 LOCK(&manager->lock); 743 744 REQUIRE(EMPTY(manager->timers)); 745 manager->done = true; 746 747 XTRACE("signal (destroy)"); 748 SIGNAL(&manager->wakeup); 749 750 UNLOCK(&manager->lock); 751 752 /* 753 * Wait for thread to exit. 754 */ 755 isc_thread_join(manager->thread, NULL); 756 757 /* 758 * Clean up. 759 */ 760 (void)isc_condition_destroy(&manager->wakeup); 761 isc_mutex_destroy(&manager->lock); 762 isc_heap_destroy(&manager->heap); 763 manager->magic = 0; 764 isc_mem_putanddetach(&manager->mctx, manager, sizeof(*manager)); 765 766 *managerp = NULL; 767 } 768