iPXE
retry.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2006 Michael Brown <mbrown@fensystems.co.uk>.
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License as
00006  * published by the Free Software Foundation; either version 2 of the
00007  * License, or any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful, but
00010  * WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
00017  * 02110-1301, USA.
00018  *
00019  * You can also choose to distribute this program under the terms of
00020  * the Unmodified Binary Distribution Licence (as given in the file
00021  * COPYING.UBDL), provided that you have satisfied its requirements.
00022  */
00023 
00024 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
00025 
00026 #include <stddef.h>
00027 #include <ipxe/timer.h>
00028 #include <ipxe/list.h>
00029 #include <ipxe/process.h>
00030 #include <ipxe/init.h>
00031 #include <ipxe/retry.h>
00032 
00033 /** @file
00034  *
00035  * Retry timers
00036  *
00037  * A retry timer is a binary exponential backoff timer.  It can be
00038  * used to build automatic retransmission into network protocols.
00039  *
00040  * This implementation of the timer is designed to satisfy RFC 2988
00041  * and therefore be usable as a TCP retransmission timer.
00042  * 
00043  */
00044 
00045 /* The theoretical minimum that the algorithm in stop_timer() can
00046  * adjust the timeout back down to is seven ticks, so set the minimum
00047  * timeout to at least that value for the sake of consistency.
00048  */
00049 #define MIN_TIMEOUT 7
00050 
00051 /** List of running timers */
00052 static LIST_HEAD ( timers );
00053 
00054 /**
00055  * Start timer with a specified timeout
00056  *
00057  * @v timer             Retry timer
00058  * @v timeout           Timeout, in ticks
00059  *
00060  * This starts the timer running with the specified timeout value.  If
00061  * stop_timer() is not called before the timer expires, the timer will
00062  * be stopped and the timer's callback function will be called.
00063  */
00064 void start_timer_fixed ( struct retry_timer *timer, unsigned long timeout ) {
00065 
00066         /* Add to list of running timers (if applicable) */
00067         if ( ! timer->running ) {
00068                 list_add ( &timer->list, &timers );
00069                 ref_get ( timer->refcnt );
00070                 timer->running = 1;
00071         }
00072 
00073         /* Record start time */
00074         timer->start = currticks();
00075 
00076         /* Record timeout */
00077         timer->timeout = timeout;
00078 
00079         DBGC2 ( timer, "Timer %p started at time %ld (expires at %ld)\n",
00080                 timer, timer->start, ( timer->start + timer->timeout ) );
00081 }
00082 
00083 /**
00084  * Start timer
00085  *
00086  * @v timer             Retry timer
00087  *
00088  * This starts the timer running with the current timeout value
00089  * (rounded up to the minimum timeout value).  If stop_timer() is not
00090  * called before the timer expires, the timer will be stopped and the
00091  * timer's callback function will be called.
00092  */
00093 void start_timer ( struct retry_timer *timer ) {
00094         unsigned long timeout = timer->timeout;
00095         unsigned long min;
00096 
00097         /* Calculate minimum timeout */
00098         min = ( timer->min ? timer->min : DEFAULT_MIN_TIMEOUT );
00099         if ( min < MIN_TIMEOUT )
00100                 min = MIN_TIMEOUT;
00101 
00102         /* Ensure timeout is at least the minimum */
00103         if ( timeout < min )
00104                 timeout = min;
00105 
00106         /* Start timer with this timeout */
00107         start_timer_fixed ( timer, timeout );
00108 }
00109 
00110 /**
00111  * Stop timer
00112  *
00113  * @v timer             Retry timer
00114  *
00115  * This stops the timer and updates the timer's timeout value.
00116  */
00117 void stop_timer ( struct retry_timer *timer ) {
00118         unsigned long old_timeout = timer->timeout;
00119         unsigned long now = currticks();
00120         unsigned long runtime;
00121 
00122         /* If timer was already stopped, do nothing */
00123         if ( ! timer->running )
00124                 return;
00125 
00126         list_del ( &timer->list );
00127         runtime = ( now - timer->start );
00128         timer->running = 0;
00129         DBGC2 ( timer, "Timer %p stopped at time %ld (ran for %ld)\n",
00130                 timer, now, runtime );
00131 
00132         /* Update timer.  Variables are:
00133          *
00134          *   r = round-trip time estimate (i.e. runtime)
00135          *   t = timeout value (i.e. timer->timeout)
00136          *   s = smoothed round-trip time
00137          *
00138          * By choice, we set t = 4s, i.e. allow for four times the
00139          * normal round-trip time to pass before retransmitting.
00140          *
00141          * We want to smooth according to s := ( 7 s + r ) / 8
00142          *
00143          * Since we don't actually store s, this reduces to
00144          * t := ( 7 t / 8 ) + ( r / 2 )
00145          *
00146          */
00147         if ( timer->count ) {
00148                 timer->count--;
00149         } else {
00150                 timer->timeout -= ( timer->timeout >> 3 );
00151                 timer->timeout += ( runtime >> 1 );
00152                 if ( timer->timeout != old_timeout ) {
00153                         DBGC ( timer, "Timer %p timeout updated to %ld\n",
00154                                timer, timer->timeout );
00155                 }
00156         }
00157 
00158         ref_put ( timer->refcnt );
00159 }
00160 
00161 /**
00162  * Handle expired timer
00163  *
00164  * @v timer             Retry timer
00165  */
00166 static void timer_expired ( struct retry_timer *timer ) {
00167         struct refcnt *refcnt = timer->refcnt;
00168         unsigned long max = ( timer->max ? timer->max : DEFAULT_MAX_TIMEOUT );
00169         int fail;
00170 
00171         /* Stop timer without performing RTT calculations */
00172         DBGC2 ( timer, "Timer %p stopped at time %ld on expiry\n",
00173                 timer, currticks() );
00174         assert ( timer->running );
00175         list_del ( &timer->list );
00176         timer->running = 0;
00177         timer->count++;
00178 
00179         /* Back off the timeout value */
00180         timer->timeout <<= 1;
00181         if ( ( fail = ( timer->timeout > max ) ) )
00182                 timer->timeout = max;
00183         DBGC ( timer, "Timer %p timeout backed off to %ld\n",
00184                timer, timer->timeout );
00185 
00186         /* Call expiry callback */
00187         timer->expired ( timer, fail );
00188         /* If refcnt is NULL, then timer may already have been freed */
00189 
00190         ref_put ( refcnt );
00191 }
00192 
00193 /**
00194  * Poll the retry timer list
00195  *
00196  */
00197 void retry_poll ( void ) {
00198         struct retry_timer *timer;
00199         unsigned long now = currticks();
00200         unsigned long used;
00201 
00202         /* Process at most one timer expiry.  We cannot process
00203          * multiple expiries in one pass, because one timer expiring
00204          * may end up triggering another timer's deletion from the
00205          * list.
00206          */
00207         list_for_each_entry ( timer, &timers, list ) {
00208                 used = ( now - timer->start );
00209                 if ( used >= timer->timeout ) {
00210                         timer_expired ( timer );
00211                         break;
00212                 }
00213         }
00214 }
00215 
00216 /**
00217  * Single-step the retry timer list
00218  *
00219  * @v process           Retry timer process
00220  */
00221 static void retry_step ( struct process *process __unused ) {
00222         retry_poll();
00223 }
00224 
00225 /** Retry timer process */
00226 PERMANENT_PROCESS ( retry_process, retry_step );