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

[Denis Kenzior <denkenz@gmail.com>]

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