diff options
| -rw-r--r-- | services/core/java/com/android/server/integrity/parser/RuleIndexingController.java | 33 | ||||
| -rw-r--r-- | services/tests/servicestests/src/com/android/server/integrity/IntegrityFileManagerTest.java | 8 |
2 files changed, 27 insertions, 14 deletions
diff --git a/services/core/java/com/android/server/integrity/parser/RuleIndexingController.java b/services/core/java/com/android/server/integrity/parser/RuleIndexingController.java index 03392abf478f..87eee4ea7be4 100644 --- a/services/core/java/com/android/server/integrity/parser/RuleIndexingController.java +++ b/services/core/java/com/android/server/integrity/parser/RuleIndexingController.java @@ -28,9 +28,9 @@ import com.android.server.integrity.model.BitInputStream; import java.io.IOException; import java.io.InputStream; import java.util.ArrayList; +import java.util.Arrays; import java.util.LinkedHashMap; import java.util.List; -import java.util.TreeSet; import java.util.stream.Collectors; /** Helper class to identify the necessary indexes that needs to be read. */ @@ -93,19 +93,28 @@ public class RuleIndexingController { return keyToIndexMap; } - private RuleIndexRange searchIndexingKeysRangeContainingKey( + private static RuleIndexRange searchIndexingKeysRangeContainingKey( LinkedHashMap<String, Integer> indexMap, String searchedKey) { - TreeSet<String> keyTreeSet = - indexMap.keySet().stream() - .filter(key -> !key.matches(START_INDEXING_KEY) && !key.matches( - END_INDEXING_KEY)) - .collect(Collectors.toCollection(TreeSet::new)); + List<String> keys = indexMap.keySet().stream().collect(Collectors.toList()); + List<String> identifiedKeyRange = + searchKeysRangeContainingKey(keys, searchedKey, 0, keys.size() - 1); + return new RuleIndexRange( + indexMap.get(identifiedKeyRange.get(0)), indexMap.get(identifiedKeyRange.get(1))); + } + + private static List<String> searchKeysRangeContainingKey( + List<String> sortedKeyList, String key, int startIndex, int endIndex) { + if (endIndex - startIndex == 1) { + return Arrays.asList(sortedKeyList.get(startIndex), sortedKeyList.get(endIndex)); + } - String minIndex = keyTreeSet.floor(searchedKey); - String maxIndex = keyTreeSet.higher(searchedKey); + int midKeyIndex = startIndex + ((endIndex - startIndex) / 2); + String midKey = sortedKeyList.get(midKeyIndex); - return new RuleIndexRange( - indexMap.get(minIndex == null ? START_INDEXING_KEY : minIndex), - indexMap.get(maxIndex == null ? END_INDEXING_KEY : maxIndex)); + if (key.compareTo(midKey) >= 0) { + return searchKeysRangeContainingKey(sortedKeyList, key, midKeyIndex, endIndex); + } else { + return searchKeysRangeContainingKey(sortedKeyList, key, startIndex, midKeyIndex); + } } } diff --git a/services/tests/servicestests/src/com/android/server/integrity/IntegrityFileManagerTest.java b/services/tests/servicestests/src/com/android/server/integrity/IntegrityFileManagerTest.java index 47c7e56febe0..a1810b971b09 100644 --- a/services/tests/servicestests/src/com/android/server/integrity/IntegrityFileManagerTest.java +++ b/services/tests/servicestests/src/com/android/server/integrity/IntegrityFileManagerTest.java @@ -16,6 +16,8 @@ package com.android.server.integrity; +import static com.android.server.integrity.model.IndexingFileConstants.INDEXING_BLOCK_SIZE; + import static com.google.common.truth.Truth.assertThat; import android.content.integrity.AppInstallMetadata; @@ -159,13 +161,14 @@ public class IntegrityFileManagerTest { // Create a rule set with 2500 package name indexed, 2500 app certificate indexed and // 500 unindexed rules. List<Rule> rules = new ArrayList<>(); + int unindexedRuleCount = 70; for (int i = 0; i < 2500; i++) { rules.add(getPackageNameIndexedRule(String.format("%s%04d", packageName, i))); rules.add(getAppCertificateIndexedRule(String.format("%s%04d", appCertificate, i))); } - for (int i = 0; i < 70; i++) { + for (int i = 0; i < unindexedRuleCount; i++) { rules.add(getInstallerCertificateRule(String.format("%s%04d", installerName, i))); } @@ -187,7 +190,8 @@ public class IntegrityFileManagerTest { List<Rule> rulesFetched = mIntegrityFileManager.readRules(appInstallMetadata); // Verify that we do not load all the rules and we have the necessary rules to evaluate. - assertThat(rulesFetched.size()).isEqualTo(270); + assertThat(rulesFetched.size()) + .isEqualTo(INDEXING_BLOCK_SIZE * 2 + unindexedRuleCount); assertThat(rulesFetched) .containsAllOf( getPackageNameIndexedRule(installedPackageName), |