Sort libraries to improve search performance
Bug: 263680288
Test: atest StagedInstallTest
Test: atest PackageManagerServiceBootTest
Test: atest AndroidPackageTest
Change-Id: Ic3f15393b90e9113f3a00c57d11d24ba2fa21fd6
diff --git a/services/core/java/com/android/server/pm/AppStateHelper.java b/services/core/java/com/android/server/pm/AppStateHelper.java
index 32479ee..1a2b01e 100644
--- a/services/core/java/com/android/server/pm/AppStateHelper.java
+++ b/services/core/java/com/android/server/pm/AppStateHelper.java
@@ -37,7 +37,7 @@
import com.android.server.LocalServices;
import java.util.ArrayList;
-import java.util.Collection;
+import java.util.Collections;
import java.util.List;
import java.util.concurrent.TimeUnit;
@@ -159,13 +159,21 @@
return false;
}
- private static boolean containsAny(Collection<String> list, Collection<String> which) {
- if (list.isEmpty()) {
- return false;
- }
- for (var element : which) {
- if (list.contains(element)) {
+ /**
+ * True if {@code arr} contains any element in {@code which}.
+ * Both {@code arr} and {@code which} must be sorted in advance.
+ */
+ private static boolean containsAny(String[] arr, List<String> which) {
+ int s1 = arr.length;
+ int s2 = which.size();
+ for (int i = 0, j = 0; i < s1 && j < s2; ) {
+ int val = arr[i].compareTo(which.get(j));
+ if (val == 0) {
return true;
+ } else if (val < 0) {
+ ++i;
+ } else {
+ ++j;
}
}
return false;
@@ -174,9 +182,9 @@
private void addLibraryDependency(ArraySet<String> results, List<String> libPackageNames) {
var pmInternal = LocalServices.getService(PackageManagerInternal.class);
- var libraryNames = new ArraySet<String>();
- var staticSharedLibraryNames = new ArraySet<String>();
- var sdkLibraryNames = new ArraySet<String>();
+ var libraryNames = new ArrayList<String>();
+ var staticSharedLibraryNames = new ArrayList<String>();
+ var sdkLibraryNames = new ArrayList<String>();
for (var packageName : libPackageNames) {
var pkg = pmInternal.getAndroidPackage(packageName);
if (pkg == null) {
@@ -199,11 +207,19 @@
return;
}
- pmInternal.forEachPackage(pkg -> {
- if (containsAny(pkg.getUsesLibraries(), libraryNames)
- || containsAny(pkg.getUsesOptionalLibraries(), libraryNames)
- || containsAny(pkg.getUsesStaticLibraries(), staticSharedLibraryNames)
- || containsAny(pkg.getUsesSdkLibraries(), sdkLibraryNames)) {
+ Collections.sort(libraryNames);
+ Collections.sort(sdkLibraryNames);
+ Collections.sort(staticSharedLibraryNames);
+
+ pmInternal.forEachPackageState(pkgState -> {
+ var pkg = pkgState.getPkg();
+ if (pkg == null) {
+ return;
+ }
+ if (containsAny(pkg.getUsesLibrariesSorted(), libraryNames)
+ || containsAny(pkg.getUsesOptionalLibrariesSorted(), libraryNames)
+ || containsAny(pkg.getUsesStaticLibrariesSorted(), staticSharedLibraryNames)
+ || containsAny(pkg.getUsesSdkLibrariesSorted(), sdkLibraryNames)) {
results.add(pkg.getPackageName());
}
});
diff --git a/services/core/java/com/android/server/pm/parsing/pkg/AndroidPackageInternal.java b/services/core/java/com/android/server/pm/parsing/pkg/AndroidPackageInternal.java
index 8d43fe7..9eca7d6 100644
--- a/services/core/java/com/android/server/pm/parsing/pkg/AndroidPackageInternal.java
+++ b/services/core/java/com/android/server/pm/parsing/pkg/AndroidPackageInternal.java
@@ -16,6 +16,8 @@
package com.android.server.pm.parsing.pkg;
+import android.annotation.NonNull;
+
import com.android.internal.content.om.OverlayConfig;
import com.android.server.pm.pkg.AndroidPackage;
@@ -31,5 +33,15 @@
*/
public interface AndroidPackageInternal extends AndroidPackage,
OverlayConfig.PackageProvider.Package {
+ @NonNull
+ String[] getUsesLibrariesSorted();
+ @NonNull
+ String[] getUsesOptionalLibrariesSorted();
+
+ @NonNull
+ String[] getUsesSdkLibrariesSorted();
+
+ @NonNull
+ String[] getUsesStaticLibrariesSorted();
}
diff --git a/services/core/java/com/android/server/pm/parsing/pkg/PackageImpl.java b/services/core/java/com/android/server/pm/parsing/pkg/PackageImpl.java
index e361c93..ed9382b 100644
--- a/services/core/java/com/android/server/pm/parsing/pkg/PackageImpl.java
+++ b/services/core/java/com/android/server/pm/parsing/pkg/PackageImpl.java
@@ -93,6 +93,7 @@
import java.io.File;
import java.security.PublicKey;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
@@ -405,6 +406,15 @@
private List<AndroidPackageSplit> mSplits;
@NonNull
+ private String[] mUsesLibrariesSorted;
+ @NonNull
+ private String[] mUsesOptionalLibrariesSorted;
+ @NonNull
+ private String[] mUsesSdkLibrariesSorted;
+ @NonNull
+ private String[] mUsesStaticLibrariesSorted;
+
+ @NonNull
public static PackageImpl forParsing(@NonNull String packageName, @NonNull String baseCodePath,
@NonNull String codePath, @NonNull TypedArray manifestArray, boolean isCoreApp) {
return new PackageImpl(packageName, baseCodePath, codePath, manifestArray, isCoreApp);
@@ -1379,6 +1389,19 @@
@NonNull
@Override
+ public String[] getUsesLibrariesSorted() {
+ if (mUsesLibrariesSorted == null) {
+ // Note lazy-sorting here doesn't break immutability because it always
+ // return the same content. In the case of multi-threading, data race in accessing
+ // mUsesLibrariesSorted might result in unnecessary creation of sorted copies
+ // which is OK because the case is quite rare.
+ mUsesLibrariesSorted = sortLibraries(usesLibraries);
+ }
+ return mUsesLibrariesSorted;
+ }
+
+ @NonNull
+ @Override
public List<String> getUsesNativeLibraries() {
return usesNativeLibraries;
}
@@ -1391,6 +1414,15 @@
@NonNull
@Override
+ public String[] getUsesOptionalLibrariesSorted() {
+ if (mUsesOptionalLibrariesSorted == null) {
+ mUsesOptionalLibrariesSorted = sortLibraries(usesOptionalLibraries);
+ }
+ return mUsesOptionalLibrariesSorted;
+ }
+
+ @NonNull
+ @Override
public List<String> getUsesOptionalNativeLibraries() {
return usesOptionalNativeLibraries;
}
@@ -1405,6 +1437,15 @@
@Override
public List<String> getUsesSdkLibraries() { return usesSdkLibraries; }
+ @NonNull
+ @Override
+ public String[] getUsesSdkLibrariesSorted() {
+ if (mUsesSdkLibrariesSorted == null) {
+ mUsesSdkLibrariesSorted = sortLibraries(usesSdkLibraries);
+ }
+ return mUsesSdkLibrariesSorted;
+ }
+
@Nullable
@Override
public String[][] getUsesSdkLibrariesCertDigests() { return usesSdkLibrariesCertDigests; }
@@ -1419,6 +1460,15 @@
return usesStaticLibraries;
}
+ @NonNull
+ @Override
+ public String[] getUsesStaticLibrariesSorted() {
+ if (mUsesStaticLibrariesSorted == null) {
+ mUsesStaticLibrariesSorted = sortLibraries(usesStaticLibraries);
+ }
+ return mUsesStaticLibrariesSorted;
+ }
+
@Nullable
@Override
public String[][] getUsesStaticLibrariesCertDigests() {
@@ -2650,6 +2700,16 @@
return this;
}
+ private static String[] sortLibraries(List<String> libraryNames) {
+ int size = libraryNames.size();
+ if (size == 0) {
+ return EmptyArray.STRING;
+ }
+ var arr = libraryNames.toArray(EmptyArray.STRING);
+ Arrays.sort(arr);
+ return arr;
+ }
+
private void assignDerivedFields2() {
mBaseAppInfoFlags = PackageInfoUtils.appInfoFlags(this, null);
mBaseAppInfoPrivateFlags = PackageInfoUtils.appInfoPrivateFlags(this, null);
diff --git a/services/tests/PackageManagerServiceTests/unit/src/com/android/server/pm/test/parsing/parcelling/AndroidPackageTest.kt b/services/tests/PackageManagerServiceTests/unit/src/com/android/server/pm/test/parsing/parcelling/AndroidPackageTest.kt
index 1619856..f0e3f3f 100644
--- a/services/tests/PackageManagerServiceTests/unit/src/com/android/server/pm/test/parsing/parcelling/AndroidPackageTest.kt
+++ b/services/tests/PackageManagerServiceTests/unit/src/com/android/server/pm/test/parsing/parcelling/AndroidPackageTest.kt
@@ -89,6 +89,10 @@
"sortReceivers",
"sortServices",
"setAllComponentsDirectBootAware",
+ "getUsesLibrariesSorted",
+ "getUsesOptionalLibrariesSorted",
+ "getUsesSdkLibrariesSorted",
+ "getUsesStaticLibrariesSorted",
// Tested through setting minor/major manually
"setLongVersionCode",
"getLongVersionCode",