/*
 * Copyright (C) 2017 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License
 */

package com.android.internal.os;

import android.annotation.NonNull;
import android.annotation.Nullable;
import android.os.Binder;
import android.os.Process;
import android.os.SystemClock;
import android.text.format.DateFormat;
import android.util.ArrayMap;
import android.util.Pair;
import android.util.Slog;
import android.util.SparseArray;

import com.android.internal.annotations.GuardedBy;
import com.android.internal.annotations.VisibleForTesting;
import com.android.internal.os.BinderInternal.CallSession;

import java.io.PrintWriter;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Random;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.function.ToDoubleFunction;

/**
 * Collects statistics about CPU time spent per binder call across multiple dimensions, e.g.
 * per thread, uid or call description.
 */
public class BinderCallsStats implements BinderInternal.Observer {
    public static final boolean ENABLED_DEFAULT = true;
    public static final boolean DETAILED_TRACKING_DEFAULT = true;
    public static final int PERIODIC_SAMPLING_INTERVAL_DEFAULT = 1000;
    public static final boolean DEFAULT_TRACK_SCREEN_INTERACTIVE = false;
    public static final boolean DEFAULT_TRACK_DIRECT_CALLING_UID = true;
    public static final int MAX_BINDER_CALL_STATS_COUNT_DEFAULT = 5000;
    private static final String DEBUG_ENTRY_PREFIX = "__DEBUG_";

    private static class OverflowBinder extends Binder {}

    private static final String TAG = "BinderCallsStats";
    private static final int CALL_SESSIONS_POOL_SIZE = 100;
    private static final int MAX_EXCEPTION_COUNT_SIZE = 50;
    private static final String EXCEPTION_COUNT_OVERFLOW_NAME = "overflow";
    // Default values for overflow entry. The work source uid does not use a default value in order
    // to have on overflow entry per work source uid.
    private static final Class<? extends Binder> OVERFLOW_BINDER = OverflowBinder.class;
    private static final boolean OVERFLOW_SCREEN_INTERACTIVE = false;
    private static final int OVERFLOW_DIRECT_CALLING_UID = -1;
    private static final int OVERFLOW_TRANSACTION_CODE = -1;

    // Whether to collect all the data: cpu + exceptions + reply/request sizes.
    private boolean mDetailedTracking = DETAILED_TRACKING_DEFAULT;
    // Sampling period to control how often to track CPU usage. 1 means all calls, 100 means ~1 out
    // of 100 requests.
    private int mPeriodicSamplingInterval = PERIODIC_SAMPLING_INTERVAL_DEFAULT;
    private int mMaxBinderCallStatsCount = MAX_BINDER_CALL_STATS_COUNT_DEFAULT;
    @GuardedBy("mLock")
    private final SparseArray<UidEntry> mUidEntries = new SparseArray<>();
    @GuardedBy("mLock")
    private final ArrayMap<String, Integer> mExceptionCounts = new ArrayMap<>();
    private final Queue<CallSession> mCallSessionsPool = new ConcurrentLinkedQueue<>();
    private final Object mLock = new Object();
    private final Random mRandom;
    private long mStartCurrentTime = System.currentTimeMillis();
    private long mStartElapsedTime = SystemClock.elapsedRealtime();
    private long mCallStatsCount = 0;
    private boolean mAddDebugEntries = false;
    private boolean mTrackDirectCallingUid = DEFAULT_TRACK_DIRECT_CALLING_UID;
    private boolean mTrackScreenInteractive = DEFAULT_TRACK_SCREEN_INTERACTIVE;

    private CachedDeviceState.Readonly mDeviceState;
    private CachedDeviceState.TimeInStateStopwatch mBatteryStopwatch;

    /** Injector for {@link BinderCallsStats}. */
    public static class Injector {
        public Random getRandomGenerator() {
            return new Random();
        }
    }

    public BinderCallsStats(Injector injector) {
        this.mRandom = injector.getRandomGenerator();
    }

    public void setDeviceState(@NonNull CachedDeviceState.Readonly deviceState) {
        if (mBatteryStopwatch != null) {
            mBatteryStopwatch.close();
        }
        mDeviceState = deviceState;
        mBatteryStopwatch = deviceState.createTimeOnBatteryStopwatch();
    }

