Am Thu, Aug 06, 2026 at 10:58:44AM -0400 schrieb Aaron Conole:
> Felix Huettner <[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]>
>
> Only quickly took a look here, so just some nits:
thanks, will fix these
>
> > @@ -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
>
> Typo - guarante => guarantee (from v3, btw)
>
> > + * cursor->position->cursor we are still at then end of the cmap.
>
> Typo - then => the
>
> > + * 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..72a396236 100644
> > --- a/lib/cmap.h
> > +++ b/lib/cmap.h
> > @@ -294,4 +294,34 @@ 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.
> > + * After calling this '.node' of the retured cursor will point the the
> > element
>
> /point the the element/point to the element/
>
> > + * at the position of 'cmap_position'.
> > + *
> > + * Note that if you previously called cmap_next_position it will already
> > have
> > + * moved its position to the element after the one it returned.
> > + * This means that if cmap_next_position returned element 1 of the cmap
> > then
> > + * the cmap_cursor created by cmap_position_to_cursor will return element
> > 2 of
> > + * the cmap and not element 1.
> > + *
> > + * If this is used in combination with cmap_position_to_cursor to store and
> > + * retrive a cursor across RCU cycles the cursor might skip elements or
> > visit
> > + * them multiple times. This only happens if the cmap is modified
> > + * concurrently. */
> > +struct cmap_cursor
> > +cmap_position_to_cursor(const struct cmap *,
> > + const struct cmap_position *);
> > +
> > +/* Convert a cmap cursor to a position.
> > + * After calling this you will need to call cmap_next_position to actually
> > get
> > + * a cmap_node. This cmap_node will be the one after the one pointed to by
> > the
> > + * cursor.
> > + *
> > + * So if previously 'cursor.node' was element 1 of the cmap then calling
> > + * cmap_cursor_to_position and then cmap_next_position will return element
> > 2
> > + * of the cmap. */
> > +void
> > +cmap_cursor_to_position(const struct cmap_cursor *,
> > + struct cmap_position *);
> > +
> > #endif /* cmap.h */
> > diff --git a/tests/library.at b/tests/library.at
> > index 80ebe6ed8..22542b86c 100644
> > --- a/tests/library.at
> > +++ b/tests/library.at
> > @@ -34,7 +34,7 @@ AT_CLEANUP
> >
> > AT_SETUP([cuckoo hash])
> > AT_KEYWORDS([cmap])
> > -AT_CHECK([ovstest test-cmap check 1], [0], [...
> > +AT_CHECK([ovstest test-cmap check 1], [0], [......
> > ])
> > AT_CLEANUP
> >
> > diff --git a/tests/test-cmap.c b/tests/test-cmap.c
> > index 3fe5ef964..cdb2d6f82 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);
> >
> > + /* 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. */
> > + 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);
> > @@ -234,6 +273,75 @@ test_cmap_insert_replace_delete(hash_func *hash)
> > cmap_destroy(&cmap);
> > }
> >
> > +/* Tests edgecases of the switching between cursors and positions. */
> > +static void
> > +test_cmap_cursor_position_switch(hash_func *hash OVS_UNUSED)
> > +{
> > + enum { N_ELEMS = 1000 };
> > +
> > + struct cmap cmap = CMAP_INITIALIZER;
> > + struct element elements[N_ELEMS];
> > + struct cmap_position position, position2;
> > + struct cmap_cursor cursor;
> > + struct element *elem;
> > + size_t i;
> > +
> > + for (i = 0; i < N_ELEMS; i++) {
> > + elements[i].value = i;
> > + }
> > +
> > + /* Case 1: Switching between cursor and position on an empty cmap. */
> > + cursor = cmap_cursor_start(&cmap);
> > + cmap_cursor_to_position(&cursor, &position);
> > + ovs_assert(cmap_next_position(&cmap, &position) == NULL);
> > + cursor = cmap_position_to_cursor(&cmap, &position);
> > + ovs_assert(cursor.node == NULL);
> > +
> > + /* Case 2: Switching when we are at the end of the cmap should leave
> > us at
> > + * the end. */
> > + cmap_insert(&cmap, &elements[0].node, hash(0));
> > + cursor = cmap_cursor_start(&cmap);
> > + ovs_assert(cursor.node);
> > + cmap_cursor_advance(&cursor);
> > + ovs_assert(cursor.node == NULL);
> > + cmap_cursor_to_position(&cursor, &position);
> > + ovs_assert(cmap_next_position(&cmap, &position) == NULL);
> > +
> > + position = (struct cmap_position){0, 0, 0};
> > + cmap_next_position(&cmap, &position);
> > + cursor = cmap_position_to_cursor(&cmap, &position);
> > + ovs_assert(cursor.node == NULL);
> > +
> > + /* Case 3: Converting twice to a position also works. */
> > + cmap_insert(&cmap, &elements[1].node, hash(1));
> > + cursor = cmap_cursor_start(&cmap);
> > + cmap_cursor_to_position(&cursor, &position);
> > + cmap_cursor_to_position(&cursor, &position2);
> > + ovs_assert(cmap_next_position(&cmap, &position) != NULL);
> > + ovs_assert(cmap_next_position(&cmap, &position) == NULL);
> > + ovs_assert(cmap_next_position(&cmap, &position2) != NULL);
> > + ovs_assert(cmap_next_position(&cmap, &position2) == NULL);
> > +
> > + /* Case 4: Position at the end needs to stay at the end after removal.
> > */
> > + cursor = cmap_cursor_start(&cmap);
> > + cmap_cursor_advance(&cursor);
> > + /* Points now to the last element. */
> > + cmap_cursor_to_position(&cursor, &position);
> > + elem = OBJECT_CONTAINING(cursor.node, elem, node);
> > + cmap_cursor_advance(&cursor);
> > + /* Points now to the end of the cmap. */
> > + cmap_cursor_to_position(&cursor, &position2);
> > + cmap_remove(&cmap, &elem->node, hash(elem->value));
> > + /* This might or might not now produce a useful element. We may just
> > not
> > + * crash. */
> > + cmap_next_position(&cmap, &position);
> > + /* This needs to be NULL, since we where at the end of the list
> > + * previously. */
> > + ovs_assert(cmap_next_position(&cmap, &position2) == NULL);
> > +
> > + cmap_destroy(&cmap);
> > +}
> > +
> > static void
> > run_test(void (*function)(hash_func *))
> > {
> > @@ -256,6 +364,7 @@ run_tests(struct ovs_cmdl_context *ctx)
> > n = ctx->argc >= 2 ? atoi(ctx->argv[1]) : 100;
> > for (i = 0; i < n; i++) {
> > run_test(test_cmap_insert_replace_delete);
> > + run_test(test_cmap_cursor_position_switch);
> > }
> > printf("\n");
> > }
>
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
