[PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[Ben Greear]

I'm hoping that I can get a few comments on this code.  It was added
to (significantly) speed up things like 'ifconfig -a' when running with
4000 or so VLAN devices.  It should also help other instances with lots
of (virtual) devices, like FrameRelay, ATM, and possibly virtual IP
interfaces.  It probably won't help 'normal' users much, and in it's final
form, should probably be a selectable option in the config process.

Anyway, let me know what you think!

Patch to net/core/dev.c of 2.4.0 fame:

*** ../../../linux/net/core/dev.c	Mon Dec 11 14:29:35 2000
--- dev.c	Sat Jan  6 14:14:10 2001
***************
*** 1,3 ****
! /*
   * 	NET3	Protocol independent device support routines.
   *
--- 1,3 ----
! /* -*- linux-c -*-
   * 	NET3	Protocol independent device support routines.
   *
***************
*** 132,138 ****
   *
   *	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
--- 133,147 ----
   *
   *	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
***************
*** 179,182 ****
--- 188,435 ----
  
  
+ #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 net_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 net_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 net_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 net_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 */
+ 
+ 
+ 
  /******************************************************************************************
  
***************
*** 397,401 ****
  {
  	struct net_device *dev;
! 
  	for (dev = dev_base; dev != NULL; dev = dev->next) {
  		if (strcmp(dev->name, name) == 0)
--- 650,673 ----
  {
  	struct net_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) {
  		if (strcmp(dev->name, name) == 0)
***************
*** 473,476 ****
--- 745,762 ----
  	struct net_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) {
  		if (dev->ifindex == ifindex)
***************
*** 550,555 ****
  	/*
  	 *	If you need over 100 please also fix the algorithm...
  	 */
! 	for (i = 0; i < 100; i++) {
  		sprintf(buf,name,i);
  		if (__dev_get_by_name(buf) == NULL) {
--- 836,843 ----
  	/*
  	 *	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(buf,name,i);
  		if (__dev_get_by_name(buf) == NULL) {
***************
*** 558,562 ****
  		}
  	}
! 	return -ENFILE;	/* Over 100 of the things .. bail out! */
  }
  
--- 846,850 ----
  		}
  	}
! 	return -ENFILE;	/* Over 8192 of the things .. bail out! */
  }
  
***************
*** 2068,2073 ****
--- 2356,2369 ----
  			if (__dev_get_by_name(ifr->ifr_newname))
  				return -EEXIST;
+ #ifdef BENS_FAST_DEV_LOOKUP
+                         write_lock_bh(&dev_base_lock); /* gotta lock it to remove stuff */
+                         __fdl_unregister_netdevice(dev); /* remove it from the hash.. */
+ #endif
  			memcpy(dev->name, ifr->ifr_newname, IFNAMSIZ);
  			dev->name[IFNAMSIZ-1] = 0;
+ #ifdef BENS_FAST_DEV_LOOKUP
+                         __fdl_register_netdevice(dev);
+                         write_unlock_bh(&dev_base_lock); /* gotta lock it to add stuff too */
+ #endif                        
  			notifier_call_chain(&netdev_chain, NETDEV_CHANGENAME, dev);
  			return 0;
***************
*** 2343,2346 ****
--- 2639,2648 ----
  		dev->next = NULL;
  		write_lock_bh(&dev_base_lock);
+ #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;
  		dev_hold(dev);
***************
*** 2397,2400 ****
--- 2699,2708 ----
  	dev_init_scheduler(dev);
  	write_lock_bh(&dev_base_lock);
+ #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;
  	dev_hold(dev);
***************
*** 2469,2473 ****
  			write_lock_bh(&dev_base_lock);
  			*dp = d->next;
! 			write_unlock_bh(&dev_base_lock);
  			break;
  		}
--- 2777,2784 ----
  			write_lock_bh(&dev_base_lock);
  			*dp = d->next;
! #ifdef BENS_FAST_DEV_LOOKUP
!                         __fdl_unregister_netdevice(dev);
! #endif
!                         write_unlock_bh(&dev_base_lock);
  			break;
  		}

-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[David S. Miller]

Unified diffs only please... Thanks.

Later,
David S. Miller
davem@redhat.com
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[Chris Wedgwood]

On Sat, Jan 06, 2001 at 02:33:27PM -0700, Ben Greear wrote:

    I'm hoping that I can get a few comments on this code.  It was
    added to (significantly) speed up things like 'ifconfig -a' when
    running with 4000 or so VLAN devices.  It should also help other
    instances with lots of (virtual) devices, like FrameRelay, ATM,
    and possibly virtual IP interfaces.  It probably won't help
    'normal' users much, and in it's final form, should probably be a
    selectable option in the config process.

Virtual IP interfaces in the form of ifname:<number> (e.g. eth:1) IMO
should be deprecated and removed completely in 2.5.x. It's an ugly
external wart that should be removed.

That said, if this was done -- how would things like routing daemons
and bind cope? Actually, when I think about it they can't cope with
situating like this now:

tapu:~# ip addr show lo
1: lo: <LOOPBACK,UP> mtu 3904 qdisc noqueue
    link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
    inet 127.0.0.1/8 scope host lo
    inet 10.0.0.1/32 scope global lo



  --cw
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[Andi Kleen]

On Sat, Jan 06, 2001 at 02:33:27PM -0700, Ben Greear wrote:
> I'm hoping that I can get a few comments on this code.  It was added
> to (significantly) speed up things like 'ifconfig -a' when running with
> 4000 or so VLAN devices.  It should also help other instances with lots
> of (virtual) devices, like FrameRelay, ATM, and possibly virtual IP
> interfaces.  It probably won't help 'normal' users much, and in it's final
> form, should probably be a selectable option in the config process.
> 
> Anyway, let me know what you think!

Does it make any significant different with the ifconfig from newest nettools? I 
removed a quadratic algorithm from ifconfig's device parsing, and with that I was 
able to display a few thousand alias devices on a unpatched kernel in reasonable time.



-Andi
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[jamal]

On Sun, 7 Jan 2001, Andi Kleen wrote:

> Does it make any significant different with the ifconfig from newest nettools? I
> removed a quadratic algorithm from ifconfig's device parsing, and with that I was
> able to display a few thousand alias devices on a unpatched kernel in reasonable time.

I think someone should just flush ifconfig down some toilet. a wrapper
around "ip" to to give the same look and feel as ifconfig would be a good
thing so that some stupid program that depends on ifconfig look and feel
would be a good start.

Not to stray from the subject, Ben's effort is still needed. I think real
numbers are useful instead of claims like it "displayed faster"

cheers,
jamal

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[Andi Kleen]

On Sat, Jan 06, 2001 at 11:00:10PM -0500, jamal wrote:
> Not to stray from the subject, Ben's effort is still needed. I think real
> numbers are useful instead of claims like it "displayed faster"

The problem with old ifconfig was really visible, old ifconfig needed several
minutes to setup. It was slow enough that "visual benchmarking" worked very well.
With the fixed ifconfig it scrolls without too annoying delays.

The ifconfig could be tuned even more by adding a hash table, but it didn't look
necessary (and frankly nobody wants to invest too much work into it, given
that ip is far superior) 

Note that the alias case is different from thousands of devices -- alias works
via SIOCGIFCONF while devices work via /proc/net/dev. 


-Andi

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[Ben Greear]

"David S. Miller" wrote:
> 
> Unified diffs only please... Thanks.

Hrm, here's one with a -u option, this what you're looking for?


--- ../../../linux/net/core/dev.c	Mon Dec 11 14:29:35 2000
+++ dev.c	Sat Jan  6 14:14:10 2001
@@ -1,4 +1,4 @@
-/*
+/* -*- linux-c -*-
  * 	NET3	Protocol independent device support routines.
  *
  *		This program is free software; you can redistribute it and/or
@@ -131,9 +132,17 @@
  *	and the routines to invoke.
  *
  *	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. 
+ *	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
  *		0004	802.2
@@ -178,6 +187,250 @@
 #endif
 
 
+#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 net_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 net_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 net_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 net_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 */
+
+
+
 /******************************************************************************************
 
 		Protocol management and registration routines
@@ -396,7 +649,26 @@
 struct net_device *__dev_get_by_name(const char *name)
 {
 	struct net_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) {
 		if (strcmp(dev->name, name) == 0)
 			return dev;
@@ -472,6 +744,20 @@
 {
 	struct net_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) {
 		if (dev->ifindex == ifindex)
 			return dev;
@@ -549,15 +835,17 @@
 
 	/*
 	 *	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 < 100; i++) {
+	for (i = 0; i < 8192; i++) {
 		sprintf(buf,name,i);
 		if (__dev_get_by_name(buf) == NULL) {
 			strcpy(dev->name, buf);
 			return i;
 		}
 	}
-	return -ENFILE;	/* Over 100 of the things .. bail out! */
+	return -ENFILE;	/* Over 8192 of the things .. bail out! */
 }
 
 /**
@@ -2067,8 +2355,16 @@
 				return -EBUSY;
 			if (__dev_get_by_name(ifr->ifr_newname))
 				return -EEXIST;
+#ifdef BENS_FAST_DEV_LOOKUP
+                        write_lock_bh(&dev_base_lock); /* gotta lock it to remove stuff */
+                        __fdl_unregister_netdevice(dev); /* remove it from the hash.. */
+#endif
 			memcpy(dev->name, ifr->ifr_newname, IFNAMSIZ);
 			dev->name[IFNAMSIZ-1] = 0;
+#ifdef BENS_FAST_DEV_LOOKUP
+                        __fdl_register_netdevice(dev);
+                        write_unlock_bh(&dev_base_lock); /* gotta lock it to add stuff too */
+#endif                        
 			notifier_call_chain(&netdev_chain, NETDEV_CHANGENAME, dev);
 			return 0;
 
@@ -2342,6 +2638,12 @@
 		}
 		dev->next = NULL;
 		write_lock_bh(&dev_base_lock);
+#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;
 		dev_hold(dev);
 		write_unlock_bh(&dev_base_lock);
@@ -2396,6 +2698,12 @@
 	dev->next = NULL;
 	dev_init_scheduler(dev);
 	write_lock_bh(&dev_base_lock);
+#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;
 	dev_hold(dev);
 	dev->deadbeaf = 0;
@@ -2468,7 +2776,10 @@
 		if (d == dev) {
 			write_lock_bh(&dev_base_lock);
 			*dp = d->next;
-			write_unlock_bh(&dev_base_lock);
+#ifdef BENS_FAST_DEV_LOOKUP
+                        __fdl_unregister_netdevice(dev);
+#endif
+                        write_unlock_bh(&dev_base_lock);
 			break;
 		}
 	}


-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[Andi Kleen]

On Sat, Jan 06, 2001 at 11:22:41PM -0700, Ben Greear wrote:
> At the time I was doing this, I downloaded the latest nettools version.
> The hashing made a very noticable difference on 4000 interfaces, but
> I haven't run any real solid benchmarkings at other levels.  Can
> you tell me some distinguishing mark (version?) on ifconfig that I
> can look for?

Just get the latest release.

> 
> I'm willing to run such benchmarks, but what would make a good benchmark,
> other than ifconfig -a?

ifconfig -a is fine IMHO. Everything else I know is just a single pass through
the lists (which even at 4000 is not very significant) 

> Suppose I bind a raw socket to device vlan4001 (ie I have 4k in the list
> before that one!!).  Currently, that means a linear search on all devices,
> right?  In that extreme example, I would expect the hash to be very
> useful.

Nope, it doesn't. Raw binding works via IP addresses, and the IP address resolution
works via the routing table, which is extensively hashed.

