[PATCH 0/7] Reduce and optimize quick/roam scan frequencies

[PATCH 0/7] Reduce and optimize quick/roam scan frequencies

[James Prestwood]

For large network deployments with many APs the list of known
frequencies can grow rather large. Since there is no cap on
the number of frequencies for quick scans this results in quite
a long scan. Roam scans (with no neighbor report) do cap at 5
frequencies but this list isn't sorted or optimized to scan
the most recently used BSS's.

These patches separate the known frequency list into two
sections, first most recently used, then most recently
seen. That way previously connected BSS frequencies are scanned
ahead of others. This also caps the number of frequencies for
quick scans to 5 per network. This still could result in 25
frequencies scanned (worst case), but its probably not very
common for a device to see 5 separate SSID's it can connect to.
In most cases its one, maybe 2.

James Prestwood (7):
  known_network: rename known_network_add_frequency
  knownnetworks: add known_network_add_connected_frequency
  network: call network_connected with BSS
  network: add network_roamed
  station: use network_roamed
  auto-t: update known frequency test to check order
  knownnetworks: limit 5 recent frequencies per network

 autotests/testKnownNetworks/frequency_test.py | 122 +++++++++++++-----
 autotests/testKnownNetworks/hw.conf           |  10 +-
 .../{ssidCCMP-2G.conf => ssidCCMP-2G-1.conf}  |   0
 .../testKnownNetworks/ssidCCMP-2G-2.conf      |   8 ++
 autotests/testKnownNetworks/ssidHotspot.conf  |   2 +-
 src/knownnetworks.c                           |  66 +++++++++-
 src/knownnetworks.h                           |   6 +-
 src/network.c                                 |  19 ++-
 src/network.h                                 |   3 +-
 src/station.c                                 |   4 +-
 10 files changed, 190 insertions(+), 50 deletions(-)
 rename autotests/testKnownNetworks/{ssidCCMP-2G.conf => ssidCCMP-2G-1.conf} (100%)
 create mode 100644 autotests/testKnownNetworks/ssidCCMP-2G-2.conf

-- 
2.34.1

[PATCH 1/7] known_network: rename known_network_add_frequency

[James Prestwood]

Rename to known_network_add_seen_frequency. This prepares to
differentiate between tracking frequencies based on a BSS being
seen versus being connected to. When a BSS has been connected to
that frequency should be preferred when roaming/quick scanning.
---
 src/knownnetworks.c | 3 ++-
 src/knownnetworks.h | 3 ++-
 src/network.c       | 6 +++---
 3 files changed, 7 insertions(+), 5 deletions(-)

