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-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 #if P2MP_SERVER
39 
40 /* define to enable a special test mode */
41 /*#define SCHEDULE_TEST*/
42 
43 #include "otime.h"
44 #include "error.h"
45 
47 {
48  struct timeval tv; /* wakeup time */
49  unsigned int pri; /* random treap priority */
50  struct schedule_entry *parent; /* treap (btree) links */
51  struct schedule_entry *lt;
52  struct schedule_entry *gt;
53 };
54 
55 struct schedule
56 {
57  struct schedule_entry *earliest_wakeup; /* cached earliest wakeup */
58  struct schedule_entry *root; /* the root of the treap (btree) */
59 };
60 
61 /* Public functions */
62 
63 struct schedule *schedule_init(void);
64 
65 void schedule_free(struct schedule *s);
66 
67 void schedule_remove_entry(struct schedule *s, struct schedule_entry *e);
68 
69 #ifdef SCHEDULE_TEST
70 void schedule_test(void);
71 
72 #endif
73 
74 /* Private Functions */
75 
76 /* is node already in tree? */
77 #define IN_TREE(e) ((e)->pri)
78 
80 
81 void schedule_add_modify(struct schedule *s, struct schedule_entry *e);
82 
83 void schedule_remove_node(struct schedule *s, struct schedule_entry *e);
84 
85 /* Public inline functions */
86 
87 /*
88  * Add a struct schedule_entry (whose storage is managed by
89  * caller) to the btree. tv signifies the wakeup time for
90  * a future event. sigma is a time interval measured
91  * in microseconds -- the event window being represented
92  * starts at (tv - sigma) and ends at (tv + sigma).
93  * Event signaling can occur anywere within this interval.
94  * Making the interval larger makes the scheduler more efficient,
95  * while making it smaller results in more precise scheduling.
96  * The caller should treat the passed struct schedule_entry as
97  * an opaque object.
98  */
99 static inline void
101  struct schedule_entry *e,
102  const struct timeval *tv,
103  unsigned int sigma)
104 {
105  if (!IN_TREE(e) || !sigma || !tv_within_sigma(tv, &e->tv, sigma))
106  {
107  e->tv = *tv;
108  schedule_add_modify(s, e);
109  s->earliest_wakeup = NULL; /* invalidate cache */
110  }
111 }
112 
113 /*
114  * Return the node with the earliest wakeup time. If two
115  * nodes have the exact same wakeup time, select based on
116  * the random priority assigned to each node (the priority
117  * is randomized every time an entry is re-added).
118  */
119 static inline struct schedule_entry *
121  struct timeval *wakeup)
122 {
123  struct schedule_entry *ret;
124 
125  /* cache result */
126  if (!s->earliest_wakeup)
127  {
129  }
130  ret = s->earliest_wakeup;
131  if (ret)
132  {
133  *wakeup = ret->tv;
134  }
135 
136  return ret;
137 }
138 
139 #endif /* if P2MP_SERVER */
140 #endif /* ifndef SCHEDULE_H */
#define IN_TREE(e)
Definition: schedule.h:77
static void schedule_add_entry(struct schedule *s, struct schedule_entry *e, const struct timeval *tv, unsigned int sigma)
Definition: schedule.h:100
unsigned int pri
Definition: schedule.h:49
struct schedule_entry * earliest_wakeup
Definition: schedule.h:57
void schedule_add_modify(struct schedule *s, struct schedule_entry *e)
Definition: schedule.c:348
struct timeval tv
Definition: schedule.h:48
void schedule_free(struct schedule *s)
Definition: schedule.c:425
void schedule_remove_node(struct schedule *s, struct schedule_entry *e)
Definition: schedule.c:252
struct schedule_entry * root
Definition: schedule.h:58
void schedule_remove_entry(struct schedule *s, struct schedule_entry *e)
Definition: schedule.c:431
struct schedule_entry * gt
Definition: schedule.h:52
Definition: schedule.h:46
struct schedule_entry * parent
Definition: schedule.h:50
struct schedule_entry * lt
Definition: schedule.h:51
struct schedule_entry * schedule_find_least(struct schedule_entry *e)
Definition: schedule.c:388
static struct schedule_entry * schedule_get_earliest_wakeup(struct schedule *s, struct timeval *wakeup)
Definition: schedule.h:120
static bool tv_within_sigma(const struct timeval *t1, const struct timeval *t2, unsigned int sigma)
Definition: otime.h:280
struct schedule * schedule_init(void)
Definition: schedule.c:416