Packet socket binding or SO_BINDTODEVICE will search the list, but it is unlikely
that these paths are worth optimizing for.


> Binding to IP addresses have the same issue??

No, uses the fib.

> Also, though hashing by name is not horribly exact, hashing on the device
> index should be nearly perfect, so finding device 666 might take a search
> through only 5 or so devices (find the hash-bucket, walk down the list in
> that bucket).

Just why? It is not in any critical path I can see at all. 


-Andi

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumissionpolicy!)

[Andi Kleen]

On Sat, Jan 06, 2001 at 11:24:41PM -0700, Ben Greear wrote:
> jamal wrote:
> > 
> 
> > Not to stray from the subject, Ben's effort is still needed. I think real
> > numbers are useful instead of claims like it "displayed faster"
> 
> A single #define near the top of the patch will turn it on/off, so
> benchmarking should be fairly easy.  Please suggest benchmarks you
> consider valid.

The only issue I know was the long delay in ifconfig.
If that's fixed I see nothing else that would be worth benchmarking. 


-Andi
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[David S. Miller]

   Date: Sat, 06 Jan 2001 21:06:54 -0700
   From: Ben Greear <greearb@candelatech.com>

   "David S. Miller" wrote:
   > 
   > Unified diffs only please... Thanks.

   Hrm, here's one with a -u option, this what you're looking for?

Yes, thanks a lot.

Later,
David S. Miller
davem@redhat.com
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[David S. Miller]

   On Sat, Jan 06, 2001 at 02:33:27PM -0700, Ben Greear wrote:

       I'm hoping that I can get a few comments on this code.  It was
       added to (significantly) speed up things like 'ifconfig -a' when
       running with 4000 or so VLAN devices.  It should also help other
       instances with lots of (virtual) devices, like FrameRelay, ATM,
       and possibly virtual IP interfaces.  It probably won't help
       'normal' users much, and in it's final form, should probably be a
       selectable option in the config process.

Ben, if ifconfig uses /proc/net/dev to list devices, how can your
changes speed up ifconfig?  Andi mentioned in another email how he has
fixed the quadratic behavior in ifconfig, you should check if it fixes
your problem.  Jamal has suggested dumping ifconfig and making a dummy
"ifconfig" which just wrappers around "ip".  I like this idea the most.

Really, what I'm concerned about is what calls dev_get_by_{name,index}
so often and in such critical places that optimizing it makes any
sense?

I don't mind optimizing stuff like this where needed, in fact I'm the
most guilty of this, check out the complex TCP hash tables we have :-)
But if it's only a problem because of poorly implemented user
applications, let's fix the apps instead of adding the complexity to
the kernel.

Later,
David S. Miller
davem@redhat.com
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[David S. Miller]

   Date:   Sat, 6 Jan 2001 23:00:10 -0500 (EST)
   From: jamal <hadi@cyberus.ca>

   I think someone should just flush ifconfig down some toilet. a wrapper
   around "ip" to to give the same look and feel as ifconfig would be a good
   thing so that some stupid program that depends on ifconfig look and feel
   would be a good start.

I could not agree more.  This reminds me to do something I could not
justify before, making netlink be enabled in the kernel and
non-configurable.

I could almost, but not quite, justify it right now just because "ip"
is becomming standard and needs it.

   Not to stray from the subject, Ben's effort is still needed. I think real
   numbers are useful instead of claims like it "displayed faster"

See my previous email, if it's just slow because of some poorly coded
version of ifconfig, it does not justify the patch.  If only a
forcefully created "benchmark" can show some performance problem, that
is not an acceptable reason to champion this patch.  Ok?

Later,
David S. Miller
davem@redhat.com
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[Ben Greear]

Chris Wedgwood wrote:
> 
> On Sat, Jan 06, 2001 at 02:33:27PM -0700, Ben Greear wrote:
> 
>     I'm hoping that I can get a few comments on this code.  It was
>     added to (significantly) speed up things like 'ifconfig -a' when
>     running with 4000 or so VLAN devices.  It should also help other
>     instances with lots of (virtual) devices, like FrameRelay, ATM,
>     and possibly virtual IP interfaces.  It probably won't help
>     'normal' users much, and in it's final form, should probably be a
>     selectable option in the config process.
> 
> Virtual IP interfaces in the form of ifname:<number> (e.g. eth:1) IMO
> should be deprecated and removed completely in 2.5.x. It's an ugly
> external wart that should be removed.

I don't know enough to have any serious opinion about virtual IP
interfaces, but I am very certain that VLANs should appear as
an interface to external code/user-land, just as eth0 does.

This hashing helps with VLANs, and since I aim to get VLANs into
the kernel proper sooner or later, having this piece in there
makes my patch a little smaller :)

However, if folks look at the patch and hate it, then it can
be left out, or changed appropriately.

Ben

-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[Ben Greear]

Andi Kleen wrote:
> 
> On Sat, Jan 06, 2001 at 02:33:27PM -0700, Ben Greear wrote:
> > I'm hoping that I can get a few comments on this code.  It was added
> > to (significantly) speed up things like 'ifconfig -a' when running with
> > 4000 or so VLAN devices.  It should also help other instances with lots
> > of (virtual) devices, like FrameRelay, ATM, and possibly virtual IP
> > interfaces.  It probably won't help 'normal' users much, and in it's final
> > form, should probably be a selectable option in the config process.
> >
> > Anyway, let me know what you think!
> 
> Does it make any significant different with the ifconfig from newest nettools? I
> removed a quadratic algorithm from ifconfig's device parsing, and with that I was
> able to display a few thousand alias devices on a unpatched kernel in reasonable time.
> 
> -Andi

At the time I was doing this, I downloaded the latest nettools version.
The hashing made a very noticable difference on 4000 interfaces, but
I haven't run any real solid benchmarkings at other levels.  Can
you tell me some distinguishing mark (version?) on ifconfig that I
can look for?

I'm willing to run such benchmarks, but what would make a good benchmark,
other than ifconfig -a?

And a question for the socket gurus:

Suppose I bind a raw socket to device vlan4001 (ie I have 4k in the list
before that one!!).  Currently, that means a linear search on all devices,
right?  In that extreme example, I would expect the hash to be very
useful.

Binding to IP addresses have the same issue??

Also, though hashing by name is not horribly exact, hashing on the device
index should be nearly perfect, so finding device 666 might take a search
through only 5 or so devices (find the hash-bucket, walk down the list in
that bucket).

-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumissionpolicy!)

[Ben Greear]

jamal wrote:
> 

> Not to stray from the subject, Ben's effort is still needed. I think real
> numbers are useful instead of claims like it "displayed faster"

A single #define near the top of the patch will turn it on/off, so
benchmarking should be fairly easy.  Please suggest benchmarks you
consider valid.

Thanks,
Ben

-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!) (Benchmarks)

[Andi Kleen]

On Sun, Jan 07, 2001 at 01:11:11AM -0700, Ben Greear wrote:
> > Packet socket binding or SO_BINDTODEVICE will search the list, but it is unlikely
> > that these paths are worth optimizing for.
> 
> The patch has been written, so even if it helps just a little more than it
> hurts, it might be worth including.  Of course, it may actually hurt more
> than help.
> 
> I'd be very interested in lucid arguments as to why adding the patch would
> actually be worse than not adding it, not just why I'm lame for considering
> it *grin* :)

It's like David said: it's not a very good idea to tune things that are not
commonly used. If some user really realistically has some workload where the
linear search is a bottleneck it can be considered. Currently it doesn't look
like it.




-Andi
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!) (Benchmarks)

[Ben Greear]

[-- Attachment #1: Type: text/plain, Size: 5587 bytes --]

Andi Kleen wrote:

> > I'm willing to run such benchmarks, but what would make a good benchmark,
> > other than ifconfig -a?
> 
> ifconfig -a is fine IMHO. Everything else I know is just a single pass through
> the lists (which even at 4000 is not very significant)

Hardware:  Celeron 500, mostly idle (ie not too scientific!!)
ifconfig:
  [root@candle bin]# /sbin/ifconfig --version
  net-tools 1.57
  ifconfig 1.40 (2000-05-21)
(vlan_test.pl is attached)

My conclusion:  The patch definately helps in this instance, but
  this instance may not be realistic.

***********************************************************************
This is with the hash patch enabled: (2.4.prerelease + VLAN patch) (run 2)
***********************************************************************

[root@candle bin]# time vlan_test.pl 
Adding VLAN interfaces 1 through 4000
Done adding 4000 VLAN interfaces in 76 seconds.
Doing ifconfig -a
10.47user 6.33system 0:16.80elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (116major+421minor)pagefaults 0swaps
Removing VLAN interfaces 1 through 4000
Done deleting 4000 VLAN interfaces in 58 seconds.

Going to add and remove 2 interfaces 1000 times.
Done adding/removing 2 VLAN interfaces 1000 times in 46 seconds.
74.12user 115.26system 3:22.81elapsed 93%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (2821121major+677780minor)pagefaults 0swaps


***********************************************************************
This is with the patch disabled: (2.4.0 + VLAN patch) (run 1)
***********************************************************************

[root@candle /root]# time vlan_test.pl
Adding VLAN interfaces 1 through 4000
Done adding 4000 VLAN interfaces in 132 seconds.
Doing ifconfig -a
10.72user 96.31system 1:55.31elapsed 92%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (117major+423minor)pagefaults 0swaps
Removing VLAN interfaces 1 through 4000
Done deleting 4000 VLAN interfaces in 65 seconds.

Going to add and remove 2 interfaces 1000 times.
Done adding/removing 2 VLAN interfaces 1000 times in 47 seconds.
74.20user 257.83system 6:04.46elapsed 91%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (2821122major+677782minor)pagefaults 0swaps


***********************************************************************
This is with the patch enabled: (2.4.0 + VLAN patch) (run 1)
***********************************************************************

[root@candle /root]# time vlan_test.pl
Adding VLAN interfaces 1 through 4000
Done adding 4000 VLAN interfaces in 83 seconds.
Doing ifconfig -a
10.61user 10.22system 0:23.43elapsed 88%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (117major+423minor)pagefaults 0swaps
Removing VLAN interfaces 1 through 4000
Done deleting 4000 VLAN interfaces in 64 seconds.

Going to add and remove 2 interfaces 1000 times.
Done adding/removing 2 VLAN interfaces 1000 times in 47 seconds.
73.69user 120.69system 3:44.10elapsed 86%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (2821122major+677782minor)pagefaults 0swaps


***********************************************************************
This is with the patch enabled: (2.4.0 + VLAN patch) (run 2)
***********************************************************************

[root@candle /root]# time vlan_test.pl
Adding VLAN interfaces 1 through 4000
Done adding 4000 VLAN interfaces in 80 seconds.
Doing ifconfig -a
10.62user 6.31system 0:18.63elapsed 90%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (117major+423minor)pagefaults 0swaps
Removing VLAN interfaces 1 through 4000
Done deleting 4000 VLAN interfaces in 61 seconds.

Going to add and remove 2 interfaces 1000 times.
Done adding/removing 2 VLAN interfaces 4000 times in 47 seconds.
74.05user 114.93system 3:33.00elapsed 88%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (2821122major+677782minor)pagefaults 0swaps


> 
> > Suppose I bind a raw socket to device vlan4001 (ie I have 4k in the list
> > before that one!!).  Currently, that means a linear search on all devices,
> > right?  In that extreme example, I would expect the hash to be very
> > useful.
> 
> Nope, it doesn't. Raw binding works via IP addresses, and the IP address resolution
> works via the routing table, which is extensively hashed.

Ahh, I meant raw, like raw Ethernet.  True, not used very often,
but I happen to have been using it lately :)

