Fix a concurrency bug in the ranking reconsideration.

If we rely on mNotificationList to be sorted, then we cannot allow
records to change without a corresponding call to sort.  Currently
RankingFuture may modify records in a separate thread, while the sort
doesn't happen until later.  This creates a window for race conditions.

Instead, RankingFuture should record operations to be performed on the
record that will replayed later, in a transaction along with a sort.

We can't simply overwrite the old record completely because another
future may be concurrently modifying a different aspect of the record.
Two futures that attempt to modify the same aspect will be serialized
and the second will overwrite eventually the first.

Change-Id: I9223cabdc60f72d8e37e6d8119bea1e0127185c0
(cherry picked from commit 77d3e0d0297caca5358879d36e8ba77710eb8e82)

5 files changed, 88 insertions, 99 deletions

diff --git a/services/core/java/com/android/server/notification/NotificationIntrusivenessExtractor.java b/services/core/java/com/android/server/notification/NotificationIntrusivenessExtractor.java
index 125158f..db17f3a 100644
--- a/services/core/java/com/android/server/notification/NotificationIntrusivenessExtractor.java
+++ b/services/core/java/com/android/server/notification/NotificationIntrusivenessExtractor.java
@@ -20,7 +20,6 @@ import android.app.Notification;
 import android.content.Context;
 import android.util.Slog;
 
-import com.android.internal.R;
 import com.android.server.notification.NotificationManagerService.NotificationRecord;
 
 /**
@@ -39,7 +38,7 @@ public class NotificationIntrusivenessExtractor implements NotificationSignalExt
         if (DBG) Slog.d(TAG, "Initializing  " + getClass().getSimpleName() + ".");
     }
 
-    public RankingFuture process(NotificationRecord record) {
+    public RankingReconsideration process(NotificationRecord record) {
         if (record == null || record.getNotification() == null) {
             if (DBG) Slog.d(TAG, "skipping empty notification");
             return null;
@@ -54,10 +53,15 @@ public class NotificationIntrusivenessExtractor implements NotificationSignalExt
             record.setRecentlyIntusive(true);
         }
 
-        return new RankingFuture(record, HANG_TIME_MS) {
+        return new RankingReconsideration(record.getKey(), HANG_TIME_MS) {
             @Override
             public void work() {
-                mRecord.setRecentlyIntusive(false);
+                // pass
+            }
+
+            @Override
+            public void applyChangesLocked(NotificationRecord record) {
+                record.setRecentlyIntusive(false);
             }
         };
     }
diff --git a/services/core/java/com/android/server/notification/NotificationManagerService.java b/services/core/java/com/android/server/notification/NotificationManagerService.java
index 8641746..bbc3091 100644
--- a/services/core/java/com/android/server/notification/NotificationManagerService.java
+++ b/services/core/java/com/android/server/notification/NotificationManagerService.java
@@ -111,7 +111,6 @@ import java.util.Collections;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.NoSuchElementException;
-import java.util.concurrent.ExecutionException;
 import java.util.concurrent.TimeUnit;
 
 /** {@hide} */
