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