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