[ovs-dev] [PATCH 2/2] [RFC] classifier: Add support for conjunctive matches.

Ben Pfaff blp at nicira.com
Thu Oct 30 06:46:28 UTC 2014


A "conjunctive match" allows higher-level matches in the flow table, such
as set membership matches, without causing a cross-product explosion for
multidimensional matches.  Please refer to the documentation that this
commit adds to ovs-ofctl(8) for a better explanation, including an example.

Issues:

- Until now the conceptual model of a cls_rule has been that it is
  immutable while it is in a classifier.  This commit adds a "conjunctive
  match" (optional) to each cls_rule, and makes the new member safely
  mutable while it is in a classifier.  This might be a conceptual failing
  bad enough to need fixing; I am not sure.

- Needs some real tests; you can run the "test-conjunction" script inside
  "make sandbox", for now.

- Fixing reg0 as the field to use for conjunctive match lookup doesn't seem
  too great.  We could make it configurable per-flow, or we could add a new
  field specifically for this purpose.  I am not sure that it should be
  fixed to 32 bits, either.

- The code needs some more comments.

- There is a memory leak in classifier_lookup() when conjunctive matches
  are used.  I'm not going to bother fixing it until the basic structure of
  the patch gets review.
---
 NEWS                         |   4 +
 lib/classifier-private.h     |   1 +
 lib/classifier.c             | 354 ++++++++++++++++++++++++++++++++++++++++---
 lib/classifier.h             |  11 ++
 lib/ofp-actions.c            | 109 ++++++++++++-
 lib/ofp-actions.h            |  12 ++
 lib/ofp-errors.h             |   8 +
 ofproto/ofproto-dpif-xlate.c |   4 +
 ofproto/ofproto.c            |  41 +++++
 tests/automake.mk            |   2 +
 tests/test-conjunction       |  22 +++
 utilities/ovs-ofctl.8.in     | 180 ++++++++++++++++++++++
 12 files changed, 722 insertions(+), 26 deletions(-)
 create mode 100755 tests/test-conjunction

diff --git a/NEWS b/NEWS
index 66e57bc..b6d9c00 100644
--- a/NEWS
+++ b/NEWS
@@ -1,5 +1,9 @@
 Post-v2.3.0
 ---------------------
+   - New support for a "conjunctive match" OpenFlow extension, which
+     allows constructing OpenFlow matches of the form "field1 in
+     {a,b,c...} AND field2 in {d,e,f...}" and generalizations.  For details,
+     see documentation fo the "conjunction" action in ovs-ofctl(8).
    - The "learn" action supports a new flag "delete_learned" that causes
      the learned flows to be deleted when the flow with the "learn" action
      is deleted.
diff --git a/lib/classifier-private.h b/lib/classifier-private.h
index 10d29a5..38938e0 100644
--- a/lib/classifier-private.h
+++ b/lib/classifier-private.h
@@ -78,6 +78,7 @@ struct cls_match {
     /* Accessed by all readers. */
     struct cmap_node cmap_node; /* Within struct cls_subtable 'rules'. */
     struct cls_rule *cls_rule;
+    OVSRCU_TYPE(struct cls_conjunction_set *) conj_set;
     struct miniflow flow;       /* Matching rule. Mask is in the subtable. */
     /* 'flow' must be the last field. */
 };
diff --git a/lib/classifier.c b/lib/classifier.c
index 284eab8..13657b8 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -31,6 +31,33 @@ VLOG_DEFINE_THIS_MODULE(classifier);
 
 struct trie_ctx;
 
+/* A collection of "struct cls_conjunction"s currently embedded into a
+ * cls_match. */
+struct cls_conjunction_set {
+    /* Link back to the cls_match.
+     *
+     * cls_conjunction_set is mostly used during classifier lookup, and, in
+     * turn, during classifier lookup the most used member of
+     * cls_conjunction_set is the rule's priority, so we cache it here for fast
+     * access. */
+    struct cls_match *match;
+    unsigned int priority;      /* Cached copy of match->priority. */
+
+    /* Conjunction information.
+     *
+     * 'min_n_clauses' allows some optimization during classifier lookup. */
+    unsigned int n;             /* Number of elements in 'conj'. */
+    unsigned int min_n_clauses; /* Smallest 'n' among elements of 'conj'. */
+    struct cls_conjunction conj[];
+};
+
+static inline size_t
+cls_conjunction_set_size(size_t n)
+{
+    return (sizeof(struct cls_conjunction_set)
+            + n * sizeof(struct cls_conjunction));
+}
+
 /* Ports trie depends on both ports sharing the same ovs_be32. */
 #define TP_PORTS_OFS32 (offsetof(struct flow, tp_src) / 4)
 BUILD_ASSERT_DECL(TP_PORTS_OFS32 == offsetof(struct flow, tp_dst) / 4);
@@ -47,6 +74,7 @@ cls_match_alloc(struct cls_rule *rule)
     cls_match->cls_rule = rule;
     miniflow_clone_inline(&cls_match->flow, &rule->match.flow, count);
     cls_match->priority = rule->priority;
+    ovsrcu_set_hidden(&cls_match->conj_set, NULL);
     rule->cls_match = cls_match;
 
     return cls_match;
@@ -169,6 +197,42 @@ cls_rule_destroy(struct cls_rule *rule)
     minimatch_destroy(&rule->match);
 }
 
