Skip site navigation (1)Skip section navigation (2)
Date:      Tue, 4 Sep 2012 12:07:33 +0000 (UTC)
From:      Gleb Smirnoff <glebius@FreeBSD.org>
To:        src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org
Subject:   svn commit: r240086 - in head: share/man/man9 sys/conf sys/libkern sys/net sys/sys
Message-ID:  <201209041207.q84C7Xl4051365@svn.freebsd.org>

next in thread | raw e-mail | index | archive | help
Author: glebius
Date: Tue Sep  4 12:07:33 2012
New Revision: 240086
URL: http://svn.freebsd.org/changeset/base/240086

Log:
  - Move jenkins.h to jenkins_hash.c
  - Provide missing function that can do hashing of arbitrary sized buffer.
  - Refetch lookup3.c and do only minimal edits to it, so that diff between
    our jenkins_hash.c and lookup3.c is minimal.
  - Add declarations for jenkins_hash(), jenkins_hash32() to sys/hash.h.
  - Document these functions in hash(9)
  
  Obtained from:	http://burtleburtle.net/bob/c/lookup3.c

Added:
  head/sys/libkern/jenkins_hash.c
     - copied, changed from r240081, head/sys/libkern/jenkins.h
Deleted:
  head/sys/libkern/jenkins.h
Modified:
  head/share/man/man9/hash.9
  head/sys/conf/files
  head/sys/net/flowtable.c
  head/sys/sys/hash.h

Modified: head/share/man/man9/hash.9
==============================================================================
--- head/share/man/man9/hash.9	Tue Sep  4 12:02:23 2012	(r240085)
+++ head/share/man/man9/hash.9	Tue Sep  4 12:07:33 2012	(r240086)
@@ -26,7 +26,7 @@
 .\"     $OpenBSD: hash.9,v 1.5 2003/04/17 05:08:39 jmc Exp $
 .\" $FreeBSD$
 .\"
-.Dd April 3, 2007
+.Dd September 4, 2012
 .Dt HASH 9
 .Os
 .Sh NAME
@@ -36,7 +36,9 @@
 .Nm hash32_str ,
 .Nm hash32_strn ,
 .Nm hash32_stre ,
-.Nm hash32_strne
+.Nm hash32_strne ,
+.Nm jenkins_hash32 ,
+.Nm jenkins_hash
 .Nd general kernel hashing functions
 .Sh SYNOPSIS
 .In sys/hash.h
@@ -50,6 +52,10 @@
 .Fn hash32_stre "const void *buf" "int end" "const char **ep" "uint32_t hash"
 .Ft uint32_t
 .Fn hash32_strne "const void *buf" "size_t len" "int end" "const char **ep" "uint32_t hash"
+.Ft uint32_t
+.Fn jenkins_hash "const void *buf" "size_t len" "uint32_t hash"
+.Ft uint32_t
+.Fn jenkins_hash32 "const uint32_t *buf" "size_t count" "uint32_t hash"
 .Sh DESCRIPTION
 The
 .Fn hash32
@@ -107,6 +113,23 @@ is not
 .Dv NULL ,
 it is set to the point in the buffer at which the hash function
 terminated hashing.
+.Pp
+The
+.Fn jenkins_hash
+function has same semantics as the
+.Fn hash32_buf ,
+but provides more advanced hashing algorithm with better distribution.
+.Pp
+The
+.Fn jenkins_hash32
+uses same hashing algorithm as the
+.Fn jenkins_hash
+function, but works only on
+.Ft uint32_t
+sized arrays, thus is simplier and faster.
+It accepts an array of
+.Ft uint32_t
+values in its first argument and size of this array in the second argument.
 .Sh RETURN VALUES
 The
 .Fn hash32
@@ -150,12 +173,24 @@ be revisited.
 .Sh HISTORY
 The
 .Nm
-functions were first committed to
+functions first appeared in
 .Nx 1.6 .
-The
-.Ox
-versions were written and massaged for
-.Ox 2.3
-by Tobias Weingartner,
-and finally committed for
-.Ox 3.2 .
+The current implementation of
+.Nm hash32
+functions was first committed to
+.Ox 3.2 ,
+and later imported to
+.Fx 6.1 .
+The
+.Nm jenkins_hash
+functions were added in
+.Fx 10.0 .
+.Sh AUTHORS
+The
+.Nm hash32
+functions were written by
+.An Tobias Weingartner .
+The
+.Nm jenkins_hash
+functions was written by
+Bob Jenkins .

