Store the collected binder latency samples in buckets to form a

histogram. Add the ability to generate histograms with varying bucket
counts and sizes.

This is a direct cherrypick with no changes

Bug: 179999191
Test: unit tests

Change-Id: I58d3cbdd9ae43c8da121ec41d994b077e29bb371
Merged-In: I58d3cbdd9ae43c8da121ec41d994b077e29bb371
(cherry picked from commit dcd3dc69a1d707a6c7185a57bee0cfc50c9f3411)

2 files changed, 136 insertions, 12 deletions

diff --git a/core/java/com/android/internal/os/BinderLatencyBuckets.java b/core/java/com/android/internal/os/BinderLatencyBuckets.java
new file mode 100644
index 000000000000..bdee4ca8a6b8
--- /dev/null
+++ b/core/java/com/android/internal/os/BinderLatencyBuckets.java
@@ -0,0 +1,91 @@
+/*
+ * 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.util.Slog;
+
+import com.android.internal.annotations.VisibleForTesting;
+
+import java.util.ArrayList;
+import java.util.Collections;
+
+/**
+ * Generates the bucket thresholds (with a custom logarithmic scale) for a histogram to store
+ * latency samples in.
+ */
+public class BinderLatencyBuckets {
+    private static final String TAG = "BinderLatencyBuckets";
+    private ArrayList<Integer> mBuckets;
+
+    /**
+     * @param bucketCount      the number of buckets the histogram should have
+     * @param firstBucketSize  the size of the first bucket (used to avoid excessive small buckets)
+     * @param scaleFactor      the rate in which each consecutive bucket increases (before rounding)
+     */
+    public BinderLatencyBuckets(int bucketCount, int firstBucketSize, float scaleFactor) {
+        mBuckets = new ArrayList<>(bucketCount - 1);
+        mBuckets.add(firstBucketSize);
+
+        // Last value and the target are disjoint as we never want to create buckets smaller than 1.
+        double lastTarget = firstBucketSize;
+        int lastValue = firstBucketSize;
+
+        // First bucket is already created and the last bucket is anything greater than the final
+        // bucket in the list, so create 'bucketCount' - 2 buckets.
+        for (int i = 1; i < bucketCount - 1; i++) {
+            // Increase the target bucket limit value by the scale factor.
+            double nextTarget = lastTarget * scaleFactor;
+
+            if (nextTarget > Integer.MAX_VALUE || lastValue == Integer.MAX_VALUE) {
+                // Do not throw an exception here as this should not affect binder calls.
+                Slog.w(TAG, "Attempted to create a bucket larger than maxint");
+                return;
+            }
+
+            if ((int) nextTarget > lastValue) {
+                // Convert the target bucket limit value to an integer.
+                mBuckets.add((int) nextTarget);
+                lastValue = (int) nextTarget;
+            } else {
+                // Avoid creating redundant buckets, so bucket size should be 1 at a minimum.
+                mBuckets.add(lastValue + 1);
+                lastValue = lastValue + 1;
+            }
+            lastTarget = nextTarget;
+        }
+    }
+
+    /** Gets the bucket index to insert the provided sample in. */
+    public int sampleToBucket(int sample) {
+        if (sample > mBuckets.get(mBuckets.size() - 1)) {
+            return mBuckets.size();
+        }
+
+        // Binary search returns the element index if it is contained in the list - in this case the
+        // correct bucket is the index after as we use [minValue, maxValue) for bucket boundaries.
+        // Otherwise, it returns (-(insertion point) - 1), where insertion point is the point where
+        // to insert the element so that the array remains sorted - in this case the bucket index
+        // is the insertion point.
+        int searchResult = Collections.binarySearch(mBuckets, sample);
+        return searchResult < 0 ? -(1 + searchResult) : searchResult + 1;
+    }
+
+    @VisibleForTesting
+    public ArrayList<Integer> getBuckets() {
+        return mBuckets;
+    }
+}
diff --git a/core/java/com/android/internal/os/BinderLatencyObserver.java b/core/java/com/android/internal/os/BinderLatencyObserver.java
index 92b495284de2..59cc66d79bce 100644
--- a/core/java/com/android/internal/os/BinderLatencyObserver.java
+++ b/core/java/com/android/internal/os/BinderLatencyObserver.java
@@ -26,7 +26,6 @@ import com.android.internal.annotations.GuardedBy;
 import com.android.internal.annotations.VisibleForTesting;
 import com.android.internal.os.BinderInternal.CallSession;
 
