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