/*
|
* 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.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();
|
|
// 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;
|
}
|
}
|
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();
|
}
|
|
// 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.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;
|
}
|
}
|
