1 /*
2  * Copyright (C) 2017 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.android.internal.os;
18 
19 import android.util.Slog;
20 
21 import com.android.internal.annotations.VisibleForTesting;
22 
23 import java.util.Arrays;
24 
25 /**
26  * Generates the bucket thresholds (with a custom logarithmic scale) for a histogram to store
27  * latency samples in.
28  */
29 @android.ravenwood.annotation.RavenwoodKeepWholeClass
30 public class BinderLatencyBuckets {
31     private static final String TAG = "BinderLatencyBuckets";
32     private final int[] mBuckets;
33 
34     /**
35      * @param bucketCount      the number of buckets the histogram should have
36      * @param firstBucketSize  the size of the first bucket (used to avoid excessive small buckets)
37      * @param scaleFactor      the rate in which each consecutive bucket increases (before rounding)
38      */
BinderLatencyBuckets(int bucketCount, int firstBucketSize, float scaleFactor)39     public BinderLatencyBuckets(int bucketCount, int firstBucketSize, float scaleFactor) {
40         int[] buffer = new int[bucketCount - 1];
41         buffer[0] = firstBucketSize;
42 
43         // Last value and the target are disjoint as we never want to create buckets smaller than 1.
44         double lastTarget = firstBucketSize;
45 
46         // First bucket is already created and the last bucket is anything greater than the final
47         // bucket in the list, so create 'bucketCount' - 2 buckets.
48         for (int i = 1; i < bucketCount - 1; i++) {
49             // Increase the target bucket limit value by the scale factor.
50             double nextTarget = lastTarget * scaleFactor;
51 
52             if (nextTarget > Integer.MAX_VALUE) {
53                 // Do not throw an exception here as this should not affect binder calls.
54                 Slog.w(TAG, "Attempted to create a bucket larger than maxint");
55                 mBuckets = Arrays.copyOfRange(buffer, 0, i);
56                 return;
57             }
58 
59             if ((int) nextTarget > buffer[i - 1]) {
60                 // Convert the target bucket limit value to an integer.
61                 buffer[i] = (int) nextTarget;
62             } else {
63                 // Avoid creating redundant buckets, so bucket size should be 1 at a minimum.
64                 buffer[i] = buffer[i - 1] + 1;
65             }
66             lastTarget = nextTarget;
67         }
68         mBuckets = buffer;
69     }
70 
71     /** Gets the bucket index to insert the provided sample in. */
sampleToBucket(int sample)72     public int sampleToBucket(int sample) {
73         if (sample >= mBuckets[mBuckets.length - 1]) {
74             return mBuckets.length;
75         }
76 
77         // Binary search returns the element index if it is contained in the list - in this case the
78         // correct bucket is the index after as we use [minValue, maxValue) for bucket boundaries.
79         // Otherwise, it returns (-(insertion point) - 1), where insertion point is the point where
80         // to insert the element so that the array remains sorted - in this case the bucket index
81         // is the insertion point.
82         int searchResult = Arrays.binarySearch(mBuckets, sample);
83         return searchResult < 0 ? -(1 + searchResult) : searchResult + 1;
84     }
85 
86     @VisibleForTesting
getBuckets()87     public int[] getBuckets() {
88         return mBuckets;
89     }
90 }
91