Merge "Cache earliest event results." into tm-dev

3 files changed, 249 insertions, 4 deletions

diff --git a/services/tests/mockingservicestests/src/com/android/server/usage/UserUsageStatsServiceTest.java b/services/tests/mockingservicestests/src/com/android/server/usage/UserUsageStatsServiceTest.java
index d74ff8f0b209..760da4d418ac 100644
--- a/services/tests/mockingservicestests/src/com/android/server/usage/UserUsageStatsServiceTest.java
+++ b/services/tests/mockingservicestests/src/com/android/server/usage/UserUsageStatsServiceTest.java
@@ -179,4 +179,177 @@ public class UserUsageStatsServiceTest {
         assertTrue(hasTestEvent);
         assertEquals(2, count);
     }
+
+    /** Tests that the API works as expected even with the caching system. */
+    @Test
+    public void testQueryEarliestEventsForPackage_Caching() throws Exception {
+        final long forcedDiff = 5000;
+        Event event1 = new Event(NOTIFICATION_SEEN, SystemClock.elapsedRealtime());
+        event1.mPackage = TEST_PACKAGE_NAME;
+        mService.reportEvent(event1);
+        final long event1ReportTime = System.currentTimeMillis();
+        Thread.sleep(forcedDiff);
+        Event event2 = new Event(ACTIVITY_RESUMED, SystemClock.elapsedRealtime());
+        event2.mPackage = TEST_PACKAGE_NAME;
+        mService.reportEvent(event2);
+        final long event2ReportTime = System.currentTimeMillis();
+
+        // Force persist the events instead of waiting for them to be processed on the handler.
+        mService.persistActiveStats();
+
+        long now = System.currentTimeMillis();
+        long startTime = now - forcedDiff * 2;
+        UsageEvents events = mService.queryEarliestEventsForPackage(
+                startTime, now, TEST_PACKAGE_NAME, ACTIVITY_RESUMED);
+
+        assertNotNull(events);
+        boolean hasTestEvent = false;
+        int count = 0;
+        while (events.hasNextEvent()) {
+            count++;
+            Event outEvent = new Event();
+            events.getNextEvent(outEvent);
+            if (outEvent.mEventType == ACTIVITY_RESUMED) {
+                hasTestEvent = true;
+            }
+        }
+        assertTrue(hasTestEvent);
+        assertEquals(2, count);
+
+        // Query again
+        events = mService.queryEarliestEventsForPackage(
+                startTime, now, TEST_PACKAGE_NAME, ACTIVITY_RESUMED);
+
+        assertNotNull(events);
+        hasTestEvent = false;
+        count = 0;
+        while (events.hasNextEvent()) {
+            count++;
+            Event outEvent = new Event();
+            events.getNextEvent(outEvent);
+            if (outEvent.mEventType == ACTIVITY_RESUMED) {
+                hasTestEvent = true;
+            }
+        }
+        assertTrue(hasTestEvent);
+        assertEquals(2, count);
+
+        // Query around just the first event
+        now = event1ReportTime;
+        startTime = now - forcedDiff * 2;
+        events = mService.queryEarliestEventsForPackage(
+                startTime, now, TEST_PACKAGE_NAME, ACTIVITY_RESUMED);
+
+        assertNotNull(events);
+        hasTestEvent = false;
+        count = 0;
+        while (events.hasNextEvent()) {
+            count++;
+            Event outEvent = new Event();
+            events.getNextEvent(outEvent);
+            if (outEvent.mEventType == ACTIVITY_RESUMED) {
+                hasTestEvent = true;
+            }
+        }
+        assertFalse(hasTestEvent);
+        assertEquals(1, count);
+
+        // Shift query around the first event, still exclude the second
+        now = event1ReportTime + forcedDiff / 2;
+        startTime = event1ReportTime - forcedDiff / 2;
+        events = mService.queryEarliestEventsForPackage(
+                startTime, now, TEST_PACKAGE_NAME, ACTIVITY_RESUMED);
+
+        assertNotNull(events);
+        hasTestEvent = false;
+        count = 0;
+        while (events.hasNextEvent()) {
+            count++;
+            Event outEvent = new Event();
+            events.getNextEvent(outEvent);
+            if (outEvent.mEventType == ACTIVITY_RESUMED) {
+                hasTestEvent = true;
+            }
+        }
+        assertFalse(hasTestEvent);
+        assertEquals(1, count);
+
+        // Shift query around the second event only
+        now = event2ReportTime + 1;
+        startTime = event1ReportTime + forcedDiff / 4;
+        events = mService.queryEarliestEventsForPackage(
+                startTime, now, TEST_PACKAGE_NAME, ACTIVITY_RESUMED);
+
+        assertNotNull(events);
+        hasTestEvent = false;
+        count = 0;
+        while (events.hasNextEvent()) {
+            count++;
+            Event outEvent = new Event();
+            events.getNextEvent(outEvent);
+            if (outEvent.mEventType == ACTIVITY_RESUMED) {
+                hasTestEvent = true;
+            }
+        }
+        assertTrue(hasTestEvent);
+        assertEquals(1, count);
+
+        // Shift query around both events
+        now = event2ReportTime + 1;
+        startTime = now - forcedDiff * 2;
+        events = mService.queryEarliestEventsForPackage(
+                startTime, now, TEST_PACKAGE_NAME, ACTIVITY_RESUMED);
+
+        assertNotNull(events);
+        hasTestEvent = false;
+        count = 0;
+        while (events.hasNextEvent()) {
+            count++;
+            Event outEvent = new Event();
+            events.getNextEvent(outEvent);
+            if (outEvent.mEventType == ACTIVITY_RESUMED) {
+                hasTestEvent = true;
+            }
+        }
+        assertTrue(hasTestEvent);
+        assertEquals(2, count);
+
+        // Query around just the first event and then shift end time to include second event
+        now = event1ReportTime;
+        startTime = now - forcedDiff * 2;
+        events = mService.queryEarliestEventsForPackage(
+                startTime, now, TEST_PACKAGE_NAME, ACTIVITY_RESUMED);
+
+        assertNotNull(events);
+        hasTestEvent = false;
+        count = 0;
+        while (events.hasNextEvent()) {
+            count++;
+            Event outEvent = new Event();
+            events.getNextEvent(outEvent);
+            if (outEvent.mEventType == ACTIVITY_RESUMED) {
+                hasTestEvent = true;
+            }
+        }
+        assertFalse(hasTestEvent);
+        assertEquals(1, count);
+
+        now = event2ReportTime + 1;
+        events = mService.queryEarliestEventsForPackage(
+                startTime, now, TEST_PACKAGE_NAME, ACTIVITY_RESUMED);
+
+        assertNotNull(events);
+        hasTestEvent = false;
+        count = 0;
+        while (events.hasNextEvent()) {
+            count++;
+            Event outEvent = new Event();
+            events.getNextEvent(outEvent);
+            if (outEvent.mEventType == ACTIVITY_RESUMED) {
+                hasTestEvent = true;
+            }
+        }
+        assertTrue(hasTestEvent);
+        assertEquals(2, count);
+    }
 }
