moonchen commented on code in PR #13559:
URL: https://github.com/apache/trafficserver/pull/13559#discussion_r3817051960
##########
src/proxy/hdrs/HdrToken.cc:
##########
@@ -274,239 +264,309 @@ HdrTokenFieldInfo _hdrtoken_strs_field_initializers[] =
{
{nullptr, 0, 0,
HdrTokenInfoFlags::NONE
},
};
-} // end anonymous namespace
-
-const char *_hdrtoken_strs_heap_f = nullptr; // storage first byte
-const char *_hdrtoken_strs_heap_l = nullptr; // storage last byte
-
-int hdrtoken_num_wks = SIZEOF(_hdrtoken_strs); // # of well-known strings
-
-const char *hdrtoken_strs[SIZEOF(_hdrtoken_strs)]; // wks_idx
-> heap ptr
-int hdrtoken_str_lengths[SIZEOF(_hdrtoken_strs)]; // wks_idx
-> length
-HdrTokenType hdrtoken_str_token_types[SIZEOF(_hdrtoken_strs)]; // wks_idx
-> token type
-int32_t hdrtoken_str_slotids[SIZEOF(_hdrtoken_strs)]; // wks_idx
-> slot id
-uint64_t hdrtoken_str_masks[SIZEOF(_hdrtoken_strs)]; // wks_idx
-> presence mask
-HdrTokenInfoFlags hdrtoken_str_flags[SIZEOF(_hdrtoken_strs)]; // wks_idx
-> flags
+struct HdrTokenCacheControlBinding {
+ const char *name;
+ uint32_t mask;
+};
-DFA *hdrtoken_strs_dfa = nullptr;
+// The cooked mask for each Cache-Control directive. This is baked into the
well-known-string
+// table, so it belongs beside the other initializers rather than in MIME.cc.
+constexpr HdrTokenCacheControlBinding _hdrtoken_strs_cc_initializers[] = {
+ {"max-age", MIME_COOKED_MASK_CC_MAX_AGE },
+ {"no-cache", MIME_COOKED_MASK_CC_NO_CACHE },
+ {"no-store", MIME_COOKED_MASK_CC_NO_STORE },
+ {"no-transform", MIME_COOKED_MASK_CC_NO_TRANSFORM },
+ {"max-stale", MIME_COOKED_MASK_CC_MAX_STALE },
+ {"min-fresh", MIME_COOKED_MASK_CC_MIN_FRESH },
+ {"only-if-cached", MIME_COOKED_MASK_CC_ONLY_IF_CACHED },
+ {"public", MIME_COOKED_MASK_CC_PUBLIC },
+ {"private", MIME_COOKED_MASK_CC_PRIVATE },
+ {"must-revalidate", MIME_COOKED_MASK_CC_MUST_REVALIDATE },
+ {"proxy-revalidate", MIME_COOKED_MASK_CC_PROXY_REVALIDATE },
+ {"s-maxage", MIME_COOKED_MASK_CC_S_MAXAGE },
+ {"need-revalidate-once", MIME_COOKED_MASK_CC_NEED_REVALIDATE_ONCE},
+ {nullptr, 0 },
+};
/***********************************************************************
* *
- * H A S H T A B L E *
+ * C O M P I L E - T I M E W K S T A B L E *
* *
***********************************************************************/
-static constexpr size_t HDRTOKEN_HASH_TABLE_SIZE = 65536;
+// hash_to_slot() folds a hash down to this many bits, so the table needs
exactly one bucket per
+// value those bits can take.
+constexpr uint32_t HDRTOKEN_HASH_SLOT_BITS = 15;
+constexpr uint32_t HDRTOKEN_HASH_SLOT_MASK = (1 << HDRTOKEN_HASH_SLOT_BITS) -
1;
+constexpr size_t HDRTOKEN_HASH_TABLE_SIZE =
static_cast<size_t>(HDRTOKEN_HASH_SLOT_MASK) + 1;
-struct HdrTokenHashBucket {
- const char *wks;
- uint32_t hash;
-};
+constexpr uint32_t
+hash_to_slot(uint32_t hash)
+{
+ return ((hash >> HDRTOKEN_HASH_SLOT_BITS) ^ hash) & HDRTOKEN_HASH_SLOT_MASK;
+}
-HdrTokenHashBucket hdrtoken_hash_table[HDRTOKEN_HASH_TABLE_SIZE];
+constexpr unsigned char
+hdrtoken_ascii_toupper(unsigned char c)
+{
+ unsigned char const is_lower = static_cast<unsigned
char>((static_cast<unsigned>(c) - 'a') < 26u);
-/**
- basic FNV hash
-**/
-#define TINY_MASK(x) (((uint32_t)1 << (x)) - 1)
+ return static_cast<unsigned char>(c - (is_lower << 5));
+}
-inline uint32_t
-hash_to_slot(uint32_t hash)
+constexpr uint32_t HDRTOKEN_HASH_SEED = 0x811c9dc5u; // FNV-1a 32-bit offset
basis
+
+constexpr uint32_t
+hdrtoken_hash_step(uint32_t hval, unsigned char c)
{
- return ((hash >> 15) ^ hash) & TINY_MASK(15);
+ return (hval ^ hdrtoken_ascii_toupper(c)) * 0x01000193u;
}
-inline uint32_t
+constexpr uint32_t
hdrtoken_hash(const unsigned char *string, unsigned int length)
{
- ATSHash32FNV1a fnv;
- fnv.update(string, length, ATSHash::nocase());
- fnv.final();
- return fnv.get();
-}
+ uint32_t hval = HDRTOKEN_HASH_SEED;
-/*-------------------------------------------------------------------------
- -------------------------------------------------------------------------*/
+ for (unsigned int i = 0; i < length; i++) {
+ hval = hdrtoken_hash_step(hval, string[i]);
+ }
+ return hval;
+}
-void
-hdrtoken_hash_init()
+constexpr size_t
+hdrtoken_max_literal_length()
{
- uint32_t i;
- int num_collisions;
+ const auto longest = std::max_element(std::cbegin(_hdrtoken_strs),
std::cend(_hdrtoken_strs),
+ [](std::string_view a,
std::string_view b) { return a.length() < b.length(); });
+ return longest->length();
Review Comment:
`min_element`/`max_element` have been `constexpr` since C++14 (N3471);
`std::sort` and `adjacent_find` only became `constexpr` in C++20, which is why
the note singles those two out.
Checked against the oldest standard library in the CI matrix rather than
inferred: both `max_element` overloads are declared `_GLIBCXX14_CONSTEXPR` on
the libstdc++ 9 release branch. The Ubuntu job builds with clang-12 against
libstdc++ 9 and passes, as does FreeBSD on libc++. Leaving as is.
##########
src/proxy/hdrs/HdrToken.cc:
##########
@@ -274,239 +264,309 @@ HdrTokenFieldInfo _hdrtoken_strs_field_initializers[] =
{
{nullptr, 0, 0,
HdrTokenInfoFlags::NONE
},
};
-} // end anonymous namespace
-
-const char *_hdrtoken_strs_heap_f = nullptr; // storage first byte
-const char *_hdrtoken_strs_heap_l = nullptr; // storage last byte
-
-int hdrtoken_num_wks = SIZEOF(_hdrtoken_strs); // # of well-known strings
-
-const char *hdrtoken_strs[SIZEOF(_hdrtoken_strs)]; // wks_idx
-> heap ptr
-int hdrtoken_str_lengths[SIZEOF(_hdrtoken_strs)]; // wks_idx
-> length
-HdrTokenType hdrtoken_str_token_types[SIZEOF(_hdrtoken_strs)]; // wks_idx
-> token type
-int32_t hdrtoken_str_slotids[SIZEOF(_hdrtoken_strs)]; // wks_idx
-> slot id
-uint64_t hdrtoken_str_masks[SIZEOF(_hdrtoken_strs)]; // wks_idx
-> presence mask
-HdrTokenInfoFlags hdrtoken_str_flags[SIZEOF(_hdrtoken_strs)]; // wks_idx
-> flags
+struct HdrTokenCacheControlBinding {
+ const char *name;
+ uint32_t mask;
+};
-DFA *hdrtoken_strs_dfa = nullptr;
+// The cooked mask for each Cache-Control directive. This is baked into the
well-known-string
+// table, so it belongs beside the other initializers rather than in MIME.cc.
+constexpr HdrTokenCacheControlBinding _hdrtoken_strs_cc_initializers[] = {
+ {"max-age", MIME_COOKED_MASK_CC_MAX_AGE },
+ {"no-cache", MIME_COOKED_MASK_CC_NO_CACHE },
+ {"no-store", MIME_COOKED_MASK_CC_NO_STORE },
+ {"no-transform", MIME_COOKED_MASK_CC_NO_TRANSFORM },
+ {"max-stale", MIME_COOKED_MASK_CC_MAX_STALE },
+ {"min-fresh", MIME_COOKED_MASK_CC_MIN_FRESH },
+ {"only-if-cached", MIME_COOKED_MASK_CC_ONLY_IF_CACHED },
+ {"public", MIME_COOKED_MASK_CC_PUBLIC },
+ {"private", MIME_COOKED_MASK_CC_PRIVATE },
+ {"must-revalidate", MIME_COOKED_MASK_CC_MUST_REVALIDATE },
+ {"proxy-revalidate", MIME_COOKED_MASK_CC_PROXY_REVALIDATE },
+ {"s-maxage", MIME_COOKED_MASK_CC_S_MAXAGE },
+ {"need-revalidate-once", MIME_COOKED_MASK_CC_NEED_REVALIDATE_ONCE},
+ {nullptr, 0 },
+};
/***********************************************************************
* *
- * H A S H T A B L E *
+ * C O M P I L E - T I M E W K S T A B L E *
* *
***********************************************************************/
-static constexpr size_t HDRTOKEN_HASH_TABLE_SIZE = 65536;
+// hash_to_slot() folds a hash down to this many bits, so the table needs
exactly one bucket per
+// value those bits can take.
+constexpr uint32_t HDRTOKEN_HASH_SLOT_BITS = 15;
+constexpr uint32_t HDRTOKEN_HASH_SLOT_MASK = (1 << HDRTOKEN_HASH_SLOT_BITS) -
1;
+constexpr size_t HDRTOKEN_HASH_TABLE_SIZE =
static_cast<size_t>(HDRTOKEN_HASH_SLOT_MASK) + 1;
-struct HdrTokenHashBucket {
- const char *wks;
- uint32_t hash;
-};
+constexpr uint32_t
+hash_to_slot(uint32_t hash)
+{
+ return ((hash >> HDRTOKEN_HASH_SLOT_BITS) ^ hash) & HDRTOKEN_HASH_SLOT_MASK;
+}
-HdrTokenHashBucket hdrtoken_hash_table[HDRTOKEN_HASH_TABLE_SIZE];
+constexpr unsigned char
+hdrtoken_ascii_toupper(unsigned char c)
+{
+ unsigned char const is_lower = static_cast<unsigned
char>((static_cast<unsigned>(c) - 'a') < 26u);
-/**
- basic FNV hash
-**/
-#define TINY_MASK(x) (((uint32_t)1 << (x)) - 1)
+ return static_cast<unsigned char>(c - (is_lower << 5));
+}
Review Comment:
Agreed, switched to the plain ASCII-range form.
The terse version was presumably for the runtime hashing path, but that does
not hold up: at `-O2` both forms produce equivalent code (19 vs 18
instructions, same number of branch/select instructions), and a `static_assert`
sweep confirms they agree on all 256 byte values. The generated
well-known-string table is byte-for-byte unchanged.
##########
include/proxy/hdrs/HdrToken.h:
##########
@@ -109,8 +115,7 @@ extern HdrTokenInfoFlags hdrtoken_str_flags[];
////////////////////////////////////////////////////////////////////////////
extern void hdrtoken_init();
-extern int hdrtoken_tokenize_dfa(const char *string, int string_len,
const char **wks_string_out = nullptr);
-extern int hdrtoken_tokenize(const char *string, int string_len, const
char **wks_string_out = nullptr);
+int hdrtoken_tokenize(const char *string, int string_len, const
char **wks_string_out = nullptr);
Review Comment:
Good catch, this was unintentional. Upstream has `extern int
hdrtoken_tokenize(...)`; the `extern` was lost when the adjacent
`hdrtoken_tokenize_dfa` declaration was deleted. Restored, along with the
alignment of that declaration block.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
