retry.c

Go to the documentation of this file.

/*
 * Copyright (C) 2006 Michael Brown <mbrown@fensystems.co.uk>.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or any later version.
 *
 * 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; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

FILE_LICENCE ( GPL2_OR_LATER );

#include <stddef.h>
#include <gpxe/timer.h>
#include <gpxe/list.h>
#include <gpxe/process.h>
#include <gpxe/init.h>
#include <gpxe/retry.h>

/** @file
 *
 * Retry timers
 *
 * A retry timer is a binary exponential backoff timer.  It can be
 * used to build automatic retransmission into network protocols.
 *
 * This implementation of the timer is designed to satisfy RFC 2988
 * and therefore be usable as a TCP retransmission timer.
 *
 * 
 */

/* The theoretical minimum that the algorithm in stop_timer() can
 * adjust the timeout back down to is seven ticks, so set the minimum
 * timeout to at least that value for the sake of consistency.
 */
#define MIN_TIMEOUT 7

/** List of running timers */
static LIST_HEAD ( timers );

/**
 * Start timer
 *
 * @v timer             Retry timer
 *
 * This starts the timer running with the current timeout value.  If
 * stop_timer() is not called before the timer expires, the timer will
 * be stopped and the timer's callback function will be called.
 */
void start_timer ( struct retry_timer *timer ) {
        if ( ! timer->running )
                list_add ( &timer->list, &timers );
        timer->start = currticks();
        timer->running = 1;

        /* 0 means "use default timeout" */
        if ( timer->min_timeout == 0 )
                timer->min_timeout = DEFAULT_MIN_TIMEOUT;
        /* We must never be less than MIN_TIMEOUT under any circumstances */
        if ( timer->min_timeout < MIN_TIMEOUT )
                timer->min_timeout = MIN_TIMEOUT;
        /* Honor user-specified minimum timeout */
        if ( timer->timeout < timer->min_timeout )
                timer->timeout = timer->min_timeout;

        DBG2 ( "Timer %p started at time %ld (expires at %ld)\n",
               timer, timer->start, ( timer->start + timer->timeout ) );
}

/**
 * Start timer with a specified fixed timeout
 *
 * @v timer             Retry timer
 * @v timeout           Timeout, in ticks
 */
void start_timer_fixed ( struct retry_timer *timer, unsigned long timeout ) {
        start_timer ( timer );
        timer->timeout = timeout;
        DBG2 ( "Timer %p expiry time changed to %ld\n",
               timer, ( timer->start + timer->timeout ) );
}

/**
 * Stop timer
 *
 * @v timer             Retry timer
 *
 * This stops the timer and updates the timer's timeout value.
 */
void stop_timer ( struct retry_timer *timer ) {
        unsigned long old_timeout = timer->timeout;
        unsigned long now = currticks();
        unsigned long runtime;

        /* If timer was already stopped, do nothing */
        if ( ! timer->running )
                return;

        list_del ( &timer->list );
        runtime = ( now - timer->start );
        timer->running = 0;
        DBG2 ( "Timer %p stopped at time %ld (ran for %ld)\n",
               timer, now, runtime );

        /* Update timer.  Variables are:
         *
         *   r = round-trip time estimate (i.e. runtime)
         *   t = timeout value (i.e. timer->timeout)
         *   s = smoothed round-trip time
         *
         * By choice, we set t = 4s, i.e. allow for four times the
         * normal round-trip time to pass before retransmitting.
         *
         * We want to smooth according to s := ( 7 s + r ) / 8
         *
         * Since we don't actually store s, this reduces to
         * t := ( 7 t / 8 ) + ( r / 2 )
         *
         */
        if ( timer->count ) {
                timer->count--;
        } else {
                timer->timeout -= ( timer->timeout >> 3 );
                timer->timeout += ( runtime >> 1 );
                if ( timer->timeout != old_timeout ) {
                        DBG ( "Timer %p timeout updated to %ld\n",
                              timer, timer->timeout );
                }
        }
}

/**
 * Handle expired timer
 *
 * @v timer             Retry timer
 */
static void timer_expired ( struct retry_timer *timer ) {
        int fail;

        /* Stop timer without performing RTT calculations */
        DBG2 ( "Timer %p stopped at time %ld on expiry\n",
               timer, currticks() );
        assert ( timer->running );
        list_del ( &timer->list );
        timer->running = 0;
        timer->count++;

        /* Back off the timeout value */
        timer->timeout <<= 1;
        if ( timer->max_timeout == 0 ) /* 0 means "use default timeout" */
                timer->max_timeout = DEFAULT_MAX_TIMEOUT;
        if ( ( fail = ( timer->timeout > timer->max_timeout ) ) )
                timer->timeout = timer->max_timeout;
        DBG ( "Timer %p timeout backed off to %ld\n",
              timer, timer->timeout );

        /* Call expiry callback */
        timer->expired ( timer, fail ); 
}

/**
 * Single-step the retry timer list
 *
 * @v process           Retry timer process
 */
static void retry_step ( struct process *process __unused ) {
        struct retry_timer *timer;
        struct retry_timer *tmp;
        unsigned long now = currticks();
        unsigned long used;

        list_for_each_entry_safe ( timer, tmp, &timers, list ) {
                used = ( now - timer->start );
                if ( used >= timer->timeout )
                        timer_expired ( timer );
        }
}

/** Retry timer process */
struct process retry_process __permanent_process = {
        .list = LIST_HEAD_INIT ( retry_process.list ),
        .step = retry_step,
};