http2_priority_dependencies.cc 5.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177
  1. // Copyright 2016 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. #include "net/spdy/http2_priority_dependencies.h"
  5. #include "base/trace_event/memory_usage_estimator.h"
  6. namespace net {
  7. Http2PriorityDependencies::Http2PriorityDependencies() = default;
  8. Http2PriorityDependencies::~Http2PriorityDependencies() = default;
  9. void Http2PriorityDependencies::OnStreamCreation(
  10. spdy::SpdyStreamId id,
  11. spdy::SpdyPriority priority,
  12. spdy::SpdyStreamId* parent_stream_id,
  13. int* weight,
  14. bool* exclusive) {
  15. if (entry_by_stream_id_.find(id) != entry_by_stream_id_.end())
  16. return;
  17. *parent_stream_id = 0;
  18. *exclusive = true;
  19. // Since the generated dependency graph is a single linked list, the value
  20. // of weight should not actually matter, and perhaps the default weight of 16
  21. // from the HTTP/2 spec would be reasonable. However, there are some servers
  22. // which currently interpret the weight field like an old SPDY priority value.
  23. // As long as those servers need to be supported, weight should be set to
  24. // a value those servers will interpret correctly.
  25. *weight = spdy::Spdy3PriorityToHttp2Weight(priority);
  26. // Dependent on the lowest-priority stream that has a priority >= |priority|.
  27. IdList::iterator parent;
  28. if (PriorityLowerBound(priority, &parent)) {
  29. *parent_stream_id = parent->first;
  30. }
  31. id_priority_lists_[priority].push_back(std::make_pair(id, priority));
  32. auto it = id_priority_lists_[priority].end();
  33. --it;
  34. entry_by_stream_id_[id] = it;
  35. }
  36. bool Http2PriorityDependencies::PriorityLowerBound(spdy::SpdyPriority priority,
  37. IdList::iterator* bound) {
  38. for (int i = priority; i >= spdy::kV3HighestPriority; --i) {
  39. if (!id_priority_lists_[i].empty()) {
  40. *bound = id_priority_lists_[i].end();
  41. --(*bound);
  42. return true;
  43. }
  44. }
  45. return false;
  46. }
  47. bool Http2PriorityDependencies::ParentOfStream(spdy::SpdyStreamId id,
  48. IdList::iterator* parent) {
  49. auto entry = entry_by_stream_id_.find(id);
  50. DCHECK(entry != entry_by_stream_id_.end());
  51. spdy::SpdyPriority priority = entry->second->second;
  52. auto curr = entry->second;
  53. if (curr != id_priority_lists_[priority].begin()) {
  54. *parent = curr;
  55. --(*parent);
  56. return true;
  57. }
  58. // |id| is at the head of its priority list, so its parent is the last
  59. // entry of the next-highest priority band.
  60. if (priority == spdy::kV3HighestPriority) {
  61. return false;
  62. }
  63. return PriorityLowerBound(priority - 1, parent);
  64. }
  65. bool Http2PriorityDependencies::ChildOfStream(spdy::SpdyStreamId id,
  66. IdList::iterator* child) {
  67. auto entry = entry_by_stream_id_.find(id);
  68. DCHECK(entry != entry_by_stream_id_.end());
  69. spdy::SpdyPriority priority = entry->second->second;
  70. *child = entry->second;
  71. ++(*child);
  72. if (*child != id_priority_lists_[priority].end()) {
  73. return true;
  74. }
  75. // |id| is at the end of its priority list, so its child is the stream
  76. // at the front of the next-lowest priority band.
  77. for (int i = priority + 1; i <= spdy::kV3LowestPriority; ++i) {
  78. if (!id_priority_lists_[i].empty()) {
  79. *child = id_priority_lists_[i].begin();
  80. return true;
  81. }
  82. }
  83. return false;
  84. }
  85. std::vector<Http2PriorityDependencies::DependencyUpdate>
  86. Http2PriorityDependencies::OnStreamUpdate(spdy::SpdyStreamId id,
  87. spdy::SpdyPriority new_priority) {
  88. std::vector<DependencyUpdate> result;
  89. result.reserve(2);
  90. auto curr_entry = entry_by_stream_id_.find(id);
  91. if (curr_entry == entry_by_stream_id_.end()) {
  92. return result;
  93. }
  94. spdy::SpdyPriority old_priority = curr_entry->second->second;
  95. if (old_priority == new_priority) {
  96. return result;
  97. }
  98. IdList::iterator old_parent;
  99. bool old_has_parent = ParentOfStream(id, &old_parent);
  100. IdList::iterator new_parent;
  101. bool new_has_parent = PriorityLowerBound(new_priority, &new_parent);
  102. // If we move |id| from MEDIUM to LOW, where HIGH = {other_id}, MEDIUM = {id},
  103. // and LOW = {}, then PriorityLowerBound(new_priority) is |id|. In this corner
  104. // case, |id| does not change parents.
  105. if (new_has_parent && new_parent->first == id) {
  106. new_has_parent = old_has_parent;
  107. new_parent = old_parent;
  108. }
  109. // If the parent has changed, we generate dependency updates.
  110. if ((old_has_parent != new_has_parent) ||
  111. (old_has_parent && old_parent->first != new_parent->first)) {
  112. // If |id| has a child, then that child moves to be dependent on
  113. // |old_parent|.
  114. IdList::iterator old_child;
  115. if (ChildOfStream(id, &old_child)) {
  116. int weight = spdy::Spdy3PriorityToHttp2Weight(old_child->second);
  117. if (old_has_parent) {
  118. result.push_back({old_child->first, old_parent->first, weight, true});
  119. } else {
  120. result.push_back({old_child->first, 0, weight, true});
  121. }
  122. }
  123. int weight = spdy::Spdy3PriorityToHttp2Weight(new_priority);
  124. // |id| moves to be dependent on |new_parent|.
  125. if (new_has_parent) {
  126. result.push_back({id, new_parent->first, weight, true});
  127. } else {
  128. result.push_back({id, 0, weight, true});
  129. }
  130. }
  131. // Move to the new priority.
  132. auto old = entry_by_stream_id_.find(id);
  133. id_priority_lists_[old->second->second].erase(old->second);
  134. id_priority_lists_[new_priority].push_back(std::make_pair(id, new_priority));
  135. auto it = id_priority_lists_[new_priority].end();
  136. --it;
  137. entry_by_stream_id_[id] = it;
  138. return result;
  139. }
  140. void Http2PriorityDependencies::OnStreamDestruction(spdy::SpdyStreamId id) {
  141. auto emit = entry_by_stream_id_.find(id);
  142. if (emit == entry_by_stream_id_.end())
  143. return;
  144. auto it = emit->second;
  145. id_priority_lists_[it->second].erase(it);
  146. entry_by_stream_id_.erase(emit);
  147. }
  148. } // namespace net