[PATCH] dev: use name hash for dev_seq_ops.

[PATCH] dev: use name hash for dev_seq_ops.

[Mihai Maruseac]

Instead of using the dev->next chain and trying to resync at each call to
dev_seq_start, use this hash and store bucket number and bucket offset in
seq->private field.

Tests revealed the following results for ifconfig > /dev/null
	* 1000 interfaces:
		* 0.114s without patch
		* 0.020s with patch
	* 3000 interfaces:
		* 0.489s without patch
		* 0.048s with patch
	* 5000 interfaces:
		* 1.363s without patch
		* 0.131s with patch

As one can notice the improvement is of 1 order of magnitude.

Signed-off-by: Mihai Maruseac <mmaruseac@ixiacom.com>
---
 net/core/dev.c |   73 +++++++++++++++++++++++++++++++++++++++++++-------------
 1 files changed, 56 insertions(+), 17 deletions(-)

diff --git a/net/core/dev.c b/net/core/dev.c
index bf49a47..2d0f126 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -4034,6 +4034,51 @@ static int dev_ifconf(struct net *net, char __user *arg)
 }
 
 #ifdef CONFIG_PROC_FS
+
+struct dev_iter_state {
+	struct seq_net_private p;
+	int bucket;
+	int offset;
+};
+
+static inline struct net_device *dev_from_same_bucket(struct seq_file *seq)
+{
+	struct net_device *dev = NULL;
+	struct net *net = seq_file_net(seq);
+	struct dev_iter_state *state = seq->private;
+	struct hlist_node *p;
+	struct hlist_head *h;
+	int count;
+
+	h = &net->dev_name_head[state->bucket];
+	count = 0;
+	hlist_for_each_entry_rcu(dev, p, h, name_hlist) {
+		if (count++ == state->offset) {
+			state->offset = count;
+			return dev;
+		}
+	}
+
+	return NULL;
+}
+
+static inline struct net_device *dev_from_new_bucket(struct seq_file *seq)
+{
+	struct dev_iter_state *state = seq->private;
+	struct net_device *dev = NULL;
+
+	while (state->bucket < NETDEV_HASHENTRIES) {
+		dev = dev_from_same_bucket(seq);
+		if (dev)
+			return dev;
+
+		state->bucket++;
+		state->offset = 0;
+	}
+
+	return NULL;
+}
+
 /*
  *	This is invoked by the /proc filesystem handler to display a device
  *	in detail.
@@ -4041,33 +4086,27 @@ static int dev_ifconf(struct net *net, char __user *arg)
 void *dev_seq_start(struct seq_file *seq, loff_t *pos)
 	__acquires(RCU)
 {
-	struct net *net = seq_file_net(seq);
-	loff_t off;
-	struct net_device *dev;
-
 	rcu_read_lock();
 	if (!*pos)
 		return SEQ_START_TOKEN;
 
-	off = 1;
-	for_each_netdev_rcu(net, dev)
-		if (off++ == *pos)
-			return dev;
-
-	return NULL;
+	return dev_from_new_bucket(seq);
 }
 
 void *dev_seq_next(struct seq_file *seq, void *v, loff_t *pos)
 {
-	struct net_device *dev = v;
+	struct net_device *dev = NULL;
+
+	++*pos;
 
 	if (v == SEQ_START_TOKEN)
-		dev = first_net_device_rcu(seq_file_net(seq));
-	else
-		dev = next_net_device_rcu(dev);
+		return dev_from_new_bucket(seq);
 
-	++*pos;
-	return dev;
+	dev = dev_from_same_bucket(seq);
+	if (dev)
+		return dev;
+
+	return dev_from_new_bucket(seq);
 }
 
 void dev_seq_stop(struct seq_file *seq, void *v)
@@ -4166,7 +4205,7 @@ static const struct seq_operations dev_seq_ops = {
 static int dev_seq_open(struct inode *inode, struct file *file)
 {
 	return seq_open_net(inode, file, &dev_seq_ops,
-			    sizeof(struct seq_net_private));
+			    sizeof(struct dev_iter_state));
 }
 
 static const struct file_operations dev_seq_fops = {
-- 
1.7.4.1

Re: [PATCH] dev: use name hash for dev_seq_ops.

[Stephen Hemminger]

On Fri,  7 Oct 2011 18:20:49 +0300
Mihai Maruseac <mihai.maruseac@gmail.com> wrote:

> Instead of using the dev->next chain and trying to resync at each call to
> dev_seq_start, use this hash and store bucket number and bucket offset in
> seq->private field.
> 
> Tests revealed the following results for ifconfig > /dev/null
> 	* 1000 interfaces:
> 		* 0.114s without patch
> 		* 0.020s with patch
> 	* 3000 interfaces:
> 		* 0.489s without patch
> 		* 0.048s with patch
> 	* 5000 interfaces:
> 		* 1.363s without patch
> 		* 0.131s with patch
> 
> As one can notice the improvement is of 1 order of magnitude.

Good idea,
This will change the ordering of entries in /proc which may upset
some program, not a critical flaw but worth noting.

Rather than recording the bucket and offset of last entry, another
alternative would be to just record the ifindex.

Also ifconfig is considered deprecated and replaced by ip commands
for general use.

Re: [PATCH] dev: use name hash for dev_seq_ops.

[Mihai Maruseac]

On Fri, Oct 7, 2011 at 7:24 PM, Stephen Hemminger <shemminger@vyatta.com> wrote:
> On Fri,  7 Oct 2011 18:20:49 +0300
> Mihai Maruseac <mihai.maruseac@gmail.com> wrote:
>
>> Instead of using the dev->next chain and trying to resync at each call to
>> dev_seq_start, use this hash and store bucket number and bucket offset in
>> seq->private field.
>>
>> Tests revealed the following results for ifconfig > /dev/null
>>       * 1000 interfaces:
>>               * 0.114s without patch
>>               * 0.020s with patch
>>       * 3000 interfaces:
>>               * 0.489s without patch
>>               * 0.048s with patch
>>       * 5000 interfaces:
>>               * 1.363s without patch
>>               * 0.131s with patch
>>
>> As one can notice the improvement is of 1 order of magnitude.
>
> Good idea,
> This will change the ordering of entries in /proc which may upset
> some program, not a critical flaw but worth noting.
>
> Rather than recording the bucket and offset of last entry, another
> alternative would be to just record the ifindex.
>
> Also ifconfig is considered deprecated and replaced by ip commands
> for general use.
>

Thanks,
This is a patch from a series of improvements to both the ifconfig and
ip commands. The ip part will come later, after being properly
implemented and tested.

-- 
Mihai

Re: [PATCH] dev: use name hash for dev_seq_ops.

[Mihai Maruseac]

On Fri, Oct 7, 2011 at 7:24 PM, Stephen Hemminger <shemminger@vyatta.com> wrote:
> On Fri,  7 Oct 2011 18:20:49 +0300
> Mihai Maruseac <mihai.maruseac@gmail.com> wrote:
>
>> Instead of using the dev->next chain and trying to resync at each call to
>> dev_seq_start, use this hash and store bucket number and bucket offset in
>> seq->private field.
>>
>> As one can notice the improvement is of 1 order of magnitude.
>
> Good idea,
> This will change the ordering of entries in /proc which may upset
> some program, not a critical flaw but worth noting.
>
> Rather than recording the bucket and offset of last entry, another
> alternative would be to just record the ifindex.
>

I tried to record the ifindex but I think that using it and
dev_get_by_index can result in an infinite loop or a NULL
dereferrence. If a device is removed and ifindex points to it we'll
get a NULL from dev_get_by_index. Checking for NULL and calling again
dev_get_by_index will end in an infinite loop at the end of the hlist.

Augmenting the structure to also contain the number of indexes when
the seq_file is opened returns to the current situation with two ints.
Also, it is more prone to bugs caused by device removal while
printing.

-- 
Mihai

Re: [PATCH] dev: use name hash for dev_seq_ops.

[Stephen Hemminger]

On Mon, 10 Oct 2011 11:43:20 +0300
Mihai Maruseac <mihai.maruseac@gmail.com> wrote:

> On Fri, Oct 7, 2011 at 7:24 PM, Stephen Hemminger <shemminger@vyatta.com> wrote:
> > On Fri,  7 Oct 2011 18:20:49 +0300
> > Mihai Maruseac <mihai.maruseac@gmail.com> wrote:
> >
> >> Instead of using the dev->next chain and trying to resync at each call to
> >> dev_seq_start, use this hash and store bucket number and bucket offset in
> >> seq->private field.
> >>
> >> As one can notice the improvement is of 1 order of magnitude.
> >
> > Good idea,
> > This will change the ordering of entries in /proc which may upset
> > some program, not a critical flaw but worth noting.
> >
> > Rather than recording the bucket and offset of last entry, another
> > alternative would be to just record the ifindex.
> >
> 
> I tried to record the ifindex but I think that using it and
> dev_get_by_index can result in an infinite loop or a NULL
> dereferrence. If a device is removed and ifindex points to it we'll
> get a NULL from dev_get_by_index. Checking for NULL and calling again
> dev_get_by_index will end in an infinite loop at the end of the hlist.
> 
> Augmenting the structure to also contain the number of indexes when
> the seq_file is opened returns to the current situation with two ints.
> Also, it is more prone to bugs caused by device removal while
> printing.

If ifindex has been deleted, the code should fall back to delivering
the next offset. That means for the rare case it would have the old
behavior of linear searching.  There is similar code already to
deal with /proc/net/route; it continues from the last address.

Re: [PATCH] dev: use name hash for dev_seq_ops.

[Mihai Maruseac]

On Mon, 2011-10-10 at 22:55 -0700, Stephen Hemminger wrote:
> If ifindex has been deleted, the code should fall back to delivering
> the next offset. That means for the rare case it would have the old
> behavior of linear searching.  There is similar code already to
> deal with /proc/net/route; it continues from the last address.

We rewrote the patch to use the ifindex. Since we are at the beginning,
the patch was sent in another thread. We'll learn how to properly send
the mail.

-- 
Thanks,
Mihai

[PATCH] dev: use ifindex hash for dev_seq_ops

[Mihai Maruseac]

Instead of using the dev->next chain and trying to resync at each call to
dev_seq_start, use the ifindex, keeping the last index in seq->private field.

Tests revealed the following results for ifconfig > /dev/null
	* 1000 interfaces:
		* 0.114s without patch
		* 0.089s with patch
	* 3000 interfaces:
		* 0.489s without patch
		* 0.110s with patch
	* 5000 interfaces:
		* 1.363s without patch
		* 0.250s with patch
	* 128000 interfaces (other setup):
		* ~100s without patch
		* ~30s with patch
---
 net/core/dev.c |   53 ++++++++++++++++++++++++++++++++---------------------
 1 files changed, 32 insertions(+), 21 deletions(-)

diff --git a/net/core/dev.c b/net/core/dev.c
index 70ecb86..3ca0df8 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -4041,6 +4041,35 @@ static int dev_ifconf(struct net *net, char __user *arg)
 }
 
 #ifdef CONFIG_PROC_FS
+
+struct dev_iter_state {
+	struct seq_net_private p;
+	int ifindex;
+};
+
+static inline struct net_device* next_dev(struct seq_file *seq, loff_t *pos)
+{
+	struct dev_iter_state *state = seq->private;
+	struct net *net = seq_file_net(seq);
+	struct net_device *dev = NULL;
+	loff_t off;
+
+	++*pos;
+	dev = dev_get_by_index_rcu(net, state->ifindex);
+	state->ifindex++;
+	if (likely(dev))
+		return dev;
+
+	off = 1;
+	for_each_netdev_rcu(net, dev)
+		if (off++ == *pos) {
+			state->ifindex = dev->ifindex + 1;
+			return dev;
+		}
+
+	return NULL;
+}
+
 /*
  *	This is invoked by the /proc filesystem handler to display a device
  *	in detail.
@@ -4048,33 +4077,15 @@ static int dev_ifconf(struct net *net, char __user *arg)
 void *dev_seq_start(struct seq_file *seq, loff_t *pos)
 	__acquires(RCU)
 {
-	struct net *net = seq_file_net(seq);
-	loff_t off;
-	struct net_device *dev;
-
 	rcu_read_lock();
 	if (!*pos)
 		return SEQ_START_TOKEN;
-
-	off = 1;
-	for_each_netdev_rcu(net, dev)
-		if (off++ == *pos)
-			return dev;
-
-	return NULL;
+	return next_dev(seq, pos);
 }
 
 void *dev_seq_next(struct seq_file *seq, void *v, loff_t *pos)
 {
-	struct net_device *dev = v;
-
-	if (v == SEQ_START_TOKEN)
-		dev = first_net_device_rcu(seq_file_net(seq));
-	else
-		dev = next_net_device_rcu(dev);
-
-	++*pos;
-	return dev;
+	return next_dev(seq, pos);
 }
 
 void dev_seq_stop(struct seq_file *seq, void *v)
@@ -4173,7 +4184,7 @@ static const struct seq_operations dev_seq_ops = {
 static int dev_seq_open(struct inode *inode, struct file *file)
 {
 	return seq_open_net(inode, file, &dev_seq_ops,
-			    sizeof(struct seq_net_private));
+			    sizeof(struct dev_iter_state));
 }
 
 static const struct file_operations dev_seq_fops = {
-- 
1.7.4.1

[PATCH] dev: use ifindex hash for dev_seq_ops

[Mihai Maruseac]

Instead of using the dev->next chain and trying to resync at each call to
dev_seq_start, use the ifindex, keeping the last index in seq->private field.

Tests revealed the following results for ifconfig > /dev/null
	* 1000 interfaces:
		* 0.114s without patch
		* 0.089s with patch
	* 3000 interfaces:
		* 0.489s without patch
		* 0.110s with patch
	* 5000 interfaces:
		* 1.363s without patch
		* 0.250s with patch
	* 128000 interfaces (other setup):
		* ~100s without patch
		* ~30s with patch

Signed-off-by: Mihai Maruseac <mmaruseac@ixiacom.com>
---
 net/core/dev.c |   53 ++++++++++++++++++++++++++++++++---------------------
 1 files changed, 32 insertions(+), 21 deletions(-)

diff --git a/net/core/dev.c b/net/core/dev.c
index 70ecb86..3ca0df8 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -4041,6 +4041,35 @@ static int dev_ifconf(struct net *net, char __user *arg)
 }
 
 #ifdef CONFIG_PROC_FS
+
+struct dev_iter_state {
+	struct seq_net_private p;
+	int ifindex;
+};
+
+static inline struct net_device *next_dev(struct seq_file *seq, loff_t *pos)
+{
+	struct dev_iter_state *state = seq->private;
+	struct net *net = seq_file_net(seq);
+	struct net_device *dev = NULL;
+	loff_t off;
+
+	++*pos;
+	dev = dev_get_by_index_rcu(net, state->ifindex);
+	state->ifindex++;
+	if (likely(dev))
+		return dev;
+
+	off = 1;
+	for_each_netdev_rcu(net, dev)
+		if (off++ == *pos) {
+			state->ifindex = dev->ifindex + 1;
+			return dev;
+		}
+
+	return NULL;
+}
+
 /*
  *	This is invoked by the /proc filesystem handler to display a device
  *	in detail.
@@ -4048,33 +4077,15 @@ static int dev_ifconf(struct net *net, char __user *arg)
 void *dev_seq_start(struct seq_file *seq, loff_t *pos)
 	__acquires(RCU)
 {
-	struct net *net = seq_file_net(seq);
-	loff_t off;
-	struct net_device *dev;
-
 	rcu_read_lock();
 	if (!*pos)
 		return SEQ_START_TOKEN;
-
-	off = 1;
-	for_each_netdev_rcu(net, dev)
-		if (off++ == *pos)
-			return dev;
-
-	return NULL;
+	return next_dev(seq, pos);
 }
 
 void *dev_seq_next(struct seq_file *seq, void *v, loff_t *pos)
 {
-	struct net_device *dev = v;
-
-	if (v == SEQ_START_TOKEN)
-		dev = first_net_device_rcu(seq_file_net(seq));
-	else
-		dev = next_net_device_rcu(dev);
-
-	++*pos;
-	return dev;
+	return next_dev(seq, pos);
 }
 
 void dev_seq_stop(struct seq_file *seq, void *v)
@@ -4173,7 +4184,7 @@ static const struct seq_operations dev_seq_ops = {
 static int dev_seq_open(struct inode *inode, struct file *file)
 {
 	return seq_open_net(inode, file, &dev_seq_ops,
-			    sizeof(struct seq_net_private));
+			    sizeof(struct dev_iter_state));
 }
 
 static const struct file_operations dev_seq_fops = {
-- 
1.7.4.1

Re: [PATCH] dev: use ifindex hash for dev_seq_ops

[Mihai Maruseac]

On Wed, 2011-10-12 at 02:57 -0700, Mihai Maruseac wrote:
> Instead of using the dev->next chain and trying to resync at each call to
> dev_seq_start, use the ifindex, keeping the last index in seq->private field.

Please consider only my last patch email, the first one was missing
Signed-off-by line.

Thanks,
Mihai

Re: [PATCH] dev: use ifindex hash for dev_seq_ops

[Stephen Hemminger]

On Wed, 12 Oct 2011 12:57:26 +0300
Mihai Maruseac <mihai.maruseac@gmail.com> wrote:

It looks like you lost the ability to seek back and read the header
(start token).  How is the header handled, is possible to rewind
the file and read it over again?


> +static inline struct net_device *next_dev(struct seq_file *seq, loff_t *pos)
> +{
> +	struct dev_iter_state *state = seq->private;
> +	struct net *net = seq_file_net(seq);
> +	struct net_device *dev = NULL;
> +	loff_t off;
> +
> +	++*pos;
> +	dev = dev_get_by_index_rcu(net, state->ifindex);

Looks good a couple of minor nits.

1. The function should not be inline, since it is in no way performance
   critical. The compiler will probably inline it anyway.

2. dev does not have to be initialized since it is assigned a few
   lines later.  Most programmers are trained now to always initialize
   variables, but often it is unnecessary.

3. The name next_dev() is a little generic; maybe a better name.

Re: [PATCH] dev: use ifindex hash for dev_seq_ops

[Mihai Maruseac]

On Wed, Oct 12, 2011 at 6:50 PM, Stephen Hemminger
<shemminger@vyatta.com> wrote:
> On Wed, 12 Oct 2011 12:57:26 +0300
> Mihai Maruseac <mihai.maruseac@gmail.com> wrote:
>
> It looks like you lost the ability to seek back and read the header
> (start token).  How is the header handled, is possible to rewind
> the file and read it over again?

We tested with a simple program reading a part of the /proc file and
then doing a seek to the start and rereading. It worked with latest
submitted patch.

>> +static inline struct net_device *next_dev(struct seq_file *seq, loff_t *pos)
>> +{
>> +     struct dev_iter_state *state = seq->private;
>> +     struct net *net = seq_file_net(seq);
>> +     struct net_device *dev = NULL;
>> +     loff_t off;
>> +
>> +     ++*pos;
>> +     dev = dev_get_by_index_rcu(net, state->ifindex);
>
> Looks good a couple of minor nits.
>
> 1. The function should not be inline, since it is in no way performance
>   critical. The compiler will probably inline it anyway.
>
> 2. dev does not have to be initialized since it is assigned a few
>   lines later.  Most programmers are trained now to always initialize
>   variables, but often it is unnecessary.
>
> 3. The name next_dev() is a little generic; maybe a better name.
>

Fixed all of them,

Thanks,
-- 
Mihai

[PATCH] dev: use ifindex hash for dev_seq_ops

[Mihai Maruseac]

Instead of using the dev->next chain and trying to resync at each call to
dev_seq_start, use the ifindex, keeping the last index in seq->private field.

Tests revealed the following results for ifconfig > /dev/null
	* 1000 interfaces:
		* 0.114s without patch
		* 0.089s with patch
	* 3000 interfaces:
		* 0.489s without patch
		* 0.110s with patch
	* 5000 interfaces:
		* 1.363s without patch
		* 0.250s with patch
	* 128000 interfaces (other setup):
		* ~100s without patch
		* ~30s with patch

Signed-off-by: Mihai Maruseac <mmaruseac@ixiacom.com>
---
 net/core/dev.c |   55 ++++++++++++++++++++++++++++++++++---------------------
 1 files changed, 34 insertions(+), 21 deletions(-)

diff --git a/net/core/dev.c b/net/core/dev.c
index 70ecb86..ea24445 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -4041,6 +4041,37 @@ static int dev_ifconf(struct net *net, char __user *arg)
 }
 
 #ifdef CONFIG_PROC_FS
+
+struct dev_iter_state {
+	struct seq_net_private p;
+	int ifindex;
+};
+
+static struct net_device *__dev_seq_next(struct seq_file *seq, loff_t *pos)
+{
+	struct dev_iter_state *state = seq->private;
+	struct net *net = seq_file_net(seq);
+	struct net_device *dev;
+	loff_t off;
+
+	dev = dev_get_by_index_rcu(net, state->ifindex);
+	if (likely(dev))
+		goto found;
+
+	off = 0;
+	for_each_netdev_rcu(net, dev)
+		if (off++ == *pos) {
+			state->ifindex = dev->ifindex;
+			goto found;
+		}
+
+	return NULL;
+found:
+	state->ifindex++;
+	++*pos;
+	return dev;
+}
+
 /*
  *	This is invoked by the /proc filesystem handler to display a device
  *	in detail.
@@ -4048,33 +4079,15 @@ static int dev_ifconf(struct net *net, char __user *arg)
 void *dev_seq_start(struct seq_file *seq, loff_t *pos)
 	__acquires(RCU)
 {
-	struct net *net = seq_file_net(seq);
-	loff_t off;
-	struct net_device *dev;
-
 	rcu_read_lock();
 	if (!*pos)
 		return SEQ_START_TOKEN;
-
-	off = 1;
-	for_each_netdev_rcu(net, dev)
-		if (off++ == *pos)
-			return dev;
-
-	return NULL;
+	return __dev_seq_next(seq, pos);
 }
 
 void *dev_seq_next(struct seq_file *seq, void *v, loff_t *pos)
 {
-	struct net_device *dev = v;
-
-	if (v == SEQ_START_TOKEN)
-		dev = first_net_device_rcu(seq_file_net(seq));
-	else
-		dev = next_net_device_rcu(dev);
-
-	++*pos;
-	return dev;
+	return __dev_seq_next(seq, pos);
 }
 
 void dev_seq_stop(struct seq_file *seq, void *v)
@@ -4173,7 +4186,7 @@ static const struct seq_operations dev_seq_ops = {
 static int dev_seq_open(struct inode *inode, struct file *file)
 {
 	return seq_open_net(inode, file, &dev_seq_ops,
-			    sizeof(struct seq_net_private));
+			    sizeof(struct dev_iter_state));
 }
 
 static const struct file_operations dev_seq_fops = {
-- 
1.7.4.1

Re: [PATCH] dev: use ifindex hash for dev_seq_ops

[Eric Dumazet]

Le vendredi 14 octobre 2011 à 12:53 +0300, Mihai Maruseac a écrit :
> Instead of using the dev->next chain and trying to resync at each call to
> dev_seq_start, use the ifindex, keeping the last index in seq->private field.
> 
> Tests revealed the following results for ifconfig > /dev/null
> 	* 1000 interfaces:
> 		* 0.114s without patch
> 		* 0.089s with patch
> 	* 3000 interfaces:
> 		* 0.489s without patch
> 		* 0.110s with patch
> 	* 5000 interfaces:
> 		* 1.363s without patch
> 		* 0.250s with patch
> 	* 128000 interfaces (other setup):
> 		* ~100s without patch
> 		* ~30s with patch
> 
> Signed-off-by: Mihai Maruseac <mmaruseac@ixiacom.com>
> ---
>  net/core/dev.c |   55 ++++++++++++++++++++++++++++++++++---------------------
>  1 files changed, 34 insertions(+), 21 deletions(-)
> 
> diff --git a/net/core/dev.c b/net/core/dev.c
> index 70ecb86..ea24445 100644
> --- a/net/core/dev.c
> +++ b/net/core/dev.c
> @@ -4041,6 +4041,37 @@ static int dev_ifconf(struct net *net, char __user *arg)
>  }
>  
>  #ifdef CONFIG_PROC_FS
> +
> +struct dev_iter_state {
> +	struct seq_net_private p;
> +	int ifindex;
> +};
> +
> +static struct net_device *__dev_seq_next(struct seq_file *seq, loff_t *pos)
> +{
> +	struct dev_iter_state *state = seq->private;
> +	struct net *net = seq_file_net(seq);
> +	struct net_device *dev;
> +	loff_t off;
> +
> +	dev = dev_get_by_index_rcu(net, state->ifindex);
> +	if (likely(dev))
> +		goto found;
> +
> +	off = 0;
> +	for_each_netdev_rcu(net, dev)
> +		if (off++ == *pos) {
> +			state->ifindex = dev->ifindex;
> +			goto found;
> +		}
> +
> +	return NULL;
> +found:
> +	state->ifindex++;

This assumes device ifindexes are contained in a small range 
[N .. N + X]

I understand this can help some benchmarks, but in real world this wont
help that much once ifindexes are 'fragmented' (If really this multi
thousand devices stuff is for real)

Listen, we currently have 256 slots in the hash table.

Can we try to make 'offset' something like  (slot_number<<24) +
(position in hash chain [slot_number]), instead of (position in devices
global list)

Re: [PATCH] dev: use ifindex hash for dev_seq_ops

[Daniel Baluta]

> This assumes device ifindexes are contained in a small range
> [N .. N + X]
>
> I understand this can help some benchmarks, but in real world this wont
> help that much once ifindexes are 'fragmented' (If really this multi
> thousand devices stuff is for real)
>
> Listen, we currently have 256 slots in the hash table.
>
> Can we try to make 'offset' something like  (slot_number<<24) +
> (position in hash chain [slot_number]), instead of (position in devices
> global list)


Eric, we can refine the idea of our first patch [1], where we recorded
the (bucket, offset) pair. Stephen, do you agree with this?


thanks,
Daniel.

[1] http://patchwork.ozlabs.org/patch/118331/

Re: [PATCH] dev: use ifindex hash for dev_seq_ops

[Stephen Hemminger]

On Mon, 17 Oct 2011 11:03:54 +0300
Daniel Baluta <dbaluta@ixiacom.com> wrote:

> > This assumes device ifindexes are contained in a small range
> > [N .. N + X]
> >
> > I understand this can help some benchmarks, but in real world this wont
> > help that much once ifindexes are 'fragmented' (If really this multi
> > thousand devices stuff is for real)
> >
> > Listen, we currently have 256 slots in the hash table.
> >
> > Can we try to make 'offset' something like  (slot_number<<24) +
> > (position in hash chain [slot_number]), instead of (position in devices
> > global list)
> 
> 
> Eric, we can refine the idea of our first patch [1], where we recorded
> the (bucket, offset) pair. Stephen, do you agree with this?
> 
> 
> thanks,
> Daniel.
> 
> [1] http://patchwork.ozlabs.org/patch/118331/

Using buckets is fine, my idea about ifindex was just to try and
preserve the order, but it doesn't matter.

[PATCH] dev: use name hash for dev_seq_ops

[Mihai Maruseac]

Instead of using the dev->next chain and trying to resync at each call to
dev_seq_start, use the name hash, keeping the bucket and the offset in
seq->private field.

The bucket number and the offset in the bucket are kept in a single unsigned
int value: pos = bucket << (32 - NETDEV_HASHBITS) + offset. When we reach the
end of the hash, both the bucket and the offset reach 0, so we need to test for
this in dev_seq_start to prevent endless loops.

Tests revealed the following results for ifconfig > /dev/null
	* 1000 interfaces:
		* 0.114s without patch
		* 0.089s with patch
	* 3000 interfaces:
		* 0.489s without patch
		* 0.110s with patch
	* 5000 interfaces:
		* 1.363s without patch
		* 0.250s with patch
	* 128000 interfaces (other setup):
		* ~100s without patch
		* ~30s with patch

Signed-off-by: Mihai Maruseac <mmaruseac@ixiacom.com>
---
 net/core/dev.c |   83 +++++++++++++++++++++++++++++++++++++++++++++----------
 1 files changed, 68 insertions(+), 15 deletions(-)

diff --git a/net/core/dev.c b/net/core/dev.c
index 70ecb86..103eb28 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -4041,6 +4041,59 @@ static int dev_ifconf(struct net *net, char __user *arg)
 }
 
 #ifdef CONFIG_PROC_FS
+
+struct dev_iter_state {
+	struct seq_net_private p;
+	unsigned int pos; /* bucket << 24 + offset */
+};
+
+#define BUCKET_SPACE (32 - NETDEV_HASHBITS)
+#define get_bucket(x) ((x) >> BUCKET_SPACE)
+#define get_offset(x) ((x) & ((1 << BUCKET_SPACE) - 1))
+#define set_bucket_offset(b, o) ((b) << BUCKET_SPACE | (o))
+
+static inline struct net_device *dev_from_same_bucket(struct seq_file *seq)
+{
+	struct dev_iter_state *state = seq->private;
+	struct net *net = seq_file_net(seq);
+	struct net_device *dev;
+	struct hlist_node *p;
+	struct hlist_head *h;
+	unsigned int count, bucket, offset;
+
+	bucket = get_bucket(state->pos);
+	offset = get_offset(state->pos);
+	h = &net->dev_name_head[bucket];
+	count = 0;
+	hlist_for_each_entry_rcu(dev, p, h, name_hlist) {
+		if (count++ == offset) {
+			state->pos = set_bucket_offset(bucket, count);
+			return dev;
+		}
+	}
+
+	return NULL;
+}
+
+static inline struct net_device *dev_from_new_bucket(struct seq_file *seq)
+{
+	struct dev_iter_state *state = seq->private;
+	struct net_device *dev;
+	unsigned int bucket;
+
+	bucket = get_bucket(state->pos);
+	do {
+		dev = dev_from_same_bucket(seq);
+		if (dev)
+			return dev;
+
+		bucket++;
+		state->pos = set_bucket_offset(bucket, 0);
+	} while (bucket < NETDEV_HASHENTRIES);
+
+	return NULL;
+}
+
 /*
  *	This is invoked by the /proc filesystem handler to display a device
  *	in detail.
@@ -4048,33 +4101,33 @@ static int dev_ifconf(struct net *net, char __user *arg)
 void *dev_seq_start(struct seq_file *seq, loff_t *pos)
 	__acquires(RCU)
 {
-	struct net *net = seq_file_net(seq);
-	loff_t off;
-	struct net_device *dev;
+	struct dev_iter_state *state = seq->private;
 
 	rcu_read_lock();
 	if (!*pos)
 		return SEQ_START_TOKEN;
 
-	off = 1;
-	for_each_netdev_rcu(net, dev)
-		if (off++ == *pos)
-			return dev;
+	/* check for end of the hash */
+	if (state->pos == 0 && *pos > 1)
+		return NULL;
 
