Add cmap_replace() and cmap_first(), as well as CMAP_FOR_EACH_SAFE and
CMAP_FOR_EACH_CONTINUE to make porting existing hmap using code a bit
easier.
CMAP_FOR_EACH_SAFE is useful in RCU postponed destructors, when it is
known that additional postponing is not needed.
Signed-off-by: Jarno Rajahalme <jrajaha...@nicira.com>
---
lib/cmap.c | 37 ++++++++++++++++++++++++++++++-------
lib/cmap.h | 40 +++++++++++++++++++++++++++++++++++-----
tests/test-cmap.c | 17 ++++++++++++++---
3 files changed, 79 insertions(+), 15 deletions(-)
diff --git a/lib/cmap.c b/lib/cmap.c
index 1eb79b4..6c23a62 100644
--- a/lib/cmap.c
+++ b/lib/cmap.c
@@ -648,8 +648,8 @@ cmap_insert(struct cmap *cmap, struct cmap_node *node,
uint32_t hash)
}
static bool
-cmap_remove__(struct cmap_impl *impl, struct cmap_node *node,
- uint32_t hash, uint32_t h)
+cmap_replace__(struct cmap_impl *impl, struct cmap_node *node,
+ struct cmap_node *replacement, uint32_t hash, uint32_t h)
{
struct cmap_bucket *b = &impl->buckets[h & impl->mask];
int slot;
@@ -659,8 +659,17 @@ cmap_remove__(struct cmap_impl *impl, struct cmap_node
*node,
return false;
}
+ /* The pointer to 'node' is changed to point to 'replacement',
+ * which is the next node if no replacement node is given. */
+ if (!replacement) {
+ replacement = cmap_node_next_protected(node);
+ } else {
+ /* 'replacement' takes the position of 'node' in the list. */
+ ovsrcu_init(&replacement->next, cmap_node_next_protected(node));
+ }
+
if (b->nodes[slot] == node) {
- b->nodes[slot] = cmap_node_next_protected(node);
+ b->nodes[slot] = replacement;
atomic_thread_fence(memory_order_release);
} else {
struct cmap_node *iter = b->nodes[slot];
@@ -671,7 +680,7 @@ cmap_remove__(struct cmap_impl *impl, struct cmap_node
*node,
}
iter = next;
}
- ovsrcu_set(&iter->next, cmap_node_next_protected(node));
+ ovsrcu_set(&iter->next, replacement);
}
return true;
}
@@ -686,15 +695,29 @@ cmap_remove__(struct cmap_impl *impl, struct cmap_node
*node,
void
cmap_remove(struct cmap *cmap, struct cmap_node *node, uint32_t hash)
{
+ cmap_replace(cmap, node, NULL, hash);
+ cmap_get_impl(cmap)->n--;
+}
+
+/* Replaces 'old_node' in 'cmap' with 'new_node'. The caller must
+ * ensure that 'cmap' cannot change concurrently (from another thread).
+ *
+ * 'old_node' must not be destroyed or modified or inserted back into 'cmap' or
+ * into any other concurrent hash map while any other thread might be accessing
+ * it. One correct way to do this is to free it from an RCU callback with
+ * ovsrcu_postpone(). */
+void
+cmap_replace(struct cmap *cmap, struct cmap_node *old_node,
+ struct cmap_node *new_node, uint32_t hash)
+{
struct cmap_impl *impl = cmap_get_impl(cmap);
uint32_t h1 = rehash(impl, hash);
uint32_t h2 = other_hash(h1);
bool ok;
- ok = (cmap_remove__(impl, node, hash, h1) ||
- cmap_remove__(impl, node, hash, h2));
+ ok = cmap_replace__(impl, old_node, new_node, hash, h1)
+ || cmap_replace__(impl, old_node, new_node, hash, h2);
ovs_assert(ok);
- impl->n--;
}
static bool
diff --git a/lib/cmap.h b/lib/cmap.h
index b9e3671..2ca23ef 100644
--- a/lib/cmap.h
+++ b/lib/cmap.h
@@ -34,16 +34,16 @@
*
* The general rules are:
*
- * - Only a single thread may safely call into cmap_insert() or
- * cmap_remove() at any given time.
+ * - Only a single thread may safely call into cmap_insert(),
+ * cmap_remove(), or cmap_replace() at any given time.
*
* - Any number of threads may use functions and macros that search or
* iterate through a given cmap, even in parallel with other threads
- * calling cmap_insert() or cmap_remove().
+ * calling cmap_insert(), cmap_remove(), or cmap_replace().
*
* There is one exception: cmap_find_protected() is only safe if no thread
- * is currently calling cmap_insert() or cmap_remove(). (Use ordinary
- * cmap_find() if that is not guaranteed.)
+ * is currently calling cmap_insert(), cmap_remove(), or cmap_replace().
+ * (Use ordinary cmap_find() if that is not guaranteed.)
*
* - See "Iteration" below for additional thread safety rules.
*
@@ -90,6 +90,8 @@ bool cmap_is_empty(const struct cmap *);
/* Insertion and deletion. */
void cmap_insert(struct cmap *, struct cmap_node *, uint32_t hash);
void cmap_remove(struct cmap *, struct cmap_node *, uint32_t hash);
+void cmap_replace(struct cmap *, struct cmap_node *old_node,
+ struct cmap_node *new_node, uint32_t hash);
/* Search.
*
@@ -172,6 +174,22 @@ struct cmap_node *cmap_find_protected(const struct cmap *,
uint32_t hash);
ASSIGN_CONTAINER(NODE, cmap_cursor_next(CURSOR, &(NODE)->MEMBER), \
MEMBER))
+#define CMAP_FOR_EACH_SAFE(NODE, NEXT, MEMBER, CURSOR, CMAP) \
+ for ((cmap_cursor_init(CURSOR, CMAP), \
+ ASSIGN_CONTAINER(NODE, cmap_cursor_next(CURSOR, NULL), MEMBER)); \
+ (NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER) \
+ ? ASSIGN_CONTAINER(NEXT, cmap_cursor_next(CURSOR, &(NODE)->MEMBER), \
+ MEMBER), 1 \
+ : 0); \
+ (NODE) = (NEXT))
+
+#define CMAP_FOR_EACH_CONTINUE(NODE, MEMBER, CURSOR, CMAP) \
+ for (ASSIGN_CONTAINER(NODE, cmap_cursor_next(CURSOR, &(NODE)->MEMBER), \
+ MEMBER); \
+ NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER); \
+ ASSIGN_CONTAINER(NODE, cmap_cursor_next(CURSOR, &(NODE)->MEMBER), \
+ MEMBER))
+
struct cmap_cursor {
const struct cmap_impl *impl;
uint32_t bucket_idx;
@@ -182,6 +200,8 @@ void cmap_cursor_init(struct cmap_cursor *, const struct
cmap *);
struct cmap_node *cmap_cursor_next(struct cmap_cursor *,
const struct cmap_node *);
+static inline struct cmap_node *cmap_first(const struct cmap *);
+
/* Another, less preferred, form of iteration, for use in situations where it
* is difficult to maintain a pointer to a cmap_node. */
struct cmap_position {
@@ -193,4 +213,14 @@ struct cmap_position {
struct cmap_node *cmap_next_position(const struct cmap *,
struct cmap_position *);
+/* Returns the first node in 'cmap', in arbitrary order, or a null pointer if
+ * 'cmap' is empty. */
+static inline struct cmap_node *
+cmap_first(const struct cmap *cmap)
+{
+ struct cmap_position pos = { 0, 0, 0 };
+
+ return cmap_next_position(cmap, &pos);
+}
+
#endif /* cmap.h */
diff --git a/tests/test-cmap.c b/tests/test-cmap.c
index 110311f..f8f68b4 100644
--- a/tests/test-cmap.c
+++ b/tests/test-cmap.c
@@ -92,6 +92,9 @@ check_cmap(struct cmap *cmap, const int values[], size_t n,
assert(count == 1);
}
+ /* Check that cmap_first() returns NULL only when cmap_is_empty(). */
+ assert(!cmap_first(cmap) == cmap_is_empty(cmap));
+
/* Check counters. */
assert(cmap_is_empty(cmap) == !n);
assert(cmap_count(cmap) == n);
@@ -155,11 +158,12 @@ constant_hash(int value OVS_UNUSED)
/* Tests basic cmap insertion and deletion. */
static void
-test_cmap_insert_delete(hash_func *hash)
+test_cmap_insert_replace_delete(hash_func *hash)
{
enum { N_ELEMS = 1000 };
struct element elements[N_ELEMS];
+ struct element copies[N_ELEMS];
int values[N_ELEMS];
struct cmap cmap;
size_t i;
@@ -173,7 +177,14 @@ test_cmap_insert_delete(hash_func *hash)
}
shuffle(values, N_ELEMS);
for (i = 0; i < N_ELEMS; i++) {
- cmap_remove(&cmap, &elements[values[i]].node, hash(values[i]));
+ copies[values[i]].value = values[i];
+ cmap_replace(&cmap, &elements[values[i]].node,
+ &copies[values[i]].node, hash(values[i]));
+ check_cmap(&cmap, values, N_ELEMS, hash);
+ }
+ shuffle(values, N_ELEMS);
+ for (i = 0; i < N_ELEMS; i++) {
+ cmap_remove(&cmap, &copies[values[i]].node, hash(values[i]));
check_cmap(&cmap, values + (i + 1), N_ELEMS - (i + 1), hash);
}
cmap_destroy(&cmap);
@@ -200,7 +211,7 @@ run_tests(int argc, char *argv[])
n = argc >= 2 ? atoi(argv[1]) : 100;
for (i = 0; i < n; i++) {
- run_test(test_cmap_insert_delete);
+ run_test(test_cmap_insert_replace_delete);
}
printf("\n");
}
--
1.7.10.4
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
