Index: net/spdy/priority_write_scheduler.h |
diff --git a/net/spdy/priority_write_scheduler.h b/net/spdy/priority_write_scheduler.h |
deleted file mode 100644 |
index 2a8276c16c0d4b2da83141641cd1677ac8f42ce9..0000000000000000000000000000000000000000 |
--- a/net/spdy/priority_write_scheduler.h |
+++ /dev/null |
@@ -1,298 +0,0 @@ |
-// Copyright (c) 2015 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 NET_SPDY_PRIORITY_WRITE_SCHEDULER_H_ |
-#define NET_SPDY_PRIORITY_WRITE_SCHEDULER_H_ |
- |
-#include <stddef.h> |
-#include <stdint.h> |
- |
-#include <algorithm> |
-#include <deque> |
-#include <tuple> |
-#include <unordered_map> |
-#include <utility> |
-#include <vector> |
- |
-#include "base/logging.h" |
-#include "net/spdy/spdy_bug_tracker.h" |
-#include "net/spdy/spdy_protocol.h" |
-#include "net/spdy/write_scheduler.h" |
- |
-namespace net { |
- |
-namespace test { |
-template <typename StreamIdType> |
-class PriorityWriteSchedulerPeer; |
-} |
- |
-// WriteScheduler implementation that manages the order in which streams are |
-// written using the SPDY priority scheme described at: |
-// https://www.chromium.org/spdy/spdy-protocol/spdy-protocol-draft3-1#TOC-2.3.3-Stream-priority |
-// |
-// Internally, PriorityWriteScheduler consists of 8 PriorityInfo objects, one |
-// for each priority value. Each PriorityInfo contains a list of streams of |
-// 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. |
-template <typename StreamIdType> |
-class PriorityWriteScheduler : public WriteScheduler<StreamIdType> { |
- public: |
- using typename WriteScheduler<StreamIdType>::StreamPrecedenceType; |
- |
- // Creates scheduler with no streams. |
- PriorityWriteScheduler() = default; |
- |
- void RegisterStream(StreamIdType stream_id, |
- const StreamPrecedenceType& precedence) override { |
- SPDY_BUG_IF(!precedence.is_spdy3_priority()) << "Expected SPDY priority"; |
- |
- // parent_id not used here, but may as well validate it. However, |
- // parent_id may legitimately not be registered yet--see b/15676312. |
- StreamIdType parent_id = precedence.parent_id(); |
- DVLOG_IF(1, parent_id != kHttp2RootStreamId && !StreamRegistered(parent_id)) |
- << "Parent stream " << parent_id << " not registered"; |
- |
- if (stream_id == kHttp2RootStreamId) { |
- SPDY_BUG << "Stream " << kHttp2RootStreamId << " already registered"; |
- return; |
- } |
- StreamInfo stream_info = {precedence.spdy3_priority(), stream_id, false}; |
- bool inserted = |
- stream_infos_.insert(std::make_pair(stream_id, stream_info)).second; |
- SPDY_BUG_IF(!inserted) << "Stream " << stream_id << " already registered"; |
- } |
- |
- void UnregisterStream(StreamIdType stream_id) override { |
- auto it = stream_infos_.find(stream_id); |
- if (it == stream_infos_.end()) { |
- SPDY_BUG << "Stream " << stream_id << " not registered"; |
- return; |
- } |
- StreamInfo& stream_info = it->second; |
- if (stream_info.ready) { |
- bool erased = |
- Erase(&priority_infos_[stream_info.priority].ready_list, stream_info); |
- DCHECK(erased); |
- } |
- stream_infos_.erase(it); |
- } |
- |
- bool StreamRegistered(StreamIdType stream_id) const override { |
- return stream_infos_.find(stream_id) != stream_infos_.end(); |
- } |
- |
- StreamPrecedenceType GetStreamPrecedence( |
- StreamIdType stream_id) const override { |
- auto it = stream_infos_.find(stream_id); |
- if (it == stream_infos_.end()) { |
- DVLOG(1) << "Stream " << stream_id << " not registered"; |
- return StreamPrecedenceType(kV3LowestPriority); |
- } |
- return StreamPrecedenceType(it->second.priority); |
- } |
- |
- void UpdateStreamPrecedence(StreamIdType stream_id, |
- const StreamPrecedenceType& precedence) override { |
- SPDY_BUG_IF(!precedence.is_spdy3_priority()) << "Expected SPDY priority"; |
- |
- // parent_id not used here, but may as well validate it. However, |
- // parent_id may legitimately not be registered yet--see b/15676312. |
- StreamIdType parent_id = precedence.parent_id(); |
- DVLOG_IF(1, parent_id != kHttp2RootStreamId && !StreamRegistered(parent_id)) |
- << "Parent stream " << parent_id << " not registered"; |
- |
- auto it = stream_infos_.find(stream_id); |
- if (it == stream_infos_.end()) { |
- // TODO(mpw): add to stream_infos_ on demand--see b/15676312. |
- DVLOG(1) << "Stream " << stream_id << " not registered"; |
- return; |
- } |
- StreamInfo& stream_info = it->second; |
- SpdyPriority new_priority = precedence.spdy3_priority(); |
- if (stream_info.priority == new_priority) { |
- return; |
- } |
- if (stream_info.ready) { |
- bool erased = |
- Erase(&priority_infos_[stream_info.priority].ready_list, stream_info); |
- DCHECK(erased); |
- priority_infos_[new_priority].ready_list.push_back(&stream_info); |
- ++num_ready_streams_; |
- } |
- stream_info.priority = new_priority; |
- } |
- |
- std::vector<StreamIdType> GetStreamChildren( |
- StreamIdType stream_id) const override { |
- return std::vector<StreamIdType>(); |
- } |
- |
- void RecordStreamEventTime(StreamIdType stream_id, |
- int64_t now_in_usec) override { |
- auto it = stream_infos_.find(stream_id); |
- if (it == stream_infos_.end()) { |
- SPDY_BUG << "Stream " << stream_id << " not registered"; |
- return; |
- } |
- PriorityInfo& priority_info = priority_infos_[it->second.priority]; |
- priority_info.last_event_time_usec = |
- std::max(priority_info.last_event_time_usec, now_in_usec); |
- } |
- |
- int64_t GetLatestEventWithPrecedence(StreamIdType stream_id) const override { |
- auto it = stream_infos_.find(stream_id); |
- if (it == stream_infos_.end()) { |
- SPDY_BUG << "Stream " << stream_id << " not registered"; |
- return 0; |
- } |
- int64_t last_event_time_usec = 0; |
- const StreamInfo& stream_info = it->second; |
- for (SpdyPriority p = kV3HighestPriority; p < stream_info.priority; ++p) { |
- last_event_time_usec = std::max(last_event_time_usec, |
- priority_infos_[p].last_event_time_usec); |
- } |
- return last_event_time_usec; |
- } |
- |
- StreamIdType PopNextReadyStream() override { |
- return std::get<0>(PopNextReadyStreamAndPrecedence()); |
- } |
- |
- // Returns the next ready stream and its precedence. |
- std::tuple<StreamIdType, StreamPrecedenceType> |
- PopNextReadyStreamAndPrecedence() override { |
- for (SpdyPriority p = kV3HighestPriority; p <= kV3LowestPriority; ++p) { |
- ReadyList& ready_list = priority_infos_[p].ready_list; |
- if (!ready_list.empty()) { |
- StreamInfo* info = ready_list.front(); |
- ready_list.pop_front(); |
- --num_ready_streams_; |
- |
- DCHECK(stream_infos_.find(info->stream_id) != stream_infos_.end()); |
- info->ready = false; |
- return std::make_tuple(info->stream_id, |
- StreamPrecedenceType(info->priority)); |
- } |
- } |
- SPDY_BUG << "No ready streams available"; |
- return std::make_tuple(0, StreamPrecedenceType(kV3LowestPriority)); |
- } |
- |
- bool ShouldYield(StreamIdType stream_id) const override { |
- auto it = stream_infos_.find(stream_id); |
- if (it == stream_infos_.end()) { |
- SPDY_BUG << "Stream " << stream_id << " not registered"; |
- return false; |
- } |
- |
- // If there's a higher priority stream, this stream should yield. |
- const StreamInfo& stream_info = it->second; |
- for (SpdyPriority p = kV3HighestPriority; p < stream_info.priority; ++p) { |
- if (!priority_infos_[p].ready_list.empty()) { |
- return true; |
- } |
- } |
- |
- // If this priority level is empty, or this stream is the next up, there's |
- // no need to yield. |
- const auto& ready_list = priority_infos_[it->second.priority].ready_list; |
- if (ready_list.empty() || ready_list.front()->stream_id == stream_id) { |
- return false; |
- } |
- |
- // There are other streams in this priority level which take precedence. |
- // Yield. |
- return true; |
- } |
- |
- void MarkStreamReady(StreamIdType stream_id, bool add_to_front) override { |
- auto it = stream_infos_.find(stream_id); |
- if (it == stream_infos_.end()) { |
- SPDY_BUG << "Stream " << stream_id << " not registered"; |
- return; |
- } |
- StreamInfo& stream_info = it->second; |
- if (stream_info.ready) { |
- return; |
- } |
- ReadyList& ready_list = priority_infos_[stream_info.priority].ready_list; |
- if (add_to_front) { |
- ready_list.push_front(&stream_info); |
- } else { |
- ready_list.push_back(&stream_info); |
- } |
- ++num_ready_streams_; |
- stream_info.ready = true; |
- } |
- |
- void MarkStreamNotReady(StreamIdType stream_id) override { |
- auto it = stream_infos_.find(stream_id); |
- if (it == stream_infos_.end()) { |
- SPDY_BUG << "Stream " << stream_id << " not registered"; |
- return; |
- } |
- StreamInfo& stream_info = it->second; |
- if (!stream_info.ready) { |
- return; |
- } |
- bool erased = |
- Erase(&priority_infos_[stream_info.priority].ready_list, stream_info); |
- DCHECK(erased); |
- stream_info.ready = false; |
- } |
- |
- // Returns true iff the number of ready streams is non-zero. |
- bool HasReadyStreams() const override { return num_ready_streams_ > 0; } |
- |
- // Returns the number of ready streams. |
- size_t NumReadyStreams() const override { return num_ready_streams_; } |
- |
- private: |
- friend class test::PriorityWriteSchedulerPeer<StreamIdType>; |
- |
- // State kept for all registered streams. All ready streams have ready = true |
- // and should be present in priority_infos_[priority].ready_list. |
- struct StreamInfo { |
- SpdyPriority priority; |
- StreamIdType stream_id; |
- bool ready; |
- }; |
- |
- // 0(1) size lookup, 0(1) insert at front or back. |
- typedef std::deque<StreamInfo*> ReadyList; |
- |
- // State kept for each priority level. |
- struct PriorityInfo { |
- // IDs of streams that are ready to write. |
- ReadyList ready_list; |
- // Time of latest write event for stream of this priority, in microseconds. |
- int64_t last_event_time_usec = 0; |
- }; |
- |
- typedef std::unordered_map<StreamIdType, StreamInfo> StreamInfoMap; |
- |
- // Erases first occurrence (which should be the only one) of |info| in |
- // |ready_list|, returning true if found (and erased), or false otherwise. |
- // Decrements |num_ready_streams_| if an entry is erased. |
- bool Erase(ReadyList* ready_list, const StreamInfo& info) { |
- auto it = std::find(ready_list->begin(), ready_list->end(), &info); |
- if (it == ready_list->end()) { |
- return false; |
- } |
- ready_list->erase(it); |
- --num_ready_streams_; |
- return true; |
- } |
- |
- // Number of ready streams. |
- size_t num_ready_streams_ = 0; |
- // Per-priority state, including ready lists. |
- PriorityInfo priority_infos_[kV3LowestPriority + 1]; |
- // StreamInfos for all registered streams. |
- StreamInfoMap stream_infos_; |
-}; |
- |
-} // namespace net |
- |
-#endif // NET_SPDY_PRIORITY_WRITE_SCHEDULER_H_ |