1 package android.os; 2 3 import android.annotation.NonNull; 4 import android.annotation.Nullable; 5 import android.annotation.SystemApi; 6 import android.annotation.TestApi; 7 import android.compat.annotation.UnsupportedAppUsage; 8 import android.content.Context; 9 import android.provider.Settings; 10 import android.provider.Settings.Global; 11 import android.util.Log; 12 import android.util.proto.ProtoOutputStream; 13 14 import com.android.internal.annotations.VisibleForTesting; 15 16 import java.util.ArrayList; 17 import java.util.Arrays; 18 19 /** 20 * Describes the source of some work that may be done by someone else. 21 * Currently the public representation of what a work source is is not 22 * defined; this is an opaque container. 23 */ 24 public class WorkSource implements Parcelable { 25 static final String TAG = "WorkSource"; 26 static final boolean DEBUG = false; 27 28 @UnsupportedAppUsage 29 int mNum; 30 @UnsupportedAppUsage 31 int[] mUids; 32 @UnsupportedAppUsage 33 String[] mNames; 34 35 private ArrayList<WorkChain> mChains; 36 37 /** 38 * Internal statics to avoid object allocations in some operations. 39 * The WorkSource object itself is not thread safe, but we need to 40 * hold sTmpWorkSource lock while working with these statics. 41 */ 42 @UnsupportedAppUsage(maxTargetSdk = Build.VERSION_CODES.P) 43 static final WorkSource sTmpWorkSource = new WorkSource(0); 44 /** 45 * For returning newbie work from a modification operation. 46 */ 47 @UnsupportedAppUsage(maxTargetSdk = Build.VERSION_CODES.P) 48 static WorkSource sNewbWork; 49 /** 50 * For returning gone work form a modification operation. 51 */ 52 @UnsupportedAppUsage(maxTargetSdk = Build.VERSION_CODES.P) 53 static WorkSource sGoneWork; 54 55 /** 56 * Create an empty work source. 57 */ WorkSource()58 public WorkSource() { 59 mNum = 0; 60 mChains = null; 61 } 62 63 /** 64 * Create a new WorkSource that is a copy of an existing one. 65 * If <var>orig</var> is null, an empty WorkSource is created. 66 */ WorkSource(WorkSource orig)67 public WorkSource(WorkSource orig) { 68 if (orig == null) { 69 mNum = 0; 70 mChains = null; 71 return; 72 } 73 mNum = orig.mNum; 74 if (orig.mUids != null) { 75 mUids = orig.mUids.clone(); 76 mNames = orig.mNames != null ? orig.mNames.clone() : null; 77 } else { 78 mUids = null; 79 mNames = null; 80 } 81 82 if (orig.mChains != null) { 83 // Make a copy of all WorkChains that exist on |orig| since they are mutable. 84 mChains = new ArrayList<>(orig.mChains.size()); 85 for (WorkChain chain : orig.mChains) { 86 mChains.add(new WorkChain(chain)); 87 } 88 } else { 89 mChains = null; 90 } 91 } 92 93 /** @hide */ 94 @UnsupportedAppUsage 95 @TestApi WorkSource(int uid)96 public WorkSource(int uid) { 97 mNum = 1; 98 mUids = new int[] { uid, 0 }; 99 mNames = null; 100 mChains = null; 101 } 102 103 /** @hide */ WorkSource(int uid, String name)104 public WorkSource(int uid, String name) { 105 if (name == null) { 106 throw new NullPointerException("Name can't be null"); 107 } 108 mNum = 1; 109 mUids = new int[] { uid, 0 }; 110 mNames = new String[] { name, null }; 111 mChains = null; 112 } 113 114 @UnsupportedAppUsage WorkSource(Parcel in)115 WorkSource(Parcel in) { 116 mNum = in.readInt(); 117 mUids = in.createIntArray(); 118 mNames = in.createStringArray(); 119 120 int numChains = in.readInt(); 121 if (numChains > 0) { 122 mChains = new ArrayList<>(numChains); 123 in.readParcelableList(mChains, WorkChain.class.getClassLoader()); 124 } else { 125 mChains = null; 126 } 127 } 128 129 /** 130 * Whether system services should create {@code WorkChains} (wherever possible) in the place 131 * of flat UID lists. 132 * 133 * @hide 134 */ isChainedBatteryAttributionEnabled(Context context)135 public static boolean isChainedBatteryAttributionEnabled(Context context) { 136 return Settings.Global.getInt(context.getContentResolver(), 137 Global.CHAINED_BATTERY_ATTRIBUTION_ENABLED, 0) == 1; 138 } 139 140 /** @hide */ 141 @UnsupportedAppUsage 142 @TestApi size()143 public int size() { 144 return mNum; 145 } 146 147 /** @hide */ 148 @UnsupportedAppUsage 149 @TestApi get(int index)150 public int get(int index) { 151 return mUids[index]; 152 } 153 154 /** 155 * Return the UID to which this WorkSource should be attributed to, i.e, the UID that 156 * initiated the work and not the UID performing it. If the WorkSource has no UIDs, returns -1 157 * instead. 158 * 159 * @hide 160 */ getAttributionUid()161 public int getAttributionUid() { 162 if (isEmpty()) { 163 return -1; 164 } 165 166 return mNum > 0 ? mUids[0] : mChains.get(0).getAttributionUid(); 167 } 168 169 /** @hide */ 170 @UnsupportedAppUsage 171 @TestApi getName(int index)172 public String getName(int index) { 173 return mNames != null ? mNames[index] : null; 174 } 175 176 /** 177 * Clear names from this WorkSource. Uids are left intact. WorkChains if any, are left 178 * intact. 179 * 180 * <p>Useful when combining with another WorkSource that doesn't have names. 181 * @hide 182 */ clearNames()183 public void clearNames() { 184 if (mNames != null) { 185 mNames = null; 186 // Clear out any duplicate uids now that we don't have names to disambiguate them. 187 int destIndex = 1; 188 int newNum = mNum; 189 for (int sourceIndex = 1; sourceIndex < mNum; sourceIndex++) { 190 if (mUids[sourceIndex] == mUids[sourceIndex - 1]) { 191 newNum--; 192 } else { 193 mUids[destIndex] = mUids[sourceIndex]; 194 destIndex++; 195 } 196 } 197 mNum = newNum; 198 } 199 } 200 201 /** 202 * Clear this WorkSource to be empty. 203 */ clear()204 public void clear() { 205 mNum = 0; 206 if (mChains != null) { 207 mChains.clear(); 208 } 209 } 210 211 @Override equals(@ullable Object o)212 public boolean equals(@Nullable Object o) { 213 if (o instanceof WorkSource) { 214 WorkSource other = (WorkSource) o; 215 216 if (diff(other)) { 217 return false; 218 } 219 220 if (mChains != null && !mChains.isEmpty()) { 221 return mChains.equals(other.mChains); 222 } else { 223 return other.mChains == null || other.mChains.isEmpty(); 224 } 225 } 226 227 return false; 228 } 229 230 @Override hashCode()231 public int hashCode() { 232 int result = 0; 233 for (int i = 0; i < mNum; i++) { 234 result = ((result << 4) | (result >>> 28)) ^ mUids[i]; 235 } 236 if (mNames != null) { 237 for (int i = 0; i < mNum; i++) { 238 result = ((result << 4) | (result >>> 28)) ^ mNames[i].hashCode(); 239 } 240 } 241 242 if (mChains != null) { 243 result = ((result << 4) | (result >>> 28)) ^ mChains.hashCode(); 244 } 245 246 return result; 247 } 248 249 /** 250 * Compare this WorkSource with another. 251 * @param other The WorkSource to compare against. 252 * @return If there is a difference, true is returned. 253 */ 254 // TODO: This is a public API so it cannot be renamed. Because it is used in several places, 255 // we keep its semantics the same and ignore any differences in WorkChains (if any). diff(WorkSource other)256 public boolean diff(WorkSource other) { 257 int N = mNum; 258 if (N != other.mNum) { 259 return true; 260 } 261 final int[] uids1 = mUids; 262 final int[] uids2 = other.mUids; 263 final String[] names1 = mNames; 264 final String[] names2 = other.mNames; 265 for (int i=0; i<N; i++) { 266 if (uids1[i] != uids2[i]) { 267 return true; 268 } 269 if (names1 != null && names2 != null && !names1[i].equals(names2[i])) { 270 return true; 271 } 272 } 273 return false; 274 } 275 276 /** 277 * Replace the current contents of this work source with the given 278 * work source. If {@code other} is null, the current work source 279 * will be made empty. 280 */ set(WorkSource other)281 public void set(WorkSource other) { 282 if (other == null) { 283 mNum = 0; 284 if (mChains != null) { 285 mChains.clear(); 286 } 287 return; 288 } 289 mNum = other.mNum; 290 if (other.mUids != null) { 291 if (mUids != null && mUids.length >= mNum) { 292 System.arraycopy(other.mUids, 0, mUids, 0, mNum); 293 } else { 294 mUids = other.mUids.clone(); 295 } 296 if (other.mNames != null) { 297 if (mNames != null && mNames.length >= mNum) { 298 System.arraycopy(other.mNames, 0, mNames, 0, mNum); 299 } else { 300 mNames = other.mNames.clone(); 301 } 302 } else { 303 mNames = null; 304 } 305 } else { 306 mUids = null; 307 mNames = null; 308 } 309 310 if (other.mChains != null) { 311 if (mChains != null) { 312 mChains.clear(); 313 } else { 314 mChains = new ArrayList<>(other.mChains.size()); 315 } 316 317 for (WorkChain chain : other.mChains) { 318 mChains.add(new WorkChain(chain)); 319 } 320 } 321 } 322 323 /** @hide */ set(int uid)324 public void set(int uid) { 325 mNum = 1; 326 if (mUids == null) mUids = new int[2]; 327 mUids[0] = uid; 328 mNames = null; 329 if (mChains != null) { 330 mChains.clear(); 331 } 332 } 333 334 /** @hide */ set(int uid, String name)335 public void set(int uid, String name) { 336 if (name == null) { 337 throw new NullPointerException("Name can't be null"); 338 } 339 mNum = 1; 340 if (mUids == null) { 341 mUids = new int[2]; 342 mNames = new String[2]; 343 } 344 mUids[0] = uid; 345 mNames[0] = name; 346 if (mChains != null) { 347 mChains.clear(); 348 } 349 } 350 351 /** 352 * Legacy API, DO NOT USE: Only deals with flat UIDs and tags. No chains are transferred, and no 353 * differences in chains are returned. This will be removed once its callers have been 354 * rewritten. 355 * 356 * NOTE: This is currently only used in GnssLocationProvider. 357 * 358 * @hide 359 * @deprecated for internal use only. WorkSources are opaque and no external callers should need 360 * to be aware of internal differences. 361 */ 362 @Deprecated 363 @TestApi setReturningDiffs(WorkSource other)364 public WorkSource[] setReturningDiffs(WorkSource other) { 365 synchronized (sTmpWorkSource) { 366 sNewbWork = null; 367 sGoneWork = null; 368 updateLocked(other, true, true); 369 if (sNewbWork != null || sGoneWork != null) { 370 WorkSource[] diffs = new WorkSource[2]; 371 diffs[0] = sNewbWork; 372 diffs[1] = sGoneWork; 373 return diffs; 374 } 375 return null; 376 } 377 } 378 379 /** 380 * Merge the contents of <var>other</var> WorkSource in to this one. 381 * 382 * @param other The other WorkSource whose contents are to be merged. 383 * @return Returns true if any new sources were added. 384 */ add(WorkSource other)385 public boolean add(WorkSource other) { 386 synchronized (sTmpWorkSource) { 387 boolean uidAdded = updateLocked(other, false, false); 388 389 boolean chainAdded = false; 390 if (other.mChains != null) { 391 // NOTE: This is quite an expensive operation, especially if the number of chains 392 // is large. We could look into optimizing it if it proves problematic. 393 if (mChains == null) { 394 mChains = new ArrayList<>(other.mChains.size()); 395 } 396 397 for (WorkChain wc : other.mChains) { 398 if (!mChains.contains(wc)) { 399 mChains.add(new WorkChain(wc)); 400 } 401 } 402 } 403 404 return uidAdded || chainAdded; 405 } 406 } 407 408 /** 409 * Legacy API: DO NOT USE. Only in use from unit tests. 410 * 411 * @hide 412 * @deprecated meant for unit testing use only. Will be removed in a future API revision. 413 */ 414 @Deprecated 415 @TestApi addReturningNewbs(WorkSource other)416 public WorkSource addReturningNewbs(WorkSource other) { 417 synchronized (sTmpWorkSource) { 418 sNewbWork = null; 419 updateLocked(other, false, true); 420 return sNewbWork; 421 } 422 } 423 424 /** @hide */ 425 @UnsupportedAppUsage 426 @TestApi add(int uid)427 public boolean add(int uid) { 428 if (mNum <= 0) { 429 mNames = null; 430 insert(0, uid); 431 return true; 432 } 433 if (mNames != null) { 434 throw new IllegalArgumentException("Adding without name to named " + this); 435 } 436 int i = Arrays.binarySearch(mUids, 0, mNum, uid); 437 if (DEBUG) Log.d(TAG, "Adding uid " + uid + " to " + this + ": binsearch res = " + i); 438 if (i >= 0) { 439 return false; 440 } 441 insert(-i-1, uid); 442 return true; 443 } 444 445 /** @hide */ 446 @UnsupportedAppUsage 447 @TestApi add(int uid, String name)448 public boolean add(int uid, String name) { 449 if (mNum <= 0) { 450 insert(0, uid, name); 451 return true; 452 } 453 if (mNames == null) { 454 throw new IllegalArgumentException("Adding name to unnamed " + this); 455 } 456 int i; 457 for (i=0; i<mNum; i++) { 458 if (mUids[i] > uid) { 459 break; 460 } 461 if (mUids[i] == uid) { 462 int diff = mNames[i].compareTo(name); 463 if (diff > 0) { 464 break; 465 } 466 if (diff == 0) { 467 return false; 468 } 469 } 470 } 471 insert(i, uid, name); 472 return true; 473 } 474 remove(WorkSource other)475 public boolean remove(WorkSource other) { 476 if (isEmpty() || other.isEmpty()) { 477 return false; 478 } 479 480 boolean uidRemoved; 481 if (mNames == null && other.mNames == null) { 482 uidRemoved = removeUids(other); 483 } else { 484 if (mNames == null) { 485 throw new IllegalArgumentException("Other " + other + " has names, but target " 486 + this + " does not"); 487 } 488 if (other.mNames == null) { 489 throw new IllegalArgumentException("Target " + this + " has names, but other " 490 + other + " does not"); 491 } 492 uidRemoved = removeUidsAndNames(other); 493 } 494 495 boolean chainRemoved = false; 496 if (other.mChains != null && mChains != null) { 497 chainRemoved = mChains.removeAll(other.mChains); 498 } 499 500 return uidRemoved || chainRemoved; 501 } 502 503 /** 504 * Create a new {@code WorkChain} associated with this WorkSource and return it. 505 * 506 * @hide 507 */ 508 @SystemApi createWorkChain()509 public WorkChain createWorkChain() { 510 if (mChains == null) { 511 mChains = new ArrayList<>(4); 512 } 513 514 final WorkChain wc = new WorkChain(); 515 mChains.add(wc); 516 517 return wc; 518 } 519 520 /** 521 * Returns {@code true} iff. this work source contains zero UIDs and zero WorkChains to 522 * attribute usage to. 523 * 524 * @hide for internal use only. 525 */ isEmpty()526 public boolean isEmpty() { 527 return mNum == 0 && (mChains == null || mChains.isEmpty()); 528 } 529 530 /** 531 * @return the list of {@code WorkChains} associated with this {@code WorkSource}. 532 * @hide 533 */ getWorkChains()534 public ArrayList<WorkChain> getWorkChains() { 535 return mChains; 536 } 537 538 /** 539 * DO NOT USE: Hacky API provided solely for {@code GnssLocationProvider}. See 540 * {@code setReturningDiffs} as well. 541 * 542 * @hide 543 */ transferWorkChains(WorkSource other)544 public void transferWorkChains(WorkSource other) { 545 if (mChains != null) { 546 mChains.clear(); 547 } 548 549 if (other.mChains == null || other.mChains.isEmpty()) { 550 return; 551 } 552 553 if (mChains == null) { 554 mChains = new ArrayList<>(4); 555 } 556 557 mChains.addAll(other.mChains); 558 other.mChains.clear(); 559 } 560 removeUids(WorkSource other)561 private boolean removeUids(WorkSource other) { 562 int N1 = mNum; 563 final int[] uids1 = mUids; 564 final int N2 = other.mNum; 565 final int[] uids2 = other.mUids; 566 boolean changed = false; 567 int i1 = 0, i2 = 0; 568 if (DEBUG) Log.d(TAG, "Remove " + other + " from " + this); 569 while (i1 < N1 && i2 < N2) { 570 if (DEBUG) Log.d(TAG, "Step: target @ " + i1 + " of " + N1 + ", other @ " + i2 571 + " of " + N2); 572 if (uids2[i2] == uids1[i1]) { 573 if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 574 + ": remove " + uids1[i1]); 575 N1--; 576 changed = true; 577 if (i1 < N1) System.arraycopy(uids1, i1+1, uids1, i1, N1-i1); 578 i2++; 579 } else if (uids2[i2] > uids1[i1]) { 580 if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip i1"); 581 i1++; 582 } else { 583 if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip i2"); 584 i2++; 585 } 586 } 587 588 mNum = N1; 589 590 return changed; 591 } 592 removeUidsAndNames(WorkSource other)593 private boolean removeUidsAndNames(WorkSource other) { 594 int N1 = mNum; 595 final int[] uids1 = mUids; 596 final String[] names1 = mNames; 597 final int N2 = other.mNum; 598 final int[] uids2 = other.mUids; 599 final String[] names2 = other.mNames; 600 boolean changed = false; 601 int i1 = 0, i2 = 0; 602 if (DEBUG) Log.d(TAG, "Remove " + other + " from " + this); 603 while (i1 < N1 && i2 < N2) { 604 if (DEBUG) Log.d(TAG, "Step: target @ " + i1 + " of " + N1 + ", other @ " + i2 605 + " of " + N2 + ": " + uids1[i1] + " " + names1[i1]); 606 if (uids2[i2] == uids1[i1] && names2[i2].equals(names1[i1])) { 607 if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 608 + ": remove " + uids1[i1] + " " + names1[i1]); 609 N1--; 610 changed = true; 611 if (i1 < N1) { 612 System.arraycopy(uids1, i1+1, uids1, i1, N1-i1); 613 System.arraycopy(names1, i1+1, names1, i1, N1-i1); 614 } 615 i2++; 616 } else if (uids2[i2] > uids1[i1] 617 || (uids2[i2] == uids1[i1] && names2[i2].compareTo(names1[i1]) > 0)) { 618 if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip i1"); 619 i1++; 620 } else { 621 if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip i2"); 622 i2++; 623 } 624 } 625 626 mNum = N1; 627 628 return changed; 629 } 630 631 @UnsupportedAppUsage(maxTargetSdk = Build.VERSION_CODES.P) updateLocked(WorkSource other, boolean set, boolean returnNewbs)632 private boolean updateLocked(WorkSource other, boolean set, boolean returnNewbs) { 633 if (mNames == null && other.mNames == null) { 634 return updateUidsLocked(other, set, returnNewbs); 635 } else { 636 if (mNum > 0 && mNames == null) { 637 throw new IllegalArgumentException("Other " + other + " has names, but target " 638 + this + " does not"); 639 } 640 if (other.mNum > 0 && other.mNames == null) { 641 throw new IllegalArgumentException("Target " + this + " has names, but other " 642 + other + " does not"); 643 } 644 return updateUidsAndNamesLocked(other, set, returnNewbs); 645 } 646 } 647 addWork(WorkSource cur, int newUid)648 private static WorkSource addWork(WorkSource cur, int newUid) { 649 if (cur == null) { 650 return new WorkSource(newUid); 651 } 652 cur.insert(cur.mNum, newUid); 653 return cur; 654 } 655 updateUidsLocked(WorkSource other, boolean set, boolean returnNewbs)656 private boolean updateUidsLocked(WorkSource other, boolean set, boolean returnNewbs) { 657 int N1 = mNum; 658 int[] uids1 = mUids; 659 final int N2 = other.mNum; 660 final int[] uids2 = other.mUids; 661 boolean changed = false; 662 int i1 = 0, i2 = 0; 663 if (DEBUG) Log.d(TAG, "Update " + this + " with " + other + " set=" + set 664 + " returnNewbs=" + returnNewbs); 665 while (i1 < N1 || i2 < N2) { 666 if (DEBUG) Log.d(TAG, "Step: target @ " + i1 + " of " + N1 + ", other @ " + i2 667 + " of " + N2); 668 if (i1 >= N1 || (i2 < N2 && uids2[i2] < uids1[i1])) { 669 // Need to insert a new uid. 670 if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 671 + ": insert " + uids2[i2]); 672 changed = true; 673 if (uids1 == null) { 674 uids1 = new int[4]; 675 uids1[0] = uids2[i2]; 676 } else if (N1 >= uids1.length) { 677 int[] newuids = new int[(uids1.length*3)/2]; 678 if (i1 > 0) System.arraycopy(uids1, 0, newuids, 0, i1); 679 if (i1 < N1) System.arraycopy(uids1, i1, newuids, i1+1, N1-i1); 680 uids1 = newuids; 681 uids1[i1] = uids2[i2]; 682 } else { 683 if (i1 < N1) System.arraycopy(uids1, i1, uids1, i1+1, N1-i1); 684 uids1[i1] = uids2[i2]; 685 } 686 if (returnNewbs) { 687 sNewbWork = addWork(sNewbWork, uids2[i2]); 688 } 689 N1++; 690 i1++; 691 i2++; 692 } else { 693 if (!set) { 694 // Skip uids that already exist or are not in 'other'. 695 if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip"); 696 if (i2 < N2 && uids2[i2] == uids1[i1]) { 697 i2++; 698 } 699 i1++; 700 } else { 701 // Remove any uids that don't exist in 'other'. 702 int start = i1; 703 while (i1 < N1 && (i2 >= N2 || uids2[i2] > uids1[i1])) { 704 if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + ": remove " + uids1[i1]); 705 sGoneWork = addWork(sGoneWork, uids1[i1]); 706 i1++; 707 } 708 if (start < i1) { 709 System.arraycopy(uids1, i1, uids1, start, N1-i1); 710 N1 -= i1-start; 711 i1 = start; 712 } 713 // If there is a matching uid, skip it. 714 if (i1 < N1 && i2 < N2 && uids2[i2] == uids1[i1]) { 715 if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + N1 + ": skip"); 716 i1++; 717 i2++; 718 } 719 } 720 } 721 } 722 723 mNum = N1; 724 mUids = uids1; 725 726 return changed; 727 } 728 729 /** 730 * Returns 0 if equal, negative if 'this' is before 'other', positive if 'this' is after 'other'. 731 */ compare(WorkSource other, int i1, int i2)732 private int compare(WorkSource other, int i1, int i2) { 733 final int diff = mUids[i1] - other.mUids[i2]; 734 if (diff != 0) { 735 return diff; 736 } 737 return mNames[i1].compareTo(other.mNames[i2]); 738 } 739 addWork(WorkSource cur, int newUid, String newName)740 private static WorkSource addWork(WorkSource cur, int newUid, String newName) { 741 if (cur == null) { 742 return new WorkSource(newUid, newName); 743 } 744 cur.insert(cur.mNum, newUid, newName); 745 return cur; 746 } 747 updateUidsAndNamesLocked(WorkSource other, boolean set, boolean returnNewbs)748 private boolean updateUidsAndNamesLocked(WorkSource other, boolean set, boolean returnNewbs) { 749 final int N2 = other.mNum; 750 final int[] uids2 = other.mUids; 751 String[] names2 = other.mNames; 752 boolean changed = false; 753 int i1 = 0, i2 = 0; 754 if (DEBUG) Log.d(TAG, "Update " + this + " with " + other + " set=" + set 755 + " returnNewbs=" + returnNewbs); 756 while (i1 < mNum || i2 < N2) { 757 if (DEBUG) Log.d(TAG, "Step: target @ " + i1 + " of " + mNum + ", other @ " + i2 758 + " of " + N2); 759 int diff = -1; 760 if (i1 >= mNum || (i2 < N2 && (diff=compare(other, i1, i2)) > 0)) { 761 // Need to insert a new uid. 762 changed = true; 763 if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + mNum 764 + ": insert " + uids2[i2] + " " + names2[i2]); 765 insert(i1, uids2[i2], names2[i2]); 766 if (returnNewbs) { 767 sNewbWork = addWork(sNewbWork, uids2[i2], names2[i2]); 768 } 769 i1++; 770 i2++; 771 } else { 772 if (!set) { 773 if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + mNum + ": skip"); 774 if (i2 < N2 && diff == 0) { 775 i2++; 776 } 777 i1++; 778 } else { 779 // Remove any uids that don't exist in 'other'. 780 int start = i1; 781 while (diff < 0) { 782 if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + ": remove " + mUids[i1] 783 + " " + mNames[i1]); 784 sGoneWork = addWork(sGoneWork, mUids[i1], mNames[i1]); 785 i1++; 786 if (i1 >= mNum) { 787 break; 788 } 789 diff = i2 < N2 ? compare(other, i1, i2) : -1; 790 } 791 if (start < i1) { 792 System.arraycopy(mUids, i1, mUids, start, mNum-i1); 793 System.arraycopy(mNames, i1, mNames, start, mNum-i1); 794 mNum -= i1-start; 795 i1 = start; 796 } 797 // If there is a matching uid, skip it. 798 if (i1 < mNum && diff == 0) { 799 if (DEBUG) Log.d(TAG, "i1=" + i1 + " i2=" + i2 + " N1=" + mNum + ": skip"); 800 i1++; 801 i2++; 802 } 803 } 804 } 805 } 806 807 return changed; 808 } 809 810 private void insert(int index, int uid) { 811 if (DEBUG) Log.d(TAG, "Insert in " + this + " @ " + index + " uid " + uid); 812 if (mUids == null) { 813 mUids = new int[4]; 814 mUids[0] = uid; 815 mNum = 1; 816 } else if (mNum >= mUids.length) { 817 int[] newuids = new int[(mNum*3)/2]; 818 if (index > 0) { 819 System.arraycopy(mUids, 0, newuids, 0, index); 820 } 821 if (index < mNum) { 822 System.arraycopy(mUids, index, newuids, index+1, mNum-index); 823 } 824 mUids = newuids; 825 mUids[index] = uid; 826 mNum++; 827 } else { 828 if (index < mNum) { 829 System.arraycopy(mUids, index, mUids, index+1, mNum-index); 830 } 831 mUids[index] = uid; 832 mNum++; 833 } 834 } 835 836 private void insert(int index, int uid, String name) { 837 if (mUids == null) { 838 mUids = new int[4]; 839 mUids[0] = uid; 840 mNames = new String[4]; 841 mNames[0] = name; 842 mNum = 1; 843 } else if (mNum >= mUids.length) { 844 int[] newuids = new int[(mNum*3)/2]; 845 String[] newnames = new String[(mNum*3)/2]; 846 if (index > 0) { 847 System.arraycopy(mUids, 0, newuids, 0, index); 848 System.arraycopy(mNames, 0, newnames, 0, index); 849 } 850 if (index < mNum) { 851 System.arraycopy(mUids, index, newuids, index+1, mNum-index); 852 System.arraycopy(mNames, index, newnames, index+1, mNum-index); 853 } 854 mUids = newuids; 855 mNames = newnames; 856 mUids[index] = uid; 857 mNames[index] = name; 858 mNum++; 859 } else { 860 if (index < mNum) { 861 System.arraycopy(mUids, index, mUids, index+1, mNum-index); 862 System.arraycopy(mNames, index, mNames, index+1, mNum-index); 863 } 864 mUids[index] = uid; 865 mNames[index] = name; 866 mNum++; 867 } 868 } 869 870 /** 871 * Represents an attribution chain for an item of work being performed. An attribution chain is 872 * an indexed list of {code (uid, tag)} nodes. The node at {@code index == 0} is the initiator 873 * of the work, and the node at the highest index performs the work. Nodes at other indices 874 * are intermediaries that facilitate the work. Examples : 875 * 876 * (1) Work being performed by uid=2456 (no chaining): 877 * <pre> 878 * WorkChain { 879 * mUids = { 2456 } 880 * mTags = { null } 881 * mSize = 1; 882 * } 883 * </pre> 884 * 885 * (2) Work being performed by uid=2456 (from component "c1") on behalf of uid=5678: 886 * 887 * <pre> 888 * WorkChain { 889 * mUids = { 5678, 2456 } 890 * mTags = { null, "c1" } 891 * mSize = 1 892 * } 893 * </pre> 894 * 895 * Attribution chains are mutable, though the only operation that can be performed on them 896 * is the addition of a new node at the end of the attribution chain to represent 897 * 898 * @hide 899 */ 900 @SystemApi 901 public static final class WorkChain implements Parcelable { 902 private int mSize; 903 private int[] mUids; 904 private String[] mTags; 905 906 // @VisibleForTesting 907 public WorkChain() { 908 mSize = 0; 909 mUids = new int[4]; 910 mTags = new String[4]; 911 } 912 913 /** @hide */ 914 @VisibleForTesting 915 public WorkChain(WorkChain other) { 916 mSize = other.mSize; 917 mUids = other.mUids.clone(); 918 mTags = other.mTags.clone(); 919 } 920 921 private WorkChain(Parcel in) { 922 mSize = in.readInt(); 923 mUids = in.createIntArray(); 924 mTags = in.createStringArray(); 925 } 926 927 /** 928 * Append a node whose uid is {@code uid} and whose optional tag is {@code tag} to this 929 * {@code WorkChain}. 930 */ 931 public WorkChain addNode(int uid, @Nullable String tag) { 932 if (mSize == mUids.length) { 933 resizeArrays(); 934 } 935 936 mUids[mSize] = uid; 937 mTags[mSize] = tag; 938 mSize++; 939 940 return this; 941 } 942 943 /** 944 * Return the UID to which this WorkChain should be attributed to, i.e, the UID that 945 * initiated the work and not the UID performing it. Returns -1 if the chain is empty. 946 */ 947 public int getAttributionUid() { 948 return mSize > 0 ? mUids[0] : -1; 949 } 950 951 /** 952 * Return the tag associated with the attribution UID. See (@link #getAttributionUid}. 953 * Returns null if the chain is empty. 954 */ 955 public String getAttributionTag() { 956 return mTags.length > 0 ? mTags[0] : null; 957 } 958 959 // TODO: The following three trivial getters are purely for testing and will be removed 960 // once we have higher level logic in place, e.g for serializing this WorkChain to a proto, 961 // diffing it etc. 962 963 964 /** @hide */ 965 @VisibleForTesting 966 public int[] getUids() { 967 int[] uids = new int[mSize]; 968 System.arraycopy(mUids, 0, uids, 0, mSize); 969 return uids; 970 } 971 972 /** @hide */ 973 @VisibleForTesting 974 public String[] getTags() { 975 String[] tags = new String[mSize]; 976 System.arraycopy(mTags, 0, tags, 0, mSize); 977 return tags; 978 } 979 980 /** @hide */ 981 @VisibleForTesting 982 public int getSize() { 983 return mSize; 984 } 985 986 private void resizeArrays() { 987 final int newSize = mSize * 2; 988 int[] uids = new int[newSize]; 989 String[] tags = new String[newSize]; 990 991 System.arraycopy(mUids, 0, uids, 0, mSize); 992 System.arraycopy(mTags, 0, tags, 0, mSize); 993 994 mUids = uids; 995 mTags = tags; 996 } 997 998 @NonNull 999 @Override 1000 public String toString() { 1001 StringBuilder result = new StringBuilder("WorkChain{"); 1002 for (int i = 0; i < mSize; ++i) { 1003 if (i != 0) { 1004 result.append(", "); 1005 } 1006 result.append("("); 1007 result.append(mUids[i]); 1008 if (mTags[i] != null) { 1009 result.append(", "); 1010 result.append(mTags[i]); 1011 } 1012 result.append(")"); 1013 } 1014 1015 result.append("}"); 1016 return result.toString(); 1017 } 1018 1019 @Override 1020 public int hashCode() { 1021 return (mSize + 31 * Arrays.hashCode(mUids)) * 31 + Arrays.hashCode(mTags); 1022 } 1023 1024 @Override 1025 public boolean equals(@Nullable Object o) { 1026 if (o instanceof WorkChain) { 1027 WorkChain other = (WorkChain) o; 1028 1029 return mSize == other.mSize 1030 && Arrays.equals(mUids, other.mUids) 1031 && Arrays.equals(mTags, other.mTags); 1032 } 1033 1034 return false; 1035 } 1036 1037 @Override 1038 public int describeContents() { 1039 return 0; 1040 } 1041 1042 @Override 1043 public void writeToParcel(Parcel dest, int flags) { 1044 dest.writeInt(mSize); 1045 dest.writeIntArray(mUids); 1046 dest.writeStringArray(mTags); 1047 } 1048 1049 public static final @android.annotation.NonNull Parcelable.Creator<WorkChain> CREATOR = 1050 new Parcelable.Creator<WorkChain>() { 1051 public WorkChain createFromParcel(Parcel in) { 1052 return new WorkChain(in); 1053 } 1054 public WorkChain[] newArray(int size) { 1055 return new WorkChain[size]; 1056 } 1057 }; 1058 } 1059 1060 /** 1061 * Computes the differences in WorkChains contained between {@code oldWs} and {@code newWs}. 1062 * 1063 * Returns {@code null} if no differences exist, otherwise returns a two element array. The 1064 * first element is a list of "new" chains, i.e WorkChains present in {@code newWs} but not in 1065 * {@code oldWs}. The second element is a list of "gone" chains, i.e WorkChains present in 1066 * {@code oldWs} but not in {@code newWs}. 1067 * 1068 * @hide 1069 */ 1070 public static ArrayList<WorkChain>[] diffChains(WorkSource oldWs, WorkSource newWs) { 1071 ArrayList<WorkChain> newChains = null; 1072 ArrayList<WorkChain> goneChains = null; 1073 1074 // TODO(narayan): This is a dumb O(M*N) algorithm that determines what has changed across 1075 // WorkSource objects. We can replace this with something smarter, for e.g by defining 1076 // a Comparator between WorkChains. It's unclear whether that will be more efficient if 1077 // the number of chains associated with a WorkSource is expected to be small 1078 if (oldWs.mChains != null) { 1079 for (int i = 0; i < oldWs.mChains.size(); ++i) { 1080 final WorkChain wc = oldWs.mChains.get(i); 1081 if (newWs.mChains == null || !newWs.mChains.contains(wc)) { 1082 if (goneChains == null) { 1083 goneChains = new ArrayList<>(oldWs.mChains.size()); 1084 } 1085 goneChains.add(wc); 1086 } 1087 } 1088 } 1089 1090 if (newWs.mChains != null) { 1091 for (int i = 0; i < newWs.mChains.size(); ++i) { 1092 final WorkChain wc = newWs.mChains.get(i); 1093 if (oldWs.mChains == null || !oldWs.mChains.contains(wc)) { 1094 if (newChains == null) { 1095 newChains = new ArrayList<>(newWs.mChains.size()); 1096 } 1097 newChains.add(wc); 1098 } 1099 } 1100 } 1101 1102 if (newChains != null || goneChains != null) { 1103 return new ArrayList[] { newChains, goneChains }; 1104 } 1105 1106 return null; 1107 } 1108 1109 @Override 1110 public int describeContents() { 1111 return 0; 1112 } 1113 1114 @Override 1115 public void writeToParcel(Parcel dest, int flags) { 1116 dest.writeInt(mNum); 1117 dest.writeIntArray(mUids); 1118 dest.writeStringArray(mNames); 1119 1120 if (mChains == null) { 1121 dest.writeInt(-1); 1122 } else { 1123 dest.writeInt(mChains.size()); 1124 dest.writeParcelableList(mChains, flags); 1125 } 1126 } 1127 1128 @Override 1129 public String toString() { 1130 StringBuilder result = new StringBuilder(); 1131 result.append("WorkSource{"); 1132 for (int i = 0; i < mNum; i++) { 1133 if (i != 0) { 1134 result.append(", "); 1135 } 1136 result.append(mUids[i]); 1137 if (mNames != null) { 1138 result.append(" "); 1139 result.append(mNames[i]); 1140 } 1141 } 1142 1143 if (mChains != null) { 1144 result.append(" chains="); 1145 for (int i = 0; i < mChains.size(); ++i) { 1146 if (i != 0) { 1147 result.append(", "); 1148 } 1149 result.append(mChains.get(i)); 1150 } 1151 } 1152 1153 result.append("}"); 1154 return result.toString(); 1155 } 1156 1157 /** @hide */ 1158 public void writeToProto(ProtoOutputStream proto, long fieldId) { 1159 final long workSourceToken = proto.start(fieldId); 1160 for (int i = 0; i < mNum; i++) { 1161 final long contentProto = proto.start(WorkSourceProto.WORK_SOURCE_CONTENTS); 1162 proto.write(WorkSourceProto.WorkSourceContentProto.UID, mUids[i]); 1163 if (mNames != null) { 1164 proto.write(WorkSourceProto.WorkSourceContentProto.NAME, mNames[i]); 1165 } 1166 proto.end(contentProto); 1167 } 1168 1169 if (mChains != null) { 1170 for (int i = 0; i < mChains.size(); i++) { 1171 final WorkChain wc = mChains.get(i); 1172 final long workChain = proto.start(WorkSourceProto.WORK_CHAINS); 1173 1174 final String[] tags = wc.getTags(); 1175 final int[] uids = wc.getUids(); 1176 for (int j = 0; j < tags.length; j++) { 1177 final long contentProto = proto.start(WorkSourceProto.WORK_SOURCE_CONTENTS); 1178 proto.write(WorkSourceProto.WorkSourceContentProto.UID, uids[j]); 1179 proto.write(WorkSourceProto.WorkSourceContentProto.NAME, tags[j]); 1180 proto.end(contentProto); 1181 } 1182 1183 proto.end(workChain); 1184 } 1185 } 1186 1187 proto.end(workSourceToken); 1188 } 1189 1190 public static final @android.annotation.NonNull Parcelable.Creator<WorkSource> CREATOR 1191 = new Parcelable.Creator<WorkSource>() { 1192 public WorkSource createFromParcel(Parcel in) { 1193 return new WorkSource(in); 1194 } 1195 public WorkSource[] newArray(int size) { 1196 return new WorkSource[size]; 1197 } 1198 }; 1199 } 1200