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->start )
  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\n", timer );
  73 }
  74
  75 /**
  76  * Stop timer
  77  *
  78  * @v timer             Retry timer
  79  *
  80  * This stops the timer and updates the timer's timeout value.
  81  */
  82 void stop_timer ( struct retry_timer *timer ) {
  83         unsigned long old_timeout = timer->timeout;
  84         unsigned long runtime;
  85
  86         /* If timer was already stopped, do nothing */
  87         if ( ! timer->start )
  88                 return;
  89
  90         DBG2 ( "Timer %p stopped\n", timer );
  91         list_del ( &timer->list );
  92         runtime = currticks() - timer->start;
  93         timer->start = 0;
  94
  95         /* Update timer.  Variables are:
  96          *
  97          *   r = round-trip time estimate (i.e. runtime)
  98          *   t = timeout value (i.e. timer->timeout)
  99          *   s = smoothed round-trip time
 100          *
 101          * By choice, we set t = 4s, i.e. allow for four times the
 102          * normal round-trip time to pass before retransmitting.
 103          *
 104          * We want to smooth according to s := ( 7 s + r ) / 8
 105          *
 106          * Since we don't actually store s, this reduces to
 107          * t := ( 7 t / 8 ) + ( r / 2 )
 108          *
 109          */
 110         if ( timer->count ) {
 111                 timer->count--;
 112         } else {
 113                 timer->timeout -= ( timer->timeout >> 3 );
 114                 timer->timeout += ( runtime >> 1 );
 115                 if ( timer->timeout != old_timeout ) {
 116                         DBG ( "Timer %p updated to %ldms\n", timer,
 117                               ( ( 1000 * timer->timeout ) / TICKS_PER_SEC ) );
 118                 }
 119         }
 120 }
 121
 122 /**
 123  * Handle expired timer
 124  *
 125  * @v timer             Retry timer
 126  */
 127 static void timer_expired ( struct retry_timer *timer ) {
 128         int fail;
 129
 130         /* Stop timer without performing RTT calculations */
 131         DBG2 ( "Timer %p stopped on expiry\n", timer );
 132         list_del ( &timer->list );
 133         timer->start = 0;
 134         timer->count++;
 135
 136         /* Back off the timeout value */
 137         timer->timeout <<= 1;
 138         if ( ( fail = ( timer->timeout > MAX_TIMEOUT ) ) )
 139                 timer->timeout = MAX_TIMEOUT;
 140         DBG ( "Timer %p backed off to %ldms\n", timer,
 141               ( ( 1000 * timer->timeout ) / TICKS_PER_SEC ) );
 142
 143         /* Call expiry callback */
 144         timer->expired ( timer, fail );
 145 }
 146
 147 /**
 148  * Single-step the retry timer list
 149  *
 150  * @v process           Retry timer process
 151  */
 152 static void retry_step ( struct process *process ) {
 153         struct retry_timer *timer;
 154         struct retry_timer *tmp;
 155         unsigned long now = currticks();
 156         unsigned long used;
 157
 158         list_for_each_entry_safe ( timer, tmp, &timers, list ) {
 159                 used = ( now - timer->start );
 160                 if ( used >= timer->timeout )
 161                         timer_expired ( timer );
 162         }
 163
 164         schedule ( process );
 165 }
 166
 167 /** Retry timer process */
 168 static struct process retry_process = {
 169         .step = retry_step,
 170 };
 171
 172 /** Initialise the retry timer module */
 173 static void init_retry ( void ) {
 174         schedule ( &retry_process );
 175 }
 176
 177 INIT_FN ( INIT_PROCESS, init_retry, NULL, NULL );