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 public class BinderLatencyBuckets { 30 private static final String TAG = "BinderLatencyBuckets"; 31 private final int[] mBuckets; 32 33 /** 34 * @param bucketCount the number of buckets the histogram should have 35 * @param firstBucketSize the size of the first bucket (used to avoid excessive small buckets) 36 * @param scaleFactor the rate in which each consecutive bucket increases (before rounding) 37 */ BinderLatencyBuckets(int bucketCount, int firstBucketSize, float scaleFactor)38 public BinderLatencyBuckets(int bucketCount, int firstBucketSize, float scaleFactor) { 39 int[] buffer = new int[bucketCount - 1]; 40 buffer[0] = firstBucketSize; 41 42 // Last value and the target are disjoint as we never want to create buckets smaller than 1. 43 double lastTarget = firstBucketSize; 44 45 // First bucket is already created and the last bucket is anything greater than the final 46 // bucket in the list, so create 'bucketCount' - 2 buckets. 47 for (int i = 1; i < bucketCount - 1; i++) { 48 // Increase the target bucket limit value by the scale factor. 49 double nextTarget = lastTarget * scaleFactor; 50 51 if (nextTarget > Integer.MAX_VALUE) { 52 // Do not throw an exception here as this should not affect binder calls. 53 Slog.w(TAG, "Attempted to create a bucket larger than maxint"); 54 mBuckets = Arrays.copyOfRange(buffer, 0, i); 55 return; 56 } 57 58 if ((int) nextTarget > buffer[i - 1]) { 59 // Convert the target bucket limit value to an integer. 60 buffer[i] = (int) nextTarget; 61 } else { 62 // Avoid creating redundant buckets, so bucket size should be 1 at a minimum. 63 buffer[i] = buffer[i - 1] + 1; 64 } 65 lastTarget = nextTarget; 66 } 67 mBuckets = buffer; 68 } 69 70 /** Gets the bucket index to insert the provided sample in. */ sampleToBucket(int sample)71 public int sampleToBucket(int sample) { 72 if (sample >= mBuckets[mBuckets.length - 1]) { 73 return mBuckets.length; 74 } 75 76 // Binary search returns the element index if it is contained in the list - in this case the 77 // correct bucket is the index after as we use [minValue, maxValue) for bucket boundaries. 78 // Otherwise, it returns (-(insertion point) - 1), where insertion point is the point where 79 // to insert the element so that the array remains sorted - in this case the bucket index 80 // is the insertion point. 81 int searchResult = Arrays.binarySearch(mBuckets, sample); 82 return searchResult < 0 ? -(1 + searchResult) : searchResult + 1; 83 } 84 85 @VisibleForTesting getBuckets()86 public int[] getBuckets() { 87 return mBuckets; 88 } 89 } 90