| // 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 <string> |
| #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_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; |
| size_t NumRegisteredStreams() const override; |
| std::string DebugString() const override; |
| |
| 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; |
| |
| // 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 ? 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> |
| 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 (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 == 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; |
| } |
| 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 == 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> |
| size_t Http2PriorityWriteScheduler<StreamIdType>::NumRegisteredStreams() const { |
| return all_stream_infos_.size(); |
| } |
| |
| template <typename StreamIdType> |
| std::string Http2PriorityWriteScheduler<StreamIdType>::DebugString() const { |
| return SpdyStrCat("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) { |
| 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 NumRegisteredStreams() reflects the total number of streams the |
| // map contains. |
| if (total_streams != NumRegisteredStreams()) { |
| 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 * NumRegisteredStreams() - 1); |
| return true; |
| } |
| |
| } // namespace spdy |
| |
| #endif // QUICHE_SPDY_CORE_HTTP2_PRIORITY_WRITE_SCHEDULER_H_ |