[Olsr-dev] [PATCH] fix hash handling for IP{v4,v6}

[Hannes Gredler]

On Tue, May 06, 2008 at 12:51:52AM +0200, Hagen Paul Pfeifer wrote:
| now I know why olsrd is so incredible fast ... the hashing is complete broken!
| ;)

there are other reasons for the speed,
like the rewrites of the past 12 months in the areas of

-timer library
-linkset handling
-inplace SPF computation
-RIB table management
-netlink interface towards kernel
-efficient message parsing
 
| The following patch fix the hash functionality for IP{v4,v6} addresses.
| Currently the code is _really_ buggy, especially for IPv6 (where nearly[tm]
| every address result in a collision). This patch try to fix them. "Try"
| because the hash result should be mixed with an additional magic cookie to
| prevent some kind of spoofing attacks. But because that isn't a hot topic at
| the moment this patch should be fine.

b/c of the nondeterminism of the exisiting hash functions (and lack of sorting),
in fact we have converted most data structures to use AVL trees rather than hashed
lookups.

--

anyway, your patch looks good (infrastructure patches are always welcome :-))
and i am going to include it in the next (0.5.7) release.

many tx !

/hannes

| diff --git a/src/hashing.c b/src/hashing.c
| --- a/src/hashing.c
| +++ b/src/hashing.c
| @@ -40,7 +40,79 @@
|  
|  #include "olsr_protocol.h"
|  #include "hashing.h"
| +#include "log.h"
|  #include "defs.h"
| +
| +/*
| + * Taken from lookup2.c by Bob Jenkins.  (http://burtleburtle.net/bob/c/lookup2.c).
| + * --------------------------------------------------------------------
| + * lookup2.c, by Bob Jenkins, December 1996, Public Domain.
| + * hash(), hash2(), hash3, and mix() are externally useful functions.
| + * Routines to test the hash are included if SELF_TEST is defined.
| + * You can use this free for any purpose.  It has no warranty.
| + * --------------------------------------------------------------------
| + */
| +#define __jhash_mix(a, b, c) \
| +{ \
| +  a -= b; a -= c; a ^= (c>>13); \
| +  b -= c; b -= a; b ^= (a<<8); \
| +  c -= a; c -= b; c ^= (b>>13); \
| +  a -= b; a -= c; a ^= (c>>12);  \
| +  b -= c; b -= a; b ^= (a<<16); \
| +  c -= a; c -= b; c ^= (b>>5); \
| +  a -= b; a -= c; a ^= (c>>3);  \
| +  b -= c; b -= a; b ^= (a<<10); \
| +  c -= a; c -= b; c ^= (b>>15); \
| +}
| +
| +static olsr_u32_t
| +jenkins_hash(const olsr_u8_t *k, olsr_u32_t length)
| +{
| +	/* k: the key
| +	 * length: length of the key
| +	 * initval: the previous hash, or an arbitrary value
| +	 */
| +	olsr_u32_t a, b, c, len;
| +
| +	/* Set up the internal state */
| +	len = length;
| +	a = b = 0x9e3779b9;	/* the golden ratio; an arbitrary value */
| +	c = 0;		/* the previous hash value */
| +
| +	/* handle most of the key */
| +	while (len >= 12) {
| +		a += (k[0] + ((olsr_u32_t)k[1] << 8) + ((olsr_u32_t)k[2]  << 16)
| +				+ ((olsr_u32_t)k[3] << 24));
| +		b += (k[4] + ((olsr_u32_t)k[5] << 8) + ((olsr_u32_t)k[6]  << 16)
| +				+ ((olsr_u32_t)k[7] << 24));
| +		c += (k[8] +((olsr_u32_t)k[9] << 8) + ((olsr_u32_t)k[10] << 16)
| +				+ ((olsr_u32_t)k[11] << 24));
| +
| +		__jhash_mix(a,b,c);
| +
| +		k += 12; len -= 12;
| +	}
| +
| +	c += length;
| +	switch(len) {
| +		case 11: c+=((olsr_u32_t)k[10]<<24);
| +		case 10: c+=((olsr_u32_t)k[9]<<16);
| +		case 9 : c+=((olsr_u32_t)k[8]<<8);
| +		/* the first byte of c is reserved for the length */
| +		case 8 : b+=((olsr_u32_t)k[7]<<24);
| +		case 7 : b+=((olsr_u32_t)k[6]<<16);
| +		case 6 : b+=((olsr_u32_t)k[5]<<8);
| +		case 5 : b+=k[4];
| +		case 4 : a+=((olsr_u32_t)k[3]<<24);
| +		case 3 : a+=((olsr_u32_t)k[2]<<16);
| +		case 2 : a+=((olsr_u32_t)k[1]<<8);
| +		case 1 : a+=k[0];
| +	}
| +	__jhash_mix(a,b,c);
| +
| +	return c;
| +}
| +
|  
|  /**
|   * Hashing function. Creates a key based on
| @@ -51,14 +123,22 @@
|  olsr_u32_t olsr_ip_hashing(const union olsr_ip_addr * address)
|  {
|    olsr_u32_t hash;
| -  if(olsr_cnf->ip_version == AF_INET) {
| -    /* IPv4 */  
| -    const olsr_u8_t * const v4x = (const olsr_u8_t *)&address->v4;
| -    hash = v4x[0] ^ v4x[1] ^ v4x[2] ^ v4x[3];
| -  } else {
| -    /* IPv6 */
| -    const char * const tmp = (const char *)&address->v6;
| -    hash = ntohl(*tmp);
| +
| +  switch (olsr_cnf->ip_version) {
| +	  case AF_INET:
| +		  hash = jenkins_hash((const olsr_u8_t *)&address->v4,
| +				  sizeof(olsr_u32_t));
| +		  break;
| +	  case AF_INET6:
| +		  hash = jenkins_hash((const olsr_u8_t *)&address->v6,
| +				  sizeof(struct in6_addr));
| +		  break;
| +	  default:
| +		  olsr_syslog(OLSR_LOG_ERR, "olsrd: programmed error in switch statement!: %s:%d\n",
| +				  __FILE__, __LINE__);
| +		  return 0;
| +		  break;
| +
|    }
|    return hash & HASHMASK;
|  }

| -- 
| Olsr-dev mailing list
| (spam-protected)
| http://lists.olsr.org/mailman/listinfo/olsr-dev