[PATCH v2 1/4] knownnetworks: pass scan_bss to known_network_add_frequency

[PATCH v2 1/4] knownnetworks: pass scan_bss to known_network_add_frequency

[James Prestwood]

This prepares to store known frequencies sorted by BSS rank.
---
 src/knownnetworks.c | 6 +++---
 src/knownnetworks.h | 3 ++-
 src/network.c       | 6 +++---
 3 files changed, 8 insertions(+), 7 deletions(-)

diff --git a/src/knownnetworks.c b/src/knownnetworks.c
index 04ce74ec..f6284fdc 100644
--- a/src/knownnetworks.c
+++ b/src/knownnetworks.c
@@ -566,7 +566,7 @@ static bool known_frequency_match(const void *a, const void *b)
  * Adds a frequency to the 'known' set of frequencies that this network
  * operates on.  The list is sorted according to most-recently seen
  */
-int known_network_add_frequency(struct network_info *info, uint32_t frequency)
+int known_network_add_frequency(struct network_info *info, struct scan_bss *bss)
 {
 	struct known_frequency *known_freq;
 
@@ -574,10 +574,10 @@ int known_network_add_frequency(struct network_info *info, uint32_t frequency)
 		info->known_frequencies = l_queue_new();
 
 	known_freq = l_queue_remove_if(info->known_frequencies,
-					known_frequency_match, &frequency);
+					known_frequency_match, &bss->frequency);
 	if (!known_freq) {
 		known_freq = l_new(struct known_frequency, 1);
-		known_freq->frequency = frequency;
+		known_freq->frequency = bss->frequency;
 	}
 
 	l_queue_push_head(info->known_frequencies, known_freq);
diff --git a/src/knownnetworks.h b/src/knownnetworks.h
index e8ffac0b..9f81e308 100644
--- a/src/knownnetworks.h
+++ b/src/knownnetworks.h
@@ -114,7 +114,8 @@ struct network_info *known_networks_find(const char *ssid,
 
 struct scan_freq_set *known_networks_get_recent_frequencies(
 						uint8_t num_networks_tosearch);
-int known_network_add_frequency(struct network_info *info, uint32_t frequency);
+int known_network_add_frequency(struct network_info *info,
+				struct scan_bss *bss);
 void known_network_frequency_sync(struct network_info *info);
 
 uint32_t known_networks_watch_add(known_networks_watch_func_t func,
diff --git a/src/network.c b/src/network.c
index 4723334e..81315746 100644
--- a/src/network.c
+++ b/src/network.c
@@ -807,7 +807,7 @@ static void add_known_frequency(void *data, void *user_data)
 	struct scan_bss *bss = data;
 	struct network_info *info = user_data;
 
-	known_network_add_frequency(info, bss->frequency);
+	known_network_add_frequency(info, bss);
 }
 
 void network_set_info(struct network *network, struct network_info *info)
@@ -1094,7 +1094,7 @@ bool network_bss_add(struct network *network, struct scan_bss *bss)
 		return false;
 
 	if (network->info)
-		known_network_add_frequency(network->info, bss->frequency);
+		known_network_add_frequency(network->info, bss);
 
 	/* Done if BSS is not HS20 or we already have network_info set */
 	if (!bss->hs20_capable)
@@ -1131,7 +1131,7 @@ bool network_bss_update(struct network *network, struct scan_bss *bss)
 
 	/* Sync frequency for already known networks */
 	if (network->info) {
-		known_network_add_frequency(network->info, bss->frequency);
+		known_network_add_frequency(network->info, bss);
 		known_network_frequency_sync(network->info);
 	}
 
-- 
2.34.1

[PATCH v2 2/4] knownnetworks: sort known frequencies by BSS rank

[James Prestwood]

Currently a quick scan uses the entire known frequency list so
ordering really doesn't matter but improvements will be made here
to make quick scans "quicker" for large network deployments (with
many known frequencies).

To prepare for this the known frequency list has been changed to
be sorted by BSS rank rather than most recently seen. This makes
a lot more sense because IWD should prefer to scan frequencies
that had higher ranked BSS's, not just frequencies that were scanned
last on the most recent scan.

As far as the disk sync goes the ranking is not included, but
ordering is. This really isn't a limitation because when IWD starts
up there isn't any guarantee its in the same physical location so
old scan ranks are likely not valid anymore. The first set of scans
will begin replacing the frequencies loaded from disk.
---
 src/knownnetworks.c | 16 ++++++++++++++--
 src/knownnetworks.h |  1 +
 2 files changed, 15 insertions(+), 2 deletions(-)

diff --git a/src/knownnetworks.c b/src/knownnetworks.c
index f6284fdc..6e549e02 100644
--- a/src/knownnetworks.c
+++ b/src/knownnetworks.c
@@ -562,9 +562,19 @@ static bool known_frequency_match(const void *a, const void *b)
 	return known_freq->frequency == *frequency;
 }
 
