1/* 2 * Copyright (C) 2015 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 18package com.android.internal.app; 19 20import android.app.usage.UsageStats; 21import android.app.usage.UsageStatsManager; 22import android.content.ComponentName; 23import android.content.Context; 24import android.content.Intent; 25import android.content.IntentFilter; 26import android.content.pm.ApplicationInfo; 27import android.content.pm.ComponentInfo; 28import android.content.pm.PackageManager; 29import android.content.pm.PackageManager.NameNotFoundException; 30import android.content.pm.ResolveInfo; 31import android.content.SharedPreferences; 32import android.content.ServiceConnection; 33import android.metrics.LogMaker; 34import android.os.Environment; 35import android.os.Handler; 36import android.os.IBinder; 37import android.os.Looper; 38import android.os.Message; 39import android.os.RemoteException; 40import android.os.storage.StorageManager; 41import android.os.UserHandle; 42import android.service.resolver.IResolverRankerService; 43import android.service.resolver.IResolverRankerResult; 44import android.service.resolver.ResolverRankerService; 45import android.service.resolver.ResolverTarget; 46import android.text.TextUtils; 47import android.util.ArrayMap; 48import android.util.Log; 49import com.android.internal.app.ResolverActivity.ResolvedComponentInfo; 50import com.android.internal.logging.MetricsLogger; 51import com.android.internal.logging.nano.MetricsProto.MetricsEvent; 52 53import java.io.File; 54import java.lang.InterruptedException; 55import java.text.Collator; 56import java.util.ArrayList; 57import java.util.Comparator; 58import java.util.concurrent.CountDownLatch; 59import java.util.concurrent.TimeUnit; 60import java.util.LinkedHashMap; 61import java.util.List; 62import java.util.Map; 63 64/** 65 * Ranks and compares packages based on usage stats. 66 */ 67class ResolverComparator implements Comparator<ResolvedComponentInfo> { 68 private static final String TAG = "ResolverComparator"; 69 70 private static final boolean DEBUG = false; 71 72 private static final int NUM_OF_TOP_ANNOTATIONS_TO_USE = 3; 73 74 // One week 75 private static final long USAGE_STATS_PERIOD = 1000 * 60 * 60 * 24 * 7; 76 77 private static final long RECENCY_TIME_PERIOD = 1000 * 60 * 60 * 12; 78 79 private static final float RECENCY_MULTIPLIER = 2.f; 80 81 // message types 82 private static final int RESOLVER_RANKER_SERVICE_RESULT = 0; 83 private static final int RESOLVER_RANKER_RESULT_TIMEOUT = 1; 84 85 // timeout for establishing connections with a ResolverRankerService. 86 private static final int CONNECTION_COST_TIMEOUT_MILLIS = 200; 87 // timeout for establishing connections with a ResolverRankerService, collecting features and 88 // predicting ranking scores. 89 private static final int WATCHDOG_TIMEOUT_MILLIS = 500; 90 91 private final Collator mCollator; 92 private final boolean mHttp; 93 private final PackageManager mPm; 94 private final UsageStatsManager mUsm; 95 private final Map<String, UsageStats> mStats; 96 private final long mCurrentTime; 97 private final long mSinceTime; 98 private final LinkedHashMap<ComponentName, ResolverTarget> mTargetsDict = new LinkedHashMap<>(); 99 private final String mReferrerPackage; 100 private final Object mLock = new Object(); 101 private ArrayList<ResolverTarget> mTargets; 102 private String mContentType; 103 private String[] mAnnotations; 104 private String mAction; 105 private ComponentName mResolvedRankerName; 106 private ComponentName mRankerServiceName; 107 private IResolverRankerService mRanker; 108 private ResolverRankerServiceConnection mConnection; 109 private AfterCompute mAfterCompute; 110 private Context mContext; 111 private CountDownLatch mConnectSignal; 112 113 private final Handler mHandler = new Handler(Looper.getMainLooper()) { 114 public void handleMessage(Message msg) { 115 switch (msg.what) { 116 case RESOLVER_RANKER_SERVICE_RESULT: 117 if (DEBUG) { 118 Log.d(TAG, "RESOLVER_RANKER_SERVICE_RESULT"); 119 } 120 if (mHandler.hasMessages(RESOLVER_RANKER_RESULT_TIMEOUT)) { 121 if (msg.obj != null) { 122 final List<ResolverTarget> receivedTargets = 123 (List<ResolverTarget>) msg.obj; 124 if (receivedTargets != null && mTargets != null 125 && receivedTargets.size() == mTargets.size()) { 126 final int size = mTargets.size(); 127 boolean isUpdated = false; 128 for (int i = 0; i < size; ++i) { 129 final float predictedProb = 130 receivedTargets.get(i).getSelectProbability(); 131 if (predictedProb != mTargets.get(i).getSelectProbability()) { 132 mTargets.get(i).setSelectProbability(predictedProb); 133 isUpdated = true; 134 } 135 } 136 if (isUpdated) { 137 mRankerServiceName = mResolvedRankerName; 138 } 139 } else { 140 Log.e(TAG, "Sizes of sent and received ResolverTargets diff."); 141 } 142 } else { 143 Log.e(TAG, "Receiving null prediction results."); 144 } 145 mHandler.removeMessages(RESOLVER_RANKER_RESULT_TIMEOUT); 146 mAfterCompute.afterCompute(); 147 } 148 break; 149 150 case RESOLVER_RANKER_RESULT_TIMEOUT: 151 if (DEBUG) { 152 Log.d(TAG, "RESOLVER_RANKER_RESULT_TIMEOUT; unbinding services"); 153 } 154 mHandler.removeMessages(RESOLVER_RANKER_SERVICE_RESULT); 155 mAfterCompute.afterCompute(); 156 break; 157 158 default: 159 super.handleMessage(msg); 160 } 161 } 162 }; 163 164 public interface AfterCompute { 165 public void afterCompute (); 166 } 167 168 public ResolverComparator(Context context, Intent intent, String referrerPackage, 169 AfterCompute afterCompute) { 170 mCollator = Collator.getInstance(context.getResources().getConfiguration().locale); 171 String scheme = intent.getScheme(); 172 mHttp = "http".equals(scheme) || "https".equals(scheme); 173 mReferrerPackage = referrerPackage; 174 mAfterCompute = afterCompute; 175 mContext = context; 176 177 mPm = context.getPackageManager(); 178 mUsm = (UsageStatsManager) context.getSystemService(Context.USAGE_STATS_SERVICE); 179 180 mCurrentTime = System.currentTimeMillis(); 181 mSinceTime = mCurrentTime - USAGE_STATS_PERIOD; 182 mStats = mUsm.queryAndAggregateUsageStats(mSinceTime, mCurrentTime); 183 mContentType = intent.getType(); 184 getContentAnnotations(intent); 185 mAction = intent.getAction(); 186 mRankerServiceName = new ComponentName(mContext, this.getClass()); 187 } 188 189 // get annotations of content from intent. 190 public void getContentAnnotations(Intent intent) { 191 ArrayList<String> annotations = intent.getStringArrayListExtra( 192 Intent.EXTRA_CONTENT_ANNOTATIONS); 193 if (annotations != null) { 194 int size = annotations.size(); 195 if (size > NUM_OF_TOP_ANNOTATIONS_TO_USE) { 196 size = NUM_OF_TOP_ANNOTATIONS_TO_USE; 197 } 198 mAnnotations = new String[size]; 199 for (int i = 0; i < size; i++) { 200 mAnnotations[i] = annotations.get(i); 201 } 202 } 203 } 204 205 public void setCallBack(AfterCompute afterCompute) { 206 mAfterCompute = afterCompute; 207 } 208 209 // compute features for each target according to usage stats of targets. 210 public void compute(List<ResolvedComponentInfo> targets) { 211 reset(); 212 213 final long recentSinceTime = mCurrentTime - RECENCY_TIME_PERIOD; 214 215 float mostRecencyScore = 1.0f; 216 float mostTimeSpentScore = 1.0f; 217 float mostLaunchScore = 1.0f; 218 float mostChooserScore = 1.0f; 219 220 for (ResolvedComponentInfo target : targets) { 221 final ResolverTarget resolverTarget = new ResolverTarget(); 222 mTargetsDict.put(target.name, resolverTarget); 223 final UsageStats pkStats = mStats.get(target.name.getPackageName()); 224 if (pkStats != null) { 225 // Only count recency for apps that weren't the caller 226 // since the caller is always the most recent. 227 // Persistent processes muck this up, so omit them too. 228 if (!target.name.getPackageName().equals(mReferrerPackage) 229 && !isPersistentProcess(target)) { 230 final float recencyScore = 231 (float) Math.max(pkStats.getLastTimeUsed() - recentSinceTime, 0); 232 resolverTarget.setRecencyScore(recencyScore); 233 if (recencyScore > mostRecencyScore) { 234 mostRecencyScore = recencyScore; 235 } 236 } 237 final float timeSpentScore = (float) pkStats.getTotalTimeInForeground(); 238 resolverTarget.setTimeSpentScore(timeSpentScore); 239 if (timeSpentScore > mostTimeSpentScore) { 240 mostTimeSpentScore = timeSpentScore; 241 } 242 final float launchScore = (float) pkStats.mLaunchCount; 243 resolverTarget.setLaunchScore(launchScore); 244 if (launchScore > mostLaunchScore) { 245 mostLaunchScore = launchScore; 246 } 247 248 float chooserScore = 0.0f; 249 if (pkStats.mChooserCounts != null && mAction != null 250 && pkStats.mChooserCounts.get(mAction) != null) { 251 chooserScore = (float) pkStats.mChooserCounts.get(mAction) 252 .getOrDefault(mContentType, 0); 253 if (mAnnotations != null) { 254 final int size = mAnnotations.length; 255 for (int i = 0; i < size; i++) { 256 chooserScore += (float) pkStats.mChooserCounts.get(mAction) 257 .getOrDefault(mAnnotations[i], 0); 258 } 259 } 260 } 261 if (DEBUG) { 262 if (mAction == null) { 263 Log.d(TAG, "Action type is null"); 264 } else { 265 Log.d(TAG, "Chooser Count of " + mAction + ":" + 266 target.name.getPackageName() + " is " + 267 Float.toString(chooserScore)); 268 } 269 } 270 resolverTarget.setChooserScore(chooserScore); 271 if (chooserScore > mostChooserScore) { 272 mostChooserScore = chooserScore; 273 } 274 } 275 } 276 277 if (DEBUG) { 278 Log.d(TAG, "compute - mostRecencyScore: " + mostRecencyScore 279 + " mostTimeSpentScore: " + mostTimeSpentScore 280 + " mostLaunchScore: " + mostLaunchScore 281 + " mostChooserScore: " + mostChooserScore); 282 } 283 284 mTargets = new ArrayList<>(mTargetsDict.values()); 285 for (ResolverTarget target : mTargets) { 286 final float recency = target.getRecencyScore() / mostRecencyScore; 287 setFeatures(target, recency * recency * RECENCY_MULTIPLIER, 288 target.getLaunchScore() / mostLaunchScore, 289 target.getTimeSpentScore() / mostTimeSpentScore, 290 target.getChooserScore() / mostChooserScore); 291 addDefaultSelectProbability(target); 292 if (DEBUG) { 293 Log.d(TAG, "Scores: " + target); 294 } 295 } 296 predictSelectProbabilities(mTargets); 297 } 298 299 @Override 300 public int compare(ResolvedComponentInfo lhsp, ResolvedComponentInfo rhsp) { 301 final ResolveInfo lhs = lhsp.getResolveInfoAt(0); 302 final ResolveInfo rhs = rhsp.getResolveInfoAt(0); 303 304 // We want to put the one targeted to another user at the end of the dialog. 305 if (lhs.targetUserId != UserHandle.USER_CURRENT) { 306 return rhs.targetUserId != UserHandle.USER_CURRENT ? 0 : 1; 307 } 308 if (rhs.targetUserId != UserHandle.USER_CURRENT) { 309 return -1; 310 } 311 312 if (mHttp) { 313 // Special case: we want filters that match URI paths/schemes to be 314 // ordered before others. This is for the case when opening URIs, 315 // to make native apps go above browsers. 316 final boolean lhsSpecific = ResolverActivity.isSpecificUriMatch(lhs.match); 317 final boolean rhsSpecific = ResolverActivity.isSpecificUriMatch(rhs.match); 318 if (lhsSpecific != rhsSpecific) { 319 return lhsSpecific ? -1 : 1; 320 } 321 } 322 323 final boolean lPinned = lhsp.isPinned(); 324 final boolean rPinned = rhsp.isPinned(); 325 326 if (lPinned && !rPinned) { 327 return -1; 328 } else if (!lPinned && rPinned) { 329 return 1; 330 } 331 332 // Pinned items stay stable within a normal lexical sort and ignore scoring. 333 if (!lPinned && !rPinned) { 334 if (mStats != null) { 335 final ResolverTarget lhsTarget = mTargetsDict.get(new ComponentName( 336 lhs.activityInfo.packageName, lhs.activityInfo.name)); 337 final ResolverTarget rhsTarget = mTargetsDict.get(new ComponentName( 338 rhs.activityInfo.packageName, rhs.activityInfo.name)); 339 340 if (lhsTarget != null && rhsTarget != null) { 341 final int selectProbabilityDiff = Float.compare( 342 rhsTarget.getSelectProbability(), lhsTarget.getSelectProbability()); 343 344 if (selectProbabilityDiff != 0) { 345 return selectProbabilityDiff > 0 ? 1 : -1; 346 } 347 } 348 } 349 } 350 351 CharSequence sa = lhs.loadLabel(mPm); 352 if (sa == null) sa = lhs.activityInfo.name; 353 CharSequence sb = rhs.loadLabel(mPm); 354 if (sb == null) sb = rhs.activityInfo.name; 355 356 return mCollator.compare(sa.toString().trim(), sb.toString().trim()); 357 } 358 359 public float getScore(ComponentName name) { 360 final ResolverTarget target = mTargetsDict.get(name); 361 if (target != null) { 362 return target.getSelectProbability(); 363 } 364 return 0; 365 } 366 367 public void updateChooserCounts(String packageName, int userId, String action) { 368 if (mUsm != null) { 369 mUsm.reportChooserSelection(packageName, userId, mContentType, mAnnotations, action); 370 } 371 } 372 373 // update ranking model when the connection to it is valid. 374 public void updateModel(ComponentName componentName) { 375 synchronized (mLock) { 376 if (mRanker != null) { 377 try { 378 int selectedPos = new ArrayList<ComponentName>(mTargetsDict.keySet()) 379 .indexOf(componentName); 380 if (selectedPos >= 0 && mTargets != null) { 381 final float selectedProbability = getScore(componentName); 382 int order = 0; 383 for (ResolverTarget target : mTargets) { 384 if (target.getSelectProbability() > selectedProbability) { 385 order++; 386 } 387 } 388 logMetrics(order); 389 mRanker.train(mTargets, selectedPos); 390 } else { 391 if (DEBUG) { 392 Log.d(TAG, "Selected a unknown component: " + componentName); 393 } 394 } 395 } catch (RemoteException e) { 396 Log.e(TAG, "Error in Train: " + e); 397 } 398 } else { 399 if (DEBUG) { 400 Log.d(TAG, "Ranker is null; skip updateModel."); 401 } 402 } 403 } 404 } 405 406 // unbind the service and clear unhandled messges. 407 public void destroy() { 408 mHandler.removeMessages(RESOLVER_RANKER_SERVICE_RESULT); 409 mHandler.removeMessages(RESOLVER_RANKER_RESULT_TIMEOUT); 410 if (mConnection != null) { 411 mContext.unbindService(mConnection); 412 mConnection.destroy(); 413 } 414 if (DEBUG) { 415 Log.d(TAG, "Unbinded Resolver Ranker."); 416 } 417 } 418 419 // records metrics for evaluation. 420 private void logMetrics(int selectedPos) { 421 if (mRankerServiceName != null) { 422 MetricsLogger metricsLogger = new MetricsLogger(); 423 LogMaker log = new LogMaker(MetricsEvent.ACTION_TARGET_SELECTED); 424 log.setComponentName(mRankerServiceName); 425 int isCategoryUsed = (mAnnotations == null) ? 0 : 1; 426 log.addTaggedData(MetricsEvent.FIELD_IS_CATEGORY_USED, isCategoryUsed); 427 log.addTaggedData(MetricsEvent.FIELD_RANKED_POSITION, selectedPos); 428 metricsLogger.write(log); 429 } 430 } 431 432 // connect to a ranking service. 433 private void initRanker(Context context) { 434 synchronized (mLock) { 435 if (mConnection != null && mRanker != null) { 436 if (DEBUG) { 437 Log.d(TAG, "Ranker still exists; reusing the existing one."); 438 } 439 return; 440 } 441 } 442 Intent intent = resolveRankerService(); 443 if (intent == null) { 444 return; 445 } 446 mConnectSignal = new CountDownLatch(1); 447 mConnection = new ResolverRankerServiceConnection(mConnectSignal); 448 context.bindServiceAsUser(intent, mConnection, Context.BIND_AUTO_CREATE, UserHandle.SYSTEM); 449 } 450 451 // resolve the service for ranking. 452 private Intent resolveRankerService() { 453 Intent intent = new Intent(ResolverRankerService.SERVICE_INTERFACE); 454 final List<ResolveInfo> resolveInfos = mPm.queryIntentServices(intent, 0); 455 for (ResolveInfo resolveInfo : resolveInfos) { 456 if (resolveInfo == null || resolveInfo.serviceInfo == null 457 || resolveInfo.serviceInfo.applicationInfo == null) { 458 if (DEBUG) { 459 Log.d(TAG, "Failed to retrieve a ranker: " + resolveInfo); 460 } 461 continue; 462 } 463 ComponentName componentName = new ComponentName( 464 resolveInfo.serviceInfo.applicationInfo.packageName, 465 resolveInfo.serviceInfo.name); 466 try { 467 final String perm = mPm.getServiceInfo(componentName, 0).permission; 468 if (!ResolverRankerService.BIND_PERMISSION.equals(perm)) { 469 Log.w(TAG, "ResolverRankerService " + componentName + " does not require" 470 + " permission " + ResolverRankerService.BIND_PERMISSION 471 + " - this service will not be queried for ResolverComparator." 472 + " add android:permission=\"" 473 + ResolverRankerService.BIND_PERMISSION + "\"" 474 + " to the <service> tag for " + componentName 475 + " in the manifest."); 476 continue; 477 } 478 if (PackageManager.PERMISSION_GRANTED != mPm.checkPermission( 479 ResolverRankerService.HOLD_PERMISSION, 480 resolveInfo.serviceInfo.packageName)) { 481 Log.w(TAG, "ResolverRankerService " + componentName + " does not hold" 482 + " permission " + ResolverRankerService.HOLD_PERMISSION 483 + " - this service will not be queried for ResolverComparator."); 484 continue; 485 } 486 } catch (NameNotFoundException e) { 487 Log.e(TAG, "Could not look up service " + componentName 488 + "; component name not found"); 489 continue; 490 } 491 if (DEBUG) { 492 Log.d(TAG, "Succeeded to retrieve a ranker: " + componentName); 493 } 494 mResolvedRankerName = componentName; 495 intent.setComponent(componentName); 496 return intent; 497 } 498 return null; 499 } 500 501 // set a watchdog, to avoid waiting for ranking service for too long. 502 private void startWatchDog(int timeOutLimit) { 503 if (DEBUG) Log.d(TAG, "Setting watchdog timer for " + timeOutLimit + "ms"); 504 if (mHandler == null) { 505 Log.d(TAG, "Error: Handler is Null; Needs to be initialized."); 506 } 507 mHandler.sendEmptyMessageDelayed(RESOLVER_RANKER_RESULT_TIMEOUT, timeOutLimit); 508 } 509 510 private class ResolverRankerServiceConnection implements ServiceConnection { 511 private final CountDownLatch mConnectSignal; 512 513 public ResolverRankerServiceConnection(CountDownLatch connectSignal) { 514 mConnectSignal = connectSignal; 515 } 516 517 public final IResolverRankerResult resolverRankerResult = 518 new IResolverRankerResult.Stub() { 519 @Override 520 public void sendResult(List<ResolverTarget> targets) throws RemoteException { 521 if (DEBUG) { 522 Log.d(TAG, "Sending Result back to Resolver: " + targets); 523 } 524 synchronized (mLock) { 525 final Message msg = Message.obtain(); 526 msg.what = RESOLVER_RANKER_SERVICE_RESULT; 527 msg.obj = targets; 528 mHandler.sendMessage(msg); 529 } 530 } 531 }; 532 533 @Override 534 public void onServiceConnected(ComponentName name, IBinder service) { 535 if (DEBUG) { 536 Log.d(TAG, "onServiceConnected: " + name); 537 } 538 synchronized (mLock) { 539 mRanker = IResolverRankerService.Stub.asInterface(service); 540 mConnectSignal.countDown(); 541 } 542 } 543 544 @Override 545 public void onServiceDisconnected(ComponentName name) { 546 if (DEBUG) { 547 Log.d(TAG, "onServiceDisconnected: " + name); 548 } 549 synchronized (mLock) { 550 destroy(); 551 } 552 } 553 554 public void destroy() { 555 synchronized (mLock) { 556 mRanker = null; 557 } 558 } 559 } 560 561 private void reset() { 562 mTargetsDict.clear(); 563 mTargets = null; 564 mRankerServiceName = new ComponentName(mContext, this.getClass()); 565 mResolvedRankerName = null; 566 startWatchDog(WATCHDOG_TIMEOUT_MILLIS); 567 initRanker(mContext); 568 } 569 570 // predict select probabilities if ranking service is valid. 571 private void predictSelectProbabilities(List<ResolverTarget> targets) { 572 if (mConnection == null) { 573 if (DEBUG) { 574 Log.d(TAG, "Has not found valid ResolverRankerService; Skip Prediction"); 575 } 576 return; 577 } else { 578 try { 579 mConnectSignal.await(CONNECTION_COST_TIMEOUT_MILLIS, TimeUnit.MILLISECONDS); 580 synchronized (mLock) { 581 if (mRanker != null) { 582 mRanker.predict(targets, mConnection.resolverRankerResult); 583 return; 584 } else { 585 if (DEBUG) { 586 Log.d(TAG, "Ranker has not been initialized; skip predict."); 587 } 588 } 589 } 590 } catch (InterruptedException e) { 591 Log.e(TAG, "Error in Wait for Service Connection."); 592 } catch (RemoteException e) { 593 Log.e(TAG, "Error in Predict: " + e); 594 } 595 } 596 if (mAfterCompute != null) { 597 mAfterCompute.afterCompute(); 598 } 599 } 600 601 // adds select prob as the default values, according to a pre-trained Logistic Regression model. 602 private void addDefaultSelectProbability(ResolverTarget target) { 603 float sum = 2.5543f * target.getLaunchScore() + 2.8412f * target.getTimeSpentScore() + 604 0.269f * target.getRecencyScore() + 4.2222f * target.getChooserScore(); 605 target.setSelectProbability((float) (1.0 / (1.0 + Math.exp(1.6568f - sum)))); 606 } 607 608 // sets features for each target 609 private void setFeatures(ResolverTarget target, float recencyScore, float launchScore, 610 float timeSpentScore, float chooserScore) { 611 target.setRecencyScore(recencyScore); 612 target.setLaunchScore(launchScore); 613 target.setTimeSpentScore(timeSpentScore); 614 target.setChooserScore(chooserScore); 615 } 616 617 static boolean isPersistentProcess(ResolvedComponentInfo rci) { 618 if (rci != null && rci.getCount() > 0) { 619 return (rci.getResolveInfoAt(0).activityInfo.applicationInfo.flags & 620 ApplicationInfo.FLAG_PERSISTENT) != 0; 621 } 622 return false; 623 } 624} 625