libeap/src/ap/acs.c

   1 /*
   2  * ACS - Automatic Channel Selection module
   3  * Copyright (c) 2011, Atheros Communications
   4  * Copyright (c) 2013, Qualcomm Atheros, Inc.
   5  *
   6  * This software may be distributed under the terms of the BSD license.
   7  * See README for more details.
   8  */
   9
  10 #include "utils/includes.h"
  11 #include <math.h>
  12
  13 #include "utils/common.h"
  14 #include "utils/list.h"
  15 #include "common/ieee802_11_defs.h"
  16 #include "common/wpa_ctrl.h"
  17 #include "drivers/driver.h"
  18 #include "hostapd.h"
  19 #include "ap_drv_ops.h"
  20 #include "ap_config.h"
  21 #include "hw_features.h"
  22 #include "acs.h"
  23
  24 /*
  25  * Automatic Channel Selection
  26  * ===========================
  27  *
  28  * More info at
  29  * ------------
  30  * http://wireless.kernel.org/en/users/Documentation/acs
  31  *
  32  * How to use
  33  * ----------
  34  * - make sure you have CONFIG_ACS=y in hostapd's .config
  35  * - use channel=0 or channel=acs to enable ACS
  36  *
  37  * How does it work
  38  * ----------------
  39  * 1. passive scans are used to collect survey data
  40  *    (it is assumed that scan trigger collection of survey data in driver)
  41  * 2. interference factor is calculated for each channel
  42  * 3. ideal channel is picked depending on channel width by using adjacent
  43  *    channel interference factors
  44  *
  45  * Known limitations
  46  * -----------------
  47  * - Current implementation depends heavily on the amount of time willing to
  48  *   spend gathering survey data during hostapd startup. Short traffic bursts
  49  *   may be missed and a suboptimal channel may be picked.
  50  * - Ideal channel may end up overlapping a channel with 40 MHz intolerant BSS
  51  *
  52  * Todo / Ideas
  53  * ------------
  54  * - implement other interference computation methods
  55  *   - BSS/RSSI based
  56  *   - spectral scan based
  57  *   (should be possibly to hook this up with current ACS scans)
  58  * - add wpa_supplicant support (for P2P)
  59  * - collect a histogram of interference over time allowing more educated
  60  *   guess about an ideal channel (perhaps CSA could be used to migrate AP to a
  61  *   new "better" channel while running)
  62  * - include neighboring BSS scan to avoid conflicts with 40 MHz intolerant BSSs
  63  *   when choosing the ideal channel
  64  *
  65  * Survey interference factor implementation details
  66  * -------------------------------------------------
  67  * Generic interference_factor in struct hostapd_channel_data is used.
  68  *
  69  * The survey interference factor is defined as the ratio of the
  70  * observed busy time over the time we spent on the channel,
  71  * this value is then amplified by the observed noise floor on
  72  * the channel in comparison to the lowest noise floor observed
  73  * on the entire band.
  74  *
  75  * This corresponds to:
  76  * ---
  77  * (busy time - tx time) / (active time - tx time) * 2^(chan_nf + band_min_nf)
  78  * ---
  79  *
  80  * The coefficient of 2 reflects the way power in "far-field"
  81  * radiation decreases as the square of distance from the antenna [1].
  82  * What this does is it decreases the observed busy time ratio if the
  83  * noise observed was low but increases it if the noise was high,
  84  * proportionally to the way "far field" radiation changes over
  85  * distance.
  86  *
  87  * If channel busy time is not available the fallback is to use channel RX time.
  88  *
  89  * Since noise floor is in dBm it is necessary to convert it into Watts so that
  90  * combined channel interference (e.g., HT40, which uses two channels) can be
  91  * calculated easily.
  92  * ---
  93  * (busy time - tx time) / (active time - tx time) *
  94  *    2^(10^(chan_nf/10) + 10^(band_min_nf/10))
  95  * ---
  96  *
  97  * However to account for cases where busy/rx time is 0 (channel load is then
  98  * 0%) channel noise floor signal power is combined into the equation so a
  99  * channel with lower noise floor is preferred. The equation becomes:
 100  * ---
 101  * 10^(chan_nf/5) + (busy time - tx time) / (active time - tx time) *
 102  *    2^(10^(chan_nf/10) + 10^(band_min_nf/10))
 103  * ---
 104  *
 105  * All this "interference factor" is purely subjective and only time
 106  * will tell how usable this is. By using the minimum noise floor we
 107  * remove any possible issues due to card calibration. The computation
 108  * of the interference factor then is dependent on what the card itself
 109  * picks up as the minimum noise, not an actual real possible card
 110  * noise value.
 111  *
 112  * Total interference computation details
 113  * --------------------------------------
 114  * The above channel interference factor is calculated with no respect to
 115  * target operational bandwidth.
 116  *
 117  * To find an ideal channel the above data is combined by taking into account
 118  * the target operational bandwidth and selected band. E.g., on 2.4 GHz channels
 119  * overlap with 20 MHz bandwidth, but there is no overlap for 20 MHz bandwidth
 120  * on 5 GHz.
 121  *
 122  * Each valid and possible channel spec (i.e., channel + width) is taken and its
 123  * interference factor is computed by summing up interferences of each channel
 124  * it overlaps. The one with least total interference is picked up.
 125  *
 126  * Note: This implies base channel interference factor must be non-negative
 127  * allowing easy summing up.
 128  *
 129  * Example ACS analysis printout
 130  * -----------------------------
 131  *
 132  * ACS: Trying survey-based ACS
 133  * ACS: Survey analysis for channel 1 (2412 MHz)
 134  * ACS:  1: min_nf=-113 interference_factor=0.0802469 nf=-113 time=162 busy=0 rx=13
 135  * ACS:  2: min_nf=-113 interference_factor=0.0745342 nf=-113 time=161 busy=0 rx=12
 136  * ACS:  3: min_nf=-113 interference_factor=0.0679012 nf=-113 time=162 busy=0 rx=11
 137  * ACS:  4: min_nf=-113 interference_factor=0.0310559 nf=-113 time=161 busy=0 rx=5
 138  * ACS:  5: min_nf=-113 interference_factor=0.0248447 nf=-113 time=161 busy=0 rx=4
 139  * ACS:  * interference factor average: 0.0557166
 140  * ACS: Survey analysis for channel 2 (2417 MHz)
 141  * ACS:  1: min_nf=-113 interference_factor=0.0185185 nf=-113 time=162 busy=0 rx=3
 142  * ACS:  2: min_nf=-113 interference_factor=0.0246914 nf=-113 time=162 busy=0 rx=4
 143  * ACS:  3: min_nf=-113 interference_factor=0.037037 nf=-113 time=162 busy=0 rx=6
 144  * ACS:  4: min_nf=-113 interference_factor=0.149068 nf=-113 time=161 busy=0 rx=24
 145  * ACS:  5: min_nf=-113 interference_factor=0.0248447 nf=-113 time=161 busy=0 rx=4
 146  * ACS:  * interference factor average: 0.050832
 147  * ACS: Survey analysis for channel 3 (2422 MHz)
 148  * ACS:  1: min_nf=-113 interference_factor=2.51189e-23 nf=-113 time=162 busy=0 rx=0
 149  * ACS:  2: min_nf=-113 interference_factor=0.0185185 nf=-113 time=162 busy=0 rx=3
 150  * ACS:  3: min_nf=-113 interference_factor=0.0186335 nf=-113 time=161 busy=0 rx=3
 151  * ACS:  4: min_nf=-113 interference_factor=0.0186335 nf=-113 time=161 busy=0 rx=3
 152  * ACS:  5: min_nf=-113 interference_factor=0.0186335 nf=-113 time=161 busy=0 rx=3
 153  * ACS:  * interference factor average: 0.0148838
 154  * ACS: Survey analysis for channel 4 (2427 MHz)
 155  * ACS:  1: min_nf=-114 interference_factor=1.58489e-23 nf=-114 time=162 busy=0 rx=0
 156  * ACS:  2: min_nf=-114 interference_factor=0.0555556 nf=-114 time=162 busy=0 rx=9
 157  * ACS:  3: min_nf=-114 interference_factor=1.58489e-23 nf=-114 time=161 busy=0 rx=0
 158  * ACS:  4: min_nf=-114 interference_factor=0.0186335 nf=-114 time=161 busy=0 rx=3
 159  * ACS:  5: min_nf=-114 interference_factor=0.00621118 nf=-114 time=161 busy=0 rx=1
 160  * ACS:  * interference factor average: 0.0160801
 161  * ACS: Survey analysis for channel 5 (2432 MHz)
 162  * ACS:  1: min_nf=-114 interference_factor=0.409938 nf=-113 time=161 busy=0 rx=66
 163  * ACS:  2: min_nf=-114 interference_factor=0.0432099 nf=-113 time=162 busy=0 rx=7
 164  * ACS:  3: min_nf=-114 interference_factor=0.0124224 nf=-113 time=161 busy=0 rx=2
 165  * ACS:  4: min_nf=-114 interference_factor=0.677019 nf=-113 time=161 busy=0 rx=109
 166  * ACS:  5: min_nf=-114 interference_factor=0.0186335 nf=-114 time=161 busy=0 rx=3
 167  * ACS:  * interference factor average: 0.232244
 168  * ACS: Survey analysis for channel 6 (2437 MHz)
 169  * ACS:  1: min_nf=-113 interference_factor=0.552795 nf=-113 time=161 busy=0 rx=89
 170  * ACS:  2: min_nf=-113 interference_factor=0.0807453 nf=-112 time=161 busy=0 rx=13
 171  * ACS:  3: min_nf=-113 interference_factor=0.0310559 nf=-113 time=161 busy=0 rx=5
 172  * ACS:  4: min_nf=-113 interference_factor=0.434783 nf=-112 time=161 busy=0 rx=70
 173  * ACS:  5: min_nf=-113 interference_factor=0.0621118 nf=-113 time=161 busy=0 rx=10
 174  * ACS:  * interference factor average: 0.232298
 175  * ACS: Survey analysis for channel 7 (2442 MHz)
 176  * ACS:  1: min_nf=-113 interference_factor=0.440994 nf=-112 time=161 busy=0 rx=71
 177  * ACS:  2: min_nf=-113 interference_factor=0.385093 nf=-113 time=161 busy=0 rx=62
 178  * ACS:  3: min_nf=-113 interference_factor=0.0372671 nf=-113 time=161 busy=0 rx=6
 179  * ACS:  4: min_nf=-113 interference_factor=0.0372671 nf=-113 time=161 busy=0 rx=6
 180  * ACS:  5: min_nf=-113 interference_factor=0.0745342 nf=-113 time=161 busy=0 rx=12
 181  * ACS:  * interference factor average: 0.195031
 182  * ACS: Survey analysis for channel 8 (2447 MHz)
 183  * ACS:  1: min_nf=-114 interference_factor=0.0496894 nf=-112 time=161 busy=0 rx=8
 184  * ACS:  2: min_nf=-114 interference_factor=0.0496894 nf=-114 time=161 busy=0 rx=8
 185  * ACS:  3: min_nf=-114 interference_factor=0.0372671 nf=-113 time=161 busy=0 rx=6
 186  * ACS:  4: min_nf=-114 interference_factor=0.12963 nf=-113 time=162 busy=0 rx=21
 187  * ACS:  5: min_nf=-114 interference_factor=0.166667 nf=-114 time=162 busy=0 rx=27
 188  * ACS:  * interference factor average: 0.0865885
 189  * ACS: Survey analysis for channel 9 (2452 MHz)
 190  * ACS:  1: min_nf=-114 interference_factor=0.0124224 nf=-114 time=161 busy=0 rx=2
 191  * ACS:  2: min_nf=-114 interference_factor=0.0310559 nf=-114 time=161 busy=0 rx=5
 192  * ACS:  3: min_nf=-114 interference_factor=1.58489e-23 nf=-114 time=161 busy=0 rx=0
 193  * ACS:  4: min_nf=-114 interference_factor=0.00617284 nf=-114 time=162 busy=0 rx=1
 194  * ACS:  5: min_nf=-114 interference_factor=1.58489e-23 nf=-114 time=162 busy=0 rx=0
 195  * ACS:  * interference factor average: 0.00993022
 196  * ACS: Survey analysis for channel 10 (2457 MHz)
 197  * ACS:  1: min_nf=-114 interference_factor=0.00621118 nf=-114 time=161 busy=0 rx=1
 198  * ACS:  2: min_nf=-114 interference_factor=0.00621118 nf=-114 time=161 busy=0 rx=1
 199  * ACS:  3: min_nf=-114 interference_factor=0.00621118 nf=-114 time=161 busy=0 rx=1
 200  * ACS:  4: min_nf=-114 interference_factor=0.0493827 nf=-114 time=162 busy=0 rx=8
 201  * ACS:  5: min_nf=-114 interference_factor=1.58489e-23 nf=-114 time=162 busy=0 rx=0
 202  * ACS:  * interference factor average: 0.0136033
 203  * ACS: Survey analysis for channel 11 (2462 MHz)
 204  * ACS:  1: min_nf=-114 interference_factor=1.58489e-23 nf=-114 time=161 busy=0 rx=0
 205  * ACS:  2: min_nf=-114 interference_factor=2.51189e-23 nf=-113 time=161 busy=0 rx=0
 206  * ACS:  3: min_nf=-114 interference_factor=2.51189e-23 nf=-113 time=161 busy=0 rx=0
 207  * ACS:  4: min_nf=-114 interference_factor=0.0432099 nf=-114 time=162 busy=0 rx=7
 208  * ACS:  5: min_nf=-114 interference_factor=0.0925926 nf=-114 time=162 busy=0 rx=15
 209  * ACS:  * interference factor average: 0.0271605
 210  * ACS: Survey analysis for channel 12 (2467 MHz)
 211  * ACS:  1: min_nf=-114 interference_factor=0.0621118 nf=-113 time=161 busy=0 rx=10
 212  * ACS:  2: min_nf=-114 interference_factor=0.00621118 nf=-114 time=161 busy=0 rx=1
 213  * ACS:  3: min_nf=-114 interference_factor=2.51189e-23 nf=-113 time=162 busy=0 rx=0
 214  * ACS:  4: min_nf=-114 interference_factor=2.51189e-23 nf=-113 time=162 busy=0 rx=0
 215  * ACS:  5: min_nf=-114 interference_factor=0.00617284 nf=-113 time=162 busy=0 rx=1
 216  * ACS:  * interference factor average: 0.0148992
 217  * ACS: Survey analysis for channel 13 (2472 MHz)
 218  * ACS:  1: min_nf=-114 interference_factor=0.0745342 nf=-114 time=161 busy=0 rx=12
 219  * ACS:  2: min_nf=-114 interference_factor=0.0555556 nf=-114 time=162 busy=0 rx=9
 220  * ACS:  3: min_nf=-114 interference_factor=1.58489e-23 nf=-114 time=162 busy=0 rx=0
 221  * ACS:  4: min_nf=-114 interference_factor=1.58489e-23 nf=-114 time=162 busy=0 rx=0
 222  * ACS:  5: min_nf=-114 interference_factor=1.58489e-23 nf=-114 time=162 busy=0 rx=0
 223  * ACS:  * interference factor average: 0.0260179
 224  * ACS: Survey analysis for selected bandwidth 20MHz
 225  * ACS:  * channel 1: total interference = 0.121432
 226  * ACS:  * channel 2: total interference = 0.137512
 227  * ACS:  * channel 3: total interference = 0.369757
 228  * ACS:  * channel 4: total interference = 0.546338
 229  * ACS:  * channel 5: total interference = 0.690538
 230  * ACS:  * channel 6: total interference = 0.762242
 231  * ACS:  * channel 7: total interference = 0.756092
 232  * ACS:  * channel 8: total interference = 0.537451
 233  * ACS:  * channel 9: total interference = 0.332313
 234  * ACS:  * channel 10: total interference = 0.152182
 235  * ACS:  * channel 11: total interference = 0.0916111
 236  * ACS:  * channel 12: total interference = 0.0816809
 237  * ACS:  * channel 13: total interference = 0.0680776
 238  * ACS: Ideal channel is 13 (2472 MHz) with total interference factor of 0.0680776
 239  *
 240  * [1] http://en.wikipedia.org/wiki/Near_and_far_field
 241  */
 242
 243
 244 static int acs_request_scan(struct hostapd_iface *iface);
 245 static int acs_survey_is_sufficient(struct freq_survey *survey);
 246
 247
 248 static void acs_clean_chan_surveys(struct hostapd_channel_data *chan)
 249 {
 250         struct freq_survey *survey, *tmp;
 251
 252         if (dl_list_empty(&chan->survey_list))
 253                 return;
 254
 255         dl_list_for_each_safe(survey, tmp, &chan->survey_list,
 256                               struct freq_survey, list) {
 257                 dl_list_del(&survey->list);
 258                 os_free(survey);
 259         }
 260 }
 261
 262
 263 static void acs_cleanup(struct hostapd_iface *iface)
 264 {
 265         int i;
 266         struct hostapd_channel_data *chan;
 267
 268         for (i = 0; i < iface->current_mode->num_channels; i++) {
 269                 chan = &iface->current_mode->channels[i];
 270
 271                 if (chan->flag & HOSTAPD_CHAN_SURVEY_LIST_INITIALIZED)
 272                         acs_clean_chan_surveys(chan);
 273
 274                 dl_list_init(&chan->survey_list);
 275                 chan->flag |= HOSTAPD_CHAN_SURVEY_LIST_INITIALIZED;
 276                 chan->min_nf = 0;
 277         }
 278
 279         iface->chans_surveyed = 0;
 280         iface->acs_num_completed_scans = 0;
 281 }
 282
 283
 284 static void acs_fail(struct hostapd_iface *iface)
 285 {
 286         wpa_printf(MSG_ERROR, "ACS: Failed to start");
 287         acs_cleanup(iface);
 288         hostapd_disable_iface(iface);
 289 }
 290
 291
 292 static long double
 293 acs_survey_interference_factor(struct freq_survey *survey, s8 min_nf)
 294 {
 295         long double factor, busy, total;
 296
 297         if (survey->filled & SURVEY_HAS_CHAN_TIME_BUSY)
 298                 busy = survey->channel_time_busy;
 299         else if (survey->filled & SURVEY_HAS_CHAN_TIME_RX)
 300                 busy = survey->channel_time_rx;
 301         else {
 302                 /* This shouldn't really happen as survey data is checked in
 303                  * acs_sanity_check() */
 304                 wpa_printf(MSG_ERROR, "ACS: Survey data missing");
 305                 return 0;
 306         }
 307
 308         total = survey->channel_time;
 309
 310         if (survey->filled & SURVEY_HAS_CHAN_TIME_TX) {
 311                 busy -= survey->channel_time_tx;
 312                 total -= survey->channel_time_tx;
 313         }
 314
 315         /* TODO: figure out the best multiplier for noise floor base */
 316         factor = pow(10, survey->nf / 5.0L) +
 317                 (busy / total) *
 318                 pow(2, pow(10, (long double) survey->nf / 10.0L) -
 319                     pow(10, (long double) min_nf / 10.0L));
 320
 321         return factor;
 322 }
 323
 324
 325 static void
 326 acs_survey_chan_interference_factor(struct hostapd_iface *iface,
 327                                     struct hostapd_channel_data *chan)
 328 {
 329         struct freq_survey *survey;
 330         unsigned int i = 0;
 331         long double int_factor = 0;
 332         unsigned count = 0;
 333
 334         if (dl_list_empty(&chan->survey_list))
 335                 return;
 336
 337         if (chan->flag & HOSTAPD_CHAN_DISABLED)
 338                 return;
 339
 340         chan->interference_factor = 0;
 341
 342         dl_list_for_each(survey, &chan->survey_list, struct freq_survey, list)
 343         {
 344                 i++;
 345
 346                 if (!acs_survey_is_sufficient(survey)) {
 347                         wpa_printf(MSG_DEBUG, "ACS: %d: insufficient data", i);
 348                         continue;
 349                 }
 350
 351                 count++;
 352                 int_factor = acs_survey_interference_factor(survey,
 353                                                             iface->lowest_nf);
 354                 chan->interference_factor += int_factor;
 355                 wpa_printf(MSG_DEBUG, "ACS: %d: min_nf=%d interference_factor=%Lg nf=%d time=%lu busy=%lu rx=%lu",
 356                            i, chan->min_nf, int_factor,
 357                            survey->nf, (unsigned long) survey->channel_time,
 358                            (unsigned long) survey->channel_time_busy,
 359                            (unsigned long) survey->channel_time_rx);
 360         }
 361
 362         if (!count)
 363                 return;
 364         chan->interference_factor /= count;
 365 }
 366
 367
 368 static int acs_usable_ht40_chan(struct hostapd_channel_data *chan)
 369 {
 370         const int allowed[] = { 36, 44, 52, 60, 100, 108, 116, 124, 132, 149,
 371                                 157, 184, 192 };
 372         unsigned int i;
 373
 374         for (i = 0; i < ARRAY_SIZE(allowed); i++)
 375                 if (chan->chan == allowed[i])
 376                         return 1;
 377
 378         return 0;
 379 }
 380
 381
 382 static int acs_usable_vht80_chan(struct hostapd_channel_data *chan)
 383 {
 384         const int allowed[] = { 36, 52, 100, 116, 132, 149 };
 385         unsigned int i;
 386
 387         for (i = 0; i < ARRAY_SIZE(allowed); i++)
 388                 if (chan->chan == allowed[i])
 389                         return 1;
 390
 391         return 0;
 392 }
 393
 394
 395 static int acs_survey_is_sufficient(struct freq_survey *survey)
 396 {
 397         if (!(survey->filled & SURVEY_HAS_NF)) {
 398                 wpa_printf(MSG_INFO, "ACS: Survey is missing noise floor");
 399                 return 0;
 400         }
 401
 402         if (!(survey->filled & SURVEY_HAS_CHAN_TIME)) {
 403                 wpa_printf(MSG_INFO, "ACS: Survey is missing channel time");
 404                 return 0;
 405         }
 406
 407         if (!(survey->filled & SURVEY_HAS_CHAN_TIME_BUSY) &&
 408             !(survey->filled & SURVEY_HAS_CHAN_TIME_RX)) {
 409                 wpa_printf(MSG_INFO,
 410                            "ACS: Survey is missing RX and busy time (at least one is required)");
 411                 return 0;
 412         }
 413
 414         return 1;
 415 }
 416
 417
 418 static int acs_survey_list_is_sufficient(struct hostapd_channel_data *chan)
 419 {
 420         struct freq_survey *survey;
 421         int ret = -1;
 422
 423         dl_list_for_each(survey, &chan->survey_list, struct freq_survey, list)
 424         {
 425                 if (acs_survey_is_sufficient(survey)) {
 426                         ret = 1;
 427                         break;
 428                 }
 429                 ret = 0;
 430         }
 431
 432         if (ret == -1)
 433                 ret = 1; /* no survey list entries */
 434
 435         if (!ret) {
 436                 wpa_printf(MSG_INFO,
 437                            "ACS: Channel %d has insufficient survey data",
 438                            chan->chan);
 439         }
 440
 441         return ret;
 442 }
 443
 444
 445 static int acs_surveys_are_sufficient(struct hostapd_iface *iface)
 446 {
 447         int i;
 448         struct hostapd_channel_data *chan;
 449         int valid = 0;
 450
 451         for (i = 0; i < iface->current_mode->num_channels; i++) {
 452                 chan = &iface->current_mode->channels[i];
 453                 if (chan->flag & HOSTAPD_CHAN_DISABLED)
 454                         continue;
 455
 456                 if (!acs_survey_list_is_sufficient(chan))
 457                         continue;
 458
 459                 valid++;
 460         }
 461
 462         /* We need at least survey data for one channel */
 463         return !!valid;
 464 }
 465
 466
 467 static int acs_usable_chan(struct hostapd_channel_data *chan)
 468 {
 469         if (dl_list_empty(&chan->survey_list))
 470                 return 0;
 471         if (chan->flag & HOSTAPD_CHAN_DISABLED)
 472                 return 0;
 473         if (!acs_survey_list_is_sufficient(chan))
 474                 return 0;
 475         return 1;
 476 }
 477
 478
 479 static int is_in_chanlist(struct hostapd_iface *iface,
 480                           struct hostapd_channel_data *chan)
 481 {
 482         if (!iface->conf->acs_ch_list.num)
 483                 return 1;
 484
 485         return freq_range_list_includes(&iface->conf->acs_ch_list, chan->chan);
 486 }
 487
 488
 489 static void acs_survey_all_chans_intereference_factor(
 490         struct hostapd_iface *iface)
 491 {
 492         int i;
 493         struct hostapd_channel_data *chan;
 494
 495         for (i = 0; i < iface->current_mode->num_channels; i++) {
 496                 chan = &iface->current_mode->channels[i];
 497
 498                 if (!acs_usable_chan(chan))
 499                         continue;
 500
 501                 if (!is_in_chanlist(iface, chan))
 502                         continue;
 503
 504                 wpa_printf(MSG_DEBUG, "ACS: Survey analysis for channel %d (%d MHz)",
 505                            chan->chan, chan->freq);
 506
 507                 acs_survey_chan_interference_factor(iface, chan);
 508
 509                 wpa_printf(MSG_DEBUG, "ACS:  * interference factor average: %Lg",
 510                            chan->interference_factor);
 511         }
 512 }
 513
 514
 515 static struct hostapd_channel_data *acs_find_chan(struct hostapd_iface *iface,
 516                                                   int freq)
 517 {
 518         struct hostapd_channel_data *chan;
 519         int i;
 520
 521         for (i = 0; i < iface->current_mode->num_channels; i++) {
 522                 chan = &iface->current_mode->channels[i];
 523
 524                 if (chan->flag & HOSTAPD_CHAN_DISABLED)
 525                         continue;
 526
 527                 if (chan->freq == freq)
 528                         return chan;
 529         }
 530
 531         return NULL;
 532 }
 533
 534
 535 static int is_24ghz_mode(enum hostapd_hw_mode mode)
 536 {
 537         return mode == HOSTAPD_MODE_IEEE80211B ||
 538                 mode == HOSTAPD_MODE_IEEE80211G;
 539 }
 540
 541
 542 static int is_common_24ghz_chan(int chan)
 543 {
 544         return chan == 1 || chan == 6 || chan == 11;
 545 }
 546
 547
 548 #ifndef ACS_ADJ_WEIGHT
 549 #define ACS_ADJ_WEIGHT 0.85
 550 #endif /* ACS_ADJ_WEIGHT */
 551
 552 #ifndef ACS_NEXT_ADJ_WEIGHT
 553 #define ACS_NEXT_ADJ_WEIGHT 0.55
 554 #endif /* ACS_NEXT_ADJ_WEIGHT */
 555
 556 #ifndef ACS_24GHZ_PREFER_1_6_11
 557 /*
 558  * Select commonly used channels 1, 6, 11 by default even if a neighboring
 559  * channel has a smaller interference factor as long as it is not better by more
 560  * than this multiplier.
 561  */
 562 #define ACS_24GHZ_PREFER_1_6_11 0.8
 563 #endif /* ACS_24GHZ_PREFER_1_6_11 */
 564
 565 /*
 566  * At this point it's assumed chan->interface_factor has been computed.
 567  * This function should be reusable regardless of interference computation
 568  * option (survey, BSS, spectral, ...). chan->interference factor must be
 569  * summable (i.e., must be always greater than zero).
 570  */
 571 static struct hostapd_channel_data *
 572 acs_find_ideal_chan(struct hostapd_iface *iface)
 573 {
 574         struct hostapd_channel_data *chan, *adj_chan, *ideal_chan = NULL,
 575                 *rand_chan = NULL;
 576         long double factor, ideal_factor = 0;
 577         int i, j;
 578         int n_chans = 1;
 579         unsigned int k;
 580
 581         /* TODO: HT40- support */
 582
 583         if (iface->conf->ieee80211n &&
 584             iface->conf->secondary_channel == -1) {
 585                 wpa_printf(MSG_ERROR, "ACS: HT40- is not supported yet. Please try HT40+");
 586                 return NULL;
 587         }
 588
 589         if (iface->conf->ieee80211n &&
 590             iface->conf->secondary_channel)
 591                 n_chans = 2;
 592
 593         if (iface->conf->ieee80211ac &&
 594             iface->conf->vht_oper_chwidth == 1)
 595                 n_chans = 4;
 596
 597         /* TODO: VHT80+80, VHT160. Update acs_adjust_vht_center_freq() too. */
 598
 599         wpa_printf(MSG_DEBUG, "ACS: Survey analysis for selected bandwidth %d MHz",
 600                    n_chans == 1 ? 20 :
 601                    n_chans == 2 ? 40 :
 602                    80);
 603
 604         for (i = 0; i < iface->current_mode->num_channels; i++) {
 605                 double total_weight;
 606                 struct acs_bias *bias, tmp_bias;
 607
 608                 chan = &iface->current_mode->channels[i];
 609
 610                 if (chan->flag & HOSTAPD_CHAN_DISABLED)
 611                         continue;
 612
 613                 if (!is_in_chanlist(iface, chan))
 614                         continue;
 615
 616                 /* HT40 on 5 GHz has a limited set of primary channels as per
 617                  * 11n Annex J */
 618                 if (iface->current_mode->mode == HOSTAPD_MODE_IEEE80211A &&
 619                     iface->conf->ieee80211n &&
 620                     iface->conf->secondary_channel &&
 621                     !acs_usable_ht40_chan(chan)) {
 622                         wpa_printf(MSG_DEBUG, "ACS: Channel %d: not allowed as primary channel for HT40",
 623                                    chan->chan);
 624                         continue;
 625                 }
 626
 627                 if (iface->current_mode->mode == HOSTAPD_MODE_IEEE80211A &&
 628                     iface->conf->ieee80211ac &&
 629                     iface->conf->vht_oper_chwidth == 1 &&
 630                     !acs_usable_vht80_chan(chan)) {
 631                         wpa_printf(MSG_DEBUG, "ACS: Channel %d: not allowed as primary channel for VHT80",
 632                                    chan->chan);
 633                         continue;
 634                 }
 635
 636                 factor = 0;
 637                 if (acs_usable_chan(chan))
 638                         factor = chan->interference_factor;
 639                 total_weight = 1;
 640
 641                 for (j = 1; j < n_chans; j++) {
 642                         adj_chan = acs_find_chan(iface, chan->freq + (j * 20));
 643                         if (!adj_chan)
 644                                 break;
 645
 646                         if (acs_usable_chan(adj_chan)) {
 647                                 factor += adj_chan->interference_factor;
 648                                 total_weight += 1;
 649                         }
 650                 }
 651
 652                 if (j != n_chans) {
 653                         wpa_printf(MSG_DEBUG, "ACS: Channel %d: not enough bandwidth",
 654                                    chan->chan);
 655                         continue;
 656                 }
 657
 658                 /* 2.4 GHz has overlapping 20 MHz channels. Include adjacent
 659                  * channel interference factor. */
 660                 if (is_24ghz_mode(iface->current_mode->mode)) {
 661                         for (j = 0; j < n_chans; j++) {
 662                                 adj_chan = acs_find_chan(iface, chan->freq +
 663                                                          (j * 20) - 5);
 664                                 if (adj_chan && acs_usable_chan(adj_chan)) {
 665                                         factor += ACS_ADJ_WEIGHT *
 666                                                 adj_chan->interference_factor;
 667                                         total_weight += ACS_ADJ_WEIGHT;
 668                                 }
 669
 670                                 adj_chan = acs_find_chan(iface, chan->freq +
 671                                                          (j * 20) - 10);
 672                                 if (adj_chan && acs_usable_chan(adj_chan)) {
 673                                         factor += ACS_NEXT_ADJ_WEIGHT *
 674                                                 adj_chan->interference_factor;
 675                                         total_weight += ACS_NEXT_ADJ_WEIGHT;
 676                                 }
 677
 678                                 adj_chan = acs_find_chan(iface, chan->freq +
 679                                                          (j * 20) + 5);
 680                                 if (adj_chan && acs_usable_chan(adj_chan)) {
 681                                         factor += ACS_ADJ_WEIGHT *
 682                                                 adj_chan->interference_factor;
 683                                         total_weight += ACS_ADJ_WEIGHT;
 684                                 }
 685
 686                                 adj_chan = acs_find_chan(iface, chan->freq +
 687                                                          (j * 20) + 10);
 688                                 if (adj_chan && acs_usable_chan(adj_chan)) {
 689                                         factor += ACS_NEXT_ADJ_WEIGHT *
 690                                                 adj_chan->interference_factor;
 691                                         total_weight += ACS_NEXT_ADJ_WEIGHT;
 692                                 }
 693                         }
 694                 }
 695
 696                 factor /= total_weight;
 697
 698                 bias = NULL;
 699                 if (iface->conf->acs_chan_bias) {
 700                         for (k = 0; k < iface->conf->num_acs_chan_bias; k++) {
 701                                 bias = &iface->conf->acs_chan_bias[k];
 702                                 if (bias->channel == chan->chan)
 703                                         break;
 704                                 bias = NULL;
 705                         }
 706                 } else if (is_24ghz_mode(iface->current_mode->mode) &&
 707                            is_common_24ghz_chan(chan->chan)) {
 708                         tmp_bias.channel = chan->chan;
 709                         tmp_bias.bias = ACS_24GHZ_PREFER_1_6_11;
 710                         bias = &tmp_bias;
 711                 }
 712
 713                 if (bias) {
 714                         factor *= bias->bias;
 715                         wpa_printf(MSG_DEBUG,
 716                                    "ACS:  * channel %d: total interference = %Lg (%f bias)",
 717                                    chan->chan, factor, bias->bias);
 718                 } else {
 719                         wpa_printf(MSG_DEBUG,
 720                                    "ACS:  * channel %d: total interference = %Lg",
 721                                    chan->chan, factor);
 722                 }
 723
 724                 if (acs_usable_chan(chan) &&
 725                     (!ideal_chan || factor < ideal_factor)) {
 726                         ideal_factor = factor;
 727                         ideal_chan = chan;
 728                 }
 729
 730                 /* This channel would at least be usable */
 731                 if (!rand_chan)
 732                         rand_chan = chan;
 733         }
 734
 735         if (ideal_chan) {
 736                 wpa_printf(MSG_DEBUG, "ACS: Ideal channel is %d (%d MHz) with total interference factor of %Lg",
 737                            ideal_chan->chan, ideal_chan->freq, ideal_factor);
 738                 return ideal_chan;
 739         }
 740
 741         return rand_chan;
 742 }
 743
 744
 745 static void acs_adjust_vht_center_freq(struct hostapd_iface *iface)
 746 {
 747         int offset;
 748
 749         wpa_printf(MSG_DEBUG, "ACS: Adjusting VHT center frequency");
 750
 751         switch (iface->conf->vht_oper_chwidth) {
 752         case VHT_CHANWIDTH_USE_HT:
 753                 offset = 2 * iface->conf->secondary_channel;
 754                 break;
 755         case VHT_CHANWIDTH_80MHZ:
 756                 offset = 6;
 757                 break;
 758         default:
 759                 /* TODO: How can this be calculated? Adjust
 760                  * acs_find_ideal_chan() */
 761                 wpa_printf(MSG_INFO, "ACS: Only VHT20/40/80 is supported now");
 762                 return;
 763         }
 764
 765         iface->conf->vht_oper_centr_freq_seg0_idx =
 766                 iface->conf->channel + offset;
 767 }
 768
 769
 770 static int acs_study_survey_based(struct hostapd_iface *iface)
 771 {
 772         wpa_printf(MSG_DEBUG, "ACS: Trying survey-based ACS");
 773
 774         if (!iface->chans_surveyed) {
 775                 wpa_printf(MSG_ERROR, "ACS: Unable to collect survey data");
 776                 return -1;
 777         }
 778
 779         if (!acs_surveys_are_sufficient(iface)) {
 780                 wpa_printf(MSG_ERROR, "ACS: Surveys have insufficient data");
 781                 return -1;
 782         }
 783
 784         acs_survey_all_chans_intereference_factor(iface);
 785         return 0;
 786 }
 787
 788
 789 static int acs_study_options(struct hostapd_iface *iface)
 790 {
 791         int err;
 792
 793         err = acs_study_survey_based(iface);
 794         if (err == 0)
 795                 return 0;
 796
 797         /* TODO: If no surveys are available/sufficient this is a good
 798          * place to fallback to BSS-based ACS */
 799
 800         return -1;
 801 }
 802
 803
 804 static void acs_study(struct hostapd_iface *iface)
 805 {
 806         struct hostapd_channel_data *ideal_chan;
 807         int err;
 808
 809         err = acs_study_options(iface);
 810         if (err < 0) {
 811                 wpa_printf(MSG_ERROR, "ACS: All study options have failed");
 812                 goto fail;
 813         }
 814
 815         ideal_chan = acs_find_ideal_chan(iface);
 816         if (!ideal_chan) {
 817                 wpa_printf(MSG_ERROR, "ACS: Failed to compute ideal channel");
 818                 err = -1;
 819                 goto fail;
 820         }
 821
 822         iface->conf->channel = ideal_chan->chan;
 823
 824         if (iface->conf->ieee80211ac)
 825                 acs_adjust_vht_center_freq(iface);
 826
 827         err = 0;
 828 fail:
 829         /*
 830          * hostapd_setup_interface_complete() will return -1 on failure,
 831          * 0 on success and 0 is HOSTAPD_CHAN_VALID :)
 832          */
 833         if (hostapd_acs_completed(iface, err) == HOSTAPD_CHAN_VALID) {
 834                 acs_cleanup(iface);
 835                 return;
 836         }
 837
 838         /* This can possibly happen if channel parameters (secondary
 839          * channel, center frequencies) are misconfigured */
 840         wpa_printf(MSG_ERROR, "ACS: Possibly channel configuration is invalid, please report this along with your config file.");
 841         acs_fail(iface);
 842 }
 843
 844
 845 static void acs_scan_complete(struct hostapd_iface *iface)
 846 {
 847         int err;
 848
 849         iface->scan_cb = NULL;
 850
 851         wpa_printf(MSG_DEBUG, "ACS: Using survey based algorithm (acs_num_scans=%d)",
 852                    iface->conf->acs_num_scans);
 853
 854         err = hostapd_drv_get_survey(iface->bss[0], 0);
 855         if (err) {
 856                 wpa_printf(MSG_ERROR, "ACS: Failed to get survey data");
 857                 goto fail;
 858         }
 859
 860         if (++iface->acs_num_completed_scans < iface->conf->acs_num_scans) {
 861                 err = acs_request_scan(iface);
 862                 if (err) {
 863                         wpa_printf(MSG_ERROR, "ACS: Failed to request scan");
 864                         goto fail;
 865                 }
 866
 867                 return;
 868         }
 869
 870         acs_study(iface);
 871         return;
 872 fail:
 873         hostapd_acs_completed(iface, 1);
 874         acs_fail(iface);
 875 }
 876
 877
 878 static int acs_request_scan(struct hostapd_iface *iface)
 879 {
 880         struct wpa_driver_scan_params params;
 881         struct hostapd_channel_data *chan;
 882         int i, *freq;
 883
 884         os_memset(&params, 0, sizeof(params));
 885         params.freqs = os_calloc(iface->current_mode->num_channels + 1,
 886                                  sizeof(params.freqs[0]));
 887         if (params.freqs == NULL)
 888                 return -1;
 889
 890         freq = params.freqs;
 891         for (i = 0; i < iface->current_mode->num_channels; i++) {
 892                 chan = &iface->current_mode->channels[i];
 893                 if (chan->flag & HOSTAPD_CHAN_DISABLED)
 894                         continue;
 895
 896                 if (!is_in_chanlist(iface, chan))
 897                         continue;
 898
 899                 *freq++ = chan->freq;
 900         }
 901         *freq = 0;
 902
 903         iface->scan_cb = acs_scan_complete;
 904
 905         wpa_printf(MSG_DEBUG, "ACS: Scanning %d / %d",
 906                    iface->acs_num_completed_scans + 1,
 907                    iface->conf->acs_num_scans);
 908
 909         if (hostapd_driver_scan(iface->bss[0], &params) < 0) {
 910                 wpa_printf(MSG_ERROR, "ACS: Failed to request initial scan");
 911                 acs_cleanup(iface);
 912                 os_free(params.freqs);
 913                 return -1;
 914         }
 915
 916         os_free(params.freqs);
 917         return 0;
 918 }
 919
 920
 921 enum hostapd_chan_status acs_init(struct hostapd_iface *iface)
 922 {
 923         int err;
 924
 925         wpa_printf(MSG_INFO, "ACS: Automatic channel selection started, this may take a bit");
 926
 927         if (iface->drv_flags & WPA_DRIVER_FLAGS_ACS_OFFLOAD) {
 928                 wpa_printf(MSG_INFO, "ACS: Offloading to driver");
 929                 err = hostapd_drv_do_acs(iface->bss[0]);
 930                 if (err)
 931                         return HOSTAPD_CHAN_INVALID;
 932                 return HOSTAPD_CHAN_ACS;
 933         }
 934
 935         if (!iface->current_mode)
 936                 return HOSTAPD_CHAN_INVALID;
 937
 938         acs_cleanup(iface);
 939
 940         err = acs_request_scan(iface);
 941         if (err < 0)
 942                 return HOSTAPD_CHAN_INVALID;
 943
 944         hostapd_set_state(iface, HAPD_IFACE_ACS);
 945         wpa_msg(iface->bss[0]->msg_ctx, MSG_INFO, ACS_EVENT_STARTED);
 946
 947         return HOSTAPD_CHAN_ACS;
 948 }