diff options
| author | jgraettinger@chromium.org <jgraettinger@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98> | 2014-04-29 17:02:06 +0000 |
|---|---|---|
| committer | jgraettinger@chromium.org <jgraettinger@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98> | 2014-04-29 17:02:06 +0000 |
| commit | 144a8c7521ce8ad02137f1b440750fdedca5e7c3 (patch) | |
| tree | 78f007032b0a2d7b671af077593d9a1bdaa85f51 | |
| parent | 04a5dfa93f3185d189452aee72bdc259df33f11b (diff) | |
| download | chromium_src-144a8c7521ce8ad02137f1b440750fdedca5e7c3.zip chromium_src-144a8c7521ce8ad02137f1b440750fdedca5e7c3.tar.gz chromium_src-144a8c7521ce8ad02137f1b440750fdedca5e7c3.tar.bz2 | |
SPDY & HPACK: Land recent internal changes (through 65328503)
Refactor RST_STREAM status code handling. Also handle SPDY4/HTTP2 status codes.
Fix an off-by-one DCHECK for frame lengths equal to the frame limit.
This lands server change 63285101 by raullenchai and 63409085 by hkhalil.
https://codereview.chromium.org/243643002/
Refactor GOAWAY status code handling, also handle SPDY4/HTTP2 status codes.
This lands server change 63424889 by hkhalil.
https://codereview.chromium.org/243613003/
SPDY tests: Additional headers validation in framer tests.
Server change also included logic to lower-case headers and error on responses with incorrect casing. This wasn't merged, as Chromium instead has handling and tests on this in SpdyStream.
This lands server change 63898388 by mlavan.
https://codereview.chromium.org/244833003/
SPDY: Replace SerializeDataFrameHeader.
Replaced with SerializeDataFrameHeaderWithPaddingLengthField, which serializes
DATA frame header and, when necessary, padding length fields. Tests are added.
This lands server change 64328823 by raullenchai.
https://codereview.chromium.org/244853004/
Modify SerializeHeaders, SerializePushPromise and SpdyFrameBuilder so that
HEADERS and PUSH_PROMISE frame payloads can be serialized into CONTINUATION
frames as needed.
This lands server change 64331353 by mlavan.
https://codereview.chromium.org/246013002/
SPDY: RST_STREAM and GO_AWAY status checking.
Call OnError() from ProcessRstStreamFramePayload() and
ProcessGoAwayFramePayload() when handling an invalid status code.
This lands server change 64372977 by mlavan.
https://codereview.chromium.org/247503002/
SPDY: Fix flaky padding edge case.
The root cause of the flakiness is: during the processing of data frame, the
visitor should be informed if the FIN flag is set and there is no more data in
this frame. One corner case that has not been covered is when
remaining_data_length_ = remaining_padding_payload_length_ = 0, which does
happen when the data payload is empty (e.g., GET request) and the padding len
is exactly 1.
This lands server change 64513441 by raullenchai.
https://codereview.chromium.org/246933003/
SPDY: Use SpdyMajorVersion rather than ints for SPDY version number.
Version comparisons are canonicalized on using the lowest applicable version
number. Also add new SPDY5 enum (just the literal; no implementation).
Fix a bug in cl/64786464 that could cause SPDY version to be
mis-parsed in the framer.
This lands server change 64786464 by mlavan and 64899106 by mlavan.
https://codereview.chromium.org/247243003/
Remove net:: when referencing types from code locations already within the net:: namespace.
Remove obsolete TODO.
This lands server change 64909661 by hkhalil and 64909678 by hkhalil.
https://codereview.chromium.org/246123005/
SPDY: Catch another edge case in version validation.
Specifically, where the version number is invalid, but happens to match the
enum number of a valid version. Also consolidate version checks in the framer
so that related logic is easier to reason about.
This lands server change 64912010 by mlavan.
https://codereview.chromium.org/247583002/
HPACK: Refactor and expand HpackHeaderTable indexing.
HpackHeaderTable now maintains indices for querying static and dynamic
entries by name and name & value. Indicies are ordered on entry name,
value, then table index. A full-table index is maintained, as well as a
reference-set index.
HpackEntry no longer tracks reference-set status (that's HpackHeaderTable's
job), and the "touch" mechanism has been replaced with a similar "state".
HpackHeaderTable & HpackEntry also now cooperate to provide HpackEntry with
sufficient bookmarking to compute it's own index.
HpackEncodingContext has been eliminated. HpackHeaderTable manages its
former responsibilities (primarly managing the static table).
Together, these changes allow an encoder to:
* Build the encoding delta via a linear walk through (just) the reference set
(assuming headers are already sorted, ala std::map).
* Map representations to entries in O(log(N)) time, preferring the
lowest-index entry.
* Determine a mapped entry's index in O(1) time.
* Add and evict representations to the dynamic table in O(log(N)) time.
* Efficiently enumerate all headers having a specific name. Not required now,
but may be in the future.
This lands server change 65185410 by jgraettinger.
https://codereview.chromium.org/246383003/
HPACK: Refactor and simplify HpackOutputStream
HpackOutputStream is no longer responsible for emitting entire opcodes. That
will be the encoder's job. Instead, it simply provides primitives for emitting
prefixes, varints, and byte arrays. The longer-term intent is that
HpackOutputStream will be merged into SpdyFrameBuilder and eliminated
altogether.
HpackOutputStream also no longer asserts a maximum literal length. Rationale
is that we already have a theoretical too-long header at this point: we might
as well emit it and allow the remote decoder to possibly accept it. At worst
we break the connection, which was going to happen anyway.
This lands server change 65186763 by jgraettinger.
https://codereview.chromium.org/247793002/
HPACK: Add HpackHuffmanTable::EncodedSize()
EncodedSize() will be used by the HPACK encoder to select identity vs Huffman
coding, without having to run the full Huffman coder. Also update tests to
compare against EncodedSize() by default.
HPACK unittest: Fixing memory error in Huffman test fixture.
This lands server change 65187740 by jgraettinger and 65328503 by jgraettinger.
https://codereview.chromium.org/247893002/
HPACK: Implement delta encoding.
HpackEncoder determines each header set's delta with the reference set, and
makes use of the full HPACK encoding grammar to emit a minimal compression
for the set.
A "encode without compression" method has also been added which bypasses the
dynamic table & Huffman coding. Selection of encoding method is controlled by
SpdyFramer::enable_compression_.
Encoding context updates are not yet used. That's a future optimization.
HpackRoundTripTest has been added to verify that HpackEncoder & HpackDecoder
successfully round-trip sequences of canned and dynamically generated header
sets.
This lands server change 65188922 by jgraettinger.
https://codereview.chromium.org/247283003/
BUG=345769,339578
Review URL: https://codereview.chromium.org/246073007
git-svn-id: svn://svn.chromium.org/chrome/trunk/src@266904 0039d316-1c4b-4281-b951-d872f2087c98
40 files changed, 3332 insertions, 1785 deletions
diff --git a/net/net.gypi b/net/net.gypi index 043e22e..22e8f0b 100644 --- a/net/net.gypi +++ b/net/net.gypi @@ -1014,8 +1014,6 @@ 'spdy/hpack_decoder.h', 'spdy/hpack_encoder.cc', 'spdy/hpack_encoder.h', - 'spdy/hpack_encoding_context.cc', - 'spdy/hpack_encoding_context.h', 'spdy/hpack_entry.cc', 'spdy/hpack_entry.h', 'spdy/hpack_header_table.cc', @@ -1577,12 +1575,12 @@ 'spdy/buffered_spdy_framer_unittest.cc', 'spdy/hpack_decoder_test.cc', 'spdy/hpack_encoder_test.cc', - 'spdy/hpack_encoding_context_test.cc', 'spdy/hpack_entry_test.cc', 'spdy/hpack_header_table_test.cc', 'spdy/hpack_huffman_table_test.cc', 'spdy/hpack_input_stream_test.cc', 'spdy/hpack_output_stream_test.cc', + 'spdy/hpack_round_trip_test.cc', 'spdy/hpack_string_util_test.cc', 'spdy/mock_spdy_framer_visitor.cc', 'spdy/mock_spdy_framer_visitor.h', diff --git a/net/quic/spdy_utils.cc b/net/quic/spdy_utils.cc index 350819e..c0894d5 100644 --- a/net/quic/spdy_utils.cc +++ b/net/quic/spdy_utils.cc @@ -16,7 +16,7 @@ namespace net { // static string SpdyUtils::SerializeUncompressedHeaders(const SpdyHeaderBlock& headers) { int length = SpdyFramer::GetSerializedLength(SPDY3, &headers); - SpdyFrameBuilder builder(length); + SpdyFrameBuilder builder(length, SPDY3); SpdyFramer::WriteHeaderBlock(&builder, SPDY3, &headers); scoped_ptr<SpdyFrame> block(builder.take()); return string(block->data(), length); diff --git a/net/spdy/hpack_decoder.cc b/net/spdy/hpack_decoder.cc index 2e1d500..6aa4f59a4 100644 --- a/net/spdy/hpack_decoder.cc +++ b/net/spdy/hpack_decoder.cc @@ -15,16 +15,20 @@ namespace net { using base::StringPiece; using std::string; +namespace { + +const uint8 kNoState = 0; +// Set on entries added to the reference set during this decoding. +const uint8 kReferencedThisEncoding = 1; + +} // namespace + HpackDecoder::HpackDecoder(const HpackHuffmanTable& table) : max_string_literal_size_(kDefaultMaxStringLiteralSize), huffman_table_(table) {} HpackDecoder::~HpackDecoder() {} -void HpackDecoder::ApplyHeaderTableSizeSetting(uint32 max_size) { - context_.ApplyHeaderTableSizeSetting(max_size); -} - bool HpackDecoder::HandleControlFrameHeadersData(SpdyStreamId id, const char* headers_data, size_t headers_data_length) { @@ -50,13 +54,19 @@ bool HpackDecoder::HandleControlFrameHeadersComplete(SpdyStreamId id) { headers_block_buffer_.clear(); // Emit everything in the reference set that hasn't already been emitted. - for (size_t i = 1; i <= context_.GetMutableEntryCount(); ++i) { - if (context_.IsReferencedAt(i) && - (context_.GetTouchCountAt(i) == HpackEncodingContext::kUntouched)) { - HandleHeaderRepresentation(context_.GetNameAt(i).as_string(), - context_.GetValueAt(i).as_string()); + // Also clear entry state for the next decoded headers block. + // TODO(jgraettinger): We may need to revisit the order in which headers + // are emitted (b/14051713). + for (HpackEntry::OrderedSet::const_iterator it = + header_table_.reference_set().begin(); + it != header_table_.reference_set().end(); ++it) { + HpackEntry* entry = *it; + + if (entry->state() == kNoState) { + HandleHeaderRepresentation(entry->name(), entry->value()); + } else { + entry->set_state(kNoState); } - context_.ClearTouchesAt(i); } // Emit the Cookie header, if any crumbles were encountered. if (!cookie_name_.empty()) { @@ -117,14 +127,19 @@ bool HpackDecoder::DecodeNextOpcode(HpackInputStream* input_stream) { bool HpackDecoder::DecodeNextContextUpdate(HpackInputStream* input_stream) { if (input_stream->MatchPrefixAndConsume(kEncodingContextEmptyReferenceSet)) { - return context_.ProcessContextUpdateEmptyReferenceSet(); + header_table_.ClearReferenceSet(); + return true; } if (input_stream->MatchPrefixAndConsume(kEncodingContextNewMaximumSize)) { uint32 size = 0; if (!input_stream->DecodeNextUint32(&size)) { return false; } - return context_.ProcessContextUpdateNewMaximumSize(size); + if (size > header_table_.settings_size_bound()) { + return false; + } + header_table_.SetMaxSize(size); + return true; } // Unrecognized encoding context update. return false; @@ -138,26 +153,26 @@ bool HpackDecoder::DecodeNextIndexedHeader(HpackInputStream* input_stream) { // If index == 0, |kEncodingContextOpcode| would have matched. CHECK_NE(index, 0u); - if (index > context_.GetEntryCount()) + HpackEntry* entry = header_table_.GetByIndex(index); + if (entry == NULL) return false; - bool emitted = false; - // The index will be put into the reference set. - if (!context_.IsReferencedAt(index)) { - HandleHeaderRepresentation(context_.GetNameAt(index).as_string(), - context_.GetValueAt(index).as_string()); - emitted = true; - } + if (entry->IsStatic()) { + HandleHeaderRepresentation(entry->name(), entry->value()); - uint32 new_index = 0; - std::vector<uint32> removed_referenced_indices; - if (!context_.ProcessIndexedHeader( - index, &new_index, &removed_referenced_indices)) { - return false; + HpackEntry* new_entry = header_table_.TryAddEntry( + entry->name(), entry->value()); + if (new_entry) { + header_table_.Toggle(new_entry); + new_entry->set_state(kReferencedThisEncoding); + } + } else { + entry->set_state(kNoState); + if (header_table_.Toggle(entry)) { + HandleHeaderRepresentation(entry->name(), entry->value()); + entry->set_state(kReferencedThisEncoding); + } } - if (emitted && new_index > 0) - context_.AddTouchesAt(new_index, 0); - return true; } @@ -176,16 +191,11 @@ bool HpackDecoder::DecodeNextLiteralHeader(HpackInputStream* input_stream, if (!should_index) return true; - uint32 new_index = 0; - std::vector<uint32> removed_referenced_indices; - if (!context_.ProcessLiteralHeaderWithIncrementalIndexing( - name, value, &new_index, &removed_referenced_indices)) { - return false; + HpackEntry* new_entry = header_table_.TryAddEntry(name, value); + if (new_entry) { + header_table_.Toggle(new_entry); + new_entry->set_state(kReferencedThisEncoding); } - - if (new_index > 0) - context_.AddTouchesAt(new_index, 0); - return true; } @@ -198,11 +208,16 @@ bool HpackDecoder::DecodeNextName( if (index_or_zero == 0) return DecodeNextStringLiteral(input_stream, true, next_name); - uint32 index = index_or_zero; - if (index > context_.GetEntryCount()) + const HpackEntry* entry = header_table_.GetByIndex(index_or_zero); + if (entry == NULL) { return false; - - *next_name = context_.GetNameAt(index_or_zero); + } else if (entry->IsStatic()) { + *next_name = entry->name(); + } else { + // |entry| could be evicted as part of this insertion. Preemptively copy. + key_buffer_.assign(entry->name()); + *next_name = key_buffer_; + } return true; } @@ -210,7 +225,7 @@ bool HpackDecoder::DecodeNextStringLiteral(HpackInputStream* input_stream, bool is_key, StringPiece* output) { if (input_stream->MatchPrefixAndConsume(kStringLiteralHuffmanEncoded)) { - string* buffer = is_key ? &huffman_key_buffer_ : &huffman_value_buffer_; + string* buffer = is_key ? &key_buffer_ : &value_buffer_; bool result = input_stream->DecodeNextHuffmanString(huffman_table_, buffer); *output = StringPiece(*buffer); return result; diff --git a/net/spdy/hpack_decoder.h b/net/spdy/hpack_decoder.h index 4e3dbea..ec2949b 100644 --- a/net/spdy/hpack_decoder.h +++ b/net/spdy/hpack_decoder.h @@ -13,7 +13,7 @@ #include "base/macros.h" #include "base/strings/string_piece.h" #include "net/base/net_export.h" -#include "net/spdy/hpack_encoding_context.h" +#include "net/spdy/hpack_header_table.h" #include "net/spdy/hpack_input_stream.h" #include "net/spdy/spdy_protocol.h" @@ -38,8 +38,9 @@ class NET_EXPORT_PRIVATE HpackDecoder { ~HpackDecoder(); // Called upon acknowledgement of SETTINGS_HEADER_TABLE_SIZE. - // See HpackEncodingContext::ApplyHeaderTableSizeSetting(). - void ApplyHeaderTableSizeSetting(uint32 max_size); + void ApplyHeaderTableSizeSetting(size_t size_setting) { + header_table_.SetSettingsHeaderTableSize(size_setting); + } // Called as headers data arrives. Returns false if an error occurred. // TODO(jgraettinger): A future version of this method will incrementally @@ -82,7 +83,7 @@ class NET_EXPORT_PRIVATE HpackDecoder { base::StringPiece value); const uint32 max_string_literal_size_; - HpackEncodingContext context_; + HpackHeaderTable header_table_; // Incrementally reconstructed cookie value. Name is also kept to preserve // input casing. @@ -97,7 +98,7 @@ class NET_EXPORT_PRIVATE HpackDecoder { // Huffman table to be applied to decoded Huffman literals, // and scratch space for storing those decoded literals. const HpackHuffmanTable& huffman_table_; - std::string huffman_key_buffer_, huffman_value_buffer_; + std::string key_buffer_, value_buffer_; // Handlers for decoding HPACK opcodes and header representations // (or parts thereof). These methods return true on success and diff --git a/net/spdy/hpack_decoder_test.cc b/net/spdy/hpack_decoder_test.cc index 9631cd1..2a5fce1 100644 --- a/net/spdy/hpack_decoder_test.cc +++ b/net/spdy/hpack_decoder_test.cc @@ -23,18 +23,6 @@ namespace test { using base::StringPiece; using std::string; -class HpackEncodingContextPeer { - public: - explicit HpackEncodingContextPeer(const HpackEncodingContext& context) - : context_(context) {} - const HpackHeaderTable& header_table() { - return context_.header_table_; - } - - private: - const HpackEncodingContext& context_; -}; - class HpackDecoderPeer { public: explicit HpackDecoderPeer(HpackDecoder* decoder) @@ -46,8 +34,8 @@ class HpackDecoderPeer { bool DecodeNextName(HpackInputStream* in, StringPiece* out) { return decoder_->DecodeNextName(in, out); } - HpackEncodingContextPeer context_peer() { - return HpackEncodingContextPeer(decoder_->context_); + const HpackHeaderTable& header_table() { + return decoder_->header_table_; } void set_cookie_name(string name) { decoder_->cookie_name_ = name; @@ -88,8 +76,7 @@ class HpackDecoderTest : public ::testing::Test { protected: HpackDecoderTest() : decoder_(ObtainHpackHuffmanTable()), - decoder_peer_(&decoder_), - context_peer_(decoder_peer_.context_peer()) {} + decoder_peer_(&decoder_) {} bool DecodeHeaderBlock(StringPiece str) { return decoder_.HandleControlFrameHeadersData(0, str.data(), str.size()) && @@ -109,7 +96,6 @@ class HpackDecoderTest : public ::testing::Test { HpackDecoder decoder_; test::HpackDecoderPeer decoder_peer_; - test::HpackEncodingContextPeer context_peer_; }; TEST_F(HpackDecoderTest, HandleControlFrameHeadersData) { @@ -257,36 +243,36 @@ TEST_F(HpackDecoderTest, InvalidIndexedHeader) { TEST_F(HpackDecoderTest, ContextUpdateMaximumSize) { EXPECT_EQ(kDefaultHeaderTableSizeSetting, - context_peer_.header_table().max_size()); + decoder_peer_.header_table().max_size()); { // Maximum-size update with size 126. Succeeds. EXPECT_TRUE(DecodeHeaderBlock(StringPiece("\x80\x7e", 2))); - EXPECT_EQ(126u, context_peer_.header_table().max_size()); + EXPECT_EQ(126u, decoder_peer_.header_table().max_size()); } string input; { // Maximum-size update with kDefaultHeaderTableSizeSetting. Succeeds. - HpackOutputStream output_stream(kuint32max); + HpackOutputStream output_stream; output_stream.AppendBits(0x80, 8); // Context update. output_stream.AppendBits(0x00, 1); // Size update. - output_stream.AppendUint32ForTest(kDefaultHeaderTableSizeSetting); + output_stream.AppendUint32(kDefaultHeaderTableSizeSetting); output_stream.TakeString(&input); EXPECT_TRUE(DecodeHeaderBlock(StringPiece(input))); EXPECT_EQ(kDefaultHeaderTableSizeSetting, - context_peer_.header_table().max_size()); + decoder_peer_.header_table().max_size()); } { // Maximum-size update with kDefaultHeaderTableSizeSetting + 1. Fails. - HpackOutputStream output_stream(kuint32max); + HpackOutputStream output_stream; output_stream.AppendBits(0x80, 8); // Context update. output_stream.AppendBits(0x00, 1); // Size update. - output_stream.AppendUint32ForTest(kDefaultHeaderTableSizeSetting + 1); + output_stream.AppendUint32(kDefaultHeaderTableSizeSetting + 1); output_stream.TakeString(&input); EXPECT_FALSE(DecodeHeaderBlock(StringPiece(input))); EXPECT_EQ(kDefaultHeaderTableSizeSetting, - context_peer_.header_table().max_size()); + decoder_peer_.header_table().max_size()); } } @@ -356,7 +342,7 @@ TEST_F(HpackDecoderTest, LiteralHeaderInvalidIndices) { // Round-tripping the header set from E.2.1 should work. TEST_F(HpackDecoderTest, BasicE21) { - HpackEncoder encoder; + HpackEncoder encoder(ObtainHpackHuffmanTable()); std::map<string, string> expected_header_set; expected_header_set[":method"] = "GET"; diff --git a/net/spdy/hpack_encoder.cc b/net/spdy/hpack_encoder.cc index 4690426..81d33ad 100644 --- a/net/spdy/hpack_encoder.cc +++ b/net/spdy/hpack_encoder.cc @@ -4,7 +4,11 @@ #include "net/spdy/hpack_encoder.h" -#include "base/strings/string_util.h" +#include <algorithm> + +#include "base/logging.h" +#include "net/spdy/hpack_header_table.h" +#include "net/spdy/hpack_huffman_table.h" #include "net/spdy/hpack_output_stream.h" namespace net { @@ -12,52 +16,249 @@ namespace net { using base::StringPiece; using std::string; -HpackEncoder::HpackEncoder() - : max_string_literal_size_(kDefaultMaxStringLiteralSize) {} +namespace { + +const uint8 kNoState = 0; +// Set on a referenced HpackEntry which is part of the current header set. +const uint8 kReferencedImplicitOn = 1; +// Set on a referenced HpackEntry which is not part of the current header set. +const uint8 kReferencedExplicitOff = 2; +// Set on a entries added to the reference set during this encoding. +const uint8 kReferencedThisEncoding = 3; + +} // namespace + +HpackEncoder::HpackEncoder(const HpackHuffmanTable& table) + : output_stream_(), + allow_huffman_compression_(true), + huffman_table_(table) {} HpackEncoder::~HpackEncoder() {} bool HpackEncoder::EncodeHeaderSet(const std::map<string, string>& header_set, string* output) { - // TOOD(jgraettinger): Do more sophisticated encoding. - HpackOutputStream output_stream(max_string_literal_size_); - for (std::map<string, string>::const_iterator it = header_set.begin(); - it != header_set.end(); ++it) { - // TODO(jgraettinger): HTTP/2 requires strict lowercasing of headers, - // and the permissiveness here isn't wanted. Back this out in upstream. - if (LowerCaseEqualsASCII(it->first, "cookie")) { - std::vector<StringPiece> crumbs; - CookieToCrumbs(it->second, &crumbs); - for (size_t i = 0; i != crumbs.size(); i++) { - if (!output_stream.AppendLiteralHeaderNoIndexingWithName( - it->first, crumbs[i])) { - return false; - } + // Walk the set of entries to encode, which are not already implied by the + // header table's reference set. They must be explicitly emitted. + Representations explicit_set(DetermineEncodingDelta(header_set)); + for (Representations::const_iterator it = explicit_set.begin(); + it != explicit_set.end(); ++it) { + // Try to find an exact match. Note that dynamic entries are preferred + // by the header table index. + HpackEntry* entry = header_table_.GetByNameAndValue(it->first, it->second); + if (entry != NULL && !entry->IsStatic()) { + // Already in the dynamic table. Simply toggle on. + CHECK_EQ(kNoState, entry->state()); + EmitDynamicIndex(entry); + continue; + } + + // Walk the set of entries to be evicted by this insertion. + HpackHeaderTable::EntryTable::iterator evict_begin, evict_end, evict_it; + header_table_.EvictionSet(it->first, it->second, &evict_begin, &evict_end); + + for (evict_it = evict_begin; evict_it != evict_end; ++evict_it) { + HpackEntry* evictee = &(*evict_it); + + if (evict_it->state() == kReferencedImplicitOn) { + // Issue twice to explicitly emit. + EmitDynamicIndex(evictee); + EmitDynamicIndex(evictee); + } else if (evictee->state() == kReferencedExplicitOff) { + // Eviction saves us from having to explicitly toggle off. + evictee->set_state(kNoState); + } else if (evictee->state() == kReferencedThisEncoding) { + // Already emitted. No action required. + evictee->set_state(kNoState); } - } else if (!output_stream.AppendLiteralHeaderNoIndexingWithName( - it->first, it->second)) { - return false; } + if (entry != NULL) { + EmitStaticIndex(entry); + } else { + EmitIndexedLiteral(*it); + } + } + // Walk the reference set, toggling off as needed and clearing encoding state. + for (HpackEntry::OrderedSet::const_iterator it = + header_table_.reference_set().begin(); + it != header_table_.reference_set().end();) { + HpackEntry* entry = *(it++); // Step to prevent invalidation. + CHECK_NE(kNoState, entry->state()); + + if (entry->state() == kReferencedExplicitOff) { + // Explicitly toggle off. + EmitDynamicIndex(entry); + } + entry->set_state(kNoState); } - output_stream.TakeString(output); + output_stream_.TakeString(output); return true; } -void HpackEncoder::CookieToCrumbs(StringPiece cookie, - std::vector<StringPiece>* out) { - out->clear(); +bool HpackEncoder::EncodeHeaderSetWithoutCompression( + const std::map<string, string>& header_set, + string* output) { + + allow_huffman_compression_ = false; + for (std::map<string, string>::const_iterator it = header_set.begin(); + it != header_set.end(); ++it) { + // Note that cookies are not crumbled in this case. + EmitNonIndexedLiteral(*it); + } + allow_huffman_compression_ = true; + output_stream_.TakeString(output); + return true; +} + +void HpackEncoder::EmitDynamicIndex(HpackEntry* entry) { + DCHECK(!entry->IsStatic()); + output_stream_.AppendPrefix(kIndexedOpcode); + output_stream_.AppendUint32(entry->Index()); + + entry->set_state(kNoState); + if (header_table_.Toggle(entry)) { + // Was added to the reference set. + entry->set_state(kReferencedThisEncoding); + } +} + +void HpackEncoder::EmitStaticIndex(HpackEntry* entry) { + DCHECK(entry->IsStatic()); + output_stream_.AppendPrefix(kIndexedOpcode); + output_stream_.AppendUint32(entry->Index()); + + HpackEntry* new_entry = header_table_.TryAddEntry(entry->name(), + entry->value()); + if (new_entry) { + // This is a static entry: no need to pin. + header_table_.Toggle(new_entry); + new_entry->set_state(kReferencedThisEncoding); + } +} + +void HpackEncoder::EmitIndexedLiteral(const Representation& representation) { + output_stream_.AppendPrefix(kLiteralIncrementalIndexOpcode); + EmitLiteral(representation); + + HpackEntry* new_entry = header_table_.TryAddEntry(representation.first, + representation.second); + if (new_entry) { + header_table_.Toggle(new_entry); + new_entry->set_state(kReferencedThisEncoding); + } +} + +void HpackEncoder::EmitNonIndexedLiteral( + const Representation& representation) { + output_stream_.AppendPrefix(kLiteralNoIndexOpcode); + output_stream_.AppendUint32(0); + EmitString(representation.first); + EmitString(representation.second); +} + +void HpackEncoder::EmitLiteral(const Representation& representation) { + const HpackEntry* name_entry = header_table_.GetByName(representation.first); + if (name_entry != NULL) { + output_stream_.AppendUint32(name_entry->Index()); + } else { + output_stream_.AppendUint32(0); + EmitString(representation.first); + } + EmitString(representation.second); +} + +void HpackEncoder::EmitString(StringPiece str) { + size_t encoded_size = (!allow_huffman_compression_ ? str.size() + : huffman_table_.EncodedSize(str)); + if (encoded_size < str.size()) { + output_stream_.AppendPrefix(kStringLiteralHuffmanEncoded); + output_stream_.AppendUint32(encoded_size); + huffman_table_.EncodeString(str, &output_stream_); + } else { + output_stream_.AppendPrefix(kStringLiteralIdentityEncoded); + output_stream_.AppendUint32(str.size()); + output_stream_.AppendBytes(str); + } +} + +// static +HpackEncoder::Representations HpackEncoder::DetermineEncodingDelta( + const std::map<string, string>& header_set) { + // Flatten & crumble headers into an ordered list of representations. + Representations full_set; + for (std::map<string, string>::const_iterator it = header_set.begin(); + it != header_set.end(); ++it) { + if (it->first == "cookie") { + // Crumble cookie, and sort the result crumbs. + size_t sort_offset = full_set.size(); + CookieToCrumbs(*it, &full_set); + std::sort(full_set.begin() + sort_offset, full_set.end()); + } else { + // Note std::map guarantees representations are ordered. + full_set.push_back(make_pair( + StringPiece(it->first), StringPiece(it->second))); + } + } + // Perform a linear merge of ordered representations with the (also ordered) + // reference set. Mark each referenced entry with current membership state, + // and gather representations which must be explicitly emitted. + Representations::const_iterator r_it = full_set.begin(); + HpackEntry::OrderedSet::const_iterator s_it = + header_table_.reference_set().begin(); + + Representations explicit_set; + while (r_it != full_set.end() && + s_it != header_table_.reference_set().end()) { + // Compare on name, then value. + int result = r_it->first.compare((*s_it)->name()); + if (result == 0) { + result = r_it->second.compare((*s_it)->value()); + } + + if (result < 0) { + explicit_set.push_back(*r_it); + ++r_it; + } else if (result > 0) { + (*s_it)->set_state(kReferencedExplicitOff); + ++s_it; + } else { + (*s_it)->set_state(kReferencedImplicitOn); + ++s_it; + ++r_it; + } + } + while (r_it != full_set.end()) { + explicit_set.push_back(*r_it); + ++r_it; + } + while (s_it != header_table_.reference_set().end()) { + (*s_it)->set_state(kReferencedExplicitOff); + ++s_it; + } + return explicit_set; +} + +// static +void HpackEncoder::CookieToCrumbs(const Representation& cookie, + Representations* out) { + // See Section 8.1.3.4 "Compressing the Cookie Header Field" in the HTTP/2 + // specification at http://tools.ietf.org/html/draft-ietf-httpbis-http2-11 + // Cookie values are split into individually-encoded HPACK representations. for (size_t pos = 0;;) { - size_t end = cookie.find(';', pos); + size_t end = cookie.second.find(";", pos); if (end == StringPiece::npos) { - out->push_back(cookie.substr(pos)); + out->push_back(make_pair( + cookie.first, + cookie.second.substr(pos))); return; } - out->push_back(cookie.substr(pos, end - pos)); + out->push_back(make_pair( + cookie.first, + cookie.second.substr(pos, end - pos))); // Consume next space if present. pos = end + 1; - if (pos != cookie.size() && cookie[pos] == ' ') { + if (pos != cookie.second.size() && cookie.second[pos] == ' ') { pos++; } } diff --git a/net/spdy/hpack_encoder.h b/net/spdy/hpack_encoder.h index 12fa8b4..df504f5 100644 --- a/net/spdy/hpack_encoder.h +++ b/net/spdy/hpack_encoder.h @@ -7,18 +7,22 @@ #include <map> #include <string> +#include <vector> #include "base/basictypes.h" #include "base/macros.h" #include "base/strings/string_piece.h" #include "net/base/net_export.h" -#include "net/spdy/hpack_encoding_context.h" +#include "net/spdy/hpack_header_table.h" +#include "net/spdy/hpack_output_stream.h" // An HpackEncoder encodes header sets as outlined in // http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-06 namespace net { +class HpackHuffmanTable; + namespace test { class HpackEncoderPeer; } // namespace test @@ -27,7 +31,9 @@ class NET_EXPORT_PRIVATE HpackEncoder { public: friend class test::HpackEncoderPeer; - explicit HpackEncoder(); + // |table| is an initialized HPACK Huffman table, having an + // externally-managed lifetime which spans beyond HpackEncoder. + explicit HpackEncoder(const HpackHuffmanTable& table); ~HpackEncoder(); // Encodes the given header set into the given string. Returns @@ -35,12 +41,52 @@ class NET_EXPORT_PRIVATE HpackEncoder { bool EncodeHeaderSet(const std::map<std::string, std::string>& header_set, std::string* output); + // Encodes the given header set into the given string. Only non-indexed + // literal representations are emitted, bypassing the header table. Huffman + // coding is also not used. Returns whether the encoding was successful. + // TODO(jgraettinger): Enable Huffman coding once the table as stablized. + bool EncodeHeaderSetWithoutCompression( + const std::map<std::string, std::string>& header_set, + std::string* output); + + // Called upon a change to SETTINGS_HEADER_TABLE_SIZE. Specifically, this + // is to be called after receiving (and sending an acknowledgement for) a + // SETTINGS_HEADER_TABLE_SIZE update from the remote decoding endpoint. + void ApplyHeaderTableSizeSetting(size_t size_setting) { + header_table_.SetSettingsHeaderTableSize(size_setting); + } + private: - static void CookieToCrumbs(base::StringPiece cookie, - std::vector<base::StringPiece>* out); + typedef std::pair<base::StringPiece, base::StringPiece> Representation; + typedef std::vector<Representation> Representations; + + // Emits a static/dynamic indexed representation (Section 4.2). + void EmitDynamicIndex(HpackEntry* entry); + void EmitStaticIndex(HpackEntry* entry); + + // Emits a literal representation (Section 4.3). + void EmitIndexedLiteral(const Representation& representation); + void EmitNonIndexedLiteral(const Representation& representation); + void EmitLiteral(const Representation& representation); + + // Emits a Huffman or identity string (whichever is smaller). + void EmitString(base::StringPiece str); + + // Determines the representation delta required to encode |header_set| in + // the current header table context. Entries in the reference set are + // enumerated and marked with membership in the current |header_set|. + // Representations which must be explicitly emitted are returned. + Representations DetermineEncodingDelta( + const std::map<std::string, std::string>& header_set); + + static void CookieToCrumbs(const Representation& cookie, + Representations* crumbs_out); + + HpackHeaderTable header_table_; + HpackOutputStream output_stream_; - uint32 max_string_literal_size_; - HpackEncodingContext context_; + bool allow_huffman_compression_; + const HpackHuffmanTable& huffman_table_; DISALLOW_COPY_AND_ASSIGN(HpackEncoder); }; diff --git a/net/spdy/hpack_encoder_test.cc b/net/spdy/hpack_encoder_test.cc index 316952e..6c8d409 100644 --- a/net/spdy/hpack_encoder_test.cc +++ b/net/spdy/hpack_encoder_test.cc @@ -18,18 +18,56 @@ using testing::ElementsAre; namespace test { +class HpackHeaderTablePeer { + public: + explicit HpackHeaderTablePeer(HpackHeaderTable* table) + : table_(table) {} + + HpackHeaderTable::EntryTable* dynamic_entries() { + return &table_->dynamic_entries_; + } + + private: + HpackHeaderTable* table_; +}; + class HpackEncoderPeer { public: + typedef HpackEncoder::Representation Representation; + typedef HpackEncoder::Representations Representations; + explicit HpackEncoderPeer(HpackEncoder* encoder) - : encoder_(encoder) {} + : encoder_(encoder) {} - void set_max_string_literal_size(uint32 size) { - encoder_->max_string_literal_size_ = size; + HpackHeaderTable* table() { + return &encoder_->header_table_; + } + HpackHeaderTablePeer table_peer() { + return HpackHeaderTablePeer(table()); + } + bool allow_huffman_compression() { + return encoder_->allow_huffman_compression_; + } + void set_allow_huffman_compression(bool allow) { + encoder_->allow_huffman_compression_ = allow; + } + void EmitString(StringPiece str) { + encoder_->EmitString(str); + } + void TakeString(string* out) { + encoder_->output_stream_.TakeString(out); } static void CookieToCrumbs(StringPiece cookie, std::vector<StringPiece>* out) { - HpackEncoder::CookieToCrumbs(cookie, out); + Representations tmp; + HpackEncoder::CookieToCrumbs(make_pair("", cookie), &tmp); + + out->clear(); + for (size_t i = 0; i != tmp.size(); ++i) { + out->push_back(tmp[i].second); + } } + private: HpackEncoder* encoder_; }; @@ -38,78 +76,348 @@ class HpackEncoderPeer { namespace { -TEST(HpackEncoderTest, CookieToCrumbs) { - test::HpackEncoderPeer peer(NULL); - std::vector<StringPiece> out; +using std::map; +using testing::ElementsAre; - // A space after ';' is consumed. All other spaces remain. - // ';' at begin and end of string produce empty crumbs. - peer.CookieToCrumbs(" foo=1;bar=2 ; baz=3; bing=4;", &out); - EXPECT_THAT(out, ElementsAre(" foo=1", "bar=2 ", "baz=3", " bing=4", "")); +class HpackEncoderTest : public ::testing::Test { + protected: + typedef test::HpackEncoderPeer::Representations Representations; - peer.CookieToCrumbs(";;foo = bar ;; ;baz =bing", &out); - EXPECT_THAT(out, ElementsAre("", "", "foo = bar ", "", "", "baz =bing")); + HpackEncoderTest() + : encoder_(ObtainHpackHuffmanTable()), + peer_(&encoder_) {} - peer.CookieToCrumbs("foo=bar; baz=bing", &out); - EXPECT_THAT(out, ElementsAre("foo=bar", "baz=bing")); + virtual void SetUp() { + static_ = peer_.table()->GetByIndex(1); + // Populate dynamic entries into the table fixture. For simplicity each + // entry has name.size() + value.size() == 10. + key_1_ = peer_.table()->TryAddEntry("key1", "value1"); + key_2_ = peer_.table()->TryAddEntry("key2", "value2"); + cookie_a_ = peer_.table()->TryAddEntry("cookie", "a=bb"); + cookie_c_ = peer_.table()->TryAddEntry("cookie", "c=dd"); - peer.CookieToCrumbs("baz=bing", &out); - EXPECT_THAT(out, ElementsAre("baz=bing")); + // No further insertions may occur without evictions. + peer_.table()->SetMaxSize(peer_.table()->size()); - peer.CookieToCrumbs("", &out); - EXPECT_THAT(out, ElementsAre("")); + // Disable Huffman coding by default. Most tests don't care about it. + peer_.set_allow_huffman_compression(false); + } + + void ExpectIndex(size_t index) { + expected_.AppendPrefix(kIndexedOpcode); + expected_.AppendUint32(index); + } + void ExpectIndexedLiteral(HpackEntry* key_entry, StringPiece value) { + expected_.AppendPrefix(kLiteralIncrementalIndexOpcode); + expected_.AppendUint32(key_entry->Index()); + expected_.AppendPrefix(kStringLiteralIdentityEncoded); + expected_.AppendUint32(value.size()); + expected_.AppendBytes(value); + } + void ExpectIndexedLiteral(StringPiece name, StringPiece value) { + expected_.AppendPrefix(kLiteralIncrementalIndexOpcode); + expected_.AppendUint32(0); + expected_.AppendPrefix(kStringLiteralIdentityEncoded); + expected_.AppendUint32(name.size()); + expected_.AppendBytes(name); + expected_.AppendPrefix(kStringLiteralIdentityEncoded); + expected_.AppendUint32(value.size()); + expected_.AppendBytes(value); + } + void ExpectNonIndexedLiteral(StringPiece name, StringPiece value) { + expected_.AppendPrefix(kLiteralNoIndexOpcode); + expected_.AppendUint32(0); + expected_.AppendPrefix(kStringLiteralIdentityEncoded); + expected_.AppendUint32(name.size()); + expected_.AppendBytes(name); + expected_.AppendPrefix(kStringLiteralIdentityEncoded); + expected_.AppendUint32(value.size()); + expected_.AppendBytes(value); + } + void CompareWithExpectedEncoding(const map<string, string>& header_set) { + string expected_out, actual_out; + expected_.TakeString(&expected_out); + EXPECT_TRUE(encoder_.EncodeHeaderSet(header_set, &actual_out)); + EXPECT_EQ(expected_out, actual_out); + } + + HpackEncoder encoder_; + test::HpackEncoderPeer peer_; + + HpackEntry* static_; + HpackEntry* key_1_; + HpackEntry* key_2_; + HpackEntry* cookie_a_; + HpackEntry* cookie_c_; + + HpackOutputStream expected_; +}; + +TEST_F(HpackEncoderTest, SingleDynamicIndex) { + ExpectIndex(key_2_->Index()); + + map<string, string> headers; + headers[key_2_->name()] = key_2_->value(); + CompareWithExpectedEncoding(headers); + + // |key_2_| was added to the reference set. + EXPECT_THAT(peer_.table()->reference_set(), ElementsAre(key_2_)); +} + +TEST_F(HpackEncoderTest, SingleStaticIndex) { + ExpectIndex(static_->Index()); + + map<string, string> headers; + headers[static_->name()] = static_->value(); + CompareWithExpectedEncoding(headers); + + // A new entry copying |static_| was inserted and added to the reference set. + HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front(); + EXPECT_NE(static_, new_entry); + EXPECT_EQ(static_->name(), new_entry->name()); + EXPECT_EQ(static_->value(), new_entry->value()); + EXPECT_THAT(peer_.table()->reference_set(), ElementsAre(new_entry)); +} + +TEST_F(HpackEncoderTest, SingleStaticIndexTooLarge) { + peer_.table()->SetMaxSize(1); // Also evicts all fixtures. + ExpectIndex(static_->Index()); + + map<string, string> headers; + headers[static_->name()] = static_->value(); + CompareWithExpectedEncoding(headers); + + EXPECT_EQ(0u, peer_.table_peer().dynamic_entries()->size()); + EXPECT_EQ(0u, peer_.table()->reference_set().size()); +} + +TEST_F(HpackEncoderTest, SingleLiteralWithIndexName) { + ExpectIndexedLiteral(key_2_, "value3"); + + map<string, string> headers; + headers[key_2_->name()] = "value3"; + CompareWithExpectedEncoding(headers); + + // A new entry was inserted and added to the reference set. + HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front(); + EXPECT_EQ(new_entry->name(), key_2_->name()); + EXPECT_EQ(new_entry->value(), "value3"); + EXPECT_THAT(peer_.table()->reference_set(), ElementsAre(new_entry)); +} + +TEST_F(HpackEncoderTest, SingleLiteralWithLiteralName) { + ExpectIndexedLiteral("key3", "value3"); + + map<string, string> headers; + headers["key3"] = "value3"; + CompareWithExpectedEncoding(headers); + + // A new entry was inserted and added to the reference set. + HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front(); + EXPECT_EQ(new_entry->name(), "key3"); + EXPECT_EQ(new_entry->value(), "value3"); + EXPECT_THAT(peer_.table()->reference_set(), ElementsAre(new_entry)); +} + +TEST_F(HpackEncoderTest, SingleLiteralTooLarge) { + peer_.table()->SetMaxSize(1); // Also evicts all fixtures. + + ExpectIndexedLiteral("key3", "value3"); + + // A header overflowing the header table is still emitted. + // The header table is empty. + map<string, string> headers; + headers["key3"] = "value3"; + CompareWithExpectedEncoding(headers); + + EXPECT_EQ(0u, peer_.table_peer().dynamic_entries()->size()); + EXPECT_EQ(0u, peer_.table()->reference_set().size()); +} + +TEST_F(HpackEncoderTest, SingleInReferenceSet) { + peer_.table()->Toggle(key_2_); + + // Nothing is emitted. + map<string, string> headers; + headers[key_2_->name()] = key_2_->value(); + CompareWithExpectedEncoding(headers); +} + +TEST_F(HpackEncoderTest, ExplicitToggleOff) { + peer_.table()->Toggle(key_1_); + peer_.table()->Toggle(key_2_); + + // |key_1_| is explicitly toggled off. + ExpectIndex(key_1_->Index()); + + map<string, string> headers; + headers[key_2_->name()] = key_2_->value(); + CompareWithExpectedEncoding(headers); +} + +TEST_F(HpackEncoderTest, ImplicitToggleOff) { + peer_.table()->Toggle(key_1_); + peer_.table()->Toggle(key_2_); + + // |key_1_| is evicted. No explicit toggle required. + ExpectIndexedLiteral("key3", "value3"); + + map<string, string> headers; + headers[key_2_->name()] = key_2_->value(); + headers["key3"] = "value3"; + CompareWithExpectedEncoding(headers); +} + +TEST_F(HpackEncoderTest, ExplicitDoubleToggle) { + peer_.table()->Toggle(key_1_); + + // |key_1_| is double-toggled prior to being evicted. + ExpectIndex(key_1_->Index()); + ExpectIndex(key_1_->Index()); + ExpectIndexedLiteral("key3", "value3"); + + map<string, string> headers; + headers[key_1_->name()] = key_1_->value(); + headers["key3"] = "value3"; + CompareWithExpectedEncoding(headers); } -// Test that EncoderHeaderSet() simply encodes everything as literals -// without indexing. -TEST(HpackEncoderTest, Basic) { - HpackEncoder encoder; +TEST_F(HpackEncoderTest, EmitThanEvict) { + // |key_1_| is toggled and placed into the reference set, + // and then immediately evicted by "key3". + ExpectIndex(key_1_->Index()); + ExpectIndexedLiteral("key3", "value3"); - std::map<string, string> header_set1; - header_set1["name1"] = "value1"; - header_set1["name2"] = "value2"; + map<string, string> headers; + headers[key_1_->name()] = key_1_->value(); + headers["key3"] = "value3"; + CompareWithExpectedEncoding(headers); +} - string encoded_header_set1; - EXPECT_TRUE(encoder.EncodeHeaderSet(header_set1, &encoded_header_set1)); - EXPECT_EQ("\x40\x05name1\x06value1" - "\x40\x05name2\x06value2", encoded_header_set1); +TEST_F(HpackEncoderTest, CookieHeaderIsCrumbled) { + peer_.table()->Toggle(cookie_a_); - std::map<string, string> header_set2; - header_set2["name2"] = "different-value"; - header_set2["name3"] = "value3"; + // |cookie_a_| is already in the reference set. |cookie_c_| is + // toggled, and "e=ff" is emitted with an indexed name. + ExpectIndex(cookie_c_->Index()); + ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff"); - string encoded_header_set2; - EXPECT_TRUE(encoder.EncodeHeaderSet(header_set2, &encoded_header_set2)); - EXPECT_EQ("\x40\x05name2\x0f" "different-value" - "\x40\x05name3\x06value3", encoded_header_set2); + map<string, string> headers; + headers["cookie"] = "e=ff; a=bb; c=dd"; + CompareWithExpectedEncoding(headers); } -TEST(HpackEncoderTest, CookieCrumbling) { - HpackEncoder encoder; +TEST_F(HpackEncoderTest, StringsDynamicallySelectHuffmanCoding) { + peer_.set_allow_huffman_compression(true); + + // Compactable string. Uses Huffman coding. + peer_.EmitString("feedbeef"); + expected_.AppendPrefix(kStringLiteralHuffmanEncoded); + expected_.AppendUint32(5); + expected_.AppendBytes("\xC4G\v\xC4q"); - std::map<string, string> header_set; - header_set["Cookie"] = "key1=value1; key2=value2"; + // Non-compactable. Uses identity coding. + peer_.EmitString("@@@@@@"); + expected_.AppendPrefix(kStringLiteralIdentityEncoded); + expected_.AppendUint32(6); + expected_.AppendBytes("@@@@@@"); - string encoded_header_set; - EXPECT_TRUE(encoder.EncodeHeaderSet(header_set, &encoded_header_set)); - EXPECT_EQ("\x40\x06""Cookie\x0bkey1=value1" - "\x40\x06""Cookie\x0bkey2=value2", encoded_header_set); + string expected_out, actual_out; + expected_.TakeString(&expected_out); + peer_.TakeString(&actual_out); + EXPECT_EQ(expected_out, actual_out); } -// Test that trying to encode a header set with a too-long header -// field will fail. -TEST(HpackEncoderTest, HeaderTooLarge) { - HpackEncoder encoder; - test::HpackEncoderPeer(&encoder).set_max_string_literal_size(10); +TEST_F(HpackEncoderTest, EncodingWithoutCompression) { + // Implementation should internally disable. + peer_.set_allow_huffman_compression(true); - std::map<string, string> header_set; - header_set["name1"] = "too-long value"; - header_set["name2"] = "value2"; + ExpectNonIndexedLiteral(":path", "/index.html"); + ExpectNonIndexedLiteral("cookie", "foo=bar; baz=bing"); + ExpectNonIndexedLiteral("hello", "goodbye"); + + map<string, string> headers; + headers[":path"] = "/index.html"; + headers["cookie"] = "foo=bar; baz=bing"; + headers["hello"] = "goodbye"; + + string expected_out, actual_out; + expected_.TakeString(&expected_out); + encoder_.EncodeHeaderSetWithoutCompression(headers, &actual_out); + EXPECT_EQ(expected_out, actual_out); +} + +TEST_F(HpackEncoderTest, MultipleEncodingPasses) { + // Pass 1: key_1_ and cookie_a_ are toggled on. + { + map<string, string> headers; + headers["key1"] = "value1"; + headers["cookie"] = "a=bb"; + + ExpectIndex(cookie_a_->Index()); + ExpectIndex(key_1_->Index()); + CompareWithExpectedEncoding(headers); + } + // Pass 2: |key_1_| is double-toggled and evicted. + // |key_2_| & |cookie_c_| are toggled on. + // |cookie_a_| is toggled off. + // A new cookie entry is added. + { + map<string, string> headers; + headers["key1"] = "value1"; + headers["key2"] = "value2"; + headers["cookie"] = "c=dd; e=ff"; + + ExpectIndex(cookie_c_->Index()); // Toggle on. + ExpectIndex(key_1_->Index()); // Double-toggle before eviction. + ExpectIndex(key_1_->Index()); + ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff"); + ExpectIndex(key_2_->Index() + 1); // Toggle on. Add 1 to reflect insertion. + ExpectIndex(cookie_a_->Index() + 1); // Toggle off. + CompareWithExpectedEncoding(headers); + } + // Pass 3: |key_2_| is evicted and implicitly toggled off. + // |cookie_c_| is explicitly toggled off. + // "key1" is re-inserted. + { + map<string, string> headers; + headers["key1"] = "value1"; + headers["key3"] = "value3"; + headers["cookie"] = "e=ff"; + + ExpectIndexedLiteral("key1", "value1"); + ExpectIndexedLiteral("key3", "value3"); + ExpectIndex(cookie_c_->Index() + 2); // Toggle off. Add 1 for insertion. + + CompareWithExpectedEncoding(headers); + } +} + +TEST_F(HpackEncoderTest, CookieToCrumbs) { + test::HpackEncoderPeer peer(NULL); + std::vector<StringPiece> out; + + // A space after ';' is consumed. All other spaces remain. + // ';' at beginning and end of string produce empty crumbs. + // See section 8.1.3.4 "Compressing the Cookie Header Field" in the HTTP/2 + // specification at http://tools.ietf.org/html/draft-ietf-httpbis-http2-11 + peer.CookieToCrumbs(" foo=1;bar=2 ; baz=3; bing=4; ", &out); + EXPECT_THAT(out, ElementsAre(" foo=1", "bar=2 ", "baz=3", " bing=4", "")); + + peer.CookieToCrumbs(";;foo = bar ;; ;baz =bing", &out); + EXPECT_THAT(out, ElementsAre("", "", "foo = bar ", "", "", "baz =bing")); + + peer.CookieToCrumbs("foo=bar; baz=bing", &out); + EXPECT_THAT(out, ElementsAre("foo=bar", "baz=bing")); + + peer.CookieToCrumbs("baz=bing", &out); + EXPECT_THAT(out, ElementsAre("baz=bing")); + + peer.CookieToCrumbs("", &out); + EXPECT_THAT(out, ElementsAre("")); - // TODO(akalin): Verify that the encoder did not attempt to encode - // the second header field. - string encoded_header_set; - EXPECT_FALSE(encoder.EncodeHeaderSet(header_set, &encoded_header_set)); + peer.CookieToCrumbs("foo;bar; baz;bing;", &out); + EXPECT_THAT(out, ElementsAre("foo", "bar", "baz", "bing", "")); } } // namespace diff --git a/net/spdy/hpack_encoding_context.cc b/net/spdy/hpack_encoding_context.cc deleted file mode 100644 index 11a99bc..0000000 --- a/net/spdy/hpack_encoding_context.cc +++ /dev/null @@ -1,234 +0,0 @@ -// Copyright 2014 The Chromium Authors. All rights reserved. -// Use of this source code is governed by a BSD-style license that can be -// found in the LICENSE file. - -#include "net/spdy/hpack_encoding_context.h" - -#include <cstddef> - -#include "base/logging.h" -#include "base/macros.h" -#include "net/spdy/hpack_constants.h" -#include "net/spdy/hpack_entry.h" - -namespace net { - -using base::StringPiece; - -namespace { - -// An entry in the static table. Must be a POD in order to avoid -// static initializers, i.e. no user-defined constructors or -// destructors. -struct StaticEntry { - const char* const name; - const size_t name_len; - const char* const value; - const size_t value_len; -}; - -// The "constructor" for a StaticEntry that computes the lengths at -// compile time. -#define STATIC_ENTRY(name, value) \ - { name, arraysize(name) - 1, value, arraysize(value) - 1 } - -const StaticEntry kStaticTable[] = { - STATIC_ENTRY(":authority" , ""), // 1 - STATIC_ENTRY(":method" , "GET"), // 2 - STATIC_ENTRY(":method" , "POST"), // 3 - STATIC_ENTRY(":path" , "/"), // 4 - STATIC_ENTRY(":path" , "/index.html"), // 5 - STATIC_ENTRY(":scheme" , "http"), // 6 - STATIC_ENTRY(":scheme" , "https"), // 7 - STATIC_ENTRY(":status" , "200"), // 8 - STATIC_ENTRY(":status" , "500"), // 9 - STATIC_ENTRY(":status" , "404"), // 10 - STATIC_ENTRY(":status" , "403"), // 11 - STATIC_ENTRY(":status" , "400"), // 12 - STATIC_ENTRY(":status" , "401"), // 13 - STATIC_ENTRY("accept-charset" , ""), // 14 - STATIC_ENTRY("accept-encoding" , ""), // 15 - STATIC_ENTRY("accept-language" , ""), // 16 - STATIC_ENTRY("accept-ranges" , ""), // 17 - STATIC_ENTRY("accept" , ""), // 18 - STATIC_ENTRY("access-control-allow-origin" , ""), // 19 - STATIC_ENTRY("age" , ""), // 20 - STATIC_ENTRY("allow" , ""), // 21 - STATIC_ENTRY("authorization" , ""), // 22 - STATIC_ENTRY("cache-control" , ""), // 23 - STATIC_ENTRY("content-disposition" , ""), // 24 - STATIC_ENTRY("content-encoding" , ""), // 25 - STATIC_ENTRY("content-language" , ""), // 26 - STATIC_ENTRY("content-length" , ""), // 27 - STATIC_ENTRY("content-location" , ""), // 28 - STATIC_ENTRY("content-range" , ""), // 29 - STATIC_ENTRY("content-type" , ""), // 30 - STATIC_ENTRY("cookie" , ""), // 31 - STATIC_ENTRY("date" , ""), // 32 - STATIC_ENTRY("etag" , ""), // 33 - STATIC_ENTRY("expect" , ""), // 34 - STATIC_ENTRY("expires" , ""), // 35 - STATIC_ENTRY("from" , ""), // 36 - STATIC_ENTRY("host" , ""), // 37 - STATIC_ENTRY("if-match" , ""), // 38 - STATIC_ENTRY("if-modified-since" , ""), // 39 - STATIC_ENTRY("if-none-match" , ""), // 40 - STATIC_ENTRY("if-range" , ""), // 41 - STATIC_ENTRY("if-unmodified-since" , ""), // 42 - STATIC_ENTRY("last-modified" , ""), // 43 - STATIC_ENTRY("link" , ""), // 44 - STATIC_ENTRY("location" , ""), // 45 - STATIC_ENTRY("max-forwards" , ""), // 46 - STATIC_ENTRY("proxy-authenticate" , ""), // 47 - STATIC_ENTRY("proxy-authorization" , ""), // 48 - STATIC_ENTRY("range" , ""), // 49 - STATIC_ENTRY("referer" , ""), // 50 - STATIC_ENTRY("refresh" , ""), // 51 - STATIC_ENTRY("retry-after" , ""), // 52 - STATIC_ENTRY("server" , ""), // 53 - STATIC_ENTRY("set-cookie" , ""), // 54 - STATIC_ENTRY("strict-transport-security" , ""), // 55 - STATIC_ENTRY("transfer-encoding" , ""), // 56 - STATIC_ENTRY("user-agent" , ""), // 57 - STATIC_ENTRY("vary" , ""), // 58 - STATIC_ENTRY("via" , ""), // 59 - STATIC_ENTRY("www-authenticate" , ""), // 60 -}; - -#undef STATIC_ENTRY - -const size_t kStaticEntryCount = arraysize(kStaticTable); - -} // namespace - -// Must match HpackEntry::kUntouched. -const uint32 HpackEncodingContext::kUntouched = 0x7fffffff; - -HpackEncodingContext::HpackEncodingContext() - : settings_header_table_size_(kDefaultHeaderTableSizeSetting) { - DCHECK_EQ(HpackEncodingContext::kUntouched, HpackEntry::kUntouched); -} - -HpackEncodingContext::~HpackEncodingContext() {} - -uint32 HpackEncodingContext::GetMutableEntryCount() const { - return header_table_.GetEntryCount(); -} - -uint32 HpackEncodingContext::GetEntryCount() const { - return GetMutableEntryCount() + kStaticEntryCount; -} - -StringPiece HpackEncodingContext::GetNameAt(uint32 index) const { - CHECK_GE(index, 1u); - CHECK_LE(index, GetEntryCount()); - if (index > header_table_.GetEntryCount()) { - const StaticEntry& entry = - kStaticTable[index - header_table_.GetEntryCount() - 1]; - return StringPiece(entry.name, entry.name_len); - } - return header_table_.GetEntry(index).name(); -} - -StringPiece HpackEncodingContext::GetValueAt(uint32 index) const { - CHECK_GE(index, 1u); - CHECK_LE(index, GetEntryCount()); - if (index > header_table_.GetEntryCount()) { - const StaticEntry& entry = - kStaticTable[index - header_table_.GetEntryCount() - 1]; - return StringPiece(entry.value, entry.value_len); - } - return header_table_.GetEntry(index).value(); -} - -bool HpackEncodingContext::IsReferencedAt(uint32 index) const { - CHECK_GE(index, 1u); - CHECK_LE(index, GetEntryCount()); - if (index > header_table_.GetEntryCount()) - return false; - return header_table_.GetEntry(index).IsReferenced(); -} - -uint32 HpackEncodingContext::GetTouchCountAt(uint32 index) const { - CHECK_GE(index, 1u); - CHECK_LE(index, GetEntryCount()); - if (index > header_table_.GetEntryCount()) - return 0; - return header_table_.GetEntry(index).TouchCount(); -} - -void HpackEncodingContext::SetReferencedAt(uint32 index, bool referenced) { - header_table_.GetMutableEntry(index)->SetReferenced(referenced); -} - -void HpackEncodingContext::AddTouchesAt(uint32 index, uint32 touch_count) { - header_table_.GetMutableEntry(index)->AddTouches(touch_count); -} - -void HpackEncodingContext::ClearTouchesAt(uint32 index) { - header_table_.GetMutableEntry(index)->ClearTouches(); -} - -void HpackEncodingContext::ApplyHeaderTableSizeSetting(uint32 size) { - settings_header_table_size_ = size; - if (size < header_table_.max_size()) { - // Implicit maximum-size context update. - CHECK(ProcessContextUpdateNewMaximumSize(size)); - } -} - -bool HpackEncodingContext::ProcessContextUpdateNewMaximumSize(uint32 size) { - if (size > settings_header_table_size_) { - return false; - } - header_table_.SetMaxSize(size); - return true; -} - -bool HpackEncodingContext::ProcessContextUpdateEmptyReferenceSet() { - for (size_t i = 1; i <= header_table_.GetEntryCount(); ++i) { - HpackEntry* entry = header_table_.GetMutableEntry(i); - if (entry->IsReferenced()) { - entry->SetReferenced(false); - } - } - return true; -} - -bool HpackEncodingContext::ProcessIndexedHeader(uint32 index, uint32* new_index, - std::vector<uint32>* removed_referenced_indices) { - CHECK_GT(index, 0u); - CHECK_LT(index, GetEntryCount()); - - if (index <= header_table_.GetEntryCount()) { - *new_index = index; - removed_referenced_indices->clear(); - HpackEntry* entry = header_table_.GetMutableEntry(index); - entry->SetReferenced(!entry->IsReferenced()); - } else { - // TODO(akalin): Make HpackEntry know about owned strings and - // non-owned strings so that it can potentially avoid copies here. - HpackEntry entry(GetNameAt(index), GetValueAt(index)); - - header_table_.TryAddEntry(entry, new_index, removed_referenced_indices); - if (*new_index >= 1) { - header_table_.GetMutableEntry(*new_index)->SetReferenced(true); - } - } - return true; -} - -bool HpackEncodingContext::ProcessLiteralHeaderWithIncrementalIndexing( - StringPiece name, - StringPiece value, - uint32* index, - std::vector<uint32>* removed_referenced_indices) { - HpackEntry entry(name, value); - header_table_.TryAddEntry(entry, index, removed_referenced_indices); - if (*index >= 1) { - header_table_.GetMutableEntry(*index)->SetReferenced(true); - } - return true; -} - -} // namespace net diff --git a/net/spdy/hpack_encoding_context.h b/net/spdy/hpack_encoding_context.h deleted file mode 100644 index 1fdf615..0000000 --- a/net/spdy/hpack_encoding_context.h +++ /dev/null @@ -1,124 +0,0 @@ -// Copyright 2014 The Chromium Authors. All rights reserved. -// Use of this source code is governed by a BSD-style license that can be -// found in the LICENSE file. - -#ifndef NET_SPDY_HPACK_ENCODING_CONTEXT_H_ -#define NET_SPDY_HPACK_ENCODING_CONTEXT_H_ - -#include <cstddef> -#include <deque> -#include <vector> - -#include "base/basictypes.h" -#include "base/macros.h" -#include "base/strings/string_piece.h" -#include "net/base/net_export.h" -#include "net/spdy/hpack_header_table.h" - -// All section references below are to -// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-06 - -namespace net { - -namespace test { -class HpackEncodingContextPeer; -} // namespace test - -// An encoding context is simply a header table and its associated -// reference set and a static table. -class NET_EXPORT_PRIVATE HpackEncodingContext { - public: - friend class test::HpackEncodingContextPeer; - - // The constant returned by GetTouchesAt() if the indexed entry - // hasn't been touched (which is distinct from having a touch count - // of 0). - // - // TODO(akalin): The distinction between untouched and having a - // touch count of 0 is confusing. Think of a better way to represent - // this state. - static const uint32 kUntouched; - - HpackEncodingContext(); - - ~HpackEncodingContext(); - - uint32 GetMutableEntryCount() const; - - uint32 GetEntryCount() const; - - // For all read accessors below, index must be >= 1 and <= - // GetEntryCount(). For all mutating accessors below, index must be - // >= 1 and <= GetMutableEntryCount(). - - // The StringPieces returned by Get{Name,Value}At() live as long as - // the next call to SetMaxSize() or the Process*() functions. - - base::StringPiece GetNameAt(uint32 index) const; - - base::StringPiece GetValueAt(uint32 index) const; - - bool IsReferencedAt(uint32 index) const; - - uint32 GetTouchCountAt(uint32 index) const; - - void SetReferencedAt(uint32 index, bool referenced); - - // Adds the given number of touches to the entry at the given - // index. It is guaranteed that GetTouchCountAt(index) will not - // equal kUntouched after this function is called (even if - // touch_count == 0). - void AddTouchesAt(uint32 index, uint32 touch_count); - - // Sets the touch count of the entry at the given index to - // kUntouched. - void ClearTouchesAt(uint32 index); - - // Called upon acknowledgement of SETTINGS_HEADER_TABLE_SIZE. - // If |max_size| is smaller than the current header table size, the change - // is treated as an implicit maximum-size context update. - void ApplyHeaderTableSizeSetting(uint32 max_size); - - // The Process*() functions below return true on success and false - // if an error was encountered. - - // Section 4.4. Sets the maximum size of the header table, evicting entries - // as needed. Fails if |max_size| is larger than SETTINGS_HEADER_TABLE_SIZE. - bool ProcessContextUpdateNewMaximumSize(uint32 max_size); - - // Section 4.4. Drops all headers from the reference set. - bool ProcessContextUpdateEmptyReferenceSet(); - - // Tries to update the encoding context given an indexed header - // opcode for the given index as described in section 3.2.1. - // new_index is filled in with the index of a mutable entry, - // or 0 if one was not created. removed_referenced_indices is filled - // in with the indices of all entries removed from the reference set. - bool ProcessIndexedHeader(uint32 nonzero_index, - uint32* new_index, - std::vector<uint32>* removed_referenced_indices); - - // Tries to update the encoding context given a literal header with - // incremental indexing opcode for the given name and value as - // described in 3.2.1. index is filled in with the index of the new - // entry if the header was successfully indexed, or 0 if - // not. removed_referenced_indices is filled in with the indices of - // all entries removed from the reference set. - bool ProcessLiteralHeaderWithIncrementalIndexing( - base::StringPiece name, - base::StringPiece value, - uint32* index, - std::vector<uint32>* removed_referenced_indices); - - private: - // Last acknowledged value for SETTINGS_HEADER_TABLE_SIZE. - uint32 settings_header_table_size_; - - HpackHeaderTable header_table_; - - DISALLOW_COPY_AND_ASSIGN(HpackEncodingContext); -}; - -} // namespace net - -#endif // NET_SPDY_HPACK_ENCODING_CONTEXT_H_ diff --git a/net/spdy/hpack_encoding_context_test.cc b/net/spdy/hpack_encoding_context_test.cc deleted file mode 100644 index de7f87d..0000000 --- a/net/spdy/hpack_encoding_context_test.cc +++ /dev/null @@ -1,220 +0,0 @@ -// Copyright 2014 The Chromium Authors. All rights reserved. -// Use of this source code is governed by a BSD-style license that can be -// found in the LICENSE file. - -#include "net/spdy/hpack_encoding_context.h" - -#include <vector> - -#include "base/basictypes.h" -#include "net/spdy/hpack_constants.h" -#include "testing/gtest/include/gtest/gtest.h" - -namespace net { - -namespace test { - -class HpackEncodingContextPeer { - public: - explicit HpackEncodingContextPeer(const HpackEncodingContext& context) - : context_(context) {} - - const HpackHeaderTable& header_table() { - return context_.header_table_; - } - uint32 settings_header_table_size() { - return context_.settings_header_table_size_; - } - - private: - const HpackEncodingContext& context_; -}; - -} // namespace test - -namespace { - -TEST(HpackEncodingContextTest, ApplyHeaderTableSizeSetting) { - HpackEncodingContext context; - test::HpackEncodingContextPeer peer(context); - - // Default setting and table size are kDefaultHeaderTableSizeSetting. - EXPECT_EQ(kDefaultHeaderTableSizeSetting, - peer.settings_header_table_size()); - EXPECT_EQ(kDefaultHeaderTableSizeSetting, - peer.header_table().max_size()); - - // Applying a larger table size setting doesn't affect the headers table. - context.ApplyHeaderTableSizeSetting(kDefaultHeaderTableSizeSetting * 2); - - EXPECT_EQ(kDefaultHeaderTableSizeSetting * 2, - peer.settings_header_table_size()); - EXPECT_EQ(kDefaultHeaderTableSizeSetting, - peer.header_table().max_size()); - - // Applying a smaller size setting does update the headers table. - context.ApplyHeaderTableSizeSetting(kDefaultHeaderTableSizeSetting / 2); - - EXPECT_EQ(kDefaultHeaderTableSizeSetting / 2, - peer.settings_header_table_size()); - EXPECT_EQ(kDefaultHeaderTableSizeSetting / 2, - peer.header_table().max_size()); -} - -TEST(HpackEncodingContextTest, ProcessContextUpdateNewMaximumSize) { - HpackEncodingContext context; - test::HpackEncodingContextPeer peer(context); - - EXPECT_EQ(kDefaultHeaderTableSizeSetting, - peer.settings_header_table_size()); - - // Shrink maximum size by half. Succeeds. - EXPECT_TRUE(context.ProcessContextUpdateNewMaximumSize( - kDefaultHeaderTableSizeSetting / 2)); - EXPECT_EQ(kDefaultHeaderTableSizeSetting / 2, - peer.header_table().max_size()); - - // Double maximum size. Succeeds. - EXPECT_TRUE(context.ProcessContextUpdateNewMaximumSize( - kDefaultHeaderTableSizeSetting)); - EXPECT_EQ(kDefaultHeaderTableSizeSetting, peer.header_table().max_size()); - - // One beyond table size setting. Fails. - EXPECT_FALSE(context.ProcessContextUpdateNewMaximumSize( - kDefaultHeaderTableSizeSetting + 1)); - EXPECT_EQ(kDefaultHeaderTableSizeSetting, peer.header_table().max_size()); -} - -// Try to process an indexed header with an index for a static -// header. That should succeed and add a mutable copy into the header -// table. -TEST(HpackEncodingContextTest, IndexedHeaderStatic) { - HpackEncodingContext encoding_context; - - std::string name = encoding_context.GetNameAt(2).as_string(); - std::string value = encoding_context.GetValueAt(2).as_string(); - EXPECT_EQ(0u, encoding_context.GetMutableEntryCount()); - EXPECT_NE(name, encoding_context.GetNameAt(1)); - EXPECT_NE(value, encoding_context.GetValueAt(1)); - - { - uint32 new_index = 0; - std::vector<uint32> removed_referenced_indices; - EXPECT_TRUE( - encoding_context.ProcessIndexedHeader(2, - &new_index, - &removed_referenced_indices)); - EXPECT_EQ(1u, new_index); - EXPECT_TRUE(removed_referenced_indices.empty()); - } - EXPECT_EQ(1u, encoding_context.GetMutableEntryCount()); - EXPECT_EQ(name, encoding_context.GetNameAt(1)); - EXPECT_EQ(value, encoding_context.GetValueAt(1)); - EXPECT_TRUE(encoding_context.IsReferencedAt(1)); - - { - uint32 new_index = 0; - std::vector<uint32> removed_referenced_indices; - EXPECT_TRUE( - encoding_context.ProcessIndexedHeader(1, - &new_index, - &removed_referenced_indices)); - EXPECT_EQ(1u, new_index); - EXPECT_TRUE(removed_referenced_indices.empty()); - } - EXPECT_EQ(1u, encoding_context.GetMutableEntryCount()); - EXPECT_EQ(name, encoding_context.GetNameAt(1)); - EXPECT_EQ(value, encoding_context.GetValueAt(1)); - EXPECT_LE(1u, encoding_context.GetMutableEntryCount()); - EXPECT_FALSE(encoding_context.IsReferencedAt(1)); -} - -// Try to process an indexed header with an index for a static header -// and an encoding context where a copy of that header wouldn't -// fit. That should succeed without making a copy. -TEST(HpackEncodingContextTest, IndexedHeaderStaticCopyDoesNotFit) { - HpackEncodingContext encoding_context; - encoding_context.ProcessContextUpdateNewMaximumSize(0); - - uint32 new_index = 0; - std::vector<uint32> removed_referenced_indices; - EXPECT_TRUE( - encoding_context.ProcessIndexedHeader(1, - &new_index, - &removed_referenced_indices)); - EXPECT_EQ(0u, new_index); - EXPECT_TRUE(removed_referenced_indices.empty()); - EXPECT_EQ(0u, encoding_context.GetMutableEntryCount()); -} - -// Add a bunch of new headers and then process a context update to empty the -// reference set. Expect it to be empty. -TEST(HpackEncodingContextTest, ProcessContextUpdateEmptyReferenceSet) { - HpackEncodingContext encoding_context; - test::HpackEncodingContextPeer peer(encoding_context); - - uint32 kEntryCount = 50; - - for (uint32 i = 1; i <= kEntryCount; ++i) { - uint32 new_index = 0; - std::vector<uint32> removed_referenced_indices; - EXPECT_TRUE( - encoding_context.ProcessIndexedHeader(i, - &new_index, - &removed_referenced_indices)); - EXPECT_EQ(1u, new_index); - EXPECT_TRUE(removed_referenced_indices.empty()); - EXPECT_EQ(i, encoding_context.GetMutableEntryCount()); - } - - for (uint32 i = 1; i <= kEntryCount; ++i) { - EXPECT_TRUE(peer.header_table().GetEntry(i).IsReferenced()); - } - encoding_context.ProcessContextUpdateEmptyReferenceSet(); - for (uint32 i = 1; i <= kEntryCount; ++i) { - EXPECT_FALSE(peer.header_table().GetEntry(i).IsReferenced()); - } -} - -// NOTE: It's too onerous to try to test invalid input to -// ProcessLiteralHeaderWithIncrementalIndexing(); that would require -// making a really large (>4GB of memory) string. - -// Try to process a reasonably-sized literal header with incremental -// indexing. It should succeed. -TEST(HpackEncodingContextTest, LiteralHeaderIncrementalIndexing) { - HpackEncodingContext encoding_context; - - uint32 index = 0; - std::vector<uint32> removed_referenced_indices; - EXPECT_TRUE( - encoding_context.ProcessLiteralHeaderWithIncrementalIndexing( - "name", "value", &index, &removed_referenced_indices)); - EXPECT_EQ(1u, index); - EXPECT_TRUE(removed_referenced_indices.empty()); - EXPECT_EQ("name", encoding_context.GetNameAt(1).as_string()); - EXPECT_EQ("value", encoding_context.GetValueAt(1).as_string()); - EXPECT_TRUE(encoding_context.IsReferencedAt(1)); - EXPECT_EQ(1u, encoding_context.GetMutableEntryCount()); -} - -// Try to process a literal header with incremental indexing that is -// too large for the header table. It should succeed without indexing -// into the table. -TEST(HpackEncodingContextTest, LiteralHeaderIncrementalIndexingDoesNotFit) { - HpackEncodingContext encoding_context; - encoding_context.ProcessContextUpdateNewMaximumSize(0); - - uint32 index = 0; - std::vector<uint32> removed_referenced_indices; - EXPECT_TRUE( - encoding_context.ProcessLiteralHeaderWithIncrementalIndexing( - "name", "value", &index, &removed_referenced_indices)); - EXPECT_EQ(0u, index); - EXPECT_TRUE(removed_referenced_indices.empty()); - EXPECT_EQ(0u, encoding_context.GetMutableEntryCount()); -} - -} // namespace - -} // namespace net diff --git a/net/spdy/hpack_entry.cc b/net/spdy/hpack_entry.cc index 298f6cb..e62c799 100644 --- a/net/spdy/hpack_entry.cc +++ b/net/spdy/hpack_entry.cc @@ -10,72 +10,79 @@ namespace net { -namespace { - -const uint32 kReferencedMask = 0x80000000; -const uint32 kTouchCountMask = 0x7fffffff; - -} // namespace - -const uint32 HpackEntry::kSizeOverhead = 32; - -const uint32 HpackEntry::kUntouched = 0x7fffffff; - -HpackEntry::HpackEntry() : referenced_and_touch_count_(kUntouched) {} - -HpackEntry::HpackEntry(base::StringPiece name, base::StringPiece value) - : name_(name.as_string()), - value_(value.as_string()), - referenced_and_touch_count_(kUntouched) {} - -bool HpackEntry::IsReferenced() const { - return ((referenced_and_touch_count_ & kReferencedMask) != 0); +using base::StringPiece; + +const size_t HpackEntry::kSizeOverhead = 32; + +bool HpackEntry::Comparator::operator() ( + const HpackEntry* lhs, const HpackEntry* rhs) const { + int result = lhs->name().compare(rhs->name()); + if (result != 0) + return result < 0; + result = lhs->value().compare(rhs->value()); + if (result != 0) + return result < 0; + DCHECK(lhs == rhs || lhs->Index() != rhs->Index()); + return lhs->Index() < rhs->Index(); } -uint32 HpackEntry::TouchCount() const { - return referenced_and_touch_count_ & kTouchCountMask; +HpackEntry::HpackEntry(StringPiece name, + StringPiece value, + bool is_static, + size_t insertion_index, + const size_t* total_table_insertions_or_current_size) + : name_(name.data(), name.size()), + value_(value.data(), value.size()), + is_static_(is_static), + state_(0), + insertion_index_(insertion_index), + total_insertions_or_size_(total_table_insertions_or_current_size) { + CHECK_NE(total_table_insertions_or_current_size, + static_cast<const size_t*>(NULL)); } -size_t HpackEntry::Size() const { - return name_.size() + value_.size() + kSizeOverhead; +HpackEntry::HpackEntry(StringPiece name, StringPiece value) + : name_(name.data(), name.size()), + value_(value.data(), value.size()), + is_static_(false), + state_(0), + insertion_index_(0), + total_insertions_or_size_(NULL) { } -std::string HpackEntry::GetDebugString() const { - const char* is_referenced_str = (IsReferenced() ? "true" : "false"); - std::string touch_count_str = "(untouched)"; - if (TouchCount() != kUntouched) - touch_count_str = base::IntToString(TouchCount()); - return "{ name: \"" + name_ + "\", value: \"" + value_ + - "\", referenced: " + is_referenced_str + ", touch_count: " + - touch_count_str + " }"; +HpackEntry::HpackEntry() + : is_static_(false), + state_(0), + insertion_index_(0), + total_insertions_or_size_(NULL) { } -bool HpackEntry::Equals(const HpackEntry& other) const { - return - StringPiecesEqualConstantTime(name_, other.name_) && - StringPiecesEqualConstantTime(value_, other.value_) && - (referenced_and_touch_count_ == other.referenced_and_touch_count_); +HpackEntry::~HpackEntry() {} + +size_t HpackEntry::Index() const { + if (total_insertions_or_size_ == NULL) { + // This is a lookup instance. + return 0; + } else if (IsStatic()) { + return 1 + insertion_index_ + *total_insertions_or_size_; + } else { + return *total_insertions_or_size_ - insertion_index_; + } } -void HpackEntry::SetReferenced(bool referenced) { - referenced_and_touch_count_ &= kTouchCountMask; - if (referenced) - referenced_and_touch_count_ |= kReferencedMask; +// static +size_t HpackEntry::Size(StringPiece name, StringPiece value) { + return name.size() + value.size() + kSizeOverhead; } - -void HpackEntry::AddTouches(uint32 additional_touch_count) { - uint32 new_touch_count = TouchCount(); - if (new_touch_count == kUntouched) - new_touch_count = 0; - new_touch_count += additional_touch_count; - DCHECK_LT(new_touch_count, kUntouched); - referenced_and_touch_count_ &= kReferencedMask; - referenced_and_touch_count_ |= new_touch_count; +size_t HpackEntry::Size() const { + return Size(name(), value()); } -void HpackEntry::ClearTouches() { - referenced_and_touch_count_ &= kReferencedMask; - referenced_and_touch_count_ |= kUntouched; +std::string HpackEntry::GetDebugString() const { + return "{ name: \"" + name_ + + "\", value: \"" + value_ + + "\", " + (IsStatic() ? "static" : "dynamic") + + ", state: " + base::IntToString(state_) + " }"; } } // namespace net diff --git a/net/spdy/hpack_entry.h b/net/spdy/hpack_entry.h index 7cfd14e..a216c63 100644 --- a/net/spdy/hpack_entry.h +++ b/net/spdy/hpack_entry.h @@ -6,95 +6,102 @@ #define NET_SPDY_HPACK_ENTRY_H_ #include <cstddef> -#include <deque> +#include <set> #include <string> -#include <vector> #include "base/basictypes.h" #include "base/macros.h" #include "base/strings/string_piece.h" #include "net/base/net_export.h" -namespace net { - // All section references below are to // http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-06 +namespace net { + // A structure for an entry in the header table (3.1.2) and the -// reference set (3.1.3). This structure also keeps track of how many -// times the entry has been 'touched', which is useful for both -// encoding and decoding. +// reference set (3.1.3). class NET_EXPORT_PRIVATE HpackEntry { public: // The constant amount added to name().size() and value().size() to // get the size of an HpackEntry as defined in 3.3.1. - static const uint32 kSizeOverhead; - - // The constant returned by touch_count() if an entry hasn't been - // touched (which is distinct from an entry having a touch count of - // 0). + static const size_t kSizeOverhead; + + // Implements a total ordering of HpackEntry on name(), value(), then Index() + // ascending. Note that Index() may change over the lifetime of an HpackEntry, + // but the relative Index() order of two entries will not. This comparator is + // composed with the 'lookup' HpackEntry constructor to allow for efficient + // lower-bounding of matching entries. + struct NET_EXPORT_PRIVATE Comparator { + bool operator() (const HpackEntry* lhs, const HpackEntry* rhs) const; + }; + typedef std::set<HpackEntry*, Comparator> OrderedSet; + + // Creates an entry. Preconditions: + // - |is_static| captures whether this entry is a member of the static + // or dynamic header table. + // - |insertion_index| is this entry's index in the total set of entries ever + // inserted into the header table (including static entries). + // - |total_table_insertions_or_current_size| references an externally- + // updated count of either the total number of header insertions (if + // !|is_static|), or the current size of the header table (if |is_static|). // - // TODO(akalin): The distinction between untouched and having a - // touch count of 0 is confusing. Think of a better way to represent - // this state. - static const uint32 kUntouched; + // The combination of |is_static|, |insertion_index|, and + // |total_table_insertions_or_current_size| allows an HpackEntry to determine + // its current table index in O(1) time. + HpackEntry(base::StringPiece name, + base::StringPiece value, + bool is_static, + size_t insertion_index, + const size_t* total_table_insertions_or_current_size); + + // Create a 'lookup' entry (only) suitable for querying a HpackEntrySet. The + // instance Index() always returns 0, and will lower-bound all entries + // matching |name| & |value| in an OrderedSet. + HpackEntry(base::StringPiece name, base::StringPiece value); // Creates an entry with empty name a value. Only defined so that // entries can be stored in STL containers. HpackEntry(); - // Creates an entry with a copy is made of the given name and value. - // - // TODO(akalin): Add option to not make a copy (for static table - // entries). - HpackEntry(base::StringPiece name, base::StringPiece value); + ~HpackEntry(); - // Copy constructor and assignment operator welcome. + const std::string& name() const { return name_; } + const std::string& value() const { return value_; } - // The name() and value() StringPieces have the same lifetime as - // this entry. + // Returns whether this entry is a member of the static (as opposed to + // dynamic) table. + bool IsStatic() const { return is_static_; } - base::StringPiece name() const { return base::StringPiece(name_); } - base::StringPiece value() const { return base::StringPiece(value_); } + // Returns and sets the state of the entry, or zero if never set. + // The semantics of |state| are specific to the encoder or decoder. + uint8 state() const { return state_; } + void set_state(uint8 state) { state_ = state; } - // Returns whether or not this entry is in the reference set. - bool IsReferenced() const; + // Returns the entry's current index in the header table. + size_t Index() const; - // Returns how many touches this entry has, or kUntouched if this - // entry hasn't been touched at all. The meaning of the touch count - // is defined by whatever is calling - // AddTouchCount()/ClearTouchCount() (i.e., the encoder or decoder). - uint32 TouchCount() const; - - // Returns the size of an entry as defined in 3.3.1. The returned - // value may not necessarily fit in 32 bits. + // Returns the size of an entry as defined in 3.3.1. + static size_t Size(base::StringPiece name, base::StringPiece value); size_t Size() const; std::string GetDebugString() const; - // Returns whether this entry has the same name, value, referenced - // state, and touch count as the given one. - bool Equals(const HpackEntry& other) const; - - void SetReferenced(bool referenced); - - // Adds the given number of touches to this entry (see - // TouchCount()). The total number of touches must not exceed 2^31 - - // 2. It is guaranteed that this entry's touch count will not equal - // kUntouched after this function is called (even if touch_count == - // 0). - void AddTouches(uint32 additional_touch_count); - - // Sets the touch count of this entry to kUntouched. - void ClearTouches(); - private: + // TODO(jgraettinger): Reduce copies, possibly via SpdyPinnableBufferPiece. std::string name_; std::string value_; - // The high bit stores 'referenced' and the rest stores the touch - // count. - uint32 referenced_and_touch_count_; + bool is_static_; + uint8 state_; + + // The entry's index in the total set of entries ever inserted into the header + // table. + size_t insertion_index_; + + // If |is_static_|, references the current size of the headers table. + // Else, references the total number of header insertions which have occurred. + const size_t* total_insertions_or_size_; }; } // namespace net diff --git a/net/spdy/hpack_entry_test.cc b/net/spdy/hpack_entry_test.cc index 422190b..84f923f 100644 --- a/net/spdy/hpack_entry_test.cc +++ b/net/spdy/hpack_entry_test.cc @@ -14,136 +14,156 @@ namespace { using std::string; -const char kName[] = "headername"; -const uint32 kNameStringLength = arraysize(kName) - 1; -const char kValue[] = "Header Value"; -const uint32 kValueStringLength = arraysize(kValue) - 1; - -// Make sure a default-constructed entry is still valid and starts off -// empty, unreferenced, and untouched. -TEST(HpackEntryTest, DefaultConstructor) { +class HpackEntryTest : public ::testing::Test { + protected: + HpackEntryTest() + : name_("header-name"), + value_("header value"), + total_insertions_(0), + table_size_(0) {} + + // These builders maintain the same external table invariants that a "real" + // table (ie HpackHeaderTable) would. + HpackEntry StaticEntry() { + return HpackEntry(name_, value_, true, total_insertions_++, &table_size_); + } + HpackEntry DynamicEntry() { + ++table_size_; + size_t index = total_insertions_++; + return HpackEntry(name_, value_, false, index, &total_insertions_); + } + void DropEntry() { --table_size_; } + + size_t Size() { + return name_.size() + value_.size() + HpackEntry::kSizeOverhead; + } + + string name_, value_; + + private: + // Referenced by HpackEntry instances. + size_t total_insertions_; + size_t table_size_; +}; + +TEST_F(HpackEntryTest, StaticConstructor) { + HpackEntry entry(StaticEntry()); + + EXPECT_EQ(name_, entry.name()); + EXPECT_EQ(value_, entry.value()); + EXPECT_TRUE(entry.IsStatic()); + EXPECT_EQ(1u, entry.Index()); + EXPECT_EQ(0u, entry.state()); + EXPECT_EQ(Size(), entry.Size()); +} + +TEST_F(HpackEntryTest, DynamicConstructor) { + HpackEntry entry(DynamicEntry()); + + EXPECT_EQ(name_, entry.name()); + EXPECT_EQ(value_, entry.value()); + EXPECT_FALSE(entry.IsStatic()); + EXPECT_EQ(1u, entry.Index()); + EXPECT_EQ(0u, entry.state()); + EXPECT_EQ(Size(), entry.Size()); +} + +TEST_F(HpackEntryTest, LookupConstructor) { + HpackEntry entry(name_, value_); + + EXPECT_EQ(name_, entry.name()); + EXPECT_EQ(value_, entry.value()); + EXPECT_FALSE(entry.IsStatic()); + EXPECT_EQ(0u, entry.Index()); + EXPECT_EQ(0u, entry.state()); + EXPECT_EQ(Size(), entry.Size()); +} + +TEST_F(HpackEntryTest, DefaultConstructor) { HpackEntry entry; + EXPECT_TRUE(entry.name().empty()); EXPECT_TRUE(entry.value().empty()); - EXPECT_FALSE(entry.IsReferenced()); - EXPECT_EQ(HpackEntry::kUntouched, entry.TouchCount()); + EXPECT_EQ(0u, entry.state()); EXPECT_EQ(HpackEntry::kSizeOverhead, entry.Size()); } -// Make sure a non-default-constructed HpackEntry starts off with -// copies of the given name and value, and unreferenced and untouched. -TEST(HpackEntryTest, NormalConstructor) { - string name = kName; - string value = kValue; - HpackEntry entry(name, value); - EXPECT_EQ(name, entry.name()); - EXPECT_EQ(value, entry.value()); - - ++name[0]; - ++value[0]; - EXPECT_NE(name, entry.name()); - EXPECT_NE(value, entry.name()); - - EXPECT_FALSE(entry.IsReferenced()); - EXPECT_EQ(HpackEntry::kUntouched, entry.TouchCount()); - EXPECT_EQ( - kNameStringLength + kValueStringLength + HpackEntry::kSizeOverhead, - entry.Size()); -} +TEST_F(HpackEntryTest, IndexUpdate) { + HpackEntry static1(StaticEntry()); + HpackEntry static2(StaticEntry()); -// Make sure twiddling the referenced bit doesn't affect the touch -// count when it's kUntouched. -TEST(HpackEntryTest, IsReferencedUntouched) { - HpackEntry entry(kName, kValue); - EXPECT_FALSE(entry.IsReferenced()); - EXPECT_EQ(HpackEntry::kUntouched, entry.TouchCount()); + EXPECT_EQ(1u, static1.Index()); + EXPECT_EQ(2u, static2.Index()); - entry.SetReferenced(true); - EXPECT_TRUE(entry.IsReferenced()); - EXPECT_EQ(HpackEntry::kUntouched, entry.TouchCount()); + HpackEntry dynamic1(DynamicEntry()); + HpackEntry dynamic2(DynamicEntry()); - entry.SetReferenced(false); - EXPECT_FALSE(entry.IsReferenced()); - EXPECT_EQ(HpackEntry::kUntouched, entry.TouchCount()); + EXPECT_EQ(1u, dynamic2.Index()); + EXPECT_EQ(2u, dynamic1.Index()); + EXPECT_EQ(3u, static1.Index()); + EXPECT_EQ(4u, static2.Index()); + + DropEntry(); // Drops |dynamic1|. + + EXPECT_EQ(1u, dynamic2.Index()); + EXPECT_EQ(2u, static1.Index()); + EXPECT_EQ(3u, static2.Index()); + + HpackEntry dynamic3(DynamicEntry()); + + EXPECT_EQ(1u, dynamic3.Index()); + EXPECT_EQ(2u, dynamic2.Index()); + EXPECT_EQ(3u, static1.Index()); + EXPECT_EQ(4u, static2.Index()); } -// Make sure changing the touch count doesn't affect the referenced -// bit when it's false. -TEST(HpackEntryTest, TouchCountNotReferenced) { - HpackEntry entry(kName, kValue); - EXPECT_FALSE(entry.IsReferenced()); - EXPECT_EQ(HpackEntry::kUntouched, entry.TouchCount()); - - entry.AddTouches(0); - EXPECT_FALSE(entry.IsReferenced()); - EXPECT_EQ(0u, entry.TouchCount()); - - entry.AddTouches(255); - EXPECT_FALSE(entry.IsReferenced()); - EXPECT_EQ(255u, entry.TouchCount()); - - // Assumes kUntouched is 1 + max touch count. - entry.AddTouches(HpackEntry::kUntouched - 256); - EXPECT_FALSE(entry.IsReferenced()); - EXPECT_EQ(HpackEntry::kUntouched - 1, entry.TouchCount()); - - entry.ClearTouches(); - EXPECT_FALSE(entry.IsReferenced()); - EXPECT_EQ(HpackEntry::kUntouched, entry.TouchCount()); +TEST_F(HpackEntryTest, ComparatorNameOrdering) { + HpackEntry entry1(StaticEntry()); + name_[0]--; + HpackEntry entry2(StaticEntry()); + + EXPECT_FALSE(HpackEntry::Comparator()(&entry1, &entry2)); + EXPECT_TRUE(HpackEntry::Comparator()(&entry2, &entry1)); } -// Make sure changing the touch count doesn't affect the referenced -// bit when it's true. -TEST(HpackEntryTest, TouchCountReferenced) { - HpackEntry entry(kName, kValue); - entry.SetReferenced(true); - EXPECT_TRUE(entry.IsReferenced()); - EXPECT_EQ(HpackEntry::kUntouched, entry.TouchCount()); - - entry.AddTouches(0); - EXPECT_TRUE(entry.IsReferenced()); - EXPECT_EQ(0u, entry.TouchCount()); - - entry.AddTouches(255); - EXPECT_TRUE(entry.IsReferenced()); - EXPECT_EQ(255u, entry.TouchCount()); - - // Assumes kUntouched is 1 + max touch count. - entry.AddTouches(HpackEntry::kUntouched - 256); - EXPECT_TRUE(entry.IsReferenced()); - EXPECT_EQ(HpackEntry::kUntouched - 1, entry.TouchCount()); - - entry.ClearTouches(); - EXPECT_TRUE(entry.IsReferenced()); - EXPECT_EQ(HpackEntry::kUntouched, entry.TouchCount()); +TEST_F(HpackEntryTest, ComparatorValueOrdering) { + HpackEntry entry1(StaticEntry()); + value_[0]--; + HpackEntry entry2(StaticEntry()); + + EXPECT_FALSE(HpackEntry::Comparator()(&entry1, &entry2)); + EXPECT_TRUE(HpackEntry::Comparator()(&entry2, &entry1)); } -// Make sure equality takes into account all entry fields. -TEST(HpackEntryTest, Equals) { - HpackEntry entry1(kName, kValue); - HpackEntry entry2(kName, kValue); - EXPECT_TRUE(entry1.Equals(entry2)); +TEST_F(HpackEntryTest, ComparatorIndexOrdering) { + HpackEntry entry1(StaticEntry()); + HpackEntry entry2(StaticEntry()); + + EXPECT_TRUE(HpackEntry::Comparator()(&entry1, &entry2)); + EXPECT_FALSE(HpackEntry::Comparator()(&entry2, &entry1)); - entry2.SetReferenced(true); - EXPECT_FALSE(entry1.Equals(entry2)); - entry2.SetReferenced(false); - EXPECT_TRUE(entry1.Equals(entry2)); + HpackEntry entry3(DynamicEntry()); + HpackEntry entry4(DynamicEntry()); - entry2.AddTouches(0); - EXPECT_FALSE(entry1.Equals(entry2)); - entry2.ClearTouches(); - EXPECT_TRUE(entry1.Equals(entry2)); + // |entry4| has lower index than |entry3|. + EXPECT_TRUE(HpackEntry::Comparator()(&entry4, &entry3)); + EXPECT_FALSE(HpackEntry::Comparator()(&entry3, &entry4)); - entry2.AddTouches(1); - EXPECT_FALSE(entry1.Equals(entry2)); - entry2.ClearTouches(); - EXPECT_TRUE(entry1.Equals(entry2)); + // |entry3| has lower index than |entry1|. + EXPECT_TRUE(HpackEntry::Comparator()(&entry3, &entry1)); + EXPECT_FALSE(HpackEntry::Comparator()(&entry1, &entry3)); + + // |entry1| & |entry2| ordering is preserved, though each Index() has changed. + EXPECT_TRUE(HpackEntry::Comparator()(&entry1, &entry2)); + EXPECT_FALSE(HpackEntry::Comparator()(&entry2, &entry1)); +} - HpackEntry entry3(kName, string(kValue) + kValue); - EXPECT_FALSE(entry1.Equals(entry3)); +TEST_F(HpackEntryTest, ComparatorEqualityOrdering) { + HpackEntry entry1(StaticEntry()); + HpackEntry entry2(DynamicEntry()); - HpackEntry entry4(string(kName) + kName, kValue); - EXPECT_FALSE(entry1.Equals(entry4)); + EXPECT_FALSE(HpackEntry::Comparator()(&entry1, &entry1)); + EXPECT_FALSE(HpackEntry::Comparator()(&entry2, &entry2)); } } // namespace diff --git a/net/spdy/hpack_header_table.cc b/net/spdy/hpack_header_table.cc index 1320bfb..a7da21b 100644 --- a/net/spdy/hpack_header_table.cc +++ b/net/spdy/hpack_header_table.cc @@ -4,76 +4,280 @@ #include "net/spdy/hpack_header_table.h" +#include <algorithm> + #include "base/logging.h" #include "net/spdy/hpack_constants.h" #include "net/spdy/hpack_string_util.h" namespace net { +using base::StringPiece; + +namespace { + +// An entry in the static table. Must be a POD in order to avoid +// static initializers, i.e. no user-defined constructors or +// destructors. +struct StaticEntry { + const char* const name; + const size_t name_len; + const char* const value; + const size_t value_len; +}; + +// The "constructor" for a StaticEntry that computes the lengths at +// compile time. +#define STATIC_ENTRY(name, value) \ + { name, arraysize(name) - 1, value, arraysize(value) - 1 } + +const StaticEntry kStaticTable[] = { + STATIC_ENTRY(":authority" , ""), // 1 + STATIC_ENTRY(":method" , "GET"), // 2 + STATIC_ENTRY(":method" , "POST"), // 3 + STATIC_ENTRY(":path" , "/"), // 4 + STATIC_ENTRY(":path" , "/index.html"), // 5 + STATIC_ENTRY(":scheme" , "http"), // 6 + STATIC_ENTRY(":scheme" , "https"), // 7 + STATIC_ENTRY(":status" , "200"), // 8 + STATIC_ENTRY(":status" , "500"), // 9 + STATIC_ENTRY(":status" , "404"), // 10 + STATIC_ENTRY(":status" , "403"), // 11 + STATIC_ENTRY(":status" , "400"), // 12 + STATIC_ENTRY(":status" , "401"), // 13 + STATIC_ENTRY("accept-charset" , ""), // 14 + STATIC_ENTRY("accept-encoding" , ""), // 15 + STATIC_ENTRY("accept-language" , ""), // 16 + STATIC_ENTRY("accept-ranges" , ""), // 17 + STATIC_ENTRY("accept" , ""), // 18 + STATIC_ENTRY("access-control-allow-origin" , ""), // 19 + STATIC_ENTRY("age" , ""), // 20 + STATIC_ENTRY("allow" , ""), // 21 + STATIC_ENTRY("authorization" , ""), // 22 + STATIC_ENTRY("cache-control" , ""), // 23 + STATIC_ENTRY("content-disposition" , ""), // 24 + STATIC_ENTRY("content-encoding" , ""), // 25 + STATIC_ENTRY("content-language" , ""), // 26 + STATIC_ENTRY("content-length" , ""), // 27 + STATIC_ENTRY("content-location" , ""), // 28 + STATIC_ENTRY("content-range" , ""), // 29 + STATIC_ENTRY("content-type" , ""), // 30 + STATIC_ENTRY("cookie" , ""), // 31 + STATIC_ENTRY("date" , ""), // 32 + STATIC_ENTRY("etag" , ""), // 33 + STATIC_ENTRY("expect" , ""), // 34 + STATIC_ENTRY("expires" , ""), // 35 + STATIC_ENTRY("from" , ""), // 36 + STATIC_ENTRY("host" , ""), // 37 + STATIC_ENTRY("if-match" , ""), // 38 + STATIC_ENTRY("if-modified-since" , ""), // 39 + STATIC_ENTRY("if-none-match" , ""), // 40 + STATIC_ENTRY("if-range" , ""), // 41 + STATIC_ENTRY("if-unmodified-since" , ""), // 42 + STATIC_ENTRY("last-modified" , ""), // 43 + STATIC_ENTRY("link" , ""), // 44 + STATIC_ENTRY("location" , ""), // 45 + STATIC_ENTRY("max-forwards" , ""), // 46 + STATIC_ENTRY("proxy-authenticate" , ""), // 47 + STATIC_ENTRY("proxy-authorization" , ""), // 48 + STATIC_ENTRY("range" , ""), // 49 + STATIC_ENTRY("referer" , ""), // 50 + STATIC_ENTRY("refresh" , ""), // 51 + STATIC_ENTRY("retry-after" , ""), // 52 + STATIC_ENTRY("server" , ""), // 53 + STATIC_ENTRY("set-cookie" , ""), // 54 + STATIC_ENTRY("strict-transport-security" , ""), // 55 + STATIC_ENTRY("transfer-encoding" , ""), // 56 + STATIC_ENTRY("user-agent" , ""), // 57 + STATIC_ENTRY("vary" , ""), // 58 + STATIC_ENTRY("via" , ""), // 59 + STATIC_ENTRY("www-authenticate" , ""), // 60 +}; + +#undef STATIC_ENTRY + +} // namespace + HpackHeaderTable::HpackHeaderTable() - : size_(0), - max_size_(kDefaultHeaderTableSizeSetting) {} + : settings_size_bound_(kDefaultHeaderTableSizeSetting), + size_(0), + max_size_(kDefaultHeaderTableSizeSetting), + total_insertions_(0), + dynamic_entries_count_(0) { + for (const StaticEntry* it = kStaticTable; + it != kStaticTable + arraysize(kStaticTable); ++it) { + static_entries_.push_back( + HpackEntry(StringPiece(it->name, it->name_len), + StringPiece(it->value, it->value_len), + true, // is_static + total_insertions_, + &dynamic_entries_count_)); + CHECK(index_.insert(&static_entries_.back()).second); + + ++total_insertions_; + } +} HpackHeaderTable::~HpackHeaderTable() {} -uint32 HpackHeaderTable::GetEntryCount() const { - size_t size = entries_.size(); - DCHECK_LE(size, kuint32max); - return static_cast<uint32>(size); +HpackEntry* HpackHeaderTable::GetByIndex(size_t index) { + if (index == 0) { + return NULL; + } + index -= 1; + if (index < dynamic_entries_.size()) { + return &dynamic_entries_[index]; + } + index -= dynamic_entries_.size(); + if (index < static_entries_.size()) { + return &static_entries_[index]; + } + return NULL; } -const HpackEntry& HpackHeaderTable::GetEntry(uint32 index) const { - CHECK_GE(index, 1u); - CHECK_LE(index, GetEntryCount()); - return entries_[index-1]; +HpackEntry* HpackHeaderTable::GetByName(StringPiece name) { + HpackEntry query(name, ""); + HpackEntry::OrderedSet::const_iterator it = index_.lower_bound(&query); + if (it != index_.end() && (*it)->name() == name) { + return *it; + } + return NULL; } -HpackEntry* HpackHeaderTable::GetMutableEntry(uint32 index) { - CHECK_GE(index, 1u); - CHECK_LE(index, GetEntryCount()); - return &entries_[index-1]; +HpackEntry* HpackHeaderTable::GetByNameAndValue(StringPiece name, + StringPiece value) { + HpackEntry query(name, value); + HpackEntry::OrderedSet::const_iterator it = index_.lower_bound(&query); + if (it != index_.end() && (*it)->name() == name && (*it)->value() == value) { + return *it; + } + return NULL; } -void HpackHeaderTable::SetMaxSize(uint32 max_size) { +void HpackHeaderTable::SetMaxSize(size_t max_size) { + CHECK_LE(max_size, settings_size_bound_); + max_size_ = max_size; - while (size_ > max_size_) { - CHECK(!entries_.empty()); - size_ -= entries_.back().Size(); - entries_.pop_back(); + if (size_ > max_size_) { + Evict(EvictionCountToReclaim(size_ - max_size_)); + CHECK_LE(size_, max_size_); + } +} + +void HpackHeaderTable::SetSettingsHeaderTableSize(size_t settings_size) { + settings_size_bound_ = settings_size; + if (settings_size_bound_ < max_size_) { + SetMaxSize(settings_size_bound_); } } -void HpackHeaderTable::TryAddEntry( - const HpackEntry& entry, - uint32* index, - std::vector<uint32>* removed_referenced_indices) { - *index = 0; - removed_referenced_indices->clear(); - - // The algorithm used here is described in 3.3.3. We're assuming - // that the given entry is caching the name/value. - size_t target_size = 0; - size_t size_t_max_size = static_cast<size_t>(max_size_); - if (entry.Size() <= size_t_max_size) { - // The conditional implies the difference can fit in 32 bits. - target_size = size_t_max_size - entry.Size(); - } - while (static_cast<size_t>(size_) > target_size) { - DCHECK(!entries_.empty()); - if (entries_.back().IsReferenced()) { - removed_referenced_indices->push_back(entries_.size()); - } - size_ -= entries_.back().Size(); - entries_.pop_back(); - } - - if (entry.Size() <= size_t_max_size) { - // Implied by the exit condition of the while loop above and the - // condition of the if. - DCHECK_LE(static_cast<size_t>(size_) + entry.Size(), size_t_max_size); - size_ += entry.Size(); - *index = 1; - entries_.push_front(entry); +void HpackHeaderTable::EvictionSet(StringPiece name, + StringPiece value, + EntryTable::iterator* begin_out, + EntryTable::iterator* end_out) { + size_t eviction_count = EvictionCountForEntry(name, value); + *begin_out = dynamic_entries_.end() - eviction_count; + *end_out = dynamic_entries_.end(); +} + +size_t HpackHeaderTable::EvictionCountForEntry(StringPiece name, + StringPiece value) const { + size_t available_size = max_size_ - size_; + size_t entry_size = HpackEntry::Size(name, value); + + if (entry_size <= available_size) { + // No evictions are required. + return 0; + } + return EvictionCountToReclaim(entry_size - available_size); +} + +size_t HpackHeaderTable::EvictionCountToReclaim(size_t reclaim_size) const { + size_t count = 0; + for (EntryTable::const_reverse_iterator it = dynamic_entries_.rbegin(); + it != dynamic_entries_.rend() && reclaim_size != 0; ++it, ++count) { + reclaim_size -= std::min(reclaim_size, it->Size()); + } + return count; +} + +void HpackHeaderTable::Evict(size_t count) { + for (size_t i = 0; i != count; ++i) { + CHECK(!dynamic_entries_.empty()); + HpackEntry* entry = &dynamic_entries_.back(); + + size_ -= entry->Size(); + CHECK_EQ(1u, index_.erase(entry)); + reference_set_.erase(entry); + dynamic_entries_.pop_back(); + + --dynamic_entries_count_; + DCHECK_EQ(dynamic_entries_count_, dynamic_entries_.size()); + } +} + +HpackEntry* HpackHeaderTable::TryAddEntry(StringPiece name, StringPiece value) { + Evict(EvictionCountForEntry(name, value)); + + size_t entry_size = HpackEntry::Size(name, value); + if (entry_size > (max_size_ - size_)) { + // Entire table has been emptied, but there's still insufficient room. + DCHECK(dynamic_entries_.empty()); + DCHECK_EQ(0u, size_); + return NULL; + } + dynamic_entries_.push_front(HpackEntry(name, + value, + false, // is_static + total_insertions_, + &total_insertions_)); + CHECK(index_.insert(&dynamic_entries_.front()).second); + + size_ += entry_size; + ++dynamic_entries_count_; + ++total_insertions_; + + DCHECK_EQ(dynamic_entries_count_, dynamic_entries_.size()); + return &dynamic_entries_.front(); +} + +void HpackHeaderTable::ClearReferenceSet() { + for (HpackEntry::OrderedSet::iterator it = reference_set_.begin(); + it != reference_set_.end(); ++it) { + (*it)->set_state(0); + } + reference_set_.clear(); +} + +bool HpackHeaderTable::Toggle(HpackEntry* entry) { + CHECK(!entry->IsStatic()); + CHECK_EQ(0u, entry->state()); + + std::pair<HpackEntry::OrderedSet::iterator, bool> insert_result = + reference_set_.insert(entry); + if (insert_result.second) { + return true; + } else { + reference_set_.erase(insert_result.first); + return false; + } +} + +void HpackHeaderTable::DebugLogTableState() const { + DVLOG(2) << "Reference Set:"; + for (HpackEntry::OrderedSet::const_iterator it = reference_set_.begin(); + it != reference_set_.end(); ++it) { + DVLOG(2) << " " << (*it)->GetDebugString(); + } + DVLOG(2) << "Dynamic table:"; + for (EntryTable::const_iterator it = dynamic_entries_.begin(); + it != dynamic_entries_.end(); ++it) { + DVLOG(2) << " " << it->GetDebugString(); + } + DVLOG(2) << "Full Index:"; + for (HpackEntry::OrderedSet::const_iterator it = index_.begin(); + it != index_.end(); ++it) { + DVLOG(2) << " " << (*it)->GetDebugString(); } } diff --git a/net/spdy/hpack_header_table.h b/net/spdy/hpack_header_table.h index 792fcfb..0e0a01b 100644 --- a/net/spdy/hpack_header_table.h +++ b/net/spdy/hpack_header_table.h @@ -7,59 +7,127 @@ #include <cstddef> #include <deque> -#include <vector> +#include <set> #include "base/basictypes.h" #include "base/macros.h" #include "net/base/net_export.h" #include "net/spdy/hpack_entry.h" -namespace net { - // All section references below are to // http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-06 +namespace net { + +namespace test { +class HpackHeaderTablePeer; +} // namespace test + // A data structure for both the header table (described in 3.1.2) and -// the reference set (3.1.3). This structure also keeps track of how -// many times a header has been 'touched', which is useful for both -// encoding and decoding. +// the reference set (3.1.3). class NET_EXPORT_PRIVATE HpackHeaderTable { public: + friend class test::HpackHeaderTablePeer; + + // HpackHeaderTable takes advantage of the deque property that references + // remain valid, so long as insertions & deletions are at the head & tail. + // If this changes (eg we start to drop entries from the middle of the table), + // this needs to be a std::list, in which case |index_| can be trivially + // extended to map to list iterators. + typedef std::deque<HpackEntry> EntryTable; + HpackHeaderTable(); ~HpackHeaderTable(); - uint32 size() const { return size_; } - uint32 max_size() const { return max_size_; } + // Last-aknowledged value of SETTINGS_HEADER_TABLE_SIZE. + size_t settings_size_bound() { return settings_size_bound_; } + + // Current and maximum estimated byte size of the table, as described in + // 3.3.1. Notably, this is /not/ the number of entries in the table. + size_t size() const { return size_; } + size_t max_size() const { return max_size_; } + + const HpackEntry::OrderedSet& reference_set() { + return reference_set_; + } - // Returns the total number of entries. - uint32 GetEntryCount() const; + // Returns the entry matching the index, or NULL. + HpackEntry* GetByIndex(size_t index); - // The given index must be >= 1 and <= GetEntryCount(). - const HpackEntry& GetEntry(uint32 index) const; + // Returns the lowest-value entry having |name|, or NULL. + HpackEntry* GetByName(base::StringPiece name); - // The given index must be >= 1 and <= GetEntryCount(). - HpackEntry* GetMutableEntry(uint32 index); + // Returns the lowest-index matching entry, or NULL. + HpackEntry* GetByNameAndValue(base::StringPiece name, + base::StringPiece value); // Sets the maximum size of the header table, evicting entries if // necessary as described in 3.3.2. - void SetMaxSize(uint32 max_size); - - // The given entry must not be one from the header table, since it - // may get evicted. Tries to add the given entry to the header - // table, evicting entries if necessary as described in 3.3.3. index - // will be filled in with the index of the added entry, or 0 if the - // entry could not be added. removed_referenced_indices will be - // filled in with the indices of any removed entries that were in - // the reference set. - void TryAddEntry(const HpackEntry& entry, - uint32* index, - std::vector<uint32>* removed_referenced_indices); + void SetMaxSize(size_t max_size); + + // Sets the SETTINGS_HEADER_TABLE_SIZE bound of the table. Will call + // SetMaxSize() as needed to preserve max_size() <= settings_size_bound(). + void SetSettingsHeaderTableSize(size_t settings_size); + + // Determine the set of entries which would be evicted by the insertion + // of |name| & |value| into the table, as per section 3.3.3. No eviction + // actually occurs. The set is returned via range [begin_out, end_out). + void EvictionSet(base::StringPiece name, base::StringPiece value, + EntryTable::iterator* begin_out, + EntryTable::iterator* end_out); + + // Adds an entry for the representation, evicting entries as needed. |name| + // and |value| must not be owned by an entry which could be evicted. The + // added HpackEntry is returned, or NULL is returned if all entries were + // evicted and the empty table is of insufficent size for the representation. + HpackEntry* TryAddEntry(base::StringPiece name, base::StringPiece value); + + // Toggles the presence of a dynamic entry in the reference set. Returns + // true if the entry was added, or false if removed. It is an error to + // Toggle(entry) if |entry->state()| != 0. + bool Toggle(HpackEntry* entry); + + // Removes all entries from the reference set. Sets the state of each removed + // entry to zero. + void ClearReferenceSet(); + + void DebugLogTableState() const; private: - std::deque<HpackEntry> entries_; - uint32 size_; - uint32 max_size_; + // Returns number of evictions required to enter |name| & |value|. + size_t EvictionCountForEntry(base::StringPiece name, + base::StringPiece value) const; + + // Returns number of evictions required to reclaim |reclaim_size| table size. + size_t EvictionCountToReclaim(size_t reclaim_size) const; + + // Evicts |count| oldest entries from the table. + void Evict(size_t count); + + EntryTable dynamic_entries_; + EntryTable static_entries_; + + // Full table index, over |dynamic_entries_| and |static_entries_|. + HpackEntry::OrderedSet index_; + // The reference set is strictly a subset of |dynamic_entries_|. + HpackEntry::OrderedSet reference_set_; + + // Last acknowledged value for SETTINGS_HEADER_TABLE_SIZE. + size_t settings_size_bound_; + + // Estimated current and maximum byte size of the table. + // |max_size_| <= |settings_header_table_size_| + size_t size_; + size_t max_size_; + + // Total number of table insertions which have occurred. Referenced by + // dynamic HpackEntry instances for determination of table index. + size_t total_insertions_; + + // Current number of dynamic entries. Referenced by static HpackEntry + // instances for determination of table index. + size_t dynamic_entries_count_; DISALLOW_COPY_AND_ASSIGN(HpackHeaderTable); }; diff --git a/net/spdy/hpack_header_table_test.cc b/net/spdy/hpack_header_table_test.cc index 0349e06..90d8135 100644 --- a/net/spdy/hpack_header_table_test.cc +++ b/net/spdy/hpack_header_table_test.cc @@ -11,207 +11,430 @@ #include "base/basictypes.h" #include "base/macros.h" +#include "net/spdy/hpack_constants.h" #include "net/spdy/hpack_entry.h" #include "testing/gtest/include/gtest/gtest.h" namespace net { -namespace { - +using base::StringPiece; +using std::distance; using std::string; -typedef std::vector<HpackEntry> HpackEntryVector; +namespace test { -// Returns an entry whose Size() is equal to the given one. -HpackEntry MakeEntryOfSize(uint32 size) { - EXPECT_GE(size, HpackEntry::kSizeOverhead); - string name((size - HpackEntry::kSizeOverhead) / 2, 'n'); - string value(size - HpackEntry::kSizeOverhead - name.size(), 'v'); - HpackEntry entry(name, value); - EXPECT_EQ(size, entry.Size()); - return entry; -} +class HpackHeaderTablePeer { + public: + explicit HpackHeaderTablePeer(HpackHeaderTable* table) + : table_(table) {} -// Returns a vector of entries whose total size is equal to the given -// one. -HpackEntryVector MakeEntriesOfTotalSize(uint32 total_size) { - EXPECT_GE(total_size, HpackEntry::kSizeOverhead); - uint32 entry_size = HpackEntry::kSizeOverhead; - uint32 remaining_size = total_size; - HpackEntryVector entries; - while (remaining_size > 0) { - EXPECT_LE(entry_size, remaining_size); - entries.push_back(MakeEntryOfSize(entry_size)); - remaining_size -= entry_size; - entry_size = std::min(remaining_size, entry_size + 32); + const HpackHeaderTable::EntryTable& dynamic_entries() { + return table_->dynamic_entries_; + } + const HpackHeaderTable::EntryTable& static_entries() { + return table_->static_entries_; + } + const HpackEntry::OrderedSet& index() { + return table_->index_; + } + std::vector<HpackEntry*> EvictionSet(StringPiece name, StringPiece value) { + HpackHeaderTable::EntryTable::iterator begin, end; + table_->EvictionSet(name, value, &begin, &end); + std::vector<HpackEntry*> result; + for (; begin != end; ++begin) { + result.push_back(&(*begin)); + } + return result; + } + size_t total_insertions() { + return table_->total_insertions_; + } + size_t dynamic_entries_count() { + return table_->dynamic_entries_count_; + } + size_t EvictionCountForEntry(StringPiece name, StringPiece value) { + return table_->EvictionCountForEntry(name, value); + } + size_t EvictionCountToReclaim(size_t reclaim_size) { + return table_->EvictionCountToReclaim(reclaim_size); + } + void Evict(size_t count) { + return table_->Evict(count); } - return entries; -} -// Adds the given vector of entries to the given header table, -// expecting no eviction to happen. -void AddEntriesExpectNoEviction(const HpackEntryVector& entries, - HpackHeaderTable* header_table) { - unsigned start_entry_count = header_table->GetEntryCount(); - for (HpackEntryVector::const_iterator it = entries.begin(); - it != entries.end(); ++it) { - uint32 index = 0; - std::vector<uint32> removed_referenced_indices; - header_table->TryAddEntry(*it, &index, &removed_referenced_indices); - EXPECT_EQ(1u, index); - EXPECT_TRUE(removed_referenced_indices.empty()); - EXPECT_EQ(start_entry_count + (it - entries.begin()) + 1u, - header_table->GetEntryCount()); + private: + HpackHeaderTable* table_; +}; + +} // namespace test + +namespace { + +class HpackHeaderTableTest : public ::testing::Test { + protected: + typedef std::vector<HpackEntry> HpackEntryVector; + + HpackHeaderTableTest() + : table_(), + peer_(&table_) {} + + // Returns an entry whose Size() is equal to the given one. + static HpackEntry MakeEntryOfSize(uint32 size) { + EXPECT_GE(size, HpackEntry::kSizeOverhead); + string name((size - HpackEntry::kSizeOverhead) / 2, 'n'); + string value(size - HpackEntry::kSizeOverhead - name.size(), 'v'); + HpackEntry entry(name, value); + EXPECT_EQ(size, entry.Size()); + return entry; } - for (HpackEntryVector::const_iterator it = entries.begin(); - it != entries.end(); ++it) { - uint32 index = header_table->GetEntryCount() - (it - entries.begin()); - HpackEntry entry = header_table->GetEntry(index); - EXPECT_TRUE(it->Equals(entry)) - << "it = " << it->GetDebugString() << " != entry = " - << entry.GetDebugString(); + // Returns a vector of entries whose total size is equal to the given + // one. + static HpackEntryVector MakeEntriesOfTotalSize(uint32 total_size) { + EXPECT_GE(total_size, HpackEntry::kSizeOverhead); + uint32 entry_size = HpackEntry::kSizeOverhead; + uint32 remaining_size = total_size; + HpackEntryVector entries; + while (remaining_size > 0) { + EXPECT_LE(entry_size, remaining_size); + entries.push_back(MakeEntryOfSize(entry_size)); + remaining_size -= entry_size; + entry_size = std::min(remaining_size, entry_size + 32); + } + return entries; } -} -// Returns the set of all indices in header_table that are in that -// table's reference set. -std::set<uint32> GetReferenceSet(const HpackHeaderTable& header_table) { - std::set<uint32> reference_set; - for (uint32 i = 1; i <= header_table.GetEntryCount(); ++i) { - if (header_table.GetEntry(i).IsReferenced()) { - reference_set.insert(i); + // Adds the given vector of entries to the given header table, + // expecting no eviction to happen. + void AddEntriesExpectNoEviction(const HpackEntryVector& entries) { + for (HpackEntryVector::const_iterator it = entries.begin(); + it != entries.end(); ++it) { + HpackHeaderTable::EntryTable::iterator begin, end; + + table_.EvictionSet(it->name(), it->value(), &begin, &end); + EXPECT_EQ(0, distance(begin, end)); + + HpackEntry* entry = table_.TryAddEntry(it->name(), it->value()); + EXPECT_NE(entry, static_cast<HpackEntry*>(NULL)); } + + for (size_t i = 0; i != entries.size(); ++i) { + size_t index = entries.size() - i; + HpackEntry* entry = table_.GetByIndex(index); + EXPECT_EQ(entries[i].name(), entry->name()); + EXPECT_EQ(entries[i].value(), entry->value()); + EXPECT_EQ(index, entry->Index()); + } + } + + HpackHeaderTable table_; + test::HpackHeaderTablePeer peer_; +}; + +TEST_F(HpackHeaderTableTest, StaticTableInitialization) { + EXPECT_EQ(0u, table_.size()); + EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.max_size()); + EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.settings_size_bound()); + + EXPECT_EQ(0u, peer_.dynamic_entries_count()); + EXPECT_EQ(0u, table_.reference_set().size()); + EXPECT_EQ(peer_.static_entries().size(), peer_.total_insertions()); + + // Static entries have been populated and inserted into the table & index. + EXPECT_NE(0u, peer_.static_entries().size()); + EXPECT_EQ(peer_.index().size(), peer_.static_entries().size()); + for (size_t i = 0; i != peer_.static_entries().size(); ++i) { + const HpackEntry* entry = &peer_.static_entries()[i]; + + EXPECT_TRUE(entry->IsStatic()); + EXPECT_EQ(entry, table_.GetByIndex(i + 1)); + EXPECT_EQ(entry, table_.GetByNameAndValue(entry->name(), entry->value())); } - return reference_set; +} + +TEST_F(HpackHeaderTableTest, BasicDynamicEntryInsertionAndEviction) { + size_t static_count = peer_.total_insertions(); + HpackEntry* first_static_entry = table_.GetByIndex(1); + + EXPECT_EQ(1u, first_static_entry->Index()); + + HpackEntry* entry = table_.TryAddEntry("header-key", "Header Value"); + EXPECT_EQ("header-key", entry->name()); + EXPECT_EQ("Header Value", entry->value()); + EXPECT_FALSE(entry->IsStatic()); + + // Table counts were updated appropriately. + EXPECT_EQ(entry->Size(), table_.size()); + EXPECT_EQ(1u, peer_.dynamic_entries_count()); + EXPECT_EQ(peer_.dynamic_entries().size(), peer_.dynamic_entries_count()); + EXPECT_EQ(static_count + 1, peer_.total_insertions()); + EXPECT_EQ(static_count + 1, peer_.index().size()); + + // Index() of entries reflects the insertion. + EXPECT_EQ(1u, entry->Index()); + EXPECT_EQ(2u, first_static_entry->Index()); + EXPECT_EQ(entry, table_.GetByIndex(1)); + EXPECT_EQ(first_static_entry, table_.GetByIndex(2)); + + // Evict |entry|. Table counts are again updated appropriately. + peer_.Evict(1); + EXPECT_EQ(0u, table_.size()); + EXPECT_EQ(0u, peer_.dynamic_entries_count()); + EXPECT_EQ(peer_.dynamic_entries().size(), peer_.dynamic_entries_count()); + EXPECT_EQ(static_count + 1, peer_.total_insertions()); + EXPECT_EQ(static_count, peer_.index().size()); + + // Index() of |first_static_entry| reflects the eviction. + EXPECT_EQ(1u, first_static_entry->Index()); + EXPECT_EQ(first_static_entry, table_.GetByIndex(1)); +} + +TEST_F(HpackHeaderTableTest, EntryIndexing) { + HpackEntry* first_static_entry = table_.GetByIndex(1); + + // Static entries are queryable by name & value. + EXPECT_EQ(first_static_entry, table_.GetByName(first_static_entry->name())); + EXPECT_EQ(first_static_entry, table_.GetByNameAndValue( + first_static_entry->name(), first_static_entry->value())); + + // Create a mix of entries which duplicate names, and names & values of both + // dynamic and static entries. + HpackEntry* entry1 = table_.TryAddEntry(first_static_entry->name(), + first_static_entry->value()); + HpackEntry* entry2 = table_.TryAddEntry(first_static_entry->name(), + "Value Four"); + HpackEntry* entry3 = table_.TryAddEntry("key-1", "Value One"); + HpackEntry* entry4 = table_.TryAddEntry("key-2", "Value Three"); + HpackEntry* entry5 = table_.TryAddEntry("key-1", "Value Two"); + HpackEntry* entry6 = table_.TryAddEntry("key-2", "Value Three"); + HpackEntry* entry7 = table_.TryAddEntry("key-2", "Value Four"); + + // Entries are queryable under their current index. + EXPECT_EQ(entry7, table_.GetByIndex(1)); + EXPECT_EQ(entry6, table_.GetByIndex(2)); + EXPECT_EQ(entry5, table_.GetByIndex(3)); + EXPECT_EQ(entry4, table_.GetByIndex(4)); + EXPECT_EQ(entry3, table_.GetByIndex(5)); + EXPECT_EQ(entry2, table_.GetByIndex(6)); + EXPECT_EQ(entry1, table_.GetByIndex(7)); + EXPECT_EQ(first_static_entry, table_.GetByIndex(8)); + + // Querying by name returns the lowest-value matching entry. + EXPECT_EQ(entry3, table_.GetByName("key-1")); + EXPECT_EQ(entry7, table_.GetByName("key-2")); + EXPECT_EQ(entry2->name(), + table_.GetByName(first_static_entry->name())->name()); + EXPECT_EQ(NULL, table_.GetByName("not-present")); + + // Querying by name & value returns the lowest-index matching entry. + EXPECT_EQ(entry3, table_.GetByNameAndValue("key-1", "Value One")); + EXPECT_EQ(entry5, table_.GetByNameAndValue("key-1", "Value Two")); + EXPECT_EQ(entry6, table_.GetByNameAndValue("key-2", "Value Three")); + EXPECT_EQ(entry7, table_.GetByNameAndValue("key-2", "Value Four")); + EXPECT_EQ(entry1, table_.GetByNameAndValue(first_static_entry->name(), + first_static_entry->value())); + EXPECT_EQ(entry2, table_.GetByNameAndValue(first_static_entry->name(), + "Value Four")); + EXPECT_EQ(NULL, table_.GetByNameAndValue("key-1", "Not Present")); + EXPECT_EQ(NULL, table_.GetByNameAndValue("not-present", "Value One")); + + // Evict |entry1|. Queries for its name & value now return the static entry. + // |entry2| remains queryable. + peer_.Evict(1); + EXPECT_EQ(first_static_entry, + table_.GetByNameAndValue(first_static_entry->name(), + first_static_entry->value())); + EXPECT_EQ(entry2, table_.GetByNameAndValue(first_static_entry->name(), + "Value Four")); + + // Evict |entry2|. Queries by its name & value are not found. + peer_.Evict(1); + EXPECT_EQ(NULL, table_.GetByNameAndValue(first_static_entry->name(), + "Value Four")); +} + +TEST_F(HpackHeaderTableTest, SetSizes) { + string key = "key", value = "value"; + HpackEntry* entry1 = table_.TryAddEntry(key, value); + HpackEntry* entry2 = table_.TryAddEntry(key, value); + HpackEntry* entry3 = table_.TryAddEntry(key, value); + + // Set exactly large enough. No Evictions. + size_t max_size = entry1->Size() + entry2->Size() + entry3->Size(); + table_.SetMaxSize(max_size); + EXPECT_EQ(3u, peer_.dynamic_entries().size()); + + // Set just too small. One eviction. + max_size = entry1->Size() + entry2->Size() + entry3->Size() - 1; + table_.SetMaxSize(max_size); + EXPECT_EQ(2u, peer_.dynamic_entries().size()); + + // Changing SETTINGS_HEADER_TABLE_SIZE doesn't affect table_.max_size(), + // iff SETTINGS_HEADER_TABLE_SIZE >= |max_size|. + EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.settings_size_bound()); + table_.SetSettingsHeaderTableSize(kDefaultHeaderTableSizeSetting*2); + EXPECT_EQ(max_size, table_.max_size()); + table_.SetSettingsHeaderTableSize(max_size + 1); + EXPECT_EQ(max_size, table_.max_size()); + EXPECT_EQ(2u, peer_.dynamic_entries().size()); + + // SETTINGS_HEADER_TABLE_SIZE upper-bounds |table_.max_size()|, + // and will force evictions. + max_size = entry3->Size() - 1; + table_.SetSettingsHeaderTableSize(max_size); + EXPECT_EQ(max_size, table_.max_size()); + EXPECT_EQ(max_size, table_.settings_size_bound()); + EXPECT_EQ(0u, peer_.dynamic_entries().size()); +} + +TEST_F(HpackHeaderTableTest, ToggleReferenceSet) { + HpackEntry* entry1 = table_.TryAddEntry("key-1", "Value One"); + HpackEntry* entry2 = table_.TryAddEntry("key-2", "Value Two"); + + // Entries must be explictly toggled after creation. + EXPECT_EQ(0u, table_.reference_set().size()); + + // Add |entry1|. + EXPECT_TRUE(table_.Toggle(entry1)); + EXPECT_EQ(1u, table_.reference_set().size()); + EXPECT_EQ(1u, table_.reference_set().count(entry1)); + EXPECT_EQ(0u, table_.reference_set().count(entry2)); + + // Add |entry2|. + EXPECT_TRUE(table_.Toggle(entry2)); + EXPECT_EQ(2u, table_.reference_set().size()); + EXPECT_EQ(1u, table_.reference_set().count(entry1)); + EXPECT_EQ(1u, table_.reference_set().count(entry2)); + + // Remove |entry2|. + EXPECT_FALSE(table_.Toggle(entry2)); + EXPECT_EQ(1u, table_.reference_set().size()); + EXPECT_EQ(0u, table_.reference_set().count(entry2)); + + // Evict |entry1|. Implicit removal from reference set. + peer_.Evict(1); + EXPECT_EQ(0u, table_.reference_set().size()); +} + +TEST_F(HpackHeaderTableTest, ClearReferenceSet) { + HpackEntry* entry1 = table_.TryAddEntry("key-1", "Value One"); + EXPECT_TRUE(table_.Toggle(entry1)); + entry1->set_state(123); + + // |entry1| state is cleared, and removed from the reference set. + table_.ClearReferenceSet(); + EXPECT_EQ(0u, entry1->state()); + EXPECT_EQ(0u, table_.reference_set().size()); +} + +TEST_F(HpackHeaderTableTest, EvictionCountForEntry) { + string key = "key", value = "value"; + HpackEntry* entry1 = table_.TryAddEntry(key, value); + HpackEntry* entry2 = table_.TryAddEntry(key, value); + size_t entry3_size = HpackEntry::Size(key, value); + + // Just enough capacity for third entry. + table_.SetMaxSize(entry1->Size() + entry2->Size() + entry3_size); + EXPECT_EQ(0u, peer_.EvictionCountForEntry(key, value)); + EXPECT_EQ(1u, peer_.EvictionCountForEntry(key, value + "x")); + + // No extra capacity. Third entry would force evictions. + table_.SetMaxSize(entry1->Size() + entry2->Size()); + EXPECT_EQ(1u, peer_.EvictionCountForEntry(key, value)); + EXPECT_EQ(2u, peer_.EvictionCountForEntry(key, value + "x")); +} + +TEST_F(HpackHeaderTableTest, EvictionCountToReclaim) { + string key = "key", value = "value"; + HpackEntry* entry1 = table_.TryAddEntry(key, value); + HpackEntry* entry2 = table_.TryAddEntry(key, value); + + EXPECT_EQ(1u, peer_.EvictionCountToReclaim(1)); + EXPECT_EQ(1u, peer_.EvictionCountToReclaim(entry1->Size())); + EXPECT_EQ(2u, peer_.EvictionCountToReclaim(entry1->Size() + 1)); + EXPECT_EQ(2u, peer_.EvictionCountToReclaim(entry1->Size() + entry2->Size())); } // Fill a header table with entries. Make sure the entries are in // reverse order in the header table. -TEST(HpackHeaderTableTest, TryAddEntryBasic) { - HpackHeaderTable header_table; - EXPECT_EQ(0u, header_table.size()); +TEST_F(HpackHeaderTableTest, TryAddEntryBasic) { + EXPECT_EQ(0u, table_.size()); + EXPECT_EQ(table_.settings_size_bound(), table_.max_size()); - HpackEntryVector entries = MakeEntriesOfTotalSize(header_table.max_size()); + HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size()); // Most of the checks are in AddEntriesExpectNoEviction(). - AddEntriesExpectNoEviction(entries, &header_table); - EXPECT_EQ(header_table.max_size(), header_table.size()); + AddEntriesExpectNoEviction(entries); + EXPECT_EQ(table_.max_size(), table_.size()); + EXPECT_EQ(table_.settings_size_bound(), table_.size()); } // Fill a header table with entries, and then ramp the table's max // size down to evict an entry one at a time. Make sure the eviction // happens as expected. -TEST(HpackHeaderTableTest, SetMaxSize) { - HpackHeaderTable header_table; +TEST_F(HpackHeaderTableTest, SetMaxSize) { + HpackEntryVector entries = MakeEntriesOfTotalSize( + kDefaultHeaderTableSizeSetting / 2); + AddEntriesExpectNoEviction(entries); - HpackEntryVector entries = MakeEntriesOfTotalSize(header_table.max_size()); - AddEntriesExpectNoEviction(entries, &header_table); - - for (HpackEntryVector::const_iterator it = entries.begin(); + for (HpackEntryVector::iterator it = entries.begin(); it != entries.end(); ++it) { - uint32 expected_count = entries.end() - it; - EXPECT_EQ(expected_count, header_table.GetEntryCount()); + size_t expected_count = distance(it, entries.end()); + EXPECT_EQ(expected_count, peer_.dynamic_entries().size()); - header_table.SetMaxSize(header_table.size() + 1); - EXPECT_EQ(expected_count, header_table.GetEntryCount()); + table_.SetMaxSize(table_.size() + 1); + EXPECT_EQ(expected_count, peer_.dynamic_entries().size()); - header_table.SetMaxSize(header_table.size()); - EXPECT_EQ(expected_count, header_table.GetEntryCount()); + table_.SetMaxSize(table_.size()); + EXPECT_EQ(expected_count, peer_.dynamic_entries().size()); --expected_count; - header_table.SetMaxSize(header_table.size() - 1); - EXPECT_EQ(expected_count, header_table.GetEntryCount()); - } - - EXPECT_EQ(0u, header_table.size()); -} - -// Setting the max size of a header table to zero should clear its -// reference set. -TEST(HpackHeaderTableTest, SetMaxSizeZeroClearsReferenceSet) { - HpackHeaderTable header_table; - - HpackEntryVector entries = MakeEntriesOfTotalSize(header_table.max_size()); - AddEntriesExpectNoEviction(entries, &header_table); - - std::set<uint32> expected_reference_set; - for (uint32 i = 1; i <= header_table.GetEntryCount(); ++i) { - header_table.GetMutableEntry(i)->SetReferenced(true); - expected_reference_set.insert(i); + table_.SetMaxSize(table_.size() - 1); + EXPECT_EQ(expected_count, peer_.dynamic_entries().size()); } - EXPECT_EQ(expected_reference_set, GetReferenceSet(header_table)); - - header_table.SetMaxSize(0); - EXPECT_TRUE(GetReferenceSet(header_table).empty()); + EXPECT_EQ(0u, table_.size()); } // Fill a header table with entries, and then add an entry just big // enough to cause eviction of all but one entry. Make sure the // eviction happens as expected and the long entry is inserted into // the table. -TEST(HpackHeaderTableTest, TryAddEntryEviction) { - HpackHeaderTable header_table; +TEST_F(HpackHeaderTableTest, TryAddEntryEviction) { + HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size()); + AddEntriesExpectNoEviction(entries); - HpackEntryVector entries = MakeEntriesOfTotalSize(header_table.max_size()); - AddEntriesExpectNoEviction(entries, &header_table); - - EXPECT_EQ(entries.size(), header_table.GetEntryCount()); - HpackEntry first_entry = header_table.GetEntry(1); + HpackEntry* survivor_entry = table_.GetByIndex(1); HpackEntry long_entry = - MakeEntryOfSize(header_table.size() - first_entry.Size()); - - header_table.SetMaxSize(header_table.size()); - EXPECT_EQ(entries.size(), header_table.GetEntryCount()); - - std::set<uint32> expected_reference_set; - for (uint32 i = 2; i <= header_table.GetEntryCount(); ++i) { - header_table.GetMutableEntry(i)->SetReferenced(true); - expected_reference_set.insert(i); - } - EXPECT_EQ(expected_reference_set, GetReferenceSet(header_table)); - - uint32 index = 0; - std::vector<uint32> removed_referenced_indices; - header_table.TryAddEntry(long_entry, &index, &removed_referenced_indices); - - EXPECT_EQ(1u, index); - EXPECT_EQ(expected_reference_set, - std::set<uint32>(removed_referenced_indices.begin(), - removed_referenced_indices.end())); - EXPECT_TRUE(GetReferenceSet(header_table).empty()); - EXPECT_EQ(2u, header_table.GetEntryCount()); - EXPECT_TRUE(header_table.GetEntry(1).Equals(long_entry)); - EXPECT_TRUE(header_table.GetEntry(2).Equals(first_entry)); + MakeEntryOfSize(table_.max_size() - survivor_entry->Size()); + + // All entries but the first are to be evicted. + EXPECT_EQ(peer_.dynamic_entries().size() - 1, peer_.EvictionSet( + long_entry.name(), long_entry.value()).size()); + + HpackEntry* new_entry = table_.TryAddEntry(long_entry.name(), + long_entry.value()); + EXPECT_EQ(1u, new_entry->Index()); + EXPECT_EQ(2u, peer_.dynamic_entries().size()); + EXPECT_EQ(table_.GetByIndex(2), survivor_entry); + EXPECT_EQ(table_.GetByIndex(1), new_entry); } // Fill a header table with entries, and then add an entry bigger than // the entire table. Make sure no entry remains in the table. -TEST(HpackHeaderTableTest, TryAddTooLargeEntry) { - HpackHeaderTable header_table; +TEST_F(HpackHeaderTableTest, TryAddTooLargeEntry) { + HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size()); + AddEntriesExpectNoEviction(entries); - HpackEntryVector entries = MakeEntriesOfTotalSize(header_table.max_size()); - AddEntriesExpectNoEviction(entries, &header_table); - - header_table.SetMaxSize(header_table.size()); - EXPECT_EQ(entries.size(), header_table.GetEntryCount()); - - std::set<uint32> expected_removed_referenced_indices; - for (uint32 i = 1; i <= header_table.GetEntryCount(); ++i) { - header_table.GetMutableEntry(i)->SetReferenced(true); - expected_removed_referenced_indices.insert(i); - } + HpackEntry long_entry = MakeEntryOfSize(table_.max_size() + 1); - HpackEntry long_entry = MakeEntryOfSize(header_table.size() + 1); - uint32 index = 0; - std::vector<uint32> removed_referenced_indices; - header_table.TryAddEntry(long_entry, &index, &removed_referenced_indices); + // All entries are to be evicted. + EXPECT_EQ(peer_.dynamic_entries().size(), peer_.EvictionSet( + long_entry.name(), long_entry.value()).size()); - EXPECT_EQ(0u, index); - EXPECT_EQ(expected_removed_referenced_indices, - std::set<uint32>(removed_referenced_indices.begin(), - removed_referenced_indices.end())); - EXPECT_EQ(0u, header_table.GetEntryCount()); + HpackEntry* new_entry = table_.TryAddEntry(long_entry.name(), + long_entry.value()); + EXPECT_EQ(new_entry, static_cast<HpackEntry*>(NULL)); + EXPECT_EQ(0u, peer_.dynamic_entries().size()); } } // namespace diff --git a/net/spdy/hpack_huffman_table.cc b/net/spdy/hpack_huffman_table.cc index 02910eb..9e8f6a1 100644 --- a/net/spdy/hpack_huffman_table.cc +++ b/net/spdy/hpack_huffman_table.cc @@ -248,6 +248,20 @@ void HpackHuffmanTable::EncodeString(StringPiece in, } } +size_t HpackHuffmanTable::EncodedSize(StringPiece in) const { + size_t bit_count = 0; + for (size_t i = 0; i != in.size(); i++) { + uint16 symbol_id = static_cast<uint8>(in[i]); + CHECK_GT(code_by_id_.size(), symbol_id); + + bit_count += length_by_id_[symbol_id]; + } + if (bit_count % 8 != 0) { + bit_count += 8 - bit_count % 8; + } + return bit_count / 8; +} + bool HpackHuffmanTable::DecodeString(HpackInputStream* in, size_t out_capacity, string* out) const { diff --git a/net/spdy/hpack_huffman_table.h b/net/spdy/hpack_huffman_table.h index 8f1ada9..f776ddd 100644 --- a/net/spdy/hpack_huffman_table.h +++ b/net/spdy/hpack_huffman_table.h @@ -77,6 +77,9 @@ class NET_EXPORT_PRIVATE HpackHuffmanTable { // context. void EncodeString(base::StringPiece in, HpackOutputStream* out) const; + // Returns the encoded size of the input string. + size_t EncodedSize(base::StringPiece in) const; + // Decodes symbols from |in| into |out|. It is the caller's responsibility // to ensure |out| has a reserved a sufficient buffer to hold decoded output. // DecodeString() halts when |in| runs out of input, in which case true is diff --git a/net/spdy/hpack_huffman_table_test.cc b/net/spdy/hpack_huffman_table_test.cc index 0c6417b..b64c374 100644 --- a/net/spdy/hpack_huffman_table_test.cc +++ b/net/spdy/hpack_huffman_table_test.cc @@ -86,6 +86,27 @@ class HpackHuffmanTablePeer { namespace { +class HpackHuffmanTableTest : public ::testing::Test { + protected: + HpackHuffmanTableTest() + : table_(), + peer_(table_) {} + + string EncodeString(StringPiece input) { + string result; + HpackOutputStream output_stream; + table_.EncodeString(input, &output_stream); + + output_stream.TakeString(&result); + // Verify EncodedSize() agrees with EncodeString(). + EXPECT_EQ(result.size(), table_.EncodedSize(input)); + return result; + } + + HpackHuffmanTable table_; + HpackHuffmanTablePeer peer_; +}; + MATCHER(DecodeEntryEq, "") { const DecodeEntry& lhs = std::tr1::get<0>(arg); const DecodeEntry& rhs = std::tr1::get<1>(arg); @@ -101,16 +122,14 @@ char bits8(const string& bitstring) { return static_cast<char>(std::bitset<8>(bitstring).to_ulong()); } -TEST(HpackHuffmanTableTest, InitializeHpackCode) { - HpackHuffmanTable table; +TEST_F(HpackHuffmanTableTest, InitializeHpackCode) { std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); - EXPECT_TRUE(table.Initialize(&code[0], code.size())); - EXPECT_TRUE(table.IsInitialized()); - EXPECT_EQ(HpackHuffmanTablePeer(table).pad_bits(), - bits8("11111111")); // First 8 bits of EOS. + EXPECT_TRUE(table_.Initialize(&code[0], code.size())); + EXPECT_TRUE(table_.IsInitialized()); + EXPECT_EQ(peer_.pad_bits(), bits8("11111111")); // First 8 bits of EOS. } -TEST(HpackHuffmanTableTest, InitializeEdgeCases) { +TEST_F(HpackHuffmanTableTest, InitializeEdgeCases) { { // Verify eight symbols can be encoded with 3 bits per symbol. HpackHuffmanSymbol code[] = { @@ -206,7 +225,7 @@ TEST(HpackHuffmanTableTest, InitializeEdgeCases) { } } -TEST(HpackHuffmanTableTest, ValidateInternalsWithSmallCode) { +TEST_F(HpackHuffmanTableTest, ValidateInternalsWithSmallCode) { HpackHuffmanSymbol code[] = { {bits32("01100000000000000000000000000000"), 4, 0}, // 3rd. {bits32("01110000000000000000000000000000"), 4, 1}, // 4th. @@ -216,11 +235,9 @@ TEST(HpackHuffmanTableTest, ValidateInternalsWithSmallCode) { {bits32("10001000000000000000000000000000"), 5, 5}, // 6th. {bits32("10011000000000000000000000000000"), 8, 6}, // 8th. {bits32("10010000000000000000000000000000"), 5, 7}}; // 7th. - HpackHuffmanTable table; - EXPECT_TRUE(table.Initialize(code, arraysize(code))); + EXPECT_TRUE(table_.Initialize(code, arraysize(code))); - HpackHuffmanTablePeer peer(table); - EXPECT_THAT(peer.code_by_id(), ElementsAre( + EXPECT_THAT(peer_.code_by_id(), ElementsAre( bits32("01100000000000000000000000000000"), bits32("01110000000000000000000000000000"), bits32("00000000000000000000000000000000"), @@ -229,10 +246,10 @@ TEST(HpackHuffmanTableTest, ValidateInternalsWithSmallCode) { bits32("10001000000000000000000000000000"), bits32("10011000000000000000000000000000"), bits32("10010000000000000000000000000000"))); - EXPECT_THAT(peer.length_by_id(), ElementsAre( + EXPECT_THAT(peer_.length_by_id(), ElementsAre( 4, 4, 2, 3, 5, 5, 8, 5)); - EXPECT_EQ(peer.decode_tables().size(), 1u); + EXPECT_EQ(1u, peer_.decode_tables().size()); { std::vector<DecodeEntry> expected; expected.resize(128, DecodeEntry(0, 2, 2)); // Fills 128. @@ -245,10 +262,10 @@ TEST(HpackHuffmanTableTest, ValidateInternalsWithSmallCode) { expected.resize(306, DecodeEntry(0, 8, 6)); // Fills 2. expected.resize(512, DecodeEntry()); // Remainder is empty. - EXPECT_THAT(peer.decode_entries(peer.decode_tables()[0]), + EXPECT_THAT(peer_.decode_entries(peer_.decode_tables()[0]), Pointwise(DecodeEntryEq(), expected)); } - EXPECT_EQ(peer.pad_bits(), bits8("10011000")); + EXPECT_EQ(bits8("10011000"), peer_.pad_bits()); char input_storage[] = {2, 3, 2, 7, 4}; StringPiece input(input_storage, arraysize(input_storage)); @@ -259,18 +276,16 @@ TEST(HpackHuffmanTableTest, ValidateInternalsWithSmallCode) { bits8("01001100")}; StringPiece expect(expect_storage, arraysize(expect_storage)); - string buffer_in, buffer_out; - HpackOutputStream output_stream(kuint32max); - table.EncodeString(input, &output_stream); - output_stream.TakeString(&buffer_in); - EXPECT_EQ(buffer_in, expect); + string buffer_in = EncodeString(input); + EXPECT_EQ(expect, buffer_in); + string buffer_out; HpackInputStream input_stream(kuint32max, buffer_in); - EXPECT_TRUE(table.DecodeString(&input_stream, input.size(), &buffer_out)); + EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out)); EXPECT_EQ(buffer_out, input); } -TEST(HpackHuffmanTableTest, ValidateMultiLevelDecodeTables) { +TEST_F(HpackHuffmanTableTest, ValidateMultiLevelDecodeTables) { HpackHuffmanSymbol code[] = { {bits32("00000000000000000000000000000000"), 6, 0}, {bits32("00000100000000000000000000000000"), 6, 1}, @@ -278,11 +293,9 @@ TEST(HpackHuffmanTableTest, ValidateMultiLevelDecodeTables) { {bits32("00001000001000000000000000000000"), 11, 3}, {bits32("00001000010000000000000000000000"), 12, 4}, }; - HpackHuffmanTable table; - EXPECT_TRUE(table.Initialize(code, arraysize(code))); + EXPECT_TRUE(table_.Initialize(code, arraysize(code))); - HpackHuffmanTablePeer peer(table); - EXPECT_EQ(peer.decode_tables().size(), 2u); + EXPECT_EQ(2u, peer_.decode_tables().size()); { std::vector<DecodeEntry> expected; expected.resize(8, DecodeEntry(0, 6, 0)); // Fills 8. @@ -290,10 +303,10 @@ TEST(HpackHuffmanTableTest, ValidateMultiLevelDecodeTables) { expected.resize(17, DecodeEntry(1, 12, 0)); // Pointer. Fills 1. expected.resize(512, DecodeEntry()); // Remainder is empty. - const DecodeTable& decode_table = peer.decode_tables()[0]; + const DecodeTable& decode_table = peer_.decode_tables()[0]; EXPECT_EQ(decode_table.prefix_length, 0); EXPECT_EQ(decode_table.indexed_length, 9); - EXPECT_THAT(peer.decode_entries(decode_table), + EXPECT_THAT(peer_.decode_entries(decode_table), Pointwise(DecodeEntryEq(), expected)); } { @@ -303,16 +316,16 @@ TEST(HpackHuffmanTableTest, ValidateMultiLevelDecodeTables) { expected.resize(5, DecodeEntry(1, 12, 4)); // Fills 1. expected.resize(8, DecodeEntry()); // Remainder is empty. - const DecodeTable& decode_table = peer.decode_tables()[1]; + const DecodeTable& decode_table = peer_.decode_tables()[1]; EXPECT_EQ(decode_table.prefix_length, 9); EXPECT_EQ(decode_table.indexed_length, 3); - EXPECT_THAT(peer.decode_entries(decode_table), + EXPECT_THAT(peer_.decode_entries(decode_table), Pointwise(DecodeEntryEq(), expected)); } - EXPECT_EQ(peer.pad_bits(), bits8("00001000")); + EXPECT_EQ(bits8("00001000"), peer_.pad_bits()); } -TEST(HpackHuffmanTableTest, DecodeWithBadInput) { +TEST_F(HpackHuffmanTableTest, DecodeWithBadInput) { HpackHuffmanSymbol code[] = { {bits32("01100000000000000000000000000000"), 4, 0}, {bits32("01110000000000000000000000000000"), 4, 1}, @@ -323,8 +336,7 @@ TEST(HpackHuffmanTableTest, DecodeWithBadInput) { {bits32("10011000000000000000000000000000"), 6, 6}, {bits32("10010000000000000000000000000000"), 5, 7}, {bits32("10011100000000000000000000000000"), 16, 8}}; - HpackHuffmanTable table; - EXPECT_TRUE(table.Initialize(code, arraysize(code))); + EXPECT_TRUE(table_.Initialize(code, arraysize(code))); string buffer; const size_t capacity = 4; @@ -334,7 +346,7 @@ TEST(HpackHuffmanTableTest, DecodeWithBadInput) { StringPiece input(input_storage, arraysize(input_storage)); HpackInputStream input_stream(kuint32max, input); - EXPECT_TRUE(table.DecodeString(&input_stream, capacity, &buffer)); + EXPECT_TRUE(table_.DecodeString(&input_stream, capacity, &buffer)); EXPECT_EQ(buffer, "\x02\x03\x02\x06"); } { @@ -344,16 +356,16 @@ TEST(HpackHuffmanTableTest, DecodeWithBadInput) { StringPiece input(input_storage, arraysize(input_storage)); HpackInputStream input_stream(kuint32max, input); - EXPECT_FALSE(table.DecodeString(&input_stream, capacity, &buffer)); + EXPECT_FALSE(table_.DecodeString(&input_stream, capacity, &buffer)); EXPECT_EQ(buffer, "\x02\x03\x02"); } { - // Repeat the shortest 00 code to overflow |buffer|. Expect to fail. + // Repeat the shortest 0b00 code to overflow |buffer|. Expect to fail. std::vector<char> input_storage(1 + capacity / 4, '\0'); StringPiece input(&input_storage[0], input_storage.size()); HpackInputStream input_stream(kuint32max, input); - EXPECT_FALSE(table.DecodeString(&input_stream, capacity, &buffer)); + EXPECT_FALSE(table_.DecodeString(&input_stream, capacity, &buffer)); std::vector<char> expected(capacity, '\x02'); EXPECT_THAT(buffer, ElementsAreArray(expected)); @@ -366,13 +378,14 @@ TEST(HpackHuffmanTableTest, DecodeWithBadInput) { StringPiece input(input_storage, arraysize(input_storage)); HpackInputStream input_stream(kuint32max, input); - EXPECT_FALSE(table.DecodeString(&input_stream, 4, &buffer)); + EXPECT_FALSE(table_.DecodeString(&input_stream, capacity, &buffer)); EXPECT_EQ(buffer, "\x06"); } } -TEST(HpackHuffmanTableTest, SpecRequestExamples) { - const HpackHuffmanTable& table(ObtainHpackHuffmanTable()); +TEST_F(HpackHuffmanTableTest, SpecRequestExamples) { + std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); + EXPECT_TRUE(table_.Initialize(&code[0], code.size())); string buffer; string test_table[] = { @@ -387,22 +400,21 @@ TEST(HpackHuffmanTableTest, SpecRequestExamples) { }; // Round-trip each test example. for (size_t i = 0; i != arraysize(test_table); i += 2) { - const string& encoded(test_table[i]); - const string& decoded(test_table[i+1]); - HpackInputStream input_stream(kuint32max, encoded); - HpackOutputStream output_stream(kuint32max); - - buffer.reserve(decoded.size()); - EXPECT_TRUE(table.DecodeString(&input_stream, decoded.size(), &buffer)); - EXPECT_EQ(decoded, buffer); - table.EncodeString(decoded, &output_stream); - output_stream.TakeString(&buffer); - EXPECT_EQ(encoded, buffer); + const string& encodedFixture(test_table[i]); + const string& decodedFixture(test_table[i+1]); + HpackInputStream input_stream(kuint32max, encodedFixture); + + EXPECT_TRUE(table_.DecodeString(&input_stream, decodedFixture.size(), + &buffer)); + EXPECT_EQ(decodedFixture, buffer); + buffer = EncodeString(decodedFixture); + EXPECT_EQ(encodedFixture, buffer); } } -TEST(HpackHuffmanTableTest, SpecResponseExamples) { - const HpackHuffmanTable& table(ObtainHpackHuffmanTable()); +TEST_F(HpackHuffmanTableTest, SpecResponseExamples) { + std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); + EXPECT_TRUE(table_.Initialize(&code[0], code.size())); string buffer; string test_table[] = { @@ -423,41 +435,40 @@ TEST(HpackHuffmanTableTest, SpecResponseExamples) { }; // Round-trip each test example. for (size_t i = 0; i != arraysize(test_table); i += 2) { - const string& encoded(test_table[i]); - const string& decoded(test_table[i+1]); - HpackInputStream input_stream(kuint32max, encoded); - HpackOutputStream output_stream(kuint32max); - - buffer.reserve(decoded.size()); - EXPECT_TRUE(table.DecodeString(&input_stream, decoded.size(), &buffer)); - EXPECT_EQ(decoded, buffer); - table.EncodeString(decoded, &output_stream); - output_stream.TakeString(&buffer); - EXPECT_EQ(encoded, buffer); + const string& encodedFixture(test_table[i]); + const string& decodedFixture(test_table[i+1]); + HpackInputStream input_stream(kuint32max, encodedFixture); + + EXPECT_TRUE(table_.DecodeString(&input_stream, decodedFixture.size(), + &buffer)); + EXPECT_EQ(decodedFixture, buffer); + buffer = EncodeString(decodedFixture); + EXPECT_EQ(encodedFixture, buffer); } } -TEST(HpackHuffmanTableTest, RoundTripIndvidualSymbols) { - const HpackHuffmanTable& table(ObtainHpackHuffmanTable()); +TEST_F(HpackHuffmanTableTest, RoundTripIndvidualSymbols) { + std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); + EXPECT_TRUE(table_.Initialize(&code[0], code.size())); for (size_t i = 0; i != 256; i++) { char c = static_cast<char>(i); char storage[3] = {c, c, c}; StringPiece input(storage, arraysize(storage)); - string buffer_in, buffer_out(input.size(), '\0'); - HpackOutputStream output_stream(kuint32max); - table.EncodeString(input, &output_stream); - output_stream.TakeString(&buffer_in); + string buffer_in = EncodeString(input); + string buffer_out; HpackInputStream input_stream(kuint32max, buffer_in); - EXPECT_TRUE(table.DecodeString(&input_stream, input.size(), &buffer_out)); + EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out)); EXPECT_EQ(input, buffer_out); } } -TEST(HpackHuffmanTableTest, RoundTripSymbolSequence) { - const HpackHuffmanTable& table(ObtainHpackHuffmanTable()); +TEST_F(HpackHuffmanTableTest, RoundTripSymbolSequence) { + std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); + EXPECT_TRUE(table_.Initialize(&code[0], code.size())); + char storage[512]; for (size_t i = 0; i != 256; i++) { @@ -466,16 +477,41 @@ TEST(HpackHuffmanTableTest, RoundTripSymbolSequence) { } StringPiece input(storage, arraysize(storage)); - string buffer_in, buffer_out(input.size(), '\0'); - HpackOutputStream output_stream(kuint32max); - table.EncodeString(input, &output_stream); - output_stream.TakeString(&buffer_in); + string buffer_in = EncodeString(input); + string buffer_out; HpackInputStream input_stream(kuint32max, buffer_in); - EXPECT_TRUE(table.DecodeString(&input_stream, input.size(), &buffer_out)); + EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out)); EXPECT_EQ(input, buffer_out); } +TEST_F(HpackHuffmanTableTest, EncodedSizeAgreesWithEncodeString) { + std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); + EXPECT_TRUE(table_.Initialize(&code[0], code.size())); + + string test_table[] = { + "", + "Mon, 21 Oct 2013 20:13:21 GMT", + "https://www.example.com", + "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", + string(1, '\0'), + string("foo\0bar", 7), + string(256, '\0'), + }; + for (size_t i = 0; i != 256; ++i) { + // Expand last |test_table| entry to cover all codes. + test_table[arraysize(test_table)-1][i] = static_cast<char>(i); + } + + HpackOutputStream output_stream; + string encoding; + for (size_t i = 0; i != arraysize(test_table); ++i) { + table_.EncodeString(test_table[i], &output_stream); + output_stream.TakeString(&encoding); + EXPECT_EQ(encoding.size(), table_.EncodedSize(test_table[i])); + } +} + } // namespace } // namespace test diff --git a/net/spdy/hpack_output_stream.cc b/net/spdy/hpack_output_stream.cc index 5290892..20f901d 100644 --- a/net/spdy/hpack_output_stream.cc +++ b/net/spdy/hpack_output_stream.cc @@ -6,43 +6,17 @@ #include "base/logging.h" -using base::StringPiece; namespace net { +using base::StringPiece; using std::string; -HpackOutputStream::HpackOutputStream(uint32 max_string_literal_size) - : max_string_literal_size_(max_string_literal_size), - bit_offset_(0) {} +HpackOutputStream::HpackOutputStream() + : bit_offset_(0) {} HpackOutputStream::~HpackOutputStream() {} -void HpackOutputStream::AppendIndexedHeader(uint32 index_or_zero) { - AppendPrefix(kIndexedOpcode); - AppendUint32(index_or_zero); -} - -bool HpackOutputStream::AppendLiteralHeaderNoIndexingWithName( - StringPiece name, StringPiece value) { - AppendPrefix(kLiteralNoIndexOpcode); - AppendBits(0x0, 8 - kLiteralNoIndexOpcode.bit_size); - if (!AppendStringLiteral(name)) - return false; - if (!AppendStringLiteral(value)) - return false; - return true; -} - -void HpackOutputStream::TakeString(string* output) { - // This must hold, since all public functions cause the buffer to - // end on a byte boundary. - DCHECK_EQ(bit_offset_, 0u); - buffer_.swap(*output); - buffer_.clear(); - bit_offset_ = 0; -} - void HpackOutputStream::AppendBits(uint8 bits, size_t bit_size) { DCHECK_GT(bit_size, 0u); DCHECK_LE(bit_size, 8u); @@ -69,6 +43,11 @@ void HpackOutputStream::AppendPrefix(HpackPrefix prefix) { AppendBits(prefix.bits, prefix.bit_size); } +void HpackOutputStream::AppendBytes(StringPiece buffer) { + DCHECK_EQ(bit_offset_, 0u); + buffer_.append(buffer.data(), buffer.size()); +} + void HpackOutputStream::AppendUint32(uint32 I) { // The algorithm below is adapted from the pseudocode in 4.1.1. size_t N = 8 - bit_offset_; @@ -86,15 +65,13 @@ void HpackOutputStream::AppendUint32(uint32 I) { } } -bool HpackOutputStream::AppendStringLiteral(base::StringPiece str) { +void HpackOutputStream::TakeString(string* output) { + // This must hold, since all public functions cause the buffer to + // end on a byte boundary. DCHECK_EQ(bit_offset_, 0u); - // TODO(akalin): Implement Huffman encoding. - AppendPrefix(kStringLiteralIdentityEncoded); - if (str.size() > max_string_literal_size_) - return false; - AppendUint32(static_cast<uint32>(str.size())); - buffer_.append(str.data(), str.size()); - return true; + buffer_.swap(*output); + buffer_.clear(); + bit_offset_ = 0; } } // namespace net diff --git a/net/spdy/hpack_output_stream.h b/net/spdy/hpack_output_stream.h index a88e522..7a0313b 100644 --- a/net/spdy/hpack_output_stream.h +++ b/net/spdy/hpack_output_stream.h @@ -12,8 +12,7 @@ #include "base/macros.h" #include "base/strings/string_piece.h" #include "net/base/net_export.h" -#include "net/spdy/hpack_constants.h" // For HpackPrefix. -#include "net/spdy/hpack_encoding_context.h" +#include "net/spdy/hpack_constants.h" // All section references below are to // http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-06 @@ -24,48 +23,21 @@ namespace net { // header fields. class NET_EXPORT_PRIVATE HpackOutputStream { public: - // |max_string_literal_size| is the largest that any one string - // |literal (header name or header value) can be. - explicit HpackOutputStream(uint32 max_string_literal_size); + explicit HpackOutputStream(); ~HpackOutputStream(); - // Corresponds to 4.2. - void AppendIndexedHeader(uint32 index_or_zero); - - // Corresponds to 4.3.1 (second form). Returns whether or not the - // append was successful; if the append was unsuccessful, no other - // member function may be called. - bool AppendLiteralHeaderNoIndexingWithName(base::StringPiece name, - base::StringPiece value); - - // Moves the internal buffer to the given string and clears all - // internal state. - void TakeString(std::string* output); - // Appends the lower |bit_size| bits of |bits| to the internal buffer. // // |bit_size| must be > 0 and <= 8. |bits| must not have any bits // set other than the lower |bit_size| bits. void AppendBits(uint8 bits, size_t bit_size); - // Accessors for testing. - - void AppendBitsForTest(uint8 bits, size_t size) { - AppendBits(bits, size); - } - - void AppendUint32ForTest(uint32 I) { - AppendUint32(I); - } - - bool AppendStringLiteralForTest(base::StringPiece str) { - return AppendStringLiteral(str); - } - - private: // Simply forwards to AppendBits(prefix.bits, prefix.bit-size). void AppendPrefix(HpackPrefix prefix); + // Directly appends |buffer|. + void AppendBytes(base::StringPiece buffer); + // Appends the given integer using the representation described in // 4.1.1. If the internal buffer ends on a byte boundary, the prefix // length N is taken to be 8; otherwise, it is taken to be the @@ -75,16 +47,10 @@ class NET_EXPORT_PRIVATE HpackOutputStream { // boundary after this function is called. void AppendUint32(uint32 I); - // Appends the given string using the representation described in - // 4.1.2. The internal buffer must end on a byte boundary, and it is - // guaranteed that the internal buffer will end on a byte boundary - // after this function is called. Returns whether or not the append - // was successful; if the append was unsuccessful, no other member - // function may be called. - bool AppendStringLiteral(base::StringPiece str); - - const uint32 max_string_literal_size_; + // Swaps the interal buffer with |output|. + void TakeString(std::string* output); + private: // The internal bit buffer. std::string buffer_; diff --git a/net/spdy/hpack_output_stream_test.cc b/net/spdy/hpack_output_stream_test.cc index 0321e3d..f8e0780 100644 --- a/net/spdy/hpack_output_stream_test.cc +++ b/net/spdy/hpack_output_stream_test.cc @@ -18,27 +18,27 @@ using std::string; // Make sure that AppendBits() appends bits starting from the most // significant bit, and that it can handle crossing a byte boundary. TEST(HpackOutputStreamTest, AppendBits) { - HpackOutputStream output_stream(kuint32max); + HpackOutputStream output_stream; string expected_str; - output_stream.AppendBitsForTest(0x1, 1); + output_stream.AppendBits(0x1, 1); expected_str.append(1, 0x00); *expected_str.rbegin() |= (0x1 << 7); - output_stream.AppendBitsForTest(0x0, 1); + output_stream.AppendBits(0x0, 1); - output_stream.AppendBitsForTest(0x3, 2); + output_stream.AppendBits(0x3, 2); *expected_str.rbegin() |= (0x3 << 4); - output_stream.AppendBitsForTest(0x0, 2); + output_stream.AppendBits(0x0, 2); // Byte-crossing append. - output_stream.AppendBitsForTest(0x7, 3); + output_stream.AppendBits(0x7, 3); *expected_str.rbegin() |= (0x7 >> 1); expected_str.append(1, 0x00); *expected_str.rbegin() |= (0x7 << 7); - output_stream.AppendBitsForTest(0x0, 7); + output_stream.AppendBits(0x0, 7); string str; output_stream.TakeString(&str); @@ -48,11 +48,11 @@ TEST(HpackOutputStreamTest, AppendBits) { // Utility function to return I as a string encoded with an N-bit // prefix. string EncodeUint32(uint8 N, uint32 I) { - HpackOutputStream output_stream(kuint32max); + HpackOutputStream output_stream; if (N < 8) { - output_stream.AppendBitsForTest(0x00, 8 - N); + output_stream.AppendBits(0x00, 8 - N); } - output_stream.AppendUint32ForTest(I); + output_stream.AppendUint32(I); string str; output_stream.TakeString(&str); return str; @@ -236,71 +236,23 @@ TEST(HpackOutputStreamTest, SixByteIntegersOneToSevenBitPrefixes) { // Test that encoding an integer with an N-bit prefix preserves the // upper (8-N) bits of the first byte. TEST(HpackOutputStreamTest, AppendUint32PreservesUpperBits) { - HpackOutputStream output_stream(kuint32max); - output_stream.AppendBitsForTest(0x7f, 7); - output_stream.AppendUint32ForTest(0x01); + HpackOutputStream output_stream; + output_stream.AppendBits(0x7f, 7); + output_stream.AppendUint32(0x01); string str; output_stream.TakeString(&str); EXPECT_EQ(string("\xff\x00", 2), str); } -// Test that encoding a string literal without huffman encoding -// encodes the size first with a 7-bit prefix and then the bytes of -// the string. -TEST(HpackOutputStreamTest, AppendStringLiteralNoHuffmanEncoding) { - HpackOutputStream output_stream(kuint32max); +TEST(HpackOutputStreamTest, AppendBytes) { + HpackOutputStream output_stream; - string literal(0x7f, 'x'); - EXPECT_TRUE(output_stream.AppendStringLiteralForTest(literal)); + output_stream.AppendBytes("buffer1"); + output_stream.AppendBytes("buffer2"); string str; output_stream.TakeString(&str); - EXPECT_EQ(string("\x7f\x00", 2) + literal, str); -} - -// Test that trying to encode a too-long string literal will fail. -TEST(HpackOutputStreamTest, AppendStringLiteralTooLong) { - HpackOutputStream output_stream(kuint32max - 1); - - EXPECT_FALSE(output_stream.AppendStringLiteralForTest( - base::StringPiece(NULL, kuint32max))); -} - -// Test that encoding an indexed header simply encodes the index. -TEST(HpackOutputStreamTest, AppendIndexedHeader) { - HpackOutputStream output_stream(kuint32max); - output_stream.AppendIndexedHeader(0xffffffff); - - string str; - output_stream.TakeString(&str); - EXPECT_EQ("\xff\x80\xff\xff\xff\x0f", str); -} - -// Test that encoding a literal header without indexing with a name -// encodes both the name and value as string literals. -TEST(HpackOutputStreamTest, AppendLiteralHeaderNoIndexingWithName) { - HpackOutputStream output_stream(kuint32max); - EXPECT_TRUE( - output_stream.AppendLiteralHeaderNoIndexingWithName("name", "value")); - - string str; - output_stream.TakeString(&str); - EXPECT_EQ("\x40\x04name\x05value", str); -} - -// Test that trying to encode a header with a too-long header name or -// value will fail. -TEST(HpackOutputStreamTest, AppendLiteralHeaderNoIndexingWithNameTooLong) { - { - HpackOutputStream output_stream(10); - EXPECT_FALSE(output_stream.AppendLiteralHeaderNoIndexingWithName( - "name", "too-long value")); - } - { - HpackOutputStream output_stream(10); - EXPECT_FALSE(output_stream.AppendLiteralHeaderNoIndexingWithName( - "too-long name", "value")); - } + EXPECT_EQ("buffer1buffer2", str); } } // namespace diff --git a/net/spdy/hpack_round_trip_test.cc b/net/spdy/hpack_round_trip_test.cc new file mode 100644 index 0000000..39be939 --- /dev/null +++ b/net/spdy/hpack_round_trip_test.cc @@ -0,0 +1,174 @@ +// Copyright 2014 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include <cmath> +#include <ctime> +#include <map> +#include <string> +#include <vector> + +#include "base/rand_util.h" +#include "net/spdy/hpack_constants.h" +#include "net/spdy/hpack_decoder.h" +#include "net/spdy/hpack_encoder.h" +#include "testing/gtest/include/gtest/gtest.h" + +namespace net { + +using std::map; +using std::string; +using std::vector; + +namespace { + +class HpackRoundTripTest : public ::testing::Test { + protected: + HpackRoundTripTest() + : encoder_(ObtainHpackHuffmanTable()), + decoder_(ObtainHpackHuffmanTable()) {} + + virtual void SetUp() { + // Use a small table size to tickle eviction handling. + encoder_.ApplyHeaderTableSizeSetting(256); + decoder_.ApplyHeaderTableSizeSetting(256); + } + + bool RoundTrip(const map<string, string>& header_set) { + string encoded; + encoder_.EncodeHeaderSet(header_set, &encoded); + + bool success = decoder_.HandleControlFrameHeadersData( + 1, encoded.data(), encoded.size()); + success &= decoder_.HandleControlFrameHeadersComplete(1); + + EXPECT_EQ(header_set, decoder_.decoded_block()); + return success; + } + + size_t SampleExponential(size_t mean, size_t sanity_bound) { + return std::min<size_t>(-std::log(base::RandDouble()) * mean, + sanity_bound); + } + + HpackEncoder encoder_; + HpackDecoder decoder_; +}; + +TEST_F(HpackRoundTripTest, ResponseFixtures) { + { + map<string, string> headers; + headers[":status"] = "302"; + headers["cache-control"] = "private"; + headers["date"] = "Mon, 21 Oct 2013 20:13:21 GMT"; + headers["location"] = "https://www.example.com"; + EXPECT_TRUE(RoundTrip(headers)); + } + { + map<string, string> headers; + headers[":status"] = "200"; + headers["cache-control"] = "private"; + headers["date"] = "Mon, 21 Oct 2013 20:13:21 GMT"; + headers["location"] = "https://www.example.com"; + EXPECT_TRUE(RoundTrip(headers)); + } + { + map<string, string> headers; + headers[":status"] = "200"; + headers["cache-control"] = "private"; + headers["content-encoding"] = "gzip"; + headers["date"] = "Mon, 21 Oct 2013 20:13:22 GMT"; + headers["location"] = "https://www.example.com"; + headers["set-cookie"] = "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU;" + " max-age=3600; version=1"; + EXPECT_TRUE(RoundTrip(headers)); + } +} + +TEST_F(HpackRoundTripTest, RequestFixtures) { + { + map<string, string> headers; + headers[":authority"] = "www.example.com"; + headers[":method"] = "GET"; + headers[":path"] = "/"; + headers[":scheme"] = "http"; + headers["cookie"] = "baz=bing; foo=bar"; + EXPECT_TRUE(RoundTrip(headers)); + } + { + map<string, string> headers; + headers[":authority"] = "www.example.com"; + headers[":method"] = "GET"; + headers[":path"] = "/"; + headers[":scheme"] = "http"; + headers["cache-control"] = "no-cache"; + headers["cookie"] = "fizzle=fazzle; foo=bar"; + EXPECT_TRUE(RoundTrip(headers)); + } + { + map<string, string> headers; + headers[":authority"] = "www.example.com"; + headers[":method"] = "GET"; + headers[":path"] = "/index.html"; + headers[":scheme"] = "https"; + headers["custom-key"] = "custom-value"; + headers["cookie"] = "baz=bing; fizzle=fazzle; garbage"; + EXPECT_TRUE(RoundTrip(headers)); + } +} + +TEST_F(HpackRoundTripTest, RandomizedExamples) { + // Grow vectors of names & values, which are seeded with fixtures and then + // expanded with dynamically generated data. Samples are taken using the + // exponential distribution. + vector<string> names; + names.push_back(":authority"); + names.push_back(":path"); + names.push_back(":status"); + // TODO(jgraettinger): Enable "cookie" as a name fixture. Crumbs may be + // reconstructed in any order, which breaks the simple validation used here. + + vector<string> values; + values.push_back("/"); + values.push_back("/index.html"); + values.push_back("200"); + values.push_back("404"); + values.push_back(""); + values.push_back("baz=bing; foo=bar; garbage"); + values.push_back("baz=bing; fizzle=fazzle; garbage"); + + int seed = std::time(NULL); + LOG(INFO) << "Seeding with srand(" << seed << ")"; + srand(seed); + + for (size_t i = 0; i != 2000; ++i) { + map<string, string> headers; + + size_t header_count = 1 + SampleExponential(7, 50); + for (size_t j = 0; j != header_count; ++j) { + size_t name_index = SampleExponential(20, 200); + size_t value_index = SampleExponential(20, 200); + + string name, value; + if (name_index >= names.size()) { + names.push_back(base::RandBytesAsString(1 + SampleExponential(5, 30))); + name = names.back(); + } else { + name = names[name_index]; + } + if (value_index >= values.size()) { + values.push_back(base::RandBytesAsString( + 1 + SampleExponential(15, 75))); + value = values.back(); + } else { + value = values[value_index]; + } + headers[name] = value; + } + EXPECT_TRUE(RoundTrip(headers)); + } +} + +} // namespace + +} // namespace net diff --git a/net/spdy/spdy_frame_builder.cc b/net/spdy/spdy_frame_builder.cc index 5b08412..a7eb91d 100644 --- a/net/spdy/spdy_frame_builder.cc +++ b/net/spdy/spdy_frame_builder.cc @@ -32,10 +32,12 @@ FlagsAndLength CreateFlagsAndLength(uint8 flags, size_t length) { } // namespace -SpdyFrameBuilder::SpdyFrameBuilder(size_t size) + SpdyFrameBuilder::SpdyFrameBuilder(size_t size, SpdyMajorVersion version) : buffer_(new char[size]), capacity_(size), - length_(0) { + length_(0), + offset_(0), + version_(version) { } SpdyFrameBuilder::~SpdyFrameBuilder() { @@ -45,7 +47,7 @@ char* SpdyFrameBuilder::GetWritableBuffer(size_t length) { if (!CanWrite(length)) { return NULL; } - return buffer_.get() + length_; + return buffer_.get() + offset_ + length_; } bool SpdyFrameBuilder::Seek(size_t length) { @@ -60,13 +62,14 @@ bool SpdyFrameBuilder::Seek(size_t length) { bool SpdyFrameBuilder::WriteControlFrameHeader(const SpdyFramer& framer, SpdyFrameType type, uint8 flags) { - DCHECK_GT(4, framer.protocol_version()); + DCHECK_GE(SPDY3, version_); DCHECK_NE(-1, - SpdyConstants::SerializeFrameType(framer.protocol_version(), type)); + SpdyConstants::SerializeFrameType(version_, type)); bool success = true; FlagsAndLength flags_length = CreateFlagsAndLength( flags, capacity_ - framer.GetControlFrameHeaderSize()); - success &= WriteUInt16(kControlFlagMask | framer.protocol_version()); + success &= WriteUInt16(kControlFlagMask | + SpdyConstants::SerializeMajorVersion(version_)); success &= WriteUInt16( SpdyConstants::SerializeFrameType(framer.protocol_version(), type)); success &= WriteBytes(&flags_length, sizeof(flags_length)); @@ -77,8 +80,8 @@ bool SpdyFrameBuilder::WriteControlFrameHeader(const SpdyFramer& framer, bool SpdyFrameBuilder::WriteDataFrameHeader(const SpdyFramer& framer, SpdyStreamId stream_id, uint8 flags) { - if (framer.protocol_version() >= 4) { - return WriteFramePrefix(framer, DATA, flags, stream_id); + if (version_ > SPDY3) { + return BeginNewFrame(framer, DATA, flags, stream_id); } DCHECK_EQ(0u, stream_id & ~kStreamIdMask); bool success = true; @@ -94,28 +97,36 @@ bool SpdyFrameBuilder::WriteDataFrameHeader(const SpdyFramer& framer, return success; } -bool SpdyFrameBuilder::WriteFramePrefix(const SpdyFramer& framer, - SpdyFrameType type, - uint8 flags, - SpdyStreamId stream_id) { - DCHECK_NE(-1, - SpdyConstants::SerializeFrameType(framer.protocol_version(), type)); +bool SpdyFrameBuilder::BeginNewFrame(const SpdyFramer& framer, + SpdyFrameType type, + uint8 flags, + SpdyStreamId stream_id) { + DCHECK(SpdyConstants::IsValidFrameType(version_, + SpdyConstants::SerializeFrameType(version_, type))); DCHECK_EQ(0u, stream_id & ~kStreamIdMask); - DCHECK_LE(4, framer.protocol_version()); + DCHECK_LT(SPDY3, framer.protocol_version()); bool success = true; - // Upstream DCHECK's that capacity_ is under the maximum frame size at this - // point. Chromium does not, because of the large additional zlib inflation - // factor we use. (Frame size is is still checked by OverwriteLength() below). - if (type != DATA) { - success &= WriteUInt16(capacity_ - framer.GetControlFrameHeaderSize()); - } else { - success &= WriteUInt16(capacity_ - framer.GetDataFrameMinimumSize()); + if (length_ > 0) { + // Update length field for previous frame. + OverwriteLength(framer, length_ - framer.GetPrefixLength(type)); + DLOG_IF(DFATAL, SpdyConstants::GetFrameMaximumSize(version_) < length_) + << "Frame length " << length_ + << " is longer than the maximum allowed length."; } + + offset_ += length_; + length_ = 0; + + // Assume all remaining capacity will be used for this frame. If not, + // the length will get overwritten when we begin the next frame. + // Don't check for length limits here because this may be larger than the + // actual frame length. + success &= WriteUInt16(capacity_ - offset_ - framer.GetPrefixLength(type)); success &= WriteUInt8( - SpdyConstants::SerializeFrameType(framer.protocol_version(), type)); + SpdyConstants::SerializeFrameType(version_, type)); success &= WriteUInt8(flags); success &= WriteUInt32(stream_id); - DCHECK_EQ(framer.GetDataFrameMinimumSize(), length()); + DCHECK_EQ(framer.GetDataFrameMinimumSize(), length_); return success; } @@ -157,16 +168,17 @@ bool SpdyFrameBuilder::RewriteLength(const SpdyFramer& framer) { bool SpdyFrameBuilder::OverwriteLength(const SpdyFramer& framer, size_t length) { - if (framer.protocol_version() < 4) { - DCHECK_GT(framer.GetFrameMaximumSize() - framer.GetFrameMinimumSize(), + if (version_ <= SPDY3) { + DCHECK_GE(SpdyConstants::GetFrameMaximumSize(version_) - + framer.GetFrameMinimumSize(), length); } else { - DCHECK_GE(framer.GetFrameMaximumSize(), length); + DCHECK_GE(SpdyConstants::GetFrameMaximumSize(version_), length); } bool success = false; const size_t old_length = length_; - if (framer.protocol_version() < 4) { + if (version_ <= SPDY3) { FlagsAndLength flags_length = CreateFlagsAndLength( 0, // We're not writing over the flags value anyway. length); @@ -186,7 +198,7 @@ bool SpdyFrameBuilder::OverwriteLength(const SpdyFramer& framer, bool SpdyFrameBuilder::OverwriteFlags(const SpdyFramer& framer, uint8 flags) { - DCHECK_LE(SPDY4, framer.protocol_version()); + DCHECK_LT(SPDY3, framer.protocol_version()); bool success = false; const size_t old_length = length_; // Flags are the fourth octet in the frame prefix. @@ -202,7 +214,7 @@ bool SpdyFrameBuilder::CanWrite(size_t length) const { return false; } - if (length_ + length > capacity_) { + if (offset_ + length_ + length > capacity_) { DCHECK(false); return false; } diff --git a/net/spdy/spdy_frame_builder.h b/net/spdy/spdy_frame_builder.h index f9826d0..b4089ba 100644 --- a/net/spdy/spdy_frame_builder.h +++ b/net/spdy/spdy_frame_builder.h @@ -28,12 +28,13 @@ class SpdyFramer; class NET_EXPORT_PRIVATE SpdyFrameBuilder { public: // Initializes a SpdyFrameBuilder with a buffer of given size - explicit SpdyFrameBuilder(size_t size); + SpdyFrameBuilder(size_t size, SpdyMajorVersion version); ~SpdyFrameBuilder(); - // Returns the size of the SpdyFrameBuilder's data. - size_t length() const { return length_; } + // Returns the total size of the SpdyFrameBuilder's data, which may include + // multiple frames. + size_t length() const { return offset_ + length_; } // Returns a writeable buffer of given size in bytes, to be appended to the // currently written frame. Does bounds checking on length but does not @@ -65,16 +66,22 @@ class NET_EXPORT_PRIVATE SpdyFrameBuilder { // version-specific information from the |framer| and length information from // capacity_. The given type must be a control frame type. // Used only for SPDY versions >=4. - bool WriteFramePrefix(const SpdyFramer& framer, - SpdyFrameType type, - uint8 flags, - SpdyStreamId stream_id); + bool BeginNewFrame(const SpdyFramer& framer, + SpdyFrameType type, + uint8 flags, + SpdyStreamId stream_id); // Takes the buffer from the SpdyFrameBuilder. SpdyFrame* take() { - SpdyFrame* rv = new SpdyFrame(buffer_.release(), length_, true); + if (version_ > SPDY3) { + DLOG_IF(DFATAL, SpdyConstants::GetFrameMaximumSize(version_) < length_) + << "Frame length " << length_ + << " is longer than the maximum allowed length."; + } + SpdyFrame* rv = new SpdyFrame(buffer_.release(), length(), true); capacity_ = 0; length_ = 0; + offset_ = 0; return rv; } @@ -129,7 +136,10 @@ class NET_EXPORT_PRIVATE SpdyFrameBuilder { scoped_ptr<char[]> buffer_; size_t capacity_; // Allocation size of payload, set by constructor. - size_t length_; // Current length of the buffer. + size_t length_; // Length of the latest frame in the buffer. + size_t offset_; // Position at which the latest frame begins. + + const SpdyMajorVersion version_; }; } // namespace net diff --git a/net/spdy/spdy_frame_builder_test.cc b/net/spdy/spdy_frame_builder_test.cc index ed565b0..66b97d5 100644 --- a/net/spdy/spdy_frame_builder_test.cc +++ b/net/spdy/spdy_frame_builder_test.cc @@ -10,19 +10,6 @@ namespace net { -TEST(SpdyFrameBuilderTestVersionAgnostic, GetWritableBuffer) { - const size_t builder_size = 10; - SpdyFrameBuilder builder(builder_size); - char* writable_buffer = builder.GetWritableBuffer(builder_size); - memset(writable_buffer, ~1, builder_size); - EXPECT_TRUE(builder.Seek(builder_size)); - scoped_ptr<SpdyFrame> frame(builder.take()); - char expected[builder_size]; - memset(expected, ~1, builder_size); - EXPECT_EQ(base::StringPiece(expected, builder_size), - base::StringPiece(frame->data(), builder_size)); -} - class SpdyFrameBuilderTest : public ::testing::TestWithParam<SpdyMajorVersion> { protected: virtual void SetUp() { @@ -38,6 +25,19 @@ INSTANTIATE_TEST_CASE_P(SpdyFrameBuilderTests, SpdyFrameBuilderTest, ::testing::Values(SPDY2, SPDY3, SPDY4)); +TEST_P(SpdyFrameBuilderTest, GetWritableBuffer) { + const size_t builder_size = 10; + SpdyFrameBuilder builder(builder_size, spdy_version_); + char* writable_buffer = builder.GetWritableBuffer(builder_size); + memset(writable_buffer, ~1, builder_size); + EXPECT_TRUE(builder.Seek(builder_size)); + scoped_ptr<SpdyFrame> frame(builder.take()); + char expected[builder_size]; + memset(expected, ~1, builder_size); + EXPECT_EQ(base::StringPiece(expected, builder_size), + base::StringPiece(frame->data(), builder_size)); +} + TEST_P(SpdyFrameBuilderTest, RewriteLength) { // Create an empty SETTINGS frame both via framer and manually via builder. // The one created via builder is initially given the incorrect length, but @@ -45,12 +45,12 @@ TEST_P(SpdyFrameBuilderTest, RewriteLength) { SpdyFramer framer(spdy_version_); SpdySettingsIR settings_ir; scoped_ptr<SpdyFrame> expected(framer.SerializeSettings(settings_ir)); - SpdyFrameBuilder builder(expected->size() + 1); - if (spdy_version_ < 4) { + SpdyFrameBuilder builder(expected->size() + 1, spdy_version_); + if (spdy_version_ <= SPDY3) { builder.WriteControlFrameHeader(framer, SETTINGS, 0); builder.WriteUInt32(0); // Write the number of settings. } else { - builder.WriteFramePrefix(framer, SETTINGS, 0, 0); + builder.BeginNewFrame(framer, SETTINGS, 0, 0); } EXPECT_TRUE(builder.GetWritableBuffer(1) != NULL); builder.RewriteLength(framer); @@ -63,14 +63,14 @@ TEST_P(SpdyFrameBuilderTest, OverwriteFlags) { // Create a HEADERS frame both via framer and manually via builder with // different flags set, then make them match using OverwriteFlags(). SpdyFramer framer(spdy_version_); - if (spdy_version_ < SPDY4) { + if (spdy_version_ <= SPDY3) { return; } SpdyHeadersIR headers_ir(1); headers_ir.set_end_headers(false); scoped_ptr<SpdyFrame> expected(framer.SerializeHeaders(headers_ir)); - SpdyFrameBuilder builder(expected->size()); - builder.WriteFramePrefix(framer, HEADERS, HEADERS_FLAG_END_HEADERS, 1); + SpdyFrameBuilder builder(expected->size(), spdy_version_); + builder.BeginNewFrame(framer, HEADERS, HEADERS_FLAG_END_HEADERS, 1); builder.OverwriteFlags(framer, 0); scoped_ptr<SpdyFrame> built(builder.take()); EXPECT_EQ(base::StringPiece(expected->data(), expected->size()), diff --git a/net/spdy/spdy_framer.cc b/net/spdy/spdy_framer.cc index 23080ac..a20d1ea 100644 --- a/net/spdy/spdy_framer.cc +++ b/net/spdy/spdy_framer.cc @@ -2,10 +2,6 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. -// TODO(rtenhove) clean up frame buffer size calculations so that we aren't -// constantly adding and subtracting header sizes; this is ugly and error- -// prone. - #include "net/spdy/spdy_framer.h" #include "base/lazy_instance.h" @@ -80,9 +76,9 @@ const size_t SpdyFramer::kControlFrameBufferSize = 18; } while (false) #endif -SettingsFlagsAndId SettingsFlagsAndId::FromWireFormat(int version, - uint32 wire) { - if (version < 3) { +SettingsFlagsAndId SettingsFlagsAndId::FromWireFormat( + SpdyMajorVersion version, uint32 wire) { + if (version < SPDY3) { ConvertFlagsAndIdForSpdy2(&wire); } return SettingsFlagsAndId(ntohl(wire) >> 24, ntohl(wire) & 0x00ffffff); @@ -93,9 +89,10 @@ SettingsFlagsAndId::SettingsFlagsAndId(uint8 flags, uint32 id) LOG_IF(DFATAL, id > (1u << 24)) << "SPDY setting ID too large: " << id; } -uint32 SettingsFlagsAndId::GetWireFormat(int version) const { +uint32 SettingsFlagsAndId::GetWireFormat(SpdyMajorVersion version) + const { uint32 wire = htonl(id_ & 0x00ffffff) | htonl(flags_ << 24); - if (version < 3) { + if (version < SPDY3) { ConvertFlagsAndIdForSpdy2(&wire); } return wire; @@ -126,6 +123,7 @@ bool SpdyFramerVisitorInterface::OnRstStreamFrameData( SpdyFramer::SpdyFramer(SpdyMajorVersion version) : current_frame_buffer_(new char[kControlFrameBufferSize]), enable_compression_(true), + hpack_encoder_(ObtainHpackHuffmanTable()), hpack_decoder_(ObtainHpackHuffmanTable()), visitor_(NULL), debug_visitor_(NULL), @@ -166,22 +164,12 @@ void SpdyFramer::Reset() { } size_t SpdyFramer::GetDataFrameMinimumSize() const { - // Size, in bytes, of the data frame header. Future versions of SPDY - // will likely vary this, so we allow for the flexibility of a function call - // for this value as opposed to a constant. - return 8; + return SpdyConstants::GetDataFrameMinimumSize(); } // Size, in bytes, of the control frame header. size_t SpdyFramer::GetControlFrameHeaderSize() const { - switch (protocol_version()) { - case SPDY2: - case SPDY3: - case SPDY4: - return 8; - } - LOG(DFATAL) << "Unhandled SPDY version."; - return 0; + return SpdyConstants::GetControlFrameHeaderSize(protocol_version()); } size_t SpdyFramer::GetSynStreamMinimumSize() const { @@ -263,7 +251,7 @@ size_t SpdyFramer::GetGoAwayMinimumSize() const { size += 4; // 3. SPDY 3+ GOAWAY frames also contain a status (4 bytes) - if (protocol_version() >= 3) { + if (protocol_version() >= SPDY3) { size += 4; } @@ -302,14 +290,14 @@ size_t SpdyFramer::GetWindowUpdateSize() const { } size_t SpdyFramer::GetBlockedSize() const { - DCHECK_LE(4, protocol_version()); + DCHECK_LT(SPDY3, protocol_version()); // Size, in bytes, of a BLOCKED frame. // The BLOCKED frame has no payload beyond the control frame header. return GetControlFrameHeaderSize(); } size_t SpdyFramer::GetPushPromiseMinimumSize() const { - DCHECK_LE(4, protocol_version()); + DCHECK_LT(SPDY3, protocol_version()); // Size, in bytes, of a PUSH_PROMISE frame, sans the embedded header block. // Calculated as frame prefix + 4 (promised stream id). return GetControlFrameHeaderSize() + 4; @@ -326,19 +314,17 @@ size_t SpdyFramer::GetFrameMinimumSize() const { } size_t SpdyFramer::GetFrameMaximumSize() const { - if (protocol_version() <= SPDY3) { - // 24-bit length field plus eight-byte frame header. - return ((1<<24) - 1) + 8; - } else { - // 14-bit length field. - return (1<<14) - 1; - } + return SpdyConstants::GetFrameMaximumSize(protocol_version()); } size_t SpdyFramer::GetDataFrameMaximumPayload() const { return GetFrameMaximumSize() - GetDataFrameMinimumSize(); } +size_t SpdyFramer::GetPrefixLength(SpdyFrameType type) const { + return SpdyConstants::GetPrefixLength(type, protocol_version()); +} + const char* SpdyFramer::StateToString(int state) { switch (state) { case SPDY_ERROR: @@ -438,6 +424,10 @@ const char* SpdyFramer::StatusCodeToString(int status_code) { return "INVALID_CREDENTIALS"; case RST_STREAM_FRAME_TOO_LARGE: return "FRAME_TOO_LARGE"; + case RST_STREAM_CONNECT_ERROR: + return "CONNECT_ERROR"; + case RST_STREAM_ENHANCE_YOUR_CALM: + return "ENHANCE_YOUR_CALM"; } return "UNKNOWN_STATUS"; } @@ -572,15 +562,20 @@ size_t SpdyFramer::ProcessInput(const char* data, size_t len) { break; } - case SPDY_IGNORE_REMAINING_PAYLOAD: - // control frame has too-large payload - // intentional fallthrough + case SPDY_IGNORE_REMAINING_PAYLOAD: { + size_t bytes_read = ProcessIgnoredControlFramePayload(/*data,*/ len); + len -= bytes_read; + data += bytes_read; + break; + } + case SPDY_FORWARD_STREAM_FRAME: { size_t bytes_read = ProcessDataFramePayload(data, len); len -= bytes_read; data += bytes_read; break; } + default: LOG(DFATAL) << "Invalid value for " << display_protocol_ << " framer state: " << state_; @@ -639,8 +634,22 @@ size_t SpdyFramer::ProcessCommonHeader(const char* data, size_t len) { DCHECK(successful_read); is_control_frame = (version & kControlFlagMask) != 0; version &= ~kControlFlagMask; // Only valid for control frames. - if (is_control_frame) { + // We check version before we check validity: version can never be + // 'invalid', it can only be unsupported. + if (version < SpdyConstants::SerializeMajorVersion(SPDY_MIN_VERSION) || + version > SpdyConstants::SerializeMajorVersion(SPDY_MAX_VERSION) || + SpdyConstants::ParseMajorVersion(version) != protocol_version()) { + // Version does not match the version the framer was initialized with. + DVLOG(1) << "Unsupported SPDY version " + << version + << " (expected " << protocol_version() << ")"; + set_error(SPDY_UNSUPPORTED_VERSION); + return 0; + } else { + // Convert version from wire format to SpdyMajorVersion. + version = SpdyConstants::ParseMajorVersion(version); + } // We check control_frame_type_field's validity in // ProcessControlFrameHeader(). successful_read = reader->ReadUInt16(&control_frame_type_field); @@ -756,12 +765,6 @@ size_t SpdyFramer::ProcessCommonHeader(const char* data, size_t len) { CHANGE_STATE(SPDY_AUTO_RESET); } } - } else if (version != protocol_version()) { - // We check version before we check validity: version can never be - // 'invalid', it can only be unsupported. - DVLOG(1) << "Unsupported SPDY version " << version - << " (expected " << protocol_version() << ")"; - set_error(SPDY_UNSUPPORTED_VERSION); } else { ProcessControlFrameHeader(control_frame_type_field); } @@ -927,7 +930,8 @@ void SpdyFramer::ProcessControlFrameHeader(uint16 control_frame_type_field) { } break; case CONTINUATION: - if (current_frame_length_ < GetContinuationMinimumSize()) { + if (current_frame_length_ < GetContinuationMinimumSize() || + protocol_version() <= SPDY3) { set_error(SPDY_INVALID_CONTROL_FRAME); } else if (current_frame_flags_ & ~HEADERS_FLAG_END_HEADERS) { set_error(SPDY_INVALID_CONTROL_FRAME_FLAGS); @@ -1043,10 +1047,11 @@ size_t SpdyFramer::UpdateCurrentFrameBuffer(const char** data, size_t* len, return bytes_to_read; } -size_t SpdyFramer::GetSerializedLength(const int spdy_version, - const SpdyHeaderBlock* headers) { +size_t SpdyFramer::GetSerializedLength( + const SpdyMajorVersion spdy_version, + const SpdyHeaderBlock* headers) { const size_t num_name_value_pairs_size - = (spdy_version < 3) ? sizeof(uint16) : sizeof(uint32); + = (spdy_version < SPDY3) ? sizeof(uint16) : sizeof(uint32); const size_t length_of_name_size = num_name_value_pairs_size; const size_t length_of_value_size = num_name_value_pairs_size; @@ -1063,16 +1068,16 @@ size_t SpdyFramer::GetSerializedLength(const int spdy_version, } void SpdyFramer::WriteHeaderBlock(SpdyFrameBuilder* frame, - const int spdy_version, + const SpdyMajorVersion spdy_version, const SpdyHeaderBlock* headers) { - if (spdy_version < 3) { + if (spdy_version < SPDY3) { frame->WriteUInt16(headers->size()); // Number of headers. } else { frame->WriteUInt32(headers->size()); // Number of headers. } SpdyHeaderBlock::const_iterator it; for (it = headers->begin(); it != headers->end(); ++it) { - if (spdy_version < 3) { + if (spdy_version < SPDY3) { frame->WriteString(it->first); frame->WriteString(it->second); } else { @@ -1597,7 +1602,8 @@ void SpdyFramer::DeliverHpackBlockAsSpdy3Block() { return; } SpdyFrameBuilder builder( - GetSerializedLength(protocol_version(), &block)); + GetSerializedLength(protocol_version(), &block), + SPDY3); SerializeNameValueBlockWithoutCompression(&builder, block); scoped_ptr<SpdyFrame> frame(builder.take()); @@ -1750,15 +1756,19 @@ size_t SpdyFramer::ProcessGoAwayFramePayload(const char* data, size_t len) { uint32 status_raw = GOAWAY_OK; successful_read = reader.ReadUInt32(&status_raw); DCHECK(successful_read); - // We've read an unsigned integer, so it's enough to only check - // upper bound to ensure the value is in valid range. - if (status_raw < GOAWAY_NUM_STATUS_CODES) { - status = static_cast<SpdyGoAwayStatus>(status_raw); + if (SpdyConstants::IsValidGoAwayStatus(protocol_version(), + status_raw)) { + status = SpdyConstants::ParseGoAwayStatus(protocol_version(), + status_raw); } else { - // TODO(hkhalil): Probably best to OnError here, depending on - // our interpretation of the spec. Keeping with existing liberal - // behavior for now. DCHECK(false); + // Throw an error for SPDY4+, keep liberal behavior + // for earlier versions. + if (protocol_version() > SPDY3) { + DLOG(WARNING) << "Invalid GO_AWAY status " << status_raw; + set_error(SPDY_INVALID_CONTROL_FRAME); + return 0; + } } } // Finished parsing the GOAWAY header, call frame handler. @@ -1816,15 +1826,17 @@ size_t SpdyFramer::ProcessRstStreamFramePayload(const char* data, size_t len) { uint32 status_raw = status; bool successful_read = reader.ReadUInt32(&status_raw); DCHECK(successful_read); - // We've read an unsigned integer, so it's enough to only check - // upper bound to ensure the value is in valid range. - if (status_raw > RST_STREAM_INVALID && - status_raw < RST_STREAM_NUM_STATUS_CODES) { + if (SpdyConstants::IsValidRstStreamStatus(protocol_version(), + status_raw)) { status = static_cast<SpdyRstStreamStatus>(status_raw); } else { - // TODO(hkhalil): Probably best to OnError here, depending on - // our interpretation of the spec. Keeping with existing liberal - // behavior for now. + // Throw an error for SPDY4+, keep liberal behavior + // for earlier versions. + if (protocol_version() > SPDY3) { + DLOG(WARNING) << "Invalid RST_STREAM status " << status_raw; + set_error(SPDY_INVALID_CONTROL_FRAME); + return 0; + } } // Finished parsing the RST_STREAM header, call frame handler. visitor_->OnRstStream(current_frame_stream_id_, status); @@ -1855,11 +1867,11 @@ size_t SpdyFramer::ProcessFramePaddingLength(const char* data, size_t len) { DCHECK_EQ(remaining_padding_payload_length_, 0u); bool pad_low = false; bool pad_high = false; - if (current_frame_flags_ & net::DATA_FLAG_PAD_LOW) { + if (current_frame_flags_ & DATA_FLAG_PAD_LOW) { pad_low = true; ++remaining_padding_length_fields_; } - if (current_frame_flags_ & net::DATA_FLAG_PAD_HIGH) { + if (current_frame_flags_ & DATA_FLAG_PAD_HIGH) { pad_high = true; ++remaining_padding_length_fields_; } @@ -1909,15 +1921,15 @@ size_t SpdyFramer::ProcessFramePadding(const char* data, size_t len) { len -= amount_to_discard; remaining_padding_payload_length_ -= amount_to_discard; remaining_data_length_ -= amount_to_discard; + } - // If the FIN flag is set, and there is no more data in this data - // frame, inform the visitor of EOF via a 0-length data frame. - if (!remaining_data_length_ && current_frame_flags_ & DATA_FLAG_FIN) { + if (remaining_data_length_ == 0) { + // If the FIN flag is set, and there is no more data in this data frame, + // inform the visitor of EOF via a 0-length data frame. + if (current_frame_flags_ & DATA_FLAG_FIN) { visitor_->OnStreamFrameData(current_frame_stream_id_, NULL, 0, true); } - } - if (remaining_data_length_ == 0) { CHANGE_STATE(SPDY_AUTO_RESET); } return original_len - len; @@ -1938,12 +1950,6 @@ size_t SpdyFramer::ProcessDataFramePayload(const char* data, size_t len) { data += amount_to_forward; len -= amount_to_forward; remaining_data_length_ -= amount_to_forward; - - // If the FIN flag is set, and there is no more data in this data - // frame, inform the visitor of EOF via a 0-length data frame. - if (!remaining_data_length_ && current_frame_flags_ & DATA_FLAG_FIN) { - visitor_->OnStreamFrameData(current_frame_stream_id_, NULL, 0, true); - } } if (remaining_data_length_ == remaining_padding_payload_length_) { @@ -1952,6 +1958,21 @@ size_t SpdyFramer::ProcessDataFramePayload(const char* data, size_t len) { return original_len - len; } +size_t SpdyFramer::ProcessIgnoredControlFramePayload(/*const char* data,*/ + size_t len) { + size_t original_len = len; + if (remaining_data_length_ > 0) { + size_t amount_to_ignore = std::min(remaining_data_length_, len); + len -= amount_to_ignore; + remaining_data_length_ -= amount_to_ignore; + } + + if (remaining_data_length_ == 0) { + CHANGE_STATE(SPDY_AUTO_RESET); + } + return original_len - len; +} + size_t SpdyFramer::ParseHeaderBlockInBuffer(const char* header_data, size_t header_length, SpdyHeaderBlock* block) const { @@ -2008,72 +2029,88 @@ size_t SpdyFramer::ParseHeaderBlockInBuffer(const char* header_data, return reader.GetBytesConsumed(); } -SpdySerializedFrame* SpdyFramer::SerializeData(const SpdyDataIR& datair) const { +SpdySerializedFrame* SpdyFramer::SerializeData( + const SpdyDataIR& data_ir) const { uint8 flags = DATA_FLAG_NONE; - if (datair.fin()) { + if (data_ir.fin()) { flags = DATA_FLAG_FIN; } if (protocol_version() > SPDY3) { int num_padding_fields = 0; - if (datair.pad_low()) { + if (data_ir.pad_low()) { flags |= DATA_FLAG_PAD_LOW; ++num_padding_fields; } - if (datair.pad_high()) { + if (data_ir.pad_high()) { flags |= DATA_FLAG_PAD_HIGH; ++num_padding_fields; } const size_t size_with_padding = num_padding_fields + - datair.data().length() + datair.padding_payload_len() + + data_ir.data().length() + data_ir.padding_payload_len() + GetDataFrameMinimumSize(); - SpdyFrameBuilder builder(size_with_padding); - builder.WriteDataFrameHeader(*this, datair.stream_id(), flags); - if (datair.pad_high()) { - builder.WriteUInt8(datair.padding_payload_len() >> 8); + SpdyFrameBuilder builder(size_with_padding, protocol_version()); + builder.WriteDataFrameHeader(*this, data_ir.stream_id(), flags); + if (data_ir.pad_high()) { + builder.WriteUInt8(data_ir.padding_payload_len() >> 8); } - if (datair.pad_low()) { - builder.WriteUInt8(datair.padding_payload_len() & 0xff); + if (data_ir.pad_low()) { + builder.WriteUInt8(data_ir.padding_payload_len() & 0xff); } - builder.WriteBytes(datair.data().data(), datair.data().length()); - if (datair.padding_payload_len() > 0) { - string padding = string(datair.padding_payload_len(), '0'); + builder.WriteBytes(data_ir.data().data(), data_ir.data().length()); + if (data_ir.padding_payload_len() > 0) { + string padding = string(data_ir.padding_payload_len(), '0'); builder.WriteBytes(padding.data(), padding.length()); } DCHECK_EQ(size_with_padding, builder.length()); return builder.take(); } else { - const size_t size = GetDataFrameMinimumSize() + datair.data().length(); - SpdyFrameBuilder builder(size); - builder.WriteDataFrameHeader(*this, datair.stream_id(), flags); - builder.WriteBytes(datair.data().data(), datair.data().length()); + const size_t size = GetDataFrameMinimumSize() + data_ir.data().length(); + SpdyFrameBuilder builder(size, protocol_version()); + builder.WriteDataFrameHeader(*this, data_ir.stream_id(), flags); + builder.WriteBytes(data_ir.data().data(), data_ir.data().length()); DCHECK_EQ(size, builder.length()); return builder.take(); } } -SpdySerializedFrame* SpdyFramer::SerializeDataFrameHeader( - const SpdyDataIR& data) const { - const size_t kSize = GetDataFrameMinimumSize(); - +SpdySerializedFrame* SpdyFramer::SerializeDataFrameHeaderWithPaddingLengthField( + const SpdyDataIR& data_ir) const { uint8 flags = DATA_FLAG_NONE; - if (data.fin()) { + if (data_ir.fin()) { flags = DATA_FLAG_FIN; } + + size_t frame_size = GetDataFrameMinimumSize(); + size_t num_padding_fields = 0; if (protocol_version() > SPDY3) { - if (data.pad_low()) { + if (data_ir.pad_low()) { flags |= DATA_FLAG_PAD_LOW; + ++num_padding_fields; } - if (data.pad_high()) { + if (data_ir.pad_high()) { flags |= DATA_FLAG_PAD_HIGH; + ++num_padding_fields; } + frame_size += num_padding_fields; } - SpdyFrameBuilder builder(kSize); - builder.WriteDataFrameHeader(*this, data.stream_id(), flags); - builder.OverwriteLength(*this, data.data().length()); - DCHECK_EQ(kSize, builder.length()); + SpdyFrameBuilder builder(frame_size, protocol_version()); + builder.WriteDataFrameHeader(*this, data_ir.stream_id(), flags); + if (protocol_version() > SPDY3) { + if (data_ir.pad_high()) { + builder.WriteUInt8(data_ir.padding_payload_len() >> 8); + } + if (data_ir.pad_low()) { + builder.WriteUInt8(data_ir.padding_payload_len() & 0xff); + } + builder.OverwriteLength(*this, num_padding_fields + + data_ir.data().length() + data_ir.padding_payload_len()); + } else { + builder.OverwriteLength(*this, data_ir.data().length()); + } + DCHECK_EQ(frame_size, builder.length()); return builder.take(); } @@ -2106,14 +2143,19 @@ SpdySerializedFrame* SpdyFramer::SerializeSynStream( string hpack_encoding; if (protocol_version() > SPDY3) { - hpack_encoder_.EncodeHeaderSet(syn_stream.name_value_block(), - &hpack_encoding); + if (enable_compression_) { + hpack_encoder_.EncodeHeaderSet( + syn_stream.name_value_block(), &hpack_encoding); + } else { + hpack_encoder_.EncodeHeaderSetWithoutCompression( + syn_stream.name_value_block(), &hpack_encoding); + } size += hpack_encoding.size(); } else { size += GetSerializedLength(syn_stream.name_value_block()); } - SpdyFrameBuilder builder(size); + SpdyFrameBuilder builder(size, protocol_version()); if (protocol_version() <= SPDY3) { builder.WriteControlFrameHeader(*this, SYN_STREAM, flags); builder.WriteUInt32(syn_stream.stream_id()); @@ -2121,10 +2163,10 @@ SpdySerializedFrame* SpdyFramer::SerializeSynStream( builder.WriteUInt8(priority << ((protocol_version() <= SPDY2) ? 6 : 5)); builder.WriteUInt8(0); // Unused byte where credential slot used to be. } else { - builder.WriteFramePrefix(*this, - HEADERS, - flags, - syn_stream.stream_id()); + builder.BeginNewFrame(*this, + HEADERS, + flags, + syn_stream.stream_id()); builder.WriteUInt32(priority); } DCHECK_EQ(GetSynStreamMinimumSize(), builder.length()); @@ -2166,22 +2208,27 @@ SpdySerializedFrame* SpdyFramer::SerializeSynReply( string hpack_encoding; if (protocol_version() > SPDY3) { - hpack_encoder_.EncodeHeaderSet(syn_reply.name_value_block(), - &hpack_encoding); + if (enable_compression_) { + hpack_encoder_.EncodeHeaderSet( + syn_reply.name_value_block(), &hpack_encoding); + } else { + hpack_encoder_.EncodeHeaderSetWithoutCompression( + syn_reply.name_value_block(), &hpack_encoding); + } size += hpack_encoding.size(); } else { size += GetSerializedLength(syn_reply.name_value_block()); } - SpdyFrameBuilder builder(size); + SpdyFrameBuilder builder(size, protocol_version()); if (protocol_version() <= SPDY3) { builder.WriteControlFrameHeader(*this, SYN_REPLY, flags); builder.WriteUInt32(syn_reply.stream_id()); } else { - builder.WriteFramePrefix(*this, - HEADERS, - flags, - syn_reply.stream_id()); + builder.BeginNewFrame(*this, + HEADERS, + flags, + syn_reply.stream_id()); } if (protocol_version() < SPDY3) { builder.WriteUInt16(0); // Unused. @@ -2218,14 +2265,14 @@ SpdySerializedFrame* SpdyFramer::SerializeRstStream( if (protocol_version() > SPDY3) { expected_length += rst_stream.description().size(); } - SpdyFrameBuilder builder(expected_length); + SpdyFrameBuilder builder(expected_length, protocol_version()); // Serialize the RST_STREAM frame. if (protocol_version() <= SPDY3) { builder.WriteControlFrameHeader(*this, RST_STREAM, 0); builder.WriteUInt32(rst_stream.stream_id()); } else { - builder.WriteFramePrefix(*this, RST_STREAM, 0, rst_stream.stream_id()); + builder.BeginNewFrame(*this, RST_STREAM, 0, rst_stream.stream_id()); } builder.WriteUInt32(rst_stream.status()); @@ -2259,11 +2306,11 @@ SpdySerializedFrame* SpdyFramer::SerializeSettings( // Size, in bytes, of this SETTINGS frame. const size_t size = GetSettingsMinimumSize() + (values->size() * setting_size); - SpdyFrameBuilder builder(size); + SpdyFrameBuilder builder(size, protocol_version()); if (protocol_version() <= SPDY3) { builder.WriteControlFrameHeader(*this, SETTINGS, flags); } else { - builder.WriteFramePrefix(*this, SETTINGS, flags, 0); + builder.BeginNewFrame(*this, SETTINGS, flags, 0); } // If this is an ACK, payload should be empty. @@ -2301,15 +2348,8 @@ SpdySerializedFrame* SpdyFramer::SerializeSettings( return builder.take(); } -SpdyFrame* SpdyFramer::SerializeBlocked(const SpdyBlockedIR& blocked) const { - DCHECK_LT(SPDY3, protocol_version()); - SpdyFrameBuilder builder(GetBlockedSize()); - builder.WriteFramePrefix(*this, BLOCKED, kNoFlags, blocked.stream_id()); - return builder.take(); -} - SpdySerializedFrame* SpdyFramer::SerializePing(const SpdyPingIR& ping) const { - SpdyFrameBuilder builder(GetPingSize()); + SpdyFrameBuilder builder(GetPingSize(), protocol_version()); if (protocol_version() <= SPDY3) { builder.WriteControlFrameHeader(*this, PING, kNoFlags); builder.WriteUInt32(static_cast<uint32>(ping.id())); @@ -2318,7 +2358,7 @@ SpdySerializedFrame* SpdyFramer::SerializePing(const SpdyPingIR& ping) const { if (ping.is_ack()) { flags |= PING_FLAG_ACK; } - builder.WriteFramePrefix(*this, PING, flags, 0); + builder.BeginNewFrame(*this, PING, flags, 0); builder.WriteUInt64(ping.id()); } DCHECK_EQ(GetPingSize(), builder.length()); @@ -2333,13 +2373,13 @@ SpdySerializedFrame* SpdyFramer::SerializeGoAway( if (protocol_version() > SPDY3) { expected_length += goaway.description().size(); } - SpdyFrameBuilder builder(expected_length); + SpdyFrameBuilder builder(expected_length, protocol_version()); // Serialize the GOAWAY frame. if (protocol_version() <= SPDY3) { builder.WriteControlFrameHeader(*this, GOAWAY, kNoFlags); } else { - builder.WriteFramePrefix(*this, GOAWAY, 0, 0); + builder.BeginNewFrame(*this, GOAWAY, 0, 0); } // GOAWAY frames specify the last good stream id for all SPDY versions. @@ -2367,6 +2407,9 @@ SpdySerializedFrame* SpdyFramer::SerializeHeaders( flags |= CONTROL_FLAG_FIN; } if (protocol_version() > SPDY3) { + // TODO(mlavan): If we overflow into a CONTINUATION frame, this will + // get overwritten below, so we should probably just get rid of the + // end_headers field. if (headers.end_headers()) { flags |= HEADERS_FLAG_END_HEADERS; } @@ -2389,21 +2432,32 @@ SpdySerializedFrame* SpdyFramer::SerializeHeaders( string hpack_encoding; if (protocol_version() > SPDY3) { - hpack_encoder_.EncodeHeaderSet(headers.name_value_block(), &hpack_encoding); + if (enable_compression_) { + hpack_encoder_.EncodeHeaderSet( + headers.name_value_block(), &hpack_encoding); + } else { + hpack_encoder_.EncodeHeaderSetWithoutCompression( + headers.name_value_block(), &hpack_encoding); + } size += hpack_encoding.size(); + if (size > GetControlFrameBufferMaxSize()) { + size += GetNumberRequiredContinuationFrames(size) * + GetContinuationMinimumSize(); + flags &= ~HEADERS_FLAG_END_HEADERS; + } } else { size += GetSerializedLength(headers.name_value_block()); } - SpdyFrameBuilder builder(size); + SpdyFrameBuilder builder(size, protocol_version()); if (protocol_version() <= SPDY3) { builder.WriteControlFrameHeader(*this, HEADERS, flags); builder.WriteUInt32(headers.stream_id()); } else { - builder.WriteFramePrefix(*this, - HEADERS, - flags, - headers.stream_id()); + builder.BeginNewFrame(*this, + HEADERS, + flags, + headers.stream_id()); if (headers.has_priority()) { builder.WriteUInt32(priority); } @@ -2414,7 +2468,10 @@ SpdySerializedFrame* SpdyFramer::SerializeHeaders( DCHECK_EQ(GetHeadersMinimumSize(), builder.length()); if (protocol_version() > SPDY3) { - builder.WriteBytes(&hpack_encoding[0], hpack_encoding.size()); + WritePayloadWithContinuation(&builder, + hpack_encoding, + headers.stream_id(), + HEADERS); } else { SerializeNameValueBlock(&builder, headers); } @@ -2435,25 +2492,35 @@ SpdySerializedFrame* SpdyFramer::SerializeHeaders( SpdySerializedFrame* SpdyFramer::SerializeWindowUpdate( const SpdyWindowUpdateIR& window_update) const { - SpdyFrameBuilder builder(GetWindowUpdateSize()); + SpdyFrameBuilder builder(GetWindowUpdateSize(), protocol_version()); if (protocol_version() <= SPDY3) { builder.WriteControlFrameHeader(*this, WINDOW_UPDATE, kNoFlags); builder.WriteUInt32(window_update.stream_id()); } else { - builder.WriteFramePrefix(*this, - WINDOW_UPDATE, - kNoFlags, - window_update.stream_id()); + builder.BeginNewFrame(*this, + WINDOW_UPDATE, + kNoFlags, + window_update.stream_id()); } builder.WriteUInt32(window_update.delta()); DCHECK_EQ(GetWindowUpdateSize(), builder.length()); return builder.take(); } +SpdyFrame* SpdyFramer::SerializeBlocked(const SpdyBlockedIR& blocked) const { + DCHECK_LT(SPDY3, protocol_version()); + SpdyFrameBuilder builder(GetBlockedSize(), protocol_version()); + builder.BeginNewFrame(*this, BLOCKED, kNoFlags, blocked.stream_id()); + return builder.take(); +} + SpdyFrame* SpdyFramer::SerializePushPromise( const SpdyPushPromiseIR& push_promise) { DCHECK_LT(SPDY3, protocol_version()); uint8 flags = 0; + // TODO(mlavan): If we overflow into a CONTINUATION frame, this will + // get overwritten below, so we should probably just get rid of the + // end_push_promise field. if (push_promise.end_push_promise()) { flags |= PUSH_PROMISE_FLAG_END_PUSH_PROMISE; } @@ -2462,21 +2529,36 @@ SpdyFrame* SpdyFramer::SerializePushPromise( string hpack_encoding; if (protocol_version() > SPDY3) { - hpack_encoder_.EncodeHeaderSet(push_promise.name_value_block(), - &hpack_encoding); + if (enable_compression_) { + hpack_encoder_.EncodeHeaderSet( + push_promise.name_value_block(), &hpack_encoding); + } else { + hpack_encoder_.EncodeHeaderSetWithoutCompression( + push_promise.name_value_block(), &hpack_encoding); + } size += hpack_encoding.size(); + if (size > GetControlFrameBufferMaxSize()) { + size += GetNumberRequiredContinuationFrames(size) * + GetContinuationMinimumSize(); + flags &= ~PUSH_PROMISE_FLAG_END_PUSH_PROMISE; + } } else { size += GetSerializedLength(push_promise.name_value_block()); } - SpdyFrameBuilder builder(size); - builder.WriteFramePrefix(*this, PUSH_PROMISE, flags, - push_promise.stream_id()); + SpdyFrameBuilder builder(size, protocol_version()); + builder.BeginNewFrame(*this, + PUSH_PROMISE, + flags, + push_promise.stream_id()); builder.WriteUInt32(push_promise.promised_stream_id()); DCHECK_EQ(GetPushPromiseMinimumSize(), builder.length()); if (protocol_version() > SPDY3) { - builder.WriteBytes(&hpack_encoding[0], hpack_encoding.size()); + WritePayloadWithContinuation(&builder, + hpack_encoding, + push_promise.stream_id(), + PUSH_PROMISE); } else { SerializeNameValueBlock(&builder, push_promise); } @@ -2507,12 +2589,17 @@ SpdyFrame* SpdyFramer::SerializeContinuation( // The size of this frame, including variable-length name-value block. size_t size = GetContinuationMinimumSize(); string hpack_encoding; - hpack_encoder_.EncodeHeaderSet(continuation.name_value_block(), - &hpack_encoding); + if (enable_compression_) { + hpack_encoder_.EncodeHeaderSet( + continuation.name_value_block(), &hpack_encoding); + } else { + hpack_encoder_.EncodeHeaderSetWithoutCompression( + continuation.name_value_block(), &hpack_encoding); + } size += hpack_encoding.size(); - SpdyFrameBuilder builder(size); - builder.WriteFramePrefix(*this, CONTINUATION, flags, + SpdyFrameBuilder builder(size, protocol_version()); + builder.BeginNewFrame(*this, CONTINUATION, flags, continuation.stream_id()); DCHECK_EQ(GetContinuationMinimumSize(), builder.length()); @@ -2602,6 +2689,69 @@ size_t SpdyFramer::GetSerializedLength(const SpdyHeaderBlock& headers) { return 2 * deflateBound(compressor, uncompressed_length); } +size_t SpdyFramer::GetNumberRequiredContinuationFrames(size_t size) { + const size_t kMaxControlFrameSize = GetControlFrameBufferMaxSize(); + DCHECK_GT(protocol_version(), SPDY3); + DCHECK_GT(size, kMaxControlFrameSize); + size_t overflow = size - kMaxControlFrameSize; + return overflow / (kMaxControlFrameSize - GetContinuationMinimumSize()) + 1; +} + +void SpdyFramer::WritePayloadWithContinuation(SpdyFrameBuilder* builder, + const string& hpack_encoding, + SpdyStreamId stream_id, + SpdyFrameType type) { + const size_t kMaxControlFrameSize = GetControlFrameBufferMaxSize(); + + // In addition to the prefix, fixed_field_size includes the size of + // any fields that come before the variable-length name/value block. + size_t fixed_field_size = 0; + uint8 end_flag = 0; + uint8 flags = 0; + if (type == HEADERS) { + fixed_field_size = GetHeadersMinimumSize(); + end_flag = HEADERS_FLAG_END_HEADERS; + } else if (type == PUSH_PROMISE) { + fixed_field_size = GetPushPromiseMinimumSize(); + end_flag = PUSH_PROMISE_FLAG_END_PUSH_PROMISE; + } else { + DLOG(FATAL) << "CONTINUATION frames cannot be used with frame type " + << FrameTypeToString(type); + } + + // Write as much of the payload as possible into the initial frame. + size_t bytes_remaining = hpack_encoding.size() - + std::min(hpack_encoding.size(), + kMaxControlFrameSize - fixed_field_size); + builder->WriteBytes(&hpack_encoding[0], + hpack_encoding.size() - bytes_remaining); + + if (bytes_remaining > 0) { + builder->OverwriteLength(*this, + kMaxControlFrameSize - GetControlFrameHeaderSize()); + } + + // Tack on CONTINUATION frames for the overflow. + while (bytes_remaining > 0) { + size_t bytes_to_write = std::min(bytes_remaining, + kMaxControlFrameSize - + GetContinuationMinimumSize()); + // Write CONTINUATION frame prefix. + if (bytes_remaining == bytes_to_write) { + flags |= end_flag; + } + builder->BeginNewFrame(*this, + CONTINUATION, + flags, + stream_id); + // Write payload fragment. + builder->WriteBytes(&hpack_encoding[hpack_encoding.size() - + bytes_remaining], + bytes_to_write); + bytes_remaining -= bytes_to_write; + } +} + // The following compression setting are based on Brian Olson's analysis. See // https://groups.google.com/group/spdy-dev/browse_thread/thread/dfaf498542fac792 // for more details. @@ -2789,7 +2939,7 @@ void SpdyFramer::SerializeNameValueBlock( // First build an uncompressed version to be fed into the compressor. const size_t uncompressed_len = GetSerializedLength( protocol_version(), &(frame.name_value_block())); - SpdyFrameBuilder uncompressed_builder(uncompressed_len); + SpdyFrameBuilder uncompressed_builder(uncompressed_len, protocol_version()); SerializeNameValueBlockWithoutCompression(&uncompressed_builder, frame.name_value_block()); scoped_ptr<SpdyFrame> uncompressed_payload(uncompressed_builder.take()); diff --git a/net/spdy/spdy_framer.h b/net/spdy/spdy_framer.h index 3188825..2da3b7e 100644 --- a/net/spdy/spdy_framer.h +++ b/net/spdy/spdy_framer.h @@ -56,14 +56,15 @@ typedef std::map<std::string, std::string> SpdyHeaderBlock; // Conveniently handles converstion to/from wire format. class NET_EXPORT_PRIVATE SettingsFlagsAndId { public: - static SettingsFlagsAndId FromWireFormat(int version, uint32 wire); + static SettingsFlagsAndId FromWireFormat(SpdyMajorVersion version, + uint32 wire); SettingsFlagsAndId() : flags_(0), id_(0) {} // TODO(hkhalil): restrict to enums instead of free-form ints. SettingsFlagsAndId(uint8 flags, uint32 id); - uint32 GetWireFormat(int version) const; + uint32 GetWireFormat(SpdyMajorVersion version) const; uint32 id() const { return id_; } uint8 flags() const { return flags_; } @@ -320,13 +321,14 @@ class NET_EXPORT_PRIVATE SpdyFramer { // Serializes a SpdyHeaderBlock. static void WriteHeaderBlock(SpdyFrameBuilder* frame, - const int spdy_version, + const SpdyMajorVersion spdy_version, const SpdyHeaderBlock* headers); // Retrieve serialized length of SpdyHeaderBlock. // TODO(hkhalil): Remove, or move to quic code. - static size_t GetSerializedLength(const int spdy_version, - const SpdyHeaderBlock* headers); + static size_t GetSerializedLength( + const SpdyMajorVersion spdy_version, + const SpdyHeaderBlock* headers); // Create a new Framer, provided a SPDY version. explicit SpdyFramer(SpdyMajorVersion version); @@ -371,8 +373,10 @@ class NET_EXPORT_PRIVATE SpdyFramer { // Serialize a data frame. SpdySerializedFrame* SerializeData(const SpdyDataIR& data) const; - // Serializes just the data frame header, excluding actual data payload. - SpdySerializedFrame* SerializeDataFrameHeader(const SpdyDataIR& data) const; + // Serializes the data frame header and optionally padding length fields, + // excluding actual data payload and padding. + SpdySerializedFrame* SerializeDataFrameHeaderWithPaddingLengthField( + const SpdyDataIR& data) const; // Serializes a SYN_STREAM frame. SpdySerializedFrame* SerializeSynStream(const SpdySynStreamIR& syn_stream); @@ -485,6 +489,9 @@ class NET_EXPORT_PRIVATE SpdyFramer { // Returns the maximum payload size of a DATA frame. size_t GetDataFrameMaximumPayload() const; + // Returns the prefix length for the given frame type. + size_t GetPrefixLength(SpdyFrameType type) const; + // For debugging. static const char* StateToString(int state); static const char* ErrorCodeToString(int error_code); @@ -497,7 +504,10 @@ class NET_EXPORT_PRIVATE SpdyFramer { SpdyStreamId expect_continuation() const { return expect_continuation_; } - SpdyPriority GetLowestPriority() const { return spdy_version_ < 3 ? 3 : 7; } + SpdyPriority GetLowestPriority() const { + return spdy_version_ < SPDY3 ? 3 : 7; + } + SpdyPriority GetHighestPriority() const { return 0; } // Deliver the given control frame's compressed headers block to the visitor @@ -509,6 +519,7 @@ class NET_EXPORT_PRIVATE SpdyFramer { size_t len); protected: + // TODO(jgraettinger): Switch to test peer pattern. FRIEND_TEST_ALL_PREFIXES(SpdyFramerTest, BasicCompression); FRIEND_TEST_ALL_PREFIXES(SpdyFramerTest, ControlFrameSizesAreValidated); FRIEND_TEST_ALL_PREFIXES(SpdyFramerTest, HeaderCompression); @@ -525,6 +536,10 @@ class NET_EXPORT_PRIVATE SpdyFramer { ReadLargeSettingsFrameInSmallChunks); FRIEND_TEST_ALL_PREFIXES(SpdyFramerTest, ControlFrameAtMaxSizeLimit); FRIEND_TEST_ALL_PREFIXES(SpdyFramerTest, ControlFrameTooLarge); + FRIEND_TEST_ALL_PREFIXES(SpdyFramerTest, + TooLargeHeadersFrameUsesContinuation); + FRIEND_TEST_ALL_PREFIXES(SpdyFramerTest, + TooLargePushPromiseFrameUsesContinuation); friend class net::HttpNetworkLayer; // This is temporary for the server. friend class net::HttpNetworkTransactionTest; friend class net::HttpProxyClientSocketPoolTest; @@ -555,6 +570,7 @@ class NET_EXPORT_PRIVATE SpdyFramer { size_t ProcessGoAwayFramePayload(const char* data, size_t len); size_t ProcessRstStreamFramePayload(const char* data, size_t len); size_t ProcessSettingsFramePayload(const char* data, size_t len); + size_t ProcessIgnoredControlFramePayload(/*const char* data,*/ size_t len); // TODO(jgraettinger): To be removed with migration to // SpdyHeadersHandlerInterface. @@ -576,6 +592,13 @@ class NET_EXPORT_PRIVATE SpdyFramer { z_stream* GetHeaderCompressor(); z_stream* GetHeaderDecompressor(); + size_t GetNumberRequiredContinuationFrames(size_t size); + + void WritePayloadWithContinuation(SpdyFrameBuilder* builder, + const std::string& hpack_encoding, + SpdyStreamId stream_id, + SpdyFrameType type); + private: // Deliver the given control frame's uncompressed headers block to the // visitor in chunks. Returns true if the visitor has accepted all of the diff --git a/net/spdy/spdy_framer_test.cc b/net/spdy/spdy_framer_test.cc index 039f4de8..8542835 100644 --- a/net/spdy/spdy_framer_test.cc +++ b/net/spdy/spdy_framer_test.cc @@ -11,6 +11,7 @@ #include "net/spdy/hpack_output_stream.h" #include "net/spdy/mock_spdy_framer_visitor.h" #include "net/spdy/spdy_frame_builder.h" +#include "net/spdy/spdy_frame_reader.h" #include "net/spdy/spdy_framer.h" #include "net/spdy/spdy_protocol.h" #include "net/spdy/spdy_test_utils.h" @@ -221,6 +222,8 @@ class SpdyFramerTestUtil { class TestSpdyVisitor : public SpdyFramerVisitorInterface, public SpdyFramerDebugVisitorInterface { public: + // This is larger than our max frame size because header blocks that + // are too long can spill over into CONTINUATION frames. static const size_t kDefaultHeaderBufferSize = 16 * 1024 * 1024; explicit TestSpdyVisitor(SpdyMajorVersion version) @@ -230,6 +233,7 @@ class TestSpdyVisitor : public SpdyFramerVisitorInterface, syn_frame_count_(0), syn_reply_frame_count_(0), headers_frame_count_(0), + push_promise_frame_count_(0), goaway_count_(0), setting_count_(0), settings_ack_sent_(0), @@ -260,13 +264,13 @@ class TestSpdyVisitor : public SpdyFramerVisitorInterface, virtual void OnError(SpdyFramer* f) OVERRIDE { LOG(INFO) << "SpdyFramer Error: " << SpdyFramer::ErrorCodeToString(f->error_code()); - error_count_++; + ++error_count_; } virtual void OnDataFrameHeader(SpdyStreamId stream_id, size_t length, bool fin) OVERRIDE { - data_frame_count_++; + ++data_frame_count_; header_stream_id_ = stream_id; } @@ -300,7 +304,9 @@ class TestSpdyVisitor : public SpdyFramerVisitorInterface, CHECK(header_buffer_valid_); size_t parsed_length = framer_.ParseHeaderBlockInBuffer( header_buffer_.get(), header_buffer_length_, &headers_); - DCHECK_EQ(header_buffer_length_, parsed_length); + LOG_IF(DFATAL, header_buffer_length_ != parsed_length) + << "Check failed: header_buffer_length_ == parsed_length " + << "(" << header_buffer_length_ << " vs. " << parsed_length << ")"; return true; } const size_t available = header_buffer_size_ - header_buffer_length_; @@ -318,24 +324,24 @@ class TestSpdyVisitor : public SpdyFramerVisitorInterface, SpdyPriority priority, bool fin, bool unidirectional) OVERRIDE { - syn_frame_count_++; + ++syn_frame_count_; InitHeaderStreaming(SYN_STREAM, stream_id); if (fin) { - fin_flag_count_++; + ++fin_flag_count_; } } virtual void OnSynReply(SpdyStreamId stream_id, bool fin) OVERRIDE { - syn_reply_frame_count_++; + ++syn_reply_frame_count_; InitHeaderStreaming(SYN_REPLY, stream_id); if (fin) { - fin_flag_count_++; + ++fin_flag_count_; } } virtual void OnRstStream(SpdyStreamId stream_id, SpdyRstStreamStatus status) OVERRIDE { - fin_frame_count_++; + ++fin_frame_count_; } virtual bool OnRstStreamFrameData(const char* rst_stream_data, @@ -349,17 +355,17 @@ class TestSpdyVisitor : public SpdyFramerVisitorInterface, virtual void OnSetting(SpdySettingsIds id, uint8 flags, uint32 value) OVERRIDE { - setting_count_++; + ++setting_count_; } virtual void OnSettingsAck() OVERRIDE { - DCHECK_GE(4, framer_.protocol_version()); - settings_ack_received_++; + DCHECK_LT(SPDY3, framer_.protocol_version()); + ++settings_ack_received_; } virtual void OnSettingsEnd() OVERRIDE { - if (framer_.protocol_version() < 4) { return; } - settings_ack_sent_++; + if (framer_.protocol_version() <= SPDY3) { return; } + ++settings_ack_sent_; } virtual void OnPing(SpdyPingId unique_id, bool is_ack) OVERRIDE { @@ -368,14 +374,14 @@ class TestSpdyVisitor : public SpdyFramerVisitorInterface, virtual void OnGoAway(SpdyStreamId last_accepted_stream_id, SpdyGoAwayStatus status) OVERRIDE { - goaway_count_++; + ++goaway_count_; } virtual void OnHeaders(SpdyStreamId stream_id, bool fin, bool end) OVERRIDE { - headers_frame_count_++; + ++headers_frame_count_; InitHeaderStreaming(HEADERS, stream_id); if (fin) { - fin_flag_count_++; + ++fin_flag_count_; } } @@ -388,13 +394,14 @@ class TestSpdyVisitor : public SpdyFramerVisitorInterface, virtual void OnPushPromise(SpdyStreamId stream_id, SpdyStreamId promised_stream_id, bool end) OVERRIDE { + ++push_promise_frame_count_; InitHeaderStreaming(PUSH_PROMISE, stream_id); last_push_promise_stream_ = stream_id; last_push_promise_promised_stream_ = promised_stream_id; } virtual void OnContinuation(SpdyStreamId stream_id, bool end) OVERRIDE { - continuation_count_++; + ++continuation_count_; } virtual void OnSendCompressedFrame(SpdyStreamId stream_id, @@ -461,6 +468,7 @@ class TestSpdyVisitor : public SpdyFramerVisitorInterface, int syn_frame_count_; int syn_reply_frame_count_; int headers_frame_count_; + int push_promise_frame_count_; int goaway_count_; int setting_count_; int settings_ack_sent_; @@ -492,12 +500,39 @@ class TestSpdyVisitor : public SpdyFramerVisitorInterface, SpdyHeaderBlock headers_; }; -// Retrieves serialized headers from SYN_STREAM frame. -// Does not check that the given frame is a SYN_STREAM. +// Retrieves serialized headers from a HEADERS or SYN_STREAM frame. base::StringPiece GetSerializedHeaders(const SpdyFrame* frame, const SpdyFramer& framer) { - return base::StringPiece(frame->data() + framer.GetSynStreamMinimumSize(), - frame->size() - framer.GetSynStreamMinimumSize()); + SpdyFrameReader reader(frame->data(), frame->size()); + reader.Seek(2); // Seek past the frame length. + SpdyFrameType frame_type; + if (framer.protocol_version() > SPDY3) { + uint8 serialized_type; + reader.ReadUInt8(&serialized_type); + frame_type = SpdyConstants::ParseFrameType(framer.protocol_version(), + serialized_type); + DCHECK_EQ(HEADERS, frame_type); + uint8 flags; + reader.ReadUInt8(&flags); + if (flags & HEADERS_FLAG_PRIORITY) { + frame_type = SYN_STREAM; + } + } else { + uint16 serialized_type; + reader.ReadUInt16(&serialized_type); + frame_type = SpdyConstants::ParseFrameType(framer.protocol_version(), + serialized_type); + DCHECK(frame_type == HEADERS || + frame_type == SYN_STREAM) << frame_type; + } + + if (frame_type == SYN_STREAM) { + return StringPiece(frame->data() + framer.GetSynStreamMinimumSize(), + frame->size() - framer.GetSynStreamMinimumSize()); + } else { + return StringPiece(frame->data() + framer.GetHeadersMinimumSize(), + frame->size() - framer.GetHeadersMinimumSize()); + } } } // namespace test @@ -517,7 +552,8 @@ class SpdyFramerTest : public ::testing::TestWithParam<SpdyMajorVersion> { protected: virtual void SetUp() { spdy_version_ = GetParam(); - spdy_version_ch_ = static_cast<unsigned char>(spdy_version_); + spdy_version_ch_ = static_cast<unsigned char>( + SpdyConstants::SerializeMajorVersion(spdy_version_)); } void CompareFrame(const string& description, @@ -673,7 +709,7 @@ TEST_P(SpdyFramerTest, HeadersWithStreamIdZero) { // Test that if we receive a PUSH_PROMISE with stream ID zero, we signal an // error (but don't crash). TEST_P(SpdyFramerTest, PushPromiseWithStreamIdZero) { - if (spdy_version_ < SPDY4) { + if (spdy_version_ <= SPDY3) { return; } @@ -698,7 +734,7 @@ TEST_P(SpdyFramerTest, PushPromiseWithStreamIdZero) { // Test that if we receive a PUSH_PROMISE with promised stream ID zero, we // signal an error (but don't crash). TEST_P(SpdyFramerTest, PushPromiseWithPromisedStreamIdZero) { - if (spdy_version_ < SPDY4) { + if (spdy_version_ <= SPDY3) { return; } @@ -721,7 +757,7 @@ TEST_P(SpdyFramerTest, PushPromiseWithPromisedStreamIdZero) { } TEST_P(SpdyFramerTest, DuplicateHeader) { - if (spdy_version_ >= 4) { + if (spdy_version_ > SPDY3) { // TODO(jgraettinger): Punting on this because we haven't determined // whether duplicate HPACK headers other than Cookie are an error. // If they are, this will need to be updated to use HpackOutputStream. @@ -729,14 +765,14 @@ TEST_P(SpdyFramerTest, DuplicateHeader) { } SpdyFramer framer(spdy_version_); // Frame builder with plentiful buffer size. - SpdyFrameBuilder frame(1024); - if (spdy_version_ < 4) { + SpdyFrameBuilder frame(1024, spdy_version_); + if (spdy_version_ <= SPDY3) { frame.WriteControlFrameHeader(framer, SYN_STREAM, CONTROL_FLAG_NONE); frame.WriteUInt32(3); // stream_id frame.WriteUInt32(0); // associated stream id frame.WriteUInt16(0); // Priority. } else { - frame.WriteFramePrefix(framer, HEADERS, HEADERS_FLAG_PRIORITY, 3); + frame.BeginNewFrame(framer, HEADERS, HEADERS_FLAG_PRIORITY, 3); frame.WriteUInt32(framer.GetHighestPriority()); } @@ -770,17 +806,17 @@ TEST_P(SpdyFramerTest, DuplicateHeader) { TEST_P(SpdyFramerTest, MultiValueHeader) { SpdyFramer framer(spdy_version_); // Frame builder with plentiful buffer size. - SpdyFrameBuilder frame(1024); - if (spdy_version_ < 4) { + SpdyFrameBuilder frame(1024, spdy_version_); + if (spdy_version_ <= SPDY3) { frame.WriteControlFrameHeader(framer, SYN_STREAM, CONTROL_FLAG_NONE); frame.WriteUInt32(3); // stream_id frame.WriteUInt32(0); // associated stream id frame.WriteUInt16(0); // Priority. } else { - frame.WriteFramePrefix(framer, - HEADERS, - HEADERS_FLAG_PRIORITY | HEADERS_FLAG_END_HEADERS, - 3); + frame.BeginNewFrame(framer, + HEADERS, + HEADERS_FLAG_PRIORITY | HEADERS_FLAG_END_HEADERS, + 3); frame.WriteUInt32(framer.GetHighestPriority()); } @@ -789,11 +825,13 @@ TEST_P(SpdyFramerTest, MultiValueHeader) { frame.WriteUInt16(1); // Number of headers. frame.WriteString("name"); frame.WriteString(value); - } else if (spdy_version_ >= 4) { - HpackOutputStream output_stream(1024); - output_stream.AppendLiteralHeaderNoIndexingWithName("name", value); + } else if (spdy_version_ > SPDY3) { + // TODO(jgraettinger): If this pattern appears again, move to test class. + std::map<string, string> header_set; + header_set["name"] = value; string buffer; - output_stream.TakeString(&buffer); + HpackEncoder encoder(ObtainHpackHuffmanTable()); + encoder.EncodeHeaderSetWithoutCompression(header_set, &buffer); frame.WriteBytes(&buffer[0], buffer.size()); } else { frame.WriteUInt32(1); // Number of headers. @@ -817,7 +855,7 @@ TEST_P(SpdyFramerTest, MultiValueHeader) { } TEST_P(SpdyFramerTest, BasicCompression) { - if (spdy_version_ >= 4) { + if (spdy_version_ > SPDY3) { // Deflate compression doesn't apply to HPACK. return; } @@ -962,7 +1000,7 @@ TEST_P(SpdyFramerTest, Basic) { 0x80, spdy_version_ch_, 0x00, 0x03, // RST_STREAM on Stream #1 0x00, 0x00, 0x00, 0x08, 0x00, 0x00, 0x00, 0x01, - 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x05, // RST_STREAM_CANCEL 0x00, 0x00, 0x00, 0x03, // DATA on Stream #3 0x00, 0x00, 0x00, 0x00, @@ -970,7 +1008,7 @@ TEST_P(SpdyFramerTest, Basic) { 0x80, spdy_version_ch_, 0x00, 0x03, // RST_STREAM on Stream #3 0x00, 0x00, 0x00, 0x08, 0x00, 0x00, 0x00, 0x03, - 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x05, // RST_STREAM_CANCEL }; const unsigned char kV3Input[] = { @@ -1021,7 +1059,7 @@ TEST_P(SpdyFramerTest, Basic) { 0x80, spdy_version_ch_, 0x00, 0x03, // RST_STREAM on Stream #1 0x00, 0x00, 0x00, 0x08, 0x00, 0x00, 0x00, 0x01, - 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x05, // RST_STREAM_CANCEL 0x00, 0x00, 0x00, 0x03, // DATA on Stream #3 0x00, 0x00, 0x00, 0x00, @@ -1029,7 +1067,7 @@ TEST_P(SpdyFramerTest, Basic) { 0x80, spdy_version_ch_, 0x00, 0x03, // RST_STREAM on Stream #3 0x00, 0x00, 0x00, 0x08, 0x00, 0x00, 0x00, 0x03, - 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x05, // RST_STREAM_CANCEL }; // SYN_STREAM doesn't exist in SPDY4, so instead we send @@ -1066,14 +1104,14 @@ TEST_P(SpdyFramerTest, Basic) { 0x00, 0x04, 0x03, 0x00, // RST_STREAM on Stream #1 0x00, 0x00, 0x00, 0x01, - 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x08, // RST_STREAM_CANCEL 0x00, 0x00, 0x00, 0x00, // DATA on Stream #3 0x00, 0x00, 0x00, 0x03, 0x00, 0x0f, 0x03, 0x00, // RST_STREAM on Stream #3 0x00, 0x00, 0x00, 0x03, - 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x08, // RST_STREAM_CANCEL 0x52, 0x45, 0x53, 0x45, // opaque data 0x54, 0x53, 0x54, 0x52, 0x45, 0x41, 0x4d, @@ -1292,7 +1330,7 @@ TEST_P(SpdyFramerTest, FinOnSynReplyFrame) { } TEST_P(SpdyFramerTest, HeaderCompression) { - if (spdy_version_ >= 4) { + if (spdy_version_ > SPDY3) { // Deflate compression doesn't apply to HPACK. return; } @@ -1376,7 +1414,7 @@ TEST_P(SpdyFramerTest, UnclosedStreamDataCompressors) { EXPECT_TRUE(syn_frame.get() != NULL); StringPiece bytes = "this is a test test test test test!"; - net::SpdyDataIR data_ir(1, bytes); + SpdyDataIR data_ir(1, bytes); data_ir.set_fin(true); scoped_ptr<SpdyFrame> send_frame(send_framer.SerializeData(data_ir)); EXPECT_TRUE(send_frame.get() != NULL); @@ -1420,7 +1458,7 @@ TEST_P(SpdyFramerTest, UnclosedStreamDataCompressorsOneByteAtATime) { EXPECT_TRUE(syn_frame.get() != NULL); const char bytes[] = "this is a test test test test test!"; - net::SpdyDataIR data_ir(1, StringPiece(bytes, arraysize(bytes))); + SpdyDataIR data_ir(1, StringPiece(bytes, arraysize(bytes))); data_ir.set_fin(true); scoped_ptr<SpdyFrame> send_frame(send_framer.SerializeData(data_ir)); EXPECT_TRUE(send_frame.get() != NULL); @@ -1454,7 +1492,7 @@ TEST_P(SpdyFramerTest, UnclosedStreamDataCompressorsOneByteAtATime) { TEST_P(SpdyFramerTest, WindowUpdateFrame) { SpdyFramer framer(spdy_version_); scoped_ptr<SpdyFrame> frame(framer.SerializeWindowUpdate( - net::SpdyWindowUpdateIR(1, 0x12345678))); + SpdyWindowUpdateIR(1, 0x12345678))); const char kDescription[] = "WINDOW_UPDATE frame, stream 1, delta 0x12345678"; const unsigned char kV3FrameData[] = { // Also applies for V2. @@ -1507,7 +1545,69 @@ TEST_P(SpdyFramerTest, CreateDataFrame) { SpdyDataIR data_header_ir(1); data_header_ir.SetDataShallow(base::StringPiece(bytes, strlen(bytes))); - frame.reset(framer.SerializeDataFrameHeader(data_header_ir)); + frame.reset(framer.SerializeDataFrameHeaderWithPaddingLengthField( + data_header_ir)); + CompareCharArraysWithHexError( + kDescription, + reinterpret_cast<const unsigned char*>(frame->data()), + framer.GetDataFrameMinimumSize(), + IsSpdy4() ? kV4FrameData : kV3FrameData, + framer.GetDataFrameMinimumSize()); + } + + { + const char kDescription[] = "'hello' data frame with more padding, no FIN"; + const unsigned char kV3FrameData[] = { // Also applies for V2. + 0x00, 0x00, 0x00, 0x01, + 0x00, 0x00, 0x00, 0x05, + 'h', 'e', 'l', 'l', + 'o' + }; + + const unsigned char kV4FrameData[] = { + 0x01, 0x0b, 0x00, 0x30, // Length = 267. PAD_HIGH and PAD_LOW set. + 0x00, 0x00, 0x00, 0x01, + 0x01, 0x04, // Pad Low and Pad High fields. + 'h', 'e', 'l', 'l', // Data + 'o', + // Padding of 260 zeros (so both PAD_HIGH and PAD_LOW fields are used). + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', + }; + const char bytes[] = "hello"; + + SpdyDataIR data_ir(1, StringPiece(bytes, strlen(bytes))); + // 260 zeros and the pad low/high fields make the overall padding to be 262 + // bytes. + data_ir.set_padding_len(262); + scoped_ptr<SpdyFrame> frame(framer.SerializeData(data_ir)); + if (IsSpdy4()) { + CompareFrame( + kDescription, *frame, kV4FrameData, arraysize(kV4FrameData)); + } else { + CompareFrame( + kDescription, *frame, kV3FrameData, arraysize(kV3FrameData)); + } + + frame.reset(framer.SerializeDataFrameHeaderWithPaddingLengthField(data_ir)); CompareCharArraysWithHexError( kDescription, reinterpret_cast<const unsigned char*>(frame->data()), @@ -1517,7 +1617,7 @@ TEST_P(SpdyFramerTest, CreateDataFrame) { } { - const char kDescription[] = "'hello' data frame with padding, no FIN"; + const char kDescription[] = "'hello' data frame with few padding, no FIN"; const unsigned char kV3FrameData[] = { // Also applies for V2. 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x05, @@ -1537,7 +1637,7 @@ TEST_P(SpdyFramerTest, CreateDataFrame) { const char bytes[] = "hello"; SpdyDataIR data_ir(1, StringPiece(bytes, strlen(bytes))); - // 7 zeros and the pad low field make the overal padding to be 8 bytes. + // 7 zeros and the pad low field make the overall padding to be 8 bytes. data_ir.set_padding_len(8); scoped_ptr<SpdyFrame> frame(framer.SerializeData(data_ir)); if (IsSpdy4()) { @@ -1550,6 +1650,47 @@ TEST_P(SpdyFramerTest, CreateDataFrame) { } { + const char kDescription[] = + "'hello' data frame with 1 byte padding, no FIN"; + const unsigned char kV3FrameData[] = { // Also applies for V2. + 0x00, 0x00, 0x00, 0x01, + 0x00, 0x00, 0x00, 0x05, + 'h', 'e', 'l', 'l', + 'o' + }; + + const unsigned char kV4FrameData[] = { + 0x00, 0x06, 0x00, 0x10, // Length = 6. PAD_LOW set. + 0x00, 0x00, 0x00, 0x01, + 0x00, // Pad Low field. + 'h', 'e', 'l', 'l', // Data + 'o', + }; + const char bytes[] = "hello"; + + SpdyDataIR data_ir(1, StringPiece(bytes, strlen(bytes))); + // The pad low field itself is used for the 1-byte padding and no padding + // payload is needed. + data_ir.set_padding_len(1); + scoped_ptr<SpdyFrame> frame(framer.SerializeData(data_ir)); + if (IsSpdy4()) { + CompareFrame( + kDescription, *frame, kV4FrameData, arraysize(kV4FrameData)); + } else { + CompareFrame( + kDescription, *frame, kV3FrameData, arraysize(kV3FrameData)); + } + + frame.reset(framer.SerializeDataFrameHeaderWithPaddingLengthField(data_ir)); + CompareCharArraysWithHexError( + kDescription, + reinterpret_cast<const unsigned char*>(frame->data()), + framer.GetDataFrameMinimumSize(), + IsSpdy4() ? kV4FrameData : kV3FrameData, + framer.GetDataFrameMinimumSize()); + } + + { const char kDescription[] = "Data frame with negative data byte, no FIN"; const unsigned char kV3FrameData[] = { // Also applies for V2. 0x00, 0x00, 0x00, 0x01, @@ -1561,7 +1702,7 @@ TEST_P(SpdyFramerTest, CreateDataFrame) { 0x00, 0x00, 0x00, 0x01, 0xff }; - net::SpdyDataIR data_ir(1, StringPiece("\xff", 1)); + SpdyDataIR data_ir(1, StringPiece("\xff", 1)); scoped_ptr<SpdyFrame> frame(framer.SerializeData(data_ir)); if (IsSpdy4()) { CompareFrame( @@ -1586,7 +1727,7 @@ TEST_P(SpdyFramerTest, CreateDataFrame) { 'h', 'e', 'l', 'l', 'o' }; - net::SpdyDataIR data_ir(1, StringPiece("hello", 5)); + SpdyDataIR data_ir(1, StringPiece("hello", 5)); data_ir.set_fin(true); scoped_ptr<SpdyFrame> frame(framer.SerializeData(data_ir)); if (IsSpdy4()) { @@ -1608,7 +1749,7 @@ TEST_P(SpdyFramerTest, CreateDataFrame) { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, }; - net::SpdyDataIR data_ir(1, StringPiece()); + SpdyDataIR data_ir(1, StringPiece()); scoped_ptr<SpdyFrame> frame(framer.SerializeData(data_ir)); if (IsSpdy4()) { CompareFrame( @@ -1617,6 +1758,14 @@ TEST_P(SpdyFramerTest, CreateDataFrame) { CompareFrame( kDescription, *frame, kV3FrameData, arraysize(kV3FrameData)); } + + frame.reset(framer.SerializeDataFrameHeaderWithPaddingLengthField(data_ir)); + CompareCharArraysWithHexError( + kDescription, + reinterpret_cast<const unsigned char*>(frame->data()), + framer.GetDataFrameMinimumSize(), + IsSpdy4() ? kV4FrameData : kV3FrameData, + framer.GetDataFrameMinimumSize()); } { @@ -1633,7 +1782,7 @@ TEST_P(SpdyFramerTest, CreateDataFrame) { 'h', 'e', 'l', 'l', 'o' }; - net::SpdyDataIR data_ir(0x7fffffff, "hello"); + SpdyDataIR data_ir(0x7fffffff, "hello"); data_ir.set_fin(true); scoped_ptr<SpdyFrame> frame(framer.SerializeData(data_ir)); if (IsSpdy4()) { @@ -1662,7 +1811,7 @@ TEST_P(SpdyFramerTest, CreateDataFrame) { memcpy(expected_frame_data.get(), kFrameHeader, arraysize(kFrameHeader)); memset(expected_frame_data.get() + arraysize(kFrameHeader), 'A', kDataSize); - net::SpdyDataIR data_ir(1, StringPiece(kData.data(), kData.size())); + SpdyDataIR data_ir(1, StringPiece(kData.data(), kData.size())); data_ir.set_fin(true); scoped_ptr<SpdyFrame> frame(framer.SerializeData(data_ir)); CompareFrame(kDescription, *frame, expected_frame_data.get(), kFrameSize); @@ -2136,7 +2285,7 @@ TEST_P(SpdyFramerTest, CreateRstStream) { 0x00, 0x00, 0x00, 0x01, 0x52, 0x53, 0x54 }; - net::SpdyRstStreamIR rst_stream(1, RST_STREAM_PROTOCOL_ERROR, "RST"); + SpdyRstStreamIR rst_stream(1, RST_STREAM_PROTOCOL_ERROR, "RST"); scoped_ptr<SpdyFrame> frame(framer.SerializeRstStream(rst_stream)); if (IsSpdy4()) { CompareFrame(kDescription, *frame, kV4FrameData, arraysize(kV4FrameData)); @@ -2158,9 +2307,9 @@ TEST_P(SpdyFramerTest, CreateRstStream) { 0x7f, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01, }; - net::SpdyRstStreamIR rst_stream(0x7FFFFFFF, - RST_STREAM_PROTOCOL_ERROR, - ""); + SpdyRstStreamIR rst_stream(0x7FFFFFFF, + RST_STREAM_PROTOCOL_ERROR, + ""); scoped_ptr<SpdyFrame> frame(framer.SerializeRstStream(rst_stream)); if (IsSpdy4()) { CompareFrame(kDescription, *frame, kV4FrameData, arraysize(kV4FrameData)); @@ -2182,9 +2331,9 @@ TEST_P(SpdyFramerTest, CreateRstStream) { 0x7f, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x06, }; - net::SpdyRstStreamIR rst_stream(0x7FFFFFFF, - RST_STREAM_INTERNAL_ERROR, - ""); + SpdyRstStreamIR rst_stream(0x7FFFFFFF, + RST_STREAM_INTERNAL_ERROR, + ""); scoped_ptr<SpdyFrame> frame(framer.SerializeRstStream(rst_stream)); if (IsSpdy4()) { CompareFrame(kDescription, *frame, kV4FrameData, arraysize(kV4FrameData)); @@ -2680,7 +2829,7 @@ TEST_P(SpdyFramerTest, CreateWindowUpdate) { 0x00, 0x00, 0x00, 0x01, }; scoped_ptr<SpdyFrame> frame( - framer.SerializeWindowUpdate(net::SpdyWindowUpdateIR(1, 1))); + framer.SerializeWindowUpdate(SpdyWindowUpdateIR(1, 1))); if (IsSpdy4()) { CompareFrame(kDescription, *frame, kV4FrameData, arraysize(kV4FrameData)); } else { @@ -2702,7 +2851,7 @@ TEST_P(SpdyFramerTest, CreateWindowUpdate) { 0x00, 0x00, 0x00, 0x01, }; scoped_ptr<SpdyFrame> frame(framer.SerializeWindowUpdate( - net::SpdyWindowUpdateIR(0x7FFFFFFF, 1))); + SpdyWindowUpdateIR(0x7FFFFFFF, 1))); if (IsSpdy4()) { CompareFrame(kDescription, *frame, kV4FrameData, arraysize(kV4FrameData)); } else { @@ -2724,7 +2873,7 @@ TEST_P(SpdyFramerTest, CreateWindowUpdate) { 0x7f, 0xff, 0xff, 0xff, }; scoped_ptr<SpdyFrame> frame(framer.SerializeWindowUpdate( - net::SpdyWindowUpdateIR(1, 0x7FFFFFFF))); + SpdyWindowUpdateIR(1, 0x7FFFFFFF))); if (IsSpdy4()) { CompareFrame(kDescription, *frame, kV4FrameData, arraysize(kV4FrameData)); } else { @@ -2769,13 +2918,13 @@ TEST_P(SpdyFramerTest, CreateBlocked) { CompareFrames(kDescription, *frame_serialized, *frame_created); } -TEST_P(SpdyFramerTest, CreatePushPromise) { +TEST_P(SpdyFramerTest, CreatePushPromiseUncompressed) { if (spdy_version_ < SPDY4) { return; } SpdyFramer framer(spdy_version_); - + framer.set_enable_compression(false); const char kDescription[] = "PUSH_PROMISE frame"; const unsigned char kFrameData[] = { @@ -2888,7 +3037,7 @@ TEST_P(SpdyFramerTest, ReadCompressedHeadersHeaderBlockWithHalfClose) { } TEST_P(SpdyFramerTest, ControlFrameAtMaxSizeLimit) { - if (spdy_version_ >= 4) { + if (spdy_version_ > SPDY3) { // TODO(jgraettinger): This test setup doesn't work with HPACK. return; } @@ -2923,7 +3072,7 @@ TEST_P(SpdyFramerTest, ControlFrameAtMaxSizeLimit) { } TEST_P(SpdyFramerTest, ControlFrameTooLarge) { - if (spdy_version_ >= 4) { + if (spdy_version_ > SPDY3) { // TODO(jgraettinger): This test setup doesn't work with HPACK. return; } @@ -2963,6 +3112,63 @@ TEST_P(SpdyFramerTest, ControlFrameTooLarge) { EXPECT_EQ(0u, visitor.header_buffer_length_); } +TEST_P(SpdyFramerTest, TooLargeHeadersFrameUsesContinuation) { + if (spdy_version_ < SPDY4) { + return; + } + SpdyFramer framer(spdy_version_); + framer.set_enable_compression(false); + SpdyHeadersIR headers(1); + + // Exact payload length will change with HPACK, but this should be long + // enough to cause an overflow. + const size_t kBigValueSize = framer.GetControlFrameBufferMaxSize(); + string big_value(kBigValueSize, 'x'); + headers.SetHeader("aa", big_value.c_str()); + scoped_ptr<SpdyFrame> control_frame(framer.SerializeHeaders(headers)); + EXPECT_TRUE(control_frame.get() != NULL); + EXPECT_GT(control_frame->size(), framer.GetControlFrameBufferMaxSize()); + + TestSpdyVisitor visitor(spdy_version_); + visitor.SimulateInFramer( + reinterpret_cast<unsigned char*>(control_frame->data()), + control_frame->size()); + EXPECT_TRUE(visitor.header_buffer_valid_); + EXPECT_EQ(0, visitor.error_count_); + EXPECT_EQ(1, visitor.headers_frame_count_); + EXPECT_EQ(1, visitor.continuation_count_); + EXPECT_EQ(1, visitor.zero_length_control_frame_header_data_count_); +} + +TEST_P(SpdyFramerTest, TooLargePushPromiseFrameUsesContinuation) { + if (spdy_version_ < SPDY4) { + return; + } + SpdyFramer framer(spdy_version_); + framer.set_enable_compression(false); + SpdyPushPromiseIR push_promise(1, 2); + + // Exact payload length will change with HPACK, but this should be long + // enough to cause an overflow. + const size_t kBigValueSize = framer.GetControlFrameBufferMaxSize(); + string big_value(kBigValueSize, 'x'); + push_promise.SetHeader("aa", big_value.c_str()); + scoped_ptr<SpdyFrame> control_frame( + framer.SerializePushPromise(push_promise)); + EXPECT_TRUE(control_frame.get() != NULL); + EXPECT_GT(control_frame->size(), framer.GetControlFrameBufferMaxSize()); + + TestSpdyVisitor visitor(spdy_version_); + visitor.SimulateInFramer( + reinterpret_cast<unsigned char*>(control_frame->data()), + control_frame->size()); + EXPECT_TRUE(visitor.header_buffer_valid_); + EXPECT_EQ(0, visitor.error_count_); + EXPECT_EQ(1, visitor.push_promise_frame_count_); + EXPECT_EQ(1, visitor.continuation_count_); + EXPECT_EQ(1, visitor.zero_length_control_frame_header_data_count_); +} + // Check that the framer stops delivering header data chunks once the visitor // declares it doesn't want any more. This is important to guard against // "zip bomb" types of attacks. @@ -3007,7 +3213,7 @@ TEST_P(SpdyFramerTest, ControlFrameMuchTooLarge) { } TEST_P(SpdyFramerTest, DecompressCorruptHeaderBlock) { - if (spdy_version_ >= 4) { + if (spdy_version_ > SPDY3) { // Deflate compression doesn't apply to HPACK. return; } @@ -3086,7 +3292,7 @@ TEST_P(SpdyFramerTest, ReadZeroLenSettingsFrame) { visitor.SimulateInFramer( reinterpret_cast<unsigned char*>(control_frame->data()), framer.GetControlFrameHeaderSize()); - if (spdy_version_ < 4) { + if (spdy_version_ <= SPDY3) { // Should generate an error, since zero-len settings frames are unsupported. EXPECT_EQ(1, visitor.error_count_); } else { @@ -3148,7 +3354,7 @@ TEST_P(SpdyFramerTest, ReadLargeSettingsFrame) { control_frame->size()); EXPECT_EQ(0, visitor.error_count_); EXPECT_EQ(3, visitor.setting_count_); - if (spdy_version_ >= 4) { + if (spdy_version_ > SPDY3) { EXPECT_EQ(1, visitor.settings_ack_sent_); } @@ -3166,7 +3372,7 @@ TEST_P(SpdyFramerTest, ReadLargeSettingsFrame) { } EXPECT_EQ(0, visitor.error_count_); EXPECT_EQ(3 * 2, visitor.setting_count_); - if (spdy_version_ >= 4) { + if (spdy_version_ > SPDY3) { EXPECT_EQ(2, visitor.settings_ack_sent_); } } @@ -3289,7 +3495,7 @@ TEST_P(SpdyFramerTest, ReadOutOfOrderSettings) { } TEST_P(SpdyFramerTest, ProcessSettingsAckFrame) { - if (spdy_version_ < 4) { + if (spdy_version_ <= SPDY3) { return; } SpdyFramer framer(spdy_version_); @@ -3310,7 +3516,7 @@ TEST_P(SpdyFramerTest, ProcessSettingsAckFrame) { TEST_P(SpdyFramerTest, ProcessDataFrameWithPadding) { - if (spdy_version_ < 4) { + if (spdy_version_ <= SPDY3) { return; } @@ -3380,7 +3586,7 @@ TEST_P(SpdyFramerTest, ProcessDataFrameWithPadding) { TEST_P(SpdyFramerTest, ReadWindowUpdate) { SpdyFramer framer(spdy_version_); scoped_ptr<SpdyFrame> control_frame( - framer.SerializeWindowUpdate(net::SpdyWindowUpdateIR(1, 2))); + framer.SerializeWindowUpdate(SpdyWindowUpdateIR(1, 2))); TestSpdyVisitor visitor(spdy_version_); visitor.SimulateInFramer( reinterpret_cast<unsigned char*>(control_frame->data()), @@ -3444,7 +3650,7 @@ TEST_P(SpdyFramerTest, ReadCredentialFrameFollowedByAnotherFrame) { string multiple_frame_data(reinterpret_cast<const char*>(kV3FrameData), arraysize(kV3FrameData)); scoped_ptr<SpdyFrame> control_frame( - framer.SerializeWindowUpdate(net::SpdyWindowUpdateIR(1, 2))); + framer.SerializeWindowUpdate(SpdyWindowUpdateIR(1, 2))); multiple_frame_data.append(string(control_frame->data(), control_frame->size())); visitor.SimulateInFramer( @@ -3455,13 +3661,13 @@ TEST_P(SpdyFramerTest, ReadCredentialFrameFollowedByAnotherFrame) { EXPECT_EQ(2u, visitor.last_window_update_delta_); } -TEST_P(SpdyFramerTest, CreateContinuation) { +TEST_P(SpdyFramerTest, CreateContinuationUncompressed) { if (spdy_version_ < SPDY4) { return; } SpdyFramer framer(spdy_version_); - + framer.set_enable_compression(false); const char kDescription[] = "CONTINUATION frame"; const unsigned char kFrameData[] = { @@ -3483,7 +3689,7 @@ TEST_P(SpdyFramerTest, CreateContinuation) { } TEST_P(SpdyFramerTest, ReadCompressedPushPromise) { - if (spdy_version_ < 4) { + if (spdy_version_ <= SPDY3) { return; } @@ -3506,7 +3712,7 @@ TEST_P(SpdyFramerTest, ReadCompressedPushPromise) { } TEST_P(SpdyFramerTest, ReadHeadersWithContinuation) { - if (spdy_version_ < 4) { + if (spdy_version_ <= SPDY3) { return; } @@ -3551,7 +3757,7 @@ TEST_P(SpdyFramerTest, ReadHeadersWithContinuation) { } TEST_P(SpdyFramerTest, ReadHeadersWithContinuationAndFin) { - if (spdy_version_ < 4) { + if (spdy_version_ <= SPDY3) { return; } @@ -3597,7 +3803,7 @@ TEST_P(SpdyFramerTest, ReadHeadersWithContinuationAndFin) { } TEST_P(SpdyFramerTest, ReadPushPromiseWithContinuation) { - if (spdy_version_ < 4) { + if (spdy_version_ <= SPDY3) { return; } @@ -3644,7 +3850,7 @@ TEST_P(SpdyFramerTest, ReadPushPromiseWithContinuation) { } TEST_P(SpdyFramerTest, ReadContinuationWithWrongStreamId) { - if (spdy_version_ < 4) { + if (spdy_version_ <= SPDY3) { return; } @@ -3680,7 +3886,7 @@ TEST_P(SpdyFramerTest, ReadContinuationWithWrongStreamId) { } TEST_P(SpdyFramerTest, ReadContinuationOutOfOrder) { - if (spdy_version_ < 4) { + if (spdy_version_ <= SPDY3) { return; } @@ -3707,7 +3913,7 @@ TEST_P(SpdyFramerTest, ReadContinuationOutOfOrder) { } TEST_P(SpdyFramerTest, ExpectContinuationReceiveData) { - if (spdy_version_ < 4) { + if (spdy_version_ <= SPDY3) { return; } @@ -3740,7 +3946,7 @@ TEST_P(SpdyFramerTest, ExpectContinuationReceiveData) { } TEST_P(SpdyFramerTest, ExpectContinuationReceiveControlFrame) { - if (spdy_version_ < 4) { + if (spdy_version_ <= SPDY3) { return; } @@ -3933,7 +4139,7 @@ TEST_P(SpdyFramerTest, StatusCodeToStringTest) { EXPECT_STREQ("FLOW_CONTROL_ERROR", SpdyFramer::StatusCodeToString(RST_STREAM_FLOW_CONTROL_ERROR)); EXPECT_STREQ("UNKNOWN_STATUS", - SpdyFramer::StatusCodeToString(RST_STREAM_NUM_STATUS_CODES)); + SpdyFramer::StatusCodeToString(-1)); } TEST_P(SpdyFramerTest, FrameTypeToStringTest) { @@ -3997,7 +4203,7 @@ TEST_P(SpdyFramerTest, CatchProbableHttpResponse) { } TEST_P(SpdyFramerTest, DataFrameFlagsV2V3) { - if (spdy_version_ >= 4) { + if (spdy_version_ > SPDY3) { return; } @@ -4008,7 +4214,7 @@ TEST_P(SpdyFramerTest, DataFrameFlagsV2V3) { SpdyFramer framer(spdy_version_); framer.set_visitor(&visitor); - net::SpdyDataIR data_ir(1, StringPiece("hello", 5)); + SpdyDataIR data_ir(1, StringPiece("hello", 5)); scoped_ptr<SpdyFrame> frame(framer.SerializeData(data_ir)); SetFrameFlags(frame.get(), flags, spdy_version_); @@ -4037,7 +4243,7 @@ TEST_P(SpdyFramerTest, DataFrameFlagsV2V3) { } TEST_P(SpdyFramerTest, DataFrameFlagsV4) { - if (spdy_version_ < 4) { + if (spdy_version_ <= SPDY3) { return; } @@ -4051,7 +4257,7 @@ TEST_P(SpdyFramerTest, DataFrameFlagsV4) { SpdyFramer framer(spdy_version_); framer.set_visitor(&visitor); - net::SpdyDataIR data_ir(1, StringPiece("hello", 5)); + SpdyDataIR data_ir(1, StringPiece("hello", 5)); scoped_ptr<SpdyFrame> frame(framer.SerializeData(data_ir)); SetFrameFlags(frame.get(), flags, spdy_version_); @@ -4210,7 +4416,7 @@ TEST_P(SpdyFramerTest, RstStreamFrameFlags) { SpdyFramer framer(spdy_version_); framer.set_visitor(&visitor); - net::SpdyRstStreamIR rst_stream(13, RST_STREAM_CANCEL, ""); + SpdyRstStreamIR rst_stream(13, RST_STREAM_CANCEL, ""); scoped_ptr<SpdyFrame> frame(framer.SerializeRstStream(rst_stream)); SetFrameFlags(frame.get(), flags, spdy_version_); @@ -4235,7 +4441,7 @@ TEST_P(SpdyFramerTest, RstStreamFrameFlags) { } TEST_P(SpdyFramerTest, SettingsFrameFlagsOldFormat) { - if (spdy_version_ >= 4) { return; } + if (spdy_version_ > SPDY3) { return; } for (int flags = 0; flags < 256; ++flags) { SCOPED_TRACE(testing::Message() << "Flags " << flags); @@ -4276,7 +4482,7 @@ TEST_P(SpdyFramerTest, SettingsFrameFlagsOldFormat) { } TEST_P(SpdyFramerTest, SettingsFrameFlags) { - if (spdy_version_ < 4) { return; } + if (spdy_version_ <= SPDY3) { return; } for (int flags = 0; flags < 256; ++flags) { SCOPED_TRACE(testing::Message() << "Flags " << flags); @@ -4422,7 +4628,7 @@ TEST_P(SpdyFramerTest, PingFrameFlags) { scoped_ptr<SpdyFrame> frame(framer.SerializePing(SpdyPingIR(42))); SetFrameFlags(frame.get(), flags, spdy_version_); - if (spdy_version_ >= SPDY4 && + if (spdy_version_ > SPDY3 && flags == PING_FLAG_ACK) { EXPECT_CALL(visitor, OnPing(42, true)); } else if (flags == 0) { @@ -4432,7 +4638,7 @@ TEST_P(SpdyFramerTest, PingFrameFlags) { } framer.ProcessInput(frame->data(), frame->size()); - if ((spdy_version_ >= SPDY4 && flags == PING_FLAG_ACK) || + if ((spdy_version_ > SPDY3 && flags == PING_FLAG_ACK) || flags == 0) { EXPECT_EQ(SpdyFramer::SPDY_RESET, framer.state()); EXPECT_EQ(SpdyFramer::SPDY_NO_ERROR, framer.error_code()) @@ -4455,7 +4661,7 @@ TEST_P(SpdyFramerTest, WindowUpdateFrameFlags) { framer.set_visitor(&visitor); scoped_ptr<SpdyFrame> frame(framer.SerializeWindowUpdate( - net::SpdyWindowUpdateIR(4, 1024))); + SpdyWindowUpdateIR(4, 1024))); SetFrameFlags(frame.get(), flags, spdy_version_); if (flags != 0) { @@ -4623,61 +4829,72 @@ TEST_P(SpdyFramerTest, SettingsFlagsAndId) { // Test handling of a RST_STREAM with out-of-bounds status codes. TEST_P(SpdyFramerTest, RstStreamStatusBounds) { - DCHECK_GE(0xff, RST_STREAM_NUM_STATUS_CODES); - + const unsigned char kRstStreamStatusTooLow = 0x00; + const unsigned char kRstStreamStatusTooHigh = 0xff; const unsigned char kV3RstStreamInvalid[] = { 0x80, spdy_version_ch_, 0x00, 0x03, 0x00, 0x00, 0x00, 0x08, 0x00, 0x00, 0x00, 0x01, - 0x00, 0x00, 0x00, RST_STREAM_INVALID + 0x00, 0x00, 0x00, kRstStreamStatusTooLow }; const unsigned char kV4RstStreamInvalid[] = { 0x00, 0x04, 0x03, 0x00, 0x00, 0x00, 0x00, 0x01, - 0x00, 0x00, 0x00, RST_STREAM_INVALID + 0x00, 0x00, 0x00, kRstStreamStatusTooLow }; const unsigned char kV3RstStreamNumStatusCodes[] = { 0x80, spdy_version_ch_, 0x00, 0x03, 0x00, 0x00, 0x00, 0x08, 0x00, 0x00, 0x00, 0x01, - 0x00, 0x00, 0x00, RST_STREAM_NUM_STATUS_CODES + 0x00, 0x00, 0x00, kRstStreamStatusTooHigh }; const unsigned char kV4RstStreamNumStatusCodes[] = { 0x00, 0x04, 0x03, 0x00, 0x00, 0x00, 0x00, 0x01, - 0x00, 0x00, 0x00, RST_STREAM_NUM_STATUS_CODES + 0x00, 0x00, 0x00, kRstStreamStatusTooHigh }; testing::StrictMock<test::MockSpdyFramerVisitor> visitor; SpdyFramer framer(spdy_version_); framer.set_visitor(&visitor); - EXPECT_CALL(visitor, OnRstStream(1, RST_STREAM_INVALID)); if (IsSpdy4()) { + EXPECT_CALL(visitor, OnError(_)); framer.ProcessInput(reinterpret_cast<const char*>(kV4RstStreamInvalid), arraysize(kV4RstStreamInvalid)); + EXPECT_EQ(SpdyFramer::SPDY_ERROR, framer.state()); + EXPECT_EQ(SpdyFramer::SPDY_INVALID_CONTROL_FRAME, framer.error_code()) + << SpdyFramer::ErrorCodeToString(framer.error_code()); } else { + EXPECT_CALL(visitor, OnRstStream(1, RST_STREAM_INVALID)); framer.ProcessInput(reinterpret_cast<const char*>(kV3RstStreamInvalid), arraysize(kV3RstStreamInvalid)); - } - EXPECT_EQ(SpdyFramer::SPDY_RESET, framer.state()); - EXPECT_EQ(SpdyFramer::SPDY_NO_ERROR, framer.error_code()) + EXPECT_EQ(SpdyFramer::SPDY_RESET, framer.state()); + EXPECT_EQ(SpdyFramer::SPDY_NO_ERROR, framer.error_code()) << SpdyFramer::ErrorCodeToString(framer.error_code()); + } + + + framer.Reset(); - EXPECT_CALL(visitor, OnRstStream(1, RST_STREAM_INVALID)); if (IsSpdy4()) { + EXPECT_CALL(visitor, OnError(_)); framer.ProcessInput( reinterpret_cast<const char*>(kV4RstStreamNumStatusCodes), arraysize(kV4RstStreamNumStatusCodes)); + EXPECT_EQ(SpdyFramer::SPDY_ERROR, framer.state()); + EXPECT_EQ(SpdyFramer::SPDY_INVALID_CONTROL_FRAME, framer.error_code()) + << SpdyFramer::ErrorCodeToString(framer.error_code()); } else { + EXPECT_CALL(visitor, OnRstStream(1, RST_STREAM_INVALID)); framer.ProcessInput( reinterpret_cast<const char*>(kV3RstStreamNumStatusCodes), arraysize(kV3RstStreamNumStatusCodes)); - } - EXPECT_EQ(SpdyFramer::SPDY_RESET, framer.state()); - EXPECT_EQ(SpdyFramer::SPDY_NO_ERROR, framer.error_code()) + EXPECT_EQ(SpdyFramer::SPDY_RESET, framer.state()); + EXPECT_EQ(SpdyFramer::SPDY_NO_ERROR, framer.error_code()) << SpdyFramer::ErrorCodeToString(framer.error_code()); + } } // Tests handling of a GOAWAY frame with out-of-bounds stream ID. diff --git a/net/spdy/spdy_protocol.cc b/net/spdy/spdy_protocol.cc index 02c74ef..b786797 100644 --- a/net/spdy/spdy_protocol.cc +++ b/net/spdy/spdy_protocol.cc @@ -49,6 +49,7 @@ bool SpdyConstants::IsValidFrameType(SpdyMajorVersion version, return true; case SPDY4: + case SPDY5: // DATA is the first valid frame. if (frame_type_field < SerializeFrameType(version, DATA)) { return false; @@ -91,6 +92,7 @@ SpdyFrameType SpdyConstants::ParseFrameType(SpdyMajorVersion version, } break; case SPDY4: + case SPDY5: switch (frame_type_field) { case 0: return DATA; @@ -148,6 +150,7 @@ int SpdyConstants::SerializeFrameType(SpdyMajorVersion version, return -1; } case SPDY4: + case SPDY5: switch (frame_type) { case DATA: return 0; @@ -199,6 +202,7 @@ bool SpdyConstants::IsValidSettingId(SpdyMajorVersion version, return true; case SPDY4: + case SPDY5: // HEADER_TABLE_SIZE is the first valid setting id. if (setting_id_field < SerializeSettingId(version, SETTINGS_HEADER_TABLE_SIZE)) { @@ -241,6 +245,7 @@ SpdySettingsIds SpdyConstants::ParseSettingId(SpdyMajorVersion version, } break; case SPDY4: + case SPDY5: switch (setting_id_field) { case 1: return SETTINGS_HEADER_TABLE_SIZE; @@ -283,6 +288,7 @@ int SpdyConstants::SerializeSettingId(SpdyMajorVersion version, return -1; } case SPDY4: + case SPDY5: switch (id) { case SETTINGS_HEADER_TABLE_SIZE: return 1; @@ -301,6 +307,405 @@ int SpdyConstants::SerializeSettingId(SpdyMajorVersion version, return -1; } +bool SpdyConstants::IsValidRstStreamStatus(SpdyMajorVersion version, + int rst_stream_status_field) { + switch (version) { + case SPDY2: + case SPDY3: + // PROTOCOL_ERROR is the valid first status code. + if (rst_stream_status_field < + SerializeRstStreamStatus(version, RST_STREAM_PROTOCOL_ERROR)) { + return false; + } + + // FRAME_TOO_LARGE is the valid last status code. + if (rst_stream_status_field > + SerializeRstStreamStatus(version, RST_STREAM_FRAME_TOO_LARGE)) { + return false; + } + + return true; + case SPDY4: + case SPDY5: + // NO_ERROR is the first valid status code. + if (rst_stream_status_field < + SerializeRstStreamStatus(version, RST_STREAM_PROTOCOL_ERROR)) { + return false; + } + + // TODO(hkhalil): Omit COMPRESSION_ERROR and SETTINGS_TIMEOUT + /* + // This works because GOAWAY and RST_STREAM share a namespace. + if (rst_stream_status_field == + SerializeGoAwayStatus(version, GOAWAY_COMPRESSION_ERROR) || + rst_stream_status_field == + SerializeGoAwayStatus(version, GOAWAY_SETTINGS_TIMEOUT)) { + return false; + } + */ + + // ENHANCE_YOUR_CALM is the last valid status code. + if (rst_stream_status_field > + SerializeRstStreamStatus(version, RST_STREAM_ENHANCE_YOUR_CALM)) { + return false; + } + + return true; + } + LOG(DFATAL) << "Unhandled SPDY version " << version; + return false; +} + +SpdyRstStreamStatus SpdyConstants::ParseRstStreamStatus( + SpdyMajorVersion version, + int rst_stream_status_field) { + switch (version) { + case SPDY2: + case SPDY3: + switch (rst_stream_status_field) { + case 1: + return RST_STREAM_PROTOCOL_ERROR; + case 2: + return RST_STREAM_INVALID_STREAM; + case 3: + return RST_STREAM_REFUSED_STREAM; + case 4: + return RST_STREAM_UNSUPPORTED_VERSION; + case 5: + return RST_STREAM_CANCEL; + case 6: + return RST_STREAM_INTERNAL_ERROR; + case 7: + return RST_STREAM_FLOW_CONTROL_ERROR; + case 8: + return RST_STREAM_STREAM_IN_USE; + case 9: + return RST_STREAM_STREAM_ALREADY_CLOSED; + case 10: + return RST_STREAM_INVALID_CREDENTIALS; + case 11: + return RST_STREAM_FRAME_TOO_LARGE; + } + break; + case SPDY4: + case SPDY5: + switch (rst_stream_status_field) { + case 1: + return RST_STREAM_PROTOCOL_ERROR; + case 2: + return RST_STREAM_INTERNAL_ERROR; + case 3: + return RST_STREAM_FLOW_CONTROL_ERROR; + case 5: + return RST_STREAM_STREAM_CLOSED; + case 6: + return RST_STREAM_FRAME_SIZE_ERROR; + case 7: + return RST_STREAM_REFUSED_STREAM; + case 8: + return RST_STREAM_CANCEL; + case 10: + return RST_STREAM_CONNECT_ERROR; + case 11: + return RST_STREAM_ENHANCE_YOUR_CALM; + } + break; + } + + LOG(DFATAL) << "Invalid RST_STREAM status " << rst_stream_status_field; + return RST_STREAM_PROTOCOL_ERROR; +} + +int SpdyConstants::SerializeRstStreamStatus( + SpdyMajorVersion version, + SpdyRstStreamStatus rst_stream_status) { + switch (version) { + case SPDY2: + case SPDY3: + switch (rst_stream_status) { + case RST_STREAM_PROTOCOL_ERROR: + return 1; + case RST_STREAM_INVALID_STREAM: + return 2; + case RST_STREAM_REFUSED_STREAM: + return 3; + case RST_STREAM_UNSUPPORTED_VERSION: + return 4; + case RST_STREAM_CANCEL: + return 5; + case RST_STREAM_INTERNAL_ERROR: + return 6; + case RST_STREAM_FLOW_CONTROL_ERROR: + return 7; + case RST_STREAM_STREAM_IN_USE: + return 8; + case RST_STREAM_STREAM_ALREADY_CLOSED: + return 9; + case RST_STREAM_INVALID_CREDENTIALS: + return 10; + case RST_STREAM_FRAME_TOO_LARGE: + return 11; + default: + LOG(DFATAL) << "Unhandled RST_STREAM status " + << rst_stream_status; + return -1; + } + case SPDY4: + case SPDY5: + switch (rst_stream_status) { + case RST_STREAM_PROTOCOL_ERROR: + return 1; + case RST_STREAM_INTERNAL_ERROR: + return 2; + case RST_STREAM_FLOW_CONTROL_ERROR: + return 3; + case RST_STREAM_STREAM_CLOSED: + return 5; + case RST_STREAM_FRAME_SIZE_ERROR: + return 6; + case RST_STREAM_REFUSED_STREAM: + return 7; + case RST_STREAM_CANCEL: + return 8; + case RST_STREAM_CONNECT_ERROR: + return 10; + case RST_STREAM_ENHANCE_YOUR_CALM: + return 11; + default: + LOG(DFATAL) << "Unhandled RST_STREAM status " + << rst_stream_status; + return -1; + } + } + LOG(DFATAL) << "Unhandled SPDY version " << version; + return -1; +} + +bool SpdyConstants::IsValidGoAwayStatus(SpdyMajorVersion version, + int goaway_status_field) { + switch (version) { + case SPDY2: + case SPDY3: + // GOAWAY_OK is the first valid status. + if (goaway_status_field < SerializeGoAwayStatus(version, GOAWAY_OK)) { + return false; + } + + // GOAWAY_INTERNAL_ERROR is the last valid status. + if (goaway_status_field > SerializeGoAwayStatus(version, + GOAWAY_INTERNAL_ERROR)) { + return false; + } + + return true; + case SPDY4: + case SPDY5: + // GOAWAY_NO_ERROR is the first valid status. + if (goaway_status_field < SerializeGoAwayStatus(version, + GOAWAY_NO_ERROR)) { + return false; + } + + // GOAWAY_INADEQUATE_SECURITY is the last valid status. + if (goaway_status_field > + SerializeGoAwayStatus(version, GOAWAY_INADEQUATE_SECURITY)) { + return false; + } + + return true; + } + LOG(DFATAL) << "Unknown SpdyMajorVersion " << version; + return false; +} + +SpdyGoAwayStatus SpdyConstants::ParseGoAwayStatus(SpdyMajorVersion version, + int goaway_status_field) { + switch (version) { + case SPDY2: + case SPDY3: + switch (goaway_status_field) { + case 0: + return GOAWAY_OK; + case 1: + return GOAWAY_PROTOCOL_ERROR; + case 2: + return GOAWAY_INTERNAL_ERROR; + } + break; + case SPDY4: + case SPDY5: + switch (goaway_status_field) { + case 0: + return GOAWAY_NO_ERROR; + case 1: + return GOAWAY_PROTOCOL_ERROR; + case 2: + return GOAWAY_INTERNAL_ERROR; + case 3: + return GOAWAY_FLOW_CONTROL_ERROR; + case 4: + return GOAWAY_SETTINGS_TIMEOUT; + case 5: + return GOAWAY_STREAM_CLOSED; + case 6: + return GOAWAY_FRAME_SIZE_ERROR; + case 7: + return GOAWAY_REFUSED_STREAM; + case 8: + return GOAWAY_CANCEL; + case 9: + return GOAWAY_COMPRESSION_ERROR; + case 10: + return GOAWAY_CONNECT_ERROR; + case 11: + return GOAWAY_ENHANCE_YOUR_CALM; + case 12: + return GOAWAY_INADEQUATE_SECURITY; + } + break; + } + + LOG(DFATAL) << "Unhandled GOAWAY status " << goaway_status_field; + return GOAWAY_PROTOCOL_ERROR; +} + +SpdyMajorVersion SpdyConstants::ParseMajorVersion(int version_number) { + switch (version_number) { + case 2: + return SPDY2; + case 3: + return SPDY3; + case 4: + return SPDY4; + case 5: + return SPDY5; + default: + LOG(DFATAL) << "Unsupported SPDY version number: " << version_number; + return SPDY3; + } +} + +int SpdyConstants::SerializeMajorVersion(SpdyMajorVersion version) { + switch (version) { + case SPDY2: + return 2; + case SPDY3: + return 3; + case SPDY4: + return 4; + case SPDY5: + return 5; + default: + LOG(DFATAL) << "Unsupported SPDY major version: " << version; + return -1; + } +} + +std::string SpdyConstants::GetVersionString(SpdyMajorVersion version) { + switch (version) { + case SPDY2: + return "spdy/2"; + case SPDY3: + return "spdy/3"; + case SPDY4: + return "spdy/4"; + case SPDY5: + return "spdy/5"; + default: + LOG(DFATAL) << "Unsupported SPDY major version: " << version; + return "spdy/3"; + } +} + +int SpdyConstants::SerializeGoAwayStatus(SpdyMajorVersion version, + SpdyGoAwayStatus status) { + switch (version) { + case SPDY2: + case SPDY3: + switch (status) { + case GOAWAY_OK: + return 0; + case GOAWAY_PROTOCOL_ERROR: + return 1; + case GOAWAY_INTERNAL_ERROR: + return 2; + default: + LOG(DFATAL) << "Serializing unhandled GOAWAY status " << status; + return -1; + } + case SPDY4: + case SPDY5: + switch (status) { + case GOAWAY_NO_ERROR: + return 0; + case GOAWAY_PROTOCOL_ERROR: + return 1; + case GOAWAY_INTERNAL_ERROR: + return 2; + case GOAWAY_FLOW_CONTROL_ERROR: + return 3; + case GOAWAY_SETTINGS_TIMEOUT: + return 4; + case GOAWAY_STREAM_CLOSED: + return 5; + case GOAWAY_FRAME_SIZE_ERROR: + return 6; + case GOAWAY_REFUSED_STREAM: + return 7; + case GOAWAY_CANCEL: + return 8; + case GOAWAY_COMPRESSION_ERROR: + return 9; + case GOAWAY_CONNECT_ERROR: + return 10; + case GOAWAY_ENHANCE_YOUR_CALM: + return 11; + case GOAWAY_INADEQUATE_SECURITY: + return 12; + default: + LOG(DFATAL) << "Serializing unhandled GOAWAY status " << status; + return -1; + } + } + LOG(DFATAL) << "Unknown SpdyMajorVersion " << version; + return -1; +} + +size_t SpdyConstants::GetDataFrameMinimumSize() { + return 8; +} + +size_t SpdyConstants::GetControlFrameHeaderSize(SpdyMajorVersion version) { + switch (version) { + case SPDY2: + case SPDY3: + case SPDY4: + case SPDY5: + return 8; + } + LOG(DFATAL) << "Unhandled SPDY version."; + return 0; +} + +size_t SpdyConstants::GetPrefixLength(SpdyFrameType type, + SpdyMajorVersion version) { + if (type != DATA) { + return GetControlFrameHeaderSize(version); + } else { + return GetDataFrameMinimumSize(); + } +} + +size_t SpdyConstants::GetFrameMaximumSize(SpdyMajorVersion version) { + if (version < SPDY4) { + // 24-bit length field plus eight-byte frame header. + return ((1<<24) - 1) + 8; + } else { + // 14-bit length field. + return (1<<14) - 1; + } +} + void SpdyDataIR::Visit(SpdyFrameVisitor* visitor) const { return visitor->VisitData(*this); } diff --git a/net/spdy/spdy_protocol.h b/net/spdy/spdy_protocol.h index 9696bf1..cc73977 100644 --- a/net/spdy/spdy_protocol.h +++ b/net/spdy/spdy_protocol.h @@ -28,14 +28,15 @@ namespace net { // The major versions of SPDY. Major version differences indicate // framer-layer incompatibility, as opposed to minor version numbers -// which indicate application-layer incompatibility. It is guaranteed -// that the enum value SPDYn maps to the integer n. +// which indicate application-layer incompatibility. Do not rely on +// the mapping from enum value SPDYn to the integer n. enum SpdyMajorVersion { SPDY2 = 2, SPDY_MIN_VERSION = SPDY2, SPDY3 = 3, SPDY4 = 4, - SPDY_MAX_VERSION = SPDY4 + SPDY5 = 5, + SPDY_MAX_VERSION = SPDY5 }; // A SPDY stream id is a 31 bit entity. @@ -360,6 +361,7 @@ enum SpdyRstStreamStatus { RST_STREAM_INVALID = 0, RST_STREAM_PROTOCOL_ERROR = 1, RST_STREAM_INVALID_STREAM = 2, + RST_STREAM_STREAM_CLOSED = 2, // Equivalent to INVALID_STREAM RST_STREAM_REFUSED_STREAM = 3, RST_STREAM_UNSUPPORTED_VERSION = 4, RST_STREAM_CANCEL = 5, @@ -368,17 +370,33 @@ enum SpdyRstStreamStatus { RST_STREAM_STREAM_IN_USE = 8, RST_STREAM_STREAM_ALREADY_CLOSED = 9, RST_STREAM_INVALID_CREDENTIALS = 10, + // FRAME_TOO_LARGE (defined by SPDY versions 3.1 and below), and + // FRAME_SIZE_ERROR (defined by HTTP/2) are mapped to the same internal + // reset status. RST_STREAM_FRAME_TOO_LARGE = 11, - RST_STREAM_NUM_STATUS_CODES = 12 + RST_STREAM_FRAME_SIZE_ERROR = 11, + RST_STREAM_SETTINGS_TIMEOUT = 12, + RST_STREAM_CONNECT_ERROR = 13, + RST_STREAM_ENHANCE_YOUR_CALM = 14, + RST_STREAM_NUM_STATUS_CODES = 15 }; // Status codes for GOAWAY frames. enum SpdyGoAwayStatus { - GOAWAY_INVALID = -1, GOAWAY_OK = 0, + GOAWAY_NO_ERROR = GOAWAY_OK, GOAWAY_PROTOCOL_ERROR = 1, GOAWAY_INTERNAL_ERROR = 2, - GOAWAY_NUM_STATUS_CODES = 3 // Must be last. + GOAWAY_FLOW_CONTROL_ERROR = 3, + GOAWAY_SETTINGS_TIMEOUT = 4, + GOAWAY_STREAM_CLOSED = 5, + GOAWAY_FRAME_SIZE_ERROR = 6, + GOAWAY_REFUSED_STREAM = 7, + GOAWAY_CANCEL = 8, + GOAWAY_COMPRESSION_ERROR = 9, + GOAWAY_CONNECT_ERROR = 10, + GOAWAY_ENHANCE_YOUR_CALM = 11, + GOAWAY_INADEQUATE_SECURITY = 12 }; // A SPDY priority is a number between 0 and 7 (inclusive). @@ -426,6 +444,62 @@ class NET_EXPORT_PRIVATE SpdyConstants { // given protocol version. // Returns -1 on failure (I.E. Invalid setting id for the given version). static int SerializeSettingId(SpdyMajorVersion version, SpdySettingsIds id); + + // Returns true if a given on-the-wire enumeration of a RST_STREAM status code + // is valid for a given protocol version, false otherwise. + static bool IsValidRstStreamStatus(SpdyMajorVersion version, + int rst_stream_status_field); + + // Parses a RST_STREAM status code from an on-the-wire enumeration of a given + // protocol version. + // Behavior is undefined for invalid RST_STREAM status code fields; consumers + // should first use IsValidRstStreamStatus() to verify validity of RST_STREAM + // status code fields.. + static SpdyRstStreamStatus ParseRstStreamStatus(SpdyMajorVersion version, + int rst_stream_status_field); + + // Serializes a given RST_STREAM status code to the on-the-wire enumeration + // value for the given protocol version. + // Returns -1 on failure (I.E. Invalid RST_STREAM status code for the given + // version). + static int SerializeRstStreamStatus(SpdyMajorVersion version, + SpdyRstStreamStatus rst_stream_status); + + // Returns true if a given on-the-wire enumeration of a GOAWAY status code is + // valid for the given protocol version, false otherwise. + static bool IsValidGoAwayStatus(SpdyMajorVersion version, + int goaway_status_field); + + // Parses a GOAWAY status from an on-the-wire enumeration of a given protocol + // version. + // Behavior is undefined for invalid GOAWAY status fields; consumers should + // first use IsValidGoAwayStatus() to verify validity of GOAWAY status fields. + static SpdyGoAwayStatus ParseGoAwayStatus(SpdyMajorVersion version, + int goaway_status_field); + + // Serializes a given GOAWAY status to the on-the-wire enumeration value for + // the given protocol version. + // Returns -1 on failure (I.E. Invalid GOAWAY status for the given version). + static int SerializeGoAwayStatus(SpdyMajorVersion version, + SpdyGoAwayStatus status); + + // Size, in bytes, of the data frame header. Future versions of SPDY + // will likely vary this, so we allow for the flexibility of a function call + // for this value as opposed to a constant. + static size_t GetDataFrameMinimumSize(); + + // Size, in bytes, of the control frame header. + static size_t GetControlFrameHeaderSize(SpdyMajorVersion version); + + static size_t GetPrefixLength(SpdyFrameType type, SpdyMajorVersion version); + + static size_t GetFrameMaximumSize(SpdyMajorVersion version); + + static SpdyMajorVersion ParseMajorVersion(int version_number); + + static int SerializeMajorVersion(SpdyMajorVersion version); + + static std::string GetVersionString(SpdyMajorVersion version); }; class SpdyFrame; @@ -636,8 +710,6 @@ class NET_EXPORT_PRIVATE SpdyRstStreamIR : public SpdyFrameWithStreamIdIR { return status_; } void set_status(SpdyRstStreamStatus status) { - DCHECK_NE(status, RST_STREAM_INVALID); - DCHECK_LT(status, RST_STREAM_NUM_STATUS_CODES); status_ = status; } diff --git a/net/spdy/spdy_protocol_test.cc b/net/spdy/spdy_protocol_test.cc index 5932328..b15783a 100644 --- a/net/spdy/spdy_protocol_test.cc +++ b/net/spdy/spdy_protocol_test.cc @@ -16,8 +16,8 @@ namespace { enum SpdyProtocolTestTypes { - SPDY2 = 2, - SPDY3 = 3, + SPDY2 = net::SPDY2, + SPDY3 = net::SPDY3, }; } // namespace @@ -28,11 +28,11 @@ class SpdyProtocolTest : public ::testing::TestWithParam<SpdyProtocolTestTypes> { protected: virtual void SetUp() { - spdy_version_ = GetParam(); + spdy_version_ = static_cast<SpdyMajorVersion>(GetParam()); } // Version of SPDY protocol to be used. - int spdy_version_; + SpdyMajorVersion spdy_version_; }; // All tests are run with two different SPDY versions: SPDY/2 and SPDY/3. diff --git a/net/spdy/spdy_session.cc b/net/spdy/spdy_session.cc index 17a6c4b..4c4900f 100644 --- a/net/spdy/spdy_session.cc +++ b/net/spdy/spdy_session.cc @@ -323,8 +323,14 @@ SpdyProtocolErrorDetails MapRstStreamStatusToProtocolError( return STATUS_CODE_STREAM_ALREADY_CLOSED; case RST_STREAM_INVALID_CREDENTIALS: return STATUS_CODE_INVALID_CREDENTIALS; - case RST_STREAM_FRAME_TOO_LARGE: - return STATUS_CODE_FRAME_TOO_LARGE; + case RST_STREAM_FRAME_SIZE_ERROR: + return STATUS_CODE_FRAME_SIZE_ERROR; + case RST_STREAM_SETTINGS_TIMEOUT: + return STATUS_CODE_SETTINGS_TIMEOUT; + case RST_STREAM_CONNECT_ERROR: + return STATUS_CODE_CONNECT_ERROR; + case RST_STREAM_ENHANCE_YOUR_CALM: + return STATUS_CODE_ENHANCE_YOUR_CALM; default: NOTREACHED(); return static_cast<SpdyProtocolErrorDetails>(-1); diff --git a/net/spdy/spdy_session.h b/net/spdy/spdy_session.h index 203f1ef..53eda74 100644 --- a/net/spdy/spdy_session.h +++ b/net/spdy/spdy_session.h @@ -95,7 +95,11 @@ enum SpdyProtocolErrorDetails { STATUS_CODE_STREAM_IN_USE = 18, STATUS_CODE_STREAM_ALREADY_CLOSED = 19, STATUS_CODE_INVALID_CREDENTIALS = 20, - STATUS_CODE_FRAME_TOO_LARGE = 21, + STATUS_CODE_FRAME_SIZE_ERROR = 21, + STATUS_CODE_SETTINGS_TIMEOUT = 32, + STATUS_CODE_CONNECT_ERROR = 33, + STATUS_CODE_ENHANCE_YOUR_CALM = 34, + // SpdySession errors PROTOCOL_ERROR_UNEXPECTED_PING = 22, PROTOCOL_ERROR_RST_STREAM_FOR_NON_ACTIVE_STREAM = 23, @@ -106,7 +110,7 @@ enum SpdyProtocolErrorDetails { PROTOCOL_ERROR_RECEIVE_WINDOW_VIOLATION = 28, // Next free value. - NUM_SPDY_PROTOCOL_ERROR_DETAILS = 32, + NUM_SPDY_PROTOCOL_ERROR_DETAILS = 35, }; SpdyProtocolErrorDetails NET_EXPORT_PRIVATE MapFramerErrorToProtocolError( SpdyFramer::SpdyError); @@ -117,7 +121,7 @@ SpdyProtocolErrorDetails NET_EXPORT_PRIVATE MapRstStreamStatusToProtocolError( // to be updated with new values, as do the mapping functions above. COMPILE_ASSERT(12 == SpdyFramer::LAST_ERROR, SpdyProtocolErrorDetails_SpdyErrors_mismatch); -COMPILE_ASSERT(12 == RST_STREAM_NUM_STATUS_CODES, +COMPILE_ASSERT(15 == RST_STREAM_NUM_STATUS_CODES, SpdyProtocolErrorDetails_RstStreamStatus_mismatch); // A helper class used to manage a request to create a stream. diff --git a/net/spdy/spdy_session_unittest.cc b/net/spdy/spdy_session_unittest.cc index 1d3ccb2..5978f93 100644 --- a/net/spdy/spdy_session_unittest.cc +++ b/net/spdy/spdy_session_unittest.cc @@ -4135,9 +4135,12 @@ TEST(MapRstStreamStatusToProtocolError, MapsValues) { CHECK_EQ(STATUS_CODE_PROTOCOL_ERROR, MapRstStreamStatusToProtocolError( RST_STREAM_PROTOCOL_ERROR)); - CHECK_EQ(STATUS_CODE_FRAME_TOO_LARGE, + CHECK_EQ(STATUS_CODE_FRAME_SIZE_ERROR, MapRstStreamStatusToProtocolError( - RST_STREAM_FRAME_TOO_LARGE)); + RST_STREAM_FRAME_SIZE_ERROR)); + CHECK_EQ(STATUS_CODE_ENHANCE_YOUR_CALM, + MapRstStreamStatusToProtocolError( + RST_STREAM_ENHANCE_YOUR_CALM)); } } // namespace net diff --git a/net/spdy/spdy_test_utils.cc b/net/spdy/spdy_test_utils.cc index e4063ea..a7cfc90 100644 --- a/net/spdy/spdy_test_utils.cc +++ b/net/spdy/spdy_test_utils.cc @@ -83,13 +83,16 @@ void CompareCharArraysWithHexError( << HexDumpWithMarks(actual, actual_len, marks.get(), max_len); } -void SetFrameFlags(SpdyFrame* frame, uint8 flags, int spdy_version) { +void SetFrameFlags(SpdyFrame* frame, + uint8 flags, + SpdyMajorVersion spdy_version) { switch (spdy_version) { - case 2: - case 3: + case SPDY2: + case SPDY3: frame->data()[4] = flags; break; - case 4: + case SPDY4: + case SPDY5: frame->data()[3] = flags; break; default: @@ -97,10 +100,12 @@ void SetFrameFlags(SpdyFrame* frame, uint8 flags, int spdy_version) { } } -void SetFrameLength(SpdyFrame* frame, size_t length, int spdy_version) { +void SetFrameLength(SpdyFrame* frame, + size_t length, + SpdyMajorVersion spdy_version) { switch (spdy_version) { - case 2: - case 3: + case SPDY2: + case SPDY3: CHECK_EQ(0u, length & ~kLengthMask); { int32 wire_length = base::HostToNet32(length); @@ -109,7 +114,8 @@ void SetFrameLength(SpdyFrame* frame, size_t length, int spdy_version) { memcpy(frame->data() + 5, reinterpret_cast<char*>(&wire_length) + 1, 3); } break; - case 4: + case SPDY4: + case SPDY5: CHECK_GT(1u<<14, length); { int32 wire_length = base::HostToNet16(static_cast<uint16>(length)); diff --git a/net/spdy/spdy_test_utils.h b/net/spdy/spdy_test_utils.h index b6e0393..920f1f7 100644 --- a/net/spdy/spdy_test_utils.h +++ b/net/spdy/spdy_test_utils.h @@ -23,9 +23,13 @@ void CompareCharArraysWithHexError( const unsigned char* expected, const int expected_len); -void SetFrameFlags(SpdyFrame* frame, uint8 flags, int spdy_version); +void SetFrameFlags(SpdyFrame* frame, + uint8 flags, + SpdyMajorVersion spdy_version); -void SetFrameLength(SpdyFrame* frame, size_t length, int spdy_version); +void SetFrameLength(SpdyFrame* frame, + size_t length, + SpdyMajorVersion spdy_version); } // namespace test diff --git a/net/tools/quic/spdy_utils.cc b/net/tools/quic/spdy_utils.cc index 0aa4638..c652322 100644 --- a/net/tools/quic/spdy_utils.cc +++ b/net/tools/quic/spdy_utils.cc @@ -158,7 +158,7 @@ string SpdyUtils::SerializeResponseHeaders( // static string SpdyUtils::SerializeUncompressedHeaders(const SpdyHeaderBlock& headers) { int length = SpdyFramer::GetSerializedLength(SPDY3, &headers); - SpdyFrameBuilder builder(length); + SpdyFrameBuilder builder(length, SPDY3); SpdyFramer::WriteHeaderBlock(&builder, SPDY3, &headers); scoped_ptr<SpdyFrame> block(builder.take()); return string(block->data(), length); diff --git a/tools/metrics/histograms/histograms.xml b/tools/metrics/histograms/histograms.xml index ae59bd0..3acb26f 100644 --- a/tools/metrics/histograms/histograms.xml +++ b/tools/metrics/histograms/histograms.xml @@ -40689,6 +40689,13 @@ Therefore, the affected-histogram name has to have at least one dot in it. <int value="29" label="GoAway Frame Corrupt"/> <int value="30" label="RstStream Frame Corrupt"/> <int value="31" label="Unexpected Frame (Expected Continuation)"/> +<!-- More SpdyRstStreamStatus --> + + <int value="32" label="Timeout waiting for settings acknowledgement"/> + <int value="33" + label="Connection established in response to CONNECT request was + abnormally closed"/> + <int value="34" label="Peer exhibiting suspect behavior."/> </enum> <enum name="SpdySessionGet" type="int"> |