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
8 * Copyright (C) 2002-2009 OpenVPN Technologies, Inc. <sales@openvpn.net>
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.
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.
19 * You should have received a copy of the GNU General Public License
20 * along with this program (see the file COPYING included with this
21 * distribution); if not, write to the Free Software Foundation, Inc.,
22 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
29 * This code implements an efficient scheduler using
30 * a random treap binary tree.
32 * The scheduler is used by the server executive to
33 * keep track of which instances need service at a
34 * known time in the future. Instances need to
35 * schedule events for things such as sending
36 * a ping or scheduling a TLS renegotiation.
41 /* define to enable a special test mode */
42 /*#define SCHEDULE_TEST*/
50 struct timeval tv
; /* wakeup time */
51 unsigned int pri
; /* random treap priority */
52 struct schedule_entry
*parent
; /* treap (btree) links */
53 struct schedule_entry
*lt
;
54 struct schedule_entry
*gt
;
60 struct schedule_entry
*earliest_wakeup
; /* cached earliest wakeup */
61 struct schedule_entry
*root
; /* the root of the treap (btree) */
64 /* Public functions */
66 struct schedule
*schedule_init (void);
67 void schedule_free (struct schedule
*s
);
68 void schedule_remove_entry (struct schedule
*s
, struct schedule_entry
*e
);
71 void schedule_test (void);
74 /* Private Functions */
76 /* is node already in tree? */
77 #define IN_TREE(e) ((e)->pri)
79 struct schedule_entry
*schedule_find_least (struct schedule_entry
*e
);
80 void schedule_add_modify (struct schedule
*s
, struct schedule_entry
*e
);
81 void schedule_remove_node (struct schedule
*s
, struct schedule_entry
*e
);
83 /* Public inline functions */
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
98 schedule_add_entry (struct schedule
*s
,
99 struct schedule_entry
*e
,
100 const struct timeval
*tv
,
103 mutex_lock (&s
->mutex
);
104 if (!IN_TREE (e
) || !sigma
|| !tv_within_sigma (tv
, &e
->tv
, sigma
))
107 schedule_add_modify (s
, e
);
108 s
->earliest_wakeup
= NULL
; /* invalidate cache */
110 mutex_unlock (&s
->mutex
);
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).
119 static inline struct schedule_entry
*
120 schedule_get_earliest_wakeup (struct schedule
*s
,
121 struct timeval
*wakeup
)
123 struct schedule_entry
*ret
;
125 mutex_lock (&s
->mutex
);
128 if (!s
->earliest_wakeup
)
129 s
->earliest_wakeup
= schedule_find_least (s
->root
);
130 ret
= s
->earliest_wakeup
;
134 mutex_unlock (&s
->mutex
);