1 /*
2  * Copyright (C) 2020 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.alarm;
18 
19 import static com.android.server.alarm.AlarmManagerService.dumpAlarmList;
20 import static com.android.server.alarm.AlarmManagerService.isTimeTickAlarm;
21 
22 import android.app.AlarmManager;
23 import android.util.IndentingPrintWriter;
24 import android.util.Slog;
25 import android.util.proto.ProtoOutputStream;
26 
27 import com.android.internal.annotations.VisibleForTesting;
28 import com.android.internal.util.StatLogger;
29 
30 import java.text.SimpleDateFormat;
31 import java.util.ArrayList;
32 import java.util.Collections;
33 import java.util.Comparator;
34 import java.util.function.Predicate;
35 
36 /**
37  * Lazy implementation of an alarm store.
38  * This keeps the alarms in a sorted list, and only batches them at the time of delivery.
39  */
40 public class LazyAlarmStore implements AlarmStore {
41     @VisibleForTesting
42     static final String TAG = LazyAlarmStore.class.getSimpleName();
43     private static final long ALARM_DEADLINE_SLOP = 500;
44 
45     private final ArrayList<Alarm> mAlarms = new ArrayList<>();
46     private Runnable mOnAlarmClockRemoved;
47 
48     interface Stats {
49         int GET_NEXT_DELIVERY_TIME = 0;
50         int GET_NEXT_WAKEUP_DELIVERY_TIME = 1;
51         int GET_COUNT = 2;
52     }
53 
54     final StatLogger mStatLogger = new StatLogger(TAG + " stats", new String[]{
55             "GET_NEXT_DELIVERY_TIME",
56             "GET_NEXT_WAKEUP_DELIVERY_TIME",
57             "GET_COUNT",
58     });
59 
60     // Decreasing time order because it is more efficient to remove from the tail of an array list.
61     private static final Comparator<Alarm> sDecreasingTimeOrder = Comparator.comparingLong(
62             Alarm::getWhenElapsed).reversed();
63 
64     @Override
add(Alarm a)65     public void add(Alarm a) {
66         int index = Collections.binarySearch(mAlarms, a, sDecreasingTimeOrder);
67         if (index < 0) {
68             index = 0 - index - 1;
69         }
70         mAlarms.add(index, a);
71     }
72 
73     @Override
addAll(ArrayList<Alarm> alarms)74     public void addAll(ArrayList<Alarm> alarms) {
75         if (alarms == null) {
76             return;
77         }
78         mAlarms.addAll(alarms);
79         Collections.sort(mAlarms, sDecreasingTimeOrder);
80     }
81 
82     @Override
remove(Predicate<Alarm> whichAlarms)83     public ArrayList<Alarm> remove(Predicate<Alarm> whichAlarms) {
84         final ArrayList<Alarm> removedAlarms = new ArrayList<>();
85         for (int i = mAlarms.size() - 1; i >= 0; i--) {
86             if (whichAlarms.test(mAlarms.get(i))) {
87                 final Alarm removed = mAlarms.remove(i);
88                 if (removed.alarmClock != null && mOnAlarmClockRemoved != null) {
89                     mOnAlarmClockRemoved.run();
90                 }
91                 if (isTimeTickAlarm(removed)) {
92                     // This code path is not invoked when delivering alarms, only when removing
93                     // alarms due to the caller cancelling it or getting uninstalled, etc.
94                     Slog.wtf(TAG, "Removed TIME_TICK alarm");
95                 }
96                 removedAlarms.add(removed);
97             }
98         }
99         return removedAlarms;
100     }
101 
102     @Override
setAlarmClockRemovalListener(Runnable listener)103     public void setAlarmClockRemovalListener(Runnable listener) {
104         mOnAlarmClockRemoved = listener;
105     }
106 
107     @Override
getNextWakeFromIdleAlarm()108     public Alarm getNextWakeFromIdleAlarm() {
109         for (int i = mAlarms.size() - 1; i >= 0; i--) {
110             final Alarm alarm = mAlarms.get(i);
111             if ((alarm.flags & AlarmManager.FLAG_WAKE_FROM_IDLE) != 0) {
112                 return alarm;
113             }
114         }
115         return null;
116     }
117 
118     @Override
size()119     public int size() {
120         return mAlarms.size();
121     }
122 
123     @Override
getNextWakeupDeliveryTime()124     public long getNextWakeupDeliveryTime() {
125         final long start = mStatLogger.getTime();
126         long nextWakeup = 0;
127         for (int i = mAlarms.size() - 1; i >= 0; i--) {
128             final Alarm a = mAlarms.get(i);
129             if (!a.wakeup) {
130                 continue;
131             }
132             if (nextWakeup == 0) {
133                 nextWakeup = a.getMaxWhenElapsed();
134             } else {
135                 if (a.getWhenElapsed() > nextWakeup) {
136                     break;
137                 }
138                 nextWakeup = Math.min(nextWakeup, a.getMaxWhenElapsed());
139             }
140         }
141         mStatLogger.logDurationStat(Stats.GET_NEXT_WAKEUP_DELIVERY_TIME, start);
142         return nextWakeup;
143     }
144 
145     @Override
getNextDeliveryTime()146     public long getNextDeliveryTime() {
147         final long start = mStatLogger.getTime();
148         final int n = mAlarms.size();
149         if (n == 0) {
150             return 0;
151         }
152         long nextDelivery = mAlarms.get(n - 1).getMaxWhenElapsed();
153         for (int i = n - 2; i >= 0; i--) {
154             final Alarm a = mAlarms.get(i);
155             if (a.getWhenElapsed() > nextDelivery) {
156                 break;
157             }
158             nextDelivery = Math.min(nextDelivery, a.getMaxWhenElapsed());
159         }
160         mStatLogger.logDurationStat(Stats.GET_NEXT_DELIVERY_TIME, start);
161         return nextDelivery;
162     }
163 
164     @Override
removePendingAlarms(long nowElapsed)165     public ArrayList<Alarm> removePendingAlarms(long nowElapsed) {
166         final ArrayList<Alarm> pending = new ArrayList<>();
167 
168         // Only send wake-up alarms if this is the absolutely latest time we can evaluate
169         // for at least one wakeup alarm. This prevents sending other non-wakeup alarms when the
170         // screen is off but the CPU is awake for some reason.
171         boolean sendWakeups = false;
172 
173         // If any alarm with FLAG_STANDALONE is present, we cannot send any alarms without that flag
174         // in the present batch.
175         boolean standalonesOnly = false;
176 
177         for (int i = mAlarms.size() - 1; i >= 0; i--) {
178             final Alarm alarm = mAlarms.get(i);
179             if (alarm.getWhenElapsed() > nowElapsed) {
180                 break;
181             }
182             mAlarms.remove(i);
183             pending.add(alarm);
184             if (alarm.wakeup && alarm.getMaxWhenElapsed() <= nowElapsed + ALARM_DEADLINE_SLOP) {
185                 // Using some slop as it is better to send the wakeup alarm now, rather than
186                 // waking up again a short time later, just to send it.
187                 sendWakeups = true;
188             }
189             if ((alarm.flags & AlarmManager.FLAG_STANDALONE) != 0) {
190                 standalonesOnly = true;
191             }
192         }
193         final ArrayList<Alarm> toSend = new ArrayList<>();
194         for (int i = pending.size() - 1; i >= 0; i--) {
195             final Alarm pendingAlarm = pending.get(i);
196             if (!sendWakeups && pendingAlarm.wakeup) {
197                 continue;
198             }
199             if (standalonesOnly && (pendingAlarm.flags & AlarmManager.FLAG_STANDALONE) == 0) {
200                 continue;
201             }
202             pending.remove(i);
203             toSend.add(pendingAlarm);
204         }
205         // Perhaps some alarms could not be sent right now. Adding them back for later.
206         addAll(pending);
207         return toSend;
208     }
209 
210     @Override
updateAlarmDeliveries(AlarmDeliveryCalculator deliveryCalculator)211     public boolean updateAlarmDeliveries(AlarmDeliveryCalculator deliveryCalculator) {
212         boolean changed = false;
213         for (final Alarm alarm : mAlarms) {
214             changed |= deliveryCalculator.updateAlarmDelivery(alarm);
215         }
216         if (changed) {
217             Collections.sort(mAlarms, sDecreasingTimeOrder);
218         }
219         return changed;
220     }
221 
222     @Override
asList()223     public ArrayList<Alarm> asList() {
224         final ArrayList<Alarm> copy = new ArrayList<>(mAlarms);
225         Collections.reverse(copy);
226         return copy;
227     }
228 
229     @Override
dump(IndentingPrintWriter ipw, long nowElapsed, SimpleDateFormat sdf)230     public void dump(IndentingPrintWriter ipw, long nowElapsed, SimpleDateFormat sdf) {
231         ipw.println(mAlarms.size() + " pending alarms: ");
232         ipw.increaseIndent();
233         dumpAlarmList(ipw, mAlarms, nowElapsed, sdf);
234         ipw.decreaseIndent();
235         mStatLogger.dump(ipw);
236     }
237 
238     @Override
dumpProto(ProtoOutputStream pos, long nowElapsed)239     public void dumpProto(ProtoOutputStream pos, long nowElapsed) {
240         for (final Alarm a : mAlarms) {
241             a.dumpDebug(pos, AlarmManagerServiceDumpProto.PENDING_ALARMS, nowElapsed);
242         }
243     }
244 
245     @Override
getName()246     public String getName() {
247         return TAG;
248     }
249 
250     @Override
getCount(Predicate<Alarm> condition)251     public int getCount(Predicate<Alarm> condition) {
252         long start = mStatLogger.getTime();
253 
254         int count = 0;
255         for (final Alarm a : mAlarms) {
256             if (condition.test(a)) {
257                 count++;
258             }
259         }
260         mStatLogger.logDurationStat(Stats.GET_COUNT, start);
261         return count;
262     }
263 }
264