blob: 39d7326758bacc8cc8ac8d7d96421508f6724118 [file] [log] [blame]
// 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.
#include <cstdint>
#include <functional>
#include <queue>
#include <vector>
#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 {
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 Observer {
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;
QpackHeaderTable(const QpackHeaderTable&) = delete;
QpackHeaderTable& operator=(const QpackHeaderTable&) = delete;
// 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);
// Register an observer to be notified when inserted_entry_count() reaches
// |required_insert_count|. After the notification, |observer| automatically
// gets unregistered.
void RegisterObserver(Observer* observer, uint64_t required_insert_count);
// 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_; }
// 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_;
// Data structure to hold an Observer and its threshold.
struct ObserverWithThreshold {
Observer* observer;
uint64_t required_insert_count;
bool operator>(const ObserverWithThreshold& other) const;
// Use std::greater so that entry with smallest |required_insert_count|
// is on top.
using ObserverHeap = std::priority_queue<ObserverWithThreshold,
// Observers waiting to be notified.
ObserverHeap observers_;
} // namespace quic