App widget backup/restore infrastructure

Backup/restore now supports app widgets.

An application involved with app widgets, either hosting or publishing,
now has associated data in its backup dataset related to the state of
widget instantiation on the ancestral device.  That data is processed
by the OS during restore so that the matching widget instances can be
"automatically" regenerated.

To take advantage of this facility, widget-using apps need to do two
things:  first, implement a backup agent and store whatever widget
state they need to properly deal with them post-restore (e.g. the
widget instance size & location, for a host); and second, implement
handlers for new AppWidgetManager broadcasts that describe how to
translate ancestral-dataset widget id numbers to the post-restore
world.  Note that a host or provider doesn't technically need to
store *any* data on its own via its agent; it just needs to opt in
to the backup/restore process by publishing an agent.  The OS will
then store a small amount of data on behalf of each widget-savvy
app within the backup dataset, and act on that data at restore time.

The broadcasts are AppWidgetManager.ACTION_APPWIDGET_RESTORED and
ACTION_APPWIDGET_HOST_RESTORED, and have three associated extras:

    EXTRA_APPWIDGET_OLD_IDS
    EXTRA_APPWIDGET_IDS
    EXTRA_HOST_ID [for the host-side broadcast]

The first two are same-sized arrays of integer widget IDs.  The
_OLD_IDS values are the widget IDs as known to the ancestral device.
The _IDS array holds the corresponding widget IDs in the new post-
restore environment.  The app should simply update the stored
widget IDs in its bookkeeping to the new values, and things are
off and running.  The HOST_ID extra, as one might expect, is the
app-defined host ID value of the particular host instance which
has just been restored.

The broadcasts are sent following the conclusion of the overall
restore pass.  This is because the restore might have occurred in a
tightly restricted lifecycle environment without content providers
or the package's custom Application class.  The _RESTORED broadcast,
however, is always delivered into a normal application environment,
so that the app can use its content provider etc as expected.

*All* widget instances that were processed over the course of the
system restore are indicated in the _RESTORED broadcast, even if
the backing provider or host is not yet installed.  The widget
participant is responsible for understanding that these are
promises that might be fulfilled later rather than necessarily
reflecting the immediate presentable widget state.  (Remember
that following a cloud restore, apps may be installed piecemeal
over a lengthy period of time.)  Telling the hosts up front
about all intended widget instances allows them to show placeholder
UI or similarly useful information rather than surprising the user
with piecemeal unexpected appearances.

The AppWidgetProvider helper class has been updated to add a new
callback, onRestored(...), invoked when the _RESTORED broadcast
is received.  The call to onRestored() is immediately followed by
an invocation of onUpdate() for the affected widgets because
they will need to have their RemoteViews regenerated under the
new ID values.

Bug 10622506
Bug 10707117

Change-Id: Ie0007cdf809600b880d91989c00c3c3b8a4f988b
diff --git a/api/current.txt b/api/current.txt
index e41b3fe..09102fb 100644
--- a/api/current.txt
+++ b/api/current.txt
@@ -4976,15 +4976,19 @@
     field public static final java.lang.String ACTION_APPWIDGET_DELETED = "android.appwidget.action.APPWIDGET_DELETED";
     field public static final java.lang.String ACTION_APPWIDGET_DISABLED = "android.appwidget.action.APPWIDGET_DISABLED";
     field public static final java.lang.String ACTION_APPWIDGET_ENABLED = "android.appwidget.action.APPWIDGET_ENABLED";
+    field public static final java.lang.String ACTION_APPWIDGET_HOST_RESTORED = "android.appwidget.action.APPWIDGET_HOST_RESTORED";
     field public static final java.lang.String ACTION_APPWIDGET_OPTIONS_CHANGED = "android.appwidget.action.APPWIDGET_UPDATE_OPTIONS";
     field public static final java.lang.String ACTION_APPWIDGET_PICK = "android.appwidget.action.APPWIDGET_PICK";
+    field public static final java.lang.String ACTION_APPWIDGET_RESTORED = "android.appwidget.action.APPWIDGET_RESTORED";
     field public static final java.lang.String ACTION_APPWIDGET_UPDATE = "android.appwidget.action.APPWIDGET_UPDATE";
     field public static final java.lang.String EXTRA_APPWIDGET_ID = "appWidgetId";
     field public static final java.lang.String EXTRA_APPWIDGET_IDS = "appWidgetIds";
+    field public static final java.lang.String EXTRA_APPWIDGET_OLD_IDS = "appWidgetOldIds";
     field public static final java.lang.String EXTRA_APPWIDGET_OPTIONS = "appWidgetOptions";
     field public static final java.lang.String EXTRA_APPWIDGET_PROVIDER = "appWidgetProvider";
     field public static final java.lang.String EXTRA_CUSTOM_EXTRAS = "customExtras";
     field public static final java.lang.String EXTRA_CUSTOM_INFO = "customInfo";
+    field public static final java.lang.String EXTRA_HOST_ID = "hostId";
     field public static final int INVALID_APPWIDGET_ID = 0; // 0x0
     field public static final java.lang.String META_DATA_APPWIDGET_PROVIDER = "android.appwidget.provider";
     field public static final java.lang.String OPTION_APPWIDGET_HOST_CATEGORY = "appWidgetCategory";
@@ -5001,6 +5005,7 @@
     method public void onDisabled(android.content.Context);
     method public void onEnabled(android.content.Context);
     method public void onReceive(android.content.Context, android.content.Intent);
+    method public void onRestored(android.content.Context, int[], int[]);
     method public void onUpdate(android.content.Context, android.appwidget.AppWidgetManager, int[]);
   }
 
diff --git a/cmds/bu/src/com/android/commands/bu/Backup.java b/cmds/bu/src/com/android/commands/bu/Backup.java
index 73fd660..2673031 100644
--- a/cmds/bu/src/com/android/commands/bu/Backup.java
+++ b/cmds/bu/src/com/android/commands/bu/Backup.java
@@ -68,6 +68,7 @@
         boolean saveObbs = false;
         boolean saveShared = false;
         boolean doEverything = false;
+        boolean doWidgets = false;
         boolean allIncludesSystem = true;
 
         String arg;
