On Thu, Oct 30, 2014 at 11:39:44AM -0700, Jarno Rajahalme wrote:
>
> On Oct 29, 2014, at 11:46 PM, 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.
> >
> > 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.
> >
>
> I think it would be better to treat changing conjunctions with a
> classifier_replace, even if the match would otherwise remain the
> same. See the comments below.
This is certainly one proper way to implement it, and it has the
advantage of maintaining the conceptual design of cls_rule as
immutable. But it's a little tricky, which is why I didn't do it for
the RFC. I'll see what I can do now.
> > - 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.
>
> A fixed field with read-only, non-maskable semantics would have its
> advantages. We could index on it separately and speed up the lookup
> if we specify that no duplicates are allowed (or use simple linear
> search if there are duplicates).
OK, you and Thomas both suggested a dedicated field, so the next
version will have one.
> > - 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.
>
> It would be lovely if we could get rid of the individual mallocs in
> question here. Like if the ?id? and ?clauses? were in the hash
> buckets directly...
It's not a problem to get rid of all the mallocs in the common case, I
just didn't take the time for the RFC version. I'll do that for the
next version.
> > +void
> > +cls_rule_set_conjunctions(struct cls_rule *cr,
> > + const struct cls_conjunction *conj, size_t n)
> > +{
>
> IMO this should take the cls->mutex, just like the classifier_insert
> and classifier_replace, if the intention is to modify the innards of
> a rule already in the classifier. Or then fold this in to
> classifier_insert() and classifier_replace() like I suggest in
> comments below.
I'll aim for the latter in a future version.
> > @@ -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);
> > + }
>
> Have you considered how to handle this in classifier_replace()?
Thanks, I had overlooked that function. I'll fix it in the next
version.
> > + /* 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) {
>
> The fact that ?hard_pri? is off by one is really confusing here...
Yeah, the switch from 'unsigned int' to 'int' will really help.
> > + 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.
>
> ?than (hard_pri - 1).?
Again becomes less confusing with unsigned->int.
> > + 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;
>
> Could store the old value in stack and modify the ?rule? in place.
You're right, none of the callers care about temporary modifications.
I'll put that in v2.
> > + rule = classifier_lookup__(cls, &annotated_flow, wc,
> > false);
>
> This might find any match that is wildcarding reg0, so we should
> make sure the recursive lookup call only visits subtables that exact
> match the whole of reg0.
That is an interesting idea, and it would not be difficult to
implement. I wonder whether it is really necessary, though. Suppose
that no flows match on the conjunction id in question (as reg0 or
conj_id) at all. Then this sub-classifier lookup is just going to
"fall through" the soft match that we're processing to the next hard
match. That's the same thing that would happen if the soft match
didn't exist at all, and it happens without needing any special case
for skipping subtables that match on reg0.
You wrote a lot of ideas about how to better and more cleanly and more
safely express conjunctions as part of cls_rule or as part of
classifier_{insert,replace}(), etc. I'm going to post v2, then get to
working on those.
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
