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.server.location.fudger; 18 19 import android.annotation.FlaggedApi; 20 import android.annotation.NonNull; 21 import android.annotation.Nullable; 22 import android.location.flags.Flags; 23 import android.location.provider.IS2CellIdsCallback; 24 import android.location.provider.IS2LevelCallback; 25 import android.util.Log; 26 27 import com.android.internal.annotations.GuardedBy; 28 import com.android.internal.location.geometry.S2CellIdUtils; 29 import com.android.internal.util.FrameworkStatsLog; 30 import com.android.server.location.provider.proxy.ProxyPopulationDensityProvider; 31 32 import java.util.Objects; 33 34 /** 35 * A cache for returning the coarsening level to be used. The coarsening level depends on the user 36 * location. If the cache contains the requested latitude/longitude, the s2 level of the cached 37 * cell id is returned. If not, a default value is returned. 38 * This class has a {@link ProxyPopulationDensityProvider} used to refresh the cache. 39 * This cache exists because {@link ProxyPopulationDensityProvider} must be queried asynchronously, 40 * whereas a synchronous answer is needed. 41 * The cache is first-in, first-out, and has a fixed size. Cache entries are valid until evicted by 42 * another value. 43 */ 44 @FlaggedApi(Flags.FLAG_POPULATION_DENSITY_PROVIDER) 45 public class LocationFudgerCache { 46 47 // The maximum number of S2 cell ids stored in the cache. 48 // Each cell id is a long, so the memory requirement is 8*MAX_CACHE_SIZE bytes. 49 protected static final int MAX_CACHE_SIZE = 20; 50 51 private final Object mLock = new Object(); 52 53 // mCache is a circular buffer of size MAX_CACHE_SIZE. The next position to be written to is 54 // mPosInCache. Initially, the cache is filled with INVALID_CELL_IDs. 55 @GuardedBy("mLock") 56 private final long[] mCache = new long[MAX_CACHE_SIZE]; 57 58 @GuardedBy("mLock") 59 private int mPosInCache = 0; 60 61 @GuardedBy("mLock") 62 private int mCacheSize = 0; 63 64 // The S2 level to coarsen to, if the cache doesn't contain a better answer. 65 // Updated concurrently by callbacks. 66 @GuardedBy("mLock") 67 private Integer mDefaultCoarseningLevel = null; 68 69 // The provider that asynchronously provides what is stored in the cache. 70 private final ProxyPopulationDensityProvider mPopulationDensityProvider; 71 72 // If two calls to logDensityBasedLocsUsed are made in an interval shorter than this value, 73 // the second is dropped. 74 protected static final int LOG_DENSITY_BASED_LOCS_USED_RATE_LIMIT_MS = 1000 * 60 * 10; // 10 min 75 76 // The system time at which the last query to logDensityBasedLocsUsed was made. 77 // Initialized to -LOG_DENSITY_BASED_LOCS_USED_RATE_LIMIT_MS, so even if made at time 0, the 78 // first call succeeds. 79 private long mLastQueryToLogDensityBasedLocsUsedMs = -LOG_DENSITY_BASED_LOCS_USED_RATE_LIMIT_MS; 80 81 private static String sTAG = "LocationFudgerCache"; 82 LocationFudgerCache(@onNull ProxyPopulationDensityProvider provider)83 public LocationFudgerCache(@NonNull ProxyPopulationDensityProvider provider) { 84 mPopulationDensityProvider = Objects.requireNonNull(provider); 85 86 asyncFetchDefaultCoarseningLevel(); 87 } 88 89 /** 90 * Called by the LocationFudger when a query couldn't be fulfilled because the cache isn't set. 91 */ onDefaultCoarseningLevelNotSet()92 public void onDefaultCoarseningLevelNotSet() { 93 if (!hasDefaultValue()) { 94 asyncFetchDefaultCoarseningLevel(); 95 } 96 logDensityBasedLocsUsed(/* nowMs=*/ System.currentTimeMillis(), 97 /* skippedNoDefault= */ true, 98 /* isCacheHit= */ false, 99 /* defaultCoarseningLevel= */ -1); 100 } 101 102 /** Returns true if the cache has successfully received a default value from the provider. */ hasDefaultValue()103 public boolean hasDefaultValue() { 104 synchronized (mLock) { 105 return (mDefaultCoarseningLevel != null); 106 } 107 } 108 109 /** 110 * Returns the S2 level to which the provided location should be coarsened. 111 * The answer comes from the cache if available, otherwise the default value is returned. 112 */ getCoarseningLevel(double latitudeDegrees, double longitudeDegrees)113 public int getCoarseningLevel(double latitudeDegrees, double longitudeDegrees) { 114 // If we still haven't received the default level from the provider, try fetching it again. 115 // The answer wouldn't come in time, but it will be used for the following queries. 116 if (!hasDefaultValue()) { 117 asyncFetchDefaultCoarseningLevel(); 118 } 119 Long s2CellId = readCacheForLatLng(latitudeDegrees, longitudeDegrees); 120 int defaultLevel = getDefaultCoarseningLevel(); 121 if (s2CellId == null) { 122 // Asynchronously queries the density from the provider. The answer won't come in time, 123 // but it will update the cache for the following queries. 124 refreshCache(latitudeDegrees, longitudeDegrees); 125 126 logDensityBasedLocsUsed(/* nowMs=*/ System.currentTimeMillis(), 127 /* skippedNoDefault= */ false, 128 /* isCacheHit= */ false, 129 /* defaultCoarseningLevel= */ defaultLevel); 130 return defaultLevel; 131 } 132 logDensityBasedLocsUsed(/* nowMs=*/ System.currentTimeMillis(), 133 /* skippedNoDefault= */ false, 134 /* isCacheHit= */ true, 135 /* defaultCoarseningLevel= */ defaultLevel); 136 return S2CellIdUtils.getLevel(s2CellId); 137 } 138 139 /** 140 * A simple wrapper around FrameworkStatsLog.write() that rate-limits the calls. 141 * Returns true on success, false if the call was dropped. 142 */ logDensityBasedLocsUsed(long nowMs, boolean skippedNoDefault, boolean isCacheHit, int defaultCoarseningLevel)143 protected boolean logDensityBasedLocsUsed(long nowMs, boolean skippedNoDefault, 144 boolean isCacheHit, int defaultCoarseningLevel) { 145 146 if (nowMs - mLastQueryToLogDensityBasedLocsUsedMs 147 < LOG_DENSITY_BASED_LOCS_USED_RATE_LIMIT_MS) { 148 return false; 149 } 150 mLastQueryToLogDensityBasedLocsUsedMs = nowMs; 151 152 FrameworkStatsLog.write(FrameworkStatsLog.DENSITY_BASED_COARSE_LOCATIONS_USAGE_REPORTED, 153 /* skipped_no_default= */ skippedNoDefault, 154 /* is_cache_hit= */ isCacheHit, 155 /* default_coarsening_level= */ defaultCoarseningLevel); 156 return true; 157 } 158 159 /** 160 * If the cache contains the current location, returns the corresponding S2 cell id. 161 * Otherwise, returns null. 162 */ 163 @Nullable readCacheForLatLng(double latDegrees, double lngDegrees)164 private Long readCacheForLatLng(double latDegrees, double lngDegrees) { 165 synchronized (mLock) { 166 for (int i = 0; i < mCacheSize; i++) { 167 if (S2CellIdUtils.containsLatLngDegrees(mCache[i], latDegrees, lngDegrees)) { 168 return mCache[i]; 169 } 170 } 171 } 172 return null; 173 } 174 175 /** Adds the provided s2 cell id to the cache. This might evict other values from the cache. */ addToCache(long s2CellId)176 public void addToCache(long s2CellId) { 177 addToCache(new long[] {s2CellId}); 178 } 179 180 /** 181 * Adds the provided s2 cell ids to the cache. This might evict other values from the cache. 182 * If more than MAX_CACHE_SIZE elements are provided, only the first elements are copied. 183 * The first element of the input is added last into the FIFO cache, so it gets evicted last. 184 */ addToCache(long[] s2CellIds)185 public void addToCache(long[] s2CellIds) { 186 synchronized (mLock) { 187 // Only copy up to MAX_CACHE_SIZE elements 188 int end = Math.min(s2CellIds.length, MAX_CACHE_SIZE); 189 mCacheSize = Math.min(mCacheSize + end, MAX_CACHE_SIZE); 190 191 // Add in reverse so the first cell of s2CellIds is the last evicted 192 for (int i = end - 1; i >= 0; i--) { 193 mCache[mPosInCache] = s2CellIds[i]; 194 mPosInCache = (mPosInCache + 1) % MAX_CACHE_SIZE; 195 } 196 } 197 } 198 199 /** 200 * Queries the population density provider for the default coarsening level (to be used if the 201 * cache doesn't contain a better answer), and updates mDefaultCoarseningLevel with the answer. 202 */ asyncFetchDefaultCoarseningLevel()203 private void asyncFetchDefaultCoarseningLevel() { 204 IS2LevelCallback callback = new IS2LevelCallback.Stub() { 205 @Override 206 public void onResult(int s2level) { 207 synchronized (mLock) { 208 mDefaultCoarseningLevel = Integer.valueOf(s2level); 209 } 210 } 211 212 @Override 213 public void onError() { 214 Log.e(sTAG, "could not get default population density"); 215 } 216 }; 217 mPopulationDensityProvider.getDefaultCoarseningLevel(callback); 218 } 219 220 /** 221 * Queries the population density provider and store the result in the cache. 222 */ refreshCache(double latitude, double longitude)223 private void refreshCache(double latitude, double longitude) { 224 long startTime = System.currentTimeMillis(); 225 IS2CellIdsCallback callback = new IS2CellIdsCallback.Stub() { 226 @Override 227 public void onResult(long[] s2CellIds) { 228 int durationMs = (int) (System.currentTimeMillis() - startTime); 229 FrameworkStatsLog.write( 230 FrameworkStatsLog.DENSITY_BASED_COARSE_LOCATIONS_PROVIDER_QUERY_REPORTED, 231 /* query_duration_millis= */ durationMs, 232 /* is_error= */ false); 233 addToCache(s2CellIds); 234 } 235 236 @Override 237 public void onError() { 238 Log.e(sTAG, "could not get population density"); 239 int durationMs = (int) (System.currentTimeMillis() - startTime); 240 FrameworkStatsLog.write( 241 FrameworkStatsLog.DENSITY_BASED_COARSE_LOCATIONS_PROVIDER_QUERY_REPORTED, 242 /* query_duration_millis= */ durationMs, 243 /* is_error= */ true); 244 } 245 }; 246 mPopulationDensityProvider.getCoarsenedS2Cells(latitude, longitude, MAX_CACHE_SIZE - 1, 247 callback); 248 } 249 250 /** 251 * Returns the default S2 level to coarsen to. This should be used if the cache 252 * does not provide a better answer. 253 */ getDefaultCoarseningLevel()254 private int getDefaultCoarseningLevel() { 255 synchronized (mLock) { 256 // The minimum valid level is 0. 257 if (mDefaultCoarseningLevel == null) { 258 return 0; 259 } 260 return mDefaultCoarseningLevel; 261 } 262 } 263 } 264