blob: 90b0d4c01a3d4e853541cd00cfc75ffad97f5b73 [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.
#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_