1/* 2 * Copyright (C) 2016 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 17package com.android.internal.util; 18 19import android.os.SystemClock; 20import android.text.format.DateUtils; 21import junit.framework.TestCase; 22 23public class TokenBucketTest extends TestCase { 24 25 static final int FILL_DELTA_VERY_SHORT = 1; 26 static final int FILL_DELTA_VERY_LONG = Integer.MAX_VALUE; 27 28 public void testArgumentValidation() { 29 assertThrow(() -> new TokenBucket(0, 1, 1)); 30 assertThrow(() -> new TokenBucket(1, 0, 1)); 31 assertThrow(() -> new TokenBucket(1, 1, 0)); 32 assertThrow(() -> new TokenBucket(0, 1)); 33 assertThrow(() -> new TokenBucket(1, 0)); 34 assertThrow(() -> new TokenBucket(-1, 1, 1)); 35 assertThrow(() -> new TokenBucket(1, -1, 1)); 36 assertThrow(() -> new TokenBucket(1, 1, -1)); 37 assertThrow(() -> new TokenBucket(-1, 1)); 38 assertThrow(() -> new TokenBucket(1, -1)); 39 40 new TokenBucket(1000, 100, 0); 41 new TokenBucket(1000, 100, 10); 42 new TokenBucket(5000, 50); 43 new TokenBucket(5000, 1); 44 } 45 46 public void testInitialCapacity() { 47 drain(new TokenBucket(FILL_DELTA_VERY_LONG, 1), 1); 48 drain(new TokenBucket(FILL_DELTA_VERY_LONG, 10), 10); 49 drain(new TokenBucket(FILL_DELTA_VERY_LONG, 1000), 1000); 50 51 drain(new TokenBucket(FILL_DELTA_VERY_LONG, 10, 0), 0); 52 drain(new TokenBucket(FILL_DELTA_VERY_LONG, 10, 3), 3); 53 drain(new TokenBucket(FILL_DELTA_VERY_LONG, 10, 10), 10); 54 55 drain(new TokenBucket(FILL_DELTA_VERY_LONG, 10, 100), 10); 56 57 drain(new TokenBucket((int)DateUtils.MINUTE_IN_MILLIS, 50), 50); 58 drain(new TokenBucket((int)DateUtils.HOUR_IN_MILLIS, 10), 10); 59 drain(new TokenBucket((int)DateUtils.DAY_IN_MILLIS, 200), 200); 60 } 61 62 public void testReset() { 63 TokenBucket tb = new TokenBucket(FILL_DELTA_VERY_LONG, 100, 10); 64 drain(tb, 10); 65 66 tb.reset(50); 67 drain(tb, 50); 68 69 tb.reset(50); 70 getOneByOne(tb, 10); 71 assertTrue(tb.has()); 72 73 tb.reset(30); 74 drain(tb, 30); 75 } 76 77 public void testFill() throws Exception { 78 int delta = 50; 79 TokenBucket tb = new TokenBucket(delta, 10, 0); 80 81 assertEmpty(tb); 82 83 Thread.sleep(3 * delta / 2); 84 85 assertTrue(tb.has()); 86 } 87 88 public void testRefill() throws Exception { 89 TokenBucket tb = new TokenBucket(FILL_DELTA_VERY_SHORT, 10, 10); 90 91 assertEquals(5, tb.get(5)); 92 assertEquals(5, tb.get(5)); 93 94 while (tb.available() < 10) { 95 Thread.sleep(2); 96 } 97 98 assertEquals(10, tb.get(10)); 99 100 while (tb.available() < 10) { 101 Thread.sleep(2); 102 } 103 104 assertEquals(10, tb.get(100)); 105 } 106 107 public void testAverage() throws Exception { 108 final int delta = 3; 109 final int want = 60; 110 111 long start = SystemClock.elapsedRealtime(); 112 TokenBucket tb = new TokenBucket(delta, 20, 0); 113 114 for (int i = 0; i < want; i++) { 115 while (!tb.has()) { 116 Thread.sleep(5 * delta); 117 } 118 tb.get(); 119 } 120 121 assertDuration(want * delta, SystemClock.elapsedRealtime() - start); 122 } 123 124 public void testBurst() throws Exception { 125 final int delta = 2; 126 final int capacity = 20; 127 final int want = 100; 128 129 long start = SystemClock.elapsedRealtime(); 130 TokenBucket tb = new TokenBucket(delta, capacity, 0); 131 132 int total = 0; 133 while (total < want) { 134 while (!tb.has()) { 135 Thread.sleep(capacity * delta - 2); 136 } 137 total += tb.get(tb.available()); 138 } 139 140 assertDuration(total * delta, SystemClock.elapsedRealtime() - start); 141 } 142 143 static void getOneByOne(TokenBucket tb, int n) { 144 while (n > 0) { 145 assertTrue(tb.has()); 146 assertTrue(tb.available() >= n); 147 assertTrue(tb.get()); 148 assertTrue(tb.available() >= n - 1); 149 n--; 150 } 151 } 152 153 void assertEmpty(TokenBucket tb) { 154 assertFalse(tb.has()); 155 assertEquals(0, tb.available()); 156 assertFalse(tb.get()); 157 } 158 159 void drain(TokenBucket tb, int n) { 160 getOneByOne(tb, n); 161 assertEmpty(tb); 162 } 163 164 void assertDuration(long expected, long elapsed) { 165 String msg = String.format( 166 "expected elapsed time at least %d ms, but was %d ms", expected, elapsed); 167 elapsed += 1; // one millisecond extra guard 168 assertTrue(msg, elapsed >= expected); 169 } 170 171 void assertThrow(Fn fn) { 172 try { 173 fn.call(); 174 fail("expected n exception to be thrown."); 175 } catch (Throwable t) {} 176 } 177 178 interface Fn { void call(); } 179} 180