Am Thu, Jun 18, 2026 at 04:25:03PM +0200 schrieb Felix Huettner:
> 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]>
> ---
> lib/cmap.c | 62 +++++++++++++++++++++++++++++++++++++++++++++++
> lib/cmap.h | 10 ++++++++
> tests/test-cmap.c | 45 +++++++++++++++++++++++++++++++---
> 3 files changed, 114 insertions(+), 3 deletions(-)
Something strange happened in the CI in regards to installation of
dependencies.
Recheck-request: github-robot-_Build_and_Test
>
> 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
> + * 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);
>
> + /* 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);
> --
> 2.43.0
>
>
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