-	return NULL;
+	return dev_from_new_bucket(seq);
 }
 
 void *dev_seq_next(struct seq_file *seq, void *v, loff_t *pos)
 {
-	struct net_device *dev = v;
+	struct net_device *dev;
+
+	++*pos;
 
 	if (v == SEQ_START_TOKEN)
-		dev = first_net_device_rcu(seq_file_net(seq));
-	else
-		dev = next_net_device_rcu(dev);
+		return dev_from_new_bucket(seq);
 
-	++*pos;
-	return dev;
+	dev = dev_from_same_bucket(seq);
+	if (dev)
+		return dev;
+
+	return dev_from_new_bucket(seq);
 }
 
 void dev_seq_stop(struct seq_file *seq, void *v)
@@ -4173,7 +4226,7 @@ static const struct seq_operations dev_seq_ops = {
 static int dev_seq_open(struct inode *inode, struct file *file)
 {
 	return seq_open_net(inode, file, &dev_seq_ops,
-			    sizeof(struct seq_net_private));
+			    sizeof(struct dev_iter_state));
 }
 
 static const struct file_operations dev_seq_fops = {
-- 
1.7.4.1

Re: [PATCH] dev: use name hash for dev_seq_ops

[David Miller]

From: Mihai Maruseac <mihai.maruseac@gmail.com>
Date: Thu, 20 Oct 2011 11:01:57 +0300

> Instead of using the dev->next chain and trying to resync at each call to
> dev_seq_start, use the name hash, keeping the bucket and the offset in
> seq->private field.

I'm totally fine with this patch from a technical perspective, but I'd
like one small thing tidied up before I apply this.

> +	unsigned int pos; /* bucket << 24 + offset */

Please don't mention this as a constant in the comment, if we ever
change NETDEV_HASHBITS this comment will be inaccurate.

I'd suggest putting the BUCKET_SPACE define before the dev_iter_state
definition, and using BUCKET_SPACE in the comment instead of 24.

Thanks.

[PATCH] dev: use name hash for dev_seq_ops

[Mihai Maruseac]

Instead of using the dev->next chain and trying to resync at each call to
dev_seq_start, use the name hash, keeping the bucket and the offset in
seq->private field.

Tests revealed the following results for ifconfig > /dev/null
	* 1000 interfaces:
		* 0.114s without patch
		* 0.089s with patch
	* 3000 interfaces:
		* 0.489s without patch
		* 0.110s with patch
	* 5000 interfaces:
		* 1.363s without patch
		* 0.250s with patch
	* 128000 interfaces (other setup):
		* ~100s without patch
		* ~30s with patch

Signed-off-by: Mihai Maruseac <mmaruseac@ixiacom.com>
---
 net/core/dev.c |   84 ++++++++++++++++++++++++++++++++++++++++++++++----------
 1 files changed, 69 insertions(+), 15 deletions(-)

diff --git a/net/core/dev.c b/net/core/dev.c
index 70ecb86..6edbcc5 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -4041,6 +4041,60 @@ static int dev_ifconf(struct net *net, char __user *arg)
 }
 
 #ifdef CONFIG_PROC_FS
