1 /*
2  * Copyright (C) 2022 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.am;
18 
19 import android.annotation.NonNull;
20 import android.util.Slog;
21 
22 import com.android.internal.annotations.VisibleForTesting;
23 
24 import java.util.Iterator;
25 import java.util.LinkedList;
26 
27 /**
28  * Base class to track certain individual event of app states, it groups the events into time-based
29  * slots, thus we could only track the total number of events in a slot, eliminating
30  * the needs to track the timestamps for each individual event. This will be much more memory
31  * efficient for the case of massive amount of events.
32  */
33 class BaseAppStateTimeSlotEvents extends BaseAppStateEvents<Integer> {
34 
35     static final boolean DEBUG_BASE_APP_TIME_SLOT_EVENTS = false;
36 
37     /**
38      * The size (in ms) of the timeslot, should be greater than 0 always.
39      */
40     final long mTimeSlotSize;
41 
42     /**
43      * The start timestamp of current timeslot.
44      */
45     long[] mCurSlotStartTime;
46 
BaseAppStateTimeSlotEvents(int uid, @NonNull String packageName, int numOfEventTypes, long timeslotSize, @NonNull String tag, @NonNull MaxTrackingDurationConfig maxTrackingDurationConfig)47     BaseAppStateTimeSlotEvents(int uid, @NonNull String packageName, int numOfEventTypes,
48             long timeslotSize, @NonNull String tag,
49             @NonNull MaxTrackingDurationConfig maxTrackingDurationConfig) {
50         super(uid, packageName, numOfEventTypes, tag, maxTrackingDurationConfig);
51         mTimeSlotSize = timeslotSize;
52         mCurSlotStartTime = new long[numOfEventTypes];
53     }
54 
BaseAppStateTimeSlotEvents(@onNull BaseAppStateTimeSlotEvents other)55     BaseAppStateTimeSlotEvents(@NonNull BaseAppStateTimeSlotEvents other) {
56         super(other);
57         mTimeSlotSize = other.mTimeSlotSize;
58         mCurSlotStartTime = new long[other.mCurSlotStartTime.length];
59         for (int i = 0; i < mCurSlotStartTime.length; i++) {
60             mCurSlotStartTime[i] = other.mCurSlotStartTime[i];
61         }
62     }
63 
64     @Override
add(LinkedList<Integer> events, LinkedList<Integer> otherEvents)65     LinkedList<Integer> add(LinkedList<Integer> events, LinkedList<Integer> otherEvents) {
66         if (DEBUG_BASE_APP_TIME_SLOT_EVENTS) {
67             Slog.wtf(mTag, "Called into BaseAppStateTimeSlotEvents#add unexpected.");
68         }
69         // This function is invalid semantically here without the information of time-bases.
70         return null;
71     }
72 
73     @Override
add(BaseAppStateEvents otherObj)74     void add(BaseAppStateEvents otherObj) {
75         if (otherObj == null || !(otherObj instanceof BaseAppStateTimeSlotEvents)) {
76             return;
77         }
78         final BaseAppStateTimeSlotEvents other = (BaseAppStateTimeSlotEvents) otherObj;
79         if (mEvents.length != other.mEvents.length) {
80             if (DEBUG_BASE_APP_TIME_SLOT_EVENTS) {
81                 Slog.wtf(mTag, "Incompatible event table this=" + this + ", other=" + other);
82             }
83             return;
84         }
85         for (int i = 0; i < mEvents.length; i++) {
86             final LinkedList<Integer> otherEvents = other.mEvents[i];
87             if (otherEvents == null || otherEvents.size() == 0) {
88                 continue;
89             }
90             LinkedList<Integer> events = mEvents[i];
91             if (events == null || events.size() == 0) {
92                 mEvents[i] = new LinkedList<Integer>(otherEvents);
93                 mCurSlotStartTime[i] = other.mCurSlotStartTime[i];
94                 continue;
95             }
96 
97             final LinkedList<Integer> dest = new LinkedList<>();
98             final Iterator<Integer> itl = events.iterator();
99             final Iterator<Integer> itr = otherEvents.iterator();
100             final long maxl = mCurSlotStartTime[i];
101             final long maxr = other.mCurSlotStartTime[i];
102             final long minl = maxl - mTimeSlotSize * (events.size() - 1);
103             final long minr = maxr - mTimeSlotSize * (otherEvents.size() - 1);
104             final long latest = Math.max(maxl, maxr);
105             final long earliest = Math.min(minl, minr);
106             for (long start = earliest; start <= latest; start += mTimeSlotSize) {
107                 dest.add((start >= minl && start <= maxl ? itl.next() : 0)
108                         + (start >= minr && start <= maxr ? itr.next() : 0));
109             }
110             mEvents[i] = dest;
111             if (maxl < maxr) {
112                 mCurSlotStartTime[i] = other.mCurSlotStartTime[i];
113             }
114             trimEvents(getEarliest(mCurSlotStartTime[i]), i);
115         }
116     }
117 
118     @Override
getTotalEventsSince(long since, long now, int index)119     int getTotalEventsSince(long since, long now, int index) {
120         final LinkedList<Integer> events = mEvents[index];
121         if (events == null || events.size() == 0) {
122             return 0;
123         }
124         final long start = getSlotStartTime(since);
125         if (start > mCurSlotStartTime[index]) {
126             return 0;
127         }
128         final long end = Math.min(getSlotStartTime(now), mCurSlotStartTime[index]);
129         final Iterator<Integer> it = events.descendingIterator();
130         int count = 0;
131         for (long time = mCurSlotStartTime[index]; time >= start && it.hasNext();
132                 time -= mTimeSlotSize) {
133             final int val = it.next();
134             if (time <= end) {
135                 count += val;
136             }
137         }
138         return count;
139     }
140 
addEvent(long now, int index)141     void addEvent(long now, int index) {
142         final long slot = getSlotStartTime(now);
143         if (DEBUG_BASE_APP_TIME_SLOT_EVENTS) {
144             Slog.i(mTag, "Adding event to slot " + slot);
145         }
146         LinkedList<Integer> events = mEvents[index];
147         if (events == null) {
148             events = new LinkedList<Integer>();
149             mEvents[index] = events;
150         }
151         if (events.size() == 0) {
152             events.add(1);
153         } else {
154             for (long start = mCurSlotStartTime[index]; start < slot; start += mTimeSlotSize) {
155                 events.add(0);
156             }
157             events.offerLast(events.pollLast() + 1);
158         }
159         mCurSlotStartTime[index] = slot;
160         trimEvents(getEarliest(now), index);
161     }
162 
163     @Override
trimEvents(long earliest, int index)164     void trimEvents(long earliest, int index) {
165         final LinkedList<Integer> events = mEvents[index];
166         if (events == null || events.size() == 0) {
167             return;
168         }
169         final long slot = getSlotStartTime(earliest);
170         for (long time = mCurSlotStartTime[index] - mTimeSlotSize * (events.size() - 1);
171                 time < slot && events.size() > 0; time += mTimeSlotSize) {
172             events.pop();
173         }
174     }
175 
getSlotStartTime(long timestamp)176     long getSlotStartTime(long timestamp) {
177         return timestamp - timestamp % mTimeSlotSize;
178     }
179 
180     @VisibleForTesting
getCurrentSlotStartTime(int index)181     long getCurrentSlotStartTime(int index) {
182         return mCurSlotStartTime[index];
183     }
184 }
185