@@ -89,6 +90,10 @@
                     allIncludesSystem = true;
                 } else if ("-nosystem".equals(arg)) {
                     allIncludesSystem = false;
+                } else if ("-widgets".equals(arg)) {
+                    doWidgets = true;
+                } else if ("-nowidgets".equals(arg)) {
+                    doWidgets = false;
                 } else if ("-all".equals(arg)) {
                     doEverything = true;
                 } else {
@@ -114,8 +119,8 @@
         try {
             fd = ParcelFileDescriptor.adoptFd(socketFd);
             String[] packArray = new String[packages.size()];
-            mBackupManager.fullBackup(fd, saveApks, saveObbs, saveShared, doEverything,
-                    allIncludesSystem, packages.toArray(packArray));
+            mBackupManager.fullBackup(fd, saveApks, saveObbs, saveShared, doWidgets,
+                    doEverything, allIncludesSystem, packages.toArray(packArray));
         } catch (RemoteException e) {
             Log.e(TAG, "Unable to invoke backup manager for backup");
         } finally {
diff --git a/core/java/android/app/IBackupAgent.aidl b/core/java/android/app/IBackupAgent.aidl
index 087f83c..4ca06ed 100644
--- a/core/java/android/app/IBackupAgent.aidl
+++ b/core/java/android/app/IBackupAgent.aidl
@@ -76,8 +76,9 @@
      * @param callbackBinder Binder on which to indicate operation completion,
      *        passed here as a convenience to the agent.
      */
-    void doRestore(in ParcelFileDescriptor data, int appVersionCode,
-            in ParcelFileDescriptor newState, int token, IBackupManager callbackBinder);
+    void doRestore(in ParcelFileDescriptor data,
+            int appVersionCode, in ParcelFileDescriptor newState,
+            int token, IBackupManager callbackBinder);
 
     /**
      * Perform a "full" backup to the given file descriptor.  The output file is presumed
@@ -112,8 +113,15 @@
      * @param path Relative path of the file within its semantic domain.
      * @param mode Access mode of the file system entity, e.g. 0660.
      * @param mtime Last modification time of the file system entity.
+     * @param token Opaque token identifying this transaction.  This must
+     *        be echoed back to the backup service binder once the agent is
+     *        finished restoring the application based on the restore data
+     *        contents.
+     * @param callbackBinder Binder on which to indicate operation completion,
+     *        passed here as a convenience to the agent.
      */
     void doRestoreFile(in ParcelFileDescriptor data, long size,
             int type, String domain, String path, long mode, long mtime,
             int token, IBackupManager callbackBinder);
+
 }
diff --git a/core/java/android/app/backup/BackupDataOutput.java b/core/java/android/app/backup/BackupDataOutput.java
index 3a070b6..845784f 100644
--- a/core/java/android/app/backup/BackupDataOutput.java
+++ b/core/java/android/app/backup/BackupDataOutput.java
@@ -17,6 +17,7 @@
 package android.app.backup;
 
 import android.os.ParcelFileDescriptor;
+import android.os.Process;
 
 import java.io.FileDescriptor;
 import java.io.IOException;
@@ -76,13 +77,19 @@
     /**
      * Mark the beginning of one record in the backup data stream. This must be called before
      * {@link #writeEntityData}.
-     * @param key A string key that uniquely identifies the data record within the application
+     * @param key A string key that uniquely identifies the data record within the application.
+     *    Keys whose first character is \uFF00 or higher are not valid.
      * @param dataSize The size in bytes of this record's data.  Passing a dataSize
      *    of -1 indicates that the record under this key should be deleted.
      * @return The number of bytes written to the backup stream
      * @throws IOException if the write failed
      */
     public int writeEntityHeader(String key, int dataSize) throws IOException {
+        if (key != null && key.charAt(0) >= 0xff00) {
+            if (Process.myUid() != Process.SYSTEM_UID) {
+                throw new IllegalArgumentException("Invalid key " + key);
+            }
+        }
         int result = writeEntityHeader_native(mBackupWriter, key, dataSize);
         if (result >= 0) {
             return result;
diff --git a/core/java/android/app/backup/IBackupManager.aidl b/core/java/android/app/backup/IBackupManager.aidl
index 12ee3b6..c629a2e 100644
--- a/core/java/android/app/backup/IBackupManager.aidl
+++ b/core/java/android/app/backup/IBackupManager.aidl
@@ -167,7 +167,7 @@
      *     are to be backed up.  The <code>allApps</code> parameter supersedes this.
      */
     void fullBackup(in ParcelFileDescriptor fd, boolean includeApks, boolean includeObbs,
-            boolean includeShared, boolean allApps, boolean allIncludesSystem,
+            boolean includeShared, boolean doWidgets, boolean allApps, boolean allIncludesSystem,
             in String[] packageNames);
 
     /**
diff --git a/core/java/android/appwidget/AppWidgetManager.java b/core/java/android/appwidget/AppWidgetManager.java
index 8a89cbc..dd3a871 100644
--- a/core/java/android/appwidget/AppWidgetManager.java
+++ b/core/java/android/appwidget/AppWidgetManager.java
@@ -214,6 +214,12 @@
     public static final String EXTRA_CUSTOM_INFO = "customInfo";
 
     /**
+     * An intent extra attached to the {@link #ACTION_APPWIDGET_HOST_RESTORED} broadcast,
+     * indicating the integer ID of the host whose widgets have just been restored.
+     */
+    public static final String EXTRA_HOST_ID = "hostId";
+
+    /**
      * An intent extra to pass to the AppWidget picker containing a {@link java.util.List} of
      * {@link android.os.Bundle} objects to mix in to the list of AppWidgets that are
      * installed.  It will be added to the extras object on the {@link android.content.Intent}
@@ -310,6 +316,86 @@
     public static final String ACTION_APPWIDGET_ENABLED = "android.appwidget.action.APPWIDGET_ENABLED";
 
     /**
+     * Sent to providers after AppWidget state related to the provider has been restored from
+     * backup. The intent contains information about how to translate AppWidget ids from the
+     * restored data to their new equivalents.
+     *
+     * <p>The intent will contain the following extras:
+     *
+     * <table>
+     *   <tr>
+     *     <td>{@link #EXTRA_APPWIDGET_OLD_IDS}</td>
+     *     <td>The set of appWidgetIds represented in a restored backup that have been successfully
+     *     incorporated into the current environment.  This may be all of the AppWidgets known
+     *     to this application, or just a subset.  Each entry in this array of appWidgetIds has
+     *     a corresponding entry in the {@link #EXTRA_APPWIDGET_IDS} extra.</td>
+     *  </tr>
+     *   <tr>
+     *     <td>{@link #EXTRA_APPWIDGET_IDS}</td>
+     *     <td>The set of appWidgetIds now valid for this application.  The app should look at
+     *     its restored widget configuration and translate each appWidgetId in the
+     *     {@link #EXTRA_APPWIDGET_OLD_IDS} array to its new value found at the corresponding
+     *     index within this array.</td>
+     *  </tr>
+     * </table>
+     *
+     * <p class="note">This is a protected intent that can only be sent
+     * by the system.
+     *
+     * @see {@link #ACTION_APPWIDGET_HOST_RESTORED} for the corresponding host broadcast
+     */
+    public static final String ACTION_APPWIDGET_RESTORED
+            = "android.appwidget.action.APPWIDGET_RESTORED";
+
+    /**
+     * Sent to widget hosts after AppWidget state related to the host has been restored from
+     * backup. The intent contains information about how to translate AppWidget ids from the
+     * restored data to their new equivalents.  If an application maintains multiple separate
+     * widget hosts instances, it will receive this broadcast separately for each one.
+     *
+     * <p>The intent will contain the following extras:
+     *
+     * <table>
+     *   <tr>
+     *     <td>{@link #EXTRA_APPWIDGET_OLD_IDS}</td>
+     *     <td>The set of appWidgetIds represented in a restored backup that have been successfully
+     *     incorporated into the current environment.  This may be all of the AppWidgets known
+     *     to this application, or just a subset.  Each entry in this array of appWidgetIds has
+     *     a corresponding entry in the {@link #EXTRA_APPWIDGET_IDS} extra.</td>
+     *  </tr>
+     *   <tr>
+     *     <td>{@link #EXTRA_APPWIDGET_IDS}</td>
+     *     <td>The set of appWidgetIds now valid for this application.  The app should look at
+     *     its restored widget configuration and translate each appWidgetId in the
+     *     {@link #EXTRA_APPWIDGET_OLD_IDS} array to its new value found at the corresponding
+     *     index within this array.</td>
+     *  </tr>
+     *  <tr>
+     *     <td>{@link #EXTRA_HOST_ID}</td>
+     *     <td>The integer ID of the widget host instance whose state has just been restored.</td>
+     *  </tr>
+     * </table>
+     *
+     * <p class="note">This is a protected intent that can only be sent
+     * by the system.
+     *
+     * @see {@link #ACTION_APPWIDGET_RESTORED} for the corresponding provider broadcast
+     */
+    public static final String ACTION_APPWIDGET_HOST_RESTORED
+            = "android.appwidget.action.APPWIDGET_HOST_RESTORED";
+
+    /**
+     * An intent extra that contains multiple appWidgetIds.  These are id values as
+     * they were provided to the application during a recent restore from backup.  It is
+     * attached to the {@link #ACTION_APPWIDGET_RESTORED} broadcast intent.
+     *
+     * <p>
+     * The value will be an int array that can be retrieved like this:
+     * {@sample frameworks/base/tests/appwidgets/AppWidgetHostTest/src/com/android/tests/appwidgethost/TestAppWidgetProvider.java getExtra_EXTRA_APPWIDGET_IDS}
+     */
+    public static final String EXTRA_APPWIDGET_OLD_IDS = "appWidgetOldIds";
+
+    /**
      * Field for the manifest meta-data tag.
      *
      * @see AppWidgetProviderInfo
diff --git a/core/java/android/appwidget/AppWidgetProvider.java b/core/java/android/appwidget/AppWidgetProvider.java
index edf142b..ab91edf 100644
--- a/core/java/android/appwidget/AppWidgetProvider.java
+++ b/core/java/android/appwidget/AppWidgetProvider.java
@@ -66,15 +66,13 @@
                     this.onUpdate(context, AppWidgetManager.getInstance(context), appWidgetIds);
                 }
             }
-        }
-        else if (AppWidgetManager.ACTION_APPWIDGET_DELETED.equals(action)) {
+        } else if (AppWidgetManager.ACTION_APPWIDGET_DELETED.equals(action)) {
             Bundle extras = intent.getExtras();
             if (extras != null && extras.containsKey(AppWidgetManager.EXTRA_APPWIDGET_ID)) {
                 final int appWidgetId = extras.getInt(AppWidgetManager.EXTRA_APPWIDGET_ID);
                 this.onDeleted(context, new int[] { appWidgetId });
             }
-        }
-        else if (AppWidgetManager.ACTION_APPWIDGET_OPTIONS_CHANGED.equals(action)) {
+        } else if (AppWidgetManager.ACTION_APPWIDGET_OPTIONS_CHANGED.equals(action)) {
             Bundle extras = intent.getExtras();
             if (extras != null && extras.containsKey(AppWidgetManager.EXTRA_APPWIDGET_ID)
                     && extras.containsKey(AppWidgetManager.EXTRA_APPWIDGET_OPTIONS)) {
@@ -83,19 +81,28 @@
                 this.onAppWidgetOptionsChanged(context, AppWidgetManager.getInstance(context),
                         appWidgetId, widgetExtras);
             }
-        }
-        else if (AppWidgetManager.ACTION_APPWIDGET_ENABLED.equals(action)) {
+        } else if (AppWidgetManager.ACTION_APPWIDGET_ENABLED.equals(action)) {
             this.onEnabled(context);
-        }
-        else if (AppWidgetManager.ACTION_APPWIDGET_DISABLED.equals(action)) {
+        } else if (AppWidgetManager.ACTION_APPWIDGET_DISABLED.equals(action)) {
             this.onDisabled(context);
+        } else if (AppWidgetManager.ACTION_APPWIDGET_RESTORED.equals(action)) {
+            Bundle extras = intent.getExtras();
+            if (extras != null) {
+                int[] oldIds = extras.getIntArray(AppWidgetManager.EXTRA_APPWIDGET_OLD_IDS);
+                int[] newIds = extras.getIntArray(AppWidgetManager.EXTRA_APPWIDGET_IDS);
+                if (oldIds != null && oldIds.length > 0) {
+                    this.onRestored(context, oldIds, newIds);
+                    this.onUpdate(context, AppWidgetManager.getInstance(context), newIds);
+                }
+            }
         }
     }
     // END_INCLUDE(onReceive)
 
     /**
-     * Called in response to the {@link AppWidgetManager#ACTION_APPWIDGET_UPDATE} broadcast when
-     * this AppWidget provider is being asked to provide {@link android.widget.RemoteViews RemoteViews}
+     * Called in response to the {@link AppWidgetManager#ACTION_APPWIDGET_UPDATE} and
+     * {@link AppWidgetManager#ACTION_APPWIDGET_RESTORED} broadcasts when this AppWidget
+     * provider is being asked to provide {@link android.widget.RemoteViews RemoteViews}
      * for a set of AppWidgets.  Override this method to implement your own AppWidget functionality.
      *
      * {@more}
@@ -123,8 +130,8 @@
      *                  running.
      * @param appWidgetManager A {@link AppWidgetManager} object you can call {@link
      *                  AppWidgetManager#updateAppWidget} on.
-     * @param appWidgetId The appWidgetId of the widget who's size changed.
-     * @param newOptions The appWidgetId of the widget who's size changed.
+     * @param appWidgetId The appWidgetId of the widget whose size changed.
+     * @param newOptions The appWidgetId of the widget whose size changed.
      *
      * @see AppWidgetManager#ACTION_APPWIDGET_OPTIONS_CHANGED
      */
@@ -181,4 +188,24 @@
      */
     public void onDisabled(Context context) {
     }
+
+    /**
+     * Called in response to the {@link AppWidgetManager#ACTION_APPWIDGET_RESTORED} broadcast
+     * when instances of this AppWidget provider have been restored from backup.  If your
+     * provider maintains any persistent data about its widget instances, override this method
+     * to remap the old AppWidgetIds to the new values and update any other app state that may
+     * be relevant.
+     *
+     * <p>This callback will be followed immediately by a call to {@link #onUpdate} so your
+     * provider can immediately generate new RemoteViews suitable for its newly-restored set
+     * of instances.
+     *
+     * {@more}
+     *
+     * @param context
+     * @param oldWidgetIds
+     * @param newWidgetIds
+     */
+    public void onRestored(Context context, int[] oldWidgetIds, int[] newWidgetIds) {
+    }
 }
diff --git a/core/java/com/android/internal/appwidget/IAppWidgetService.aidl b/core/java/com/android/internal/appwidget/IAppWidgetService.aidl
index 7ddd5d2..5214dd9 100644
--- a/core/java/com/android/internal/appwidget/IAppWidgetService.aidl
+++ b/core/java/com/android/internal/appwidget/IAppWidgetService.aidl
@@ -59,6 +59,5 @@
     void bindRemoteViewsService(int appWidgetId, in Intent intent, in IBinder connection, int userId);
     void unbindRemoteViewsService(int appWidgetId, in Intent intent, int userId);
     int[] getAppWidgetIds(in ComponentName provider, int userId);
-
 }
 
diff --git a/core/java/com/android/internal/backup/LocalTransport.java b/core/java/com/android/internal/backup/LocalTransport.java
index a604d84..1bfad05 100644
--- a/core/java/com/android/internal/backup/LocalTransport.java
+++ b/core/java/com/android/internal/backup/LocalTransport.java
@@ -34,6 +34,8 @@
 import java.io.FileInputStream;
 import java.io.FileOutputStream;
 import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Collections;
 
 import libcore.io.ErrnoException;
 import libcore.io.Libcore;
@@ -55,20 +57,24 @@
     private static final String TRANSPORT_DESTINATION_STRING
             = "Backing up to debug-only private cache";
 
-    // The single hardcoded restore set always has the same (nonzero!) token
-    private static final long RESTORE_TOKEN = 1;
+    // The currently-active restore set always has the same (nonzero!) token
+    private static final long CURRENT_SET_TOKEN = 1;
 
     private Context mContext;
     private File mDataDir = new File(Environment.getDownloadCacheDirectory(), "backup");
+    private File mCurrentSetDir = new File(mDataDir, Long.toString(CURRENT_SET_TOKEN));
+
     private PackageInfo[] mRestorePackages = null;
     private int mRestorePackage = -1;  // Index into mRestorePackages
+    private File mRestoreDataDir;
+    private long mRestoreToken;
 
 
     public LocalTransport(Context context) {
         mContext = context;
-        mDataDir.mkdirs();
-        if (!SELinux.restorecon(mDataDir)) {
-            Log.e(TAG, "SELinux restorecon failed for " + mDataDir);
+        mCurrentSetDir.mkdirs();
+        if (!SELinux.restorecon(mCurrentSetDir)) {
+            Log.e(TAG, "SELinux restorecon failed for " + mCurrentSetDir);
         }
     }
 
@@ -96,7 +102,7 @@
 
     public int initializeDevice() {
         if (DEBUG) Log.v(TAG, "wiping all data");
-        deleteContents(mDataDir);
+        deleteContents(mCurrentSetDir);
         return BackupConstants.TRANSPORT_OK;
     }
 
@@ -112,7 +118,7 @@
             }
         }
 
-        File packageDir = new File(mDataDir, packageInfo.packageName);
+        File packageDir = new File(mCurrentSetDir, packageInfo.packageName);
         packageDir.mkdirs();
 
         // Each 'record' in the restore set is kept in its own file, named by
