/*
  *  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-2018 OpenVPN 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; if not, write to the Free Software Foundation, Inc.,
  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 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  /* if 1 */

 
 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 /* if 1 */

 
 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 /* ifdef SCHEDULE_TEST */
 #endif /* if P2MP_SERVER */