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