Merge "[res] Optimize idmap format for lookups" into main

4 files changed, 110 insertions, 96 deletions

diff --git a/libs/androidfw/Idmap.cpp b/libs/androidfw/Idmap.cpp
index f066e4620675..3ecd82b074a1 100644
--- a/libs/androidfw/Idmap.cpp
+++ b/libs/androidfw/Idmap.cpp
@@ -65,13 +65,7 @@ struct Idmap_data_header {
   uint32_t string_pool_index_offset;
 };
 
-struct Idmap_target_entry {
-  uint32_t target_id;
-  uint32_t overlay_id;
-};
-
 struct Idmap_target_entry_inline {
-  uint32_t target_id;
   uint32_t start_value_index;
   uint32_t value_count;
 };
@@ -81,10 +75,9 @@ struct Idmap_target_entry_inline_value {
   Res_value value;
 };
 
-struct Idmap_overlay_entry {
-  uint32_t overlay_id;
-  uint32_t target_id;
-};
+static constexpr uint32_t convert_dev_target_id(uint32_t dev_target_id) {
+  return (0x00FFFFFFU & dtohl(dev_target_id));
+}
 
 OverlayStringPool::OverlayStringPool(const LoadedIdmap* loaded_idmap)
     : data_header_(loaded_idmap->data_header_),
@@ -117,27 +110,29 @@ size_t OverlayStringPool::size() const {
 }
 
 OverlayDynamicRefTable::OverlayDynamicRefTable(const Idmap_data_header* data_header,
-                                               const Idmap_overlay_entry* entries,
+                                               Idmap_overlay_entries entries,
                                                uint8_t target_assigned_package_id)
     : data_header_(data_header),
       entries_(entries),
-      target_assigned_package_id_(target_assigned_package_id) {}
+      target_assigned_package_id_(target_assigned_package_id) {
+}
 
 status_t OverlayDynamicRefTable::lookupResourceId(uint32_t* resId) const {
-  const Idmap_overlay_entry* first_entry = entries_;
-  const Idmap_overlay_entry* end_entry = entries_ + dtohl(data_header_->overlay_entry_count);
-  auto entry = std::lower_bound(first_entry, end_entry, *resId,
-                                [](const Idmap_overlay_entry& e1, const uint32_t overlay_id) {
-    return dtohl(e1.overlay_id) < overlay_id;
-  });
-
-  if (entry == end_entry || dtohl(entry->overlay_id) != *resId) {
+  const auto count = dtohl(data_header_->overlay_entry_count);
+  const auto overlay_it_end = entries_.overlay_id + count;
+  const auto entry_it = std::lower_bound(entries_.overlay_id, overlay_it_end, *resId,
+                                         [](uint32_t dev_overlay_id, uint32_t overlay_id) {
+                                           return dtohl(dev_overlay_id) < overlay_id;
+                                         });
+
+  if (entry_it == overlay_it_end || dtohl(*entry_it) != *resId) {
     // A mapping for the target resource id could not be found.
     return DynamicRefTable::lookupResourceId(resId);
   }
 
-  *resId = (0x00FFFFFFU & dtohl(entry->target_id))
-      | (((uint32_t) target_assigned_package_id_) << 24U);
+  const auto index = entry_it - entries_.overlay_id;
+  *resId = convert_dev_target_id(entries_.target_id[index]) |
+           (((uint32_t)target_assigned_package_id_) << 24U);
   return NO_ERROR;
 }
 
@@ -145,12 +140,10 @@ status_t OverlayDynamicRefTable::lookupResourceIdNoRewrite(uint32_t* resId) cons
   return DynamicRefTable::lookupResourceId(resId);
 }
 