diff --git a/src/knownnetworks.c b/src/knownnetworks.c
index 04ce74ec..eac6c66b 100644
--- a/src/knownnetworks.c
+++ b/src/knownnetworks.c
@@ -566,7 +566,8 @@ 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_seen_frequency(struct network_info *info,
+					uint32_t frequency)
 {
 	struct known_frequency *known_freq;
 
diff --git a/src/knownnetworks.h b/src/knownnetworks.h
index e8ffac0b..d404b161 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_seen_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/network.c b/src/network.c
index 4723334e..3e8770bc 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_seen_frequency(info, bss->frequency);
 }
 
 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_seen_frequency(network->info, bss->frequency);
 
 	/* 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_seen_frequency(network->info, bss->frequency);
 		known_network_frequency_sync(network->info);
 	}
 
-- 
2.34.1

[PATCH 2/7] knownnetworks: add known_network_add_connected_frequency

[James Prestwood]

This should be called when BSS is connected/roamed to which will
insert the frequency ahead of entries which were only seen in scan
results.

Providing this and the 'seen' variant sets up the frequency list
into two adjacent sections:
  [Most recently used]...[Most recently seen]

Doing this will allow scanning to be more optimized and limit the
number of frequencies while prefering BSS's that have been connected
to prior.

Note that this list format is not synced to the file system.
Frequencies will be synced in the order of this list but not
containing the 'connected' bit. When IWD restarts this information
will be lost, but the list is still sorted on disk in a better state
than it was prior.
---
 src/knownnetworks.c | 59 ++++++++++++++++++++++++++++++++++++++++++++-
 src/knownnetworks.h |  3 +++
 2 files changed, 61 insertions(+), 1 deletion(-)

diff --git a/src/knownnetworks.c b/src/knownnetworks.c
index eac6c66b..e44109fd 100644
--- a/src/knownnetworks.c
+++ b/src/knownnetworks.c
@@ -562,15 +562,70 @@ 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 *ka = a;
+
+	/*
+	 * Only meant to be used to insert 'seen' frequencies. Any existing
+	 * entry that has 'connected' set should preceed an entry that was
+	 * only seen.
+	 */
+	if (ka->connected)
+		return -1;
+
+	/*
+	 * Otherwise, insert immediately after the last 'connected' entry,
+	 * i.e. the most recently seen
+	 */
+	return 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. Frequencies added here will follow frequencies which have been
+ * connected to and inserted according to most-recently seen
  */
 int known_network_add_seen_frequency(struct network_info *info,
 					uint32_t frequency)
 {
 	struct known_frequency *known_freq;
 
+	if (!info->known_frequencies)
+		info->known_frequencies = l_queue_new();
+
+	known_freq = l_queue_find(info->known_frequencies,
+					known_frequency_match, &frequency);
+	/*
+	 * If no match, create a new one.
+	 * If connected to frequency before leave that entry in place
+	 */
+	if (!known_freq) {
+		known_freq = l_new(struct known_frequency, 1);
+		known_freq->frequency = frequency;
+	} else if (known_freq->connected)
+		return 0;
+
+	l_queue_remove(info->known_frequencies, known_freq);
+
+	/* insert the entry immediately after the last 'connected' entry */
+	l_queue_insert(info->known_frequencies, known_freq,
+			known_frequency_compare, NULL);
+
+	return 0;
+}
+
+/*
+ * Adds a frequency to the known set of frequencies that this network operates
+ * on. Frequencies added here are assumed to be most recently used and inserted
+ * at the head of the queue.
+ */
+int known_network_add_connected_frequency(struct network_info *info,
+						uint32_t frequency)
+{
+	struct known_frequency *known_freq;
+
 	if (!info->known_frequencies)
 		info->known_frequencies = l_queue_new();
 
@@ -581,6 +636,8 @@ int known_network_add_seen_frequency(struct network_info *info,
 		known_freq->frequency = frequency;
 	}
 
+	known_freq->connected = true;
+
 	l_queue_push_head(info->known_frequencies, known_freq);
 
 	return 0;
diff --git a/src/knownnetworks.h b/src/knownnetworks.h
index d404b161..644e713f 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;
+	bool connected : 1;
 };
 
 void __network_config_parse(const struct l_settings *settings,
@@ -116,6 +117,8 @@ struct scan_freq_set *known_networks_get_recent_frequencies(
 						uint8_t num_networks_tosearch);
 int known_network_add_seen_frequency(struct network_info *info,
 					uint32_t frequency);
+int known_network_add_connected_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,
-- 
2.34.1

[PATCH 3/7] network: call network_connected with BSS

[James Prestwood]

This will allow the BSS frequency to be inserted at the head of the
known frequency list, allowing future scans to prefer that frequency.
---
 src/network.c | 4 +++-
 src/network.h | 2 +-
 src/station.c | 2 +-
 3 files changed, 5 insertions(+), 3 deletions(-)

diff --git a/src/network.c b/src/network.c
index 3e8770bc..f4496c25 100644
--- a/src/network.c
+++ b/src/network.c
@@ -167,7 +167,7 @@ static bool network_secret_check_cacheable(void *data, void *user_data)
 	return false;
 }
 
