Fix bad alarm delivery

The man bent over his hourglass,
A programmer of sorts. The day was green.

They said, "You have a blue hourglass,
You do not fire alarms when they're asked."

The man replied, "Alarms as they're asked
are changed within the blue hourglass."

And they said then, "But fire, you must
Alarms beyond us, yet themselves,

Alarms within the blue hourglass
That trigger exactly when they're asked."

 ---

Fix the delivery-fuzzing semantics that had been introduced in
81f9882b5aadd6a2289c9f521a06a7af5f35ebf0.  That patch turned out
to be incomplete; in particular, alarms scheduled later might require
the validity of an already-scheduled kernel alarm even if they did
not affect the head alarm batch directly, and this was not being
addressed.  For now, roll back the fuzzed delivery logic entirely.
(This is not a full revert because that patch also caused exact alarms
to be considered standalone for batching purposes, and we need to
preserve that new policy.)

Bug 18726690
Bug 18765436

This is a 'git revert' of 81f9882b5aadd6a2289c9f521a06a7af5f35ebf0
*except* that this CL preserves the "exact alarms are treated as
standalone" portion of the original patch.

(Cherrypick of 5c3e277fb42bd799287936c5aee0d30fbcc7e65c from its
original branch.)

Change-Id: Ib9c3200f7e6bc6fa0c9928ee9db4cfd87f039353
diff --git a/services/core/java/com/android/server/AlarmManagerService.java b/services/core/java/com/android/server/AlarmManagerService.java
index 47bf188..a9a756e 100644
--- a/services/core/java/com/android/server/AlarmManagerService.java
+++ b/services/core/java/com/android/server/AlarmManagerService.java
@@ -61,7 +61,6 @@
 import java.util.HashMap;
 import java.util.LinkedList;
 import java.util.Locale;
-import java.util.Random;
 import java.util.TimeZone;
 
 import static android.app.AlarmManager.RTC_WAKEUP;
@@ -115,12 +114,8 @@
     final Object mLock = new Object();
 
     long mNativeData;
-
-    private final Random mFuzzer = new Random();
-    private long mNextWakeupBatchStart;     // nominal start of next wakeup's delivery window
-    private long mNextWakeup;               // actual scheduled next wakeup within that window
+    private long mNextWakeup;
     private long mNextNonWakeup;
-
     int mBroadcastRefCount = 0;
     PowerManager.WakeLock mWakeLock;
     boolean mLastWakeLockUnimportantForLogging;
@@ -372,27 +367,14 @@
 
     static class BatchTimeOrder implements Comparator<Batch> {
         public int compare(Batch b1, Batch b2) {
-            final long start1 = b1.start;
-            final long start2 = b2.start;
-            if (start1 > start2) {
+            long when1 = b1.start;
+            long when2 = b2.start;
+            if (when1 - when2 > 0) {
                 return 1;
             }
-            if (start1 < start2) {
+            if (when1 - when2 < 0) {
                 return -1;
             }
-
-            // Identical trigger times.  As a secondary ordering, require that
-            // the batch with the shorter allowable delivery window sorts first.
-            final long interval1 = b1.end - b1.start;
-            final long interval2 = b2.end - b2.start;
-            if (interval1 > interval2) {
-                return 1;
-            }
-            if (interval2 < interval1) {
-                return -1;
-            }
-
-            // equal start + delivery window => they're identical
             return 0;
         }
     }
@@ -615,7 +597,7 @@
     @Override
     public void onStart() {
         mNativeData = init();
-        mNextWakeup = mNextWakeupBatchStart = mNextNonWakeup = 0;
+        mNextWakeup = mNextNonWakeup = 0;
 
         // We have to set current TimeZone info to kernel
         // because kernel doesn't keep this after reboot
@@ -823,7 +805,6 @@
                         "AlarmManager.set");
             }
 
-            // Exact alarms are standalone; inexact get batched together
             setImpl(type, triggerAtTime, windowLength, interval, operation,
                     windowLength == AlarmManager.WINDOW_EXACT, workSource, alarmClock);
         }
