Merge "Add CountQuotaTracker."

3 files changed, 1653 insertions, 20 deletions

diff --git a/services/core/java/com/android/server/utils/quota/CountQuotaTracker.java b/services/core/java/com/android/server/utils/quota/CountQuotaTracker.java
new file mode 100644
index 000000000000..7fe4bf849443
--- /dev/null
+++ b/services/core/java/com/android/server/utils/quota/CountQuotaTracker.java
@@ -0,0 +1,802 @@
+/*
+ * 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.utils.quota;
+
+import static android.text.format.DateUtils.MINUTE_IN_MILLIS;
+
+import static com.android.server.utils.quota.Uptc.string;
+
+import android.annotation.NonNull;
+import android.annotation.Nullable;
+import android.app.AlarmManager;
+import android.content.Context;
+import android.os.Handler;
+import android.os.Looper;
+import android.os.Message;
+import android.os.UserHandle;
+import android.util.ArrayMap;
+import android.util.LongArrayQueue;
+import android.util.Slog;
+import android.util.TimeUtils;
+import android.util.proto.ProtoOutputStream;
+import android.util.quota.CountQuotaTrackerProto;
+
+import com.android.internal.annotations.GuardedBy;
+import com.android.internal.annotations.VisibleForTesting;
+import com.android.internal.util.IndentingPrintWriter;
+
+import java.util.function.Consumer;
+import java.util.function.Function;
+
+/**
+ * Class that tracks whether an app has exceeded its defined count quota.
+ *
+ * Quotas are applied per userId-package-tag combination (UPTC). Tags can be null.
+ *
+ * This tracker tracks the count of instantaneous events.
+ *
+ * Limits are applied according to the category the UPTC is placed in. If a UPTC reaches its limit,
+ * it will be considered out of quota until it is below that limit again. A {@link Category} is a
+ * basic construct to apply different limits to different groups of UPTCs. For example, standby
+ * buckets can be a set of categories, or foreground & background could be two categories. If every
+ * UPTC should have the same limits applied, then only one category is needed
+ * ({@see Category.SINGLE_CATEGORY}).
+ *
+ * Note: all limits are enforced per category unless explicitly stated otherwise.
+ *
+ * Test: atest com.android.server.utils.quota.CountQuotaTrackerTest
+ *
+ * @hide
+ */
+public class CountQuotaTracker extends QuotaTracker {
+    private static final String TAG = CountQuotaTracker.class.getSimpleName();
+    private static final boolean DEBUG = false;
+
+    private static final String ALARM_TAG_CLEANUP = "*" + TAG + ".cleanup*";
+
+    @VisibleForTesting
+    static class ExecutionStats {
+        /**
+         * The time after which this record should be considered invalid (out of date), in the
+         * elapsed realtime timebase.
+         */
+        public long expirationTimeElapsed;
+
+        /** The window size that's used when counting the number of events. */
+        public long windowSizeMs;
+        /** The maximum number of events allowed within the window size. */
+        public int countLimit;
+
+        /** The total number of events that occurred in the window. */
+        public int countInWindow;
+
+        /**
+         * The time after which the app will be under the category quota again. This is only valid
+         * if {@link #countInWindow} >= {@link #countLimit}.
+         */
+        public long inQuotaTimeElapsed;
+
+        @Override
+        public String toString() {
+            return "expirationTime=" + expirationTimeElapsed + ", "
+                    + "windowSizeMs=" + windowSizeMs + ", "
+                    + "countLimit=" + countLimit + ", "
+                    + "countInWindow=" + countInWindow + ", "
+                    + "inQuotaTime=" + inQuotaTimeElapsed;
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+            if (obj instanceof ExecutionStats) {
+                ExecutionStats other = (ExecutionStats) obj;
+                return this.expirationTimeElapsed == other.expirationTimeElapsed
+                        && this.windowSizeMs == other.windowSizeMs
+                        && this.countLimit == other.countLimit
+                        && this.countInWindow == other.countInWindow
+                        && this.inQuotaTimeElapsed == other.inQuotaTimeElapsed;
+            }
+            return false;
+        }
+
+        @Override
+        public int hashCode() {
+            int result = 0;
+            result = 31 * result + Long.hashCode(expirationTimeElapsed);
+            result = 31 * result + Long.hashCode(windowSizeMs);
+            result = 31 * result + countLimit;
+            result = 31 * result + countInWindow;
+            result = 31 * result + Long.hashCode(inQuotaTimeElapsed);
+            return result;
+        }
+    }
+
+    /** List of times of all instantaneous events for a UPTC, in chronological order. */
+    // TODO(146148168): introduce a bucketized mode that's more efficient but less accurate
+    @GuardedBy("mLock")
+    private final UptcMap<LongArrayQueue> mEventTimes = new UptcMap<>();
+
+    /** Cached calculation results for each app. */
+    @GuardedBy("mLock")
+    private final UptcMap<ExecutionStats> mExecutionStatsCache = new UptcMap<>();
+
+    private final Handler mHandler;
+
+    @GuardedBy("mLock")
+    private long mNextCleanupTimeElapsed = 0;
+    @GuardedBy("mLock")
+    private final AlarmManager.OnAlarmListener mEventCleanupAlarmListener = () ->
+            CountQuotaTracker.this.mHandler.obtainMessage(MSG_CLEAN_UP_EVENTS).sendToTarget();
+
+    /** The rolling window size for each Category's count limit. */
+    @GuardedBy("mLock")
+    private final ArrayMap<Category, Long> mCategoryCountWindowSizesMs = new ArrayMap<>();
+
+    /**
+     * The maximum count for each Category. For each max value count in the map, the app will
+     * not be allowed any more events within the latest time interval of its rolling window size.
+     *
+     * @see #mCategoryCountWindowSizesMs
+     */
+    @GuardedBy("mLock")
+    private final ArrayMap<Category, Integer> mMaxCategoryCounts = new ArrayMap<>();
+
+    /** The longest period a registered category applies to. */
+    @GuardedBy("mLock")
+    private long mMaxPeriodMs = 0;
+
+    /** Drop any old events. */
+    private static final int MSG_CLEAN_UP_EVENTS = 1;
+
+    public CountQuotaTracker(@NonNull Context context, @NonNull Categorizer categorizer) {
+        this(context, categorizer, new Injector());
+    }
+
+    @VisibleForTesting
+    CountQuotaTracker(@NonNull Context context, @NonNull Categorizer categorizer,
+            Injector injector) {
+        super(context, categorizer, injector);
+
+        mHandler = new CqtHandler(context.getMainLooper());
+    }
+
+    // Exposed API to users.
+
+    /**
+     * Record that an instantaneous event happened.
+     *
+     * @return true if the UPTC is within quota, false otherwise.
+     */
+    public boolean noteEvent(int userId, @NonNull String packageName, @Nullable String tag) {
+        synchronized (mLock) {
+            if (!isEnabledLocked() || isQuotaFreeLocked(userId, packageName)) {
+                return true;
+            }
+            final long nowElapsed = mInjector.getElapsedRealtime();
+
+            final LongArrayQueue times = mEventTimes
+                    .getOrCreate(userId, packageName, tag, mCreateLongArrayQueue);
+            times.addLast(nowElapsed);
+            final ExecutionStats stats = getExecutionStatsLocked(userId, packageName, tag);
+            stats.countInWindow++;
+            stats.expirationTimeElapsed = Math.min(stats.expirationTimeElapsed,
+                    nowElapsed + stats.windowSizeMs);
+            if (stats.countInWindow == stats.countLimit) {
+                final long windowEdgeElapsed = nowElapsed - stats.windowSizeMs;
+                while (times.size() > 0 && times.peekFirst() < windowEdgeElapsed) {
+                    times.removeFirst();
+                }
+                stats.inQuotaTimeElapsed = times.peekFirst() + stats.windowSizeMs;
+                postQuotaStatusChanged(userId, packageName, tag);
+            } else if (stats.countLimit > 9
+                    && stats.countInWindow == stats.countLimit * 4 / 5) {
+                // TODO: log high watermark to statsd
+                Slog.w(TAG, string(userId, packageName, tag)
+                        + " has reached 80% of it's count limit of " + stats.countLimit);
+            }
+            maybeScheduleCleanupAlarmLocked();
+            return isWithinQuotaLocked(stats);
+        }
+    }
+
+    /**
+     * Set count limit over a rolling time window for the specified category.
+     *
+     * @param category     The category these limits apply to.
+     * @param limit        The maximum event count an app can have in the rolling window. Must be
+     *                     nonnegative.
+     * @param timeWindowMs The rolling time window (in milliseconds) to use when checking quota
+     *                     usage. Must be at least {@value #MIN_WINDOW_SIZE_MS} and no longer than
+     *                     {@value #MAX_WINDOW_SIZE_MS}
+     */
+    public void setCountLimit(@NonNull Category category, int limit, long timeWindowMs) {
+        if (limit < 0 || timeWindowMs < 0) {
+            throw new IllegalArgumentException("Limit and window size must be nonnegative.");
+        }
+        synchronized (mLock) {
+            final Integer oldLimit = mMaxCategoryCounts.put(category, limit);
+            final long newWindowSizeMs = Math.max(MIN_WINDOW_SIZE_MS,
+                    Math.min(timeWindowMs, MAX_WINDOW_SIZE_MS));
+            final Long oldWindowSizeMs = mCategoryCountWindowSizesMs.put(category, newWindowSizeMs);
+            if (oldLimit != null && oldWindowSizeMs != null
+                    && oldLimit == limit && oldWindowSizeMs == newWindowSizeMs) {
+                // No change.
+                return;
+            }
+            mDeleteOldEventTimesFunctor.updateMaxPeriod();
+            mMaxPeriodMs = mDeleteOldEventTimesFunctor.mMaxPeriodMs;
+            invalidateAllExecutionStatsLocked();
+        }
+        scheduleQuotaCheck();
+    }
+
+    /**
+     * Gets the count limit for the specified category.
+     */
+    public int getLimit(@NonNull Category category) {
+        synchronized (mLock) {
+            final Integer limit = mMaxCategoryCounts.get(category);
+            if (limit == null) {
+                throw new IllegalArgumentException("Limit for " + category + " not defined");
+            }
+            return limit;
+        }
+    }
+
+    /**
+     * Gets the count time window for the specified category.
+     */
+    public long getWindowSizeMs(@NonNull Category category) {
+        synchronized (mLock) {
+            final Long limitMs = mCategoryCountWindowSizesMs.get(category);
+            if (limitMs == null) {
+                throw new IllegalArgumentException("Limit for " + category + " not defined");
+            }
+            return limitMs;
+        }
+    }
+
+    // Internal implementation.
+
+    @Override
+    @GuardedBy("mLock")
+    void dropEverythingLocked() {
+        mExecutionStatsCache.clear();
+        mEventTimes.clear();
+    }
+
+    @Override
+    @GuardedBy("mLock")
+    @NonNull
+    Handler getHandler() {
+        return mHandler;
+    }
+
+    @Override
+    @GuardedBy("mLock")
+    long getInQuotaTimeElapsedLocked(final int userId, @NonNull final String packageName,
+            @Nullable final String tag) {
+        return getExecutionStatsLocked(userId, packageName, tag).inQuotaTimeElapsed;
+    }
+
+    @Override
+    @GuardedBy("mLock")
+    void handleRemovedAppLocked(String packageName, int uid) {
+        if (packageName == null) {
+            Slog.wtf(TAG, "Told app removed but given null package name.");
+            return;
+        }
+        final int userId = UserHandle.getUserId(uid);
+
+        mEventTimes.delete(userId, packageName);
+        mExecutionStatsCache.delete(userId, packageName);
+    }
+
+    @Override
+    @GuardedBy("mLock")
+    void handleRemovedUserLocked(int userId) {
+        mEventTimes.delete(userId);
+        mExecutionStatsCache.delete(userId);
+    }
+
+    @Override
+    @GuardedBy("mLock")
+    boolean isWithinQuotaLocked(final int userId, @NonNull final String packageName,
+            @Nullable final String tag) {
+        if (!isEnabledLocked()) return true;
+
+        // Quota constraint is not enforced when quota is free.
+        if (isQuotaFreeLocked(userId, packageName)) {
+            return true;
+        }
+
+        return isWithinQuotaLocked(getExecutionStatsLocked(userId, packageName, tag));
+    }
+
+    @Override
+    @GuardedBy("mLock")
+    void maybeUpdateAllQuotaStatusLocked() {
+        final UptcMap<Boolean> doneMap = new UptcMap<>();
+        mEventTimes.forEach((userId, packageName, tag, events) -> {
+            if (!doneMap.contains(userId, packageName, tag)) {
+                maybeUpdateStatusForUptcLocked(userId, packageName, tag);
+                doneMap.add(userId, packageName, tag, Boolean.TRUE);
+            }
+        });
+
+    }
+
+    @Override
+    void maybeUpdateQuotaStatus(final int userId, @NonNull final String packageName,
+            @Nullable final String tag) {
+        synchronized (mLock) {
+            maybeUpdateStatusForUptcLocked(userId, packageName, tag);
+        }
+    }
+
+    @Override
+    @GuardedBy("mLock")
+    void onQuotaFreeChangedLocked(boolean isFree) {
+        // Nothing to do here.
+    }
+
+    @Override
+    @GuardedBy("mLock")
+    void onQuotaFreeChangedLocked(int userId, @NonNull String packageName, boolean isFree) {
+        maybeUpdateStatusForPkgLocked(userId, packageName);
+    }
+
+    @GuardedBy("mLock")
+    private boolean isWithinQuotaLocked(@NonNull final ExecutionStats stats) {
+        return isUnderCountQuotaLocked(stats);
+    }
+
+    @GuardedBy("mLock")
+    private boolean isUnderCountQuotaLocked(@NonNull ExecutionStats stats) {
+        return stats.countInWindow < stats.countLimit;
+    }
+
+    /** Returns the execution stats of the app in the most recent window. */
+    @GuardedBy("mLock")
+    @VisibleForTesting
+    @NonNull
+    ExecutionStats getExecutionStatsLocked(final int userId, @NonNull final String packageName,
+            @Nullable final String tag) {
+        return getExecutionStatsLocked(userId, packageName, tag, true);
+    }
+
+    @GuardedBy("mLock")
+    @NonNull
+    private ExecutionStats getExecutionStatsLocked(final int userId,
+            @NonNull final String packageName, @Nullable String tag,
+            final boolean refreshStatsIfOld) {
+        final ExecutionStats stats =
+                mExecutionStatsCache.getOrCreate(userId, packageName, tag, mCreateExecutionStats);
+        if (refreshStatsIfOld) {
+            final Category category = mCategorizer.getCategory(userId, packageName, tag);
+            final long countWindowSizeMs = mCategoryCountWindowSizesMs.getOrDefault(category,
+                    Long.MAX_VALUE);
+            final int countLimit = mMaxCategoryCounts.getOrDefault(category, Integer.MAX_VALUE);
+            if (stats.expirationTimeElapsed <= mInjector.getElapsedRealtime()
+                    || stats.windowSizeMs != countWindowSizeMs
+                    || stats.countLimit != countLimit) {
+                // The stats are no longer valid.
+                stats.windowSizeMs = countWindowSizeMs;
+                stats.countLimit = countLimit;
+                updateExecutionStatsLocked(userId, packageName, tag, stats);
+            }
+        }
+
+        return stats;
+    }
+
+    @GuardedBy("mLock")
+    @VisibleForTesting
+    void updateExecutionStatsLocked(final int userId, @NonNull final String packageName,
+            @Nullable final String tag, @NonNull ExecutionStats stats) {
+        stats.countInWindow = 0;
+        stats.inQuotaTimeElapsed = 0;
+
+        // This can be used to determine when an app will have enough quota to transition from
+        // out-of-quota to in-quota.
+        final long nowElapsed = mInjector.getElapsedRealtime();
+        stats.expirationTimeElapsed = nowElapsed + mMaxPeriodMs;
+
+        final LongArrayQueue events = mEventTimes.get(userId, packageName, tag);
+        if (events == null) {
+            return;
+        }
+
+        // The minimum time between the start time and the beginning of the events that were
+        // looked at --> how much time the stats will be valid for.
+        long emptyTimeMs = Long.MAX_VALUE - nowElapsed;
+
+        final long eventStartWindowElapsed = nowElapsed - stats.windowSizeMs;
+        for (int i = events.size() - 1; i >= 0; --i) {
+            final long eventTimeElapsed = events.get(i);
+            if (eventTimeElapsed < eventStartWindowElapsed) {
+                // This event happened before the window. No point in going any further.
+                break;
+            }
+            stats.countInWindow++;
+            emptyTimeMs = Math.min(emptyTimeMs, eventTimeElapsed - eventStartWindowElapsed);
+
+            if (stats.countInWindow >= stats.countLimit) {
+                stats.inQuotaTimeElapsed = Math.max(stats.inQuotaTimeElapsed,
+                        eventTimeElapsed + stats.windowSizeMs);
+            }
+        }
+
+        stats.expirationTimeElapsed = nowElapsed + emptyTimeMs;
+    }
+
+    /** Invalidate ExecutionStats for all apps. */
+    @GuardedBy("mLock")
+    private void invalidateAllExecutionStatsLocked() {
+        final long nowElapsed = mInjector.getElapsedRealtime();
+        mExecutionStatsCache.forEach((appStats) -> {
+            if (appStats != null) {
+                appStats.expirationTimeElapsed = nowElapsed;
+            }
+        });
+    }
+
+    @GuardedBy("mLock")
+    private void invalidateAllExecutionStatsLocked(final int userId,
+            @NonNull final String packageName) {
+        final ArrayMap<String, ExecutionStats> appStats =
+                mExecutionStatsCache.get(userId, packageName);
+        if (appStats != null) {
+            final long nowElapsed = mInjector.getElapsedRealtime();
+            final int numStats = appStats.size();
+            for (int i = 0; i < numStats; ++i) {
+                final ExecutionStats stats = appStats.valueAt(i);
+                if (stats != null) {
+                    stats.expirationTimeElapsed = nowElapsed;
+                }
+            }
+        }
+    }
+
+    @GuardedBy("mLock")
+    private void invalidateExecutionStatsLocked(final int userId, @NonNull final String packageName,
+            @Nullable String tag) {
+        final ExecutionStats stats = mExecutionStatsCache.get(userId, packageName, tag);
+        if (stats != null) {
+            stats.expirationTimeElapsed = mInjector.getElapsedRealtime();
+        }
+    }
+
+    private static final class EarliestEventTimeFunctor implements Consumer<LongArrayQueue> {
+        long earliestTimeElapsed = Long.MAX_VALUE;
+
+        @Override
+        public void accept(LongArrayQueue events) {
+            if (events != null && events.size() > 0) {
+                earliestTimeElapsed = Math.min(earliestTimeElapsed, events.get(0));
+            }
+        }
+
+        void reset() {
+            earliestTimeElapsed = Long.MAX_VALUE;
+        }
+    }
+
+    private final EarliestEventTimeFunctor mEarliestEventTimeFunctor =
+            new EarliestEventTimeFunctor();
+
+    /** Schedule a cleanup alarm if necessary and there isn't already one scheduled. */
+    @GuardedBy("mLock")
+    @VisibleForTesting
+    void maybeScheduleCleanupAlarmLocked() {
+        if (mNextCleanupTimeElapsed > mInjector.getElapsedRealtime()) {
+            // There's already an alarm scheduled. Just stick with that one. There's no way we'll
+            // end up scheduling an earlier alarm.
+            if (DEBUG) {
+                Slog.v(TAG, "Not scheduling cleanup since there's already one at "
+                        + mNextCleanupTimeElapsed + " (in " + (mNextCleanupTimeElapsed
+                        - mInjector.getElapsedRealtime()) + "ms)");
+            }
+            return;
+        }
+
+        mEarliestEventTimeFunctor.reset();
+        mEventTimes.forEach(mEarliestEventTimeFunctor);
+        final long earliestEndElapsed = mEarliestEventTimeFunctor.earliestTimeElapsed;
+        if (earliestEndElapsed == Long.MAX_VALUE) {
+            // Couldn't find a good time to clean up. Maybe this was called after we deleted all
+            // events.
+            if (DEBUG) {
+                Slog.d(TAG, "Didn't find a time to schedule cleanup");
+            }
+            return;
+        }
+
+        // Need to keep events for all apps up to the max period, regardless of their current
+        // category.
+        long nextCleanupElapsed = earliestEndElapsed + mMaxPeriodMs;
+        if (nextCleanupElapsed - mNextCleanupTimeElapsed <= 10 * MINUTE_IN_MILLIS) {
+            // No need to clean up too often. Delay the alarm if the next cleanup would be too soon
+            // after it.
+            nextCleanupElapsed += 10 * MINUTE_IN_MILLIS;
+        }
+        mNextCleanupTimeElapsed = nextCleanupElapsed;
+        scheduleAlarm(AlarmManager.ELAPSED_REALTIME, nextCleanupElapsed, ALARM_TAG_CLEANUP,
+                mEventCleanupAlarmListener);
+        if (DEBUG) {
+            Slog.d(TAG, "Scheduled next cleanup for " + mNextCleanupTimeElapsed);
+        }
+    }
+
+    @GuardedBy("mLock")
+    private boolean maybeUpdateStatusForPkgLocked(final int userId,
+            @NonNull final String packageName) {
+        final UptcMap<Boolean> done = new UptcMap<>();
+
+        if (!mEventTimes.contains(userId, packageName)) {
+            return false;
+        }
+        final ArrayMap<String, LongArrayQueue> events = mEventTimes.get(userId, packageName);
+        if (events == null) {
+            Slog.wtf(TAG,
+                    "Events map was null even though mEventTimes said it contained "
+                            + string(userId, packageName, null));
+            return false;
+        }
+
+        // Lambdas can't interact with non-final outer variables.
+        final boolean[] changed = {false};
+        events.forEach((tag, eventList) -> {
+            if (!done.contains(userId, packageName, tag)) {
+                changed[0] |= maybeUpdateStatusForUptcLocked(userId, packageName, tag);
+                done.add(userId, packageName, tag, Boolean.TRUE);
+            }
+        });
+
+        return changed[0];
+    }
+
+    /**
+     * Posts that the quota status for the UPTC has changed if it has changed. Avoid calling if
+     * there are no {@link QuotaChangeListener}s registered as the work done will be useless.
+     *
+     * @return true if the in/out quota status changed
+     */
+    @GuardedBy("mLock")
+    private boolean maybeUpdateStatusForUptcLocked(final int userId,
+            @NonNull final String packageName, @Nullable final String tag) {
+        final boolean oldInQuota = isWithinQuotaLocked(
+                getExecutionStatsLocked(userId, packageName, tag, false));
+
+        final boolean newInQuota;
+        if (!isEnabledLocked() || isQuotaFreeLocked(userId, packageName)) {
+            newInQuota = true;
+        } else {
+            newInQuota = isWithinQuotaLocked(
+                    getExecutionStatsLocked(userId, packageName, tag, true));
+        }
+
+        if (!newInQuota) {
+            maybeScheduleStartAlarmLocked(userId, packageName, tag);
+        } else {
+            cancelScheduledStartAlarmLocked(userId, packageName, tag);
+        }
+
+        if (oldInQuota != newInQuota) {
+            if (DEBUG) {
+                Slog.d(TAG,
+                        "Quota status changed from " + oldInQuota + " to " + newInQuota + " for "
+                                + string(userId, packageName, tag));
+            }
+            postQuotaStatusChanged(userId, packageName, tag);
+            return true;
+        }
+
+        return false;
+    }
+
+    private final class DeleteEventTimesFunctor implements Consumer<LongArrayQueue> {
+        private long mMaxPeriodMs;
+
+        @Override
+        public void accept(LongArrayQueue times) {
+            if (times != null) {
+                // Remove everything older than mMaxPeriodMs time ago.
+                while (times.size() > 0
+                        && times.peekFirst() <= mInjector.getElapsedRealtime() - mMaxPeriodMs) {
+                    times.removeFirst();
+                }
+            }
+        }
+
+        private void updateMaxPeriod() {
+            long maxPeriodMs = 0;
+            for (int i = mCategoryCountWindowSizesMs.size() - 1; i >= 0; --i) {
+                maxPeriodMs = Long.max(maxPeriodMs, mCategoryCountWindowSizesMs.valueAt(i));
+            }
+            mMaxPeriodMs = maxPeriodMs;
+        }
+    }
+
+    private final DeleteEventTimesFunctor mDeleteOldEventTimesFunctor =
+            new DeleteEventTimesFunctor();
+
+    @GuardedBy("mLock")
+    @VisibleForTesting
+    void deleteObsoleteEventsLocked() {
+        mEventTimes.forEach(mDeleteOldEventTimesFunctor);
+    }
+
+    private class CqtHandler extends Handler {
+        CqtHandler(Looper looper) {
+            super(looper);
+        }
+
+        @Override
+        public void handleMessage(Message msg) {
+            synchronized (mLock) {
+                switch (msg.what) {
+                    case MSG_CLEAN_UP_EVENTS: {
+                        if (DEBUG) {
+                            Slog.d(TAG, "Cleaning up events.");
+                        }
+                        deleteObsoleteEventsLocked();
+                        maybeScheduleCleanupAlarmLocked();
+                        break;
+                    }
+                }
+            }
+        }
+    }
+
+    private Function<Void, LongArrayQueue> mCreateLongArrayQueue = aVoid -> new LongArrayQueue();
+    private Function<Void, ExecutionStats> mCreateExecutionStats = aVoid -> new ExecutionStats();
+
+    //////////////////////// TESTING HELPERS /////////////////////////////
+
+    @VisibleForTesting
+    @Nullable
+    LongArrayQueue getEvents(int userId, String packageName, String tag) {
+        return mEventTimes.get(userId, packageName, tag);
+    }
+
+    //////////////////////////// DATA DUMP //////////////////////////////
+
+    /** Dump state in text format. */
+    public void dump(final IndentingPrintWriter pw) {
+        pw.print(TAG);
+        pw.println(":");
+        pw.increaseIndent();
+
+        synchronized (mLock) {
+            super.dump(pw);
+            pw.println();
+
+            pw.println("Instantaneous events:");
+            pw.increaseIndent();
+            mEventTimes.forEach((userId, pkgName, tag, events) -> {
+                if (events.size() > 0) {
+                    pw.print(string(userId, pkgName, tag));
+                    pw.println(":");
+                    pw.increaseIndent();
+                    pw.print(events.get(0));
+                    for (int i = 1; i < events.size(); ++i) {
+                        pw.print(", ");
+                        pw.print(events.get(i));
+                    }
+                    pw.decreaseIndent();
+                    pw.println();
+                }
+            });
+            pw.decreaseIndent();
+
+            pw.println();
+            pw.println("Cached execution stats:");
+            pw.increaseIndent();
+            mExecutionStatsCache.forEach((userId, pkgName, tag, stats) -> {
+                if (stats != null) {
+                    pw.print(string(userId, pkgName, tag));
+                    pw.println(":");
+                    pw.increaseIndent();
+                    pw.println(stats);
+                    pw.decreaseIndent();
+                }
+            });
+            pw.decreaseIndent();
+
+            pw.println();
+            pw.println("Limits:");
+            pw.increaseIndent();
+            final int numCategories = mCategoryCountWindowSizesMs.size();
+            for (int i = 0; i < numCategories; ++i) {
+                final Category category = mCategoryCountWindowSizesMs.keyAt(i);
+                pw.print(category);
+                pw.print(": ");
+                pw.print(mMaxCategoryCounts.get(category));
+                pw.print(" events in ");
+                pw.println(TimeUtils.formatDuration(mCategoryCountWindowSizesMs.get(category)));
+            }
+            pw.decreaseIndent();
+        }
+        pw.decreaseIndent();
+    }
+
+    /**
+     * Dump state to proto.
+     *
+     * @param proto   The ProtoOutputStream to write to.
+     * @param fieldId The field ID of the {@link CountQuotaTrackerProto}.
+     */
+    public void dump(ProtoOutputStream proto, long fieldId) {
+        final long token = proto.start(fieldId);
+
+        synchronized (mLock) {
+            super.dump(proto, CountQuotaTrackerProto.BASE_QUOTA_DATA);
+
+            for (int i = 0; i < mCategoryCountWindowSizesMs.size(); ++i) {
+                final Category category = mCategoryCountWindowSizesMs.keyAt(i);
+                final long clToken = proto.start(CountQuotaTrackerProto.COUNT_LIMIT);
+                category.dumpDebug(proto, CountQuotaTrackerProto.CountLimit.CATEGORY);
+                proto.write(CountQuotaTrackerProto.CountLimit.LIMIT,
+                        mMaxCategoryCounts.get(category));
+                proto.write(CountQuotaTrackerProto.CountLimit.WINDOW_SIZE_MS,
+                        mCategoryCountWindowSizesMs.get(category));
+                proto.end(clToken);
+            }
+
+            mExecutionStatsCache.forEach((userId, pkgName, tag, stats) -> {
+                final boolean isQuotaFree = isIndividualQuotaFreeLocked(userId, pkgName);
+
+                final long usToken = proto.start(CountQuotaTrackerProto.UPTC_STATS);
+
+                (new Uptc(userId, pkgName, tag))
+                        .dumpDebug(proto, CountQuotaTrackerProto.UptcStats.UPTC);
+
+                proto.write(CountQuotaTrackerProto.UptcStats.IS_QUOTA_FREE, isQuotaFree);
+
+                final LongArrayQueue events = mEventTimes.get(userId, pkgName, tag);
+                if (events != null) {
+                    for (int j = events.size() - 1; j >= 0; --j) {
+                        final long eToken = proto.start(CountQuotaTrackerProto.UptcStats.EVENTS);
+                        proto.write(CountQuotaTrackerProto.Event.TIMESTAMP_ELAPSED, events.get(j));
+                        proto.end(eToken);
+                    }
+                }
+
+                final long statsToken = proto.start(
+                        CountQuotaTrackerProto.UptcStats.EXECUTION_STATS);
+                proto.write(
+                        CountQuotaTrackerProto.ExecutionStats.EXPIRATION_TIME_ELAPSED,
+                        stats.expirationTimeElapsed);
+                proto.write(
+                        CountQuotaTrackerProto.ExecutionStats.WINDOW_SIZE_MS,
+                        stats.windowSizeMs);
+                proto.write(CountQuotaTrackerProto.ExecutionStats.COUNT_LIMIT, stats.countLimit);
+                proto.write(
+                        CountQuotaTrackerProto.ExecutionStats.COUNT_IN_WINDOW,
+                        stats.countInWindow);
+                proto.write(
+                        CountQuotaTrackerProto.ExecutionStats.IN_QUOTA_TIME_ELAPSED,
+                        stats.inQuotaTimeElapsed);
+                proto.end(statsToken);
+
+                proto.end(usToken);
+            });
+
+            proto.end(token);
+        }
+    }
+}
diff --git a/services/core/java/com/android/server/utils/quota/UptcMap.java b/services/core/java/com/android/server/utils/quota/UptcMap.java
index 80f4f0a88ec3..a3d6ee52db6a 100644
--- a/services/core/java/com/android/server/utils/quota/UptcMap.java
+++ b/services/core/java/com/android/server/utils/quota/UptcMap.java
@@ -112,37 +112,20 @@ class UptcMap<T> {
         return data.get(tag);
     }
 
