From bbfe5872463139d0ce5af75aeb31544bdd04523a Mon Sep 17 00:00:00 2001 From: Howard Chu Date: Mon, 3 Dec 2012 18:14:28 -0800 Subject: [PATCH] Add support for 64 bit index hashing --- include/lutil_hash.h | 42 ++++++++++++++++++---- libraries/liblutil/hash.c | 70 +++++++++++++++++++++++++++++++++++-- servers/slapd/bconfig.c | 22 ++++++++++-- servers/slapd/proto-slap.h | 2 ++ servers/slapd/schema_init.c | 55 ++++++++++++++++++++++++++--- 5 files changed, 174 insertions(+), 17 deletions(-) diff --git a/include/lutil_hash.h b/include/lutil_hash.h index c38e748c29..b7de772ce4 100644 --- a/include/lutil_hash.h +++ b/include/lutil_hash.h @@ -22,26 +22,56 @@ LDAP_BEGIN_DECL #define LUTIL_HASH_BYTES 4 -struct lutil_HASHContext { +#ifdef HAVE_LONG_LONG + +typedef union lutil_HASHContext { + ber_uint_t hash; + unsigned long long hash64; +} lutil_HASH_CTX; + +#else /* !HAVE_LONG_LONG */ + +typedef struct lutil_HASHContext { ber_uint_t hash; -}; +} lutil_HASH_CTX; + +#endif /* HAVE_LONG_LONG */ LDAP_LUTIL_F( void ) lutil_HASHInit LDAP_P(( - struct lutil_HASHContext *context)); + lutil_HASH_CTX *context)); LDAP_LUTIL_F( void ) lutil_HASHUpdate LDAP_P(( - struct lutil_HASHContext *context, + lutil_HASH_CTX *context, unsigned char const *buf, ber_len_t len)); LDAP_LUTIL_F( void ) lutil_HASHFinal LDAP_P(( unsigned char digest[LUTIL_HASH_BYTES], - struct lutil_HASHContext *context)); + lutil_HASH_CTX *context)); + +#ifdef HAVE_LONG_LONG + +#define LUTIL_HASH64_BYTES 8 + +LDAP_LUTIL_F( void ) +lutil_HASH64Init LDAP_P(( + lutil_HASH_CTX *context)); + +LDAP_LUTIL_F( void ) +lutil_HASH64Update LDAP_P(( + lutil_HASH_CTX *context, + unsigned char const *buf, + ber_len_t len)); + +LDAP_LUTIL_F( void ) +lutil_HASH64Final LDAP_P(( + unsigned char digest[LUTIL_HASH64_BYTES], + lutil_HASH_CTX *context)); -typedef struct lutil_HASHContext lutil_HASH_CTX; +#endif /* HAVE_LONG_LONG */ LDAP_END_DECL diff --git a/libraries/liblutil/hash.c b/libraries/liblutil/hash.c index 26691dd297..46f0f92e1c 100644 --- a/libraries/liblutil/hash.c +++ b/libraries/liblutil/hash.c @@ -32,7 +32,7 @@ * Initialize context */ void -lutil_HASHInit( struct lutil_HASHContext *ctx ) +lutil_HASHInit( lutil_HASH_CTX *ctx ) { ctx->hash = HASH_OFFSET; } @@ -42,7 +42,7 @@ lutil_HASHInit( struct lutil_HASHContext *ctx ) */ void lutil_HASHUpdate( - struct lutil_HASHContext *ctx, + lutil_HASH_CTX *ctx, const unsigned char *buf, ber_len_t len ) { @@ -66,7 +66,7 @@ lutil_HASHUpdate( * Save hash */ void -lutil_HASHFinal( unsigned char *digest, struct lutil_HASHContext *ctx ) +lutil_HASHFinal( unsigned char *digest, lutil_HASH_CTX *ctx ) { ber_uint_t h = ctx->hash; @@ -75,3 +75,67 @@ lutil_HASHFinal( unsigned char *digest, struct lutil_HASHContext *ctx ) digest[2] = (h>>16) & 0xffU; digest[3] = (h>>24) & 0xffU; } + +#ifdef HAVE_LONG_LONG + +/* 64 bit Fowler/Noll/Vo-O FNV-1a hash code */ + +#define HASH64_OFFSET 0xcbf29ce484222325ULL + +/* + * Initialize context + */ +void +lutil_HASH64Init( lutil_HASH_CTX *ctx ) +{ + ctx->hash64 = HASH64_OFFSET; +} + +/* + * Update hash + */ +void +lutil_HASH64Update( + lutil_HASH_CTX *ctx, + const unsigned char *buf, + ber_len_t len ) +{ + const unsigned char *p, *e; + unsigned long long h; + + p = buf; + e = &buf[len]; + + h = ctx->hash64; + + while( p < e ) { + /* xor the bottom with the current octet */ + h ^= *p++; + + /* multiply by the 64 bit FNV magic prime mod 2^64 */ + h += (h << 1) + (h << 4) + (h << 5) + + (h << 7) + (h << 8) + (h << 40); + + } + + ctx->hash64 = h; +} + +/* + * Save hash + */ +void +lutil_HASH64Final( unsigned char *digest, lutil_HASH_CTX *ctx ) +{ + unsigned long long h = ctx->hash; + + digest[0] = h & 0xffU; + digest[1] = (h>>8) & 0xffU; + digest[2] = (h>>16) & 0xffU; + digest[3] = (h>>24) & 0xffU; + digest[4] = (h>>32) & 0xffU; + digest[5] = (h>>40) & 0xffU; + digest[6] = (h>>48) & 0xffU; + digest[7] = (h>>56) & 0xffU; +} +#endif /* HAVE_LONG_LONG */ diff --git a/servers/slapd/bconfig.c b/servers/slapd/bconfig.c index 17cae260c8..d36616f5e5 100644 --- a/servers/slapd/bconfig.c +++ b/servers/slapd/bconfig.c @@ -196,6 +196,7 @@ enum { CFG_ACL_ADD, CFG_SYNC_SUBENTRY, CFG_LTHREADS, + CFG_IX_HASH64, CFG_LAST }; @@ -395,6 +396,9 @@ static ConfigTable config_back_cf_table[] = { { "include", "file", 2, 2, 0, ARG_MAGIC, &config_include, "( OLcfgGlAt:19 NAME 'olcInclude' " "SUP labeledURI )", NULL, NULL }, + { "index_hash64", "on|off", 2, 2, 0, ARG_ON_OFF|ARG_MAGIC|CFG_IX_HASH64, + &config_generic, "( OLcfgGlAt:94 NAME 'olcIndexHash64' " + "SYNTAX OMsBoolean SINGLE-VALUE )", NULL, NULL }, { "index_substr_if_minlen", "min", 2, 2, 0, ARG_UINT|ARG_NONZERO|ARG_MAGIC|CFG_SSTR_IF_MIN, &config_generic, "( OLcfgGlAt:20 NAME 'olcIndexSubstrIfMinLen' " "SYNTAX OMsInteger SINGLE-VALUE )", NULL, NULL }, @@ -826,8 +830,8 @@ static ConfigOCs cf_ocs[] = { "olcConnMaxPending $ olcConnMaxPendingAuth $ " "olcDisallows $ olcGentleHUP $ olcIdleTimeout $ " "olcIndexSubstrIfMaxLen $ olcIndexSubstrIfMinLen $ " - "olcIndexSubstrAnyLen $ olcIndexSubstrAnyStep $ olcIndexIntLen $ " - "olcLocalSSF $ olcLogFile $ olcLogLevel $ " + "olcIndexSubstrAnyLen $ olcIndexSubstrAnyStep $ olcIndexHash64 $ " + "olcIndexIntLen $ olcLocalSSF $ olcLogFile $ olcLogLevel $ " "olcPasswordCryptSaltFormat $ olcPasswordHash $ olcPidFile $ " "olcPluginLogFile $ olcReadOnly $ olcReferral $ " "olcReplogFile $ olcRequires $ olcRestrict $ olcReverseLookup $ " @@ -1199,6 +1203,9 @@ config_generic(ConfigArgs *c) { case CFG_SSTR_IF_MIN: c->value_uint = index_substr_if_minlen; break; + case CFG_IX_HASH64: + c->value_int = slap_hash64( -1 ); + break; case CFG_IX_INTLEN: c->value_int = index_intlen; break; @@ -1378,6 +1385,10 @@ config_generic(ConfigArgs *c) { c->be->be_flags &= ~SLAP_DBFLAG_HIDDEN; break; + case CFG_IX_HASH64: + slap_hash64( 0 ); + break; + case CFG_IX_INTLEN: index_intlen = SLAP_INDEX_INTLEN_DEFAULT; index_intlen_strlen = SLAP_INDEX_INTLEN_STRLEN( @@ -1885,6 +1896,11 @@ config_generic(ConfigArgs *c) { return(1); break; + case CFG_IX_HASH64: + if ( slap_hash64( c->value_int != 0 )) + return 1; + break; + case CFG_IX_INTLEN: if ( c->value_int < SLAP_INDEX_INTLEN_DEFAULT ) c->value_int = SLAP_INDEX_INTLEN_DEFAULT; @@ -1894,7 +1910,7 @@ config_generic(ConfigArgs *c) { index_intlen_strlen = SLAP_INDEX_INTLEN_STRLEN( index_intlen ); break; - + case CFG_SORTVALS: { ADlist *svnew = NULL, *svtail, *sv; diff --git a/servers/slapd/proto-slap.h b/servers/slapd/proto-slap.h index 198303d786..9516bb508b 100644 --- a/servers/slapd/proto-slap.h +++ b/servers/slapd/proto-slap.h @@ -1771,6 +1771,8 @@ LDAP_SLAPD_V( int ) schema_init_done; LDAP_SLAPD_F (int) slap_schema_init LDAP_P((void)); LDAP_SLAPD_F (void) schema_destroy LDAP_P(( void )); +LDAP_SLAPD_F (int) slap_hash64 LDAP_P((int)); + LDAP_SLAPD_F( slap_mr_indexer_func ) octetStringIndexer; LDAP_SLAPD_F( slap_mr_filter_func ) octetStringFilter; diff --git a/servers/slapd/schema_init.c b/servers/slapd/schema_init.c index 080bd6a7ad..08ef8437ef 100644 --- a/servers/slapd/schema_init.c +++ b/servers/slapd/schema_init.c @@ -105,12 +105,57 @@ #include "lutil.h" #include "lutil_hash.h" + +#ifdef LUTIL_HASH64_BYTES +#define HASH_BYTES LUTIL_HASH64_BYTES +#define HASH_LEN hashlen +static void (*hashinit)(lutil_HASH_CTX *ctx) = lutil_HASHInit; +static void (*hashupdate)(lutil_HASH_CTX *ctx,unsigned char const *buf, ber_len_t len) = lutil_HASHUpdate; +static void (*hashfinal)(unsigned char digest[HASH_BYTES], lutil_HASH_CTX *ctx) = lutil_HASHFinal; +static int hashlen = LUTIL_HASH_BYTES; +#define HASH_Init(c) hashinit(c) +#define HASH_Update(c,buf,len) hashupdate(c,buf,len) +#define HASH_Final(d,c) hashfinal(d,c) + +/* Toggle between 32 and 64 bit hashing, default to 32 for compatibility + -1 to query, returns 1 if 64 bit, 0 if 32. + 0/1 to set 32/64, returns 0 on success, -1 on failure */ +int slap_hash64( int onoff ) +{ + if ( onoff < 0 ) { + return hashlen == LUTIL_HASH64_BYTES; + } else if ( onoff ) { + hashinit = lutil_HASH64Init; + hashupdate = lutil_HASH64Update; + hashfinal = lutil_HASH64Final; + hashlen = LUTIL_HASH64_BYTES; + } else { + hashinit = lutil_HASHInit; + hashupdate = lutil_HASHUpdate; + hashfinal = lutil_HASHFinal; + hashlen = LUTIL_HASH_BYTES; + } + return 0; +} + +#else #define HASH_BYTES LUTIL_HASH_BYTES -#define HASH_CONTEXT lutil_HASH_CTX +#define HASH_LEN HASH_BYTES #define HASH_Init(c) lutil_HASHInit(c) #define HASH_Update(c,buf,len) lutil_HASHUpdate(c,buf,len) #define HASH_Final(d,c) lutil_HASHFinal(d,c) +int slap_has64( int onoff ) +{ + if ( onoff < 0 ) + return 0; + else + return onoff ? -1 : 0; +} + +#endif +#define HASH_CONTEXT lutil_HASH_CTX + /* approx matching rules */ #define directoryStringApproxMatchOID "1.3.6.1.4.1.4203.666.4.4" #define directoryStringApproxMatch approxMatch @@ -647,7 +692,7 @@ int octetStringIndexer( unsigned char HASHdigest[HASH_BYTES]; struct berval digest; digest.bv_val = (char *)HASHdigest; - digest.bv_len = sizeof(HASHdigest); + digest.bv_len = HASH_LEN; for( i=0; !BER_BVISNULL( &values[i] ); i++ ) { /* just count them */ @@ -693,7 +738,7 @@ int octetStringFilter( struct berval *value = (struct berval *) assertedValue; struct berval digest; digest.bv_val = (char *)HASHdigest; - digest.bv_len = sizeof(HASHdigest); + digest.bv_len = HASH_LEN; slen = syntax->ssyn_oidlen; mlen = mr->smr_oidlen; @@ -856,7 +901,7 @@ octetStringSubstringsIndexer( unsigned char HASHdigest[HASH_BYTES]; struct berval digest; digest.bv_val = (char *)HASHdigest; - digest.bv_len = sizeof(HASHdigest); + digest.bv_len = HASH_LEN; nkeys = 0; @@ -1021,7 +1066,7 @@ octetStringSubstringsFilter ( } digest.bv_val = (char *)HASHdigest; - digest.bv_len = sizeof(HASHdigest); + digest.bv_len = HASH_LEN; slen = syntax->ssyn_oidlen; mlen = mr->smr_oidlen; -- 2.39.5