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