1 // Copyright (c) 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 #include "quiche/http2/core/priority_write_scheduler.h"
6
7 #include "quiche/common/platform/api/quiche_expect_bug.h"
8 #include "quiche/common/platform/api/quiche_test.h"
9 #include "quiche/spdy/core/spdy_protocol.h"
10 #include "quiche/spdy/test_tools/spdy_test_utils.h"
11
12 namespace http2 {
13 namespace test {
14
15 using ::spdy::kHttp2RootStreamId;
16 using ::spdy::SpdyPriority;
17 using ::spdy::SpdyStreamId;
18 using ::testing::Eq;
19 using ::testing::Optional;
20
21 template <typename StreamIdType>
22 class PriorityWriteSchedulerPeer {
23 public:
PriorityWriteSchedulerPeer(PriorityWriteScheduler<StreamIdType> * scheduler)24 explicit PriorityWriteSchedulerPeer(
25 PriorityWriteScheduler<StreamIdType>* scheduler)
26 : scheduler_(scheduler) {}
27
NumReadyStreams(SpdyPriority priority) const28 size_t NumReadyStreams(SpdyPriority priority) const {
29 return scheduler_->priority_infos_[priority].ready_list.size();
30 }
31
32 private:
33 PriorityWriteScheduler<StreamIdType>* scheduler_;
34 };
35
36 namespace {
37
38 class PriorityWriteSchedulerTest : public quiche::test::QuicheTest {
39 public:
40 static constexpr int kLowestPriority =
41 PriorityWriteScheduler<SpdyStreamId>::kLowestPriority;
42
PriorityWriteSchedulerTest()43 PriorityWriteSchedulerTest() : peer_(&scheduler_) {}
44
45 PriorityWriteScheduler<SpdyStreamId> scheduler_;
46 PriorityWriteSchedulerPeer<SpdyStreamId> peer_;
47 };
48
TEST_F(PriorityWriteSchedulerTest,RegisterUnregisterStreams)49 TEST_F(PriorityWriteSchedulerTest, RegisterUnregisterStreams) {
50 EXPECT_FALSE(scheduler_.HasReadyStreams());
51 EXPECT_FALSE(scheduler_.StreamRegistered(1));
52 EXPECT_EQ(0u, scheduler_.NumRegisteredStreams());
53 scheduler_.RegisterStream(1, 1);
54 EXPECT_TRUE(scheduler_.StreamRegistered(1));
55 EXPECT_EQ(1u, scheduler_.NumRegisteredStreams());
56
57 // Try redundant registrations.
58 EXPECT_QUICHE_BUG(scheduler_.RegisterStream(1, 1),
59 "Stream 1 already registered");
60 EXPECT_EQ(1u, scheduler_.NumRegisteredStreams());
61
62 EXPECT_QUICHE_BUG(scheduler_.RegisterStream(1, 2),
63 "Stream 1 already registered");
64 EXPECT_EQ(1u, scheduler_.NumRegisteredStreams());
65
66 scheduler_.RegisterStream(2, 3);
67 EXPECT_EQ(2u, scheduler_.NumRegisteredStreams());
68
69 // Verify registration != ready.
70 EXPECT_FALSE(scheduler_.HasReadyStreams());
71
72 scheduler_.UnregisterStream(1);
73 EXPECT_EQ(1u, scheduler_.NumRegisteredStreams());
74 scheduler_.UnregisterStream(2);
75 EXPECT_EQ(0u, scheduler_.NumRegisteredStreams());
76
77 // Try redundant unregistration.
78 EXPECT_QUICHE_BUG(scheduler_.UnregisterStream(1), "Stream 1 not registered");
79 EXPECT_QUICHE_BUG(scheduler_.UnregisterStream(2), "Stream 2 not registered");
80 EXPECT_EQ(0u, scheduler_.NumRegisteredStreams());
81 }
82
TEST_F(PriorityWriteSchedulerTest,GetStreamPriority)83 TEST_F(PriorityWriteSchedulerTest, GetStreamPriority) {
84 // Unknown streams tolerated due to b/15676312. However, return lowest
85 // priority.
86 EXPECT_EQ(kLowestPriority, scheduler_.GetStreamPriority(1));
87
88 scheduler_.RegisterStream(1, 3);
89 EXPECT_EQ(3, scheduler_.GetStreamPriority(1));
90
91 // Redundant registration shouldn't change stream priority.
92 EXPECT_QUICHE_BUG(scheduler_.RegisterStream(1, 4),
93 "Stream 1 already registered");
94 EXPECT_EQ(3, scheduler_.GetStreamPriority(1));
95
96 scheduler_.UpdateStreamPriority(1, 5);
97 EXPECT_EQ(5, scheduler_.GetStreamPriority(1));
98
99 // Toggling ready state shouldn't change stream priority.
100 scheduler_.MarkStreamReady(1, true);
101 EXPECT_EQ(5, scheduler_.GetStreamPriority(1));
102
103 // Test changing priority of ready stream.
104 EXPECT_EQ(1u, peer_.NumReadyStreams(5));
105 scheduler_.UpdateStreamPriority(1, 6);
106 EXPECT_EQ(6, scheduler_.GetStreamPriority(1));
107 EXPECT_EQ(0u, peer_.NumReadyStreams(5));
108 EXPECT_EQ(1u, peer_.NumReadyStreams(6));
109
110 EXPECT_EQ(1u, scheduler_.PopNextReadyStream());
111 EXPECT_EQ(6, scheduler_.GetStreamPriority(1));
112
113 scheduler_.UnregisterStream(1);
114 EXPECT_EQ(kLowestPriority, scheduler_.GetStreamPriority(1));
115 }
116
TEST_F(PriorityWriteSchedulerTest,PopNextReadyStreamAndPriority)117 TEST_F(PriorityWriteSchedulerTest, PopNextReadyStreamAndPriority) {
118 scheduler_.RegisterStream(1, 3);
119 scheduler_.MarkStreamReady(1, true);
120 EXPECT_EQ(std::make_tuple(1u, 3), scheduler_.PopNextReadyStreamAndPriority());
121 scheduler_.UnregisterStream(1);
122 }
123
TEST_F(PriorityWriteSchedulerTest,UpdateStreamPriority)124 TEST_F(PriorityWriteSchedulerTest, UpdateStreamPriority) {
125 // For the moment, updating stream priority on a non-registered stream should
126 // have no effect. In the future, it will lazily cause the stream to be
127 // registered (b/15676312).
128 EXPECT_EQ(kLowestPriority, scheduler_.GetStreamPriority(3));
129 EXPECT_FALSE(scheduler_.StreamRegistered(3));
130 scheduler_.UpdateStreamPriority(3, 1);
131 EXPECT_FALSE(scheduler_.StreamRegistered(3));
132 EXPECT_EQ(kLowestPriority, scheduler_.GetStreamPriority(3));
133
134 scheduler_.RegisterStream(3, 1);
135 EXPECT_EQ(1, scheduler_.GetStreamPriority(3));
136 scheduler_.UpdateStreamPriority(3, 2);
137 EXPECT_EQ(2, scheduler_.GetStreamPriority(3));
138
139 // Updating priority of stream to current priority value is valid, but has no
140 // effect.
141 scheduler_.UpdateStreamPriority(3, 2);
142 EXPECT_EQ(2, scheduler_.GetStreamPriority(3));
143
144 // Even though stream 4 is marked ready after stream 5, it should be returned
145 // first by PopNextReadyStream() since it has higher priority.
146 scheduler_.RegisterStream(4, 1);
147 scheduler_.MarkStreamReady(3, false); // priority 2
148 EXPECT_TRUE(scheduler_.IsStreamReady(3));
149 scheduler_.MarkStreamReady(4, false); // priority 1
150 EXPECT_TRUE(scheduler_.IsStreamReady(4));
151 EXPECT_EQ(4u, scheduler_.PopNextReadyStream());
152 EXPECT_FALSE(scheduler_.IsStreamReady(4));
153 EXPECT_EQ(3u, scheduler_.PopNextReadyStream());
154 EXPECT_FALSE(scheduler_.IsStreamReady(3));
155
156 // Verify that lowering priority of stream 4 causes it to be returned later
157 // by PopNextReadyStream().
158 scheduler_.MarkStreamReady(3, false); // priority 2
159 scheduler_.MarkStreamReady(4, false); // priority 1
160 scheduler_.UpdateStreamPriority(4, 3);
161 EXPECT_EQ(3u, scheduler_.PopNextReadyStream());
162 EXPECT_EQ(4u, scheduler_.PopNextReadyStream());
163
164 scheduler_.UnregisterStream(3);
165 }
166
TEST_F(PriorityWriteSchedulerTest,MarkStreamReadyBack)167 TEST_F(PriorityWriteSchedulerTest, MarkStreamReadyBack) {
168 EXPECT_FALSE(scheduler_.HasReadyStreams());
169 EXPECT_QUICHE_BUG(scheduler_.MarkStreamReady(1, false),
170 "Stream 1 not registered");
171 EXPECT_FALSE(scheduler_.HasReadyStreams());
172 EXPECT_QUICHE_BUG(EXPECT_EQ(0u, scheduler_.PopNextReadyStream()),
173 "No ready streams available");
174
175 // Add a bunch of ready streams to tail of per-priority lists.
176 // Expected order: (P2) 4, (P3) 1, 2, 3, (P5) 5.
177 scheduler_.RegisterStream(1, 3);
178 scheduler_.MarkStreamReady(1, false);
179 EXPECT_TRUE(scheduler_.HasReadyStreams());
180 scheduler_.RegisterStream(2, 3);
181 scheduler_.MarkStreamReady(2, false);
182 scheduler_.RegisterStream(3, 3);
183 scheduler_.MarkStreamReady(3, false);
184 scheduler_.RegisterStream(4, 2);
185 scheduler_.MarkStreamReady(4, false);
186 scheduler_.RegisterStream(5, 5);
187 scheduler_.MarkStreamReady(5, false);
188
189 EXPECT_EQ(4u, scheduler_.PopNextReadyStream());
190 EXPECT_EQ(1u, scheduler_.PopNextReadyStream());
191 EXPECT_EQ(2u, scheduler_.PopNextReadyStream());
192 EXPECT_EQ(3u, scheduler_.PopNextReadyStream());
193 EXPECT_EQ(5u, scheduler_.PopNextReadyStream());
194 EXPECT_QUICHE_BUG(EXPECT_EQ(0u, scheduler_.PopNextReadyStream()),
195 "No ready streams available");
196 }
197
TEST_F(PriorityWriteSchedulerTest,MarkStreamReadyFront)198 TEST_F(PriorityWriteSchedulerTest, MarkStreamReadyFront) {
199 EXPECT_FALSE(scheduler_.HasReadyStreams());
200 EXPECT_QUICHE_BUG(scheduler_.MarkStreamReady(1, true),
201 "Stream 1 not registered");
202 EXPECT_FALSE(scheduler_.HasReadyStreams());
203 EXPECT_QUICHE_BUG(EXPECT_EQ(0u, scheduler_.PopNextReadyStream()),
204 "No ready streams available");
205
206 // Add a bunch of ready streams to head of per-priority lists.
207 // Expected order: (P2) 4, (P3) 3, 2, 1, (P5) 5
208 scheduler_.RegisterStream(1, 3);
209 scheduler_.MarkStreamReady(1, true);
210 EXPECT_TRUE(scheduler_.HasReadyStreams());
211 scheduler_.RegisterStream(2, 3);
212 scheduler_.MarkStreamReady(2, true);
213 scheduler_.RegisterStream(3, 3);
214 scheduler_.MarkStreamReady(3, true);
215 scheduler_.RegisterStream(4, 2);
216 scheduler_.MarkStreamReady(4, true);
217 scheduler_.RegisterStream(5, 5);
218 scheduler_.MarkStreamReady(5, true);
219
220 EXPECT_EQ(4u, scheduler_.PopNextReadyStream());
221 EXPECT_EQ(3u, scheduler_.PopNextReadyStream());
222 EXPECT_EQ(2u, scheduler_.PopNextReadyStream());
223 EXPECT_EQ(1u, scheduler_.PopNextReadyStream());
224 EXPECT_EQ(5u, scheduler_.PopNextReadyStream());
225 EXPECT_QUICHE_BUG(EXPECT_EQ(0u, scheduler_.PopNextReadyStream()),
226 "No ready streams available");
227 }
228
TEST_F(PriorityWriteSchedulerTest,MarkStreamReadyBackAndFront)229 TEST_F(PriorityWriteSchedulerTest, MarkStreamReadyBackAndFront) {
230 scheduler_.RegisterStream(1, 4);
231 scheduler_.RegisterStream(2, 3);
232 scheduler_.RegisterStream(3, 3);
233 scheduler_.RegisterStream(4, 3);
234 scheduler_.RegisterStream(5, 4);
235 scheduler_.RegisterStream(6, 1);
236
237 // Add a bunch of ready streams to per-priority lists, with variety of adding
238 // at head and tail.
239 // Expected order: (P1) 6, (P3) 4, 2, 3, (P4) 1, 5
240 scheduler_.MarkStreamReady(1, true);
241 scheduler_.MarkStreamReady(2, true);
242 scheduler_.MarkStreamReady(3, false);
243 scheduler_.MarkStreamReady(4, true);
244 scheduler_.MarkStreamReady(5, false);
245 scheduler_.MarkStreamReady(6, true);
246
247 EXPECT_EQ(6u, scheduler_.PopNextReadyStream());
248 EXPECT_EQ(4u, scheduler_.PopNextReadyStream());
249 EXPECT_EQ(2u, scheduler_.PopNextReadyStream());
250 EXPECT_EQ(3u, scheduler_.PopNextReadyStream());
251 EXPECT_EQ(1u, scheduler_.PopNextReadyStream());
252 EXPECT_EQ(5u, scheduler_.PopNextReadyStream());
253 EXPECT_QUICHE_BUG(EXPECT_EQ(0u, scheduler_.PopNextReadyStream()),
254 "No ready streams available");
255 }
256
TEST_F(PriorityWriteSchedulerTest,MarkStreamNotReady)257 TEST_F(PriorityWriteSchedulerTest, MarkStreamNotReady) {
258 // Verify ready state reflected in NumReadyStreams().
259 scheduler_.RegisterStream(1, 1);
260 EXPECT_EQ(0u, scheduler_.NumReadyStreams());
261 scheduler_.MarkStreamReady(1, false);
262 EXPECT_EQ(1u, scheduler_.NumReadyStreams());
263 scheduler_.MarkStreamNotReady(1);
264 EXPECT_EQ(0u, scheduler_.NumReadyStreams());
265
266 // Empty pop should fail.
267 EXPECT_QUICHE_BUG(EXPECT_EQ(0u, scheduler_.PopNextReadyStream()),
268 "No ready streams available");
269
270 // Tolerate redundant marking of a stream as not ready.
271 scheduler_.MarkStreamNotReady(1);
272 EXPECT_EQ(0u, scheduler_.NumReadyStreams());
273
274 // Should only be able to mark registered streams.
275 EXPECT_QUICHE_BUG(scheduler_.MarkStreamNotReady(3),
276 "Stream 3 not registered");
277 }
278
TEST_F(PriorityWriteSchedulerTest,UnregisterRemovesStream)279 TEST_F(PriorityWriteSchedulerTest, UnregisterRemovesStream) {
280 scheduler_.RegisterStream(3, 4);
281 scheduler_.MarkStreamReady(3, false);
282 EXPECT_EQ(1u, scheduler_.NumReadyStreams());
283
284 // Unregistering a stream should remove it from set of ready streams.
285 scheduler_.UnregisterStream(3);
286 EXPECT_EQ(0u, scheduler_.NumReadyStreams());
287 EXPECT_QUICHE_BUG(EXPECT_EQ(0u, scheduler_.PopNextReadyStream()),
288 "No ready streams available");
289 }
290
TEST_F(PriorityWriteSchedulerTest,ShouldYield)291 TEST_F(PriorityWriteSchedulerTest, ShouldYield) {
292 scheduler_.RegisterStream(1, 1);
293 scheduler_.RegisterStream(4, 4);
294 scheduler_.RegisterStream(5, 4);
295 scheduler_.RegisterStream(7, 7);
296
297 // Make sure we don't yield when the list is empty.
298 EXPECT_FALSE(scheduler_.ShouldYield(1));
299
300 // Add a low priority stream.
301 scheduler_.MarkStreamReady(4, false);
302 // 4 should not yield to itself.
303 EXPECT_FALSE(scheduler_.ShouldYield(4));
304 // 7 should yield as 4 is blocked and a higher priority.
305 EXPECT_TRUE(scheduler_.ShouldYield(7));
306 // 5 should yield to 4 as they are the same priority.
307 EXPECT_TRUE(scheduler_.ShouldYield(5));
308 // 1 should not yield as 1 is higher priority.
309 EXPECT_FALSE(scheduler_.ShouldYield(1));
310
311 // Add a second stream in that priority class.
312 scheduler_.MarkStreamReady(5, false);
313 // 4 and 5 are both blocked, but 4 is at the front so should not yield.
314 EXPECT_FALSE(scheduler_.ShouldYield(4));
315 EXPECT_TRUE(scheduler_.ShouldYield(5));
316 }
317
TEST_F(PriorityWriteSchedulerTest,GetLatestEventWithPriority)318 TEST_F(PriorityWriteSchedulerTest, GetLatestEventWithPriority) {
319 EXPECT_QUICHE_BUG(
320 scheduler_.RecordStreamEventTime(3, absl::FromUnixMicros(5)),
321 "Stream 3 not registered");
322 EXPECT_QUICHE_BUG(
323 EXPECT_FALSE(scheduler_.GetLatestEventWithPriority(4).has_value()),
324 "Stream 4 not registered");
325
326 for (int i = 1; i < 5; ++i) {
327 scheduler_.RegisterStream(i, i);
328 }
329 for (int i = 1; i < 5; ++i) {
330 EXPECT_FALSE(scheduler_.GetLatestEventWithPriority(i).has_value());
331 }
332 for (int i = 1; i < 5; ++i) {
333 scheduler_.RecordStreamEventTime(i, absl::FromUnixMicros(i * 100));
334 }
335 EXPECT_FALSE(scheduler_.GetLatestEventWithPriority(1).has_value());
336 for (int i = 2; i < 5; ++i) {
337 EXPECT_THAT(scheduler_.GetLatestEventWithPriority(i),
338 Optional(Eq(absl::FromUnixMicros((i - 1) * 100))));
339 }
340 }
341
342 } // namespace
343 } // namespace test
344 } // namespace http2
345