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
  34 /** Default timeout value */
  35 #define MIN_TIMEOUT ( TICKS_PER_SEC / 4 )
  36
  37 /** Limit after which the timeout will be deemed permanent */
  38 #define MAX_TIMEOUT ( 10 * TICKS_PER_SEC )
  39
  40 /* The theoretical minimum that the algorithm in stop_timer() can
  41  * adjust the timeout back down to is seven ticks, so set the minimum
  42  * timeout to at least that value for the sake of consistency.
  43  */
  44 #if MIN_TIMEOUT < 7
  45 #undef MIN_TIMEOUT
  46 #define MIN_TIMEOUT 7
  47 #endif
  48
  49 /** List of running timers */
  50 static LIST_HEAD ( timers );
  51
  52 /**
  53  * Start timer
  54  *
  55  * @v timer             Retry timer
  56  *
  57  * This starts the timer running with the current timeout value.  If
  58  * stop_timer() is not called before the timer expires, the timer will
  59  * be stopped and the timer's callback function will be called.
  60  */
  61 void start_timer ( struct retry_timer *timer ) {
  62         list_add ( &timer->list, &timers );
  63         timer->start = currticks();
  64         if ( timer->timeout < MIN_TIMEOUT )
  65                 timer->timeout = MIN_TIMEOUT;
  66 }
  67
  68 /**
  69  * Stop timer
  70  *
  71  * @v timer             Retry timer
  72  *
  73  * This stops the timer and updates the timer's timeout value.
  74  */
  75 void stop_timer ( struct retry_timer *timer ) {
  76         unsigned long old_timeout = timer->timeout;
  77         unsigned long runtime;
  78
  79         list_del ( &timer->list );
  80         runtime = currticks() - timer->start;
  81
  82         /* Update timer.  Variables are:
  83          *
  84          *   r = round-trip time estimate (i.e. runtime)
  85          *   t = timeout value (i.e. timer->timeout)
  86          *   s = smoothed round-trip time
  87          *
  88          * By choice, we set t = 4s, i.e. allow for four times the
  89          * normal round-trip time to pass before retransmitting.
  90          *
  91          * We want to smooth according to s := ( 7 s + r ) / 8
  92          *
  93          * Since we don't actually store s, this reduces to
  94          * t := ( 7 t / 8 ) + ( r / 2 )
  95          *
  96          */
  97         timer->timeout -= ( timer->timeout >> 3 );
  98         timer->timeout += ( runtime >> 1 );
  99         if ( timer->timeout != old_timeout ) {
 100                 DBG ( "Timer updated to %dms\n",
 101                       ( ( 1000 * timer->timeout ) / TICKS_PER_SEC ) );
 102         }
 103 }
 104
 105 /**
 106  * Single-step the retry timer list
 107  *
 108  * @v process           Retry timer process
 109  */
 110 static void retry_step ( struct process *process ) {
 111         struct retry_timer *timer;
 112         struct retry_timer *tmp;
 113         unsigned long now = currticks();
 114         unsigned long used;
 115         int fail;
 116
 117         list_for_each_entry_safe ( timer, tmp, &timers, list ) {
 118                 used = ( now - timer->start );
 119                 if ( used >= timer->timeout ) {
 120                         /* Stop timer without performing RTT calculations */
 121                         list_del ( &timer->list );
 122                         /* Back off the timeout value */
 123                         timer->timeout <<= 1;
 124                         if ( ( fail = ( timer->timeout > MAX_TIMEOUT ) ) )
 125                                 timer->timeout = MAX_TIMEOUT;
 126                         DBG ( "Timer backed off to %dms\n",
 127                               ( ( 1000 * timer->timeout ) / TICKS_PER_SEC ) );
 128                         /* Call expiry callback */
 129                         timer->expired ( timer, fail );
 130                 }
 131         }
 132
 133         schedule ( process );
 134 }
 135
 136 /** Retry timer process */
 137 static struct process retry_process = {
 138         .step = retry_step,
 139 };
 140
 141 /** Initialise the retry timer module */
 142 static void init_retry ( void ) {
 143         schedule ( &retry_process );
 144 }
 145
 146 INIT_FN ( INIT_PROCESS, init_retry, NULL, NULL );