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
68#if defined(__GNUC__) || defined(__clang__)
69#pragma GCC diagnostic push
70#pragma GCC diagnostic ignored "-Wconversion"
71#endif
72
73static inline void
75{
76 e->pri = random();
77 if (e->pri < 1)
78 {
79 e->pri = 1;
80 }
81}
82
83#if defined(__GNUC__) || defined(__clang__)
84#pragma GCC diagnostic pop
85#endif
86
87/* This is the master key comparison routine. A key is
88 * simply a struct timeval containing the absolute time for
89 * an event. The unique treap priority (pri) is used to ensure
90 * that keys do not collide.
91 */
92static inline int
93schedule_entry_compare(const struct schedule_entry *e1, 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 */
134static 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 */
177static 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 */
251void
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 */
288static 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
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 */
347void
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 {
361 }
362
363 /* set random priority */
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 /* This is the magic of the randomized treap algorithm which
375 * keeps the tree balanced. Move the node up the tree until
376 * its own priority is greater than that of its parent */
377 while (e->parent && e->parent->pri > e->pri)
378 {
379 schedule_rotate_up(s, e);
380 }
381}
382
383/*
384 * Find the earliest event to be scheduled
385 */
386struct schedule_entry *
388{
389 if (e)
390 {
391 while (e->lt)
392 {
393#ifdef SCHEDULE_TEST
394 ++z.lsteps;
395#endif
396 e = e->lt;
397 }
398 }
399
400#ifdef ENABLE_DEBUG
402 {
403 schedule_entry_debug_info("schedule_find_least", e);
404 }
405#endif
406
407 return e;
408}
409
410/*
411 * Public functions below this point
412 */
413
414struct schedule *
416{
417 struct schedule *s;
418
419 ALLOC_OBJ_CLEAR(s, struct schedule);
420 return s;
421}
422
423void
425{
426 free(s);
427}
428
429void
431{
432 s->earliest_wakeup = NULL; /* invalidate cache */
434}
435
436/*
437 * Debug functions below this point
438 */
439
440#ifdef SCHEDULE_TEST
441
442static inline struct schedule_entry *
443schedule_find_earliest_wakeup(struct schedule *s)
444{
445 return schedule_find_least(s->root);
446}
447
448/*
449 * Recursively check that the treap (btree) is
450 * internally consistent.
451 */
452int
453schedule_debug_entry(const struct schedule_entry *e, int depth, int *count, struct timeval *least,
454 const struct timeval *min, const struct timeval *max)
455{
456 struct gc_arena gc = gc_new();
457 int maxdepth = depth;
458 if (e)
459 {
460 int d;
461
462 ASSERT(e != e->lt);
463 ASSERT(e != e->gt);
464 ASSERT(e != e->parent);
465 ASSERT(!e->parent || e->parent != e->lt);
466 ASSERT(!e->parent || e->parent != e->gt);
467 ASSERT(!e->lt || e->lt != e->gt);
468
469 if (e->lt)
470 {
471 ASSERT(e->lt->parent == e);
472 ASSERT(schedule_entry_compare(e->lt, e) == -1);
473 ASSERT(e->lt->pri >= e->pri);
474 }
475
476 if (e->gt)
477 {
478 ASSERT(e->gt->parent == e);
480 ASSERT(e->gt->pri >= e->pri);
481 }
482
483 ASSERT(tv_le(min, &e->tv));
484 ASSERT(tv_le(&e->tv, max));
485
486 if (count)
487 {
488 ++(*count);
489 }
490
491 if (least && tv_lt(&e->tv, least))
492 {
493 *least = e->tv;
494 }
495
496 d = schedule_debug_entry(e->lt, depth + 1, count, least, min, &e->tv);
497 if (d > maxdepth)
498 {
499 maxdepth = d;
500 }
501
502 d = schedule_debug_entry(e->gt, depth + 1, count, least, &e->tv, max);
503 if (d > maxdepth)
504 {
505 maxdepth = d;
506 }
507 }
508 gc_free(&gc);
509 return maxdepth;
510}
511
512int
513schedule_debug(struct schedule *s, int *count, struct timeval *least)
514{
515 struct timeval min;
516 struct timeval max;
517
518 min.tv_sec = 0;
519 min.tv_usec = 0;
520 max.tv_sec = 0x7FFFFFFF;
521 max.tv_usec = 0x7FFFFFFF;
522
523 if (s->root)
524 {
525 ASSERT(s->root->parent == NULL);
526 }
527 return schedule_debug_entry(s->root, 0, count, least, &min, &max);
528}
529
530#if 1
531
532void
533tv_randomize(struct timeval *tv)
534{
535 tv->tv_sec += random() % 100;
536 tv->tv_usec = random() % 100;
537}
538
539#else /* if 1 */
540
541void
542tv_randomize(struct timeval *tv)
543{
544 struct gc_arena gc = gc_new();
545 long int choice = get_random();
546 if ((choice & 0xFF) == 0)
547 {
548 tv->tv_usec += ((choice >> 8) & 0xFF);
549 }
550 else
551 {
552 prng_bytes((uint8_t *)tv, sizeof(struct timeval));
553 }
554 gc_free(&gc);
555}
556
557#endif /* if 1 */
558
559void
560schedule_verify(struct schedule *s)
561{
562 struct gc_arena gc = gc_new();
563 struct timeval least;
564 int count;
565 int maxlev;
566 struct schedule_entry *e;
567 const struct status zz = z;
568
569 least.tv_sec = least.tv_usec = 0x7FFFFFFF;
570
571 count = 0;
572
573 maxlev = schedule_debug(s, &count, &least);
574
575 e = schedule_find_earliest_wakeup(s);
576
577 if (e)
578 {
579 printf("Verification Phase count=%d maxlev=%d sru=%d ins=%d coll=%d ls=%d l=%s", count,
580 maxlev, zz.sru, zz.ins, zz.coll, zz.lsteps, tv_string(&e->tv, &gc));
581
582 if (!tv_eq(&least, &e->tv))
583 {
584 printf(" [COMPUTED DIFFERENT MIN VALUES!]");
585 }
586
587 printf("\n");
588 }
589
590 CLEAR(z);
591 gc_free(&gc);
592}
593
594void
595schedule_randomize_array(struct schedule_entry **array, int size)
596{
597 int i;
598 for (i = 0; i < size; ++i)
599 {
600 const int src = get_random() % size;
601 struct schedule_entry *tmp = array[i];
602 if (i != src)
603 {
604 array[i] = array[src];
605 array[src] = tmp;
606 }
607 }
608}
609
610void
611schedule_print_work(struct schedule_entry *e, int indent)
612{
613 struct gc_arena gc = gc_new();
614 int i;
615 for (i = 0; i < indent; ++i)
616 {
617 printf(" ");
618 }
619 if (e)
620 {
621 printf("%s [%u] e=" ptr_format ", p=" ptr_format " lt=" ptr_format " gt=" ptr_format "\n",
622 tv_string(&e->tv, &gc), e->pri, (ptr_type)e, (ptr_type)e->parent, (ptr_type)e->lt,
623 (ptr_type)e->gt);
624 schedule_print_work(e->lt, indent + 1);
625 schedule_print_work(e->gt, indent + 1);
626 }
627 else
628 {
629 printf("NULL\n");
630 }
631 gc_free(&gc);
632}
633
634void
635schedule_print(struct schedule *s)
636{
637 printf("*************************\n");
638 schedule_print_work(s->root, 0);
639}
640
641void
642schedule_test(void)
643{
644 struct gc_arena gc = gc_new();
645 int n = 1000;
646 int n_mod = 25;
647
648 int i, j;
649 struct schedule_entry **array;
650 struct schedule *s = schedule_init();
651 struct schedule_entry *e;
652
653 CLEAR(z);
654 ALLOC_ARRAY(array, struct schedule_entry *, n);
655
656 printf("Creation/Insertion Phase\n");
657
658 for (i = 0; i < n; ++i)
659 {
660 ALLOC_OBJ_CLEAR(array[i], struct schedule_entry);
661 tv_randomize(&array[i]->tv);
662 /*schedule_print (s);*/
663 /*schedule_verify (s);*/
664 schedule_add_modify(s, array[i]);
665 }
666
667 schedule_randomize_array(array, n);
668
669 /*schedule_print (s);*/
670 schedule_verify(s);
671
672 for (j = 1; j <= n_mod; ++j)
673 {
674 printf("Modification Phase Pass %d\n", j);
675
676 for (i = 0; i < n; ++i)
677 {
678 e = schedule_find_earliest_wakeup(s);
679 /*printf ("BEFORE %s\n", tv_string (&e->tv, &gc));*/
680 tv_randomize(&e->tv);
681 /*printf ("AFTER %s\n", tv_string (&e->tv, &gc));*/
683 /*schedule_verify (s);*/
684 /*schedule_print (s);*/
685 }
686 schedule_verify(s);
687 /*schedule_print (s);*/
688 }
689
690 /*printf ("INS=%d\n", z.ins);*/
691
692 while ((e = schedule_find_earliest_wakeup(s)))
693 {
695 /*schedule_verify (s);*/
696 }
697 schedule_verify(s);
698
699 printf("S->ROOT is %s\n", s->root ? "NOT NULL" : "NULL");
700
701 for (i = 0; i < n; ++i)
702 {
703 free(array[i]);
704 }
705 free(array);
706 free(s);
707 gc_free(&gc);
708}
709
710#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:1718
long int get_random(void)
Definition crypto.c:1725
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(msglvl_t level)
Definition error.h:259
#define dmsg(flags,...)
Definition error.h:172
#define ASSERT(x)
Definition error.h:219
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:167
static bool tv_eq(const struct timeval *t1, const struct timeval *t2)
Definition otime.h:218
static bool tv_lt(const struct timeval *t1, const struct timeval *t2)
Definition otime.h:150
static void schedule_set_pri(struct schedule_entry *e)
Definition schedule.c:74
static void schedule_rotate_up(struct schedule *s, struct schedule_entry *e)
Definition schedule.c:178
void schedule_remove_entry(struct schedule *s, struct schedule_entry *e)
Definition schedule.c:430
struct schedule * schedule_init(void)
Definition schedule.c:415
void schedule_remove_node(struct schedule *s, struct schedule_entry *e)
Definition schedule.c:252
struct schedule_entry * schedule_find_least(struct schedule_entry *e)
Definition schedule.c:387
static int schedule_entry_compare(const struct schedule_entry *e1, const struct schedule_entry *e2)
Definition schedule.c:93
void schedule_add_modify(struct schedule *s, struct schedule_entry *e)
Definition schedule.c:348
static void schedule_insert(struct schedule *s, struct schedule_entry *e)
Definition schedule.c:289
void schedule_free(struct schedule *s)
Definition schedule.c:424
static void schedule_detach_parent(struct schedule *s, struct schedule_entry *e)
Definition schedule.c:135
#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:131