• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (C) 2022 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.android.server.job;
18 
19 import android.annotation.NonNull;
20 import android.annotation.Nullable;
21 import android.util.ArraySet;
22 import android.util.Pools;
23 import android.util.SparseArray;
24 
25 import com.android.internal.annotations.VisibleForTesting;
26 import com.android.server.job.controllers.JobStatus;
27 
28 import java.util.ArrayList;
29 import java.util.Collections;
30 import java.util.Comparator;
31 import java.util.List;
32 import java.util.Objects;
33 import java.util.PriorityQueue;
34 
35 /**
36  * A utility class to maintain a sorted list of currently pending jobs. The sorting system is
37  * modeled after topological sort, so the returned order may not always be consistent.
38  */
39 class PendingJobQueue {
40     private final Pools.Pool<AppJobQueue> mAppJobQueuePool = new Pools.SimplePool<>(8);
41 
42     /** Set of currently used queues, keyed by source UID. */
43     private final SparseArray<AppJobQueue> mCurrentQueues = new SparseArray<>();
44     /**
45      * Same set of AppJobQueues as in {@link #mCurrentQueues}, but ordered by the next timestamp
46      * to make iterating through the job list faster.
47      */
48     private final PriorityQueue<AppJobQueue> mOrderedQueues = new PriorityQueue<>(
49             (ajq1, ajq2) -> {
50                 final long t1 = ajq1.peekNextTimestamp();
51                 final long t2 = ajq2.peekNextTimestamp();
52                 if (t1 == AppJobQueue.NO_NEXT_TIMESTAMP) {
53                     if (t2 == AppJobQueue.NO_NEXT_TIMESTAMP) {
54                         return 0;
55                     }
56                     return 1;
57                 } else if (t2 == AppJobQueue.NO_NEXT_TIMESTAMP) {
58                     return -1;
59                 }
60                 final int o1 = ajq1.peekNextOverrideState();
61                 final int o2 = ajq2.peekNextOverrideState();
62                 if (o1 != o2) {
63                     // Higher override state (OVERRIDE_FULL) should be before lower state
64                     // (OVERRIDE_SOFT)
65                     return Integer.compare(o2, o1);
66                 }
67                 return Long.compare(t1, t2);
68             });
69 
70     private int mSize = 0;
71 
72     /**
73      * Whether to batch iteration so that we pull several of an app's jobs from the queue at the
74      * same time (resulting in some out of order pulls) instead of pulling purely based on the
75      * sort order. Batching it this way will mean we try to run several jobs of the same app at the
76      * same, resulting in fewer process restarts, and can allow the iteration runtime to amortize
77      * to O(A*J) instead of O(A*J*log(A)), where A = # apps and J = average # jobs per app.
78      */
79     private boolean mOptimizeIteration = true;
80 
81     /**
82      * Number of jobs that have been pulled from the queue in succession. Used when
83      * {@link #mOptimizeIteration} is true to know when to switch to the next AppJobQueue.
84      */
85     private int mPullCount = 0;
86 
87     private boolean mNeedToResetIterators = false;
88 
add(@onNull JobStatus job)89     void add(@NonNull JobStatus job) {
90         final AppJobQueue ajq = getAppJobQueue(job.getSourceUid(), true);
91         final long prevTimestamp = ajq.peekNextTimestamp();
92         ajq.add(job);
93         mSize++;
94         if (prevTimestamp != ajq.peekNextTimestamp()) {
95             mOrderedQueues.remove(ajq);
96             mOrderedQueues.offer(ajq);
97         }
98     }
99 
addAll(@onNull ArraySet<JobStatus> jobs)100     void addAll(@NonNull ArraySet<JobStatus> jobs) {
101         final SparseArray<List<JobStatus>> jobsByUid = new SparseArray<>();
102         for (int i = jobs.size() - 1; i >= 0; --i) {
103             final JobStatus job = jobs.valueAt(i);
104             List<JobStatus> appJobs = jobsByUid.get(job.getSourceUid());
105             if (appJobs == null) {
106                 appJobs = new ArrayList<>();
107                 jobsByUid.put(job.getSourceUid(), appJobs);
108             }
109             appJobs.add(job);
110         }
111         for (int i = jobsByUid.size() - 1; i >= 0; --i) {
112             final AppJobQueue ajq = getAppJobQueue(jobsByUid.keyAt(i), true);
113             ajq.addAll(jobsByUid.valueAt(i));
114         }
115         mSize += jobs.size();
116         mOrderedQueues.clear();
117     }
118 
clear()119     void clear() {
120         mSize = 0;
121         for (int i = mCurrentQueues.size() - 1; i >= 0; --i) {
122             final AppJobQueue ajq = mCurrentQueues.valueAt(i);
123             ajq.clear();
124             mAppJobQueuePool.release(ajq);
125         }
126         mCurrentQueues.clear();
127         mOrderedQueues.clear();
128     }
129 
contains(@onNull JobStatus job)130     boolean contains(@NonNull JobStatus job) {
131         final AppJobQueue ajq = mCurrentQueues.get(job.getSourceUid());
132         if (ajq == null) {
133             return false;
134         }
135         return ajq.contains(job);
136     }
137 
getAppJobQueue(int uid, boolean create)138     private AppJobQueue getAppJobQueue(int uid, boolean create) {
139         AppJobQueue ajq = mCurrentQueues.get(uid);
140         if (ajq == null && create) {
141             ajq = mAppJobQueuePool.acquire();
142             if (ajq == null) {
143                 ajq = new AppJobQueue();
144             }
145             mCurrentQueues.put(uid, ajq);
146         }
147         return ajq;
148     }
149 
150     @Nullable
next()151     JobStatus next() {
152         if (mNeedToResetIterators) {
153             mOrderedQueues.clear();
154             for (int i = mCurrentQueues.size() - 1; i >= 0; --i) {
155                 final AppJobQueue ajq = mCurrentQueues.valueAt(i);
156                 ajq.resetIterator(0);
157                 mOrderedQueues.offer(ajq);
158             }
159             mNeedToResetIterators = false;
160             // Reset the pull count when the front of the queue changes.
161             mPullCount = 0;
162         } else if (mOrderedQueues.size() == 0) {
163             // Something significant changed, so the priority queue was cleared. Lazily regenerate
164             // the queue.
165             for (int i = mCurrentQueues.size() - 1; i >= 0; --i) {
166                 final AppJobQueue ajq = mCurrentQueues.valueAt(i);
167                 mOrderedQueues.offer(ajq);
168             }
169             // Reset the pull count when the front of the queue changes.
170             mPullCount = 0;
171         }
172         final int numQueues = mOrderedQueues.size();
173         if (numQueues == 0) {
174             return null;
175         }
176 
177         // Increase the pull limit at a slightly faster rate than log(A) increases (until A>=33).
178         // The pull limit increase is intended to balance fairness (one app can't starve out others)
179         // with efficiency (reducing process restarts).
180         // 1-4 apps --> pullLimit = 1, 5-8 apps --> pullLimit = 2, 9+ apps --> pullLimit = 3
181         final int pullLimit = mOptimizeIteration ? Math.min(3, ((numQueues - 1) >>> 2) + 1) : 1;
182 
183         final AppJobQueue earliestQueue = mOrderedQueues.peek();
184         if (earliestQueue != null) {
185             final JobStatus job = earliestQueue.next();
186             // Change the front of the queue if we've pulled pullLimit jobs from the current head
187             // or we're dealing with test jobs
188             // or the current head has no more jobs to provide.
189             if (++mPullCount >= pullLimit
190                     || (job != null && earliestQueue.peekNextOverrideState() != job.overrideState)
191                     || earliestQueue.peekNextTimestamp() == AppJobQueue.NO_NEXT_TIMESTAMP) {
192                 mOrderedQueues.poll();
193                 if (earliestQueue.peekNextTimestamp() != AppJobQueue.NO_NEXT_TIMESTAMP) {
194                     // No need to put back in the queue if it has no more jobs to give.
195                     mOrderedQueues.offer(earliestQueue);
196                 }
197                 // Reset the pull count when the front of the queue changes.
198                 mPullCount = 0;
199             }
200             return job;
201         }
202         return null;
203     }
204 
remove(@onNull JobStatus job)205     boolean remove(@NonNull JobStatus job) {
206         final AppJobQueue ajq = getAppJobQueue(job.getSourceUid(), false);
207         if (ajq == null) {
208             return false;
209         }
210 
211         final long prevTimestamp = ajq.peekNextTimestamp();
212         if (!ajq.remove(job)) {
213             return false;
214         }
215 
216         mSize--;
217         if (ajq.size() == 0) {
218             mCurrentQueues.remove(job.getSourceUid());
219             mOrderedQueues.remove(ajq);
220             ajq.clear();
221             mAppJobQueuePool.release(ajq);
222         } else if (prevTimestamp != ajq.peekNextTimestamp()) {
223             // Removing the job changed the "next timestamp" in the queue, so we need to reinsert
224             // it to fix the ordering.
225             mOrderedQueues.remove(ajq);
226             mOrderedQueues.offer(ajq);
227         }
228 
229         return true;
230     }
231 
232     /** Resets the iterating index to the front of the queue. */
resetIterator()233     void resetIterator() {
234         // Lazily reset the iterating indices (avoid looping through all the current queues until
235         // absolutely necessary).
236         mNeedToResetIterators = true;
237     }
238 
239     @VisibleForTesting
setOptimizeIteration(boolean optimize)240     void setOptimizeIteration(boolean optimize) {
241         mOptimizeIteration = optimize;
242     }
243 
size()244     int size() {
245         return mSize;
246     }
247 
248     private static final class AppJobQueue {
249         static final long NO_NEXT_TIMESTAMP = -1L;
250         static final int NO_NEXT_OVERRIDE_STATE = -1;
251 
252         private static class AdjustedJobStatus {
253             public long adjustedEnqueueTime;
254             public JobStatus job;
255 
clear()256             void clear() {
257                 adjustedEnqueueTime = 0;
258                 job = null;
259             }
260         }
261 
262         private static final Comparator<AdjustedJobStatus> sJobComparator = (aj1, aj2) -> {
263             if (aj1 == aj2) {
264                 return 0;
265             }
266             final JobStatus job1 = aj1.job;
267             final JobStatus job2 = aj2.job;
268             if (job1 == job2) {
269                 return 0;
270             }
271             // Jobs with an override state set (via adb) should be put first as tests/developers
272             // expect the jobs to run immediately.
273             if (job1.overrideState != job2.overrideState) {
274                 // Higher override state (OVERRIDE_FULL) should be before lower state
275                 // (OVERRIDE_SOFT)
276                 return Integer.compare(job2.overrideState, job1.overrideState);
277             }
278 
279             final boolean job1UI = job1.getJob().isUserInitiated();
280             final boolean job2UI = job2.getJob().isUserInitiated();
281             if (job1UI != job2UI) {
282                 // Attempt to run user-initiated jobs ahead of all other jobs.
283                 return job1UI ? -1 : 1;
284             }
285 
286             final boolean job1EJ = job1.isRequestedExpeditedJob();
287             final boolean job2EJ = job2.isRequestedExpeditedJob();
288             if (job1EJ != job2EJ) {
289                 // Attempt to run requested expedited jobs ahead of regular jobs, regardless of
290                 // expedited job quota.
291                 return job1EJ ? -1 : 1;
292             }
293 
294             if (Objects.equals(job1.getNamespace(), job2.getNamespace())) {
295                 final int job1Priority = job1.getEffectivePriority();
296                 final int job2Priority = job2.getEffectivePriority();
297                 if (job1Priority != job2Priority) {
298                     // Use the priority set by an app for intra-app job ordering. Higher
299                     // priority should be before lower priority.
300                     return Integer.compare(job2Priority, job1Priority);
301                 }
302             }
303 
304             if (job1.lastEvaluatedBias != job2.lastEvaluatedBias) {
305                 // Higher bias should go first.
306                 return Integer.compare(job2.lastEvaluatedBias, job1.lastEvaluatedBias);
307             }
308 
309             return Long.compare(job1.enqueueTime, job2.enqueueTime);
310         };
311 
312         private static final Pools.Pool<AdjustedJobStatus> mAdjustedJobStatusPool =
313                 new Pools.SimplePool<>(16);
314 
315         private final List<AdjustedJobStatus> mJobs = new ArrayList<>();
316         private int mCurIndex = 0;
317 
add(@onNull JobStatus jobStatus)318         void add(@NonNull JobStatus jobStatus) {
319             AdjustedJobStatus adjustedJobStatus = mAdjustedJobStatusPool.acquire();
320             if (adjustedJobStatus == null) {
321                 adjustedJobStatus = new AdjustedJobStatus();
322             }
323             adjustedJobStatus.adjustedEnqueueTime = jobStatus.enqueueTime;
324             adjustedJobStatus.job = jobStatus;
325 
326             int where = Collections.binarySearch(mJobs, adjustedJobStatus, sJobComparator);
327             if (where < 0) {
328                 where = ~where;
329             }
330             mJobs.add(where, adjustedJobStatus);
331             if (where < mCurIndex) {
332                 // Shift the current index back to make sure the new job is evaluated on the next
333                 // iteration.
334                 mCurIndex = where;
335             }
336 
337             if (where > 0) {
338                 final long prevTimestamp = mJobs.get(where - 1).adjustedEnqueueTime;
339                 adjustedJobStatus.adjustedEnqueueTime =
340                         Math.max(prevTimestamp, adjustedJobStatus.adjustedEnqueueTime);
341             }
342             final int numJobs = mJobs.size();
343             if (where < numJobs - 1) {
344                 // Potentially need to adjust following job timestamps as well.
345                 for (int i = where; i < numJobs; ++i) {
346                     final AdjustedJobStatus ajs = mJobs.get(i);
347                     if (adjustedJobStatus.adjustedEnqueueTime < ajs.adjustedEnqueueTime) {
348                         // No further need to adjust.
349                         break;
350                     }
351                     ajs.adjustedEnqueueTime = adjustedJobStatus.adjustedEnqueueTime;
352                 }
353             }
354         }
355 
addAll(@onNull List<JobStatus> jobs)356         void addAll(@NonNull List<JobStatus> jobs) {
357             int earliestIndex = Integer.MAX_VALUE;
358 
359             for (int i = jobs.size() - 1; i >= 0; --i) {
360                 final JobStatus job = jobs.get(i);
361 
362                 AdjustedJobStatus adjustedJobStatus = mAdjustedJobStatusPool.acquire();
363                 if (adjustedJobStatus == null) {
364                     adjustedJobStatus = new AdjustedJobStatus();
365                 }
366                 adjustedJobStatus.adjustedEnqueueTime = job.enqueueTime;
367                 adjustedJobStatus.job = job;
368 
369                 int where = Collections.binarySearch(mJobs, adjustedJobStatus, sJobComparator);
370                 if (where < 0) {
371                     where = ~where;
372                 }
373                 mJobs.add(where, adjustedJobStatus);
374                 if (where < mCurIndex) {
375                     // Shift the current index back to make sure the new job is evaluated on the
376                     // next iteration.
377                     mCurIndex = where;
378                 }
379                 earliestIndex = Math.min(earliestIndex, where);
380             }
381 
382             final int numJobs = mJobs.size();
383             for (int i = Math.max(earliestIndex, 1); i < numJobs; ++i) {
384                 final AdjustedJobStatus ajs = mJobs.get(i);
385                 final AdjustedJobStatus prev = mJobs.get(i - 1);
386                 ajs.adjustedEnqueueTime =
387                         Math.max(ajs.adjustedEnqueueTime, prev.adjustedEnqueueTime);
388             }
389         }
390 
clear()391         void clear() {
392             mJobs.clear();
393             mCurIndex = 0;
394         }
395 
contains(@onNull JobStatus job)396         boolean contains(@NonNull JobStatus job) {
397             return indexOf(job) >= 0;
398         }
399 
400         /** Returns the current index of the job, or -1 if the job isn't in the list. */
indexOf(@onNull JobStatus jobStatus)401         private int indexOf(@NonNull JobStatus jobStatus) {
402             // Binary search can't guarantee returning the correct index
403             // if there are multiple jobs whose sorting comparison are 0, so we need to iterate
404             // through the entire list.
405             for (int i = 0, size = mJobs.size(); i < size; ++i) {
406                 AdjustedJobStatus adjustedJobStatus = mJobs.get(i);
407                 if (adjustedJobStatus.job == jobStatus) {
408                     return i;
409                 }
410             }
411             return -1;
412         }
413 
414         @Nullable
next()415         JobStatus next() {
416             if (mCurIndex >= mJobs.size()) {
417                 return null;
418             }
419             return mJobs.get(mCurIndex++).job;
420         }
421 
peekNextOverrideState()422         int peekNextOverrideState() {
423             if (mCurIndex >= mJobs.size()) {
424                 return NO_NEXT_OVERRIDE_STATE;
425             }
426             return mJobs.get(mCurIndex).job.overrideState;
427         }
428 
peekNextTimestamp()429         long peekNextTimestamp() {
430             if (mCurIndex >= mJobs.size()) {
431                 return NO_NEXT_TIMESTAMP;
432             }
433             return mJobs.get(mCurIndex).adjustedEnqueueTime;
434         }
435 
remove(@onNull JobStatus jobStatus)436         boolean remove(@NonNull JobStatus jobStatus) {
437             final int idx = indexOf(jobStatus);
438             if (idx < 0) {
439                 // Doesn't exist...
440                 return false;
441             }
442             final AdjustedJobStatus adjustedJobStatus = mJobs.remove(idx);
443             adjustedJobStatus.clear();
444             mAdjustedJobStatusPool.release(adjustedJobStatus);
445             if (idx < mCurIndex) {
446                 mCurIndex--;
447             }
448             return true;
449         }
450 
451         /**
452          * Resets the internal index to point to the first JobStatus whose adjusted time is equal to
453          * or after the given timestamp.
454          */
resetIterator(long earliestEnqueueTime)455         void resetIterator(long earliestEnqueueTime) {
456             if (earliestEnqueueTime == 0 || mJobs.size() == 0) {
457                 mCurIndex = 0;
458                 return;
459             }
460 
461             // Binary search
462             int low = 0;
463             int high = mJobs.size() - 1;
464 
465             while (low < high) {
466                 int mid = (low + high) >>> 1;
467                 AdjustedJobStatus midVal = mJobs.get(mid);
468 
469                 if (midVal.adjustedEnqueueTime < earliestEnqueueTime) {
470                     low = mid + 1;
471                 } else if (midVal.adjustedEnqueueTime > earliestEnqueueTime) {
472                     high = mid - 1;
473                 } else {
474                     high = mid;
475                 }
476             }
477             mCurIndex = high;
478         }
479 
size()480         int size() {
481             return mJobs.size();
482         }
483     }
484 }
485