1 /* 2 * Copyright (C) 2019 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 static android.app.job.JobInfo.NETWORK_TYPE_ANY; 20 import static android.app.job.JobInfo.NETWORK_TYPE_NONE; 21 22 import static org.junit.Assert.assertEquals; 23 import static org.junit.Assert.assertFalse; 24 import static org.junit.Assert.assertNotNull; 25 import static org.junit.Assert.assertNull; 26 import static org.junit.Assert.assertTrue; 27 import static org.junit.Assert.fail; 28 29 import android.app.job.JobInfo; 30 import android.content.ComponentName; 31 import android.platform.test.annotations.LargeTest; 32 import android.util.ArraySet; 33 import android.util.Log; 34 import android.util.SparseArrayMap; 35 import android.util.SparseBooleanArray; 36 import android.util.SparseLongArray; 37 38 import com.android.server.job.controllers.JobStatus; 39 40 import org.junit.Test; 41 42 import java.util.ArrayList; 43 import java.util.List; 44 import java.util.Random; 45 46 public class PendingJobQueueTest { 47 private static final String TAG = PendingJobQueueTest.class.getSimpleName(); 48 49 private static final int[] sRegJobPriorities = { 50 JobInfo.PRIORITY_HIGH, JobInfo.PRIORITY_DEFAULT, 51 JobInfo.PRIORITY_LOW, JobInfo.PRIORITY_MIN 52 }; 53 createJobInfo(int jobId)54 private static JobInfo.Builder createJobInfo(int jobId) { 55 return new JobInfo.Builder(jobId, new ComponentName("foo", "bar")); 56 } 57 createJobStatus(String testTag, JobInfo.Builder jobInfoBuilder, int callingUid)58 private JobStatus createJobStatus(String testTag, JobInfo.Builder jobInfoBuilder, 59 int callingUid) { 60 return createJobStatus(testTag, jobInfoBuilder, callingUid, "PJQTest"); 61 } 62 createJobStatus(String testTag, JobInfo.Builder jobInfoBuilder, int callingUid, String namespace)63 private JobStatus createJobStatus(String testTag, JobInfo.Builder jobInfoBuilder, 64 int callingUid, String namespace) { 65 return JobStatus.createFromJobInfo( 66 jobInfoBuilder.build(), callingUid, "com.android.test", 0, namespace, testTag); 67 } 68 69 @Test testAdd()70 public void testAdd() { 71 List<JobStatus> jobs = new ArrayList<>(); 72 jobs.add(createJobStatus("testAdd", createJobInfo(1), 1)); 73 jobs.add(createJobStatus("testAdd", createJobInfo(2), 2)); 74 jobs.add(createJobStatus("testAdd", createJobInfo(3).setExpedited(true), 3)); 75 jobs.add(createJobStatus("testAdd", createJobInfo(4), 4)); 76 jobs.add(createJobStatus("testAdd", createJobInfo(5).setExpedited(true), 5)); 77 78 PendingJobQueue jobQueue = new PendingJobQueue(); 79 for (int i = 0; i < jobs.size(); ++i) { 80 jobQueue.add(jobs.get(i)); 81 assertEquals(i + 1, jobQueue.size()); 82 } 83 84 JobStatus job; 85 while ((job = jobQueue.next()) != null) { 86 jobs.remove(job); 87 } 88 assertEquals(0, jobs.size()); 89 } 90 91 @Test testAddAll()92 public void testAddAll() { 93 List<JobStatus> jobs = new ArrayList<>(); 94 jobs.add(createJobStatus("testAddAll", createJobInfo(1), 1)); 95 jobs.add(createJobStatus("testAddAll", createJobInfo(2), 2)); 96 jobs.add(createJobStatus("testAddAll", createJobInfo(3).setExpedited(true), 3)); 97 jobs.add(createJobStatus("testAddAll", createJobInfo(4), 4)); 98 jobs.add(createJobStatus("testAddAll", createJobInfo(5).setExpedited(true), 5)); 99 100 PendingJobQueue jobQueue = new PendingJobQueue(); 101 jobQueue.addAll(jobs); 102 assertEquals(jobs.size(), jobQueue.size()); 103 104 JobStatus job; 105 while ((job = jobQueue.next()) != null) { 106 jobs.remove(job); 107 } 108 assertEquals(0, jobs.size()); 109 } 110 111 @Test testClear()112 public void testClear() { 113 List<JobStatus> jobs = new ArrayList<>(); 114 jobs.add(createJobStatus("testClear", createJobInfo(1), 1)); 115 jobs.add(createJobStatus("testClear", createJobInfo(2), 2)); 116 jobs.add(createJobStatus("testClear", createJobInfo(3).setExpedited(true), 3)); 117 jobs.add(createJobStatus("testClear", createJobInfo(4), 4)); 118 jobs.add(createJobStatus("testClear", createJobInfo(5).setExpedited(true), 5)); 119 120 PendingJobQueue jobQueue = new PendingJobQueue(); 121 jobQueue.addAll(jobs); 122 assertEquals(jobs.size(), jobQueue.size()); 123 assertNotNull(jobQueue.next()); 124 125 jobQueue.clear(); 126 assertEquals(0, jobQueue.size()); 127 assertNull(jobQueue.next()); 128 } 129 130 @Test testContains()131 public void testContains() { 132 JobStatus joba1 = createJobStatus("testRemove", createJobInfo(1), 1); 133 JobStatus joba2 = createJobStatus("testRemove", createJobInfo(2), 1); 134 JobStatus jobb1 = createJobStatus("testRemove", createJobInfo(3).setExpedited(true), 2); 135 JobStatus jobb2 = createJobStatus("testRemove", 136 createJobInfo(4).setPriority(JobInfo.PRIORITY_MIN), 2); 137 138 // Make joba1 and joba2 sort-equivalent 139 joba1.enqueueTime = 3; 140 joba2.enqueueTime = 3; 141 jobb1.enqueueTime = 4; 142 jobb2.enqueueTime = 1; 143 144 PendingJobQueue jobQueue = new PendingJobQueue(); 145 146 assertFalse(jobQueue.contains(joba1)); 147 assertFalse(jobQueue.contains(joba2)); 148 assertFalse(jobQueue.contains(jobb1)); 149 assertFalse(jobQueue.contains(jobb2)); 150 151 jobQueue.add(joba1); 152 153 assertTrue(jobQueue.contains(joba1)); 154 assertFalse(jobQueue.contains(joba2)); 155 assertFalse(jobQueue.contains(jobb1)); 156 assertFalse(jobQueue.contains(jobb2)); 157 158 jobQueue.add(jobb1); 159 160 assertTrue(jobQueue.contains(joba1)); 161 assertFalse(jobQueue.contains(joba2)); 162 assertTrue(jobQueue.contains(jobb1)); 163 assertFalse(jobQueue.contains(jobb2)); 164 165 jobQueue.add(jobb2); 166 167 assertTrue(jobQueue.contains(joba1)); 168 assertFalse(jobQueue.contains(joba2)); 169 assertTrue(jobQueue.contains(jobb1)); 170 assertTrue(jobQueue.contains(jobb2)); 171 172 jobQueue.add(joba2); 173 174 assertTrue(jobQueue.contains(joba1)); 175 assertTrue(jobQueue.contains(joba2)); 176 assertTrue(jobQueue.contains(jobb1)); 177 assertTrue(jobQueue.contains(jobb2)); 178 } 179 180 @Test testRemove()181 public void testRemove() { 182 List<JobStatus> jobs = new ArrayList<>(); 183 jobs.add(createJobStatus("testRemove", createJobInfo(1), 1)); 184 jobs.add(createJobStatus("testRemove", createJobInfo(2), 2)); 185 jobs.add(createJobStatus("testRemove", createJobInfo(3).setExpedited(true), 3)); 186 jobs.add(createJobStatus("testRemove", createJobInfo(4), 4)); 187 jobs.add(createJobStatus("testRemove", createJobInfo(5).setExpedited(true), 5)); 188 189 PendingJobQueue jobQueue = new PendingJobQueue(); 190 jobQueue.addAll(jobs); 191 192 ArraySet<JobStatus> removed = new ArraySet<>(); 193 JobStatus job; 194 for (int i = 0; i < jobs.size(); ++i) { 195 jobQueue.remove(jobs.get(i)); 196 removed.add(jobs.get(i)); 197 198 assertEquals(jobs.size() - i - 1, jobQueue.size()); 199 200 jobQueue.resetIterator(); 201 while ((job = jobQueue.next()) != null) { 202 assertFalse("Queue retained a removed job " + testJobToString(job), 203 removed.contains(job)); 204 } 205 } 206 assertNull(jobQueue.next()); 207 assertEquals(0, jobQueue.size()); 208 } 209 210 @Test testRemove_duringIteration()211 public void testRemove_duringIteration() { 212 List<JobStatus> jobs = new ArrayList<>(); 213 jobs.add(createJobStatus("testRemove", createJobInfo(1), 1)); 214 jobs.add(createJobStatus("testRemove", createJobInfo(2), 2)); 215 jobs.add(createJobStatus("testRemove", createJobInfo(3).setExpedited(true), 3)); 216 jobs.add(createJobStatus("testRemove", createJobInfo(4), 4)); 217 jobs.add(createJobStatus("testRemove", createJobInfo(5).setExpedited(true), 5)); 218 219 PendingJobQueue jobQueue = new PendingJobQueue(); 220 jobQueue.addAll(jobs); 221 222 ArraySet<JobStatus> removed = new ArraySet<>(); 223 JobStatus job; 224 jobQueue.resetIterator(); 225 while ((job = jobQueue.next()) != null) { 226 jobQueue.remove(job); 227 removed.add(job); 228 assertFalse("Queue retained a removed job " + testJobToString(job), 229 jobQueue.contains(job)); 230 } 231 assertNull(jobQueue.next()); 232 assertEquals(0, jobQueue.size()); 233 } 234 235 @Test testRemove_outOfOrder()236 public void testRemove_outOfOrder() { 237 List<JobStatus> jobs = new ArrayList<>(); 238 JobStatus job1 = createJobStatus("testRemove", createJobInfo(1), 1); 239 JobStatus job2 = createJobStatus("testRemove", createJobInfo(2), 1); 240 JobStatus job3 = createJobStatus("testRemove", createJobInfo(3).setExpedited(true), 1); 241 JobStatus job4 = createJobStatus("testRemove", 242 createJobInfo(4).setPriority(JobInfo.PRIORITY_MIN), 1); 243 JobStatus job5 = createJobStatus("testRemove", createJobInfo(5).setExpedited(true), 1); 244 245 // Enqueue order (by ID): 4, 5, 3, {1,2 -- at the same time} 246 job1.enqueueTime = 3; 247 job2.enqueueTime = 3; 248 job3.enqueueTime = 4; 249 job4.enqueueTime = 1; 250 job5.enqueueTime = 2; 251 252 // 1 & 2 have the same enqueue time (could happen at boot), so ordering won't be consistent 253 // between the two 254 // Result job order should be (by ID): 5, 3, {1,2}, {1,2}, 4 255 256 // Intended removal order (by ID): 5, 3, 2, 1, 4 257 jobs.add(job5); 258 jobs.add(job3); 259 jobs.add(job2); 260 jobs.add(job1); 261 jobs.add(job4); 262 263 PendingJobQueue jobQueue = new PendingJobQueue(); 264 jobQueue.addAll(jobs); 265 266 ArraySet<JobStatus> removed = new ArraySet<>(); 267 JobStatus job; 268 while ((job = jobQueue.next()) != null) { 269 Log.d(TAG, testJobToString(job)); 270 } 271 for (int i = 0; i < jobs.size(); ++i) { 272 jobQueue.remove(jobs.get(i)); 273 removed.add(jobs.get(i)); 274 275 assertEquals(jobs.size() - i - 1, jobQueue.size()); 276 277 jobQueue.resetIterator(); 278 while ((job = jobQueue.next()) != null) { 279 assertFalse("Queue retained a removed job " + testJobToString(job), 280 removed.contains(job)); 281 } 282 } 283 assertNull(jobQueue.next()); 284 285 // Intended removal order (by ID): 3, 1, 2, 5, 4 286 jobs.clear(); 287 jobs.add(job3); 288 jobs.add(job1); 289 jobs.add(job5); 290 jobs.add(job2); 291 jobs.add(job4); 292 293 jobQueue.addAll(jobs); 294 295 removed.clear(); 296 for (int i = 0; i < jobs.size(); ++i) { 297 jobQueue.remove(jobs.get(i)); 298 removed.add(jobs.get(i)); 299 300 assertEquals(jobs.size() - i - 1, jobQueue.size()); 301 302 jobQueue.resetIterator(); 303 while ((job = jobQueue.next()) != null) { 304 assertFalse("Queue retained a removed job " + testJobToString(job), 305 removed.contains(job)); 306 } 307 } 308 assertNull(jobQueue.next()); 309 310 // Intended removal order (by ID): 3, 2, 1, 4, 5 311 jobs.clear(); 312 jobs.add(job3); 313 jobs.add(job2); 314 jobs.add(job1); 315 jobs.add(job4); 316 jobs.add(job5); 317 318 jobQueue.addAll(jobs); 319 320 removed.clear(); 321 for (int i = 0; i < jobs.size(); ++i) { 322 jobQueue.remove(jobs.get(i)); 323 removed.add(jobs.get(i)); 324 325 assertEquals(jobs.size() - i - 1, jobQueue.size()); 326 327 jobQueue.resetIterator(); 328 while ((job = jobQueue.next()) != null) { 329 assertFalse("Queue retained a removed job " + testJobToString(job), 330 removed.contains(job)); 331 } 332 } 333 assertNull(jobQueue.next()); 334 } 335 336 @Test testPendingJobSorting()337 public void testPendingJobSorting() { 338 PendingJobQueue jobQueue = new PendingJobQueue(); 339 340 // First letter in job variable name indicate regular (r) or expedited (e). 341 // Capital letters in job variable name indicate the app/UID. 342 // Numbers in job variable name indicate the enqueue time. 343 // Expected sort order: 344 // eA7 > rA1 > eB6 > rB2 > eC3 > rD4 > eE5 > eF9 > rF8 > eC11 > rC10 > rG12 > rG13 > eE14 345 // Intentions: 346 // * A jobs let us test skipping both regular and expedited jobs of other apps 347 // * B jobs let us test skipping only regular job of another app without going too far 348 // * C jobs test that regular jobs don't skip over other app's jobs and that EJs only 349 // skip up to level of the earliest regular job 350 // * E jobs test that expedited jobs don't skip the line when the app has no regular jobs 351 // * F jobs test correct expedited/regular ordering doesn't push jobs too high in list 352 // * G jobs test correct ordering for regular jobs 353 // * H job tests correct behavior when enqueue times are the same 354 JobStatus rA1 = createJobStatus("testPendingJobSorting", createJobInfo(1), 1); 355 JobStatus rB2 = createJobStatus("testPendingJobSorting", createJobInfo(2), 2); 356 JobStatus eC3 = createJobStatus("testPendingJobSorting", 357 createJobInfo(3).setExpedited(true), 3); 358 JobStatus rD4 = createJobStatus("testPendingJobSorting", createJobInfo(4), 4); 359 JobStatus eE5 = createJobStatus("testPendingJobSorting", 360 createJobInfo(5).setExpedited(true), 5); 361 JobStatus eB6 = createJobStatus("testPendingJobSorting", 362 createJobInfo(6).setExpedited(true), 2); 363 JobStatus eA7 = createJobStatus("testPendingJobSorting", 364 createJobInfo(7).setExpedited(true), 1); 365 JobStatus rH8 = createJobStatus("testPendingJobSorting", createJobInfo(8), 8); 366 JobStatus rF8 = createJobStatus("testPendingJobSorting", createJobInfo(8), 6); 367 JobStatus eF9 = createJobStatus("testPendingJobSorting", 368 createJobInfo(9).setExpedited(true), 6); 369 JobStatus rC10 = createJobStatus("testPendingJobSorting", createJobInfo(10), 3); 370 JobStatus eC11 = createJobStatus("testPendingJobSorting", 371 createJobInfo(11).setExpedited(true), 3); 372 JobStatus rG12 = createJobStatus("testPendingJobSorting", createJobInfo(12), 7); 373 JobStatus rG13 = createJobStatus("testPendingJobSorting", createJobInfo(13), 7); 374 JobStatus eE14 = createJobStatus("testPendingJobSorting", 375 createJobInfo(14).setExpedited(true), 5); 376 377 rA1.enqueueTime = 10; 378 rB2.enqueueTime = 20; 379 eC3.enqueueTime = 30; 380 rD4.enqueueTime = 40; 381 eE5.enqueueTime = 50; 382 eB6.enqueueTime = 60; 383 eA7.enqueueTime = 70; 384 rF8.enqueueTime = 80; 385 rH8.enqueueTime = 80; 386 eF9.enqueueTime = 90; 387 rC10.enqueueTime = 100; 388 eC11.enqueueTime = 110; 389 rG12.enqueueTime = 120; 390 rG13.enqueueTime = 130; 391 eE14.enqueueTime = 140; 392 393 // Add in random order so sorting is apparent. 394 jobQueue.add(eC3); 395 jobQueue.add(eE5); 396 jobQueue.add(rA1); 397 jobQueue.add(rG13); 398 jobQueue.add(rD4); 399 jobQueue.add(eA7); 400 jobQueue.add(rG12); 401 jobQueue.add(rH8); 402 jobQueue.add(rF8); 403 jobQueue.add(eB6); 404 jobQueue.add(eE14); 405 jobQueue.add(eF9); 406 jobQueue.add(rB2); 407 jobQueue.add(rC10); 408 jobQueue.add(eC11); 409 410 JobStatus job; 411 final JobStatus[] expectedPureOrder = new JobStatus[]{ 412 eC3, rD4, eE5, eB6, rB2, eA7, rA1, rH8, eF9, rF8, eC11, rC10, rG12, rG13, eE14}; 413 int idx = 0; 414 jobQueue.setOptimizeIteration(false); 415 checkPendingJobInvariants(jobQueue); 416 jobQueue.resetIterator(); 417 while ((job = jobQueue.next()) != null) { 418 assertEquals("List wasn't correctly sorted @ index " + idx, 419 expectedPureOrder[idx].getJobId(), job.getJobId()); 420 idx++; 421 } 422 423 final JobStatus[] expectedOptimizedOrder = new JobStatus[]{ 424 eC3, eC11, rD4, eE5, eE14, eB6, rB2, eA7, rA1, rH8, eF9, rF8, rC10, rG12, rG13}; 425 idx = 0; 426 jobQueue.setOptimizeIteration(true); 427 checkPendingJobInvariants(jobQueue); 428 jobQueue.resetIterator(); 429 while ((job = jobQueue.next()) != null) { 430 assertEquals("Optimized list wasn't correctly sorted @ index " + idx, 431 expectedOptimizedOrder[idx].getJobId(), job.getJobId()); 432 idx++; 433 } 434 } 435 436 @Test testPendingJobSorting_namespacing()437 public void testPendingJobSorting_namespacing() { 438 PendingJobQueue jobQueue = new PendingJobQueue(); 439 440 // First letter in job variable name indicate regular (r) or expedited (e). 441 // Capital letters in job variable name indicate the app/UID. 442 // Third letter (x, y, z) indicates the namespace. 443 // Numbers in job variable name indicate the enqueue time. 444 // Expected sort order: 445 // eCx3 > rDx4 > eBy6 > rBy2 > eAy7 > rAx1 > eCy8 > rEz9 > rEz5 446 // Intentions: 447 // * A jobs test expedited is before regular, regardless of namespace 448 // * B jobs test expedited is before regular, in the same namespace 449 // * C jobs test sorting by priority with different namespaces 450 // * E jobs test sorting by priority in the same namespace 451 final String namespaceX = null; 452 final String namespaceY = "y"; 453 final String namespaceZ = "z"; 454 JobStatus rAx1 = createJobStatus("testPendingJobSorting", 455 createJobInfo(1), 1, namespaceX); 456 JobStatus rBy2 = createJobStatus("testPendingJobSorting", 457 createJobInfo(2), 2, namespaceY); 458 JobStatus eCx3 = createJobStatus("testPendingJobSorting", 459 createJobInfo(3).setExpedited(true).setPriority(JobInfo.PRIORITY_HIGH), 460 3, namespaceX); 461 JobStatus rDx4 = createJobStatus("testPendingJobSorting", 462 createJobInfo(4), 4, namespaceX); 463 JobStatus rEz5 = createJobStatus("testPendingJobSorting", 464 createJobInfo(5).setPriority(JobInfo.PRIORITY_LOW), 5, namespaceZ); 465 JobStatus eBy6 = createJobStatus("testPendingJobSorting", 466 createJobInfo(6).setExpedited(true), 2, namespaceY); 467 JobStatus eAy7 = createJobStatus("testPendingJobSorting", 468 createJobInfo(7).setExpedited(true), 1, namespaceY); 469 JobStatus eCy8 = createJobStatus("testPendingJobSorting", 470 createJobInfo(8).setExpedited(true).setPriority(JobInfo.PRIORITY_MAX), 471 3, namespaceY); 472 JobStatus rEz9 = createJobStatus("testPendingJobSorting", 473 createJobInfo(9).setPriority(JobInfo.PRIORITY_HIGH), 5, namespaceZ); 474 475 rAx1.enqueueTime = 10; 476 rBy2.enqueueTime = 20; 477 eCx3.enqueueTime = 30; 478 rDx4.enqueueTime = 40; 479 rEz5.enqueueTime = 50; 480 eBy6.enqueueTime = 60; 481 eAy7.enqueueTime = 70; 482 eCy8.enqueueTime = 80; 483 rEz9.enqueueTime = 90; 484 485 // Add in random order so sorting is apparent. 486 jobQueue.add(rEz9); 487 jobQueue.add(eCy8); 488 jobQueue.add(rDx4); 489 jobQueue.add(rEz5); 490 jobQueue.add(rBy2); 491 jobQueue.add(rAx1); 492 jobQueue.add(eCx3); 493 jobQueue.add(eBy6); 494 jobQueue.add(eAy7); 495 496 JobStatus job; 497 final JobStatus[] expectedPureOrder = new JobStatus[]{ 498 eCx3, rDx4, eBy6, rBy2, eAy7, rAx1, eCy8, rEz9, rEz5}; 499 int idx = 0; 500 jobQueue.setOptimizeIteration(false); 501 checkPendingJobInvariants(jobQueue); 502 jobQueue.resetIterator(); 503 while ((job = jobQueue.next()) != null) { 504 assertEquals("List wasn't correctly sorted @ index " + idx, 505 expectedPureOrder[idx].getJobId(), job.getJobId()); 506 idx++; 507 } 508 509 final JobStatus[] expectedOptimizedOrder = new JobStatus[]{ 510 eCx3, eCy8, rDx4, eBy6, rBy2, eAy7, rAx1, rEz9, rEz5}; 511 idx = 0; 512 jobQueue.setOptimizeIteration(true); 513 checkPendingJobInvariants(jobQueue); 514 jobQueue.resetIterator(); 515 while ((job = jobQueue.next()) != null) { 516 assertEquals("Optimized list wasn't correctly sorted @ index " + idx, 517 expectedOptimizedOrder[idx].getJobId(), job.getJobId()); 518 idx++; 519 } 520 } 521 522 @Test testPendingJobSorting_Random()523 public void testPendingJobSorting_Random() { 524 PendingJobQueue jobQueue = new PendingJobQueue(); 525 Random random = new Random(1); // Always use the same series of pseudo random values. 526 527 for (int i = 0; i < 5000; ++i) { 528 final boolean ui = random.nextBoolean(); 529 final boolean ej = !ui && random.nextBoolean(); 530 JobStatus job = createJobStatus("testPendingJobSorting_Random", 531 createJobInfo(i).setExpedited(ej).setUserInitiated(ui) 532 .setRequiredNetworkType(ui ? NETWORK_TYPE_ANY : NETWORK_TYPE_NONE), 533 random.nextInt(250)); 534 job.enqueueTime = random.nextInt(1_000_000); 535 jobQueue.add(job); 536 } 537 538 checkPendingJobInvariants(jobQueue); 539 } 540 541 @Test testPendingJobSorting_Random_namespacing()542 public void testPendingJobSorting_Random_namespacing() { 543 PendingJobQueue jobQueue = new PendingJobQueue(); 544 Random random = new Random(1); // Always use the same series of pseudo random values. 545 546 for (int i = 0; i < 5000; ++i) { 547 JobStatus job = createJobStatus("testPendingJobSorting_Random", 548 createJobInfo(i).setExpedited(random.nextBoolean()), random.nextInt(250), 549 "namespace" + random.nextInt(5)); 550 job.enqueueTime = random.nextInt(1_000_000); 551 jobQueue.add(job); 552 } 553 554 checkPendingJobInvariants(jobQueue); 555 } 556 557 @Test testPendingJobSortingTransitivity()558 public void testPendingJobSortingTransitivity() { 559 PendingJobQueue jobQueue = new PendingJobQueue(); 560 // Always use the same series of pseudo random values. 561 for (int seed : new int[]{1337, 7357, 606, 6357, 41106010, 3, 2, 1}) { 562 Random random = new Random(seed); 563 564 jobQueue.clear(); 565 566 for (int i = 0; i < 300; ++i) { 567 final boolean ui = random.nextBoolean(); 568 final boolean ej = !ui && random.nextBoolean(); 569 JobStatus job = createJobStatus("testPendingJobSortingTransitivity", 570 createJobInfo(i).setExpedited(ej).setUserInitiated(ui) 571 .setRequiredNetworkType(ui ? NETWORK_TYPE_ANY : NETWORK_TYPE_NONE), 572 random.nextInt(50)); 573 job.enqueueTime = random.nextInt(1_000_000); 574 job.overrideState = random.nextInt(4); 575 jobQueue.add(job); 576 } 577 578 checkPendingJobInvariants(jobQueue); 579 } 580 } 581 582 @Test 583 @LargeTest testPendingJobSortingTransitivity_Concentrated()584 public void testPendingJobSortingTransitivity_Concentrated() { 585 PendingJobQueue jobQueue = new PendingJobQueue(); 586 // Always use the same series of pseudo random values. 587 for (int seed : new int[]{1337, 6000, 637739, 6357, 1, 7, 13}) { 588 Random random = new Random(seed); 589 590 jobQueue.clear(); 591 592 for (int i = 0; i < 300; ++i) { 593 final boolean ui = random.nextFloat() < .02; 594 final boolean ej = !ui && random.nextFloat() < .03; 595 JobStatus job = createJobStatus("testPendingJobSortingTransitivity_Concentrated", 596 createJobInfo(i).setExpedited(ej).setUserInitiated(ui) 597 .setRequiredNetworkType(ui ? NETWORK_TYPE_ANY : NETWORK_TYPE_NONE), 598 random.nextInt(20)); 599 job.enqueueTime = random.nextInt(250); 600 job.overrideState = random.nextFloat() < .01 601 ? JobStatus.OVERRIDE_SORTING : JobStatus.OVERRIDE_NONE; 602 jobQueue.add(job); 603 Log.d(TAG, testJobToString(job)); 604 } 605 606 checkPendingJobInvariants(jobQueue); 607 } 608 } 609 610 @Test 611 public void testPendingJobSorting_Random_WithPriority() { 612 PendingJobQueue jobQueue = new PendingJobQueue(); 613 Random random = new Random(1); // Always use the same series of pseudo random values. 614 615 for (int i = 0; i < 5000; ++i) { 616 final boolean isEj = random.nextBoolean(); 617 final int priority; 618 if (isEj) { 619 priority = random.nextBoolean() ? JobInfo.PRIORITY_MAX : JobInfo.PRIORITY_HIGH; 620 } else { 621 priority = sRegJobPriorities[random.nextInt(sRegJobPriorities.length)]; 622 } 623 JobStatus job = createJobStatus("testPendingJobSorting_Random_WithPriority", 624 createJobInfo(i).setExpedited(isEj).setPriority(priority), 625 random.nextInt(250)); 626 job.enqueueTime = random.nextInt(1_000_000); 627 jobQueue.add(job); 628 } 629 630 checkPendingJobInvariants(jobQueue); 631 } 632 633 @Test 634 public void testPendingJobSortingTransitivity_WithPriority() { 635 PendingJobQueue jobQueue = new PendingJobQueue(); 636 // Always use the same series of pseudo random values. 637 for (int seed : new int[]{1337, 7357, 606, 6357, 41106010, 3, 2, 1}) { 638 Random random = new Random(seed); 639 640 jobQueue.clear(); 641 642 for (int i = 0; i < 300; ++i) { 643 final boolean isEj = random.nextBoolean(); 644 final int priority; 645 if (isEj) { 646 priority = random.nextBoolean() ? JobInfo.PRIORITY_MAX : JobInfo.PRIORITY_HIGH; 647 } else { 648 priority = sRegJobPriorities[random.nextInt(sRegJobPriorities.length)]; 649 } 650 JobStatus job = createJobStatus("testPendingJobSortingTransitivity_WithPriority", 651 createJobInfo(i).setExpedited(isEj).setPriority(priority), 652 random.nextInt(50)); 653 job.enqueueTime = random.nextInt(1_000_000); 654 job.overrideState = random.nextInt(4); 655 jobQueue.add(job); 656 } 657 658 checkPendingJobInvariants(jobQueue); 659 } 660 } 661 662 @Test 663 @LargeTest 664 public void testPendingJobSortingTransitivity_Concentrated_WithPriority() { 665 PendingJobQueue jobQueue = new PendingJobQueue(); 666 // Always use the same series of pseudo random values. 667 for (int seed : new int[]{1337, 6000, 637739, 6357, 1, 7, 13}) { 668 Random random = new Random(seed); 669 670 jobQueue.clear(); 671 672 for (int i = 0; i < 300; ++i) { 673 final boolean isEj = random.nextFloat() < .03; 674 final int priority; 675 if (isEj) { 676 priority = random.nextBoolean() ? JobInfo.PRIORITY_MAX : JobInfo.PRIORITY_HIGH; 677 } else { 678 priority = sRegJobPriorities[random.nextInt(sRegJobPriorities.length)]; 679 } 680 JobStatus job = createJobStatus( 681 "testPendingJobSortingTransitivity_Concentrated_WithPriority", 682 createJobInfo(i).setExpedited(isEj).setPriority(priority), 683 random.nextInt(20)); 684 job.enqueueTime = random.nextInt(250); 685 job.overrideState = random.nextFloat() < .01 686 ? JobStatus.OVERRIDE_SORTING : JobStatus.OVERRIDE_NONE; 687 jobQueue.add(job); 688 Log.d(TAG, testJobToString(job)); 689 } 690 691 checkPendingJobInvariants(jobQueue); 692 } 693 } 694 695 private void checkPendingJobInvariants(PendingJobQueue jobQueue) { 696 final SparseBooleanArray eJobSeen = new SparseBooleanArray(); 697 final SparseBooleanArray regJobSeen = new SparseBooleanArray(); 698 // Latest priority enqueue times seen for each priority+namespace for each app. 699 final SparseArrayMap<String, SparseLongArray> latestPriorityRegEnqueueTimesPerUid = 700 new SparseArrayMap<>(); 701 final SparseArrayMap<String, SparseLongArray> latestPriorityEjEnqueueTimesPerUid = 702 new SparseArrayMap<>(); 703 final int noEntry = -1; 704 int prevOverrideState = noEntry; 705 706 JobStatus job; 707 jobQueue.resetIterator(); 708 int count = 0; 709 while ((job = jobQueue.next()) != null) { 710 count++; 711 final int uid = job.getSourceUid(); 712 713 // Invariant #1: All jobs are sorted by override state 714 // Invariant #2: All jobs (for a UID) are sorted by priority order 715 // Invariant #3: Jobs (for a UID) with the same priority are sorted by enqueue time. 716 // Invariant #4: User-initiated jobs (for a UID) should be before all other jobs. 717 // Invariant #5: EJs (for a UID) should be before regular jobs 718 719 // Invariant 1 720 if (prevOverrideState != job.overrideState) { 721 if (prevOverrideState != noEntry) { 722 assertTrue(prevOverrideState > job.overrideState); 723 } 724 // Override state can make ordering weird. Clear the other cached states 725 // to avoid confusion in the other checks. 726 latestPriorityEjEnqueueTimesPerUid.clear(); 727 latestPriorityRegEnqueueTimesPerUid.clear(); 728 eJobSeen.clear(); 729 regJobSeen.clear(); 730 prevOverrideState = job.overrideState; 731 } 732 733 final int priority = job.getEffectivePriority(); 734 final SparseArrayMap<String, SparseLongArray> latestPriorityEnqueueTimesPerUid = 735 job.isRequestedExpeditedJob() 736 ? latestPriorityEjEnqueueTimesPerUid 737 : latestPriorityRegEnqueueTimesPerUid; 738 SparseLongArray latestPriorityEnqueueTimes = 739 latestPriorityEnqueueTimesPerUid.get(uid, job.getNamespace()); 740 if (latestPriorityEnqueueTimes != null) { 741 // Invariant 2 742 for (int p = priority - 1; p >= JobInfo.PRIORITY_MIN; --p) { 743 // If we haven't seen the priority, there shouldn't be an entry in the array. 744 assertEquals("Jobs not properly sorted by priority for uid " + uid, 745 noEntry, latestPriorityEnqueueTimes.get(p, noEntry)); 746 } 747 748 // Invariant 3 749 final long lastSeenPriorityEnqueueTime = 750 latestPriorityEnqueueTimes.get(priority, noEntry); 751 if (lastSeenPriorityEnqueueTime != noEntry) { 752 assertTrue("Jobs with same priority for uid " + uid 753 + " not sorted by enqueue time: " 754 + lastSeenPriorityEnqueueTime + " before " + job.enqueueTime, 755 lastSeenPriorityEnqueueTime <= job.enqueueTime); 756 } 757 } else { 758 latestPriorityEnqueueTimes = new SparseLongArray(); 759 latestPriorityEnqueueTimesPerUid.add( 760 uid, job.getNamespace(), latestPriorityEnqueueTimes); 761 } 762 latestPriorityEnqueueTimes.put(priority, job.enqueueTime); 763 764 if (job.isRequestedExpeditedJob()) { 765 eJobSeen.put(uid, true); 766 } else if (!job.getJob().isUserInitiated()) { 767 regJobSeen.put(uid, true); 768 } 769 770 // Invariant 4 771 if (job.getJob().isUserInitiated()) { 772 if (eJobSeen.get(uid)) { 773 fail("UID " + uid + " had a UIJ ordered after an EJ"); 774 } 775 if (regJobSeen.get(uid)) { 776 fail("UID " + uid + " had a UIJ ordered after a regular job"); 777 } 778 } 779 780 // Invariant 5 781 if (job.isRequestedExpeditedJob() && regJobSeen.get(uid)) { 782 fail("UID " + uid + " had an EJ ordered after a regular job"); 783 } 784 } 785 assertEquals("Iterator didn't go through all jobs", jobQueue.size(), count); 786 } 787 788 private static String testJobToString(JobStatus job) { 789 return "testJob " + job.getSourceUid() + "/" + job.getNamespace() + "/" + job.getJobId() 790 + "/o" + job.overrideState 791 + "/p" + job.getEffectivePriority() 792 + "/b" + job.lastEvaluatedBias 793 + "/" 794 + (job.isRequestedExpeditedJob() 795 ? "e" : (job.getJob().isUserInitiated() ? "u" : "r")) 796 + "@" + job.enqueueTime; 797 } 798 } 799