All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH] (1/4) support large number of network devices
@ 2004-01-16 23:46 Stephen Hemminger
  2004-01-16 23:48 ` [PATCH] (2/4) support large number of network devices -- name hash Stephen Hemminger
                   ` (3 more replies)
  0 siblings, 4 replies; 8+ messages in thread
From: Stephen Hemminger @ 2004-01-16 23:46 UTC (permalink / raw)
  To: David S. Miller; +Cc: netdev

In preparation for the other changes to allow large number
of network devices, move the device table head and lock from
over in the network drivers setup code into the core netdev code.


diff -Nru a/drivers/net/Space.c b/drivers/net/Space.c
--- a/drivers/net/Space.c	Thu Jan 15 16:12:02 2004
+++ b/drivers/net/Space.c	Thu Jan 15 16:12:02 2004
@@ -455,28 +455,3 @@
 }
 
 device_initcall(net_olddevs_init);
-
-/*
- * The @dev_base list is protected by @dev_base_lock and the rtln
- * semaphore.
- *
- * Pure readers hold dev_base_lock for reading.
- *
- * Writers must hold the rtnl semaphore while they loop through the
- * dev_base list, and hold dev_base_lock for writing when they do the
- * actual updates.  This allows pure readers to access the list even
- * while a writer is preparing to update it.
- *
- * To put it another way, dev_base_lock is held for writing only to
- * protect against pure readers; the rtnl semaphore provides the
- * protection against other writers.
- *
- * See, for example usages, register_netdevice() and
- * unregister_netdevice(), which must be called with the rtnl
- * semaphore held.
- */
-struct net_device *dev_base;
-rwlock_t dev_base_lock = RW_LOCK_UNLOCKED;
-
-EXPORT_SYMBOL(dev_base);
-EXPORT_SYMBOL(dev_base_lock);
diff -Nru a/net/core/dev.c b/net/core/dev.c
--- a/net/core/dev.c	Thu Jan 15 16:12:02 2004
+++ b/net/core/dev.c	Thu Jan 15 16:12:02 2004
@@ -161,6 +161,31 @@
 #endif
 
 /*
+ * The @dev_base list is protected by @dev_base_lock and the rtln
+ * semaphore.
+ *
+ * Pure readers hold dev_base_lock for reading.
+ *
+ * Writers must hold the rtnl semaphore while they loop through the
+ * dev_base list, and hold dev_base_lock for writing when they do the
+ * actual updates.  This allows pure readers to access the list even
+ * while a writer is preparing to update it.
+ *
+ * To put it another way, dev_base_lock is held for writing only to
+ * protect against pure readers; the rtnl semaphore provides the
+ * protection against other writers.
+ *
+ * See, for example usages, register_netdevice() and
+ * unregister_netdevice(), which must be called with the rtnl
+ * semaphore held.
+ */
+struct net_device *dev_base;
+rwlock_t dev_base_lock = RW_LOCK_UNLOCKED;
+
+EXPORT_SYMBOL(dev_base);
+EXPORT_SYMBOL(dev_base_lock);
+
+/*
  *	Our notifier list
  */
 

^ permalink raw reply	[flat|nested] 8+ messages in thread

* [PATCH] (2/4) support large number of network devices -- name hash
  2004-01-16 23:46 [PATCH] (1/4) support large number of network devices Stephen Hemminger
@ 2004-01-16 23:48 ` Stephen Hemminger
  2004-01-17  2:22   ` YOSHIFUJI Hideaki / 吉藤英明
  2004-01-16 23:49 ` [PATCH] (3/4) support large number of network devices -- hash ifindex Stephen Hemminger
                   ` (2 subsequent siblings)
  3 siblings, 1 reply; 8+ messages in thread
From: Stephen Hemminger @ 2004-01-16 23:48 UTC (permalink / raw)
  To: David S. Miller; +Cc: netdev

Add a hash list to speed lookup's of network device name
used in dev_alloc_name and by other protocols.
Keep a tail pointer as well to allow quick append to the end
of the device singly linked device list.

