1/*
2 * Copyright (C) 2018 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 androidx.car.moderator;
18
19import static java.util.concurrent.TimeUnit.SECONDS;
20
21import android.util.Log;
22
23import androidx.annotation.FloatRange;
24import androidx.annotation.IntRange;
25import androidx.annotation.MainThread;
26import androidx.annotation.VisibleForTesting;
27import androidx.core.util.Preconditions;
28
29/**
30 * A class that keeps track of a general number of permitted actions that happen over time and
31 * determines if a subsequent interaction is allowed. The type of interaction is arbitrary and not
32 * transparent to this class. Instead, it will refer to these actions as "permits," short for
33 * "permitted action." It is up to a user of this class to determine the unit of permits.
34 *
35 * <p>This class allows for two quick acquires in succession to only consume one permit. This is
36 * intended behavior to account for the fact that the user can be using many taps to scroll
37 * quickly. This can fit within the window for which a user does not necessary have their eyes
38 * off the road for a long period of time, and thus should not be penalized.
39 *
40 * <p>This class allows for the maximum number of permits that can be stored,the amount of permits
41 * that are filled each second, as well as the delay before re-fill to be configured.
42 */
43public class ContentRateLimiter {
44    private static final String TAG = "ContentRateLimiter";
45
46    /** The maximum number of stored permits. */
47    private double mMaxStoredPermits;
48
49    /**
50     * The interval between two unit requests at our stable rate. For example, a stable rate of
51     * 5 permits per second has a stable interval of 200ms.
52     */
53    private long mStableIntervalMs;
54
55    /**
56     * The amount of time to wait between when a permit is acquired and when the model starts
57     * refilling.
58     */
59    private long mFillDelayMs;
60
61    /** Unlimited mode. Once enabled, any number of permits can be acquired and consumed. */
62    private boolean mUnlimitedModeEnabled;
63
64    /**
65     * Used to do incremental calculations by {@link #getLastCalculatedPermitCount()}, cannot be
66     * used directly.
67     */
68    private double mLastCalculatedPermitCount;
69
70    /** Time in milliseconds when permits can resume incrementing. */
71    private long mResumeIncrementingMs;
72
73    /** Tracks if the model will allow a second permit to be requested in the fill delay. */
74    private boolean mSecondaryFillDelayPermitAvailable = true;
75
76    private final ElapsedTimeProvider mElapsedTimeProvider;
77
78    /**
79     * An interface for a provider of the current time that has passed since boot. This interface
80     * is meant to abstract the {@link android.os.SystemClock} so that it can be mocked during
81     * testing.
82     */
83    interface ElapsedTimeProvider {
84        /** Returns milliseconds since boot, including time spent in sleep. */
85        long getElapsedRealtime();
86    }
87
88    /**
89     * Creates a {@code ContentRateLimiter} with the given parameters.
90     *
91     * @param acquiredPermitsPerSecond The amount of permits that are acquired each second.
92     * @param maxStoredPermits The maximum number of permits that can be stored.
93     * @param fillDelayMs The amount of time to wait between when a permit is acquired and when
94     *                    the number of available permits start refilling.
95     */
96    public ContentRateLimiter(
97            @FloatRange(from = 0, fromInclusive = false) double acquiredPermitsPerSecond,
98            @FloatRange(from = 0) double maxStoredPermits,
99            @IntRange(from = 0) long fillDelayMs) {
100        this(acquiredPermitsPerSecond, maxStoredPermits, fillDelayMs,
101                new SystemClockTimeProvider());
102    }
103
104    // A constructor that allows for the SystemClockTimeProvider to be provided. This is needed for
105    // testing so that the unit test does not rely on the actual SystemClock.
106    @VisibleForTesting
107    ContentRateLimiter(
108            @FloatRange(from = 0, fromInclusive = false) double acquiredPermitsPerSecond,
109            @FloatRange(from = 0) double maxStoredPermits,
110            @IntRange(from = 0) long fillDelayMs,
111            ElapsedTimeProvider elapsedTimeProvider) {
112        mElapsedTimeProvider = elapsedTimeProvider;
113        mResumeIncrementingMs = mElapsedTimeProvider.getElapsedRealtime();
114        setAcquiredPermitsRate(acquiredPermitsPerSecond);
115        setMaxStoredPermits(maxStoredPermits);
116        setPermitFillDelay(fillDelayMs);
117
118        if (Log.isLoggable(TAG, Log.VERBOSE)) {
119            Log.v(TAG, String.format("permitsPerSecond: %f maxStoredPermits: %f, fillDelayMs %d",
120                    acquiredPermitsPerSecond, maxStoredPermits, fillDelayMs));
121        }
122    }
123
124    /**
125     * Sets the amount of permits that are acquired each second. These permits are acquired when
126     * the {@code ContentRateLimiter} is not being interacted with. That is, the
127     * {@link #tryAcquire()} or {@link #tryAcquire(int)} methods have not been called.
128     *
129     * @param acquiredPermitsPerSecond The number of permits acquired each second. Must be greater
130     *                                 than zero.
131     */
132    public void setAcquiredPermitsRate(
133            @FloatRange(from = 0, fromInclusive = false) double acquiredPermitsPerSecond) {
134        Preconditions.checkArgument(acquiredPermitsPerSecond > 0);
135        mStableIntervalMs = (long) (SECONDS.toMillis(1L) / acquiredPermitsPerSecond);
136    }
137
138    /**
139     * The maximum amount of permits that can be stored. Permits are accumulated when the
140     * the {@code ContentRateLimiter} is not being interacted with. That is, the
141     * {@link #tryAcquire()} or {@link #tryAcquire(int)} methods have not been called.
142     *
143     * @param maxStoredPermits The maximum number of stored permits. Must be greater than or equal
144     *                         to zero.
145     */
146    public void setMaxStoredPermits(@FloatRange(from = 0) double maxStoredPermits) {
147        Preconditions.checkArgument(maxStoredPermits >= 0);
148        mMaxStoredPermits = maxStoredPermits;
149        mLastCalculatedPermitCount = maxStoredPermits;
150    }
151
152    /**
153     * Sets delay before permits begin accumulating. This is the delay after a {@link #tryAcquire()}
154     * or {@link #tryAcquire(int)} has been called. After the given delay, permits will be
155     * accumulated at the rate set by {@link #setAcquiredPermitsRate(double)}.
156     *
157     * @param fillDelayMs The delay in milliseconds before permits accumulate.
158     */
159    public void setPermitFillDelay(@IntRange(from = 0) long fillDelayMs) {
160        Preconditions.checkArgument(fillDelayMs >= 0);
161        mFillDelayMs = fillDelayMs;
162    }
163
164    /** Gets the current number of stored permits ready to be used. */
165    @MainThread
166    public double getAvailablePermits() {
167        return getLastCalculatedPermitCount();
168    }
169
170    /**
171     * Sets the current number of stored permits that are ready to be used. If this value exceeds
172     * the maximum number of stored permits that is passed to the constructor, then the max value
173     * is used instead.
174     */
175    @MainThread
176    public void setAvailablePermits(double availablePermits) {
177        setLastCalculatedPermitCount(availablePermits, mElapsedTimeProvider.getElapsedRealtime());
178    }
179
180    /** Gets the max number of permits allowed to be stored for future usage. */
181    public double getMaxStoredPermits() {
182        return mMaxStoredPermits;
183    }
184
185    /**
186     * Checks if there are enough available permits for a single permit to be acquired.
187     *
188     * @return {@code true} if unlimited mode is enabled or enough permits are acquirable at the
189     * time of this call; {@code false} if there isn't the number of permits requested available
190     * currently.
191     */
192    @MainThread
193    public boolean tryAcquire() {
194        return tryAcquire(1);
195    }
196
197    /**
198     * Checks whether there are enough available permits to acquire.
199     *
200     * @return {@code true} if unlimited mode is enabled or enough permits are acquirable at the
201     * time of this call; {@code false} if there isn't the number of permits requested available
202     * currently.
203     */
204    @MainThread
205    public boolean tryAcquire(int permits) {
206        // Once unlimited mode is enabled, we can acquire any number of permits we want and don't
207        // consume the stored permits.
208        if (mUnlimitedModeEnabled) {
209            if (Log.isLoggable(TAG, Log.DEBUG)) {
210                Log.d(TAG, "Unlimited mode is enabled.");
211            }
212            return true;
213        }
214        double availablePermits = getLastCalculatedPermitCount();
215        long nowMs = mElapsedTimeProvider.getElapsedRealtime();
216
217        if (Log.isLoggable(TAG, Log.VERBOSE)) {
218            Log.v(TAG, String.format("Requesting: %d, Stored: %f/%f", permits,
219                    mLastCalculatedPermitCount, mMaxStoredPermits));
220        }
221        if (availablePermits <= permits) {
222            // Once locked out, the user is prevented from acquiring any more permits until they
223            // have waited long enough for a permit to refill. If the user attempts to acquire a
224            // permit during this time, the countdown timer until a permit is refilled is reset.
225            setLastCalculatedPermitCount(0, nowMs + mFillDelayMs);
226            return false;
227        } else if (nowMs < mResumeIncrementingMs && mSecondaryFillDelayPermitAvailable) {
228            // If a second permit is requested between the time a first permit was requested and
229            // the fill delay, allow the second permit to be acquired without decrementing the model
230            // and set the point where permits can resume incrementing {@link #mFillDelayMs} in the
231            // future.
232            setLastCalculatedPermitCount(availablePermits, nowMs + mFillDelayMs);
233            // Don't allow a third "free" permit to be acquired in the fill delay fringe.
234            mSecondaryFillDelayPermitAvailable = false;
235
236            if (Log.isLoggable(TAG, Log.DEBUG)) {
237                Log.d(TAG, "Used up free secondary permit");
238            }
239            return true;
240        } else {
241            // Decrement the available permits, and set the point where permits can resume
242            // incrementing {@link #mFillDelayMs} in the future.
243            setLastCalculatedPermitCount(availablePermits - permits, nowMs + mFillDelayMs);
244
245            if (Log.isLoggable(TAG, Log.VERBOSE)) {
246                Log.v(TAG, String.format("permits remaining %s, secondary permit available %s",
247                        mLastCalculatedPermitCount,
248                        mSecondaryFillDelayPermitAvailable));
249            }
250
251            mSecondaryFillDelayPermitAvailable = true;
252            return true;
253        }
254    }
255
256    /**
257     * Sets unlimited mode. If enabled, there is no restriction on the number of permits that
258     * can be acquired and any interaction does not consume stored permits.
259     */
260    public void setUnlimitedMode(boolean enabled) {
261        mUnlimitedModeEnabled = enabled;
262    }
263
264    /**
265     * Updates {@link #mLastCalculatedPermitCount} and {@link #mResumeIncrementingMs} based on the
266     * current time.
267     */
268    private double getLastCalculatedPermitCount() {
269        long nowMs = mElapsedTimeProvider.getElapsedRealtime();
270        if (nowMs > mResumeIncrementingMs) {
271            long deltaMs = nowMs - mResumeIncrementingMs;
272            double newPermits = deltaMs / (double) mStableIntervalMs;
273            setLastCalculatedPermitCount(mLastCalculatedPermitCount + newPermits, nowMs);
274        }
275        return mLastCalculatedPermitCount;
276    }
277
278    private void setLastCalculatedPermitCount(double newCount, long nextMs) {
279        mLastCalculatedPermitCount = Math.min(mMaxStoredPermits, newCount);
280        mResumeIncrementingMs = nextMs;
281    }
282}
283