quic/core/qpack/qpack_header_table.h

// Copyright (c) 2018 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.

#ifndef QUICHE_QUIC_CORE_QPACK_QPACK_HEADER_TABLE_H_
#define QUICHE_QUIC_CORE_QPACK_QPACK_HEADER_TABLE_H_

#include <cstdint>
#include <functional>
#include <queue>
#include <vector>

#include "absl/strings/string_view.h"
#include "quic/platform/api/quic_export.h"
#include "spdy/core/hpack/hpack_entry.h"
#include "spdy/core/hpack/hpack_header_table.h"

namespace quic {

namespace test {

class QpackHeaderTablePeer;

}  // namespace test

using QpackEntry = spdy::HpackEntry;
constexpr size_t kQpackEntrySizeOverhead = spdy::kHpackEntrySizeOverhead;

// This class manages the QPACK static and dynamic tables.  For dynamic entries,
// it only has a concept of absolute indices.  The caller needs to perform the
// necessary transformations to and from relative indices and post-base indices.
class QUIC_EXPORT_PRIVATE QpackHeaderTable {
 public:
  using EntryTable = spdy::HpackHeaderTable::EntryTable;
  using EntryHasher = spdy::HpackHeaderTable::EntryHasher;
  using EntriesEq = spdy::HpackHeaderTable::EntriesEq;
  using UnorderedEntrySet = spdy::HpackHeaderTable::UnorderedEntrySet;
  using NameToEntryMap = spdy::HpackHeaderTable::NameToEntryMap;

  // Result of header table lookup.
  enum class MatchType { kNameAndValue, kName, kNoMatch };

  // Observer interface for dynamic table insertion.
  class QUIC_EXPORT_PRIVATE Observer {
   public:
    virtual ~Observer() = default;

    // Called when inserted_entry_count() reaches the threshold the Observer was
    // registered with.  After this call the Observer automatically gets
    // deregistered.
    virtual void OnInsertCountReachedThreshold() = 0;

    // Called when QpackHeaderTable is destroyed to let the Observer know that
    // it must not call UnregisterObserver().
    virtual void Cancel() = 0;
  };

  QpackHeaderTable();
  QpackHeaderTable(const QpackHeaderTable&) = delete;
  QpackHeaderTable& operator=(const QpackHeaderTable&) = delete;

  ~QpackHeaderTable();

  // Returns the entry at absolute index |index| from the static or dynamic
  // table according to |is_static|.  |index| is zero based for both the static
  // and the dynamic table.  The returned pointer is valid until the entry is
  // evicted, even if other entries are inserted into the dynamic table.
  // Returns nullptr if entry does not exist.
  const QpackEntry* LookupEntry(bool is_static, uint64_t index) const;

  // Returns the absolute index of an entry with matching name and value if such
  // exists, otherwise one with matching name is such exists.  |index| is zero
  // based for both the static and the dynamic table.
  MatchType FindHeaderField(absl::string_view name,
                            absl::string_view value,
                            bool* is_static,
                            uint64_t* index) const;

  // Returns whether an entry with |name| and |value| has a size (including
  // overhead) that is smaller than or equal to the capacity of the dynamic
  // table.
  bool EntryFitsDynamicTableCapacity(absl::string_view name,
                                     absl::string_view value) const;

  // Inserts (name, value) into the dynamic table.  Entry must not be larger
  // than the capacity of the dynamic table.  May evict entries.  Returns the
  // absolute index of the inserted dynamic table entry.
  uint64_t InsertEntry(absl::string_view name, absl::string_view value);

  // Returns the size of the largest entry that could be inserted into the
  // dynamic table without evicting entry |index|.  |index| might be larger than
  // inserted_entry_count(), in which case the capacity of the table is
  // returned.  |index| must not be smaller than dropped_entry_count().
  uint64_t MaxInsertSizeWithoutEvictingGivenEntry(uint64_t index) const;

  // Change dynamic table capacity to |capacity|.  Returns true on success.
  // Returns false is |capacity| exceeds maximum dynamic table capacity.
  bool SetDynamicTableCapacity(uint64_t capacity);

  // Set |maximum_dynamic_table_capacity_|.  The initial value is zero.  The
  // final value is determined by the decoder and is sent to the encoder as
  // SETTINGS_HEADER_TABLE_SIZE.  Therefore in the decoding context the final
  // value can be set upon connection establishment, whereas in the encoding
  // context it can be set when the SETTINGS frame is received.
  // This method must only be called at most once.
  // Returns true if |maximum_dynamic_table_capacity| is set for the first time
  // or if it doesn't change current value. The setting is not changed when
  // returning false.
  bool SetMaximumDynamicTableCapacity(uint64_t maximum_dynamic_table_capacity);

