Move TertiaryKeyRotationScheduler and TertiaryKeyRotationWindowedCount

Migrate these classes into the framework to support encryption in the
framework for backups. There's a modification to the RotationTracker
class to re-introduce a test supporting constructor.

The modification to the blueprint is needed to provide Truthy which
is used in the tests of the migrated classes.

Bug: 111386661
Test: make RunBackupEncryptionRoboTests
Change-Id: Ibe96a9a52f638d5e87e1be46af5803672288f482

3 files changed, 257 insertions, 7 deletions

diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/TertiaryKeyRotationScheduler.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/TertiaryKeyRotationScheduler.java
new file mode 100644
index 000000000000..f16a68d64213
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/TertiaryKeyRotationScheduler.java
@@ -0,0 +1,104 @@
+/*
+ * Copyright (C) 2019 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.server.backup.encryption.keys;
+
+import android.content.Context;
+
+import com.android.internal.annotations.VisibleForTesting;
+
+/**
+ * Schedules tertiary key rotations in a staggered fashion.
+ *
+ * <p>Apps are due a key rotation after a certain number of backups. Rotations are then staggerered
+ * over a period of time, through restricting the number of rotations allowed in a 24-hour window.
+ * This will causes the apps to enter a staggered cycle of regular rotations.
+ *
+ * <p>Note: the methods in this class are not optimized to be super fast. They make blocking IO to
+ * ensure that scheduler information is committed to disk, so that it is available after the user
+ * turns their device off and on. This ought to be fine as
+ *
+ * <ul>
+ *   <li>It will be invoked before a backup, so should never be invoked on the UI thread
+ *   <li>It will be invoked before a backup, so the vast amount of time is spent on the backup, not
+ *       writing tiny amounts of data to disk.
+ * </ul>
+ */
+public class TertiaryKeyRotationScheduler {
+    /** Default number of key rotations allowed within 24 hours. */
+    private static final int KEY_ROTATION_LIMIT = 2;
+
+    /** A new instance, using {@code context} to determine where to store state. */
+    public static TertiaryKeyRotationScheduler getInstance(Context context) {
+        TertiaryKeyRotationWindowedCount windowedCount =
+                TertiaryKeyRotationWindowedCount.getInstance(context);
+        TertiaryKeyRotationTracker tracker = TertiaryKeyRotationTracker.getInstance(context);
+        return new TertiaryKeyRotationScheduler(tracker, windowedCount, KEY_ROTATION_LIMIT);
+    }
+
+    private final TertiaryKeyRotationTracker mTracker;
+    private final TertiaryKeyRotationWindowedCount mWindowedCount;
+    private final int mMaximumRotationsPerWindow;
+
+    /**
+     * A new instance.
+     *
+     * @param tracker Tracks how many times each application has backed up.
+     * @param windowedCount Tracks how many rotations have happened in the last 24 hours.
+     * @param maximumRotationsPerWindow The maximum number of key rotations allowed per 24 hours.
+     */
+    @VisibleForTesting
+    TertiaryKeyRotationScheduler(
+            TertiaryKeyRotationTracker tracker,
+            TertiaryKeyRotationWindowedCount windowedCount,
+            int maximumRotationsPerWindow) {
+        mTracker = tracker;
+        mWindowedCount = windowedCount;
+        mMaximumRotationsPerWindow = maximumRotationsPerWindow;
+    }
+
+    /**
+     * Returns {@code true} if the app with {@code packageName} is due having its key rotated.
+     *
+     * <p>This ought to be queried before backing up an app, to determine whether to do an
+     * incremental backup or a full backup. (A full backup forces key rotation.)
+     */
+    public boolean isKeyRotationDue(String packageName) {
+        if (mWindowedCount.getCount() >= mMaximumRotationsPerWindow) {
+            return false;
+        }
+        return mTracker.isKeyRotationDue(packageName);
+    }
+
+    /**
+     * Records that a backup happened for the app with the given {@code packageName}.
+     *
+     * <p>Each backup brings the app closer to the point at which a key rotation is due.
+     */
+    public void recordBackup(String packageName) {
+        mTracker.recordBackup(packageName);
+    }
+
+    /**
+     * Records a key rotation happened for the app with the given {@code packageName}.
+     *
+     * <p>This resets the countdown until the next key rotation is due.
+     */
+    public void recordKeyRotation(String packageName) {
+        mTracker.resetCountdown(packageName);
+        mWindowedCount.record();
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/TertiaryKeyRotationTracker.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/TertiaryKeyRotationTracker.java
index ec90f6c8c95e..1a281e79cc48 100644
--- a/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/TertiaryKeyRotationTracker.java
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/TertiaryKeyRotationTracker.java
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2018 The Android Open Source Project
+ * Copyright (C) 2019 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.
@@ -16,6 +16,8 @@
 
 package com.android.server.backup.encryption.keys;
 
+import static com.android.internal.util.Preconditions.checkArgument;
+
 import android.content.Context;
 import android.content.SharedPreferences;
 import android.util.Slog;
@@ -46,15 +48,27 @@ public class TertiaryKeyRotationTracker {
      */
     public static TertiaryKeyRotationTracker getInstance(Context context) {
         return new TertiaryKeyRotationTracker(
-                context.getSharedPreferences(SHARED_PREFERENCES_NAME, Context.MODE_PRIVATE));
+                context.getSharedPreferences(SHARED_PREFERENCES_NAME, Context.MODE_PRIVATE),
+                MAX_BACKUPS_UNTIL_TERTIARY_KEY_ROTATION);
     }
 
     private final SharedPreferences mSharedPreferences;
+    private final int mMaxBackupsTillRotation;
 
-    /** New instance, storing data in {@code mSharedPreferences}. */
+    /**
+     * New instance, storing data in {@code sharedPreferences} and initializing backup countdown to
+     * {@code maxBackupsTillRotation}.
+     */
     @VisibleForTesting
-    TertiaryKeyRotationTracker(SharedPreferences sharedPreferences) {
+    TertiaryKeyRotationTracker(SharedPreferences sharedPreferences, int maxBackupsTillRotation) {
+        checkArgument(
+                maxBackupsTillRotation >= 0,
+                String.format(
+                        Locale.US,
+                        "maxBackupsTillRotation should be non-negative but was %d",
+                        maxBackupsTillRotation));
         mSharedPreferences = sharedPreferences;
+        mMaxBackupsTillRotation = maxBackupsTillRotation;
     }
 
     /**
@@ -63,7 +77,7 @@ public class TertiaryKeyRotationTracker {
      * @param packageName The package name of the app.
      */
     public boolean isKeyRotationDue(String packageName) {
-        return getBackupsSinceRotation(packageName) >= MAX_BACKUPS_UNTIL_TERTIARY_KEY_ROTATION;
+        return getBackupsSinceRotation(packageName) >= mMaxBackupsTillRotation;
     }
 
     /**
@@ -84,7 +98,7 @@ public class TertiaryKeyRotationTracker {
                             packageName,
                             Math.max(
                                     0,
-                                    MAX_BACKUPS_UNTIL_TERTIARY_KEY_ROTATION
+                                    mMaxBackupsTillRotation
                                             - backupsSinceRotation)));
         }
     }
@@ -102,7 +116,7 @@ public class TertiaryKeyRotationTracker {
     public void markAllForRotation() {
         SharedPreferences.Editor editor = mSharedPreferences.edit();
         for (String packageName : mSharedPreferences.getAll().keySet()) {
-            editor.putInt(packageName, MAX_BACKUPS_UNTIL_TERTIARY_KEY_ROTATION);
+            editor.putInt(packageName, mMaxBackupsTillRotation);
         }
         editor.apply();
     }
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/TertiaryKeyRotationWindowedCount.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/TertiaryKeyRotationWindowedCount.java
new file mode 100644
index 000000000000..b90343ad4b35
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/TertiaryKeyRotationWindowedCount.java
@@ -0,0 +1,132 @@
+/*
+ * Copyright (C) 2019 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.server.backup.encryption.keys;
+
+import android.content.Context;
+import android.util.Slog;
+
+import com.android.internal.annotations.VisibleForTesting;
+
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.EOFException;
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.time.Clock;
+import java.util.ArrayList;
+import java.util.concurrent.TimeUnit;
+
+/**
+ * Tracks (and commits to disk) how many key rotations have happened in the last 24 hours. This
+ * allows us to limit (and therefore stagger) the number of key rotations in a given period of time.
+ *
+ * <p>Note to engineers thinking of replacing the below with fancier algorithms and data structures:
+ * we expect the total size of this count at any time to be below however many rotations we allow in
+ * the window, which is going to be in single digits. Any changes that mean we write to disk more
+ * frequently, that the code is no longer resistant to clock changes, or that the code is more
+ * difficult to understand are almost certainly not worthwhile.
+ */
+public class TertiaryKeyRotationWindowedCount {
+    private static final String TAG = "TertiaryKeyRotCount";
+
+    private static final int WINDOW_IN_HOURS = 24;
+    private static final String LOG_FILE_NAME = "tertiary_key_rotation_windowed_count";
+
+    private final Clock mClock;
+    private final File mFile;
+    private ArrayList<Long> mEvents;
+
+    /** Returns a new instance, persisting state to the files dir of {@code context}. */
+    public static TertiaryKeyRotationWindowedCount getInstance(Context context) {
+        File logFile = new File(context.getFilesDir(), LOG_FILE_NAME);
+        return new TertiaryKeyRotationWindowedCount(logFile, Clock.systemDefaultZone());
+    }
+
+    /** A new instance, committing state to {@code file}, and reading time from {@code clock}. */
+    @VisibleForTesting
+    TertiaryKeyRotationWindowedCount(File file, Clock clock) {
+        mFile = file;
+        mClock = clock;
+        mEvents = new ArrayList<>();
+        try {
+            loadFromFile();
+        } catch (IOException e) {
+            Slog.e(TAG, "Error reading " + LOG_FILE_NAME, e);
+        }
+    }
+
+    /** Records a key rotation at the current time. */
+    public void record() {
+        mEvents.add(mClock.millis());
+        compact();
+        try {
+            saveToFile();
+        } catch (IOException e) {
+            Slog.e(TAG, "Error saving " + LOG_FILE_NAME, e);
+        }
+    }
+
+    /** Returns the number of key rotation that have been recorded in the window. */
+    public int getCount() {
+        compact();
+        return mEvents.size();
+    }
+
+    private void compact() {
+        long minimumTimestamp = getMinimumTimestamp();
+        long now = mClock.millis();
+        ArrayList<Long> compacted = new ArrayList<>();
+        for (long event : mEvents) {
+            if (event >= minimumTimestamp && event <= now) {
+                compacted.add(event);
+            }
+        }
+        mEvents = compacted;
+    }
+
+    private long getMinimumTimestamp() {
+        return mClock.millis() - TimeUnit.HOURS.toMillis(WINDOW_IN_HOURS) + 1;
+    }
+
+    private void loadFromFile() throws IOException {
+        if (!mFile.exists()) {
+            return;
+        }
+        try (FileInputStream fis = new FileInputStream(mFile);
+                DataInputStream dis = new DataInputStream(fis)) {
+            while (true) {
+                mEvents.add(dis.readLong());
+            }
+        } catch (EOFException eof) {
+            // expected
+        }
+    }
+
+    private void saveToFile() throws IOException {
+        // File size is maximum number of key rotations in window multiplied by 8 bytes, which is
+        // why
+        // we just overwrite it each time. We expect it will always be less than 100 bytes in size.
+        try (FileOutputStream fos = new FileOutputStream(mFile);
+                DataOutputStream dos = new DataOutputStream(fos)) {
+            for (long event : mEvents) {
+                dos.writeLong(event);
+            }
+        }
+    }
+}