Add OperationScheduler (and test) to the common static library;

includes new string parsing function (and test).

4 files changed, 430 insertions, 14 deletions

diff --git a/common/Android.mk b/common/Android.mk
index 349bb86..76091eb 100644
--- a/common/Android.mk
+++ b/common/Android.mk
@@ -24,3 +24,6 @@ include $(BUILD_STATIC_JAVA_LIBRARY)
 
 # Include this library in the build server's output directory
 $(call dist-for-goals, droid, $(LOCAL_BUILT_MODULE):android-common.jar)
+
+# Build the test package
+include $(call all-makefiles-under,$(LOCAL_PATH))
diff --git a/common/java/com/android/common/OperationScheduler.java b/common/java/com/android/common/OperationScheduler.java
new file mode 100644
index 0000000..71b22ce
--- /dev/null
+++ b/common/java/com/android/common/OperationScheduler.java
@@ -0,0 +1,297 @@
+/*
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.common;
+
+import android.content.SharedPreferences;
+import android.text.format.Time;
+
+import java.util.Map;
+import java.util.TreeSet;
+
+/**
+ * Tracks the success/failure history of a particular network operation in
+ * persistent storage and computes retry strategy accordingly.  Handles
+ * exponential backoff, periodic rescheduling, event-driven triggering,
+ * retry-after moratorium intervals, etc. based on caller-specified parameters.
+ *
+ * <p>This class does not directly perform or invoke any operations,
+ * it only keeps track of the schedule.  Somebody else needs to call
+ * {@link #getNextTimeMillis()} as appropriate and do the actual work.
+ */
+public class OperationScheduler {
+    /** Tunable parameter options for {@link #getNextTimeMillis}. */
+    public static class Options {
+        /** Wait this long after every error before retrying. */
+        public long backoffFixedMillis = 0;
+
+        /** Wait this long times the number of consecutive errors so far before retrying. */
+        public long backoffIncrementalMillis = 5000;
+
+        /** Maximum duration of moratorium to honor.  Mostly an issue for clock rollbacks. */
+        public long maxMoratoriumMillis = 24 * 3600 * 1000;
+
+        /** Minimum duration after success to wait before allowing another trigger. */
+        public long minTriggerMillis = 0;
+
+        /** Automatically trigger this long after the last success. */
+        public long periodicIntervalMillis = 0;
+
+        @Override
+        public String toString() {
+            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);
+        }
+    }
+
+    private static final String PREFIX = "OperationScheduler_";
+    private final SharedPreferences mStorage;
+
+    /**
+     * Initialize the scheduler state.
+     * @param storage to use for recording the state of operations across restarts/reboots
+     */
+    public OperationScheduler(SharedPreferences storage) {
+        mStorage = storage;
+    }
+
+    /**
+     * Parse scheduler options supplied in this string form:
+     *
+     * <pre>
+     * backoff=(fixed)+(incremental) max=(maxmoratorium) min=(mintrigger) [period=](interval)
+     * </pre>
+     *
+     * All values are times in (possibly fractional) <em>seconds</em> (not milliseconds).
+     * Omitted settings are left at whatever existing default value was passed in.
+     *
+     * <p>
+     * The default options: <code>backoff=0+5 max=86400 min=0 period=0</code><br>
+     * Fractions are OK: <code>backoff=+2.5 period=10.0</code><br>
+     * The "period=" can be omitted: <code>3600</code><br>
+     *
+     * @param spec describing some or all scheduler options.
+     * @param options to update with parsed values.
+     * @return the options passed in (for convenience)
+     * @throws IllegalArgumentException if the syntax is invalid
+     */
+    public static Options parseOptions(String spec, Options options)
+            throws IllegalArgumentException {
+        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));
+                }
+            } else if (param.startsWith("max=")) {
+                options.maxMoratoriumMillis = parseSeconds(param.substring(4));
+            } else if (param.startsWith("min=")) {
+                options.minTriggerMillis = parseSeconds(param.substring(4));
+            } else if (param.startsWith("period=")) {
+                options.periodicIntervalMillis = parseSeconds(param.substring(7));
+            } else {
+                options.periodicIntervalMillis = parseSeconds(param);
+            }
+        }
+        return options;
+    }
+
+    private static long parseSeconds(String param) throws NumberFormatException {
+        return (long) (Float.parseFloat(param) * 1000);
+    }
+
+    /**
+     * Compute the time of the next operation.  Does not modify any state.
+     *
+     * @param options to use for this computation.
+     * @return the wall clock time ({@link System#currentTimeMillis()}) when the
+     * next operation should be attempted -- immediately, if the return value is
+     * before the current time.
+     */
+    public long getNextTimeMillis(Options options) {
+        boolean enabledState = mStorage.getBoolean(PREFIX + "enabledState", true);
+        if (!enabledState) return Long.MAX_VALUE;
+
+        boolean permanentError = mStorage.getBoolean(PREFIX + "permanentError", false);
+        if (permanentError) return Long.MAX_VALUE;
+
+        // We do quite a bit of limiting to prevent a clock rollback from totally
+        // hosing the scheduler.  Times which are supposed to be in the past are
+        // clipped to the current time so we don't languish forever.
+
+        int errorCount = mStorage.getInt(PREFIX + "errorCount", 0);
+        long now = System.currentTimeMillis();
+        long lastSuccessTimeMillis = getTimeBefore(PREFIX + "lastSuccessTimeMillis", now);
+        long lastErrorTimeMillis = getTimeBefore(PREFIX + "lastErrorTimeMillis", now);
+        long triggerTimeMillis = mStorage.getLong(PREFIX + "triggerTimeMillis", Long.MAX_VALUE);
+        long moratoriumSetMillis = mStorage.getLong(PREFIX + "moratoriumSetTimeMillis", 0);
+        long moratoriumTimeMillis = getTimeBefore(PREFIX + "moratoriumTimeMillis",
+                moratoriumSetMillis + options.maxMoratoriumMillis);
+
+        long time = triggerTimeMillis;
+        if (options.periodicIntervalMillis > 0) {
+            time = Math.min(time, lastSuccessTimeMillis + options.periodicIntervalMillis);
+        }
+        if (time >= moratoriumTimeMillis - options.maxMoratoriumMillis) {
+            time = Math.max(time, moratoriumTimeMillis);
+        }
+        time = Math.max(time, lastSuccessTimeMillis + options.minTriggerMillis);
+        time = Math.max(time, lastErrorTimeMillis + options.backoffFixedMillis +
+                options.backoffIncrementalMillis * errorCount);
+        return time;
+    }
+
+    /**
+     * Fetch a {@link SharedPreferences} property, but force it to be before
+     * a certain time, updating the value if necessary.  This is to recover
+     * gracefully from clock rollbacks which could otherwise strand our timers.
+     *
+     * @param name of SharedPreferences key
+     * @param max time to allow in result
+     * @return current value attached to key (default 0), limited by max
+     */
+    private long getTimeBefore(String name, long max) {
+        long time = mStorage.getLong(name, 0);
+        if (time > max) mStorage.edit().putLong(name, (time = max)).commit();
+        return time;
+    }
+
+    /**
+     * Request an operation to be performed at a certain time.  The actual
+     * scheduled time may be affected by error backoff logic and defined
+     * minimum intervals.
+     *
+     * @param millis wall clock time ({@link System#currentTimeMillis()}) to
+     * trigger another operation; 0 to trigger immediately
+     */
+    public void setTriggerTimeMillis(long millis) {
+        mStorage.edit().putLong(PREFIX + "triggerTimeMillis", millis).commit();
+    }
+
+    /**
+     * Forbid any operations until after a certain (absolute) time.
+     * Commonly used when a server returns a "Retry-After:" type directive.
+     * Limited by {@link #Options.maxMoratoriumMillis}.
+     *
+     * @param millis wall clock time ({@link System#currentTimeMillis()}) to
+     * wait before attempting any more operations; 0 to remove moratorium
+     */
+    public void setMoratoriumTimeMillis(long millis) {
+        mStorage.edit()
+                .putLong(PREFIX + "moratoriumTimeMillis", millis)
+                .putLong(PREFIX + "moratoriumSetTimeMillis", System.currentTimeMillis())
+                .commit();
+    }
+
+    /**
+     * Enable or disable all operations.  When disabled, all calls to
+     * {@link #getNextTimeMillis()} return {@link Long#MAX_VALUE}.
+     * Commonly used when data network availability goes up and down.
+     *
+     * @param enabled if operations can be performed
+     */
+    public void setEnabledState(boolean enabled) {
+        mStorage.edit().putBoolean(PREFIX + "enabledState", enabled).commit();
+    }
+
+    /**
+     * Report successful completion of an operation.  Resets all error
+     * counters, clears any trigger directives, and records the success.
+     */
+    public void onSuccess() {
+        resetTransientError();
+        resetPermanentError();
+        long now = System.currentTimeMillis();
+        mStorage.edit()
+                .remove(PREFIX + "errorCount")
+                .remove(PREFIX + "lastErrorTimeMillis")
+                .remove(PREFIX + "permanentError")
+                .remove(PREFIX + "triggerTimeMillis")
+                .putLong(PREFIX + "lastSuccessTimeMillis", now).commit();
+    }
+
+    /**
+     * Report a transient error (usually a network failure).  Increments
+     * the error count and records the time of the latest error for backoff
+     * purposes.
+     */
+    public void onTransientError() {
+        long now = System.currentTimeMillis();
+        mStorage.edit().putLong(PREFIX + "lastErrorTimeMillis", now).commit();
+        mStorage.edit().putInt(PREFIX + "errorCount",
+                mStorage.getInt(PREFIX + "errorCount", 0) + 1).commit();
+    }
+
+    /**
+     * Reset all transient error counts, allowing the next operation to proceed
+     * immediately without backoff.  Commonly used on network state changes, when
+     * partial progress occurs (some data received), and in other circumstances
+     * where there is reason to hope things might start working better.
+     */
+    public void resetTransientError() {
+        mStorage.edit()
+                .remove(PREFIX + "lastErrorTimeMillis")
+                .remove(PREFIX + "errorCount").commit();
+    }
+
+    /**
+     * Report a permanent error that will not go away until further notice.
+     * No operation will be scheduled until {@link #resetPermanentError()}
+     * is called.  Commonly used for authentication failures (which are reset
+     * when the accounts database is updated).
+     */
+    public void onPermanentError() {
+        mStorage.edit().putBoolean(PREFIX + "permanentError", true).commit();
+    }
+
+    /**
+     * Reset any permanent error status set by {@link #onPermanentError},
+     * allowing operations to be scheduled as normal.
+     */
+    public void resetPermanentError() {
+        mStorage.edit().remove(PREFIX + "permanentError").commit();
+    }
+
+    /**
+     * Return a string description of the scheduler state for debugging.
+     */
+    public String toString() {
+        StringBuilder out = new StringBuilder("[OperationScheduler:");
+        for (String key : new TreeSet<String>(mStorage.getAll().keySet())) {  // Sort keys
+            if (key.startsWith(PREFIX)) {
+                if (key.endsWith("TimeMillis")) {
+                    Time time = new Time();
+                    time.set(mStorage.getLong(key, 0));
+                    out.append(" ").append(key.substring(PREFIX.length(), key.length() - 10));
+                    out.append("=").append(time.format("%Y-%m-%d/%H:%M:%S"));
+                } else {
+                    out.append(" ").append(key.substring(PREFIX.length()));
+                    out.append("=").append(mStorage.getAll().get(key).toString());
+                }
+            }
+        }
+        return out.append("]").toString();
+    }
+}
diff --git a/common/tests/src/com/android/common/OperationSchedulerTest.java b/common/tests/src/com/android/common/OperationSchedulerTest.java
new file mode 100644
index 0000000..13f710d
--- /dev/null
+++ b/common/tests/src/com/android/common/OperationSchedulerTest.java
@@ -0,0 +1,116 @@
+/*
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.common;
+
+import android.content.SharedPreferences;
+import android.test.AndroidTestCase;
+
+public class OperationSchedulerTest extends AndroidTestCase {
+    public void testScheduler() throws Exception {
+        String name = "OperationSchedulerTest.testScheduler";
+        SharedPreferences storage = getContext().getSharedPreferences(name, 0);
+        storage.edit().clear().commit();
+
+        OperationScheduler scheduler = new OperationScheduler(storage);
+        OperationScheduler.Options options = new OperationScheduler.Options();
+        assertEquals(Long.MAX_VALUE, scheduler.getNextTimeMillis(options));
+
+        long beforeTrigger = System.currentTimeMillis();
+        scheduler.setTriggerTimeMillis(beforeTrigger + 1000000);
+        assertEquals(beforeTrigger + 1000000, scheduler.getNextTimeMillis(options));
+
+        // It will schedule for the later of the trigger and the moratorium...
+        scheduler.setMoratoriumTimeMillis(beforeTrigger + 500000);
+        assertEquals(beforeTrigger + 1000000, scheduler.getNextTimeMillis(options));
+        scheduler.setMoratoriumTimeMillis(beforeTrigger + 1500000);
+        assertEquals(beforeTrigger + 1500000, scheduler.getNextTimeMillis(options));
+
+        // Test enable/disable toggle
+        scheduler.setEnabledState(false);
+        assertEquals(Long.MAX_VALUE, scheduler.getNextTimeMillis(options));
+        scheduler.setEnabledState(true);
+        assertEquals(beforeTrigger + 1500000, scheduler.getNextTimeMillis(options));
+
+        // Backoff interval after an error
+        long beforeError = System.currentTimeMillis();
+        scheduler.onTransientError();
+        long afterError = System.currentTimeMillis();
+        assertEquals(beforeTrigger + 1500000, scheduler.getNextTimeMillis(options));
+        options.backoffFixedMillis = 1000000;
+        options.backoffIncrementalMillis = 500000;
+        assertTrue(beforeError + 1500000 <= scheduler.getNextTimeMillis(options));
+        assertTrue(afterError + 1500000 >= scheduler.getNextTimeMillis(options));
+
+        // Two errors: backoff interval increases
+        beforeError = System.currentTimeMillis();
+        scheduler.onTransientError();
+        afterError = System.currentTimeMillis();
+        assertTrue(beforeError + 2000000 <= scheduler.getNextTimeMillis(options));
+        assertTrue(afterError + 2000000 >= scheduler.getNextTimeMillis(options));
+
+        // Permanent error holds true even if transient errors are reset
+        // However, we remember that the transient error was reset...
+        scheduler.onPermanentError();
+        assertEquals(Long.MAX_VALUE, scheduler.getNextTimeMillis(options));
+        scheduler.resetTransientError();
+        assertEquals(Long.MAX_VALUE, scheduler.getNextTimeMillis(options));
+        scheduler.resetPermanentError();
+        assertEquals(beforeTrigger + 1500000, scheduler.getNextTimeMillis(options));
+
+        // Success resets the trigger
+        long beforeSuccess = System.currentTimeMillis();
+        scheduler.onSuccess();
+        long afterSuccess = System.currentTimeMillis();
+        assertEquals(Long.MAX_VALUE, scheduler.getNextTimeMillis(options));
+
+        // The moratorium is not reset by success!
+        scheduler.setTriggerTimeMillis(beforeSuccess + 500000);
+        assertEquals(beforeTrigger + 1500000, scheduler.getNextTimeMillis(options));
+        scheduler.setMoratoriumTimeMillis(0);
+        assertEquals(beforeSuccess + 500000, scheduler.getNextTimeMillis(options));
+
+        // Periodic interval after success
+        options.periodicIntervalMillis = 250000;
+        assertTrue(beforeSuccess + 250000 <= scheduler.getNextTimeMillis(options));
+        assertTrue(afterSuccess + 250000 >= scheduler.getNextTimeMillis(options));
+
+        // Trigger minimum is also since the last success
+        options.minTriggerMillis = 1000000;
+        assertTrue(beforeSuccess + 1000000 <= scheduler.getNextTimeMillis(options));
+        assertTrue(afterSuccess + 1000000 >= scheduler.getNextTimeMillis(options));
+    }
+
+    public void testParseOptions() throws Exception {
+         OperationScheduler.Options options = new OperationScheduler.Options();
+         assertEquals(
+                 "OperationScheduler.Options[backoff=0.0+5.0 max=86400.0 min=0.0 period=3600.0]",
+                 OperationScheduler.parseOptions("3600", options).toString());
+
+         assertEquals(
+                 "OperationScheduler.Options[backoff=0.0+2.5 max=86400.0 min=0.0 period=3700.0]",
+                 OperationScheduler.parseOptions("backoff=+2.5 3700", options).toString());
+
+         assertEquals(
+                 "OperationScheduler.Options[backoff=10.0+2.5 max=12345.6 min=7.0 period=3800.0]",
+                 OperationScheduler.parseOptions("max=12345.6 min=7 backoff=10 period=3800",
+                         options).toString());
+
+         assertEquals(
+                "OperationScheduler.Options[backoff=10.0+2.5 max=12345.6 min=7.0 period=3800.0]",
+                 OperationScheduler.parseOptions("", options).toString());
+    }
+}
diff --git a/common/tests/src/com/android/common/PatternsTest.java b/common/tests/src/com/android/common/PatternsTest.java
index a89ad62..7fabe5e 100644
--- a/common/tests/src/com/android/common/PatternsTest.java
+++ b/common/tests/src/com/android/common/PatternsTest.java
@@ -28,10 +28,10 @@ public class PatternsTest extends TestCase {
     public void testTldPattern() throws Exception {
         boolean t;
 
-        t = Patterns.TOP_LEVEL_DOMAIN_PATTERN.matcher("com").matches();
+        t = Patterns.TOP_LEVEL_DOMAIN.matcher("com").matches();
         assertTrue("Missed valid TLD", t);
 
-        t = Patterns.TOP_LEVEL_DOMAIN_PATTERN.matcher("xer").matches();
+        t = Patterns.TOP_LEVEL_DOMAIN.matcher("xer").matches();
         assertFalse("Matched invalid TLD!", t);
     }
 
@@ -39,19 +39,19 @@ public class PatternsTest extends TestCase {
     public void testUrlPattern() throws Exception {
         boolean t;
 
-        t = Patterns.WEB_URL_PATTERN.matcher("http://www.google.com").matches();
+        t = Patterns.WEB_URL.matcher("http://www.google.com").matches();
         assertTrue("Valid URL", t);
 
-        t = Patterns.WEB_URL_PATTERN.matcher("ftp://www.example.com").matches();
+        t = Patterns.WEB_URL.matcher("ftp://www.example.com").matches();
         assertFalse("Matched invalid protocol", t);
 
-        t = Patterns.WEB_URL_PATTERN.matcher("http://www.example.com:8080").matches();
+        t = Patterns.WEB_URL.matcher("http://www.example.com:8080").matches();
         assertTrue("Didn't match valid URL with port", t);
 
-        t = Patterns.WEB_URL_PATTERN.matcher("http://www.example.com:8080/?foo=bar").matches();
+        t = Patterns.WEB_URL.matcher("http://www.example.com:8080/?foo=bar").matches();
         assertTrue("Didn't match valid URL with port and query args", t);
 
-        t = Patterns.WEB_URL_PATTERN.matcher("http://www.example.com:8080/~user/?foo=bar").matches();
+        t = Patterns.WEB_URL.matcher("http://www.example.com:8080/~user/?foo=bar").matches();
         assertTrue("Didn't match valid URL with ~", t);
     }
 
@@ -59,10 +59,10 @@ public class PatternsTest extends TestCase {
     public void testIpPattern() throws Exception {
         boolean t;
 
-        t = Patterns.IP_ADDRESS_PATTERN.matcher("172.29.86.3").matches();
+        t = Patterns.IP_ADDRESS.matcher("172.29.86.3").matches();
         assertTrue("Valid IP", t);
 
-        t = Patterns.IP_ADDRESS_PATTERN.matcher("1234.4321.9.9").matches();
+        t = Patterns.IP_ADDRESS.matcher("1234.4321.9.9").matches();
         assertFalse("Invalid IP", t);
     }
 
@@ -70,10 +70,10 @@ public class PatternsTest extends TestCase {
     public void testDomainPattern() throws Exception {
         boolean t;
 
-        t = Patterns.DOMAIN_NAME_PATTERN.matcher("mail.example.com").matches();
+        t = Patterns.DOMAIN_NAME.matcher("mail.example.com").matches();
         assertTrue("Valid domain", t);
 
-        t = Patterns.DOMAIN_NAME_PATTERN.matcher("__+&42.xer").matches();
+        t = Patterns.DOMAIN_NAME.matcher("__+&42.xer").matches();
         assertFalse("Invalid domain", t);
     }
 
@@ -81,10 +81,10 @@ public class PatternsTest extends TestCase {
     public void testPhonePattern() throws Exception {
         boolean t;
 
-        t = Patterns.PHONE_PATTERN.matcher("(919) 555-1212").matches();
+        t = Patterns.PHONE.matcher("(919) 555-1212").matches();
         assertTrue("Valid phone", t);
 
-        t = Patterns.PHONE_PATTERN.matcher("2334 9323/54321").matches();
+        t = Patterns.PHONE.matcher("2334 9323/54321").matches();
         assertFalse("Invalid phone", t);
 
         String[] tests = {
@@ -115,7 +115,7 @@ public class PatternsTest extends TestCase {
         };
 
         for (String test : tests) {
-            Matcher m = Patterns.PHONE_PATTERN.matcher(test);
+            Matcher m = Patterns.PHONE.matcher(test);
 
             assertTrue("Valid phone " + test, m.find());
         }