diff --git a/services/appwidget/java/com/android/server/appwidget/AppWidgetServiceImpl.java b/services/appwidget/java/com/android/server/appwidget/AppWidgetServiceImpl.java
index 5567707..d7649dc 100644
--- a/services/appwidget/java/com/android/server/appwidget/AppWidgetServiceImpl.java
+++ b/services/appwidget/java/com/android/server/appwidget/AppWidgetServiceImpl.java
@@ -17,6 +17,7 @@
 package com.android.server.appwidget;
 
 import static android.appwidget.flags.Flags.removeAppWidgetServiceIoFromCriticalPath;
+import static android.appwidget.flags.Flags.supportResumeRestoreAfterReboot;
 import static android.content.Context.KEYGUARD_SERVICE;
 import static android.content.Intent.FLAG_ACTIVITY_EXCLUDE_FROM_RECENTS;
 import static android.content.Intent.FLAG_ACTIVITY_NEW_TASK;
@@ -166,6 +167,8 @@
 import java.util.Objects;
 import java.util.Set;
 import java.util.concurrent.atomic.AtomicLong;
+import java.util.function.BiConsumer;
+import java.util.function.Function;
 import java.util.function.LongSupplier;
 
 class AppWidgetServiceImpl extends IAppWidgetService.Stub implements WidgetBackupProvider,
@@ -457,7 +460,7 @@
                 break;
             case Intent.ACTION_EXTERNAL_APPLICATIONS_AVAILABLE:
                 added = true;
-                // Follow through
+                // fall through
             case Intent.ACTION_EXTERNAL_APPLICATIONS_UNAVAILABLE:
                 pkgList = intent.getStringArrayExtra(Intent.EXTRA_CHANGED_PACKAGE_LIST);
                 break;
@@ -3571,6 +3574,13 @@
             }
 
             out.endTag(null, "gs");
+
+            if (supportResumeRestoreAfterReboot()
+                    && mBackupRestoreController.requiresPersistenceLocked()) {
+                AppWidgetXmlUtil.writeBackupRestoreControllerState(
+                        out, mBackupRestoreController.getStateLocked(userId));
+            }
+
             out.endDocument();
             return true;
         } catch (IOException e) {
@@ -3717,6 +3727,32 @@
                         LoadedWidgetState loadedWidgets = new LoadedWidgetState(widget,
                                 hostTag, providerTag);
                         outLoadedWidgets.add(loadedWidgets);
+                    } else if (supportResumeRestoreAfterReboot()
+                            && AppWidgetXmlUtil.TAG_BACKUP_RESTORE_CONTROLLER_STATE.equals(tag)) {
+                        final BackupRestoreController.State s =
+                                AppWidgetXmlUtil.readBackupRestoreControllerState(parser);
+                        if (s == null) {
+                            continue;
+                        }
+                        final Set<String> prunedAppsInFile = s.getPrunedApps();
+                        if (prunedAppsInFile != null) {
+                            final Set<String> prunedAppsInMemory = mBackupRestoreController
+                                    .mPrunedAppsPerUser.get(userId);
+                            if (prunedAppsInMemory == null) {
+                                mBackupRestoreController.mPrunedAppsPerUser.put(
+                                        userId, prunedAppsInFile);
+                            } else {
+                                prunedAppsInMemory.addAll(prunedAppsInFile);
+                            }
+                        }
+                        loadUpdateRecords(s.getUpdatesByProvider(),
+                                this::findProviderByTag,
+                                mBackupRestoreController.mUpdatesByProvider::get,
+                                mBackupRestoreController.mUpdatesByProvider::put);
+                        loadUpdateRecords(s.getUpdatesByHost(),
+                                this::findHostByTag,
+                                mBackupRestoreController.mUpdatesByHost::get,
+                                mBackupRestoreController.mUpdatesByHost::put);
                     }
                 }
             } while (type != XmlPullParser.END_DOCUMENT);
@@ -3732,6 +3768,36 @@
         return version;
     }
 
