net/spdy/hpack_encoder_test.cc

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