Remove unused Http2PriorityWriteScheduler. PiperOrigin-RevId: 406349602
diff --git a/http2/core/http2_priority_write_scheduler.h b/http2/core/http2_priority_write_scheduler.h deleted file mode 100644 index 4d64d75..0000000 --- a/http2/core/http2_priority_write_scheduler.h +++ /dev/null
@@ -1,791 +0,0 @@ -// 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_HTTP2_CORE_HTTP2_PRIORITY_WRITE_SCHEDULER_H_ -#define QUICHE_HTTP2_CORE_HTTP2_PRIORITY_WRITE_SCHEDULER_H_ - -#include <cstdint> -#include <deque> -#include <map> -#include <memory> -#include <queue> -#include <set> -#include <string> -#include <tuple> -#include <unordered_map> -#include <utility> -#include <vector> - -#include "absl/container/flat_hash_map.h" -#include "absl/strings/str_cat.h" -#include "http2/core/write_scheduler.h" -#include "common/platform/api/quiche_bug_tracker.h" -#include "common/platform/api/quiche_logging.h" -#include "spdy/core/spdy_intrusive_list.h" -#include "spdy/core/spdy_protocol.h" - -namespace http2 { - -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; - size_t NumRegisteredStreams() const override; - std::string DebugString() const override; - - private: - friend class test::Http2PriorityWriteSchedulerPeer<StreamIdType>; - - struct StreamInfo; - using StreamInfoVector = absl::InlinedVector<StreamInfo*, 4>; - - struct StreamInfo : public spdy::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 = spdy::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; - - // Returns true if this stream is ancestor of |other|. - bool IsAncestorOf(const StreamInfo& other) const { - for (const StreamInfo* p = other.parent; p != nullptr; p = p->parent) { - if (p == this) { - return true; - } - } - return false; - } - - // 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 ? spdy::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. - absl::flat_hash_map<StreamIdType, std::unique_ptr<StreamInfo>> - 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. - spdy::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 = std::make_unique<StreamInfo>(); - root_stream_info_ = root_stream_info.get(); - root_stream_info->id = spdy::kHttp2RootStreamId; - root_stream_info->weight = spdy::kHttp2DefaultStreamWeight; - root_stream_info->parent = nullptr; - root_stream_info->priority = 1.0; - root_stream_info->ready = false; - all_stream_infos_[spdy::kHttp2RootStreamId] = std::move(root_stream_info); -} - -template <typename StreamIdType> -bool Http2PriorityWriteScheduler<StreamIdType>::StreamRegistered( - StreamIdType stream_id) const { - return all_stream_infos_.find(stream_id) != all_stream_infos_.end(); -} - -template <typename StreamIdType> -void Http2PriorityWriteScheduler<StreamIdType>::RegisterStream( - StreamIdType stream_id, - const StreamPrecedenceType& precedence) { - // TODO(mpw): uncomment the QUICHE_BUG_IF below once all tests - // (e.g. SpdyClientDispatcher) modified to pass StreamPrecedence instances - // appropriate for protocol version under test. - // - // QUICHE_BUG_IF(spdy_bug_8_1, precedence.is_spdy3_priority()) - // << "Expected HTTP/2 stream dependency"; - - if (StreamRegistered(stream_id)) { - QUICHE_BUG(spdy_bug_8_2) << "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. - QUICHE_VLOG(1) << "Parent stream " << precedence.parent_id() - << " not registered"; - parent = root_stream_info_; - } - - auto new_stream_info = std::make_unique<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. - QUICHE_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. - QUICHE_DCHECK(!new_stream_info_ptr->ready); -} - -template <typename StreamIdType> -void Http2PriorityWriteScheduler<StreamIdType>::UnregisterStream( - StreamIdType stream_id) { - if (stream_id == spdy::kHttp2RootStreamId) { - QUICHE_BUG(spdy_bug_8_3) << "Cannot unregister root stream"; - return; - } - // Remove the stream from table. - auto it = all_stream_infos_.find(stream_id); - if (it == all_stream_infos_.end()) { - QUICHE_BUG(spdy_bug_8_4) << "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. - QUICHE_VLOG(1) << "Stream " << stream_id << " not registered"; - return StreamPrecedenceType(spdy::kHttp2RootStreamId, - spdy::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) { - QUICHE_BUG(spdy_bug_8_5) << "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 QUICHE_BUG_IF below once all tests - // (e.g. SpdyClientDispatcher) modified to pass StreamPrecedence instances - // appropriate for protocol version under test. - // - // QUICHE_BUG_IF(spdy_bug_8_6, precedence.is_spdy3_priority()) - // << "Expected HTTP/2 stream dependency"; - if (stream_id == spdy::kHttp2RootStreamId) { - QUICHE_BUG(spdy_bug_8_7) << "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. - QUICHE_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) { - QUICHE_BUG(spdy_bug_8_8) << "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. - QUICHE_VLOG(1) << "Parent stream " << parent_id << " not registered"; - return; - } - - if (stream_info->parent == new_parent && - (!exclusive || new_parent->children.size() == 1u)) { - // If the new parent is already the stream's parent, and exclusivity (if - // specified) is already satisfied, we are done. - 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 == spdy::kHttp2RootStreamId) { - QUICHE_BUG(spdy_bug_8_9) << "Cannot record event time for root stream"; - return; - } - StreamInfo* stream_info = FindStream(stream_id); - if (stream_info == nullptr) { - QUICHE_BUG(spdy_bug_8_10) << "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 == spdy::kHttp2RootStreamId) { - QUICHE_BUG(spdy_bug_8_11) << "Invalid argument: root stream"; - return 0; - } - const StreamInfo* stream_info = FindStream(stream_id); - if (stream_info == nullptr) { - QUICHE_BUG(spdy_bug_8_12) << "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 == spdy::kHttp2RootStreamId) { - QUICHE_BUG(spdy_bug_8_13) << "Invalid argument: root stream"; - return false; - } - const StreamInfo* stream_info = FindStream(stream_id); - if (stream_info == nullptr) { - QUICHE_BUG(spdy_bug_8_14) << "Stream " << stream_id << " not registered"; - return false; - } - if (HasReadyAncestor(*stream_info)) { - return true; - } - for (const StreamInfo& scheduled : scheduling_queue_) { - if (HasReadyAncestor(scheduled)) { - // Skip streams which cannot be scheduled. - continue; - } - if (stream_info->IsAncestorOf(scheduled)) { - // Do not yield to descendants. - return false; - } - // Yield to streams with higher priorities. - return scheduled.SchedulesBefore(*stream_info); - } - return false; -} - -template <typename StreamIdType> -void Http2PriorityWriteScheduler<StreamIdType>::MarkStreamReady( - StreamIdType stream_id, - bool add_to_front) { - if (stream_id == spdy::kHttp2RootStreamId) { - QUICHE_BUG(spdy_bug_8_15) << "Cannot mark root stream ready"; - return; - } - StreamInfo* stream_info = FindStream(stream_id); - if (stream_info == nullptr) { - QUICHE_BUG(spdy_bug_8_16) << "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 == spdy::kHttp2RootStreamId) { - QUICHE_BUG(spdy_bug_8_17) << "Cannot mark root stream unready"; - return; - } - StreamInfo* stream_info = FindStream(stream_id); - if (stream_info == nullptr) { - QUICHE_BUG(spdy_bug_8_18) << "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) { - QUICHE_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) { - QUICHE_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()); - } - } - QUICHE_BUG(spdy_bug_8_19) << "No ready streams"; - return std::make_tuple( - spdy::kHttp2RootStreamId, - StreamPrecedenceType(spdy::kHttp2RootStreamId, - spdy::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 == spdy::kHttp2RootStreamId) { - QUICHE_BUG(spdy_bug_8_20) << "Try to check whether root stream is ready"; - return false; - } - const StreamInfo* stream_info = FindStream(stream_id); - if (stream_info == nullptr) { - QUICHE_BUG(spdy_bug_8_21) << "Stream " << stream_id << " not registered"; - return false; - } - return stream_info->ready; -} - -template <typename StreamIdType> -size_t Http2PriorityWriteScheduler<StreamIdType>::NumRegisteredStreams() const { - return all_stream_infos_.size(); -} - -template <typename StreamIdType> -std::string Http2PriorityWriteScheduler<StreamIdType>::DebugString() const { - return absl::StrCat("Http2PriorityWriteScheduler {num_registered_streams=", - NumRegisteredStreams(), - " num_ready_streams=", NumReadyStreams(), "}"); -} - -template <typename StreamIdType> -bool Http2PriorityWriteScheduler<StreamIdType>::ValidateInvariantsForTests() - const { - size_t total_streams = 0; - size_t 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) { - QUICHE_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 != spdy::kHttp2RootStreamId && - !StreamHasChild(*stream_info.parent, &stream_info)) { - QUICHE_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) { - QUICHE_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) { - QUICHE_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 NumRegisteredStreams() reflects the total number of streams the - // map contains. - if (total_streams != NumRegisteredStreams()) { - QUICHE_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) - QUICHE_DCHECK(streams_visited == 2 * NumRegisteredStreams() - 1); - return true; -} - -} // namespace http2 - -#endif // QUICHE_HTTP2_CORE_HTTP2_PRIORITY_WRITE_SCHEDULER_H_
diff --git a/http2/core/http2_priority_write_scheduler_test.cc b/http2/core/http2_priority_write_scheduler_test.cc deleted file mode 100644 index 7f08619..0000000 --- a/http2/core/http2_priority_write_scheduler_test.cc +++ /dev/null
@@ -1,970 +0,0 @@ -// 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 "http2/core/http2_priority_write_scheduler.h" - -#include <initializer_list> - -#include "common/platform/api/quiche_test.h" -#include "common/platform/api/quiche_test_helpers.h" - -using ::testing::AssertionFailure; -using ::testing::AssertionResult; -using ::testing::AssertionSuccess; -using ::testing::ElementsAre; -using ::testing::IsEmpty; -using ::testing::UnorderedElementsAre; - -namespace http2 { -namespace test { - -using ::spdy::kHttp2MaxStreamWeight; -using ::spdy::kHttp2MinStreamWeight; -using ::spdy::kHttp2RootStreamId; -using ::spdy::kV3LowestPriority; -using ::spdy::SpdyStreamPrecedence; - -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 QuicheTest { - protected: - typedef uint32_t SpdyStreamId; - - Http2PriorityWriteSchedulerTest() : peer_(&scheduler_) {} - - Http2PriorityWriteScheduler<SpdyStreamId> scheduler_; - Http2PriorityWriteSchedulerPeer<SpdyStreamId> peer_; -}; - -TEST_F(Http2PriorityWriteSchedulerTest, RegisterAndUnregisterStreams) { - EXPECT_EQ(1u, scheduler_.NumRegisteredStreams()); - EXPECT_TRUE(scheduler_.StreamRegistered(0)); - EXPECT_FALSE(scheduler_.StreamRegistered(1)); - - scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); - EXPECT_EQ(2u, scheduler_.NumRegisteredStreams()); - 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_QUICHE_BUG( - scheduler_.RegisterStream(5, SpdyStreamPrecedence(1, 50, false)), - "Stream 5 already registered"); - EXPECT_EQ(3u, scheduler_.NumRegisteredStreams()); - 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(4u, scheduler_.NumRegisteredStreams()); - EXPECT_TRUE(scheduler_.StreamRegistered(1)); - EXPECT_TRUE(scheduler_.StreamRegistered(5)); - ASSERT_TRUE(scheduler_.StreamRegistered(13)); - EXPECT_EQ(130, scheduler_.GetStreamPrecedence(13).weight()); - EXPECT_EQ(5u, scheduler_.GetStreamPrecedence(13).parent_id()); - - scheduler_.UnregisterStream(5); - // Cannot remove a stream that has already been removed. - EXPECT_QUICHE_BUG(scheduler_.UnregisterStream(5), "Stream 5 not registered"); - EXPECT_EQ(3u, scheduler_.NumRegisteredStreams()); - 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(0u, scheduler_.GetStreamPrecedence(7).parent_id()); - // Now stream 7 already exists, so this should fail: - EXPECT_QUICHE_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(0u, 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_QUICHE_BUG(scheduler_.RegisterStream(1, SpdyStreamPrecedence(4)), - "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(2u, scheduler_.GetStreamPrecedence(3).parent_id()); - scheduler_.UnregisterStream(3); - EXPECT_EQ(kHttp2RootStreamId, scheduler_.GetStreamPrecedence(3).parent_id()); -} - -TEST_F(Http2PriorityWriteSchedulerTest, GetStreamChildren) { - EXPECT_QUICHE_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_QUICHE_BUG(EXPECT_THAT(scheduler_.GetStreamChildren(7), IsEmpty()), - "Stream 7 not registered"); -} - -TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamWeight) { - EXPECT_QUICHE_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_QUICHE_BUG( - scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 500, false)), - "Invalid weight: 500"); - EXPECT_EQ(kHttp2MaxStreamWeight, scheduler_.GetStreamPrecedence(3).weight()); - EXPECT_QUICHE_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, RegisterStreamParentExclusive) { - /* 0 - / \ - 1 2 - */ - scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); - scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false)); - /* 0 - | - 3 - / \ - 1 2 - */ - scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 100, true)); - EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(3)); - EXPECT_THAT(scheduler_.GetStreamChildren(3), UnorderedElementsAre(1, 2)); - EXPECT_THAT(scheduler_.GetStreamChildren(1), IsEmpty()); - EXPECT_THAT(scheduler_.GetStreamChildren(2), IsEmpty()); - ASSERT_TRUE(peer_.ValidateInvariants()); -} - -TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentExclusive) { - /* 0 - /|\ - 1 2 3 - */ - scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); - scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false)); - scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 100, false)); - /* 0 - | - 1 - / \ - 2 3 - */ - scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(0, 100, true)); - 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, UpdateStreamParentExclusive2) { - /* 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(3, 100, false)); - scheduler_.RegisterStream(5, SpdyStreamPrecedence(3, 100, false)); - scheduler_.RegisterStream(6, SpdyStreamPrecedence(4, 100, false)); - // Update stream 1's parent to 4 exclusive. - /* 0 - | - 4 - | - 1 - /|\ - 2 3 6 - | - 5 - */ - scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(4, 100, true)); - EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(4)); - EXPECT_THAT(scheduler_.GetStreamChildren(4), ElementsAre(1)); - EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(2, 3, 6)); - EXPECT_THAT(scheduler_.GetStreamChildren(2), IsEmpty()); - EXPECT_THAT(scheduler_.GetStreamChildren(3), ElementsAre(5)); - EXPECT_THAT(scheduler_.GetStreamChildren(6), IsEmpty()); - ASSERT_TRUE(peer_.ValidateInvariants()); -} - -TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentNonExclusive) { - /* 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(3, 100, false)); - scheduler_.RegisterStream(5, SpdyStreamPrecedence(3, 100, false)); - scheduler_.RegisterStream(6, SpdyStreamPrecedence(4, 100, false)); - // Update stream 1's parent to 4. - /* 0 - | - 4 - / \ - 6 1 - / \ - 2 3 - | - 5 - */ - scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(4, 100, false)); - EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(4)); - EXPECT_THAT(scheduler_.GetStreamChildren(4), UnorderedElementsAre(6, 1)); - EXPECT_THAT(scheduler_.GetStreamChildren(6), IsEmpty()); - EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(2, 3)); - EXPECT_THAT(scheduler_.GetStreamChildren(2), IsEmpty()); - EXPECT_THAT(scheduler_.GetStreamChildren(3), ElementsAre(5)); - EXPECT_THAT(scheduler_.GetStreamChildren(5), 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)); - EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(2, 3)); - EXPECT_THAT(scheduler_.GetStreamChildren(2), IsEmpty()); - EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); - 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)); - EXPECT_THAT(scheduler_.GetStreamChildren(2), UnorderedElementsAre(3)); - EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); - } - ASSERT_TRUE(peer_.ValidateInvariants()); -} - -TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentToSelf) { - scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); - EXPECT_QUICHE_BUG( - scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(1, 100, false)), - "Cannot set stream to be its own parent"); - EXPECT_QUICHE_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(0u, scheduler_.GetStreamPrecedence(1).parent_id()); - EXPECT_EQ(0u, scheduler_.GetStreamPrecedence(2).parent_id()); - EXPECT_EQ(0u, scheduler_.GetStreamPrecedence(3).parent_id()); - EXPECT_EQ(1u, scheduler_.GetStreamPrecedence(4).parent_id()); - EXPECT_EQ(1u, scheduler_.GetStreamPrecedence(5).parent_id()); - EXPECT_EQ(2u, scheduler_.GetStreamPrecedence(6).parent_id()); - EXPECT_EQ(3u, scheduler_.GetStreamPrecedence(7).parent_id()); - EXPECT_EQ(4u, scheduler_.GetStreamPrecedence(8).parent_id()); - EXPECT_EQ(4u, scheduler_.GetStreamPrecedence(9).parent_id()); - EXPECT_EQ(5u, scheduler_.GetStreamPrecedence(10).parent_id()); - EXPECT_EQ(5u, scheduler_.GetStreamPrecedence(11).parent_id()); - EXPECT_EQ(6u, scheduler_.GetStreamPrecedence(12).parent_id()); - EXPECT_EQ(7u, scheduler_.GetStreamPrecedence(13).parent_id()); - EXPECT_EQ(7u, scheduler_.GetStreamPrecedence(14).parent_id()); - EXPECT_EQ(8u, scheduler_.GetStreamPrecedence(15).parent_id()); - EXPECT_EQ(8u, 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_QUICHE_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_QUICHE_BUG(scheduler_.RecordStreamEventTime(3, 5), - "Stream 3 not registered"); - EXPECT_QUICHE_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(5u, scheduler_.PopNextReadyStream()); - EXPECT_EQ(2u, scheduler_.PopNextReadyStream()); - scheduler_.MarkStreamReady(2, false); - EXPECT_EQ(3u, scheduler_.PopNextReadyStream()); - scheduler_.MarkStreamReady(3, false); - EXPECT_EQ(4u, scheduler_.PopNextReadyStream()); - scheduler_.MarkStreamReady(4, false); - EXPECT_EQ(2u, scheduler_.PopNextReadyStream()); - scheduler_.MarkStreamReady(2, true); - EXPECT_EQ(2u, scheduler_.PopNextReadyStream()); - scheduler_.MarkStreamReady(5, false); - scheduler_.MarkStreamReady(2, true); - EXPECT_EQ(5u, 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()); -} - -TEST_F(Http2PriorityWriteSchedulerTest, ShouldYield) { - /* - 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, 200, false)); - scheduler_.RegisterStream(6, SpdyStreamPrecedence(1, 255, false)); - scheduler_.RegisterStream(7, SpdyStreamPrecedence(2, 100, false)); - scheduler_.RegisterStream(8, SpdyStreamPrecedence(5, 100, false)); - - scheduler_.MarkStreamReady(5, false); - - for (int i = 1; i <= 8; ++i) { - // Verify only 4 and 8 should yield to 5. - if (i == 4 || i == 8) { - EXPECT_TRUE(scheduler_.ShouldYield(i)) << "stream_id: " << i; - } else { - EXPECT_FALSE(scheduler_.ShouldYield(i)) << "stream_id: " << i; - } - } - - // Marks streams 1 and 2 ready. - scheduler_.MarkStreamReady(1, false); - scheduler_.MarkStreamReady(2, false); - // 1 should not yield. - EXPECT_FALSE(scheduler_.ShouldYield(1)); - // Verify 2 should yield to 1. - EXPECT_TRUE(scheduler_.ShouldYield(2)); -} - -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 http2
diff --git a/http2/core/priority_write_scheduler.h b/http2/core/priority_write_scheduler.h index b59e294..87de3a7 100644 --- a/http2/core/priority_write_scheduler.h +++ b/http2/core/priority_write_scheduler.h
@@ -18,6 +18,7 @@ #include "absl/strings/str_cat.h" #include "http2/core/write_scheduler.h" #include "common/platform/api/quiche_bug_tracker.h" +#include "common/platform/api/quiche_export.h" #include "common/platform/api/quiche_logging.h" #include "spdy/core/spdy_protocol.h" @@ -37,9 +38,9 @@ // that priority that are ready to write, as well as a timestamp of the last // I/O event that occurred for a stream of that priority. // -// DO NOT USE. Deprecated. template <typename StreamIdType> -class PriorityWriteScheduler : public WriteScheduler<StreamIdType> { +class QUICHE_EXPORT_PRIVATE PriorityWriteScheduler + : public WriteScheduler<StreamIdType> { public: using typename WriteScheduler<StreamIdType>::StreamPrecedenceType; @@ -286,7 +287,7 @@ // State kept for all registered streams. All ready streams have ready = true // and should be present in priority_infos_[priority].ready_list. - struct StreamInfo { + struct QUICHE_EXPORT_PRIVATE StreamInfo { spdy::SpdyPriority priority; StreamIdType stream_id; bool ready; @@ -296,7 +297,7 @@ using ReadyList = std::deque<StreamInfo*>; // State kept for each priority level. - struct PriorityInfo { + struct QUICHE_EXPORT_PRIVATE PriorityInfo { // IDs of streams that are ready to write. ReadyList ready_list; // Time of latest write event for stream of this priority, in microseconds.
diff --git a/http2/core/write_scheduler.h b/http2/core/write_scheduler.h index 4973a2d..3b58c4f 100644 --- a/http2/core/write_scheduler.h +++ b/http2/core/write_scheduler.h
@@ -22,14 +22,6 @@ // where (writable) higher-priority streams are always given precedence // over lower-priority streams. // -// Http2PriorityWriteScheduler: implements SPDY priority-based stream -// scheduling coupled with the HTTP/2 stream dependency model. This is only -// intended as a transitional step towards Http2WeightedWriteScheduler. -// -// Http2WeightedWriteScheduler (coming soon): implements the HTTP/2 stream -// dependency model with weighted stream scheduling, fully conforming to -// RFC 7540. -// // The type used to represent stream IDs (StreamIdType) is templated in order // to allow for use by both SPDY and QUIC codebases. It must be a POD that // supports comparison (i.e., a numeric type).