BackgroundScanScheduler: Optimize buckets

Optimize the buckets to ensure that the same channel is not scheduled
across multiple buckets. The settings are split if some of the channels
in the setting is already being scanned in lower time period bucket.
Also go thru each bucket and check if any of them don't fit into the
bucket specifications, if yes create split buckets with the same
time period. The split buckets will cumulatively contain all the channels
needed to be scanned in the original buckets.

BUG:28022609
Change-Id: Ie24bc3ec891965adad0ce6e855015be6ff5f0740
TEST: Compiles & unit-test passes

4 files changed, 605 insertions, 63 deletions

diff --git a/service/java/com/android/server/wifi/scanner/BackgroundScanScheduler.java b/service/java/com/android/server/wifi/scanner/BackgroundScanScheduler.java
index 949e7a0ad..94b53342a 100644
--- a/service/java/com/android/server/wifi/scanner/BackgroundScanScheduler.java
+++ b/service/java/com/android/server/wifi/scanner/BackgroundScanScheduler.java
@@ -22,6 +22,8 @@ import android.net.wifi.ScanResult;
 import android.net.wifi.WifiScanner;
 import android.net.wifi.WifiScanner.ScanData;
 import android.net.wifi.WifiScanner.ScanSettings;
+import android.util.ArraySet;
+import android.util.Pair;
 import android.util.Rational;
 import android.util.Slog;
 
@@ -32,10 +34,14 @@ import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.Iterator;
 import java.util.List;
+import java.util.ListIterator;
 import java.util.Map;
