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
 170 TEST_F(HpackEncoderTest, SingleStaticIndex) {
 171   ExpectIndex(IndexOf(static_));
 172
 173   map<string, string> headers;
 174   headers[static_->name()] = static_->value();
 175   CompareWithExpectedEncoding(headers);
 176 }
 177
 178 TEST_F(HpackEncoderTest, SingleStaticIndexTooLarge) {
 179   peer_.table()->SetMaxSize(1);  // Also evicts all fixtures.
 180   ExpectIndex(IndexOf(static_));
 181
 182   map<string, string> headers;
 183   headers[static_->name()] = static_->value();
 184   CompareWithExpectedEncoding(headers);
 185
 186   EXPECT_EQ(0u, peer_.table_peer().dynamic_entries()->size());
 187 }
 188
 189 TEST_F(HpackEncoderTest, SingleLiteralWithIndexName) {
 190   ExpectIndexedLiteral(key_2_, "value3");
 191
 192   map<string, string> headers;
 193   headers[key_2_->name()] = "value3";
 194   CompareWithExpectedEncoding(headers);
 195
 196   // A new entry was inserted and added to the reference set.
 197   HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front();
 198   EXPECT_EQ(new_entry->name(), key_2_->name());
 199   EXPECT_EQ(new_entry->value(), "value3");
 200 }
 201
 202 TEST_F(HpackEncoderTest, SingleLiteralWithLiteralName) {
 203   ExpectIndexedLiteral("key3", "value3");
 204
 205   map<string, string> headers;
 206   headers["key3"] = "value3";
 207   CompareWithExpectedEncoding(headers);
 208
 209   HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front();
 210   EXPECT_EQ(new_entry->name(), "key3");
 211   EXPECT_EQ(new_entry->value(), "value3");
 212 }
 213
 214 TEST_F(HpackEncoderTest, SingleLiteralTooLarge) {
 215   peer_.table()->SetMaxSize(1);  // Also evicts all fixtures.
 216
 217   ExpectIndexedLiteral("key3", "value3");
 218
 219   // A header overflowing the header table is still emitted.
 220   // The header table is empty.
 221   map<string, string> headers;
 222   headers["key3"] = "value3";
 223   CompareWithExpectedEncoding(headers);
 224
 225   EXPECT_EQ(0u, peer_.table_peer().dynamic_entries()->size());
 226 }
 227
 228 TEST_F(HpackEncoderTest, EmitThanEvict) {
 229   // |key_1_| is toggled and placed into the reference set,
 230   // and then immediately evicted by "key3".
 231   ExpectIndex(IndexOf(key_1_));
 232   ExpectIndexedLiteral("key3", "value3");
 233
 234   map<string, string> headers;
 235   headers[key_1_->name()] = key_1_->value();
 236   headers["key3"] = "value3";
 237   CompareWithExpectedEncoding(headers);
 238 }
 239
 240 TEST_F(HpackEncoderTest, CookieHeaderIsCrumbled) {
 241   ExpectIndex(IndexOf(cookie_a_));
 242   ExpectIndex(IndexOf(cookie_c_));
 243   ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff");
 244
 245   map<string, string> headers;
 246   headers["cookie"] = "e=ff; a=bb; c=dd";
 247   CompareWithExpectedEncoding(headers);
 248 }
 249
 250 TEST_F(HpackEncoderTest, StringsDynamicallySelectHuffmanCoding) {
 251   peer_.set_allow_huffman_compression(true);
 252
 253   // Compactable string. Uses Huffman coding.
 254   peer_.EmitString("feedbeef");
 255   expected_.AppendPrefix(kStringLiteralHuffmanEncoded);
 256   expected_.AppendUint32(6);
 257   expected_.AppendBytes("\x94\xA5\x92""2\x96_");
 258
 259   // Non-compactable. Uses identity coding.
 260   peer_.EmitString("@@@@@@");
 261   expected_.AppendPrefix(kStringLiteralIdentityEncoded);
 262   expected_.AppendUint32(6);
 263   expected_.AppendBytes("@@@@@@");
 264
 265   string expected_out, actual_out;
 266   expected_.TakeString(&expected_out);
 267   peer_.TakeString(&actual_out);
 268   EXPECT_EQ(expected_out, actual_out);
 269 }
 270
 271 TEST_F(HpackEncoderTest, EncodingWithoutCompression) {
 272   // Implementation should internally disable.
 273   peer_.set_allow_huffman_compression(true);
 274
 275   ExpectNonIndexedLiteral(":path", "/index.html");
 276   ExpectNonIndexedLiteral("cookie", "foo=bar; baz=bing");
 277   ExpectNonIndexedLiteral("hello", "goodbye");
 278
 279   map<string, string> headers;
 280   headers[":path"] = "/index.html";
 281   headers["cookie"] = "foo=bar; baz=bing";
 282   headers["hello"] = "goodbye";
 283
 284   string expected_out, actual_out;
 285   expected_.TakeString(&expected_out);
 286   encoder_.EncodeHeaderSetWithoutCompression(headers, &actual_out);
 287   EXPECT_EQ(expected_out, actual_out);
 288 }
 289
 290 TEST_F(HpackEncoderTest, MultipleEncodingPasses) {
 291   // Pass 1.
 292   {
 293     map<string, string> headers;
 294     headers["key1"] = "value1";
 295     headers["cookie"] = "a=bb";
 296
 297     ExpectIndex(IndexOf(cookie_a_));
 298     ExpectIndex(IndexOf(key_1_));
 299     CompareWithExpectedEncoding(headers);
 300   }
 301   // Header table is:
 302   // 65: key1: value1
 303   // 64: key2: value2
 304   // 63: cookie: a=bb
 305   // 62: cookie: c=dd
 306   // Pass 2.
 307   {
 308     map<string, string> headers;
 309     headers["key1"] = "value1";
 310     headers["key2"] = "value2";
 311     headers["cookie"] = "c=dd; e=ff";
 312
 313     ExpectIndex(IndexOf(cookie_c_));
 314     // This cookie evicts |key1| from the header table.
 315     ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff");
 316     // |key1| is inserted to the header table, which evicts |key2|.
 317     ExpectIndexedLiteral("key1", "value1");
 318     // |key2| is inserted to the header table, which evicts |cookie_a|.
 319     ExpectIndexedLiteral("key2", "value2");
 320
 321     CompareWithExpectedEncoding(headers);
 322   }
 323   // Header table is:
 324   // 65: cookie: c=dd
 325   // 64: cookie: e=ff
 326   // 63: key1: value1
 327   // 62: key2: value2
 328   // Pass 3.
 329   {
 330     map<string, string> headers;
 331     headers["key1"] = "value1";
 332     headers["key3"] = "value3";
 333     headers["cookie"] = "e=ff";
 334
 335     ExpectIndex(64);
 336     ExpectIndex(63);
 337     ExpectIndexedLiteral("key3", "value3");
 338
 339     CompareWithExpectedEncoding(headers);
 340   }
 341 }
 342
 343 TEST_F(HpackEncoderTest, CookieToCrumbs) {
 344   test::HpackEncoderPeer peer(NULL);
 345   std::vector<StringPiece> out;
 346
 347   // A space after ';' is consumed. All other spaces remain. ';' at beginning
 348   // and end of string produce empty crumbs. Duplicate crumbs are removed.
 349   // See section 8.1.3.4 "Compressing the Cookie Header Field" in the HTTP/2
 350   // specification at http://tools.ietf.org/html/draft-ietf-httpbis-http2-11
 351   peer.CookieToCrumbs(" foo=1;bar=2 ; bar=3;  bing=4; ", &out);
 352   EXPECT_THAT(out, ElementsAre("", " bing=4", " foo=1", "bar=2 ", "bar=3"));
 353
 354   peer.CookieToCrumbs(";;foo = bar ;; ;baz =bing", &out);
 355   EXPECT_THAT(out, ElementsAre("", "baz =bing", "foo = bar "));
 356
 357   peer.CookieToCrumbs("baz=bing; foo=bar; baz=bing", &out);
 358   EXPECT_THAT(out, ElementsAre("baz=bing", "foo=bar"));
 359
 360   peer.CookieToCrumbs("baz=bing", &out);
 361   EXPECT_THAT(out, ElementsAre("baz=bing"));
 362
 363   peer.CookieToCrumbs("", &out);
 364   EXPECT_THAT(out, ElementsAre(""));
 365
 366   peer.CookieToCrumbs("foo;bar; baz;baz;bing;", &out);
 367   EXPECT_THAT(out, ElementsAre("", "bar", "baz", "bing", "foo"));
 368 }
 369
 370 TEST_F(HpackEncoderTest, UpdateCharacterCounts) {
 371   std::vector<size_t> counts(256, 0);
 372   size_t total_counts = 0;
 373   encoder_.SetCharCountsStorage(&counts, &total_counts);
 374
 375   char kTestString[] = "foo\0\1\xff""boo";
 376   peer_.UpdateCharacterCounts(
 377       StringPiece(kTestString, arraysize(kTestString) - 1));
 378
 379   std::vector<size_t> expect(256, 0);
 380   expect[static_cast<uint8>('f')] = 1;
 381   expect[static_cast<uint8>('o')] = 4;
 382   expect[static_cast<uint8>('\0')] = 1;
 383   expect[static_cast<uint8>('\1')] = 1;
 384   expect[static_cast<uint8>('\xff')] = 1;
 385   expect[static_cast<uint8>('b')] = 1;
 386
 387   EXPECT_EQ(expect, counts);
 388   EXPECT_EQ(9u, total_counts);
 389 }
 390
 391 }  // namespace
 392
 393 }  // namespace net