On 3/21/25 6:14 PM, Ilya Maximets wrote:
> On 3/21/25 17:32, Dumitru Ceara via dev wrote:
>> On 3/21/25 7:31 AM, Ales Musil wrote:
>>> @@ -108,40 +98,52 @@ bool
>>> ofctrl_acked_seqnos_contains(const struct ofctrl_acked_seqnos *seqnos,
>>> uint64_t val)
>>> {
>>> - struct ofctrl_ack_seqno *sn;
>>> + if (vector_is_empty(&seqnos->acked)) {
>>> + return false;
>>> + }
>>> +
>>> + size_t low = 0;
>>> + size_t high = vector_len(&seqnos->acked) -1;
>>> + uint64_t *acked = vector_get_array(&seqnos->acked);
>>>
>>> - HMAP_FOR_EACH_WITH_HASH (sn, node, hash_uint64(val), &seqnos->acked) {
>>> - if (sn->seqno == val) {
>>> + while (low <= high) {
>>> + size_t mid = low + (high - low) / 2;
>>> +
>>> + if (acked[mid] == val) {
>>> return true;
>>> }
>>> +
>>> + if (acked[mid] >= acked[low]) {
>>> + if (val >= acked[low] && val < acked[mid]) {
>>> + high = mid - 1;
>>> + } else {
>>> + low = mid + 1;
>>> + }
>>> + } else {
>>> + if (val > acked[mid] && val <= acked[high]) {
>>> + low = mid + 1;
>>> + } else {
>>> + high = mid - 1;
>>> + }
>>> + }
>>> }
>>> - return false;
>>> -}
>>
>> I think this definitely deserves a comment. :)
>>
>> This works because sequence numbers are acked in increasing order
>> (except for the case when sequence numbers overflow).
>
> The data structure is also used for nb_cfg numbers. I'm not sure we can
> guarantee that they can never jump back or overflow. Database can be reset
> for example. And while this is far reached and the function is not used
> for this use case, I'm not convinced it's a good idea to assume any kind
> of order in this generic function.
>
Good point, I missed the nb_cfg case exactly because we don't call this
function there. If we decide to use this binary search variation, it
should only be for data structures that are collections whose order is
guaranteed.
Which means that maybe we shouldn't change ofctrl_acked_seqnos after
all; the current hash based implementation is probably good enough.
>> So the sequence
>> number collection is always a "sorted and shifted" ordered collection
>> which allows us to implement the binary search above if we store them as
>> a vector.
>
> FWIW, I'm also not sure this binary search implementation is correct.
> I didn't look very close, but on a first read it seems that it can't
> find the second element of an ascending 2-element vector. And if that's
> true, it will fail to find elements in any array half the time.
I might be missing something but it seems to me that the code above
works fine when searching for the second element of an ascending
2-element vector. I didn't look closely yet though.
> I'd suggest to add vector_find function instead and use the standard
> bsearch() inside. And and some unit tests.
+1 for bsearch() if we decide we need a vector_find(). Also +1 for unit
tests.
>
> But again, I'm not convinced we can assume the values to be sorted here.
>
> Best regards, Ilya Maximets.
>
Regards,
Dumitru
_______________________________________________
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