The original idea for the hashing came after I was severly chastised by a few
for even considering allowing 4000 VLAN Interfaces into the kernel.  The
complaint was that somehow having lots of devices was going to hurt performance.

The eventual conclusion (by me at least), was that there were no linear
lookups in any critical path I could think of.  However, things like
binding to interfaces, and searching for them (ifconfig -i vlan3999),
were doing (at least) linear searching, so hashing it might make the
user happier.

> 
> Packet socket binding or SO_BINDTODEVICE will search the list, but it is unlikely
> that these paths are worth optimizing for.

The patch has been written, so even if it helps just a little more than it
hurts, it might be worth including.  Of course, it may actually hurt more
than help.

I'd be very interested in lucid arguments as to why adding the patch would
actually be worse than not adding it, not just why I'm lame for considering
it *grin* :)

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

[-- Attachment #2: vlan_test.pl --]
[-- Type: application/x-perl, Size: 1510 bytes --]

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[David Ford]

On Sun, 7 Jan 2001, Chris Wedgwood wrote:
> Virtual IP interfaces in the form of ifname:<number> (e.g. eth:1) IMO
> should be deprecated and removed completely in 2.5.x. It's an ugly
> external wart that should be removed.
> 
> That said, if this was done -- how would things like routing daemons
> and bind cope? Actually, when I think about it they can't cope with
> situating like this now:
> 
> tapu:~# ip addr show lo
> 1: lo: <LOOPBACK,UP> mtu 3904 qdisc noqueue
>     link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
>     inet 127.0.0.1/8 scope host lo
>     inet 10.0.0.1/32 scope global lo

BIND copes just fine, how would it not?  I haven't heard any problems with
routing daemons either.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

[little bit OT] ip _IS_ _NOT_ ifconfig and route ! (was Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!))

[Henning P. Schmiedehausen]

davem@redhat.com (David S. Miller) writes:

>   Date:   Sat, 6 Jan 2001 23:00:10 -0500 (EST)
>   From: jamal <hadi@cyberus.ca>

>   I think someone should just flush ifconfig down some toilet. a wrapper
>   around "ip" to to give the same look and feel as ifconfig would be a good
>   thing so that some stupid program that depends on ifconfig look and feel
>   would be a good start.

>I could not agree more.  This reminds me to do something I could not
>justify before, making netlink be enabled in the kernel and
>non-configurable.

The fact there there are no man pages, no backward compatibility and
no information for people coming from other unixes (and pretty much
everything else _has_ ifconfig and friends), that iproute does not
work with older kernels, that everyone that reads the docs and looks
for ifconfig and that booting another kernel completely breaks your ip
configuration (which is, in the times of co-located, headless servers
some 3,000 miles away somehow a concern to administrators and users)
should IMNSVHO count at least a little towards keeping the older
tools.

As long as "man ip" on my machines returns "ip(7) - ip - Linux IPv4
protocol implementation", using "ip" exclusively instead of ifconfig
and route is IMHO not an option for anyone else than bleeding edge
hackers and linux gurus.

ip is an ultra-powerful command for the linux ip routing
subsystem. But at least IMHO it introduces so many new and different
concepts that there should be an "ip_lite" config command that at
least related semantically to the ifconfig/route/arp combo, so that
you can tell newbies (and I consider in this case people with 10+
years of Solaris experience as "linux routing command newbies") that

ifconfig eth0 ----> ip link show eth0

and so on. Give a small command with a small man page for these
"normal" cases and give all-powerful "ip" for all the cool, advanced
stuff.

Maybe the major distribution vendors should pay a decent technical
writer to work with Alexey to whip up man pages for these tools. There
are none in the iproute-current package (I looked) which contains all
the informations in an unix-compatible format. 

And yes, I don't consider HTML, tex, texinfo or info or (horrors) PS
and PDF format "decent documentation", Unix-style wise. At least as
long as we don't have a man command that understands HTML like Solaris
man does.

yes, it _is_ cool to type "ip route show" and pretend to be on level
with Cisco. But where is the documentation to _parse_ the displayed
information aside from reading lots of mailing list articles and code?
And don't tell me it's in the docs in the package. There is a
reference with at best terse examples. 

To quote a randomly picked part (p.25):

--- cut ---
scope SCOPE_VAL

- scope of the destinations covered by the route prefix. SCOPE_VAL may
  be a number or a string from the file /etc/iproute2/rt_scopes. If
  this parameter is omitted, ip assumes scope global for all gatewayed
  unicast routes, scope link for direct unicast routes and broadcasts
  and scope host for local routes.

--- cut ---

% ip route show
192.168.2.4 dev eth0  scope link 
192.168.2.0/24 dev eth0  proto kernel  scope link  src 192.168.2.4 
127.0.0.0/8 dev lo  scope link 
default via 192.168.2.1 dev eth0 

fine. Why is the last route (which is IMHO a gatewayed unicast route)
not

0.0.0.0/0 vial 192.168.2.1 dev eth0 scope global

?

In fact it behaves like this:

% ip route show scope global
default via 192.168.2.1 dev eth0 

I didn't find any "the default route is displayed different and scope
global is normally omitted" in the documentation. And the list goes
on.

And, please, convert all this "link" "route" "show" with abreviations
and abiguities into either getopt "-l" "-r" "s" or long_getopts
"--link" "--route" "--show" command line options. Why? Easy: consider

link == "-t link"   and show == "-s"

then

"ip -t link -s"  yields the same result as "ip -s -t link"

but

% ip link show
1: lo: <LOOPBACK,UP> mtu 3924 qdisc noqueue 
    link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
2: eth0: <BROADCAST,MULTICAST,UP> mtu 1500 qdisc pfifo_fast qlen 100
    link/ether 00:50:04:48:b9:f0 brd ff:ff:ff:ff:ff:ff
% ip show link
Object "show" is unknown, try "ip help".

any further questions? If you write scripts where you push your
arguments on a stack and then do a " join arguments into line, execute
line", having position independend argument order is a clear win over
every syntactic sugar. But then again, it is a real world use.

	Regards
		Henning
-- 
Dipl.-Inf. (Univ.) Henning P. Schmiedehausen       -- Geschaeftsfuehrer
INTERMETA - Gesellschaft fuer Mehrwertdienste mbH     hps@intermeta.de

Am Schwabachgrund 22  Fon.: 09131 / 50654-0   info@intermeta.de
D-91054 Buckenhof     Fax.: 09131 / 50654-20   
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [little bit OT] ip _IS_ _NOT_ ifconfig and route ! (was Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!))

[David S. Miller]

   Date: 	Sun, 7 Jan 2001 11:40:10 +0000 (UTC)
   From: "Henning P. Schmiedehausen" <hps@tanstaafl.de>

   As long as "man ip" on my machines returns "ip(7) - ip - Linux IPv4
   protocol implementation", using "ip" exclusively instead of
   ifconfig and route is IMHO not an option for anyone else than
   bleeding edge hackers and linux gurus.

As long as "man printf" gives me that damn shell command manpage, I
will not use printf in my C applications. :-))))  Yes, I do
understand, "ip" needs some more documentation perhaps.

Nobody has suggested getting rid of ifconfig, rather we have suggested
to implement it in terms of "ip" because, as you even mention, "ip" is
powerful and can do everything ifconfig can do thus ifconfig can be
implemented as a wrapper on top of "ip".

Nobody has suggested to use "ip" exclusively, you will not invoke "ip"
with the suggestion I am making.  Ifconfig indirectly will, but you
won't even notice nor should you care.  They will be packaged
together, so even that won't be an issue.

Later,
David S. Miller
davem@redhat.com
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[David S. Miller]

   Date:   Mon, 8 Jan 2001 01:13:08 +1300
   From: Chris Wedgwood <cw@f00f.org>

   OK, I'm a liar -- bind does handle this. Cool.

Standard BSD allows it, what do you expect :-)

   This is good news, because it means there is a precedent for multiple
   addresses on a single interface so we can kill the <ifname>:<n>
   syntax in favor of the above which is cleaner of more accurately
   represents what is happening.

If this is really true, 2.5.x is an appropriate time to make
this, no sooner.

Later,
David S. Miller
davem@redhat.com
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[Chris Wedgwood]

On Sun, Jan 07, 2001 at 02:22:31AM -0800, David Ford wrote:

    BIND copes just fine, how would it not?  I haven't heard any
    problems with routing daemons either.

Bind knows about multiple virtual interfaces; but we can also have
multiple addresses on a single interface and have no virtual
interfaces at all.

I doubt bind knows about this nor handles it.

<pause>

OK, I'm a liar -- bind does handle this. Cool.

Jan  8 01:09:12 tapu named[599]: listening on [127.0.0.1].53 (lo)
Jan  8 01:09:12 tapu named[599]: listening on [10.0.0.1].53 (lo)
Jan  8 01:09:12 tapu named[599]: listening on [x.x.x.x].53 (x0)
Jan  8 01:09:12 tapu named[599]: Forwarding source address is [0.0.0.0].1032

This is good news, because it means there is a precedent for multiple
addresses on a single interface so we can kill the <ifname>:<n>
syntax in favor of the above which is cleaner of more accurately
represents what is happening.



  --cw
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[David Ford]

On Mon, 8 Jan 2001, Chris Wedgwood wrote:
> Bind knows about multiple virtual interfaces; but we can also have
> multiple addresses on a single interface and have no virtual
> interfaces at all.
> 
> I doubt bind knows about this nor handles it.
> 
> <pause>
> 
> OK, I'm a liar -- bind does handle this. Cool.
> 
> Jan  8 01:09:12 tapu named[599]: listening on [127.0.0.1].53 (lo)
> Jan  8 01:09:12 tapu named[599]: listening on [10.0.0.1].53 (lo)
> Jan  8 01:09:12 tapu named[599]: listening on [x.x.x.x].53 (x0)
> Jan  8 01:09:12 tapu named[599]: Forwarding source address is [0.0.0.0].1032
> 
> This is good news, because it means there is a precedent for multiple
> addresses on a single interface so we can kill the <ifname>:<n>
> syntax in favor of the above which is cleaner of more accurately
> represents what is happening.

I've been using the new form for a long long time now and I assure you, BIND
hasn't had any problems with it for a long long time. :)

BIND as most all programs, should not care what the interface is or how it
is laid out.  It binds to an address and port and shouldn't care otherwise.

Would I really put you in a quandry if I told you I had multiple different
media interfaces all with the same IP and BIND happily answered on all of
them? ;)

-d


--
---NOTICE--- fwd: fwd: fwd: type emails will be deleted automatically.
      "There is a natural aristocracy among men. The grounds of this are
      virtue and talents", Thomas Jefferson [1742-1826], 3rd US President

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Alan Cox]

> + *      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

It makes a lot of difference tha the vlan goes 2nd. Most sane people wont
have vlans active on a high load interface.

>  			strcpy(dev->name, buf);
>  			return i;
>  		}
>  	}
> -	return -ENFILE;	/* Over 100 of the things .. bail out! */
> +	return -ENFILE;	/* Over 8192 of the things .. bail out! */

So fix the algorithm. You want the list sorted at this point, or to generate
a bitmap of free/used entries and scan the list then scan the map

Question: How do devices with hardware vlan support fit into your model ?

Alan

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Alan Cox]

>    thing so that some stupid program that depends on ifconfig look and feel
>    would be a good start.
> 
> I could not agree more.  This reminds me to do something I could not
> justify before, making netlink be enabled in the kernel and
> non-configurable.

