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(-) 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
