OpenVPN
schedule.h
Go to the documentation of this file.
1/*
2 * OpenVPN -- An application to securely tunnel IP networks
3 * over a single TCP/UDP port, with support for SSL/TLS-based
4 * session authentication and key exchange,
5 * packet encryption, packet authentication, and
6 * packet compression.
7 *
8 * Copyright (C) 2002-2025 OpenVPN Inc <sales@openvpn.net>
9 *
10 * This program is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License version 2
12 * as published by the Free Software Foundation.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, see <https://www.gnu.org/licenses/>.
21 */
22
23#ifndef SCHEDULE_H
24#define SCHEDULE_H
25
26/*
27 * This code implements an efficient scheduler using
28 * a random treap binary tree.
29 *
30 * The scheduler is used by the server executive to
31 * keep track of which instances need service at a
32 * known time in the future. Instances need to
33 * schedule events for things such as sending
34 * a ping or scheduling a TLS renegotiation.
35 */
36
37/* define to enable a special test mode */
38/*#define SCHEDULE_TEST*/
39
40#include "otime.h"
41#include "error.h"
42
44{
45 struct timeval tv; /* wakeup time */
46 unsigned int pri; /* random treap priority */
47 struct schedule_entry *parent; /* treap (btree) links */
50};
51
53{
54 struct schedule_entry *earliest_wakeup; /* cached earliest wakeup */
55 struct schedule_entry *root; /* the root of the treap (btree) */
56};
57
58/* Public functions */
59
60struct schedule *schedule_init(void);
61
62void schedule_free(struct schedule *s);
63
64void schedule_remove_entry(struct schedule *s, struct schedule_entry *e);
65
66#ifdef SCHEDULE_TEST
67void schedule_test(void);
68
69#endif
70
71/* Private Functions */
72
73/* is node already in tree? */
74#define IN_TREE(e) ((e)->pri)
75
77
78void schedule_add_modify(struct schedule *s, struct schedule_entry *e);
79
80void schedule_remove_node(struct schedule *s, struct schedule_entry *e);
81
82/* Public inline functions */
83
84/*
85 * Add a struct schedule_entry (whose storage is managed by
86 * caller) to the btree. tv signifies the wakeup time for
87 * a future event. sigma is a time interval measured
88 * in microseconds -- the event window being represented
89 * starts at (tv - sigma) and ends at (tv + sigma).
90 * Event signaling can occur anywere within this interval.
91 * Making the interval larger makes the scheduler more efficient,
92 * while making it smaller results in more precise scheduling.
93 * The caller should treat the passed struct schedule_entry as
94 * an opaque object.
95 */
96static inline void
97schedule_add_entry(struct schedule *s, struct schedule_entry *e, const struct timeval *tv,
98 unsigned int sigma)
99{
100 if (!IN_TREE(e) || !sigma || !tv_within_sigma(tv, &e->tv, sigma))
101 {
102 e->tv = *tv;
104 s->earliest_wakeup = NULL; /* invalidate cache */
105 }
106}
107
108/*
109 * Return the node with the earliest wakeup time. If two
110 * nodes have the exact same wakeup time, select based on
111 * the random priority assigned to each node (the priority
112 * is randomized every time an entry is re-added).
113 */
114static inline struct schedule_entry *
115schedule_get_earliest_wakeup(struct schedule *s, struct timeval *wakeup)
116{
117 struct schedule_entry *ret;
118
119 /* cache result */
120 if (!s->earliest_wakeup)
121 {
123 }
124 ret = s->earliest_wakeup;
125 if (ret)
126 {
127 *wakeup = ret->tv;
128 }
129
130 return ret;
131}
132
133#endif /* ifndef SCHEDULE_H */
static bool tv_within_sigma(const struct timeval *t1, const struct timeval *t2, unsigned int sigma)
Definition otime.h:246
void schedule_remove_entry(struct schedule *s, struct schedule_entry *e)
Definition schedule.c:421
struct schedule * schedule_init(void)
Definition schedule.c:406
void schedule_remove_node(struct schedule *s, struct schedule_entry *e)
Definition schedule.c:243
static struct schedule_entry * schedule_get_earliest_wakeup(struct schedule *s, struct timeval *wakeup)
Definition schedule.h:115
struct schedule_entry * schedule_find_least(struct schedule_entry *e)
Definition schedule.c:378
static void schedule_add_entry(struct schedule *s, struct schedule_entry *e, const struct timeval *tv, unsigned int sigma)
Definition schedule.h:97
void schedule_add_modify(struct schedule *s, struct schedule_entry *e)
Definition schedule.c:339
void schedule_free(struct schedule *s)
Definition schedule.c:415
#define IN_TREE(e)
Definition schedule.h:74
Definition schedule.h:44
unsigned int pri
Definition schedule.h:46
struct timeval tv
Definition schedule.h:45
struct schedule_entry * lt
Definition schedule.h:48
struct schedule_entry * parent
Definition schedule.h:47
struct schedule_entry * gt
Definition schedule.h:49
struct schedule_entry * earliest_wakeup
Definition schedule.h:54
struct schedule_entry * root
Definition schedule.h:55