  // Get |maximum_dynamic_table_capacity_|.
  uint64_t maximum_dynamic_table_capacity() const {
    return maximum_dynamic_table_capacity_;
  }

  // Register an observer to be notified when inserted_entry_count() reaches
  // |required_insert_count|.  After the notification, |observer| automatically
  // gets unregistered.  Each observer must only be registered at most once.
  void RegisterObserver(uint64_t required_insert_count, Observer* observer);

  // Unregister previously registered observer.  Must be called with the same
  // |required_insert_count| value that |observer| was registered with.  Must be
  // called before an observer still waiting for notification is destroyed,
  // unless QpackHeaderTable already called Observer::Cancel(), in which case
  // this method must not be called.
  void UnregisterObserver(uint64_t required_insert_count, Observer* observer);

  // Used on request streams to encode and decode Required Insert Count.
  uint64_t max_entries() const { return max_entries_; }

  // The number of entries inserted to the dynamic table (including ones that
  // were dropped since).  Used for relative indexing on the encoder stream.
  uint64_t inserted_entry_count() const {
    return dynamic_entries_.size() + dropped_entry_count_;
  }

  // The number of entries dropped from the dynamic table.
  uint64_t dropped_entry_count() const { return dropped_entry_count_; }

  // Returns the draining index described at
  // https://quicwg.org/base-drafts/draft-ietf-quic-qpack.html#avoiding-blocked-insertions.
  // Entries with an index larger than or equal to the draining index take up
  // approximately |1.0 - draining_fraction| of dynamic table capacity.  The
  // remaining capacity is taken up by draining entries and unused space.
  // The returned index might not be the index of a valid entry.
  uint64_t draining_index(float draining_fraction) const;

  void set_dynamic_table_entry_referenced() {
    dynamic_table_entry_referenced_ = true;
  }
  bool dynamic_table_entry_referenced() const {
    return dynamic_table_entry_referenced_;
  }

 private:
  friend class test::QpackHeaderTablePeer;

  // Evict entries from the dynamic table until table size is less than or equal
  // to current value of |dynamic_table_capacity_|.
  void EvictDownToCurrentCapacity();

  // Static Table

  // |static_entries_|, |static_index_|, |static_name_index_| are owned by
  // QpackStaticTable singleton.

  // Tracks QpackEntries by index.
  const EntryTable& static_entries_;

  // Tracks the unique static entry for a given header name and value.
  const UnorderedEntrySet& static_index_;

  // Tracks the first static entry for a given header name.
  const NameToEntryMap& static_name_index_;

  // Dynamic Table

  // Queue of dynamic table entries, for lookup by index.
  // |dynamic_entries_| owns the entries in the dynamic table.
  EntryTable dynamic_entries_;

  // An unordered set of QpackEntry pointers with a comparison operator that
  // only cares about name and value.  This allows fast lookup of the most
  // recently inserted dynamic entry for a given header name and value pair.
  // Entries point to entries owned by |dynamic_entries_|.
  UnorderedEntrySet dynamic_index_;

  // An unordered map of QpackEntry pointers keyed off header name.  This allows
  // fast lookup of the most recently inserted dynamic entry for a given header
  // name.  Entries point to entries owned by |dynamic_entries_|.
  NameToEntryMap dynamic_name_index_;

  // Size of the dynamic table.  This is the sum of the size of its entries.
  uint64_t dynamic_table_size_;

  // Dynamic Table Capacity is the maximum allowed value of
  // |dynamic_table_size_|.  Entries are evicted if necessary before inserting a
  // new entry to ensure that dynamic table size never exceeds capacity.
  // Initial value is |maximum_dynamic_table_capacity_|.  Capacity can be
  // changed by the encoder, as long as it does not exceed
  // |maximum_dynamic_table_capacity_|.
  uint64_t dynamic_table_capacity_;

  // Maximum allowed value of |dynamic_table_capacity|.  The initial value is
  // zero.  Can be changed by SetMaximumDynamicTableCapacity().
  uint64_t maximum_dynamic_table_capacity_;

  // MaxEntries, see Section 3.2.2.  Calculated based on
  // |maximum_dynamic_table_capacity_|.
  uint64_t max_entries_;

  // The number of entries dropped from the dynamic table.
  uint64_t dropped_entry_count_;

  // Observers waiting to be notified, sorted by required insert count.
  std::multimap<uint64_t, Observer*> observers_;

  // True if any dynamic table entries have been referenced from a header block.
  // Set directly by the encoder or decoder.  Used for stats.
  bool dynamic_table_entry_referenced_;
};

}  // namespace quic

#endif  // QUICHE_QUIC_CORE_QPACK_QPACK_HEADER_TABLE_H_