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