src/net/retry.c

   1 /*
   2  * Copyright (C) 2006 Michael Brown <mbrown@fensystems.co.uk>.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License as
   6  * published by the Free Software Foundation; either version 2 of the
   7  * License, or any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17  */
  18
  19 #include <stddef.h>
  20 #include <latch.h>
  21 #include <gpxe/list.h>
  22 #include <gpxe/process.h>
  23 #include <gpxe/init.h>
  24 #include <gpxe/retry.h>
  25
  26 /** @file
  27  *
  28  * Retry timers
  29  *
  30  * A retry timer is a binary exponential backoff timer.  It can be
  31  * used to build automatic retransmission into network protocols.
  32  *
  33  * This implementation of the timer is designed to satisfy RFC 2988
  34  * and therefore be usable as a TCP retransmission timer.
  35  *
  36  *
  37  */
  38
  39 /** Default timeout value */
  40 #define MIN_TIMEOUT ( TICKS_PER_SEC / 4 )
  41
  42 /** Limit after which the timeout will be deemed permanent */
  43 #define MAX_TIMEOUT ( 10 * TICKS_PER_SEC )
  44
  45 /* The theoretical minimum that the algorithm in stop_timer() can
  46  * adjust the timeout back down to is seven ticks, so set the minimum
  47  * timeout to at least that value for the sake of consistency.
  48  */
  49 #if MIN_TIMEOUT < 7
  50 #undef MIN_TIMEOUT
  51 #define MIN_TIMEOUT 7
  52 #endif
  53
  54 /** List of running timers */
  55 static LIST_HEAD ( timers );
  56
  57 /**
  58  * Start timer
  59  *
  60  * @v timer             Retry timer
  61  *
  62  * This starts the timer running with the current timeout value.  If
  63  * stop_timer() is not called before the timer expires, the timer will
  64  * be stopped and the timer's callback function will be called.
  65  */
  66 void start_timer ( struct retry_timer *timer ) {
  67         if ( ! timer_running ( timer ) )
  68                 list_add ( &timer->list, &timers );
  69         timer->start = currticks();
  70         if ( timer->timeout < MIN_TIMEOUT )
  71                 timer->timeout = MIN_TIMEOUT;
  72         DBG2 ( "Timer %p started at time %ld (expires at %ld)\n",
  73                timer, timer->start, ( timer->start + timer->timeout ) );
  74 }
  75
  76 /**
  77  * Start timer with no delay
  78  *
  79  * @v timer             Retry timer
  80  *
  81  * This starts the timer running with a zero timeout value.
  82  */
  83 void start_timer_nodelay ( struct retry_timer *timer ) {
  84         start_timer ( timer );
  85         timer->timeout = 0;
  86 }
  87
  88 /**
  89  * Stop timer
  90  *
  91  * @v timer             Retry timer
  92  *
  93  * This stops the timer and updates the timer's timeout value.
  94  */
  95 void stop_timer ( struct retry_timer *timer ) {
  96         unsigned long old_timeout = timer->timeout;
  97         unsigned long now = currticks();
  98         unsigned long runtime;
  99
 100         /* If timer was already stopped, do nothing */
 101         if ( ! timer_running ( timer ) )
 102                 return;
 103
 104         list_del ( &timer->list );
 105         runtime = ( now - timer->start );
 106         timer->start = 0;
 107         DBG2 ( "Timer %p stopped at time %ld (ran for %ld)\n",
 108                timer, now, runtime );
 109
 110         /* Update timer.  Variables are:
 111          *
 112          *   r = round-trip time estimate (i.e. runtime)
 113          *   t = timeout value (i.e. timer->timeout)
 114          *   s = smoothed round-trip time
 115          *
 116          * By choice, we set t = 4s, i.e. allow for four times the
 117          * normal round-trip time to pass before retransmitting.
 118          *
 119          * We want to smooth according to s := ( 7 s + r ) / 8
 120          *
 121          * Since we don't actually store s, this reduces to
 122          * t := ( 7 t / 8 ) + ( r / 2 )
 123          *
 124          */
 125         if ( timer->count ) {
 126                 timer->count--;
 127         } else {
 128                 timer->timeout -= ( timer->timeout >> 3 );
 129                 timer->timeout += ( runtime >> 1 );
 130                 if ( timer->timeout != old_timeout ) {
 131                         DBG ( "Timer %p timeout updated to %ld\n",
 132                               timer, timer->timeout );
 133                 }
 134         }
 135 }
 136
 137 /**
 138  * Handle expired timer
 139  *
 140  * @v timer             Retry timer
 141  */
 142 static void timer_expired ( struct retry_timer *timer ) {
 143         int fail;
 144
 145         /* Stop timer without performing RTT calculations */
 146         DBG2 ( "Timer %p stopped at time %ld on expiry\n",
 147                timer, currticks() );
 148         list_del ( &timer->list );
 149         timer->start = 0;
 150         timer->count++;
 151
 152         /* Back off the timeout value */
 153         timer->timeout <<= 1;
 154         if ( ( fail = ( timer->timeout > MAX_TIMEOUT ) ) )
 155                 timer->timeout = MAX_TIMEOUT;
 156         DBG ( "Timer %p timeout backed off to %ld\n",
 157               timer, timer->timeout );
 158
 159         /* Call expiry callback */
 160         timer->expired ( timer, fail );
 161 }
 162
 163 /**
 164  * Single-step the retry timer list
 165  *
 166  * @v process           Retry timer process
 167  */
 168 static void retry_step ( struct process *process __unused ) {
 169         struct retry_timer *timer;
 170         struct retry_timer *tmp;
 171         unsigned long now = currticks();
 172         unsigned long used;
 173
 174         list_for_each_entry_safe ( timer, tmp, &timers, list ) {
 175                 used = ( now - timer->start );
 176                 if ( used >= timer->timeout )
 177                         timer_expired ( timer );
 178         }
 179 }
 180
 181 /** Retry timer process */
 182 struct process retry_process __permanent_process = {
 183         .step = retry_step,
 184 };