add exponential backoff option to OperationScheduler

Change-Id: I583f2d628726a3579aba66a49310a0ccffa94c0a

2 files changed, 81 insertions, 12 deletions

diff --git a/common/java/com/android/common/OperationScheduler.java b/common/java/com/android/common/OperationScheduler.java
index b8fc7bc..261b15d 100644
--- a/common/java/com/android/common/OperationScheduler.java
+++ b/common/java/com/android/common/OperationScheduler.java
@@ -42,6 +42,9 @@ public class OperationScheduler {
         /** Wait this long times the number of consecutive errors so far before retrying. */
         public long backoffIncrementalMillis = 5000;
 
+        /** Wait this long times 2^(number of consecutive errors so far) before retrying. */
+        public int backoffExponentialMillis = 0;
+
         /** Maximum duration of moratorium to honor.  Mostly an issue for clock rollbacks. */
         public long maxMoratoriumMillis = 24 * 3600 * 1000;
 
@@ -53,11 +56,20 @@ public class OperationScheduler {
 
         @Override
         public String toString() {
-            return String.format(
+            if (backoffExponentialMillis > 0) {
+                return String.format(
+                    "OperationScheduler.Options[backoff=%.1f+%.1f+%.1f max=%.1f min=%.1f period=%.1f]",
+                    backoffFixedMillis / 1000.0, backoffIncrementalMillis / 1000.0,
+                    backoffExponentialMillis / 1000.0,
+                    maxMoratoriumMillis / 1000.0, minTriggerMillis / 1000.0,
+                    periodicIntervalMillis / 1000.0);
+            } else {
+                return String.format(
                     "OperationScheduler.Options[backoff=%.1f+%.1f max=%.1f min=%.1f period=%.1f]",
                     backoffFixedMillis / 1000.0, backoffIncrementalMillis / 1000.0,
                     maxMoratoriumMillis / 1000.0, minTriggerMillis / 1000.0,
                     periodicIntervalMillis / 1000.0);
+            }
         }
     }
 
@@ -76,7 +88,7 @@ public class OperationScheduler {
      * Parse scheduler options supplied in this string form:
      *
      * <pre>
-     * backoff=(fixed)+(incremental) max=(maxmoratorium) min=(mintrigger) [period=](interval)
+     * backoff=(fixed)+(incremental)[+(exponential)] max=(maxmoratorium) min=(mintrigger) [period=](interval)
      * </pre>
      *
      * All values are times in (possibly fractional) <em>seconds</em> (not milliseconds).
@@ -97,14 +109,18 @@ public class OperationScheduler {
         for (String param : spec.split(" +")) {
             if (param.length() == 0) continue;
             if (param.startsWith("backoff=")) {
-                int plus = param.indexOf('+', 8);
-                if (plus < 0) {
-                    options.backoffFixedMillis = parseSeconds(param.substring(8));
-                } else {
-                    if (plus > 8) {
-                        options.backoffFixedMillis = parseSeconds(param.substring(8, plus));
-                    }
-                    options.backoffIncrementalMillis = parseSeconds(param.substring(plus + 1));
+                String[] pieces = param.substring(8).split("\\+");
+                if (pieces.length > 3) {
+                    throw new IllegalArgumentException("bad value for backoff: [" + spec + "]");
+                }
+                if (pieces.length > 0 && pieces[0].length() > 0) {
+                    options.backoffFixedMillis = parseSeconds(pieces[0]);
+                }
+                if (pieces.length > 1 && pieces[1].length() > 0) {
+                    options.backoffIncrementalMillis = parseSeconds(pieces[1]);
+                }
+                if (pieces.length > 2 && pieces[2].length() > 0) {
+                    options.backoffExponentialMillis = (int)parseSeconds(pieces[2]);
                 }
             } else if (param.startsWith("max=")) {
                 options.maxMoratoriumMillis = parseSeconds(param.substring(4));
@@ -160,8 +176,21 @@ public class OperationScheduler {
         time = Math.max(time, moratoriumTimeMillis);
         time = Math.max(time, lastSuccessTimeMillis + options.minTriggerMillis);
         if (errorCount > 0) {
-            time = Math.max(time, lastErrorTimeMillis + options.backoffFixedMillis +
-                    options.backoffIncrementalMillis * errorCount);
+            int shift = errorCount-1;
+            // backoffExponentialMillis is an int, so we can safely
+            // double it 30 times without overflowing a long.
+            if (shift > 30) shift = 30;
+            long backoff = options.backoffFixedMillis +
+                (options.backoffIncrementalMillis * errorCount) +
+                (((long)options.backoffExponentialMillis) << shift);
+
+            // Treat backoff like a moratorium: don't let the backoff
+            // time grow too large.
+            if (moratoriumTimeMillis > 0 && backoff > moratoriumTimeMillis) {
+                backoff = moratoriumTimeMillis;
+            }
+
+            time = Math.max(time, lastErrorTimeMillis + backoff);
         }
         return time;
     }
diff --git a/common/tests/src/com/android/common/OperationSchedulerTest.java b/common/tests/src/com/android/common/OperationSchedulerTest.java
index 955508f..87e2cd8 100644
--- a/common/tests/src/com/android/common/OperationSchedulerTest.java
+++ b/common/tests/src/com/android/common/OperationSchedulerTest.java
@@ -119,6 +119,42 @@ public class OperationSchedulerTest extends AndroidTestCase {
         assertEquals(beforeSuccess + 1000000, scheduler.getNextTimeMillis(options));
     }
 
+    @MediumTest
+    public void testExponentialBackoff() throws Exception {
+        TimeTravelScheduler scheduler = new TimeTravelScheduler();
+        OperationScheduler.Options options = new OperationScheduler.Options();
+        options.backoffFixedMillis = 100;
+        options.backoffIncrementalMillis = 1000;
+        options.backoffExponentialMillis = 10000;
+        scheduler.setTriggerTimeMillis(0);
+        scheduler.setEnabledState(true);
+
+        // Backoff interval after an error
+        long beforeError = (scheduler.timeMillis += 10);
+        scheduler.onTransientError();
+        assertEquals(0, scheduler.getLastSuccessTimeMillis());
+        assertEquals(beforeError, scheduler.getLastAttemptTimeMillis());
+        assertEquals(beforeError + 11100, scheduler.getNextTimeMillis(options));
+
+        // Second error
+        beforeError = (scheduler.timeMillis += 10);
+        scheduler.onTransientError();
+        assertEquals(beforeError, scheduler.getLastAttemptTimeMillis());
+        assertEquals(beforeError + 22100, scheduler.getNextTimeMillis(options));
+
+        // Third error
+        beforeError = (scheduler.timeMillis += 10);
+        scheduler.onTransientError();
+        assertEquals(beforeError, scheduler.getLastAttemptTimeMillis());
+        assertEquals(beforeError + 43100, scheduler.getNextTimeMillis(options));
+
+        // Fourth error
+        beforeError = (scheduler.timeMillis += 10);
+        scheduler.onTransientError();
+        assertEquals(beforeError, scheduler.getLastAttemptTimeMillis());
+        assertEquals(beforeError + 84100, scheduler.getNextTimeMillis(options));
+    }
+
     @SmallTest
     public void testParseOptions() throws Exception {
          OperationScheduler.Options options = new OperationScheduler.Options();
@@ -138,6 +174,10 @@ public class OperationSchedulerTest extends AndroidTestCase {
          assertEquals(
                 "OperationScheduler.Options[backoff=10.0+2.5 max=12345.6 min=7.0 period=3800.0]",
                  OperationScheduler.parseOptions("", options).toString());
+
+         assertEquals(
+                 "OperationScheduler.Options[backoff=5.0+2.5+10.0 max=12345.6 min=7.0 period=3600.0]",
+                 OperationScheduler.parseOptions("backoff=5.0++10.0 3600", options).toString());
     }
 
     @SmallTest