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