+    private <T> void loadUpdateRecords(
+            @Nullable final SparseArray<
+                    List<BackupRestoreController.RestoreUpdateRecord>> updatesOnFile,
+            @NonNull final Function<Integer, T> findKeyByTagCb,
+            @NonNull final Function<T, List<
+                    BackupRestoreController.RestoreUpdateRecord>> findRecordsCb,
+            @NonNull final BiConsumer<T, List<
+                    BackupRestoreController.RestoreUpdateRecord>> newRecordsCb) {
+        if (updatesOnFile == null) {
+            return;
+        }
+        for (int i = 0; i < updatesOnFile.size(); i++) {
+            final int tag = updatesOnFile.keyAt(i);
+            final List<
+                    BackupRestoreController.RestoreUpdateRecord
+                    > recordsOnFile = updatesOnFile.get(tag);
+            if (recordsOnFile == null || recordsOnFile.isEmpty()) {
+                continue;
+            }
+            final T key = findKeyByTagCb.apply(tag);
+            final List<BackupRestoreController.RestoreUpdateRecord> recordsInMemory =
+                    findRecordsCb.apply(key);
+            if (recordsInMemory != null) {
+                recordsInMemory.addAll(recordsOnFile);
+            } else  {
+                newRecordsCb.accept(key, recordsOnFile);
+            }
+        }
+    }
+
     private void performUpgradeLocked(int fromVersion) {
         if (fromVersion < CURRENT_VERSION) {
             Slog.v(TAG, "Upgrading widget database from " + fromVersion + " to "
@@ -4674,7 +4740,7 @@
         }
     }
 
-    private static final class Provider {
+    static final class Provider {
 
         ProviderId id;
         AppWidgetProviderInfo info;
@@ -4931,7 +4997,7 @@
         }
     }
 
-    private static final class Host {
+    static final class Host {
         HostId id;
         ArrayList<Widget> widgets = new ArrayList<>();
         IAppWidgetHost callbacks;
@@ -5250,10 +5316,10 @@
     /**
      * This class encapsulates the backup and restore logic for a user group state.
      */
-    private final class BackupRestoreController {
+    final class BackupRestoreController {
         private static final String TAG = "BackupRestoreController";
 
-        private static final boolean DEBUG = true;
+        private static final boolean DEBUG = AppWidgetServiceImpl.DEBUG;
 
         // Version of backed-up widget state.
         private static final int WIDGET_STATE_VERSION = 2;
@@ -5262,16 +5328,31 @@
         // 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.
+        @GuardedBy("AppWidgetServiceImpl.this.mLock")
         private final SparseArray<Set<String>> mPrunedAppsPerUser = new SparseArray<>();
 
-        private final HashMap<Provider, ArrayList<RestoreUpdateRecord>> mUpdatesByProvider =
-                new HashMap<>();
-        private final HashMap<Host, ArrayList<RestoreUpdateRecord>> mUpdatesByHost =
-                new HashMap<>();
+        @GuardedBy("AppWidgetServiceImpl.this.mLock")
+        final Map<Provider, List<RestoreUpdateRecord>> mUpdatesByProvider =
+                new ArrayMap<>();
 
-        @GuardedBy("mLock")
+        @GuardedBy("AppWidgetServiceImpl.this.mLock")
+        private final Map<Host, List<RestoreUpdateRecord>> mUpdatesByHost =
+                new ArrayMap<>();
+
+        @GuardedBy("AppWidgetServiceImpl.this.mLock")
         private boolean mHasSystemRestoreFinished;
 
+        @GuardedBy("AppWidgetServiceImpl.this.mLock")
+        public boolean requiresPersistenceLocked() {
+            if (mHasSystemRestoreFinished) {
+                // No need to persist intermediate states if system restore is already finished.
+                return false;
+            }
+            // If either of the internal states is non-empty, then we need to persist that
+            return !(mPrunedAppsPerUser.size() == 0 && mUpdatesByProvider.isEmpty()
+                    && mUpdatesByHost.isEmpty());
+        }
+
         public List<String> getWidgetParticipants(int userId) {
             if (DEBUG) {
                 Slog.i(TAG, "Getting widget participants for user: " + userId);
@@ -5436,7 +5517,7 @@
                                 // If there's no live entry for this provider, add an inactive one
                                 // so that widget IDs referring to them can be properly allocated
 
-                                // Backup and resotre only for the parent profile.
+                                // Backup and restore only for the parent profile.
                                 ComponentName componentName = new ComponentName(pkg, cl);
 
                                 Provider p = findProviderLocked(componentName, userId);
@@ -5579,9 +5660,9 @@
 
             final UserHandle userHandle = new UserHandle(userId);
             // Build the providers' broadcasts and send them off
-            Set<Map.Entry<Provider, ArrayList<RestoreUpdateRecord>>> providerEntries
+            Set<Map.Entry<Provider, List<RestoreUpdateRecord>>> providerEntries
                     = mUpdatesByProvider.entrySet();
-            for (Map.Entry<Provider, ArrayList<RestoreUpdateRecord>> e : providerEntries) {
+            for (Map.Entry<Provider, List<RestoreUpdateRecord>> e : providerEntries) {
                 // For each provider there's a list of affected IDs
                 Provider provider = e.getKey();
                 if (provider.zombie) {
@@ -5589,7 +5670,7 @@
                     // We'll be called again when the provider is installed.
                     continue;
                 }
-                ArrayList<RestoreUpdateRecord> updates = e.getValue();
+                List<RestoreUpdateRecord> updates = e.getValue();
                 final int pending = countPendingUpdates(updates);
                 if (DEBUG) {
                     Slog.i(TAG, "Provider " + provider + " pending: " + pending);
@@ -5618,12 +5699,12 @@
             }
 
             // same thing per host
-            Set<Map.Entry<Host, ArrayList<RestoreUpdateRecord>>> hostEntries
+            Set<Map.Entry<Host, List<RestoreUpdateRecord>>> hostEntries
                     = mUpdatesByHost.entrySet();
-            for (Map.Entry<Host, ArrayList<RestoreUpdateRecord>> e : hostEntries) {
+            for (Map.Entry<Host, List<RestoreUpdateRecord>> e : hostEntries) {
                 Host host = e.getKey();
                 if (host.id.uid != UNKNOWN_UID) {
-                    ArrayList<RestoreUpdateRecord> updates = e.getValue();
+                    List<RestoreUpdateRecord> updates = e.getValue();
                     final int pending = countPendingUpdates(updates);
                     if (DEBUG) {
                         Slog.i(TAG, "Host " + host + " pending: " + pending);
@@ -5714,8 +5795,9 @@
             return false;
         }
 
+        @GuardedBy("mLock")
         private void stashProviderRestoreUpdateLocked(Provider provider, int oldId, int newId) {
-            ArrayList<RestoreUpdateRecord> r = mUpdatesByProvider.get(provider);
+            List<RestoreUpdateRecord> r = mUpdatesByProvider.get(provider);
             if (r == null) {
                 r = new ArrayList<>();
                 mUpdatesByProvider.put(provider, r);
@@ -5732,7 +5814,7 @@
             r.add(new RestoreUpdateRecord(oldId, newId));
         }
 
-        private boolean alreadyStashed(ArrayList<RestoreUpdateRecord> stash,
+        private boolean alreadyStashed(List<RestoreUpdateRecord> stash,
                 final int oldId, final int newId) {
             final int N = stash.size();
             for (int i = 0; i < N; i++) {
@@ -5744,8 +5826,9 @@
             return false;
         }
 
+        @GuardedBy("mLock")
         private void stashHostRestoreUpdateLocked(Host host, int oldId, int newId) {
-            ArrayList<RestoreUpdateRecord> r = mUpdatesByHost.get(host);
+            List<RestoreUpdateRecord> r = mUpdatesByHost.get(host);
             if (r == null) {
                 r = new ArrayList<>();
                 mUpdatesByHost.put(host, r);
@@ -5835,7 +5918,7 @@
                     || widget.provider.getUserId() == userId);
         }
 
-        private int countPendingUpdates(ArrayList<RestoreUpdateRecord> updates) {
+        private int countPendingUpdates(List<RestoreUpdateRecord> updates) {
             int pending = 0;
             final int N = updates.size();
             for (int i = 0; i < N; i++) {
@@ -5847,9 +5930,28 @@
             return pending;
         }
 
+        @GuardedBy("mLock")
+        @NonNull
+        private State getStateLocked(final int userId) {
+            final Set<String> prunedApps = mPrunedAppsPerUser.get(userId);
+            final SparseArray<List<RestoreUpdateRecord>> updatesByProvider = new SparseArray<>();
+            final SparseArray<List<RestoreUpdateRecord>> updatesByHost = new SparseArray<>();
+            mUpdatesByProvider.forEach((p, updates) -> {
+                if (p.getUserId() == userId) {
+                    updatesByProvider.put(p.tag, new ArrayList<>(updates));
+                }
+            });
+            mUpdatesByHost.forEach((h, updates) -> {
+                if (h.getUserId() == userId) {
+                    updatesByHost.put(h.tag, new ArrayList<>(updates));
+                }
+            });
+            return new State(prunedApps, updatesByProvider, updatesByHost);
+        }
+
         // Accumulate a list of updates that affect the given provider for a final
         // coalesced notification broadcast once restore is over.
-        private class RestoreUpdateRecord {
+        static class RestoreUpdateRecord {
             public int oldId;
             public int newId;
             public boolean notified;
@@ -5860,6 +5962,45 @@
                 notified = false;
             }
         }
+
+        static final class State {
+            // 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.
+            @Nullable
+            private final Set<String> mPrunedApps;
+
+            @Nullable
+            private final SparseArray<List<RestoreUpdateRecord>> mUpdatesByProvider;
+
+            @Nullable
+            private final SparseArray<List<RestoreUpdateRecord>> mUpdatesByHost;
+
+            State(
+                    @Nullable final Set<String> prunedApps,
+                    @Nullable final SparseArray<List<RestoreUpdateRecord>> updatesByProvider,
+                    @Nullable final SparseArray<List<RestoreUpdateRecord>> updatesByHost) {
+                mPrunedApps = prunedApps;
+                mUpdatesByProvider = updatesByProvider;
+                mUpdatesByHost = updatesByHost;
+            }
+
+            @Nullable
+            Set<String> getPrunedApps() {
+                return mPrunedApps;
+            }
+
+            @Nullable
+            SparseArray<List<BackupRestoreController.RestoreUpdateRecord>> getUpdatesByProvider() {
+                return mUpdatesByProvider;
+            }
+
+            @Nullable
+            SparseArray<List<BackupRestoreController.RestoreUpdateRecord>> getUpdatesByHost() {
+                return mUpdatesByHost;
+            }
+        }
     }
 
     private class AppWidgetManagerLocal extends AppWidgetManagerInternal {
diff --git a/services/appwidget/java/com/android/server/appwidget/AppWidgetXmlUtil.java b/services/appwidget/java/com/android/server/appwidget/AppWidgetXmlUtil.java
index d781cd8..ce9130a 100644
--- a/services/appwidget/java/com/android/server/appwidget/AppWidgetXmlUtil.java
+++ b/services/appwidget/java/com/android/server/appwidget/AppWidgetXmlUtil.java
@@ -22,17 +22,24 @@
 import android.content.ComponentName;
 import android.os.Build;
 import android.text.TextUtils;
+import android.util.ArraySet;
+import android.util.Log;
 import android.util.SizeF;
 import android.util.Slog;
+import android.util.SparseArray;
 
 import com.android.modules.utils.TypedXmlPullParser;
 import com.android.modules.utils.TypedXmlSerializer;
 
+import org.xmlpull.v1.XmlPullParser;
+import org.xmlpull.v1.XmlPullParserException;
+
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.List;
 import java.util.Objects;
+import java.util.Set;
 import java.util.stream.Collectors;
 
 /**
@@ -65,6 +72,16 @@
     private static final String ATTR_DESCRIPTION_RES = "description_res";
     private static final String ATTR_PROVIDER_INHERITANCE = "provider_inheritance";
     private static final String ATTR_OS_FINGERPRINT = "os_fingerprint";
+    static final String TAG_BACKUP_RESTORE_CONTROLLER_STATE = "br";
+    private static final String TAG_PRUNED_APPS = "pruned_apps";
+    private static final String ATTR_TAG = "tag";
+    private static final String ATTR_PACKAGE_NAMES = "pkgs";
+    private static final String TAG_PROVIDER_UPDATES = "provider_updates";
+    private static final String TAG_HOST_UPDATES = "host_updates";
+    private static final String TAG_RECORD = "record";
+    private static final String ATTR_OLD_ID = "old_id";
+    private static final String ATTR_NEW_ID = "new_id";
+    private static final String ATTR_NOTIFIED = "notified";
     private static final String SIZE_SEPARATOR = ",";
 
     /**
@@ -165,4 +182,168 @@
             return null;
         }
     }
+
+    /**
+     * Persists {@link AppWidgetServiceImpl.BackupRestoreController.State} to disk as XML.
+     * See {@link #readBackupRestoreControllerState(TypedXmlPullParser)} for example XML.
+     *
+     * @param out XML serializer
+     * @param state {@link AppWidgetServiceImpl.BackupRestoreController.State} of
+     *      intermediate states to be persisted as xml to resume restore after reboot.
+     */
+    static void writeBackupRestoreControllerState(
+            @NonNull final TypedXmlSerializer out,
+            @NonNull final AppWidgetServiceImpl.BackupRestoreController.State state)
+            throws IOException {
+        Objects.requireNonNull(out);
+        Objects.requireNonNull(state);
+        out.startTag(null, TAG_BACKUP_RESTORE_CONTROLLER_STATE);
+        final Set<String> prunedApps = state.getPrunedApps();
+        if (prunedApps != null && !prunedApps.isEmpty()) {
+            out.startTag(null, TAG_PRUNED_APPS);
+            out.attribute(null, ATTR_PACKAGE_NAMES, String.join(",", prunedApps));
+            out.endTag(null, TAG_PRUNED_APPS);
+        }
+        final SparseArray<List<AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord>>
+                updatesByProvider = state.getUpdatesByProvider();
+        if (updatesByProvider != null) {
+            writeUpdateRecords(out, TAG_PROVIDER_UPDATES, updatesByProvider);
+        }
+        final SparseArray<List<AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord>>
+                updatesByHost = state.getUpdatesByHost();
+        if (updatesByHost != null) {
+            writeUpdateRecords(out, TAG_HOST_UPDATES, updatesByHost);
+        }
+        out.endTag(null, TAG_BACKUP_RESTORE_CONTROLLER_STATE);
+    }
+
+    private static void writeUpdateRecords(@NonNull final TypedXmlSerializer out,
+            @NonNull final String outerTag, @NonNull final SparseArray<List<
+                    AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord>> records)
+            throws IOException {
+        for (int i = 0; i < records.size(); i++) {
+            final int tag = records.keyAt(i);
+            out.startTag(null, outerTag);
+            out.attributeInt(null, ATTR_TAG, tag);
+            final List<AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord> entries =
+                    records.get(tag);
+            for (AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord entry : entries) {
+                out.startTag(null, TAG_RECORD);
+                out.attributeInt(null, ATTR_OLD_ID, entry.oldId);
+                out.attributeInt(null, ATTR_NEW_ID, entry.newId);
+                out.attributeBoolean(null, ATTR_NOTIFIED, entry.notified);
+                out.endTag(null, TAG_RECORD);
+            }
+            out.endTag(null, outerTag);
+        }
+    }
+
+    /**
+     * Parses {@link AppWidgetServiceImpl.BackupRestoreController.State} from xml.
+     *
+     * <pre>
+     * {@code
+     *     <?xml version="1.0"?>
+     *     <br>
+     *         <pruned_apps pkgs="com.example.app1,com.example.app2,com.example.app3" />
+     *         <provider_updates tag="0">
+     *             <record old_id="10" new_id="0" notified="false" />
+     *         </provider_updates>
+     *         <provider_updates tag="1">
+     *             <record old_id="9" new_id="1" notified="true" />
+     *         </provider_updates>
+     *         <provider_updates tag="2">
+     *             <record old_id="8" new_id="2" notified="false" />
+     *         </provider_updates>
+     *         <host_updates tag="0">
+     *             <record old_id="10" new_id="0" notified="false" />
+     *         </host_updates>
+     *         <host_updates tag="1">
+     *             <record old_id="9" new_id="1" notified="true" />
+     *         </host_updates>
+     *         <host_updates tag="2">
+     *             <record old_id="8" new_id="2" notified="false" />
+     *         </host_updates>
+     *     </br>
+     * }
+     * </pre>
+     *
+     * @param parser XML parser
+     * @return {@link AppWidgetServiceImpl.BackupRestoreController.State} of intermediate states
+     * in {@link AppWidgetServiceImpl.BackupRestoreController}, so that backup & restore can be
+     * resumed after reboot.
+     */
+    @Nullable
+    static AppWidgetServiceImpl.BackupRestoreController.State
+            readBackupRestoreControllerState(@NonNull final TypedXmlPullParser parser) {
+        Objects.requireNonNull(parser);
+        int type;
+        String tag = null;
+        final Set<String> prunedApps = new ArraySet<>(1);
+        final SparseArray<List<AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord>>
+                updatesByProviders = new SparseArray<>();
+        final SparseArray<List<AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord>>
+                updatesByHosts = new SparseArray<>();
+
+        try {
+            do {
+                type = parser.next();
+                if (type != XmlPullParser.START_TAG) {
+                    continue;
+                }
+                tag = parser.getName();
+                switch (tag) {
+                    case TAG_PRUNED_APPS:
+                        final String packages =
+                                parser.getAttributeValue(null, ATTR_PACKAGE_NAMES);
+                        prunedApps.addAll(Arrays.asList(packages.split(",")));
+                        break;
+                    case TAG_PROVIDER_UPDATES:
+                        updatesByProviders.put(parser.getAttributeInt(null, ATTR_TAG),
+                                parseRestoreUpdateRecords(parser));
+                        break;
+                    case TAG_HOST_UPDATES:
+                        updatesByHosts.put(parser.getAttributeInt(null, ATTR_TAG),
+                                parseRestoreUpdateRecords(parser));
+                        break;
+                    default:
+                        break;
+                }
+            } while (type != XmlPullParser.END_DOCUMENT
+                    && (!TAG_BACKUP_RESTORE_CONTROLLER_STATE.equals(tag)
+                            || type != XmlPullParser.END_TAG));
+        } catch (IOException | XmlPullParserException e) {
+            Log.e(TAG, "error parsing state", e);
+            return null;
+        }
+        return new AppWidgetServiceImpl.BackupRestoreController.State(
+                prunedApps, updatesByProviders, updatesByHosts);
+    }
+
+    @NonNull
+    private static List<
+            AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord
+            > parseRestoreUpdateRecords(@NonNull final TypedXmlPullParser parser)
+            throws XmlPullParserException, IOException {
+        int type;
+        String tag;
+        final List<AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord> ret =
+                new ArrayList<>();
+        do {
+            type = parser.next();
+            tag = parser.getName();
+            if (tag.equals(TAG_RECORD) && type == XmlPullParser.START_TAG) {
+                final int oldId = parser.getAttributeInt(null, ATTR_OLD_ID);
+                final int newId = parser.getAttributeInt(null, ATTR_NEW_ID);
+                final boolean notified = parser.getAttributeBoolean(
+                        null, ATTR_NOTIFIED);
+                final AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord record =
+                        new AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord(
+                                oldId, newId);
+                record.notified = notified;
+                ret.add(record);
+            }
+        } while (tag.equals(TAG_RECORD));
+        return ret;
+    }
 }
diff --git a/services/tests/servicestests/src/com/android/server/appwidget/AppWidgetServiceImplTest.java b/services/tests/servicestests/src/com/android/server/appwidget/AppWidgetServiceImplTest.java
index 8a7815e..c34e28f 100644
--- a/services/tests/servicestests/src/com/android/server/appwidget/AppWidgetServiceImplTest.java
+++ b/services/tests/servicestests/src/com/android/server/appwidget/AppWidgetServiceImplTest.java
@@ -47,7 +47,9 @@
 import android.os.Handler;
 import android.os.UserHandle;
 import android.test.InstrumentationTestCase;
+import android.util.ArraySet;
 import android.util.AtomicFile;
+import android.util.SparseArray;
 import android.util.Xml;
 import android.widget.RemoteViews;
 
@@ -67,10 +69,12 @@
 import java.io.FileInputStream;
 import java.io.FileOutputStream;
 import java.io.IOException;
+import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Objects;
 import java.util.Random;
+import java.util.Set;
 import java.util.concurrent.CountDownLatch;
 
 /**
@@ -388,6 +392,93 @@
         assertThat(target.previewLayout).isEqualTo(original.previewLayout);
     }
 
+    public void testBackupRestoreControllerStatePersistence() throws IOException {
+        // Setup mock data
+        final Set<String> mockPrunedApps = getMockPrunedApps();
+        final SparseArray<
+                List<AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord>
+                > mockUpdatesByProvider = getMockUpdates();
+        final  SparseArray<
+                List<AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord>
+                > mockUpdatesByHost = getMockUpdates();
+        final AppWidgetServiceImpl.BackupRestoreController.State state =
+                new AppWidgetServiceImpl.BackupRestoreController.State(
+                        mockPrunedApps, mockUpdatesByProvider, mockUpdatesByHost);
+
+        final File file = new File(mTestContext.getDataDir(), "state.xml");
+        saveBackupRestoreControllerState(file, state);
+        final AppWidgetServiceImpl.BackupRestoreController.State target =
+                loadStateLocked(file);
+        assertNotNull(target);
+        final SparseArray<List<AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord>>
+                actualUpdatesByProvider = target.getUpdatesByProvider();
+        assertNotNull(actualUpdatesByProvider);
+        final SparseArray<List<AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord>>
+                actualUpdatesByHost = target.getUpdatesByHost();
+        assertNotNull(actualUpdatesByHost);
+
+        assertEquals(mockPrunedApps, target.getPrunedApps());
+        for (int i = 0; i < mockUpdatesByProvider.size(); i++) {
+            final int key = mockUpdatesByProvider.keyAt(i);
+            verifyRestoreUpdateRecord(
+                    actualUpdatesByProvider.get(key), mockUpdatesByProvider.get(key));
+        }
+        for (int i = 0; i < mockUpdatesByHost.size(); i++) {
+            final int key = mockUpdatesByHost.keyAt(i);
+            verifyRestoreUpdateRecord(
+                    actualUpdatesByHost.get(key), mockUpdatesByHost.get(key));
+        }
+    }
+
+    private void verifyRestoreUpdateRecord(
+            @NonNull final List<AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord>
+                    actualUpdates,
+            @NonNull final List<AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord>
+                    expectedUpdates) {
+        assertEquals(expectedUpdates.size(), actualUpdates.size());
+        for (int i = 0; i < expectedUpdates.size(); i++) {
+            final AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord expected =
+                    expectedUpdates.get(i);
+            final AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord actual =
+                    actualUpdates.get(i);
+            assertEquals(expected.oldId, actual.oldId);
+            assertEquals(expected.newId, actual.newId);
+            assertEquals(expected.notified, actual.notified);
+        }
+    }
+
+    @NonNull
+    private static Set<String> getMockPrunedApps() {
+        final Set<String> mockPrunedApps = new ArraySet<>(10);
+        for (int i = 0; i < 10; i++) {
+            mockPrunedApps.add("com.example.app" + i);
+        }
+        return mockPrunedApps;
+    }
+
+    @NonNull
+    private static SparseArray<
+            List<AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord>
+            > getMockUpdates() {
+        final SparseArray<List<
+                AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord>> ret =
+                new SparseArray<>(4);
+        ret.put(0, new ArrayList<>());
+        for (int i = 0; i < 5; i++) {
+            final AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord record =
+                    new AppWidgetServiceImpl.BackupRestoreController.RestoreUpdateRecord(
+                            5 - i, i);
+            record.notified = (i % 2 == 1);
+            final int key = (i < 3) ? 1 : 2;
+            if (!ret.contains(key)) {
+                ret.put(key, new ArrayList<>());
+            }
+            ret.get(key).add(record);
+        }
+        ret.put(3, new ArrayList<>());
+        return ret;
+    }
+
     private int setupHostAndWidget() {
         List<PendingHostUpdate> updates = mService.startListening(
                 mMockHost, mPkgName, HOST_ID, new int[0]).getList();
@@ -418,6 +509,40 @@
         return mTestContext.getResources().getInteger(resId);
     }
 
+    private static void saveBackupRestoreControllerState(
+            @NonNull final File dst,
+            @Nullable final AppWidgetServiceImpl.BackupRestoreController.State state)
+            throws IOException {
+        Objects.requireNonNull(dst);
+        if (state == null) {
+            return;
+        }
+        final AtomicFile file = new AtomicFile(dst);
+        final FileOutputStream stream = file.startWrite();
+        final TypedXmlSerializer out = Xml.resolveSerializer(stream);
+        out.startDocument(null, true);
+        AppWidgetXmlUtil.writeBackupRestoreControllerState(out, state);
+        out.endDocument();
+        file.finishWrite(stream);
+    }
+
+    private static AppWidgetServiceImpl.BackupRestoreController.State loadStateLocked(
+            @NonNull final File dst) {
+        Objects.requireNonNull(dst);
+        final AtomicFile file = new AtomicFile(dst);
+        try (FileInputStream stream = file.openRead()) {
+            final TypedXmlPullParser parser = Xml.resolvePullParser(stream);
+            int type;
+            while ((type = parser.next()) != XmlPullParser.END_DOCUMENT
+                    && type != XmlPullParser.START_TAG) {
+                // drain whitespace, comments, etc.
+            }
+            return AppWidgetXmlUtil.readBackupRestoreControllerState(parser);
+        } catch (IOException | XmlPullParserException e) {
+            return null;
+        }
+    }
+
     private static void saveWidgetProviderInfoLocked(@NonNull final File dst,
             @Nullable final AppWidgetProviderInfo info)
             throws IOException {