    @Override
    @Nullable
    public CallSession callStarted(Binder binder, int code, int workSourceUid) {
        if (mDeviceState == null || mDeviceState.isCharging()) {
            return null;
        }

        final CallSession s = obtainCallSession();
        s.binderClass = binder.getClass();
        s.transactionCode = code;
        s.exceptionThrown = false;
        s.cpuTimeStarted = -1;
        s.timeStarted = -1;
        if (shouldRecordDetailedData()) {
            s.cpuTimeStarted = getThreadTimeMicro();
            s.timeStarted = getElapsedRealtimeMicro();
        }
        return s;
    }

    private CallSession obtainCallSession() {
        CallSession s = mCallSessionsPool.poll();
        return s == null ? new CallSession() : s;
    }

    @Override
    public void callEnded(@Nullable CallSession s, int parcelRequestSize,
            int parcelReplySize, int workSourceUid) {
        if (s == null) {
            return;
        }

        processCallEnded(s, parcelRequestSize, parcelReplySize, workSourceUid);

        if (mCallSessionsPool.size() < CALL_SESSIONS_POOL_SIZE) {
            mCallSessionsPool.add(s);
        }
    }

    private void processCallEnded(CallSession s,
            int parcelRequestSize, int parcelReplySize, int workSourceUid) {
        // Non-negative time signals we need to record data for this call.
        final boolean recordCall = s.cpuTimeStarted >= 0;
        final long duration;
        final long latencyDuration;
        if (recordCall) {
            duration = getThreadTimeMicro() - s.cpuTimeStarted;
            latencyDuration = getElapsedRealtimeMicro() - s.timeStarted;
        } else {
            duration = 0;
            latencyDuration = 0;
        }
        final boolean screenInteractive = mTrackScreenInteractive
                ? mDeviceState.isScreenInteractive()
                : OVERFLOW_SCREEN_INTERACTIVE;
        final int callingUid = mTrackDirectCallingUid
                ? getCallingUid()
                : OVERFLOW_DIRECT_CALLING_UID;

        synchronized (mLock) {
            // This was already checked in #callStart but check again while synchronized.
            if (mDeviceState == null || mDeviceState.isCharging()) {
                return;
            }

            final UidEntry uidEntry = getUidEntry(workSourceUid);
            uidEntry.callCount++;

            if (recordCall) {
                uidEntry.cpuTimeMicros += duration;
                uidEntry.recordedCallCount++;

                final CallStat callStat = uidEntry.getOrCreate(
                        callingUid, s.binderClass, s.transactionCode,
                        screenInteractive,
                        mCallStatsCount >= mMaxBinderCallStatsCount);
                final boolean isNewCallStat = callStat.callCount == 0;
                if (isNewCallStat) {
                    mCallStatsCount++;
                }

                callStat.callCount++;
                callStat.recordedCallCount++;
                callStat.cpuTimeMicros += duration;
                callStat.maxCpuTimeMicros = Math.max(callStat.maxCpuTimeMicros, duration);
                callStat.latencyMicros += latencyDuration;
                callStat.maxLatencyMicros =
                        Math.max(callStat.maxLatencyMicros, latencyDuration);
                if (mDetailedTracking) {
                    callStat.exceptionCount += s.exceptionThrown ? 1 : 0;
                    callStat.maxRequestSizeBytes =
                            Math.max(callStat.maxRequestSizeBytes, parcelRequestSize);
                    callStat.maxReplySizeBytes =
                            Math.max(callStat.maxReplySizeBytes, parcelReplySize);
                }
            } else {
                // Only record the total call count if we already track data for this key.
                // It helps to keep the memory usage down when sampling is enabled.
                final CallStat callStat = uidEntry.get(
                        callingUid, s.binderClass, s.transactionCode,
                        mDeviceState.isScreenInteractive());
                if (callStat != null) {
                    callStat.callCount++;
                }
            }
        }
    }

