[PATCH] fib_semantics: prevent long hash chains in access server config

[PATCH] fib_semantics: prevent long hash chains in access server config

[Benjamin LaHaise]

This is a patch from a while ago that I'm resending.  Basically, in access 
server configurations, a lot of routes have the same local ip address but on 
different devices.  This fixes the long chains that result from not including 
the device index in the hash.

		-ben

diff --git a/net/ipv4/fib_semantics.c b/net/ipv4/fib_semantics.c
index 1351a26..5375824 100644
--- a/net/ipv4/fib_semantics.c
+++ b/net/ipv4/fib_semantics.c
@@ -196,11 +196,21 @@ static __inline__ int nh_comp(const struct fib_info *fi, const struct fib_info *
 	return 0;
 }
 
+static inline unsigned int fib_devindex_hashfn(unsigned int val)
+{
+	unsigned int mask = DEVINDEX_HASHSIZE - 1;
+
+	return (val ^
+		(val >> DEVINDEX_HASHBITS) ^
+		(val >> (DEVINDEX_HASHBITS * 2))) & mask;
+}
+
 static inline unsigned int fib_info_hashfn(const struct fib_info *fi)
 {
 	unsigned int mask = (fib_hash_size - 1);
 	unsigned int val = fi->fib_nhs;
 
+	val ^= fib_devindex_hashfn(fi->fib_dev->ifindex);
 	val ^= fi->fib_protocol;
 	val ^= (__force u32)fi->fib_prefsrc;
 	val ^= fi->fib_priority;
@@ -234,15 +244,6 @@ static struct fib_info *fib_find_info(const struct fib_info *nfi)
 	return NULL;
 }
 
-static inline unsigned int fib_devindex_hashfn(unsigned int val)
-{
-	unsigned int mask = DEVINDEX_HASHSIZE - 1;
-
-	return (val ^
-		(val >> DEVINDEX_HASHBITS) ^
-		(val >> (DEVINDEX_HASHBITS * 2))) & mask;
-}
-
 /* Check, that the gateway is already configured.
    Used only by redirect accept routine.
  */

Re: [PATCH] fib_semantics: prevent long hash chains in access server config

[David Miller]

From: Benjamin LaHaise <bcrl@kvack.org>
Date: Sat, 12 Jan 2008 13:58:19 -0500

> This is a patch from a while ago that I'm resending.  Basically, in
> access server configurations, a lot of routes have the same local ip
> address but on different devices.  This fixes the long chains that
> result from not including the device index in the hash.

I'm not applying this for the same reason I didn't apply it last time.

Please listen to the reason this time, and do not resubmit this until
the problem with this patch is resolved.

The fib_dev is an attribute of the first nexthop, ie. the
fib_info->fib_nh[0] member.

There can be multiple nexthops.

It is pointless to salt the hash with one of the nexthop
device indexes if you do not also compare the index in the
hash lookup comparisons.

And guess why we don't do this?  Because it's not part of
the key.  Other aspects of the base fib_info and nexthops
provide the uniqueness, not the devindex of the first hop.

So you'll need to find another way to do this.

Re: [PATCH] fib_semantics: prevent long hash chains in access server config

[Benjamin LaHaise]

On Sat, Jan 12, 2008 at 09:38:57PM -0800, David Miller wrote:
> And guess why we don't do this?  Because it's not part of
> the key.  Other aspects of the base fib_info and nexthops
> provide the uniqueness, not the devindex of the first hop.
> 
> So you'll need to find another way to do this.

Ah, you're right indeed.  It's probably easier for me to change how the 
daemon adds the local ip address for these point to point interfaces.

		-ben
-- 
"Time is of no importance, Mr. President, only life is important."
Don't Email: <zyntrop@kvack.org>.

Re: [PATCH] fib_semantics: prevent long hash chains in access server config

[David Miller]

From: Benjamin LaHaise <bcrl@kvack.org>
Date: Sun, 13 Jan 2008 12:58:49 -0500

> Ah, you're right indeed.  It's probably easier for me to change how the 
> daemon adds the local ip address for these point to point interfaces.

I guess you didn't understand, I checked in the following
patch which implements things correctly.

commit d5414fdd4098742a5a9d255c4b9af587318c525f
Author: David S. Miller <davem@davemloft.net>
Date:   Sat Jan 12 21:49:01 2008 -0800

    [IPV4] FIB: Include nexthop device indexes in fib_info hashfn.
    
    Signed-off-by: David S. Miller <davem@davemloft.net>

diff --git a/net/ipv4/fib_semantics.c b/net/ipv4/fib_semantics.c
index 3ed920b..0e08df4 100644
--- a/net/ipv4/fib_semantics.c
+++ b/net/ipv4/fib_semantics.c
@@ -194,6 +194,15 @@ static __inline__ int nh_comp(const struct fib_info *fi, const struct fib_info *
 	return 0;
 }
 
+static inline unsigned int fib_devindex_hashfn(unsigned int val)
+{
+	unsigned int mask = DEVINDEX_HASHSIZE - 1;
+
+	return (val ^
+		(val >> DEVINDEX_HASHBITS) ^
+		(val >> (DEVINDEX_HASHBITS * 2))) & mask;
+}
+
 static inline unsigned int fib_info_hashfn(const struct fib_info *fi)
 {
 	unsigned int mask = (fib_hash_size - 1);
@@ -202,6 +211,9 @@ static inline unsigned int fib_info_hashfn(const struct fib_info *fi)
 	val ^= fi->fib_protocol;
 	val ^= (__force u32)fi->fib_prefsrc;
 	val ^= fi->fib_priority;
+	for_nexthops(fi) {
+		val ^= fib_devindex_hashfn(nh->nh_oif);
+	} endfor_nexthops(fi)
 
 	return (val ^ (val >> 7) ^ (val >> 12)) & mask;
 }
@@ -232,15 +244,6 @@ static struct fib_info *fib_find_info(const struct fib_info *nfi)
 	return NULL;
 }
 
-static inline unsigned int fib_devindex_hashfn(unsigned int val)
-{
-	unsigned int mask = DEVINDEX_HASHSIZE - 1;
-
-	return (val ^
-		(val >> DEVINDEX_HASHBITS) ^
-		(val >> (DEVINDEX_HASHBITS * 2))) & mask;
-}
-
 /* Check, that the gateway is already configured.
    Used only by redirect accept routine.
  */