diff --git a/services/usage/java/com/android/server/usage/UsageStatsService.java b/services/usage/java/com/android/server/usage/UsageStatsService.java
index 01a965230abd..6f89bb25e2ca 100644
--- a/services/usage/java/com/android/server/usage/UsageStatsService.java
+++ b/services/usage/java/com/android/server/usage/UsageStatsService.java
@@ -1453,7 +1453,7 @@ public class UsageStatsService extends SystemService implements
             @NonNull String packageName, int eventType) {
         synchronized (mLock) {
             if (!mUserUnlockedStates.contains(userId)) {
-                Slog.w(TAG, "Failed to query earliset package events for locked user " + userId);
+                Slog.w(TAG, "Failed to query earliest package events for locked user " + userId);
                 return null;
             }
 
diff --git a/services/usage/java/com/android/server/usage/UserUsageStatsService.java b/services/usage/java/com/android/server/usage/UserUsageStatsService.java
index 79f5808739db..c609add0b5d7 100644
--- a/services/usage/java/com/android/server/usage/UserUsageStatsService.java
+++ b/services/usage/java/com/android/server/usage/UserUsageStatsService.java
@@ -48,6 +48,7 @@ import android.util.ArrayMap;
 import android.util.ArraySet;
 import android.util.AtomicFile;
 import android.util.Slog;
+import android.util.SparseArrayMap;
 import android.util.SparseIntArray;
 
 import com.android.internal.util.ArrayUtils;
@@ -104,6 +105,23 @@ class UserUsageStatsService {
         void onNewUpdate(int mUserId);
     }
 
+    private static final class CachedEarlyEvents {
+        public long searchBeginTime;
+
+        public long eventTime;
+
+        @Nullable
+        public List<UsageEvents.Event> events;
+    }
+
+    /**
+     * Mapping of {@link UsageEvents.Event} event value to packageName-cached early usage event.
+     * This is used to reduce how much we need to interact with the underlying database to get the
+     * earliest event for a specific package.
+     */
+    private final SparseArrayMap<String, CachedEarlyEvents> mCachedEarlyEvents =
+            new SparseArrayMap<>();
+
     UserUsageStatsService(Context context, int userId, File usageStatsDir,
             StatsUpdatedListener listener) {
         mContext = context;
@@ -177,9 +195,14 @@ class UserUsageStatsService {
     void userStopped() {
         // Flush events to disk immediately to guarantee persistence.
         persistActiveStats();
+        mCachedEarlyEvents.clear();
     }
 
     int onPackageRemoved(String packageName, long timeRemoved) {
+        for (int i = mCachedEarlyEvents.numMaps() - 1; i >= 0; --i) {
+            final int eventType = mCachedEarlyEvents.keyAt(i);
+            mCachedEarlyEvents.delete(eventType, packageName);
+        }
         return mDatabase.onPackageRemoved(packageName, timeRemoved);
     }
 
@@ -240,6 +263,7 @@ class UserUsageStatsService {
     }
 
     private void onTimeChanged(long oldTime, long newTime) {
+        mCachedEarlyEvents.clear();
         persistActiveStats();
         mDatabase.onTimeChanged(newTime - oldTime);
         loadActiveStats(newTime);
@@ -675,14 +699,56 @@ class UserUsageStatsService {
      * for the package as well as the earliest event of {@code eventType} seen for the package.
      */
     @Nullable
-    UsageEvents queryEarliestEventsForPackage(final long beginTime, final long endTime,
+    UsageEvents queryEarliestEventsForPackage(long beginTime, final long endTime,
             @NonNull final String packageName, final int eventType) {
-        if (!validRange(checkAndGetTimeLocked(), beginTime, endTime)) {
+        final long currentTime = checkAndGetTimeLocked();
+        if (!validRange(currentTime, beginTime, endTime)) {
             return null;
         }
+
+        CachedEarlyEvents cachedEvents = mCachedEarlyEvents.get(eventType, packageName);
+        if (cachedEvents != null) {
+            // We can use this cached event if the previous search time was the exact same
+            // or earlier AND the event we previously found was at this current time or
+            // afterwards. Since no new events will be added before the cached event,
+            // redoing the search will yield the same event.
+            if (cachedEvents.searchBeginTime <= beginTime && beginTime <= cachedEvents.eventTime) {
+                final int numEvents = cachedEvents.events == null ? 0 : cachedEvents.events.size();
+                if ((numEvents == 0
+                        || cachedEvents.events.get(numEvents - 1).getEventType() != eventType)
+                        && cachedEvents.eventTime < endTime) {
+                    // We didn't find a match in the earlier range but this new request is allowing
+                    // us to look at events after the previous request's end time, so we may find
+                    // something new.
+                    beginTime = Math.min(currentTime, cachedEvents.eventTime);
+                    // Leave the cachedEvents's searchBeginTime as the earlier begin time to
+                    // cache/show that we searched the entire range (the union of the two queries):
+                    // [previous query's begin time, current query's end time].
+                } else if (cachedEvents.eventTime <= endTime) {
+                    if (cachedEvents.events == null) {
+                        return null;
+                    }
+                    return new UsageEvents(cachedEvents.events, new String[]{packageName}, false);
+                } else {
+                    // Any event we previously found is after the end of this query's range, but
+                    // this query starts at the same time (or after) the previous query's begin time
+                    // so there is no event to return.
+                    return null;
+                }
+            } else {
+                // The previous query isn't helpful in any way for this query. Reset the event data.
+                cachedEvents.searchBeginTime = beginTime;
+            }
+        } else {
+            cachedEvents = new CachedEarlyEvents();
+            cachedEvents.searchBeginTime = beginTime;
+            mCachedEarlyEvents.add(eventType, packageName, cachedEvents);
+        }
+
+        final long finalBeginTime = beginTime;
         final List<Event> results = queryStats(INTERVAL_DAILY,
                 beginTime, endTime, (stats, mutable, accumulatedResult) -> {
-                    final int startIndex = stats.events.firstIndexOnOrAfter(beginTime);
+                    final int startIndex = stats.events.firstIndexOnOrAfter(finalBeginTime);
                     final int size = stats.events.size();
                     for (int i = startIndex; i < size; i++) {
                         final Event event = stats.events.get(i);
@@ -706,9 +772,15 @@ class UserUsageStatsService {
                 });
 
         if (results == null || results.isEmpty()) {
+            // There won't be any new events added earlier than endTime, so we can use endTime to
+            // avoid querying for events earlier than it.
+            cachedEvents.eventTime = Math.min(currentTime, endTime);
+            cachedEvents.events = null;
             return null;
         }
 
+        cachedEvents.eventTime = results.get(results.size() - 1).getTimeStamp();
+        cachedEvents.events = results;
         return new UsageEvents(results, new String[]{packageName}, false);
     }