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
8 * Copyright (C) 2002-2005 OpenVPN Solutions LLC <info@openvpn.net>
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.
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.
19 * You should have received a copy of the GNU General Public License
20 * along with this program (see the file COPYING included with this
21 * distribution); if not, write to the Free Software Foundation, Inc.,
22 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
26 #include "config-win32.h"
52 static struct status z
;
58 schedule_entry_debug_info (const char *caller
, const struct schedule_entry
*e
)
60 struct gc_arena gc
= gc_new ();
63 dmsg (D_SCHEDULER
, "SCHEDULE: %s wakeup=[%s] pri=%u",
65 tv_string_abs (&e
->tv
, &gc
),
70 dmsg (D_SCHEDULER
, "SCHEDULE: %s NULL",
78 schedule_set_pri (struct schedule_entry
*e
)
85 /* This is the master key comparison routine. A key is
86 * simply a struct timeval containing the absolute time for
87 * an event. The unique treap priority (pri) is used to ensure
88 * that keys do not collide.
91 schedule_entry_compare (const struct schedule_entry
*e1
,
92 const struct schedule_entry
*e2
)
94 if (e1
->tv
.tv_sec
< e2
->tv
.tv_sec
)
96 else if (e1
->tv
.tv_sec
> e2
->tv
.tv_sec
)
100 if (e1
->tv
.tv_usec
< e2
->tv
.tv_usec
)
102 else if (e1
->tv
.tv_usec
> e2
->tv
.tv_usec
)
106 if (e1
->pri
< e2
->pri
)
108 else if (e1
->pri
> e2
->pri
)
117 * Detach a btree node from its parent
120 schedule_detach_parent (struct schedule
*s
, struct schedule_entry
*e
)
126 if (e
->parent
->lt
== e
)
127 e
->parent
->lt
= NULL
;
128 else if (e
->parent
->gt
== e
)
129 e
->parent
->gt
= NULL
;
132 /* parent <-> child linkage is corrupted */
139 if (s
->root
== e
) /* last element deleted, tree is empty */
147 * Given a binary search tree, move a node toward the root
148 * while still maintaining the correct ordering relationships
149 * within the tree. This function is the workhorse
150 * of the tree balancer.
152 * This code will break on key collisions, which shouldn't
153 * happen because the treap priority is considered part of the key
154 * and is guaranteed to be unique.
157 schedule_rotate_up (struct schedule
*s
, struct schedule_entry
*e
)
161 struct schedule_entry
*lt
= e
->lt
;
162 struct schedule_entry
*gt
= e
->gt
;
163 struct schedule_entry
*p
= e
->parent
;
164 struct schedule_entry
*gp
= p
->parent
;
166 if (gp
) /* if grandparent exists, modify its child link */
170 else if (gp
->lt
== p
)
177 else /* no grandparent, now we are the root */
182 /* grandparent is now our parent */
185 /* parent is now our child */
188 /* reorient former parent's links
189 to reflect new position in the tree */
206 /* parent <-> child linkage is corrupted */
217 * This is the treap deletion algorithm:
219 * Rotate lesser-priority children up in the tree
220 * until we are childless. Then delete.
223 schedule_remove_node (struct schedule
*s
, struct schedule_entry
*e
)
225 while (e
->lt
|| e
->gt
)
231 if (e
->lt
->pri
< e
->gt
->pri
)
232 schedule_rotate_up (s
, e
->lt
);
234 schedule_rotate_up (s
, e
->gt
);
237 schedule_rotate_up (s
, e
->lt
);
240 schedule_rotate_up (s
, e
->gt
);
243 schedule_detach_parent (s
, e
);
248 * Trivially add a node to a binary search tree without
249 * regard for balance.
252 schedule_insert (struct schedule
*s
, struct schedule_entry
*e
)
254 struct schedule_entry
*c
= s
->root
;
257 const int comp
= schedule_entry_compare (e
, c
);
293 /* rare key/priority collision -- no big deal,
294 just choose another priority and retry */
298 schedule_set_pri (e
);
299 /* msg (M_INFO, "PRI COLLISION pri=%u", e->pri); */
307 * Given an element, remove it from the btree if it's already
308 * there and re-insert it based on its current key.
311 schedule_add_modify (struct schedule
*s
, struct schedule_entry
*e
)
314 if (check_debug_level (D_SCHEDULER
))
315 schedule_entry_debug_info ("schedule_add_modify", e
);
318 /* already in tree, remove */
320 schedule_remove_node (s
, e
);
322 /* set random priority */
323 schedule_set_pri (e
);
326 schedule_insert (s
, e
); /* trivial insert into tree */
328 s
->root
= e
; /* tree was empty, we are the first element */
330 /* This is the magic of the randomized treap algorithm which
331 keeps the tree balanced. Move the node up the tree until
332 its own priority is greater than that of its parent */
333 while (e
->parent
&& e
->parent
->pri
> e
->pri
)
334 schedule_rotate_up (s
, e
);
338 * Find the earliest event to be scheduled
340 struct schedule_entry
*
341 schedule_find_least (struct schedule_entry
*e
)
355 if (check_debug_level (D_SCHEDULER
))
356 schedule_entry_debug_info ("schedule_find_least", e
);
363 * Public functions below this point
371 ALLOC_OBJ_CLEAR (s
, struct schedule
);
372 mutex_init (&s
->mutex
);
377 schedule_free (struct schedule
*s
)
379 mutex_destroy (&s
->mutex
);
384 schedule_remove_entry (struct schedule
*s
, struct schedule_entry
*e
)
386 mutex_lock (&s
->mutex
);
387 s
->earliest_wakeup
= NULL
; /* invalidate cache */
388 schedule_remove_node (s
, e
);
389 mutex_unlock (&s
->mutex
);
393 * Debug functions below this point
398 static inline struct schedule_entry
*
399 schedule_find_earliest_wakeup (struct schedule
*s
)
401 return schedule_find_least (s
->root
);
405 * Recursively check that the treap (btree) is
406 * internally consistent.
409 schedule_debug_entry (const struct schedule_entry
* e
,
412 struct timeval
*least
,
413 const struct timeval
*min
,
414 const struct timeval
*max
)
416 struct gc_arena gc
= gc_new ();
417 int maxdepth
= depth
;
424 ASSERT (e
!= e
->parent
);
425 ASSERT (!e
->parent
|| e
->parent
!= e
->lt
);
426 ASSERT (!e
->parent
|| e
->parent
!= e
->gt
);
427 ASSERT (!e
->lt
|| e
->lt
!= e
->gt
);
431 ASSERT (e
->lt
->parent
== e
);
432 ASSERT (schedule_entry_compare (e
->lt
, e
) == -1);
433 ASSERT (e
->lt
->pri
>= e
->pri
);
438 ASSERT (e
->gt
->parent
== e
);
439 ASSERT (schedule_entry_compare (e
->gt
, e
));
440 ASSERT (e
->gt
->pri
>= e
->pri
);
443 ASSERT (tv_le (min
, &e
->tv
));
444 ASSERT (tv_le (&e
->tv
, max
));
449 if (least
&& tv_lt (&e
->tv
, least
))
452 d
= schedule_debug_entry (e
->lt
, depth
+1, count
, least
, min
, &e
->tv
);
456 d
= schedule_debug_entry (e
->gt
, depth
+1, count
, least
, &e
->tv
, max
);
465 schedule_debug (struct schedule
*s
, int *count
, struct timeval
*least
)
472 max
.tv_sec
= 0x7FFFFFFF;
473 max
.tv_usec
= 0x7FFFFFFF;
477 ASSERT (s
->root
->parent
== NULL
);
479 return schedule_debug_entry (s
->root
, 0, count
, least
, &min
, &max
);
485 tv_randomize (struct timeval
*tv
)
487 tv
->tv_sec
+= random() % 100;
488 tv
->tv_usec
= random () % 100;
494 tv_randomize (struct timeval
*tv
)
496 struct gc_arena gc
= gc_new ();
497 long int choice
= get_random ();
498 if ((choice
& 0xFF) == 0)
499 tv
->tv_usec
+= ((choice
>> 8) & 0xFF);
501 prng_bytes ((uint8_t *)tv
, sizeof (struct timeval
));
508 schedule_verify (struct schedule
*s
)
510 struct gc_arena gc
= gc_new ();
511 struct timeval least
;
514 struct schedule_entry
* e
;
515 const struct status zz
= z
;
517 least
.tv_sec
= least
.tv_usec
= 0x7FFFFFFF;
521 maxlev
= schedule_debug (s
, &count
, &least
);
523 e
= schedule_find_earliest_wakeup (s
);
527 printf ("Verification Phase count=%d maxlev=%d sru=%d ins=%d coll=%d ls=%d l=%s",
534 tv_string (&e
->tv
, &gc
));
536 if (!tv_eq (&least
, &e
->tv
))
537 printf (" [COMPUTED DIFFERENT MIN VALUES!]");
547 schedule_randomize_array (struct schedule_entry
**array
, int size
)
550 for (i
= 0; i
< size
; ++i
)
552 const int src
= get_random () % size
;
553 struct schedule_entry
*tmp
= array
[i
];
556 array
[i
] = array
[src
];
563 schedule_print_work (struct schedule_entry
*e
, int indent
)
565 struct gc_arena gc
= gc_new ();
567 for (i
= 0; i
< indent
; ++i
)
571 printf ("%s [%u] e=" ptr_format
", p=" ptr_format
" lt=" ptr_format
" gt=" ptr_format
"\n",
572 tv_string (&e
->tv
, &gc
),
578 schedule_print_work (e
->lt
, indent
+1);
579 schedule_print_work (e
->gt
, indent
+1);
587 schedule_print (struct schedule
*s
)
589 printf ("*************************\n");
590 schedule_print_work (s
->root
, 0);
596 struct gc_arena gc
= gc_new ();
601 struct schedule_entry
**array
;
602 struct schedule
*s
= schedule_init ();
603 struct schedule_entry
* e
;
606 ALLOC_ARRAY (array
, struct schedule_entry
*, n
);
608 printf ("Creation/Insertion Phase\n");
610 for (i
= 0; i
< n
; ++i
)
612 ALLOC_OBJ_CLEAR (array
[i
], struct schedule_entry
);
613 tv_randomize (&array
[i
]->tv
);
614 /*schedule_print (s);*/
615 /*schedule_verify (s);*/
616 schedule_add_modify (s
, array
[i
]);
619 schedule_randomize_array (array
, n
);
621 /*schedule_print (s);*/
624 for (j
= 1; j
<= n_mod
; ++j
)
626 printf ("Modification Phase Pass %d\n", j
);
628 for (i
= 0; i
< n
; ++i
)
630 e
= schedule_find_earliest_wakeup (s
);
631 /*printf ("BEFORE %s\n", tv_string (&e->tv, &gc));*/
632 tv_randomize (&e
->tv
);
633 /*printf ("AFTER %s\n", tv_string (&e->tv, &gc));*/
634 schedule_add_modify (s
, e
);
635 /*schedule_verify (s);*/
636 /*schedule_print (s);*/
639 /*schedule_print (s);*/
642 /*printf ("INS=%d\n", z.ins);*/
644 while ((e
= schedule_find_earliest_wakeup (s
)))
646 schedule_remove_node (s
, e
);
647 /*schedule_verify (s);*/
651 printf ("S->ROOT is %s\n", s
->root
? "NOT NULL" : "NULL");
653 for (i
= 0; i
< n
; ++i
)