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 17 package com.android.server.wifi.util; 18 19 import android.util.SparseIntArray; 20 21 /** 22 * Utilities for Metrics collections. 23 */ 24 public class MetricsUtils { 25 /** 26 * A generic bucket containing a start, end, and count. The utility classes will convert to 27 * such a generic bucket which can then be copied into the specific bucket of the proto. 28 */ 29 public static class GenericBucket { 30 public long start; 31 public long end; 32 public int count; 33 } 34 35 /** 36 * Specifies a ~log histogram consisting of two levels of buckets - a set of N big buckets: 37 * 38 * Buckets starts at: B + P * M^i, where i=0, ... , N-1 (N big buckets) 39 * Each big bucket is divided into S sub-buckets 40 * 41 * Each (big) bucket is M times bigger than the previous one. 42 * 43 * The buckets are then: 44 * #0: B + P * M^0 with S buckets each of width (P*M^1-P*M^0)/S 45 * #1: B + P * M^1 with S buckets each of width (P*M^2-P*M^1)/S 46 * ... 47 * #N-1: B + P * M^(N-1) with S buckets each of width (P*M^N-P*M^(N-1))/S 48 */ 49 public static class LogHistParms { 50 public LogHistParms(int b, int p, int m, int s, int n) { 51 this.b = b; 52 this.p = p; 53 this.m = m; 54 this.s = s; 55 this.n = n; 56 57 // derived values 58 mLog = Math.log(m); 59 bb = new double[n]; 60 sbw = new double[n]; 61 bb[0] = b + p; 62 sbw[0] = p * (m - 1.0) / (double) s; 63 for (int i = 1; i < n; ++i) { 64 bb[i] = m * (bb[i - 1] - b) + b; 65 sbw[i] = m * sbw[i - 1]; 66 } 67 } 68 69 // spec 70 public int b; 71 public int p; 72 public int m; 73 public int s; 74 public int n; 75 76 // derived 77 public double mLog; 78 public double[] bb; // bucket base 79 public double[] sbw; // sub-bucket width 80 } 81 82 /** 83 * Adds the input value to the log histogram based on the histogram parameters. 84 */ 85 public static int addValueToLogHistogram(long x, SparseIntArray histogram, LogHistParms hp) { 86 double logArg = (double) (x - hp.b) / (double) hp.p; 87 int bigBucketIndex = -1; 88 if (logArg > 0) { 89 bigBucketIndex = (int) (Math.log(logArg) / hp.mLog); 90 } 91 int subBucketIndex; 92 if (bigBucketIndex < 0) { 93 bigBucketIndex = 0; 94 subBucketIndex = 0; 95 } else if (bigBucketIndex >= hp.n) { 96 bigBucketIndex = hp.n - 1; 97 subBucketIndex = hp.s - 1; 98 } else { 99 subBucketIndex = (int) ((x - hp.bb[bigBucketIndex]) / hp.sbw[bigBucketIndex]); 100 if (subBucketIndex >= hp.s) { // probably a rounding error so move to next big bucket 101 bigBucketIndex++; 102 if (bigBucketIndex >= hp.n) { 103 bigBucketIndex = hp.n - 1; 104 subBucketIndex = hp.s - 1; 105 } else { 106 subBucketIndex = (int) ((x - hp.bb[bigBucketIndex]) / hp.sbw[bigBucketIndex]); 107 } 108 } 109 } 110 int key = bigBucketIndex * hp.s + subBucketIndex; 111 112 // note that get() returns 0 if index not there already 113 int newValue = histogram.get(key) + 1; 114 histogram.put(key, newValue); 115 116 return newValue; 117 } 118 119 /** 120 * Converts the log histogram (with the specified histogram parameters) to an array of generic 121 * histogram buckets. 122 */ 123 public static GenericBucket[] logHistogramToGenericBuckets(SparseIntArray histogram, 124 LogHistParms hp) { 125 GenericBucket[] protoArray = new GenericBucket[histogram.size()]; 126 for (int i = 0; i < histogram.size(); ++i) { 127 int key = histogram.keyAt(i); 128 129 protoArray[i] = new GenericBucket(); 130 protoArray[i].start = (long) (hp.bb[key / hp.s] + hp.sbw[key / hp.s] * (key % hp.s)); 131 protoArray[i].end = (long) (protoArray[i].start + hp.sbw[key / hp.s]); 132 protoArray[i].count = histogram.valueAt(i); 133 } 134 135 return protoArray; 136 } 137 138 /** 139 * Adds the input value to the histogram based on the lineaer histogram parameters. 140 * 141 * The 'int[] hp' contains a list of bucket limits. The number of buckets is hp.length() + 1 142 * where buckets are: 143 * - < hp[0] 144 * - [hp[0], hp[1]) 145 * ... 146 * - >= hp[hp.length() - 1] 147 */ 148 public static int addValueToLinearHistogram(int x, SparseIntArray histogram, int[] hp) { 149 int bucket = 0; 150 for (int limit : hp) { 151 if (x >= limit) { 152 bucket++; 153 continue; 154 } 155 break; 156 } 157 158 // note that get() returns 0 if index not there already 159 int newValue = histogram.get(bucket) + 1; 160 histogram.put(bucket, newValue); 161 162 return newValue; 163 } 164 165 /** 166 * Converts the histogram (with the specified linear histogram parameters) to an array of 167 * generic histogram buckets. 168 */ 169 public static GenericBucket[] linearHistogramToGenericBuckets(SparseIntArray histogram, 170 int[] linearHistParams) { 171 GenericBucket[] protoArray = new GenericBucket[histogram.size()]; 172 for (int i = 0; i < histogram.size(); ++i) { 173 int bucket = histogram.keyAt(i); 174 175 protoArray[i] = new GenericBucket(); 176 if (bucket == 0) { 177 protoArray[i].start = Integer.MIN_VALUE; 178 protoArray[i].end = linearHistParams[0]; 179 } else if (bucket != linearHistParams.length) { 180 protoArray[i].start = linearHistParams[bucket - 1]; 181 protoArray[i].end = linearHistParams[bucket]; 182 } else { 183 protoArray[i].start = linearHistParams[linearHistParams.length - 1]; 184 protoArray[i].end = Integer.MAX_VALUE; 185 } 186 protoArray[i].count = histogram.valueAt(i); 187 } 188 189 return protoArray; 190 } 191 } 192
