[ovs-dev] [RFC 05/14] udpif: Separate ukey maps from revalidators.

Joe Stringer joestringer at nicira.com
Thu Aug 21 05:42:00 UTC 2014


An upcoming patch will change the access patterns for ukey maps to
increase the number of writers, and shift write-access from revalidator
threads to upcall handler threads. As such, it no longer makes sense to
tie these maps to revalidators in a 1:1 relationship.

This patch separates the ukey maps from the revalidators, and increases
the number of maps used to store ukeys, to reduce contention.

Signed-off-by: Joe Stringer <joestringer at nicira.com>
---
 ofproto/ofproto-dpif-upcall.c |  155 +++++++++++++++++++++++------------------
 1 file changed, 87 insertions(+), 68 deletions(-)

diff --git a/ofproto/ofproto-dpif-upcall.c b/ofproto/ofproto-dpif-upcall.c
index db11964..9e8a3ac 100644
--- a/ofproto/ofproto-dpif-upcall.c
+++ b/ofproto/ofproto-dpif-upcall.c
@@ -57,17 +57,20 @@ struct handler {
     uint32_t handler_id;               /* Handler id. */
 };
 
+/* In the absence of a multiple-writer multiple-reader datastructure for
+ * storing ukeys, we use a large number of cmaps, each with its own lock for
+ * writing. */
+struct umap {
+    struct ovs_mutex mutex;            /* Take for writing to the following. */
+    struct cmap cmap;                  /* Datapath flow keys. */
+};
+
 /* A thread that processes datapath flows, updates OpenFlow statistics, and
  * updates or removes them if necessary. */
 struct revalidator {
     struct udpif *udpif;               /* Parent udpif. */
     pthread_t thread;                  /* Thread ID. */
     unsigned int id;                   /* ovsthread_id_self(). */
-    struct ovs_mutex *mutex;           /* Points into udpif->ukeys for this
-                                          revalidator. Required for writing
-                                          to 'ukeys'. */
-    struct cmap *ukeys;                /* Points into udpif->ukeys for this
-                                          revalidator. Used for GC phase. */
 };
 
 /* An upcall handler for ofproto_dpif.
@@ -111,16 +114,13 @@ struct udpif {
     long long int dump_duration;       /* Duration of the last flow dump. */
     struct seq *dump_seq;              /* Increments each dump iteration. */
 
-    /* There are 'n_revalidators' ukey cmaps. Each revalidator retains a
-     * reference to one of these for garbage collection.
+    /* There are 'n_umaps' maps of ukeys.
      *
      * During the flow dump phase, revalidators insert into these with a random
      * distribution. During the garbage collection phase, each revalidator
-     * takes care of garbage collecting one of these hmaps. */
-    struct {
-        struct ovs_mutex mutex;        /* Take for writing to the following. */
-        struct cmap cmap;              /* Datapath flow keys. */
-    } *ukeys;
+     * takes care of garbage collecting a slice of these maps. */
+    struct umap *ukeys;
+    size_t n_umaps;
 
     /* Datapath flow statistics. */
     unsigned int max_n_flows;
@@ -185,9 +185,10 @@ struct upcall {
  * the dump phase, but are owned by a single revalidator, and are destroyed
  * by that revalidator during the garbage-collection phase.
  *
- * While some elements of a udpif_key are protected by a mutex, the ukey itself
- * is not.  Therefore it is not safe to destroy a udpif_key except when all
- * revalidators are in garbage collection phase, or they aren't running. */
+ * The mutex within the ukey protects some members of the ukey. The ukey
+ * itself is protected by RCU and is held within a umap in the parent udpif.
+ * Adding or removing a ukey from a umap is only safe when holding the
+ * corresponding umap lock. */
 struct udpif_key {
     struct cmap_node cmap_node;     /* In parent revalidator 'ukeys' map. */
 
@@ -249,7 +250,7 @@ static bool ukey_acquire(struct udpif *udpif, const struct nlattr *key,
                          size_t key_len, long long int used,
                          struct udpif_key **result);
 static void ukey_delete__(struct udpif_key *);
-static void ukey_delete(struct revalidator *, struct udpif_key *);
+static void ukey_delete(struct umap *, struct udpif_key *);
 static enum upcall_type classify_upcall(enum dpif_upcall_type type,
                                         const struct nlattr *userdata);
 
@@ -293,6 +294,12 @@ udpif_create(struct dpif_backer *backer, struct dpif *dpif)
     atomic_init(&udpif->n_flows, 0);
     atomic_init(&udpif->n_flows_timestamp, LLONG_MIN);
     ovs_mutex_init(&udpif->n_flows_mutex);
+    udpif->n_umaps = 128;
+    udpif->ukeys = xmalloc(udpif->n_umaps * sizeof *udpif->ukeys);
+    for (int i = 0; i < udpif->n_umaps; i++) {
+        cmap_init(&udpif->ukeys[i].cmap);
+        ovs_mutex_init(&udpif->ukeys[i].mutex);
+    }
 
     dpif_register_upcall_cb(dpif, upcall_cb, udpif);
 
@@ -319,6 +326,13 @@ udpif_destroy(struct udpif *udpif)
 {
     udpif_stop_threads(udpif);
 
+    for (int i = 0; i < udpif->n_umaps; i++) {
+        cmap_destroy(&udpif->ukeys[i].cmap);
+        ovs_mutex_destroy(&udpif->ukeys[i].mutex);
+    }
+    free(udpif->ukeys);
+    udpif->ukeys = NULL;
+
     list_remove(&udpif->list_node);
     latch_destroy(&udpif->exit_latch);
     seq_destroy(udpif->reval_seq);
@@ -355,9 +369,6 @@ udpif_stop_threads(struct udpif *udpif)
             /* Delete ukeys, and delete all flows from the datapath to prevent
              * double-counting stats. */
             revalidator_purge(revalidator);
-
-            cmap_destroy(&udpif->ukeys[i].cmap);
-            ovs_mutex_destroy(&udpif->ukeys[i].mutex);
         }
 
         latch_poll(&udpif->exit_latch);
@@ -371,9 +382,6 @@ udpif_stop_threads(struct udpif *udpif)
         free(udpif->handlers);
         udpif->handlers = NULL;
         udpif->n_handlers = 0;
-
-        free(udpif->ukeys);
-        udpif->ukeys = NULL;
     }
 }
 
