Fix issue #32180780: Sync adapters inappropriately being run...

...during full-data backup/restore

The activity manager now tells job scheduler service about the
current backup that is running (only if it is a full backup), it
there is a new condition where we won't consider jobs associated
with the current backup to be ready to run.

Also...  just a little optimization here. :)  The focus is on
scheduling  jobs with a 0 deadline, meaning they should run right
away.  Now the timing controller does a quick check for a new
job to see if its constraints are already satisifed, and doesn't
do anything further if that is the case (doesn't add to the list,
doesn't re-evaluate alarms, etc).  And in the path to scheduling
a job, we do a check to see if the new job is already ready and if
so then just directly add it to the pending list and schedule it.

Doing this required removing what I think is the last bit of code
relying on handler serializing for thread safety, so now everything
in the job scheduler is protected by our global lock and we can
do whatever we want with the lock held and be assured the state
remains consistent.

Also did some small optimizations to many of the other controllers,
mostly switching from an ArrayList to an ArraySet for their tracked
jobs, since one of the things we do frequently is add/remove jobs.

Finally, added some nullability annotations to the JobScheduler
APIs.

Test: bit CtsJobSchedulerTestCases:*

Change-Id: I533fad94ba59468a52fe3d077a0ceab3427f0012
diff --git a/core/java/android/app/job/JobInfo.java b/core/java/android/app/job/JobInfo.java
index 23baa17..fa07fbd 100644
--- a/core/java/android/app/job/JobInfo.java
+++ b/core/java/android/app/job/JobInfo.java
@@ -244,7 +244,7 @@
     /**
      * Bundle of extras which are returned to your application at execution time.
      */
-    public PersistableBundle getExtras() {
+    public @NonNull PersistableBundle getExtras() {
         return extras;
     }
 
@@ -252,7 +252,7 @@
      * Bundle of transient extras which are returned to your application at execution time,
      * but not persisted by the system.
      */
-    public Bundle getTransientExtras() {
+    public @NonNull Bundle getTransientExtras() {
         return transientExtras;
     }
 
@@ -260,7 +260,7 @@
      * ClipData of information that is returned to your application at execution time,
      * but not persisted by the system.
      */
-    public ClipData getClipData() {
+    public @Nullable ClipData getClipData() {
         return clipData;
     }
 
@@ -274,7 +274,7 @@
     /**
      * Name of the service endpoint that will be called back into by the JobScheduler.
      */
-    public ComponentName getService() {
+    public @NonNull ComponentName getService() {
         return service;
     }
 
@@ -327,8 +327,7 @@
      * Which content: URIs must change for the job to be scheduled.  Returns null
      * if there are none required.
      */
-    @Nullable
-    public TriggerContentUri[] getTriggerContentUris() {
+    public @Nullable TriggerContentUri[] getTriggerContentUris() {
         return triggerContentUris;
     }
 
@@ -811,7 +810,7 @@
          * @param jobService The endpoint that you implement that will receive the callback from the
          * JobScheduler.
          */
-        public Builder(int jobId, ComponentName jobService) {
+        public Builder(int jobId, @NonNull ComponentName jobService) {
             mJobService = jobService;
             mJobId = jobId;
         }
@@ -832,7 +831,7 @@
          * Set optional extras. This is persisted, so we only allow primitive types.
          * @param extras Bundle containing extras you want the scheduler to hold on to for you.
          */
-        public Builder setExtras(PersistableBundle extras) {
+        public Builder setExtras(@NonNull PersistableBundle extras) {
             mExtras = extras;
             return this;
         }
@@ -842,7 +841,7 @@
          * persisted with {@link #setPersisted(boolean)}; mixing the two is not allowed.
          * @param extras Bundle containing extras you want the scheduler to hold on to for you.
          */
-        public Builder setTransientExtras(Bundle extras) {
+        public Builder setTransientExtras(@NonNull Bundle extras) {
             mTransientExtras = extras;
             return this;
         }
@@ -869,7 +868,7 @@
          * {@link android.content.Intent#FLAG_GRANT_WRITE_URI_PERMISSION}, and
          * {@link android.content.Intent#FLAG_GRANT_PREFIX_URI_PERMISSION}.
          */
-        public Builder setClipData(ClipData clip, int grantFlags) {
+        public Builder setClipData(@Nullable ClipData clip, int grantFlags) {
             mClipData = clip;
             mClipGrantFlags = grantFlags;
             return this;
diff --git a/core/java/android/app/job/JobParameters.java b/core/java/android/app/job/JobParameters.java
index 673d1b8..0985f5f 100644
--- a/core/java/android/app/job/JobParameters.java
+++ b/core/java/android/app/job/JobParameters.java
@@ -16,6 +16,8 @@
 
 package android.app.job;
 
+import android.annotation.NonNull;
+import android.annotation.Nullable;
 import android.app.job.IJobCallback;
 import android.content.ClipData;
 import android.net.Uri;
@@ -91,7 +93,7 @@
      * {@link android.app.job.JobInfo.Builder#setExtras(android.os.PersistableBundle)}. This will
      * never be null. If you did not set any extras this will be an empty bundle.
      */
-    public PersistableBundle getExtras() {
+    public @NonNull PersistableBundle getExtras() {
         return extras;
     }
 
@@ -100,7 +102,7 @@
      * {@link android.app.job.JobInfo.Builder#setTransientExtras(android.os.Bundle)}. This will
      * never be null. If you did not set any extras this will be an empty bundle.
      */
-    public Bundle getTransientExtras() {
+    public @NonNull Bundle getTransientExtras() {
         return transientExtras;
     }
 
@@ -109,7 +111,7 @@
      * {@link android.app.job.JobInfo.Builder#setClipData(ClipData, int)}. Will be null
      * if it was not set.
      */
-    public ClipData getClipData() {
+    public @Nullable ClipData getClipData() {
         return clipData;
     }
 
@@ -140,7 +142,7 @@
      * always use {@link #getTriggeredContentAuthorities()} to determine whether the job was
      * triggered due to any content changes and the authorities they are associated with.
      */
-    public Uri[] getTriggeredContentUris() {
+    public @Nullable Uri[] getTriggeredContentUris() {
         return mTriggeredContentUris;
     }
 
@@ -152,7 +154,7 @@
      * to retrieve the details of which URIs changed (as long as that has not exceeded the maximum
      * number it can reported).
      */
-    public String[] getTriggeredContentAuthorities() {
+    public @Nullable String[] getTriggeredContentAuthorities() {
         return mTriggeredContentAuthorities;
     }
 
@@ -183,7 +185,7 @@
      * (This means that for correct operation, you must always call dequeueWork() after you have
      * completed other work, to check either for more work or allow the system to stop the job.)
      */
-    public JobWorkItem dequeueWork() {
+    public @Nullable JobWorkItem dequeueWork() {
         try {
             return getCallback().dequeueWork(getJobId());
         } catch (RemoteException e) {
@@ -207,7 +209,7 @@
      * @param work The work you have completed processing, as previously returned by
      * {@link #dequeueWork()}
      */
-    public void completeWork(JobWorkItem work) {
+    public void completeWork(@NonNull JobWorkItem work) {
         try {
             if (!getCallback().completeWork(getJobId(), work.getWorkId())) {
                 throw new IllegalArgumentException("Given work is not active: " + work);
diff --git a/core/java/android/app/job/JobScheduler.java b/core/java/android/app/job/JobScheduler.java
index e0afe03..4d6e3a2 100644
--- a/core/java/android/app/job/JobScheduler.java
+++ b/core/java/android/app/job/JobScheduler.java
@@ -72,7 +72,7 @@
      * you can schedule.
      * @return An int representing ({@link #RESULT_SUCCESS} or {@link #RESULT_FAILURE}).
      */
-    public abstract int schedule(JobInfo job);
+    public abstract int schedule(@NonNull JobInfo job);
 
     /**
      * Similar to {@link #schedule}, but allows you to enqueue work for an existing job.  If a job
@@ -108,7 +108,7 @@
      * @param work New work to enqueue.  This will be available later when the job starts running.
      * @return An int representing ({@link #RESULT_SUCCESS} or {@link #RESULT_FAILURE}).
      */
-    public abstract int enqueue(JobInfo job, JobWorkItem work);
+    public abstract int enqueue(@NonNull JobInfo job, @NonNull JobWorkItem work);
 
     /**
      *
@@ -121,7 +121,8 @@
      * @hide
      */
     @SystemApi
-    public abstract int scheduleAsPackage(JobInfo job, String packageName, int userId, String tag);
+    public abstract int scheduleAsPackage(@NonNull JobInfo job, @NonNull String packageName,
+            int userId, String tag);
 
     /**
      * Cancel a job that is pending in the JobScheduler.
diff --git a/services/core/java/com/android/server/am/ActivityManagerService.java b/services/core/java/com/android/server/am/ActivityManagerService.java
index fa936c2..25c1c56 100644
--- a/services/core/java/com/android/server/am/ActivityManagerService.java
+++ b/services/core/java/com/android/server/am/ActivityManagerService.java
@@ -358,6 +358,7 @@
 import android.view.View;
 import android.view.WindowManager;
 
+import com.android.server.job.JobSchedulerInternal;
 import com.google.android.collect.Lists;
 import com.google.android.collect.Maps;
 
@@ -18158,6 +18159,9 @@
             return false;
         }
 
+        int oldBackupUid;
+        int newBackupUid;
+
         synchronized(this) {
             // !!! TODO: currently no check here that we're already bound
             BatteryStatsImpl.Uid.Pkg.Serv ss = null;
@@ -18198,6 +18202,8 @@
                 proc.inFullBackup = true;
             }
             r.app = proc;
+            oldBackupUid = mBackupTarget != null ? mBackupTarget.appInfo.uid : -1;
+            newBackupUid = proc.inFullBackup ? r.appInfo.uid : -1;
             mBackupTarget = r;
             mBackupAppName = app.packageName;
 
@@ -18223,6 +18229,14 @@
             // know that it's scheduled for a backup-agent operation.
         }
 
+        JobSchedulerInternal js = LocalServices.getService(JobSchedulerInternal.class);
+        if (oldBackupUid != -1) {
+            js.removeBackingUpUid(oldBackupUid);
+        }
+        if (newBackupUid != -1) {
+            js.addBackingUpUid(newBackupUid);
+        }
+
         return true;
     }
 
@@ -18235,6 +18249,9 @@
             mBackupTarget = null;
             mBackupAppName = null;
         }
+
+        JobSchedulerInternal js = LocalServices.getService(JobSchedulerInternal.class);
+        js.clearAllBackingUpUids();
     }
 
     // A backup agent has just come up
@@ -18272,6 +18289,8 @@
             return;
         }
 
+        int oldBackupUid;
+
         synchronized(this) {
             try {
                 if (mBackupAppName == null) {
@@ -18289,6 +18308,8 @@
                 updateOomAdjLocked(proc);
                 proc.inFullBackup = false;
 
+                oldBackupUid = mBackupTarget != null ? mBackupTarget.appInfo.uid : -1;
+
                 // If the app crashed during backup, 'thread' will be null here
                 if (proc.thread != null) {
                     try {
@@ -18304,7 +18325,13 @@
                 mBackupAppName = null;
             }
         }
+
+        if (oldBackupUid != -1) {
+            JobSchedulerInternal js = LocalServices.getService(JobSchedulerInternal.class);
+            js.removeBackingUpUid(oldBackupUid);
+        }
     }
+
     // =========================================================
     // BROADCASTS
     // =========================================================
diff --git a/services/core/java/com/android/server/job/JobSchedulerInternal.java b/services/core/java/com/android/server/job/JobSchedulerInternal.java
index 75170ec..bc6bd50 100644
--- a/services/core/java/com/android/server/job/JobSchedulerInternal.java
+++ b/services/core/java/com/android/server/job/JobSchedulerInternal.java
@@ -30,4 +30,11 @@
      * Returns a list of pending jobs scheduled by the system service.
      */
     List<JobInfo> getSystemScheduledPendingJobs();
+
+    /**
+     * These are for activity manager to communicate to use what is currently performing backups.
+     */
+    void addBackingUpUid(int uid);
+    void removeBackingUpUid(int uid);
+    void clearAllBackingUpUids();
 }
diff --git a/services/core/java/com/android/server/job/JobSchedulerService.java b/services/core/java/com/android/server/job/JobSchedulerService.java
index c8bfa34..3db2f31 100644
--- a/services/core/java/com/android/server/job/JobSchedulerService.java
+++ b/services/core/java/com/android/server/job/JobSchedulerService.java
@@ -174,6 +174,11 @@
      */
     final SparseIntArray mUidPriorityOverride = new SparseIntArray();
 
+    /**
+     * Which uids are currently performing backups, so we shouldn't allow their jobs to run.
+     */
+    final SparseIntArray mBackingUpUids = new SparseIntArray();
+
     // -- Pre-allocated temporaries only for use in assignJobsToContextsLocked --
 
     /**
@@ -621,14 +626,30 @@
             jobStatus.prepareLocked(ActivityManager.getService());
 
             if (toCancel != null) {
-                cancelJobImpl(toCancel, jobStatus);
+                cancelJobImplLocked(toCancel, jobStatus);
             }
             if (work != null) {
                 // If work has been supplied, enqueue it into the new job.
                 jobStatus.enqueueWorkLocked(ActivityManager.getService(), work);
             }
             startTrackingJobLocked(jobStatus, toCancel);
-            mHandler.obtainMessage(MSG_CHECK_JOB).sendToTarget();
+
+            // If the job is immediately ready to run, then we can just immediately
+            // put it in the pending list and try to schedule it.  This is especially
+            // important for jobs with a 0 deadline constraint, since they will happen a fair
+            // amount, we want to handle them as quickly as possible, and semantically we want to
+            // make sure we have started holding the wake lock for the job before returning to
+            // the caller.
+            // If the job is not yet ready to run, there is nothing more to do -- we are
+            // now just waiting for one of its controllers to change state and schedule
+            // the job appropriately.
+            if (isReadyToBeExecutedLocked(jobStatus)) {
+                // This is a new job, we can just immediately put it on the pending
+                // list and try to run it.
+                mJobPackageTracker.notePending(jobStatus);
+                mPendingJobs.add(jobStatus);
+                maybeRunPendingJobsLocked();
+            }
         }
         return JobScheduler.RESULT_SUCCESS;
     }
@@ -659,25 +680,23 @@
     }
 
     void cancelJobsForUser(int userHandle) {
-        List<JobStatus> jobsForUser;
         synchronized (mLock) {
-            jobsForUser = mJobs.getJobsByUser(userHandle);
-        }
-        for (int i=0; i<jobsForUser.size(); i++) {
-            JobStatus toRemove = jobsForUser.get(i);
-            cancelJobImpl(toRemove, null);
+            final List<JobStatus> jobsForUser = mJobs.getJobsByUser(userHandle);
+            for (int i=0; i<jobsForUser.size(); i++) {
+                JobStatus toRemove = jobsForUser.get(i);
+                cancelJobImplLocked(toRemove, null);
+            }
         }
     }
 
     void cancelJobsForPackageAndUid(String pkgName, int uid) {
-        List<JobStatus> jobsForUid;
         synchronized (mLock) {
-            jobsForUid = mJobs.getJobsByUid(uid);
-        }
-        for (int i = jobsForUid.size() - 1; i >= 0; i--) {
-            final JobStatus job = jobsForUid.get(i);
-            if (job.getSourcePackageName().equals(pkgName)) {
-                cancelJobImpl(job, null);
+            final List<JobStatus> jobsForUid = mJobs.getJobsByUid(uid);
+            for (int i = jobsForUid.size() - 1; i >= 0; i--) {
+                final JobStatus job = jobsForUid.get(i);
+                if (job.getSourcePackageName().equals(pkgName)) {
+                    cancelJobImplLocked(job, null);
+                }
             }
         }
     }
@@ -690,13 +709,12 @@
      *
      */
     public void cancelJobsForUid(int uid) {
-        List<JobStatus> jobsForUid;
         synchronized (mLock) {
-            jobsForUid = mJobs.getJobsByUid(uid);
-        }
-        for (int i=0; i<jobsForUid.size(); i++) {
-            JobStatus toRemove = jobsForUid.get(i);
-            cancelJobImpl(toRemove, null);
+            final List<JobStatus> jobsForUid = mJobs.getJobsByUid(uid);
+            for (int i=0; i<jobsForUid.size(); i++) {
+                JobStatus toRemove = jobsForUid.get(i);
+                cancelJobImplLocked(toRemove, null);
+            }
         }
     }
 
@@ -711,25 +729,23 @@
         JobStatus toCancel;
         synchronized (mLock) {
             toCancel = mJobs.getJobByUidAndJobId(uid, jobId);
-        }
-        if (toCancel != null) {
-            cancelJobImpl(toCancel, null);
+            if (toCancel != null) {
+                cancelJobImplLocked(toCancel, null);
+            }
         }
     }
 
-    private void cancelJobImpl(JobStatus cancelled, JobStatus incomingJob) {
-        synchronized (mLock) {
-            if (DEBUG) Slog.d(TAG, "CANCEL: " + cancelled.toShortString());
-            cancelled.unprepareLocked(ActivityManager.getService());
-            stopTrackingJobLocked(cancelled, incomingJob, true /* writeBack */);
-            // Remove from pending queue.
-            if (mPendingJobs.remove(cancelled)) {
-                mJobPackageTracker.noteNonpending(cancelled);
-            }
-            // Cancel if running.
-            stopJobOnServiceContextLocked(cancelled, JobParameters.REASON_CANCELED);
-            reportActiveLocked();
+    private void cancelJobImplLocked(JobStatus cancelled, JobStatus incomingJob) {
+        if (DEBUG) Slog.d(TAG, "CANCEL: " + cancelled.toShortString());
+        cancelled.unprepareLocked(ActivityManager.getService());
+        stopTrackingJobLocked(cancelled, incomingJob, true /* writeBack */);
+        // Remove from pending queue.
+        if (mPendingJobs.remove(cancelled)) {
+            mJobPackageTracker.noteNonpending(cancelled);
         }
+        // Cancel if running.
+        stopJobOnServiceContextLocked(cancelled, JobParameters.REASON_CANCELED);
+        reportActiveLocked();
     }
 
     void updateUidState(int uid, int procState) {
@@ -770,8 +786,8 @@
                             mLocalDeviceIdleController.setJobsActive(true);
                         }
                     }
+                    mHandler.obtainMessage(MSG_CHECK_JOB).sendToTarget();
                 }
-                mHandler.obtainMessage(MSG_CHECK_JOB).sendToTarget();
             }
         }
     }
@@ -990,7 +1006,7 @@
      * @return A newly instantiated JobStatus with the same constraints as the last job except
      * with adjusted timing constraints.
      *
-     * @see JobHandler#maybeQueueReadyJobsForExecutionLockedH
+     * @see #maybeQueueReadyJobsForExecutionLocked
      */
     private JobStatus getRescheduleJobForFailureLocked(JobStatus failureToReschedule) {
         final long elapsedNowMillis = SystemClock.elapsedRealtime();
@@ -1128,7 +1144,7 @@
         mHandler.obtainMessage(MSG_JOB_EXPIRED, jobStatus).sendToTarget();
     }
 
-    private class JobHandler extends Handler {
+    final private class JobHandler extends Handler {
 
         public JobHandler(Looper looper) {
             super(looper);
@@ -1140,283 +1156,278 @@
                 if (!mReadyToRock) {
                     return;
                 }
-            }
-            switch (message.what) {
-                case MSG_JOB_EXPIRED:
-                    synchronized (mLock) {
+                switch (message.what) {
+                    case MSG_JOB_EXPIRED: {
                         JobStatus runNow = (JobStatus) message.obj;
                         // runNow can be null, which is a controller's way of indicating that its
                         // state is such that all ready jobs should be run immediately.
                         if (runNow != null && isReadyToBeExecutedLocked(runNow)) {
                             mJobPackageTracker.notePending(runNow);
                             mPendingJobs.add(runNow);
+                        } else {
+                            queueReadyJobsForExecutionLocked();
                         }
-                        queueReadyJobsForExecutionLockedH();
-                    }
-                    break;
-                case MSG_CHECK_JOB:
-                    synchronized (mLock) {
+                    } break;
+                    case MSG_CHECK_JOB:
                         if (mReportedActive) {
                             // if jobs are currently being run, queue all ready jobs for execution.
-                            queueReadyJobsForExecutionLockedH();
+                            queueReadyJobsForExecutionLocked();
                         } else {
                             // Check the list of jobs and run some of them if we feel inclined.
-                            maybeQueueReadyJobsForExecutionLockedH();
+                            maybeQueueReadyJobsForExecutionLocked();
                         }
-                    }
-                    break;
-                case MSG_CHECK_JOB_GREEDY:
-                    synchronized (mLock) {
-                        queueReadyJobsForExecutionLockedH();
-                    }
-                    break;
-                case MSG_STOP_JOB:
-                    cancelJobImpl((JobStatus)message.obj, null);
-                    break;
-            }
-            maybeRunPendingJobsH();
-            // Don't remove JOB_EXPIRED in case one came along while processing the queue.
-            removeMessages(MSG_CHECK_JOB);
-        }
-
-        /**
-         * Run through list of jobs and execute all possible - at least one is expired so we do
-         * as many as we can.
-         */
-        private void queueReadyJobsForExecutionLockedH() {
-            if (DEBUG) {
-                Slog.d(TAG, "queuing all ready jobs for execution:");
-            }
-            noteJobsNonpending(mPendingJobs);
-            mPendingJobs.clear();
-            mJobs.forEachJob(mReadyQueueFunctor);
-            mReadyQueueFunctor.postProcess();
-
-            if (DEBUG) {
-                final int queuedJobs = mPendingJobs.size();
-                if (queuedJobs == 0) {
-                    Slog.d(TAG, "No jobs pending.");
-                } else {
-                    Slog.d(TAG, queuedJobs + " jobs queued.");
+                        break;
+                    case MSG_CHECK_JOB_GREEDY:
+                        queueReadyJobsForExecutionLocked();
+                        break;
+                    case MSG_STOP_JOB:
+                        cancelJobImplLocked((JobStatus) message.obj, null);
+                        break;
                 }
+                maybeRunPendingJobsLocked();
+                // Don't remove JOB_EXPIRED in case one came along while processing the queue.
+                removeMessages(MSG_CHECK_JOB);
             }
         }
+    }
 
-        class ReadyJobQueueFunctor implements JobStatusFunctor {
-            ArrayList<JobStatus> newReadyJobs;
+    /**
+     * Run through list of jobs and execute all possible - at least one is expired so we do
+     * as many as we can.
+     */
+    private void queueReadyJobsForExecutionLocked() {
+        if (DEBUG) {
+            Slog.d(TAG, "queuing all ready jobs for execution:");
+        }
+        noteJobsNonpending(mPendingJobs);
+        mPendingJobs.clear();
+        mJobs.forEachJob(mReadyQueueFunctor);
+        mReadyQueueFunctor.postProcess();
 
-            @Override
-            public void process(JobStatus job) {
-                if (isReadyToBeExecutedLocked(job)) {
-                    if (DEBUG) {
-                        Slog.d(TAG, "    queued " + job.toShortString());
-                    }
-                    if (newReadyJobs == null) {
-                        newReadyJobs = new ArrayList<JobStatus>();
-                    }
-                    newReadyJobs.add(job);
-                } else if (areJobConstraintsNotSatisfiedLocked(job)) {
-                    stopJobOnServiceContextLocked(job,
-                            JobParameters.REASON_CONSTRAINTS_NOT_SATISFIED);
-                }
-            }
-
-            public void postProcess() {
-                if (newReadyJobs != null) {
-                    noteJobsPending(newReadyJobs);
-                    mPendingJobs.addAll(newReadyJobs);
-                }
-                newReadyJobs = null;
+        if (DEBUG) {
+            final int queuedJobs = mPendingJobs.size();
+            if (queuedJobs == 0) {
+                Slog.d(TAG, "No jobs pending.");
+            } else {
+                Slog.d(TAG, queuedJobs + " jobs queued.");
             }
         }
-        private final ReadyJobQueueFunctor mReadyQueueFunctor = new ReadyJobQueueFunctor();
+    }
 
-        /**
-         * The state of at least one job has changed. Here is where we could enforce various
-         * policies on when we want to execute jobs.
-         * Right now the policy is such:
-         * If >1 of the ready jobs is idle mode we send all of them off
-         * if more than 2 network connectivity jobs are ready we send them all off.
-         * If more than 4 jobs total are ready we send them all off.
-         * TODO: It would be nice to consolidate these sort of high-level policies somewhere.
-         */
-        class MaybeReadyJobQueueFunctor implements JobStatusFunctor {
-            int chargingCount;
-            int batteryNotLowCount;
-            int storageNotLowCount;
-            int idleCount;
-            int backoffCount;
-            int connectivityCount;
-            int contentCount;
-            List<JobStatus> runnableJobs;
+    final class ReadyJobQueueFunctor implements JobStatusFunctor {
+        ArrayList<JobStatus> newReadyJobs;
 
-            public MaybeReadyJobQueueFunctor() {
-                reset();
-            }
-
-            // Functor method invoked for each job via JobStore.forEachJob()
-            @Override
-            public void process(JobStatus job) {
-                if (isReadyToBeExecutedLocked(job)) {
-                    try {
-                        if (ActivityManager.getService().isAppStartModeDisabled(job.getUid(),
-                                job.getJob().getService().getPackageName())) {
-                            Slog.w(TAG, "Aborting job " + job.getUid() + ":"
-                                    + job.getJob().toString() + " -- package not allowed to start");
-                            mHandler.obtainMessage(MSG_STOP_JOB, job).sendToTarget();
-                            return;
-                        }
-                    } catch (RemoteException e) {
-                    }
-                    if (job.getNumFailures() > 0) {
-                        backoffCount++;
-                    }
-                    if (job.hasIdleConstraint()) {
-                        idleCount++;
-                    }
-                    if (job.hasConnectivityConstraint()) {
-                        connectivityCount++;
-                    }
-                    if (job.hasChargingConstraint()) {
-                        chargingCount++;
-                    }
-                    if (job.hasBatteryNotLowConstraint()) {
-                        batteryNotLowCount++;
-                    }
-                    if (job.hasStorageNotLowConstraint()) {
-                        storageNotLowCount++;
-                    }
-                    if (job.hasContentTriggerConstraint()) {
-                        contentCount++;
-                    }
-                    if (runnableJobs == null) {
-                        runnableJobs = new ArrayList<>();
-                    }
-                    runnableJobs.add(job);
-                } else if (areJobConstraintsNotSatisfiedLocked(job)) {
-                    stopJobOnServiceContextLocked(job,
-                            JobParameters.REASON_CONSTRAINTS_NOT_SATISFIED);
-                }
-            }
-
-            public void postProcess() {
-                if (backoffCount > 0 ||
-                        idleCount >= mConstants.MIN_IDLE_COUNT ||
-                        connectivityCount >= mConstants.MIN_CONNECTIVITY_COUNT ||
-                        chargingCount >= mConstants.MIN_CHARGING_COUNT ||
-                        batteryNotLowCount >= mConstants.MIN_BATTERY_NOT_LOW_COUNT ||
-                        storageNotLowCount >= mConstants.MIN_STORAGE_NOT_LOW_COUNT ||
-                        contentCount >= mConstants.MIN_CONTENT_COUNT ||
-                        (runnableJobs != null
-                                && runnableJobs.size() >= mConstants.MIN_READY_JOBS_COUNT)) {
-                    if (DEBUG) {
-                        Slog.d(TAG, "maybeQueueReadyJobsForExecutionLockedH: Running jobs.");
-                    }
-                    noteJobsPending(runnableJobs);
-                    mPendingJobs.addAll(runnableJobs);
-                } else {
-                    if (DEBUG) {
-                        Slog.d(TAG, "maybeQueueReadyJobsForExecutionLockedH: Not running anything.");
-                    }
-                }
-
-                // Be ready for next time
-                reset();
-            }
-
-            private void reset() {
-                chargingCount = 0;
-                idleCount =  0;
-                backoffCount = 0;
-                connectivityCount = 0;
-                batteryNotLowCount = 0;
-                storageNotLowCount = 0;
-                contentCount = 0;
-                runnableJobs = null;
-            }
-        }
-        private final MaybeReadyJobQueueFunctor mMaybeQueueFunctor = new MaybeReadyJobQueueFunctor();
-
-        private void maybeQueueReadyJobsForExecutionLockedH() {
-            if (DEBUG) Slog.d(TAG, "Maybe queuing ready jobs...");
-
-            noteJobsNonpending(mPendingJobs);
-            mPendingJobs.clear();
-            mJobs.forEachJob(mMaybeQueueFunctor);
-            mMaybeQueueFunctor.postProcess();
-        }
-
-        /**
-         * Criteria for moving a job into the pending queue:
-         *      - It's ready.
-         *      - It's not pending.
-         *      - It's not already running on a JSC.
-         *      - The user that requested the job is running.
-         *      - The component is enabled and runnable.
-         */
-        private boolean isReadyToBeExecutedLocked(JobStatus job) {
-            final boolean jobExists = mJobs.containsJob(job);
-            final boolean jobReady = job.isReady();
-            final boolean jobPending = mPendingJobs.contains(job);
-            final boolean jobActive = isCurrentlyActiveLocked(job);
-
-            final int userId = job.getUserId();
-            final boolean userStarted = ArrayUtils.contains(mStartedUsers, userId);
-
-            if (DEBUG) {
-                Slog.v(TAG, "isReadyToBeExecutedLocked: " + job.toShortString()
-                        + " exists=" + jobExists
-                        + " ready=" + jobReady + " pending=" + jobPending
-                        + " active=" + jobActive + " userStarted=" + userStarted);
-            }
-
-            // Short circuit: don't do the expensive PM check unless we really think
-            // we might need to run this job now.
-            if (!jobExists || !userStarted || !jobReady || jobPending || jobActive) {
-                return false;
-            }
-
-            final boolean componentPresent;
-            try {
-                componentPresent = (AppGlobals.getPackageManager().getServiceInfo(
-                        job.getServiceComponent(), PackageManager.MATCH_DEBUG_TRIAGED_MISSING,
-                        userId) != null);
-            } catch (RemoteException e) {
-                throw e.rethrowAsRuntimeException();
-            }
-
-            if (DEBUG) {
-                Slog.v(TAG, "isReadyToBeExecutedLocked: " + job.toShortString()
-                        + " componentPresent=" + componentPresent);
-            }
-
-            // Everything else checked out so far, so this is the final yes/no check
-            return componentPresent;
-        }
-
-        /**
-         * Criteria for cancelling an active job:
-         *      - It's not ready
-         *      - It's running on a JSC.
-         */
-        private boolean areJobConstraintsNotSatisfiedLocked(JobStatus job) {
-            return !job.isReady() && isCurrentlyActiveLocked(job);
-        }
-
-        /**
-         * Reconcile jobs in the pending queue against available execution contexts.
-         * A controller can force a job into the pending queue even if it's already running, but
-         * here is where we decide whether to actually execute it.
-         */
-        private void maybeRunPendingJobsH() {
-            synchronized (mLock) {
+        @Override
+        public void process(JobStatus job) {
+            if (isReadyToBeExecutedLocked(job)) {
                 if (DEBUG) {
-                    Slog.d(TAG, "pending queue: " + mPendingJobs.size() + " jobs.");
+                    Slog.d(TAG, "    queued " + job.toShortString());
                 }
-                assignJobsToContextsLocked();
-                reportActiveLocked();
+                if (newReadyJobs == null) {
+                    newReadyJobs = new ArrayList<JobStatus>();
+                }
+                newReadyJobs.add(job);
+            } else if (areJobConstraintsNotSatisfiedLocked(job)) {
+                stopJobOnServiceContextLocked(job,
+                        JobParameters.REASON_CONSTRAINTS_NOT_SATISFIED);
             }
         }
+
+        public void postProcess() {
+            if (newReadyJobs != null) {
+                noteJobsPending(newReadyJobs);
+                mPendingJobs.addAll(newReadyJobs);
+            }
+            newReadyJobs = null;
+        }
+    }
+    private final ReadyJobQueueFunctor mReadyQueueFunctor = new ReadyJobQueueFunctor();
+
+    /**
+     * The state of at least one job has changed. Here is where we could enforce various
+     * policies on when we want to execute jobs.
+     * Right now the policy is such:
+     * If >1 of the ready jobs is idle mode we send all of them off
+     * if more than 2 network connectivity jobs are ready we send them all off.
+     * If more than 4 jobs total are ready we send them all off.
+     * TODO: It would be nice to consolidate these sort of high-level policies somewhere.
+     */
+    final class MaybeReadyJobQueueFunctor implements JobStatusFunctor {
+        int chargingCount;
+        int batteryNotLowCount;
+        int storageNotLowCount;
+        int idleCount;
+        int backoffCount;
+        int connectivityCount;
+        int contentCount;
+        List<JobStatus> runnableJobs;
+
+        public MaybeReadyJobQueueFunctor() {
+            reset();
+        }
+
+        // Functor method invoked for each job via JobStore.forEachJob()
+        @Override
+        public void process(JobStatus job) {
+            if (isReadyToBeExecutedLocked(job)) {
+                try {
+                    if (ActivityManager.getService().isAppStartModeDisabled(job.getUid(),
+                            job.getJob().getService().getPackageName())) {
+                        Slog.w(TAG, "Aborting job " + job.getUid() + ":"
+                                + job.getJob().toString() + " -- package not allowed to start");
+                        mHandler.obtainMessage(MSG_STOP_JOB, job).sendToTarget();
+                        return;
+                    }
+                } catch (RemoteException e) {
+                }
+                if (job.getNumFailures() > 0) {
+                    backoffCount++;
+                }
+                if (job.hasIdleConstraint()) {
+                    idleCount++;
+                }
+                if (job.hasConnectivityConstraint()) {
+                    connectivityCount++;
+                }
+                if (job.hasChargingConstraint()) {
+                    chargingCount++;
+                }
+                if (job.hasBatteryNotLowConstraint()) {
+                    batteryNotLowCount++;
+                }
+                if (job.hasStorageNotLowConstraint()) {
+                    storageNotLowCount++;
+                }
+                if (job.hasContentTriggerConstraint()) {
+                    contentCount++;
+                }
+                if (runnableJobs == null) {
+                    runnableJobs = new ArrayList<>();
+                }
+                runnableJobs.add(job);
+            } else if (areJobConstraintsNotSatisfiedLocked(job)) {
+                stopJobOnServiceContextLocked(job,
+                        JobParameters.REASON_CONSTRAINTS_NOT_SATISFIED);
+            }
+        }
+
+        public void postProcess() {
+            if (backoffCount > 0 ||
+                    idleCount >= mConstants.MIN_IDLE_COUNT ||
+                    connectivityCount >= mConstants.MIN_CONNECTIVITY_COUNT ||
+                    chargingCount >= mConstants.MIN_CHARGING_COUNT ||
+                    batteryNotLowCount >= mConstants.MIN_BATTERY_NOT_LOW_COUNT ||
+                    storageNotLowCount >= mConstants.MIN_STORAGE_NOT_LOW_COUNT ||
+                    contentCount >= mConstants.MIN_CONTENT_COUNT ||
+                    (runnableJobs != null
+                            && runnableJobs.size() >= mConstants.MIN_READY_JOBS_COUNT)) {
+                if (DEBUG) {
+                    Slog.d(TAG, "maybeQueueReadyJobsForExecutionLocked: Running jobs.");
+                }
+                noteJobsPending(runnableJobs);
+                mPendingJobs.addAll(runnableJobs);
+            } else {
+                if (DEBUG) {
+                    Slog.d(TAG, "maybeQueueReadyJobsForExecutionLocked: Not running anything.");
+                }
+            }
+
+            // Be ready for next time
+            reset();
+        }
+
+        private void reset() {
+            chargingCount = 0;
+            idleCount =  0;
+            backoffCount = 0;
+            connectivityCount = 0;
+            batteryNotLowCount = 0;
+            storageNotLowCount = 0;
+            contentCount = 0;
+            runnableJobs = null;
+        }
+    }
+    private final MaybeReadyJobQueueFunctor mMaybeQueueFunctor = new MaybeReadyJobQueueFunctor();
+
+    private void maybeQueueReadyJobsForExecutionLocked() {
+        if (DEBUG) Slog.d(TAG, "Maybe queuing ready jobs...");
+
+        noteJobsNonpending(mPendingJobs);
+        mPendingJobs.clear();
+        mJobs.forEachJob(mMaybeQueueFunctor);
+        mMaybeQueueFunctor.postProcess();
+    }
+
+    /**
+     * Criteria for moving a job into the pending queue:
+     *      - It's ready.
+     *      - It's not pending.
+     *      - It's not already running on a JSC.
+     *      - The user that requested the job is running.
+     *      - The component is enabled and runnable.
+     */
+    private boolean isReadyToBeExecutedLocked(JobStatus job) {
+        final boolean jobExists = mJobs.containsJob(job);
+        final boolean jobReady = job.isReady();
+        final boolean jobPending = mPendingJobs.contains(job);
+        final boolean jobActive = isCurrentlyActiveLocked(job);
+        final boolean jobBackingUp = mBackingUpUids.indexOfKey(job.getSourceUid()) >= 0;
+
+        final int userId = job.getUserId();
+        final boolean userStarted = ArrayUtils.contains(mStartedUsers, userId);
+
+        if (DEBUG) {
+            Slog.v(TAG, "isReadyToBeExecutedLocked: " + job.toShortString()
+                    + " exists=" + jobExists
+                    + " ready=" + jobReady + " pending=" + jobPending
+                    + " active=" + jobActive + " backingup=" + jobBackingUp
+                    + " userStarted=" + userStarted);
+        }
+
+        // Short circuit: don't do the expensive PM check unless we really think
+        // we might need to run this job now.
+        if (!jobExists || !userStarted || !jobReady || jobPending || jobActive || jobBackingUp) {
+            return false;
+        }
+
+        final boolean componentPresent;
+        try {
+            componentPresent = (AppGlobals.getPackageManager().getServiceInfo(
+                    job.getServiceComponent(), PackageManager.MATCH_DEBUG_TRIAGED_MISSING,
+                    userId) != null);
+        } catch (RemoteException e) {
+            throw e.rethrowAsRuntimeException();
+        }
+
+        if (DEBUG) {
+            Slog.v(TAG, "isReadyToBeExecutedLocked: " + job.toShortString()
+                    + " componentPresent=" + componentPresent);
+        }
+
+        // Everything else checked out so far, so this is the final yes/no check
+        return componentPresent;
+    }
+
+    /**
+     * Criteria for cancelling an active job:
+     *      - It's not ready
+     *      - It's running on a JSC.
+     */
+    private boolean areJobConstraintsNotSatisfiedLocked(JobStatus job) {
+        return !job.isReady() && isCurrentlyActiveLocked(job);
+    }
+
+    /**
+     * Reconcile jobs in the pending queue against available execution contexts.
+     * A controller can force a job into the pending queue even if it's already running, but
+     * here is where we decide whether to actually execute it.
+     */
+    private void maybeRunPendingJobsLocked() {
+        if (DEBUG) {
+            Slog.d(TAG, "pending queue: " + mPendingJobs.size() + " jobs.");
+        }
+        assignJobsToContextsLocked();
+        reportActiveLocked();
     }
 
     private int adjustJobPriority(int curPriority, JobStatus job) {
@@ -1619,6 +1630,38 @@
                 return pendingJobs;
             }
         }
+
+        @Override
+        public void addBackingUpUid(int uid) {
+            synchronized (mLock) {
+                // No need to actually do anything here, since for a full backup the
+                // activity manager will kill the process which will kill the job (and
+                // cause it to restart, but now it can't run).
+                mBackingUpUids.put(uid, uid);
+            }
+        }
+
+        @Override
+        public void removeBackingUpUid(int uid) {
+            synchronized (mLock) {
+                mBackingUpUids.delete(uid);
+                // If there are any jobs for this uid, we need to rebuild the pending list
+                // in case they are now ready to run.
+                if (mJobs.countJobsForUid(uid) > 0) {
+                    mHandler.obtainMessage(MSG_CHECK_JOB).sendToTarget();
+                }
+            }
+        }
+
+        @Override
+        public void clearAllBackingUpUids() {
+            synchronized (mLock) {
+                if (mBackingUpUids.size() > 0) {
+                    mBackingUpUids.clear();
+                    mHandler.obtainMessage(MSG_CHECK_JOB).sendToTarget();
+                }
+            }
+        }
     }
 
     /**
@@ -1868,7 +1911,8 @@
                     return JobSchedulerShellCommand.CMD_ERR_CONSTRAINTS;
                 }
 
-                mHandler.obtainMessage(MSG_CHECK_JOB_GREEDY).sendToTarget();
+                queueReadyJobsForExecutionLocked();
+                maybeRunPendingJobsLocked();
             }
         } catch (RemoteException e) {
             // can't happen
@@ -2015,7 +2059,7 @@
 
                     job.dump(pw, "    ", true);
                     pw.print("    Ready: ");
-                    pw.print(mHandler.isReadyToBeExecutedLocked(job));
+                    pw.print(isReadyToBeExecutedLocked(job));
                     pw.print(" (job=");
                     pw.print(job.isReady());
                     pw.print(" user=");
@@ -2024,6 +2068,8 @@
                     pw.print(!mPendingJobs.contains(job));
                     pw.print(" !active=");
                     pw.print(!isCurrentlyActiveLocked(job));
+                    pw.print(" !backingup=");
+                    pw.print(!(mBackingUpUids.indexOfKey(job.getSourceUid()) >= 0));
                     pw.print(" comp=");
                     boolean componentPresent = false;
                     try {
@@ -2052,6 +2098,24 @@
                     pw.print(": "); pw.println(mUidPriorityOverride.valueAt(i));
                 }
             }
+            if (mBackingUpUids.size() > 0) {
+                pw.println();
+                pw.println("Backing up uids:");
+                boolean first = true;
+                for (int i = 0; i < mBackingUpUids.size(); i++) {
+                    int uid = mBackingUpUids.keyAt(i);
+                    if (filterUidFinal == -1 || filterUidFinal == UserHandle.getAppId(uid)) {
+                        if (first) {
+                            pw.print("  ");
+                            first = false;
+                        } else {
+                            pw.print(", ");
+                        }
+                        pw.print(UserHandle.formatUid(uid));
+                    }
+                }
+                pw.println();
+            }
             pw.println();
             mJobPackageTracker.dump(pw, "", filterUidFinal);
             pw.println();
diff --git a/services/core/java/com/android/server/job/controllers/AppIdleController.java b/services/core/java/com/android/server/job/controllers/AppIdleController.java
index 2dbecbd..68dd00f 100644
--- a/services/core/java/com/android/server/job/controllers/AppIdleController.java
+++ b/services/core/java/com/android/server/job/controllers/AppIdleController.java
@@ -123,7 +123,8 @@
     }
 
     @Override
-    public void maybeStopTrackingJobLocked(JobStatus jobStatus, JobStatus incomingJob, boolean forUpdate) {
+    public void maybeStopTrackingJobLocked(JobStatus jobStatus, JobStatus incomingJob,
+            boolean forUpdate) {
     }
 
     @Override
diff --git a/services/core/java/com/android/server/job/controllers/BatteryController.java b/services/core/java/com/android/server/job/controllers/BatteryController.java
index 91a962d..b1f8f6b 100644
--- a/services/core/java/com/android/server/job/controllers/BatteryController.java
+++ b/services/core/java/com/android/server/job/controllers/BatteryController.java
@@ -24,6 +24,7 @@
 import android.os.BatteryManagerInternal;
 import android.os.SystemClock;
 import android.os.UserHandle;
+import android.util.ArraySet;
 import android.util.Slog;
 
 import com.android.internal.annotations.VisibleForTesting;
@@ -32,9 +33,6 @@
 import com.android.server.job.StateChangedListener;
 
 import java.io.PrintWriter;
-import java.util.ArrayList;
-import java.util.Iterator;
-import java.util.List;
 
 /**
  * Simple controller that tracks whether the phone is charging or not. The phone is considered to
@@ -47,7 +45,7 @@
     private static final Object sCreationLock = new Object();
     private static volatile BatteryController sController;
 
-    private List<JobStatus> mTrackedTasks = new ArrayList<JobStatus>();
+    private final ArraySet<JobStatus> mTrackedTasks = new ArraySet<>();
     private ChargingTracker mChargeTracker;
 
     public static BatteryController get(JobSchedulerService taskManagerService) {
@@ -82,6 +80,7 @@
     public void maybeStartTrackingJobLocked(JobStatus taskStatus, JobStatus lastJob) {
         if (taskStatus.hasPowerConstraint()) {
             mTrackedTasks.add(taskStatus);
+            taskStatus.setTrackingController(JobStatus.TRACKING_BATTERY);
             taskStatus.setChargingConstraintSatisfied(mChargeTracker.isOnStablePower());
             taskStatus.setBatteryNotLowConstraintSatisfied(mChargeTracker.isBatteryNotLow());
         }
@@ -89,7 +88,7 @@
 
     @Override
     public void maybeStopTrackingJobLocked(JobStatus taskStatus, JobStatus incomingJob, boolean forUpdate) {
-        if (taskStatus.hasPowerConstraint()) {
+        if (taskStatus.clearTrackingController(JobStatus.TRACKING_BATTERY)) {
             mTrackedTasks.remove(taskStatus);
         }
     }
@@ -103,7 +102,7 @@
         boolean reportChange = false;
         synchronized (mLock) {
             for (int i = mTrackedTasks.size() - 1; i >= 0; i--) {
-                final JobStatus ts = mTrackedTasks.get(i);
+                final JobStatus ts = mTrackedTasks.valueAt(i);
                 boolean previous = ts.setChargingConstraintSatisfied(stablePower);
                 if (previous != stablePower) {
                     reportChange = true;
@@ -251,7 +250,7 @@
         pw.print(mTrackedTasks.size());
         pw.println(":");
         for (int i = 0; i < mTrackedTasks.size(); i++) {
-            final JobStatus js = mTrackedTasks.get(i);
+            final JobStatus js = mTrackedTasks.valueAt(i);
             if (!js.shouldDump(filterUid)) {
                 continue;
             }
diff --git a/services/core/java/com/android/server/job/controllers/ConnectivityController.java b/services/core/java/com/android/server/job/controllers/ConnectivityController.java
index 5ebcc93..f426818 100644
--- a/services/core/java/com/android/server/job/controllers/ConnectivityController.java
+++ b/services/core/java/com/android/server/job/controllers/ConnectivityController.java
@@ -27,6 +27,7 @@
 import android.net.NetworkPolicyManager;
 import android.os.Process;
 import android.os.UserHandle;
+import android.util.ArraySet;
 import android.util.Slog;
 
 import com.android.internal.annotations.GuardedBy;
@@ -34,7 +35,6 @@
 import com.android.server.job.StateChangedListener;
 
 import java.io.PrintWriter;
-import java.util.ArrayList;
 
 /**
  * Handles changes in connectivity.
@@ -54,7 +54,7 @@
     private boolean mValidated;
 
     @GuardedBy("mLock")
-    private final ArrayList<JobStatus> mTrackedJobs = new ArrayList<JobStatus>();
+    private final ArraySet<JobStatus> mTrackedJobs = new ArraySet<>();
 
     /** Singleton. */
     private static ConnectivityController mSingleton;
@@ -87,13 +87,14 @@
         if (jobStatus.hasConnectivityConstraint()) {
             updateConstraintsSatisfied(jobStatus, null);
             mTrackedJobs.add(jobStatus);
+            jobStatus.setTrackingController(JobStatus.TRACKING_CONNECTIVITY);
         }
     }
 
     @Override
     public void maybeStopTrackingJobLocked(JobStatus jobStatus, JobStatus incomingJob,
             boolean forUpdate) {
-        if (jobStatus.hasConnectivityConstraint()) {
+        if (jobStatus.clearTrackingController(JobStatus.TRACKING_CONNECTIVITY)) {
             mTrackedJobs.remove(jobStatus);
         }
     }
@@ -150,8 +151,8 @@
     private void updateTrackedJobs(int uid, NetworkCapabilities capabilities) {
         synchronized (mLock) {
             boolean changed = false;
-            for (int i = 0; i < mTrackedJobs.size(); i++) {
-                final JobStatus js = mTrackedJobs.get(i);
+            for (int i = mTrackedJobs.size()-1; i >= 0; i--) {
+                final JobStatus js = mTrackedJobs.valueAt(i);
                 if (uid == -1 || uid == js.getSourceUid()) {
                     changed |= updateConstraintsSatisfied(js, capabilities);
                 }
@@ -168,8 +169,8 @@
     @Override
     public void onNetworkActive() {
         synchronized (mLock) {
-            for (int i = 0; i < mTrackedJobs.size(); i++) {
-                final JobStatus js = mTrackedJobs.get(i);
+            for (int i = mTrackedJobs.size()-1; i >= 0; i--) {
+                final JobStatus js = mTrackedJobs.valueAt(i);
                 if (js.isReady()) {
                     if (DEBUG) {
                         Slog.d(TAG, "Running " + js + " due to network activity.");
@@ -239,7 +240,7 @@
         pw.print(mTrackedJobs.size());
         pw.println(":");
         for (int i = 0; i < mTrackedJobs.size(); i++) {
-            final JobStatus js = mTrackedJobs.get(i);
+            final JobStatus js = mTrackedJobs.valueAt(i);
             if (js.shouldDump(filterUid)) {
                 pw.print("  #");
                 js.printUniqueId(pw);
diff --git a/services/core/java/com/android/server/job/controllers/ContentObserverController.java b/services/core/java/com/android/server/job/controllers/ContentObserverController.java
index 29f0e2c..cfafc38 100644
--- a/services/core/java/com/android/server/job/controllers/ContentObserverController.java
+++ b/services/core/java/com/android/server/job/controllers/ContentObserverController.java
@@ -35,9 +35,6 @@
 
 import java.io.PrintWriter;
 import java.util.ArrayList;
-import java.util.Iterator;
-import java.util.List;
-import java.util.Objects;
 
 /**
  * Controller for monitoring changes to content URIs through a ContentObserver.
@@ -61,11 +58,11 @@
     private static final Object sCreationLock = new Object();
     private static volatile ContentObserverController sController;
 
-    final private List<JobStatus> mTrackedTasks = new ArrayList<JobStatus>();
+    final private ArraySet<JobStatus> mTrackedTasks = new ArraySet<>();
     /**
      * Per-userid {@link JobInfo.TriggerContentUri} keyed ContentObserver cache.
      */
-    SparseArray<ArrayMap<JobInfo.TriggerContentUri, ObserverInstance>> mObservers =
+    final SparseArray<ArrayMap<JobInfo.TriggerContentUri, ObserverInstance>> mObservers =
             new SparseArray<>();
     final Handler mHandler;
 
@@ -101,6 +98,7 @@
                 Slog.i(TAG, "Tracking content-trigger job " + taskStatus);
             }
             mTrackedTasks.add(taskStatus);
+            taskStatus.setTrackingController(JobStatus.TRACKING_CONTENT);
             boolean havePendingUris = false;
             // If there is a previous job associated with the new job, propagate over
             // any pending content URI trigger reports.
@@ -156,7 +154,8 @@
     @Override
     public void maybeStopTrackingJobLocked(JobStatus taskStatus, JobStatus incomingJob,
             boolean forUpdate) {
-        if (taskStatus.hasContentTriggerConstraint()) {
+        if (taskStatus.clearTrackingController(JobStatus.TRACKING_CONTENT)) {
+            mTrackedTasks.remove(taskStatus);
             if (taskStatus.contentObserverJobInstance != null) {
                 taskStatus.contentObserverJobInstance.unscheduleLocked();
                 if (incomingJob != null) {
@@ -190,7 +189,6 @@
             if (DEBUG) {
                 Slog.i(TAG, "No longer tracking job " + taskStatus);
             }
-            mTrackedTasks.remove(taskStatus);
         }
     }
 
@@ -374,9 +372,8 @@
     @Override
     public void dumpControllerStateLocked(PrintWriter pw, int filterUid) {
         pw.println("Content:");
-        Iterator<JobStatus> it = mTrackedTasks.iterator();
-        while (it.hasNext()) {
-            JobStatus js = it.next();
+        for (int i = 0; i < mTrackedTasks.size(); i++) {
+            JobStatus js = mTrackedTasks.valueAt(i);
             if (!js.shouldDump(filterUid)) {
                 continue;
             }
diff --git a/services/core/java/com/android/server/job/controllers/DeviceIdleJobsController.java b/services/core/java/com/android/server/job/controllers/DeviceIdleJobsController.java
index f7706d7..5ccf812 100644
--- a/services/core/java/com/android/server/job/controllers/DeviceIdleJobsController.java
+++ b/services/core/java/com/android/server/job/controllers/DeviceIdleJobsController.java
@@ -164,13 +164,12 @@
 
     @Override
     public void maybeStartTrackingJobLocked(JobStatus jobStatus, JobStatus lastJob) {
-        synchronized (mLock) {
-            updateTaskStateLocked(jobStatus);
-        }
+        updateTaskStateLocked(jobStatus);
     }
 
     @Override
-    public void maybeStopTrackingJobLocked(JobStatus jobStatus, JobStatus incomingJob, boolean forUpdate) {
+    public void maybeStopTrackingJobLocked(JobStatus jobStatus, JobStatus incomingJob,
+            boolean forUpdate) {
     }
 
     @Override
diff --git a/services/core/java/com/android/server/job/controllers/IdleController.java b/services/core/java/com/android/server/job/controllers/IdleController.java
index 0e04d24..7e92293 100644
--- a/services/core/java/com/android/server/job/controllers/IdleController.java
+++ b/services/core/java/com/android/server/job/controllers/IdleController.java
@@ -17,7 +17,6 @@
 package com.android.server.job.controllers;
 
 import java.io.PrintWriter;
-import java.util.ArrayList;
 
 import android.app.AlarmManager;
 import android.app.PendingIntent;
@@ -27,6 +26,7 @@
 import android.content.IntentFilter;
 import android.os.SystemClock;
 import android.os.UserHandle;
+import android.util.ArraySet;
 import android.util.Slog;
 
 import com.android.server.am.ActivityManagerService;
@@ -40,7 +40,7 @@
     // screen off or dreaming for at least this long
     private long mInactivityIdleThreshold;
     private long mIdleWindowSlop;
-    final ArrayList<JobStatus> mTrackedTasks = new ArrayList<JobStatus>();
+    final ArraySet<JobStatus> mTrackedTasks = new ArraySet<>();
     IdlenessTracker mIdleTracker;
 
     // Singleton factory
@@ -69,13 +69,17 @@
     public void maybeStartTrackingJobLocked(JobStatus taskStatus, JobStatus lastJob) {
         if (taskStatus.hasIdleConstraint()) {
             mTrackedTasks.add(taskStatus);
+            taskStatus.setTrackingController(JobStatus.TRACKING_IDLE);
             taskStatus.setIdleConstraintSatisfied(mIdleTracker.isIdle());
         }
     }
 
     @Override
-    public void maybeStopTrackingJobLocked(JobStatus taskStatus, JobStatus incomingJob, boolean forUpdate) {
-        mTrackedTasks.remove(taskStatus);
+    public void maybeStopTrackingJobLocked(JobStatus taskStatus, JobStatus incomingJob,
+            boolean forUpdate) {
+        if (taskStatus.clearTrackingController(JobStatus.TRACKING_IDLE)) {
+            mTrackedTasks.remove(taskStatus);
+        }
     }
 
     /**
@@ -83,8 +87,8 @@
      */
     void reportNewIdleState(boolean isIdle) {
         synchronized (mLock) {
-            for (JobStatus task : mTrackedTasks) {
-                task.setIdleConstraintSatisfied(isIdle);
+            for (int i = mTrackedTasks.size()-1; i >= 0; i--) {
+                mTrackedTasks.valueAt(i).setIdleConstraintSatisfied(isIdle);
             }
         }
         mStateChangedListener.onControllerStateChanged();
@@ -200,7 +204,7 @@
         pw.print(mTrackedTasks.size());
         pw.println(":");
         for (int i = 0; i < mTrackedTasks.size(); i++) {
-            final JobStatus js = mTrackedTasks.get(i);
+            final JobStatus js = mTrackedTasks.valueAt(i);
             if (!js.shouldDump(filterUid)) {
                 continue;
             }
diff --git a/services/core/java/com/android/server/job/controllers/JobStatus.java b/services/core/java/com/android/server/job/controllers/JobStatus.java
index 1ab66b9..4d5aba3 100644
--- a/services/core/java/com/android/server/job/controllers/JobStatus.java
+++ b/services/core/java/com/android/server/job/controllers/JobStatus.java
@@ -128,6 +128,38 @@
     // Set to true if doze constraint was satisfied due to app being whitelisted.
     public boolean dozeWhitelisted;
 
+    /**
+     * Flag for {@link #trackingControllers}: the battery controller is currently tracking this job.
+     */
+    public static final int TRACKING_BATTERY = 1<<0;
+    /**
+     * Flag for {@link #trackingControllers}: the network connectivity controller is currently
+     * tracking this job.
+     */
+    public static final int TRACKING_CONNECTIVITY = 1<<1;
+    /**
+     * Flag for {@link #trackingControllers}: the content observer controller is currently
+     * tracking this job.
+     */
+    public static final int TRACKING_CONTENT = 1<<2;
+    /**
+     * Flag for {@link #trackingControllers}: the idle controller is currently tracking this job.
+     */
+    public static final int TRACKING_IDLE = 1<<3;
+    /**
+     * Flag for {@link #trackingControllers}: the storage controller is currently tracking this job.
+     */
+    public static final int TRACKING_STORAGE = 1<<4;
+    /**
+     * Flag for {@link #trackingControllers}: the time controller is currently tracking this job.
+     */
+    public static final int TRACKING_TIME = 1<<5;
+
+    /**
+     * Bit mask of controllers that are currently tracking the job.
+     */
+    private int trackingControllers;
+
     // These are filled in by controllers when preparing for execution.
     public ArraySet<Uri> changedUris;
     public ArraySet<String> changedAuthorities;
@@ -609,6 +641,18 @@
         return (satisfiedConstraints&constraint) != 0;
     }
 
+    boolean clearTrackingController(int which) {
+        if ((trackingControllers&which) != 0) {
+            trackingControllers &= ~which;
+            return true;
+        }
+        return false;
+    }
+
+    void setTrackingController(int which) {
+        trackingControllers |= which;
+    }
+
     public boolean shouldDump(int filterUid) {
         return filterUid == -1 || UserHandle.getAppId(getUid()) == filterUid
                 || UserHandle.getAppId(getSourceUid()) == filterUid;
@@ -925,6 +969,16 @@
                 pw.print(prefix); pw.println("Doze whitelisted: true");
             }
         }
+        if (trackingControllers != 0) {
+            pw.print(prefix); pw.print("Tracking:");
+            if ((trackingControllers&TRACKING_BATTERY) != 0) pw.print(" BATTERY");
+            if ((trackingControllers&TRACKING_CONNECTIVITY) != 0) pw.print(" CONNECTIVITY");
+            if ((trackingControllers&TRACKING_CONTENT) != 0) pw.print(" CONTENT");
+            if ((trackingControllers&TRACKING_IDLE) != 0) pw.print(" IDLE");
+            if ((trackingControllers&TRACKING_STORAGE) != 0) pw.print(" STORAGE");
+            if ((trackingControllers&TRACKING_TIME) != 0) pw.print(" TIME");
+            pw.println();
+        }
         if (changedAuthorities != null) {
             pw.print(prefix); pw.println("Changed authorities:");
             for (int i=0; i<changedAuthorities.size(); i++) {
diff --git a/services/core/java/com/android/server/job/controllers/StorageController.java b/services/core/java/com/android/server/job/controllers/StorageController.java
index 60ae5a7..4fe8eca 100644
--- a/services/core/java/com/android/server/job/controllers/StorageController.java
+++ b/services/core/java/com/android/server/job/controllers/StorageController.java
@@ -20,9 +20,9 @@
 import android.content.Context;
 import android.content.Intent;
 import android.content.IntentFilter;
-import android.os.BatteryManager;
 import android.os.SystemClock;
 import android.os.UserHandle;
+import android.util.ArraySet;
 import android.util.Slog;
 
 import com.android.internal.annotations.VisibleForTesting;
@@ -31,8 +31,6 @@
 import com.android.server.storage.DeviceStorageMonitorService;
 
 import java.io.PrintWriter;
-import java.util.ArrayList;
-import java.util.List;
 
 /**
  * Simple controller that tracks the status of the device's storage.
@@ -43,7 +41,7 @@
     private static final Object sCreationLock = new Object();
     private static volatile StorageController sController;
 
-    private List<JobStatus> mTrackedTasks = new ArrayList<JobStatus>();
+    private final ArraySet<JobStatus> mTrackedTasks = new ArraySet<JobStatus>();
     private StorageTracker mStorageTracker;
 
     public static StorageController get(JobSchedulerService taskManagerService) {
@@ -78,13 +76,15 @@
     public void maybeStartTrackingJobLocked(JobStatus taskStatus, JobStatus lastJob) {
         if (taskStatus.hasStorageNotLowConstraint()) {
             mTrackedTasks.add(taskStatus);
+            taskStatus.setTrackingController(JobStatus.TRACKING_STORAGE);
             taskStatus.setStorageNotLowConstraintSatisfied(mStorageTracker.isStorageNotLow());
         }
     }
 
     @Override
-    public void maybeStopTrackingJobLocked(JobStatus taskStatus, JobStatus incomingJob, boolean forUpdate) {
-        if (taskStatus.hasPowerConstraint()) {
+    public void maybeStopTrackingJobLocked(JobStatus taskStatus, JobStatus incomingJob,
+            boolean forUpdate) {
+        if (taskStatus.clearTrackingController(JobStatus.TRACKING_STORAGE)) {
             mTrackedTasks.remove(taskStatus);
         }
     }
@@ -94,7 +94,7 @@
         boolean reportChange = false;
         synchronized (mLock) {
             for (int i = mTrackedTasks.size() - 1; i >= 0; i--) {
-                final JobStatus ts = mTrackedTasks.get(i);
+                final JobStatus ts = mTrackedTasks.valueAt(i);
                 boolean previous = ts.setStorageNotLowConstraintSatisfied(storageNotLow);
                 if (previous != storageNotLow) {
                     reportChange = true;
@@ -178,7 +178,7 @@
         pw.print(mTrackedTasks.size());
         pw.println(":");
         for (int i = 0; i < mTrackedTasks.size(); i++) {
-            final JobStatus js = mTrackedTasks.get(i);
+            final JobStatus js = mTrackedTasks.valueAt(i);
             if (!js.shouldDump(filterUid)) {
                 continue;
             }
diff --git a/services/core/java/com/android/server/job/controllers/TimeController.java b/services/core/java/com/android/server/job/controllers/TimeController.java
index 0b3b00f..01c841e 100644
--- a/services/core/java/com/android/server/job/controllers/TimeController.java
+++ b/services/core/java/com/android/server/job/controllers/TimeController.java
@@ -51,7 +51,7 @@
 
     private AlarmManager mAlarmService = null;
     /** List of tracked jobs, sorted asc. by deadline */
-    private final List<JobStatus> mTrackedJobs = new LinkedList<JobStatus>();
+    private final List<JobStatus> mTrackedJobs = new LinkedList<>();
     /** Singleton. */
     private static TimeController mSingleton;
 
@@ -78,6 +78,20 @@
     public void maybeStartTrackingJobLocked(JobStatus job, JobStatus lastJob) {
         if (job.hasTimingDelayConstraint() || job.hasDeadlineConstraint()) {
             maybeStopTrackingJobLocked(job, null, false);
+
+            // First: check the constraints now, because if they are already satisfied
+            // then there is no need to track it.  This gives us a fast path for a common
+            // pattern of having a job with a 0 deadline constraint ("run immediately").
+            // Unlike most controllers, once one of our constraints has been satisfied, it
+            // will never be unsatisfied (our time base can not go backwards).
+            final long nowElapsedMillis = SystemClock.elapsedRealtime();
+            if (job.hasDeadlineConstraint() && evaluateDeadlineConstraint(job, nowElapsedMillis)) {
+                return;
+            } else if (job.hasTimingDelayConstraint() && evaluateTimingDelayConstraint(job,
+                    nowElapsedMillis)) {
+                return;
+            }
+
             boolean isInsert = false;
             ListIterator<JobStatus> it = mTrackedJobs.listIterator(mTrackedJobs.size());
             while (it.hasPrevious()) {
@@ -92,6 +106,7 @@
                 it.next();
             }
             it.add(job);
+            job.setTrackingController(JobStatus.TRACKING_TIME);
             maybeUpdateAlarmsLocked(
                     job.hasTimingDelayConstraint() ? job.getEarliestRunTime() : Long.MAX_VALUE,
                     job.hasDeadlineConstraint() ? job.getLatestRunTimeElapsed() : Long.MAX_VALUE,
@@ -102,13 +117,15 @@
     /**
      * When we stop tracking a job, we only need to update our alarms if the job we're no longer
      * tracking was the one our alarms were based off of.
-     * Really an == comparison should be enough, but why play with fate? We'll do <=.
      */
     @Override
-    public void maybeStopTrackingJobLocked(JobStatus job, JobStatus incomingJob, boolean forUpdate) {
-        if (mTrackedJobs.remove(job)) {
-            checkExpiredDelaysAndResetAlarm();
-            checkExpiredDeadlinesAndResetAlarm();
+    public void maybeStopTrackingJobLocked(JobStatus job, JobStatus incomingJob,
+            boolean forUpdate) {
+        if (job.clearTrackingController(JobStatus.TRACKING_TIME)) {
+            if (mTrackedJobs.remove(job)) {
+                checkExpiredDelaysAndResetAlarm();
+                checkExpiredDeadlinesAndResetAlarm();
+            }
         }
     }
 
@@ -147,17 +164,12 @@
                 if (!job.hasDeadlineConstraint()) {
                     continue;
                 }
-                final long jobDeadline = job.getLatestRunTimeElapsed();
 
-                if (jobDeadline <= nowElapsedMillis) {
-                    if (job.hasTimingDelayConstraint()) {
-                        job.setTimingDelayConstraintSatisfied(true);
-                    }
-                    job.setDeadlineConstraintSatisfied(true);
+                if (evaluateDeadlineConstraint(job, nowElapsedMillis)) {
                     mStateChangedListener.onRunJobNow(job);
                     it.remove();
                 } else {  // Sorted by expiry time, so take the next one and stop.
-                    nextExpiryTime = jobDeadline;
+                    nextExpiryTime = job.getLatestRunTimeElapsed();
                     nextExpiryUid = job.getSourceUid();
                     break;
                 }
@@ -166,6 +178,19 @@
         }
     }
 
+    private boolean evaluateDeadlineConstraint(JobStatus job, long nowElapsedMillis) {
+        final long jobDeadline = job.getLatestRunTimeElapsed();
+
+        if (jobDeadline <= nowElapsedMillis) {
+            if (job.hasTimingDelayConstraint()) {
+                job.setTimingDelayConstraintSatisfied(true);
+            }
+            job.setDeadlineConstraintSatisfied(true);
+            return true;
+        }
+        return false;
+    }
+
     /**
      * Handles alarm that notifies us that a job's delay has expired. Iterates through the list of
      * tracked jobs and marks them as ready as appropriate.
@@ -182,9 +207,7 @@
                 if (!job.hasTimingDelayConstraint()) {
                     continue;
                 }
-                final long jobDelayTime = job.getEarliestRunTime();
-                if (jobDelayTime <= nowElapsedMillis) {
-                    job.setTimingDelayConstraintSatisfied(true);
+                if (evaluateTimingDelayConstraint(job, nowElapsedMillis)) {
                     if (canStopTrackingJobLocked(job)) {
                         it.remove();
                     }
@@ -194,6 +217,7 @@
                 } else if (!job.isConstraintSatisfied(JobStatus.CONSTRAINT_TIMING_DELAY)) {
                     // If this job still doesn't have its delay constraint satisfied,
                     // then see if it is the next upcoming delay time for the alarm.
+                    final long jobDelayTime = job.getEarliestRunTime();
                     if (nextDelayTime > jobDelayTime) {
                         nextDelayTime = jobDelayTime;
                         nextDelayUid = job.getSourceUid();
@@ -207,6 +231,15 @@
         }
     }
 
+    private boolean evaluateTimingDelayConstraint(JobStatus job, long nowElapsedMillis) {
+        final long jobDelayTime = job.getEarliestRunTime();
+        if (jobDelayTime <= nowElapsedMillis) {
+            job.setTimingDelayConstraintSatisfied(true);
+            return true;
+        }
+        return false;
+    }
+
     private void maybeUpdateAlarmsLocked(long delayExpiredElapsed, long deadlineExpiredElapsed,
             int uid) {
         if (delayExpiredElapsed < mNextDelayExpiredElapsedMillis) {