With the small nits below:
Acked-by: Jarno Rajahalme <jrajaha...@nicira.com>
On Jan 9, 2015, at 11:42 AM, Ben Pfaff <b...@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.
>
> Signed-off-by: Ben Pfaff <b...@nicira.com>
> ---
> 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.
>
> v2.1->v3:
> - Nontrivial rebase due to upstream changes.
> - Fix race condition modifying rules to add or remove conjunctions.
> - Fix race condition adding rules with conjunctions.
> - Document where one should specify extra constraints.
> - Add some tests.
> —
>
(snip)
> +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);
Could compute the hash after the “continue” to not compute it if not needed?
> + 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);
Empty line here would help seeing the scope of ’n'.
> + cm = n < n_cm_stubs ? &cm_stubs[n++] : xmalloc(sizeof *cm);
Post-increment seems to be wasted as the scope of ’n’ is this block only?
> + 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);
Since the stub entires are not removed from the hmap, is it necessary to remove
the malloced ones either?
> + free(cm);
> + }
> + }
> + }
> + hmap_destroy(matches);
> +}
> +
(snip)
>
> 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"
I do not see why this is needed here.
> #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,
> +
I do not see this latter error code being used, is it not needed after all?
> /* ## --------------------- ## */
> /* ## OFPET_BAD_INSTRUCTION ## */
> /* ## --------------------- ## */
> diff --git a/lib/ofp-util.c b/lib/ofp-util.c
> index 53982d5..2270a93 100644
> --- a/lib/ofp-util.c
> +++ b/lib/ofp-util.c
> @@ -1,5 +1,5 @@
> /*
> - * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014 Nicira, Inc.
> + * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015 Nicira, Inc.
> *
> * Licensed under the Apache License, Version 2.0 (the "License");
> * you may not use this file except in compliance with the License.
> @@ -186,7 +186,7 @@ ofputil_netmask_to_wcbits(ovs_be32 netmask)
> void
> ofputil_wildcard_from_ofpfw10(uint32_t ofpfw, struct flow_wildcards *wc)
> {
> - BUILD_ASSERT_DECL(FLOW_WC_SEQ == 29);
> + BUILD_ASSERT_DECL(FLOW_WC_SEQ == 30);
>
> /* Initialize most of wc. */
> flow_wildcards_init_catchall(wc);
> diff --git a/lib/ovs-router.c b/lib/ovs-router.c
> index a121354..8de2e2d 100644
> --- a/lib/ovs-router.c
> +++ b/lib/ovs-router.c
> @@ -1,5 +1,5 @@
> /*
> - * Copyright (c) 2014 Nicira, Inc.
> + * Copyright (c) 2014, 2015 Nicira, Inc.
> *
> * Licensed under the Apache License, Version 2.0 (the "License");
> * you may not use this file except in compliance with the License.
> @@ -118,7 +118,7 @@ ovs_router_insert__(uint8_t priority, ovs_be32 ip_dst,
> uint8_t plen,
> cls_rule_init(&p->cr, &match, priority); /* Longest prefix matches first.
> */
>
> ovs_mutex_lock(&mutex);
> - cr = classifier_replace(&cls, &p->cr);
> + cr = classifier_replace(&cls, &p->cr, NULL, 0);
> ovs_mutex_unlock(&mutex);
>
> if (cr) {
> diff --git a/lib/tnl-ports.c b/lib/tnl-ports.c
> index ff616a2..e6739b9 100644
> --- a/lib/tnl-ports.c
> +++ b/lib/tnl-ports.c
> @@ -1,5 +1,5 @@
> /*
> - * Copyright (c) 2014 Nicira, Inc.
> + * Copyright (c) 2014, 2015 Nicira, Inc.
> *
> * Licensed under the Apache License, Version 2.0 (the "License");
> * you may not use this file except in compliance with the License.
> @@ -103,7 +103,7 @@ tnl_port_map_insert(odp_port_t port, ovs_be32 ip_dst,
> ovs_be16 udp_port,
> ovs_refcount_init(&p->ref_cnt);
> strncpy(p->dev_name, dev_name, IFNAMSIZ);
>
> - classifier_insert(&cls, &p->cr);
> + classifier_insert(&cls, &p->cr, NULL, 0);
> }
> ovs_mutex_unlock(&mutex);
> }
> diff --git a/ofproto/ofproto-dpif-xlate.c b/ofproto/ofproto-dpif-xlate.c
> index 4a5b7fd..2efcbb9 100644
> --- a/ofproto/ofproto-dpif-xlate.c
> +++ b/ofproto/ofproto-dpif-xlate.c
> @@ -1,4 +1,4 @@
> -/* Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014 Nicira, Inc.
> +/* Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2015 Nicira, Inc.
> *
> * Licensed under the Apache License, Version 2.0 (the "License");
> * you may not use this file except in compliance with the License.
> @@ -2635,7 +2635,7 @@ compose_output_action__(struct xlate_ctx *ctx,
> ofp_port_t ofp_port,
>
> /* If 'struct flow' gets additional metadata, we'll need to zero it out
> * before traversing a patch port. */
> - BUILD_ASSERT_DECL(FLOW_WC_SEQ == 29);
> + BUILD_ASSERT_DECL(FLOW_WC_SEQ == 30);
> memset(&flow_tnl, 0, sizeof flow_tnl);
>
> if (!xport) {
> @@ -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;
> +
This should never happen, do you consider OVS_NOT_REACHED() too risky?
> case OFPACT_EXIT:
> ctx->exit = true;
> break;
(snip)
> diff --git a/tests/classifier.at b/tests/classifier.at
> index eb97022..9489da6 100644
> --- a/tests/classifier.at
> +++ b/tests/classifier.at
> @@ -124,3 +124,161 @@ Datapath actions: 3
> ])
> OVS_VSWITCHD_STOP(["/'prefixes' with incompatible field: ipv6_label/d"])
> AT_CLEANUP
> +
> +AT_BANNER([conjunctive match])
> +
> +AT_SETUP([single conjunctive match])
> +OVS_VSWITCHD_START
> +ADD_OF_PORTS([br0], 1, 2, 3, 4, 5)
> +AT_DATA([flows.txt], [dnl
> +conj_id=1,actions=3
> +priority=100,ip,ip_src=10.0.0.1,actions=conjunction(1,1/2)
> +priority=100,ip,ip_src=10.0.0.4,actions=conjunction(1,1/2)
> +priority=100,ip,ip_src=10.0.0.6,actions=conjunction(1,1/2)
> +priority=100,ip,ip_src=10.0.0.7,actions=conjunction(1,1/2)
> +priority=100,ip,ip_dst=10.0.0.2,actions=conjunction(1,2/2)
> +priority=100,ip,ip_dst=10.0.0.5,actions=conjunction(1,2/2)
> +priority=100,ip,ip_dst=10.0.0.7,actions=conjunction(1,2/2)
> +priority=100,ip,ip_dst=10.0.0.8,actions=conjunction(1,2/2)
> +priority=100,ip,ip_src=10.0.0.1,ip_dst=10.0.0.4,actions=4
> +priority=100,ip,ip_src=10.0.0.3,ip_dst=10.0.0.5,actions=5
> +
> +priority=0 actions=2
> +])
> +AT_CHECK([ovs-ofctl add-flows br0 flows.txt])
> +for src in 0 1 2 3 4 5 6 7; do
> + for dst in 0 1 2 3 4 5 6 7; do
> + if test $src$dst = 14; then
> + out=4
> + elif test $src$dst = 35; then
> + out=5
> + else
> + out=2
> + case $src in [[1467]]) case $dst in [[2578]]) out=3 ;; esac ;;
> esac
> + fi
> + AT_CHECK([ovs-appctl ofproto/trace br0
> "in_port=1,dl_type=0x0800,nw_src=10.0.0.$src,nw_dst=10.0.0.$dst"], [0],
> [stdout])
> + AT_CHECK_UNQUOTED([tail -1 stdout], [0], [Datapath actions: $out
> +])
> + done
> +done
> +OVS_VSWITCHD_STOP
> +AT_CLEANUP
> +
> +AT_SETUP([multiple conjunctive match])
> +OVS_VSWITCHD_START
> +ADD_OF_PORTS([br0], 1, 2, 3, 4, 5)
> +AT_DATA([flows.txt], [dnl
> +conj_id=1,actions=1
> +conj_id=2,actions=2
> +conj_id=3,actions=3
> +
> +priority=5,ip,ip_src=20.0.0.0/8,actions=conjunction(1,1/2),conjunction(2,1/2)
> +priority=5,ip,ip_src=10.1.0.0/16,actions=conjunction(1,1/2),conjunction(3,2/3)
> +priority=5,ip,ip_src=10.2.0.0/16,actions=conjunction(1,1/2),conjunction(2,1/2)
> +priority=5,ip,ip_src=10.1.3.0/24,actions=conjunction(1,1/2),conjunction(3,2/3)
> +priority=5,ip,ip_src=10.1.4.5/32,actions=conjunction(1,1/2),conjunction(2,1/2)
> +
> +priority=5,ip,ip_dst=20.0.0.0/8,actions=conjunction(1,2/2)
> +priority=5,ip,ip_dst=10.1.0.0/16,actions=conjunction(1,2/2)
> +priority=5,ip,ip_dst=10.2.0.0/16,actions=conjunction(1,2/2)
> +priority=5,ip,ip_dst=10.1.3.0/24,actions=conjunction(1,2/2)
> +priority=5,ip,ip_dst=10.1.4.5/32,actions=conjunction(1,2/2)
> +priority=5,ip,ip_dst=30.0.0.0/8,actions=conjunction(2,2/2),conjunction(3,1/3)
> +priority=5,ip,ip_dst=40.5.0.0/16,actions=conjunction(2,2/2),conjunction(3,1/3)
> +
> +priority=5,tcp,tcp_dst=80,actions=conjunction(3,3/3)
> +priority=5,tcp,tcp_dst=443,actions=conjunction(3,3/3)
> +
> +priority=5,tcp,tcp_src=80,actions=conjunction(3,3/3)
> +priority=5,tcp,tcp_src=443,actions=conjunction(3,3/3)
> +
> +priority=0,actions=4
> +])
> +AT_CHECK([ovs-ofctl add-flows br0 flows.txt])
> +for a0 in \
> + '1 20.0.0.1' \
> + '2 10.1.0.1' \
> + '3 10.2.0.1' \
> + '4 10.1.3.1' \
> + '5 10.1.4.5' \
> + '6 1.2.3.4'
> +do
> + for b0 in \
> + '1 20.0.0.1' \
> + '2 10.1.0.1' \
> + '3 10.2.0.1' \
> + '4 10.1.3.1' \
> + '5 10.1.4.5' \
> + '6 30.0.0.1' \
> + '7 40.5.0.1' \
> + '8 1.2.3.4'
> + do
> + for c0 in '1 80' '2 443' '3 8080'; do
> + for d0 in '1 80' '2 443' '3 8080'; do
> + set $a0; a=$1 ip_src=$2
> + set $b0; b=$1 ip_dst=$2
> + set $c0; c=$1 tcp_src=$2
> + set $d0; d=$1 tcp_dst=$2
> + case $a$b$c$d in
> + [[12345]][[12345]]??) out=1 ;;
> + [[135]][[67]]??) out=2 ;;
> + [[24]][[67]][[12]]? | [[24]][[67]]?[[12]]) out=3 ;;
> + *) out=4
> + esac
> + AT_CHECK([ovs-appctl ofproto/trace br0
> "in_port=5,dl_type=0x0800,nw_proto=6,nw_src=$ip_src,nw_dst=$ip_dst,tcp_src=$tcp_src,tcp_dst=$tcp_dst"],
> [0], [stdout])
> + AT_CHECK_UNQUOTED([tail -1 stdout], [0], [Datapath actions:
> $out
> +])
> + done
> + done
> + done
> +done
> +OVS_VSWITCHD_STOP
> +AT_CLEANUP
> +
> +# In conjunctive match, we can find some soft matches that turn out not to
> be a
> +# real match. Usually, that's the end of the road--there is no real match.
> +# But if there is a flow identical to one of the flows that was a soft match,
> +# except with a lower priority, then we have to try again with that lower
> +# priority flow. This test checks this special case.
> +AT_SETUP([conjunctive match priority fallback])
> +OVS_VSWITCHD_START
> +ADD_OF_PORTS([br0], 1, 2, 3, 4, 5, 6)
> +AT_DATA([flows.txt], [dnl
> +conj_id=1,actions=1
> +conj_id=3,actions=3
> +
> +priority=5,ip,ip_src=10.0.0.1,actions=conjunction(1,1/2)
> +priority=5,ip,ip_src=10.0.0.2,actions=conjunction(1,1/2)
> +priority=5,ip,ip_dst=10.0.0.1,actions=conjunction(1,2/2)
> +priority=5,ip,ip_dst=10.0.0.2,actions=conjunction(1,2/2)
> +priority=5,ip,ip_dst=10.0.0.3,actions=conjunction(1,2/2)
> +
> +priority=4,ip,ip_src=10.0.0.3,ip_dst=10.0.0.2,actions=2
> +
> +priority=3,ip,ip_src=10.0.0.1,actions=conjunction(3,1/2)
> +priority=3,ip,ip_src=10.0.0.3,actions=conjunction(3,1/2)
> +priority=3,ip,ip_dst=10.0.0.2,actions=conjunction(3,2/2)
> +priority=3,ip,ip_dst=10.0.0.3,actions=conjunction(3,2/2)
> +priority=3,ip,ip_dst=10.0.0.4,actions=conjunction(3,2/2)
> +
> +priority=2,ip,ip_src=10.0.0.1,ip_dst=10.0.0.5,actions=4
> +
It would be good to also have an identical lower priority rule that is a hard
match.
> +priority=0,actions=5
> +])
> +AT_CHECK([ovs-ofctl add-flows br0 flows.txt])
> +for src in 0 1 2 3; do
> + for dst in 0 1 2 3 4 5; do
> + case $src$dst in
> + [[12]][[123]]) out=1 ;;
> + 32) out=2 ;;
> + [[13]][[234]]) out=3 ;;
> + 15) out=4 ;;
> + *) out=5
> + esac
> + AT_CHECK([ovs-appctl ofproto/trace br0
> "in_port=6,dl_type=0x0800,nw_src=10.0.0.$src,nw_dst=10.0.0.$dst"], [0],
> [stdout])
> + AT_CHECK_UNQUOTED([tail -1 stdout], [0], [Datapath actions: $out
> +])
> + done
> +done
> +OVS_VSWITCHD_STOP
> +AT_CLEANUP
>
(snip)
> 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
Are we running this script as part of the test suite?
> diff --git a/utilities/ovs-ofctl.8.in b/utilities/ovs-ofctl.8.in
> index 7ffbeaa..aa6da29 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.
Better say “below” than “later”, as the latter could be understood as “in
future”.
Jarno
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