Modified: head/sys/conf/files
==============================================================================
--- head/sys/conf/files	Tue Sep  4 12:02:23 2012	(r240085)
+++ head/sys/conf/files	Tue Sep  4 12:07:33 2012	(r240086)
@@ -2797,6 +2797,7 @@ libkern/inet_aton.c		standard
 libkern/inet_ntoa.c		standard
 libkern/inet_ntop.c		standard
 libkern/inet_pton.c		standard
+libkern/jenkins_hash.c		standard
 libkern/mcount.c		optional profiling-routine
 libkern/memcchr.c		standard
 libkern/memcmp.c		standard

Copied and modified: head/sys/libkern/jenkins_hash.c (from r240081, head/sys/libkern/jenkins.h)
==============================================================================
--- head/sys/libkern/jenkins.h	Tue Sep  4 05:54:43 2012	(r240081, copy source)
+++ head/sys/libkern/jenkins_hash.c	Tue Sep  4 12:07:33 2012	(r240086)
@@ -1,43 +1,44 @@
-#ifndef __LIBKERN_JENKINS_H__
-#define __LIBKERN_JENKINS_H__
 /*
  * Taken from http://burtleburtle.net/bob/c/lookup3.c
  * $FreeBSD$
  */
 
+#include <sys/hash.h>
+#include <machine/endian.h>
+
 /*
 -------------------------------------------------------------------------------
-  lookup3.c, by Bob Jenkins, May 2006, Public Domain.
-
-  These are functions for producing 32-bit hashes for hash table lookup.
-  hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
-  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's in
-  the public domain.  It has no warranty.
-
-  You probably want to use hashlittle().  hashlittle() and hashbig()
-  hash byte arrays.  hashlittle() is faster than hashbig() on
-  little-endian machines.  Intel and AMD are little-endian machines.
-  On second thought, you probably want hashlittle2(), which is identical to
-  hashlittle() except it returns two 32-bit hashes for the price of one.
-  You could implement hashbig2() if you wanted but I haven't bothered here.
+lookup3.c, by Bob Jenkins, May 2006, Public Domain.
 
-  If you want to find a hash of, say, exactly 7 integers, do
-    a = i1;  b = i2;  c = i3;
-    mix(a,b,c);
-    a += i4; b += i5; c += i6;
-    mix(a,b,c);
-    a += i7;
-    final(a,b,c);
-  then use c as the hash value.  If you have a variable length array of
-  4-byte integers to hash, use hashword().  If you have a byte array (like
-  a character string), use hashlittle().  If you have several byte arrays, or
-  a mix of things, see the comments above hashlittle().
-  
-  Why is this so big?  I read 12 bytes at a time into 3 4-byte integers,
-  then mix those integers.  This is fast (you can do a lot more thorough
-  mixing with 12*3 instructions on 3 integers than you can with 3 instructions
-  on 1 byte), but shoehorning those bytes into integers efficiently is messy.
+These are functions for producing 32-bit hashes for hash table lookup.
+hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() 
+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's in
+the public domain.  It has no warranty.
+
+You probably want to use hashlittle().  hashlittle() and hashbig()
+hash byte arrays.  hashlittle() is is faster than hashbig() on
+little-endian machines.  Intel and AMD are little-endian machines.
+On second thought, you probably want hashlittle2(), which is identical to
+hashlittle() except it returns two 32-bit hashes for the price of one.  
+You could implement hashbig2() if you wanted but I haven't bothered here.
+
+If you want to find a hash of, say, exactly 7 integers, do
+  a = i1;  b = i2;  c = i3;
+  mix(a,b,c);
+  a += i4; b += i5; c += i6;
+  mix(a,b,c);
+  a += i7;
+  final(a,b,c);
+then use c as the hash value.  If you have a variable length array of
+4-byte integers to hash, use hashword().  If you have a byte array (like
+a character string), use hashlittle().  If you have several byte arrays, or
+a mix of things, see the comments above hashlittle().  
+
+Why is this so big?  I read 12 bytes at a time into 3 4-byte integers, 
+then mix those integers.  This is fast (you can do a lot more thorough
+mixing with 12*3 instructions on 3 integers than you can with 3 instructions
+on 1 byte), but shoehorning those bytes into integers efficiently is messy.
 -------------------------------------------------------------------------------
 */
 
