[PATCH v3 1/4] network: add network_update_known_frequencies

[PATCH v3 1/4] network: add network_update_known_frequencies

[James Prestwood]

In order to support an ordered list of known frequencies the list
should be in order of last seen BSS frequencies with the highest
ranked ones first. To accomplish this without adding a lot of
complexity the frequencies can be pushed into the list as long as
they are pushed in reverse rank order (lowest rank first, highest
last). This ensures that very high ranked BSS's will always get
superseded by subsequent scans if not seen.

This adds a new network API to update the known frequency list
based on the current newtork->bss_list. This assumes that station
always wipes the BSS list on scans and populates with only fresh
BSS entries. After the scan this API can be called and it will
reverse the list, then add each frequency.
---
 src/network.c | 40 ++++++++++++++++++++++++++++------------
 src/network.h |  2 ++
 2 files changed, 30 insertions(+), 12 deletions(-)

v4:
 * Added an API to do the insertion once all the BSS's have been added
   to the network object.
 * I'm also ok adding something to ELL like:
   l_queue_new_reverse(list);

   The current reverse is in-place, so I cant really use it unless I
   wanted to reverse twice to get it back to decending order.

diff --git a/src/network.c b/src/network.c
index 4723334e..287e2be0 100644
--- a/src/network.c
+++ b/src/network.c
@@ -802,21 +802,13 @@ const struct network_info *network_get_info(const struct network *network)
 	return network->info;
 }
 
-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);
-}
-
 void network_set_info(struct network *network, struct network_info *info)
 {
 	if (info) {
 		network->info = info;
 		network->info->seen_count++;
 
-		l_queue_foreach(network->bss_list, add_known_frequency, info);
+		network_update_known_frequencies(network);
 	} else {
 		network->info->seen_count--;
 		network->info = NULL;
@@ -1087,15 +1079,39 @@ static bool match_hotspot_network(const struct network_info *info,
 	return true;
 }
 
+bool network_update_known_frequencies(struct network *network)
+{
+	const struct l_queue_entry *e;
+	struct l_queue *reversed;
+
+	if (!network->info)
+		return false;
+
+	reversed = l_queue_new();
+
+	for (e = l_queue_get_entries(network->bss_list); e; e = e->next) {
+		struct scan_bss *bss = e->data;
+
+		l_queue_push_head(reversed, bss);
+	}
+
+	for (e = l_queue_get_entries(reversed); e; e = e->next) {
+		struct scan_bss *bss = e->data;
+
+		known_network_add_frequency(network->info, bss->frequency);
+	}
+
+	l_queue_destroy(reversed, NULL);
+
+	return true;
+}
+
 bool network_bss_add(struct network *network, struct scan_bss *bss)
 {
 	if (!l_queue_insert(network->bss_list, bss, scan_bss_rank_compare,
 									NULL))
 		return false;
 
-	if (network->info)
-		known_network_add_frequency(network->info, bss->frequency);
-
 	/* Done if BSS is not HS20 or we already have network_info set */
 	if (!bss->hs20_capable)
 		return true;
diff --git a/src/network.h b/src/network.h
index f29649f7..ea619f3f 100644
--- a/src/network.h
+++ b/src/network.h
@@ -61,6 +61,8 @@ void network_set_info(struct network *network, struct network_info *info);
 void network_set_force_default_owe_group(struct network *network);
 bool network_get_force_default_owe_group(struct network *network);
 
+bool network_update_known_frequencies(struct network *network);
+
 int network_can_connect_bss(struct network *network,
 						const struct scan_bss *bss);
 int network_autoconnect(struct network *network, struct scan_bss *bss);
-- 
2.34.1

[PATCH v3 2/4] station: use network_update_known_frequencies

[James Prestwood]

Updates each network with its new, most current, set of BSS's
for the different types of scans: dbus/autoconnect, hidden, and
OWE.
---
 src/station.c | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/src/station.c b/src/station.c
index a6442d3e..b186c505 100644
--- a/src/station.c
+++ b/src/station.c
@@ -350,6 +350,8 @@ static bool process_network(const void *key, void *data, void *user_data)
 		l_queue_insert(station->networks_sorted, network,
 				network_rank_compare, NULL);
 
+		network_update_known_frequencies(network);
+
 		return false;
 	}
 
@@ -799,6 +801,8 @@ free:
 		scan_bss_free(bss);
 	}
 
+	network_update_known_frequencies(network);
+
 	l_queue_destroy(bss_list, NULL);
 
 done:
@@ -3684,6 +3688,8 @@ next:
 		return true;
 	}
 
