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