[ovs-discuss] Datapath implementation query

[Prathap T]

Hi Jesse:

  "Imagine a 1 bit long flow. The flow in the table has the value 0 and
the mask is 1 (significant). There is also another mask with the value
0 (not significant). If a packet came in with the header value of 1
and it tried the second mask first then the value would become 0,
matching the flow in table on the basis of a strict comparison.
However, in reality these flows don't match."

I could guess this, but I could not really understand on when this would
happen. In the case you have mentioned, dosen't the flow with the
mask of 1 be of a higher priority then the other one in the userspace?
dosen't the userspace take care to generate datapath flows that will have
the masks of higher priority entries, and in the example, it is almost
impossible to have the 1 bit flow that has a mask with value 0 because of
priority? Please help me understand.

Yes it is a functionality similar to TCAM. However in our hardware we have
limited TCAM and we have to deal with millions of entries in which case we
use h/w implemented hash tables.

Regards,
Prathap

On Fri, Apr 15, 2016 at 2:09 AM, Jesse Gross <jesse at kernel.org> wrote:

> On Thu, Apr 14, 2016 at 11:09 AM, Prathap T <prathap.bgl at gmail.com> wrote:
> > Hi OVS-Team:
> >
> >   We are porting OVS onto one of our hardware and I had a question in the
> > kernel datapath implementation.
> >
> > In the function - masked_flow_lookup
> >
> > ovs_flow_mask_key(&masked_key, unmasked, mask);
> >     hash = flow_hash(&masked_key, &mask->range);
> >     head = find_bucket(ti, hash);
> >     (*n_mask_hit)++;
> >     hlist_for_each_entry_rcu(flow, head, flow_table.node[ti->node_ver]) {
> >         if (flow->mask == mask && flow->flow_table.hash == hash &&
> >             flow_cmp_masked_key(flow, &masked_key, &mask->range))
> >             return flow;
> >     }
> >
> > why is that the code compares the flow->mask == mask; is it not enough to
> > just compare the key?? Is it just an optimization??
> > If mask comparison is needed, can you please explain the traffic context
> > that makes this necessary?
>
> It's not an optimization, it's necessary for correctness.
>
> Masks are inherently tied to the flows that they are masking. The
> simplest implementation of what is being done here would be a linear
> search over each flow, masking the incoming packet headers and doing a
> comparison with the stored flow. As an optimization, we do the masking
> once for each mask and then do a hash table lookup over all flows that
> use that mask since it is common for flows to share masks. However, we
> still must act as if the mask and flow are paired.
>
> Imagine a 1 bit long flow. The flow in the table has the value 0 and
> the mask is 1 (significant). There is also another mask with the value
> 0 (not significant). If a packet came in with the header value of 1
> and it tried the second mask first then the value would become 0,
> matching the flow in table on the basis of a strict comparison.
> However, in reality these flows don't match.
>
> > The reason I'm asking is that, we have some space issues and cannot store
> > anymore than the keys in the hardware structure. If the mask comparison
> is
> > not needed, we may want to skip it. If it is needed, we will have to
> > compromise on some of the key elements.
>
> I suspect that there are better ways of using your hardware rather
> than directly porting this logic. For example, this function is pretty
> much exactly mirroring the logic implemented in a TCAM.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://openvswitch.org/pipermail/ovs-discuss/attachments/20160415/314a47b2/attachment-0002.html>