diff options
6 files changed, 288 insertions, 28 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; } } diff --git a/core/tests/coretests/src/com/android/internal/os/BinderCallsStatsTest.java b/core/tests/coretests/src/com/android/internal/os/BinderCallsStatsTest.java index 1156120217aa..cec62164e57a 100644 --- a/core/tests/coretests/src/com/android/internal/os/BinderCallsStatsTest.java +++ b/core/tests/coretests/src/com/android/internal/os/BinderCallsStatsTest.java @@ -764,7 +764,7 @@ public class BinderCallsStatsTest { bcs.elapsedTime += 20; bcs.callEnded(callSession, REQUEST_SIZE, REPLY_SIZE, WORKSOURCE_UID); - assertEquals(1, bcs.getLatencyObserver().getLatencySamples().size()); + assertEquals(1, bcs.getLatencyObserver().getLatencyHistograms().size()); } @Test @@ -778,7 +778,7 @@ public class BinderCallsStatsTest { bcs.elapsedTime += 20; bcs.callEnded(callSession, REQUEST_SIZE, REPLY_SIZE, WORKSOURCE_UID); - assertEquals(0, bcs.getLatencyObserver().getLatencySamples().size()); + assertEquals(0, bcs.getLatencyObserver().getLatencyHistograms().size()); } class TestBinderCallsStats extends BinderCallsStats { diff --git a/core/tests/coretests/src/com/android/internal/os/BinderLatencyBucketsTest.java b/core/tests/coretests/src/com/android/internal/os/BinderLatencyBucketsTest.java new file mode 100644 index 000000000000..00443a967c79 --- /dev/null +++ b/core/tests/coretests/src/com/android/internal/os/BinderLatencyBucketsTest.java @@ -0,0 +1,69 @@ +/* + * Copyright (C) 2018 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 static com.google.common.truth.Truth.assertThat; + +import static org.junit.Assert.assertEquals; + +import android.platform.test.annotations.Presubmit; + +import androidx.test.filters.SmallTest; +import androidx.test.runner.AndroidJUnit4; + +import org.junit.Test; +import org.junit.runner.RunWith; + +@SmallTest +@RunWith(AndroidJUnit4.class) +@Presubmit +public class BinderLatencyBucketsTest { + @Test + public void testBucketThresholds() { + BinderLatencyBuckets latencyBuckets = new BinderLatencyBuckets(10, 2, 1.45f); + assertThat(latencyBuckets.getBuckets()) + .containsExactly(2, 3, 4, 6, 8, 12, 18, 26, 39) + .inOrder(); + } + + @Test + public void testSampleAssignment() { + BinderLatencyBuckets latencyBuckets = new BinderLatencyBuckets(10, 2, 1.45f); + assertEquals(0, latencyBuckets.sampleToBucket(0)); + assertEquals(0, latencyBuckets.sampleToBucket(1)); + assertEquals(1, latencyBuckets.sampleToBucket(2)); + assertEquals(2, latencyBuckets.sampleToBucket(3)); + assertEquals(3, latencyBuckets.sampleToBucket(4)); + assertEquals(5, latencyBuckets.sampleToBucket(9)); + assertEquals(6, latencyBuckets.sampleToBucket(13)); + assertEquals(7, latencyBuckets.sampleToBucket(25)); + assertEquals(9, latencyBuckets.sampleToBucket(100)); + } + + @Test + public void testMaxIntBuckets() { + BinderLatencyBuckets latencyBuckets = new BinderLatencyBuckets(5, Integer.MAX_VALUE / 2, 2); + assertThat(latencyBuckets.getBuckets()) + .containsExactly(Integer.MAX_VALUE / 2, Integer.MAX_VALUE - 1) + .inOrder(); + + assertEquals(0, latencyBuckets.sampleToBucket(0)); + assertEquals(0, latencyBuckets.sampleToBucket(Integer.MAX_VALUE / 2 - 1)); + assertEquals(1, latencyBuckets.sampleToBucket(Integer.MAX_VALUE - 2)); + assertEquals(2, latencyBuckets.sampleToBucket(Integer.MAX_VALUE)); + } +} diff --git a/core/tests/coretests/src/com/android/internal/os/BinderLatencyObserverTest.java b/core/tests/coretests/src/com/android/internal/os/BinderLatencyObserverTest.java index 36915a205ee0..f65fb9583d6c 100644 --- a/core/tests/coretests/src/com/android/internal/os/BinderLatencyObserverTest.java +++ b/core/tests/coretests/src/com/android/internal/os/BinderLatencyObserverTest.java @@ -33,7 +33,6 @@ import com.android.internal.os.BinderLatencyObserver.LatencyDims; import org.junit.Test; import org.junit.runner.RunWith; -import java.util.ArrayList; import java.util.Arrays; import java.util.Random; @@ -44,6 +43,7 @@ public class BinderLatencyObserverTest { @Test public void testLatencyCollectionWithMultipleClasses() { TestBinderLatencyObserver blo = new TestBinderLatencyObserver(); + blo.setHistogramBucketsParams(5, 5, 1.125f); Binder binder = new Binder(); CallSession callSession = new CallSession(); @@ -51,20 +51,24 @@ public class BinderLatencyObserverTest { callSession.transactionCode = 1; blo.callEnded(callSession); blo.callEnded(callSession); + blo.callEnded(callSession); callSession.transactionCode = 2; blo.callEnded(callSession); + blo.callEnded(callSession); - ArrayMap<LatencyDims, ArrayList<Long>> latencySamples = blo.getLatencySamples(); - assertEquals(2, latencySamples.keySet().size()); - assertThat(latencySamples.get(new LatencyDims(binder.getClass(), 1))) - .containsExactlyElementsIn(Arrays.asList(1L, 2L)); - assertThat(latencySamples.get(new LatencyDims(binder.getClass(), 2))).containsExactly(3L); + ArrayMap<LatencyDims, int[]> latencyHistograms = blo.getLatencyHistograms(); + assertEquals(2, latencyHistograms.keySet().size()); + assertThat(latencyHistograms.get(new LatencyDims(binder.getClass(), 1))) + .asList().containsExactly(2, 0, 1, 0, 0).inOrder(); + assertThat(latencyHistograms.get(new LatencyDims(binder.getClass(), 2))) + .asList().containsExactly(0, 0, 0, 0, 2).inOrder(); } @Test public void testSampling() { TestBinderLatencyObserver blo = new TestBinderLatencyObserver(); blo.setSamplingInterval(2); + blo.setHistogramBucketsParams(5, 5, 1.125f); Binder binder = new Binder(); CallSession callSession = new CallSession(); @@ -74,17 +78,58 @@ public class BinderLatencyObserverTest { callSession.transactionCode = 2; blo.callEnded(callSession); - ArrayMap<LatencyDims, ArrayList<Long>> latencySamples = blo.getLatencySamples(); - assertEquals(1, latencySamples.size()); - LatencyDims dims = latencySamples.keySet().iterator().next(); + ArrayMap<LatencyDims, int[]> latencyHistograms = blo.getLatencyHistograms(); + assertEquals(1, latencyHistograms.size()); + LatencyDims dims = latencyHistograms.keySet().iterator().next(); assertEquals(binder.getClass(), dims.getBinderClass()); assertEquals(1, dims.getTransactionCode()); - ArrayList<Long> values = latencySamples.get(dims); - assertThat(values).containsExactly(1L); + assertThat(latencyHistograms.get(dims)).asList().containsExactly(1, 0, 0, 0, 0).inOrder(); + } + + @Test + public void testTooCallLengthOverflow() { + TestBinderLatencyObserver blo = new TestBinderLatencyObserver(); + blo.setElapsedTime(2L + (long) Integer.MAX_VALUE); + blo.setHistogramBucketsParams(5, 5, 1.125f); + + Binder binder = new Binder(); + CallSession callSession = new CallSession(); + callSession.binderClass = binder.getClass(); + callSession.transactionCode = 1; + blo.callEnded(callSession); + + // The long call should be capped to maxint (to not overflow) and placed in the last bucket. + assertThat(blo.getLatencyHistograms() + .get(new LatencyDims(binder.getClass(), 1))) + .asList().containsExactly(0, 0, 0, 0, 1) + .inOrder(); + } + + @Test + public void testHistogramBucketOverflow() { + TestBinderLatencyObserver blo = new TestBinderLatencyObserver(); + blo.setHistogramBucketsParams(3, 5, 1.125f); + + Binder binder = new Binder(); + CallSession callSession = new CallSession(); + callSession.binderClass = binder.getClass(); + callSession.transactionCode = 1; + blo.callEnded(callSession); + + LatencyDims dims = new LatencyDims(binder.getClass(), 1); + // Fill the buckets with maxint. + Arrays.fill(blo.getLatencyHistograms().get(dims), Integer.MAX_VALUE); + assertThat(blo.getLatencyHistograms().get(dims)) + .asList().containsExactly(Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE); + // Try to add another sample. + blo.callEnded(callSession); + // Make sure the buckets don't overflow. + assertThat(blo.getLatencyHistograms().get(dims)) + .asList().containsExactly(Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE); } public static class TestBinderLatencyObserver extends BinderLatencyObserver { - private long mElapsedTimeCallCount = 0; + private long mElapsedTime = 0; TestBinderLatencyObserver() { // Make random generator not random. @@ -104,7 +149,12 @@ public class BinderLatencyObserverTest { @Override protected long getElapsedRealtimeMicro() { - return ++mElapsedTimeCallCount; + mElapsedTime += 2; + return mElapsedTime; + } + + public void setElapsedTime(long time) { + mElapsedTime = time; } } } diff --git a/services/core/java/com/android/server/BinderCallsStatsService.java b/services/core/java/com/android/server/BinderCallsStatsService.java index 9c8582f78134..f4a8f372bc36 100644 --- a/services/core/java/com/android/server/BinderCallsStatsService.java +++ b/services/core/java/com/android/server/BinderCallsStatsService.java @@ -133,6 +133,12 @@ public class BinderCallsStatsService extends Binder { private static final String SETTINGS_COLLECT_LATENCY_DATA_KEY = "collect_Latency_data"; private static final String SETTINGS_LATENCY_OBSERVER_SAMPLING_INTERVAL_KEY = "latency_observer_sampling_interval"; + private static final String SETTINGS_LATENCY_HISTOGRAM_BUCKET_COUNT_KEY = + "latency_histogram_bucket_count"; + private static final String SETTINGS_LATENCY_HISTOGRAM_FIRST_BUCKET_SIZE_KEY = + "latency_histogram_first_bucket_size"; + private static final String SETTINGS_LATENCY_HISTOGRAM_BUCKET_SCALE_FACTOR_KEY = + "latency_histogram_bucket_scale_factor"; private boolean mEnabled; private final Uri mUri = Settings.Global.getUriFor(Settings.Global.BINDER_CALLS_STATS); @@ -190,9 +196,20 @@ public class BinderCallsStatsService extends Binder { mParser.getBoolean(SETTINGS_COLLECT_LATENCY_DATA_KEY, BinderCallsStats.DEFAULT_COLLECT_LATENCY_DATA)); // Binder latency observer settings. - mBinderCallsStats.getLatencyObserver().setSamplingInterval(mParser.getInt( + BinderLatencyObserver binderLatencyObserver = mBinderCallsStats.getLatencyObserver(); + binderLatencyObserver.setSamplingInterval(mParser.getInt( SETTINGS_LATENCY_OBSERVER_SAMPLING_INTERVAL_KEY, BinderLatencyObserver.PERIODIC_SAMPLING_INTERVAL_DEFAULT)); + binderLatencyObserver.setHistogramBucketsParams( + mParser.getInt( + SETTINGS_LATENCY_HISTOGRAM_BUCKET_COUNT_KEY, + BinderLatencyObserver.BUCKET_COUNT_DEFAULT), + mParser.getInt( + SETTINGS_LATENCY_HISTOGRAM_FIRST_BUCKET_SIZE_KEY, + BinderLatencyObserver.FIRST_BUCKET_SIZE_DEFAULT), + mParser.getFloat( + SETTINGS_LATENCY_HISTOGRAM_BUCKET_SCALE_FACTOR_KEY, + BinderLatencyObserver.BUCKET_SCALE_FACTOR_DEFAULT)); final boolean enabled = |