    private UidEntry getUidEntry(int uid) {
        UidEntry uidEntry = mUidEntries.get(uid);
        if (uidEntry == null) {
            uidEntry = new UidEntry(uid);
            mUidEntries.put(uid, uidEntry);
        }
        return uidEntry;
    }

    @Override
    public void callThrewException(@Nullable CallSession s, Exception exception) {
        if (s == null) {
            return;
        }
        s.exceptionThrown = true;
        try {
            String className = exception.getClass().getName();
            synchronized (mLock) {
                if (mExceptionCounts.size() >= MAX_EXCEPTION_COUNT_SIZE) {
                    className = EXCEPTION_COUNT_OVERFLOW_NAME;
                }
                final Integer count = mExceptionCounts.get(className);
                mExceptionCounts.put(className, count == null ? 1 : count + 1);
            }
        } catch (RuntimeException e) {
            // Do not propagate the exception. We do not want to swallow original exception.
            Slog.wtf(TAG, "Unexpected exception while updating mExceptionCounts");
        }
    }

    @Nullable
    private Method getDefaultTransactionNameMethod(Class<? extends Binder> binder) {
        try {
            return binder.getMethod("getDefaultTransactionName", int.class);
        } catch (NoSuchMethodException e) {
            // The method might not be present for stubs not generated with AIDL.
            return null;
        }
    }