-import java.util.ArrayList;
 import java.util.Random;
 
 /** Collects statistics about Binder call latency per calling API and method. */
@@ -34,18 +33,25 @@ public class BinderLatencyObserver {
     private static final String TAG = "BinderLatencyObserver";
     public static final int PERIODIC_SAMPLING_INTERVAL_DEFAULT = 10;
 
-    // This is not the final data structure - we will eventually store latency histograms instead of
-    // raw samples as it is much more memory / disk space efficient.
-    // TODO(b/179999191): change this to store the histogram.
-    // TODO(b/179999191): pre allocate the array size so we would not have to resize this.
+    // Histogram buckets parameters.
+    public static final int BUCKET_COUNT_DEFAULT = 100;
+    public static final int FIRST_BUCKET_SIZE_DEFAULT = 5;
+    public static final float BUCKET_SCALE_FACTOR_DEFAULT = 1.125f;
+
     @GuardedBy("mLock")
-    private final ArrayMap<LatencyDims, ArrayList<Long>> mLatencySamples = new ArrayMap<>();
+    private final ArrayMap<LatencyDims, int[]> mLatencyHistograms = new ArrayMap<>();
     private final Object mLock = new Object();
 
     // 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 mBucketCount = BUCKET_COUNT_DEFAULT;
+    private int mFirstBucketSize = FIRST_BUCKET_SIZE_DEFAULT;
+    private float mBucketScaleFactor = BUCKET_SCALE_FACTOR_DEFAULT;
+
     private final Random mRandom;
+    private BinderLatencyBuckets mLatencyBuckets;
 
     /** Injector for {@link BinderLatencyObserver}. */
     public static class Injector {
@@ -56,6 +62,8 @@ public class BinderLatencyObserver {
 
     public BinderLatencyObserver(Injector injector) {
         mRandom = injector.getRandomGenerator();
+        mLatencyBuckets = new BinderLatencyBuckets(
+            mBucketCount, mFirstBucketSize, mBucketScaleFactor);
     }
 
     /** Should be called when a Binder call completes, will store latency data. */
@@ -67,12 +75,21 @@ public class BinderLatencyObserver {
         LatencyDims dims = new LatencyDims(s.binderClass, s.transactionCode);
         long callDuration = getElapsedRealtimeMicro() - s.timeStarted;
 
+        // Find the bucket this sample should go to.
+        int bucketIdx = mLatencyBuckets.sampleToBucket(
+                callDuration > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) callDuration);
+
         synchronized (mLock) {
-            if (!mLatencySamples.containsKey(dims)) {
-                mLatencySamples.put(dims, new ArrayList<Long>());
+            int[] buckets = mLatencyHistograms.get(dims);
+            if (buckets == null) {
+                buckets = new int[mBucketCount];
+                mLatencyHistograms.put(dims, buckets);
             }
 
-            mLatencySamples.get(dims).add(callDuration);
+            // Increment the correct bucket.
+            if (buckets[bucketIdx] < Integer.MAX_VALUE) {
+                buckets[bucketIdx] += 1;
+            }
         }
     }
 
@@ -100,10 +117,26 @@ public class BinderLatencyObserver {
         }
     }
 
+    /** Updates the histogram buckets parameters. */
+    public void setHistogramBucketsParams(
+            int bucketCount, int firstBucketSize, float bucketScaleFactor) {
+        synchronized (mLock) {
+            if (bucketCount != mBucketCount || firstBucketSize != mFirstBucketSize
+                    || bucketScaleFactor != mBucketScaleFactor) {
+                mBucketCount = bucketCount;
+                mFirstBucketSize = firstBucketSize;
+                mBucketScaleFactor = bucketScaleFactor;
+                mLatencyBuckets = new BinderLatencyBuckets(
+                    mBucketCount, mFirstBucketSize, mBucketScaleFactor);
+                reset();
+            }
+        }
+    }
+
     /** Resets the sample collection. */
     public void reset() {
         synchronized (mLock) {
-            mLatencySamples.clear();
+            mLatencyHistograms.clear();
         }
     }
 
@@ -151,7 +184,7 @@ public class BinderLatencyObserver {
     }
 
     @VisibleForTesting
-    public ArrayMap<LatencyDims, ArrayList<Long>> getLatencySamples() {
-        return mLatencySamples;
+    public ArrayMap<LatencyDims, int[]> getLatencyHistograms() {
+        return mLatencyHistograms;
     }
 }