-void network_connected(struct network *network)
+void network_connected(struct network *network, struct scan_bss *bss)
 {
 	enum security security = network_get_security(network);
 	const char *ssid = network_get_ssid(network);
@@ -190,6 +190,8 @@ void network_connected(struct network *network)
 		if (err < 0)
 			l_error("Error %i touching network config", err);
 
+		known_network_add_connected_frequency(network->info,
+							bss->frequency);
 		/* Syncs frequencies of already known network*/
 		known_network_frequency_sync(network->info);
 	}
diff --git a/src/network.h b/src/network.h
index f29649f7..e7638899 100644
--- a/src/network.h
+++ b/src/network.h
@@ -31,7 +31,7 @@ struct scan_bss;
 struct handshake_state;
 struct erp_cache_entry;
 
-void network_connected(struct network *network);
+void network_connected(struct network *network, struct scan_bss *bss);
 void network_disconnected(struct network *network);
 bool network_rankmod(const struct network *network, double *rankmod);
 
diff --git a/src/station.c b/src/station.c
index 73de26bb..4facc0bc 100644
--- a/src/station.c
+++ b/src/station.c
@@ -3213,7 +3213,7 @@ static void station_connect_ok(struct station *station)
 			l_warn("Could not request neighbor report");
 	}
 
-	network_connected(station->connected_network);
+	network_connected(station->connected_network, station->connected_bss);
 
 	if (station->netconfig) {
 		if (hs->fils_ip_req_ie && hs->fils_ip_resp_ie) {
-- 
2.34.1

[PATCH 4/7] network: add network_roamed

[James Prestwood]

Allows known frequencies to include the roam BSS frequency and
sync.
---
 src/network.c | 9 +++++++++
 src/network.h | 1 +
 2 files changed, 10 insertions(+)

diff --git a/src/network.c b/src/network.c
index f4496c25..04d1bf82 100644
--- a/src/network.c
+++ b/src/network.c
@@ -204,6 +204,15 @@ void network_connected(struct network *network, struct scan_bss *bss)
 	network->provisioning_hidden = false;
 }
 
+void network_roamed(struct network *network, struct scan_bss *bss)
+{
+	if (network->info) {
+		known_network_add_connected_frequency(network->info,
+							bss->frequency);
+		known_network_frequency_sync(network->info);
+	}
+}
+
 void network_disconnected(struct network *network)
 {
 	network_settings_close(network);
diff --git a/src/network.h b/src/network.h
index e7638899..323f64a5 100644
--- a/src/network.h
+++ b/src/network.h
@@ -32,6 +32,7 @@ struct handshake_state;
 struct erp_cache_entry;
 
 void network_connected(struct network *network, struct scan_bss *bss);
+void network_roamed(struct network *network, struct scan_bss *bss);
 void network_disconnected(struct network *network);
 bool network_rankmod(const struct network *network, double *rankmod);
 
-- 
2.34.1

[PATCH 5/7] station: use network_roamed

[James Prestwood]

---
 src/station.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/src/station.c b/src/station.c
index 4facc0bc..10860808 100644
--- a/src/station.c
+++ b/src/station.c
@@ -2106,6 +2106,8 @@ static void station_roamed(struct station *station)
 		L_WARN_ON(!netconfig_after_roam(station));
 	} else
 		station_enter_state(station, STATION_STATE_CONNECTED);
+
+	network_roamed(station->connected_network, station->connected_bss);
 }
 
 static void station_roam_retry(struct station *station)
-- 
2.34.1

[PATCH 6/7] auto-t: update known frequency test to check order

[James Prestwood]

Known frequencies are stored in order of most recently used, so
add some logic to the test to exercise the reordering of frequencies
as connections are made.
---
 autotests/testKnownNetworks/frequency_test.py | 122 +++++++++++++-----
 autotests/testKnownNetworks/hw.conf           |  10 +-
 .../{ssidCCMP-2G.conf => ssidCCMP-2G-1.conf}  |   0
 .../testKnownNetworks/ssidCCMP-2G-2.conf      |   8 ++
 autotests/testKnownNetworks/ssidHotspot.conf  |   2 +-
 5 files changed, 102 insertions(+), 40 deletions(-)
 rename autotests/testKnownNetworks/{ssidCCMP-2G.conf => ssidCCMP-2G-1.conf} (100%)
 create mode 100644 autotests/testKnownNetworks/ssidCCMP-2G-2.conf

