diff options
5 files changed, 629 insertions, 92 deletions
diff --git a/apex/jobscheduler/service/java/com/android/server/tare/EconomicPolicy.java b/apex/jobscheduler/service/java/com/android/server/tare/EconomicPolicy.java index d401373c0066..aeb6abc3ce1b 100644 --- a/apex/jobscheduler/service/java/com/android/server/tare/EconomicPolicy.java +++ b/apex/jobscheduler/service/java/com/android/server/tare/EconomicPolicy.java @@ -306,6 +306,10 @@ public abstract class EconomicPolicy { return eventId & MASK_TYPE; } + static boolean isReward(int eventId) { + return getEventType(eventId) == TYPE_REWARD; + } + @NonNull static String eventToString(int eventId) { switch (eventId & MASK_TYPE) { diff --git a/apex/jobscheduler/service/java/com/android/server/tare/Ledger.java b/apex/jobscheduler/service/java/com/android/server/tare/Ledger.java index 2e2a9b56d3df..3b5e444e1300 100644 --- a/apex/jobscheduler/service/java/com/android/server/tare/Ledger.java +++ b/apex/jobscheduler/service/java/com/android/server/tare/Ledger.java @@ -22,10 +22,14 @@ import static com.android.server.tare.TareUtils.cakeToString; import static com.android.server.tare.TareUtils.dumpTime; import static com.android.server.tare.TareUtils.getCurrentTimeMillis; +import android.annotation.CurrentTimeMillisLong; import android.annotation.NonNull; import android.annotation.Nullable; import android.util.IndentingPrintWriter; import android.util.SparseLongArray; +import android.util.TimeUtils; + +import com.android.internal.annotations.VisibleForTesting; import java.util.ArrayList; import java.util.List; @@ -34,6 +38,21 @@ import java.util.List; * Ledger to track the last recorded balance and recent activities of an app. */ class Ledger { + /** The window size within which rewards will be counted and used towards reward limiting. */ + private static final long TOTAL_REWARD_WINDOW_MS = 24 * HOUR_IN_MILLIS; + /** The number of buckets to split {@link #TOTAL_REWARD_WINDOW_MS} into. */ + @VisibleForTesting + static final int NUM_REWARD_BUCKET_WINDOWS = 4; + /** + * The duration size of each bucket resulting from splitting {@link #TOTAL_REWARD_WINDOW_MS} + * into smaller buckets. + */ + private static final long REWARD_BUCKET_WINDOW_SIZE_MS = + TOTAL_REWARD_WINDOW_MS / NUM_REWARD_BUCKET_WINDOWS; + /** The maximum number of transactions to retain in memory at any one time. */ + @VisibleForTesting + static final int MAX_TRANSACTION_COUNT = 50; + static class Transaction { public final long startTimeMs; public final long endTimeMs; @@ -54,18 +73,47 @@ class Ledger { } } + static class RewardBucket { + @CurrentTimeMillisLong + public long startTimeMs; + public final SparseLongArray cumulativeDelta = new SparseLongArray(); + + private void reset() { + startTimeMs = 0; + cumulativeDelta.clear(); + } + } + /** Last saved balance. This doesn't take currently ongoing events into account. */ private long mCurrentBalance = 0; - private final List<Transaction> mTransactions = new ArrayList<>(); - private final SparseLongArray mCumulativeDeltaPerReason = new SparseLongArray(); - private long mEarliestSumTime; + private final Transaction[] mTransactions = new Transaction[MAX_TRANSACTION_COUNT]; + /** Index within {@link #mTransactions} where the next transaction should be placed. */ + private int mTransactionIndex = 0; + private final RewardBucket[] mRewardBuckets = new RewardBucket[NUM_REWARD_BUCKET_WINDOWS]; + /** Index within {@link #mRewardBuckets} of the current active bucket. */ + private int mRewardBucketIndex = 0; Ledger() { } - Ledger(long currentBalance, @NonNull List<Transaction> transactions) { + Ledger(long currentBalance, @NonNull List<Transaction> transactions, + @NonNull List<RewardBucket> rewardBuckets) { mCurrentBalance = currentBalance; - mTransactions.addAll(transactions); + + final int numTxs = transactions.size(); + for (int i = Math.max(0, numTxs - MAX_TRANSACTION_COUNT); i < numTxs; ++i) { + mTransactions[mTransactionIndex++] = transactions.get(i); + } + mTransactionIndex %= MAX_TRANSACTION_COUNT; + + final int numBuckets = rewardBuckets.size(); + if (numBuckets > 0) { + // Set the index to -1 so that we put the first bucket in index 0. + mRewardBucketIndex = -1; + for (int i = Math.max(0, numBuckets - NUM_REWARD_BUCKET_WINDOWS); i < numBuckets; ++i) { + mRewardBuckets[++mRewardBucketIndex] = rewardBuckets.get(i); + } + } } long getCurrentBalance() { @@ -74,66 +122,142 @@ class Ledger { @Nullable Transaction getEarliestTransaction() { - if (mTransactions.size() > 0) { - return mTransactions.get(0); + for (int t = 0; t < mTransactions.length; ++t) { + final Transaction transaction = + mTransactions[(mTransactionIndex + t) % mTransactions.length]; + if (transaction != null) { + return transaction; + } } return null; } @NonNull + List<RewardBucket> getRewardBuckets() { + final long cutoffMs = getCurrentTimeMillis() - TOTAL_REWARD_WINDOW_MS; + final List<RewardBucket> list = new ArrayList<>(NUM_REWARD_BUCKET_WINDOWS); + for (int i = 1; i <= NUM_REWARD_BUCKET_WINDOWS; ++i) { + final int idx = (mRewardBucketIndex + i) % NUM_REWARD_BUCKET_WINDOWS; + final RewardBucket rewardBucket = mRewardBuckets[idx]; + if (rewardBucket != null) { + if (cutoffMs <= rewardBucket.startTimeMs) { + list.add(rewardBucket); + } else { + rewardBucket.reset(); + } + } + } + return list; + } + + @NonNull List<Transaction> getTransactions() { - return mTransactions; + final List<Transaction> list = new ArrayList<>(MAX_TRANSACTION_COUNT); + for (int i = 0; i < MAX_TRANSACTION_COUNT; ++i) { + final int idx = (mTransactionIndex + i) % MAX_TRANSACTION_COUNT; + final Transaction transaction = mTransactions[idx]; + if (transaction != null) { + list.add(transaction); + } + } + return list; } void recordTransaction(@NonNull Transaction transaction) { - mTransactions.add(transaction); + mTransactions[mTransactionIndex] = transaction; mCurrentBalance += transaction.delta; + mTransactionIndex = (mTransactionIndex + 1) % MAX_TRANSACTION_COUNT; - final long sum = mCumulativeDeltaPerReason.get(transaction.eventId); - mCumulativeDeltaPerReason.put(transaction.eventId, sum + transaction.delta); - mEarliestSumTime = Math.min(mEarliestSumTime, transaction.startTimeMs); + if (EconomicPolicy.isReward(transaction.eventId)) { + final RewardBucket bucket = getCurrentRewardBucket(); + bucket.cumulativeDelta.put(transaction.eventId, + bucket.cumulativeDelta.get(transaction.eventId, 0) + transaction.delta); + } + } + + @NonNull + private RewardBucket getCurrentRewardBucket() { + RewardBucket bucket = mRewardBuckets[mRewardBucketIndex]; + final long now = getCurrentTimeMillis(); + if (bucket == null) { + bucket = new RewardBucket(); + bucket.startTimeMs = now; + mRewardBuckets[mRewardBucketIndex] = bucket; + return bucket; + } + + if (now - bucket.startTimeMs < REWARD_BUCKET_WINDOW_SIZE_MS) { + return bucket; + } + + mRewardBucketIndex = (mRewardBucketIndex + 1) % NUM_REWARD_BUCKET_WINDOWS; + bucket = mRewardBuckets[mRewardBucketIndex]; + if (bucket == null) { + bucket = new RewardBucket(); + mRewardBuckets[mRewardBucketIndex] = bucket; + } + bucket.reset(); + // Using now as the start time means there will be some gaps between sequential buckets, + // but makes processing of large gaps between events easier. + bucket.startTimeMs = now; + return bucket; } long get24HourSum(int eventId, final long now) { final long windowStartTime = now - 24 * HOUR_IN_MILLIS; - if (mEarliestSumTime < windowStartTime) { - // Need to redo sums - mCumulativeDeltaPerReason.clear(); - for (int i = mTransactions.size() - 1; i >= 0; --i) { - final Transaction transaction = mTransactions.get(i); - if (transaction.endTimeMs <= windowStartTime) { - break; - } - long sum = mCumulativeDeltaPerReason.get(transaction.eventId); - if (transaction.startTimeMs >= windowStartTime) { - sum += transaction.delta; - } else { - // Pro-rate durationed deltas. Intentionally floor the result. - sum += (long) (1.0 * (transaction.endTimeMs - windowStartTime) - * transaction.delta) - / (transaction.endTimeMs - transaction.startTimeMs); - } - mCumulativeDeltaPerReason.put(transaction.eventId, sum); + long sum = 0; + for (int i = 0; i < mRewardBuckets.length; ++i) { + final RewardBucket bucket = mRewardBuckets[i]; + if (bucket != null + && bucket.startTimeMs >= windowStartTime && bucket.startTimeMs < now) { + sum += bucket.cumulativeDelta.get(eventId, 0); } - mEarliestSumTime = windowStartTime; } - return mCumulativeDeltaPerReason.get(eventId); + return sum; } - /** Deletes transactions that are older than {@code minAgeMs}. */ - void removeOldTransactions(long minAgeMs) { + /** + * Deletes transactions that are older than {@code minAgeMs}. + * @return The earliest transaction in the ledger, or {@code null} if there are no more + * transactions. + */ + @Nullable + Transaction removeOldTransactions(long minAgeMs) { final long cutoff = getCurrentTimeMillis() - minAgeMs; - while (mTransactions.size() > 0 && mTransactions.get(0).endTimeMs <= cutoff) { - mTransactions.remove(0); + for (int t = 0; t < mTransactions.length; ++t) { + final int idx = (mTransactionIndex + t) % mTransactions.length; + final Transaction transaction = mTransactions[idx]; + if (transaction == null) { + continue; + } + if (transaction.endTimeMs <= cutoff) { + mTransactions[idx] = null; + } else { + // Everything we look at after this transaction will also be within the window, + // so no need to go further. + return transaction; + } } + return null; } void dump(IndentingPrintWriter pw, int numRecentTransactions) { pw.print("Current balance", cakeToString(getCurrentBalance())).println(); + pw.println(); - final int size = mTransactions.size(); - for (int i = Math.max(0, size - numRecentTransactions); i < size; ++i) { - final Transaction transaction = mTransactions.get(i); + boolean printedTransactionTitle = false; + for (int t = 0; t < Math.min(MAX_TRANSACTION_COUNT, numRecentTransactions); ++t) { + final int idx = (mTransactionIndex - t + MAX_TRANSACTION_COUNT) % MAX_TRANSACTION_COUNT; + final Transaction transaction = mTransactions[idx]; + if (transaction == null) { + continue; + } + + if (!printedTransactionTitle) { + pw.println("Transactions:"); + pw.increaseIndent(); + printedTransactionTitle = true; + } dumpTime(pw, transaction.startTimeMs); pw.print("--"); @@ -151,5 +275,42 @@ class Ledger { pw.print(cakeToString(transaction.ctp)); pw.println(")"); } + if (printedTransactionTitle) { + pw.decreaseIndent(); + pw.println(); + } + + final long now = getCurrentTimeMillis(); + boolean printedBucketTitle = false; + for (int b = 0; b < NUM_REWARD_BUCKET_WINDOWS; ++b) { + final int idx = (mRewardBucketIndex - b + NUM_REWARD_BUCKET_WINDOWS) + % NUM_REWARD_BUCKET_WINDOWS; + final RewardBucket rewardBucket = mRewardBuckets[idx]; + if (rewardBucket == null) { + continue; + } + + if (!printedBucketTitle) { + pw.println("Reward buckets:"); + pw.increaseIndent(); + printedBucketTitle = true; + } + + dumpTime(pw, rewardBucket.startTimeMs); + pw.print(" ("); + TimeUtils.formatDuration(now - rewardBucket.startTimeMs, pw); + pw.println(" ago):"); + pw.increaseIndent(); + for (int r = 0; r < rewardBucket.cumulativeDelta.size(); ++r) { + pw.print(EconomicPolicy.eventToString(rewardBucket.cumulativeDelta.keyAt(r))); + pw.print(": "); + pw.println(cakeToString(rewardBucket.cumulativeDelta.valueAt(r))); + } + pw.decreaseIndent(); + } + if (printedBucketTitle) { + pw.decreaseIndent(); + pw.println(); + } } } diff --git a/apex/jobscheduler/service/java/com/android/server/tare/Scribe.java b/apex/jobscheduler/service/java/com/android/server/tare/Scribe.java index 941cc39f2d97..8f7657e6c414 100644 --- a/apex/jobscheduler/service/java/com/android/server/tare/Scribe.java +++ b/apex/jobscheduler/service/java/com/android/server/tare/Scribe.java @@ -62,15 +62,14 @@ public class Scribe { private static final int MAX_NUM_TRANSACTION_DUMP = 25; /** * The maximum amount of time we'll keep a transaction around for. - * For now, only keep transactions we actually have a use for. We can increase it if we want - * to use older transactions or provide older transactions to apps. */ - private static final long MAX_TRANSACTION_AGE_MS = 24 * HOUR_IN_MILLIS; + private static final long MAX_TRANSACTION_AGE_MS = 8 * 24 * HOUR_IN_MILLIS; private static final String XML_TAG_HIGH_LEVEL_STATE = "irs-state"; private static final String XML_TAG_LEDGER = "ledger"; private static final String XML_TAG_TARE = "tare"; private static final String XML_TAG_TRANSACTION = "transaction"; + private static final String XML_TAG_REWARD_BUCKET = "rewardBucket"; private static final String XML_TAG_USER = "user"; private static final String XML_TAG_PERIOD_REPORT = "report"; @@ -346,8 +345,8 @@ public class Scribe { for (int pIdx = mLedgers.numElementsForKey(userId) - 1; pIdx >= 0; --pIdx) { final String pkgName = mLedgers.keyAt(uIdx, pIdx); final Ledger ledger = mLedgers.get(userId, pkgName); - ledger.removeOldTransactions(MAX_TRANSACTION_AGE_MS); - Ledger.Transaction transaction = ledger.getEarliestTransaction(); + final Ledger.Transaction transaction = + ledger.removeOldTransactions(MAX_TRANSACTION_AGE_MS); if (transaction != null) { earliestEndTime = Math.min(earliestEndTime, transaction.endTimeMs); } @@ -370,6 +369,7 @@ public class Scribe { final String pkgName; final long curBalance; final List<Ledger.Transaction> transactions = new ArrayList<>(); + final List<Ledger.RewardBucket> rewardBuckets = new ArrayList<>(); pkgName = parser.getAttributeValue(null, XML_ATTR_PACKAGE_NAME); curBalance = parser.getAttributeLong(null, XML_ATTR_CURRENT_BALANCE); @@ -391,8 +391,7 @@ public class Scribe { } continue; } - if (eventType != XmlPullParser.START_TAG || !XML_TAG_TRANSACTION.equals(tagName)) { - // Expecting only "transaction" tags. + if (eventType != XmlPullParser.START_TAG || tagName == null) { Slog.e(TAG, "Unexpected event: (" + eventType + ") " + tagName); return null; } @@ -402,25 +401,37 @@ public class Scribe { if (DEBUG) { Slog.d(TAG, "Starting ledger tag: " + tagName); } - final String tag = parser.getAttributeValue(null, XML_ATTR_TAG); - final long startTime = parser.getAttributeLong(null, XML_ATTR_START_TIME); - final long endTime = parser.getAttributeLong(null, XML_ATTR_END_TIME); - final int eventId = parser.getAttributeInt(null, XML_ATTR_EVENT_ID); - final long delta = parser.getAttributeLong(null, XML_ATTR_DELTA); - final long ctp = parser.getAttributeLong(null, XML_ATTR_CTP); - if (endTime <= endTimeCutoff) { - if (DEBUG) { - Slog.d(TAG, "Skipping event because it's too old."); - } - continue; + switch (tagName) { + case XML_TAG_TRANSACTION: + final long endTime = parser.getAttributeLong(null, XML_ATTR_END_TIME); + if (endTime <= endTimeCutoff) { + if (DEBUG) { + Slog.d(TAG, "Skipping event because it's too old."); + } + continue; + } + final String tag = parser.getAttributeValue(null, XML_ATTR_TAG); + final long startTime = parser.getAttributeLong(null, XML_ATTR_START_TIME); + final int eventId = parser.getAttributeInt(null, XML_ATTR_EVENT_ID); + final long delta = parser.getAttributeLong(null, XML_ATTR_DELTA); + final long ctp = parser.getAttributeLong(null, XML_ATTR_CTP); + transactions.add( + new Ledger.Transaction(startTime, endTime, eventId, tag, delta, ctp)); + break; + case XML_TAG_REWARD_BUCKET: + rewardBuckets.add(readRewardBucketFromXml(parser)); + break; + default: + // Expecting only "transaction" and "rewardBucket" tags. + Slog.e(TAG, "Unexpected event: (" + eventType + ") " + tagName); + return null; } - transactions.add(new Ledger.Transaction(startTime, endTime, eventId, tag, delta, ctp)); } if (!isInstalled) { return null; } - return Pair.create(pkgName, new Ledger(curBalance, transactions)); + return Pair.create(pkgName, new Ledger(curBalance, transactions, rewardBuckets)); } /** @@ -508,6 +519,44 @@ public class Scribe { return report; } + /** + * @param parser Xml parser at the beginning of a {@value #XML_TAG_REWARD_BUCKET} tag. The next + * "parser.next()" call will take the parser into the body of the tag. + * @return Newly instantiated {@link Ledger.RewardBucket} holding all the information we just + * read out of the xml tag. + */ + @Nullable + private static Ledger.RewardBucket readRewardBucketFromXml(TypedXmlPullParser parser) + throws XmlPullParserException, IOException { + + final Ledger.RewardBucket rewardBucket = new Ledger.RewardBucket(); + + rewardBucket.startTimeMs = parser.getAttributeLong(null, XML_ATTR_START_TIME); + + for (int eventType = parser.next(); eventType != XmlPullParser.END_DOCUMENT; + eventType = parser.next()) { + final String tagName = parser.getName(); + if (eventType == XmlPullParser.END_TAG) { + if (XML_TAG_REWARD_BUCKET.equals(tagName)) { + // We've reached the end of the rewardBucket tag. + break; + } + continue; + } + if (eventType != XmlPullParser.START_TAG || !XML_ATTR_DELTA.equals(tagName)) { + // Expecting only delta tags. + Slog.e(TAG, "Unexpected event: (" + eventType + ") " + tagName); + return null; + } + + final int eventId = parser.getAttributeInt(null, XML_ATTR_EVENT_ID); + final long delta = parser.getAttributeLong(null, XML_ATTR_DELTA); + rewardBucket.cumulativeDelta.put(eventId, delta); + } + + return rewardBucket; + } + private void scheduleCleanup(long earliestEndTime) { if (earliestEndTime == Long.MAX_VALUE) { return; @@ -595,6 +644,11 @@ public class Scribe { } writeTransaction(out, transaction); } + + final List<Ledger.RewardBucket> rewardBuckets = ledger.getRewardBuckets(); + for (int r = 0; r < rewardBuckets.size(); ++r) { + writeRewardBucket(out, rewardBuckets.get(r)); + } out.endTag(null, XML_TAG_LEDGER); } out.endTag(null, XML_TAG_USER); @@ -616,6 +670,23 @@ public class Scribe { out.endTag(null, XML_TAG_TRANSACTION); } + private static void writeRewardBucket(@NonNull TypedXmlSerializer out, + @NonNull Ledger.RewardBucket rewardBucket) throws IOException { + final int numEvents = rewardBucket.cumulativeDelta.size(); + if (numEvents == 0) { + return; + } + out.startTag(null, XML_TAG_REWARD_BUCKET); + out.attributeLong(null, XML_ATTR_START_TIME, rewardBucket.startTimeMs); + for (int i = 0; i < numEvents; ++i) { + out.startTag(null, XML_ATTR_DELTA); + out.attributeInt(null, XML_ATTR_EVENT_ID, rewardBucket.cumulativeDelta.keyAt(i)); + out.attributeLong(null, XML_ATTR_DELTA, rewardBucket.cumulativeDelta.valueAt(i)); + out.endTag(null, XML_ATTR_DELTA); + } + out.endTag(null, XML_TAG_REWARD_BUCKET); + } + private static void writeReport(@NonNull TypedXmlSerializer out, @NonNull Analyst.Report report) throws IOException { out.startTag(null, XML_TAG_PERIOD_REPORT); diff --git a/services/tests/mockingservicestests/src/com/android/server/tare/ScribeTest.java b/services/tests/mockingservicestests/src/com/android/server/tare/ScribeTest.java index 721777ca6b38..13510adbb960 100644 --- a/services/tests/mockingservicestests/src/com/android/server/tare/ScribeTest.java +++ b/services/tests/mockingservicestests/src/com/android/server/tare/ScribeTest.java @@ -30,6 +30,7 @@ import android.content.pm.PackageInfo; import android.os.UserHandle; import android.util.Log; import android.util.SparseArrayMap; +import android.util.SparseLongArray; import androidx.test.InstrumentationRegistry; import androidx.test.filters.SmallTest; @@ -174,10 +175,13 @@ public class ScribeTest { when(mIrs.getConsumptionLimitLocked()).thenReturn(consumptionLimit); Ledger ledger = mScribeUnderTest.getLedgerLocked(TEST_USER_ID, TEST_PACKAGE); - ledger.recordTransaction(new Ledger.Transaction(0, 1000L, 1, null, 2000, 0)); + ledger.recordTransaction( + new Ledger.Transaction(0, 1000L, EconomicPolicy.TYPE_REWARD | 1, null, 2000, 0)); // Negative ledger balance shouldn't affect the total circulation value. ledger = mScribeUnderTest.getLedgerLocked(TEST_USER_ID + 1, TEST_PACKAGE); - ledger.recordTransaction(new Ledger.Transaction(0, 1000L, 1, null, -5000, 3000)); + ledger.recordTransaction( + new Ledger.Transaction(0, 1000L, + EconomicPolicy.TYPE_ACTION | 1, null, -5000, 3000)); mScribeUnderTest.setLastReclamationTimeLocked(lastReclamationTime); mScribeUnderTest.setConsumptionLimitLocked(consumptionLimit); mScribeUnderTest.adjustRemainingConsumableCakesLocked( @@ -209,9 +213,13 @@ public class ScribeTest { @Test public void testWritingPopulatedLedgerToDisk() { final Ledger ogLedger = mScribeUnderTest.getLedgerLocked(TEST_USER_ID, TEST_PACKAGE); - ogLedger.recordTransaction(new Ledger.Transaction(0, 1000, 1, null, 51, 0)); - ogLedger.recordTransaction(new Ledger.Transaction(1500, 2000, 2, "green", 52, -1)); - ogLedger.recordTransaction(new Ledger.Transaction(2500, 3000, 3, "blue", 3, 12)); + ogLedger.recordTransaction( + new Ledger.Transaction(0, 1000, EconomicPolicy.TYPE_REWARD | 1, null, 51, 0)); + ogLedger.recordTransaction( + new Ledger.Transaction(1500, 2000, + EconomicPolicy.TYPE_REWARD | 2, "green", 52, -1)); + ogLedger.recordTransaction( + new Ledger.Transaction(2500, 3000, EconomicPolicy.TYPE_REWARD | 3, "blue", 3, 12)); mScribeUnderTest.writeImmediatelyForTesting(); mScribeUnderTest.loadFromDiskLocked(); @@ -230,11 +238,13 @@ public class ScribeTest { addInstalledPackage(userId, pkgName); final Ledger ledger = mScribeUnderTest.getLedgerLocked(userId, pkgName); ledger.recordTransaction(new Ledger.Transaction( - 0, 1000L * u + l, 1, null, -51L * u + l, 50)); + 0, 1000L * u + l, EconomicPolicy.TYPE_ACTION | 1, null, -51L * u + l, 50)); ledger.recordTransaction(new Ledger.Transaction( - 1500L * u + l, 2000L * u + l, 2 * u + l, "green" + u + l, 52L * u + l, 0)); + 1500L * u + l, 2000L * u + l, + EconomicPolicy.TYPE_REWARD | 2 * u + l, "green" + u + l, 52L * u + l, 0)); ledger.recordTransaction(new Ledger.Transaction( - 2500L * u + l, 3000L * u + l, 3 * u + l, "blue" + u + l, 3L * u + l, 0)); + 2500L * u + l, 3000L * u + l, + EconomicPolicy.TYPE_REWARD | 3 * u + l, "blue" + u + l, 3L * u + l, 0)); ledgers.add(userId, pkgName, ledger); } } @@ -248,9 +258,12 @@ public class ScribeTest { @Test public void testDiscardLedgerFromDisk() { final Ledger ogLedger = mScribeUnderTest.getLedgerLocked(TEST_USER_ID, TEST_PACKAGE); - ogLedger.recordTransaction(new Ledger.Transaction(0, 1000, 1, null, 51, 1)); - ogLedger.recordTransaction(new Ledger.Transaction(1500, 2000, 2, "green", 52, 0)); - ogLedger.recordTransaction(new Ledger.Transaction(2500, 3000, 3, "blue", 3, 1)); + ogLedger.recordTransaction( + new Ledger.Transaction(0, 1000, EconomicPolicy.TYPE_REWARD | 1, null, 51, 1)); + ogLedger.recordTransaction( + new Ledger.Transaction(1500, 2000, EconomicPolicy.TYPE_REWARD | 2, "green", 52, 0)); + ogLedger.recordTransaction( + new Ledger.Transaction(2500, 3000, EconomicPolicy.TYPE_REWARD | 3, "blue", 3, 1)); mScribeUnderTest.writeImmediatelyForTesting(); mScribeUnderTest.loadFromDiskLocked(); @@ -269,9 +282,12 @@ public class ScribeTest { public void testLoadingMissingPackageFromDisk() { final String pkgName = TEST_PACKAGE + ".uninstalled"; final Ledger ogLedger = mScribeUnderTest.getLedgerLocked(TEST_USER_ID, pkgName); - ogLedger.recordTransaction(new Ledger.Transaction(0, 1000, 1, null, 51, 1)); - ogLedger.recordTransaction(new Ledger.Transaction(1500, 2000, 2, "green", 52, 2)); - ogLedger.recordTransaction(new Ledger.Transaction(2500, 3000, 3, "blue", 3, 3)); + ogLedger.recordTransaction( + new Ledger.Transaction(0, 1000, EconomicPolicy.TYPE_REGULATION | 1, null, 51, 1)); + ogLedger.recordTransaction( + new Ledger.Transaction(1500, 2000, EconomicPolicy.TYPE_REWARD | 2, "green", 52, 2)); + ogLedger.recordTransaction( + new Ledger.Transaction(2500, 3000, EconomicPolicy.TYPE_ACTION | 3, "blue", -3, 3)); mScribeUnderTest.writeImmediatelyForTesting(); // Package isn't installed, so make sure it's not saved to memory after loading. @@ -283,9 +299,13 @@ public class ScribeTest { public void testLoadingMissingUserFromDisk() { final int userId = TEST_USER_ID + 1; final Ledger ogLedger = mScribeUnderTest.getLedgerLocked(userId, TEST_PACKAGE); - ogLedger.recordTransaction(new Ledger.Transaction(0, 1000, 1, null, 51, 0)); - ogLedger.recordTransaction(new Ledger.Transaction(1500, 2000, 2, "green", 52, 1)); - ogLedger.recordTransaction(new Ledger.Transaction(2500, 3000, 3, "blue", 3, 3)); + ogLedger.recordTransaction( + new Ledger.Transaction(0, 1000, EconomicPolicy.TYPE_REWARD | 1, null, 51, 0)); + ogLedger.recordTransaction( + new Ledger.Transaction(1500, 2000, EconomicPolicy.TYPE_REWARD | 2, "green", 52, 1)); + ogLedger.recordTransaction( + new Ledger.Transaction(2500, 3000, + EconomicPolicy.TYPE_REGULATION | 3, "blue", 3, 3)); mScribeUnderTest.writeImmediatelyForTesting(); // User doesn't show up with any packages, so make sure nothing is saved after loading. @@ -331,12 +351,34 @@ public class ScribeTest { } assertNotNull(actual); assertEquals(expected.getCurrentBalance(), actual.getCurrentBalance()); + List<Ledger.Transaction> expectedTransactions = expected.getTransactions(); List<Ledger.Transaction> actualTransactions = actual.getTransactions(); assertEquals(expectedTransactions.size(), actualTransactions.size()); for (int i = 0; i < expectedTransactions.size(); ++i) { assertTransactionsEqual(expectedTransactions.get(i), actualTransactions.get(i)); } + + List<Ledger.RewardBucket> expectedRewardBuckets = expected.getRewardBuckets(); + List<Ledger.RewardBucket> actualRewardBuckets = actual.getRewardBuckets(); + assertEquals(expectedRewardBuckets.size(), actualRewardBuckets.size()); + for (int i = 0; i < expectedRewardBuckets.size(); ++i) { + assertRewardBucketsEqual(expectedRewardBuckets.get(i), actualRewardBuckets.get(i)); + } + } + + private void assertSparseLongArraysEqual(SparseLongArray expected, SparseLongArray actual) { + if (expected == null) { + assertNull(actual); + return; + } + assertNotNull(actual); + final int size = expected.size(); + assertEquals(size, actual.size()); + for (int i = 0; i < size; ++i) { + assertEquals(expected.keyAt(i), actual.keyAt(i)); + assertEquals(expected.valueAt(i), actual.valueAt(i)); + } } private void assertReportListsEqual(List<Analyst.Report> expected, @@ -382,6 +424,17 @@ public class ScribeTest { } } + private void assertRewardBucketsEqual(Ledger.RewardBucket expected, + Ledger.RewardBucket actual) { + if (expected == null) { + assertNull(actual); + return; + } + assertNotNull(actual); + assertEquals(expected.startTimeMs, actual.startTimeMs); + assertSparseLongArraysEqual(expected.cumulativeDelta, actual.cumulativeDelta); + } + private void assertTransactionsEqual(Ledger.Transaction expected, Ledger.Transaction actual) { if (expected == null) { assertNull(actual); diff --git a/services/tests/servicestests/src/com/android/server/tare/LedgerTest.java b/services/tests/servicestests/src/com/android/server/tare/LedgerTest.java index 22dcf842906c..54566c39a8d2 100644 --- a/services/tests/servicestests/src/com/android/server/tare/LedgerTest.java +++ b/services/tests/servicestests/src/com/android/server/tare/LedgerTest.java @@ -22,7 +22,12 @@ import static android.text.format.DateUtils.MINUTE_IN_MILLIS; import static com.android.server.tare.TareUtils.getCurrentTimeMillis; import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertNotNull; import static org.junit.Assert.assertNull; +import static org.junit.Assert.assertTrue; + +import android.util.SparseLongArray; import androidx.test.filters.SmallTest; import androidx.test.runner.AndroidJUnit4; @@ -32,7 +37,10 @@ import org.junit.Test; import org.junit.runner.RunWith; import java.time.Clock; +import java.time.Duration; import java.time.ZoneOffset; +import java.util.ArrayList; +import java.util.List; /** Test that the ledger records transactions correctly. */ @RunWith(AndroidJUnit4.class) @@ -44,6 +52,11 @@ public class LedgerTest { TareUtils.sSystemClock = Clock.fixed(Clock.systemUTC().instant(), ZoneOffset.UTC); } + private void shiftSystemTime(long incrementMs) { + TareUtils.sSystemClock = + Clock.offset(TareUtils.sSystemClock, Duration.ofMillis(incrementMs)); + } + @Test public void testInitialState() { final Ledger ledger = new Ledger(); @@ -52,37 +65,149 @@ public class LedgerTest { } @Test + public void testInitialization_FullLists() { + final long balance = 1234567890L; + List<Ledger.Transaction> transactions = new ArrayList<>(); + List<Ledger.RewardBucket> rewardBuckets = new ArrayList<>(); + + final long now = getCurrentTimeMillis(); + Ledger.Transaction secondTxn = null; + Ledger.RewardBucket remainingBucket = null; + for (int i = 0; i < Ledger.MAX_TRANSACTION_COUNT; ++i) { + final long start = now - 10 * HOUR_IN_MILLIS + i * MINUTE_IN_MILLIS; + Ledger.Transaction transaction = new Ledger.Transaction( + start, start + MINUTE_IN_MILLIS, 1, null, 400, 0); + if (i == 1) { + secondTxn = transaction; + } + transactions.add(transaction); + } + for (int b = 0; b < Ledger.NUM_REWARD_BUCKET_WINDOWS; ++b) { + final long start = now - (Ledger.NUM_REWARD_BUCKET_WINDOWS - b) * 24 * HOUR_IN_MILLIS; + Ledger.RewardBucket rewardBucket = new Ledger.RewardBucket(); + rewardBucket.startTimeMs = start; + for (int r = 0; r < 5; ++r) { + rewardBucket.cumulativeDelta.put(EconomicPolicy.TYPE_REWARD | r, b * start + r); + } + if (b == Ledger.NUM_REWARD_BUCKET_WINDOWS - 1) { + remainingBucket = rewardBucket; + } + rewardBuckets.add(rewardBucket); + } + final Ledger ledger = new Ledger(balance, transactions, rewardBuckets); + assertEquals(balance, ledger.getCurrentBalance()); + assertEquals(transactions, ledger.getTransactions()); + // Everything but the last bucket is old, so the returned list should only contain that + // bucket. + rewardBuckets.clear(); + rewardBuckets.add(remainingBucket); + assertEquals(rewardBuckets, ledger.getRewardBuckets()); + + // Make sure the ledger can properly record new transactions. + final long start = now - MINUTE_IN_MILLIS; + final long delta = 400; + final Ledger.Transaction transaction = new Ledger.Transaction( + start, start + MINUTE_IN_MILLIS, EconomicPolicy.TYPE_REWARD | 1, null, delta, 0); + ledger.recordTransaction(transaction); + assertEquals(balance + delta, ledger.getCurrentBalance()); + transactions = ledger.getTransactions(); + assertEquals(secondTxn, transactions.get(0)); + assertEquals(transaction, transactions.get(Ledger.MAX_TRANSACTION_COUNT - 1)); + final Ledger.RewardBucket rewardBucket = new Ledger.RewardBucket(); + rewardBucket.startTimeMs = now; + rewardBucket.cumulativeDelta.put(EconomicPolicy.TYPE_REWARD | 1, delta); + rewardBuckets = ledger.getRewardBuckets(); + assertRewardBucketsEqual(remainingBucket, rewardBuckets.get(0)); + assertRewardBucketsEqual(rewardBucket, rewardBuckets.get(1)); + } + + @Test + public void testInitialization_OverflowingLists() { + final long balance = 1234567890L; + final List<Ledger.Transaction> transactions = new ArrayList<>(); + final List<Ledger.RewardBucket> rewardBuckets = new ArrayList<>(); + + final long now = getCurrentTimeMillis(); + for (int i = 0; i < 2 * Ledger.MAX_TRANSACTION_COUNT; ++i) { + final long start = now - 20 * HOUR_IN_MILLIS + i * MINUTE_IN_MILLIS; + Ledger.Transaction transaction = new Ledger.Transaction( + start, start + MINUTE_IN_MILLIS, 1, null, 400, 0); + transactions.add(transaction); + } + for (int b = 0; b < 2 * Ledger.NUM_REWARD_BUCKET_WINDOWS; ++b) { + final long start = now + - (2 * Ledger.NUM_REWARD_BUCKET_WINDOWS - b) * 6 * HOUR_IN_MILLIS; + Ledger.RewardBucket rewardBucket = new Ledger.RewardBucket(); + rewardBucket.startTimeMs = start; + for (int r = 0; r < 5; ++r) { + rewardBucket.cumulativeDelta.put(EconomicPolicy.TYPE_REWARD | r, b * start + r); + } + rewardBuckets.add(rewardBucket); + } + final Ledger ledger = new Ledger(balance, transactions, rewardBuckets); + assertEquals(balance, ledger.getCurrentBalance()); + assertEquals(transactions.subList(Ledger.MAX_TRANSACTION_COUNT, + 2 * Ledger.MAX_TRANSACTION_COUNT), + ledger.getTransactions()); + assertEquals(rewardBuckets.subList(Ledger.NUM_REWARD_BUCKET_WINDOWS, + 2 * Ledger.NUM_REWARD_BUCKET_WINDOWS), + ledger.getRewardBuckets()); + } + + @Test public void testMultipleTransactions() { final Ledger ledger = new Ledger(); ledger.recordTransaction(new Ledger.Transaction(0, 1000, 1, null, 5, 0)); assertEquals(5, ledger.getCurrentBalance()); - assertEquals(5, ledger.get24HourSum(1, 60_000)); ledger.recordTransaction(new Ledger.Transaction(2000, 2000, 1, null, 25, 0)); assertEquals(30, ledger.getCurrentBalance()); - assertEquals(30, ledger.get24HourSum(1, 60_000)); ledger.recordTransaction(new Ledger.Transaction(5000, 5500, 1, null, -10, 5)); assertEquals(20, ledger.getCurrentBalance()); - assertEquals(20, ledger.get24HourSum(1, 60_000)); } @Test public void test24HourSum() { + final long now = getCurrentTimeMillis(); + final long end = now + 24 * HOUR_IN_MILLIS; + final int reward1 = EconomicPolicy.TYPE_REWARD | 1; + final int reward2 = EconomicPolicy.TYPE_REWARD | 2; final Ledger ledger = new Ledger(); - ledger.recordTransaction(new Ledger.Transaction(0, 1000, 1, null, 500, 0)); - assertEquals(500, ledger.get24HourSum(1, 24 * HOUR_IN_MILLIS)); + + // First bucket + assertEquals(0, ledger.get24HourSum(reward1, end)); + ledger.recordTransaction(new Ledger.Transaction(now, now + 1000, reward1, null, 500, 0)); + assertEquals(500, ledger.get24HourSum(reward1, end)); + assertEquals(0, ledger.get24HourSum(reward2, end)); + ledger.recordTransaction( + new Ledger.Transaction(now + 2 * HOUR_IN_MILLIS, now + 3 * HOUR_IN_MILLIS, + reward1, null, 2500, 0)); + assertEquals(3000, ledger.get24HourSum(reward1, end)); + // Second bucket + shiftSystemTime(7 * HOUR_IN_MILLIS); // now + 7 + ledger.recordTransaction( + new Ledger.Transaction(now + 7 * HOUR_IN_MILLIS, now + 7 * HOUR_IN_MILLIS, + reward1, null, 1, 0)); ledger.recordTransaction( - new Ledger.Transaction(2 * HOUR_IN_MILLIS, 3 * HOUR_IN_MILLIS, 1, null, 2500, 0)); - assertEquals(3000, ledger.get24HourSum(1, 24 * HOUR_IN_MILLIS)); + new Ledger.Transaction(now + 7 * HOUR_IN_MILLIS, now + 7 * HOUR_IN_MILLIS, + reward2, null, 42, 0)); + assertEquals(3001, ledger.get24HourSum(reward1, end)); + assertEquals(42, ledger.get24HourSum(reward2, end)); + // Third bucket + shiftSystemTime(12 * HOUR_IN_MILLIS); // now + 19 ledger.recordTransaction( - new Ledger.Transaction(4 * HOUR_IN_MILLIS, 4 * HOUR_IN_MILLIS, 1, null, 1, 0)); - assertEquals(3001, ledger.get24HourSum(1, 24 * HOUR_IN_MILLIS)); - assertEquals(2501, ledger.get24HourSum(1, 25 * HOUR_IN_MILLIS)); - assertEquals(2501, ledger.get24HourSum(1, 26 * HOUR_IN_MILLIS)); - // Pro-rated as the second transaction phases out - assertEquals(1251, - ledger.get24HourSum(1, 26 * HOUR_IN_MILLIS + 30 * MINUTE_IN_MILLIS)); - assertEquals(1, ledger.get24HourSum(1, 27 * HOUR_IN_MILLIS)); - assertEquals(0, ledger.get24HourSum(1, 28 * HOUR_IN_MILLIS)); + new Ledger.Transaction(now + 12 * HOUR_IN_MILLIS, now + 13 * HOUR_IN_MILLIS, + reward1, null, 300, 0)); + assertEquals(3301, ledger.get24HourSum(reward1, end)); + assertRewardBucketsInOrder(ledger.getRewardBuckets()); + // Older buckets should be excluded + assertEquals(301, ledger.get24HourSum(reward1, end + HOUR_IN_MILLIS)); + assertEquals(301, ledger.get24HourSum(reward1, end + 2 * HOUR_IN_MILLIS)); + // 2nd bucket should still be included since it started at the 7 hour mark + assertEquals(301, ledger.get24HourSum(reward1, end + 6 * HOUR_IN_MILLIS)); + assertEquals(42, ledger.get24HourSum(reward2, end + 6 * HOUR_IN_MILLIS)); + assertEquals(300, ledger.get24HourSum(reward1, end + 7 * HOUR_IN_MILLIS + 1)); + assertEquals(0, ledger.get24HourSum(reward2, end + 8 * HOUR_IN_MILLIS)); + assertEquals(0, ledger.get24HourSum(reward1, end + 19 * HOUR_IN_MILLIS + 1)); } @Test @@ -125,4 +250,127 @@ public class LedgerTest { ledger.removeOldTransactions(0); assertNull(ledger.getEarliestTransaction()); } + + @Test + public void testTransactionsAlwaysInOrder() { + final Ledger ledger = new Ledger(); + List<Ledger.Transaction> transactions = ledger.getTransactions(); + assertTrue(transactions.isEmpty()); + + final long now = getCurrentTimeMillis(); + Ledger.Transaction transaction1 = new Ledger.Transaction( + now - 48 * HOUR_IN_MILLIS, now - 40 * HOUR_IN_MILLIS, 1, null, 4800, 0); + Ledger.Transaction transaction2 = new Ledger.Transaction( + now - 24 * HOUR_IN_MILLIS, now - 23 * HOUR_IN_MILLIS, 1, null, 600, 0); + Ledger.Transaction transaction3 = new Ledger.Transaction( + now - 22 * HOUR_IN_MILLIS, now - 21 * HOUR_IN_MILLIS, 1, null, 600, 0); + // Instant event + Ledger.Transaction transaction4 = new Ledger.Transaction( + now - 20 * HOUR_IN_MILLIS, now - 20 * HOUR_IN_MILLIS, 1, null, 500, 0); + + Ledger.Transaction transaction5 = new Ledger.Transaction( + now - 15 * HOUR_IN_MILLIS, now - 15 * HOUR_IN_MILLIS + MINUTE_IN_MILLIS, + 1, null, 400, 0); + ledger.recordTransaction(transaction1); + ledger.recordTransaction(transaction2); + ledger.recordTransaction(transaction3); + ledger.recordTransaction(transaction4); + ledger.recordTransaction(transaction5); + + transactions = ledger.getTransactions(); + assertEquals(5, transactions.size()); + assertTransactionsInOrder(transactions); + + for (int i = 0; i < Ledger.MAX_TRANSACTION_COUNT - 5; ++i) { + final long start = now - 10 * HOUR_IN_MILLIS + i * MINUTE_IN_MILLIS; + Ledger.Transaction transaction = new Ledger.Transaction( + start, start + MINUTE_IN_MILLIS, 1, null, 400, 0); + ledger.recordTransaction(transaction); + } + transactions = ledger.getTransactions(); + assertEquals(Ledger.MAX_TRANSACTION_COUNT, transactions.size()); + assertTransactionsInOrder(transactions); + + long start = now - 5 * HOUR_IN_MILLIS; + Ledger.Transaction transactionLast5 = new Ledger.Transaction( + start, start + MINUTE_IN_MILLIS, 1, null, 4800, 0); + start = now - 4 * HOUR_IN_MILLIS; + Ledger.Transaction transactionLast4 = new Ledger.Transaction( + start, start + MINUTE_IN_MILLIS, 1, null, 600, 0); + start = now - 3 * HOUR_IN_MILLIS; + Ledger.Transaction transactionLast3 = new Ledger.Transaction( + start, start + MINUTE_IN_MILLIS, 1, null, 600, 0); + // Instant event + start = now - 2 * HOUR_IN_MILLIS; + Ledger.Transaction transactionLast2 = new Ledger.Transaction( + start, start, 1, null, 500, 0); + Ledger.Transaction transactionLast1 = new Ledger.Transaction( + start, start + MINUTE_IN_MILLIS, 1, null, 400, 0); + ledger.recordTransaction(transactionLast5); + ledger.recordTransaction(transactionLast4); + ledger.recordTransaction(transactionLast3); + ledger.recordTransaction(transactionLast2); + ledger.recordTransaction(transactionLast1); + + transactions = ledger.getTransactions(); + assertEquals(Ledger.MAX_TRANSACTION_COUNT, transactions.size()); + assertTransactionsInOrder(transactions); + assertEquals(transactionLast1, transactions.get(Ledger.MAX_TRANSACTION_COUNT - 1)); + assertEquals(transactionLast2, transactions.get(Ledger.MAX_TRANSACTION_COUNT - 2)); + assertEquals(transactionLast3, transactions.get(Ledger.MAX_TRANSACTION_COUNT - 3)); + assertEquals(transactionLast4, transactions.get(Ledger.MAX_TRANSACTION_COUNT - 4)); + assertEquals(transactionLast5, transactions.get(Ledger.MAX_TRANSACTION_COUNT - 5)); + assertFalse(transactions.contains(transaction1)); + assertFalse(transactions.contains(transaction2)); + assertFalse(transactions.contains(transaction3)); + assertFalse(transactions.contains(transaction4)); + assertFalse(transactions.contains(transaction5)); + } + + private void assertSparseLongArraysEqual(SparseLongArray expected, SparseLongArray actual) { + if (expected == null) { + assertNull(actual); + return; + } + assertNotNull(actual); + final int size = expected.size(); + assertEquals(size, actual.size()); + for (int i = 0; i < size; ++i) { + assertEquals(expected.keyAt(i), actual.keyAt(i)); + assertEquals(expected.valueAt(i), actual.valueAt(i)); + } + } + + private void assertRewardBucketsEqual(Ledger.RewardBucket expected, + Ledger.RewardBucket actual) { + if (expected == null) { + assertNull(actual); + return; + } + assertNotNull(actual); + assertEquals(expected.startTimeMs, actual.startTimeMs); + assertSparseLongArraysEqual(expected.cumulativeDelta, actual.cumulativeDelta); + } + + private void assertRewardBucketsInOrder(List<Ledger.RewardBucket> rewardBuckets) { + assertNotNull(rewardBuckets); + for (int i = 1; i < rewardBuckets.size(); ++i) { + final Ledger.RewardBucket prev = rewardBuckets.get(i - 1); + final Ledger.RewardBucket cur = rewardBuckets.get(i); + assertTrue("Newer bucket stored before older bucket @ index " + i + + ": " + prev.startTimeMs + " vs " + cur.startTimeMs, + prev.startTimeMs <= cur.startTimeMs); + } + } + + private void assertTransactionsInOrder(List<Ledger.Transaction> transactions) { + assertNotNull(transactions); + for (int i = 1; i < transactions.size(); ++i) { + final Ledger.Transaction prev = transactions.get(i - 1); + final Ledger.Transaction cur = transactions.get(i); + assertTrue("Newer transaction stored before older transaction @ index " + i + + ": " + prev.endTimeMs + " vs " + cur.endTimeMs, + prev.endTimeMs <= cur.endTimeMs); + } + } } |