gfe-relnote: Move Http2PriorityWriteScheduler from gfe/gfe2/spdy/ to third_party/spdy/core/ to allow QUIC to use it. No functional change expected, not flag protected. Also copy gtl::intrusive_list as SpdyIntrusiveList. PiperOrigin-RevId: 259535206 Change-Id: Ie600cc4a403ac90a6302824f98bc5e7fd86fca25
diff --git a/spdy/core/http2_priority_write_scheduler.h b/spdy/core/http2_priority_write_scheduler.h new file mode 100644 index 0000000..1f72fdb --- /dev/null +++ b/spdy/core/http2_priority_write_scheduler.h
@@ -0,0 +1,774 @@ +// Copyright (c) 2019 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_SPDY_CORE_HTTP2_PRIORITY_WRITE_SCHEDULER_H_ +#define QUICHE_SPDY_CORE_HTTP2_PRIORITY_WRITE_SCHEDULER_H_ + +#include <cstdint> +#include <deque> +#include <map> +#include <memory> +#include <queue> +#include <set> +#include <tuple> +#include <unordered_map> +#include <utility> +#include <vector> + +#include "net/third_party/quiche/src/spdy/core/spdy_intrusive_list.h" +#include "net/third_party/quiche/src/spdy/core/spdy_protocol.h" +#include "net/third_party/quiche/src/spdy/core/write_scheduler.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_bug_tracker.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_containers.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_logging.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_map_util.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_ptr_util.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_utils.h" + +namespace spdy { + +namespace test { +template <typename StreamIdType> +class Http2PriorityWriteSchedulerPeer; +} + +// This data structure implements the HTTP/2 stream priority tree defined in +// section 5.3 of RFC 7540: +// http://tools.ietf.org/html/rfc7540#section-5.3 +// +// Streams can be added and removed, and dependencies between them defined. +// Streams constitute a tree rooted at stream ID 0: each stream has a single +// parent stream, and 0 or more child streams. Individual streams can be +// marked as ready to read/write, and then the whole structure can be queried +// to pick the next stream to read/write out of those that are ready. +template <typename StreamIdType> +class Http2PriorityWriteScheduler : public WriteScheduler<StreamIdType> { + public: + using typename WriteScheduler<StreamIdType>::StreamPrecedenceType; + + Http2PriorityWriteScheduler(); + Http2PriorityWriteScheduler(const Http2PriorityWriteScheduler&) = delete; + Http2PriorityWriteScheduler& operator=(const Http2PriorityWriteScheduler&) = + delete; + + // WriteScheduler methods + void RegisterStream(StreamIdType stream_id, + const StreamPrecedenceType& precedence) override; + void UnregisterStream(StreamIdType stream_id) override; + bool StreamRegistered(StreamIdType stream_id) const override; + StreamPrecedenceType GetStreamPrecedence( + StreamIdType stream_id) const override; + void UpdateStreamPrecedence(StreamIdType stream_id, + const StreamPrecedenceType& precedence) override; + std::vector<StreamIdType> GetStreamChildren( + StreamIdType stream_id) const override; + void RecordStreamEventTime(StreamIdType stream_id, + int64_t now_in_usec) override; + int64_t GetLatestEventWithPrecedence(StreamIdType stream_id) const override; + bool ShouldYield(StreamIdType stream_id) const override; + void MarkStreamReady(StreamIdType stream_id, bool add_to_front) override; + void MarkStreamNotReady(StreamIdType stream_id) override; + bool HasReadyStreams() const override; + StreamIdType PopNextReadyStream() override; + std::tuple<StreamIdType, StreamPrecedenceType> + PopNextReadyStreamAndPrecedence() override; + size_t NumReadyStreams() const override; + bool IsStreamReady(StreamIdType stream_id) const override; + SpdyString DebugString() const override; + + // Return the number of streams currently in the tree. + int num_streams() const; + + private: + friend class test::Http2PriorityWriteSchedulerPeer<StreamIdType>; + + struct StreamInfo; + typedef SpdyInlinedVector<StreamInfo*, 4> StreamInfoVector; + + struct StreamInfo : public SpdyIntrusiveLink<StreamInfo> { + // ID for this stream. + StreamIdType id; + // StreamInfo for parent stream. + StreamInfo* parent = nullptr; + // Weights can range between 1 and 256 (inclusive). + int weight = kHttp2DefaultStreamWeight; + // The total weight of this stream's direct descendants. + int total_child_weights = 0; + // Pointers to StreamInfos for children, if any. + StreamInfoVector children; + // Whether the stream is ready for writing. The stream is present in + // scheduling_queue_ iff true. + bool ready = false; + // The scheduling priority of this stream. Streams with higher priority + // values are scheduled first. + // TODO(mpw): rename to avoid confusion with SPDY priorities, + // which this is not. + float priority = 0; + // Ordinal value for this stream, used to ensure round-robin scheduling: + // among streams with the same scheduling priority, streams with lower + // ordinal are scheduled first. + int64_t ordinal = 0; + // Time of latest write event for stream of this priority, in microseconds. + int64_t last_event_time_usec = 0; + + // Whether this stream should be scheduled ahead of another stream. + bool SchedulesBefore(const StreamInfo& other) const { + return (priority != other.priority) ? priority > other.priority + : ordinal < other.ordinal; + } + + // Returns the StreamPrecedenceType for this StreamInfo. + StreamPrecedenceType ToStreamPrecedence() const { + StreamIdType parent_id = + parent == nullptr ? kHttp2RootStreamId : parent->id; + bool exclusive = parent != nullptr && parent->children.size() == 1; + return StreamPrecedenceType(parent_id, weight, exclusive); + } + }; + + static bool Remove(StreamInfoVector* stream_infos, + const StreamInfo* stream_info); + + // Returns true iff any direct or transitive parent of the given stream is + // currently ready. + static bool HasReadyAncestor(const StreamInfo& stream_info); + + // Returns StreamInfo for the given stream, or nullptr if it isn't + // registered. + const StreamInfo* FindStream(StreamIdType stream_id) const; + StreamInfo* FindStream(StreamIdType stream_id); + + // Helpers for UpdateStreamPrecedence(). + void UpdateStreamParent(StreamInfo* stream_info, + StreamIdType parent_id, + bool exclusive); + void UpdateStreamWeight(StreamInfo* stream_info, int weight); + + // Update all priority values in the subtree rooted at the given stream, not + // including the stream itself. If this results in priority value changes for + // scheduled streams, those streams are rescheduled to ensure proper ordering + // of scheduling_queue_. + // TODO(mpw): rename to avoid confusion with SPDY priorities. + void UpdatePrioritiesUnder(StreamInfo* stream_info); + + // Inserts stream into scheduling_queue_ at the appropriate location given + // its priority and ordinal. Time complexity is O(scheduling_queue.size()). + void Schedule(StreamInfo* stream_info); + + // Removes stream from scheduling_queue_. + void Unschedule(StreamInfo* stream_info); + + // Return true if all internal invariants hold (useful for unit tests). + // Unless there are bugs, this should always return true. + bool ValidateInvariantsForTests() const; + + // Returns true if the parent stream has the given stream in its children. + bool StreamHasChild(const StreamInfo& parent_info, + const StreamInfo* child_info) const; + + // Pointee owned by all_stream_infos_. + StreamInfo* root_stream_info_; + // Maps from stream IDs to StreamInfo objects. + SpdySmallMap<StreamIdType, std::unique_ptr<StreamInfo>, 10> all_stream_infos_; + // Queue containing all ready streams, ordered with streams of higher + // priority before streams of lower priority, and, among streams of equal + // priority, streams with lower ordinal before those with higher + // ordinal. Note that not all streams in scheduling_queue_ are eligible to be + // picked as the next stream: some may have ancestor stream(s) that are ready + // and unblocked. In these situations the occluded child streams are left in + // the queue, to reduce churn. + SpdyIntrusiveList<StreamInfo> scheduling_queue_; + // Ordinal value to assign to next node inserted into scheduling_queue_ when + // |add_to_front == true|. Decremented after each assignment. + int64_t head_ordinal_ = -1; + // Ordinal value to assign to next node inserted into scheduling_queue_ when + // |add_to_front == false|. Incremented after each assignment. + int64_t tail_ordinal_ = 0; +}; + +template <typename StreamIdType> +Http2PriorityWriteScheduler<StreamIdType>::Http2PriorityWriteScheduler() { + auto root_stream_info = SpdyMakeUnique<StreamInfo>(); + root_stream_info_ = root_stream_info.get(); + root_stream_info->id = kHttp2RootStreamId; + root_stream_info->weight = kHttp2DefaultStreamWeight; + root_stream_info->parent = nullptr; + root_stream_info->priority = 1.0; + root_stream_info->ready = false; + all_stream_infos_[kHttp2RootStreamId] = std::move(root_stream_info); +} + +template <typename StreamIdType> +int Http2PriorityWriteScheduler<StreamIdType>::num_streams() const { + return all_stream_infos_.size(); +} + +template <typename StreamIdType> +bool Http2PriorityWriteScheduler<StreamIdType>::StreamRegistered( + StreamIdType stream_id) const { + return SpdyContainsKey(all_stream_infos_, stream_id); +} + +template <typename StreamIdType> +void Http2PriorityWriteScheduler<StreamIdType>::RegisterStream( + StreamIdType stream_id, + const StreamPrecedenceType& precedence) { + // TODO(mpw): uncomment the SPDY_BUG_IF below once all tests + // (e.g. SpdyClientDispatcher) modified to pass StreamPrecedence instances + // appropriate for protocol version under test. + // + // SPDY_BUG_IF(precedence.is_spdy3_priority()) + // << "Expected HTTP/2 stream dependency"; + + if (StreamRegistered(stream_id)) { + SPDY_BUG << "Stream " << stream_id << " already registered"; + return; + } + + StreamInfo* parent = FindStream(precedence.parent_id()); + if (parent == nullptr) { + // parent_id may legitimately not be registered yet--see b/15676312. + SPDY_VLOG(1) << "Parent stream " << precedence.parent_id() + << " not registered"; + parent = root_stream_info_; + } + + auto new_stream_info = SpdyMakeUnique<StreamInfo>(); + StreamInfo* new_stream_info_ptr = new_stream_info.get(); + new_stream_info_ptr->id = stream_id; + new_stream_info_ptr->weight = precedence.weight(); + new_stream_info_ptr->parent = parent; + all_stream_infos_[stream_id] = std::move(new_stream_info); + if (precedence.is_exclusive()) { + // Move the parent's current children below the new stream. + using std::swap; + swap(new_stream_info_ptr->children, parent->children); + new_stream_info_ptr->total_child_weights = parent->total_child_weights; + // Update each child's parent. + for (StreamInfo* child : new_stream_info_ptr->children) { + child->parent = new_stream_info_ptr; + } + // Clear parent's old child data. + DCHECK(parent->children.empty()); + parent->total_child_weights = 0; + } + // Add new stream to parent. + parent->children.push_back(new_stream_info_ptr); + parent->total_child_weights += precedence.weight(); + + // Update all priorities under parent, since addition of a stream affects + // sibling priorities as well. + UpdatePrioritiesUnder(parent); + + // Stream starts with ready == false, so no need to schedule it yet. + DCHECK(!new_stream_info_ptr->ready); +} + +template <typename StreamIdType> +void Http2PriorityWriteScheduler<StreamIdType>::UnregisterStream( + StreamIdType stream_id) { + if (stream_id == kHttp2RootStreamId) { + SPDY_BUG << "Cannot unregister root stream"; + return; + } + // Remove the stream from table. + auto it = all_stream_infos_.find(stream_id); + if (it == all_stream_infos_.end()) { + SPDY_BUG << "Stream " << stream_id << " not registered"; + return; + } + std::unique_ptr<StreamInfo> stream_info(std::move(it->second)); + all_stream_infos_.erase(it); + // If ready (and hence scheduled), unschedule. + if (stream_info->ready) { + Unschedule(stream_info.get()); + } + + StreamInfo* parent = stream_info->parent; + // Remove the stream from parent's child list. + Remove(&parent->children, stream_info.get()); + parent->total_child_weights -= stream_info->weight; + + // Move the stream's children to the parent's child list. + // Update each child's parent and weight. + for (StreamInfo* child : stream_info->children) { + child->parent = parent; + parent->children.push_back(child); + // Divide the removed stream's weight among its children, rounding to the + // nearest valid weight. + float float_weight = stream_info->weight * + static_cast<float>(child->weight) / + static_cast<float>(stream_info->total_child_weights); + int new_weight = floor(float_weight + 0.5); + if (new_weight == 0) { + new_weight = 1; + } + child->weight = new_weight; + parent->total_child_weights += child->weight; + } + UpdatePrioritiesUnder(parent); +} + +template <typename StreamIdType> +typename Http2PriorityWriteScheduler<StreamIdType>::StreamPrecedenceType +Http2PriorityWriteScheduler<StreamIdType>::GetStreamPrecedence( + StreamIdType stream_id) const { + const StreamInfo* stream_info = FindStream(stream_id); + if (stream_info == nullptr) { + // Unknown streams tolerated due to b/15676312. However, return lowest + // weight. + SPDY_VLOG(1) << "Stream " << stream_id << " not registered"; + return StreamPrecedenceType(kHttp2RootStreamId, kHttp2MinStreamWeight, + false); + } + return stream_info->ToStreamPrecedence(); +} + +template <typename StreamIdType> +std::vector<StreamIdType> +Http2PriorityWriteScheduler<StreamIdType>::GetStreamChildren( + StreamIdType stream_id) const { + std::vector<StreamIdType> child_vec; + const StreamInfo* stream_info = FindStream(stream_id); + if (stream_info == nullptr) { + SPDY_BUG << "Stream " << stream_id << " not registered"; + } else { + child_vec.reserve(stream_info->children.size()); + for (StreamInfo* child : stream_info->children) { + child_vec.push_back(child->id); + } + } + return child_vec; +} + +template <typename StreamIdType> +void Http2PriorityWriteScheduler<StreamIdType>::UpdateStreamPrecedence( + StreamIdType stream_id, + const StreamPrecedenceType& precedence) { + // TODO(mpw): uncomment the SPDY_BUG_IF below once all tests + // (e.g. SpdyClientDispatcher) modified to pass StreamPrecedence instances + // appropriate for protocol version under test. + // + // SPDY_BUG_IF(precedence.is_spdy3_priority()) + // << "Expected HTTP/2 stream dependency"; + if (stream_id == kHttp2RootStreamId) { + SPDY_BUG << "Cannot set precedence of root stream"; + return; + } + + StreamInfo* stream_info = FindStream(stream_id); + if (stream_info == nullptr) { + // TODO(mpw): add to all_stream_infos_ on demand--see b/15676312. + SPDY_VLOG(1) << "Stream " << stream_id << " not registered"; + return; + } + UpdateStreamParent(stream_info, precedence.parent_id(), + precedence.is_exclusive()); + UpdateStreamWeight(stream_info, precedence.weight()); +} + +template <typename StreamIdType> +void Http2PriorityWriteScheduler<StreamIdType>::UpdateStreamWeight( + StreamInfo* stream_info, + int weight) { + if (weight == stream_info->weight) { + return; + } + if (stream_info->parent != nullptr) { + stream_info->parent->total_child_weights += (weight - stream_info->weight); + } + stream_info->weight = weight; + + // Change in weight also affects sibling priorities. + UpdatePrioritiesUnder(stream_info->parent); +} + +template <typename StreamIdType> +void Http2PriorityWriteScheduler<StreamIdType>::UpdateStreamParent( + StreamInfo* stream_info, + StreamIdType parent_id, + bool exclusive) { + if (stream_info->id == parent_id) { + SPDY_BUG << "Cannot set stream to be its own parent"; + return; + } + StreamInfo* new_parent = FindStream(parent_id); + if (new_parent == nullptr) { + // parent_id may legitimately not be registered yet--see b/15676312. + SPDY_VLOG(1) << "Parent stream " << parent_id << " not registered"; + return; + } + + // If the new parent is already the stream's parent, we're done. + if (stream_info->parent == new_parent) { + return; + } + + // Next, check to see if the new parent is currently a descendant + // of the stream. + StreamInfo* last = new_parent->parent; + bool cycle_exists = false; + while (last != nullptr) { + if (last == stream_info) { + cycle_exists = true; + break; + } + last = last->parent; + } + + if (cycle_exists) { + // The new parent moves to the level of the current stream. + UpdateStreamParent(new_parent, stream_info->parent->id, false); + } + + // Remove stream from old parent's child list. + StreamInfo* old_parent = stream_info->parent; + Remove(&old_parent->children, stream_info); + old_parent->total_child_weights -= stream_info->weight; + UpdatePrioritiesUnder(old_parent); + + if (exclusive) { + // Move the new parent's current children below the current stream. + for (StreamInfo* child : new_parent->children) { + child->parent = stream_info; + stream_info->children.push_back(child); + } + stream_info->total_child_weights += new_parent->total_child_weights; + // Clear new parent's old child data. + new_parent->children.clear(); + new_parent->total_child_weights = 0; + } + + // Make the change. + stream_info->parent = new_parent; + new_parent->children.push_back(stream_info); + new_parent->total_child_weights += stream_info->weight; + UpdatePrioritiesUnder(new_parent); +} + +template <typename StreamIdType> +void Http2PriorityWriteScheduler<StreamIdType>::RecordStreamEventTime( + StreamIdType stream_id, + int64_t now_in_usec) { + if (stream_id == kHttp2RootStreamId) { + SPDY_BUG << "Cannot record event time for root stream"; + return; + } + StreamInfo* stream_info = FindStream(stream_id); + if (stream_info == nullptr) { + SPDY_BUG << "Stream " << stream_id << " not registered"; + return; + } + stream_info->last_event_time_usec = now_in_usec; +} + +// O(n) in the number of streams, which isn't great. However, this method will +// soon be superseded by +// Http2WeightedWriteScheduler::GetLatestEventWithPrecedence(), for which an +// efficient implementation is straightforward. Also, this method is only +// called when calculating idle timeouts, so performance isn't key. +template <typename StreamIdType> +int64_t Http2PriorityWriteScheduler<StreamIdType>::GetLatestEventWithPrecedence( + StreamIdType stream_id) const { + if (stream_id == kHttp2RootStreamId) { + SPDY_BUG << "Invalid argument: root stream"; + return 0; + } + const StreamInfo* stream_info = FindStream(stream_id); + if (stream_info == nullptr) { + SPDY_BUG << "Stream " << stream_id << " not registered"; + return 0; + } + int64_t last_event_time_usec = 0; + for (const auto& kv : all_stream_infos_) { + const StreamInfo& other = *kv.second; + if (other.priority > stream_info->priority) { + last_event_time_usec = + std::max(last_event_time_usec, other.last_event_time_usec); + } + } + return last_event_time_usec; +} + +// Worst-case time complexity of O(n*d), where n is scheduling queue length and +// d is tree depth. In practice, should be much shorter, since loop terminates +// at first writable stream or |stream_id| (whichever is first). +template <typename StreamIdType> +bool Http2PriorityWriteScheduler<StreamIdType>::ShouldYield( + StreamIdType stream_id) const { + if (stream_id == kHttp2RootStreamId) { + SPDY_BUG << "Invalid argument: root stream"; + return false; + } + const StreamInfo* stream_info = FindStream(stream_id); + if (stream_info == nullptr) { + SPDY_BUG << "Stream " << stream_id << " not registered"; + return false; + } + for (const StreamInfo& scheduled : scheduling_queue_) { + if (stream_info == &scheduled) { + return false; + } + if (!HasReadyAncestor(scheduled)) { + return true; + } + } + return false; +} + +template <typename StreamIdType> +void Http2PriorityWriteScheduler<StreamIdType>::MarkStreamReady( + StreamIdType stream_id, + bool add_to_front) { + if (stream_id == kHttp2RootStreamId) { + SPDY_BUG << "Cannot mark root stream ready"; + return; + } + StreamInfo* stream_info = FindStream(stream_id); + if (stream_info == nullptr) { + SPDY_BUG << "Stream " << stream_id << " not registered"; + return; + } + if (stream_info->ready) { + return; + } + stream_info->ordinal = add_to_front ? head_ordinal_-- : tail_ordinal_++; + Schedule(stream_info); +} + +template <typename StreamIdType> +void Http2PriorityWriteScheduler<StreamIdType>::MarkStreamNotReady( + StreamIdType stream_id) { + if (stream_id == kHttp2RootStreamId) { + SPDY_BUG << "Cannot mark root stream unready"; + return; + } + StreamInfo* stream_info = FindStream(stream_id); + if (stream_info == nullptr) { + SPDY_BUG << "Stream " << stream_id << " not registered"; + return; + } + if (!stream_info->ready) { + return; + } + Unschedule(stream_info); +} + +template <typename StreamIdType> +bool Http2PriorityWriteScheduler<StreamIdType>::Remove( + StreamInfoVector* stream_infos, + const StreamInfo* stream_info) { + for (typename StreamInfoVector::iterator it = stream_infos->begin(); + it != stream_infos->end(); ++it) { + if (*it == stream_info) { + stream_infos->erase(it); + return true; + } + } + return false; +} + +template <typename StreamIdType> +bool Http2PriorityWriteScheduler<StreamIdType>::HasReadyAncestor( + const StreamInfo& stream_info) { + for (const StreamInfo* parent = stream_info.parent; parent != nullptr; + parent = parent->parent) { + if (parent->ready) { + return true; + } + } + return false; +} + +template <typename StreamIdType> +const typename Http2PriorityWriteScheduler<StreamIdType>::StreamInfo* +Http2PriorityWriteScheduler<StreamIdType>::FindStream( + StreamIdType stream_id) const { + auto it = all_stream_infos_.find(stream_id); + return it == all_stream_infos_.end() ? nullptr : it->second.get(); +} + +template <typename StreamIdType> +typename Http2PriorityWriteScheduler<StreamIdType>::StreamInfo* +Http2PriorityWriteScheduler<StreamIdType>::FindStream(StreamIdType stream_id) { + auto it = all_stream_infos_.find(stream_id); + return it == all_stream_infos_.end() ? nullptr : it->second.get(); +} + +template <typename StreamIdType> +void Http2PriorityWriteScheduler<StreamIdType>::UpdatePrioritiesUnder( + StreamInfo* stream_info) { + for (StreamInfo* child : stream_info->children) { + child->priority = stream_info->priority * + (static_cast<float>(child->weight) / + static_cast<float>(stream_info->total_child_weights)); + if (child->ready) { + // Reposition in scheduling_queue_. Use post-order for scheduling, to + // benefit from the fact that children have priority <= parent priority. + Unschedule(child); + UpdatePrioritiesUnder(child); + Schedule(child); + } else { + UpdatePrioritiesUnder(child); + } + } +} + +template <typename StreamIdType> +void Http2PriorityWriteScheduler<StreamIdType>::Schedule( + StreamInfo* stream_info) { + DCHECK(!stream_info->ready); + for (StreamInfo& s : scheduling_queue_) { + if (stream_info->SchedulesBefore(s)) { + scheduling_queue_.insert(&s, stream_info); + stream_info->ready = true; + return; + } + } + scheduling_queue_.push_back(stream_info); + stream_info->ready = true; +} + +template <typename StreamIdType> +void Http2PriorityWriteScheduler<StreamIdType>::Unschedule( + StreamInfo* stream_info) { + DCHECK(stream_info->ready); + scheduling_queue_.erase(stream_info); + stream_info->ready = false; +} + +template <typename StreamIdType> +bool Http2PriorityWriteScheduler<StreamIdType>::StreamHasChild( + const StreamInfo& parent_info, + const StreamInfo* child_info) const { + auto found = std::find(parent_info.children.begin(), + parent_info.children.end(), child_info); + return found != parent_info.children.end(); +} + +template <typename StreamIdType> +bool Http2PriorityWriteScheduler<StreamIdType>::HasReadyStreams() const { + return !scheduling_queue_.empty(); +} + +template <typename StreamIdType> +StreamIdType Http2PriorityWriteScheduler<StreamIdType>::PopNextReadyStream() { + return std::get<0>(PopNextReadyStreamAndPrecedence()); +} + +template <typename StreamIdType> +std::tuple< + StreamIdType, + typename Http2PriorityWriteScheduler<StreamIdType>::StreamPrecedenceType> +Http2PriorityWriteScheduler<StreamIdType>::PopNextReadyStreamAndPrecedence() { + for (StreamInfo& stream_info : scheduling_queue_) { + if (!HasReadyAncestor(stream_info)) { + Unschedule(&stream_info); + return std::make_tuple(stream_info.id, stream_info.ToStreamPrecedence()); + } + } + SPDY_BUG << "No ready streams"; + return std::make_tuple( + kHttp2RootStreamId, + StreamPrecedenceType(kHttp2RootStreamId, kHttp2MinStreamWeight, false)); +} + +template <typename StreamIdType> +size_t Http2PriorityWriteScheduler<StreamIdType>::NumReadyStreams() const { + return scheduling_queue_.size(); +} + +template <typename StreamIdType> +bool Http2PriorityWriteScheduler<StreamIdType>::IsStreamReady( + StreamIdType stream_id) const { + if (stream_id == kHttp2RootStreamId) { + SPDY_BUG << "Try to check whether root stream is ready"; + return false; + } + const StreamInfo* stream_info = FindStream(stream_id); + if (stream_info == nullptr) { + SPDY_BUG << "Stream " << stream_id << " not registered"; + return false; + } + return stream_info->ready; +} + +template <typename StreamIdType> +SpdyString Http2PriorityWriteScheduler<StreamIdType>::DebugString() const { + return SpdyStrCat("Http2PriorityWriteScheduler {num_streams=", num_streams(), + " num_ready_streams=", NumReadyStreams(), "}"); +} + +template <typename StreamIdType> +bool Http2PriorityWriteScheduler<StreamIdType>::ValidateInvariantsForTests() + const { + int total_streams = 0; + int streams_visited = 0; + // Iterate through all streams in the map. + for (const auto& kv : all_stream_infos_) { + ++total_streams; + ++streams_visited; + StreamIdType stream_id = kv.first; + const StreamInfo& stream_info = *kv.second; + + // Verify each StreamInfo mapped under the proper stream ID. + if (stream_id != stream_info.id) { + SPDY_DLOG(INFO) << "Stream ID " << stream_id + << " maps to StreamInfo with ID " << stream_info.id; + return false; + } + + // All streams except the root should have a parent, and should appear in + // the children of that parent. + if (stream_info.id != kHttp2RootStreamId && + !StreamHasChild(*stream_info.parent, &stream_info)) { + SPDY_DLOG(INFO) << "Parent stream " << stream_info.parent->id + << " is not registered, or does not list stream " + << stream_info.id << " as its child."; + return false; + } + + if (!stream_info.children.empty()) { + int total_child_weights = 0; + // Iterate through the stream's children. + for (StreamInfo* child : stream_info.children) { + ++streams_visited; + // Each stream in the list should exist and should have this stream + // set as its parent. + if (!StreamRegistered(child->id) || child->parent != &stream_info) { + SPDY_DLOG(INFO) << "Child stream " << child->id + << " is not registered, " + << "or does not list " << stream_info.id + << " as its parent."; + return false; + } + total_child_weights += child->weight; + } + // Verify that total_child_weights is correct. + if (total_child_weights != stream_info.total_child_weights) { + SPDY_DLOG(INFO) << "Child weight totals do not agree. For stream " + << stream_info.id << " total_child_weights has value " + << stream_info.total_child_weights << ", expected " + << total_child_weights; + return false; + } + } + } + + // Make sure num_streams reflects the total number of streams the map + // contains. + if (total_streams != num_streams()) { + SPDY_DLOG(INFO) << "Map contains incorrect number of streams."; + return false; + } + // Validate the validation function; we should have visited each stream twice + // (except for the root) + DCHECK(streams_visited == 2 * num_streams() - 1); + return true; +} + +} // namespace spdy + +#endif // QUICHE_SPDY_CORE_HTTP2_PRIORITY_WRITE_SCHEDULER_H_
diff --git a/spdy/core/http2_priority_write_scheduler_test.cc b/spdy/core/http2_priority_write_scheduler_test.cc new file mode 100644 index 0000000..17b7721 --- /dev/null +++ b/spdy/core/http2_priority_write_scheduler_test.cc
@@ -0,0 +1,799 @@ +#include "net/third_party/quiche/src/spdy/core/http2_priority_write_scheduler.h" + +#include <initializer_list> + +#include "net/third_party/quiche/src/spdy/platform/api/spdy_test.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_test_helpers.h" + +using ::testing::AssertionFailure; +using ::testing::AssertionResult; +using ::testing::AssertionSuccess; +using ::testing::ElementsAre; +using ::testing::IsEmpty; +using ::testing::UnorderedElementsAre; + +namespace spdy { + +namespace test { + +template <typename StreamIdType> +class Http2PriorityWriteSchedulerPeer { + public: + explicit Http2PriorityWriteSchedulerPeer( + Http2PriorityWriteScheduler<StreamIdType>* scheduler) + : scheduler_(scheduler) {} + + int TotalChildWeights(StreamIdType stream_id) const { + return scheduler_->FindStream(stream_id)->total_child_weights; + } + + bool ValidateInvariants() const { + return scheduler_->ValidateInvariantsForTests(); + } + + private: + Http2PriorityWriteScheduler<StreamIdType>* scheduler_; +}; + +class Http2PriorityWriteSchedulerTest : public ::testing::Test { + protected: + typedef uint32_t SpdyStreamId; + + Http2PriorityWriteSchedulerTest() : peer_(&scheduler_) {} + + Http2PriorityWriteScheduler<SpdyStreamId> scheduler_; + Http2PriorityWriteSchedulerPeer<SpdyStreamId> peer_; +}; + +TEST_F(Http2PriorityWriteSchedulerTest, RegisterAndUnregisterStreams) { + EXPECT_EQ(1, scheduler_.num_streams()); + EXPECT_TRUE(scheduler_.StreamRegistered(0)); + EXPECT_FALSE(scheduler_.StreamRegistered(1)); + + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); + EXPECT_EQ(2, scheduler_.num_streams()); + ASSERT_TRUE(scheduler_.StreamRegistered(1)); + EXPECT_EQ(100, scheduler_.GetStreamPrecedence(1).weight()); + EXPECT_FALSE(scheduler_.StreamRegistered(5)); + EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(1)); + + scheduler_.RegisterStream(5, SpdyStreamPrecedence(0, 50, false)); + // Should not be able to add a stream with an id that already exists. + EXPECT_SPDY_BUG( + scheduler_.RegisterStream(5, SpdyStreamPrecedence(1, 50, false)), + "Stream 5 already registered"); + EXPECT_EQ(3, scheduler_.num_streams()); + EXPECT_TRUE(scheduler_.StreamRegistered(1)); + ASSERT_TRUE(scheduler_.StreamRegistered(5)); + EXPECT_EQ(50, scheduler_.GetStreamPrecedence(5).weight()); + EXPECT_FALSE(scheduler_.StreamRegistered(13)); + + scheduler_.RegisterStream(13, SpdyStreamPrecedence(5, 130, true)); + EXPECT_EQ(4, scheduler_.num_streams()); + EXPECT_TRUE(scheduler_.StreamRegistered(1)); + EXPECT_TRUE(scheduler_.StreamRegistered(5)); + ASSERT_TRUE(scheduler_.StreamRegistered(13)); + EXPECT_EQ(130, scheduler_.GetStreamPrecedence(13).weight()); + EXPECT_EQ(5, scheduler_.GetStreamPrecedence(13).parent_id()); + + scheduler_.UnregisterStream(5); + // Cannot remove a stream that has already been removed. + EXPECT_SPDY_BUG(scheduler_.UnregisterStream(5), "Stream 5 not registered"); + EXPECT_EQ(3, scheduler_.num_streams()); + EXPECT_TRUE(scheduler_.StreamRegistered(1)); + EXPECT_FALSE(scheduler_.StreamRegistered(5)); + EXPECT_TRUE(scheduler_.StreamRegistered(13)); + EXPECT_EQ(kHttp2RootStreamId, scheduler_.GetStreamPrecedence(13).parent_id()); + + // The parent stream 19 doesn't exist, so this should use 0 as parent stream: + scheduler_.RegisterStream(7, SpdyStreamPrecedence(19, 70, false)); + EXPECT_TRUE(scheduler_.StreamRegistered(7)); + EXPECT_EQ(0, scheduler_.GetStreamPrecedence(7).parent_id()); + // Now stream 7 already exists, so this should fail: + EXPECT_SPDY_BUG( + scheduler_.RegisterStream(7, SpdyStreamPrecedence(1, 70, false)), + "Stream 7 already registered"); + // Try adding a second child to stream 13: + scheduler_.RegisterStream(17, SpdyStreamPrecedence(13, 170, false)); + + scheduler_.UpdateStreamPrecedence(17, SpdyStreamPrecedence(13, 150, false)); + EXPECT_EQ(150, scheduler_.GetStreamPrecedence(17).weight()); + + ASSERT_TRUE(peer_.ValidateInvariants()); +} + +TEST_F(Http2PriorityWriteSchedulerTest, RegisterStreamWithSpdy3Priority) { + EXPECT_FALSE(scheduler_.StreamRegistered(1)); + scheduler_.RegisterStream(1, SpdyStreamPrecedence(3)); + EXPECT_EQ(0, scheduler_.NumReadyStreams()); + EXPECT_TRUE(scheduler_.StreamRegistered(1)); + EXPECT_EQ(3, scheduler_.GetStreamPrecedence(1).spdy3_priority()); + EXPECT_EQ(147, scheduler_.GetStreamPrecedence(1).weight()); + EXPECT_EQ(kHttp2RootStreamId, scheduler_.GetStreamPrecedence(1).parent_id()); + EXPECT_THAT(scheduler_.GetStreamChildren(1), IsEmpty()); + + EXPECT_SPDY_BUG(scheduler_.RegisterStream(1, SpdyStreamPrecedence(4)), + "Expected HTTP/2 stream dependency|" + "Stream 1 already registered"); + EXPECT_EQ(3, scheduler_.GetStreamPrecedence(1).spdy3_priority()); +} + +TEST_F(Http2PriorityWriteSchedulerTest, GetStreamWeight) { + // Unknown streams tolerated due to b/15676312. + EXPECT_EQ(kHttp2MinStreamWeight, scheduler_.GetStreamPrecedence(3).weight()); + scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 130, true)); + EXPECT_EQ(130, scheduler_.GetStreamPrecedence(3).weight()); + scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 50, true)); + EXPECT_EQ(50, scheduler_.GetStreamPrecedence(3).weight()); + scheduler_.UnregisterStream(3); + EXPECT_EQ(kHttp2MinStreamWeight, scheduler_.GetStreamPrecedence(3).weight()); +} + +TEST_F(Http2PriorityWriteSchedulerTest, GetStreamPriority) { + // Unknown streams tolerated due to b/15676312. + EXPECT_EQ(kV3LowestPriority, + scheduler_.GetStreamPrecedence(3).spdy3_priority()); + scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 130, true)); + EXPECT_EQ(3, scheduler_.GetStreamPrecedence(3).spdy3_priority()); + scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 50, true)); + EXPECT_EQ(5, scheduler_.GetStreamPrecedence(3).spdy3_priority()); + scheduler_.UnregisterStream(3); + EXPECT_EQ(kV3LowestPriority, + scheduler_.GetStreamPrecedence(3).spdy3_priority()); +} + +TEST_F(Http2PriorityWriteSchedulerTest, GetStreamParent) { + // Unknown streams tolerated due to b/15676312. + EXPECT_EQ(kHttp2RootStreamId, scheduler_.GetStreamPrecedence(3).parent_id()); + scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 20, false)); + scheduler_.RegisterStream(3, SpdyStreamPrecedence(2, 30, false)); + EXPECT_EQ(2, scheduler_.GetStreamPrecedence(3).parent_id()); + scheduler_.UnregisterStream(3); + EXPECT_EQ(kHttp2RootStreamId, scheduler_.GetStreamPrecedence(3).parent_id()); +} + +TEST_F(Http2PriorityWriteSchedulerTest, GetStreamChildren) { + EXPECT_SPDY_BUG(EXPECT_THAT(scheduler_.GetStreamChildren(7), IsEmpty()), + "Stream 7 not registered"); + scheduler_.RegisterStream(7, SpdyStreamPrecedence(0, 70, false)); + EXPECT_THAT(scheduler_.GetStreamChildren(7), IsEmpty()); + scheduler_.RegisterStream(9, SpdyStreamPrecedence(7, 90, false)); + scheduler_.RegisterStream(15, SpdyStreamPrecedence(7, 150, false)); + EXPECT_THAT(scheduler_.GetStreamChildren(7), UnorderedElementsAre(9, 15)); + scheduler_.UnregisterStream(7); + EXPECT_SPDY_BUG(EXPECT_THAT(scheduler_.GetStreamChildren(7), IsEmpty()), + "Stream 7 not registered"); +} + +TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamWeight) { + EXPECT_SPDY_BUG( + scheduler_.UpdateStreamPrecedence(0, SpdyStreamPrecedence(0, 10, false)), + "Cannot set precedence of root stream"); + + // For the moment, updating stream precedence on a non-registered stream + // should have no effect. In the future, it will lazily cause the stream to + // be registered (b/15676312). + scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 10, false)); + EXPECT_FALSE(scheduler_.StreamRegistered(3)); + + scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 10, false)); + scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 20, false)); + EXPECT_EQ(20, scheduler_.GetStreamPrecedence(3).weight()); + ASSERT_TRUE(peer_.ValidateInvariants()); + + EXPECT_SPDY_BUG( + scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 500, false)), + "Invalid weight: 500"); + EXPECT_EQ(kHttp2MaxStreamWeight, scheduler_.GetStreamPrecedence(3).weight()); + EXPECT_SPDY_BUG( + scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 0, false)), + "Invalid weight: 0"); + EXPECT_EQ(kHttp2MinStreamWeight, scheduler_.GetStreamPrecedence(3).weight()); + ASSERT_TRUE(peer_.ValidateInvariants()); + + scheduler_.UnregisterStream(3); +} + +// Basic case of reparenting a subtree. +TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentBasicNonExclusive) { + /* Tree: + 0 + / \ + 1 2 + / \ + 3 4 + */ + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false)); + scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(2, 100, false)); + EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(2)); + EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(3, 4)); + EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(1)); + EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); + EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty()); + ASSERT_TRUE(peer_.ValidateInvariants()); +} + +// Basic case of reparenting a subtree. Result here is the same as the +// non-exclusive case. +TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentBasicExclusive) { + /* Tree: + 0 + / \ + 1 2 + / \ + 3 4 + */ + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false)); + scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(2, 100, true)); + EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(2)); + EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(3, 4)); + EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(1)); + EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); + EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty()); + ASSERT_TRUE(peer_.ValidateInvariants()); +} + +// We can't set the parent of a nonexistent stream, or set the parent to a +// nonexistent stream. +TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentNonexistent) { + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false)); + for (bool exclusive : {true, false}) { + // For the moment, updating stream precedence on a non-registered stream or + // attempting to set parent to a nonexistent stream should have no + // effect. In the future, it will lazily cause the stream(s) to be + // registered (b/15676312). + + // No-op: parent stream 3 not registered + scheduler_.UpdateStreamPrecedence(1, + SpdyStreamPrecedence(3, 100, exclusive)); + + // No-op: stream 4 not registered + scheduler_.UpdateStreamPrecedence(4, + SpdyStreamPrecedence(2, 100, exclusive)); + + // No-op: stream 3 not registered + scheduler_.UpdateStreamPrecedence(3, + SpdyStreamPrecedence(4, 100, exclusive)); + + EXPECT_THAT(scheduler_.GetStreamChildren(0), UnorderedElementsAre(1, 2)); + EXPECT_THAT(scheduler_.GetStreamChildren(1), IsEmpty()); + EXPECT_THAT(scheduler_.GetStreamChildren(2), IsEmpty()); + EXPECT_FALSE(scheduler_.StreamRegistered(3)); + EXPECT_FALSE(scheduler_.StreamRegistered(4)); + } + ASSERT_TRUE(peer_.ValidateInvariants()); +} + +// We should be able to add multiple children to streams. +TEST_F(Http2PriorityWriteSchedulerTest, + UpdateStreamParentMultipleChildrenNonExclusive) { + /* Tree: + 0 + / \ + 1 2 + / \ \ + 3 4 5 + */ + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(5, SpdyStreamPrecedence(2, 100, false)); + scheduler_.UpdateStreamPrecedence(2, SpdyStreamPrecedence(1, 100, false)); + EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(1)); + EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(2, 3, 4)); + EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(5)); + EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); + EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty()); + EXPECT_THAT(scheduler_.GetStreamChildren(5), IsEmpty()); + ASSERT_TRUE(peer_.ValidateInvariants()); +} + +TEST_F(Http2PriorityWriteSchedulerTest, + UpdateStreamParentMultipleChildrenExclusive) { + /* Tree: + 0 + / \ + 1 2 + / \ \ + 3 4 5 + */ + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(5, SpdyStreamPrecedence(2, 100, false)); + scheduler_.UpdateStreamPrecedence(2, SpdyStreamPrecedence(1, 100, true)); + EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(1)); + EXPECT_THAT(scheduler_.GetStreamChildren(1), ElementsAre(2)); + EXPECT_THAT(scheduler_.GetStreamChildren(2), UnorderedElementsAre(3, 4, 5)); + EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); + EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty()); + EXPECT_THAT(scheduler_.GetStreamChildren(5), IsEmpty()); + ASSERT_TRUE(peer_.ValidateInvariants()); +} + +TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentToChildNonExclusive) { + /* Tree: + 0 + | + 1 + / \ + 2 3 + | + 4 + */ + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(2, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(4, SpdyStreamPrecedence(2, 100, false)); + scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(2, 100, false)); + EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(2)); + EXPECT_THAT(scheduler_.GetStreamChildren(1), ElementsAre(3)); + EXPECT_THAT(scheduler_.GetStreamChildren(2), UnorderedElementsAre(1, 4)); + EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); + EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty()); + ASSERT_TRUE(peer_.ValidateInvariants()); +} + +TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentToChildExclusive) { + /* Tree: + 0 + | + 1 + / \ + 2 3 + | + 4 + */ + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(2, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(4, SpdyStreamPrecedence(2, 100, false)); + scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(2, 100, true)); + EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(2)); + EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(3, 4)); + EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(1)); + EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); + EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty()); + ASSERT_TRUE(peer_.ValidateInvariants()); +} + +TEST_F(Http2PriorityWriteSchedulerTest, + UpdateStreamParentToGrandchildNonExclusive) { + /* Tree: + 0 + | + 1 + / \ + 2 3 + / \ + 4 5 + | + 6 + */ + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(2, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(4, SpdyStreamPrecedence(2, 100, false)); + scheduler_.RegisterStream(5, SpdyStreamPrecedence(2, 100, false)); + scheduler_.RegisterStream(6, SpdyStreamPrecedence(4, 100, false)); + scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(4, 100, false)); + EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(4)); + EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(2, 3)); + EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(5)); + EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); + EXPECT_THAT(scheduler_.GetStreamChildren(4), UnorderedElementsAre(1, 6)); + EXPECT_THAT(scheduler_.GetStreamChildren(5), IsEmpty()); + EXPECT_THAT(scheduler_.GetStreamChildren(6), IsEmpty()); + ASSERT_TRUE(peer_.ValidateInvariants()); +} + +TEST_F(Http2PriorityWriteSchedulerTest, + UpdateStreamParentToGrandchildExclusive) { + /* Tree: + 0 + | + 1 + / \ + 2 3 + / \ + 4 5 + | + 6 + */ + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(2, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(4, SpdyStreamPrecedence(2, 100, false)); + scheduler_.RegisterStream(5, SpdyStreamPrecedence(2, 100, false)); + scheduler_.RegisterStream(6, SpdyStreamPrecedence(4, 100, false)); + scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(4, 100, true)); + EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(4)); + EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(2, 3, 6)); + EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(5)); + EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); + EXPECT_THAT(scheduler_.GetStreamChildren(4), ElementsAre(1)); + EXPECT_THAT(scheduler_.GetStreamChildren(5), IsEmpty()); + EXPECT_THAT(scheduler_.GetStreamChildren(6), IsEmpty()); + ASSERT_TRUE(peer_.ValidateInvariants()); +} + +TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentToParent) { + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(2, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); + for (bool exclusive : {true, false}) { + scheduler_.UpdateStreamPrecedence(2, + SpdyStreamPrecedence(1, 100, exclusive)); + EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(1)); + EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(2, 3)); + EXPECT_THAT(scheduler_.GetStreamChildren(2), IsEmpty()); + EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); + } + ASSERT_TRUE(peer_.ValidateInvariants()); +} + +TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentToSelf) { + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); + EXPECT_SPDY_BUG( + scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(1, 100, false)), + "Cannot set stream to be its own parent"); + EXPECT_SPDY_BUG( + scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(1, 100, true)), + "Cannot set stream to be its own parent"); + EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(1)); + EXPECT_THAT(scheduler_.GetStreamChildren(1), IsEmpty()); + ASSERT_TRUE(peer_.ValidateInvariants()); +} + +TEST_F(Http2PriorityWriteSchedulerTest, BlockAndUnblock) { + /* Create the tree. + + 0 + / | \ + / | \ + 1 2 3 + / \ \ \ + 4 5 6 7 + /| / \ | |\ + 8 9 10 11 12 13 14 + / \ + 15 16 + + */ + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(5, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(8, SpdyStreamPrecedence(4, 100, false)); + scheduler_.RegisterStream(9, SpdyStreamPrecedence(4, 100, false)); + scheduler_.RegisterStream(10, SpdyStreamPrecedence(5, 100, false)); + scheduler_.RegisterStream(11, SpdyStreamPrecedence(5, 100, false)); + scheduler_.RegisterStream(15, SpdyStreamPrecedence(8, 100, false)); + scheduler_.RegisterStream(16, SpdyStreamPrecedence(8, 100, false)); + scheduler_.RegisterStream(12, SpdyStreamPrecedence(2, 100, false)); + scheduler_.RegisterStream(6, SpdyStreamPrecedence(2, 100, true)); + scheduler_.RegisterStream(7, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(13, SpdyStreamPrecedence(7, 100, true)); + scheduler_.RegisterStream(14, SpdyStreamPrecedence(7, 100, false)); + scheduler_.UpdateStreamPrecedence(7, SpdyStreamPrecedence(3, 100, false)); + EXPECT_EQ(0, scheduler_.GetStreamPrecedence(1).parent_id()); + EXPECT_EQ(0, scheduler_.GetStreamPrecedence(2).parent_id()); + EXPECT_EQ(0, scheduler_.GetStreamPrecedence(3).parent_id()); + EXPECT_EQ(1, scheduler_.GetStreamPrecedence(4).parent_id()); + EXPECT_EQ(1, scheduler_.GetStreamPrecedence(5).parent_id()); + EXPECT_EQ(2, scheduler_.GetStreamPrecedence(6).parent_id()); + EXPECT_EQ(3, scheduler_.GetStreamPrecedence(7).parent_id()); + EXPECT_EQ(4, scheduler_.GetStreamPrecedence(8).parent_id()); + EXPECT_EQ(4, scheduler_.GetStreamPrecedence(9).parent_id()); + EXPECT_EQ(5, scheduler_.GetStreamPrecedence(10).parent_id()); + EXPECT_EQ(5, scheduler_.GetStreamPrecedence(11).parent_id()); + EXPECT_EQ(6, scheduler_.GetStreamPrecedence(12).parent_id()); + EXPECT_EQ(7, scheduler_.GetStreamPrecedence(13).parent_id()); + EXPECT_EQ(7, scheduler_.GetStreamPrecedence(14).parent_id()); + EXPECT_EQ(8, scheduler_.GetStreamPrecedence(15).parent_id()); + EXPECT_EQ(8, scheduler_.GetStreamPrecedence(16).parent_id()); + ASSERT_TRUE(peer_.ValidateInvariants()); + + EXPECT_EQ(peer_.TotalChildWeights(0), + scheduler_.GetStreamPrecedence(1).weight() + + scheduler_.GetStreamPrecedence(2).weight() + + scheduler_.GetStreamPrecedence(3).weight()); + EXPECT_EQ(peer_.TotalChildWeights(3), + scheduler_.GetStreamPrecedence(7).weight()); + EXPECT_EQ(peer_.TotalChildWeights(7), + scheduler_.GetStreamPrecedence(13).weight() + + scheduler_.GetStreamPrecedence(14).weight()); + EXPECT_EQ(peer_.TotalChildWeights(13), 0); + EXPECT_EQ(peer_.TotalChildWeights(14), 0); + + ASSERT_TRUE(peer_.ValidateInvariants()); +} + +TEST_F(Http2PriorityWriteSchedulerTest, HasReadyStreams) { + EXPECT_FALSE(scheduler_.HasReadyStreams()); + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 10, false)); + EXPECT_FALSE(scheduler_.HasReadyStreams()); + scheduler_.MarkStreamReady(1, false); + EXPECT_TRUE(scheduler_.HasReadyStreams()); + EXPECT_TRUE(scheduler_.IsStreamReady(1)); + scheduler_.MarkStreamNotReady(1); + EXPECT_FALSE(scheduler_.HasReadyStreams()); + EXPECT_FALSE(scheduler_.IsStreamReady(1)); + scheduler_.MarkStreamReady(1, true); + EXPECT_TRUE(scheduler_.HasReadyStreams()); + EXPECT_TRUE(scheduler_.IsStreamReady(1)); + scheduler_.UnregisterStream(1); + EXPECT_FALSE(scheduler_.HasReadyStreams()); + ASSERT_TRUE(peer_.ValidateInvariants()); + EXPECT_SPDY_BUG(scheduler_.IsStreamReady(1), "Stream 1 not registered"); +} + +TEST_F(Http2PriorityWriteSchedulerTest, CalculateRoundedWeights) { + /* Create the tree. + + 0 + / \ + 1 2 + /| |\ |\ + 8 3 4 5 6 7 + */ + scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(4, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(5, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 10, true)); + scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 5, false)); + scheduler_.RegisterStream(6, SpdyStreamPrecedence(2, 1, false)); + scheduler_.RegisterStream(7, SpdyStreamPrecedence(2, 1, false)); + scheduler_.RegisterStream(8, SpdyStreamPrecedence(1, 1, false)); + + // Remove higher-level streams. + scheduler_.UnregisterStream(1); + scheduler_.UnregisterStream(2); + + // 3.3 rounded down = 3. + EXPECT_EQ(3, scheduler_.GetStreamPrecedence(3).weight()); + EXPECT_EQ(3, scheduler_.GetStreamPrecedence(4).weight()); + EXPECT_EQ(3, scheduler_.GetStreamPrecedence(5).weight()); + // 2.5 rounded up = 3. + EXPECT_EQ(3, scheduler_.GetStreamPrecedence(6).weight()); + EXPECT_EQ(3, scheduler_.GetStreamPrecedence(7).weight()); + // 0 is not a valid weight, so round up to 1. + EXPECT_EQ(1, scheduler_.GetStreamPrecedence(8).weight()); + ASSERT_TRUE(peer_.ValidateInvariants()); +} + +TEST_F(Http2PriorityWriteSchedulerTest, GetLatestEventWithPrecedence) { + EXPECT_SPDY_BUG(scheduler_.RecordStreamEventTime(3, 5), + "Stream 3 not registered"); + EXPECT_SPDY_BUG(EXPECT_EQ(0, scheduler_.GetLatestEventWithPrecedence(4)), + "Stream 4 not registered"); + + for (int i = 1; i < 5; ++i) { + int weight = SpdyStreamPrecedence(i).weight(); + scheduler_.RegisterStream(i, SpdyStreamPrecedence(0, weight, false)); + } + for (int i = 1; i < 5; ++i) { + EXPECT_EQ(0, scheduler_.GetLatestEventWithPrecedence(i)); + } + for (int i = 1; i < 5; ++i) { + scheduler_.RecordStreamEventTime(i, i * 100); + } + for (int i = 1; i < 5; ++i) { + EXPECT_EQ((i - 1) * 100, scheduler_.GetLatestEventWithPrecedence(i)); + } +} + +// Add ready streams at front and back. +TEST_F(Http2PriorityWriteSchedulerTest, MarkReadyFrontAndBack) { + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 10, false)); + scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 20, false)); + scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 20, false)); + scheduler_.RegisterStream(4, SpdyStreamPrecedence(0, 20, false)); + scheduler_.RegisterStream(5, SpdyStreamPrecedence(0, 30, false)); + + for (int i = 1; i < 6; ++i) { + scheduler_.MarkStreamReady(i, false); + } + EXPECT_EQ(5, scheduler_.PopNextReadyStream()); + EXPECT_EQ(2, scheduler_.PopNextReadyStream()); + scheduler_.MarkStreamReady(2, false); + EXPECT_EQ(3, scheduler_.PopNextReadyStream()); + scheduler_.MarkStreamReady(3, false); + EXPECT_EQ(4, scheduler_.PopNextReadyStream()); + scheduler_.MarkStreamReady(4, false); + EXPECT_EQ(2, scheduler_.PopNextReadyStream()); + scheduler_.MarkStreamReady(2, true); + EXPECT_EQ(2, scheduler_.PopNextReadyStream()); + scheduler_.MarkStreamReady(5, false); + scheduler_.MarkStreamReady(2, true); + EXPECT_EQ(5, scheduler_.PopNextReadyStream()); +} + +// Add ready streams at front and back and pop them with +// PopNextReadyStreamAndPrecedence. +TEST_F(Http2PriorityWriteSchedulerTest, PopNextReadyStreamAndPrecedence) { + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 10, false)); + scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 20, false)); + scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 20, false)); + scheduler_.RegisterStream(4, SpdyStreamPrecedence(0, 20, false)); + scheduler_.RegisterStream(5, SpdyStreamPrecedence(0, 30, false)); + + for (int i = 1; i < 6; ++i) { + scheduler_.MarkStreamReady(i, false); + } + EXPECT_EQ(std::make_tuple(5, SpdyStreamPrecedence(0, 30, false)), + scheduler_.PopNextReadyStreamAndPrecedence()); + EXPECT_EQ(std::make_tuple(2, SpdyStreamPrecedence(0, 20, false)), + scheduler_.PopNextReadyStreamAndPrecedence()); + scheduler_.MarkStreamReady(2, false); + EXPECT_EQ(std::make_tuple(3, SpdyStreamPrecedence(0, 20, false)), + scheduler_.PopNextReadyStreamAndPrecedence()); + scheduler_.MarkStreamReady(3, false); + EXPECT_EQ(std::make_tuple(4, SpdyStreamPrecedence(0, 20, false)), + scheduler_.PopNextReadyStreamAndPrecedence()); + scheduler_.MarkStreamReady(4, false); + EXPECT_EQ(std::make_tuple(2, SpdyStreamPrecedence(0, 20, false)), + scheduler_.PopNextReadyStreamAndPrecedence()); + scheduler_.MarkStreamReady(2, true); + EXPECT_EQ(std::make_tuple(2, SpdyStreamPrecedence(0, 20, false)), + scheduler_.PopNextReadyStreamAndPrecedence()); + scheduler_.MarkStreamReady(5, false); + scheduler_.MarkStreamReady(2, true); + EXPECT_EQ(std::make_tuple(5, SpdyStreamPrecedence(0, 30, false)), + scheduler_.PopNextReadyStreamAndPrecedence()); +} + +class PopNextReadyStreamTest : public Http2PriorityWriteSchedulerTest { + protected: + void SetUp() override { + /* Create the tree. + + 0 + /|\ + 1 2 3 + /| |\ + 4 5 6 7 + / + 8 + + */ + scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 100, false)); + scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(5, SpdyStreamPrecedence(1, 100, false)); + scheduler_.RegisterStream(6, SpdyStreamPrecedence(2, 100, false)); + scheduler_.RegisterStream(7, SpdyStreamPrecedence(2, 100, false)); + scheduler_.RegisterStream(8, SpdyStreamPrecedence(4, 100, false)); + + // Set all nodes ready to write. + for (SpdyStreamId id = 1; id <= 8; ++id) { + scheduler_.MarkStreamReady(id, false); + } + } + + AssertionResult PopNextReturnsCycle( + std::initializer_list<SpdyStreamId> stream_ids) { + int count = 0; + const int kNumCyclesToCheck = 2; + for (int i = 0; i < kNumCyclesToCheck; i++) { + for (SpdyStreamId expected_id : stream_ids) { + SpdyStreamId next_id = scheduler_.PopNextReadyStream(); + scheduler_.MarkStreamReady(next_id, false); + if (next_id != expected_id) { + return AssertionFailure() << "Pick " << count << ": expected stream " + << expected_id << " instead of " << next_id; + } + if (!peer_.ValidateInvariants()) { + return AssertionFailure() << "ValidateInvariants failed"; + } + ++count; + } + } + return AssertionSuccess(); + } +}; + +// When all streams are schedulable, only top-level streams should be returned. +TEST_F(PopNextReadyStreamTest, NoneBlocked) { + EXPECT_TRUE(PopNextReturnsCycle({1, 2, 3})); +} + +// When a parent stream is blocked, its children should be scheduled, if +// priorities allow. +TEST_F(PopNextReadyStreamTest, SingleStreamBlocked) { + scheduler_.MarkStreamNotReady(1); + + // Round-robin only across 2 and 3, since children of 1 have lower priority. + EXPECT_TRUE(PopNextReturnsCycle({2, 3})); + + // Make children of 1 have equal priority as 2 and 3, after which they should + // be returned as well. + scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(0, 200, false)); + EXPECT_TRUE(PopNextReturnsCycle({4, 5, 2, 3})); +} + +// Block multiple levels of streams. +TEST_F(PopNextReadyStreamTest, MultiLevelBlocked) { + for (SpdyStreamId stream_id : {1, 4, 5}) { + scheduler_.MarkStreamNotReady(stream_id); + } + // Round-robin only across 2 and 3, since children of 1 have lower priority. + EXPECT_TRUE(PopNextReturnsCycle({2, 3})); + + // Make 8 have equal priority as 2 and 3. + scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(0, 200, false)); + EXPECT_TRUE(PopNextReturnsCycle({8, 2, 3})); +} + +// A removed stream shouldn't be scheduled. +TEST_F(PopNextReadyStreamTest, RemoveStream) { + scheduler_.UnregisterStream(1); + + // Round-robin only across 2 and 3, since previous children of 1 have lower + // priority (the weight of 4 and 5 is scaled down when they are elevated to + // siblings of 2 and 3). + EXPECT_TRUE(PopNextReturnsCycle({2, 3})); + + // Make previous children of 1 have equal priority as 2 and 3. + scheduler_.UpdateStreamPrecedence(4, SpdyStreamPrecedence(0, 100, false)); + scheduler_.UpdateStreamPrecedence(5, SpdyStreamPrecedence(0, 100, false)); + EXPECT_TRUE(PopNextReturnsCycle({4, 5, 2, 3})); +} + +// Block an entire subtree. +TEST_F(PopNextReadyStreamTest, SubtreeBlocked) { + for (SpdyStreamId stream_id : {1, 4, 5, 8}) { + scheduler_.MarkStreamNotReady(stream_id); + } + EXPECT_TRUE(PopNextReturnsCycle({2, 3})); +} + +// If all parent streams are blocked, children should be returned. +TEST_F(PopNextReadyStreamTest, ParentsBlocked) { + for (SpdyStreamId stream_id : {1, 2, 3}) { + scheduler_.MarkStreamNotReady(stream_id); + } + EXPECT_TRUE(PopNextReturnsCycle({4, 5, 6, 7})); +} + +// Unblocking streams should make them schedulable. +TEST_F(PopNextReadyStreamTest, BlockAndUnblock) { + EXPECT_TRUE(PopNextReturnsCycle({1, 2, 3})); + scheduler_.MarkStreamNotReady(2); + EXPECT_TRUE(PopNextReturnsCycle({1, 3})); + scheduler_.MarkStreamReady(2, false); + // Cycle order permuted since 2 effectively appended at tail. + EXPECT_TRUE(PopNextReturnsCycle({1, 3, 2})); +} + +// Block nodes in multiple subtrees. +TEST_F(PopNextReadyStreamTest, ScatteredBlocked) { + for (SpdyStreamId stream_id : {1, 2, 6, 7}) { + scheduler_.MarkStreamNotReady(stream_id); + } + // Only 3 returned, since of remaining streams it has highest priority. + EXPECT_TRUE(PopNextReturnsCycle({3})); + + // Make children of 1 have priority equal to 3. + scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(0, 200, false)); + EXPECT_TRUE(PopNextReturnsCycle({4, 5, 3})); + + // When 4 is blocked, its child 8 should take its place, since it has same + // priority. + scheduler_.MarkStreamNotReady(4); + EXPECT_TRUE(PopNextReturnsCycle({8, 5, 3})); +} + +} // namespace test +} // namespace spdy
diff --git a/spdy/core/spdy_intrusive_list.h b/spdy/core/spdy_intrusive_list.h new file mode 100644 index 0000000..16917f9 --- /dev/null +++ b/spdy/core/spdy_intrusive_list.h
@@ -0,0 +1,326 @@ +// Copyright (c) 2019 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_SPDY_CORE_SPDY_INTRUSIVE_LIST_H_ +#define QUICHE_SPDY_CORE_SPDY_INTRUSIVE_LIST_H_ + +// A SpdyIntrusiveList<> is a doubly-linked list where the link pointers are +// embedded in the elements. They are circularly linked making insertion and +// removal into a known position constant time and branch-free operations. +// +// Usage is similar to an STL list<> where feasible, but there are important +// differences. First and foremost, the elements must derive from the +// SpdyIntrusiveLink<> base class: +// +// struct Foo : public SpdyIntrusiveLink<Foo> { +// // ... +// } +// +// SpdyIntrusiveList<Foo> l; +// l.push_back(new Foo); +// l.push_front(new Foo); +// l.erase(&l.front()); +// l.erase(&l.back()); +// +// Intrusive lists are primarily useful when you would have considered embedding +// link pointers in your class directly for space or performance reasons. An +// SpdyIntrusiveLink<> is the size of 2 pointers, usually 16 bytes on 64-bit +// systems. Intrusive lists do not perform memory allocation (unlike the STL +// list<> class) and thus may use less memory than list<>. In particular, if the +// list elements are pointers to objects, using a list<> would perform an extra +// memory allocation for each list node structure, while an SpdyIntrusiveList<> +// would not. +// +// Note that SpdyIntrusiveLink is exempt from the C++ style guide's limitations +// on multiple inheritance, so it's fine to inherit from both SpdyIntrusiveLink +// and a base class, even if the base class is not a pure interface. +// +// Because the list pointers are embedded in the objects stored in an +// SpdyIntrusiveList<>, erasing an item from a list is constant time. Consider +// the following: +// +// map<string,Foo> foo_map; +// list<Foo*> foo_list; +// +// foo_list.push_back(&foo_map["bar"]); +// foo_list.erase(&foo_map["bar"]); // Compile error! +// +// The problem here is that a Foo* doesn't know where on foo_list it resides, +// so removal requires iteration over the list. Various tricks can be performed +// to overcome this. For example, a foo_list::iterator can be stored inside of +// the Foo object. But at that point you'd be better off using an +// SpdyIntrusiveList<>: +// +// map<string,Foo> foo_map; +// SpdyIntrusiveList<Foo> foo_list; +// +// foo_list.push_back(&foo_map["bar"]); +// foo_list.erase(&foo_map["bar"]); // Yeah! +// +// Note that SpdyIntrusiveLists come with a few limitations. The primary +// limitation is that the SpdyIntrusiveLink<> base class is not copyable or +// assignable. The result is that STL algorithms which mutate the order of +// iterators, such as reverse() and unique(), will not work by default with +// SpdyIntrusiveLists. In order to allow these algorithms to work you'll need to +// define swap() and/or operator= for your class. +// +// Another limitation is that the SpdyIntrusiveList<> structure itself is not +// copyable or assignable since an item/link combination can only exist on one +// SpdyIntrusiveList<> at a time. This limitation is a result of the link +// pointers for an item being intrusive in the item itself. For example, the +// following will not compile: +// +// FooList a; +// FooList b(a); // no copy constructor +// b = a; // no assignment operator +// +// The similar STL code does work since the link pointers are external to the +// item: +// +// list<int*> a; +// a.push_back(new int); +// list<int*> b(a); +// CHECK(a.front() == b.front()); +// +// Note that SpdyIntrusiveList::size() runs in O(N) time. + +#include <stddef.h> +#include <iterator> + + +namespace spdy { + +template <typename T, typename ListID> class SpdyIntrusiveList; + +template <typename T, typename ListID = void> class SpdyIntrusiveLink { + protected: + // We declare the constructor protected so that only derived types and the + // befriended list can construct this. + SpdyIntrusiveLink() : next_(nullptr), prev_(nullptr) {} + +#ifndef SWIG + SpdyIntrusiveLink(const SpdyIntrusiveLink&) = delete; + SpdyIntrusiveLink& operator=(const SpdyIntrusiveLink&) = delete; +#endif // SWIG + + private: + // We befriend the matching list type so that it can manipulate the links + // while they are kept private from others. + friend class SpdyIntrusiveList<T, ListID>; + + // Encapsulates the logic to convert from a link to its derived type. + T* cast_to_derived() { return static_cast<T*>(this); } + const T* cast_to_derived() const { return static_cast<const T*>(this); } + + SpdyIntrusiveLink* next_; + SpdyIntrusiveLink* prev_; +}; + +template <typename T, typename ListID = void> class SpdyIntrusiveList { + template <typename QualifiedT, typename QualifiedLinkT> class iterator_impl; + + public: + typedef T value_type; + typedef value_type *pointer; + typedef const value_type *const_pointer; + typedef value_type &reference; + typedef const value_type &const_reference; + typedef size_t size_type; + typedef ptrdiff_t difference_type; + + typedef SpdyIntrusiveLink<T, ListID> link_type; + typedef iterator_impl<T, link_type> iterator; + typedef iterator_impl<const T, const link_type> const_iterator; + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + typedef std::reverse_iterator<iterator> reverse_iterator; + + SpdyIntrusiveList() { clear(); } + // After the move constructor the moved-from list will be empty. + // + // NOTE: There is no move assign operator (for now). + // The reason is that at the moment 'clear()' does not unlink the nodes. + // It makes is_linked() return true when it should return false. + // If such node is removed from the list (e.g. from its destructor), or is + // added to another list - a memory corruption will occur. + // Admitedly the destructor does not unlink the nodes either, but move-assign + // will likely make the problem more prominent. +#ifndef SWIG + SpdyIntrusiveList(SpdyIntrusiveList&& src) noexcept { + clear(); + if (src.empty()) return; + sentinel_link_.next_ = src.sentinel_link_.next_; + sentinel_link_.prev_ = src.sentinel_link_.prev_; + // Fix head and tail nodes of the list. + sentinel_link_.prev_->next_ = &sentinel_link_; + sentinel_link_.next_->prev_ = &sentinel_link_; + src.clear(); + } +#endif // SWIG + + iterator begin() { return iterator(sentinel_link_.next_); } + const_iterator begin() const { return const_iterator(sentinel_link_.next_); } + iterator end() { return iterator(&sentinel_link_); } + const_iterator end() const { return const_iterator(&sentinel_link_); } + reverse_iterator rbegin() { return reverse_iterator(end()); } + const_reverse_iterator rbegin() const { + return const_reverse_iterator(end()); + } + reverse_iterator rend() { return reverse_iterator(begin()); } + const_reverse_iterator rend() const { + return const_reverse_iterator(begin()); + } + + bool empty() const { return (sentinel_link_.next_ == &sentinel_link_); } + // This runs in O(N) time. + size_type size() const { return std::distance(begin(), end()); } + size_type max_size() const { return size_type(-1); } + + reference front() { return *begin(); } + const_reference front() const { return *begin(); } + reference back() { return *(--end()); } + const_reference back() const { return *(--end()); } + + static iterator insert(iterator position, T *obj) { + return insert_link(position.link(), obj); + } + void push_front(T* obj) { insert(begin(), obj); } + void push_back(T* obj) { insert(end(), obj); } + + static iterator erase(T* obj) { + link_type* obj_link = obj; + // Fix up the next and previous links for the previous and next objects. + obj_link->next_->prev_ = obj_link->prev_; + obj_link->prev_->next_ = obj_link->next_; + // Zero out the next and previous links for the removed item. This will + // cause any future attempt to remove the item from the list to cause a + // crash instead of possibly corrupting the list structure. + link_type* next_link = obj_link->next_; + obj_link->next_ = nullptr; + obj_link->prev_ = nullptr; + return iterator(next_link); + } + + static iterator erase(iterator position) { + return erase(position.operator->()); + } + void pop_front() { erase(begin()); } + void pop_back() { erase(--end()); } + + // Check whether the given element is linked into some list. Note that this + // does *not* check whether it is linked into a particular list. + // Also, if clear() is used to clear the containing list, is_linked() will + // still return true even though obj is no longer in any list. + static bool is_linked(const T* obj) { + return obj->link_type::next_ != nullptr; + } + + void clear() { + sentinel_link_.next_ = sentinel_link_.prev_ = &sentinel_link_; + } + void swap(SpdyIntrusiveList& x) { + SpdyIntrusiveList tmp; + tmp.splice(tmp.begin(), *this); + this->splice(this->begin(), x); + x.splice(x.begin(), tmp); + } + + void splice(iterator pos, SpdyIntrusiveList& src) { + splice(pos, src.begin(), src.end()); + } + + void splice(iterator pos, iterator i) { splice(pos, i, std::next(i)); } + + void splice(iterator pos, iterator first, iterator last) { + if (first == last) return; + + link_type* const last_prev = last.link()->prev_; + + // Remove from the source. + first.link()->prev_->next_ = last.operator->(); + last.link()->prev_ = first.link()->prev_; + + // Attach to the destination. + first.link()->prev_ = pos.link()->prev_; + pos.link()->prev_->next_ = first.operator->(); + last_prev->next_ = pos.operator->(); + pos.link()->prev_ = last_prev; + } + + private: + static iterator insert_link(link_type* next_link, T* obj) { + link_type* obj_link = obj; + obj_link->next_ = next_link; + link_type* const initial_next_prev = next_link->prev_; + obj_link->prev_ = initial_next_prev; + initial_next_prev->next_ = obj_link; + next_link->prev_ = obj_link; + return iterator(obj_link); + } + + // The iterator implementation is parameterized on a potentially qualified + // variant of T and the matching qualified link type. Essentially, QualifiedT + // will either be 'T' or 'const T', the latter for a const_iterator. + template <typename QualifiedT, typename QualifiedLinkT> + class iterator_impl : public std::iterator<std::bidirectional_iterator_tag, + QualifiedT> { + public: + typedef std::iterator<std::bidirectional_iterator_tag, QualifiedT> base; + + iterator_impl() : link_(nullptr) {} + iterator_impl(QualifiedLinkT* link) : link_(link) {} + iterator_impl(const iterator_impl& x) : link_(x.link_) {} + + // Allow converting and comparing across iterators where the pointer + // assignment and comparisons (respectively) are allowed. + template <typename U, typename V> + iterator_impl(const iterator_impl<U, V>& x) : link_(x.link_) {} + template <typename U, typename V> + bool operator==(const iterator_impl<U, V>& x) const { + return link_ == x.link_; + } + template <typename U, typename V> + bool operator!=(const iterator_impl<U, V>& x) const { + return link_ != x.link_; + } + + typename base::reference operator*() const { return *operator->(); } + typename base::pointer operator->() const { + return link_->cast_to_derived(); + } + + QualifiedLinkT *link() const { return link_; } + +#ifndef SWIG // SWIG can't wrap these operator overloads. + iterator_impl& operator++() { link_ = link_->next_; return *this; } + iterator_impl operator++(int /*unused*/) { + iterator_impl tmp = *this; + ++*this; + return tmp; + } + iterator_impl& operator--() { link_ = link_->prev_; return *this; } + iterator_impl operator--(int /*unused*/) { + iterator_impl tmp = *this; + --*this; + return tmp; + } +#endif // SWIG + + private: + // Ensure iterators can access other iterators node directly. + template <typename U, typename V> friend class iterator_impl; + + QualifiedLinkT* link_; + }; + + // This bare link acts as the sentinel node. + link_type sentinel_link_; + + // These are private and undefined to prevent copying and assigning. + SpdyIntrusiveList(const SpdyIntrusiveList&); + void operator=(const SpdyIntrusiveList&); +}; + +} // namespace spdy + +#endif // QUICHE_SPDY_CORE_SPDY_INTRUSIVE_LIST_H_
diff --git a/spdy/core/spdy_intrusive_list_test.cc b/spdy/core/spdy_intrusive_list_test.cc new file mode 100644 index 0000000..eee65e3 --- /dev/null +++ b/spdy/core/spdy_intrusive_list_test.cc
@@ -0,0 +1,427 @@ +// Copyright (c) 2019 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 "net/third_party/quiche/src/spdy/core/spdy_intrusive_list.h" + +#include <algorithm> +#include <cstddef> +#include <list> +#include <utility> + +#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h" +#include "net/third_party/quiche/src/spdy/platform/api/spdy_test.h" + +namespace spdy { +namespace test { + +struct ListId2 {}; + +struct TestItem : public SpdyIntrusiveLink<TestItem>, + public SpdyIntrusiveLink<TestItem, ListId2> { + int n; +}; +typedef SpdyIntrusiveList<TestItem> TestList; +typedef std::list<TestItem*> CanonicalList; + +void swap(TestItem &a, TestItem &b) { + using std::swap; + swap(a.n, b.n); +} + +class IntrusiveListTest : public ::testing::Test { + protected: + void CheckLists() { + CheckLists(l1, ll1); + if (::testing::Test::HasFailure()) return; + CheckLists(l2, ll2); + } + + void CheckLists(const TestList &list_a, const CanonicalList &list_b) { + ASSERT_EQ(list_a.size(), list_b.size()); + TestList::const_iterator it_a = list_a.begin(); + CanonicalList::const_iterator it_b = list_b.begin(); + while (it_a != list_a.end()) { + EXPECT_EQ(&*it_a++, *it_b++); + } + EXPECT_EQ(list_a.end(), it_a); + EXPECT_EQ(list_b.end(), it_b); + } + + void PrepareLists(int num_elems_1, int num_elems_2 = 0) { + FillLists(&l1, &ll1, e, num_elems_1); + FillLists(&l2, &ll2, e + num_elems_1, num_elems_2); + } + + void FillLists(TestList *list_a, CanonicalList *list_b, TestItem *elems, + int num_elems) { + list_a->clear(); + list_b->clear(); + for (int i = 0; i < num_elems; ++i) { + list_a->push_back(elems + i); + list_b->push_back(elems + i); + } + CheckLists(*list_a, *list_b); + } + + TestItem e[10]; + TestList l1, l2; + CanonicalList ll1, ll2; +}; + +TEST(NewIntrusiveListTest, Basic) { + TestList list1; + + CHECK_EQ(sizeof(SpdyIntrusiveLink<TestItem>), sizeof(void *) * 2); + + for (int i = 0; i < 10; ++i) { + TestItem *e = new TestItem; + e->n = i; + list1.push_front(e); + } + CHECK_EQ(list1.size(), 10); + + // Verify we can reverse a list because we defined swap for TestItem. + std::reverse(list1.begin(), list1.end()); + CHECK_EQ(list1.size(), 10); + + // Check both const and non-const forward iteration. + const TestList& clist1 = list1; + int i = 0; + TestList::iterator iter = list1.begin(); + for (; + iter != list1.end(); + ++iter, ++i) { + CHECK_EQ(iter->n, i); + } + CHECK(iter == clist1.end()); + CHECK(iter != clist1.begin()); + i = 0; + iter = list1.begin(); + for (; + iter != list1.end(); + ++iter, ++i) { + CHECK_EQ(iter->n, i); + } + CHECK(iter == clist1.end()); + CHECK(iter != clist1.begin()); + + CHECK_EQ(list1.front().n, 0); + CHECK_EQ(list1.back().n, 9); + + // Verify we can swap 2 lists. + TestList list2; + list2.swap(list1); + CHECK_EQ(list1.size(), 0); + CHECK_EQ(list2.size(), 10); + + // Check both const and non-const reverse iteration. + const TestList& clist2 = list2; + TestList::reverse_iterator riter = list2.rbegin(); + i = 9; + for (; + riter != list2.rend(); + ++riter, --i) { + CHECK_EQ(riter->n, i); + } + CHECK(riter == clist2.rend()); + CHECK(riter != clist2.rbegin()); + + riter = list2.rbegin(); + i = 9; + for (; + riter != list2.rend(); + ++riter, --i) { + CHECK_EQ(riter->n, i); + } + CHECK(riter == clist2.rend()); + CHECK(riter != clist2.rbegin()); + + while (!list2.empty()) { + TestItem *e = &list2.front(); + list2.pop_front(); + delete e; + } +} + +TEST(NewIntrusiveListTest, Erase) { + TestList l; + TestItem *e[10]; + + // Create a list with 10 items. + for (int i = 0; i < 10; ++i) { + e[i] = new TestItem; + l.push_front(e[i]); + } + + // Test that erase works. + for (int i = 0; i < 10; ++i) { + CHECK_EQ(l.size(), (10 - i)); + + TestList::iterator iter = l.erase(e[i]); + CHECK(iter != TestList::iterator(e[i])); + + CHECK_EQ(l.size(), (10 - i - 1)); + delete e[i]; + } +} + +TEST(NewIntrusiveListTest, Insert) { + TestList l; + TestList::iterator iter = l.end(); + TestItem *e[10]; + + // Create a list with 10 items. + for (int i = 9; i >= 0; --i) { + e[i] = new TestItem; + iter = l.insert(iter, e[i]); + CHECK_EQ(&(*iter), e[i]); + } + + CHECK_EQ(l.size(), 10); + + // Verify insertion order. + iter = l.begin(); + for (TestItem *item : e) { + CHECK_EQ(&(*iter), item); + iter = l.erase(item); + delete item; + } +} + +TEST(NewIntrusiveListTest, Move) { + // Move contructible. + + { // Move-construct from an empty list. + TestList src; + TestList dest(std::move(src)); + EXPECT_TRUE(dest.empty()); + } + + { // Move-construct from a single item list. + TestItem e; + TestList src; + src.push_front(&e); + + TestList dest(std::move(src)); + EXPECT_TRUE(src.empty()); // NOLINT bugprone-use-after-move + ASSERT_THAT(dest.size(), 1); + EXPECT_THAT(&dest.front(), &e); + EXPECT_THAT(&dest.back(), &e); + } + + { // Move-construct from a list with multiple items. + TestItem items[10]; + TestList src; + for (TestItem &e : items) src.push_back(&e); + + TestList dest(std::move(src)); + EXPECT_TRUE(src.empty()); // NOLINT bugprone-use-after-move + // Verify the items on the destination list. + ASSERT_THAT(dest.size(), 10); + int i = 0; + for (TestItem &e : dest) { + EXPECT_THAT(&e, &items[i++]) << " for index " << i; + } + } +} + +TEST(NewIntrusiveListTest, StaticInsertErase) { + TestList l; + TestItem e[2]; + TestList::iterator i = l.begin(); + TestList::insert(i, &e[0]); + TestList::insert(&e[0], &e[1]); + TestList::erase(&e[0]); + TestList::erase(TestList::iterator(&e[1])); + EXPECT_TRUE(l.empty()); +} + +TEST_F(IntrusiveListTest, Splice) { + // We verify that the contents of this secondary list aren't affected by any + // of the splices. + SpdyIntrusiveList<TestItem, ListId2> secondary_list; + for (int i = 0; i < 3; ++i) { + secondary_list.push_back(&e[i]); + } + + // Test the basic cases: + // - The lists range from 0 to 2 elements. + // - The insertion point ranges from begin() to end() + // - The transfered range has multiple sizes and locations in the source. + for (int l1_count = 0; l1_count < 3; ++l1_count) { + for (int l2_count = 0; l2_count < 3; ++l2_count) { + for (int pos = 0; pos <= l1_count; ++pos) { + for (int first = 0; first <= l2_count; ++first) { + for (int last = first; last <= l2_count; ++last) { + PrepareLists(l1_count, l2_count); + + l1.splice(std::next(l1.begin(), pos), std::next(l2.begin(), first), + std::next(l2.begin(), last)); + ll1.splice(std::next(ll1.begin(), pos), ll2, + std::next(ll2.begin(), first), + std::next(ll2.begin(), last)); + + CheckLists(); + + ASSERT_EQ(3, secondary_list.size()); + for (int i = 0; i < 3; ++i) { + EXPECT_EQ(&e[i], &*std::next(secondary_list.begin(), i)); + } + } + } + } + } + } +} + +// Build up a set of classes which form "challenging" type hierarchies to use +// with an SpdyIntrusiveList. +struct BaseLinkId {}; +struct DerivedLinkId {}; + +struct AbstractBase : public SpdyIntrusiveLink<AbstractBase, BaseLinkId> { + virtual ~AbstractBase() = 0; + virtual SpdyString name() { return "AbstractBase"; } +}; +AbstractBase::~AbstractBase() {} +struct DerivedClass : public SpdyIntrusiveLink<DerivedClass, DerivedLinkId>, + public AbstractBase { + virtual ~DerivedClass() {} + virtual SpdyString name() { return "DerivedClass"; } +}; +struct VirtuallyDerivedBaseClass : public virtual AbstractBase { + virtual ~VirtuallyDerivedBaseClass() = 0; + virtual SpdyString name() { return "VirtuallyDerivedBaseClass"; } +}; +VirtuallyDerivedBaseClass::~VirtuallyDerivedBaseClass() {} +struct VirtuallyDerivedClassA + : public SpdyIntrusiveLink<VirtuallyDerivedClassA, DerivedLinkId>, + public virtual VirtuallyDerivedBaseClass { + virtual ~VirtuallyDerivedClassA() {} + virtual SpdyString name() { return "VirtuallyDerivedClassA"; } +}; +struct NonceClass { + virtual ~NonceClass() {} + int data_; +}; +struct VirtuallyDerivedClassB + : public SpdyIntrusiveLink<VirtuallyDerivedClassB, DerivedLinkId>, + public virtual NonceClass, + public virtual VirtuallyDerivedBaseClass { + virtual ~VirtuallyDerivedClassB() {} + virtual SpdyString name() { return "VirtuallyDerivedClassB"; } +}; +struct VirtuallyDerivedClassC + : public SpdyIntrusiveLink<VirtuallyDerivedClassC, DerivedLinkId>, + public virtual AbstractBase, + public virtual NonceClass, + public virtual VirtuallyDerivedBaseClass { + virtual ~VirtuallyDerivedClassC() {} + virtual SpdyString name() { return "VirtuallyDerivedClassC"; } +}; + +// Test for multiple layers between the element type and the link. +namespace templated_base_link { +template <typename T> struct AbstractBase : public SpdyIntrusiveLink<T> { + virtual ~AbstractBase() = 0; +}; +template <typename T> AbstractBase<T>::~AbstractBase() {} +struct DerivedClass : public AbstractBase<DerivedClass> { + int n; +}; +} + +TEST(NewIntrusiveListTest, HandleInheritanceHierarchies) { + { + SpdyIntrusiveList<DerivedClass, DerivedLinkId> list; + DerivedClass elements[2]; + EXPECT_TRUE(list.empty()); + list.push_back(&elements[0]); + EXPECT_EQ(1, list.size()); + list.push_back(&elements[1]); + EXPECT_EQ(2, list.size()); + list.pop_back(); + EXPECT_EQ(1, list.size()); + list.pop_back(); + EXPECT_TRUE(list.empty()); + } + { + SpdyIntrusiveList<VirtuallyDerivedClassA, DerivedLinkId> list; + VirtuallyDerivedClassA elements[2]; + EXPECT_TRUE(list.empty()); + list.push_back(&elements[0]); + EXPECT_EQ(1, list.size()); + list.push_back(&elements[1]); + EXPECT_EQ(2, list.size()); + list.pop_back(); + EXPECT_EQ(1, list.size()); + list.pop_back(); + EXPECT_TRUE(list.empty()); + } + { + SpdyIntrusiveList<VirtuallyDerivedClassC, DerivedLinkId> list; + VirtuallyDerivedClassC elements[2]; + EXPECT_TRUE(list.empty()); + list.push_back(&elements[0]); + EXPECT_EQ(1, list.size()); + list.push_back(&elements[1]); + EXPECT_EQ(2, list.size()); + list.pop_back(); + EXPECT_EQ(1, list.size()); + list.pop_back(); + EXPECT_TRUE(list.empty()); + } + { + SpdyIntrusiveList<AbstractBase, BaseLinkId> list; + DerivedClass d1; + VirtuallyDerivedClassA d2; + VirtuallyDerivedClassB d3; + VirtuallyDerivedClassC d4; + EXPECT_TRUE(list.empty()); + list.push_back(&d1); + EXPECT_EQ(1, list.size()); + list.push_back(&d2); + EXPECT_EQ(2, list.size()); + list.push_back(&d3); + EXPECT_EQ(3, list.size()); + list.push_back(&d4); + EXPECT_EQ(4, list.size()); + SpdyIntrusiveList<AbstractBase, BaseLinkId>::iterator it = list.begin(); + EXPECT_EQ("DerivedClass", (it++)->name()); + EXPECT_EQ("VirtuallyDerivedClassA", (it++)->name()); + EXPECT_EQ("VirtuallyDerivedClassB", (it++)->name()); + EXPECT_EQ("VirtuallyDerivedClassC", (it++)->name()); + } + { + SpdyIntrusiveList<templated_base_link::DerivedClass> list; + templated_base_link::DerivedClass elements[2]; + EXPECT_TRUE(list.empty()); + list.push_back(&elements[0]); + EXPECT_EQ(1, list.size()); + list.push_back(&elements[1]); + EXPECT_EQ(2, list.size()); + list.pop_back(); + EXPECT_EQ(1, list.size()); + list.pop_back(); + EXPECT_TRUE(list.empty()); + } +} + + +class IntrusiveListTagTypeTest : public testing::Test { + protected: + struct Tag {}; + class Element : public SpdyIntrusiveLink<Element, Tag> {}; +}; + +TEST_F(IntrusiveListTagTypeTest, TagTypeListID) { + SpdyIntrusiveList<Element, Tag> list; + { + Element e; + list.push_back(&e); + } +} + +} // namespace test +} // namespace spdy
diff --git a/spdy/platform/api/spdy_containers.h b/spdy/platform/api/spdy_containers.h index e4f4c49..9a90556 100644 --- a/spdy/platform/api/spdy_containers.h +++ b/spdy/platform/api/spdy_containers.h
@@ -37,6 +37,12 @@ return SpdyHashStringPairImpl(a, b); } +// Used for maps that are typically small, then it is faster than (for example) +// hash_map which is optimized for large data sets. SpdySmallMap upgrades itself +// automatically to a SpdySmallMapImpl-specified map when it runs out of space. +template <typename Key, typename Value, int Size> +using SpdySmallMap = SpdySmallMapImpl<Key, Value, Size>; + } // namespace spdy #endif // QUICHE_SPDY_PLATFORM_API_SPDY_CONTAINERS_H_
diff --git a/spdy/platform/api/spdy_map_util.h b/spdy/platform/api/spdy_map_util.h new file mode 100644 index 0000000..e9b5f85 --- /dev/null +++ b/spdy/platform/api/spdy_map_util.h
@@ -0,0 +1,19 @@ +// Copyright (c) 2019 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_SPDY_PLATFORM_API_SPDY_MAP_UTIL_H_ +#define QUICHE_SPDY_PLATFORM_API_SPDY_MAP_UTIL_H_ + +#include "net/spdy/platform/impl/spdy_map_util_impl.h" + +namespace spdy { + +template <class Collection, class Key> +bool SpdyContainsKey(const Collection& collection, const Key& key) { + return SpdyContainsKeyImpl(collection, key); +} + +} // namespace spdy + +#endif // QUICHE_SPDY_PLATFORM_API_SPDY_MAP_UTIL_H_