diff --git a/autotests/testKnownNetworks/frequency_test.py b/autotests/testKnownNetworks/frequency_test.py
index 83e51c06..4443d2a1 100644
--- a/autotests/testKnownNetworks/frequency_test.py
+++ b/autotests/testKnownNetworks/frequency_test.py
@@ -8,13 +8,21 @@ import iwd
 from iwd import IWD
 from iwd import PSKAgent
 from iwd import NetworkType
+from hostapd import HostapdCLI
+from hwsim import Hwsim
 import testutil
 import os
 from configparser import ConfigParser
+from dataclasses import dataclass
+
+@dataclass
+class KnownFreq:
+    uuid: str
+    freqs: list
 
 class Test(unittest.TestCase):
-    def connect_network(self, wd, device, network):
-        ordered_network = device.get_ordered_network(network)
+    def connect_network(self, wd, device, network, scan=False):
+        ordered_network = device.get_ordered_network(network, full_scan=scan)
 
         condition = 'not obj.connected'
         wd.wait_for_object_condition(ordered_network.network_object, condition)
@@ -29,7 +37,39 @@ class Test(unittest.TestCase):
         condition = 'not obj.connected'
         wd.wait_for_object_condition(ordered_network.network_object, condition)
 
+    def read_known_freqs(self):
+        ret = {}
+        config = ConfigParser()
+        config.read('/tmp/iwd/.known_network.freq')
+        for s in config.sections():
+            ret[os.path.basename(config[s]['name'])] = KnownFreq(s, config[s]['list'].split(' '))
+
+        return ret
+
     def test_connection_success(self):
+        hostapd_psks = [
+            HostapdCLI(config="ssidCCMP-2G-1.conf"),
+            HostapdCLI(config="ssidCCMP-2G-2.conf"),
+            HostapdCLI(config="ssidCCMP-5G.conf"),
+        ]
+
+        hwsim = Hwsim()
+
+        rule0 = hwsim.rules.create()
+        rule0.source = hostapd_psks[0].bssid
+        rule0.signal = -2000
+        rule0.enabled = True
+
+        rule1 = hwsim.rules.create()
+        rule1.source = hostapd_psks[1].bssid
+        rule1.signal = -5000
+        rule1.enabled = True
+
+        rule2 = hwsim.rules.create()
+        rule2.source = hostapd_psks[2].bssid
+        rule2.signal = -7000
+        rule2.enabled = True
+
         wd = IWD(True, '/tmp')
 
         psk_agent = PSKAgent("secret123")
@@ -42,8 +82,7 @@ class Test(unittest.TestCase):
         # Connect to the PSK network, then Hotspot so IWD creates 2 entries in
         # the known frequency file.
         #
-
-        self.connect_network(wd, device, 'ssidCCMP')
+        self.connect_network(wd, device, "ssidCCMP")
 
         wd.unregister_psk_agent(psk_agent)
 
@@ -57,30 +96,27 @@ class Test(unittest.TestCase):
         psk_freqs = None
         psk_uuid = None
         hs20_freqs = None
-        hs20_uuid = None
-        config = ConfigParser()
-        config.read('/tmp/iwd/.known_network.freq')
-        for s in config.sections():
-            if os.path.basename(config[s]['name']) == 'ssidCCMP.psk':
-                psk_freqs = config[s]['list']
-                psk_freqs = psk_freqs.split(' ')
-                psk_uuid = s
-            elif os.path.basename(config[s]['name']) == 'example.conf':
-                hs20_freqs = config[s]['list']
-                hs20_freqs = hs20_freqs.split(' ')
-                hs20_uuid = s
+
+        freqs = self.read_known_freqs()
+
+        psk_freqs = freqs['ssidCCMP.psk']
+        hs20_freqs = freqs['example.conf']
 
         #
         # Verify the frequencies are what we expect
         #
         self.assertIsNotNone(psk_freqs)