+
+#define BUCKET_SPACE (32 - NETDEV_HASHBITS)
+
+struct dev_iter_state {
+	struct seq_net_private p;
+	unsigned int pos; /* bucket << BUCKET_SPACE + offset */
+};
+
+#define get_bucket(x) ((x) >> BUCKET_SPACE)
+#define get_offset(x) ((x) & ((1 << BUCKET_SPACE) - 1))
+#define set_bucket_offset(b, o) ((b) << BUCKET_SPACE | (o))
+
+static inline struct net_device *dev_from_same_bucket(struct seq_file *seq)
+{
+	struct dev_iter_state *state = seq->private;
+	struct net *net = seq_file_net(seq);
+	struct net_device *dev;
+	struct hlist_node *p;
+	struct hlist_head *h;
+	unsigned int count, bucket, offset;
+
+	bucket = get_bucket(state->pos);
+	offset = get_offset(state->pos);
+	h = &net->dev_name_head[bucket];
+	count = 0;
+	hlist_for_each_entry_rcu(dev, p, h, name_hlist) {
+		if (count++ == offset) {
+			state->pos = set_bucket_offset(bucket, count);
+			return dev;
+		}
+	}
+
+	return NULL;
+}
+
+static inline struct net_device *dev_from_new_bucket(struct seq_file *seq)
+{
+	struct dev_iter_state *state = seq->private;
+	struct net_device *dev;
+	unsigned int bucket;
+
+	bucket = get_bucket(state->pos);
+	do {
+		dev = dev_from_same_bucket(seq);
+		if (dev)
+			return dev;
+
+		bucket++;
+		state->pos = set_bucket_offset(bucket, 0);
+	} while (bucket < NETDEV_HASHENTRIES);
+
+	return NULL;
+}
+
 /*
  *	This is invoked by the /proc filesystem handler to display a device
  *	in detail.
@@ -4048,33 +4102,33 @@ static int dev_ifconf(struct net *net, char __user *arg)
 void *dev_seq_start(struct seq_file *seq, loff_t *pos)
 	__acquires(RCU)
 {
-	struct net *net = seq_file_net(seq);
-	loff_t off;
-	struct net_device *dev;
+	struct dev_iter_state *state = seq->private;
 
 	rcu_read_lock();
 	if (!*pos)
 		return SEQ_START_TOKEN;
 
-	off = 1;
-	for_each_netdev_rcu(net, dev)
-		if (off++ == *pos)
-			return dev;
+	/* check for end of the hash */
+	if (state->pos == 0 && *pos > 1)
+		return NULL;
 
