Am Sat, Jun 27, 2026 at 12:09:13PM -0400 schrieb Aaron Conole:
> (NOTE: I just realized that the reply-to-all wasn't directly sending to
> you, but rather just the mailing list - I'll go back and + for each of
> the replies I've sent so far)
>
> Felix Huettner via dev <[email protected]> writes:
>
> > A cmap cursor may not be held across rcu cycles. If there is a need for
> > iteration across rcu cycles the only previous solution was using a
> > cmap_position. However iterating using a position is significantly less
> > performant than iterating using a cursor.
> >
> > With this can we support swapping between cursors and positions. So a
> > position can be used to store the state across rcu cycles while the
> > cursor can be used for fast iteration.
> >
> > Signed-off-by: Felix Huettner <[email protected]>
> > ---
Hi Aaron,
thanks for the review.
>
> "Strangeness" indeed (from your test case changes). I think this needs
> more documentation. Any user of cursor->position->cursor may be tripped
> up by the fact that it advances the resulting cursor by one element (a
> fact that's documented in your test, but not anywhere else). I think it
> needs to be explicitly stated how the access pattern should work.
Yes i'll add comments with examples to both functions.
>
> Also, I'm a bit skeptical about how this will work across an RCU
> quiescent period when a concurrent remove happens while traversing during
> this time. What I think will happen, based on reading the code, is that
> pos->offset will be advanced past the end of the chain by one. When it
> gets restored from position_to_cursor, it won't find any node, and then
> will advance to the first node of the next non-empty set, but will skip
> past any nodes in the current chain. I might be wrong on that, but the
> above paragraph makes me doubt what is going on. BUT - it's difficult
> to evaluate because I don't see that kind of pattern in the test case.
I think that is correct. Between the cmap_cursor_to_position and
cmap_position_to_cursor the cmap might have added or removed buckets. So
there can be no guarantee that all elements are visited or that elements
are visited only once.
Basically you have the same guarantees as a cmap_position has during
that time.
I'll add a comment for this as well.
>
> CC'd Ilya, just because I want to double check my work.
>
> > lib/cmap.c | 62 +++++++++++++++++++++++++++++++++++++++++++++++
> > lib/cmap.h | 10 ++++++++
> > tests/test-cmap.c | 45 +++++++++++++++++++++++++++++++---
> > 3 files changed, 114 insertions(+), 3 deletions(-)
> >
> > diff --git a/lib/cmap.c b/lib/cmap.c
> > index 8ca893b0b..be8ef15fb 100644
> > --- a/lib/cmap.c
> > +++ b/lib/cmap.c
> > @@ -1068,3 +1068,65 @@ cmap_next_position(const struct cmap *cmap,
> > pos->bucket = pos->entry = pos->offset = 0;
> > return NULL;
> > }
> > +
> > +struct cmap_cursor
> > +cmap_position_to_cursor(const struct cmap *cmap,
> > + const struct cmap_position *pos)
> > +{
> > + struct cmap_cursor cursor;
> > +
> > + cursor.impl = cmap_get_impl(cmap);
> > + cursor.bucket_idx = pos->bucket;
> > + cursor.entry_idx = pos->entry;
> > + cursor.node = NULL;
> > +
> > + if (cursor.bucket_idx <= cursor.impl->mask && cursor.entry_idx <
> > CMAP_K) {
> > + const struct cmap_node *node = cmap_node_next(
> > + &cursor.impl->buckets[cursor.bucket_idx].
> > + nodes[cursor.entry_idx++]);
> > +
> > + unsigned int i;
> > + for (i = 0; node; i++, node = cmap_node_next(node)) {
> > + if (i == pos->offset) {
> > + cursor.node = CONST_CAST(struct cmap_node *, node);
> > + break;
> > + }
> > + }
> > +
> > + }
> > +
> > + if (!cursor.node) {
> > + cmap_cursor_advance(&cursor);
> > + }
> > +
> > + return cursor;
> > +}
> > +
> > +void
> > +cmap_cursor_to_position(const struct cmap_cursor *cursor,
> > + struct cmap_position *pos)
> > +{
> > + pos->bucket = cursor->bucket_idx;
> > + pos->offset = 0;
> > +
> > + /* This can only happen if the previous cmap_cursor_advance call
> > + * determined that we are at the end of the cmap. Our only required
> > + * behaviour here is to guarante that after converting
>
> guarantee
>
> > + * cursor->position->cursor we are still at then end of the cmap.
> > + * Since the bucket_idx will already be larger than the mask we can
> > + * just set the entry to some arbitrary value. */
> > + if (cursor->entry_idx == 0) {
> > + pos->entry = 0;
> > + return;
> > + }
> > +
> > + pos->entry = cursor->entry_idx - 1;
> > + const struct cmap_node *node = cmap_node_next(
> > + &cursor->impl->buckets[pos->bucket].
> > + nodes[pos->entry]);
> > + while (node && node != cursor->node) {
> > + pos->offset++;
> > + node = cmap_node_next(node);
> > + }
> > + pos->offset++;
> > +}
> > diff --git a/lib/cmap.h b/lib/cmap.h
> > index 72e2ec5f7..b61a7c533 100644
> > --- a/lib/cmap.h
> > +++ b/lib/cmap.h
> > @@ -294,4 +294,14 @@ cmap_remove(struct cmap *cmap, struct cmap_node *node,
> > uint32_t hash)
> > return cmap_replace(cmap, node, NULL, hash);
> > }
> >
> > +/* Convert a cmap position to a cursor. */
> > +struct cmap_cursor
> > +cmap_position_to_cursor(const struct cmap *,
> > + const struct cmap_position *);
> > +
> > +/* Convert a cmap cursor to a position. */
> > +void
> > +cmap_cursor_to_position(const struct cmap_cursor *,
> > + struct cmap_position *);
> > +
> > #endif /* cmap.h */
> > diff --git a/tests/test-cmap.c b/tests/test-cmap.c
> > index 3fe5ef964..15a90e01c 100644
> > --- a/tests/test-cmap.c
> > +++ b/tests/test-cmap.c
> > @@ -55,7 +55,7 @@ static void
> > check_cmap(struct cmap *cmap, const int values[], size_t n,
> > hash_func *hash)
> > {
> > - int *sort_values, *cmap_values, *cmap_values2;
> > + int *sort_values, *cmap_values, *cmap_values2, *cmap_values3;
> > const struct element *e;
> > size_t i, batch_size;
> >
> > @@ -66,6 +66,7 @@ check_cmap(struct cmap *cmap, const int values[], size_t
> > n,
> > sort_values = xmalloc(sizeof *sort_values * n);
> > cmap_values = xmalloc(sizeof *sort_values * n);
> > cmap_values2 = xmalloc(sizeof *sort_values * n);
> > + cmap_values3 = xmalloc(sizeof *sort_values * n);
> >
> > /* Here we test cursor iteration */
> > i = 0;
> > @@ -86,16 +87,54 @@ check_cmap(struct cmap *cmap, const int values[],
> > size_t n,
> > }
> > assert(i == n);
>
> Can we add tests for:
>
> 1. Position is saved, and cmap is modified
> 2. Cursor at end of cmap
> 3. Empty cmap (I think the test is always at least one element)
> 4. Two consecutive cursor position conversions without an intervening
> positon-cursor conversion?
> 5. Exhaustion case I mentioned above
I can add tests for 2-5. But testing for 1 is hard since we can not
define what is supposed to happen. Based on the hash and the random
basis of the cmap the new element might be added before or after the
possition. So we either get it, or we do not get it if we continue. That
would be just like using only a position in the first place.
>
> > + /* Here we test switching between cursors and positions.
> > + * We switch on every odd iteration.
> > + * It is a little strange since the cursor always points to the current
> > + * element being iterated over while the position points to the next
> > + * element. */
>
> This is the kind of thing that needs to be documented with the API,
> because it makes me nervous about this change.
It is especially confusing when trying to iterate with both methods.
However that was never the goal (just a good testcase). The goal was to
be able to iterate over a cmap with cmap_cursor and have some way to
hold that cursor across RCU cycles. So i don't think there is a
practical case for iterating with both methods.
Thanks a lot for the review, changes will be in the next version.
Felix
>
> > + bool use_position = true;
> > + pos = (struct cmap_position){0, 0, 0 };
> > + struct cmap_cursor cur;
> > + for (i = 0; i < n; i++) {
> > + if (i % 2 == 1) {
> > + if (use_position) {
> > + cur = cmap_position_to_cursor(cmap, &pos);
> > + } else {
> > + cmap_cursor_to_position(&cur, &pos);
> > + }
> > + use_position = !use_position;
> > + }
> > +
> > + if (use_position) {
> > + node = cmap_next_position(cmap, &pos);
> > + } else {
> > + /* Because of the strangeness above we do not need to advance
> > if
> > + * we just switched back from a position. */
> > + if (i % 2 == 0) {
> > + cmap_cursor_advance(&cur);
> > + }
> > + node = cur.node;
> > + }
> > +
> > + e = OBJECT_CONTAINING(node, e, node);
> > + ovs_assert(i < n);
> > + cmap_values3[i] = e->value;
> > + }
> > + ovs_assert(i == n);
> > +
> > memcpy(sort_values, values, sizeof *sort_values * n);
> > qsort(sort_values, n, sizeof *sort_values, compare_ints);
> > qsort(cmap_values, n, sizeof *cmap_values, compare_ints);
> > qsort(cmap_values2, n, sizeof *cmap_values2, compare_ints);
> > + qsort(cmap_values3, n, sizeof *cmap_values3, compare_ints);
> >
> > for (i = 0; i < n; i++) {
> > - assert(sort_values[i] == cmap_values[i]);
> > - assert(sort_values[i] == cmap_values2[i]);
> > + ovs_assert(sort_values[i] == cmap_values[i]);
> > + ovs_assert(sort_values[i] == cmap_values2[i]);
> > + ovs_assert(sort_values[i] == cmap_values3[i]);
> > }
> >
> > + free(cmap_values3);
> > free(cmap_values2);
> > free(cmap_values);
> > free(sort_values);
>
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
