idmap: optimize time to create idmap data

Change idmap to iterate over the resources in the overlay package
instead of the target package when scanning for resources defined in
both packages. This cuts down the runtime cost of creating an idmap
considerably since the algorithm now scales with the number of resources
in the overlay package (a handful) and not the number of resources in
the target package (android: 10k, SystemUI: 8k) at a minor cost to code
complexity.

Improvements on the runtime of ResTable::createIdmap (systrace on an
emulator running aosp_x86_64-eng):

  - target=android: 12.5 ms -> 3.0 ms
  - target=SystemUI: 8.6 ms -> 1.0 ms

The bulk of the cost of creating an idmap from installd is now the fork
and execl to call "idmap --fd ..." which weigh in at 16 ms.

Bug: 80150169
Test: make libandroidfw_tests
Test: atest OverlayHostTests OverlayDeviceTests
Change-Id: I98e18d5958c0cd835a73055b714f5bf0f4f95a09

4 files changed, 134 insertions, 124 deletions

diff --git a/libs/androidfw/AssetManager.cpp b/libs/androidfw/AssetManager.cpp
index 1cb0d25d8c08..365be10f597f 100644
--- a/libs/androidfw/AssetManager.cpp
+++ b/libs/androidfw/AssetManager.cpp
@@ -349,7 +349,7 @@ bool AssetManager::createIdmap(const char* targetApkPath, const char* overlayApk
                 goto exit;
             }
         }
-        ret = tables[0].createIdmap(tables[1], targetCrc, overlayCrc,
+        ret = tables[1].createIdmap(tables[0], targetCrc, overlayCrc,
                 targetApkPath, overlayApkPath, (void**)outData, outSize) == NO_ERROR;
     }
 
diff --git a/libs/androidfw/ResourceTypes.cpp b/libs/androidfw/ResourceTypes.cpp
index 76db18de6122..f7fb89e54ef3 100644
--- a/libs/androidfw/ResourceTypes.cpp
+++ b/libs/androidfw/ResourceTypes.cpp
@@ -26,7 +26,9 @@
 
 #include <algorithm>
 #include <limits>
+#include <map>
 #include <memory>
+#include <set>
 #include <type_traits>
 
 #include <android-base/macros.h>
@@ -7033,170 +7035,178 @@ status_t DynamicRefTable::lookupResourceValue(Res_value* value) const {
     return NO_ERROR;
 }
 
