[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");