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