| Message ID | 1538428349-41368-1-git-send-email-hzhou8@ebay.com |
|---|---|
| State | Accepted |
| Headers | show |
| Series | [ovs-dev] bfd: Make the tp_dst masking megaflow-friendly. | expand |
On Mon, Oct 01, 2018 at 02:12:29PM -0700, Han Zhou wrote: > From: Han Zhou <hzhou8@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@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. 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 */
On Wed, Oct 03, 2018 at 02:05:30PM -0700, Ben Pfaff wrote: > On Mon, Oct 01, 2018 at 02:12:29PM -0700, Han Zhou wrote: > > From: Han Zhou <hzhou8@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@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? Oh, I should also admit that I haven't tested this.
On Wed, Oct 3, 2018 at 2:05 PM Ben Pfaff <blp@ovn.org> wrote: > > On Mon, Oct 01, 2018 at 02:12:29PM -0700, Han Zhou wrote: > > From: Han Zhou <hzhou8@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@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. > > 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 */ 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?
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@ovn.org> wrote: > > > > On Mon, Oct 01, 2018 at 02:12:29PM -0700, Han Zhou wrote: > > > From: Han Zhou <hzhou8@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@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@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@ebay.com> Signed-off-by: Ben Pfaff <blp@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 */
On Wed, Oct 3, 2018 at 3:27 PM Ben Pfaff <blp@ovn.org> wrote: > > 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@ovn.org> wrote: > > > > > > On Mon, Oct 01, 2018 at 02:12:29PM -0700, Han Zhou wrote: > > > > From: Han Zhou <hzhou8@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@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@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@ebay.com> > Signed-off-by: Ben Pfaff <blp@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 > Thanks Ben. Do you mind back-porting to at least 2.10 and 2.9?
On Wed, Oct 03, 2018 at 03:30:48PM -0700, Han Zhou wrote: > On Wed, Oct 3, 2018 at 3:27 PM Ben Pfaff <blp@ovn.org> wrote: > > > > 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@ovn.org> wrote: > > > > > > > > On Mon, Oct 01, 2018 at 02:12:29PM -0700, Han Zhou wrote: > > > > > From: Han Zhou <hzhou8@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@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: > > Thanks Ben. Do you mind back-porting to at least 2.10 and 2.9? OK, done.
diff --git a/lib/bfd.c b/lib/bfd.c index 5308262..1697d02 100644 --- a/lib/bfd.c +++ b/lib/bfd.c @@ -656,6 +656,19 @@ bfd_put_packet(struct bfd *bfd, struct dp_packet *p, ovs_mutex_unlock(&mutex); } +static void +unwildcard_tp_dst(const struct flow *flow, struct flow_wildcards *wc) +{ + uint64_t diff = BFD_DEST_PORT ^ ntohs(flow->tp_dst); + if (diff) { + unsigned int eqbits = raw_clz64(diff << 48 | UINT64_C(1) << 47); + /* Set mask including the first mismatching bit. */ + wc->masks.tp_dst |= htons((uint16_t)~0u << (16 - eqbits -1)); + } else { + memset(&wc->masks.tp_dst, 0xff, sizeof wc->masks.tp_dst); + } +} + bool bfd_should_process_flow(const struct bfd *bfd_, const struct flow *flow, struct flow_wildcards *wc) @@ -673,7 +686,7 @@ 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); + unwildcard_tp_dst(flow, wc); if (flow->tp_dst == htons(BFD_DEST_PORT)) { bool check_tnl_key;