summaryrefslogtreecommitdiff
path: root/src/openvpn/schedule.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/openvpn/schedule.c')
-rw-r--r--src/openvpn/schedule.c846
1 files changed, 455 insertions, 391 deletions
diff --git a/src/openvpn/schedule.c b/src/openvpn/schedule.c
index 471330f..610bfa4 100644
--- a/src/openvpn/schedule.c
+++ b/src/openvpn/schedule.c
@@ -5,7 +5,7 @@
* packet encryption, packet authentication, and
* packet compression.
*
- * Copyright (C) 2002-2010 OpenVPN Technologies, Inc. <sales@openvpn.net>
+ * Copyright (C) 2002-2017 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
@@ -43,10 +43,10 @@
struct status
{
- int sru;
- int ins;
- int coll;
- int lsteps;
+ int sru;
+ int ins;
+ int coll;
+ int lsteps;
};
static struct status z;
@@ -55,31 +55,33 @@ static struct status z;
#ifdef ENABLE_DEBUG
static void
-schedule_entry_debug_info (const char *caller, const struct schedule_entry *e)
+schedule_entry_debug_info(const char *caller, const struct schedule_entry *e)
{
- struct gc_arena gc = gc_new ();
- if (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);
+ dmsg(D_SCHEDULER, "SCHEDULE: %s wakeup=[%s] pri=%u",
+ caller,
+ tv_string_abs(&e->tv, &gc),
+ e->pri);
}
- else
+ else
{
- dmsg (D_SCHEDULER, "SCHEDULE: %s NULL",
- caller);
+ dmsg(D_SCHEDULER, "SCHEDULE: %s NULL",
+ caller);
}
- gc_free (&gc);
+ gc_free(&gc);
}
#endif
static inline void
-schedule_set_pri (struct schedule_entry *e)
+schedule_set_pri(struct schedule_entry *e)
{
- e->pri = random ();
- if (e->pri < 1)
- e->pri = 1;
+ e->pri = random();
+ if (e->pri < 1)
+ {
+ e->pri = 1;
+ }
}
/* This is the master key comparison routine. A key is
@@ -88,28 +90,42 @@ schedule_set_pri (struct schedule_entry *e)
* that keys do not collide.
*/
static inline int
-schedule_entry_compare (const struct schedule_entry *e1,
- const struct schedule_entry *e2)
+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_sec < e2->tv.tv_sec)
+ {
+ return -1;
+ }
+ else if (e1->tv.tv_sec > e2->tv.tv_sec)
{
- 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;
- }
+ 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;
+ }
+ }
}
}
@@ -117,28 +133,34 @@ schedule_entry_compare (const struct schedule_entry *e1,
* Detach a btree node from its parent
*/
static inline void
-schedule_detach_parent (struct schedule *s, struct schedule_entry *e)
+schedule_detach_parent(struct schedule *s, struct schedule_entry *e)
{
- if (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;
- }
+ 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;
+ }
+ }
}
}
@@ -154,61 +176,69 @@ schedule_detach_parent (struct schedule *s, struct schedule_entry *e)
* and is guaranteed to be unique.
*/
static void
-schedule_rotate_up (struct schedule *s, struct schedule_entry *e)
+schedule_rotate_up(struct schedule *s, struct schedule_entry *e)
{
- if (e && e->parent)
+ 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);
- }
+ 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;
+ ++z.sru;
#endif
}
}
@@ -220,28 +250,36 @@ schedule_rotate_up (struct schedule *s, struct schedule_entry *e)
* until we are childless. Then delete.
*/
void
-schedule_remove_node (struct schedule *s, struct schedule_entry *e)
+schedule_remove_node(struct schedule *s, struct schedule_entry *e)
{
- while (e->lt || e->gt)
+ 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);
+ 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;
+ schedule_detach_parent(s, e);
+ e->pri = 0;
}
/*
@@ -249,57 +287,57 @@ schedule_remove_node (struct schedule *s, struct schedule_entry *e)
* regard for balance.
*/
static void
-schedule_insert (struct schedule *s, struct schedule_entry *e)
+schedule_insert(struct schedule *s, struct schedule_entry *e)
{
- struct schedule_entry *c = s->root;
- while (true)
+ struct schedule_entry *c = s->root;
+ while (true)
{
- const int comp = schedule_entry_compare (e, c);
+ const int comp = schedule_entry_compare(e, c);
#ifdef SCHEDULE_TEST
- ++z.ins;
+ ++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 */
+ 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;
+ ++z.coll;
#endif
- schedule_set_pri (e);
- /* msg (M_INFO, "PRI COLLISION pri=%u", e->pri); */
- c = s->root;
- continue;
- }
+ schedule_set_pri(e);
+ /* msg (M_INFO, "PRI COLLISION pri=%u", e->pri); */
+ c = s->root;
+ continue;
+ }
}
}
@@ -308,55 +346,65 @@ schedule_insert (struct schedule *s, struct schedule_entry *e)
* there and re-insert it based on its current key.
*/
void
-schedule_add_modify (struct schedule *s, struct schedule_entry *e)
+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);
+ 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);
+ /* already in tree, remove */
+ if (IN_TREE(e))
+ {
+ schedule_remove_node(s, e);
+ }
- /* set random priority */
- schedule_set_pri (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 */
+ 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);
+ }
+ /* 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)
+schedule_find_least(struct schedule_entry *e)
{
- if (e)
+ if (e)
{
- while (e->lt)
- {
+ while (e->lt)
+ {
#ifdef SCHEDULE_TEST
- ++z.lsteps;
+ ++z.lsteps;
#endif
- e = e->lt;
- }
+ e = e->lt;
+ }
}
-
+
#ifdef ENABLE_DEBUG
- if (check_debug_level (D_SCHEDULER))
- schedule_entry_debug_info ("schedule_find_least", e);
+ if (check_debug_level(D_SCHEDULER))
+ {
+ schedule_entry_debug_info("schedule_find_least", e);
+ }
#endif
- return e;
+ return e;
}
/*
@@ -364,25 +412,25 @@ schedule_find_least (struct schedule_entry *e)
*/
struct schedule *
-schedule_init (void)
+schedule_init(void)
{
- struct schedule *s;
+ struct schedule *s;
- ALLOC_OBJ_CLEAR (s, struct schedule);
- return s;
+ ALLOC_OBJ_CLEAR(s, struct schedule);
+ return s;
}
void
-schedule_free (struct schedule *s)
+schedule_free(struct schedule *s)
{
- free (s);
+ free(s);
}
void
-schedule_remove_entry (struct schedule *s, struct schedule_entry *e)
+schedule_remove_entry(struct schedule *s, struct schedule_entry *e)
{
- s->earliest_wakeup = NULL; /* invalidate cache */
- schedule_remove_node (s, e);
+ s->earliest_wakeup = NULL; /* invalidate cache */
+ schedule_remove_node(s, e);
}
/*
@@ -392,9 +440,9 @@ schedule_remove_entry (struct schedule *s, struct schedule_entry *e)
#ifdef SCHEDULE_TEST
static inline struct schedule_entry *
-schedule_find_earliest_wakeup (struct schedule *s)
+schedule_find_earliest_wakeup(struct schedule *s)
{
- return schedule_find_least (s->root);
+ return schedule_find_least(s->root);
}
/*
@@ -402,258 +450,274 @@ schedule_find_earliest_wakeup (struct schedule *s)
* 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)
+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)
+ 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;
+ 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;
+ gc_free(&gc);
+ return maxdepth;
}
int
-schedule_debug (struct schedule *s, int *count, struct timeval *least)
+schedule_debug(struct schedule *s, int *count, struct timeval *least)
{
- struct timeval min;
- struct timeval max;
+ struct timeval min;
+ struct timeval max;
- min.tv_sec = 0;
- min.tv_usec = 0;
- max.tv_sec = 0x7FFFFFFF;
- max.tv_usec = 0x7FFFFFFF;
+ min.tv_sec = 0;
+ min.tv_usec = 0;
+ max.tv_sec = 0x7FFFFFFF;
+ max.tv_usec = 0x7FFFFFFF;
- if (s->root)
+ if (s->root)
{
- ASSERT (s->root->parent == NULL);
+ ASSERT(s->root->parent == NULL);
}
- return schedule_debug_entry (s->root, 0, count, least, &min, &max);
+ return schedule_debug_entry(s->root, 0, count, least, &min, &max);
}
#if 1
void
-tv_randomize (struct timeval *tv)
+tv_randomize(struct timeval *tv)
{
- tv->tv_sec += random() % 100;
- tv->tv_usec = random () % 100;
+ tv->tv_sec += random() % 100;
+ tv->tv_usec = random() % 100;
}
-#else
+#else /* if 1 */
void
-tv_randomize (struct timeval *tv)
+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);
+ 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
+#endif /* if 1 */
void
-schedule_verify (struct schedule *s)
+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;
+ 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;
+ least.tv_sec = least.tv_usec = 0x7FFFFFFF;
- count = 0;
+ count = 0;
- maxlev = schedule_debug (s, &count, &least);
+ maxlev = schedule_debug(s, &count, &least);
- e = schedule_find_earliest_wakeup (s);
+ e = schedule_find_earliest_wakeup(s);
- if (e)
+ 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");
+ 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);
+
+ CLEAR(z);
+ gc_free(&gc);
}
void
-schedule_randomize_array (struct schedule_entry **array, int size)
+schedule_randomize_array(struct schedule_entry **array, int size)
{
- int i;
- for (i = 0; i < size; ++i)
+ 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;
- }
+ 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)
+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)
+ 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 ("%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);
+ printf("NULL\n");
}
- else
- printf ("NULL\n");
- gc_free (&gc);
+ gc_free(&gc);
}
void
-schedule_print (struct schedule *s)
+schedule_print(struct schedule *s)
{
- printf ("*************************\n");
- schedule_print_work (s->root, 0);
+ printf("*************************\n");
+ schedule_print_work(s->root, 0);
}
void
-schedule_test (void)
+schedule_test(void)
{
- struct gc_arena gc = gc_new ();
- int n = 1000;
- int n_mod = 25;
+ 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;
+ 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);
+ CLEAR(z);
+ ALLOC_ARRAY(array, struct schedule_entry *, n);
- printf ("Creation/Insertion Phase\n");
+ printf("Creation/Insertion Phase\n");
- for (i = 0; i < n; ++i)
+ 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]);
+ 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_randomize_array(array, n);
- /*schedule_print (s);*/
- schedule_verify (s);
+ /*schedule_print (s);*/
+ schedule_verify(s);
- for (j = 1; j <= n_mod; ++j)
+ 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("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);*/
+ /*printf ("INS=%d\n", z.ins);*/
- while ((e = schedule_find_earliest_wakeup (s)))
+ while ((e = schedule_find_earliest_wakeup(s)))
{
- schedule_remove_node (s, e);
- /*schedule_verify (s);*/
+ schedule_remove_node(s, e);
+ /*schedule_verify (s);*/
}
- schedule_verify (s);
+ schedule_verify(s);
- printf ("S->ROOT is %s\n", s->root ? "NOT NULL" : "NULL");
+ printf("S->ROOT is %s\n", s->root ? "NOT NULL" : "NULL");
- for (i = 0; i < n; ++i)
+ for (i = 0; i < n; ++i)
{
- free (array[i]);
+ free(array[i]);
}
- free (array);
- free (s);
- gc_free (&gc);
+ free(array);
+ free(s);
+ gc_free(&gc);
}
-#endif
-#endif
+#endif /* ifdef SCHEDULE_TEST */
+#endif /* if P2MP_SERVER */