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