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