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