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 <gpxe/timer.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 /* The theoretical minimum that the algorithm in stop_timer() can
  40  * adjust the timeout back down to is seven ticks, so set the minimum
  41  * timeout to at least that value for the sake of consistency.
  42  */
  43 #define MIN_TIMEOUT 7
  44
  45 /** List of running timers */
  46 static LIST_HEAD ( timers );
  47
  48 /**
  49  * Start timer
  50  *
  51  * @v timer             Retry timer
  52  *
  53  * This starts the timer running with the current timeout value.  If
  54  * stop_timer() is not called before the timer expires, the timer will
  55  * be stopped and the timer's callback function will be called.
  56  */
  57 void start_timer ( struct retry_timer *timer ) {
  58         if ( ! timer->running )
  59                 list_add ( &timer->list, &timers );
  60         timer->start = currticks();
  61         timer->running = 1;
  62
  63         /* 0 means "use default timeout" */
  64         if ( timer->min_timeout == 0 )
  65                 timer->min_timeout = DEFAULT_MIN_TIMEOUT;
  66         /* We must never be less than MIN_TIMEOUT under any circumstances */
  67         if ( timer->min_timeout < MIN_TIMEOUT )
  68                 timer->min_timeout = MIN_TIMEOUT;
  69         /* Honor user-specified minimum timeout */
  70         if ( timer->timeout < timer->min_timeout )
  71                 timer->timeout = timer->min_timeout;
  72
  73         DBG2 ( "Timer %p started at time %ld (expires at %ld)\n",
  74                timer, timer->start, ( timer->start + timer->timeout ) );
  75 }
  76
  77 /**
  78  * Start timer with a specified fixed timeout
  79  *
  80  * @v timer             Retry timer
  81  * @v timeout           Timeout, in ticks
  82  */
  83 void start_timer_fixed ( struct retry_timer *timer, unsigned long timeout ) {
  84         start_timer ( timer );
  85         timer->timeout = timeout;
  86         DBG2 ( "Timer %p expiry time changed to %ld\n",
  87                timer, ( timer->start + timer->timeout ) );
  88 }
  89
  90 /**
  91  * Stop timer
  92  *
  93  * @v timer             Retry timer
  94  *
  95  * This stops the timer and updates the timer's timeout value.
  96  */
  97 void stop_timer ( struct retry_timer *timer ) {
  98         unsigned long old_timeout = timer->timeout;
  99         unsigned long now = currticks();
 100         unsigned long runtime;
 101
 102         /* If timer was already stopped, do nothing */
 103         if ( ! timer->running )
 104                 return;
 105
 106         list_del ( &timer->list );
 107         runtime = ( now - timer->start );
 108         timer->running = 0;
 109         DBG2 ( "Timer %p stopped at time %ld (ran for %ld)\n",
 110                timer, now, runtime );
 111
 112         /* Update timer.  Variables are:
 113          *
 114          *   r = round-trip time estimate (i.e. runtime)
 115          *   t = timeout value (i.e. timer->timeout)
 116          *   s = smoothed round-trip time
 117          *
 118          * By choice, we set t = 4s, i.e. allow for four times the
 119          * normal round-trip time to pass before retransmitting.
 120          *
 121          * We want to smooth according to s := ( 7 s + r ) / 8
 122          *
 123          * Since we don't actually store s, this reduces to
 124          * t := ( 7 t / 8 ) + ( r / 2 )
 125          *
 126          */
 127         if ( timer->count ) {
 128                 timer->count--;
 129         } else {
 130                 timer->timeout -= ( timer->timeout >> 3 );
 131                 timer->timeout += ( runtime >> 1 );
 132                 if ( timer->timeout != old_timeout ) {
 133                         DBG ( "Timer %p timeout updated to %ld\n",
 134                               timer, timer->timeout );
 135                 }
 136         }
 137 }
 138
 139 /**
 140  * Handle expired timer
 141  *
 142  * @v timer             Retry timer
 143  */
 144 static void timer_expired ( struct retry_timer *timer ) {
 145         int fail;
 146
 147         /* Stop timer without performing RTT calculations */
 148         DBG2 ( "Timer %p stopped at time %ld on expiry\n",
 149                timer, currticks() );
 150         assert ( timer->running );
 151         list_del ( &timer->list );
 152         timer->running = 0;
 153         timer->count++;
 154
 155         /* Back off the timeout value */
 156         timer->timeout <<= 1;
 157         if ( timer->max_timeout == 0 ) /* 0 means "use default timeout" */
 158                 timer->max_timeout = DEFAULT_MAX_TIMEOUT;
 159         if ( ( fail = ( timer->timeout > timer->max_timeout ) ) )
 160                 timer->timeout = timer->max_timeout;
 161         DBG ( "Timer %p timeout backed off to %ld\n",
 162               timer, timer->timeout );
 163
 164         /* Call expiry callback */
 165         timer->expired ( timer, fail );
 166 }
 167
 168 /**
 169  * Single-step the retry timer list
 170  *
 171  * @v process           Retry timer process
 172  */
 173 static void retry_step ( struct process *process __unused ) {
 174         struct retry_timer *timer;
 175         struct retry_timer *tmp;
 176         unsigned long now = currticks();
 177         unsigned long used;
 178
 179         list_for_each_entry_safe ( timer, tmp, &timers, list ) {
 180                 used = ( now - timer->start );
 181                 if ( used >= timer->timeout )
 182                         timer_expired ( timer );
 183         }
 184 }
 185
 186 /** Retry timer process */
 187 struct process retry_process __permanent_process = {
 188         .step = retry_step,
 189 };