+	network_update_known_frequencies(network_psk ?: network_open);
+
 	error = network_connect_new_hidden_network(network_psk ?: network_open,
 							msg);
 
-- 
2.34.1

[PATCH v3 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 | 30 +++++++++++++++++++-----------
 src/knownnetworks.h |  6 ++++--
 src/station.c       | 10 ++++++++--
 3 files changed, 31 insertions(+), 15 deletions(-)

diff --git a/src/knownnetworks.c b/src/knownnetworks.c
index 04ce74ec..fc810057 100644
--- a/src/knownnetworks.c
+++ b/src/knownnetworks.c
@@ -517,8 +517,23 @@ struct network_info *known_networks_find(const char *ssid,
 	return l_queue_find(known_networks, network_info_match, &query);
 }
 
+static void known_network_append_frequencies(const struct network_info *info,
+						struct scan_freq_set *set,
+						uint8_t max)
+{
+	const struct l_queue_entry *entry;
+
+	for (entry = l_queue_get_entries(info->known_frequencies); entry && max;
+					entry = entry->next, max--) {
+		const struct known_frequency *known_freq = entry->data;
+
+		scan_freq_set_add(set, known_freq->frequency);
+	}
+}
+
 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
@@ -527,10 +542,9 @@ struct scan_freq_set *known_networks_get_recent_frequencies(
 	 * list.
 	 */
 	const struct l_queue_entry *network_entry;
-	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();
@@ -541,14 +555,8 @@ struct scan_freq_set *known_networks_get_recent_frequencies(
 						num_networks_tosearch--) {
 		const struct network_info *network = network_entry->data;
 
-		for (freq_entry = l_queue_get_entries(
-						network->known_frequencies);
-				freq_entry; freq_entry = freq_entry->next) {
-			const struct known_frequency *known_freq =
-							freq_entry->data;
-
-			scan_freq_set_add(set, known_freq->frequency);
-		}
+		known_network_append_frequencies(network, set,
+							freqs_per_network);
 	}
 
 	return set;
diff --git a/src/knownnetworks.h b/src/knownnetworks.h
index e8ffac0b..741d42ed 100644
--- a/src/knownnetworks.h
+++ b/src/knownnetworks.h
@@ -113,8 +113,10 @@ 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);
-int known_network_add_frequency(struct network_info *info, uint32_t frequency);
+						uint8_t num_networks_tosearch,
+						uint8_t freqs_per_network);
+int known_network_add_frequency(struct network_info *info,
+				uint32_t frequency);
 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/station.c b/src/station.c
index b186c505..8a5f4e18 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;
@@ -1438,7 +1441,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;
 
@@ -2761,7 +2766,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 v3 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 v3 1/4] network: add network_update_known_frequencies

[Denis Kenzior]

Hi James,

On 1/26/24 14:22, James Prestwood wrote:
> In order to support an ordered list of known frequencies the list
> should be in order of last seen BSS frequencies with the highest
> ranked ones first. To accomplish this without adding a lot of
> complexity the frequencies can be pushed into the list as long as
> they are pushed in reverse rank order (lowest rank first, highest
> last). This ensures that very high ranked BSS's will always get
> superseded by subsequent scans if not seen.
> 
> This adds a new network API to update the known frequency list
> based on the current newtork->bss_list. This assumes that station
> always wipes the BSS list on scans and populates with only fresh

Sort of.  Strictly speaking it takes the frequencies scanned into account.  So 
for example if we scan only certain 2.4GHz channels (say through DBus Scan API), 
then only BSSes within that frequency set will be updated.  However, such scans 
are initiated one-after-the-other, so it is probably okay in this case.

One thing you might have to be careful of is limited scans due to roaming logic. 
  But I think this series is good enough for now.

