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