Why. Its bad enough that the networking layer doesnt let you configure out
stuff like SACK and the big routing hashes. Please don't make it even worse
for the embedded world. 99.9% of Linux boxes probably have less than 5 routing
table entries

> I could almost, but not quite, justify it right now just because "ip"
> is becomming standard and needs it.

ip is also not the smallest and simplest of binaries. You can fit an ifconfig
for ip in about 24K
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Alan Cox]

> Suppose I bind a raw socket to device vlan4001 (ie I have 4k in the list
> before that one!!).  Currently, that means a linear search on all devices,
> right?  In that extreme example, I would expect the hash to be very
> useful.

At this point you have to ask 'why is vlan4001 an interface'. Would it not
be cleaner to add the vlan id to the entries in the list of addresses per
interface ?

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Matti Aarnio]

On Sun, Jan 07, 2001 at 01:42:50PM +0000, Alan Cox wrote:
> > + *      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
> 
> It makes a lot of difference tha the vlan goes 2nd. Most sane people wont
> have vlans active on a high load interface.

	VLAN tag header appears as Layer-3 protocol, which then
	causes loop into VLAN reception code and back to generic
	Layer-3 receiver.

	I just tried to pull data from another machine, which
	is on normal port thru VLAN trunking port to receiving
	machine, and got fast-ether at wire speed. (As near as
	ncftp's 11.11 MB/sec is wirespeed..)

> So fix the algorithm. You want the list sorted at this point, or to generate
> a bitmap of free/used entries and scan the list then scan the map
> 
> Question: How do devices with hardware vlan support fit into your model ?

	Hardware VLAN support at several network cards is just
	to recognize VLAN tags, and then do the right thing
	( = skip 4 bytes ) when doing TCP/UDP checksum.

> Alan

/Matti Aarnio
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[jamal]

On Sat, 6 Jan 2001, David S. Miller wrote:

> I could not agree more.  This reminds me to do something I could not
> justify before, making netlink be enabled in the kernel and
> non-configurable.

I always use netlink and friends for something or the other. Route
protocols, traffic control configuration, device configuration,
firewalling; I dont see a problem turning it on. Maybe defaulting it to
on, and then totaly getting rid of the config option.

> I could almost, but not quite, justify it right now just because "ip"
> is becomming standard and needs it.

"ip" has been standard to some people for a few moons now ;->
It is more documneted than ifconfig ;-> and does a lot more

>
>    Not to stray from the subject, Ben's effort is still needed. I think real
>    numbers are useful instead of claims like it "displayed faster"
>
> See my previous email, if it's just slow because of some poorly coded
> version of ifconfig, it does not justify the patch.  If only a
> forcefully created "benchmark" can show some performance problem, that
> is not an acceptable reason to champion this patch.  Ok?
>

True.
All the kernel paths affected are really config/control paths as well as
slow paths (eg some device binding to sockets, MSG_DONTROUTE slow path,
traffic control setup, route config, arp config are some that seem useful).

The argumenet for the patch (and it might be weak) If you have 4000
devices, it makes sense for two reasons:
-Some of these paths might hold locks which might stall the fast path.
-Or if you have a busy system, they will contribute to the load.

I used to be against VLANS being devices, i am withdrawing that comment; it's
a lot easier to look on them as devices if you want to run IP on them. And
in this case, it makes sense the possibilirt of  over a thousand devices
is good.

So instead of depending what ifconfig does, maybe a better test for Ben is
to measure the kernel level improvement in the lookup for example from
2..6000 devices. Tests with the user space tools will also help. example
to add to Andi's flavor:
"date; time ifconfig -a; date" for each number of devices.
repeat for ip as well ;->
Plot kernel and the two user tools results after several iterations
(number of devices on x-axis and some time/CPU measure on y-axis).

cheers,
jamal




-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[jamal]

On Sun, 7 Jan 2001, Alan Cox wrote:

> Why. Its bad enough that the networking layer doesnt let you configure out
> stuff like SACK and the big routing hashes. Please don't make it even worse
> for the embedded world. 99.9% of Linux boxes probably have less than 5 routing
> table entries

Ok. Good point.
But remember that parsing /proc for an embedded system is also not the
most healthy thing.

>
> > I could almost, but not quite, justify it right now just because "ip"
> > is becomming standard and needs it.
>
> ip is also not the smallest and simplest of binaries. You can fit an ifconfig
> for ip in about 24K
>

ip is also a replacement of many nettools: ifconfig, route, arp config,
tunneling setup etc. You can also do many funky things with it using
small scripts (ip dup-address detection is documented).
Seems like Alexey already has a wrapper "ifcfg" which is a ifconfig
replacement. It does not format display the same way as ifconfig; however,
that would only be necessary if some app is dependent on ifconfig output.

cheers,
jamal

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[Gleb Natapov]

On Sun, Jan 07, 2001 at 10:56:23AM -0500, jamal wrote:
[snip]
> 
> I used to be against VLANS being devices, i am withdrawing that comment; it's
> a lot easier to look on them as devices if you want to run IP on them. And
> in this case, it makes sense the possibilirt of  over a thousand devices
> is good.
>

Glad to hear :) So perhaps this is a good time to move one of VLAN implementations
into the official kernel?

--
			Gleb.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[jamal]

On Sun, 7 Jan 2001, Gleb Natapov wrote:

> > I used to be against VLANS being devices, i am withdrawing that comment; it's
> > a lot easier to look on them as devices if you want to run IP on them. And
> > in this case, it makes sense the possibilirt of  over a thousand devices
> > is good.
> >
>
> Glad to hear :) So perhaps this is a good time to move one of VLAN implementations
> into the official kernel?
>

Absolutely.
I think we need a VLAN implementation in there.

cheers,
jamal


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Miquel van Smoorenburg]

In article <E14FGD4-0002f7-00@the-village.bc.nu>,
Alan Cox  <alan@lxorguk.ukuu.org.uk> wrote:
>At this point you have to ask 'why is vlan4001 an interface'. Would it not
>be cleaner to add the vlan id to the entries in the list of addresses per
>interface ?

Not all the world is IP - what if you want to bridge between 
an ATM ELAN (LANE) and a VLAN? Note that different ATM ELANs also
show up as seperate interfaces.

Mike.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Alan Cox]

> 	I just tried to pull data from another machine, which
> 	is on normal port thru VLAN trunking port to receiving
> 	machine, and got fast-ether at wire speed. (As near as
>	ncftp's 11.11 MB/sec is wirespeed..)

But talking between two vlans on the same physical lan you will go in and back
out via the switch and you wont
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Alan Cox]

> Ok. Good point.
> But remember that parsing /proc for an embedded system is also not the
> most healthy thing.

I dont compile in /proc either. SIOCGIFCONF is enough for an embedded box.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[jamal]

On Sun, 7 Jan 2001, Chris Wedgwood wrote:

> That said, if this was done -- how would things like routing daemons
> and bind cope?

I dont know of any routing daemons that are taking advantage of the
alias interfaces today. This being said, i think that the fact that a
lot of protocols that need IP-ization are coming up eg VLANs; you should
see a good use for this. Out of curiosity for the VLAN people, how do you
work with something like Zebra?
One could have the route daemon take charge of management of these
devices, a master device like "eth0" and a attached device like "vlan0".
They both share the same ifindex but different have labels.
Basically, i dont think there would be a problem.

cheers,
jamal



-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Matti Aarnio]

On Sun, Jan 07, 2001 at 04:46:14PM +0000, Alan Cox wrote:
> But talking between two vlans on the same physical lan you will go in and back
> out via the switch and you wont

  So ?

  If your box is routing in between VLANs, you are using it wrong way, IMO.

  On the other hand, I could very well put clients in some building into
  an set where I have a switch with FE connection to router, and lots of
  10BaseT ports to clients.  Hard-limiting bandwith to said 10 Mbit.

  I use VLAN truncked systems mainly for network administration, for
  DHCP servers.

/Matti Aarnio
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[Gleb Natapov]

On Sun, Jan 07, 2001 at 11:56:26AM -0500, jamal wrote:
> 
> 
> On Sun, 7 Jan 2001, Chris Wedgwood wrote:
> 
> > That said, if this was done -- how would things like routing daemons
> > and bind cope?
> 
> I dont know of any routing daemons that are taking advantage of the
> alias interfaces today. This being said, i think that the fact that a
> lot of protocols that need IP-ization are coming up eg VLANs; you should
> see a good use for this. Out of curiosity for the VLAN people, how do you
> work with something like Zebra?

Without any problems. Zebra sees different VLAN interfaces as different networks
and happily route between them.

> One could have the route daemon take charge of management of these
> devices, a master device like "eth0" and a attached device like "vlan0".
> They both share the same ifindex but different have labels.
> Basically, i dont think there would be a problem.
>

Theoretically it seems to be possible but it's much harder to do in Zebra than 
in kernel. And "eth0" shouldn't share ifindex with "vlan0" I don't think SNMP
will be happy about that.

--
			Gleb.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

routable interfaces WAS( Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[jamal]

On Sun, 7 Jan 2001, Gleb Natapov wrote:

> > One could have the route daemon take charge of management of these
> > devices, a master device like "eth0" and a attached device like "vlan0".
> > They both share the same ifindex but different have labels.
> > Basically, i dont think there would be a problem.
> >
>
> Theoretically it seems to be possible but it's much harder to do in Zebra than
> in kernel. And "eth0" shouldn't share ifindex with "vlan0" I don't think SNMP
> will be happy about that.

A very good reason why you would want them to have separate ifindices.
Essentially, vlans have to be separate interfaces today. Other "virtual"
interfaces such as aliased devices are not going to work with route
daemons today since they dont meet this requirement.

Not to rain on Ben's parade but:
My thought was to have the vlan be attached on the interface ifa list and
just give it a different label since it is a "virtual interface" on top
of the "physical interface". Now that you mention the SNMP requirement,
maybe an idea of major:minor ifindex makes sense. Say make the ifindex
a u32 with major 16 bit and minor 16 bit. This way we can have upto 2^16
physical interfaces and upto 2^16 virtual interfaces on the physical
interface. The search will be broken into two 16 bits.

Thoughts?

cheers,
jamal

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Alan Cox]

> Um, what about people running their box as just a VLAN router/firewall?
> That seems to be one of the principle uses so far.  Actually, in that case
> both VLAN and IP traffic would come through, so it would be a tie if VLAN
> came first, but non-vlan traffic would suffer worse.

Why would someone filter between vlans when any node on each vlan can happily
ignore the vlan partitioning

> So, how can I make sure that it is second in the list?

Register vlan in the top level protocol hash then have that yank the header
and feed the packets through the hash again.

> Actually, VLAN code no longer uses this method to generate it's name,
> it uses it's own mechanism (which, by the way, the hashed name lookup
> makes much faster.)  So, this part of the patch can be removed.

Ok

> > Question: How do devices with hardware vlan support fit into your model ?
> I don't know of any, and I'm not sure how they would be supported.

Several cards have vlan ability, but Matti reports they just lose the header
not filter on it if I understood him

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[jamal]

On Sun, 7 Jan 2001, Ben Greear wrote:

> > Question: How do devices with hardware vlan support fit into your model ?
>
> I don't know of any, and I'm not sure how they would be supported.
>

erm, this is a MUST. You MUST factor the hardware VLANs and be totaly
802.1q compliant. Also of interest is 802.1P and D. We must have full
compliance, not some toy emulation.

