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-2010 OpenVPN Technologies, 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 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 23 */ 24 25#ifndef SCHEDULE_H 26#define SCHEDULE_H 27 28/* 29 * This code implements an efficient scheduler using 30 * a random treap binary tree. 31 * 32 * The scheduler is used by the server executive to 33 * keep track of which instances need service at a 34 * known time in the future. Instances need to 35 * schedule events for things such as sending 36 * a ping or scheduling a TLS renegotiation. 37 */ 38 39#if P2MP_SERVER 40 41/* define to enable a special test mode */ 42/*#define SCHEDULE_TEST*/ 43 44#include "otime.h" 45#include "error.h" 46 47struct schedule_entry 48{ 49 struct timeval tv; /* wakeup time */ 50 unsigned int pri; /* random treap priority */ 51 struct schedule_entry *parent; /* treap (btree) links */ 52 struct schedule_entry *lt; 53 struct schedule_entry *gt; 54}; 55 56struct schedule 57{ 58 struct schedule_entry *earliest_wakeup; /* cached earliest wakeup */ 59 struct schedule_entry *root; /* the root of the treap (btree) */ 60}; 61 62/* Public functions */ 63 64struct schedule *schedule_init (void); 65void schedule_free (struct schedule *s); 66void schedule_remove_entry (struct schedule *s, struct schedule_entry *e); 67 68#ifdef SCHEDULE_TEST 69void schedule_test (void); 70#endif 71 72/* Private Functions */ 73 74/* is node already in tree? */ 75#define IN_TREE(e) ((e)->pri) 76 77struct schedule_entry *schedule_find_least (struct schedule_entry *e); 78void schedule_add_modify (struct schedule *s, struct schedule_entry *e); 79void schedule_remove_node (struct schedule *s, struct schedule_entry *e); 80 81/* Public inline functions */ 82 83/* 84 * Add a struct schedule_entry (whose storage is managed by 85 * caller) to the btree. tv signifies the wakeup time for 86 * a future event. sigma is a time interval measured 87 * in microseconds -- the event window being represented 88 * starts at (tv - sigma) and ends at (tv + sigma). 89 * Event signaling can occur anywere within this interval. 90 * Making the interval larger makes the scheduler more efficient, 91 * while making it smaller results in more precise scheduling. 92 * The caller should treat the passed struct schedule_entry as 93 * an opaque object. 94 */ 95static inline void 96schedule_add_entry (struct schedule *s, 97 struct schedule_entry *e, 98 const struct timeval *tv, 99 unsigned int sigma) 100{ 101 if (!IN_TREE (e) || !sigma || !tv_within_sigma (tv, &e->tv, sigma)) 102 { 103 e->tv = *tv; 104 schedule_add_modify (s, e); 105 s->earliest_wakeup = NULL; /* invalidate cache */ 106 } 107} 108 109/* 110 * Return the node with the earliest wakeup time. If two 111 * nodes have the exact same wakeup time, select based on 112 * the random priority assigned to each node (the priority 113 * is randomized every time an entry is re-added). 114 */ 115static inline struct schedule_entry * 116schedule_get_earliest_wakeup (struct schedule *s, 117 struct timeval *wakeup) 118{ 119 struct schedule_entry *ret; 120 121 /* cache result */ 122 if (!s->earliest_wakeup) 123 s->earliest_wakeup = schedule_find_least (s->root); 124 ret = s->earliest_wakeup; 125 if (ret) 126 *wakeup = ret->tv; 127 128 return ret; 129} 130 131#endif 132#endif 133