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