1 /* 2 * Copyright (C) 2021 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.tare; 18 19 import static android.text.format.DateUtils.HOUR_IN_MILLIS; 20 import static android.util.TimeUtils.dumpTime; 21 22 import static com.android.server.tare.TareUtils.cakeToString; 23 import static com.android.server.tare.TareUtils.getCurrentTimeMillis; 24 25 import android.annotation.CurrentTimeMillisLong; 26 import android.annotation.NonNull; 27 import android.annotation.Nullable; 28 import android.util.IndentingPrintWriter; 29 import android.util.SparseLongArray; 30 import android.util.TimeUtils; 31 32 import com.android.internal.annotations.VisibleForTesting; 33 34 import java.util.ArrayList; 35 import java.util.List; 36 37 /** 38 * Ledger to track the last recorded balance and recent activities of an app. 39 */ 40 class Ledger { 41 /** The window size within which rewards will be counted and used towards reward limiting. */ 42 private static final long TOTAL_REWARD_WINDOW_MS = 24 * HOUR_IN_MILLIS; 43 /** The number of buckets to split {@link #TOTAL_REWARD_WINDOW_MS} into. */ 44 @VisibleForTesting 45 static final int NUM_REWARD_BUCKET_WINDOWS = 4; 46 /** 47 * The duration size of each bucket resulting from splitting {@link #TOTAL_REWARD_WINDOW_MS} 48 * into smaller buckets. 49 */ 50 private static final long REWARD_BUCKET_WINDOW_SIZE_MS = 51 TOTAL_REWARD_WINDOW_MS / NUM_REWARD_BUCKET_WINDOWS; 52 /** The maximum number of transactions to retain in memory at any one time. */ 53 @VisibleForTesting 54 static final int MAX_TRANSACTION_COUNT = 50; 55 56 static class Transaction { 57 public final long startTimeMs; 58 public final long endTimeMs; 59 public final int eventId; 60 @Nullable 61 public final String tag; 62 public final long delta; 63 public final long ctp; 64 Transaction(long startTimeMs, long endTimeMs, int eventId, @Nullable String tag, long delta, long ctp)65 Transaction(long startTimeMs, long endTimeMs, 66 int eventId, @Nullable String tag, long delta, long ctp) { 67 this.startTimeMs = startTimeMs; 68 this.endTimeMs = endTimeMs; 69 this.eventId = eventId; 70 this.tag = tag; 71 this.delta = delta; 72 this.ctp = ctp; 73 } 74 } 75 76 static class RewardBucket { 77 @CurrentTimeMillisLong 78 public long startTimeMs; 79 public final SparseLongArray cumulativeDelta = new SparseLongArray(); 80 reset()81 private void reset() { 82 startTimeMs = 0; 83 cumulativeDelta.clear(); 84 } 85 } 86 87 /** Last saved balance. This doesn't take currently ongoing events into account. */ 88 private long mCurrentBalance = 0; 89 private final Transaction[] mTransactions = new Transaction[MAX_TRANSACTION_COUNT]; 90 /** Index within {@link #mTransactions} where the next transaction should be placed. */ 91 private int mTransactionIndex = 0; 92 private final RewardBucket[] mRewardBuckets = new RewardBucket[NUM_REWARD_BUCKET_WINDOWS]; 93 /** Index within {@link #mRewardBuckets} of the current active bucket. */ 94 private int mRewardBucketIndex = 0; 95 Ledger()96 Ledger() { 97 } 98 Ledger(long currentBalance, @NonNull List<Transaction> transactions, @NonNull List<RewardBucket> rewardBuckets)99 Ledger(long currentBalance, @NonNull List<Transaction> transactions, 100 @NonNull List<RewardBucket> rewardBuckets) { 101 mCurrentBalance = currentBalance; 102 103 final int numTxs = transactions.size(); 104 for (int i = Math.max(0, numTxs - MAX_TRANSACTION_COUNT); i < numTxs; ++i) { 105 mTransactions[mTransactionIndex++] = transactions.get(i); 106 } 107 mTransactionIndex %= MAX_TRANSACTION_COUNT; 108 109 final int numBuckets = rewardBuckets.size(); 110 if (numBuckets > 0) { 111 // Set the index to -1 so that we put the first bucket in index 0. 112 mRewardBucketIndex = -1; 113 for (int i = Math.max(0, numBuckets - NUM_REWARD_BUCKET_WINDOWS); i < numBuckets; ++i) { 114 mRewardBuckets[++mRewardBucketIndex] = rewardBuckets.get(i); 115 } 116 } 117 } 118 getCurrentBalance()119 long getCurrentBalance() { 120 return mCurrentBalance; 121 } 122 123 @Nullable getEarliestTransaction()124 Transaction getEarliestTransaction() { 125 for (int t = 0; t < mTransactions.length; ++t) { 126 final Transaction transaction = 127 mTransactions[(mTransactionIndex + t) % mTransactions.length]; 128 if (transaction != null) { 129 return transaction; 130 } 131 } 132 return null; 133 } 134 135 @NonNull getRewardBuckets()136 List<RewardBucket> getRewardBuckets() { 137 final long cutoffMs = getCurrentTimeMillis() - TOTAL_REWARD_WINDOW_MS; 138 final List<RewardBucket> list = new ArrayList<>(NUM_REWARD_BUCKET_WINDOWS); 139 for (int i = 1; i <= NUM_REWARD_BUCKET_WINDOWS; ++i) { 140 final int idx = (mRewardBucketIndex + i) % NUM_REWARD_BUCKET_WINDOWS; 141 final RewardBucket rewardBucket = mRewardBuckets[idx]; 142 if (rewardBucket != null) { 143 if (cutoffMs <= rewardBucket.startTimeMs) { 144 list.add(rewardBucket); 145 } else { 146 rewardBucket.reset(); 147 } 148 } 149 } 150 return list; 151 } 152 153 @NonNull getTransactions()154 List<Transaction> getTransactions() { 155 final List<Transaction> list = new ArrayList<>(MAX_TRANSACTION_COUNT); 156 for (int i = 0; i < MAX_TRANSACTION_COUNT; ++i) { 157 final int idx = (mTransactionIndex + i) % MAX_TRANSACTION_COUNT; 158 final Transaction transaction = mTransactions[idx]; 159 if (transaction != null) { 160 list.add(transaction); 161 } 162 } 163 return list; 164 } 165 recordTransaction(@onNull Transaction transaction)166 void recordTransaction(@NonNull Transaction transaction) { 167 mTransactions[mTransactionIndex] = transaction; 168 mCurrentBalance += transaction.delta; 169 mTransactionIndex = (mTransactionIndex + 1) % MAX_TRANSACTION_COUNT; 170 171 if (EconomicPolicy.isReward(transaction.eventId)) { 172 final RewardBucket bucket = getCurrentRewardBucket(); 173 bucket.cumulativeDelta.put(transaction.eventId, 174 bucket.cumulativeDelta.get(transaction.eventId, 0) + transaction.delta); 175 } 176 } 177 178 @NonNull getCurrentRewardBucket()179 private RewardBucket getCurrentRewardBucket() { 180 RewardBucket bucket = mRewardBuckets[mRewardBucketIndex]; 181 final long now = getCurrentTimeMillis(); 182 if (bucket == null) { 183 bucket = new RewardBucket(); 184 bucket.startTimeMs = now; 185 mRewardBuckets[mRewardBucketIndex] = bucket; 186 return bucket; 187 } 188 189 if (now - bucket.startTimeMs < REWARD_BUCKET_WINDOW_SIZE_MS) { 190 return bucket; 191 } 192 193 mRewardBucketIndex = (mRewardBucketIndex + 1) % NUM_REWARD_BUCKET_WINDOWS; 194 bucket = mRewardBuckets[mRewardBucketIndex]; 195 if (bucket == null) { 196 bucket = new RewardBucket(); 197 mRewardBuckets[mRewardBucketIndex] = bucket; 198 } 199 bucket.reset(); 200 // Using now as the start time means there will be some gaps between sequential buckets, 201 // but makes processing of large gaps between events easier. 202 bucket.startTimeMs = now; 203 return bucket; 204 } 205 get24HourSum(int eventId, final long now)206 long get24HourSum(int eventId, final long now) { 207 final long windowStartTime = now - 24 * HOUR_IN_MILLIS; 208 long sum = 0; 209 for (int i = 0; i < mRewardBuckets.length; ++i) { 210 final RewardBucket bucket = mRewardBuckets[i]; 211 if (bucket != null 212 && bucket.startTimeMs >= windowStartTime && bucket.startTimeMs < now) { 213 sum += bucket.cumulativeDelta.get(eventId, 0); 214 } 215 } 216 return sum; 217 } 218 219 /** 220 * Deletes transactions that are older than {@code minAgeMs}. 221 * @return The earliest transaction in the ledger, or {@code null} if there are no more 222 * transactions. 223 */ 224 @Nullable removeOldTransactions(long minAgeMs)225 Transaction removeOldTransactions(long minAgeMs) { 226 final long cutoff = getCurrentTimeMillis() - minAgeMs; 227 for (int t = 0; t < mTransactions.length; ++t) { 228 final int idx = (mTransactionIndex + t) % mTransactions.length; 229 final Transaction transaction = mTransactions[idx]; 230 if (transaction == null) { 231 continue; 232 } 233 if (transaction.endTimeMs <= cutoff) { 234 mTransactions[idx] = null; 235 } else { 236 // Everything we look at after this transaction will also be within the window, 237 // so no need to go further. 238 return transaction; 239 } 240 } 241 return null; 242 } 243 dump(IndentingPrintWriter pw, int numRecentTransactions)244 void dump(IndentingPrintWriter pw, int numRecentTransactions) { 245 pw.print("Current balance", cakeToString(getCurrentBalance())).println(); 246 pw.println(); 247 248 boolean printedTransactionTitle = false; 249 for (int t = 0; t < Math.min(MAX_TRANSACTION_COUNT, numRecentTransactions); ++t) { 250 final int idx = (mTransactionIndex + t) % MAX_TRANSACTION_COUNT; 251 final Transaction transaction = mTransactions[idx]; 252 if (transaction == null) { 253 continue; 254 } 255 256 if (!printedTransactionTitle) { 257 pw.println("Transactions:"); 258 pw.increaseIndent(); 259 printedTransactionTitle = true; 260 } 261 262 dumpTime(pw, transaction.startTimeMs); 263 pw.print("--"); 264 dumpTime(pw, transaction.endTimeMs); 265 pw.print(": "); 266 pw.print(EconomicPolicy.eventToString(transaction.eventId)); 267 if (transaction.tag != null) { 268 pw.print("("); 269 pw.print(transaction.tag); 270 pw.print(")"); 271 } 272 pw.print(" --> "); 273 pw.print(cakeToString(transaction.delta)); 274 pw.print(" (ctp="); 275 pw.print(cakeToString(transaction.ctp)); 276 pw.println(")"); 277 } 278 if (printedTransactionTitle) { 279 pw.decreaseIndent(); 280 pw.println(); 281 } 282 283 final long now = getCurrentTimeMillis(); 284 boolean printedBucketTitle = false; 285 for (int b = 0; b < NUM_REWARD_BUCKET_WINDOWS; ++b) { 286 final int idx = (mRewardBucketIndex - b + NUM_REWARD_BUCKET_WINDOWS) 287 % NUM_REWARD_BUCKET_WINDOWS; 288 final RewardBucket rewardBucket = mRewardBuckets[idx]; 289 if (rewardBucket == null || rewardBucket.startTimeMs == 0) { 290 continue; 291 } 292 293 if (!printedBucketTitle) { 294 pw.println("Reward buckets:"); 295 pw.increaseIndent(); 296 printedBucketTitle = true; 297 } 298 299 dumpTime(pw, rewardBucket.startTimeMs); 300 pw.print(" ("); 301 TimeUtils.formatDuration(now - rewardBucket.startTimeMs, pw); 302 pw.println(" ago):"); 303 pw.increaseIndent(); 304 for (int r = 0; r < rewardBucket.cumulativeDelta.size(); ++r) { 305 pw.print(EconomicPolicy.eventToString(rewardBucket.cumulativeDelta.keyAt(r))); 306 pw.print(": "); 307 pw.println(cakeToString(rewardBucket.cumulativeDelta.valueAt(r))); 308 } 309 pw.decreaseIndent(); 310 } 311 if (printedBucketTitle) { 312 pw.decreaseIndent(); 313 pw.println(); 314 } 315 } 316 } 317