1/* $NetBSD: timer.c,v 1.13 2024/02/21 22:52:29 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 60struct 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 83struct 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 98void 99isc_timermgr_poke(isc_timermgr_t *manager); 100 101static inline isc_result_t 102schedule(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 184static inline void 185deschedule(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 209static void 210timerevent_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 215static void 216timerevent_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 230static void 231timer_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 UNLOCK(&timer->lock); 237 (void)isc_task_purgeevent(timer->task, (isc_event_t *)event); 238 LOCK(&timer->lock); 239 } 240} 241 242isc_result_t 243isc_timer_create(isc_timermgr_t *manager, isc_timertype_t type, 244 const isc_time_t *expires, const isc_interval_t *interval, 245 isc_task_t *task, isc_taskaction_t action, void *arg, 246 isc_timer_t **timerp) { 247 REQUIRE(VALID_MANAGER(manager)); 248 REQUIRE(task != NULL); 249 REQUIRE(action != NULL); 250 251 isc_timer_t *timer; 252 isc_result_t result; 253 isc_time_t now; 254 255 /* 256 * Create a new 'type' timer managed by 'manager'. The timers 257 * parameters are specified by 'expires' and 'interval'. Events 258 * will be posted to 'task' and when dispatched 'action' will be 259 * called with 'arg' as the arg value. The new timer is returned 260 * in 'timerp'. 261 */ 262 if (expires == NULL) { 263 expires = isc_time_epoch; 264 } 265 if (interval == NULL) { 266 interval = isc_interval_zero; 267 } 268 REQUIRE(type == isc_timertype_inactive || 269 !(isc_time_isepoch(expires) && isc_interval_iszero(interval))); 270 REQUIRE(timerp != NULL && *timerp == NULL); 271 REQUIRE(type != isc_timertype_limited || 272 !(isc_time_isepoch(expires) || isc_interval_iszero(interval))); 273 274 /* 275 * Get current time. 276 */ 277 if (type != isc_timertype_inactive) { 278 TIME_NOW(&now); 279 } else { 280 /* 281 * We don't have to do this, but it keeps the compiler from 282 * complaining about "now" possibly being used without being 283 * set, even though it will never actually happen. 284 */ 285 isc_time_settoepoch(&now); 286 } 287 288 timer = isc_mem_get(manager->mctx, sizeof(*timer)); 289 290 timer->manager = manager; 291 292 if (type == isc_timertype_once && !isc_interval_iszero(interval)) { 293 result = isc_time_add(&now, interval, &timer->idle); 294 if (result != ISC_R_SUCCESS) { 295 isc_mem_put(manager->mctx, timer, sizeof(*timer)); 296 return (result); 297 } 298 } else { 299 isc_time_settoepoch(&timer->idle); 300 } 301 302 timer->type = type; 303 timer->expires = *expires; 304 timer->interval = *interval; 305 timer->task = NULL; 306 isc_task_attach(task, &timer->task); 307 timer->action = action; 308 /* 309 * Removing the const attribute from "arg" is the best of two 310 * evils here. If the timer->arg member is made const, then 311 * it affects a great many recipients of the timer event 312 * which did not pass in an "arg" that was truly const. 313 * Changing isc_timer_create() to not have "arg" prototyped as const, 314 * though, can cause compilers warnings for calls that *do* 315 * have a truly const arg. The caller will have to carefully 316 * keep track of whether arg started as a true const. 317 */ 318 DE_CONST(arg, timer->arg); 319 timer->index = 0; 320 isc_mutex_init(&timer->lock); 321 ISC_LINK_INIT(timer, link); 322 323 ISC_LIST_INIT(timer->active); 324 325 timer->magic = TIMER_MAGIC; 326 327 LOCK(&manager->lock); 328 329 /* 330 * Note we don't have to lock the timer like we normally would because 331 * there are no external references to it yet. 332 */ 333 334 if (type != isc_timertype_inactive) { 335 result = schedule(timer, &now, true); 336 } else { 337 result = ISC_R_SUCCESS; 338 } 339 if (result == ISC_R_SUCCESS) { 340 *timerp = timer; 341 APPEND(manager->timers, timer, link); 342 } 343 344 UNLOCK(&manager->lock); 345 346 if (result != ISC_R_SUCCESS) { 347 timer->magic = 0; 348 isc_mutex_destroy(&timer->lock); 349 isc_task_detach(&timer->task); 350 isc_mem_put(manager->mctx, timer, sizeof(*timer)); 351 return (result); 352 } 353 354 return (ISC_R_SUCCESS); 355} 356 357isc_result_t 358isc_timer_reset(isc_timer_t *timer, isc_timertype_t type, 359 const isc_time_t *expires, const isc_interval_t *interval, 360 bool purge) { 361 isc_time_t now; 362 isc_timermgr_t *manager; 363 isc_result_t result; 364 365 /* 366 * Change the timer's type, expires, and interval values to the given 367 * values. If 'purge' is true, any pending events from this timer 368 * are purged from its task's event queue. 369 */ 370 371 REQUIRE(VALID_TIMER(timer)); 372 manager = timer->manager; 373 REQUIRE(VALID_MANAGER(manager)); 374 375 if (expires == NULL) { 376 expires = isc_time_epoch; 377 } 378 if (interval == NULL) { 379 interval = isc_interval_zero; 380 } 381 REQUIRE(type == isc_timertype_inactive || 382 !(isc_time_isepoch(expires) && isc_interval_iszero(interval))); 383 REQUIRE(type != isc_timertype_limited || 384 !(isc_time_isepoch(expires) || isc_interval_iszero(interval))); 385 386 /* 387 * Get current time. 388 */ 389 if (type != isc_timertype_inactive) { 390 TIME_NOW(&now); 391 } else { 392 /* 393 * We don't have to do this, but it keeps the compiler from 394 * complaining about "now" possibly being used without being 395 * set, even though it will never actually happen. 396 */ 397 isc_time_settoepoch(&now); 398 } 399 400 LOCK(&manager->lock); 401 LOCK(&timer->lock); 402 403 if (purge) { 404 timer_purge(timer); 405 } 406 timer->type = type; 407 timer->expires = *expires; 408 timer->interval = *interval; 409 if (type == isc_timertype_once && !isc_interval_iszero(interval)) { 410 result = isc_time_add(&now, interval, &timer->idle); 411 } else { 412 isc_time_settoepoch(&timer->idle); 413 result = ISC_R_SUCCESS; 414 } 415 416 if (result == ISC_R_SUCCESS) { 417 if (type == isc_timertype_inactive) { 418 deschedule(timer); 419 result = ISC_R_SUCCESS; 420 } else { 421 result = schedule(timer, &now, true); 422 } 423 } 424 425 UNLOCK(&timer->lock); 426 UNLOCK(&manager->lock); 427 428 return (result); 429} 430 431isc_timertype_t 432isc_timer_gettype(isc_timer_t *timer) { 433 isc_timertype_t t; 434 435 REQUIRE(VALID_TIMER(timer)); 436 437 LOCK(&timer->lock); 438 t = timer->type; 439 UNLOCK(&timer->lock); 440 441 return (t); 442} 443 444isc_result_t 445isc_timer_touch(isc_timer_t *timer) { 446 isc_result_t result; 447 isc_time_t now; 448 449 /* 450 * Set the last-touched time of 'timer' to the current time. 451 */ 452 453 REQUIRE(VALID_TIMER(timer)); 454 455 LOCK(&timer->lock); 456 457 /* 458 * We'd like to 459 * 460 * REQUIRE(timer->type == isc_timertype_once); 461 * 462 * but we cannot without locking the manager lock too, which we 463 * don't want to do. 464 */ 465 466 TIME_NOW(&now); 467 result = isc_time_add(&now, &timer->interval, &timer->idle); 468 469 UNLOCK(&timer->lock); 470 471 return (result); 472} 473 474void 475isc_timer_destroy(isc_timer_t **timerp) { 476 isc_timer_t *timer = NULL; 477 isc_timermgr_t *manager = NULL; 478 479 REQUIRE(timerp != NULL && VALID_TIMER(*timerp)); 480 481 timer = *timerp; 482 *timerp = NULL; 483 484 manager = timer->manager; 485 486 LOCK(&manager->lock); 487 488 LOCK(&timer->lock); 489 timer_purge(timer); 490 deschedule(timer); 491 UNLOCK(&timer->lock); 492 493 UNLINK(manager->timers, timer, link); 494 495 UNLOCK(&manager->lock); 496 497 isc_task_detach(&timer->task); 498 isc_mutex_destroy(&timer->lock); 499 timer->magic = 0; 500 isc_mem_put(manager->mctx, timer, sizeof(*timer)); 501} 502 503static void 504timer_post_event(isc_timermgr_t *manager, isc_timer_t *timer, 505 isc_eventtype_t type) { 506 isc_timerevent_t *event; 507 XTRACEID("posting", timer); 508 509 event = (isc_timerevent_t *)isc_event_allocate( 510 manager->mctx, timer, type, timer->action, timer->arg, 511 sizeof(*event)); 512 513 ISC_LINK_INIT(event, ev_timerlink); 514 ((isc_event_t *)event)->ev_destroy = timerevent_destroy; 515 ((isc_event_t *)event)->ev_destroy_arg = timer; 516 517 event->due = timer->due; 518 519 LOCK(&timer->lock); 520 ISC_LIST_APPEND(timer->active, event, ev_timerlink); 521 UNLOCK(&timer->lock); 522 523 isc_task_send(timer->task, ISC_EVENT_PTR(&event)); 524} 525 526static void 527dispatch(isc_timermgr_t *manager, isc_time_t *now) { 528 bool done = false, post_event, need_schedule; 529 isc_eventtype_t type = 0; 530 isc_timer_t *timer; 531 isc_result_t result; 532 bool idle; 533 534 /*! 535 * The caller must be holding the manager lock. 536 */ 537 538 while (manager->nscheduled > 0 && !done) { 539 timer = isc_heap_element(manager->heap, 1); 540 INSIST(timer != NULL && timer->type != isc_timertype_inactive); 541 if (isc_time_compare(now, &timer->due) >= 0) { 542 if (timer->type == isc_timertype_ticker) { 543 type = ISC_TIMEREVENT_TICK; 544 post_event = true; 545 need_schedule = true; 546 } else if (timer->type == isc_timertype_limited) { 547 int cmp; 548 cmp = isc_time_compare(now, &timer->expires); 549 if (cmp >= 0) { 550 type = ISC_TIMEREVENT_LIFE; 551 post_event = true; 552 need_schedule = false; 553 } else { 554 type = ISC_TIMEREVENT_TICK; 555 post_event = true; 556 need_schedule = true; 557 } 558 } else if (!isc_time_isepoch(&timer->expires) && 559 isc_time_compare(now, &timer->expires) >= 0) 560 { 561 type = ISC_TIMEREVENT_LIFE; 562 post_event = true; 563 need_schedule = false; 564 } else { 565 idle = false; 566 567 LOCK(&timer->lock); 568 if (!isc_time_isepoch(&timer->idle) && 569 isc_time_compare(now, &timer->idle) >= 0) 570 { 571 idle = true; 572 } 573 UNLOCK(&timer->lock); 574 if (idle) { 575 type = ISC_TIMEREVENT_IDLE; 576 post_event = true; 577 need_schedule = false; 578 } else { 579 /* 580 * Idle timer has been touched; 581 * reschedule. 582 */ 583 XTRACEID("idle reschedule", timer); 584 post_event = false; 585 need_schedule = true; 586 } 587 } 588 589 if (post_event) { 590 timer_post_event(manager, timer, type); 591 } 592 593 timer->index = 0; 594 isc_heap_delete(manager->heap, 1); 595 manager->nscheduled--; 596 597 if (need_schedule) { 598 result = schedule(timer, now, false); 599 if (result != ISC_R_SUCCESS) { 600 UNEXPECTED_ERROR( 601 "couldn't schedule timer: %s", 602 isc_result_totext(result)); 603 } 604 } 605 } else { 606 manager->due = timer->due; 607 done = true; 608 } 609 } 610} 611 612static isc_threadresult_t 613run(void *uap) { 614 isc_timermgr_t *manager = uap; 615 isc_time_t now; 616 isc_result_t result; 617 618 LOCK(&manager->lock); 619 while (!manager->done) { 620 TIME_NOW(&now); 621 622 XTRACETIME("running", now); 623 624 dispatch(manager, &now); 625 626 if (manager->nscheduled > 0) { 627 XTRACETIME2("waituntil", manager->due, now); 628 result = WAITUNTIL(&manager->wakeup, &manager->lock, 629 &manager->due); 630 INSIST(result == ISC_R_SUCCESS || 631 result == ISC_R_TIMEDOUT); 632 } else { 633 XTRACETIME("wait", now); 634 WAIT(&manager->wakeup, &manager->lock); 635 } 636 XTRACE("wakeup"); 637 } 638 UNLOCK(&manager->lock); 639 640 return ((isc_threadresult_t)0); 641} 642 643static bool 644sooner(void *v1, void *v2) { 645 isc_timer_t *t1, *t2; 646 647 t1 = v1; 648 t2 = v2; 649 REQUIRE(VALID_TIMER(t1)); 650 REQUIRE(VALID_TIMER(t2)); 651 652 if (isc_time_compare(&t1->due, &t2->due) < 0) { 653 return (true); 654 } 655 return (false); 656} 657 658static void 659set_index(void *what, unsigned int index) { 660 isc_timer_t *timer; 661 662 REQUIRE(VALID_TIMER(what)); 663 timer = what; 664 665 timer->index = index; 666} 667 668isc_result_t 669isc__timermgr_create(isc_mem_t *mctx, isc_timermgr_t **managerp) { 670 isc_timermgr_t *manager; 671 672 /* 673 * Create a timer manager. 674 */ 675 676 REQUIRE(managerp != NULL && *managerp == NULL); 677 678 manager = isc_mem_get(mctx, sizeof(*manager)); 679 680 manager->magic = TIMER_MANAGER_MAGIC; 681 manager->mctx = NULL; 682 manager->done = false; 683 INIT_LIST(manager->timers); 684 manager->nscheduled = 0; 685 isc_time_settoepoch(&manager->due); 686 manager->heap = NULL; 687 isc_heap_create(mctx, sooner, set_index, 0, &manager->heap); 688 isc_mutex_init(&manager->lock); 689 isc_mem_attach(mctx, &manager->mctx); 690 isc_condition_init(&manager->wakeup); 691 isc_thread_create(run, manager, &manager->thread); 692 isc_thread_setname(manager->thread, "timer"); 693 694 *managerp = manager; 695 696 return (ISC_R_SUCCESS); 697} 698 699void 700isc_timermgr_poke(isc_timermgr_t *manager) { 701 REQUIRE(VALID_MANAGER(manager)); 702 703 SIGNAL(&manager->wakeup); 704} 705 706void 707isc__timermgr_destroy(isc_timermgr_t **managerp) { 708 isc_timermgr_t *manager; 709 710 /* 711 * Destroy a timer manager. 712 */ 713 714 REQUIRE(managerp != NULL); 715 manager = *managerp; 716 REQUIRE(VALID_MANAGER(manager)); 717 718 LOCK(&manager->lock); 719 720 REQUIRE(EMPTY(manager->timers)); 721 manager->done = true; 722 723 XTRACE("signal (destroy)"); 724 SIGNAL(&manager->wakeup); 725 726 UNLOCK(&manager->lock); 727 728 /* 729 * Wait for thread to exit. 730 */ 731 isc_thread_join(manager->thread, NULL); 732 733 /* 734 * Clean up. 735 */ 736 (void)isc_condition_destroy(&manager->wakeup); 737 isc_mutex_destroy(&manager->lock); 738 isc_heap_destroy(&manager->heap); 739 manager->magic = 0; 740 isc_mem_putanddetach(&manager->mctx, manager, sizeof(*manager)); 741 742 *managerp = NULL; 743} 744