@@ -453,8 +452,7 @@ public class NotificationManagerService extends SystemService {
 
 
 
-    public static final class NotificationRecord
-    {
+    public static final class NotificationRecord {
         final StatusBarNotification sbn;
         SingleNotificationStats stats;
         boolean isCanceled;
@@ -556,13 +554,13 @@ public class NotificationManagerService extends SystemService {
             return mContactAffinity;
         }
 
-        public boolean isRecentlyIntrusive() {
-            return mRecentlyIntrusive;
-        }
-
         public void setRecentlyIntusive(boolean recentlyIntrusive) {
             mRecentlyIntrusive = recentlyIntrusive;
         }
+
+        public boolean isRecentlyIntrusive() {
+            return mRecentlyIntrusive;
+        }
     }
 
     private static final class ToastRecord
@@ -1635,8 +1633,8 @@ public class NotificationManagerService extends SystemService {
                 if (!mSignalExtractors.isEmpty()) {
                     for (NotificationSignalExtractor extractor : mSignalExtractors) {
                         try {
-                            RankingFuture future = extractor.process(r);
-                            scheduleRankingReconsideration(future);
+                            RankingReconsideration recon = extractor.process(r);
+                            scheduleRankingReconsideration(recon);
                         } catch (Throwable t) {
                             Slog.w(TAG, "NotificationSignalExtractor failed.", t);
                         }
@@ -1982,39 +1980,40 @@ public class NotificationManagerService extends SystemService {
         }
     }
 
-    private void scheduleRankingReconsideration(RankingFuture future) {
-        if (future != null) {
-            Message m = Message.obtain(mRankingHandler, MESSAGE_RECONSIDER_RANKING, future);
-            long delay = future.getDelay(TimeUnit.MILLISECONDS);
+    private void scheduleRankingReconsideration(RankingReconsideration recon) {
+        if (recon != null) {
+            Message m = Message.obtain(mRankingHandler, MESSAGE_RECONSIDER_RANKING, recon);
+            long delay = recon.getDelay(TimeUnit.MILLISECONDS);
             mRankingHandler.sendMessageDelayed(m, delay);
         }
     }
 
     private void handleRankingReconsideration(Message message) {
-        if (!(message.obj instanceof RankingFuture)) return;
-
-        RankingFuture future = (RankingFuture) message.obj;
-        future.run();
-        try {
-            NotificationRecord record = future.get();
-            synchronized (mNotificationList) {
-                int before = mNotificationList.indexOf(record);
-                if (before != -1) {
-                    Collections.sort(mNotificationList, mRankingComparator);
-                    int after = mNotificationList.indexOf(record);
-
-                    if (before != after) {
-                        scheduleSendRankingUpdate();
-                    }
-                }
+        if (!(message.obj instanceof RankingReconsideration)) return;
+        RankingReconsideration recon = (RankingReconsideration) message.obj;
+        recon.run();
+        boolean orderChanged;
+        synchronized (mNotificationList) {
+            final NotificationRecord record = mNotificationsByKey.get(recon.getKey());
+            if (record == null) {
+                return;
             }
-        } catch (InterruptedException e) {
-            // we're running the future explicitly, so this should never happen
-        } catch (ExecutionException e) {
-            // we're running the future explicitly, so this should never happen
+            int before = findNotificationRecordIndexLocked(record);
+            recon.applyChangesLocked(record);
+            Collections.sort(mNotificationList, mRankingComparator);
+            int after = findNotificationRecordIndexLocked(record);
+            orderChanged = before != after;
+        }
+        if (orderChanged) {
+            scheduleSendRankingUpdate();
         }
     }
 
+    // lock on mNotificationList
+    private int findNotificationRecordIndexLocked(NotificationRecord target) {
+        return Collections.binarySearch(mNotificationList, target, mRankingComparator);
+    }
+
     private void scheduleSendRankingUpdate() {
         mHandler.removeMessages(MESSAGE_SEND_RANKING_UPDATE);
         Message m = Message.obtain(mHandler, MESSAGE_SEND_RANKING_UPDATE);
diff --git a/services/core/java/com/android/server/notification/NotificationSignalExtractor.java b/services/core/java/com/android/server/notification/NotificationSignalExtractor.java
index a41fdfe..71c819e 100644
--- a/services/core/java/com/android/server/notification/NotificationSignalExtractor.java
+++ b/services/core/java/com/android/server/notification/NotificationSignalExtractor.java
@@ -18,6 +18,8 @@ package com.android.server.notification;
 
 import android.content.Context;
 
+import com.android.server.notification.NotificationManagerService.NotificationRecord;
+
 /**
  * Extracts signals that will be useful to the {@link NotificationComparator} and caches them
  *  on the {@link NotificationManagerService.NotificationRecord} object. These annotations will
@@ -32,10 +34,10 @@ public interface NotificationSignalExtractor {
      * Called once per notification that is posted or updated.
      *
      * @return null if the work is done, or a future if there is more to do. The
-     * {@link RankingFuture} will be run on a worker thread, and if notifications are re-ordered
-     * by that execution, the {@link NotificationManagerService} may send order update
-     * events to the {@link android.service.notification.NotificationListenerService}s.
+     * {@link RankingReconsideration} will be run on a worker thread, and if notifications
+     * are re-ordered by that execution, the {@link NotificationManagerService} may send order
+     * update events to the {@link android.service.notification.NotificationListenerService}s.
      */
-    public RankingFuture process(NotificationManagerService.NotificationRecord notification);
+    public RankingReconsideration process(NotificationRecord notification);
 
 }
diff --git a/services/core/java/com/android/server/notification/RankingFuture.java b/services/core/java/com/android/server/notification/RankingReconsideration.java
index d711d02..cf5e210 100644
--- a/services/core/java/com/android/server/notification/RankingFuture.java
+++ b/services/core/java/com/android/server/notification/RankingReconsideration.java
@@ -15,14 +15,16 @@
  */
 package com.android.server.notification;
 
-import java.util.concurrent.Delayed;
-import java.util.concurrent.ExecutionException;
-import java.util.concurrent.ScheduledFuture;
+import com.android.server.notification.NotificationManagerService.NotificationRecord;
+
 import java.util.concurrent.TimeUnit;
-import java.util.concurrent.TimeoutException;
 
-public abstract class RankingFuture
-        implements ScheduledFuture<NotificationManagerService.NotificationRecord> {
+/**
+ * Represents future work required to extract signals from notifications for ranking.
+ *
+ * {@hide}
+ */
+public abstract class RankingReconsideration implements Runnable {
     private static final long IMMEDIATE = 0l;
 
     private static final int START = 0;
@@ -32,18 +34,22 @@ public abstract class RankingFuture
 
     private int mState;
     private long mDelay;
-    protected NotificationManagerService.NotificationRecord mRecord;
+    protected String mKey;
 
-    public RankingFuture(NotificationManagerService.NotificationRecord record) {
-        this(record, IMMEDIATE);
+    public RankingReconsideration(String key) {
+        this(key, IMMEDIATE);
     }
 
-    public RankingFuture(NotificationManagerService.NotificationRecord record, long delay) {
+    public RankingReconsideration(String key, long delay) {
         mDelay = delay;
-        mRecord = record;
+        mKey = key;
         mState = START;
     }
 
+    public String getKey() {
+        return mKey;
+    }
+
     public void run() {
         if (mState == START) {
             mState = RUNNING;
@@ -57,18 +63,10 @@ public abstract class RankingFuture
         }
     }
 
-    @Override
     public long getDelay(TimeUnit unit) {
         return unit.convert(mDelay, TimeUnit.MILLISECONDS);
     }
 
-    @Override
-    public int compareTo(Delayed another) {
-        return Long.compare(getDelay(TimeUnit.MILLISECONDS),
-                another.getDelay(TimeUnit.MILLISECONDS));
-    }
-
-    @Override
     public boolean cancel(boolean mayInterruptIfRunning) {
         if (mState == START) {  // can't cancel if running or done
             mState = CANCELLED;
@@ -77,42 +75,25 @@ public abstract class RankingFuture
         return false;
     }
 
-    @Override
     public boolean isCancelled() {
         return mState == CANCELLED;
     }
 
-    @Override
     public boolean isDone() {
         return mState == DONE;
     }
 
-    @Override
-    public NotificationManagerService.NotificationRecord get()
-            throws InterruptedException, ExecutionException {
-        while (!isDone()) {
-            synchronized (this) {
-                this.wait();
-            }
-        }
-        return mRecord;
-    }
-
-    @Override
-    public NotificationManagerService.NotificationRecord get(long timeout, TimeUnit unit)
-            throws InterruptedException, ExecutionException, TimeoutException {
-        long timeoutMillis = unit.convert(timeout, TimeUnit.MILLISECONDS);
-        long start = System.currentTimeMillis();
-        long now = System.currentTimeMillis();
-        while (!isDone() && (now - start) < timeoutMillis) {
-            try {
-                wait(timeoutMillis - (now - start));
-            } catch (InterruptedException e) {
-                now = System.currentTimeMillis();
-            }
-        }
-        return mRecord;
-    }
-
+    /**
+     * Analyse the notification.  This will be called on a worker thread. To
+     * avoid concurrency issues, do not use held references to modify the
+     * {@link NotificationRecord}.
+     */
     public abstract void work();
+
+    /**
+     * Apply any computed changes to the notification record.  This method will be
+     * called on the main service thread, synchronized on he mNotificationList.
+     * @param record The locked record to be updated.
+     */
+    public abstract void applyChangesLocked(NotificationRecord record);
 }
diff --git a/services/core/java/com/android/server/notification/ValidateNotificationPeople.java b/services/core/java/com/android/server/notification/ValidateNotificationPeople.java
index b5c2730..157d749 100644
--- a/services/core/java/com/android/server/notification/ValidateNotificationPeople.java
+++ b/services/core/java/com/android/server/notification/ValidateNotificationPeople.java
@@ -59,7 +59,7 @@ public class ValidateNotificationPeople implements NotificationSignalExtractor {
     // maps raw person handle to resolved person object
     private LruCache<String, LookupResult> mPeopleCache;
 
-    private RankingFuture validatePeople(NotificationRecord record) {
+    private RankingReconsideration validatePeople(final NotificationRecord record) {
         float affinity = NONE;
         Bundle extras = record.getNotification().extras;
         if (extras == null) {
@@ -99,11 +99,11 @@ public class ValidateNotificationPeople implements NotificationSignalExtractor {
         }
 
         if (DEBUG) Slog.d(TAG, "Pending: future work scheduled for: " + record.sbn.getKey());
-        return new RankingFuture(record) {
+        return new RankingReconsideration(record.getKey()) {
+            float mContactAffinity = NONE;
             @Override
             public void work() {
-                if (INFO) Slog.i(TAG, "Executing: validation for: " + mRecord.sbn.getKey());
-                float affinity = NONE;
+                if (INFO) Slog.i(TAG, "Executing: validation for: " + record.getKey());
                 for (final String handle: pendingLookups) {
                     LookupResult lookupResult = null;
                     final Uri uri = Uri.parse(handle);
@@ -124,13 +124,16 @@ public class ValidateNotificationPeople implements NotificationSignalExtractor {
                         synchronized (mPeopleCache) {
                             mPeopleCache.put(handle, lookupResult);
                         }
-                        affinity = Math.max(affinity, lookupResult.getAffinity());
+                        mContactAffinity = Math.max(mContactAffinity, lookupResult.getAffinity());
                     }
                 }
-                float affinityBound = mRecord.getContactAffinity();
-                affinity = Math.max(affinity, affinityBound);
-                mRecord.setContactAffinity(affinity);
-                if (INFO) Slog.i(TAG, "final affinity: " + affinity);
+            }
+
+            @Override
+            public void applyChangesLocked(NotificationRecord operand) {
+                float affinityBound = operand.getContactAffinity();
+                operand.setContactAffinity(Math.max(mContactAffinity, affinityBound));
+                if (INFO) Slog.i(TAG, "final affinity: " + operand.getContactAffinity());
             }
         };
     }
@@ -229,7 +232,7 @@ public class ValidateNotificationPeople implements NotificationSignalExtractor {
                 mContext.getContentResolver(), SETTING_ENABLE_PEOPLE_VALIDATOR, 1);
     }
 
-    public RankingFuture process(NotificationManagerService.NotificationRecord record) {
+    public RankingReconsideration process(NotificationRecord record) {
         if (!mEnabled) {
             if (INFO) Slog.i(TAG, "disabled");
             return null;