[ovs-dev] [PATCH 2/3] datapath: Mega flow implementation

[Andy Zhou]

The user space logic ensures no key will overlap (in the kernel), so the
order of masks are not important for correctness.

Ordering masks to improve efficiency is an interesting idea. However, it is
not clear ordering by mask specificity will gain efficiency -- there is no
guarantee that the frequency of exact match will be higher than that of
wildcarded match.   One possible solution is to order them by the 'hit
rate' collected at run time -- but may not work as well when traffic cycles
through masks with rapid bursts. Any other ideas?

Andy



On Wed, Jun 12, 2013 at 3:40 AM, Rajahalme, Jarno (NSN - FI/Espoo) <
jarno.rajahalme at nsn.com> wrote:

>
> On Jun 10, 2013, at 20:04 , ext Jesse Gross wrote:
> >
> >>>> +static bool __flow_cmp_key_mask(struct sw_flow *flow, u32 hash, u8
> >>>> *key,
> >>>> +                               int key_start, int key_len,
> >>>> +                               struct sw_flow_mask *mfm)
> >>>> +{
> >>>> +       return (flow->hash == hash && (flow->mfm == mfm) &&
> >>>> +               !memcmp((u8 *)&flow->key + key_start, key, (key_len -
> >>>> key_start)));
> >>>> +}
> >>>
> >>> Since the flows are non-overlapping, do we need to compare the masks?
> >>
> >> Yes, we are comparing masked key, which is no longer unique without
> >> comparing the mask.
> >
> > Well, more to the point, I think we want to make sure that they are
> > unique. The ordering of the masks has no inherent meaning so in order
> > to avoid surprising behavior I think we need to enforce that there is
> > no possibility of overlap. This should happen naturally when we start
> > looking up exact matches on flow setup.
>
> The masks could be added to the list so as to keep a partial ordering
> between the masks, where masks completely covering (have all the same
> 1-bits + some) other masks would be closer to the front. This way a full
> mask (if any) would be at front, and all-wildcards mask (if any) would be
> at the back. It would be safe to stop at first match from the beginning,
> and maybe more importantly, there would be no confusion nor any performance
> penalty for any exact (full mask) matches, as they would match at the first
> try. Any additional cycles would be spent only on flows that currently all
> go to userspace.
>
>   Jarno
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openvswitch.org/pipermail/ovs-dev/attachments/20130612/8fb92fc5/attachment-0003.html>