+import java.util.Set;
 
 /**
  * <p>This class takes a series of scan requests and formulates the best hardware level scanning
@@ -58,7 +64,8 @@ public class BackgroundScanScheduler {
     private static final boolean DBG = false;
 
     public static final int DEFAULT_MAX_BUCKETS = 8;
-    public static final int DEFAULT_MAX_CHANNELS = 32;
+    // Max channels that can be specified per bucket
+    public static final int DEFAULT_MAX_CHANNELS_PER_BUCKET = 16;
     // anecdotally, some chipsets will fail without explanation with a higher batch size, and
     // there is apparently no way to retrieve the maximum batch size
     public static final int DEFAULT_MAX_SCANS_TO_BATCH = 10;
@@ -116,14 +123,30 @@ public class BackgroundScanScheduler {
             (PREDEFINED_BUCKET_PERIODS.length - 1);
 
     /**
-     * this class is an intermediate representation for scheduling
+     * This class is an intermediate representation for scheduling. This maintins the channel
+     * collection to be scanned by the bucket as settings are added to it.
      */
     private class Bucket {
         public int period;
-        public final List<ScanSettings> settings = new ArrayList<>();
+        public int bucketId;
+        private final List<ScanSettings> mScanSettingsList = new ArrayList<>();
+        private final ChannelCollection mChannelCollection;
 
         Bucket(int period) {
             this.period = period;
+            this.bucketId = 0;
+            mScanSettingsList.clear();
+            mChannelCollection = mChannelHelper.createChannelCollection();
+        }
+
+        /**
+         * Copy constructor which populates the settings list from the original bucket object.
+         */
+        Bucket(Bucket originalBucket) {
+            this(originalBucket.period);
+            for (ScanSettings settings : originalBucket.getSettingsList()) {
+                mScanSettingsList.add(settings);
+            }
         }
 
         /**
@@ -135,20 +158,49 @@ public class BackgroundScanScheduler {
             return channelSettings;
         }
 
+        public boolean addSettings(ScanSettings scanSettings) {
+            mChannelCollection.addChannels(scanSettings);
+            return mScanSettingsList.add(scanSettings);
+        }
+
+        public boolean removeSettings(ScanSettings scanSettings) {
+            if (mScanSettingsList.remove(scanSettings)) {
+                // It's difficult to handle settings removal from buckets in terms of
+                // maintaining the correct channel collection, so recreate the channel
+                // collection from the remaining elements.
+                updateChannelCollection();
+                return true;
+            }
+            return false;
+        }
+
+        public List<ScanSettings> getSettingsList() {
+            return mScanSettingsList;
+        }
+
+        public void updateChannelCollection() {
+            mChannelCollection.clear();
+            for (ScanSettings settings : mScanSettingsList) {
+                mChannelCollection.addChannels(settings);
+            }
+        }
+
+        public ChannelCollection getChannelCollection() {
+            return mChannelCollection;
+        }
+
         /**
          * convert the setting for this bucket to HAL representation
          */
-        public WifiNative.BucketSettings createBucketSettings(int bucketId,
-                int maxChannels) {
+        public WifiNative.BucketSettings createBucketSettings(int bucketId, int maxChannels) {
+            this.bucketId = bucketId;
             int reportEvents = WifiScanner.REPORT_EVENT_NO_BATCH;
             int maxPeriodInMs = 0;
             int stepCount = 0;
             int bucketIndex = 0;
 
-            mChannelCollection.clear();
-
-            for (int i = 0; i < settings.size(); ++i) {
-                WifiScanner.ScanSettings setting = settings.get(i);
+            for (int i = 0; i < mScanSettingsList.size(); ++i) {
+                WifiScanner.ScanSettings setting = mScanSettingsList.get(i);
                 int requestedReportEvents = setting.reportEvents;
                 if ((requestedReportEvents & WifiScanner.REPORT_EVENT_NO_BATCH) == 0) {
                     reportEvents &= ~WifiScanner.REPORT_EVENT_NO_BATCH;
@@ -159,9 +211,6 @@ public class BackgroundScanScheduler {
                 if ((requestedReportEvents & WifiScanner.REPORT_EVENT_FULL_SCAN_RESULT) != 0) {
                     reportEvents |= WifiScanner.REPORT_EVENT_FULL_SCAN_RESULT;
                 }
-
-                mChannelCollection.addChannels(setting);
-
                 // For the bucket allocated to exponential back off scan, the values of
                 // the exponential back off scan related parameters from the very first
                 // setting in the settings list will be used to configure this bucket.
@@ -179,7 +228,6 @@ public class BackgroundScanScheduler {
                                     : setting.maxPeriodInMs;
                     stepCount = setting.stepCount;
                 }
-
             }
 
             WifiNative.BucketSettings bucketSettings = new WifiNative.BucketSettings();
@@ -197,6 +245,13 @@ public class BackgroundScanScheduler {
      * Maintains a list of buckets and the number that are active (non-null)
      */
     private class BucketList {
+        // Comparator to sort the buckets in order of increasing time periods
+        private final Comparator<Bucket> mTimePeriodSortComparator =
+                new Comparator<Bucket>() {
+                    public int compare(Bucket b1, Bucket b2) {
+                        return b1.period - b2.period;
+                    }
+                };
         private final Bucket[] mBuckets;
         private int mActiveBucketCount = 0;
 
@@ -248,10 +303,24 @@ public class BackgroundScanScheduler {
                 return mActiveBucketCount;
             }
         }
+
+        /**
+         * Returns the active regular buckets sorted by their increasing time periods.
+         */
+        public List<Bucket> getSortedActiveRegularBucketList() {
+            ArrayList<Bucket> activeBuckets = new ArrayList<>();
+            for (int i = 0; i < mBuckets.length; i++) {
+                if (mBuckets[i] != null && i != EXPONENTIAL_BACK_OFF_BUCKET_IDX) {
+                    activeBuckets.add(mBuckets[i]);
+                }
+            }
+            Collections.sort(activeBuckets, mTimePeriodSortComparator);
+            return activeBuckets;
+        }
     }
 
     private int mMaxBuckets = DEFAULT_MAX_BUCKETS;
-    private int mMaxChannels = DEFAULT_MAX_CHANNELS;
+    private int mMaxChannelsPerBucket = DEFAULT_MAX_CHANNELS_PER_BUCKET;
     private int mMaxBatch = DEFAULT_MAX_SCANS_TO_BATCH;
     private int mMaxApPerScan = DEFAULT_MAX_AP_PER_SCAN;
 
@@ -263,13 +332,13 @@ public class BackgroundScanScheduler {
         mMaxBuckets = maxBuckets;
     }
 
-    public int getMaxChannels() {
-        return mMaxChannels;
+    public int getMaxChannelsPerBucket() {
+        return mMaxChannelsPerBucket;
     }
 
     // TODO: find a way to get max channels
-    public void setMaxChannels(int maxChannels) {
-        mMaxChannels = maxChannels;
+    public void setMaxChannelsPerBucket(int maxChannels) {
+        mMaxChannelsPerBucket = maxChannels;
     }
 
     public int getMaxBatch() {
@@ -291,14 +360,13 @@ public class BackgroundScanScheduler {
 
     private final BucketList mBuckets = new BucketList();
     private final ChannelHelper mChannelHelper;
-    private final ChannelCollection mChannelCollection;
     private WifiNative.ScanSettings mSchedule;
-    private final Map<ScanSettings, Integer> mSettingsToScheduledBucket = new HashMap<>();
+    // This keeps track of the settings to the max time period bucket to which it was scheduled.
+    private final Map<ScanSettings, Bucket> mSettingsToScheduledBucket = new HashMap<>();
 
     public BackgroundScanScheduler(ChannelHelper channelHelper) {
         mChannelHelper = channelHelper;
-        mChannelCollection = mChannelHelper.createChannelCollection();
-        createSchedule();
+        createSchedule(new ArrayList<Bucket>(), getMaxChannelsPerBucket());
     }
 
     /**
@@ -313,7 +381,12 @@ public class BackgroundScanScheduler {
 
         compactBuckets(getMaxBuckets());
 
-        createSchedule();
+        List<Bucket> bucketList = optimizeBuckets();
+
+        List<Bucket> fixedBucketList =
+                fixBuckets(bucketList, getMaxBuckets(), getMaxChannelsPerBucket());
+
+        createSchedule(fixedBucketList, getMaxChannelsPerBucket());
     }
 
     /**
@@ -343,10 +416,13 @@ public class BackgroundScanScheduler {
                 getScheduledBucket(settings));
     }
 
-    private int getScheduledBucket(ScanSettings settings) {
-        Integer scheduledBucket = mSettingsToScheduledBucket.get(settings);
-        if (scheduledBucket != null) {
-            return scheduledBucket;
+    /**
+     * Retrieves the max time period bucket idx at which this setting was scheduled
+     */
+    public int getScheduledBucket(ScanSettings settings) {
+        Bucket maxScheduledBucket = mSettingsToScheduledBucket.get(settings);
+        if (maxScheduledBucket != null) {
+            return maxScheduledBucket.bucketId;
         } else {
             Slog.wtf(TAG, "No bucket found for settings");
             return -1;
@@ -356,11 +432,10 @@ public class BackgroundScanScheduler {
     /**
      * creates a schedule for the current buckets
      */
-    private void createSchedule() {
-        mSettingsToScheduledBucket.clear();
+    private void createSchedule(List<Bucket> bucketList, int maxChannelsPerBucket) {
         WifiNative.ScanSettings schedule = new WifiNative.ScanSettings();
-        schedule.num_buckets = mBuckets.getActiveCount();
-        schedule.buckets = new WifiNative.BucketSettings[mBuckets.getActiveCount()];
+        schedule.num_buckets = bucketList.size();
+        schedule.buckets = new WifiNative.BucketSettings[bucketList.size()];
 
         schedule.max_ap_per_scan = 0;
         schedule.report_threshold_num_scans = getMaxBatch();
@@ -368,34 +443,27 @@ public class BackgroundScanScheduler {
 
         // set all buckets in schedule
         int bucketId = 0;
-        for (int i = 0; i < mBuckets.size(); ++i) {
-            if (mBuckets.isActive(i)) {
-                schedule.buckets[bucketId] =
-                        mBuckets.get(i).createBucketSettings(bucketId, getMaxChannels());
-
-                for (ScanSettings settings : mBuckets.get(i).settings) {
-                    mSettingsToScheduledBucket.put(settings, bucketId);
-
-                    // set APs per scan
-                    if (settings.numBssidsPerScan > schedule.max_ap_per_scan) {
-                        schedule.max_ap_per_scan = settings.numBssidsPerScan;
-                    }
-
-                    // set batching
-                    if (settings.maxScansToCache != 0
-                            && settings.maxScansToCache < schedule.report_threshold_num_scans) {
-                        schedule.report_threshold_num_scans = settings.maxScansToCache;
-                    }
-
-                    // note hidden networks
-                    if (settings.hiddenNetworkIds != null) {
-                        for (int j = 0; j < settings.hiddenNetworkIds.length; j++) {
-                            hiddenNetworkIdSet.add(settings.hiddenNetworkIds[j]);
-                        }
+        for (Bucket bucket : bucketList) {
+            schedule.buckets[bucketId] =
+                    bucket.createBucketSettings(bucketId, maxChannelsPerBucket);
+            for (ScanSettings settings : bucket.getSettingsList()) {
+                // set APs per scan
+                if (settings.numBssidsPerScan > schedule.max_ap_per_scan) {
+                    schedule.max_ap_per_scan = settings.numBssidsPerScan;
+                }
+                // set batching
+                if (settings.maxScansToCache != 0
+                        && settings.maxScansToCache < schedule.report_threshold_num_scans) {
+                    schedule.report_threshold_num_scans = settings.maxScansToCache;
+                }
+                // note hidden networks
+                if (settings.hiddenNetworkIds != null) {
+                    for (int j = 0; j < settings.hiddenNetworkIds.length; j++) {
+                        hiddenNetworkIdSet.add(settings.hiddenNetworkIds[j]);
                     }
                 }
-                bucketId++;
             }
+            bucketId++;
         }
 
         schedule.report_threshold_percent = DEFAULT_REPORT_THRESHOLD_PERCENTAGE;
@@ -437,16 +505,14 @@ public class BackgroundScanScheduler {
     private void addScanToBuckets(ScanSettings settings) {
         int bucketIndex;
 
-        if (settings.maxPeriodInMs != 0
-                && settings.maxPeriodInMs != settings.periodInMs) {
+        if (settings.maxPeriodInMs != 0 && settings.maxPeriodInMs != settings.periodInMs) {
             // exponential back off scan has a dedicated bucket
             bucketIndex = EXPONENTIAL_BACK_OFF_BUCKET_IDX;
         } else {
-            bucketIndex = findBestRegularBucketIndex(settings.periodInMs,
-                                                     NUM_OF_REGULAR_BUCKETS);
+            bucketIndex = findBestRegularBucketIndex(settings.periodInMs, NUM_OF_REGULAR_BUCKETS);
         }
 
-        mBuckets.getOrCreate(bucketIndex).settings.add(settings);
+        mBuckets.getOrCreate(bucketIndex).addSettings(settings);
     }
 
     /**
@@ -485,12 +551,303 @@ public class BackgroundScanScheduler {
         for (int i = NUM_OF_REGULAR_BUCKETS - 1;
                 i >= 0 && mBuckets.getActiveRegularBucketCount() > maxRegularBuckets; --i) {
             if (mBuckets.isActive(i)) {
-                for (ScanSettings scanRequest : mBuckets.get(i).settings) {
+                for (ScanSettings scanRequest : mBuckets.get(i).getSettingsList()) {
                     int newBucketIndex = findBestRegularBucketIndex(scanRequest.periodInMs, i);
-                    mBuckets.getOrCreate(newBucketIndex).settings.add(scanRequest);
+                    mBuckets.getOrCreate(newBucketIndex).addSettings(scanRequest);
                 }
                 mBuckets.clear(i);
             }
         }
     }
+
+    /**
+     * Clone the provided scan settings fields to a new ScanSettings object.
+     */
+    private ScanSettings cloneScanSettings(ScanSettings originalSettings) {
+        ScanSettings settings = new ScanSettings();
+        settings.band = originalSettings.band;
+        settings.channels = originalSettings.channels;
+        settings.hiddenNetworkIds = originalSettings.hiddenNetworkIds;
+        settings.periodInMs = originalSettings.periodInMs;
+        settings.reportEvents = originalSettings.reportEvents;
+        settings.numBssidsPerScan = originalSettings.numBssidsPerScan;
+        settings.maxScansToCache = originalSettings.maxScansToCache;
+        settings.maxPeriodInMs = originalSettings.maxPeriodInMs;
+        settings.stepCount = originalSettings.stepCount;
+        settings.isPnoScan = originalSettings.isPnoScan;
+        return settings;
+    }
+
+    /**
+     * Creates a split scan setting that needs to be added back to the current bucket.
+     */
+    private ScanSettings createCurrentBucketSplitSettings(ScanSettings originalSettings,
+            Set<Integer> currentBucketChannels) {
+        ScanSettings currentBucketSettings = cloneScanSettings(originalSettings);
+        // Let's create a new settings for the current bucket with the same flags, but the missing
+        // channels from the other bucket
+        currentBucketSettings.band = WifiScanner.WIFI_BAND_UNSPECIFIED;
+        currentBucketSettings.channels = new WifiScanner.ChannelSpec[currentBucketChannels.size()];
+        int chanIdx = 0;
+        for (Integer channel : currentBucketChannels) {
+            currentBucketSettings.channels[chanIdx++] = new WifiScanner.ChannelSpec(channel);
+        }
+        return currentBucketSettings;
+    }
+
+    /**
+     * Creates a split scan setting that needs to be added to the target lower time period bucket.
+     * The reportEvents field is modified to remove REPORT_EVENT_AFTER_EACH_SCAN because we
+     * need this flag only in the higher time period bucket.
+     */
+    private ScanSettings createTargetBucketSplitSettings(ScanSettings originalSettings,
+            Set<Integer> targetBucketChannels) {
+        ScanSettings targetBucketSettings = cloneScanSettings(originalSettings);
+        // The new settings for the other bucket will have the channels that already in the that
+        // bucket. We'll need to do some migration of the |reportEvents| flags.
+        targetBucketSettings.band = WifiScanner.WIFI_BAND_UNSPECIFIED;
+        targetBucketSettings.channels = new WifiScanner.ChannelSpec[targetBucketChannels.size()];
+        int chanIdx = 0;
+        for (Integer channel : targetBucketChannels) {
+            targetBucketSettings.channels[chanIdx++] = new WifiScanner.ChannelSpec(channel);
+        }
+        targetBucketSettings.reportEvents =
+                originalSettings.reportEvents
+                        & (WifiScanner.REPORT_EVENT_NO_BATCH
+                                | WifiScanner.REPORT_EVENT_FULL_SCAN_RESULT);
+        return targetBucketSettings;
+    }
+
+    /**
+     * Split the scan settings into 2 so that they can be put into 2 separate buckets.
+     * @return The first scan setting needs to be added back to the current bucket
+     *         The second scan setting needs to be added to the other bucket
+     */
+    private Pair<ScanSettings, ScanSettings> createSplitSettings(ScanSettings originalSettings,
+            ChannelCollection targetBucketChannelCol) {
+        Set<Integer> currentBucketChannels =
+                targetBucketChannelCol.getMissingChannelsFromSettings(originalSettings);
+        Set<Integer> targetBucketChannels =
+                targetBucketChannelCol.getContainingChannelsFromSettings(originalSettings);
+        // Two Copy of the original settings
+        ScanSettings currentBucketSettings =
+                createCurrentBucketSplitSettings(originalSettings, currentBucketChannels);
+        ScanSettings targetBucketSettings =
+                createTargetBucketSplitSettings(originalSettings, targetBucketChannels);
+        return Pair.create(currentBucketSettings, targetBucketSettings);
+    }
+
+    /**
+     * Try to merge the settings to lower buckets.
+     * Check if the channels in this settings is already covered by a lower time period
+     * bucket. If it's partially covered, the settings is split else the entire settings
+     * is moved to the lower time period bucket.
+     * This method updates the |mSettingsToScheduledBucket| mapping.
+     * @return Pair<wasMerged, remainingSplitSettings>
+     *         wasMerged -  boolean indicating whether the original setting was merged to lower time
+     *                      period buckets.
+     *         remainingSplitSettings - Partial Scan Settings that need to be added back to the
+     *                                  current bucket.
+     */
+    private Pair<Boolean, ScanSettings> mergeSettingsToLowerBuckets(ScanSettings originalSettings,
+            Bucket currentBucket, ListIterator<Bucket> iterTargetBuckets) {
+        ScanSettings remainingSplitSettings = null;
+        boolean wasMerged = false;
+        Bucket maxScheduledBucket = currentBucket;
+
+        while (iterTargetBuckets.hasPrevious()) {
+            Bucket targetBucket = iterTargetBuckets.previous();
+            ChannelCollection targetBucketChannelCol = targetBucket.getChannelCollection();
+            if (targetBucketChannelCol.containsSettings(originalSettings)) {
+                targetBucket.addSettings(originalSettings);
+                // Update the max scheduled bucket for this setting
+                maxScheduledBucket = targetBucket;
+                wasMerged = true;
+            } else if (targetBucketChannelCol.partiallyContainsSettings(originalSettings)) {
+                Pair<ScanSettings, ScanSettings> splitSettings;
+                if (remainingSplitSettings == null) {
+                    splitSettings = createSplitSettings(originalSettings, targetBucketChannelCol);
+                } else {
+                    splitSettings =
+                            createSplitSettings(remainingSplitSettings, targetBucketChannelCol);
+                }
+                targetBucket.addSettings(splitSettings.second);
+                // Update the |remainingSplitSettings| to keep track of the remaining scan settings.
+                // The original settings could be split across multiple buckets.
+                remainingSplitSettings = splitSettings.first;
+                wasMerged = true;
+            }
+        }
+        // Update the settings to scheduled bucket mapping. This is needed for event
+        // reporting lookup
+        mSettingsToScheduledBucket.put(originalSettings, maxScheduledBucket);
+
+        return Pair.create(wasMerged, remainingSplitSettings);
+    }
+
+    /**
+     * Optimize all the active buckets by removing duplicate channels in the buckets.
+     * This method tries to go through the settings in all the buckets and checks if the same
+     * channels for the setting is already being scanned by another bucked with lower time period.
+     * If yes, move the setting to the lower time period bucket. If all the settings from a higher
+     * period has been moved out, that bucket can be removed.
+     *
+     * We're trying to avoid cases where we have the same channels being scanned in different
+     * buckets. This is to workaround the fact that the HAL implementations have a max number of
+     * cumulative channel across buckets (b/28022609).
+     */
+    private List<Bucket> optimizeBuckets() {
+        mSettingsToScheduledBucket.clear();
+        List<Bucket> sortedBuckets = mBuckets.getSortedActiveRegularBucketList();
+        ListIterator<Bucket> iterBuckets = sortedBuckets.listIterator();
+        // This is needed to keep track of split settings that need to be added back to the same
+        // bucket at the end of iterating thru all the settings. This has to be a separate temp list
+        // to prevent concurrent modification exceptions during iterations.
+        List<ScanSettings> currentBucketSplitSettingsList = new ArrayList<>();
+
+        // We need to go thru each setting starting from the lowest time period bucket and check
+        // if they're already contained in a lower time period bucket. If yes, delete the setting
+        // from the current bucket and move it to the other bucket. If the settings are only
+        // partially contained, split the settings into two and move the partial bucket back
+        // to the same bucket. Finally, if all the settings have been moved out, remove the current
+        // bucket altogether.
+        while (iterBuckets.hasNext()) {
+            Bucket currentBucket = iterBuckets.next();
+            Iterator<ScanSettings> iterSettings = currentBucket.getSettingsList().iterator();
+
+            currentBucketSplitSettingsList.clear();
+
+            while (iterSettings.hasNext()) {
+                ScanSettings currentSettings = iterSettings.next();
+                ListIterator<Bucket> iterTargetBuckets =
+                        sortedBuckets.listIterator(iterBuckets.previousIndex());
+
+                Pair<Boolean, ScanSettings> mergeResult =
+                        mergeSettingsToLowerBuckets(
+                                currentSettings, currentBucket, iterTargetBuckets);
+
+                boolean wasMerged = mergeResult.first.booleanValue();
+                if (wasMerged) {
+                    // Remove the original settings from the current bucket.
+                    iterSettings.remove();
+                    ScanSettings remainingSplitSettings = mergeResult.second;
+                    if (remainingSplitSettings != null) {
+                        // Add back the remaining split settings to the current bucket.
+                        currentBucketSplitSettingsList.add(remainingSplitSettings);
+                    }
+                }
+            }
+
+            for (ScanSettings splitSettings: currentBucketSplitSettingsList) {
+                currentBucket.addSettings(splitSettings);
+            }
+            if (currentBucket.getSettingsList().isEmpty()) {
+                iterBuckets.remove();
+            } else {
+                // Update the channel collection to account for the removed settings
+                currentBucket.updateChannelCollection();
+            }
+        }
+
+        // Update the settings to scheduled bucket map for all exponential scans.
+        if (mBuckets.isActive(EXPONENTIAL_BACK_OFF_BUCKET_IDX)) {
+            Bucket exponentialBucket = mBuckets.get(EXPONENTIAL_BACK_OFF_BUCKET_IDX);
+            for (ScanSettings settings : exponentialBucket.getSettingsList()) {
+                mSettingsToScheduledBucket.put(settings, exponentialBucket);
+            }
+            sortedBuckets.add(exponentialBucket);
+        }
+
+        return sortedBuckets;
+    }
+
+    /**
+     * Partition the channel set into 2 or more based on the max channels that can be specified for
+     * each bucket.
+     */
+    private List<Set<Integer>> partitionChannelSet(Set<Integer> originalChannelSet,
+            int maxChannelsPerBucket) {
+        ArrayList<Set<Integer>> channelSetList = new ArrayList();
+        ArraySet<Integer> channelSet = new ArraySet<>();
+        Iterator<Integer> iterChannels = originalChannelSet.iterator();
+
+        while (iterChannels.hasNext()) {
+            channelSet.add(iterChannels.next());
+            if (channelSet.size() == maxChannelsPerBucket) {
+                channelSetList.add(channelSet);
+                channelSet = new ArraySet<>();
+            }
+        }
+        // Add the last partial set if any
+        if (!channelSet.isEmpty()) {
+            channelSetList.add(channelSet);
+        }
+        return channelSetList;
+    }
+
+    /**
+     * Creates a list of split buckets with the channel collection corrected to fit the
+     * max channel list size that can be specified. The original channel collection will be split
+     * into multiple buckets with the same scan settings.
+     * Note: This does not update the mSettingsToScheduledBucket map because this bucket is
+     * essentially a copy of the original bucket, so it should not affect the event reporting.
+     * This bucket results will come back the same time the original bucket results come back.
+     */
+    private List<Bucket> createSplitBuckets(Bucket originalBucket, List<Set<Integer>> channelSets) {
+        List<Bucket> splitBucketList = new ArrayList<>();
+        int channelSetIdx = 0;
+
+        for (Set<Integer> channelSet : channelSets) {
+            Bucket splitBucket;
+            if (channelSetIdx == 0) {
+                // Need to keep the original bucket to keep track of the settings to scheduled
+                // bucket mapping.
+                splitBucket = originalBucket;
+            } else {
+                splitBucket = new Bucket(originalBucket);
+            }
+            ChannelCollection splitBucketChannelCollection = splitBucket.getChannelCollection();
+            splitBucketChannelCollection.clear();
+            for (Integer channel : channelSet) {
+                splitBucketChannelCollection.addChannel(channel);
+            }
+            channelSetIdx++;
+            splitBucketList.add(splitBucket);
+        }
+        return splitBucketList;
+    }
+
+    /**
+     * Check if any of the buckets don't fit into the bucket specification and fix it. This
+     * creates duplicate buckets to fit all the channels. So, the channels to be scanned
+     * will be split across 2 (or more) buckets.
+     * TODO: If we reach the max number of buckets, then this fix will be skipped!
+     */
+    private List<Bucket> fixBuckets(List<Bucket> originalBucketList, int maxBuckets,
+            int maxChannelsPerBucket) {
+        List<Bucket> fixedBucketList = new ArrayList<>();
+        int totalNumBuckets = originalBucketList.size();
+
+        for (Bucket originalBucket : originalBucketList) {
+            ChannelCollection channelCollection = originalBucket.getChannelCollection();
+            Set<Integer> channelSet = channelCollection.getChannelSet();
+            if (channelSet.size() > maxChannelsPerBucket) {
+                List<Set<Integer>> channelSetList =
+                        partitionChannelSet(channelSet, maxChannelsPerBucket);
+                int newTotalNumBuckets = totalNumBuckets + channelSetList.size() - 1;
+                if (newTotalNumBuckets <= maxBuckets) {
+                    List<Bucket> splitBuckets = createSplitBuckets(originalBucket, channelSetList);
+                    for (Bucket bucket : splitBuckets) {
+                        fixedBucketList.add(bucket);
+                    }
+                    totalNumBuckets = newTotalNumBuckets;
+                } else {
+                    fixedBucketList.add(originalBucket);
+                }
+            } else {
+                fixedBucketList.add(originalBucket);
+            }
+        }
+        return fixedBucketList;
+    }
 }
diff --git a/service/java/com/android/server/wifi/scanner/ChannelHelper.java b/service/java/com/android/server/wifi/scanner/ChannelHelper.java
index e6042c4b1..d4168123d 100644
--- a/service/java/com/android/server/wifi/scanner/ChannelHelper.java
+++ b/service/java/com/android/server/wifi/scanner/ChannelHelper.java
@@ -17,6 +17,7 @@
 package com.android.server.wifi.scanner;
 
 import android.net.wifi.WifiScanner;
+import android.util.ArraySet;
 
 import com.android.server.wifi.WifiNative;
 
@@ -87,6 +88,14 @@ public abstract class ChannelHelper {
          */
         public abstract boolean containsChannel(int channel);
         /**
+         * @return true if the collection contains all the channels of the supplied band
+         */
+        public abstract boolean containsBand(int band);
+        /**
+         * @return true if the collection contains some of the channels of the supplied band
+         */
+        public abstract boolean partiallyContainsBand(int band);
+        /**
          * @return true if the collection contains no channels
          */
         public abstract boolean isEmpty();
@@ -94,6 +103,19 @@ public abstract class ChannelHelper {
          * Remove all channels from the collection
          */
         public abstract void clear();
+        /**
+         * Retrieves a list of channels from the band which are missing in the channel collection.
+         */
+        public abstract Set<Integer> getMissingChannelsFromBand(int band);
+        /**
+         * Retrieves a list of channels from the band which are contained in the channel collection.
+         */
+        public abstract Set<Integer> getContainingChannelsFromBand(int band);
+        /**
+         * Gets a list of channels specified in the current channel collection. This will return
+         * an empty set if an entire Band if specified or if the list is empty.
+         */
+        public abstract Set<Integer> getChannelSet();
 
         /**
          * Add all channels in the ScanSetting to the collection
@@ -122,6 +144,73 @@ public abstract class ChannelHelper {
         }
 
         /**
+         * Checks if all channels in ScanSetting is in the collection
+         */
+        public boolean containsSettings(WifiScanner.ScanSettings scanSettings) {
+            if (scanSettings.band == WifiScanner.WIFI_BAND_UNSPECIFIED) {
+                for (int j = 0; j < scanSettings.channels.length; ++j) {
+                    if (!containsChannel(scanSettings.channels[j].frequency)) {
+                        return false;
+                    }
+                }
+                return true;
+            } else {
+                return containsBand(scanSettings.band);
+            }
+        }
+
+        /**
+         * Checks if at least some of the channels in ScanSetting is in the collection
+         */
+        public boolean partiallyContainsSettings(WifiScanner.ScanSettings scanSettings) {
+            if (scanSettings.band == WifiScanner.WIFI_BAND_UNSPECIFIED) {
+                for (int j = 0; j < scanSettings.channels.length; ++j) {
+                    if (containsChannel(scanSettings.channels[j].frequency)) {
+                        return true;
+                    }
+                }
+                return false;
+            } else {
+                return partiallyContainsBand(scanSettings.band);
+            }
+        }
+
+        /**
+         * Retrieves a list of missing channels in the collection from the provided settings.
+         */
+        public Set<Integer> getMissingChannelsFromSettings(WifiScanner.ScanSettings scanSettings) {
+            if (scanSettings.band == WifiScanner.WIFI_BAND_UNSPECIFIED) {
+                ArraySet<Integer> missingChannels = new ArraySet<>();
+                for (int j = 0; j < scanSettings.channels.length; ++j) {
+                    if (!containsChannel(scanSettings.channels[j].frequency)) {
+                        missingChannels.add(scanSettings.channels[j].frequency);
+                    }
+                }
+                return missingChannels;
+            } else {
+                return getMissingChannelsFromBand(scanSettings.band);
+            }
+        }
+
+        /**
+         * Retrieves a list of containing channels in the collection from the provided settings.
+         */
+        public Set<Integer> getContainingChannelsFromSettings(
+                WifiScanner.ScanSettings scanSettings) {
+            if (scanSettings.band == WifiScanner.WIFI_BAND_UNSPECIFIED) {
+                ArraySet<Integer> containingChannels = new ArraySet<>();
+                for (int j = 0; j < scanSettings.channels.length; ++j) {
+                    if (containsChannel(scanSettings.channels[j].frequency)) {
+                        containingChannels.add(scanSettings.channels[j].frequency);
+                    }
+                }
+                return containingChannels;
+            } else {
+                return getContainingChannelsFromBand(scanSettings.band);
+            }
+        }
+
+        /**
          * Store the channels in this collection in the supplied BucketSettings. If maxChannels is
          * exceeded or a band better describes the channels then a band is specified instead of a
          * channel list.
diff --git a/service/java/com/android/server/wifi/scanner/KnownBandsChannelHelper.java b/service/java/com/android/server/wifi/scanner/KnownBandsChannelHelper.java
index 3214cf2d1..b180da71d 100644
--- a/service/java/com/android/server/wifi/scanner/KnownBandsChannelHelper.java
+++ b/service/java/com/android/server/wifi/scanner/KnownBandsChannelHelper.java
@@ -171,6 +171,28 @@ public class KnownBandsChannelHelper extends ChannelHelper {
         }
 
         @Override
+        public boolean containsBand(int band) {
+            WifiScanner.ChannelSpec[] bandChannels = getAvailableScanChannels(band);
+            for (int i = 0; i < bandChannels.length; ++i) {
+                if (!mChannels.contains(bandChannels[i].frequency)) {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        @Override
+        public boolean partiallyContainsBand(int band) {
+            WifiScanner.ChannelSpec[] bandChannels = getAvailableScanChannels(band);
+            for (int i = 0; i < bandChannels.length; ++i) {
+                if (mChannels.contains(bandChannels[i].frequency)) {
+                    return true;
+                }
+            }
+            return false;
+        }
+
+        @Override
         public boolean isEmpty() {
             return mChannels.isEmpty();
         }
@@ -183,6 +205,39 @@ public class KnownBandsChannelHelper extends ChannelHelper {
         }
 
         @Override
+        public Set<Integer> getMissingChannelsFromBand(int band) {
+            ArraySet<Integer> missingChannels = new ArraySet<>();
+            WifiScanner.ChannelSpec[] bandChannels = getAvailableScanChannels(band);
+            for (int i = 0; i < bandChannels.length; ++i) {
+                if (!mChannels.contains(bandChannels[i].frequency)) {
+                    missingChannels.add(bandChannels[i].frequency);
+                }
+            }
+            return missingChannels;
+        }
+
+        @Override
+        public Set<Integer> getContainingChannelsFromBand(int band) {
+            ArraySet<Integer> containingChannels = new ArraySet<>();
+            WifiScanner.ChannelSpec[] bandChannels = getAvailableScanChannels(band);
+            for (int i = 0; i < bandChannels.length; ++i) {
+                if (mChannels.contains(bandChannels[i].frequency)) {
+                    containingChannels.add(bandChannels[i].frequency);
+                }
+            }
+            return containingChannels;
+        }
+
+        @Override
+        public Set<Integer> getChannelSet() {
+            if (!isEmpty() && mAllBands != mExactBands) {
+                return mChannels;
+            } else {
+                return new ArraySet<>();
+            }
+        }
+
+        @Override
         public void fillBucketSettings(WifiNative.BucketSettings bucketSettings, int maxChannels) {
             if ((mChannels.size() > maxChannels || mAllBands == mExactBands)
                     && mAllBands != 0) {
diff --git a/service/java/com/android/server/wifi/scanner/NoBandChannelHelper.java b/service/java/com/android/server/wifi/scanner/NoBandChannelHelper.java
index 4528a53a6..7b1602008 100644
--- a/service/java/com/android/server/wifi/scanner/NoBandChannelHelper.java
+++ b/service/java/com/android/server/wifi/scanner/NoBandChannelHelper.java
@@ -91,6 +91,22 @@ public class NoBandChannelHelper extends ChannelHelper {
         }
 
         @Override
+        public boolean containsBand(int band) {
+            if (band != WifiScanner.WIFI_BAND_UNSPECIFIED) {
+                return mAllChannels;
+            }
+            return false;
+        }
+
+        @Override
+        public boolean partiallyContainsBand(int band) {
+            // We don't need to partially collapse settings in supplicant scanner because we
+            // don't have any limitation on the number of channels that can be scanned. We also
+            // don't currently keep track of bands very well in NoBandChannelHelper.
+            return false;
+        }
+
+        @Override
         public boolean isEmpty() {
             return !mAllChannels && mChannels.isEmpty();
         }
@@ -102,6 +118,31 @@ public class NoBandChannelHelper extends ChannelHelper {
         }
 
         @Override
+        public Set<Integer> getMissingChannelsFromBand(int band) {
+            // We don't need to partially collapse settings in supplicant scanner because we
+            // don't have any limitation on the number of channels that can be scanned. We also
+            // don't currently keep track of bands very well in NoBandChannelHelper.
+            return new ArraySet<Integer>();
+        }
+
+        @Override
+        public Set<Integer> getContainingChannelsFromBand(int band) {
+            // We don't need to partially collapse settings in supplicant scanner because we
+            // don't have any limitation on the number of channels that can be scanned. We also
+            // don't currently keep track of bands very well in NoBandChannelHelper.
+            return new ArraySet<Integer>();
+        }
+
+        @Override
+        public Set<Integer> getChannelSet() {
+            if (!isEmpty() && !mAllChannels) {
+                return mChannels;
+            } else {
+                return new ArraySet<>();
+            }
+        }
+
+        @Override
         public void fillBucketSettings(WifiNative.BucketSettings bucketSettings, int maxChannels) {
             if (mAllChannels || mChannels.size() > maxChannels) {
                 bucketSettings.band = WifiScanner.WIFI_BAND_BOTH_WITH_DFS;