    @Nullable
    private String resolveTransactionCode(Method getDefaultTransactionName, int transactionCode) {
        if (getDefaultTransactionName == null) {
            return null;
        }

        try {
            return (String) getDefaultTransactionName.invoke(null, transactionCode);
        } catch (IllegalAccessException | InvocationTargetException | ClassCastException e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * This method is expensive to call.
     */
    public ArrayList<ExportedCallStat> getExportedCallStats() {
        // We do not collect all the data if detailed tracking is off.
        if (!mDetailedTracking) {
            return new ArrayList<>();
        }

        ArrayList<ExportedCallStat> resultCallStats = new ArrayList<>();
        synchronized (mLock) {
            final int uidEntriesSize = mUidEntries.size();
            for (int entryIdx = 0; entryIdx < uidEntriesSize; entryIdx++) {
                final UidEntry entry = mUidEntries.valueAt(entryIdx);
                for (CallStat stat : entry.getCallStatsList()) {
                    ExportedCallStat exported = new ExportedCallStat();
                    exported.workSourceUid = entry.workSourceUid;
                    exported.callingUid = stat.callingUid;
                    exported.className = stat.binderClass.getName();
                    exported.binderClass = stat.binderClass;
                    exported.transactionCode = stat.transactionCode;
                    exported.screenInteractive = stat.screenInteractive;
                    exported.cpuTimeMicros = stat.cpuTimeMicros;
                    exported.maxCpuTimeMicros = stat.maxCpuTimeMicros;
                    exported.latencyMicros = stat.latencyMicros;
                    exported.maxLatencyMicros = stat.maxLatencyMicros;
                    exported.recordedCallCount = stat.recordedCallCount;
                    exported.callCount = stat.callCount;
                    exported.maxRequestSizeBytes = stat.maxRequestSizeBytes;
                    exported.maxReplySizeBytes = stat.maxReplySizeBytes;
                    exported.exceptionCount = stat.exceptionCount;
                    resultCallStats.add(exported);
                }
            }
        }

        // Resolve codes outside of the lock since it can be slow.
        ExportedCallStat previous = null;
        // Cache the previous method/transaction code.
        Method getDefaultTransactionName = null;
        String previousMethodName = null;
        resultCallStats.sort(BinderCallsStats::compareByBinderClassAndCode);
        for (ExportedCallStat exported : resultCallStats) {
            final boolean isClassDifferent = previous == null
                    || !previous.className.equals(exported.className);
            if (isClassDifferent) {
                getDefaultTransactionName = getDefaultTransactionNameMethod(exported.binderClass);
            }

            final boolean isCodeDifferent = previous == null
                    || previous.transactionCode != exported.transactionCode;
            final String methodName;
            if (isClassDifferent || isCodeDifferent) {
                String resolvedCode = resolveTransactionCode(
                        getDefaultTransactionName, exported.transactionCode);
                methodName = resolvedCode == null
                        ? String.valueOf(exported.transactionCode)
                        : resolvedCode;
            } else {
                methodName = previousMethodName;
            }
            previousMethodName = methodName;
            exported.methodName = methodName;
        }

        // Debug entries added to help validate the data.
        if (mAddDebugEntries && mBatteryStopwatch != null) {
            resultCallStats.add(createDebugEntry("start_time_millis", mStartElapsedTime));
            resultCallStats.add(createDebugEntry("end_time_millis", SystemClock.elapsedRealtime()));
            resultCallStats.add(
                    createDebugEntry("battery_time_millis", mBatteryStopwatch.getMillis()));
        }

        return resultCallStats;
    }

    private ExportedCallStat createDebugEntry(String variableName, long value) {
        final int uid = Process.myUid();
        final ExportedCallStat callStat = new ExportedCallStat();
        callStat.className = "";
        callStat.workSourceUid = uid;
        callStat.callingUid = uid;
        callStat.recordedCallCount = 1;
        callStat.callCount = 1;
        callStat.methodName = DEBUG_ENTRY_PREFIX + variableName;
        callStat.latencyMicros = value;
        return callStat;
    }

    /** @hide */
    public ArrayMap<String, Integer> getExportedExceptionStats() {
        synchronized (mLock) {
            return new ArrayMap(mExceptionCounts);
        }
    }

    /** Writes the collected statistics to the supplied {@link PrintWriter}.*/
    public void dump(PrintWriter pw, AppIdToPackageMap packageMap, boolean verbose) {
        synchronized (mLock) {
            dumpLocked(pw, packageMap, verbose);
        }
    }

    private void dumpLocked(PrintWriter pw, AppIdToPackageMap packageMap, boolean verbose) {
        long totalCallsCount = 0;
        long totalRecordedCallsCount = 0;
        long totalCpuTime = 0;
        pw.print("Start time: ");
        pw.println(DateFormat.format("yyyy-MM-dd HH:mm:ss", mStartCurrentTime));
        pw.print("On battery time (ms): ");
        pw.println(mBatteryStopwatch != null ? mBatteryStopwatch.getMillis() : 0);
        pw.println("Sampling interval period: " + mPeriodicSamplingInterval);
        final List<UidEntry> entries = new ArrayList<>();

        final int uidEntriesSize = mUidEntries.size();
        for (int i = 0; i < uidEntriesSize; i++) {
            UidEntry e = mUidEntries.valueAt(i);
            entries.add(e);
            totalCpuTime += e.cpuTimeMicros;
            totalRecordedCallsCount += e.recordedCallCount;
            totalCallsCount += e.callCount;
        }

        entries.sort(Comparator.<UidEntry>comparingDouble(value -> value.cpuTimeMicros).reversed());
        final String datasetSizeDesc = verbose ? "" : "(top 90% by cpu time) ";
        final StringBuilder sb = new StringBuilder();
        pw.println("Per-UID raw data " + datasetSizeDesc
                + "(package/uid, worksource, call_desc, screen_interactive, "
                + "cpu_time_micros, max_cpu_time_micros, "
                + "latency_time_micros, max_latency_time_micros, exception_count, "
                + "max_request_size_bytes, max_reply_size_bytes, recorded_call_count, "
                + "call_count):");
        final List<ExportedCallStat> exportedCallStats = getExportedCallStats();
        exportedCallStats.sort(BinderCallsStats::compareByCpuDesc);
        for (ExportedCallStat e : exportedCallStats) {
            if (e.methodName.startsWith(DEBUG_ENTRY_PREFIX)) {
                // Do not dump debug entries.
                continue;
            }
            sb.setLength(0);
            sb.append("    ")
                    .append(packageMap.mapUid(e.callingUid))
                    .append(',')
                    .append(packageMap.mapUid(e.workSourceUid))
                    .append(',').append(e.className)
                    .append('#').append(e.methodName)
                    .append(',').append(e.screenInteractive)
                    .append(',').append(e.cpuTimeMicros)
                    .append(',').append(e.maxCpuTimeMicros)
                    .append(',').append(e.latencyMicros)
                    .append(',').append(e.maxLatencyMicros)
                    .append(',').append(mDetailedTracking ? e.exceptionCount : '_')
                    .append(',').append(mDetailedTracking ? e.maxRequestSizeBytes : '_')
                    .append(',').append(mDetailedTracking ? e.maxReplySizeBytes : '_')
                    .append(',').append(e.recordedCallCount)
                    .append(',').append(e.callCount);
            pw.println(sb);
        }
        pw.println();
        pw.println("Per-UID Summary " + datasetSizeDesc
                + "(cpu_time, % of total cpu_time, recorded_call_count, call_count, package/uid):");
        final List<UidEntry> summaryEntries = verbose ? entries
                : getHighestValues(entries, value -> value.cpuTimeMicros, 0.9);
        for (UidEntry entry : summaryEntries) {
            String uidStr = packageMap.mapUid(entry.workSourceUid);
            pw.println(String.format("  %10d %3.0f%% %8d %8d %s",
                    entry.cpuTimeMicros, 100d * entry.cpuTimeMicros / totalCpuTime,
                    entry.recordedCallCount, entry.callCount, uidStr));
        }
        pw.println();
        pw.println(String.format("  Summary: total_cpu_time=%d, "
                        + "calls_count=%d, avg_call_cpu_time=%.0f",
                totalCpuTime, totalCallsCount, (double) totalCpuTime / totalRecordedCallsCount));
        pw.println();

        pw.println("Exceptions thrown (exception_count, class_name):");
        final List<Pair<String, Integer>> exceptionEntries = new ArrayList<>();
        // We cannot use new ArrayList(Collection) constructor because MapCollections does not
        // implement toArray method.
        mExceptionCounts.entrySet().iterator().forEachRemaining(
                (e) -> exceptionEntries.add(Pair.create(e.getKey(), e.getValue())));
        exceptionEntries.sort((e1, e2) -> Integer.compare(e2.second, e1.second));
        for (Pair<String, Integer> entry : exceptionEntries) {
            pw.println(String.format("  %6d %s", entry.second, entry.first));
        }

        if (mPeriodicSamplingInterval != 1) {
            pw.println("");
            pw.println("/!\\ Displayed data is sampled. See sampling interval at the top.");
        }
    }

    protected long getThreadTimeMicro() {
        return SystemClock.currentThreadTimeMicro();
    }

    protected int getCallingUid() {
        return Binder.getCallingUid();
    }

    protected long getElapsedRealtimeMicro() {
        return SystemClock.elapsedRealtimeNanos() / 1000;
    }

    protected boolean shouldRecordDetailedData() {
        return mRandom.nextInt() % mPeriodicSamplingInterval == 0;
    }

    /**
     * Sets to true to collect all the data.
     */
    public void setDetailedTracking(boolean enabled) {
        synchronized (mLock) {
            if (enabled != mDetailedTracking) {
                mDetailedTracking = enabled;
                reset();
            }
        }
    }

    /**
     * Whether to track the screen state.
     */
    public void setTrackScreenInteractive(boolean enabled) {
        synchronized (mLock) {
            if (enabled != mTrackScreenInteractive) {
                mTrackScreenInteractive = enabled;
                reset();
            }
        }
    }

    /**
     * Whether to track direct caller uid.
     */
    public void setTrackDirectCallerUid(boolean enabled) {
        synchronized (mLock) {
            if (enabled != mTrackDirectCallingUid) {
                mTrackDirectCallingUid = enabled;
                reset();
            }
        }
    }

    public void setAddDebugEntries(boolean addDebugEntries) {
        mAddDebugEntries = addDebugEntries;
    }

    /**
     * Sets the maximum number of items to track.
     */
    public void setMaxBinderCallStats(int maxKeys) {
        if (maxKeys <= 0) {
            Slog.w(TAG, "Ignored invalid max value (value must be positive): "
                    + maxKeys);
            return;
        }

        synchronized (mLock) {
            if (maxKeys != mMaxBinderCallStatsCount) {
                mMaxBinderCallStatsCount = maxKeys;
                reset();
            }
        }
    }

    public void setSamplingInterval(int samplingInterval) {
        if (samplingInterval <= 0) {
            Slog.w(TAG, "Ignored invalid sampling interval (value must be positive): "
                    + samplingInterval);
            return;
        }

        synchronized (mLock) {
            if (samplingInterval != mPeriodicSamplingInterval) {
                mPeriodicSamplingInterval = samplingInterval;
                reset();
            }
        }
    }

    public void reset() {
        synchronized (mLock) {
            mCallStatsCount = 0;
            mUidEntries.clear();
            mExceptionCounts.clear();
            mStartCurrentTime = System.currentTimeMillis();
            mStartElapsedTime = SystemClock.elapsedRealtime();
            if (mBatteryStopwatch != null) {
                mBatteryStopwatch.reset();
            }
        }
    }

    /**
     * Aggregated data by uid/class/method to be sent through statsd.
     */
    public static class ExportedCallStat {
        public int callingUid;
        public int workSourceUid;
        public String className;
        public String methodName;
        public boolean screenInteractive;
        public long cpuTimeMicros;
        public long maxCpuTimeMicros;
        public long latencyMicros;
        public long maxLatencyMicros;
        public long callCount;
        public long recordedCallCount;
        public long maxRequestSizeBytes;
        public long maxReplySizeBytes;
        public long exceptionCount;

        // Used internally.
        Class<? extends Binder> binderClass;
        int transactionCode;
    }

    @VisibleForTesting
    public static class CallStat {
        // The UID who executed the transaction (i.e. Binder#getCallingUid).
        public final int callingUid;
        public final Class<? extends Binder> binderClass;
        public final int transactionCode;
        // True if the screen was interactive when the call ended.
        public final boolean screenInteractive;
        // Number of calls for which we collected data for. We do not record data for all the calls
        // when sampling is on.
        public long recordedCallCount;
        // Roughly the real number of total calls. We only track only track the API call count once
        // at least one non-sampled count happened.
        public long callCount;
        // Total CPU of all for all the recorded calls.
        // Approximate total CPU usage can be computed by
        // cpuTimeMicros * callCount / recordedCallCount
        public long cpuTimeMicros;
        public long maxCpuTimeMicros;
        // Total latency of all for all the recorded calls.
        // Approximate average latency can be computed by
        // latencyMicros * callCount / recordedCallCount
        public long latencyMicros;
        public long maxLatencyMicros;
        // The following fields are only computed if mDetailedTracking is set.
        public long maxRequestSizeBytes;
        public long maxReplySizeBytes;
        public long exceptionCount;

        CallStat(int callingUid, Class<? extends Binder> binderClass, int transactionCode,
                boolean screenInteractive) {
            this.callingUid = callingUid;
            this.binderClass = binderClass;
            this.transactionCode = transactionCode;
            this.screenInteractive = screenInteractive;
        }
    }

    /** Key used to store CallStat object in a Map. */
    public static class CallStatKey {
        public int callingUid;
        public Class<? extends Binder> binderClass;
        public int transactionCode;
        private boolean screenInteractive;

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }

            final CallStatKey key = (CallStatKey) o;
            return callingUid == key.callingUid
                    && transactionCode == key.transactionCode
                    && screenInteractive == key.screenInteractive
                    && (binderClass.equals(key.binderClass));
        }

        @Override
        public int hashCode() {
            int result = binderClass.hashCode();
            result = 31 * result + transactionCode;
            result = 31 * result + callingUid;
            result = 31 * result + (screenInteractive ? 1231 : 1237);
            return result;
        }
    }