@@ -146,12 +147,10 @@ and these came close:
  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 jenkins_hash32(
+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;
 
@@ -182,4 +181,283 @@ jenkins_hashword(
   /*------------------------------------------------------ report the result */
   return c;
 }
-#endif 
+
+#if BYTE_ORDER == LITTLE_ENDIAN
+/*
+-------------------------------------------------------------------------------
+hashlittle() -- hash a variable-length key into a 32-bit value
+  k       : the key (the unaligned variable-length array of bytes)
+  length  : the length of the key, counting by bytes
+  initval : can be any 4-byte value
+Returns a 32-bit value.  Every bit of the key affects every bit of
+the return value.  Two keys differing by one or two bits will have
+totally different hash values.
+
+The best hash table sizes are powers of 2.  There is no need to do
+mod a prime (mod is sooo slow!).  If you need less than 32 bits,
+use a bitmask.  For example, if you need only 10 bits, do
+  h = (h & hashmask(10));
+In which case, the hash table should have hashsize(10) elements.
+
+If you are hashing n strings (uint8_t **)k, do it like this:
+  for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
+
+By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
+code any way you wish, private, educational, or commercial.  It's free.
+
+Use for hash table lookup, or anything where one collision in 2^^32 is
+acceptable.  Do NOT use for cryptographic purposes.
+-------------------------------------------------------------------------------
+*/
+
+uint32_t jenkins_hash( const void *key, size_t length, uint32_t initval)
+{
+  uint32_t a,b,c;                                          /* internal state */
+  union { const void *ptr; size_t i; } u;     /* needed for Mac Powerbook G4 */
+
+  /* Set up the internal state */
+  a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
+
+  u.ptr = key;
+  if ((u.i & 0x3) == 0) {
+    const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
+
+    /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
+    while (length > 12)
+    {
+      a += k[0];
+      b += k[1];
+      c += k[2];
+      mix(a,b,c);
+      length -= 12;
+      k += 3;
+    }
+
+    /*----------------------------- handle the last (probably partial) block */
+    /* 
+     * "k[2]&0xffffff" actually reads beyond the end of the string, but
+     * then masks off the part it's not allowed to read.  Because the
+     * string is aligned, the masked-off tail is in the same word as the
+     * rest of the string.  Every machine with memory protection I've seen
+     * does it on word boundaries, so is OK with this.  But VALGRIND will
+     * still catch it and complain.  The masking trick does make the hash
+     * noticably faster for short strings (like English words).
+     */
+
+    switch(length)
+    {
+    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
+    case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
+    case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
+    case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
+    case 8 : b+=k[1]; a+=k[0]; break;
+    case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
+    case 6 : b+=k[1]&0xffff; a+=k[0]; break;
+    case 5 : b+=k[1]&0xff; a+=k[0]; break;
+    case 4 : a+=k[0]; break;
+    case 3 : a+=k[0]&0xffffff; break;
+    case 2 : a+=k[0]&0xffff; break;
+    case 1 : a+=k[0]&0xff; break;
+    case 0 : return c;              /* zero length strings require no mixing */
+    }
+
+  } else if ((u.i & 0x1) == 0) {
+    const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */
+    const uint8_t  *k8;
+
+    /*--------------- all but last block: aligned reads and different mixing */
+    while (length > 12)
+    {
+      a += k[0] + (((uint32_t)k[1])<<16);
+      b += k[2] + (((uint32_t)k[3])<<16);
+      c += k[4] + (((uint32_t)k[5])<<16);
+      mix(a,b,c);
+      length -= 12;
+      k += 6;
+    }
+
+    /*----------------------------- handle the last (probably partial) block */
+    k8 = (const uint8_t *)k;
+    switch(length)
+    {
+    case 12: c+=k[4]+(((uint32_t)k[5])<<16);
+             b+=k[2]+(((uint32_t)k[3])<<16);
+             a+=k[0]+(((uint32_t)k[1])<<16);
+             break;
+    case 11: c+=((uint32_t)k8[10])<<16;     /* fall through */
+    case 10: c+=k[4];
+             b+=k[2]+(((uint32_t)k[3])<<16);
+             a+=k[0]+(((uint32_t)k[1])<<16);
+             break;
+    case 9 : c+=k8[8];                      /* fall through */
+    case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
+             a+=k[0]+(((uint32_t)k[1])<<16);
+             break;
+    case 7 : b+=((uint32_t)k8[6])<<16;      /* fall through */
+    case 6 : b+=k[2];
+             a+=k[0]+(((uint32_t)k[1])<<16);
+             break;
+    case 5 : b+=k8[4];                      /* fall through */
+    case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
+             break;
+    case 3 : a+=((uint32_t)k8[2])<<16;      /* fall through */
+    case 2 : a+=k[0];
+             break;
+    case 1 : a+=k8[0];
+             break;
+    case 0 : return c;                     /* zero length requires no mixing */
+    }
+
+  } else {                        /* need to read the key one byte at a time */
+    const uint8_t *k = (const uint8_t *)key;
+
+    /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
+    while (length > 12)
+    {
+      a += k[0];
+      a += ((uint32_t)k[1])<<8;
+      a += ((uint32_t)k[2])<<16;
+      a += ((uint32_t)k[3])<<24;
+      b += k[4];
+      b += ((uint32_t)k[5])<<8;
+      b += ((uint32_t)k[6])<<16;
+      b += ((uint32_t)k[7])<<24;
+      c += k[8];
+      c += ((uint32_t)k[9])<<8;
+      c += ((uint32_t)k[10])<<16;
+      c += ((uint32_t)k[11])<<24;
+      mix(a,b,c);
+      length -= 12;
+      k += 12;
+    }
+
+    /*-------------------------------- last block: affect all 32 bits of (c) */
+    switch(length)                   /* all the case statements fall through */
+    {
+    case 12: c+=((uint32_t)k[11])<<24;
+    case 11: c+=((uint32_t)k[10])<<16;
+    case 10: c+=((uint32_t)k[9])<<8;
+    case 9 : c+=k[8];
+    case 8 : b+=((uint32_t)k[7])<<24;
+    case 7 : b+=((uint32_t)k[6])<<16;
+    case 6 : b+=((uint32_t)k[5])<<8;
+    case 5 : b+=k[4];
+    case 4 : a+=((uint32_t)k[3])<<24;
+    case 3 : a+=((uint32_t)k[2])<<16;
+    case 2 : a+=((uint32_t)k[1])<<8;
+    case 1 : a+=k[0];
+             break;
+    case 0 : return c;
+    }
+  }
+
+  final(a,b,c);
+  return c;
+}
+
+#else /* !(BYTE_ORDER == LITTLE_ENDIAN) */
+
+/*
+ * hashbig():
+ * This is the same as hashword() on big-endian machines.  It is different
+ * from hashlittle() on all machines.  hashbig() takes advantage of
+ * big-endian byte ordering. 
+ */
+uint32_t jenkins_hash( const void *key, size_t length, uint32_t initval)
+{
+  uint32_t a,b,c;
+  union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
+
+  /* Set up the internal state */
+  a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
+
+  u.ptr = key;
+  if ((u.i & 0x3) == 0) {
+    const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
+
+    /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
+    while (length > 12)
+    {
+      a += k[0];
+      b += k[1];
+      c += k[2];
+      mix(a,b,c);
+      length -= 12;
+      k += 3;
+    }
+
+    /*----------------------------- handle the last (probably partial) block */
+    /* 
+     * "k[2]<<8" actually reads beyond the end of the string, but
+     * then shifts out the part it's not allowed to read.  Because the
+     * string is aligned, the illegal read is in the same word as the
+     * rest of the string.  Every machine with memory protection I've seen
+     * does it on word boundaries, so is OK with this.  But VALGRIND will
+     * still catch it and complain.  The masking trick does make the hash
+     * noticably faster for short strings (like English words).
+     */
+
+    switch(length)
+    {
+    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
+    case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
+    case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
+    case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
+    case 8 : b+=k[1]; a+=k[0]; break;
+    case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
+    case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
+    case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
+    case 4 : a+=k[0]; break;
+    case 3 : a+=k[0]&0xffffff00; break;
+    case 2 : a+=k[0]&0xffff0000; break;
+    case 1 : a+=k[0]&0xff000000; break;
+    case 0 : return c;              /* zero length strings require no mixing */
+    }
+
+  } else {                        /* need to read the key one byte at a time */
+    const uint8_t *k = (const uint8_t *)key;
+
+    /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
+    while (length > 12)
+    {
+      a += ((uint32_t)k[0])<<24;
+      a += ((uint32_t)k[1])<<16;
+      a += ((uint32_t)k[2])<<8;
+      a += ((uint32_t)k[3]);
+      b += ((uint32_t)k[4])<<24;
+      b += ((uint32_t)k[5])<<16;
+      b += ((uint32_t)k[6])<<8;
+      b += ((uint32_t)k[7]);
+      c += ((uint32_t)k[8])<<24;
+      c += ((uint32_t)k[9])<<16;
+      c += ((uint32_t)k[10])<<8;
+      c += ((uint32_t)k[11]);
+      mix(a,b,c);
+      length -= 12;
+      k += 12;
+    }
+
+    /*-------------------------------- last block: affect all 32 bits of (c) */
+    switch(length)                   /* all the case statements fall through */
+    {
+    case 12: c+=k[11];
+    case 11: c+=((uint32_t)k[10])<<8;
+    case 10: c+=((uint32_t)k[9])<<16;
+    case 9 : c+=((uint32_t)k[8])<<24;
+    case 8 : b+=k[7];
+    case 7 : b+=((uint32_t)k[6])<<8;
+    case 6 : b+=((uint32_t)k[5])<<16;
+    case 5 : b+=((uint32_t)k[4])<<24;
+    case 4 : a+=k[3];
+    case 3 : a+=((uint32_t)k[2])<<8;
+    case 2 : a+=((uint32_t)k[1])<<16;
+    case 1 : a+=((uint32_t)k[0])<<24;
+             break;
+    case 0 : return c;
+    }
+  }
+
+  final(a,b,c);
+  return c;
+}
+#endif

Modified: head/sys/net/flowtable.c
==============================================================================
--- head/sys/net/flowtable.c	Tue Sep  4 12:02:23 2012	(r240085)
+++ head/sys/net/flowtable.c	Tue Sep  4 12:07:33 2012	(r240086)
@@ -41,6 +41,7 @@ __FBSDID("$FreeBSD$");
 #include <sys/bitstring.h>
 #include <sys/condvar.h>
 #include <sys/callout.h>
+#include <sys/hash.h>
 #include <sys/kernel.h>  
 #include <sys/kthread.h>
 #include <sys/limits.h>
@@ -73,7 +74,6 @@ __FBSDID("$FreeBSD$");
 #include <netinet/udp.h>
 #include <netinet/sctp.h>
 
-#include <libkern/jenkins.h>
 #include <ddb/ddb.h>
 
 struct ipv4_tuple {
@@ -585,7 +585,7 @@ ipv4_flow_lookup_hash_internal(
 	} else
 		offset = V_flow_hashjitter + proto;
 
-	return (jenkins_hashword(key, 3, offset));
+	return (jenkins_hash32(key, 3, offset));
 }
 
 static struct flentry *
@@ -791,7 +791,7 @@ ipv6_flow_lookup_hash_internal(
 	} else
 		offset = V_flow_hashjitter + proto;
 
-	return (jenkins_hashword(key, 9, offset));
+	return (jenkins_hash32(key, 9, offset));
 }
 
 static struct flentry *

Modified: head/sys/sys/hash.h
==============================================================================
--- head/sys/sys/hash.h	Tue Sep  4 12:02:23 2012	(r240085)
+++ head/sys/sys/hash.h	Tue Sep  4 12:07:33 2012	(r240086)
@@ -118,4 +118,13 @@ hash32_strne(const void *buf, size_t len
 
 	return hash;
 }
+
+#ifdef _KERNEL
+/*
+ * Hashing function from Bob Jenkins. Implementation in libkern/jenkins_hash.c.
+ */
+uint32_t jenkins_hash(const void *, size_t, uint32_t);
+uint32_t jenkins_hash32(const uint32_t *, size_t, uint32_t);
+#endif /* _KERNEL */
+
 #endif /* !_SYS_HASH_H_ */



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201209041207.q84C7Xl4051365>