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