    @VisibleForTesting
    public static class UidEntry {
        // The UID who is responsible for the binder transaction. If the bluetooth process execute a
        // transaction on behalf of app foo, the workSourceUid will be the uid of app foo.
        public int workSourceUid;
        // Number of calls for which we collected data for. We do not record data for all the calls
        // when sampling is on.
        public long recordedCallCount;
        // Real number of total calls.
        public long callCount;
        // Total CPU of all for all the recorded calls.
        // Approximate total CPU usage can be computed by
        // cpuTimeMicros * callCount / recordedCallCount
        public long cpuTimeMicros;

        UidEntry(int uid) {
            this.workSourceUid = uid;
        }

        // Aggregate time spent per each call name: call_desc -> cpu_time_micros
        private Map<CallStatKey, CallStat> mCallStats = new ArrayMap<>();
        private CallStatKey mTempKey = new CallStatKey();

        @Nullable
        CallStat get(int callingUid, Class<? extends Binder> binderClass, int transactionCode,
                boolean screenInteractive) {
            // Use a global temporary key to avoid creating new objects for every lookup.
            mTempKey.callingUid = callingUid;
            mTempKey.binderClass = binderClass;
            mTempKey.transactionCode = transactionCode;
            mTempKey.screenInteractive = screenInteractive;
            return mCallStats.get(mTempKey);
        }