+static int known_frequency_compare(const void *a, const void *b,
+					void *user_data)
+{
+	const struct known_frequency *kf_a = a;
+	const struct known_frequency *kf_b = b;
+
+	return (kf_b->rank > kf_a->rank) ? 1 : -1;
+}
+
 /*
  * Adds a frequency to the 'known' set of frequencies that this network
- * operates on.  The list is sorted according to most-recently seen
+ * operates on.  The list is sorted according to the rank of the BSS on that
+ * frequency.
  */
 int known_network_add_frequency(struct network_info *info, struct scan_bss *bss)
 {
@@ -578,9 +588,11 @@ int known_network_add_frequency(struct network_info *info, struct scan_bss *bss)
 	if (!known_freq) {
 		known_freq = l_new(struct known_frequency, 1);
 		known_freq->frequency = bss->frequency;
+		known_freq->rank = bss->rank;
 	}
 
-	l_queue_push_head(info->known_frequencies, known_freq);
+	l_queue_insert(info->known_frequencies, known_freq,
+			known_frequency_compare, NULL);
 
 	return 0;
 }
diff --git a/src/knownnetworks.h b/src/knownnetworks.h
index 9f81e308..36106501 100644
--- a/src/knownnetworks.h
+++ b/src/knownnetworks.h
@@ -96,6 +96,7 @@ typedef void (*known_networks_destroy_func_t)(void *user_data);
 
 struct known_frequency {
 	uint32_t frequency;
+	uint16_t rank;
 };
 
 void __network_config_parse(const struct l_settings *settings,
-- 
2.34.1

[PATCH v2 3/4] station: knownnetworks: limit quick scans to 5 freqs per network

[James Prestwood]

In very large network deployments there could be a vast amount of APs
which could create a large known frequency list after some time once
all the APs are seen in scan results. This then increases the quick
scan time significantly, in the very worst case (but unlikely) just
as long as a full scan.

To help with this support in knownnetworks was added to limit the
number of frequencies per network. Station will now only get 5
recent frequencies per network making the maximum frequencies 25
in the worst case (~2.5s scan).

The magic values are now defines, and the recent roam frequencies
was also changed to use this define as well.
---
 src/knownnetworks.c |  9 ++++++---
 src/knownnetworks.h |  3 ++-
 src/station.c       | 10 ++++++++--
 3 files changed, 16 insertions(+), 6 deletions(-)

diff --git a/src/knownnetworks.c b/src/knownnetworks.c
index 6e549e02..fe0fce09 100644
--- a/src/knownnetworks.c
+++ b/src/knownnetworks.c
@@ -518,7 +518,8 @@ struct network_info *known_networks_find(const char *ssid,
 }
 
 struct scan_freq_set *known_networks_get_recent_frequencies(
-						uint8_t num_networks_tosearch)
+						uint8_t num_networks_tosearch,
+						uint8_t freqs_per_network)
 {
 	/*
 	 * This search function assumes that the known networks are always
@@ -530,7 +531,7 @@ struct scan_freq_set *known_networks_get_recent_frequencies(
 	const struct l_queue_entry *freq_entry;
 	struct scan_freq_set *set;
 
-	if (!num_networks_tosearch)
+	if (!num_networks_tosearch || !freqs_per_network)
 		return NULL;
 
 	set = scan_freq_set_new();
@@ -540,10 +541,12 @@ struct scan_freq_set *known_networks_get_recent_frequencies(
 				network_entry = network_entry->next,
 						num_networks_tosearch--) {
 		const struct network_info *network = network_entry->data;
+		uint8_t freqs_found = 0;
 
 		for (freq_entry = l_queue_get_entries(
 						network->known_frequencies);
-				freq_entry; freq_entry = freq_entry->next) {
+				freq_entry && freqs_found < freqs_per_network;
+				freq_entry = freq_entry->next, freqs_found++) {
 			const struct known_frequency *known_freq =
 							freq_entry->data;
 
diff --git a/src/knownnetworks.h b/src/knownnetworks.h
index 36106501..108f334e 100644
--- a/src/knownnetworks.h
+++ b/src/knownnetworks.h
@@ -114,7 +114,8 @@ struct network_info *known_networks_find(const char *ssid,
 						enum security security);
 
 struct scan_freq_set *known_networks_get_recent_frequencies(
-						uint8_t num_networks_tosearch);
+						uint8_t num_networks_tosearch,
+						uint8_t freqs_per_network);
 int known_network_add_frequency(struct network_info *info,
 				struct scan_bss *bss);
 void known_network_frequency_sync(struct network_info *info);
diff --git a/src/station.c b/src/station.c
index a6442d3e..1b34b956 100644
--- a/src/station.c
+++ b/src/station.c
@@ -64,6 +64,9 @@
 #include "src/eap-tls-common.h"
 #include "src/storage.h"
 
+#define STATION_RECENT_NETWORK_LIMIT	5
+#define STATION_RECENT_FREQS_LIMIT	5
+
 static struct l_queue *station_list;
 static uint32_t netdev_watch;
 static uint32_t mfp_setting;
@@ -1434,7 +1437,9 @@ static int station_quick_scan_trigger(struct station *station)
 		return -EAGAIN;
 	}
 
-	known_freq_set = known_networks_get_recent_frequencies(5);
+	known_freq_set = known_networks_get_recent_frequencies(
+						STATION_RECENT_NETWORK_LIMIT,
+						STATION_RECENT_FREQS_LIMIT);
 	if (!known_freq_set)
 		return -ENODATA;
 
@@ -2757,7 +2762,8 @@ static int station_roam_scan_known_freqs(struct station *station)
 	const struct network_info *info = network_get_info(
 						station->connected_network);
 	struct scan_freq_set *freqs = network_info_get_roam_frequencies(info,
-					station->connected_bss->frequency, 5);
+					station->connected_bss->frequency,
+					STATION_RECENT_FREQS_LIMIT);
 	int r = -ENODATA;
 
 	if (!freqs)
-- 
2.34.1

[PATCH v2 4/4] auto-t: add test for known frequency sorting/maximum

[James Prestwood]

Modify the existing frequency test to check that the ordering
lines up with the ranking of the BSS.

Add a test to check that quick scans limit the number of known
frequencies.
---
 autotests/testKnownNetworks/frequency_test.py | 110 ++++++++++++++++--
 autotests/testKnownNetworks/hw.conf           |   1 +
 2 files changed, 102 insertions(+), 9 deletions(-)

diff --git a/autotests/testKnownNetworks/frequency_test.py b/autotests/testKnownNetworks/frequency_test.py
index 83e51c06..c2fd1290 100644
--- a/autotests/testKnownNetworks/frequency_test.py
+++ b/autotests/testKnownNetworks/frequency_test.py
@@ -4,17 +4,15 @@ import unittest
 import sys
 
 sys.path.append('../util')
-import iwd
 from iwd import IWD
 from iwd import PSKAgent
-from iwd import NetworkType
-import testutil
+from hwsim import Hwsim
 import os
 from configparser import ConfigParser
 
 class Test(unittest.TestCase):
     def connect_network(self, wd, device, network):
-        ordered_network = device.get_ordered_network(network)
+        ordered_network = device.get_ordered_network(network, full_scan=True)
 
         condition = 'not obj.connected'
         wd.wait_for_object_condition(ordered_network.network_object, condition)
@@ -30,7 +28,7 @@ class Test(unittest.TestCase):
         wd.wait_for_object_condition(ordered_network.network_object, condition)
 
     def test_connection_success(self):
-        wd = IWD(True, '/tmp')
+        wd = self.wd
 
         psk_agent = PSKAgent("secret123")
         wd.register_psk_agent(psk_agent)
@@ -38,6 +36,11 @@ class Test(unittest.TestCase):
         devices = wd.list_devices(1)
         device = devices[0]
 
+
+        # Set the signals so that the 2.4GHz ranking will be higher
+        self.ssidccmp_2g_rule.signal = -2000
+        self.ssidccmp_5g_rule.signal = -8000
+
         #
         # Connect to the PSK network, then Hotspot so IWD creates 2 entries in
         # the known frequency file.
@@ -75,8 +78,10 @@ class Test(unittest.TestCase):
         #
         self.assertIsNotNone(psk_freqs)
         self.assertIsNotNone(psk_uuid)
-        self.assertIn('5180', psk_freqs)
-        self.assertIn('2412', psk_freqs)
+
+        # The 2.4GHz frequency should come first, as it was ranked higher
+        self.assertEqual('2412', psk_freqs[0])
+        self.assertEqual('5180', psk_freqs[1])
 
         self.assertIsNotNone(hs20_freqs)
         self.assertIsNotNone(hs20_uuid)
@@ -92,6 +97,10 @@ class Test(unittest.TestCase):
         psk_agent = PSKAgent("secret123")
         wd.register_psk_agent(psk_agent)
 
+        # Now set the signals so that the 5GHz ranking will be higher
+        self.ssidccmp_2g_rule.signal = -8000
+        self.ssidccmp_5g_rule.signal = -2000
+
         #
         # Reconnect, this should generate a completely new UUID since we
         # previously forgot the network.
@@ -120,8 +129,78 @@ class Test(unittest.TestCase):
         self.assertIsNotNone(psk_freqs)
         self.assertIsNotNone(psk_uuid2)
         self.assertNotEqual(psk_uuid, psk_uuid2)
-        self.assertIn('5180', psk_freqs)
-        self.assertIn('2412', psk_freqs)
+        # Now the 5GHz frequency should be first
+        self.assertEqual('5180', psk_freqs[0])
+        self.assertEqual('2412', psk_freqs[1])
+
+    def test_maximum_frequencies(self):
+        psk_agent = PSKAgent("secret123")
+        self.wd.register_psk_agent(psk_agent)
+
+        devices = self.wd.list_devices(1)
+        device = devices[0]
+
+        # Connect and generate a known frequencies file
+        self.connect_network(self.wd, device, 'ssidCCMP')
+
+        self.wd.unregister_psk_agent(psk_agent)
+
+        #
+        # Rewrite the known frequencies file to move the valid network
+        # frequencies to the end, past the maximum for a quick scan
+        #
+        config = ConfigParser()
+        config.read('/tmp/iwd/.known_network.freq')
+        for s in config.sections():
+            if os.path.basename(config[s]['name']) == 'ssidCCMP.psk':
+                config.set(s, 'list', "2417 2422 2427 2432 2437 2442 2447 2452 2457 2462 2467 2472 2484 2412 5180")
+                break
+
+        self.wd.stop()
+
+        with open('/tmp/iwd/.known_network.freq', 'w') as f:
+            config.write(f)
+
+        self.wd = IWD(True)
+
+        devices = self.wd.list_devices(1)
+        device = devices[0]
+
+        device.autoconnect = True
+
+        device.wait_for_event("autoconnect_quick")
+
+        condition = "obj.scanning == True"
+        self.wd.wait_for_object_condition(device, condition)
+
+        condition = "obj.scanning == False"
+        self.wd.wait_for_object_condition(device, condition)
+
+        #
+        # Check that the quick scan didn't return any results
+        #
+        with self.assertRaises(Exception):
+            device.get_ordered_network("ssidCCMP", scan_if_needed=False)
+
+        device.wait_for_event("autoconnect_full")
+
+        condition = "obj.scanning == True"
+        self.wd.wait_for_object_condition(device, condition)
+
+        condition = "obj.scanning == False"
+        self.wd.wait_for_object_condition(device, condition)
+
+        #
+        # The full scan should now see the network
+        #
+        device.get_ordered_network("ssidCCMP", scan_if_needed=False)
+
+    def setUp(self):
+        self.wd = IWD(True)
+
+    def tearDown(self):
+        self.wd.stop()
+        self.wd = None
 
     @classmethod
     def setUpClass(cls):
@@ -129,10 +208,23 @@ class Test(unittest.TestCase):
         conf = '[General]\nDisableANQP=0\n'
         os.system('echo "%s" > /tmp/main.conf' % conf)
 
+        hwsim = Hwsim()
+
+        cls.ssidccmp_2g_rule = hwsim.rules.create()
+        cls.ssidccmp_2g_rule.source = hwsim.get_radio('rad1').addresses[0]
+        cls.ssidccmp_2g_rule.enabled = True
+
+        cls.ssidccmp_5g_rule = hwsim.rules.create()
+        cls.ssidccmp_5g_rule.source = hwsim.get_radio('rad2').addresses[0]
+        cls.ssidccmp_5g_rule.enabled = True
+
     @classmethod
     def tearDownClass(cls):
         IWD.clear_storage()
         os.remove('/tmp/main.conf')
 
+        cls.ssidccmp_2g_rule.remove()
+        cls.ssidccmp_5g_rule.remove()
+
 if __name__ == '__main__':
     unittest.main(exit=True)
diff --git a/autotests/testKnownNetworks/hw.conf b/autotests/testKnownNetworks/hw.conf
index 8a7ef73a..f68b63a5 100644
--- a/autotests/testKnownNetworks/hw.conf
+++ b/autotests/testKnownNetworks/hw.conf
@@ -2,6 +2,7 @@
 num_radios=5
 start_iwd=0
 reg_domain=US
+hwsim_medium=yes
 
 [HOSTAPD]
 rad0=ssidNew.conf
-- 
2.34.1

Re: [PATCH v2 2/4] knownnetworks: sort known frequencies by BSS rank

[Denis Kenzior]

Hi James,

On 1/24/24 07:39, James Prestwood wrote:
> Currently a quick scan uses the entire known frequency list so
> ordering really doesn't matter but improvements will be made here
> to make quick scans "quicker" for large network deployments (with
> many known frequencies).
> 
> To prepare for this the known frequency list has been changed to
> be sorted by BSS rank rather than most recently seen. This makes
> a lot more sense because IWD should prefer to scan frequencies
> that had higher ranked BSS's, not just frequencies that were scanned
> last on the most recent scan.

Interesting.  I definitely agree with the argument for treating frequencies with 
higher-ranked candidates as preferred, but I'm not sure that directly basing the 
frequency preference on the bss rank is the right thing to do.  A client might 
start right under an AP, ranking it quite high, but then rapidly move away where 
no APs exist on this frequency.  So you end up always scanning the original AP's 
frequency.  Some sort of temporal rank decay would be needed?

Perhaps an easier way to accomplish this would be to add known frequencies in 
reverse bss->rank sorted order.  That way last seen frequency with best ranked 
BSS would be first?

Do note however that the quick scan approach is really meant for smallish 
networks, to cut down scanning time when moving between Home / Office location 
for example.  It works surprisingly well, but might not be appropriate for rapid 
roaming in a large network.

> 
> As far as the disk sync goes the ranking is not included, but
> ordering is. This really isn't a limitation because when IWD starts
> up there isn't any guarantee its in the same physical location so
> old scan ranks are likely not valid anymore. The first set of scans
> will begin replacing the frequencies loaded from disk.
> ---
>   src/knownnetworks.c | 16 ++++++++++++++--
>   src/knownnetworks.h |  1 +
>   2 files changed, 15 insertions(+), 2 deletions(-)
> 

Regards,
-Denis

Re: [PATCH v2 1/4] knownnetworks: pass scan_bss to known_network_add_frequency

[Denis Kenzior]

Hi James,

On 1/24/24 07:39, James Prestwood wrote:
> This prepares to store known frequencies sorted by BSS rank.
> ---
>   src/knownnetworks.c | 6 +++---
>   src/knownnetworks.h | 3 ++-
>   src/network.c       | 6 +++---
>   3 files changed, 8 insertions(+), 7 deletions(-)
> 

I'm actually fine with this patch, but small nit:

> diff --git a/src/knownnetworks.c b/src/knownnetworks.c
> index 04ce74ec..f6284fdc 100644
> --- a/src/knownnetworks.c
> +++ b/src/knownnetworks.c
> @@ -566,7 +566,7 @@ static bool known_frequency_match(const void *a, const void *b)
>    * Adds a frequency to the 'known' set of frequencies that this network
>    * operates on.  The list is sorted according to most-recently seen
>    */
> -int known_network_add_frequency(struct network_info *info, uint32_t frequency)
> +int known_network_add_frequency(struct network_info *info, struct scan_bss *bss)

const struct scan_bss ?

>   {
>   	struct known_frequency *known_freq;
>   

Regards,
-Denis

Re: [PATCH v2 3/4] station: knownnetworks: limit quick scans to 5 freqs per network

[Denis Kenzior]

Hi James,

On 1/24/24 07:40, James Prestwood wrote:
> In very large network deployments there could be a vast amount of APs
> which could create a large known frequency list after some time once
> all the APs are seen in scan results. This then increases the quick
> scan time significantly, in the very worst case (but unlikely) just
> as long as a full scan.
> 
> To help with this support in knownnetworks was added to limit the
> number of frequencies per network. Station will now only get 5
> recent frequencies per network making the maximum frequencies 25
> in the worst case (~2.5s scan).
> 
> The magic values are now defines, and the recent roam frequencies
> was also changed to use this define as well.

Yep, I like it.

> ---
>   src/knownnetworks.c |  9 ++++++---
>   src/knownnetworks.h |  3 ++-
>   src/station.c       | 10 ++++++++--
>   3 files changed, 16 insertions(+), 6 deletions(-)
> 
> diff --git a/src/knownnetworks.c b/src/knownnetworks.c
> index 6e549e02..fe0fce09 100644
> --- a/src/knownnetworks.c
> +++ b/src/knownnetworks.c
> @@ -518,7 +518,8 @@ struct network_info *known_networks_find(const char *ssid,
>   }
>   
>   struct scan_freq_set *known_networks_get_recent_frequencies(
> -						uint8_t num_networks_tosearch)
> +						uint8_t num_networks_tosearch,
> +						uint8_t freqs_per_network)
>   {
>   	/*
>   	 * This search function assumes that the known networks are always
> @@ -530,7 +531,7 @@ struct scan_freq_set *known_networks_get_recent_frequencies(
>   	const struct l_queue_entry *freq_entry;
>   	struct scan_freq_set *set;
>   
> -	if (!num_networks_tosearch)
> +	if (!num_networks_tosearch || !freqs_per_network)
>   		return NULL;
>   
>   	set = scan_freq_set_new();
> @@ -540,10 +541,12 @@ struct scan_freq_set *known_networks_get_recent_frequencies(
>   				network_entry = network_entry->next,
>   						num_networks_tosearch--) {
>   		const struct network_info *network = network_entry->data;
> +		uint8_t freqs_found = 0;
>   
>   		for (freq_entry = l_queue_get_entries(
>   						network->known_frequencies);
> -				freq_entry; freq_entry = freq_entry->next) {
> +				freq_entry && freqs_found < freqs_per_network;
> +				freq_entry = freq_entry->next, freqs_found++) {

This is getting a bit unreadable.  Maybe a while loop makes this look better?

freq_entry = l_queue_get_entries();

while (freq_entry && freqs_found < freq_per_network) {
	...
	freqs_found += 1;
	freq_entry = freq_entry->next;
}

>   			const struct known_frequency *known_freq =
>   							freq_entry->data;
>   

Regards,
-Denis

Re: [PATCH v2 2/4] knownnetworks: sort known frequencies by BSS rank

[James Prestwood]

Hi Denis,

On 1/24/24 10:10 AM, Denis Kenzior wrote:
> Hi James,
>
> On 1/24/24 07:39, James Prestwood wrote:
>> Currently a quick scan uses the entire known frequency list so
>> ordering really doesn't matter but improvements will be made here
>> to make quick scans "quicker" for large network deployments (with
>> many known frequencies).
>>
>> To prepare for this the known frequency list has been changed to
>> be sorted by BSS rank rather than most recently seen. This makes
>> a lot more sense because IWD should prefer to scan frequencies
>> that had higher ranked BSS's, not just frequencies that were scanned
>> last on the most recent scan.
>
> Interesting.  I definitely agree with the argument for treating 
> frequencies with higher-ranked candidates as preferred, but I'm not 
> sure that directly basing the frequency preference on the bss rank is 
> the right thing to do.  A client might start right under an AP, 
> ranking it quite high, but then rapidly move away where no APs exist 
> on this frequency.  So you end up always scanning the original AP's 
> frequency.  Some sort of temporal rank decay would be needed?
Yeah, I see your point...
>
> Perhaps an easier way to accomplish this would be to add known 
> frequencies in reverse bss->rank sorted order.  That way last seen 
> frequency with best ranked BSS would be first?

I'm not sure I understand, how would this be any different than just 
reversing the list I already have? Or are you saying sort by both rank 
and last seen? Essentially have the list segmented into chunks of 
frequencies found with prior scans:

[Last Scan] [N - 1] [N - 2] [ etc ]

And if a duplicate is found, move it to the front, sorted by rank?

>
> Do note however that the quick scan approach is really meant for 
> smallish networks, to cut down scanning time when moving between Home 
> / Office location for example.  It works surprisingly well, but might 
> not be appropriate for rapid roaming in a large network.
Exactly, e.g. with 50 APs (assuming you've seen them all) a "quick" scan 
takes 5 seconds.
>
>>
>> As far as the disk sync goes the ranking is not included, but
>> ordering is. This really isn't a limitation because when IWD starts
>> up there isn't any guarantee its in the same physical location so
>> old scan ranks are likely not valid anymore. The first set of scans
>> will begin replacing the frequencies loaded from disk.
>> ---
>>   src/knownnetworks.c | 16 ++++++++++++++--
>>   src/knownnetworks.h |  1 +
>>   2 files changed, 15 insertions(+), 2 deletions(-)
>>
>
> Regards,
> -Denis
>

Re: [PATCH v2 2/4] knownnetworks: sort known frequencies by BSS rank

[Denis Kenzior]

Hi James,

>> Perhaps an easier way to accomplish this would be to add known frequencies in 
>> reverse bss->rank sorted order.  That way last seen frequency with best ranked 
>> BSS would be first?
> 
> I'm not sure I understand, how would this be any different than just reversing

Well, right now we maintain the least recently seen frequency list in a very 
simple way:

- When scan results become available
	- Walk the result list (which is sorted by bss_rank?)
	- Add each result's frequency to the frequency cache
		- Remove any matching entry in the cache
		- Add it to head

Since the result list is sorted, the top entry in the frequency cache is the 
least ranked.  This doesn't matter for small networks since there would only be 
a couple results.

What we should do is to add the frequencies to the frequency cache in reverse 
order.  That way the highest ranked bss is at the top of the frequency cache.

Hope that made sense.
  Regards,
-Denis

Re: [PATCH v2 2/4] knownnetworks: sort known frequencies by BSS rank

[James Prestwood]

On 1/24/24 10:44 AM, Denis Kenzior wrote:
> Hi James,
>
>>> Perhaps an easier way to accomplish this would be to add known 
>>> frequencies in reverse bss->rank sorted order.  That way last seen 
>>> frequency with best ranked BSS would be first?
>>
>> I'm not sure I understand, how would this be any different than just 
>> reversing
>
> Well, right now we maintain the least recently seen frequency list in 
> a very simple way:
>
> - When scan results become available
>     - Walk the result list (which is sorted by bss_rank?)
>     - Add each result's frequency to the frequency cache
>         - Remove any matching entry in the cache
>         - Add it to head
>
> Since the result list is sorted, the top entry in the frequency cache 
> is the least ranked.  This doesn't matter for small networks since 
> there would only be a couple results.
>
> What we should do is to add the frequencies to the frequency cache in 
> reverse order.  That way the highest ranked bss is at the top of the 
> frequency cache.

Oh I see, I didn't realize the list was already sorted since its coming 
from network->bss_list. But wouldn't we have the same problem here? Old 
frequencies with a high rank would remain at the front unless they were 
seen by a recent scan. So if you saw a really high ranked AP once then 
never again it would always stay at the front.

Another thing I didn't consider is multiple BSS's on the same frequency :)

Maybe introducing a last seen time would help, though that adds even 
more complication.

>
> Hope that made sense.
>  Regards,
> -Denis
>

Re: [PATCH v2 2/4] knownnetworks: sort known frequencies by BSS rank

[Denis Kenzior]

Hi James,

On 1/24/24 12:55, James Prestwood wrote:
> 
> On 1/24/24 10:44 AM, Denis Kenzior wrote:
>> Hi James,
>>
>>>> Perhaps an easier way to accomplish this would be to add known frequencies 
>>>> in reverse bss->rank sorted order.  That way last seen frequency with best 
>>>> ranked BSS would be first?
>>>
>>> I'm not sure I understand, how would this be any different than just reversing
>>
>> Well, right now we maintain the least recently seen frequency list in a very 
>> simple way:
>>
>> - When scan results become available
>>     - Walk the result list (which is sorted by bss_rank?)
>>     - Add each result's frequency to the frequency cache
>>         - Remove any matching entry in the cache
>>         - Add it to head
>>
>> Since the result list is sorted, the top entry in the frequency cache is the 
>> least ranked.  This doesn't matter for small networks since there would only 
>> be a couple results.
>>
>> What we should do is to add the frequencies to the frequency cache in reverse 
>> order.  That way the highest ranked bss is at the top of the frequency cache.
> 
> Oh I see, I didn't realize the list was already sorted since its coming from 
> network->bss_list. But wouldn't we have the same problem here? Old frequencies 

There are a few paths.  One if network becoming promoted from unknown -> known, 
one for scan results being reported.  But in all or most cases the order is 
predetermined and would be by bss rank.

> with a high rank would remain at the front unless they were seen by a recent 

No, because each time the frequency cache is updated, new entries are put at the 
top of the list.  This automatically pushes older (as in least recently seen 
order) entries further down.

> scan. So if you saw a really high ranked AP once then never again it would 
> always stay at the front.

Nope.  Not in the current used implementation.

> 
> Another thing I didn't consider is multiple BSS's on the same frequency :)

This is generally not a problem since frequencies are stored per SSID, so for 
well planned networks you wouldn't have this.  But yes, this possibility is 
something you need to take into account.  My suggestion would still handle this 
nicely.

> 
> Maybe introducing a last seen time would help, though that adds even more 
> complication.

Yep.  Only reason to do so would be for serialization to disk I think.

Regards,
-Denis

Re: [PATCH v2 2/4] knownnetworks: sort known frequencies by BSS rank

[James Prestwood]

Hi Denis,

On 1/24/24 11:06 AM, Denis Kenzior wrote:
> Hi James,
>
> On 1/24/24 12:55, James Prestwood wrote:
>>
>> On 1/24/24 10:44 AM, Denis Kenzior wrote:
>>> Hi James,
>>>
>>>>> Perhaps an easier way to accomplish this would be to add known 
>>>>> frequencies in reverse bss->rank sorted order.  That way last seen 
>>>>> frequency with best ranked BSS would be first?
>>>>
>>>> I'm not sure I understand, how would this be any different than 
>>>> just reversing
>>>
>>> Well, right now we maintain the least recently seen frequency list 
>>> in a very simple way:
>>>
>>> - When scan results become available
>>>     - Walk the result list (which is sorted by bss_rank?)
>>>     - Add each result's frequency to the frequency cache
>>>         - Remove any matching entry in the cache
>>>         - Add it to head
>>>
>>> Since the result list is sorted, the top entry in the frequency 
>>> cache is the least ranked.  This doesn't matter for small networks 
>>> since there would only be a couple results.
>>>
>>> What we should do is to add the frequencies to the frequency cache 
>>> in reverse order.  That way the highest ranked bss is at the top of 
>>> the frequency cache.

Ok I understand what your getting at now, but providing the list in 
reverse order is somewhat problematic. The majority of additions are 
going to be from station's can results, via network_bss_add(). We 
_could_ reverse the BSS list in station but that seems like an expensive 
operation for each scan, and I really don't want to muck with that code. 
The only somewhat simple place to reverse the list is when a known 
network is added. But again its expensive.

To avoid refactoring elsewhere, I think the only way would be to 
timestamp entries (based on bss->time_stamp) and sort by both rank and 
timestamp. We could also limit the list to e.g. 5 values if we wanted to 
avoid storing a ton of u64's in memory.

Thanks,

James

>>
> Regards,
> -Denis

Re: [PATCH v2 2/4] knownnetworks: sort known frequencies by BSS rank

[Denis Kenzior]

Hi James,

On 1/25/24 07:21, James Prestwood wrote:
> Hi Denis,
> 
> On 1/24/24 11:06 AM, Denis Kenzior wrote:
>> Hi James,
>>
>> On 1/24/24 12:55, James Prestwood wrote:
>>>
>>> On 1/24/24 10:44 AM, Denis Kenzior wrote:
>>>> Hi James,
>>>>
>>>>>> Perhaps an easier way to accomplish this would be to add known frequencies 
>>>>>> in reverse bss->rank sorted order.  That way last seen frequency with best 
>>>>>> ranked BSS would be first?
>>>>>
>>>>> I'm not sure I understand, how would this be any different than just reversing
>>>>
>>>> Well, right now we maintain the least recently seen frequency list in a very 
>>>> simple way:
>>>>
>>>> - When scan results become available
>>>>     - Walk the result list (which is sorted by bss_rank?)
>>>>     - Add each result's frequency to the frequency cache
>>>>         - Remove any matching entry in the cache
>>>>         - Add it to head
>>>>
>>>> Since the result list is sorted, the top entry in the frequency cache is the 
>>>> least ranked.  This doesn't matter for small networks since there would only 
>>>> be a couple results.
>>>>
>>>> What we should do is to add the frequencies to the frequency cache in 
>>>> reverse order.  That way the highest ranked bss is at the top of the 
>>>> frequency cache.
> 
> Ok I understand what your getting at now, but providing the list in reverse 
> order is somewhat problematic. The majority of additions are going to be from 
> station's can results, via network_bss_add(). We _could_ reverse the BSS list in 
> station but that seems like an expensive operation for each scan, and I really 

Nah, it is a trivial operation.  In fact, l_queue_reverse() already exists.

What you can also do is remove the known frequency update from network_bss_add() 
and have station manage it explicitly.  You can then do all sorts of fancy 
things in station_set_scan_results().  Couple of examples.

example 1
   - allocate array of l_queue_size(new_bss_list) pairs: [network, frequency]
   - After calling station_add_seen_bss, jot down network/frequency into the array
   - Run another loop after to add the frequencies in reverse bss rank order

example 2:
   - Allocate array of l_queue_size(new_bss_list) struct scan_bss pointers
   - run qsort and sort the entries however you want (say by bss->time_stamp)

> don't want to muck with that code. The only somewhat simple place to reverse the 
> list is when a known network is added. But again its expensive.
> 
> To avoid refactoring elsewhere, I think the only way would be to timestamp 
> entries (based on bss->time_stamp) and sort by both rank and timestamp. We could 
> also limit the list to e.g. 5 values if we wanted to avoid storing a ton of 
> u64's in memory.
> 

See above.  I'm really not sure that sorting by timestamp AND rank will do 
anything.  If the driver does things properly then it will report 
NL80211_BSS_LAST_SEEN_BOOTTIME value, so all entries will have a unique time_stamp.

Another thing I thought of is that we probably should be updating the known 
frequency list based on any neighbor reports we obtain.  Just in case we get 
disconnected for whatever reason before we attempt to roam.

Regards,
-Denis