1 /*
2  * Copyright (C) 2018 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 package com.android.server.appop;
17 
18 import static android.app.AppOpsManager.FILTER_BY_ATTRIBUTION_TAG;
19 import static android.app.AppOpsManager.FILTER_BY_OP_NAMES;
20 import static android.app.AppOpsManager.FILTER_BY_PACKAGE_NAME;
21 import static android.app.AppOpsManager.FILTER_BY_UID;
22 import static android.app.AppOpsManager.HISTORY_FLAG_AGGREGATE;
23 import static android.app.AppOpsManager.HISTORY_FLAG_DISCRETE;
24 
25 import android.annotation.NonNull;
26 import android.annotation.Nullable;
27 import android.app.AppOpsManager;
28 import android.app.AppOpsManager.HistoricalMode;
29 import android.app.AppOpsManager.HistoricalOp;
30 import android.app.AppOpsManager.HistoricalOps;
31 import android.app.AppOpsManager.HistoricalOpsRequestFilter;
32 import android.app.AppOpsManager.HistoricalPackageOps;
33 import android.app.AppOpsManager.HistoricalUidOps;
34 import android.app.AppOpsManager.OpFlags;
35 import android.app.AppOpsManager.OpHistoryFlags;
36 import android.app.AppOpsManager.UidState;
37 import android.content.ContentResolver;
38 import android.database.ContentObserver;
39 import android.net.Uri;
40 import android.os.Build;
41 import android.os.Bundle;
42 import android.os.Debug;
43 import android.os.Environment;
44 import android.os.Message;
45 import android.os.Process;
46 import android.os.RemoteCallback;
47 import android.os.UserHandle;
48 import android.provider.Settings;
49 import android.util.ArraySet;
50 import android.util.LongSparseArray;
51 import android.util.Slog;
52 import android.util.TimeUtils;
53 import android.util.Xml;
54 
55 import com.android.internal.annotations.GuardedBy;
56 import com.android.internal.os.AtomicDirectory;
57 import com.android.internal.util.ArrayUtils;
58 import com.android.internal.util.XmlUtils;
59 import com.android.internal.util.function.pooled.PooledLambda;
60 import com.android.modules.utils.TypedXmlPullParser;
61 import com.android.modules.utils.TypedXmlSerializer;
62 import com.android.server.FgThread;
63 import com.android.server.IoThread;
64 
65 import org.xmlpull.v1.XmlPullParserException;
66 
67 import java.io.File;
68 import java.io.FileInputStream;
69 import java.io.FileNotFoundException;
70 import java.io.FileOutputStream;
71 import java.io.IOException;
72 import java.io.PrintWriter;
73 import java.nio.file.Files;
74 import java.text.SimpleDateFormat;
75 import java.util.ArrayList;
76 import java.util.Arrays;
77 import java.util.Collections;
78 import java.util.Date;
79 import java.util.LinkedList;
80 import java.util.List;
81 import java.util.Objects;
82 import java.util.Set;
83 import java.util.concurrent.TimeUnit;
84 
85 /**
86  * This class manages historical app op state. This includes reading, persistence,
87  * accounting, querying.
88  * <p>
89  * The history is kept forever in multiple files. Each file time contains the
90  * relative offset from the current time which time is encoded in the file name.
91  * The files contain historical app op state snapshots which have times that
92  * are relative to the time of the container file.
93  *
94  * The data in the files are stored in a logarithmic fashion where where every
95  * subsequent file would contain data for ten times longer interval with ten
96  * times more time distance between snapshots. Hence, the more time passes
97  * the lesser the fidelity.
98  * <p>
99  * For example, the first file would contain data for 1 days with snapshots
100  * every 0.1 days, the next file would contain data for the period 1 to 10
101  * days with snapshots every 1 days, and so on.
102  * <p>
103  * THREADING AND LOCKING: Reported ops must be processed as quickly as possible.
104  * We keep ops pending to be persisted in memory and write to disk on a background
105  * thread. Hence, methods that report op changes are locking only the in memory
106  * state guarded by the mInMemoryLock which happens to be the app ops service lock
107  * avoiding a lock addition on the critical path. When a query comes we need to
108  * evaluate it based off both in memory and on disk state. This means they need to
109  * be frozen with respect to each other and not change from the querying caller's
110  * perspective. To achieve this we add a dedicated mOnDiskLock to guard the on
111  * disk state. To have fast critical path we need to limit the locking of the
112  * mInMemoryLock, thus for operations that touch in memory and on disk state one
113  * must grab first the mOnDiskLock and then the mInMemoryLock and limit the
114  * in memory lock to extraction of relevant data. Locking order is critical to
115  * avoid deadlocks. The convention is that xxxDLocked suffix means the method
116  * must be called with the mOnDiskLock lock, xxxMLocked suffix means the method
117  * must be called with the mInMemoryLock, xxxDMLocked suffix means the method
118  * must be called with the mOnDiskLock and mInMemoryLock locks acquired in that
119  * exact order.
120  * <p>
121  * INITIALIZATION: We can initialize persistence only after the system is ready
122  * as we need to check the optional configuration override from the settings
123  * database which is not initialized at the time the app ops service is created.
124  * This means that all entry points that touch persistence should be short
125  * circuited via isPersistenceInitialized() check.
126  */
127 // TODO (bug:122218838): Make sure we handle start of epoch time
128 // TODO (bug:122218838): Validate changed time is handled correctly
129 final class HistoricalRegistry {
130     private static final boolean DEBUG = false;
131     private static final boolean KEEP_WTF_LOG = Build.IS_DEBUGGABLE;
132 
133     private static final String LOG_TAG = HistoricalRegistry.class.getSimpleName();
134 
135     private static final String PARAMETER_DELIMITER = ",";
136     private static final String PARAMETER_ASSIGNMENT = "=";
137 
138     private volatile @NonNull DiscreteRegistry mDiscreteRegistry;
139 
140     @GuardedBy("mLock")
141     private @NonNull LinkedList<HistoricalOps> mPendingWrites = new LinkedList<>();
142 
143     // Lock for read/write access to on disk state
144     private final Object mOnDiskLock = new Object();
145 
146     //Lock for read/write access to in memory state
147     private final @NonNull Object mInMemoryLock;
148 
149     private static final int MSG_WRITE_PENDING_HISTORY = 1;
150 
151     // See mMode
152     private static final int DEFAULT_MODE = AppOpsManager.HISTORICAL_MODE_ENABLED_ACTIVE;
153 
154     // See mBaseSnapshotInterval
155     private static final long DEFAULT_SNAPSHOT_INTERVAL_MILLIS = TimeUnit.MINUTES.toMillis(15);
156 
157     // See mIntervalCompressionMultiplier
158     private static final long DEFAULT_COMPRESSION_STEP = 10;
159 
160     private static final String HISTORY_FILE_SUFFIX = ".xml";
161 
162     /**
163      * Whether history is enabled.
164      */
165     @GuardedBy("mInMemoryLock")
166     private int mMode = AppOpsManager.HISTORICAL_MODE_ENABLED_ACTIVE;
167 
168     /**
169      * This granularity has been chosen to allow clean delineation for intervals
170      * humans understand, 15 min, 60, min, a day, a week, a month (30 days).
171      */
172     @GuardedBy("mInMemoryLock")
173     private long mBaseSnapshotInterval = DEFAULT_SNAPSHOT_INTERVAL_MILLIS;
174 
175     /**
176      * The compression between steps. Each subsequent step is this much longer
177      * in terms of duration and each snapshot is this much more apart from the
178      * previous step.
179      */
180     @GuardedBy("mInMemoryLock")
181     private long mIntervalCompressionMultiplier = DEFAULT_COMPRESSION_STEP;
182 
183     // The current ops to which to add statistics.
184     @GuardedBy("mInMemoryLock")
185     private @Nullable HistoricalOps mCurrentHistoricalOps;
186 
187     // The time we should write the next snapshot.
188     @GuardedBy("mInMemoryLock")
189     private long mNextPersistDueTimeMillis;
190 
191     // How much to offset the history on the next write.
192     @GuardedBy("mInMemoryLock")
193     private long mPendingHistoryOffsetMillis;
194 
195     // Object managing persistence (read/write)
196     @GuardedBy("mOnDiskLock")
197     private Persistence mPersistence;
198 
HistoricalRegistry(@onNull Object lock)199     HistoricalRegistry(@NonNull Object lock) {
200         mInMemoryLock = lock;
201         mDiscreteRegistry = new DiscreteRegistry(lock);
202     }
203 
HistoricalRegistry(@onNull HistoricalRegistry other)204     HistoricalRegistry(@NonNull HistoricalRegistry other) {
205         this(other.mInMemoryLock);
206         mMode = other.mMode;
207         mBaseSnapshotInterval = other.mBaseSnapshotInterval;
208         mIntervalCompressionMultiplier = other.mIntervalCompressionMultiplier;
209         mDiscreteRegistry = other.mDiscreteRegistry;
210     }
211 
systemReady(@onNull ContentResolver resolver)212     void systemReady(@NonNull ContentResolver resolver) {
213         mDiscreteRegistry.systemReady();
214         final Uri uri = Settings.Global.getUriFor(Settings.Global.APPOP_HISTORY_PARAMETERS);
215         resolver.registerContentObserver(uri, false, new ContentObserver(
216                 FgThread.getHandler()) {
217             @Override
218             public void onChange(boolean selfChange) {
219                 updateParametersFromSetting(resolver);
220             }
221         });
222 
223         updateParametersFromSetting(resolver);
224 
225         synchronized (mOnDiskLock) {
226             synchronized (mInMemoryLock) {
227                 if (mMode != AppOpsManager.HISTORICAL_MODE_DISABLED) {
228                     // Can be uninitialized if there is no config in the settings table.
229                     if (!isPersistenceInitializedMLocked()) {
230                         mPersistence = new Persistence(mBaseSnapshotInterval,
231                                 mIntervalCompressionMultiplier);
232                     }
233 
234                     // When starting always adjust history to now.
235                     final long lastPersistTimeMills =
236                             mPersistence.getLastPersistTimeMillisDLocked();
237 
238                     if (lastPersistTimeMills > 0) {
239                         mPendingHistoryOffsetMillis = System.currentTimeMillis()
240                                 - lastPersistTimeMills;
241 
242                         if (DEBUG) {
243                             Slog.i(LOG_TAG, "Time since last write: "
244                                     + TimeUtils.formatDuration(mPendingHistoryOffsetMillis)
245                                     + " by which to push history on next write");
246                         }
247                     }
248                 }
249             }
250         }
251     }
252 
isPersistenceInitializedMLocked()253     private boolean isPersistenceInitializedMLocked() {
254         return mPersistence != null;
255     }
256 
updateParametersFromSetting(@onNull ContentResolver resolver)257     private void updateParametersFromSetting(@NonNull ContentResolver resolver) {
258         final String setting = Settings.Global.getString(resolver,
259                 Settings.Global.APPOP_HISTORY_PARAMETERS);
260         if (setting == null) {
261             return;
262         }
263         String modeValue = null;
264         String baseSnapshotIntervalValue = null;
265         String intervalMultiplierValue = null;
266         final String[] parameters = setting.split(PARAMETER_DELIMITER);
267         for (String parameter : parameters) {
268             final String[] parts = parameter.split(PARAMETER_ASSIGNMENT);
269             if (parts.length == 2) {
270                 final String key = parts[0].trim();
271                 switch (key) {
272                     case Settings.Global.APPOP_HISTORY_MODE: {
273                         modeValue = parts[1].trim();
274                     } break;
275                     case Settings.Global.APPOP_HISTORY_BASE_INTERVAL_MILLIS: {
276                         baseSnapshotIntervalValue = parts[1].trim();
277                     } break;
278                     case Settings.Global.APPOP_HISTORY_INTERVAL_MULTIPLIER: {
279                         intervalMultiplierValue = parts[1].trim();
280                     } break;
281                     default: {
282                         Slog.w(LOG_TAG, "Unknown parameter: " + parameter);
283                     }
284                 }
285             }
286         }
287         if (modeValue != null && baseSnapshotIntervalValue != null
288                 && intervalMultiplierValue != null) {
289             try {
290                 final int mode = AppOpsManager.parseHistoricalMode(modeValue);
291                 final long baseSnapshotInterval = Long.parseLong(baseSnapshotIntervalValue);
292                 final int intervalCompressionMultiplier = Integer.parseInt(intervalMultiplierValue);
293                 setHistoryParameters(mode, baseSnapshotInterval,intervalCompressionMultiplier);
294                 return;
295             } catch (NumberFormatException ignored) {}
296         }
297         Slog.w(LOG_TAG, "Bad value for" + Settings.Global.APPOP_HISTORY_PARAMETERS
298                 + "=" + setting + " resetting!");
299     }
300 
dump(String prefix, PrintWriter pw, int filterUid, @Nullable String filterPackage, @Nullable String filterAttributionTag, int filterOp, @HistoricalOpsRequestFilter int filter)301     void dump(String prefix, PrintWriter pw, int filterUid, @Nullable String filterPackage,
302             @Nullable String filterAttributionTag, int filterOp,
303             @HistoricalOpsRequestFilter int filter) {
304         synchronized (mOnDiskLock) {
305             synchronized (mInMemoryLock) {
306                 pw.println();
307                 pw.print(prefix);
308                 pw.print("History:");
309 
310                 pw.print("  mode=");
311                 pw.println(AppOpsManager.historicalModeToString(mMode));
312 
313                 final StringDumpVisitor visitor = new StringDumpVisitor(prefix + "  ",
314                         pw, filterUid, filterPackage, filterAttributionTag, filterOp, filter);
315                 final long nowMillis = System.currentTimeMillis();
316 
317                 // Dump in memory state first
318                 final HistoricalOps currentOps = getUpdatedPendingHistoricalOpsMLocked(
319                         nowMillis);
320                 makeRelativeToEpochStart(currentOps, nowMillis);
321                 currentOps.accept(visitor);
322 
323                 if (!isPersistenceInitializedMLocked()) {
324                     Slog.e(LOG_TAG, "Interaction before persistence initialized");
325                     return;
326                 }
327 
328                 final List<HistoricalOps> ops = mPersistence.readHistoryDLocked();
329                 if (ops != null) {
330                     // TODO (bug:122218838): Make sure this is properly dumped
331                     final long remainingToFillBatchMillis = mNextPersistDueTimeMillis
332                             - nowMillis - mBaseSnapshotInterval;
333                     final int opCount = ops.size();
334                     for (int i = 0; i < opCount; i++) {
335                         final HistoricalOps op = ops.get(i);
336                         op.offsetBeginAndEndTime(remainingToFillBatchMillis);
337                         makeRelativeToEpochStart(op, nowMillis);
338                         op.accept(visitor);
339                     }
340                 } else {
341                     pw.println("  Empty");
342                 }
343             }
344         }
345     }
346 
dumpDiscreteData(@onNull PrintWriter pw, int uidFilter, @Nullable String packageNameFilter, @Nullable String attributionTagFilter, @HistoricalOpsRequestFilter int filter, int dumpOp, @NonNull SimpleDateFormat sdf, @NonNull Date date, @NonNull String prefix, int nDiscreteOps)347     void dumpDiscreteData(@NonNull PrintWriter pw, int uidFilter,
348             @Nullable String packageNameFilter, @Nullable String attributionTagFilter,
349             @HistoricalOpsRequestFilter int filter, int dumpOp,
350             @NonNull SimpleDateFormat sdf, @NonNull Date date, @NonNull String prefix,
351             int nDiscreteOps) {
352         mDiscreteRegistry.dump(pw, uidFilter, packageNameFilter, attributionTagFilter, filter,
353                 dumpOp, sdf, date, prefix, nDiscreteOps);
354     }
355 
getMode()356     @HistoricalMode int getMode() {
357         synchronized (mInMemoryLock) {
358             return mMode;
359         }
360     }
361 
getHistoricalOpsFromDiskRaw(int uid, @Nullable String packageName, @Nullable String attributionTag, @Nullable String[] opNames, @OpHistoryFlags int historyFlags, @HistoricalOpsRequestFilter int filter, long beginTimeMillis, long endTimeMillis, @OpFlags int flags, String[] attributionExemptedPackages, @NonNull RemoteCallback callback)362     void getHistoricalOpsFromDiskRaw(int uid, @Nullable String packageName,
363             @Nullable String attributionTag, @Nullable String[] opNames,
364             @OpHistoryFlags int historyFlags, @HistoricalOpsRequestFilter int filter,
365             long beginTimeMillis, long endTimeMillis, @OpFlags int flags,
366             String[] attributionExemptedPackages, @NonNull RemoteCallback callback) {
367         final HistoricalOps result = new HistoricalOps(beginTimeMillis, endTimeMillis);
368 
369         if ((historyFlags & HISTORY_FLAG_AGGREGATE) != 0) {
370             synchronized (mOnDiskLock) {
371                 synchronized (mInMemoryLock) {
372                     if (!isPersistenceInitializedMLocked()) {
373                         Slog.e(LOG_TAG, "Interaction before persistence initialized");
374                         callback.sendResult(new Bundle());
375                         return;
376                     }
377                 }
378                 mPersistence.collectHistoricalOpsDLocked(result, uid, packageName,
379                         attributionTag,
380                         opNames, filter, beginTimeMillis, endTimeMillis, flags);
381             }
382         }
383 
384         if ((historyFlags & HISTORY_FLAG_DISCRETE) != 0) {
385             mDiscreteRegistry.addFilteredDiscreteOpsToHistoricalOps(result, beginTimeMillis,
386                     endTimeMillis, filter, uid, packageName, opNames, attributionTag,
387                     flags, new ArraySet<>(attributionExemptedPackages));
388         }
389 
390         final Bundle payload = new Bundle();
391         payload.putParcelable(AppOpsManager.KEY_HISTORICAL_OPS, result);
392         callback.sendResult(payload);
393     }
394 
getHistoricalOps(int uid, @Nullable String packageName, @Nullable String attributionTag, @Nullable String[] opNames, @OpHistoryFlags int historyFlags, @HistoricalOpsRequestFilter int filter, long beginTimeMillis, long endTimeMillis, @OpFlags int flags, @Nullable String[] attributionExemptPkgs, @NonNull RemoteCallback callback)395     void getHistoricalOps(int uid, @Nullable String packageName, @Nullable String attributionTag,
396             @Nullable String[] opNames, @OpHistoryFlags int historyFlags,
397             @HistoricalOpsRequestFilter int filter, long beginTimeMillis, long endTimeMillis,
398             @OpFlags int flags, @Nullable String[] attributionExemptPkgs,
399             @NonNull RemoteCallback callback) {
400         final long currentTimeMillis = System.currentTimeMillis();
401         if (endTimeMillis == Long.MAX_VALUE) {
402             endTimeMillis = currentTimeMillis;
403         }
404 
405         final Bundle payload = new Bundle();
406 
407         // Argument times are based off epoch start while our internal store is
408         // based off now, so take this into account.
409         final long inMemoryAdjBeginTimeMillis = Math.max(currentTimeMillis - endTimeMillis, 0);
410         final long inMemoryAdjEndTimeMillis = Math.max(currentTimeMillis - beginTimeMillis, 0);
411         final HistoricalOps result = new HistoricalOps(inMemoryAdjBeginTimeMillis,
412                 inMemoryAdjEndTimeMillis);
413 
414         if ((historyFlags & HISTORY_FLAG_DISCRETE) != 0) {
415             mDiscreteRegistry.addFilteredDiscreteOpsToHistoricalOps(result, beginTimeMillis,
416                     endTimeMillis, filter, uid, packageName, opNames, attributionTag, flags,
417                     new ArraySet<>(attributionExemptPkgs));
418         }
419 
420         if ((historyFlags & HISTORY_FLAG_AGGREGATE) != 0) {
421             synchronized (mOnDiskLock) {
422                 final List<HistoricalOps> pendingWrites;
423                 final HistoricalOps currentOps;
424                 boolean collectOpsFromDisk;
425 
426                 synchronized (mInMemoryLock) {
427                     if (!isPersistenceInitializedMLocked()) {
428                         Slog.e(LOG_TAG, "Interaction before persistence initialized");
429                         callback.sendResult(new Bundle());
430                         return;
431                     }
432 
433                     currentOps = getUpdatedPendingHistoricalOpsMLocked(currentTimeMillis);
434                     if (!(inMemoryAdjBeginTimeMillis >= currentOps.getEndTimeMillis()
435                             || inMemoryAdjEndTimeMillis <= currentOps.getBeginTimeMillis())) {
436                         // Some of the current batch falls into the query, so extract that.
437                         final HistoricalOps currentOpsCopy = new HistoricalOps(currentOps);
438                         currentOpsCopy.filter(uid, packageName, attributionTag, opNames,
439                                 historyFlags, filter, inMemoryAdjBeginTimeMillis,
440                                 inMemoryAdjEndTimeMillis);
441                         result.merge(currentOpsCopy);
442                     }
443                     pendingWrites = new ArrayList<>(mPendingWrites);
444                     mPendingWrites.clear();
445                     collectOpsFromDisk = inMemoryAdjEndTimeMillis > currentOps.getEndTimeMillis();
446                 }
447 
448                 // If the query was only for in-memory state - done.
449                 if (collectOpsFromDisk) {
450                     // If there is a write in flight we need to force it now
451                     persistPendingHistory(pendingWrites);
452                     // Collect persisted state.
453                     final long onDiskAndInMemoryOffsetMillis = currentTimeMillis
454                             - mNextPersistDueTimeMillis + mBaseSnapshotInterval;
455                     final long onDiskAdjBeginTimeMillis = Math.max(inMemoryAdjBeginTimeMillis
456                             - onDiskAndInMemoryOffsetMillis, 0);
457                     final long onDiskAdjEndTimeMillis = Math.max(inMemoryAdjEndTimeMillis
458                             - onDiskAndInMemoryOffsetMillis, 0);
459                     mPersistence.collectHistoricalOpsDLocked(result, uid, packageName,
460                             attributionTag,
461                             opNames, filter, onDiskAdjBeginTimeMillis, onDiskAdjEndTimeMillis,
462                             flags);
463                 }
464             }
465         }
466         // Rebase the result time to be since epoch.
467         result.setBeginAndEndTime(beginTimeMillis, endTimeMillis);
468 
469         // Send back the result.
470         payload.putParcelable(AppOpsManager.KEY_HISTORICAL_OPS, result);
471         callback.sendResult(payload);
472     }
473 
incrementOpAccessedCount(int op, int uid, @NonNull String packageName, @Nullable String attributionTag, @UidState int uidState, @OpFlags int flags, long accessTime, @AppOpsManager.AttributionFlags int attributionFlags, int attributionChainId)474     void incrementOpAccessedCount(int op, int uid, @NonNull String packageName,
475             @Nullable String attributionTag, @UidState int uidState, @OpFlags int flags,
476             long accessTime, @AppOpsManager.AttributionFlags int attributionFlags,
477             int attributionChainId) {
478         synchronized (mInMemoryLock) {
479             if (mMode == AppOpsManager.HISTORICAL_MODE_ENABLED_ACTIVE) {
480                 if (!isPersistenceInitializedMLocked()) {
481                     Slog.v(LOG_TAG, "Interaction before persistence initialized");
482                     return;
483                 }
484                 getUpdatedPendingHistoricalOpsMLocked(
485                         System.currentTimeMillis()).increaseAccessCount(op, uid, packageName,
486                         attributionTag, uidState, flags, 1);
487 
488                 mDiscreteRegistry.recordDiscreteAccess(uid, packageName, op, attributionTag,
489                         flags, uidState, accessTime, -1, attributionFlags, attributionChainId);
490             }
491         }
492     }
493 
incrementOpRejected(int op, int uid, @NonNull String packageName, @Nullable String attributionTag, @UidState int uidState, @OpFlags int flags)494     void incrementOpRejected(int op, int uid, @NonNull String packageName,
495             @Nullable String attributionTag, @UidState int uidState, @OpFlags int flags) {
496         synchronized (mInMemoryLock) {
497             if (mMode == AppOpsManager.HISTORICAL_MODE_ENABLED_ACTIVE) {
498                 if (!isPersistenceInitializedMLocked()) {
499                     Slog.v(LOG_TAG, "Interaction before persistence initialized");
500                     return;
501                 }
502                 getUpdatedPendingHistoricalOpsMLocked(
503                         System.currentTimeMillis()).increaseRejectCount(op, uid, packageName,
504                         attributionTag, uidState, flags, 1);
505             }
506         }
507     }
508 
increaseOpAccessDuration(int op, int uid, @NonNull String packageName, @Nullable String attributionTag, @UidState int uidState, @OpFlags int flags, long eventStartTime, long increment, @AppOpsManager.AttributionFlags int attributionFlags, int attributionChainId)509     void increaseOpAccessDuration(int op, int uid, @NonNull String packageName,
510             @Nullable String attributionTag, @UidState int uidState, @OpFlags int flags,
511             long eventStartTime, long increment,
512             @AppOpsManager.AttributionFlags int attributionFlags, int attributionChainId) {
513         synchronized (mInMemoryLock) {
514             if (mMode == AppOpsManager.HISTORICAL_MODE_ENABLED_ACTIVE) {
515                 if (!isPersistenceInitializedMLocked()) {
516                     Slog.v(LOG_TAG, "Interaction before persistence initialized");
517                     return;
518                 }
519                 getUpdatedPendingHistoricalOpsMLocked(
520                         System.currentTimeMillis()).increaseAccessDuration(op, uid, packageName,
521                         attributionTag, uidState, flags, increment);
522                 mDiscreteRegistry.recordDiscreteAccess(uid, packageName, op, attributionTag,
523                         flags, uidState, eventStartTime, increment, attributionFlags,
524                         attributionChainId);
525             }
526         }
527     }
528 
setHistoryParameters(@istoricalMode int mode, long baseSnapshotInterval, long intervalCompressionMultiplier)529     void setHistoryParameters(@HistoricalMode int mode,
530             long baseSnapshotInterval, long intervalCompressionMultiplier) {
531         synchronized (mOnDiskLock) {
532             synchronized (mInMemoryLock) {
533                 // NOTE: We allow this call if persistence is not initialized as
534                 // it is a part of the persistence initialization process.
535                 boolean resampleHistory = false;
536                 Slog.i(LOG_TAG, "New history parameters: mode:"
537                         + AppOpsManager.historicalModeToString(mode) + " baseSnapshotInterval:"
538                         + baseSnapshotInterval + " intervalCompressionMultiplier:"
539                         + intervalCompressionMultiplier);
540                 if (mMode != mode) {
541                     mMode = mode;
542                     if (mMode == AppOpsManager.HISTORICAL_MODE_DISABLED) {
543                         clearHistoryOnDiskDLocked();
544                     }
545                     if (mMode == AppOpsManager.HISTORICAL_MODE_ENABLED_PASSIVE) {
546                         mDiscreteRegistry.setDebugMode(true);
547                     }
548                 }
549                 if (mBaseSnapshotInterval != baseSnapshotInterval) {
550                     mBaseSnapshotInterval = baseSnapshotInterval;
551                     resampleHistory = true;
552                 }
553                 if (mIntervalCompressionMultiplier != intervalCompressionMultiplier) {
554                     mIntervalCompressionMultiplier = intervalCompressionMultiplier;
555                     resampleHistory = true;
556                 }
557                 if (resampleHistory) {
558                     resampleHistoryOnDiskInMemoryDMLocked(0);
559                 }
560             }
561         }
562     }
563 
offsetHistory(long offsetMillis)564     void offsetHistory(long offsetMillis) {
565         synchronized (mOnDiskLock) {
566             synchronized (mInMemoryLock) {
567                 if (!isPersistenceInitializedMLocked()) {
568                     Slog.e(LOG_TAG, "Interaction before persistence initialized");
569                     return;
570                 }
571             }
572             final List<HistoricalOps> history = mPersistence.readHistoryDLocked();
573             clearHistoricalRegistry();
574             if (history != null) {
575                 final int historySize = history.size();
576                 for (int i = 0; i < historySize; i++) {
577                     final HistoricalOps ops = history.get(i);
578                     ops.offsetBeginAndEndTime(offsetMillis);
579                 }
580                 if (offsetMillis < 0) {
581                     pruneFutureOps(history);
582                 }
583                 mPersistence.persistHistoricalOpsDLocked(history);
584             }
585         }
586     }
587 
offsetDiscreteHistory(long offsetMillis)588     void offsetDiscreteHistory(long offsetMillis) {
589         mDiscreteRegistry.offsetHistory(offsetMillis);
590     }
591 
addHistoricalOps(HistoricalOps ops)592     void addHistoricalOps(HistoricalOps ops) {
593         final List<HistoricalOps> pendingWrites;
594         synchronized (mInMemoryLock) {
595             if (!isPersistenceInitializedMLocked()) {
596                 Slog.d(LOG_TAG, "Interaction before persistence initialized");
597                 return;
598             }
599             // The history files start from mBaseSnapshotInterval - take this into account.
600             ops.offsetBeginAndEndTime(mBaseSnapshotInterval);
601             mPendingWrites.offerFirst(ops);
602             pendingWrites = new ArrayList<>(mPendingWrites);
603             mPendingWrites.clear();
604         }
605         persistPendingHistory(pendingWrites);
606     }
607 
resampleHistoryOnDiskInMemoryDMLocked(long offsetMillis)608     private void resampleHistoryOnDiskInMemoryDMLocked(long offsetMillis) {
609         mPersistence = new Persistence(mBaseSnapshotInterval, mIntervalCompressionMultiplier);
610         offsetHistory(offsetMillis);
611     }
612 
resetHistoryParameters()613     void resetHistoryParameters() {
614         if (!isPersistenceInitializedMLocked()) {
615             Slog.d(LOG_TAG, "Interaction before persistence initialized");
616             return;
617         }
618         setHistoryParameters(DEFAULT_MODE, DEFAULT_SNAPSHOT_INTERVAL_MILLIS,
619                 DEFAULT_COMPRESSION_STEP);
620         mDiscreteRegistry.setDebugMode(false);
621     }
622 
clearHistory(int uid, String packageName)623     void clearHistory(int uid, String packageName) {
624         synchronized (mOnDiskLock) {
625             synchronized (mInMemoryLock) {
626                 if (!isPersistenceInitializedMLocked()) {
627                     Slog.d(LOG_TAG, "Interaction before persistence initialized");
628                     return;
629                 }
630                 if (mMode != AppOpsManager.HISTORICAL_MODE_ENABLED_ACTIVE) {
631                     return;
632                 }
633 
634                 for (int index = 0; index < mPendingWrites.size(); index++) {
635                     mPendingWrites.get(index).clearHistory(uid, packageName);
636                 }
637 
638                 getUpdatedPendingHistoricalOpsMLocked(System.currentTimeMillis())
639                         .clearHistory(uid, packageName);
640 
641                 mPersistence.clearHistoryDLocked(uid, packageName);
642             }
643         }
644         mDiscreteRegistry.clearHistory(uid, packageName);
645     }
646 
writeAndClearDiscreteHistory()647     void writeAndClearDiscreteHistory() {
648         mDiscreteRegistry.writeAndClearAccessHistory();
649     }
650 
clearAllHistory()651     void clearAllHistory() {
652         clearHistoricalRegistry();
653         mDiscreteRegistry.clearHistory();
654     }
655 
clearHistoricalRegistry()656     void clearHistoricalRegistry() {
657         synchronized (mOnDiskLock) {
658             synchronized (mInMemoryLock) {
659                 if (!isPersistenceInitializedMLocked()) {
660                     Slog.d(LOG_TAG, "Interaction before persistence initialized");
661                     return;
662                 }
663                 clearHistoryOnDiskDLocked();
664                 mNextPersistDueTimeMillis = 0;
665                 mPendingHistoryOffsetMillis = 0;
666                 mCurrentHistoricalOps = null;
667             }
668         }
669     }
670 
clearHistoryOnDiskDLocked()671     private void clearHistoryOnDiskDLocked() {
672         IoThread.getHandler().removeMessages(MSG_WRITE_PENDING_HISTORY);
673         synchronized (mInMemoryLock) {
674             mCurrentHistoricalOps = null;
675             mNextPersistDueTimeMillis = System.currentTimeMillis();
676             mPendingWrites.clear();
677         }
678         Persistence.clearHistoryDLocked();
679     }
680 
getUpdatedPendingHistoricalOpsMLocked(long now)681     private @NonNull HistoricalOps getUpdatedPendingHistoricalOpsMLocked(long now) {
682         if (mCurrentHistoricalOps != null) {
683             final long remainingTimeMillis = mNextPersistDueTimeMillis - now;
684             if (remainingTimeMillis > mBaseSnapshotInterval) {
685                 // If time went backwards we need to push history to the future with the
686                 // overflow over our snapshot interval. If time went forward do nothing
687                 // as we would naturally push history into the past on the next write.
688                 mPendingHistoryOffsetMillis = remainingTimeMillis - mBaseSnapshotInterval;
689             }
690             final long elapsedTimeMillis = mBaseSnapshotInterval - remainingTimeMillis;
691             mCurrentHistoricalOps.setEndTime(elapsedTimeMillis);
692             if (remainingTimeMillis > 0) {
693                 if (DEBUG) {
694                     Slog.i(LOG_TAG, "Returning current in-memory state");
695                 }
696                 return mCurrentHistoricalOps;
697             }
698             if (mCurrentHistoricalOps.isEmpty()) {
699                 mCurrentHistoricalOps.setBeginAndEndTime(0, 0);
700                 mNextPersistDueTimeMillis = now + mBaseSnapshotInterval;
701                 return mCurrentHistoricalOps;
702             }
703             // The current batch is full, so persist taking into account overdue persist time.
704             mCurrentHistoricalOps.offsetBeginAndEndTime(mBaseSnapshotInterval);
705             mCurrentHistoricalOps.setBeginTime(mCurrentHistoricalOps.getEndTimeMillis()
706                     - mBaseSnapshotInterval);
707             final long overdueTimeMillis = Math.abs(remainingTimeMillis);
708             mCurrentHistoricalOps.offsetBeginAndEndTime(overdueTimeMillis);
709             schedulePersistHistoricalOpsMLocked(mCurrentHistoricalOps);
710         }
711         // The current batch is in the future, i.e. not complete yet.
712         mCurrentHistoricalOps = new HistoricalOps(0, 0);
713         mNextPersistDueTimeMillis = now + mBaseSnapshotInterval;
714         if (DEBUG) {
715             Slog.i(LOG_TAG, "Returning new in-memory state");
716         }
717         return mCurrentHistoricalOps;
718     }
719 
shutdown()720     void shutdown() {
721         synchronized (mInMemoryLock) {
722             if (mMode == AppOpsManager.HISTORICAL_MODE_DISABLED) {
723                 return;
724             }
725         }
726         // Do not call persistPendingHistory inside the memory lock, due to possible deadlock
727         persistPendingHistory();
728     }
729 
persistPendingHistory()730     void persistPendingHistory() {
731         final List<HistoricalOps> pendingWrites;
732         synchronized (mOnDiskLock) {
733             synchronized (mInMemoryLock) {
734                 pendingWrites = new ArrayList<>(mPendingWrites);
735                 mPendingWrites.clear();
736                 if (mPendingHistoryOffsetMillis != 0) {
737                     resampleHistoryOnDiskInMemoryDMLocked(mPendingHistoryOffsetMillis);
738                     mPendingHistoryOffsetMillis = 0;
739                 }
740             }
741             persistPendingHistory(pendingWrites);
742         }
743         mDiscreteRegistry.writeAndClearAccessHistory();
744     }
745 
persistPendingHistory(@onNull List<HistoricalOps> pendingWrites)746     private void persistPendingHistory(@NonNull List<HistoricalOps> pendingWrites) {
747         synchronized (mOnDiskLock) {
748             IoThread.getHandler().removeMessages(MSG_WRITE_PENDING_HISTORY);
749             if (pendingWrites.isEmpty()) {
750                 return;
751             }
752             final int opCount = pendingWrites.size();
753             // Pending writes are offset relative to each other, so take this
754             // into account to persist everything in one shot - single write.
755             for (int i = 0; i < opCount; i++) {
756                 final HistoricalOps current = pendingWrites.get(i);
757                 if (i > 0) {
758                     final HistoricalOps previous = pendingWrites.get(i - 1);
759                     current.offsetBeginAndEndTime(previous.getBeginTimeMillis());
760                 }
761             }
762             mPersistence.persistHistoricalOpsDLocked(pendingWrites);
763         }
764     }
765 
schedulePersistHistoricalOpsMLocked(@onNull HistoricalOps ops)766     private void schedulePersistHistoricalOpsMLocked(@NonNull HistoricalOps ops) {
767         final Message message = PooledLambda.obtainMessage(
768                 HistoricalRegistry::persistPendingHistory, HistoricalRegistry.this);
769         message.what = MSG_WRITE_PENDING_HISTORY;
770         IoThread.getHandler().sendMessage(message);
771         mPendingWrites.offerFirst(ops);
772     }
773 
makeRelativeToEpochStart(@onNull HistoricalOps ops, long nowMillis)774     private static void makeRelativeToEpochStart(@NonNull HistoricalOps ops, long nowMillis) {
775         ops.setBeginAndEndTime(nowMillis - ops.getEndTimeMillis(),
776                 nowMillis- ops.getBeginTimeMillis());
777     }
778 
pruneFutureOps(@onNull List<HistoricalOps> ops)779     private void pruneFutureOps(@NonNull List<HistoricalOps> ops) {
780         final int opCount = ops.size();
781         for (int i = opCount - 1; i >= 0; i--) {
782             final HistoricalOps op = ops.get(i);
783             if (op.getEndTimeMillis() <= mBaseSnapshotInterval) {
784                 ops.remove(i);
785             } else if (op.getBeginTimeMillis() < mBaseSnapshotInterval) {
786                 final double filterScale = (double) (op.getEndTimeMillis() - mBaseSnapshotInterval)
787                         / (double) op.getDurationMillis();
788                 Persistence.spliceFromBeginning(op, filterScale);
789             }
790         }
791     }
792 
793     private static final class Persistence {
794         private static final boolean DEBUG = false;
795 
796         private static final String LOG_TAG = Persistence.class.getSimpleName();
797 
798         private static final String TAG_HISTORY = "history";
799         private static final String TAG_OPS = "ops";
800         private static final String TAG_UID = "uid";
801         private static final String TAG_PACKAGE = "pkg";
802         private static final String TAG_ATTRIBUTION = "ftr";
803         private static final String TAG_OP = "op";
804         private static final String TAG_STATE = "st";
805 
806         private static final String ATTR_VERSION = "ver";
807         private static final String ATTR_NAME = "na";
808         private static final String ATTR_ACCESS_COUNT = "ac";
809         private static final String ATTR_REJECT_COUNT = "rc";
810         private static final String ATTR_ACCESS_DURATION = "du";
811         private static final String ATTR_BEGIN_TIME = "beg";
812         private static final String ATTR_END_TIME = "end";
813         private static final String ATTR_OVERFLOW = "ov";
814 
815         private static final int CURRENT_VERSION = 2;
816 
817         private final long mBaseSnapshotInterval;
818         private final long mIntervalCompressionMultiplier;
819 
Persistence(long baseSnapshotInterval, long intervalCompressionMultiplier)820         Persistence(long baseSnapshotInterval, long intervalCompressionMultiplier) {
821             mBaseSnapshotInterval = baseSnapshotInterval;
822             mIntervalCompressionMultiplier = intervalCompressionMultiplier;
823         }
824 
825         private static final AtomicDirectory sHistoricalAppOpsDir = new AtomicDirectory(
826                 new File(new File(Environment.getDataSystemDirectory(), "appops"), "history"));
827 
generateFile(@onNull File baseDir, int depth)828         private File generateFile(@NonNull File baseDir, int depth) {
829             final long globalBeginMillis = computeGlobalIntervalBeginMillis(depth);
830             return new File(baseDir, Long.toString(globalBeginMillis) + HISTORY_FILE_SUFFIX);
831         }
832 
clearHistoryDLocked(int uid, String packageName)833         void clearHistoryDLocked(int uid, String packageName) {
834             List<HistoricalOps> historicalOps = readHistoryDLocked();
835 
836             if (historicalOps == null) {
837                 return;
838             }
839 
840             for (int index = 0; index < historicalOps.size(); index++) {
841                 historicalOps.get(index).clearHistory(uid, packageName);
842             }
843 
844             clearHistoryDLocked();
845 
846             persistHistoricalOpsDLocked(historicalOps);
847         }
848 
clearHistoryDLocked()849         static void clearHistoryDLocked() {
850             sHistoricalAppOpsDir.delete();
851         }
852 
persistHistoricalOpsDLocked(@onNull List<HistoricalOps> ops)853         void persistHistoricalOpsDLocked(@NonNull List<HistoricalOps> ops) {
854             if (DEBUG) {
855                 Slog.i(LOG_TAG, "Persisting ops:\n" + opsToDebugString(ops));
856                 enforceOpsWellFormed(ops);
857             }
858             try {
859                 final File newBaseDir = sHistoricalAppOpsDir.startWrite();
860                 final File oldBaseDir = sHistoricalAppOpsDir.getBackupDirectory();
861                 final HistoricalFilesInvariant filesInvariant;
862                 if (DEBUG) {
863                     filesInvariant = new HistoricalFilesInvariant();
864                     filesInvariant.startTracking(oldBaseDir);
865                 }
866                 final Set<String> oldFileNames = getHistoricalFileNames(oldBaseDir);
867                 handlePersistHistoricalOpsRecursiveDLocked(newBaseDir, oldBaseDir, ops,
868                         oldFileNames,  0);
869                 if (DEBUG) {
870                     filesInvariant.stopTracking(newBaseDir);
871                 }
872                 sHistoricalAppOpsDir.finishWrite();
873             } catch (Throwable t) {
874                 wtf("Failed to write historical app ops, restoring backup", t, null);
875                 sHistoricalAppOpsDir.failWrite();
876             }
877         }
878 
readHistoryRawDLocked()879         @Nullable List<HistoricalOps> readHistoryRawDLocked() {
880             return collectHistoricalOpsBaseDLocked(Process.INVALID_UID /*filterUid*/,
881                     null /*filterPackageName*/, null /*filterAttributionTag*/,
882                     null /*filterOpNames*/, 0 /*filter*/, 0 /*filterBeginTimeMills*/,
883                     Long.MAX_VALUE /*filterEndTimeMills*/, AppOpsManager.OP_FLAGS_ALL);
884         }
885 
readHistoryDLocked()886         @Nullable List<HistoricalOps> readHistoryDLocked() {
887             final List<HistoricalOps> result = readHistoryRawDLocked();
888             // Take into account in memory state duration.
889             if (result != null) {
890                 final int opCount = result.size();
891                 for (int i = 0; i < opCount; i++) {
892                     result.get(i).offsetBeginAndEndTime(mBaseSnapshotInterval);
893                 }
894             }
895             return result;
896         }
897 
getLastPersistTimeMillisDLocked()898         long getLastPersistTimeMillisDLocked() {
899             File baseDir = null;
900             try {
901                 baseDir = sHistoricalAppOpsDir.startRead();
902                 final File[] files = baseDir.listFiles();
903                 if (files != null && files.length > 0) {
904                     File shortestFile = null;
905                     for (File candidate : files) {
906                         final String candidateName = candidate.getName();
907                         if (!candidateName.endsWith(HISTORY_FILE_SUFFIX)) {
908                             continue;
909                         }
910                         if (shortestFile == null) {
911                             shortestFile = candidate;
912                         } else if (candidateName.length() < shortestFile.getName().length()) {
913                             shortestFile = candidate;
914                         }
915                     }
916                     if (shortestFile == null) {
917                         return 0;
918                     }
919                     return shortestFile.lastModified();
920                 }
921                 sHistoricalAppOpsDir.finishRead();
922             } catch (Throwable e) {
923                 wtf("Error reading historical app ops. Deleting history.", e, baseDir);
924                 sHistoricalAppOpsDir.delete();
925             }
926             return 0;
927         }
928 
collectHistoricalOpsDLocked(@onNull HistoricalOps currentOps, int filterUid, @Nullable String filterPackageName, @Nullable String filterAttributionTag, @Nullable String[] filterOpNames, @HistoricalOpsRequestFilter int filter, long filterBeingMillis, long filterEndMillis, @OpFlags int filterFlags)929         private void collectHistoricalOpsDLocked(@NonNull HistoricalOps currentOps, int filterUid,
930                 @Nullable String filterPackageName, @Nullable String filterAttributionTag,
931                 @Nullable String[] filterOpNames, @HistoricalOpsRequestFilter int filter,
932                 long filterBeingMillis, long filterEndMillis, @OpFlags int filterFlags) {
933             final List<HistoricalOps> readOps = collectHistoricalOpsBaseDLocked(filterUid,
934                     filterPackageName, filterAttributionTag, filterOpNames, filter,
935                     filterBeingMillis, filterEndMillis, filterFlags);
936             if (readOps != null) {
937                 final int readCount = readOps.size();
938                 for (int i = 0; i < readCount; i++) {
939                     final HistoricalOps readOp = readOps.get(i);
940                     currentOps.merge(readOp);
941                 }
942              }
943         }
944 
collectHistoricalOpsBaseDLocked(int filterUid, @Nullable String filterPackageName, @Nullable String filterAttributionTag, @Nullable String[] filterOpNames, @HistoricalOpsRequestFilter int filter, long filterBeginTimeMillis, long filterEndTimeMillis, @OpFlags int filterFlags)945         private @Nullable LinkedList<HistoricalOps> collectHistoricalOpsBaseDLocked(int filterUid,
946                 @Nullable String filterPackageName, @Nullable String filterAttributionTag,
947                 @Nullable String[] filterOpNames, @HistoricalOpsRequestFilter int filter,
948                 long filterBeginTimeMillis, long filterEndTimeMillis, @OpFlags int filterFlags) {
949             File baseDir = null;
950             try {
951                 baseDir = sHistoricalAppOpsDir.startRead();
952                 final HistoricalFilesInvariant filesInvariant;
953                 if (DEBUG) {
954                     filesInvariant = new HistoricalFilesInvariant();
955                     filesInvariant.startTracking(baseDir);
956                 }
957                 final Set<String> historyFiles = getHistoricalFileNames(baseDir);
958                 final long[] globalContentOffsetMillis = {0};
959                 final LinkedList<HistoricalOps> ops = collectHistoricalOpsRecursiveDLocked(
960                         baseDir, filterUid, filterPackageName, filterAttributionTag, filterOpNames,
961                         filter, filterBeginTimeMillis, filterEndTimeMillis, filterFlags,
962                         globalContentOffsetMillis, null /*outOps*/, 0 /*depth*/, historyFiles);
963                 if (DEBUG) {
964                     filesInvariant.stopTracking(baseDir);
965                 }
966                 sHistoricalAppOpsDir.finishRead();
967                 return ops;
968             } catch (Throwable t) {
969                 wtf("Error reading historical app ops. Deleting history.", t, baseDir);
970                 sHistoricalAppOpsDir.delete();
971             }
972             return null;
973         }
974 
collectHistoricalOpsRecursiveDLocked( @onNull File baseDir, int filterUid, @Nullable String filterPackageName, @Nullable String filterAttributionTag, @Nullable String[] filterOpNames, @HistoricalOpsRequestFilter int filter, long filterBeginTimeMillis, long filterEndTimeMillis, @OpFlags int filterFlags, @NonNull long[] globalContentOffsetMillis, @Nullable LinkedList<HistoricalOps> outOps, int depth, @NonNull Set<String> historyFiles)975         private @Nullable LinkedList<HistoricalOps> collectHistoricalOpsRecursiveDLocked(
976                 @NonNull File baseDir, int filterUid, @Nullable String filterPackageName,
977                 @Nullable String filterAttributionTag, @Nullable String[] filterOpNames,
978                 @HistoricalOpsRequestFilter int filter, long filterBeginTimeMillis,
979                 long filterEndTimeMillis, @OpFlags int filterFlags,
980                 @NonNull long[] globalContentOffsetMillis,
981                 @Nullable LinkedList<HistoricalOps> outOps, int depth,
982                 @NonNull Set<String> historyFiles)
983                 throws IOException, XmlPullParserException {
984             final long previousIntervalEndMillis = (long) Math.pow(mIntervalCompressionMultiplier,
985                     depth) * mBaseSnapshotInterval;
986             final long currentIntervalEndMillis = (long) Math.pow(mIntervalCompressionMultiplier,
987                     depth + 1) * mBaseSnapshotInterval;
988 
989             filterBeginTimeMillis = Math.max(filterBeginTimeMillis - previousIntervalEndMillis, 0);
990             filterEndTimeMillis = filterEndTimeMillis - previousIntervalEndMillis;
991 
992             // Read historical data at this level
993             final List<HistoricalOps> readOps = readHistoricalOpsLocked(baseDir,
994                     previousIntervalEndMillis, currentIntervalEndMillis, filterUid,
995                     filterPackageName, filterAttributionTag, filterOpNames, filter,
996                     filterBeginTimeMillis, filterEndTimeMillis, filterFlags,
997                     globalContentOffsetMillis, depth, historyFiles);
998             // Empty is a special signal to stop diving
999             if (readOps != null && readOps.isEmpty()) {
1000                 return outOps;
1001             }
1002 
1003             // Collect older historical data from subsequent levels
1004             outOps = collectHistoricalOpsRecursiveDLocked(baseDir, filterUid, filterPackageName,
1005                     filterAttributionTag, filterOpNames, filter, filterBeginTimeMillis,
1006                     filterEndTimeMillis, filterFlags, globalContentOffsetMillis, outOps, depth + 1,
1007                     historyFiles);
1008 
1009             // Make older historical data relative to the current historical level
1010             if (outOps != null) {
1011                 final int opCount = outOps.size();
1012                 for (int i = 0; i < opCount; i++) {
1013                     final HistoricalOps collectedOp = outOps.get(i);
1014                     collectedOp.offsetBeginAndEndTime(currentIntervalEndMillis);
1015                 }
1016             }
1017 
1018             if (readOps != null) {
1019                 if (outOps == null) {
1020                     outOps = new LinkedList<>();
1021                 }
1022                 // Add the read ops to output
1023                 final int opCount = readOps.size();
1024                 for (int i = opCount - 1; i >= 0; i--) {
1025                     outOps.offerFirst(readOps.get(i));
1026                 }
1027             }
1028 
1029             return outOps;
1030         }
1031 
handlePersistHistoricalOpsRecursiveDLocked(@onNull File newBaseDir, @NonNull File oldBaseDir, @Nullable List<HistoricalOps> passedOps, @NonNull Set<String> oldFileNames, int depth)1032         private void handlePersistHistoricalOpsRecursiveDLocked(@NonNull File newBaseDir,
1033                 @NonNull File oldBaseDir, @Nullable List<HistoricalOps> passedOps,
1034                 @NonNull Set<String> oldFileNames, int depth)
1035                 throws IOException, XmlPullParserException {
1036             final long previousIntervalEndMillis = (long) Math.pow(mIntervalCompressionMultiplier,
1037                     depth) * mBaseSnapshotInterval;
1038             final long currentIntervalEndMillis = (long) Math.pow(mIntervalCompressionMultiplier,
1039                     depth + 1) * mBaseSnapshotInterval;
1040 
1041             if (passedOps == null || passedOps.isEmpty()) {
1042                 if (!oldFileNames.isEmpty()) {
1043                     // If there is an old file we need to copy it over to the new state.
1044                     final File oldFile = generateFile(oldBaseDir, depth);
1045                     if (oldFileNames.remove(oldFile.getName())) {
1046                         final File newFile = generateFile(newBaseDir, depth);
1047                         Files.createLink(newFile.toPath(), oldFile.toPath());
1048                     }
1049                     handlePersistHistoricalOpsRecursiveDLocked(newBaseDir, oldBaseDir,
1050                             passedOps, oldFileNames, depth + 1);
1051                 }
1052                 return;
1053             }
1054 
1055             if (DEBUG) {
1056                 enforceOpsWellFormed(passedOps);
1057             }
1058 
1059             // Normalize passed ops time to be based off this interval start
1060             final int passedOpCount = passedOps.size();
1061             for (int i = 0; i < passedOpCount; i++) {
1062                 final HistoricalOps passedOp = passedOps.get(i);
1063                 passedOp.offsetBeginAndEndTime(-previousIntervalEndMillis);
1064             }
1065 
1066             if (DEBUG) {
1067                 enforceOpsWellFormed(passedOps);
1068             }
1069 
1070             // Read persisted ops for this interval
1071             final List<HistoricalOps> existingOps = readHistoricalOpsLocked(oldBaseDir,
1072                     previousIntervalEndMillis, currentIntervalEndMillis,
1073                     Process.INVALID_UID /*filterUid*/, null /*filterPackageName*/,
1074                     null /*filterAttributionTag*/, null /*filterOpNames*/, 0 /*filter*/,
1075                     Long.MIN_VALUE /*filterBeginTimeMillis*/,
1076                     Long.MAX_VALUE /*filterEndTimeMillis*/, AppOpsManager.OP_FLAGS_ALL, null, depth,
1077                     null /*historyFiles*/);
1078             if (DEBUG) {
1079                 enforceOpsWellFormed(existingOps);
1080             }
1081 
1082             // Offset existing ops to account for elapsed time
1083             if (existingOps != null) {
1084                 final int existingOpCount = existingOps.size();
1085                 if (existingOpCount > 0) {
1086                     // Compute elapsed time
1087                     final long elapsedTimeMillis = passedOps.get(passedOps.size() - 1)
1088                         .getEndTimeMillis();
1089                     for (int i = 0; i < existingOpCount; i++) {
1090                         final HistoricalOps existingOp = existingOps.get(i);
1091                         existingOp.offsetBeginAndEndTime(elapsedTimeMillis);
1092                     }
1093                 }
1094             }
1095 
1096             if (DEBUG) {
1097                 enforceOpsWellFormed(existingOps);
1098             }
1099 
1100             final long slotDurationMillis = previousIntervalEndMillis;
1101 
1102             // Consolidate passed ops at the current slot duration ensuring each snapshot is
1103             // full. To achieve this we put all passed and existing ops in a list and will
1104             // merge them to ensure each represents a snapshot at the current granularity.
1105             final List<HistoricalOps> allOps = new LinkedList<>(passedOps);
1106             if (existingOps != null) {
1107                 allOps.addAll(existingOps);
1108             }
1109 
1110             if (DEBUG) {
1111                 enforceOpsWellFormed(allOps);
1112             }
1113 
1114             // Compute ops to persist and overflow ops
1115             List<HistoricalOps> persistedOps = null;
1116             List<HistoricalOps> overflowedOps = null;
1117 
1118             // We move a snapshot into the next level only if the start time is
1119             // after the end of the current interval. This avoids rewriting all
1120             // files to propagate the information added to the history on every
1121             // iteration. Instead, we would rewrite the next level file only if
1122             // an entire snapshot from the previous level is being propagated.
1123             // The trade off is that we need to store how much the last snapshot
1124             // of the current interval overflows past the interval end. We write
1125             // the overflow data to avoid parsing all snapshots on query.
1126             long intervalOverflowMillis = 0;
1127             final int opCount = allOps.size();
1128             for (int i = 0; i < opCount; i++) {
1129                 final HistoricalOps op = allOps.get(i);
1130                 final HistoricalOps persistedOp;
1131                 final HistoricalOps overflowedOp;
1132                 if (op.getEndTimeMillis() <= currentIntervalEndMillis) {
1133                     persistedOp = op;
1134                     overflowedOp = null;
1135                 } else if (op.getBeginTimeMillis() < currentIntervalEndMillis) {
1136                     persistedOp = op;
1137                     intervalOverflowMillis = op.getEndTimeMillis() - currentIntervalEndMillis;
1138                     if (intervalOverflowMillis > previousIntervalEndMillis) {
1139                         final double splitScale = (double) intervalOverflowMillis
1140                                 / op.getDurationMillis();
1141                         overflowedOp = spliceFromEnd(op, splitScale);
1142                         intervalOverflowMillis = op.getEndTimeMillis() - currentIntervalEndMillis;
1143                     } else {
1144                         overflowedOp = null;
1145                     }
1146                 } else {
1147                     persistedOp = null;
1148                     overflowedOp = op;
1149                 }
1150                 if (persistedOp != null) {
1151                     if (persistedOps == null) {
1152                         persistedOps = new ArrayList<>();
1153                     }
1154                     persistedOps.add(persistedOp);
1155                 }
1156                 if (overflowedOp != null) {
1157                     if (overflowedOps == null) {
1158                         overflowedOps = new ArrayList<>();
1159                     }
1160                     overflowedOps.add(overflowedOp);
1161                 }
1162             }
1163 
1164             if (DEBUG) {
1165                 enforceOpsWellFormed(persistedOps);
1166                 enforceOpsWellFormed(overflowedOps);
1167             }
1168 
1169             final File newFile = generateFile(newBaseDir, depth);
1170             oldFileNames.remove(newFile.getName());
1171 
1172             if (persistedOps != null) {
1173                 normalizeSnapshotForSlotDuration(persistedOps, slotDurationMillis);
1174                 writeHistoricalOpsDLocked(persistedOps, intervalOverflowMillis, newFile);
1175                 if (DEBUG) {
1176                     Slog.i(LOG_TAG, "Persisted at depth: " + depth + " file: " + newFile
1177                             + " ops:\n" + opsToDebugString(persistedOps));
1178                     enforceOpsWellFormed(persistedOps);
1179                 }
1180             }
1181 
1182             handlePersistHistoricalOpsRecursiveDLocked(newBaseDir, oldBaseDir,
1183                     overflowedOps, oldFileNames, depth + 1);
1184         }
1185 
readHistoricalOpsLocked(File baseDir, long intervalBeginMillis, long intervalEndMillis, int filterUid, @Nullable String filterPackageName, @Nullable String filterAttributionTag, @Nullable String[] filterOpNames, @HistoricalOpsRequestFilter int filter, long filterBeginTimeMillis, long filterEndTimeMillis, @OpFlags int filterFlags, @Nullable long[] cumulativeOverflowMillis, int depth, @NonNull Set<String> historyFiles)1186         private @Nullable List<HistoricalOps> readHistoricalOpsLocked(File baseDir,
1187                 long intervalBeginMillis, long intervalEndMillis, int filterUid,
1188                 @Nullable String filterPackageName, @Nullable String filterAttributionTag,
1189                 @Nullable String[] filterOpNames, @HistoricalOpsRequestFilter int filter,
1190                 long filterBeginTimeMillis, long filterEndTimeMillis, @OpFlags int filterFlags,
1191                 @Nullable long[] cumulativeOverflowMillis, int depth,
1192                 @NonNull Set<String> historyFiles)
1193                 throws IOException, XmlPullParserException {
1194             final File file = generateFile(baseDir, depth);
1195             if (historyFiles != null) {
1196                 historyFiles.remove(file.getName());
1197             }
1198             if (filterBeginTimeMillis >= filterEndTimeMillis
1199                     || filterEndTimeMillis < intervalBeginMillis) {
1200                 // Don't go deeper
1201                 return Collections.emptyList();
1202             }
1203             if (filterBeginTimeMillis >= (intervalEndMillis
1204                     + ((intervalEndMillis - intervalBeginMillis) / mIntervalCompressionMultiplier)
1205                     + (cumulativeOverflowMillis != null ? cumulativeOverflowMillis[0] : 0))
1206                     || !file.exists()) {
1207                 if (historyFiles == null || historyFiles.isEmpty()) {
1208                     // Don't go deeper
1209                     return Collections.emptyList();
1210                 } else {
1211                     // Keep diving
1212                     return null;
1213                 }
1214             }
1215             return readHistoricalOpsLocked(file, filterUid, filterPackageName, filterAttributionTag,
1216                     filterOpNames, filter, filterBeginTimeMillis, filterEndTimeMillis, filterFlags,
1217                     cumulativeOverflowMillis);
1218         }
1219 
readHistoricalOpsLocked(@onNull File file, int filterUid, @Nullable String filterPackageName, @Nullable String filterAttributionTag, @Nullable String[] filterOpNames, @HistoricalOpsRequestFilter int filter, long filterBeginTimeMillis, long filterEndTimeMillis, @OpFlags int filterFlags, @Nullable long[] cumulativeOverflowMillis)1220         private @Nullable  List<HistoricalOps> readHistoricalOpsLocked(@NonNull File file,
1221                 int filterUid, @Nullable String filterPackageName,
1222                 @Nullable String filterAttributionTag, @Nullable String[] filterOpNames,
1223                 @HistoricalOpsRequestFilter int filter, long filterBeginTimeMillis,
1224                 long filterEndTimeMillis, @OpFlags int filterFlags,
1225                 @Nullable long[] cumulativeOverflowMillis)
1226                 throws IOException, XmlPullParserException {
1227             if (DEBUG) {
1228                 Slog.i(LOG_TAG, "Reading ops from:" + file);
1229             }
1230             List<HistoricalOps> allOps = null;
1231             try (FileInputStream stream = new FileInputStream(file)) {
1232                 final TypedXmlPullParser parser = Xml.resolvePullParser(stream);
1233                 XmlUtils.beginDocument(parser, TAG_HISTORY);
1234 
1235                 // We haven't released version 1 and have more detailed
1236                 // accounting - just nuke the current state
1237                 final int version = parser.getAttributeInt(null, ATTR_VERSION);
1238                 if (CURRENT_VERSION == 2 && version < CURRENT_VERSION) {
1239                     throw new IllegalStateException("Dropping unsupported history "
1240                             + "version 1 for file:" + file);
1241                 }
1242 
1243                 final long overflowMillis = parser.getAttributeLong(null, ATTR_OVERFLOW, 0);
1244                 final int depth = parser.getDepth();
1245                 while (XmlUtils.nextElementWithin(parser, depth)) {
1246                     if (TAG_OPS.equals(parser.getName())) {
1247                         final HistoricalOps ops = readeHistoricalOpsDLocked(parser, filterUid,
1248                                 filterPackageName, filterAttributionTag, filterOpNames, filter,
1249                                 filterBeginTimeMillis, filterEndTimeMillis, filterFlags,
1250                                 cumulativeOverflowMillis);
1251                         if (ops == null) {
1252                             continue;
1253                         }
1254                         if (ops.isEmpty()) {
1255                             XmlUtils.skipCurrentTag(parser);
1256                             continue;
1257                         }
1258                         if (allOps == null) {
1259                             allOps = new ArrayList<>();
1260                         }
1261                         allOps.add(ops);
1262                     }
1263                 }
1264                 if (cumulativeOverflowMillis != null) {
1265                     cumulativeOverflowMillis[0] += overflowMillis;
1266                 }
1267             } catch (FileNotFoundException e) {
1268                 Slog.i(LOG_TAG, "No history file: " + file.getName());
1269                 return Collections.emptyList();
1270             }
1271             if (DEBUG) {
1272                 if (allOps != null) {
1273                     Slog.i(LOG_TAG, "Read from file: " + file + " ops:\n"
1274                             + opsToDebugString(allOps));
1275                     enforceOpsWellFormed(allOps);
1276                 }
1277             }
1278             return allOps;
1279         }
1280 
readeHistoricalOpsDLocked( @onNull TypedXmlPullParser parser, int filterUid, @Nullable String filterPackageName, @Nullable String filterAttributionTag, @Nullable String[] filterOpNames, @HistoricalOpsRequestFilter int filter, long filterBeginTimeMillis, long filterEndTimeMillis, @OpFlags int filterFlags, @Nullable long[] cumulativeOverflowMillis)1281         private @Nullable HistoricalOps readeHistoricalOpsDLocked(
1282                 @NonNull TypedXmlPullParser parser, int filterUid,
1283                 @Nullable String filterPackageName,
1284                 @Nullable String filterAttributionTag, @Nullable String[] filterOpNames,
1285                 @HistoricalOpsRequestFilter int filter, long filterBeginTimeMillis,
1286                 long filterEndTimeMillis, @OpFlags int filterFlags,
1287                 @Nullable long[] cumulativeOverflowMillis)
1288                 throws IOException, XmlPullParserException {
1289             final long beginTimeMillis = parser.getAttributeLong(null, ATTR_BEGIN_TIME, 0)
1290                     + (cumulativeOverflowMillis != null ? cumulativeOverflowMillis[0] : 0);
1291             final long endTimeMillis = parser.getAttributeLong(null, ATTR_END_TIME, 0)
1292                     + (cumulativeOverflowMillis != null ? cumulativeOverflowMillis[0] : 0);
1293             // Keep reading as subsequent records may start matching
1294             if (filterEndTimeMillis < beginTimeMillis) {
1295                 return null;
1296             }
1297             // Stop reading as subsequent records will not match
1298             if (filterBeginTimeMillis > endTimeMillis) {
1299                 return new HistoricalOps(0, 0);
1300             }
1301             final long filteredBeginTimeMillis = Math.max(beginTimeMillis, filterBeginTimeMillis);
1302             final long filteredEndTimeMillis = Math.min(endTimeMillis, filterEndTimeMillis);
1303             // // Keep reading as subsequent records may start matching
1304             // if (filteredEndTimeMillis - filterBeginTimeMillis <= 0) {
1305             //     return null;
1306             // }
1307             final double filterScale = (double) (filteredEndTimeMillis - filteredBeginTimeMillis)
1308                     / (double) (endTimeMillis - beginTimeMillis);
1309             HistoricalOps ops = null;
1310             final int depth = parser.getDepth();
1311             while (XmlUtils.nextElementWithin(parser, depth)) {
1312                 if (TAG_UID.equals(parser.getName())) {
1313                     final HistoricalOps returnedOps = readHistoricalUidOpsDLocked(ops, parser,
1314                             filterUid, filterPackageName, filterAttributionTag, filterOpNames,
1315                             filter, filterFlags, filterScale);
1316                     if (ops == null) {
1317                         ops = returnedOps;
1318                     }
1319                 }
1320             }
1321             if (ops != null) {
1322                 ops.setBeginAndEndTime(filteredBeginTimeMillis, filteredEndTimeMillis);
1323             }
1324             return ops;
1325         }
1326 
readHistoricalUidOpsDLocked( @ullable HistoricalOps ops, @NonNull TypedXmlPullParser parser, int filterUid, @Nullable String filterPackageName, @Nullable String filterAttributionTag, @Nullable String[] filterOpNames, @HistoricalOpsRequestFilter int filter, @OpFlags int filterFlags, double filterScale)1327         private @Nullable HistoricalOps readHistoricalUidOpsDLocked(
1328                 @Nullable HistoricalOps ops, @NonNull TypedXmlPullParser parser, int filterUid,
1329                 @Nullable String filterPackageName, @Nullable String filterAttributionTag,
1330                 @Nullable String[] filterOpNames, @HistoricalOpsRequestFilter int filter,
1331                 @OpFlags int filterFlags, double filterScale)
1332                 throws IOException, XmlPullParserException {
1333             final int uid = parser.getAttributeInt(null, ATTR_NAME);
1334             if ((filter & FILTER_BY_UID) != 0 && filterUid != uid) {
1335                 XmlUtils.skipCurrentTag(parser);
1336                 return null;
1337             }
1338             final int depth = parser.getDepth();
1339             while (XmlUtils.nextElementWithin(parser, depth)) {
1340                 if (TAG_PACKAGE.equals(parser.getName())) {
1341                     final HistoricalOps returnedOps = readHistoricalPackageOpsDLocked(ops, uid,
1342                             parser, filterPackageName, filterAttributionTag, filterOpNames, filter,
1343                             filterFlags, filterScale);
1344                     if (ops == null) {
1345                         ops = returnedOps;
1346                     }
1347                 }
1348             }
1349             return ops;
1350         }
1351 
readHistoricalPackageOpsDLocked( @ullable HistoricalOps ops, int uid, @NonNull TypedXmlPullParser parser, @Nullable String filterPackageName, @Nullable String filterAttributionTag, @Nullable String[] filterOpNames, @HistoricalOpsRequestFilter int filter, @OpFlags int filterFlags, double filterScale)1352         private @Nullable HistoricalOps readHistoricalPackageOpsDLocked(
1353                 @Nullable HistoricalOps ops, int uid, @NonNull TypedXmlPullParser parser,
1354                 @Nullable String filterPackageName, @Nullable String filterAttributionTag,
1355                 @Nullable String[] filterOpNames, @HistoricalOpsRequestFilter int filter,
1356                 @OpFlags int filterFlags, double filterScale)
1357                 throws IOException, XmlPullParserException {
1358             final String packageName = XmlUtils.readStringAttribute(parser, ATTR_NAME);
1359             if ((filter & FILTER_BY_PACKAGE_NAME) != 0 && !filterPackageName.equals(packageName)) {
1360                 XmlUtils.skipCurrentTag(parser);
1361                 return null;
1362             }
1363             final int depth = parser.getDepth();
1364             while (XmlUtils.nextElementWithin(parser, depth)) {
1365                 if (TAG_ATTRIBUTION.equals(parser.getName())) {
1366                     final HistoricalOps returnedOps = readHistoricalAttributionOpsDLocked(ops, uid,
1367                             packageName, parser, filterAttributionTag, filterOpNames, filter,
1368                             filterFlags, filterScale);
1369                     if (ops == null) {
1370                         ops = returnedOps;
1371                     }
1372                 }
1373             }
1374             return ops;
1375         }
1376 
readHistoricalAttributionOpsDLocked( @ullable HistoricalOps ops, int uid, String packageName, @NonNull TypedXmlPullParser parser, @Nullable String filterAttributionTag, @Nullable String[] filterOpNames, @HistoricalOpsRequestFilter int filter, @OpFlags int filterFlags, double filterScale)1377         private @Nullable HistoricalOps readHistoricalAttributionOpsDLocked(
1378                 @Nullable HistoricalOps ops, int uid, String packageName,
1379                 @NonNull TypedXmlPullParser parser, @Nullable String filterAttributionTag,
1380                 @Nullable String[] filterOpNames, @HistoricalOpsRequestFilter int filter,
1381                 @OpFlags int filterFlags, double filterScale)
1382                 throws IOException, XmlPullParserException {
1383             final String attributionTag = XmlUtils.readStringAttribute(parser, ATTR_NAME);
1384             if ((filter & FILTER_BY_ATTRIBUTION_TAG) != 0 && !Objects.equals(filterAttributionTag,
1385                     attributionTag)) {
1386                 XmlUtils.skipCurrentTag(parser);
1387                 return null;
1388             }
1389             final int depth = parser.getDepth();
1390             while (XmlUtils.nextElementWithin(parser, depth)) {
1391                 if (TAG_OP.equals(parser.getName())) {
1392                     final HistoricalOps returnedOps = readHistoricalOpDLocked(ops, uid, packageName,
1393                             attributionTag, parser, filterOpNames, filter, filterFlags,
1394                             filterScale);
1395                     if (ops == null) {
1396                         ops = returnedOps;
1397                     }
1398                 }
1399             }
1400             return ops;
1401         }
1402 
readHistoricalOpDLocked(@ullable HistoricalOps ops, int uid, @NonNull String packageName, @Nullable String attributionTag, @NonNull TypedXmlPullParser parser, @Nullable String[] filterOpNames, @HistoricalOpsRequestFilter int filter, @OpFlags int filterFlags, double filterScale)1403         private @Nullable HistoricalOps readHistoricalOpDLocked(@Nullable HistoricalOps ops,
1404                 int uid, @NonNull String packageName, @Nullable String attributionTag,
1405                 @NonNull TypedXmlPullParser parser, @Nullable String[] filterOpNames,
1406                 @HistoricalOpsRequestFilter int filter, @OpFlags int filterFlags,
1407                 double filterScale)
1408                 throws IOException, XmlPullParserException {
1409             final int op = parser.getAttributeInt(null, ATTR_NAME);
1410             if ((filter & FILTER_BY_OP_NAMES) != 0 && !ArrayUtils.contains(filterOpNames,
1411                     AppOpsManager.opToPublicName(op))) {
1412                 XmlUtils.skipCurrentTag(parser);
1413                 return null;
1414             }
1415             final int depth = parser.getDepth();
1416             while (XmlUtils.nextElementWithin(parser, depth)) {
1417                 if (TAG_STATE.equals(parser.getName())) {
1418                     final HistoricalOps returnedOps = readStateDLocked(ops, uid,
1419                             packageName, attributionTag, op, parser, filterFlags, filterScale);
1420                     if (ops == null) {
1421                         ops = returnedOps;
1422                     }
1423                 }
1424             }
1425             return ops;
1426         }
1427 
readStateDLocked(@ullable HistoricalOps ops, int uid, @NonNull String packageName, @Nullable String attributionTag, int op, @NonNull TypedXmlPullParser parser, @OpFlags int filterFlags, double filterScale)1428         private @Nullable HistoricalOps readStateDLocked(@Nullable HistoricalOps ops,
1429                 int uid, @NonNull String packageName, @Nullable String attributionTag, int op,
1430                 @NonNull TypedXmlPullParser parser, @OpFlags int filterFlags, double filterScale)
1431                 throws IOException, XmlPullParserException {
1432             final long key = parser.getAttributeLong(null, ATTR_NAME);
1433             final int flags = AppOpsManager.extractFlagsFromKey(key) & filterFlags;
1434             if (flags == 0) {
1435                 return null;
1436             }
1437             final int uidState = AppOpsManager.extractUidStateFromKey(key);
1438             long accessCount = parser.getAttributeLong(null, ATTR_ACCESS_COUNT, 0);
1439             if (accessCount > 0) {
1440                 if (!Double.isNaN(filterScale)) {
1441                     accessCount = (long) HistoricalOps.round(
1442                             (double) accessCount * filterScale);
1443                 }
1444                 if (ops == null) {
1445                     ops = new HistoricalOps(0, 0);
1446                 }
1447                 ops.increaseAccessCount(op, uid, packageName, attributionTag, uidState, flags,
1448                         accessCount);
1449             }
1450             long rejectCount = parser.getAttributeLong(null, ATTR_REJECT_COUNT, 0);
1451             if (rejectCount > 0) {
1452                 if (!Double.isNaN(filterScale)) {
1453                     rejectCount = (long) HistoricalOps.round(
1454                             (double) rejectCount * filterScale);
1455                 }
1456                 if (ops == null) {
1457                     ops = new HistoricalOps(0, 0);
1458                 }
1459                 ops.increaseRejectCount(op, uid, packageName, attributionTag, uidState, flags,
1460                         rejectCount);
1461             }
1462             long accessDuration =  parser.getAttributeLong(null, ATTR_ACCESS_DURATION, 0);
1463             if (accessDuration > 0) {
1464                 if (!Double.isNaN(filterScale)) {
1465                     accessDuration = (long) HistoricalOps.round(
1466                             (double) accessDuration * filterScale);
1467                 }
1468                 if (ops == null) {
1469                     ops = new HistoricalOps(0, 0);
1470                 }
1471                 ops.increaseAccessDuration(op, uid, packageName, attributionTag, uidState, flags,
1472                         accessDuration);
1473             }
1474             return ops;
1475         }
1476 
writeHistoricalOpsDLocked(@ullable List<HistoricalOps> allOps, long intervalOverflowMillis, @NonNull File file)1477         private void writeHistoricalOpsDLocked(@Nullable List<HistoricalOps> allOps,
1478                 long intervalOverflowMillis, @NonNull File file) throws IOException {
1479             final FileOutputStream output = sHistoricalAppOpsDir.openWrite(file);
1480             try {
1481                 final TypedXmlSerializer serializer = Xml.resolveSerializer(output);
1482                 serializer.setFeature("http://xmlpull.org/v1/doc/features.html#indent-output",
1483                         true);
1484                 serializer.startDocument(null, true);
1485                 serializer.startTag(null, TAG_HISTORY);
1486                 serializer.attributeInt(null, ATTR_VERSION, CURRENT_VERSION);
1487                 if (intervalOverflowMillis != 0) {
1488                     serializer.attributeLong(null, ATTR_OVERFLOW, intervalOverflowMillis);
1489                 }
1490                 if (allOps != null) {
1491                     final int opsCount = allOps.size();
1492                     for (int i = 0; i < opsCount; i++) {
1493                         final HistoricalOps ops = allOps.get(i);
1494                         writeHistoricalOpDLocked(ops, serializer);
1495                     }
1496                 }
1497                 serializer.endTag(null, TAG_HISTORY);
1498                 serializer.endDocument();
1499                 sHistoricalAppOpsDir.closeWrite(output);
1500             } catch (IOException e) {
1501                 sHistoricalAppOpsDir.failWrite(output);
1502                 throw e;
1503             }
1504         }
1505 
writeHistoricalOpDLocked(@onNull HistoricalOps ops, @NonNull TypedXmlSerializer serializer)1506         private void writeHistoricalOpDLocked(@NonNull HistoricalOps ops,
1507                 @NonNull TypedXmlSerializer serializer) throws IOException {
1508             serializer.startTag(null, TAG_OPS);
1509             serializer.attributeLong(null, ATTR_BEGIN_TIME, ops.getBeginTimeMillis());
1510             serializer.attributeLong(null, ATTR_END_TIME, ops.getEndTimeMillis());
1511             final int uidCount = ops.getUidCount();
1512             for (int i = 0; i < uidCount; i++) {
1513                 final HistoricalUidOps uidOp = ops.getUidOpsAt(i);
1514                 writeHistoricalUidOpsDLocked(uidOp, serializer);
1515             }
1516             serializer.endTag(null, TAG_OPS);
1517         }
1518 
writeHistoricalUidOpsDLocked(@onNull HistoricalUidOps uidOps, @NonNull TypedXmlSerializer serializer)1519         private void writeHistoricalUidOpsDLocked(@NonNull HistoricalUidOps uidOps,
1520                 @NonNull TypedXmlSerializer serializer) throws IOException {
1521             serializer.startTag(null, TAG_UID);
1522             serializer.attributeInt(null, ATTR_NAME, uidOps.getUid());
1523             final int packageCount = uidOps.getPackageCount();
1524             for (int i = 0; i < packageCount; i++) {
1525                 final HistoricalPackageOps packageOps = uidOps.getPackageOpsAt(i);
1526                 writeHistoricalPackageOpsDLocked(packageOps, serializer);
1527             }
1528             serializer.endTag(null, TAG_UID);
1529         }
1530 
writeHistoricalPackageOpsDLocked(@onNull HistoricalPackageOps packageOps, @NonNull TypedXmlSerializer serializer)1531         private void writeHistoricalPackageOpsDLocked(@NonNull HistoricalPackageOps packageOps,
1532                 @NonNull TypedXmlSerializer serializer) throws IOException {
1533             serializer.startTag(null, TAG_PACKAGE);
1534             serializer.attributeInterned(null, ATTR_NAME, packageOps.getPackageName());
1535             final int numAttributions = packageOps.getAttributedOpsCount();
1536             for (int i = 0; i < numAttributions; i++) {
1537                 final AppOpsManager.AttributedHistoricalOps op = packageOps.getAttributedOpsAt(i);
1538                 writeHistoricalAttributionOpsDLocked(op, serializer);
1539             }
1540             serializer.endTag(null, TAG_PACKAGE);
1541         }
1542 
writeHistoricalAttributionOpsDLocked( @onNull AppOpsManager.AttributedHistoricalOps attributionOps, @NonNull TypedXmlSerializer serializer)1543         private void writeHistoricalAttributionOpsDLocked(
1544                 @NonNull AppOpsManager.AttributedHistoricalOps attributionOps,
1545                 @NonNull TypedXmlSerializer serializer) throws IOException {
1546             serializer.startTag(null, TAG_ATTRIBUTION);
1547             XmlUtils.writeStringAttribute(serializer, ATTR_NAME, attributionOps.getTag());
1548             final int opCount = attributionOps.getOpCount();
1549             for (int i = 0; i < opCount; i++) {
1550                 final HistoricalOp op = attributionOps.getOpAt(i);
1551                 writeHistoricalOpDLocked(op, serializer);
1552             }
1553             serializer.endTag(null, TAG_ATTRIBUTION);
1554         }
1555 
writeHistoricalOpDLocked(@onNull HistoricalOp op, @NonNull TypedXmlSerializer serializer)1556         private void writeHistoricalOpDLocked(@NonNull HistoricalOp op,
1557                 @NonNull TypedXmlSerializer serializer) throws IOException {
1558             final LongSparseArray keys = op.collectKeys();
1559             if (keys == null || keys.size() <= 0) {
1560                 return;
1561             }
1562             serializer.startTag(null, TAG_OP);
1563             serializer.attributeInt(null, ATTR_NAME, op.getOpCode());
1564             final int keyCount = keys.size();
1565             for (int i = 0; i < keyCount; i++) {
1566                 writeStateOnLocked(op, keys.keyAt(i), serializer);
1567             }
1568             serializer.endTag(null, TAG_OP);
1569         }
1570 
writeStateOnLocked(@onNull HistoricalOp op, long key, @NonNull TypedXmlSerializer serializer)1571         private void writeStateOnLocked(@NonNull HistoricalOp op, long key,
1572                 @NonNull TypedXmlSerializer serializer) throws IOException {
1573             final int uidState = AppOpsManager.extractUidStateFromKey(key);
1574             final int flags = AppOpsManager.extractFlagsFromKey(key);
1575 
1576             final long accessCount = op.getAccessCount(uidState, uidState, flags);
1577             final long rejectCount = op.getRejectCount(uidState, uidState, flags);
1578             final long accessDuration = op.getAccessDuration(uidState, uidState, flags);
1579 
1580             if (accessCount <= 0 && rejectCount <= 0 && accessDuration <= 0) {
1581                 return;
1582             }
1583 
1584             serializer.startTag(null, TAG_STATE);
1585             serializer.attributeLong(null, ATTR_NAME, key);
1586             if (accessCount > 0) {
1587                 serializer.attributeLong(null, ATTR_ACCESS_COUNT, accessCount);
1588             }
1589             if (rejectCount > 0) {
1590                 serializer.attributeLong(null, ATTR_REJECT_COUNT, rejectCount);
1591             }
1592             if (accessDuration > 0) {
1593                 serializer.attributeLong(null, ATTR_ACCESS_DURATION, accessDuration);
1594             }
1595             serializer.endTag(null, TAG_STATE);
1596         }
1597 
enforceOpsWellFormed(@onNull List<HistoricalOps> ops)1598         private static void enforceOpsWellFormed(@NonNull List<HistoricalOps> ops) {
1599             if (ops == null) {
1600                 return;
1601             }
1602             HistoricalOps previous;
1603             HistoricalOps current = null;
1604             final int opsCount = ops.size();
1605             for (int i = 0; i < opsCount; i++) {
1606                 previous = current;
1607                 current = ops.get(i);
1608                 if (current.isEmpty()) {
1609                     throw new IllegalStateException("Empty ops:\n"
1610                             + opsToDebugString(ops));
1611                 }
1612                 if (current.getEndTimeMillis() < current.getBeginTimeMillis()) {
1613                     throw new IllegalStateException("Begin after end:\n"
1614                             + opsToDebugString(ops));
1615                 }
1616                 if (previous != null) {
1617                     if (previous.getEndTimeMillis() > current.getBeginTimeMillis()) {
1618                         throw new IllegalStateException("Intersecting ops:\n"
1619                                 + opsToDebugString(ops));
1620                     }
1621                     if (previous.getBeginTimeMillis() > current.getBeginTimeMillis()) {
1622                         throw new IllegalStateException("Non increasing ops:\n"
1623                                 + opsToDebugString(ops));
1624                     }
1625                 }
1626             }
1627         }
1628 
computeGlobalIntervalBeginMillis(int depth)1629         private long computeGlobalIntervalBeginMillis(int depth) {
1630             long beginTimeMillis = 0;
1631             for (int i = 0; i < depth + 1; i++) {
1632                 beginTimeMillis += Math.pow(mIntervalCompressionMultiplier, i);
1633             }
1634             return beginTimeMillis * mBaseSnapshotInterval;
1635         }
1636 
spliceFromEnd(@onNull HistoricalOps ops, double spliceRatio)1637         private static @NonNull HistoricalOps spliceFromEnd(@NonNull HistoricalOps ops,
1638                 double spliceRatio) {
1639             if (DEBUG) {
1640                 Slog.w(LOG_TAG, "Splicing from end:" + ops + " ratio:" + spliceRatio);
1641             }
1642             final HistoricalOps splice = ops.spliceFromEnd(spliceRatio);
1643             if (DEBUG) {
1644                 Slog.w(LOG_TAG, "Spliced into:" + ops + " and:" + splice);
1645             }
1646             return splice;
1647         }
1648 
1649 
spliceFromBeginning(@onNull HistoricalOps ops, double spliceRatio)1650         private static @NonNull HistoricalOps spliceFromBeginning(@NonNull HistoricalOps ops,
1651                 double spliceRatio) {
1652             if (DEBUG) {
1653                 Slog.w(LOG_TAG, "Splicing from beginning:" + ops + " ratio:" + spliceRatio);
1654             }
1655             final HistoricalOps splice = ops.spliceFromBeginning(spliceRatio);
1656             if (DEBUG) {
1657                 Slog.w(LOG_TAG, "Spliced into:" + ops + " and:" + splice);
1658             }
1659             return splice;
1660         }
1661 
normalizeSnapshotForSlotDuration(@onNull List<HistoricalOps> ops, long slotDurationMillis)1662         private static void normalizeSnapshotForSlotDuration(@NonNull List<HistoricalOps> ops,
1663                 long slotDurationMillis) {
1664             if (DEBUG) {
1665                 Slog.i(LOG_TAG, "Normalizing for slot duration: " + slotDurationMillis
1666                         + " ops:\n" + opsToDebugString(ops));
1667                 enforceOpsWellFormed(ops);
1668             }
1669             long slotBeginTimeMillis;
1670             final int opCount = ops.size();
1671             for (int processedIdx = opCount - 1; processedIdx >= 0; processedIdx--) {
1672                 final HistoricalOps processedOp = ops.get(processedIdx);
1673                 slotBeginTimeMillis = Math.max(processedOp.getEndTimeMillis()
1674                         - slotDurationMillis, 0);
1675                 for (int candidateIdx = processedIdx - 1; candidateIdx >= 0; candidateIdx--) {
1676                     final HistoricalOps candidateOp = ops.get(candidateIdx);
1677                     final long candidateSlotIntersectionMillis = candidateOp.getEndTimeMillis()
1678                             - Math.min(slotBeginTimeMillis, processedOp.getBeginTimeMillis());
1679                     if (candidateSlotIntersectionMillis <= 0) {
1680                         break;
1681                     }
1682                     final float candidateSplitRatio = candidateSlotIntersectionMillis
1683                             / (float) candidateOp.getDurationMillis();
1684                     if (Float.compare(candidateSplitRatio, 1.0f) >= 0) {
1685                         ops.remove(candidateIdx);
1686                         processedIdx--;
1687                         processedOp.merge(candidateOp);
1688                     } else {
1689                         final HistoricalOps endSplice = spliceFromEnd(candidateOp,
1690                                 candidateSplitRatio);
1691                         if (endSplice != null) {
1692                             processedOp.merge(endSplice);
1693                         }
1694                         if (candidateOp.isEmpty()) {
1695                             ops.remove(candidateIdx);
1696                             processedIdx--;
1697                         }
1698                     }
1699                 }
1700             }
1701             if (DEBUG) {
1702                 Slog.i(LOG_TAG, "Normalized for slot duration: " + slotDurationMillis
1703                         + " ops:\n" + opsToDebugString(ops));
1704                 enforceOpsWellFormed(ops);
1705             }
1706         }
1707 
opsToDebugString(@onNull List<HistoricalOps> ops)1708         private static @NonNull String opsToDebugString(@NonNull List<HistoricalOps> ops) {
1709             StringBuilder builder = new StringBuilder();
1710             final int opCount = ops.size();
1711             for (int i = 0; i < opCount; i++) {
1712                 builder.append("  ");
1713                 builder.append(ops.get(i));
1714                 if (i < opCount - 1) {
1715                     builder.append('\n');
1716                 }
1717             }
1718             return builder.toString();
1719         }
1720 
getHistoricalFileNames(@onNull File historyDir)1721         private static Set<String> getHistoricalFileNames(@NonNull File historyDir)  {
1722             final File[] files = historyDir.listFiles();
1723             if (files == null) {
1724                 return Collections.emptySet();
1725             }
1726             final ArraySet<String> fileNames = new ArraySet<>(files.length);
1727             for (File file : files) {
1728                 fileNames.add(file.getName());
1729 
1730             }
1731             return fileNames;
1732         }
1733     }
1734 
1735     private static class HistoricalFilesInvariant {
1736         private final @NonNull List<File> mBeginFiles = new ArrayList<>();
1737 
startTracking(@onNull File folder)1738         public void startTracking(@NonNull File folder) {
1739             final File[] files = folder.listFiles();
1740             if (files != null) {
1741                 Collections.addAll(mBeginFiles, files);
1742             }
1743         }
1744 
stopTracking(@onNull File folder)1745         public void stopTracking(@NonNull File folder) {
1746             final List<File> endFiles = new ArrayList<>();
1747             final File[] files = folder.listFiles();
1748             if (files != null) {
1749                 Collections.addAll(endFiles, files);
1750             }
1751             final long beginOldestFileOffsetMillis = getOldestFileOffsetMillis(mBeginFiles);
1752             final long endOldestFileOffsetMillis = getOldestFileOffsetMillis(endFiles);
1753             if (endOldestFileOffsetMillis < beginOldestFileOffsetMillis) {
1754                 final String message = "History loss detected!"
1755                         + "\nold files: " + mBeginFiles;
1756                 wtf(message, null, folder);
1757                 throw new IllegalStateException(message);
1758             }
1759         }
1760 
getOldestFileOffsetMillis(@onNull List<File> files)1761         private static long getOldestFileOffsetMillis(@NonNull List<File> files) {
1762             if (files.isEmpty()) {
1763                 return 0;
1764             }
1765             String longestName = files.get(0).getName();
1766             final int fileCount = files.size();
1767             for (int i = 1; i < fileCount; i++) {
1768                 final File file = files.get(i);
1769                 if (file.getName().length() > longestName.length()) {
1770                     longestName = file.getName();
1771                 }
1772             }
1773             return Long.parseLong(longestName.replace(HISTORY_FILE_SUFFIX, ""));
1774         }
1775     }
1776 
1777     private final class StringDumpVisitor implements AppOpsManager.HistoricalOpsVisitor {
1778         private final long mNow = System.currentTimeMillis();
1779 
1780         private final SimpleDateFormat mDateFormatter = new SimpleDateFormat(
1781                 "yyyy-MM-dd HH:mm:ss.SSS");
1782         private final Date mDate = new Date();
1783 
1784         private final @NonNull String mOpsPrefix;
1785         private final @NonNull String mUidPrefix;
1786         private final @NonNull String mPackagePrefix;
1787         private final @NonNull String mAttributionPrefix;
1788         private final @NonNull String mEntryPrefix;
1789         private final @NonNull String mUidStatePrefix;
1790         private final @NonNull PrintWriter mWriter;
1791         private final int mFilterUid;
1792         private final String mFilterPackage;
1793         private final String mFilterAttributionTag;
1794         private final int mFilterOp;
1795         private final @HistoricalOpsRequestFilter int mFilter;
1796 
StringDumpVisitor(@onNull String prefix, @NonNull PrintWriter writer, int filterUid, @Nullable String filterPackage, @Nullable String filterAttributionTag, int filterOp, @HistoricalOpsRequestFilter int filter)1797         StringDumpVisitor(@NonNull String prefix, @NonNull PrintWriter writer, int filterUid,
1798                 @Nullable String filterPackage, @Nullable String filterAttributionTag, int filterOp,
1799                 @HistoricalOpsRequestFilter int filter) {
1800             mOpsPrefix = prefix + "  ";
1801             mUidPrefix = mOpsPrefix + "  ";
1802             mPackagePrefix = mUidPrefix + "  ";
1803             mAttributionPrefix = mPackagePrefix + "  ";
1804             mEntryPrefix = mAttributionPrefix + "  ";
1805             mUidStatePrefix = mEntryPrefix + "  ";
1806             mWriter = writer;
1807             mFilterUid = filterUid;
1808             mFilterPackage = filterPackage;
1809             mFilterAttributionTag = filterAttributionTag;
1810             mFilterOp = filterOp;
1811             mFilter = filter;
1812         }
1813 
1814         @Override
visitHistoricalOps(HistoricalOps ops)1815         public void visitHistoricalOps(HistoricalOps ops) {
1816             mWriter.println();
1817             mWriter.print(mOpsPrefix);
1818             mWriter.println("snapshot:");
1819             mWriter.print(mUidPrefix);
1820             mWriter.print("begin = ");
1821             mDate.setTime(ops.getBeginTimeMillis());
1822             mWriter.print(mDateFormatter.format(mDate));
1823             mWriter.print("  (");
1824             TimeUtils.formatDuration(ops.getBeginTimeMillis() - mNow, mWriter);
1825             mWriter.println(")");
1826             mWriter.print(mUidPrefix);
1827             mWriter.print("end = ");
1828             mDate.setTime(ops.getEndTimeMillis());
1829             mWriter.print(mDateFormatter.format(mDate));
1830             mWriter.print("  (");
1831             TimeUtils.formatDuration(ops.getEndTimeMillis() - mNow, mWriter);
1832             mWriter.println(")");
1833         }
1834 
1835         @Override
visitHistoricalUidOps(HistoricalUidOps ops)1836         public void visitHistoricalUidOps(HistoricalUidOps ops) {
1837             if ((mFilter & FILTER_BY_UID) != 0 && mFilterUid != ops.getUid()) {
1838                 return;
1839             }
1840             mWriter.println();
1841             mWriter.print(mUidPrefix);
1842             mWriter.print("Uid ");
1843             UserHandle.formatUid(mWriter, ops.getUid());
1844             mWriter.println(":");
1845         }
1846 
1847         @Override
visitHistoricalPackageOps(HistoricalPackageOps ops)1848         public void visitHistoricalPackageOps(HistoricalPackageOps ops) {
1849             if ((mFilter & FILTER_BY_PACKAGE_NAME) != 0 && !mFilterPackage.equals(
1850                     ops.getPackageName())) {
1851                 return;
1852             }
1853             mWriter.print(mPackagePrefix);
1854             mWriter.print("Package ");
1855             mWriter.print(ops.getPackageName());
1856             mWriter.println(":");
1857         }
1858 
1859         @Override
visitHistoricalAttributionOps(AppOpsManager.AttributedHistoricalOps ops)1860         public void visitHistoricalAttributionOps(AppOpsManager.AttributedHistoricalOps ops) {
1861             if ((mFilter & FILTER_BY_ATTRIBUTION_TAG) != 0 && !Objects.equals(mFilterPackage,
1862                     ops.getTag())) {
1863                 return;
1864             }
1865             mWriter.print(mAttributionPrefix);
1866             mWriter.print("Attribution ");
1867             mWriter.print(ops.getTag());
1868             mWriter.println(":");
1869         }
1870 
1871         @Override
visitHistoricalOp(HistoricalOp ops)1872         public void visitHistoricalOp(HistoricalOp ops) {
1873             if ((mFilter & FILTER_BY_OP_NAMES) != 0  && mFilterOp != ops.getOpCode()) {
1874                 return;
1875             }
1876             mWriter.print(mEntryPrefix);
1877             mWriter.print(AppOpsManager.opToName(ops.getOpCode()));
1878             mWriter.println(":");
1879             final LongSparseArray keys = ops.collectKeys();
1880             final int keyCount = keys.size();
1881             for (int i = 0; i < keyCount; i++) {
1882                 final long key = keys.keyAt(i);
1883                 final int uidState = AppOpsManager.extractUidStateFromKey(key);
1884                 final int flags = AppOpsManager.extractFlagsFromKey(key);
1885                 boolean printedUidState = false;
1886                 final long accessCount = ops.getAccessCount(uidState, uidState, flags);
1887                 if (accessCount > 0) {
1888                     if (!printedUidState) {
1889                         mWriter.print(mUidStatePrefix);
1890                         mWriter.print(AppOpsManager.keyToString(key));
1891                         mWriter.print(" = ");
1892                         printedUidState = true;
1893                     }
1894                     mWriter.print("access=");
1895                     mWriter.print(accessCount);
1896                 }
1897                 final long rejectCount = ops.getRejectCount(uidState, uidState, flags);
1898                 if (rejectCount > 0) {
1899                     if (!printedUidState) {
1900                         mWriter.print(mUidStatePrefix);
1901                         mWriter.print(AppOpsManager.keyToString(key));
1902                         mWriter.print(" = ");
1903                         printedUidState = true;
1904                     } else {
1905                         mWriter.print(", ");
1906                     }
1907                     mWriter.print("reject=");
1908                     mWriter.print(rejectCount);
1909                 }
1910                 final long accessDuration = ops.getAccessDuration(uidState, uidState, flags);
1911                 if (accessDuration > 0) {
1912                     if (!printedUidState) {
1913                         mWriter.print(mUidStatePrefix);
1914                         mWriter.print(AppOpsManager.keyToString(key));
1915                         mWriter.print(" = ");
1916                         printedUidState = true;
1917                     } else {
1918                         mWriter.print(", ");
1919                     }
1920                     mWriter.print("duration=");
1921                     TimeUtils.formatDuration(accessDuration, mWriter);
1922                 }
1923                 if (printedUidState) {
1924                     mWriter.println("");
1925                 }
1926             }
1927         }
1928     }
1929 
wtf(@ullable String message, @Nullable Throwable t, @Nullable File storage)1930     private static void wtf(@Nullable String message, @Nullable Throwable t,
1931             @Nullable File storage) {
1932         Slog.wtf(LOG_TAG, message, t);
1933         if (KEEP_WTF_LOG) {
1934             try {
1935                 final File file = new File(new File(Environment.getDataSystemDirectory(), "appops"),
1936                         "wtf" + TimeUtils.formatForLogging(System.currentTimeMillis()));
1937                 if (file.createNewFile()) {
1938                     try (PrintWriter writer = new PrintWriter(file)) {
1939                         if (t != null) {
1940                             writer.append('\n').append(t.toString());
1941                         }
1942                         writer.append('\n').append(Debug.getCallers(10));
1943                         if (storage != null) {
1944                             writer.append("\nfiles: " + Arrays.toString(storage.listFiles()));
1945                         } else {
1946                             writer.append("\nfiles: none");
1947                         }
1948                     }
1949                 }
1950             } catch (IOException e) {
1951                 /* ignore */
1952             }
1953         }
1954     }
1955 }
1956