Imported Upstream version 2.3_rc1

1 files changed, 0 insertions, 653 deletions

diff --git a/schedule.c b/schedule.c
deleted file mode 100644
index f0482ab..0000000
--- a/schedule.c
+++ /dev/null
@@ -1,653 +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
- */
-
-#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