-        self.assertIsNotNone(psk_uuid)
-        self.assertIn('5180', psk_freqs)
-        self.assertIn('2412', psk_freqs)
+        self.assertIsNotNone(psk_freqs.uuid)
+        # Save to compare later
+        psk_uuid = psk_freqs.uuid
+        self.assertIn('5180', psk_freqs.freqs)
+        # First should be the connected network. The other two's order is
+        # unknown since its based on whenever the BSS was seen.
+        self.assertEqual(psk_freqs.freqs[0], '2412')
 
         self.assertIsNotNone(hs20_freqs)
-        self.assertIsNotNone(hs20_uuid)
-        self.assertIn('2412', hs20_freqs)
+        self.assertIsNotNone(hs20_freqs.uuid)
+        self.assertIn('2417', hs20_freqs.freqs)
 
         #
         # Forget all know networks, this should remove all entries in the
@@ -92,11 +128,15 @@ class Test(unittest.TestCase):
         psk_agent = PSKAgent("secret123")
         wd.register_psk_agent(psk_agent)
 
+        # Rank a different BSS higher
+        rule0.signal = -7000
+        rule1.signal = -2000
+
         #
         # Reconnect, this should generate a completely new UUID since we
         # previously forgot the network.
         #
-        self.connect_network(wd, device, 'ssidCCMP')
+        self.connect_network(wd, device, 'ssidCCMP', scan=True)
 
         wd.unregister_psk_agent(psk_agent)
 
@@ -107,21 +147,33 @@ class Test(unittest.TestCase):
         psk_freqs = None
         psk_uuid2 = None
         hs20_freqs = None
-        config = ConfigParser()
-        config.read('/tmp/iwd/.known_network.freq')
-        for s in config.sections():
-            self.assertNotEqual(os.path.basename(config[s]['name']),
-                                    'example.conf')
-            if os.path.basename(config[s]['name']) == 'ssidCCMP.psk':
-                psk_freqs = config[s]['list']
-                psk_freqs = psk_freqs.split(' ')
-                psk_uuid2 = s
+
+        freqs = self.read_known_freqs()
+
+        psk_freqs = freqs['ssidCCMP.psk']
 
         self.assertIsNotNone(psk_freqs)
-        self.assertIsNotNone(psk_uuid2)
-        self.assertNotEqual(psk_uuid, psk_uuid2)
-        self.assertIn('5180', psk_freqs)
-        self.assertIn('2412', psk_freqs)
+        self.assertIsNotNone(psk_freqs.uuid)
+        self.assertNotEqual(psk_uuid2, psk_freqs.uuid)
+        self.assertIn('5180', psk_freqs.freqs)
+        # The 2417 frequency BSS should be first
+        self.assertEqual(psk_freqs.freqs[0], '2417')
+
+        # Rank the 5G BSS highest
+        rule0.signal = -7000
+        rule1.signal = -7000
+        rule2.signal = -2000
+
+        print("CONNECTING AGAGIn")
+        self.connect_network(wd, device, 'ssidCCMP', scan=True)
+
+        freqs = self.read_known_freqs()
+
+        psk_freqs = freqs['ssidCCMP.psk']
+
+        # The 5180 frequency BSS should now be first, followed by 2417
+        self.assertEqual(psk_freqs.freqs[0], '5180')
+        self.assertEqual(psk_freqs.freqs[1], '2417')
 
     @classmethod
     def setUpClass(cls):
diff --git a/autotests/testKnownNetworks/hw.conf b/autotests/testKnownNetworks/hw.conf
index 8a7ef73a..9fb3dbd5 100644
--- a/autotests/testKnownNetworks/hw.conf
+++ b/autotests/testKnownNetworks/hw.conf
@@ -1,10 +1,12 @@
 [SETUP]
-num_radios=5
+num_radios=6
 start_iwd=0
 reg_domain=US
+hwsim_medium=true
 
 [HOSTAPD]
 rad0=ssidNew.conf
