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