Limit the UserPackage cache size.

Limit the number of UserPackage objects we keep in the cache.
Also, only cache the objects in the system server's process.

Bug: 268366471
Test: atest android.content.pm.UserPackageTest
Change-Id: I15355e55a6a6ce27ca6a1052f45949aa89f5125c

3 files changed, 102 insertions, 9 deletions

diff --git a/core/java/android/content/pm/UserPackage.java b/core/java/android/content/pm/UserPackage.java
index 7ca92c3d4777..c35e67801b71 100644
--- a/core/java/android/content/pm/UserPackage.java
+++ b/core/java/android/content/pm/UserPackage.java
@@ -18,14 +18,16 @@ package android.content.pm;
 
 import android.annotation.NonNull;
 import android.annotation.UserIdInt;
-import android.os.Process;
-import android.os.UserHandle;
 import android.util.SparseArrayMap;
 
 import com.android.internal.annotations.GuardedBy;
+import com.android.internal.annotations.VisibleForTesting;
 import com.android.internal.util.ArrayUtils;
 
+import libcore.util.EmptyArray;
+
 import java.util.Objects;
+import java.util.Random;
 
 /**
  * POJO to represent a package for a specific user ID.
@@ -34,6 +36,16 @@ import java.util.Objects;
  */
 public final class UserPackage {
     private static final boolean ENABLE_CACHING = true;
+    /**
+     * The maximum number of entries to keep in the cache per user ID.
+     * The value should ideally be high enough to cover all packages on an end-user device,
+     * but low enough that stale or invalid packages would eventually (probably) get removed.
+     * This should benefit components that loop through all packages on a device and use this class,
+     * since being able to cache the objects for all packages on the device
+     * means we don't have to keep recreating the objects.
+     */
+    @VisibleForTesting
+    static final int MAX_NUM_CACHED_ENTRIES_PER_USER = 1000;
 
     @UserIdInt
     public final int userId;
@@ -43,11 +55,13 @@ public final class UserPackage {
     @GuardedBy("sCacheLock")
     private static final SparseArrayMap<String, UserPackage> sCache = new SparseArrayMap<>();
 
-    private static final class NoPreloadHolder {
-        /** Set of userIDs to cache objects for. */
-        @GuardedBy("sCacheLock")
-        private static int[] sUserIds = new int[]{UserHandle.getUserId(Process.myUid())};
-    }
+    /**
+     * Set of userIDs to cache objects for. We start off with an empty set, so there's no caching
+     * by default. The system will override with a valid set of userIDs in its process so that
+     * caching becomes active in the system process.
+     */
+    @GuardedBy("sCacheLock")
+    private static int[] sUserIds = EmptyArray.INT;
 
     private UserPackage(int userId, String packageName) {
         this.userId = userId;
@@ -87,13 +101,14 @@ public final class UserPackage {
         }
 
         synchronized (sCacheLock) {
-            if (!ArrayUtils.contains(NoPreloadHolder.sUserIds, userId)) {
+            if (!ArrayUtils.contains(sUserIds, userId)) {
                 // Don't cache objects for invalid userIds.
                 return new UserPackage(userId, packageName);
             }
 
             UserPackage up = sCache.get(userId, packageName);
             if (up == null) {
+                maybePurgeRandomEntriesLocked(userId);
                 packageName = packageName.intern();
                 up = new UserPackage(userId, packageName);
                 sCache.add(userId, packageName, up);
@@ -121,7 +136,7 @@ public final class UserPackage {
 
         userIds = userIds.clone();
         synchronized (sCacheLock) {
-            NoPreloadHolder.sUserIds = userIds;
+            sUserIds = userIds;
 
             for (int u = sCache.numMaps() - 1; u >= 0; --u) {
                 final int userId = sCache.keyAt(u);
@@ -131,4 +146,35 @@ public final class UserPackage {
             }
         }
     }
+
+    @VisibleForTesting
+    public static int numEntriesForUser(int userId) {
+        synchronized (sCacheLock) {
+            return sCache.numElementsForKey(userId);
+        }
+    }
+
+    /** Purge a random set of entries if the cache size is too large. */
+    @GuardedBy("sCacheLock")
+    private static void maybePurgeRandomEntriesLocked(int userId) {
+        final int uIdx = sCache.indexOfKey(userId);
+        if (uIdx < 0) {
+            return;
+        }
+        int numCached = sCache.numElementsForKeyAt(uIdx);
+        if (numCached < MAX_NUM_CACHED_ENTRIES_PER_USER) {
+            return;
+        }
+        // Purge a random set of 1% of cached elements for the userId. We don't want to use a
+        // deterministic system of purging because that may cause us to repeatedly remove elements
+        // that are frequently added and queried more than others. Choosing a random set
+        // means we will probably eventually remove less useful elements.
+        // An LRU cache is too expensive for this commonly used utility class.
+        final Random rand = new Random();
+        final int numToPurge = Math.max(1, MAX_NUM_CACHED_ENTRIES_PER_USER / 100);
+        for (int i = 0; i < numToPurge && numCached > 0; ++i) {
+            final int removeIdx = rand.nextInt(numCached--);
+            sCache.deleteAt(uIdx, removeIdx);
+        }
+    }
 }
diff --git a/core/java/android/util/SparseArrayMap.java b/core/java/android/util/SparseArrayMap.java
index 1a2c4df96b36..b4e1f59874b0 100644
--- a/core/java/android/util/SparseArrayMap.java
+++ b/core/java/android/util/SparseArrayMap.java
@@ -90,6 +90,14 @@ public class SparseArrayMap<K, V> {
     }
 
     /**
+     * Removes the data for the keyIndex and mapIndex, if there was any.
+     * @hide
+     */
+    public void deleteAt(int keyIndex, int mapIndex) {
+        mData.valueAt(keyIndex).removeAt(mapIndex);
+    }
+
+    /**
      * Get the value associated with the int-K pair.
      */
     @Nullable
diff --git a/core/tests/coretests/src/android/content/pm/UserPackageTest.java b/core/tests/coretests/src/android/content/pm/UserPackageTest.java
new file mode 100644
index 000000000000..5114e2cf9327
--- /dev/null
+++ b/core/tests/coretests/src/android/content/pm/UserPackageTest.java
@@ -0,0 +1,39 @@
+/*
+ * Copyright (C) 2023 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 android.content.pm;
+
+import android.platform.test.annotations.Presubmit;
+
+import junit.framework.TestCase;
+
+@Presubmit
+public class UserPackageTest extends TestCase {
+    public void testCacheLimit() {
+        UserPackage.setValidUserIds(new int[]{0});
+        for (int i = 0; i < UserPackage.MAX_NUM_CACHED_ENTRIES_PER_USER; ++i) {
+            UserPackage.of(0, "app" + i);
+            assertEquals(i + 1, UserPackage.numEntriesForUser(0));
+        }
+
+        for (int i = 0; i < UserPackage.MAX_NUM_CACHED_ENTRIES_PER_USER; ++i) {
+            UserPackage.of(0, "appOverLimit" + i);
+            final int numCached = UserPackage.numEntriesForUser(0);
+            assertTrue(numCached >= 1);
+            assertTrue(numCached <= UserPackage.MAX_NUM_CACHED_ENTRIES_PER_USER);
+        }
+    }
+}