@@ -405,15 +413,10 @@ udpif_start_threads(struct udpif *udpif, size_t n_handlers,
         udpif->reval_exit = false;
         udpif->revalidators = xzalloc(udpif->n_revalidators
                                       * sizeof *udpif->revalidators);
-        udpif->ukeys = xmalloc(sizeof *udpif->ukeys * n_revalidators);
         for (i = 0; i < udpif->n_revalidators; i++) {
             struct revalidator *revalidator = &udpif->revalidators[i];
 
             revalidator->udpif = udpif;
-            cmap_init(&udpif->ukeys[i].cmap);
-            ovs_mutex_init(&udpif->ukeys[i].mutex);
-            revalidator->mutex = &udpif->ukeys[i].mutex;
-            revalidator->ukeys = &udpif->ukeys[i].cmap;
             revalidator->thread = ovs_thread_create(
                 "revalidator", udpif_revalidator, revalidator);
         }
@@ -496,7 +499,7 @@ udpif_get_memory_usage(struct udpif *udpif, struct simap *usage)
     simap_increase(usage, "handlers", udpif->n_handlers);
 
     simap_increase(usage, "revalidators", udpif->n_revalidators);
-    for (i = 0; i < udpif->n_revalidators; i++) {
+    for (i = 0; i < udpif->n_umaps; i++) {
         simap_increase(usage, "udpif keys", cmap_count(&udpif->ukeys[i].cmap));
     }
 }
@@ -1154,7 +1157,7 @@ ukey_lookup(struct udpif *udpif, const struct nlattr *key, size_t key_len,
             uint32_t hash)
 {
     struct udpif_key *ukey;
-    struct cmap *cmap = &udpif->ukeys[hash % udpif->n_revalidators].cmap;
+    struct cmap *cmap = &udpif->ukeys[hash % udpif->n_umaps].cmap;
 
     CMAP_FOR_EACH_WITH_HASH (ukey, cmap_node, hash, cmap) {
         if (ukey->key_len == key_len && !memcmp(ukey->key, key, key_len)) {
@@ -1204,7 +1207,7 @@ ukey_acquire(struct udpif *udpif, const struct nlattr *key, size_t key_len,
     bool locked = false;
 
     hash = hash_bytes(key, key_len, udpif->secret);
-    idx = hash % udpif->n_revalidators;
+    idx = hash % udpif->n_umaps;
 
     ovs_mutex_lock(&udpif->ukeys[idx].mutex);
     ukey = ukey_lookup(udpif, key, key_len, hash);
@@ -1235,9 +1238,10 @@ ukey_delete__(struct udpif_key *ukey)
 }
 
 static void
-ukey_delete(struct revalidator *revalidator, struct udpif_key *ukey)
+ukey_delete(struct umap *umap, struct udpif_key *ukey)
+    OVS_REQUIRES(umap->mutex)
 {
-    cmap_remove(revalidator->ukeys, &ukey->cmap_node, ukey->hash);
+    cmap_remove(&umap->cmap, &ukey->cmap_node, ukey->hash);
     ovsrcu_postpone(ukey_delete__, ukey);
 }
 
@@ -1492,17 +1496,17 @@ push_dump_ops__(struct udpif *udpif, struct dump_op *ops, size_t n_ops)
 }
 
 static void
-push_dump_ops(struct revalidator *revalidator,
+push_dump_ops(struct udpif *udpif, struct umap *umap,
               struct dump_op *ops, size_t n_ops)
 {
     int i;
 
-    push_dump_ops__(revalidator->udpif, ops, n_ops);
-    ovs_mutex_lock(revalidator->mutex);
+    push_dump_ops__(udpif, ops, n_ops);
+    ovs_mutex_lock(&umap->mutex);
     for (i = 0; i < n_ops; i++) {
-        ukey_delete(revalidator, ops[i].ukey);
+        ukey_delete(umap, ops[i].ukey);
     }
-    ovs_mutex_unlock(revalidator->mutex);
+    ovs_mutex_unlock(&umap->mutex);
 }
 
 static void
@@ -1626,44 +1630,52 @@ handle_missed_revalidation(struct revalidator *revalidator,
 static void
 revalidator_sweep__(struct revalidator *revalidator, bool purge)
 {
-    struct dump_op ops[REVALIDATE_MAX_BATCH];
-    struct udpif_key *ukey;
-    size_t n_ops;
+    struct udpif *udpif;
     uint64_t dump_seq;
+    int slice;
 
-    n_ops = 0;
-    dump_seq = seq_read(revalidator->udpif->dump_seq);
+    udpif = revalidator->udpif;
+    dump_seq = seq_read(udpif->dump_seq);
+    slice = revalidator - udpif->revalidators;
+    ovs_assert(slice < udpif->n_revalidators);
+
+    for (int i = slice; i < udpif->n_umaps; i += udpif->n_revalidators) {
+        struct dump_op ops[REVALIDATE_MAX_BATCH];
+        struct udpif_key *ukey;
+        struct umap *umap = &udpif->ukeys[i];
+        size_t n_ops = 0;
 
-    CMAP_FOR_EACH(ukey, cmap_node, revalidator->ukeys) {
-        bool flow_exists, seq_mismatch;
+        CMAP_FOR_EACH(ukey, cmap_node, &umap->cmap) {
+            bool flow_exists, seq_mismatch;
 
-        ovs_mutex_lock(&ukey->mutex);
-        flow_exists = ukey->flow_exists;
-        seq_mismatch = (ukey->dump_seq != dump_seq
-                        && revalidator->udpif->need_revalidate);
-        ovs_mutex_unlock(&ukey->mutex);
+            ovs_mutex_lock(&ukey->mutex);
+            flow_exists = ukey->flow_exists;
+            seq_mismatch = (ukey->dump_seq != dump_seq
+                            && revalidator->udpif->need_revalidate);
+            ovs_mutex_unlock(&ukey->mutex);
 
-        if (flow_exists
-            && (purge
-                || (seq_mismatch
-                    && !handle_missed_revalidation(revalidator, ukey)))) {
-            struct dump_op *op = &ops[n_ops++];
+            if (flow_exists
+                && (purge
+                    || (seq_mismatch
+                        && !handle_missed_revalidation(revalidator, ukey)))) {
+                struct dump_op *op = &ops[n_ops++];
 
-            dump_op_init(op, ukey->key, ukey->key_len, ukey);
-            if (n_ops == REVALIDATE_MAX_BATCH) {
-                push_dump_ops(revalidator, ops, n_ops);
-                n_ops = 0;
+                dump_op_init(op, ukey->key, ukey->key_len, ukey);
+                if (n_ops == REVALIDATE_MAX_BATCH) {
+                    push_dump_ops(udpif, umap, ops, n_ops);
+                    n_ops = 0;
+                }
+            } else if (!flow_exists) {
+                ovs_mutex_lock(&umap->mutex);
+                ukey_delete(umap, ukey);
+                ovs_mutex_unlock(&umap->mutex);
             }
-        } else if (!flow_exists) {
-            ovs_mutex_lock(revalidator->mutex);
-            ukey_delete(revalidator, ukey);
-            ovs_mutex_unlock(revalidator->mutex);
         }
-    }
 
-    if (n_ops) {
-        push_dump_ops(revalidator, ops, n_ops);
-        ovsrcu_quiesce();
+        if (n_ops) {
+            push_dump_ops(udpif, umap, ops, n_ops);
+            ovsrcu_quiesce();
+        }
     }
 }
 
@@ -1688,8 +1700,15 @@ upcall_unixctl_show(struct unixctl_conn *conn, int argc OVS_UNUSED,
 
     LIST_FOR_EACH (udpif, list_node, &all_udpifs) {
         unsigned int flow_limit;
-        size_t i;
+        size_t i, elements[64];
+
+        ovs_assert(n_revalidators < 64);
 
+        memset(elements, 0, sizeof elements);
+        for (i = 0; i < udpif->n_umaps; i++) {
+            int idx = i % n_revalidators;
+            elements[idx] += cmap_count(&udpif->ukeys[i].cmap);
+        }
         atomic_read(&udpif->flow_limit, &flow_limit);
 
         ds_put_format(&ds, "%s:\n", dpif_name(udpif->dpif));
@@ -1703,7 +1722,7 @@ upcall_unixctl_show(struct unixctl_conn *conn, int argc OVS_UNUSED,
             struct revalidator *revalidator = &udpif->revalidators[i];
 
             ds_put_format(&ds, "\t%u: (keys %"PRIuSIZE")\n",
-                          revalidator->id, cmap_count(&udpif->ukeys[i].cmap));
+                          revalidator->id, elements[i]);
         }
     }
 
-- 
1.7.10.4




More information about the dev mailing list