You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by zw...@apache.org on 2011/12/01 23:51:36 UTC
svn commit: r1209291 - in /trafficserver/traffic/trunk: CHANGES
proxy/hdrs/HdrToken.cc proxy/hdrs/MIME.cc
Author: zwoop
Date: Thu Dec 1 22:51:35 2011
New Revision: 1209291
URL: http://svn.apache.org/viewvc?rev=1209291&view=rev
Log:
TS-1030 Improve hashing mechanism on WKS.
Modified:
trafficserver/traffic/trunk/CHANGES
trafficserver/traffic/trunk/proxy/hdrs/HdrToken.cc
trafficserver/traffic/trunk/proxy/hdrs/MIME.cc
Modified: trafficserver/traffic/trunk/CHANGES
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/CHANGES?rev=1209291&r1=1209290&r2=1209291&view=diff
==============================================================================
--- trafficserver/traffic/trunk/CHANGES (original)
+++ trafficserver/traffic/trunk/CHANGES Thu Dec 1 22:51:35 2011
@@ -1,6 +1,9 @@
-*- coding: utf-8 -*-
Changes with Apache Traffic Server 3.1.2
- *) [TS-1028] Avoid triggering assert when running debug build and enabling per-thread connection pols
+ *) [TS-1030] Improve hashing mechanism on WKS.
+
+ *) [TS-1028] Avoid triggering assert when running debug build and enabling
+ per-thread connection pols
*) [TS-1021] Remove extra newline from binary logs.
Modified: trafficserver/traffic/trunk/proxy/hdrs/HdrToken.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/proxy/hdrs/HdrToken.cc?rev=1209291&r1=1209290&r2=1209291&view=diff
==============================================================================
--- trafficserver/traffic/trunk/proxy/hdrs/HdrToken.cc (original)
+++ trafficserver/traffic/trunk/proxy/hdrs/HdrToken.cc Thu Dec 1 22:51:35 2011
@@ -336,27 +336,36 @@ DFA *hdrtoken_strs_dfa = NULL;
struct HdrTokenHashBucket
{
const char *wks;
+ uint32_t hash;
};
HdrTokenHashBucket hdrtoken_hash_table[HDRTOKEN_HASH_TABLE_SIZE];
-#define TINY_MASK(x) (((u_int32_t)1<<(x))-1)
-
/**
basic FNV hash
**/
-inline unsigned int
+#define TINY_MASK(x) (((u_int32_t)1<<(x))-1)
+
+inline uint32_t
+hash_to_slot(uint32_t hash)
+{
+ return ((hash>>15) ^ hash) & TINY_MASK(15);
+}
+
+inline uint32_t
hdrtoken_hash(const unsigned char *string, unsigned int length)
{
- const uint32_t InitialFNV = 2166136261U;
- const int32_t FNVMultiple = 16777619;
+ static const uint32_t InitialFNV = 2166136261U;
+ static const int32_t FNVMultiple = 16777619;
uint32_t hash = InitialFNV;
- for(size_t i = 0; i < length; i++) {
+
+ for (size_t i = 0; i < length; i++) {
hash = hash ^ (toupper(string[i]));
hash = hash * FNVMultiple;
}
- return (((hash>>15) ^ hash) & TINY_MASK(15));
+
+ return hash;
}
/*-------------------------------------------------------------------------
@@ -498,7 +507,6 @@ const char *_hdrtoken_commonly_tokenized
// Header extensions
"X-Forwarded-For",
"TE",
-
};
/*-------------------------------------------------------------------------
@@ -507,14 +515,12 @@ const char *_hdrtoken_commonly_tokenized
void
hdrtoken_hash_init()
{
- unsigned int i;
+ uint32_t i;
int num_collisions;
- for (i = 0; i < HDRTOKEN_HASH_TABLE_SIZE; i++) {
- hdrtoken_hash_table[i].wks = NULL;
- }
-
+ memset(hdrtoken_hash_table, 0, sizeof(hdrtoken_hash_table));
num_collisions = 0;
+
for (i = 0; i < (int) SIZEOF(_hdrtoken_commonly_tokenized_strs); i++) {
// convert the common string to the well-known token
unsigned const char *wks;
@@ -523,14 +529,18 @@ hdrtoken_hash_init()
(const char **) &wks);
ink_release_assert(wks_idx >= 0);
- unsigned int slot = hdrtoken_hash(wks, hdrtoken_str_lengths[wks_idx]);
+ uint32_t hash = hdrtoken_hash(wks, hdrtoken_str_lengths[wks_idx]);
+ uint32_t slot = hash_to_slot(hash);
+
if (hdrtoken_hash_table[slot].wks) {
printf("ERROR: hdrtoken_hash_table[%u] collision: '%s' replacing '%s'\n",
slot, (const char*)wks, hdrtoken_hash_table[slot].wks);
++num_collisions;
}
- hdrtoken_hash_table[slot].wks = (const char *) wks;
+ hdrtoken_hash_table[slot].wks = (const char *)wks;
+ hdrtoken_hash_table[slot].hash = hash;
}
+
if (num_collisions > 0)
abort();
}
@@ -549,7 +559,7 @@ hdrtoken_hash_init()
static inline unsigned int
snap_up_to_multiple(unsigned int n, unsigned int unit)
{
- return (((n + (unit - 1)) / unit) * unit);
+ return ((n + (unit - 1)) / unit) * unit;
}
/**
@@ -673,7 +683,7 @@ hdrtoken_tokenize_dfa(const char *string
}
//printf("hdrtoken_tokenize_dfa(%d,*s) - return %d\n",string_len,string,wks_idx);
- return (wks_idx);
+ return wks_idx;
}
/*-------------------------------------------------------------------------
@@ -691,19 +701,23 @@ hdrtoken_tokenize(const char *string, in
wks_idx = hdrtoken_wks_to_index(string);
if (wks_string_out)
*wks_string_out = string;
- return (wks_idx);
+ return wks_idx;
}
- unsigned int slot = hdrtoken_hash((const unsigned char *) string, (unsigned int) string_len);
+ uint32_t hash = hdrtoken_hash((const unsigned char *) string, (unsigned int) string_len);
+ uint32_t slot = hash_to_slot(hash);
+
bucket = &(hdrtoken_hash_table[slot]);
if ((bucket->wks != NULL) &&
+ (bucket->hash == hash) &&
(hdrtoken_wks_to_length(bucket->wks) == string_len)) {
wks_idx = hdrtoken_wks_to_index(bucket->wks);
if (wks_string_out)
*wks_string_out = bucket->wks;
- return (wks_idx);
+ return wks_idx;
}
+ Debug("hdr_token", "Did not find a WKS for '%.*s'", string_len, string);
return -1;
}
@@ -715,7 +729,7 @@ hdrtoken_string_to_wks(const char *strin
{
const char *wks = NULL;
hdrtoken_tokenize(string, (int) strlen(string), &wks);
- return (wks);
+ return wks;
}
/*-------------------------------------------------------------------------
@@ -726,5 +740,5 @@ hdrtoken_string_to_wks(const char *strin
{
const char *wks = NULL;
hdrtoken_tokenize(string, length, &wks);
- return (wks);
+ return wks;
}
Modified: trafficserver/traffic/trunk/proxy/hdrs/MIME.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/proxy/hdrs/MIME.cc?rev=1209291&r1=1209290&r2=1209291&view=diff
==============================================================================
--- trafficserver/traffic/trunk/proxy/hdrs/MIME.cc (original)
+++ trafficserver/traffic/trunk/proxy/hdrs/MIME.cc Thu Dec 1 22:51:35 2011
@@ -572,8 +572,8 @@ mime_hdr_sanity_check(MIMEHdrImpl * mh)
const char *wks = hdrtoken_index_to_wks(field->m_wks_idx);
int len = hdrtoken_index_to_length(field->m_wks_idx);
- ink_release_assert(field->m_len_name == len);
- ink_release_assert(strncasecmp(field->m_ptr_name, wks, field->m_len_name) == 0);
+ if (field->m_len_name != len || strncasecmp(field->m_ptr_name, wks, field->m_len_name) != 0)
+ Warning("Encountered WKS hash collision on '%.*s'", field->m_len_name, field->m_ptr_name);
uint64_t mask = mime_field_presence_mask(field->m_wks_idx);
masksum |= mask;