From 349cfa7acb95abe865209a28e417ec74b56f9bba Mon Sep 17 00:00:00 2001 From: Alberto Gonzalez Iniesta Date: Tue, 21 Feb 2012 15:53:40 +0100 Subject: Imported Upstream version 2.2.1 --- schedule.c | 653 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 653 insertions(+) create mode 100644 schedule.c (limited to 'schedule.c') diff --git a/schedule.c b/schedule.c new file mode 100644 index 0000000..f0482ab --- /dev/null +++ b/schedule.c @@ -0,0 +1,653 @@ +/* + * 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. + * + * 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 -- cgit v1.2.3