Note: Uses 8bits for hash and the filename hash function

diff -Nru a/include/linux/netdevice.h b/include/linux/netdevice.h
--- a/include/linux/netdevice.h	Fri Jan 16 14:20:47 2004
+++ b/include/linux/netdevice.h	Fri Jan 16 14:20:47 2004
@@ -375,6 +375,8 @@
 	atomic_t		refcnt;
 	/* delayed register/unregister */
 	struct list_head	todo_list;
+	/* device name hash chain */
+	struct hlist_node	name_hlist;
 
 	/* register/unregister state machine */
 	enum { NETREG_UNINITIALIZED=0,
diff -Nru a/net/core/dev.c b/net/core/dev.c
--- a/net/core/dev.c	Fri Jan 16 14:20:47 2004
+++ b/net/core/dev.c	Fri Jan 16 14:20:47 2004
@@ -180,11 +180,22 @@
  * semaphore held.
  */
 struct net_device *dev_base;
+struct net_device **dev_tail = &dev_base;
 rwlock_t dev_base_lock = RW_LOCK_UNLOCKED;
 
 EXPORT_SYMBOL(dev_base);
 EXPORT_SYMBOL(dev_base_lock);
 
+#define NETDEV_HASHBITS	8
+static struct hlist_head dev_name_head[1<<NETDEV_HASHBITS];
+
+static inline struct hlist_head *dev_name_hash(const char *name)
+{
+	size_t len = min(strlen(name),(size_t)(IFNAMSIZ-1));
+	unsigned hash = full_name_hash(name, len);
+	return &dev_name_head[hash & ((1<<NETDEV_HASHBITS)-1)];
+}
+
 /*
  *	Our notifier list
  */
@@ -444,12 +455,15 @@
 
 struct net_device *__dev_get_by_name(const char *name)
 {
-	struct net_device *dev;
+	struct hlist_node *p;
 
-	for (dev = dev_base; dev; dev = dev->next)
+	hlist_for_each(p, dev_name_hash(name)) {
+		struct net_device *dev
+			= hlist_entry(p, struct net_device, name_hlist);
 		if (!strncmp(dev->name, name, IFNAMSIZ))
-			break;
-	return dev;
+			return dev;
+	}
+	return NULL;
 }
 
 /**
@@ -730,6 +744,9 @@
 	else
 		strlcpy(dev->name, newname, IFNAMSIZ);
 
+	hlist_del(&dev->name_hlist);
+	hlist_add_head(&dev->name_hlist, dev_name_hash(dev->name));
+
 	class_device_rename(&dev->class_dev, dev->name);
 	notifier_call_chain(&netdev_chain, NETDEV_CHANGENAME, dev);
 	return 0;
@@ -2718,7 +2735,8 @@
 
 int register_netdevice(struct net_device *dev)
 {
-	struct net_device *d, **dp;
+	struct hlist_head *head;
+	struct hlist_node *p;
 	int ret;
 
 	BUG_ON(dev_boot_phase);
@@ -2759,13 +2777,17 @@
 	if (dev->iflink == -1)
 		dev->iflink = dev->ifindex;
 
-	/* Check for existence, and append to tail of chain */
-	ret = -EEXIST;
-	for (dp = &dev_base; (d = *dp) != NULL; dp = &d->next) {
-		if (d == dev || !strcmp(d->name, dev->name))
-			goto out_err;
-	}
-	
+	/* Check for existence of name */
+	head = dev_name_hash(dev->name);
+	hlist_for_each(p, head) {
+		struct net_device *d
+			= hlist_entry(p, struct net_device, name_hlist);
+		if (!strncmp(d->name, dev->name, IFNAMSIZ)) {
+			ret = -EEXIST;
+ 			goto out_err;
+		}
+ 	}
+
 	/* Fix illegal SG+CSUM combinations. */
 	if ((dev->features & NETIF_F_SG) &&
 	    !(dev->features & (NETIF_F_IP_CSUM |
@@ -2794,7 +2816,9 @@
 	dev->next = NULL;
 	dev_init_scheduler(dev);
 	write_lock_bh(&dev_base_lock);
-	*dp = dev;
+	*dev_tail = dev;
+	dev_tail = &dev->next;
+	hlist_add_head(&dev->name_hlist, head);
 	dev_hold(dev);
 	dev->reg_state = NETREG_REGISTERING;
 	write_unlock_bh(&dev_base_lock);
@@ -3016,6 +3040,9 @@
 	for (dp = &dev_base; (d = *dp) != NULL; dp = &d->next) {
 		if (d == dev) {
 			write_lock_bh(&dev_base_lock);
+			hlist_del(&dev->name_hlist);
+			if (dev_tail == &dev->next)
+				dev_tail = dp;
 			*dp = d->next;
 			write_unlock_bh(&dev_base_lock);
 			break;
@@ -3091,6 +3118,9 @@
 	INIT_LIST_HEAD(&ptype_all);
 	for (i = 0; i < 16; i++) 
 		INIT_LIST_HEAD(&ptype_base[i]);
+
+	for (i = 0; i < ARRAY_SIZE(dev_name_head); i++)
+		INIT_HLIST_HEAD(&dev_name_head[i]);
 
 	/*
 	 *	Initialise the packet receive queues.

^ permalink raw reply	[flat|nested] 8+ messages in thread

* [PATCH] (3/4) support large number of network devices -- hash ifindex
  2004-01-16 23:46 [PATCH] (1/4) support large number of network devices Stephen Hemminger
  2004-01-16 23:48 ` [PATCH] (2/4) support large number of network devices -- name hash Stephen Hemminger
@ 2004-01-16 23:49 ` Stephen Hemminger
  2004-01-16 23:50 ` [PATCH] (4/4) support large number of network devices -- alloc_name bitmap Stephen Hemminger
  2004-01-20  5:24 ` [PATCH] (1/4) support large number of network devices David S. Miller
  3 siblings, 0 replies; 8+ messages in thread
From: Stephen Hemminger @ 2004-01-16 23:49 UTC (permalink / raw)
  To: David S. Miller; +Cc: netdev

Add an additional hash chain to keep track of network devices
by index.  This gets used during route manipulation and when
allocating a unique ifindex.

diff -Nru a/include/linux/netdevice.h b/include/linux/netdevice.h
--- a/include/linux/netdevice.h	Fri Jan 16 09:27:12 2004
+++ b/include/linux/netdevice.h	Fri Jan 16 09:27:12 2004
@@ -377,6 +377,8 @@
 	struct list_head	todo_list;
 	/* device name hash chain */
 	struct hlist_node	name_hlist;
+	/* device index hash chain */
+	struct hlist_node	index_hlist;
 
 	/* register/unregister state machine */
 	enum { NETREG_UNINITIALIZED=0,
diff -Nru a/net/core/dev.c b/net/core/dev.c
--- a/net/core/dev.c	Fri Jan 16 09:27:12 2004
+++ b/net/core/dev.c	Fri Jan 16 09:27:12 2004
@@ -188,6 +188,7 @@
 
 #define NETDEV_HASHBITS	8
 static struct hlist_head dev_name_head[1<<NETDEV_HASHBITS];
+static struct hlist_head dev_index_head[1<<NETDEV_HASHBITS];
 
 static inline struct hlist_head *dev_name_hash(const char *name)
 {
@@ -196,6 +197,11 @@
 	return &dev_name_head[hash & ((1<<NETDEV_HASHBITS)-1)];
 }
 
+static inline struct hlist_head *dev_index_hash(int ifindex)
+{
+	return &dev_index_head[ifindex & ((1<<NETDEV_HASHBITS)-1)];
+}
+
 /*
  *	Our notifier list
  */
@@ -531,12 +537,15 @@
 
 struct net_device *__dev_get_by_index(int ifindex)
 {
-	struct net_device *dev;
+	struct hlist_node *p;
 
-	for (dev = dev_base; dev; dev = dev->next)
+	hlist_for_each(p, dev_index_hash(ifindex)) {
+		struct net_device *dev
+			= hlist_entry(p, struct net_device, index_hlist);
 		if (dev->ifindex == ifindex)
-			break;
-	return dev;
+			return dev;
+	}
+	return NULL;
 }
 
 
@@ -2819,6 +2828,7 @@
 	*dev_tail = dev;
 	dev_tail = &dev->next;
 	hlist_add_head(&dev->name_hlist, head);
+	hlist_add_head(&dev->index_hlist, dev_index_hash(dev->ifindex));
 	dev_hold(dev);
 	dev->reg_state = NETREG_REGISTERING;
 	write_unlock_bh(&dev_base_lock);
@@ -3041,6 +3051,7 @@
 		if (d == dev) {
 			write_lock_bh(&dev_base_lock);
 			hlist_del(&dev->name_hlist);
+			hlist_del(&dev->index_hlist);
 			if (dev_tail == &dev->next)
 				dev_tail = dp;
 			*dp = d->next;
@@ -3121,6 +3132,9 @@
 
 	for (i = 0; i < ARRAY_SIZE(dev_name_head); i++)
 		INIT_HLIST_HEAD(&dev_name_head[i]);
+
+	for (i = 0; i < ARRAY_SIZE(dev_index_head); i++)
+		INIT_HLIST_HEAD(&dev_index_head[i]);
 
 	/*
 	 *	Initialise the packet receive queues.

^ permalink raw reply	[flat|nested] 8+ messages in thread

* [PATCH] (4/4) support large number of network devices -- alloc_name bitmap
  2004-01-16 23:46 [PATCH] (1/4) support large number of network devices Stephen Hemminger
  2004-01-16 23:48 ` [PATCH] (2/4) support large number of network devices -- name hash Stephen Hemminger
  2004-01-16 23:49 ` [PATCH] (3/4) support large number of network devices -- hash ifindex Stephen Hemminger
@ 2004-01-16 23:50 ` Stephen Hemminger
  2004-01-20  5:24 ` [PATCH] (1/4) support large number of network devices David S. Miller
  3 siblings, 0 replies; 8+ messages in thread
From: Stephen Hemminger @ 2004-01-16 23:50 UTC (permalink / raw)
  To: David S. Miller; +Cc: netdev

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;
 }
 
 

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] (2/4) support large number of network devices -- name hash
  2004-01-16 23:48 ` [PATCH] (2/4) support large number of network devices -- name hash Stephen Hemminger
@ 2004-01-17  2:22   ` YOSHIFUJI Hideaki / 吉藤英明
  2004-01-19 19:28     ` Stephen Hemminger
  0 siblings, 1 reply; 8+ messages in thread
From: YOSHIFUJI Hideaki / 吉藤英明 @ 2004-01-17  2:22 UTC (permalink / raw)
  To: shemminger; +Cc: davem, netdev, yoshfuji

In article <20040116154814.7c7f31ac.shemminger@osdl.org> (at Fri, 16 Jan 2004 15:48:14 -0800), Stephen Hemminger <shemminger@osdl.org> says:

> +	size_t len = min(strlen(name),(size_t)(IFNAMSIZ-1));

strnlen(name, IFNAMESIZ) ?

-- 
Hideaki YOSHIFUJI @ USAGI Project <yoshfuji@linux-ipv6.org>
GPG FP: 9022 65EB 1ECF 3AD1 0BDF  80D8 4807 F894 E062 0EEA

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] (2/4) support large number of network devices -- name hash
  2004-01-17  2:22   ` YOSHIFUJI Hideaki / 吉藤英明
@ 2004-01-19 19:28     ` Stephen Hemminger
  2004-01-22  2:10       ` YOSHIFUJI Hideaki / 吉藤英明
  0 siblings, 1 reply; 8+ messages in thread
From: Stephen Hemminger @ 2004-01-19 19:28 UTC (permalink / raw)
  To: YOSHIFUJI Hideaki / ____________, davem; +Cc: netdev, yoshfuji

Use strnlen, great idea, thanks.

diff -Nru a/net/core/dev.c b/net/core/dev.c
--- a/net/core/dev.c	Mon Jan 19 11:30:20 2004
+++ b/net/core/dev.c	Mon Jan 19 11:30:20 2004
@@ -192,8 +192,8 @@
 
 static inline struct hlist_head *dev_name_hash(const char *name)
 {
-	size_t len = min(strlen(name),(size_t)(IFNAMSIZ-1));
-	unsigned hash = full_name_hash(name, len);
+	unsigned hash = full_name_hash(name, 
+				       strnlen(name, IFNAMSIZ-1));
 	return &dev_name_head[hash & ((1<<NETDEV_HASHBITS)-1)];
 }
 

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] (1/4) support large number of network devices
  2004-01-16 23:46 [PATCH] (1/4) support large number of network devices Stephen Hemminger
                   ` (2 preceding siblings ...)
  2004-01-16 23:50 ` [PATCH] (4/4) support large number of network devices -- alloc_name bitmap Stephen Hemminger
@ 2004-01-20  5:24 ` David S. Miller
  3 siblings, 0 replies; 8+ messages in thread
From: David S. Miller @ 2004-01-20  5:24 UTC (permalink / raw)
  To: Stephen Hemminger; +Cc: netdev


I think I'm going to defer this change until the next 2.6.x, we have enough
crap in there now I believe :-)

Please remeber to resend this as I do want to integrate your work.

Thanks Stephen.

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] (2/4) support large number of network devices -- name hash
  2004-01-19 19:28     ` Stephen Hemminger
@ 2004-01-22  2:10       ` YOSHIFUJI Hideaki / 吉藤英明
  0 siblings, 0 replies; 8+ messages in thread
From: YOSHIFUJI Hideaki / 吉藤英明 @ 2004-01-22  2:10 UTC (permalink / raw)
  To: shemminger; +Cc: davem, netdev, yoshfuji

In article <20040119112850.3b3575a7.shemminger@osdl.org> (at Mon, 19 Jan 2004 11:28:50 -0800), Stephen Hemminger <shemminger@osdl.org> says:

> Use strnlen, great idea, thanks.

> -	size_t len = min(strlen(name),(size_t)(IFNAMSIZ-1));
> -	unsigned hash = full_name_hash(name, len);
> +	unsigned hash = full_name_hash(name, 
> +				       strnlen(name, IFNAMSIZ-1));

I prefer IFNAMSIZ over IFNAMSIZ-1 here
bacause maximum length of valid name is IFNAMSIZ-1.

strnlen(3):
       size_t strnlen(const char *s, size_t maxlen);
:
       The strnlen function returns strlen(s), if that is less than maxlen, or
       maxlen  if there is no '\0' character among the first maxlen characters
       pointed to by s.

If strnlen(name,IFNAMSIZ) returns IFNAMSIZ, name is not terminated.
while strnlen(name,IFNAMSIZ-1) does not tell whether it is terminated or not.

--yoshfuji

^ permalink raw reply	[flat|nested] 8+ messages in thread

end of thread, other threads:[~2004-01-22  2:10 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-01-16 23:46 [PATCH] (1/4) support large number of network devices Stephen Hemminger
2004-01-16 23:48 ` [PATCH] (2/4) support large number of network devices -- name hash Stephen Hemminger
2004-01-17  2:22   ` YOSHIFUJI Hideaki / 吉藤英明
2004-01-19 19:28     ` Stephen Hemminger
2004-01-22  2:10       ` YOSHIFUJI Hideaki / 吉藤英明
2004-01-16 23:49 ` [PATCH] (3/4) support large number of network devices -- hash ifindex Stephen Hemminger
2004-01-16 23:50 ` [PATCH] (4/4) support large number of network devices -- alloc_name bitmap Stephen Hemminger
2004-01-20  5:24 ` [PATCH] (1/4) support large number of network devices David S. Miller

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.