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   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
  90 namespace {
  91
  92 using std::map;
  93 using testing::ElementsAre;
  94
  95 class 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   void SetUp() override {
 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
 175 TEST_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
 183 TEST_F(HpackEncoderTest, SingleStaticIndex) {
 184   ExpectIndex(IndexOf(static_));
 185
 186   map<string, string> headers;
 187   headers[static_->name()] = static_->value();
 188   CompareWithExpectedEncoding(headers);
 189 }
 190
 191 TEST_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
 202 TEST_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
 215 TEST_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
 227 TEST_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
 241 TEST_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
 253 TEST_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
 263 TEST_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
 284 TEST_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
 303 TEST_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["key2"] = "value2";
 323     headers["cookie"] = "c=dd; e=ff";
 324
 325     ExpectIndex(IndexOf(cookie_c_));
 326     // This cookie evicts |key1| from the dynamic table.
 327     ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff");
 328     // "key2: value2"
 329     ExpectIndex(65);
 330
 331     CompareWithExpectedEncoding(headers);
 332   }
 333   // Header table is:
 334   // 65: key2: value2
 335   // 64: cookie: a=bb
 336   // 63: cookie: c=dd
 337   // 62: cookie: e=ff
 338   // Pass 3.
 339   {
 340     map<string, string> headers;
 341     headers["key2"] = "value2";
 342     headers["cookie"] = "a=bb; b=cc; c=dd";
 343
 344     // "cookie: a=bb"
 345     ExpectIndex(64);
 346     // This cookie evicts |key2| from the dynamic table.
 347     ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "b=cc");
 348     // "cookie: c=dd"
 349     ExpectIndex(64);
 350     // "key2: value2"
 351     ExpectIndexedLiteral("key2", "value2");
 352
 353     CompareWithExpectedEncoding(headers);
 354   }
 355 }
 356
 357 TEST_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   // This entry pushes "cookie: a=bb" back to 63.
 371   ExpectIndexedLiteral(peer_.table()->GetByName(":authority"),
 372                        "www.example.com");
 373   ExpectNonIndexedLiteral(":path", "/spam/eggs.html");
 374   // Regular headers are endoded in alphabetical order.
 375   // This entry pushes "cookie: a=bb" back to 64.
 376   ExpectIndexedLiteral("-foo", "bar");
 377   ExpectIndex(64);
 378   ExpectIndexedLiteral("foo", "bar");
 379   CompareWithExpectedEncoding(headers);
 380 }
 381
 382 TEST_F(HpackEncoderTest, CookieToCrumbs) {
 383   test::HpackEncoderPeer peer(NULL);
 384   std::vector<StringPiece> out;
 385
 386   // A space after ';' is consumed. All other spaces remain. ';' at beginning
 387   // and end of string produce empty crumbs. Duplicate crumbs are removed.
 388   // See section 8.1.3.4 "Compressing the Cookie Header Field" in the HTTP/2
 389   // specification at http://tools.ietf.org/html/draft-ietf-httpbis-http2-11
 390   peer.CookieToCrumbs(" foo=1;bar=2 ; bar=3;  bing=4; ", &out);
 391   EXPECT_THAT(out, ElementsAre("", " bing=4", " foo=1", "bar=2 ", "bar=3"));
 392
 393   peer.CookieToCrumbs(";;foo = bar ;; ;baz =bing", &out);
 394   EXPECT_THAT(out, ElementsAre("", "baz =bing", "foo = bar "));
 395
 396   peer.CookieToCrumbs("baz=bing; foo=bar; baz=bing", &out);
 397   EXPECT_THAT(out, ElementsAre("baz=bing", "foo=bar"));
 398
 399   peer.CookieToCrumbs("baz=bing", &out);
 400   EXPECT_THAT(out, ElementsAre("baz=bing"));
 401
 402   peer.CookieToCrumbs("", &out);
 403   EXPECT_THAT(out, ElementsAre(""));
 404
 405   peer.CookieToCrumbs("foo;bar; baz;baz;bing;", &out);
 406   EXPECT_THAT(out, ElementsAre("", "bar", "baz", "bing", "foo"));
 407 }
 408
 409 TEST_F(HpackEncoderTest, UpdateCharacterCounts) {
 410   std::vector<size_t> counts(256, 0);
 411   size_t total_counts = 0;
 412   encoder_.SetCharCountsStorage(&counts, &total_counts);
 413
 414   char kTestString[] = "foo\0\1\xff""boo";
 415   peer_.UpdateCharacterCounts(
 416       StringPiece(kTestString, arraysize(kTestString) - 1));
 417
 418   std::vector<size_t> expect(256, 0);
 419   expect[static_cast<uint8>('f')] = 1;
 420   expect[static_cast<uint8>('o')] = 4;
 421   expect[static_cast<uint8>('\0')] = 1;
 422   expect[static_cast<uint8>('\1')] = 1;
 423   expect[static_cast<uint8>('\xff')] = 1;
 424   expect[static_cast<uint8>('b')] = 1;
 425
 426   EXPECT_EQ(expect, counts);
 427   EXPECT_EQ(9u, total_counts);
 428 }
 429
 430 TEST_F(HpackEncoderTest, DecomposeRepresentation) {
 431   test::HpackEncoderPeer peer(NULL);
 432   std::vector<StringPiece> out;
 433
 434   peer.DecomposeRepresentation("", &out);
 435   EXPECT_THAT(out, ElementsAre(""));
 436
 437   peer.DecomposeRepresentation("foobar", &out);
 438   EXPECT_THAT(out, ElementsAre("foobar"));
 439
 440   peer.DecomposeRepresentation(StringPiece("foo\0bar", 7), &out);
 441   EXPECT_THAT(out, ElementsAre("foo", "bar"));
 442
 443   peer.DecomposeRepresentation(StringPiece("\0foo\0bar", 8), &out);
 444   EXPECT_THAT(out, ElementsAre("", "foo", "bar"));
 445
 446   peer.DecomposeRepresentation(StringPiece("foo\0bar\0", 8), &out);
 447   EXPECT_THAT(out, ElementsAre("foo", "bar", ""));
 448
 449   peer.DecomposeRepresentation(StringPiece("\0foo\0bar\0", 9), &out);
 450   EXPECT_THAT(out, ElementsAre("", "foo", "bar", ""));
 451 }
 452
 453 // Test that encoded headers do not have \0-delimited multiple values, as this
 454 // became disallowed in HTTP/2 draft-14.
 455 TEST_F(HpackEncoderTest, CrumbleNullByteDelimitedValue) {
 456   map<string, string> headers;
 457   // A header field to be crumbled: "spam: foo\0bar".
 458   headers["spam"] = string("foo\0bar", 7);
 459
 460   ExpectIndexedLiteral("spam", "foo");
 461   expected_.AppendPrefix(kLiteralIncrementalIndexOpcode);
 462   expected_.AppendUint32(62);
 463   expected_.AppendPrefix(kStringLiteralIdentityEncoded);
 464   expected_.AppendUint32(3);
 465   expected_.AppendBytes("bar");
 466   CompareWithExpectedEncoding(headers);
 467 }
 468
 469 }  // namespace
 470
 471 }  // namespace net