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