src/openvpn/schedule.c

   1 /*
   2  *  OpenVPN -- An application to securely tunnel IP networks
   3  *             over a single TCP/UDP port, with support for SSL/TLS-based
   4  *             session authentication and key exchange,
   5  *             packet encryption, packet authentication, and
   6  *             packet compression.
   7  *
   8  *  Copyright (C) 2002-2005 OpenVPN Solutions LLC <info@openvpn.net>
   9  *
  10  *  This program is free software; you can redistribute it and/or modify
  11  *  it under the terms of the GNU General Public License version 2
  12  *  as published by the Free Software Foundation.
  13  *
  14  *  This program is distributed in the hope that it will be useful,
  15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  *  GNU General Public License for more details.
  18  *
  19  *  You should have received a copy of the GNU General Public License
  20  *  along with this program (see the file COPYING included with this
  21  *  distribution); if not, write to the Free Software Foundation, Inc.,
  22  *  59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  23  */
  24
  25 #ifdef WIN32
  26 #include "config-win32.h"
  27 #else
  28 #include "config.h"
  29 #endif
  30
  31 #include "syshead.h"
  32
  33 #if P2MP_SERVER
  34
  35 #include "buffer.h"
  36 #include "misc.h"
  37 #include "crypto.h"
  38 #include "schedule.h"
  39
  40 #include "memdbg.h"
  41
  42 #ifdef SCHEDULE_TEST
  43
  44 struct status
  45 {
  46   int sru;
  47   int ins;
  48   int coll;
  49   int lsteps;
  50 };
  51
  52 static struct status z;
  53
  54 #endif
  55
  56 #ifdef ENABLE_DEBUG
  57 static void
  58 schedule_entry_debug_info (const char *caller, const struct schedule_entry *e)
  59 {
  60   struct gc_arena gc = gc_new ();
  61   if (e)
  62     {
  63       dmsg (D_SCHEDULER, "SCHEDULE: %s wakeup=[%s] pri=%u",
  64            caller,
  65            tv_string_abs (&e->tv, &gc),
  66            e->pri);
  67     }
  68   else
  69     {
  70       dmsg (D_SCHEDULER, "SCHEDULE: %s NULL",
  71            caller);
  72     }
  73   gc_free (&gc);
  74 }
  75 #endif
  76
  77 static inline void
  78 schedule_set_pri (struct schedule_entry *e)
  79 {
  80   e->pri = random ();
  81   if (e->pri < 1)
  82     e->pri = 1;
  83 }
  84
  85 /* This is the master key comparison routine.  A key is
  86  * simply a struct timeval containing the absolute time for
  87  * an event.  The unique treap priority (pri) is used to ensure
  88  * that keys do not collide.
  89  */
  90 static inline int
  91 schedule_entry_compare (const struct schedule_entry *e1,
  92                         const struct schedule_entry *e2)
  93 {
  94   if (e1->tv.tv_sec < e2->tv.tv_sec)
  95     return -1;
  96   else if (e1->tv.tv_sec > e2->tv.tv_sec)
  97     return 1;
  98   else
  99     {
 100       if (e1->tv.tv_usec < e2->tv.tv_usec)
 101         return -1;
 102       else if (e1->tv.tv_usec > e2->tv.tv_usec)
 103         return 1;
 104       else
 105         {
 106           if (e1->pri < e2->pri)
 107             return -1;
 108           else if (e1->pri > e2->pri)
 109             return 1;
 110           else
 111             return 0;
 112         }
 113     }
 114 }
 115
 116 /*
 117  * Detach a btree node from its parent
 118  */
 119 static inline void
 120 schedule_detach_parent (struct schedule *s, struct schedule_entry *e)
 121 {
 122   if (e)
 123     {
 124       if (e->parent)
 125         {
 126           if (e->parent->lt == e)
 127             e->parent->lt = NULL;
 128           else if (e->parent->gt == e)
 129             e->parent->gt = NULL;
 130           else
 131             {
 132               /* parent <-> child linkage is corrupted */
 133               ASSERT (0);
 134             }
 135           e->parent = NULL;
 136         }
 137       else
 138         {
 139           if (s->root == e) /* last element deleted, tree is empty */
 140             s->root = NULL;
 141         }
 142     }
 143 }
 144
 145 /*
 146  *
 147  * Given a binary search tree, move a node toward the root
 148  * while still maintaining the correct ordering relationships
 149  * within the tree.  This function is the workhorse
 150  * of the tree balancer.
 151  *
 152  * This code will break on key collisions, which shouldn't
 153  * happen because the treap priority is considered part of the key
 154  * and is guaranteed to be unique.
 155  */
 156 static void
 157 schedule_rotate_up (struct schedule *s, struct schedule_entry *e)
 158 {
 159   if (e && e->parent)
 160     {
 161       struct schedule_entry *lt = e->lt;
 162       struct schedule_entry *gt = e->gt;
 163       struct schedule_entry *p = e->parent;
 164       struct schedule_entry *gp = p->parent;
 165
 166       if (gp) /* if grandparent exists, modify its child link */
 167         {
 168           if (gp->gt == p)
 169             gp->gt = e;
 170           else if (gp->lt == p)
 171             gp->lt = e;
 172           else
 173             {
 174               ASSERT (0);
 175             }
 176         }
 177       else /* no grandparent, now we are the root */
 178         {
 179           s->root = e;
 180         }
 181
 182       /* grandparent is now our parent */
 183       e->parent = gp;
 184
 185       /* parent is now our child */
 186       p->parent = e;
 187
 188       /* reorient former parent's links
 189          to reflect new position in the tree */
 190       if (p->gt == e)
 191         {
 192           e->lt = p;
 193           p->gt = lt;
 194           if (lt)
 195             lt->parent = p;
 196         }
 197       else if (p->lt == e)
 198         {
 199           e->gt = p;
 200           p->lt = gt;
 201           if (gt)
 202             gt->parent = p;
 203         }
 204       else
 205         {
 206           /* parent <-> child linkage is corrupted */
 207           ASSERT (0);
 208         }
 209
 210 #ifdef SCHEDULE_TEST
 211       ++z.sru;
 212 #endif
 213     }
 214 }
 215
 216 /*
 217  * This is the treap deletion algorithm:
 218  *
 219  * Rotate lesser-priority children up in the tree
 220  * until we are childless.  Then delete.
 221  */
 222 void
 223 schedule_remove_node (struct schedule *s, struct schedule_entry *e)
 224 {
 225   while (e->lt || e->gt)
 226     {
 227       if (e->lt)
 228         {
 229           if (e->gt)
 230             {
 231               if (e->lt->pri < e->gt->pri)
 232                 schedule_rotate_up (s, e->lt);
 233               else
 234                 schedule_rotate_up (s, e->gt);
 235             }
 236           else
 237             schedule_rotate_up (s, e->lt);
 238         }
 239       else if (e->gt)
 240         schedule_rotate_up (s, e->gt);
 241     }
 242
 243   schedule_detach_parent (s, e);
 244   e->pri = 0;
 245 }
 246
 247 /*
 248  * Trivially add a node to a binary search tree without
 249  * regard for balance.
 250  */
 251 static void
 252 schedule_insert (struct schedule *s, struct schedule_entry *e)
 253 {
 254   struct schedule_entry *c = s->root;
 255   while (true)
 256     {
 257       const int comp = schedule_entry_compare (e, c);
 258
 259 #ifdef SCHEDULE_TEST
 260       ++z.ins;
 261 #endif
 262
 263       if (comp == -1)
 264         {
 265           if (c->lt)
 266             {
 267               c = c->lt;
 268               continue;
 269             }
 270           else
 271             {
 272               c->lt = e;
 273               e->parent = c;
 274               break;
 275             }
 276         }
 277       else if (comp == 1)
 278         {
 279           if (c->gt)
 280             {
 281               c = c->gt;
 282               continue;
 283             }
 284           else
 285             {
 286               c->gt = e;
 287               e->parent = c;
 288               break;
 289             }
 290         }
 291       else
 292         {
 293           /* rare key/priority collision -- no big deal,
 294              just choose another priority and retry */
 295 #ifdef SCHEDULE_TEST
 296           ++z.coll;
 297 #endif
 298           schedule_set_pri (e);
 299           /* msg (M_INFO, "PRI COLLISION pri=%u", e->pri); */
 300           c = s->root;
 301           continue;
 302         }
 303     }
 304 }
 305
 306 /*
 307  * Given an element, remove it from the btree if it's already
 308  * there and re-insert it based on its current key.
 309  */
 310 void
 311 schedule_add_modify (struct schedule *s, struct schedule_entry *e)
 312 {
 313 #ifdef ENABLE_DEBUG
 314   if (check_debug_level (D_SCHEDULER))
 315     schedule_entry_debug_info ("schedule_add_modify", e);
 316 #endif
 317
 318   /* already in tree, remove */
 319   if (IN_TREE (e))
 320     schedule_remove_node (s, e);
 321
 322   /* set random priority */
 323   schedule_set_pri (e);
 324
 325   if (s->root)
 326     schedule_insert (s, e);      /* trivial insert into tree */
 327   else
 328     s->root = e; /* tree was empty, we are the first element */
 329
 330   /* This is the magic of the randomized treap algorithm which
 331      keeps the tree balanced.  Move the node up the tree until
 332      its own priority is greater than that of its parent */
 333   while (e->parent && e->parent->pri > e->pri)
 334     schedule_rotate_up (s, e);
 335 }
 336
 337 /*
 338  * Find the earliest event to be scheduled
 339  */
 340 struct schedule_entry *
 341 schedule_find_least (struct schedule_entry *e)
 342 {
 343   if (e)
 344     {
 345       while (e->lt)
 346         {
 347 #ifdef SCHEDULE_TEST
 348           ++z.lsteps;
 349 #endif
 350           e = e->lt;
 351         }
 352     }
 353
 354 #ifdef ENABLE_DEBUG
 355   if (check_debug_level (D_SCHEDULER))
 356     schedule_entry_debug_info ("schedule_find_least", e);
 357 #endif
 358
 359   return e;
 360 }
 361
 362 /*
 363  *  Public functions below this point
 364  */
 365
 366 struct schedule *
 367 schedule_init (void)
 368 {
 369   struct schedule *s;
 370
 371   ALLOC_OBJ_CLEAR (s, struct schedule);
 372   mutex_init (&s->mutex);
 373   return s;
 374 }
 375
 376 void
 377 schedule_free (struct schedule *s)
 378 {
 379   mutex_destroy (&s->mutex);
 380   free (s);
 381 }
 382
 383 void
 384 schedule_remove_entry (struct schedule *s, struct schedule_entry *e)
 385 {
 386   mutex_lock (&s->mutex);
 387   s->earliest_wakeup = NULL; /* invalidate cache */
 388   schedule_remove_node (s, e);
 389   mutex_unlock (&s->mutex);
 390 }
 391
 392 /*
 393  *  Debug functions below this point
 394  */
 395
 396 #ifdef SCHEDULE_TEST
 397
 398 static inline struct schedule_entry *
 399 schedule_find_earliest_wakeup (struct schedule *s)
 400 {
 401   return schedule_find_least (s->root);
 402 }
 403
 404 /*
 405  * Recursively check that the treap (btree) is
 406  * internally consistent.
 407  */
 408 int
 409 schedule_debug_entry (const struct schedule_entry* e,
 410                       int depth,
 411                       int *count,
 412                       struct timeval *least,
 413                       const struct timeval *min,
 414                       const struct timeval *max)
 415 {
 416   struct gc_arena gc = gc_new ();
 417   int maxdepth = depth;
 418   if (e)
 419     {
 420       int d;
 421
 422       ASSERT (e != e->lt);
 423       ASSERT (e != e->gt);
 424       ASSERT (e != e->parent);
 425       ASSERT (!e->parent || e->parent != e->lt);
 426       ASSERT (!e->parent || e->parent != e->gt);
 427       ASSERT (!e->lt || e->lt != e->gt);
 428
 429       if (e->lt)
 430         {
 431           ASSERT (e->lt->parent == e);
 432           ASSERT (schedule_entry_compare (e->lt, e) == -1);
 433           ASSERT (e->lt->pri >= e->pri);
 434         }
 435
 436       if (e->gt)
 437         {
 438           ASSERT (e->gt->parent == e);
 439           ASSERT (schedule_entry_compare (e->gt, e));
 440           ASSERT (e->gt->pri >= e->pri);
 441         }
 442
 443       ASSERT (tv_le (min, &e->tv));
 444       ASSERT (tv_le (&e->tv, max));
 445
 446       if (count)
 447         ++(*count);
 448
 449       if (least && tv_lt (&e->tv, least))
 450         *least = e->tv;
 451
 452       d = schedule_debug_entry (e->lt, depth+1, count, least, min, &e->tv);
 453       if (d > maxdepth)
 454         maxdepth = d;
 455
 456       d = schedule_debug_entry (e->gt, depth+1, count, least, &e->tv, max);
 457       if (d > maxdepth)
 458         maxdepth = d;
 459     }
 460   gc_free (&gc);
 461   return maxdepth;
 462 }
 463
 464 int
 465 schedule_debug (struct schedule *s, int *count, struct timeval *least)
 466 {
 467   struct timeval min;
 468   struct timeval max;
 469
 470   min.tv_sec = 0;
 471   min.tv_usec = 0;
 472   max.tv_sec = 0x7FFFFFFF;
 473   max.tv_usec = 0x7FFFFFFF;
 474
 475   if (s->root)
 476     {
 477       ASSERT (s->root->parent == NULL);
 478     }
 479   return schedule_debug_entry (s->root, 0, count, least, &min, &max);
 480 }
 481
 482 #if 1
 483
 484 void
 485 tv_randomize (struct timeval *tv)
 486 {
 487   tv->tv_sec += random() % 100;
 488   tv->tv_usec = random () % 100;
 489 }
 490
 491 #else
 492
 493 void
 494 tv_randomize (struct timeval *tv)
 495 {
 496   struct gc_arena gc = gc_new ();
 497   long int choice = get_random ();
 498   if ((choice & 0xFF) == 0)
 499     tv->tv_usec += ((choice >> 8) & 0xFF);
 500   else
 501     prng_bytes ((uint8_t *)tv, sizeof (struct timeval));
 502   gc_free (&gc);
 503 }
 504
 505 #endif
 506
 507 void
 508 schedule_verify (struct schedule *s)
 509 {
 510   struct gc_arena gc = gc_new ();
 511   struct timeval least;
 512   int count;
 513   int maxlev;
 514   struct schedule_entry* e;
 515   const struct status zz = z;
 516
 517   least.tv_sec = least.tv_usec = 0x7FFFFFFF;
 518
 519   count = 0;
 520
 521   maxlev = schedule_debug (s, &count, &least);
 522
 523   e = schedule_find_earliest_wakeup (s);
 524
 525   if (e)
 526     {
 527       printf ("Verification Phase  count=%d maxlev=%d sru=%d ins=%d coll=%d ls=%d l=%s",
 528               count,
 529               maxlev,
 530               zz.sru,
 531               zz.ins,
 532               zz.coll,
 533               zz.lsteps,
 534               tv_string (&e->tv, &gc));
 535
 536       if (!tv_eq (&least, &e->tv))
 537         printf (" [COMPUTED DIFFERENT MIN VALUES!]");
 538
 539       printf ("\n");
 540     }
 541
 542   CLEAR (z);
 543   gc_free (&gc);
 544 }
 545
 546 void
 547 schedule_randomize_array (struct schedule_entry **array, int size)
 548 {
 549   int i;
 550   for (i = 0; i < size; ++i)
 551     {
 552       const int src = get_random () % size;
 553       struct schedule_entry *tmp = array [i];
 554       if (i != src)
 555         {
 556           array [i] = array [src];
 557           array [src] = tmp;
 558         }
 559     }
 560 }
 561
 562 void
 563 schedule_print_work (struct schedule_entry *e, int indent)
 564 {
 565   struct gc_arena gc = gc_new ();
 566   int i;
 567   for (i = 0; i < indent; ++i)
 568     printf (" ");
 569   if (e)
 570     {
 571       printf ("%s [%u] e=" ptr_format ", p=" ptr_format " lt=" ptr_format " gt=" ptr_format "\n",
 572               tv_string (&e->tv, &gc),
 573               e->pri,
 574               (ptr_type)e,
 575               (ptr_type)e->parent,
 576               (ptr_type)e->lt,
 577               (ptr_type)e->gt);
 578       schedule_print_work (e->lt, indent+1);
 579       schedule_print_work (e->gt, indent+1);
 580     }
 581   else
 582     printf ("NULL\n");
 583   gc_free (&gc);
 584 }
 585
 586 void
 587 schedule_print (struct schedule *s)
 588 {
 589   printf ("*************************\n");
 590   schedule_print_work (s->root, 0);
 591 }
 592
 593 void
 594 schedule_test (void)
 595 {
 596   struct gc_arena gc = gc_new ();
 597   int n = 1000;
 598   int n_mod = 25;
 599
 600   int i, j;
 601   struct schedule_entry **array;
 602   struct schedule *s = schedule_init ();
 603   struct schedule_entry* e;
 604
 605   CLEAR (z);
 606   ALLOC_ARRAY (array, struct schedule_entry *, n);
 607
 608   printf ("Creation/Insertion Phase\n");
 609
 610   for (i = 0; i < n; ++i)
 611     {
 612       ALLOC_OBJ_CLEAR (array[i], struct schedule_entry);
 613       tv_randomize (&array[i]->tv);
 614       /*schedule_print (s);*/
 615       /*schedule_verify (s);*/
 616       schedule_add_modify (s, array[i]);
 617     }
 618
 619   schedule_randomize_array (array, n);
 620
 621   /*schedule_print (s);*/
 622   schedule_verify (s);
 623
 624   for (j = 1; j <= n_mod; ++j)
 625     {
 626       printf ("Modification Phase Pass %d\n", j);
 627
 628       for (i = 0; i < n; ++i)
 629         {
 630           e = schedule_find_earliest_wakeup (s);
 631           /*printf ("BEFORE %s\n", tv_string (&e->tv, &gc));*/
 632           tv_randomize (&e->tv);
 633           /*printf ("AFTER %s\n", tv_string (&e->tv, &gc));*/
 634           schedule_add_modify (s, e);
 635           /*schedule_verify (s);*/
 636           /*schedule_print (s);*/
 637         }
 638       schedule_verify (s);
 639       /*schedule_print (s);*/
 640     }
 641
 642   /*printf ("INS=%d\n", z.ins);*/
 643
 644   while ((e = schedule_find_earliest_wakeup (s)))
 645     {
 646       schedule_remove_node (s, e);
 647       /*schedule_verify (s);*/
 648     }
 649   schedule_verify (s);
 650
 651   printf ("S->ROOT is %s\n", s->root ? "NOT NULL" : "NULL");
 652
 653   for (i = 0; i < n; ++i)
 654     {
 655       free (array[i]);
 656     }
 657   free (array);
 658   free (s);
 659   gc_free (&gc);
 660 }
 661
 662 #endif
 663 #endif