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

Ben Pfaff blp at nicira.com
Fri Jan 9 19:44:07 UTC 2015


Thanks.

I posted v3:
        http://openvswitch.org/pipermail/dev/2015-January/050297.html
        http://openvswitch.org/pipermail/dev/2015-January/050296.html

I posted it marked as [RFC], but that's a mistake: I consider this now
ready for review.

On Tue, Jan 06, 2015 at 02:45:34PM -0800, Jarno Rajahalme wrote:
> I?ll review the v3 when ready,
> 
>   Jarno
> 
> On Dec 30, 2014, at 4:30 PM, Ben Pfaff <blp at nicira.com> wrote:
> 
> > 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.
> > 
> > - The code needs some more comments.
> > ---
> > v1->v2:
> >  - Use 1-based dimension numbers in formatted syntax, e.g. 1/2 and 2/2,
> >    not 0/2 and 1/2.
> >  - Add new conj_id field instead of overwriting reg0.
> >  - Since priority is now an 'int', get rid of awkward +1s and comparisons
> >    on priorities in classifier_lookup().
> >  - Fix memory leak in classifier_replace().
> >  - Modify conj_id in-place in classifier_lookup() instead of copying
> >    entire flow.
> >  - Remove prototype for nonexistent cls_rule_init_conjunction().
> >  - Fix memory leak in classifier_lookup(), and eliminate memory allocation
> >    in the common case of few conjunctive matches.
> > 
> > v2->v2.1:
> >  - Rebase.
> > ---
> > NEWS                         |    4 +
> > lib/classifier-private.h     |    3 +-
> > lib/classifier.c             |  396 +++++++++++++++++++++++++++++++++++++++---
> > lib/classifier.h             |   10 ++
> > lib/flow.c                   |    1 +
> > lib/flow.h                   |    3 +-
> > lib/match.c                  |   11 ++
> > lib/match.h                  |    3 +-
> > lib/meta-flow.c              |   17 ++
> > lib/meta-flow.h              |   14 ++
> > lib/nx-match.c               |    4 +
> > lib/ofp-actions.c            |  112 +++++++++++-
> > 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/ofproto.at             |    3 +-
> > tests/test-conjunction       |   22 +++
> > utilities/ovs-ofctl.8.in     |  185 ++++++++++++++++++++
> > 20 files changed, 825 insertions(+), 30 deletions(-)
> > create mode 100755 tests/test-conjunction
> > 
> > diff --git a/NEWS b/NEWS
> > index f2fceb5..0bbe6f7 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).
> >    - Add bash command-line completion support for ovs-appctl/ovs-dpctl/
> >      ovs-ofctl/ovsdb-tool commands.  Please check
> >      utilities/ovs-command-compgen.INSTALL.md for how to use.
> > diff --git a/lib/classifier-private.h b/lib/classifier-private.h
> > index 2522e91..2230286 100644
> > --- a/lib/classifier-private.h
> > +++ b/lib/classifier-private.h
> > @@ -68,7 +68,7 @@ struct cls_partition {
> > /* Internal representation of a rule in a "struct cls_subtable". */
> > struct cls_match {
> >     /* Accessed by everybody. */
> > -    struct rculist list; /* Identical, lower-priority rules. */
> > +    struct rculist list; /* Identical, lower-priority "cls_match"es. */
> > 
> >     /* Accessed only by writers. */
> >     struct cls_partition *partition;
> > @@ -80,6 +80,7 @@ struct cls_match {
> >     /* Accessed by all readers. */
> >     struct cmap_node cmap_node; /* Within struct cls_subtable 'rules'. */
> >     const struct cls_rule *cls_rule;
> > +    OVSRCU_TYPE(struct cls_conjunction_set *) conj_set;
> >     const 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 dd60cc7..36194d2 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;
> > +    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);
> > @@ -49,6 +76,7 @@ cls_match_alloc(const struct cls_rule *rule)
> >     *CONST_CAST(int *, &cls_match->priority) = rule->priority;
> >     miniflow_clone_inline(CONST_CAST(struct miniflow *, &cls_match->flow),
> >                           &rule->match.flow, count);
> > +    ovsrcu_set_hidden(&cls_match->conj_set, NULL);
> > 
> >     return cls_match;
> > }
> > @@ -199,6 +227,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
> > @@ -593,6 +657,14 @@ classifier_replace(struct classifier *cls, const struct cls_rule *rule)
> >             }
> > 
> >             if (old) {
> > +                struct cls_conjunction_set *conj_set;
> > +
> > +                conj_set = ovsrcu_get_protected(struct cls_conjunction_set *,
> > +                                                &iter->conj_set);
> > +                if (conj_set) {
> > +                    ovsrcu_postpone(free, conj_set);
> > +                }
> > +
> >                 ovsrcu_postpone(free, iter);
> >                 old->cls_match = NULL;
> > 
> > @@ -669,6 +741,7 @@ classifier_remove(struct classifier *cls, const struct cls_rule *rule)
> > {
> >     struct cls_partition *partition;
> >     struct cls_match *cls_match;
> > +    struct cls_conjunction_set *conj_set;
> >     struct cls_subtable *subtable;
> >     struct cls_match *prev;
> >     struct cls_match *next;
> > @@ -779,6 +852,11 @@ check_priority:
> >     }
> > 
> > free:
> > +    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);
> >     cls->n_rules--;
> > 
> > @@ -808,27 +886,107 @@ 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 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,
> > +                       struct conjunctive_match *cm_stubs, size_t n_cm_stubs,
> > +                       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 *cm;
> > +
> > +        if (c->n_clauses > max_n_clauses) {
> > +            continue;
> > +        }
> > +
> > +        cm = find_conjunctive_match__(matches, c->id, hash);
> > +        if (!cm) {
> > +            size_t n = hmap_count(matches);
> > +            cm = n < n_cm_stubs ? &cm_stubs[n++] : xmalloc(sizeof *cm);
> > +            hmap_insert(matches, &cm->hmap_node, hash);
> > +            cm->id = c->id;
> > +            cm->clauses = UINT64_MAX << (c->n_clauses & 63);
> > +        }
> > +        cm->clauses |= UINT64_C(1) << c->clause;
> > +        if (cm->clauses == UINT64_MAX) {
> > +            *idp = cm->id;
> > +            return true;
> > +        }
> > +    }
> > +    return false;
> > +}
> > +
> > +static void
> > +free_conjunctive_matches(struct hmap *matches,
> > +                         struct conjunctive_match *cm_stubs, size_t n_cm_stubs)
> > +{
> > +    if (hmap_count(matches) > n_cm_stubs) {
> > +        struct conjunctive_match *cm, *next;
> > +
> > +        HMAP_FOR_EACH_SAFE (cm, next, hmap_node, matches) {
> > +            if (!(cm >= cm_stubs && cm < &cm_stubs[n_cm_stubs])) {
> > +                hmap_remove(matches, &cm->hmap_node);
> > +                free(cm);
> > +            }
> > +        }
> > +    }
> > +    hmap_destroy(matches);
> > +}
> > +
> > +/* 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.
> >  *
> >  * 'flow' is non-const to allow for temporary modifications during the lookup.
> >  * Any changes are restored before returning. */
> > -const struct cls_rule *
> > -classifier_lookup(const struct classifier *cls, struct flow *flow,
> > -                  struct flow_wildcards *wc)
> > +static const struct cls_rule *
> > +classifier_lookup__(const struct classifier *cls, struct flow *flow,
> > +                    struct flow_wildcards *wc, bool allow_conjunctive_matches)
> > {
> >     const struct cls_partition *partition;
> > -    tag_type tags;
> > -    int best_priority = INT_MIN;
> > -    const struct cls_match *best;
> >     struct trie_ctx trie_ctx[CLS_MAX_TRIES];
> > -    struct cls_subtable *subtable;
> > +    const struct cls_match *match;
> > +    tag_type tags;
> > +
> > +    /* Highest-priority flow in 'cls' that certainly matches 'flow'. */
> > +    const struct cls_match *hard = NULL;
> > +    int hard_pri = INT_MIN;     /* hard ? hard->priority : INT_MIN. */
> > +
> > +    /* 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);
> > +    int soft_pri = INT_MIN;    /* n_soft ? MAX(soft[*]->priority) : INT_MIN. */
> > 
> >     /* Synchronize for cls->n_tries and subtable->trie_plen.  They can change
> >      * when table configuration changes, which happens typically only on
> > @@ -864,23 +1022,213 @@ classifier_lookup(const struct classifier *cls, struct flow *flow,
> >         trie_ctx_init(&trie_ctx[i], &cls->tries[i]);
> >     }
> > 
> > -    best = NULL;
> > -    PVECTOR_FOR_EACH_PRIORITY(subtable, best_priority, 2,
> > -                              sizeof(struct cls_subtable), &cls->subtables) {
> > -        const 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 && rule->priority > best_priority) {
> > -            best_priority = rule->priority;
> > -            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;
> > +        } 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 (soft_pri < match->priority) {
> > +                soft_pri = match->priority;
> > +            }
> >         }
> >     }
> > 
> > -    return best ? best->cls_rule : NULL;
> > +    /* 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 less than or equal to
> > +         * the hard match's priority.  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 = INT_MIN;
> > +        int n_soft_pri = 0;
> > +        for (int i = 0; i < n_soft; i++) {
> > +            if (soft[i]->priority > soft_pri) {
> > +                soft_pri = soft[i]->priority;
> > +                n_soft_pri = 1;
> > +            } else if (soft[i]->priority == soft_pri) {
> > +                n_soft_pri++;
> > +            }
> > +        }
> > +        ovs_assert(soft_pri > hard_pri);
> > +
> > +        /* Look for a real match among the highest-priority soft matches.
> > +         *
> > +         * It's unusual to have many conjunctive matches, so we use stubs to
> > +         * avoid calling malloc() in the common case.  An hmap has a built-in
> > +         * stub for up to 2 hmap_nodes; possibly, we would benefit a variant
> > +         * with a bigger stub. */
> > +        struct conjunctive_match cm_stubs[16];
> > +        struct hmap matches;
> > +
> > +        hmap_init(&matches);
> > +        for (int i = 0; i < n_soft; i++) {
> > +            uint32_t id;
> > +
> > +            if (soft[i]->priority == soft_pri
> > +                && find_conjunctive_match(soft[i], n_soft_pri, &matches,
> > +                                          cm_stubs, ARRAY_SIZE(cm_stubs),
> > +                                          &id)) {
> > +                uint32_t saved_conj_id = flow->conj_id;
> > +                const struct cls_rule *rule;
> > +
> > +                flow->conj_id = id;
> > +                rule = classifier_lookup__(cls, flow, wc, false);
> > +                flow->conj_id = saved_conj_id;
> > +
> > +                if (rule) {
> > +                    free_conjunctive_matches(&matches,
> > +                                             cm_stubs, ARRAY_SIZE(cm_stubs));
> > +                    if (soft != soft_stub) {
> > +                        free(soft);
> > +                    }
> > +                    return rule;
> > +                }
> > +            }
> > +        }
> > +        free_conjunctive_matches(&matches, cm_stubs, ARRAY_SIZE(cm_stubs));
> > +
> > +        /* 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 != 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;
> > +                    }
> > +                }
> > +            } else {
> > +                /* No such lower-priority flow (probably the common case). */
> > +                soft[i] = 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()).
> > + *
> > + * 'flow' is non-const to allow for temporary modifications during the lookup.
> > + * Any changes are restored before returning. */
> > +const struct cls_rule *
> > +classifier_lookup(const struct classifier *cls, 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 9ebc506..a0335a1 100644
> > --- a/lib/classifier.h
> > +++ b/lib/classifier.h
> > @@ -255,6 +255,12 @@ struct classifier {
> >     bool publish;                   /* Make changes visible to lookups? */
> > };
> > 
> > +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 rculist node;         /* In struct cls_subtable 'rules_list'. */
> > @@ -269,6 +275,10 @@ void cls_rule_init_from_minimatch(struct cls_rule *, const struct minimatch *,
> > 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);
> > void cls_rule_format(const struct cls_rule *, struct ds *);
> > diff --git a/lib/flow.c b/lib/flow.c
> > index eb7fdf1..f30f3b6 100644
> > --- a/lib/flow.c
> > +++ b/lib/flow.c
> > @@ -990,6 +990,7 @@ flow_wildcards_clear_non_packet_fields(struct flow_wildcards *wc)
> >     memset(&wc->masks.metadata, 0, sizeof wc->masks.metadata);
> >     memset(&wc->masks.regs, 0, sizeof wc->masks.regs);
> >     wc->masks.actset_output = 0;
> > +    wc->masks.conj_id = 0;
> > }
> > 
> > /* Returns true if 'wc' matches every packet, false if 'wc' fixes any bits or
> > diff --git a/lib/flow.h b/lib/flow.h
> > index 8e56d05..1ca3b6e 100644
> > --- a/lib/flow.h
> > +++ b/lib/flow.h
> > @@ -101,6 +101,7 @@ struct flow {
> >     uint32_t skb_priority;      /* Packet priority for QoS. */
> >     uint32_t pkt_mark;          /* Packet mark. */
> >     uint32_t recirc_id;         /* Must be exact match. */
> > +    uint32_t conj_id;           /* Conjunction ID. */
> >     union flow_in_port in_port; /* Input port.*/
> >     ofp_port_t actset_output;   /* Output port in action set. */
> >     ovs_be16 pad1;              /* Pad to 32 bits. */
> > @@ -156,7 +157,7 @@ BUILD_ASSERT_DECL(sizeof(struct flow) % 4 == 0);
> > 
> > /* Remember to update FLOW_WC_SEQ when changing 'struct flow'. */
> > BUILD_ASSERT_DECL(offsetof(struct flow, dp_hash) + sizeof(uint32_t)
> > -                  == sizeof(struct flow_tnl) + 180
> > +                  == sizeof(struct flow_tnl) + 184
> >                   && FLOW_WC_SEQ == 28);
> > 
> > /* Incremental points at which flow classification may be performed in
> > diff --git a/lib/match.c b/lib/match.c
> > index 480b972..acfb2b3 100644
> > --- a/lib/match.c
> > +++ b/lib/match.c
> > @@ -89,6 +89,13 @@ match_set_recirc_id(struct match *match, uint32_t value)
> > }
> > 
> > void
> > +match_set_conj_id(struct match *match, uint32_t value)
> > +{
> > +    match->flow.conj_id = value;
> > +    match->wc.masks.conj_id = UINT32_MAX;
> > +}
> > +
> > +void
> > match_set_reg(struct match *match, unsigned int reg_idx, uint32_t value)
> > {
> >     match_set_reg_masked(match, reg_idx, value, UINT32_MAX);
> > @@ -888,6 +895,10 @@ match_format(const struct match *match, struct ds *s, int priority)
> >                              wc->masks.dp_hash);
> >     }
> > 
> > +    if (wc->masks.conj_id) {
> > +        ds_put_format(s, "conj_id=%"PRIu32",", f->conj_id);
> > +    }
> > +
> >     if (wc->masks.skb_priority) {
> >         ds_put_format(s, "skb_priority=%#"PRIx32",", f->skb_priority);
> >     }
> > diff --git a/lib/match.h b/lib/match.h
> > index a245bcf..452b5e7 100644
> > --- a/lib/match.h
> > +++ b/lib/match.h
> > @@ -46,7 +46,8 @@ void match_set_dp_hash(struct match *, uint32_t value);
> > void match_set_dp_hash_masked(struct match *, uint32_t value, uint32_t mask);
> > 
> > void match_set_recirc_id(struct match *, uint32_t value);
> > -void match_set_recirc_id_masked(struct match *, uint32_t value, uint32_t mask);
> > +
> > +void match_set_conj_id(struct match *, uint32_t value);
> > 
> > void match_set_reg(struct match *, unsigned int reg_idx, uint32_t value);
> > void match_set_reg_masked(struct match *, unsigned int reg_idx,
> > diff --git a/lib/meta-flow.c b/lib/meta-flow.c
> > index 90dd27c..67115b2 100644
> > --- a/lib/meta-flow.c
> > +++ b/lib/meta-flow.c
> > @@ -108,6 +108,8 @@ mf_is_all_wild(const struct mf_field *mf, const struct flow_wildcards *wc)
> >         return !wc->masks.dp_hash;
> >     case MFF_RECIRC_ID:
> >         return !wc->masks.recirc_id;
> > +    case MFF_CONJ_ID:
> > +        return !wc->masks.conj_id;
> >     case MFF_TUN_SRC:
> >         return !wc->masks.tunnel.ip_src;
> >     case MFF_TUN_DST:
> > @@ -363,6 +365,7 @@ mf_is_value_valid(const struct mf_field *mf, const union mf_value *value)
> >     switch (mf->id) {
> >     case MFF_DP_HASH:
> >     case MFF_RECIRC_ID:
> > +    case MFF_CONJ_ID:
> >     case MFF_TUN_ID:
> >     case MFF_TUN_SRC:
> >     case MFF_TUN_DST:
> > @@ -464,6 +467,9 @@ mf_get_value(const struct mf_field *mf, const struct flow *flow,
> >     case MFF_RECIRC_ID:
> >         value->be32 = htonl(flow->recirc_id);
> >         break;
> > +    case MFF_CONJ_ID:
> > +        value->be32 = htonl(flow->conj_id);
> > +        break;
> >     case MFF_TUN_ID:
> >         value->be64 = flow->tunnel.tun_id;
> >         break;
> > @@ -669,6 +675,9 @@ mf_set_value(const struct mf_field *mf,
> >     case MFF_RECIRC_ID:
> >         match_set_recirc_id(match, ntohl(value->be32));
> >         break;
> > +    case MFF_CONJ_ID:
> > +        match_set_conj_id(match, ntohl(value->be32));
> > +        break;
> >     case MFF_TUN_ID:
> >         match_set_tun_id(match, value->be64);
> >         break;
> > @@ -898,6 +907,9 @@ mf_set_flow_value(const struct mf_field *mf,
> >     case MFF_RECIRC_ID:
> >         flow->recirc_id = ntohl(value->be32);
> >         break;
> > +    case MFF_CONJ_ID:
> > +        flow->conj_id = ntohl(value->be32);
> > +        break;
> >     case MFF_TUN_ID:
> >         flow->tunnel.tun_id = value->be64;
> >         break;
> > @@ -1152,6 +1164,10 @@ mf_set_wild(const struct mf_field *mf, struct match *match)
> >         match->flow.recirc_id = 0;
> >         match->wc.masks.recirc_id = 0;
> >         break;
> > +    case MFF_CONJ_ID:
> > +        match->flow.conj_id = 0;
> > +        match->wc.masks.conj_id = 0;
> > +        break;
> >     case MFF_TUN_ID:
> >         match_set_tun_id_masked(match, htonll(0), htonll(0));
> >         break;
> > @@ -1373,6 +1389,7 @@ mf_set(const struct mf_field *mf,
> > 
> >     switch (mf->id) {
> >     case MFF_RECIRC_ID:
> > +    case MFF_CONJ_ID:
> >     case MFF_IN_PORT:
> >     case MFF_IN_PORT_OXM:
> >     case MFF_ACTSET_OUTPUT:
> > diff --git a/lib/meta-flow.h b/lib/meta-flow.h
> > index 62e9c79..1ee5c75 100644
> > --- a/lib/meta-flow.h
> > +++ b/lib/meta-flow.h
> > @@ -299,6 +299,20 @@ enum OVS_PACKED_ENUM mf_field_id {
> >      */
> >     MFF_RECIRC_ID,
> > 
> > +    /* "conj_id".
> > +     *
> > +     * ID for "conjunction" actions.  Please refer to ovs-ofctl(8)
> > +     * documentation of "conjunction" for details.
> > +     *
> > +     * Type: be32.
> > +     * Maskable: no.
> > +     * Formatting: decimal.
> > +     * Prerequisites: none.
> > +     * Access: read-only.
> > +     * NXM: NXM_NX_CONJ_ID(37) since v2.4.
> > +     * OXM: none. */
> > +    MFF_CONJ_ID,
> > +
> >     /* "tun_id" (aka "tunnel_id").
> >      *
> >      * The "key" or "tunnel ID" or "VNI" in a packet received via a keyed
> > diff --git a/lib/nx-match.c b/lib/nx-match.c
> > index 2ad3cf2..8644787 100644
> > --- a/lib/nx-match.c
> > +++ b/lib/nx-match.c
> > @@ -829,6 +829,10 @@ nx_put_raw(struct ofpbuf *b, enum ofp_version oxm, const struct match *match,
> >         nxm_put_32(b, MFF_RECIRC_ID, oxm, htonl(flow->recirc_id));
> >     }
> > 
> > +    if (match->wc.masks.conj_id) {
> > +        nxm_put_32(b, MFF_CONJ_ID, oxm, htonl(flow->conj_id));
> > +    }
> > +
> >     if (match->wc.masks.in_port.ofp_port) {
> >         ofp_port_t in_port = flow->in_port.ofp_port;
> >         if (oxm) {
> > diff --git a/lib/ofp-actions.c b/lib/ofp-actions.c
> > index 4680d81..e694fd9 100644
> > --- a/lib/ofp-actions.c
> > +++ b/lib/ofp-actions.c
> > @@ -281,6 +281,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. */
> > @@ -3898,6 +3901,89 @@ 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 + 1, oc->n_clauses);
> > +}
> > +
> > +static char * OVS_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 < 1) {
> > +        return xstrdup("clause index must be positive");
> > +    } else if (clause > n_clauses) {
> > +        return xstrdup("clause index must be less than or equal to "
> > +                       "number of clauses");
> > +    }
> > +
> > +    add_conjunction(ofpacts, id, clause - 1, n_clauses);
> > +    return NULL;
> > +}
> > +
> > /* Action structure for NXAST_MULTIPATH.
> >  *
> >  * This action performs the following steps in sequence:
> > @@ -4644,6 +4730,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:
> > @@ -4710,6 +4797,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:
> > @@ -4925,6 +5013,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:
> > @@ -5455,6 +5544,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);
> > 
> > @@ -5576,8 +5668,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)
> > @@ -5589,6 +5685,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
> > @@ -5887,6 +5994,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 8362aa8..5458583 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 238fded..56b7652 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 ba0c0d8..283df27 100644
> > --- a/ofproto/ofproto-dpif-xlate.c
> > +++ b/ofproto/ofproto-dpif-xlate.c
> > @@ -3742,6 +3742,7 @@ ofpact_needs_recirculation_after_mpls(const struct ofpact *a, struct xlate_ctx *
> >     case OFPACT_SET_TUNNEL:
> >     case OFPACT_SET_QUEUE:
> >     case OFPACT_POP_QUEUE:
> > +    case OFPACT_CONJUNCTION:
> >     case OFPACT_NOTE:
> >     case OFPACT_OUTPUT_REG:
> >     case OFPACT_EXIT:
> > @@ -4055,6 +4056,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 dc7b551..1881c0b 100644
> > --- a/ofproto/ofproto.c
> > +++ b/ofproto/ofproto.c
> > @@ -4138,6 +4138,45 @@ evict_rules_from_table(struct oftable *table, unsigned int extra_space)
> >     return error;
> > }
> > 
> > +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.
> >  *
> > @@ -4285,6 +4324,7 @@ add_flow(struct ofproto *ofproto, struct ofputil_flow_mod *fm,
> > 
> >     classifier_defer(&table->cls);
> >     classifier_insert(&table->cls, &rule->cr);
> > +    set_conjunction(rule);
> > 
> >     error = ofproto->ofproto_class->rule_insert(rule);
> >     if (error) {
> > @@ -4398,6 +4438,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 33502bc..35ccf9e 100644
> > --- a/tests/automake.mk
> > +++ b/tests/automake.mk
> > @@ -322,3 +322,5 @@ clean-pki:
> > 	rm -f tests/pki/stamp
> > 	rm -rf tests/pki
> > endif
> > +
> > +EXTRA_DIST += tests/test-conjunction
> > diff --git a/tests/ofproto.at b/tests/ofproto.at
> > index 8cfecc6..9e7b1bf 100644
> > --- a/tests/ofproto.at
> > +++ b/tests/ofproto.at
> > @@ -1405,6 +1405,7 @@ OVS_VSWITCHD_START
> >     matching:
> >       dp_hash: arbitrary mask
> >       recirc_id: exact match or wildcard
> > +      conj_id: exact match or wildcard
> >       tun_id: arbitrary mask
> >       tun_src: arbitrary mask
> >       tun_dst: arbitrary mask
> > @@ -1482,7 +1483,7 @@ AT_CHECK(
> > # Check that the configuration was updated.
> > mv expout orig-expout
> > sed 's/classifier/main/
> > -74s/1000000/1024/' < orig-expout > expout
> > +75s/1000000/1024/' < orig-expout > expout
> > AT_CHECK([ovs-ofctl -O OpenFlow13 dump-table-features br0 | sed '/^$/d
> > /^OFPST_TABLE_FEATURES/d'], [0], [expout])
> > OVS_VSWITCHD_STOP
> > diff --git a/tests/test-conjunction b/tests/test-conjunction
> > new file mode 100755
> > index 0000000..83dbe37
> > --- /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
> > +conj_id=1,ip,actions=mod_dl_src:00:11:22:33:44:55,local
> > +ip,ip_src=10.0.0.1,actions=conjunction(1,1/2)
> > +ip,ip_src=10.0.0.4,actions=conjunction(1,1/2)
> > +ip,ip_src=10.0.0.6,actions=conjunction(1,1/2)
> > +ip,ip_src=10.0.0.7,actions=conjunction(1,1/2)
> > +ip,ip_dst=10.0.0.2,actions=conjunction(1,2/2)
> > +ip,ip_dst=10.0.0.5,actions=conjunction(1,2/2)
> > +ip,ip_dst=10.0.0.7,actions=conjunction(1,2/2)
> > +ip,ip_dst=10.0.0.8,actions=conjunction(1,2/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 7ffbeaa..1e8727a 100644
> > --- a/utilities/ovs-ofctl.8.in
> > +++ b/utilities/ovs-ofctl.8.in
> > @@ -1141,6 +1141,11 @@ output group in the OpenFlow action set), then the value will be
> > .IP
> > This field was introduced in Open vSwitch 2.4 to conform with the
> > OpenFlow 1.5 (draft) specification.
> > +.
> > +.IP \fBconj_id=\fIvalue\fR
> > +Matches the given 32-bit \fIvalue\fR against the conjunction ID.  This
> > +is used only with the \fBconjunction\fR action, documented later.
> > +.
> > .PP
> > Defining IPv6 flows (those with \fBdl_type\fR equal to 0x86dd) requires
> > support for NXM.  The following shorthand notations are available for
> > @@ -1783,6 +1788,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 1 to \fIn\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 setting \fBconj_id\fR to 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 1 of
> > +2), \fIand\fR the IP destination is one of the values in the flows
> > +that match on IP destination (dimension 2 of 2), Open vSwitch searches
> > +for a flow that matches \fBconj_id\fR against the conjunction ID
> > +(1234), finding the first flow listed below.
> > +.RS +1in
> > +.br
> > +.B "conj_id=1234 actions=controller"
> > +.br
> > +.B "ip,ip_src=10.0.0.1 actions=conjunction(1234, 1/2)"
> > +.br
> > +.B "ip,ip_src=10.0.0.4 actions=conjunction(1234, 1/2)"
> > +.br
> > +.B "ip,ip_src=10.0.0.6 actions=conjunction(1234, 1/2)"
> > +.br
> > +.B "ip,ip_src=10.0.0.7 actions=conjunction(1234, 1/2)"
> > +.br
> > +.B "ip,ip_dst=10.0.0.2 actions=conjunction(1234, 2/2)"
> > +.br
> > +.B "ip,ip_dst=10.0.0.5 actions=conjunction(1234, 2/2)"
> > +.br
> > +.B "ip,ip_dst=10.0.0.7 actions=conjunction(1234, 2/2)"
> > +.br
> > +.B "ip,ip_dst=10.0.0.8 actions=conjunction(1234, 2/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 1 matches on \fBip_src\fR, dimension 2 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
> > +\fBconj_id=\fIid\fR is done in the same general-purpose way as other flow
> > +table searches, so one can use flows with \fBconj_id=\fIid\fR to act
> > +differently depending on circumstances.  (One exception is that the
> > +search for the \fBconj_id=\fIid\fR flow itself ignores conjunctive flows,
> > +to avoid recursion.) If the search with \fBconj_id=\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
> > +\fBconj_id=\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 "conj_id=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
> > -- 
> > 1.7.10.4
> > 
> > _______________________________________________
> > dev mailing list
> > dev at openvswitch.org
> > http://openvswitch.org/mailman/listinfo/dev
> 



More information about the dev mailing list