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