quiche/http2/hpack/hpack_header_table.cc

// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "quiche/http2/hpack/hpack_header_table.h"

#include <algorithm>
#include <cstddef>
#include <iterator>
#include <string>
#include <utility>

#include "absl/strings/string_view.h"
#include "quiche/http2/hpack/hpack_constants.h"
#include "quiche/http2/hpack/hpack_entry.h"
#include "quiche/http2/hpack/hpack_static_table.h"
#include "quiche/common/platform/api/quiche_logging.h"

namespace spdy {

HpackHeaderTable::HpackHeaderTable()
    : static_entries_(ObtainHpackStaticTable().GetStaticEntries()),
      static_index_(ObtainHpackStaticTable().GetStaticIndex()),
      static_name_index_(ObtainHpackStaticTable().GetStaticNameIndex()),
      settings_size_bound_(kDefaultHeaderTableSizeSetting),
      size_(0),
      max_size_(kDefaultHeaderTableSizeSetting),
      dynamic_table_insertions_(0) {}

HpackHeaderTable::~HpackHeaderTable() = default;

size_t HpackHeaderTable::GetByName(absl::string_view name) {
  {
    auto it = static_name_index_.find(name);
    if (it != static_name_index_.end()) {
      return 1 + it->second;
    }
  }
  {
    auto it = dynamic_name_index_.find(name);
    if (it != dynamic_name_index_.end()) {
      return dynamic_table_insertions_ - (*it)->added_index() +
             kStaticTableSize;
    }
  }
  return kHpackEntryNotFound;
}

size_t HpackHeaderTable::GetByNameAndValue(absl::string_view name,
                                           absl::string_view value) {
  HpackLookupEntry query{name, value};
  {
    auto it = static_index_.find(query);
    if (it != static_index_.end()) {
      return 1 + it->second;
    }
  }
  {
    auto it = dynamic_index_.find(query);
    if (it != dynamic_index_.end()) {
      return dynamic_table_insertions_ - (*it)->added_index() +
             kStaticTableSize;
    }
  }
  return kHpackEntryNotFound;
}

void HpackHeaderTable::SetMaxSize(size_t max_size) {
  QUICHE_CHECK_LE(max_size, settings_size_bound_);

  max_size_ = max_size;
  if (size_ > max_size_) {
    Evict(EvictionCountToReclaim(size_ - max_size_));
    QUICHE_CHECK_LE(size_, max_size_);
  }
}

void HpackHeaderTable::SetSettingsHeaderTableSize(size_t settings_size) {
  settings_size_bound_ = settings_size;
  SetMaxSize(settings_size_bound_);
}

void HpackHeaderTable::EvictionSet(absl::string_view name,
                                   absl::string_view value,
                                   DynamicEntryTable::iterator* begin_out,
                                   DynamicEntryTable::iterator* end_out) {
  size_t eviction_count = EvictionCountForEntry(name, value);
  *begin_out = dynamic_entries_.begin();
  *end_out = std::next(dynamic_entries_.begin(), eviction_count);
}

size_t HpackHeaderTable::EvictionCountForEntry(absl::string_view name,
                                               absl::string_view value) const {
  size_t available_size = max_size_ - size_;
  size_t entry_size = HpackEntry::Size(name, value);

  if (entry_size <= available_size) {
    // No evictions are required.
    return 0;
  }
  return EvictionCountToReclaim(entry_size - available_size);
}

size_t HpackHeaderTable::EvictionCountToReclaim(size_t reclaim_size) const {
  size_t count = 0;
  for (auto it = dynamic_entries_.begin();
       it != dynamic_entries_.end() && reclaim_size != 0; ++it, ++count) {
    reclaim_size -= std::min(reclaim_size, it->Size());
  }
  return count;
}

void HpackHeaderTable::Evict(size_t count) {
  for (size_t i = 0; i != count; ++i) {
    QUICHE_CHECK(!dynamic_entries_.empty());

    const HpackEntry& entry = dynamic_entries_.front();

    size_ -= entry.Size();
    auto it = dynamic_index_.find(&entry);
    QUICHE_DCHECK(it != dynamic_index_.end());
    // Only remove an entry from the index if its pointer matches.
    if (it != dynamic_index_.end() && *it == &entry) {
      dynamic_index_.erase(it);
    }
    auto name_it = dynamic_name_index_.find(entry.name());
    QUICHE_DCHECK(name_it != dynamic_name_index_.end());
    // Only remove an entry from the literal index if its pointer matches.
    if (name_it != dynamic_name_index_.end() && *name_it == &entry) {
      dynamic_name_index_.erase(name_it);
    }
    dynamic_entries_.pop_front();
  }
  if (dynamic_entries_.empty()) {
    dynamic_index_.clear();
    dynamic_name_index_.clear();
  }
}

void HpackHeaderTable::TryAddEntry(absl::string_view name,
                                   absl::string_view value) {
  // Since |dynamic_entries_| has iterator stability, |name| and |value| are
  // valid even after evicting other entries and push_back() making room for
  // the new one.
  Evict(EvictionCountForEntry(name, value));

  const size_t entry_size = HpackEntry::Size(name, value);
  if (entry_size > (max_size_ - size_)) {
    // Entire table has been emptied, but there's still insufficient room.
    QUICHE_DCHECK(dynamic_entries_.empty());
    QUICHE_DCHECK_EQ(0u, size_);
    return;
  }

  dynamic_entries_.push_back(HpackEntry{std::string(name), std::string(value),
                                        dynamic_table_insertions_});
  // This needs to be incremented before we use dynamic_index_ and
  // dynamic_name_index_ next time.
  ++dynamic_table_insertions_;
  size_ += entry_size;
  const HpackEntry* new_entry = &dynamic_entries_.back();
  auto index_result = dynamic_index_.insert(new_entry);
  if (!index_result.second) {
    // An entry with the same name and value already exists in the dynamic
    // index. We should replace it with the newly added entry.
    const HpackEntry* old_entry = *index_result.first;
    QUICHE_DVLOG(1) << "Found existing entry at: " << old_entry->added_index()
                    << " replacing with: " << new_entry->GetDebugString()
                    << " at: " << new_entry->added_index();
    QUICHE_DCHECK_GT(new_entry->added_index(), old_entry->added_index());
    dynamic_index_.erase(index_result.first);
    auto insert_result = dynamic_index_.insert(new_entry);
    QUICHE_CHECK(insert_result.second);
  }

  auto name_result = dynamic_name_index_.insert(new_entry);
  if (!name_result.second) {
    // An entry with the same name already exists in the dynamic index. We
    // should replace it with the newly added entry.
    const HpackEntry* old_entry = *name_result.first;
    QUICHE_DVLOG(1) << "Found existing entry at: " << old_entry->added_index()
                    << " replacing with: " << new_entry->GetDebugString()
                    << " at: " << new_entry->added_index();
    QUICHE_DCHECK_GT(new_entry->added_index(), old_entry->added_index());
    dynamic_name_index_.erase(name_result.first);
    auto insert_result = dynamic_name_index_.insert(new_entry);
    QUICHE_CHECK(insert_result.second);
  }
}

}  // namespace spdy