This patch should increase the performance of dev_get
and dev_get_by_index when you have large numbers of interfaces.
This is particularly useful when you are using, say, 4000 VLAN
interfaces or something...
(This patch is included in the VLAN patch..so don't apply it again.)
Comments & suggestions welcome...
*** ../../../linux/net/core/dev.c Mon Sep 4 10:39:29 2000
--- dev.c Sun Oct 15 15:15:15 2000
***************
*** 1,3 ****
! /*
* NET3 Protocol independent device support routines.
*
--- 1,3 ----
! /* -*- linux-c -*-
* NET3 Protocol independent device support routines.
*
***************
*** 93,96 ****
--- 93,101 ----
#include <linux/wireless.h>
#endif /* CONFIG_NET_RADIO */
+
+ #ifdef CONFIG_VLAN_802_1Q
+ #include "../802_1Q/vlan.h"
+ #endif
+
#ifdef CONFIG_PLIP
extern int plip_init(void);
***************
*** 122,128 ****
*
* Why 16. Because with 16 the only overlap we get on a hash of the
! * low nibble of the protocol value is RARP/SNAP/X.25.
*
* 0800 IP
* 0001 802.3
* 0002 AX.25
--- 127,141 ----
*
* Why 16. Because with 16 the only overlap we get on a hash of the
! * low nibble of the protocol value is RARP/SNAP/X.25.
! *
! * NOTE: That is no longer true with the addition of VLAN tags. Not
! * sure which should go first, but I bet it won't make much
! * difference if we are running VLANs. The good news is that
! * this protocol won't be in the list unless compiled in, so
! * the average user (w/out VLANs) will not be adversly affected.
! * --BLG
*
* 0800 IP
+ * 8100 802.1Q VLAN
* 0001 802.3
* 0002 AX.25
***************
*** 169,172 ****
--- 182,429 ----
+ #define BENS_FAST_DEV_LOOKUP
+ #ifdef BENS_FAST_DEV_LOOKUP
+ /* Fash Device Lookup code. Should give much better than
+ * linear speed when looking for devices by idx or name.
+ * --Ben (greearb@candelatech.com)
+ */
+ #define FDL_HASH_LEN 256
+
+ /* #define FDL_DEBUG */
+
+ struct dev_hash_node {
+ struct device* dev;
+ struct dev_hash_node* next;
+ };
+
+ struct dev_hash_node* fdl_name_base[FDL_HASH_LEN];/* hashed by name */
+ struct dev_hash_node* fdl_idx_base[FDL_HASH_LEN]; /* hashed by index */
+ int fdl_initialized_yet = 0;
+
+ /* TODO: Make these inline methods */
+ /* Nice cheesy little hash method to be used on device-names (eth0, ppp0, etc) */
+ int fdl_calc_name_idx(const char* dev_name) {
+ int tmp = 0;
+ int i;
+ #ifdef FDL_DEBUG
+ printk(KERN_ERR "fdl_calc_name_idx, name: %s\n", dev_name);
+ #endif
+ 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 */
+ }
+ #ifdef FDL_DEBUG
+ printk(KERN_ERR "fdl_calc_name_idx, rslt: %i\n", (int)(tmp % FDL_HASH_LEN));
+ #endif
+ return (tmp % FDL_HASH_LEN);
+ }
+
+ int fdl_calc_index_idx(const int ifindex) {
+ return (ifindex % FDL_HASH_LEN);
+ }
+
+
+ /* Better have a lock on the dev_base before calling this... */
+ int __fdl_ensure_init(void) {
+ #ifdef FDL_DEBUG
+ printk(KERN_ERR "__fdl_ensure_init, enter\n");
+ #endif
+ if (! fdl_initialized_yet) {
+ /* only do this once.. */
+ int i;
+ int idx = 0; /* into the hash table */
+ struct device* dev = dev_base;
+ struct dev_hash_node* dhn;
+
+ #ifdef FDL_DEBUG
+ printk(KERN_ERR "__fdl_ensure_init, doing real work...");
+ #endif
+
+ fdl_initialized_yet = 1; /* it has been attempted at least... */
+
+ for (i = 0; i<FDL_HASH_LEN; i++) {
+ fdl_name_base[i] = NULL;
+ fdl_idx_base[i] = NULL;
+ }
+
+ /* add any current devices to the hash tables at this time. Note that
+ * this method must be called with locks on the dev_base acquired.
+ */
+ while (dev) {
+
+ #ifdef FDL_DEBUG
+ printk(KERN_ERR "__fdl_ensure_init, dev: %p dev: %s, idx: %i\n", dev, dev->name, idx);
+ #endif
+ /* first, take care of the hash-by-name */
+ idx = fdl_calc_name_idx(dev->name);
+ dhn = kmalloc(sizeof(struct dev_hash_node), GFP_ATOMIC);
+ if (dhn) {
+ dhn->dev = dev;
+ dhn->next = fdl_name_base[idx];
+ fdl_name_base[idx] = dhn;
+ }
+ else {
+ /* Nasty..couldn't get memory... */
+ return -ENOMEM;
+ }
+
+ /* now, do the hash-by-idx */
+ idx = fdl_calc_index_idx(dev->ifindex);
+ dhn = kmalloc(sizeof(struct dev_hash_node), GFP_ATOMIC);
+ if (dhn) {
+ dhn->dev = dev;
+ dhn->next = fdl_idx_base[idx];
+ fdl_idx_base[idx] = dhn;
+ }
+ else {
+ /* Nasty..couldn't get memory... */
+ return -ENOMEM;
+ }
+
+ dev = dev->next;
+ }
+ fdl_initialized_yet = 2; /* initialization actually worked */
+ }
+ #ifdef FDL_DEBUG
+ printk(KERN_ERR "__fdl_ensure_init, end, fdl_initialized_yet: %i\n", fdl_initialized_yet);
+ #endif
+ if (fdl_initialized_yet == 2) {
+ return 0;
+ }
+ else {
+ return -1;
+ }
+ }/* fdl_ensure_init */
+
+
+ /* called from register_netdevice, assumes dev is locked, and that no one
+ * will be calling __find_dev_by_name before this exits.. etc.
+ */
+ int __fdl_register_netdevice(struct device* dev) {
+ if (__fdl_ensure_init() == 0) {
+ /* first, take care of the hash-by-name */
+ int idx = fdl_calc_name_idx(dev->name);
+ struct dev_hash_node* dhn = kmalloc(sizeof(struct dev_hash_node), GFP_ATOMIC);
+
+ #ifdef FDL_DEBUG
+ printk(KERN_ERR "__fdl_register_netdevice, dev: %p dev: %s, idx: %i", dev, dev->name, idx);
+ #endif
+
+ if (dhn) {
+ dhn->dev = dev;
+ dhn->next = fdl_name_base[idx];
+ fdl_name_base[idx] = dhn;
+ }
+ else {
+ /* Nasty..couldn't get memory... */
+ /* Don't try to use these hash tables any more... */
+ fdl_initialized_yet = 1; /* tried, but failed */
+ return -ENOMEM;
+ }
+
+ /* now, do the hash-by-idx */
+ idx = fdl_calc_index_idx(dev->ifindex);
+ dhn = kmalloc(sizeof(struct dev_hash_node), GFP_ATOMIC);
+
+ #ifdef FDL_DEBUG
+ printk(KERN_ERR "__fdl_register_netdevice, ifindex: %i, idx: %i", dev->ifindex, idx);
+ #endif
+
+ if (dhn) {
+ dhn->dev = dev;
+ dhn->next = fdl_idx_base[idx];
+ fdl_idx_base[idx] = dhn;
+ }
+ else {
+ /* Nasty..couldn't get memory... */
+ /* Don't try to use these hash tables any more... */
+ fdl_initialized_yet = 1; /* tried, but failed */
+ return -ENOMEM;
+ }
+ }
+ return 0;
+ } /* fdl_register_netdevice */
+
+
+ /* called from register_netdevice, assumes dev is locked, and that no one
+ * will be calling __find_dev_by_name, etc. Returns 0 if found & removed one,
+ * returns -1 otherwise.
+ */
+ int __fdl_unregister_netdevice(struct device* dev) {
+ int retval = -1;
+ if (fdl_initialized_yet == 2) { /* If we've been initialized correctly... */
+ /* first, take care of the hash-by-name */
+ int idx = fdl_calc_name_idx(dev->name);
+ struct dev_hash_node* prev = fdl_name_base[idx];
+ struct dev_hash_node* cur = NULL;
+
+ #ifdef FDL_DEBUG
+ printk(KERN_ERR "__fdl_unregister_netdevice, dev: %p dev: %s, idx: %i", dev, dev->name, idx);
+ #endif
+
+ if (prev) {
+ if (strcmp(dev->name, prev->dev->name) == 0) {
+ /* it's the first one... */
+ fdl_name_base[idx] = prev->next;
+ kfree(prev);
+ retval = 0;
+ }
+ else {
+ cur = prev->next;
+ while (cur) {
+ if (strcmp(dev->name, cur->dev->name) == 0) {
+ prev->next = cur->next;
+ kfree(cur);
+ retval = 0;
+ break;
+ }
+ else {
+ prev = cur;
+ cur = cur->next;
+ }
+ }
+ }
+ }
+
+ /* Now, the hash-by-index */
+ idx = fdl_calc_index_idx(dev->ifindex);
+ prev = fdl_idx_base[idx];
+ cur = NULL;
+ if (prev) {
+ if (dev->ifindex == prev->dev->ifindex) {
+ /* it's the first one... */
+ fdl_idx_base[idx] = prev->next;
+ kfree(prev);
+ retval = 0;
+ }
+ else {
+ cur = prev->next;
+ while (cur) {
+ if (dev->ifindex == cur->dev->ifindex) {
+ prev->next = cur->next;
+ kfree(cur);
+ retval = 0;
+ break;
+ }
+ else {
+ prev = cur;
+ cur = cur->next;
+ }
+ }
+ }
+ }
+ }/* if we ensured init OK */
+ return retval;
+ } /* fdl_unregister_netdevice */
+
+
+
+ #endif /* BENS_FAST_DEV_LOOKUP */
+
+
+
/******************************************************************************************
***************
*** 266,269 ****
--- 523,545 ----
struct device *dev;
+ #ifdef BENS_FAST_DEV_LOOKUP
+ int idx = fdl_calc_name_idx(name);
+ struct dev_hash_node* dhn;
+ if (fdl_initialized_yet == 2) {
+ #ifdef FDL_DEBUG
+ printk(KERN_ERR "__dev_get_by_name, name: %s idx: %i\n", name, idx);
+ #endif
+ dhn = fdl_name_base[idx];
+ while (dhn) {
+ if (strcmp(dhn->dev->name, name) == 0) {
+ /* printk(KERN_ERR "__dev_get_by_name, found it: %p\n", dhn->dev); */
+ return dhn->dev;
+ }
+ dhn = dhn->next;
+ }
+ /* printk(KERN_ERR "__dev_get_by_name, didn't find it for name: %s\n", name); */
+ return NULL;
+ }
+ #endif
for (dev = dev_base; dev != NULL; dev = dev->next)
{
***************
*** 277,281 ****
{
struct device *dev;
!
for (dev = dev_base; dev != NULL; dev = dev->next)
{
--- 553,569 ----
{
struct device *dev;
! #ifdef BENS_FAST_DEV_LOOKUP
! int idx = fdl_calc_index_idx(ifindex);
! struct dev_hash_node* dhn;
! if (fdl_initialized_yet == 2) { /* have we gone through initialization before... */
! dhn = fdl_idx_base[idx];
! while (dhn) {
! if (dhn->dev->ifindex == ifindex)
! return dhn->dev;
! dhn = dhn->next;
! }
! return NULL;
! }
! #endif
for (dev = dev_base; dev != NULL; dev = dev->next)
{
***************
*** 309,314 ****
/*
* If you need over 100 please also fix the algorithm...
! */
! for(i=0;i<100;i++)
{
sprintf(dev->name,name,i);
--- 597,605 ----
/*
* If you need over 100 please also fix the algorithm...
! *
! * Increased it to deal with VLAN interfaces. It is unlikely
! * that this many will ever be added, but it can't hurt! -BLG
! */
! for(i=0;i<8192;i++)
{
sprintf(dev->name,name,i);
***************
*** 316,320 ****
return i;
}
! return -ENFILE; /* Over 100 of the things .. bail out! */
}
--- 607,611 ----
return i;
}
! return -ENFILE; /* Over 8192 of the things .. bail out! */
}
***************
*** 829,833 ****
return;
! offset=skb->data-skb->mac.raw;
skb_push(skb,offset); /* Put header back on for bridge */
--- 1120,1124 ----
return;
! offset = skb->data - skb->mac.raw;
skb_push(skb,offset); /* Put header back on for bridge */
***************
*** 938,942 ****
/*
! * Fetch the packet protocol ID.
*/
--- 1229,1233 ----
/*
! * Fetch the packet protocol ID. (In Network Byte Order --BLG)
*/
***************
*** 1576,1581 ****
--- 1867,1879 ----
if (dev_get(ifr->ifr_newname))
return -EEXIST;
+ #ifdef BENS_FAST_DEV_LOOKUP
+ /* Doesn't seem to need any additional locking in kernel 2.2 series... --Ben */
+ __fdl_unregister_netdevice(dev); /* take it out of the name hash table */
+ #endif
memcpy(dev->name, ifr->ifr_newname, IFNAMSIZ);
dev->name[IFNAMSIZ-1] = 0;
+ #ifdef BENS_FAST_DEV_LOOKUP
+ __fdl_register_netdevice(dev); /* put it back in the name hash table, with the new name */
+ #endif
notifier_call_chain(&netdev_chain, NETDEV_CHANGENAME, dev);
return 0;
***************
*** 1780,1783 ****
--- 2078,2087 ----
}
dev->next = NULL;
+ #ifdef BENS_FAST_DEV_LOOKUP
+ /* Must do this before dp is set to dev, or it could be added twice, once
+ * on initialization based on dev_base, and once again after that...
+ */
+ __fdl_register_netdevice(dev);
+ #endif
*dp = dev;
return 0;
***************
*** 1800,1803 ****
--- 2104,2114 ----
if (dev->iflink == -1)
dev->iflink = dev->ifindex;
+
+ #ifdef BENS_FAST_DEV_LOOKUP
+ /* Must do this before dp is set to dev, or it could be added twice, once
+ * on initialization based on dev_base, and once again after that...
+ */
+ __fdl_register_netdevice(dev);
+ #endif
*dp = dev;
***************
*** 1847,1850 ****
--- 2158,2164 ----
if (d == dev) {
*dp = d->next;
+ #ifdef BENS_FAST_DEV_LOOKUP
+ __fdl_unregister_netdevice(dev);
+ #endif
synchronize_bh();
d->next = NULL;
--
Ben Greear (greearb@candelatech.com) http://www.candelatech.com
Author of ScryMUD: scry.wanfear.com 4444 (Released under GPL)
http://scry.wanfear.com http://scry.wanfear.com/~greear
-
: send the line "unsubscribe linux-net" in
the body of a message to majordomo@vger.kernel.org