+void
+cls_rule_set_conjunctions(struct cls_rule *cr,
+                          const struct cls_conjunction *conj, size_t n)
+{
+    struct cls_match *match = cr->cls_match;
+    struct cls_conjunction_set *old = ovsrcu_get_protected(struct cls_conjunction_set *, &match->conj_set);
+    struct cls_conjunction *old_conj = old ? old->conj : NULL;
+    unsigned int old_n = old ? old->n : 0;
+
+    if (old_n != n || (n && memcmp(old_conj, conj, n * sizeof *conj))) {
+        struct cls_conjunction_set *new;
+
+        if (old) {
+            ovsrcu_postpone(free, old);
+        }
+
+        if (n) {
+            size_t min_n_clauses = conj[0].n_clauses;
+            for (size_t i = 1; i < n; i++) {
+                min_n_clauses = MIN(min_n_clauses, conj[i].n_clauses);
+            }
+
+            new = xmalloc(cls_conjunction_set_size(n));
+            new->match = match;
+            new->priority = match->priority;
+            new->n = n;
+            new->min_n_clauses = min_n_clauses;
+            memcpy(new->conj, conj, n * sizeof *conj);
+        } else {
+            new = NULL;
+        }
+        ovsrcu_set(&match->conj_set, new);
+    }
+}
+
+
 /* Returns true if 'a' and 'b' match the same packets at the same priority,
  * false if they differ in some way. */
 bool
@@ -538,6 +602,7 @@ classifier_remove(struct classifier *cls, struct cls_rule *rule)
 {
     struct cls_partition *partition;
     struct cls_match *cls_match;
+    struct cls_conjunction_set *conj_set;
     struct cls_match *head;
     struct cls_subtable *subtable;
     int i;
@@ -623,6 +688,11 @@ classifier_remove(struct classifier *cls, struct cls_rule *rule)
 
     cls->n_rules--;
 
+    conj_set = ovsrcu_get_protected(struct cls_conjunction_set *,
+                                    &cls_match->conj_set);
+    if (conj_set) {
+        ovsrcu_postpone(free, conj_set);
+    }
     ovsrcu_postpone(free, cls_match);
     rule->cls_match = NULL;
 unlock:
@@ -654,24 +724,85 @@ trie_ctx_init(struct trie_ctx *ctx, const struct cls_trie *trie)
     ctx->lookup_done = false;
 }
 
