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
9 #include "quiche/quic/platform/api/quic_test.h"
10
11 namespace quic {
12 namespace test {
13
14 class QpackBlockingManagerPeer {
15 public:
stream_is_blocked(const QpackBlockingManager * manager,QuicStreamId stream_id)16 static bool stream_is_blocked(const QpackBlockingManager* manager,
17 QuicStreamId stream_id) {
18 for (const auto& header_blocks_for_stream : manager->header_blocks_) {
19 if (header_blocks_for_stream.first != stream_id) {
20 continue;
21 }
22 for (const auto& indices : header_blocks_for_stream.second) {
23 if (QpackBlockingManager::RequiredInsertCount(indices) >
24 manager->known_received_count_) {
25 return true;
26 }
27 }
28 }
29
30 return false;
31 }
32 };
33
34 namespace {
35
36 class QpackBlockingManagerTest : public QuicTest {
37 protected:
38 QpackBlockingManagerTest() = default;
39 ~QpackBlockingManagerTest() override = default;
40
stream_is_blocked(QuicStreamId stream_id) const41 bool stream_is_blocked(QuicStreamId stream_id) const {
42 return QpackBlockingManagerPeer::stream_is_blocked(&manager_, stream_id);
43 }
44
45 QpackBlockingManager manager_;
46 };
47
TEST_F(QpackBlockingManagerTest,Empty)48 TEST_F(QpackBlockingManagerTest, Empty) {
49 EXPECT_EQ(0u, manager_.known_received_count());
50 EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
51 manager_.smallest_blocking_index());
52
53 EXPECT_FALSE(manager_.OnHeaderAcknowledgement(0));
54 EXPECT_FALSE(manager_.OnHeaderAcknowledgement(1));
55 }
56
TEST_F(QpackBlockingManagerTest,NotBlockedByInsertCountIncrement)57 TEST_F(QpackBlockingManagerTest, NotBlockedByInsertCountIncrement) {
58 EXPECT_TRUE(manager_.OnInsertCountIncrement(2));
59
60 // Stream 0 is not blocked, because it only references entries that are
61 // already acknowledged by an Insert Count Increment instruction.
62 manager_.OnHeaderBlockSent(0, {1, 0});
63 EXPECT_FALSE(stream_is_blocked(0));
64 }
65
TEST_F(QpackBlockingManagerTest,UnblockedByInsertCountIncrement)66 TEST_F(QpackBlockingManagerTest, UnblockedByInsertCountIncrement) {
67 manager_.OnHeaderBlockSent(0, {1, 0});
68 EXPECT_TRUE(stream_is_blocked(0));
69
70 EXPECT_TRUE(manager_.OnInsertCountIncrement(2));
71 EXPECT_FALSE(stream_is_blocked(0));
72 }
73
TEST_F(QpackBlockingManagerTest,NotBlockedByHeaderAcknowledgement)74 TEST_F(QpackBlockingManagerTest, NotBlockedByHeaderAcknowledgement) {
75 manager_.OnHeaderBlockSent(0, {2, 1, 1});
76 EXPECT_TRUE(stream_is_blocked(0));
77
78 EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0));
79 EXPECT_FALSE(stream_is_blocked(0));
80
81 // Stream 1 is not blocked, because it only references entries that are
82 // already acknowledged by a Header Acknowledgement instruction.
83 manager_.OnHeaderBlockSent(1, {2, 2});
84 EXPECT_FALSE(stream_is_blocked(1));
85 }
86
TEST_F(QpackBlockingManagerTest,UnblockedByHeaderAcknowledgement)87 TEST_F(QpackBlockingManagerTest, UnblockedByHeaderAcknowledgement) {
88 manager_.OnHeaderBlockSent(0, {2, 1, 1});
89 manager_.OnHeaderBlockSent(1, {2, 2});
90 EXPECT_TRUE(stream_is_blocked(0));
91 EXPECT_TRUE(stream_is_blocked(1));
92
93 EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0));
94 EXPECT_FALSE(stream_is_blocked(0));
95 EXPECT_FALSE(stream_is_blocked(1));
96 }
97
TEST_F(QpackBlockingManagerTest,KnownReceivedCount)98 TEST_F(QpackBlockingManagerTest, KnownReceivedCount) {
99 EXPECT_EQ(0u, manager_.known_received_count());
100
101 // Sending a header block does not change Known Received Count.
102 manager_.OnHeaderBlockSent(0, {0});
103 EXPECT_EQ(0u, manager_.known_received_count());
104
105 manager_.OnHeaderBlockSent(1, {1});
106 EXPECT_EQ(0u, manager_.known_received_count());
107
108 // Header Acknowledgement might increase Known Received Count.
109 EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0));
110 EXPECT_EQ(1u, manager_.known_received_count());
111
112 manager_.OnHeaderBlockSent(2, {5});
113 EXPECT_EQ(1u, manager_.known_received_count());
114
115 EXPECT_TRUE(manager_.OnHeaderAcknowledgement(1));
116 EXPECT_EQ(2u, manager_.known_received_count());
117
118 // Insert Count Increment increases Known Received Count.
119 EXPECT_TRUE(manager_.OnInsertCountIncrement(2));
120 EXPECT_EQ(4u, manager_.known_received_count());
121
122 EXPECT_TRUE(manager_.OnHeaderAcknowledgement(2));
123 EXPECT_EQ(6u, manager_.known_received_count());
124
125 // Stream Cancellation does not change Known Received Count.
126 manager_.OnStreamCancellation(0);
127 EXPECT_EQ(6u, manager_.known_received_count());
128
129 // Header Acknowledgement of a block with smaller Required Insert Count does
130 // not increase Known Received Count.
131 manager_.OnHeaderBlockSent(0, {3});
132 EXPECT_EQ(6u, manager_.known_received_count());
133
134 EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0));
135 EXPECT_EQ(6u, manager_.known_received_count());
136
137 // Header Acknowledgement of a block with equal Required Insert Count does not
138 // increase Known Received Count.
139 manager_.OnHeaderBlockSent(1, {5});
140 EXPECT_EQ(6u, manager_.known_received_count());
141
142 EXPECT_TRUE(manager_.OnHeaderAcknowledgement(1));
143 EXPECT_EQ(6u, manager_.known_received_count());
144 }
145
TEST_F(QpackBlockingManagerTest,SmallestBlockingIndex)146 TEST_F(QpackBlockingManagerTest, SmallestBlockingIndex) {
147 EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
148 manager_.smallest_blocking_index());
149
150 manager_.OnHeaderBlockSent(0, {0});
151 EXPECT_EQ(0u, manager_.smallest_blocking_index());
152
153 manager_.OnHeaderBlockSent(1, {2});
154 EXPECT_EQ(0u, manager_.smallest_blocking_index());
155
156 EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0));
157 EXPECT_EQ(2u, manager_.smallest_blocking_index());
158
159 manager_.OnHeaderBlockSent(1, {1});
160 EXPECT_EQ(1u, manager_.smallest_blocking_index());
161
162 EXPECT_TRUE(manager_.OnHeaderAcknowledgement(1));
163 EXPECT_EQ(1u, manager_.smallest_blocking_index());
164
165 // Insert Count Increment does not change smallest blocking index.
166 EXPECT_TRUE(manager_.OnInsertCountIncrement(2));
167 EXPECT_EQ(1u, manager_.smallest_blocking_index());
168
169 manager_.OnStreamCancellation(1);
170 EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
171 manager_.smallest_blocking_index());
172 }
173
TEST_F(QpackBlockingManagerTest,HeaderAcknowledgementsOnSingleStream)174 TEST_F(QpackBlockingManagerTest, HeaderAcknowledgementsOnSingleStream) {
175 EXPECT_EQ(0u, manager_.known_received_count());
176 EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
177 manager_.smallest_blocking_index());
178
179 manager_.OnHeaderBlockSent(0, {2, 1, 1});
180 EXPECT_EQ(0u, manager_.known_received_count());
181 EXPECT_TRUE(stream_is_blocked(0));
182 EXPECT_EQ(1u, manager_.smallest_blocking_index());
183
184 manager_.OnHeaderBlockSent(0, {1, 0});
185 EXPECT_EQ(0u, manager_.known_received_count());
186 EXPECT_TRUE(stream_is_blocked(0));
187 EXPECT_EQ(0u, manager_.smallest_blocking_index());
188
189 EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0));
190 EXPECT_EQ(3u, manager_.known_received_count());
191 EXPECT_FALSE(stream_is_blocked(0));
192 EXPECT_EQ(0u, manager_.smallest_blocking_index());
193
194 manager_.OnHeaderBlockSent(0, {3});
195 EXPECT_EQ(3u, manager_.known_received_count());
196 EXPECT_TRUE(stream_is_blocked(0));
197 EXPECT_EQ(0u, manager_.smallest_blocking_index());
198
199 EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0));
200 EXPECT_EQ(3u, manager_.known_received_count());
201 EXPECT_TRUE(stream_is_blocked(0));
202 EXPECT_EQ(3u, manager_.smallest_blocking_index());
203
204 EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0));
205 EXPECT_EQ(4u, manager_.known_received_count());
206 EXPECT_FALSE(stream_is_blocked(0));
207 EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
208 manager_.smallest_blocking_index());
209
210 EXPECT_FALSE(manager_.OnHeaderAcknowledgement(0));
211 }
212
TEST_F(QpackBlockingManagerTest,CancelStream)213 TEST_F(QpackBlockingManagerTest, CancelStream) {
214 manager_.OnHeaderBlockSent(0, {3});
215 EXPECT_TRUE(stream_is_blocked(0));
216 EXPECT_EQ(3u, manager_.smallest_blocking_index());
217
218 manager_.OnHeaderBlockSent(0, {2});
219 EXPECT_TRUE(stream_is_blocked(0));
220 EXPECT_EQ(2u, manager_.smallest_blocking_index());
221
222 manager_.OnHeaderBlockSent(1, {4});
223 EXPECT_TRUE(stream_is_blocked(0));
224 EXPECT_TRUE(stream_is_blocked(1));
225 EXPECT_EQ(2u, manager_.smallest_blocking_index());
226
227 manager_.OnStreamCancellation(0);
228 EXPECT_FALSE(stream_is_blocked(0));
229 EXPECT_TRUE(stream_is_blocked(1));
230 EXPECT_EQ(4u, manager_.smallest_blocking_index());
231
232 manager_.OnStreamCancellation(1);
233 EXPECT_FALSE(stream_is_blocked(0));
234 EXPECT_FALSE(stream_is_blocked(1));
235 EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
236 manager_.smallest_blocking_index());
237 }
238
TEST_F(QpackBlockingManagerTest,BlockingAllowedOnStream)239 TEST_F(QpackBlockingManagerTest, BlockingAllowedOnStream) {
240 const QuicStreamId kStreamId1 = 1;
241 const QuicStreamId kStreamId2 = 2;
242 const QuicStreamId kStreamId3 = 3;
243
244 // No stream can block if limit is 0.
245 EXPECT_FALSE(manager_.blocking_allowed_on_stream(kStreamId1, 0));
246 EXPECT_FALSE(manager_.blocking_allowed_on_stream(kStreamId2, 0));
247
248 // Either stream can block if limit is larger.
249 EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId1, 1));
250 EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId2, 1));
251
252 // Doubly block first stream.
253 manager_.OnHeaderBlockSent(kStreamId1, {0});
254 manager_.OnHeaderBlockSent(kStreamId1, {1});
255
256 // First stream is already blocked so it can carry more blocking references.
257 EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId1, 1));
258 // Second stream is not allowed to block if limit is already reached.
259 EXPECT_FALSE(manager_.blocking_allowed_on_stream(kStreamId2, 1));
260
261 // Either stream can block if limit is larger than number of blocked streams.
262 EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId1, 2));
263 EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId2, 2));
264
265 // Block second stream.
266 manager_.OnHeaderBlockSent(kStreamId2, {2});
267
268 // Streams are already blocked so either can carry more blocking references.
269 EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId1, 2));
270 EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId2, 2));
271
272 // Third, unblocked stream is not allowed to block unless limit is strictly
273 // larger than number of blocked streams.
274 EXPECT_FALSE(manager_.blocking_allowed_on_stream(kStreamId3, 2));
275 EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId3, 3));
276
277 // Acknowledge decoding of first header block on first stream.
278 // Stream is still blocked on its second header block.
279 manager_.OnHeaderAcknowledgement(kStreamId1);
280
281 EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId1, 2));
282 EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId2, 2));
283
284 // Acknowledge decoding of second header block on first stream.
285 // This unblocks the stream.
286 manager_.OnHeaderAcknowledgement(kStreamId1);
287
288 // First stream is not allowed to block if limit is already reached.
289 EXPECT_FALSE(manager_.blocking_allowed_on_stream(kStreamId1, 1));
290 // Second stream is already blocked so it can carry more blocking references.
291 EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId2, 1));
292
293 // Either stream can block if limit is larger than number of blocked streams.
294 EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId1, 2));
295 EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId2, 2));
296
297 // Unblock second stream.
298 manager_.OnHeaderAcknowledgement(kStreamId2);
299
300 // No stream can block if limit is 0.
301 EXPECT_FALSE(manager_.blocking_allowed_on_stream(kStreamId1, 0));
302 EXPECT_FALSE(manager_.blocking_allowed_on_stream(kStreamId2, 0));
303
304 // Either stream can block if limit is larger.
305 EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId1, 1));
306 EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId2, 1));
307 }
308
TEST_F(QpackBlockingManagerTest,InsertCountIncrementOverflow)309 TEST_F(QpackBlockingManagerTest, InsertCountIncrementOverflow) {
310 EXPECT_TRUE(manager_.OnInsertCountIncrement(10));
311 EXPECT_EQ(10u, manager_.known_received_count());
312
313 EXPECT_FALSE(manager_.OnInsertCountIncrement(
314 std::numeric_limits<uint64_t>::max() - 5));
315 }
316
317 } // namespace
318 } // namespace test
319 } // namespace quic
320