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(IndexOf(key_entry));
 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   size_t IndexOf(HpackEntry* entry) {
 147     return peer_.table()->IndexOf(entry);
 148   }
 149
 150   HpackEncoder encoder_;
 151   test::HpackEncoderPeer peer_;
 152
 153   HpackEntry* static_;
 154   HpackEntry* key_1_;
 155   HpackEntry* key_2_;
 156   HpackEntry* cookie_a_;
 157   HpackEntry* cookie_c_;
 158
 159   HpackOutputStream expected_;
 160 };
 161
 162 TEST_F(HpackEncoderTest, SingleDynamicIndex) {
 163   ExpectIndex(IndexOf(key_2_));
 164
 165   map<string, string> headers;
 166   headers[key_2_->name()] = key_2_->value();
 167   CompareWithExpectedEncoding(headers);
 168
 169   // |key_2_| was added to the reference set.
 170   EXPECT_THAT(peer_.table()->reference_set(), ElementsAre(key_2_));
 171 }
 172
 173 TEST_F(HpackEncoderTest, SingleStaticIndex) {
 174   ExpectIndex(IndexOf(static_));
 175
 176   map<string, string> headers;
 177   headers[static_->name()] = static_->value();
 178   CompareWithExpectedEncoding(headers);
 179
 180   // A new entry copying |static_| was inserted and added to the reference set.
 181   HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front();
 182   EXPECT_NE(static_, new_entry);
 183   EXPECT_EQ(static_->name(), new_entry->name());
 184   EXPECT_EQ(static_->value(), new_entry->value());
 185   EXPECT_THAT(peer_.table()->reference_set(), ElementsAre(new_entry));
 186 }
 187
 188 TEST_F(HpackEncoderTest, SingleStaticIndexTooLarge) {
 189   peer_.table()->SetMaxSize(1);  // Also evicts all fixtures.
 190   ExpectIndex(IndexOf(static_));
 191
 192   map<string, string> headers;
 193   headers[static_->name()] = static_->value();
 194   CompareWithExpectedEncoding(headers);
 195
 196   EXPECT_EQ(0u, peer_.table_peer().dynamic_entries()->size());
 197   EXPECT_EQ(0u, peer_.table()->reference_set().size());
 198 }
 199
 200 TEST_F(HpackEncoderTest, SingleLiteralWithIndexName) {
 201   ExpectIndexedLiteral(key_2_, "value3");
 202
 203   map<string, string> headers;
 204   headers[key_2_->name()] = "value3";
 205   CompareWithExpectedEncoding(headers);
 206
 207   // A new entry was inserted and added to the reference set.
 208   HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front();
 209   EXPECT_EQ(new_entry->name(), key_2_->name());
 210   EXPECT_EQ(new_entry->value(), "value3");
 211   EXPECT_THAT(peer_.table()->reference_set(), ElementsAre(new_entry));
 212 }
 213
 214 TEST_F(HpackEncoderTest, SingleLiteralWithLiteralName) {
 215   ExpectIndexedLiteral("key3", "value3");
 216
 217   map<string, string> headers;
 218   headers["key3"] = "value3";
 219   CompareWithExpectedEncoding(headers);
 220
 221   // A new entry was inserted and added to the reference set.
 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   EXPECT_THAT(peer_.table()->reference_set(), ElementsAre(new_entry));
 226 }
 227
 228 TEST_F(HpackEncoderTest, SingleLiteralTooLarge) {
 229   peer_.table()->SetMaxSize(1);  // Also evicts all fixtures.
 230
 231   ExpectIndexedLiteral("key3", "value3");
 232
 233   // A header overflowing the header table is still emitted.
 234   // The header table is empty.
 235   map<string, string> headers;
 236   headers["key3"] = "value3";
 237   CompareWithExpectedEncoding(headers);
 238
 239   EXPECT_EQ(0u, peer_.table_peer().dynamic_entries()->size());
 240   EXPECT_EQ(0u, peer_.table()->reference_set().size());
 241 }
 242
 243 TEST_F(HpackEncoderTest, SingleInReferenceSet) {
 244   peer_.table()->Toggle(key_2_);
 245
 246   // Nothing is emitted.
 247   map<string, string> headers;
 248   headers[key_2_->name()] = key_2_->value();
 249   CompareWithExpectedEncoding(headers);
 250 }
 251
 252 TEST_F(HpackEncoderTest, ExplicitToggleOff) {
 253   peer_.table()->Toggle(key_1_);
 254   peer_.table()->Toggle(key_2_);
 255
 256   // |key_1_| is explicitly toggled off.
 257   ExpectIndex(IndexOf(key_1_));
 258
 259   map<string, string> headers;
 260   headers[key_2_->name()] = key_2_->value();
 261   CompareWithExpectedEncoding(headers);
 262 }
 263
 264 TEST_F(HpackEncoderTest, ImplicitToggleOff) {
 265   peer_.table()->Toggle(key_1_);
 266   peer_.table()->Toggle(key_2_);
 267
 268   // |key_1_| is evicted. No explicit toggle required.
 269   ExpectIndexedLiteral("key3", "value3");
 270
 271   map<string, string> headers;
 272   headers[key_2_->name()] = key_2_->value();
 273   headers["key3"] = "value3";
 274   CompareWithExpectedEncoding(headers);
 275 }
 276
 277 TEST_F(HpackEncoderTest, ExplicitDoubleToggle) {
 278   peer_.table()->Toggle(key_1_);
 279
 280   // |key_1_| is double-toggled prior to being evicted.
 281   ExpectIndex(IndexOf(key_1_));
 282   ExpectIndex(IndexOf(key_1_));
 283   ExpectIndexedLiteral("key3", "value3");
 284
 285   map<string, string> headers;
 286   headers[key_1_->name()] = key_1_->value();
 287   headers["key3"] = "value3";
 288   CompareWithExpectedEncoding(headers);
 289 }
 290
 291 TEST_F(HpackEncoderTest, EmitThanEvict) {
 292   // |key_1_| is toggled and placed into the reference set,
 293   // and then immediately evicted by "key3".
 294   ExpectIndex(IndexOf(key_1_));
 295   ExpectIndexedLiteral("key3", "value3");
 296
 297   map<string, string> headers;
 298   headers[key_1_->name()] = key_1_->value();
 299   headers["key3"] = "value3";
 300   CompareWithExpectedEncoding(headers);
 301 }
 302
 303 TEST_F(HpackEncoderTest, CookieHeaderIsCrumbled) {
 304   peer_.table()->Toggle(cookie_a_);
 305
 306   // |cookie_a_| is already in the reference set. |cookie_c_| is
 307   // toggled, and "e=ff" is emitted with an indexed name.
 308   ExpectIndex(IndexOf(cookie_c_));
 309   ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff");
 310
 311   map<string, string> headers;
 312   headers["cookie"] = "e=ff; a=bb; c=dd";
 313   CompareWithExpectedEncoding(headers);
 314 }
 315
 316 TEST_F(HpackEncoderTest, StringsDynamicallySelectHuffmanCoding) {
 317   peer_.set_allow_huffman_compression(true);
 318
 319   // Compactable string. Uses Huffman coding.
 320   peer_.EmitString("feedbeef");
 321   expected_.AppendPrefix(kStringLiteralHuffmanEncoded);
 322   expected_.AppendUint32(6);
 323   expected_.AppendBytes("\xE0\xB5\xD3\xBDk\xE1");
 324
 325   // Non-compactable. Uses identity coding.
 326   peer_.EmitString("@@@@@@");
 327   expected_.AppendPrefix(kStringLiteralIdentityEncoded);
 328   expected_.AppendUint32(6);
 329   expected_.AppendBytes("@@@@@@");
 330
 331   string expected_out, actual_out;
 332   expected_.TakeString(&expected_out);
 333   peer_.TakeString(&actual_out);
 334   EXPECT_EQ(expected_out, actual_out);
 335 }
 336
 337 TEST_F(HpackEncoderTest, EncodingWithoutCompression) {
 338   // Implementation should internally disable.
 339   peer_.set_allow_huffman_compression(true);
 340
 341   ExpectNonIndexedLiteral(":path", "/index.html");
 342   ExpectNonIndexedLiteral("cookie", "foo=bar; baz=bing");
 343   ExpectNonIndexedLiteral("hello", "goodbye");
 344
 345   map<string, string> headers;
 346   headers[":path"] = "/index.html";
 347   headers["cookie"] = "foo=bar; baz=bing";
 348   headers["hello"] = "goodbye";
 349
 350   string expected_out, actual_out;
 351   expected_.TakeString(&expected_out);
 352   encoder_.EncodeHeaderSetWithoutCompression(headers, &actual_out);
 353   EXPECT_EQ(expected_out, actual_out);
 354 }
 355
 356 TEST_F(HpackEncoderTest, MultipleEncodingPasses) {
 357   // Pass 1: key_1_ and cookie_a_ are toggled on.
 358   {
 359     map<string, string> headers;
 360     headers["key1"] = "value1";
 361     headers["cookie"] = "a=bb";
 362
 363     ExpectIndex(IndexOf(cookie_a_));
 364     ExpectIndex(IndexOf(key_1_));
 365     CompareWithExpectedEncoding(headers);
 366   }
 367   // Pass 2: |key_1_| is double-toggled and evicted.
 368   // |key_2_| & |cookie_c_| are toggled on.
 369   // |cookie_a_| is toggled off.
 370   // A new cookie entry is added.
 371   {
 372     map<string, string> headers;
 373     headers["key1"] = "value1";
 374     headers["key2"] = "value2";
 375     headers["cookie"] = "c=dd; e=ff";
 376
 377     ExpectIndex(IndexOf(cookie_c_));  // Toggle on.
 378     ExpectIndex(IndexOf(key_1_));  // Double-toggle before eviction.
 379     ExpectIndex(IndexOf(key_1_));
 380     ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff");
 381
 382     ExpectIndex(IndexOf(key_2_) + 1);  // Toggle on. Add 1 to reflect insertion.
 383     ExpectIndex(IndexOf(cookie_a_) + 1);  // Toggle off.
 384     CompareWithExpectedEncoding(headers);
 385   }
 386   // Pass 3: |key_2_| is evicted and implicitly toggled off.
 387   // |cookie_c_| is explicitly toggled off.
 388   // "key1" is re-inserted.
 389   {
 390     map<string, string> headers;
 391     headers["key1"] = "value1";
 392     headers["key3"] = "value3";
 393     headers["cookie"] = "e=ff";
 394
 395     ExpectIndexedLiteral("key1", "value1");
 396     ExpectIndexedLiteral("key3", "value3");
 397     ExpectIndex(IndexOf(cookie_c_) + 2);  // Toggle off. Add 1 for insertion.
 398
 399     CompareWithExpectedEncoding(headers);
 400   }
 401 }
 402
 403 TEST_F(HpackEncoderTest, CookieToCrumbs) {
 404   test::HpackEncoderPeer peer(NULL);
 405   std::vector<StringPiece> out;
 406
 407   // A space after ';' is consumed. All other spaces remain. ';' at beginning
 408   // and end of string produce empty crumbs. Duplicate crumbs are removed.
 409   // See section 8.1.3.4 "Compressing the Cookie Header Field" in the HTTP/2
 410   // specification at http://tools.ietf.org/html/draft-ietf-httpbis-http2-11
 411   peer.CookieToCrumbs(" foo=1;bar=2 ; bar=3;  bing=4; ", &out);
 412   EXPECT_THAT(out, ElementsAre("", " bing=4", " foo=1", "bar=2 ", "bar=3"));
 413
 414   peer.CookieToCrumbs(";;foo = bar ;; ;baz =bing", &out);
 415   EXPECT_THAT(out, ElementsAre("", "baz =bing", "foo = bar "));
 416
 417   peer.CookieToCrumbs("baz=bing; foo=bar; baz=bing", &out);
 418   EXPECT_THAT(out, ElementsAre("baz=bing", "foo=bar"));
 419
 420   peer.CookieToCrumbs("baz=bing", &out);
 421   EXPECT_THAT(out, ElementsAre("baz=bing"));
 422
 423   peer.CookieToCrumbs("", &out);
 424   EXPECT_THAT(out, ElementsAre(""));
 425
 426   peer.CookieToCrumbs("foo;bar; baz;baz;bing;", &out);
 427   EXPECT_THAT(out, ElementsAre("", "bar", "baz", "bing", "foo"));
 428 }
 429
 430 TEST_F(HpackEncoderTest, UpdateCharacterCounts) {
 431   std::vector<size_t> counts(256, 0);
 432   size_t total_counts = 0;
 433   encoder_.SetCharCountsStorage(&counts, &total_counts);
 434
 435   char kTestString[] = "foo\0\1\xff""boo";
 436   peer_.UpdateCharacterCounts(
 437       StringPiece(kTestString, arraysize(kTestString) - 1));
 438
 439   std::vector<size_t> expect(256, 0);
 440   expect[static_cast<uint8>('f')] = 1;
 441   expect[static_cast<uint8>('o')] = 4;
 442   expect[static_cast<uint8>('\0')] = 1;
 443   expect[static_cast<uint8>('\1')] = 1;
 444   expect[static_cast<uint8>('\xff')] = 1;
 445   expect[static_cast<uint8>('b')] = 1;
 446
 447   EXPECT_EQ(expect, counts);
 448   EXPECT_EQ(9u, total_counts);
 449 }
 450
 451 }  // namespace
 452
 453 }  // namespace net