| /* |
| * Copyright (C) 2015 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.android.server.wifi.scanner; |
| |
| import android.annotation.NonNull; |
| import android.annotation.Nullable; |
| 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; |
| |
| import com.android.server.wifi.WifiNative; |
| import com.android.server.wifi.scanner.ChannelHelper.ChannelCollection; |
| |
| 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 |
| * schedule it can to try and satisfy requests. The hardware level accepts a series of buckets, |
| * where each bucket represents a set of channels and an interval to scan at. This |
| * scheduler operates as follows:</p> |
| * |
| * <p>Each new request is placed in the best predefined bucket. Once all requests have been added |
| * the last buckets (lower priority) are placed in the next best bucket until the number of buckets |
| * is less than the number supported by the hardware. |
| * |
| * <p>Finally, the scheduler creates a WifiNative.ScanSettings from the list of buckets which may be |
| * passed through the Wifi HAL.</p> |
| * |
| * <p>This class is not thread safe.</p> |
| */ |
| public class BackgroundScanScheduler { |
| |
| private static final String TAG = "BackgroundScanScheduler"; |
| private static final boolean DBG = false; |
| |
| public static final int DEFAULT_MAX_BUCKETS = 8; |
| // 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; |
| public static final int DEFAULT_MAX_AP_PER_SCAN = 32; |
| |
| /** |
| * Value that all scan periods must be an integer multiple of |
| */ |
| private static final int PERIOD_MIN_GCD_MS = 10000; |
| /** |
| * Default period to use if no buckets are being scheduled |
| */ |
| private static final int DEFAULT_PERIOD_MS = 30000; |
| /** |
| * Scan report threshold percentage to assign to the schedule by default |
| * @see com.android.server.wifi.WifiNative.ScanSettings#report_threshold_percent |
| */ |
| private static final int DEFAULT_REPORT_THRESHOLD_PERCENTAGE = 100; |
| |
| /** |
| * List of predefined periods (in ms) that buckets can be scheduled at. Ordered by preference |
| * if there are not enough buckets for all periods. All periods MUST be an integer multiple of |
| * the next smallest bucket with the smallest bucket having a period of PERIOD_MIN_GCD_MS. |
| * This requirement allows scans to be scheduled more efficiently because scan requests with |
| * intersecting channels will result in those channels being scanned exactly once at the smaller |
| * period and no unnecessary scan being scheduled. If this was not the case and two requests |
| * had channel 5 with periods of 15 seconds and 25 seconds then channel 5 would be scanned |
| * 296 (3600/15 + 3600/25 - 3500/75) times an hour instead of 240 times an hour (3600/15) if |
| * the 25s scan is rescheduled at 30s. This is less important with higher periods as it has |
| * significantly less impact. Ranking could be done by favoring shorter or longer; however, |
| * this would result in straying further from the requested period and possibly power |
| * implications if the scan is scheduled at a significantly lower period. |
| * |
| * For example if the hardware only supports 2 buckets and scans are requested with periods of |
| * 40s, 20s and 10s then the two buckets scheduled will have periods 40s and 20s and the 10s |
| * scan will be placed in the 20s bucket. |
| * |
| * If there are special scan requests such as exponential back off, we always dedicate a bucket |
| * for each type. Regular scan requests will be packed into the remaining buckets. |
| */ |
| private static final int[] PREDEFINED_BUCKET_PERIODS = { |
| 3 * PERIOD_MIN_GCD_MS, // 30s |
| 12 * PERIOD_MIN_GCD_MS, // 120s |
| 48 * PERIOD_MIN_GCD_MS, // 480s |
| 1 * PERIOD_MIN_GCD_MS, // 10s |
| 6 * PERIOD_MIN_GCD_MS, // 60s |
| 192 * PERIOD_MIN_GCD_MS, // 1920s |
| 24 * PERIOD_MIN_GCD_MS, // 240s |
| 96 * PERIOD_MIN_GCD_MS, // 960s |
| 384 * PERIOD_MIN_GCD_MS, // 3840s |
| -1, // place holder for exponential back off scan |
| }; |
| |
| private static final int EXPONENTIAL_BACK_OFF_BUCKET_IDX = |
| (PREDEFINED_BUCKET_PERIODS.length - 1); |
| private static final int NUM_OF_REGULAR_BUCKETS = |
| (PREDEFINED_BUCKET_PERIODS.length - 1); |
| |
| /** |
| * 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 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); |
| } |
| } |
| |
| /** |
| * convert ChannelSpec to native representation |
| */ |
| private WifiNative.ChannelSettings createChannelSettings(int frequency) { |
| WifiNative.ChannelSettings channelSettings = new WifiNative.ChannelSettings(); |
| channelSettings.frequency = frequency; |
| 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) { |
| this.bucketId = bucketId; |
| int reportEvents = WifiScanner.REPORT_EVENT_NO_BATCH; |
| int maxPeriodInMs = 0; |
| int stepCount = 0; |
| int bucketIndex = 0; |
| |
| 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; |
| } |
| if ((requestedReportEvents & WifiScanner.REPORT_EVENT_AFTER_EACH_SCAN) != 0) { |
| reportEvents |= WifiScanner.REPORT_EVENT_AFTER_EACH_SCAN; |
| } |
| if ((requestedReportEvents & WifiScanner.REPORT_EVENT_FULL_SCAN_RESULT) != 0) { |
| reportEvents |= WifiScanner.REPORT_EVENT_FULL_SCAN_RESULT; |
| } |
| // 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. |
| // |
| if (i == 0 && setting.maxPeriodInMs != 0 |
| && setting.maxPeriodInMs != setting.periodInMs) { |
| // Align the starting period with one of the pre-defined regular |
| // scan periods. This will optimize the scan schedule when it has |
| // both exponential back off scan and regular scan(s). |
| bucketIndex = findBestRegularBucketIndex(setting.periodInMs, |
| NUM_OF_REGULAR_BUCKETS); |
| period = PREDEFINED_BUCKET_PERIODS[bucketIndex]; |
| maxPeriodInMs = (setting.maxPeriodInMs < period) |
| ? period |
| : setting.maxPeriodInMs; |
| stepCount = setting.stepCount; |
| } |
| } |
| |
| WifiNative.BucketSettings bucketSettings = new WifiNative.BucketSettings(); |
| bucketSettings.bucket = bucketId; |
| bucketSettings.report_events = reportEvents; |
| bucketSettings.period_ms = period; |
| bucketSettings.max_period_ms = maxPeriodInMs; |
| bucketSettings.step_count = stepCount; |
| mChannelCollection.fillBucketSettings(bucketSettings, maxChannels); |
| return bucketSettings; |
| } |
| } |
| |
| /** |
| * 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; |
| |
| BucketList() { |
| mBuckets = new Bucket[PREDEFINED_BUCKET_PERIODS.length]; |
| } |
| |
| public void clearAll() { |
| Arrays.fill(mBuckets, null); |
| mActiveBucketCount = 0; |
| } |
| |
| public void clear(int index) { |
| if (mBuckets[index] != null) { |
| --mActiveBucketCount; |
| mBuckets[index] = null; |
| } |
| } |
| |
| public Bucket getOrCreate(int index) { |
| Bucket bucket = mBuckets[index]; |
| if (bucket == null) { |
| ++mActiveBucketCount; |
| bucket = mBuckets[index] = new Bucket(PREDEFINED_BUCKET_PERIODS[index]); |
| } |
| return bucket; |
| } |
| |
| public boolean isActive(int index) { |
| return mBuckets[index] != null; |
| } |
| |
| public Bucket get(int index) { |
| return mBuckets[index]; |
| } |
| |
| public int size() { |
| return mBuckets.length; |
| } |
| |
| public int getActiveCount() { |
| return mActiveBucketCount; |
| } |
| |
| public int getActiveRegularBucketCount() { |
| if (isActive(EXPONENTIAL_BACK_OFF_BUCKET_IDX)) { |
| return mActiveBucketCount - 1; |
| } else { |
| 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 mMaxChannelsPerBucket = DEFAULT_MAX_CHANNELS_PER_BUCKET; |
| private int mMaxBatch = DEFAULT_MAX_SCANS_TO_BATCH; |
| private int mMaxApPerScan = DEFAULT_MAX_AP_PER_SCAN; |
| |
| public int getMaxBuckets() { |
| return mMaxBuckets; |
| } |
| |
| public void setMaxBuckets(int maxBuckets) { |
| mMaxBuckets = maxBuckets; |
| } |
| |
| public int getMaxChannelsPerBucket() { |
| return mMaxChannelsPerBucket; |
| } |
| |
| // TODO: find a way to get max channels |
| public void setMaxChannelsPerBucket(int maxChannels) { |
| mMaxChannelsPerBucket = maxChannels; |
| } |
| |
| public int getMaxBatch() { |
| return mMaxBatch; |
| } |
| |
| // TODO: find a way to get max batch size |
| public void setMaxBatch(int maxBatch) { |
| mMaxBatch = maxBatch; |
| } |
| |
| public int getMaxApPerScan() { |
| return mMaxApPerScan; |
| } |
| |
| public void setMaxApPerScan(int maxApPerScan) { |
| mMaxApPerScan = maxApPerScan; |
| } |
| |
| private final BucketList mBuckets = new BucketList(); |
| private final ChannelHelper mChannelHelper; |
| private WifiNative.ScanSettings mSchedule; |
| // 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; |
| createSchedule(new ArrayList<Bucket>(), getMaxChannelsPerBucket()); |
| } |
| |
| /** |
| * Updates the schedule from the given set of requests. |
| */ |
| public void updateSchedule(@NonNull Collection<ScanSettings> requests) { |
| // create initial schedule |
| mBuckets.clearAll(); |
| for (ScanSettings request : requests) { |
| addScanToBuckets(request); |
| } |
| |
| compactBuckets(getMaxBuckets()); |
| |
| List<Bucket> bucketList = optimizeBuckets(); |
| |
| List<Bucket> fixedBucketList = |
| fixBuckets(bucketList, getMaxBuckets(), getMaxChannelsPerBucket()); |
| |
| createSchedule(fixedBucketList, getMaxChannelsPerBucket()); |
| } |
| |
| /** |
| * Retrieves the current scanning schedule. |
| */ |
| public @NonNull WifiNative.ScanSettings getSchedule() { |
| return mSchedule; |
| } |
| |
| /** |
| * Returns true if the given scan result should be reported to a listener with the given |
| * settings. |
| */ |
| public boolean shouldReportFullScanResultForSettings(@NonNull ScanResult result, |
| int bucketsScanned, @NonNull ScanSettings settings) { |
| return ScanScheduleUtil.shouldReportFullScanResultForSettings(mChannelHelper, |
| result, bucketsScanned, settings, getScheduledBucket(settings)); |
| } |
| |
| /** |
| * Returns a filtered version of the scan results from the chip that represents only the data |
| * requested in the settings. Will return null if the result should not be reported. |
| */ |
| public @Nullable ScanData[] filterResultsForSettings(@NonNull ScanData[] scanDatas, |
| @NonNull ScanSettings settings) { |
| return ScanScheduleUtil.filterResultsForSettings(mChannelHelper, scanDatas, settings, |
| getScheduledBucket(settings)); |
| } |
| |
| /** |
| * 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; |
| } |
| } |
| |
| /** |
| * creates a schedule for the current buckets |
| */ |
| private void createSchedule(List<Bucket> bucketList, int maxChannelsPerBucket) { |
| WifiNative.ScanSettings schedule = new WifiNative.ScanSettings(); |
| schedule.num_buckets = bucketList.size(); |
| schedule.buckets = new WifiNative.BucketSettings[bucketList.size()]; |
| |
| schedule.max_ap_per_scan = 0; |
| schedule.report_threshold_num_scans = getMaxBatch(); |
| HashSet<Integer> hiddenNetworkIdSet = new HashSet<>(); |
| |
| // set all buckets in schedule |
| int bucketId = 0; |
| 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++; |
| } |
| |
| schedule.report_threshold_percent = DEFAULT_REPORT_THRESHOLD_PERCENTAGE; |
| |
| if (schedule.max_ap_per_scan == 0 || schedule.max_ap_per_scan > getMaxApPerScan()) { |
| schedule.max_ap_per_scan = getMaxApPerScan(); |
| } |
| if (hiddenNetworkIdSet.size() > 0) { |
| schedule.hiddenNetworkIds = new int[hiddenNetworkIdSet.size()]; |
| int numHiddenNetworks = 0; |
| for (Integer hiddenNetworkId : hiddenNetworkIdSet) { |
| schedule.hiddenNetworkIds[numHiddenNetworks++] = hiddenNetworkId; |
| } |
| } |
| |
| // update base period as gcd of periods |
| if (schedule.num_buckets > 0) { |
| int gcd = schedule.buckets[0].period_ms; |
| for (int b = 1; b < schedule.num_buckets; b++) { |
| gcd = Rational.gcd(schedule.buckets[b].period_ms, gcd); |
| } |
| |
| if (gcd < PERIOD_MIN_GCD_MS) { |
| Slog.wtf(TAG, "found gcd less than min gcd"); |
| gcd = PERIOD_MIN_GCD_MS; |
| } |
| |
| schedule.base_period_ms = gcd; |
| } else { |
| schedule.base_period_ms = DEFAULT_PERIOD_MS; |
| } |
| |
| mSchedule = schedule; |
| } |
| |
| /** |
| * Add a scan to the most appropriate bucket, creating the bucket if necessary. |
| */ |
| private void addScanToBuckets(ScanSettings settings) { |
| int bucketIndex; |
| |
| 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); |
| } |
| |
| mBuckets.getOrCreate(bucketIndex).addSettings(settings); |
| } |
| |
| /** |
| * find closest bucket period to the requested period in all predefined buckets |
| */ |
| private static int findBestRegularBucketIndex(int requestedPeriod, int maxNumBuckets) { |
| maxNumBuckets = Math.min(maxNumBuckets, NUM_OF_REGULAR_BUCKETS); |
| int index = -1; |
| int minDiff = Integer.MAX_VALUE; |
| for (int i = 0; i < maxNumBuckets; ++i) { |
| int diff = Math.abs(PREDEFINED_BUCKET_PERIODS[i] - requestedPeriod); |
| if (diff < minDiff) { |
| minDiff = diff; |
| index = i; |
| } |
| } |
| if (index == -1) { |
| Slog.wtf(TAG, "Could not find best bucket for period " + requestedPeriod + " in " |
| + maxNumBuckets + " buckets"); |
| } |
| return index; |
| } |
| |
| /** |
| * Reduce the number of required buckets by reassigning lower priority buckets to the next |
| * closest period bucket. |
| */ |
| private void compactBuckets(int maxBuckets) { |
| int maxRegularBuckets = maxBuckets; |
| |
| // reserve one bucket for exponential back off scan if there is |
| // such request(s) |
| if (mBuckets.isActive(EXPONENTIAL_BACK_OFF_BUCKET_IDX)) { |
| maxRegularBuckets--; |
| } |
| for (int i = NUM_OF_REGULAR_BUCKETS - 1; |
| i >= 0 && mBuckets.getActiveRegularBucketCount() > maxRegularBuckets; --i) { |
| if (mBuckets.isActive(i)) { |
| for (ScanSettings scanRequest : mBuckets.get(i).getSettingsList()) { |
| int newBucketIndex = findBestRegularBucketIndex(scanRequest.periodInMs, i); |
| 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; |
| } |
| } |
