Re: [PATCH RFC 3/3] station: improve roam scan strategy

On 4/15/25 3:21 AM, Alexander Ganslandt wrote:
> When IWD decides to roam, it scans either neighbor freqs or known freqs
> (if neighbors are not available). If it fails to roam after getting the
> scan results, it scans ALL freqs. In my testing there's a high chance
> that both neighbor and/or known scans fail to roam and we end up
> scanning all freqs. This is very slow and if you're already moving away
> from the current BSS, there's a high chance you will lose connection
> completely before the scan is finished.
> 
> Instead of scanning all freqs at once, split them up into prioritized
> subsets. Each subset contains a handful of freqs each, a lower index for
> the subset means that its freqs are more common. So subset 0 has the
> most common freqs and subset 3 has the least common freqs. The first two
> subsets also contain no DFS channels, speeding up scanning even more. In
> order to make this efficient, use the "scan_freq_map" to avoid scanning
> freqs that were recently scanned.
> 
> When a roam scan is triggered, add the most prioritized freqs to the
> list of freqs that should be scanned. The order of priority is:
> 
> 1. Neighbor freqs
> 2. Known freqs
> 3. Subsets, starting with index 0 and incrementing if the subset is
>     exhausted
> 
> For each freq candidate, check the scan_freq_map to see how long time
> ago this freq was last scanned, this is denoted as its "age". If its age
> is above a threshold, add the freq to the list, otherwise discard it.
> Once the list has a certain size, start the scan. If no roaming occurs
> after the scan is completed, run the same function again. It will now
> pick new freqs since the previous freqs have been updated in
> scan_freq_map.
> 
> This approach results in more scans, but fewer freqs per scan, leading
> to shorter delays between scan results. It also avoids scanning the same
> freqs back-to-back, which is generally not very useful. In combination
> with the freq priority, this increases the chance of finding a good BSS
> early.
> ---
>   src/station.c | 190 +++++++++++++++++++++++++++++++++++++++++++++-------------
>   1 file changed, 149 insertions(+), 41 deletions(-)

<snip>

> @@ -2385,6 +2387,8 @@ static void station_roam_retry(struct station *station)
>   		station_roam_timeout_rearm(station, roam_retry_interval);
>   }
>   
> +static void station_start_roam(struct station *station);
> +

Just FYI, we don't like forward-declarations of static functions.  See 
doc/coding-style.txt item M17

> +static void station_filter_roam_scan_freq(uint32_t freq, void *user_data)
> +{
> +	struct scan_freq_set *freqs = user_data;
> +	uint64_t age = scan_get_freq_age(freq);

Have you considered maintaining a scan_freq_set of all the frequencies scanned 
by the neighbor and known-frequency stages instead of maintaining an hashtable 
based on age?
> +
> +	if (scan_freq_set_size(freqs) >= STATION_MAX_SCAN_FREQS) {
> +		return;
> +	}
> +
> +	if (age < STATION_MAX_SCAN_FREQ_AGE) {
> +		return;
> +	}

This is against the preferred Linux Kernel coding style.

> +
> +	scan_freq_set_add(freqs, freq);
> +}
> +
> +static struct scan_freq_set *station_get_roam_scan_freqs(struct station *station)
> +{
> +	struct scan_freq_set *tmp;
> +	struct scan_freq_set *scan_freqs;
> +
> +	scan_freqs = scan_freq_set_new();
> +
> +	/* Add current frequency, always scan this to get updated data for the
> +	 * current BSS */
> +	scan_freq_set_add(scan_freqs, station->connected_bss->frequency);
> +
> +	/* Add neighbor frequencies */
> +	scan_freq_set_foreach(station->roam_freqs, station_filter_roam_scan_freq, scan_freqs);
> +	if (scan_freq_set_size(scan_freqs) >= STATION_MAX_SCAN_FREQS) {
> +		goto out;
> +	}

So the idea is to add up to STATION_MAX_SCAN_FREQS to a new set, starting in 
order of preference with:
	1. neighbor frequency set
	2. known network set
	3. scan frequency ordering set

while filtering the frequencies already scanned.

How do you know when to give up the current attempt?

> +
> +	/* Add known frequencies */
> +	const struct network_info *info = network_get_info(
> +						station->connected_network);
> +	tmp = network_info_get_roam_frequencies(info,
> +					station->connected_bss->frequency,
> +					10);
> +	scan_freq_set_foreach(tmp, station_filter_roam_scan_freq, scan_freqs);
> +	scan_freq_set_free(tmp);
> +	if (scan_freq_set_size(scan_freqs) >= STATION_MAX_SCAN_FREQS) {
> +		goto out;
> +	}
> +
> +	/* Add frequencies based on the prioritized subsets */
> +	for (uint8_t i = 0; i < L_ARRAY_SIZE(station->scan_freqs_order); i++) {
> +		scan_freq_set_foreach(station->scan_freqs_order[i], station_filter_roam_scan_freq, scan_freqs);
> +		if (scan_freq_set_size(scan_freqs) >= STATION_MAX_SCAN_FREQS) {
> +			goto out;
> +		}
> +	}
> +
> +out:
> +	/* TODO: Arbitrary number to not have too small freq list */
> +	if (scan_freq_set_size(scan_freqs) <= 5) {

Why 5?  Why is this different from STATION_MAX_SCAN_FREQS?

> +		/* Might as well add the neighbors */
> +		scan_freq_set_merge(scan_freqs, station->roam_freqs);
> +	}
> +
> +	return scan_freqs;
> +}
> +

<snip>

