1 // Copyright (c) 2012 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 <ctype.h> 6 #include <string> 7 8 #include "base/compiler_specific.h" 9 #include "base/logging.h" 10 #include "base/memory/scoped_ptr.h" 11 #include "base/memory/scoped_vector.h" 12 #include "net/base/prioritized_dispatcher.h" 13 #include "net/base/request_priority.h" 14 #include "testing/gtest/include/gtest/gtest.h" 15 16 namespace net { 17 18 namespace { 19 20 // We rely on the priority enum values being sequential having starting at 0, 21 // and increasing for higher priorities. 22 COMPILE_ASSERT(MINIMUM_PRIORITY == 0u && 23 MINIMUM_PRIORITY == IDLE && 24 IDLE < LOWEST && 25 LOWEST < HIGHEST && 26 HIGHEST <= MAXIMUM_PRIORITY, 27 priority_indexes_incompatible); 28 29 class PrioritizedDispatcherTest : public testing::Test { 30 public: 31 typedef PrioritizedDispatcher::Priority Priority; 32 // A job that appends |tag| to |log| when started and '.' when finished. 33 // This is intended to confirm the execution order of a sequence of jobs added 34 // to the dispatcher. Note that finishing order of jobs does not matter. 35 class TestJob : public PrioritizedDispatcher::Job { 36 public: 37 TestJob(PrioritizedDispatcher* dispatcher, 38 char tag, 39 Priority priority, 40 std::string* log) 41 : dispatcher_(dispatcher), 42 tag_(tag), 43 priority_(priority), 44 running_(false), 45 log_(log) {} 46 47 bool running() const { 48 return running_; 49 } 50 51 const PrioritizedDispatcher::Handle handle() const { 52 return handle_; 53 } 54 55 void Add(bool at_head) { 56 CHECK(handle_.is_null()); 57 CHECK(!running_); 58 size_t num_queued = dispatcher_->num_queued_jobs(); 59 size_t num_running = dispatcher_->num_running_jobs(); 60 61 if (!at_head) { 62 handle_ = dispatcher_->Add(this, priority_); 63 } else { 64 handle_ = dispatcher_->AddAtHead(this, priority_); 65 } 66 67 if (handle_.is_null()) { 68 EXPECT_EQ(num_queued, dispatcher_->num_queued_jobs()); 69 EXPECT_TRUE(running_); 70 EXPECT_EQ(num_running + 1, dispatcher_->num_running_jobs()); 71 } else { 72 EXPECT_FALSE(running_); 73 EXPECT_EQ(priority_, handle_.priority()); 74 EXPECT_EQ(tag_, reinterpret_cast<TestJob*>(handle_.value())->tag_); 75 EXPECT_EQ(num_running, dispatcher_->num_running_jobs()); 76 } 77 } 78 79 void ChangePriority(Priority priority) { 80 CHECK(!handle_.is_null()); 81 CHECK(!running_); 82 size_t num_queued = dispatcher_->num_queued_jobs(); 83 size_t num_running = dispatcher_->num_running_jobs(); 84 85 handle_ = dispatcher_->ChangePriority(handle_, priority); 86 87 if (handle_.is_null()) { 88 EXPECT_TRUE(running_); 89 EXPECT_EQ(num_queued - 1, dispatcher_->num_queued_jobs()); 90 EXPECT_EQ(num_running + 1, dispatcher_->num_running_jobs()); 91 } else { 92 EXPECT_FALSE(running_); 93 EXPECT_EQ(priority, handle_.priority()); 94 EXPECT_EQ(tag_, reinterpret_cast<TestJob*>(handle_.value())->tag_); 95 EXPECT_EQ(num_queued, dispatcher_->num_queued_jobs()); 96 EXPECT_EQ(num_running, dispatcher_->num_running_jobs()); 97 } 98 } 99 100 void Cancel() { 101 CHECK(!handle_.is_null()); 102 CHECK(!running_); 103 size_t num_queued = dispatcher_->num_queued_jobs(); 104 105 dispatcher_->Cancel(handle_); 106 107 EXPECT_EQ(num_queued - 1, dispatcher_->num_queued_jobs()); 108 handle_ = PrioritizedDispatcher::Handle(); 109 } 110 111 void Finish() { 112 CHECK(running_); 113 running_ = false; 114 log_->append(1u, '.'); 115 116 dispatcher_->OnJobFinished(); 117 } 118 119 // PriorityDispatch::Job interface 120 virtual void Start() OVERRIDE { 121 EXPECT_FALSE(running_); 122 handle_ = PrioritizedDispatcher::Handle(); 123 running_ = true; 124 log_->append(1u, tag_); 125 } 126 127 private: 128 PrioritizedDispatcher* dispatcher_; 129 130 char tag_; 131 Priority priority_; 132 133 PrioritizedDispatcher::Handle handle_; 134 bool running_; 135 136 std::string* log_; 137 }; 138 139 protected: 140 void Prepare(const PrioritizedDispatcher::Limits& limits) { 141 dispatcher_.reset(new PrioritizedDispatcher(limits)); 142 } 143 144 TestJob* AddJob(char data, Priority priority) { 145 TestJob* job = new TestJob(dispatcher_.get(), data, priority, &log_); 146 jobs_.push_back(job); 147 job->Add(false); 148 return job; 149 } 150 151 TestJob* AddJobAtHead(char data, Priority priority) { 152 TestJob* job = new TestJob(dispatcher_.get(), data, priority, &log_); 153 jobs_.push_back(job); 154 job->Add(true); 155 return job; 156 } 157 158 void Expect(std::string log) { 159 EXPECT_EQ(0u, dispatcher_->num_queued_jobs()); 160 EXPECT_EQ(0u, dispatcher_->num_running_jobs()); 161 EXPECT_EQ(log, log_); 162 log_.clear(); 163 } 164 165 std::string log_; 166 scoped_ptr<PrioritizedDispatcher> dispatcher_; 167 ScopedVector<TestJob> jobs_; 168 }; 169 170 TEST_F(PrioritizedDispatcherTest, GetLimits) { 171 // Set non-trivial initial limits. 172 PrioritizedDispatcher::Limits original_limits(NUM_PRIORITIES, 5); 173 original_limits.reserved_slots[HIGHEST] = 1; 174 original_limits.reserved_slots[LOW] = 2; 175 Prepare(original_limits); 176 177 // Get current limits, make sure the original limits are returned. 178 PrioritizedDispatcher::Limits retrieved_limits = dispatcher_->GetLimits(); 179 ASSERT_EQ(original_limits.total_jobs, retrieved_limits.total_jobs); 180 ASSERT_EQ(NUM_PRIORITIES, retrieved_limits.reserved_slots.size()); 181 for (size_t priority = MINIMUM_PRIORITY; priority <= MAXIMUM_PRIORITY; 182 ++priority) { 183 EXPECT_EQ(original_limits.reserved_slots[priority], 184 retrieved_limits.reserved_slots[priority]); 185 } 186 187 // Set new limits. 188 PrioritizedDispatcher::Limits new_limits(NUM_PRIORITIES, 6); 189 new_limits.reserved_slots[MEDIUM] = 3; 190 new_limits.reserved_slots[LOWEST] = 1; 191 Prepare(new_limits); 192 193 // Get current limits, make sure the new limits are returned. 194 retrieved_limits = dispatcher_->GetLimits(); 195 ASSERT_EQ(new_limits.total_jobs, retrieved_limits.total_jobs); 196 ASSERT_EQ(NUM_PRIORITIES, retrieved_limits.reserved_slots.size()); 197 for (size_t priority = MINIMUM_PRIORITY; priority <= MAXIMUM_PRIORITY; 198 ++priority) { 199 EXPECT_EQ(new_limits.reserved_slots[priority], 200 retrieved_limits.reserved_slots[priority]); 201 } 202 } 203 204 TEST_F(PrioritizedDispatcherTest, AddAFIFO) { 205 // Allow only one running job. 206 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1); 207 Prepare(limits); 208 209 TestJob* job_a = AddJob('a', IDLE); 210 TestJob* job_b = AddJob('b', IDLE); 211 TestJob* job_c = AddJob('c', IDLE); 212 TestJob* job_d = AddJob('d', IDLE); 213 214 ASSERT_TRUE(job_a->running()); 215 job_a->Finish(); 216 ASSERT_TRUE(job_b->running()); 217 job_b->Finish(); 218 ASSERT_TRUE(job_c->running()); 219 job_c->Finish(); 220 ASSERT_TRUE(job_d->running()); 221 job_d->Finish(); 222 223 Expect("a.b.c.d."); 224 } 225 226 TEST_F(PrioritizedDispatcherTest, AddPriority) { 227 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1); 228 Prepare(limits); 229 230 TestJob* job_a = AddJob('a', IDLE); 231 TestJob* job_b = AddJob('b', MEDIUM); 232 TestJob* job_c = AddJob('c', HIGHEST); 233 TestJob* job_d = AddJob('d', HIGHEST); 234 TestJob* job_e = AddJob('e', MEDIUM); 235 236 ASSERT_TRUE(job_a->running()); 237 job_a->Finish(); 238 ASSERT_TRUE(job_c->running()); 239 job_c->Finish(); 240 ASSERT_TRUE(job_d->running()); 241 job_d->Finish(); 242 ASSERT_TRUE(job_b->running()); 243 job_b->Finish(); 244 ASSERT_TRUE(job_e->running()); 245 job_e->Finish(); 246 247 Expect("a.c.d.b.e."); 248 } 249 250 TEST_F(PrioritizedDispatcherTest, AddAtHead) { 251 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1); 252 Prepare(limits); 253 254 TestJob* job_a = AddJob('a', MEDIUM); 255 TestJob* job_b = AddJobAtHead('b', MEDIUM); 256 TestJob* job_c = AddJobAtHead('c', HIGHEST); 257 TestJob* job_d = AddJobAtHead('d', HIGHEST); 258 TestJob* job_e = AddJobAtHead('e', MEDIUM); 259 TestJob* job_f = AddJob('f', MEDIUM); 260 261 ASSERT_TRUE(job_a->running()); 262 job_a->Finish(); 263 ASSERT_TRUE(job_d->running()); 264 job_d->Finish(); 265 ASSERT_TRUE(job_c->running()); 266 job_c->Finish(); 267 ASSERT_TRUE(job_e->running()); 268 job_e->Finish(); 269 ASSERT_TRUE(job_b->running()); 270 job_b->Finish(); 271 ASSERT_TRUE(job_f->running()); 272 job_f->Finish(); 273 274 Expect("a.d.c.e.b.f."); 275 } 276 277 TEST_F(PrioritizedDispatcherTest, EnforceLimits) { 278 // Reserve 2 for HIGHEST and 1 for LOW or higher. 279 // This leaves 2 for LOWEST or lower. 280 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 5); 281 limits.reserved_slots[HIGHEST] = 2; 282 limits.reserved_slots[LOW] = 1; 283 Prepare(limits); 284 285 TestJob* job_a = AddJob('a', IDLE); // Uses unreserved slot. 286 TestJob* job_b = AddJob('b', IDLE); // Uses unreserved slot. 287 TestJob* job_c = AddJob('c', LOWEST); // Must wait. 288 TestJob* job_d = AddJob('d', LOW); // Uses reserved slot. 289 TestJob* job_e = AddJob('e', MEDIUM); // Must wait. 290 TestJob* job_f = AddJob('f', HIGHEST); // Uses reserved slot. 291 TestJob* job_g = AddJob('g', HIGHEST); // Uses reserved slot. 292 TestJob* job_h = AddJob('h', HIGHEST); // Must wait. 293 294 EXPECT_EQ(5u, dispatcher_->num_running_jobs()); 295 EXPECT_EQ(3u, dispatcher_->num_queued_jobs()); 296 297 ASSERT_TRUE(job_a->running()); 298 ASSERT_TRUE(job_b->running()); 299 ASSERT_TRUE(job_d->running()); 300 ASSERT_TRUE(job_f->running()); 301 ASSERT_TRUE(job_g->running()); 302 // a, b, d, f, g are running. Finish them in any order. 303 job_b->Finish(); // Releases h. 304 job_f->Finish(); 305 job_a->Finish(); 306 job_g->Finish(); // Releases e. 307 job_d->Finish(); 308 ASSERT_TRUE(job_e->running()); 309 ASSERT_TRUE(job_h->running()); 310 // h, e are running. 311 job_e->Finish(); // Releases c. 312 ASSERT_TRUE(job_c->running()); 313 job_c->Finish(); 314 job_h->Finish(); 315 316 Expect("abdfg.h...e..c.."); 317 } 318 319 TEST_F(PrioritizedDispatcherTest, ChangePriority) { 320 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 2); 321 // Reserve one slot only for HIGHEST priority requests. 322 limits.reserved_slots[HIGHEST] = 1; 323 Prepare(limits); 324 325 TestJob* job_a = AddJob('a', IDLE); 326 TestJob* job_b = AddJob('b', LOW); 327 TestJob* job_c = AddJob('c', MEDIUM); 328 TestJob* job_d = AddJob('d', MEDIUM); 329 TestJob* job_e = AddJob('e', IDLE); 330 331 ASSERT_FALSE(job_b->running()); 332 ASSERT_FALSE(job_c->running()); 333 job_b->ChangePriority(MEDIUM); 334 job_c->ChangePriority(LOW); 335 336 ASSERT_TRUE(job_a->running()); 337 job_a->Finish(); 338 ASSERT_TRUE(job_d->running()); 339 job_d->Finish(); 340 341 EXPECT_FALSE(job_e->running()); 342 // Increasing |job_e|'s priority to HIGHEST should result in it being 343 // started immediately. 344 job_e->ChangePriority(HIGHEST); 345 ASSERT_TRUE(job_e->running()); 346 job_e->Finish(); 347 348 ASSERT_TRUE(job_b->running()); 349 job_b->Finish(); 350 ASSERT_TRUE(job_c->running()); 351 job_c->Finish(); 352 353 Expect("a.d.be..c."); 354 } 355 356 TEST_F(PrioritizedDispatcherTest, Cancel) { 357 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1); 358 Prepare(limits); 359 360 TestJob* job_a = AddJob('a', IDLE); 361 TestJob* job_b = AddJob('b', IDLE); 362 TestJob* job_c = AddJob('c', IDLE); 363 TestJob* job_d = AddJob('d', IDLE); 364 TestJob* job_e = AddJob('e', IDLE); 365 366 ASSERT_FALSE(job_b->running()); 367 ASSERT_FALSE(job_d->running()); 368 job_b->Cancel(); 369 job_d->Cancel(); 370 371 ASSERT_TRUE(job_a->running()); 372 job_a->Finish(); 373 ASSERT_TRUE(job_c->running()); 374 job_c->Finish(); 375 ASSERT_TRUE(job_e->running()); 376 job_e->Finish(); 377 378 Expect("a.c.e."); 379 } 380 381 TEST_F(PrioritizedDispatcherTest, Evict) { 382 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1); 383 Prepare(limits); 384 385 TestJob* job_a = AddJob('a', IDLE); 386 TestJob* job_b = AddJob('b', LOW); 387 TestJob* job_c = AddJob('c', HIGHEST); 388 TestJob* job_d = AddJob('d', LOW); 389 TestJob* job_e = AddJob('e', HIGHEST); 390 391 EXPECT_EQ(job_b, dispatcher_->EvictOldestLowest()); 392 EXPECT_EQ(job_d, dispatcher_->EvictOldestLowest()); 393 394 ASSERT_TRUE(job_a->running()); 395 job_a->Finish(); 396 ASSERT_TRUE(job_c->running()); 397 job_c->Finish(); 398 ASSERT_TRUE(job_e->running()); 399 job_e->Finish(); 400 401 Expect("a.c.e."); 402 } 403 404 TEST_F(PrioritizedDispatcherTest, EvictFromEmpty) { 405 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1); 406 Prepare(limits); 407 EXPECT_TRUE(dispatcher_->EvictOldestLowest() == NULL); 408 } 409 410 TEST_F(PrioritizedDispatcherTest, AddWhileZeroLimits) { 411 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 2); 412 Prepare(limits); 413 414 dispatcher_->SetLimitsToZero(); 415 TestJob* job_a = AddJob('a', LOW); 416 TestJob* job_b = AddJob('b', MEDIUM); 417 TestJob* job_c = AddJobAtHead('c', MEDIUM); 418 419 EXPECT_EQ(0u, dispatcher_->num_running_jobs()); 420 EXPECT_EQ(3u, dispatcher_->num_queued_jobs()); 421 422 dispatcher_->SetLimits(limits); 423 EXPECT_EQ(2u, dispatcher_->num_running_jobs()); 424 EXPECT_EQ(1u, dispatcher_->num_queued_jobs()); 425 426 ASSERT_TRUE(job_b->running()); 427 job_b->Finish(); 428 429 ASSERT_TRUE(job_c->running()); 430 job_c->Finish(); 431 432 ASSERT_TRUE(job_a->running()); 433 job_a->Finish(); 434 435 Expect("cb.a.."); 436 } 437 438 TEST_F(PrioritizedDispatcherTest, ReduceLimitsWhileJobQueued) { 439 PrioritizedDispatcher::Limits initial_limits(NUM_PRIORITIES, 2); 440 Prepare(initial_limits); 441 442 TestJob* job_a = AddJob('a', MEDIUM); 443 TestJob* job_b = AddJob('b', MEDIUM); 444 TestJob* job_c = AddJob('c', MEDIUM); 445 TestJob* job_d = AddJob('d', MEDIUM); 446 TestJob* job_e = AddJob('e', MEDIUM); 447 448 EXPECT_EQ(2u, dispatcher_->num_running_jobs()); 449 EXPECT_EQ(3u, dispatcher_->num_queued_jobs()); 450 451 // Reduce limits to just allow one job at a time. Running jobs should not 452 // be affected. 453 dispatcher_->SetLimits(PrioritizedDispatcher::Limits(NUM_PRIORITIES, 1)); 454 455 EXPECT_EQ(2u, dispatcher_->num_running_jobs()); 456 EXPECT_EQ(3u, dispatcher_->num_queued_jobs()); 457 458 // Finishing a job should not result in another job starting. 459 ASSERT_TRUE(job_a->running()); 460 job_a->Finish(); 461 EXPECT_EQ(1u, dispatcher_->num_running_jobs()); 462 EXPECT_EQ(3u, dispatcher_->num_queued_jobs()); 463 464 ASSERT_TRUE(job_b->running()); 465 job_b->Finish(); 466 EXPECT_EQ(1u, dispatcher_->num_running_jobs()); 467 EXPECT_EQ(2u, dispatcher_->num_queued_jobs()); 468 469 // Increasing the limits again should let c start. 470 dispatcher_->SetLimits(initial_limits); 471 472 ASSERT_TRUE(job_c->running()); 473 job_c->Finish(); 474 ASSERT_TRUE(job_d->running()); 475 job_d->Finish(); 476 ASSERT_TRUE(job_e->running()); 477 job_e->Finish(); 478 479 Expect("ab..cd.e.."); 480 } 481 482 TEST_F(PrioritizedDispatcherTest, ZeroLimitsThenCancel) { 483 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1); 484 Prepare(limits); 485 486 TestJob* job_a = AddJob('a', IDLE); 487 TestJob* job_b = AddJob('b', IDLE); 488 TestJob* job_c = AddJob('c', IDLE); 489 dispatcher_->SetLimitsToZero(); 490 491 ASSERT_TRUE(job_a->running()); 492 EXPECT_FALSE(job_b->running()); 493 EXPECT_FALSE(job_c->running()); 494 job_a->Finish(); 495 496 EXPECT_FALSE(job_b->running()); 497 EXPECT_FALSE(job_c->running()); 498 499 // Cancelling b shouldn't start job c. 500 job_b->Cancel(); 501 EXPECT_FALSE(job_c->running()); 502 503 // Restoring the limits should start c. 504 dispatcher_->SetLimits(limits); 505 ASSERT_TRUE(job_c->running()); 506 job_c->Finish(); 507 508 Expect("a.c."); 509 } 510 511 TEST_F(PrioritizedDispatcherTest, ZeroLimitsThenIncreasePriority) { 512 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 2); 513 limits.reserved_slots[HIGHEST] = 1; 514 Prepare(limits); 515 516 TestJob* job_a = AddJob('a', IDLE); 517 TestJob* job_b = AddJob('b', IDLE); 518 EXPECT_TRUE(job_a->running()); 519 EXPECT_FALSE(job_b->running()); 520 dispatcher_->SetLimitsToZero(); 521 522 job_b->ChangePriority(HIGHEST); 523 EXPECT_FALSE(job_b->running()); 524 job_a->Finish(); 525 EXPECT_FALSE(job_b->running()); 526 527 job_b->Cancel(); 528 Expect("a."); 529 } 530 531 #if GTEST_HAS_DEATH_TEST && !defined(NDEBUG) 532 TEST_F(PrioritizedDispatcherTest, CancelNull) { 533 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1); 534 Prepare(limits); 535 EXPECT_DEBUG_DEATH(dispatcher_->Cancel(PrioritizedDispatcher::Handle()), ""); 536 } 537 538 TEST_F(PrioritizedDispatcherTest, CancelMissing) { 539 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1); 540 Prepare(limits); 541 AddJob('a', IDLE); 542 TestJob* job_b = AddJob('b', IDLE); 543 PrioritizedDispatcher::Handle handle = job_b->handle(); 544 ASSERT_FALSE(handle.is_null()); 545 dispatcher_->Cancel(handle); 546 EXPECT_DEBUG_DEATH(dispatcher_->Cancel(handle), ""); 547 } 548 549 // TODO(szym): Fix the PriorityQueue::Pointer check to die here. 550 // http://crbug.com/130846 551 TEST_F(PrioritizedDispatcherTest, DISABLED_CancelIncompatible) { 552 PrioritizedDispatcher::Limits limits(NUM_PRIORITIES, 1); 553 Prepare(limits); 554 AddJob('a', IDLE); 555 TestJob* job_b = AddJob('b', IDLE); 556 PrioritizedDispatcher::Handle handle = job_b->handle(); 557 ASSERT_FALSE(handle.is_null()); 558 559 // New dispatcher. 560 Prepare(limits); 561 AddJob('a', IDLE); 562 AddJob('b', IDLE); 563 EXPECT_DEBUG_DEATH(dispatcher_->Cancel(handle), ""); 564 } 565 #endif // GTEST_HAS_DEATH_TEST && !defined(NDEBUG) 566 567 } // namespace 568 569 } // namespace net 570