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 (!is_in_chanlist(iface, chan))
544 continue;
545
546 if (!is_in_freqlist(iface, chan))
547 continue;
548
549 if (chan->max_tx_power < iface->conf->min_tx_power)
550 continue;
551
552 wpa_printf(MSG_DEBUG, "ACS: Survey analysis for channel %d (%d MHz)",
553 chan->chan, chan->freq);
554
555 acs_survey_chan_interference_factor(iface, chan);
556
557 wpa_printf(MSG_DEBUG, "ACS: * interference factor average: %Lg",
558 chan->interference_factor);
559 }
560 }
561
562
acs_survey_all_chans_interference_factor(struct hostapd_iface * iface)563 static void acs_survey_all_chans_interference_factor(
564 struct hostapd_iface *iface)
565 {
566 int i;
567 struct hostapd_hw_modes *mode;
568
569 for (i = 0; i < iface->num_hw_features; i++) {
570 mode = &iface->hw_features[i];
571 if (!hostapd_hw_skip_mode(iface, mode))
572 acs_survey_mode_interference_factor(iface, mode);
573 }
574 }
575
576
577 static struct hostapd_channel_data *
acs_find_chan_mode(struct hostapd_hw_modes * mode,int freq)578 acs_find_chan_mode(struct hostapd_hw_modes *mode, int freq)
579 {
580 struct hostapd_channel_data *chan;
581 int i;
582
583 for (i = 0; i < mode->num_channels; i++) {
584 chan = &mode->channels[i];
585
586 if (chan->flag & HOSTAPD_CHAN_DISABLED)
587 continue;
588
589 if (chan->freq == freq)
590 return chan;
591 }
592
593 return NULL;
594 }
595
596
597 static struct hostapd_channel_data *
acs_find_chan(struct hostapd_iface * iface,int freq)598 acs_find_chan(struct hostapd_iface *iface, int freq)
599 {
600 int i;
601 struct hostapd_hw_modes *mode;
602 struct hostapd_channel_data *chan;
603
604 for (i = 0; i < iface->num_hw_features; i++) {
605 mode = &iface->hw_features[i];
606 if (!hostapd_hw_skip_mode(iface, mode)) {
607 chan = acs_find_chan_mode(mode, freq);
608 if (chan)
609 return chan;
610 }
611 }
612
613 return NULL;
614 }
615
616
is_24ghz_mode(enum hostapd_hw_mode mode)617 static int is_24ghz_mode(enum hostapd_hw_mode mode)
618 {
619 return mode == HOSTAPD_MODE_IEEE80211B ||
620 mode == HOSTAPD_MODE_IEEE80211G;
621 }
622
623
is_common_24ghz_chan(int chan)624 static int is_common_24ghz_chan(int chan)
625 {
626 return chan == 1 || chan == 6 || chan == 11;
627 }
628
629
630 #ifndef ACS_ADJ_WEIGHT
631 #define ACS_ADJ_WEIGHT 0.85
632 #endif /* ACS_ADJ_WEIGHT */
633
634 #ifndef ACS_NEXT_ADJ_WEIGHT
635 #define ACS_NEXT_ADJ_WEIGHT 0.55
636 #endif /* ACS_NEXT_ADJ_WEIGHT */
637
638 #ifndef ACS_24GHZ_PREFER_1_6_11
639 /*
640 * Select commonly used channels 1, 6, 11 by default even if a neighboring
641 * channel has a smaller interference factor as long as it is not better by more
642 * than this multiplier.
643 */
644 #define ACS_24GHZ_PREFER_1_6_11 0.8
645 #endif /* ACS_24GHZ_PREFER_1_6_11 */
646
647 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)648 acs_find_ideal_chan_mode(struct hostapd_iface *iface,
649 struct hostapd_hw_modes *mode,
650 int n_chans, u32 bw,
651 struct hostapd_channel_data **rand_chan,
652 struct hostapd_channel_data **ideal_chan,
653 long double *ideal_factor)
654 {
655 struct hostapd_channel_data *chan, *adj_chan = NULL;
656 long double factor;
657 int i, j;
658 unsigned int k;
659
660 for (i = 0; i < mode->num_channels; i++) {
661 double total_weight;
662 struct acs_bias *bias, tmp_bias;
663
664 chan = &mode->channels[i];
665
666 /* Since in the current ACS implementation the first channel is
667 * always a primary channel, skip channels not available as
668 * primary until more sophisticated channel selection is
669 * implemented. */
670 if (!chan_pri_allowed(chan))
671 continue;
672
673 if (!is_in_chanlist(iface, chan))
674 continue;
675
676 if (!is_in_freqlist(iface, chan))
677 continue;
678
679 if (chan->max_tx_power < iface->conf->min_tx_power)
680 continue;
681
682 if (!chan_bw_allowed(chan, bw, 1, 1)) {
683 wpa_printf(MSG_DEBUG,
684 "ACS: Channel %d: BW %u is not supported",
685 chan->chan, bw);
686 continue;
687 }
688
689 /* HT40 on 5 GHz has a limited set of primary channels as per
690 * 11n Annex J */
691 if (mode->mode == HOSTAPD_MODE_IEEE80211A &&
692 ((iface->conf->ieee80211n &&
693 iface->conf->secondary_channel) ||
694 is_6ghz_freq(chan->freq)) &&
695 !acs_usable_bw40_chan(chan)) {
696 wpa_printf(MSG_DEBUG,
697 "ACS: Channel %d: not allowed as primary channel for 40 MHz bandwidth",
698 chan->chan);
699 continue;
700 }
701
702 if (mode->mode == HOSTAPD_MODE_IEEE80211A &&
703 (iface->conf->ieee80211ac || iface->conf->ieee80211ax)) {
704 if (hostapd_get_oper_chwidth(iface->conf) ==
705 CHANWIDTH_80MHZ &&
706 !acs_usable_bw80_chan(chan)) {
707 wpa_printf(MSG_DEBUG,
708 "ACS: Channel %d: not allowed as primary channel for 80 MHz bandwidth",
709 chan->chan);
710 continue;
711 }
712
713 if (hostapd_get_oper_chwidth(iface->conf) ==
714 CHANWIDTH_160MHZ &&
715 !acs_usable_bw160_chan(chan)) {
716 wpa_printf(MSG_DEBUG,
717 "ACS: Channel %d: not allowed as primary channel for 160 MHz bandwidth",
718 chan->chan);
719 continue;
720 }
721 }
722
723 factor = 0;
724 if (acs_usable_chan(chan))
725 factor = chan->interference_factor;
726 total_weight = 1;
727
728 for (j = 1; j < n_chans; j++) {
729 adj_chan = acs_find_chan(iface, chan->freq + (j * 20));
730 if (!adj_chan)
731 break;
732
733 if (!chan_bw_allowed(adj_chan, bw, 1, 0)) {
734 wpa_printf(MSG_DEBUG,
735 "ACS: PRI Channel %d: secondary channel %d BW %u is not supported",
736 chan->chan, adj_chan->chan, bw);
737 break;
738 }
739
740 if (acs_usable_chan(adj_chan)) {
741 factor += adj_chan->interference_factor;
742 total_weight += 1;
743 }
744 }
745
746 if (j != n_chans) {
747 wpa_printf(MSG_DEBUG, "ACS: Channel %d: not enough bandwidth",
748 chan->chan);
749 continue;
750 }
751
752 /* 2.4 GHz has overlapping 20 MHz channels. Include adjacent
753 * channel interference factor. */
754 if (is_24ghz_mode(mode->mode)) {
755 for (j = 0; j < n_chans; j++) {
756 adj_chan = acs_find_chan(iface, chan->freq +
757 (j * 20) - 5);
758 if (adj_chan && acs_usable_chan(adj_chan)) {
759 factor += ACS_ADJ_WEIGHT *
760 adj_chan->interference_factor;
761 total_weight += ACS_ADJ_WEIGHT;
762 }
763
764 adj_chan = acs_find_chan(iface, chan->freq +
765 (j * 20) - 10);
766 if (adj_chan && acs_usable_chan(adj_chan)) {
767 factor += ACS_NEXT_ADJ_WEIGHT *
768 adj_chan->interference_factor;
769 total_weight += ACS_NEXT_ADJ_WEIGHT;
770 }
771
772 adj_chan = acs_find_chan(iface, chan->freq +
773 (j * 20) + 5);
774 if (adj_chan && acs_usable_chan(adj_chan)) {
775 factor += ACS_ADJ_WEIGHT *
776 adj_chan->interference_factor;
777 total_weight += ACS_ADJ_WEIGHT;
778 }
779
780 adj_chan = acs_find_chan(iface, chan->freq +
781 (j * 20) + 10);
782 if (adj_chan && acs_usable_chan(adj_chan)) {
783 factor += ACS_NEXT_ADJ_WEIGHT *
784 adj_chan->interference_factor;
785 total_weight += ACS_NEXT_ADJ_WEIGHT;
786 }
787 }
788 }
789
790 factor /= total_weight;
791
792 bias = NULL;
793 if (iface->conf->acs_chan_bias) {
794 for (k = 0; k < iface->conf->num_acs_chan_bias; k++) {
795 bias = &iface->conf->acs_chan_bias[k];
796 if (bias->channel == chan->chan)
797 break;
798 bias = NULL;
799 }
800 } else if (is_24ghz_mode(mode->mode) &&
801 is_common_24ghz_chan(chan->chan)) {
802 tmp_bias.channel = chan->chan;
803 tmp_bias.bias = ACS_24GHZ_PREFER_1_6_11;
804 bias = &tmp_bias;
805 }
806
807 if (bias) {
808 factor *= bias->bias;
809 wpa_printf(MSG_DEBUG,
810 "ACS: * channel %d: total interference = %Lg (%f bias)",
811 chan->chan, factor, bias->bias);
812 } else {
813 wpa_printf(MSG_DEBUG,
814 "ACS: * channel %d: total interference = %Lg",
815 chan->chan, factor);
816 }
817
818 if (acs_usable_chan(chan) &&
819 (!*ideal_chan || factor < *ideal_factor)) {
820 *ideal_factor = factor;
821 *ideal_chan = chan;
822 }
823
824 /* This channel would at least be usable */
825 if (!(*rand_chan))
826 *rand_chan = chan;
827 }
828 }
829
830
831 /*
832 * At this point it's assumed chan->interference_factor has been computed.
833 * This function should be reusable regardless of interference computation
834 * option (survey, BSS, spectral, ...). chan->interference factor must be
835 * summable (i.e., must be always greater than zero).
836 */
837 static struct hostapd_channel_data *
acs_find_ideal_chan(struct hostapd_iface * iface)838 acs_find_ideal_chan(struct hostapd_iface *iface)
839 {
840 struct hostapd_channel_data *ideal_chan = NULL,
841 *rand_chan = NULL;
842 long double ideal_factor = 0;
843 int i;
844 int n_chans = 1;
845 u32 bw;
846 struct hostapd_hw_modes *mode;
847
848 if (is_6ghz_op_class(iface->conf->op_class)) {
849 bw = op_class_to_bandwidth(iface->conf->op_class);
850 n_chans = bw / 20;
851 goto bw_selected;
852 }
853
854 /* TODO: HT40- support */
855
856 if (iface->conf->ieee80211n &&
857 iface->conf->secondary_channel == -1) {
858 wpa_printf(MSG_ERROR, "ACS: HT40- is not supported yet. Please try HT40+");
859 return NULL;
860 }
861
862 if (iface->conf->ieee80211n &&
863 iface->conf->secondary_channel)
864 n_chans = 2;
865
866 if (iface->conf->ieee80211ac || iface->conf->ieee80211ax) {
867 switch (hostapd_get_oper_chwidth(iface->conf)) {
868 case CHANWIDTH_80MHZ:
869 n_chans = 4;
870 break;
871 case CHANWIDTH_160MHZ:
872 n_chans = 8;
873 break;
874 }
875 }
876
877 bw = num_chan_to_bw(n_chans);
878
879 bw_selected:
880 /* TODO: VHT/HE80+80. Update acs_adjust_center_freq() too. */
881
882 wpa_printf(MSG_DEBUG,
883 "ACS: Survey analysis for selected bandwidth %d MHz", bw);
884
885 for (i = 0; i < iface->num_hw_features; i++) {
886 mode = &iface->hw_features[i];
887 if (!hostapd_hw_skip_mode(iface, mode))
888 acs_find_ideal_chan_mode(iface, mode, n_chans, bw,
889 &rand_chan, &ideal_chan,
890 &ideal_factor);
891 }
892
893 if (ideal_chan) {
894 wpa_printf(MSG_DEBUG, "ACS: Ideal channel is %d (%d MHz) with total interference factor of %Lg",
895 ideal_chan->chan, ideal_chan->freq, ideal_factor);
896 return ideal_chan;
897 }
898
899 return rand_chan;
900 }
901
902
acs_adjust_center_freq(struct hostapd_iface * iface)903 static void acs_adjust_center_freq(struct hostapd_iface *iface)
904 {
905 int offset;
906
907 wpa_printf(MSG_DEBUG, "ACS: Adjusting VHT center frequency");
908
909 switch (hostapd_get_oper_chwidth(iface->conf)) {
910 case CHANWIDTH_USE_HT:
911 offset = 2 * iface->conf->secondary_channel;
912 break;
913 case CHANWIDTH_80MHZ:
914 offset = 6;
915 break;
916 case CHANWIDTH_160MHZ:
917 offset = 14;
918 break;
919 default:
920 /* TODO: How can this be calculated? Adjust
921 * acs_find_ideal_chan() */
922 wpa_printf(MSG_INFO,
923 "ACS: Only VHT20/40/80/160 is supported now");
924 return;
925 }
926
927 hostapd_set_oper_centr_freq_seg0_idx(iface->conf,
928 iface->conf->channel + offset);
929 }
930
931
acs_study_survey_based(struct hostapd_iface * iface)932 static int acs_study_survey_based(struct hostapd_iface *iface)
933 {
934 wpa_printf(MSG_DEBUG, "ACS: Trying survey-based ACS");
935
936 if (!iface->chans_surveyed) {
937 wpa_printf(MSG_ERROR, "ACS: Unable to collect survey data");
938 return -1;
939 }
940
941 if (!acs_surveys_are_sufficient(iface)) {
942 wpa_printf(MSG_ERROR, "ACS: Surveys have insufficient data");
943 return -1;
944 }
945
946 acs_survey_all_chans_interference_factor(iface);
947 return 0;
948 }
949
950
acs_study_options(struct hostapd_iface * iface)951 static int acs_study_options(struct hostapd_iface *iface)
952 {
953 if (acs_study_survey_based(iface) == 0)
954 return 0;
955
956 /* TODO: If no surveys are available/sufficient this is a good
957 * place to fallback to BSS-based ACS */
958
959 return -1;
960 }
961
962
acs_study(struct hostapd_iface * iface)963 static void acs_study(struct hostapd_iface *iface)
964 {
965 struct hostapd_channel_data *ideal_chan;
966 int err;
967
968 err = acs_study_options(iface);
969 if (err < 0) {
970 wpa_printf(MSG_ERROR, "ACS: All study options have failed");
971 goto fail;
972 }
973
974 ideal_chan = acs_find_ideal_chan(iface);
975 if (!ideal_chan) {
976 wpa_printf(MSG_ERROR, "ACS: Failed to compute ideal channel");
977 err = -1;
978 goto fail;
979 }
980
981 iface->conf->channel = ideal_chan->chan;
982 iface->freq = ideal_chan->freq;
983
984 if (iface->conf->ieee80211ac || iface->conf->ieee80211ax)
985 acs_adjust_center_freq(iface);
986
987 err = 0;
988 fail:
989 /*
990 * hostapd_setup_interface_complete() will return -1 on failure,
991 * 0 on success and 0 is HOSTAPD_CHAN_VALID :)
992 */
993 if (hostapd_acs_completed(iface, err) == HOSTAPD_CHAN_VALID) {
994 acs_cleanup(iface);
995 return;
996 }
997
998 /* This can possibly happen if channel parameters (secondary
999 * channel, center frequencies) are misconfigured */
1000 wpa_printf(MSG_ERROR, "ACS: Possibly channel configuration is invalid, please report this along with your config file.");
1001 acs_fail(iface);
1002 }
1003
1004
acs_scan_complete(struct hostapd_iface * iface)1005 static void acs_scan_complete(struct hostapd_iface *iface)
1006 {
1007 int err;
1008
1009 iface->scan_cb = NULL;
1010
1011 wpa_printf(MSG_DEBUG, "ACS: Using survey based algorithm (acs_num_scans=%d)",
1012 iface->conf->acs_num_scans);
1013
1014 err = hostapd_drv_get_survey(iface->bss[0], 0);
1015 if (err) {
1016 wpa_printf(MSG_ERROR, "ACS: Failed to get survey data");
1017 goto fail;
1018 }
1019
1020 if (++iface->acs_num_completed_scans < iface->conf->acs_num_scans) {
1021 err = acs_request_scan(iface);
1022 if (err) {
1023 wpa_printf(MSG_ERROR, "ACS: Failed to request scan");
1024 goto fail;
1025 }
1026
1027 return;
1028 }
1029
1030 acs_study(iface);
1031 return;
1032 fail:
1033 hostapd_acs_completed(iface, 1);
1034 acs_fail(iface);
1035 }
1036
1037
acs_request_scan_add_freqs(struct hostapd_iface * iface,struct hostapd_hw_modes * mode,int * freq)1038 static int * acs_request_scan_add_freqs(struct hostapd_iface *iface,
1039 struct hostapd_hw_modes *mode,
1040 int *freq)
1041 {
1042 struct hostapd_channel_data *chan;
1043 int i;
1044
1045 for (i = 0; i < mode->num_channels; i++) {
1046 chan = &mode->channels[i];
1047 if (chan->flag & HOSTAPD_CHAN_DISABLED)
1048 continue;
1049
1050 if (!is_in_chanlist(iface, chan))
1051 continue;
1052
1053 if (!is_in_freqlist(iface, chan))
1054 continue;
1055
1056 if (chan->max_tx_power < iface->conf->min_tx_power)
1057 continue;
1058
1059 *freq++ = chan->freq;
1060 }
1061
1062 return freq;
1063 }
1064
1065
acs_request_scan(struct hostapd_iface * iface)1066 static int acs_request_scan(struct hostapd_iface *iface)
1067 {
1068 struct wpa_driver_scan_params params;
1069 int i, *freq;
1070 int num_channels;
1071 struct hostapd_hw_modes *mode;
1072
1073 os_memset(¶ms, 0, sizeof(params));
1074
1075 num_channels = 0;
1076 for (i = 0; i < iface->num_hw_features; i++) {
1077 mode = &iface->hw_features[i];
1078 if (!hostapd_hw_skip_mode(iface, mode))
1079 num_channels += mode->num_channels;
1080 }
1081
1082 params.freqs = os_calloc(num_channels + 1, sizeof(params.freqs[0]));
1083 if (params.freqs == NULL)
1084 return -1;
1085
1086 freq = params.freqs;
1087
1088 for (i = 0; i < iface->num_hw_features; i++) {
1089 mode = &iface->hw_features[i];
1090 if (!hostapd_hw_skip_mode(iface, mode))
1091 freq = acs_request_scan_add_freqs(iface, mode, freq);
1092 }
1093
1094 *freq = 0;
1095
1096 if (params.freqs == freq) {
1097 wpa_printf(MSG_ERROR, "ACS: No available channels found");
1098 os_free(params.freqs);
1099 return -1;
1100 }
1101
1102 iface->scan_cb = acs_scan_complete;
1103
1104 wpa_printf(MSG_DEBUG, "ACS: Scanning %d / %d",
1105 iface->acs_num_completed_scans + 1,
1106 iface->conf->acs_num_scans);
1107
1108 if (hostapd_driver_scan(iface->bss[0], ¶ms) < 0) {
1109 wpa_printf(MSG_ERROR, "ACS: Failed to request initial scan");
1110 acs_cleanup(iface);
1111 os_free(params.freqs);
1112 return -1;
1113 }
1114
1115 os_free(params.freqs);
1116 return 0;
1117 }
1118
1119
acs_init(struct hostapd_iface * iface)1120 enum hostapd_chan_status acs_init(struct hostapd_iface *iface)
1121 {
1122 wpa_printf(MSG_INFO, "ACS: Automatic channel selection started, this may take a bit");
1123
1124 if (iface->drv_flags & WPA_DRIVER_FLAGS_ACS_OFFLOAD) {
1125 wpa_printf(MSG_INFO, "ACS: Offloading to driver");
1126 if (hostapd_drv_do_acs(iface->bss[0]))
1127 return HOSTAPD_CHAN_INVALID;
1128 return HOSTAPD_CHAN_ACS;
1129 }
1130
1131 if (!iface->current_mode &&
1132 iface->conf->hw_mode != HOSTAPD_MODE_IEEE80211ANY)
1133 return HOSTAPD_CHAN_INVALID;
1134
1135 acs_cleanup(iface);
1136
1137 if (acs_request_scan(iface) < 0)
1138 return HOSTAPD_CHAN_INVALID;
1139
1140 hostapd_set_state(iface, HAPD_IFACE_ACS);
1141 wpa_msg(iface->bss[0]->msg_ctx, MSG_INFO, ACS_EVENT_STARTED);
1142
1143 return HOSTAPD_CHAN_ACS;
1144 }
1145