svn commit: r193854  in head/sys: libkern net
Kip Macy
kmacy at FreeBSD.org
Tue Jun 9 20:21:41 UTC 2009
Author: kmacy
Date: Tue Jun 9 20:21:40 2009
New Revision: 193854
URL: http://svn.freebsd.org/changeset/base/193854
Log:
move jenkins hash to its own header in libkern
Added:
head/sys/libkern/jenkins.h (contents, props changed)
Modified:
head/sys/net/flowtable.c
Added: head/sys/libkern/jenkins.h
==============================================================================
 /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ head/sys/libkern/jenkins.h Tue Jun 9 20:21:40 2009 (r193854)
@@ 0,0 +1,149 @@
+#ifndef __LIBKERN_JENKINS_H__
+#define __LIBKERN_JENKINS_H__
+/*
+ * Taken from http://burtleburtle.net/bob/c/lookup3.c
+ * $FreeBSD$
+ */
+
+#define rot(x,k) (((x)<<(k))  ((x)>>(32(k))))
+
+/*
+
+mix  mix 3 32bit values reversibly.
+
+This is reversible, so any information in (a,b,c) before mix() is
+still in (a,b,c) after mix().
+
+If four pairs of (a,b,c) inputs are run through mix(), or through
+mix() in reverse, there are at least 32 bits of the output that
+are sometimes the same for one pair and different for another pair.
+This was tested for:
+* pairs that differed by one bit, by two bits, in any combination
+ of top bits of (a,b,c), or in any combination of bottom bits of
+ (a,b,c).
+* "differ" is defined as +, , ^, or ~^. For + and , I transformed
+ the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
+ is commonly produced by subtraction) look like a single 1bit
+ difference.
+* the base values were pseudorandom, all zero but one bit set, or
+ all zero plus a counter that starts at zero.
+
+Some k values for my "a=c; a^=rot(c,k); c+=b;" arrangement that
+satisfy this are
+ 4 6 8 16 19 4
+ 9 15 3 18 27 15
+ 14 9 3 7 17 3
+Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
+for "differ" defined as + with a onebit base and a twobit delta. I
+used http://burtleburtle.net/bob/hash/avalanche.html to choose
+the operations, constants, and arrangements of the variables.
+
+This does not achieve avalanche. There are input bits of (a,b,c)
+that fail to affect some output bits of (a,b,c), especially of a. The
+most thoroughly mixed value is c, but it doesn't really even achieve
+avalanche in c.
+
+This allows some parallelism. Readafterwrites are good at doubling
+the number of bits affected, so the goal of mixing pulls in the opposite
+direction as the goal of parallelism. I did what I could. Rotates
+seem to cost as much as shifts on every machine I could lay my hands
+on, and rotates are much kinder to the top and bottom bits, so I used
+rotates.
+
+*/
+#define mix(a,b,c) \
+{ \
+ a = c; a ^= rot(c, 4); c += b; \
+ b = a; b ^= rot(a, 6); a += c; \
+ c = b; c ^= rot(b, 8); b += a; \
+ a = c; a ^= rot(c,16); c += b; \
+ b = a; b ^= rot(a,19); a += c; \
+ c = b; c ^= rot(b, 4); b += a; \
+}
+
+/*
+
+final  final mixing of 3 32bit values (a,b,c) into c
+
+Pairs of (a,b,c) values differing in only a few bits will usually
+produce values of c that look totally different. This was tested for
+* pairs that differed by one bit, by two bits, in any combination
+ of top bits of (a,b,c), or in any combination of bottom bits of
+ (a,b,c).
+* "differ" is defined as +, , ^, or ~^. For + and , I transformed
+ the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
+ is commonly produced by subtraction) look like a single 1bit
+ difference.
+* the base values were pseudorandom, all zero but one bit set, or
+ all zero plus a counter that starts at zero.
+
+These constants passed:
+ 14 11 25 16 4 14 24
+ 12 14 25 16 4 14 24
+and these came close:
+ 4 8 15 26 3 22 24
+ 10 8 15 26 3 22 24
+ 11 8 15 26 3 22 24
+
+*/
+#define final(a,b,c) \
+{ \
+ c ^= b; c = rot(b,14); \
+ a ^= c; a = rot(c,11); \
+ b ^= a; b = rot(a,25); \
+ c ^= b; c = rot(b,16); \
+ a ^= c; a = rot(c,4); \
+ b ^= a; b = rot(a,14); \
+ c ^= b; c = rot(b,24); \
+}
+
+/*
+
+ This works on all machines. To be useful, it requires
+  that the key be an array of uint32_t's, and
+  that the length be the number of uint32_t's in the key
+
+ The function hashword() is identical to hashlittle() on littleendian
+ machines, and identical to hashbig() on bigendian machines,
+ except that the length has to be measured in uint32_ts rather than in
+ bytes. hashlittle() is more complicated than hashword() only because
+ hashlittle() has to dance around fitting the key bytes into registers.
+
+*/
+static uint32_t
+jenkins_hashword(
+ const uint32_t *k, /* the key, an array of uint32_t values */
+ size_t length, /* the length of the key, in uint32_ts */
+ uint32_t initval /* the previous hash, or an arbitrary value */
+)
+{
+ uint32_t a,b,c;
+
+ /* Set up the internal state */
+ a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
+
+ /* handle most of the key */
+ while (length > 3)
+ {
+ a += k[0];
+ b += k[1];
+ c += k[2];
+ mix(a,b,c);
+ length = 3;
+ k += 3;
+ }
+
+ /* handle the last 3 uint32_t's */
+ switch(length) /* all the case statements fall through */
+ {
+ case 3 : c+=k[2];
+ case 2 : b+=k[1];
+ case 1 : a+=k[0];
+ final(a,b,c);
+ case 0: /* case 0: nothing left to add */
+ break;
+ }
+ /* report the result */
+ return c;
+}
+#endif
Modified: head/sys/net/flowtable.c
==============================================================================
 head/sys/net/flowtable.c Tue Jun 9 20:20:08 2009 (r193853)
