summaryrefslogtreecommitdiff
path: root/openvpn/src/openvpn/schedule.c
diff options
context:
space:
mode:
Diffstat (limited to 'openvpn/src/openvpn/schedule.c')
-rw-r--r--openvpn/src/openvpn/schedule.c659
1 files changed, 0 insertions, 659 deletions
diff --git a/openvpn/src/openvpn/schedule.c b/openvpn/src/openvpn/schedule.c
deleted file mode 100644
index 471330f0..00000000
--- a/openvpn/src/openvpn/schedule.c
+++ /dev/null
@@ -1,659 +0,0 @@
-/*
- * 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
- */
-
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#elif defined(_MSC_VER)
-#include "config-msvc.h"
-#endif
-
-#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);
- return s;
-}
-
-void
-schedule_free (struct schedule *s)
-{
- free (s);
-}
-
-void
-schedule_remove_entry (struct schedule *s, struct schedule_entry *e)
-{
- s->earliest_wakeup = NULL; /* invalidate cache */
- schedule_remove_node (s, e);
-}
-
-/*
- * 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 v1.2.3 (git 2.25.1) at 2024-12-28 00:08:13 +0000