@@ -193,7 +199,7 @@
     public int clearBackupData(PackageInfo packageInfo) {
         if (DEBUG) Log.v(TAG, "clearBackupData() pkg=" + packageInfo.packageName);
 
-        File packageDir = new File(mDataDir, packageInfo.packageName);
+        File packageDir = new File(mCurrentSetDir, packageInfo.packageName);
         final File[] fileset = packageDir.listFiles();
         if (fileset != null) {
             for (File f : fileset) {
@@ -210,22 +216,38 @@
     }
 
     // Restore handling
+    static final long[] POSSIBLE_SETS = { 2, 3, 4, 5, 6, 7, 8, 9 }; 
     public RestoreSet[] getAvailableRestoreSets() throws android.os.RemoteException {
-        // one hardcoded restore set
-        RestoreSet set = new RestoreSet("Local disk image", "flash", RESTORE_TOKEN);
-        RestoreSet[] array = { set };
-        return array;
+        long[] existing = new long[POSSIBLE_SETS.length + 1];
+        int num = 0;
+
+        // see which possible non-current sets exist, then put the current set at the end
+        for (long token : POSSIBLE_SETS) {
+            if ((new File(mDataDir, Long.toString(token))).exists()) {
+                existing[num++] = token;
+            }
+        }
+        // and always the currently-active set last
+        existing[num++] = CURRENT_SET_TOKEN;
+
+        RestoreSet[] available = new RestoreSet[num];
+        for (int i = 0; i < available.length; i++) {
+            available[i] = new RestoreSet("Local disk image", "flash", existing[i]);
+        }
+        return available;
     }
 
     public long getCurrentRestoreSet() {
-        // The hardcoded restore set always has the same token
-        return RESTORE_TOKEN;
+        // The current restore set always has the same token
+        return CURRENT_SET_TOKEN;
     }
 
     public int startRestore(long token, PackageInfo[] packages) {
         if (DEBUG) Log.v(TAG, "start restore " + token);
         mRestorePackages = packages;
         mRestorePackage = -1;
+        mRestoreToken = token;
+        mRestoreDataDir = new File(mDataDir, Long.toString(token));
         return BackupConstants.TRANSPORT_OK;
     }
 
@@ -234,7 +256,7 @@
         while (++mRestorePackage < mRestorePackages.length) {
             String name = mRestorePackages[mRestorePackage].packageName;
             // skip packages where we have a data dir but no actual contents
-            String[] contents = (new File(mDataDir, name)).list();
+            String[] contents = (new File(mRestoreDataDir, name)).list();
             if (contents != null && contents.length > 0) {
                 if (DEBUG) Log.v(TAG, "  nextRestorePackage() = " + name);
                 return name;
@@ -248,29 +270,32 @@
     public int getRestoreData(ParcelFileDescriptor outFd) {
         if (mRestorePackages == null) throw new IllegalStateException("startRestore not called");
         if (mRestorePackage < 0) throw new IllegalStateException("nextRestorePackage not called");
-        File packageDir = new File(mDataDir, mRestorePackages[mRestorePackage].packageName);
+        File packageDir = new File(mRestoreDataDir, mRestorePackages[mRestorePackage].packageName);
 
         // The restore set is the concatenation of the individual record blobs,
-        // each of which is a file in the package's directory
-        File[] blobs = packageDir.listFiles();
+        // each of which is a file in the package's directory.  We return the
+        // data in lexical order sorted by key, so that apps which use synthetic
+        // keys like BLOB_1, BLOB_2, etc will see the date in the most obvious
+        // order.
+        ArrayList<DecodedFilename> blobs = contentsByKey(packageDir);
         if (blobs == null) {  // nextRestorePackage() ensures the dir exists, so this is an error
-            Log.e(TAG, "Error listing directory: " + packageDir);
+            Log.e(TAG, "No keys for package: " + packageDir);
             return BackupConstants.TRANSPORT_ERROR;
         }
 
         // We expect at least some data if the directory exists in the first place
-        if (DEBUG) Log.v(TAG, "  getRestoreData() found " + blobs.length + " key files");
+        if (DEBUG) Log.v(TAG, "  getRestoreData() found " + blobs.size() + " key files");
         BackupDataOutput out = new BackupDataOutput(outFd.getFileDescriptor());
         try {
-            for (File f : blobs) {
+            for (DecodedFilename keyEntry : blobs) {
+                File f = keyEntry.file;
                 FileInputStream in = new FileInputStream(f);
                 try {
                     int size = (int) f.length();
                     byte[] buf = new byte[size];
                     in.read(buf);
-                    String key = new String(Base64.decode(f.getName()));
-                    if (DEBUG) Log.v(TAG, "    ... key=" + key + " size=" + size);
-                    out.writeEntityHeader(key, size);
+                    if (DEBUG) Log.v(TAG, "    ... key=" + keyEntry.key + " size=" + size);
+                    out.writeEntityHeader(keyEntry.key, size);
                     out.writeEntityData(buf, size);
                 } finally {
                     in.close();
@@ -283,6 +308,39 @@
         }
     }
 
+    static class DecodedFilename implements Comparable<DecodedFilename> {
+        public File file;
+        public String key;
+
+        public DecodedFilename(File f) {
+            file = f;
+            key = new String(Base64.decode(f.getName()));
+        }
+
+        @Override
+        public int compareTo(DecodedFilename other) {
+            // sorts into ascending lexical order by decoded key
+            return key.compareTo(other.key);
+        }
+    }
+
+    // Return a list of the files in the given directory, sorted lexically by
+    // the Base64-decoded file name, not by the on-disk filename
+    private ArrayList<DecodedFilename> contentsByKey(File dir) {
+        File[] allFiles = dir.listFiles();
+        if (allFiles == null || allFiles.length == 0) {
+            return null;
+        }
+
+        // Decode the filenames into keys then sort lexically by key
+        ArrayList<DecodedFilename> contents = new ArrayList<DecodedFilename>();
+        for (File f : allFiles) {
+            contents.add(new DecodedFilename(f));
+        }
+        Collections.sort(contents);
+        return contents;
+    }
+
     public void finishRestore() {
         if (DEBUG) Log.v(TAG, "finishRestore()");
     }
diff --git a/core/java/com/android/server/AppWidgetBackupBridge.java b/core/java/com/android/server/AppWidgetBackupBridge.java
new file mode 100644
index 0000000..2ea2f79
--- /dev/null
+++ b/core/java/com/android/server/AppWidgetBackupBridge.java
@@ -0,0 +1,63 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server;
+
+import java.util.List;
+
+/**
+ * Runtime bridge between the Backup Manager Service and the App Widget Service,
+ * since those two modules are intentionally decoupled for modularity.
+ *
+ * @hide
+ */
+public class AppWidgetBackupBridge {
+    private static WidgetBackupProvider sAppWidgetService;
+
+    public static void register(WidgetBackupProvider instance) {
+        sAppWidgetService = instance;
+    }
+
+    public static List<String> getWidgetParticipants(int userId) {
+        return (sAppWidgetService != null)
+                ? sAppWidgetService.getWidgetParticipants(userId)
+                : null;
+    }
+
+    public static byte[] getWidgetState(String packageName, int userId) {
+        return (sAppWidgetService != null)
+                ? sAppWidgetService.getWidgetState(packageName, userId)
+                : null;
+    }
+
+    public static void restoreStarting(int userId) {
+        if (sAppWidgetService != null) {
+            sAppWidgetService.restoreStarting(userId);
+        }
+    }
+
+    public static void restoreWidgetState(String packageName, byte[] restoredState, int userId) {
+        if (sAppWidgetService != null) {
+            sAppWidgetService.restoreWidgetState(packageName, restoredState, userId);
+        }
+    }
+
+    public static void restoreFinished(int userId) {
+        if (sAppWidgetService != null) {
+            sAppWidgetService.restoreFinished(userId);
+        }
+    }
+}
diff --git a/core/java/com/android/server/WidgetBackupProvider.java b/core/java/com/android/server/WidgetBackupProvider.java
new file mode 100644
index 0000000..a2efbdd
--- /dev/null
+++ b/core/java/com/android/server/WidgetBackupProvider.java
@@ -0,0 +1,34 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server;
+
+import java.util.List;
+
+/**
+ * Shim to allow core/backup to communicate with the app widget service
+ * about various important events without needing to be able to see the
+ * implementation of the service.
+ *
+ * @hide
+ */
+public interface WidgetBackupProvider {
+    public List<String> getWidgetParticipants(int userId);
+    public byte[] getWidgetState(String packageName, int userId);
+    public void restoreStarting(int userId);
+    public void restoreWidgetState(String packageName, byte[] restoredState, int userId);
+    public void restoreFinished(int userId);
+}
diff --git a/core/res/AndroidManifest.xml b/core/res/AndroidManifest.xml
index 37ef539b..4e1efc6 100644
--- a/core/res/AndroidManifest.xml
+++ b/core/res/AndroidManifest.xml
@@ -83,6 +83,8 @@
     <protected-broadcast android:name="android.appwidget.action.APPWIDGET_DELETED" />
     <protected-broadcast android:name="android.appwidget.action.APPWIDGET_DISABLED" />
     <protected-broadcast android:name="android.appwidget.action.APPWIDGET_ENABLED" />
+    <protected-broadcast android:name="android.appwidget.action.APPWIDGET_HOST_RESTORED" />
+    <protected-broadcast android:name="android.appwidget.action.APPWIDGET_RESTORED" />
 
     <protected-broadcast android:name="android.backup.intent.RUN" />
     <protected-broadcast android:name="android.backup.intent.CLEAR" />
diff --git a/services/appwidget/java/com/android/server/appwidget/AppWidgetService.java b/services/appwidget/java/com/android/server/appwidget/AppWidgetService.java
index e208677..77d5076 100644
--- a/services/appwidget/java/com/android/server/appwidget/AppWidgetService.java
+++ b/services/appwidget/java/com/android/server/appwidget/AppWidgetService.java
@@ -23,7 +23,6 @@
 import android.content.Context;
 import android.content.Intent;
 import android.content.IntentFilter;
-import android.content.pm.PackageManager;
 import android.os.Binder;
 import android.os.Bundle;
 import android.os.Handler;
@@ -38,18 +37,19 @@
 import com.android.internal.appwidget.IAppWidgetService;
 import com.android.internal.os.BackgroundThread;
 import com.android.internal.util.IndentingPrintWriter;
+import com.android.server.AppWidgetBackupBridge;
+import com.android.server.WidgetBackupProvider;
 import com.android.server.SystemService;
 
 import java.io.FileDescriptor;
 import java.io.PrintWriter;
 import java.util.List;
-import java.util.Locale;
 
 
 /**
  * SystemService that publishes an IAppWidgetService.
  */
-public class AppWidgetService extends SystemService {
+public class AppWidgetService extends SystemService implements WidgetBackupProvider {
 
     static final String TAG = "AppWidgetService";
 
@@ -72,6 +72,7 @@
     @Override
     public void onStart() {
         publishBinderService(Context.APPWIDGET_SERVICE, mServiceImpl);
+        AppWidgetBackupBridge.register(this);
     }
 
     @Override
@@ -81,13 +82,40 @@
         }
     }
 
+
+    // backup <-> app widget service bridge surface
+    @Override
+    public List<String> getWidgetParticipants(int userId) {
+        return mServiceImpl.getWidgetParticipants(userId);
+    }
+
+    @Override
+    public byte[] getWidgetState(String packageName, int userId) {
+        return mServiceImpl.getWidgetState(packageName, userId);
+    }
+
+    @Override
+    public void restoreStarting(int userId) {
+        mServiceImpl.restoreStarting(userId);
+    }
+
+    @Override
+    public void restoreWidgetState(String packageName, byte[] restoredState, int userId) {
+        mServiceImpl.restoreWidgetState(packageName, restoredState, userId);
+    }
+
+    @Override
+    public void restoreFinished(int userId) {
+        mServiceImpl.restoreFinished(userId);
+    }
+
+
+    // implementation entry point and binder service
     private final AppWidgetServiceStub mServiceImpl = new AppWidgetServiceStub();
 
-    private class AppWidgetServiceStub extends IAppWidgetService.Stub {
+    class AppWidgetServiceStub extends IAppWidgetService.Stub {
 
         private boolean mSafeMode;
-        private Locale mLocale;
-        private PackageManager mPackageManager;
 
         public void systemRunning(boolean safeMode) {
             mSafeMode = safeMode;
@@ -227,6 +255,29 @@
             }
         }
 
+
+        // support of the widget/backup bridge
+        public List<String> getWidgetParticipants(int userId) {
+            return getImplForUser(userId).getWidgetParticipants();
+        }
+
+        public byte[] getWidgetState(String packageName, int userId) {
+            return getImplForUser(userId).getWidgetState(packageName);
+        }
+
+        public void restoreStarting(int userId) {
+            getImplForUser(userId).restoreStarting();
+        }
+
+        public void restoreWidgetState(String packageName, byte[] restoredState, int userId) {
+            getImplForUser(userId).restoreWidgetState(packageName, restoredState);
+        }
+
+        public void restoreFinished(int userId) {
+            getImplForUser(userId).restoreFinished();
+        }
+
+
         private void checkPermission(int userId) {
             int realUserId = ActivityManager.handleIncomingUser(
                     Binder.getCallingPid(),
diff --git a/services/appwidget/java/com/android/server/appwidget/AppWidgetServiceImpl.java b/services/appwidget/java/com/android/server/appwidget/AppWidgetServiceImpl.java
index b6391b6..b84df79 100644
--- a/services/appwidget/java/com/android/server/appwidget/AppWidgetServiceImpl.java
+++ b/services/appwidget/java/com/android/server/appwidget/AppWidgetServiceImpl.java
@@ -31,6 +31,7 @@
 import android.content.pm.IPackageManager;
 import android.content.pm.PackageInfo;
 import android.content.pm.PackageManager;
+import android.content.pm.PackageManager.NameNotFoundException;
 import android.content.pm.ResolveInfo;
 import android.content.pm.ServiceInfo;
 import android.content.res.Resources;
@@ -51,6 +52,7 @@
 import android.util.AttributeSet;
 import android.util.Pair;
 import android.util.Slog;
+import android.util.SparseArray;
 import android.util.TypedValue;
 import android.util.Xml;
 import android.view.Display;
@@ -66,6 +68,8 @@
 import org.xmlpull.v1.XmlPullParserException;
 import org.xmlpull.v1.XmlSerializer;
 
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
 import java.io.File;
 import java.io.FileDescriptor;
 import java.io.FileInputStream;
@@ -79,8 +83,11 @@
 import java.util.Iterator;
 import java.util.List;
 import java.util.Locale;
+import java.util.Map.Entry;
 import java.util.Set;
 
+import libcore.util.MutableInt;
+
 class AppWidgetServiceImpl {
 
     private static final String KEYGUARD_HOST_PACKAGE = "com.android.keyguard";
@@ -89,8 +96,10 @@
     private static final String SETTINGS_FILENAME = "appwidgets.xml";
     private static final int MIN_UPDATE_PERIOD = 30 * 60 * 1000; // 30 minutes
     private static final int CURRENT_VERSION = 1; // Bump if the stored widgets need to be upgraded.
+    private static final int WIDGET_STATE_VERSION = 1;  // version of backed-up widget state
 
-    private static boolean DBG = false;
+    private static boolean DBG = true;
+    private static boolean DEBUG_BACKUP = DBG || true;
 
     /*
      * When identifying a Host or Provider based on the calling process, use the uid field. When
@@ -105,6 +114,25 @@
         boolean zombie; // if we're in safe mode, don't prune this just because nobody references it
 
         int tag; // for use while saving state (the index)
+
+        // is there an instance of this provider hosted by the given app?
+        public boolean isHostedBy(String packageName) {
+            final int N = instances.size();
+            for (int i = 0; i < N; i++) {
+                AppWidgetId id = instances.get(i);
+                if (packageName.equals(id.host.packageName)) {
+                    return true;
+                }
+            }
+            return false;
+        }
+
+        @Override
+        public String toString() {
+            return "Provider{" + ((info == null) ? "null" : info.provider)
+                    + (zombie ? " Z" : "")
+                    + '}';
+        }
     }
 
     static class Host {
@@ -125,14 +153,62 @@
                 return this.uid == callingUid;
             }
         }
+
+        boolean hostsPackage(String pkg) {
+            final int N = instances.size();
+            for (int i = 0; i < N; i++) {
+                Provider p = instances.get(i).provider;
+                if (p.info != null && pkg.equals(p.info.provider.getPackageName())) {
+                    return true;
+                }
+            }
+            return false;
+        }
+
+        @Override
+        public String toString() {
+            return "Host{" + packageName + ":" + hostId + '}';
+        }
     }
 
     static class AppWidgetId {
         int appWidgetId;
+        int restoredId;  // tracking & remapping any restored state
         Provider provider;
         RemoteViews views;
         Bundle options;
         Host host;
+
+        @Override
+        public String toString() {
+            return "AppWidgetId{" + appWidgetId + ':' + host + ':' + provider + '}';
+        }
+    }
+
+    AppWidgetId findRestoredWidgetLocked(int restoredId, Host host, Provider p) {
+        if (DEBUG_BACKUP) {
+            Slog.i(TAG, "Find restored widget: id=" + restoredId
+                    + " host=" + host + " provider=" + p);
+        }
+
+        if (p == null || host == null) {
+            return null;
+        }
+
+        final int N = mAppWidgetIds.size();
+        for (int i = 0; i < N; i++) {
+            AppWidgetId widget = mAppWidgetIds.get(i);
+            if (widget.restoredId == restoredId
+                    && widget.host.hostId == host.hostId
+                    && widget.host.packageName.equals(host.packageName)
+                    && widget.provider.info.provider.equals(p.info.provider)) {
+                if (DEBUG_BACKUP) {
+                    Slog.i(TAG, "   Found at " + i + " : " + widget);
+                }
+                return widget;
+            }
+        }
+        return null;
     }
 
     /**
@@ -194,6 +270,22 @@
     boolean mStateLoaded;
     int mMaxWidgetBitmapMemory;
 
+    // Map old (restored) widget IDs to new AppWidgetId instances.  This object is used
+    // as the lock around manipulation of the overall restored-widget state, just as
+    // mAppWidgetIds is used as the lock object around all "live" widget state
+    // manipulations.  Methods that must be called with this lock held are decorated
+    // with the suffix "Lr".
+    //
+    // In cases when both of those locks must be held concurrently, mRestoredWidgetIds
+    // must be acquired *first.*
+    private final SparseArray<AppWidgetId> mRestoredWidgetIds = new SparseArray<AppWidgetId>();
+
+    // We need to make sure to wipe the pre-restore widget state only once for
+    // a given package.  Keep track of what we've done so far here; the list is
+    // cleared at the start of every system restore pass, but preserved through
+    // any install-time restore operations.
+    HashSet<String> mPrunedApps = new HashSet<String>();
+
     private final Handler mSaveStateHandler;
 
     // These are for debugging only -- widgets are going missing in some rare instances
@@ -300,10 +392,19 @@
                         providersModified |= updateProvidersForPackageLocked(pkgName, null);
                     }
                 } else {
-                    // The package was just added
+                    // The package was just added.  Fix up the providers...
                     for (String pkgName : pkgList) {
                         providersModified |= addProvidersForPackageLocked(pkgName);
                     }
+                    // ...and see if these are hosts we've been awaiting
+                    for (String pkg : pkgList) {
+                        try {
+                            int uid = getUidForPackage(pkg);
+                            resolveHostUidLocked(pkg, uid);
+                        } catch (NameNotFoundException e) {
+                            // shouldn't happen; we just installed it!
+                        }
+                    }
                 }
                 saveStateAsync();
             }
@@ -331,6 +432,19 @@
         }
     }
 
+    void resolveHostUidLocked(String pkg, int uid) {
+        final int N = mHosts.size();
+        for (int i = 0; i < N; i++) {
+            Host h = mHosts.get(i);
+            if (h.uid == -1 && pkg.equals(h.packageName)) {
+                if (DEBUG_BACKUP) {
+                    Slog.i(TAG, "host " + pkg + ":" + h.hostId + " resolved to uid " + uid);
+                }
+                h.uid = uid;
+            }
+        }
+    }
+
     private void dumpProvider(Provider p, int index, PrintWriter pw) {
         AppWidgetProviderInfo info = p.info;
         pw.print("  ["); pw.print(index); pw.print("] provider ");
@@ -433,7 +547,7 @@
             if (!mHasFeature) {
                 return;
             }
-            loadAppWidgetListLocked();
+            loadWidgetProviderListLocked();
             loadStateLocked();
             mStateLoaded = true;
         }
@@ -516,6 +630,7 @@
     }
 
     void deleteHostLocked(Host host) {
+        if (DBG) log("Deleting host " + host);
         final int N = host.instances.size();
         for (int i = N - 1; i >= 0; i--) {
             AppWidgetId id = host.instances.get(i);
@@ -719,7 +834,7 @@
             }
             final ComponentName componentName = intent.getComponent();
             try {
-                final ServiceInfo si = AppGlobals.getPackageManager().getServiceInfo(componentName,
+                final ServiceInfo si = mPm.getServiceInfo(componentName,
                         PackageManager.GET_PERMISSIONS, mUserId);
                 if (!android.Manifest.permission.BIND_REMOTEVIEWS.equals(si.permission)) {
                     throw new SecurityException("Selected service does not require "
@@ -981,7 +1096,6 @@
             if (!mHasFeature) {
                 return;
             }
-            options = cloneIfLocalBinder(options);
             ensureStateLoadedLocked();
             AppWidgetId id = lookupAppWidgetIdLocked(appWidgetId);
 
@@ -991,7 +1105,7 @@
 
             Provider p = id.provider;
             // Merge the options
-            id.options.putAll(options);
+            id.options.putAll(cloneIfLocalBinder(options));
 
             // send the broacast saying that this appWidgetId has been deleted
             Intent intent = new Intent(AppWidgetManager.ACTION_APPWIDGET_OPTIONS_CHANGED);
@@ -1278,9 +1392,13 @@
     }
 
     Provider lookupProviderLocked(ComponentName provider) {
-        final int N = mInstalledProviders.size();
+        return lookupProviderLocked(provider, mInstalledProviders);
+    }
+
+    Provider lookupProviderLocked(ComponentName provider, ArrayList<Provider> installedProviders) {
+        final int N = installedProviders.size();
         for (int i = 0; i < N; i++) {
-            Provider p = mInstalledProviders.get(i);
+            Provider p = installedProviders.get(i);
             if (p.info.provider.equals(provider)) {
                 return p;
             }
@@ -1317,11 +1435,12 @@
 
     void pruneHostLocked(Host host) {
         if (host.instances.size() == 0 && host.callbacks == null) {
+            if (DBG) log("Pruning host " + host);
             mHosts.remove(host);
         }
     }
 
-    void loadAppWidgetListLocked() {
+    void loadWidgetProviderListLocked() {
         Intent intent = new Intent(AppWidgetManager.ACTION_APPWIDGET_UPDATE);
         try {
             List<ResolveInfo> broadcastReceivers = mPm.queryIntentReceivers(intent,
@@ -1348,7 +1467,23 @@
         Provider p = parseProviderInfoXml(new ComponentName(ri.activityInfo.packageName,
                 ri.activityInfo.name), ri);
         if (p != null) {
-            mInstalledProviders.add(p);
+            // we might have an inactive entry for this provider already due to
+            // a preceding restore operation.  if so, fix it up in place; otherwise
+            // just add this new one.
+            Provider existing = lookupProviderLocked(p.info.provider);
+            if (existing != null) {
+                if (existing.zombie && !mSafeMode) {
+                    // it's a placeholder that was set up during an app restore
+                    existing.zombie = false;
+                    existing.info = p.info; // the real one filled out from the ResolveInfo
+                    existing.uid = p.uid;
+                    if (DEBUG_BACKUP) {
+                        Slog.i(TAG, "Provider placeholder now reified: " + existing);
+                    }
+                }
+            } else {
+                mInstalledProviders.add(p);
+            }
             return true;
         } else {
             return false;
@@ -1463,6 +1598,554 @@
         }
     }
 
+    public List<String> getWidgetParticipants() {
+        HashSet<String> packages = new HashSet<String>();
+        synchronized (mAppWidgetIds) {
+            final int N = mAppWidgetIds.size();
+            for (int i = 0; i < N; i++) {
+                final AppWidgetId id = mAppWidgetIds.get(i);
+                packages.add(id.host.packageName);
+                packages.add(id.provider.info.provider.getPackageName());
+            }
+        }
+        return new ArrayList<String>(packages);
+    }
+
+    private void serializeProvider(XmlSerializer out, Provider p) throws IOException {
+        out.startTag(null, "p");
+        out.attribute(null, "pkg", p.info.provider.getPackageName());
+        out.attribute(null, "cl", p.info.provider.getClassName());
+        out.endTag(null, "p");
+    }
+
+    private void serializeHost(XmlSerializer out, Host host) throws IOException {
+        out.startTag(null, "h");
+        out.attribute(null, "pkg", host.packageName);
+        out.attribute(null, "id", Integer.toHexString(host.hostId));
+        out.endTag(null, "h");
+    }
+
+    private void serializeAppWidgetId(XmlSerializer out, AppWidgetId id) throws IOException {
+        out.startTag(null, "g");
+        out.attribute(null, "id", Integer.toHexString(id.appWidgetId));
+        out.attribute(null, "rid", Integer.toHexString(id.restoredId));
+        out.attribute(null, "h", Integer.toHexString(id.host.tag));
+        if (id.provider != null) {
+            out.attribute(null, "p", Integer.toHexString(id.provider.tag));
+        }
+        if (id.options != null) {
+            out.attribute(null, "min_width", Integer.toHexString(id.options.getInt(
+                    AppWidgetManager.OPTION_APPWIDGET_MIN_WIDTH)));
+            out.attribute(null, "min_height", Integer.toHexString(id.options.getInt(
+                    AppWidgetManager.OPTION_APPWIDGET_MIN_HEIGHT)));
+            out.attribute(null, "max_width", Integer.toHexString(id.options.getInt(
+                    AppWidgetManager.OPTION_APPWIDGET_MAX_WIDTH)));
+            out.attribute(null, "max_height", Integer.toHexString(id.options.getInt(
+                    AppWidgetManager.OPTION_APPWIDGET_MAX_HEIGHT)));
+            out.attribute(null, "host_category", Integer.toHexString(id.options.getInt(
+                    AppWidgetManager.OPTION_APPWIDGET_HOST_CATEGORY)));
+        }
+        out.endTag(null, "g");
+    }
+
+    private Bundle parseWidgetIdOptions(XmlPullParser parser) {
+        Bundle options = new Bundle();
+        String minWidthString = parser.getAttributeValue(null, "min_width");
+        if (minWidthString != null) {
+            options.putInt(AppWidgetManager.OPTION_APPWIDGET_MIN_WIDTH,
+                    Integer.parseInt(minWidthString, 16));
+        }
+        String minHeightString = parser.getAttributeValue(null, "min_height");
+        if (minHeightString != null) {
+            options.putInt(AppWidgetManager.OPTION_APPWIDGET_MIN_HEIGHT,
+                    Integer.parseInt(minHeightString, 16));
+        }
+        String maxWidthString = parser.getAttributeValue(null, "max_width");
+        if (maxWidthString != null) {
+            options.putInt(AppWidgetManager.OPTION_APPWIDGET_MAX_WIDTH,
+                    Integer.parseInt(maxWidthString, 16));
+        }
+        String maxHeightString = parser.getAttributeValue(null, "max_height");
+        if (maxHeightString != null) {
+            options.putInt(AppWidgetManager.OPTION_APPWIDGET_MAX_HEIGHT,
+                    Integer.parseInt(maxHeightString, 16));
+        }
+        String categoryString = parser.getAttributeValue(null, "host_category");
+        if (categoryString != null) {
+            options.putInt(AppWidgetManager.OPTION_APPWIDGET_HOST_CATEGORY,
+                    Integer.parseInt(categoryString, 16));
+        }
+        return options;
+    }
+
+    // Does this package either host or provide any active widgets?
+    private boolean packageNeedsWidgetBackupLocked(String packageName) {
+        int N = mAppWidgetIds.size();
+        for (int i = 0; i < N; i++) {
+            AppWidgetId id = mAppWidgetIds.get(i);
+            if (packageName.equals(id.host.packageName)) {
+                // this package is hosting widgets, so it knows widget IDs
+                return true;
+            }
+            Provider p = id.provider;
+            if (p != null && packageName.equals(p.info.provider.getPackageName())) {
+                // someone is hosting this app's widgets, so it knows widget IDs
+                return true;
+            }
+        }
+        return false;
+    }
+
+    // build the widget-state blob that we save for the app during backup.
+    public byte[] getWidgetState(String backupTarget) {
+        if (!mHasFeature) {
+            return null;
+        }
+
+        ByteArrayOutputStream stream = new ByteArrayOutputStream();
+        synchronized (mAppWidgetIds) {
+            // Preflight: if this app neither hosts nor provides any live widgets
+            // we have no work to do.
+            if (!packageNeedsWidgetBackupLocked(backupTarget)) {
+                return null;
+            }
+
+            try {
+                XmlSerializer out = new FastXmlSerializer();
+                out.setOutput(stream, "utf-8");
+                out.startDocument(null, true);
+                out.startTag(null, "ws");      // widget state
+                out.attribute(null, "version", String.valueOf(WIDGET_STATE_VERSION));
+                out.attribute(null, "pkg", backupTarget);
+
+                // Remember all the providers that are currently hosted or published
+                // by this package: that is, all of the entities related to this app
+                // which will need to be told about id remapping.
+                int N = mInstalledProviders.size();
+                int index = 0;
+                for (int i = 0; i < N; i++) {
+                    Provider p = mInstalledProviders.get(i);
+                    if (p.instances.size() > 0) {
+                        if (backupTarget.equals(p.info.provider.getPackageName())
+                                || p.isHostedBy(backupTarget)) {
+                            serializeProvider(out, p);
+                            p.tag = index++;
+                        }
+                    }
+                }
+
+                N = mHosts.size();
+                index = 0;
+                for (int i = 0; i < N; i++) {
+                    Host host = mHosts.get(i);
+                    if (backupTarget.equals(host.packageName)
+                            || host.hostsPackage(backupTarget)) {
+                        serializeHost(out, host);
+                        host.tag = index++;
+                    }
+                }
+
+                // All widget instances involving this package,
+                // either as host or as provider
+                N = mAppWidgetIds.size();
+                for (int i = 0; i < N; i++) {
+                    AppWidgetId id = mAppWidgetIds.get(i);
+                    if (backupTarget.equals(id.host.packageName)
+                            || backupTarget.equals(id.provider.info.provider.getPackageName())) {
+                        serializeAppWidgetId(out, id);
+                    }
+                }
+
+                out.endTag(null, "ws");
+                out.endDocument();
+            } catch (IOException e) {
+                Slog.w(TAG, "Unable to save widget state for " + backupTarget);
+                return null;
+            }
+
+        }
+        return stream.toByteArray();
+    }
+
+    public void restoreStarting() {
+        if (DEBUG_BACKUP) {
+            Slog.i(TAG, "restore starting for user " + mUserId);
+        }
+        synchronized (mRestoredWidgetIds) {
+            // We're starting a new "system" restore operation, so any widget restore
+            // state that we see from here on is intended to replace the current
+            // widget configuration of any/all of the affected apps.
+            mPrunedApps.clear();
+            mUpdatesByProvider.clear();
+            mUpdatesByHost.clear();
+        }
+    }
+
+    // We're restoring widget state for 'pkg', so we start by wiping (a) all widget
+    // instances that are hosted by that app, and (b) all instances in other hosts
+    // for which 'pkg' is the provider.  We assume that we'll be restoring all of
+    // these hosts & providers, so will be reconstructing a correct live state.
+    private void pruneWidgetStateLr(String pkg) {
+        if (!mPrunedApps.contains(pkg)) {
+            if (DEBUG_BACKUP) {
+                Slog.i(TAG, "pruning widget state for restoring package " + pkg);
+            }
+            for (int i = mAppWidgetIds.size() - 1; i >= 0; i--) {
+                AppWidgetId id = mAppWidgetIds.get(i);
+                Provider p = id.provider;
+                if (id.host.packageName.equals(pkg)
+                        || p.info.provider.getPackageName().equals(pkg)) {
+                    // 'pkg' is either the host or the provider for this instances,
+                    // so we tear it down in anticipation of it (possibly) being
+                    // reconstructed due to the restore
+                    p.instances.remove(id);
+
+                    unbindAppWidgetRemoteViewsServicesLocked(id);
+                    mAppWidgetIds.remove(i);
+                }
+            }
+            mPrunedApps.add(pkg);
+        } else {
+            if (DEBUG_BACKUP) {
+                Slog.i(TAG, "already pruned " + pkg + ", continuing normally");
+            }
+        }
+    }
+
+    // Accumulate a list of updates that affect the given provider for a final
+    // coalesced notification broadcast once restore is over.
+    class RestoreUpdateRecord {
+        public int oldId;
+        public int newId;
+        public boolean notified;
+
+        public RestoreUpdateRecord(int theOldId, int theNewId) {
+            oldId = theOldId;
+            newId = theNewId;
+            notified = false;
+        }
+    }
+
+    HashMap<Provider, ArrayList<RestoreUpdateRecord>> mUpdatesByProvider
+            = new HashMap<Provider, ArrayList<RestoreUpdateRecord>>();
+    HashMap<Host, ArrayList<RestoreUpdateRecord>> mUpdatesByHost
+            = new HashMap<Host, ArrayList<RestoreUpdateRecord>>();
+
+    private boolean alreadyStashed(ArrayList<RestoreUpdateRecord> stash,
+            final int oldId, final int newId) {
+        final int N = stash.size();
+        for (int i = 0; i < N; i++) {
+            RestoreUpdateRecord r = stash.get(i);
+            if (r.oldId == oldId && r.newId == newId) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    private void stashProviderRestoreUpdateLr(Provider provider, int oldId, int newId) {
+        ArrayList<RestoreUpdateRecord> r = mUpdatesByProvider.get(provider);
+        if (r == null) {
+            r = new ArrayList<RestoreUpdateRecord>();
+            mUpdatesByProvider.put(provider, r);
+        } else {
+            // don't duplicate
+            if (alreadyStashed(r, oldId, newId)) {
+                if (DEBUG_BACKUP) {
+                    Slog.i(TAG, "ID remap " + oldId + " -> " + newId
+                            + " already stashed for " + provider);
+                }
+                return;
+            }
+        }
+        r.add(new RestoreUpdateRecord(oldId, newId));
+    }
+
+    private void stashHostRestoreUpdateLr(Host host, int oldId, int newId) {
+        ArrayList<RestoreUpdateRecord> r = mUpdatesByHost.get(host);
+        if (r == null) {
+            r = new ArrayList<RestoreUpdateRecord>();
+            mUpdatesByHost.put(host, r);
+        } else {
+            if (alreadyStashed(r, oldId, newId)) {
+                if (DEBUG_BACKUP) {
+                    Slog.i(TAG, "ID remap " + oldId + " -> " + newId
+                            + " already stashed for " + host);
+                }
+                return;
+            }
+        }
+        r.add(new RestoreUpdateRecord(oldId, newId));
+    }
+
+    public void restoreWidgetState(String packageName, byte[] restoredState) {
+        if (!mHasFeature) {
+            return;
+        }
+
+        if (DEBUG_BACKUP) {
+            Slog.i(TAG, "Restoring widget state for " + packageName);
+        }
+
+        ByteArrayInputStream stream = new ByteArrayInputStream(restoredState);
+        try {
+            // Providers mentioned in the widget dataset by ordinal
+            ArrayList<Provider> restoredProviders = new ArrayList<Provider>();
+
+            // Hosts mentioned in the widget dataset by ordinal
+            ArrayList<Host> restoredHosts = new ArrayList<Host>();
+
+            //HashSet<String> toNotify = new HashSet<String>();
+
+            XmlPullParser parser = Xml.newPullParser();
+            parser.setInput(stream, null);
+
+            synchronized (mAppWidgetIds) {
+                synchronized (mRestoredWidgetIds) {
+                    int type;
+                    do {
+                        type = parser.next();
+                        if (type == XmlPullParser.START_TAG) {
+                            final String tag = parser.getName();
+                            if ("ws".equals(tag)) {
+                                String v = parser.getAttributeValue(null, "version");
+                                String pkg = parser.getAttributeValue(null, "pkg");
+
+                                // TODO: fix up w.r.t. canonical vs current package names
+                                if (!packageName.equals(pkg)) {
+                                    Slog.w(TAG, "Package mismatch in ws");
+                                    return;
+                                }
+
+                                int version = Integer.parseInt(v);
+                                if (version > WIDGET_STATE_VERSION) {
+                                    Slog.w(TAG, "Unable to process state version " + version);
+                                    return;
+                                }
+                            } else if ("p".equals(tag)) {
+                                String pkg = parser.getAttributeValue(null, "pkg");
+                                String cl = parser.getAttributeValue(null, "cl");
+
+                                // hostedProviders index will match 'p' attribute in widget's
+                                // entry in the xml file being restored
+                                // If there's no live entry for this provider, add an inactive one
+                                // so that widget IDs referring to them can be properly allocated
+                                final ComponentName cn = new ComponentName(pkg, cl);
+                                Provider p = lookupProviderLocked(cn, mInstalledProviders);
+                                if (p == null) {
+                                    p = new Provider();
+                                    p.info = new AppWidgetProviderInfo();
+                                    p.info.provider = cn;
+                                    p.zombie = true;
+                                    mInstalledProviders.add(p);
+                                }
+                                if (DEBUG_BACKUP) {
+                                    Slog.i(TAG, "   provider " + cn);
+                                }
+                                restoredProviders.add(p);
+                            } else if ("h".equals(tag)) {
+                                // The host app may not yet exist on the device.  If it's here we
+                                // just use the existing Host entry, otherwise we create a
+                                // placeholder whose uid will be fixed up at PACKAGE_ADDED time.
+                                String pkg = parser.getAttributeValue(null, "pkg");
+                                int uid;
+                                try {
+                                    uid = getUidForPackage(pkg);
+                                } catch (NameNotFoundException e) {
+                                    uid = -1;
+                                }
+                                int hostId = Integer.parseInt(
+                                        parser.getAttributeValue(null, "id"), 16);
+                                Host h = lookupOrAddHostLocked(uid, pkg, hostId);
+                                if (DEBUG_BACKUP) {
+                                    Slog.i(TAG, "   host[" + restoredHosts.size()
+                                            + "]: {" + h.packageName + ":" + h.hostId + "}");
+                                }
+                                restoredHosts.add(h);
+                            } else if ("g".equals(tag)) {
+                                int restoredId = Integer.parseInt(
+                                        parser.getAttributeValue(null, "id"), 16);
+                                int hostIndex = Integer.parseInt(
+                                        parser.getAttributeValue(null, "h"), 16);
+                                Host host = restoredHosts.get(hostIndex);
+                                Provider p = null;
+                                String prov = parser.getAttributeValue(null, "p");
+                                if (prov != null) {
+                                    // could have been null if the app had allocated an id
+                                    // but not yet established a binding under that id
+                                    int which = Integer.parseInt(prov, 16);
+                                    p = restoredProviders.get(which);
+                                }
+
+                                // We'll be restoring widget state for both the host and
+                                // provider sides of this widget ID, so make sure we are
+                                // beginning from a clean slate on both fronts.
+                                pruneWidgetStateLr(host.packageName);
+                                if (p != null) {
+                                    pruneWidgetStateLr(p.info.provider.getPackageName());
+                                }
+
+                                // Have we heard about this ancestral widget instance before?
+                                AppWidgetId id = findRestoredWidgetLocked(restoredId, host, p);
+                                if (id == null) {
+                                    id = new AppWidgetId();
+                                    id.appWidgetId = mNextAppWidgetId++;
+                                    id.restoredId = restoredId;
+                                    id.options = parseWidgetIdOptions(parser);
+                                    id.host = host;
+                                    id.host.instances.add(id);
+                                    id.provider = p;
+                                    if (id.provider != null) {
+                                        id.provider.instances.add(id);
+                                    }
+                                    if (DEBUG_BACKUP) {
+                                        Slog.i(TAG, "New restored id " + restoredId
+                                                + " now " + id);
+                                    }
+                                    mAppWidgetIds.add(id);
+                                }
+                                if (id.provider.info != null) {
+                                    stashProviderRestoreUpdateLr(id.provider,
+                                            restoredId, id.appWidgetId);
+                                } else {
+                                    Slog.w(TAG, "Missing provider for restored widget " + id);
+                                }
+                                stashHostRestoreUpdateLr(id.host, restoredId, id.appWidgetId);
+
+                                if (DEBUG_BACKUP) {
+                                    Slog.i(TAG, "   instance: " + restoredId
+                                            + " -> " + id.appWidgetId
+                                            + " :: p=" + id.provider);
+                                }
+                            }
+                        }
+                    } while (type != XmlPullParser.END_DOCUMENT);
+
+                    // We've updated our own bookkeeping.  We'll need to notify the hosts and
+                    // providers about the changes, but we can't do that yet because the restore
+                    // target is not necessarily fully live at this moment.  Set aside the
+                    // information for now; the backup manager will call us once more at the
+                    // end of the process when all of the targets are in a known state, and we
+                    // will update at that point.
+                }
+            }
+        } catch (XmlPullParserException e) {
+            Slog.w(TAG, "Unable to restore widget state for " + packageName);
+        } catch (IOException e) {
+            Slog.w(TAG, "Unable to restore widget state for " + packageName);
+        } finally {
+            saveStateAsync();
+        }
+    }
+
+    // Called once following the conclusion of a restore operation.  This is when we
+    // send out updates to apps involved in widget-state restore telling them about
+    // the new widget ID space.
+    public void restoreFinished() {
+        if (DEBUG_BACKUP) {
+            Slog.i(TAG, "restoreFinished for " + mUserId);
+        }
+
+        final UserHandle userHandle = new UserHandle(mUserId);
+        synchronized (mRestoredWidgetIds) {
+            // Build the providers' broadcasts and send them off
+            Set<Entry<Provider, ArrayList<RestoreUpdateRecord>>> providerEntries
+                    = mUpdatesByProvider.entrySet();
+            for (Entry<Provider, ArrayList<RestoreUpdateRecord>> e : providerEntries) {
+                // For each provider there's a list of affected IDs
+                Provider provider = e.getKey();
+                ArrayList<RestoreUpdateRecord> updates = e.getValue();
+                final int pending = countPendingUpdates(updates);
+                if (DEBUG_BACKUP) {
+                    Slog.i(TAG, "Provider " + provider + " pending: " + pending);
+                }
+                if (pending > 0) {
+                    int[] oldIds = new int[pending];
+                    int[] newIds = new int[pending];
+                    final int N = updates.size();
+                    int nextPending = 0;
+                    for (int i = 0; i < N; i++) {
+                        RestoreUpdateRecord r = updates.get(i);
+                        if (!r.notified) {
+                            r.notified = true;
+                            oldIds[nextPending] = r.oldId;
+                            newIds[nextPending] = r.newId;
+                            nextPending++;
+                            if (DEBUG_BACKUP) {
+                                Slog.i(TAG, "   " + r.oldId + " => " + r.newId);
+                            }
+                        }
+                    }
+                    sendWidgetRestoreBroadcast(AppWidgetManager.ACTION_APPWIDGET_RESTORED,
+                            provider, null, oldIds, newIds, userHandle);
+                }
+            }
+
+            // same thing per host
+            Set<Entry<Host, ArrayList<RestoreUpdateRecord>>> hostEntries
+                    = mUpdatesByHost.entrySet();
+            for (Entry<Host, ArrayList<RestoreUpdateRecord>> e : hostEntries) {
+                Host host = e.getKey();
+                if (host.uid > 0) {
+                    ArrayList<RestoreUpdateRecord> updates = e.getValue();
+                    final int pending = countPendingUpdates(updates);
+                    if (DEBUG_BACKUP) {
+                        Slog.i(TAG, "Host " + host + " pending: " + pending);
+                    }
+                    if (pending > 0) {
+                        int[] oldIds = new int[pending];
+                        int[] newIds = new int[pending];
+                        final int N = updates.size();
+                        int nextPending = 0;
+                        for (int i = 0; i < N; i++) {
+                            RestoreUpdateRecord r = updates.get(i);
+                            if (!r.notified) {
+                                r.notified = true;
+                                oldIds[nextPending] = r.oldId;
+                                newIds[nextPending] = r.newId;
+                                nextPending++;
+                                if (DEBUG_BACKUP) {
+                                    Slog.i(TAG, "   " + r.oldId + " => " + r.newId);
+                                }
+                            }
+                        }
+                        sendWidgetRestoreBroadcast(AppWidgetManager.ACTION_APPWIDGET_HOST_RESTORED,
+                                null, host, oldIds, newIds, userHandle);
+                    }
+                }
+            }
+        }
+    }
+
+    private int countPendingUpdates(ArrayList<RestoreUpdateRecord> updates) {
+        int pending = 0;
+        final int N = updates.size();
+        for (int i = 0; i < N; i++) {
+            RestoreUpdateRecord r = updates.get(i);
+            if (!r.notified) {
+                pending++;
+            }
+        }
+        return pending;
+    }
+
+    void sendWidgetRestoreBroadcast(String action, Provider provider, Host host,
+            int[] oldIds, int[] newIds, UserHandle userHandle) {
+        Intent intent = new Intent(action);
+        intent.putExtra(AppWidgetManager.EXTRA_APPWIDGET_OLD_IDS, oldIds);
+        intent.putExtra(AppWidgetManager.EXTRA_APPWIDGET_IDS, newIds);
+        if (provider != null) {
+            intent.setComponent(provider.info.provider);
+            mContext.sendBroadcastAsUser(intent, userHandle);
+        }
+        if (host != null) {
+            intent.setComponent(null);
+            intent.setPackage(host.packageName);
+            intent.putExtra(AppWidgetManager.EXTRA_HOST_ID, host.hostId);
+            mContext.sendBroadcastAsUser(intent, userHandle);
+        }
+    }
+
     private Provider parseProviderInfoXml(ComponentName component, ResolveInfo ri) {
         Provider p = null;
 
@@ -1660,10 +2343,7 @@
             for (int i = 0; i < N; i++) {
                 Provider p = mInstalledProviders.get(i);
                 if (p.instances.size() > 0) {
-                    out.startTag(null, "p");
-                    out.attribute(null, "pkg", p.info.provider.getPackageName());
-                    out.attribute(null, "cl", p.info.provider.getClassName());
-                    out.endTag(null, "p");
+                    serializeProvider(out, p);
                     p.tag = providerIndex;
                     providerIndex++;
                 }
@@ -1672,35 +2352,14 @@
             N = mHosts.size();
             for (int i = 0; i < N; i++) {
                 Host host = mHosts.get(i);
-                out.startTag(null, "h");
-                out.attribute(null, "pkg", host.packageName);
-                out.attribute(null, "id", Integer.toHexString(host.hostId));
-                out.endTag(null, "h");
+                serializeHost(out, host);
                 host.tag = i;
             }
 
             N = mAppWidgetIds.size();
             for (int i = 0; i < N; i++) {
                 AppWidgetId id = mAppWidgetIds.get(i);
-                out.startTag(null, "g");
-                out.attribute(null, "id", Integer.toHexString(id.appWidgetId));
-                out.attribute(null, "h", Integer.toHexString(id.host.tag));
-                if (id.provider != null) {
-                    out.attribute(null, "p", Integer.toHexString(id.provider.tag));
-                }
-                if (id.options != null) {
-                    out.attribute(null, "min_width", Integer.toHexString(id.options.getInt(
-                            AppWidgetManager.OPTION_APPWIDGET_MIN_WIDTH)));
-                    out.attribute(null, "min_height", Integer.toHexString(id.options.getInt(
-                            AppWidgetManager.OPTION_APPWIDGET_MIN_HEIGHT)));
-                    out.attribute(null, "max_width", Integer.toHexString(id.options.getInt(
-                            AppWidgetManager.OPTION_APPWIDGET_MAX_WIDTH)));
-                    out.attribute(null, "max_height", Integer.toHexString(id.options.getInt(
-                            AppWidgetManager.OPTION_APPWIDGET_MAX_HEIGHT)));
-                    out.attribute(null, "host_category", Integer.toHexString(id.options.getInt(
-                            AppWidgetManager.OPTION_APPWIDGET_HOST_CATEGORY)));
-                }
-                out.endTag(null, "g");
+                serializeAppWidgetId(out, id);
             }
 
             Iterator<String> it = mPackagesWithBindWidgetPermission.iterator();
@@ -1801,6 +2460,11 @@
                             mNextAppWidgetId = id.appWidgetId + 1;
                         }
 
+                        // restored ID is allowed to be absent
+                        String restoredIdString = parser.getAttributeValue(null, "rid");
+                        id.restoredId = (restoredIdString == null) ? 0
+                                : Integer.parseInt(restoredIdString, 16);
+
                         Bundle options = new Bundle();
                         String minWidthString = parser.getAttributeValue(null, "min_width");
                         if (minWidthString != null) {
@@ -1975,8 +2639,7 @@
                 continue;
             }
             if (pkgName.equals(ai.packageName)) {
-                addProviderLocked(ri);
-                providersAdded = true;
+                providersAdded = addProviderLocked(ri);
             }
         }
 
diff --git a/services/backup/java/com/android/server/backup/BackupManagerService.java b/services/backup/java/com/android/server/backup/BackupManagerService.java
index 8eaefef..1a1512f 100644
--- a/services/backup/java/com/android/server/backup/BackupManagerService.java
+++ b/services/backup/java/com/android/server/backup/BackupManagerService.java
@@ -24,6 +24,7 @@
 import android.app.IBackupAgent;
 import android.app.PendingIntent;
 import android.app.backup.BackupAgent;
+import android.app.backup.BackupDataInput;
 import android.app.backup.BackupDataOutput;
 import android.app.backup.FullBackup;
 import android.app.backup.RestoreSet;
@@ -82,12 +83,14 @@
 import com.android.internal.backup.BackupConstants;
 import com.android.internal.backup.IBackupTransport;
 import com.android.internal.backup.IObbBackupService;
+import com.android.server.AppWidgetBackupBridge;
 import com.android.server.EventLogTags;
 import com.android.server.SystemService;
 import com.android.server.backup.PackageManagerBackupAgent.Metadata;
 
 import java.io.BufferedInputStream;
 import java.io.BufferedOutputStream;
+import java.io.ByteArrayInputStream;
 import java.io.ByteArrayOutputStream;
 import java.io.DataInputStream;
 import java.io.DataOutputStream;
@@ -115,10 +118,13 @@
 import java.util.Date;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
+import java.util.Map.Entry;
 import java.util.Random;
 import java.util.Set;
+import java.util.TreeMap;
 import java.util.concurrent.atomic.AtomicBoolean;
 import java.util.zip.Deflater;
 import java.util.zip.DeflaterOutputStream;
@@ -136,22 +142,43 @@
 import javax.crypto.spec.PBEKeySpec;
 import javax.crypto.spec.SecretKeySpec;
 
+import libcore.io.ErrnoException;
+import libcore.io.Libcore;
+
 public class BackupManagerService extends IBackupManager.Stub {
 
     private static final String TAG = "BackupManagerService";
     private static final boolean DEBUG = true;
     private static final boolean MORE_DEBUG = false;
 
+    // System-private key used for backing up an app's widget state.  Must
+    // begin with U+FFxx by convention (we reserve all keys starting
+    // with U+FF00 or higher for system use).
+    static final String KEY_WIDGET_STATE = "\uffed\uffedwidget";
+
     // Historical and current algorithm names
     static final String PBKDF_CURRENT = "PBKDF2WithHmacSHA1";
     static final String PBKDF_FALLBACK = "PBKDF2WithHmacSHA1And8bit";
 
     // Name and current contents version of the full-backup manifest file
+    //
+    // Manifest version history:
+    //
+    // 1 : initial release
     static final String BACKUP_MANIFEST_FILENAME = "_manifest";
     static final int BACKUP_MANIFEST_VERSION = 1;
+
+    // External archive format version history:
+    //
+    // 1 : initial release
+    // 2 : no format change per se; version bump to facilitate PBKDF2 version skew detection
+    // 3 : introduced "_meta" metadata file; no other format change per se
+    static final int BACKUP_FILE_VERSION = 3;
     static final String BACKUP_FILE_HEADER_MAGIC = "ANDROID BACKUP\n";
-    static final int BACKUP_FILE_VERSION = 2;
     static final int BACKUP_PW_FILE_VERSION = 2;
+    static final String BACKUP_METADATA_FILENAME = "_meta";
+    static final int BACKUP_METADATA_VERSION = 1;
+    static final int BACKUP_WIDGET_METADATA_TOKEN = 0x01FFED01;
     static final boolean COMPRESS_FULL_BACKUPS = true; // should be true in production
 
     static final String SHARED_BACKUP_AGENT_PACKAGE = "com.android.sharedstoragebackup";
@@ -186,6 +213,7 @@
     private static final int MSG_RUN_FULL_RESTORE = 10;
     private static final int MSG_RETRY_INIT = 11;
     private static final int MSG_RETRY_CLEAR = 12;
+    private static final int MSG_WIDGET_BROADCAST = 13;
 
     // backup task state machine tick
     static final int MSG_BACKUP_RESTORE_STEP = 20;
@@ -337,42 +365,47 @@
         public long token;
         public PackageInfo pkgInfo;
         public int pmToken; // in post-install restore, the PM's token for this transaction
-        public boolean needFullBackup;
+        public boolean isSystemRestore;
         public String[] filterSet;
 
+        // Restore a single package
         RestoreParams(IBackupTransport _transport, String _dirName, IRestoreObserver _obs,
-                long _token, PackageInfo _pkg, int _pmToken, boolean _needFullBackup) {
+                long _token, PackageInfo _pkg, int _pmToken) {
             transport = _transport;
             dirName = _dirName;
             observer = _obs;
             token = _token;
             pkgInfo = _pkg;
             pmToken = _pmToken;
-            needFullBackup = _needFullBackup;
+            isSystemRestore = false;
             filterSet = null;
         }
 
+        // Restore everything possible.  This is the form that Setup Wizard or similar
+        // restore UXes use.
         RestoreParams(IBackupTransport _transport, String _dirName, IRestoreObserver _obs,
-                long _token, boolean _needFullBackup) {
+                long _token) {
             transport = _transport;
             dirName = _dirName;
             observer = _obs;
             token = _token;
             pkgInfo = null;
             pmToken = 0;
-            needFullBackup = _needFullBackup;
+            isSystemRestore = true;
             filterSet = null;
         }
 
+        // Restore some set of packages.  Leave this one up to the caller to specify
+        // whether it's to be considered a system-level restore.
         RestoreParams(IBackupTransport _transport, String _dirName, IRestoreObserver _obs,
-                long _token, String[] _filterSet, boolean _needFullBackup) {
+                long _token, String[] _filterSet, boolean _isSystemRestore) {
             transport = _transport;
             dirName = _dirName;
             observer = _obs;
             token = _token;
             pkgInfo = null;
             pmToken = 0;
-            needFullBackup = _needFullBackup;
+            isSystemRestore = _isSystemRestore;
             filterSet = _filterSet;
         }
     }
@@ -413,16 +446,19 @@
         public boolean includeApks;
         public boolean includeObbs;
         public boolean includeShared;
+        public boolean doWidgets;
         public boolean allApps;
         public boolean includeSystem;
         public String[] packages;
 
         FullBackupParams(ParcelFileDescriptor output, boolean saveApks, boolean saveObbs,
-                boolean saveShared, boolean doAllApps, boolean doSystem, String[] pkgList) {
+                boolean saveShared, boolean alsoWidgets, boolean doAllApps, boolean doSystem,
+                String[] pkgList) {
             fd = output;
             includeApks = saveApks;
             includeObbs = saveObbs;
             includeShared = saveShared;
+            doWidgets = alsoWidgets;
             allApps = doAllApps;
             includeSystem = doSystem;
             packages = pkgList;
@@ -618,7 +654,8 @@
                 FullBackupParams params = (FullBackupParams)msg.obj;
                 PerformFullBackupTask task = new PerformFullBackupTask(params.fd,
                         params.observer, params.includeApks, params.includeObbs,
-                        params.includeShared, params.curPassword, params.encryptPassword,
+                        params.includeShared, params.doWidgets,
+                        params.curPassword, params.encryptPassword,
                         params.allApps, params.includeSystem, params.packages, params.latch);
                 (new Thread(task)).start();
                 break;
@@ -631,7 +668,7 @@
                 PerformRestoreTask task = new PerformRestoreTask(
                         params.transport, params.dirName, params.observer,
                         params.token, params.pkgInfo, params.pmToken,
-                        params.needFullBackup, params.filterSet);
+                        params.isSystemRestore, params.filterSet);
                 Message restoreMsg = obtainMessage(MSG_BACKUP_RESTORE_STEP, task);
                 sendMessage(restoreMsg);
                 break;
@@ -770,6 +807,13 @@
                 }
                 break;
             }
+
+            case MSG_WIDGET_BROADCAST:
+            {
+                final Intent intent = (Intent) msg.obj;
+                mContext.sendBroadcastAsUser(intent, UserHandle.OWNER);
+                break;
+            }
             }
         }
     }
@@ -2360,10 +2404,40 @@
 
         @Override
         public void operationComplete() {
-            // Okay, the agent successfully reported back to us.  Spin the data off to the
+            // Okay, the agent successfully reported back to us.  The next thing we do is
+            // push the app widget state for the app, if any.
+            final String pkgName = mCurrentPackage.packageName;
+            final long filepos = mBackupDataName.length();
+            FileDescriptor fd = mBackupData.getFileDescriptor();
+            try {
+                BackupDataOutput out = new BackupDataOutput(fd);
+                byte[] widgetState = AppWidgetBackupBridge.getWidgetState(pkgName,
+                        UserHandle.USER_OWNER);
+                if (widgetState != null) {
+                    out.writeEntityHeader(KEY_WIDGET_STATE, widgetState.length);
+                    out.writeEntityData(widgetState, widgetState.length);
+                } else {
+                    // No widget state for this app, but push a 'delete' operation for it
+                    // in case they're trying to play games with the payload.
+                    out.writeEntityHeader(KEY_WIDGET_STATE, -1);
+                }
+            } catch (IOException e) {
+                // Hard disk error; recovery/failure policy TBD.  For now roll back,
+                // but we may want to consider this a transport-level failure (i.e.
+                // we're in such a bad state that we can't contemplate doing backup
+                // operations any more during this pass).
+                Slog.w(TAG, "Unable to save widget state for " + pkgName);
+                try {
+                    Libcore.os.ftruncate(fd, filepos);
+                } catch (ErrnoException ee) {
+                    Slog.w(TAG, "Unable to roll back!");
+                }
+            }
+
+            // Spin the data off to the
             // transport and proceed with the next stage.
             if (MORE_DEBUG) Slog.v(TAG, "operationComplete(): sending data to transport for "
-                    + mCurrentPackage.packageName);
+                    + pkgName);
             mBackupHandler.removeMessages(MSG_TIMEOUT);
             clearAgentState();
             addBackupTrace("operation complete");
@@ -2402,17 +2476,14 @@
                 if (mStatus == BackupConstants.TRANSPORT_OK) {
                     mBackupDataName.delete();
                     mNewStateName.renameTo(mSavedStateName);
-                    EventLog.writeEvent(EventLogTags.BACKUP_PACKAGE,
-                            mCurrentPackage.packageName, size);
-                    logBackupComplete(mCurrentPackage.packageName);
+                    EventLog.writeEvent(EventLogTags.BACKUP_PACKAGE, pkgName, size);
+                    logBackupComplete(pkgName);
                 } else {
-                    EventLog.writeEvent(EventLogTags.BACKUP_TRANSPORT_FAILURE,
-                            mCurrentPackage.packageName);
+                    EventLog.writeEvent(EventLogTags.BACKUP_TRANSPORT_FAILURE, pkgName);
                 }
             } catch (Exception e) {
-                Slog.e(TAG, "Transport error backing up " + mCurrentPackage.packageName, e);
-                EventLog.writeEvent(EventLogTags.BACKUP_TRANSPORT_FAILURE,
-                        mCurrentPackage.packageName);
+                Slog.e(TAG, "Transport error backing up " + pkgName, e);
+                EventLog.writeEvent(EventLogTags.BACKUP_TRANSPORT_FAILURE, pkgName);
                 mStatus = BackupConstants.TRANSPORT_ERROR;
             } finally {
                 try { if (backupData != null) backupData.close(); } catch (IOException e) {}
@@ -2631,18 +2702,21 @@
         boolean mIncludeApks;
         boolean mIncludeObbs;
         boolean mIncludeShared;
+        boolean mDoWidgets;
         boolean mAllApps;
         final boolean mIncludeSystem;
-        String[] mPackages;
+        ArrayList<String> mPackages;
         String mCurrentPassword;
         String mEncryptPassword;
         AtomicBoolean mLatchObject;
         File mFilesDir;
         File mManifestFile;
+        File mMetadataFile;
         
 
         class FullBackupRunner implements Runnable {
             PackageInfo mPackage;
+            byte[] mWidgetData;
             IBackupAgent mAgent;
             ParcelFileDescriptor mPipe;
             int mToken;
@@ -2650,8 +2724,10 @@
             boolean mWriteManifest;
 
             FullBackupRunner(PackageInfo pack, IBackupAgent agent, ParcelFileDescriptor pipe,
-                    int token, boolean sendApk, boolean writeManifest)  throws IOException {
+                    int token, boolean sendApk, boolean writeManifest, byte[] widgetData)
+                            throws IOException {
                 mPackage = pack;
+                mWidgetData = widgetData;
                 mAgent = agent;
                 mPipe = ParcelFileDescriptor.dup(pipe.getFileDescriptor());
                 mToken = token;
@@ -2666,12 +2742,24 @@
                             mPipe.getFileDescriptor());
 
                     if (mWriteManifest) {
+                        final boolean writeWidgetData = mWidgetData != null;
                         if (MORE_DEBUG) Slog.d(TAG, "Writing manifest for " + mPackage.packageName);
-                        writeAppManifest(mPackage, mManifestFile, mSendApk);
+                        writeAppManifest(mPackage, mManifestFile, mSendApk, writeWidgetData);
                         FullBackup.backupToTar(mPackage.packageName, null, null,
                                 mFilesDir.getAbsolutePath(),
                                 mManifestFile.getAbsolutePath(),
                                 output);
+                        mManifestFile.delete();
+
+                        // We only need to write a metadata file if we have widget data to stash
+                        if (writeWidgetData) {
+                            writeMetadata(mPackage, mMetadataFile, mWidgetData);
+                            FullBackup.backupToTar(mPackage.packageName, null, null,
+                                    mFilesDir.getAbsolutePath(),
+                                    mMetadataFile.getAbsolutePath(),
+                                    output);
+                            mMetadataFile.delete();
+                        }
                     }
 
                     if (mSendApk) {
@@ -2696,16 +2784,19 @@
 
         PerformFullBackupTask(ParcelFileDescriptor fd, IFullBackupRestoreObserver observer, 
                 boolean includeApks, boolean includeObbs, boolean includeShared,
-                String curPassword, String encryptPassword, boolean doAllApps,
+                boolean doWidgets, String curPassword, String encryptPassword, boolean doAllApps,
                 boolean doSystem, String[] packages, AtomicBoolean latch) {
             mOutputFile = fd;
             mObserver = observer;
             mIncludeApks = includeApks;
             mIncludeObbs = includeObbs;
             mIncludeShared = includeShared;
+            mDoWidgets = doWidgets;
             mAllApps = doAllApps;
             mIncludeSystem = doSystem;
-            mPackages = packages;
+            mPackages = (packages == null)
+                    ? new ArrayList<String>()
+                    : new ArrayList<String>(Arrays.asList(packages));
             mCurrentPassword = curPassword;
             // when backing up, if there is a current backup password, we require that
             // the user use a nonempty encryption password as well.  if one is supplied
@@ -2720,13 +2811,28 @@
 
             mFilesDir = new File("/data/system");
             mManifestFile = new File(mFilesDir, BACKUP_MANIFEST_FILENAME);
+            mMetadataFile = new File(mFilesDir, BACKUP_METADATA_FILENAME);
+        }
+
+        void addPackagesToSet(TreeMap<String, PackageInfo> set, List<String> pkgNames) {
+            for (String pkgName : pkgNames) {
+                if (!set.containsKey(pkgName)) {
+                    try {
+                        PackageInfo info = mPackageManager.getPackageInfo(pkgName,
+                                PackageManager.GET_SIGNATURES);
+                        set.put(pkgName, info);
+                    } catch (NameNotFoundException e) {
+                        Slog.w(TAG, "Unknown package " + pkgName + ", skipping");
+                    }
+                }
+            }
         }
 
         @Override
         public void run() {
             Slog.i(TAG, "--- Performing full-dataset backup ---");
 
-            List<PackageInfo> packagesToBackup = new ArrayList<PackageInfo>();
+            TreeMap<String, PackageInfo> packagesToBackup = new TreeMap<String, PackageInfo>();
             FullBackupObbConnection obbConnection = new FullBackupObbConnection();
             obbConnection.establish();  // we'll want this later
 
@@ -2734,63 +2840,70 @@
 
             // doAllApps supersedes the package set if any
             if (mAllApps) {
-                packagesToBackup = mPackageManager.getInstalledPackages(
+                List<PackageInfo> allPackages = mPackageManager.getInstalledPackages(
                         PackageManager.GET_SIGNATURES);
-                // Exclude system apps if we've been asked to do so
-                if (mIncludeSystem == false) {
-                    for (int i = 0; i < packagesToBackup.size(); ) {
-                        PackageInfo pkg = packagesToBackup.get(i);
-                        if ((pkg.applicationInfo.flags & ApplicationInfo.FLAG_SYSTEM) != 0) {
-                            packagesToBackup.remove(i);
-                        } else {
-                            i++;
-                        }
+                for (int i = 0; i < allPackages.size(); i++) {
+                    PackageInfo pkg = allPackages.get(i);
+                    // Exclude system apps if we've been asked to do so
+                    if (mIncludeSystem == true
+                            || ((pkg.applicationInfo.flags & ApplicationInfo.FLAG_SYSTEM) != 0)) {
+                        packagesToBackup.put(pkg.packageName, pkg);
                     }
                 }
             }
 
+            // If we're doing widget state as well, ensure that we have all the involved
+            // host & provider packages in the set
+            if (mDoWidgets) {
+                List<String> pkgs =
+                        AppWidgetBackupBridge.getWidgetParticipants(UserHandle.USER_OWNER);
+                if (pkgs != null) {
+                    if (MORE_DEBUG) {
+                        Slog.i(TAG, "Adding widget participants to backup set:");
+                        StringBuilder sb = new StringBuilder(128);
+                        sb.append("   ");
+                        for (String s : pkgs) {
+                            sb.append(' ');
+                            sb.append(s);
+                        }
+                        Slog.i(TAG, sb.toString());
+                    }
+                    addPackagesToSet(packagesToBackup, pkgs);
+                }
+            }
+
             // Now process the command line argument packages, if any. Note that explicitly-
             // named system-partition packages will be included even if includeSystem was
             // set to false.
             if (mPackages != null) {
-                for (String pkgName : mPackages) {
-                    try {
-                        packagesToBackup.add(mPackageManager.getPackageInfo(pkgName,
-                                PackageManager.GET_SIGNATURES));
-                    } catch (NameNotFoundException e) {
-                        Slog.w(TAG, "Unknown package " + pkgName + ", skipping");
-                    }
-                }
+                addPackagesToSet(packagesToBackup, mPackages);
             }
 
-            // Cull any packages that have indicated that backups are not permitted, as well
-            // as any explicit mention of the 'special' shared-storage agent package (we
-            // handle that one at the end).
-            for (int i = 0; i < packagesToBackup.size(); ) {
-                PackageInfo pkg = packagesToBackup.get(i);
+            // Now we cull any inapplicable / inappropriate packages from the set
+            Iterator<Entry<String, PackageInfo>> iter = packagesToBackup.entrySet().iterator();
+            while (iter.hasNext()) {
+                PackageInfo pkg = iter.next().getValue();
                 if ((pkg.applicationInfo.flags & ApplicationInfo.FLAG_ALLOW_BACKUP) == 0
                         || pkg.packageName.equals(SHARED_BACKUP_AGENT_PACKAGE)) {
-                    packagesToBackup.remove(i);
-                } else {
-                    i++;
-                }
-            }
-
-            // Cull any packages that run as system-domain uids but do not define their
-            // own backup agents
-            for (int i = 0; i < packagesToBackup.size(); ) {
-                PackageInfo pkg = packagesToBackup.get(i);
-                if ((pkg.applicationInfo.uid < Process.FIRST_APPLICATION_UID)
+                    // Cull any packages that have indicated that backups are not permitted, as well
+                    // as any explicit mention of the 'special' shared-storage agent package (we
+                    // handle that one at the end).
+                    iter.remove();
+                } else if ((pkg.applicationInfo.uid < Process.FIRST_APPLICATION_UID)
                         && (pkg.applicationInfo.backupAgentName == null)) {
+                    // Cull any packages that run as system-domain uids but do not define their
+                    // own backup agents
                     if (MORE_DEBUG) {
                         Slog.i(TAG, "... ignoring non-agent system package " + pkg.packageName);
                     }
-                    packagesToBackup.remove(i);
-                } else {
-                    i++;
+                    iter.remove();
                 }
             }
 
+            // flatten the set of packages now so we can explicitly control the ordering
+            ArrayList<PackageInfo> backupQueue =
+                    new ArrayList<PackageInfo>(packagesToBackup.values());
+
             FileOutputStream ofstream = new FileOutputStream(mOutputFile.getFileDescriptor());
             OutputStream out = null;
 
@@ -2866,16 +2979,16 @@
                 if (mIncludeShared) {
                     try {
                         pkg = mPackageManager.getPackageInfo(SHARED_BACKUP_AGENT_PACKAGE, 0);
-                        packagesToBackup.add(pkg);
+                        backupQueue.add(pkg);
                     } catch (NameNotFoundException e) {
                         Slog.e(TAG, "Unable to find shared-storage backup handler");
                     }
                 }
 
                 // Now back up the app data via the agent mechanism
-                int N = packagesToBackup.size();
+                int N = backupQueue.size();
                 for (int i = 0; i < N; i++) {
-                    pkg = packagesToBackup.get(i);
+                    pkg = backupQueue.get(i);
                     backupOnePackage(pkg, out);
 
                     // after the app's agent runs to handle its private filesystem
@@ -3006,11 +3119,13 @@
                             && ((app.flags & ApplicationInfo.FLAG_SYSTEM) == 0 ||
                                 (app.flags & ApplicationInfo.FLAG_UPDATED_SYSTEM_APP) != 0);
 
+                    byte[] widgetBlob = AppWidgetBackupBridge.getWidgetState(pkg.packageName,
+                            UserHandle.USER_OWNER);
                     sendOnBackupPackage(isSharedStorage ? "Shared storage" : pkg.packageName);
 
                     final int token = generateToken();
                     FullBackupRunner runner = new FullBackupRunner(pkg, agent, pipes[1],
-                            token, sendApk, !isSharedStorage);
+                            token, sendApk, !isSharedStorage, widgetBlob);
                     pipes[1].close();   // the runner has dup'd it
                     pipes[1] = null;
                     Thread t = new Thread(runner);
@@ -3086,8 +3201,8 @@
             }
         }
 
-        private void writeAppManifest(PackageInfo pkg, File manifestFile, boolean withApk)
-                throws IOException {
+        private void writeAppManifest(PackageInfo pkg, File manifestFile,
+                boolean withApk, boolean withWidgets) throws IOException {
             // Manifest format. All data are strings ending in LF:
             //     BACKUP_MANIFEST_VERSION, currently 1
             //
@@ -3125,6 +3240,43 @@
             outstream.close();
         }
 
+        // Widget metadata format. All header entries are strings ending in LF:
+        //
+        // Version 1 header:
+        //     BACKUP_METADATA_VERSION, currently "1"
+        //     package name
+        //
+        // File data (all integers are binary in network byte order)
+        // *N: 4 : integer token identifying which metadata blob
+        //     4 : integer size of this blob = N
+        //     N : raw bytes of this metadata blob
+        //
+        // Currently understood blobs (always in network byte order):
+        //
+        //     widgets : metadata token = 0x01FFED01 (BACKUP_WIDGET_METADATA_TOKEN)
+        //
+        // Unrecognized blobs are *ignored*, not errors.
+        private void writeMetadata(PackageInfo pkg, File destination, byte[] widgetData)
+                throws IOException {
+            StringBuilder b = new StringBuilder(512);
+            StringBuilderPrinter printer = new StringBuilderPrinter(b);
+            printer.println(Integer.toString(BACKUP_METADATA_VERSION));
+            printer.println(pkg.packageName);
+
+            FileOutputStream fout = new FileOutputStream(destination);
+            BufferedOutputStream bout = new BufferedOutputStream(fout);
+            DataOutputStream out = new DataOutputStream(bout);
+            bout.write(b.toString().getBytes());    // bypassing DataOutputStream
+
+            if (widgetData != null && widgetData.length > 0) {
+                out.writeInt(BACKUP_WIDGET_METADATA_TOKEN);
+                out.writeInt(widgetData.length);
+                out.write(widgetData);
+            }
+            bout.flush();
+            out.close();
+        }
+
         private void tearDown(PackageInfo pkg) {
             if (pkg != null) {
                 final ApplicationInfo app = pkg.applicationInfo;
@@ -3228,6 +3380,7 @@
         ApplicationInfo mTargetApp;
         FullBackupObbConnection mObbConnection = null;
         ParcelFileDescriptor[] mPipes = null;
+        byte[] mWidgetData = null;
 
         long mBytes;
 
@@ -3524,7 +3677,8 @@
                         // Clean up the previous agent relationship if necessary,
                         // and let the observer know we're considering a new app.
                         if (mAgent != null) {
-                            if (DEBUG) Slog.d(TAG, "Saw new package; tearing down old one");
+                            if (DEBUG) Slog.d(TAG, "Saw new package; finalizing old one");
+                            // Now we're really done
                             tearDownPipes();
                             tearDownAgent(mTargetApp);
                             mTargetApp = null;
@@ -3540,6 +3694,9 @@
                         // input file
                         skipTarPadding(info.size, instream);
                         sendOnRestorePackage(pkg);
+                    } else if (info.path.equals(BACKUP_METADATA_FILENAME)) {
+                        // Metadata blobs!
+                        readMetadata(info, instream);
                     } else {
                         // Non-manifest, so it's actual file data.  Is this a package
                         // we're ignoring?
@@ -3996,6 +4153,71 @@
             }
         }
 
+        // Read a widget metadata file, returning the restored blob
+        void readMetadata(FileMetadata info, InputStream instream) throws IOException {
+            byte[] data = null;
+
+            // Fail on suspiciously large widget dump files
+            if (info.size > 64 * 1024) {
+                throw new IOException("Metadata too big; corrupt? size=" + info.size);
+            }
+
+            byte[] buffer = new byte[(int) info.size];
+            if (readExactly(instream, buffer, 0, (int)info.size) == info.size) {
+                mBytes += info.size;
+            } else throw new IOException("Unexpected EOF in widget data");
+
+            String[] str = new String[1];
+            int offset = extractLine(buffer, 0, str);
+            int version = Integer.parseInt(str[0]);
+            if (version == BACKUP_MANIFEST_VERSION) {
+                offset = extractLine(buffer, offset, str);
+                final String pkg = str[0];
+                if (info.packageName.equals(pkg)) {
+                    // Data checks out -- the rest of the buffer is a concatenation of
+                    // binary blobs as described in the comment at writeAppWidgetData()
+                    ByteArrayInputStream bin = new ByteArrayInputStream(buffer,
+                            offset, buffer.length - offset);
+                    DataInputStream in = new DataInputStream(bin);
+                    while (bin.available() > 0) {
+                        int token = in.readInt();
+                        int size = in.readInt();
+                        if (size > 64 * 1024) {
+                            throw new IOException("Datum "
+                                    + Integer.toHexString(token)
+                                    + " too big; corrupt? size=" + info.size);
+                        }
+                        switch (token) {
+                            case BACKUP_WIDGET_METADATA_TOKEN:
+                            {
+                                if (MORE_DEBUG) {
+                                    Slog.i(TAG, "Got widget metadata for " + info.packageName);
+                                }
+                                mWidgetData = new byte[size];
+                                in.read(mWidgetData);
+                                break;
+                            }
+                            default:
+                            {
+                                if (DEBUG) {
+                                    Slog.i(TAG, "Ignoring metadata blob "
+                                            + Integer.toHexString(token)
+                                            + " for " + info.packageName);
+                                }
+                                in.skipBytes(size);
+                                break;
+                            }
+                        }
+                    }
+                } else {
+                    Slog.w(TAG, "Metadata mismatch: package " + info.packageName
+                            + " but widget data for " + pkg);
+                }
+            } else {
+                Slog.w(TAG, "Unsupported metadata version " + version);
+            }
+        }
+
         // Returns a policy constant; takes a buffer arg to reduce memory churn
         RestorePolicy readAppManifest(FileMetadata info, InputStream instream)
                 throws IOException {
@@ -4486,7 +4708,7 @@
         private PackageInfo mTargetPackage;
         private File mStateDir;
         private int mPmToken;
-        private boolean mNeedFullBackup;
+        private boolean mIsSystemRestore;
         private HashSet<String> mFilterSet;
         private long mStartRealtime;
         private PackageManagerBackupAgent mPmAgent;
@@ -4497,11 +4719,13 @@
         private boolean mFinished;
         private int mStatus;
         private File mBackupDataName;
+        private File mStageName;
         private File mNewStateName;
         private File mSavedStateName;
         private ParcelFileDescriptor mBackupData;
         private ParcelFileDescriptor mNewState;
         private PackageInfo mCurrentPackage;
+        private byte[] mWidgetData;
 
 
         class RestoreRequest {
@@ -4516,7 +4740,7 @@
 
         PerformRestoreTask(IBackupTransport transport, String dirName, IRestoreObserver observer,
                 long restoreSetToken, PackageInfo targetPackage, int pmToken,
-                boolean needFullBackup, String[] filterSet) {
+                boolean isSystemRestore, String[] filterSet) {
             mCurrentState = RestoreState.INITIAL;
             mFinished = false;
             mPmAgent = null;
@@ -4526,7 +4750,7 @@
             mToken = restoreSetToken;
             mTargetPackage = targetPackage;
             mPmToken = pmToken;
-            mNeedFullBackup = needFullBackup;
+            mIsSystemRestore = isSystemRestore;
 
             if (filterSet != null) {
                 mFilterSet = new HashSet<String>();
@@ -4696,8 +4920,7 @@
                 omPackage.packageName = PACKAGE_MANAGER_SENTINEL;
                 mPmAgent = new PackageManagerBackupAgent(
                         mPackageManager, mAgentPackages);
-                initiateOneRestore(omPackage, 0, IBackupAgent.Stub.asInterface(mPmAgent.onBind()),
-                        mNeedFullBackup);
+                initiateOneRestore(omPackage, 0, IBackupAgent.Stub.asInterface(mPmAgent.onBind()));
                 // The PM agent called operationComplete() already, because our invocation
                 // of it is process-local and therefore synchronous.  That means that a
                 // RUNNING_QUEUE message is already enqueued.  Only if we're unable to
@@ -4727,6 +4950,12 @@
 
             // Metadata is intact, so we can now run the restore queue.  If we get here,
             // we have already enqueued the necessary next-step message on the looper.
+            // We've deferred telling the App Widget service that we might be replacing
+            // the widget environment with something else, but now we know we've got
+            // data coming, so we do it here.
+            if (mIsSystemRestore) {
+                AppWidgetBackupBridge.restoreStarting(UserHandle.USER_OWNER);
+            }
         }
 
         void restoreNextAgent() {
@@ -4835,7 +5064,7 @@
 
                 // And then finally start the restore on this agent
                 try {
-                    initiateOneRestore(packageInfo, metaInfo.versionCode, agent, mNeedFullBackup);
+                    initiateOneRestore(packageInfo, metaInfo.versionCode, agent);
                     ++mCount;
                 } catch (Exception e) {
                     Slog.e(TAG, "Error when attempting restore: " + e.toString());
@@ -4889,6 +5118,9 @@
             mBackupHandler.sendEmptyMessageDelayed(MSG_RESTORE_TIMEOUT,
                     TIMEOUT_RESTORE_INTERVAL);
 
+            // Kick off any work that may be needed regarding app widget restores
+            AppWidgetBackupBridge.restoreFinished(UserHandle.USER_OWNER);
+
             // done; we can finally release the wakelock
             Slog.i(TAG, "Restore complete.");
             mWakelock.release();
@@ -4896,43 +5128,92 @@
 
         // Call asynchronously into the app, passing it the restore data.  The next step
         // after this is always a callback, either operationComplete() or handleTimeout().
-        void initiateOneRestore(PackageInfo app, int appVersionCode, IBackupAgent agent,
-                boolean needFullBackup) {
+        void initiateOneRestore(PackageInfo app, int appVersionCode, IBackupAgent agent) {
             mCurrentPackage = app;
+            mWidgetData = null;
             final String packageName = app.packageName;
 
             if (DEBUG) Slog.d(TAG, "initiateOneRestore packageName=" + packageName);
 
             // !!! TODO: get the dirs from the transport
             mBackupDataName = new File(mDataDir, packageName + ".restore");
+            mStageName = new File(mDataDir, packageName + ".stage");
             mNewStateName = new File(mStateDir, packageName + ".new");
             mSavedStateName = new File(mStateDir, packageName);
 
+            // don't stage the 'android' package where the wallpaper data lives.  this is
+            // an optimization: we know there's no widget data hosted/published by that
+            // package, and this way we avoid doing a spurious copy of MB-sized wallpaper
+            // data following the download.
+            boolean staging = !packageName.equals("android");
+            ParcelFileDescriptor stage;
+            File downloadFile = (staging) ? mStageName : mBackupDataName;
+
             final int token = generateToken();
             try {
                 // Run the transport's restore pass
-                mBackupData = ParcelFileDescriptor.open(mBackupDataName,
+                stage = ParcelFileDescriptor.open(downloadFile,
                             ParcelFileDescriptor.MODE_READ_WRITE |
                             ParcelFileDescriptor.MODE_CREATE |
                             ParcelFileDescriptor.MODE_TRUNCATE);
 
                 if (!SELinux.restorecon(mBackupDataName)) {
-                    Slog.e(TAG, "SElinux restorecon failed for " + mBackupDataName);
+                    Slog.e(TAG, "SElinux restorecon failed for " + downloadFile);
                 }
 
-                if (mTransport.getRestoreData(mBackupData) != BackupConstants.TRANSPORT_OK) {
+                if (mTransport.getRestoreData(stage) != BackupConstants.TRANSPORT_OK) {
                     // Transport-level failure, so we wind everything up and
                     // terminate the restore operation.
                     Slog.e(TAG, "Error getting restore data for " + packageName);
                     EventLog.writeEvent(EventLogTags.RESTORE_TRANSPORT_FAILURE);
-                    mBackupData.close();
-                    mBackupDataName.delete();
+                    stage.close();
+                    downloadFile.delete();
                     executeNextState(RestoreState.FINAL);
                     return;
                 }
 
+                // We have the data from the transport. Now we extract and strip
+                // any per-package metadata (typically widget-related information)
+                // if appropriate
+                if (staging) {
+                    stage.close();
+                    stage = ParcelFileDescriptor.open(downloadFile,
+                            ParcelFileDescriptor.MODE_READ_ONLY);
+
+                    mBackupData = ParcelFileDescriptor.open(mBackupDataName,
+                            ParcelFileDescriptor.MODE_READ_WRITE |
+                            ParcelFileDescriptor.MODE_CREATE |
+                            ParcelFileDescriptor.MODE_TRUNCATE);
+
+                    BackupDataInput in = new BackupDataInput(stage.getFileDescriptor());
+                    BackupDataOutput out = new BackupDataOutput(mBackupData.getFileDescriptor());
+                    byte[] buffer = new byte[8192]; // will grow when needed
+                    while (in.readNextHeader()) {
+                        final String key = in.getKey();
+                        final int size = in.getDataSize();
+
+                        // is this a special key?
+                        if (key.equals(KEY_WIDGET_STATE)) {
+                            if (DEBUG) {
+                                Slog.i(TAG, "Restoring widget state for " + packageName);
+                            }
+                            mWidgetData = new byte[size];
+                            in.readEntityData(mWidgetData, 0, size);
+                        } else {
+                            if (size > buffer.length) {
+                                buffer = new byte[size];
+                            }
+                            in.readEntityData(buffer, 0, size);
+                            out.writeEntityHeader(key, size);
+                            out.writeEntityData(buffer, size);
+                        }
+                    }
+
+                    mBackupData.close();
+                }
+
                 // Okay, we have the data.  Now have the agent do the restore.
-                mBackupData.close();
+                stage.close();
                 mBackupData = ParcelFileDescriptor.open(mBackupDataName,
                             ParcelFileDescriptor.MODE_READ_ONLY);
 
@@ -4943,7 +5224,8 @@
 
                 // Kick off the restore, checking for hung agents
                 prepareOperationTimeout(token, TIMEOUT_RESTORE_INTERVAL, this);
-                agent.doRestore(mBackupData, appVersionCode, mNewState, token, mBackupManagerBinder);
+                agent.doRestore(mBackupData, appVersionCode, mNewState,
+                        token, mBackupManagerBinder);
             } catch (Exception e) {
                 Slog.e(TAG, "Unable to call app for restore: " + packageName, e);
                 EventLog.writeEvent(EventLogTags.RESTORE_AGENT_FAILURE, packageName, e.toString());
@@ -4966,6 +5248,7 @@
 
         void agentCleanup() {
             mBackupDataName.delete();
+            mStageName.delete();
             try { if (mBackupData != null) mBackupData.close(); } catch (IOException e) {}
             try { if (mNewState != null) mNewState.close(); } catch (IOException e) {}
             mBackupData = mNewState = null;
@@ -5024,9 +5307,17 @@
         public void operationComplete() {
             int size = (int) mBackupDataName.length();
             EventLog.writeEvent(EventLogTags.RESTORE_PACKAGE, mCurrentPackage.packageName, size);
+
             // Just go back to running the restore queue
             agentCleanup();
 
+            // If there was widget state associated with this app, get the OS to
+            // incorporate it into current bookeeping and then pass that along to
+            // the app as part of the restore operation.
+            if (mWidgetData != null) {
+                restoreWidgetData(mCurrentPackage.packageName, mWidgetData);
+            }
+
             executeNextState(RestoreState.RUNNING_QUEUE);
         }
 
@@ -5050,6 +5341,12 @@
         }
     }
 
+    // Used by both incremental and full restore
+    void restoreWidgetData(String packageName, byte[] widgetData) {
+        // Apply the restored widget state and generate the ID update for the app
+        AppWidgetBackupBridge.restoreWidgetState(packageName, widgetData, UserHandle.USER_OWNER);
+    }
+
     class PerformClearTask implements Runnable {
         IBackupTransport mTransport;
         PackageInfo mPackage;
@@ -5345,8 +5642,9 @@
     // Run a *full* backup pass for the given package, writing the resulting data stream
     // to the supplied file descriptor.  This method is synchronous and does not return
     // to the caller until the backup has been completed.
+    @Override
     public void fullBackup(ParcelFileDescriptor fd, boolean includeApks,
-            boolean includeObbs, boolean includeShared,
+            boolean includeObbs, boolean includeShared, boolean doWidgets,
             boolean doAllApps, boolean includeSystem, String[] pkgList) {
         mContext.enforceCallingPermission(android.Manifest.permission.BACKUP, "fullBackup");
 
@@ -5382,7 +5680,7 @@
             Slog.i(TAG, "Beginning full backup...");
 
             FullBackupParams params = new FullBackupParams(fd, includeApks, includeObbs,
-                    includeShared, doAllApps, includeSystem, pkgList);
+                    includeShared, doWidgets, doAllApps, includeSystem, pkgList);
             final int token = generateToken();
             synchronized (mFullConfirmations) {
                 mFullConfirmations.put(token, params);
@@ -5839,7 +6137,7 @@
                 mWakelock.acquire();
                 Message msg = mBackupHandler.obtainMessage(MSG_RUN_RESTORE);
                 msg.obj = new RestoreParams(transport, dirName, null,
-                        restoreSet, pkg, token, true);
+                        restoreSet, pkg, token);
                 mBackupHandler.sendMessage(msg);
             } catch (RemoteException e) {
                 // Binding to the transport broke; back off and proceed with the installation.
@@ -6020,7 +6318,7 @@
                         mWakelock.acquire();
                         Message msg = mBackupHandler.obtainMessage(MSG_RUN_RESTORE);
                         msg.obj = new RestoreParams(mRestoreTransport, dirName,
-                                observer, token, true);
+                                observer, token);
                         mBackupHandler.sendMessage(msg);
                         Binder.restoreCallingIdentity(oldId);
                         return 0;
@@ -6032,6 +6330,7 @@
             return -1;
         }
 
+        // Restores of more than a single package are treated as 'system' restores
         public synchronized int restoreSome(long token, IRestoreObserver observer,
                 String[] packages) {
             mContext.enforceCallingOrSelfPermission(android.Manifest.permission.BACKUP,
@@ -6090,7 +6389,7 @@
                         mWakelock.acquire();
                         Message msg = mBackupHandler.obtainMessage(MSG_RUN_RESTORE);
                         msg.obj = new RestoreParams(mRestoreTransport, dirName, observer, token,
-                                packages, true);
+                                packages, packages.length > 1);
                         mBackupHandler.sendMessage(msg);
                         Binder.restoreCallingIdentity(oldId);
                         return 0;
@@ -6169,7 +6468,7 @@
             mWakelock.acquire();
             Message msg = mBackupHandler.obtainMessage(MSG_RUN_RESTORE);
             msg.obj = new RestoreParams(mRestoreTransport, dirName,
-                    observer, token, app, 0, false);
+                    observer, token, app, 0);
             mBackupHandler.sendMessage(msg);
             Binder.restoreCallingIdentity(oldId);
             return 0;