[ovs-dev] [PATCH] bfd: Make the tp_dst masking megaflow-friendly.

[Ben Pfaff]

On Wed, Oct 03, 2018 at 03:02:54PM -0700, Han Zhou wrote:
> On Wed, Oct 3, 2018 at 2:05 PM Ben Pfaff <blp at ovn.org> wrote:
> >
> > On Mon, Oct 01, 2018 at 02:12:29PM -0700, Han Zhou wrote:
> > > From: Han Zhou <hzhou8 at ebay.com>
> > >
> > > When there are tunnel ports with BFD enabled, all UDP flows will have
> > > dst port as match condition in datapath, which causes unnecessarily
> > > high flow miss for all UDP traffic, and results in latency increase.
> > > For more details, see [1].
> > >
> > > This patch solves the problem by masking tp_dst only for the leading
> > > bits that is enough to tell the mismatch when it is not BFD traffic.
> > >
> > > [1]
> https://mail.openvswitch.org/pipermail/ovs-discuss/2018-September/047360.html
> > >
> > > Signed-off-by: Han Zhou <hzhou8 at ebay.com>
> >
> > I think that we only need to "un-wildcard" one bit, not all the leading
> > bits.
> >
> > What do you think of the following slight generalization?
> >
> > Thanks,
> >
> > Ben.

> Thanks Ben. Yes, your version is better! I didn't realize that one bit is
> enough to tell the unmatching. It is more megaflow-friendly. Will you send
> the formal patch?

Oops, I just applied it, but here's a copy of formal version anyway:

--8<--------------------------cut here-------------------------->8--

From: Han Zhou <hzhou8 at ebay.com>
Date: Wed, 3 Oct 2018 15:11:20 -0700
Subject: [PATCH] bfd: Make the tp_dst masking megaflow-friendly.

When there are tunnel ports with BFD enabled, all UDP flows will have
dst port as match condition in datapath, which causes unnecessarily
high flow miss for all UDP traffic, and results in latency increase.

This patch solves the problem by masking tp_dst only for a single
bit that is enough to tell the mismatch when it is not BFD traffic.

Reported-at: https://mail.openvswitch.org/pipermail/ovs-discuss/2018-September/047360.html
Signed-off-by: Han Zhou <hzhou8 at ebay.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
---
 lib/bfd.c  | 23 +++++++++++------------
 lib/flow.h | 22 ++++++++++++++++++++++
 2 files changed, 33 insertions(+), 12 deletions(-)

diff --git a/lib/bfd.c b/lib/bfd.c
index 530826240c71..cc8c6857afa4 100644
--- a/lib/bfd.c
+++ b/lib/bfd.c
@@ -672,19 +672,18 @@ bfd_should_process_flow(const struct bfd *bfd_, const struct flow *flow,
 
     if (flow->dl_type == htons(ETH_TYPE_IP)) {
         memset(&wc->masks.nw_proto, 0xff, sizeof wc->masks.nw_proto);
-        if (flow->nw_proto == IPPROTO_UDP && !(flow->nw_frag & FLOW_NW_FRAG_LATER)) {
-            memset(&wc->masks.tp_dst, 0xff, sizeof wc->masks.tp_dst);
-            if (flow->tp_dst == htons(BFD_DEST_PORT)) {
-                bool check_tnl_key;
-
-                atomic_read_relaxed(&bfd->check_tnl_key, &check_tnl_key);
-                if (check_tnl_key) {
-                    memset(&wc->masks.tunnel.tun_id, 0xff,
-                           sizeof wc->masks.tunnel.tun_id);
-                    return flow->tunnel.tun_id == htonll(0);
-                }
-                return true;
+        if (flow->nw_proto == IPPROTO_UDP
+            && !(flow->nw_frag & FLOW_NW_FRAG_LATER)
+            && tp_dst_equals(flow, BFD_DEST_PORT, wc)) {
+            bool check_tnl_key;
+
+            atomic_read_relaxed(&bfd->check_tnl_key, &check_tnl_key);
+            if (check_tnl_key) {
+                memset(&wc->masks.tunnel.tun_id, 0xff,
+                       sizeof wc->masks.tunnel.tun_id);
+                return flow->tunnel.tun_id == htonll(0);
             }
+            return true;
         }
     }
     return false;
diff --git a/lib/flow.h b/lib/flow.h
index 1f6c1d6ae30d..902ab1bad5f1 100644
--- a/lib/flow.h
+++ b/lib/flow.h
@@ -1188,4 +1188,26 @@ static inline bool is_stp(const struct flow *flow)
             && eth_addr_equals(flow->dl_dst, eth_addr_stp));
 }
 
+/* Returns true if flow->tp_dst equals 'port'.  If 'wc' is nonnull, sets
+ * appropriate bits in wc->masks.tp_dst to account for the test.
+ *
+ * The caller must already have ensured that 'flow' is a protocol for which
+ * tp_dst is relevant. */
+static inline bool tp_dst_equals(const struct flow *flow, uint16_t port,
+                                 struct flow_wildcards *wc)
+{
+    uint16_t diff = port ^ ntohs(flow->tp_dst);
+    if (wc) {
+        if (diff) {
+            /* Set mask for the most significant mismatching bit. */
+            int ofs = raw_clz64((uint64_t) diff << 48); /* range [0,15] */
+            wc->masks.tp_dst |= htons(0x8000 >> ofs);
+        } else {
+            /* Must match all bits. */
+            wc->masks.tp_dst = OVS_BE16_MAX;
+        }
+    }
+    return !diff;
+}
+
 #endif /* flow.h */
-- 
2.16.1