fib_hash: improve route deletion scaling on interface drop with lots of interfaces
Subsystems (3)
RFC PATCH 1/1 fib_hash: improve route deletion scaling on interface drop with lots of interfaces
Hi folks,
Below is a patch to improve the scaling of interface destruction in fib_hash. The general idea is to tie the fib_alias structure into a list off of net_device and walk that list during a fib_flush() caused by an interface drop. This makes the resulting flush only have to walk the number of routes attached to an interface rather than the number of routes attached to all interfaces at the expense of a couple of additional pointers in struct fib_alias.
This patch is against Linus' tree. I'll post against net-next after a bit more testing and feedback. With 20,000 interfaces & routes, interface deletion time improves from 53s to 40s. Note that this is with other changes applied to improve sysfs and procfs scaling, as otherwise those are the bottleneck. Next up in the network code is rt_cache_flush(). Comments?
-ben
include/linux/netdevice.h +1 -0
@@ -856,6 +856,7 @@ struct net_device/* delayed register/unregister */ struct list_head todo_list; +struct list_head fib_list;/* device index hash chain */ struct hlist_node index_hlist;
include/net/ip_fib.h +1 -1
@@ -149,7 +149,7 @@ struct fib_table {int (*tb_delete)(struct fib_table *,struct fib_config *);int (*tb_dump)(struct fib_table *table,struct sk_buff *skb,struct netlink_callback *cb); -int (*tb_flush)(struct fib_table *table); +int (*tb_flush)(struct fib_table *table,struct net_device *dev);void (*tb_select_default)(struct fib_table *table,const struct flowi *flp,struct fib_result *res);
net/core/dev.c +1 -0
@@ -5173,6 +5173,7 @@ struct net_device *alloc_netdev_mq(int sizeof_priv, const char *name,netdev_init_queues (dev);INIT_LIST_HEAD (&dev->napi_list); +INIT_LIST_HEAD (&dev->fib_list); dev->priv_flags =IFF_XMIT_DST_RELEASE ;setup (dev);strcpy (dev->name, name);
net/ipv4/fib_frontend.c +6 -5
@@ -128,18 +128,19 @@ void fib_select_default(struct net *net, tb->tb_select_default (tb, flp, res); } -static void fib_flush (struct net *net) +static void fib_flush (struct net_device *dev) {int flushed =0 ;struct fib_table *tb;struct hlist_node *node;struct hlist_head *head;unsigned int h; +struct net *net =dev_net (dev);for (h =0 ; h <FIB_TABLE_HASHSZ ; h++) { head = &net->ipv4.fib_table_hash[h];hlist_for_each_entry (tb, node, head, tb_hlist) - flushed += tb->tb_flush (tb); + flushed += tb->tb_flush (tb, dev); }if (flushed)
@@ -805,7 +806,7 @@ static void fib_del_ifaddr(struct in_ifaddr *ifa)for stray nexthop entries, then ignite fib_flush. */ if (fib_sync_down_addr (dev_net (dev), ifa->ifa_local)) -fib_flush (dev_net (dev)); +fib_flush (dev); } }#undef LOCAL_OK
@@ -895,7 +896,7 @@ static void nl_fib_lookup_exit(struct net *net)static void fib_disable_ip (struct net_device *dev,int force) {if (fib_sync_down_dev (dev, force)) -fib_flush (dev_net (dev)); +fib_flush (dev);rt_cache_flush (dev_net (dev),0 );arp_ifdown (dev); }
@@ -1009,7 +1010,7 @@ static void __net_exit ip_fib_net_exit(struct net *net) head = &net->ipv4.fib_table_hash[i];hlist_for_each_entry_safe (tb, node, tmp, head, tb_hlist) {hlist_del (node); - tb->tb_flush (tb); + tb->tb_flush (tb,NULL );kfree (tb); } }
net/ipv4/fib_hash.c +65 -5
112 lines not on this page · raw message
net/ipv4/fib_lookup.h +8 -0
@@ -5,9 +5,17 @@#include <linux/list.h> #include <net/ip_fib.h> +struct fib_node ; +struct fn_zone ; +struct fib_alias {struct list_head fa_list; +struct list_head fa_dev_list;struct fib_info *fa_info; +#ifdef CONFIG_IP_FIB_HASH +struct fib_node *fa_fib_node; +struct fn_zone *fa_fz; +#endif u8 fa_tos;u8 fa_type;u8 fa_scope;
net/ipv4/fib_trie.c +1 -1
@@ -1786,7 +1786,7 @@ static struct leaf *trie_leafindex(struct trie *t, int index)/* * Caller must hold RTNL. */ -static int fn_trie_flush (struct fib_table *tb) +static int fn_trie_flush (struct fib_table *tb,struct net_device *dev) {struct trie *t = (struct trie *) tb->tb_data;struct leaf *l, *ll =NULL ;
David Miller
maintainerFrom: Benjamin LaHaise <[email protected]>
Date: Mon, 26 Oct 2009 20:03:02 -0400
Quoted 8 lines
Below is a patch to improve the scaling of interface destruction in
fib_hash. The general idea is to tie thefib_aliasstructure into a list off ofnet_deviceand walk that list during afib_flush()caused by an interface drop. This makes the resulting flush only have to walk the number of routes attached to an interface rather than the number of routes attached to all interfaces at the expense of a couple of additional pointers in structfib_alias.
Quoted 5 lines
This patch is against Linus' tree. I'll post against net-next after a bit more testing and feedback. With 20,000 interfaces & routes, interface deletion time improves from 53s to 40s. Note that this is with other changes applied to improve sysfs and procfs scaling, as otherwise those are the bottleneck. Next up in the network code is
rt_cache_flush(). Comments?
On a real router adding and removing routes is happening a lot whereas interface changes are rare. You're making a more common operation more expensive for the sake of a less common one.
Quoted 4 lines
net/ipv4/fib_frontend.c +0
-0@@ -128,18 +128,19 @@ void fib_select_default(struct net *net, tb->tb_select_default (tb, flp, res); }
net/ipv4/fib_frontend.c void fib_select_default(struct net *net, · line 139
Quoted 10 lines
net/ipv4/fib_frontend.c +2
-1-static void fib_flush (struct net *net) +static void fib_flush (struct net_device *dev) {int flushed =0 ;struct fib_table *tb;struct hlist_node *node;struct hlist_head *head;unsigned int h; +struct net *net =dev_net (dev);
Please put local variable lines that are longer at the beginning of the list of variable declarations at the top of a function, not the other way around which stands out like a sore thumb and looks ugly.
Quoted 10 lines · On Mon, 26 Oct 2009 20:03:02 -0400 Benjamin LaHaise <[email protected]> wrote:
Hi folks,
Below is a patch to improve the scaling of interface destruction in
fib_hash. The general idea is to tie thefib_aliasstructure into a list off ofnet_deviceand walk that list during afib_flush()caused by an interface drop. This makes the resulting flush only have to walk the number of routes attached to an interface rather than the number of routes attached to all interfaces at the expense of a couple of additional pointers in structfib_alias.
Quoted 8 lines
This patch is against Linus' tree. I'll post against net-next after a bit more testing and feedback. With 20,000 interfaces & routes, interface deletion time improves from 53s to 40s. Note that this is with other changes applied to improve sysfs and procfs scaling, as otherwise those are the bottleneck. Next up in the network code is
rt_cache_flush(). Comments?-ben
Any one doing large number of interfaces should be using FIB_TRIE?
Quoted 5 lines · David Miller
Quoted 1 line
bottleneck. Next up in the network code is
rt_cache_flush(). Comments?On a real router adding and removing routes is happening a lot whereas interface changes are rare. You're making a more common operation more expensive for the sake of a less common one.
It's not a question of more common vs less common, but if the system can recover from an adverse event within a reasonable amount of time. Tunnel flaps occur in the real world, and this results in the change of state of a large number of interfaces at the same time. Would it be okay if this is wrapped in a config option? I agree that the extra overhead is not for everyone.
Quoted 3 lines
Please put local variable lines that are longer at the beginning of the list of variable declarations at the top of a function, not the other way around which stands out like a sore thumb and looks ugly.
Whoops, will fix.
-ben
Hello,
Quoted 9 lines · Benjamin LaHaise
Hi folks,
Below is a patch to improve the scaling of interface destruction in
fib_hash. The general idea is to tie thefib_aliasstructure into a list off ofnet_deviceand walk that list during afib_flush()caused by an interface drop. This makes the resulting flush only have to walk the number of routes attached to an interface rather than the number of routes attached to all interfaces at the expense of a couple of additional pointers in structfib_alias.
May be this can not work for multipath routes because
you consider only the first device (fib_dev). Also nh_dev is optional, not every route has device, so you should add checks for dev ! NULL.
net/ipv4/fib_hash.c static int fn_hash_insert(struct fib_table *tb, struct fib_config *cfg) · line 523
Quoted 8 lines
net/ipv4/fib_hash.c +4
-0@@ -516,6 +517,10 @@ static int fn_hash_insert(struct fib_table *tb, struct fib_config *cfg) new_fa->fa_type = cfg->fc_type; new_fa->fa_scope = cfg->fc_scope; new_fa->fa_state =0 ; + new_fa->fa_fib_node = f; + new_fa->fa_fz = fz; + + dev = fi->fib_dev;
Regards
--
Julian Anastasov <[email protected]>
David Miller
maintainerFrom: Benjamin LaHaise <[email protected]>
Date: Tue, 27 Oct 2009 10:24:26 -0400
Quoted 7 lines · David Miller
Quoted 5 lines
Quoted 1 line
bottleneck. Next up in the network code is
rt_cache_flush(). Comments?On a real router adding and removing routes is happening a lot whereas interface changes are rare. You're making a more common operation more expensive for the sake of a less common one.
Quoted 6 lines
It's not a question of more common vs less common, but if the system can recover from an adverse event within a reasonable amount of time. Tunnel flaps occur in the real world, and this results in the change of state of a large number of interfaces at the same time. Would it be okay if this is wrapped in a config option? I agree that the extra overhead is not for everyone.
Having it in a config option is worse, distributions are going to turn it on so it would be protecting nothing for %99.999 of folks out there.