1 // Copyright (c) 2019 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 #include "quiche/quic/core/qpack/qpack_blocking_manager.h"
6
7 #include <limits>
8 #include <utility>
9
10 namespace quic {
11
QpackBlockingManager()12 QpackBlockingManager::QpackBlockingManager() : known_received_count_(0) {}
13
OnHeaderAcknowledgement(QuicStreamId stream_id)14 bool QpackBlockingManager::OnHeaderAcknowledgement(QuicStreamId stream_id) {
15 auto it = header_blocks_.find(stream_id);
16 if (it == header_blocks_.end()) {
17 return false;
18 }
19
20 QUICHE_DCHECK(!it->second.empty());
21
22 const IndexSet& indices = it->second.front();
23 QUICHE_DCHECK(!indices.empty());
24
25 const uint64_t required_index_count = RequiredInsertCount(indices);
26 if (known_received_count_ < required_index_count) {
27 known_received_count_ = required_index_count;
28 }
29
30 DecreaseReferenceCounts(indices);
31
32 it->second.pop_front();
33 if (it->second.empty()) {
34 header_blocks_.erase(it);
35 }
36
37 return true;
38 }
39
OnStreamCancellation(QuicStreamId stream_id)40 void QpackBlockingManager::OnStreamCancellation(QuicStreamId stream_id) {
41 auto it = header_blocks_.find(stream_id);
42 if (it == header_blocks_.end()) {
43 return;
44 }
45
46 for (const IndexSet& indices : it->second) {
47 DecreaseReferenceCounts(indices);
48 }
49
50 header_blocks_.erase(it);
51 }
52
OnInsertCountIncrement(uint64_t increment)53 bool QpackBlockingManager::OnInsertCountIncrement(uint64_t increment) {
54 if (increment >
55 std::numeric_limits<uint64_t>::max() - known_received_count_) {
56 return false;
57 }
58
59 known_received_count_ += increment;
60 return true;
61 }
62
OnHeaderBlockSent(QuicStreamId stream_id,IndexSet indices)63 void QpackBlockingManager::OnHeaderBlockSent(QuicStreamId stream_id,
64 IndexSet indices) {
65 QUICHE_DCHECK(!indices.empty());
66
67 IncreaseReferenceCounts(indices);
68 header_blocks_[stream_id].push_back(std::move(indices));
69 }
70
blocking_allowed_on_stream(QuicStreamId stream_id,uint64_t maximum_blocked_streams) const71 bool QpackBlockingManager::blocking_allowed_on_stream(
72 QuicStreamId stream_id, uint64_t maximum_blocked_streams) const {
73 // This should be the most common case: the limit is larger than the number of
74 // streams that have unacknowledged header blocks (regardless of whether they
75 // are blocked or not) plus one for stream |stream_id|.
76 if (header_blocks_.size() + 1 <= maximum_blocked_streams) {
77 return true;
78 }
79
80 // This should be another common case: no blocked stream allowed.
81 if (maximum_blocked_streams == 0) {
82 return false;
83 }
84
85 uint64_t blocked_stream_count = 0;
86 for (const auto& header_blocks_for_stream : header_blocks_) {
87 for (const IndexSet& indices : header_blocks_for_stream.second) {
88 if (RequiredInsertCount(indices) > known_received_count_) {
89 if (header_blocks_for_stream.first == stream_id) {
90 // Sending blocking references is allowed if stream |stream_id| is
91 // already blocked.
92 return true;
93 }
94 ++blocked_stream_count;
95 // If stream |stream_id| is already blocked, then it is not counted yet,
96 // therefore the number of blocked streams is at least
97 // |blocked_stream_count + 1|, which cannot be more than
98 // |maximum_blocked_streams| by API contract.
99 // If stream |stream_id| is not blocked, then blocking will increase the
100 // blocked stream count to at least |blocked_stream_count + 1|. If that
101 // is larger than |maximum_blocked_streams|, then blocking is not
102 // allowed on stream |stream_id|.
103 if (blocked_stream_count + 1 > maximum_blocked_streams) {
104 return false;
105 }
106 break;
107 }
108 }
109 }
110
111 // Stream |stream_id| is not blocked.
112 // If there are no blocked streams, then
113 // |blocked_stream_count + 1 <= maximum_blocked_streams| because
114 // |maximum_blocked_streams| is larger than zero.
115 // If there are are blocked streams, then
116 // |blocked_stream_count + 1 <= maximum_blocked_streams| otherwise the method
117 // would have returned false when |blocked_stream_count| was incremented.
118 // Therefore blocking on |stream_id| is allowed.
119 return true;
120 }
121
smallest_blocking_index() const122 uint64_t QpackBlockingManager::smallest_blocking_index() const {
123 return entry_reference_counts_.empty()
124 ? std::numeric_limits<uint64_t>::max()
125 : entry_reference_counts_.begin()->first;
126 }
127
128 // static
RequiredInsertCount(const IndexSet & indices)129 uint64_t QpackBlockingManager::RequiredInsertCount(const IndexSet& indices) {
130 return *indices.rbegin() + 1;
131 }
132
IncreaseReferenceCounts(const IndexSet & indices)133 void QpackBlockingManager::IncreaseReferenceCounts(const IndexSet& indices) {
134 for (const uint64_t index : indices) {
135 auto it = entry_reference_counts_.lower_bound(index);
136 if (it != entry_reference_counts_.end() && it->first == index) {
137 ++it->second;
138 } else {
139 entry_reference_counts_.insert(it, {index, 1});
140 }
141 }
142 }
143
DecreaseReferenceCounts(const IndexSet & indices)144 void QpackBlockingManager::DecreaseReferenceCounts(const IndexSet& indices) {
145 for (const uint64_t index : indices) {
146 auto it = entry_reference_counts_.find(index);
147 QUICHE_DCHECK(it != entry_reference_counts_.end());
148 QUICHE_DCHECK_NE(0u, it->second);
149
150 if (it->second == 1) {
151 entry_reference_counts_.erase(it);
152 } else {
153 --it->second;
154 }
155 }
156 }
157
158 } // namespace quic
159