1/*
2 * WPA Supplicant - background scan and roaming module: learn
3 * Copyright (c) 2009-2010, Jouni Malinen <j@w1.fi>
4 *
5 * This software may be distributed under the terms of the BSD license.
6 * See README for more details.
7 */
8
9#include "includes.h"
10
11#include "common.h"
12#include "eloop.h"
13#include "list.h"
14#include "common/ieee802_11_defs.h"
15#include "drivers/driver.h"
16#include "config_ssid.h"
17#include "wpa_supplicant_i.h"
18#include "driver_i.h"
19#include "scan.h"
20#include "bgscan.h"
21
22struct bgscan_learn_bss {
23	struct dl_list list;
24	u8 bssid[ETH_ALEN];
25	int freq;
26	u8 *neigh; /* num_neigh * ETH_ALEN buffer */
27	size_t num_neigh;
28};
29
30struct bgscan_learn_data {
31	struct wpa_supplicant *wpa_s;
32	const struct wpa_ssid *ssid;
33	int scan_interval;
34	int signal_threshold;
35	int short_interval; /* use if signal < threshold */
36	int long_interval; /* use if signal > threshold */
37	struct os_reltime last_bgscan;
38	char *fname;
39	struct dl_list bss;
40	int *supp_freqs;
41	int probe_idx;
42};
43
44
45static void bss_free(struct bgscan_learn_bss *bss)
46{
47	os_free(bss->neigh);
48	os_free(bss);
49}
50
51
52static int bssid_in_array(u8 *array, size_t array_len, const u8 *bssid)
53{
54	size_t i;
55
56	if (array == NULL || array_len == 0)
57		return 0;
58
59	for (i = 0; i < array_len; i++) {
60		if (os_memcmp(array + i * ETH_ALEN, bssid, ETH_ALEN) == 0)
61			return 1;
62	}
63
64	return 0;
65}
66
67
68static void bgscan_learn_add_neighbor(struct bgscan_learn_bss *bss,
69				      const u8 *bssid)
70{
71	u8 *n;
72
73	if (os_memcmp(bss->bssid, bssid, ETH_ALEN) == 0)
74		return;
75	if (bssid_in_array(bss->neigh, bss->num_neigh, bssid))
76		return;
77
78	n = os_realloc_array(bss->neigh, bss->num_neigh + 1, ETH_ALEN);
79	if (n == NULL)
80		return;
81
82	os_memcpy(n + bss->num_neigh * ETH_ALEN, bssid, ETH_ALEN);
83	bss->neigh = n;
84	bss->num_neigh++;
85}
86
87
88static struct bgscan_learn_bss * bgscan_learn_get_bss(
89	struct bgscan_learn_data *data, const u8 *bssid)
90{
91	struct bgscan_learn_bss *bss;
92
93	dl_list_for_each(bss, &data->bss, struct bgscan_learn_bss, list) {
94		if (os_memcmp(bss->bssid, bssid, ETH_ALEN) == 0)
95			return bss;
96	}
97	return NULL;
98}
99
100
101static int bgscan_learn_load(struct bgscan_learn_data *data)
102{
103	FILE *f;
104	char buf[128];
105	struct bgscan_learn_bss *bss;
106
107	if (data->fname == NULL)
108		return 0;
109
110	f = fopen(data->fname, "r");
111	if (f == NULL)
112		return 0;
113
114	wpa_printf(MSG_DEBUG, "bgscan learn: Loading data from %s",
115		   data->fname);
116
117	if (fgets(buf, sizeof(buf), f) == NULL ||
118	    os_strncmp(buf, "wpa_supplicant-bgscan-learn\n", 28) != 0) {
119		wpa_printf(MSG_INFO, "bgscan learn: Invalid data file %s",
120			   data->fname);
121		fclose(f);
122		return -1;
123	}
124
125	while (fgets(buf, sizeof(buf), f)) {
126		if (os_strncmp(buf, "BSS ", 4) == 0) {
127			bss = os_zalloc(sizeof(*bss));
128			if (!bss)
129				continue;
130			if (hwaddr_aton(buf + 4, bss->bssid) < 0) {
131				bss_free(bss);
132				continue;
133			}
134			bss->freq = atoi(buf + 4 + 18);
135			dl_list_add(&data->bss, &bss->list);
136			wpa_printf(MSG_DEBUG, "bgscan learn: Loaded BSS "
137				   "entry: " MACSTR " freq=%d",
138				   MAC2STR(bss->bssid), bss->freq);
139		}
140
141		if (os_strncmp(buf, "NEIGHBOR ", 9) == 0) {
142			u8 addr[ETH_ALEN];
143
144			if (hwaddr_aton(buf + 9, addr) < 0)
145				continue;
146			bss = bgscan_learn_get_bss(data, addr);
147			if (bss == NULL)
148				continue;
149			if (hwaddr_aton(buf + 9 + 18, addr) < 0)
150				continue;
151
152			bgscan_learn_add_neighbor(bss, addr);
153		}
154	}
155
156	fclose(f);
157	return 0;
158}
159
160
161static void bgscan_learn_save(struct bgscan_learn_data *data)
162{
163	FILE *f;
164	struct bgscan_learn_bss *bss;
165
166	if (data->fname == NULL)
167		return;
168
169	wpa_printf(MSG_DEBUG, "bgscan learn: Saving data to %s",
170		   data->fname);
171
172	f = fopen(data->fname, "w");
173	if (f == NULL)
174		return;
175	fprintf(f, "wpa_supplicant-bgscan-learn\n");
176
177	dl_list_for_each(bss, &data->bss, struct bgscan_learn_bss, list) {
178		fprintf(f, "BSS " MACSTR " %d\n",
179			MAC2STR(bss->bssid), bss->freq);
180	}
181
182	dl_list_for_each(bss, &data->bss, struct bgscan_learn_bss, list) {
183		size_t i;
184		for (i = 0; i < bss->num_neigh; i++) {
185			fprintf(f, "NEIGHBOR " MACSTR " " MACSTR "\n",
186				MAC2STR(bss->bssid),
187				MAC2STR(bss->neigh + i * ETH_ALEN));
188		}
189	}
190
191	fclose(f);
192}
193
194
195static int in_array(int *array, int val)
196{
197	int i;
198
199	if (array == NULL)
200		return 0;
201
202	for (i = 0; array[i]; i++) {
203		if (array[i] == val)
204			return 1;
205	}
206
207	return 0;
208}
209
210
211static int * bgscan_learn_get_freqs(struct bgscan_learn_data *data,
212				    size_t *count)
213{
214	struct bgscan_learn_bss *bss;
215	int *freqs = NULL, *n;
216
217	*count = 0;
218
219	dl_list_for_each(bss, &data->bss, struct bgscan_learn_bss, list) {
220		if (in_array(freqs, bss->freq))
221			continue;
222		n = os_realloc_array(freqs, *count + 2, sizeof(int));
223		if (n == NULL)
224			return freqs;
225		freqs = n;
226		freqs[*count] = bss->freq;
227		(*count)++;
228		freqs[*count] = 0;
229	}
230
231	return freqs;
232}
233
234
235static int * bgscan_learn_get_probe_freq(struct bgscan_learn_data *data,
236					 int *freqs, size_t count)
237{
238	int idx, *n;
239
240	if (data->supp_freqs == NULL)
241		return freqs;
242
243	idx = data->probe_idx;
244	do {
245		if (!in_array(freqs, data->supp_freqs[idx])) {
246			wpa_printf(MSG_DEBUG, "bgscan learn: Probe new freq "
247				   "%u", data->supp_freqs[idx]);
248			data->probe_idx = idx + 1;
249			if (data->supp_freqs[data->probe_idx] == 0)
250				data->probe_idx = 0;
251			n = os_realloc_array(freqs, count + 2, sizeof(int));
252			if (n == NULL)
253				return freqs;
254			freqs = n;
255			freqs[count] = data->supp_freqs[idx];
256			count++;
257			freqs[count] = 0;
258			break;
259		}
260
261		idx++;
262		if (data->supp_freqs[idx] == 0)
263			idx = 0;
264	} while (idx != data->probe_idx);
265
266	return freqs;
267}
268
269
270static void bgscan_learn_timeout(void *eloop_ctx, void *timeout_ctx)
271{
272	struct bgscan_learn_data *data = eloop_ctx;
273	struct wpa_supplicant *wpa_s = data->wpa_s;
274	struct wpa_driver_scan_params params;
275	int *freqs = NULL;
276	size_t count, i;
277	char msg[100], *pos;
278
279	os_memset(&params, 0, sizeof(params));
280	params.num_ssids = 1;
281	params.ssids[0].ssid = data->ssid->ssid;
282	params.ssids[0].ssid_len = data->ssid->ssid_len;
283	if (data->ssid->scan_freq)
284		params.freqs = data->ssid->scan_freq;
285	else {
286		freqs = bgscan_learn_get_freqs(data, &count);
287		wpa_printf(MSG_DEBUG, "bgscan learn: BSSes in this ESS have "
288			   "been seen on %u channels", (unsigned int) count);
289		freqs = bgscan_learn_get_probe_freq(data, freqs, count);
290
291		msg[0] = '\0';
292		pos = msg;
293		for (i = 0; freqs && freqs[i]; i++) {
294			int ret;
295			ret = os_snprintf(pos, msg + sizeof(msg) - pos, " %d",
296					  freqs[i]);
297			if (ret < 0 || ret >= msg + sizeof(msg) - pos)
298				break;
299			pos += ret;
300		}
301		pos[0] = '\0';
302		wpa_printf(MSG_DEBUG, "bgscan learn: Scanning frequencies:%s",
303			   msg);
304		params.freqs = freqs;
305	}
306
307	wpa_printf(MSG_DEBUG, "bgscan learn: Request a background scan");
308	if (wpa_supplicant_trigger_scan(wpa_s, &params)) {
309		wpa_printf(MSG_DEBUG, "bgscan learn: Failed to trigger scan");
310		eloop_register_timeout(data->scan_interval, 0,
311				       bgscan_learn_timeout, data, NULL);
312	} else
313		os_get_reltime(&data->last_bgscan);
314	os_free(freqs);
315}
316
317
318static int bgscan_learn_get_params(struct bgscan_learn_data *data,
319				   const char *params)
320{
321	const char *pos;
322
323	if (params == NULL)
324		return 0;
325
326	data->short_interval = atoi(params);
327
328	pos = os_strchr(params, ':');
329	if (pos == NULL)
330		return 0;
331	pos++;
332	data->signal_threshold = atoi(pos);
333	pos = os_strchr(pos, ':');
334	if (pos == NULL) {
335		wpa_printf(MSG_ERROR, "bgscan learn: Missing scan interval "
336			   "for high signal");
337		return -1;
338	}
339	pos++;
340	data->long_interval = atoi(pos);
341	pos = os_strchr(pos, ':');
342	if (pos) {
343		pos++;
344		data->fname = os_strdup(pos);
345	}
346
347	return 0;
348}
349
350
351static int * bgscan_learn_get_supp_freqs(struct wpa_supplicant *wpa_s)
352{
353	struct hostapd_hw_modes *modes;
354	int i, j, *freqs = NULL, *n;
355	size_t count = 0;
356
357	modes = wpa_s->hw.modes;
358	if (modes == NULL)
359		return NULL;
360
361	for (i = 0; i < wpa_s->hw.num_modes; i++) {
362		for (j = 0; j < modes[i].num_channels; j++) {
363			if (modes[i].channels[j].flag & HOSTAPD_CHAN_DISABLED)
364				continue;
365			/* some hw modes (e.g. 11b & 11g) contain same freqs */
366			if (in_array(freqs, modes[i].channels[j].freq))
367				continue;
368			n = os_realloc_array(freqs, count + 2, sizeof(int));
369			if (n == NULL)
370				continue;
371
372			freqs = n;
373			freqs[count] = modes[i].channels[j].freq;
374			count++;
375			freqs[count] = 0;
376		}
377	}
378
379	return freqs;
380}
381
382
383static void * bgscan_learn_init(struct wpa_supplicant *wpa_s,
384				const char *params,
385				const struct wpa_ssid *ssid)
386{
387	struct bgscan_learn_data *data;
388
389	data = os_zalloc(sizeof(*data));
390	if (data == NULL)
391		return NULL;
392	dl_list_init(&data->bss);
393	data->wpa_s = wpa_s;
394	data->ssid = ssid;
395	if (bgscan_learn_get_params(data, params) < 0) {
396		os_free(data->fname);
397		os_free(data);
398		return NULL;
399	}
400	if (data->short_interval <= 0)
401		data->short_interval = 30;
402	if (data->long_interval <= 0)
403		data->long_interval = 30;
404
405	if (bgscan_learn_load(data) < 0) {
406		os_free(data->fname);
407		os_free(data);
408		return NULL;
409	}
410
411	wpa_printf(MSG_DEBUG, "bgscan learn: Signal strength threshold %d  "
412		   "Short bgscan interval %d  Long bgscan interval %d",
413		   data->signal_threshold, data->short_interval,
414		   data->long_interval);
415
416	if (data->signal_threshold &&
417	    wpa_drv_signal_monitor(wpa_s, data->signal_threshold, 4) < 0) {
418		wpa_printf(MSG_ERROR, "bgscan learn: Failed to enable "
419			   "signal strength monitoring");
420	}
421
422	data->supp_freqs = bgscan_learn_get_supp_freqs(wpa_s);
423	data->scan_interval = data->short_interval;
424	if (data->signal_threshold) {
425		/* Poll for signal info to set initial scan interval */
426		struct wpa_signal_info siginfo;
427		if (wpa_drv_signal_poll(wpa_s, &siginfo) == 0 &&
428		    siginfo.current_signal >= data->signal_threshold)
429			data->scan_interval = data->long_interval;
430	}
431
432	eloop_register_timeout(data->scan_interval, 0, bgscan_learn_timeout,
433			       data, NULL);
434
435	/*
436	 * This function is called immediately after an association, so it is
437	 * reasonable to assume that a scan was completed recently. This makes
438	 * us skip an immediate new scan in cases where the current signal
439	 * level is below the bgscan threshold.
440	 */
441	os_get_reltime(&data->last_bgscan);
442
443	return data;
444}
445
446
447static void bgscan_learn_deinit(void *priv)
448{
449	struct bgscan_learn_data *data = priv;
450	struct bgscan_learn_bss *bss, *n;
451
452	bgscan_learn_save(data);
453	eloop_cancel_timeout(bgscan_learn_timeout, data, NULL);
454	if (data->signal_threshold)
455		wpa_drv_signal_monitor(data->wpa_s, 0, 0);
456	os_free(data->fname);
457	dl_list_for_each_safe(bss, n, &data->bss, struct bgscan_learn_bss,
458			      list) {
459		dl_list_del(&bss->list);
460		bss_free(bss);
461	}
462	os_free(data->supp_freqs);
463	os_free(data);
464}
465
466
467static int bgscan_learn_bss_match(struct bgscan_learn_data *data,
468				  struct wpa_scan_res *bss)
469{
470	const u8 *ie;
471
472	ie = wpa_scan_get_ie(bss, WLAN_EID_SSID);
473	if (ie == NULL)
474		return 0;
475
476	if (data->ssid->ssid_len != ie[1] ||
477	    os_memcmp(data->ssid->ssid, ie + 2, ie[1]) != 0)
478		return 0; /* SSID mismatch */
479
480	return 1;
481}
482
483
484static int bgscan_learn_notify_scan(void *priv,
485				    struct wpa_scan_results *scan_res)
486{
487	struct bgscan_learn_data *data = priv;
488	size_t i, j;
489#define MAX_BSS 50
490	u8 bssid[MAX_BSS * ETH_ALEN];
491	size_t num_bssid = 0;
492
493	wpa_printf(MSG_DEBUG, "bgscan learn: scan result notification");
494
495	eloop_cancel_timeout(bgscan_learn_timeout, data, NULL);
496	eloop_register_timeout(data->scan_interval, 0, bgscan_learn_timeout,
497			       data, NULL);
498
499	for (i = 0; i < scan_res->num; i++) {
500		struct wpa_scan_res *res = scan_res->res[i];
501		if (!bgscan_learn_bss_match(data, res))
502			continue;
503
504		if (num_bssid < MAX_BSS) {
505			os_memcpy(bssid + num_bssid * ETH_ALEN, res->bssid,
506				  ETH_ALEN);
507			num_bssid++;
508		}
509	}
510	wpa_printf(MSG_DEBUG, "bgscan learn: %u matching BSSes in scan "
511		   "results", (unsigned int) num_bssid);
512
513	for (i = 0; i < scan_res->num; i++) {
514		struct wpa_scan_res *res = scan_res->res[i];
515		struct bgscan_learn_bss *bss;
516
517		if (!bgscan_learn_bss_match(data, res))
518			continue;
519
520		bss = bgscan_learn_get_bss(data, res->bssid);
521		if (bss && bss->freq != res->freq) {
522			wpa_printf(MSG_DEBUG, "bgscan learn: Update BSS "
523			   MACSTR " freq %d -> %d",
524				   MAC2STR(res->bssid), bss->freq, res->freq);
525			bss->freq = res->freq;
526		} else if (!bss) {
527			wpa_printf(MSG_DEBUG, "bgscan learn: Add BSS " MACSTR
528				   " freq=%d", MAC2STR(res->bssid), res->freq);
529			bss = os_zalloc(sizeof(*bss));
530			if (!bss)
531				continue;
532			os_memcpy(bss->bssid, res->bssid, ETH_ALEN);
533			bss->freq = res->freq;
534			dl_list_add(&data->bss, &bss->list);
535		}
536
537		for (j = 0; j < num_bssid; j++) {
538			u8 *addr = bssid + j * ETH_ALEN;
539			bgscan_learn_add_neighbor(bss, addr);
540		}
541	}
542
543	/*
544	 * A more advanced bgscan could process scan results internally, select
545	 * the BSS and request roam if needed. This sample uses the existing
546	 * BSS/ESS selection routine. Change this to return 1 if selection is
547	 * done inside the bgscan module.
548	 */
549
550	return 0;
551}
552
553
554static void bgscan_learn_notify_beacon_loss(void *priv)
555{
556	wpa_printf(MSG_DEBUG, "bgscan learn: beacon loss");
557	/* TODO: speed up background scanning */
558}
559
560
561static void bgscan_learn_notify_signal_change(void *priv, int above,
562					      int current_signal,
563					      int current_noise,
564					      int current_txrate)
565{
566	struct bgscan_learn_data *data = priv;
567	int scan = 0;
568	struct os_reltime now;
569
570	if (data->short_interval == data->long_interval ||
571	    data->signal_threshold == 0)
572		return;
573
574	wpa_printf(MSG_DEBUG, "bgscan learn: signal level changed "
575		   "(above=%d current_signal=%d current_noise=%d "
576		   "current_txrate=%d)", above, current_signal,
577		   current_noise, current_txrate);
578	if (data->scan_interval == data->long_interval && !above) {
579		wpa_printf(MSG_DEBUG, "bgscan learn: Start using short bgscan "
580			   "interval");
581		data->scan_interval = data->short_interval;
582		os_get_reltime(&now);
583		if (now.sec > data->last_bgscan.sec + 1)
584			scan = 1;
585	} else if (data->scan_interval == data->short_interval && above) {
586		wpa_printf(MSG_DEBUG, "bgscan learn: Start using long bgscan "
587			   "interval");
588		data->scan_interval = data->long_interval;
589		eloop_cancel_timeout(bgscan_learn_timeout, data, NULL);
590		eloop_register_timeout(data->scan_interval, 0,
591				       bgscan_learn_timeout, data, NULL);
592	} else if (!above) {
593		/*
594		 * Signal dropped further 4 dB. Request a new scan if we have
595		 * not yet scanned in a while.
596		 */
597		os_get_reltime(&now);
598		if (now.sec > data->last_bgscan.sec + 10)
599			scan = 1;
600	}
601
602	if (scan) {
603		wpa_printf(MSG_DEBUG, "bgscan learn: Trigger immediate scan");
604		eloop_cancel_timeout(bgscan_learn_timeout, data, NULL);
605		eloop_register_timeout(0, 0, bgscan_learn_timeout, data, NULL);
606	}
607}
608
609
610const struct bgscan_ops bgscan_learn_ops = {
611	.name = "learn",
612	.init = bgscan_learn_init,
613	.deinit = bgscan_learn_deinit,
614	.notify_scan = bgscan_learn_notify_scan,
615	.notify_beacon_loss = bgscan_learn_notify_beacon_loss,
616	.notify_signal_change = bgscan_learn_notify_signal_change,
617};
618