@@ -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 guarantee that after converting
+ * cursor->position->cursor we are still at the 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++;
+}
@@ -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 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 */
@@ -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
@@ -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");
}
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 <felix.huettner@digits.schwarz> --- Notes: v4->v5: fix typos lib/cmap.c | 62 +++++++++++++++++++++++++ lib/cmap.h | 30 ++++++++++++ tests/library.at | 2 +- tests/test-cmap.c | 115 ++++++++++++++++++++++++++++++++++++++++++++-- 4 files changed, 205 insertions(+), 4 deletions(-)