xref: /frameworks/base/services/backup/java/com/android/server/backup/BackupManagerService.java

/*
 * Copyright (C) 2009 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.backup;

import android.app.ActivityManagerNative;
import android.app.AlarmManager;
import android.app.AppGlobals;
import android.app.IActivityManager;
import android.app.IApplicationThread;
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.BackupTransport;
import android.app.backup.FullBackup;
import android.app.backup.RestoreDescription;
import android.app.backup.RestoreSet;
import android.app.backup.IBackupManager;
import android.app.backup.IFullBackupRestoreObserver;
import android.app.backup.IRestoreObserver;
import android.app.backup.IRestoreSession;
import android.content.ActivityNotFoundException;
import android.content.BroadcastReceiver;
import android.content.ComponentName;
import android.content.ContentResolver;
import android.content.Context;
import android.content.Intent;
import android.content.IntentFilter;
import android.content.ServiceConnection;
import android.content.pm.ApplicationInfo;
import android.content.pm.IPackageDataObserver;
import android.content.pm.IPackageDeleteObserver;
import android.content.pm.IPackageInstallObserver;
import android.content.pm.IPackageManager;
import android.content.pm.PackageInfo;
import android.content.pm.PackageManager;
import android.content.pm.ResolveInfo;
import android.content.pm.ServiceInfo;
import android.content.pm.Signature;
import android.content.pm.PackageManager.NameNotFoundException;
import android.database.ContentObserver;
import android.net.Uri;
import android.os.Binder;
import android.os.Build;
import android.os.Bundle;
import android.os.Environment;
import android.os.Handler;
import android.os.HandlerThread;
import android.os.IBinder;
import android.os.Looper;
import android.os.Message;
import android.os.ParcelFileDescriptor;
import android.os.PowerManager;
import android.os.Process;
import android.os.RemoteException;
import android.os.SELinux;
import android.os.ServiceManager;
import android.os.SystemClock;
import android.os.UserHandle;
import android.os.WorkSource;
import android.os.Environment.UserEnvironment;
import android.os.storage.IMountService;
import android.os.storage.StorageManager;
import android.provider.Settings;
import android.system.ErrnoException;
import android.system.Os;
import android.util.ArrayMap;
import android.util.AtomicFile;
import android.util.EventLog;
import android.util.Log;
import android.util.Slog;
import android.util.SparseArray;
import android.util.StringBuilderPrinter;

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;
import java.io.EOFException;
import java.io.File;
import java.io.FileDescriptor;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.RandomAccessFile;
import java.security.InvalidAlgorithmParameterException;
import java.security.InvalidKeyException;
import java.security.Key;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.security.spec.InvalidKeySpecException;
import java.security.spec.KeySpec;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
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.Objects;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.zip.Deflater;
import java.util.zip.DeflaterOutputStream;
import java.util.zip.InflaterInputStream;

import javax.crypto.BadPaddingException;
import javax.crypto.Cipher;
import javax.crypto.CipherInputStream;
import javax.crypto.CipherOutputStream;
import javax.crypto.IllegalBlockSizeException;
import javax.crypto.NoSuchPaddingException;
import javax.crypto.SecretKey;
import javax.crypto.SecretKeyFactory;
import javax.crypto.spec.IvParameterSpec;
import javax.crypto.spec.PBEKeySpec;
import javax.crypto.spec.SecretKeySpec;

import libcore.io.IoUtils;

public class BackupManagerService {

    private static final String TAG = "BackupManagerService";
    private static final boolean DEBUG = true;
    private static final boolean MORE_DEBUG = false;
    private static final boolean DEBUG_SCHEDULING = MORE_DEBUG || true;

    // 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_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 SETTINGS_PACKAGE = "com.android.providers.settings";
    static final String SHARED_BACKUP_AGENT_PACKAGE = "com.android.sharedstoragebackup";
    static final String SERVICE_ACTION_TRANSPORT_HOST = "android.backup.TRANSPORT_HOST";

    // How often we perform a backup pass.  Privileged external callers can
    // trigger an immediate pass.
    private static final long BACKUP_INTERVAL = AlarmManager.INTERVAL_HOUR;

    // Random variation in backup scheduling time to avoid server load spikes
    private static final int FUZZ_MILLIS = 5 * 60 * 1000;

    // The amount of time between the initial provisioning of the device and
    // the first backup pass.
    private static final long FIRST_BACKUP_INTERVAL = 12 * AlarmManager.INTERVAL_HOUR;

    // Retry interval for clear/init when the transport is unavailable
    private static final long TRANSPORT_RETRY_INTERVAL = 1 * AlarmManager.INTERVAL_HOUR;

    private static final String RUN_BACKUP_ACTION = "android.app.backup.intent.RUN";
    private static final String RUN_INITIALIZE_ACTION = "android.app.backup.intent.INIT";
    private static final String RUN_CLEAR_ACTION = "android.app.backup.intent.CLEAR";
    private static final int MSG_RUN_BACKUP = 1;
    private static final int MSG_RUN_ADB_BACKUP = 2;
    private static final int MSG_RUN_RESTORE = 3;
    private static final int MSG_RUN_CLEAR = 4;
    private static final int MSG_RUN_INITIALIZE = 5;
    private static final int MSG_RUN_GET_RESTORE_SETS = 6;
    private static final int MSG_TIMEOUT = 7;
    private static final int MSG_RESTORE_TIMEOUT = 8;
    private static final int MSG_FULL_CONFIRMATION_TIMEOUT = 9;
    private static final int MSG_RUN_ADB_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;
    private static final int MSG_RUN_FULL_TRANSPORT_BACKUP = 14;

    // backup task state machine tick
    static final int MSG_BACKUP_RESTORE_STEP = 20;
    static final int MSG_OP_COMPLETE = 21;

    // Timeout interval for deciding that a bind or clear-data has taken too long
    static final long TIMEOUT_INTERVAL = 10 * 1000;

    // Timeout intervals for agent backup & restore operations
    static final long TIMEOUT_BACKUP_INTERVAL = 30 * 1000;
    static final long TIMEOUT_FULL_BACKUP_INTERVAL = 5 * 60 * 1000;
    static final long TIMEOUT_SHARED_BACKUP_INTERVAL = 30 * 60 * 1000;
    static final long TIMEOUT_RESTORE_INTERVAL = 60 * 1000;
    static final long TIMEOUT_RESTORE_FINISHED_INTERVAL = 30 * 1000;

    // User confirmation timeout for a full backup/restore operation.  It's this long in
    // order to give them time to enter the backup password.
    static final long TIMEOUT_FULL_CONFIRMATION = 60 * 1000;

    // How long between attempts to perform a full-data backup of any given app
    static final long MIN_FULL_BACKUP_INTERVAL = 1000 * 60 * 60 * 24; // one day

    Context mContext;
    private PackageManager mPackageManager;
    IPackageManager mPackageManagerBinder;
    private IActivityManager mActivityManager;
    private PowerManager mPowerManager;
    private AlarmManager mAlarmManager;
    private IMountService mMountService;
    IBackupManager mBackupManagerBinder;

    boolean mEnabled;   // access to this is synchronized on 'this'
    boolean mProvisioned;
    boolean mAutoRestore;
    PowerManager.WakeLock mWakelock;
    HandlerThread mHandlerThread;
    BackupHandler mBackupHandler;
    PendingIntent mRunBackupIntent, mRunInitIntent;
    BroadcastReceiver mRunBackupReceiver, mRunInitReceiver;
    // map UIDs to the set of participating packages under that UID
    final SparseArray<HashSet<String>> mBackupParticipants
            = new SparseArray<HashSet<String>>();
    // set of backup services that have pending changes
    class BackupRequest {
        public String packageName;

        BackupRequest(String pkgName) {
            packageName = pkgName;
        }

        public String toString() {
            return "BackupRequest{pkg=" + packageName + "}";
        }
    }
    // Backups that we haven't started yet.  Keys are package names.
    HashMap<String,BackupRequest> mPendingBackups
            = new HashMap<String,BackupRequest>();

    // Pseudoname that we use for the Package Manager metadata "package"
    static final String PACKAGE_MANAGER_SENTINEL = "@pm@";

    // locking around the pending-backup management
    final Object mQueueLock = new Object();

    // The thread performing the sequence of queued backups binds to each app's agent
    // in succession.  Bind notifications are asynchronously delivered through the
    // Activity Manager; use this lock object to signal when a requested binding has
    // completed.
    final Object mAgentConnectLock = new Object();
    IBackupAgent mConnectedAgent;
    volatile boolean mBackupRunning;
    volatile boolean mConnecting;
    volatile long mLastBackupPass;
    volatile long mNextBackupPass;

    // For debugging, we maintain a progress trace of operations during backup
    static final boolean DEBUG_BACKUP_TRACE = true;
    final List<String> mBackupTrace = new ArrayList<String>();

    // A similar synchronization mechanism around clearing apps' data for restore
    final Object mClearDataLock = new Object();
    volatile boolean mClearingData;

    // Transport bookkeeping
    final Intent mTransportServiceIntent = new Intent(SERVICE_ACTION_TRANSPORT_HOST);
    final ArrayMap<String,String> mTransportNames
            = new ArrayMap<String,String>();             // component name -> registration name
    final ArrayMap<String,IBackupTransport> mTransports
            = new ArrayMap<String,IBackupTransport>();   // registration name -> binder
    final ArrayMap<String,TransportConnection> mTransportConnections
            = new ArrayMap<String,TransportConnection>();
    String mCurrentTransport;
    ActiveRestoreSession mActiveRestoreSession;

    // Watch the device provisioning operation during setup
    ContentObserver mProvisionedObserver;

    // The published binder is actually to a singleton trampoline object that calls
    // through to the proper code.  This indirection lets us turn down the heavy
    // implementation object on the fly without disturbing binders that have been
    // cached elsewhere in the system.
    static Trampoline sInstance;
    static Trampoline getInstance() {
        // Always constructed during system bringup, so no need to lazy-init
        return sInstance;
    }

    public static final class Lifecycle extends SystemService {

        public Lifecycle(Context context) {
            super(context);
            sInstance = new Trampoline(context);
        }

        @Override
        public void onStart() {
            publishBinderService(Context.BACKUP_SERVICE, sInstance);
        }

        @Override
        public void onBootPhase(int phase) {
            if (phase == PHASE_SYSTEM_SERVICES_READY) {
                sInstance.initialize(UserHandle.USER_OWNER);
            } else if (phase == PHASE_THIRD_PARTY_APPS_CAN_START) {
                ContentResolver r = sInstance.mContext.getContentResolver();
                boolean areEnabled = Settings.Secure.getInt(r,
                        Settings.Secure.BACKUP_ENABLED, 0) != 0;
                try {
                    sInstance.setBackupEnabled(areEnabled);
                } catch (RemoteException e) {
                    // can't happen; it's a local object
                }
            }
        }
    }

    class ProvisionedObserver extends ContentObserver {
        public ProvisionedObserver(Handler handler) {
            super(handler);
        }

        public void onChange(boolean selfChange) {
            final boolean wasProvisioned = mProvisioned;
            final boolean isProvisioned = deviceIsProvisioned();
            // latch: never unprovision
            mProvisioned = wasProvisioned || isProvisioned;
            if (MORE_DEBUG) {
                Slog.d(TAG, "Provisioning change: was=" + wasProvisioned
                        + " is=" + isProvisioned + " now=" + mProvisioned);
            }

            synchronized (mQueueLock) {
                if (mProvisioned && !wasProvisioned && mEnabled) {
                    // we're now good to go, so start the backup alarms
                    if (MORE_DEBUG) Slog.d(TAG, "Now provisioned, so starting backups");
                    startBackupAlarmsLocked(FIRST_BACKUP_INTERVAL);
                    scheduleNextFullBackupJob();
                }
            }
        }
    }

    class RestoreGetSetsParams {
        public IBackupTransport transport;
        public ActiveRestoreSession session;
        public IRestoreObserver observer;

        RestoreGetSetsParams(IBackupTransport _transport, ActiveRestoreSession _session,
                IRestoreObserver _observer) {
            transport = _transport;
            session = _session;
            observer = _observer;
        }
    }

    class RestoreParams {
        public IBackupTransport transport;
        public String dirName;
        public IRestoreObserver observer;
        public long token;
        public PackageInfo pkgInfo;
        public int pmToken; // in post-install restore, the PM's token for this transaction
        public boolean isSystemRestore;
        public String[] filterSet;

        // Restore a single package
        RestoreParams(IBackupTransport _transport, String _dirName, IRestoreObserver _obs,
                long _token, PackageInfo _pkg, int _pmToken) {
            transport = _transport;
            dirName = _dirName;
            observer = _obs;
            token = _token;
            pkgInfo = _pkg;
            pmToken = _pmToken;
            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) {
            transport = _transport;
            dirName = _dirName;
            observer = _obs;
            token = _token;
            pkgInfo = null;
            pmToken = 0;
            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 _isSystemRestore) {
            transport = _transport;
            dirName = _dirName;
            observer = _obs;
            token = _token;
            pkgInfo = null;
            pmToken = 0;
            isSystemRestore = _isSystemRestore;
            filterSet = _filterSet;
        }
    }

    class ClearParams {
        public IBackupTransport transport;
        public PackageInfo packageInfo;

        ClearParams(IBackupTransport _transport, PackageInfo _info) {
            transport = _transport;
            packageInfo = _info;
        }
    }

    class ClearRetryParams {
        public String transportName;
        public String packageName;

        ClearRetryParams(String transport, String pkg) {
            transportName = transport;
            packageName = pkg;
        }
    }

    class FullParams {
        public ParcelFileDescriptor fd;
        public final AtomicBoolean latch;
        public IFullBackupRestoreObserver observer;
        public String curPassword;     // filled in by the confirmation step
        public String encryptPassword;

        FullParams() {
            latch = new AtomicBoolean(false);
        }
    }

    class FullBackupParams extends FullParams {
        public boolean includeApks;
        public boolean includeObbs;
        public boolean includeShared;
        public boolean doWidgets;
        public boolean allApps;
        public boolean includeSystem;
        public boolean doCompress;
        public String[] packages;

        FullBackupParams(ParcelFileDescriptor output, boolean saveApks, boolean saveObbs,
                boolean saveShared, boolean alsoWidgets, boolean doAllApps, boolean doSystem,
                boolean compress, String[] pkgList) {
            fd = output;
            includeApks = saveApks;
            includeObbs = saveObbs;
            includeShared = saveShared;
            doWidgets = alsoWidgets;
            allApps = doAllApps;
            includeSystem = doSystem;
            doCompress = compress;
            packages = pkgList;
        }
    }

    class FullRestoreParams extends FullParams {
        FullRestoreParams(ParcelFileDescriptor input) {
            fd = input;
        }
    }

    // Bookkeeping of in-flight operations for timeout etc. purposes.  The operation
    // token is the index of the entry in the pending-operations list.
    static final int OP_PENDING = 0;
    static final int OP_ACKNOWLEDGED = 1;
    static final int OP_TIMEOUT = -1;

    class Operation {
        public int state;
        public BackupRestoreTask callback;

        Operation(int initialState, BackupRestoreTask callbackObj) {
            state = initialState;
            callback = callbackObj;
        }
    }
    final SparseArray<Operation> mCurrentOperations = new SparseArray<Operation>();
    final Object mCurrentOpLock = new Object();
    final Random mTokenGenerator = new Random();

    final SparseArray<FullParams> mFullConfirmations = new SparseArray<FullParams>();

    // Where we keep our journal files and other bookkeeping
    File mBaseStateDir;
    File mDataDir;
    File mJournalDir;
    File mJournal;

    // Backup password, if any, and the file where it's saved.  What is stored is not the
    // password text itself; it's the result of a PBKDF2 hash with a randomly chosen (but
    // persisted) salt.  Validation is performed by running the challenge text through the
    // same PBKDF2 cycle with the persisted salt; if the resulting derived key string matches
    // the saved hash string, then the challenge text matches the originally supplied
    // password text.
    private final SecureRandom mRng = new SecureRandom();
    private String mPasswordHash;
    private File mPasswordHashFile;
    private int mPasswordVersion;
    private File mPasswordVersionFile;
    private byte[] mPasswordSalt;

    // Configuration of PBKDF2 that we use for generating pw hashes and intermediate keys
    static final int PBKDF2_HASH_ROUNDS = 10000;
    static final int PBKDF2_KEY_SIZE = 256;     // bits
    static final int PBKDF2_SALT_SIZE = 512;    // bits
    static final String ENCRYPTION_ALGORITHM_NAME = "AES-256";

    // Keep a log of all the apps we've ever backed up, and what the
    // dataset tokens are for both the current backup dataset and
    // the ancestral dataset.
    private File mEverStored;
    HashSet<String> mEverStoredApps = new HashSet<String>();

    static final int CURRENT_ANCESTRAL_RECORD_VERSION = 1;  // increment when the schema changes
    File mTokenFile;
    Set<String> mAncestralPackages = null;
    long mAncestralToken = 0;
    long mCurrentToken = 0;

    // Persistently track the need to do a full init
    static final String INIT_SENTINEL_FILE_NAME = "_need_init_";
    HashSet<String> mPendingInits = new HashSet<String>();  // transport names

    // Round-robin queue for scheduling full backup passes
    static final int SCHEDULE_FILE_VERSION = 1; // current version of the schedule file
    class FullBackupEntry implements Comparable<FullBackupEntry> {
        String packageName;
        long lastBackup;

        FullBackupEntry(String pkg, long when) {
            packageName = pkg;
            lastBackup = when;
        }

        @Override
        public int compareTo(FullBackupEntry other) {
            if (lastBackup < other.lastBackup) return -1;
            else if (lastBackup > other.lastBackup) return 1;
            else return 0;
        }
    }

    File mFullBackupScheduleFile;
    // If we're running a schedule-driven full backup, this is the task instance doing it
    PerformFullTransportBackupTask mRunningFullBackupTask; // inside mQueueLock
    ArrayList<FullBackupEntry> mFullBackupQueue;           // inside mQueueLock

    // Utility: build a new random integer token
    int generateToken() {
        int token;
        do {
            synchronized (mTokenGenerator) {
                token = mTokenGenerator.nextInt();
            }
        } while (token < 0);
        return token;
    }

    // High level policy: apps are ineligible for backup if certain conditions apply
    public static boolean appIsEligibleForBackup(ApplicationInfo app) {
        // 1. their manifest states android:allowBackup="false"
        if ((app.flags&ApplicationInfo.FLAG_ALLOW_BACKUP) == 0) {
            return false;
        }

        // 2. they run as a system-level uid but do not supply their own backup agent
        if ((app.uid < Process.FIRST_APPLICATION_UID) && (app.backupAgentName == null)) {
            return false;
        }

        // 3. it is the special shared-storage backup package used for 'adb backup'
        if (app.packageName.equals(BackupManagerService.SHARED_BACKUP_AGENT_PACKAGE)) {
            return false;
        }

        return true;
    }

    /* does *not* check overall backup eligibility policy! */
    public static boolean appGetsFullBackup(PackageInfo pkg) {
        if (pkg.applicationInfo.backupAgentName != null) {
            // If it has an agent, it gets full backups only if it says so
            return (pkg.applicationInfo.flags & ApplicationInfo.FLAG_FULL_BACKUP_ONLY) != 0;
        }

        // No agent means we do full backups for it
        return true;
    }

    // ----- Asynchronous backup/restore handler thread -----

    private class BackupHandler extends Handler {
        public BackupHandler(Looper looper) {
            super(looper);
        }

        public void handleMessage(Message msg) {

            switch (msg.what) {
            case MSG_RUN_BACKUP:
            {
                mLastBackupPass = System.currentTimeMillis();
                mNextBackupPass = mLastBackupPass + BACKUP_INTERVAL;

                IBackupTransport transport = getTransport(mCurrentTransport);
                if (transport == null) {
                    Slog.v(TAG, "Backup requested but no transport available");
                    synchronized (mQueueLock) {
                        mBackupRunning = false;
                    }
                    mWakelock.release();
                    break;
                }

                // snapshot the pending-backup set and work on that
                ArrayList<BackupRequest> queue = new ArrayList<BackupRequest>();
                File oldJournal = mJournal;
                synchronized (mQueueLock) {
                    // Do we have any work to do?  Construct the work queue
                    // then release the synchronization lock to actually run
                    // the backup.
                    if (mPendingBackups.size() > 0) {
                        for (BackupRequest b: mPendingBackups.values()) {
                            queue.add(b);
                        }
                        if (DEBUG) Slog.v(TAG, "clearing pending backups");
                        mPendingBackups.clear();

                        // Start a new backup-queue journal file too
                        mJournal = null;

                    }
                }

                // At this point, we have started a new journal file, and the old
                // file identity is being passed to the backup processing task.
                // When it completes successfully, that old journal file will be
                // deleted.  If we crash prior to that, the old journal is parsed
                // at next boot and the journaled requests fulfilled.
                boolean staged = true;
                if (queue.size() > 0) {
                    // Spin up a backup state sequence and set it running
                    try {
                        String dirName = transport.transportDirName();
                        PerformBackupTask pbt = new PerformBackupTask(transport, dirName,
                                queue, oldJournal);
                        Message pbtMessage = obtainMessage(MSG_BACKUP_RESTORE_STEP, pbt);
                        sendMessage(pbtMessage);
                    } catch (RemoteException e) {
                        // unable to ask the transport its dir name -- transient failure, since
                        // the above check succeeded.  Try again next time.
                        Slog.e(TAG, "Transport became unavailable attempting backup");
                        staged = false;
                    }
                } else {
                    Slog.v(TAG, "Backup requested but nothing pending");
                    staged = false;
                }

                if (!staged) {
                    // if we didn't actually hand off the wakelock, rewind until next time
                    synchronized (mQueueLock) {
                        mBackupRunning = false;
                    }
                    mWakelock.release();
                }
                break;
            }

            case MSG_BACKUP_RESTORE_STEP:
            {
                try {
                    BackupRestoreTask task = (BackupRestoreTask) msg.obj;
                    if (MORE_DEBUG) Slog.v(TAG, "Got next step for " + task + ", executing");
                    task.execute();
                } catch (ClassCastException e) {
                    Slog.e(TAG, "Invalid backup task in flight, obj=" + msg.obj);
                }
                break;
            }

            case MSG_OP_COMPLETE:
            {
                try {
                    BackupRestoreTask task = (BackupRestoreTask) msg.obj;
                    task.operationComplete();
                } catch (ClassCastException e) {
                    Slog.e(TAG, "Invalid completion in flight, obj=" + msg.obj);
                }
                break;
            }

            case MSG_RUN_ADB_BACKUP:
            {
                // TODO: refactor full backup to be a looper-based state machine
                // similar to normal backup/restore.
                FullBackupParams params = (FullBackupParams)msg.obj;
                PerformAdbBackupTask task = new PerformAdbBackupTask(params.fd,
                        params.observer, params.includeApks, params.includeObbs,
                        params.includeShared, params.doWidgets,
                        params.curPassword, params.encryptPassword,
                        params.allApps, params.includeSystem, params.doCompress,
                        params.packages, params.latch);
                (new Thread(task, "adb-backup")).start();
                break;
            }

            case MSG_RUN_FULL_TRANSPORT_BACKUP:
            {
                PerformFullTransportBackupTask task = (PerformFullTransportBackupTask) msg.obj;
                (new Thread(task, "transport-backup")).start();
                break;
            }

            case MSG_RUN_RESTORE:
            {
                RestoreParams params = (RestoreParams)msg.obj;
                Slog.d(TAG, "MSG_RUN_RESTORE observer=" + params.observer);
                BackupRestoreTask task = new PerformUnifiedRestoreTask(params.transport,
                        params.observer, params.token, params.pkgInfo, params.pmToken,
                        params.isSystemRestore, params.filterSet);
                Message restoreMsg = obtainMessage(MSG_BACKUP_RESTORE_STEP, task);
                sendMessage(restoreMsg);
                break;
            }

            case MSG_RUN_ADB_RESTORE:
            {
                // TODO: refactor full restore to be a looper-based state machine
                // similar to normal backup/restore.
                FullRestoreParams params = (FullRestoreParams)msg.obj;
                PerformAdbRestoreTask task = new PerformAdbRestoreTask(params.fd,
                        params.curPassword, params.encryptPassword,
                        params.observer, params.latch);
                (new Thread(task, "adb-restore")).start();
                break;
            }

            case MSG_RUN_CLEAR:
            {
                ClearParams params = (ClearParams)msg.obj;
                (new PerformClearTask(params.transport, params.packageInfo)).run();
                break;
            }

            case MSG_RETRY_CLEAR:
            {
                // reenqueues if the transport remains unavailable
                ClearRetryParams params = (ClearRetryParams)msg.obj;
                clearBackupData(params.transportName, params.packageName);
                break;
            }

            case MSG_RUN_INITIALIZE:
            {
                HashSet<String> queue;

                // Snapshot the pending-init queue and work on that
                synchronized (mQueueLock) {
                    queue = new HashSet<String>(mPendingInits);
                    mPendingInits.clear();
                }

                (new PerformInitializeTask(queue)).run();
                break;
            }

            case MSG_RETRY_INIT:
            {
                synchronized (mQueueLock) {
                    recordInitPendingLocked(msg.arg1 != 0, (String)msg.obj);
                    mAlarmManager.set(AlarmManager.RTC_WAKEUP, System.currentTimeMillis(),
                            mRunInitIntent);
                }
                break;
            }

            case MSG_RUN_GET_RESTORE_SETS:
            {
                // Like other async operations, this is entered with the wakelock held
                RestoreSet[] sets = null;
                RestoreGetSetsParams params = (RestoreGetSetsParams)msg.obj;
                try {
                    sets = params.transport.getAvailableRestoreSets();
                    // cache the result in the active session
                    synchronized (params.session) {
                        params.session.mRestoreSets = sets;
                    }
                    if (sets == null) EventLog.writeEvent(EventLogTags.RESTORE_TRANSPORT_FAILURE);
                } catch (Exception e) {
                    Slog.e(TAG, "Error from transport getting set list");
                } finally {
                    if (params.observer != null) {
                        try {
                            params.observer.restoreSetsAvailable(sets);
                        } catch (RemoteException re) {
                            Slog.e(TAG, "Unable to report listing to observer");
                        } catch (Exception e) {
                            Slog.e(TAG, "Restore observer threw", e);
                        }
                    }

                    // Done: reset the session timeout clock
                    removeMessages(MSG_RESTORE_TIMEOUT);
                    sendEmptyMessageDelayed(MSG_RESTORE_TIMEOUT, TIMEOUT_RESTORE_INTERVAL);

                    mWakelock.release();
                }
                break;
            }

            case MSG_TIMEOUT:
            {
                handleTimeout(msg.arg1, msg.obj);
                break;
            }

            case MSG_RESTORE_TIMEOUT:
            {
                synchronized (BackupManagerService.this) {
                    if (mActiveRestoreSession != null) {
                        // Client app left the restore session dangling.  We know that it
                        // can't be in the middle of an actual restore operation because
                        // the timeout is suspended while a restore is in progress.  Clean
                        // up now.
                        Slog.w(TAG, "Restore session timed out; aborting");
                        mActiveRestoreSession.markTimedOut();
                        post(mActiveRestoreSession.new EndRestoreRunnable(
                                BackupManagerService.this, mActiveRestoreSession));
                    }
                }
                break;
            }

            case MSG_FULL_CONFIRMATION_TIMEOUT:
            {
                synchronized (mFullConfirmations) {
                    FullParams params = mFullConfirmations.get(msg.arg1);
                    if (params != null) {
                        Slog.i(TAG, "Full backup/restore timed out waiting for user confirmation");

                        // Release the waiter; timeout == completion
                        signalFullBackupRestoreCompletion(params);

                        // Remove the token from the set
                        mFullConfirmations.delete(msg.arg1);

                        // Report a timeout to the observer, if any
                        if (params.observer != null) {
                            try {
                                params.observer.onTimeout();
                            } catch (RemoteException e) {
                                /* don't care if the app has gone away */
                            }
                        }
                    } else {
                        Slog.d(TAG, "couldn't find params for token " + msg.arg1);
                    }
                }
                break;
            }

            case MSG_WIDGET_BROADCAST:
            {
                final Intent intent = (Intent) msg.obj;
                mContext.sendBroadcastAsUser(intent, UserHandle.OWNER);
                break;
            }
            }
        }
    }

    // ----- Debug-only backup operation trace -----
    void addBackupTrace(String s) {
        if (DEBUG_BACKUP_TRACE) {
            synchronized (mBackupTrace) {
                mBackupTrace.add(s);
            }
        }
    }

    void clearBackupTrace() {
        if (DEBUG_BACKUP_TRACE) {
            synchronized (mBackupTrace) {
                mBackupTrace.clear();
            }
        }
    }

    // ----- Main service implementation -----

    public BackupManagerService(Context context, Trampoline parent) {
        mContext = context;
        mPackageManager = context.getPackageManager();
        mPackageManagerBinder = AppGlobals.getPackageManager();
        mActivityManager = ActivityManagerNative.getDefault();

        mAlarmManager = (AlarmManager) context.getSystemService(Context.ALARM_SERVICE);
        mPowerManager = (PowerManager) context.getSystemService(Context.POWER_SERVICE);
        mMountService = IMountService.Stub.asInterface(ServiceManager.getService("mount"));

        mBackupManagerBinder = Trampoline.asInterface(parent.asBinder());

        // spin up the backup/restore handler thread
        mHandlerThread = new HandlerThread("backup", Process.THREAD_PRIORITY_BACKGROUND);
        mHandlerThread.start();
        mBackupHandler = new BackupHandler(mHandlerThread.getLooper());

        // Set up our bookkeeping
        final ContentResolver resolver = context.getContentResolver();
        mProvisioned = Settings.Global.getInt(resolver,
                Settings.Global.DEVICE_PROVISIONED, 0) != 0;
        mAutoRestore = Settings.Secure.getInt(resolver,
                Settings.Secure.BACKUP_AUTO_RESTORE, 1) != 0;

        mProvisionedObserver = new ProvisionedObserver(mBackupHandler);
        resolver.registerContentObserver(
                Settings.Global.getUriFor(Settings.Global.DEVICE_PROVISIONED),
                false, mProvisionedObserver);

        // If Encrypted file systems is enabled or disabled, this call will return the
        // correct directory.
        mBaseStateDir = new File(Environment.getSecureDataDirectory(), "backup");
        mBaseStateDir.mkdirs();
        if (!SELinux.restorecon(mBaseStateDir)) {
            Slog.e(TAG, "SELinux restorecon failed on " + mBaseStateDir);
        }
        mDataDir = Environment.getDownloadCacheDirectory();

        mPasswordVersion = 1;       // unless we hear otherwise
        mPasswordVersionFile = new File(mBaseStateDir, "pwversion");
        if (mPasswordVersionFile.exists()) {
            FileInputStream fin = null;
            DataInputStream in = null;
            try {
                fin = new FileInputStream(mPasswordVersionFile);
                in = new DataInputStream(fin);
                mPasswordVersion = in.readInt();
            } catch (IOException e) {
                Slog.e(TAG, "Unable to read backup pw version");
            } finally {
                try {
                    if (in != null) in.close();
                    if (fin != null) fin.close();
                } catch (IOException e) {
                    Slog.w(TAG, "Error closing pw version files");
                }
            }
        }

        mPasswordHashFile = new File(mBaseStateDir, "pwhash");
        if (mPasswordHashFile.exists()) {
            FileInputStream fin = null;
            DataInputStream in = null;
            try {
                fin = new FileInputStream(mPasswordHashFile);
                in = new DataInputStream(new BufferedInputStream(fin));
                // integer length of the salt array, followed by the salt,
                // then the hex pw hash string
                int saltLen = in.readInt();
                byte[] salt = new byte[saltLen];
                in.readFully(salt);
                mPasswordHash = in.readUTF();
                mPasswordSalt = salt;
            } catch (IOException e) {
                Slog.e(TAG, "Unable to read saved backup pw hash");
            } finally {
                try {
                    if (in != null) in.close();
                    if (fin != null) fin.close();
                } catch (IOException e) {
                    Slog.w(TAG, "Unable to close streams");
                }
            }
        }

        // Alarm receivers for scheduled backups & initialization operations
        mRunBackupReceiver = new RunBackupReceiver();
        IntentFilter filter = new IntentFilter();
        filter.addAction(RUN_BACKUP_ACTION);
        context.registerReceiver(mRunBackupReceiver, filter,
                android.Manifest.permission.BACKUP, null);

        mRunInitReceiver = new RunInitializeReceiver();
        filter = new IntentFilter();
        filter.addAction(RUN_INITIALIZE_ACTION);
        context.registerReceiver(mRunInitReceiver, filter,
                android.Manifest.permission.BACKUP, null);

        Intent backupIntent = new Intent(RUN_BACKUP_ACTION);
        backupIntent.addFlags(Intent.FLAG_RECEIVER_REGISTERED_ONLY);
        mRunBackupIntent = PendingIntent.getBroadcast(context, MSG_RUN_BACKUP, backupIntent, 0);

        Intent initIntent = new Intent(RUN_INITIALIZE_ACTION);
        backupIntent.addFlags(Intent.FLAG_RECEIVER_REGISTERED_ONLY);
        mRunInitIntent = PendingIntent.getBroadcast(context, MSG_RUN_INITIALIZE, initIntent, 0);

        // Set up the backup-request journaling
        mJournalDir = new File(mBaseStateDir, "pending");
        mJournalDir.mkdirs();   // creates mBaseStateDir along the way
        mJournal = null;        // will be created on first use

        // Set up the various sorts of package tracking we do
        mFullBackupScheduleFile = new File(mBaseStateDir, "fb-schedule");
        initPackageTracking();

        // Build our mapping of uid to backup client services.  This implicitly
        // schedules a backup pass on the Package Manager metadata the first
        // time anything needs to be backed up.
        synchronized (mBackupParticipants) {
            addPackageParticipantsLocked(null);
        }

        // Set up our transport options and initialize the default transport
        // TODO: Don't create transports that we don't need to?
        mCurrentTransport = Settings.Secure.getString(context.getContentResolver(),
                Settings.Secure.BACKUP_TRANSPORT);
        if ("".equals(mCurrentTransport)) {
            mCurrentTransport = null;
        }
        if (DEBUG) Slog.v(TAG, "Starting with transport " + mCurrentTransport);

        // Find all transport hosts and bind to their services
        List<ResolveInfo> hosts = mPackageManager.queryIntentServicesAsUser(
                mTransportServiceIntent, 0, UserHandle.USER_OWNER);
        if (DEBUG) {
            Slog.v(TAG, "Found transports: " + ((hosts == null) ? "null" : hosts.size()));
        }
        if (hosts != null) {
            for (int i = 0; i < hosts.size(); i++) {
                final ServiceInfo transport = hosts.get(i).serviceInfo;
                if (MORE_DEBUG) {
                    Slog.v(TAG, "   " + transport.packageName + "/" + transport.name);
                }
                tryBindTransport(transport);
            }
        }

        // Now that we know about valid backup participants, parse any
        // leftover journal files into the pending backup set
        parseLeftoverJournals();

        // Power management
        mWakelock = mPowerManager.newWakeLock(PowerManager.PARTIAL_WAKE_LOCK, "*backup*");
    }

    private class RunBackupReceiver extends BroadcastReceiver {
        public void onReceive(Context context, Intent intent) {
            if (RUN_BACKUP_ACTION.equals(intent.getAction())) {
                synchronized (mQueueLock) {
                    if (mPendingInits.size() > 0) {
                        // If there are pending init operations, we process those
                        // and then settle into the usual periodic backup schedule.
                        if (DEBUG) Slog.v(TAG, "Init pending at scheduled backup");
                        try {
                            mAlarmManager.cancel(mRunInitIntent);
                            mRunInitIntent.send();
                        } catch (PendingIntent.CanceledException ce) {
                            Slog.e(TAG, "Run init intent cancelled");
                            // can't really do more than bail here
                        }
                    } else {
                        // Don't run backups now if we're disabled or not yet
                        // fully set up.
                        if (mEnabled && mProvisioned) {
                            if (!mBackupRunning) {
                                if (DEBUG) Slog.v(TAG, "Running a backup pass");

                                // Acquire the wakelock and pass it to the backup thread.  it will
                                // be released once backup concludes.
                                mBackupRunning = true;
                                mWakelock.acquire();

                                Message msg = mBackupHandler.obtainMessage(MSG_RUN_BACKUP);
                                mBackupHandler.sendMessage(msg);
                            } else {
                                Slog.i(TAG, "Backup time but one already running");
                            }
                        } else {
                            Slog.w(TAG, "Backup pass but e=" + mEnabled + " p=" + mProvisioned);
                        }
                    }
                }
            }
        }
    }

    private class RunInitializeReceiver extends BroadcastReceiver {
        public void onReceive(Context context, Intent intent) {
            if (RUN_INITIALIZE_ACTION.equals(intent.getAction())) {
                synchronized (mQueueLock) {
                    if (DEBUG) Slog.v(TAG, "Running a device init");

                    // Acquire the wakelock and pass it to the init thread.  it will
                    // be released once init concludes.
                    mWakelock.acquire();

                    Message msg = mBackupHandler.obtainMessage(MSG_RUN_INITIALIZE);
                    mBackupHandler.sendMessage(msg);
                }
            }
        }
    }

    private void initPackageTracking() {
        if (MORE_DEBUG) Slog.v(TAG, "` tracking");

        // Remember our ancestral dataset
        mTokenFile = new File(mBaseStateDir, "ancestral");
        try {
            RandomAccessFile tf = new RandomAccessFile(mTokenFile, "r");
            int version = tf.readInt();
            if (version == CURRENT_ANCESTRAL_RECORD_VERSION) {
                mAncestralToken = tf.readLong();
                mCurrentToken = tf.readLong();

                int numPackages = tf.readInt();
                if (numPackages >= 0) {
                    mAncestralPackages = new HashSet<String>();
                    for (int i = 0; i < numPackages; i++) {
                        String pkgName = tf.readUTF();
                        mAncestralPackages.add(pkgName);
                    }
                }
            }
            tf.close();
        } catch (FileNotFoundException fnf) {
            // Probably innocuous
            Slog.v(TAG, "No ancestral data");
        } catch (IOException e) {
            Slog.w(TAG, "Unable to read token file", e);
        }

        // Keep a log of what apps we've ever backed up.  Because we might have
        // rebooted in the middle of an operation that was removing something from
        // this log, we sanity-check its contents here and reconstruct it.
        mEverStored = new File(mBaseStateDir, "processed");
        File tempProcessedFile = new File(mBaseStateDir, "processed.new");

        // If we were in the middle of removing something from the ever-backed-up
        // file, there might be a transient "processed.new" file still present.
        // Ignore it -- we'll validate "processed" against the current package set.
        if (tempProcessedFile.exists()) {
            tempProcessedFile.delete();
        }

        // If there are previous contents, parse them out then start a new
        // file to continue the recordkeeping.
        if (mEverStored.exists()) {
            RandomAccessFile temp = null;
            RandomAccessFile in = null;

            try {
                temp = new RandomAccessFile(tempProcessedFile, "rws");
                in = new RandomAccessFile(mEverStored, "r");

                while (true) {
                    PackageInfo info;
                    String pkg = in.readUTF();
                    try {
                        info = mPackageManager.getPackageInfo(pkg, 0);
                        mEverStoredApps.add(pkg);
                        temp.writeUTF(pkg);
                        if (MORE_DEBUG) Slog.v(TAG, "   + " + pkg);
                    } catch (NameNotFoundException e) {
                        // nope, this package was uninstalled; don't include it
                        if (MORE_DEBUG) Slog.v(TAG, "   - " + pkg);
                    }
                }
            } catch (EOFException e) {
                // Once we've rewritten the backup history log, atomically replace the
                // old one with the new one then reopen the file for continuing use.
                if (!tempProcessedFile.renameTo(mEverStored)) {
                    Slog.e(TAG, "Error renaming " + tempProcessedFile + " to " + mEverStored);
                }
            } catch (IOException e) {
                Slog.e(TAG, "Error in processed file", e);
            } finally {
                try { if (temp != null) temp.close(); } catch (IOException e) {}
                try { if (in != null) in.close(); } catch (IOException e) {}
            }
        }

        // Resume the full-data backup queue
        mFullBackupQueue = readFullBackupSchedule();

        // Register for broadcasts about package install, etc., so we can
        // update the provider list.
        IntentFilter filter = new IntentFilter();
        filter.addAction(Intent.ACTION_PACKAGE_ADDED);
        filter.addAction(Intent.ACTION_PACKAGE_REMOVED);
        filter.addAction(Intent.ACTION_PACKAGE_CHANGED);
        filter.addDataScheme("package");
        mContext.registerReceiver(mBroadcastReceiver, filter);
        // Register for events related to sdcard installation.
        IntentFilter sdFilter = new IntentFilter();
        sdFilter.addAction(Intent.ACTION_EXTERNAL_APPLICATIONS_AVAILABLE);
        sdFilter.addAction(Intent.ACTION_EXTERNAL_APPLICATIONS_UNAVAILABLE);
        mContext.registerReceiver(mBroadcastReceiver, sdFilter);
    }

    private ArrayList<FullBackupEntry> readFullBackupSchedule() {
        ArrayList<FullBackupEntry> schedule = null;
        synchronized (mQueueLock) {
            if (mFullBackupScheduleFile.exists()) {
                FileInputStream fstream = null;
                BufferedInputStream bufStream = null;
                DataInputStream in = null;
                try {
                    fstream = new FileInputStream(mFullBackupScheduleFile);
                    bufStream = new BufferedInputStream(fstream);
                    in = new DataInputStream(bufStream);

                    int version = in.readInt();
                    if (version != SCHEDULE_FILE_VERSION) {
                        Slog.e(TAG, "Unknown backup schedule version " + version);
                        return null;
                    }

                    int N = in.readInt();
                    schedule = new ArrayList<FullBackupEntry>(N);
                    for (int i = 0; i < N; i++) {
                        String pkgName = in.readUTF();
                        long lastBackup = in.readLong();
                        schedule.add(new FullBackupEntry(pkgName, lastBackup));
                    }
                    Collections.sort(schedule);
                } catch (Exception e) {
                    Slog.e(TAG, "Unable to read backup schedule", e);
                    mFullBackupScheduleFile.delete();
                    schedule = null;
                } finally {
                    IoUtils.closeQuietly(in);
                    IoUtils.closeQuietly(bufStream);
                    IoUtils.closeQuietly(fstream);
                }
            }

            if (schedule == null) {
                // no prior queue record, or unable to read it.  Set up the queue
                // from scratch.
                List<PackageInfo> apps =
                        PackageManagerBackupAgent.getStorableApplications(mPackageManager);
                final int N = apps.size();
                schedule = new ArrayList<FullBackupEntry>(N);
                for (int i = 0; i < N; i++) {
                    PackageInfo info = apps.get(i);
                    if (appGetsFullBackup(info)) {
                        schedule.add(new FullBackupEntry(info.packageName, 0));
                    }
                }
                writeFullBackupScheduleAsync();
            }
        }
        return schedule;
    }

    Runnable mFullBackupScheduleWriter = new Runnable() {
        @Override public void run() {
            synchronized (mQueueLock) {
                try {
                    ByteArrayOutputStream bufStream = new ByteArrayOutputStream(4096);
                    DataOutputStream bufOut = new DataOutputStream(bufStream);
                    bufOut.writeInt(SCHEDULE_FILE_VERSION);

                    // version 1:
                    //
                    // [int] # of packages in the queue = N
                    // N * {
                    //     [utf8] package name
                    //     [long] last backup time for this package
                    //     }
                    int N = mFullBackupQueue.size();
                    bufOut.writeInt(N);

                    for (int i = 0; i < N; i++) {
                        FullBackupEntry entry = mFullBackupQueue.get(i);
                        bufOut.writeUTF(entry.packageName);
                        bufOut.writeLong(entry.lastBackup);
                    }
                    bufOut.flush();

                    AtomicFile af = new AtomicFile(mFullBackupScheduleFile);
                    FileOutputStream out = af.startWrite();
                    out.write(bufStream.toByteArray());
                    af.finishWrite(out);
                } catch (Exception e) {
                    Slog.e(TAG, "Unable to write backup schedule!", e);
                }
            }
        }
    };

    private void writeFullBackupScheduleAsync() {
        mBackupHandler.removeCallbacks(mFullBackupScheduleWriter);
        mBackupHandler.post(mFullBackupScheduleWriter);
    }

    private void parseLeftoverJournals() {
        for (File f : mJournalDir.listFiles()) {
            if (mJournal == null || f.compareTo(mJournal) != 0) {
                // This isn't the current journal, so it must be a leftover.  Read
                // out the package names mentioned there and schedule them for
                // backup.
                RandomAccessFile in = null;
                try {
                    Slog.i(TAG, "Found stale backup journal, scheduling");
                    in = new RandomAccessFile(f, "r");
                    while (true) {
                        String packageName = in.readUTF();
                        if (MORE_DEBUG) Slog.i(TAG, "  " + packageName);
                        dataChangedImpl(packageName);
                    }
                } catch (EOFException e) {
                    // no more data; we're done
                } catch (Exception e) {
                    Slog.e(TAG, "Can't read " + f, e);
                } finally {
                    // close/delete the file
                    try { if (in != null) in.close(); } catch (IOException e) {}
                    f.delete();
                }
            }
        }
    }

    private SecretKey buildPasswordKey(String algorithm, String pw, byte[] salt, int rounds) {
        return buildCharArrayKey(algorithm, pw.toCharArray(), salt, rounds);
    }

    private SecretKey buildCharArrayKey(String algorithm, char[] pwArray, byte[] salt, int rounds) {
        try {
            SecretKeyFactory keyFactory = SecretKeyFactory.getInstance(algorithm);
            KeySpec ks = new PBEKeySpec(pwArray, salt, rounds, PBKDF2_KEY_SIZE);
            return keyFactory.generateSecret(ks);
        } catch (InvalidKeySpecException e) {
            Slog.e(TAG, "Invalid key spec for PBKDF2!");
        } catch (NoSuchAlgorithmException e) {
            Slog.e(TAG, "PBKDF2 unavailable!");
        }
        return null;
    }

    private String buildPasswordHash(String algorithm, String pw, byte[] salt, int rounds) {
        SecretKey key = buildPasswordKey(algorithm, pw, salt, rounds);
        if (key != null) {
            return byteArrayToHex(key.getEncoded());
        }
        return null;
    }

    private String byteArrayToHex(byte[] data) {
        StringBuilder buf = new StringBuilder(data.length * 2);
        for (int i = 0; i < data.length; i++) {
            buf.append(Byte.toHexString(data[i], true));
        }
        return buf.toString();
    }

    private byte[] hexToByteArray(String digits) {
        final int bytes = digits.length() / 2;
        if (2*bytes != digits.length()) {
            throw new IllegalArgumentException("Hex string must have an even number of digits");
        }

        byte[] result = new byte[bytes];
        for (int i = 0; i < digits.length(); i += 2) {
            result[i/2] = (byte) Integer.parseInt(digits.substring(i, i+2), 16);
        }
        return result;
    }

    private byte[] makeKeyChecksum(String algorithm, byte[] pwBytes, byte[] salt, int rounds) {
        char[] mkAsChar = new char[pwBytes.length];
        for (int i = 0; i < pwBytes.length; i++) {
            mkAsChar[i] = (char) pwBytes[i];
        }

        Key checksum = buildCharArrayKey(algorithm, mkAsChar, salt, rounds);
        return checksum.getEncoded();
    }

    // Used for generating random salts or passwords
    private byte[] randomBytes(int bits) {
        byte[] array = new byte[bits / 8];
        mRng.nextBytes(array);
        return array;
    }

    boolean passwordMatchesSaved(String algorithm, String candidatePw, int rounds) {
        if (mPasswordHash == null) {
            // no current password case -- require that 'currentPw' be null or empty
            if (candidatePw == null || "".equals(candidatePw)) {
                return true;
            } // else the non-empty candidate does not match the empty stored pw
        } else {
            // hash the stated current pw and compare to the stored one
            if (candidatePw != null && candidatePw.length() > 0) {
                String currentPwHash = buildPasswordHash(algorithm, candidatePw, mPasswordSalt, rounds);
                if (mPasswordHash.equalsIgnoreCase(currentPwHash)) {
                    // candidate hash matches the stored hash -- the password matches
                    return true;
                }
            } // else the stored pw is nonempty but the candidate is empty; no match
        }
        return false;
    }

    public boolean setBackupPassword(String currentPw, String newPw) {
        mContext.enforceCallingOrSelfPermission(android.Manifest.permission.BACKUP,
                "setBackupPassword");

        // When processing v1 passwords we may need to try two different PBKDF2 checksum regimes
        final boolean pbkdf2Fallback = (mPasswordVersion < BACKUP_PW_FILE_VERSION);

        // If the supplied pw doesn't hash to the the saved one, fail.  The password
        // might be caught in the legacy crypto mismatch; verify that too.
        if (!passwordMatchesSaved(PBKDF_CURRENT, currentPw, PBKDF2_HASH_ROUNDS)
                && !(pbkdf2Fallback && passwordMatchesSaved(PBKDF_FALLBACK,
                        currentPw, PBKDF2_HASH_ROUNDS))) {
            return false;
        }

        // Snap up to current on the pw file version
        mPasswordVersion = BACKUP_PW_FILE_VERSION;
        FileOutputStream pwFout = null;
        DataOutputStream pwOut = null;
        try {
            pwFout = new FileOutputStream(mPasswordVersionFile);
            pwOut = new DataOutputStream(pwFout);
            pwOut.writeInt(mPasswordVersion);
        } catch (IOException e) {
            Slog.e(TAG, "Unable to write backup pw version; password not changed");
            return false;
        } finally {
            try {
                if (pwOut != null) pwOut.close();
                if (pwFout != null) pwFout.close();
            } catch (IOException e) {
                Slog.w(TAG, "Unable to close pw version record");
            }
        }

        // Clearing the password is okay
        if (newPw == null || newPw.isEmpty()) {
            if (mPasswordHashFile.exists()) {
                if (!mPasswordHashFile.delete()) {
                    // Unable to delete the old pw file, so fail
                    Slog.e(TAG, "Unable to clear backup password");
                    return false;
                }
            }
            mPasswordHash = null;
            mPasswordSalt = null;
            return true;
        }

        try {
            // Okay, build the hash of the new backup password
            byte[] salt = randomBytes(PBKDF2_SALT_SIZE);
            String newPwHash = buildPasswordHash(PBKDF_CURRENT, newPw, salt, PBKDF2_HASH_ROUNDS);

            OutputStream pwf = null, buffer = null;
            DataOutputStream out = null;
            try {
                pwf = new FileOutputStream(mPasswordHashFile);
                buffer = new BufferedOutputStream(pwf);
                out = new DataOutputStream(buffer);
                // integer length of the salt array, followed by the salt,
                // then the hex pw hash string
                out.writeInt(salt.length);
                out.write(salt);
                out.writeUTF(newPwHash);
                out.flush();
                mPasswordHash = newPwHash;
                mPasswordSalt = salt;
                return true;
            } finally {
                if (out != null) out.close();
                if (buffer != null) buffer.close();
                if (pwf != null) pwf.close();
            }
        } catch (IOException e) {
            Slog.e(TAG, "Unable to set backup password");
        }
        return false;
    }

    public boolean hasBackupPassword() {
        mContext.enforceCallingOrSelfPermission(android.Manifest.permission.BACKUP,
                "hasBackupPassword");

        return mPasswordHash != null && mPasswordHash.length() > 0;
    }

    private boolean backupPasswordMatches(String currentPw) {
        if (hasBackupPassword()) {
            final boolean pbkdf2Fallback = (mPasswordVersion < BACKUP_PW_FILE_VERSION);
            if (!passwordMatchesSaved(PBKDF_CURRENT, currentPw, PBKDF2_HASH_ROUNDS)
                    && !(pbkdf2Fallback && passwordMatchesSaved(PBKDF_FALLBACK,
                            currentPw, PBKDF2_HASH_ROUNDS))) {
                if (DEBUG) Slog.w(TAG, "Backup password mismatch; aborting");
                return false;
            }
        }
        return true;
    }

    // Maintain persistent state around whether need to do an initialize operation.
    // Must be called with the queue lock held.
    void recordInitPendingLocked(boolean isPending, String transportName) {
        if (DEBUG) Slog.i(TAG, "recordInitPendingLocked: " + isPending
                + " on transport " + transportName);
        mBackupHandler.removeMessages(MSG_RETRY_INIT);

        try {
            IBackupTransport transport = getTransport(transportName);
            if (transport != null) {
                String transportDirName = transport.transportDirName();
                File stateDir = new File(mBaseStateDir, transportDirName);
                File initPendingFile = new File(stateDir, INIT_SENTINEL_FILE_NAME);

                if (isPending) {
                    // We need an init before we can proceed with sending backup data.
                    // Record that with an entry in our set of pending inits, as well as
                    // journaling it via creation of a sentinel file.
                    mPendingInits.add(transportName);
                    try {
                        (new FileOutputStream(initPendingFile)).close();
                    } catch (IOException ioe) {
                        // Something is badly wrong with our permissions; just try to move on
                    }
                } else {
                    // No more initialization needed; wipe the journal and reset our state.
                    initPendingFile.delete();
                    mPendingInits.remove(transportName);
                }
                return; // done; don't fall through to the error case
            }
        } catch (RemoteException e) {
            // transport threw when asked its name; fall through to the lookup-failed case
        }

        // The named transport doesn't exist or threw.  This operation is
        // important, so we record the need for a an init and post a message
        // to retry the init later.
        if (isPending) {
            mPendingInits.add(transportName);
            mBackupHandler.sendMessageDelayed(
                    mBackupHandler.obtainMessage(MSG_RETRY_INIT,
                            (isPending ? 1 : 0),
                            0,
                            transportName),
                    TRANSPORT_RETRY_INTERVAL);
        }
    }

    // Reset all of our bookkeeping, in response to having been told that
    // the backend data has been wiped [due to idle expiry, for example],
    // so we must re-upload all saved settings.
    void resetBackupState(File stateFileDir) {
        synchronized (mQueueLock) {
            // Wipe the "what we've ever backed up" tracking
            mEverStoredApps.clear();
            mEverStored.delete();

            mCurrentToken = 0;
            writeRestoreTokens();

            // Remove all the state files
            for (File sf : stateFileDir.listFiles()) {
                // ... but don't touch the needs-init sentinel
                if (!sf.getName().equals(INIT_SENTINEL_FILE_NAME)) {
                    sf.delete();
                }
            }
        }

        // Enqueue a new backup of every participant
        synchronized (mBackupParticipants) {
            final int N = mBackupParticipants.size();
            for (int i=0; i<N; i++) {
                HashSet<String> participants = mBackupParticipants.valueAt(i);
                if (participants != null) {
                    for (String packageName : participants) {
                        dataChangedImpl(packageName);
                    }
                }
            }
        }
    }

    // Add a transport to our set of available backends.  If 'transport' is null, this
    // is an unregistration, and the transport's entry is removed from our bookkeeping.
    private void registerTransport(String name, String component, IBackupTransport transport) {
        synchronized (mTransports) {
            if (DEBUG) Slog.v(TAG, "Registering transport "
                    + component + "::" + name + " = " + transport);
            if (transport != null) {
                mTransports.put(name, transport);
                mTransportNames.put(component, name);
            } else {
                mTransports.remove(mTransportNames.get(component));
                mTransportNames.remove(component);
                // Nothing further to do in the unregistration case
                return;
            }
        }

        // If the init sentinel file exists, we need to be sure to perform the init
        // as soon as practical.  We also create the state directory at registration
        // time to ensure it's present from the outset.
        try {
            String transportName = transport.transportDirName();
            File stateDir = new File(mBaseStateDir, transportName);
            stateDir.mkdirs();

            File initSentinel = new File(stateDir, INIT_SENTINEL_FILE_NAME);
            if (initSentinel.exists()) {
                synchronized (mQueueLock) {
                    mPendingInits.add(transportName);

                    // TODO: pick a better starting time than now + 1 minute
                    long delay = 1000 * 60; // one minute, in milliseconds
                    mAlarmManager.set(AlarmManager.RTC_WAKEUP,
                            System.currentTimeMillis() + delay, mRunInitIntent);
                }
            }
        } catch (RemoteException e) {
            // the transport threw when asked its file naming prefs; declare it invalid
            Slog.e(TAG, "Unable to register transport as " + name);
            mTransportNames.remove(component);
            mTransports.remove(name);
        }
    }

    // ----- Track installation/removal of packages -----
    BroadcastReceiver mBroadcastReceiver = new BroadcastReceiver() {
        public void onReceive(Context context, Intent intent) {
            if (DEBUG) Slog.d(TAG, "Received broadcast " + intent);

            String action = intent.getAction();
            boolean replacing = false;
            boolean added = false;
            boolean changed = false;
            Bundle extras = intent.getExtras();
            String pkgList[] = null;
            if (Intent.ACTION_PACKAGE_ADDED.equals(action) ||
                    Intent.ACTION_PACKAGE_REMOVED.equals(action) ||
                    Intent.ACTION_PACKAGE_CHANGED.equals(action)) {
                Uri uri = intent.getData();
                if (uri == null) {
                    return;
                }
                String pkgName = uri.getSchemeSpecificPart();
                if (pkgName != null) {
                    pkgList = new String[] { pkgName };
                }
                changed = Intent.ACTION_PACKAGE_CHANGED.equals(action);

                // At package-changed we only care about looking at new transport states
                if (changed) {
                    try {
                        if (MORE_DEBUG) {
                            Slog.i(TAG, "Package " + pkgName + " changed; rechecking");
                        }
                        // unbind existing possibly-stale connections to that package's transports
                        synchronized (mTransports) {
                            TransportConnection conn = mTransportConnections.get(pkgName);
                            if (conn != null) {
                                final ServiceInfo svc = conn.mTransport;
                                ComponentName svcName =
                                        new ComponentName(svc.packageName, svc.name);
                                String flatName = svcName.flattenToShortString();
                                Slog.i(TAG, "Unbinding " + svcName);

                                mContext.unbindService(conn);
                                mTransportConnections.remove(pkgName);
                                mTransports.remove(mTransportNames.get(flatName));
                                mTransportNames.remove(flatName);
                            }
                        }
                        // and then (re)bind as appropriate
                        PackageInfo app = mPackageManager.getPackageInfo(pkgName, 0);
                        checkForTransportAndBind(app);
                    } catch (NameNotFoundException e) {
                        // Nope, can't find it - just ignore
                        if (MORE_DEBUG) {
                            Slog.w(TAG, "Can't find changed package " + pkgName);
                        }
                    }
                    return; // nothing more to do in the PACKAGE_CHANGED case
                }

                added = Intent.ACTION_PACKAGE_ADDED.equals(action);
                replacing = extras.getBoolean(Intent.EXTRA_REPLACING, false);
            } else if (Intent.ACTION_EXTERNAL_APPLICATIONS_AVAILABLE.equals(action)) {
                added = true;
                pkgList = intent.getStringArrayExtra(Intent.EXTRA_CHANGED_PACKAGE_LIST);
            } else if (Intent.ACTION_EXTERNAL_APPLICATIONS_UNAVAILABLE.equals(action)) {
                added = false;
                pkgList = intent.getStringArrayExtra(Intent.EXTRA_CHANGED_PACKAGE_LIST);
            }

            if (pkgList == null || pkgList.length == 0) {
                return;
            }

            final int uid = extras.getInt(Intent.EXTRA_UID);
            if (added) {
                synchronized (mBackupParticipants) {
                    if (replacing) {
                        // This is the package-replaced case; we just remove the entry
                        // under the old uid and fall through to re-add.
                        removePackageParticipantsLocked(pkgList, uid);
                    }
                    addPackageParticipantsLocked(pkgList);
                }
                // If they're full-backup candidates, add them there instead
                for (String packageName : pkgList) {
                    try {
                        PackageInfo app = mPackageManager.getPackageInfo(packageName, 0);
                        long now = System.currentTimeMillis();
                        if (appGetsFullBackup(app)) {
                            enqueueFullBackup(packageName, now);
                            scheduleNextFullBackupJob();
                        }

                        // Transport maintenance: rebind to known existing transports that have
                        // just been updated; and bind to any newly-installed transport services.
                        synchronized (mTransports) {
                            final TransportConnection conn = mTransportConnections.get(packageName);
                            if (conn != null) {
                                if (MORE_DEBUG) {
                                    Slog.i(TAG, "Transport package changed; rebinding");
                                }
                                bindTransport(conn.mTransport);
                            } else {
                                checkForTransportAndBind(app);
                            }
                        }

                    } catch (NameNotFoundException e) {
                        // doesn't really exist; ignore it
                        if (DEBUG) {
                            Slog.i(TAG, "Can't resolve new app " + packageName);
                        }
                    }
                }

            } else {
                if (replacing) {
                    // The package is being updated.  We'll receive a PACKAGE_ADDED shortly.
                } else {
                    synchronized (mBackupParticipants) {
                        removePackageParticipantsLocked(pkgList, uid);
                    }
                }
            }
        }
    };

    // ----- Track connection to transports service -----
    class TransportConnection implements ServiceConnection {
        ServiceInfo mTransport;

        public TransportConnection(ServiceInfo transport) {
            mTransport = transport;
        }

        @Override
        public void onServiceConnected(ComponentName component, IBinder service) {
            if (DEBUG) Slog.v(TAG, "Connected to transport " + component);
            final String name = component.flattenToShortString();
            try {
                IBackupTransport transport = IBackupTransport.Stub.asInterface(service);
                registerTransport(transport.name(), name, transport);
                EventLog.writeEvent(EventLogTags.BACKUP_TRANSPORT_LIFECYCLE, name, 1);
            } catch (RemoteException e) {
                Slog.e(TAG, "Unable to register transport " + component);
                EventLog.writeEvent(EventLogTags.BACKUP_TRANSPORT_LIFECYCLE, name, 0);
            }
        }

        @Override
        public void onServiceDisconnected(ComponentName component) {
            if (DEBUG) Slog.v(TAG, "Disconnected from transport " + component);
            final String name = component.flattenToShortString();
            EventLog.writeEvent(EventLogTags.BACKUP_TRANSPORT_LIFECYCLE, name, 0);
            registerTransport(null, name, null);
        }
    };

    // Check whether the given package hosts a transport, and bind if so
    void checkForTransportAndBind(PackageInfo pkgInfo) {
        Intent intent = new Intent(mTransportServiceIntent)
                .setPackage(pkgInfo.packageName);
        List<ResolveInfo> hosts = mPackageManager.queryIntentServicesAsUser(
                intent, 0, UserHandle.USER_OWNER);
        final int N = hosts.size();
        for (int i = 0; i < N; i++) {
            final ServiceInfo info = hosts.get(i).serviceInfo;
            tryBindTransport(info);
        }
    }

    // Verify that the service exists and is hosted by a privileged app, then proceed to bind
    boolean tryBindTransport(ServiceInfo info) {
        try {
            PackageInfo packInfo = mPackageManager.getPackageInfo(info.packageName, 0);
            if ((packInfo.applicationInfo.flags & ApplicationInfo.FLAG_PRIVILEGED) != 0) {
                return bindTransport(info);
            } else {
                Slog.w(TAG, "Transport package " + info.packageName + " not privileged");
            }
        } catch (NameNotFoundException e) {
            Slog.w(TAG, "Problem resolving transport package " + info.packageName);
        }
        return false;
    }

    // Actually bind; presumes that we have already validated the transport service
    boolean bindTransport(ServiceInfo transport) {
        ComponentName svcName = new ComponentName(transport.packageName, transport.name);
        if (DEBUG) {
            Slog.i(TAG, "Binding to transport host " + svcName);
        }
        Intent intent = new Intent(mTransportServiceIntent);
        intent.setComponent(svcName);

        TransportConnection connection;
        synchronized (mTransports) {
            connection = mTransportConnections.get(transport.packageName);
            if (null == connection) {
                connection = new TransportConnection(transport);
                mTransportConnections.put(transport.packageName, connection);
            } else {
                // This is a rebind due to package upgrade.  The service won't be
                // automatically relaunched for us until we explicitly rebind, but
                // we need to unbind the now-orphaned original connection.
                mContext.unbindService(connection);
            }
        }
        return mContext.bindServiceAsUser(intent,
                connection, Context.BIND_AUTO_CREATE,
                UserHandle.OWNER);
    }

    // Add the backup agents in the given packages to our set of known backup participants.
    // If 'packageNames' is null, adds all backup agents in the whole system.
    void addPackageParticipantsLocked(String[] packageNames) {
        // Look for apps that define the android:backupAgent attribute
        List<PackageInfo> targetApps = allAgentPackages();
        if (packageNames != null) {
            if (MORE_DEBUG) Slog.v(TAG, "addPackageParticipantsLocked: #" + packageNames.length);
            for (String packageName : packageNames) {
                addPackageParticipantsLockedInner(packageName, targetApps);
            }
        } else {
            if (MORE_DEBUG) Slog.v(TAG, "addPackageParticipantsLocked: all");
            addPackageParticipantsLockedInner(null, targetApps);
        }
    }

    private void addPackageParticipantsLockedInner(String packageName,
            List<PackageInfo> targetPkgs) {
        if (MORE_DEBUG) {
            Slog.v(TAG, "Examining " + packageName + " for backup agent");
        }

        for (PackageInfo pkg : targetPkgs) {
            if (packageName == null || pkg.packageName.equals(packageName)) {
                int uid = pkg.applicationInfo.uid;
                HashSet<String> set = mBackupParticipants.get(uid);
                if (set == null) {
                    set = new HashSet<String>();
                    mBackupParticipants.put(uid, set);
                }
                set.add(pkg.packageName);
                if (MORE_DEBUG) Slog.v(TAG, "Agent found; added");

                // Schedule a backup for it on general principles
                if (MORE_DEBUG) Slog.i(TAG, "Scheduling backup for new app " + pkg.packageName);
                dataChangedImpl(pkg.packageName);
            }
        }
    }

    // Remove the given packages' entries from our known active set.
    void removePackageParticipantsLocked(String[] packageNames, int oldUid) {
        if (packageNames == null) {
            Slog.w(TAG, "removePackageParticipants with null list");
            return;
        }

        if (MORE_DEBUG) Slog.v(TAG, "removePackageParticipantsLocked: uid=" + oldUid
                + " #" + packageNames.length);
        for (String pkg : packageNames) {
            // Known previous UID, so we know which package set to check
            HashSet<String> set = mBackupParticipants.get(oldUid);
            if (set != null && set.contains(pkg)) {
                removePackageFromSetLocked(set, pkg);
                if (set.isEmpty()) {
                    if (MORE_DEBUG) Slog.v(TAG, "  last one of this uid; purging set");
                    mBackupParticipants.remove(oldUid);
                }
            }
        }
    }

    private void removePackageFromSetLocked(final HashSet<String> set,
            final String packageName) {
        if (set.contains(packageName)) {
            // Found it.  Remove this one package from the bookkeeping, and
            // if it's the last participating app under this uid we drop the
            // (now-empty) set as well.
            // Note that we deliberately leave it 'known' in the "ever backed up"
            // bookkeeping so that its current-dataset data will be retrieved
            // if the app is subsequently reinstalled
            if (MORE_DEBUG) Slog.v(TAG, "  removing participant " + packageName);
            set.remove(packageName);
            mPendingBackups.remove(packageName);
        }
    }

    // Returns the set of all applications that define an android:backupAgent attribute
    List<PackageInfo> allAgentPackages() {
        // !!! TODO: cache this and regenerate only when necessary
        int flags = PackageManager.GET_SIGNATURES;
        List<PackageInfo> packages = mPackageManager.getInstalledPackages(flags);
        int N = packages.size();
        for (int a = N-1; a >= 0; a--) {
            PackageInfo pkg = packages.get(a);
            try {
                ApplicationInfo app = pkg.applicationInfo;
                if (((app.flags&ApplicationInfo.FLAG_ALLOW_BACKUP) == 0)
                        || app.backupAgentName == null) {
                    packages.remove(a);
                }
                else {
                    // we will need the shared library path, so look that up and store it here.
                    // This is used implicitly when we pass the PackageInfo object off to
                    // the Activity Manager to launch the app for backup/restore purposes.
                    app = mPackageManager.getApplicationInfo(pkg.packageName,
                            PackageManager.GET_SHARED_LIBRARY_FILES);
                    pkg.applicationInfo.sharedLibraryFiles = app.sharedLibraryFiles;
                }
            } catch (NameNotFoundException e) {
                packages.remove(a);
            }
        }
        return packages;
    }

    // Called from the backup tasks: record that the given app has been successfully
    // backed up at least once.  This includes both key/value and full-data backups
    // through the transport.
    void logBackupComplete(String packageName) {
        if (packageName.equals(PACKAGE_MANAGER_SENTINEL)) return;

        synchronized (mEverStoredApps) {
            if (!mEverStoredApps.add(packageName)) return;

            RandomAccessFile out = null;
            try {
                out = new RandomAccessFile(mEverStored, "rws");
                out.seek(out.length());
                out.writeUTF(packageName);
            } catch (IOException e) {
                Slog.e(TAG, "Can't log backup of " + packageName + " to " + mEverStored);
            } finally {
                try { if (out != null) out.close(); } catch (IOException e) {}
            }
        }
    }

    // Remove our awareness of having ever backed up the given package
    void removeEverBackedUp(String packageName) {
        if (DEBUG) Slog.v(TAG, "Removing backed-up knowledge of " + packageName);
        if (MORE_DEBUG) Slog.v(TAG, "New set:");

        synchronized (mEverStoredApps) {
            // Rewrite the file and rename to overwrite.  If we reboot in the middle,
            // we'll recognize on initialization time that the package no longer
            // exists and fix it up then.
            File tempKnownFile = new File(mBaseStateDir, "processed.new");
            RandomAccessFile known = null;
            try {
                known = new RandomAccessFile(tempKnownFile, "rws");
                mEverStoredApps.remove(packageName);
                for (String s : mEverStoredApps) {
                    known.writeUTF(s);
                    if (MORE_DEBUG) Slog.v(TAG, "    " + s);
                }
                known.close();
                known = null;
                if (!tempKnownFile.renameTo(mEverStored)) {
                    throw new IOException("Can't rename " + tempKnownFile + " to " + mEverStored);
                }
            } catch (IOException e) {
                // Bad: we couldn't create the new copy.  For safety's sake we
                // abandon the whole process and remove all what's-backed-up
                // state entirely, meaning we'll force a backup pass for every
                // participant on the next boot or [re]install.
                Slog.w(TAG, "Error rewriting " + mEverStored, e);
                mEverStoredApps.clear();
                tempKnownFile.delete();
                mEverStored.delete();
            } finally {
                try { if (known != null) known.close(); } catch (IOException e) {}
            }
        }
    }

    // Persistently record the current and ancestral backup tokens as well
    // as the set of packages with data [supposedly] available in the
    // ancestral dataset.
    void writeRestoreTokens() {
        try {
            RandomAccessFile af = new RandomAccessFile(mTokenFile, "rwd");

            // First, the version number of this record, for futureproofing
            af.writeInt(CURRENT_ANCESTRAL_RECORD_VERSION);

            // Write the ancestral and current tokens
            af.writeLong(mAncestralToken);
            af.writeLong(mCurrentToken);

            // Now write the set of ancestral packages
            if (mAncestralPackages == null) {
                af.writeInt(-1);
            } else {
                af.writeInt(mAncestralPackages.size());
                if (DEBUG) Slog.v(TAG, "Ancestral packages:  " + mAncestralPackages.size());
                for (String pkgName : mAncestralPackages) {
                    af.writeUTF(pkgName);
                    if (MORE_DEBUG) Slog.v(TAG, "   " + pkgName);
                }
            }
            af.close();
        } catch (IOException e) {
            Slog.w(TAG, "Unable to write token file:", e);
        }
    }

    // Return the given transport
    private IBackupTransport getTransport(String transportName) {
        synchronized (mTransports) {
            IBackupTransport transport = mTransports.get(transportName);
            if (transport == null) {
                Slog.w(TAG, "Requested unavailable transport: " + transportName);
            }
            return transport;
        }
    }

    // fire off a backup agent, blocking until it attaches or times out
    IBackupAgent bindToAgentSynchronous(ApplicationInfo app, int mode) {
        IBackupAgent agent = null;
        synchronized(mAgentConnectLock) {
            mConnecting = true;
            mConnectedAgent = null;
            try {
                if (mActivityManager.bindBackupAgent(app, mode)) {
                    Slog.d(TAG, "awaiting agent for " + app);

                    // success; wait for the agent to arrive
                    // only wait 10 seconds for the bind to happen
                    long timeoutMark = System.currentTimeMillis() + TIMEOUT_INTERVAL;
                    while (mConnecting && mConnectedAgent == null
                            && (System.currentTimeMillis() < timeoutMark)) {
                        try {
                            mAgentConnectLock.wait(5000);
                        } catch (InterruptedException e) {
                            // just bail
                            if (DEBUG) Slog.w(TAG, "Interrupted: " + e);
                            mActivityManager.clearPendingBackup();
                            return null;
                        }
                    }

                    // if we timed out with no connect, abort and move on
                    if (mConnecting == true) {
                        Slog.w(TAG, "Timeout waiting for agent " + app);
                        mActivityManager.clearPendingBackup();
                        return null;
                    }
                    if (DEBUG) Slog.i(TAG, "got agent " + mConnectedAgent);
                    agent = mConnectedAgent;
                }
            } catch (RemoteException e) {
                // can't happen - ActivityManager is local
            }
        }
        return agent;
    }

    // clear an application's data, blocking until the operation completes or times out
    void clearApplicationDataSynchronous(String packageName) {
        // Don't wipe packages marked allowClearUserData=false
        try {
            PackageInfo info = mPackageManager.getPackageInfo(packageName, 0);
            if ((info.applicationInfo.flags & ApplicationInfo.FLAG_ALLOW_CLEAR_USER_DATA) == 0) {
                if (MORE_DEBUG) Slog.i(TAG, "allowClearUserData=false so not wiping "
                        + packageName);
                return;
            }
        } catch (NameNotFoundException e) {
            Slog.w(TAG, "Tried to clear data for " + packageName + " but not found");
            return;
        }

        ClearDataObserver observer = new ClearDataObserver();

        synchronized(mClearDataLock) {
            mClearingData = true;
            try {
                mActivityManager.clearApplicationUserData(packageName, observer, 0);
            } catch (RemoteException e) {
                // can't happen because the activity manager is in this process
            }

            // only wait 10 seconds for the clear data to happen
            long timeoutMark = System.currentTimeMillis() + TIMEOUT_INTERVAL;
            while (mClearingData && (System.currentTimeMillis() < timeoutMark)) {
                try {
                    mClearDataLock.wait(5000);
                } catch (InterruptedException e) {
                    // won't happen, but still.
                    mClearingData = false;
                }
            }
        }
    }

    class ClearDataObserver extends IPackageDataObserver.Stub {
        public void onRemoveCompleted(String packageName, boolean succeeded) {
            synchronized(mClearDataLock) {
                mClearingData = false;
                mClearDataLock.notifyAll();
            }
        }
    }

    // Get the restore-set token for the best-available restore set for this package:
    // the active set if possible, else the ancestral one.  Returns zero if none available.
    long getAvailableRestoreToken(String packageName) {
        long token = mAncestralToken;
        synchronized (mQueueLock) {
            if (mEverStoredApps.contains(packageName)) {
                token = mCurrentToken;
            }
        }
        return token;
    }

    // -----
    // Interface and methods used by the asynchronous-with-timeout backup/restore operations

    interface BackupRestoreTask {
        // Execute one tick of whatever state machine the task implements
        void execute();

        // An operation that wanted a callback has completed
        void operationComplete();

        // An operation that wanted a callback has timed out
        void handleTimeout();
    }

    void prepareOperationTimeout(int token, long interval, BackupRestoreTask callback) {
        if (MORE_DEBUG) Slog.v(TAG, "starting timeout: token=" + Integer.toHexString(token)
                + " interval=" + interval);
        synchronized (mCurrentOpLock) {
            mCurrentOperations.put(token, new Operation(OP_PENDING, callback));

            Message msg = mBackupHandler.obtainMessage(MSG_TIMEOUT, token, 0, callback);
            mBackupHandler.sendMessageDelayed(msg, interval);
        }
    }

    // synchronous waiter case
    boolean waitUntilOperationComplete(int token) {
        if (MORE_DEBUG) Slog.i(TAG, "Blocking until operation complete for "
                + Integer.toHexString(token));
        int finalState = OP_PENDING;
        Operation op = null;
        synchronized (mCurrentOpLock) {
            while (true) {
                op = mCurrentOperations.get(token);
                if (op == null) {
                    // mysterious disappearance: treat as success with no callback
                    break;
                } else {
                    if (op.state == OP_PENDING) {
                        try {
                            mCurrentOpLock.wait();
                        } catch (InterruptedException e) {}
                        // When the wait is notified we loop around and recheck the current state
                    } else {
                        // No longer pending; we're done
                        finalState = op.state;
                        break;
                    }
                }
            }
        }

        mBackupHandler.removeMessages(MSG_TIMEOUT);
        if (MORE_DEBUG) Slog.v(TAG, "operation " + Integer.toHexString(token)
                + " complete: finalState=" + finalState);
        return finalState == OP_ACKNOWLEDGED;
    }

    void handleTimeout(int token, Object obj) {
        // Notify any synchronous waiters
        Operation op = null;
        synchronized (mCurrentOpLock) {
            op = mCurrentOperations.get(token);
            if (MORE_DEBUG) {
                if (op == null) Slog.w(TAG, "Timeout of token " + Integer.toHexString(token)
                        + " but no op found");
            }
            int state = (op != null) ? op.state : OP_TIMEOUT;
            if (state == OP_PENDING) {
                if (DEBUG) Slog.v(TAG, "TIMEOUT: token=" + Integer.toHexString(token));
                op.state = OP_TIMEOUT;
                mCurrentOperations.put(token, op);
            }
            mCurrentOpLock.notifyAll();
        }

        // If there's a TimeoutHandler for this event, call it
        if (op != null && op.callback != null) {
            op.callback.handleTimeout();
        }
    }

    // ----- Back up a set of applications via a worker thread -----

    enum BackupState {
        INITIAL,
        RUNNING_QUEUE,
        FINAL
    }

    class PerformBackupTask implements BackupRestoreTask {
        private static final String TAG = "PerformBackupTask";

        IBackupTransport mTransport;
        ArrayList<BackupRequest> mQueue;
        ArrayList<BackupRequest> mOriginalQueue;
        File mStateDir;
        File mJournal;
        BackupState mCurrentState;

        // carried information about the current in-flight operation
        IBackupAgent mAgentBinder;
        PackageInfo mCurrentPackage;
        File mSavedStateName;
        File mBackupDataName;
        File mNewStateName;
        ParcelFileDescriptor mSavedState;
        ParcelFileDescriptor mBackupData;
        ParcelFileDescriptor mNewState;
        int mStatus;
        boolean mFinished;

        public PerformBackupTask(IBackupTransport transport, String dirName,
                ArrayList<BackupRequest> queue, File journal) {
            mTransport = transport;
            mOriginalQueue = queue;
            mJournal = journal;

            mStateDir = new File(mBaseStateDir, dirName);

            mCurrentState = BackupState.INITIAL;
            mFinished = false;

            addBackupTrace("STATE => INITIAL");
        }

        // Main entry point: perform one chunk of work, updating the state as appropriate
        // and reposting the next chunk to the primary backup handler thread.
        @Override
        public void execute() {
            switch (mCurrentState) {
                case INITIAL:
                    beginBackup();
                    break;

                case RUNNING_QUEUE:
                    invokeNextAgent();
                    break;

                case FINAL:
                    if (!mFinished) finalizeBackup();
                    else {
                        Slog.e(TAG, "Duplicate finish");
                    }
                    mFinished = true;
                    break;
            }
        }

        // We're starting a backup pass.  Initialize the transport and send
        // the PM metadata blob if we haven't already.
        void beginBackup() {
            if (DEBUG_BACKUP_TRACE) {
                clearBackupTrace();
                StringBuilder b = new StringBuilder(256);
                b.append("beginBackup: [");
                for (BackupRequest req : mOriginalQueue) {
                    b.append(' ');
                    b.append(req.packageName);
                }
                b.append(" ]");
                addBackupTrace(b.toString());
            }

            mAgentBinder = null;
            mStatus = BackupTransport.TRANSPORT_OK;

            // Sanity check: if the queue is empty we have no work to do.
            if (mOriginalQueue.isEmpty()) {
                Slog.w(TAG, "Backup begun with an empty queue - nothing to do.");
                addBackupTrace("queue empty at begin");
                executeNextState(BackupState.FINAL);
                return;
            }

            // We need to retain the original queue contents in case of transport
            // failure, but we want a working copy that we can manipulate along
            // the way.
            mQueue = (ArrayList<BackupRequest>) mOriginalQueue.clone();

            if (DEBUG) Slog.v(TAG, "Beginning backup of " + mQueue.size() + " targets");

            File pmState = new File(mStateDir, PACKAGE_MANAGER_SENTINEL);
            try {
                final String transportName = mTransport.transportDirName();
                EventLog.writeEvent(EventLogTags.BACKUP_START, transportName);

                // If we haven't stored package manager metadata yet, we must init the transport.
                if (mStatus == BackupTransport.TRANSPORT_OK && pmState.length() <= 0) {
                    Slog.i(TAG, "Initializing (wiping) backup state and transport storage");
                    addBackupTrace("initializing transport " + transportName);
                    resetBackupState(mStateDir);  // Just to make sure.
                    mStatus = mTransport.initializeDevice();

                    addBackupTrace("transport.initializeDevice() == " + mStatus);
                    if (mStatus == BackupTransport.TRANSPORT_OK) {
                        EventLog.writeEvent(EventLogTags.BACKUP_INITIALIZE);
                    } else {
                        EventLog.writeEvent(EventLogTags.BACKUP_TRANSPORT_FAILURE, "(initialize)");
                        Slog.e(TAG, "Transport error in initializeDevice()");
                    }
                }

                // The package manager doesn't have a proper <application> etc, but since
                // it's running here in the system process we can just set up its agent
                // directly and use a synthetic BackupRequest.  We always run this pass
                // because it's cheap and this way we guarantee that we don't get out of
                // step even if we're selecting among various transports at run time.
                if (mStatus == BackupTransport.TRANSPORT_OK) {
                    PackageManagerBackupAgent pmAgent = new PackageManagerBackupAgent(
                            mPackageManager);
                    mStatus = invokeAgentForBackup(PACKAGE_MANAGER_SENTINEL,
                            IBackupAgent.Stub.asInterface(pmAgent.onBind()), mTransport);
                    addBackupTrace("PMBA invoke: " + mStatus);

                    // Because the PMBA is a local instance, it has already executed its
                    // backup callback and returned.  Blow away the lingering (spurious)
                    // pending timeout message for it.
                    mBackupHandler.removeMessages(MSG_TIMEOUT);
                }

                if (mStatus == BackupTransport.TRANSPORT_NOT_INITIALIZED) {
                    // The backend reports that our dataset has been wiped.  Note this in
                    // the event log; the no-success code below will reset the backup
                    // state as well.
                    EventLog.writeEvent(EventLogTags.BACKUP_RESET, mTransport.transportDirName());
                }
            } catch (Exception e) {
                Slog.e(TAG, "Error in backup thread", e);
                addBackupTrace("Exception in backup thread: " + e);
                mStatus = BackupTransport.TRANSPORT_ERROR;
            } finally {
                // If we've succeeded so far, invokeAgentForBackup() will have run the PM
                // metadata and its completion/timeout callback will continue the state
                // machine chain.  If it failed that won't happen; we handle that now.
                addBackupTrace("exiting prelim: " + mStatus);
                if (mStatus != BackupTransport.TRANSPORT_OK) {
                    // if things went wrong at this point, we need to
                    // restage everything and try again later.
                    resetBackupState(mStateDir);  // Just to make sure.
                    executeNextState(BackupState.FINAL);
                }
            }
        }

        // Transport has been initialized and the PM metadata submitted successfully
        // if that was warranted.  Now we process the single next thing in the queue.
        void invokeNextAgent() {
            mStatus = BackupTransport.TRANSPORT_OK;
            addBackupTrace("invoke q=" + mQueue.size());

            // Sanity check that we have work to do.  If not, skip to the end where
            // we reestablish the wakelock invariants etc.
            if (mQueue.isEmpty()) {
                if (DEBUG) Slog.i(TAG, "queue now empty");
                executeNextState(BackupState.FINAL);
                return;
            }

            // pop the entry we're going to process on this step
            BackupRequest request = mQueue.get(0);
            mQueue.remove(0);

            Slog.d(TAG, "starting agent for backup of " + request);
            addBackupTrace("launch agent for " + request.packageName);

            // Verify that the requested app exists; it might be something that
            // requested a backup but was then uninstalled.  The request was
            // journalled and rather than tamper with the journal it's safer
            // to sanity-check here.  This also gives us the classname of the
            // package's backup agent.
            try {
                mCurrentPackage = mPackageManager.getPackageInfo(request.packageName,
                        PackageManager.GET_SIGNATURES);
                if (mCurrentPackage.applicationInfo.backupAgentName == null) {
                    // The manifest has changed but we had a stale backup request pending.
                    // This won't happen again because the app won't be requesting further
                    // backups.
                    Slog.i(TAG, "Package " + request.packageName
                            + " no longer supports backup; skipping");
                    addBackupTrace("skipping - no agent, completion is noop");
                    executeNextState(BackupState.RUNNING_QUEUE);
                    return;
                }

                if ((mCurrentPackage.applicationInfo.flags & ApplicationInfo.FLAG_STOPPED) != 0) {
                    // The app has been force-stopped or cleared or just installed,
                    // and not yet launched out of that state, so just as it won't
                    // receive broadcasts, we won't run it for backup.
                    addBackupTrace("skipping - stopped");
                    executeNextState(BackupState.RUNNING_QUEUE);
                    return;
                }

                IBackupAgent agent = null;
                try {
                    mWakelock.setWorkSource(new WorkSource(mCurrentPackage.applicationInfo.uid));
                    agent = bindToAgentSynchronous(mCurrentPackage.applicationInfo,
                            IApplicationThread.BACKUP_MODE_INCREMENTAL);
                    addBackupTrace("agent bound; a? = " + (agent != null));
                    if (agent != null) {
                        mAgentBinder = agent;
                        mStatus = invokeAgentForBackup(request.packageName, agent, mTransport);
                        // at this point we'll either get a completion callback from the
                        // agent, or a timeout message on the main handler.  either way, we're
                        // done here as long as we're successful so far.
                    } else {
                        // Timeout waiting for the agent
                        mStatus = BackupTransport.AGENT_ERROR;
                    }
                } catch (SecurityException ex) {
                    // Try for the next one.
                    Slog.d(TAG, "error in bind/backup", ex);
                    mStatus = BackupTransport.AGENT_ERROR;
                            addBackupTrace("agent SE");
                }
            } catch (NameNotFoundException e) {
                Slog.d(TAG, "Package does not exist; skipping");
                addBackupTrace("no such package");
                mStatus = BackupTransport.AGENT_UNKNOWN;
            } finally {
                mWakelock.setWorkSource(null);

                // If there was an agent error, no timeout/completion handling will occur.
                // That means we need to direct to the next state ourselves.
                if (mStatus != BackupTransport.TRANSPORT_OK) {
                    BackupState nextState = BackupState.RUNNING_QUEUE;
                    mAgentBinder = null;

                    // An agent-level failure means we reenqueue this one agent for
                    // a later retry, but otherwise proceed normally.
                    if (mStatus == BackupTransport.AGENT_ERROR) {
                        if (MORE_DEBUG) Slog.i(TAG, "Agent failure for " + request.packageName
                                + " - restaging");
                        dataChangedImpl(request.packageName);
                        mStatus = BackupTransport.TRANSPORT_OK;
                        if (mQueue.isEmpty()) nextState = BackupState.FINAL;
                    } else if (mStatus == BackupTransport.AGENT_UNKNOWN) {
                        // Failed lookup of the app, so we couldn't bring up an agent, but
                        // we're otherwise fine.  Just drop it and go on to the next as usual.
                        mStatus = BackupTransport.TRANSPORT_OK;
                    } else {
                        // Transport-level failure means we reenqueue everything
                        revertAndEndBackup();
                        nextState = BackupState.FINAL;
                    }

                    executeNextState(nextState);
                } else {
                    // success case
                    addBackupTrace("expecting completion/timeout callback");
                }
            }
        }

        void finalizeBackup() {
            addBackupTrace("finishing");

            // Either backup was successful, in which case we of course do not need
            // this pass's journal any more; or it failed, in which case we just
            // re-enqueued all of these packages in the current active journal.
            // Either way, we no longer need this pass's journal.
            if (mJournal != null && !mJournal.delete()) {
                Slog.e(TAG, "Unable to remove backup journal file " + mJournal);
            }

            // If everything actually went through and this is the first time we've
            // done a backup, we can now record what the current backup dataset token
            // is.
            if ((mCurrentToken == 0) && (mStatus == BackupTransport.TRANSPORT_OK)) {
                addBackupTrace("success; recording token");
                try {
                    mCurrentToken = mTransport.getCurrentRestoreSet();
                    writeRestoreTokens();
                } catch (RemoteException e) {
                    // nothing for it at this point, unfortunately, but this will be
                    // recorded the next time we fully succeed.
                    addBackupTrace("transport threw returning token");
                }
            }

            // Set up the next backup pass - at this point we can set mBackupRunning
            // to false to allow another pass to fire, because we're done with the
            // state machine sequence and the wakelock is refcounted.
            synchronized (mQueueLock) {
                mBackupRunning = false;
                if (mStatus == BackupTransport.TRANSPORT_NOT_INITIALIZED) {
                    // Make sure we back up everything and perform the one-time init
                    clearMetadata();
                    if (DEBUG) Slog.d(TAG, "Server requires init; rerunning");
                    addBackupTrace("init required; rerunning");
                    backupNow();
                }
            }

            // Only once we're entirely finished do we release the wakelock
            clearBackupTrace();
            Slog.i(BackupManagerService.TAG, "Backup pass finished.");
            mWakelock.release();
        }

        // Remove the PM metadata state. This will generate an init on the next pass.
        void clearMetadata() {
            final File pmState = new File(mStateDir, PACKAGE_MANAGER_SENTINEL);
            if (pmState.exists()) pmState.delete();
        }

        // Invoke an agent's doBackup() and start a timeout message spinning on the main
        // handler in case it doesn't get back to us.
        int invokeAgentForBackup(String packageName, IBackupAgent agent,
                IBackupTransport transport) {
            if (DEBUG) Slog.d(TAG, "invokeAgentForBackup on " + packageName);
            addBackupTrace("invoking " + packageName);

            mSavedStateName = new File(mStateDir, packageName);
            mBackupDataName = new File(mDataDir, packageName + ".data");
            mNewStateName = new File(mStateDir, packageName + ".new");
            if (MORE_DEBUG) Slog.d(TAG, "data file: " + mBackupDataName);

            mSavedState = null;
            mBackupData = null;
            mNewState = null;

            final int token = generateToken();
            try {
                // Look up the package info & signatures.  This is first so that if it
                // throws an exception, there's no file setup yet that would need to
                // be unraveled.
                if (packageName.equals(PACKAGE_MANAGER_SENTINEL)) {
                    // The metadata 'package' is synthetic; construct one and make
                    // sure our global state is pointed at it
                    mCurrentPackage = new PackageInfo();
                    mCurrentPackage.packageName = packageName;
                }

                // In a full backup, we pass a null ParcelFileDescriptor as
                // the saved-state "file". This is by definition an incremental,
                // so we build a saved state file to pass.
                mSavedState = ParcelFileDescriptor.open(mSavedStateName,
                        ParcelFileDescriptor.MODE_READ_ONLY |
                        ParcelFileDescriptor.MODE_CREATE);  // Make an empty file if necessary

                mBackupData = ParcelFileDescriptor.open(mBackupDataName,
                        ParcelFileDescriptor.MODE_READ_WRITE |
                        ParcelFileDescriptor.MODE_CREATE |
                        ParcelFileDescriptor.MODE_TRUNCATE);

                if (!SELinux.restorecon(mBackupDataName)) {
                    Slog.e(TAG, "SELinux restorecon failed on " + mBackupDataName);
                }

                mNewState = ParcelFileDescriptor.open(mNewStateName,
                        ParcelFileDescriptor.MODE_READ_WRITE |
                        ParcelFileDescriptor.MODE_CREATE |
                        ParcelFileDescriptor.MODE_TRUNCATE);

                // Initiate the target's backup pass
                addBackupTrace("setting timeout");
                prepareOperationTimeout(token, TIMEOUT_BACKUP_INTERVAL, this);
                addBackupTrace("calling agent doBackup()");
                agent.doBackup(mSavedState, mBackupData, mNewState, token, mBackupManagerBinder);
            } catch (Exception e) {
                Slog.e(TAG, "Error invoking for backup on " + packageName);
                addBackupTrace("exception: " + e);
                EventLog.writeEvent(EventLogTags.BACKUP_AGENT_FAILURE, packageName,
                        e.toString());
                agentErrorCleanup();
                return BackupTransport.AGENT_ERROR;
            }

            // At this point the agent is off and running.  The next thing to happen will
            // either be a callback from the agent, at which point we'll process its data
            // for transport, or a timeout.  Either way the next phase will happen in
            // response to the TimeoutHandler interface callbacks.
            addBackupTrace("invoke success");
            return BackupTransport.TRANSPORT_OK;
        }

        public void failAgent(IBackupAgent agent, String message) {
            try {
                agent.fail(message);
            } catch (Exception e) {
                Slog.w(TAG, "Error conveying failure to " + mCurrentPackage.packageName);
            }
        }

        // SHA-1 a byte array and return the result in hex
        private String SHA1Checksum(byte[] input) {
            final byte[] checksum;
            try {
                MessageDigest md = MessageDigest.getInstance("SHA-1");
                checksum = md.digest(input);
            } catch (NoSuchAlgorithmException e) {
                Slog.e(TAG, "Unable to use SHA-1!");
                return "00";
            }

            StringBuffer sb = new StringBuffer(checksum.length * 2);
            for (int i = 0; i < checksum.length; i++) {
                sb.append(Integer.toHexString(checksum[i]));
            }
            return sb.toString();
        }

        private void writeWidgetPayloadIfAppropriate(FileDescriptor fd, String pkgName)
                throws IOException {
            byte[] widgetState = AppWidgetBackupBridge.getWidgetState(pkgName,
                    UserHandle.USER_OWNER);
            // has the widget state changed since last time?
            final File widgetFile = new File(mStateDir, pkgName + "_widget");
            final boolean priorStateExists = widgetFile.exists();

            if (MORE_DEBUG) {
                if (priorStateExists || widgetState != null) {
                    Slog.i(TAG, "Checking widget update: state=" + (widgetState != null)
                            + " prior=" + priorStateExists);
                }
            }

            if (!priorStateExists && widgetState == null) {
                // no prior state, no new state => nothing to do
                return;
            }

            // if the new state is not null, we might need to compare checksums to
            // determine whether to update the widget blob in the archive.  If the
            // widget state *is* null, we know a priori at this point that we simply
            // need to commit a deletion for it.
            String newChecksum = null;
            if (widgetState != null) {
                newChecksum = SHA1Checksum(widgetState);
                if (priorStateExists) {
                    final String priorChecksum;
                    try (
                        FileInputStream fin = new FileInputStream(widgetFile);
                        DataInputStream in = new DataInputStream(fin)
                    ) {
                        priorChecksum = in.readUTF();
                    }
                    if (Objects.equals(newChecksum, priorChecksum)) {
                        // Same checksum => no state change => don't rewrite the widget data
                        return;
                    }
                }
            } // else widget state *became* empty, so we need to commit a deletion

            BackupDataOutput out = new BackupDataOutput(fd);
            if (widgetState != null) {
                try (
                    FileOutputStream fout = new FileOutputStream(widgetFile);
                    DataOutputStream stateOut = new DataOutputStream(fout)
                ) {
                    stateOut.writeUTF(newChecksum);
                }

                out.writeEntityHeader(KEY_WIDGET_STATE, widgetState.length);
                out.writeEntityData(widgetState, widgetState.length);
            } else {
                // Widget state for this app has been removed; commit a deletion
                out.writeEntityHeader(KEY_WIDGET_STATE, -1);
                widgetFile.delete();
            }
        }

        @Override
        public void operationComplete() {
            // Okay, the agent successfully reported back to us!
            final String pkgName = mCurrentPackage.packageName;
            final long filepos = mBackupDataName.length();
            FileDescriptor fd = mBackupData.getFileDescriptor();
            try {
                // If it's a 3rd party app, see whether they wrote any protected keys
                // and complain mightily if they are attempting shenanigans.
                if (mCurrentPackage.applicationInfo != null &&
                        (mCurrentPackage.applicationInfo.flags&ApplicationInfo.FLAG_SYSTEM) == 0) {
                    ParcelFileDescriptor readFd = ParcelFileDescriptor.open(mBackupDataName,
                            ParcelFileDescriptor.MODE_READ_ONLY);
                    BackupDataInput in = new BackupDataInput(readFd.getFileDescriptor());
                    try {
                        while (in.readNextHeader()) {
                            final String key = in.getKey();
                            if (key != null && key.charAt(0) >= 0xff00) {
                                // Not okay: crash them and bail.
                                failAgent(mAgentBinder, "Illegal backup key: " + key);
                                addBackupTrace("illegal key " + key + " from " + pkgName);
                                EventLog.writeEvent(EventLogTags.BACKUP_AGENT_FAILURE, pkgName,
                                        "bad key");
                                mBackupHandler.removeMessages(MSG_TIMEOUT);
                                agentErrorCleanup();
                                // agentErrorCleanup() implicitly executes next state properly
                                return;
                            }
                            in.skipEntityData();
                        }
                    } finally {
                        if (readFd != null) {
                            readFd.close();
                        }
                    }
                }

                // Piggyback the widget state payload, if any
                writeWidgetPayloadIfAppropriate(fd, pkgName);
            } 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 {
                    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 "
                    + pkgName);
            mBackupHandler.removeMessages(MSG_TIMEOUT);
            clearAgentState();
            addBackupTrace("operation complete");

            ParcelFileDescriptor backupData = null;
            mStatus = BackupTransport.TRANSPORT_OK;
            try {
                int size = (int) mBackupDataName.length();
                if (size > 0) {
                    if (mStatus == BackupTransport.TRANSPORT_OK) {
                        backupData = ParcelFileDescriptor.open(mBackupDataName,
                                ParcelFileDescriptor.MODE_READ_ONLY);
                        addBackupTrace("sending data to transport");
                        mStatus = mTransport.performBackup(mCurrentPackage, backupData);
                    }

                    // TODO - We call finishBackup() for each application backed up, because
                    // we need to know now whether it succeeded or failed.  Instead, we should
                    // hold off on finishBackup() until the end, which implies holding off on
                    // renaming *all* the output state files (see below) until that happens.

                    addBackupTrace("data delivered: " + mStatus);
                    if (mStatus == BackupTransport.TRANSPORT_OK) {
                        addBackupTrace("finishing op on transport");
                        mStatus = mTransport.finishBackup();
                        addBackupTrace("finished: " + mStatus);
                    } else if (mStatus == BackupTransport.TRANSPORT_PACKAGE_REJECTED) {
                        addBackupTrace("transport rejected package");
                    }
                } else {
                    if (DEBUG) Slog.i(TAG, "no backup data written; not calling transport");
                    addBackupTrace("no data to send");
                }

                if (mStatus == BackupTransport.TRANSPORT_OK) {
                    // After successful transport, delete the now-stale data
                    // and juggle the files so that next time we supply the agent
                    // with the new state file it just created.
                    mBackupDataName.delete();
                    mNewStateName.renameTo(mSavedStateName);
                    EventLog.writeEvent(EventLogTags.BACKUP_PACKAGE, pkgName, size);
                    logBackupComplete(pkgName);
                } else if (mStatus == BackupTransport.TRANSPORT_PACKAGE_REJECTED) {
                    // The transport has rejected backup of this specific package.  Roll it
                    // back but proceed with running the rest of the queue.
                    mBackupDataName.delete();
                    mNewStateName.delete();
                    EventLogTags.writeBackupAgentFailure(pkgName, "Transport rejected");
                } else {
                    // Actual transport-level failure to communicate the data to the backend
                    EventLog.writeEvent(EventLogTags.BACKUP_TRANSPORT_FAILURE, pkgName);
                }
            } catch (Exception e) {
                Slog.e(TAG, "Transport error backing up " + pkgName, e);
                EventLog.writeEvent(EventLogTags.BACKUP_TRANSPORT_FAILURE, pkgName);
                mStatus = BackupTransport.TRANSPORT_ERROR;
            } finally {
                try { if (backupData != null) backupData.close(); } catch (IOException e) {}
            }

            final BackupState nextState;
            if (mStatus == BackupTransport.TRANSPORT_OK
                    || mStatus == BackupTransport.TRANSPORT_PACKAGE_REJECTED) {
                // Success or single-package rejection.  Proceed with the next app if any,
                // otherwise we're done.
                nextState = (mQueue.isEmpty()) ? BackupState.FINAL : BackupState.RUNNING_QUEUE;
            } else {
                // Any other error here indicates a transport-level failure.  That means
                // we need to halt everything and reschedule everything for next time.
                revertAndEndBackup();
                nextState = BackupState.FINAL;
            }

            executeNextState(nextState);
        }

        @Override
        public void handleTimeout() {
            // Whoops, the current agent timed out running doBackup().  Tidy up and restage
            // it for the next time we run a backup pass.
            // !!! TODO: keep track of failure counts per agent, and blacklist those which
            // fail repeatedly (i.e. have proved themselves to be buggy).
            Slog.e(TAG, "Timeout backing up " + mCurrentPackage.packageName);
            EventLog.writeEvent(EventLogTags.BACKUP_AGENT_FAILURE, mCurrentPackage.packageName,
                    "timeout");
            addBackupTrace("timeout of " + mCurrentPackage.packageName);
            agentErrorCleanup();
            dataChangedImpl(mCurrentPackage.packageName);
        }

        void revertAndEndBackup() {
            if (MORE_DEBUG) Slog.i(TAG, "Reverting backup queue - restaging everything");
            addBackupTrace("transport error; reverting");
            for (BackupRequest request : mOriginalQueue) {
                dataChangedImpl(request.packageName);
            }
            // We also want to reset the backup schedule based on whatever
            // the transport suggests by way of retry/backoff time.
            restartBackupAlarm();
        }

        void agentErrorCleanup() {
            mBackupDataName.delete();
            mNewStateName.delete();
            clearAgentState();

            executeNextState(mQueue.isEmpty() ? BackupState.FINAL : BackupState.RUNNING_QUEUE);
        }

        // Cleanup common to both success and failure cases
        void clearAgentState() {
            try { if (mSavedState != null) mSavedState.close(); } catch (IOException e) {}
            try { if (mBackupData != null) mBackupData.close(); } catch (IOException e) {}
            try { if (mNewState != null) mNewState.close(); } catch (IOException e) {}
            synchronized (mCurrentOpLock) {
                // Current-operation callback handling requires the validity of these various
                // bits of internal state as an invariant of the operation still being live.
                // This means we make sure to clear all of the state in unison inside the lock.
                mCurrentOperations.clear();
                mSavedState = mBackupData = mNewState = null;
            }

            // If this was a pseudopackage there's no associated Activity Manager state
            if (mCurrentPackage.applicationInfo != null) {
                addBackupTrace("unbinding " + mCurrentPackage.packageName);
                try {  // unbind even on timeout, just in case
                    mActivityManager.unbindBackupAgent(mCurrentPackage.applicationInfo);
                } catch (RemoteException e) { /* can't happen; activity manager is local */ }
            }
        }

        void restartBackupAlarm() {
            addBackupTrace("setting backup trigger");
            synchronized (mQueueLock) {
                try {
                    startBackupAlarmsLocked(mTransport.requestBackupTime());
                } catch (RemoteException e) { /* cannot happen */ }
            }
        }

        void executeNextState(BackupState nextState) {
            if (MORE_DEBUG) Slog.i(TAG, " => executing next step on "
                    + this + " nextState=" + nextState);
            addBackupTrace("executeNextState => " + nextState);
            mCurrentState = nextState;
            Message msg = mBackupHandler.obtainMessage(MSG_BACKUP_RESTORE_STEP, this);
            mBackupHandler.sendMessage(msg);
        }
    }


    // ----- Full backup/restore to a file/socket -----

    class FullBackupObbConnection implements ServiceConnection {
        volatile IObbBackupService mService;

        FullBackupObbConnection() {
            mService = null;
        }

        public void establish() {
            if (DEBUG) Slog.i(TAG, "Initiating bind of OBB service on " + this);
            Intent obbIntent = new Intent().setComponent(new ComponentName(
                    "com.android.sharedstoragebackup",
                    "com.android.sharedstoragebackup.ObbBackupService"));
            BackupManagerService.this.mContext.bindService(
                    obbIntent, this, Context.BIND_AUTO_CREATE);
        }

        public void tearDown() {
            BackupManagerService.this.mContext.unbindService(this);
        }

        public boolean backupObbs(PackageInfo pkg, OutputStream out) {
            boolean success = false;
            waitForConnection();

            ParcelFileDescriptor[] pipes = null;
            try {
                pipes = ParcelFileDescriptor.createPipe();
                int token = generateToken();
                prepareOperationTimeout(token, TIMEOUT_FULL_BACKUP_INTERVAL, null);
                mService.backupObbs(pkg.packageName, pipes[1], token, mBackupManagerBinder);
                routeSocketDataToOutput(pipes[0], out);
                success = waitUntilOperationComplete(token);
            } catch (Exception e) {
                Slog.w(TAG, "Unable to back up OBBs for " + pkg, e);
            } finally {
                try {
                    out.flush();
                    if (pipes != null) {
                        if (pipes[0] != null) pipes[0].close();
                        if (pipes[1] != null) pipes[1].close();
                    }
                } catch (IOException e) {
                    Slog.w(TAG, "I/O error closing down OBB backup", e);
                }
            }
            return success;
        }

        public void restoreObbFile(String pkgName, ParcelFileDescriptor data,
                long fileSize, int type, String path, long mode, long mtime,
                int token, IBackupManager callbackBinder) {
            waitForConnection();

            try {
                mService.restoreObbFile(pkgName, data, fileSize, type, path, mode, mtime,
                        token, callbackBinder);
            } catch (Exception e) {
                Slog.w(TAG, "Unable to restore OBBs for " + pkgName, e);
            }
        }

        private void waitForConnection() {
            synchronized (this) {
                while (mService == null) {
                    if (DEBUG) Slog.i(TAG, "...waiting for OBB service binding...");
                    try {
                        this.wait();
                    } catch (InterruptedException e) { /* never interrupted */ }
                }
                if (DEBUG) Slog.i(TAG, "Connected to OBB service; continuing");
            }
        }

        @Override
        public void onServiceConnected(ComponentName name, IBinder service) {
            synchronized (this) {
                mService = IObbBackupService.Stub.asInterface(service);
                if (DEBUG) Slog.i(TAG, "OBB service connection " + mService
                        + " connected on " + this);
                this.notifyAll();
            }
        }

        @Override
        public void onServiceDisconnected(ComponentName name) {
            synchronized (this) {
                mService = null;
                if (DEBUG) Slog.i(TAG, "OBB service connection disconnected on " + this);
                this.notifyAll();
            }
        }

    }

    private void routeSocketDataToOutput(ParcelFileDescriptor inPipe, OutputStream out)
            throws IOException {
        FileInputStream raw = new FileInputStream(inPipe.getFileDescriptor());
        DataInputStream in = new DataInputStream(raw);

        byte[] buffer = new byte[32 * 1024];
        int chunkTotal;
        while ((chunkTotal = in.readInt()) > 0) {
            while (chunkTotal > 0) {
                int toRead = (chunkTotal > buffer.length) ? buffer.length : chunkTotal;
                int nRead = in.read(buffer, 0, toRead);
                out.write(buffer, 0, nRead);
                chunkTotal -= nRead;
            }
        }
    }

    // Core logic for performing one package's full backup, gathering the tarball from the
    // application and emitting it to the designated OutputStream.
    class FullBackupEngine {
        OutputStream mOutput;
        IFullBackupRestoreObserver mObserver;
        File mFilesDir;
        File mManifestFile;
        File mMetadataFile;
        boolean mIncludeApks;

        class FullBackupRunner implements Runnable {
            PackageInfo mPackage;
            byte[] mWidgetData;
            IBackupAgent mAgent;
            ParcelFileDescriptor mPipe;
            int mToken;
            boolean mSendApk;
            boolean mWriteManifest;

            FullBackupRunner(PackageInfo pack, IBackupAgent agent, ParcelFileDescriptor pipe,
                    int token, boolean sendApk, boolean writeManifest, byte[] widgetData)
                            throws IOException {
                mPackage = pack;
                mWidgetData = widgetData;
                mAgent = agent;
                mPipe = ParcelFileDescriptor.dup(pipe.getFileDescriptor());
                mToken = token;
                mSendApk = sendApk;
                mWriteManifest = writeManifest;
            }

            @Override
            public void run() {
                try {
                    BackupDataOutput output = new BackupDataOutput(
                            mPipe.getFileDescriptor());

                    if (mWriteManifest) {
                        final boolean writeWidgetData = mWidgetData != null;
                        if (MORE_DEBUG) Slog.d(TAG, "Writing manifest for " + mPackage.packageName);
                        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) {
                        writeApkToBackup(mPackage, output);
                    }

                    if (DEBUG) Slog.d(TAG, "Calling doFullBackup() on " + mPackage.packageName);
                    prepareOperationTimeout(mToken, TIMEOUT_FULL_BACKUP_INTERVAL, null);
                    mAgent.doFullBackup(mPipe, mToken, mBackupManagerBinder);
                } catch (IOException e) {
                    Slog.e(TAG, "Error running full backup for " + mPackage.packageName);
                } catch (RemoteException e) {
                    Slog.e(TAG, "Remote agent vanished during full backup of "
                            +