[PATCH] (4/4) support large number of network devices -- alloc_name bitmap

[Stephen Hemminger <shemminger@osdl.org>]

Convert dev_alloc_name from O(n^2) algorithm with a limit
of 100 of same prefix; to a two pass O(n) algorithim with a limit of 
32k devices with the same prefix.

This version finds the first free slot, and handles overflow correctly
for long names.

diff -Nru a/net/core/dev.c b/net/core/dev.c
--- a/net/core/dev.c	Fri Jan 16 15:45:04 2004
+++ b/net/core/dev.c	Fri Jan 16 15:45:04 2004
@@ -698,8 +698,11 @@
 int dev_alloc_name(struct net_device *dev, const char *name)
 {
 	int i;
-	char buf[32];
-	char *p;
+	char buf[IFNAMSIZ];
+	const char *p;
+	const int max_netdevices = 8*PAGE_SIZE;
+	long *inuse;
+	struct net_device *d;
 
 	/*
 	 * Verify the string as this thing may have come from
@@ -707,20 +710,41 @@
 	 * characters, or no "%" characters at all.
 	 */
 	p = strchr(name, '%');
-	if (p && (p[1] != 'd' || strchr(p + 2, '%')))
+	if (p && ((p[1] != 'd' || strchr(p + 2, '%'))
+		  || (p - name) > IFNAMSIZ-2))
 		return -EINVAL;
 
-	/*
-	 * If you need over 100 please also fix the algorithm...
-	 */
-	for (i = 0; i < 100; 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))
+			continue;
+		if (i < 0 || i >= max_netdevices)
+			continue;
+
+		/*  avoid cases where sscanf is not exact inverse of printf */
 		snprintf(buf, sizeof(buf), name, i);
-		if (!__dev_get_by_name(buf)) {
-			strcpy(dev->name, buf);
-			return i;
-		}
+		if (!strncmp(buf, d->name, IFNAMSIZ))
+			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)) {
+		strlcpy(dev->name, buf, IFNAMSIZ);
+		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;
 }