[res] Optimize idmap format for lookups
Idmap format is currently storing sorted mappings for the
overlays: be it target id -> overlay id, or target id ->
frro data, or the reverse overlay id -> target id list
All of these require binary search for finding the right entry,
and this binary search always touches just 4 bytes of the key,
skipping over all remaining bytes of value. This usually doesn't
make much of a difference for the smaller idmaps but in case of
the larger ones binary search has to load a whole bunch of
RAM into the CPU cache to then throw at least half of it away.
This CL rearranges all mappings into two separate lists: the
first one only contains the sorted keys, and the second one
stores the corresponding data in the same order. This means the
search can only touch the minimum amount of RAM and disk pages,
and then jump exactly to the value of the element it found.
We don't have any benchmarks that would _directly_ capture the
speedup here, and the Java resources_perf ones are too noisy to
make a clear call, but overall they look like some 3-5% speedup
for the overlaid lookups
Test: atest libanrdoidfw_tests idmap2_tests libandroidfw_benchmarks
Flag: EXEMPT performance optimization
Change-Id: I450797f233c9371e70738546a89feaa0e683b333
diff --git a/libs/androidfw/Idmap.cpp b/libs/androidfw/Idmap.cpp
index f066e46..3ecd82b 100644
--- a/libs/androidfw/Idmap.cpp
+++ b/libs/androidfw/Idmap.cpp
@@ -65,13 +65,7 @@
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 @@
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 @@
}
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;
- });
+ 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 == end_entry || dtohl(entry->overlay_id) != *resId) {
+ 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 @@
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 @@
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 @@
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;
- });
+ 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 (entry != end_entry && (0x00FFFFFFU & dtohl(entry->target_id)) == target_res_id) {
- uint32_t overlay_resource_id = dtohl(entry->overlay_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 @@
}
// 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;
- });
+ 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 != end_inline_entry &&
- (0x00FFFFFFU & dtohl(inline_entry->target_id)) == target_res_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 @@
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 @@
}
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 @@
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 @@
#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 @@
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 @@
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 @@
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 64b1f0c..e213fbd 100644
--- a/libs/androidfw/include/androidfw/Idmap.h
+++ b/libs/androidfw/include/androidfw/Idmap.h
@@ -40,6 +40,19 @@
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 @@
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 @@
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 @@
}
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 @@
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 @@
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 c264890..e330410 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 8e847e8..7e4b261 100644
--- a/libs/androidfw/tests/data/overlay/overlay.idmap
+++ b/libs/androidfw/tests/data/overlay/overlay.idmap
Binary files differ