From d67e90e8a8301a87726420a1071fca8e52172bd4 Mon Sep 17 00:00:00 2001 From: Yurii Zubrytskyi Date: Fri, 30 Aug 2024 17:39:56 -0700 Subject: [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 --- libs/androidfw/Idmap.cpp | 153 +++++++++++++++++++++++++---------------------- 1 file changed, 80 insertions(+), 73 deletions(-) (limited to 'libs/androidfw/Idmap.cpp') 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 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 -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 ReadString(const uint8_t** in_out_data_ptr, size_t* in_out_size, - const std::string& label) { - const auto* len = ReadType(in_out_data_ptr, in_out_size, label + " length"); + const char* label) { + const auto* len = ReadType(in_out_data_ptr, in_out_size, label); if (len == nullptr) { return {}; } @@ -242,7 +238,7 @@ std::optional 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 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&& 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::Load(StringPiece idmap_path, StringPiece idmap_data) { ATRACE_CALL(); @@ -319,14 +315,21 @@ std::unique_ptr LoadedIdmap::Load(StringPiece idmap_path, StringPie if (data_header == nullptr) { return {}; } - auto target_entries = ReadType(&data_ptr, &data_size, "target", - dtohl(data_header->target_entry_count)); - if (target_entries == nullptr) { + Idmap_target_entries target_entries{ + .target_id = ReadType(&data_ptr, &data_size, "entries.target_id", + dtohl(data_header->target_entry_count)), + .overlay_id = ReadType(&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( - &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(&data_ptr, &data_size, "target inline.target_id", + dtohl(data_header->target_inline_entry_count)), + .entry = ReadType(&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::Load(StringPiece idmap_path, StringPie return {}; } - auto overlay_entries = ReadType(&data_ptr, &data_size, "target inline", - dtohl(data_header->overlay_entry_count)); - if (overlay_entries == nullptr) { + Idmap_overlay_entries overlay_entries{ + .overlay_id = ReadType(&data_ptr, &data_size, "overlay entries.overlay_id", + dtohl(data_header->overlay_entry_count)), + .target_id = ReadType(&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 string_pool = ReadString(&data_ptr, &data_size, "string pool"); -- cgit v1.2.3-59-g8ed1b