[RFC] 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

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

From: Benjamin LaHaise <bcrl@lhnet.ca>
Date: Mon, 26 Oct 2009 20:03:02 -0400

> 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?

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.

> @@ -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);
>  

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.
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

On Mon, 26 Oct 2009 20:03:02 -0400
Benjamin LaHaise <bcrl@lhnet.ca> wrote:

> 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
> 

Any one doing large number of interfaces should be using FIB_TRIE?

On Mon, Oct 26, 2009 at 05:17:49PM -0700, David Miller wrote:
> > 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.

> 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
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Hello,

On Mon, 26 Oct 2009, Benjamin LaHaise wrote:

> 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.

	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.

> @@ -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 <ja@ssi.bg>

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

From: Benjamin LaHaise <bcrl@lhnet.ca>
Date: Tue, 27 Oct 2009 10:24:26 -0400

> On Mon, Oct 26, 2009 at 05:17:49PM -0700, David Miller wrote:
>> > 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.

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.
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html