@@ -896,7 +877,7 @@
 
             pw.print("nowRTC="); pw.print(nowRTC);
             pw.print("="); pw.print(sdf.format(new Date(nowRTC)));
-            pw.print(" nowELAPSED="); pw.print(nowELAPSED);
+            pw.print(" nowELAPSED="); TimeUtils.formatDuration(nowELAPSED, pw);
             pw.println();
             if (!mInteractive) {
                 pw.print("Time since non-interactive: ");
@@ -1102,6 +1083,17 @@
         return true;
     }
 
+    private Batch findFirstWakeupBatchLocked() {
+        final int N = mAlarmBatches.size();
+        for (int i = 0; i < N; i++) {
+            Batch b = mAlarmBatches.get(i);
+            if (b.hasWakeups()) {
+                return b;
+            }
+        }
+        return null;
+    }
+
     private AlarmManager.AlarmClockInfo getNextAlarmClockImpl(int userId) {
         synchronized (mLock) {
             return mNextAlarmClockForUser.get(userId);
@@ -1236,48 +1228,16 @@
         // prior to that which contains no wakeups, we schedule that as well.
         long nextNonWakeup = 0;
         if (mAlarmBatches.size() > 0) {
-            // Find the first wakeup alarm and note the following batch as well.  We'll be
-            // choosing a fuzzed delivery time within the first's allowable interval but
-            // ensuring that it does not encroach on the second's start time, to minimize
-            // alarm reordering.
-            Batch firstWakeup = null, nextAfterWakeup = null;
-            final int N = mAlarmBatches.size();
-            for (int i = 0; i < N; i++) {
-                Batch b = mAlarmBatches.get(i);
-                if (b.hasWakeups()) {
-                    firstWakeup = b;
-                    if (i < N-1) {
-                        nextAfterWakeup = mAlarmBatches.get(i+1);
-                    }
-                    break;
-                }
-            }
-
-            // There's a subtlety here: we depend on the invariant that if two batches
-            // exist with the same start time, the one with the shorter delivery window
-            // is sorted before the other.  This guarantees us that we need only look
-            // at the first [relevant] batch in the queue in order to schedule an alarm
-            // appropriately.
+            final Batch firstWakeup = findFirstWakeupBatchLocked();
             final Batch firstBatch = mAlarmBatches.get(0);
-            if (firstWakeup != null && mNextWakeupBatchStart != firstWakeup.start) {
-                mNextWakeupBatchStart = mNextWakeup = firstWakeup.start;
-                final long windowEnd = (nextAfterWakeup == null)
-                        ? firstWakeup.end
-                        : Math.min(firstWakeup.end, nextAfterWakeup.start);
-                final long interval = windowEnd - firstWakeup.start;
-                // if the interval is over maxint we're into crazy land anyway, but
-                // just in case we check and don't fuzz if the conversion to int for
-                // random-number purposes would blow up
-                if (interval > 0 && interval < Integer.MAX_VALUE) {
-                    mNextWakeup += mFuzzer.nextInt((int) interval);
-                }
-                setLocked(ELAPSED_REALTIME_WAKEUP, mNextWakeup);
+            if (firstWakeup != null && mNextWakeup != firstWakeup.start) {
+                mNextWakeup = firstWakeup.start;
+                setLocked(ELAPSED_REALTIME_WAKEUP, firstWakeup.start);
             }
             if (firstBatch != firstWakeup) {
                 nextNonWakeup = firstBatch.start;
             }
         }
-
         if (mPendingNonWakeupAlarms.size() > 0) {
             if (nextNonWakeup == 0 || mNextNonWakeupDeliveryTime < nextNonWakeup) {
                 nextNonWakeup = mNextNonWakeupDeliveryTime;