From 05ad47add8796880c5ba18d55ab6d5221f3e708d Mon Sep 17 00:00:00 2001 From: Hugo Benichi Date: Tue, 18 Oct 2016 08:43:30 +0900 Subject: [PATCH] DO NOT MERGE: TokenBucket for rate-limiting and throttling This patch adds a TokenBucket class that can accumulate and distribute tokens over time. Test: comes with unit tests. Bug: 32198637 (cherry picked from commit 998493f0ee39ae0e9ffdea27f48f1b11b0807fcb) Change-Id: I4012ae6d02f7004bceee9a2ba03914f2a2506031 --- .../com/android/internal/util/TokenBucket.java | 126 +++++++++++++++ .../src/android/util/TokenBucketTest.java | 180 +++++++++++++++++++++ 2 files changed, 306 insertions(+) create mode 100644 core/java/com/android/internal/util/TokenBucket.java create mode 100644 core/tests/coretests/src/android/util/TokenBucketTest.java diff --git a/core/java/com/android/internal/util/TokenBucket.java b/core/java/com/android/internal/util/TokenBucket.java new file mode 100644 index 000000000000..effb82ba7a2d --- /dev/null +++ b/core/java/com/android/internal/util/TokenBucket.java @@ -0,0 +1,126 @@ +/* + * Copyright (C) 2016 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.util; + +import android.os.SystemClock; + +import static com.android.internal.util.Preconditions.checkArgumentNonnegative; +import static com.android.internal.util.Preconditions.checkArgumentPositive; + +/** + * A class useful for rate-limiting or throttling that stores and distributes tokens. + * + * A TokenBucket starts with a fixed capacity of tokens, an initial amount of tokens, and + * a fixed filling period (in milliseconds). + * + * For every filling period, the bucket gains one token, up to its maximum capacity from + * which point tokens simply overflow and are lost. Tokens can be obtained one by one or n by n. + * + * The available amount of tokens is computed lazily when the bucket state is inspected. + * Therefore it is purely synchronous and does not involve any asynchronous activity. + * It is not synchronized in any way and not a thread-safe object. + */ +public class TokenBucket { + + private final int mFillDelta; // Time in ms it takes to generate one token. + private final int mCapacity; // Maximum number of tokens that can be stored. + private long mLastFill; // Last time in ms the bucket generated tokens. + private int mAvailable; // Current number of available tokens. + + /** + * Create a new TokenBucket. + * @param deltaMs the time in milliseconds it takes to generate a new token. + * Must be strictly positive. + * @param capacity the maximum token capacity. Must be strictly positive. + * @param tokens the starting amount of token. Must be positive or zero. + */ + public TokenBucket(int deltaMs, int capacity, int tokens) { + mFillDelta = checkArgumentPositive(deltaMs, "deltaMs must be strictly positive"); + mCapacity = checkArgumentPositive(capacity, "capacity must be strictly positive"); + mAvailable = Math.min(checkArgumentNonnegative(tokens), mCapacity); + mLastFill = scaledTime(); + } + + /** + * Create a new TokenBucket that starts completely filled. + * @param deltaMs the time in milliseconds it takes to generate a new token. + * Must be strictly positive. + * @param capacity the maximum token capacity. Must be strictly positive. + */ + public TokenBucket(int deltaMs, int capacity) { + this(deltaMs, capacity, capacity); + } + + /** Reset this TokenBucket and set its number of available tokens. */ + public void reset(int tokens) { + checkArgumentNonnegative(tokens); + mAvailable = Math.min(tokens, mCapacity); + mLastFill = scaledTime(); + } + + /** Returns this TokenBucket maximum token capacity. */ + public int capacity() { + return mCapacity; + } + + /** Returns this TokenBucket currently number of available tokens. */ + public int available() { + fill(); + return mAvailable; + } + + /** Returns true if this TokenBucket as one or more tokens available. */ + public boolean has() { + fill(); + return mAvailable > 0; + } + + /** Consumes a token from this TokenBucket and returns true if a token is available. */ + public boolean get() { + return (get(1) == 1); + } + + /** + * Try to consume many tokens from this TokenBucket. + * @param n the number of tokens to consume. + * @return the number of tokens that were actually consumed. + */ + public int get(int n) { + fill(); + if (n <= 0) { + return 0; + } + if (n > mAvailable) { + int got = mAvailable; + mAvailable = 0; + return got; + } + mAvailable -= n; + return n; + } + + private void fill() { + final long now = scaledTime(); + final int diff = (int) (now - mLastFill); + mAvailable = Math.min(mCapacity, mAvailable + diff); + mLastFill = now; + } + + private long scaledTime() { + return SystemClock.elapsedRealtime() / mFillDelta; + } +} diff --git a/core/tests/coretests/src/android/util/TokenBucketTest.java b/core/tests/coretests/src/android/util/TokenBucketTest.java new file mode 100644 index 000000000000..a053ad33f589 --- /dev/null +++ b/core/tests/coretests/src/android/util/TokenBucketTest.java @@ -0,0 +1,180 @@ +/* + * Copyright (C) 2016 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.util; + +import android.os.SystemClock; +import android.text.format.DateUtils; +import junit.framework.TestCase; + +public class TokenBucketTest extends TestCase { + + static final int FILL_DELTA_VERY_SHORT = 1; + static final int FILL_DELTA_VERY_LONG = Integer.MAX_VALUE; + + public void testArgumentValidation() { + assertThrow(() -> new TokenBucket(0, 1, 1)); + assertThrow(() -> new TokenBucket(1, 0, 1)); + assertThrow(() -> new TokenBucket(1, 1, 0)); + assertThrow(() -> new TokenBucket(0, 1)); + assertThrow(() -> new TokenBucket(1, 0)); + assertThrow(() -> new TokenBucket(-1, 1, 1)); + assertThrow(() -> new TokenBucket(1, -1, 1)); + assertThrow(() -> new TokenBucket(1, 1, -1)); + assertThrow(() -> new TokenBucket(-1, 1)); + assertThrow(() -> new TokenBucket(1, -1)); + + new TokenBucket(1000, 100, 0); + new TokenBucket(1000, 100, 10); + new TokenBucket(5000, 50); + new TokenBucket(5000, 1); + } + + public void testInitialCapacity() { + drain(new TokenBucket(FILL_DELTA_VERY_LONG, 1), 1); + drain(new TokenBucket(FILL_DELTA_VERY_LONG, 10), 10); + drain(new TokenBucket(FILL_DELTA_VERY_LONG, 1000), 1000); + + drain(new TokenBucket(FILL_DELTA_VERY_LONG, 10, 0), 0); + drain(new TokenBucket(FILL_DELTA_VERY_LONG, 10, 3), 3); + drain(new TokenBucket(FILL_DELTA_VERY_LONG, 10, 10), 10); + + drain(new TokenBucket(FILL_DELTA_VERY_LONG, 10, 100), 10); + + drain(new TokenBucket((int)DateUtils.MINUTE_IN_MILLIS, 50), 50); + drain(new TokenBucket((int)DateUtils.HOUR_IN_MILLIS, 10), 10); + drain(new TokenBucket((int)DateUtils.DAY_IN_MILLIS, 200), 200); + } + + public void testReset() { + TokenBucket tb = new TokenBucket(FILL_DELTA_VERY_LONG, 100, 10); + drain(tb, 10); + + tb.reset(50); + drain(tb, 50); + + tb.reset(50); + getOneByOne(tb, 10); + assertTrue(tb.has()); + + tb.reset(30); + drain(tb, 30); + } + + public void testFill() throws Exception { + int delta = 50; + TokenBucket tb = new TokenBucket(delta, 10, 0); + + assertEmpty(tb); + + Thread.sleep(3 * delta / 2); + + assertTrue(tb.has()); + } + + public void testRefill() throws Exception { + TokenBucket tb = new TokenBucket(FILL_DELTA_VERY_SHORT, 10, 10); + + assertEquals(5, tb.get(5)); + assertEquals(5, tb.get(5)); + + while (tb.available() < 10) { + Thread.sleep(2); + } + + assertEquals(10, tb.get(10)); + + while (tb.available() < 10) { + Thread.sleep(2); + } + + assertEquals(10, tb.get(100)); + } + + public void testAverage() throws Exception { + final int delta = 3; + final int want = 60; + + long start = SystemClock.elapsedRealtime(); + TokenBucket tb = new TokenBucket(delta, 20, 0); + + for (int i = 0; i < want; i++) { + while (!tb.has()) { + Thread.sleep(5 * delta); + } + tb.get(); + } + + assertDuration(want * delta, SystemClock.elapsedRealtime() - start); + } + + public void testBurst() throws Exception { + final int delta = 2; + final int capacity = 20; + final int want = 100; + + long start = SystemClock.elapsedRealtime(); + TokenBucket tb = new TokenBucket(delta, capacity, 0); + + int total = 0; + while (total < want) { + while (!tb.has()) { + Thread.sleep(capacity * delta - 2); + } + total += tb.get(tb.available()); + } + + assertDuration(total * delta, SystemClock.elapsedRealtime() - start); + } + + static void getOneByOne(TokenBucket tb, int n) { + while (n > 0) { + assertTrue(tb.has()); + assertTrue(tb.available() >= n); + assertTrue(tb.get()); + assertTrue(tb.available() >= n - 1); + n--; + } + } + + void assertEmpty(TokenBucket tb) { + assertFalse(tb.has()); + assertEquals(0, tb.available()); + assertFalse(tb.get()); + } + + void drain(TokenBucket tb, int n) { + getOneByOne(tb, n); + assertEmpty(tb); + } + + void assertDuration(long expected, long elapsed) { + String msg = String.format( + "expected elapsed time at least %d ms, but was %d ms", expected, elapsed); + elapsed += 1; // one millisecond extra guard + assertTrue(msg, elapsed >= expected); + } + + void assertThrow(Fn fn) { + try { + fn.call(); + fail("expected n exception to be thrown."); + } catch (Throwable t) {} + } + + interface Fn { void call(); } +} + -- 2.11.0