Repository: trafficserver Updated Branches: refs/heads/master be237ea7e -> d08db5d46
TS-3400: Use common FNV hash code everywhere Remove 3 implementations of the FNV hashing algorithm in preference to the copy we have in libts. Add simple case-insensitive hashing support to the common implementation (using toupper so we remain compatible). Coverity CID #1021863 Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/d08db5d4 Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/d08db5d4 Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/d08db5d4 Branch: refs/heads/master Commit: d08db5d46a979ec9dd4a4d00fa560858096579d6 Parents: be237ea Author: James Peach <[email protected]> Authored: Thu Jan 29 11:14:27 2015 -0800 Committer: James Peach <[email protected]> Committed: Mon Feb 23 09:34:15 2015 -0800 ---------------------------------------------------------------------- CHANGES | 4 +++- iocore/hostdb/I_HostDBProcessor.h | 21 ++++++++------------ lib/ts/Hash.h | 9 +++++++++ lib/ts/HashFNV.cc | 29 ++-------------------------- lib/ts/HashFNV.h | 35 ++++++++++++++++++++++++++++++++-- proxy/hdrs/HdrToken.cc | 15 ++++----------- proxy/logstats.cc | 10 ++++------ 7 files changed, 63 insertions(+), 60 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d08db5d4/CHANGES ---------------------------------------------------------------------- diff --git a/CHANGES b/CHANGES index a286ec5..ea982c8 100644 --- a/CHANGES +++ b/CHANGES @@ -1,6 +1,8 @@ -*- coding: utf-8 -*- Changes with Apache Traffic Server 5.3.0 - + + *) [TS-3400] Use common FNV hash code everywhere. + *) [TS-3334] Restore default for proxy.config.proxy_name. *) [TS-3345] cacheurl plugin: Better error handling on config problems. http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d08db5d4/iocore/hostdb/I_HostDBProcessor.h ---------------------------------------------------------------------- diff --git a/iocore/hostdb/I_HostDBProcessor.h b/iocore/hostdb/I_HostDBProcessor.h index c26a403..ab1f3ed 100644 --- a/iocore/hostdb/I_HostDBProcessor.h +++ b/iocore/hostdb/I_HostDBProcessor.h @@ -64,20 +64,15 @@ static inline unsigned int makeHostHash(const char *string) { ink_assert(string && *string); - if (!string || *string == 0) - return 0; - - const uint32_t InitialFNV = 2166136261U; - const int32_t FNVMultiple = 16777619; - - uint64_t hash = InitialFNV; - uint32_t *p = (uint32_t *) &hash; - while(*string) { - p[0] = p[0] ^ (toupper(*string)); - hash = (p[1] ^ p[0]) * FNVMultiple; - ++string; + + if (string && *string) { + ATSHash32FNV1a fnv; + fnv.update(string, strlen(string), ATSHash::nocase()); + fnv.final(); + return fnv.get(); } - return (p[1] ^ p[0]); + + return 0; } // http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d08db5d4/lib/ts/Hash.h ---------------------------------------------------------------------- diff --git a/lib/ts/Hash.h b/lib/ts/Hash.h index bd67e2c..2306389 100644 --- a/lib/ts/Hash.h +++ b/lib/ts/Hash.h @@ -24,6 +24,7 @@ #include <cstddef> #include <stdint.h> +#include <ctype.h> struct ATSHashBase { @@ -35,6 +36,14 @@ struct ATSHashBase struct ATSHash:ATSHashBase { + struct nullxfrm { + uint8_t operator() (uint8_t byte) const { return byte; } + }; + + struct nocase { + uint8_t operator() (uint8_t byte) const { return toupper(byte); } + }; + virtual const void *get(void) const = 0; virtual size_t size(void) const = 0; virtual bool operator==(const ATSHash &) const; http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d08db5d4/lib/ts/HashFNV.cc ---------------------------------------------------------------------- diff --git a/lib/ts/HashFNV.cc b/lib/ts/HashFNV.cc index 36042a9..c4897bb 100644 --- a/lib/ts/HashFNV.cc +++ b/lib/ts/HashFNV.cc @@ -9,8 +9,8 @@ #include "HashFNV.h" -#define FNV_INIT_32 ((uint32_t)0x811c9dc5) -#define FNV_INIT_64 ((uint64_t)0xcbf29ce484222325ULL) +static const uint32_t FNV_INIT_32 = 0x811c9dc5u; +static const uint64_t FNV_INIT_64 = 0xcbf29ce484222325ull; // FNV-1a 64bit ATSHash32FNV1a::ATSHash32FNV1a(void) @@ -19,18 +19,6 @@ ATSHash32FNV1a::ATSHash32FNV1a(void) } void -ATSHash32FNV1a::update(const void *data, size_t len) -{ - uint8_t *bp = (uint8_t *) data; - uint8_t *be = bp + len; - - while (bp < be) { - hval ^= (uint32_t) *bp++; - hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24); - } -} - -void ATSHash32FNV1a::final(void) { } @@ -52,19 +40,6 @@ ATSHash64FNV1a::ATSHash64FNV1a(void) { this->clear(); } - -void -ATSHash64FNV1a::update(const void *data, size_t len) -{ - uint8_t *bp = (uint8_t *) data; - uint8_t *be = bp + len; - - while (bp < be) { - hval ^= (uint64_t) *bp++; - hval += (hval << 1) + (hval << 4) + (hval << 5) + (hval << 7) + (hval << 8) + (hval << 40); - } -} - void ATSHash64FNV1a::final(void) { http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d08db5d4/lib/ts/HashFNV.h ---------------------------------------------------------------------- diff --git a/lib/ts/HashFNV.h b/lib/ts/HashFNV.h index 9fec580..4467b7a 100644 --- a/lib/ts/HashFNV.h +++ b/lib/ts/HashFNV.h @@ -34,7 +34,10 @@ struct ATSHash32FNV1a:ATSHash32 { ATSHash32FNV1a(void); - void update(const void *data, size_t len); + + template <typename Transform> void update(const void *data, size_t len, Transform xfrm); + void update(const void *data, size_t len) { update(data, len, ATSHash::nullxfrm()); } + void final(void); uint32_t get(void) const; void clear(void); @@ -43,10 +46,25 @@ private: uint32_t hval; }; +template <typename Transform> void +ATSHash32FNV1a::update(const void *data, size_t len, Transform xfrm) +{ + uint8_t *bp = (uint8_t *) data; + uint8_t *be = bp + len; + + for (; bp < be; ++bp) { + hval ^= (uint32_t) xfrm(*bp); + hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24); + } +} + struct ATSHash64FNV1a:ATSHash64 { ATSHash64FNV1a(void); - void update(const void *data, size_t len); + + template <typename Transform> void update(const void *data, size_t len, Transform xfrm); + void update(const void *data, size_t len) { update(data, len, ATSHash::nullxfrm()); } + void final(void); uint64_t get(void) const; void clear(void); @@ -55,4 +73,17 @@ private: uint64_t hval; }; + +template <typename Transform> void +ATSHash64FNV1a::update(const void *data, size_t len, Transform xfrm) +{ + uint8_t *bp = (uint8_t *) data; + uint8_t *be = bp + len; + + for (; bp < be; ++bp) { + hval ^= (uint64_t) xfrm(*bp); + hval += (hval << 1) + (hval << 4) + (hval << 5) + (hval << 7) + (hval << 8) + (hval << 40); + } +} + #endif http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d08db5d4/proxy/hdrs/HdrToken.cc ---------------------------------------------------------------------- diff --git a/proxy/hdrs/HdrToken.cc b/proxy/hdrs/HdrToken.cc index 4bcf956..9f012e6 100644 --- a/proxy/hdrs/HdrToken.cc +++ b/proxy/hdrs/HdrToken.cc @@ -368,17 +368,10 @@ hash_to_slot(uint32_t hash) inline uint32_t hdrtoken_hash(const unsigned char *string, unsigned int length) { - static const uint32_t InitialFNV = 2166136261U; - static const int32_t FNVMultiple = 16777619; - - uint32_t hash = InitialFNV; - - for (size_t i = 0; i < length; i++) { - hash = hash ^ (toupper(string[i])); - hash = hash * FNVMultiple; - } - - return hash; + ATSHash32FNV1a fnv; + fnv.update(string, length, ATSHash::nocase()); + fnv.final(); + return fnv.get(); } /*------------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/trafficserver/blob/d08db5d4/proxy/logstats.cc ---------------------------------------------------------------------- diff --git a/proxy/logstats.cc b/proxy/logstats.cc index fdd4417..92cbe7c 100644 --- a/proxy/logstats.cc +++ b/proxy/logstats.cc @@ -329,16 +329,14 @@ struct eqstr struct hash_fnv32 { inline uint32_t operator()(const char* s) const { - uint32_t hval = (uint32_t)0x811c9dc5; /* FNV1_32_INIT */ + ATSHash32FNV1a fnv; if (s) { - while (*s) { - hval ^= (uint32_t)*s++; - hval *= (uint32_t)0x01000193; /* FNV_32_PRIME */ - } + fnv.update(s, strlen(s)); } - return hval; + fnv.final(); + return fnv.get(); } };
