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