[PATCH net-next 1/3] ipv4: Lock-less per-packet multipath
From: Peter Nørlund <hidden>
Date: 2015-06-17 20:08:04
Also in:
netdev
Subsystem:
networking [general], networking [ipv4/ipv6], the rest · Maintainers:
"David S. Miller", Eric Dumazet, Jakub Kicinski, Paolo Abeni, David Ahern, Ido Schimmel, Linus Torvalds
Possibly related (same subject, not in this thread)
- 2015-06-20 · Re: [PATCH net-next 1/3] ipv4: Lock-less per-packet multipath · Peter Nørlund <hidden>
- 2015-06-18 · Re: [PATCH net-next 1/3] ipv4: Lock-less per-packet multipath · Alexander Duyck <hidden>
The current multipath attempted to be quasi random, but in most cases it behaved just like a round robin balancing. This patch refactors the algorithm to be exactly that and in doing so, avoids the spin lock. The new design paves the way for hash-based multipath, replacing the modulo with thresholds, minimizing disruption in case of failing paths or route replacements. Signed-off-by: Peter Nørlund <pch-chEQUL3jiZBWk0Htik3J/w@public.gmane.org> --- include/net/ip_fib.h | 6 +-- net/ipv4/Kconfig | 1 + net/ipv4/fib_semantics.c | 116 ++++++++++++++++++++++++++--------------------- 3 files changed, 68 insertions(+), 55 deletions(-)
diff --git a/include/net/ip_fib.h b/include/net/ip_fib.h
index 54271ed..4be4f25 100644
--- a/include/net/ip_fib.h
+++ b/include/net/ip_fib.h@@ -76,8 +76,8 @@ struct fib_nh { unsigned int nh_flags; unsigned char nh_scope; #ifdef CONFIG_IP_ROUTE_MULTIPATH - int nh_weight; - int nh_power; + int nh_mp_weight; + atomic_t nh_mp_upper_bound; #endif #ifdef CONFIG_IP_ROUTE_CLASSID __u32 nh_tclassid;
@@ -115,7 +115,7 @@ struct fib_info { #define fib_advmss fib_metrics[RTAX_ADVMSS-1] int fib_nhs; #ifdef CONFIG_IP_ROUTE_MULTIPATH - int fib_power; + int fib_mp_weight; #endif struct rcu_head rcu; struct fib_nh fib_nh[0];
diff --git a/net/ipv4/Kconfig b/net/ipv4/Kconfig
index d83071d..cb91f67 100644
--- a/net/ipv4/Kconfig
+++ b/net/ipv4/Kconfig@@ -81,6 +81,7 @@ config IP_MULTIPLE_TABLES config IP_ROUTE_MULTIPATH bool "IP: equal cost multipath" depends on IP_ADVANCED_ROUTER + select BITREVERSE help Normally, the routing tables specify a single action to be taken in a deterministic manner for a given packet. If you say Y here
diff --git a/net/ipv4/fib_semantics.c b/net/ipv4/fib_semantics.c
index 28ec3c1..8c8df80 100644
--- a/net/ipv4/fib_semantics.c
+++ b/net/ipv4/fib_semantics.c@@ -15,6 +15,7 @@ #include <asm/uaccess.h> #include <linux/bitops.h> +#include <linux/bitrev.h> #include <linux/types.h> #include <linux/kernel.h> #include <linux/jiffies.h>
@@ -57,7 +58,7 @@ static struct hlist_head fib_info_devhash[DEVINDEX_HASHSIZE]; #ifdef CONFIG_IP_ROUTE_MULTIPATH -static DEFINE_SPINLOCK(fib_multipath_lock); +static DEFINE_PER_CPU(u8, fib_mp_rr_counter); #define for_nexthops(fi) { \ int nhsel; const struct fib_nh *nh; \
@@ -261,7 +262,7 @@ static inline int nh_comp(const struct fib_info *fi, const struct fib_info *ofi) nh->nh_gw != onh->nh_gw || nh->nh_scope != onh->nh_scope || #ifdef CONFIG_IP_ROUTE_MULTIPATH - nh->nh_weight != onh->nh_weight || + nh->nh_mp_weight != onh->nh_mp_weight || #endif #ifdef CONFIG_IP_ROUTE_CLASSID nh->nh_tclassid != onh->nh_tclassid ||
@@ -449,6 +450,43 @@ static int fib_count_nexthops(struct rtnexthop *rtnh, int remaining) return remaining > 0 ? 0 : nhs; } +static void fib_rebalance(struct fib_info *fi) +{ + int factor; + int total; + int w; + + if (fi->fib_nhs < 2) + return; + + total = 0; + for_nexthops(fi) { + if (!(nh->nh_flags & RTNH_F_DEAD)) + total += nh->nh_mp_weight; + } endfor_nexthops(fi); + + if (likely(total != 0)) { + factor = DIV_ROUND_UP(total, 8388608); + total /= factor; + } else { + factor = 1; + } + + w = 0; + change_nexthops(fi) { + int upper_bound; + + if (nexthop_nh->nh_flags & RTNH_F_DEAD) { + upper_bound = -1; + } else { + w += nexthop_nh->nh_mp_weight / factor; + upper_bound = DIV_ROUND_CLOSEST(256 * w, total); + } + + atomic_set(&nexthop_nh->nh_mp_upper_bound, upper_bound); + } endfor_nexthops(fi); +} + static int fib_get_nhs(struct fib_info *fi, struct rtnexthop *rtnh, int remaining, struct fib_config *cfg) {
@@ -461,7 +499,7 @@ static int fib_get_nhs(struct fib_info *fi, struct rtnexthop *rtnh, nexthop_nh->nh_flags = (cfg->fc_flags & ~0xFF) | rtnh->rtnh_flags; nexthop_nh->nh_oif = rtnh->rtnh_ifindex; - nexthop_nh->nh_weight = rtnh->rtnh_hops + 1; + nexthop_nh->nh_mp_weight = rtnh->rtnh_hops + 1; attrlen = rtnh_attrlen(rtnh); if (attrlen > 0) {
@@ -884,7 +922,7 @@ struct fib_info *fib_create_info(struct fib_config *cfg) fi->fib_net->ipv4.fib_num_tclassid_users++; #endif #ifdef CONFIG_IP_ROUTE_MULTIPATH - nh->nh_weight = 1; + nh->nh_mp_weight = 1; #endif }
@@ -936,8 +974,15 @@ struct fib_info *fib_create_info(struct fib_config *cfg) change_nexthops(fi) { fib_info_update_nh_saddr(net, nexthop_nh); +#ifdef CONFIG_IP_ROUTE_MULTIPATH + fi->fib_mp_weight += nexthop_nh->nh_mp_weight; +#endif } endfor_nexthops(fi) +#ifdef CONFIG_IP_ROUTE_MULTIPATH + fib_rebalance(fi); +#endif + link_it: ofi = fib_find_info(fi); if (ofi) {
@@ -1050,7 +1095,7 @@ int fib_dump_info(struct sk_buff *skb, u32 portid, u32 seq, int event, goto nla_put_failure; rtnh->rtnh_flags = nh->nh_flags & 0xFF; - rtnh->rtnh_hops = nh->nh_weight - 1; + rtnh->rtnh_hops = nh->nh_mp_weight - 1; rtnh->rtnh_ifindex = nh->nh_oif; if (nh->nh_gw &&
@@ -1130,12 +1175,6 @@ int fib_sync_down_dev(struct net_device *dev, int force) else if (nexthop_nh->nh_dev == dev && nexthop_nh->nh_scope != scope) { nexthop_nh->nh_flags |= RTNH_F_DEAD; -#ifdef CONFIG_IP_ROUTE_MULTIPATH - spin_lock_bh(&fib_multipath_lock); - fi->fib_power -= nexthop_nh->nh_power; - nexthop_nh->nh_power = 0; - spin_unlock_bh(&fib_multipath_lock); -#endif dead++; } #ifdef CONFIG_IP_ROUTE_MULTIPATH
@@ -1149,6 +1188,10 @@ int fib_sync_down_dev(struct net_device *dev, int force) fi->fib_flags |= RTNH_F_DEAD; ret++; } + +#ifdef CONFIG_IP_ROUTE_MULTIPATH + fib_rebalance(fi); +#endif } return ret;
@@ -1254,16 +1297,15 @@ int fib_sync_up(struct net_device *dev) !__in_dev_get_rtnl(dev)) continue; alive++; - spin_lock_bh(&fib_multipath_lock); - nexthop_nh->nh_power = 0; nexthop_nh->nh_flags &= ~RTNH_F_DEAD; - spin_unlock_bh(&fib_multipath_lock); } endfor_nexthops(fi) if (alive > 0) { fi->fib_flags &= ~RTNH_F_DEAD; ret++; } + + fib_rebalance(fi); } return ret;
@@ -1276,49 +1318,19 @@ int fib_sync_up(struct net_device *dev) void fib_select_multipath(struct fib_result *res) { struct fib_info *fi = res->fi; - int w; - - spin_lock_bh(&fib_multipath_lock); - if (fi->fib_power <= 0) { - int power = 0; - change_nexthops(fi) { - if (!(nexthop_nh->nh_flags & RTNH_F_DEAD)) { - power += nexthop_nh->nh_weight; - nexthop_nh->nh_power = nexthop_nh->nh_weight; - } - } endfor_nexthops(fi); - fi->fib_power = power; - if (power <= 0) { - spin_unlock_bh(&fib_multipath_lock); - /* Race condition: route has just become dead. */ - res->nh_sel = 0; - return; - } - } + u8 w; + w = bitrev8(this_cpu_inc_return(fib_mp_rr_counter)); - /* w should be random number [0..fi->fib_power-1], - * it is pretty bad approximation. - */ - - w = jiffies % fi->fib_power; + for_nexthops(fi) { + if (w >= atomic_read(&nh->nh_mp_upper_bound)) + continue; - change_nexthops(fi) { - if (!(nexthop_nh->nh_flags & RTNH_F_DEAD) && - nexthop_nh->nh_power) { - w -= nexthop_nh->nh_power; - if (w <= 0) { - nexthop_nh->nh_power--; - fi->fib_power--; - res->nh_sel = nhsel; - spin_unlock_bh(&fib_multipath_lock); - return; - } - } + res->nh_sel = nhsel; + return; } endfor_nexthops(fi); - /* Race condition: route has just become dead. */ + /* Race condition: route has just become dead */ res->nh_sel = 0; - spin_unlock_bh(&fib_multipath_lock); } #endif
--
2.1.4