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