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_header_table.h" 6 7#include <algorithm> 8#include <set> 9#include <string> 10#include <vector> 11 12#include "base/basictypes.h" 13#include "base/macros.h" 14#include "net/spdy/hpack_constants.h" 15#include "net/spdy/hpack_entry.h" 16#include "testing/gtest/include/gtest/gtest.h" 17 18namespace net { 19 20using base::StringPiece; 21using std::distance; 22using std::string; 23 24namespace test { 25 26class HpackHeaderTablePeer { 27 public: 28 explicit HpackHeaderTablePeer(HpackHeaderTable* table) 29 : table_(table) {} 30 31 const HpackHeaderTable::EntryTable& dynamic_entries() { 32 return table_->dynamic_entries_; 33 } 34 const HpackHeaderTable::EntryTable& static_entries() { 35 return table_->static_entries_; 36 } 37 size_t index_size() { 38 return table_->static_index_.size() + table_->dynamic_index_.size(); 39 } 40 std::vector<HpackEntry*> EvictionSet(StringPiece name, StringPiece value) { 41 HpackHeaderTable::EntryTable::iterator begin, end; 42 table_->EvictionSet(name, value, &begin, &end); 43 std::vector<HpackEntry*> result; 44 for (; begin != end; ++begin) { 45 result.push_back(&(*begin)); 46 } 47 return result; 48 } 49 size_t total_insertions() { 50 return table_->total_insertions_; 51 } 52 size_t dynamic_entries_count() { 53 return table_->dynamic_entries_.size(); 54 } 55 size_t EvictionCountForEntry(StringPiece name, StringPiece value) { 56 return table_->EvictionCountForEntry(name, value); 57 } 58 size_t EvictionCountToReclaim(size_t reclaim_size) { 59 return table_->EvictionCountToReclaim(reclaim_size); 60 } 61 void Evict(size_t count) { 62 return table_->Evict(count); 63 } 64 65 void AddDynamicEntry(StringPiece name, StringPiece value) { 66 table_->dynamic_entries_.push_back( 67 HpackEntry(name, value, false, table_->total_insertions_++)); 68 } 69 70 private: 71 HpackHeaderTable* table_; 72}; 73 74} // namespace test 75 76namespace { 77 78class HpackHeaderTableTest : public ::testing::Test { 79 protected: 80 typedef std::vector<HpackEntry> HpackEntryVector; 81 82 HpackHeaderTableTest() : table_(), peer_(&table_) {} 83 84 // Returns an entry whose Size() is equal to the given one. 85 static HpackEntry MakeEntryOfSize(uint32 size) { 86 EXPECT_GE(size, HpackEntry::kSizeOverhead); 87 string name((size - HpackEntry::kSizeOverhead) / 2, 'n'); 88 string value(size - HpackEntry::kSizeOverhead - name.size(), 'v'); 89 HpackEntry entry(name, value); 90 EXPECT_EQ(size, entry.Size()); 91 return entry; 92 } 93 94 // Returns a vector of entries whose total size is equal to the given 95 // one. 96 static HpackEntryVector MakeEntriesOfTotalSize(uint32 total_size) { 97 EXPECT_GE(total_size, HpackEntry::kSizeOverhead); 98 uint32 entry_size = HpackEntry::kSizeOverhead; 99 uint32 remaining_size = total_size; 100 HpackEntryVector entries; 101 while (remaining_size > 0) { 102 EXPECT_LE(entry_size, remaining_size); 103 entries.push_back(MakeEntryOfSize(entry_size)); 104 remaining_size -= entry_size; 105 entry_size = std::min(remaining_size, entry_size + 32); 106 } 107 return entries; 108 } 109 110 // Adds the given vector of entries to the given header table, 111 // expecting no eviction to happen. 112 void AddEntriesExpectNoEviction(const HpackEntryVector& entries) { 113 for (HpackEntryVector::const_iterator it = entries.begin(); 114 it != entries.end(); ++it) { 115 HpackHeaderTable::EntryTable::iterator begin, end; 116 117 table_.EvictionSet(it->name(), it->value(), &begin, &end); 118 EXPECT_EQ(0, distance(begin, end)); 119 120 const HpackEntry* entry = table_.TryAddEntry(it->name(), it->value()); 121 EXPECT_NE(entry, static_cast<HpackEntry*>(NULL)); 122 } 123 124 for (size_t i = 0; i != entries.size(); ++i) { 125 // Static table has 61 entries, dynamic entries follow those. 126 size_t index = 61 + entries.size() - i; 127 const HpackEntry* entry = table_.GetByIndex(index); 128 EXPECT_EQ(entries[i].name(), entry->name()); 129 EXPECT_EQ(entries[i].value(), entry->value()); 130 EXPECT_EQ(index, table_.IndexOf(entry)); 131 } 132 } 133 134 HpackEntry DynamicEntry(string name, string value) { 135 peer_.AddDynamicEntry(name, value); 136 return peer_.dynamic_entries().back(); 137 } 138 139 HpackHeaderTable table_; 140 test::HpackHeaderTablePeer peer_; 141}; 142 143TEST_F(HpackHeaderTableTest, StaticTableInitialization) { 144 EXPECT_EQ(0u, table_.size()); 145 EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.max_size()); 146 EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.settings_size_bound()); 147 148 EXPECT_EQ(0u, peer_.dynamic_entries_count()); 149 EXPECT_EQ(peer_.static_entries().size(), peer_.total_insertions()); 150 151 // Static entries have been populated and inserted into the table & index. 152 EXPECT_NE(0u, peer_.static_entries().size()); 153 EXPECT_EQ(peer_.index_size(), peer_.static_entries().size()); 154 for (size_t i = 0; i != peer_.static_entries().size(); ++i) { 155 const HpackEntry* entry = &peer_.static_entries()[i]; 156 157 EXPECT_TRUE(entry->IsStatic()); 158 EXPECT_EQ(entry, table_.GetByIndex(i + 1)); 159 EXPECT_EQ(entry, table_.GetByNameAndValue(entry->name(), entry->value())); 160 } 161} 162 163TEST_F(HpackHeaderTableTest, BasicDynamicEntryInsertionAndEviction) { 164 size_t static_count = peer_.total_insertions(); 165 const HpackEntry* first_static_entry = table_.GetByIndex(1); 166 167 EXPECT_EQ(1u, table_.IndexOf(first_static_entry)); 168 169 const HpackEntry* entry = table_.TryAddEntry("header-key", "Header Value"); 170 EXPECT_EQ("header-key", entry->name()); 171 EXPECT_EQ("Header Value", entry->value()); 172 EXPECT_FALSE(entry->IsStatic()); 173 174 // Table counts were updated appropriately. 175 EXPECT_EQ(entry->Size(), table_.size()); 176 EXPECT_EQ(1u, peer_.dynamic_entries_count()); 177 EXPECT_EQ(peer_.dynamic_entries().size(), peer_.dynamic_entries_count()); 178 EXPECT_EQ(static_count + 1, peer_.total_insertions()); 179 EXPECT_EQ(static_count + 1, peer_.index_size()); 180 181 // Index() of entries reflects the insertion. 182 EXPECT_EQ(1u, table_.IndexOf(first_static_entry)); 183 // Static table has 61 entries. 184 EXPECT_EQ(62u, table_.IndexOf(entry)); 185 EXPECT_EQ(first_static_entry, table_.GetByIndex(1)); 186 EXPECT_EQ(entry, table_.GetByIndex(62)); 187 188 // Evict |entry|. Table counts are again updated appropriately. 189 peer_.Evict(1); 190 EXPECT_EQ(0u, table_.size()); 191 EXPECT_EQ(0u, peer_.dynamic_entries_count()); 192 EXPECT_EQ(peer_.dynamic_entries().size(), peer_.dynamic_entries_count()); 193 EXPECT_EQ(static_count + 1, peer_.total_insertions()); 194 EXPECT_EQ(static_count, peer_.index_size()); 195 196 // Index() of |first_static_entry| reflects the eviction. 197 EXPECT_EQ(1u, table_.IndexOf(first_static_entry)); 198 EXPECT_EQ(first_static_entry, table_.GetByIndex(1)); 199} 200 201TEST_F(HpackHeaderTableTest, EntryIndexing) { 202 const HpackEntry* first_static_entry = table_.GetByIndex(1); 203 204 // Static entries are queryable by name & value. 205 EXPECT_EQ(first_static_entry, table_.GetByName(first_static_entry->name())); 206 EXPECT_EQ(first_static_entry, table_.GetByNameAndValue( 207 first_static_entry->name(), first_static_entry->value())); 208 209 // Create a mix of entries which duplicate names, and names & values of both 210 // dynamic and static entries. 211 const HpackEntry* entry1 = table_.TryAddEntry(first_static_entry->name(), 212 first_static_entry->value()); 213 const HpackEntry* entry2 = 214 table_.TryAddEntry(first_static_entry->name(), "Value Four"); 215 const HpackEntry* entry3 = table_.TryAddEntry("key-1", "Value One"); 216 const HpackEntry* entry4 = table_.TryAddEntry("key-2", "Value Three"); 217 const HpackEntry* entry5 = table_.TryAddEntry("key-1", "Value Two"); 218 const HpackEntry* entry6 = table_.TryAddEntry("key-2", "Value Three"); 219 const HpackEntry* entry7 = table_.TryAddEntry("key-2", "Value Four"); 220 221 // Entries are queryable under their current index. 222 EXPECT_EQ(entry7, table_.GetByIndex(62)); 223 EXPECT_EQ(entry6, table_.GetByIndex(63)); 224 EXPECT_EQ(entry5, table_.GetByIndex(64)); 225 EXPECT_EQ(entry4, table_.GetByIndex(65)); 226 EXPECT_EQ(entry3, table_.GetByIndex(66)); 227 EXPECT_EQ(entry2, table_.GetByIndex(67)); 228 EXPECT_EQ(entry1, table_.GetByIndex(68)); 229 EXPECT_EQ(first_static_entry, table_.GetByIndex(1)); 230 231 // Querying by name returns the lowest-value matching entry. 232 EXPECT_EQ(entry3, table_.GetByName("key-1")); 233 EXPECT_EQ(entry7, table_.GetByName("key-2")); 234 EXPECT_EQ(entry2->name(), 235 table_.GetByName(first_static_entry->name())->name()); 236 EXPECT_EQ(NULL, table_.GetByName("not-present")); 237 238 // Querying by name & value returns the lowest-index matching entry among 239 // static entries, and the highest-index one among dynamic entries. 240 EXPECT_EQ(entry3, table_.GetByNameAndValue("key-1", "Value One")); 241 EXPECT_EQ(entry5, table_.GetByNameAndValue("key-1", "Value Two")); 242 EXPECT_EQ(entry4, table_.GetByNameAndValue("key-2", "Value Three")); 243 EXPECT_EQ(entry7, table_.GetByNameAndValue("key-2", "Value Four")); 244 EXPECT_EQ(first_static_entry, 245 table_.GetByNameAndValue(first_static_entry->name(), 246 first_static_entry->value())); 247 EXPECT_EQ(entry2, table_.GetByNameAndValue(first_static_entry->name(), 248 "Value Four")); 249 EXPECT_EQ(NULL, table_.GetByNameAndValue("key-1", "Not Present")); 250 EXPECT_EQ(NULL, table_.GetByNameAndValue("not-present", "Value One")); 251 252 // Evict |entry1|. Queries for its name & value now return the static entry. 253 // |entry2| remains queryable. 254 peer_.Evict(1); 255 EXPECT_EQ(first_static_entry, 256 table_.GetByNameAndValue(first_static_entry->name(), 257 first_static_entry->value())); 258 EXPECT_EQ(entry2, table_.GetByNameAndValue(first_static_entry->name(), 259 "Value Four")); 260 261 // Evict |entry2|. Queries by its name & value are not found. 262 peer_.Evict(1); 263 EXPECT_EQ(NULL, table_.GetByNameAndValue(first_static_entry->name(), 264 "Value Four")); 265} 266 267TEST_F(HpackHeaderTableTest, SetSizes) { 268 string key = "key", value = "value"; 269 const HpackEntry* entry1 = table_.TryAddEntry(key, value); 270 const HpackEntry* entry2 = table_.TryAddEntry(key, value); 271 const HpackEntry* entry3 = table_.TryAddEntry(key, value); 272 273 // Set exactly large enough. No Evictions. 274 size_t max_size = entry1->Size() + entry2->Size() + entry3->Size(); 275 table_.SetMaxSize(max_size); 276 EXPECT_EQ(3u, peer_.dynamic_entries().size()); 277 278 // Set just too small. One eviction. 279 max_size = entry1->Size() + entry2->Size() + entry3->Size() - 1; 280 table_.SetMaxSize(max_size); 281 EXPECT_EQ(2u, peer_.dynamic_entries().size()); 282 283 // Changing SETTINGS_HEADER_TABLE_SIZE doesn't affect table_.max_size(), 284 // iff SETTINGS_HEADER_TABLE_SIZE >= |max_size|. 285 EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.settings_size_bound()); 286 table_.SetSettingsHeaderTableSize(kDefaultHeaderTableSizeSetting*2); 287 EXPECT_EQ(max_size, table_.max_size()); 288 table_.SetSettingsHeaderTableSize(max_size + 1); 289 EXPECT_EQ(max_size, table_.max_size()); 290 EXPECT_EQ(2u, peer_.dynamic_entries().size()); 291 292 // SETTINGS_HEADER_TABLE_SIZE upper-bounds |table_.max_size()|, 293 // and will force evictions. 294 max_size = entry3->Size() - 1; 295 table_.SetSettingsHeaderTableSize(max_size); 296 EXPECT_EQ(max_size, table_.max_size()); 297 EXPECT_EQ(max_size, table_.settings_size_bound()); 298 EXPECT_EQ(0u, peer_.dynamic_entries().size()); 299} 300 301TEST_F(HpackHeaderTableTest, EvictionCountForEntry) { 302 string key = "key", value = "value"; 303 const HpackEntry* entry1 = table_.TryAddEntry(key, value); 304 const HpackEntry* entry2 = table_.TryAddEntry(key, value); 305 size_t entry3_size = HpackEntry::Size(key, value); 306 307 // Just enough capacity for third entry. 308 table_.SetMaxSize(entry1->Size() + entry2->Size() + entry3_size); 309 EXPECT_EQ(0u, peer_.EvictionCountForEntry(key, value)); 310 EXPECT_EQ(1u, peer_.EvictionCountForEntry(key, value + "x")); 311 312 // No extra capacity. Third entry would force evictions. 313 table_.SetMaxSize(entry1->Size() + entry2->Size()); 314 EXPECT_EQ(1u, peer_.EvictionCountForEntry(key, value)); 315 EXPECT_EQ(2u, peer_.EvictionCountForEntry(key, value + "x")); 316} 317 318TEST_F(HpackHeaderTableTest, EvictionCountToReclaim) { 319 string key = "key", value = "value"; 320 const HpackEntry* entry1 = table_.TryAddEntry(key, value); 321 const HpackEntry* entry2 = table_.TryAddEntry(key, value); 322 323 EXPECT_EQ(1u, peer_.EvictionCountToReclaim(1)); 324 EXPECT_EQ(1u, peer_.EvictionCountToReclaim(entry1->Size())); 325 EXPECT_EQ(2u, peer_.EvictionCountToReclaim(entry1->Size() + 1)); 326 EXPECT_EQ(2u, peer_.EvictionCountToReclaim(entry1->Size() + entry2->Size())); 327} 328 329// Fill a header table with entries. Make sure the entries are in 330// reverse order in the header table. 331TEST_F(HpackHeaderTableTest, TryAddEntryBasic) { 332 EXPECT_EQ(0u, table_.size()); 333 EXPECT_EQ(table_.settings_size_bound(), table_.max_size()); 334 335 HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size()); 336 337 // Most of the checks are in AddEntriesExpectNoEviction(). 338 AddEntriesExpectNoEviction(entries); 339 EXPECT_EQ(table_.max_size(), table_.size()); 340 EXPECT_EQ(table_.settings_size_bound(), table_.size()); 341} 342 343// Fill a header table with entries, and then ramp the table's max 344// size down to evict an entry one at a time. Make sure the eviction 345// happens as expected. 346TEST_F(HpackHeaderTableTest, SetMaxSize) { 347 HpackEntryVector entries = MakeEntriesOfTotalSize( 348 kDefaultHeaderTableSizeSetting / 2); 349 AddEntriesExpectNoEviction(entries); 350 351 for (HpackEntryVector::iterator it = entries.begin(); 352 it != entries.end(); ++it) { 353 size_t expected_count = distance(it, entries.end()); 354 EXPECT_EQ(expected_count, peer_.dynamic_entries().size()); 355 356 table_.SetMaxSize(table_.size() + 1); 357 EXPECT_EQ(expected_count, peer_.dynamic_entries().size()); 358 359 table_.SetMaxSize(table_.size()); 360 EXPECT_EQ(expected_count, peer_.dynamic_entries().size()); 361 362 --expected_count; 363 table_.SetMaxSize(table_.size() - 1); 364 EXPECT_EQ(expected_count, peer_.dynamic_entries().size()); 365 } 366 EXPECT_EQ(0u, table_.size()); 367} 368 369// Fill a header table with entries, and then add an entry just big 370// enough to cause eviction of all but one entry. Make sure the 371// eviction happens as expected and the long entry is inserted into 372// the table. 373TEST_F(HpackHeaderTableTest, TryAddEntryEviction) { 374 HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size()); 375 AddEntriesExpectNoEviction(entries); 376 377 const HpackEntry* survivor_entry = table_.GetByIndex(61 + 1); 378 HpackEntry long_entry = 379 MakeEntryOfSize(table_.max_size() - survivor_entry->Size()); 380 381 // All dynamic entries but the first are to be evicted. 382 EXPECT_EQ(peer_.dynamic_entries().size() - 1, peer_.EvictionSet( 383 long_entry.name(), long_entry.value()).size()); 384 385 const HpackEntry* new_entry = 386 table_.TryAddEntry(long_entry.name(), long_entry.value()); 387 EXPECT_EQ(62u, table_.IndexOf(new_entry)); 388 EXPECT_EQ(2u, peer_.dynamic_entries().size()); 389 EXPECT_EQ(table_.GetByIndex(63), survivor_entry); 390 EXPECT_EQ(table_.GetByIndex(62), new_entry); 391} 392 393// Fill a header table with entries, and then add an entry bigger than 394// the entire table. Make sure no entry remains in the table. 395TEST_F(HpackHeaderTableTest, TryAddTooLargeEntry) { 396 HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size()); 397 AddEntriesExpectNoEviction(entries); 398 399 const HpackEntry long_entry = MakeEntryOfSize(table_.max_size() + 1); 400 401 // All entries are to be evicted. 402 EXPECT_EQ(peer_.dynamic_entries().size(), peer_.EvictionSet( 403 long_entry.name(), long_entry.value()).size()); 404 405 const HpackEntry* new_entry = 406 table_.TryAddEntry(long_entry.name(), long_entry.value()); 407 EXPECT_EQ(new_entry, static_cast<HpackEntry*>(NULL)); 408 EXPECT_EQ(0u, peer_.dynamic_entries().size()); 409} 410 411TEST_F(HpackHeaderTableTest, ComparatorNameOrdering) { 412 HpackEntry entry1("header", "value"); 413 HpackEntry entry2("HEADER", "value"); 414 415 HpackHeaderTable::EntryComparator comparator; 416 EXPECT_FALSE(comparator(&entry1, &entry2)); 417 EXPECT_TRUE(comparator(&entry2, &entry1)); 418} 419 420TEST_F(HpackHeaderTableTest, ComparatorValueOrdering) { 421 HpackEntry entry1("header", "value"); 422 HpackEntry entry2("header", "VALUE"); 423 424 HpackHeaderTable::EntryComparator comparator; 425 EXPECT_FALSE(comparator(&entry1, &entry2)); 426 EXPECT_TRUE(comparator(&entry2, &entry1)); 427} 428 429TEST_F(HpackHeaderTableTest, ComparatorIndexOrdering) { 430 HpackHeaderTable::EntryComparator comparator; 431 HpackEntry entry1(DynamicEntry("name", "value")); 432 HpackEntry entry2(DynamicEntry("name", "value")); 433 434 // |entry1| has lower insertion index than |entry2|. 435 EXPECT_TRUE(comparator(&entry1, &entry2)); 436 EXPECT_FALSE(comparator(&entry2, &entry1)); 437} 438 439TEST_F(HpackHeaderTableTest, ComparatorEqualityOrdering) { 440 HpackEntry entry1("name", "value"); 441 HpackEntry entry2(DynamicEntry("name", "value")); 442 443 HpackHeaderTable::EntryComparator comparator; 444 EXPECT_FALSE(comparator(&entry1, &entry1)); 445 EXPECT_FALSE(comparator(&entry2, &entry2)); 446} 447 448} // namespace 449 450} // namespace net 451