        CallStat getOrCreate(int callingUid, Class<? extends Binder> binderClass,
                int transactionCode, boolean screenInteractive, boolean maxCallStatsReached) {
            CallStat mapCallStat = get(callingUid, binderClass, transactionCode, screenInteractive);
            // Only create CallStat if it's a new entry, otherwise update existing instance.
            if (mapCallStat == null) {
                if (maxCallStatsReached) {
                    mapCallStat = get(OVERFLOW_DIRECT_CALLING_UID, OVERFLOW_BINDER,
                            OVERFLOW_TRANSACTION_CODE, OVERFLOW_SCREEN_INTERACTIVE);
                    if (mapCallStat != null) {
                        return mapCallStat;
                    }

                    callingUid = OVERFLOW_DIRECT_CALLING_UID;
                    binderClass = OVERFLOW_BINDER;
                    transactionCode = OVERFLOW_TRANSACTION_CODE;
                    screenInteractive = OVERFLOW_SCREEN_INTERACTIVE;
                }

                mapCallStat = new CallStat(callingUid, binderClass, transactionCode,
                        screenInteractive);
                CallStatKey key = new CallStatKey();
                key.callingUid = callingUid;
                key.binderClass = binderClass;
                key.transactionCode = transactionCode;
                key.screenInteractive = screenInteractive;
                mCallStats.put(key, mapCallStat);
            }
            return mapCallStat;
        }

