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.text.format.DateUtils.MINUTE_IN_MILLIS;
21 
22 import static com.android.server.tare.TareUtils.getCurrentTimeMillis;
23 
24 import static org.junit.Assert.assertEquals;
25 import static org.junit.Assert.assertFalse;
26 import static org.junit.Assert.assertNotNull;
27 import static org.junit.Assert.assertNull;
28 import static org.junit.Assert.assertTrue;
29 
30 import android.util.SparseLongArray;
31 
32 import androidx.test.filters.SmallTest;
33 import androidx.test.runner.AndroidJUnit4;
34 
35 import org.junit.Before;
36 import org.junit.Test;
37 import org.junit.runner.RunWith;
38 
39 import java.time.Clock;
40 import java.time.Duration;
41 import java.time.ZoneOffset;
42 import java.util.ArrayList;
43 import java.util.List;
44 
45 /** Test that the ledger records transactions correctly. */
46 @RunWith(AndroidJUnit4.class)
47 @SmallTest
48 public class LedgerTest {
49 
50     @Before
setUp()51     public void setUp() {
52         TareUtils.sSystemClock = Clock.fixed(Clock.systemUTC().instant(), ZoneOffset.UTC);
53     }
54 
shiftSystemTime(long incrementMs)55     private void shiftSystemTime(long incrementMs) {
56         TareUtils.sSystemClock =
57                 Clock.offset(TareUtils.sSystemClock, Duration.ofMillis(incrementMs));
58     }
59 
60     @Test
testInitialState()61     public void testInitialState() {
62         final Ledger ledger = new Ledger();
63         assertEquals(0, ledger.getCurrentBalance());
64         assertEquals(0, ledger.get24HourSum(0, 0));
65     }
66 
67     @Test
testInitialization_FullLists()68     public void testInitialization_FullLists() {
69         final long balance = 1234567890L;
70         List<Ledger.Transaction> transactions = new ArrayList<>();
71         List<Ledger.RewardBucket> rewardBuckets = new ArrayList<>();
72 
73         final long now = getCurrentTimeMillis();
74         Ledger.Transaction secondTxn = null;
75         Ledger.RewardBucket remainingBucket = null;
76         for (int i = 0; i < Ledger.MAX_TRANSACTION_COUNT; ++i) {
77             final long start = now - 10 * HOUR_IN_MILLIS + i * MINUTE_IN_MILLIS;
78             Ledger.Transaction transaction = new Ledger.Transaction(
79                     start, start + MINUTE_IN_MILLIS, 1, null, 400, 0);
80             if (i == 1) {
81                 secondTxn = transaction;
82             }
83             transactions.add(transaction);
84         }
85         for (int b = 0; b < Ledger.NUM_REWARD_BUCKET_WINDOWS; ++b) {
86             final long start = now - (Ledger.NUM_REWARD_BUCKET_WINDOWS - b) * 24 * HOUR_IN_MILLIS;
87             Ledger.RewardBucket rewardBucket = new Ledger.RewardBucket();
88             rewardBucket.startTimeMs = start;
89             for (int r = 0; r < 5; ++r) {
90                 rewardBucket.cumulativeDelta.put(EconomicPolicy.TYPE_REWARD | r, b * start + r);
91             }
92             if (b == Ledger.NUM_REWARD_BUCKET_WINDOWS - 1) {
93                 remainingBucket = rewardBucket;
94             }
95             rewardBuckets.add(rewardBucket);
96         }
97         final Ledger ledger = new Ledger(balance, transactions, rewardBuckets);
98         assertEquals(balance, ledger.getCurrentBalance());
99         assertEquals(transactions, ledger.getTransactions());
100         // Everything but the last bucket is old, so the returned list should only contain that
101         // bucket.
102         rewardBuckets.clear();
103         rewardBuckets.add(remainingBucket);
104         assertEquals(rewardBuckets, ledger.getRewardBuckets());
105 
106         // Make sure the ledger can properly record new transactions.
107         final long start = now - MINUTE_IN_MILLIS;
108         final long delta = 400;
109         final Ledger.Transaction transaction = new Ledger.Transaction(
110                 start, start + MINUTE_IN_MILLIS, EconomicPolicy.TYPE_REWARD | 1, null, delta, 0);
111         ledger.recordTransaction(transaction);
112         assertEquals(balance + delta, ledger.getCurrentBalance());
113         transactions = ledger.getTransactions();
114         assertEquals(secondTxn, transactions.get(0));
115         assertEquals(transaction, transactions.get(Ledger.MAX_TRANSACTION_COUNT - 1));
116         final Ledger.RewardBucket rewardBucket = new Ledger.RewardBucket();
117         rewardBucket.startTimeMs = now;
118         rewardBucket.cumulativeDelta.put(EconomicPolicy.TYPE_REWARD | 1, delta);
119         rewardBuckets = ledger.getRewardBuckets();
120         assertRewardBucketsEqual(remainingBucket, rewardBuckets.get(0));
121         assertRewardBucketsEqual(rewardBucket, rewardBuckets.get(1));
122     }
123 
124     @Test
testInitialization_OverflowingLists()125     public void testInitialization_OverflowingLists() {
126         final long balance = 1234567890L;
127         final List<Ledger.Transaction> transactions = new ArrayList<>();
128         final List<Ledger.RewardBucket> rewardBuckets = new ArrayList<>();
129 
130         final long now = getCurrentTimeMillis();
131         for (int i = 0; i < 2 * Ledger.MAX_TRANSACTION_COUNT; ++i) {
132             final long start = now - 20 * HOUR_IN_MILLIS + i * MINUTE_IN_MILLIS;
133             Ledger.Transaction transaction = new Ledger.Transaction(
134                     start, start + MINUTE_IN_MILLIS, 1, null, 400, 0);
135             transactions.add(transaction);
136         }
137         for (int b = 0; b < 2 * Ledger.NUM_REWARD_BUCKET_WINDOWS; ++b) {
138             final long start = now
139                     - (2 * Ledger.NUM_REWARD_BUCKET_WINDOWS - b) * 6 * HOUR_IN_MILLIS;
140             Ledger.RewardBucket rewardBucket = new Ledger.RewardBucket();
141             rewardBucket.startTimeMs = start;
142             for (int r = 0; r < 5; ++r) {
143                 rewardBucket.cumulativeDelta.put(EconomicPolicy.TYPE_REWARD | r, b * start + r);
144             }
145             rewardBuckets.add(rewardBucket);
146         }
147         final Ledger ledger = new Ledger(balance, transactions, rewardBuckets);
148         assertEquals(balance, ledger.getCurrentBalance());
149         assertEquals(transactions.subList(Ledger.MAX_TRANSACTION_COUNT,
150                         2 * Ledger.MAX_TRANSACTION_COUNT),
151                 ledger.getTransactions());
152         assertEquals(rewardBuckets.subList(Ledger.NUM_REWARD_BUCKET_WINDOWS,
153                         2 * Ledger.NUM_REWARD_BUCKET_WINDOWS),
154                 ledger.getRewardBuckets());
155     }
156 
157     @Test
testMultipleTransactions()158     public void testMultipleTransactions() {
159         final Ledger ledger = new Ledger();
160         ledger.recordTransaction(new Ledger.Transaction(0, 1000, 1, null, 5, 0));
161         assertEquals(5, ledger.getCurrentBalance());
162         ledger.recordTransaction(new Ledger.Transaction(2000, 2000, 1, null, 25, 0));
163         assertEquals(30, ledger.getCurrentBalance());
164         ledger.recordTransaction(new Ledger.Transaction(5000, 5500, 1, null, -10, 5));
165         assertEquals(20, ledger.getCurrentBalance());
166     }
167 
168     @Test
test24HourSum()169     public void test24HourSum() {
170         final long now = getCurrentTimeMillis();
171         final long end = now + 24 * HOUR_IN_MILLIS;
172         final int reward1 = EconomicPolicy.TYPE_REWARD | 1;
173         final int reward2 = EconomicPolicy.TYPE_REWARD | 2;
174         final Ledger ledger = new Ledger();
175 
176         // First bucket
177         assertEquals(0, ledger.get24HourSum(reward1, end));
178         ledger.recordTransaction(new Ledger.Transaction(now, now + 1000, reward1, null, 500, 0));
179         assertEquals(500, ledger.get24HourSum(reward1, end));
180         assertEquals(0, ledger.get24HourSum(reward2, end));
181         ledger.recordTransaction(
182                 new Ledger.Transaction(now + 2 * HOUR_IN_MILLIS, now + 3 * HOUR_IN_MILLIS,
183                         reward1, null, 2500, 0));
184         assertEquals(3000, ledger.get24HourSum(reward1, end));
185         // Second bucket
186         shiftSystemTime(7 * HOUR_IN_MILLIS); // now + 7
187         ledger.recordTransaction(
188                 new Ledger.Transaction(now + 7 * HOUR_IN_MILLIS, now + 7 * HOUR_IN_MILLIS,
189                         reward1, null, 1, 0));
190         ledger.recordTransaction(
191                 new Ledger.Transaction(now + 7 * HOUR_IN_MILLIS, now + 7 * HOUR_IN_MILLIS,
192                         reward2, null, 42, 0));
193         assertEquals(3001, ledger.get24HourSum(reward1, end));
194         assertEquals(42, ledger.get24HourSum(reward2, end));
195         // Third bucket
196         shiftSystemTime(12 * HOUR_IN_MILLIS); // now + 19
197         ledger.recordTransaction(
198                 new Ledger.Transaction(now + 12 * HOUR_IN_MILLIS, now + 13 * HOUR_IN_MILLIS,
199                         reward1, null, 300, 0));
200         assertEquals(3301, ledger.get24HourSum(reward1, end));
201         assertRewardBucketsInOrder(ledger.getRewardBuckets());
202         // Older buckets should be excluded
203         assertEquals(301, ledger.get24HourSum(reward1, end + HOUR_IN_MILLIS));
204         assertEquals(301, ledger.get24HourSum(reward1, end + 2 * HOUR_IN_MILLIS));
205         // 2nd bucket should still be included since it started at the 7 hour mark
206         assertEquals(301, ledger.get24HourSum(reward1, end + 6 * HOUR_IN_MILLIS));
207         assertEquals(42, ledger.get24HourSum(reward2, end + 6 * HOUR_IN_MILLIS));
208         assertEquals(300, ledger.get24HourSum(reward1, end + 7 * HOUR_IN_MILLIS + 1));
209         assertEquals(0, ledger.get24HourSum(reward2, end + 8 * HOUR_IN_MILLIS));
210         assertEquals(0, ledger.get24HourSum(reward1, end + 19 * HOUR_IN_MILLIS + 1));
211     }
212 
213     @Test
testRemoveOldTransactions()214     public void testRemoveOldTransactions() {
215         final Ledger ledger = new Ledger();
216         ledger.removeOldTransactions(24 * HOUR_IN_MILLIS);
217         assertNull(ledger.getEarliestTransaction());
218 
219         final long now = getCurrentTimeMillis();
220         Ledger.Transaction transaction1 = new Ledger.Transaction(
221                 now - 48 * HOUR_IN_MILLIS, now - 40 * HOUR_IN_MILLIS, 1, null, 4800, 0);
222         Ledger.Transaction transaction2 = new Ledger.Transaction(
223                 now - 24 * HOUR_IN_MILLIS, now - 23 * HOUR_IN_MILLIS, 1, null, 600, 0);
224         Ledger.Transaction transaction3 = new Ledger.Transaction(
225                 now - 22 * HOUR_IN_MILLIS, now - 21 * HOUR_IN_MILLIS, 1, null, 600, 0);
226         // Instant event
227         Ledger.Transaction transaction4 = new Ledger.Transaction(
228                 now - 20 * HOUR_IN_MILLIS, now - 20 * HOUR_IN_MILLIS, 1, null, 500, 0);
229         // Recent event
230         Ledger.Transaction transaction5 = new Ledger.Transaction(
231                 now - 5 * MINUTE_IN_MILLIS, now - MINUTE_IN_MILLIS, 1, null, 400, 0);
232         ledger.recordTransaction(transaction1);
233         ledger.recordTransaction(transaction2);
234         ledger.recordTransaction(transaction3);
235         ledger.recordTransaction(transaction4);
236         ledger.recordTransaction(transaction5);
237 
238         assertEquals(transaction1, ledger.getEarliestTransaction());
239         ledger.removeOldTransactions(24 * HOUR_IN_MILLIS);
240         assertEquals(transaction2, ledger.getEarliestTransaction());
241         ledger.removeOldTransactions(23 * HOUR_IN_MILLIS);
242         assertEquals(transaction3, ledger.getEarliestTransaction());
243         // Shouldn't delete transaction3 yet since there's still a piece of it within the min age
244         // window.
245         ledger.removeOldTransactions(21 * HOUR_IN_MILLIS + 30 * MINUTE_IN_MILLIS);
246         assertEquals(transaction3, ledger.getEarliestTransaction());
247         // Instant event should be removed as soon as we hit the exact threshold.
248         ledger.removeOldTransactions(20 * HOUR_IN_MILLIS);
249         assertEquals(transaction5, ledger.getEarliestTransaction());
250         ledger.removeOldTransactions(0);
251         assertNull(ledger.getEarliestTransaction());
252     }
253 
254     @Test
testTransactionsAlwaysInOrder()255     public void testTransactionsAlwaysInOrder() {
256         final Ledger ledger = new Ledger();
257         List<Ledger.Transaction> transactions = ledger.getTransactions();
258         assertTrue(transactions.isEmpty());
259 
260         final long now = getCurrentTimeMillis();
261         Ledger.Transaction transaction1 = new Ledger.Transaction(
262                 now - 48 * HOUR_IN_MILLIS, now - 40 * HOUR_IN_MILLIS, 1, null, 4800, 0);
263         Ledger.Transaction transaction2 = new Ledger.Transaction(
264                 now - 24 * HOUR_IN_MILLIS, now - 23 * HOUR_IN_MILLIS, 1, null, 600, 0);
265         Ledger.Transaction transaction3 = new Ledger.Transaction(
266                 now - 22 * HOUR_IN_MILLIS, now - 21 * HOUR_IN_MILLIS, 1, null, 600, 0);
267         // Instant event
268         Ledger.Transaction transaction4 = new Ledger.Transaction(
269                 now - 20 * HOUR_IN_MILLIS, now - 20 * HOUR_IN_MILLIS, 1, null, 500, 0);
270 
271         Ledger.Transaction transaction5 = new Ledger.Transaction(
272                 now - 15 * HOUR_IN_MILLIS, now - 15 * HOUR_IN_MILLIS + MINUTE_IN_MILLIS,
273                 1, null, 400, 0);
274         ledger.recordTransaction(transaction1);
275         ledger.recordTransaction(transaction2);
276         ledger.recordTransaction(transaction3);
277         ledger.recordTransaction(transaction4);
278         ledger.recordTransaction(transaction5);
279 
280         transactions = ledger.getTransactions();
281         assertEquals(5, transactions.size());
282         assertTransactionsInOrder(transactions);
283 
284         for (int i = 0; i < Ledger.MAX_TRANSACTION_COUNT - 5; ++i) {
285             final long start = now - 10 * HOUR_IN_MILLIS + i * MINUTE_IN_MILLIS;
286             Ledger.Transaction transaction = new Ledger.Transaction(
287                     start, start + MINUTE_IN_MILLIS, 1, null, 400, 0);
288             ledger.recordTransaction(transaction);
289         }
290         transactions = ledger.getTransactions();
291         assertEquals(Ledger.MAX_TRANSACTION_COUNT, transactions.size());
292         assertTransactionsInOrder(transactions);
293 
294         long start = now - 5 * HOUR_IN_MILLIS;
295         Ledger.Transaction transactionLast5 = new Ledger.Transaction(
296                 start, start + MINUTE_IN_MILLIS, 1, null, 4800, 0);
297         start = now - 4 * HOUR_IN_MILLIS;
298         Ledger.Transaction transactionLast4 = new Ledger.Transaction(
299                 start, start + MINUTE_IN_MILLIS, 1, null, 600, 0);
300         start = now - 3 * HOUR_IN_MILLIS;
301         Ledger.Transaction transactionLast3 = new Ledger.Transaction(
302                 start, start + MINUTE_IN_MILLIS, 1, null, 600, 0);
303         // Instant event
304         start = now - 2 * HOUR_IN_MILLIS;
305         Ledger.Transaction transactionLast2 = new Ledger.Transaction(
306                 start, start, 1, null, 500, 0);
307         Ledger.Transaction transactionLast1 = new Ledger.Transaction(
308                 start, start + MINUTE_IN_MILLIS, 1, null, 400, 0);
309         ledger.recordTransaction(transactionLast5);
310         ledger.recordTransaction(transactionLast4);
311         ledger.recordTransaction(transactionLast3);
312         ledger.recordTransaction(transactionLast2);
313         ledger.recordTransaction(transactionLast1);
314 
315         transactions = ledger.getTransactions();
316         assertEquals(Ledger.MAX_TRANSACTION_COUNT, transactions.size());
317         assertTransactionsInOrder(transactions);
318         assertEquals(transactionLast1, transactions.get(Ledger.MAX_TRANSACTION_COUNT - 1));
319         assertEquals(transactionLast2, transactions.get(Ledger.MAX_TRANSACTION_COUNT - 2));
320         assertEquals(transactionLast3, transactions.get(Ledger.MAX_TRANSACTION_COUNT - 3));
321         assertEquals(transactionLast4, transactions.get(Ledger.MAX_TRANSACTION_COUNT - 4));
322         assertEquals(transactionLast5, transactions.get(Ledger.MAX_TRANSACTION_COUNT - 5));
323         assertFalse(transactions.contains(transaction1));
324         assertFalse(transactions.contains(transaction2));
325         assertFalse(transactions.contains(transaction3));
326         assertFalse(transactions.contains(transaction4));
327         assertFalse(transactions.contains(transaction5));
328     }
329 
assertSparseLongArraysEqual(SparseLongArray expected, SparseLongArray actual)330     private void assertSparseLongArraysEqual(SparseLongArray expected, SparseLongArray actual) {
331         if (expected == null) {
332             assertNull(actual);
333             return;
334         }
335         assertNotNull(actual);
336         final int size = expected.size();
337         assertEquals(size, actual.size());
338         for (int i = 0; i < size; ++i) {
339             assertEquals(expected.keyAt(i), actual.keyAt(i));
340             assertEquals(expected.valueAt(i), actual.valueAt(i));
341         }
342     }
343 
assertRewardBucketsEqual(Ledger.RewardBucket expected, Ledger.RewardBucket actual)344     private void assertRewardBucketsEqual(Ledger.RewardBucket expected,
345             Ledger.RewardBucket actual) {
346         if (expected == null) {
347             assertNull(actual);
348             return;
349         }
350         assertNotNull(actual);
351         assertEquals(expected.startTimeMs, actual.startTimeMs);
352         assertSparseLongArraysEqual(expected.cumulativeDelta, actual.cumulativeDelta);
353     }
354 
assertRewardBucketsInOrder(List<Ledger.RewardBucket> rewardBuckets)355     private void assertRewardBucketsInOrder(List<Ledger.RewardBucket> rewardBuckets) {
356         assertNotNull(rewardBuckets);
357         for (int i = 1; i < rewardBuckets.size(); ++i) {
358             final Ledger.RewardBucket prev = rewardBuckets.get(i - 1);
359             final Ledger.RewardBucket cur = rewardBuckets.get(i);
360             assertTrue("Newer bucket stored before older bucket @ index " + i
361                             + ": " + prev.startTimeMs + " vs " + cur.startTimeMs,
362                     prev.startTimeMs <= cur.startTimeMs);
363         }
364     }
365 
assertTransactionsInOrder(List<Ledger.Transaction> transactions)366     private void assertTransactionsInOrder(List<Ledger.Transaction> transactions) {
367         assertNotNull(transactions);
368         for (int i = 1; i < transactions.size(); ++i) {
369             final Ledger.Transaction prev = transactions.get(i - 1);
370             final Ledger.Transaction cur = transactions.get(i);
371             assertTrue("Newer transaction stored before older transaction @ index " + i
372                             + ": " + prev.endTimeMs + " vs " + cur.endTimeMs,
373                     prev.endTimeMs <= cur.endTimeMs);
374         }
375     }
376 }
377