net/base/prioritized_dispatcher_unittest.cc

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