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
acs_clean_chan_surveys(struct hostapd_channel_data * chan)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
acs_cleanup_mode(struct hostapd_hw_modes * mode)264 static void acs_cleanup_mode(struct hostapd_hw_modes *mode)
265 {
266 int i;
267 struct hostapd_channel_data *chan;
268
269 for (i = 0; i < mode->num_channels; i++) {
270 chan = &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
281
acs_cleanup(struct hostapd_iface * iface)282 void acs_cleanup(struct hostapd_iface *iface)
283 {
284 int i;
285
286 for (i = 0; i < iface->num_hw_features; i++)
287 acs_cleanup_mode(&iface->hw_features[i]);
288
289 iface->chans_surveyed = 0;
290 iface->acs_num_completed_scans = 0;
291 }
292
293
acs_fail(struct hostapd_iface * iface)294 static void acs_fail(struct hostapd_iface *iface)
295 {
296 wpa_printf(MSG_ERROR, "ACS: Failed to start");
297 acs_cleanup(iface);
298 hostapd_disable_iface(iface);
299 }
300
301
302 static long double
acs_survey_interference_factor(struct freq_survey * survey,s8 min_nf)303 acs_survey_interference_factor(struct freq_survey *survey, s8 min_nf)
304 {
305 long double factor, busy, total;
306
307 if (survey->filled & SURVEY_HAS_CHAN_TIME_BUSY)
308 busy = survey->channel_time_busy;
309 else if (survey->filled & SURVEY_HAS_CHAN_TIME_RX)
310 busy = survey->channel_time_rx;
311 else {
312 wpa_printf(MSG_ERROR, "ACS: Survey data missing");
313 return 0;
314 }
315
316 total = survey->channel_time;
317
318 if (survey->filled & SURVEY_HAS_CHAN_TIME_TX) {
319 busy -= survey->channel_time_tx;
320 total -= survey->channel_time_tx;
321 }
322
323 /* TODO: figure out the best multiplier for noise floor base */
324 factor = pow(10, survey->nf / 5.0L) +
325 (total ? (busy / total) : 0) *
326 pow(2, pow(10, (long double) survey->nf / 10.0L) -
327 pow(10, (long double) min_nf / 10.0L));
328
329 return factor;
330 }
331
332
333 static void
acs_survey_chan_interference_factor(struct hostapd_iface * iface,struct hostapd_channel_data * chan)334 acs_survey_chan_interference_factor(struct hostapd_iface *iface,
335 struct hostapd_channel_data *chan)
336 {
337 struct freq_survey *survey;
338 unsigned int i = 0;
339 long double int_factor = 0;
340 unsigned count = 0;
341
342 if (dl_list_empty(&chan->survey_list) ||
343 (chan->flag & HOSTAPD_CHAN_DISABLED))
344 return;
345
346 chan->interference_factor = 0;
347
348 dl_list_for_each(survey, &chan->survey_list, struct freq_survey, list)
349 {
350 i++;
351
352 if (!acs_survey_is_sufficient(survey)) {
353 wpa_printf(MSG_DEBUG, "ACS: %d: insufficient data", i);
354 continue;
355 }
356
357 count++;
358 int_factor = acs_survey_interference_factor(survey,
359 iface->lowest_nf);
360 chan->interference_factor += int_factor;
361 wpa_printf(MSG_DEBUG, "ACS: %d: min_nf=%d interference_factor=%Lg nf=%d time=%lu busy=%lu rx=%lu",
362 i, chan->min_nf, int_factor,
363 survey->nf, (unsigned long) survey->channel_time,
364 (unsigned long) survey->channel_time_busy,
365 (unsigned long) survey->channel_time_rx);
366 }
367
368 if (count)
369 chan->interference_factor /= count;
370 }
371
372
acs_usable_bw40_chan(const struct hostapd_channel_data * chan)373 static int acs_usable_bw40_chan(const struct hostapd_channel_data *chan)
374 {
375 const int allowed[] = { 5180, 5220, 5260, 5300, 5500, 5540, 5580, 5620,
376 5660, 5745, 5785, 4920, 4960, 5955, 5995, 6035,
377 6075, 6115, 6155, 6195, 6235, 6275, 6315, 6355,
378 6395, 6435, 6475, 6515, 6555, 6595, 6635, 6675,
379 6715, 6755, 6795, 6835, 6875, 6915, 6955, 6995,
380 7035, 7075 };
381 unsigned int i;
382
383 for (i = 0; i < ARRAY_SIZE(allowed); i++)
384 if (chan->freq == allowed[i])
385 return 1;
386
387 return 0;
388 }
389
390
acs_usable_bw80_chan(const struct hostapd_channel_data * chan)391 static int acs_usable_bw80_chan(const struct hostapd_channel_data *chan)
392 {
393 const int allowed[] = { 5180, 5260, 5500, 5580, 5660, 5745, 5955, 6035,
394 6115, 6195, 6275, 6355, 6435, 6515, 6595, 6675,
395 6755, 6835, 6915, 6995 };
396 unsigned int i;
397
398 for (i = 0; i < ARRAY_SIZE(allowed); i++)
399 if (chan->freq == allowed[i])
400 return 1;
401
402 return 0;
403 }
404
405
acs_usable_bw160_chan(const struct hostapd_channel_data * chan)406 static int acs_usable_bw160_chan(const struct hostapd_channel_data *chan)
407 {
408 const int allowed[] = { 5180, 5500, 5955, 6115, 6275, 6435, 6595, 6755,
409 6915 };
410 unsigned int i;
411
412 for (i = 0; i < ARRAY_SIZE(allowed); i++)
413 if (chan->freq == allowed[i])
414 return 1;
415
416 return 0;
417 }
418
419
acs_survey_is_sufficient(struct freq_survey * survey)420 static int acs_survey_is_sufficient(struct freq_survey *survey)
421 {
422 if (!(survey->filled & SURVEY_HAS_NF)) {
423 wpa_printf(MSG_INFO, "ACS: Survey is missing noise floor");
424 return 0;
425 }
426
427 if (!(survey->filled & SURVEY_HAS_CHAN_TIME)) {
428 wpa_printf(MSG_INFO, "ACS: Survey is missing channel time");
429 return 0;
430 }
431
432 if (!(survey->filled & SURVEY_HAS_CHAN_TIME_BUSY) &&
433 !(survey->filled & SURVEY_HAS_CHAN_TIME_RX)) {
434 wpa_printf(MSG_INFO,
435 "ACS: Survey is missing RX and busy time (at least one is required)");
436 return 0;
437 }
438
439 return 1;
440 }
441
442
acs_survey_list_is_sufficient(struct hostapd_channel_data * chan)443 static int acs_survey_list_is_sufficient(struct hostapd_channel_data *chan)
444 {
445 struct freq_survey *survey;
446 int ret = -1;
447
448 dl_list_for_each(survey, &chan->survey_list, struct freq_survey, list)
449 {
450 if (acs_survey_is_sufficient(survey)) {
451 ret = 1;
452 break;
453 }
454 ret = 0;
455 }
456
457 if (ret == -1)
458 ret = 1; /* no survey list entries */
459
460 if (!ret) {
461 wpa_printf(MSG_INFO,
462 "ACS: Channel %d has insufficient survey data",
463 chan->chan);
464 }
465
466 return ret;
467 }
468
469
acs_surveys_are_sufficient_mode(struct hostapd_hw_modes * mode)470 static int acs_surveys_are_sufficient_mode(struct hostapd_hw_modes *mode)
471 {
472 int i;
473 struct hostapd_channel_data *chan;
474
475 for (i = 0; i < mode->num_channels; i++) {
476 chan = &mode->channels[i];
477 if (!(chan->flag & HOSTAPD_CHAN_DISABLED) &&
478 acs_survey_list_is_sufficient(chan))
479 return 1;
480 }
481
482 return 0;
483 }
484
485
acs_surveys_are_sufficient(struct hostapd_iface * iface)486 static int acs_surveys_are_sufficient(struct hostapd_iface *iface)
487 {
488 int i;
489 struct hostapd_hw_modes *mode;
490
491 for (i = 0; i < iface->num_hw_features; i++) {
492 mode = &iface->hw_features[i];
493 if (!hostapd_hw_skip_mode(iface, mode) &&
494 acs_surveys_are_sufficient_mode(mode))
495 return 1;
496 }
497
498 return 0;
499 }
500
501
acs_usable_chan(struct hostapd_channel_data * chan)502 static int acs_usable_chan(struct hostapd_channel_data *chan)
503 {
504 return !dl_list_empty(&chan->survey_list) &&
505 !(chan->flag & HOSTAPD_CHAN_DISABLED) &&
506 acs_survey_list_is_sufficient(chan);
507 }
508
509
is_in_chanlist(struct hostapd_iface * iface,struct hostapd_channel_data * chan)510 static int is_in_chanlist(struct hostapd_iface *iface,
511 struct hostapd_channel_data *chan)
512 {
513 if (!iface->conf->acs_ch_list.num)
514 return 1;
515
516 return freq_range_list_includes(&iface->conf->acs_ch_list, chan->chan);
517 }
518
519
is_in_freqlist(struct hostapd_iface * iface,struct hostapd_channel_data * chan)520 static int is_in_freqlist(struct hostapd_iface *iface,
521 struct hostapd_channel_data *chan)
522 {
523 if (!iface->conf->acs_freq_list.num)
524 return 1;
525
526 return freq_range_list_includes(&iface->conf->acs_freq_list,
527 chan->freq);
528 }
529
530
acs_survey_mode_interference_factor(struct hostapd_iface * iface,struct hostapd_hw_modes * mode)531 static void acs_survey_mode_interference_factor(
532 struct hostapd_iface *iface, struct hostapd_hw_modes *mode)
533 {
534 int i;
535 struct hostapd_channel_data *chan;
536
537 for (i = 0; i < mode->num_channels; i++) {
538 chan = &mode->channels[i];
539
540 if (!acs_usable_chan(chan))
541 continue;
542
543 if ((chan->flag & HOSTAPD_CHAN_RADAR) &&
544 iface->conf->acs_exclude_dfs)
545 continue;
546
547 if (!is_in_chanlist(iface, chan))
548 continue;
549
550 if (!is_in_freqlist(iface, chan))
551 continue;
552
553 if (chan->max_tx_power < iface->conf->min_tx_power)
554 continue;
555
556 wpa_printf(MSG_DEBUG, "ACS: Survey analysis for channel %d (%d MHz)",
557 chan->chan, chan->freq);
558
559 acs_survey_chan_interference_factor(iface, chan);
560
561 wpa_printf(MSG_DEBUG, "ACS: * interference factor average: %Lg",
562 chan->interference_factor);
563 }
564 }
565
566
acs_survey_all_chans_interference_factor(struct hostapd_iface * iface)567 static void acs_survey_all_chans_interference_factor(
568 struct hostapd_iface *iface)
569 {
570 int i;
571 struct hostapd_hw_modes *mode;
572
573 for (i = 0; i < iface->num_hw_features; i++) {
574 mode = &iface->hw_features[i];
575 if (!hostapd_hw_skip_mode(iface, mode))
576 acs_survey_mode_interference_factor(iface, mode);
577 }
578 }
579
580
581 static struct hostapd_channel_data *
acs_find_chan_mode(struct hostapd_hw_modes * mode,int freq)582 acs_find_chan_mode(struct hostapd_hw_modes *mode, int freq)
583 {
584 struct hostapd_channel_data *chan;
585 int i;
586
587 for (i = 0; i < mode->num_channels; i++) {
588 chan = &mode->channels[i];
589
590 if (chan->flag & HOSTAPD_CHAN_DISABLED)
591 continue;
592
593 if (chan->freq == freq)
594 return chan;
595 }
596
597 return NULL;
598 }
599
600
601 static struct hostapd_channel_data *
acs_find_chan(struct hostapd_iface * iface,int freq)602 acs_find_chan(struct hostapd_iface *iface, int freq)
603 {
604 int i;
605 struct hostapd_hw_modes *mode;
606 struct hostapd_channel_data *chan;
607
608 for (i = 0; i < iface->num_hw_features; i++) {
609 mode = &iface->hw_features[i];
610 if (!hostapd_hw_skip_mode(iface, mode)) {
611 chan = acs_find_chan_mode(mode, freq);
612 if (chan)
613 return chan;
614 }
615 }
616
617 return NULL;
618 }
619
620
is_24ghz_mode(enum hostapd_hw_mode mode)621 static int is_24ghz_mode(enum hostapd_hw_mode mode)
622 {
623 return mode == HOSTAPD_MODE_IEEE80211B ||
624 mode == HOSTAPD_MODE_IEEE80211G;
625 }
626
627
is_common_24ghz_chan(int chan)628 static int is_common_24ghz_chan(int chan)
629 {
630 return chan == 1 || chan == 6 || chan == 11;
631 }
632
633
634 #ifndef ACS_ADJ_WEIGHT
635 #define ACS_ADJ_WEIGHT 0.85
636 #endif /* ACS_ADJ_WEIGHT */
637
638 #ifndef ACS_NEXT_ADJ_WEIGHT
639 #define ACS_NEXT_ADJ_WEIGHT 0.55
640 #endif /* ACS_NEXT_ADJ_WEIGHT */
641
642 #ifndef ACS_24GHZ_PREFER_1_6_11
643 /*
644 * Select commonly used channels 1, 6, 11 by default even if a neighboring
645 * channel has a smaller interference factor as long as it is not better by more
646 * than this multiplier.
647 */
648 #define ACS_24GHZ_PREFER_1_6_11 0.8
649 #endif /* ACS_24GHZ_PREFER_1_6_11 */
650
651 static void
acs_find_ideal_chan_mode(struct hostapd_iface * iface,struct hostapd_hw_modes * mode,int n_chans,u32 bw,struct hostapd_channel_data ** rand_chan,struct hostapd_channel_data ** ideal_chan,long double * ideal_factor)652 acs_find_ideal_chan_mode(struct hostapd_iface *iface,
653 struct hostapd_hw_modes *mode,
654 int n_chans, u32 bw,
655 struct hostapd_channel_data **rand_chan,
656 struct hostapd_channel_data **ideal_chan,
657 long double *ideal_factor)
658 {
659 struct hostapd_channel_data *chan, *adj_chan = NULL;
660 long double factor;
661 int i, j;
662 unsigned int k;
663
664 for (i = 0; i < mode->num_channels; i++) {
665 double total_weight;
666 struct acs_bias *bias, tmp_bias;
667
668 chan = &mode->channels[i];
669
670 /* Since in the current ACS implementation the first channel is
671 * always a primary channel, skip channels not available as
672 * primary until more sophisticated channel selection is
673 * implemented. */
674 if (!chan_pri_allowed(chan))
675 continue;
676
677 if ((chan->flag & HOSTAPD_CHAN_RADAR) &&
678 iface->conf->acs_exclude_dfs)
679 continue;
680
681 if (!is_in_chanlist(iface, chan))
682 continue;
683
684 if (!is_in_freqlist(iface, chan))
685 continue;
686
687 if (chan->max_tx_power < iface->conf->min_tx_power)
688 continue;
689
690 if (!chan_bw_allowed(chan, bw, 1, 1)) {
691 wpa_printf(MSG_DEBUG,
692 "ACS: Channel %d: BW %u is not supported",
693 chan->chan, bw);
694 continue;
695 }
696
697 /* HT40 on 5 GHz has a limited set of primary channels as per
698 * 11n Annex J */
699 if (mode->mode == HOSTAPD_MODE_IEEE80211A &&
700 ((iface->conf->ieee80211n &&
701 iface->conf->secondary_channel) ||
702 is_6ghz_freq(chan->freq)) &&
703 !acs_usable_bw40_chan(chan)) {
704 wpa_printf(MSG_DEBUG,
705 "ACS: Channel %d: not allowed as primary channel for 40 MHz bandwidth",
706 chan->chan);
707 continue;
708 }
709
710 if (mode->mode == HOSTAPD_MODE_IEEE80211A &&
711 (iface->conf->ieee80211ac || iface->conf->ieee80211ax)) {
712 if (hostapd_get_oper_chwidth(iface->conf) ==
713 CHANWIDTH_80MHZ &&
714 !acs_usable_bw80_chan(chan)) {
715 wpa_printf(MSG_DEBUG,
716 "ACS: Channel %d: not allowed as primary channel for 80 MHz bandwidth",
717 chan->chan);
718 continue;
719 }
720
721 if (hostapd_get_oper_chwidth(iface->conf) ==
722 CHANWIDTH_160MHZ &&
723 !acs_usable_bw160_chan(chan)) {
724 wpa_printf(MSG_DEBUG,
725 "ACS: Channel %d: not allowed as primary channel for 160 MHz bandwidth",
726 chan->chan);
727 continue;
728 }
729 }
730
731 factor = 0;
732 if (acs_usable_chan(chan))
733 factor = chan->interference_factor;
734 total_weight = 1;
735
736 for (j = 1; j < n_chans; j++) {
737 adj_chan = acs_find_chan(iface, chan->freq + (j * 20));
738 if (!adj_chan)
739 break;
740
741 if (!chan_bw_allowed(adj_chan, bw, 1, 0)) {
742 wpa_printf(MSG_DEBUG,
743 "ACS: PRI Channel %d: secondary channel %d BW %u is not supported",
744 chan->chan, adj_chan->chan, bw);
745 break;
746 }
747
748 if (acs_usable_chan(adj_chan)) {
749 factor += adj_chan->interference_factor;
750 total_weight += 1;
751 }
752 }
753
754 if (j != n_chans) {
755 wpa_printf(MSG_DEBUG, "ACS: Channel %d: not enough bandwidth",
756 chan->chan);
757 continue;
758 }
759
760 /* 2.4 GHz has overlapping 20 MHz channels. Include adjacent
761 * channel interference factor. */
762 if (is_24ghz_mode(mode->mode)) {
763 for (j = 0; j < n_chans; j++) {
764 adj_chan = acs_find_chan(iface, chan->freq +
765 (j * 20) - 5);
766 if (adj_chan && acs_usable_chan(adj_chan)) {
767 factor += ACS_ADJ_WEIGHT *
768 adj_chan->interference_factor;
769 total_weight += ACS_ADJ_WEIGHT;
770 }
771
772 adj_chan = acs_find_chan(iface, chan->freq +
773 (j * 20) - 10);
774 if (adj_chan && acs_usable_chan(adj_chan)) {
775 factor += ACS_NEXT_ADJ_WEIGHT *
776 adj_chan->interference_factor;
777 total_weight += ACS_NEXT_ADJ_WEIGHT;
778 }
779
780 adj_chan = acs_find_chan(iface, chan->freq +
781 (j * 20) + 5);
782 if (adj_chan && acs_usable_chan(adj_chan)) {
783 factor += ACS_ADJ_WEIGHT *
784 adj_chan->interference_factor;
785 total_weight += ACS_ADJ_WEIGHT;
786 }
787
788 adj_chan = acs_find_chan(iface, chan->freq +
789 (j * 20) + 10);
790 if (adj_chan && acs_usable_chan(adj_chan)) {
791 factor += ACS_NEXT_ADJ_WEIGHT *
792 adj_chan->interference_factor;
793 total_weight += ACS_NEXT_ADJ_WEIGHT;
794 }
795 }
796 }
797
798 factor /= total_weight;
799
800 bias = NULL;
801 if (iface->conf->acs_chan_bias) {
802 for (k = 0; k < iface->conf->num_acs_chan_bias; k++) {
803 bias = &iface->conf->acs_chan_bias[k];
804 if (bias->channel == chan->chan)
805 break;
806 bias = NULL;
807 }
808 } else if (is_24ghz_mode(mode->mode) &&
809 is_common_24ghz_chan(chan->chan)) {
810 tmp_bias.channel = chan->chan;
811 tmp_bias.bias = ACS_24GHZ_PREFER_1_6_11;
812 bias = &tmp_bias;
813 }
814
815 if (bias) {
816 factor *= bias->bias;
817 wpa_printf(MSG_DEBUG,
818 "ACS: * channel %d: total interference = %Lg (%f bias)",
819 chan->chan, factor, bias->bias);
820 } else {
821 wpa_printf(MSG_DEBUG,
822 "ACS: * channel %d: total interference = %Lg",
823 chan->chan, factor);
824 }
825
826 if (acs_usable_chan(chan) &&
827 (!*ideal_chan || factor < *ideal_factor)) {
828 *ideal_factor = factor;
829 *ideal_chan = chan;
830 }
831
832 /* This channel would at least be usable */
833 if (!(*rand_chan))
834 *rand_chan = chan;
835 }
836 }
837
838
839 /*
840 * At this point it's assumed chan->interference_factor has been computed.
841 * This function should be reusable regardless of interference computation
842 * option (survey, BSS, spectral, ...). chan->interference factor must be
843 * summable (i.e., must be always greater than zero).
844 */
845 static struct hostapd_channel_data *
acs_find_ideal_chan(struct hostapd_iface * iface)846 acs_find_ideal_chan(struct hostapd_iface *iface)
847 {
848 struct hostapd_channel_data *ideal_chan = NULL,
849 *rand_chan = NULL;
850 long double ideal_factor = 0;
851 int i;
852 int n_chans = 1;
853 u32 bw;
854 struct hostapd_hw_modes *mode;
855
856 if (is_6ghz_op_class(iface->conf->op_class)) {
857 bw = op_class_to_bandwidth(iface->conf->op_class);
858 n_chans = bw / 20;
859 goto bw_selected;
860 }
861
862 /* TODO: HT40- support */
863
864 if (iface->conf->ieee80211n &&
865 iface->conf->secondary_channel == -1) {
866 wpa_printf(MSG_ERROR, "ACS: HT40- is not supported yet. Please try HT40+");
867 return NULL;
868 }
869
870 if (iface->conf->ieee80211n &&
871 iface->conf->secondary_channel)
872 n_chans = 2;
873
874 if (iface->conf->ieee80211ac || iface->conf->ieee80211ax) {
875 switch (hostapd_get_oper_chwidth(iface->conf)) {
876 case CHANWIDTH_80MHZ:
877 n_chans = 4;
878 break;
879 case CHANWIDTH_160MHZ:
880 n_chans = 8;
881 break;
882 }
883 }
884
885 bw = num_chan_to_bw(n_chans);
886
887 bw_selected:
888 /* TODO: VHT/HE80+80. Update acs_adjust_center_freq() too. */
889
890 wpa_printf(MSG_DEBUG,
891 "ACS: Survey analysis for selected bandwidth %d MHz", bw);
892
893 for (i = 0; i < iface->num_hw_features; i++) {
894 mode = &iface->hw_features[i];
895 if (!hostapd_hw_skip_mode(iface, mode))
896 acs_find_ideal_chan_mode(iface, mode, n_chans, bw,
897 &rand_chan, &ideal_chan,
898 &ideal_factor);
899 }
900
901 if (ideal_chan) {
902 wpa_printf(MSG_DEBUG, "ACS: Ideal channel is %d (%d MHz) with total interference factor of %Lg",
903 ideal_chan->chan, ideal_chan->freq, ideal_factor);
904 return ideal_chan;
905 }
906
907 return rand_chan;
908 }
909
910
acs_adjust_center_freq(struct hostapd_iface * iface)911 static void acs_adjust_center_freq(struct hostapd_iface *iface)
912 {
913 int offset;
914
915 wpa_printf(MSG_DEBUG, "ACS: Adjusting VHT center frequency");
916
917 switch (hostapd_get_oper_chwidth(iface->conf)) {
918 case CHANWIDTH_USE_HT:
919 offset = 2 * iface->conf->secondary_channel;
920 break;
921 case CHANWIDTH_80MHZ:
922 offset = 6;
923 break;
924 case CHANWIDTH_160MHZ:
925 offset = 14;
926 break;
927 default:
928 /* TODO: How can this be calculated? Adjust
929 * acs_find_ideal_chan() */
930 wpa_printf(MSG_INFO,
931 "ACS: Only VHT20/40/80/160 is supported now");
932 return;
933 }
934
935 hostapd_set_oper_centr_freq_seg0_idx(iface->conf,
936 iface->conf->channel + offset);
937 }
938
939
acs_study_survey_based(struct hostapd_iface * iface)940 static int acs_study_survey_based(struct hostapd_iface *iface)
941 {
942 wpa_printf(MSG_DEBUG, "ACS: Trying survey-based ACS");
943
944 if (!iface->chans_surveyed) {
945 wpa_printf(MSG_ERROR, "ACS: Unable to collect survey data");
946 return -1;
947 }
948
949 if (!acs_surveys_are_sufficient(iface)) {
950 wpa_printf(MSG_ERROR, "ACS: Surveys have insufficient data");
951 return -1;
952 }
953
954 acs_survey_all_chans_interference_factor(iface);
955 return 0;
956 }
957
958
acs_study_options(struct hostapd_iface * iface)959 static int acs_study_options(struct hostapd_iface *iface)
960 {
961 if (acs_study_survey_based(iface) == 0)
962 return 0;
963
964 /* TODO: If no surveys are available/sufficient this is a good
965 * place to fallback to BSS-based ACS */
966
967 return -1;
968 }
969
970
acs_study(struct hostapd_iface * iface)971 static void acs_study(struct hostapd_iface *iface)
972 {
973 struct hostapd_channel_data *ideal_chan;
974 int err;
975
976 err = acs_study_options(iface);
977 if (err < 0) {
978 wpa_printf(MSG_ERROR, "ACS: All study options have failed");
979 goto fail;
980 }
981
982 ideal_chan = acs_find_ideal_chan(iface);
983 if (!ideal_chan) {
984 wpa_printf(MSG_ERROR, "ACS: Failed to compute ideal channel");
985 err = -1;
986 goto fail;
987 }
988
989 iface->conf->channel = ideal_chan->chan;
990 iface->freq = ideal_chan->freq;
991
992 if (iface->conf->ieee80211ac || iface->conf->ieee80211ax)
993 acs_adjust_center_freq(iface);
994
995 err = 0;
996 fail:
997 /*
998 * hostapd_setup_interface_complete() will return -1 on failure,
999 * 0 on success and 0 is HOSTAPD_CHAN_VALID :)
1000 */
1001 if (hostapd_acs_completed(iface, err) == HOSTAPD_CHAN_VALID) {
1002 acs_cleanup(iface);
1003 return;
1004 }
1005
1006 /* This can possibly happen if channel parameters (secondary
1007 * channel, center frequencies) are misconfigured */
1008 wpa_printf(MSG_ERROR, "ACS: Possibly channel configuration is invalid, please report this along with your config file.");
1009 acs_fail(iface);
1010 }
1011
1012
acs_scan_complete(struct hostapd_iface * iface)1013 static void acs_scan_complete(struct hostapd_iface *iface)
1014 {
1015 int err;
1016
1017 iface->scan_cb = NULL;
1018
1019 wpa_printf(MSG_DEBUG, "ACS: Using survey based algorithm (acs_num_scans=%d)",
1020 iface->conf->acs_num_scans);
1021
1022 err = hostapd_drv_get_survey(iface->bss[0], 0);
1023 if (err) {
1024 wpa_printf(MSG_ERROR, "ACS: Failed to get survey data");
1025 goto fail;
1026 }
1027
1028 if (++iface->acs_num_completed_scans < iface->conf->acs_num_scans) {
1029 err = acs_request_scan(iface);
1030 if (err) {
1031 wpa_printf(MSG_ERROR, "ACS: Failed to request scan");
1032 goto fail;
1033 }
1034
1035 return;
1036 }
1037
1038 acs_study(iface);
1039 return;
1040 fail:
1041 hostapd_acs_completed(iface, 1);
1042 acs_fail(iface);
1043 }
1044
1045
acs_request_scan_add_freqs(struct hostapd_iface * iface,struct hostapd_hw_modes * mode,int * freq)1046 static int * acs_request_scan_add_freqs(struct hostapd_iface *iface,
1047 struct hostapd_hw_modes *mode,
1048 int *freq)
1049 {
1050 struct hostapd_channel_data *chan;
1051 int i;
1052
1053 for (i = 0; i < mode->num_channels; i++) {
1054 chan = &mode->channels[i];
1055 if ((chan->flag & HOSTAPD_CHAN_DISABLED) ||
1056 ((chan->flag & HOSTAPD_CHAN_RADAR) &&
1057 iface->conf->acs_exclude_dfs))
1058 continue;
1059
1060 if (!is_in_chanlist(iface, chan))
1061 continue;
1062
1063 if (!is_in_freqlist(iface, chan))
1064 continue;
1065
1066 if (chan->max_tx_power < iface->conf->min_tx_power)
1067 continue;
1068
1069 *freq++ = chan->freq;
1070 }
1071
1072 return freq;
1073 }
1074
1075
acs_request_scan(struct hostapd_iface * iface)1076 static int acs_request_scan(struct hostapd_iface *iface)
1077 {
1078 struct wpa_driver_scan_params params;
1079 int i, *freq;
1080 int num_channels;
1081 struct hostapd_hw_modes *mode;
1082
1083 os_memset(¶ms, 0, sizeof(params));
1084
1085 num_channels = 0;
1086 for (i = 0; i < iface->num_hw_features; i++) {
1087 mode = &iface->hw_features[i];
1088 if (!hostapd_hw_skip_mode(iface, mode))
1089 num_channels += mode->num_channels;
1090 }
1091
1092 params.freqs = os_calloc(num_channels + 1, sizeof(params.freqs[0]));
1093 if (params.freqs == NULL)
1094 return -1;
1095
1096 freq = params.freqs;
1097
1098 for (i = 0; i < iface->num_hw_features; i++) {
1099 mode = &iface->hw_features[i];
1100 if (!hostapd_hw_skip_mode(iface, mode))
1101 freq = acs_request_scan_add_freqs(iface, mode, freq);
1102 }
1103
1104 *freq = 0;
1105
1106 if (params.freqs == freq) {
1107 wpa_printf(MSG_ERROR, "ACS: No available channels found");
1108 os_free(params.freqs);
1109 return -1;
1110 }
1111
1112 iface->scan_cb = acs_scan_complete;
1113
1114 wpa_printf(MSG_DEBUG, "ACS: Scanning %d / %d",
1115 iface->acs_num_completed_scans + 1,
1116 iface->conf->acs_num_scans);
1117
1118 if (hostapd_driver_scan(iface->bss[0], ¶ms) < 0) {
1119 wpa_printf(MSG_ERROR, "ACS: Failed to request initial scan");
1120 acs_cleanup(iface);
1121 os_free(params.freqs);
1122 return -1;
1123 }
1124
1125 os_free(params.freqs);
1126 return 0;
1127 }
1128
1129
acs_init(struct hostapd_iface * iface)1130 enum hostapd_chan_status acs_init(struct hostapd_iface *iface)
1131 {
1132 wpa_printf(MSG_INFO, "ACS: Automatic channel selection started, this may take a bit");
1133
1134 if (iface->drv_flags & WPA_DRIVER_FLAGS_ACS_OFFLOAD) {
1135 wpa_printf(MSG_INFO, "ACS: Offloading to driver");
1136 if (hostapd_drv_do_acs(iface->bss[0]))
1137 return HOSTAPD_CHAN_INVALID;
1138 return HOSTAPD_CHAN_ACS;
1139 }
1140
1141 if (!iface->current_mode &&
1142 iface->conf->hw_mode != HOSTAPD_MODE_IEEE80211ANY)
1143 return HOSTAPD_CHAN_INVALID;
1144
1145 acs_cleanup(iface);
1146
1147 if (acs_request_scan(iface) < 0)
1148 return HOSTAPD_CHAN_INVALID;
1149
1150 hostapd_set_state(iface, HAPD_IFACE_ACS);
1151 wpa_msg(iface->bss[0]->msg_ctx, MSG_INFO, ACS_EVENT_STARTED);
1152
1153 return HOSTAPD_CHAN_ACS;
1154 }
1155