-/* Finds and returns the highest-priority rule in 'cls' that matches 'flow'.
- * Returns a null pointer if no rules in 'cls' match 'flow'.  If multiple rules
- * of equal priority match 'flow', returns one arbitrarily.
- *
- * If a rule is found and 'wc' is non-null, bitwise-OR's 'wc' with the
- * set of bits that were significant in the lookup.  At some point
- * earlier, 'wc' should have been initialized (e.g., by
- * flow_wildcards_init_catchall()). */
-struct cls_rule *
-classifier_lookup(const struct classifier *cls, const struct flow *flow,
-                  struct flow_wildcards *wc)
+struct conjunctive_match {
+    struct hmap_node hmap_node;
+    uint64_t id;
+    uint64_t clauses;
+};
+
+static struct conjunctive_match *
+find_conjunctive_match__(struct hmap *matches, uint64_t id, uint32_t hash)
+{
+    struct conjunctive_match *m;
+
+    HMAP_FOR_EACH_IN_BUCKET (m, hmap_node, hash, matches) {
+        if (m->id == id) {
+            return m;
+        }
+    }
+    return NULL;
+}
+
+static bool
+find_conjunctive_match(const struct cls_conjunction_set *set,
+                       unsigned int max_n_clauses,
+                       struct hmap *matches, uint32_t *idp)
+{
+    const struct cls_conjunction *c;
+
+    if (max_n_clauses > set->min_n_clauses) {
+        return false;
+    }
+
+    for (c = set->conj; c < &set->conj[set->n]; c++) {
+        uint32_t hash = hash_int(c->id, 0);
+        struct conjunctive_match *m;
+
+        if (c->n_clauses > max_n_clauses) {
+            continue;
+        }
+
+        m = find_conjunctive_match__(matches, c->id, hash);
+        if (!m) {
+            m = xmalloc(sizeof *m);
+            hmap_insert(matches, &m->hmap_node, hash);
+            m->id = c->id;
+            m->clauses = UINT64_MAX << (c->n_clauses & 63);
+        }
+        m->clauses |= UINT64_C(1) << c->clause;
+        if (m->clauses == UINT64_MAX) {
+            *idp = m->id;
+            return true;
+        }
+    }
+    return false;
+}
+
+/* Like classifier_lookup(), except that support for conjunctive matches can be
+ * configured with 'allow_conjunctive_matches'.  That feature is not exposed
+ * externally because turning off conjunctive matches is only useful to avoid
+ * recursion within this function itself.  */
+static struct cls_rule *
+classifier_lookup__(const struct classifier *cls, const struct flow *flow,
+                    struct flow_wildcards *wc, bool allow_conjunctive_matches)
 {
     const struct cls_partition *partition;
-    tag_type tags;
-    unsigned int min_priority = 0;
-    const struct cls_match *best;
     struct trie_ctx trie_ctx[CLS_MAX_TRIES];
-    struct cls_subtable *subtable;
+    struct cls_match *match;
+    tag_type tags;
+
+    /* Highest-priority flow in 'cls' that certainly matches 'flow'. */
+    struct cls_match *hard = NULL;
+    unsigned int hard_pri = 0;  /* hard ? hard->priority + 1 : 0. */
+
+    /* Highest-priority conjunctive flows in 'cls' matching 'flow'.  Since
+     * these are (components of) conjunctive flows, we can only know whether
+     * the full conjunctive flow matches after seeing multiple of them.  Thus,
+     * we refer to these as "soft matches". */
+    struct cls_conjunction_set *soft_stub[64];
+    struct cls_conjunction_set **soft = soft_stub;
+    size_t n_soft = 0, allocated_soft = ARRAY_SIZE(soft_stub);
+    unsigned int soft_pri = 0;  /* n_soft ? MAX(soft[*]->priority) + 1 : 0. */
 
     /* Synchronize for cls->n_tries and subtable->trie_plen.  They can change
      * when table configuration changes, which happens typically only on
@@ -707,23 +838,198 @@ classifier_lookup(const struct classifier *cls, const struct flow *flow,
         trie_ctx_init(&trie_ctx[i], &cls->tries[i]);
     }
 
-    best = NULL;
-    PVECTOR_FOR_EACH_PRIORITY(subtable, min_priority, 2,
-                              sizeof(struct cls_subtable), &cls->subtables) {
-        struct cls_match *rule;
+    /* Main loop. */
+    struct cls_subtable *subtable;
+    PVECTOR_FOR_EACH_PRIORITY (subtable, hard_pri, 2, sizeof *subtable,
+                               &cls->subtables) {
+        struct cls_conjunction_set *conj_set;
 
+        /* Skip subtables not in our partition. */
         if (!tag_intersects(tags, subtable->tag)) {
             continue;
         }
 
-        rule = find_match_wc(subtable, flow, trie_ctx, cls->n_tries, wc);
-        if (rule->priority >= min_priority) {
-            min_priority = rule->priority + 1;
-            best = rule;
+        /* Skip subtables with no match, or where the match is lower-priority
+         * than some certain match we've already found. */
+        match = find_match_wc(subtable, flow, trie_ctx, cls->n_tries, wc);
+        if (!match || match->priority < hard_pri) {
+            continue;
+        }
+
+        conj_set = ovsrcu_get(struct cls_conjunction_set *, &match->conj_set);
+        if (!conj_set) {
+            /* 'match' isn't part of a conjunctive match.  It's the best
+             * certain match we've got so far, since we know that it's
+             * higher-priority than hard_pri.
+             *
+             * (There might be a higher-priority conjunctive match.  We can't
+             * tell yet.) */
+            hard = match;
+            hard_pri = hard->priority + 1;
+        } else if (allow_conjunctive_matches) {
+            /* 'match' is part of a conjunctive match.  Add it to the list. */
+            if (OVS_UNLIKELY(n_soft >= allocated_soft)) {
+                struct cls_conjunction_set **old_soft = soft;
+
+                allocated_soft *= 2;
+                soft = xmalloc(allocated_soft * sizeof *soft);
+                memcpy(soft, old_soft, n_soft * sizeof *soft);
+                if (old_soft != soft_stub) {
+                    free(old_soft);
+                }
+            }
+            soft[n_soft++] = conj_set;
+
+            /* Keep track of the highest-priority soft match. */
+            if (match->priority >= soft_pri) {
+                soft_pri = match->priority + 1;
+            }
+        }
+    }
+
+    /* In the common case, at this point we have no soft matches and we can
+     * return immediately.  (We do the same thing if we have potential soft
+     * matches but none of them are higher-priority than our hard match.)*/
+    if (hard_pri >= soft_pri) {
+        if (soft != soft_stub) {
+            free(soft);
+        }
+        return hard ? hard->cls_rule : NULL;
+    }
+
+    /* At this point, we have some soft matches.  We might also have a hard
+     * match; if so, its priority is lower than the highest-priority soft
+     * match. */
+
+    /* Soft match loop.
+     *
+     * Check whether soft matches are real matches. */
+    for (;;) {
+        /* Delete soft matches that are null.  This only happens in second and
+         * subsequent iterations of the soft match loop, when we drop back from
+         * a high-priority soft match to a lower-priority one.
+         *
+         * Also, delete soft matches whose priority is smaller than the hard
+         * match (if any).  In the first iteration of the soft match, these can
+         * be in 'soft' because the earlier main loop found the soft match
+         * before the hard match.  In second and later iteration of the soft
+         * match loop, these can be in 'soft' because we dropped back from a
+         * high-priority soft match to a lower-priority soft match.
+         *
+         * Also, delete soft matches that cannot be satisfied because there are
+         * fewer soft matches than required to satisfy any of their
+         * conjunctions.  Since deleting soft matches can cause this condition
+         * to become true for new soft matches, we iterate until we've deleted
+         * as many as possible. */
+        bool deleted;
+        do {
+            deleted = false;
+            for (int i = 0; i < n_soft; ) {
+                if (!soft[i]
+                    || soft[i]->priority <= hard_pri
+                    || n_soft < soft[i]->min_n_clauses) {
+                    deleted = true;
+                    soft[i] = soft[--n_soft];
+                } else {
+                    i++;
+                }
+            }
+        } while (deleted);
+        if (n_soft < 2) {
+            break;
+        }
+
+        /* Find the highest priority among the soft matches.  (We know this
+         * must be higher than the hard match's priority; otherwise we would
+         * have deleted all of the soft matches in the previous loop.)  Count
+         * the number of soft matches that have that priority. */
+        soft_pri = 0;
+        int n_soft_pri = 0;
+        for (int i = 0; i < n_soft; i++) {
+            if (soft[i]->priority + 1 > soft_pri) {
+                soft_pri = soft[i]->priority + 1;
+                n_soft_pri = 1;
+            } else if (soft[i]->priority + 1 == soft_pri) {
+                n_soft_pri++;
+            }
+        }
+        ovs_assert(soft_pri > hard_pri);
+
+        /* Look for a real match among the highest-priority soft matches. */
+        struct hmap matches;
+        hmap_init(&matches);
+        for (int i = 0; i < n_soft; i++) {
+            uint32_t id;
+
+            if (soft[i]->priority + 1 == soft_pri
+                && find_conjunctive_match(soft[i], n_soft_pri,
+                                          &matches, &id)) {
+                struct flow annotated_flow = *flow;
+                struct cls_rule *rule;
+
+                annotated_flow.regs[0] = id;
+                rule = classifier_lookup__(cls, &annotated_flow, wc, false);
+                if (rule) {
+                    if (soft != soft_stub) {
+                        free(soft);
+                    }
+                    hmap_destroy(&matches); /* XXX memory leak */
+                    return rule;
+                }
+            }
+        }
+        hmap_destroy(&matches); /* XXX memory leak */
+
+        /* There's no real match among the highest-priority soft matches.
+         * However, if any of those soft matches has a lower-priority but
+         * otherwise identical flow match, then we need to consider those for
+         * soft or hard matches.
+         *
+         * The next iteration of the soft match loop will delete any null
+         * pointers we put into 'soft' (and some others too). */
+        for (int i = 0; i < n_soft; i++) {
+            if (soft[i]->priority + 1 != soft_pri) {
+                continue;
+            }
+
+            /* Find next-lower-priority flow with identical flow match. */
+            match = next_rule_in_list(soft[i]->match);
+            if (match) {
+                soft[i] = ovsrcu_get(struct cls_conjunction_set *, &match->conj_set);
+                if (!soft[i]) {
+                    /* The flow is a hard match; don't treat as a soft
+                     * match. */
+                    if (match->priority >= hard_pri) {
+                        hard = match;
+                        hard_pri = hard->priority + 1;
+                    }
+                }
+            } else {
+                /* No such lower-priority flow (probably the common case). */
+                soft[i] = NULL;
+            }
         }
     }
 
-    return best ? best->cls_rule : NULL;
+    if (soft != soft_stub) {
+        free(soft);
+    }
+    return hard ? hard->cls_rule : NULL;
+}
+
+/* Finds and returns the highest-priority rule in 'cls' that matches 'flow'.
+ * Returns a null pointer if no rules in 'cls' match 'flow'.  If multiple rules
+ * of equal priority match 'flow', returns one arbitrarily.
+ *
+ * If a rule is found and 'wc' is non-null, bitwise-OR's 'wc' with the
+ * set of bits that were significant in the lookup.  At some point
+ * earlier, 'wc' should have been initialized (e.g., by
+ * flow_wildcards_init_catchall()). */
+struct cls_rule *
+classifier_lookup(const struct classifier *cls, const struct flow *flow,
+                  struct flow_wildcards *wc)
+{
+    return classifier_lookup__(cls, flow, wc, true);
 }
 
 /* Finds and returns a rule in 'cls' with exactly the same priority and
diff --git a/lib/classifier.h b/lib/classifier.h
index c910ac4..a417b5f 100644
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -255,6 +255,12 @@ struct classifier {
     unsigned int n_tries;
 };
 
+struct cls_conjunction {
+    uint32_t id;
+    uint8_t clause;
+    uint8_t n_clauses;
+};
+
 /* A rule to be inserted to the classifier. */
 struct cls_rule {
     struct minimatch match;      /* Matching rule. */
@@ -266,10 +272,15 @@ void cls_rule_init(struct cls_rule *, const struct match *,
                    unsigned int priority);
 void cls_rule_init_from_minimatch(struct cls_rule *, const struct minimatch *,
                                   unsigned int priority);
+void cls_rule_init_conjunction(struct cls_rule *,
+                               const struct cls_conjunction *, size_t n);
 void cls_rule_clone(struct cls_rule *, const struct cls_rule *);
 void cls_rule_move(struct cls_rule *dst, struct cls_rule *src);
 void cls_rule_destroy(struct cls_rule *);
 
+void cls_rule_set_conjunctions(struct cls_rule *,
+                               const struct cls_conjunction *, size_t n);
+
 bool cls_rule_equal(const struct cls_rule *, const struct cls_rule *);
 uint32_t cls_rule_hash(const struct cls_rule *, uint32_t basis);
 
diff --git a/lib/ofp-actions.c b/lib/ofp-actions.c
index 41c7622..1d936b1 100644
--- a/lib/ofp-actions.c
+++ b/lib/ofp-actions.c
@@ -279,6 +279,9 @@ enum ofp_raw_action_type {
 
     /* NX1.0+(29): struct nx_action_sample. */
     NXAST_RAW_SAMPLE,
+
+    /* NX1.0+(34): struct nx_action_conjunction. */
+    NXAST_RAW_CONJUNCTION,
 };
 
 /* OpenFlow actions are always a multiple of 8 bytes in length. */
@@ -3845,6 +3848,86 @@ format_LEARN(const struct ofpact_learn *a, struct ds *s)
     learn_format(a, s);
 }
 
+/* Action structure for NXAST_CONJUNCTION. */
+struct nx_action_conjunction {
+    ovs_be16 type;                  /* OFPAT_VENDOR. */
+    ovs_be16 len;                   /* At least 16. */
+    ovs_be32 vendor;                /* NX_VENDOR_ID. */
+    ovs_be16 subtype;               /* See enum ofp_raw_action_type. */
+    uint8_t clause;
+    uint8_t n_clauses;
+    ovs_be32 id;
+};
+OFP_ASSERT(sizeof(struct nx_action_conjunction) == 16);
+
+static void
+add_conjunction(struct ofpbuf *out,
+                uint32_t id, uint8_t clause, uint8_t n_clauses)
+{
+    struct ofpact_conjunction *oc;
+
+    oc = ofpact_put_CONJUNCTION(out);
+    oc->id = id;
+    oc->clause = clause;
+    oc->n_clauses = n_clauses;
+}
+
+static enum ofperr
+decode_NXAST_RAW_CONJUNCTION(const struct nx_action_conjunction *nac,
+                             struct ofpbuf *out)
+{
+    if (nac->n_clauses < 2 || nac->n_clauses > 64
+        || nac->clause >= nac->n_clauses) {
+        return OFPERR_NXBAC_BAD_CONJUNCTION;
+    } else {
+        add_conjunction(out, ntohl(nac->id), nac->clause, nac->n_clauses);
+        return 0;
+    }
+}
+
+static void
+encode_CONJUNCTION(const struct ofpact_conjunction *oc,
+                   enum ofp_version ofp_version OVS_UNUSED, struct ofpbuf *out)
+{
+    struct nx_action_conjunction *nac = put_NXAST_CONJUNCTION(out);
+    nac->clause = oc->clause;
+    nac->n_clauses = oc->n_clauses;
+    nac->id = htonl(oc->id);
+}
+
+static void
+format_CONJUNCTION(const struct ofpact_conjunction *oc, struct ds *s)
+{
+    ds_put_format(s, "conjunction(%"PRIu32",%"PRIu8"/%"PRIu8")",
+                  oc->id, oc->clause, oc->n_clauses);
+}
+
+static char * WARN_UNUSED_RESULT
+parse_CONJUNCTION(const char *arg, struct ofpbuf *ofpacts,
+                  enum ofputil_protocol *usable_protocols OVS_UNUSED)
+{
+    uint8_t n_clauses;
+    uint8_t clause;
+    uint32_t id;
+    int n;
+
+    if (!ovs_scan(arg, "%"SCNi32" , %"SCNu8" / %"SCNu8" %n",
+                  &id, &clause, &n_clauses, &n) || n != strlen(arg)) {
+        return xstrdup("\"conjunction\" syntax is \"conjunction(id,i/n)\"");
+    }
+
+    if (n_clauses < 2) {
+        return xstrdup("conjunction must have at least 2 clauses");
+    } else if (n_clauses > 64) {
+        return xstrdup("conjunction must have at most 64 clauses");
+    } else if (clause >= n_clauses) {
+        return xstrdup("clause index must be less than number of clauses");
+    }
+
+    add_conjunction(ofpacts, id, clause, n_clauses);
+    return NULL;
+}
+
 /* Action structure for NXAST_MULTIPATH.
  *
  * This action performs the following steps in sequence:
@@ -4591,6 +4674,7 @@ ofpact_is_set_or_move_action(const struct ofpact *a)
     case OFPACT_GOTO_TABLE:
     case OFPACT_GROUP:
     case OFPACT_LEARN:
+    case OFPACT_CONJUNCTION:
     case OFPACT_METER:
     case OFPACT_MULTIPATH:
     case OFPACT_NOTE:
@@ -4657,6 +4741,7 @@ ofpact_is_allowed_in_actions_set(const struct ofpact *a)
     case OFPACT_EXIT:
     case OFPACT_FIN_TIMEOUT:
     case OFPACT_LEARN:
+    case OFPACT_CONJUNCTION:
     case OFPACT_MULTIPATH:
     case OFPACT_NOTE:
     case OFPACT_OUTPUT_REG:
@@ -4872,6 +4957,7 @@ ovs_instruction_type_from_ofpact_type(enum ofpact_type type)
     case OFPACT_FIN_TIMEOUT:
     case OFPACT_RESUBMIT:
     case OFPACT_LEARN:
+    case OFPACT_CONJUNCTION:
     case OFPACT_MULTIPATH:
     case OFPACT_NOTE:
     case OFPACT_EXIT:
@@ -5409,6 +5495,9 @@ ofpact_check__(enum ofputil_protocol *usable_protocols, struct ofpact *a,
     case OFPACT_LEARN:
         return learn_check(ofpact_get_LEARN(a), flow);
 
+    case OFPACT_CONJUNCTION:
+        return 0;
+
     case OFPACT_MULTIPATH:
         return multipath_check(ofpact_get_MULTIPATH(a), flow);
 
@@ -5530,8 +5619,12 @@ ofpacts_check_consistency(struct ofpact ofpacts[], size_t ofpacts_len,
             : 0);
 }
 
-/* Verifies that the 'ofpacts_len' bytes of actions in 'ofpacts' are
- * in the appropriate order as defined by the OpenFlow spec. */
+/* Verifies that the 'ofpacts_len' bytes of actions in 'ofpacts' are in the
+ * appropriate order as defined by the OpenFlow spec and as required by Open
+ * vSwitch.
+ *
+ * 'allowed_ovsinsts' is a bitmap of OVSINST_* values, in which 1-bits indicate
+ * instructions that are allowed within 'ofpacts[]'. */
 static enum ofperr
 ofpacts_verify(const struct ofpact ofpacts[], size_t ofpacts_len,
                uint32_t allowed_ovsinsts)
@@ -5543,6 +5636,17 @@ ofpacts_verify(const struct ofpact ofpacts[], size_t ofpacts_len,
     OFPACT_FOR_EACH (a, ofpacts, ofpacts_len) {
         enum ovs_instruction_type next;
 
+        if (a->type == OFPACT_CONJUNCTION) {
+            OFPACT_FOR_EACH (a, ofpacts, ofpacts_len) {
+                if (a->type != OFPACT_CONJUNCTION) {
+                    VLOG_WARN("when %s action is present, it must be the only "
+                              "kind of action used", ofpact_name(a->type));
+                    return OFPERR_NXBAC_BAD_CONJUNCTION;
+                }
+            }
+            return 0;
+        }
+
         next = ovs_instruction_type_from_ofpact_type(a->type);
         if (a > ofpacts
             && (inst == OVSINST_OFPIT11_APPLY_ACTIONS
@@ -5841,6 +5945,7 @@ ofpact_outputs_to_port(const struct ofpact *ofpact, ofp_port_t port)
     case OFPACT_FIN_TIMEOUT:
     case OFPACT_RESUBMIT:
     case OFPACT_LEARN:
+    case OFPACT_CONJUNCTION:
     case OFPACT_MULTIPATH:
     case OFPACT_NOTE:
     case OFPACT_EXIT:
diff --git a/lib/ofp-actions.h b/lib/ofp-actions.h
index e863cdc..2302de0 100644
--- a/lib/ofp-actions.h
+++ b/lib/ofp-actions.h
@@ -19,6 +19,7 @@
 
 #include <stddef.h>
 #include <stdint.h>
+#include "classifier.h"
 #include "meta-flow.h"
 #include "ofp-errors.h"
 #include "ofp-util.h"
@@ -96,6 +97,7 @@
     /* Flow table interaction. */                                       \
     OFPACT(RESUBMIT,        ofpact_resubmit,    ofpact, "resubmit")     \
     OFPACT(LEARN,           ofpact_learn,       specs, "learn")         \
+    OFPACT(CONJUNCTION,     ofpact_conjunction, ofpact, "conjunction")  \
                                                                         \
     /* Arithmetic. */                                                   \
     OFPACT(MULTIPATH,       ofpact_multipath,   ofpact, "multipath")    \
@@ -611,6 +613,16 @@ enum nx_mp_algorithm {
     NX_MP_ALG_ITER_HASH = 3,
 };
 
+/* OFPACT_CONJUNCTION.
+ *
+ * Used for NXAST_CONJUNCTION. */
+struct ofpact_conjunction {
+    struct ofpact ofpact;
+    uint8_t clause;
+    uint8_t n_clauses;
+    uint32_t id;
+};
+
 /* OFPACT_MULTIPATH.
  *
  * Used for NXAST_MULTIPATH. */
diff --git a/lib/ofp-errors.h b/lib/ofp-errors.h
index 2516b39..a9237c3 100644
--- a/lib/ofp-errors.h
+++ b/lib/ofp-errors.h
@@ -230,6 +230,14 @@ enum ofperr {
      * value. */
     OFPERR_NXBAC_MUST_BE_ZERO,
 
+    /* NX1.0-1.1(2,526), NX1.2+(15).  Conjunction action must be only action
+     * present.  Conjunction action must have at least one clause. */
+    OFPERR_NXBAC_BAD_CONJUNCTION,
+
+    /* NX1.0-1.1(2,527), NX1.2+(16).  Conjunction actions may not be modified.
+     * (Instead, remove the flow and add a new one in its place.) */
+    OFPERR_NXBAC_READONLY_CONJUNCTION,
+
 /* ## --------------------- ## */
 /* ## OFPET_BAD_INSTRUCTION ## */
 /* ## --------------------- ## */
diff --git a/ofproto/ofproto-dpif-xlate.c b/ofproto/ofproto-dpif-xlate.c
index e9bb4ff..730fe77 100644
--- a/ofproto/ofproto-dpif-xlate.c
+++ b/ofproto/ofproto-dpif-xlate.c
@@ -3570,6 +3570,7 @@ ofpact_needs_recirculation_after_mpls(const struct xlate_ctx *ctx,
     case OFPACT_SET_MPLS_TTL:
     case OFPACT_SET_MPLS_TC:
     case OFPACT_SET_MPLS_LABEL:
+    case OFPACT_CONJUNCTION:
     case OFPACT_NOTE:
     case OFPACT_OUTPUT_REG:
     case OFPACT_EXIT:
@@ -3872,6 +3873,9 @@ do_xlate_actions(const struct ofpact *ofpacts, size_t ofpacts_len,
             xlate_learn_action(ctx, ofpact_get_LEARN(a));
             break;
 
+        case OFPACT_CONJUNCTION:
+            break;
+
         case OFPACT_EXIT:
             ctx->exit = true;
             break;
diff --git a/ofproto/ofproto.c b/ofproto/ofproto.c
index b8f0e62..e87dfa4 100644
--- a/ofproto/ofproto.c
+++ b/ofproto/ofproto.c
@@ -4124,6 +4124,45 @@ evict_rules_from_table(struct oftable *table, unsigned int extra_space)
     return 0;
 }
 
+static bool
+is_conjunction(const struct ofpact *ofpacts, size_t ofpacts_len)
+{
+    return ofpacts_len > 0 && ofpacts->type == OFPACT_CONJUNCTION;
+}
+
+static void
+set_conjunction(struct rule *rule)
+    OVS_REQUIRES(ofproto_mutex)
+{
+    struct cls_rule *cr = CONST_CAST(struct cls_rule *, &rule->cr);
+    const struct rule_actions *actions = rule_get_actions(rule);
+    if (is_conjunction(actions->ofpacts, actions->ofpacts_len)) {
+        struct cls_conjunction *conjs;
+        const struct ofpact *ofpact;
+        int n_conjs;
+        int i;
+
+        n_conjs = 0;
+        OFPACT_FOR_EACH (ofpact, actions->ofpacts, actions->ofpacts_len) {
+            n_conjs++;
+        }
+
+        conjs = xzalloc(n_conjs * sizeof *conjs);
+        i = 0;
+        OFPACT_FOR_EACH (ofpact, actions->ofpacts, actions->ofpacts_len) {
+            struct ofpact_conjunction *oc = ofpact_get_CONJUNCTION(ofpact);
+            conjs[i].clause = oc->clause;
+            conjs[i].n_clauses = oc->n_clauses;
+            conjs[i].id = oc->id;
+            i++;
+        }
+        cls_rule_set_conjunctions(cr, conjs, n_conjs);
+        free(conjs);
+    } else {
+        cls_rule_set_conjunctions(cr, NULL, 0);
+    }
+}
+
 /* Implements OFPFC_ADD and the cases for OFPFC_MODIFY and OFPFC_MODIFY_STRICT
  * in which no matching flow already exists in the flow table.
  *
@@ -4269,6 +4308,7 @@ add_flow(struct ofproto *ofproto, struct ofputil_flow_mod *fm,
     }
 
     classifier_insert(&table->cls, CONST_CAST(struct cls_rule *, &rule->cr));
+    set_conjunction(rule);
 
     error = ofproto->ofproto_class->rule_insert(rule);
     if (error) {
@@ -4379,6 +4419,7 @@ modify_flows__(struct ofproto *ofproto, struct ofputil_flow_mod *fm,
         if (change_actions) {
             ovsrcu_set(&rule->actions, rule_actions_create(fm->ofpacts,
                                                            fm->ofpacts_len));
+            set_conjunction(rule);
         }
 
         if (change_actions || reset_counters) {
diff --git a/tests/automake.mk b/tests/automake.mk
index 1f13230..89b7d8a 100644
--- a/tests/automake.mk
+++ b/tests/automake.mk
@@ -314,3 +314,5 @@ clean-pki:
 	rm -f tests/pki/stamp
 	rm -rf tests/pki
 endif
+
+EXTRA_DIST += tests/test-conjunction
diff --git a/tests/test-conjunction b/tests/test-conjunction
new file mode 100755
index 0000000..46bde14
--- /dev/null
+++ b/tests/test-conjunction
@@ -0,0 +1,22 @@
+#! /bin/sh
+ovs-vsctl --may-exist add-br br0
+ovs-ofctl del-flows br0
+ovs-ofctl add-flows br0 - <<EOF
+reg0=1,ip,actions=mod_dl_src:00:11:22:33:44:55,local
+ip,ip_src=10.0.0.1,actions=conjunction(1,0/2)
+ip,ip_src=10.0.0.4,actions=conjunction(1,0/2)
+ip,ip_src=10.0.0.6,actions=conjunction(1,0/2)
+ip,ip_src=10.0.0.7,actions=conjunction(1,0/2)
+ip,ip_dst=10.0.0.2,actions=conjunction(1,1/2)
+ip,ip_dst=10.0.0.5,actions=conjunction(1,1/2)
+ip,ip_dst=10.0.0.7,actions=conjunction(1,1/2)
+ip,ip_dst=10.0.0.8,actions=conjunction(1,1/2)
+EOF
+
+# This should match the conjunctive flow and thus change the Ethernet
+# source address and output to local.
+ovs-appctl ofproto/trace br0 tcp,ip_src=10.0.0.1,ip_dst=10.0.0.5
+printf "%s\n\n" '------------------------------------------------------------'
+
+# This should not match anything and thus get dropped.
+ovs-appctl ofproto/trace br0 tcp,ip_src=10.0.0.2,ip_dst=10.0.0.5
diff --git a/utilities/ovs-ofctl.8.in b/utilities/ovs-ofctl.8.in
index bcc3f33..289d87b 100644
--- a/utilities/ovs-ofctl.8.in
+++ b/utilities/ovs-ofctl.8.in
@@ -1757,6 +1757,186 @@ unaffected.  Any further actions, including those which may be in
 other tables, or different levels of the \fBresubmit\fR call stack,
 are ignored.  Actions in the action set is still executed (specify
 \fBclear_actions\fR before \fBexit\fR to discard them).
+.
+.IP "\fBconjunction(\fIid\fB, \fIk\fB/\fIn\fR\fB)\fR"
+An individual OpenFlow flow can match only a single value for each
+field.  However, situations often arise where one wants to match one
+of a set of values within a field or fields.  For matching a single
+field against a set, it is straightforward and efficient to add
+multiple flows to the flow table, one for each value in the set.  For
+example, one might use the following flows to send packets with IP
+source address \fIa\fR, \fIb\fR, \fIc\fR, or \fId\fR to the OpenFlow
+controller:
+.RS +1in
+.br
+\fBip,ip_src=\fIa\fB actions=controller\fR
+.br
+\fBip,ip_src=\fIb\fB actions=controller\fR
+.br
+\fBip,ip_src=\fIc\fB actions=controller\fR
+.br
+\fBip,ip_src=\fId\fB actions=controller\fR
+.br
+.RE
+.IP
+Similarly, these flows send packets with IP destination address
+\fIe\fR, \fIf\fR, \fIg\fR, or \fIh\fR to the OpenFlow controller:
+.RS +1in
+.br
+\fBip,ip_dst=\fIe\fB actions=controller\fR
+.br
+\fBip,ip_dst=\fIf\fB actions=controller\fR
+.br
+\fBip,ip_dst=\fIg\fB actions=controller\fR
+.br
+\fBip,ip_dst=\fIh\fB actions=controller\fR
+.br
+.RE
+.IP
+Installing all of the above flows in a single flow table yields a
+disjunctive effect: a packet is sent to the controller if \fBip_src\fR
+\[mo] {\fIa\fR,\fIb\fR,\fIc\fR,\fId\fR} or \fBip_dst\fR \[mo]
+{\fIe\fR,\fIf\fR,\fIg\fR,\fIh\fR} (or both).  (Pedantically, if both
+of the above sets of flows are present in the flow table, they should
+have different priorities, because OpenFlow says that the results are
+undefined when two flows with same priority can both match a single
+packet.)
+.IP
+Suppose, on the other hand, one wishes to match conjunctively, that
+is, to send a packet to the controller only if both \fBip_src\fR \[mo]
+{\fIa\fR,\fIb\fR,\fIc\fR,\fId\fR} and \fBip_dst\fR \[mo]
+{\fIe\fR,\fIf\fR,\fIg\fR,\fIh\fR}.  This requires 4 \[mu] 4 = 16
+flows, one for each possible pairing of \fBip_src\fR and \fBip_dst\fR.
+That is acceptable for our small example, but it does not gracefully
+extend to larger sets or greater numbers of dimensions.
+.IP
+The \fBconjunction\fR action is a solution for conjunctive matches
+that is built into Open vSwitch.  A \fBconjunction\fR action ties
+groups of individual OpenFlow flows into higher-level ``conjunctive
+flows''.  Each group corresponds to one dimension, and each flow
+within the group matches one possible value for the dimension .  A
+packet that matches one flow from each group matches the conjunctive
+flow.
+.IP
+To implement a conjunctive flow with \Bconjunction\fR, assign the
+conjunctive flow a 32-bit \fIid\fR, which must be unique within an
+OpenFlow table.  Assign each of the \fIn\fR \[>=] 2 dimensions a
+unique number from 0 to \fIn - 1\fR; the ordering is unimportant.  Add
+one flow to the OpenFlow flow table for each possible value of each
+dimension with \fBconjunction(\fIid, \fIk\fB/\fIn\fB)\fR as the flow's
+actions, where \fIk\fR is the number assigned to the flow's dimension.
+Together, these flows specify the conjunctive flow's match condition.
+When the conjunctive match condition is met, Open vSwitch looks up one
+more flow that specifies the conjunctive flow's actions and receives
+its statistics.  This flow is found by replacing \fBreg0\fR by the
+specified \fIid\fR and then again searching the flow table.
+.IP
+The following flows provide an example.  Whenever the IP source is one
+of the values in the flows that match on the IP source (dimension 0 of
+2), \fIand\fR the IP destination is one of the values in the flows
+that match on IP destination (dimension 0 of 2), Open vSwitch searches
+for a flow that matches \fBreg0\fR against the conjunction ID (1234),
+finding the first flow in the flow table.
+.RS +1in
+.br
+.B "reg0=1234 actions=controller"
+.br
+.B "ip,ip_src=10.0.0.1 actions=conjunction(1234, 0/2)"
+.br
+.B "ip,ip_src=10.0.0.4 actions=conjunction(1234, 0/2)"
+.br
+.B "ip,ip_src=10.0.0.6 actions=conjunction(1234, 0/2)"
+.br
+.B "ip,ip_src=10.0.0.7 actions=conjunction(1234, 0/2)"
+.br
+.B "ip,ip_dst=10.0.0.2 actions=conjunction(1234, 1/2)"
+.br
+.B "ip,ip_dst=10.0.0.5 actions=conjunction(1234, 1/2)"
+.br
+.B "ip,ip_dst=10.0.0.7 actions=conjunction(1234, 1/2)"
+.br
+.B "ip,ip_dst=10.0.0.8 actions=conjunction(1234, 1/2)"
+.RE
+.IP
+Many subtleties exist:
+.RS
+.IP \(bu
+In the example above, every flow in a single dimension has the same
+form, that is, dimension 0 matches on \fBip_src\fR, dimension 1 on
+\fBip_dst\fR, but this is not a requirement.  Different flows within a
+dimension may match on different bits within a field (e.g. IP network
+prefixes of different lengths, or TCP/UDP port ranges as bitwise
+matches), or even on entirely different fields (e.g. to match packets
+for TCP source port 80 or TCP destination port 80).
+.IP \(bu
+The flows within a dimension can vary their matches across more than
+one field, e.g. to match only specific pairs of IP source and
+destination addresses or L4 port numbers.
+.IP \(bu
+A flow may have multiple \fBconjunction\fR actions, with different
+\fIid\fR values.  This is useful for multiple conjunctive flows with
+overlapping sets.  If one conjunctive flow matches packets with both
+\fBip_src\fR \[mo] {\fIa\fR,\fIb\fR} and \fBip_dst\fR \[mo]
+{\fId\fR,\fIe\fR} and a second conjunctive flow matches \fBip_src\fR
+\[mo] {\fIb\fR,\fIc\fR} and \fBip_dst\fR \[mo] {\fIf\fR,\fIg\fR}, for
+example, then the flow that matches \fBip_src=\fIb\fR would have two
+\fBconjunction\fR actions, one for each conjunctive flow.  The order
+of \fBconjunction\fR actions within a list of actions is not
+significant.
+.IP \(bu
+A flow with \fBconjunction\fR actions may not have any other actions.
+(It would not be useful.)
+.IP \(bu
+All of the flows that constitute a conjunctive flow with a given
+\fIid\fR must have the same priority.  (Flows with the same \fIid\fR
+but different priorities are currently treated as different
+conjunctive flows, that is, currently \fIid\fR values need only be
+unique within an OpenFlow table at a given priority.  This behavior
+isn't guaranteed to stay the same in later releases, so please use
+\fIid\fR values unique within an OpenFlow table.)
+.IP \(bu
+Conjunctive flows must not overlap with each other, at a given
+priority, that is, any given packet must be able to match at most one
+conjunctive flow at a given priority.  Overlapping conjunctive flows
+yield unpredictable results.
+.IP \(bu
+Following a conjunctive flow match, the search for the flow with
+\fBreg0=\fIid\fR is done in the same general-purpose way as other flow
+table searches, so one can use flows with \fBreg0=\fIid\fR to act
+differently depending on circumstances.  (One exception is that the
+search for the \fBreg0=\fIid\fR flow itself ignores conjunctive flows,
+to avoid recursion.) If the search with \fBreg0=\fIid\fR fails, Open
+vSwitch acts as if the conjunctive flow had not matched at all, and
+continues searching the flow table for other matching flows.
+.IP \(bu
+OpenFlow prerequisite checking occurs for the flow with
+\fBreg0=\fIid\fR in the same way as any other flow, e.g. in an
+OpenFlow 1.1+ context, putting a \fBmod_nw_src\fR action into the
+example above would require adding an \fBip\fR match, like this:
+.RS +1in
+.br
+.B "reg0=1234,ip actions=mod_nw_src:1.2.3.4,controller"
+.br
+.RE
+.IP \(bu
+The flows that constitute a conjunctive flow do not have useful
+statistics.  They are never updated with byte or packet counts, and so
+on.  (For such a flow, therefore, the idle and hard timeouts work much
+the same way.)
+.IP \(bu
+Conjunctive flows can be a useful building block for negation, that
+is, inequality matches like \fBtcp_src\fR \[!=] 80.  To implement an
+inequality match, convert it to a pair of range matches, e.g. 0 \[<=]
+\fBtcp_src\ < 80 and 80 < \fBtcp_src\fR \[<=] 65535, then convert each
+of the range matches into a collection of bitwise matches as explained
+above in the description of \fBtcp_src\fR.
+.IP \(bu
+A conjunctive match must have \fIn\fR \[>=] 2 dimensions (otherwise a
+conjunctive match is not necessary).  Open vSwitch enforces this.
+.IP \(bu
+Each dimension within a conjunctive match should ordinarily have more
+than one flow.  Open vSwitch does not enforce this.
+.RE
 .RE
 .
 .PP
-- 
2.1.0




More information about the dev mailing list