Updated retry timer mechanism to incorporate smoothed RTT estimation.
authorMichael Brown <mcb30@etherboot.org>
Thu, 1 Jun 2006 14:33:52 +0000 (14:33 +0000)
committerMichael Brown <mcb30@etherboot.org>
Thu, 1 Jun 2006 14:33:52 +0000 (14:33 +0000)
AoE now uses the retry timer mechanism.

src/include/gpxe/retry.h
src/net/aoe.c
src/net/retry.c

index 8a9e2cf..8f197bc 100644 (file)
@@ -9,28 +9,27 @@
 
 #include <gpxe/list.h>
 
-/** Effective maximum retry count for exponential backoff calculation */
-#define BACKOFF_LIMIT 5
-
 /** A retry timer */
 struct retry_timer {
        /** List of active timers */
        struct list_head list;
-       /** Base timeout (in ticks) */
-       unsigned int base;
-       /** Retry count */
-       unsigned int retries;
-       /** Expiry time (in ticks) */
-       unsigned long expiry;
+       /** Timeout value (in ticks) */
+       unsigned long timeout;
+       /** Start time (in ticks) */
+       unsigned long start;
        /** Timer expired callback
         *
         * @v timer     Retry timer
+        * @v fail      Failure indicator
+        *
+        * The timer will already be stopped when this method is
+        * called.  The failure indicator will be True if the retry
+        * timeout has already exceeded @c MAX_TIMEOUT.
         */
-       void ( * expired ) ( struct retry_timer *timer );
+       void ( * expired ) ( struct retry_timer *timer, int over );
 };
 
 extern void start_timer ( struct retry_timer *timer );
-extern void reset_timer ( struct retry_timer *timer );
 extern void stop_timer ( struct retry_timer *timer );
 
 #endif /* _GPXE_RETRY_H */
index 198bbb5..1e9eb32 100644 (file)
@@ -115,9 +115,27 @@ static int aoe_send_command ( struct aoe_session *aoe ) {
                         aoe->command_offset, data_out_len );
 
        /* Send packet */
+       start_timer ( &aoe->timer );
        return net_transmit_via ( pkb, aoe->netdev );
 }
 
+/**
+ * Handle AoE retry timer expiry
+ *
+ * @v timer            AoE retry timer
+ * @v fail             Failure indicator
+ */
+static void aoe_timer_expired ( struct retry_timer *timer, int fail ) {
+       struct aoe_session *aoe =
+               container_of ( timer, struct aoe_session, timer );
+
+       if ( fail ) {
+               aoe_done ( aoe, -ETIMEDOUT );
+       } else {
+               aoe_send_command ( aoe );
+       }
+}
+
 /**
  * Handle AoE response
  *
@@ -134,10 +152,18 @@ static int aoe_rx_response ( struct aoe_session *aoe, struct aoehdr *aoehdr,
        unsigned int data_len;
        
        /* Sanity check */
-       if ( len < ( sizeof ( *aoehdr ) + sizeof ( *aoecmd ) ) )
+       if ( len < ( sizeof ( *aoehdr ) + sizeof ( *aoecmd ) ) ) {
+               /* Ignore packet; allow timer to trigger retransmit */
                return -EINVAL;
+       }
        rx_data_len = ( len - sizeof ( *aoehdr ) - sizeof ( *aoecmd ) );
 
+       /* Stop retry timer.  After this point, every code path must
+        * either terminate the AoE operation via aoe_done(), or
+        * transmit a new packet.
+        */
+       stop_timer ( &aoe->timer );
+
        /* Check for fatal errors */
        if ( aoehdr->ver_flags & AOE_FL_ERROR ) {
                aoe_done ( aoe, -EIO );
@@ -268,6 +294,7 @@ NET_PROTOCOL ( aoe_protocol );
  */
 void aoe_open ( struct aoe_session *aoe ) {
        memset ( aoe->target, 0xff, sizeof ( aoe->target ) );
+       aoe->timer.expired = aoe_timer_expired;
        list_add ( &aoe->list, &aoe_sessions );
 }
 
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 );
                }
        }