[PATCH] dev: use name hash for dev_seq_ops.

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

On Fri,  7 Oct 2011 18:20:49 +0300
Mihai Maruseac [off-list ref] 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.

On Fri, Oct 7, 2011 at 7:24 PM, Stephen Hemminger [off-list ref] wrote:

On Fri,  7 Oct 2011 18:20:49 +0300
Mihai Maruseac [off-list ref] wrote:

quoted

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

On Fri, Oct 7, 2011 at 7:24 PM, Stephen Hemminger [off-list ref] wrote:

On Fri,  7 Oct 2011 18:20:49 +0300
Mihai Maruseac [off-list ref] wrote:

quoted

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

On Mon, 10 Oct 2011 11:43:20 +0300
Mihai Maruseac [off-list ref] wrote:

On Fri, Oct 7, 2011 at 7:24 PM, Stephen Hemminger [off-list ref] wrote:

quoted

On Fri,  7 Oct 2011 18:20:49 +0300
Mihai Maruseac [off-list ref] wrote:

quoted

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.

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

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

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

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

On Wed, 12 Oct 2011 12:57:26 +0300
Mihai Maruseac [off-list ref] 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.

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

On Wed, Oct 12, 2011 at 6:50 PM, Stephen Hemminger
[off-list ref] wrote:

On Wed, 12 Oct 2011 12:57:26 +0300
Mihai Maruseac [off-list ref] 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.

quoted

+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

Le vendredi 14 octobre 2011 à 12:53 +0300, Mihai Maruseac a écrit :

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)

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/

On Mon, 17 Oct 2011 11:03:54 +0300
Daniel Baluta [off-list ref] wrote:

quoted

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.