Home | History | Annotate | Download | only in spdy 
      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
    454