[ovs-dev] [PATCH 1/3] Classifier: Staged sub-table matching.

[Ben Pfaff]

On Tue, Nov 05, 2013 at 01:54:37PM -0800, Jarno Rajahalme wrote:
> 
> On Nov 5, 2013, at 1:16 PM, Ben Pfaff <blp at nicira.com> wrote:
> 
> > On Fri, Nov 01, 2013 at 03:20:10PM -0700, Jarno Rajahalme wrote:
> >> v2: Properly finish hashes, more flexible configuration.
> >> 
> >> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>

...

> > Here, this check is always true if there is a single rule, but it does
> > not catch every case where there is a single rule, because of hash
> > collisions.  That requires a full collision of all 32 bits of the hash,
> > so it is probably rare and not worth concerning ourselves about, but I
> > thought I'd point it out in case you didn't know.  (It might be worth
> > noting in the comment?)
> > +        /* Check if we have narrowed down to a single rule already.  This
> > +         * check shows a measurable benefit with non-trivial flow tables. */
> > +        if (!inode->s) {
> > 
> 
> I actually had a comment to almost that effect earlier, but then
> removed it. Would this help:
> 
> /* (Rare) hash collisions may cause us to miss the opportunity for this optimization. */

Yes, thanks.

> > I didn't look at the flow.[ch] code yet.  It looks tricky.
> 
> The *minimask_range() functions should not be much trickier than the
> existing minimask functions, even though it took some effort to get
> them right.

OK.  I'll look at them now.

> Probably should have flagged the struct flow changes as RFC, but the
> staged rearrangement was the most efficient implementation I could
> think of. There is an alternative that would allow arbitrary
> non-overlapping ?stage masks? to be used, but that would require
> explicit storage of those masks and/or more computation to combine
> those masks with the table?s masks. I did not fully explore this
> alternative, as it seemed to me that the classifier remains simpler
> this way.

I don't think that we should explore a more complex structure until we
conclude that it would be superior.