cheers,
jamal

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: routable interfaces WAS( Re: [PATCH] hashed device lookup (DoesNOT meet Linus' sumission policy!)

[jamal]

On Sun, 7 Jan 2001, Ben Greear wrote:

> > My thought was to have the vlan be attached on the interface ifa list and
> > just give it a different label since it is a "virtual interface" on top
> > of the "physical interface". Now that you mention the SNMP requirement,
> > maybe an idea of major:minor ifindex makes sense. Say make the ifindex
> > a u32 with major 16 bit and minor 16 bit. This way we can have upto 2^16
> > physical interfaces and upto 2^16 virtual interfaces on the physical
> > interface. The search will be broken into two 16 bits.
>
> What problem does this fix?
>
> If you are mucking with the ifindex, you may be affecting many places
> in the rest of the kernel, as well as user-space programs which use
> ifindex to bind to raw devices.
>

I am talking about 2.5 possibilities now that 2.4 is out. I think
"parasitic/virtual" interfaces is not a issue specific to VLANs.
VLANs happen to use devices today to solve the problem.
As pointed by that example no routing daemons are doing aliased
interfaces (which are also virtual interfaces).
We need some more general solution.

cheers,
jamal

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Alan Cox]

> Thats what it already does, if I understand correctly.  Of course, if VLAN
> is loaded as a module, then it will be in the hash before IP, right?

Thats fine. I think it'll be a different hash bucket anyway. The point of
having vlan first is that if its not registered or the interface isnt doing
vlan there is basically a zero overhead
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: routable interfaces WAS( Re: [PATCH] hashed device lookup (DoesNOT meet Linus' sumission policy!)

[Gleb Natapov]

On Sun, Jan 07, 2001 at 01:29:51PM -0500, jamal wrote:
> 
> 
> On Sun, 7 Jan 2001, Ben Greear wrote:
> 
> > > My thought was to have the vlan be attached on the interface ifa list and
> > > just give it a different label since it is a "virtual interface" on top
> > > of the "physical interface". Now that you mention the SNMP requirement,
> > > maybe an idea of major:minor ifindex makes sense. Say make the ifindex
> > > a u32 with major 16 bit and minor 16 bit. This way we can have upto 2^16
> > > physical interfaces and upto 2^16 virtual interfaces on the physical
> > > interface. The search will be broken into two 16 bits.
> >
> > What problem does this fix?
> >
> > If you are mucking with the ifindex, you may be affecting many places
> > in the rest of the kernel, as well as user-space programs which use
> > ifindex to bind to raw devices.
> >
> 
> I am talking about 2.5 possibilities now that 2.4 is out. I think
> "parasitic/virtual" interfaces is not a issue specific to VLANs.
> VLANs happen to use devices today to solve the problem.
> As pointed by that example no routing daemons are doing aliased
> interfaces (which are also virtual interfaces).
> We need some more general solution.
>

And what about bonding device? What major number should they use? 

Ifindexes not reusable so in your scheme we should have separate minor 
counter for each major interface, what for?

--
			Gleb.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Matti Aarnio]

On Sun, Jan 07, 2001 at 06:06:37PM +0000, Alan Cox wrote:
> > Um, what about people running their box as just a VLAN router/firewall?
> > That seems to be one of the principle uses so far.  Actually, in that case
> > both VLAN and IP traffic would come through, so it would be a tie if VLAN
> > came first, but non-vlan traffic would suffer worse.
> 
> Why would someone filter between vlans when any node on each vlan can happily
> ignore the vlan partitioning

	VLANs are Level-2, that is SWITCHING.

	They have no real meaning unless you have a switching fabric,
	in which they present ways to hard-partition ports to different
	switching domains without having physically separate cabling.

	Normal hosts are connected on non-truncking ports, and only some
	rare systems are connected to 802.1Q trunks so they can access
	multiple VLANs inside the fabric.

	No ordinary hosts are able to choose at which VLANs they are.
	Truncking ports have ways to control which VLANs are allowed
	to go thru them (at least at Cisco hardware I am familiar with).

> > So, how can I make sure that it is second in the list?
> 
> Register vlan in the top level protocol hash then have that yank the header
> and feed the packets through the hash again.

	That is what the two existing VLAN codes for Linux do now.

	Better(?) way could be to have a way to have device specific
	reception vector in addition to xmit vector.  That way we could
	stack "Layer-2 protocols", like 802.1Q and (to an extent) even
	802 bridging.

	See  ftp://zmailer.org/linux/netif_rx.patch

	After all, if you have a way to plumb reception to an optional
	bridging layer, you propably would not need netif_rx() contained
	bridging code.

> > > Question: How do devices with hardware vlan support fit into your model ?
> > I don't know of any, and I'm not sure how they would be supported.
> 
> Several cards have vlan ability, but Matti reports they just lose the header
> not filter on it if I understood him

	No you didn't understand.

	Nothing is lost, it relates to hardware assisted received
	IP frame TCP/UDP checksumming by the network cards.  Some
	cards support that, some support it even in presense of
	802.1Q TAG header.

	I don't yet see any cards which have hardware assist for
	IPv6 checksumming.  VLAN tags or not.

	Reception must handle at first tearing off the VLAN header
	when receiving the frame, then return back to  netif_rx()
	to see what was inside - SNAP frame, IPv4 frame, whatever.

/Matti Aarnio
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[jamal]

On Sun, 7 Jan 2001, Ben Greear wrote:
> jamal wrote:
> >
> > erm, this is a MUST. You MUST factor the hardware VLANs and be totaly
> > 802.1q compliant. Also of interest is 802.1P and D. We must have full
> > compliance, not some toy emulation.
>
> I have seen neither hardware nor spec sheets on how these NICs are doing
> VLAN 'support'.  So, I don't know what the best way to support them is.
>

Most of the GIGe interfaces do provide VLAN insertion/removal. You
pass/receive it as part of the DMA descriptor.

> If it requires driver changes, then the ethernet driver folks will need
> to be involved.
>

I think the design MUST consider not just a poor man's VLAN way of
doing things. You and the other VLAN folks (Gleb and co) will have to iron
that out. Basically, all i am saying is that if there is going to be a
linux solution at some point, the requirement for these devices is a MUST.
Please involve me in discussions you guys end up having.

> There is also a difference between supporting hardware VLAN solutions
> and being 100% compliant:  If I can send/receive packets that are
> 100% compliant from an RTL 8139 NIC, then as far as the world (ie Switch) knows,
> I am 100% compliant.
>

ok.

> If the specific VLAN hardware features are not supported in some exotic
> NIC, then that should just mean slightly less performance, or worst cast,
> not supporting that particular NIC.

The included design must be flexible enough to allow for this. As much as
i hate it, some vendors will continue releasing binaries only for their
code.

>
> My vlan code supports setting of Priority bits already (thats' the .1P, right?)
>

right. There's a lot of work to be done in that area.

> What is the .1D stuff about?
>

spanning tree. Seems the bridging code already does this.

cheers,
jamal

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Matti Aarnio]

On Sun, Jan 07, 2001 at 01:21:11PM -0500, jamal wrote:
> On Sun, 7 Jan 2001, Ben Greear wrote:
> > > Question: How do devices with hardware vlan support fit into your model ?
> > I don't know of any, and I'm not sure how they would be supported.
> 
> erm, this is a MUST. You MUST factor the hardware VLANs and be totaly
> 802.1q compliant. Also of interest is 802.1P and D. We must have full
> compliance, not some toy emulation.

	Read what I wrote about the issue to Alan.
	Ben's code has no problems with receiving VLANs with network
	cards which have "hardware support" for VLANs.

	But this is far away from device name hashes.
	(Which aren't in data reception or sending fastpaths, anyway.)

> cheers,
> jamal

/Matti Aarnio
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Ben Greear]

Alan Cox wrote:
> 
> > + *      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
> 
> It makes a lot of difference tha the vlan goes 2nd. Most sane people wont
> have vlans active on a high load interface.

Um, what about people running their box as just a VLAN router/firewall?
That seems to be one of the principle uses so far.  Actually, in that case
both VLAN and IP traffic would come through, so it would be a tie if VLAN
came first, but non-vlan traffic would suffer worse.

So, how can I make sure that it is second in the list?

> 
> >                       strcpy(dev->name, buf);
> >                       return i;
> >               }
> >       }
> > -     return -ENFILE; /* Over 100 of the things .. bail out! */
> > +     return -ENFILE; /* Over 8192 of the things .. bail out! */
> 
> So fix the algorithm. You want the list sorted at this point, or to generate
> a bitmap of free/used entries and scan the list then scan the map

Actually, VLAN code no longer uses this method to generate it's name,
it uses it's own mechanism (which, by the way, the hashed name lookup
makes much faster.)  So, this part of the patch can be removed.

> 
> Question: How do devices with hardware vlan support fit into your model ?

I don't know of any, and I'm not sure how they would be supported.

> 
> Alan