-	return NULL;
+	return dev_from_new_bucket(seq);
 }
 
 void *dev_seq_next(struct seq_file *seq, void *v, loff_t *pos)
 {
-	struct net_device *dev = v;
+	struct net_device *dev;
+
+	++*pos;
 
 	if (v == SEQ_START_TOKEN)
-		dev = first_net_device_rcu(seq_file_net(seq));
-	else
-		dev = next_net_device_rcu(dev);
+		return dev_from_new_bucket(seq);
 
-	++*pos;
-	return dev;
+	dev = dev_from_same_bucket(seq);
+	if (dev)
+		return dev;
+
+	return dev_from_new_bucket(seq);
 }
 
 void dev_seq_stop(struct seq_file *seq, void *v)
@@ -4173,7 +4227,7 @@ static const struct seq_operations dev_seq_ops = {
 static int dev_seq_open(struct inode *inode, struct file *file)
 {
 	return seq_open_net(inode, file, &dev_seq_ops,
-			    sizeof(struct seq_net_private));
+			    sizeof(struct dev_iter_state));
 }
 
 static const struct file_operations dev_seq_fops = {
-- 
1.7.4.1

Re: [PATCH] dev: use name hash for dev_seq_ops

[Eric Dumazet]

Le vendredi 21 octobre 2011 à 09:45 +0300, Mihai Maruseac a écrit :
> Instead of using the dev->next chain and trying to resync at each call to
> dev_seq_start, use the name hash, keeping the bucket and the offset in
> seq->private field.
> 
...
> Signed-off-by: Mihai Maruseac <mmaruseac@ixiacom.com>

Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>

Thanks

Re: [PATCH] dev: use name hash for dev_seq_ops

[David Miller]

From: Mihai Maruseac <mihai.maruseac@gmail.com>
Date: Fri, 21 Oct 2011 09:45:10 +0300

> Instead of using the dev->next chain and trying to resync at each call to
> dev_seq_start, use the name hash, keeping the bucket and the offset in
> seq->private field.
> 
> Tests revealed the following results for ifconfig > /dev/null
 ...
> Signed-off-by: Mihai Maruseac <mmaruseac@ixiacom.com>

Applied.

Re: [PATCH] dev: use name hash for dev_seq_ops

[Stephen Hemminger]

On Fri, 21 Oct 2011 09:45:10 +0300
Mihai Maruseac <mihai.maruseac@gmail.com> wrote:

> Instead of using the dev->next chain and trying to resync at each call to
> dev_seq_start, use the name hash, keeping the bucket and the offset in
> seq->private field.
> 
> Tests revealed the following results for ifconfig > /dev/null
> 	* 1000 interfaces:
> 		* 0.114s without patch
> 		* 0.089s with patch
> 	* 3000 interfaces:
> 		* 0.489s without patch
> 		* 0.110s with patch
> 	* 5000 interfaces:
> 		* 1.363s without patch
> 		* 0.250s with patch
> 	* 128000 interfaces (other setup):
> 		* ~100s without patch
> 		* ~30s with patch
> 
> Signed-off-by: Mihai Maruseac <mmaruseac@ixiacom.com>
> ---
>  net/core/dev.c |   84 ++++++++++++++++++++++++++++++++++++++++++++++----------
>  1 files changed, 69 insertions(+), 15 deletions(-)
> 
> diff --git a/net/core/dev.c b/net/core/dev.c
> index 70ecb86..6edbcc5 100644
> --- a/net/core/dev.c
> +++ b/net/core/dev.c
> @@ -4041,6 +4041,60 @@ static int dev_ifconf(struct net *net, char __user *arg)
>  }
>  
>  #ifdef CONFIG_PROC_FS
> +
> +#define BUCKET_SPACE (32 - NETDEV_HASHBITS)
> +
> +struct dev_iter_state {
> +	struct seq_net_private p;
> +	unsigned int pos; /* bucket << BUCKET_SPACE + offset */
> +};
> +
> +#define get_bucket(x) ((x) >> BUCKET_SPACE)
> +#define get_offset(x) ((x) & ((1 << BUCKET_SPACE) - 1))
> +#define set_bucket_offset(b, o) ((b) << BUCKET_SPACE | (o))
> +
> +static inline struct net_device *dev_from_same_bucket(struct seq_file *seq)
>

Why are all these function marked inline? They are big, hardly hot path
and better to not continue the bad practice of inlining too much code.