-    /**
-     * Returns the index for which {@link #getUserIdAtIndex(int)} would return the specified userId,
-     * or a negative number if the specified userId is not mapped.
-     */
-    public int indexOfUserId(int userId) {
-        return mData.indexOfKey(userId);
-    }
-
-    /**
-     * Returns the index for which {@link #getPackageNameAtIndex(int, int)} would return the
-     * specified userId, or a negative number if the specified userId and packageName are not mapped
-     * together.
-     */
-    public int indexOfUserIdAndPackage(int userId, @NonNull String packageName) {
-        return mData.indexOfKey(userId, packageName);
-    }
-
     /** Returns the userId at the given index. */
-    public int getUserIdAtIndex(int index) {
+    private int getUserIdAtIndex(int index) {
         return mData.keyAt(index);
     }
 
     /** Returns the package name at the given index. */
     @NonNull
-    public String getPackageNameAtIndex(int userIndex, int packageIndex) {
+    private String getPackageNameAtIndex(int userIndex, int packageIndex) {
         return mData.keyAt(userIndex, packageIndex);
     }
 
     /** Returns the tag at the given index. */
     @NonNull
-    public String getTagAtIndex(int userIndex, int packageIndex, int tagIndex) {
+    private String getTagAtIndex(int userIndex, int packageIndex, int tagIndex) {
         // This structure never inserts a null ArrayMap, so if the indices are valid, valueAt()
         // won't return null.
         return mData.valueAt(userIndex, packageIndex).keyAt(tagIndex);
diff --git a/services/tests/mockingservicestests/src/com/android/server/utils/quota/CountQuotaTrackerTest.java b/services/tests/mockingservicestests/src/com/android/server/utils/quota/CountQuotaTrackerTest.java
new file mode 100644
index 000000000000..80aec73035bc
--- /dev/null
+++ b/services/tests/mockingservicestests/src/com/android/server/utils/quota/CountQuotaTrackerTest.java
@@ -0,0 +1,848 @@
+/*
+ * 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.utils.quota;
+
+import static com.android.dx.mockito.inline.extended.ExtendedMockito.doNothing;
+import static com.android.dx.mockito.inline.extended.ExtendedMockito.inOrder;
+import static com.android.dx.mockito.inline.extended.ExtendedMockito.mockitoSession;
+import static com.android.dx.mockito.inline.extended.ExtendedMockito.spyOn;
+import static com.android.dx.mockito.inline.extended.ExtendedMockito.when;
+import static com.android.server.utils.quota.Category.SINGLE_CATEGORY;
+import static com.android.server.utils.quota.QuotaTracker.MAX_WINDOW_SIZE_MS;
+import static com.android.server.utils.quota.QuotaTracker.MIN_WINDOW_SIZE_MS;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+import static org.mockito.ArgumentMatchers.any;
+import static org.mockito.ArgumentMatchers.anyInt;
+import static org.mockito.ArgumentMatchers.anyLong;
+import static org.mockito.Mockito.atLeastOnce;
+import static org.mockito.Mockito.eq;
+import static org.mockito.Mockito.never;
+import static org.mockito.Mockito.timeout;
+import static org.mockito.Mockito.times;
+import static org.mockito.Mockito.verify;
+
+import android.app.AlarmManager;
+import android.content.BroadcastReceiver;
+import android.content.Context;
+import android.content.Intent;
+import android.net.Uri;
+import android.os.Handler;
+import android.os.Looper;
+import android.os.SystemClock;
+import android.os.UserHandle;
+import android.util.LongArrayQueue;
+
+import androidx.test.runner.AndroidJUnit4;
+
+import com.android.server.LocalServices;
+import com.android.server.utils.quota.CountQuotaTracker.ExecutionStats;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.ArgumentCaptor;
+import org.mockito.InOrder;
+import org.mockito.Mock;
+import org.mockito.MockitoSession;
+import org.mockito.quality.Strictness;
+
+/**
+ * Tests for {@link CountQuotaTracker}.
+ */
+@RunWith(AndroidJUnit4.class)
+public class CountQuotaTrackerTest {
+    private static final long SECOND_IN_MILLIS = 1000L;
+    private static final long MINUTE_IN_MILLIS = 60 * SECOND_IN_MILLIS;
+    private static final long HOUR_IN_MILLIS = 60 * MINUTE_IN_MILLIS;
+    private static final String TAG_CLEANUP = "*CountQuotaTracker.cleanup*";
+    private static final String TAG_QUOTA_CHECK = "*QuotaTracker.quota_check*";
+    private static final String TEST_PACKAGE = "com.android.frameworks.mockingservicestests";
+    private static final String TEST_TAG = "testing";
+    private static final int TEST_UID = 10987;
+    private static final int TEST_USER_ID = 0;
+
+    /** A {@link Category} to represent the ACTIVE standby bucket. */
+    private static final Category ACTIVE_BUCKET_CATEGORY = new Category("ACTIVE");
+
+    /** A {@link Category} to represent the WORKING_SET standby bucket. */
+    private static final Category WORKING_SET_BUCKET_CATEGORY = new Category("WORKING_SET");
+
+    /** A {@link Category} to represent the FREQUENT standby bucket. */
+    private static final Category FREQUENT_BUCKET_CATEGORY = new Category("FREQUENT");
+
+    /** A {@link Category} to represent the RARE standby bucket. */
+    private static final Category RARE_BUCKET_CATEGORY = new Category("RARE");
+
+    private CountQuotaTracker mQuotaTracker;
+    private final CategorizerForTest mCategorizer = new CategorizerForTest();
+    private final InjectorForTest mInjector = new InjectorForTest();
+    private final TestQuotaChangeListener mQuotaChangeListener = new TestQuotaChangeListener();
+    private BroadcastReceiver mReceiver;
+    private MockitoSession mMockingSession;
+    @Mock
+    private AlarmManager mAlarmManager;
+    @Mock
+    private Context mContext;
+
+    static class CategorizerForTest implements Categorizer {
+        private Category mCategoryToUse = SINGLE_CATEGORY;
+
+        @Override
+        public Category getCategory(int userId,
+                String packageName, String tag) {
+            return mCategoryToUse;
+        }
+    }
+
+    private static class InjectorForTest extends QuotaTracker.Injector {
+        private long mElapsedTime = SystemClock.elapsedRealtime();
+
+        @Override
+        long getElapsedRealtime() {
+            return mElapsedTime;
+        }
+
+        @Override
+        boolean isAlarmManagerReady() {
+            return true;
+        }
+    }
+
+    private static class TestQuotaChangeListener implements QuotaChangeListener {
+
+        @Override
+        public void onQuotaStateChanged(int userId, String packageName, String tag) {
+
+        }
+    }
+
+    @Before
+    public void setUp() {
+        mMockingSession = mockitoSession()
+                .initMocks(this)
+                .strictness(Strictness.LENIENT)
+                .mockStatic(LocalServices.class)
+                .startMocking();
+
+        when(mContext.getMainLooper()).thenReturn(Looper.getMainLooper());
+        when(mContext.getSystemService(AlarmManager.class)).thenReturn(mAlarmManager);
+
+        // Freeze the clocks at 24 hours after this moment in time. Several tests create sessions
+        // in the past, and QuotaController sometimes floors values at 0, so if the test time
+        // causes sessions with negative timestamps, they will fail.
+        advanceElapsedClock(24 * HOUR_IN_MILLIS);
+
+        // Initialize real objects.
+        // Capture the listeners.
+        ArgumentCaptor<BroadcastReceiver> receiverCaptor =
+                ArgumentCaptor.forClass(BroadcastReceiver.class);
+        mQuotaTracker = new CountQuotaTracker(mContext, mCategorizer, mInjector);
+        mQuotaTracker.setEnabled(true);
+        mQuotaTracker.setQuotaFree(false);
+        mQuotaTracker.registerQuotaChangeListener(mQuotaChangeListener);
+        verify(mContext, atLeastOnce()).registerReceiverAsUser(
+                receiverCaptor.capture(), eq(UserHandle.ALL), any(), any(), any());
+        mReceiver = receiverCaptor.getValue();
+    }
+
+    @After
+    public void tearDown() {
+        if (mMockingSession != null) {
+            mMockingSession.finishMocking();
+        }
+    }
+
+    /**
+     * Returns true if the two {@link LongArrayQueue}s have the same size and the same elements in
+     * the same order.
+     */
+    private static boolean longArrayQueueEquals(LongArrayQueue queue1, LongArrayQueue queue2) {
+        if (queue1 == queue2) {
+            return true;
+        } else if (queue1 == null || queue2 == null) {
+            return false;
+        }
+        if (queue1.size() == queue2.size()) {
+            for (int i = 0; i < queue1.size(); ++i) {
+                if (queue1.get(i) != queue2.get(i)) {
+                    return false;
+                }
+            }
+            return true;
+        }
+        return false;
+    }
+
+    private void advanceElapsedClock(long incrementMs) {
+        mInjector.mElapsedTime += incrementMs;
+    }
+
+    private void logEvents(int count) {
+        logEvents(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, count);
+    }
+
+    private void logEvents(int userId, String pkgName, String tag, int count) {
+        for (int i = 0; i < count; ++i) {
+            mQuotaTracker.noteEvent(userId, pkgName, tag);
+        }
+    }
+
+    private void logEventAt(long timeElapsed) {
+        logEventAt(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, timeElapsed);
+    }
+
+    private void logEventAt(int userId, String pkgName, String tag, long timeElapsed) {
+        long now = mInjector.getElapsedRealtime();
+        mInjector.mElapsedTime = timeElapsed;
+        mQuotaTracker.noteEvent(userId, pkgName, tag);
+        mInjector.mElapsedTime = now;
+    }
+
+    private void logEventsAt(int userId, String pkgName, String tag, long timeElapsed, int count) {
+        for (int i = 0; i < count; ++i) {
+            logEventAt(userId, pkgName, tag, timeElapsed);
+        }
+    }
+
+    @Test
+    public void testDeleteObsoleteEventsLocked() {
+        // Count window size should only apply to event list.
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 7, 2 * HOUR_IN_MILLIS);
+
+        final long now = mInjector.getElapsedRealtime();
+
+        logEventAt(now - 6 * HOUR_IN_MILLIS);
+        logEventAt(now - 5 * HOUR_IN_MILLIS);
+        logEventAt(now - 4 * HOUR_IN_MILLIS);
+        logEventAt(now - 3 * HOUR_IN_MILLIS);
+        logEventAt(now - 2 * HOUR_IN_MILLIS);
+        logEventAt(now - HOUR_IN_MILLIS);
+        logEventAt(now - 1);
+
+        LongArrayQueue expectedEvents = new LongArrayQueue();
+        expectedEvents.addLast(now - HOUR_IN_MILLIS);
+        expectedEvents.addLast(now - 1);
+
+        mQuotaTracker.deleteObsoleteEventsLocked();
+
+        LongArrayQueue remainingEvents = mQuotaTracker.getEvents(TEST_USER_ID, TEST_PACKAGE,
+                TEST_TAG);
+        assertTrue(longArrayQueueEquals(expectedEvents, remainingEvents));
+    }
+
+    @Test
+    public void testAppRemoval() {
+        final long now = mInjector.getElapsedRealtime();
+        logEventAt(TEST_USER_ID, "com.android.test.remove", "tag1", now - (6 * HOUR_IN_MILLIS));
+        logEventAt(TEST_USER_ID, "com.android.test.remove", "tag2",
+                now - (2 * HOUR_IN_MILLIS + MINUTE_IN_MILLIS));
+        logEventAt(TEST_USER_ID, "com.android.test.remove", "tag3", now - (HOUR_IN_MILLIS));
+        // Test that another app isn't affected.
+        LongArrayQueue expected1 = new LongArrayQueue();
+        expected1.addLast(now - 10 * MINUTE_IN_MILLIS);
+        LongArrayQueue expected2 = new LongArrayQueue();
+        expected2.addLast(now - 70 * MINUTE_IN_MILLIS);
+        logEventAt(TEST_USER_ID, "com.android.test.stay", "tag1", now - 10 * MINUTE_IN_MILLIS);
+        logEventAt(TEST_USER_ID, "com.android.test.stay", "tag2", now - 70 * MINUTE_IN_MILLIS);
+
+        Intent removal = new Intent(Intent.ACTION_PACKAGE_FULLY_REMOVED,
+                Uri.fromParts("package", "com.android.test.remove", null));
+        removal.putExtra(Intent.EXTRA_UID, TEST_UID);
+        mReceiver.onReceive(mContext, removal);
+        assertNull(
+                mQuotaTracker.getEvents(TEST_USER_ID, "com.android.test.remove", "tag1"));
+        assertNull(
+                mQuotaTracker.getEvents(TEST_USER_ID, "com.android.test.remove", "tag2"));
+        assertNull(
+                mQuotaTracker.getEvents(TEST_USER_ID, "com.android.test.remove", "tag3"));
+        assertTrue(longArrayQueueEquals(expected1,
+                mQuotaTracker.getEvents(TEST_USER_ID, "com.android.test.stay", "tag1")));
+        assertTrue(longArrayQueueEquals(expected2,
+                mQuotaTracker.getEvents(TEST_USER_ID, "com.android.test.stay", "tag2")));
+    }
+
+    @Test
+    public void testUserRemoval() {
+        final long now = mInjector.getElapsedRealtime();
+        logEventAt(TEST_USER_ID, TEST_PACKAGE, "tag1", now - (6 * HOUR_IN_MILLIS));
+        logEventAt(TEST_USER_ID, TEST_PACKAGE, "tag2",
+                now - (2 * HOUR_IN_MILLIS + MINUTE_IN_MILLIS));
+        logEventAt(TEST_USER_ID, TEST_PACKAGE, "tag3", now - (HOUR_IN_MILLIS));
+        // Test that another user isn't affected.
+        LongArrayQueue expected = new LongArrayQueue();
+        expected.addLast(now - (70 * MINUTE_IN_MILLIS));
+        expected.addLast(now - (10 * MINUTE_IN_MILLIS));
+        logEventAt(10, TEST_PACKAGE, "tag4", now - (70 * MINUTE_IN_MILLIS));
+        logEventAt(10, TEST_PACKAGE, "tag4", now - 10 * MINUTE_IN_MILLIS);
+
+        Intent removal = new Intent(Intent.ACTION_USER_REMOVED);
+        removal.putExtra(Intent.EXTRA_USER_HANDLE, TEST_USER_ID);
+        mReceiver.onReceive(mContext, removal);
+        assertNull(mQuotaTracker.getEvents(TEST_USER_ID, TEST_PACKAGE, "tag1"));
+        assertNull(mQuotaTracker.getEvents(TEST_USER_ID, TEST_PACKAGE, "tag2"));
+        assertNull(mQuotaTracker.getEvents(TEST_USER_ID, TEST_PACKAGE, "tag3"));
+        longArrayQueueEquals(expected, mQuotaTracker.getEvents(10, TEST_PACKAGE, "tag4"));
+    }
+
+    @Test
+    public void testUpdateExecutionStatsLocked_NoTimer() {
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 3, 24 * HOUR_IN_MILLIS);
+        final long now = mInjector.getElapsedRealtime();
+
+        // Added in chronological order.
+        logEventAt(now - 4 * HOUR_IN_MILLIS);
+        logEventAt(now - HOUR_IN_MILLIS);
+        logEventAt(now - 5 * MINUTE_IN_MILLIS);
+        logEventAt(now - MINUTE_IN_MILLIS);
+
+        // Test an app that hasn't had any activity.
+        ExecutionStats expectedStats = new ExecutionStats();
+        ExecutionStats inputStats = new ExecutionStats();
+
+        inputStats.windowSizeMs = expectedStats.windowSizeMs = 12 * HOUR_IN_MILLIS;
+        inputStats.countLimit = expectedStats.countLimit = 3;
+        // Invalid time is now +24 hours since there are no sessions at all for the app.
+        expectedStats.expirationTimeElapsed = now + 24 * HOUR_IN_MILLIS;
+        mQuotaTracker.updateExecutionStatsLocked(TEST_USER_ID, "com.android.test.not.run", TEST_TAG,
+                inputStats);
+        assertEquals(expectedStats, inputStats);
+
+        // Now test app that has had activity.
+
+        inputStats.windowSizeMs = expectedStats.windowSizeMs = MINUTE_IN_MILLIS;
+        // Invalid time is now since there was an event exactly windowSizeMs ago.
+        expectedStats.expirationTimeElapsed = now;
+        expectedStats.countInWindow = 1;
+        mQuotaTracker.updateExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, inputStats);
+        assertEquals(expectedStats, inputStats);
+
+        inputStats.windowSizeMs = expectedStats.windowSizeMs = 3 * MINUTE_IN_MILLIS;
+        expectedStats.expirationTimeElapsed = now + 2 * MINUTE_IN_MILLIS;
+        expectedStats.countInWindow = 1;
+        mQuotaTracker.updateExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, inputStats);
+        assertEquals(expectedStats, inputStats);
+
+        inputStats.windowSizeMs = expectedStats.windowSizeMs = 4 * MINUTE_IN_MILLIS;
+        expectedStats.expirationTimeElapsed = now + 3 * MINUTE_IN_MILLIS;
+        expectedStats.countInWindow = 1;
+        mQuotaTracker.updateExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, inputStats);
+        assertEquals(expectedStats, inputStats);
+
+        inputStats.windowSizeMs = expectedStats.windowSizeMs = 49 * MINUTE_IN_MILLIS;
+        // Invalid time is now +44 minutes since the earliest session in the window is now-5
+        // minutes.
+        expectedStats.expirationTimeElapsed = now + 44 * MINUTE_IN_MILLIS;
+        expectedStats.countInWindow = 2;
+        mQuotaTracker.updateExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, inputStats);
+        assertEquals(expectedStats, inputStats);
+
+        inputStats.windowSizeMs = expectedStats.windowSizeMs = 50 * MINUTE_IN_MILLIS;
+        expectedStats.expirationTimeElapsed = now + 45 * MINUTE_IN_MILLIS;
+        expectedStats.countInWindow = 2;
+        mQuotaTracker.updateExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, inputStats);
+        assertEquals(expectedStats, inputStats);
+
+        inputStats.windowSizeMs = expectedStats.windowSizeMs = HOUR_IN_MILLIS;
+        // Invalid time is now since the event is at the very edge of the window
+        // cutoff time.
+        expectedStats.expirationTimeElapsed = now;
+        expectedStats.countInWindow = 3;
+        // App is at event count limit but the oldest session is at the edge of the window, so
+        // in quota time is now.
+        expectedStats.inQuotaTimeElapsed = now;
+        mQuotaTracker.updateExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, inputStats);
+        assertEquals(expectedStats, inputStats);
+
+        inputStats.windowSizeMs = expectedStats.windowSizeMs = 2 * HOUR_IN_MILLIS;
+        expectedStats.expirationTimeElapsed = now + HOUR_IN_MILLIS;
+        expectedStats.countInWindow = 3;
+        expectedStats.inQuotaTimeElapsed = now + HOUR_IN_MILLIS;
+        mQuotaTracker.updateExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, inputStats);
+        assertEquals(expectedStats, inputStats);
+
+        inputStats.windowSizeMs = expectedStats.windowSizeMs = 5 * HOUR_IN_MILLIS;
+        expectedStats.expirationTimeElapsed = now + HOUR_IN_MILLIS;
+        expectedStats.countInWindow = 4;
+        expectedStats.inQuotaTimeElapsed = now + 4 * HOUR_IN_MILLIS;
+        mQuotaTracker.updateExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, inputStats);
+        assertEquals(expectedStats, inputStats);
+
+        inputStats.windowSizeMs = expectedStats.windowSizeMs = 6 * HOUR_IN_MILLIS;
+        expectedStats.expirationTimeElapsed = now + 2 * HOUR_IN_MILLIS;
+        expectedStats.countInWindow = 4;
+        expectedStats.inQuotaTimeElapsed = now + 5 * HOUR_IN_MILLIS;
+        mQuotaTracker.updateExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, inputStats);
+        assertEquals(expectedStats, inputStats);
+    }
+
+    /**
+     * Tests that getExecutionStatsLocked returns the correct stats.
+     */
+    @Test
+    public void testGetExecutionStatsLocked_Values() {
+        // The handler could cause changes to the cached stats, so prevent it from operating in
+        // this test.
+        Handler handler = mQuotaTracker.getHandler();
+        spyOn(handler);
+        doNothing().when(handler).handleMessage(any());
+
+        mQuotaTracker.setCountLimit(RARE_BUCKET_CATEGORY, 3, 24 * HOUR_IN_MILLIS);
+        mQuotaTracker.setCountLimit(FREQUENT_BUCKET_CATEGORY, 4, 8 * HOUR_IN_MILLIS);
+        mQuotaTracker.setCountLimit(WORKING_SET_BUCKET_CATEGORY, 9, 2 * HOUR_IN_MILLIS);
+        mQuotaTracker.setCountLimit(ACTIVE_BUCKET_CATEGORY, 10, 10 * MINUTE_IN_MILLIS);
+
+        final long now = mInjector.getElapsedRealtime();
+
+        logEventAt(now - 23 * HOUR_IN_MILLIS);
+        logEventAt(now - 7 * HOUR_IN_MILLIS);
+        logEventAt(now - 5 * HOUR_IN_MILLIS);
+        logEventAt(now - 2 * HOUR_IN_MILLIS);
+        logEventAt(now - 5 * MINUTE_IN_MILLIS);
+
+        ExecutionStats expectedStats = new ExecutionStats();
+
+        // Active
+        expectedStats.expirationTimeElapsed = now + 5 * MINUTE_IN_MILLIS;
+        expectedStats.windowSizeMs = 10 * MINUTE_IN_MILLIS;
+        expectedStats.countLimit = 10;
+        expectedStats.countInWindow = 1;
+        mCategorizer.mCategoryToUse = ACTIVE_BUCKET_CATEGORY;
+        assertEquals(expectedStats,
+                mQuotaTracker.getExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG));
+
+        // Working
+        expectedStats.expirationTimeElapsed = now;
+        expectedStats.windowSizeMs = 2 * HOUR_IN_MILLIS;
+        expectedStats.countLimit = 9;
+        expectedStats.countInWindow = 2;
+        mCategorizer.mCategoryToUse = WORKING_SET_BUCKET_CATEGORY;
+        assertEquals(expectedStats,
+                mQuotaTracker.getExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG));
+
+        // Frequent
+        expectedStats.expirationTimeElapsed = now + HOUR_IN_MILLIS;
+        expectedStats.windowSizeMs = 8 * HOUR_IN_MILLIS;
+        expectedStats.countLimit = 4;
+        expectedStats.countInWindow = 4;
+        expectedStats.inQuotaTimeElapsed = now + HOUR_IN_MILLIS;
+        mCategorizer.mCategoryToUse = FREQUENT_BUCKET_CATEGORY;
+        assertEquals(expectedStats,
+                mQuotaTracker.getExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG));
+
+        // Rare
+        expectedStats.expirationTimeElapsed = now + HOUR_IN_MILLIS;
+        expectedStats.windowSizeMs = 24 * HOUR_IN_MILLIS;
+        expectedStats.countLimit = 3;
+        expectedStats.countInWindow = 5;
+        expectedStats.inQuotaTimeElapsed = now + 19 * HOUR_IN_MILLIS;
+        mCategorizer.mCategoryToUse = RARE_BUCKET_CATEGORY;
+        assertEquals(expectedStats,
+                mQuotaTracker.getExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG));
+    }
+
+    /**
+     * Tests that getExecutionStatsLocked returns the correct stats soon after device startup.
+     */
+    @Test
+    public void testGetExecutionStatsLocked_Values_BeginningOfTime() {
+        // Set time to 3 minutes after boot.
+        mInjector.mElapsedTime = 3 * MINUTE_IN_MILLIS;
+
+        logEventAt(30_000);
+        logEventAt(MINUTE_IN_MILLIS);
+        logEventAt(2 * MINUTE_IN_MILLIS);
+
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 10, 2 * HOUR_IN_MILLIS);
+
+        ExecutionStats expectedStats = new ExecutionStats();
+
+        expectedStats.windowSizeMs = 2 * HOUR_IN_MILLIS;
+        expectedStats.countLimit = 10;
+        expectedStats.countInWindow = 3;
+        expectedStats.expirationTimeElapsed = 2 * HOUR_IN_MILLIS + 30_000;
+        assertEquals(expectedStats,
+                mQuotaTracker.getExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG));
+    }
+
+    @Test
+    public void testisWithinQuota_GlobalQuotaFree() {
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 0, 2 * HOUR_IN_MILLIS);
+        mQuotaTracker.setQuotaFree(true);
+        assertTrue(mQuotaTracker.isWithinQuota(TEST_USER_ID, TEST_PACKAGE, null));
+        assertTrue(mQuotaTracker.isWithinQuota(TEST_USER_ID, "com.android.random.app", null));
+    }
+
+    @Test
+    public void testisWithinQuota_UptcQuotaFree() {
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 0, 2 * HOUR_IN_MILLIS);
+        mQuotaTracker.setQuotaFree(TEST_USER_ID, TEST_PACKAGE, true);
+        assertTrue(mQuotaTracker.isWithinQuota(TEST_USER_ID, TEST_PACKAGE, null));
+        assertFalse(
+                mQuotaTracker.isWithinQuota(TEST_USER_ID, "com.android.random.app", null));
+    }
+
+    @Test
+    public void testisWithinQuota_UnderCount() {
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 10, 2 * HOUR_IN_MILLIS);
+        logEvents(5);
+        assertTrue(mQuotaTracker.isWithinQuota(TEST_USER_ID, TEST_PACKAGE, TEST_TAG));
+    }
+
+    @Test
+    public void testisWithinQuota_OverCount() {
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 25, HOUR_IN_MILLIS);
+        logEvents(TEST_USER_ID, "com.android.test.spam", TEST_TAG, 30);
+        assertFalse(mQuotaTracker.isWithinQuota(TEST_USER_ID, "com.android.test.spam", TEST_TAG));
+    }
+
+    @Test
+    public void testisWithinQuota_EqualsCount() {
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 25, HOUR_IN_MILLIS);
+        logEvents(25);
+        assertFalse(mQuotaTracker.isWithinQuota(TEST_USER_ID, TEST_PACKAGE, TEST_TAG));
+    }
+
+    @Test
+    public void testisWithinQuota_DifferentCategories() {
+        mQuotaTracker.setCountLimit(RARE_BUCKET_CATEGORY, 3, 24 * HOUR_IN_MILLIS);
+        mQuotaTracker.setCountLimit(FREQUENT_BUCKET_CATEGORY, 4, 24 * HOUR_IN_MILLIS);
+        mQuotaTracker.setCountLimit(WORKING_SET_BUCKET_CATEGORY, 5, 24 * HOUR_IN_MILLIS);
+        mQuotaTracker.setCountLimit(ACTIVE_BUCKET_CATEGORY, 6, 24 * HOUR_IN_MILLIS);
+
+        for (int i = 0; i < 7; ++i) {
+            logEvents(1);
+
+            mCategorizer.mCategoryToUse = RARE_BUCKET_CATEGORY;
+            assertEquals("Rare has incorrect quota status with " + (i + 1) + " events",
+                    i < 2,
+                    mQuotaTracker.isWithinQuota(TEST_USER_ID, TEST_PACKAGE, TEST_TAG));
+            mCategorizer.mCategoryToUse = FREQUENT_BUCKET_CATEGORY;
+            assertEquals("Frequent has incorrect quota status with " + (i + 1) + " events",
+                    i < 3,
+                    mQuotaTracker.isWithinQuota(TEST_USER_ID, TEST_PACKAGE, TEST_TAG));
+            mCategorizer.mCategoryToUse = WORKING_SET_BUCKET_CATEGORY;
+            assertEquals("Working has incorrect quota status with " + (i + 1) + " events",
+                    i < 4,
+                    mQuotaTracker.isWithinQuota(TEST_USER_ID, TEST_PACKAGE, TEST_TAG));
+            mCategorizer.mCategoryToUse = ACTIVE_BUCKET_CATEGORY;
+            assertEquals("Active has incorrect quota status with " + (i + 1) + " events",
+                    i < 5,
+                    mQuotaTracker.isWithinQuota(TEST_USER_ID, TEST_PACKAGE, TEST_TAG));
+        }
+    }
+
+    @Test
+    public void testMaybeScheduleCleanupAlarmLocked() {
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 5, 24 * HOUR_IN_MILLIS);
+
+        // No sessions saved yet.
+        mQuotaTracker.maybeScheduleCleanupAlarmLocked();
+        verify(mAlarmManager, never()).set(anyInt(), anyLong(), eq(TAG_CLEANUP), any(), any());
+
+        // Test with only one timing session saved.
+        final long now = mInjector.getElapsedRealtime();
+        logEventAt(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, now - 6 * HOUR_IN_MILLIS);
+        mQuotaTracker.maybeScheduleCleanupAlarmLocked();
+        verify(mAlarmManager, timeout(1000).times(1))
+                .set(anyInt(), eq(now + 18 * HOUR_IN_MILLIS), eq(TAG_CLEANUP), any(), any());
+
+        // Test with new (more recent) timing sessions saved. AlarmManger shouldn't be called again.
+        logEventAt(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, now - 3 * HOUR_IN_MILLIS);
+        logEventAt(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, now - HOUR_IN_MILLIS);
+        mQuotaTracker.maybeScheduleCleanupAlarmLocked();
+        verify(mAlarmManager, times(1))
+                .set(anyInt(), eq(now + 18 * HOUR_IN_MILLIS), eq(TAG_CLEANUP), any(), any());
+    }
+
+    /**
+     * Tests that maybeScheduleStartAlarm schedules an alarm for the right time.
+     */
+    @Test
+    public void testMaybeScheduleStartAlarmLocked() {
+        // logEvent calls maybeScheduleCleanupAlarmLocked which interferes with these tests
+        // because it schedules an alarm too. Prevent it from doing so.
+        spyOn(mQuotaTracker);
+        doNothing().when(mQuotaTracker).maybeScheduleCleanupAlarmLocked();
+
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 10, 8 * HOUR_IN_MILLIS);
+
+        // No sessions saved yet.
+        mQuotaTracker.maybeScheduleStartAlarmLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        verify(mAlarmManager, never()).set(anyInt(), anyLong(), eq(TAG_QUOTA_CHECK), any(), any());
+
+        // Test with timing sessions out of window.
+        final long now = mInjector.getElapsedRealtime();
+        logEventsAt(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, now - 10 * HOUR_IN_MILLIS, 20);
+        mQuotaTracker.maybeScheduleStartAlarmLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        verify(mAlarmManager, never()).set(anyInt(), anyLong(), eq(TAG_QUOTA_CHECK), any(), any());
+
+        // Test with timing sessions in window but still in quota.
+        final long start = now - (6 * HOUR_IN_MILLIS);
+        final long expectedAlarmTime = start + 8 * HOUR_IN_MILLIS;
+        logEventsAt(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, start, 5);
+        mQuotaTracker.maybeScheduleStartAlarmLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        verify(mAlarmManager, never()).set(anyInt(), anyLong(), eq(TAG_QUOTA_CHECK), any(), any());
+
+        // Add some more sessions, but still in quota.
+        logEventsAt(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, now - 3 * HOUR_IN_MILLIS, 1);
+        logEventsAt(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, now - HOUR_IN_MILLIS, 3);
+        mQuotaTracker.maybeScheduleStartAlarmLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        verify(mAlarmManager, never()).set(anyInt(), anyLong(), eq(TAG_QUOTA_CHECK), any(), any());
+
+        // Test when out of quota.
+        logEventsAt(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, now - HOUR_IN_MILLIS, 1);
+        mQuotaTracker.maybeScheduleStartAlarmLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        verify(mAlarmManager, timeout(1000).times(1))
+                .set(anyInt(), eq(expectedAlarmTime), eq(TAG_QUOTA_CHECK), any(), any());
+
+        // Alarm already scheduled, so make sure it's not scheduled again.
+        mQuotaTracker.maybeScheduleStartAlarmLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        verify(mAlarmManager, times(1))
+                .set(anyInt(), eq(expectedAlarmTime), eq(TAG_QUOTA_CHECK), any(), any());
+    }
+
+    /** Tests that the start alarm is properly rescheduled if the app's category is changed. */
+    @Test
+    public void testMaybeScheduleStartAlarmLocked_CategoryChange() {
+        // logEvent calls maybeScheduleCleanupAlarmLocked which interferes with these tests
+        // because it schedules an alarm too. Prevent it from doing so.
+        spyOn(mQuotaTracker);
+        doNothing().when(mQuotaTracker).maybeScheduleCleanupAlarmLocked();
+
+        mQuotaTracker.setCountLimit(RARE_BUCKET_CATEGORY, 10, 24 * HOUR_IN_MILLIS);
+        mQuotaTracker.setCountLimit(FREQUENT_BUCKET_CATEGORY, 10, 8 * HOUR_IN_MILLIS);
+        mQuotaTracker.setCountLimit(WORKING_SET_BUCKET_CATEGORY, 10, 2 * HOUR_IN_MILLIS);
+        mQuotaTracker.setCountLimit(ACTIVE_BUCKET_CATEGORY, 10, 10 * MINUTE_IN_MILLIS);
+
+        final long now = mInjector.getElapsedRealtime();
+
+        // Affects rare bucket
+        logEventsAt(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, now - 12 * HOUR_IN_MILLIS, 9);
+        // Affects frequent and rare buckets
+        logEventsAt(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, now - 4 * HOUR_IN_MILLIS, 4);
+        // Affects working, frequent, and rare buckets
+        final long outOfQuotaTime = now - HOUR_IN_MILLIS;
+        logEventsAt(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, outOfQuotaTime, 7);
+        // Affects all buckets
+        logEventsAt(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, now - 5 * MINUTE_IN_MILLIS, 3);
+
+        InOrder inOrder = inOrder(mAlarmManager);
+
+        // Start in ACTIVE bucket.
+        mCategorizer.mCategoryToUse = ACTIVE_BUCKET_CATEGORY;
+        mQuotaTracker.maybeScheduleStartAlarmLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        inOrder.verify(mAlarmManager, never())
+                .set(anyInt(), anyLong(), eq(TAG_QUOTA_CHECK), any(), any());
+        inOrder.verify(mAlarmManager, never()).cancel(any(AlarmManager.OnAlarmListener.class));
+
+        // And down from there.
+        final long expectedWorkingAlarmTime = outOfQuotaTime + (2 * HOUR_IN_MILLIS);
+        mCategorizer.mCategoryToUse = WORKING_SET_BUCKET_CATEGORY;
+        mQuotaTracker.maybeScheduleStartAlarmLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        inOrder.verify(mAlarmManager, timeout(1000).times(1))
+                .set(anyInt(), eq(expectedWorkingAlarmTime), eq(TAG_QUOTA_CHECK), any(), any());
+
+        final long expectedFrequentAlarmTime = outOfQuotaTime + (8 * HOUR_IN_MILLIS);
+        mCategorizer.mCategoryToUse = FREQUENT_BUCKET_CATEGORY;
+        mQuotaTracker.maybeScheduleStartAlarmLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        inOrder.verify(mAlarmManager, timeout(1000).times(1))
+                .set(anyInt(), eq(expectedFrequentAlarmTime), eq(TAG_QUOTA_CHECK), any(), any());
+
+        final long expectedRareAlarmTime = outOfQuotaTime + (24 * HOUR_IN_MILLIS);
+        mCategorizer.mCategoryToUse = RARE_BUCKET_CATEGORY;
+        mQuotaTracker.maybeScheduleStartAlarmLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        inOrder.verify(mAlarmManager, timeout(1000).times(1))
+                .set(anyInt(), eq(expectedRareAlarmTime), eq(TAG_QUOTA_CHECK), any(), any());
+
+        // And back up again.
+        mCategorizer.mCategoryToUse = FREQUENT_BUCKET_CATEGORY;
+        mQuotaTracker.maybeScheduleStartAlarmLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        inOrder.verify(mAlarmManager, timeout(1000).times(1))
+                .set(anyInt(), eq(expectedFrequentAlarmTime), eq(TAG_QUOTA_CHECK), any(), any());
+
+        mCategorizer.mCategoryToUse = WORKING_SET_BUCKET_CATEGORY;
+        mQuotaTracker.maybeScheduleStartAlarmLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        inOrder.verify(mAlarmManager, timeout(1000).times(1))
+                .set(anyInt(), eq(expectedWorkingAlarmTime), eq(TAG_QUOTA_CHECK), any(), any());
+
+        mCategorizer.mCategoryToUse = ACTIVE_BUCKET_CATEGORY;
+        mQuotaTracker.maybeScheduleStartAlarmLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        inOrder.verify(mAlarmManager, timeout(1000).times(1))
+                .cancel(any(AlarmManager.OnAlarmListener.class));
+        inOrder.verify(mAlarmManager, timeout(1000).times(0))
+                .set(anyInt(), anyLong(), eq(TAG_QUOTA_CHECK), any(), any());
+    }
+
+    @Test
+    public void testConstantsUpdating_ValidValues() {
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 0, 60_000);
+        assertEquals(0, mQuotaTracker.getLimit(SINGLE_CATEGORY));
+        assertEquals(60_000, mQuotaTracker.getWindowSizeMs(SINGLE_CATEGORY));
+    }
+
+    @Test
+    public void testConstantsUpdating_InvalidValues() {
+        // Test negatives.
+        try {
+            mQuotaTracker.setCountLimit(SINGLE_CATEGORY, -1, 5000);
+            fail("Negative count limit didn't throw an exception");
+        } catch (IllegalArgumentException e) {
+            // Success
+        }
+        try {
+            mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 1, -1);
+            fail("Negative count window size didn't throw an exception");
+        } catch (IllegalArgumentException e) {
+            // Success
+        }
+
+        // Test window sizes too low.
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 0, 1);
+        assertEquals(MIN_WINDOW_SIZE_MS, mQuotaTracker.getWindowSizeMs(SINGLE_CATEGORY));
+
+        // Test window sizes too high.
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 0, 365 * 24 * HOUR_IN_MILLIS);
+        assertEquals(MAX_WINDOW_SIZE_MS, mQuotaTracker.getWindowSizeMs(SINGLE_CATEGORY));
+    }
+
+    /** Tests that events aren't counted when global quota is free. */
+    @Test
+    public void testLogEvent_GlobalQuotaFree() {
+        mQuotaTracker.setQuotaFree(true);
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 10, 2 * HOUR_IN_MILLIS);
+
+        ExecutionStats stats =
+                mQuotaTracker.getExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        assertEquals(0, stats.countInWindow);
+
+        for (int i = 0; i < 10; ++i) {
+            mQuotaTracker.noteEvent(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+            advanceElapsedClock(10 * SECOND_IN_MILLIS);
+
+            mQuotaTracker.updateExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, stats);
+            assertEquals(0, stats.countInWindow);
+        }
+    }
+
+    /**
+     * Tests that events are counted when global quota is not free.
+     */
+    @Test
+    public void testLogEvent_GlobalQuotaNotFree() {
+        mQuotaTracker.setQuotaFree(false);
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 10, 2 * HOUR_IN_MILLIS);
+
+        ExecutionStats stats =
+                mQuotaTracker.getExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        assertEquals(0, stats.countInWindow);
+
+        for (int i = 0; i < 10; ++i) {
+            mQuotaTracker.noteEvent(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+            advanceElapsedClock(10 * SECOND_IN_MILLIS);
+
+            mQuotaTracker.updateExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, stats);
+            assertEquals(i + 1, stats.countInWindow);
+        }
+    }
+
+    /** Tests that events aren't counted when the uptc quota is free. */
+    @Test
+    public void testLogEvent_UptcQuotaFree() {
+        mQuotaTracker.setQuotaFree(TEST_USER_ID, TEST_PACKAGE, true);
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 10, 2 * HOUR_IN_MILLIS);
+
+        ExecutionStats stats =
+                mQuotaTracker.getExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        assertEquals(0, stats.countInWindow);
+
+        for (int i = 0; i < 10; ++i) {
+            mQuotaTracker.noteEvent(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+            advanceElapsedClock(10 * SECOND_IN_MILLIS);
+
+            mQuotaTracker.updateExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, stats);
+            assertEquals(0, stats.countInWindow);
+        }
+    }
+
+    /**
+     * Tests that events are counted when UPTC quota is not free.
+     */
+    @Test
+    public void testLogEvent_UptcQuotaNotFree() {
+        mQuotaTracker.setQuotaFree(TEST_USER_ID, TEST_PACKAGE, false);
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 10, 2 * HOUR_IN_MILLIS);
+
+        ExecutionStats stats =
+                mQuotaTracker.getExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        assertEquals(0, stats.countInWindow);
+
+        for (int i = 0; i < 10; ++i) {
+            mQuotaTracker.noteEvent(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+            advanceElapsedClock(10 * SECOND_IN_MILLIS);
+
+            mQuotaTracker.updateExecutionStatsLocked(TEST_USER_ID, TEST_PACKAGE, TEST_TAG, stats);
+            assertEquals(i + 1, stats.countInWindow);
+        }
+    }
+
+    /**
+     * Tests that QuotaChangeListeners are notified when a UPTC reaches its count quota.
+     */
+    @Test
+    public void testTracking_OutOfQuota() {
+        spyOn(mQuotaChangeListener);
+
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 10, 2 * HOUR_IN_MILLIS);
+        logEvents(9);
+
+        mQuotaTracker.noteEvent(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+
+        // Wait for some extra time to allow for processing.
+        verify(mQuotaChangeListener, timeout(3 * SECOND_IN_MILLIS).times(1))
+                .onQuotaStateChanged(eq(TEST_USER_ID), eq(TEST_PACKAGE), eq(TEST_TAG));
+        assertFalse(mQuotaTracker.isWithinQuota(TEST_USER_ID, TEST_PACKAGE, TEST_TAG));
+    }
+
+    /**
+     * Tests that QuotaChangeListeners are not incorrectly notified after a UPTC event is logged
+     * quota times.
+     */
+    @Test
+    public void testTracking_InQuota() {
+        spyOn(mQuotaChangeListener);
+
+        mQuotaTracker.setCountLimit(SINGLE_CATEGORY, 5, MINUTE_IN_MILLIS);
+
+        // Log an event once per minute. This is well below the quota, so listeners should not be
+        // notified.
+        for (int i = 0; i < 10; i++) {
+            advanceElapsedClock(MINUTE_IN_MILLIS);
+            mQuotaTracker.noteEvent(TEST_USER_ID, TEST_PACKAGE, TEST_TAG);
+        }
+
+        // Wait for some extra time to allow for processing.
+        verify(mQuotaChangeListener, timeout(3 * SECOND_IN_MILLIS).times(0))
+                .onQuotaStateChanged(eq(TEST_USER_ID), eq(TEST_PACKAGE), eq(TEST_TAG));
+        assertTrue(mQuotaTracker.isWithinQuota(TEST_USER_ID, TEST_PACKAGE, TEST_TAG));
+    }
+}