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