services/core/java/com/android/server/task/TaskManagerService.java - platform/frameworks/base - Gitiles

 /*
  * Copyright (C) 2014 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License
  */

 package com.android.server.task;

 import java.io.FileDescriptor;
 import java.io.PrintWriter;
 import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.List;

 import android.app.task.ITaskManager;
 import android.app.task.Task;
 import android.app.task.TaskManager;
 import android.content.Context;
 import android.content.pm.PackageManager;
 import android.os.Binder;
 import android.os.Handler;
 import android.os.Looper;
 import android.os.Message;
 import android.os.RemoteException;
 import android.os.SystemClock;
 import android.util.Slog;
 import android.util.SparseArray;

 import com.android.server.task.controllers.BatteryController;
 import com.android.server.task.controllers.ConnectivityController;
 import com.android.server.task.controllers.IdleController;
 import com.android.server.task.controllers.StateController;
 import com.android.server.task.controllers.TaskStatus;
 import com.android.server.task.controllers.TimeController;

 import java.util.LinkedList;

 /**
  * Responsible for taking tasks representing work to be performed by a client app, and determining
  * based on the criteria specified when that task should be run against the client application's
  * endpoint.
  * Implements logic for scheduling, and rescheduling tasks. The TaskManagerService knows nothing
  * about constraints, or the state of active tasks. It receives callbacks from the various
  * controllers and completed tasks and operates accordingly.
  *
  * Note on locking: Any operations that manipulate {@link #mTasks} need to lock on that object, and
  * similarly for {@link #mActiveServices}. If both locks need to be held take mTasksSet first and then
  * mActiveService afterwards.
  * @hide
  */
 public class TaskManagerService extends com.android.server.SystemService
         implements StateChangedListener, TaskCompletedListener, TaskMapReadFinishedListener {
     // TODO: Switch this off for final version.
     static final boolean DEBUG = true;
     /** The number of concurrent tasks we run at one time. */
     private static final int MAX_TASK_CONTEXTS_COUNT = 3;
     static final String TAG = "TaskManager";
     /**
      * When a task fails, it gets rescheduled according to its backoff policy. To be nice, we allow
      * this amount of time from the rescheduled time by which the retry must occur.
      */
     private static final long RESCHEDULE_WINDOW_SLOP_MILLIS = 5000L;

     /** Master list of tasks. */
     private final TaskStore mTasks;

     static final int MSG_TASK_EXPIRED = 0;
     static final int MSG_CHECK_TASKS = 1;

     // Policy constants
     /**
      * Minimum # of idle tasks that must be ready in order to force the TM to schedule things
      * early.
      */
     private static final int MIN_IDLE_COUNT = 1;
     /**
      * Minimum # of connectivity tasks that must be ready in order to force the TM to schedule
      * things early.
      */
     private static final int MIN_CONNECTIVITY_COUNT = 2;
     /**
      * Minimum # of tasks (with no particular constraints) for which the TM will be happy running
      * some work early.
      */
     private static final int MIN_READY_TASKS_COUNT = 4;

     /**
      * Track Services that have currently active or pending tasks. The index is provided by
      * {@link TaskStatus#getServiceToken()}
      */
     private final List<TaskServiceContext> mActiveServices = new LinkedList<TaskServiceContext>();
     /** List of controllers that will notify this service of updates to tasks. */
     private List<StateController> mControllers;
     /**
      * Queue of pending tasks. The TaskServiceContext class will receive tasks from this list
      * when ready to execute them.
      */
     private final LinkedList<TaskStatus> mPendingTasks = new LinkedList<TaskStatus>();

     private final TaskHandler mHandler;
     private final TaskManagerStub mTaskManagerStub;

     /**
      * Entry point from client to schedule the provided task.
      * This will add the task to the
      * @param task Task object containing execution parameters
      * @param uId The package identifier of the application this task is for.
      * @param canPersistTask Whether or not the client has the appropriate permissions for persisting
      *                    of this task.
      * @return Result of this operation. See <code>TaskManager#RESULT_*</code> return codes.
      */
     public int schedule(Task task, int uId, boolean canPersistTask) {
         TaskStatus taskStatus = new TaskStatus(task, uId, canPersistTask);
         startTrackingTask(taskStatus);
         return TaskManager.RESULT_SUCCESS;
     }

     public List<Task> getPendingTasks(int uid) {
         ArrayList<Task> outList = new ArrayList<Task>();
         synchronized (mTasks) {
             for (TaskStatus ts : mTasks.getTasks()) {
                 if (ts.getUid() == uid) {
                     outList.add(ts.getTask());
                 }
             }
         }
         return outList;
     }

     /**
      * Entry point from client to cancel all tasks originating from their uid.
      * This will remove the task from the master list, and cancel the task if it was staged for
      * execution or being executed.
      * @param uid To check against for removal of a task.
      */
     public void cancelTaskForUid(int uid) {
         // Remove from master list.
         synchronized (mTasks) {
             if (!mTasks.removeAllByUid(uid)) {
                 // If it's not in the master list, it's nowhere.
                 return;
             }
         }
         // Remove from pending queue.
         synchronized (mPendingTasks) {
             Iterator<TaskStatus> it = mPendingTasks.iterator();
             while (it.hasNext()) {
                 TaskStatus ts = it.next();
                 if (ts.getUid() == uid) {
                     it.remove();
                 }
             }
         }
         // Cancel if running.
         synchronized (mActiveServices) {
             for (TaskServiceContext tsc : mActiveServices) {
                 if (tsc.getRunningTask().getUid() == uid) {
                     tsc.cancelExecutingTask();
                 }
             }
         }
     }

     /**
      * Entry point from client to cancel the task corresponding to the taskId provided.
      * This will remove the task from the master list, and cancel the task if it was staged for
      * execution or being executed.
      * @param uid Uid of the calling client.
      * @param taskId Id of the task, provided at schedule-time.
      */
     public void cancelTask(int uid, int taskId) {
         synchronized (mTasks) {
             if (!mTasks.remove(uid, taskId)) {
                 // If it's not in the master list, it's nowhere.
                 return;
             }
         }
         synchronized (mPendingTasks) {
             Iterator<TaskStatus> it = mPendingTasks.iterator();
             while (it.hasNext()) {
                 TaskStatus ts = it.next();
                 if (ts.getUid() == uid && ts.getTaskId() == taskId) {
                     it.remove();
                     // If we got it from pending, it didn't make it to active so return.
                     return;
                 }
             }
         }
         synchronized (mActiveServices) {
             for (TaskServiceContext tsc : mActiveServices) {
                 if (tsc.getRunningTask().getUid() == uid &&
                         tsc.getRunningTask().getTaskId() == taskId) {
                     tsc.cancelExecutingTask();
                     return;
                 }
             }
         }
     }

     /**
      * Initializes the system service.
      * <p>
      * Subclasses must define a single argument constructor that accepts the context
      * and passes it to super.
      * </p>
      *
      * @param context The system server context.
      */
     public TaskManagerService(Context context) {
         super(context);
         mTasks = TaskStore.initAndGet(this);
         mHandler = new TaskHandler(context.getMainLooper());
         mTaskManagerStub = new TaskManagerStub();
         // Create the "runners".
         for (int i = 0; i < MAX_TASK_CONTEXTS_COUNT; i++) {
             mActiveServices.add(
                     new TaskServiceContext(this, context.getMainLooper()));
         }
         // Create the controllers.
         mControllers = new LinkedList<StateController>();
         mControllers.add(ConnectivityController.get(this));
         mControllers.add(TimeController.get(this));
         mControllers.add(IdleController.get(this));
         mControllers.add(BatteryController.get(this));
     }

     @Override
     public void onStart() {
         publishBinderService(Context.TASK_SERVICE, mTaskManagerStub);
     }

     /**
      * Called when we have a task status object that we need to insert in our
      * {@link com.android.server.task.TaskStore}, and make sure all the relevant controllers know
      * about.
      */
     private void startTrackingTask(TaskStatus taskStatus) {
         synchronized (mTasks) {
             mTasks.add(taskStatus);
         }
         for (StateController controller : mControllers) {
             controller.maybeStartTrackingTask(taskStatus);

         }
     }

     /**
      * Called when we want to remove a TaskStatus object that we've finished executing. Returns the
      * object removed.
      */
     private boolean stopTrackingTask(TaskStatus taskStatus) {
         boolean removed;
         synchronized (mTasks) {
             // Remove from store as well as controllers.
             removed = mTasks.remove(taskStatus);
         }
         if (removed) {
             for (StateController controller : mControllers) {
                 controller.maybeStopTrackingTask(taskStatus);
             }
         }
         return removed;
     }

     private boolean cancelTaskOnServiceContext(TaskStatus ts) {
         synchronized (mActiveServices) {
             for (TaskServiceContext tsc : mActiveServices) {
                 if (tsc.getRunningTask() == ts) {
                     tsc.cancelExecutingTask();
                     return true;
                 }
             }
             return false;
         }
     }

     /**
      * @param ts TaskStatus we are querying against.
      * @return Whether or not the task represented by the status object is currently being run or
      * is pending.
      */
     private boolean isCurrentlyActive(TaskStatus ts) {
         synchronized (mActiveServices) {
             for (TaskServiceContext serviceContext : mActiveServices) {
                 if (serviceContext.getRunningTask() == ts) {
                     return true;
                 }
             }
             return false;
         }
     }

     /**
      * A task is rescheduled with exponential back-off if the client requests this from their
      * execution logic.
      * A caveat is for idle-mode tasks, for which the idle-mode constraint will usurp the
      * timeliness of the reschedule. For an idle-mode task, no deadline is given.
      * @param failureToReschedule Provided task status that we will reschedule.
      * @return A newly instantiated TaskStatus with the same constraints as the last task except
      * with adjusted timing constraints.
      */
     private TaskStatus getRescheduleTaskForFailure(TaskStatus failureToReschedule) {
         final long elapsedNowMillis = SystemClock.elapsedRealtime();
         final Task task = failureToReschedule.getTask();

         final long initialBackoffMillis = task.getInitialBackoffMillis();
         final int backoffAttempt = failureToReschedule.getNumFailures() + 1;
         long newEarliestRuntimeElapsed = elapsedNowMillis;

         switch (task.getBackoffPolicy()) {
             case Task.BackoffPolicy.LINEAR:
                 newEarliestRuntimeElapsed += initialBackoffMillis * backoffAttempt;
                 break;
             default:
                 if (DEBUG) {
                     Slog.v(TAG, "Unrecognised back-off policy, defaulting to exponential.");
                 }
             case Task.BackoffPolicy.EXPONENTIAL:
                 newEarliestRuntimeElapsed += Math.pow(initialBackoffMillis, backoffAttempt);
                 break;
         }
         long newLatestRuntimeElapsed = failureToReschedule.hasIdleConstraint() ? Long.MAX_VALUE
                 : newEarliestRuntimeElapsed + RESCHEDULE_WINDOW_SLOP_MILLIS;
         return new TaskStatus(failureToReschedule, newEarliestRuntimeElapsed,
                 newLatestRuntimeElapsed, backoffAttempt);
     }

     /**
      * Called after a periodic has executed so we can to re-add it. We take the last execution time
      * of the task to be the time of completion (i.e. the time at which this function is called).
      * This could be inaccurate b/c the task can run for as long as
      * {@link com.android.server.task.TaskServiceContext#EXECUTING_TIMESLICE_MILLIS}, but will lead
      * to underscheduling at least, rather than if we had taken the last execution time to be the
      * start of the execution.
      * @return A new task representing the execution criteria for this instantiation of the
      * recurring task.
      */
     private TaskStatus getRescheduleTaskForPeriodic(TaskStatus periodicToReschedule) {
         final long elapsedNow = SystemClock.elapsedRealtime();
         // Compute how much of the period is remaining.
         long runEarly = Math.max(periodicToReschedule.getLatestRunTimeElapsed() - elapsedNow, 0);
         long newEarliestRunTimeElapsed = elapsedNow + runEarly;
         long period = periodicToReschedule.getTask().getIntervalMillis();
         long newLatestRuntimeElapsed = newEarliestRunTimeElapsed + period;

         if (DEBUG) {
             Slog.v(TAG, "Rescheduling executed periodic. New execution window [" +
                     newEarliestRunTimeElapsed/1000 + ", " + newLatestRuntimeElapsed/1000 + "]s");
         }
         return new TaskStatus(periodicToReschedule, newEarliestRunTimeElapsed,
                 newLatestRuntimeElapsed, 0 /* backoffAttempt */);
     }

     // TaskCompletedListener implementations.

     /**
      * A task just finished executing. We fetch the
      * {@link com.android.server.task.controllers.TaskStatus} from the store and depending on
      * whether we want to reschedule we readd it to the controllers.
      * @param taskStatus Completed task.
      * @param needsReschedule Whether the implementing class should reschedule this task.
      */
     @Override
     public void onTaskCompleted(TaskStatus taskStatus, boolean needsReschedule) {
         if (!stopTrackingTask(taskStatus)) {
             if (DEBUG) {
                 Slog.e(TAG, "Error removing task: could not find task to remove. Was task" +
                         "removed while executing?");
             }
             return;
         }
         if (needsReschedule) {
             TaskStatus rescheduled = getRescheduleTaskForFailure(taskStatus);
             startTrackingTask(rescheduled);
         } else if (taskStatus.getTask().isPeriodic()) {
             TaskStatus rescheduledPeriodic = getRescheduleTaskForPeriodic(taskStatus);
             startTrackingTask(rescheduledPeriodic);
         }
         mHandler.obtainMessage(MSG_CHECK_TASKS).sendToTarget();
     }

     // StateChangedListener implementations.

     /**
      * Off-board work to our handler thread as quickly as possible, b/c this call is probably being
      * made on the main thread.
      * For now this takes the task and if it's ready to run it will run it. In future we might not
      * provide the task, so that the StateChangedListener has to run through its list of tasks to
      * see which are ready. This will further decouple the controllers from the execution logic.
      */
     @Override
     public void onControllerStateChanged() {
         // Post a message to to run through the list of tasks and start/stop any that are eligible.
         mHandler.obtainMessage(MSG_CHECK_TASKS).sendToTarget();
     }

     @Override
     public void onTaskDeadlineExpired(TaskStatus taskStatus) {
         mHandler.obtainMessage(MSG_TASK_EXPIRED, taskStatus);
     }

     /**
      * Disk I/O is finished, take the list of tasks we read from disk and add them to our
      * {@link TaskStore}.
      * This is run on the {@link com.android.server.IoThread} instance, which is a separate thread,
      * and is called once at boot.
      */
     @Override
     public void onTaskMapReadFinished(List<TaskStatus> tasks) {
         synchronized (mTasks) {
             for (TaskStatus ts : tasks) {
                 if (mTasks.contains(ts)) {
                     // An app with BOOT_COMPLETED *might* have decided to reschedule their task, in
                     // the same amount of time it took us to read it from disk. If this is the case
                     // we leave it be.
                     continue;
                 }
                 startTrackingTask(ts);
             }
         }
     }

     private class TaskHandler extends Handler {

         public TaskHandler(Looper looper) {
             super(looper);
         }

         @Override
         public void handleMessage(Message message) {
             switch (message.what) {
                 case MSG_TASK_EXPIRED:
                     final TaskStatus expired = (TaskStatus) message.obj;  // Unused for now.
                     queueReadyTasksForExecutionH();
                     break;
                 case MSG_CHECK_TASKS:
                     // Check the list of tasks and run some of them if we feel inclined.
                     maybeQueueReadyTasksForExecutionH();
                     break;
             }
             maybeRunNextPendingTaskH();
             // Don't remove TASK_EXPIRED in case one came along while processing the queue.
             removeMessages(MSG_CHECK_TASKS);
         }

         /**
          * Run through list of tasks and execute all possible - at least one is expired so we do
          * as many as we can.
          */
         private void queueReadyTasksForExecutionH() {
             synchronized (mTasks) {
                 for (TaskStatus ts : mTasks.getTasks()) {
                     final boolean criteriaSatisfied = ts.isReady();
                     final boolean isRunning = isCurrentlyActive(ts);
                     if (criteriaSatisfied && !isRunning) {
                         synchronized (mPendingTasks) {
                             mPendingTasks.add(ts);
                         }
                     } else if (!criteriaSatisfied && isRunning) {
                         cancelTaskOnServiceContext(ts);
                     }
                 }
             }
         }

         /**
          * The state of at least one task has changed. Here is where we could enforce various
          * policies on when we want to execute tasks.
          * Right now the policy is such:
          *      If >1 of the ready tasks is idle mode we send all of them off
          *      if more than 2 network connectivity tasks are ready we send them all off.
          *      If more than 4 tasks total are ready we send them all off.
          *      TODO: It would be nice to consolidate these sort of high-level policies somewhere.
          */
         private void maybeQueueReadyTasksForExecutionH() {
             synchronized (mTasks) {
                 int idleCount = 0;
                 int connectivityCount = 0;
                 List<TaskStatus> runnableTasks = new ArrayList<TaskStatus>();
                 for (TaskStatus ts : mTasks.getTasks()) {
                     final boolean criteriaSatisfied = ts.isReady();
                     final boolean isRunning = isCurrentlyActive(ts);
                     if (criteriaSatisfied && !isRunning) {
                         if (ts.hasIdleConstraint()) {
                             idleCount++;
                         }
                         if (ts.hasConnectivityConstraint() || ts.hasMeteredConstraint()) {
                             connectivityCount++;
                         }
                         runnableTasks.add(ts);
                     } else if (!criteriaSatisfied && isRunning) {
                         cancelTaskOnServiceContext(ts);
                     }
                 }
                 if (idleCount >= MIN_IDLE_COUNT || connectivityCount >= MIN_CONNECTIVITY_COUNT ||
                         runnableTasks.size() >= MIN_READY_TASKS_COUNT) {
                     for (TaskStatus ts : runnableTasks) {
                         synchronized (mPendingTasks) {
                             mPendingTasks.add(ts);
                         }
                     }
                 }
             }
         }

         /**
          * Checks the state of the pending queue against any available
          * {@link com.android.server.task.TaskServiceContext} that can run a new task.
          * {@link com.android.server.task.TaskServiceContext}.
          */
         private void maybeRunNextPendingTaskH() {
             TaskStatus nextPending;
             synchronized (mPendingTasks) {
                 nextPending = mPendingTasks.poll();
             }
             if (nextPending == null) {
                 return;
             }

             synchronized (mActiveServices) {
                 for (TaskServiceContext tsc : mActiveServices) {
                     if (tsc.isAvailable()) {
                         if (tsc.executeRunnableTask(nextPending)) {
                             return;
                         }
                     }
                 }
             }
         }
     }

     /**
      * Binder stub trampoline implementation
      */
     final class TaskManagerStub extends ITaskManager.Stub {
         /** Cache determination of whether a given app can persist tasks
          * key is uid of the calling app; value is undetermined/true/false
          */
         private final SparseArray<Boolean> mPersistCache = new SparseArray<Boolean>();

         // Determine whether the caller is allowed to persist tasks, with a small cache
         // because the lookup is expensive enough that we'd like to avoid repeating it.
         // This must be called from within the calling app's binder identity!
         private boolean canCallerPersistTasks() {
             final boolean canPersist;
             final int callingUid = Binder.getCallingUid();
             synchronized (mPersistCache) {
                 Boolean cached = mPersistCache.get(callingUid);
                 if (cached) {
                     canPersist = cached.booleanValue();
                 } else {
                     // Persisting tasks is tantamount to running at boot, so we permit
                     // it when the app has declared that it uses the RECEIVE_BOOT_COMPLETED
                     // permission
                     int result = getContext().checkCallingPermission(
                             android.Manifest.permission.RECEIVE_BOOT_COMPLETED);
                     canPersist = (result == PackageManager.PERMISSION_GRANTED);
                     mPersistCache.put(callingUid, canPersist);
                 }
             }
             return canPersist;
         }

         // ITaskManager implementation
         @Override
         public int schedule(Task task) throws RemoteException {
             final boolean canPersist = canCallerPersistTasks();
             final int uid = Binder.getCallingUid();

             long ident = Binder.clearCallingIdentity();
             try {
                 return TaskManagerService.this.schedule(task, uid, canPersist);
             } finally {
                 Binder.restoreCallingIdentity(ident);
             }
         }

         @Override
         public List<Task> getAllPendingTasks() throws RemoteException {
             final int uid = Binder.getCallingUid();

             long ident = Binder.clearCallingIdentity();
             try {
                 return TaskManagerService.this.getPendingTasks(uid);
             } finally {
                 Binder.restoreCallingIdentity(ident);
             }
         }

         @Override
         public void cancelAll() throws RemoteException {
             final int uid = Binder.getCallingUid();

             long ident = Binder.clearCallingIdentity();
             try {
                 TaskManagerService.this.cancelTaskForUid(uid);
             } finally {
                 Binder.restoreCallingIdentity(ident);
             }
         }

         @Override
         public void cancel(int taskId) throws RemoteException {
             final int uid = Binder.getCallingUid();

             long ident = Binder.clearCallingIdentity();
             try {
                 TaskManagerService.this.cancelTask(uid, taskId);
             } finally {
                 Binder.restoreCallingIdentity(ident);
             }
         }

         /**
          * "dumpsys" infrastructure
          */
         @Override
         public void dump(FileDescriptor fd, PrintWriter pw, String[] args) {
             getContext().enforceCallingOrSelfPermission(android.Manifest.permission.DUMP, TAG);

             long identityToken = Binder.clearCallingIdentity();
             try {
                 TaskManagerService.this.dumpInternal(pw);
             } finally {
                 Binder.restoreCallingIdentity(identityToken);
             }
         }
     };

     void dumpInternal(PrintWriter pw) {
         synchronized (mTasks) {
             pw.print("Registered tasks:");
             if (mTasks.size() > 0) {
                 for (TaskStatus ts : mTasks.getTasks()) {
                     pw.println();
                     ts.dump(pw, "  ");
                 }
             } else {
                 pw.println();
                 pw.println("No tasks scheduled.");
             }
         }
         pw.println();
     }
 }
	/*
	* Copyright (C) 2014 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License
	*/

	package com.android.server.task;

	import java.io.FileDescriptor;
	import java.io.PrintWriter;
	import java.util.ArrayList;
	import java.util.Iterator;
	import java.util.List;

	import android.app.task.ITaskManager;
	import android.app.task.Task;
	import android.app.task.TaskManager;
	import android.content.Context;
	import android.content.pm.PackageManager;
	import android.os.Binder;
	import android.os.Handler;
	import android.os.Looper;
	import android.os.Message;
	import android.os.RemoteException;
	import android.os.SystemClock;
	import android.util.Slog;
	import android.util.SparseArray;

	import com.android.server.task.controllers.BatteryController;
	import com.android.server.task.controllers.ConnectivityController;
	import com.android.server.task.controllers.IdleController;
	import com.android.server.task.controllers.StateController;
	import com.android.server.task.controllers.TaskStatus;
	import com.android.server.task.controllers.TimeController;

	import java.util.LinkedList;

	/**
	* Responsible for taking tasks representing work to be performed by a client app, and determining
	* based on the criteria specified when that task should be run against the client application's
	* endpoint.
	* Implements logic for scheduling, and rescheduling tasks. The TaskManagerService knows nothing
	* about constraints, or the state of active tasks. It receives callbacks from the various
	* controllers and completed tasks and operates accordingly.
	*
	* Note on locking: Any operations that manipulate {@link #mTasks} need to lock on that object, and
	* similarly for {@link #mActiveServices}. If both locks need to be held take mTasksSet first and then
	* mActiveService afterwards.
	* @hide
	*/
	public class TaskManagerService extends com.android.server.SystemService
	implements StateChangedListener, TaskCompletedListener, TaskMapReadFinishedListener {
	// TODO: Switch this off for final version.
	static final boolean DEBUG = true;
	/** The number of concurrent tasks we run at one time. */
	private static final int MAX_TASK_CONTEXTS_COUNT = 3;
	static final String TAG = "TaskManager";
	/**
	* When a task fails, it gets rescheduled according to its backoff policy. To be nice, we allow
	* this amount of time from the rescheduled time by which the retry must occur.
	*/
	private static final long RESCHEDULE_WINDOW_SLOP_MILLIS = 5000L;

	/** Master list of tasks. */
	private final TaskStore mTasks;

	static final int MSG_TASK_EXPIRED = 0;
	static final int MSG_CHECK_TASKS = 1;

	// Policy constants
	/**
	* Minimum # of idle tasks that must be ready in order to force the TM to schedule things
	* early.
	*/
	private static final int MIN_IDLE_COUNT = 1;
	/**
	* Minimum # of connectivity tasks that must be ready in order to force the TM to schedule
	* things early.
	*/
	private static final int MIN_CONNECTIVITY_COUNT = 2;
	/**
	* Minimum # of tasks (with no particular constraints) for which the TM will be happy running
	* some work early.
	*/
	private static final int MIN_READY_TASKS_COUNT = 4;

	/**
	* Track Services that have currently active or pending tasks. The index is provided by
	* {@link TaskStatus#getServiceToken()}
	*/
	private final List<TaskServiceContext> mActiveServices = new LinkedList<TaskServiceContext>();
	/** List of controllers that will notify this service of updates to tasks. */
	private List<StateController> mControllers;
	/**
	* Queue of pending tasks. The TaskServiceContext class will receive tasks from this list
	* when ready to execute them.
	*/
	private final LinkedList<TaskStatus> mPendingTasks = new LinkedList<TaskStatus>();

	private final TaskHandler mHandler;
	private final TaskManagerStub mTaskManagerStub;

	/**
	* Entry point from client to schedule the provided task.
	* This will add the task to the
	* @param task Task object containing execution parameters
	* @param uId The package identifier of the application this task is for.
	* @param canPersistTask Whether or not the client has the appropriate permissions for persisting
	* of this task.
	* @return Result of this operation. See <code>TaskManager#RESULT_*</code> return codes.
	*/
	public int schedule(Task task, int uId, boolean canPersistTask) {
	TaskStatus taskStatus = new TaskStatus(task, uId, canPersistTask);
	startTrackingTask(taskStatus);
	return TaskManager.RESULT_SUCCESS;
	}

	public List<Task> getPendingTasks(int uid) {
	ArrayList<Task> outList = new ArrayList<Task>();
	synchronized (mTasks) {
	for (TaskStatus ts : mTasks.getTasks()) {
	if (ts.getUid() == uid) {
	outList.add(ts.getTask());
	}
	}
	}
	return outList;
	}

	/**
	* Entry point from client to cancel all tasks originating from their uid.
	* This will remove the task from the master list, and cancel the task if it was staged for
	* execution or being executed.
	* @param uid To check against for removal of a task.
	*/
	public void cancelTaskForUid(int uid) {
	// Remove from master list.
	synchronized (mTasks) {
	if (!mTasks.removeAllByUid(uid)) {
	// If it's not in the master list, it's nowhere.
	return;
	}
	}
	// Remove from pending queue.
	synchronized (mPendingTasks) {
	Iterator<TaskStatus> it = mPendingTasks.iterator();
	while (it.hasNext()) {
	TaskStatus ts = it.next();
	if (ts.getUid() == uid) {
	it.remove();
	}
	}
	}
	// Cancel if running.
	synchronized (mActiveServices) {
	for (TaskServiceContext tsc : mActiveServices) {
	if (tsc.getRunningTask().getUid() == uid) {
	tsc.cancelExecutingTask();
	}
	}
	}
	}

	/**
	* Entry point from client to cancel the task corresponding to the taskId provided.
	* This will remove the task from the master list, and cancel the task if it was staged for
	* execution or being executed.
	* @param uid Uid of the calling client.
	* @param taskId Id of the task, provided at schedule-time.
	*/
	public void cancelTask(int uid, int taskId) {
	synchronized (mTasks) {
	if (!mTasks.remove(uid, taskId)) {
	// If it's not in the master list, it's nowhere.
	return;
	}
	}
	synchronized (mPendingTasks) {
	Iterator<TaskStatus> it = mPendingTasks.iterator();
	while (it.hasNext()) {
	TaskStatus ts = it.next();
	if (ts.getUid() == uid && ts.getTaskId() == taskId) {
	it.remove();
	// If we got it from pending, it didn't make it to active so return.
	return;
	}
	}
	}
	synchronized (mActiveServices) {
	for (TaskServiceContext tsc : mActiveServices) {
	if (tsc.getRunningTask().getUid() == uid &&
	tsc.getRunningTask().getTaskId() == taskId) {
	tsc.cancelExecutingTask();
	return;
	}
	}
	}
	}

	/**
	* Initializes the system service.
	* <p>
	* Subclasses must define a single argument constructor that accepts the context
	* and passes it to super.
	* </p>
	*
	* @param context The system server context.
	*/
	public TaskManagerService(Context context) {
	super(context);
	mTasks = TaskStore.initAndGet(this);
	mHandler = new TaskHandler(context.getMainLooper());
	mTaskManagerStub = new TaskManagerStub();
	// Create the "runners".
	for (int i = 0; i < MAX_TASK_CONTEXTS_COUNT; i++) {
	mActiveServices.add(
	new TaskServiceContext(this, context.getMainLooper()));
	}
	// Create the controllers.
	mControllers = new LinkedList<StateController>();
	mControllers.add(ConnectivityController.get(this));
	mControllers.add(TimeController.get(this));
	mControllers.add(IdleController.get(this));
	mControllers.add(BatteryController.get(this));
	}

	@Override
	public void onStart() {
	publishBinderService(Context.TASK_SERVICE, mTaskManagerStub);
	}

	/**
	* Called when we have a task status object that we need to insert in our
	* {@link com.android.server.task.TaskStore}, and make sure all the relevant controllers know
	* about.
	*/
	private void startTrackingTask(TaskStatus taskStatus) {
	synchronized (mTasks) {
	mTasks.add(taskStatus);
	}
	for (StateController controller : mControllers) {
	controller.maybeStartTrackingTask(taskStatus);

	}
	}

	/**
	* Called when we want to remove a TaskStatus object that we've finished executing. Returns the
	* object removed.
	*/
	private boolean stopTrackingTask(TaskStatus taskStatus) {
	boolean removed;
	synchronized (mTasks) {
	// Remove from store as well as controllers.
	removed = mTasks.remove(taskStatus);
	}
	if (removed) {
	for (StateController controller : mControllers) {
	controller.maybeStopTrackingTask(taskStatus);
	}
	}
	return removed;
	}

	private boolean cancelTaskOnServiceContext(TaskStatus ts) {
	synchronized (mActiveServices) {
	for (TaskServiceContext tsc : mActiveServices) {
	if (tsc.getRunningTask() == ts) {
	tsc.cancelExecutingTask();
	return true;
	}
	}
	return false;
	}
	}

	/**
	* @param ts TaskStatus we are querying against.
	* @return Whether or not the task represented by the status object is currently being run or
	* is pending.
	*/
	private boolean isCurrentlyActive(TaskStatus ts) {
	synchronized (mActiveServices) {
	for (TaskServiceContext serviceContext : mActiveServices) {
	if (serviceContext.getRunningTask() == ts) {
	return true;
	}
	}
	return false;
	}
	}

	/**
	* A task is rescheduled with exponential back-off if the client requests this from their
	* execution logic.
	* A caveat is for idle-mode tasks, for which the idle-mode constraint will usurp the
	* timeliness of the reschedule. For an idle-mode task, no deadline is given.
	* @param failureToReschedule Provided task status that we will reschedule.
	* @return A newly instantiated TaskStatus with the same constraints as the last task except
	* with adjusted timing constraints.
	*/
	private TaskStatus getRescheduleTaskForFailure(TaskStatus failureToReschedule) {
	final long elapsedNowMillis = SystemClock.elapsedRealtime();
	final Task task = failureToReschedule.getTask();

	final long initialBackoffMillis = task.getInitialBackoffMillis();
	final int backoffAttempt = failureToReschedule.getNumFailures() + 1;
	long newEarliestRuntimeElapsed = elapsedNowMillis;

	switch (task.getBackoffPolicy()) {
	case Task.BackoffPolicy.LINEAR:
	newEarliestRuntimeElapsed += initialBackoffMillis * backoffAttempt;
	break;
	default:
	if (DEBUG) {
	Slog.v(TAG, "Unrecognised back-off policy, defaulting to exponential.");
	}
	case Task.BackoffPolicy.EXPONENTIAL:
	newEarliestRuntimeElapsed += Math.pow(initialBackoffMillis, backoffAttempt);
	break;
	}
	long newLatestRuntimeElapsed = failureToReschedule.hasIdleConstraint() ? Long.MAX_VALUE
	: newEarliestRuntimeElapsed + RESCHEDULE_WINDOW_SLOP_MILLIS;
	return new TaskStatus(failureToReschedule, newEarliestRuntimeElapsed,
	newLatestRuntimeElapsed, backoffAttempt);
	}

	/**
	* Called after a periodic has executed so we can to re-add it. We take the last execution time
	* of the task to be the time of completion (i.e. the time at which this function is called).
	* This could be inaccurate b/c the task can run for as long as
	* {@link com.android.server.task.TaskServiceContext#EXECUTING_TIMESLICE_MILLIS}, but will lead
	* to underscheduling at least, rather than if we had taken the last execution time to be the
	* start of the execution.
	* @return A new task representing the execution criteria for this instantiation of the
	* recurring task.
	*/
	private TaskStatus getRescheduleTaskForPeriodic(TaskStatus periodicToReschedule) {
	final long elapsedNow = SystemClock.elapsedRealtime();
	// Compute how much of the period is remaining.
	long runEarly = Math.max(periodicToReschedule.getLatestRunTimeElapsed() - elapsedNow, 0);
	long newEarliestRunTimeElapsed = elapsedNow + runEarly;
	long period = periodicToReschedule.getTask().getIntervalMillis();
	long newLatestRuntimeElapsed = newEarliestRunTimeElapsed + period;

	if (DEBUG) {
	Slog.v(TAG, "Rescheduling executed periodic. New execution window [" +
	newEarliestRunTimeElapsed/1000 + ", " + newLatestRuntimeElapsed/1000 + "]s");
	}
	return new TaskStatus(periodicToReschedule, newEarliestRunTimeElapsed,
	newLatestRuntimeElapsed, 0 /* backoffAttempt */);
	}

	// TaskCompletedListener implementations.

	/**
	* A task just finished executing. We fetch the
	* {@link com.android.server.task.controllers.TaskStatus} from the store and depending on
	* whether we want to reschedule we readd it to the controllers.
	* @param taskStatus Completed task.
	* @param needsReschedule Whether the implementing class should reschedule this task.
	*/
	@Override
	public void onTaskCompleted(TaskStatus taskStatus, boolean needsReschedule) {
	if (!stopTrackingTask(taskStatus)) {
	if (DEBUG) {
	Slog.e(TAG, "Error removing task: could not find task to remove. Was task" +
	"removed while executing?");
	}
	return;
	}
	if (needsReschedule) {
	TaskStatus rescheduled = getRescheduleTaskForFailure(taskStatus);
	startTrackingTask(rescheduled);
	} else if (taskStatus.getTask().isPeriodic()) {
	TaskStatus rescheduledPeriodic = getRescheduleTaskForPeriodic(taskStatus);
	startTrackingTask(rescheduledPeriodic);
	}
	mHandler.obtainMessage(MSG_CHECK_TASKS).sendToTarget();
	}

	// StateChangedListener implementations.

	/**
	* Off-board work to our handler thread as quickly as possible, b/c this call is probably being
	* made on the main thread.
	* For now this takes the task and if it's ready to run it will run it. In future we might not
	* provide the task, so that the StateChangedListener has to run through its list of tasks to
	* see which are ready. This will further decouple the controllers from the execution logic.
	*/
	@Override
	public void onControllerStateChanged() {
	// Post a message to to run through the list of tasks and start/stop any that are eligible.
	mHandler.obtainMessage(MSG_CHECK_TASKS).sendToTarget();
	}

	@Override
	public void onTaskDeadlineExpired(TaskStatus taskStatus) {
	mHandler.obtainMessage(MSG_TASK_EXPIRED, taskStatus);
	}

	/**
	* Disk I/O is finished, take the list of tasks we read from disk and add them to our
	* {@link TaskStore}.
	* This is run on the {@link com.android.server.IoThread} instance, which is a separate thread,
	* and is called once at boot.
	*/
	@Override
	public void onTaskMapReadFinished(List<TaskStatus> tasks) {
	synchronized (mTasks) {
	for (TaskStatus ts : tasks) {
	if (mTasks.contains(ts)) {
	// An app with BOOT_COMPLETED might have decided to reschedule their task, in
	// the same amount of time it took us to read it from disk. If this is the case
	// we leave it be.
	continue;
	}
	startTrackingTask(ts);
	}
	}
	}

	private class TaskHandler extends Handler {

	public TaskHandler(Looper looper) {
	super(looper);
	}

	@Override
	public void handleMessage(Message message) {
	switch (message.what) {
	case MSG_TASK_EXPIRED:
	final TaskStatus expired = (TaskStatus) message.obj; // Unused for now.
	queueReadyTasksForExecutionH();
	break;
	case MSG_CHECK_TASKS:
	// Check the list of tasks and run some of them if we feel inclined.
	maybeQueueReadyTasksForExecutionH();
	break;
	}
	maybeRunNextPendingTaskH();
	// Don't remove TASK_EXPIRED in case one came along while processing the queue.
	removeMessages(MSG_CHECK_TASKS);
	}

	/**
	* Run through list of tasks and execute all possible - at least one is expired so we do
	* as many as we can.
	*/
	private void queueReadyTasksForExecutionH() {
	synchronized (mTasks) {
	for (TaskStatus ts : mTasks.getTasks()) {
	final boolean criteriaSatisfied = ts.isReady();
	final boolean isRunning = isCurrentlyActive(ts);
	if (criteriaSatisfied && !isRunning) {
	synchronized (mPendingTasks) {
	mPendingTasks.add(ts);
	}
	} else if (!criteriaSatisfied && isRunning) {
	cancelTaskOnServiceContext(ts);
	}
	}
	}
	}

	/**
	* The state of at least one task has changed. Here is where we could enforce various
	* policies on when we want to execute tasks.
	* Right now the policy is such:
	* If >1 of the ready tasks is idle mode we send all of them off
	* if more than 2 network connectivity tasks are ready we send them all off.
	* If more than 4 tasks total are ready we send them all off.
	* TODO: It would be nice to consolidate these sort of high-level policies somewhere.
	*/
	private void maybeQueueReadyTasksForExecutionH() {
	synchronized (mTasks) {
	int idleCount = 0;
	int connectivityCount = 0;
	List<TaskStatus> runnableTasks = new ArrayList<TaskStatus>();
	for (TaskStatus ts : mTasks.getTasks()) {
	final boolean criteriaSatisfied = ts.isReady();
	final boolean isRunning = isCurrentlyActive(ts);
	if (criteriaSatisfied && !isRunning) {
	if (ts.hasIdleConstraint()) {
	idleCount++;
	}
	if (ts.hasConnectivityConstraint() \|\| ts.hasMeteredConstraint()) {
	connectivityCount++;
	}
	runnableTasks.add(ts);
	} else if (!criteriaSatisfied && isRunning) {
	cancelTaskOnServiceContext(ts);
	}
	}
	if (idleCount >= MIN_IDLE_COUNT \|\| connectivityCount >= MIN_CONNECTIVITY_COUNT \|\|
	runnableTasks.size() >= MIN_READY_TASKS_COUNT) {
	for (TaskStatus ts : runnableTasks) {
	synchronized (mPendingTasks) {
	mPendingTasks.add(ts);
	}
	}
	}
	}
	}

	/**
	* Checks the state of the pending queue against any available
	* {@link com.android.server.task.TaskServiceContext} that can run a new task.
	* {@link com.android.server.task.TaskServiceContext}.
	*/
	private void maybeRunNextPendingTaskH() {
	TaskStatus nextPending;
	synchronized (mPendingTasks) {
	nextPending = mPendingTasks.poll();
	}
	if (nextPending == null) {
	return;
	}

	synchronized (mActiveServices) {
	for (TaskServiceContext tsc : mActiveServices) {
	if (tsc.isAvailable()) {
	if (tsc.executeRunnableTask(nextPending)) {
	return;
	}
	}
	}
	}
	}
	}

	/**
	* Binder stub trampoline implementation
	*/
	final class TaskManagerStub extends ITaskManager.Stub {
	/** Cache determination of whether a given app can persist tasks
	* key is uid of the calling app; value is undetermined/true/false
	*/
	private final SparseArray<Boolean> mPersistCache = new SparseArray<Boolean>();

	// Determine whether the caller is allowed to persist tasks, with a small cache
	// because the lookup is expensive enough that we'd like to avoid repeating it.
	// This must be called from within the calling app's binder identity!
	private boolean canCallerPersistTasks() {
	final boolean canPersist;
	final int callingUid = Binder.getCallingUid();
	synchronized (mPersistCache) {
	Boolean cached = mPersistCache.get(callingUid);
	if (cached) {
	canPersist = cached.booleanValue();
	} else {
	// Persisting tasks is tantamount to running at boot, so we permit
	// it when the app has declared that it uses the RECEIVE_BOOT_COMPLETED
	// permission
	int result = getContext().checkCallingPermission(
	android.Manifest.permission.RECEIVE_BOOT_COMPLETED);
	canPersist = (result == PackageManager.PERMISSION_GRANTED);
	mPersistCache.put(callingUid, canPersist);
	}
	}
	return canPersist;
	}

	// ITaskManager implementation
	@Override
	public int schedule(Task task) throws RemoteException {
	final boolean canPersist = canCallerPersistTasks();
	final int uid = Binder.getCallingUid();

	long ident = Binder.clearCallingIdentity();
	try {
	return TaskManagerService.this.schedule(task, uid, canPersist);
	} finally {
	Binder.restoreCallingIdentity(ident);
	}
	}

	@Override
	public List<Task> getAllPendingTasks() throws RemoteException {
	final int uid = Binder.getCallingUid();

	long ident = Binder.clearCallingIdentity();
	try {
	return TaskManagerService.this.getPendingTasks(uid);
	} finally {
	Binder.restoreCallingIdentity(ident);
	}
	}

	@Override
	public void cancelAll() throws RemoteException {
	final int uid = Binder.getCallingUid();

	long ident = Binder.clearCallingIdentity();
	try {
	TaskManagerService.this.cancelTaskForUid(uid);
	} finally {
	Binder.restoreCallingIdentity(ident);
	}
	}

	@Override
	public void cancel(int taskId) throws RemoteException {
	final int uid = Binder.getCallingUid();

	long ident = Binder.clearCallingIdentity();
	try {
	TaskManagerService.this.cancelTask(uid, taskId);
	} finally {
	Binder.restoreCallingIdentity(ident);
	}
	}

	/**
	* "dumpsys" infrastructure
	*/
	@Override
	public void dump(FileDescriptor fd, PrintWriter pw, String[] args) {
	getContext().enforceCallingOrSelfPermission(android.Manifest.permission.DUMP, TAG);

	long identityToken = Binder.clearCallingIdentity();
	try {
	TaskManagerService.this.dumpInternal(pw);
	} finally {
	Binder.restoreCallingIdentity(identityToken);
	}
	}
	};

	void dumpInternal(PrintWriter pw) {
	synchronized (mTasks) {
	pw.print("Registered tasks:");
	if (mTasks.size() > 0) {
	for (TaskStatus ts : mTasks.getTasks()) {
	pw.println();
	ts.dump(pw, " ");
	}
	} else {
	pw.println();
	pw.println("No tasks scheduled.");
	}
	}
	pw.println();
	}
	}