-rad1=ssidCCMP-2G.conf
-rad2=ssidCCMP-5G.conf
-rad3=ssidHotspot.conf
+rad1=ssidCCMP-2G-1.conf
+rad2=ssidCCMP-2G-2.conf
+rad3=ssidCCMP-5G.conf
+rad4=ssidHotspot.conf
diff --git a/autotests/testKnownNetworks/ssidCCMP-2G.conf b/autotests/testKnownNetworks/ssidCCMP-2G-1.conf
similarity index 100%
rename from autotests/testKnownNetworks/ssidCCMP-2G.conf
rename to autotests/testKnownNetworks/ssidCCMP-2G-1.conf
diff --git a/autotests/testKnownNetworks/ssidCCMP-2G-2.conf b/autotests/testKnownNetworks/ssidCCMP-2G-2.conf
new file mode 100644
index 00000000..0d806fde
--- /dev/null
+++ b/autotests/testKnownNetworks/ssidCCMP-2G-2.conf
@@ -0,0 +1,8 @@
+hw_mode=g
+channel=2
+ssid=ssidCCMP
+
+wpa=2
+wpa_pairwise=CCMP
+wpa_passphrase=secret123
+beacon_int=10
diff --git a/autotests/testKnownNetworks/ssidHotspot.conf b/autotests/testKnownNetworks/ssidHotspot.conf
index 95170c84..35b31fbe 100644
--- a/autotests/testKnownNetworks/ssidHotspot.conf
+++ b/autotests/testKnownNetworks/ssidHotspot.conf
@@ -1,6 +1,6 @@
 #ctrl_interface=/var/run/hostapd
 hw_mode=g
-channel=1
+channel=2
 wpa=2
 ssid=Hotspot
 rsn_pairwise=CCMP
-- 
2.34.1

[PATCH 7/7] knownnetworks: limit 5 recent frequencies per network

[James Prestwood]

Since this is meant to be used for quick/roam scans we should be
putting a cap on the frequencies scanned. For large networks with
many BSS's this could end up scanning quite a few frequencies which
isn't very 'quick' as it should be.

Since the known frequency list is now sorted in most recently used
order we can grab the first 5 frequencies per network and be
somewhat confident that this will result in a BSS to connect to.
---
 src/knownnetworks.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/src/knownnetworks.c b/src/knownnetworks.c
