Towards an RFC2988-compliant timer.
[people/andreif/gpxe.git] / src / net / retry.c
index f00c178..07b4af4 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.
- */
-
-/** List of running timers */
-static LIST_HEAD ( timers );
-
-/**
- * Reload timer
+ * A retry timer is a binary exponential backoff timer.  It can be
+ * used to build automatic retransmission into network protocols.
  *
- * @v timer            Retry timer
+ * This implementation of the timer is designed to satisfy RFC 2988
+ * and therefore be usable as a TCP retransmission 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 );
-}
+/** Default timeout value */
+#define MIN_TIMEOUT ( TICKS_PER_SEC / 4 )
 
-/**
- * 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.
+/** Limit after which the timeout will be deemed permanent */
+#define MAX_TIMEOUT ( 10 * TICKS_PER_SEC )
+
+/* 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 +75,63 @@ 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 )
+        *
+        */
+       if ( timer->count ) {
+               timer->count--;
+       } else {
+               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 ) );
+               }
+       }
+}
+
+/**
+ * Handle expired timer
+ *
+ * @v timer            Retry timer
+ */
+static void timer_expired ( struct retry_timer *timer ) {
+       int fail;
+
+       /* Stop timer without performing RTT calculations */
        list_del ( &timer->list );
+       timer->count++;
+
+       /* 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 ); 
 }
 
 /**
@@ -105,13 +143,12 @@ static void retry_step ( struct process *process ) {
        struct retry_timer *timer;
        struct retry_timer *tmp;
        unsigned long now = currticks();
+       unsigned long used;
 
        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 )
+                       timer_expired ( timer );
        }
 
        schedule ( process );