util: add util_linear_map
PATCH 1/8 util: add util_linear_map
This has been needed elsewhere but generally shortcuts could be taken mapping with ranges starting/ending with zero. This is a more general linear mapping utility to map values between any two ranges.
--- src/util.c | 30 ++++++++++++++++++++++++++++++ src/util.h | 11 +++++++++++ 2 files changed, 41 insertions(+)
src/util.c +30 -0
@@ -312,6 +312,36 @@ bool util_ip_prefix_tohl(const char *ip, uint8_t *prefix_out,return true; } +/* +* Linearly maps @value (expected to be within range @a_start and @a_end) to +* a new value between @b_start and @b_end. +* +* Returns: false if +* @value is not between @a_start and @a_end +* @a_start/@a_end or @b_start/@b_end are equal. +*/ +bool util_linear_map (double value,double a_start,double a_end, +double b_start,double b_end,double *mapped_value) +{ +/* Check value is within a's range */ +if (a_start < a_end) { +if (value < a_start || value > a_end) +return false; + }else if (a_start > a_end) { +if (value > a_start || value < a_end) +return false; + }else +return false; + +if (b_start == b_end) +return false; + + *mapped_value = b_start + (((b_end - b_start) / (a_end - a_start)) * + (value - a_start)); + +return true; +} +struct scan_freq_set {uint16_t channels_2ghz;struct l_uintset *channels_5ghz;
src/util.h +11 -0
@@ -106,6 +106,17 @@ static inline bool util_ip_subnet_match(uint8_t prefix_len, ~((1u << (8 - (prefix_len % 8))) - 1)); } +/* +* Linearly maps (interpolates) 'value' from range 'a' to range 'b' +* +* Fails if: +* - value is not between a and b +* - a_start == a_end +* - b_start == b_end +*/ +bool util_linear_map (double value,double a_start,double a_end, +double b_start,double b_end,double *mapped_value); +typedef void (*scan_freq_set_func_t )(uint32_t freq,void *userdata);struct scan_freq_set *scan_freq_set_new (void );
Signature · 1 line
2.34.1
PATCH 2/8 unit: add linear mapping test
--- unit/test-util.c | 70 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 70 insertions(+)
unit/test-util.c +70 -0
@@ -184,6 +184,75 @@ static void ip_prefix_test(const void *data) } } +struct linear_map_case { +double value; +double a_start; +double a_end; +double b_start; +double b_end; +double expected; + +bool fails :1 ; +}; + +struct linear_map_case cases[] = { +/* Value out of range */ + { + .value =100 , + .a_start =1 , + .a_end =3 , + .b_start =10 , + .b_end =12 , + .fails = true, + }, +/* Ascending start range */ + { + .value =1 , + .a_start =0 , + .a_end =2 , + .b_start =10 , + .b_end =12 , + .expected =11 , + }, +/* Descending start range */ + { + .value =1 , + .a_start =2 , + .a_end =0 , + .b_start =10 , + .b_end =12 , + .expected =11 , + }, +/* Negatives */ + { + .value =-1 , + .a_start =-2 , + .a_end =0 , + .b_start =0 , + .b_end =2 , + .expected =1 , + }, +}; + +static void test_linear_map (const void *data) +{ +double mapped; +unsigned int i; + +for (i =0 ; i <L_ARRAY_SIZE (cases); i++) { +struct linear_map_case *c = &cases[i]; +bool ret =util_linear_map (c->value, c->a_start, c->a_end, + c->b_start, c->b_end, &mapped); +if (c->fails) { +assert (ret == false); +continue ; + } + +assert (ret); +assert (mapped == c->expected); + } +} +int main (int argc,char *argv[]) {l_test_init (&argc, &argv);
@@ -192,6 +261,7 @@ int main(int argc, char *argv[])l_test_add ("/util/get_domain/" , get_domain_test,NULL );l_test_add ("/util/get_username/" , get_username_test,NULL );l_test_add ("/util/ip_prefix/" , ip_prefix_test,NULL ); +l_test_add ("/util/test_linear_map" , test_linear_map,NULL );return l_test_run (); }
Signature · 1 line
2.34.1
PATCH 3/8 util: add util_exponential_decay
In reply to James PrestwoodThis is copied from network.c that uses a static table to lookup exponential decay values by index (generated from 1/pow(n, 0.3)). network.c uses this for network ranking but it can be useful for BSS ranking as well if you need to apply some exponential backoff to a value.
--- src/util.c | 28 ++++++++++++++++++++++++++++ src/util.h | 2 ++ 2 files changed, 30 insertions(+)
src/util.c +28 -0
@@ -636,3 +636,31 @@ struct scan_freq_set *scan_freq_set_clone(const struct scan_freq_set *set,return new; } + +/* First 64 entries calculated by 1 / pow(n, 0.3) for n >= 1 */ +static const double rankmod_table[] = { +1.0000000000 ,0.8122523964 ,0.7192230933 ,0.6597539554 , +0.6170338627 ,0.5841906811 ,0.5577898253 ,0.5358867313 , +0.5172818580 ,0.5011872336 ,0.4870596972 ,0.4745102806 , +0.4632516708 ,0.4530661223 ,0.4437850034 ,0.4352752816 , +0.4274303178 ,0.4201634287 ,0.4134032816 ,0.4070905315 , +0.4011753236 ,0.3956154062 ,0.3903746872 ,0.3854221125 , +0.3807307877 ,0.3762772797 ,0.3720410580 ,0.3680040435 , +0.3641502401 ,0.3604654325 ,0.3569369365 ,0.3535533906 , +0.3503045821 ,0.3471812999 ,0.3441752105 ,0.3412787518 , +0.3384850430 ,0.3357878061 ,0.3331812996 ,0.3306602598 , +0.3282198502 ,0.3258556179 ,0.3235634544 ,0.3213395618 , +0.3191804229 ,0.3170827751 ,0.3150435863 ,0.3130600345 , +0.3111294892 ,0.3092494947 ,0.3074177553 ,0.3056321221 , +0.3038905808 ,0.3021912409 ,0.3005323264 ,0.2989121662 , +0.2973291870 ,0.2957819051 ,0.2942689208 ,0.2927889114 , +0.2913406263 ,0.2899228820 ,0.2885345572 ,0.2871745887 , +}; + +double util_exponential_decay (unsigned int n) +{ +if (n >L_ARRAY_SIZE (rankmod_table)) +return rankmod_table[L_ARRAY_SIZE (rankmod_table) -1 ]; + +return rankmod_table[n]; +}
src/util.h +2 -0
@@ -141,4 +141,6 @@ struct scan_freq_set *scan_freq_set_clone(const struct scan_freq_set *set,DEFINE_CLEANUP_FUNC (scan_freq_set_free); +double util_exponential_decay (unsigned int n); +#endif /* __UTIL_H */
Signature · 1 line
2.34.1
Re: [PATCH 3/8] util: add util_exponential_decay
Hi James,
Quoted 32 lines · James Prestwood
This is copied from
network.cthat uses a static table to lookup exponential decay values by index (generated from 1/pow(n, 0.3)).network.cuses this for network ranking but it can be useful for BSS ranking as well if you need to apply some exponential backoff to a value.--- src/util.c | 28 ++++++++++++++++++++++++++++ src/util.h | 2 ++ 2 files changed, 30 insertions(+)src/util.c +14
-0@@ -636,3 +636,31 @@ struct scan_freq_set *scan_freq_set_clone(const struct scan_freq_set *set,return new; } + +/* First 64 entries calculated by 1 / pow(n, 0.3) for n >= 1 */ +static const double rankmod_table[] = { +1.0000000000 ,0.8122523964 ,0.7192230933 ,0.6597539554 , +0.6170338627 ,0.5841906811 ,0.5577898253 ,0.5358867313 , +0.5172818580 ,0.5011872336 ,0.4870596972 ,0.4745102806 , +0.4632516708 ,0.4530661223 ,0.4437850034 ,0.4352752816 , +0.4274303178 ,0.4201634287 ,0.4134032816 ,0.4070905315 , +0.4011753236 ,0.3956154062 ,0.3903746872 ,0.3854221125 , +0.3807307877 ,0.3762772797 ,0.3720410580 ,0.3680040435 , +0.3641502401 ,0.3604654325 ,0.3569369365 ,0.3535533906 , +0.3503045821 ,0.3471812999 ,0.3441752105 ,0.3412787518 , +0.3384850430 ,0.3357878061 ,0.3331812996 ,0.3306602598 , +0.3282198502 ,0.3258556179 ,0.3235634544 ,0.3213395618 ,
src/util.c struct scan_freq_set *scan_freq_set_clone(const struct scan_freq_set *set, · line 662
Quoted 10 lines
src/util.c +10
-0+0.3191804229 ,0.3170827751 ,0.3150435863 ,0.3130600345 , +0.3111294892 ,0.3092494947 ,0.3074177553 ,0.3056321221 , +0.3038905808 ,0.3021912409 ,0.3005323264 ,0.2989121662 , +0.2973291870 ,0.2957819051 ,0.2942689208 ,0.2927889114 , + 0.2913406263, 0.2899228820, 0.2885345572, 0.2871745887, +}; + +double util_exponential_decay (unsigned int n) +{ +if (n >L_ARRAY_SIZE (rankmod_table))
I changed '>' to '>=' to avoid overflow. All 8 patches have been applied, thanks.
Regards,
-Denis
PATCH 4/8 network: use util_exponential_decay
In reply to James Prestwood--- src/network.c | 35 ++++------------------------------- 1 file changed, 4 insertions(+), 31 deletions(-)
src/network.c +4 -31
@@ -56,6 +56,7 @@#include "src/erp.h" #include "src/handshake.h" #include "src/band.h" +#include "src/util.h" #define SAE_PT_SETTING "SAE-PT-Group%u"
@@ -212,31 +213,10 @@ void network_disconnected(struct network *network)station_hide_network (network->station, network); } -/* First 64 entries calculated by 1 / pow(n, 0.3) for n >= 1 */ -static const double rankmod_table[] = { -1.0000000000 ,0.8122523964 ,0.7192230933 ,0.6597539554 , -0.6170338627 ,0.5841906811 ,0.5577898253 ,0.5358867313 , -0.5172818580 ,0.5011872336 ,0.4870596972 ,0.4745102806 , -0.4632516708 ,0.4530661223 ,0.4437850034 ,0.4352752816 , -0.4274303178 ,0.4201634287 ,0.4134032816 ,0.4070905315 , -0.4011753236 ,0.3956154062 ,0.3903746872 ,0.3854221125 , -0.3807307877 ,0.3762772797 ,0.3720410580 ,0.3680040435 , -0.3641502401 ,0.3604654325 ,0.3569369365 ,0.3535533906 , -0.3503045821 ,0.3471812999 ,0.3441752105 ,0.3412787518 , -0.3384850430 ,0.3357878061 ,0.3331812996 ,0.3306602598 , -0.3282198502 ,0.3258556179 ,0.3235634544 ,0.3213395618 , -0.3191804229 ,0.3170827751 ,0.3150435863 ,0.3130600345 , -0.3111294892 ,0.3092494947 ,0.3074177553 ,0.3056321221 , -0.3038905808 ,0.3021912409 ,0.3005323264 ,0.2989121662 , -0.2973291870 ,0.2957819051 ,0.2942689208 ,0.2927889114 , -0.2913406263 ,0.2899228820 ,0.2885345572 ,0.2871745887 , -}; -bool network_rankmod (const struct network *network,double *rankmod) {struct network_info *info = network->info;int n; -int nmax;/* * Current policy is that only networks successfully connected
@@ -250,12 +230,7 @@ bool network_rankmod(const struct network *network, double *rankmod)if (n <0 )return false; - nmax =L_ARRAY_SIZE (rankmod_table); - -if (n >= nmax) - n = nmax -1 ; - - *rankmod = rankmod_table[n]; + *rankmod =util_exponential_decay (n);return true; }
@@ -2018,10 +1993,8 @@ void network_rank_update(struct network *network, bool connected)L_WARN_ON (n <0 ); -if (n >= (int )L_ARRAY_SIZE (rankmod_table)) - n =L_ARRAY_SIZE (rankmod_table) -1 ; - - network->rank = rankmod_table[n] * best_bss->rank +USHRT_MAX ; + network->rank = +util_exponential_decay (n) * best_bss->rank +USHRT_MAX ; }else network->rank = best_bss->rank;
Signature · 1 line
2.34.1
PATCH 5/8 scan: parse station count from BSS load IE
In reply to James PrestwoodThis will be used in BSS ranking
--- src/scan.c | 4 ++-- src/scan.h | 1 + 2 files changed, 3 insertions(+), 2 deletions(-)
src/scan.c +2 -2
@@ -1343,8 +1343,8 @@ static bool scan_parse_bss_information_elements(struct scan_bss *bss, iter.len + 2);break ;case IE_TYPE_BSS_LOAD : -if (ie_parse_bss_load (&iter,NULL , &bss->utilization, -NULL ) <0 ) +if (ie_parse_bss_load (&iter, &bss->sta_count, + &bss->utilization,NULL ) <0 )l_warn ("Unable to parse BSS Load IE for " MAC ,MAC_STR (bss->addr));else
src/scan.h +1 -0
@@ -67,6 +67,7 @@ struct scan_bss {uint8_t ssid[SSID_MAX_SIZE ];uint8_t ssid_len;uint8_t utilization; +uint16_t sta_count;uint8_t cc[3 ];uint16_t rank;uint64_t time_stamp;
Signature · 1 line
2.34.1
PATCH 6/8 scan: add ranking modifiers for utilization/station count
In reply to James PrestwoodThe utilization rank factor already existed but was very rigid and only checked a few values. This adds the (optional) ability to start applying an exponentially decaying factor to both utilization and station count after some threshold is reached.
This area needs to be re-worked in order to support very highly loaded networks. If a network either doesn't support client balancing or does it poorly its left up to the clients to choose the best BSS possible given all the information available. In these cases connecting to a highly loaded BSS may fail, or result in a disconnect soon after connecting. In these cases its likely better for IWD to choose a slightly lower RSSI/datarate BSS over the conventionally 'best' BSS in order to aid in distributing the network load.
The thresholds are currently optional and not enabled by default but if set they behave as follows:
If the value is above the threshold it is mapped to an integer between 0 and 30. (using a starting range of <value> - 255). This integer is then used to index in the exponential decay table to get a factor between 1 and 0. This factor is then applied to the rank.
Note that as the value increases above the threshold the rank will be increasingly effected, as is expected for an exponential function. These option should be used with care as it may have unintended consequences, especially with very high load networks. i.e. you may see IWD roaming to BSS's with much lower signal if there are high load BSS's nearby.
To maintain the existing behavior if there is no utilization factor set in main.conf the legacy thresholds/factors will be used.
--- src/scan.c | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 86 insertions(+), 7 deletions(-)
src/scan.c +86 -7
@@ -56,6 +56,8 @@static double RANK_2G_FACTOR ;static double RANK_5G_FACTOR ;static double RANK_6G_FACTOR ; +static uint32_t RANK_HIGH_UTILIZATION ; +static uint32_t RANK_HIGH_STATION_COUNT ;static uint32_t SCAN_MAX_INTERVAL ;static uint32_t SCAN_INIT_INTERVAL ;
@@ -1681,10 +1683,77 @@ static struct scan_bss *scan_parse_result(struct l_genl_msg *msg,return bss; } -static void scan_bss_compute_rank (struct scan_bss *bss) +static double scan_legacy_utilization_factor (uint8_t utilization) {static const double RANK_HIGH_UTILIZATION_FACTOR =0.8 ;static const double RANK_LOW_UTILIZATION_FACTOR =1.2 ; + +if (utilization >=192 ) +return RANK_HIGH_UTILIZATION_FACTOR ; +else if (utilization <=63 ) +return RANK_LOW_UTILIZATION_FACTOR ; + +return 1.0 ; +} + +static double scan_get_load_factors (uint8_t utilization,uint16_t sta_count) +{ +double n; +double factor =1.0 ; +/* +* The exponential decay table has 64 entries (0 <= n <= 63) which range +* from 1.0 to 0.28. For the utilization and station count factors we +* likely don't want to adjust the rank so drastically (potentially a +* 78% reduction in the worse case) so cap the index at 30 which equates +* to ~64% at the worst case. +*/ +static const uint8_t LOAD_DECAY_OFFSET =30 ; + +if (!RANK_HIGH_UTILIZATION ) { +/* +* To maintain existing behavior, if the utilization factor is +* unset (default) fall back to the static thresholds and +* factor weights. +*/ + factor =scan_legacy_utilization_factor (utilization); + goto sta_count; + }else if (utilization <RANK_HIGH_UTILIZATION ) + goto sta_count; + +/* Map the utilization threshold -> 255 to rankmod_table indexes */ +if (L_WARN_ON (!util_linear_map (utilization,RANK_HIGH_UTILIZATION , +255 ,0 ,LOAD_DECAY_OFFSET , &n))) + goto sta_count; + + factor =util_exponential_decay (n); + +sta_count: +if (!RANK_HIGH_STATION_COUNT || sta_count <RANK_HIGH_STATION_COUNT ) +return factor; + +/* +* The station count is a uint16 so in theory it could be excessively +* large. In practice APs generally can't handle anywhere near this so +* put a cap at 255. If at some time in the future APs begin to handle +* this level of capacity we could increase this. +* +* TODO: A warning is used here to make this visible. If we see cases +* where this is happening we may need to give this another look. +*/ +if (L_WARN_ON (sta_count >255 )) + sta_count =255 ; + +if (L_WARN_ON (!util_linear_map (sta_count,RANK_HIGH_STATION_COUNT , +255 ,0 ,LOAD_DECAY_OFFSET , &n))) +return factor; + + factor *=util_exponential_decay (n); + +return factor; +} + +static void scan_bss_compute_rank (struct scan_bss *bss) +{static const double RANK_HIGH_SNR_FACTOR =1.2 ;static const double RANK_LOW_SNR_FACTOR =0.8 ;double rank;
@@ -1708,12 +1777,8 @@ static void scan_bss_compute_rank(struct scan_bss *bss) rank *=RANK_6G_FACTOR ;/* Rank loaded APs lower and lightly loaded APs higher */ -if (bss->have_utilization) { -if (bss->utilization >=192 ) - rank *=RANK_HIGH_UTILIZATION_FACTOR ; -else if (bss->utilization <=63 ) - rank *=RANK_LOW_UTILIZATION_FACTOR ; - } +if (bss->have_utilization) + rank *=scan_get_load_factors (bss->utilization, bss->sta_count);if (bss->have_snr) {if (bss->snr <=15 )
@@ -2599,6 +2664,20 @@ static int scan_init(void)if (SCAN_MAX_INTERVAL >UINT16_MAX )SCAN_MAX_INTERVAL =UINT16_MAX ; +if (!l_settings_get_uint (config,"Rank" ,"HighUtilizationThreshold" , + &RANK_HIGH_UTILIZATION )) +RANK_HIGH_UTILIZATION =0 ; + +if (L_WARN_ON (RANK_HIGH_UTILIZATION >255 )) +RANK_HIGH_UTILIZATION =255 ; + +if (!l_settings_get_uint (config,"Rank" ,"HighStationCountThreshold" , + &RANK_HIGH_STATION_COUNT )) +RANK_HIGH_STATION_COUNT =0 ; + +if (L_WARN_ON (RANK_HIGH_STATION_COUNT >255 )) +RANK_HIGH_STATION_COUNT =255 ; +return 0 ; }
Signature · 1 line
2.34.1
PATCH 7/8 doc: document [Rank].HighUtilization/StationCount thresholds
In reply to James Prestwood--- src/iwd.config.rst | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+)
src/iwd.config.rst +22 -0
@@ -341,6 +341,28 @@ autoconnect purposes. A value of 0.0 will disable the 6GHz band and prevent scanning or connecting on those frequencies. + * - HighUtilizationThreshold + - Values: unsigned integer value 0 - 255 (default: **0**, disabled) + + **Warning: This is an experimental feature** + + The BSS utilization threshold at which a negative rank factor begins to + be applied to the BSS. As the load increases for a BSS the ranking factor + decays exponentially, meaning the ranking factor will decrease + exponentially. Setting this can have very drastic effects on the BSS rank + if its utilization is high, use with care. + + * - HighStationCountThreshold + - Values: unsigned integer value 0 - 255 (default: **0**, disabled) + + **Warning: This is an experimental feature** + + The BSS station count threshold at which a negative rank factor begins to + be applied to the BSS. As the station count increases for a BSS the + ranking factor decays exponentially, meaning the ranking factor will + decrease exponentially. Setting this can have very drastic effects on the + BSS rank if its station count is high, use with care. + Scan ----
Signature · 1 line
2.34.1
PATCH 8/8 station: print client count in scan results
In reply to James Prestwood--- src/station.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
src/station.c +2 -1
@@ -425,7 +425,8 @@ static void station_print_scan_bss(const struct scan_bss *bss) ptr +=sprintf (ptr,", snr: %d" , bss->snr);if (bss->have_utilization) - ptr +=sprintf (ptr,", load: %u/255" , bss->utilization); + ptr +=sprintf (ptr,", load: %u/255, clients: %u" , + bss->utilization, bss->sta_count); l_debug("Processing BSS '%s' with SSID: %s, freq: %u, rank: %u, " "strength: %i, data_rate: %u.%u%s",
Signature · 1 line
2.34.1