Skip to contentSkip to conversation

fib_semantics: prevent long hash chains in access server config

PATCH In review Benjamin LaHaise 2 participants 4 messages Jan 12, 2008 – Jan 14, 2008

Subsystems (3)
Networking Network drivers IPv4/IPv6
lore
Share & tools
lore

Benjamin LaHaise

author
#0 lore raw

PATCH 1/1 fib_semantics: prevent long hash chains in access server config

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

net/ipv4/fib_semantics.c +10 -9
index 1351a26..5375824 100644
@@ -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.
  */
maintainer
#1 lore raw

From: Benjamin LaHaise <[email protected]>
Date: Sat, 12 Jan 2008 13:58:19 -0500

Quoted 4 lines

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.

author
#2 lore raw
Quoted 5 lines · David Miller

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

Signature · 2 lines
"Time is of no importance, Mr. President, only life is important."
Don't Email: <[email protected]>.
maintainer
#3 lore raw

From: Benjamin LaHaise <[email protected]>
Date: Sun, 13 Jan 2008 12:58:49 -0500

Quoted 2 lines

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 <[email protected]>
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 <[email protected]>
net/ipv4/fib_semantics.c +12 -9
index 3ed920b..0e08df4 100644
@@ -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.
  */