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 | 30 ++++++++++++ tests/library.at | 2 +- tests/test-cmap.c | 115 ++++++++++++++++++++++++++++++++++++++++++++-- 4 files changed, 205 insertions(+), 4 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..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 + * 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"); } -- 2.43.0 _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
