| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright 2015 The Chromium Authors. All rights reserved. | |
| 2 // Use of this source code is governed by a BSD-style license that can be | |
| 3 // found in the LICENSE file. | |
| 4 | |
| 5 #ifndef NET_SPDY_HTTP2_WRITE_SCHEDULER_H_ | |
| 6 #define NET_SPDY_HTTP2_WRITE_SCHEDULER_H_ | |
| 7 | |
| 8 #include <stdint.h> | |
| 9 | |
| 10 #include <algorithm> | |
| 11 #include <cmath> | |
| 12 #include <deque> | |
| 13 #include <map> | |
| 14 #include <memory> | |
| 15 #include <queue> | |
| 16 #include <set> | |
| 17 #include <tuple> | |
| 18 #include <unordered_map> | |
| 19 #include <utility> | |
| 20 #include <vector> | |
| 21 | |
| 22 #include "base/containers/linked_list.h" | |
| 23 #include "base/containers/small_map.h" | |
| 24 #include "base/logging.h" | |
| 25 #include "base/macros.h" | |
| 26 #include "base/memory/ptr_util.h" | |
| 27 #include "base/stl_util.h" | |
| 28 #include "net/spdy/spdy_bug_tracker.h" | |
| 29 #include "net/spdy/spdy_protocol.h" | |
| 30 #include "net/spdy/write_scheduler.h" | |
| 31 | |
| 32 namespace net { | |
| 33 | |
| 34 namespace test { | |
| 35 template <typename StreamIdType> | |
| 36 class Http2PriorityWriteSchedulerPeer; | |
| 37 } | |
| 38 | |
| 39 // This data structure implements the HTTP/2 stream priority tree defined in | |
| 40 // section 5.3 of RFC 7540: | |
| 41 // http://tools.ietf.org/html/rfc7540#section-5.3 | |
| 42 // | |
| 43 // Streams can be added and removed, and dependencies between them defined. | |
| 44 // Streams constitute a tree rooted at stream ID 0: each stream has a single | |
| 45 // parent stream, and 0 or more child streams. Individual streams can be | |
| 46 // marked as ready to read/write, and then the whole structure can be queried | |
| 47 // to pick the next stream to read/write out of those that are ready. | |
| 48 template <typename StreamIdType> | |
| 49 class Http2PriorityWriteScheduler : public WriteScheduler<StreamIdType> { | |
| 50 public: | |
| 51 using typename WriteScheduler<StreamIdType>::StreamPrecedenceType; | |
| 52 | |
| 53 Http2PriorityWriteScheduler(); | |
| 54 | |
| 55 // WriteScheduler methods | |
| 56 void RegisterStream(StreamIdType stream_id, | |
| 57 const StreamPrecedenceType& precedence) override; | |
| 58 void UnregisterStream(StreamIdType stream_id) override; | |
| 59 bool StreamRegistered(StreamIdType stream_id) const override; | |
| 60 StreamPrecedenceType GetStreamPrecedence( | |
| 61 StreamIdType stream_id) const override; | |
| 62 void UpdateStreamPrecedence(StreamIdType stream_id, | |
| 63 const StreamPrecedenceType& precedence) override; | |
| 64 std::vector<StreamIdType> GetStreamChildren( | |
| 65 StreamIdType stream_id) const override; | |
| 66 void RecordStreamEventTime(StreamIdType stream_id, | |
| 67 int64_t now_in_usec) override; | |
| 68 int64_t GetLatestEventWithPrecedence(StreamIdType stream_id) const override; | |
| 69 bool ShouldYield(StreamIdType stream_id) const override; | |
| 70 void MarkStreamReady(StreamIdType stream_id, bool add_to_front) override; | |
| 71 void MarkStreamNotReady(StreamIdType stream_id) override; | |
| 72 bool HasReadyStreams() const override; | |
| 73 StreamIdType PopNextReadyStream() override; | |
| 74 std::tuple<StreamIdType, StreamPrecedenceType> | |
| 75 PopNextReadyStreamAndPrecedence() override; | |
| 76 size_t NumReadyStreams() const override; | |
| 77 | |
| 78 // Return the number of streams currently in the tree. | |
| 79 int num_streams() const; | |
| 80 | |
| 81 private: | |
| 82 friend class test::Http2PriorityWriteSchedulerPeer<StreamIdType>; | |
| 83 | |
| 84 struct StreamInfo; | |
| 85 using StreamInfoVector = std::vector<StreamInfo*>; | |
| 86 | |
| 87 struct StreamInfo : public base::LinkNode<StreamInfo> { | |
| 88 // ID for this stream. | |
| 89 StreamIdType id; | |
| 90 // StreamInfo for parent stream. | |
| 91 StreamInfo* parent = nullptr; | |
| 92 // Weights can range between 1 and 256 (inclusive). | |
| 93 int weight = kHttp2DefaultStreamWeight; | |
| 94 // The total weight of this stream's direct descendants. | |
| 95 int total_child_weights = 0; | |
| 96 // Pointers to StreamInfos for children, if any. | |
| 97 StreamInfoVector children; | |
| 98 // Whether the stream is ready for writing. The stream is present in | |
| 99 // scheduling_queue_ iff true. | |
| 100 bool ready = false; | |
| 101 // The scheduling priority of this stream. Streams with higher priority | |
| 102 // values are scheduled first. | |
| 103 // TODO(mpw): rename to avoid confusion with SPDY priorities, | |
| 104 // which this is not. | |
| 105 float priority = 0; | |
| 106 // Ordinal value for this stream, used to ensure round-robin scheduling: | |
| 107 // among streams with the same scheduling priority, streams with lower | |
| 108 // ordinal are scheduled first. | |
| 109 int64_t ordinal = 0; | |
| 110 // Time of latest write event for stream of this priority, in microseconds. | |
| 111 int64_t last_event_time_usec = 0; | |
| 112 | |
| 113 // Whether this stream should be scheduled ahead of another stream. | |
| 114 bool SchedulesBefore(const StreamInfo& other) const { | |
| 115 return (priority != other.priority) ? priority > other.priority | |
| 116 : ordinal < other.ordinal; | |
| 117 } | |
| 118 | |
| 119 // Returns the StreamPrecedenceType for this StreamInfo. | |
| 120 StreamPrecedenceType ToStreamPrecedence() const { | |
| 121 StreamIdType parent_id = | |
| 122 parent == nullptr ? kHttp2RootStreamId : parent->id; | |
| 123 bool exclusive = parent != nullptr && parent->children.size() == 1; | |
| 124 return StreamPrecedenceType(parent_id, weight, exclusive); | |
| 125 } | |
| 126 }; | |
| 127 | |
| 128 static bool Remove(StreamInfoVector* stream_infos, | |
| 129 const StreamInfo* stream_info); | |
| 130 | |
| 131 // Returns true iff any direct or transitive parent of the given stream is | |
| 132 // currently ready. | |
| 133 static bool HasReadyAncestor(const StreamInfo& stream_info); | |
| 134 | |
| 135 // Returns StreamInfo for the given stream, or nullptr if it isn't | |
| 136 // registered. | |
| 137 const StreamInfo* FindStream(StreamIdType stream_id) const; | |
| 138 StreamInfo* FindStream(StreamIdType stream_id); | |
| 139 | |
| 140 // Helpers for UpdateStreamPrecedence(). | |
| 141 void UpdateStreamParent(StreamInfo* stream_info, | |
| 142 StreamIdType parent_id, | |
| 143 bool exclusive); | |
| 144 void UpdateStreamWeight(StreamInfo* stream_info, int weight); | |
| 145 | |
| 146 // Update all priority values in the subtree rooted at the given stream, not | |
| 147 // including the stream itself. If this results in priority value changes for | |
| 148 // scheduled streams, those streams are rescheduled to ensure proper ordering | |
| 149 // of scheduling_queue_. | |
| 150 // TODO(mpw): rename to avoid confusion with SPDY priorities. | |
| 151 void UpdatePrioritiesUnder(StreamInfo* stream_info); | |
| 152 | |
| 153 // Inserts stream into scheduling_queue_ at the appropriate location given | |
| 154 // its priority and ordinal. Time complexity is O(scheduling_queue.size()). | |
| 155 void Schedule(StreamInfo* stream_info); | |
| 156 | |
| 157 // Removes stream from scheduling_queue_. | |
| 158 void Unschedule(StreamInfo* stream_info); | |
| 159 | |
| 160 // Return true if all internal invariants hold (useful for unit tests). | |
| 161 // Unless there are bugs, this should always return true. | |
| 162 bool ValidateInvariantsForTests() const; | |
| 163 | |
| 164 // Returns true if the parent stream has the given stream in its children. | |
| 165 bool StreamHasChild(const StreamInfo& parent_info, | |
| 166 const StreamInfo* child_info) const; | |
| 167 | |
| 168 // Pointee owned by all_stream_infos_. | |
| 169 StreamInfo* root_stream_info_; | |
| 170 // Maps from stream IDs to StreamInfo objects. | |
| 171 base::SmallMap<std::unordered_map<StreamIdType, std::unique_ptr<StreamInfo>>, | |
| 172 10> | |
| 173 all_stream_infos_; | |
| 174 // Queue containing all ready streams, ordered with streams of higher | |
| 175 // priority before streams of lower priority, and, among streams of equal | |
| 176 // priority, streams with lower ordinal before those with higher | |
| 177 // ordinal. Note that not all streams in scheduling_queue_ are eligible to be | |
| 178 // picked as the next stream: some may have ancestor stream(s) that are ready | |
| 179 // and unblocked. In these situations the occluded child streams are left in | |
| 180 // the queue, to reduce churn. | |
| 181 base::LinkedList<StreamInfo> scheduling_queue_; | |
| 182 // Ordinal value to assign to next node inserted into scheduling_queue_ when | |
| 183 // |add_to_front == true|. Decremented after each assignment. | |
| 184 int64_t head_ordinal_ = -1; | |
| 185 // Ordinal value to assign to next node inserted into scheduling_queue_ when | |
| 186 // |add_to_front == false|. Incremented after each assignment. | |
| 187 int64_t tail_ordinal_ = 0; | |
| 188 | |
| 189 DISALLOW_COPY_AND_ASSIGN(Http2PriorityWriteScheduler); | |
| 190 }; | |
| 191 | |
| 192 template <typename StreamIdType> | |
| 193 Http2PriorityWriteScheduler<StreamIdType>::Http2PriorityWriteScheduler() { | |
| 194 std::unique_ptr<StreamInfo> root_stream_info = base::MakeUnique<StreamInfo>(); | |
| 195 root_stream_info_ = root_stream_info.get(); | |
| 196 root_stream_info->id = kHttp2RootStreamId; | |
| 197 root_stream_info->weight = kHttp2DefaultStreamWeight; | |
| 198 root_stream_info->parent = nullptr; | |
| 199 root_stream_info->priority = 1.0; | |
| 200 root_stream_info->ready = false; | |
| 201 all_stream_infos_[kHttp2RootStreamId] = std::move(root_stream_info); | |
| 202 } | |
| 203 | |
| 204 template <typename StreamIdType> | |
| 205 int Http2PriorityWriteScheduler<StreamIdType>::num_streams() const { | |
| 206 return all_stream_infos_.size(); | |
| 207 } | |
| 208 | |
| 209 template <typename StreamIdType> | |
| 210 bool Http2PriorityWriteScheduler<StreamIdType>::StreamRegistered( | |
| 211 StreamIdType stream_id) const { | |
| 212 return base::ContainsKey(all_stream_infos_, stream_id); | |
| 213 } | |
| 214 | |
| 215 template <typename StreamIdType> | |
| 216 void Http2PriorityWriteScheduler<StreamIdType>::RegisterStream( | |
| 217 StreamIdType stream_id, | |
| 218 const StreamPrecedenceType& precedence) { | |
| 219 SPDY_BUG_IF(precedence.is_spdy3_priority()) | |
| 220 << "Expected HTTP/2 stream dependency"; | |
| 221 | |
| 222 if (StreamRegistered(stream_id)) { | |
| 223 SPDY_BUG << "Stream " << stream_id << " already registered"; | |
| 224 return; | |
| 225 } | |
| 226 | |
| 227 StreamInfo* parent = FindStream(precedence.parent_id()); | |
| 228 if (parent == nullptr) { | |
| 229 // parent_id may legitimately not be registered yet--see b/15676312. | |
| 230 DVLOG(1) << "Parent stream " << precedence.parent_id() << " not registered"; | |
| 231 parent = root_stream_info_; | |
| 232 } | |
| 233 | |
| 234 std::unique_ptr<StreamInfo> new_stream_info = base::MakeUnique<StreamInfo>(); | |
| 235 StreamInfo* new_stream_info_ptr = new_stream_info.get(); | |
| 236 new_stream_info_ptr->id = stream_id; | |
| 237 new_stream_info_ptr->weight = precedence.weight(); | |
| 238 new_stream_info_ptr->parent = parent; | |
| 239 all_stream_infos_[stream_id] = std::move(new_stream_info); | |
| 240 if (precedence.is_exclusive()) { | |
| 241 // Move the parent's current children below the new stream. | |
| 242 using std::swap; | |
| 243 swap(new_stream_info_ptr->children, parent->children); | |
| 244 new_stream_info_ptr->total_child_weights = parent->total_child_weights; | |
| 245 // Update each child's parent. | |
| 246 for (StreamInfo* child : new_stream_info_ptr->children) { | |
| 247 child->parent = new_stream_info_ptr; | |
| 248 } | |
| 249 // Clear parent's old child data. | |
| 250 DCHECK(parent->children.empty()); | |
| 251 parent->total_child_weights = 0; | |
| 252 } | |
| 253 // Add new stream to parent. | |
| 254 parent->children.push_back(new_stream_info_ptr); | |
| 255 parent->total_child_weights += precedence.weight(); | |
| 256 | |
| 257 // Update all priorities under parent, since addition of a stream affects | |
| 258 // sibling priorities as well. | |
| 259 UpdatePrioritiesUnder(parent); | |
| 260 | |
| 261 // Stream starts with ready == false, so no need to schedule it yet. | |
| 262 DCHECK(!new_stream_info_ptr->ready); | |
| 263 } | |
| 264 | |
| 265 template <typename StreamIdType> | |
| 266 void Http2PriorityWriteScheduler<StreamIdType>::UnregisterStream( | |
| 267 StreamIdType stream_id) { | |
| 268 if (stream_id == kHttp2RootStreamId) { | |
| 269 SPDY_BUG << "Cannot unregister root stream"; | |
| 270 return; | |
| 271 } | |
| 272 // Remove the stream from table. | |
| 273 auto it = all_stream_infos_.find(stream_id); | |
| 274 if (it == all_stream_infos_.end()) { | |
| 275 SPDY_BUG << "Stream " << stream_id << " not registered"; | |
| 276 return; | |
| 277 } | |
| 278 std::unique_ptr<StreamInfo> stream_info(std::move(it->second)); | |
| 279 all_stream_infos_.erase(it); | |
| 280 // If ready (and hence scheduled), unschedule. | |
| 281 if (stream_info->ready) { | |
| 282 Unschedule(stream_info.get()); | |
| 283 } | |
| 284 | |
| 285 StreamInfo* parent = stream_info->parent; | |
| 286 // Remove the stream from parent's child list. | |
| 287 Remove(&parent->children, stream_info.get()); | |
| 288 parent->total_child_weights -= stream_info->weight; | |
| 289 | |
| 290 // Move the stream's children to the parent's child list. | |
| 291 // Update each child's parent and weight. | |
| 292 for (StreamInfo* child : stream_info->children) { | |
| 293 child->parent = parent; | |
| 294 parent->children.push_back(child); | |
| 295 // Divide the removed stream's weight among its children, rounding to the | |
| 296 // nearest valid weight. | |
| 297 float float_weight = stream_info->weight * | |
| 298 static_cast<float>(child->weight) / | |
| 299 static_cast<float>(stream_info->total_child_weights); | |
| 300 int new_weight = floor(float_weight + 0.5); | |
| 301 if (new_weight == 0) { | |
| 302 new_weight = 1; | |
| 303 } | |
| 304 child->weight = new_weight; | |
| 305 parent->total_child_weights += child->weight; | |
| 306 } | |
| 307 UpdatePrioritiesUnder(parent); | |
| 308 } | |
| 309 | |
| 310 template <typename StreamIdType> | |
| 311 typename Http2PriorityWriteScheduler<StreamIdType>::StreamPrecedenceType | |
| 312 Http2PriorityWriteScheduler<StreamIdType>::GetStreamPrecedence( | |
| 313 StreamIdType stream_id) const { | |
| 314 const StreamInfo* stream_info = FindStream(stream_id); | |
| 315 if (stream_info == nullptr) { | |
| 316 // Unknown streams tolerated due to b/15676312. However, return lowest | |
| 317 // weight. | |
| 318 DVLOG(1) << "Stream " << stream_id << " not registered"; | |
| 319 return StreamPrecedenceType(kHttp2RootStreamId, kHttp2MinStreamWeight, | |
| 320 false); | |
| 321 } | |
| 322 return stream_info->ToStreamPrecedence(); | |
| 323 } | |
| 324 | |
| 325 template <typename StreamIdType> | |
| 326 std::vector<StreamIdType> Http2PriorityWriteScheduler< | |
| 327 StreamIdType>::GetStreamChildren(StreamIdType stream_id) const { | |
| 328 std::vector<StreamIdType> child_vec; | |
| 329 const StreamInfo* stream_info = FindStream(stream_id); | |
| 330 if (stream_info == nullptr) { | |
| 331 SPDY_BUG << "Stream " << stream_id << " not registered"; | |
| 332 } else { | |
| 333 child_vec.reserve(stream_info->children.size()); | |
| 334 for (StreamInfo* child : stream_info->children) { | |
| 335 child_vec.push_back(child->id); | |
| 336 } | |
| 337 } | |
| 338 return child_vec; | |
| 339 } | |
| 340 | |
| 341 template <typename StreamIdType> | |
| 342 void Http2PriorityWriteScheduler<StreamIdType>::UpdateStreamPrecedence( | |
| 343 StreamIdType stream_id, | |
| 344 const StreamPrecedenceType& precedence) { | |
| 345 SPDY_BUG_IF(precedence.is_spdy3_priority()) | |
| 346 << "Expected HTTP/2 stream dependency"; | |
| 347 if (stream_id == kHttp2RootStreamId) { | |
| 348 SPDY_BUG << "Cannot set precedence of root stream"; | |
| 349 return; | |
| 350 } | |
| 351 | |
| 352 StreamInfo* stream_info = FindStream(stream_id); | |
| 353 if (stream_info == nullptr) { | |
| 354 // TODO(mpw): add to all_stream_infos_ on demand--see b/15676312. | |
| 355 DVLOG(1) << "Stream " << stream_id << " not registered"; | |
| 356 return; | |
| 357 } | |
| 358 UpdateStreamParent(stream_info, precedence.parent_id(), | |
| 359 precedence.is_exclusive()); | |
| 360 UpdateStreamWeight(stream_info, precedence.weight()); | |
| 361 } | |
| 362 | |
| 363 template <typename StreamIdType> | |
| 364 void Http2PriorityWriteScheduler<StreamIdType>::UpdateStreamWeight( | |
| 365 StreamInfo* stream_info, | |
| 366 int weight) { | |
| 367 if (weight == stream_info->weight) { | |
| 368 return; | |
| 369 } | |
| 370 if (stream_info->parent != nullptr) { | |
| 371 stream_info->parent->total_child_weights += (weight - stream_info->weight); | |
| 372 } | |
| 373 stream_info->weight = weight; | |
| 374 | |
| 375 // Change in weight also affects sibling priorities. | |
| 376 UpdatePrioritiesUnder(stream_info->parent); | |
| 377 } | |
| 378 | |
| 379 template <typename StreamIdType> | |
| 380 void Http2PriorityWriteScheduler<StreamIdType>::UpdateStreamParent( | |
| 381 StreamInfo* stream_info, | |
| 382 StreamIdType parent_id, | |
| 383 bool exclusive) { | |
| 384 if (stream_info->id == parent_id) { | |
| 385 SPDY_BUG << "Cannot set stream to be its own parent"; | |
| 386 return; | |
| 387 } | |
| 388 StreamInfo* new_parent = FindStream(parent_id); | |
| 389 if (new_parent == nullptr) { | |
| 390 // parent_id may legitimately not be registered yet--see b/15676312. | |
| 391 DVLOG(1) << "Parent stream " << parent_id << " not registered"; | |
| 392 return; | |
| 393 } | |
| 394 | |
| 395 // If the new parent is already the stream's parent, we're done. | |
| 396 if (stream_info->parent == new_parent) { | |
| 397 return; | |
| 398 } | |
| 399 | |
| 400 // Next, check to see if the new parent is currently a descendant | |
| 401 // of the stream. | |
| 402 StreamInfo* last = new_parent->parent; | |
| 403 bool cycle_exists = false; | |
| 404 while (last != nullptr) { | |
| 405 if (last == stream_info) { | |
| 406 cycle_exists = true; | |
| 407 break; | |
| 408 } | |
| 409 last = last->parent; | |
| 410 } | |
| 411 | |
| 412 if (cycle_exists) { | |
| 413 // The new parent moves to the level of the current stream. | |
| 414 UpdateStreamParent(new_parent, stream_info->parent->id, false); | |
| 415 } | |
| 416 | |
| 417 // Remove stream from old parent's child list. | |
| 418 StreamInfo* old_parent = stream_info->parent; | |
| 419 Remove(&old_parent->children, stream_info); | |
| 420 old_parent->total_child_weights -= stream_info->weight; | |
| 421 UpdatePrioritiesUnder(old_parent); | |
| 422 | |
| 423 if (exclusive) { | |
| 424 // Move the new parent's current children below the current stream. | |
| 425 for (StreamInfo* child : new_parent->children) { | |
| 426 child->parent = stream_info; | |
| 427 stream_info->children.push_back(child); | |
| 428 } | |
| 429 stream_info->total_child_weights += new_parent->total_child_weights; | |
| 430 // Clear new parent's old child data. | |
| 431 new_parent->children.clear(); | |
| 432 new_parent->total_child_weights = 0; | |
| 433 } | |
| 434 | |
| 435 // Make the change. | |
| 436 stream_info->parent = new_parent; | |
| 437 new_parent->children.push_back(stream_info); | |
| 438 new_parent->total_child_weights += stream_info->weight; | |
| 439 UpdatePrioritiesUnder(new_parent); | |
| 440 } | |
| 441 | |
| 442 template <typename StreamIdType> | |
| 443 void Http2PriorityWriteScheduler<StreamIdType>::RecordStreamEventTime( | |
| 444 StreamIdType stream_id, | |
| 445 int64_t now_in_usec) { | |
| 446 if (stream_id == kHttp2RootStreamId) { | |
| 447 SPDY_BUG << "Cannot record event time for root stream"; | |
| 448 return; | |
| 449 } | |
| 450 StreamInfo* stream_info = FindStream(stream_id); | |
| 451 if (stream_info == nullptr) { | |
| 452 SPDY_BUG << "Stream " << stream_id << " not registered"; | |
| 453 return; | |
| 454 } | |
| 455 stream_info->last_event_time_usec = now_in_usec; | |
| 456 } | |
| 457 | |
| 458 // O(n) in the number of streams, which isn't great. However, this method will | |
| 459 // soon be superseded by | |
| 460 // Http2WeightedWriteScheduler::GetLatestEventWithPrecedence(), for which an | |
| 461 // efficient implementation is straightforward. Also, this method is only | |
| 462 // called when calculating idle timeouts, so performance isn't key. | |
| 463 template <typename StreamIdType> | |
| 464 int64_t Http2PriorityWriteScheduler<StreamIdType>::GetLatestEventWithPrecedence( | |
| 465 StreamIdType stream_id) const { | |
| 466 if (stream_id == kHttp2RootStreamId) { | |
| 467 SPDY_BUG << "Invalid argument: root stream"; | |
| 468 return 0; | |
| 469 } | |
| 470 const StreamInfo* stream_info = FindStream(stream_id); | |
| 471 if (stream_info == nullptr) { | |
| 472 SPDY_BUG << "Stream " << stream_id << " not registered"; | |
| 473 return 0; | |
| 474 } | |
| 475 int64_t last_event_time_usec = 0; | |
| 476 for (const auto& kv : all_stream_infos_) { | |
| 477 const StreamInfo& other = *kv.second; | |
| 478 if (other.priority > stream_info->priority) { | |
| 479 last_event_time_usec = | |
| 480 std::max(last_event_time_usec, other.last_event_time_usec); | |
| 481 } | |
| 482 } | |
| 483 return last_event_time_usec; | |
| 484 } | |
| 485 | |
| 486 // Worst-case time complexity of O(n*d), where n is scheduling queue length and | |
| 487 // d is tree depth. In practice, should be much shorter, since loop terminates | |
| 488 // at first writable stream or |stream_id| (whichever is first). | |
| 489 template <typename StreamIdType> | |
| 490 bool Http2PriorityWriteScheduler<StreamIdType>::ShouldYield( | |
| 491 StreamIdType stream_id) const { | |
| 492 if (stream_id == kHttp2RootStreamId) { | |
| 493 SPDY_BUG << "Invalid argument: root stream"; | |
| 494 return false; | |
| 495 } | |
| 496 const StreamInfo* stream_info = FindStream(stream_id); | |
| 497 if (stream_info == nullptr) { | |
| 498 SPDY_BUG << "Stream " << stream_id << " not registered"; | |
| 499 return false; | |
| 500 } | |
| 501 for (base::LinkNode<StreamInfo>* s = scheduling_queue_.head(); | |
| 502 s != scheduling_queue_.end(); s = s->next()) { | |
| 503 if (stream_info == s->value()) { | |
| 504 return false; | |
| 505 } | |
| 506 if (!HasReadyAncestor(*s->value())) { | |
| 507 return true; | |
| 508 } | |
| 509 } | |
| 510 return false; | |
| 511 } | |
| 512 | |
| 513 template <typename StreamIdType> | |
| 514 void Http2PriorityWriteScheduler<StreamIdType>::MarkStreamReady( | |
| 515 StreamIdType stream_id, | |
| 516 bool add_to_front) { | |
| 517 if (stream_id == kHttp2RootStreamId) { | |
| 518 SPDY_BUG << "Cannot mark root stream ready"; | |
| 519 return; | |
| 520 } | |
| 521 StreamInfo* stream_info = FindStream(stream_id); | |
| 522 if (stream_info == nullptr) { | |
| 523 SPDY_BUG << "Stream " << stream_id << " not registered"; | |
| 524 return; | |
| 525 } | |
| 526 if (stream_info->ready) { | |
| 527 return; | |
| 528 } | |
| 529 stream_info->ordinal = add_to_front ? head_ordinal_-- : tail_ordinal_++; | |
| 530 Schedule(stream_info); | |
| 531 } | |
| 532 | |
| 533 template <typename StreamIdType> | |
| 534 void Http2PriorityWriteScheduler<StreamIdType>::MarkStreamNotReady( | |
| 535 StreamIdType stream_id) { | |
| 536 if (stream_id == kHttp2RootStreamId) { | |
| 537 SPDY_BUG << "Cannot mark root stream unready"; | |
| 538 return; | |
| 539 } | |
| 540 StreamInfo* stream_info = FindStream(stream_id); | |
| 541 if (stream_info == nullptr) { | |
| 542 SPDY_BUG << "Stream " << stream_id << " not registered"; | |
| 543 return; | |
| 544 } | |
| 545 if (!stream_info->ready) { | |
| 546 return; | |
| 547 } | |
| 548 Unschedule(stream_info); | |
| 549 } | |
| 550 | |
| 551 template <typename StreamIdType> | |
| 552 bool Http2PriorityWriteScheduler<StreamIdType>::Remove( | |
| 553 StreamInfoVector* stream_infos, | |
| 554 const StreamInfo* stream_info) { | |
| 555 for (typename StreamInfoVector::iterator it = stream_infos->begin(); | |
| 556 it != stream_infos->end(); ++it) { | |
| 557 if (*it == stream_info) { | |
| 558 stream_infos->erase(it); | |
| 559 return true; | |
| 560 } | |
| 561 } | |
| 562 return false; | |
| 563 } | |
| 564 | |
| 565 template <typename StreamIdType> | |
| 566 bool Http2PriorityWriteScheduler<StreamIdType>::HasReadyAncestor( | |
| 567 const StreamInfo& stream_info) { | |
| 568 for (const StreamInfo* parent = stream_info.parent; parent != nullptr; | |
| 569 parent = parent->parent) { | |
| 570 if (parent->ready) { | |
| 571 return true; | |
| 572 } | |
| 573 } | |
| 574 return false; | |
| 575 } | |
| 576 | |
| 577 template <typename StreamIdType> | |
| 578 const typename Http2PriorityWriteScheduler<StreamIdType>::StreamInfo* | |
| 579 Http2PriorityWriteScheduler<StreamIdType>::FindStream( | |
| 580 StreamIdType stream_id) const { | |
| 581 auto it = all_stream_infos_.find(stream_id); | |
| 582 return it == all_stream_infos_.end() ? nullptr : it->second.get(); | |
| 583 } | |
| 584 | |
| 585 template <typename StreamIdType> | |
| 586 typename Http2PriorityWriteScheduler<StreamIdType>::StreamInfo* | |
| 587 Http2PriorityWriteScheduler<StreamIdType>::FindStream(StreamIdType stream_id) { | |
| 588 auto it = all_stream_infos_.find(stream_id); | |
| 589 return it == all_stream_infos_.end() ? nullptr : it->second.get(); | |
| 590 } | |
| 591 | |
| 592 template <typename StreamIdType> | |
| 593 void Http2PriorityWriteScheduler<StreamIdType>::UpdatePrioritiesUnder( | |
| 594 StreamInfo* stream_info) { | |
| 595 for (StreamInfo* child : stream_info->children) { | |
| 596 child->priority = stream_info->priority * | |
| 597 (static_cast<float>(child->weight) / | |
| 598 static_cast<float>(stream_info->total_child_weights)); | |
| 599 if (child->ready) { | |
| 600 // Reposition in scheduling_queue_. Use post-order for scheduling, to | |
| 601 // benefit from the fact that children have priority <= parent priority. | |
| 602 Unschedule(child); | |
| 603 UpdatePrioritiesUnder(child); | |
| 604 Schedule(child); | |
| 605 } else { | |
| 606 UpdatePrioritiesUnder(child); | |
| 607 } | |
| 608 } | |
| 609 } | |
| 610 | |
| 611 template <typename StreamIdType> | |
| 612 void Http2PriorityWriteScheduler<StreamIdType>::Schedule( | |
| 613 StreamInfo* stream_info) { | |
| 614 DCHECK(!stream_info->ready); | |
| 615 for (base::LinkNode<StreamInfo>* s = scheduling_queue_.head(); | |
| 616 s != scheduling_queue_.end(); s = s->next()) { | |
| 617 if (stream_info->SchedulesBefore(*s->value())) { | |
| 618 stream_info->InsertBefore(s); | |
| 619 stream_info->ready = true; | |
| 620 return; | |
| 621 } | |
| 622 } | |
| 623 stream_info->InsertAfter(scheduling_queue_.tail()); | |
| 624 stream_info->ready = true; | |
| 625 } | |
| 626 | |
| 627 template <typename StreamIdType> | |
| 628 void Http2PriorityWriteScheduler<StreamIdType>::Unschedule( | |
| 629 StreamInfo* stream_info) { | |
| 630 DCHECK(stream_info->ready); | |
| 631 stream_info->RemoveFromList(); | |
| 632 stream_info->ready = false; | |
| 633 } | |
| 634 | |
| 635 template <typename StreamIdType> | |
| 636 bool Http2PriorityWriteScheduler<StreamIdType>::StreamHasChild( | |
| 637 const StreamInfo& parent_info, | |
| 638 const StreamInfo* child_info) const { | |
| 639 auto found = std::find(parent_info.children.begin(), | |
| 640 parent_info.children.end(), child_info); | |
| 641 return found != parent_info.children.end(); | |
| 642 } | |
| 643 | |
| 644 template <typename StreamIdType> | |
| 645 bool Http2PriorityWriteScheduler<StreamIdType>::HasReadyStreams() const { | |
| 646 return !scheduling_queue_.empty(); | |
| 647 } | |
| 648 | |
| 649 template <typename StreamIdType> | |
| 650 StreamIdType Http2PriorityWriteScheduler<StreamIdType>::PopNextReadyStream() { | |
| 651 return std::get<0>(PopNextReadyStreamAndPrecedence()); | |
| 652 } | |
| 653 | |
| 654 template <typename StreamIdType> | |
| 655 std::tuple< | |
| 656 StreamIdType, | |
| 657 typename Http2PriorityWriteScheduler<StreamIdType>::StreamPrecedenceType> | |
| 658 Http2PriorityWriteScheduler<StreamIdType>::PopNextReadyStreamAndPrecedence() { | |
| 659 for (base::LinkNode<StreamInfo>* s = scheduling_queue_.head(); | |
| 660 s != scheduling_queue_.end(); s = s->next()) { | |
| 661 StreamInfo* stream_info = s->value(); | |
| 662 if (!HasReadyAncestor(*stream_info)) { | |
| 663 Unschedule(stream_info); | |
| 664 return std::make_tuple(stream_info->id, | |
| 665 stream_info->ToStreamPrecedence()); | |
| 666 } | |
| 667 } | |
| 668 SPDY_BUG << "No ready streams"; | |
| 669 return std::make_tuple( | |
| 670 kHttp2RootStreamId, | |
| 671 StreamPrecedenceType(kHttp2RootStreamId, kHttp2MinStreamWeight, false)); | |
| 672 } | |
| 673 | |
| 674 template <typename StreamIdType> | |
| 675 size_t Http2PriorityWriteScheduler<StreamIdType>::NumReadyStreams() const { | |
| 676 base::LinkNode<StreamInfo>* node = scheduling_queue_.head(); | |
| 677 size_t size = 0; | |
| 678 while (node != scheduling_queue_.end()) | |
| 679 ++size; | |
| 680 return size; | |
| 681 } | |
| 682 | |
| 683 template <typename StreamIdType> | |
| 684 bool Http2PriorityWriteScheduler<StreamIdType>::ValidateInvariantsForTests() | |
| 685 const { | |
| 686 int total_streams = 0; | |
| 687 int streams_visited = 0; | |
| 688 // Iterate through all streams in the map. | |
| 689 for (const auto& kv : all_stream_infos_) { | |
| 690 ++total_streams; | |
| 691 ++streams_visited; | |
| 692 StreamIdType stream_id = kv.first; | |
| 693 const StreamInfo& stream_info = *kv.second.get(); | |
| 694 | |
| 695 // Verify each StreamInfo mapped under the proper stream ID. | |
| 696 if (stream_id != stream_info.id) { | |
| 697 DLOG(INFO) << "Stream ID " << stream_id << " maps to StreamInfo with ID " | |
| 698 << stream_info.id; | |
| 699 return false; | |
| 700 } | |
| 701 | |
| 702 // All streams except the root should have a parent, and should appear in | |
| 703 // the children of that parent. | |
| 704 if (stream_info.id != kHttp2RootStreamId && | |
| 705 !StreamHasChild(*stream_info.parent, &stream_info)) { | |
| 706 DLOG(INFO) << "Parent stream " << stream_info.parent->id | |
| 707 << " is not registered, or does not list stream " | |
| 708 << stream_info.id << " as its child."; | |
| 709 return false; | |
| 710 } | |
| 711 | |
| 712 if (!stream_info.children.empty()) { | |
| 713 int total_child_weights = 0; | |
| 714 // Iterate through the stream's children. | |
| 715 for (StreamInfo* child : stream_info.children) { | |
| 716 ++streams_visited; | |
| 717 // Each stream in the list should exist and should have this stream | |
| 718 // set as its parent. | |
| 719 if (!StreamRegistered(child->id) || child->parent != &stream_info) { | |
| 720 DLOG(INFO) << "Child stream " << child->id << " is not registered, " | |
| 721 << "or does not list " << stream_info.id | |
| 722 << " as its parent."; | |
| 723 return false; | |
| 724 } | |
| 725 total_child_weights += child->weight; | |
| 726 } | |
| 727 // Verify that total_child_weights is correct. | |
| 728 if (total_child_weights != stream_info.total_child_weights) { | |
| 729 DLOG(INFO) << "Child weight totals do not agree. For stream " | |
| 730 << stream_info.id << " total_child_weights has value " | |
| 731 << stream_info.total_child_weights << ", expected " | |
| 732 << total_child_weights; | |
| 733 return false; | |
| 734 } | |
| 735 } | |
| 736 } | |
| 737 | |
| 738 // Make sure num_streams reflects the total number of streams the map | |
| 739 // contains. | |
| 740 if (total_streams != num_streams()) { | |
| 741 DLOG(INFO) << "Map contains incorrect number of streams."; | |
| 742 return false; | |
| 743 } | |
| 744 // Validate the validation function; we should have visited each stream twice | |
| 745 // (except for the root) | |
| 746 DCHECK(streams_visited == 2 * num_streams() - 1); | |
| 747 return true; | |
| 748 } | |
| 749 | |
| 750 } // namespace net | |
| 751 | |
| 752 #endif // NET_SPDY_HTTP2_WRITE_SCHEDULER_H_ | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2791883003:
Remove Http2PriorityWriteScheduler. (Closed)
