[res] Optimize name lookups in idmap service

The most common operation when build idmaps is to find the
resource ID by name. This is the least optimized operation
in the current resources data structures, as they only
expect ID -> value lookups

This change adds an optional flag that creates a name->ID
hash map inside ResStringPool, and use it when loading
APKs in idmap2d

Bug: 282215580
Test: build + boot + perf record

Change-Id: I82f4d684cb48e2dcddcd677b882b11497c1c13b1

5 files changed, 94 insertions, 41 deletions

diff --git a/cmds/idmap2/libidmap2/ResourceContainer.cpp b/cmds/idmap2/libidmap2/ResourceContainer.cpp
index 9025b5bd2e6f..3c0e118bbfe7 100644
--- a/cmds/idmap2/libidmap2/ResourceContainer.cpp
+++ b/cmds/idmap2/libidmap2/ResourceContainer.cpp
@@ -268,10 +268,11 @@ struct ResState {
   std::unique_ptr<AssetManager2> am;
   ZipAssetsProvider* zip_assets;
 
-  static Result<ResState> Initialize(std::unique_ptr<ZipAssetsProvider> zip) {
+  static Result<ResState> Initialize(std::unique_ptr<ZipAssetsProvider> zip,
+                                     package_property_t flags) {
     ResState state;
     state.zip_assets = zip.get();
-    if ((state.apk_assets = ApkAssets::Load(std::move(zip))) == nullptr) {
+    if ((state.apk_assets = ApkAssets::Load(std::move(zip), flags)) == nullptr) {
       return Error("failed to load apk asset");
     }
 
@@ -284,7 +285,7 @@ struct ResState {
     }
 
     state.am = std::make_unique<AssetManager2>();
-    if (!state.am->SetApkAssets({state.apk_assets})) {
+    if (!state.am->SetApkAssets({state.apk_assets}, false)) {
       return Error("failed to create asset manager");
     }
 
@@ -343,8 +344,8 @@ Result<const ResState*> ApkResourceContainer::GetState() const {
     return state;
   }
 
-  auto state =
-      ResState::Initialize(std::move(std::get<std::unique_ptr<ZipAssetsProvider>>(state_)));
+  auto state = ResState::Initialize(std::move(std::get<std::unique_ptr<ZipAssetsProvider>>(state_)),
+                                    PROPERTY_OPTIMIZE_NAME_LOOKUPS);
   if (!state) {
     return state.GetError();
   }
diff --git a/libs/androidfw/LoadedArsc.cpp b/libs/androidfw/LoadedArsc.cpp
index 02707e0e0c73..d9166a16cdea 100644
--- a/libs/androidfw/LoadedArsc.cpp
+++ b/libs/androidfw/LoadedArsc.cpp
@@ -454,7 +454,8 @@ const LoadedPackage* LoadedArsc::GetPackageById(uint8_t package_id) const {
 std::unique_ptr<const LoadedPackage> LoadedPackage::Load(const Chunk& chunk,
                                                          package_property_t property_flags) {
   ATRACE_NAME("LoadedPackage::Load");
-  std::unique_ptr<LoadedPackage> loaded_package(new LoadedPackage());
+  const bool optimize_name_lookups = (property_flags & PROPERTY_OPTIMIZE_NAME_LOOKUPS) != 0;
+  std::unique_ptr<LoadedPackage> loaded_package(new LoadedPackage(optimize_name_lookups));
 
   // typeIdOffset was added at some point, but we still must recognize apps built before this
   // was added.
diff --git a/libs/androidfw/ResourceTypes.cpp b/libs/androidfw/ResourceTypes.cpp
index 4c992becda7c..2c99f1aa3675 100644
--- a/libs/androidfw/ResourceTypes.cpp
+++ b/libs/androidfw/ResourceTypes.cpp
@@ -447,15 +447,19 @@ Res_png_9patch* Res_png_9patch::deserialize(void* inData)
 // --------------------------------------------------------------------
 // --------------------------------------------------------------------
 
-ResStringPool::ResStringPool()
-    : mError(NO_INIT), mOwnedData(NULL), mHeader(NULL), mCache(NULL)
-{
+ResStringPool::ResStringPool() : mError(NO_INIT), mOwnedData(NULL), mHeader(NULL), mCache(NULL) {
 }
 
-ResStringPool::ResStringPool(const void* data, size_t size, bool copyData)
-    : mError(NO_INIT), mOwnedData(NULL), mHeader(NULL), mCache(NULL)
-{
-    setTo(data, size, copyData);
+ResStringPool::ResStringPool(bool optimize_name_lookups) : ResStringPool() {
+  if (optimize_name_lookups) {
+    mIndexLookupCache.emplace();
+  }
+}
+
+ResStringPool::ResStringPool(const void* data, size_t size, bool copyData,
+                             bool optimize_name_lookups)
+    : ResStringPool(optimize_name_lookups) {
+  setTo(data, size, copyData);
 }
 
 ResStringPool::~ResStringPool()
@@ -683,6 +687,14 @@ status_t ResStringPool::setTo(incfs::map_ptr<void> data, size_t size, bool copyD
         mStylePoolSize = 0;
     }
 
+    if (mIndexLookupCache) {
+      if ((mHeader->flags & ResStringPool_header::UTF8_FLAG) != 0) {
+        mIndexLookupCache->first.reserve(mHeader->stringCount);
+      } else {
+        mIndexLookupCache->second.reserve(mHeader->stringCount);
+      }
+    }
+
     return (mError=NO_ERROR);
 }
 
@@ -708,6 +720,10 @@ void ResStringPool::uninit()
         free(mOwnedData);
         mOwnedData = NULL;
     }
+    if (mIndexLookupCache) {
+      mIndexLookupCache->first.clear();
+      mIndexLookupCache->second.clear();
+    }
 }
 
 /**
@@ -824,11 +840,11 @@ base::expected<StringPiece16, NullOrIOError> ResStringPool::stringAt(size_t idx)
 
                 // encLen must be less than 0x7FFF due to encoding.
                 if ((uint32_t)(u8str+*u8len-strings) < mStringPoolSize) {
-                    AutoMutex lock(mDecodeLock);
+                  AutoMutex lock(mCachesLock);
 
-                    if (mCache != NULL && mCache[idx] != NULL) {
-                        return StringPiece16(mCache[idx], *u16len);
-                    }
+                  if (mCache != NULL && mCache[idx] != NULL) {
+                    return StringPiece16(mCache[idx], *u16len);
+                  }
 
                     // Retrieve the actual length of the utf8 string if the
                     // encoded length was truncated
@@ -1093,12 +1109,24 @@ base::expected<size_t, NullOrIOError> ResStringPool::indexOfString(const char16_
             // block, start searching at the back.
             String8 str8(str, strLen);
             const size_t str8Len = str8.size();
+            std::optional<AutoMutex> cacheLock;
+            if (mIndexLookupCache) {
+              cacheLock.emplace(mCachesLock);
+              if (auto it = mIndexLookupCache->first.find(std::string_view(str8));
+                  it != mIndexLookupCache->first.end()) {
+                return it->second;
+              }
+            }
+
             for (int i=mHeader->stringCount-1; i>=0; i--) {
                 const base::expected<StringPiece, NullOrIOError> s = string8At(i);
                 if (UNLIKELY(IsIOError(s))) {
                     return base::unexpected(s.error());
                 }
                 if (s.has_value()) {
+                  if (mIndexLookupCache) {
+                    mIndexLookupCache->first.insert({*s, i});
+                  }
                     if (kDebugStringPoolNoisy) {
                         ALOGI("Looking at %s, i=%d\n", s->data(), i);
                     }
@@ -1151,20 +1179,32 @@ base::expected<size_t, NullOrIOError> ResStringPool::indexOfString(const char16_
             // most often this happens because we want to get IDs for style
             // span tags; since those always appear at the end of the string
             // block, start searching at the back.
+            std::optional<AutoMutex> cacheLock;
+            if (mIndexLookupCache) {
+              cacheLock.emplace(mCachesLock);
+              if (auto it = mIndexLookupCache->second.find({str, strLen});
+                  it != mIndexLookupCache->second.end()) {
+                return it->second;
+              }
+            }
             for (int i=mHeader->stringCount-1; i>=0; i--) {
                 const base::expected<StringPiece16, NullOrIOError> s = stringAt(i);
                 if (UNLIKELY(IsIOError(s))) {
                     return base::unexpected(s.error());
                 }
                 if (kDebugStringPoolNoisy) {
-                    ALOGI("Looking at %s, i=%d\n", String8(s->data(), s->size()).c_str(), i);
+                  ALOGI("Looking16 at %s, i=%d\n", String8(s->data(), s->size()).c_str(), i);
                 }
-                if (s.has_value() && strLen == s->size() &&
-                        strzcmp16(s->data(), s->size(), str, strLen) == 0) {
+                if (s.has_value()) {
+                  if (mIndexLookupCache) {
+                    mIndexLookupCache->second.insert({*s, i});
+                  }
+                  if (strLen == s->size() && strzcmp16(s->data(), s->size(), str, strLen) == 0) {
                     if (kDebugStringPoolNoisy) {
-                        ALOGI("MATCH!");
+                      ALOGI("MATCH16!");
                     }
                     return i;
+                  }
                 }
             }
         }
diff --git a/libs/androidfw/include/androidfw/LoadedArsc.h b/libs/androidfw/include/androidfw/LoadedArsc.h
index 3a7287187781..413b27829474 100644
--- a/libs/androidfw/include/androidfw/LoadedArsc.h
+++ b/libs/androidfw/include/androidfw/LoadedArsc.h
@@ -99,6 +99,9 @@ enum : package_property_t {
 
   // The apk assets only contain the overlayable declarations information.
   PROPERTY_ONLY_OVERLAYABLES = 1U << 5U,
+
+  // Optimize the resource lookups by name via an in-memory lookup table.
+  PROPERTY_OPTIMIZE_NAME_LOOKUPS = 1U << 6U,
 };
 
 struct OverlayableInfo {
@@ -285,7 +288,9 @@ class LoadedPackage {
  private:
   DISALLOW_COPY_AND_ASSIGN(LoadedPackage);
 
-  LoadedPackage() = default;
+  explicit LoadedPackage(bool optimize_name_lookups = false)
+      : type_string_pool_(optimize_name_lookups), key_string_pool_(optimize_name_lookups) {
+  }
 
   ResStringPool type_string_pool_;
   ResStringPool key_string_pool_;
diff --git a/libs/androidfw/include/androidfw/ResourceTypes.h b/libs/androidfw/include/androidfw/ResourceTypes.h
index 44ab14a8a7ac..3d1403d0e039 100644
--- a/libs/androidfw/include/androidfw/ResourceTypes.h
+++ b/libs/androidfw/include/androidfw/ResourceTypes.h
@@ -22,27 +22,28 @@
 
 #include <android-base/expected.h>
 #include <android-base/unique_fd.h>
-
+#include <android/configuration.h>
 #include <androidfw/Asset.h>
 #include <androidfw/Errors.h>
 #include <androidfw/LocaleData.h>
 #include <androidfw/StringPiece.h>
 #include <utils/ByteOrder.h>
 #include <utils/Errors.h>
+#include <utils/KeyedVector.h>
 #include <utils/String16.h>
 #include <utils/Vector.h>
-#include <utils/KeyedVector.h>
-
 #include <utils/threads.h>
 
 #include <stdint.h>
 #include <sys/types.h>
 
-#include <android/configuration.h>
-
 #include <array>
 #include <map>
 #include <memory>
+#include <optional>
+#include <string_view>
+#include <unordered_map>
+#include <utility>
 
 namespace android {
 
@@ -512,23 +513,24 @@ struct ResStringPool_span
 class ResStringPool
 {
 public:
-    ResStringPool();
-    ResStringPool(const void* data, size_t size, bool copyData=false);
-    virtual ~ResStringPool();
+ ResStringPool();
+ explicit ResStringPool(bool optimize_name_lookups);
+ ResStringPool(const void* data, size_t size, bool copyData = false,
+               bool optimize_name_lookups = false);
+ virtual ~ResStringPool();
 
-    void setToEmpty();
-    status_t setTo(incfs::map_ptr<void> data, size_t size, bool copyData=false);
+ void setToEmpty();
+ status_t setTo(incfs::map_ptr<void> data, size_t size, bool copyData = false);
 
-    status_t getError() const;
+ status_t getError() const;
 
-    void uninit();
+ void uninit();
 
-    // Return string entry as UTF16; if the pool is UTF8, the string will
-    // be converted before returning.
-    inline base::expected<StringPiece16, NullOrIOError> stringAt(
-            const ResStringPool_ref& ref) const {
-        return stringAt(ref.index);
-    }
+ // Return string entry as UTF16; if the pool is UTF8, the string will
+ // be converted before returning.
+ inline base::expected<StringPiece16, NullOrIOError> stringAt(const ResStringPool_ref& ref) const {
+   return stringAt(ref.index);
+ }
     virtual base::expected<StringPiece16, NullOrIOError> stringAt(size_t idx) const;
 
     // Note: returns null if the string pool is not UTF8.
@@ -557,7 +559,7 @@ private:
     void*                                         mOwnedData;
     incfs::verified_map_ptr<ResStringPool_header> mHeader;
     size_t                                        mSize;
-    mutable Mutex                                 mDecodeLock;
+    mutable Mutex                                 mCachesLock;
     incfs::map_ptr<uint32_t>                      mEntries;
     incfs::map_ptr<uint32_t>                      mEntryStyles;
     incfs::map_ptr<void>                          mStrings;
@@ -566,6 +568,10 @@ private:
     incfs::map_ptr<uint32_t>                      mStyles;
     uint32_t                                      mStylePoolSize;    // number of uint32_t
 
+    mutable std::optional<std::pair<std::unordered_map<std::string_view, int>,
+                                    std::unordered_map<std::u16string_view, int>>>
+        mIndexLookupCache;
+
     base::expected<StringPiece, NullOrIOError> stringDecodeAt(
         size_t idx, incfs::map_ptr<uint8_t> str, size_t encLen) const;
 };