Updated retry timer mechanism to incorporate smoothed RTT estimation.

AoE now uses the retry timer mechanism.

1 files changed, 63 insertions, 47 deletions

diff --git a/src/net/retry.c b/src/net/retry.c
index fd704266..531a1b95 100644
--- a/src/net/retry.c
+++ b/src/net/retry.c
@@ -27,61 +27,42 @@
  *
  * 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 );
 		}
 	}