Updated retry timer mechanism to incorporate smoothed RTT estimation.
[gpxe.git] / src / net / retry.c
index fd70426..531a1b9 100644 (file)
  *
  * Retry timers
  *
- * A retry timer is a truncated binary exponential backoff timer.  It
- * can be used to build automatic retransmission into network
- * protocols.
+ * A retry timer is a binary exponential backoff timer.  It can be
+ * used to build automatic retransmission into network protocols.
  */
 
-/** List of running timers */
-static LIST_HEAD ( timers );
+/** Default timeout value */
+#define MIN_TIMEOUT ( TICKS_PER_SEC / 4 )
 
-/**
- * Reload timer
- *
- * @v timer            Retry timer
- *
- * This reloads the timer with a new expiry time.  The expiry time
- * will be the timer's base timeout value, shifted left by the number
- * of retries (i.e. the number of timer expiries since the last timer
- * reset).
- */
-static void reload_timer ( struct retry_timer *timer ) {
-       unsigned int exp;
-
-       exp = timer->retries;
-       if ( exp > BACKOFF_LIMIT )
-               exp = BACKOFF_LIMIT;
-       timer->expiry = currticks() + ( timer->base << exp );
-}
+/** Limit after which the timeout will be deemed permanent */
+#define MAX_TIMEOUT ( 10 * TICKS_PER_SEC )
 
-/**
- * Reset timer
- *
- * @v timer            Retry timer
- *
- * This resets the timer, i.e. clears its retry count and starts it
- * running with its base timeout value.
- *
- * Note that it is explicitly permitted to call reset_timer() on an
- * inactive timer.
+/* The theoretical minimum that the algorithm in stop_timer() can
+ * adjust the timeout back down to is seven ticks, so set the minimum
+ * timeout to at least that value for the sake of consistency.
  */
-void reset_timer ( struct retry_timer *timer ) {
-       timer->retries = 0;
-       reload_timer ( timer );
-}
+#if MIN_TIMEOUT < 7
+#undef MIN_TIMEOUT
+#define MIN_TIMEOUT 7
+#endif
+
+/** List of running timers */
+static LIST_HEAD ( timers );
 
 /**
  * Start timer
  *
  * @v timer            Retry timer
  *
- * This resets the timer and starts it running (i.e. adds it to the
- * list of running timers).  The retry_timer::base and
- * retry_timer::callback fields must have been filled in.
+ * This starts the timer running with the current timeout value.  If
+ * stop_timer() is not called before the timer expires, the timer will
+ * be stopped and the timer's callback function will be called.
  */
 void start_timer ( struct retry_timer *timer ) {
        list_add ( &timer->list, &timers );
-       reset_timer ( timer );
+       timer->start = currticks();
+       if ( timer->timeout < MIN_TIMEOUT )
+               timer->timeout = MIN_TIMEOUT;
 }
 
 /**
@@ -89,11 +70,36 @@ void start_timer ( struct retry_timer *timer ) {
  *
  * @v timer            Retry timer
  *
- * This stops the timer (i.e. removes it from the list of running
- * timers).
+ * This stops the timer and updates the timer's timeout value.
  */
 void stop_timer ( struct retry_timer *timer ) {
+       unsigned long old_timeout = timer->timeout;
+       unsigned long runtime;
+
        list_del ( &timer->list );
+       runtime = currticks() - timer->start;
+
+       /* Update timer.  Variables are:
+        *
+        *   r = round-trip time estimate (i.e. runtime)
+        *   t = timeout value (i.e. timer->timeout)
+        *   s = smoothed round-trip time
+        *
+        * By choice, we set t = 4s, i.e. allow for four times the
+        * normal round-trip time to pass before retransmitting.
+        *
+        * We want to smooth according to s := ( 7 s + r ) / 8
+        *
+        * Since we don't actually store s, this reduces to
+        * t := ( 7 t / 8 ) + ( r / 2 )
+        *
+        */
+       timer->timeout -= ( timer->timeout >> 3 );
+       timer->timeout += ( runtime >> 1 );
+       if ( timer->timeout != old_timeout ) {
+               DBG ( "Timer updated to %dms\n",
+                     ( ( 1000 * timer->timeout ) / TICKS_PER_SEC ) );
+       }
 }
 
 /**
@@ -105,12 +111,22 @@ static void retry_step ( struct process *process ) {
        struct retry_timer *timer;
        struct retry_timer *tmp;
        unsigned long now = currticks();
+       unsigned long used;
+       int fail;
 
        list_for_each_entry_safe ( timer, tmp, &timers, list ) {
-               if ( timer->expiry <= now ) {
-                       timer->retries++;
-                       reload_timer ( timer );
-                       timer->expired ( timer );
+               used = ( now - timer->start );
+               if ( used >= timer->timeout ) {
+                       /* Stop timer without performing RTT calculations */
+                       list_del ( &timer->list );
+                       /* Back off the timeout value */
+                       timer->timeout <<= 1;
+                       if ( ( fail = ( timer->timeout > MAX_TIMEOUT ) ) )
+                               timer->timeout = MAX_TIMEOUT;
+                       DBG ( "Timer backed off to %dms\n",
+                             ( ( 1000 * timer->timeout ) / TICKS_PER_SEC ) );
+                       /* Call expiry callback */
+                       timer->expired ( timer, fail );
                }
        }