        /**
         * Returns list of calls sorted by CPU time
         */
        public Collection<CallStat> getCallStatsList() {
            return mCallStats.values();
        }

        @Override
        public String toString() {
            return "UidEntry{" +
                    "cpuTimeMicros=" + cpuTimeMicros +
                    ", callCount=" + callCount +
                    ", mCallStats=" + mCallStats +
                    '}';
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }

            UidEntry uidEntry = (UidEntry) o;
            return workSourceUid == uidEntry.workSourceUid;
        }

        @Override
        public int hashCode() {
            return workSourceUid;
        }
    }

    @VisibleForTesting
    public SparseArray<UidEntry> getUidEntries() {
        return mUidEntries;
    }

    @VisibleForTesting
    public ArrayMap<String, Integer> getExceptionCounts() {
        return mExceptionCounts;
    }

    @VisibleForTesting
    public static <T> List<T> getHighestValues(List<T> list, ToDoubleFunction<T> toDouble,
            double percentile) {
        List<T> sortedList = new ArrayList<>(list);
        sortedList.sort(Comparator.comparingDouble(toDouble).reversed());
        double total = 0;
        for (T item : list) {
            total += toDouble.applyAsDouble(item);
        }
        List<T> result = new ArrayList<>();
        double runningSum = 0;
        for (T item : sortedList) {
            if (runningSum > percentile * total) {
                break;
            }
            result.add(item);
            runningSum += toDouble.applyAsDouble(item);
        }
        return result;
    }

    private static int compareByCpuDesc(
            ExportedCallStat a, ExportedCallStat b) {
        return Long.compare(b.cpuTimeMicros, a.cpuTimeMicros);
    }

    private static int compareByBinderClassAndCode(
            ExportedCallStat a, ExportedCallStat b) {
        int result = a.className.compareTo(b.className);
        return result != 0
                ? result
                : Integer.compare(a.transactionCode, b.transactionCode);
    }
}