> @@ -5007,44 +5083,79 @@ static void station_add_2_4ghz_freq(uint32_t freq, void *user_data)
>   
>   static void station_fill_scan_freq_subsets(struct station *station)
>   {
> -	const struct scan_freq_set *supported =
> -				wiphy_get_supported_freqs(station->wiphy);

For the most part the changes in this function make sense to me.  They can also 
be split out into a standalone commit since they improve on the already existing 
scan_freqs_order logic and will in theory speed up discovery via the Scan() api.

How do you deal with strange channels that might be supported only on some hardware?

>   	unsigned int subset_idx = 0;
>   
> -	/*
> -	 * Scan the 2.4GHz "social channels" first, 5GHz second, if supported,
> -	 * all other 2.4GHz channels last.  To be refined as needed.
> -	 */
> +	station->scan_freqs_order[subset_idx] = scan_freq_set_new();
> +
> +	/* Subset 0: 2.4GHz "social channels" and lower 5GHz non-DFS channels */
>   	if (allowed_bands & BAND_FREQ_2_4_GHZ) {
> -		station->scan_freqs_order[subset_idx] = scan_freq_set_new();
> -		scan_freq_set_add(station->scan_freqs_order[subset_idx], 2412);
> -		scan_freq_set_add(station->scan_freqs_order[subset_idx], 2437);
> -		scan_freq_set_add(station->scan_freqs_order[subset_idx], 2462);
> -		subset_idx++;
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 2412); /* 1 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 2437); /* 6 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 2462); /* 11 */

Ensure that lines are <= 80 columns.  See doc/coding-style.txt

>   	}
>   
> -	/*
> -	 * TODO: It may might sense to split up 5 and 6ghz into separate subsets
> -	 *       since the channel set is so large.
> -	 */
> -	if (allowed_bands & (BAND_FREQ_5_GHZ | BAND_FREQ_6_GHZ)) {
> -		uint32_t mask = allowed_bands &
> -					(BAND_FREQ_5_GHZ | BAND_FREQ_6_GHZ);
> -		struct scan_freq_set *set = scan_freq_set_clone(supported,
> -								mask);
> -
> -		/* 5/6ghz didn't add any frequencies */
> -		if (scan_freq_set_isempty(set)) {
> -			scan_freq_set_free(set);
> -		} else
> -			station->scan_freqs_order[subset_idx++] = set;
> +	if (allowed_bands & BAND_FREQ_5_GHZ) {
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5180); /* 36 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5200); /* 40 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5220); /* 44 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5240); /* 48 */
>   	}
>   
> -	/* Add remaining 2.4ghz channels to subset */
> +	station->scan_freqs_order[++subset_idx] = scan_freq_set_new();
> +
> +	/* Subset 1: 2.4GHz common "middle channels" and high 5GHz non-DFS channels */
>   	if (allowed_bands & BAND_FREQ_2_4_GHZ) {
> -		station->scan_freqs_order[subset_idx] = scan_freq_set_new();
> -		scan_freq_set_foreach(supported, station_add_2_4ghz_freq,
> -					station->scan_freqs_order[subset_idx]);
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 2422); /* 3 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 2427); /* 4 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 2447); /* 8 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 2452); /* 9 */
> +	}
> +
> +	if (allowed_bands & BAND_FREQ_5_GHZ) {
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5745); /* 149 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5765); /* 153 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5785); /* 157 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5805); /* 161 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5825); /* 165 */
> +	}
> +
> +	station->scan_freqs_order[++subset_idx] = scan_freq_set_new();
> +
> +	/* TODO: Add 6GHz here, after more common 2.4 and 5GHz, but before DFS */
> +
> +	/* Subset 2: 2.4GHz remaining channels and 5GHz most common DFS channels */
> +	if (allowed_bands & BAND_FREQ_2_4_GHZ) {
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 2417); /* 2 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 2432); /* 5 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 2442); /* 7 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 2457); /* 10 */

For example, there may be the weird channel 13 in 2.4G band.

> +	}
> +
> +	if (allowed_bands & BAND_FREQ_5_GHZ) {
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5260); /* 52 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5280); /* 56 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5300); /* 60 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5320); /* 64 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5500); /* 100 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5520); /* 104 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5540); /* 108 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5560); /* 112 */
> +	}
> +
> +	station->scan_freqs_order[++subset_idx] = scan_freq_set_new();
> +
> +	/* Subset 3: Remaining 5GHz DFS channels */
> +	if (allowed_bands & BAND_FREQ_5_GHZ) {
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5340); /* 68 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5480); /* 96 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5580); /* 116 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5600); /* 120 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5620); /* 124 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5640); /* 128 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5660); /* 132 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5680); /* 136 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5700); /* 140 */
> +		scan_freq_set_add(station->scan_freqs_order[subset_idx], 5720); /* 144 */
>   	}

There is now a left-over if() here that cannot happen and should be taken out.

Does the logic now need to take into account the fact that any given frequency 
set might be empty?

>   
>   	/*
> @@ -5223,11 +5334,8 @@ static void station_free(struct station *station)
>   
>   	l_queue_destroy(station->anqp_pending, remove_anqp);
>   
> -	scan_freq_set_free(station->scan_freqs_order[0]);
> -	scan_freq_set_free(station->scan_freqs_order[1]);
> -
> -	if (station->scan_freqs_order[2])
> -		scan_freq_set_free(station->scan_freqs_order[2]);
> +	for (uint8_t i = 0; i < 4; i++)
> +		scan_freq_set_free(station->scan_freqs_order[i]);

We prefer somewhat old style C here.  Also magic number 4 should be changed to 
L_ARRAY_SIZE.

>   
>   	wiphy_state_watch_remove(station->wiphy, station->wiphy_watch);
>   
> 

Regards,
-Denis