[ovs-dev] [PATCH 4/5] lib/cmap: Add more hmap-like functionality.

Jarno Rajahalme jrajahalme at nicira.com
Fri May 23 00:37:41 UTC 2014


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 <jrajahalme at 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




More information about the dev mailing list