summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--core/java/com/android/internal/util/TokenBucket.java126
-rw-r--r--core/tests/coretests/src/android/util/TokenBucketTest.java180
2 files changed, 306 insertions, 0 deletions
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(); }
+}
+
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-22 06:42:03 +0000