[PATCH] dev-alloc-name-by-check-name-existence.patch

[PATCH] dev-alloc-name-by-check-name-existence.patch

[Cheng Renquan]

Nowadays the net_device names have been mounted on a hash table,
check name existence should be much faster than ever before, hence
the extra page of memory for bitmap scanning is no longer needed.

Signed-off-by: Cheng Renquan <crquan@gmail.com>

---
 net/core/dev.c |   33 ++++++---------------------------
 1 file changed, 6 insertions(+), 27 deletions(-)

Index: linux-3.14.3/net/core/dev.c
===================================================================
--- linux-3.14.3.orig/net/core/dev.c	2014-05-06 07:59:58.000000000 -0700
+++ linux-3.14.3/net/core/dev.c	2014-05-24 13:56:02.592865482 -0700
@@ -960,54 +960,33 @@
  *	Returns the number of the unit assigned or a negative errno code.
  */
 
 static int __dev_alloc_name(struct net *net, const char *name, char *buf)
 {
 	int i = 0;
 	const char *p;
-	const int max_netdevices = 8*PAGE_SIZE;
-	unsigned long *inuse;
-	struct net_device *d;
 
 	p = strnchr(name, IFNAMSIZ-1, '%');
 	if (p) {
 		/*
 		 * Verify the string as this thing may have come from
 		 * the user.  There must be either one "%d" and no other "%"
 		 * characters.
 		 */
 		if (p[1] != 'd' || strchr(p + 2, '%'))
 			return -EINVAL;
 
-		/* Use one page as a bit array of possible slots */
-		inuse = (unsigned long *) get_zeroed_page(GFP_ATOMIC);
-		if (!inuse)
-			return -ENOMEM;
-
-		for_each_netdev(net, d) {
-			if (!sscanf(d->name, name, &i))
-				continue;
-			if (i < 0 || i >= max_netdevices)
-				continue;
-
-			/*  avoid cases where sscanf is not exact inverse of printf */
-			snprintf(buf, IFNAMSIZ, name, i);
-			if (!strncmp(buf, d->name, IFNAMSIZ))
-				set_bit(i, inuse);
-		}
-
-		i = find_first_zero_bit(inuse, max_netdevices);
-		free_page((unsigned long) inuse);
+		do {
+			if (snprintf(buf, IFNAMSIZ, name, i) >= IFNAMSIZ)
+				break;
+			if (!__dev_get_by_name(net, buf))
+				return i;
+		} while (++i > 0);
 	}
 
-	if (buf != name)
-		snprintf(buf, IFNAMSIZ, name, i);
-	if (!__dev_get_by_name(net, 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] dev-alloc-name-by-check-name-existence.patch

[David Miller]

From: Cheng Renquan <crquan@gmail.com>
Date: Sat, 24 May 2014 14:46:51 -0700

> Nowadays the net_device names have been mounted on a hash table,
> check name existence should be much faster than ever before, hence
> the extra page of memory for bitmap scanning is no longer needed.
> 
> Signed-off-by: Cheng Renquan <crquan@gmail.com>

The cost is iterating creating the string over and over again
and then doing the hash lookup each time.

Whereas the bitmap lookup is one word sized load for every
BITS_PER_LONG indexes checked.

Did you even test your change with large numbers of devices?

Re: [PATCH] dev-alloc-name-by-check-name-existence.patch

[crquan]

On Sat, May 24, 2014 at 2:57 PM, David Miller <davem@davemloft.net> wrote:
> The cost is iterating creating the string over and over again
> and then doing the hash lookup each time.

The original code calls sscanf / snprintf / strncmp for each existing intf,
new code is not creating the string, it calls snprintf only, and it won't call
more than original times of snprintf, right? I think here it depends on
hash lookup performance,

>
> Whereas the bitmap lookup is one word sized load for every
> BITS_PER_LONG indexes checked.
>
> Did you even test your change with large numbers of devices?

the worst case might be "eth0", "eth1", ... "eth4096", ... all exists, and
try to allocate next "eth%d", then it equals to N times hash lookup,
in general case, if allocating for a different prefix "veth%d" or not
all sequential
existing, it returns faster

The benefit is not requiring extra page of memory

Re: [PATCH] dev-alloc-name-by-check-name-existence.patch

[David Miller]

From: crquan <crquan@gmail.com>
Date: Sat, 24 May 2014 19:58:12 -0700

> On Sat, May 24, 2014 at 2:57 PM, David Miller <davem@davemloft.net> wrote:
>> The cost is iterating creating the string over and over again
>> and then doing the hash lookup each time.
> 
> The original code calls sscanf / snprintf / strncmp for each existing intf,
> new code is not creating the string, it calls snprintf only, and it won't call
> more than original times of snprintf, right? I think here it depends on
> hash lookup performance,

The bitmap scan is one call, and fast forwards the search to the first open
index.

So it's a bitmap scan plus _ONE_ string creation and hash lookup in the most
common case, even with thousands upon thousands of devices.

I'm not applying your patch, it's a regression.

If you disagree with me, show performance numbers supporting your argument.