[PATCH] support for large number of network devices.

[PATCH] support for large number of network devices.

[Stephen Hemminger]

When using pseudo network devices, and really big machines; there is
sometimes a need to have a lot of network devices.  This replaces the
existing 2.6.1 limit of 100 entries an was O(n^2)
with a algorithm that will handle up to 32768 entries with O(n) behaviour.

Does need a temporary page, but that shouldn't be a big deal.
It has the same semantics, it will find the first empty name and use it.

diff -Nru a/net/core/dev.c b/net/core/dev.c
--- a/net/core/dev.c	Tue Jan 13 15:42:19 2004
+++ b/net/core/dev.c	Tue Jan 13 15:42:19 2004
@@ -650,8 +650,11 @@
 int dev_alloc_name(struct net_device *dev, const char *name)
 {
 	int i;
-	char buf[32];
 	char *p;
+	const int max_netdevices = 8*PAGE_SIZE;
+	long *inuse;
+	struct net_device *d;
+	char buf[IFNAMSIZ];
 
 	/*
 	 * Verify the string as this thing may have come from
@@ -662,17 +665,34 @@
 	if (p && (p[1] != 'd' || strchr(p + 2, '%')))
 		return -EINVAL;
 
-	/*
-	 * If you need over 100 please also fix the algorithm...
-	 */
-	for (i = 0; i < 100; i++) {
-		snprintf(buf, sizeof(buf), name, i);
-		if (!__dev_get_by_name(buf)) {
-			strcpy(dev->name, buf);
-			return i;
+	/* Use one page as a bit array of possible slots */
+	inuse = (long *) get_zeroed_page(GFP_ATOMIC);
+	if (!inuse) 
+		return -ENOMEM;
+
+	for (d = dev_base; d; d = d->next) {
+		if (sscanf(d->name, name, &i)) {
+			if (i < 0 || i >= max_netdevices)
+				continue;
+
+			set_bit(i, inuse);
 		}
 	}
-	return -ENFILE;	/* Over 100 of the things .. bail out! */
+
+	i = find_first_zero_bit(inuse, max_netdevices);
+	free_page((unsigned long) inuse);
+	snprintf(buf, sizeof(buf), name, i);
+
+	if (!__dev_get_by_name(buf)) {
+		strcpy(dev->name, buf);
+		return i;
+	}
+
+	/* It is possible to run out of possible slots
+	 * when the name is long and there isn't enough space left
+	 * for the digits, or if all bits are used.
+	 */
+	return -ENFILE;
 }
 
 

Re: [PATCH] support for large number of network devices.

[David S. Miller]

On Tue, 13 Jan 2004 15:46:10 -0800
Stephen Hemminger <shemminger@osdl.org> wrote:

> When using pseudo network devices, and really big machines; there is
> sometimes a need to have a lot of network devices.  This replaces the
> existing 2.6.1 limit of 100 entries an was O(n^2)
> with a algorithm that will handle up to 32768 entries with O(n) behaviour.
> 
> Does need a temporary page, but that shouldn't be a big deal.
> It has the same semantics, it will find the first empty name and use it.

I think your code has different semantics than exist currently.

For example, let's use the example of asking for "slip%d" then "eth%d".
The existing code would hand out "slip0" then "eth0", but your code would
deliver "slip0" then "eth1" which is not correct.

Or did I miss something clever in your algorithm?

Re: [PATCH] support for large number of network devices.

[Stephen Hemminger]

On Tue, 13 Jan 2004 15:59:21 -0800
"David S. Miller" <davem@redhat.com> wrote:

> On Tue, 13 Jan 2004 15:46:10 -0800
> Stephen Hemminger <shemminger@osdl.org> wrote:
> 
> > When using pseudo network devices, and really big machines; there is
> > sometimes a need to have a lot of network devices.  This replaces the
> > existing 2.6.1 limit of 100 entries an was O(n^2)
> > with a algorithm that will handle up to 32768 entries with O(n) behaviour.
> > 
> > Does need a temporary page, but that shouldn't be a big deal.
> > It has the same semantics, it will find the first empty name and use it.
> 
> I think your code has different semantics than exist currently.
> 
> For example, let's use the example of asking for "slip%d" then "eth%d".
> The existing code would hand out "slip0" then "eth0", but your code would
> deliver "slip0" then "eth1" which is not correct.
> 
> Or did I miss something clever in your algorithm?

	It uses the output format string for the sscanf match, and since
	sscanf formats have to match. 	sscanf("eth0", "slip%d", &i) returns 0
	so eth0 would be skipped

Re: [PATCH] support for large number of network devices.

[Ben Greear]

Stephen Hemminger wrote:
> When using pseudo network devices, and really big machines; there is
> sometimes a need to have a lot of network devices.  This replaces the
> existing 2.6.1 limit of 100 entries an was O(n^2)
> with a algorithm that will handle up to 32768 entries with O(n) behaviour.

Might be a good time to put in hash tables to find network devices by
name and by device-id.  There are a few parts of the networking stack
that do lookups, and walking the device list when it's 4k entries
long takes a while...

Ben

-- 
Ben Greear <greearb@candelatech.com>
Candela Technologies Inc  http://www.candelatech.com

Re: [PATCH] support for large number of network devices.

[Stephen Hemminger]

On Tue, 13 Jan 2004 16:23:25 -0800
Ben Greear <greearb@candelatech.com> wrote:

> Stephen Hemminger wrote:
> > When using pseudo network devices, and really big machines; there is
> > sometimes a need to have a lot of network devices.  This replaces the
> > existing 2.6.1 limit of 100 entries an was O(n^2)
> > with a algorithm that will handle up to 32768 entries with O(n) behaviour.
> 
> Might be a good time to put in hash tables to find network devices by
> name and by device-id.  There are a few parts of the networking stack
> that do lookups, and walking the device list when it's 4k entries
> long takes a while...

I have a patch for name hashing, but don't know if it's needed.
Even without it I can add 9 thousand bridge entries,
and each one takes longer to start the command than add the entry now. 

Re: [PATCH] support for large number of network devices.

[Ben Greear]

Stephen Hemminger wrote:
> On Tue, 13 Jan 2004 16:23:25 -0800
> Ben Greear <greearb@candelatech.com> wrote:
> 
> 
>>Stephen Hemminger wrote:
>>
>>>When using pseudo network devices, and really big machines; there is
>>>sometimes a need to have a lot of network devices.  This replaces the
>>>existing 2.6.1 limit of 100 entries an was O(n^2)
>>>with a algorithm that will handle up to 32768 entries with O(n) behaviour.
>>
>>Might be a good time to put in hash tables to find network devices by
>>name and by device-id.  There are a few parts of the networking stack
>>that do lookups, and walking the device list when it's 4k entries
>>long takes a while...
> 
> 
> I have a patch for name hashing, but don't know if it's needed.
> Even without it I can add 9 thousand bridge entries,
> and each one takes longer to start the command than add the entry now. 

Check out the af_packet code.  At least some branches do a
device lookup by name for each transmitted packet.  One
method is:  packet_sendmsg_spkt

packet_sendmsg gets by index, which could also be hashed...

At one time ifconfig -a was almost un-usable with large numbers
of devices, but I think it has been improved.  I haven't tried on
large numbers of devices lately...

-- 
Ben Greear <greearb@candelatech.com>
Candela Technologies Inc  http://www.candelatech.com

Re: [PATCH] support for large number of network devices.

[Matt Mackall]

On Tue, Jan 13, 2004 at 04:13:03PM -0800, Stephen Hemminger wrote:
> On Tue, 13 Jan 2004 15:59:21 -0800
> "David S. Miller" <davem@redhat.com> wrote:
> 
> > On Tue, 13 Jan 2004 15:46:10 -0800
> > Stephen Hemminger <shemminger@osdl.org> wrote:
> > 
> > > When using pseudo network devices, and really big machines; there is
> > > sometimes a need to have a lot of network devices.  This replaces the
> > > existing 2.6.1 limit of 100 entries an was O(n^2)
> > > with a algorithm that will handle up to 32768 entries with O(n) behaviour.
> > > 
> > > Does need a temporary page, but that shouldn't be a big deal.
> > > It has the same semantics, it will find the first empty name and use it.
> > 
> > I think your code has different semantics than exist currently.
> > 
> > For example, let's use the example of asking for "slip%d" then "eth%d".
> > The existing code would hand out "slip0" then "eth0", but your code would
> > deliver "slip0" then "eth1" which is not correct.
> > 
> > Or did I miss something clever in your algorithm?
> 
> 	It uses the output format string for the sscanf match, and since
> 	sscanf formats have to match. 	sscanf("eth0", "slip%d", &i) returns 0
> 	so eth0 would be skipped

Unfortunately sscanf("eth0-not-allocated", "eth%d", &i) fools it.
Which may or may not be worth worrying about.

-- 
 Matt Mackall : http://www.selenic.com : Linux development and consulting

Re: [PATCH] support for large number of network devices.

[David S. Miller]

On Tue, 13 Jan 2004 17:55:32 -0800
Ben Greear <greearb@candelatech.com> wrote:

> Stephen Hemminger wrote:
> > I have a patch for name hashing, but don't know if it's needed.
> > Even without it I can add 9 thousand bridge entries,
> > and each one takes longer to start the command than add the entry now. 
> 
> Check out the af_packet code.  At least some branches do a
> device lookup by name for each transmitted packet.  One
> method is:  packet_sendmsg_spkt
> 
> packet_sendmsg gets by index, which could also be hashed...
> 
> At one time ifconfig -a was almost un-usable with large numbers
> of devices, but I think it has been improved.  I haven't tried on
> large numbers of devices lately...

I found some other fast-path'ish cases of dev_get_by_name(), one of which
is atalk_rcv()'s handling of IP over DDP packets.

I didn't even search around for __dev_get() and dev_get_by_index() cases.
There are probably some more there.

Therefore, I think it's wise to just do this right from the start and use a hash.
Stephen can you test up and submit the netdev name hash patch you have?

Re: [PATCH] support for large number of network devices.

[Ben Greear]

David S. Miller wrote:

> Therefore, I think it's wise to just do this right from the start and use a hash.
> Stephen can you test up and submit the netdev name hash patch you have?
> 

In case it proves useful, here's the hash I used before.  It makes some
assumptions based on the fact that the last two characters of a device name
are often numbers, especially when you have lots of devices.  Someone
did a mapping of this and found it worked well for vlans, at least.


int fdl_calc_name_idx(const char* dev_name) {
  int tmp = 0;
  int i;

  for (i = 0; dev_name[i]; i++) {
    tmp += (int)(dev_name[i]);
  }
  if (i > 3) {
    tmp += (dev_name[i-2] * 10); /* might add a little spread to the hash */
    tmp += (dev_name[i-3] * 100); /* might add a little spread to the hash */
  }
  return (tmp % FDL_HASH_LEN);
}


-- 
Ben Greear <greearb@candelatech.com>
Candela Technologies Inc  http://www.candelatech.com

Re: [PATCH] support for large number of network devices.

[Stephen Hemminger]

> Unfortunately sscanf("eth0-not-allocated", "eth%d", &i) fools it.
> Which may or may not be worth worrying about.

Hmmm,  the old code would have assigned "eth0" in that case, new code
would assign "eth1".  Other difference is in the case of whitespace.
scanf("white  space0", "white space%d", &i)
because any whitespace matches multiple whitespace characters.

Is it worth making a separate explicit match routine?

Re: [PATCH] support for large number of network devices.

[Matt Mackall]

On Wed, Jan 14, 2004 at 11:37:34AM -0800, Stephen Hemminger wrote:
> 
> > Unfortunately sscanf("eth0-not-allocated", "eth%d", &i) fools it.
> > Which may or may not be worth worrying about.
> 
> Hmmm,  the old code would have assigned "eth0" in that case, new code
> would assign "eth1".  Other difference is in the case of whitespace.
> scanf("white  space0", "white space%d", &i)
> because any whitespace matches multiple whitespace characters.
> 
> Is it worth making a separate explicit match routine?

I think it's probably easier to just add O(1) lookup and then do
explicit lookups on eth0..ethx. As Dave's pointed out, fast lookups
are wanted elsewhere. I made a quick hack to make the sscanf trick
work (try scanning for "eth%d%c" and insisting that %c not get parsed)
but it was not pretty.

-- 
Matt Mackall : http://www.selenic.com : Linux development and consulting

Re: [PATCH] support for large number of network devices.

[David S. Miller]

On Wed, 14 Jan 2004 11:37:34 -0800
Stephen Hemminger <shemminger@osdl.org> wrote:

> > Unfortunately sscanf("eth0-not-allocated", "eth%d", &i) fools it.
> > Which may or may not be worth worrying about.
> 
> Hmmm,  the old code would have assigned "eth0" in that case, new code
> would assign "eth1".  Other difference is in the case of whitespace.
> scanf("white  space0", "white space%d", &i)
> because any whitespace matches multiple whitespace characters.
> 
> Is it worth making a separate explicit match routine?

My only concern right now is that, since we're in the middle of 2.6.x, we not
break semantics of such a core routine like this one.

Although I'm willing to accept that certain cases are just rediculious and not worth
worrying about, just try your best to create a version of the patch
that matches current behavior as best as possible and we'll work from
that.

Re: [PATCH] support for large number of network devices.

[Stephen Hemminger]

This should make it match the existing semantics more exactly.
It will skip the false positive matchs from sscanf trailing chars
or blanks.

diff -Nru a/net/core/dev.c b/net/core/dev.c
--- a/net/core/dev.c	Wed Jan 14 16:24:08 2004
+++ b/net/core/dev.c	Wed Jan 14 16:24:08 2004
@@ -654,7 +654,7 @@
 	const int max_netdevices = 8*PAGE_SIZE;
 	long *inuse;
 	struct net_device *d;
-	char buf[IFNAMSIZ];
+	char buf[32];
 
 	/*
 	 * Verify the string as this thing may have come from
@@ -671,12 +671,14 @@
 		return -ENOMEM;
 
 	for (d = dev_base; d; d = d->next) {
-		if (sscanf(d->name, name, &i)) {
-			if (i < 0 || i >= max_netdevices)
-				continue;
+		if (!sscanf(d->name, name, &i))
+			continue;
+		if (i < 0 || i >= max_netdevices)
+			continue;
 
+		snprintf(buf, sizeof(buf), name, i);
+		if (!strncmp(buf, d->name, IFNAMSIZ))
 			set_bit(i, inuse);
-		}
 	}
 
 	i = find_first_zero_bit(inuse, max_netdevices);
@@ -684,7 +686,7 @@
 	snprintf(buf, sizeof(buf), name, i);
 
 	if (!__dev_get_by_name(buf)) {
-		strcpy(dev->name, buf);
+		strlcpy(dev->name, buf, IFNAMSIZ);
 		return i;
 	}
 

Re: [PATCH] support for large number of network devices.

[David S. Miller]

On Wed, 14 Jan 2004 16:24:11 -0800
Stephen Hemminger <shemminger@osdl.org> wrote:

> This should make it match the existing semantics more exactly.
> It will skip the false positive matchs from sscanf trailing chars
> or blanks.

Ok, but... I thought we had decided to move towards the hashing based
patch you said you had so we can kill two birds with one stone?

At least, that is the conclusion I thought we had arrived at.
:-)

Re: [PATCH] support for large number of network devices.

[Stephen Hemminger]

On Thu, 15 Jan 2004 00:46:31 -0800
"David S. Miller" <davem@redhat.com> wrote:

> On Wed, 14 Jan 2004 16:24:11 -0800
> Stephen Hemminger <shemminger@osdl.org> wrote:
> 
> > This should make it match the existing semantics more exactly.
> > It will skip the false positive matchs from sscanf trailing chars
> > or blanks.
> 
> Ok, but... I thought we had decided to move towards the hashing based
> patch you said you had so we can kill two birds with one stone?
> 
> At least, that is the conclusion I thought we had arrived at.
> :-)

The right way is a combination of the two pass dev_alloc_name and hashing
the names.  Both work together

Re: [PATCH] support for large number of network devices.

[David S. Miller]

On Thu, 15 Jan 2004 09:52:52 -0800
Stephen Hemminger <shemminger@osdl.org> wrote:

> On Thu, 15 Jan 2004 00:46:31 -0800
> "David S. Miller" <davem@redhat.com> wrote:
> 
> > Ok, but... I thought we had decided to move towards the hashing based
> > patch you said you had so we can kill two birds with one stone?
> > 
> > At least, that is the conclusion I thought we had arrived at.
> > :-)
> 
> The right way is a combination of the two pass dev_alloc_name and hashing
> the names.  Both work together

Ok, please resend the final version of your dev_alloc_name() bitmap patch
under seperate cover so I can apply it, thanks.

Re: [PATCH] support for large number of network devices.

[Jean Tourrilhes]

Stephen Hemminger wrote :
> 
> When using pseudo network devices, and really big machines; there is
> sometimes a need to have a lot of network devices.  This replaces the
> existing 2.6.1 limit of 100 entries an was O(n^2)
> with a algorithm that will handle up to 32768 entries with O(n) behaviour.

	You may want to be careful about buffer overflow in
dev->name. The old code did not check for it, because it was replacing
'%d' with a most 2 char ('0' to '99').
	The new code may create overflow for device names such as :
		'reallylongname%d'
	And you don't seem the catch that (unless I overlooked something).

	The problem is more messy that it looks like, because there is
no sane way to handle overflow. You can return an error to the driver,
and the driver may bail out properly (or crash), but the end user has
no way to overcome the issue and get its card loaded (short of editing
the driver and recompiling the kernel).
	So, there is a bit of auding to do first. I know for example
the HostAP create such long names.
	But that's only my humble opinion ;-)

	Jean