index e44109fd..ecdd79a1 100644
--- a/src/knownnetworks.c
+++ b/src/knownnetworks.c
@@ -540,10 +540,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 num_freqs = 5;
 
 		for (freq_entry = l_queue_get_entries(
 						network->known_frequencies);
-				freq_entry; freq_entry = freq_entry->next) {
+				freq_entry && num_freqs;
+				freq_entry = freq_entry->next, num_freqs--) {
 			const struct known_frequency *known_freq =
 							freq_entry->data;
 
-- 
2.34.1

Re: [PATCH 1/7] known_network: rename known_network_add_frequency

[Denis Kenzior]

Hi James,

On 12/20/23 07:11, James Prestwood wrote:
> Rename to known_network_add_seen_frequency. This prepares to
> differentiate between tracking frequencies based on a BSS being
> seen versus being connected to. When a BSS has been connected to
> that frequency should be preferred when roaming/quick scanning.

Okay, you assert this, but can you elaborate on how you came to this conclusion? 
  I would think that adding a BSS you have seen recently in scan results should 
be preferred over one you might have connected to days earlier but haven't seen 
since.

Regards,
-Denis

Re: [PATCH 2/7] knownnetworks: add known_network_add_connected_frequency

[Denis Kenzior]

Hi James,

On 12/20/23 07:11, James Prestwood wrote:
> This should be called when BSS is connected/roamed to which will
> insert the frequency ahead of entries which were only seen in scan
> results.
> 
> Providing this and the 'seen' variant sets up the frequency list
> into two adjacent sections:
>    [Most recently used]...[Most recently seen]
> 

So why not just keep two lists?

> Doing this will allow scanning to be more optimized and limit the
> number of frequencies while prefering BSS's that have been connected
> to prior.
> 
> Note that this list format is not synced to the file system.
> Frequencies will be synced in the order of this list but not
> containing the 'connected' bit. When IWD restarts this information
> will be lost, but the list is still sorted on disk in a better state
> than it was prior.
> ---
>   src/knownnetworks.c | 59 ++++++++++++++++++++++++++++++++++++++++++++-
>   src/knownnetworks.h |  3 +++
>   2 files changed, 61 insertions(+), 1 deletion(-)
> 
> diff --git a/src/knownnetworks.c b/src/knownnetworks.c
> index eac6c66b..e44109fd 100644
> --- a/src/knownnetworks.c
> +++ b/src/knownnetworks.c
> @@ -562,15 +562,70 @@ 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 *ka = a;
> +
> +	/*
> +	 * Only meant to be used to insert 'seen' frequencies. Any existing
> +	 * entry that has 'connected' set should preceed an entry that was

precede?

> +	 * only seen.
> +	 */
> +	if (ka->connected)
> +		return -1; > +
> +	/*
> +	 * Otherwise, insert immediately after the last 'connected' entry,
> +	 * i.e. the most recently seen
> +	 */
> +	return 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. Frequencies added here will follow frequencies which have been
> + * connected to and inserted according to most-recently seen
>    */
>   int known_network_add_seen_frequency(struct network_info *info,
>   					uint32_t frequency)
>   {
>   	struct known_frequency *known_freq;
>   
> +	if (!info->known_frequencies)
> +		info->known_frequencies = l_queue_new();
> +

I'm not thrilled about the implementation...

> +	known_freq = l_queue_find(info->known_frequencies,
> +					known_frequency_match, &frequency);

You walk the entire queue once, then walk it again to remove the known_freq 
object, then walk it one more time for the insert.

> +	/*
> +	 * If no match, create a new one.
> +	 * If connected to frequency before leave that entry in place
> +	 */
> +	if (!known_freq) {
> +		known_freq = l_new(struct known_frequency, 1);
> +		known_freq->frequency = frequency;
> +	} else if (known_freq->connected)
> +		return 0;

So 'seeing' a frequency that has been connected to before doesn't change its 
sort order?

> +
> +	l_queue_remove(info->known_frequencies, known_freq);
> +
> +	/* insert the entry immediately after the last 'connected' entry */
> +	l_queue_insert(info->known_frequencies, known_freq,
> +			known_frequency_compare, NULL);
> +
> +	return 0;
> +}
> +
> +/*
> + * Adds a frequency to the known set of frequencies that this network operates
> + * on. Frequencies added here are assumed to be most recently used and inserted
> + * at the head of the queue.
> + */
> +int known_network_add_connected_frequency(struct network_info *info,
> +						uint32_t frequency)
> +{
> +	struct known_frequency *known_freq;
> +
>   	if (!info->known_frequencies)
>   		info->known_frequencies = l_queue_new();
>   
> @@ -581,6 +636,8 @@ int known_network_add_seen_frequency(struct network_info *info,
>   		known_freq->frequency = frequency;
>   	}
>   
> +	known_freq->connected = true;
> +
>   	l_queue_push_head(info->known_frequencies, known_freq);
>   
>   	return 0;

Overall I'm getting the feeling that the linked-list is the wrong data structure 
for all this.  If the intent is to maintain a bounded shortlist of frequencies 
to scan for a given network, then that's what we should do instead.

Regards,
-Denis

Re: [PATCH 2/7] knownnetworks: add known_network_add_connected_frequency

[James Prestwood]

Hi Denis,
>
> Overall I'm getting the feeling that the linked-list is the wrong data 
> structure for all this.  If the intent is to maintain a bounded 
> shortlist of frequencies to scan for a given network, then that's what 
> we should do instead.

Yeah I agree, this is a bit complicated. I think a much simpler approach 
would be to limit the known frequency list to some maximum size (e.g. 5) 
and store frequencies based on the BSS rank rather than seen/connected.

Thanks,

James

>
> Regards,
> -Denis