src/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   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
  74  private:
  75   HpackEncoder* encoder_;
  76 };
  77
  78 }  // namespace test
  79
  80 namespace {
  81
  82 using std::map;
  83 using testing::ElementsAre;
  84
  85 class HpackEncoderTest : public ::testing::Test {
  86  protected:
  87   typedef test::HpackEncoderPeer::Representations Representations;
  88
  89   HpackEncoderTest()
  90       : encoder_(ObtainHpackHuffmanTable()),
  91         peer_(&encoder_) {}
  92
  93   virtual void SetUp() {
  94     static_ = peer_.table()->GetByIndex(1);
  95     // Populate dynamic entries into the table fixture. For simplicity each
  96     // entry has name.size() + value.size() == 10.
  97     key_1_ = peer_.table()->TryAddEntry("key1", "value1");
  98     key_2_ = peer_.table()->TryAddEntry("key2", "value2");
  99     cookie_a_ = peer_.table()->TryAddEntry("cookie", "a=bb");
 100     cookie_c_ = peer_.table()->TryAddEntry("cookie", "c=dd");
 101
 102     // No further insertions may occur without evictions.
 103     peer_.table()->SetMaxSize(peer_.table()->size());
 104
 105     // Disable Huffman coding by default. Most tests don't care about it.
 106     peer_.set_allow_huffman_compression(false);
 107   }
 108
 109   void ExpectIndex(size_t index) {
 110     expected_.AppendPrefix(kIndexedOpcode);
 111     expected_.AppendUint32(index);
 112   }
 113   void ExpectIndexedLiteral(HpackEntry* key_entry, StringPiece value) {
 114     expected_.AppendPrefix(kLiteralIncrementalIndexOpcode);
 115     expected_.AppendUint32(key_entry->Index());
 116     expected_.AppendPrefix(kStringLiteralIdentityEncoded);
 117     expected_.AppendUint32(value.size());
 118     expected_.AppendBytes(value);
 119   }
 120   void ExpectIndexedLiteral(StringPiece name, StringPiece value) {
 121     expected_.AppendPrefix(kLiteralIncrementalIndexOpcode);
 122     expected_.AppendUint32(0);
 123     expected_.AppendPrefix(kStringLiteralIdentityEncoded);
 124     expected_.AppendUint32(name.size());
 125     expected_.AppendBytes(name);
 126     expected_.AppendPrefix(kStringLiteralIdentityEncoded);
 127     expected_.AppendUint32(value.size());
 128     expected_.AppendBytes(value);
 129   }
 130   void ExpectNonIndexedLiteral(StringPiece name, StringPiece value) {
 131     expected_.AppendPrefix(kLiteralNoIndexOpcode);
 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 CompareWithExpectedEncoding(const map<string, string>& header_set) {
 141     string expected_out, actual_out;
 142     expected_.TakeString(&expected_out);
 143     EXPECT_TRUE(encoder_.EncodeHeaderSet(header_set, &actual_out));
 144     EXPECT_EQ(expected_out, actual_out);
 145   }
 146
 147   HpackEncoder encoder_;
 148   test::HpackEncoderPeer peer_;
 149
 150   HpackEntry* static_;
 151   HpackEntry* key_1_;
 152   HpackEntry* key_2_;
 153   HpackEntry* cookie_a_;
 154   HpackEntry* cookie_c_;
 155
 156   HpackOutputStream expected_;
 157 };
 158
 159 TEST_F(HpackEncoderTest, SingleDynamicIndex) {
 160   ExpectIndex(key_2_->Index());
 161
 162   map<string, string> headers;
 163   headers[key_2_->name()] = key_2_->value();
 164   CompareWithExpectedEncoding(headers);
 165
 166   // |key_2_| was added to the reference set.
 167   EXPECT_THAT(peer_.table()->reference_set(), ElementsAre(key_2_));
 168 }
 169
 170 TEST_F(HpackEncoderTest, SingleStaticIndex) {
 171   ExpectIndex(static_->Index());
 172
 173   map<string, string> headers;
 174   headers[static_->name()] = static_->value();
 175   CompareWithExpectedEncoding(headers);
 176
 177   // A new entry copying |static_| was inserted and added to the reference set.
 178   HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front();
 179   EXPECT_NE(static_, new_entry);
 180   EXPECT_EQ(static_->name(), new_entry->name());
 181   EXPECT_EQ(static_->value(), new_entry->value());
 182   EXPECT_THAT(peer_.table()->reference_set(), ElementsAre(new_entry));
 183 }
 184
 185 TEST_F(HpackEncoderTest, SingleStaticIndexTooLarge) {
 186   peer_.table()->SetMaxSize(1);  // Also evicts all fixtures.
 187   ExpectIndex(static_->Index());
 188
 189   map<string, string> headers;
 190   headers[static_->name()] = static_->value();
 191   CompareWithExpectedEncoding(headers);
 192
 193   EXPECT_EQ(0u, peer_.table_peer().dynamic_entries()->size());
 194   EXPECT_EQ(0u, peer_.table()->reference_set().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   EXPECT_THAT(peer_.table()->reference_set(), ElementsAre(new_entry));
 209 }
 210
 211 TEST_F(HpackEncoderTest, SingleLiteralWithLiteralName) {
 212   ExpectIndexedLiteral("key3", "value3");
 213
 214   map<string, string> headers;
 215   headers["key3"] = "value3";
 216   CompareWithExpectedEncoding(headers);
 217
 218   // A new entry was inserted and added to the reference set.
 219   HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front();
 220   EXPECT_EQ(new_entry->name(), "key3");
 221   EXPECT_EQ(new_entry->value(), "value3");
 222   EXPECT_THAT(peer_.table()->reference_set(), ElementsAre(new_entry));
 223 }
 224
 225 TEST_F(HpackEncoderTest, SingleLiteralTooLarge) {
 226   peer_.table()->SetMaxSize(1);  // Also evicts all fixtures.
 227
 228   ExpectIndexedLiteral("key3", "value3");
 229
 230   // A header overflowing the header table is still emitted.
 231   // The header table is empty.
 232   map<string, string> headers;
 233   headers["key3"] = "value3";
 234   CompareWithExpectedEncoding(headers);
 235
 236   EXPECT_EQ(0u, peer_.table_peer().dynamic_entries()->size());
 237   EXPECT_EQ(0u, peer_.table()->reference_set().size());
 238 }
 239
 240 TEST_F(HpackEncoderTest, SingleInReferenceSet) {
 241   peer_.table()->Toggle(key_2_);
 242
 243   // Nothing is emitted.
 244   map<string, string> headers;
 245   headers[key_2_->name()] = key_2_->value();
 246   CompareWithExpectedEncoding(headers);
 247 }
 248
 249 TEST_F(HpackEncoderTest, ExplicitToggleOff) {
 250   peer_.table()->Toggle(key_1_);
 251   peer_.table()->Toggle(key_2_);
 252
 253   // |key_1_| is explicitly toggled off.
 254   ExpectIndex(key_1_->Index());
 255
 256   map<string, string> headers;
 257   headers[key_2_->name()] = key_2_->value();
 258   CompareWithExpectedEncoding(headers);
 259 }
 260
 261 TEST_F(HpackEncoderTest, ImplicitToggleOff) {
 262   peer_.table()->Toggle(key_1_);
 263   peer_.table()->Toggle(key_2_);
 264
 265   // |key_1_| is evicted. No explicit toggle required.
 266   ExpectIndexedLiteral("key3", "value3");
 267
 268   map<string, string> headers;
 269   headers[key_2_->name()] = key_2_->value();
 270   headers["key3"] = "value3";
 271   CompareWithExpectedEncoding(headers);
 272 }
 273
 274 TEST_F(HpackEncoderTest, ExplicitDoubleToggle) {
 275   peer_.table()->Toggle(key_1_);
 276
 277   // |key_1_| is double-toggled prior to being evicted.
 278   ExpectIndex(key_1_->Index());
 279   ExpectIndex(key_1_->Index());
 280   ExpectIndexedLiteral("key3", "value3");
 281
 282   map<string, string> headers;
 283   headers[key_1_->name()] = key_1_->value();
 284   headers["key3"] = "value3";
 285   CompareWithExpectedEncoding(headers);
 286 }
 287
 288 TEST_F(HpackEncoderTest, EmitThanEvict) {
 289   // |key_1_| is toggled and placed into the reference set,
 290   // and then immediately evicted by "key3".
 291   ExpectIndex(key_1_->Index());
 292   ExpectIndexedLiteral("key3", "value3");
 293
 294   map<string, string> headers;
 295   headers[key_1_->name()] = key_1_->value();
 296   headers["key3"] = "value3";
 297   CompareWithExpectedEncoding(headers);
 298 }
 299
 300 TEST_F(HpackEncoderTest, CookieHeaderIsCrumbled) {
 301   peer_.table()->Toggle(cookie_a_);
 302
 303   // |cookie_a_| is already in the reference set. |cookie_c_| is
 304   // toggled, and "e=ff" is emitted with an indexed name.
 305   ExpectIndex(cookie_c_->Index());
 306   ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff");
 307
 308   map<string, string> headers;
 309   headers["cookie"] = "e=ff; a=bb; c=dd";
 310   CompareWithExpectedEncoding(headers);
 311 }
 312
 313 TEST_F(HpackEncoderTest, StringsDynamicallySelectHuffmanCoding) {
 314   peer_.set_allow_huffman_compression(true);
 315
 316   // Compactable string. Uses Huffman coding.
 317   peer_.EmitString("feedbeef");
 318   expected_.AppendPrefix(kStringLiteralHuffmanEncoded);
 319   expected_.AppendUint32(5);
 320   expected_.AppendBytes("\xC4G\v\xC4q");
 321
 322   // Non-compactable. Uses identity coding.
 323   peer_.EmitString("@@@@@@");
 324   expected_.AppendPrefix(kStringLiteralIdentityEncoded);
 325   expected_.AppendUint32(6);
 326   expected_.AppendBytes("@@@@@@");
 327
 328   string expected_out, actual_out;
 329   expected_.TakeString(&expected_out);
 330   peer_.TakeString(&actual_out);
 331   EXPECT_EQ(expected_out, actual_out);
 332 }
 333
 334 TEST_F(HpackEncoderTest, EncodingWithoutCompression) {
 335   // Implementation should internally disable.
 336   peer_.set_allow_huffman_compression(true);
 337
 338   ExpectNonIndexedLiteral(":path", "/index.html");
 339   ExpectNonIndexedLiteral("cookie", "foo=bar; baz=bing");
 340   ExpectNonIndexedLiteral("hello", "goodbye");
 341
 342   map<string, string> headers;
 343   headers[":path"] = "/index.html";
 344   headers["cookie"] = "foo=bar; baz=bing";
 345   headers["hello"] = "goodbye";
 346
 347   string expected_out, actual_out;
 348   expected_.TakeString(&expected_out);
 349   encoder_.EncodeHeaderSetWithoutCompression(headers, &actual_out);
 350   EXPECT_EQ(expected_out, actual_out);
 351 }
 352
 353 TEST_F(HpackEncoderTest, MultipleEncodingPasses) {
 354   // Pass 1: key_1_ and cookie_a_ are toggled on.
 355   {
 356     map<string, string> headers;
 357     headers["key1"] = "value1";
 358     headers["cookie"] = "a=bb";
 359
 360     ExpectIndex(cookie_a_->Index());
 361     ExpectIndex(key_1_->Index());
 362     CompareWithExpectedEncoding(headers);
 363   }
 364   // Pass 2: |key_1_| is double-toggled and evicted.
 365   // |key_2_| & |cookie_c_| are toggled on.
 366   // |cookie_a_| is toggled off.
 367   // A new cookie entry is added.
 368   {
 369     map<string, string> headers;
 370     headers["key1"] = "value1";
 371     headers["key2"] = "value2";
 372     headers["cookie"] = "c=dd; e=ff";
 373
 374     ExpectIndex(cookie_c_->Index());  // Toggle on.
 375     ExpectIndex(key_1_->Index());  // Double-toggle before eviction.
 376     ExpectIndex(key_1_->Index());
 377     ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff");
 378     ExpectIndex(key_2_->Index() + 1);  // Toggle on. Add 1 to reflect insertion.
 379     ExpectIndex(cookie_a_->Index() + 1);  // Toggle off.
 380     CompareWithExpectedEncoding(headers);
 381   }
 382   // Pass 3: |key_2_| is evicted and implicitly toggled off.
 383   // |cookie_c_| is explicitly toggled off.
 384   // "key1" is re-inserted.
 385   {
 386     map<string, string> headers;
 387     headers["key1"] = "value1";
 388     headers["key3"] = "value3";
 389     headers["cookie"] = "e=ff";
 390
 391     ExpectIndexedLiteral("key1", "value1");
 392     ExpectIndexedLiteral("key3", "value3");
 393     ExpectIndex(cookie_c_->Index() + 2);  // Toggle off. Add 1 for insertion.
 394
 395     CompareWithExpectedEncoding(headers);
 396   }
 397 }
 398
 399 TEST_F(HpackEncoderTest, CookieToCrumbs) {
 400   test::HpackEncoderPeer peer(NULL);
 401   std::vector<StringPiece> out;
 402
 403   // A space after ';' is consumed. All other spaces remain. ';' at beginning
 404   // and end of string produce empty crumbs. Duplicate crumbs are removed.
 405   // See section 8.1.3.4 "Compressing the Cookie Header Field" in the HTTP/2
 406   // specification at http://tools.ietf.org/html/draft-ietf-httpbis-http2-11
 407   peer.CookieToCrumbs(" foo=1;bar=2 ; bar=3;  bing=4; ", &out);
 408   EXPECT_THAT(out, ElementsAre("", " bing=4", " foo=1", "bar=2 ", "bar=3"));
 409
 410   peer.CookieToCrumbs(";;foo = bar ;; ;baz =bing", &out);
 411   EXPECT_THAT(out, ElementsAre("", "baz =bing", "foo = bar "));
 412
 413   peer.CookieToCrumbs("baz=bing; foo=bar; baz=bing", &out);
 414   EXPECT_THAT(out, ElementsAre("baz=bing", "foo=bar"));
 415
 416   peer.CookieToCrumbs("baz=bing", &out);
 417   EXPECT_THAT(out, ElementsAre("baz=bing"));
 418
 419   peer.CookieToCrumbs("", &out);
 420   EXPECT_THAT(out, ElementsAre(""));
 421
 422   peer.CookieToCrumbs("foo;bar; baz;baz;bing;", &out);
 423   EXPECT_THAT(out, ElementsAre("", "bar", "baz", "bing", "foo"));
 424 }
 425
 426 TEST_F(HpackEncoderTest, UpdateCharacterCounts) {
 427   std::vector<size_t> counts(256, 0);
 428   size_t total_counts = 0;
 429   encoder_.SetCharCountsStorage(&counts, &total_counts);
 430
 431   char kTestString[] = "foo\0\1\xff""boo";
 432   peer_.UpdateCharacterCounts(
 433       StringPiece(kTestString, arraysize(kTestString) - 1));
 434
 435   std::vector<size_t> expect(256, 0);
 436   expect[static_cast<uint8>('f')] = 1;
 437   expect[static_cast<uint8>('o')] = 4;
 438   expect[static_cast<uint8>('\0')] = 1;
 439   expect[static_cast<uint8>('\1')] = 1;
 440   expect[static_cast<uint8>('\xff')] = 1;
 441   expect[static_cast<uint8>('b')] = 1;
 442
 443   EXPECT_EQ(expect, counts);
 444   EXPECT_EQ(9u, total_counts);
 445 }
 446
 447 }  // namespace
 448
 449 }  // namespace net