am 08d9d9a4: Merge "Runtime resource overlay, iteration 1."

* commit '08d9d9a46250c4fad66e9b637e8898a3524c4286':
  Runtime resource overlay, iteration 1.

3 files changed, 860 insertions, 56 deletions

diff --git a/libs/utils/AssetManager.cpp b/libs/utils/AssetManager.cpp
index e09e755..13004cd 100644
--- a/libs/utils/AssetManager.cpp
+++ b/libs/utils/AssetManager.cpp
@@ -36,6 +36,19 @@
 #include <dirent.h>
 #include <errno.h>
 #include <assert.h>
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+#ifndef TEMP_FAILURE_RETRY
+/* Used to retry syscalls that can return EINTR. */
+#define TEMP_FAILURE_RETRY(exp) ({         \
+    typeof (exp) _rc;                      \
+    do {                                   \
+        _rc = (exp);                       \
+    } while (_rc == -1 && errno == EINTR); \
+    _rc; })
+#endif
 
 using namespace android;
 
@@ -48,6 +61,7 @@ static const char* kDefaultVendor = "default";
 static const char* kAssetsRoot = "assets";
 static const char* kAppZipName = NULL; //"classes.jar";
 static const char* kSystemAssets = "framework/framework-res.apk";
+static const char* kIdmapCacheDir = "resource-cache";
 
 static const char* kExcludeExtension = ".EXCLUDE";
 
@@ -55,6 +69,35 @@ static Asset* const kExcludedAsset = (Asset*) 0xd000000d;
 
 static volatile int32_t gCount = 0;
 
