From 3258cf3f11bf7c68a2e69e1808c4551cc899725a Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Fri, 24 Sep 2010 15:34:06 +0930 Subject: tdb: add Bob Jenkins lookup3 hash as helper hash. This is a better hash than the default: shipping it with tdb makes it easy for callers to use it as the hash by passing it to tdb_open_ex(). This version taken from CCAN and modified, which took it from http://www.burtleburtle.net/bob/c/lookup3.c. Signed-off-by: Rusty Russell --- lib/tdb/ABI/tdb-1.2.5.sigs | 61 +++++++ lib/tdb/common/hash.c | 380 +++++++++++++++++++++++++++++++++++++++++++ lib/tdb/common/open.c | 16 +- lib/tdb/common/tdb_private.h | 1 + lib/tdb/configure.ac | 2 +- lib/tdb/include/tdb.h | 1 + lib/tdb/wscript | 4 +- 7 files changed, 447 insertions(+), 18 deletions(-) create mode 100644 lib/tdb/ABI/tdb-1.2.5.sigs create mode 100644 lib/tdb/common/hash.c diff --git a/lib/tdb/ABI/tdb-1.2.5.sigs b/lib/tdb/ABI/tdb-1.2.5.sigs new file mode 100644 index 0000000000..1e01f3ba24 --- /dev/null +++ b/lib/tdb/ABI/tdb-1.2.5.sigs @@ -0,0 +1,61 @@ +tdb_add_flags: void (struct tdb_context *, unsigned int) +tdb_append: int (struct tdb_context *, TDB_DATA, TDB_DATA) +tdb_chainlock: int (struct tdb_context *, TDB_DATA) +tdb_chainlock_mark: int (struct tdb_context *, TDB_DATA) +tdb_chainlock_nonblock: int (struct tdb_context *, TDB_DATA) +tdb_chainlock_read: int (struct tdb_context *, TDB_DATA) +tdb_chainlock_unmark: int (struct tdb_context *, TDB_DATA) +tdb_chainunlock: int (struct tdb_context *, TDB_DATA) +tdb_chainunlock_read: int (struct tdb_context *, TDB_DATA) +tdb_check: int (struct tdb_context *, int (*)(TDB_DATA, TDB_DATA, void *), void *) +tdb_close: int (struct tdb_context *) +tdb_delete: int (struct tdb_context *, TDB_DATA) +tdb_dump_all: void (struct tdb_context *) +tdb_enable_seqnum: void (struct tdb_context *) +tdb_error: enum TDB_ERROR (struct tdb_context *) +tdb_errorstr: const char *(struct tdb_context *) +tdb_exists: int (struct tdb_context *, TDB_DATA) +tdb_fd: int (struct tdb_context *) +tdb_fetch: TDB_DATA (struct tdb_context *, TDB_DATA) +tdb_firstkey: TDB_DATA (struct tdb_context *) +tdb_freelist_size: int (struct tdb_context *) +tdb_get_flags: int (struct tdb_context *) +tdb_get_logging_private: void *(struct tdb_context *) +tdb_get_seqnum: int (struct tdb_context *) +tdb_hash_size: int (struct tdb_context *) +tdb_increment_seqnum_nonblock: void (struct tdb_context *) +tdb_jenkins_hash: unsigned int (TDB_DATA *) +tdb_lockall: int (struct tdb_context *) +tdb_lockall_mark: int (struct tdb_context *) +tdb_lockall_nonblock: int (struct tdb_context *) +tdb_lockall_read: int (struct tdb_context *) +tdb_lockall_read_nonblock: int (struct tdb_context *) +tdb_lockall_unmark: int (struct tdb_context *) +tdb_log_fn: tdb_log_func (struct tdb_context *) +tdb_map_size: size_t (struct tdb_context *) +tdb_name: const char *(struct tdb_context *) +tdb_nextkey: TDB_DATA (struct tdb_context *, TDB_DATA) +tdb_null: dptr = 0xXXXX, dsize = 0 +tdb_open: struct tdb_context *(const char *, int, int, int, mode_t) +tdb_open_ex: struct tdb_context *(const char *, int, int, int, mode_t, const struct tdb_logging_context *, tdb_hash_func) +tdb_parse_record: int (struct tdb_context *, TDB_DATA, int (*)(TDB_DATA, TDB_DATA, void *), void *) +tdb_printfreelist: int (struct tdb_context *) +tdb_remove_flags: void (struct tdb_context *, unsigned int) +tdb_reopen: int (struct tdb_context *) +tdb_reopen_all: int (int) +tdb_repack: int (struct tdb_context *) +tdb_set_logging_function: void (struct tdb_context *, const struct tdb_logging_context *) +tdb_set_max_dead: void (struct tdb_context *, int) +tdb_setalarm_sigptr: void (struct tdb_context *, volatile sig_atomic_t *) +tdb_store: int (struct tdb_context *, TDB_DATA, TDB_DATA, int) +tdb_transaction_cancel: int (struct tdb_context *) +tdb_transaction_commit: int (struct tdb_context *) +tdb_transaction_prepare_commit: int (struct tdb_context *) +tdb_transaction_start: int (struct tdb_context *) +tdb_transaction_start_nonblock: int (struct tdb_context *) +tdb_traverse: int (struct tdb_context *, tdb_traverse_func, void *) +tdb_traverse_read: int (struct tdb_context *, tdb_traverse_func, void *) +tdb_unlockall: int (struct tdb_context *) +tdb_unlockall_read: int (struct tdb_context *) +tdb_validate_freelist: int (struct tdb_context *, int *) +tdb_wipe_all: int (struct tdb_context *) diff --git a/lib/tdb/common/hash.c b/lib/tdb/common/hash.c new file mode 100644 index 0000000000..c07297ec19 --- /dev/null +++ b/lib/tdb/common/hash.c @@ -0,0 +1,380 @@ + /* + Unix SMB/CIFS implementation. + + trivial database library + + Copyright (C) Rusty Russell 2010 + + ** NOTE! The following LGPL license applies to the tdb + ** library. This does NOT imply that all of Samba is released + ** under the LGPL + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 3 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, see . +*/ +#include "tdb_private.h" + +/* This is based on the hash algorithm from gdbm */ +unsigned int tdb_old_hash(TDB_DATA *key) +{ + uint32_t value; /* Used to compute the hash value. */ + uint32_t i; /* Used to cycle through random values. */ + + /* Set the initial value from the key size. */ + for (value = 0x238F13AF * key->dsize, i=0; i < key->dsize; i++) + value = (value + (key->dptr[i] << (i*5 % 24))); + + return (1103515243 * value + 12345); +} + +#ifndef WORDS_BIGENDIAN +# define HASH_LITTLE_ENDIAN 1 +# define HASH_BIG_ENDIAN 0 +#else +# define HASH_LITTLE_ENDIAN 0 +# define HASH_BIG_ENDIAN 1 +#endif + +/* +------------------------------------------------------------------------------- +lookup3.c, by Bob Jenkins, May 2006, Public Domain. + +These are functions for producing 32-bit hashes for hash table lookup. +hash_word(), 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 hash_word(). 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. +*/ + +#define hashsize(n) ((uint32_t)1<<(n)) +#define hashmask(n) (hashsize(n)-1) +#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) + +/* +------------------------------------------------------------------------------- +mix -- mix 3 32-bit 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 1-bit + 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 one-bit base and a two-bit 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. Read-after-writes 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 32-bit 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 1-bit + 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); \ +} + + +/* +------------------------------------------------------------------------------- +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 + val2 : IN: can be any 4-byte value OUT: second 32 bit hash. +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. Note that the return value is better +mixed than val2, so use that first. + +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 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). + */ +#ifndef VALGRIND + + 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 /* make valgrind happy */ + + k8 = (const uint8_t *)k; + switch(length) + { + case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; + case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ + case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ + case 9 : c+=k8[8]; /* fall through */ + case 8 : b+=k[1]; a+=k[0]; break; + case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ + case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ + case 5 : b+=k8[4]; /* fall through */ + case 4 : a+=k[0]; break; + case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ + case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ + case 1 : a+=k8[0]; break; + case 0 : return c; + } + +#endif /* !valgrind */ + + } else if (HASH_LITTLE_ENDIAN && ((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; +} + +unsigned int tdb_jenkins_hash(TDB_DATA *key) +{ + return hashlittle(key->dptr, key->dsize); +} diff --git a/lib/tdb/common/open.c b/lib/tdb/common/open.c index a964994509..f0e2dfc7e1 100644 --- a/lib/tdb/common/open.c +++ b/lib/tdb/common/open.c @@ -30,20 +30,6 @@ /* all contexts, to ensure no double-opens (fcntl locks don't nest!) */ static struct tdb_context *tdbs = NULL; - -/* This is based on the hash algorithm from gdbm */ -static unsigned int default_tdb_hash(TDB_DATA *key) -{ - uint32_t value; /* Used to compute the hash value. */ - uint32_t i; /* Used to cycle through random values. */ - - /* Set the initial value from the key size. */ - for (value = 0x238F13AF * key->dsize, i=0; i < key->dsize; i++) - value = (value + (key->dptr[i] << (i*5 % 24))); - - return (1103515243 * value + 12345); -} - /* We use two hashes to double-check they're using the right hash function. */ void tdb_header_hash(struct tdb_context *tdb, uint32_t *magic1_hash, uint32_t *magic2_hash) @@ -191,7 +177,7 @@ struct tdb_context *tdb_open_ex(const char *name, int hash_size, int tdb_flags, tdb->hash_fn = hash_fn; hash_alg = "user defined"; } else { - tdb->hash_fn = default_tdb_hash; + tdb->hash_fn = tdb_old_hash; hash_alg = "default"; } diff --git a/lib/tdb/common/tdb_private.h b/lib/tdb/common/tdb_private.h index eccd6880ef..fe3603c104 100644 --- a/lib/tdb/common/tdb_private.h +++ b/lib/tdb/common/tdb_private.h @@ -272,3 +272,4 @@ bool tdb_write_all(int fd, const void *buf, size_t count); int tdb_transaction_recover(struct tdb_context *tdb); void tdb_header_hash(struct tdb_context *tdb, uint32_t *magic1_hash, uint32_t *magic2_hash); +unsigned int tdb_old_hash(TDB_DATA *key); diff --git a/lib/tdb/configure.ac b/lib/tdb/configure.ac index 839086525a..a858aa7ec3 100644 --- a/lib/tdb/configure.ac +++ b/lib/tdb/configure.ac @@ -2,7 +2,7 @@ AC_PREREQ(2.50) AC_DEFUN([SMB_MODULE_DEFAULT], [echo -n ""]) AC_DEFUN([SMB_LIBRARY_ENABLE], [echo -n ""]) AC_DEFUN([SMB_ENABLE], [echo -n ""]) -AC_INIT(tdb, 1.2.4) +AC_INIT(tdb, 1.2.5) AC_CONFIG_SRCDIR([common/tdb.c]) AC_CONFIG_HEADER(include/config.h) AC_LIBREPLACE_ALL_CHECKS diff --git a/lib/tdb/include/tdb.h b/lib/tdb/include/tdb.h index 050f398eec..08b6b3ab55 100644 --- a/lib/tdb/include/tdb.h +++ b/lib/tdb/include/tdb.h @@ -142,6 +142,7 @@ _PUBLIC_ void tdb_add_flags(struct tdb_context *tdb, unsigned flag); _PUBLIC_ void tdb_remove_flags(struct tdb_context *tdb, unsigned flag); _PUBLIC_ void tdb_enable_seqnum(struct tdb_context *tdb); _PUBLIC_ void tdb_increment_seqnum_nonblock(struct tdb_context *tdb); +_PUBLIC_ unsigned int tdb_jenkins_hash(TDB_DATA *key); _PUBLIC_ int tdb_check(struct tdb_context *tdb, int (*check) (TDB_DATA key, TDB_DATA data, void *private_data), void *private_data); diff --git a/lib/tdb/wscript b/lib/tdb/wscript index ff468f2797..970c6287cf 100644 --- a/lib/tdb/wscript +++ b/lib/tdb/wscript @@ -1,7 +1,7 @@ #!/usr/bin/env python APPNAME = 'tdb' -VERSION = '1.2.4' +VERSION = '1.2.5' blddir = 'bin' @@ -58,7 +58,7 @@ def build(bld): COMMON_SRC = bld.SUBDIR('common', '''check.c error.c tdb.c traverse.c freelistcheck.c lock.c dump.c freelist.c - io.c open.c transaction.c''') + io.c open.c transaction.c hash.c''') if not bld.CONFIG_SET('USING_SYSTEM_TDB'): bld.SAMBA_LIBRARY('tdb', -- cgit