-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: routable interfaces WAS( Re: [PATCH] hashed device lookup (DoesNOT meet Linus' sumission policy!)

[jamal]

On Sun, 7 Jan 2001, Gleb Natapov wrote:

> And what about bonding device? What major number should they use?

Would that include several ifindeces?
use standards. 802.3ad(?). Didnt Intel release some code on this or
are they still playing the big bad corporation? Normaly standards will
take care of things like MIBs etc.

> Ifindexes not reusable so in your scheme we should have separate minor
> counter for each major interface, what for?

Still each "interface" has its own ifindex, so counters will be
per-interface.
Here's what i mean:

netdevice (major part of ifindex, proto unaware link layer)
	|
	|
	--> protocol level (IPV4, V6 etc)
             | ..........|
             |           |--> interface 2^16
             |
              -->interface 1

The interface could be looked as something on top of a device (struct
ifa) and is distinguishable on the device by its minor number. EG
ifindex 1002 is eth0:2.
I could write a whole lengthy RFC if it is of interest and we could
use that as a starting point for discussion.
Note, i dont think this would affect the core code other than the setup
part.

cheers,
jamal


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Ben Greear]

Alan Cox wrote:
> 
> > Suppose I bind a raw socket to device vlan4001 (ie I have 4k in the list
> > before that one!!).  Currently, that means a linear search on all devices,
> > right?  In that extreme example, I would expect the hash to be very
> > useful.
> 
> At this point you have to ask 'why is vlan4001 an interface'. Would it not
> be cleaner to add the vlan id to the entries in the list of addresses per
> interface ?

Among other things, some VLAN switches won't work unless you can change
the MAC address on your VLANs to be different from the rest of the
VLAN MACs on that physical interface.  For OSPF you also need to
have multicast work on them, and other things that look very much like
a real interface.

Also, by making the VLANs a net_device, the rest of the kernel and
user-space code (ip, ifconfig, for example), works as expected, with
no changes.

-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[jamal]

On Sun, 7 Jan 2001, Matti Aarnio wrote:

> 	Read what I wrote about the issue to Alan.
> 	Ben's code has no problems with receiving VLANs with network
> 	cards which have "hardware support" for VLANs.
>

OK. I suppose an skb->vlan_tag is passed to the driver and it will know
what to do with it (pass it on a descriptor etc).

cheers,
jamal

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: routable interfaces WAS( Re: [PATCH] hashed device lookup(DoesNOT meet Linus' sumission policy!)

[Sandy Harris]

jamal wrote:

> > What problem does this fix?
> >
> > If you are mucking with the ifindex, you may be affecting many places
> > in the rest of the kernel, as well as user-space programs which use
> > ifindex to bind to raw devices.
>
> I am talking about 2.5 possibilities now that 2.4 is out. I think
> "parasitic/virtual" interfaces is not a issue specific to VLANs.
> VLANs happen to use devices today to solve the problem.
> As pointed by that example no routing daemons are doing aliased
> interfaces (which are also virtual interfaces).
> We need some more general solution.
> 
Something like this also becomes an issue when you want routing
daemons to interact sensibly with IPSEC tunnels. A paper on these
issues is at:

http://www.quintillion.com/fdis/moat/ipsec+routing/

It is not (AFAIK) clear that the FreeS/WAN team will adopt the solutions
suggested there, but it is very clear we need to deal with those issues.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: routable interfaces WAS( Re: [PATCH] hashed device lookup (DoesNOT meet Linus' sumission policy!)

[Ben Greear]

jamal wrote:

> A very good reason why you would want them to have separate ifindices.
> Essentially, vlans have to be separate interfaces today. Other "virtual"
> interfaces such as aliased devices are not going to work with route
> daemons today since they dont meet this requirement.
> 
> Not to rain on Ben's parade but:
> My thought was to have the vlan be attached on the interface ifa list and
> just give it a different label since it is a "virtual interface" on top
> of the "physical interface". Now that you mention the SNMP requirement,
> maybe an idea of major:minor ifindex makes sense. Say make the ifindex
> a u32 with major 16 bit and minor 16 bit. This way we can have upto 2^16
> physical interfaces and upto 2^16 virtual interfaces on the physical
> interface. The search will be broken into two 16 bits.

What problem does this fix?

If you are mucking with the ifindex, you may be affecting many places
in the rest of the kernel, as well as user-space programs which use
ifindex to bind to raw devices.

On the other hand, the hash patch touches only one file, and should
not have any external impacts.

> 
> Thoughts?
> 
> cheers,
> jamal

-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Matti Aarnio]

On Sun, Jan 07, 2001 at 02:10:52PM -0500, jamal wrote:
> On Sun, 7 Jan 2001, Matti Aarnio wrote:
> > 	Read what I wrote about the issue to Alan.
> > 	Ben's code has no problems with receiving VLANs with network
> > 	cards which have "hardware support" for VLANs.
> 
> OK. I suppose an skb->vlan_tag is passed to the driver and it will know
> what to do with it (pass it on a descriptor etc).

	Sure, nice.  WHY SHOULD THERE BE MORE LAYER-2 STUFF ADDED TO
	SKB OBJECTS ?

	One of important abstraction issues is to isolate device specific
	new things (like what VLAN/PVC/SVC is used at your favourtite
	802.1Q/ATM/X.25/FrameRelay connection).

	The less we leak that kind of things to SKB, the better, IMO.
	They are net_device issues, after all.

	Tell me (if you can), why packet sender calls hardware-header
	generation for packet, if the card can insert it for you ?
	Consider the structure of Ethernet MAC header, where is source
	address ?  Where is the destination address ?  If you write the
	destination, why should you not write the source there too ?

	No doubt some cards can fill in the source address while doing
	frame transmit, but is it worth the hazzle ?

> cheers,
> jamal

/Matti Aarnio
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Ben Greear]

Alan Cox wrote:
> 
> > Um, what about people running their box as just a VLAN router/firewall?
> > That seems to be one of the principle uses so far.  Actually, in that case
> > both VLAN and IP traffic would come through, so it would be a tie if VLAN
> > came first, but non-vlan traffic would suffer worse.
> 
> Why would someone filter between vlans when any node on each vlan can happily
> ignore the vlan partitioning

Suppose you have a 100bt link upstream, and want to re-sell that as 10 10Mb
links to all the customers in one building.  With VLANs, you can
haul all the data over one wire to a Linux box with 11 interfaces: 1 running
VLAN (100bt), and 10 others running 10bt ethernet.  Now, your uses are
segregated, and you only have 1 100bt wire running to the basement, instead
of 10.

Alternately, if you have a VLAN ethernet switch, your linux box just feeds
100bt into it, and acts as a router with 10 (vlan) interfaces.

In either of these cases, assuming the etherswitch and/or Linux box is secure,
the customers will not be able to be on other peoples VLAN.  This enables
all kinds of routing/billing possibilities...

> > So, how can I make sure that it is second in the list?
> 
> Register vlan in the top level protocol hash then have that yank the header
> and feed the packets through the hash again.

Thats what it already does, if I understand correctly.  Of course, if VLAN
is loaded as a module, then it will be in the hash before IP, right?


-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Ben Greear]

jamal wrote:
> 
> On Sun, 7 Jan 2001, Ben Greear wrote:
> 
> > > Question: How do devices with hardware vlan support fit into your model ?
> >
> > I don't know of any, and I'm not sure how they would be supported.
> >
> 
> erm, this is a MUST. You MUST factor the hardware VLANs and be totaly
> 802.1q compliant. Also of interest is 802.1P and D. We must have full
> compliance, not some toy emulation.

I have seen neither hardware nor spec sheets on how these NICs are doing
VLAN 'support'.  So, I don't know what the best way to support them is.

If it requires driver changes, then the ethernet driver folks will need
to be involved.

There is also a difference between supporting hardware VLAN solutions
and being 100% compliant:  If I can send/receive packets that are
100% compliant from an RTL 8139 NIC, then as far as the world (ie Switch) knows,
I am 100% compliant.

If the specific VLAN hardware features are not supported in some exotic
NIC, then that should just mean slightly less performance, or worst cast,
not supporting that particular NIC.

My vlan code supports setting of Priority bits already (thats' the .1P, right?)

What is the .1D stuff about?

> 
> cheers,
> jamal

-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumissionpolicy!)

[Ben Greear]

jamal wrote:

> So instead of depending what ifconfig does, maybe a better test for Ben is
> to measure the kernel level improvement in the lookup for example from
> 2..6000 devices.

In the benchmark I gave, the performance increase was in the kernel,
not user space, and it was more than 10 times faster, at least with 4k
VLANs.  Adding VLANs was about twice as fast, and deleting them was
faster, though not as much.

 Tests with the user space tools will also help. example
> to add to Andi's flavor:
> "date; time ifconfig -a; date" for each number of devices.
> repeat for ip as well ;->

I can show a range w/out much trouble.  I think I'll also tweak
the hash code to just do linear lookups if the number of interfaces
is below some number, (probably 20, or whatever the numbers show
is good...)

Ben

-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: routable interfaces WAS( Re: [PATCH] hashed device lookup(DoesNOT meet Linus' sumission policy!)

[Ben Greear]

Sandy Harris wrote:
> 
> jamal wrote:
> 
> > > What problem does this fix?
> > >
> > > If you are mucking with the ifindex, you may be affecting many places
> > > in the rest of the kernel, as well as user-space programs which use
> > > ifindex to bind to raw devices.
> >
> > I am talking about 2.5 possibilities now that 2.4 is out. I think
> > "parasitic/virtual" interfaces is not a issue specific to VLANs.
> > VLANs happen to use devices today to solve the problem.
> > As pointed by that example no routing daemons are doing aliased
> > interfaces (which are also virtual interfaces).
> > We need some more general solution.
> >
> Something like this also becomes an issue when you want routing
> daemons to interact sensibly with IPSEC tunnels. A paper on these
> issues is at:
> 
> http://www.quintillion.com/fdis/moat/ipsec+routing/
> 
> It is not (AFAIK) clear that the FreeS/WAN team will adopt the solutions
> suggested there, but it is very clear we need to deal with those issues.

Hrm, what if they just made each IP-SEC interface a net_device?  If they
are a routable entity, with it's own IP address, it starts to look a lot
like an interface/net_device.

This has seeming worked well for VLANs:  Maybe net_device is already
general enough??

So, what would be the down-side of having VLANs and other virtual interfaces
be net_devices?  The only thing I ever thought of was the linear lookups,
which is why I wrote the hash code.  The beauty of working with existing
user-space tools should not be over-looked!

It may be easier to fix other problems with many interface/net_devices
than cram a whole other virtual net_device structure (with many duplicate
functionalities found in the current net_device).

Ben

-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[5116]

On  7 Jan, Alan Cox wrote:
>> Um, what about people running their box as just a VLAN router/firewall?
>> That seems to be one of the principle uses so far.  Actually, in that case
>> both VLAN and IP traffic would come through, so it would be a tie if VLAN
>> came first, but non-vlan traffic would suffer worse.
> 
> Why would someone filter between vlans when any node on each vlan can happily
> ignore the vlan partitioning
> 
You might be connected to a vlan capable switch which will only feed the
`right' vlan to a certain port... In this case an one-armed firewall
might make sense.

/Daniel
-- 


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[jamal]

On Sun, 7 Jan 2001, Matti Aarnio wrote:

> On Sun, Jan 07, 2001 at 02:10:52PM -0500, jamal wrote:
> > OK. I suppose an skb->vlan_tag is passed to the driver and it will know
> > what to do with it (pass it on a descriptor etc).
>
> 	Sure, nice.  WHY SHOULD THERE BE MORE LAYER-2 STUFF ADDED TO
> 	SKB OBJECTS ?
>
> 	One of important abstraction issues is to isolate device specific
> 	new things (like what VLAN/PVC/SVC is used at your favourtite
> 	802.1Q/ATM/X.25/FrameRelay connection).
>
> 	The less we leak that kind of things to SKB, the better, IMO.
> 	They are net_device issues, after all.

You are right, the IP-ization information should be a "device" specific.
What "device" means is the other discussion [I think we need new naming
conventions and abstractions]

> 	Tell me (if you can), why packet sender calls hardware-header
> 	generation for packet, if the card can insert it for you ?
> 	Consider the structure of Ethernet MAC header, where is source
> 	address ?  Where is the destination address ?  If you write the
> 	destination, why should you not write the source there too ?
>

It doesnt cost that much to do in s/ware if it is contigous and you have
the information. some form of neighbor discovery  protocol gathers
all that info for you it is pretty cheap to insert the dst/src/etherype
which you already have.
Linux already has the 14 bytes link layer header cached today based on ARP
for example. Works very nicely on the transmit path.
Now consider trying to insert the VLAN header after all this work (it goes
between the src MAC and the ethertype). If the hardware knows what to do
with the tag, you dont need the hardware header rebuilder function.

cheers,
jamal

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: routable interfaces WAS( Re: [PATCH] hashed device lookup(DoesNOT meet Linus' sumission policy!)

[jamal]

On Sun, 7 Jan 2001, Ben Greear wrote:

> Hrm, what if they just made each IP-SEC interface a net_device?  If they
> are a routable entity, with it's own IP address, it starts to look a lot
> like an interface/net_device.

As in my response to Matti, i thing a netdevice is a generalized link
layer structure and should remain that way.
To add a new naming convention a "link" or maybe an "interface"
is what the protocol aware part should be.
Define a routable "interface" to be  one that (from an abstraction
perspective) sits on top of a netdevice and has a ifindex, name, and IP
address (v4 or V6)
I think the goals of the author of that IPSEC article are served with this
scheme. I need to read that article, i just schemed through it.

>
> This has seeming worked well for VLANs:  Maybe net_device is already
> general enough??

I think it is not proper to generalize netdevices for IP. I am not
thinking of dead protocols like IPX, more of other newer encapsulations
such as MPLS etc.

>
> So, what would be the down-side of having VLANs and other virtual interfaces
> be net_devices?  The only thing I ever thought of was the linear lookups,
> which is why I wrote the hash code.  The beauty of working with existing
> user-space tools should not be over-looked!
>

IP configuration tools you mean. Fine, they should be used to configure
"interfaces" in the way i defined them above.

> It may be easier to fix other problems with many interface/net_devices
> than cram a whole other virtual net_device structure (with many duplicate
> functionalities found in the current net_device).
>

It makes sense from an abstraction and management perspective to have all
virtual interfaces which run on top of a physical interface to be
managed in conjuction with the device. Device goes down, you destroy them
or send them to a shutdown state (instead of messaging) etc.

cheers,
jamal

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[David Ford]

[-- Attachment #1: Type: text/plain, Size: 449 bytes --]

Alan Cox wrote:

> > Um, what about people running their box as just a VLAN router/firewall?
> > That seems to be one of the principle uses so far.  Actually, in that case
> > both VLAN and IP traffic would come through, so it would be a tie if VLAN
> > came first, but non-vlan traffic would suffer worse.
>
> Why would someone filter between vlans when any node on each vlan can happily
> ignore the vlan partitioning

ports 137-139 blather.

-d


[-- Attachment #2: Card for David Ford --]
[-- Type: text/x-vcard, Size: 274 bytes --]

begin:vcard 
n:Ford;David
x-mozilla-html:TRUE
url:www.blue-labs.org
adr:;;;;;;
version:2.1
email;internet:david@blue-labs.org
title:Blue Labs Developer
note;quoted-printable:GPG key: http://www.blue-labs.org/david@nifty.key=0D=0A
x-mozilla-cpt:;9952
fn:David Ford
end:vcard

Re: routable interfaces WAS( Re: [PATCH] hashed device lookup(DoesNOTmeet Linus' sumission policy!)

[Ben Greear]

jamal wrote:
> 
> On Sun, 7 Jan 2001, Ben Greear wrote:
> 
> > Hrm, what if they just made each IP-SEC interface a net_device?  If they
> > are a routable entity, with it's own IP address, it starts to look a lot
> > like an interface/net_device.
> 
> As in my response to Matti, i thing a netdevice is a generalized link
> layer structure and should remain that way.

Yes, but VLANs are a link-layer structure too, and things like tunnels
are really link-layer too, as far as protocols using them are concerned.

With tunneling and virtual interfaces, you could conceivably do something
like:

OC3 - ATM - Ethernet - VLAN - IP - IP-Sec - IP
as well as plain old:
Ethernet - IP

Which of these are netdevices?

(I argue that at least the Ethernet-over-ATM, VLAN, and IP-Sec entities could
profit from being a net_device at it's core.)

You argue that we should split the net_device into physical and virtual portions.

Perhaps you could give an idea of the data members that would belong in the new
structures?  I argue that you lose the minute you need one in both structures :)

> > This has seeming worked well for VLANs:  Maybe net_device is already
> > general enough??
> 
> I think it is not proper to generalize netdevices for IP. I am not
> thinking of dead protocols like IPX, more of other newer encapsulations
> such as MPLS etc.

MPLS can run over FrameRelay, Ethernet, and ATM, at the moment (right?).

What if you want to run MPLS over an IP-Sec link?  If you want it to
magically work, IP-Sec could be a net_device with it's own particular
member methods and private data that let it do the right thing.

> > So, what would be the down-side of having VLANs and other virtual interfaces
> > be net_devices?  The only thing I ever thought of was the linear lookups,
> > which is why I wrote the hash code.  The beauty of working with existing
> > user-space tools should not be over-looked!
> >
> 
> IP configuration tools you mean. Fine, they should be used to configure
> "interfaces" in the way i defined them above.

Think also of creating sockets with SOCK_RAW and other lower-level
(but user-space) access to the net_device's methods.

> It makes sense from an abstraction and management perspective to have all
> virtual interfaces which run on top of a physical interface to be
> managed in conjuction with the device.

What if you had an inverse-MUX type of device that spanned two different
physical interfaces.  Then, one can go down, but the virtual interface
is still up.  So, there is not a one-to-one coorespondence.  At a higher
level, what if your interface is some tunnel running over IP.  IP in turn
can be routed out any physical interface (and may dynamically change due
to routing protocols.)

> Device goes down, you destroy them
> or send them to a shutdown state (instead of messaging) etc.
> 
> cheers,
> jamal

-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[Andi Kleen]

On Sun, Jan 07, 2001 at 04:01:04AM -0800, David S. Miller wrote:
>    Date:   Mon, 8 Jan 2001 01:13:08 +1300
>    From: Chris Wedgwood <cw@f00f.org>
> 
>    OK, I'm a liar -- bind does handle this. Cool.
> 
> Standard BSD allows it, what do you expect :-)
> 
>    This is good news, because it means there is a precedent for multiple
>    addresses on a single interface so we can kill the <ifname>:<n>
>    syntax in favor of the above which is cleaner of more accurately
>    represents what is happening.
> 
> If this is really true, 2.5.x is an appropriate time to make
> this, no sooner.

I think it would be better to keep it. The ifa based alias interface 
emulation adds minor overhead (currently it's only a few lines of code,
assuming we need named if addresses for other reasons too, which we do) 
and removing it it would break a lot of configuration scripts etc., for 
no really good gain. 


-Andi



-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[Chris Wedgwood]

On Mon, Jan 08, 2001 at 06:32:14AM +0100, Andi Kleen wrote:

    I think it would be better to keep it. The ifa based alias
    interface emulation adds minor overhead (currently it's only a
    few lines of code, assuming we need named if addresses for other
    reasons too, which we do) and removing it it would break a lot of
    configuration scripts etc., for no really good gain.

It's ugly and deceptive -- eth0:0 is _not_ a separate device to eth0,
so why pretend it is?

Yes, FIXING this wart will break stuff, that is part of the reason we
have development cycles. Applications that break need fixing anyhow,
as DaveM says BSD support multiple addresses per interface anyhow, so
perhaps not many applications will break at all -- I've not really
checked.

2.5.x seems like an excellent time to FIX this. I guess the final
decision is that of DaveM and Alexey.



  --cw (These are mine opinions alone, but they should be everyones)
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[Blu3Viper]

On Mon, 8 Jan 2001, Andi Kleen wrote:
> > If this is really true, 2.5.x is an appropriate time to make
> > this, no sooner.
> 
> I think it would be better to keep it. The ifa based alias interface 
> emulation adds minor overhead (currently it's only a few lines of code,
> assuming we need named if addresses for other reasons too, which we do) 
> and removing it it would break a lot of configuration scripts etc., for 
> no really good gain. 

How about turning it out with a legacy/deprecated CONFIG_ option so we can
prepare people. For now it can default to enabled.

-d

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[Andi Kleen]

On Mon, Jan 08, 2001 at 07:12:09PM +1300, Chris Wedgwood wrote:
> On Mon, Jan 08, 2001 at 06:32:14AM +0100, Andi Kleen wrote:
> 
>     I think it would be better to keep it. The ifa based alias
>     interface emulation adds minor overhead (currently it's only a
>     few lines of code, assuming we need named if addresses for other
>     reasons too, which we do) and removing it it would break a lot of
>     configuration scripts etc., for no really good gain.
> 
> It's ugly and deceptive -- eth0:0 is _not_ a separate device to eth0,
> so why pretend it is?

Who says that it names a device? It names interfaces.
There are good reasons to have names for ifas, and I see no really good
convincing reasons not to put these names into the interface name space.
(in addition it'll save a lot of people a lot of grief) 
When you're proposing a change that breaks thousands of configuration you
need a really good reason for it, and so far I cannot see one. It would 
be different if the older way needed lots of hard to maintain fragile code in 
the kernel, but that's really not the case. 


-Andi
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[David Ford]

On Mon, 8 Jan 2001, Andi Kleen wrote:
> Who says that it names a device? It names interfaces.
> There are good reasons to have names for ifas, and I see no really good
> convincing reasons not to put these names into the interface name space.
> (in addition it'll save a lot of people a lot of grief) 
> When you're proposing a change that breaks thousands of configuration you
> need a really good reason for it, and so far I cannot see one. It would 
> be different if the older way needed lots of hard to maintain fragile code in 
> the kernel, but that's really not the case. 

If people are upgrading to things like 2.6, then one must expect some
changes.  The eth0:0 style has already been whittled down, it has nothing
now but the IP and mask info. It's a something between two styles.  It
encourages a non-scalable use.  I.e. eth0:2342, or eth0:http.  It came up
because listing w/ ifconfig -a in it's current form wasn't satisfactorily
fast.

Distributions should be encouraged to use ip rather than ifconfig/route.  It
works better and does more, the output is more informative, more concise,
and less confusing.  It doesn't take that much more disk space than ifconfig
and route does, ifconfig and route take 74K, ip takes 89K. I don't think 15k
of disk space is sufficient concern, given that inodes are probably page
size.  That comes out to three pages difference.  Even on a floppy that's
not much.  I didn't even compile optimized for size either.

Due to that, 'eth0:n' becomes a byproduct without much merit.  People who
insist on eth0:n are probably people who also will insist on 1.2.13 for
their router simply because they don't want or need to change it.  The new
form with the new tool is easier, especially if you have any cisco
background.  You can't beat 'ip a a 10.1.1.1/24 brd + dev eth0' for the
netmask and figuring out the broadcast properly without error.  It's shorter
and less prone to error and more easily scriptable because you don't need a
changing label.  It's also more easily parsed by scripts.

-d


--
---NOTICE--- fwd: fwd: fwd: type emails will be deleted automatically.
      "There is a natural aristocracy among men. The grounds of this are
      virtue and talents", Thomas Jefferson [1742-1826], 3rd US President

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (New Benchmarks)

[David S. Miller]

   Date: 	Mon, 08 Jan 2001 01:12:21 -0700
   From: Ben Greear <greearb@candelatech.com>

   http://grok.yi.org/~greear/hashed_dev.png
   (If you can't get to it, let me know and I'll email it to you...some
    cable modem networks have I firewalled.)

It just seems that this shows that the implementation of ifconfig can
be improved, since "ip" can do the same thing several orders of
magnitude better (ie. non-quadratic system time complexity).

This is the argument I started with when this thread began, so my
position hasn't changed, it has in fact been well supported by your
tests :-)

Later,
David S. Miller
davem@redhat.com
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (New Benchmarks)

[Ben Greear]

See a pretty graph showing performance of ifconfig and ip
both with and without my device-hashed-lookup patch:

http://grok.yi.org/~greear/hashed_dev.png
(If you can't get to it, let me know and I'll email it to you...some
 cable modem networks have I firewalled.)

I ran ifconfig -a and ip addr show every 50 interfaces,
as I added 4000 interfaces, and used the 'time -p' program to
find the system and user times.

Summary:
	ifconfig scales badly, ip is better.
	Both ip and ifconfig work better with the hash patch, at
        least when the number of interfaces grows past 1000.

If anyone wants the raw numbers, I can provide them and the script
that generated them.

NOTE:  I stopped the non-hashed test after 3000 interfaces because
it was just going too slow (ifconfig was killing me!)

So, is this good enough reason to add the hashed patch?

If not, I feel sure I can write a program that binds to a specific
interface 10k times, and my assumption is that the hash will help
significantly if there are lots of interfaces.  However, I'd
rather not go to the hassle if the ifconfig/ip numbers are sufficient.

If no amount of benchmarking will change key player's minds, then
go ahead and tell me now so that I can go back to hacking code
and just include this patch with my VLAN patch.

Thanks,
Ben

-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: routable interfaces WAS( Re: [PATCH] hashed device lookup(DoesNOTmeet Linus' sumission policy!)

[jamal]

On Sun, 7 Jan 2001, Ben Greear wrote:
> jamal wrote:

> > As in my response to Matti, i thing a netdevice is a generalized link
> > layer structure and should remain that way.
>
> Yes, but VLANs are a link-layer structure too, and things like tunnels
> are really link-layer too, as far as protocols using them are concerned.
>
> With tunneling and virtual interfaces, you could conceivably do something
> like:
>
> OC3 - ATM - Ethernet - VLAN - IP - IP-Sec - IP
> as well as plain old:
> Ethernet - IP
>
> Which of these are netdevices?
>

I think you are mixing up the packet munging/management part of the entity
and the data part. There is a very close relation, however the munger is
_not_ a netdevice. The entry l2 protocol demuxing selects the munger.

> (I argue that at least the Ethernet-over-ATM, VLAN, and IP-Sec entities could
> profit from being a net_device at it's core.)
>
> You argue that we should split the net_device into physical and virtual
> portions.

Iam not asking for this. It is pseudo-already-there.
What i am asking for is consistency. A virtual IP address is "virtual" and
resides on top of a link (eg ethernet) as does a VLAN. Yet a VLAN gets its
own life as a netdevice. Why? so that it can be "routable".

> Perhaps you could give an idea of the data members that would belong in the new
> structures?  I argue that you lose the minute you need one in both structures :)
>

I dont have to add new data structures. The ifa structure on a netdevice
is sufficient. It has a name/label, it has an IP address, it lacks an
ifindex. counters is the other lacking one (thinking of what Gleb posted).
A vlan device could be a simple IP-alias.
I am not all bent to insist that it has to be an ifa. What matters is
consistency. I want an alias to be used by a route daemon. The easiest
brute force way is to make it a netdevice. You might hack this from the
route daemon itself as well but as Gleb was pointing out SNMP wont be
happy.

> > > This has seeming worked well for VLANs:  Maybe net_device is already
> > > general enough??
> >
> > I think it is not proper to generalize netdevices for IP. I am not
> > thinking of dead protocols like IPX, more of other newer encapsulations
> > such as MPLS etc.
>
> MPLS can run over FrameRelay, Ethernet, and ATM, at the moment (right?).
>
> What if you want to run MPLS over an IP-Sec link?  If you want it to
> magically work, IP-Sec could be a net_device with it's own particular
> member methods and private data that let it do the right thing.
>

Again, this is an issue of netdevice data vs its associated methods/mungers.

>
> What if you had an inverse-MUX type of device that spanned two different
> physical interfaces.  Then, one can go down, but the virtual interface
> is still up.  So, there is not a one-to-one coorespondence.  At a higher
> level, what if your interface is some tunnel running over IP.  IP in turn
> can be routed out any physical interface (and may dynamically change due
> to routing protocols.)

it's that thin line between a netdevice and the packet munging.
Today the first association is via a l2 demux point -- that split is very
clean, IMO.
An IP packet comes in, you invoke the IP handling code. a type
ETH_P_802_1Q comes in you invoke the vlan handling code. At some point
along that path you invoke the ip handling code which ends up invoking the
IPSEC handler etc. IP/GRE or IPIP tunnels get handled the same way.
NOTE that this has absolutely nothing to do with a netdevice. Your VLAN
code manages the state mapping of what vlanid maps to what skb->dev. I
would say this is where the one-to-one mapping is maintained. You dont
have to assume a device to get the mapping.
Infact each of those stages maintains some state to work. IP maintains a
route table.
it should probably be refined further to be based on a classification of
any sort needed instead of the incremental classification only.
The posting by Matti pointed to some page that was suggesting a netif_rx
per input device. I also think this is that linked association that a
netdvice is a net-munger as well as a routable interface.
Maybe the netdevice is the best abstraction for a routable interface
because it is already stamped in people's heads and also because IP rules.
Once you've stripped all headers and done what you need to do just pass it
to a dev->rx() and it will take it from there. I still see confusion.

BTW,The problem you described will face you on a VLAN spanning two physical
ports ;-> Do tell me how you solve it.

cheers,
jamal




-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[jamal]

On Sun, 7 Jan 2001, David Ford wrote:

> Distributions should be encouraged to use ip rather than ifconfig/route.  It
> works better and does more, the output is more informative, more concise,
> and less confusing.  It doesn't take that much more disk space than ifconfig
> and route does, ifconfig and route take 74K, ip takes 89K. I don't think 15k
> of disk space is sufficient concern, given that inodes are probably page
> size.

Actually if you count arp which is also part of ip; ip becomes smaller
by about 15K.

cheers,
jamal

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (New Benchmarks)

[Ben Greear]

"David S. Miller" wrote:
> 
>    Date:        Mon, 08 Jan 2001 01:12:21 -0700
>    From: Ben Greear <greearb@candelatech.com>
> 
>    http://grok.yi.org/~greear/hashed_dev.png
>    (If you can't get to it, let me know and I'll email it to you...some
>     cable modem networks have I firewalled.)
> 
> It just seems that this shows that the implementation of ifconfig can
> be improved, since "ip" can do the same thing several orders of
> magnitude better (ie. non-quadratic system time complexity).
> 
> This is the argument I started with when this thread began, so my
> position hasn't changed, it has in fact been well supported by your
> tests :-)

I don't argue that ifconfig shouldn't be fixed, but the hash speeds up
ip by about 2X too.  Is that not useful enough?  ip seems to be implemented
pretty efficient, so if the hash helps it significantly then maybe it
can help other efficient programs too.  Notice that it is the system
(ie kernel) time that stays remarkably flat with the hash + ip graph.

Ben

-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (New Benchmarks)

[Andi Kleen]

On Mon, Jan 08, 2001 at 04:23:41PM +0100, Ben Greear wrote:
> I don't argue that ifconfig shouldn't be fixed, but the hash speeds up

It's already fixed since months. There was one stupid algorithm, which
I was to blame for when I changed ifconfig to use a device list two years ago.
At that time I didn't think that anybody would be ever crazy enough to set up
4000 interfaces and just chosed the simplest list management. I fixed it 
when you first complained a few months ago and now the list insertion works
that the list does not need to be walked fully in the usual case.
It could be optimized more in user space, but it's probably not worth it. 

> ip by about 2X too.  Is that not useful enough?  ip seems to be implemented
> pretty efficient, so if the hash helps it significantly then maybe it
> can help other efficient programs too.  Notice that it is the system
> (ie kernel) time that stays remarkably flat with the hash + ip graph.

Just does your benchmark represent anything that real users do frequently ? 

If you really want to optimize I'm sure there are lots of areas in the kernel
where your efforts are better spent ;) [just run with a the kernel profiler on
for a few days on your box and look at all the real hot spots] 

BTW, if you just want to optimize ip link ls speed it would be probably enough
to keep a one behind cache that just caches the next member after the last
search. 


-Andi
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission policy!)

[Blu3Viper]

> Actually if you count arp which is also part of ip; ip becomes smaller
> by about 15K.

...i always forget some small detail.

thx

-d

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (New Benchmarks)

[Ben Greear]

Andi Kleen wrote:
> 
> On Mon, Jan 08, 2001 at 04:23:41PM +0100, Ben Greear wrote:
> > I don't argue that ifconfig shouldn't be fixed, but the hash speeds up
> 
> It's already fixed since months. There was one stupid algorithm, which
> I was to blame for when I changed ifconfig to use a device list two years ago.

The benchmark was run against this one:
[root@candle lanforge]# ifconfig --version
net-tools 1.57
ifconfig 1.40 (2000-05-21)


The latest I could find anywhere....  Please tell me the version of a
newer one if it exists.

> > ip by about 2X too.  Is that not useful enough?  ip seems to be implemented
> > pretty efficient, so if the hash helps it significantly then maybe it
> > can help other efficient programs too.  Notice that it is the system
> > (ie kernel) time that stays remarkably flat with the hash + ip graph.
> 
> Just does your benchmark represent anything that real users do frequently ?

I'm going to write something that binds to a raw device, which is something
users (DHCP, for sure) does.  If it does not show any significant improvement,
then I'll drop the issue untill many-many interfaces are more common.

> 
> If you really want to optimize I'm sure there are lots of areas in the kernel
> where your efforts are better spent ;) [just run with a the kernel profiler on
> for a few days on your box and look at all the real hot spots]

I was just trying to smooth VLAN's adoption into the kernel by removing the
one linear-lookup that I know of relating to lots of VLANs.  It obviously
isn't horribly important, but it was fun :)


> 
> BTW, if you just want to optimize ip link ls speed it would be probably enough
> to keep a one behind cache that just caches the next member after the last
> search.

That is still linear in the kernel...or do you mean cache in the kernel?  At any
rate, I'm more concerned about random access.

> 
> -Andi

-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Christopher E. Brown]

On Sun, 7 Jan 2001, Alan Cox wrote:

> > Um, what about people running their box as just a VLAN router/firewall?
> > That seems to be one of the principle uses so far.  Actually, in that case
> > both VLAN and IP traffic would come through, so it would be a tie if VLAN
> > came first, but non-vlan traffic would suffer worse.
> 
> Why would someone filter between vlans when any node on each vlan can happily
> ignore the vlan partitioning


	Think VLANing switch clusters.  Say 4 switches connected by
GigE on 4 floors or in 4 separate building.  Now, across these
switches 20 VLANS are running, with the switches enforcing VLAN
partitioning.  The client PCs know nothing about it, as each one
resides within a single VLAN.

	Now we have our Linux box with 2 x 100Mbit FD links to the
switch cluster running 10 VLANS per interface, and an external
DS1/SDSL/whatever connection.  We now have 20 separate zones with
different security controls per zone, with per switchport control over
who resided in what group.  Or even forget the routing and just
plugging a Linux box to a companies 200VLAN setup to provide
DHCP/whatever.

	I must say, I *hate* VLANs for this use, it is a horrible
thing to do that wastes massive amounts of bandwidth on simulating a
local broadcast domain across a much larger area, but oh well.  As
long as we have stupid managers and brain dead sales persons not much
will change.  Are there better things to do than VLAN?  YES!  Will we
get stuck with needing VLANs in the real world?  YES!


---
        The roaches seem to have survived, but they are not routing packets
correctly.
        --About the Internet and nuclear war.


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] hashed device lookup (Does NOT meet Linus' sumission

[Ben Greear]

"Christopher E. Brown" wrote:
> 

>         Think VLANing switch clusters.  Say 4 switches connected by
> GigE on 4 floors or in 4 separate building.  Now, across these
> switches 20 VLANS are running, with the switches enforcing VLAN
> partitioning.  The client PCs know nothing about it, as each one
> resides within a single VLAN.

That would seem to cut down broadcast packets, and generally be a good
thing!

> 
>         Now we have our Linux box with 2 x 100Mbit FD links to the
> switch cluster running 10 VLANS per interface, and an external
> DS1/SDSL/whatever connection.  We now have 20 separate zones with
> different security controls per zone, with per switchport control over
> who resided in what group.  Or even forget the routing and just
> plugging a Linux box to a companies 200VLAN setup to provide
> DHCP/whatever.
> 
>         I must say, I *hate* VLANs for this use, it is a horrible
> thing to do that wastes massive amounts of bandwidth on simulating a
> local broadcast domain across a much larger area, but oh well.  As
> long as we have stupid managers and brain dead sales persons not much
> will change.  Are there better things to do than VLAN?  YES!  Will we
> get stuck with needing VLANs in the real world?  YES!

Umm, how does using VLANs lead to wasting massive amount of bandwidth?
(You seem to be saying that by partitioning the network we make each
partition bigger??)

What are the better solutions?

And what does your dislike for sales and management have to do with
the topic at hand?



-- 
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/