-IdmapResMap::IdmapResMap(const Idmap_data_header* data_header,
-                         const Idmap_target_entry* entries,
-                         const Idmap_target_entry_inline* inline_entries,
+IdmapResMap::IdmapResMap(const Idmap_data_header* data_header, Idmap_target_entries entries,
+                         Idmap_target_inline_entries inline_entries,
                          const Idmap_target_entry_inline_value* inline_entry_values,
-                         const ConfigDescription* configs,
-                         uint8_t target_assigned_package_id,
+                         const ConfigDescription* configs, uint8_t target_assigned_package_id,
                          const OverlayDynamicRefTable* overlay_ref_table)
     : data_header_(data_header),
       entries_(entries),
@@ -158,7 +151,8 @@ IdmapResMap::IdmapResMap(const Idmap_data_header* data_header,
       inline_entry_values_(inline_entry_values),
       configurations_(configs),
       target_assigned_package_id_(target_assigned_package_id),
-      overlay_ref_table_(overlay_ref_table) { }
+      overlay_ref_table_(overlay_ref_table) {
+}
 
 IdmapResMap::Result IdmapResMap::Lookup(uint32_t target_res_id) const {
   if ((target_res_id >> 24U) != target_assigned_package_id_) {
@@ -171,15 +165,15 @@ IdmapResMap::Result IdmapResMap::Lookup(uint32_t target_res_id) const {
   target_res_id &= 0x00FFFFFFU;
 
   // Check if the target resource is mapped to an overlay resource.
-  auto first_entry = entries_;
-  auto end_entry = entries_ + dtohl(data_header_->target_entry_count);
-  auto entry = std::lower_bound(first_entry, end_entry, target_res_id,
-                                [](const Idmap_target_entry& e, const uint32_t target_id) {
-    return (0x00FFFFFFU & dtohl(e.target_id)) < target_id;
-  });
-
-  if (entry != end_entry && (0x00FFFFFFU & dtohl(entry->target_id)) == target_res_id) {
-    uint32_t overlay_resource_id = dtohl(entry->overlay_id);
+  const auto target_end = entries_.target_id + dtohl(data_header_->target_entry_count);
+  auto target_it = std::lower_bound(entries_.target_id, target_end, target_res_id,
+                                    [](uint32_t dev_target_id, uint32_t target_id) {
+                                      return convert_dev_target_id(dev_target_id) < target_id;
+                                    });
+
+  if (target_it != target_end && convert_dev_target_id(*target_it) == target_res_id) {
+    const auto index = target_it - entries_.target_id;
+    uint32_t overlay_resource_id = dtohl(entries_.overlay_id[index]);
     // Lookup the resource without rewriting the overlay resource id back to the target resource id
     // being looked up.
     overlay_ref_table_->lookupResourceIdNoRewrite(&overlay_resource_id);
@@ -187,20 +181,22 @@ IdmapResMap::Result IdmapResMap::Lookup(uint32_t target_res_id) const {
   }
 
   // Check if the target resources is mapped to an inline table entry.
-  auto first_inline_entry = inline_entries_;
-  auto end_inline_entry = inline_entries_ + dtohl(data_header_->target_inline_entry_count);
-  auto inline_entry = std::lower_bound(first_inline_entry, end_inline_entry, target_res_id,
-                                       [](const Idmap_target_entry_inline& e,
-                                          const uint32_t target_id) {
-    return (0x00FFFFFFU & dtohl(e.target_id)) < target_id;
-  });
-
-  if (inline_entry != end_inline_entry &&
-      (0x00FFFFFFU & dtohl(inline_entry->target_id)) == target_res_id) {
+  const auto inline_entry_target_end =
+      inline_entries_.target_id + dtohl(data_header_->target_inline_entry_count);
+  const auto inline_entry_target_it =
+      std::lower_bound(inline_entries_.target_id, inline_entry_target_end, target_res_id,
+                       [](uint32_t dev_target_id, uint32_t target_id) {
+                         return convert_dev_target_id(dev_target_id) < target_id;
+                       });
+
+  if (inline_entry_target_it != inline_entry_target_end &&
+      convert_dev_target_id(*inline_entry_target_it) == target_res_id) {
+    const auto index = inline_entry_target_it - inline_entries_.target_id;
     std::map<ConfigDescription, Res_value> values_map;
-    for (int i = 0; i < inline_entry->value_count; i++) {
-      const auto& value = inline_entry_values_[inline_entry->start_value_index + i];
-      const auto& config = configurations_[value.config_index];
+    const auto& inline_entry = inline_entries_.entry[index];
+    for (int i = 0; i < dtohl(inline_entry.value_count); i++) {
+      const auto& value = inline_entry_values_[dtohl(inline_entry.start_value_index) + i];
+      const auto& config = configurations_[dtohl(value.config_index)];
       values_map[config] = value.value;
     }
     return Result(std::move(values_map));
@@ -210,15 +206,15 @@ IdmapResMap::Result IdmapResMap::Lookup(uint32_t target_res_id) const {
 
 namespace {
 template <typename T>
-const T* ReadType(const uint8_t** in_out_data_ptr, size_t* in_out_size, const std::string& label,
+const T* ReadType(const uint8_t** in_out_data_ptr, size_t* in_out_size, const char* label,
                   size_t count = 1) {
   if (!util::IsFourByteAligned(*in_out_data_ptr)) {
-    LOG(ERROR) << "Idmap " << label << " is not word aligned.";
+    LOG(ERROR) << "Idmap " << label << " in " << __func__ << " is not word aligned.";
     return {};
   }
   if ((*in_out_size / sizeof(T)) < count) {
-    LOG(ERROR) << "Idmap too small for the number of " << label << " entries ("
-               << count << ").";
+    LOG(ERROR) << "Idmap too small for the number of " << label << " in " << __func__
+               << " entries (" << count << ").";
     return nullptr;
   }
   auto data_ptr = *in_out_data_ptr;
@@ -229,8 +225,8 @@ const T* ReadType(const uint8_t** in_out_data_ptr, size_t* in_out_size, const st
 }
 
 std::optional<std::string_view> ReadString(const uint8_t** in_out_data_ptr, size_t* in_out_size,
-                                           const std::string& label) {
-  const auto* len = ReadType<uint32_t>(in_out_data_ptr, in_out_size, label + " length");
+                                           const char* label) {
+  const auto* len = ReadType<uint32_t>(in_out_data_ptr, in_out_size, label);
   if (len == nullptr) {
     return {};
   }
@@ -242,7 +238,7 @@ std::optional<std::string_view> ReadString(const uint8_t** in_out_data_ptr, size
   const uint32_t padding_size = (4U - ((size_t)*in_out_data_ptr & 0x3U)) % 4U;
   for (uint32_t i = 0; i < padding_size; i++) {
     if (**in_out_data_ptr != 0) {
-      LOG(ERROR) << " Idmap padding of " << label << " is non-zero.";
+      LOG(ERROR) << " Idmap padding of " << label << " in " << __func__ << " is non-zero.";
       return {};
     }
     *in_out_data_ptr += sizeof(uint8_t);
@@ -258,12 +254,10 @@ std::optional<std::string_view> ReadString(const uint8_t** in_out_data_ptr, size
 #endif
 
 LoadedIdmap::LoadedIdmap(const std::string& idmap_path, const Idmap_header* header,
-                         const Idmap_data_header* data_header,
-                         const Idmap_target_entry* target_entries,
-                         const Idmap_target_entry_inline* target_inline_entries,
+                         const Idmap_data_header* data_header, Idmap_target_entries target_entries,
+                         Idmap_target_inline_entries target_inline_entries,
                          const Idmap_target_entry_inline_value* inline_entry_values,
-                         const ConfigDescription* configs,
-                         const Idmap_overlay_entry* overlay_entries,
+                         const ConfigDescription* configs, Idmap_overlay_entries overlay_entries,
                          std::unique_ptr<ResStringPool>&& string_pool,
                          std::string_view overlay_apk_path, std::string_view target_apk_path)
     : header_(header),
@@ -274,10 +268,12 @@ LoadedIdmap::LoadedIdmap(const std::string& idmap_path, const Idmap_header* head
       configurations_(configs),
       overlay_entries_(overlay_entries),
       string_pool_(std::move(string_pool)),
-      idmap_fd_(android::base::utf8::open(idmap_path.c_str(), O_RDONLY|O_CLOEXEC|O_BINARY|O_PATH)),
+      idmap_fd_(
+          android::base::utf8::open(idmap_path.c_str(), O_RDONLY | O_CLOEXEC | O_BINARY | O_PATH)),
       overlay_apk_path_(overlay_apk_path),
       target_apk_path_(target_apk_path),
-      idmap_last_mod_time_(getFileModDate(idmap_fd_.get())) {}
+      idmap_last_mod_time_(getFileModDate(idmap_fd_.get())) {
+}
 
 std::unique_ptr<LoadedIdmap> LoadedIdmap::Load(StringPiece idmap_path, StringPiece idmap_data) {
   ATRACE_CALL();
@@ -319,14 +315,21 @@ std::unique_ptr<LoadedIdmap> LoadedIdmap::Load(StringPiece idmap_path, StringPie
   if (data_header == nullptr) {
     return {};
   }
-  auto target_entries = ReadType<Idmap_target_entry>(&data_ptr, &data_size, "target",
-                                                     dtohl(data_header->target_entry_count));
-  if (target_entries == nullptr) {
+  Idmap_target_entries target_entries{
+      .target_id = ReadType<uint32_t>(&data_ptr, &data_size, "entries.target_id",
+                                      dtohl(data_header->target_entry_count)),
+      .overlay_id = ReadType<uint32_t>(&data_ptr, &data_size, "entries.overlay_id",
+                                       dtohl(data_header->target_entry_count)),
+  };
+  if (!target_entries.target_id || !target_entries.overlay_id) {
     return {};
   }
-  auto target_inline_entries = ReadType<Idmap_target_entry_inline>(
-      &data_ptr, &data_size, "target inline", dtohl(data_header->target_inline_entry_count));
-  if (target_inline_entries == nullptr) {
+  Idmap_target_inline_entries target_inline_entries{
+      .target_id = ReadType<uint32_t>(&data_ptr, &data_size, "target inline.target_id",
+                                      dtohl(data_header->target_inline_entry_count)),
+      .entry = ReadType<Idmap_target_entry_inline>(&data_ptr, &data_size, "target inline.entry",
+                                                   dtohl(data_header->target_inline_entry_count))};
+  if (!target_inline_entries.target_id || !target_inline_entries.entry) {
     return {};
   }
 
@@ -344,9 +347,13 @@ std::unique_ptr<LoadedIdmap> LoadedIdmap::Load(StringPiece idmap_path, StringPie
     return {};
   }
 
-  auto overlay_entries = ReadType<Idmap_overlay_entry>(&data_ptr, &data_size, "target inline",
-                                                       dtohl(data_header->overlay_entry_count));
-  if (overlay_entries == nullptr) {
+  Idmap_overlay_entries overlay_entries{
+      .overlay_id = ReadType<uint32_t>(&data_ptr, &data_size, "overlay entries.overlay_id",
+                                       dtohl(data_header->overlay_entry_count)),
+      .target_id = ReadType<uint32_t>(&data_ptr, &data_size, "overlay entries.target_id",
+                                      dtohl(data_header->overlay_entry_count)),
+  };
+  if (!overlay_entries.overlay_id || !overlay_entries.target_id) {
     return {};
   }
   std::optional<std::string_view> string_pool = ReadString(&data_ptr, &data_size, "string pool");
diff --git a/libs/androidfw/include/androidfw/Idmap.h b/libs/androidfw/include/androidfw/Idmap.h
index 64b1f0c6ed03..e213fbd22ab0 100644
--- a/libs/androidfw/include/androidfw/Idmap.h
+++ b/libs/androidfw/include/androidfw/Idmap.h
@@ -40,6 +40,19 @@ struct Idmap_target_entry_inline;
 struct Idmap_target_entry_inline_value;
 struct Idmap_overlay_entry;
 
+struct Idmap_target_entries {
+  const uint32_t* target_id = nullptr;
+  const uint32_t* overlay_id = nullptr;
+};
+struct Idmap_target_inline_entries {
+  const uint32_t* target_id = nullptr;
+  const Idmap_target_entry_inline* entry = nullptr;
+};
+struct Idmap_overlay_entries {
+  const uint32_t* overlay_id = nullptr;
+  const uint32_t* target_id = nullptr;
+};
+
 // A string pool for overlay apk assets. The string pool holds the strings of the overlay resources
 // table and additionally allows for loading strings from the idmap string pool. The idmap string
 // pool strings are offset after the end of the overlay resource table string pool entries so
@@ -67,7 +80,7 @@ class OverlayDynamicRefTable : public DynamicRefTable {
 
  private:
   explicit OverlayDynamicRefTable(const Idmap_data_header* data_header,
-                                  const Idmap_overlay_entry* entries,
+                                  Idmap_overlay_entries entries,
                                   uint8_t target_assigned_package_id);
 
   // Rewrites a compile-time overlay resource id to the runtime resource id of corresponding target
@@ -75,8 +88,8 @@ class OverlayDynamicRefTable : public DynamicRefTable {
   status_t lookupResourceIdNoRewrite(uint32_t* resId) const;
 
   const Idmap_data_header* data_header_;
-  const Idmap_overlay_entry* entries_;
-  const int8_t target_assigned_package_id_;
+  Idmap_overlay_entries entries_;
+  uint8_t target_assigned_package_id_;
 
   friend LoadedIdmap;
   friend IdmapResMap;
@@ -131,17 +144,15 @@ class IdmapResMap {
   }
 
  private:
-  explicit IdmapResMap(const Idmap_data_header* data_header,
-                       const Idmap_target_entry* entries,
-                       const Idmap_target_entry_inline* inline_entries,
+  explicit IdmapResMap(const Idmap_data_header* data_header, Idmap_target_entries entries,
+                       Idmap_target_inline_entries inline_entries,
                        const Idmap_target_entry_inline_value* inline_entry_values,
-                       const ConfigDescription* configs,
-                       uint8_t target_assigned_package_id,
+                       const ConfigDescription* configs, uint8_t target_assigned_package_id,
                        const OverlayDynamicRefTable* overlay_ref_table);
 
   const Idmap_data_header* data_header_;
-  const Idmap_target_entry* entries_;
-  const Idmap_target_entry_inline* inline_entries_;
+  Idmap_target_entries entries_;
+  Idmap_target_inline_entries inline_entries_;
   const Idmap_target_entry_inline_value* inline_entry_values_;
   const ConfigDescription* configurations_;
   const uint8_t target_assigned_package_id_;
@@ -192,11 +203,11 @@ class LoadedIdmap {
 
   const Idmap_header* header_;
   const Idmap_data_header* data_header_;
-  const Idmap_target_entry* target_entries_;
-  const Idmap_target_entry_inline* target_inline_entries_;
+  Idmap_target_entries target_entries_;
+  Idmap_target_inline_entries target_inline_entries_;
   const Idmap_target_entry_inline_value* inline_entry_values_;
   const ConfigDescription* configurations_;
-  const Idmap_overlay_entry* overlay_entries_;
+  const Idmap_overlay_entries overlay_entries_;
   const std::unique_ptr<ResStringPool> string_pool_;
 
   android::base::unique_fd idmap_fd_;
@@ -207,17 +218,13 @@ class LoadedIdmap {
  private:
   DISALLOW_COPY_AND_ASSIGN(LoadedIdmap);
 
-  explicit LoadedIdmap(const std::string& idmap_path,
-                       const Idmap_header* header,
-                       const Idmap_data_header* data_header,
-                       const Idmap_target_entry* target_entries,
-                       const Idmap_target_entry_inline* target_inline_entries,
+  explicit LoadedIdmap(const std::string& idmap_path, const Idmap_header* header,
+                       const Idmap_data_header* data_header, Idmap_target_entries target_entries,
+                       Idmap_target_inline_entries target_inline_entries,
                        const Idmap_target_entry_inline_value* inline_entry_values_,
-                       const ConfigDescription* configs,
-                       const Idmap_overlay_entry* overlay_entries,
+                       const ConfigDescription* configs, Idmap_overlay_entries overlay_entries,
                        std::unique_ptr<ResStringPool>&& string_pool,
-                       std::string_view overlay_apk_path,
-                       std::string_view target_apk_path);
+                       std::string_view overlay_apk_path, std::string_view target_apk_path);
 
   friend OverlayStringPool;
 };
diff --git a/libs/androidfw/include/androidfw/ResourceTypes.h b/libs/androidfw/include/androidfw/ResourceTypes.h
index c2648909386c..e330410ed1a0 100644
--- a/libs/androidfw/include/androidfw/ResourceTypes.h
+++ b/libs/androidfw/include/androidfw/ResourceTypes.h
@@ -48,7 +48,7 @@
 namespace android {
 
 constexpr const uint32_t kIdmapMagic = 0x504D4449u;
-constexpr const uint32_t kIdmapCurrentVersion = 0x00000009u;
+constexpr const uint32_t kIdmapCurrentVersion = 0x0000000Au;
 
 // This must never change.
 constexpr const uint32_t kFabricatedOverlayMagic = 0x4f525246; // FRRO (big endian)
diff --git a/libs/androidfw/tests/data/overlay/overlay.idmap b/libs/androidfw/tests/data/overlay/overlay.idmap
index 8e847e81aa31..7e4b261cf109 100644
--- a/libs/androidfw/tests/data/overlay/overlay.idmap
+++ b/libs/androidfw/tests/data/overlay/overlay.idmap