• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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(&params, 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], &params) < 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