+++ head/sys/net/flowtable.c Tue Jun 9 20:21:40 2009 (r193854)
@@ 67,150 +67,7 @@ __FBSDID("$FreeBSD$");
#include <netinet/udp.h>
#include <netinet/sctp.h>
/*
 * Taken from http://burtleburtle.net/bob/c/lookup3.c
 */

#define rot(x,k) (((x)<<(k))  ((x)>>(32(k))))

/*

mix  mix 3 32bit values reversibly.

This is reversible, so any information in (a,b,c) before mix() is
still in (a,b,c) after mix().

If four pairs of (a,b,c) inputs are run through mix(), or through
mix() in reverse, there are at least 32 bits of the output that
are sometimes the same for one pair and different for another pair.
This was tested for:
* pairs that differed by one bit, by two bits, in any combination
 of top bits of (a,b,c), or in any combination of bottom bits of
 (a,b,c).
* "differ" is defined as +, , ^, or ~^. For + and , I transformed
 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
 is commonly produced by subtraction) look like a single 1bit
 difference.
* the base values were pseudorandom, all zero but one bit set, or
 all zero plus a counter that starts at zero.

Some k values for my "a=c; a^=rot(c,k); c+=b;" arrangement that
satisfy this are
 4 6 8 16 19 4
 9 15 3 18 27 15
 14 9 3 7 17 3
Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
for "differ" defined as + with a onebit base and a twobit delta. I
used http://burtleburtle.net/bob/hash/avalanche.html to choose
the operations, constants, and arrangements of the variables.

This does not achieve avalanche. There are input bits of (a,b,c)
that fail to affect some output bits of (a,b,c), especially of a. The
most thoroughly mixed value is c, but it doesn't really even achieve
avalanche in c.

This allows some parallelism. Readafterwrites are good at doubling
the number of bits affected, so the goal of mixing pulls in the opposite
direction as the goal of parallelism. I did what I could. Rotates
seem to cost as much as shifts on every machine I could lay my hands
on, and rotates are much kinder to the top and bottom bits, so I used
rotates.

*/
#define mix(a,b,c) \
{ \
 a = c; a ^= rot(c, 4); c += b; \
 b = a; b ^= rot(a, 6); a += c; \
 c = b; c ^= rot(b, 8); b += a; \
 a = c; a ^= rot(c,16); c += b; \
 b = a; b ^= rot(a,19); a += c; \
 c = b; c ^= rot(b, 4); b += a; \
}

/*

final  final mixing of 3 32bit values (a,b,c) into c

Pairs of (a,b,c) values differing in only a few bits will usually
produce values of c that look totally different. This was tested for
* pairs that differed by one bit, by two bits, in any combination
 of top bits of (a,b,c), or in any combination of bottom bits of
 (a,b,c).
* "differ" is defined as +, , ^, or ~^. For + and , I transformed
 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
 is commonly produced by subtraction) look like a single 1bit
 difference.
* the base values were pseudorandom, all zero but one bit set, or
 all zero plus a counter that starts at zero.

These constants passed:
 14 11 25 16 4 14 24
 12 14 25 16 4 14 24
and these came close:
 4 8 15 26 3 22 24
 10 8 15 26 3 22 24
 11 8 15 26 3 22 24

*/
#define final(a,b,c) \
{ \
 c ^= b; c = rot(b,14); \
 a ^= c; a = rot(c,11); \
 b ^= a; b = rot(a,25); \
 c ^= b; c = rot(b,16); \
 a ^= c; a = rot(c,4); \
 b ^= a; b = rot(a,14); \
 c ^= b; c = rot(b,24); \
}

/*

 This works on all machines. To be useful, it requires
  that the key be an array of uint32_t's, and
  that the length be the number of uint32_t's in the key

 The function hashword() is identical to hashlittle() on littleendian
 machines, and identical to hashbig() on bigendian machines,
 except that the length has to be measured in uint32_ts rather than in
 bytes. hashlittle() is more complicated than hashword() only because
 hashlittle() has to dance around fitting the key bytes into registers.

*/
static uint32_t hashword(
const uint32_t *k, /* the key, an array of uint32_t values */
size_t length, /* the length of the key, in uint32_ts */
uint32_t initval) /* the previous hash, or an arbitrary value */
{
 uint32_t a,b,c;

 /* Set up the internal state */
 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;

 /* handle most of the key */
 while (length > 3)
 {
 a += k[0];
 b += k[1];
 c += k[2];
 mix(a,b,c);
 length = 3;
 k += 3;
 }

 /* handle the last 3 uint32_t's */
 switch(length) /* all the case statements fall through */
 {
 case 3 : c+=k[2];
 case 2 : b+=k[1];
 case 1 : a+=k[0];
 final(a,b,c);
 case 0: /* case 0: nothing left to add */
 break;
 }
 /* report the result */
 return c;
}

+#include <libkern/jenkins.h>
struct ipv4_tuple {
uint16_t ip_sport; /* source port */
@@ 525,7 +382,7 @@ ipv4_flow_lookup_hash_internal(struct mb
((uint16_t *)key)[1] = dport;
skipports:
 hash = hashword(key, 3, hashjitter + proto);
+ hash = jenkins_hashword(key, 3, hashjitter + proto);
if (m != NULL && (m>m_flags & M_FLOWID) == 0) {
m>m_flags = M_FLOWID;
m>m_pkthdr.flowid = hash;
More information about the svnsrcall
mailing list