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
schedule_entry_debug_info(const char * caller,const struct schedule_entry * e)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
schedule_set_pri(struct schedule_entry * e)75 schedule_set_pri(struct schedule_entry *e)
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
schedule_entry_compare(const struct schedule_entry * e1,const struct schedule_entry * e2)90 schedule_entry_compare(const struct schedule_entry *e1,
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
schedule_detach_parent(struct schedule * s,struct schedule_entry * e)133 schedule_detach_parent(struct schedule *s, struct schedule_entry *e)
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
schedule_rotate_up(struct schedule * s,struct schedule_entry * e)176 schedule_rotate_up(struct schedule *s, struct schedule_entry *e)
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
schedule_remove_node(struct schedule * s,struct schedule_entry * e)250 schedule_remove_node(struct schedule *s, struct schedule_entry *e)
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
278 schedule_detach_parent(s, e);
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
schedule_insert(struct schedule * s,struct schedule_entry * e)287 schedule_insert(struct schedule *s, struct schedule_entry *e)
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
schedule_add_modify(struct schedule * s,struct schedule_entry * e)346 schedule_add_modify(struct schedule *s, struct schedule_entry *e)
347 {
348 #ifdef ENABLE_DEBUG
349 if (check_debug_level(D_SCHEDULER))
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 *
schedule_find_least(struct schedule_entry * e)386 schedule_find_least(struct schedule_entry *e)
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
400 if (check_debug_level(D_SCHEDULER))
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 *
schedule_init(void)414 schedule_init(void)
415 {
416 struct schedule *s;
417
418 ALLOC_OBJ_CLEAR(s, struct schedule);
419 return s;
420 }
421
422 void
schedule_free(struct schedule * s)423 schedule_free(struct schedule *s)
424 {
425 free(s);
426 }
427
428 void
schedule_remove_entry(struct schedule * s,struct schedule_entry * e)429 schedule_remove_entry(struct schedule *s, struct schedule_entry *e)
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 *
schedule_find_earliest_wakeup(struct schedule * s)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
schedule_debug_entry(const struct schedule_entry * e,int depth,int * count,struct timeval * least,const struct timeval * min,const struct timeval * max)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);
482 ASSERT(schedule_entry_compare(e->gt, 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
schedule_debug(struct schedule * s,int * count,struct timeval * least)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
tv_randomize(struct timeval * tv)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
tv_randomize(struct timeval * tv)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
schedule_verify(struct schedule * s)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
schedule_randomize_array(struct schedule_entry ** array,int size)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
schedule_print_work(struct schedule_entry * e,int indent)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
schedule_print(struct schedule * s)648 schedule_print(struct schedule *s)
649 {
650 printf("*************************\n");
651 schedule_print_work(s->root, 0);
652 }
653
654 void
schedule_test(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 */
724