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 "net/third_party/quiche/src/quic/platform/api/quic_export.h"
#include "net/third_party/quiche/src/quic/platform/api/quic_string_piece.h"
#include "net/third_party/quiche/src/spdy/core/hpack/hpack_entry.h"
#include "net/third_party/quiche/src/spdy/core/hpack/hpack_header_table.h"

namespace quic {

using QpackEntry = spdy::HpackEntry;

// 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 };

  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(QuicStringPiece name,
                            QuicStringPiece value,
                            bool* is_static,
                            uint64_t* index) const;

  // Insert (name, value) into the dynamic table.  May evict entries.  Returns a
  // pointer to the inserted owned entry on success.  Returns nullptr if entry
  // is larger than the capacity of the dynamic table.
  const QpackEntry* InsertEntry(QuicStringPiece name, QuicStringPiece value);

  // 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.
  void SetMaximumDynamicTableCapacity(uint64_t maximum_dynamic_table_capacity);

  // 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_; }

 private:
  // 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_;
};

}  // namespace quic

#endif  // QUICHE_QUIC_CORE_QPACK_QPACK_HEADER_TABLE_H_