[ovs-dev] [PATCH v3 2/2] [RFC] classifier: Add support for conjunctive matches.
Ben Pfaff
blp at nicira.com
Sun Jan 11 21:29:53 UTC 2015
On Fri, Jan 09, 2015 at 04:54:42PM -0800, Jarno Rajahalme wrote:
> With the small nits below:
>
> Acked-by: Jarno Rajahalme <jrajahalme at nicira.com>
Thanks. I fixed up everything you mentioned and applied this to master.
I gave details below; the only bit where I think you might want followup
is on the treatment of OFPACT_CONJUNCTION in action translation (see
below).
> On Jan 9, 2015, at 11:42 AM, 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.
> >
> > Signed-off-by: Ben Pfaff <blp at nicira.com>
...
> > +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?
Thanks, reordered.
> > + 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'.
Added.
> > + 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?
Oops. The logic seems to be OK otherwise so I just dropped the ++.
> > + 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?
No. Dropped.
> > 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.
Dropped.
> > + /* 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?
Dropped. (This was a relic of an earlier idea I had.)
> > @@ -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?
I think it's too risky because not every action execution comes as a
result of a classifier lookup. We don't prevent "conjunction" from
appearing in the actions in a "packet-out", for example. It's useless
there. We could ignore it, or go to some trouble to give some kind of
error. I decided to just ignore it. Maybe we should log it?
> > 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.
You're right. I added one and thereby found a bug. Incremental
follows:
diff --git a/lib/classifier.c b/lib/classifier.c
index d8b76af..556cba3 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -1113,26 +1113,25 @@ classifier_lookup__(const struct classifier *cls, struct flow *flow,
* 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++;
- }
+ * It is tempting to delete soft matches that cannot be satisfied
+ * because there are fewer soft matches than required to satisfy any of
+ * their conjunctions, but we cannot do that because there might be
+ * lower priority soft or hard matches with otherwise identical
+ * matches. (We could special case those here, but there's no
+ * need--we'll do so at the bottom of the soft match loop anyway and
+ * this duplicates less code.)
+ *
+ * It's also tempting to break out of the soft match loop if 'n_soft ==
+ * 1' but that would also miss lower-priority hard matches. We could
+ * special case that also but again there's no need. */
+ for (int i = 0; i < n_soft; ) {
+ if (!soft[i] || soft[i]->priority <= hard_pri) {
+ soft[i] = soft[--n_soft];
+ } else {
+ i++;
}
- } while (deleted);
- if (n_soft < 2) {
+ }
+ if (!n_soft) {
break;
}
diff --git a/tests/classifier.at b/tests/classifier.at
index 9489da6..cfa1bc7 100644
--- a/tests/classifier.at
+++ b/tests/classifier.at
@@ -242,7 +242,7 @@ AT_CLEANUP
# 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)
+ADD_OF_PORTS([br0], 1, 2, 3, 4, 5, 6, 7)
AT_DATA([flows.txt], [dnl
conj_id=1,actions=1
conj_id=3,actions=3
@@ -261,9 +261,11 @@ 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
+priority=2,ip,ip_dst=10.0.0.1,actions=4
-priority=0,actions=5
+priority=1,ip,ip_src=10.0.0.1,ip_dst=10.0.0.5,actions=5
+
+priority=0,actions=6
])
AT_CHECK([ovs-ofctl add-flows br0 flows.txt])
for src in 0 1 2 3; do
@@ -272,10 +274,11 @@ for src in 0 1 2 3; do
[[12]][[123]]) out=1 ;;
32) out=2 ;;
[[13]][[234]]) out=3 ;;
- 15) out=4 ;;
- *) out=5
+ ?1) out=4 ;;
+ 15) out=5 ;;
+ *) out=6
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([ovs-appctl ofproto/trace br0 "in_port=7,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
> > 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?
No, that's not needed anymore. Dropped.
> > 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”.
Thanks, I switched to saying (see below).
More information about the dev
mailing list