1// Copyright 2014 The Chromium Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#include "net/spdy/hpack_encoder.h" 6 7#include <map> 8#include <string> 9 10#include "testing/gmock/include/gmock/gmock.h" 11#include "testing/gtest/include/gtest/gtest.h" 12 13namespace net { 14 15using base::StringPiece; 16using std::string; 17using testing::ElementsAre; 18 19namespace test { 20 21class HpackHeaderTablePeer { 22 public: 23 explicit HpackHeaderTablePeer(HpackHeaderTable* table) 24 : table_(table) {} 25 26 HpackHeaderTable::EntryTable* dynamic_entries() { 27 return &table_->dynamic_entries_; 28 } 29 30 private: 31 HpackHeaderTable* table_; 32}; 33 34class HpackEncoderPeer { 35 public: 36 typedef HpackEncoder::Representation Representation; 37 typedef HpackEncoder::Representations Representations; 38 39 explicit HpackEncoderPeer(HpackEncoder* encoder) 40 : encoder_(encoder) {} 41 42 HpackHeaderTable* table() { 43 return &encoder_->header_table_; 44 } 45 HpackHeaderTablePeer table_peer() { 46 return HpackHeaderTablePeer(table()); 47 } 48 bool allow_huffman_compression() { 49 return encoder_->allow_huffman_compression_; 50 } 51 void set_allow_huffman_compression(bool allow) { 52 encoder_->allow_huffman_compression_ = allow; 53 } 54 void EmitString(StringPiece str) { 55 encoder_->EmitString(str); 56 } 57 void TakeString(string* out) { 58 encoder_->output_stream_.TakeString(out); 59 } 60 void UpdateCharacterCounts(StringPiece str) { 61 encoder_->UpdateCharacterCounts(str); 62 } 63 static void CookieToCrumbs(StringPiece cookie, 64 std::vector<StringPiece>* out) { 65 Representations tmp; 66 HpackEncoder::CookieToCrumbs(make_pair("", cookie), &tmp); 67 68 out->clear(); 69 for (size_t i = 0; i != tmp.size(); ++i) { 70 out->push_back(tmp[i].second); 71 } 72 } 73 static void DecomposeRepresentation(StringPiece value, 74 std::vector<StringPiece>* out) { 75 Representations tmp; 76 HpackEncoder::DecomposeRepresentation(make_pair("foobar", value), &tmp); 77 78 out->clear(); 79 for (size_t i = 0; i != tmp.size(); ++i) { 80 out->push_back(tmp[i].second); 81 } 82 } 83 84 private: 85 HpackEncoder* encoder_; 86}; 87 88} // namespace test 89 90namespace { 91 92using std::map; 93using testing::ElementsAre; 94 95class HpackEncoderTest : public ::testing::Test { 96 protected: 97 typedef test::HpackEncoderPeer::Representations Representations; 98 99 HpackEncoderTest() 100 : encoder_(ObtainHpackHuffmanTable()), 101 peer_(&encoder_), 102 static_(peer_.table()->GetByIndex(1)) {} 103 104 virtual void SetUp() { 105 // Populate dynamic entries into the table fixture. For simplicity each 106 // entry has name.size() + value.size() == 10. 107 key_1_ = peer_.table()->TryAddEntry("key1", "value1"); 108 key_2_ = peer_.table()->TryAddEntry("key2", "value2"); 109 cookie_a_ = peer_.table()->TryAddEntry("cookie", "a=bb"); 110 cookie_c_ = peer_.table()->TryAddEntry("cookie", "c=dd"); 111 112 // No further insertions may occur without evictions. 113 peer_.table()->SetMaxSize(peer_.table()->size()); 114 115 // Disable Huffman coding by default. Most tests don't care about it. 116 peer_.set_allow_huffman_compression(false); 117 } 118 119 void ExpectIndex(size_t index) { 120 expected_.AppendPrefix(kIndexedOpcode); 121 expected_.AppendUint32(index); 122 } 123 void ExpectIndexedLiteral(const HpackEntry* key_entry, StringPiece value) { 124 expected_.AppendPrefix(kLiteralIncrementalIndexOpcode); 125 expected_.AppendUint32(IndexOf(key_entry)); 126 expected_.AppendPrefix(kStringLiteralIdentityEncoded); 127 expected_.AppendUint32(value.size()); 128 expected_.AppendBytes(value); 129 } 130 void ExpectIndexedLiteral(StringPiece name, StringPiece value) { 131 expected_.AppendPrefix(kLiteralIncrementalIndexOpcode); 132 expected_.AppendUint32(0); 133 expected_.AppendPrefix(kStringLiteralIdentityEncoded); 134 expected_.AppendUint32(name.size()); 135 expected_.AppendBytes(name); 136 expected_.AppendPrefix(kStringLiteralIdentityEncoded); 137 expected_.AppendUint32(value.size()); 138 expected_.AppendBytes(value); 139 } 140 void ExpectNonIndexedLiteral(StringPiece name, StringPiece value) { 141 expected_.AppendPrefix(kLiteralNoIndexOpcode); 142 expected_.AppendUint32(0); 143 expected_.AppendPrefix(kStringLiteralIdentityEncoded); 144 expected_.AppendUint32(name.size()); 145 expected_.AppendBytes(name); 146 expected_.AppendPrefix(kStringLiteralIdentityEncoded); 147 expected_.AppendUint32(value.size()); 148 expected_.AppendBytes(value); 149 } 150 void CompareWithExpectedEncoding(const map<string, string>& header_set) { 151 string expected_out, actual_out; 152 expected_.TakeString(&expected_out); 153 EXPECT_TRUE(encoder_.EncodeHeaderSet(header_set, &actual_out)); 154 EXPECT_EQ(expected_out, actual_out); 155 } 156 size_t IndexOf(HpackEntry* entry) { 157 return peer_.table()->IndexOf(entry); 158 } 159 size_t IndexOf(const HpackEntry* entry) { 160 return peer_.table()->IndexOf(entry); 161 } 162 163 HpackEncoder encoder_; 164 test::HpackEncoderPeer peer_; 165 166 const HpackEntry* static_; 167 const HpackEntry* key_1_; 168 const HpackEntry* key_2_; 169 const HpackEntry* cookie_a_; 170 const HpackEntry* cookie_c_; 171 172 HpackOutputStream expected_; 173}; 174 175TEST_F(HpackEncoderTest, SingleDynamicIndex) { 176 ExpectIndex(IndexOf(key_2_)); 177 178 map<string, string> headers; 179 headers[key_2_->name()] = key_2_->value(); 180 CompareWithExpectedEncoding(headers); 181} 182 183TEST_F(HpackEncoderTest, SingleStaticIndex) { 184 ExpectIndex(IndexOf(static_)); 185 186 map<string, string> headers; 187 headers[static_->name()] = static_->value(); 188 CompareWithExpectedEncoding(headers); 189} 190 191TEST_F(HpackEncoderTest, SingleStaticIndexTooLarge) { 192 peer_.table()->SetMaxSize(1); // Also evicts all fixtures. 193 ExpectIndex(IndexOf(static_)); 194 195 map<string, string> headers; 196 headers[static_->name()] = static_->value(); 197 CompareWithExpectedEncoding(headers); 198 199 EXPECT_EQ(0u, peer_.table_peer().dynamic_entries()->size()); 200} 201 202TEST_F(HpackEncoderTest, SingleLiteralWithIndexName) { 203 ExpectIndexedLiteral(key_2_, "value3"); 204 205 map<string, string> headers; 206 headers[key_2_->name()] = "value3"; 207 CompareWithExpectedEncoding(headers); 208 209 // A new entry was inserted and added to the reference set. 210 HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front(); 211 EXPECT_EQ(new_entry->name(), key_2_->name()); 212 EXPECT_EQ(new_entry->value(), "value3"); 213} 214 215TEST_F(HpackEncoderTest, SingleLiteralWithLiteralName) { 216 ExpectIndexedLiteral("key3", "value3"); 217 218 map<string, string> headers; 219 headers["key3"] = "value3"; 220 CompareWithExpectedEncoding(headers); 221 222 HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front(); 223 EXPECT_EQ(new_entry->name(), "key3"); 224 EXPECT_EQ(new_entry->value(), "value3"); 225} 226 227TEST_F(HpackEncoderTest, SingleLiteralTooLarge) { 228 peer_.table()->SetMaxSize(1); // Also evicts all fixtures. 229 230 ExpectIndexedLiteral("key3", "value3"); 231 232 // A header overflowing the header table is still emitted. 233 // The header table is empty. 234 map<string, string> headers; 235 headers["key3"] = "value3"; 236 CompareWithExpectedEncoding(headers); 237 238 EXPECT_EQ(0u, peer_.table_peer().dynamic_entries()->size()); 239} 240 241TEST_F(HpackEncoderTest, EmitThanEvict) { 242 // |key_1_| is toggled and placed into the reference set, 243 // and then immediately evicted by "key3". 244 ExpectIndex(IndexOf(key_1_)); 245 ExpectIndexedLiteral("key3", "value3"); 246 247 map<string, string> headers; 248 headers[key_1_->name()] = key_1_->value(); 249 headers["key3"] = "value3"; 250 CompareWithExpectedEncoding(headers); 251} 252 253TEST_F(HpackEncoderTest, CookieHeaderIsCrumbled) { 254 ExpectIndex(IndexOf(cookie_a_)); 255 ExpectIndex(IndexOf(cookie_c_)); 256 ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff"); 257 258 map<string, string> headers; 259 headers["cookie"] = "e=ff; a=bb; c=dd"; 260 CompareWithExpectedEncoding(headers); 261} 262 263TEST_F(HpackEncoderTest, StringsDynamicallySelectHuffmanCoding) { 264 peer_.set_allow_huffman_compression(true); 265 266 // Compactable string. Uses Huffman coding. 267 peer_.EmitString("feedbeef"); 268 expected_.AppendPrefix(kStringLiteralHuffmanEncoded); 269 expected_.AppendUint32(6); 270 expected_.AppendBytes("\x94\xA5\x92""2\x96_"); 271 272 // Non-compactable. Uses identity coding. 273 peer_.EmitString("@@@@@@"); 274 expected_.AppendPrefix(kStringLiteralIdentityEncoded); 275 expected_.AppendUint32(6); 276 expected_.AppendBytes("@@@@@@"); 277 278 string expected_out, actual_out; 279 expected_.TakeString(&expected_out); 280 peer_.TakeString(&actual_out); 281 EXPECT_EQ(expected_out, actual_out); 282} 283 284TEST_F(HpackEncoderTest, EncodingWithoutCompression) { 285 // Implementation should internally disable. 286 peer_.set_allow_huffman_compression(true); 287 288 ExpectNonIndexedLiteral(":path", "/index.html"); 289 ExpectNonIndexedLiteral("cookie", "foo=bar; baz=bing"); 290 ExpectNonIndexedLiteral("hello", "goodbye"); 291 292 map<string, string> headers; 293 headers[":path"] = "/index.html"; 294 headers["cookie"] = "foo=bar; baz=bing"; 295 headers["hello"] = "goodbye"; 296 297 string expected_out, actual_out; 298 expected_.TakeString(&expected_out); 299 encoder_.EncodeHeaderSetWithoutCompression(headers, &actual_out); 300 EXPECT_EQ(expected_out, actual_out); 301} 302 303TEST_F(HpackEncoderTest, MultipleEncodingPasses) { 304 // Pass 1. 305 { 306 map<string, string> headers; 307 headers["key1"] = "value1"; 308 headers["cookie"] = "a=bb"; 309 310 ExpectIndex(IndexOf(cookie_a_)); 311 ExpectIndex(IndexOf(key_1_)); 312 CompareWithExpectedEncoding(headers); 313 } 314 // Header table is: 315 // 65: key1: value1 316 // 64: key2: value2 317 // 63: cookie: a=bb 318 // 62: cookie: c=dd 319 // Pass 2. 320 { 321 map<string, string> headers; 322 headers["key1"] = "value1"; 323 headers["key2"] = "value2"; 324 headers["cookie"] = "c=dd; e=ff"; 325 326 ExpectIndex(IndexOf(cookie_c_)); 327 // key1 by index. 328 ExpectIndex(65); 329 // key2 by index. 330 ExpectIndex(64); 331 // This cookie evicts |key1| from the header table. 332 ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff"); 333 334 CompareWithExpectedEncoding(headers); 335 } 336 // Header table is: 337 // 65: key2: value2 338 // 64: cookie: a=bb 339 // 63: cookie: c=dd 340 // 62: cookie: e=ff 341 // Pass 3. 342 { 343 map<string, string> headers; 344 headers["key1"] = "value1"; 345 headers["key3"] = "value3"; 346 headers["cookie"] = "e=ff"; 347 348 // cookie: e=ff by index. 349 ExpectIndex(62); 350 ExpectIndexedLiteral("key1", "value1"); 351 ExpectIndexedLiteral("key3", "value3"); 352 353 CompareWithExpectedEncoding(headers); 354 } 355} 356 357TEST_F(HpackEncoderTest, PseudoHeadersFirst) { 358 map<string, string> headers; 359 // A pseudo-header to be indexed. 360 headers[":authority"] = "www.example.com"; 361 // A pseudo-header that should not be indexed. 362 headers[":path"] = "/spam/eggs.html"; 363 // A regular header which precedes ":" alphabetically, should still be encoded 364 // after pseudo-headers. 365 headers["-foo"] = "bar"; 366 headers["foo"] = "bar"; 367 headers["cookie"] = "c=dd"; 368 369 // Pseudo-headers are encoded in alphabetical order. 370 ExpectIndexedLiteral(peer_.table()->GetByName(":authority"), 371 "www.example.com"); 372 ExpectNonIndexedLiteral(":path", "/spam/eggs.html"); 373 // Regular headers in the header table are encoded first. 374 ExpectIndex(IndexOf(cookie_a_)); 375 // Regular headers not in the header table are encoded, in alphabetical order. 376 ExpectIndexedLiteral("-foo", "bar"); 377 ExpectIndexedLiteral("foo", "bar"); 378 CompareWithExpectedEncoding(headers); 379} 380 381TEST_F(HpackEncoderTest, CookieToCrumbs) { 382 test::HpackEncoderPeer peer(NULL); 383 std::vector<StringPiece> out; 384 385 // A space after ';' is consumed. All other spaces remain. ';' at beginning 386 // and end of string produce empty crumbs. Duplicate crumbs are removed. 387 // See section 8.1.3.4 "Compressing the Cookie Header Field" in the HTTP/2 388 // specification at http://tools.ietf.org/html/draft-ietf-httpbis-http2-11 389 peer.CookieToCrumbs(" foo=1;bar=2 ; bar=3; bing=4; ", &out); 390 EXPECT_THAT(out, ElementsAre("", " bing=4", " foo=1", "bar=2 ", "bar=3")); 391 392 peer.CookieToCrumbs(";;foo = bar ;; ;baz =bing", &out); 393 EXPECT_THAT(out, ElementsAre("", "baz =bing", "foo = bar ")); 394 395 peer.CookieToCrumbs("baz=bing; foo=bar; baz=bing", &out); 396 EXPECT_THAT(out, ElementsAre("baz=bing", "foo=bar")); 397 398 peer.CookieToCrumbs("baz=bing", &out); 399 EXPECT_THAT(out, ElementsAre("baz=bing")); 400 401 peer.CookieToCrumbs("", &out); 402 EXPECT_THAT(out, ElementsAre("")); 403 404 peer.CookieToCrumbs("foo;bar; baz;baz;bing;", &out); 405 EXPECT_THAT(out, ElementsAre("", "bar", "baz", "bing", "foo")); 406} 407 408TEST_F(HpackEncoderTest, UpdateCharacterCounts) { 409 std::vector<size_t> counts(256, 0); 410 size_t total_counts = 0; 411 encoder_.SetCharCountsStorage(&counts, &total_counts); 412 413 char kTestString[] = "foo\0\1\xff""boo"; 414 peer_.UpdateCharacterCounts( 415 StringPiece(kTestString, arraysize(kTestString) - 1)); 416 417 std::vector<size_t> expect(256, 0); 418 expect[static_cast<uint8>('f')] = 1; 419 expect[static_cast<uint8>('o')] = 4; 420 expect[static_cast<uint8>('\0')] = 1; 421 expect[static_cast<uint8>('\1')] = 1; 422 expect[static_cast<uint8>('\xff')] = 1; 423 expect[static_cast<uint8>('b')] = 1; 424 425 EXPECT_EQ(expect, counts); 426 EXPECT_EQ(9u, total_counts); 427} 428 429TEST_F(HpackEncoderTest, DecomposeRepresentation) { 430 test::HpackEncoderPeer peer(NULL); 431 std::vector<StringPiece> out; 432 433 peer.DecomposeRepresentation("", &out); 434 EXPECT_THAT(out, ElementsAre("")); 435 436 peer.DecomposeRepresentation("foobar", &out); 437 EXPECT_THAT(out, ElementsAre("foobar")); 438 439 peer.DecomposeRepresentation(StringPiece("foo\0bar", 7), &out); 440 EXPECT_THAT(out, ElementsAre("foo", "bar")); 441 442 peer.DecomposeRepresentation(StringPiece("\0foo\0bar", 8), &out); 443 EXPECT_THAT(out, ElementsAre("", "foo", "bar")); 444 445 peer.DecomposeRepresentation(StringPiece("foo\0bar\0", 8), &out); 446 EXPECT_THAT(out, ElementsAre("foo", "bar", "")); 447 448 peer.DecomposeRepresentation(StringPiece("\0foo\0bar\0", 9), &out); 449 EXPECT_THAT(out, ElementsAre("", "foo", "bar", "")); 450} 451 452// Test that encoded headers do not have \0-delimited multiple values, as this 453// became disallowed in HTTP/2 draft-14. 454TEST_F(HpackEncoderTest, CrumbleNullByteDelimitedValue) { 455 map<string, string> headers; 456 // A header field to be crumbled: "spam: foo\0bar". 457 headers["spam"] = string("foo\0bar", 7); 458 459 ExpectIndexedLiteral("spam", "foo"); 460 expected_.AppendPrefix(kLiteralIncrementalIndexOpcode); 461 expected_.AppendUint32(62); 462 expected_.AppendPrefix(kStringLiteralIdentityEncoded); 463 expected_.AppendUint32(3); 464 expected_.AppendBytes("bar"); 465 CompareWithExpectedEncoding(headers); 466} 467 468} // namespace 469 470} // namespace net 471