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-2018 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, write to the Free Software Foundation, Inc.,
21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22 */
23
24 #ifndef SCHEDULE_H
25 #define SCHEDULE_H
26
27 /*
28 * This code implements an efficient scheduler using
29 * a random treap binary tree.
30 *
31 * The scheduler is used by the server executive to
32 * keep track of which instances need service at a
33 * known time in the future. Instances need to
34 * schedule events for things such as sending
35 * a ping or scheduling a TLS renegotiation.
36 */
37
38 /* define to enable a special test mode */
39 /*#define SCHEDULE_TEST*/
40
41 #include "otime.h"
42 #include "error.h"
43
44 struct schedule_entry
45 {
46 struct timeval tv; /* wakeup time */
47 unsigned int pri; /* random treap priority */
48 struct schedule_entry *parent; /* treap (btree) links */
49 struct schedule_entry *lt;
50 struct schedule_entry *gt;
51 };
52
53 struct schedule
54 {
55 struct schedule_entry *earliest_wakeup; /* cached earliest wakeup */
56 struct schedule_entry *root; /* the root of the treap (btree) */
57 };
58
59 /* Public functions */
60
61 struct schedule *schedule_init(void);
62
63 void schedule_free(struct schedule *s);
64
65 void schedule_remove_entry(struct schedule *s, struct schedule_entry *e);
66
67 #ifdef SCHEDULE_TEST
68 void schedule_test(void);
69
70 #endif
71
72 /* Private Functions */
73
74 /* is node already in tree? */
75 #define IN_TREE(e) ((e)->pri)
76
77 struct schedule_entry *schedule_find_least(struct schedule_entry *e);
78
79 void schedule_add_modify(struct schedule *s, struct schedule_entry *e);
80
81 void schedule_remove_node(struct schedule *s, struct schedule_entry *e);
82
83 /* Public inline functions */
84
85 /*
86 * Add a struct schedule_entry (whose storage is managed by
87 * caller) to the btree. tv signifies the wakeup time for
88 * a future event. sigma is a time interval measured
89 * in microseconds -- the event window being represented
90 * starts at (tv - sigma) and ends at (tv + sigma).
91 * Event signaling can occur anywere within this interval.
92 * Making the interval larger makes the scheduler more efficient,
93 * while making it smaller results in more precise scheduling.
94 * The caller should treat the passed struct schedule_entry as
95 * an opaque object.
96 */
97 static inline void
schedule_add_entry(struct schedule * s,struct schedule_entry * e,const struct timeval * tv,unsigned int sigma)98 schedule_add_entry(struct schedule *s,
99 struct schedule_entry *e,
100 const struct timeval *tv,
101 unsigned int sigma)
102 {
103 if (!IN_TREE(e) || !sigma || !tv_within_sigma(tv, &e->tv, sigma))
104 {
105 e->tv = *tv;
106 schedule_add_modify(s, e);
107 s->earliest_wakeup = NULL; /* invalidate cache */
108 }
109 }
110
111 /*
112 * Return the node with the earliest wakeup time. If two
113 * nodes have the exact same wakeup time, select based on
114 * the random priority assigned to each node (the priority
115 * is randomized every time an entry is re-added).
116 */
117 static inline struct schedule_entry *
schedule_get_earliest_wakeup(struct schedule * s,struct timeval * wakeup)118 schedule_get_earliest_wakeup(struct schedule *s,
119 struct timeval *wakeup)
120 {
121 struct schedule_entry *ret;
122
123 /* cache result */
124 if (!s->earliest_wakeup)
125 {
126 s->earliest_wakeup = schedule_find_least(s->root);
127 }
128 ret = s->earliest_wakeup;
129 if (ret)
130 {
131 *wakeup = ret->tv;
132 }
133
134 return ret;
135 }
136
137 #endif /* ifndef SCHEDULE_H */
138