Skip to contentSkip to conversation

Fix hash function for IP addresses on 64bit little-endian machines.

PATCH In review NeilBrown 2 participants 2 messages Dec 16, 2005 1 message not in the archive

Subsystems (3)
lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): 20051216152056.4989.patches@notabene

NeilBrown

author
#1 lore raw

PATCH 1/1 Fix hash function for IP addresses on 64bit little-endian machines.

This patch against 2.6.15-rc5-mm2 is suitable, but not critical, for 2.6.15.

--
The hash.h hash_long function, when used on a 64 bit machine, ignores many of the middle-order bits. (The prime chosen it too bit-sparse).

IP addresses for clients of an NFS server are very likely to differ only in the low-order bits. As addresses are stored in network-byte-order, these bits become middle-order bits in a little-endian 64bit 'long', and so do not contribute to the hash. Thus you can have the situation where all clients appear on one hash chain.

So, until hash_long is fixed (or maybe forever), us a hash function that works well on IP addresses - xor the bytes together.

Thanks to "Iozone" <[email protected]> for identifying this problem.

Cc "Iozone" <[email protected]>

### Diffstat output

 ./net/sunrpc/svcauth_unix.c |   14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)
net/sunrpc/svcauth_unix.c renamed from net/sunrpc/svcauth_unix.c~current~ +13 -1
diff ./net/sunrpc/svcauth_unix.c~current~ ./net/sunrpc/svcauth_unix.c
@@ -101,10 +101,22 @@ static void ip_map_put(struct cache_head
 	}
 }
 
+#if IP_HASHBITS == 8
+/* hash_long on a 64 bit machine is currently REALLY BAD for
+ * IP addresses in reverse-endian (i.e. on a little-endian machine).
+ * So use a trivial but reliable hash instead
+ */
+static inline int hash_ip(unsigned long ip)
+{
+	int hash = ip ^ (ip>>16);
+	return (hash ^ (hash>>8)) & 0xff;
+}
+#endif
+
 static inline int ip_map_hash(struct ip_map *item)
 {
 	return hash_str(item->m_class, IP_HASHBITS) ^ 
-		hash_long((unsigned long)item->m_addr.s_addr, IP_HASHBITS);
+		hash_ip((unsigned long)item->m_addr.s_addr);
 }
 static inline int ip_map_match(struct ip_map *item, struct ip_map *tmp)
 {

-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files for problems? Stop! Download the new AJAX search engine that makes searching your log files as easy as surfing the web. DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist - [email protected]
https://lists.sourceforge.net/lists/listinfo/nfs

#2 lore raw
Quoted 1 line · NeilBrown

(add Bill to cc)

Quoted 42 lines

This patch against 2.6.15-rc5-mm2 is suitable, but not critical, for 2.6.15.

--
The hash.h hash_long function, when used on a 64 bit machine, ignores many of the middle-order bits. (The prime chosen it too bit-sparse).

IP addresses for clients of an NFS server are very likely to differ only in the low-order bits. As addresses are stored in network-byte-order, these bits become middle-order bits in a little-endian 64bit 'long', and so do not contribute to the hash. Thus you can have the situation where all clients appear on one hash chain.

So, until hash_long is fixed (or maybe forever), us a hash function that works well on IP addresses - xor the bytes together.

Thanks to "Iozone" <[email protected]> for identifying this problem.

Cc "Iozone" <[email protected]>

### Diffstat output

 ./net/sunrpc/svcauth_unix.c |   14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

diff ./net/sunrpc/svcauth_unix.c~current~ ./net/sunrpc/svcauth_unix.c

net/sunrpc/svcauth_unix.c renamed from net/sunrpc/svcauth_unix.c~current~ +10 -0
@@ -101,10 +101,22 @@ static void ip_map_put(struct cache_head
 	}
 }
 
+#if IP_HASHBITS == 8
+/* hash_long on a 64 bit machine is currently REALLY BAD for
+ * IP addresses in reverse-endian (i.e. on a little-endian machine).
+ * So use a trivial but reliable hash instead
+ */
+static inline int hash_ip(unsigned long ip)
+{
+	int hash = ip ^ (ip>>16);
+	return (hash ^ (hash>>8)) & 0xff;
+}

net/sunrpc/svcauth_unix.c static void ip_map_put(struct cache_head · line 122

Quoted 10 lines
net/sunrpc/svcauth_unix.c renamed from net/sunrpc/svcauth_unix.c~current~ +3 -1
+#endif
+
 static inline int ip_map_hash(struct ip_map *item)
 {
 	return hash_str(item->m_class, IP_HASHBITS) ^ 
-		hash_long((unsigned long)item->m_addr.s_addr, IP_HASHBITS);
+		hash_ip((unsigned long)item->m_addr.s_addr);
 }
 static inline int ip_map_match(struct ip_map *item, struct ip_map *tmp)
 {

-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files for problems? Stop! Download the new AJAX search engine that makes searching your log files as easy as surfing the web. DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist - [email protected]
https://lists.sourceforge.net/lists/listinfo/nfs