1 /* 2 * Copyright (C) 2024 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 17 package com.android.internal.util; 18 19 import android.os.SystemClock; 20 import java.util.concurrent.atomic.AtomicInteger; 21 import java.util.concurrent.atomic.AtomicReference; 22 23 /** 24 * A speed/rate limiting cache that's used to cache a value to be returned as long as period hasn't 25 * elapsed and then fetches a new value after period has elapsed. Use this when AIDL calls are 26 * expensive but the value returned by those APIs don't change often enough (or the recency doesn't 27 * matter as much), to incur the cost every time. This class maintains the last fetch time and 28 * fetches a new value when period has passed. Do not use this for API calls that have side-effects. 29 * <p> 30 * By passing in an optional <code>count</code> during creation, this can be used as a rate 31 * limiter that allows up to <code>count</code> calls per period to be passed on to the query 32 * and then the cached value is returned for the remainder of the period. It uses a simple fixed 33 * window method to track rate. Use a window and count appropriate for bursts of calls and for 34 * high latency/cost of the AIDL call. 35 * <p> 36 * This class is thread-safe. When multiple threads call get(), they will all fetch a new value 37 * if the cached value is stale. This is to prevent a slow getting thread from blocking other 38 * threads from getting a fresh value. In such circumsntaces it's possible to exceed 39 * <code>count</code> calls in a given period by up to the number of threads that are concurrently 40 * attempting to get a fresh value minus one. 41 * 42 * @param <Value> The type of the return value 43 * @hide 44 */ 45 @android.ravenwood.annotation.RavenwoodKeepWholeClass 46 public class RateLimitingCache<Value> { 47 48 private final long mPeriodMillis; // window size 49 private final int mLimit; // max per window 50 // random offset to avoid batching of AIDL calls at window boundary 51 private final long mRandomOffset; 52 private final AtomicReference<CachedValue> mCachedValue = new AtomicReference(); 53 54 /** 55 * The interface to fetch the actual value, if the cache is null or expired. 56 * @hide 57 * @param <V> The return value type 58 */ 59 public interface ValueFetcher<V> { 60 /** Called when the cache needs to be updated. 61 * @return the latest value fetched from the source 62 */ fetchValue()63 V fetchValue(); 64 } 65 66 class CachedValue { 67 Value value; 68 long timestamp; 69 AtomicInteger count; // current count within window 70 } 71 72 /** 73 * Create a speed limiting cache that returns the same value until periodMillis has passed 74 * and then fetches a new value via the {@link ValueFetcher}. 75 * 76 * @param periodMillis time to wait before fetching a new value. Use a negative period to 77 * indicate the value never changes and is fetched only once and 78 * cached. A value of 0 will mean always fetch a new value. 79 */ RateLimitingCache(long periodMillis)80 public RateLimitingCache(long periodMillis) { 81 this(periodMillis, 1); 82 } 83 84 /** 85 * Create a rate-limiting cache that allows up to <code>count</code> number of AIDL calls per 86 * period before it starts returning a cached value. The count resets when the next period 87 * begins. 88 * 89 * @param periodMillis the window of time in which <code>count</code> calls will fetch the 90 * newest value from the AIDL call. 91 * @param count how many times during the period it's ok to forward the request to the fetcher 92 * in the {@link #get(ValueFetcher)} method. 93 */ RateLimitingCache(long periodMillis, int count)94 public RateLimitingCache(long periodMillis, int count) { 95 mPeriodMillis = periodMillis; 96 mLimit = count; 97 if (mLimit > 1 && periodMillis > 1) { 98 mRandomOffset = (long) (Math.random() * (periodMillis / 2)); 99 } else { 100 mRandomOffset = 0; 101 } 102 } 103 104 /** 105 * Returns the current time in <code>elapsedRealtime</code>. Can be overridden to use 106 * a different timebase that is monotonically increasing; for example, uptimeMillis() 107 * @return a monotonically increasing time in milliseconds 108 */ getTime()109 protected long getTime() { 110 return SystemClock.elapsedRealtime(); 111 } 112 113 /** 114 * Returns either the cached value, if called more frequently than the specific rate, or 115 * a new value is fetched and cached. Warning: if the caller is likely to mutate the returned 116 * object, override this method and make a clone before returning it. 117 * @return the cached or latest value 118 */ get(ValueFetcher<Value> query)119 public Value get(ValueFetcher<Value> query) { 120 CachedValue cached = mCachedValue.get(); 121 122 // If the value never changes and there is a previous cached value, return it 123 if (mPeriodMillis < 0 && cached != null && cached.timestamp != 0) { 124 return cached.value; 125 } 126 127 // Get the current time and add a random offset to avoid colliding with other 128 // caches with similar harmonic window boundaries 129 final long now = getTime() + mRandomOffset; 130 final boolean newWindow = cached == null || now - cached.timestamp >= mPeriodMillis; 131 if (newWindow || cached.count.getAndIncrement() < mLimit) { 132 // Fetch a new value 133 Value freshValue = query.fetchValue(); 134 long freshTimestamp = now; 135 // If rate limiting, set timestamp to start of this window 136 if (mLimit > 1) { 137 freshTimestamp = now - (now % mPeriodMillis); 138 } 139 140 CachedValue freshCached = new CachedValue(); 141 freshCached.value = freshValue; 142 freshCached.timestamp = freshTimestamp; 143 if (newWindow) { 144 freshCached.count = new AtomicInteger(1); 145 } else { 146 freshCached.count = cached.count; 147 } 148 149 // If we fail to CAS then it means that another thread beat us to it. 150 // In this case we don't override their work. 151 mCachedValue.compareAndSet(cached, freshCached); 152 } 153 return mCachedValue.get().value; 154 } 155 } 156