| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright 2014 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/http2_write_scheduler.h" | |
| 6 | |
| 7 #include "net/spdy/spdy_test_utils.h" | |
| 8 #include "net/test/gtest_util.h" | |
| 9 #include "testing/gmock/include/gmock/gmock.h" | |
| 10 #include "testing/gtest/include/gtest/gtest.h" | |
| 11 | |
| 12 namespace net { | |
| 13 | |
| 14 using ::testing::AssertionFailure; | |
| 15 using ::testing::AssertionResult; | |
| 16 using ::testing::AssertionSuccess; | |
| 17 using ::testing::ElementsAre; | |
| 18 using ::testing::IsEmpty; | |
| 19 using ::testing::UnorderedElementsAre; | |
| 20 | |
| 21 namespace test { | |
| 22 | |
| 23 template <typename StreamIdType> | |
| 24 class Http2PriorityWriteSchedulerPeer { | |
| 25 public: | |
| 26 explicit Http2PriorityWriteSchedulerPeer( | |
| 27 Http2PriorityWriteScheduler<StreamIdType>* scheduler) | |
| 28 : scheduler_(scheduler) {} | |
| 29 | |
| 30 int TotalChildWeights(StreamIdType stream_id) const { | |
| 31 return scheduler_->FindStream(stream_id)->total_child_weights; | |
| 32 } | |
| 33 | |
| 34 bool ValidateInvariants() const { | |
| 35 return scheduler_->ValidateInvariantsForTests(); | |
| 36 } | |
| 37 | |
| 38 private: | |
| 39 Http2PriorityWriteScheduler<StreamIdType>* scheduler_; | |
| 40 }; | |
| 41 | |
| 42 class Http2PriorityWriteSchedulerTest : public ::testing::Test { | |
| 43 protected: | |
| 44 using SpdyStreamId = uint32_t; | |
| 45 | |
| 46 Http2PriorityWriteSchedulerTest() : peer_(&scheduler_) {} | |
| 47 | |
| 48 Http2PriorityWriteScheduler<SpdyStreamId> scheduler_; | |
| 49 Http2PriorityWriteSchedulerPeer<SpdyStreamId> peer_; | |
| 50 }; | |
| 51 | |
| 52 TEST_F(Http2PriorityWriteSchedulerTest, RegisterAndUnregisterStreams) { | |
| 53 EXPECT_EQ(1, scheduler_.num_streams()); | |
| 54 EXPECT_TRUE(scheduler_.StreamRegistered(0)); | |
| 55 EXPECT_FALSE(scheduler_.StreamRegistered(1)); | |
| 56 | |
| 57 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); | |
| 58 EXPECT_EQ(2, scheduler_.num_streams()); | |
| 59 ASSERT_TRUE(scheduler_.StreamRegistered(1)); | |
| 60 EXPECT_EQ(100, scheduler_.GetStreamPrecedence(1).weight()); | |
| 61 EXPECT_FALSE(scheduler_.StreamRegistered(5)); | |
| 62 EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(1)); | |
| 63 | |
| 64 scheduler_.RegisterStream(5, SpdyStreamPrecedence(0, 50, false)); | |
| 65 // Should not be able to add a stream with an id that already exists. | |
| 66 EXPECT_SPDY_BUG( | |
| 67 scheduler_.RegisterStream(5, SpdyStreamPrecedence(1, 50, false)), | |
| 68 "Stream 5 already registered"); | |
| 69 EXPECT_EQ(3, scheduler_.num_streams()); | |
| 70 EXPECT_TRUE(scheduler_.StreamRegistered(1)); | |
| 71 ASSERT_TRUE(scheduler_.StreamRegistered(5)); | |
| 72 EXPECT_EQ(50, scheduler_.GetStreamPrecedence(5).weight()); | |
| 73 EXPECT_FALSE(scheduler_.StreamRegistered(13)); | |
| 74 | |
| 75 scheduler_.RegisterStream(13, SpdyStreamPrecedence(5, 130, true)); | |
| 76 EXPECT_EQ(4, scheduler_.num_streams()); | |
| 77 EXPECT_TRUE(scheduler_.StreamRegistered(1)); | |
| 78 EXPECT_TRUE(scheduler_.StreamRegistered(5)); | |
| 79 ASSERT_TRUE(scheduler_.StreamRegistered(13)); | |
| 80 EXPECT_EQ(130, scheduler_.GetStreamPrecedence(13).weight()); | |
| 81 EXPECT_EQ(5u, scheduler_.GetStreamPrecedence(13).parent_id()); | |
| 82 | |
| 83 scheduler_.UnregisterStream(5); | |
| 84 // Cannot remove a stream that has already been removed. | |
| 85 EXPECT_SPDY_BUG(scheduler_.UnregisterStream(5), "Stream 5 not registered"); | |
| 86 EXPECT_EQ(3, scheduler_.num_streams()); | |
| 87 EXPECT_TRUE(scheduler_.StreamRegistered(1)); | |
| 88 EXPECT_FALSE(scheduler_.StreamRegistered(5)); | |
| 89 EXPECT_TRUE(scheduler_.StreamRegistered(13)); | |
| 90 EXPECT_EQ(kHttp2RootStreamId, scheduler_.GetStreamPrecedence(13).parent_id()); | |
| 91 | |
| 92 // The parent stream 19 doesn't exist, so this should use 0 as parent stream: | |
| 93 scheduler_.RegisterStream(7, SpdyStreamPrecedence(19, 70, false)); | |
| 94 EXPECT_TRUE(scheduler_.StreamRegistered(7)); | |
| 95 EXPECT_EQ(0u, scheduler_.GetStreamPrecedence(7).parent_id()); | |
| 96 // Now stream 7 already exists, so this should fail: | |
| 97 EXPECT_SPDY_BUG( | |
| 98 scheduler_.RegisterStream(7, SpdyStreamPrecedence(1, 70, false)), | |
| 99 "Stream 7 already registered"); | |
| 100 // Try adding a second child to stream 13: | |
| 101 scheduler_.RegisterStream(17, SpdyStreamPrecedence(13, 170, false)); | |
| 102 | |
| 103 scheduler_.UpdateStreamPrecedence(17, SpdyStreamPrecedence(13, 150, false)); | |
| 104 EXPECT_EQ(150, scheduler_.GetStreamPrecedence(17).weight()); | |
| 105 | |
| 106 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 107 } | |
| 108 | |
| 109 TEST_F(Http2PriorityWriteSchedulerTest, RegisterStreamWithSpdy3Priority) { | |
| 110 EXPECT_FALSE(scheduler_.StreamRegistered(1)); | |
| 111 EXPECT_SPDY_BUG(scheduler_.RegisterStream(1, SpdyStreamPrecedence(3)), | |
| 112 "Expected HTTP/2 stream dependency"); | |
| 113 EXPECT_EQ(0u, scheduler_.NumReadyStreams()); | |
| 114 EXPECT_TRUE(scheduler_.StreamRegistered(1)); | |
| 115 EXPECT_EQ(3, scheduler_.GetStreamPrecedence(1).spdy3_priority()); | |
| 116 EXPECT_EQ(147, scheduler_.GetStreamPrecedence(1).weight()); | |
| 117 EXPECT_EQ(kHttp2RootStreamId, scheduler_.GetStreamPrecedence(1).parent_id()); | |
| 118 EXPECT_THAT(scheduler_.GetStreamChildren(1), IsEmpty()); | |
| 119 | |
| 120 EXPECT_SPDY_BUG(scheduler_.RegisterStream(1, SpdyStreamPrecedence(4)), | |
| 121 "Stream 1 already registered"); | |
| 122 EXPECT_EQ(3, scheduler_.GetStreamPrecedence(1).spdy3_priority()); | |
| 123 } | |
| 124 | |
| 125 TEST_F(Http2PriorityWriteSchedulerTest, GetStreamWeight) { | |
| 126 // Unknown streams tolerated due to b/15676312. | |
| 127 EXPECT_EQ(kHttp2MinStreamWeight, scheduler_.GetStreamPrecedence(3).weight()); | |
| 128 scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 130, true)); | |
| 129 EXPECT_EQ(130, scheduler_.GetStreamPrecedence(3).weight()); | |
| 130 scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 50, true)); | |
| 131 EXPECT_EQ(50, scheduler_.GetStreamPrecedence(3).weight()); | |
| 132 scheduler_.UnregisterStream(3); | |
| 133 EXPECT_EQ(kHttp2MinStreamWeight, scheduler_.GetStreamPrecedence(3).weight()); | |
| 134 } | |
| 135 | |
| 136 TEST_F(Http2PriorityWriteSchedulerTest, GetStreamPriority) { | |
| 137 // Unknown streams tolerated due to b/15676312. | |
| 138 EXPECT_EQ(kV3LowestPriority, | |
| 139 scheduler_.GetStreamPrecedence(3).spdy3_priority()); | |
| 140 scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 130, true)); | |
| 141 EXPECT_EQ(3, scheduler_.GetStreamPrecedence(3).spdy3_priority()); | |
| 142 scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 50, true)); | |
| 143 EXPECT_EQ(5, scheduler_.GetStreamPrecedence(3).spdy3_priority()); | |
| 144 scheduler_.UnregisterStream(3); | |
| 145 EXPECT_EQ(kV3LowestPriority, | |
| 146 scheduler_.GetStreamPrecedence(3).spdy3_priority()); | |
| 147 } | |
| 148 | |
| 149 TEST_F(Http2PriorityWriteSchedulerTest, GetStreamParent) { | |
| 150 // Unknown streams tolerated due to b/15676312. | |
| 151 EXPECT_EQ(kHttp2RootStreamId, scheduler_.GetStreamPrecedence(3).parent_id()); | |
| 152 scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 20, false)); | |
| 153 scheduler_.RegisterStream(3, SpdyStreamPrecedence(2, 30, false)); | |
| 154 EXPECT_EQ(2u, scheduler_.GetStreamPrecedence(3).parent_id()); | |
| 155 scheduler_.UnregisterStream(3); | |
| 156 EXPECT_EQ(kHttp2RootStreamId, scheduler_.GetStreamPrecedence(3).parent_id()); | |
| 157 } | |
| 158 | |
| 159 TEST_F(Http2PriorityWriteSchedulerTest, GetStreamChildren) { | |
| 160 EXPECT_SPDY_BUG(EXPECT_THAT(scheduler_.GetStreamChildren(7), IsEmpty()), | |
| 161 "Stream 7 not registered"); | |
| 162 scheduler_.RegisterStream(7, SpdyStreamPrecedence(0, 70, false)); | |
| 163 EXPECT_THAT(scheduler_.GetStreamChildren(7), IsEmpty()); | |
| 164 scheduler_.RegisterStream(9, SpdyStreamPrecedence(7, 90, false)); | |
| 165 scheduler_.RegisterStream(15, SpdyStreamPrecedence(7, 150, false)); | |
| 166 EXPECT_THAT(scheduler_.GetStreamChildren(7), UnorderedElementsAre(9, 15)); | |
| 167 scheduler_.UnregisterStream(7); | |
| 168 EXPECT_SPDY_BUG(EXPECT_THAT(scheduler_.GetStreamChildren(7), IsEmpty()), | |
| 169 "Stream 7 not registered"); | |
| 170 } | |
| 171 | |
| 172 TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamWeight) { | |
| 173 EXPECT_SPDY_BUG( | |
| 174 scheduler_.UpdateStreamPrecedence(0, SpdyStreamPrecedence(0, 10, false)), | |
| 175 "Cannot set precedence of root stream"); | |
| 176 | |
| 177 // For the moment, updating stream precedence on a non-registered stream | |
| 178 // should have no effect. In the future, it will lazily cause the stream to | |
| 179 // be registered (b/15676312). | |
| 180 scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 10, false)); | |
| 181 EXPECT_FALSE(scheduler_.StreamRegistered(3)); | |
| 182 | |
| 183 scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 10, false)); | |
| 184 scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 20, false)); | |
| 185 EXPECT_EQ(20, scheduler_.GetStreamPrecedence(3).weight()); | |
| 186 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 187 | |
| 188 EXPECT_SPDY_BUG( | |
| 189 scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 500, false)), | |
| 190 "Invalid weight: 500"); | |
| 191 EXPECT_EQ(kHttp2MaxStreamWeight, scheduler_.GetStreamPrecedence(3).weight()); | |
| 192 EXPECT_SPDY_BUG( | |
| 193 scheduler_.UpdateStreamPrecedence(3, SpdyStreamPrecedence(0, 0, false)), | |
| 194 "Invalid weight: 0"); | |
| 195 EXPECT_EQ(kHttp2MinStreamWeight, scheduler_.GetStreamPrecedence(3).weight()); | |
| 196 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 197 | |
| 198 scheduler_.UnregisterStream(3); | |
| 199 } | |
| 200 | |
| 201 // Basic case of reparenting a subtree. | |
| 202 TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentBasicNonExclusive) { | |
| 203 /* Tree: | |
| 204 0 | |
| 205 / \ | |
| 206 1 2 | |
| 207 / \ | |
| 208 3 4 | |
| 209 */ | |
| 210 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); | |
| 211 scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false)); | |
| 212 scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); | |
| 213 scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false)); | |
| 214 scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(2, 100, false)); | |
| 215 EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(2)); | |
| 216 EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(3, 4)); | |
| 217 EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(1)); | |
| 218 EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); | |
| 219 EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty()); | |
| 220 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 221 } | |
| 222 | |
| 223 // Basic case of reparenting a subtree. Result here is the same as the | |
| 224 // non-exclusive case. | |
| 225 TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentBasicExclusive) { | |
| 226 /* Tree: | |
| 227 0 | |
| 228 / \ | |
| 229 1 2 | |
| 230 / \ | |
| 231 3 4 | |
| 232 */ | |
| 233 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); | |
| 234 scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false)); | |
| 235 scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); | |
| 236 scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false)); | |
| 237 scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(2, 100, true)); | |
| 238 EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(2)); | |
| 239 EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(3, 4)); | |
| 240 EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(1)); | |
| 241 EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); | |
| 242 EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty()); | |
| 243 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 244 } | |
| 245 | |
| 246 // We can't set the parent of a nonexistent stream, or set the parent to a | |
| 247 // nonexistent stream. | |
| 248 TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentNonexistent) { | |
| 249 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); | |
| 250 scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false)); | |
| 251 for (bool exclusive : {true, false}) { | |
| 252 // For the moment, updating stream precedence on a non-registered stream or | |
| 253 // attempting to set parent to a nonexistent stream should have no | |
| 254 // effect. In the future, it will lazily cause the stream(s) to be | |
| 255 // registered (b/15676312). | |
| 256 | |
| 257 // No-op: parent stream 3 not registered | |
| 258 scheduler_.UpdateStreamPrecedence(1, | |
| 259 SpdyStreamPrecedence(3, 100, exclusive)); | |
| 260 | |
| 261 // No-op: stream 4 not registered | |
| 262 scheduler_.UpdateStreamPrecedence(4, | |
| 263 SpdyStreamPrecedence(2, 100, exclusive)); | |
| 264 | |
| 265 // No-op: stream 3 not registered | |
| 266 scheduler_.UpdateStreamPrecedence(3, | |
| 267 SpdyStreamPrecedence(4, 100, exclusive)); | |
| 268 | |
| 269 EXPECT_THAT(scheduler_.GetStreamChildren(0), UnorderedElementsAre(1, 2)); | |
| 270 EXPECT_THAT(scheduler_.GetStreamChildren(1), IsEmpty()); | |
| 271 EXPECT_THAT(scheduler_.GetStreamChildren(2), IsEmpty()); | |
| 272 EXPECT_FALSE(scheduler_.StreamRegistered(3)); | |
| 273 EXPECT_FALSE(scheduler_.StreamRegistered(4)); | |
| 274 } | |
| 275 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 276 } | |
| 277 | |
| 278 // We should be able to add multiple children to streams. | |
| 279 TEST_F(Http2PriorityWriteSchedulerTest, | |
| 280 UpdateStreamParentMultipleChildrenNonExclusive) { | |
| 281 /* Tree: | |
| 282 0 | |
| 283 / \ | |
| 284 1 2 | |
| 285 / \ \ | |
| 286 3 4 5 | |
| 287 */ | |
| 288 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); | |
| 289 scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false)); | |
| 290 scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); | |
| 291 scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false)); | |
| 292 scheduler_.RegisterStream(5, SpdyStreamPrecedence(2, 100, false)); | |
| 293 scheduler_.UpdateStreamPrecedence(2, SpdyStreamPrecedence(1, 100, false)); | |
| 294 EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(1)); | |
| 295 EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(2, 3, 4)); | |
| 296 EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(5)); | |
| 297 EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); | |
| 298 EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty()); | |
| 299 EXPECT_THAT(scheduler_.GetStreamChildren(5), IsEmpty()); | |
| 300 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 301 } | |
| 302 | |
| 303 TEST_F(Http2PriorityWriteSchedulerTest, | |
| 304 UpdateStreamParentMultipleChildrenExclusive) { | |
| 305 /* Tree: | |
| 306 0 | |
| 307 / \ | |
| 308 1 2 | |
| 309 / \ \ | |
| 310 3 4 5 | |
| 311 */ | |
| 312 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); | |
| 313 scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false)); | |
| 314 scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); | |
| 315 scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false)); | |
| 316 scheduler_.RegisterStream(5, SpdyStreamPrecedence(2, 100, false)); | |
| 317 scheduler_.UpdateStreamPrecedence(2, SpdyStreamPrecedence(1, 100, true)); | |
| 318 EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(1)); | |
| 319 EXPECT_THAT(scheduler_.GetStreamChildren(1), ElementsAre(2)); | |
| 320 EXPECT_THAT(scheduler_.GetStreamChildren(2), UnorderedElementsAre(3, 4, 5)); | |
| 321 EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); | |
| 322 EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty()); | |
| 323 EXPECT_THAT(scheduler_.GetStreamChildren(5), IsEmpty()); | |
| 324 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 325 } | |
| 326 | |
| 327 TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentToChildNonExclusive) { | |
| 328 /* Tree: | |
| 329 0 | |
| 330 | | |
| 331 1 | |
| 332 / \ | |
| 333 2 3 | |
| 334 | | |
| 335 4 | |
| 336 */ | |
| 337 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); | |
| 338 scheduler_.RegisterStream(2, SpdyStreamPrecedence(1, 100, false)); | |
| 339 scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); | |
| 340 scheduler_.RegisterStream(4, SpdyStreamPrecedence(2, 100, false)); | |
| 341 scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(2, 100, false)); | |
| 342 EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(2)); | |
| 343 EXPECT_THAT(scheduler_.GetStreamChildren(1), ElementsAre(3)); | |
| 344 EXPECT_THAT(scheduler_.GetStreamChildren(2), UnorderedElementsAre(1, 4)); | |
| 345 EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); | |
| 346 EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty()); | |
| 347 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 348 } | |
| 349 | |
| 350 TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentToChildExclusive) { | |
| 351 /* Tree: | |
| 352 0 | |
| 353 | | |
| 354 1 | |
| 355 / \ | |
| 356 2 3 | |
| 357 | | |
| 358 4 | |
| 359 */ | |
| 360 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); | |
| 361 scheduler_.RegisterStream(2, SpdyStreamPrecedence(1, 100, false)); | |
| 362 scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); | |
| 363 scheduler_.RegisterStream(4, SpdyStreamPrecedence(2, 100, false)); | |
| 364 scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(2, 100, true)); | |
| 365 EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(2)); | |
| 366 EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(3, 4)); | |
| 367 EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(1)); | |
| 368 EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); | |
| 369 EXPECT_THAT(scheduler_.GetStreamChildren(4), IsEmpty()); | |
| 370 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 371 } | |
| 372 | |
| 373 TEST_F(Http2PriorityWriteSchedulerTest, | |
| 374 UpdateStreamParentToGrandchildNonExclusive) { | |
| 375 /* Tree: | |
| 376 0 | |
| 377 | | |
| 378 1 | |
| 379 / \ | |
| 380 2 3 | |
| 381 / \ | |
| 382 4 5 | |
| 383 | | |
| 384 6 | |
| 385 */ | |
| 386 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); | |
| 387 scheduler_.RegisterStream(2, SpdyStreamPrecedence(1, 100, false)); | |
| 388 scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); | |
| 389 scheduler_.RegisterStream(4, SpdyStreamPrecedence(2, 100, false)); | |
| 390 scheduler_.RegisterStream(5, SpdyStreamPrecedence(2, 100, false)); | |
| 391 scheduler_.RegisterStream(6, SpdyStreamPrecedence(4, 100, false)); | |
| 392 scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(4, 100, false)); | |
| 393 EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(4)); | |
| 394 EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(2, 3)); | |
| 395 EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(5)); | |
| 396 EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); | |
| 397 EXPECT_THAT(scheduler_.GetStreamChildren(4), UnorderedElementsAre(1, 6)); | |
| 398 EXPECT_THAT(scheduler_.GetStreamChildren(5), IsEmpty()); | |
| 399 EXPECT_THAT(scheduler_.GetStreamChildren(6), IsEmpty()); | |
| 400 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 401 } | |
| 402 | |
| 403 TEST_F(Http2PriorityWriteSchedulerTest, | |
| 404 UpdateStreamParentToGrandchildExclusive) { | |
| 405 /* Tree: | |
| 406 0 | |
| 407 | | |
| 408 1 | |
| 409 / \ | |
| 410 2 3 | |
| 411 / \ | |
| 412 4 5 | |
| 413 | | |
| 414 6 | |
| 415 */ | |
| 416 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); | |
| 417 scheduler_.RegisterStream(2, SpdyStreamPrecedence(1, 100, false)); | |
| 418 scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); | |
| 419 scheduler_.RegisterStream(4, SpdyStreamPrecedence(2, 100, false)); | |
| 420 scheduler_.RegisterStream(5, SpdyStreamPrecedence(2, 100, false)); | |
| 421 scheduler_.RegisterStream(6, SpdyStreamPrecedence(4, 100, false)); | |
| 422 scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(4, 100, true)); | |
| 423 EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(4)); | |
| 424 EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(2, 3, 6)); | |
| 425 EXPECT_THAT(scheduler_.GetStreamChildren(2), ElementsAre(5)); | |
| 426 EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); | |
| 427 EXPECT_THAT(scheduler_.GetStreamChildren(4), ElementsAre(1)); | |
| 428 EXPECT_THAT(scheduler_.GetStreamChildren(5), IsEmpty()); | |
| 429 EXPECT_THAT(scheduler_.GetStreamChildren(6), IsEmpty()); | |
| 430 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 431 } | |
| 432 | |
| 433 TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentToParent) { | |
| 434 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); | |
| 435 scheduler_.RegisterStream(2, SpdyStreamPrecedence(1, 100, false)); | |
| 436 scheduler_.RegisterStream(3, SpdyStreamPrecedence(1, 100, false)); | |
| 437 for (bool exclusive : {true, false}) { | |
| 438 scheduler_.UpdateStreamPrecedence(2, | |
| 439 SpdyStreamPrecedence(1, 100, exclusive)); | |
| 440 EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(1)); | |
| 441 EXPECT_THAT(scheduler_.GetStreamChildren(1), UnorderedElementsAre(2, 3)); | |
| 442 EXPECT_THAT(scheduler_.GetStreamChildren(2), IsEmpty()); | |
| 443 EXPECT_THAT(scheduler_.GetStreamChildren(3), IsEmpty()); | |
| 444 } | |
| 445 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 446 } | |
| 447 | |
| 448 TEST_F(Http2PriorityWriteSchedulerTest, UpdateStreamParentToSelf) { | |
| 449 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); | |
| 450 EXPECT_SPDY_BUG( | |
| 451 scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(1, 100, false)), | |
| 452 "Cannot set stream to be its own parent"); | |
| 453 EXPECT_SPDY_BUG( | |
| 454 scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(1, 100, true)), | |
| 455 "Cannot set stream to be its own parent"); | |
| 456 EXPECT_THAT(scheduler_.GetStreamChildren(0), ElementsAre(1)); | |
| 457 EXPECT_THAT(scheduler_.GetStreamChildren(1), IsEmpty()); | |
| 458 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 459 } | |
| 460 | |
| 461 TEST_F(Http2PriorityWriteSchedulerTest, BlockAndUnblock) { | |
| 462 /* Create the tree. | |
| 463 | |
| 464 0 | |
| 465 / | \ | |
| 466 / | \ | |
| 467 1 2 3 | |
| 468 / \ \ \ | |
| 469 4 5 6 7 | |
| 470 /| / \ | |\ | |
| 471 8 9 10 11 12 13 14 | |
| 472 / \ | |
| 473 15 16 | |
| 474 | |
| 475 */ | |
| 476 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); | |
| 477 scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false)); | |
| 478 scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 100, false)); | |
| 479 scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false)); | |
| 480 scheduler_.RegisterStream(5, SpdyStreamPrecedence(1, 100, false)); | |
| 481 scheduler_.RegisterStream(8, SpdyStreamPrecedence(4, 100, false)); | |
| 482 scheduler_.RegisterStream(9, SpdyStreamPrecedence(4, 100, false)); | |
| 483 scheduler_.RegisterStream(10, SpdyStreamPrecedence(5, 100, false)); | |
| 484 scheduler_.RegisterStream(11, SpdyStreamPrecedence(5, 100, false)); | |
| 485 scheduler_.RegisterStream(15, SpdyStreamPrecedence(8, 100, false)); | |
| 486 scheduler_.RegisterStream(16, SpdyStreamPrecedence(8, 100, false)); | |
| 487 scheduler_.RegisterStream(12, SpdyStreamPrecedence(2, 100, false)); | |
| 488 scheduler_.RegisterStream(6, SpdyStreamPrecedence(2, 100, true)); | |
| 489 scheduler_.RegisterStream(7, SpdyStreamPrecedence(0, 100, false)); | |
| 490 scheduler_.RegisterStream(13, SpdyStreamPrecedence(7, 100, true)); | |
| 491 scheduler_.RegisterStream(14, SpdyStreamPrecedence(7, 100, false)); | |
| 492 scheduler_.UpdateStreamPrecedence(7, SpdyStreamPrecedence(3, 100, false)); | |
| 493 EXPECT_EQ(0u, scheduler_.GetStreamPrecedence(1).parent_id()); | |
| 494 EXPECT_EQ(0u, scheduler_.GetStreamPrecedence(2).parent_id()); | |
| 495 EXPECT_EQ(0u, scheduler_.GetStreamPrecedence(3).parent_id()); | |
| 496 EXPECT_EQ(1u, scheduler_.GetStreamPrecedence(4).parent_id()); | |
| 497 EXPECT_EQ(1u, scheduler_.GetStreamPrecedence(5).parent_id()); | |
| 498 EXPECT_EQ(2u, scheduler_.GetStreamPrecedence(6).parent_id()); | |
| 499 EXPECT_EQ(3u, scheduler_.GetStreamPrecedence(7).parent_id()); | |
| 500 EXPECT_EQ(4u, scheduler_.GetStreamPrecedence(8).parent_id()); | |
| 501 EXPECT_EQ(4u, scheduler_.GetStreamPrecedence(9).parent_id()); | |
| 502 EXPECT_EQ(5u, scheduler_.GetStreamPrecedence(10).parent_id()); | |
| 503 EXPECT_EQ(5u, scheduler_.GetStreamPrecedence(11).parent_id()); | |
| 504 EXPECT_EQ(6u, scheduler_.GetStreamPrecedence(12).parent_id()); | |
| 505 EXPECT_EQ(7u, scheduler_.GetStreamPrecedence(13).parent_id()); | |
| 506 EXPECT_EQ(7u, scheduler_.GetStreamPrecedence(14).parent_id()); | |
| 507 EXPECT_EQ(8u, scheduler_.GetStreamPrecedence(15).parent_id()); | |
| 508 EXPECT_EQ(8u, scheduler_.GetStreamPrecedence(16).parent_id()); | |
| 509 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 510 | |
| 511 EXPECT_EQ(peer_.TotalChildWeights(0), | |
| 512 scheduler_.GetStreamPrecedence(1).weight() + | |
| 513 scheduler_.GetStreamPrecedence(2).weight() + | |
| 514 scheduler_.GetStreamPrecedence(3).weight()); | |
| 515 EXPECT_EQ(peer_.TotalChildWeights(3), | |
| 516 scheduler_.GetStreamPrecedence(7).weight()); | |
| 517 EXPECT_EQ(peer_.TotalChildWeights(7), | |
| 518 scheduler_.GetStreamPrecedence(13).weight() + | |
| 519 scheduler_.GetStreamPrecedence(14).weight()); | |
| 520 EXPECT_EQ(peer_.TotalChildWeights(13), 0); | |
| 521 EXPECT_EQ(peer_.TotalChildWeights(14), 0); | |
| 522 | |
| 523 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 524 } | |
| 525 | |
| 526 TEST_F(Http2PriorityWriteSchedulerTest, HasReadyStreams) { | |
| 527 EXPECT_FALSE(scheduler_.HasReadyStreams()); | |
| 528 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 10, false)); | |
| 529 EXPECT_FALSE(scheduler_.HasReadyStreams()); | |
| 530 scheduler_.MarkStreamReady(1, false); | |
| 531 EXPECT_TRUE(scheduler_.HasReadyStreams()); | |
| 532 scheduler_.MarkStreamNotReady(1); | |
| 533 EXPECT_FALSE(scheduler_.HasReadyStreams()); | |
| 534 scheduler_.MarkStreamReady(1, true); | |
| 535 EXPECT_TRUE(scheduler_.HasReadyStreams()); | |
| 536 scheduler_.UnregisterStream(1); | |
| 537 EXPECT_FALSE(scheduler_.HasReadyStreams()); | |
| 538 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 539 } | |
| 540 | |
| 541 TEST_F(Http2PriorityWriteSchedulerTest, CalculateRoundedWeights) { | |
| 542 /* Create the tree. | |
| 543 | |
| 544 0 | |
| 545 / \ | |
| 546 1 2 | |
| 547 /| |\ |\ | |
| 548 8 3 4 5 6 7 | |
| 549 */ | |
| 550 scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 100, false)); | |
| 551 scheduler_.RegisterStream(4, SpdyStreamPrecedence(0, 100, false)); | |
| 552 scheduler_.RegisterStream(5, SpdyStreamPrecedence(0, 100, false)); | |
| 553 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 10, true)); | |
| 554 scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 5, false)); | |
| 555 scheduler_.RegisterStream(6, SpdyStreamPrecedence(2, 1, false)); | |
| 556 scheduler_.RegisterStream(7, SpdyStreamPrecedence(2, 1, false)); | |
| 557 scheduler_.RegisterStream(8, SpdyStreamPrecedence(1, 1, false)); | |
| 558 | |
| 559 // Remove higher-level streams. | |
| 560 scheduler_.UnregisterStream(1); | |
| 561 scheduler_.UnregisterStream(2); | |
| 562 | |
| 563 // 3.3 rounded down = 3. | |
| 564 EXPECT_EQ(3, scheduler_.GetStreamPrecedence(3).weight()); | |
| 565 EXPECT_EQ(3, scheduler_.GetStreamPrecedence(4).weight()); | |
| 566 EXPECT_EQ(3, scheduler_.GetStreamPrecedence(5).weight()); | |
| 567 // 2.5 rounded up = 3. | |
| 568 EXPECT_EQ(3, scheduler_.GetStreamPrecedence(6).weight()); | |
| 569 EXPECT_EQ(3, scheduler_.GetStreamPrecedence(7).weight()); | |
| 570 // 0 is not a valid weight, so round up to 1. | |
| 571 EXPECT_EQ(1, scheduler_.GetStreamPrecedence(8).weight()); | |
| 572 ASSERT_TRUE(peer_.ValidateInvariants()); | |
| 573 } | |
| 574 | |
| 575 TEST_F(Http2PriorityWriteSchedulerTest, GetLatestEventWithPrecedence) { | |
| 576 EXPECT_SPDY_BUG(scheduler_.RecordStreamEventTime(3, 5), | |
| 577 "Stream 3 not registered"); | |
| 578 EXPECT_SPDY_BUG(EXPECT_EQ(0, scheduler_.GetLatestEventWithPrecedence(4)), | |
| 579 "Stream 4 not registered"); | |
| 580 | |
| 581 for (int i = 1; i < 5; ++i) { | |
| 582 int weight = SpdyStreamPrecedence(i).weight(); | |
| 583 scheduler_.RegisterStream(i, SpdyStreamPrecedence(0, weight, false)); | |
| 584 } | |
| 585 for (int i = 1; i < 5; ++i) { | |
| 586 EXPECT_EQ(0, scheduler_.GetLatestEventWithPrecedence(i)); | |
| 587 } | |
| 588 for (int i = 1; i < 5; ++i) { | |
| 589 scheduler_.RecordStreamEventTime(i, i * 100); | |
| 590 } | |
| 591 for (int i = 1; i < 5; ++i) { | |
| 592 EXPECT_EQ((i - 1) * 100, scheduler_.GetLatestEventWithPrecedence(i)); | |
| 593 } | |
| 594 } | |
| 595 | |
| 596 // Add ready streams at front and back. | |
| 597 TEST_F(Http2PriorityWriteSchedulerTest, MarkReadyFrontAndBack) { | |
| 598 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 10, false)); | |
| 599 scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 20, false)); | |
| 600 scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 20, false)); | |
| 601 scheduler_.RegisterStream(4, SpdyStreamPrecedence(0, 20, false)); | |
| 602 scheduler_.RegisterStream(5, SpdyStreamPrecedence(0, 30, false)); | |
| 603 | |
| 604 for (int i = 1; i < 6; ++i) { | |
| 605 scheduler_.MarkStreamReady(i, false); | |
| 606 } | |
| 607 EXPECT_EQ(5u, scheduler_.PopNextReadyStream()); | |
| 608 EXPECT_EQ(2u, scheduler_.PopNextReadyStream()); | |
| 609 scheduler_.MarkStreamReady(2, false); | |
| 610 EXPECT_EQ(3u, scheduler_.PopNextReadyStream()); | |
| 611 scheduler_.MarkStreamReady(3, false); | |
| 612 EXPECT_EQ(4u, scheduler_.PopNextReadyStream()); | |
| 613 scheduler_.MarkStreamReady(4, false); | |
| 614 EXPECT_EQ(2u, scheduler_.PopNextReadyStream()); | |
| 615 scheduler_.MarkStreamReady(2, true); | |
| 616 EXPECT_EQ(2u, scheduler_.PopNextReadyStream()); | |
| 617 scheduler_.MarkStreamReady(5, false); | |
| 618 scheduler_.MarkStreamReady(2, true); | |
| 619 EXPECT_EQ(5u, scheduler_.PopNextReadyStream()); | |
| 620 } | |
| 621 | |
| 622 // Add ready streams at front and back and pop them with | |
| 623 // PopNextReadyStreamAndPrecedence. | |
| 624 TEST_F(Http2PriorityWriteSchedulerTest, PopNextReadyStreamAndPrecedence) { | |
| 625 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 10, false)); | |
| 626 scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 20, false)); | |
| 627 scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 20, false)); | |
| 628 scheduler_.RegisterStream(4, SpdyStreamPrecedence(0, 20, false)); | |
| 629 scheduler_.RegisterStream(5, SpdyStreamPrecedence(0, 30, false)); | |
| 630 | |
| 631 for (int i = 1; i < 6; ++i) { | |
| 632 scheduler_.MarkStreamReady(i, false); | |
| 633 } | |
| 634 EXPECT_EQ(std::make_tuple(5u, SpdyStreamPrecedence(0, 30, false)), | |
| 635 scheduler_.PopNextReadyStreamAndPrecedence()); | |
| 636 EXPECT_EQ(std::make_tuple(2u, SpdyStreamPrecedence(0, 20, false)), | |
| 637 scheduler_.PopNextReadyStreamAndPrecedence()); | |
| 638 scheduler_.MarkStreamReady(2, false); | |
| 639 EXPECT_EQ(std::make_tuple(3u, SpdyStreamPrecedence(0, 20, false)), | |
| 640 scheduler_.PopNextReadyStreamAndPrecedence()); | |
| 641 scheduler_.MarkStreamReady(3, false); | |
| 642 EXPECT_EQ(std::make_tuple(4u, SpdyStreamPrecedence(0, 20, false)), | |
| 643 scheduler_.PopNextReadyStreamAndPrecedence()); | |
| 644 scheduler_.MarkStreamReady(4, false); | |
| 645 EXPECT_EQ(std::make_tuple(2u, SpdyStreamPrecedence(0, 20, false)), | |
| 646 scheduler_.PopNextReadyStreamAndPrecedence()); | |
| 647 scheduler_.MarkStreamReady(2, true); | |
| 648 EXPECT_EQ(std::make_tuple(2u, SpdyStreamPrecedence(0, 20, false)), | |
| 649 scheduler_.PopNextReadyStreamAndPrecedence()); | |
| 650 scheduler_.MarkStreamReady(5, false); | |
| 651 scheduler_.MarkStreamReady(2, true); | |
| 652 EXPECT_EQ(std::make_tuple(5u, SpdyStreamPrecedence(0, 30, false)), | |
| 653 scheduler_.PopNextReadyStreamAndPrecedence()); | |
| 654 } | |
| 655 | |
| 656 class PopNextReadyStreamTest : public Http2PriorityWriteSchedulerTest { | |
| 657 protected: | |
| 658 void SetUp() override { | |
| 659 /* Create the tree. | |
| 660 | |
| 661 0 | |
| 662 /|\ | |
| 663 1 2 3 | |
| 664 /| |\ | |
| 665 4 5 6 7 | |
| 666 / | |
| 667 8 | |
| 668 | |
| 669 */ | |
| 670 scheduler_.RegisterStream(1, SpdyStreamPrecedence(0, 100, false)); | |
| 671 scheduler_.RegisterStream(2, SpdyStreamPrecedence(0, 100, false)); | |
| 672 scheduler_.RegisterStream(3, SpdyStreamPrecedence(0, 100, false)); | |
| 673 scheduler_.RegisterStream(4, SpdyStreamPrecedence(1, 100, false)); | |
| 674 scheduler_.RegisterStream(5, SpdyStreamPrecedence(1, 100, false)); | |
| 675 scheduler_.RegisterStream(6, SpdyStreamPrecedence(2, 100, false)); | |
| 676 scheduler_.RegisterStream(7, SpdyStreamPrecedence(2, 100, false)); | |
| 677 scheduler_.RegisterStream(8, SpdyStreamPrecedence(4, 100, false)); | |
| 678 | |
| 679 // Set all nodes ready to write. | |
| 680 for (SpdyStreamId id = 1; id <= 8; ++id) { | |
| 681 scheduler_.MarkStreamReady(id, false); | |
| 682 } | |
| 683 } | |
| 684 | |
| 685 AssertionResult PopNextReturnsCycle( | |
| 686 std::initializer_list<SpdyStreamId> stream_ids) { | |
| 687 int count = 0; | |
| 688 const int kNumCyclesToCheck = 2; | |
| 689 for (int i = 0; i < kNumCyclesToCheck; i++) { | |
| 690 for (SpdyStreamId expected_id : stream_ids) { | |
| 691 SpdyStreamId next_id = scheduler_.PopNextReadyStream(); | |
| 692 scheduler_.MarkStreamReady(next_id, false); | |
| 693 if (next_id != expected_id) { | |
| 694 return AssertionFailure() << "Pick " << count << ": expected stream " | |
| 695 << expected_id << " instead of " << next_id; | |
| 696 } | |
| 697 if (!peer_.ValidateInvariants()) { | |
| 698 return AssertionFailure() << "ValidateInvariants failed"; | |
| 699 } | |
| 700 ++count; | |
| 701 } | |
| 702 } | |
| 703 return AssertionSuccess(); | |
| 704 } | |
| 705 }; | |
| 706 | |
| 707 // When all streams are schedulable, only top-level streams should be returned. | |
| 708 TEST_F(PopNextReadyStreamTest, NoneBlocked) { | |
| 709 EXPECT_TRUE(PopNextReturnsCycle({1, 2, 3})); | |
| 710 } | |
| 711 | |
| 712 // When a parent stream is blocked, its children should be scheduled, if | |
| 713 // priorities allow. | |
| 714 TEST_F(PopNextReadyStreamTest, SingleStreamBlocked) { | |
| 715 scheduler_.MarkStreamNotReady(1); | |
| 716 | |
| 717 // Round-robin only across 2 and 3, since children of 1 have lower priority. | |
| 718 EXPECT_TRUE(PopNextReturnsCycle({2, 3})); | |
| 719 | |
| 720 // Make children of 1 have equal priority as 2 and 3, after which they should | |
| 721 // be returned as well. | |
| 722 scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(0, 200, false)); | |
| 723 EXPECT_TRUE(PopNextReturnsCycle({4, 5, 2, 3})); | |
| 724 } | |
| 725 | |
| 726 // Block multiple levels of streams. | |
| 727 TEST_F(PopNextReadyStreamTest, MultiLevelBlocked) { | |
| 728 for (SpdyStreamId stream_id : {1, 4, 5}) { | |
| 729 scheduler_.MarkStreamNotReady(stream_id); | |
| 730 } | |
| 731 // Round-robin only across 2 and 3, since children of 1 have lower priority. | |
| 732 EXPECT_TRUE(PopNextReturnsCycle({2, 3})); | |
| 733 | |
| 734 // Make 8 have equal priority as 2 and 3. | |
| 735 scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(0, 200, false)); | |
| 736 EXPECT_TRUE(PopNextReturnsCycle({8, 2, 3})); | |
| 737 } | |
| 738 | |
| 739 // A removed stream shouldn't be scheduled. | |
| 740 TEST_F(PopNextReadyStreamTest, RemoveStream) { | |
| 741 scheduler_.UnregisterStream(1); | |
| 742 | |
| 743 // Round-robin only across 2 and 3, since previous children of 1 have lower | |
| 744 // priority (the weight of 4 and 5 is scaled down when they are elevated to | |
| 745 // siblings of 2 and 3). | |
| 746 EXPECT_TRUE(PopNextReturnsCycle({2, 3})); | |
| 747 | |
| 748 // Make previous children of 1 have equal priority as 2 and 3. | |
| 749 scheduler_.UpdateStreamPrecedence(4, SpdyStreamPrecedence(0, 100, false)); | |
| 750 scheduler_.UpdateStreamPrecedence(5, SpdyStreamPrecedence(0, 100, false)); | |
| 751 EXPECT_TRUE(PopNextReturnsCycle({4, 5, 2, 3})); | |
| 752 } | |
| 753 | |
| 754 // Block an entire subtree. | |
| 755 TEST_F(PopNextReadyStreamTest, SubtreeBlocked) { | |
| 756 for (SpdyStreamId stream_id : {1, 4, 5, 8}) { | |
| 757 scheduler_.MarkStreamNotReady(stream_id); | |
| 758 } | |
| 759 EXPECT_TRUE(PopNextReturnsCycle({2, 3})); | |
| 760 } | |
| 761 | |
| 762 // If all parent streams are blocked, children should be returned. | |
| 763 TEST_F(PopNextReadyStreamTest, ParentsBlocked) { | |
| 764 for (SpdyStreamId stream_id : {1, 2, 3}) { | |
| 765 scheduler_.MarkStreamNotReady(stream_id); | |
| 766 } | |
| 767 EXPECT_TRUE(PopNextReturnsCycle({4, 5, 6, 7})); | |
| 768 } | |
| 769 | |
| 770 // Unblocking streams should make them schedulable. | |
| 771 TEST_F(PopNextReadyStreamTest, BlockAndUnblock) { | |
| 772 EXPECT_TRUE(PopNextReturnsCycle({1, 2, 3})); | |
| 773 scheduler_.MarkStreamNotReady(2); | |
| 774 EXPECT_TRUE(PopNextReturnsCycle({1, 3})); | |
| 775 scheduler_.MarkStreamReady(2, false); | |
| 776 // Cycle order permuted since 2 effectively appended at tail. | |
| 777 EXPECT_TRUE(PopNextReturnsCycle({1, 3, 2})); | |
| 778 } | |
| 779 | |
| 780 // Block nodes in multiple subtrees. | |
| 781 TEST_F(PopNextReadyStreamTest, ScatteredBlocked) { | |
| 782 for (SpdyStreamId stream_id : {1, 2, 6, 7}) { | |
| 783 scheduler_.MarkStreamNotReady(stream_id); | |
| 784 } | |
| 785 // Only 3 returned, since of remaining streams it has highest priority. | |
| 786 EXPECT_TRUE(PopNextReturnsCycle({3})); | |
| 787 | |
| 788 // Make children of 1 have priority equal to 3. | |
| 789 scheduler_.UpdateStreamPrecedence(1, SpdyStreamPrecedence(0, 200, false)); | |
| 790 EXPECT_TRUE(PopNextReturnsCycle({4, 5, 3})); | |
| 791 | |
| 792 // When 4 is blocked, its child 8 should take its place, since it has same | |
| 793 // priority. | |
| 794 scheduler_.MarkStreamNotReady(4); | |
| 795 EXPECT_TRUE(PopNextReturnsCycle({8, 5, 3})); | |
| 796 } | |
| 797 | |
| 798 } // namespace test | |
| 799 } // namespace net | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2791883003:
Remove Http2PriorityWriteScheduler. (Closed)
