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