+namespace {
+    // Transform string /a/b/c.apk to /data/resource-cache/a@b@c.apk@idmap
+    String8 idmapPathForPackagePath(const String8& pkgPath)
+    {
+        const char* root = getenv("ANDROID_DATA");
+        LOG_ALWAYS_FATAL_IF(root == NULL, "ANDROID_DATA not set");
+        String8 path(root);
+        path.appendPath(kIdmapCacheDir);
+
+        char buf[256]; // 256 chars should be enough for anyone...
+        strncpy(buf, pkgPath.string(), 255);
+        buf[255] = '\0';
+        char* filename = buf;
+        while (*filename && *filename == '/') {
+            ++filename;
+        }
+        char* p = filename;
+        while (*p) {
+            if (*p == '/') {
+                *p = '@';
+            }
+            ++p;
+        }
+        path.appendPath(filename);
+        path.append("@idmap");
+
+        return path;
+    }
+}
 
 /*
  * ===========================================================================
@@ -122,7 +165,7 @@ bool AssetManager::addAssetPath(const String8& path, void** cookie)
             return true;
         }
     }
-    
+
     LOGV("In %p Asset %s path: %s", this,
          ap.type == kFileTypeDirectory ? "dir" : "zip", ap.path.string());
 
@@ -133,9 +176,181 @@ bool AssetManager::addAssetPath(const String8& path, void** cookie)
         *cookie = (void*)mAssetPaths.size();
     }
 
+    // add overlay packages for /system/framework; apps are handled by the
+    // (Java) package manager
+    if (strncmp(path.string(), "/system/framework/", 18) == 0) {
+        // When there is an environment variable for /vendor, this
+        // should be changed to something similar to how ANDROID_ROOT
+        // and ANDROID_DATA are used in this file.
+        String8 overlayPath("/vendor/overlay/framework/");
+        overlayPath.append(path.getPathLeaf());
+        if (TEMP_FAILURE_RETRY(access(overlayPath.string(), R_OK)) == 0) {
+            asset_path oap;
+            oap.path = overlayPath;
+            oap.type = ::getFileType(overlayPath.string());
+            bool addOverlay = (oap.type == kFileTypeRegular); // only .apks supported as overlay
+            if (addOverlay) {
+                oap.idmap = idmapPathForPackagePath(overlayPath);
+
+                if (isIdmapStaleLocked(ap.path, oap.path, oap.idmap)) {
+                    addOverlay = createIdmapFileLocked(ap.path, oap.path, oap.idmap);
+                }
+            }
+            if (addOverlay) {
+                mAssetPaths.add(oap);
+            } else {
+                LOGW("failed to add overlay package %s\n", overlayPath.string());
+            }
+        }
+    }
+
+    return true;
+}
+
+bool AssetManager::isIdmapStaleLocked(const String8& originalPath, const String8& overlayPath,
+                                      const String8& idmapPath)
+{
+    struct stat st;
+    if (TEMP_FAILURE_RETRY(stat(idmapPath.string(), &st)) == -1) {
+        if (errno == ENOENT) {
+            return true; // non-existing idmap is always stale
+        } else {
+            LOGW("failed to stat file %s: %s\n", idmapPath.string(), strerror(errno));
+            return false;
+        }
+    }
+    if (st.st_size < ResTable::IDMAP_HEADER_SIZE_BYTES) {
+        LOGW("file %s has unexpectedly small size=%zd\n", idmapPath.string(), (size_t)st.st_size);
+        return false;
+    }
+    int fd = TEMP_FAILURE_RETRY(::open(idmapPath.string(), O_RDONLY));
+    if (fd == -1) {
+        LOGW("failed to open file %s: %s\n", idmapPath.string(), strerror(errno));
+        return false;
+    }
+    char buf[ResTable::IDMAP_HEADER_SIZE_BYTES];
+    ssize_t bytesLeft = ResTable::IDMAP_HEADER_SIZE_BYTES;
+    for (;;) {
+        ssize_t r = TEMP_FAILURE_RETRY(read(fd, buf + ResTable::IDMAP_HEADER_SIZE_BYTES - bytesLeft,
+                                            bytesLeft));
+        if (r < 0) {
+            TEMP_FAILURE_RETRY(close(fd));
+            return false;
+        }
+        bytesLeft -= r;
+        if (bytesLeft == 0) {
+            break;
+        }
+    }
+    TEMP_FAILURE_RETRY(close(fd));
+
+    uint32_t cachedOriginalCrc, cachedOverlayCrc;
+    if (!ResTable::getIdmapInfo(buf, ResTable::IDMAP_HEADER_SIZE_BYTES,
+                                &cachedOriginalCrc, &cachedOverlayCrc)) {
+        return false;
+    }
+
+    uint32_t actualOriginalCrc, actualOverlayCrc;
+    if (!getZipEntryCrcLocked(originalPath, "resources.arsc", &actualOriginalCrc)) {
+        return false;
+    }
+    if (!getZipEntryCrcLocked(overlayPath, "resources.arsc", &actualOverlayCrc)) {
+        return false;
+    }
+    return cachedOriginalCrc != actualOriginalCrc || cachedOverlayCrc != actualOverlayCrc;
+}
+
+bool AssetManager::getZipEntryCrcLocked(const String8& zipPath, const char* entryFilename,
+                                        uint32_t* pCrc)
+{
+    asset_path ap;
+    ap.path = zipPath;
+    const ZipFileRO* zip = getZipFileLocked(ap);
+    if (zip == NULL) {
+        return false;
+    }
+    const ZipEntryRO entry = zip->findEntryByName(entryFilename);
+    if (entry == NULL) {
+        return false;
+    }
+    if (!zip->getEntryInfo(entry, NULL, NULL, NULL, NULL, NULL, (long*)pCrc)) {
+        return false;
+    }
     return true;
 }
 
+bool AssetManager::createIdmapFileLocked(const String8& originalPath, const String8& overlayPath,
+                                         const String8& idmapPath)
+{
+    LOGD("%s: originalPath=%s overlayPath=%s idmapPath=%s\n",
+         __FUNCTION__, originalPath.string(), overlayPath.string(), idmapPath.string());
+    ResTable tables[2];
+    const String8* paths[2] = { &originalPath, &overlayPath };
+    uint32_t originalCrc, overlayCrc;
+    bool retval = false;
+    ssize_t offset = 0;
+    int fd = 0;
+    uint32_t* data = NULL;
+    size_t size;
+
+    for (int i = 0; i < 2; ++i) {
+        asset_path ap;
+        ap.type = kFileTypeRegular;
+        ap.path = *paths[i];
+        Asset* ass = openNonAssetInPathLocked("resources.arsc", Asset::ACCESS_BUFFER, ap);
+        if (ass == NULL) {
+            LOGW("failed to find resources.arsc in %s\n", ap.path.string());
+            goto error;
+        }
+        tables[i].add(ass, (void*)1, false);
+    }
+
+    if (!getZipEntryCrcLocked(originalPath, "resources.arsc", &originalCrc)) {
+        LOGW("failed to retrieve crc for resources.arsc in %s\n", originalPath.string());
+        goto error;
+    }
+    if (!getZipEntryCrcLocked(overlayPath, "resources.arsc", &overlayCrc)) {
+        LOGW("failed to retrieve crc for resources.arsc in %s\n", overlayPath.string());
+        goto error;
+    }
+
+    if (tables[0].createIdmap(tables[1], originalCrc, overlayCrc,
+                              (void**)&data, &size) != NO_ERROR) {
+        LOGW("failed to generate idmap data for file %s\n", idmapPath.string());
+        goto error;
+    }
+
+    // This should be abstracted (eg replaced by a stand-alone
+    // application like dexopt, triggered by something equivalent to
+    // installd).
+    fd = TEMP_FAILURE_RETRY(::open(idmapPath.string(), O_WRONLY | O_CREAT | O_TRUNC, 0644));
+    if (fd == -1) {
+        LOGW("failed to write idmap file %s (open: %s)\n", idmapPath.string(), strerror(errno));
+        goto error_free;
+    }
+    for (;;) {
+        ssize_t written = TEMP_FAILURE_RETRY(write(fd, data + offset, size));
+        if (written < 0) {
+            LOGW("failed to write idmap file %s (write: %s)\n", idmapPath.string(),
+                 strerror(errno));
+            goto error_close;
+        }
+        size -= (size_t)written;
+        offset += written;
+        if (size == 0) {
+            break;
+        }
+    }
+
+    retval = true;
+error_close:
+    TEMP_FAILURE_RETRY(close(fd));
+error_free:
+    free(data);
+error:
+    return retval;
+}
+
 bool AssetManager::addDefaultAssets()
 {
     const char* root = getenv("ANDROID_ROOT");
@@ -404,6 +619,7 @@ const ResTable* AssetManager::getResTable(bool required) const
         ResTable* sharedRes = NULL;
         bool shared = true;
         const asset_path& ap = mAssetPaths.itemAt(i);
+        Asset* idmap = openIdmapLocked(ap);
         LOGV("Looking for resource asset in '%s'\n", ap.path.string());
         if (ap.type != kFileTypeDirectory) {
             if (i == 0) {
@@ -433,7 +649,7 @@ const ResTable* AssetManager::getResTable(bool required) const
                     // can quickly copy it out for others.
                     LOGV("Creating shared resources for %s", ap.path.string());
                     sharedRes = new ResTable();
-                    sharedRes->add(ass, (void*)(i+1), false);
+                    sharedRes->add(ass, (void*)(i+1), false, idmap);
                     sharedRes = const_cast<AssetManager*>(this)->
                         mZipSet.setZipResourceTable(ap.path, sharedRes);
                 }
@@ -457,7 +673,7 @@ const ResTable* AssetManager::getResTable(bool required) const
                 rt->add(sharedRes);
             } else {
                 LOGV("Parsing resources for %s", ap.path.string());
-                rt->add(ass, (void*)(i+1), !shared);
+                rt->add(ass, (void*)(i+1), !shared, idmap);
             }
 
             if (!shared) {
@@ -498,6 +714,21 @@ void AssetManager::updateResourceParamsLocked() const
     res->setParameters(mConfig);
 }
 
+Asset* AssetManager::openIdmapLocked(const struct asset_path& ap) const
+{
+    Asset* ass = NULL;
+    if (ap.idmap.size() != 0) {
+        ass = const_cast<AssetManager*>(this)->
+            openAssetFromFileLocked(ap.idmap, Asset::ACCESS_BUFFER);
+        if (ass) {
+            LOGV("loading idmap %s\n", ap.idmap.string());
+        } else {
+            LOGW("failed to load idmap %s\n", ap.idmap.string());
+        }
+    }
+    return ass;
+}
+
 const ResTable& AssetManager::getResources(bool required) const
 {
     const ResTable* rt = getResTable(required);
diff --git a/libs/utils/README b/libs/utils/README
index 36a706d..01741e0 100644
--- a/libs/utils/README
+++ b/libs/utils/README
@@ -1,4 +1,6 @@
 Android Utility Function Library
+================================
+
 
 If you need a feature that is native to Linux but not present on other
 platforms, construct a platform-dependent implementation that shares
@@ -12,3 +14,276 @@ The ultimate goal is *not* to create a super-duper platform abstraction
 layer.  The goal is to provide an optimized solution for Linux with
 reasonable implementations for other platforms.
 
+
+
+Resource overlay
+================
+
+
+Introduction
+------------
+
+Overlay packages are special .apk files which provide no code but
+additional resource values (and possibly new configurations) for
+resources in other packages. When an application requests resources,
+the system will return values from either the application's original
+package or any associated overlay package. Any redirection is completely
+transparent to the calling application.
+
+Resource values have the following precedence table, listed in
+descending precedence.
+
+ * overlay package, matching config (eg res/values-en-land)
+
+ * original package, matching config
+
+ * overlay package, no config (eg res/values)
+
+ * original package, no config
+
+During compilation, overlay packages are differentiated from regular
+packages by passing the -o flag to aapt.
+
+
+Background
+----------
+
+This section provides generic background material on resources in
+Android.
+
+
+How resources are bundled in .apk files
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Android .apk files are .zip files, usually housing .dex code,
+certificates and resources, though packages containing resources but
+no code are possible. Resources can be divided into the following
+categories; a `configuration' indicates a set of phone language, display
+density, network operator, etc.
+
+ * assets: uncompressed, raw files packaged as part of an .apk and
+           explicitly referenced by filename. These files are
+           independent of configuration.
+
+ * res/drawable: bitmap or xml graphics. Each file may have different
+                 values depending on configuration.
+
+ * res/values: integers, strings, etc. Each resource may have different
+               values depending on configuration.
+
+Resource meta information and information proper is stored in a binary
+format in a named file resources.arsc, bundled as part of the .apk.
+
+Resource IDs and lookup
+~~~~~~~~~~~~~~~~~~~~~~~
+During compilation, the aapt tool gathers application resources and
+generates a resources.arsc file. Each resource name is assigned an
+integer ID 0xppttiii (translated to a symbolic name via R.java), where
+
+ * pp: corresponds to the package namespace (details below).
+
+ * tt: corresponds to the resource type (string, int, etc). Every
+       resource of the same type within the same package has the same
+       tt value, but depending on available types, the actual numerical
+       value may be different between packages.
+
+ * iiii: sequential number, assigned in the order resources are found.
+
+Resource values are specified paired with a set of configuration
+constraints (the default being the empty set), eg res/values-sv-port
+which imposes restrictions on language (Swedish) and display orientation
+(portrait). During lookup, every constraint set is matched against the
+current configuration, and the value corresponding to the best matching
+constraint set is returned (ResourceTypes.{h,cpp}).
+
+Parsing of resources.arsc is handled by ResourceTypes.cpp; this utility
+is governed by AssetManager.cpp, which tracks loaded resources per
+process.
+
+Assets are looked up by path and filename in AssetManager.cpp. The path
+to resources in res/drawable are located by ResourceTypes.cpp and then
+handled like assets by AssetManager.cpp. Other resources are handled
+solely by ResourceTypes.cpp.
+
+Package ID as namespace
+~~~~~~~~~~~~~~~~~~~~~~~
+The pp part of a resource ID defines a namespace. Android currently
+defines two namespaces:
+
+ * 0x01: system resources (pre-installed in framework-res.apk)
+
+ * 0x7f: application resources (bundled in the application .apk)
+
+ResourceTypes.cpp supports package IDs between 0x01 and 0x7f
+(inclusive); values outside this range are invalid.
+
+Each running (Dalvik) process is assigned a unique instance of
+AssetManager, which in turn keeps a forest structure of loaded
+resource.arsc files. Normally, this forest is structured as follows,
+where mPackageMap is the internal vector employed in ResourceTypes.cpp.
+
+mPackageMap[0x00] -> system package
+mPackageMap[0x01] -> NULL
+mPackageMap[0x02] -> NULL
+...
+mPackageMap[0x7f - 2] -> NULL
+mPackageMap[0x7f - 1] -> application package
+
+
+
+The resource overlay extension
+------------------------------
+
+The resource overlay mechanism aims to (partly) shadow and extend
+existing resources with new values for defined and new configurations.
+Technically, this is achieved by adding resource-only packages (called
+overlay packages) to existing resource namespaces, like so:
+
+mPackageMap[0x00] -> system package -> system overlay package
+mPackageMap[0x01] -> NULL
+mPackageMap[0x02] -> NULL
+...
+mPackageMap[0x7f - 2] -> NULL
+mPackageMap[0x7f - 1] -> application package -> overlay 1 -> overlay 2
+
+The use of overlay resources is completely transparent to
+applications; no additional resource identifiers are introduced, only
+configuration/value pairs. Any number of overlay packages may be loaded
+at a time; overlay packages are agnostic to what they target -- both
+system and application resources are fair game.
+
+The package targeted by an overlay package is called the target or
+original package.
+
+Resource overlay operates on symbolic resources names. Hence, to
+override the string/str1 resources in a package, the overlay package
+would include a resource also named string/str1. The end user does not
+have to worry about the numeric resources IDs assigned by aapt, as this
+is resolved automatically by the system.
+
+As of this writing, the use of resource overlay has not been fully
+explored. Until it has, only OEMs are trusted to use resource overlay.
+For this reason, overlay packages must reside in /system/overlay.
+
+
+Resource ID mapping
+~~~~~~~~~~~~~~~~~~~
+Resource identifiers must be coherent within the same namespace (ie
+PackageGroup in ResourceTypes.cpp). Calling applications will refer to
+resources using the IDs defined in the original package, but there is no
+guarantee aapt has assigned the same ID to the corresponding resource in
+an overlay package. To translate between the two, a resource ID mapping
+{original ID -> overlay ID} is created during package installation
+(PackageManagerService.java) and used during resource lookup. The
+mapping is stored in /data/resource-cache, with a @idmap file name
+suffix.
+
+The idmap file format is documented in a separate section, below.
+
+
+Package management
+~~~~~~~~~~~~~~~~~~
+Packages are managed by the PackageManagerService. Addition and removal
+of packages are monitored via the inotify framework, exposed via
+android.os.FileObserver.
+
+During initialization of a Dalvik process, ActivityThread.java requests
+the process' AssetManager (by proxy, via AssetManager.java and JNI)
+to load a list of packages. This list includes overlay packages, if
+present.
+
+When a target package or a corresponding overlay package is installed,
+the target package's process is stopped and a new idmap is generated.
+This is similar to how applications are stopped when their packages are
+upgraded.
+
+
+Creating overlay packages
+-------------------------
+
+Overlay packages should contain no code, define (some) resources with
+the same type and name as in the original package, and be compiled with
+the -o flag passed to aapt.
+
+The aapt -o flag instructs aapt to create an overlay package.
+Technically, this means the package will be assigned package id 0x00.
+
+There are no restrictions on overlay packages names, though the naming
+convention <original.package.name>.overlay.<name> is recommended.
+
+
+Example overlay package
+~~~~~~~~~~~~~~~~~~~~~~~
+
+To overlay the resource bool/b in package com.foo.bar, to be applied
+when the display is in landscape mode, create a new package with
+no source code and a single .xml file under res/values-land, with
+an entry for bool/b. Compile with aapt -o and place the results in
+/system/overlay by adding the following to Android.mk:
+
+LOCAL_AAPT_FLAGS := -o com.foo.bar
+LOCAL_MODULE_PATH := $(TARGET_OUT)/overlay
+
+
+The ID map (idmap) file format
+------------------------------
+
+The idmap format is designed for lookup performance. However, leading
+and trailing undefined overlay values are discarded to reduce the memory
+footprint.
+
+
+idmap grammar
+~~~~~~~~~~~~~
+All atoms (names in square brackets) are uint32_t integers. The
+idmap-magic constant spells "idmp" in ASCII. Offsets are given relative
+to the data_header, not to the beginning of the file.
+
+map          := header data
+header       := idmap-magic <crc32-original-pkg> <crc32-overlay-pkg>
+idmap-magic  := <0x706d6469>
+data         := data_header type_block+
+data_header  := <m> header_block{m}
+header_block := <0> | <type_block_offset>
+type_block   := <n> <id_offset> entry{n}
+entry        := <resource_id_in_target_package>
+
+
+idmap example
+~~~~~~~~~~~~~
+Given a pair of target and overlay packages with CRC sums 0x216a8fe2
+and 0x6b9beaec, each defining the following resources
+
+Name          Target package  Overlay package
+string/str0   0x7f010000      -
+string/str1   0x7f010001      0x7f010000
+string/str2   0x7f010002      -
+string/str3   0x7f010003      0x7f010001
+string/str4   0x7f010004      -
+bool/bool0    0x7f020000      -
+integer/int0  0x7f030000      0x7f020000
+integer/int1  0x7f030001      -
+
+the corresponding resource map is
+
+0x706d6469 0x216a8fe2 0x6b9beaec 0x00000003 \
+0x00000004 0x00000000 0x00000009 0x00000003 \
+0x00000001 0x7f010000 0x00000000 0x7f010001 \
+0x00000001 0x00000000 0x7f020000
+
+or, formatted differently
+
+0x706d6469  # magic: all idmap files begin with this constant
+0x216a8fe2  # CRC32 of the resources.arsc file in the original package
+0x6b9beaec  # CRC32 of the resources.arsc file in the overlay package
+0x00000003  # header; three types (string, bool, integer) in the target package
+0x00000004  #   header_block for type 0 (string) is located at offset 4
+0x00000000  #   no bool type exists in overlay package -> no header_block
+0x00000009  #   header_block for type 2 (integer) is located at offset 9
+0x00000003  # header_block for string; overlay IDs span 3 elements
+0x00000001  #   the first string in target package is entry 1 == offset
+0x7f010000  #   target 0x7f01001 -> overlay 0x7f010000
+0x00000000  #   str2 not defined in overlay package
+0x7f010001  #   target 0x7f010003 -> overlay 0x7f010001
+0x00000001  # header_block for integer; overlay IDs span 1 element
+0x00000000  #   offset == 0
+0x7f020000  #   target 0x7f030000 -> overlay 0x7f020000
diff --git a/libs/utils/ResourceTypes.cpp b/libs/utils/ResourceTypes.cpp
index 7fb7ae3..57aaf24 100644
--- a/libs/utils/ResourceTypes.cpp
+++ b/libs/utils/ResourceTypes.cpp
@@ -63,6 +63,10 @@ namespace android {
 #endif
 #endif
 
+#define IDMAP_MAGIC         0x706d6469
+// size measured in sizeof(uint32_t)
+#define IDMAP_HEADER_SIZE (ResTable::IDMAP_HEADER_SIZE_BYTES / sizeof(uint32_t))
+
 static void printToLogFunc(void* cookie, const char* txt)
 {
     LOGV("%s", txt);
@@ -214,6 +218,81 @@ static void deserializeInternal(const void* inData, Res_png_9patch* outData) {
     outData->colors = (uint32_t*) data;
 }
 
+static bool assertIdmapHeader(const uint32_t* map, size_t sizeBytes)
+{
+    if (sizeBytes < ResTable::IDMAP_HEADER_SIZE_BYTES) {
+        LOGW("idmap assertion failed: size=%d bytes\n", sizeBytes);
+        return false;
+    }
+    if (*map != htodl(IDMAP_MAGIC)) { // htodl: map data expected to be in correct endianess
+        LOGW("idmap assertion failed: invalid magic found (is 0x%08x, expected 0x%08x)\n",
+             *map, htodl(IDMAP_MAGIC));
+        return false;
+    }
+    return true;
+}
+
+static status_t idmapLookup(const uint32_t* map, size_t sizeBytes, uint32_t key, uint32_t* outValue)
+{
+    // see README for details on the format of map
+    if (!assertIdmapHeader(map, sizeBytes)) {
+        return UNKNOWN_ERROR;
+    }
+    map = map + IDMAP_HEADER_SIZE; // skip ahead to data segment
+    // size of data block, in uint32_t
+    const size_t size = (sizeBytes - ResTable::IDMAP_HEADER_SIZE_BYTES) / sizeof(uint32_t);
+    const uint32_t type = Res_GETTYPE(key) + 1; // add one, idmap stores "public" type id
+    const uint32_t entry = Res_GETENTRY(key);
+    const uint32_t typeCount = *map;
+
+    if (type > typeCount) {
+        LOGW("Resource ID map: type=%d exceeds number of types=%d\n", type, typeCount);
+        return UNKNOWN_ERROR;
+    }
+    if (typeCount > size) {
+        LOGW("Resource ID map: number of types=%d exceeds size of map=%d\n", typeCount, size);
+        return UNKNOWN_ERROR;
+    }
+    const uint32_t typeOffset = map[type];
+    if (typeOffset == 0) {
+        *outValue = 0;
+        return NO_ERROR;
+    }
+    if (typeOffset + 1 > size) {
+        LOGW("Resource ID map: type offset=%d exceeds reasonable value, size of map=%d\n",
+             typeOffset, size);
+        return UNKNOWN_ERROR;
+    }
+    const uint32_t entryCount = map[typeOffset];
+    const uint32_t entryOffset = map[typeOffset + 1];
+    if (entryCount == 0 || entry < entryOffset || entry - entryOffset > entryCount - 1) {
+        *outValue = 0;
+        return NO_ERROR;
+    }
+    const uint32_t index = typeOffset + 2 + entry - entryOffset;
+    if (index > size) {
+        LOGW("Resource ID map: entry index=%d exceeds size of map=%d\n", index, size);
+        *outValue = 0;
+        return NO_ERROR;
+    }
+    *outValue = map[index];
+
+    return NO_ERROR;
+}
+
+static status_t getIdmapPackageId(const uint32_t* map, size_t mapSize, uint32_t *outId)
+{
+    if (!assertIdmapHeader(map, mapSize)) {
+        return UNKNOWN_ERROR;
+    }
+    const uint32_t* p = map + IDMAP_HEADER_SIZE + 1;
+    while (*p == 0) {
+        ++p;
+    }
+    *outId = (map[*p + IDMAP_HEADER_SIZE + 2] >> 24) & 0x000000ff;
+    return NO_ERROR;
+}
+
 Res_png_9patch* Res_png_9patch::deserialize(const void* inData)
 {
     if (sizeof(void*) != sizeof(int32_t)) {
@@ -1235,7 +1314,13 @@ status_t ResXMLTree::validateNode(const ResXMLTree_node* node) const
 
 struct ResTable::Header
 {
-    Header(ResTable* _owner) : owner(_owner), ownedData(NULL), header(NULL) { }
+    Header(ResTable* _owner) : owner(_owner), ownedData(NULL), header(NULL),
+        resourceIDMap(NULL), resourceIDMapSize(0) { }
+
+    ~Header()
+    {
+        free(resourceIDMap);
+    }
 
     ResTable* const                 owner;
     void*                           ownedData;
@@ -1246,6 +1331,8 @@ struct ResTable::Header
     void*                           cookie;
 
     ResStringPool                   values;
+    uint32_t*                       resourceIDMap;
+    size_t                          resourceIDMapSize;
 };
 
 struct ResTable::Type
@@ -1661,12 +1748,13 @@ inline ssize_t ResTable::getResourcePackageIndex(uint32_t resID) const
     return ((ssize_t)mPackageMap[Res_GETPACKAGE(resID)+1])-1;
 }
 
-status_t ResTable::add(const void* data, size_t size, void* cookie, bool copyData)
+status_t ResTable::add(const void* data, size_t size, void* cookie, bool copyData,
+                       const void* idmap)
 {
-    return add(data, size, cookie, NULL, copyData);
+    return add(data, size, cookie, NULL, copyData, reinterpret_cast<const Asset*>(idmap));
 }
 
-status_t ResTable::add(Asset* asset, void* cookie, bool copyData)
+status_t ResTable::add(Asset* asset, void* cookie, bool copyData, const void* idmap)
 {
     const void* data = asset->getBuffer(true);
     if (data == NULL) {
@@ -1674,7 +1762,7 @@ status_t ResTable::add(Asset* asset, void* cookie, bool copyData)
         return UNKNOWN_ERROR;
     }
     size_t size = (size_t)asset->getLength();
-    return add(data, size, cookie, asset, copyData);
+    return add(data, size, cookie, asset, copyData, reinterpret_cast<const Asset*>(idmap));
 }
 
 status_t ResTable::add(ResTable* src)
@@ -1702,19 +1790,30 @@ status_t ResTable::add(ResTable* src)
 }
 
 status_t ResTable::add(const void* data, size_t size, void* cookie,
-                       Asset* asset, bool copyData)
+                       Asset* asset, bool copyData, const Asset* idmap)
 {
     if (!data) return NO_ERROR;
     Header* header = new Header(this);
     header->index = mHeaders.size();
     header->cookie = cookie;
+    if (idmap != NULL) {
+        const size_t idmap_size = idmap->getLength();
+        const void* idmap_data = const_cast<Asset*>(idmap)->getBuffer(true);
+        header->resourceIDMap = (uint32_t*)malloc(idmap_size);
+        if (header->resourceIDMap == NULL) {
+            delete header;
+            return (mError = NO_MEMORY);
+        }
+        memcpy((void*)header->resourceIDMap, idmap_data, idmap_size);
+        header->resourceIDMapSize = idmap_size;
+    }
     mHeaders.add(header);
 
     const bool notDeviceEndian = htods(0xf0) != 0xf0;
 
     LOAD_TABLE_NOISY(
-        LOGV("Adding resources to ResTable: data=%p, size=0x%x, cookie=%p, asset=%p, copy=%d\n",
-             data, size, cookie, asset, copyData));
+        LOGV("Adding resources to ResTable: data=%p, size=0x%x, cookie=%p, asset=%p, copy=%d "
+             "idmap=%p\n", data, size, cookie, asset, copyData, idmap));
     
     if (copyData || notDeviceEndian) {
         header->ownedData = malloc(size);
@@ -1781,7 +1880,16 @@ status_t ResTable::add(const void* data, size_t size, void* cookie,
                      dtohl(header->header->packageCount));
                 return (mError=BAD_TYPE);
             }
-            if (parsePackage((ResTable_package*)chunk, header) != NO_ERROR) {
+            uint32_t idmap_id = 0;
+            if (idmap != NULL) {
+                uint32_t tmp;
+                if (getIdmapPackageId(header->resourceIDMap,
+                                      header->resourceIDMapSize,
+                                      &tmp) == NO_ERROR) {
+                    idmap_id = tmp;
+                }
+            }
+            if (parsePackage((ResTable_package*)chunk, header, idmap_id) != NO_ERROR) {
                 return mError;
             }
             curPackage++;
@@ -1803,6 +1911,7 @@ status_t ResTable::add(const void* data, size_t size, void* cookie,
     if (mError != NO_ERROR) {
         LOGW("No string values found in resource table!");
     }
+
     TABLE_NOISY(LOGV("Returning from add with mError=%d\n", mError));
     return mError;
 }
@@ -1925,17 +2034,38 @@ ssize_t ResTable::getResource(uint32_t resID, Res_value* outValue, bool mayBeBag
     size_t ip = grp->packages.size();
     while (ip > 0) {
         ip--;
+        int T = t;
+        int E = e;
 
         const Package* const package = grp->packages[ip];
+        if (package->header->resourceIDMap) {
+            uint32_t overlayResID = 0x0;
+            status_t retval = idmapLookup(package->header->resourceIDMap,
+                                          package->header->resourceIDMapSize,
+                                          resID, &overlayResID);
+            if (retval == NO_ERROR && overlayResID != 0x0) {
+                // for this loop iteration, this is the type and entry we really want
+                LOGV("resource map 0x%08x -> 0x%08x\n", resID, overlayResID);
+                T = Res_GETTYPE(overlayResID);
+                E = Res_GETENTRY(overlayResID);
+            } else {
+                // resource not present in overlay package, continue with the next package
+                continue;
+            }
+        }
 
         const ResTable_type* type;
         const ResTable_entry* entry;
         const Type* typeClass;
-        ssize_t offset = getEntry(package, t, e, &mParams, &type, &entry, &typeClass);
+        ssize_t offset = getEntry(package, T, E, &mParams, &type, &entry, &typeClass);
         if (offset <= 0) {
-            if (offset < 0) {
+            // No {entry, appropriate config} pair found in package. If this
+            // package is an overlay package (ip != 0), this simply means the
+            // overlay package did not specify a default.
+            // Non-overlay packages are still required to provide a default.
+            if (offset < 0 && ip == 0) {
                 LOGW("Failure getting entry for 0x%08x (t=%d e=%d) in package %zd (error %d)\n",
-                        resID, t, e, ip, (int)offset);
+                        resID, T, E, ip, (int)offset);
                 return offset;
             }
             continue;
@@ -1965,13 +2095,16 @@ ssize_t ResTable::getResource(uint32_t resID, Res_value* outValue, bool mayBeBag
 
         if (outSpecFlags != NULL) {
             if (typeClass->typeSpecFlags != NULL) {
-                *outSpecFlags |= dtohl(typeClass->typeSpecFlags[e]);
+                *outSpecFlags |= dtohl(typeClass->typeSpecFlags[E]);
             } else {
                 *outSpecFlags = -1;
             }
         }
-        
-        if (bestPackage != NULL && bestItem.isMoreSpecificThan(thisConfig)) {
+
+        if (bestPackage != NULL &&
+            (bestItem.isMoreSpecificThan(thisConfig) || bestItem.diff(thisConfig) == 0)) {
+            // Discard thisConfig not only if bestItem is more specific, but also if the two configs
+            // are identical (diff == 0), or overlay packages will not take effect.
             continue;
         }
         
@@ -2165,21 +2298,45 @@ ssize_t ResTable::getBagLocked(uint32_t resID, const bag_entry** outBag,
 
     TABLE_NOISY(LOGI("Building bag: %p\n", (void*)resID));
     
+    ResTable_config bestConfig;
+    memset(&bestConfig, 0, sizeof(bestConfig));
+
     // Now collect all bag attributes from all packages.
     size_t ip = grp->packages.size();
     while (ip > 0) {
         ip--;
+        int T = t;
+        int E = e;
 
         const Package* const package = grp->packages[ip];
+        if (package->header->resourceIDMap) {
+            uint32_t overlayResID = 0x0;
+            status_t retval = idmapLookup(package->header->resourceIDMap,
+                                          package->header->resourceIDMapSize,
+                                          resID, &overlayResID);
+            if (retval == NO_ERROR && overlayResID != 0x0) {
+                // for this loop iteration, this is the type and entry we really want
+                LOGV("resource map 0x%08x -> 0x%08x\n", resID, overlayResID);
+                T = Res_GETTYPE(overlayResID);
+                E = Res_GETENTRY(overlayResID);
+            } else {
+                // resource not present in overlay package, continue with the next package
+                continue;
+            }
+        }
 
         const ResTable_type* type;
         const ResTable_entry* entry;
         const Type* typeClass;
-        LOGV("Getting entry pkg=%p, t=%d, e=%d\n", package, t, e);
-        ssize_t offset = getEntry(package, t, e, &mParams, &type, &entry, &typeClass);
+        LOGV("Getting entry pkg=%p, t=%d, e=%d\n", package, T, E);
+        ssize_t offset = getEntry(package, T, E, &mParams, &type, &entry, &typeClass);
         LOGV("Resulting offset=%d\n", offset);
         if (offset <= 0) {
-            if (offset < 0) {
+            // No {entry, appropriate config} pair found in package. If this
+            // package is an overlay package (ip != 0), this simply means the
+            // overlay package did not specify a default.
+            // Non-overlay packages are still required to provide a default.
+            if (offset < 0 && ip == 0) {
                 if (set) free(set);
                 return offset;
             }
@@ -2192,6 +2349,15 @@ ssize_t ResTable::getBagLocked(uint32_t resID, const bag_entry** outBag,
             continue;
         }
 
+        if (set != NULL && !type->config.isBetterThan(bestConfig, NULL)) {
+            continue;
+        }
+        bestConfig = type->config;
+        if (set) {
+            free(set);
+            set = NULL;
+        }
+
         const uint16_t entrySize = dtohs(entry->size);
         const uint32_t parent = entrySize >= sizeof(ResTable_map_entry)
             ? dtohl(((const ResTable_map_entry*)entry)->parent.ident) : 0;
@@ -2203,43 +2369,41 @@ ssize_t ResTable::getBagLocked(uint32_t resID, const bag_entry** outBag,
         TABLE_NOISY(LOGI("Found map: size=%p parent=%p count=%d\n",
                          entrySize, parent, count));
 
-        if (set == NULL) {
-            // If this map inherits from another, we need to start
-            // with its parent's values.  Otherwise start out empty.
-            TABLE_NOISY(printf("Creating new bag, entrySize=0x%08x, parent=0x%08x\n",
-                         entrySize, parent));
-            if (parent) {
-                const bag_entry* parentBag;
-                uint32_t parentTypeSpecFlags = 0;
-                const ssize_t NP = getBagLocked(parent, &parentBag, &parentTypeSpecFlags);
-                const size_t NT = ((NP >= 0) ? NP : 0) + N;
-                set = (bag_set*)malloc(sizeof(bag_set)+sizeof(bag_entry)*NT);
-                if (set == NULL) {
-                    return NO_MEMORY;
-                }
-                if (NP > 0) {
-                    memcpy(set+1, parentBag, NP*sizeof(bag_entry));
-                    set->numAttrs = NP;
-                    TABLE_NOISY(LOGI("Initialized new bag with %d inherited attributes.\n", NP));
-                } else {
-                    TABLE_NOISY(LOGI("Initialized new bag with no inherited attributes.\n"));
-                    set->numAttrs = 0;
-                }
-                set->availAttrs = NT;
-                set->typeSpecFlags = parentTypeSpecFlags;
+        // If this map inherits from another, we need to start
+        // with its parent's values.  Otherwise start out empty.
+        TABLE_NOISY(printf("Creating new bag, entrySize=0x%08x, parent=0x%08x\n",
+                           entrySize, parent));
+        if (parent) {
+            const bag_entry* parentBag;
+            uint32_t parentTypeSpecFlags = 0;
+            const ssize_t NP = getBagLocked(parent, &parentBag, &parentTypeSpecFlags);
+            const size_t NT = ((NP >= 0) ? NP : 0) + N;
+            set = (bag_set*)malloc(sizeof(bag_set)+sizeof(bag_entry)*NT);
+            if (set == NULL) {
+                return NO_MEMORY;
+            }
+            if (NP > 0) {
+                memcpy(set+1, parentBag, NP*sizeof(bag_entry));
+                set->numAttrs = NP;
+                TABLE_NOISY(LOGI("Initialized new bag with %d inherited attributes.\n", NP));
             } else {
-                set = (bag_set*)malloc(sizeof(bag_set)+sizeof(bag_entry)*N);
-                if (set == NULL) {
-                    return NO_MEMORY;
-                }
+                TABLE_NOISY(LOGI("Initialized new bag with no inherited attributes.\n"));
                 set->numAttrs = 0;
-                set->availAttrs = N;
-                set->typeSpecFlags = 0;
             }
+            set->availAttrs = NT;
+            set->typeSpecFlags = parentTypeSpecFlags;
+        } else {
+            set = (bag_set*)malloc(sizeof(bag_set)+sizeof(bag_entry)*N);
+            if (set == NULL) {
+                return NO_MEMORY;
+            }
+            set->numAttrs = 0;
+            set->availAttrs = N;
+            set->typeSpecFlags = 0;
         }
 
         if (typeClass->typeSpecFlags != NULL) {
-            set->typeSpecFlags |= dtohl(typeClass->typeSpecFlags[e]);
+            set->typeSpecFlags |= dtohl(typeClass->typeSpecFlags[E]);
         } else {
             set->typeSpecFlags = -1;
         }
@@ -3759,7 +3923,7 @@ ssize_t ResTable::getEntry(
 }
 
 status_t ResTable::parsePackage(const ResTable_package* const pkg,
-                                const Header* const header)
+                                const Header* const header, uint32_t idmap_id)
 {
     const uint8_t* base = (const uint8_t*)pkg;
     status_t err = validate_chunk(&pkg->header, sizeof(*pkg),
@@ -3793,8 +3957,12 @@ status_t ResTable::parsePackage(const ResTable_package* const pkg,
     
     Package* package = NULL;
     PackageGroup* group = NULL;
-    uint32_t id = dtohl(pkg->id);
-    if (id != 0 && id < 256) {
+    uint32_t id = idmap_id != 0 ? idmap_id : dtohl(pkg->id);
+    // If at this point id == 0, pkg is an overlay package without a
+    // corresponding idmap. During regular usage, overlay packages are
+    // always loaded alongside their idmaps, but during idmap creation
+    // the package is temporarily loaded by itself.
+    if (id < 256) {
     
         package = new Package(this, header, pkg);
         if (package == NULL) {
@@ -3847,7 +4015,7 @@ status_t ResTable::parsePackage(const ResTable_package* const pkg,
             return (mError=err);
         }
     } else {
-        LOG_ALWAYS_FATAL("Skins not supported!");
+        LOG_ALWAYS_FATAL("Package id out of range");
         return NO_ERROR;
     }
 
@@ -3998,6 +4166,136 @@ status_t ResTable::parsePackage(const ResTable_package* const pkg,
     return NO_ERROR;
 }
 
+status_t ResTable::createIdmap(const ResTable& overlay, uint32_t originalCrc, uint32_t overlayCrc,
+                               void** outData, size_t* outSize) const
+{
+    // see README for details on the format of map
+    if (mPackageGroups.size() == 0) {
+        return UNKNOWN_ERROR;
+    }
+    if (mPackageGroups[0]->packages.size() == 0) {
+        return UNKNOWN_ERROR;
+    }
+
+    Vector<Vector<uint32_t> > map;
+    const PackageGroup* pg = mPackageGroups[0];
+    const Package* pkg = pg->packages[0];
+    size_t typeCount = pkg->types.size();
+    // starting size is header + first item (number of types in map)
+    *outSize = (IDMAP_HEADER_SIZE + 1) * sizeof(uint32_t);
+    const String16 overlayPackage(overlay.mPackageGroups[0]->packages[0]->package->name);
+    const uint32_t pkg_id = pkg->package->id << 24;
+
+    for (size_t typeIndex = 0; typeIndex < typeCount; ++typeIndex) {
+        ssize_t offset = -1;
+        const Type* typeConfigs = pkg->getType(typeIndex);
+        ssize_t mapIndex = map.add();
+        if (mapIndex < 0) {
+            return NO_MEMORY;
+        }
+        Vector<uint32_t>& vector = map.editItemAt(mapIndex);
+        for (size_t entryIndex = 0; entryIndex < typeConfigs->entryCount; ++entryIndex) {
+            uint32_t resID = (0xff000000 & ((pkg->package->id)<<24))
+                | (0x00ff0000 & ((typeIndex+1)<<16))
+                | (0x0000ffff & (entryIndex));
+            resource_name resName;
+            if (!this->getResourceName(resID, &resName)) {
+                return UNKNOWN_ERROR;
+            }
+
+            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());
+            if (overlayResID != 0) {
+                // overlay package has package ID == 0, use original package's ID instead
+                overlayResID |= pkg_id;
+            }
+            vector.push(overlayResID);
+            if (overlayResID != 0 && offset == -1) {
+                offset = Res_GETENTRY(resID);
+            }
+#if 0
+            if (overlayResID != 0) {
+                LOGD("%s/%s 0x%08x -> 0x%08x\n",
+                     String8(String16(resName.type)).string(),
+                     String8(String16(resName.name)).string(),
+                     resID, overlayResID);
+            }
+#endif
+        }
+
+        if (offset != -1) {
+            // shave off leading and trailing entries which lack overlay values
+            vector.removeItemsAt(0, offset);
+            vector.insertAt((uint32_t)offset, 0, 1);
+            while (vector.top() == 0) {
+                vector.pop();
+            }
+            // reserve space for number and offset of entries, and the actual entries
+            *outSize += (2 + vector.size()) * sizeof(uint32_t);
+        } else {
+            // no entries of current type defined in overlay package
+            vector.clear();
+            // reserve space for type offset
+            *outSize += 1 * sizeof(uint32_t);
+        }
+    }
+
+    if ((*outData = malloc(*outSize)) == NULL) {
+        return NO_MEMORY;
+    }
+    uint32_t* data = (uint32_t*)*outData;
+    *data++ = htodl(IDMAP_MAGIC);
+    *data++ = htodl(originalCrc);
+    *data++ = htodl(overlayCrc);
+    const size_t mapSize = map.size();
+    *data++ = htodl(mapSize);
+    size_t offset = mapSize;
+    for (size_t i = 0; i < mapSize; ++i) {
+        const Vector<uint32_t>& vector = map.itemAt(i);
+        const size_t N = vector.size();
+        if (N == 0) {
+            *data++ = htodl(0);
+        } else {
+            offset++;
+            *data++ = htodl(offset);
+            offset += N;
+        }
+    }
+    for (size_t i = 0; i < mapSize; ++i) {
+        const Vector<uint32_t>& vector = map.itemAt(i);
+        const size_t N = vector.size();
+        if (N == 0) {
+            continue;
+        }
+        *data++ = htodl(N - 1); // do not count the offset (which is vector's first element)
+        for (size_t j = 0; j < N; ++j) {
+            const uint32_t& overlayResID = vector.itemAt(j);
+            *data++ = htodl(overlayResID);
+        }
+    }
+
+    return NO_ERROR;
+}
+
+bool ResTable::getIdmapInfo(const void* idmap, size_t sizeBytes,
+                            uint32_t* pOriginalCrc, uint32_t* pOverlayCrc)
+{
+    const uint32_t* map = (const uint32_t*)idmap;
+    if (!assertIdmapHeader(map, sizeBytes)) {
+        return false;
+    }
+    *pOriginalCrc = map[1];
+    *pOverlayCrc = map[2];
+    return true;
+}
+
+
 #ifndef HAVE_ANDROID_OS
 #define CHAR16_TO_CSTR(c16, len) (String8(String16(c16,len)).string())