(NOTE: I just realized that the reply-to-all wasn't directly sending to you, but rather just the mailing list - I'll go back and + for each of the replies I've sent so far)
Felix Huettner via dev <[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]> > --- "Strangeness" indeed (from your test case changes). I think this needs more documentation. Any user of cursor->position->cursor may be tripped up by the fact that it advances the resulting cursor by one element (a fact that's documented in your test, but not anywhere else). I think it needs to be explicitly stated how the access pattern should work. Also, I'm a bit skeptical about how this will work across an RCU quiescent period when a concurrent remove happens while traversing during this time. What I think will happen, based on reading the code, is that pos->offset will be advanced past the end of the chain by one. When it gets restored from position_to_cursor, it won't find any node, and then will advance to the first node of the next non-empty set, but will skip past any nodes in the current chain. I might be wrong on that, but the above paragraph makes me doubt what is going on. BUT - it's difficult to evaluate because I don't see that kind of pattern in the test case. CC'd Ilya, just because I want to double check my work. > 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 guarantee > + * 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); Can we add tests for: 1. Position is saved, and cmap is modified 2. Cursor at end of cmap 3. Empty cmap (I think the test is always at least one element) 4. Two consecutive cursor position conversions without an intervening positon-cursor conversion? 5. Exhaustion case I mentioned above > + /* 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. */ This is the kind of thing that needs to be documented with the API, because it makes me nervous about this change. > + 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); _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
