On Sat, Mar 22, 2025 at 10:40 PM Dumitru Ceara <[email protected]> wrote:
> 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;
> >>> -}
> >>
>
Hi Dumitru and Ilya,
thank you for the review.
> >> 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.
>
The find is not used at all in the nb_cfg, it looks only at the last
acked seqno. So this function should be fine as is. There are other
assumptions even in the current code about the order.
> >> 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.
>
The vector_find is fine, however it can be a footgun because the user
will have to ensure it is ordered. Also why do we need unit test for
functions provided by libc? vector_find() would be just a wrapper so it
doesn't make sense to test libc in our code in my opinion. Also
bsearch() doesn't work on rotated/shifted arrays AFAIK, which is the
case here.
> >
> > But again, I'm not convinced we can assume the values to be sorted here.
> >
> > Best regards, Ilya Maximets.
> >
>
> Regards,
> Dumitru
>
>
Thanks,
Ales
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
