src/openvpn/schedule.h

   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-2005 OpenVPN Solutions LLC <info@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 "thread.h"
  46 #include "error.h"
  47
  48 struct schedule_entry
  49 {
  50   struct timeval tv;             /* wakeup time */
  51   unsigned int pri;              /* random treap priority */
  52   struct schedule_entry *parent; /* treap (btree) links */
  53   struct schedule_entry *lt;
  54   struct schedule_entry *gt;
  55 };
  56
  57 struct schedule
  58 {
  59   MUTEX_DEFINE (mutex);
  60   struct schedule_entry *earliest_wakeup; /* cached earliest wakeup */
  61   struct schedule_entry *root;            /* the root of the treap (btree) */
  62 };
  63
  64 /* Public functions */
  65
  66 struct schedule *schedule_init (void);
  67 void schedule_free (struct schedule *s);
  68 void schedule_remove_entry (struct schedule *s, struct schedule_entry *e);
  69
  70 #ifdef SCHEDULE_TEST
  71 void schedule_test (void);
  72 #endif
  73
  74 /* Private Functions */
  75
  76 /* is node already in tree? */
  77 #define IN_TREE(e) ((e)->pri)
  78
  79 struct schedule_entry *schedule_find_least (struct schedule_entry *e);
  80 void schedule_add_modify (struct schedule *s, struct schedule_entry *e);
  81 void schedule_remove_node (struct schedule *s, struct schedule_entry *e);
  82
  83 /* Public inline functions */
  84
  85 /*
  86  * Add a struct schedule_entry (whose storage is managed by
  87  * caller) to the btree.  tv signifies the wakeup time for
  88  * a future event.  sigma is a time interval measured
  89  * in microseconds -- the event window being represented
  90  * starts at (tv - sigma) and ends at (tv + sigma).
  91  * Event signaling can occur anywere within this interval.
  92  * Making the interval larger makes the scheduler more efficient,
  93  * while making it smaller results in more precise scheduling.
  94  * The caller should treat the passed struct schedule_entry as
  95  * an opaque object.
  96  */
  97 static inline void
  98 schedule_add_entry (struct schedule *s,
  99                     struct schedule_entry *e,
 100                     const struct timeval *tv,
 101                     unsigned int sigma)
 102 {
 103   mutex_lock (&s->mutex);
 104   if (!IN_TREE (e) || !sigma || !tv_within_sigma (tv, &e->tv, sigma))
 105     {
 106       e->tv = *tv;
 107       schedule_add_modify (s, e);
 108       s->earliest_wakeup = NULL; /* invalidate cache */
 109     }
 110   mutex_unlock (&s->mutex);
 111 }
 112
 113 /*
 114  * Return the node with the earliest wakeup time.  If two
 115  * nodes have the exact same wakeup time, select based on
 116  * the random priority assigned to each node (the priority
 117  * is randomized every time an entry is re-added).
 118  */
 119 static inline struct schedule_entry *
 120 schedule_get_earliest_wakeup (struct schedule *s,
 121                               struct timeval *wakeup)
 122 {
 123   struct schedule_entry *ret;
 124
 125   mutex_lock (&s->mutex);
 126
 127   /* cache result */
 128   if (!s->earliest_wakeup)
 129     s->earliest_wakeup = schedule_find_least (s->root);
 130   ret = s->earliest_wakeup;
 131   if (ret)
 132     *wakeup = ret->tv;
 133
 134   mutex_unlock (&s->mutex);
 135
 136   return ret;
 137 }
 138
 139 #endif
 140 #endif