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