-struct IdmapTypeMap {
-    ssize_t overlayTypeId;
-    size_t entryOffset;
-    Vector<uint32_t> entryMap;
+struct IdmapMatchingResources {
+    void Add(uint32_t targetResId, uint32_t overlayResId) {
+        uint8_t targetTypeid = Res_GETTYPE(targetResId);
+        if (typeMappings.find(targetTypeid) == typeMappings.end()) {
+            typeMappings.emplace(targetTypeid, std::set<std::pair<uint32_t, uint32_t>>());
+        }
+        auto& entries = typeMappings[targetTypeid];
+        entries.insert(std::make_pair(targetResId, overlayResId));
+    }
+
+    void FixPadding() {
+        for (auto ti = typeMappings.cbegin(); ti != typeMappings.cend(); ++ti) {
+            uint32_t last_seen = 0xffffffff;
+            size_t total_entries = 0;
+            for (auto ei = ti->second.cbegin(); ei != ti->second.cend(); ++ei) {
+                assert(last_seen == 0xffffffff || last_seen < ei->first);
+                entryPadding[ei->first] = (last_seen == 0xffffffff) ? 0 : ei->first - last_seen - 1;
+                last_seen = ei->first;
+                total_entries += 1 + entryPadding[ei->first];
+            }
+            numberOfEntriesIncludingPadding[ti->first] = total_entries;
+        }
+    }
+
+    // resource type ID in context of target -> set of resource entries mapping target -> overlay
+    std::map<uint8_t, std::set<std::pair<uint32_t, uint32_t>>> typeMappings;
+
+    // resource ID in context of target -> trailing padding for that resource (call FixPadding
+    // before use)
+    std::map<uint32_t, size_t> entryPadding;
+
+    // resource type ID in context of target -> total number of entries, including padding entries,
+    // for that type (call FixPadding before use)
+    std::map<uint8_t, size_t> numberOfEntriesIncludingPadding;
 };
 
-status_t ResTable::createIdmap(const ResTable& overlay,
+status_t ResTable::createIdmap(const ResTable& targetResTable,
         uint32_t targetCrc, uint32_t overlayCrc,
         const char* targetPath, const char* overlayPath,
         void** outData, size_t* outSize) const
 {
-    // see README for details on the format of map
-    if (mPackageGroups.size() == 0) {
-        ALOGW("idmap: target package has no package groups, cannot create idmap\n");
+    if (targetPath == NULL || overlayPath == NULL || outData == NULL || outSize == NULL) {
+        ALOGE("idmap: unexpected NULL parameter");
         return UNKNOWN_ERROR;
     }
-
-    if (mPackageGroups[0]->packages.size() == 0) {
-        ALOGW("idmap: target package has no packages in its first package group, "
-                "cannot create idmap\n");
+    if (strlen(targetPath) > 255) {
+        ALOGE("idmap: target path exceeds idmap file format limit of 255 chars");
+        return UNKNOWN_ERROR;
+    }
+    if (strlen(overlayPath) > 255) {
+        ALOGE("idmap: overlay path exceeds idmap file format limit of 255 chars");
+        return UNKNOWN_ERROR;
+    }
+    if (mPackageGroups.size() == 0 || mPackageGroups[0]->packages.size() == 0) {
+        ALOGE("idmap: invalid overlay package");
+        return UNKNOWN_ERROR;
+    }
+    if (targetResTable.mPackageGroups.size() == 0 ||
+            targetResTable.mPackageGroups[0]->packages.size() == 0) {
+        ALOGE("idmap: invalid target package");
         return UNKNOWN_ERROR;
     }
 
-    // The number of resources overlaid that were not explicitly marked overlayable.
-    size_t forcedOverlayCount = 0u;
-
-    KeyedVector<uint8_t, IdmapTypeMap> map;
-
-    // overlaid packages are assumed to contain only one package group
-    const PackageGroup* pg = mPackageGroups[0];
-
-    // starting size is header
-    *outSize = ResTable::IDMAP_HEADER_SIZE_BYTES;
+    const ResTable_package* targetPackageStruct = targetResTable.mPackageGroups[0]->packages[0]->package;
+    const size_t tmpNameSize = arraysize(targetPackageStruct->name);
+    char16_t tmpName[tmpNameSize];
+    strcpy16_dtoh(tmpName, targetPackageStruct->name, tmpNameSize);
+    const String16 targetPackageName(tmpName);
 
-    // target package id and number of types in map
-    *outSize += 2 * sizeof(uint16_t);
+    const PackageGroup* packageGroup = mPackageGroups[0];
 
-    // overlay packages are assumed to contain only one package group
-    const ResTable_package* overlayPackageStruct = overlay.mPackageGroups[0]->packages[0]->package;
-    char16_t tmpName[sizeof(overlayPackageStruct->name)/sizeof(overlayPackageStruct->name[0])];
-    strcpy16_dtoh(tmpName, overlayPackageStruct->name, sizeof(overlayPackageStruct->name)/sizeof(overlayPackageStruct->name[0]));
-    const String16 overlayPackage(tmpName);
+    // the number of resources overlaid that were not explicitly marked overlayable
+    size_t forcedOverlayCount = 0u;
 
-    for (size_t typeIndex = 0; typeIndex < pg->types.size(); ++typeIndex) {
-        const TypeList& typeList = pg->types[typeIndex];
+    // find the resources that exist in both packages
+    IdmapMatchingResources matchingResources;
+    for (size_t typeIndex = 0; typeIndex < packageGroup->types.size(); ++typeIndex) {
+        const TypeList& typeList = packageGroup->types[typeIndex];
         if (typeList.isEmpty()) {
             continue;
         }
-
         const Type* typeConfigs = typeList[0];
 
-        IdmapTypeMap typeMap;
-        typeMap.overlayTypeId = -1;
-        typeMap.entryOffset = 0;
-
         for (size_t entryIndex = 0; entryIndex < typeConfigs->entryCount; ++entryIndex) {
-            uint32_t resID = Res_MAKEID(pg->id - 1, typeIndex, entryIndex);
-            resource_name resName;
-            if (!this->getResourceName(resID, false, &resName)) {
-                if (typeMap.entryMap.isEmpty()) {
-                    typeMap.entryOffset++;
-                }
+            uint32_t overlay_resid = Res_MAKEID(packageGroup->id - 1, typeIndex, entryIndex);
+            resource_name current_res;
+            if (!getResourceName(overlay_resid, false, &current_res)) {
                 continue;
             }
 
             uint32_t typeSpecFlags = 0u;
-            const String16 overlayType(resName.type, resName.typeLen);
-            const String16 overlayName(resName.name, resName.nameLen);
-            uint32_t overlayResID = overlay.identifierForName(overlayName.string(),
-                                                              overlayName.size(),
-                                                              overlayType.string(),
-                                                              overlayType.size(),
-                                                              overlayPackage.string(),
-                                                              overlayPackage.size(),
-                                                              &typeSpecFlags);
-            if (overlayResID == 0) {
-                // No such target resource was found.
-                if (typeMap.entryMap.isEmpty()) {
-                    typeMap.entryOffset++;
-                }
+            const uint32_t target_resid = targetResTable.identifierForName(
+                    current_res.name,
+                    current_res.nameLen,
+                    current_res.type,
+                    current_res.typeLen,
+                    targetPackageName.string(),
+                    targetPackageName.size(),
+                    &typeSpecFlags);
+
+            if (target_resid == 0) {
                 continue;
             }
 
-            // Now that we know this is being overlaid, check if it can be, and emit a warning if
-            // it can't.
             if ((dtohl(typeConfigs->typeSpecFlags[entryIndex]) &
                     ResTable_typeSpec::SPEC_OVERLAYABLE) == 0) {
-                forcedOverlayCount++;
-            }
-
-            if (typeMap.overlayTypeId == -1) {
-                typeMap.overlayTypeId = Res_GETTYPE(overlayResID) + 1;
-            }
-
-            if (Res_GETTYPE(overlayResID) + 1 != static_cast<size_t>(typeMap.overlayTypeId)) {
-                ALOGE("idmap: can't mix type ids in entry map. Resource 0x%08x maps to 0x%08x"
-                        " but entries should map to resources of type %02zx",
-                        resID, overlayResID, typeMap.overlayTypeId);
-                return BAD_TYPE;
-            }
-
-            if (typeMap.entryOffset + typeMap.entryMap.size() < entryIndex) {
-                // pad with 0xffffffff's (indicating non-existing entries) before adding this entry
-                size_t index = typeMap.entryMap.size();
-                size_t numItems = entryIndex - (typeMap.entryOffset + index);
-                if (typeMap.entryMap.insertAt(0xffffffff, index, numItems) < 0) {
-                    return NO_MEMORY;
-                }
+                ++forcedOverlayCount;
             }
-            typeMap.entryMap.add(Res_GETENTRY(overlayResID));
-        }
 
-        if (!typeMap.entryMap.isEmpty()) {
-            if (map.add(static_cast<uint8_t>(typeIndex), typeMap) < 0) {
-                return NO_MEMORY;
-            }
-            *outSize += (4 * sizeof(uint16_t)) + (typeMap.entryMap.size() * sizeof(uint32_t));
+            matchingResources.Add(target_resid, overlay_resid);
         }
     }
 
-    if (map.isEmpty()) {
-        ALOGW("idmap: no resources in overlay package present in base package");
+    if (matchingResources.typeMappings.empty()) {
+        ALOGE("idmap: no matching resources");
         return UNKNOWN_ERROR;
     }
 
+    matchingResources.FixPadding();
+
+    // write idmap
+    *outSize = ResTable::IDMAP_HEADER_SIZE_BYTES; // magic, version, target and overlay crc
+    *outSize += 2 * sizeof(uint16_t); // target package id, type count
+    const auto typesEnd = matchingResources.typeMappings.cend();
+    for (auto ti = matchingResources.typeMappings.cbegin(); ti != typesEnd; ++ti) {
+        *outSize += 4 * sizeof(uint16_t); // target type, overlay type, entry count, entry offset
+        *outSize += matchingResources.numberOfEntriesIncludingPadding[ti->first] *
+            sizeof(uint32_t); // entries
+    }
     if ((*outData = malloc(*outSize)) == NULL) {
         return NO_MEMORY;
     }
 
-    uint32_t* data = (uint32_t*)*outData;
-    *data++ = htodl(IDMAP_MAGIC);
-    *data++ = htodl(ResTable::IDMAP_CURRENT_VERSION);
-    *data++ = htodl(targetCrc);
-    *data++ = htodl(overlayCrc);
-    const char* paths[] = { targetPath, overlayPath };
-    for (int j = 0; j < 2; ++j) {
-        char* p = (char*)data;
-        const char* path = paths[j];
-        const size_t I = strlen(path);
-        if (I > 255) {
-            ALOGV("path exceeds expected 255 characters: %s\n", path);
-            return UNKNOWN_ERROR;
-        }
-        for (size_t i = 0; i < 256; ++i) {
-            *p++ = i < I ? path[i] : '\0';
-        }
-        data += 256 / sizeof(uint32_t);
+    // write idmap header
+    uint32_t* data = reinterpret_cast<uint32_t*>(*outData);
+    *data++ = htodl(IDMAP_MAGIC); // write: magic
+    *data++ = htodl(ResTable::IDMAP_CURRENT_VERSION); // write: version
+    *data++ = htodl(targetCrc); // write: target crc
+    *data++ = htodl(overlayCrc); // write: overlay crc
+
+    char* charData = reinterpret_cast<char*>(data);
+    size_t pathLen = strlen(targetPath);
+    for (size_t i = 0; i < 256; ++i) {
+        *charData++ = i < pathLen ? targetPath[i] : '\0'; // write: target path
     }
-    const size_t mapSize = map.size();
+    pathLen = strlen(overlayPath);
+    for (size_t i = 0; i < 256; ++i) {
+        *charData++ = i < pathLen ? overlayPath[i] : '\0'; // write: overlay path
+    }
+    data += (2 * 256) / sizeof(uint32_t);
+
+    // write idmap data header
     uint16_t* typeData = reinterpret_cast<uint16_t*>(data);
-    *typeData++ = htods(pg->id);
-    *typeData++ = htods(mapSize);
-    for (size_t i = 0; i < mapSize; ++i) {
-        uint8_t targetTypeId = map.keyAt(i);
-        const IdmapTypeMap& typeMap = map[i];
-        *typeData++ = htods(targetTypeId + 1);
-        *typeData++ = htods(typeMap.overlayTypeId);
-        *typeData++ = htods(typeMap.entryMap.size());
-        *typeData++ = htods(typeMap.entryOffset);
-
-        const size_t entryCount = typeMap.entryMap.size();
-        uint32_t* entries = reinterpret_cast<uint32_t*>(typeData);
-        for (size_t j = 0; j < entryCount; j++) {
-            entries[j] = htodl(typeMap.entryMap[j]);
+    *typeData++ = htods(targetPackageStruct->id); // write: target package id
+    *typeData++ =
+        htods(static_cast<uint16_t>(matchingResources.typeMappings.size())); // write: type count
+
+    // write idmap data
+    for (auto ti = matchingResources.typeMappings.cbegin(); ti != typesEnd; ++ti) {
+        const size_t entryCount = matchingResources.numberOfEntriesIncludingPadding[ti->first];
+        auto ei = ti->second.cbegin();
+        *typeData++ = htods(Res_GETTYPE(ei->first) + 1); // write: target type id
+        *typeData++ = htods(Res_GETTYPE(ei->second) + 1); // write: overlay type id
+        *typeData++ = htods(entryCount); // write: entry count
+        *typeData++ = htods(Res_GETENTRY(ei->first)); // write: (target) entry offset
+        uint32_t *entryData = reinterpret_cast<uint32_t*>(typeData);
+        for (; ei != ti->second.cend(); ++ei) {
+            const size_t padding = matchingResources.entryPadding[ei->first];
+            for (size_t i = 0; i < padding; ++i) {
+                *entryData++ = htodl(0xffffffff); // write: padding
+            }
+            *entryData++ = htodl(Res_GETENTRY(ei->second)); // write: (overlay) entry
         }
         typeData += entryCount * 2;
     }
diff --git a/libs/androidfw/include/androidfw/ResourceTypes.h b/libs/androidfw/include/androidfw/ResourceTypes.h
index 59abad45edbb..ad33fcfa2429 100644
--- a/libs/androidfw/include/androidfw/ResourceTypes.h
+++ b/libs/androidfw/include/androidfw/ResourceTypes.h
@@ -1990,7 +1990,7 @@ public:
     // Return value: on success: NO_ERROR; caller is responsible for free-ing
     // outData (using free(3)). On failure, any status_t value other than
     // NO_ERROR; the caller should not free outData.
-    status_t createIdmap(const ResTable& overlay,
+    status_t createIdmap(const ResTable& targetResTable,
             uint32_t targetCrc, uint32_t overlayCrc,
             const char* targetPath, const char* overlayPath,
             void** outData, size_t* outSize) const;
diff --git a/libs/androidfw/tests/Idmap_test.cpp b/libs/androidfw/tests/Idmap_test.cpp
index 26d28965d459..10b83a75304d 100644
--- a/libs/androidfw/tests/Idmap_test.cpp
+++ b/libs/androidfw/tests/Idmap_test.cpp
@@ -40,7 +40,7 @@ class IdmapTest : public ::testing::Test {
     ASSERT_EQ(NO_ERROR, overlay_table.add(overlay_data_.data(), overlay_data_.size()));
 
     char target_name[256] = "com.android.basic";
-    ASSERT_EQ(NO_ERROR, target_table_.createIdmap(overlay_table, 0, 0, target_name, target_name,
+    ASSERT_EQ(NO_ERROR, overlay_table.createIdmap(target_table_, 0, 0, target_name, target_name,
                                                   &data_, &data_size_));
   }