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