summaryrefslogtreecommitdiffstats
path: root/schedule.c
diff options
context:
space:
mode:
Diffstat (limited to 'schedule.c')
-rw-r--r--schedule.c657
1 files changed, 657 insertions, 0 deletions
diff --git a/schedule.c b/schedule.c
new file mode 100644
index 0000000..8a53031
--- /dev/null
+++ b/schedule.c
@@ -0,0 +1,657 @@
+/*
+ * 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-2010 OpenVPN Technologies, 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 (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
+ */
+
+#include "syshead.h"
+
+#if P2MP_SERVER
+
+#include "buffer.h"
+#include "misc.h"
+#include "crypto.h"
+#include "schedule.h"
+
+#include "memdbg.h"
+
+#ifdef SCHEDULE_TEST
+
+struct status
+{
+ int sru;
+ int ins;
+ int coll;
+ int lsteps;
+};
+
+static struct status z;
+
+#endif
+
+#ifdef ENABLE_DEBUG
+static void
+schedule_entry_debug_info (const char *caller, const struct schedule_entry *e)
+{
+ struct gc_arena gc = gc_new ();
+ if (e)
+ {
+ dmsg (D_SCHEDULER, "SCHEDULE: %s wakeup=[%s] pri=%u",
+ caller,
+ tv_string_abs (&e->tv, &gc),
+ e->pri);
+ }
+ else
+ {
+ dmsg (D_SCHEDULER, "SCHEDULE: %s NULL",
+ caller);
+ }
+ gc_free (&gc);
+}
+#endif
+
+static inline void
+schedule_set_pri (struct schedule_entry *e)
+{
+ e->pri = random ();
+ if (e->pri < 1)
+ e->pri = 1;
+}
+
+/* This is the master key comparison routine. A key is
+ * simply a struct timeval containing the absolute time for
+ * an event. The unique treap priority (pri) is used to ensure
+ * that keys do not collide.
+ */
+static inline int
+schedule_entry_compare (const struct schedule_entry *e1,
+ const struct schedule_entry *e2)
+{
+ if (e1->tv.tv_sec < e2->tv.tv_sec)
+ return -1;
+ else if (e1->tv.tv_sec > e2->tv.tv_sec)
+ return 1;
+ else
+ {
+ if (e1->tv.tv_usec < e2->tv.tv_usec)
+ return -1;
+ else if (e1->tv.tv_usec > e2->tv.tv_usec)
+ return 1;
+ else
+ {
+ if (e1->pri < e2->pri)
+ return -1;
+ else if (e1->pri > e2->pri)
+ return 1;
+ else
+ return 0;
+ }
+ }
+}
+
+/*
+ * Detach a btree node from its parent
+ */
+static inline void
+schedule_detach_parent (struct schedule *s, struct schedule_entry *e)
+{
+ if (e)
+ {
+ if (e->parent)
+ {
+ if (e->parent->lt == e)
+ e->parent->lt = NULL;
+ else if (e->parent->gt == e)
+ e->parent->gt = NULL;
+ else
+ {
+ /* parent <-> child linkage is corrupted */
+ ASSERT (0);
+ }
+ e->parent = NULL;
+ }
+ else
+ {
+ if (s->root == e) /* last element deleted, tree is empty */
+ s->root = NULL;
+ }
+ }
+}
+
+/*
+ *
+ * Given a binary search tree, move a node toward the root
+ * while still maintaining the correct ordering relationships
+ * within the tree. This function is the workhorse
+ * of the tree balancer.
+ *
+ * This code will break on key collisions, which shouldn't
+ * happen because the treap priority is considered part of the key
+ * and is guaranteed to be unique.
+ */
+static void
+schedule_rotate_up (struct schedule *s, struct schedule_entry *e)
+{
+ if (e && e->parent)
+ {
+ struct schedule_entry *lt = e->lt;
+ struct schedule_entry *gt = e->gt;
+ struct schedule_entry *p = e->parent;
+ struct schedule_entry *gp = p->parent;
+
+ if (gp) /* if grandparent exists, modify its child link */
+ {
+ if (gp->gt == p)
+ gp->gt = e;
+ else if (gp->lt == p)
+ gp->lt = e;
+ else
+ {
+ ASSERT (0);
+ }
+ }
+ else /* no grandparent, now we are the root */
+ {
+ s->root = e;
+ }
+
+ /* grandparent is now our parent */
+ e->parent = gp;
+
+ /* parent is now our child */
+ p->parent = e;
+
+ /* reorient former parent's links
+ to reflect new position in the tree */
+ if (p->gt == e)
+ {
+ e->lt = p;
+ p->gt = lt;
+ if (lt)
+ lt->parent = p;
+ }
+ else if (p->lt == e)
+ {
+ e->gt = p;
+ p->lt = gt;
+ if (gt)
+ gt->parent = p;
+ }
+ else
+ {
+ /* parent <-> child linkage is corrupted */
+ ASSERT (0);
+ }
+
+#ifdef SCHEDULE_TEST
+ ++z.sru;
+#endif
+ }
+}
+
+/*
+ * This is the treap deletion algorithm:
+ *
+ * Rotate lesser-priority children up in the tree
+ * until we are childless. Then delete.
+ */
+void
+schedule_remove_node (struct schedule *s, struct schedule_entry *e)
+{
+ while (e->lt || e->gt)
+ {
+ if (e->lt)
+ {
+ if (e->gt)
+ {
+ if (e->lt->pri < e->gt->pri)
+ schedule_rotate_up (s, e->lt);
+ else
+ schedule_rotate_up (s, e->gt);
+ }
+ else
+ schedule_rotate_up (s, e->lt);
+ }
+ else if (e->gt)
+ schedule_rotate_up (s, e->gt);
+ }
+
+ schedule_detach_parent (s, e);
+ e->pri = 0;
+}
+
+/*
+ * Trivially add a node to a binary search tree without
+ * regard for balance.
+ */
+static void
+schedule_insert (struct schedule *s, struct schedule_entry *e)
+{
+ struct schedule_entry *c = s->root;
+ while (true)
+ {
+ const int comp = schedule_entry_compare (e, c);
+
+#ifdef SCHEDULE_TEST
+ ++z.ins;
+#endif
+
+ if (comp == -1)
+ {
+ if (c->lt)
+ {
+ c = c->lt;
+ continue;
+ }
+ else
+ {
+ c->lt = e;
+ e->parent = c;
+ break;
+ }
+ }
+ else if (comp == 1)
+ {
+ if (c->gt)
+ {
+ c = c->gt;
+ continue;
+ }
+ else
+ {
+ c->gt = e;
+ e->parent = c;
+ break;
+ }
+ }
+ else
+ {
+ /* rare key/priority collision -- no big deal,
+ just choose another priority and retry */
+#ifdef SCHEDULE_TEST
+ ++z.coll;
+#endif
+ schedule_set_pri (e);
+ /* msg (M_INFO, "PRI COLLISION pri=%u", e->pri); */
+ c = s->root;
+ continue;
+ }
+ }
+}
+
+/*
+ * Given an element, remove it from the btree if it's already
+ * there and re-insert it based on its current key.
+ */
+void
+schedule_add_modify (struct schedule *s, struct schedule_entry *e)
+{
+#ifdef ENABLE_DEBUG
+ if (check_debug_level (D_SCHEDULER))
+ schedule_entry_debug_info ("schedule_add_modify", e);
+#endif
+
+ /* already in tree, remove */
+ if (IN_TREE (e))
+ schedule_remove_node (s, e);
+
+ /* set random priority */
+ schedule_set_pri (e);
+
+ if (s->root)
+ schedule_insert (s, e); /* trivial insert into tree */
+ else
+ s->root = e; /* tree was empty, we are the first element */
+
+ /* This is the magic of the randomized treap algorithm which
+ keeps the tree balanced. Move the node up the tree until
+ its own priority is greater than that of its parent */
+ while (e->parent && e->parent->pri > e->pri)
+ schedule_rotate_up (s, e);
+}
+
+/*
+ * Find the earliest event to be scheduled
+ */
+struct schedule_entry *
+schedule_find_least (struct schedule_entry *e)
+{
+ if (e)
+ {
+ while (e->lt)
+ {
+#ifdef SCHEDULE_TEST
+ ++z.lsteps;
+#endif
+ e = e->lt;
+ }
+ }
+
+#ifdef ENABLE_DEBUG
+ if (check_debug_level (D_SCHEDULER))
+ schedule_entry_debug_info ("schedule_find_least", e);
+#endif
+
+ return e;
+}
+
+/*
+ * Public functions below this point
+ */
+
+struct schedule *
+schedule_init (void)
+{
+ struct schedule *s;
+
+ ALLOC_OBJ_CLEAR (s, struct schedule);
+ mutex_init (&s->mutex);
+ return s;
+}
+
+void
+schedule_free (struct schedule *s)
+{
+ mutex_destroy (&s->mutex);
+ free (s);
+}
+
+void
+schedule_remove_entry (struct schedule *s, struct schedule_entry *e)
+{
+ mutex_lock (&s->mutex);
+ s->earliest_wakeup = NULL; /* invalidate cache */
+ schedule_remove_node (s, e);
+ mutex_unlock (&s->mutex);
+}
+
+/*
+ * Debug functions below this point
+ */
+
+#ifdef SCHEDULE_TEST
+
+static inline struct schedule_entry *
+schedule_find_earliest_wakeup (struct schedule *s)
+{
+ return schedule_find_least (s->root);
+}
+
+/*
+ * Recursively check that the treap (btree) is
+ * internally consistent.
+ */
+int
+schedule_debug_entry (const struct schedule_entry* e,
+ int depth,
+ int *count,
+ struct timeval *least,
+ const struct timeval *min,
+ const struct timeval *max)
+{
+ struct gc_arena gc = gc_new ();
+ int maxdepth = depth;
+ if (e)
+ {
+ int d;
+
+ ASSERT (e != e->lt);
+ ASSERT (e != e->gt);
+ ASSERT (e != e->parent);
+ ASSERT (!e->parent || e->parent != e->lt);
+ ASSERT (!e->parent || e->parent != e->gt);
+ ASSERT (!e->lt || e->lt != e->gt);
+
+ if (e->lt)
+ {
+ ASSERT (e->lt->parent == e);
+ ASSERT (schedule_entry_compare (e->lt, e) == -1);
+ ASSERT (e->lt->pri >= e->pri);
+ }
+
+ if (e->gt)
+ {
+ ASSERT (e->gt->parent == e);
+ ASSERT (schedule_entry_compare (e->gt, e));
+ ASSERT (e->gt->pri >= e->pri);
+ }
+
+ ASSERT (tv_le (min, &e->tv));
+ ASSERT (tv_le (&e->tv, max));
+
+ if (count)
+ ++(*count);
+
+ if (least && tv_lt (&e->tv, least))
+ *least = e->tv;
+
+ d = schedule_debug_entry (e->lt, depth+1, count, least, min, &e->tv);
+ if (d > maxdepth)
+ maxdepth = d;
+
+ d = schedule_debug_entry (e->gt, depth+1, count, least, &e->tv, max);
+ if (d > maxdepth)
+ maxdepth = d;
+ }
+ gc_free (&gc);
+ return maxdepth;
+}
+
+int
+schedule_debug (struct schedule *s, int *count, struct timeval *least)
+{
+ struct timeval min;
+ struct timeval max;
+
+ min.tv_sec = 0;
+ min.tv_usec = 0;
+ max.tv_sec = 0x7FFFFFFF;
+ max.tv_usec = 0x7FFFFFFF;
+
+ if (s->root)
+ {
+ ASSERT (s->root->parent == NULL);
+ }
+ return schedule_debug_entry (s->root, 0, count, least, &min, &max);
+}
+
+#if 1
+
+void
+tv_randomize (struct timeval *tv)
+{
+ tv->tv_sec += random() % 100;
+ tv->tv_usec = random () % 100;
+}
+
+#else
+
+void
+tv_randomize (struct timeval *tv)
+{
+ struct gc_arena gc = gc_new ();
+ long int choice = get_random ();
+ if ((choice & 0xFF) == 0)
+ tv->tv_usec += ((choice >> 8) & 0xFF);
+ else
+ prng_bytes ((uint8_t *)tv, sizeof (struct timeval));
+ gc_free (&gc);
+}
+
+#endif
+
+void
+schedule_verify (struct schedule *s)
+{
+ struct gc_arena gc = gc_new ();
+ struct timeval least;
+ int count;
+ int maxlev;
+ struct schedule_entry* e;
+ const struct status zz = z;
+
+ least.tv_sec = least.tv_usec = 0x7FFFFFFF;
+
+ count = 0;
+
+ maxlev = schedule_debug (s, &count, &least);
+
+ e = schedule_find_earliest_wakeup (s);
+
+ if (e)
+ {
+ printf ("Verification Phase count=%d maxlev=%d sru=%d ins=%d coll=%d ls=%d l=%s",
+ count,
+ maxlev,
+ zz.sru,
+ zz.ins,
+ zz.coll,
+ zz.lsteps,
+ tv_string (&e->tv, &gc));
+
+ if (!tv_eq (&least, &e->tv))
+ printf (" [COMPUTED DIFFERENT MIN VALUES!]");
+
+ printf ("\n");
+ }
+
+ CLEAR (z);
+ gc_free (&gc);
+}
+
+void
+schedule_randomize_array (struct schedule_entry **array, int size)
+{
+ int i;
+ for (i = 0; i < size; ++i)
+ {
+ const int src = get_random () % size;
+ struct schedule_entry *tmp = array [i];
+ if (i != src)
+ {
+ array [i] = array [src];
+ array [src] = tmp;
+ }
+ }
+}
+
+void
+schedule_print_work (struct schedule_entry *e, int indent)
+{
+ struct gc_arena gc = gc_new ();
+ int i;
+ for (i = 0; i < indent; ++i)
+ printf (" ");
+ if (e)
+ {
+ printf ("%s [%u] e=" ptr_format ", p=" ptr_format " lt=" ptr_format " gt=" ptr_format "\n",
+ tv_string (&e->tv, &gc),
+ e->pri,
+ (ptr_type)e,
+ (ptr_type)e->parent,
+ (ptr_type)e->lt,
+ (ptr_type)e->gt);
+ schedule_print_work (e->lt, indent+1);
+ schedule_print_work (e->gt, indent+1);
+ }
+ else
+ printf ("NULL\n");
+ gc_free (&gc);
+}
+
+void
+schedule_print (struct schedule *s)
+{
+ printf ("*************************\n");
+ schedule_print_work (s->root, 0);
+}
+
+void
+schedule_test (void)
+{
+ struct gc_arena gc = gc_new ();
+ int n = 1000;
+ int n_mod = 25;
+
+ int i, j;
+ struct schedule_entry **array;
+ struct schedule *s = schedule_init ();
+ struct schedule_entry* e;
+
+ CLEAR (z);
+ ALLOC_ARRAY (array, struct schedule_entry *, n);
+
+ printf ("Creation/Insertion Phase\n");
+
+ for (i = 0; i < n; ++i)
+ {
+ ALLOC_OBJ_CLEAR (array[i], struct schedule_entry);
+ tv_randomize (&array[i]->tv);
+ /*schedule_print (s);*/
+ /*schedule_verify (s);*/
+ schedule_add_modify (s, array[i]);
+ }
+
+ schedule_randomize_array (array, n);
+
+ /*schedule_print (s);*/
+ schedule_verify (s);
+
+ for (j = 1; j <= n_mod; ++j)
+ {
+ printf ("Modification Phase Pass %d\n", j);
+
+ for (i = 0; i < n; ++i)
+ {
+ e = schedule_find_earliest_wakeup (s);
+ /*printf ("BEFORE %s\n", tv_string (&e->tv, &gc));*/
+ tv_randomize (&e->tv);
+ /*printf ("AFTER %s\n", tv_string (&e->tv, &gc));*/
+ schedule_add_modify (s, e);
+ /*schedule_verify (s);*/
+ /*schedule_print (s);*/
+ }
+ schedule_verify (s);
+ /*schedule_print (s);*/
+ }
+
+ /*printf ("INS=%d\n", z.ins);*/
+
+ while ((e = schedule_find_earliest_wakeup (s)))
+ {
+ schedule_remove_node (s, e);
+ /*schedule_verify (s);*/
+ }
+ schedule_verify (s);
+
+ printf ("S->ROOT is %s\n", s->root ? "NOT NULL" : "NULL");
+
+ for (i = 0; i < n; ++i)
+ {
+ free (array[i]);
+ }
+ free (array);
+ free (s);
+ gc_free (&gc);
+}
+
+#endif
+#endif
generated by cgit (git 2.34.1) at 2024-11-17 15:13:02 +0000