> BSS entries. After the scan this API can be called and it will
> reverse the list, then add each frequency.
> ---
>   src/network.c | 40 ++++++++++++++++++++++++++++------------
>   src/network.h |  2 ++
>   2 files changed, 30 insertions(+), 12 deletions(-)
> 
> v4:
>   * Added an API to do the insertion once all the BSS's have been added
>     to the network object.
>   * I'm also ok adding something to ELL like:
>     l_queue_new_reverse(list);

Given the sizes of our queues, it might be faster to reverse it twice than 
re-allocate / free one.  Might even be a good candidate for l_newa() if you can 
keep a known bound on the number of entries.

> 
>     The current reverse is in-place, so I cant really use it unless I
>     wanted to reverse twice to get it back to decending order.
> 

<snip>

>   bool network_bss_add(struct network *network, struct scan_bss *bss)
>   {
>   	if (!l_queue_insert(network->bss_list, bss, scan_bss_rank_compare,
>   									NULL))
>   		return false;
>   
> -	if (network->info)
> -		known_network_add_frequency(network->info, bss->frequency);
> -
>   	/* Done if BSS is not HS20 or we already have network_info set */
>   	if (!bss->hs20_capable)
>   		return true;

This part looked like it belong with patch 2, so I moved it there.

All patches applied, thanks.

Regards,
-Denis

Re: [PATCH v3 1/4] network: add network_update_known_frequencies

[James Prestwood]

Hi Denis,

On 1/29/24 6:54 PM, Denis Kenzior wrote:
> Hi James,
>
> On 1/26/24 14:22, James Prestwood wrote:
>> In order to support an ordered list of known frequencies the list
>> should be in order of last seen BSS frequencies with the highest
>> ranked ones first. To accomplish this without adding a lot of
>> complexity the frequencies can be pushed into the list as long as
>> they are pushed in reverse rank order (lowest rank first, highest
>> last). This ensures that very high ranked BSS's will always get
>> superseded by subsequent scans if not seen.
>>
>> This adds a new network API to update the known frequency list
>> based on the current newtork->bss_list. This assumes that station
>> always wipes the BSS list on scans and populates with only fresh
>
> Sort of.  Strictly speaking it takes the frequencies scanned into 
> account.  So for example if we scan only certain 2.4GHz channels (say 
> through DBus Scan API), then only BSSes within that frequency set will 
> be updated.  However, such scans are initiated one-after-the-other, so 
> it is probably okay in this case.
Yeah we are technically re-adding the same frequencies for each 
successive scan.
>
> One thing you might have to be careful of is limited scans due to 
> roaming logic.  But I think this series is good enough for now.
Yep this is why I didn't add anything in the roaming results just yet. 
That and neighbor reports will require a bit more thought. I think for 
roam scans/NR's we might be able to get away with doing the same thing, 
but limited only to the connected network. In theory a roam scan should 
still yield more updated frequencies than past scans, so we probably 
could shove those to the head of the queue in the same fashion.
>
>> BSS entries. After the scan this API can be called and it will
>> reverse the list, then add each frequency.
>> ---
>>   src/network.c | 40 ++++++++++++++++++++++++++++------------
>>   src/network.h |  2 ++
>>   2 files changed, 30 insertions(+), 12 deletions(-)
>>
>> v4:
>>   * Added an API to do the insertion once all the BSS's have been added
>>     to the network object.
>>   * I'm also ok adding something to ELL like:
>>     l_queue_new_reverse(list);
>
> Given the sizes of our queues, it might be faster to reverse it twice 
> than re-allocate / free one.  Might even be a good candidate for 
> l_newa() if you can keep a known bound on the number of entries.
>
>>
>>     The current reverse is in-place, so I cant really use it unless I
>>     wanted to reverse twice to get it back to decending order.
>>
>
> <snip>
>
>>   bool network_bss_add(struct network *network, struct scan_bss *bss)
>>   {
>>       if (!l_queue_insert(network->bss_list, bss, scan_bss_rank_compare,
>>                                       NULL))
>>           return false;
>>   -    if (network->info)
>> -        known_network_add_frequency(network->info, bss->frequency);
>> -
>>       /* Done if BSS is not HS20 or we already have network_info set */
>>       if (!bss->hs20_capable)
>>           return true;
>
> This part looked like it belong with patch 2, so I moved it there.
>
> All patches applied, thanks.
>
> Regards,
> -Denis
>