aboutsummaryrefslogtreecommitdiff
path: root/schedule.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--schedule.h140
1 files changed, 140 insertions, 0 deletions
diff --git a/schedule.h b/schedule.h
new file mode 100644
index 0000000..4e0ae74
--- /dev/null
+++ b/schedule.h
@@ -0,0 +1,140 @@
+/*
+ * 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-2005 OpenVPN Solutions LLC <info@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 (see the file COPYING included with this
+ * distribution); if not, write to the Free Software Foundation, Inc.,
+ * 59 Temple Place, Suite 330, Boston, MA 02111-1307 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.
+ */
+
+#if P2MP_SERVER
+
+/* define to enable a special test mode */
+/*#define SCHEDULE_TEST*/
+
+#include "otime.h"
+#include "thread.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
+{
+ MUTEX_DEFINE (mutex);
+ 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)
+{
+ mutex_lock (&s->mutex);
+ 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 */
+ }
+ mutex_unlock (&s->mutex);
+}
+
+/*
+ * 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;
+
+ mutex_lock (&s->mutex);
+
+ /* cache result */
+ if (!s->earliest_wakeup)
+ s->earliest_wakeup = schedule_find_least (s->root);
+ ret = s->earliest_wakeup;
+ if (ret)
+ *wakeup = ret->tv;
+
+ mutex_unlock (&s->mutex);
+
+ return ret;
+}
+
+#endif
+#endif