/*
* OpenVPN -- An application to securely tunnel IP networks
* over a single TCP/UDP port, with support for SSL/TLS-based
* session authentication and key exchange,
* packet encryption, packet authentication, and
* packet compression.
*
* Copyright (C) 2002-2009 OpenVPN Technologies, Inc. <sales@openvpn.net>
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2
* as published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program (see the file COPYING included with this
* distribution); if not, write to the Free Software Foundation, Inc.,
* 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
#ifndef SCHEDULE_H
#define SCHEDULE_H
/*
* This code implements an efficient scheduler using
* a random treap binary tree.
*
* The scheduler is used by the server executive to
* keep track of which instances need service at a
* known time in the future. Instances need to
* schedule events for things such as sending
* a ping or scheduling a TLS renegotiation.
*/
#if P2MP_SERVER
/* define to enable a special test mode */
/*#define SCHEDULE_TEST*/
#include "otime.h"
#include "thread.h"
#include "error.h"
struct schedule_entry
{
struct timeval tv; /* wakeup time */
unsigned int pri; /* random treap priority */
struct schedule_entry *parent; /* treap (btree) links */
struct schedule_entry *lt;
struct schedule_entry *gt;
};
struct schedule
{
MUTEX_DEFINE (mutex);
struct schedule_entry *earliest_wakeup; /* cached earliest wakeup */
struct schedule_entry *root; /* the root of the treap (btree) */
};
/* Public functions */
struct schedule *schedule_init (void);
void schedule_free (struct schedule *s);
void schedule_remove_entry (struct schedule *s, struct schedule_entry *e);
#ifdef SCHEDULE_TEST
void schedule_test (void);
#endif
/* Private Functions */
/* is node already in tree? */
#define IN_TREE(e) ((e)->pri)
struct schedule_entry *schedule_find_least (struct schedule_entry *e);
void schedule_add_modify (struct schedule *s, struct schedule_entry *e);
void schedule_remove_node (struct schedule *s, struct schedule_entry *e);
/* Public inline functions */
/*
* Add a struct schedule_entry (whose storage is managed by
* caller) to the btree. tv signifies the wakeup time for
* a future event. sigma is a time interval measured
* in microseconds -- the event window being represented
* starts at (tv - sigma) and ends at (tv + sigma).
* Event signaling can occur anywere within this interval.
* Making the interval larger makes the scheduler more efficient,
* while making it smaller results in more precise scheduling.
* The caller should treat the passed struct schedule_entry as
* an opaque object.
*/
static inline void
schedule_add_entry (struct schedule *s,
struct schedule_entry *e,
const struct timeval *tv,
unsigned int sigma)
{
mutex_lock (&s->mutex);
if (!IN_TREE (e) || !sigma || !tv_within_sigma (tv, &e->tv, sigma))
{
e->tv = *tv;
schedule_add_modify (s, e);
s->earliest_wakeup = NULL; /* invalidate cache */
}
mutex_unlock (&s->mutex);
}
/*
* Return the node with the earliest wakeup time. If two
* nodes have the exact same wakeup time, select based on
* the random priority assigned to each node (the priority
* is randomized every time an entry is re-added).
*/
static inline struct schedule_entry *
schedule_get_earliest_wakeup (struct schedule *s,
struct timeval *wakeup)
{
struct schedule_entry *ret;
mutex_lock (&s->mutex);
/* cache result */
if (!s->earliest_wakeup)
s->earliest_wakeup = schedule_find_least (s->root);
ret = s->earliest_wakeup;
if (ret)
*wakeup = ret->tv;
mutex_unlock (&s->mutex);
return ret;
}
#endif
#endif
